Rényi-infinity constrained sampling with $d^3$ membership queries
This work addresses a fundamental algorithmic problem in sampling for convex bodies, offering a novel method with improved convergence guarantees and query complexity, which is incremental but significant for the field of computational geometry and optimization.
The paper tackles the problem of uniform sampling over convex bodies by proposing a constrained proximal sampler that converges in Rényi-infinity divergence with no query overhead from a warm start, achieving an algorithm with query complexity of approximately O(d^3 polylog(1/ε)) to sample ε-close to uniform, improving on prior results in other divergences.
Uniform sampling over a convex body is a fundamental algorithmic problem, yet the convergence in KL or Rényi divergence of most samplers remains poorly understood. In this work, we propose a constrained proximal sampler, a principled and simple algorithm that possesses elegant convergence guarantees. Leveraging the uniform ergodicity of this sampler, we show that it converges in the Rényi-infinity divergence ($\mathcal R_\infty$) with no query complexity overhead when starting from a warm start. This is the strongest of commonly considered performance metrics, implying rates in $\{\mathcal R_q, \mathsf{KL}\}$ convergence as special cases. By applying this sampler within an annealing scheme, we propose an algorithm which can approximately sample $\varepsilon$-close to the uniform distribution on convex bodies in $\mathcal R_\infty$-divergence with $\widetilde{\mathcal{O}}(d^3\, \text{polylog} \frac{1}{\varepsilon})$ query complexity. This improves on all prior results in $\{\mathcal R_q, \mathsf{KL}\}$-divergences, without resorting to any algorithmic modifications or post-processing of the sample. It also matches the prior best known complexity in total variation distance.