# A Proximal Algorithm for Sampling from Non-smooth Potentials

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 51 references that are in the map.
- First posted on arXiv 9 Oct 2021.

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

- [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)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [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)
- [Efficient MCMC Sampling with Dimension-Free Convergence Rate using ADMM-type Splitting](https://mlsanity.com/paper/1905.11937/) (2019)
- [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)
- [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)
- [A proximal bundle variant with optimal iteration-complexity for a large range of prox stepsizes](https://mlsanity.com/paper/2003.11457/) (2020)
- [A unified analysis of a class of proximal bundle methods for solving hybrid convex composite optimization problems](https://mlsanity.com/paper/2110.01084/) (2021)
- [Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization](https://mlsanity.com/paper/2012.11554/) (2020)

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

- [The probability flow ODE is provably fast](https://mlsanity.com/paper/2305.11798/) (2023)
- [Improved analysis for a proximal algorithm for sampling](https://mlsanity.com/paper/2202.06386/) (2022)
- [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)
- [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)
- [A Proximal Algorithm for Sampling](https://mlsanity.com/paper/2202.13975/) (2022)
- [Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling](https://mlsanity.com/paper/2210.08448/) (2022)
- [Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks](https://mlsanity.com/paper/2302.09699/) (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)
- [Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler](https://mlsanity.com/paper/2302.06085/) (2023)
- [Bregman Proximal Langevin Monte Carlo via Bregman--Moreau Envelopes](https://mlsanity.com/paper/2207.04387/) (2022)
- [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)
- [Faster Sampling via Stochastic Gradient Proximal Sampler](https://mlsanity.com/paper/2405.16734/) (2024)
- [Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms](https://mlsanity.com/paper/2305.15988/) (2023)
- [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)
- [Alternating Diffusion for Proximal Sampling with Zeroth Order Queries](https://mlsanity.com/paper/2603.19633/) (2026)
- [Functional Stochastic Localization](https://mlsanity.com/paper/2602.03999/) (2026)
- [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)

In this work, we examine sampling problems with non-smooth potentials. We propose a novel Markov chain Monte Carlo algorithm for sampling from non-smooth potentials. We provide a non-asymptotical analysis of our algorithm and establish a polynomial-time complexity tilde cal O(dvarepsilon-1) to obtain varepsilon total variation distance to the target density, better than most existing results under the same assumptions. Our method is based on the proximal bundle method and an alternating sampling framework. This framework requires the so-called restricted Gaussian oracle, which can be viewed as a sampling counterpart of the proximal mapping in convex optimization. One key contribution of this work is a fast algorithm that realizes the restricted Gaussian oracle for any convex non-smooth potential with bounded Lipschitz constant.