Source-linked AI summary
Stochastic Expectation Propagation
Yingzhen Li, Jose Miguel Hernandez-Lobato, Richard E. Turner
TL;DR
EP’s local approximating factors make its memory overhead grow with dataset size, limiting its use on large datasets. SEP keeps a global posterior approximation but updates it locally, and experiments report accuracy competitive with EP alongside substantially lower memory use.
Problem
EP requires a separate approximating factor for each datapoint, so its memory overhead grows with N and can become prohibitive on large datasets.
Source: §1 · p. 1Method
SEP ties the local approximating factors into a global posterior approximation and updates it using local, damped stochastic estimates.
Source: §1 · p. 2Results
Takeaways & Limitations
SEP offers a way to reduce EP’s memory demands while retaining competitive accuracy across the reported Bayesian learning experiments.
Source: §6 · p. 8Whether there are more direct relationships between EP and SEP remains an open question.
Source: §4.1 · p. 4
Abstract
from arXiv · showhide
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.
1 Introduction
EP’s local updates seem attractive for large datasets, but storing a separate approximating factor for every datapoint makes its memory cost grow with N. SEP aims to retain local computation with a global approximation, reducing that memory burden while preserving accuracy.
1 Introduction
- EP refines local factors for individual datapoints, making its computations easy to parallelise and distribute, with good practical performance on small-data applications.Source: §1 · p. 1
- EP’s per-datapoint approximating factors make its memory overhead grow with N, while VI refines a global approximation directly and avoids that scaling.Source: §1 · p. 1
- VI’s variational free-energy approaches can be biased, and may be poorly suited to models with non-smooth likelihoods, motivating EP for some applications.Source: §1 · p. 1
- Existing scaling approaches include storing all factors, using ADF with poorly calibrated uncertainties, simplifying factors while retaining N-scaling, or grouping datapoints for coarse-grained updates.Low-rank Gaussian factors, for example, reduce storage from O(ND^2) to O(ND) but still scale with N.Source: §1 · p. 2
- SEP maintains a global approximation updated locally using damped stochastic estimates on data subsamples, reducing EP’s memory footprint by a factor of N.The paper also extends the method to control approximation granularity and handle latent-variable models.Source: §1 · p. 2
2 Expectation Propagation and Assumed Density Filtering
EP iteratively refines local approximating factors using cavity distributions, while ADF omits factor removal and maintains only a global approximation. EP’s explicit factors create memory costs that scale with the dataset size; ADF’s updates can instead cause posterior variance to collapse.
2 Expectation Propagation and Assumed Density Filtering
- Because EP’s updates are coupled through the cavity distributions, the factor updates must be iterated.Source: §2 · p. 2
- EP updates one factor at a time by forming a cavity distribution, adding the corresponding likelihood to obtain a tilted distribution, and projecting to update the factor.For exponential-family approximations, the KL minimisation reduces to moment matching.Source: §2 · p. 2
- EP must store each approximating factor to remove it when computing a cavity, giving its memory footprint O(N).Source: §2 · p. 3
- ADF avoids storing local factors by replacing the cavity with the full approximation, but repeated updates over-count factors and shrink posterior variance toward zero.Early stopping is required to prevent overfitting, and ADF generally gives poorly calibrated uncertainty estimates.Source: §2 · p. 3
3 Stochastic Expectation Propagation
SEP ties the local approximating factors into one global factor and updates it using EP-like local computations. Damping lets each datapoint contribute a partial update, while the global representation reduces memory use relative to EP.
3 Stochastic Expectation Propagation
- SEP ties EP’s approximating factors into a single global factor, combining local updates with a global approximation and reduced memory demands.It can also be viewed as a corrected ADF that prevents overfitting.Source: §3 · p. 3
- SEP forms a cavity by removing one copy of the shared factor, computes a tilted distribution with the datapoint likelihood, and moment-matches an intermediate factor.Source: §3 · p. 3
- SEP damps the factor update because the intermediate factor captures only one likelihood’s effect; a natural learning rate is ϵ = 1/N.Other learning rates, including ones decreasing according to the Robbins-Monro condition, may be appropriate.Source: §3 · pp. 3–4
- With Gaussian approximating factors, SEP reduces EP storage from O(ND^2) to O(D^2).Source: §3 · p. 4
4 Algorithmic extensions to SEP and theoretical results
The section extends SEP through parallel updates and links to variational methods, while also varying approximation granularity and applying SEP to latent-variable models.
4.1 Parallel SEP: relating the EP fixed points to SEP
- Parallel SEP uses identical minibatch cavities and combines projected intermediate factors, spanning SEP at M=1 to Averaged EP at M=N.The intermediate projections form an inner loop and their combination an outer loop.Source: §4.1 · p. 4
- Under Robbins-Monro rates SEP shares AEP fixed points and, under AEP’s restrictive conditions, EP’s; a more direct SEP–EP relationship remains open.The stated AEP conditions include log-concave likelihoods that vary slowly with the parameters.Source: §4.1 · p. 4
4.2 Stochastic power EP: relationships to variational methods
- SEP’s global-form replacement yields SVMP, an SVI instance sharing VI’s fixed points under Robbins-Monro rates, and extends to power EP with care at limits.The section notes that interpreting the alpha-divergence as it approaches −1 requires care.Source: §4.2 · pp. 4–5, Figure 2 · p. 5
4.3 Distributed SEP: controlling granularity of the approximation
- Partitioning data into K groups gives each group an approximating factor, interpolating between SEP at K=1 and EP at K=N to accommodate differing likelihood contributions.The passage contrasts this with distributed EP updates, which require multiple likelihood terms and may need additional approximations.Source: §4.3 · p. 5
4.4 SEP with latent variables
- For latent-variable models, SEP ties parameter factors globally while retaining local hidden-variable factors that need not be stored, though nonanalytic updates may increase computation time.When updates for the local factors are nonanalytic, they are initialized from scratch at each update.Source: §4.4 · p. 5
5 Experiments
Across synthetic and real-world classification, clustering, and neural-network regression experiments, SEP generally approaches EP’s accuracy while using a global approximation. The experiments also show that performance depends on data structure and that memory savings can be substantial.
5 Experiments
- The experiments evaluated SEP across synthetic and real-world datasets, small and large scales, and probit regression, mixture-of-Gaussians clustering, and Bayesian neural networks.The neural-network tests used probabilistic backpropagation on regression datasets.Source: §5 · p. 6, §5.3 · p. 7
5.1 Bayesian probit regression
- On synthetic probit data, SEP approached EP on Gaussian inputs but was slightly worse on mixture-of-Gaussians inputs; finer-grained factors helped when grouped by mixture component.Retaining more factors than the number of clusters generally offered no advantage.Source: §5.1 · p. 6
- On MNIST odd-versus-even classification, DSEP significantly outperformed ADF and approached full EP, reducing memory to 0.001% of EP without substantially losing accuracy.DSEP used one global approximating factor per digit class; SEP accuracy was still increasing at the end of learning.Source: §5.1 · p. 6
- On six UCI binary-classification datasets, SEP performed very similarly to EP in test log-likelihood, while EP substantially outperformed ADF.The authors attribute ADF’s poor test log-likelihood to poorly approximated posterior variance despite reasonable mean classification error.Source: §5.1 · p. 6, Table 1 · p. 7
5.2 Mixture of Gaussians for clustering
- For a synthetic mixture-of-Gaussians clustering task, SEP captured uncertainty and produced approximations nearly identical to EP; ADF collapsed toward a point estimate.The comparison approximated the joint posterior over cluster means and cluster identities, with other parameters assumed known.Source: §5.2 · p. 7
5.3 Probabilistic backpropagation
- SEP typically performed similarly to EP or outperformed it in probabilistic backpropagation, with memory reductions reaching 65,107Mb on Year Prediction MSD.ADF often outperformed EP in this setting, possibly because PBP’s additional moment approximation is more accurate with more factors.Source: §5.3 · pp. 7–8, Table 2 · p. 8
6 Conclusions and future work
The paper presents SEP as a way to reduce EP’s memory use while maintaining competitive accuracy. It identifies future work on data partitioning, minibatches, theoretical understanding, and systematic comparisons with variational methods.
6 Conclusions and future work
- Experiments on probit regression and mixture-of-Gaussians clustering found SEP competitive with EP, while large real-world probabilistic backpropagation experiments showed comparable performance with a much smaller memory footprint.The paper connects SEP with assumed density filtering, variational message passing, variational inference, stochastic variational inference, and averaged EP.Source: §6 · p. 8
- Future experiments will study data partitioning for finer-grained DSEP approximations and minibatch updates.DSEP showed promising experimental performance.Source: §6 · p. 8
- The authors identify limited convergence results for SEP and EP and call for theoretical study and systematic comparisons to guide method choice.Source: §6 · p. 8
Stochastic Expectation Propagation: Supplementary
The supplement develops power EP and alpha-EP connections, then relates stochastic VMP to SVI. It shows that SVI with learning rate 1/N is equivalent to stochastic VMP.
A.1 Power EP and alpha-EP
- For β < ∞, converged power EP with power 1/β returns a local optimum of the α-divergence at α = −1 + 2/β, but excludes α = −1 (β = ∞), so VMP is not its special case.Source: §A.1 · p. 10
A.2 Connecting SVMP to SVI
- VMP computes expected sufficient statistics using the current global parameter, then forms and zeros an ELBO gradient to obtain a local update.The global natural parameter combines the prior parameter with contributions from the local updates.Source: §A.2 · p. 11
- With learning rate ϵ = 1/N, SVI and stochastic VMP produce the same global parameter update.In practice, the supplement describes a damped update and gives 1/N as a typical step size.Source: §A.2 · p. 11
A.3 SEP from a global approximation perspective
The supplement interprets SEP as stochastic global optimization of an alpha-divergence while retaining local computations. At convergence, however, SEP/AEP need not globally minimize that divergence.
A.3 SEP from a global approximation perspective
- SEP can be viewed as stochastic optimization of Dα[p(θ|{x_n}^N)||q(θ)] with α = −1 + 2/N.The interpretation connects the AEP inner loop to PEP with power 1/N, treating f(θ)^N as a composite likelihood factor.Source: §A.3 · p. 12
- SEP/AEP convergence does not generally minimize the global alpha-divergence, because the outer loop averages intermediate natural parameters rather than following its gradient.Local and global alpha-divergence optimization have matching fixed points only at α = −1.Source: §A.3 · p. 12
- Under Robbins–Monro learning rates, the fixed points of averaged EP are also fixed points of stochastic EP.The supplement states the corresponding fixed-point condition for stochastic PEP when α ≠ −1.Source: §A.3 · p. 12
B.1 Distributed computing methods
The supplement describes distributed SEP/AEP variants and extends SEP's memory-saving factor tying to latent-variable models. Local hidden-variable factors can be omitted from memory in suitable settings.
B.1 Distributed computing methods
- DEP uses sampling for the projection step on each data partition, whereas DSEP/DAEP retain deterministic computations.DEP partitions the dataset and approximates each partition's likelihood with a local factor.Source: Figure 2 · p. 13, §B.1 · p. 13
- DSEP/DAEP run SEP/AEP within each partition, modifying only copies of the corresponding subset's factors.Their approximate posterior uses partition factors raised to the partition size, with each factor approximating that subset's likelihood.Source: §B.1 · p. 13
B.2 SEP with latent variables
- For simple latent-variable models, SEP can avoid storing local hidden-variable factors, reducing memory by a factor of N.This applies when hidden-variable moments can be computed analytically; if moment computation requires an expensive inner optimization, retaining the factors may be preferable.Source: §B.2 · pp. 13–14
- For a latent variable shared within a subset D_k, the described construction reduces memory by a factor of N/K.The supplement represents its approximate posterior as q(h_k) ∝ p0(h_k)g_k(h_k)^N_k.Source: §B.2 · p. 14
C.1 Details of Bayesian neural network tests
On neural-network regression tests, SEP attained similar accuracies to EP while requiring substantially less memory. With sampling-based moments, SEP also performed almost as well as EP.
C.1 Details of Bayesian neural network tests
- The neural-network tests used one-hidden-layer networks, 40 passes over training data, and 90/10 random train-test splits.Splitting was repeated 20 times except on Year Prediction MSD and Protein Structure, where it was performed once and five times, respectively.Source: §C.1 · p. 14
- SEP attained similar accuracies to EP while using 2.7GB of memory on Year Prediction MSD, compared with an EP test run on a machine with more than 100GB RAM.The SEP figure includes 1.9GB for dataset storage; the authors report savings of tens of gigabytes on this dataset.Source: §C.1 · p. 14
C.2 Stochastic EP with sampling protocal
- SEP performed almost as well as EP when moments were computed by sampling on the sigmoid-regression tests.The tests used 20 random data partitions; AEP was indistinguishable from DEP and reduced memory by a factor of K.Source: §C.2 · p. 15, Figure 3 · p. 15
C.3 Further Comparisons for SEP, DSEP and full EP
On kernel probit regression, SEP, DSEP, and full EP performed similarly, with their results becoming indistinguishable as the dataset grew. Under 10% label flips, SEP was almost as robust as DSEP and EP, though when SEP gives poor approximations remains future work.
C.3 Further Comparisons for SEP, DSEP and full EP
- An XOR kernel-probit test examined heterogeneous likelihood contributions, with DSEP partitioning data by four cluster centroids and results averaged over 10 repetitions.The kernel used an RBF width of 1.0, and the study evaluated training sets of 10, 20, and 50 examples per cluster.Source: §C.3 · p. 15
- With 10% of training labels flipped, SEP was almost as robust as DSEP and EP; tested outlier types yielded no case where EP or DSEP significantly outperformed SEP.Figure 5 shows the label-flip comparison.Source: §C.3 · p. 15, Figure 5 · p. 17
- Future work remains to characterize when SEP gives poor approximations and whether it fails in the same way as EP, which can fail to converge.Source: §C.3 · p. 15
- On kernel probit, SEP was slightly better on classification error, EP had the best test log-likelihood, and DSEP was very similar; differences vanished as N grew.Table 2 reports average test results, and Figure 4 compares predictions as training data size increases.Source: §C.3 · p. 15, Table 2 · p. 16, Figure 4 · p. 16