Rényi-infinity constrained sampling with d3 membership queries

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 (R ∞ ) with no query complexity overhead when starting from a warm start. This is the strongest of commonly considered performance metrics, implying rates in R q , KL convergence as special cases.

By applying this sampler within an annealing scheme, we propose an algorithm which can approximately sample ε-close to the uniform distribution on convex bodies in R ∞ -divergence with O(d 3 polylog 1 ε ) query complexity. This improves on all prior results in R q , 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.