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 standard Strang splittings of kinetic Langevin dynamics can achieve provable square-root acceleration with fixed parameters. By transferring non-acceleration results from optimization through an exact noisy heavy-ball representation, it shows that fixed-parameter cold-start mixing cannot uniformly attain ballistic rates, while OBABO has optimal linear condition-number dependence up to logarithmic factors.

  • Problem

    Whether gradient-based sampling admits a provable analogue of Nesterov acceleration remains open because mixing-time lower bounds characterizing acceleration have been lacking.

    Source: §1.1 · p. 2

  • Method

    The paper derives an exact noisy heavy-ball representation and applies a heavy-ball cycling dichotomy to construct Gaussian slow modes or metastable dilated potentials.

    Source: §2 · p. 9, §3 · p. 12

  • Results

    Fixed-parameter tunings for all six standard Strang splittings either mix no faster than order κ^-1 on a Gaussian target or exhibit exponentially long metastability.

    Source: §1.4 · p. 7

  • Takeaways & Limitations

    Within fixed-parameter OBABO tunings, cold-start total-variation mixing has linear condition-number dependence up to logarithmic factors.

    Source: §1.4 · p. 7

    The results do not determine whether Metropolis adjustment can accelerate mixing, because acceptance and momentum flips may alter or disrupt the attracting cycles used in the lower bounds.

    Source: §7 · p. 50

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.

This paper asks whether fixed-parameter kinetic Langevin discretizations can achieve uniform cold-start mixing at the ballistic O(√κ) rate using only curvature information. It establishes non-acceleration for OBABO and the other standard Strang splittings, while analyzing unadjusted chains relative to their invariant laws and providing complementary lower- and upper-bound results.

1.1. Motivation.

  • Continuous-time kinetic Langevin suggests square-root acceleration, but OBABO’s full-class guarantee is order κ per step, unlike its order-√κ Gaussian relaxation scale.The question is whether tuning from only (K,L,d) can uniformly achieve order-√κ total variation mixing from every deterministic initial state.Source: §1.1 · p. 2

1.2. Contributions.

  • For every numerically stable fixed-parameter OBABO tuning, either a Gaussian target is nonaccelerated or a smooth strongly convex target exhibits exponentially long metastability.The dichotomy transfers the heavy-ball result of Goujaud, Taylor and Dieuleveut because eliminating velocity yields an exact noisy heavy-ball recursion.Source: §1.2 · p. 3, §1.4 · p. 6

1.4. Main results.

  • Order κ, up to logarithmic factors, is optimal among fixed-parameter OBABO cold-start bounds, ruling out every polynomial convergence rate larger than κ^-1, including κ^-1/2.The upper bound follows from contraction and regularization estimates, while the lower bound applies over the full smooth strongly convex class.Source: §1.1 · p. 2, §1.2 · p. 3, §1.4 · p. 7

1.2. Contributions.

  • Dilation preserves curvature bounds while reducing normalized noise by R^-1, producing mixing-time lower bounds exponential in R^2 from initial states at Wasserstein distance O(R).The cycling argument requires an attracting cycle, obtained by proving strict inclusion inside a roots-of-unity cycling region.Source: §1.2 · p. 3, §1.4 · p. 6

1.4. Main results.

  • The same lower-bound dichotomy extends to BAOAB and the other four standard Strang splittings; an explicit one-dimensional C∞ example already cycles at condition number 25.The six schemes reduce to noisy heavy-ball recursions, and the explicit OBABO construction has total variation distance at least 3/8 for exponentially many steps after dilation.Source: §1.2 · p. 3, §1.4 · pp. 7–8

1.3. Setting and notation.

  • The analysis concerns C∞ potentials with Hessian eigenvalues in [1,κ], deterministic cold starts, and fixed parameters depending only on curvature bounds and dimension.The chain’s invariant law generally differs from the continuous diffusion’s invariant measure, and uniform cold-start bounds must retain initial-state dependence.Source: §1.3 · pp. 4–5

1.5. Related work.

  • Existing discretization results provide Wasserstein contraction or sublinear guarantees, but none establishes √κ mixing for a kinetic Langevin discretization; Appendix A also rules it out for the left-endpoint exponential integrator.Related results include κ5/6 dependence for randomized midpoint under a χ2-warm-start assumption [1], Gaussian ballistic rates for generalized Hamiltonian Monte Carlo with partial velocity refreshment, and couplings for OBABO and exponential integrators [15] [28] [30].Source: §1.5 · pp. 8–9
  • Fixed curvature bounds do not yield a cold-start total-variation mixing bound of order √κ for any fixed OBABO step size and friction over the full target class.The result concerns the idealized setting where global curvature bounds are known exactly, and holds up to logarithmic factors.Source: §1.5 · p. 9
  • The analysis concerns unadjusted OBABO and other standard Strang splittings, with lower bounds measured against each chain’s own invariant law rather than the target distribution.Consequently, asymptotic-bias estimates are unnecessary, while Metropolis adjustment removes the bias entirely [11] [9].Source: §1.5 · p. 9

1.6. Organization of the paper.

  • The paper proceeds from a noisy heavy-ball reformulation through non-acceleration and mixing lower bounds, then proves an order-κ cold-start upper bound and extends the results to other Strang splittings.It also discusses scope and open problems, proves Gaussian non-acceleration for the left-endpoint exponential integrator, and characterizes worst-case asymptotic total-variation rates for kinetic Langevin diffusion on Gaussian targets.Source: §1.6 · p. 9

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

This section shows that OBABO positions obey an exact noisy heavy-ball recursion, linking the scheme to Polyak momentum and enabling a precise stability characterization for quadratic potentials.

Noisy heavy-ball representation

  • OBABO positions satisfy a two-step noisy heavy-ball recursion with step size s = h^2(1 + β)/2 and independent centered Gaussian noise.Eliminating velocity introduces an auxiliary X_{−1} encoding the initial velocity; Gaussian initialization makes the noise identically distributed from the first update onward.Source: §2 · pp. 9–10

Quadratic analysis

  • Suppressing noise yields Polyak’s heavy-ball method, while quadratic potentials produce position and phase-space matrices with a common characteristic polynomial.The matrices act respectively on (X_k, X_{k−1}) and (X_k, V_k), providing the deterministic representation used for stability analysis.Source: §2 · p. 11

Numerical stability

  • All quadratic modes with curvatures in [1,κ] are Schur stable exactly when 0 < s < 2(1 + β)/κ.For OBABO, this condition is equivalent to 0 < h < 2/√κ.Source: §2 · p. 11
  • When h ≥ 2/√κ, the OBABO chain for U_κ(x) = κ|x|^2/2 has no invariant probability law.The instability follows from a mode with eigenvalue at most −1, whose noisy autoregression cannot possess a stationary distribution.Source: §2 · p. 11

3. The deterministic heavy-ball dichotomy.

This section develops a deterministic heavy-ball dichotomy by constructing and characterizing attracting cycles for admissible tunings on smooth strongly convex potentials. It also establishes local quadratic structure and applicability to the remaining Strang splittings, supporting subsequent metastability analysis.

Potential construction

  • The construction uses a piecewise-quadratic potential defined through projection onto the convex hull of the cycle points, with gradient ∇ψ(x) = x + (κ − 1)proj_C(x).The projection inequalities reduce to a single cycling quadratic because rotational symmetry makes the relevant inner products depend only on index differences.Source: §3 · pp. 13–14

Cycle characterization

  • For fixed numerically stable parameters (s,β), an m-periodic heavy-ball cycle exists on a 1-strongly convex potential with κ-Lipschitz gradient exactly when P_m(s,β;κ) ≤ 0.The cycle is prescribed as the vertices of a regular m-gon, and the potential is constructed so the recursion advances through them.Source: §3 · pp. 12, 14

Strict cycling regime

  • When P_m(s,β;κ) < 0, each cycle point has a positive-radius neighborhood where the projection is constant and ψ is quadratic with Hessian I_d2.The radius r_max is determined by the minimum distance to the relevant projection half-plane boundaries.Source: §3 · pp. 14, 16

Parameter regions

  • The cycling region is described by step-size intervals [s_−(β,m;κ), s_+(β,m;κ)], and consecutive periods have overlapping intervals with nonempty interior.This overlap supplies a period for which the cycling inequality is strict under the section’s stated parameter condition.Source: §3 · p. 16

Deterministic heavy-ball dichotomy

  • Lemma 3.3 guarantees an integer period m≥3 with P_m(s,β;κ)<0 for every tuning satisfying the stated hypotheses.The proof selects a period by combining numerical stability, step-size bounds, and level-set inequalities.Source: §3 · pp. 18–19

Smooth attracting cycle

  • The m-step Jacobian is M=A_1^m, and its spectral radius is controlled by the heavy-ball quadratic spectral radius, making the cycle linearly attracting.At each cycle point, the Hessian equals the identity, so numerical stability determines the local linearization.Source: §3 · pp. 19–21
  • Proposition 3.4 smooths the cycling potential while preserving 1-strong convexity, κ-Lipschitz gradients, the cycle, and identity Hessians near cycle points.The resulting potential satisfies ∇U(x)=x+w(x) with uniformly bounded w, while the cycle’s local linearization remains constant-coefficient.Source: §3 · pp. 20–21

Connection to metastability

  • These constructions meet the later metastability theorem’s assumptions, and because they depend only on (s,β), they apply unchanged to the other Strang splittings.The cycle equation, local Hessian identity, spectral-radius bound, and global gradient bound provide the required hypotheses.Source: §3 · p. 21

4. Proofs of the mixing time lower bounds.

This section develops lower-bound tools for OBABO, combining Gaussian autoregression analysis with metastability of noisy heavy-ball recursions near attracting cycles. It applies these tools to derive mixing lower bounds and illustrates the mechanism through an explicit smooth one-dimensional example with exponential-in-R^2 time scales.

4.1. The quadratic case.

  • For stable Gaussian autoregressions, total-variation decay has asymptotic exponential rate equal to the phase matrix’s spectral radius, with suitable initial states attaining the rate.The result also gives a unique centered-Gaussian invariant law and supports quadratic OBABO lower bounds through the worst-case spectral radius.Source: §4.1 · pp. 23–24
  • The quadratic lemma further shows that fixed left-endpoint exponential-integrator parameters are either unstable on some Gaussian target or have total-variation contraction factor at least 1 − 64/κ.For the kinetic Langevin diffusion, it also gives a decay exponent at most K at critical friction.Source: §4.1 · p. 24

4.2. Metastability of noisy heavy-ball recursions.

  • The metastability construction applies an abstract stable-cycle argument to noisy heavy-ball dynamics, providing the confinement and total-variation separation estimates used for OBABO and later Strang-splitting lower bounds.Stable deterministic attractors persist under small random perturbations; the paper’s contribution is making the resulting estimates explicit for mixing-time lower bounds [21, Chapter 6],,.Source: §4.2 · p. 25
  • Lemma 4.4 proves that a noisy heavy-ball recursion near a stable periodic orbit remains confined with failure probability at most A n e^(-bR^2), while distributions near consecutive cycle points stay separated in total variation.The argument uses the dilation U_R(x)=R^2U(x/R), geometrically decaying linearized products, and one-step noise tail bounds without requiring independent noise variables.Source: §4.2 · pp. 27–28

4.3. From an attracting cycle to OBABO metastability.

  • Attracting-cycle initializations yield unique invariant laws and a start remaining at least 3/8 from stationarity for all n ≤ N_R, with N_R exponential in R^2.The proof obtains a total-variation separation of at least 3/8 through time N_R, after first establishing invariant-law existence, uniqueness, and moment control.Source: §4.3 · pp. 29, 30, 32

4.4. Proofs of Theorem 1.1 and Corollary 1.2.

  • Theorem 1.1 combines a Gaussian relaxation case with a smooth roots-of-unity cycling case, proving the corresponding OBABO total-variation lower bounds.When the spectral relaxation factor is at least qκ, Gaussian targets give the lower bound; otherwise a smooth period-m cycle supplies the cycling construction.Source: §4.4 · p. 32

4.5. An explicit one-dimensional instance.

  • For the smooth potential U∈C∞(R) with 1≤U''≤25 at s=1/9 and β=4/9, the noise-free recursion has an exact period-three orbit with uniformly controlled additive perturbations.At N_R=floor(16^-1 e^(R^2/8000)), one of two starts is at least 3/8 from stationarity.Source: §4.5 · pp. 33, 34, 36

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

The section proves a cold-start total-variation upper bound with diffusive O(κ) dependence for a numerically stable fixed-parameter OBABO tuning. It also shows this scale is sharp among such tunings, while noting extension limits for other Strang splittings.

Diffusive upper bound

  • Theorem 5.1 gives a numerically stable fixed-parameter OBABO tuning whose cold-start bound decays as e^(-cn/κ), with explicit constants C = 143 and c = 1/[128(1 − e^-1)].The tuning yields an ε-mixing bound after n ≥ (κ/c) log(Cκ(1 + W2(δz,π))/ε) steps.Source: §5 · pp. 36–37

Proof mechanism

  • The proof combines Wasserstein contraction from Leimkuhler, Paulin and Whalley [30] with the dimension-free Wasserstein-to-total-variation regularization estimate of Bou-Rabee, Cox and Schieven [6].The regularization estimate applies to OBABO for every step size and number of steps, and the proof uses 24 regularization steps.Source: §5 · pp. 36–37

Sharpness

  • Corollary 1.3 establishes sharpness: no fixed-parameter tuning can achieve a cold-start mixing scale τ(κ) = o(κ) uniformly over the smooth strongly convex class.The contradiction uses either a slowly relaxing Gaussian mode or metastability from an attracting cycle after potential dilation.Source: §5 · p. 38

Other Strang splittings

  • The contraction stage also covers BAOAB and other Strang splittings, but analogous total-variation upper bounds require corresponding regularization estimates not pursued here.The stated theorem is therefore specific to OBABO.Source: §5 · p. 38

6. Extension to standard Strang splittings.

This section extends the lower-bound framework from OBABO to all six standard Strang splittings by reducing them to noisy heavy-ball recursions and adapting the confinement and pairwise-separation arguments. It shows that the splittings share the same non-acceleration lower-bound orders, including under the stated step-size condition for the remaining schemes.

6. Extension to standard Strang splittings.

  • All six standard Strang splittings reduce to noisy heavy-ball recursions, so the OBABO dichotomy and cold-start lower bounds extend beyond OBABO.The heavy-ball step size is h^2(1+β)/2 for OBABO, BAOAB, ABOBA, and OABAO, and √β h^2 for AOBOA and BOAOB; the resulting noises are independent or 1-dependent.Source: §6 · p. 38

6.1. BAOAB.

  • BAOAB has OBABO’s deterministic heavy-ball recursion with 1-dependent noise; no numerically stable fixed-parameter tuning achieves a uniform cold-start rate larger than κ^-1 over class (1.7).Source: §6.1 · pp. 41–42

6.2. The remaining Strang splittings.

  • The remaining four splittings also satisfy the non-acceleration dichotomy under their respective heavy-ball step sizes and stability condition 0 < s† < 2(1+β)/κ.Their quadratic phase matrices share characteristic polynomial data with trace 1+β−s†λ and determinant β, enabling the same spectral-radius and attracting-cycle arguments.Source: §6.2 · pp. 44–45
  • For BOAOB, ABOBA, and AOBOA, cycle initializations yield pairwise total-variation separation at least 1 − 4n e−c0R2, transferring from recursion variables to phase space.The transfers use a linear bijection for ABOBA and AOBOA and the position as a measurable state function for BOAOB.Source: §6.2 · p. 46
  • For OABAO, shifted force-evaluation variables obey the BAOAB noisy heavy-ball recursion, while shifted initial errors and recovery of positions require separate control.The resulting position events give pair separation with failure probability at most 8n e−c0R2 for n ≥ 1.Source: §6.2 · pp. 46–48
  • The relevant one- or two-step kernels have positive continuous densities, implying strong Feller properties, irreducibility, and uniqueness of the invariant law for all four splittings.For ABOBA and AOBOA, these properties are established in pair coordinates and uniqueness transfers from the squared kernel.Source: §6.2 · p. 48
  • At the applicable time-window endpoint, two evolved laws remain at total-variation distance at least 3/4, so one initial state stays at least 3/8 from stationarity throughout the window.The initial states have Wasserstein distance at most C0(1 + R) from the invariant law, while the invariant second moment is bounded by C(1 + R2).Source: §6.2 · p. 48
  • Corollary 6.7 extends the no-fixed-parameter-acceleration result to BOAOB, ABOBA, AOBOA, and OABAO under 0 < s† < 2(1 + β)/L.The proof replaces Theorem 1.1 with Theorem 6.6; normalization carries over, and OABAO’s smaller time window changes only a fixed constant.Source: §6.2 · p. 49

7. Consequences, scope and open problems.

Fixed-parameter standard Strang splittings have optimal cold-start total-variation mixing time linear in κ up to logarithmic factors, while left-endpoint exponential integrators also lack uniform ballistic guarantees. The section distinguishes discretization artifacts from diffusion behavior and identifies randomized, Metropolized, warm-start, and modified-dynamics acceleration as open directions.

Consequences

  • OBABO has cold-start mixing time Θ(κ) up to logarithmic factors among fixed-parameter tunings, and the same non-acceleration orders extend to all standard Strang splittings.Lower bounds exclude uniform o(κ) mixing, while a fixed-parameter OBABO tuning achieves the matching diffusive-scale upper bound up to logarithms.Source: §7 · p. 49

Scope

  • The lower bounds concern finite-step discretizations, not the exact diffusion or Gaussian-only guarantees, because accelerated Gaussian tuning can create non-Gaussian attracting-cycle metastability.On Gaussian targets, optimally tuned OBABO has relaxation scale √κ, whereas the exact process has continuous-time convergence guarantees; dilation transfers attracting cycles to metastable potentials.Source: §7 · p. 49
  • Every fixed-parameter left-endpoint exponential integrator is either Gaussian-unstable or fails a cold-start ballistic bound, through a Gaussian mechanism rather than a deterministic cycle.Its eliminated dynamics is a two-step recurrence, so Proposition A.1 supplies the direct Gaussian obstruction.Source: §7 · pp. 49–50

Open problems

  • The conjecture is that broad consistent explicit discretizations with O(1) gradient evaluations per step cannot achieve any uniform cold-start mixing time o(κ) under fixed-parameter tuning.The conjecture is formulated for normalized K = 1, L = κ, d = 2 and point-mass starts controlled through Wasserstein distance; weak consistency alone may be insufficient to characterize admissible tuned kernels.Source: §7 · p. 50
  • Randomized midpoint achieves κ5/6 mixing up to logarithmic factors from controlled χ2 starts, but ballistic acceleration from arbitrary point-mass starts remains unresolved for randomized integrators.Runge-Kutta-Nyström analyses address finite-time L2 accuracy and bias rather than κ-dependent mixing, and their internal randomness prevents direct transfer of the deterministic-cycle lower bound.Source: §7 · p. 50
  • Metropolized OBABO, warm starts, adaptive parameters, time-dependent splittings, and modified kinetic dynamics remain open routes because acceptance or extra gradient terms may alter the lower-bound mechanism.Metropolized OBABO preserves the target exactly but can either break attracting cycles or undo progress; gradient-adjusted dynamics reaches √κ on Gaussian targets, with non-Gaussian acceleration still open.Source: §7 · pp. 50–51

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

Appendix A proves Gaussian non-acceleration for the left-endpoint exponential integrator: instability at the largest curvature eliminates invariant laws, while stability still yields slow contraction for the smallest curvature.

Construction and proof

  • The integrator freezes the force at the initial position and exactly solves the resulting linear stochastic differential equation at each step [15] [28].The appendix derives the result by applying Lemma 4.1 to the resulting Gaussian autoregression.Source: Appendix A · pp. 51, 53

Gaussian non-acceleration

  • If M_κ is not Schur stable, the left-endpoint exponential integrator for U_κ has no invariant probability law.The proof uses a positive-definite one-step noise covariance and an invariant characteristic-function contradiction.Source: Appendix A · pp. 52–53
  • If M_κ is Schur stable, then every M_λ with λ ∈ [1,κ] is Schur stable, and the U_1 chain has a unique invariant law.Stability of lower curvatures follows from the Jury conditions and monotonicity in the curvature parameter.Source: Appendix A · pp. 52–53
  • For κ ≥ 64, the low-curvature matrix satisfies ρ(M_1) ≥ 1 − 32/κ, ruling out uniformly accelerated Gaussian relaxation.The bound follows by analyzing the characteristic equation in both the real-root and complex-conjugate-root cases.Source: Appendix A · p. 53

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

This appendix establishes the sharp worst-case cold-start total variation decay rate for kinetic Langevin diffusion on Gaussian targets with smallest curvature K. At critical friction, the optimal worst-case asymptotic exponent over deterministic initial states is √K, while no friction can guarantee a larger exponent.

Sharp rate

  • √K is the optimal worst-case asymptotic total variation decay exponent over deterministic initial states on Gaussian targets with smallest curvature K.For every friction, some deterministic initial state decays with exponent −α(γ,H), and −α(γ,H) ≤ √K; critical friction attains the matching upper exponent from every deterministic initial state.Source: Appendix B · p. 54

Alternative proof

  • The sharp exponent also follows from entropy decay and Pinsker’s inequality at critical friction, despite the arbitrarily small exponent loss in Arnold and Erb [2, Theorem 4.9(ii)].The diffusion started from a point is nondegenerate Gaussian at every positive time, so its relative entropy with respect to equilibrium is finite.Source: Appendix B · p. 54

Scope and limitations

  • For nonquadratic strongly convex potentials, sharp cold-start total variation rates remain open because Dirac initial conditions have infinite relative entropy.Lu [33] gives an entropy rate of order √K, while Guillin and Monmarché [24] and Eberle and Lörler address related entropy or relaxation-time notions rather than this deterministic-start total variation result.Source: Appendix B · p. 54

Proposition B.1

  • Proposition B.1 characterizes the rate through the spectral abscissa α(γ,H), with eigenvalues determined by µ^2 + γµ + λ = 0.The Gaussian equilibrium is the unique invariant law, and suitable initial states attain the asymptotic exponent e^{α(γ,H)} in the stated total variation bounds.Source: Appendix B · p. 54

Related papers

Loading 2608.25279v1…