PaperlayerView exact revision on arXiv

Source-linked AI summary

Persistence Pays: Square-root condition-number dependence for Metropolis-adjusted kinetic Langevin Monte Carlo with a non-reversibly updated accept/reject uniform

Nawaf Bou-Rabee

arXiv:2610.35781v1math.PRcs.NAmath.NAstat.CO

TL;DR

Square-root acceleration under numerical discretization remains open for general strongly log-concave targets. The paper analyzes Metropolis-adjusted OBABO and reports logistic-regression costs growing like the square root of the condition number at the mode, while its theorem gives a κ^3/4 cost there.

  • Problem

    Whether kinetic Langevin’s square-root acceleration survives numerical discretization remains open for general strongly log-concave targets.

    Source: §1 · p. 1

  • Method

    The analysis studies OBABO with friction 2√m and couples adjusted-chain copies using unadjusted endpoint laws.

    Source: §1.1 · p. 1, §1.2 · p. 3

  • Results

    For logistic-regression posteriors, the theorem gives cost of order κ^3/4, while measured cost grows like the square root of the condition number at the mode.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    For fixed d ≥ 2, the √κ dependence cannot be improved beyond logarithmic factors, and a warm start does not remove it.

    Source: §2.4 · p. 9

    The present argument requires a Lipschitz Hessian; with only strong convexity and a Lipschitz gradient, the available summed bound is not small at the theorem’s step size.

    Source: §1.4 · p. 4

Abstract

from arXiv · show

We prove accelerated mixing for a Metropolis-adjusted kinetic Langevin sampler: the OBABO splitting with friction $2\sqrt m$, adjusted with Neal's non-reversibly updated uniform, which is redrawn after every epoch of $E$ steps. For targets $e^{-U}$ on $\mathbb{R}^d$ with $mI\preceq\nabla^2U\preceq LI$ and an $L_H$-Lipschitz Hessian, started from a Gaussian at an approximate minimizer, the chain reaches total variation accuracy $\varepsilon$ after $\tilde O\big(\sqrt{\kappa d}+\sqrt{L_H}(d/m)^{3/4}\big)$ gradient evaluations, where $\kappa=L/m$ and $\tilde O$ hides logarithmic factors. The $\sqrt\kappa$ term is necessary, already on Gaussian targets. The proof discretizes Lu's entropic hypocoercivity by means of an entropy inequality for free transport, so that the relative entropy of the unadjusted chain decays at a rate of order $\sqrt m$ up to a discretization bias. With the non-reversibly updated uniform, the leading energy errors of velocity Verlet telescope along a path. A coupling argument combines the two. On Bayesian logistic regression posteriors for two standard data sets, which satisfy these assumptions, the gradient cost of the chain with the non-reversibly updated uniform grows roughly like the square root of the condition number at the posterior mode, and that of standard adjusted OBABO roughly like its $3/4$ power.

1. Introduction.

The paper studies whether kinetic Langevin’s square-root condition-number acceleration survives discretization and Metropolis adjustment. It analyzes an OBABO sampler with a non-reversibly updated acceptance threshold, proves mixing guarantees, and explains the proof’s scope and limitations.

1.1. The sampler and the main result.

  • The sampler uses OBABO with friction 2√m and Neal’s non-reversibly updated uniform, drawing a threshold once per epoch and updating it after accepted moves.The acceptance rule keeps the target invariant; accumulated energy errors govern rejection within an epoch.Source: §1.1 · pp. 1–2
  • On logistic regression posteriors, the theorem’s bound scales like κ^3/4, while measured cost grows roughly like the square root of the condition number at the mode.For these posteriors, L_H grows like κ^3/2, making the theorem’s second term dominant.Source: §1.1 · p. 2

1.2. Ingredients of the proof.

  • An entropy inequality for free transport controls the trapezoidal-rule mismatch in OBABO, enabling discrete entropic hypocoercivity with decay rate of order √m in physical time, uniformly in κ up to discretization bias.The bias depends on step size, energy and velocity moments, and L_H.Source: §1.2 · p. 3

1.3. Sketch of the proof of Theorem 1.

  • The non-reversibly updated threshold makes rejection depend on accumulated epoch energy error; telescoping leading Verlet errors avoids a rejection bound growing with the number of steps.The remaining rejection control depends on the accumulated trapezoidal errors and moment bounds.Source: §1.2 · p. 3

1.2. Ingredients of the proof.

  • The proof couples adjusted and unadjusted chains at epoch endpoints, using entropy contraction and bounds on epoch rejection probabilities to control their meeting probability.An L2 warm start transfers the stationary bound on epochs beginning outside the high-acceptance set; the argument needs no bound on adjusted-chain excursions.Source: §1.2 · p. 3

1.4. The role of the Hessian-Lipschitz constant.

  • The proof’s Hessian-Lipschitz assumption controls the cubic trapezoidal error; with only strong convexity and a Lipschitz gradient, its available summed bound is not small at the theorem’s step size.The paper leaves open whether sharper cancellation arguments can remove this assumption for square-root acceleration.Source: §1.4 · p. 4

1.5. Relation to the literature.

  • The paper presents its adjusted-chain result as a first √κ mixing bound for a Metropolis-adjusted kinetic Langevin discretization on a class of non-Gaussian targets.It also gives a discrete entropic hypocoercivity bound for unadjusted OBABO; the paper reports formal verification of Theorems 1 and 2 and Propositions 2.4 and 3.1 in Lean 4.Source: §1.5 · pp. 4–5, §1.7 · p. 5

2. Setting and main results.

The paper studies Metropolis-adjusted OBABO under strong convexity, smoothness, and Hessian-Lipschitz assumptions, using an epoch-wise non-reversibly updated uniform. It proves mixing and relative-entropy results, and establishes that the square-root condition-number dependence is necessary for the adjusted chain.

2.1. Notation and assumptions.

  • The target assumes mI ⪯ ∇²U(x) ⪯ LI and an LH-Lipschitz Hessian; its phase-space law combines the position target with standard Gaussian velocity.The condition number is κ = L/m, and the dimensionless Hessian-Lipschitz ratio is lH = LH/m^3/2.Source: §2.1 · p. 6

2.2. OBABO.

  • OBABO uses friction γ = 2√m, with velocity Verlet between Ornstein-Uhlenbeck half-steps; each flight advances position by hV.The position and velocity are tracked through the Verlet step and the intervening free flight.Source: §2.2 · p. 6

2.3. The adjusted chain.

  • Each epoch draws one exponential threshold, carries it across E accept/reject steps, and updates it after accepted moves by subtracting the energy error.In uniform form, the threshold is Neal’s update u ← ue^∆H; it remains unchanged on rejection.Source: §2.3 · p. 7
  • Along a rejection-free epoch, accumulated Verlet energy errors telescope through the G terms, unlike the sum of positive parts under a fresh uniform at every step.The chain is invariant because the accept/reject update preserves the extended target µ ⊗ Exp(1).Source: §2.3 · p. 7

2.4. Main results.

  • Theorem 1 reaches total variation accuracy ε after at most NE+1 gradient evaluations for an initial law with finite L2 warmness, with parameters chosen from κ, lH, d, warmness, and ε.Up to logarithms, the step size is the smaller of D^-1/2 and (κ/(lH D^3/2))^1/2, and an epoch lasts order Λ units of 1/√m.Source: §2.4 · p. 9
  • For every fixed dimension, the √κ factor in the adjusted-chain bound cannot be improved beyond logarithmic factors, even from a warm start and on Gaussian targets.The proposition also bounds dimension dependence over all step sizes between d^1/6 and d^1/2 for its Gaussian family.Source: §2.4 · pp. 9–10
  • Under the stated assumptions, unadjusted OBABO has relative-entropy decay at a rate involving no κ, while its discretization bias depends on the upper Hessian bound and velocity moments.The theorem applies when γ = 2√m and √mh ≤ 3/16; its moment terms are not controlled uniformly over the class at flight speeds above v*.Source: §2.4 · p. 10

3. An entropy inequality for free transport.

The section establishes an entropy inequality for free transport and gives proofs under different assumptions. It then recasts the inequality in the form used for OBABO.

3. An entropy inequality for free transport.

  • For X and V, the entropy at an intermediate free-transport time is bounded by the sum of its endpoint entropies.The result is stated for a nondegenerate Gaussian reference density; the section gives a proof via strong subadditivity and a general proof without moment assumptions.Source: §3 · p. 10, §3.1 · p. 11

3.1. Proof by strong subadditivity.

  • The first proof uses strong subadditivity along a Brownian bridge, assuming finite second moments and finite differential entropy.The proof relates the entropy of the interpolated position to the endpoint entropies.Source: §3 · p. 10, §3.1 · p. 11

3.2. The general case.

  • A dual proof requires only finite endpoint relative entropies; the Gaussian relative-entropy term cannot generally be omitted.The section notes that intermediate mutual information can exceed the sum of endpoint mutual informations.Source: §3.2 · pp. 11–12

3.3. The form used for OBABO.

  • For OBABO, the inequality bounds velocity entropy along a free flight by the endpoint velocity entropies.The corollary follows by rescaling velocity and applying the proposition with a Gaussian reference of covariance h^2I.Source: §3.3 · p. 13

4. Discrete entropic hypocoercivity for OBABO.

The section adapts entropic hypocoercivity to OBABO by controlling free transport and the trapezoidal-rule error in the transport corrector. It obtains one-step decay of a corrected entropy functional, with energy-error increments controlled by summation by parts.

4.1. Functionals.

  • The functional combines relative entropy with Lu’s transport corrector, the derivative of half the squared Wasserstein distance along free transport.The section also records bounds relating velocity entropy, position Wasserstein distance, and the corrector.Source: §4.1 · p. 13

4.2. Exact one-step identities.

  • The Ornstein-Uhlenbeck half-steps contract velocity entropy and scale the corrector, while force kicks preserve the position marginal and change the corrector explicitly.The velocity entropy contracts by e^(-2√mh) under an Ornstein-Uhlenbeck half-step.Source: §4.2 · pp. 13–14

4.3. Free transport.

  • An entropy inequality for free transport bounds velocity entropy between flight endpoints and supports an integrated bound on the corrector’s change.The proof extends the free-transport estimate to general laws through approximation; the section notes that the force-transport cancellation becomes a trapezoidal rule in OBABO.Source: §4.3 · pp. 15–16

4.4. The trapezoidal rule error.

  • The trapezoidal-rule error controls the mismatch between the integrated velocity entropy during a flight and its endpoint approximation.The section expresses this error through the velocity-Verlet step and bounds it using endpoint velocity entropies.Source: §4.4 · p. 16

4.5. The corrector over one velocity Verlet step.

  • Over one velocity-Verlet step, the corrector bound combines free-transport control with the trapezoidal-rule error.The bound does not require Fisher information, a Hessian-Lipschitz constant, or a lower bound on elapsed time.Source: §4.5 · p. 17

4.6. One-step decay of Ent + η C.

  • The corrected functional H=Ent+ηC obeys a one-step decay bound with an energy-error increment and nonnegative remainder terms.Across steps, summation by parts bounds the geometrically weighted leading energy-error contribution by the terminal energy term.Source: §4.6 · pp. 18–19
  • The one-step estimate combines Ornstein-Uhlenbeck entropy dissipation with the corrector bound to contract the corrected functional.The energy-error increments telescope under summation by parts, leaving a terminal term and nonpositive terms.Source: §4.6 · pp. 18–19

4.7. Proof of Theorem 2.

  • The proof of Theorem 2 applies the one-step estimate to OBABO and uses a starting-entropy bound for the initialized chain.The section specifies parameter choices and derives the resulting decay bound.Source: §4.7 · p. 19

5. The non-reversibly updated uniform, the coupling argument and moment bounds.

This section controls epoch-level rejection using accumulated signed energy errors and endpoint coupling, while developing moment bounds for the unadjusted chain and a faster-flight comparison chain. It bounds the comparison chain’s Gaussian-energy growth and transition-density supremum in terms of h, d, and the OU contraction factor r.

5.1. Acceptance of every move of an epoch.

  • Acceptance throughout an epoch depends on the maximum partial sum of signed energy errors, rather than the sum of positive one-step errors.On full acceptance, the adjusted epoch coincides with the unadjusted chain; for quadratic U, the leading energy-error remainder vanishes.Source: §5.1 · pp. 19–20

5.2. The coupling theorem.

  • A maximal coupling of whole noise blocks makes the unadjusted chains’ endpoint disagreement probability equal their total variation distance.The coupling theorem combines this endpoint coupling with epoch rejection bounds; localization is required only at epoch boundaries, using stationarity and an L2(µ) warm start.Source: §5.2 · pp. 20–21

5.3. Moments of the unadjusted chain on the region where friction dominates.

  • On the friction-dominated region, the drift and stopped-moment bounds control the unadjusted chain’s energy and flight-speed moments.The stated comparisons are 0.79H ≤ V ≤ 1.2H and 0.996H ≤ HG ≤ H; the moment argument applies below the speed threshold v∗.Source: §5.3 · pp. 22–23

5.4. A comparison chain.

  • A comparison chain follows velocity Verlet for flights at most v∗ and reverses velocity without moving position for faster flights.Its modified energy satisfies HG(Φ♯(w)) ≤ (1 + 0.081h)HG(w), and its corrector bound supports an entropy-decay estimate for the comparison chain.Source: §5.4 · pp. 23–25
  • a_k ≤ 1.008ρ^(k−1)(a_0 + 2kb), with b = h(d + 2) and ρ = 1 + 0.081h, bounds the comparison chain’s Gaussian-energy moment.The passage also states that the L2 norm of H_G increases by at most h(d + 2) per step and that b is added for W♯_k.Source: §5.4 · p. 26
  • The density of δ_zK is bounded by (2πhσ²)^−d; Lebesgue-preserving bijections preserve its supremum, while an OU half-step multiplies it by at most r^−d = e^(dh).Source: §5.4 · p. 26

6. Proof of the main theorem.

The proof establishes mixing under four conditions controlling rejection, numerical error, entropy decay, and escape from the friction-dominated region. It chooses epoch and step-size parameters to satisfy those conditions, yielding total variation accuracy ε at the stated gradient cost.

Proof of the main theorem

  • The explicit conditions separately control the entropy-decay bias and trapezoidal-rule errors, while the escape condition keeps the chain in the friction-dominated region with high probability.With fresh uniforms, the rejection term would instead be of order E h̄^3 Q.Source: §6 · p. 26
  • The proof sets the epoch duration to t0 = CΛ and chooses the smaller step size allowed by the leading energy-error and accumulated trapezoidal-remainder constraints.The epoch must also be long enough for the entropy term to decay.Source: §6 · p. 28
  • A single sufficiently large absolute constant makes all four conditions hold, giving TV(νP^N,µ) ≤ ε.The conditions control rejection, numerical error, entropy decay, and escape from the region where friction dominates the energy error.Source: §6 · pp. 26, 28
  • The parameter choice bounds the total cost by NE + 1 gradient evaluations.The proof uses a logarithmic bound on N and an upper bound on Q to establish the cost.Source: §6 · p. 28

7. Bayesian logistic regression.

On breast-cancer and Sonar logistic-regression posteriors, the non-reversibly updated uniform has empirically lower condition-number scaling in gradient cost than the fresh-uniform chain. The experiments use a step size based on curvature at the mode, outside the theorem’s parameter range.

Curvature of the mode

  • For these posteriors, Theorem 1 guarantees cost of order κ^3/4, with the √lH D^3/4 term growing like κ^3/4 and dominating over our range of s; square-root growth measured below goes beyond what it proves.Source: §7 · p. 29

Data

  • The benchmark uses 569 breast-cancer observations with 30 covariates and 208 Sonar observations with 60 covariates, each with an intercept.The authors report that some parameter directions are nearly linearly separable, where likelihood curvature is almost flat and the prior sets curvature.Source: §7 · p. 29

Global curvature

  • At global-curvature step sizes, both chains reject fewer than 0.2% of moves and their IATs remain between 3.1 and 4.6 time units as κ ranges from 11 to 1.9 · 10^4.At these rejection rates, the two acceptance rules give nearly the same chain.Source: §7 · p. 30

Curvature of the mode

  • In curvature-at-mode experiments, ˆκ = ˆL ranged from 9.5 to 9.5 · 10^4 for breast cancer and 8 to 5.6 · 10^4 for Sonar; chains rejected 7%–11% and 7%–13% of moves, respectively.Source: §7 · p. 30
  • Cost slopes are 0.54 ± 0.01 and 0.50 ± 0.02 for the non-reversibly updated uniform, versus 0.76 ± 0.02 and 0.76 ± 0.05 for fresh uniforms.Figure 4 plots gradient evaluations per effective sample against ˆκ for breast cancer and Sonar, respectively.Source: §7 · p. 30, Figure 4 · p. 30

8. Discussion and open problems.

The discussion identifies open questions about the regularity assumptions, initialization, dimension dependence, and generalizing beyond OBABO. It also specifies gaps between the current bounds and sharper behavior observed or established in narrower settings.

The Hessian-Lipschitz condition

  • Whether square-root acceleration requires a Lipschitz Hessian remains open, although the trapezoidal-error order is sharp under strong convexity and a Lipschitz gradient alone.A Hölder-continuous Hessian of exponent α gives error of order h^(2+α)|V|^(2+α).Source: §8 · pp. 30–31

Cold starts

  • For poorly initialized densities with log M2 of order κd, the first complexity term becomes Õ(κ√d); a bound from an arbitrary point without the optimization initialization stage remains open.The theorem does not directly apply to a point mass, and the approximate-minimizer initialization gradients are additional to sampling cost.Source: §8 · p. 31

Dependence on the dimension

  • The dimension dependence is not known to be optimal: the upper bound is Õ(√κ d^1/2), while the Gaussian lower bound is proportional to √κ d^1/6.The upper bound controls a position-dependent energy term uniformly on an energy sublevel of level at least order d; sharpening it requires better rejection control and larger steps.Source: §8 · p. 31
  • The entropy estimate’s Gaussian moment remainder is O(h̄^2d), while stationary relative entropy for unadjusted OBABO is O(h̄^4d) for steps bounded away from the stability boundary h̄ = 2.Source: §8 · p. 31

Other integrators

  • An analogous accelerated-mixing entropy estimate for other adjusted splittings, including OABAO with the non-reversibly updated uniform, remains open.Source: §8 · p. 31

APPENDIX A: PROOF OF THE FREE-TRANSPORT ESTIMATE (4.4)

The appendix fixes notation for conditional moments and entropy quantities used for a law on position-velocity pairs.

Appendix A

  • The displacement ξ is y − T(y) for a Brenier map, as in [29].Source: Appendix A · p. 31
  • For (Y,W) distributed according to q′, m(y) and Σ(y) denote the conditional mean and covariance of W given Y = y.Source: Appendix A · p. 31
  • The quantities J(q′) and Ev(q′) are the expected squared conditional-mean norm and the conditional relative entropy to φ, respectively.Source: Appendix A · p. 31

A.1. The velocity covariance term.

The appendix bounds the velocity-covariance contribution using Brenier-map structure and Gaussian duality. Centering the conditional laws supplies an additional term in the bound.

A.1. The velocity covariance term.

  • Centering the conditional laws contributes the term −2J; the singular Hessian part enters once with a sign rather than being split into two parts.The text contrasts this treatment with Lu’s separate handling of the Hessian parts.Source: §A.1 · p. 32
  • The Brenier potential has distributional Hessian Gdy plus a singular positive-semidefinite part, and det G is positive almost everywhere.The density relation identifies the determinant of the Alexandrov Hessian with the source and target densities.Source: §A.1 · p. 32
  • Gaussian duality bounds the covariance defect Σ:(I−G) using conditional-law KL divergence, the conditional mean, and log det G.The argument first obtains a pointwise bound and then integrates it against the position density.Source: §A.1 · p. 32

A.2. Free transport of q.

Free transport is represented by adding Gaussian noise to position and velocity and evolving the resulting law. The appendix establishes regularity and moment bounds needed to apply the covariance estimate along this evolution.

A.2. Free transport of q.

  • The free-transport variables are W=V+√ιζ_v and Y_s=X+sV+√ι(ζ_x+sζ_v), with Gaussian noise independent of (X,V).The noise variance parameter is σ_s²=ι(1+s²), and β_s=s/(1+s²).Source: §A.2 · p. 32
  • The transported densities are smooth and the position density has two-sided Gaussian tail bounds uniformly for s in [0,t].These bounds support the moment and integrability estimates used in the argument.Source: §A.2 · p. 33
  • Moment equations yield bounds on the acceleration and its derivative, allowing the covariance lemma to apply to q_s throughout the transport interval.The resulting bounds include |a_s|≤C(1+|y|), |e_s|≤C(1+|y|)^2, and regularity bounds for n_sΣ_s.Source: §A.2 · p. 33
  • The conditional mean and covariance of W given Y_s=y are expressed through β_s y, a conditional average b(s,y), and the covariance of F_s.The conditional law π_{s,y} supplies the averages defining b(s,y) and the covariance term.Source: §A.2 · p. 33
  • The conditional-mean velocity generates a global flow that transports ν_s to ν_s′ between times s and s′.The flow exists because m_s is smooth with bounded spatial gradient, and the continuity equation identifies its transported law.Source: §A.2 · p. 33

A.3. Coupling along the flow of the mean velocity.

The coupling follows the flow generated by the conditional-mean velocity and uses its Taylor expansion to control the Wasserstein distance to the target. The resulting estimate is uniform over the transport interval.

A.3. Coupling along the flow of the mean velocity.

  • A third-order Taylor expansion of the mean-velocity flow controls displacement from its initial point using the velocity, acceleration, and acceleration derivative.The flow derivatives are m, a, and e, with growth bounds that yield a remainder controlled by moments of ν_s.Source: §A.3 · p. 33
  • Coupling the flowed position with its Brenier image bounds W(s+ϑ) by the squared displacement from the original position plus its transport error.The coupling uses (X_ϑ(Y),T_s(Y)) for Y distributed as ν_s.Source: §A.3 · p. 34
  • The cross term and velocity term in that estimate are identified with C(q_s) and J(q_s), respectively.Uniform second-moment bounds make the resulting estimate uniform in s and ϑ.Source: §A.3 · p. 34

A.4. Conclusion.

The appendix sums forward and backward flow estimates over a partition, then passes to an integral using continuity. Bounding the remaining term yields the stated simplified inequality.

A.4. Conclusion.

  • The forward and backward estimates at adjacent partition points are added, causing the Wasserstein terms to cancel across the partition.The partition increment is ϑ=t/N.Source: §A.4 · p. 34
  • Continuity of the upper bound on Q allows the partition sum to converge to its integral over [0,t].The bound uses 4Ev(q_s)−J(q_s)−ΔL(ν_s), with 4Ev(q_s)−ΔL(ν_s) equal to 5h(ν_s) plus a constant.Source: §A.4 · p. 34
  • Using −J≤J≤2Ev simplifies the bound to Q≤6Ev(q_s)−ΔL(ν_s), proving (4.4).Retaining −J would improve the constants of Proposition 4.10 slightly, but the proof does not use that improvement.Source: §A.4 · p. 34

APPENDIX B: PROOF OF PROPOSITION 2.4

For quadratic targets, the appendix bounds mixing by controlling crossings of a stationary half-space under the adjusted chain. It then optimizes a Gaussian step-size expression to obtain the first condition.

APPENDIX B: PROOF OF PROPOSITION 2.4

  • The proof takes A = {x₁ ≤ 0}, which has stationary mass 1/2, and a crossing requires an accepted proposal from x₁ ≤ 0 to x′₁ > 0.The position changes only on accepted moves.Source: Appendix B · p. 34
  • Each step’s crossing probability is bounded by the stationary one-step crossing probability, and the conductance lower bound then yields a mixing-time bound for the extended chain.The stationary crossing probability is defined conditionally on starting in A.Source: Appendix B · pp. 34–35
  • For quadratic U, the energy error is a sum of coordinate-wise terms, with the coordinate pairs independent under μ.This factorization supports the Gaussian crossing analysis.Source: Appendix B · p. 35
  • 64/(3d − 4) is the minimizing value of h̄^6 for the displayed function, yielding the first condition.The minimizing step is within the stated velocity Verlet stability range.Source: Appendix B · p. 35

Related papers

Loading 2610.35781v1…