Convergence of Langevin MCMC in KL-divergence

Xiang Cheng; Peter Bartlett

Source-linked AI summary

Convergence of Langevin MCMC in KL-divergence

Xiang Cheng, Peter Bartlett

arXiv:1705.09048v2May 25, 2017stat.ML

TL;DR

The paper studies sampling from densities with unknown normalizing constants and establishes convergence of discrete Langevin diffusion in KL-divergence. It also derives convergence results in total variation and 2-Wasserstein distance, while noting a limitation without strong convexity.

Problem
Sampling can involve densities whose normalizing constants are unknown or computationally intractable.
Method
The analysis treats Langevin diffusion through its gradient-flow relationship with the Fokker–Planck equation.
Results
The paper establishes convergence in KL-divergence and obtains convergence rates in total variation and 2-Wasserstein distance.
Takeaways & Limitations
KL-divergence convergence provides a stronger guarantee while yielding corresponding total-variation and 2-Wasserstein convergence results.
Takeaways & Limitations
Without strong convexity, the analysis does not obtain a 2-Wasserstein bound from the objective-gap argument used under strong convexity.

Abstract

from arXiv · show

Langevin diffusion is a commonly used tool for sampling from a given distribution. In this work, we establish that when the target density $p^*$ is such that $\log p^*$ is $L$ smooth and $m$ strongly convex, discrete Langevin diffusion produces a distribution $p$ with $KL(p||p^*)\leq ε$ in $\tilde{O}(\frac{d}ε)$ steps, where $d$ is the dimension of the sample space. We also study the convergence rate when the strong-convexity assumption is absent. By considering the Langevin diffusion as a gradient flow in the space of probability distributions, we obtain an elegant analysis that applies to the stronger property of convergence in KL-divergence and gives a conceptually simpler proof of the best-known convergence results in weaker metrics.

1 Introduction

The paper studies sampling from a density whose normalizing constant is unknown and analyzes discrete Langevin diffusion through convergence in KL-divergence.

The target density is known up to a normalizing constant, which can be computationally intractable in variational inference.
Langevin diffusion provides a way to sample from the target density, with the target as the stationary distribution of its stochastic differential equation.
Langevin MCMC discretizes the continuous Langevin diffusion to obtain an algorithm.
Previous analyses established convergence in total variation and 2-Wasserstein distance by separately controlling diffusion convergence and discretization error.
The paper establishes convergence in KL-divergence, a notion linked to maximum likelihood, Bayesian information gain, and information theory.

2 Related Work

Related work develops convergence analyses for discrete Langevin methods, variants for nonsmooth targets, stochastic-gradient methods, and a probability-space gradient-flow perspective.

Dalalyan and Durmus and Moulines developed non-asymptotic and 2-Wasserstein convergence analyses for discrete Langevin diffusion.
Variants of discrete Langevin methods address targets for which −log p∗ is not smooth, including uniform distributions over convex sets.
Dalalyan et al. studied Langevin Monte Carlo when only stochastic gradients are available.
The paper uses theory treating Langevin diffusion as a gradient flow over probability distributions.
In this view, discrete Langevin diffusion is a deterministic convex optimization procedure with KL-divergence as its objective.
The associated tangent velocity can also be interpreted as a deterministic transformation inducing a normalizing flow.

3 Our Contribution

The paper’s contribution is a KL-divergence convergence analysis for Langevin MCMC under strong convexity, together with convergence results when strong convexity is absent.

The paper establishes the first non-asymptotic KL-divergence convergence result for discrete Langevin diffusion when U is m strongly convex and L smooth.
The resulting KL analysis yields convergence results in total variation and 2-Wasserstein distance as corollaries.
The iteration-complexity table compares Langevin MCMC requirements for achieving ε error in total variation, KL-divergence, and 2-Wasserstein distance.
The paper also gives a convergence result when U is convex and smooth but not strongly convex.
Without strong convexity, the total-variation result has better dimension dependence but worse ε dependence than the corresponding result in prior work.

4 Definitions

The paper defines the target, Langevin processes, KL objective, probability-space geometry, and transport concepts used in its convergence analysis.

Probability-space geometry: The framework uses probability distributions with densities, couplings, Wasserstein distance, push-forward measures, geodesics, metric derivatives, and tangent velocity fields.
Target and processes: The target distribution p∗ has U(x) = −log p∗(x) + C, with L-Lipschitz gradients and m-strong convexity in the strongly convex setting.
Target and processes: Exact Langevin diffusion is defined by a stochastic differential equation driven by d-dimensional Brownian motion.
Target and processes: Langevin MCMC uses an initial distribution and stepsize, while discretized Langevin diffusion defines the corresponding continuous-time approximation.
Target and processes: The distinction between the discretized and exact processes is their drift evaluation: one uses the discretized state and the other the continuous state.
Probability-space objective: KL-divergence is represented by an objective F minimized at p∗, where F(p∗) = 0.

5 Preliminary Lemmas

The section develops a probability-space calculus for tracking the functional F along distributional curves and sets up a coupling-based comparison of exact and discretized Langevin dynamics.

The analysis studies how F(µ_t) evolves along absolutely continuous curves in P(R^d), using tangent velocity fields and the continuity equation.
The operator Dµ(v) is introduced to represent the directional action of a velocity field on F, and it is linear in v.
The curve p_t is analyzed by constructing auxiliary exact-Langevin and discretized processes that share Brownian motions and therefore define couplings.
The auxiliary process z represents the discretization error through its divergence from the exact-flow distribution, while the shared-noise construction links the compared curves.
The proof separates the decrease in F from exact Langevin, the discretization error, and their combined effect on the functional's evolution.

6 Strong Convexity Result

Under m-strong convexity and L-smoothness, the paper proves KL convergence for discrete Langevin dynamics and derives total-variation and Wasserstein consequences through the same framework.

The strong-convexity analysis assumes U is m-strongly convex and L-smooth and studies the resulting convergence of discrete Langevin dynamics.
Theorem 3 provides the principal KL-convergence guarantee for the discretized process, with p_t initialized as specified in the theorem.
The theorem immediately yields convergence rates in total variation and 2-Wasserstein distance for p_kh.
To achieve δ accuracy in total variation or W2, the proof applies Theorem 3 with ε = δ^2.
The proof uses strong geodesic convexity of F with respect to W2 to control F(µ) − F(p*) through the norm of its distributional gradient.
The analysis bounds moments of p_t to control discretization error, then combines differential inequalities and Gronwall's inequality to obtain the theorem.
Once F(p_t) reaches the ε threshold, continuity and the nonpositive derivative condition preserve the bound through the final time.

7 Weak convexity result

Without strong convexity, the paper analyzes discrete Langevin diffusion under convexity and smoothness, obtaining total-variation convergence with improved dimension dependence but worse dependence on ε or δ than prior results.

Assumptions: The non-strongly-convex analysis assumes log p* remains convex and L-smooth, while allowing strong convexity to be absent.The analysis also introduces πh as the stationary distribution of the discretized process and assumes a suitable initial distribution.
Theorem 5: Theorem 5 establishes convergence for the discretized Langevin process under the stated initial-distribution and stepsize conditions.The theorem uses constants C1, C2 and a maximal admissible stepsize h′ defined at the beginning of the section.
Guarantee: The resulting choice of iterations and continuous time yields total-variation error dTV(rk, p*) ≤ √ε.The proof combines discretization control with the convergence analysis for the associated functional.
Limitation: Without strong convexity, bounding F(rk) − F(p*) does not provide a corresponding W2 bound as in the strongly convex case.The stated limitation concerns Wasserstein convergence, not the total-variation guarantee.
Comparison: The result has better dependence on dimension d than the comparison bound, but worse dependence on δ and is not strictly better overall.The paper explicitly notes this trade-off even after ignoring the constants C1 and C2.

8 Supplementary Materials

The supplementary material develops the transport- and coupling-based lemmas supporting the main convergence theorems, including gradient-flow identities, convexity arguments, regularity, and discretization control.

Regularity: The supplementary lemmas establish regularity and moment properties needed to define the relevant Wasserstein gradients and expectations along the Langevin process.These results include well-definedness of wpt and bounds derived inductively from smoothness, strong convexity, and the initialization assumption.
Proof ingredients: Several lemmas derive these statements through optimal couplings, metric derivatives, continuity equations, Cauchy–Schwarz, and Lipschitz-gradient bounds.The supplementary proofs explicitly identify these ingredients in the transport and discretization arguments.
Functional analysis: The proof framework treats KL divergence as a functional on probability distributions and uses its gradient-flow and first-order properties in Wasserstein space.The supplementary results connect the Fokker–Planck equation to steepest descent and establish strong geodesic convexity when appropriate.
Weak convexity: In the weak-convexity analysis, synchronous couplings show that the discretized process contracts toward the stationary distribution πh in W2 for sufficiently small stepsizes.The argument couples successive iterates with πh and uses stationarity of πh under the discrete Langevin update.
Proof of Theorem 5: The proof of Theorem 5 combines discretization-error bounds, functional decrease estimates, and two regimes for the functional gap before selecting h and the iteration count.The theorem follows after applying the auxiliary lemmas and choosing parameters to make the resulting error at most ε.