pipette
ESEspañol

Polytope Sampling at the Speed of Isoperimetry

Anming Gu, Bobby Shi, Kevin Tian, Hubert Yang

Preprint

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