mlsanityData to 7 Oct 2026

Mean-Square Analysis of Discretized Ito Diffusions for Heavy-tailed Sampling

arXiv 2303.00570 ↗First posted 1 Mar 2023math.ST cs.LG cs.NAcited by 4

Not on the map. Why?

Abstract (arXiv)

We analyze the complexity of sampling from a class of heavy-tailed distributions by discretizing a natural class of Ito diffusions associated with weighted Poincar'e inequalities. Based on a mean-square analysis, we establish the iteration complexity for obtaining a sample whose distribution is ε close to the target distribution in the Wasserstein-2 metric. In this paper, our results take the mean-square analysis to its limits, i.e., we invariably only require that the target density has finite variance, the minimal requirement for a mean-square analysis. To obtain explicit estimates, we compute upper bounds on certain moments associated with heavy-tailed targets under various assumptions. We also provide similar iteration complexity results for the case where only function evaluations of the unnormalized target density are available by estimating the gradients using a Gaussian smoothing technique. We provide illustrative examples based on the multivariate t-distribution.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 41 of its 88 references that are in the map. First posted on arXiv 1 Mar 2023.

Builds on

41 of 88 references.

References · 41

  1. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 224
  2. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 206
  3. 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 195
  4. 2018Analysis of Langevin Monte Carlo via convex optimizationcited by 126
  5. 2018Log-concave sampling: Metropolis-Hastings algorithms are fastcited by 117
  6. 2017User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradientcited by 116
  7. 2020Structured Logconcave Sampling with a Restricted Gaussian Oraclecited by 85
  8. 2019The Randomized Midpoint Method for Log-Concave Samplingcited by 77
  9. 2022Improved analysis for a proximal algorithm for samplingcited by 72
  10. 2022Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlocited by 63
  11. 2018Mirrored Langevin Dynamicscited by 61
  12. 2018On sampling from a log-concave density using kinetic Langevin diffusionscited by 61
29 more
  1. 2020Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithmcited by 57
  2. 2020Wasserstein Control of Mirror Langevin Monte Carlocited by 55
  3. 2020On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothnesscited by 55
  4. 2020Efficient constrained sampling via the mirror-Langevin algorithmcited by 55
  5. 2019Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradientscited by 51
  6. 2020Learning Halfspaces with Massart Noise Under Structured Distributionscited by 45
  7. 2021Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Samplingcited by 44
  8. 2020Exponential ergodicity of mirror-Langevin diffusionscited by 37
  9. 2021The Mirror Langevin Algorithm Converges with Vanishing Biascited by 37
  10. 2018Coupling and Convergence for Hamiltonian Monte Carlocited by 36
  11. 2019Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyondcited by 33
  12. 2020Fractional Underdamped Langevin Dynamics: Retargeting SGD with Momentum under Heavy-Tailed Gradient Noisecited by 33
  13. 2019Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributionscited by 28
  14. 2016Measuring Sample Quality with Diffusionscited by 25
  15. 2020On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Methodcited by 23
  16. 2019Efficient MCMC Sampling with Dimension-Free Convergence Rate using ADMM-type Splittingcited by 22
  17. 2020Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlocited by 22
  18. 2020Riemannian Langevin Algorithm for Solving Semidefinite Programscited by 22
  19. 2016Auxiliary gradient-based sampling algorithmscited by 21
  20. 2019Bounding the error of discretized Langevin algorithms for non-strongly log-concave targetscited by 16
  21. 2019Non-Asymptotic Analysis of Fractional Langevin Monte Carlo for Non-Convex Optimizationcited by 8
  22. 2020Langevin Monte Carlo: random coordinate descent and variance reductioncited by 7
  23. 2022Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Timecited by 7
  24. 2022Heavy-tailed Sampling via Transformed Unadjusted Langevin Algorithmcited by 6
  25. 2022Stereographic Markov Chain Monte Carlocited by 6
  26. 2014Efficient strategy for the Markov chain Monte Carlo in high-dimension with heavy-tailed target probability distributioncited by 5
  27. 2020Complexity of zigzag sampling algorithm for strongly log-concave distributionscited by 5
  28. 2021Comparison of Markov chains via weak Poincar'e inequalities with application to pseudo-marginal MCMCcited by 5
  29. 2015On the Use of Cauchy Prior Distributions for Bayesian Logistic Regressioncited by 4

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 1; 2025: 2.

4 papers.

  1. 2023Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequalitycited by 31
  2. 2024Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusioncited by 19
  3. 2025Anchored Langevin Algorithmscited by 2
  4. 2025Sampling by averaging: A multiscale approach to score estimationcited by 1