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.
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.
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