Computational complexity of Bayesian inference

1 Setup

• Bayes net = DAG, one random variable per vertex, joint factorizes as \(P(X) = \prod_i P(X_i \mid \mathrm{pa}(X_i))\).
• Inference = compute a conditional \(P(\text{latent} \mid \text{observed})\).
• Problem size = total size of the conditional probability tables.

2 Hardness

• Exact inference is NP-hard(Cooper 1990). Bayes nets can encode SAT; SAT is NP-complete, so generic Bayes-net inference is at least as hard.
• Approximate inference is also NP-hard (Dagum and Luby 1993).
  • absolute approximation: estimate within \(\pm\varepsilon\).
  • relative approximation: estimate within a multiplicative \((1\pm\varepsilon)\) factor.
  • Both are NP-hard deterministically; no randomized polynomial-time algorithm gets either with high probability unless \(\mathrm{NP}=\mathrm{RP}\) (not believed).
• Relative approximation is #P-complete (Roth 1996) — counting-hard, believed strictly harder than NP.

3 Tractable special cases

• Positive result (Dagum and Luby 1997): a randomized polynomial-time algorithm gives a relative approximation if the Local Variance Bound (LVB) is polynomial in network size.
• LVB bounded \(\iff\) conditional probabilities are not extreme (not pushed toward 0/1). Extreme probabilities are what would let us smuggle a SAT instance in.
• Takeaways (Huggins): determinism is the enemy; restrict the distributions, not just the graph structure; the specific conditional we ask for matters; the algorithm is a sampler (MCMC-like).

4 Sampling vs computing

• Sampling from the posterior and computing posterior probabilities are roughly interchangeable in Bayes-net world (Dagum & Luby’s algorithm samples).
• Not true in general: there exist distributions samplable in polynomial time whose density cannot be computed in polynomial time (Yamakami 1999).
• So efficiently-samplable-but-not-computable posteriors are possible — a reason to prefer sampling-based inference.

5 Variational Bayes

• Variational inference does not escape the hardness — it relocates it: integration is replaced by optimization of the ELBO, which is generally non-convex.
• We trade an exactness guarantee for a tractable-but-biased optimization; provable guarantees hold only under certain conditions [@?{Yang Pati alpha variational inference statistical guarantees}]. See variational inference.

6 Complexity classes

• P — solvable in polynomial time (tractable).
• NP — a claimed solution is checkable in polynomial time; finding one is believed hard.
• RP — randomized P: may miss “yes” instances with bounded probability, never wrong on “no”. \(\mathrm{P}=\mathrm{RP}\) is widely believed.
• #P — the counting version of NP: not “is there a solution?” but “how many?”. A #P oracle solves the whole polynomial hierarchy — much harder than NP.
• Polynomial hierarchy — a tower built on NP / co-NP; collapses are not believed.

7 Conjugacy

• Contrast the hardness above with the tractable corner: under a conjugate prior in an exponential family, the posterior stays in the prior’s family and the Bayesian update is a closed-form update of the natural parameters — O(1) per observation, no integration.
• This is the special case classical statistics trains us on, and it badly oversells how easy Bayesian inference is in general.

8 More recent

• Parameterized complexity of Bayesian inference (Bodlaender, Donselaar, and Kwisthout 2022) — which structural parameters make it tractable.
• High-dimensional Bayesian variable selection complexity (Yang, Wainwright, and Jordan 2016).
• Polynomial-time guarantees for sampling-based posterior inference in high-dimensional GLMs [@?{Altmeyer polynomial time guarantees sampling posterior generalised linear models}] — modern positive result on exponential-family models, echoing the sampling-vs-computing point.
• Broader survey: Algorithmic Bayesian Epistemology (Neyman 2024).

9 References