mlsanityData to 7 Oct 2026

Query lower bounds for log-concave sampling

arXiv 2304.02599 ↗First posted 5 Apr 2023math.ST cs.DS cs.LGcited by 12

Not on the map. Why?

Abstract (arXiv)

Log-concave sampling has witnessed remarkable algorithmic advances in recent years, but the corresponding problem of proving lower bounds for this task has remained elusive, with lower bounds previously known only in dimension one. In this work, we establish the following query lower bounds: (1) sampling from strongly log-concave and log-smooth distributions in dimension d≥ 2 requires Omega(log kappa) queries, which is sharp in any constant dimension, and (2) sampling from Gaussians in dimension d (hence also from general log-concave and log-smooth distributions in dimension d) requires widetilde Omega(min(√kappa log d, d)) queries, which is nearly sharp for the class of Gaussians. Here kappa denotes the condition number of the target distribution. Our proofs rely upon (1) a multiscale construction inspired by work on the Kakeya conjecture in geometric measure theory, and (2) a novel reduction that demonstrates that block Krylov algorithms are optimal for this problem, as well as connections to lower bound techniques based on Wishart matrices developed in the matrix-vector query literature.

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

Builds on

53 of 96 references.

References · 53

  1. 2014Convex Optimization: Algorithms and Complexitycited by 569
  2. 2014Sketching as a Tool for Numerical Linear Algebracited by 285
  3. 2019Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Sufficescited by 224
  4. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 206
  5. 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 195
  6. 2017Underdamped Langevin MCMC: A non-asymptotic analysiscited by 131
  7. 2018Analysis of Langevin Monte Carlo via convex optimizationcited by 126
  8. 2018Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problemcited by 123
  9. 2018Log-concave sampling: Metropolis-Hastings algorithms are fastcited by 117
  10. 2017User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradientcited by 116
  11. 2020Structured Logconcave Sampling with a Restricted Gaussian Oraclecited by 85
  12. 2019The Randomized Midpoint Method for Log-Concave Samplingcited by 77
38 more
  1. 2022Improved analysis for a proximal algorithm for samplingcited by 72
  2. 2015Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decompositioncited by 63
  3. 2022Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlocited by 63
  4. 2020Hutch++: Optimal Stochastic Trace Estimationcited by 62
  5. 2018On sampling from a log-concave density using kinetic Langevin diffusionscited by 61
  6. 2020Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithmcited by 57
  7. 2020Wasserstein Control of Mirror Langevin Monte Carlocited by 55
  8. 2020Efficient constrained sampling via the mirror-Langevin algorithmcited by 55
  9. 2019Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradientscited by 51
  10. 2022Private Convex Optimization via Exponential Mechanismcited by 47
  11. 2021Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Samplingcited by 44
  12. 2023Faster high-accuracy log-concave sampling via algorithmic warm startscited by 44
  13. 2020Exponential ergodicity of mirror-Langevin diffusionscited by 37
  14. 2021The Mirror Langevin Algorithm Converges with Vanishing Biascited by 37
  15. 2020Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin Algorithmcited by 34
  16. 2019Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetrycited by 31
  17. 2023Improved dimension dependence of a proximal algorithm for samplingcited by 29
  18. 2014Testing for high-dimensional geometry in random graphscited by 25
  19. 2022Convergence of the Riemannian Langevin Algorithmcited by 23
  20. 2020Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlocited by 22
  21. 2022Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Samplingcited by 21
  22. 2021Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributionscited by 19
  23. 2021The query complexity of sampling from strongly log-concave distributions in one dimensioncited by 18
  24. 2019Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Boundscited by 16
  25. 2022Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chainscited by 16
  26. 2022Fisher information lower bounds for samplingcited by 12
  27. 2018Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Lawcited by 11
  28. 2017Lower Bound for Randomized First Order Convex Optimizationcited by 9
  29. 2019The gradient complexity of linear regressioncited by 9
  30. 2021Sublinear Time Spectral Density Estimationcited by 9
  31. 2019Querying a Matrix through Matrix-Vector Productscited by 8
  32. 2020Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problemscited by 8
  33. 2017Approximating the Spectrum of a Graphcited by 7
  34. 2019Computational Separations between Sampling and Optimizationcited by 7
  35. 2020Oracle Lower Bounds for Stochastic Gradient Sampling Algorithmscited by 7
  36. 2020Random Coordinate Langevin Monte Carlocited by 7
  37. 2022Low-Rank Approximation with 1/ε1/3 Matrix-Vector Productscited by 7
  38. 2018Prior-preconditioned conjugate gradient method for accelerated Gibbs sampling in "large n & large p" Bayesian sparse regressioncited by 6

50 most cited of 53 All 53 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

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

12 papers.

  1. 2024Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Samplingcited by 23
  2. 2024Sharper Bounds for Chebyshev Moment Matching, with Applicationscited by 3
  3. 2023Krylov Methods are (nearly) Optimal for Low-Rank Approximationcited by 2
  4. 2026High-accuracy log-concave sampling with stochastic queriescited by 2
  5. 2026Query Lower Bounds for Diffusion Samplingcited by 2
  6. 2025Limits of quantum generative models with classical sampling hardnesscited by 1
  7. 2026Windowed thinning and query complexity for the bouncy particle and Zigzag samplerscited by 1
  8. 2025Lower bounds for trace estimation via Block Krylov and other methodscited by 0
  9. 2025Query Efficient Structured Matrix Learningcited by 0
  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