The Sample Complexity of Approximate Rejection Sampling with Applications to Smoothed Online Learning
This work addresses a theoretical limitation in sampling theory and extends robustness in online learning, though it is incremental in building on prior bounded Radon-Nikodym derivative results.
The paper tackles the problem of approximate rejection sampling from distributions with bounded f-divergence, establishing an optimal total variation distance of ϔ(D/f'(n)) as a function of sample size n. It applies this result to smoothed online learning, showing that recent regret bounds hold under relaxed adversary constraints.
Suppose we are given access to $n$ independent samples from distribution $μ$ and we wish to output one of them with the goal of making the output distributed as close as possible to a target distribution $ν$. In this work we show that the optimal total variation distance as a function of $n$ is given by $\tildeΘ(\frac{D}{f'(n)})$ over the class of all pairs $ν,μ$ with a bounded $f$-divergence $D_f(ν\|μ)\leq D$. Previously, this question was studied only for the case when the Radon-Nikodym derivative of $ν$ with respect to $μ$ is uniformly bounded. We then consider an application in the seemingly very different field of smoothed online learning, where we show that recent results on the minimax regret and the regret of oracle-efficient algorithms still hold even under relaxed constraints on the adversary (to have bounded $f$-divergence, as opposed to bounded Radon-Nikodym derivative). Finally, we also study efficacy of importance sampling for mean estimates uniform over a function class and compare importance sampling with rejection sampling.