mlsanityData to 14 Oct 2026

The query complexity of sampling from strongly log-concave distributions in one dimension

arXiv 2105.14163 ↗First posted 29 May 2021math.ST cs.LG stat.THcited by 18

Not on the map. Why?

Abstract (arXiv)

We establish the first tight lower bound of Omega(loglogkappa) on the query complexity of sampling from the class of strongly log-concave and log-smooth distributions with condition number kappa in one dimension. Whereas existing guarantees for MCMC-based algorithms scale polynomially in kappa, we introduce a novel algorithm based on rejection sampling that closes this doubly exponential gap.

Key facts. Cited by 18 papers in the map (data through 14 Oct 2026). Builds on 14 of its 36 references that are in the map. First posted on arXiv 29 May 2021.

Builds on

14 of 36 references.

References · 14

  1. 2014Convex Optimization: Algorithms and Complexitycited by 575
  2. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 208
  3. 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 197
  4. 2018Analysis of Langevin Monte Carlo via convex optimizationcited by 127
  5. 2018Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problemcited by 123
  6. 2017User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradientcited by 116
  7. 2019The Randomized Midpoint Method for Log-Concave Samplingcited by 78
  8. 2020Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithmcited by 57
  9. 2020Exponential ergodicity of mirror-Langevin diffusionscited by 37
  10. 2019Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetrycited by 34
  11. 2019Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Boundscited by 16
  12. 2020Oracle Lower Bounds for Stochastic Gradient Sampling Algorithmscited by 8
2 more
  1. 2020Random Coordinate Langevin Monte Carlocited by 7
  2. 2020Random Coordinate Underdamped Langevin Monte Carlocited by 6

Built on by

Cited by year (2026 to 14 Oct)

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

18 papers.

Sort:

By area:

  1. 2022Improved analysis for a proximal algorithm for samplingcited by 73
  2. 2022Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlocited by 63
  3. 2023Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequalitycited by 31
  4. 2023Improved dimension dependence of a proximal algorithm for samplingcited by 30
  5. 2022Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Samplingcited by 22
  6. 2024Entropy contraction of the Gibbs sampler under log-concavitycited by 13
  7. 2022Fisher information lower bounds for samplingcited by 12
  8. 2023Query lower bounds for log-concave samplingcited by 12
  9. 2025Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequalitycited by 12
  10. 2024Fast Convergence of Phi-Divergence Along the Unadjusted Langevin Algorithm and Proximal Samplercited by 11
  11. 2023Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimationcited by 10
  12. 2024A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplerscited by 6
6 more
  1. 2024Characterizing Dependence of Samples along the Langevin Dynamics and Algorithms via Contraction of Phi-Mutual Informationcited by 5
  2. 2025Gradient Flow Sampler-based Distributionally Robust Optimizationcited by 2
  3. 2026High-accuracy log-concave sampling with stochastic queriescited by 2
  4. 2026Query Lower Bounds for Diffusion Samplingcited by 2
  5. 2026Smoothed Score Queries and the Complexity of Samplingcited by 0
  6. 2026Provable Quantum-Classical Separation for Continuous Gibbs Samplingcited by 0