mlsanityData to 7 Oct 2026

Fisher information lower bounds for sampling

arXiv 2210.02482 ↗First posted 5 Oct 2022stat.ML cs.LG math.STcited by 12

Not on the map. Why?

Abstract (arXiv)

We prove two lower bounds for the complexity of non-log-concave sampling within the framework of Balasubramanian et al. (2022), who introduced the use of Fisher information (FI) bounds as a notion of approximate first-order stationarity in sampling. Our first lower bound shows that averaged LMC is optimal for the regime of large FI by reducing the problem of finding stationary points in non-convex optimization to sampling. Our second lower bound shows that in the regime of small FI, obtaining a FI of at most varepsilon2 from the target distribution requires poly(1/varepsilon) queries, which is surprising as it rules out the existence of high-accuracy algorithms (e.g., algorithms using Metropolis-Hastings filters) in this context.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 31 of its 50 references that are in the map. First posted on arXiv 5 Oct 2022.

Builds on

31 of 50 references.

References · 31

  1. 2014Convex Optimization: Algorithms and Complexitycited by 569
  2. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 224
  3. 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 195
  4. 2022Convergence of score-based generative modeling for general data distributionscited by 179
  5. 2022Convergence for score-based generative modeling with polynomial complexitycited by 176
  6. 2016High-dimensional Bayesian inference via the Unadjusted Langevin Algorithmcited by 144
  7. 2017Underdamped Langevin MCMC: A non-asymptotic analysiscited by 131
  8. 2017Lower Bounds for Finding Stationary Points Icited by 125
  9. 2018Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problemcited by 123
  10. 2017Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimizationcited by 96
  11. 2022Improved analysis for a proximal algorithm for samplingcited by 72
  12. 2018Sharp convergence rates for Langevin dynamics in the nonconvex settingcited by 67
19 more
  1. 2022Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlocited by 63
  2. 2020Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithmcited by 57
  3. 2017Lower Bounds for Finding Stationary Points II: First-Order Methodscited by 55
  4. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 55
  5. 2020On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothnesscited by 55
  6. 2022Private Convex Optimization via Exponential Mechanismcited by 47
  7. 2021Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Samplingcited by 44
  8. 2018Non-asymptotic bounds for sampling algorithms without log-concavitycited by 35
  9. 2017Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlocited by 33
  10. 2019Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyondcited by 33
  11. 2020Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Samplingcited by 32
  12. 2019Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetrycited by 31
  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. 2022On the complexity of finding stationary points of smooth functions in one dimensioncited by 8
  17. 2020Oracle Lower Bounds for Stochastic Gradient Sampling Algorithmscited by 7
  18. 2022Heavy-tailed Sampling via Transformed Unadjusted Langevin Algorithmcited by 6
  19. 2020How to trap a gradient flowcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 3; 2024: 3; 2025: 1; 2026: 4.

12 papers.

  1. 2023Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequalitycited by 31
  2. 2024Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Samplingcited by 23
  3. 2022Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Samplingcited by 21
  4. 2023Query lower bounds for log-concave samplingcited by 12
  5. 2025Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequalitycited by 11
  6. 2023Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimationcited by 10
  7. 2024A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplerscited by 5
  8. 2024Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature and Bayesian Optimizationcited by 2
  9. 2026Query Lower Bounds for Diffusion Samplingcited by 2
  10. 2026Complexity of Non-Log-Concave Sampling in Fisher Informationcited by 0
  11. 2026Smoothed Score Queries and the Complexity of Samplingcited by 0
  12. 2026Provable Quantum-Classical Separation for Continuous Gibbs Samplingcited by 0