Research map / Optimization / Nonconvex and smooth optimization
Faster Sampling via Stochastic Gradient Proximal Sampler
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Stochastic Proximal Samplers (SPS) that run stochastic-gradient inner samplers (SGLD or warm-started MALA) for the restricted Gaussian oracle, giving TV-convergence gradient complexities of Õ(dε⁻²) and Õ(d^{1/2}ε⁻²) for non-log-concave LSI targets.
Problem
Sampling from non-log-concave finite-sum target distributions with stochastic gradients while retaining the fast convergence of the proximal sampler, which previously required full gradients and stationary-point information.
Approach
Replace the joint target with a mini-batch-randomized joint distribution and alternate an exact Gaussian step with an inexact stochastic inner sampler (SGLD or warm-started MALA) for the restricted Gaussian oracle; the analysis controls error via second moments rather than stationary points of f.
Key results
- SPS-SGLD achieves Õ(dε⁻²) gradient complexity and SPS-MALA Õ(d^{1/2}ε⁻²), versus Õ(d^{4/3}ε⁻²) for CC-SGLD, a factor of at least Õ(d^{1/3}) improvement.
- On synthetic mixtures with d from 10 to 50, the optimal TV distance of SPS-SGLD is at least 0.5 smaller than that of SGLD across all dimensions tested.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SPS-SGLD instead of CC-SGLD | Stochastic proximal sampling · LSI, finite-sum, component-smooth targets | TV gradient complexity: at least an \tilde{\mathcal{O}}(d^{1/3}) factor | Helped |
| Use SPS-MALA instead of SPS-SGLD as the inner sampler | Stochastic proximal sampler · LSI, finite-sum, component-smooth targets | TV gradient complexity: d\epsilon^{-2} -> d^{1/2}\epsilon^{-2} | Helped |
| Use SPS-SGLD instead of vanilla SGLD | Sampling on synthetic data · Synthetic data, dimensions 10, 20, 30, 40, 50 | TV distance: at least 0.5 smaller | Helped |
Limitations
- Experiments only on small synthetic mixture targets with d up to 50 and only SPS-SGLD is empirically tested
- SPS-MALA gradient complexity degrades with variance sigma^2 through mini-batch size
- Analysis requires LSI and component smoothness assumptions and an extra kappa factor over full-batch stationary-point-based results
Experimental setup
Datasets: synthetic Gaussian mixture target (n=100 components, d in 10-50)
Benchmarks: synthetic mixture sampling task
Metrics: total variation distance (marginal estimate) gradient complexity
Baselines: SGLD CC-SGLD AB-SGLD
Builds on: proximal sampler SGLD MALA CC-SGLD
Closest papers by meaning
- Stochastic Proximal Langevin Algorithm: Potential Splitting and Nonasymptotic Rates (NeurIPS 2019 · similarity 0.93)
- Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin Algorithm (NeurIPS 2020 · similarity 0.90)
- Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization (NeurIPS 2022 · similarity 0.89)
- Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel (ICLR 2025 · similarity 0.87)
- From stability of Langevin diffusion to convergence of proximal MCMC for non-log-concave sampling (NeurIPS 2025 · similarity 0.87)
- Non-asymptotic Error Bounds in $\mathcal{W}_2$-Distance with Sqrt(d) Dimension Dependence and First Order Convergence for Langevin Monte Carlo beyond Log-Concavity (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.