Hit-and-Run Mixing via Localization Schemes

Abstract We analyze the hit-and-run algorithm for sampling uniformly from an isotropic convex body K in n dimensions. We show that the algorithm mixes in $$\epsilon $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ϵ</mml:mi> </mml:math> -total variation error with $$O_\epsilon (n^2/ \psi _n^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>O</mml:mi> <mml:mi>ϵ</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>/</mml:mo> <mml:msubsup> <mml:mi>ψ</mml:mi> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msubsup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> steps, where $$\psi _n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ψ</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:math> is the smallest isoperimetric constant for any isotropic logconcave distribution, also known as the Kannan-Lovasz-Simonovits (KLS) constant [19]. Our bound improves upon previous bounds of the form $$O_\epsilon (n^2 R^2/r^2)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>O</mml:mi> <mml:mi>ϵ</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:msup> <mml:mi>R</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>/</mml:mo> <mml:msup> <mml:mi>r</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , which depend on the ratio R / r of the radii of the circumscribed and inscribed balls of K , gaining a factor of n in the case of isotropic convex bodies. Consequently, our result gives a mixing time estimate for the hit-and-run which matches the state-of-the-art bounds for the ball walk. Our main proof technique is based on an annealing of localization schemes introduced in Chen and Eldan [7], which allows us to reduce the problem to the analysis of the mixing time on truncated Gaussian distributions.