Accelerated convergence in Hit-and-Run Monte Carlo and a coordinate-free randomized Kaczmarz algorithm
Open Access
- 1 January 2025
- journal article
- Published by Institute of Mathematical Statistics in Electronic Journal of Probability
- Vol. 30 (none) , 1-28
Abstract
Hit-and-Run is a coordinate-free Gibbs sampler, yet the quantitative advantages of its coordinate-free property remain largely unexplored beyond empirical studies. In this paper, we prove sharp estimates for the Wasserstein contraction of Hit-and-Run in Gaussian target measures via coupling methods and conclude mixing time bounds. Our results uncover accelerated convergence rates in certain settings. Furthermore, we extend these insights to a coordinate-free variant of the randomized Kaczmarz algorithm, an iterative method for linear systems, and demonstrate analogous convergence rates. These findings offer new insights into the advantages and limitations of coordinate-free methods for both sampling and optimization.Keywords
All Related Versions
This publication has 36 references indexed in Scilit:
- Non-reversible lifts of reversible diffusion processes and relaxation timesProbability Theory and Related Fields, 2024
- Comparison of hit-and-run, slice sampler and random walk MetropolisJournal of Applied Probability, 2018
- Duality on gradient estimates and Wasserstein controlsJournal of Functional Analysis, 2010
- Ricci curvature of Markov chains on metric spacesJournal of Functional Analysis, 2009
- A Randomized Kaczmarz Algorithm with Exponential ConvergenceJournal of Fourier Analysis and Applications, 2008
- Geometric Random Walks: A Survey2005
- One-shot coupling for certain stochastic recursive sequencesStochastic Processes and their Applications, 2002
- Hit-and-run mixes fastMathematical Programming, 1999
- Random walks and anO*(n5) volume algorithm for convex bodiesRandom Structures & Algorithms, 1997
- Time-Dependent Statistics of the Ising ModelJournal of Mathematical Physics, 1963