Fast Convergent Algorithms for Expectation Propagation Approximate Bayesian Inference

A growing number of challenging machine learning applications require decision-making from incomplete data (e.g., stochastic optimization, active sampling, robotics), which relies on quantitative representations of uncertainty (e.g., Bayesian posterior, belief state) and is out of reach of the commonly used paradigm of learning as point estimation on hand-selected data. While Bayesian inference is harder than point estimation in general, it can be relaxed to variational optimization problems which can be computationally competitive, if only they are treated with the algorithmic state-of-the-art established for the latter. In this paper, we propose a novel algorithm for the expectation propagation (EP; or adaptive TAP, or expectation consistent (EC)) relaxation [11, 8, 12], which is both much faster than the commonly used sequential EP algorithm, and is provably convergent (the sequential algorithm lacks such a guarantee). Our method builds on the convergent double loop algorithm of [12], but runs orders of magnitude faster. We gain a deeper understanding of EP (or EC) as optimization problem, unifying it with covariance decoupling ideas [19, 10], and allowing for "point estimation" algorithmic progress to be brought to bear on this powerful approximate inference formulation.