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 li...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-05
Main Authors: Chewi, Sinho, Gerber, Patrik, Chen, Lu, Thibaut Le Gouic, Rigollet, Philippe
Format: Article
Language:English
Subjects:
Algorithms
Alphabets
Complexity
Minimax technique
Rejection
Sampling
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 \(\mathcal O(K)\) to \(\mathcal O(\log^2 K)\), where \(K\) is the number of arms.
ISSN:2331-8422