PaperlayerView exact revision on arXiv

Source-linked AI summary

Sharp convergence rates for Langevin dynamics in the nonconvex setting

Xiang Cheng, Niladri S. Chatterji, Yasin Abbasi-Yadkori, Peter L. Bartlett, Michael I. Jordan

arXiv:1805.01648v4stat.MLcs.LGmath.PRstat.CO

TL;DR

Sampling from nonconvex distributions lacks detailed nonasymptotic convergence guarantees, especially for dimension dependence. This paper analyzes overdamped and underdamped Langevin MCMC and shows polynomial dependence on dimension and accuracy, with exponential dependence on LR^2.

  • Problem

    The paper addresses limited nonasymptotic understanding of sampling convergence rates and their dimension dependence for distributions that are nonconvex inside a bounded region.

    Source: §1 · p. 2

  • Method

    The paper analyzes overdamped and underdamped Langevin diffusion for potentials that are smooth everywhere and strongly convex outside a radius-R ball.

    Source: §1 · p. 2, §3 · p. 5, §4 · p. 6

  • Results

    The iteration complexity is polynomial in dimension d and accuracy ε, but exponential in LR^2, for sampling guarantees measured in 1-Wasserstein distance.

    Source: §1 · p. 2, §5 · p. 14

  • Takeaways & Limitations

    Under the stated structural assumptions, sampling is provably tractable when the target is not too badly nonconvex.

    Source: §1 · p. 2

    The guarantees retain exponential dependence on LR^2, and the paper identifies reducing this dependence as an open direction.

    Source: §1 · p. 2, §5 · p. 14

Abstract

from arXiv · show

We study the problem of sampling from a distribution $p^*(x) \propto \exp\left(-U(x)\right)$, where the function $U$ is $L$-smooth everywhere and $m$-strongly convex outside a ball of radius $R$, but potentially nonconvex inside this ball. We study both overdamped and underdamped Langevin MCMC and establish upper bounds on the number of steps required to obtain a sample from a distribution that is within $ε$ of $p^*$ in $1$-Wasserstein distance. For the first-order method (overdamped Langevin MCMC), the iteration complexity is $\tilde{\mathcal{O}}\left(e^{cLR^2}d/ε^2\right)$, where $d$ is the dimension of the underlying space. For the second-order method (underdamped Langevin MCMC), the iteration complexity is $\tilde{\mathcal{O}}\left(e^{cLR^2}\sqrt{d}/ε\right)$ for an explicit positive constant $c$. Surprisingly, the iteration complexity for both these algorithms is only polynomial in the dimension $d$ and the target accuracy $ε$. It is exponential, however, in the problem parameter $LR^2$, which is a measure of non-log-concavity of the target distribution.

1. Introduction

The paper studies overdamped and underdamped Langevin MCMC for targets whose potential is smooth everywhere but strongly convex outside a ball. It establishes Wasserstein-1 sampling rates polynomial in dimension and accuracy, with exponential dependence only on LR^2, a measure of nonconvexity.

Problem and methods

  • Under an L-smoothness assumption and strong convexity outside radius R, the paper analyzes gradient-based overdamped and underdamped Langevin MCMC for sampling from p*(x) ∝ exp(−U(x)).The rates are measured in 1-Wasserstein distance.Source: §1 · pp. 1–2

Main contribution

  • The main contribution is polynomial dependence on dimension d and target accuracy ε, with exponential dependence on LR^2, so sampling remains tractable when nonconvexity is not too severe.The paper frames LR^2 as a measure of the potential’s nonconvexity.Source: §1 · pp. 2–3

Underdamped Langevin MCMC

  • Underdamped Langevin MCMC requires approximately e O(e^{cLR^2}√d/ε) iterations, retaining a quadratic speed-up in d and ε over the overdamped method.Here c is an explicit positive constant.Source: §1 · pp. 2–3

Overdamped Langevin MCMC

  • Overdamped Langevin MCMC requires approximately e O(e^{cLR^2}d/ε^2) iterations, combining continuous-time contraction with discretization-error analysis.This rate extends the expected d/ε^2 dependence to the nonconvex setting under the stated assumptions.Source: §1 · p. 3

Related work

  • For overdamped Langevin MCMC, combining Eberle (2016)’s continuous-time convergence rate with Durmus and Moulines (2016)’s discretization analysis yields e O(ecLR2d/ε2) timesteps.Source: §1 · p. 3

2. Notation, definitions and assumptions

The paper establishes notation for norms and Brownian motion, assumes a smooth potential that is stationary at zero and strongly convex outside a ball, and defines coupling-based Wasserstein analysis.

2. Notation, definitions and assumptions

  • The notation section fixes q-norms for vectors in R^d and uses B_t for standard Brownian motion.Source: §2 · p. 4

2.1 Assumptions on the potential U

  • The potential U is continuously differentiable with L-Lipschitz gradients, has a stationary point at zero, and is strongly convex outside a radius-R ball with parameters m and R.The condition number is defined as κ := L/m; placing the stationary point at zero is without loss of generality by shifting coordinates.Source: §2.1 · pp. 4–5

2.2 Coupling and Wasserstein distance

  • The paper defines transference plans and couplings between probability measures on R^d, forming the basis for its Wasserstein-distance analysis.Source: §2.2 · p. 5

3. Overdamped Langevin diffusion

This section analyzes overdamped Langevin diffusion and its discretized, implementable MCMC algorithm, whose iterates target p*(y) ∝ e−U(y). The resulting iteration complexity is exponential in nonconvexity LR^2 but polynomial in dimension and accuracy when LR^2 is constant.

Method

  • The overdamped Langevin SDE has invariant distribution p*(y) ∝ e−U(y), and its discretization yields Algorithm 1 with matching iterate and SDE marginals.The discretized process uses step size δ and can be implemented using a gradient oracle.Source: §3 · pp. 5–6

Convergence rate

  • For constant LR^2, overdamped MCMC requires eΩ(d/ε^2) iterations, matching the strongly log-concave rate of Durmus and Moulines (2016).Theorem 2 provides the convergence guarantee for the discretized algorithm under the stated step-size, initialization, and accuracy conditions.Source: §3 · pp. 5–6

Interpretation

  • LR^2 measures nonconvexity, and large values can correspond to numerous deep local minima, explaining exponential runtime dependence on this quantity.The strong-convexity and target-accuracy assumptions are presented as simplifications that can be removed or arranged without loss of generality.Source: §3 · p. 6

4. Underdamped Langevin diffusion

This section develops underdamped Langevin MCMC, its implementable discretization, and a coupling-based convergence analysis. It establishes almost-sure exponential contraction through alternating reflection and synchronous coupling phases, yielding iteration complexity exponential in $LR^2$ but polynomial in dimension and target accuracy.

4. Underdamped Langevin diffusion

  • Underdamped Langevin MCMC uses a discretized second-order diffusion whose y-marginal has invariant distribution p* and is implemented by Algorithm 2.The discretized iterates have the same distribution as the continuous-time SDE at matching times.Source: §4 · p. 7
  • For constant LR^2, the method requires e O(d/ε) iterations, a quadratic improvement over first-order overdamped Langevin MCMC.The complexity remains exponential in LR^2, while the condition on strong convexity and target accuracy is stated to be removable.Source: §4 · p. 8

4.1 A coupling construction

  • The coupling construction combines synchronous noise coupling near the target and reflection coupling in selected directions, with a smoothed distance and update schedule ensuring regularity.The constructed dynamics are distributionally equivalent to the original underdamped Langevin SDE.Source: §4.1 · pp. 8, 10

4.2 Lyapunov Function

  • A Lyapunov function built from a decreasing distance function contracts at rate e−Cmt, implying convergence of the coupled distributions in 1-Wasserstein distance.The proof analyzes the discretization-error processes together with the coupling state.Source: §4.2 · pp. 11–12

4.3 Proof Sketch

  • The proof sketch follows the Lyapunov function pathwise, alternating reflection and synchronous coupling as the process moves through the regions illustrated in Figure 1b.The analysis simplifies by temporarily setting discretization-error terms to zero.Source: §4.3 · pp. 12–13
  • The distance measure f contracts almost surely at rate exp(−Cmt), and the Lyapunov function L_t inherits the same rate.This follows from Lemmas 9, 29, and 30.Source: §4.3 · p. 13
  • During synchronous coupling, f(r_t2) ≤ e−Cm(t2−t1)f(r_t1) almost surely because Assumption (A3) ensures contraction when the state is sufficiently large.The argument uses synchronous coupling over [t1, t2).Source: §4.3 · pp. 13–14
  • When reflection coupling resumes after T_sync, the Lyapunov-function jump at t2 is negative almost surely, preserving contraction across the transition.The jump is from exp(−Cm(t2−t1))f(r_t1) to f(r_t2).Source: §4.3 · p. 14

5. Discussion · Appendix · Appendix A. Index of notation

The discussion highlights polynomial-time sampling under a structural assumption more general than log-concavity, with underdamped dynamics improving runtime, while the appendices provide proofs, coupling details, notation, and analysis constants. Future work targets weaker or alternative structural assumptions and algorithms using richer information.

5. Discussion

  • The paper establishes sampling guarantees polynomial in dimension and accuracy under a structural assumption more general than log-concavity, with underdamped dynamics improving runtime as in the strongly convex case.The authors identify this as a central contribution of the work.Source: §5 · p. 14
  • Future work includes finding assumptions that reduce the exponential dependence on LR^2, extending guarantees to weak convexity outside a ball, and using Metropolis-Hastings or higher-order discretizations.These directions broaden both the admissible target distributions and the algorithmic information available beyond gradient oracles.Source: §5 · p. 14

Appendix

  • The appendix contains notation, auxiliary constants, theorem proofs, contraction constructions, moment bounds, coupling results, and verification that Algorithm 2 implements (7).Appendices A–H organize the supporting definitions and technical analysis.Source: Appendix · p. 18

Appendix A. Index of notation

  • Appendix A lists the paper’s variables alphabetically and references their definitions.The index includes parameters, rates, approximation functions, and quantities used by both overdamped and underdamped analyses.Source: Appendix · p. 18
  • The notation index defines α_f and R_f as parameters of f, and records C_m and C_o as underdamped and overdamped contraction rates.It also identifies ℓ as a twice continuously differentiable approximation to the Euclidean norm.Source: Appendix A · p. 19
  • The index identifies L as both the Lipschitz gradient parameter and Lyapunov function, while m is the contraction parameter outside the R ball.These symbols refer to distinct roles despite sharing the notation L.Source: Appendix A · p. 19
  • The index also records M for analysis-specific definitions and ν as the coupling stepsize used in underdamped coupling.ν is additionally referenced in the appendix’s discussion of the small constants.Source: Appendix · p. 18, Appendix A · p. 19

Appendix B. Two Small Constants · Proof

Appendix B specifies small parameters β and ν that regularize the proofs while remaining inverse-polynomial in the problem parameters. It defines the smooth norm approximation and explains the discretized coupling used to establish existence and control its error.

Appendix B. Two Small Constants

  • The paper takes β = 1/poly(L, 1/m, d, R) as a small constant controlling smoothing, with exact β values specified in the proofs of Theorems 2 and 3.β can be made arbitrarily small without additional computation costs.Source: Appendix B · p. 20
  • The smoothed approximation q(r) to |r| yields a function ℓ(·) approximating ∥·∥2 with continuous second derivatives.For ∥x∥2 ≥ β/2, ℓ(x) equals ∥x∥2, while its deviation from the norm is at most β/3.Source: Appendix B · pp. 20–21
  • Because ℓ(·) is strongly convex with parameter 1/β^2 near zero, the coupling is designed to have no noise within radius β/2.This avoids complications caused by the smoothing region’s strong convexity.Source: Appendix B · p. 20
  • ν discretizes switches between synchronous and reflection coupling at deterministic finite intervals, making strong-solution existence verifiable by standard results.Although discontinuous-coefficient SDE results could suffice, the proof uses this discretized construction instead.Source: Appendix B · p. 20
  • The discretized coupling introduces σt, whose error is o(ν^2), and ν = 1/poly(L, 1/m, d, R) can be taken arbitrarily small without added computation costs.The exact value of ν is specified in the proof and Theorem 3.Source: Appendix B · p. 20
  • The approximation satisfies ∥∇ℓ(x)∥2 ≤ 1, agrees with the normalized vector outside radius β/2, and has everywhere-defined continuous derivatives.These properties follow from the corresponding regularity and monotonicity properties of q.Source: Appendix B · p. 21, Proof · p. 21

Proof

  • The proof establishes the smoothing lemmas by applying the chain rule and verifying algebraically that q and ℓ have the stated bounds, derivatives, and continuity.In particular, q(r), q′(r)/r, and q′′(r)/r^2 are continuous, while q(r)=r for r≥β/2.Source: Proof · pp. 21–22

Appendix C. Proofs for overdamped Langevin Monte Carlo · C.1 Coupling construction for overdamped Langevin MCMC

Appendix C.1 constructs a coupling for overdamped Langevin MCMC and develops the ingredients needed to analyze convergence of the continuous-time process. The construction preserves the target SDE’s marginal distribution and uses a Lyapunov process for the convergence argument.

C.1 Coupling construction for overdamped Langevin MCMC

  • The construction introduces a small constant β and a smoothed approximation ℓ(x) = q(||x||_2) of ||x||_2.Source: §C.1 · p. 22
  • The proof begins by establishing convergence of the continuous-time process to its invariant distribution through a coupling of the SDEs in Eqs. (3) and (4).Source: §C.1 · p. 22
  • The coupled processes are initialized together and evolved using their difference z_t and a distance-dependent function M(r).Source: §C.1 · p. 22
  • The coupling coefficients γ_t and γ̄_t are Lipschitz and gradient-Lipschitz for every z_t ∈ R^d, with 0/0 defined as 0 when ||z_t||_2 = 0.Source: §C.1 · p. 23
  • Lemma 8 states that the coupled dynamics in Eq. (31) is distributionally equivalent to the SDE in Eq. (3).Source: §C.1 · p. 23
  • The proof then defines f(r_t), two stochastic processes, and a resulting stochastic process L_t that serves as the Lyapunov function.Source: §C.1 · p. 23

C.2 Proof of Theorem 2

The proof establishes Theorem 2 through a three-step argument: control the transformed process, prove Lyapunov contraction, and convert that contraction into an iteration-complexity bound in 1-Wasserstein distance.

Proof strategy

  • The proof first analyzes f(ℓ(z_t)) with Itô’s lemma, using a technique essentially taken from Eberle (2016), and bounds its drift across the regions defined by β and R.The regional bounds use smoothness, strong convexity outside the radius-R ball, and properties of the auxiliary functions f and q.Source: §C.2 · pp. 23–24

Lyapunov contraction

  • The second step shows that the Lyapunov function L_t defined in Eq. (38) contracts sufficiently fast, then applies Grönwall’s inequality and expectation bounds to obtain its finite-time estimate.The argument differentiates the stochastic processes φ_t and ξ_t and controls the initial value before setting t = nδ.Source: §C.2 · pp. 26–27

Wasserstein guarantee

  • The final step translates the bound on E[f(ℓ(z_{nδ}))] into a bound on E[∥z_{nδ}∥2], which yields the theorem’s 1-Wasserstein iteration-complexity guarantee.This translation uses Lemma 31(F3), the definition of C_o, the theorem’s condition on m, and the prescribed accuracy restriction.Source: §C.2 · p. 28

Appendix D. Proofs for Underadmped Langevin Monte Carlo · D.1 Overview · D.2 Contraction under Reflection Coupling

Appendix D proves underdamped Langevin contraction by analyzing four switching cases for a Lyapunov quantity, then applying the resulting contraction recursively to control Wasserstein distance. The reflection-coupling argument establishes exponential contraction with discretization error terms through derivative bounds, case analysis, and Grönwall’s lemma.

D.1 Overview

  • The proof’s central claim is that L_t contracts almost surely by e^(-C_mν) over each interval [(k−1)ν, kν].Lemma 26 is established by proving the same contraction bound across all four possible transitions of μ_k.Source: §D.1 · p. 29
  • The four switching cases μ_{k−1}, μ_k ∈ {0,1} each satisfy L_{kν} ≤ e^(-C_mν)L_{(k−1)ν}.The μ_{k−1}=0, μ_k=1 transition is the difficult case because L_t jumps at t=kν, but the jump is proved negative.Source: §D.1 · p. 29

D.2 Contraction under Reflection Coupling

  • Lemma 9 shows that μ_k f(r_t) contracts at rate exp(−C_m t), up to discretization error terms.The contraction is proved under reflection coupling using a tailored function f and bounds on its derivatives and associated terms.Source: §D.2 · pp. 29–30
  • Itô’s lemma and the derivative identities reduce the analysis to a differential inequality with contraction rate C_m and error term 5βd_s.The resulting bound is d(μ_k·(f(r_s)−ξ_s)−σ_s−φ_s) ≤ −C_m(μ_k·(f(r_s)−ξ_s)−(σ_s+φ_s)) + 5βd_s.Source: §D.2 · pp. 30, 35
  • The reflection-coupling proof bounds the drift contributions separately across four regions determined by whether ||z_s||_2 and ||z_s+w_s||_2 lie below or above β.The argument uses the expression for q′ in each region and combines the resulting bounds with properties of f, q, and the coupling dynamics.Source: §D.2 · pp. 32–33

D.1 Overview

  • Grönwall’s lemma converts the differential inequality over each interval [kν,(k+1)ν) into the claimed contraction result.Lemma 26 is then applied recursively, while E[L_t] is shown to sandwich W_1(p_t,p*), yielding the theorem.Source: §D.1 · p. 29, §D.2 · p. 35

D.3 Main results for synchronous coupling

Lemma 10 establishes that, with probability one, the synchronous coupling contracts over each period Tsync by the factor exp(−CmTsync). This period-wise contraction is weaker than a bound for every time t but sufficient for the paper’s purposes.

Main result

  • With probability one, f(r_s) contracts over each Tsync period by exp(−CmTsync), under e^72LR^2 ≥ 2.The result applies at synchronization times and is sufficient despite not proving contraction at every t.Source: §D.3 · pp. 35–36

D.4 Discretization Error Bound … Appendix F. Bounding moments

This section develops the Lyapunov and moment analyses underlying the underdamped Langevin convergence proof. It establishes properties of the auxiliary function and bounds the discretization-error terms needed to combine with Lyapunov contraction.

D.4 Discretization Error Bound

  • The discretization analysis separately bounds E[ξ_t], E[σ_t], and E[φ_t], with E[φ_t] = 0 because φ_t is a martingale.E[ξ_t] arises from using ∇U instead of ∇U(x_t), while E[σ_t] arises from updating τ_k and μ_k only at discrete ν-intervals.Source: §D.4 · p. 44, §D.4.1 · p. 44, §D.4.2 · pp. 45, 50

D.4.1 Bound on E[ξ_t]

  • E[ξ_t] is bounded using the moment bounds established in Appendix F, together with Lemma 15 and its supporting corollaries.This term quantifies the gradient-discretization discrepancy between ∇U and ∇U(x_t).Source: §D.4.1 · p. 44

D.4.2 Bounds on E[σ_t] and E[φ_t]

  • For β ≤ 0.0001R and sufficiently small ν, Lemma 18 bounds E[σ_t] with constants polynomial in L, 1/m, d, R, and 1/C_m.The admissible step condition is ν ≤ C_3, where C_3 = 1/poly(L, 1/m, d, R).Source: §D.4.2 · p. 45
  • Corollary 21 provides the resulting small-ν control of the discretization terms under the same β condition, while Lemma 23 gives E[φ_t] = 0.The σ_t bound depends on ν and can therefore be made arbitrarily small.Source: §D.4.2 · pp. 45, 49, 50

D.5 Putting it all together

  • The final proof combines the discretization bounds with results from Appendices D.2 and D.3, showing Lyapunov contraction with probability one and completing Theorem 3.The contraction argument is organized through Lemma 26, which combines Lemmas 27–30; the proof then specifies the algorithm’s number of steps.Source: §D.5 · pp. 50, 52
  • Lemmas 29 and 30 bound the Lyapunov function across indicator transitions by exponential contraction terms plus 5β or 5β^ν.These bounds cover the cases (µ_k, µ_{k−1}) = (1,1) and (0,1), while the preceding material includes the (0,0) case.Source: §D.5 · p. 58

Appendix E. Properties of f

  • Under e^(72LR^2) ≥ 2, the auxiliary function f satisfies f(0)=0, f′(0)=1, has f′′(r)≤0, and becomes linear-curvature-free for r>2R_f.The concavity follows from ψ′≤0, g′≤0, ψ≥0, and g≥1/2; beyond 2R_f, both derivatives vanish.Source: Appendix E · pp. 59–60

Appendix F. Bounding moments

  • Bounding moments of x_t, u_t, y_t, and v_t is necessary for discretization-error analysis, with Lemmas 32 and 33 providing the main moment bounds.Lemma 32 concerns x_t and u_t, whereas Lemma 33 concerns y_t and v_t.Source: Appendix F · p. 61

F.1 Proof of Lemma 32 · F.2 Proof of Lemma 33

These appendices prove Lemmas 32 and 33 by analyzing Lyapunov-function evolution under the respective stochastic dynamics. The arguments combine Itô calculus, auxiliary inequalities, step-size conditions, and recursive or invariant-distribution bounds.

F.1 Proof of Lemma 32

  • Lemma 32’s proof derives the Lyapunov-function evolution and bounds its three resulting terms separately.The bounds invoke auxiliary lemmas, smoothness, Cauchy–Schwarz, Young’s and Jensen’s inequalities, the dynamics, and algebraic estimates.Source: §F.1 · pp. 63–64
  • Applying Grönwall’s lemma over each interval and then recursively using a geometric sum extends the Lemma 32 bound to all positive integer steps and arbitrary t ≥ 0.The proof concludes by combining the one-step estimate with Eq. (78) and Grönwall’s lemma.Source: §F.1 · p. 65
  • The paper introduces auxiliary lemmas useful in the preceding proof; Lemma 34 assumes δ ≤ 1/1000, and its derivation cites Itô’s Lemma, Assumption (A1), Young’s inequality, and cκ from Eq. (6).Source: §F.1 · pp. 65–66

F.2 Proof of Lemma 33

  • Lemma 33 analyzes its Lyapunov function with Itô’s lemma, and the Brownian-motion term vanishes after taking expectations.Because (y_t, v_t) follows the invariant distribution p* for all t ≥ 0, the resulting expectation bound completes the lemma.Source: §F.2 · p. 69
  • Lemma 36 analyzes the dynamics by splitting cases according to whether ∥x_kδ∥₂ is at least or at most R, using Assumptions (A1) and (A3), δ ≤ 1/(κL), and recursive iteration over k steps.Source: §F.2 · pp. 70–71
  • A second Itô calculation bounds the Lyapunov drift by separating contributions supported inside and outside the radius-R region.The indicator identities follow from the definition of l(y), while Young’s inequality controls the remaining terms before expectations are taken.Source: §F.2 · pp. 71–72

Appendix G. Existence of Coupling · Appendix H. Coupling and Discretization

Appendix G establishes well-posedness of the coupled stochastic processes, while Appendix H validates the Brownian coupling and derives an explicit Gaussian representation for the discretized underdamped dynamics. Together, these results justify the coupling construction and enable efficient coordinatewise sampling.

Appendix G. Existence of Coupling

  • The proof verifies the required Lipschitz conditions for the drift and diffusion terms, including the transformed covariance structure.Source: Appendix G · pp. 73–74
  • The coupled process has a unique strong solution that is t-continuous with probability one under the stated regularity conditions.Source: Appendix G · pp. 73, 75
  • The solution is adapted to the filtration generated by the process states and Brownian increments.Source: Appendix G · p. 73
  • The constructed process φ_t likewise has a unique solution that is almost surely continuous and adapted to the relevant filtration.Source: Appendix G · p. 75

Appendix H. Coupling and Discretization

  • The transformed noise process is shown to be Brownian because it is a continuous martingale with quadratic variation (s′ − s)I.Source: Appendix H · p. 76
  • Conditioned on (x_kδ, u_kδ), the discretized underdamped solution over one step is an explicitly characterized Gaussian.Source: Appendix H · p. 77
  • The Gaussian representation includes conditional means, variances, and cross-covariances for x_t and u_t.Source: Appendix H · pp. 77–78
  • Sampling from this Gaussian takes time linear in d because its d coordinates are independent.Source: Appendix H · p. 78

Related papers

Loading 1805.01648v4…