Sampling with Barriers: Faster Mixing via Lewis Weights

Abstract: We analyze Riemannian Hamiltonian Monte Carlo (RHMC) for sampling a polytope defined by m inequalities in R^n endowed with the metric defined by the Hessian of a self-concordant convex barrier function. We use a hybrid of the p-Lewis weight barrier and the standard logarithmic barrier and prove that the mixing rate is bounded by \tilde{O}(m1/3n 4/3), improving on the previous best bound of \tilde{O}(mn2/3), based on the log barrier. Our analysis overcomes several technical challenges to establish this result, in the process deriving smoothness bounds on Hamiltonian curves and extending self-concordance notions to the infinity norm; both properties appear to be of independent interest.