Bounding errors of Expectation-Propagation
Expectation Propagation is a very popular algorithm for variational inference, but comes with few theoretical guarantees. In this article, we prove that the approximation errors made by EP can be bounded. Our bounds have an asymptotic interpretation in the number n of datapoints, which allows us to study EP's convergence with respect to the true posterior. In particular, we show that EP converges at a rate of O(n −2 ) for the mean, up to an order of magnitude faster than the traditional Gaussian approximation at the mode. We also give similar asymptotic expansions for moments of order 2 to 4, as well as excess Kullback-Leibler cost (defined as the additional KL cost incurred by using EP rather than the ideal Gaussian approximation). All these expansions highlight the superior convergence properties of EP. Our approach for deriving those results is likely applicable to many similar approximate inference methods. In addition, we introduce bounds on the moments of log-concave distributions that may be of independent interest.
The paper derives inference bounds for the Expectation-Propagation (EP) algorithm in variational inference. The results are developed for log-concave distributions with slowly-changing logs, relating the finite-sample bounds to these obtained via Bernstein-von Mises limits for the Canonical Gaussian Approximation (CGA). Kullback-Leibler divergence costs of EP versus CGA are also discussed. EP is a popular method that works well in practice but comes with few theoretical guarantees, so these developments are of interest.There are of course several directions in which these results could be improved, which the authors already discuss. In practice, the current results are still restrictive, but they are certainly a step in the right direction. My main discussion point is that EP is often more powerful for prediction than inference, but the paper only discusses inference approximation bounds. I expect that, even in cases when the sites are not log-concave, EP could perform badly in inference but reasonably in prediction. In that sense, the current bounds are not as interesting as they could be. Some minor points:* the notation $\phi_p$ to denote $\sum \phi_i$ is a bit confusing. * many of the formulae don't have punctuation marks at the end.* The authors could cite "Expectation propagation as a way of life" by Andrew Gelman, Aki Vehtari, Pasi Jylaenki, Christian Robert, Nicolas Chopin, John P. Cunningham. * The references should be cleaned up.