  Suppose we are given access to $n$ independent samples from distribution
$\mu$ and we wish to output one of them with the goal of making the output
distributed as close as possible to a target distribution $\nu$. In this work
we show that the optimal total variation distance as a function of $n$ is given
by $\tilde\Theta(\frac{D}{f'(n)})$ over the class of all pairs $\nu,\mu$ with a
bounded $f$-divergence $D_f(\nu\|\mu)\leq D$. Previously, this question was
studied only for the case when the Radon-Nikodym derivative of $\nu$ with
respect to $\mu$ 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.

Machine Learning;Machine Learning