Exponential ergodicity of mirror-Langevin diffusions

Sinho Chewi, Thibaut Le Gouic, Chen Lu, Tyler Maunu, Philippe Rigollet, Austin J. Stromme

Abstract

This paper introduces Newton-Langevin diffusions, a novel class of sampling algorithms designed as the sampling analogue to Newton’s method in optimization. We demonstrate that these diffusions converge to a target distribution exponentially fast with a rate that is dimension-free and independent of the target distribution's specific parameters. This approach provides a robust solution for sampling from ill-conditioned distributions where standard first-order methods typically struggle.

Introduction

Sampling from probability distributions, particularly posteriors in Bayesian inference, is fundamental to modern statistics and machine learning. The Langevin Diffusion (LD) is the standard tool for this task, functioning similarly to gradient descent by moving particles toward high-probability regions. However, LD is highly sensitive to the "conditioning" of the distribution. When a distribution is "stretched" or "squashed" in certain directions, the convergence speed of LD becomes heavily dependent on the condition number and the dimensionality of the space.

While optimization utilizes Newton’s Method to handle ill-conditioning through second-order Hessian information, sampling has historically lacked a similarly robust, affine-invariant counterpart with rigorous theoretical guarantees. This work fills that gap by leveraging the geometry of Mirror-Langevin Diffusions.

Methodology

Our approach is built upon Mirror-Langevin Diffusions (MLD). Similar to mirror descent in optimization, MLD utilizes a "mirror map" $\phi$ to transform the geometry of the space of probability measures.

Newton-Langevin Diffusion (NLD)

We define NLD as a specific instance of MLD where the mirror map is chosen to be the potential function $V$ of the target distribution (where $\pi \propto e^{-V}$). By incorporating the Hessian of the potential, the algorithm effectively "normalizes" the distribution's geometry, allowing it to adapt to local curvature.

Convergence Analysis via Chi-Squared Tracking

Unlike traditional analyses that track convergence using Kullback-Leibler (KL) divergence, we utilize chi-squared ($\chi^2$) divergence. This choice reveals that a "Mirror Poincaré inequality" is the sufficient condition for exponential convergence. We prove that NLD satisfies this inequality with a constant of 1, leading to a remarkably fast convergence rate of $e^{-2t}$ in $\chi^2$ divergence.

Empirical Results

We evaluate the discretized version of our diffusion, the Newton-Langevin Algorithm (NLA), against standard methods like the Unadjusted Langevin Algorithm (ULA) and Tamed ULA (TULA) across several challenging scenarios.

NLA demonstrates superior stability and accuracy in capturing the geometry of an ill-conditioned target distribution compared to ULA and TULA.

Key Findings

  • Dimension-Free Convergence: The convergence rate of NLD does not depend on the dimension $d$ or the specific properties of the potential $V$, provided it is strictly log-concave.
  • Superior Speed: In high-dimensional and ill-conditioned tests, NLA consistently reaches the target distribution orders of magnitude faster than first-order alternatives.
Convergence comparison showing NLA's rapid, exponential decay in error relative to MLA, ULA, and TULA.

Discussion and Limitations

While NLD offers powerful theoretical and empirical advantages, it introduces new challenges. The algorithm requires inverting the Hessian matrix at each step, which can be computationally expensive in extremely high dimensions. This suggests the future development of "Quasi-Newton" sampling variants. Additionally, while the continuous-time diffusion has strong guarantees, further research is needed to formally bound the discretization error introduced by finite step sizes in NLA.

Despite these hurdles, Newton-Langevin diffusions represent a significant step forward in making sampling as robust and affine-invariant as modern optimization.

Summary updated

BibTeX
@inproceedings{chewi2020exponential,
  author = {Sinho Chewi and Thibaut Le Gouic and Chen Lu and Tyler Maunu and Philippe Rigollet and Austin J. Stromme},
  title = {{Exponential ergodicity of mirror-Langevin diffusions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=rRxWxpV4Bec},
}
Figure