PaperlayerView exact revision on arXiv

Source-linked AI summary

Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices

Santosh S. Vempala, Andre Wibisono

arXiv:1903.08568v4cs.DScs.LGmath.PRstat.ML

TL;DR

For non-log-concave targets, whether isoperimetric assumptions suffice for ULA convergence is unclear. This paper proves KL and Rényi convergence guarantees under specified isoperimetric and smoothness assumptions, without requiring convexity or higher-derivative bounds.

  • Problem

    Whether log-Sobolev or Poincaré inequalities suffice for ULA convergence without log-concavity remains an open question.

    Source: §1 · p. 4

  • Method

    The paper analyzes discrete-time ULA and establishes convergence under isoperimetric conditions, alongside a bias bound under third-order smoothness.

    Source: §1 · p. 6, §3 · pp. 9–10

  • Results

    Under isoperimetric assumptions and bounded Hessian, the paper proves KL and Rényi convergence guarantees for ULA without convexity or higher-derivative bounds.

    Source: §1 · p. 6, §9 · p. 43

  • Takeaways & Limitations

    The stated convergence guarantees show that log-concavity is not required when the specified isoperimetric assumptions hold.

    Source: §1 · p. 4, §9 · p. 43

    The KL-bias bound may not be tight: it scales linearly with step size, whereas the Gaussian example suggests quadratic scaling, leaving optimal ULA bias analysis open.

    Source: §9 · p. 43

Abstract

from arXiv · show

We study the Unadjusted Langevin Algorithm (ULA) for sampling from a probability distribution $ν= e^{-f}$ on $\mathbb{R}^n$. We prove a convergence guarantee in Kullback-Leibler (KL) divergence assuming $ν$ satisfies a log-Sobolev inequality and the Hessian of $f$ is bounded. Notably, we do not assume convexity or bounds on higher derivatives. We also prove convergence guarantees in Rényi divergence of order $q > 1$ assuming the limit of ULA satisfies either the log-Sobolev or Poincaré inequality. We also prove a bound on the bias of the limiting distribution of ULA assuming third-order smoothness of $f$, without requiring isoperimetry.

1 Introduction

The paper asks whether isoperimetric assumptions can support rapid ULA convergence beyond logconcavity. It establishes KL and Rényi convergence guarantees under specified smoothness and isoperimetry conditions, and studies the bias and properties of ULA’s limiting distribution.

Motivation and setup

  • ULA uses gradient-oracle access without requiring the density’s normalizing constant, but its discrete-time limit is biased, making convergence beyond logconcavity challenging.The paper motivates this setting by the need for efficient sampling guarantees for complicated, non-logconcave distributions.Source: §1 · pp. 3–4

KL convergence

  • Under a log-Sobolev inequality and L-smoothness, ULA has a KL convergence guarantee with a step-size condition.Here L-smoothness means the gradient of f is L-Lipschitz.Source: §1 · pp. 4–5

Rényi convergence

  • For continuous-time Langevin dynamics, Rényi divergence converges under LSI, while under Poincaré inequality the result covers q ≥ 2 and has a slower initial phase.For a reasonable starting distribution, the Poincaré case incurs an extra factor of n compared with convergence under LSI.Source: §1 · pp. 5–6
  • ULA converges in Rényi divergence to its biased limit when that limit satisfies LSI or Poincaré inequality, yielding a guarantee toward the target distribution.The target guarantee combines convergence to the biased limit with a decomposition of Rényi divergence.Source: §1 · p. 6

2 Review of KL divergence along Langevin dynamics

This section reviews KL divergence and isoperimetric inequalities, then shows that Langevin dynamics decreases KL divergence and converges exponentially under a log-Sobolev inequality (LSI).

2.1 KL divergence

  • KL divergence is nonnegative, vanishes only when ρ = ν, and controls total variation and, under LSI or Talagrand’s inequality, quadratic Wasserstein distance.It is an asymmetric measure of distance from ρ to the base distribution ν.Source: §2.1 · p. 7

2.2 Log-Sobolev inequality

  • LSI is a strong isoperimetry condition that applies beyond strongly log-concave distributions, including some non-log-concave distributions.It is stable under bounded perturbations and Lipschitz mappings and has a tensorization property.Source: §2.2 · pp. 7–8

2.2.1 Talagrand inequality

  • If ν satisfies LSI with constant α, it also satisfies Talagrand’s inequality with the same constant; for log-concave ν, the two inequalities are equivalent.Thus, under LSI, KL divergence controls the Wasserstein distance.Source: §2.2.1 · p. 8

2.3 Langevin dynamics

  • Along Langevin dynamics, KL divergence with respect to ν decreases, and the target distribution ν is stationary.The decrease follows from the nonnegativity of relative Fisher information.Source: §2.3 · p. 9

2.3.1 Exponential convergence of KL divergence along Langevin dynamics under LSI

  • Under LSI with constant α > 0, KL divergence converges exponentially fast along Langevin dynamics.Theorem 4 gives this convergence guarantee.Source: §2.3.1 · p. 9

3 Unadjusted Langevin Algorithm

This section analyzes discrete-time ULA under a log-Sobolev inequality (LSI) and bounded Hessian, establishing KL convergence guarantees and bounds on the bias of its fixed-step limiting distribution. It also describes a third-order smoothness route to a relative Fisher information bias bound without isoperimetry.

3.1 Convergence of KL divergence along ULA under LSI

  • For fixed η, ULA converges to a biased limit with positive asymptotic KL divergence; under LSI and L-smoothness its bias is bounded by 8nL^2η, versus O(η^2) in the Gaussian example.The Gaussian example shows the bound can be looser than the actual bias order in that case.Source: §3 · p. 10, §3.1 · p. 11
  • The proof compares one ULA step with Langevin dynamics over time η, which contracts KL exponentially under LSI, and bounds the discretization error.Figure 2 states the ULA KL bound as e^(-αη)H + O(η^2nL^2), where H is the current KL divergence.Source: §3.1 · p. 10, Figure 2 · p. 11
  • Under LSI and L-smoothness, Theorem 1 gives a KL convergence guarantee for ULA with step size η ≤ α/(4L^2), including a step-size and iteration-complexity prescription to reach tolerance δ.The stated prescription uses η ≤ (α/(4L^2)) min{1, δ/(4n)} and gives an iteration bound in terms of α, η, the initial KL divergence, and δ.Source: §3.1 · pp. 10–11
  • Since LSI implies Talagrand’s inequality, Theorem 1 also yields a convergence guarantee in Wasserstein distance.Source: §3.1 · p. 11
  • With third-order smoothness of f, a bias bound in relative Fisher information is available without an isoperimetric assumption.Source: §3.1 · p. 11

4 Review of R´enyi divergence along Langevin dynamics

The section reviews Rényi divergence and its behavior under Langevin dynamics. Under a log-Sobolev inequality (LSI), the divergence converges exponentially when initially finite; along the dynamics it is always nonincreasing.

4.1 R´enyi divergence

  • Rényi divergence generalizes KL divergence, is nonnegative and increases with order, and its infinite-order value is finite exactly when ρ is warm relative to ν.It can be infinite at sufficiently large finite orders as well.Source: §4.1 · p. 12

4.1.1 Log-Sobolev inequality

  • For q ≥ 1, LSI supplies a relation between Rényi divergence and Rényi information; at q = 1 this recovers the KL-divergence and relative-Fisher-information form of LSI.Source: §4.1.1 · pp. 12–13

4.2 Langevin dynamics

  • Rényi divergence is nonincreasing along Langevin dynamics, which can also be viewed as its gradient flow under a suitably defined target-dependent metric [14].Source: §4.2 · p. 13

4.2.1 Convergence of R´enyi divergence along Langevin dynamics under LSI

  • Under LSI, Rényi divergence of order q ≥ 1 converges exponentially along Langevin dynamics when its initial value is finite.Even if initially infinite, it eventually becomes finite by hypercontractivity; combining hypercontractivity with the convergence result can yield rate 2α after an initial waiting time [14].Source: §4.2.1 · p. 13
  • Under a Poincaré inequality, Rényi divergence still converges along Langevin dynamics, decreasing linearly at first and exponentially after it falls below 1.Source: §4.2.1 · p. 13

5 R´enyi divergence along ULA

The section characterizes Rényi convergence of ULA by separating transient convergence to the biased limit from asymptotic bias. Under an LSI assumption on that limit, the transient term decays exponentially, while the bias may be infinite for sufficiently large orders.

5 R´enyi divergence along ULA

  • The asymptotic Rényi bias may be infinite for large q, but for each fixed q > 1 it is finite at sufficiently small step sizes; Example 3 gives bias O(η2).The section’s bias discussion also gives an example-specific threshold for infinite divergence when q is large.Source: §5 · p. 14

5.1 Decomposition of R´enyi divergence

  • The divergence decomposition separates the term measured against the biased limit, which decays exponentially under LSI, from the asymptotic Rényi bias.This decomposition underlies the section’s convergence characterization.Source: §5.1 · p. 14

5.2 Rapid convergence of R´enyi divergence to biased limit under LSI

  • If the biased limit νη satisfies LSI, Rényi divergence to it converges exponentially; this assumption is verifiable for Gaussian or smooth strongly log-concave ν, but is unclear generally.Each ULA step separates into a deterministic gradient map that preserves Rényi divergence and Gaussian heat flow that decreases it; Figure 3 gives the decrease factor e^-αη.Source: §5.2 · pp. 14–15, Figure 3 · p. 15

5.3 Convergence of R´enyi divergence along ULA under LSI

  • Under Assumption 1, Theorem 5 characterizes order-q Rényi convergence along ULA using exponential convergence to the biased limit and a finite initial R2q,νη(ρ0).The result assumes ν is L-smooth and a sufficiently small step size; it does not bound the asymptotic bias. The cited discussion contrasts this with [35] and [34], which do not estimate the bias, and [21], which does.Source: §5.3 · pp. 15–16

6 Poincar´e inequality

The section uses the Poincaré inequality (PI) to establish Rényi-divergence bounds and convergence guarantees for Langevin dynamics and ULA. For ULA, convergence to the true target is characterized through convergence to its biased limit.

6 Poincar´e inequality

  • PI is weaker than the log-Sobolev inequality (LSI), and the section’s Rényi-divergence bound under PI is approximately equivalent to the LSI bound when the divergence is small.The text also describes PI as a linearization of LSI and Talagrand’s inequality, and notes that PI can be easier to verify using Lyapunov criteria and integrability conditions.Source: §6 · pp. 16–17

6.1 Convergence of R´enyi divergence along Langevin dynamics under Poincar´e

  • Under PI, Rényi divergence along Langevin dynamics initially decreases linearly and then exponentially once it falls below a constant.The theorem concerns order q ≥ 2 and states that from initial divergence at least 1, the dynamics reaches a target level δ within a stated time bound.Source: §6.1 · p. 17

6.2 Convergence of R´enyi divergence to biased limit under Poincar´e

  • ULA’s Rényi divergence converges exponentially to its biased limit when that limit satisfies PI, but verifying this condition is unclear in general.The condition is verifiable in the Gaussian and smooth strongly logconcave cases; discrete-time convergence is stated to match the continuous-time rate.Source: §6.2 · p. 17

6.3 Convergence of R´enyi divergence along ULA under Poincar´e

  • The ULA guarantee for the true target combines convergence to the biased limit with a step size chosen according to the bias, with an additional dimension dependence versus the LSI case.The section gives bias-dependent examples: when Rq,ν(νη) = O(η), γq(δ) = Ω(δ); when Rq,ν(νη) = O(η2), the text gives a different dependence.Source: §6.3 · p. 18

7 Properties of Biased Limit

The section bounds the bias of ULA’s limiting distribution under third-order smoothness and shows that strong log-concavity and smoothness give the biased limit isoperimetric properties. It also qualifies what these results establish: a relative Fisher information bound need not imply distributional convergence, and the Rényi convergence bound leaves the bias unbounded.

7.1 Bound on bias under third-order smoothness

  • O(η²) upper and Ω(η²) lower bounds describe the dependence on step size in the bias bounds under third-order smoothness.The stated condition for the upper bound is (L, M)-smoothness and η ≤ 1/(2L); the lower bound is stated for any f and η > 0 when the biased limit and quantities exist.Source: §7.1 · pp. 18–19
  • Under LSI, the upper bound yields Hν(νη) ≤ O(η n (L^2 + nLM + nM^2)), adding third-order smoothness dependence relative to the stated O(η n L^2) bound.The third-order-smoothness bias bound does not require isoperimetry.Source: §7.1 · p. 19
  • A relative Fisher information bound does not in general imply convergence of the underlying distributions [7].The section also notes Jν(νη) ≤ η n L^2 when f is L-smooth and ΔΔf ≥ 0.Source: §7.1 · p. 19

7.2 Isoperimetry of biased limit under strong log-concavity and smoothness

  • For smooth, strongly log-concave targets, the biased limit satisfies LSI and therefore Poincaré, supporting ULA Rényi convergence to that limit.The convergence bound remains in terms of the Rényi bias, which this section does not bound; the relative Fisher information bias bound does not establish a Rényi bias bound.Source: §7.2 · p. 19
  • Work by [7] extends the interpolation technique to Rényi convergence under LSI and a general family of isoperimetric inequalities, and bounds Rényi bias under LSI and smoothness.Theorem 8 is stated for an α-strongly log-concave, L-smooth target, with a step-size condition; its bound is not given in the supplied passage.Source: §7.2 · p. 19

8 Proofs and details

This section develops the proof tools for ULA convergence and limiting-distribution analysis, including continuous-time KL decay, discretization recursion, and Rényi-divergence contraction. It also establishes bounds used to analyze limiting-distribution bias and proves a log-Sobolev inequality for the ULA limit under strong convexity.

8.1.3 Proof of Theorem 4

  • Hν(ρt) ≤ e^-2αtHν(ρ0) under the LSI assumption with constant α.The proof integrates the KL decay inequality along Langevin dynamics.Source: §8.1.3 · p. 20

8.2.1 Proof of Lemma 3

  • A Brownian SDE with frozen drift reproduces one ULA update, whose Fokker–Planck drift differs from Langevin’s by replacing ∇f(x) with a conditional expectation.That drift difference is identified as the discretization error in the KL derivative bound.Source: §8.2.1 · pp. 21–23

8.2.2 Proof of Theorem 1

  • η ≤ δα/(16nL^2) yields Hν(ρk) ≤ e^-αηkHν(ρ0) + δ/2.This is the bound obtained by iterating the one-step recursion for ULA.Source: §8.2.2 · p. 24

8.3.6 Hypercontractivity

  • For q ≥ q0, Langevin dynamics gives Rq,ν(ρt) ≤ Rq0,ν(ρ0) after t ≥ (1/(2α)) log((q−1)/(q0−1)).The result assumes an LSI with constant α and finite initial Rq0,ν(ρ0), for q0 > 1.Source: §8.3.6 · pp. 28–29

8.4.2 Proof of Lemma 8

  • For q > 0, Rényi divergence is invariant under differentiable bijections; also, if ν satisfies LSI with constant α > 0, a differentiable L-Lipschitz pushforward satisfies LSI with constant α/L².Source: §8.4.2 · p. 30
  • Along each ULA (11) step from xk ∼ρk to xk+1 ∼ρk+1, Rényi divergence with respect to νη decreases by a constant factor; Theorem 5 follows directly from Lemma 7 and Lemma 8.Source: §8.4.2 · p. 32, §8.4.3 · p. 33

8.5.2 Proof of Theorem 3

  • Theorem 3’s proof combines Lemmas 6 and 9, considering separately whether the initial Rényi divergence is at least or at most 1.Lemma 9’s proof applies a Poincaré inequality and a monotonicity condition to obtain its desired inequality.Source: §8.5.1 · p. 33, §8.5.2 · p. 34

8.5.3 Proof of Lemma 10

  • Lemma 10’s proof transfers the Poincaré inequality through a deterministic update and Gaussian convolution; Theorem 6 first brings R_2q,νη(ρk) to at most 1.The proof then applies Lemma 10’s second case and Lemma 7.Source: §8.5.3 · pp. 34–35, §8.5.4 · p. 35

8.6.4 Proof of upper bound in Theorem 7

  • Theorem 7’s upper-bound proof combines bounds on relative Fisher information, the expected value, and Fisher information.The relative Fisher information bound assumes L-smoothness and η ≤ 1/(2L); the Fisher-information bounds cover L-smooth and (L, M)-smooth cases.Source: §8.6.1 · pp. 36–37, §8.6.3 · p. 39, §8.6.4 · p. 41

8.6.5 Proof of lower bound in Theorem 7

  • Theorem 7’s lower-bound proof uses identities satisfied by the biased limit and applies Cauchy–Schwarz.The identities include E_νη[∇f] = 0.Source: §8.6.5 · pp. 41–42

8.6.6 Proof of Theorem 8

  • With α-strongly convex f and 0 ≤ η ≤ 1/L, the proof shows that the limiting ULA distribution satisfies an LSI.It propagates LSI through each update and takes the limit of the iterates.Source: §8.6.6 · pp. 42–43

9 Discussion

The discussion recaps ULA convergence guarantees under isoperimetry and bounded Hessian without convexity or higher-derivative bounds. It highlights limitations in the bias and Rényi assumptions, open questions about affine-invariant dynamics, and later extensions of the analysis techniques.

9 Discussion

  • Under LSI and bounded Hessian, the paper establishes ULA convergence guarantees in KL and Rényi divergence without convexity or higher-derivative bounds.The KL result includes a complexity guarantee; the authors note its dependence on the condition number may not be tight.Source: §9 · p. 43
  • The KL bias bound scales linearly with step size, versus quadratic scaling suggested by a Gaussian example; improving ULA’s bias analysis remains open.Underdamped Langevin [56] and proximal Langevin [77] can achieve smaller bias.Source: §9 · p. 43
  • Rényi convergence requires the biased ULA limit to satisfy isoperimetry, verified under strong log-concavity and target smoothness; broader conditions remain open.The authors ask whether these assumptions can be relaxed or follow from isoperimetry and smoothness of the target.Source: §9 · p. 43
  • An affine-invariant Langevin method might reduce smoothness dependence to logarithmic, but discretization analysis remains challenging.Continuous-time approaches include interacting Langevin dynamics [36] and Newton Langevin dynamics [22].Source: §9 · p. 43
  • The one-step interpolation and simultaneous-heat-flow analyses have informed ULA variants and other samplers across manifold, tail, Rényi, Fisher-information, proximal, and mirror settings [75] [50] [33] [40] [21] [7] [77] [17].The cited extensions include sampling on complete Riemannian manifolds and products of spheres, from sub-Gaussian or heavy-tailed distributions, and under mirror isoperimetric inequalities.Source: §9 · pp. 43–44

A Appendix · A.1 Review on notation and basic properties

This appendix section establishes notation for probability densities and common differential operators, along with matrix and Gaussian conventions. It also records an integration-by-parts condition and a shorthand for omitting function arguments.

A.1 Review on notation and basic properties

  • Distributions are represented by Lebesgue densities normalized to integrate to one; the usual assumptions are full support and a smooth, positive density.The section also introduces notation for expectation under a distribution.Source: §A.1 · p. 49
  • The notation includes the Euclidean inner product, positive-semidefinite matrix ordering, and Gaussian distributions specified by their mean and covariance.Source: §A.1 · p. 49
  • For smooth functions, the gradient is the vector of first partial derivatives and the Hessian is the matrix of second partial derivatives.Source: §A.1 · p. 49
  • The Laplacian is the trace of the Hessian, and the divergence of a vector field is defined as a differential operator.Source: §A.1 · pp. 49–50
  • The divergence of a gradient equals the Laplacian.Source: §A.1 · p. 50
  • An integration-by-parts formula is stated for functions and vector fields with sufficiently fast decay at infinity; function arguments are omitted when clear.Source: §A.1 · p. 50

A.2 Derivation of the Fokker-Planck equation

For an SDE driven by Brownian motion and a smooth vector field, the probability density evolves according to the Fokker–Planck equation. The section derives this evolution by comparing the time derivative of test-function expectations with the SDE’s small-time behavior.

A.2 Derivation of the Fokker-Planck equation

  • The density of the SDE’s state evolves according to the Fokker–Planck equation.The setup uses a smooth vector field and Brownian motion starting at zero.Source: §A.2 · p. 50
  • The heuristic derivation evaluates smooth test-function expectations in two ways, using Gaussian Brownian increments, a Taylor expansion, and integration by parts.Comparing the resulting expressions for arbitrary test functions yields the density evolution.Source: §A.2 · pp. 50–51
  • For v = −∇f, the equation specializes to Langevin dynamics; for constant v = −∇f(x0), it gives the evolution equation for one ULA step.The latter specialization is used in the proof of Lemma 3.Source: §A.2 · pp. 50–51

A.3 Remaining proofs … A.3.4 Proof of Lemma 20

These remaining proofs establish how log-Sobolev and Poincaré inequalities behave under Lipschitz transformations and convolution. They apply those properties to derive the stated lemmas.

A.3.1 Proof of Lemma 16

  • For Lemma 16, the proof represents the transformed measure as the law of T(X) and composes a smooth test function g with T.The gradient of the composition is bounded using the L-Lipschitz property of T.Source: §A.3.1 · p. 52
  • The transformed measure satisfies an LSI with constant α/L^2, by applying ν’s LSI after bounding the composed gradient.The proof attributes the resulting inequality to the assumption that ν satisfies an LSI with constant α.Source: §A.3.1 · p. 52

A.3.2 Proof of Lemma 17

  • For Lemma 17, the proof invokes the convolution property of LSI measures with constants α and α̃, then concludes using the 2t term.The supplied passage does not expose the full convolution constant.Source: §A.3.2 · p. 52

A.3.3 Proof of Lemma 19

  • For Lemma 19, the proof pushes a smooth test function through T and bounds its gradient using the L-Lipschitz property.It takes X distributed as ν, so T(X) is distributed as ν̃.Source: §A.3.3 · p. 52
  • The transformed measure satisfies a Poincaré inequality with constant α/L^2, using the Poincaré inequality for ν with constant α.Source: §A.3.3 · pp. 52–53

A.3.4 Proof of Lemma 20

  • For Lemma 20, the proof invokes the convolution property of Poincaré inequalities and applies it using the Gaussian term with parameter 2t.The supplied passages do not expose the full convolution constant.Source: §A.3.4 · p. 53

Related papers

Loading 1903.08568v4…