2022-05-03-chewi22a.md

title	abstract	software	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Rejection sampling from shape-constrained distributions in sublinear time	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.	https://github.com/PatrikGerber/Rejection-sampling	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	chewi22a	0	Rejection sampling from shape-constrained distributions in sublinear time	2249	2265	2249-2265	2249	false	Chewi, Sinho and Gerber, Patrik R. and Lu, Chen and Le Gouic, Thibaut and Rigollet, Philippe	given family Sinho Chewi given family Patrik R. Gerber given family Chen Lu given family Thibaut Le Gouic given family Philippe Rigollet	2022-05-03		Proceedings of The 25th International Conference on Artificial Intelligence and Statistics	151	inproceedings	date-parts 2022 5 3	https://proceedings.mlr.press/v151/chewi22a/chewi22a.pdf