# Faster Sampling via Stochastic Gradient Proximal Sampler

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 49 references that are in the map.
- First posted on arXiv 27 May 2024.

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

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Stochastic Gradient Hamiltonian Monte Carlo](https://mlsanity.com/paper/1402.4102/) (2014)
- [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)
- [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)
- [User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient](https://mlsanity.com/paper/1710.00095/) (2017)
- [Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/1707.06618/) (2017)
- [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)
- [Improved analysis for a proximal algorithm for sampling](https://mlsanity.com/paper/2202.06386/) (2022)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Coupling and Convergence for Hamiltonian Monte Carlo](https://mlsanity.com/paper/1805.00452/) (2018)
- [High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm](https://mlsanity.com/paper/1908.10859/) (2019)
- [Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling](https://mlsanity.com/paper/2010.09597/) (2020)
- [Langevin diffusions and the Metropolis-adjusted Langevin algorithm](https://mlsanity.com/paper/1309.2983/) (2013)
- [Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions](https://mlsanity.com/paper/1905.02313/) (2019)
- [A Proximal Algorithm for Sampling from Non-smooth Potentials](https://mlsanity.com/paper/2110.04597/) (2021)
- [Particle-based Variational Inference with Preconditioned Functional Gradient Flow](https://mlsanity.com/paper/2211.13954/) (2022)
- [Faster Sampling without Isoperimetry via Diffusion-based Monte Carlo](https://mlsanity.com/paper/2401.06325/) (2024)
- [Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions](https://mlsanity.com/paper/1708.07114/) (2017)
- [Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo](https://mlsanity.com/paper/1802.08898/) (2018)
- [Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities](https://mlsanity.com/paper/1812.06243/) (2018)
- [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)
- [Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms](https://mlsanity.com/paper/2206.03792/) (2022)

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

- [On the Robustness of Langevin Dynamics to Score Function Error](https://mlsanity.com/paper/2603.11319/) (2026)
- [High-accuracy log-concave sampling with stochastic queries](https://mlsanity.com/paper/2602.14342/) (2026)
- [Beyond Propagation of Chaos: A Stochastic Algorithm for Mean Field Optimization](https://mlsanity.com/paper/2503.13115/) (2025)
- [Langevin Dynamics: A Unified Perspective on Optimization via Lyapunov Potentials](https://mlsanity.com/paper/2407.04264/) (2024)
- [Local Geometric Mixing via Dobrushin Contraction with Applications to Diffusion Path Monte Carlo and the Proximal Sampler](https://mlsanity.com/paper/2609.28338/) (2026)

## Abstract (arXiv)

Stochastic gradients have been widely integrated into Langevin-based methods to improve their scalability and efficiency in solving large-scale sampling problems. However, the proximal sampler, which exhibits much faster convergence than Langevin-based algorithms in the deterministic setting Lee et al. (2021), has yet to be explored in its stochastic variants. In this paper, we study the Stochastic Proximal Samplers (SPS) for sampling from non-log-concave distributions. We first establish a general framework for implementing stochastic proximal samplers and establish the convergence theory accordingly. We show that the convergence to the target distribution can be guaranteed as long as the second moment of the algorithm trajectory is bounded and restricted Gaussian oracles can be well approximated. We then provide two implementable variants based on Stochastic gradient Langevin dynamics (SGLD) and Metropolis-adjusted Langevin algorithm (MALA), giving rise to SPS-SGLD and SPS-MALA. We further show that SPS-SGLD and SPS-MALA can achieve ε-sampling error in total variation (TV) distance within tildeO(dε-2) and tildeO(d1/2ε-2) gradient complexities, which outperform the best-known result by at least an tildeO(d1/3) factor. This enhancement in performance is corroborated by our empirical studies on synthetic data with various dimensions, demonstrating the efficiency of our proposed algorithm.