# An Efficient Sampling Algorithm for Non-smooth Composite Potentials

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Oct 2019.

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

- [Improved dimension dependence of a proximal algorithm for sampling](https://mlsanity.com/paper/2302.10081/) (2023)
- [A Proximal Algorithm for Sampling from Non-smooth Potentials](https://mlsanity.com/paper/2110.04597/) (2021)
- [A Proximal Algorithm for Sampling](https://mlsanity.com/paper/2202.13975/) (2022)
- [When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint](https://mlsanity.com/paper/2110.01827/) (2021)
- [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)
- [NF-ULA: Langevin Monte Carlo with Normalizing Flow Prior for Imaging Inverse Problems](https://mlsanity.com/paper/2304.08342/) (2023)
- [Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms](https://mlsanity.com/paper/2305.15988/) (2023)
- [Fast Score-Based Sampling via Log-Concave Reductions](https://mlsanity.com/paper/2512.24152/) (2025)
- [Anchored Langevin Algorithms](https://mlsanity.com/paper/2509.19455/) (2025)
- [A Proximal Algorithm for Sampling from Non-convex Potentials](https://mlsanity.com/paper/2205.10188/) (2022)
- [Stochastic Langevin Differential Inclusions with Applications to Machine Learning](https://mlsanity.com/paper/2206.11533/) (2022)
- [Active-Trace Complexity Bounds for Moreau--Yosida Unadjusted Langevin Sampling](https://mlsanity.com/paper/2608.13467/) (2026)
- [A proximal gradient algorithm for composite log-concave sampling](https://mlsanity.com/paper/2605.12461/) (2026)
- [Poisson-Corrector Complexity Bounds for Moreau--Yosida Unadjusted Langevin Sampling](https://mlsanity.com/paper/2609.12594/) (2026)
- [Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo](https://mlsanity.com/paper/2102.13068/) (2021)
- [Nuclear Norm-Regularized Bayesian Matrix Completion](https://mlsanity.com/paper/2609.30078/) (2026)

## Abstract (arXiv)

We consider the problem of sampling from a density of the form p(x) propto exp(-f(x)- g(x)), where f: ℝd rightarrow ℝ is a smooth and strongly convex function and g: ℝd rightarrow ℝ is a convex and Lipschitz function. We propose a new algorithm based on the Metropolis-Hastings framework, and prove that it mixes to within TV distance varepsilon of the target density in at most O(d log (d/varepsilon)) iterations. This guarantee extends previous results on sampling from distributions with smooth log densities (g = 0) to the more general composite non-smooth case, with the same mixing time up to a multiple of the condition number. Our method is based on a novel proximal-based proposal distribution that can be efficiently computed for a large class of non-smooth functions g.