Elliptical slice sampling

Iain Murray, Ryan Prescott Adams, David J. C. MacKay

Abstract

Many probabilistic models, such as Gaussian Processes (GPs), introduce strong dependencies between variables through a latent multivariate Gaussian prior. Standard Markov chain Monte Carlo (MCMC) methods often struggle with these dependencies, requiring extensive manual tuning of step-size parameters to achieve efficient sampling. We present Elliptical Slice Sampling (ESS), a simple and robust algorithm designed specifically for models with Gaussian priors. ESS has zero free parameters to tune, yet it performs as well as, or better than, optimally tuned traditional methods by leveraging the inherent geometry of the Gaussian distribution.

The Challenge of Latent Gaussian Models

In models like Gaussian Processes, variables are highly correlated. This structure poses significant hurdles for traditional sampling techniques:

  1. Gibbs Sampling typically fails because updating one variable at a time leads to extremely slow exploration due to high correlation.
  2. Metropolis-Hastings (MH) requires a carefully chosen step-size. A step that is too large leads to frequent rejections, while a step that is too small results in slow, diffusive movement. Finding the "Goldilocks" step size requires tedious preliminary tuning runs that must be repeated whenever the model or data changes.

The Mechanism: Elliptical Geometry and Adaptive Bracketing

Elliptical Slice Sampling addresses these issues by moving along an ellipse in the latent space rather than a straight line. Given a current state $\mathbf{f}$ and a random draw from the Gaussian prior $\boldsymbol{ u}$, the algorithm defines an ellipse: $\mathbf{f}^* = \boldsymbol{ u} \sin \theta + \mathbf{f} \cos \theta$. This ellipse passes through the current state and is mathematically guaranteed to stay within the "high-probability shell" of the Gaussian prior.

The elliptical slice sampling procedure: (a) An ellipse is defined by the current state and a random draw from the prior. (b-e) The algorithm adaptively shrinks the search bracket on the ellipse until a valid point is found.

Instead of a fixed step size, ESS uses a variation of slice sampling. It defines a likelihood threshold and then searches for an angle $\theta$ on the ellipse that satisfies this threshold. If a proposed angle is rejected, the algorithm "shrinks" the search bracket exponentially until a valid point is found. Because it is a slice sampler, it always accepts a new state (provided the likelihood is not zero everywhere), ensuring that no computational effort is wasted on rejected proposals in the traditional sense.

Performance Evaluation

The authors evaluated ESS across several tasks, including synthetic GP regression, USPS handwritten digit classification, and modeling coal-mining disasters using a Log Gaussian Cox process.

A key insight from these experiments is the "Ellipse Advantage." In high dimensions, Gaussian distributions resemble thin spherical shells. Straight-line proposals used in standard MH quickly exit this shell into regions of near-zero probability. By construction, the ellipse stays within the shell, allowing for much larger and more effective moves across the posterior distribution.

Comparison of log-likelihood traces for Control Variables vs. Elliptical Slice Sampling. ESS maintains high likelihood values while the control method fails to explore the posterior effectively.

Key Results and Robustness

  • Efficiency: In GP regression, ESS performed as well as the best possible tuned Metropolis-Hastings without requiring any manual intervention.
  • High-Dimensional Success: On complex tasks like USPS classification, ESS continued to provide effective samples where "Control Variable" methods (relying on low-dimensional approximations) began to fail or became computationally prohibitive.
  • Human Time Savings: While ESS may require more likelihood evaluations per iteration than a perfectly tuned MH sampler, it significantly reduces "human time" by eliminating the need for pilot chains and parameter tuning.

Discussion and Limitations

While ESS is a powerful "drop-in" replacement for Gaussian priors, it has specific limitations. If a model includes a large, unknown constant offset added to the entire latent vector, the prior covariance can become poorly conditioned, causing ESS to struggle. In such cases, modeling offsets as separate variables is recommended. Additionally, because ESS is strictly designed for Gaussian priors, extending its elliptical intuition to other structured or heavy-tailed priors remains a subject for future research.

Summary updated

Abstract

Many probabilistic models introduce strong dependencies between variables using a latent multivariate Gaussian distribution or a Gaussian process. We present a new Markov chain Monte Carlo algorith...
BibTeX
@inproceedings{murray2010elliptical,
  author = {Iain Murray and Ryan Prescott Adams and David J. C. MacKay},
  title = {{Elliptical slice sampling}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2010},
  url = {https://openreview.net/forum?id=NM1Hy31PGsU},
}
Figure