Introduction
In Bayesian machine learning, the central challenge often lies in sampling from intractable posterior distributions. Researchers typically face a trade-off between the asymptotic exactness of Markov Chain Monte Carlo (MCMC) methods and the speed of deterministic approximations like Expectation Propagation (EP) or Variational Bayes (VB). While MCMC methods eventually converge to the true distribution, they are often computationally expensive and difficult to tune. Conversely, deterministic methods are fast but introduce inherent bias by forcing the posterior into a simplified shape, such as a Gaussian.
This paper introduces EPESS, a hybrid inference method that bridges this gap. By leveraging a deterministic Gaussian approximation from EP to "re-center" the Elliptical Slice Sampling (ESS) algorithm, the authors achieve significant improvements in efficiency—up to an order of magnitude—for Bayesian classification and multivariate Gaussian problems.
The Challenge of Elliptical Slice Sampling
Elliptical Slice Sampling (ESS) is a popular MCMC method designed for models with Gaussian priors. However, its performance degrades significantly when the prior and the posterior are poorly aligned. When the likelihood is "strong" (highly informative), the posterior becomes much narrower than the prior. In these scenarios, the ESS sampler spends the majority of its computational budget in "shrinkage" steps—repeatedly narrowing its search window to find a valid point. This leads to high computational costs and poor mixing of the Markov chain.
The EPESS Framework
To address these limitations, the authors propose Expectation Propagation based Elliptical Slice Sampling (EPESS). The core innovation is to use EP to find a Gaussian approximation of the posterior first. This approximation is then treated as the "prior" for a subsequent ESS sampler.
By reformulating the target distribution so that the EP approximation acts as the prior, the remaining "likelihood" term becomes "weak" or nearly constant. ESS thrives in this regime, as the proposal distribution is already a good guess for the target. This allows for much larger moves in the state space and significantly fewer rejected proposals or shrinkage steps.
Advanced Variants: Recycled and Analytic ESS
The paper introduces two key technical enhancements:
- Recycled ESS: Instead of stopping after finding one valid point, the sampler "recycles" the current search bracket to find multiple points ($J > 1$) per iteration. Since the search bracket has already been narrowed to a high-probability region, finding subsequent points is computationally inexpensive.
- Analytic Elliptical Slice Sampling: For specific cases like Truncated Multivariate Gaussians (TMG) with linear constraints, the authors demonstrate that one can analytically solve for the valid regions of the slice. This eliminates iterative shrinkage steps entirely, providing a massive boost in efficiency.
Experimental Evaluation and Results
The authors evaluated EPESS across several standard benchmarks, including Probit regression on UCI datasets (Breast Cancer, Ionosphere, Sonar, and Musk) and synthetic TMG quadrature problems.
Key Findings
- Probit Regression: EPESS outperformed state-of-the-art methods like Hamiltonian Monte Carlo (HMC) and EP-based Metropolis-Hastings (EPMH) by approximately a factor of 5 in terms of effective sample size per function evaluation.
- TMG Quadrature: The Analytic EPESS method outperformed "Exact-HMC" by orders of magnitude, particularly as the truncated region moved further from the origin—a scenario where standard ESS typically fails.
- Inclusive Approximations: The authors argue that EP is a superior partner for MCMC compared to Variational Bayes. While VB is "exclusive" and can trap a sampler in a single local mode, EP is "inclusive," matching global moments and providing a safer, more robust starting point for global sampling.
Limitations and Future Work
The primary limitation of EPESS is its dependency on the accuracy of the initial EP approximation. In experiments involving the Log-Gaussian Cox Process (LGCP), where the EP approximation was inaccurate, EPESS performed no better than standard ESS. Additionally, while standard ESS is tuning-free, Recycled ESS introduces a new parameter ($J$) that requires user discretion.
Future research directions include extending Analytic ESS to more complex, non-linear geometries and exploring the use of "Power EP" to create even more inclusive approximations, potentially further weakening the likelihood term and enhancing sampler performance.
Summary updated