Elliptical slice sampling

Iain Murray, Ryan P. Adams, David Mackay

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 algorithm for performing inference in models with multivariate Gaussian priors. Its key properties are: 1) it has simple, generic code applicable to many models, 2) it has no free parameters, 3) it works well for a variety of Gaussian process based models. These properties make our method ideal for use while model building, removing the need to spend time deriving and tuning updates for more complex algorithms.

Introduction

Probabilistic models, particularly those utilizing Gaussian Processes (GPs), often involve complex dependencies between latent variables. Sampling from the posterior distributions of these models using standard Markov chain Monte Carlo (MCMC) methods presents significant challenges. Gibbs sampling is frequently inefficient because the tight coupling of variables leads to slow exploration of the state space. Metropolis-Hastings (MH) requires careful tuning of the proposal step size; a step size that is too large results in high rejection rates, while one that is too small leads to slow mixing. This manual tuning process is a significant bottleneck in model development.

The Elliptical Slice Sampling Algorithm

Elliptical slice sampling addresses these issues by leveraging the geometry of the Gaussian prior. Unlike standard slice sampling, which moves along a straight line, this algorithm defines an ellipse in the latent space.

The elliptical slice sampling procedure: (a) An initial state (cross) and a prior draw define an ellipse. (b-e) The algorithm adaptively searches for a new state (blue dot) by shrinking a bracket on the ellipse until a point with sufficient likelihood is found.

The algorithm proceeds as follows:

  1. Ellipse Construction: Given a current state $\mathbf{f}$ and an auxiliary draw $\boldsymbol{\nu}$ from the Gaussian prior, a full ellipse is defined. Any point on this ellipse has the same prior probability as the original points.
  2. Prior-Preserving Rotations: The transformation $\mathbf{f}' = \mathbf{f} \cos \theta + \boldsymbol{\nu} \sin \theta$ is a rotation that leaves the Gaussian prior invariant. This allows the algorithm to focus entirely on satisfying the likelihood constraints.
  3. Adaptive Bracketing: The algorithm uses slice sampling to select an angle $\theta$. If a proposed point has a low likelihood, the search bracket is exponentially shrunk until an acceptable state is found. This mechanism eliminates the need for user-defined parameters.

Experimental Evaluation

The authors evaluated the algorithm across several benchmarks:

  • Synthetic GP Regression: Testing scaling and correctness across 1D to 10D datasets.
  • USPS Digit Classification: A real-world benchmark using logistic Gaussian Processes.
  • Coal-Mining Disasters: A Log Gaussian Cox process modeling event rates over time.

Results and Discussion

Elliptical slice sampling demonstrates superior efficiency compared to traditional methods. It consistently produces more effective samples than perfectly tuned Metropolis-Hastings. Notably, in high-dimensional spaces where standard methods often fail to move, elliptical slice sampling remains robust.

Comparison of log-likelihood exploration between control variables and elliptical slice sampling. The elliptical method provides consistent exploration without the need for manual parameter tuning.

The "set-it-and-forget-it" nature of the algorithm is a primary advantage. While there is a computational cost associated with drawing from the Gaussian prior ($O(N^2)$ or $O(N^3)$), the savings in "human time" spent tuning parameters often outweighs the CPU overhead. The method serves as a reliable drop-in replacement for Gibbs and MH across various likelihood models, including Gaussian, Logistic, and Poisson.

Conclusion

Elliptical slice sampling provides a robust, parameter-free alternative for inference in models with multivariate Gaussian priors. By staying within the high-probability "shell" of the Gaussian distribution through elliptical moves, it achieves efficient exploration in high-dimensional spaces where other methods struggle. Its simplicity and lack of tuning requirements make it an ideal tool for rapid model prototyping and 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 algorithm for performing inference in models with multivariate Gaussian priors. Its key properties are: 1) it has simple, generic code applicable to many models, 2) it has no free parameters, 3) it works well for a variety of Gaussian process based models. These properties make our method ideal for use while model building, removing the need to spend time deriving and tuning updates for more complex algorithms.
BibTeX
@inproceedings{murray2010elliptical,
  author = {Iain Murray and Ryan P. Adams and David Mackay},
  title = {{Elliptical slice sampling}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2010},
  url = {https://openreview.net/forum?id=NM1Hy31PGsU},
}
Figure