Oracle-based Uniform Sampling from Convex Bodies
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910022701678592 |
|---|---|
| author | Dang, Thanh Liang, Jiaming |
| author_facet | Dang, Thanh Liang, Jiaming |
| contents | We propose new Markov chain Monte Carlo algorithms to sample a uniform distribution on a convex body $K$. Our algorithms are based on the 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 an efficient implementation of the RGO for uniform sampling on convex $K$ that goes beyond the membership-oracle model used in many classical and modern uniform samplers, and instead leverages richer oracle access commonly assumed in convex optimization. We implement the RGO via rejection sampling and access to either a projection oracle or a separation oracle on $K$. In both oracle models, we provide non-asymptotic complexity guarantees for obtaining unbiased samples, with accuracy quantified in Rényi divergence and $χ^2$-divergence, and we support these theoretical guarantees with numerical experiments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_02983 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Oracle-based Uniform Sampling from Convex Bodies Dang, Thanh Liang, Jiaming Data Structures and Algorithms Machine Learning Optimization and Control We propose new Markov chain Monte Carlo algorithms to sample a uniform distribution on a convex body $K$. Our algorithms are based on the 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 an efficient implementation of the RGO for uniform sampling on convex $K$ that goes beyond the membership-oracle model used in many classical and modern uniform samplers, and instead leverages richer oracle access commonly assumed in convex optimization. We implement the RGO via rejection sampling and access to either a projection oracle or a separation oracle on $K$. In both oracle models, we provide non-asymptotic complexity guarantees for obtaining unbiased samples, with accuracy quantified in Rényi divergence and $χ^2$-divergence, and we support these theoretical guarantees with numerical experiments. |
| title | Oracle-based Uniform Sampling from Convex Bodies |
| topic | Data Structures and Algorithms Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2510.02983 |