Fast Convergent Algorithms for Expectation Propagation Approximate Bayesian Inference

Matthias W. Seeger, Hannes NickischAISTATS 2011 · OpenReview

Abstract

Expectation Propagation (EP) is a powerful framework for approximate Bayesian inference, often yielding more accurate posterior estimates than Variational Bayes (VB). However, its practical application is hindered by convergence instabilities and the high computational cost of calculating marginal variances. This paper presents a novel EP algorithm that combines double-loop optimization with covariance decoupling. The resulting method is provably convergent and achieves speedups of over an order of magnitude compared to standard sequential EP. We demonstrate its effectiveness on large-scale image deblurring and MRI reconstruction tasks, where it provides superior uncertainty quantification.

Introduction

Bayesian inference is considered the "gold standard" for decision-making under uncertainty. However, for complex models, calculating the exact posterior distribution is computationally impossible. Expectation Propagation (EP) is a popular approximation method known for being more accurate than simpler alternatives like Variational Bayes (VB). Despite its accuracy, EP faces two major challenges: instability, as sequential EP has no convergence guarantees, and computational cost, specifically the "variance bottleneck" where calculating marginal variances for large-scale problems (e.g., $n$ pixels in an image) becomes prohibitively expensive.

Methods

The authors introduce a "Fast EP" algorithm by marrying two existing frameworks:

  1. Double-Loop EP: This framework turns EP into a constrained optimization problem, making it provably convergent.
  2. Covariance Decoupling: This technique uses Fenchel duality to "decouple" the calculation of means from the calculation of variances.

The core innovation is the reordering of optimization steps. The algorithm performs "optimistic" updates, solving for the model's means—a relatively inexpensive penalized least squares problem—multiple times while keeping the expensive variances fixed. The full Gaussian variances are only recomputed when necessary to ensure the algorithm continues to descend toward the solution. A rigorous fallback mechanism is included to ensure convergence even if optimistic steps fail.

Original image used as ground truth in deblurring experiments.

Results and Discussion

The algorithm was evaluated on image processing tasks, including image deblurring (reconstructing sharp images from noisy versions using Laplace sparsity priors) and Cartesian MRI reconstruction.

Speed and Scalability

The proposed algorithm is at least 10x faster than standard sequential EP. On a $128 \times 128$ image ($n \approx 16,000$), where sequential methods were infeasible, the new algorithm converged within minutes. Unlike parallel or sequential EP, which can fluctuate, this method shows smooth, monotonic convergence.

Inference Quality

EP consistently provided better variance estimates and more pronounced structures in the posterior marginals compared to VB. While VB is easier to scale, it tends to "over-penalize" and underestimate uncertainty. EP's richer posterior information is critical for tasks like active learning or experimental design.

Posterior marginal variance map produced by the EP algorithm, illustrating the detailed uncertainty information captured.

Conclusion

This research provides a mathematically guaranteed and computationally efficient solver for EP, making high-quality Bayesian inference practical for large-scale problems. Future work includes scaling beyond the $10^4$ latent variable limit imposed by Cholesky decomposition and improving EP's robustness to variance approximations like the Lanczos method.

Summary updated

BibTeX
@inproceedings{seeger2011fast,
  author = {Matthias W. Seeger and Hannes Nickisch},
  title = {{Fast Convergent Algorithms for Expectation Propagation Approximate Bayesian Inference}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2011},
  url = {https://openreview.net/forum?id=Yx95e_cd6z4},
}
Figure