Expectation Propagation (Minka, 2001) is a widely successful algorithm for
variational inference. EP is an iterative algorithm used to approximate
complicated distributions, typically to find a Gaussian approximation of
posterior distributions. In many applications of this type, EP performs
extremely well. Surprisingly, despite its widespread use, there are very few
theoretical guarantees on Gaussian EP, and it is quite poorly understood.
In order to analyze EP, we first introduce a variant of EP: averaged-EP
(aEP), which operates on a smaller parameter space. We then consider aEP and EP
in the limit of infinite data, where the overall contribution of each
likelihood term is small and where posteriors are almost Gaussian. In this
limit, we prove that the iterations of both aEP and EP are simple: they behave
like iterations of Newton's algorithm for finding the mode of a function. We
use this limit behavior to prove that EP is asymptotically exact, and to obtain
other insights into the dynamic behavior of EP: for example, that it may
diverge under poor initialization exactly like Newton's method. EP is a simple
algorithm to state, but a difficult one to study. Our results should facilitate
further research into the theoretical properties of this important method.
%0 Generic
%1 dehaene2015expectation
%A Dehaene, Guillaume
%A Barthelmé, Simon
%D 2015
%K bayesian optimization tutorial
%T Expectation Propagation in the large-data limit
%U http://arxiv.org/abs/1503.08060
%X Expectation Propagation (Minka, 2001) is a widely successful algorithm for
variational inference. EP is an iterative algorithm used to approximate
complicated distributions, typically to find a Gaussian approximation of
posterior distributions. In many applications of this type, EP performs
extremely well. Surprisingly, despite its widespread use, there are very few
theoretical guarantees on Gaussian EP, and it is quite poorly understood.
In order to analyze EP, we first introduce a variant of EP: averaged-EP
(aEP), which operates on a smaller parameter space. We then consider aEP and EP
in the limit of infinite data, where the overall contribution of each
likelihood term is small and where posteriors are almost Gaussian. In this
limit, we prove that the iterations of both aEP and EP are simple: they behave
like iterations of Newton's algorithm for finding the mode of a function. We
use this limit behavior to prove that EP is asymptotically exact, and to obtain
other insights into the dynamic behavior of EP: for example, that it may
diverge under poor initialization exactly like Newton's method. EP is a simple
algorithm to state, but a difficult one to study. Our results should facilitate
further research into the theoretical properties of this important method.
@misc{dehaene2015expectation,
abstract = {Expectation Propagation (Minka, 2001) is a widely successful algorithm for
variational inference. EP is an iterative algorithm used to approximate
complicated distributions, typically to find a Gaussian approximation of
posterior distributions. In many applications of this type, EP performs
extremely well. Surprisingly, despite its widespread use, there are very few
theoretical guarantees on Gaussian EP, and it is quite poorly understood.
In order to analyze EP, we first introduce a variant of EP: averaged-EP
(aEP), which operates on a smaller parameter space. We then consider aEP and EP
in the limit of infinite data, where the overall contribution of each
likelihood term is small and where posteriors are almost Gaussian. In this
limit, we prove that the iterations of both aEP and EP are simple: they behave
like iterations of Newton's algorithm for finding the mode of a function. We
use this limit behavior to prove that EP is asymptotically exact, and to obtain
other insights into the dynamic behavior of EP: for example, that it may
diverge under poor initialization exactly like Newton's method. EP is a simple
algorithm to state, but a difficult one to study. Our results should facilitate
further research into the theoretical properties of this important method.},
added-at = {2016-04-01T07:03:07.000+0200},
author = {Dehaene, Guillaume and Barthelmé, Simon},
biburl = {https://www.bibsonomy.org/bibtex/28d81a2058b1cf0e1f302ee5ac95a0e16/pixor},
description = {1503.08060v2.pdf},
interhash = {6d8fd3a5b4e9b249e2d9aa33e4400620},
intrahash = {8d81a2058b1cf0e1f302ee5ac95a0e16},
keywords = {bayesian optimization tutorial},
note = {cite arxiv:1503.08060v2.pdf},
timestamp = {2016-04-01T07:03:07.000+0200},
title = {Expectation Propagation in the large-data limit},
url = {http://arxiv.org/abs/1503.08060},
year = 2015
}