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

The paper studies whether ULA can rapidly sample non-logconcave distributions under isoperimetric assumptions rather than logconcavity. It proves KL and Rényi convergence guarantees and analyzes discretization bias, while identifying limits from the biased ULA distribution and the current KL bias bound.

  • Problem

    Rapid discrete-time sampling beyond logconcavity remains challenging, motivating whether LSI and Poincaré inequality suffice for ULA convergence.

  • Method

    The paper analyzes ULA using LSI or Poincaré inequality, bounded Hessian assumptions, and properties of its biased limiting distribution.

  • Results

    Under LSI and bounded Hessian, the paper proves KL convergence for ULA; it also proves Rényi convergence when the biased limit satisfies LSI or Poincaré inequality.

  • Takeaways & Limitations

    LSI and Poincaré inequality provide sufficient isoperimetric foundations for the paper’s ULA convergence guarantees beyond convexity and logconcavity.

  • Takeaways & Limitations

    The asymptotic Rényi bias may be infinite for sufficiently large q, and the KL bias analysis gives O(η) although the Gaussian example has O(η^2).

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 LSI and Poincaré inequality suffice for rapid ULA convergence beyond logconcavity. It proves KL and Rényi guarantees under isoperimetric and smoothness conditions, and analyzes the biased limit.

  • Motivation: Non-logconcave sampling matters because modern high-dimensional applications use complicated distributions, while existing guarantees often rely on logconcavity.The paper emphasizes sampling’s connection to optimization through annealing and distributional gradient flows.
  • ULA setting: ULA uses gradient-oracle access to f and, unlike continuous-time Langevin dynamics, converges in discrete time to a biased limit rather than exactly to ν.As η approaches zero, ULA recovers Langevin dynamics, which converges to ν.
  • Motivation: LSI and Poincaré inequality cover distributions beyond logconcavity, including nonconvex uniform distributions and bounded perturbations of logconcave measures.These isoperimetric conditions are preserved under bounded perturbations and Lipschitz mappings, unlike logconcavity.
  • KL convergence: Under LSI and L-smoothness, Theorem 1 gives a KL convergence guarantee for ULA with a sufficiently small step size, without convexity or higher-derivative bounds.The stated step-size condition is 0 < η ≤ α/(4L^2).
  • Rényi convergence: The paper proves Rényi convergence for q > 1 along ULA when the biased limit satisfies LSI or Poincaré inequality, using convergence to the limit plus a divergence decomposition.Under Poincaré inequality, convergence is initially slower and can incur an extra factor of n for reasonable starts.
  • Biased limit: For the biased limit, the paper bounds relative Fisher-information bias under third-order smoothness and proves LSI inheritance when the target is smooth and strongly logconcave.The third-order-smoothness bias result does not require isoperimetry.

2 Review of KL divergence along Langevin dynamics

The section defines KL divergence and the log-Sobolev framework, then reviews Langevin dynamics as a Wasserstein gradient flow whose convergence accelerates exponentially under LSI.

  • 2.1 KL divergence: KL divergence is a nonnegative, asymmetric measure of distance from ρ to ν, minimized exactly when ρ = ν.Under LSI or Talagrand’s inequality, it also controls quadratic Wasserstein distance.
  • 2.2 Log-Sobolev inequality: LSI relates KL divergence to relative Fisher information and extends beyond strong logconcavity through perturbation, Lipschitz-mapping, and tensorization properties.These properties allow non-logconcave distributions to satisfy LSI with dimension-independent constants.
  • 2.3 Langevin dynamics: Langevin dynamics evolves the target distribution through a stochastic differential equation, with its density governed equivalently by the Fokker–Planck equation.The target ν is stationary for this evolution.
  • 2.3 Langevin dynamics: Along Langevin dynamics, KL divergence decreases because its time derivative is controlled by nonnegative relative Fisher information, yielding convergence toward ν.The density evolution brings any initial distribution closer to the target.
  • 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.This rate reflects gradient-flow convergence under the gradient-domination interpretation of LSI.

3 Unadjusted Langevin Algorithm

This section analyzes ULA as a discrete approximation to Langevin dynamics, establishing KL convergence under LSI and smoothness while quantifying discretization bias.

  • Algorithm: ULA evolves distributions through discrete noisy gradient steps, with ρk denoting the distribution of the kth iterate.The noise variables are independent standard Gaussians, and the algorithm uses gradient-oracle access to f.
  • KL convergence: Under LSI with constant α and L-smoothness, one ULA step contracts KL divergence up to an O(η2nL2) discretization error.The proof compares one ULA step with η units of continuous-time Langevin dynamics, whose KL divergence contracts exponentially.
  • KL convergence: For 0 < η ≤ α/(4L2), ULA reaches KL divergence below δ after k ≥ (1/(αη)) log(2Hν(ρ0)/δ) iterations.The permitted step size is further restricted by η ≤ (α/(4L2)) min{1, δ/(4n)} to achieve the target accuracy.
  • Consequences: Theorem 1 also yields a Wasserstein convergence guarantee because LSI implies Talagrand’s inequality.This transfers the KL guarantee to quadratic Wasserstein distance under the same assumptions.
  • Bias: The biased limit νη differs from ν at fixed η, with Hν(νη) ≤ 8nL2η under LSI and smoothness.The paper notes that the Gaussian example has the smaller bias order O(η2), while the general bound is O(η).
  • Bias: Third-order smoothness alone, without isoperimetry, yields a relative Fisher-information bias bound for the limiting distribution.This result does not require the LSI assumption used for the KL convergence theorem.

4 Review of R´enyi divergence along Langevin dynamics

This section reviews Rényi divergence and its behavior along continuous-time Langevin dynamics. Under LSI it decreases exponentially, while under Poincaré inequality the convergence initially has a linear phase.

  • Rényi divergence: Rényi divergence generalizes KL divergence and provides a stronger distance measure as its order q increases.It is nonnegative, vanishes only when ρ = ν, and can become infinite for sufficiently large q.
  • Rényi divergence: For Gaussian ρ = N(0, σ2I) and ν = N(0, λ2I) with σ2 > λ2, Rq,ν(ρ) is infinite when q ≥ σ2/(σ2−λ2).This example demonstrates that finite Rényi divergence depends on the order q and the pair of distributions.
  • Langevin dynamics: Along Langevin dynamics, Rényi divergence is nonincreasing for every q > 0.The dynamics can also be viewed as a gradient flow of Rényi divergence under a suitable target-dependent metric.
  • Langevin dynamics: Under LSI, Rényi divergence converges exponentially fast along Langevin dynamics for q ≥ 1.For q = 1, this recovers the exponential KL convergence rate.
  • Langevin dynamics: If the initial Rényi divergence is infinite, LSI-based hypercontractivity makes it finite after some time, after which exponential convergence applies.The theorem directly assumes finite initial divergence, while the hypercontractivity result addresses eventual finiteness.
  • Poincaré inequality: Under Poincaré inequality, Rényi divergence initially decreases linearly and then decreases exponentially once it is below 1.Thus the Poincaré-based rate differs from the purely exponential LSI behavior.

5 R´enyi divergence along ULA

The paper proves Rényi-divergence convergence for ULA toward its biased limit under an LSI assumption on that limit, then combines this with a bias decomposition to characterize convergence toward the target. The asymptotic Rényi bias can be finite for sufficiently small step sizes but is not generally bounded by the main result.

  • 5 Rényi divergence along ULA: For each fixed q > 1, the asymptotic Rényi bias is finite for sufficiently small η; in Example 3, it is O(η2).The example also gives a finite bound for 1 < q < 2/(ηα), while the bias is infinite for sufficiently large q.
  • 5.3 Convergence of Rényi divergence along ULA under LSI: The Rényi-divergence bound separates convergence to νη from the asymptotic bias between νη and ν.The first term contracts exponentially under LSI, while the second term is the limiting bias.
  • 5.2 Rapid convergence of Rényi divergence to biased limit under LSI: ULA converges exponentially fast in Rényi divergence to the biased limit νη when νη satisfies LSI.The proof decomposes each ULA step into a divergence-preserving deterministic gradient map and heat-flow evolution that contracts Rényi divergence.
  • 5.2 Rapid convergence of Rényi divergence to biased limit under LSI: The analysis assumes νη satisfies LSI, but verifying this condition in general remains unclear.It is verified for Gaussian targets and smooth strongly log-concave targets.
  • 5.3 Convergence of Rényi divergence along ULA under LSI: The main ULA guarantee requires L-smoothness, a step-size restriction, and finite initial Rényi divergence of order 2q.The resulting iteration complexity depends on the largest step size whose asymptotic bias is at most the target tolerance.

6 Poincar´e inequality

The paper extends Rényi-divergence convergence analysis from LSI to the weaker Poincaré inequality. Under a Poincaré condition on the biased limit, ULA converges exponentially to that limit and admits a target-distribution guarantee after accounting for asymptotic bias.

  • 6 Poincaré inequality: Poincaré inequality is weaker than LSI and yields an analogous Rényi-divergence control when the current divergence is small.The paper uses this control to analyze convergence under Poincaré inequality.
  • 6 Poincaré inequality: Under Poincaré inequality, Rényi divergence along Langevin dynamics first decreases linearly and then converges exponentially once sufficiently small.This establishes the continuous-time behavior used for the discrete-time analysis.
  • 6.2 Convergence of Rényi divergence to biased limit under Poincaré: ULA converges exponentially fast in Rényi divergence to νη when νη satisfies Poincaré inequality.The discrete-time rate matches the corresponding continuous-time convergence rate.
  • 6.3 Convergence of Rényi divergence along ULA under Poincaré: The Poincaré-based target guarantee assumes ν is L-smooth, νη satisfies Poincaré inequality, and the initial order-2q Rényi divergence is finite.The result combines convergence to νη with a decomposition separating the target bias.
  • 6.3 Convergence of Rényi divergence along ULA under Poincaré: The Poincaré-based complexity has additional dimension dependence compared with the LSI case.The admissible step size is determined by the asymptotic Rényi bias threshold γq(δ).

7 Properties of Biased Limit

The paper studies the biased limiting distribution of ULA independently of isoperimetry. It bounds relative Fisher-information bias under third-order smoothness and shows that smooth strongly log-concave targets make the biased limit satisfy LSI.

  • 7 Properties of Biased Limit: Third-order smoothness controls the relative Fisher-information bias of the ULA limit without requiring isoperimetry.The assumption requires Lipschitz gradient and Lipschitz Hessian.
  • 7 Properties of Biased Limit: The relative Fisher-information bias has an upper bound of order O(η2) and a lower bound of order Ω(η2).Thus, the lower bound has the correct step-size order, while the upper bound is not matched in the stated result.
  • 7 Properties of Biased Limit: Under LSI, the third-order-smoothness bound implies a KL-bias bound with additional dependence on third-order smoothness but no isoperimetric assumption.The comparison is with the LSI-and-smoothness KL bound whose dependence is O(η n L2).
  • 7 Properties of Biased Limit: Relative Fisher-information convergence does not necessarily imply convergence of the underlying distributions.This limits how directly the Fisher-information bias bound can establish distributional convergence.
  • 7 Properties of Biased Limit: If ν is smooth and strongly log-concave, then νη satisfies LSI and therefore also Poincaré inequality.This verifies the assumptions needed for the paper’s Rényi-divergence convergence results in that setting.

8 Proofs and details

The proofs analyze ULA through continuous-time interpolation, divergence identities, isoperimetric inequalities, and pushforward properties. These tools establish KL and Rényi contraction statements while quantifying discretization error and step-size effects.

  • Proofs and details: Under LSI, integrating the KL differential inequality gives exponential continuous-time decay Hν(ρt) ≤ e^-2αt Hν(ρ0).LSI also yields a Wasserstein-2 control through Talagrand’s inequality.
  • Proofs and details: ULA can be represented over one step by a stochastic differential equation whose time-η output matches the ULA update.This interpolation enables comparison between ULA and Langevin dynamics through their Fokker–Planck equations.
  • Proofs and details: The interpolated ULA Fokker–Planck equation differs from Langevin dynamics through a conditional expected gradient rather than the true gradient.The resulting extra term is treated as the discretization error.
  • Proofs and details: The ULA KL recursion combines LSI contraction with a discretization-error term controlled by smoothness and step size.For a target tolerance δ, the proof imposes an additional step-size restriction proportional to δα/(nL2).
  • Proofs and details: Rényi divergence is monotone in its order, and differentiable bijective pushforwards preserve it.These facts support order changes and the divergence-preserving gradient-step argument.
  • Proofs and details: Under LSI, continuous-time Rényi divergence contracts exponentially, with finite higher-order divergence becoming available after a logarithmic time threshold.The proof combines fixed-order contraction with an evolving order parameter.
  • Proofs and details: LSI constants degrade under an L-Lipschitz pushforward to α/L2.This mapping property helps transfer isoperimetric assumptions to transformed distributions.
  • Proofs and details: Third-order smoothness yields Eνη[||∇f||2 − Δf] = O(η), the key bias relation used in the biased-limit analysis.For the target ν, the corresponding expectation is zero.

9 Discussion

The paper establishes ULA convergence under isoperimetric assumptions and bounded Hessian without convexity, while identifying open questions about bias, invariant formulations, and broader extensions.

  • Under LSI and bounded Hessian, the paper proves ULA convergence guarantees without assuming convexity or bounds on higher derivatives.
  • The KL-bias analysis scales linearly with step size, although Gaussian examples indicate quadratic scaling may be optimal.
  • The paper leaves open whether ULA analysis under LSI and smoothness can achieve the optimal bias.
  • Rényi convergence relies on isoperimetry assumptions for the biased limit, whose broader validity and possible relaxation remain unresolved.
  • An affine-invariant Langevin formulation could yield logarithmic rather than polynomial dependence on smoothness, but discretization analysis remains challenging.
  • The one-step interpolation technique has been extended to ULA variants on manifolds, products of spheres, and related sampling algorithms.

A.1 Review on notation and basic properties

This section establishes notation for densities, vectors, matrices, derivatives, Gaussian distributions, and integration by parts used throughout the paper.

  • Probability distributions on R^n are represented by smooth, full-support densities with respect to Lebesgue measure.
  • The inner product is defined coordinatewise, positive-semidefinite ordering is used for symmetric matrices, and N(µ, Σ) denotes a Gaussian distribution.
  • The gradient is the vector of first partial derivatives, while the Hessian is the matrix of second partial derivatives.
  • The Laplacian is the trace of the Hessian, and the divergence is defined for smooth vector fields; divergence of a gradient equals the Laplacian.
  • The section states an integration-by-parts formula for functions and vector fields with sufficiently fast decay at infinity.

A.2 Derivation of the Fokker-Planck equation

The appendix derives the Fokker–Planck equation for a stochastic differential equation by differentiating test-function expectations and applying Taylor expansion and integration by parts.

  • A stochastic differential equation driven by Brownian motion induces an evolving probability density described by the Fokker–Planck equation.
  • The derivation differentiates the expectation of a smooth test function along the stochastic process.
  • For a small time increment, the stochastic update is expanded using an independent Gaussian increment and Taylor expansion.
  • Taking expectations removes the centered Gaussian term, after which integration by parts converts the resulting expression into the Fokker–Planck form.
  • Comparing the two representations for arbitrary test functions identifies the density evolution equation.
  • Setting the vector field to −∇f recovers Langevin dynamics and its Fokker–Planck equation; a constant vector field yields ULA’s one-step evolution.

A.3 Remaining proofs

The remaining proofs establish how log-Sobolev and Poincaré inequalities transform under Lipschitz maps and convolution, supporting the paper’s isoperimetric arguments.

  • Under an L-Lipschitz map, an LSI constant α transforms to α/L^2.
  • The proof uses the chain rule to relate gradients after transformation and then applies the original measure’s LSI.
  • LSI is also combined through a convolution property for measures with positive LSI constants.
  • Under an L-Lipschitz map, a Poincaré constant α transforms to α/L^2.
  • The Poincaré proof parallels the LSI argument by applying the chain rule and the original measure’s Poincaré inequality.
  • Poincaré constants also satisfy a convolution property, with Gaussian convolution supplying the relevant example in the proof.
Loading 1903.08568v4…