# Sampling from Log-Concave Distributions with Infinity-Distance Guarantees

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 50 references that are in the map.
- First posted on arXiv 7 Nov 2021.

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

- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem](https://mlsanity.com/paper/1802.08089/) (2018)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [Convergence of Langevin MCMC in KL-divergence](https://mlsanity.com/paper/1705.09048/) (2017)
- [On sampling from a log-concave density using kinetic Langevin diffusions](https://mlsanity.com/paper/1807.09382/) (2018)
- [Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo](https://mlsanity.com/paper/1705.08964/) (2017)
- [Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation](https://mlsanity.com/paper/1710.06261/) (2017)
- [Faster Differentially Private Samplers via R'enyi Divergence Analysis of Discretized Langevin MCMC](https://mlsanity.com/paper/2010.14658/) (2020)
- [Eldan's Stochastic Localization and the KLS Conjecture: Isoperimetry, Concentration and Mixing](https://mlsanity.com/paper/1612.01507/) (2016)
- [An Introduction to Hamiltonian Monte Carlo Method for Sampling](https://mlsanity.com/paper/2108.12107/) (2021)
- [Efficient Sampling from Time-Varying Log-Concave Distributions](https://mlsanity.com/paper/1309.5977/) (2013)
- [The Mixing Time of the Dikin Walk in a Polytope - A Simple Proof](https://mlsanity.com/paper/1508.01977/) (2015)
- [Sampling Matrices from Harish-Chandra-Itzykson-Zuber Densities with Applications to Quantum Inference and Differential Privacy](https://mlsanity.com/paper/2011.05417/) (2020)

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

- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation](https://mlsanity.com/paper/2211.00724/) (2022)
- [Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy](https://mlsanity.com/paper/2310.14661/) (2023)
- [Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization](https://mlsanity.com/paper/2204.01585/) (2022)
- [Private Matrix Approximation and Geometry of Unitary Orbits](https://mlsanity.com/paper/2207.02794/) (2022)
- [Purifying Approximate Differential Privacy with Randomized Post-processing](https://mlsanity.com/paper/2503.21071/) (2025)
- [Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walk](https://mlsanity.com/paper/2206.09384/) (2022)

## Abstract (arXiv)

For a d-dimensional log-concave distribution π(θ) propto e-f(θ) constrained to a convex body K, the problem of outputting samples from a distribution nu which is varepsilon-close in infinity-distance supθ ∈ K |log fracnu(θ)π(θ)| to π arises in differentially private optimization. While sampling within total-variation distance varepsilon of π can be done by algorithms whose runtime depends polylogarithmically on frac1varepsilon, prior algorithms for sampling in varepsilon infinity distance have runtime bounds that depend polynomially on frac1varepsilon. We bridge this gap by presenting an algorithm that outputs a point varepsilon-close to π in infinity distance that requires at most poly(log frac1varepsilon, d) calls to a membership oracle for K and evaluation oracle for f, when f is Lipschitz. Our approach departs from prior works that construct Markov chains on a frac1varepsilon2-discretization of K to achieve a sample with varepsilon infinity-distance error, and present a method to directly convert continuous samples from K with total-variation bounds to samples with infinity bounds. This approach also allows us to obtain an improvement on the dimension d in the running time for the problem of sampling from a log-concave distribution on polytopes K with infinity distance varepsilon, by plugging in TV-distance running time bounds for the Dikin Walk Markov chain.