# Sampling with Barriers: Faster Mixing via Lewis Weights

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 28 references that are in the map.
- First posted on arXiv 1 Mar 2023.

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

- [Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation](https://mlsanity.com/paper/1710.06261/) (2017)
- [Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space](https://mlsanity.com/paper/2202.01908/) (2022)
- [Solving Linear Programs with Sqrt(rank) Linear System Solves](https://mlsanity.com/paper/1910.08033/) (2019)
- [Geodesic Walks in Polytopes](https://mlsanity.com/paper/1606.04696/) (2016)
- [Strong Self-Concordance and Sampling](https://mlsanity.com/paper/1911.05656/) (2019)
- [Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integrators](https://mlsanity.com/paper/2210.07219/) (2022)
- [Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast](https://mlsanity.com/paper/2009.11338/) (2020)

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

- [In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies](https://mlsanity.com/paper/2405.01425/) (2024)
- [Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm](https://mlsanity.com/paper/2312.08823/) (2023)
- [Simplicity Bias via Global Convergence of Sharpness Minimization](https://mlsanity.com/paper/2410.16401/) (2024)
- [R'enyi-infinity constrained sampling with d3 membership queries](https://mlsanity.com/paper/2407.12967/) (2024)
- [Oracle-based Uniform Sampling from Convex Bodies](https://mlsanity.com/paper/2510.02983/) (2025)
- [Tukey Depth Mechanisms for Practical Private Mean Estimation](https://mlsanity.com/paper/2502.18698/) (2025)
- [Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling](https://mlsanity.com/paper/2307.12943/) (2023)

## Abstract (arXiv)

We analyze Riemannian Hamiltonian Monte Carlo (RHMC) for sampling a polytope defined by m inequalities in Rn endowed with the metric defined by the Hessian of a convex barrier function. 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 has a linear dependence on the number of inequalities. We introduce a hybrid of the Lewis weights barrier and the standard logarithmic barrier and prove that the mixing rate for the corresponding RHMC is bounded by tilde O(m1/3n4/3), improving on the previous best bound of tilde O(mn2/3) (based on the log barrier). This continues the general parallels between optimization and sampling, with the latter typically leading to new tools and more refined analysis. To prove our main results, we have to overcomes several challenges relating to the smoothness of Hamiltonian curves and the 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 to the infinity norm, which gives sharper bounds; these properties appear to be of independent interest.