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

Abstract

We establish the first tight lower bound of $\Omega (\log \log \kappa )$ 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.

arXiv comment19 pages, 4 figures

References in corpus (6)

• Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
• The Randomized Midpoint Method for Log-Concave Sampling
• Complexity of randomized algorithms for underdamped Langevin dynamics
• Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry
• Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm
• Random Coordinate Langevin Monte Carlo