Oracle-based Uniform Sampling from Convex Bodies
This work addresses a fundamental problem in computational geometry and statistics for researchers and practitioners needing efficient sampling methods, but it is incremental as it builds on existing frameworks with novel oracle implementations.
The paper tackles the problem of uniformly sampling from convex bodies by proposing new Markov chain Monte Carlo algorithms based on the Alternating Sampling Framework, with a key contribution being an efficient implementation of the restricted Gaussian oracle using rejection sampling and access to projection or separation oracles, resulting in non-asymptotic complexity bounds for unbiased samples measured in Rényi or χ²-divergence.
We propose new Markov chain Monte Carlo algorithms to sample a uniform distribution on a convex body $K$. Our algorithms are based on the Alternating Sampling Framework/proximal sampler, which uses Gibbs sampling on an augmented distribution and assumes access to the so-called restricted Gaussian oracle (RGO). The key contribution of this work is the efficient implementation of RGO for uniform sampling on $K$ via rejection sampling and access to either a projection oracle or a separation oracle on $K$. In both oracle cases, we establish non-asymptotic complexities to obtain unbiased samples where the accuracy is measured in Rényi divergence or $χ^2$-divergence.