PreprintCC BY 4.0arXiv
Polytope Sampling at the Speed of Isoperimetry
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 · polylog(m/δ) iterations, each running in time O(mnω− 1), to return a sample within total variation distance δ to the uniform distribution. When m =O(n) and δ= poly(1/n), our runtime improves upon all prior works by an Ω(n2/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é constant of the uniform distribution with respect to the logarithmic barrier.
Related
BibTeX
@misc{gu2026polytope,
title = {{Polytope Sampling at the Speed of Isoperimetry}},
author = {Anming Gu and Bobby Shi and Kevin Tian and Hubert Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.23775},
eprint = {2610.23775},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.23775},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Polytope Sampling at the Speed of Isoperimetry
AU - Anming Gu
AU - Bobby Shi
AU - Kevin Tian
AU - Hubert Yang
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.23775
UR - https://arxiv.org/abs/2610.23775
AB - 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 · polylog(m/δ) iterations, each running in time O(mn^ω− 1), to return a sample within total variation distance δ to the uniform distribution. When m =O(n) and δ= poly(1/n), our runtime improves upon all prior works by an Ω(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é constant of the uniform distribution with respect to the logarithmic barrier.
ER -