Sampling Polytopes with Riemannian HMC: Faster Mixing via the Lewis Weights Barrier |
Original Papers |
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. |
inproceedings |
Proceedings of Machine Learning Research |
PMLR |
2640-3498 |
gatmiry24a |
0 |
Sampling Polytopes with Riemannian HMC: Faster Mixing via the Lewis Weights Barrier |
1796 |
1881 |
1796-1881 |
1796 |
false |
Gatmiry, Khashayar and Kelner, Jonathan and Vempala, Santosh S. |
| given |
family |
Khashayar |
Gatmiry |
|
| given |
family |
Jonathan |
Kelner |
|
| given |
family |
Santosh S. |
Vempala |
|
|
2024-06-30 |
|
Proceedings of Thirty Seventh Conference on Learning Theory |
247 |
inproceedings |
|
|
|