PaperlayerView exact revision on arXiv

Source-linked AI summary

Provable Non-Acceleration of Standard Strang Splittings of Kinetic Langevin Dynamics

Nawaf Bou-Rabee

arXiv:2608.25279v1math.PRmath.NAstat.COstat.ML

TL;DR

The paper asks whether fixed-parameter kinetic Langevin splittings can achieve ballistic sampling acceleration. It transfers a heavy-ball non-acceleration dichotomy to sampling and proves that OBABO has optimal cold-start total variation dependence linear in κ up to logarithmic factors, with corresponding lower bounds for the other standard Strang splittings.

  • Problem

    Whether gradient-based sampling admits a provable Nesterov-like acceleration remains unresolved because mixing-time lower bounds had been lacking.

  • Method

    The paper eliminates velocity to obtain noisy heavy-ball recursions and transfers an optimization non-acceleration dichotomy into Gaussian slow modes or attracting-cycle metastability.

  • Results

    Fixed-parameter OBABO cannot achieve ballistic cold-start mixing uniformly: lower bounds exclude rates faster than order κ^-1, while a matching order-κ upper bound holds up to logarithmic factors.

  • Takeaways & Limitations

    Among fixed-parameter OBABO tunings, the optimal cold-start total variation condition-number dependence over the smooth strongly convex class is linear up to logarithmic factors.

  • Takeaways & Limitations

    The conclusions concern fixed-parameter cold-start bounds; possible alternatives include warm starts, adaptive or target-dependent tuning, randomized integrators, and modified dynamics.

Abstract

from arXiv · show

The OBABO and BAOAB schemes and the other standard Strang splittings of kinetic (underdamped) Langevin dynamics are widely used Markov chain Monte Carlo algorithms. Under a suitable friction scaling, the underlying diffusion relaxes on a ballistic time scale, suggesting that these discretizations, suitably tuned, sample targets with condition number $κ$ in $O(\sqrtκ)$ iterations. We prove that no fixed choice of step size and friction, based only on the curvature bounds and the dimension, achieves this acceleration: total variation mixing time lower bounds for OBABO show that ballistic cold-start mixing fails uniformly over the smooth strongly convex class, and the lower bounds extend, with the same orders, to BAOAB and the other four Strang splittings. The proof transfers non-acceleration from optimization to sampling. Eliminating velocity gives an exact noisy heavy-ball recursion, and by the non-acceleration theorem of Goujaud, Taylor and Dieuleveut, for every tuning either some Gaussian target has a mode with relaxation time at least of order $κ$, or an attracting cycle exists on a smooth potential; dilating such a potential as $U_R(x)=R^2U(x/R)$ preserves its curvature bounds and produces metastability for a number of steps exponential in $R^2$, from an initial state at Wasserstein distance $O(R)$ from equilibrium. Using contraction estimates of Leimkuhler, Paulin and Whalley and a Wasserstein-to-total-variation regularization estimate, we prove a complementary upper bound of $O(κ)$ steps, up to logarithmic factors, for a fixed-parameter OBABO tuning. Hence, among fixed-parameter OBABO tunings, the optimal condition-number dependence of cold-start total variation mixing over this class is linear, up to logarithmic factors. A direct Gaussian calculation also rules out fixed-parameter acceleration for the left-endpoint exponential integrator.

1. Introduction.

The paper proves that fixed-parameter standard Strang splittings cannot achieve ballistic cold-start mixing uniformly over smooth strongly convex targets. For OBABO, linear condition-number dependence is optimal up to logarithmic factors, while the lower-bound mechanism extends to all six splittings.

  • Main results: Gaussian targets can have relaxation time of order κ, ruling out the ballistic order-√κ scale for fixed-parameter OBABO bounds.The paper contrasts this with the optimally tuned Gaussian contraction factor, whose relaxation scale is order √κ.
  • Main results: Theorem 5.1 provides a complementary OBABO cold-start total variation upper bound of order κ, up to logarithmic factors.Its proof combines Wasserstein contraction with Wasserstein-to-total-variation regularization.
  • Main results: Dilating a cycling potential preserves curvature bounds and produces exponentially long metastability in R^2, with initial Wasserstein distance O(R).This supplies the nonquadratic branch of the mixing-time lower bound.
  • Extension to standard Strang splittings: The lower bounds transfer from OBABO to BAOAB, ABOBA, OABAO, AOBOA, and BOAOB through noisy heavy-ball recursions obtained by eliminating velocity.Noise is independent for some splittings and only adjacent-step correlated for others, which does not affect the Gaussian-tail argument.
  • Explicit one-dimensional instance: An explicit one-dimensional smooth strongly convex potential with curvature bounds 1 ≤ U′′ ≤ 25 exhibits an attracting three-cycle and exponentially long cold-start metastability.The example uses the OBABO tuning optimal over quadratic potentials with curvatures in [1].
  • Main results: Theorem 1.1 gives a quadratic-versus-cycling dichotomy for every numerically stable fixed-parameter OBABO tuning.The quadratic case yields a Gaussian obstruction; the cycling case yields metastability on a smooth strongly convex potential.

2. OBABO position as an exact noisy heavy-ball method.

The OBABO position process admits an exact two-step noisy heavy-ball representation, with initialization encoding the initial velocity. For quadratic targets, stability is characterized explicitly and determines the admissible step-size range.

  • Initialization: The auxiliary position X−1 encodes the initial velocity and is not an earlier position visited by the chain.The initialization relation can instead be read as defining V0 from (X−1,X0).
  • Exact representation: OBABO positions satisfy an exact noisy heavy-ball recursion with step size s = h^2 and momentum β.The recursion includes centered Gaussian noise terms ζ_k.
  • Noise structure: Distinct noise terms are independent centered Gaussians because they depend on disjoint noise pairs.A convention with an independent initial Gaussian equalizes the noise distribution from the first update onward, whereas deterministic cold starts use a smaller first covariance.
  • Quadratic case: For quadratic potentials, the deterministic position recursion is Polyak’s heavy-ball method, and its two-step matrix has momentum parameter β.The corresponding phase-space and position matrices share their characteristic polynomial.
  • Stability: All quadratic modes are Schur stable exactly when 0 < s < 2(1 + β)/κ.For OBABO, this is equivalent to 0 < h < 2/√κ; if h ≥ 2/√κ, the quadratic target Uκ has no invariant probability law.

3. The deterministic heavy-ball dichotomy.

The deterministic analysis transfers a heavy-ball non-acceleration dichotomy to smooth strongly convex potentials. Either quadratic convergence is nonaccelerated, or a smooth attracting cycle can be constructed, with strict inequalities providing neighborhoods needed for the sampling lower bounds.

  • Deterministic reduction: The analysis removes noise from the position recursion and studies deterministic heavy-ball dynamics with fixed parameters satisfying numerical stability.The construction prescribes a periodic point sequence and then builds a potential realizing that sequence.
  • Cycling construction: A heavy-ball cycle can follow the vertices of a regular m-gon on a 1-strongly convex potential with κ-Lipschitz gradient when an explicit quadratic in s is nonpositive.The roots-of-unity construction uses cyclic rotations of the polygon vertices.
  • Potential construction: The potential is built from the convex hull of the cycle points using a metric-projection formula, which determines the required gradient values.The projection inequalities reduce to a single cycling quadratic because of rotational symmetry.
  • Attraction geometry: Strict negativity of the cycling quadratic makes all projection inequalities strict and creates a positive-radius neighborhood around every cycle vertex.Within each neighborhood, the metric projection is constant and the potential is quadratic with Hessian I_d.
  • Smooth realization: The resulting smooth construction has an exponentially stable linearization along the cycle and can be mollified without changing the dynamics near its vertices.The mollified potential belongs to the paper’s smooth strongly convex class.

4. Proofs of the mixing time lower bounds.

The lower-bound proof analyzes Gaussian autoregressions and metastable noisy heavy-ball cycles. These mechanisms yield either nonaccelerated Gaussian relaxation or exponentially long total-variation separation after dilation.

  • 4.1. The quadratic case.: Lemma 4.1 identifies the spectral radius as the asymptotic total variation decay rate for stable Gaussian autoregressive processes.The rate is an upper bound from every initial state and is attained for suitable initial states.
  • 4.1. The quadratic case.: In the quadratic case, a curvature attaining the worst heavy-ball contraction factor produces a Gaussian target with nonaccelerated total variation relaxation.The corresponding initial states realize the maximal asymptotic contraction factor.
  • 4.2. Metastability of noisy heavy-ball recursions.: The cycling case confines noisy iterates near consecutive points of a dilated attracting cycle, with failure probability at most 2ne^(-c0R^2) for OBABO.Disjoint neighborhoods convert confinement into total variation separation.
  • 4.3. From an attracting cycle to OBABO metastability.: Theorem 4.5 converts cycle separation into a unique invariant law and a cold-start total variation lower bound of at least 3/8 through the metastable time window.The same lower bound persists at all earlier times because total variation distance to an invariant law is nonincreasing.

5. Proof of the mixing time upper bound and sharpness of the diffusive scale.

The paper proves an O(κ)-scale cold-start total-variation upper bound for a fixed-parameter OBABO tuning, matching the lower-bound order up to logarithmic factors. The extension of this upper-bound argument to other splittings is limited by available regularization estimates.

  • 5.1. Diffusive upper bound.: The upper bound combines Wasserstein contraction with a 24-step Wasserstein-to-total-variation regularization estimate.The regularization estimate is dimension-independent and permits a free number of regularization steps.
  • 5.1. Diffusive upper bound.: Theorem 5.1 provides a numerically stable fixed-parameter OBABO tuning with total variation convergence bounded by Cκe^(-cn/κ).The constants are C = 143 and c = 1/[128(1 − e^(-1))].
  • 5.2. Sharpness of the diffusive scale.: Solving the convergence bound gives a cold-start mixing time of order κ times logarithmic factors involving κ, the initial Wasserstein distance, and ε.The initial-state dependence is retained explicitly because deterministic starts can be arbitrarily far from equilibrium.
  • 5.2. Sharpness of the diffusive scale.: The lower-bound dichotomy rules out any uniform cold-start exponential convergence rate of larger order than κ^(-1) for fixed-parameter OBABO over the full smooth strongly convex class.The contradiction uses either a Gaussian case or a dilated cycling family.
  • 5.2. Sharpness of the diffusive scale.: For other Strang splittings, contraction estimates extend, but analogous upper bounds are not stated because corresponding regularization estimates are not pursued.Theorem 5.1 is therefore formulated for OBABO only.

6. Extension to standard Strang splittings.

Eliminating velocity from all six standard Strang splittings yields noisy heavy-ball recursions. The quadratic-versus-cycling dichotomy and corresponding cold-start lower bounds therefore extend beyond OBABO, with noise-dependence and stability conditions adjusted by splitting.

  • 6. Extension to standard Strang splittings.: The six standard Strang splittings reduce to noisy heavy-ball recursions with momentum β and splitting-dependent heavy-ball step sizes.Noise is independent for some splittings and 1-dependent for others.
  • 6.1. BAOAB.: BAOAB has the same deterministic heavy-ball recursion as OBABO, but its eliminated Gaussian noise is 1-dependent rather than independent.The position-pair process is consequently non-Markov, requiring phase-space invariant-law arguments.
  • 6.1. BAOAB.: Theorem 6.3 and Corollary 6.4 extend the non-acceleration dichotomy and no-fixed-parameter-acceleration result to BAOAB.The resulting convergence-rate obstruction remains of order κ^(-1) under the stated polynomial-prefactor condition.
  • 6.2. The remaining Strang splittings.: Theorem 6.6 extends the dichotomy to ABOBA, OABAO, AOBOA, and BOAOB under their corresponding heavy-ball stability condition.For OABAO, only the metastable time window changes by a fixed constant.
  • 6.2. The remaining Strang splittings.: The remaining splittings transfer cycle-induced total variation separation through transformed recursion variables or measurable phase-space maps.At the endpoint of the applicable window, the two starts are separated by at least 3/4, implying one is at least 3/8 from stationarity.
  • 6.2. The remaining Strang splittings.: Corollary 6.7 rules out fixed-parameter acceleration for each of the four remaining standard Strang splittings.The numerical stability condition is expressed as 0 < s† < 2(1 + β)/L.

7. Consequences, scope and open problems.

The paper proves that fixed-parameter standard splittings cannot achieve uniform cold-start ballistic mixing over the smooth strongly convex class, while identifying boundaries where acceleration remains unresolved.

  • Lower bounds: No fixed step size and friction based only on curvature bounds and dimension yields uniform OBABO cold-start mixing of order √κ.Some targets instead have mixing time not of any order o(κ).
  • Scope: The lower bounds concern fixed-parameter discretizations, whereas the exact diffusion and optimally tuned Gaussian OBABO chain retain relaxation scales of order √κ.Finite-step metastable cycles have no counterpart in the continuous diffusion.
  • Open problems: The informal conjecture is not yet formalized for all admissible discretizations, since weak consistency alone constrains only the small-step limit.The result leaves warm-start acceleration, target-dependent parameters, time-dependent splittings, and modified dynamics beyond Gaussian acceleration open.
  • Extensions: The six standard Strang splittings satisfy the corresponding uniform cold-start exponential lower bounds, and the left-endpoint exponential integrator is ruled out by a Gaussian rate lower bound.For the latter method, the obstruction is Gaussian rather than an attracting deterministic cycle.
  • Open problems: Randomized midpoint achieves condition-number dependence κ5/6 under a controlled χ2-divergence initialization, but not the ballistic scale or point-mass cold-start setting studied here.Whether internal randomization permits uniform ballistic mixing from arbitrary point masses remains open for randomized Runge-Kutta-Nyström schemes.
  • Open problems: Metropolized OBABO remains unresolved because acceptance decisions and rejection momentum flips can alter or break the attracting cycles underlying the lower bounds.The unadjusted and Metropolized chains also target different invariant laws, so a generic claim that adjustment only slows mixing is invalid.

APPENDIX A: GAUSSIAN NON-ACCELERATION OF THE LEFT-ENDPOINT EXPONENTIAL INTEGRATOR

Appendix A analyzes the left-endpoint exponential integrator on quadratic targets through its linear Gaussian recursion. It shows that instability eliminates invariant laws, while stability still permits a low-curvature mode with non-accelerated relaxation.

  • Method: The left-endpoint exponential integrator freezes the force during each step and exactly solves the resulting linear stochastic differential equation.Eliminating velocity produces a two-step recurrence involving gradients at two successive positions.
  • Stability analysis: For a quadratic potential, the deterministic update is represented by a matrix Mλ, with stability determined by its characteristic polynomial and Jury conditions.Stability at the largest curvature implies stability across all curvatures in [1,κ].
  • Non-acceleration result: If Mκ is not Schur stable, the integrator has no invariant probability law for the corresponding Gaussian target.The characteristic-function argument uses positive-definite noise covariance to rule out an invariant law.
  • Conclusion: Thus the left-endpoint exponential integrator admits no uniform cold-start ballistic mixing bound over the smooth strongly convex class.Its non-acceleration mechanism is purely Gaussian rather than metastability from an attracting cycle.
  • Non-acceleration result: If Mκ is Schur stable, the low-curvature matrix satisfies ρ(M1) ≥ 1 − 32/κ for κ ≥ 64.The chain for U1 nevertheless has a unique invariant law and Gaussian autoregressive representation.

APPENDIX B: SHARP COLD-START TOTAL VARIATION RATES FOR THE KINETIC LANGEVIN DIFFUSION ON GAUSSIAN TARGETS

Appendix B determines sharp worst-case cold-start total variation rates for the kinetic Langevin diffusion on Gaussian targets. The optimal worst-case exponent is achieved at critical friction and is limited by the smallest curvature.

  • Rate characterization: For every friction γ, a deterministic initial state has asymptotic total variation decay exponent −α(γ,H), where α is the drift matrix’s spectral abscissa.The Gaussian invariant law is unique for the continuous diffusion.
  • Worst-case rate: The smallest curvature K bounds every friction’s worst-case exponent by √K, so no friction yields a larger uniform deterministic-start exponent.The bound follows from the roots of µ^2 + γµ + λ = 0 evaluated at λ = K.
  • Optimality: At critical friction, the exponent √K is attained from every deterministic initial state, with equality for a suitable initial state.This establishes √K as the optimal worst-case asymptotic total variation exponent.
  • Scope: These Gaussian diffusion rates do not directly settle cold-start total variation rates for nonquadratic strongly convex potentials.Existing entropy bounds do not directly apply to Dirac initial conditions because their relative entropy is infinite.
  • Finite-time consequence: The appendix provides finite-time lower bounds for mixing from a deterministic state, with the mixing-time definition extended from integer to continuous times.Monotonicity of total variation under the Markov kernel transfers the integer-time result to all t ≥ 0.
Loading 2608.25279v1…