mlsanityData to 14 Oct 2026

Oracle-based Uniform Sampling from Convex Bodies

arXiv 2510.02983 ↗First posted 3 Oct 2025cs.DS cs.LG math.OCcited by 3

Not on the map. Why?

Abstract (arXiv)

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'enyi divergence and chi2-divergence, and we support these theoretical guarantees with numerical experiments.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 31 of its 78 references that are in the map. First posted on arXiv 3 Oct 2025.

Builds on

31 of 78 references.

References · 31

  1. 2021Convex optimizationcited by 2,515
  2. 2020Structured Logconcave Sampling with a Restricted Gaussian Oraclecited by 86
  3. 2022Improved analysis for a proximal algorithm for samplingcited by 73
  4. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  5. 2020Wasserstein Control of Mirror Langevin Monte Carlocited by 55
  6. 2020Efficient constrained sampling via the mirror-Langevin algorithmcited by 55
  7. 2015Sampling from a log-concave distribution with Projected Langevin Monte Carlocited by 52
  8. 2022Private Convex Optimization via Exponential Mechanismcited by 49
  9. 2017Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlocited by 43
  10. 2021The Mirror Langevin Algorithm Converges with Vanishing Biascited by 37
  11. 2017Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computationcited by 32
  12. 2023Improved dimension dependence of a proximal algorithm for samplingcited by 30
19 more
  1. 2021The Langevin Monte Carlo algorithm in the non-smooth log-concave casecited by 26
  2. 2021A Proximal Algorithm for Sampling from Non-smooth Potentialscited by 24
  3. 2022A Proximal Algorithm for Samplingcited by 22
  4. 2024In-and-Out: Algorithmic Diffusion for Sampling Convex Bodiescited by 19
  5. 2016Geodesic Walks in Polytopescited by 13
  6. 2022Penalized Overdamped and Underdamped Langevin Monte Carlo Algorithms for Constrained Samplingcited by 13
  7. 2024Sampling and Integration of Logconcave Functions by Algorithmic Diffusioncited by 12
  8. 2025Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequalitycited by 12
  9. 2023Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithmcited by 11
  10. 2024Fast Convergence of Phi-Divergence Along the Unadjusted Langevin Algorithm and Proximal Samplercited by 11
  11. 2022Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integratorscited by 10
  12. 2023Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Samplercited by 10
  13. 2020Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fastcited by 9
  14. 2023Sampling with Barriers: Faster Mixing via Lewis Weightscited by 7
  15. 2025Faster logconcave sampling from a cold start in high dimensioncited by 7
  16. 2024Proximal Oracles for Optimization and Samplingcited by 6
  17. 2020On the mixing time of coordinate Hit-and-Runcited by 5
  18. 2024Rapid Mixing at the Uniqueness Thresholdcited by 4
  19. 2013Efficient Random-Walk Methods for Approximating Polytope Volumecited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Alternating Diffusion for Proximal Sampling with Zeroth Order Queriescited by 1
  2. 2026A proximal gradient algorithm for composite log-concave samplingcited by 1
  3. 2026The Geometry of Efficient Nonconvex Samplingcited by 0