Skip to content
Preprint

Polytope Sampling at the Speed of Isoperimetry

Oct 2026 · 0 citations
Computer Science Mathematics

Abstract

We give faster algorithms for sampling from the uniform distribution over a polytope. Our main result is an algorithm that, when applied to a polytope with $m$ constraints in $n$ dimensions, uses $m \cdot \mathrm{poly}\log(\frac m \delta)$ iterations, each running in time $O(mn^{\omega - 1})$, to return a sample within total variation distance $\delta$ to the uniform distribution. When $m =O(n)$ and $\delta = \mathrm{poly}(\frac 1 n)$, our runtime improves upon all prior works by an $\Omega(n^{2/3})$ factor. Our sampler is based on the recent \emph{functional stochastic localization} framework of [GST26], and achieves an iteration count nearly matching the Poincar\'e constant of the uniform distribution with respect to the logarithmic barrier.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.