Computational complexity of Bayesian inference

February 28, 2025 — February 28, 2025

Bayes
how do science
statistics

Suspiciously similar content

Figure 1

Jonathan Huggins summarizes: Complexity of Inference in Bayesian Networks.

To cover: Sampling from a posterior measure versus calculating, it, approximation versus exact computation. Graphical models. What does calculation even mean on arbitrary measure spaces?

1 References

Bodlaender, Donselaar, and Kwisthout. 2022. “Parameterized Complexity Results for Bayesian Inference.”
Cooper. 1990. “The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks.” Artificial Intelligence.
Dagum, and Luby. 1993. “Approximating Probabilistic Inference in Bayesian Belief Networks Is NP-Hard.” Artificial Intelligence.
———. 1997. “An Optimal Approximation Algorithm for Bayesian Inference.” Artificial Intelligence.
Roth. 1996. “On the Hardness of Approximate Reasoning.” Artificial Intelligence.
Yamakami. 1999. “Polynomial Time Samplable Distributions.” Journal of Complexity.
Yang, Wainwright, and Jordan. 2016. “On the Computational Complexity of High-Dimensional Bayesian Variable Selection.” The Annals of Statistics.