# Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time

arXiv: https://arxiv.org/abs/2207.02189 · HTML: https://mlsanity.com/paper/2207.02189/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 50 references that are in the map.
- First posted on arXiv 5 Jul 2022.

## Builds on (most cited first, 26 of 26)

- [Stochastic Gradient Hamiltonian Monte Carlo](https://mlsanity.com/paper/1402.4102/) (2014)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [A Conceptual Introduction to Hamiltonian Monte Carlo](https://mlsanity.com/paper/1701.02434/) (2017)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [Structured Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2010.03106/) (2020)
- [On sampling from a log-concave density using kinetic Langevin diffusions](https://mlsanity.com/paper/1807.09382/) (2018)
- [Generalizing Hamiltonian Monte Carlo with Neural Networks](https://mlsanity.com/paper/1711.09268/) (2017)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [Acceleration Methods](https://mlsanity.com/paper/2101.09545/) (2021)
- [Exponential ergodicity of mirror-Langevin diffusions](https://mlsanity.com/paper/2005.09669/) (2020)
- [Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions](https://mlsanity.com/paper/1905.02313/) (2019)
- [Sqrt(d) Dimension Dependence of Langevin Monte Carlo](https://mlsanity.com/paper/2109.03839/) (2021)
- [Is There an Analog of Nesterov Acceleration for MCMC?](https://mlsanity.com/paper/1902.00996/) (2019)
- [A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network](https://mlsanity.com/paper/2010.01618/) (2020)
- [Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions](https://mlsanity.com/paper/2106.05480/) (2021)
- [Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo](https://mlsanity.com/paper/2105.00887/) (2021)
- [Acceleration via Fractal Learning Rate Schedules](https://mlsanity.com/paper/2103.01338/) (2021)
- [Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo](https://mlsanity.com/paper/1802.08898/) (2018)
- [Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-Lojasiewicz Functions when the Non-Convexity is Averaged-Out](https://mlsanity.com/paper/2206.11872/) (2022)
- [Hamiltonian Dynamics with Non-Newtonian Momentum for Rapid Sampling](https://mlsanity.com/paper/2111.02434/) (2021)
- [Escaping Saddle Points Faster with Stochastic Momentum](https://mlsanity.com/paper/2106.02985/) (2021)
- [An Introduction to Hamiltonian Monte Carlo Method for Sampling](https://mlsanity.com/paper/2108.12107/) (2021)
- [Entropy-based adaptive Hamiltonian Monte Carlo](https://mlsanity.com/paper/2110.14625/) (2021)
- [Magnetic Hamiltonian Monte Carlo](https://mlsanity.com/paper/1607.02738/) (2016)

## Built on by (most cited first, 7 of 7)

- [Improved Discretization Analysis for Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2302.08049/) (2023)
- [Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps](https://mlsanity.com/paper/2209.12771/) (2022)
- [Constrained Exploration via Reflected Replica Exchange Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2405.07839/) (2024)
- [Mean-Square Analysis of Discretized Ito Diffusions for Heavy-tailed Sampling](https://mlsanity.com/paper/2303.00570/) (2023)
- [On the Dissipation of Ideal Hamiltonian Monte Carlo Sampler](https://mlsanity.com/paper/2209.07438/) (2022)
- [Hamiltonian Monte Carlo Inference of Marginalized Linear Mixed-Effects Models](https://mlsanity.com/paper/2410.24079/) (2024)
- [Accelerating Hamiltonian Monte Carlo for Bayesian Inference in Neural Networks and Neural Operators](https://mlsanity.com/paper/2507.14652/) (2025)

## Abstract (arXiv)

Hamiltonian Monte Carlo (HMC) is a popular method in sampling. While there are quite a few works of studying this method on various aspects, an interesting question is how to choose its integration time to achieve acceleration. In this work, we consider accelerating the process of sampling from a distribution π(x) propto exp(-f(x)) via HMC via time-varying integration time. When the potential f is L-smooth and m-strongly convex, i.e. for sampling from a log-smooth and strongly log-concave target distribution π, it is known that under a constant integration time, the number of iterations that ideal HMC takes to get an ε Wasserstein-2 distance to the target π is O( kappa log frac1ε ), where kappa := fracLm is the condition number. We propose a scheme of time-varying integration time based on the roots of Chebyshev polynomials. We show that in the case of quadratic potential f, i.e., when the target π is a Gaussian distribution, ideal HMC with this choice of integration time only takes O( √kappa log frac1ε ) number of iterations to reach Wasserstein-2 distance less than ε; this improvement on the dependence on condition number is akin to acceleration in optimization. The design and analysis of HMC with the proposed integration time is built on the tools of Chebyshev polynomials. Experiments find the advantage of adopting our scheme of time-varying integration time even for sampling from distributions with smooth strongly convex potentials that are not quadratic.