mlsanityData to 7 Oct 2026

A Proximal Algorithm for Sampling from Non-smooth Potentials

arXiv 2110.04597 ↗First posted 9 Oct 2021cs.LG math.OCcited by 23

Not on the map. Why?

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.

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

Builds on

23 of 51 references.

References · 23

  1. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 206
  2. 2017Underdamped Langevin MCMC: A non-asymptotic analysiscited by 131
  3. 2018Analysis of Langevin Monte Carlo via convex optimizationcited by 126
  4. 2018Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problemcited by 123
  5. 2018Log-concave sampling: Metropolis-Hastings algorithms are fastcited by 117
  6. 2017Convergence of Langevin MCMC in KL-divergencecited by 86
  7. 2020Structured Logconcave Sampling with a Restricted Gaussian Oraclecited by 85
  8. 2016Efficient Bayesian computation by proximal Markov chain Monte Carlo: when Langevin meets Moreaucited by 83
  9. 2019The Randomized Midpoint Method for Log-Concave Samplingcited by 77
  10. 2019Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradientscited by 51
  11. 2017Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computationcited by 32
  12. 2019Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetrycited by 31
11 more
  1. 2019Langevin Monte Carlo without smoothnesscited by 27
  2. 2021The Langevin Monte Carlo algorithm in the non-smooth log-concave casecited by 26
  3. 2019Efficient MCMC Sampling with Dimension-Free Convergence Rate using ADMM-type Splittingcited by 22
  4. 2019An Efficient Sampling Algorithm for Non-smooth Composite Potentialscited by 19
  5. 2017Fast MCMC sampling algorithms on polytopescited by 17
  6. 2016Eldan's Stochastic Localization and the KLS Conjecture: Isoperimetry, Concentration and Mixingcited by 13
  7. 2021When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpointcited by 12
  8. 2020Composite Logconcave Sampling with a Restricted Gaussian Oraclecited by 8
  9. 2020A proximal bundle variant with optimal iteration-complexity for a large range of prox stepsizescited by 7
  10. 2021A unified analysis of a class of proximal bundle methods for solving hybrid convex composite optimization problemscited by 7
  11. 2020Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimizationcited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 6; 2023: 6; 2024: 5; 2025: 2; 2026: 4.

23 papers.

Sort:

By area:

  1. 2023The probability flow ODE is provably fastcited by 145
  2. 2022Improved analysis for a proximal algorithm for samplingcited by 72
  3. 2022Private Convex Optimization via Exponential Mechanismcited by 47
  4. 2023Faster high-accuracy log-concave sampling via algorithmic warm startscited by 44
  5. 2023Improved dimension dependence of a proximal algorithm for samplingcited by 29
  6. 2024Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Samplingcited by 23
  7. 2022A Proximal Algorithm for Samplingcited by 21
  8. 2022Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Samplingcited by 21
  9. 2023Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Riskscited by 12
  10. 2025Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequalitycited by 11
  11. 2024Fast Convergence of Phi-Divergence Along the Unadjusted Langevin Algorithm and Proximal Samplercited by 10
  12. 2023Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Samplercited by 9
11 more
  1. 2022Bregman Proximal Langevin Monte Carlo via Bregman--Moreau Envelopescited by 7
  2. 2024Characterizing Dependence of Samples along the Langevin Dynamics and Algorithms via Contraction of Phi-Mutual Informationcited by 5
  3. 2024Proximal Oracles for Optimization and Samplingcited by 5
  4. 2024Faster Sampling via Stochastic Gradient Proximal Samplercited by 5
  5. 2023Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithmscited by 4
  6. 2025Oracle-based Uniform Sampling from Convex Bodiescited by 3
  7. 2022A Proximal Algorithm for Sampling from Non-convex Potentialscited by 2
  8. 2026Alternating Diffusion for Proximal Sampling with Zeroth Order Queriescited by 1
  9. 2026Functional Stochastic Localizationcited by 0
  10. 2026The Geometry of Efficient Nonconvex Samplingcited by 0
  11. 2026Local Geometric Mixing via Dobrushin Contraction with Applications to Diffusion Path Monte Carlo and the Proximal Samplercited by 0