# A Proximal Algorithm for Sampling

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 70 references that are in the map.
- First posted on arXiv 28 Feb 2022.

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

- [What Are Bayesian Neural Network Posteriors Really Like?](https://mlsanity.com/paper/2104.14421/) (2021)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [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)
- [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)
- [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)
- [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)
- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [On sampling from a log-concave density using kinetic Langevin diffusions](https://mlsanity.com/paper/1807.09382/) (2018)
- [On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness](https://mlsanity.com/paper/2005.13097/) (2020)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [Improved Bounds for Discretization of Langevin Diffusions: Near-Optimal Rates without Convexity](https://mlsanity.com/paper/1907.11331/) (2019)
- [Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin Algorithm](https://mlsanity.com/paper/2006.09270/) (2020)
- [Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry](https://mlsanity.com/paper/1911.01469/) (2019)
- [Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation](https://mlsanity.com/paper/1710.06261/) (2017)
- [Langevin Monte Carlo without smoothness](https://mlsanity.com/paper/1905.13285/) (2019)
- [The Langevin Monte Carlo algorithm in the non-smooth log-concave case](https://mlsanity.com/paper/2101.10695/) (2021)
- [A Proximal Algorithm for Sampling from Non-smooth Potentials](https://mlsanity.com/paper/2110.04597/) (2021)
- [An Efficient Sampling Algorithm for Non-smooth Composite Potentials](https://mlsanity.com/paper/1910.00551/) (2019)
- [Fast MCMC sampling algorithms on polytopes](https://mlsanity.com/paper/1710.08165/) (2017)
- [Bounding the error of discretized Langevin algorithms for non-strongly log-concave targets](https://mlsanity.com/paper/1906.08530/) (2019)
- [Eldan's Stochastic Localization and the KLS Conjecture: Isoperimetry, Concentration and Mixing](https://mlsanity.com/paper/1612.01507/) (2016)
- [When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint](https://mlsanity.com/paper/2110.01827/) (2021)
- [Composite Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2006.05976/) (2020)

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

- [The probability flow ODE is provably fast](https://mlsanity.com/paper/2305.11798/) (2023)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Models](https://mlsanity.com/paper/2309.11420/) (2023)
- [Improved dimension dependence of a proximal algorithm for sampling](https://mlsanity.com/paper/2302.10081/) (2023)
- [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)
- [Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequality](https://mlsanity.com/paper/2502.05623/) (2025)
- [Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians](https://mlsanity.com/paper/2410.01656/) (2024)
- [Proximal Oracles for Optimization and Sampling](https://mlsanity.com/paper/2404.02239/) (2024)
- [Characterizing Dependence of Samples along the Langevin Dynamics and Algorithms via Contraction of Phi-Mutual Information](https://mlsanity.com/paper/2402.17067/) (2024)
- [Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms](https://mlsanity.com/paper/2305.15988/) (2023)
- [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)
- [A Proximal Algorithm for Sampling from Non-convex Potentials](https://mlsanity.com/paper/2205.10188/) (2022)
- [Entropy-Guided Sampling of Flat Modes in Discrete Spaces](https://mlsanity.com/paper/2505.02296/) (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)
- [Improved sampling algorithms and functional inequalities for non-log-concave distributions](https://mlsanity.com/paper/2507.11236/) (2025)
- [Sampling on Metric Graphs](https://mlsanity.com/paper/2512.02175/) (2025)
- [The Geometry of Efficient Nonconvex Sampling](https://mlsanity.com/paper/2603.25622/) (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 study sampling problems associated with potentials that lack smoothness. The potentials can be either convex or non-convex. Departing from the standard smooth setting, the potentials are only assumed to be weakly smooth or non-smooth, or the summation of multiple such functions. We develop a sampling algorithm that resembles proximal algorithms in optimization for this challenging sampling task. Our algorithm is based on a special case of Gibbs sampling known as the alternating sampling framework (ASF). The key contribution of this work is a practical realization of the ASF based on rejection sampling for both non-convex and convex potentials that are not necessarily smooth. In almost all the cases of sampling considered in this work, our proximal sampling algorithm achieves better complexity than all existing methods.