Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions

by Zongchen Chen and Santosh S. Vempala

Theory of Computing, Volume 18(9), pp. 1-18, 2022

Bibliography with links to cited articles

[1]   David Applegate and Ravi Kannan: Sampling and integration of near log-concave functions. In Proc. 23rd STOC, pp. 156–163. ACM Press, 1991. [doi:10.1145/103418.103439]

[2]   Yu Cao, Jianfeng Lu, and Lihan Wang: On explicit L2-convergence rate estimate for underdamped Langevin dynamics, 2019. [arXiv:1908.04746]

[3]   Niladri S. Chatterji, Nicolas Flammarion, Yi-An Ma, Peter L. Bartlett, and Michael I. Jordan: On the theory of variance reduction for stochastic gradient Monte Carlo. In Proc. 35th Internat. Conf. Artificial Intelligence and Statistics (ICML’18), pp. 80:764–773. MLR Press, 2018. PMLR. [arXiv:1802.05431]

[4]   Yuansi Chen, Raaz Dwivedi, Martin J. Wainwright, and Bin Yu: Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients. JMLR, 21(92):1–72, 2019. JMLR. [arXiv:1905.12247]

[5]   Zongchen Chen and Santosh S. Vempala: Optimal convergence rate of Hamiltonian Monte Carlo for strongly logconcave distributions. In Proc. 23rd Internat. Conf. on Randomization and Computation (RANDOM’19), pp. 64:1–12. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.APPROX-RANDOM.2019.64, arXiv:1905.02313]

[6]   Xiang Cheng, Niladri S. Chatterji, Yasin Abbasi-Yadkori, Peter L. Bartlett, and Michael I. Jordan: Sharp convergence rates for Langevin dynamics in the nonconvex setting, 2018. [arXiv:1805.01648]

[7]   Xiang Cheng, Niladri S. Chatterji, Peter L. Bartlett, and Michael I. Jordan: Underdamped Langevin MCMC: A non-asymptotic analysis. In Proc. 31st Ann. Conf. on Learning Theory (COLT’18), pp. 75:1–24. MLR Press, 2018. PMLR. [arXiv:1707.03663]

[8]   Arnak S. Dalalyan: Theoretical guarantees for approximate sampling from smooth and log-concave densities. J. Royal Statistical Soc. Ser. B, 79(3):651–676, 2017. [doi:10.1111/rssb.12183, arXiv:1412.7392]

[9]   Arnak S. Dalalyan and Avetik Karagulyan: User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient. Stoch. Proc. Appl., 129(12):5278–5311, 2019. [doi:10.1016/j.spa.2019.02.016, arXiv:1710.00095]

[10]   Arnak S. Dalalyan and Lionel Riou-Durand: On sampling from a log-concave density using kinetic Langevin diffusions. Bernoulli, 26(3):1956–1988, 2020. [doi:10.3150/19-BEJ1178, arXiv:1807.09382]

[11]   Arnak S. Dalalyan, Lionel Riou-Durand, and Avetik Karagulyan: Bounding the error of discretized Langevin algorithms for non-strongly log-concave targets, 2019. [arXiv:1906.08530]

[12]   Raaz Dwivedi, Yuansi Chen, Martin J. Wainwright, and Bin Yu: Log-concave sampling: Metropolis-Hastings algorithms are fast! JMLR, 20(183):1–42, 2019. JMLR, Preliminary version in COLT’18. [arXiv:1801.02309]

[13]   Yin Tat Lee, Ruoqi Shen, and Kevin Tian: Logsmooth gradient concentration and tighter runtimes for Metropolized Hamiltonian Monte Carlo. In Proc. 33rd Ann. Conf. on Learning Theory (COLT’20), pp. 125:2565–2597. MLR Press, 2020. PMLR. [arXiv:2002.04121]

[14]   Yin Tat Lee, Zhao Song, and Santosh S. Vempala: Algorithmic theory of ODEs and sampling from well-conditioned logconcave densities, 2018. [arXiv:1812.06243]

[15]   Yin Tat Lee and Santosh S. Vempala: Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation. In Proc. 50th STOC, pp. 1115–1121. ACM Press, 2018. [doi:10.1145/3188745.3188774, arXiv:1710.06261]

[16]   László Lovász and Santosh S. Vempala: Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization. In Proc. 47th FOCS, pp. 57–68. IEEE Comp. Soc., 2006. [doi:10.1109/FOCS.2006.28]

[17]   Yi-An Ma, Niladri Chatterji, Xiang Cheng, Nicolas Flammarion, Peter Bartlett, and Michael I. Jordan: Is there an analog of Nesterov acceleration for MCMC?, 2019. [arXiv:1902.00996]

[18]   Oren Mangoubi and Aaron Smith: Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions 1: Continuous dynamics, 2017. [arXiv:1708.07114]

[19]   Oren Mangoubi and Aaron Smith: Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions 2: Numerical integrators. In Proc. 22nd Internat. Conf. Artificial Intelligence and Statistics (AISTATS’19), pp. 89:586–595. MLR Press, 2019. PMLR.

[20]   Oren Mangoubi and Nisheeth Vishnoi: Dimensionally tight bounds for second-order Hamiltonian Monte Carlo. In Proc. 31st Adv. Neural Info. Proc. Sys. (NeurIPS’18), pp. 6027–6037. Curran Assoc., 2018. NeurIPS.

[21]   Wenlong Mou, Yi-An Ma, Martin J. Wainwright, Peter L. Bartlett, and Michael I. Jordan: High-order Langevin diffusion yields an accelerated MCMC algorithm. JMLR, 22(42):1–41, 2021. JMLR. [arXiv:1908.10859]

[22]   Yann Ollivier: Ricci curvature of Markov chains on metric spaces. J. Functional Anal., 256(3):810–864, 2009. [doi:10.1016/j.jfa.2008.11.001, arXiv:math/0701886]

[23]   Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky: Non-convex learning via stochastic gradient Langevin dynamics: A nonasymptotic analysis. In Proc. 30th Ann. Conf. on Learning Theory (COLT’17), pp. 65:1–30. MLR Press, 2017. PMLR. [arXiv:1702.03849]

[24]   Christof Seiler, Simon Rubinstein-Salzedo, and Susan Holmes: Positive curvature and Hamiltonian Monte Carlo. In Proc. 27th Adv. Neural Info. Proc. Sys. (NIPS’14), pp. 586–594. Curran Assoc., 2014. NIPS.

[25]   Ruoqi Shen and Yin Tat Lee: The Randomized Midpoint Method for log-concave sampling. In Proc. 32nd Adv. Neural Info. Proc. Sys. (NeurIPS’19), pp. 2100–2111. Curran Assoc., 2019. NeurIPS. [arXiv:1909.05503]

[26]   Santosh S. Vempala and Andre Wibisono: Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices. In Proc. 32nd Adv. Neural Info. Proc. Sys. (NeurIPS’19), pp. 8094–8106. Curran Assoc., 2019. NeurIPS. [arXiv:1903.08568]

[27]   Andre Wibisono: Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem. In Proc. 31st Ann. Conf. on Learning Theory (COLT’18), pp. 75:2093–3027. MLR Press, 2018. PMLR. [arXiv:1802.08089]

[28]   Andre Wibisono: Proximal Langevin algorithm: Rapid convergence under isoperimetry, 2019. [arXiv:1911.01469]

[29]   Yuchen Zhang, Percy S. Liang, and Moses Charikar: A hitting time analysis of stochastic gradient Langevin dynamics. In Proc. 30th Ann. Conf. on Learning Theory (COLT’17), pp. 65:1980–2022. MLR Press, 2017. PMLR. [arXiv:1702.05575]

[30]   Xingyu Zhou: On the Fenchel Duality between strong convexity and Lipschitz Continuous Gradient, 2018. SLIDES. [arXiv:1803.06573]