# R'enyi-infinity constrained sampling with d3 membership queries

arXiv: https://arxiv.org/abs/2407.12967 · HTML: https://mlsanity.com/paper/2407.12967/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 73 references that are in the map.
- First posted on arXiv 17 Jul 2024.

## Builds on (most cited first, 30 of 30)

- [Pyro: Deep Universal Probabilistic Programming](https://mlsanity.com/paper/1810.09538/) (2018)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Convergence of Langevin MCMC in KL-divergence](https://mlsanity.com/paper/1705.09048/) (2017)
- [Structured Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2010.03106/) (2020)
- [Improved analysis for a proximal algorithm for sampling](https://mlsanity.com/paper/2202.06386/) (2022)
- [Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm](https://mlsanity.com/paper/2012.12810/) (2020)
- [Wasserstein Control of Mirror Langevin Monte Carlo](https://mlsanity.com/paper/2002.04363/) (2020)
- [Efficient constrained sampling via the mirror-Langevin algorithm](https://mlsanity.com/paper/2010.16212/) (2020)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo](https://mlsanity.com/paper/1705.08964/) (2017)
- [Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence](https://mlsanity.com/paper/2007.11612/) (2020)
- [Improved Bounds for Discretization of Langevin Diffusions: Near-Optimal Rates without Convexity](https://mlsanity.com/paper/1907.11331/) (2019)
- [The Mirror Langevin Algorithm Converges with Vanishing Bias](https://mlsanity.com/paper/2109.12077/) (2021)
- [Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation](https://mlsanity.com/paper/1710.06261/) (2017)
- [Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequality](https://mlsanity.com/paper/2303.03589/) (2023)
- [Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space](https://mlsanity.com/paper/2202.01908/) (2022)
- [Improved Discretization Analysis for Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2302.08049/) (2023)
- [Faster Differentially Private Samplers via R'enyi Divergence Analysis of Discretized Langevin MCMC](https://mlsanity.com/paper/2010.14658/) (2020)
- [The Langevin Monte Carlo algorithm in the non-smooth log-concave case](https://mlsanity.com/paper/2101.10695/) (2021)
- [Riemannian Langevin Algorithm for Solving Semidefinite Programs](https://mlsanity.com/paper/2010.11176/) (2020)
- [In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies](https://mlsanity.com/paper/2405.01425/) (2024)
- [Fast MCMC sampling algorithms on polytopes](https://mlsanity.com/paper/1710.08165/) (2017)
- [When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?](https://mlsanity.com/paper/2304.04724/) (2023)
- [Private Convex Optimization in General Norms](https://mlsanity.com/paper/2207.08347/) (2022)
- [Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm](https://mlsanity.com/paper/2312.08823/) (2023)
- [Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integrators](https://mlsanity.com/paper/2210.07219/) (2022)
- [Sampling with Barriers: Faster Mixing via Lewis Weights](https://mlsanity.com/paper/2303.00480/) (2023)

## Built on by (most cited first, 3 of 3)

- [Beyond the d2.5-mixing bound for Dikin walks on polytopes](https://mlsanity.com/paper/2607.13943/) (2026)
- [A proximal gradient algorithm for composite log-concave sampling](https://mlsanity.com/paper/2605.12461/) (2026)
- [Thin-shell stability of Gaussian cooling: logconcave sampling with sesteric complexity from a cold start](https://mlsanity.com/paper/2609.15884/) (2026)

## Abstract (arXiv)

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.