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]