Abstract
Sampling from high-dimensional, non-log-concave distributions is a central challenge in machine learning and statistics. This paper provides new theoretical guarantees for the Unadjusted Langevin Algorithm (ULA), demonstrating that it converges rapidly under isoperimetric conditions such as the Log-Sobolev Inequality (LSI) or Poincaré inequality. By relaxing the standard assumption of log-concavity, this work establishes a more robust foundation for Langevin-based sampling in complex, non-convex energy landscapes. The authors utilize a one-step interpolation technique to bound discretization error and asymptotic bias, showing that isoperimetry is the fundamental property governing convergence in KL and Rényi divergence.
Introduction
The task of sampling from a probability distribution $\nu \propto e^{-f}$ is fundamental to Bayesian inference and optimization. While the convergence of sampling algorithms is well-understood for log-concave distributions (where $f$ is convex), many practical applications involve "messy," non-convex landscapes. The Unadjusted Langevin Algorithm (ULA) is widely used due to its simplicity and reliance only on the gradient $\nabla f$. However, as a discrete-time approximation of continuous Langevin dynamics, ULA introduces an inherent bias.
The primary contribution of this work is proving that log-concavity is not a necessary condition for fast convergence. Instead, functional inequalities like LSI—which relate the variance or entropy of a distribution to its gradient information—suffice to ensure that the sampler does not get trapped in local minima or bottlenecks. This is significant because isoperimetry is preserved under small perturbations, whereas log-concavity is easily destroyed.
Methods
The authors analyze ULA using a "one-step interpolation" technique, comparing the discrete update of the algorithm to the continuous-time Langevin process over a single time step. The analysis relies on three main pillars:
- Isoperimetric Inequalities: The target distribution is assumed to satisfy either a Log-Sobolev Inequality (LSI) or a Poincaré Inequality. These conditions ensure the distribution is well-connected, preventing the sampler from becoming stuck in deep "wells."
- Smoothness Constraints: The potential $f$ is assumed to be $L$-smooth (bounded Hessian), which is necessary to control the discretization error. The authors also show that third-order smoothness of $f$ is enough to bound the bias in Fisher information.
- Divergence Analysis: Convergence is measured using Kullback-Leibler (KL) divergence and Rényi divergence. The latter provides stronger control over the tails of the distribution and is significantly harder to prove.
Key Results
The paper establishes several significant bounds for ULA performance:
- KL Convergence: Under LSI with constant $\alpha$, ULA with step size $\eta$ reaches an error $\delta$ in KL divergence after roughly $k = \tilde{O}\left(\frac{L^2 n}{\alpha^2 \delta}\right)$ iterations.
- Asymptotic Bias: The authors provide an explicit bound for the asymptotic bias: $H_\nu(\nu_\eta) \le \frac{8nL^2\eta}{\alpha}$. This shows the bias scales linearly with the step size $\eta$ and the dimension $n$.
- Rényi Convergence: If the biased limit of the algorithm satisfies isoperimetry, ULA converges exponentially fast to that limit in Rényi divergence.
- Poincaré vs. LSI: While the Poincaré inequality is a weaker assumption, it leads to slower convergence (initially linear rather than exponential) and a worse dependence on the dimension $n$.
Discussion
This work shifts the focus from geometric properties like convexity to functional properties like isoperimetry. This is a significant theoretical advancement because isoperimetric constants are often more stable under small perturbations than log-concavity.
However, several open questions remain. The current bias bound scales linearly with $\eta$, whereas Gaussian examples suggest a quadratic $\eta^2$ scaling might be possible. Additionally, the dependence on the condition number $\kappa = L/\alpha$ is currently quadratic; improving this to a linear dependence remains a challenge. Finally, while the paper proves convergence for the biased limit under certain conditions, verifying these assumptions for general non-convex targets is a key area for future research.
Summary updated