# Improved dimension dependence of a proximal algorithm for sampling

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 47 references that are in the map.
- First posted on arXiv 20 Feb 2023.

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

- [Stein Variational Gradient Descent: A General Purpose Bayesian Inference Algorithm](https://mlsanity.com/paper/1608.04471/) (2016)
- [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)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [Structured Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2010.03106/) (2020)
- [Efficient Bayesian computation by proximal Markov chain Monte Carlo: when Langevin meets Moreau](https://mlsanity.com/paper/1612.07471/) (2016)
- [The Randomized Midpoint Method for Log-Concave Sampling](https://mlsanity.com/paper/1909.05503/) (2019)
- [Improved analysis for a proximal algorithm for sampling](https://mlsanity.com/paper/2202.06386/) (2022)
- [On sampling from a log-concave density using kinetic Langevin diffusions](https://mlsanity.com/paper/1807.09382/) (2018)
- [Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss](https://mlsanity.com/paper/2205.13710/) (2022)
- [Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm](https://mlsanity.com/paper/2012.12810/) (2020)
- [On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness](https://mlsanity.com/paper/2005.13097/) (2020)
- [Variational Wasserstein gradient flow](https://mlsanity.com/paper/2112.02424/) (2021)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence](https://mlsanity.com/paper/2007.11612/) (2020)
- [Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin Algorithm](https://mlsanity.com/paper/2006.09270/) (2020)
- [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)
- [Sqrt(d) Dimension Dependence of Langevin Monte Carlo](https://mlsanity.com/paper/2109.03839/) (2021)
- [A Proximal Algorithm for Sampling from Non-smooth Potentials](https://mlsanity.com/paper/2110.04597/) (2021)
- [On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method](https://mlsanity.com/paper/2011.03176/) (2020)
- [A Proximal Algorithm for Sampling](https://mlsanity.com/paper/2202.13975/) (2022)
- [An Efficient Sampling Algorithm for Non-smooth Composite Potentials](https://mlsanity.com/paper/1910.00551/) (2019)
- [The query complexity of sampling from strongly log-concave distributions in one dimension](https://mlsanity.com/paper/2105.14163/) (2021)
- [A Proximal Algorithm for Sampling from Non-convex Potentials](https://mlsanity.com/paper/2205.10188/) (2022)

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

- [The probability flow ODE is provably fast](https://mlsanity.com/paper/2305.11798/) (2023)
- [Principled Probabilistic Imaging using Diffusion Models as Plug-and-Play Priors](https://mlsanity.com/paper/2405.18782/) (2024)
- [Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling](https://mlsanity.com/paper/2407.16936/) (2024)
- [Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion](https://mlsanity.com/paper/2402.17886/) (2024)
- [In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies](https://mlsanity.com/paper/2405.01425/) (2024)
- [High-accuracy sampling for diffusion models and log-concave distributions](https://mlsanity.com/paper/2602.01338/) (2026)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequality](https://mlsanity.com/paper/2502.05623/) (2025)
- [Fast Convergence of Phi-Divergence Along the Unadjusted Langevin Algorithm and Proximal Sampler](https://mlsanity.com/paper/2410.10699/) (2024)
- [Sampling from the Mean-Field Stationary Distribution](https://mlsanity.com/paper/2402.07355/) (2024)
- [Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians](https://mlsanity.com/paper/2410.01656/) (2024)
- [Faster logconcave sampling from a cold start in high dimension](https://mlsanity.com/paper/2505.01937/) (2025)
- [Proximal Oracles for Optimization and Sampling](https://mlsanity.com/paper/2404.02239/) (2024)
- [A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers](https://mlsanity.com/paper/2405.16736/) (2024)
- [Characterizing Dependence of Samples along the Langevin Dynamics and Algorithms via Contraction of Phi-Mutual Information](https://mlsanity.com/paper/2402.17067/) (2024)
- [Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Bias](https://mlsanity.com/paper/2408.13115/) (2024)
- [Beyond Scores: Proximal Diffusion Models](https://mlsanity.com/paper/2507.08956/) (2025)
- [Oracle-based Uniform Sampling from Convex Bodies](https://mlsanity.com/paper/2510.02983/) (2025)
- [Convergence Analysis of the Wasserstein Proximal Algorithm beyond Geodesic Convexity](https://mlsanity.com/paper/2501.14993/) (2025)
- [High-accuracy log-concave sampling with stochastic queries](https://mlsanity.com/paper/2602.14342/) (2026)
- [Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Sampler](https://mlsanity.com/paper/2609.06905/) (2026)
- [Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions](https://mlsanity.com/paper/2505.15059/) (2025)
- [Alternating Diffusion for Proximal Sampling with Zeroth Order Queries](https://mlsanity.com/paper/2603.19633/) (2026)
- [A proximal gradient algorithm for composite log-concave sampling](https://mlsanity.com/paper/2605.12461/) (2026)
- [A transport approach to the cutoff phenomenon](https://mlsanity.com/paper/2509.08560/) (2025)
- [Functional Stochastic Localization](https://mlsanity.com/paper/2602.03999/) (2026)
- [The Geometry of Efficient Nonconvex Sampling](https://mlsanity.com/paper/2603.25622/) (2026)
- [Complexity of Non-Log-Concave Sampling in Fisher Information](https://mlsanity.com/paper/2605.15859/) (2026)
- [Local Geometric Mixing via Dobrushin Contraction with Applications to Diffusion Path Monte Carlo and the Proximal Sampler](https://mlsanity.com/paper/2609.28338/) (2026)
- [Reflected Proximal Dynamics for Accelerated High-Accuracy Log-Concave Sampling](https://mlsanity.com/paper/2610.16248/) (2026)

## Abstract (arXiv)

We propose a sampling algorithm that achieves superior complexity bounds in all the classical settings (strongly log-concave, log-concave, Logarithmic-Sobolev inequality (LSI), Poincar'e inequality) as well as more general settings with semi-smooth or composite potentials. Our algorithm is based on the proximal sampler introduced in~citetlee2021structured. The performance of this proximal sampler is determined by that of the restricted Gaussian oracle (RGO), a key step in the proximal sampler. The main contribution of this work is an inexact realization of RGO based on approximate rejection sampling. To bound the inexactness of RGO, we establish a new concentration inequality for semi-smooth functions over Gaussian distributions, extending the well-known concentration inequality for Lipschitz functions. Applying our RGO implementation to the proximal sampler, we achieve state-of-the-art complexity bounds in almost all settings. For instance, for strongly log-concave distributions, our method has complexity bound tildeO(kappa d1/2) without warm start, better than the minimax bound for MALA. For distributions satisfying the LSI, our bound is tilde O(hat kappa d1/2) where hat kappa is the ratio between smoothness and the LSI constant, better than all existing bounds.