Persistence Pays: Square-root condition-number dependence for Metropolis-adjusted kinetic Langevin Monte Carlo with a non-reversibly updated accept/reject uniform
Abstract
We prove accelerated mixing for a Metropolis-adjusted kinetic Langevin sampler: the OBABO splitting with friction 2√m, adjusted with Neal's non-reversibly updated uniform, which is redrawn after every epoch of E steps. For targets e−U on ℝd with mI⪯∇2U⪯ LI and an LH-Lipschitz Hessian, started from a Gaussian at an approximate minimizer, the chain reaches total variation accuracy ε after Õ(√(κd)+√(LH)(d/m)3/4) gradient evaluations, where κ=L/m and Õ hides logarithmic factors. The √κ 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 √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.
Related
- Nii-MALA: A Fast Metropolis-Adjusted Langevin Sampler with Radial Velocity Benchmarks
- A spectral gap for Metropolis-adjusted Langevin algorithm with a uniformly randomized step size
- Scaled Null-Adjusted Persistence: A Multiscale Bridge between Modularity and Persistence
- Tight Stochastic Condition-Number Dependence in Nonconvex-Strongly-Concave Minimax Optimization
- Convergence of Independence Metropolis-Hastings Algorithms in High Dimensions: Iteration Lengths, Cutoff Profiles, and Diagnostic Unreliability
BibTeX
@misc{bourabee2026persistence,
title = {{Persistence Pays: Square-root condition-number dependence for Metropolis-adjusted kinetic Langevin Monte Carlo with a non-reversibly updated accept/reject uniform}},
author = {Nawaf Bou-Rabee},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.35781},
eprint = {2610.35781},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.35781},
}
RIS
TY - UNPB
TI - Persistence Pays: Square-root condition-number dependence for Metropolis-adjusted kinetic Langevin Monte Carlo with a non-reversibly updated accept/reject uniform
AU - Nawaf Bou-Rabee
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.35781
UR - https://arxiv.org/abs/2610.35781
AB - We prove accelerated mixing for a Metropolis-adjusted kinetic Langevin sampler: the OBABO splitting with friction 2√m, adjusted with Neal's non-reversibly updated uniform, which is redrawn after every epoch of E steps. For targets e^−U on ℝ^d with mI⪯∇^2U⪯ LI and an L_H-Lipschitz Hessian, started from a Gaussian at an approximate minimizer, the chain reaches total variation accuracy ε after Õ(√(κd)+√(L_H)(d/m)^3/4) gradient evaluations, where κ=L/m and Õ hides logarithmic factors. The √κ 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 √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.
ER -