The query complexity of sampling from strongly log-concave distributions in one dimension
This addresses a fundamental computational bottleneck in sampling for machine learning and statistics, providing optimal bounds for a specific class of distributions.
The paper tackled the problem of sampling from strongly log-concave distributions in one dimension, establishing a tight lower bound of Ω(log log κ) on query complexity and introducing a rejection sampling algorithm that closes a doubly exponential gap compared to existing MCMC methods.
We establish the first tight lower bound of $Ω(\log\logκ)$ on the query complexity of sampling from the class of strongly log-concave and log-smooth distributions with condition number $κ$ in one dimension. Whereas existing guarantees for MCMC-based algorithms scale polynomially in $κ$, we introduce a novel algorithm based on rejection sampling that closes this doubly exponential gap.