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.
Cite
Text
Chewi et al. "The Query Complexity of Sampling from Strongly Log-Concave Distributions in One Dimension." Conference on Learning Theory, 2022.Markdown
[Chewi et al. "The Query Complexity of Sampling from Strongly Log-Concave Distributions in One Dimension." Conference on Learning Theory, 2022.](https://mlanthology.org/colt/2022/chewi2022colt-query/)BibTeX
@inproceedings{chewi2022colt-query,
title = {{The Query Complexity of Sampling from Strongly Log-Concave Distributions in One Dimension}},
author = {Chewi, Sinho and Gerber, Patrik R and Lu, Chen and Le Gouic, Thibaut and Rigollet, Philippe},
booktitle = {Conference on Learning Theory},
year = {2022},
pages = {2041-2059},
volume = {178},
url = {https://mlanthology.org/colt/2022/chewi2022colt-query/}
}