Rejection sampling from shape-constrained distributions in sublinear time

Sinho Chewi, Patrik R. Gerber, Chen Lu, Thibaut Le Gouic, Philippe Rigollet
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:2249-2265, 2022.

Abstract

We consider the task of generating exact samples from a target distribution, known up to normalization, over a finite alphabet. The classical algorithm for this task is rejection sampling, and although it has been used in practice for decades, there is surprisingly little study of its fundamental limitations. In this work, we study the query complexity of rejection sampling in a minimax framework for various classes of discrete distributions. Our results provide new algorithms for sampling whose complexity scales sublinearly with the alphabet size. When applied to adversarial bandits, we show that a slight modification of the EXP3 algorithm reduces the per-iteration complexity from O(K) to O(log(K) log(K/\ensuremath{\delta})) with probability 1-\ensuremath{\delta}, where K is the number of arms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-chewi22a, title = { Rejection sampling from shape-constrained distributions in sublinear time }, author = {Chewi, Sinho and Gerber, Patrik R. and Lu, Chen and Le Gouic, Thibaut and Rigollet, Philippe}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {2249--2265}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/chewi22a/chewi22a.pdf}, url = {https://proceedings.mlr.press/v151/chewi22a.html}, abstract = { We consider the task of generating exact samples from a target distribution, known up to normalization, over a finite alphabet. The classical algorithm for this task is rejection sampling, and although it has been used in practice for decades, there is surprisingly little study of its fundamental limitations. In this work, we study the query complexity of rejection sampling in a minimax framework for various classes of discrete distributions. Our results provide new algorithms for sampling whose complexity scales sublinearly with the alphabet size. When applied to adversarial bandits, we show that a slight modification of the EXP3 algorithm reduces the per-iteration complexity from O(K) to O(log(K) log(K/\ensuremath{\delta})) with probability 1-\ensuremath{\delta}, where K is the number of arms. } }
Endnote
%0 Conference Paper %T Rejection sampling from shape-constrained distributions in sublinear time %A Sinho Chewi %A Patrik R. Gerber %A Chen Lu %A Thibaut Le Gouic %A Philippe Rigollet %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-chewi22a %I PMLR %P 2249--2265 %U https://proceedings.mlr.press/v151/chewi22a.html %V 151 %X We consider the task of generating exact samples from a target distribution, known up to normalization, over a finite alphabet. The classical algorithm for this task is rejection sampling, and although it has been used in practice for decades, there is surprisingly little study of its fundamental limitations. In this work, we study the query complexity of rejection sampling in a minimax framework for various classes of discrete distributions. Our results provide new algorithms for sampling whose complexity scales sublinearly with the alphabet size. When applied to adversarial bandits, we show that a slight modification of the EXP3 algorithm reduces the per-iteration complexity from O(K) to O(log(K) log(K/\ensuremath{\delta})) with probability 1-\ensuremath{\delta}, where K is the number of arms.
APA
Chewi, S., Gerber, P.R., Lu, C., Le Gouic, T. & Rigollet, P.. (2022). Rejection sampling from shape-constrained distributions in sublinear time . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:2249-2265 Available from https://proceedings.mlr.press/v151/chewi22a.html.

Related Material