mlsanityData to 7 Oct 2026

A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers

arXiv 2405.16736 ↗First posted 27 May 2024math.ST stat.ML stat.THcited by 5

Not on the map. Why?

Abstract (arXiv)

We study the complexity of heavy-tailed sampling and present a separation result in terms of obtaining high-accuracy versus low-accuracy guarantees i.e., samplers that require only O(log(1/varepsilon)) versus Omega(poly(1/varepsilon)) iterations to output a sample which is varepsilon-close to the target in chi2-divergence. Our results are presented for proximal samplers that are based on Gaussian versus stable oracles. We show that proximal samplers based on the Gaussian oracle have a fundamental barrier in that they necessarily achieve only low-accuracy guarantees when sampling from a class of heavy-tailed targets. In contrast, proximal samplers based on the stable oracle exhibit high-accuracy guarantees, thereby overcoming the aforementioned limitation. We also prove lower bounds for samplers under the stable oracle and show that our upper bounds cannot be fundamentally improved.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 36 of its 64 references that are in the map. First posted on arXiv 27 May 2024.

Builds on

36 of 64 references.

References · 36

  1. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 242
  2. 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 195
  3. 2017Underdamped Langevin MCMC: A non-asymptotic analysiscited by 131
  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. 2020Structured Logconcave Sampling with a Restricted Gaussian Oraclecited by 85
  7. 2019The Randomized Midpoint Method for Log-Concave Samplingcited by 77
  8. 2022Improved analysis for a proximal algorithm for samplingcited by 72
  9. 2022Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlocited by 63
  10. 2018On sampling from a log-concave density using kinetic Langevin diffusionscited by 61
  11. 2020Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithmcited by 57
  12. 2020On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothnesscited by 55
24 more
  1. 2020Learning Halfspaces with Massart Noise Under Structured Distributionscited by 45
  2. 2018Global Non-convex Optimization with Discretized Diffusionscited by 44
  3. 2021Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Samplingcited by 44
  4. 2020Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergencecited by 42
  5. 2019Improved Bounds for Discretization of Langevin Diffusions: Near-Optimal Rates without Convexitycited by 38
  6. 2019Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyondcited by 33
  7. 2020Fractional Underdamped Langevin Dynamics: Retargeting SGD with Momentum under Heavy-Tailed Gradient Noisecited by 33
  8. 2023Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequalitycited by 31
  9. 2023Improved dimension dependence of a proximal algorithm for samplingcited by 29
  10. 2021Sqrt(d) Dimension Dependence of Langevin Monte Carlocited by 25
  11. 2020On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Methodcited by 23
  12. 2020Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlocited by 22
  13. 2021Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributionscited by 19
  14. 2021The query complexity of sampling from strongly log-concave distributions in one dimensioncited by 18
  15. 2019Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Boundscited by 16
  16. 2022Fisher information lower bounds for samplingcited by 12
  17. 2023Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Samplercited by 9
  18. 2019Non-Asymptotic Analysis of Fractional Langevin Monte Carlo for Non-Convex Optimizationcited by 8
  19. 2020Oracle Lower Bounds for Stochastic Gradient Sampling Algorithmscited by 7
  20. 2023A Simple Proof of the Mixing of Metropolis-Adjusted Langevin Algorithm under Smoothness and Isoperimetrycited by 7
  21. 2022Stereographic Markov Chain Monte Carlocited by 6
  22. 2014Efficient strategy for the Markov chain Monte Carlo in high-dimension with heavy-tailed target probability distributioncited by 5
  23. 2021Comparison of Markov chains via weak Poincar'e inequalities with application to pseudo-marginal MCMCcited by 5
  24. 2015On the Use of Cauchy Prior Distributions for Bayesian Logistic Regressioncited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 2.

5 papers.

  1. 2025On the query complexity of sampling from non-log-concave distributionscited by 5
  2. 2025Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributionscited by 1
  3. 2025R'enyi Differential Privacy for Heavy-Tailed SDEs via Fractional Poincar'e Inequalitiescited by 0
  4. 2026Functional Stochastic Localizationcited by 0
  5. 2026Local Geometric Mixing via Dobrushin Contraction with Applications to Diffusion Path Monte Carlo and the Proximal Samplercited by 0