R'enyi-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'enyi 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'enyi-infinity divergence (mathcal R_∞) with no query complexity overhead when starting from a warm start. This is the strongest of commonly considered performance metrics, implying rates in mathcal Rq, mathsfKL 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_∞-divergence with widetildeO(d3, polylog frac1varepsilon) query complexity. This improves on all prior results in mathcal Rq, mathsfKL-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.