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

Sinho Chewi, Patrik R Gerber, Chen Lu, Thibaut Le Gouic, Philippe Rigollet
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:2041-2059, 2022.

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 this Paper

BibTeX
@InProceedings{pmlr-v178-chewi22b, 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 Gouic, Thibaut Le and Rigollet, Philippe}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {2041--2059}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/chewi22b/chewi22b.pdf}, url = {https://proceedings.mlr.press/v178/chewi22b.html}, 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.} }
Endnote
%0 Conference Paper %T The query complexity of sampling from strongly log-concave distributions in one dimension %A Sinho Chewi %A Patrik R Gerber %A Chen Lu %A Thibaut Le Gouic %A Philippe Rigollet %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-chewi22b %I PMLR %P 2041--2059 %U https://proceedings.mlr.press/v178/chewi22b.html %V 178 %X 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.
APA
Chewi, S., Gerber, P.R., Lu, C., Gouic, T.L. & Rigollet, P.. (2022). The query complexity of sampling from strongly log-concave distributions in one dimension. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:2041-2059 Available from https://proceedings.mlr.press/v178/chewi22b.html.

Related Material