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

• URL: http://arxiv.org/abs/2608.25279v1
• Date: Wed, 26 Aug 2026 01:27:39 GMT
• Title: Provable Non-Acceleration of Standard Strang Splittings of Kinetic Langevin Dynamics
• Abstract summary: OBABO and BAOAB schemes and the other standard Strang splittings of kinetic (underdamped) Langevin dynamics are widely used Markov chain Monte Carlo algorithms.<n>We prove that no fixed choice of step size and friction, based only on the curvature bounds and the dimension, achieves this acceleration.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Steady-State Convergence of Stochastic Approximation [19.40811084751516]
  We develop a unified SSC theory for constant-stepsize contractive SA driven by Markovian, multiplicative noise.<n>A key methodological contribution is a multi-step framework that progressively reduces the original recursion to tractable auxiliary dynamics.<n>We show that the leading-order bias can be universality of order $sqrt$, in contrast to the $$-order bias in the smooth regime.
  arXiv  Detail & Related papers  (2026-09-14T02:15:03Z)
• Strong Averaging Principle and Long-Time Dynamics for Fast-Slow SDEs with Increasing Time-Scale Separation and Degenerate Noise [1.0026496861838448]
  We establish a strong averaging principle for fast-slow differential equations with a time-dependent scale-separation parameter.<n>In contrast to approaches based on noise-induced smoothing or regularity, our approach relies on dissipativity of the frozen fast dynamics.
  arXiv  Detail & Related papers  (2026-08-24T16:30:59Z)
• Exploiting the path-integral radius of gyration in open quantum dynamics [0.0]
  A major challenge in open quantum dynamics is the inclusion of Matsubara-decay terms in the memory kernel.<n>We show that the well-known Ishizaki--Tanimura correction is equivalent to separating smooth from Brownian' contributions.<n>We also develop a simple A4' adaptation of the AAA' algorithm in order to fit $mathcal R2()$ to a sum over poles.
  arXiv  Detail & Related papers  (2026-02-16T11:10:24Z)
• RanSOM: Second-Order Momentum with Randomized Scaling for Constrained and Unconstrained Optimization [1.3537117504260623]
  Momentum methods, such as Polyak's Heavy Ball, are the standard for training deep networks but suffer from curvature-induced bias in settings.<n>We propose textbfRanSOM, a unified framework that eliminates this bias by replacing deterministic step sizes with randomized steps drawn from distributions with mean $_t$.<n>We instantiate this framework in two algorithms: textbfRanSOM-E for unconstrained optimization and textbfRanSOM-B for constrained optimization.
  arXiv  Detail & Related papers  (2026-02-06T16:09:36Z)
• Robust Sublinear Convergence Rates for Iterative Bregman Projections [21.689846521201588]
  We use entropic regularization to approximate linear programs whose constraints split into two (or more) tractable blocks.<n>We derive the flow-Sinkhorn algorithm for the Wasserstein-1 distance on graphs.
  arXiv  Detail & Related papers  (2026-02-01T18:20:19Z)
• Stabilizing Fixed-Point Iteration for Markov Chain Poisson Equations [49.702772230127465]
  We study finite-state Markov chains with $n$ states and transition matrix $P$.<n>We show that all non-decaying modes are captured by a real peripheral invariant subspace $mathcalK(P)$, and that the induced operator on the quotient space $mathbbRn/mathcalK(P) is strictly contractive, yielding a unique quotient solution.
  arXiv  Detail & Related papers  (2026-01-31T02:57:01Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  We consider clipped optimization problems with heavy-tailed noise with structured density. We show that it is possible to get faster rates of convergence than $mathcalO(K-(alpha - 1)/alpha)$, when the gradients have finite moments of order. We prove that the resulting estimates have negligible bias and controllable variance.
  arXiv  Detail & Related papers  (2023-11-07T17:39:17Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  We consider a smooth and strongly convex objective function using a Newton method. We show that there exists a universal weighted averaging scheme that transitions to local convergence at an optimal stage.
  arXiv  Detail & Related papers  (2022-04-20T07:14:21Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  This work provides a general framework for the non-asymotic analysis of sampling error in 2-Wasserstein distance. Our theoretical analysis is further validated by numerical experiments.
  arXiv  Detail & Related papers  (2021-09-08T18:00:05Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence [8.873449722727026]
  We show that the rate estimate $widetildemathcalO(depsilon-1)$ improves the previously known rates in both of these metrics. In particular, for convex and firstorder smooth potentials, we show that LMC algorithm achieves the rate estimate $widetildemathcalO(depsilon-1)$ which improves the previously known rates in both of these metrics.
  arXiv  Detail & Related papers  (2020-07-22T18:18:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.