Polytope Sampling at the Speed of Isoperimetry
In the authors' words
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 constraints in dimensions, uses iterations, each running in time , to return a sample within total variation distance to the uniform distribution. When and , our runtime improves upon all prior works by an factor. Our sampler is based on the recent 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.
Main resultThe abstract does not state a limitation.
Appeared: Monday, October 19. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 58 pages