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.

19 pages, 4 figures

References in corpus (3)

• Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry
• Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm
• Random Coordinate Langevin Monte Carlo