Sampling Polytopes with Riemannian HMC: Faster Mixing via the Lewis Weights Barrier

Khashayar Gatmiry, Jonathan Kelner, Santosh S. Vempala
Proceedings of Thirty Seventh Conference on Learning Theory, PMLR 247:1796-1881, 2024.

Abstract

We analyze Riemannian Hamiltonian Monte Carlo (RHMC) on a manifold endowed with the metric defined by the Hessian of a convex barrier function and apply it to sample a polytope defined by $m$ inequalities in $\R^n$. The advantage of RHMC over Euclidean methods such as the ball walk, hit-and-run and the Dikin walk is in its ability to take longer steps. However, in all previous work, the mixing rate of RHMC has a linear dependence on the number of inequalities. We introduce a hybrid of the Lewis weight barrier and the standard logarithmic barrier and prove that the mixing rate for the corresponding RHMC is bounded by $\tilde O(m^{1/3}n^{4/3})$, improving on the previous best bound of $\tilde O(mn^{2/3})$ (based on the log barrier). This continues the general parallels between optimization and sampling, with the latter typically leading to new tools and requiring more refined analysis. To prove our main results, we overcomes several challenges relating to the smoothness of Hamiltonian curves and self-concordance properties of the barrier. In the process, we give a general framework for the analysis of Markov chains on Riemannian manifolds, derive new smoothness bounds on Hamiltonian curves, a central topic of comparison geometry, and extend self-concordance theory to the infinity norm, which gives sharper bounds; these properties all appear to be of independent interest.

Cite this Paper

BibTeX
@InProceedings{pmlr-v247-gatmiry24a, title = {Sampling Polytopes with Riemannian HMC: Faster Mixing via the Lewis Weights Barrier}, author = {Gatmiry, Khashayar and Kelner, Jonathan and Vempala, Santosh S.}, booktitle = {Proceedings of Thirty Seventh Conference on Learning Theory}, pages = {1796--1881}, year = {2024}, editor = {Agrawal, Shipra and Roth, Aaron}, volume = {247}, series = {Proceedings of Machine Learning Research}, month = {30 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v247/gatmiry24a/gatmiry24a.pdf}, url = {https://proceedings.mlr.press/v247/gatmiry24a.html}, abstract = {We analyze Riemannian Hamiltonian Monte Carlo (RHMC) on a manifold endowed with the metric defined by the Hessian of a convex barrier function and apply it to sample a polytope defined by $m$ inequalities in $\R^n$. The advantage of RHMC over Euclidean methods such as the ball walk, hit-and-run and the Dikin walk is in its ability to take longer steps. However, in all previous work, the mixing rate of RHMC has a linear dependence on the number of inequalities. We introduce a hybrid of the Lewis weight barrier and the standard logarithmic barrier and prove that the mixing rate for the corresponding RHMC is bounded by $\tilde O(m^{1/3}n^{4/3})$, improving on the previous best bound of $\tilde O(mn^{2/3})$ (based on the log barrier). This continues the general parallels between optimization and sampling, with the latter typically leading to new tools and requiring more refined analysis. To prove our main results, we overcomes several challenges relating to the smoothness of Hamiltonian curves and self-concordance properties of the barrier. In the process, we give a general framework for the analysis of Markov chains on Riemannian manifolds, derive new smoothness bounds on Hamiltonian curves, a central topic of comparison geometry, and extend self-concordance theory to the infinity norm, which gives sharper bounds; these properties all appear to be of independent interest.} }
Endnote
%0 Conference Paper %T Sampling Polytopes with Riemannian HMC: Faster Mixing via the Lewis Weights Barrier %A Khashayar Gatmiry %A Jonathan Kelner %A Santosh S. Vempala %B Proceedings of Thirty Seventh Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2024 %E Shipra Agrawal %E Aaron Roth %F pmlr-v247-gatmiry24a %I PMLR %P 1796--1881 %U https://proceedings.mlr.press/v247/gatmiry24a.html %V 247 %X We analyze Riemannian Hamiltonian Monte Carlo (RHMC) on a manifold endowed with the metric defined by the Hessian of a convex barrier function and apply it to sample a polytope defined by $m$ inequalities in $\R^n$. The advantage of RHMC over Euclidean methods such as the ball walk, hit-and-run and the Dikin walk is in its ability to take longer steps. However, in all previous work, the mixing rate of RHMC has a linear dependence on the number of inequalities. We introduce a hybrid of the Lewis weight barrier and the standard logarithmic barrier and prove that the mixing rate for the corresponding RHMC is bounded by $\tilde O(m^{1/3}n^{4/3})$, improving on the previous best bound of $\tilde O(mn^{2/3})$ (based on the log barrier). This continues the general parallels between optimization and sampling, with the latter typically leading to new tools and requiring more refined analysis. To prove our main results, we overcomes several challenges relating to the smoothness of Hamiltonian curves and self-concordance properties of the barrier. In the process, we give a general framework for the analysis of Markov chains on Riemannian manifolds, derive new smoothness bounds on Hamiltonian curves, a central topic of comparison geometry, and extend self-concordance theory to the infinity norm, which gives sharper bounds; these properties all appear to be of independent interest.
APA
Gatmiry, K., Kelner, J. & Vempala, S.S.. (2024). Sampling Polytopes with Riemannian HMC: Faster Mixing via the Lewis Weights Barrier. Proceedings of Thirty Seventh Conference on Learning Theory, in Proceedings of Machine Learning Research 247:1796-1881 Available from https://proceedings.mlr.press/v247/gatmiry24a.html.

Related Material