Complexity of zigzag sampling algorithm for strongly log-concave distributions

Abstract

We study the computational complexity of zigzag sampling algorithm for strongly log-concave distributions. The zigzag process has the advantage of not requiring time discretization for implementation, and that each proposed bouncing event requires only one evaluation of partial derivative of the potential, while its convergence rate is dimension independent. Using these properties, we prove that the zigzag sampling algorithm achieves $\epsilon$ error in chi-square divergence with a computational cost equivalent to $O({\kappa }^2{d}^{\frac{1}{2}}(\log \frac{1}{\epsilon }{)}^{\frac{3}{2}})$ gradient evaluations in the regime $\kappa \ll \frac{d}{\log d}$ under a warm start assumption, where $\kappa$ is the condition number and $d$ is the dimension.

arXiv commentWe added a new discussion that the warmness assumption of our main theorem can be achieved using LMC

References in corpus (24)

• Generalized event-chain Monte Carlo: Constructing rejection-free global-balance algorithms from infinitesimal steps
• The Zig-Zag Process and Super-Efficient Sampling for Bayesian Analysis of Big Data
• Rejection-free Monte-Carlo sampling for general potentials
• Irreversible Monte Carlo Algorithms for Efficient Sampling
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Randomized Hamiltonian Monte Carlo
• Piecewise-Deterministic Markov Chain Monte Carlo
• Ergodicity of the zigzag process
• Coupling and Convergence for Hamiltonian Monte Carlo
• A piecewise deterministic scaling limit of Lifted Metropolis-Hastings in the Curie-Weiss model
• High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm
• Is There an Analog of Nesterov Acceleration for MCMC?
• Limit theorems for the Zig-Zag process
• Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
• Exponential decay of Rényi divergence under Fokker-Planck equations
• On explicit $L^2$-convergence rate estimate for piecewise deterministic Markov processes in MCMC algorithms
• Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo
• Random Coordinate Langevin Monte Carlo
• Spectral analysis of the zigzag process
• Random Coordinate Underdamped Langevin Monte Carlo
• Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence