  Expectation propagation (EP) is a deterministic approximation algorithm that
is often used to perform approximate Bayesian parameter learning. EP
approximates the full intractable posterior distribution through a set of local
approximations that are iteratively refined for each datapoint. EP can offer
analytic and computational advantages over other approximations, such as
Variational Inference (VI), and is the method of choice for a number of models.
The local nature of EP appears to make it an ideal candidate for performing
Bayesian learning on large models in large-scale dataset settings. However, EP
has a crucial limitation in this context: the number of approximating factors
needs to increase with the number of data-points, N, which often entails a
prohibitively large memory overhead. This paper presents an extension to EP,
called stochastic expectation propagation (SEP), that maintains a global
posterior approximation (like VI) but updates it in a local way (like EP).
Experiments on a number of canonical learning problems using synthetic and
real-world datasets indicate that SEP performs almost as well as full EP, but
reduces the memory consumption by a factor of $N$. SEP is therefore ideally
suited to performing approximate Bayesian learning in the large model, large
dataset setting.
