Faster sampling algorithms improve high dimensional polytope exploration
Polytope Sampling at the Speed of Isoperimetry
Data Structures and Algorithms
Summary
Sampling means picking random points inside complicated shapes called polytopes, which is hard when the shapes have many sides and dimensions. The paper presents a new method that speeds up this process using fewer steps and faster calculations. This makes it easier to study or use these shapes in math and computer science. The method builds on a recent approach involving something called functional stochastic localization, which helps ensure the samples are close to truly random.
What this means in practice
- •For optimization engineers: Improve random sampling inside constraint-defined regions to speed up algorithms that rely on uniform sampling within polytopes.
- •For machine learning developers: Generate faster uniform samples from high-dimensional feasible sets to improve training and inference in constrained optimization tasks.
Authors
Anming Gu, Bobby Shi, Kevin Tian, Hubert Yang
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 δ)$ 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 $δ= \mathrm{poly}(\frac 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.