# The Sample Complexity of Approximate Rejection Sampling with Applications to
Smoothed Online Learning

Adam Block and Yury Polyanskiy
MIT

###### Abstract

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^{\prime}(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.

##  1 Introduction

Consider the following problem: given $n$ independent samples from some base
distribution $\mu$, how can a learner generate a single sample from a target
distribution $\nu$? This simple question dates back decades, with the first
formal solution, rejection sampling, provided already by Von Neumann (1951).
Due to its simplicity, this sampling problem appears as a primitive in
numerous applications in machine learning, theoretical computer science, and
cryptography (Lyubashevsky, 2012; Liu, 1996; Naesseth et al., 2017; Ozols et
al., 2013); thus, constructing efficient solutions has filled many works
(Grover et al., 2018; Gilks and Wild, 1992; Martino and Míguez, 2011). Perhaps
surprisingly, though, the original solution of rejection sampling (Von
Neumann, 1951) remains a popular method even today.

Given $X_{1},\dots,X_{n}\sim\mu$, recall that rejection sampling takes as a
parameter some $M$, which is a uniform upper bound on the Radon-Nikodym
derivative $\frac{d\nu}{d\mu}$, and for each $1\leq i\leq n$, accepts $X_{i}$
with probability $\frac{1}{M}\cdot\frac{d\nu}{d\mu}(X_{i})$ and returns an
arbitrary accepted $X_{i}$ as a sample from $\nu$. It is an easy exercise to
see that if $M\geq\left|\left|\frac{d\nu}{d\mu}\right|\right|_{\infty}$, then
any accepted sample has distribution $\nu$. Furthermore, it is not hard to see
that any sample gets accepted with probability $\frac{1}{M}$ independently of
other samples and thus, if we want to have at least one accepted sample with
high probability, we require $n=\Theta(M)$. While there has been quite a lot
of work in the information theory community dedicated to refining this bound
(Liu and Verdu, 2018; Harsha et al., 2007) as well as developments in the
statistical community dedicated to improving sampling efficiency under strong
structural assumptions (Gilks and Wild, 1992; Görür and Teh, 2011), the scope
of most all of this work is limited by the requirement that
$\left|\left|\frac{d\nu}{d\mu}\right|\right|_{\infty}<\infty$. In many
settings, this assumption is false (Block et al., 2023); as a result, we focus
on a similar problem without the stringent assumption on a uniform upper
bound. Unfortunately, it is not hard to see that there exist examples where we
simply cannot recover a sample exactly from $\nu$ without this uniform upper
bound (see Theorem 30 for an example). Consequently, we relax our desideratum
to consider approximate sampling. Specifically, we ask the following question:

> How many independent samples $X_{1},\dots,X_{n}$ do we need from a source
> distribution $\mu$ such that we can select some $j^{\ast}\in[n]$ in order
> for the law of $X_{j^{\ast}}$ to be within total variation distance
> $\varepsilon$ of $\nu$?

Despite its simplicity, to the best of our knowledge this question has not
been considered in the literature to date. We emphasize several special cases
in the related work in Appendix A. In this work we give a complete answer to
this question with essentially matching upper and lower bounds for all
superlinear $f$-divergences of practical interest. While the upper bounds are
achieved with a modified rejection sampler and the analysis follows without
too much difficulty from classical work, the lower bounds require a more
technical approach. In order to quantify how far apart $\nu$ is from $\mu$, we
use the information-theoretic notion of an $f$-divergence, where for two
measures $\nu\ll\mu$ defined on a common set and a convex function $f$, we
define

$\displaystyle
D_{f}\left(\nu||\mu\right)=\mathbb{E}_{\mu}\left[f\left(\frac{d\nu}{d\mu}(Z)\right)\right].$
(1)

We give a more formal definition below, but we observe here that the notion of
$f$-divergence generalizes common divergences including total variation, KL-
divergence, Renyi divergences, and $\mathcal{E}_{\gamma}$ divergence
(Polyanskiy and Wu, 2022+; Van Erven and Harremos, 2014; Asoodeh et al.,
2021). We will make the assumption that for some convex $f$, the source and
target measures satisfy $D_{f}\left(\nu||\mu\right)<\infty$ and ask what the
sample complexity of $\varepsilon$-approximate rejection sampling is under
this constraint. Interestingly, the answer depends on the tail behavior of
$f$; in particular, if $\sup f^{\prime}(x)<\infty$ then rejection sampling
cannot work under only this constraint (see Proposition 4). If we have an
$f$-divergence constraint with $f^{\prime}(\infty)=\infty$, however, we will
see that

$\displaystyle
n=\widetilde{\Theta}\left((f^{\prime})^{-1}\left(\frac{D_{f}\left(\nu||\mu\right)}{\varepsilon}\right)\right)$
(2)

samples is both necessary and sufficient in order to generate a sample
$X_{j^{\ast}}$ that is $\varepsilon$-close in total variation. In fact, we
show that von Neumann’s original rejection sampler is essentially optimal for
this problem and we do not require the more complicated samplers introduced
for exact sampling by Harsha et al. (2007); Liu and Verdu (2018). As mentioned
above, the upper bounds are relatively standard, with much of the technical
effort involving the construction of lower bounds.

While the above results are interesting in their own right, we emphasize one
key use case of our results in a seemingly unrelated field: smoothed online
learning. We briefly recall the setup. For general online learning, we fix a
set of contexts $\mathcal{X}$, a set of targets $\mathcal{Y}$ and a function
class $\mathcal{F}:\mathcal{X}\to\mathcal{Y}$ as well as a loss function
$\ell:\mathcal{Y}\times\mathcal{Y}\to[0,1]$. For some horizon $T$, online
learning proceeds in rounds where for each time $1\leq t\leq T$ the following
happens:

  1. 1.

Nature chooses some context $x_{t}$ and label $y_{t}$.

  2. 2.

the Learner chooses some prediction $\widehat{y}_{t}\in\mathcal{Y}$.

  3. 3.

The learner sees $y_{t}$ and suffers loss $\ell(\widehat{y}_{t},y_{t})$.

As in Block et al. (2022); Haghtalab et al. (2022a), we distinguish between
the _proper_ and _improper_ settings. In the former, the Learner must choose
some function $f_{t}\in\mathcal{F}$ before seeing $x_{t}$ and then predicts
$\widehat{y}_{t}=f_{t}(x_{t})$. In the latter, the Learner observes $x_{t}$
and then predicts an arbitrary $\widehat{y}_{t}\in\mathcal{Y}_{t}$. The goal
in both cases is to minimize the expected regret to the best function in
hindsight, where

$\displaystyle\operatorname{Reg}_{T}=\sum_{t=1}^{T}\ell(\widehat{y}_{t},y_{t})-\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}\ell(f(x_{t}),y_{t}).$
(3)

As stated, there is no restriction on Nature’s choice of the context and
label, which is called the adversarial setting. Despite its popularity due to
the robustness of the regime and the lack of assumptions, there are two major
problems with the fully adversarial setting: first, simple function classes
like thresholds in one dimension that can be easily learned when the data
appear independently become unlearnable in the adversarial regime (Rakhlin et
al., 2015; Littlestone, 1988); second, even when function classes are
learnable, they often cannot be learned efficiently (Hazan and Koren, 2016).
In order to solve the first issue, the notion of smoothed online learning has
recently gained traction (Rakhlin et al., 2011; Haghtalab et al., 2022a, b;
Block et al., 2022; Block and Simchowitz, 2022). Motivated by smoothed
analysis of algorithms, Rakhlin et al. (2011); Haghtalab et al. (2022b)
consider the following setting. For a fixed base measure $\mu$ on some set
$\mathcal{X}$, we say that a measure $\nu$ is $\sigma$-_smooth_ with respect
to $\mu$ if
$\left|\left|\frac{d\nu}{d\mu}\right|\right|_{\infty}\leq\frac{1}{\sigma}$. An
adversary is $\sigma$-_smooth_ with respect to some fixed $\mu$ if for all
$t$, it holds that the distribution $p_{t}$ of $x_{t}$ conditioned on all the
history is $\sigma$-smooth. One motivation for this definition is to suppose
that Nature is fully adversarial, but corrupted by some small amount of noise.
For example, if $\mathcal{X}=\mathbb{R}^{d}$, we could imagine adding a small
amount of uniform or Gaussian noise to an adversarial input (Block et al.,
2023). In Block et al. (2022); Haghtalab et al. (2022b), the minimax optimal
rates for smoothed online learning were derived up to polylogarithmic factors.
As an example, if we let $\mathrm{vc}\left(\mathcal{F}\right)$ denote the
Vapnik-Chervonenkis dimension (Blumer et al., 1989) of some binary valued
function class $\mathcal{F}$, then there exists some algorithm capable of
achieving, with respect to the indicator loss,

$\displaystyle\mathbb{E}\left[\operatorname{Reg}_{T}\right]=O\left(\sqrt{T\cdot\mathrm{vc}\left(\mathcal{F}\right)\cdot\log\left(\frac{T}{\sigma}\right)}\right).$
(4)

Unfortunately, in many common settings, a uniform bound on
$\frac{dp_{t}}{d\mu}$ may not be achievable. For example, consider again the
case of a small amount of Gaussian noise in $\mathbb{R}^{d}$ being added to an
adversarial input. A natural choice of $\mu$ would be some fixed Gaussian, but
there is no way to ensure that
$\left|\left|\frac{dp_{t}}{d\mu}\right|\right|_{\infty}$ is finite. Even when
the Radon-Nikodym derivative is uniformly bounded, it may be, as in many high
dimensional settings, that this bound is too large for the resulting
implications to be meaningful. Thus, in Section 4, we propose a more general
notion, of an $f$-smoothed adversary, where the distribution $p_{t}$ of the
contexts $x_{t}$ conditional on the history satisfies
$D_{f}\left(p_{t}||\mu\right)\leq\frac{1}{\sigma}$. In this harder setting,
the results of Block et al. (2022); Haghtalab et al. (2022a, b) no longer
apply due to the breakdown of a key technical step used in the proofs of all
of these results. In Section 4, we apply our bounds on the sample complexity
of approximate rejection sampling to generalize the approach of these works
and achieve upper bounds on the information theoretic rates of $f$-smoothed
online learning, which are tight for some $f$-divergences.

While the information theoretic rates provided in Block et al. (2022);
Haghtalab et al. (2022b) are important, the suggested algorithms that achieve
these rates are computationally intractable and thus two _oracle-efficient_
algorithms were also proposed, where the learner has access to an Empirical
Risk Minimization (ERM) oracle returning the minimizer over $\mathcal{F}$ of a
weighted cumulative loss function evaluated on some data set (see Definition
35 for a formal definition). Once again, the analysis of these two algorithms
does not extend beyond the standard smoothed setting; in Section 4, we again
apply our rejection sampling sample complexity bounds to demonstrate that, by
modifying the hyperparameters of the two proposed algorithms, we can still
maintain a no-regret guarantee under the significantly more general
$f$-smoothed online learning setting.

We defer discussion of related work to Appendix A for the sake of space. We
now summarize our key contributions:

  * •

In Theorem 3, we provide an upper bound on the complexity of approximately
sampling from some target measure $\nu$ given access to samples from $\mu$. In
particular, we show that by modifying classical rejection sampling,
$\widetilde{\Theta}\left((f^{\prime})^{-1}\left(\frac{D_{f}\left(\nu||\mu\right)}{\varepsilon}\right)\right)$
samples suffice to obtain a sample with total variation distance at most
$\varepsilon$ from the target.

  * •

In Proposition 4 and Theorems 5 and 6, we show that the upper bound given by
rejection sampling is essentially tight. In particular, we show that rejection
sampling is in some sense generic in that “the best” way to use samples from
$\mu$ to produce a sample from $\nu$ is the approach described above.
Furthermore, we show that if $f^{\prime}$ is bounded above, then the
approximate sampling problem is impossible; if $f^{\prime}$ is unbounded, we
show in Theorems 5 and 6 that the sample complexity derived in Theorem 3 is
essentially tight as $\varepsilon\downarrow 0$. In particular, Theorem 5 shows
that for all $n$, there exist distributions with bounded $f$-divergence such
that
$\Omega\left((f^{\prime})^{-1}\left(\frac{D_{f}\left(\nu||\mu\right)}{\varepsilon}\right)\right)$
samples are necessary to produce an $\varepsilon$-approximate sample from the
target measure, while in Theorem 6, we show that (for a slightly smaller class
of $f$ satisfying a mild growth condition) there exist distributions such that
the preceding lower bound holds uniformly in $n$.

  * •

In Section 4, we generalize previous results on smoothed online learning to
the significantly more general setting of $f$-smoothed online learning. In
particular, we derive minimax upper bounds without regard to computation time
as well as demonstrating that two oracle-efficient algorithms (one proper and
one improper) proposed in Block et al. (2022) remain no-regret even in the
more general $f$-smoothed online learning setting. Moreover, in Theorem 12, we
answer an open question in Block et al. (2022) by showing that an instance of
FTPL has regret scaling like $\sigma^{-1/4}$ as opposed to $\sigma^{-1/2}$,
where $\sigma$ is the smoothness parameter of the adversary; this generalizes
a result of Haghtalab et al. (2022a) to arbitrary context spaces.

  * •

In Appendix B, we prove new bounds on the quality of importance sampling for
estimating means with respect to a target $\nu$ uniformly over a function
class $\mathcal{F}$ when we have access to samples from $\mu$. We then compare
these results to estimates using rejection sampling assuming
$D_{f}\left(\nu||\mu\right)<\infty$ for the special case of
$\chi^{2}$-divergence and compare these results with earlier bounds from
Chatterjee and Diaconis (2018); Cortes et al. (2010).

##### Notation

In the sequel, we will always denote by $\mu$ a base measure on the set
$\mathcal{X}$ with associated $\sigma$-algebra $\mathscr{F}$. We will denote
by $X_{1:n}=(X_{1},\dots,X_{n})$ a vector of $n$ independent samples from
$\mu$ and we will let $j^{\ast}$ be a selection rule. We will reserve $\nu$
for our target measure and the letters $\varepsilon,\delta,\gamma$ will all be
reserved for small positive real constants. Furthermore, we will reserve $f$
for a convex function mapping the positive reals to the positive reals
satisfying $f(1)=f^{\prime}(1)=0$. Furthermore, for such an $f$, we will let
$f^{-1}(u)=\inf\left\\{t>0|f^{\prime}(t)\geq u\right\\}$ where we adopt the
standard convention of taking the infimum of the empty set to be infinite. For
a given random variable $Y$, we will denote by $P_{Y}$ the distribution of
$Y$. We use $O(\cdot),\Omega(\cdot)$ to denote asymptotic big-oh notation and
apply tildes to hide polylogarithmic factors.

##  2 Problem Setup and Notation

In this section, we formally define the necessary information theoretic
quantities and state the problem. To begin, we define $f$-divergence. For more
information on information theoretic notions, see Polyanskiy and Wu (2022+)

######  Definition 1.

Let $f:[0,\infty]\to\mathbb{R}_{\geq 0}\cup\\{\infty\\}$ be a convex function
satisfying $f(1)=f^{\prime}(1)=0$. For two probability measures $\nu,\mu$ on
some space $\mathcal{X}$, define the $f$-divergence,

$\displaystyle
D_{f}\left(\nu||\mu\right)=\mathbb{E}_{\mu}\left[f\left(\frac{d\nu}{d\mu}(Z)\right)\mathbb{I}\left[\frac{d\nu}{d\mu}(Z)<\infty\right]\right]+f^{\prime}(\infty)\mu\left(\frac{d\nu}{d\mu}(Z)=\infty\right).$
(5)

Note that if $\nu\ll\mu$ then we may ignore the second term.

######  Remark 2.

As a technical aside, throughout the paper, we will be using $f^{\prime}$ and
$f^{\prime\prime}$ to denote the first and second derivatives of the $f$
appearing in Definition 1. By Rademacher’s Theorem (Rademacher, 1919), $f$ is
differentiable almost everywhere, but for any points where $f$ is not
differentiable, we will take $f^{\prime}$ to be the maximal subgradient. As
$f$ is increasing, $f^{\prime}$ is nondecreasing and thus we can take
$f^{\prime\prime}$ to be the right derivative of $f^{\prime}$, which is always
well-defined.

We will phrase our results in terms of $D_{f}\left(\nu||\mu\right)$ for
general $f$, but there are several important examples that will come up
throughout the paper. Before formally introducing the problem, we will give
several examples of well-known $f$-divergences:

######  Example 1 (Total Variation).

Consider $f(x)=\left|x-1\right|-(x-1)$. In this case we have

$\displaystyle
D_{f}\left(\nu||\mu\right)=\operatorname{TV}(\nu,\mu)=\sup_{A\in\mathscr{F}}\left|\nu(A)-\mu(A)\right|$
(6)

the total variation distance, where $\mathscr{F}$ is the common
$\sigma$-algebra over $\mathcal{X}$ on which $\nu,\mu$ are defined.

######  Example 2 (KL Divergence).

If we set $f(x)=x\log(x)-x+1$ then we get
$D_{f}\left(\nu||\mu\right)=D_{KL}\left(\nu||\mu\right)$ the KL divergence.

######  Example 3 (Renyi Divergence).

If we set $f(x)=x^{\lambda}-\lambda x+\lambda-1$, then we get that

$\displaystyle
D_{f}\left(\nu||\mu\right)=e^{(\lambda-1)D_{\lambda}\left(\nu||\mu\right)}$
(7)

where $D_{\lambda}\left(\nu||\mu\right)$ is the Renyi divergence of order
$\lambda$. Special cases of $D_{\lambda}\left(\nu||\mu\right)$ include the
case where $\lambda\downarrow 1$ in which case we have the KL divergence again
and $\lambda=2$, in which case we recover (a monotone transformation of) the
standard $\chi^{2}$ divergence.

######  Example 4 ($\mathcal{E}_{\gamma}$ Divergence).

If, for $\gamma\geq 1$, we set $f_{\gamma}(x)=(x-\gamma)_{+}$, then denote by
$\mathcal{E}_{\gamma}(\nu||\mu)$ the divergence associated with this $f$. This
divergence was originally defined in (Polyanskiy, 2010, (2.141)) for the study
of channel coding. Since then it appeared prominently in the study of
differential privacy (Asoodeh et al., 2021) and wiretap channels (Liu et al.,
2017). It will also be crucial in the proof of our lower bounds below.

We now define the primary object of study. Given $X_{1:n}=(X_{1},\dots,X_{n})$
a tuple of elements of $\mathcal{X}$, we define a _selection rule_ $j^{\ast}$
as any random variable taking values in $[n]$ and depending in any way on
$X_{1:n}$. We are now ready to formally state the main problem:

> Question: Suppose that $\mathcal{X}$ is an arbitrary set with
> $\sigma$-algebra $\mathscr{F}$ and suppose that $\mu,\nu$ are probability
> measures with respect to $\mathscr{F}$ satisfying, for some fixed $f$,
> $D_{f}\left(\nu||\mu\right)<\infty$. For fixed $\varepsilon>0$, how large
> does $n$ have to be such that there exists a selection rule $j^{\ast}$
> ensuring that
> $\operatorname{TV}\left(P_{X_{j^{\ast}}},\nu\right)<\varepsilon$?

As an example, we consider traditional rejection sampling. We construct a
random set $\mathcal{S}\subset[n]$ by adding $j$ to $\mathcal{S}$ with
probability $\frac{1}{M}\cdot\frac{d\nu}{d\mu}(X_{j})$, which is at most $1$
by the assumption that
$M>\left|\left|\frac{d\nu}{d\mu}\right|\right|_{\infty}$. If $\mathcal{S}$ is
nonempty, we let $j^{\ast}$ be an arbitrary element and otherwise we select
$j^{\ast}$ uniformly at random. As we shall show for the sake of completeness
(see Lemma 26 in Appendix D), the probability that $\mathcal{S}$ is empty is
at most $e^{-\frac{n}{M}}$ and if $\mathcal{S}$ is nonempty then
$X_{j^{\ast}}$ is distributed according to $\nu$. Thus if
$n=M\log\left(\frac{1}{\delta}\right)$, with probability at least $1-\delta$,
$X_{j^{\ast}}$ is distributed according to $\nu$. Because we required
$M>\left|\left|\frac{d\nu}{d\mu}\right|\right|_{\infty}$, we see that
$\Theta\left(\left|\left|\frac{d\nu}{d\mu}\right|\right|_{\infty}\log\left(\frac{1}{\delta}\right)\right)$
samples are sufficient to exactly sample from $\nu$ with high probability. The
necessity will be seen as a very special case of our lower bounds in the
following section.

##  3 Sample Complexity of Rejection Sampling

In this section, we state and sketch the proofs of our main results regarding
rejection sampling and fully answer the question raised in Section 2. We will
divide our results into two theorems, one providing an upper bound using a
modified version of rejection sampling, and the other giving an almost
matching lower bound. We begin with the upper bound:

######  Theorem 3 (Upper Bound).

Suppose that $\mu,\nu$ are probability distributions on some set $\mathcal{X}$
and suppose that $X_{1},\dots,X_{n}\sim\mu$ are independent. Fix some $f$
satisfying the conditions in Definition 1. For $\varepsilon>0$, if

$\displaystyle
n\geq\frac{1}{1-\varepsilon}\log\left(\frac{2}{\varepsilon}\right)(f^{\prime})^{-1}\left(\frac{2D_{f}\left(\nu||\mu\right)}{\varepsilon}\right)$
(8)

then there exists a selection rule $j^{\ast}$ satisfying
$\operatorname{TV}\left(P_{X_{j^{\ast}}},\nu\right)\leq\varepsilon$.

We will split our discussion into two cases: the superlinear case, where
$f^{\prime}(t)\uparrow\infty$ as $t\uparrow\infty$ and the linear case, where
$f^{\prime}(t)$ is bounded from above. In the former, we will see that as
$n\uparrow\infty$, we can always use rejection sampling to get an increasingly
good approximation of a sample from $\nu$ because $(f^{\prime})^{-1}$ is
finite on the entire positive real line. In the linear case, however, we shall
shortly prove that no selection rule can hope to get arbitrarily close to
$\nu$ in total variation. Before sketching the proof of Theorem 3, we provide
some examples.

######  Example 5 (Total Variation).

Recall that total variation is the $f$-divergence such that
$f(x)=\left|x-1\right|-x+1$. Note that $f^{\prime}(x)=0$ for all $x>1$ and so
$(f^{\prime})^{-1}(M)$ is infinite for $M>0$. Thus Theorem 3 is vacuous when
we only have control over total variation, as expected.

######  Example 6 (KL Divergence).

As we saw in Example 2, KL divergence is the $f$-divergence where we set
$f(x)=x\log(x)-x+1$. In this case, we see that $f^{\prime}(x)=\log(x)$ and so
Theorem 3 tells us that in order to be $\varepsilon$-close in total variation,
$\widetilde{O}\left(\exp\left(\frac{D_{KL}\left(\nu||\mu\right)}{\varepsilon}\right)\right)$
samples suffice.

######  Example 7 (Renyi Divergence).

Remember from Example 3 that $f(x)=x^{\lambda}-\lambda x+\lambda-1$ for
$\lambda>1$ defines the Renyi divergence. In this case we see that
$\widetilde{O}\left(e^{D_{\lambda}\left(\nu||\mu\right)}\varepsilon^{-\frac{1}{\lambda-1}}\right)$
samples suffice. As $\lambda\uparrow\infty$, we recover the standard rejection
sampling bound by taking $\varepsilon\downarrow 0$ and noting that
$D_{\infty}(\nu||\mu)=\left|\left|\frac{d\nu}{d\mu}\right|\right|_{\infty}$.
In the special case of $\lambda=2$, we note that Renyi divergence recovers
$\chi^{2}$-divergence and note that
$\widetilde{O}\left(\frac{\chi^{2}(\nu||\mu)}{\varepsilon}\right)$ samples
suffice.

We now sketch the proof of the upper bound, deferring details to Appendix D:

###### Proof of Theorem 3.

Let $\nu_{M}$ denote the measure $\nu$ conditioned on the event that
$\frac{d\nu}{d\mu}\leq M$ and let $\widetilde{\nu}$ denote the law of the
sample produced by rejection sampling from $\nu_{M}$ with $n$ samples. The
standard analysis of rejection sampling tells us that if
$n=\Omega\left(\log\left(\frac{1}{\varepsilon}\right)M\right)$ then
$\operatorname{TV}\left(\widetilde{\nu},\nu_{M}\right)\leq\varepsilon$. We
show in Lemma 27 that if $M>1$, then

$\displaystyle\nu\left(\frac{d\nu}{d\mu}>M\right)\leq\frac{D_{f}\left(\nu||\mu\right)}{f^{\prime}(M)}.$
(9)

Using this result, we show that
$\operatorname{TV}\left(\nu_{M},\nu\right)\leq\frac{D_{f}\left(\nu||\mu\right)}{f^{\prime}(M)}$
and conclude by applying the triangle inequality. ∎

We now turn to our lower bounds. In particular, we show that for any
$f$-divergence, there exist distributions $\mu,\nu$ satisfying
$D_{f}\left(\nu||\mu\right)<\infty$ such that in order for there to exist a
selector rule guaranteeing that
$\operatorname{TV}\left(P_{X_{j^{\ast}}},\nu\right)<\varepsilon$, we require
$n$ to be sufficiently large. We will again split our discussion into the
linear and superlinear cases. For the linear case, we have the following lower
bound:

######  Proposition 4 (Lower Bound, Linear Case).

Suppose that $f$ is a convex function as in Definition 1 satisfying
$f^{\prime}(t)\leq C<\infty$ for all $t>1$. Then there exist distributions
$\mu,\nu$ such that $D_{f}\left(\nu||\mu\right)<\infty$ and
$\varepsilon=\varepsilon(f,D_{f}\left(\nu||\mu\right))>0$ such that for all
$n$ and $X_{1},\ldots X_{n}\stackrel{{\scriptstyle iid}}{{\sim}}\mu$.

$\displaystyle\inf_{j^{\ast}}\operatorname{TV}\left(P_{X_{j^{\ast}}},\nu\right)\geq\varepsilon$
(10)

where the infimum is over all selection rules $j^{\ast}$.

Note that Proposition 4 matches the upper bound for linear $f$ in Theorem 3
and reflect the fact that for $f$ that do not grow superlinearly,
$D_{f}\left(\nu||\mu\right)<\infty$ provides very weak control on $\nu$.
Intuitively this should be clear: note that if $f$ is in the linear regime,
then $D_{f}\left(\nu||\mu\right)$ can remain finite even when $\nu$ is
singular with respect to $\mu$ and thus samples from $\mu$ can never hope to
approximate $\nu$ to arbitrary precision. A full proof can be found in
Appendix D.

Moving on to the more interesting case of superlinear $f$, we provide a lower
bound that matches the upper bound found in Theorem 3 for all superlinear $f$.

######  Theorem 5 (Lower Bound, Superlinear Case).

Let $f$ be a convex function as in Definition 1 that grows superlinearly. Then
for all $0<\varepsilon\leq 1/4$ and $\delta>2f(1/2)$, there exists a pair of
measures $\nu,\mu$ such that $D_{f}\left(\nu||\mu\right)\leq\delta$ and any
selection rule $j^{\ast}$ satisfying
$\operatorname{TV}(P_{X_{j^{\ast}}},\nu)\leq\varepsilon$ requires

$\displaystyle
n\geq\frac{1}{2}\cdot(f^{\prime})^{-1}\left(\frac{\delta}{2\varepsilon}\right).$
(11)

While we provide full details in Appendix D, we provide a sketch of the proof
here:

###### Proof.

A simple computation found in Lemma 28 tells us that if $\widetilde{\nu}$ is
the law of $X_{j^{\ast}}$, then the Radon-Nikodym derivative of
$\widetilde{\nu}$ with respect to $\mu$ is uniformly bounded by $n$. Another
computation, found in Lemma 31 tells us that if $\widetilde{\nu}$ has
likelihood ratio bounded by $n$, then we can lower bound
$\operatorname{TV}\left(\widetilde{\nu},\nu\right)$ by
$\mathcal{E}_{n}(\nu||\mu)$. Combining these facts, we see that it suffices to
exhibit two distributions $\mu,\nu$, such that
$D_{f}\left(\nu||\mu\right)\leq\delta$ and
$\mathcal{E}_{n}\left(\nu||\mu\right)\geq\varepsilon$ for all $n$ not
satisfying (11). Thus, we have reduced the proof to determining if the point
$(\varepsilon,\delta)$ lies above some point in the _joint range_ of $\mu$ and
$\nu$, i.e., the set
$\left\\{(\mathcal{E}_{n}(\nu||\mu),D_{f}\left(\nu||\mu\right))\right\\}$
where $\mu$ and $\nu$ vary over all distributions. In Harremoës and Vajda
(2011), it was shown that the distributions extremizing the joint range are
typically pairs of Bernoulli random variables. We thus consider
$\mu=\operatorname{Ber}\left(\frac{\varepsilon}{n}\right)$ and
$\nu=\operatorname{Ber}(2\varepsilon)$ and show that
$\mathcal{E}_{n}(\nu||\mu)=\varepsilon$, while
$D_{f}\left(\nu||\mu\right)\leq\delta$, unless $n$ is sufficiently large so as
to satisfy (11). The result follows. ∎

Note that Theorem 5 tells us that, up to logarithmic factors, the sample
complexity determined in Theorem 3 is optimal. There is one disadvantage to
the above result, however: as is clear from the proof, the distributions $\mu$
and $\nu$ depend on $n$ and thus the order of quantifiers in Theorem 5 is
weaker than that in Theorem 3. In order to address this shortcoming, we prove
a slightly weaker lower bound under a mild growth condition on $f$:

######  Theorem 6.

Let $f$ be a convex function as in Definition 1 that grows superlinearly.
Suppose that $f$ satisfies a mild growth condition (see Theorem 33 for formal
statement). Then, for any $\zeta>0$, there exist distributions $\mu,\nu$ with
$D_{f}\left(\nu||\mu\right)<\infty$ such that for all sufficiently large
$n\in\mathbb{N}$, with $X_{1},\dots,X_{n}$ sampled independently from $\mu$,
it holds that

$\displaystyle\inf_{j^{\ast}}\operatorname{TV}\left(P_{X_{j^{\ast}}},\nu\right)\geq\frac{\zeta^{1+\zeta}}{8}\cdot\left(\frac{D_{f}\left(\nu||\mu\right)}{f^{\prime}(n)}\right)^{1+\zeta}$
(12)

where the infimum is taken over all selection rules.

We note that the mild growth condition required in Theorem 6 is purely
technical and likely could be removed with more elaborate analysis; on the
other hand, this condition is satisfied by all commonly used, superlinear
$f$-divergences of which we are aware. By Theorem 3, we see that if

$n=\widetilde{O}\left((f^{\prime})^{-1}\left(\frac{D_{f}\left(\nu||\mu\right)}{\varepsilon}\right)\right),$
(13)

then rejection sampling suffices to generate an $\varepsilon$-approximate
sample from $\nu$. On the other hand, setting $\zeta=o(1)$ as
$\varepsilon\downarrow 0$, Theorem 6 tells us that in the worst case, we
require

$n=\widetilde{\Omega}\left((f^{\prime})^{-1}\left(\frac{D_{f}\left(\nu||\mu\right)}{\varepsilon^{1-o(1)}}\right)\right)$
(14)

samples for the right hand side in (12) to be below $\varepsilon$. Thus, as
$\varepsilon\downarrow 0$, these bounds essentially match. In particular,
because the $f$-divergences in Examples 6 and 7 satisfy the mild growth
condition, the sample complexity upper bounds derived in those examples are
indeed tight for all sufficiently large $n$.

We defer a detailed proof of Theorem 6 to Appendix D. The method is similar to
that of Theorem 5 in that we reduce to lower bounding
$\mathcal{E}_{n}(\nu||\mu)$ for distributions $\nu,\mu$ with bounded
$f$-divergence. The difference is that we exhibit a _single_ pair $(\mu,\nu)$,
depending on $f$ but independent of $n$, such that the desired properties
hold.

Combining Theorems 3, 5 and 6, we have shown that
$\widetilde{\Theta}\left((f^{\prime})^{-1}(D_{f}\left(\nu||\mu\right))/\varepsilon\right)$
samples are both necessary and sufficient to generate an
$\varepsilon$-approximate sample from $\nu$. One immediate application of
these results is to the problem of estimating means according to $\nu$
uniformly over some function class $\mathcal{F}$ when given samples from
$\mu$. In Appendix B, we compare estimators using Theorem 3 to the classical
importance sampling approach. For the sake of space, this is deferred to the
appendix; we now proceed to our main application regarding smoothed online
learning.

##  4 Smoothed Online Learning

Our most important immediate application is to the question of generalizing
smoothed online learning as outlined in the introduction. In this section, we
extend results proved for smoothed adversaries (Rakhlin et al., 2011; Block et
al., 2022; Haghtalab et al., 2022b, a) described in the introduction to allow
for a more powerful Nature. To do this, we employ the following definition:

######  Definition 7.

Fix a base measure $\mu$ on some set $\mathcal{X}$. We say that a measure
$\nu$ is $(f,\sigma)$-smooth (or $f$-smooth) with respect to $\mu$ if
$D_{f}\left(\nu||\mu\right)\leq\frac{1}{\sigma}$. An adversary is
$(f,\sigma)$-smooth with respect to $\mu$ if for all $1\leq t\leq T$, the
distribution $p_{t}$ of $x_{t}$, conditioned on all the history, is
$(f,\sigma)$-smooth.

Definition 7 motivates an obvious question: can we achieve improvement over
the fully adversarial setting even when we only require Nature to be
$f$-smooth? The answer will, of course, depend on what $f$ we choose. For the
case of eventually linear $f$, for example, we see that no improvement is
possible in general:

######  Proposition 8.

Suppose that
$\mathcal{F}=\left\\{x\mapsto\mathbb{I}[x\geq\theta]|\theta\in[0,1]\right\\}$
is the class of thresholds in one dimension. Let $f$ be a convex function as
in Definition 1 that is eventually linear, in the sense that $f^{\prime}$ is
bounded above. For all $0<\sigma<1$ there is a $(f,\sigma)$-smooth adversary
such that any learner experiences
$\mathbb{E}\left[\operatorname{Reg}_{T}\right]=\Omega(T)$.

This result, proved in Appendix E, is not surprising in light of the fact that
fully adversarial online learning of $\mathcal{F}$ is impossible; if $f$ is
linear, then Nature can mix the worst-case adversary with a base distribution
and still incur linear regret with finite $D_{f}\left(\nu||\mu\right)$. More
interesting is the case of stronger $f$-divergences. Before we present our
results, we state our main technical tool, which generalizes a technique
introduced in Haghtalab et al. (2022b) and extended in Block et al. (2022). In
those works, the authors introduced a coupling between the sequence contexts
produced by a smooth, adaptive adversary and a larger set of independent
sampled drawn from the base measure. Using the tools developed in Section 3,
we extend this technique beyond the case of uniformly bounded Radon-Nikodym
derivatives:

######  Lemma 9.

Let $\mathcal{X}$ be a set and $\mu$ some measure on $\mathcal{X}$. Suppose
that an adversary is $(f,\sigma)$-smooth with respect to $\mu$ for some $f$
satisfying the conditions of Definition 1 such that $\sup
f^{\prime}(t)=\infty$. For any $T$ and any $\varepsilon,\delta>0$, if

$\displaystyle
n\geq\frac{1}{1-\varepsilon}\log\left(\frac{T}{\delta}\right)(f^{\prime})^{-1}\left(\frac{1}{\varepsilon\sigma}\right)$
(15)

then there exists a coupling between $(x_{1},\dots,x_{T})$ and
$\left\\{Z_{t,j}|1\leq t\leq T\text{ and }1\leq j\leq n\right\\}$ such that
the $(x_{1},\dots,x_{T})$ are distributed according to the adversary, the
$Z_{t,j}\sim\mu$ are independent, and, with probability at least $1-\delta$,
there are selection rules $j^{\ast}_{t}$ such that
$\operatorname{TV}\left(P_{x_{t}},P_{Z_{t,j^{\ast}_{t}}}\right)\leq\varepsilon$.

We defer the construction of the coupling to Appendix E; for now we focus on
the implications. Our first result extends Block et al. (2022, Theorem 3) and
Haghtalab et al. (2022b, Theorem 3.1) to the case of $f$-smoothed online
learning. While we state the result for general real-valued function classes
in Appendix E, for the sake of simplicity we restrict our focus to binary-
valued $\mathcal{F}$ here.

######  Theorem 10.

Suppose $\mathcal{F}\to\left\\{\pm 1\right\\}$ is a binary valued function
class and let $\mathrm{vc}\left(\mathcal{F}\right)$ denote its Vapnik-
Chervonenkis dimension. Suppose that $(x_{t},y_{t})$ are generated by a
$(f,\sigma)$-smoothed adversary in the sense of Definition 7 such that
$f^{\prime}(\infty)=\infty$. Then there exists an algorithm such that

$\displaystyle\mathbb{E}\left[\operatorname{Reg}_{T}\right]\lesssim\sqrt{T\log(T)\cdot\mathrm{vc}\left(\mathcal{F}\right)}+\inf_{0<\varepsilon<1}\varepsilon
T+\sqrt{T\mathrm{vc}\left(\mathcal{F}\right)\log\left(T(f^{\prime})^{-1}\left(\frac{1}{\varepsilon\sigma}\right)\right)}.$
(16)

We remark that Theorem 10 is a special case of the more general Theorem 34
applying to arbitrary real-valued function classes, which we state and prove
in Appendix E. The proof follows the approach of Block et al. (2022) with the
modification of applying the more general coupling in Lemma 9 and is deferred
to the appendix. Here, we consider two instantiations of $f$-divergences.
First, for the case of Renyi divergence (see examples 3 and 7), we see that
for a Renyi-smoothed adversary, regret of the order
$\widetilde{O}\left(\left(1+\frac{1}{\lambda-1}\right)\sqrt{T\mathrm{vc}\left(\mathcal{F}\right)\log\left(\frac{1}{\sigma}\right)}\right)$
is attainable. Observe that when $\lambda\uparrow\infty$, we recover the
results of Block et al. (2022). On the other hand, if $\lambda$ is bounded
away from 1, which covers the case of an adversary bounded in $\chi^{2}$
divergence, we see that the cost of assuming only
$D_{\lambda}\left(p_{t}||\mu\right)<\infty$ is only on the order of a constant
more than in the standard setting. The situation is different if we assume
that the adversary is $f$-smoothed in the sense of KL divergence: in this
case, we are only able to recover regret scaling like
$\widetilde{O}\left(T^{2/3}\left(\mathrm{vc}\left(\mathcal{F}\right)/\sigma\right)^{1/3}\right)$.
While the results for Renyi divergence are optimal up to polylogarithmic
factors, we leave as an interesting open direction the question of whether the
regret against a KL-smoothed adversary can be improved.

While Theorem 10 is important insofar as it gives the information theoretic
rates of $f$-smoothed online learning, the algorithms, where provided, are
computationally intractable. We now demonstrate that two algorithms proposed
by Block et al. (2022); Haghtalab et al. (2022a) for smoothed online learning
remain no-regret even if we weaken our assumptions to include
$(f,\sigma)$-smoothed adveraries. These algorithms are _oracle-efficient_ ,
i.e., they make few calls to an Empirical Risk Minimization (ERM) oracle for
the function class $\mathcal{F}$; an ERM oracle, formally defined in Appendix
E (see Definition 35), returns the minimizer of a weighted, cumulative loss
function defined over the function class $\mathcal{F}$. Once again, for the
sake of simplicity, we state our results for the case of binary valued
$\mathcal{F}$ and defer the more general statement and proof to the appendix.

######  Theorem 11.

Suppose that $\mathcal{F}:\mathcal{X}\to\left\\{\pm 1\right\\}$ is a function
class with VC dimension $\mathrm{vc}\left(\mathcal{F}\right)$ and that
$\ell:[-1,1]\times[-1,1]\to[0,1]$ is a loss function that is convex and
1-Lipschitz in the first argument. Then there is an _improper_ algorithm
requiring 2 calls to the ERM oracle per time $t$ such that if the adversary is
$(f,\sigma)$-smoothed, then the regret is bounded as follows:

$\displaystyle\mathbb{E}\left[\operatorname{Reg}_{T}\right]\lesssim\inf_{\alpha>0}\left\\{\alpha
T+\sqrt{\mathrm{vc}\left(\mathcal{F}\right)\cdot
T\cdot\log(T)\cdot(f^{\prime})^{-1}\left(\frac{1}{\alpha\sigma}\right)}\right\\}.$
(17)

We prove Theorem 11 in Appendix E, where we apply Lemma 9 to the argument of
Block et al. (2022). We instantiate the bound in (17) in two cases, Renyi
divergence (Example 3) and KL Divergence (Example 2). If we assume that our
adversary is smoothed in the sense of Renyi divergence, then optimizing
$\alpha$ leads us to an oracle-efficient algorithm attaining regret scaling
like
$\widetilde{O}\left(\mathrm{vc}\left(\mathcal{F}\right)^{\frac{\lambda-1}{2\lambda-1}}\cdot
T^{\frac{\lambda}{2\lambda-1}}\cdot\sigma^{-\frac{1}{2\lambda-1}}\right)$.
Noting that if
$\left|\left|\frac{dp_{t}}{d\mu}\right|\right|_{\infty}\leq(\sigma^{\prime})^{-1}$
then we may take $\sigma=(\sigma^{\prime})^{\lambda-1}$, we observe that in
the limit as $\lambda\uparrow\infty$, we recover the
$\widetilde{O}\left(\sqrt{\mathrm{vc}\left(\mathcal{F}\right)\cdot
T/\sigma^{\prime}}\right)$ rate from Block et al. (2022, Theorem 7). In the
special case where $\lambda=2$, we see that the regret scales like
$\widetilde{O}\left((\mathrm{vc}\left(\mathcal{F}\right)/\sigma)^{1/3}\cdot
T^{2/3}\right)$. On the other hand, if we make the weaker assumption that the
adversary is only smoothed in the KL sense, then Theorem 11 only recovers a
regret that scales as $\widetilde{O}\left(\log(d)T/(\sigma\log(T))\right)$,
which is sublinear in $T$ but very slow.

We turn now to the case of proper algorithms. As in Block et al. (2022), we
instantiate Follow the Perturbed Leader (FTPL) with a perturbation by a
Gaussian process; again, we apply our Lemma 9 to the proof techniques found in
Block et al. (2022, Appendix E). For the sake of simplicity, we restrict our
focus to binary valued function classes with linear loss.

######  Theorem 12.

Suppose that we are in the situation of Theorem 11, with the loss function
$\ell$ being linear, i.e., $\ell(\widehat{y},y)=(1-\widehat{y}\cdot y)/2$.
Suppose further that our adversary is $(f,\sigma)$-smooth in the sense of
Renyi Divergence, i.e., for some $\lambda\geq 2$,
$D_{\lambda}\left(p_{t}||\mu\right)\leq 1/\sigma$ for all $p_{t}$. Then there
is a _proper_ algorithm requiring only 1 call to the ERM oracle per round such
that the regret is bounded as follows:

$\displaystyle\mathbb{E}\left[\operatorname{Reg}_{T}\right]=\widetilde{O}\left(\sqrt{\mathrm{vc}\left(\mathcal{F}\right)}\cdot
T^{\frac{2\lambda+1}{4\lambda-1}}\cdot\sigma^{-\frac{1}{4\lambda-1}}\right).$
(18)

Note that our regret in Theorem 12 actually improves on that of (Block et al.,
2022, Theorem 10) in the case where we take $\lambda\uparrow\infty$. Indeed,
if we are in the strongly smooth regime such that the Radon-Nikodym derivative
of the adversary’s distribution is uniformly bounded by $\sigma^{\prime-1}$,
then in the limit we recover an expected regret scaling like
$\widetilde{O}\left(\sqrt{\mathrm{vc}\left(\mathcal{F}\right)\cdot
T}\cdot(\sigma^{\prime})^{-\frac{1}{4}}\right)$, which matches that of the
instantiation of FTPL found in Haghtalab et al. (2022a) for discrete
$\mathcal{X}$. Thus, by examining $f$-smoothed adversaries, we anwer an open
question of Block et al. (2022) on improving the dependence on
$\sigma^{\prime}$ of the expected regret of FTPL with a Gaussian perturbation.

We leave as an interesting further direction the question regarding the
tightness of the regret of the algorithms in Theorems 11 and 12. As shown in
Block et al. (2022); Haghtalab et al. (2022a), even in the case of strongly
smoothed adversaries, there is a statistical-computational gap wherein the
dependence of the expected regret for an oracle-efficient algorithm on
$\sigma$ must be polynomial, but Theorem 10 yields a statistical rate that is
polylogarithmic in the same. Even in the adversarial setting, however, it is
unknown if such an exponential gap exists for oracle-efficient _improper_
algorithms (Hazan and Koren, 2016).

Finally, we observe that Theorem 12 only applies to $f$-smoothed adversaries
in the Renyi sense for $\lambda\geq 2$. Our proof proceeds by a change of
measure argument, wherein we replace an expectation over the base measure
$\mu$ by an expectation over the adversary’s distribution $p_{t}$; for a
weaker $f$-divergence like KL, the analogous statement would require bounding
an exponential moment, which would require significantly stronger analysis. We
leave the question of existence of oracle-efficient proper algorithms for KL
smoothed adversaries as yet another interesting further direction.

## Acknowledgements

AB acknowledges support from the National Science Foundation Graduate Research
Fellowship under Grant No. 1122374 as well as support from ONR under grant
N00014-20-1-2336 and DOE under grant DE-SC0022199. YP was supported in part by
the MIT-IBM Watson AI Lab and by the NSF grant CCF-2131115. We also
acknowledge an anonymous reviewer for pointing us to a relevant reference.

## References

  * Agrawal et al. [2022] Shweta Agrawal, Damien Stehle, and Anshu Yadav.  Round-optimal lattice-based threshold signatures, revisited.  Cryptology ePrint Archive, Paper 2022/634, 2022.  URL https://eprint.iacr.org/2022/634.  https://eprint.iacr.org/2022/634.
  * Asoodeh et al. [2021] Shahab Asoodeh, Maryam Aliakbarpour, and Flavio P Calmon.  Local differential privacy is equivalent to contraction of $\mathcal{E}_{\gamma}$-divergence.  _arXiv preprint arXiv:2102.01258_ , 2021.
  * Bartlett et al. [1994] Peter L Bartlett, Philip M Long, and Robert C Williamson.  Fat-shattering and the learnability of real-valued functions.  In _Proceedings of the seventh annual conference on Computational learning theory_ , pages 299–310, 1994.
  * Bauer and Mnih [2019] Matthias Bauer and Andriy Mnih.  Resampled priors for variational autoencoders.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 66–75. PMLR, 2019.
  * Bercu et al. [2002] Bernard Bercu, Elisabeth Gassiat, and Emmanuel Rio.  Concentration inequalities, large and moderate deviations for self-normalized empirical processes.  _The Annals of Probability_ , 30(4):1576–1604, 2002.
  * Block and Simchowitz [2022] Adam Block and Max Simchowitz.  Efficient and near-optimal smoothed online learning for generalized linear functions.  _arXiv preprint arXiv:2205.13056_ , 2022.
  * Block et al. [2021] Adam Block, Yuval Dagan, and Alexander Rakhlin.  Majorizing measures, sequential complexities, and online learning.  In _Conference on Learning Theory_ , pages 587–590. PMLR, 2021.
  * Block et al. [2022] Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin.  Smoothed online learning is as easy as statistical learning.  _arXiv preprint arXiv:2202.04690_ , 2022.
  * Block et al. [2023] Adam Block, Max Simchowitz, and Russ Tedrake.  Smoothed online learning for prediction in piecewise affine systems, 2023\.
  * Blumer et al. [1989] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth.  Learnability and the vapnik-chervonenkis dimension.  _Journal of the ACM (JACM)_ , 36(4):929–965, 1989\.
  * Cesa-Bianchi and Lugosi [2006] Nicolo Cesa-Bianchi and Gábor Lugosi.  _Prediction, learning, and games_.  Cambridge university press, 2006.
  * Chatterjee and Diaconis [2018] Sourav Chatterjee and Persi Diaconis.  The sample size required in importance sampling.  _The Annals of Applied Probability_ , 28(2):1099–1135, 2018.
  * Cortes et al. [2010] Corinna Cortes, Yishay Mansour, and Mehryar Mohri.  Learning bounds for importance weighting.  _Advances in neural information processing systems_ , 23, 2010.
  * Devevey et al. [2022] Julien Devevey, Omar Fawzi, Alain Passelègue, and Damien Stehlé.  On rejection sampling in lyubashevsky’s signature scheme.  _Cryptology ePrint Archive_ , 2022.
  * Flury [1990] Bernard D Flury.  Acceptance–rejection sampling made easy.  _Siam Review_ , 32(3):474–476, 1990.
  * Gilks and Wild [1992] Walter R Gilks and Pascal Wild.  Adaptive rejection sampling for gibbs sampling.  _Journal of the Royal Statistical Society: Series C (Applied Statistics)_ , 41(2):337–348, 1992.
  * Giné and Nickl [2021] Evarist Giné and Richard Nickl.  _Mathematical foundations of infinite-dimensional statistical models_.  Cambridge university press, 2021.
  * Görür and Teh [2011] Dilan Görür and Yee Whye Teh.  Concave-convex adaptive rejection sampling.  _Journal of Computational and Graphical Statistics_ , 20(3):670–691, 2011.
  * Grover et al. [2018] Aditya Grover, Ramki Gummadi, Miguel Lazaro-Gredilla, Dale Schuurmans, and Stefano Ermon.  Variational rejection sampling.  In _International Conference on Artificial Intelligence and Statistics_ , pages 823–832. PMLR, 2018.
  * Haghtalab et al. [2020] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty.  Smoothed analysis of online and differentially private learning.  _Advances in Neural Information Processing Systems_ , 33:9203–9215, 2020.
  * Haghtalab et al. [2022a] Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang.  Oracle-efficient online learning for beyond worst-case adversaries.  _arXiv preprint arXiv:2202.08549_ , 2022a.
  * Haghtalab et al. [2022b] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty.  Smoothed analysis with adaptive adversaries.  In _2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 942–953. IEEE, 2022b.
  * Harremoës and Vajda [2011] Peter Harremoës and Igor Vajda.  On pairs of $f$-divergences and their joint range.  _IEEE Transactions on Information Theory_ , 57(6):3230–3235, 2011.
  * Harsha et al. [2007] Prahladh Harsha, Rahul Jain, David McAllester, and Jaikumar Radhakrishnan.  The communication complexity of correlation.  In _Twenty-Second Annual IEEE Conference on Computational Complexity (CCC’07)_ , pages 10–23. IEEE, 2007.
  * Harviainen et al. [2021] Juha Harviainen, Antti Röyskö, and Mikko Koivisto.  Approximating the permanent with deep rejection sampling.  _Advances in Neural Information Processing Systems_ , 34:213–224, 2021.
  * Hazan and Koren [2016] Elad Hazan and Tomer Koren.  The computational power of optimization in online learning.  In _Proceedings of the forty-eighth annual ACM symposium on Theory of Computing_ , pages 128–141, 2016.
  * Kalai and Vempala [2005] Adam Kalai and Santosh Vempala.  Efficient algorithms for online decision problems.  _Journal of Computer and System Sciences_ , 71(3):291–307, 2005.
  * Kearns and Schapire [1994] Michael J Kearns and Robert E Schapire.  Efficient distribution-free learning of probabilistic concepts.  _Journal of Computer and System Sciences_ , 48(3):464–497, 1994.
  * Kloek and Van Dijk [1978] Tuen Kloek and Herman K Van Dijk.  Bayesian estimates of equation system parameters: an application of integration by monte carlo.  _Econometrica: Journal of the Econometric Society_ , pages 1–19, 1978\.
  * Littlestone [1988] Nick Littlestone.  Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.  _Machine learning_ , 2(4):285–318, 1988.
  * Liu and Verdu [2018] Jingbo Liu and Sergio Verdu.  Rejection sampling and noncausal sampling under moment constraints.  In _2018 IEEE International Symposium on Information Theory (ISIT)_ , pages 1565–1569. IEEE, 2018.
  * Liu et al. [2017] Jingbo Liu, Paul Cuff, and Sergio Verdú.  $\mathcal{E}_{\gamma}$ -resolvability.  _IEEE Transactions on Information Theory_ , 63(5):2629–2658, 2017.  doi: 10.1109/TIT.2016.2642111.
  * Liu [1996] Jun S Liu.  Metropolized independent sampling with comparisons to rejection sampling and importance sampling.  _Statistics and computing_ , 6(2):113–119, 1996\.
  * Liu and Liu [2001] Jun S Liu and Jun S Liu.  _Monte Carlo strategies in scientific computing_ , volume 10.  Springer, 2001.
  * Lyubashevsky [2012] Vadim Lyubashevsky.  Lattice signatures without trapdoors.  In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , pages 738–755. Springer, 2012.
  * Martino and Míguez [2011] Luca Martino and Joaquín Míguez.  A generalization of the adaptive rejection sampling algorithm.  _Statistics and Computing_ , 21(4):633–647, 2011\.
  * Naesseth et al. [2017] Christian Naesseth, Francisco Ruiz, Scott Linderman, and David Blei.  Reparameterization gradients through acceptance-rejection sampling algorithms.  In _Artificial Intelligence and Statistics_ , pages 489–498. PMLR, 2017.
  * Ozols et al. [2013] Maris Ozols, Martin Roetteler, and Jérémie Roland.  Quantum rejection sampling.  _ACM Transactions on Computation Theory (TOCT)_ , 5(3):1–33, 2013.
  * Polyanskiy [2010] Y. Polyanskiy.  _Channel coding: non-asymptotic fundamental limits_.  PhD thesis, Princeton Univ., Princeton, NJ, USA, 2010.  URL http://people.lids.mit.edu/yp/homepage.
  * Polyanskiy and Wu [2022+] Yury Polyanskiy and Yihong Wu.  _Information Theory: From Coding to Learning_.  Cambridge University Press, 2022+.
  * Rademacher [1919] Hans Rademacher.  Über partielle und totale differenzierbarkeit von funktionen mehrerer variabeln und über die transformation der doppelintegrale.  _Mathematische Annalen_ , 79(4):340–359, 1919\.
  * Rakhlin et al. [2011] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Online learning: Stochastic, constrained, and smoothed adversaries.  _Advances in neural information processing systems_ , 24, 2011.
  * Rakhlin et al. [2015] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Sequential complexities and uniform martingale laws of large numbers.  _Probability theory and related fields_ , 161(1):111–153, 2015.
  * Rakhlin et al. [2012] Sasha Rakhlin, Ohad Shamir, and Karthik Sridharan.  Relax and randomize: From value to algorithms.  _Advances in Neural Information Processing Systems_ , 25, 2012.
  * Rudelson and Vershynin [2006] Mark Rudelson and Roman Vershynin.  Combinatorics of random processes and sections of convex bodies.  _Annals of Mathematics_ , pages 603–648, 2006.
  * Srinivasan [2002] Rajan Srinivasan.  _Importance sampling: Applications in communications and detection_.  Springer Science & Business Media, 2002.
  * Tokdar and Kass [2010] Surya T Tokdar and Robert E Kass.  Importance sampling: a review.  _Wiley Interdisciplinary Reviews: Computational Statistics_ , 2(1):54–60, 2010.
  * Van Erven and Harremos [2014] Tim Van Erven and Peter Harremos.  Rényi divergence and kullback-leibler divergence.  _IEEE Transactions on Information Theory_ , 60(7):3797–3820, 2014.
  * van Handel [2013] Ramon van Handel.  The universal glivenko–cantelli property.  _Probability Theory and Related Fields_ , 155(3-4):911–934, 2013.
  * Van Handel [2014] Ramon Van Handel.  Probability in high dimension.  Technical report, PRINCETON UNIV NJ, 2014.
  * Von Neumann [1951] John Von Neumann.  13\. various techniques used in connection with random digits.  _Appl. Math Ser_ , 12(36-38):3, 1951.
  * Wainwright [2019] Martin J Wainwright.  _High-dimensional statistics: A non-asymptotic viewpoint_ , volume 48.  Cambridge University Press, 2019.
  * Zheng et al. [2021] Zhongxiang Zheng, Anyu Wang, and Lingyue Qin.  Rejection sampling revisit: How to choose parameters in lattice-based signature.  _Mathematical Problems in Engineering_ , 2021, 2021.

##  Appendix A Related Work

##### Rejection Sampling

As mentioned in the introduction, rejection sampling was pioneered by Von
Neumann [1951] and has received much attention due to its simplicity and
general application, with far too many references to list [Gilks and Wild,
1992, Liu, 1996, Flury, 1990, Harviainen et al., 2021, Bauer and Mnih, 2019].
More recently, the information theory community has been interested in
improving the bounds on the sample complexity of _exact_ rejection sampling
under assumed additional structure, such as a Renyi divergence bound [Liu and
Verdu, 2018, Harsha et al., 2007].

Perhaps surprisingly, _approximate_ rejection sampling has received relatively
little attention. Several works have proposed a tradeoff between the sample
complexity of approximate rejection sampling and the accuracy of the produced
sample; one example is Grover et al. [2018], which demonstrated a qualitative
monotonicity property that describes this tradeoff in a particular family of
distributions, without providing any quantitative guarantees. Some works in
cryptography [Lyubashevsky, 2012, Zheng et al., 2021, Agrawal et al., 2022]
have provided upper bounds on the sample complexity in the particular case of
the discrete Gaussian family on a lattice. Even more recently, a concurrent
work [Devevey et al., 2022] demonstrates upper and lower bounds for _exact_
rejection sampling as well as some upper bounds for _approximate_ rejection
sampling for probability distributions on the discrete hypercube. In
contradistinction to these previous works, our results hold for arbitrary
probability distributions and significantly more general $f$-divergences.

##### Smoothed Online Learning

The study of online learning dates back decades with too many references to
list here. A good introduction to the general field can be found in Cesa-
Bianchi and Lugosi [2006]. More recently, there has been a surge of interest
in sequential analogues of statistical learning phenomena [Rakhlin et al.,
2015, 2012, Block et al., 2021]. Due to the statistical and computational
challenges of this regime, however, several works have proposed the _smoothed_
online learning setting [Rakhlin et al., 2011, Haghtalab et al., 2020], with
Haghtalab et al. [2022b], Block et al. [2022] providing statistical rates
defining the difficulty of a smoothed online learning problem and Block et al.
[2022], Haghtalab et al. [2022a], Block and Simchowitz [2022] providing
oracle-efficient algorithms. In this work, we generalize the results of Block
et al. [2022], Haghtalab et al. [2022a] to what we call the $f$-smoothed
online learning setting, where the adversary is constrained to only be smooth
in a weaker sense.

##### Out-of-Distribution Learning

Importance sampling was introduced in Kloek and Van Dijk [1978] and studied
extensively thereafter due to its wide applicability. Again, there are far too
many references in this popular field to include here, but a few standard
treatments are Liu and Liu [2001], Srinivasan [2002], Tokdar and Kass [2010].
Most similar to our work are Chatterjee and Diaconis [2018], Cortes et al.
[2010]. In the first work, the authors precisely compute the sample complexity
of importance sampling to estimate the mean of a given function $f$ under some
target measure $\nu$. They observe that
$\widetilde{\Theta}\left(e^{D_{KL}\left(\nu||\mu\right)}\right)$ samples are
both necessary and sufficient to do this and provide several instantiations of
their main bound. Unfortunately, their bounds are too weak to apply to the
problem of estimating means uniformly over a large function class, as is
required for learning theory. In Cortes et al. [2010], the authors prove upper
bounds on the sample complexity of importance sampling assuming that the
function class $\mathcal{F}$ has finite pseudo-dimension, under both bounded
likelihood and bounded Renyi constraints. They also prove a lower bound.

##  Appendix B Comparison to Importance Sampling for Uniform Mean Estimation

In this appendix, we apply our main result to uniform mean estimation. More
specifically, suppose that the learner has access to
$X_{1},\dots,X_{n}\sim\mu$ independent samples and, for some other measure
$\nu$, wishes to estimate $\mathbb{E}_{Y\sim\nu}\left[f(Y)\right]$ for all
functions $f$ in some class $\mathcal{F}$. A natural quesiton is how large $n$
must be and how close $\nu$ has to be to $\mu$ in order for our estimates to
be within $\varepsilon$ of $\mathbb{E}\left[f(Y)\right]$ with high
probability. In this section, we will compare two common approaches. The first
uses importance sampling, where we take our estimate to be

$\displaystyle
I_{n}(f)=\frac{1}{n}\sum_{i=1}^{n}\frac{d\nu}{d\mu}(X_{i})f(X_{i}),$ (19)

while the second is to use rejection sampling to generate $n^{\prime}$
independent samples from $\nu$ and then simply use the empirical mean of these
samples to estimate $\mathbb{E}_{Y\sim\nu}\left[f(Y)\right]$. We begin by
considering importance sampling.

In the special case where $\mathcal{F}=\\{f\\}$ is a singleton, the following
theorem of Chatterjee and Diaconis [2018] fully answers the question of sample
complexity:

######  Theorem 13 (Theorem 1.1, Chatterjee and Diaconis [2018]).

Suppose that $X_{1},\dots,X_{n}\sim\mu$ are independent and suppose that
$n\geq\exp\left(D_{KL}\left(\nu||\mu\right)\right)$. If $f$ is a real-valued,
measurable function, then it holds that

$\displaystyle\mathbb{E}\left[\left|I_{n}(f)-\mathbb{E}_{\nu}\left[f(Y)\right]\right|\right]\leq\left|\left|f\right|\right|_{L^{2}(\nu)}\left(\left(\frac{e^{D_{KL}\left(\nu||\mu\right)}}{n}\right)^{\frac{1}{4}}+2\sqrt{\mathbb{P}_{Y\sim\nu}\left(\frac{d\nu}{d\mu}(Y)>\sqrt{e^{D_{KL}\left(\nu||\mu\right)}\cdot
n}\right)}\right).$ (20)

Moreover, if $n\leq e^{D_{KL}\left(\nu||\mu\right)}$ then with probability at
least $1-\delta$,

$\displaystyle
I_{n}(1)\leq\sqrt{\frac{n}{e^{D_{KL}\left(\nu||\mu\right)}}}+\frac{\mathbb{P}\left(\frac{d\nu}{d\mu}(Y)\leq\sqrt{e^{D_{KL}\left(\nu||\mu\right)}\cdot
n}\right)}{1-\delta}.$ (21)

Thus Theorem 13 shows that
$\Theta\left(\exp(D_{KL}\left(\nu||\mu\right))\right)$ samples are necessary
and sufficient in order for importance sampling to generate an estimate that
is close in expectation to the true mean. Unfortunately, the above guarantee
is too weak to be applied to large function classes. While Cortes et al.
[2010] provides several bounds on importance sampling that hold uniformly in a
function class with bounded pseudo-dimension, we provide here a generalization
of their result that holds for most Donsker function classes. Before doing
this, we need to define the relevant notion of complexity of the function
class: that of the bracketing number. For more details, see Giné and Nickl
[2021].

######  Definition 14.

Let $\mathcal{F}:\mathcal{X}\to[-1,1]$ be a real-valued function class. Given
real-valued functions $f_{-},f_{+}$, we define the bracket $[f_{-},f_{+}]$ as
the set of functions $f\in\mathcal{F}$ such that $f_{-}\leq f\leq f_{+}$
pointwise. We say that $[f_{-},f_{+}]$ is an $\varepsilon$ bracket with
respect to $\mu$ if
$\left|\left|f_{+}-f_{-}\right|\right|_{L^{2}(\mu)}\leq\varepsilon$. We define
the bracketing number $N_{[]}\left(\mathcal{F},\varepsilon\right)$ as the
minimal number of $\varepsilon$-brackets such that $\mathcal{F}$ is contained
in the union of these brackets. Finally, we say that $\mathcal{F}$ has finite
bracketing integral if

$\displaystyle\int_{0}^{2}\sqrt{\log
N_{[]}\left(\mathcal{F},\varepsilon\right)}d\varepsilon<\infty.$ (22)

While there are more general complexity assumptions under which our
conclusions hold, for the sake of simplicity, we consider the bracketing
integral. We have the following result:

######  Theorem 15.

Suppose that $\mathcal{F}:\mathcal{X}\to[-1,1]$ is a real-valued function
class with finite bracketing integral with respect to $\mu$. Suppose further
that $\chi^{2}\left(\nu||\mu\right)<\infty$. Then the following inequality
holds:

$\displaystyle\mathbb{E}\left[\sup_{f\in\mathcal{F}}\left|I_{n}(f)-\mathbb{E}_{\nu}\left[f(Y)\right]\right|\right]\lesssim\sqrt{1+\chi^{2}\left(\nu||\mu\right)}\cdot\max\left(n^{-1/3},\sqrt{\frac{1+\chi^{2}\left(\nu||\mu\right)}{n}}\cdot\int_{0}^{2}\sqrt{\log
N_{[]}\left(\mathcal{F},\alpha\right)}d\alpha\right).$ (23)

The proof of Theorem 15 rests on the following result. For future reference,
we denote by $P_{n}$ the empirical measure on $n$ independently sampled points
from $\mu$.

######  Theorem 16 (Theorem 1.1 from Bercu et al. [2002]).

Suppose that $\mathcal{F}$ is a real valued function class with finite bracket
numbers satisfying

$\displaystyle
E_{\mathcal{F}}=\sup_{n>0}\mathbb{E}\left[\sup_{f\in\mathcal{F}}\max\left(P_{n}\left(f-\mathbb{E}_{\mu}[f]\right),0\right)\right]<\infty.$
(24)

For any $\delta>0$ and $\alpha>\sqrt{2}$, there exist constants $\theta,n_{0}$
depending on $\delta$ and $\alpha$ such that

$\displaystyle\mathbb{P}\left(\sup_{f\in\mathcal{F}}\frac{P_{n}(f-\mathbb{E}_{\mu}\left[f\right])}{\sqrt{P_{n}\left(f-\mathbb{E}_{\mu}[f]\right)^{2}}}\geq\frac{x+E_{\mathcal{F}}}{\sqrt{n}}\right)\leq
e^{-\frac{x^{2}}{4\alpha^{2}(1+\delta)}}$ (25)

for all $n\geq n_{0}$ and $x\leq\theta\sqrt{n}$.

We observe that Giné and Nickl [2021, Theorem 3.5.13] tells us that, up to a
constant, $E$ is bounded by the bracketing integral of $\mathcal{F}$. We are
now ready to prove our importance sampling bound:

###### Proof of Theorem 15.

We will apply Theorem 16 to the function class

$\displaystyle\widetilde{\mathcal{F}}=\frac{d\nu}{d\mu}\cdot\mathcal{F}=\left\\{x\mapsto\frac{d\nu}{d\mu}(x)\cdot
f(x)|f\in\mathcal{F}\right\\}.$ (26)

We first note that Cauchy-Schwarz tells us that if $[f_{-},f_{+}]$ is an
$\varepsilon$-bracket for $\mu$ then $\left[\frac{d\nu}{d\mu}\cdot
f_{-},\frac{d\nu}{d\mu}\cdot f_{+}\right]$ is a
$(\sqrt{1+\chi^{2}\left(\nu||\mu\right)}\cdot\varepsilon)$-bracket for $\mu$.
We further note that

$\displaystyle I_{n}(f)=P_{n}\left(\frac{d\nu}{d\mu}\cdot f\right)$
$\displaystyle\mathbb{E}_{\nu}\left[f(Y)\right]\mathbb{E}_{\mu}\left[\frac{d\nu}{d\mu}\cdot
f\right].$ (27)

Now note that it suffices to prove an upper tail bound and symmetry will imply
a lower tail bound as well. We will apply Theorem 16, but first we must bound
the relevant quantities. Observe that Giné and Nickl [2021, Theorem 3.5.13]
implies that $E_{\mathcal{F}}$ is bounded by the bracketing integral of
$\mathcal{F}$; combining this with our observation on the relationship between
$\varepsilon$-brackets of $\mathcal{F}$ and those of
$\widetilde{\mathcal{F}}$, we see that

$\displaystyle
E_{\widetilde{\mathcal{F}}}\lesssim\sqrt{1+\chi^{2}\left(\nu||\mu\right)}\cdot\int_{0}^{2}\sqrt{\log
N_{[]}\left(\mathcal{F},\alpha\right)d\alpha}.$ (28)

We further observe by Cauchy-Schwartz that

$\displaystyle\sqrt{P_{n}\left(f-\mathbb{E}_{\mu}[f]\right)^{2}}$
$\displaystyle\leq 2\cdot\sqrt{P_{n}\left(\frac{d\nu}{d\mu}\cdot
f\right)^{2}+\mathbb{E}_{\mu}\left[\left(\frac{d\nu}{d\mu}\cdot
f\right)^{2}\right]}$ (29) $\displaystyle\leq
2\cdot\sqrt{P_{n}\left(\frac{d\nu}{d\mu}\right)^{2}\cdot
P_{n}(f)^{2}+(1+\chi^{2}\left(\nu||\mu\right))\cdot\mathbb{E}_{\mu}\left[f^{2}\right]}$
(30) $\displaystyle\leq
2\cdot\sqrt{P_{n}\left(\frac{d\nu}{d\mu}^{2}\right)+1+\chi^{2}\left(\nu||\mu\right)},$
(31)

where we used the fact that $\mathcal{F}$ is uniformly bounded. We further
note by Markov’s inequality that

$\displaystyle\mathbb{P}\left(P_{n}\left(\frac{d\nu}{d\mu}\right)^{2}>u^{2}\right)\leq\frac{1+\chi^{2}\left(\nu||\mu\right)}{u^{2}}.$
(32)

By Theorem 16, it holds that

$\displaystyle\mathbb{P}\left(\sup_{f\in\mathcal{F}}I_{n}(f)-\mathbb{E}_{\nu}\left[f\right]>t\text{
and }P_{n}\left(\frac{d\nu}{d\mu}\right)^{2}\leq
u^{2}\right)\leq\exp\left(-C\left(\sqrt{\frac{n}{1+u^{2}+\chi^{2}\left(\nu||\mu\right)}}\cdot
t-E_{\widetilde{\mathcal{F}}}\right)^{2}\right).$ (33)

Now, setting

$\displaystyle u=n^{\frac{1}{6}}\cdot
t^{\frac{2}{3}}\cdot\sqrt{1+\chi^{2}\left(\nu||\mu\right)}$ (34)

we see that as long as

$\displaystyle t\geq C\sqrt{\frac{1+\chi^{2}\left(\nu||\mu\right)}{n}}\cdot
E_{\widetilde{\mathcal{F}}},$ (35)

it holds that

$\displaystyle\mathbb{P}\left(\sup_{f\in\mathcal{F}}I_{n}(f)-\mathbb{E}_{\nu}\left[f\right]>t\text{
and }P_{n}\left(\frac{d\nu}{d\mu}\right)^{2}\leq u^{2}\right)\leq
C\exp\left(-C\frac{n^{2/3}t^{2/3}}{(1+\chi^{2}\left(\nu||\mu\right))}\right).$
(36)

Applying (32), we see that

$\displaystyle\mathbb{P}\left(\sup_{f\in\mathcal{F}}I_{n}(f)-\mathbb{E}_{\nu}\left[f\right]>t\right)$
$\displaystyle\leq\frac{1}{n^{1/3}\cdot
t^{4/3}}+C\exp\left(-C\frac{n^{2/3}t^{2/3}}{(1+\chi^{2}\left(\nu||\mu\right))}\right).$
(37)

The same result holds for the lower tail by applying the identical argument to
$-\mathcal{F}$. To conclude, we observe that

$\displaystyle\mathbb{E}\left[\sup_{f\in\mathcal{F}}\left|I_{n}(f)-\mathbb{E}_{\nu}\left[f\right]\right|\right]$
$\displaystyle=\int_{0}^{\infty}\mathbb{P}\left(\sup_{f\in\mathcal{F}}\left|I_{n}(f)-\mathbb{E}_{\nu}\left[f\right]\right|>t\right)dt$
(38)
$\displaystyle\lesssim\sqrt{\frac{1+\chi^{2}\left(\nu||\mu\right)}{n}}\cdot
E_{\widetilde{\mathcal{F}}}+\frac{\sqrt{1+\chi^{2}\left(\nu||\mu\right)}}{n^{\frac{1}{3}}}$
(39)
$\displaystyle\lesssim\sqrt{1+\chi^{2}\left(\nu||\mu\right)}\cdot\max\left(n^{-1/3},\sqrt{\frac{1+\chi^{2}\left(\nu||\mu\right)}{n}}\cdot\int_{0}^{2}\sqrt{\log
N_{[]}\left(\mathcal{F},\alpha\right)}d\alpha\right)$ (40)

as desired. ∎

Note that as $n\uparrow\infty$, the rates given by Theorem 15 scale like
$O\left(n^{-1/3}\right)$. One improvement on these rates follows from the work
of Cortes et al. [2010], where they assume that the function class
$\mathcal{F}$ has finite pseudo-dimension and obtain rates that scale like
$O\left(n^{-3/8}\right)$; note that the property of a class having finite
bracketing integral is distinct from that of having finite pseudo-dimension;
indeed van Handel [2013, Proposition 1.7] shows that bracketing numbers can be
arbitrarily large even for classes of finite VC dimension, whereas Giné and
Nickl [2021] shows that classes with infinite VC dimension such as Sobolev
spaces still may have small bracketing numbers. In Cortes et al. [2010,
Proposition 2], the authors show a lower bound for importance sampling
assuming that $\frac{d\nu}{d\mu}$ is uniformly bounded and the sample size is
large relative to this uniform bound. In essence, this shows that if
$\chi^{2}\left(\nu||\mu\right)$ is infinite, then we cannot hope to get an
importance sampling estimator that converges to the population mean at a
$\Theta\left(n^{-\frac{1}{2}}\right)$ rate. We leave as an interesting
direction for future research the problem of closing the gap between these two
rates.

We now turn to our second estimator: using rejection sampling to produce
independent samples from $\nu$ and taking the sample mean. More precisely,
given $X_{1},\dots,X_{n}\sim\mu$ independent and for some $m\in\mathbb{N}$
dividing $n$, suppose we partition $[n]$ into sets of size $m$ and conduct the
rejection sampling procedure of Theorem 3 on each subset, generation $n/m$
independent samples $X_{1}^{\prime},\dots,X_{n/m}^{\prime}\sim\nu_{M}$
independent with probability at least $1-n\delta$ for some $\delta$. For given
$m,n$, let

$\displaystyle J_{m,n}(f)=\frac{m}{n}\cdot\sum_{i=1}^{n/m}f(X_{i}^{\prime})$
(41)

denote the rejection sampling estimate of $\mathbb{E}_{\nu}\left[f(Y)\right]$.
We have the following result:

######  Corollary 17.

Suppose that $\mathcal{F}:\mathcal{X}\to[-1,1]$ is a real-valued function
class with finite bracketing integral with respect to $\mu$ and that
$D_{f}\left(\nu||\mu\right)<\infty$. Suppose further that for some
$\frac{1}{2}>\varepsilon>0$,

$\displaystyle m\geq
4\log\left(\frac{1}{\varepsilon}\right)\cdot(f^{\prime})^{-1}\left(\frac{D_{f}\left(\nu||\mu\right)}{\varepsilon}\right).$
(42)

Then it holds that

$\displaystyle\mathbb{E}\left[\sup_{g\in\mathcal{F}}\left|J_{m,n}(g)-\mathbb{E}_{\nu}\left[g(Y)\right]\right|\right]\lesssim\left(\int_{0}^{2}\sqrt{\log
N_{[]}\left(\mathcal{F},\alpha\right)}d\alpha\right)\cdot\sqrt{\frac{m}{n}}+2\varepsilon$
(43)

###### Proof.

We begin by invoking Theorem 3 and observing that we may choose
$X_{1}^{\prime},\dots,X_{n/m}^{\prime}\sim\widetilde{\nu}$ independent for
some $\widetilde{\nu}$ satisfying
$\operatorname{TV}\left(\widetilde{\nu},\nu\right)\leq\varepsilon$. Observe
that by Giné and Nickl [2021, Theorem 3.5.13], it holds that

$\displaystyle\mathbb{E}\left[\sup_{g\in\mathcal{F}}\left|J_{m,n}(g)-\mathbb{E}_{\widetilde{\nu}}\left[g(\widetilde{Y})\right]\right|\right]\lesssim\sqrt{\frac{m}{n}}\cdot\left(\int_{0}^{2}\sqrt{\log
N_{[]}\left(\mathcal{F},\alpha\right)}d\alpha\right).$ (44)

Now, noting that $g$ takes values in $[-1,1]$, we see that

$\displaystyle\mathbb{E}\left[\sup_{g\in\mathcal{F}}\left|\mathbb{E}_{\widetilde{\nu}}\left[g(\widetilde{Y})\right]-\mathbb{E}_{\nu}\left[g(Y)\right]\right|\right]\leq
2\cdot\operatorname{TV}\left(\widetilde{\nu},\nu\right)\leq 2\varepsilon.$
(45)

The result follows. ∎

Rescaling, we see that Corollary 17 tells us that if we wish to apply the
estimator (41), we need

$\displaystyle
n=\Theta\left(\frac{\log\left(\frac{1}{\varepsilon}\right)\cdot(f^{\prime})^{-1}\left(\frac{D_{f}\left(\nu||\mu\right)}{\varepsilon}\right)}{\varepsilon^{2}}\cdot\left(\int_{0}^{2}\sqrt{\log
N_{[]}\left(\mathcal{F},\alpha\right)}d\alpha\right)^{2}\right)$ (46)

samples in order for our estimate to be within $\varepsilon$ of the true
population mean, uniformly in the function class $\mathcal{F}$. In the special
case where our $f$-divergence is $\chi^{2}\left(\nu||\mu\right)$, we see that
$\widetilde{\Theta}\left(\chi^{2}\left(\nu||\mu\right)\cdot\varepsilon^{-3}\right)$
samples suffice to recover a uniform estimate of the mean within $\varepsilon$
error. Note that this matches the rate given by importance sampling: according
to Theorem 15,
$O\left(\chi^{2}\left(\nu||\mu\right)\cdot\varepsilon^{-3}\right)$ samples
suffice to recover $\varepsilon$-accurate uniform estimates in expectation in
the same situation. On the other hand, Corollary 17 applies to arbitrary
$f$-divergences and thus is significantly more general; we defer to future
work the question of when Theorem 15 can be extended to more general
$f$-divergences. We observe, however, that the analysis of the rejection-
sampling estimator is essentially tight while that of the importance sampling
estimator is potentially loose. One case where importance sampling improves on
rejection sampling is when $\mathcal{F}$ has finite pseudo-dimension; in this
case, the results of Cortes et al. [2010, Theorem 3] tell us that
$\widetilde{O}\left(\sqrt{\chi^{2}\left(\nu||\mu\right)}\cdot\varepsilon^{-8/3}\right)$
samples suffice for importance sampling, which is strictly better than the
rate for rejection sampling derived above.

##  Appendix C Sequential Complexities and Minimax Regret

In this section, we recall some basic definitions of different notions of
complexity of an online learning problem and how they relate to the regret.
These results will be used throughout Appendix E. Many of the adversarial
complexities were introduced in Rakhlin et al. [2015] and we closely follow
the presentation in that work as well as that in Block et al. [2022]. We begin
by recalling the definition of scale-sensitive VC dimension from Bartlett et
al. [1994]:

######  Definition 18.

Let $\mathcal{F}:\mathcal{X}\to\mathbb{R}$ be a function class. For any
$\alpha>0$ and points $X=\\{x_{1},\dots,x_{m}\\}\subset\mathcal{X}$, we say
that the set of points $X$ shatters $\mathcal{F}$ at scale $\alpha$ with
witnesses $s_{1},\dots,s_{m}\in\mathbb{R}$ if for all $m$-tuples of signs
$\varepsilon=(\varepsilon_{1},\dots,\varepsilon_{m})$, there exists some
$f_{\varepsilon}\in\mathcal{F}$ such that for all $1\leq i\leq m$:

$\displaystyle\varepsilon_{i}(f_{\varepsilon}(x_{i})-s_{i})\geq\frac{\alpha}{2}.$
(47)

We let $\mathrm{vc}\left(\mathcal{F},\alpha\right)$ denote the maximal $m$
such that there exists a set $X$ of size $m$ shattering $\mathcal{F}$ and let
$\mathrm{vc}\left(\mathcal{F}\right)=\sup_{\alpha}\mathrm{vc}\left(\mathcal{F},\alpha\right)$.

It is well known from Kearns and Schapire [1994], Bartlett et al. [1994] that
$\mathrm{vc}\left(\mathcal{F},\alpha\right)$ charaterize the learnability of
$\mathcal{F}$ when the data are independent and identically distributed (i.e.,
the batch setting). Another related quantity is the Rademacher complexity,
defined for some set $x_{1},\dots,x_{n}\in\mathcal{X}$ to be

$\displaystyle\mathfrak{R}_{n}(\mathcal{F})=\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{i=1}^{n}\varepsilon_{i}f(x_{i})\right],$
(48)

where the $\varepsilon_{i}$ are independent Rademacher random variables. The
following result can be found in Rudelson and Vershynin [2006]:

######  Proposition 19.

Let $\mathcal{F}:\mathcal{X}\to[-1,1]$ be a function class. Then it holds that

$\displaystyle\mathfrak{R}_{n}(\mathcal{F})\lesssim\inf_{\gamma>0}\gamma
n+\sqrt{n}\int_{\gamma}^{1}\sqrt{\mathrm{vc}\left(\mathcal{F},\delta\right)}d\delta.$
(49)

A similar result applying to the fully adversarial setting was proved in Block
et al. [2021]. In order to state the analogue precisely, we first recall the
notion of distribution-dependent sequential Rademacher complexity from Rakhlin
et al. [2011]. For a given depth $T$, full binary tree $\mathbf{x}$, with
vertices labelled by elements of some space $\mathcal{X}$ and a path
$\varepsilon\in\left\\{\pm 1\right\\}^{T}$, we denote by
$\mathbf{x}_{t}(\varepsilon)$ the vertex at step $t$ of the path given by
$\varepsilon$ starting at the root that takes the right child at time $s$ if
$\varepsilon_{s}=1$ and the left child otherwise. For a given adversary
producing $x_{1},\dots,x_{T}$, let $P_{x_{1:T}}$ denote the join distribution
of $x_{1},\dots,x_{T}$ and let $p_{t}$ denote the distribution of $x_{t}$
conditional on the history. Define the measure $\rho_{P_{x_{1:T}}}$ on an
ordered pair $(\mathbf{x},\mathbf{x}^{\prime})$ of depth $T$ binary trees with
labels in $\mathcal{X}$ recursively as follows. First sample
$\mathbf{x}_{0},\mathbf{x}_{0}^{\prime}\sim p_{0}$ indpeendently. Now suppose
that $t>0$ anda for any $s<t$, let

$\displaystyle\chi_{s}(\varepsilon)=\begin{cases}\mathbf{x}_{s}(\varepsilon)&\varepsilon_{s}=1\\\
\mathbf{x}_{s}^{\prime}(\varepsilon)&\varepsilon_{s}=-1\end{cases}.$ (50)

Sample $\mathbf{x}_{t}(\varepsilon),\mathbf{x}_{t}^{\prime}(\varepsilon)\sim
p_{t}(\cdot|\chi_{1}(\varepsilon),\dots,\chi_{t-1}(\varepsilon))$
independently and proceed until two depth $T$ binary trees are constructed. We
now define the distribution-dependent sequential Rademacher complexity:

######  Definition 20 (Definition 2 from Rakhlin et al. [2011]).

Let $\mathcal{F}:\mathcal{X}\to[-1,1]$ be a function class and fix a
distribution $P_{x_{1:T}}$ on tuples $(x_{1},\dots,x_{T})$. We define the
distribution-dependent sequential Rademacher complexity as follows:

$\displaystyle\mathfrak{R}^{\mathrm{seq}}_{T}\left(\mathcal{F},P_{x_{1:T}}\right)=\mathbb{E}_{(\mathbf{x},\mathbf{x}^{\prime})\sim\rho_{P_{x_{1:T}}}}\left[\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}f(\mathbf{x}_{t}(\varepsilon))\right]\right].$
(51)

For a given class of distributions $\mathscr{D}=\left\\{P_{x_{1:T}}\right\\}$,
define

$\displaystyle\mathfrak{R}^{\mathrm{seq}}_{T}\left(\mathcal{F},\mathscr{D}\right)=\sup_{P_{x_{1:T}}\in\mathscr{D}}\mathfrak{R}^{\mathrm{seq}}_{T}\left(\mathcal{F},P_{x_{1:T}}\right).$
(52)

Note that if $\mathscr{D}$ is the set of all distributions on $\mathcal{X}$
then the notion of standard, sequential Rademacher complexity from Rakhlin et
al. [2015] is recovered. The reason for introducing this admittedly technical
notion of complexity is the following result:

######  Theorem 21 (Theorem 3 and Lemma 20 from Rakhlin et al. [2011]).

Let $\mathcal{F}:\mathcal{X}\to[-1,1]$ be a function class and
$\ell:[-1,1]\times[-1,1]\to[0,1]$ a loss function Lipschitz in the first
argument. Suppose that we are in the online learning setting described in
Section 4 and the adversary is constrained to choose $x_{1:T}$ according to
some distribution in $\mathscr{D}$. Then there exists an algorithm such that

$\displaystyle\mathbb{E}\left[\operatorname{Reg}_{T}\right]\lesssim\mathfrak{R}^{\mathrm{seq}}_{T}(\mathcal{F},\mathscr{D}).$
(53)

Returning to combinatorial notions of complexity, Rakhlin et al. [2015]
introduced the following sequential analogue of the scale-sensitive VC
dimension:

######  Definition 22.

Let $\mathcal{F}:\mathcal{X}\to\mathbb{R}$ be a function class. For any
$\alpha>0$ and complete binary tree $\mathbf{x}$ of depth $m$, we say that
$\mathcal{F}$ is shattered by $\mathbf{x}$ with witness (complete binary) tree
$\mathbf{s}\in\mathbb{R}^{\left|\mathbf{x}\right|}$ if for all $m$-tuples of
signs $\varepsilon=(\varepsilon_{1},\dots,\varepsilon_{n})$, there exists some
$f_{\varepsilon}\in\mathcal{F}$ such that for all $1\leq i\leq m$, it holds
that

$\displaystyle\varepsilon_{i}\left(f_{\varepsilon}(\mathbf{x}_{i}(\varepsilon))-\mathbf{s}_{i}(\varepsilon)\right)\geq\frac{\alpha}{2}.$
(54)

We let $\mathrm{fat}\left(\mathcal{F},\alpha\right)$, the sequential fat-
shattering dimension, denote the maximal $m$ such that there exists a tree
$\mathbf{x}$ of depth $m$ that shatters $\mathcal{F}$.

Note that in general
$\mathrm{fat}\left(\mathcal{F},\alpha\right)\gg\mathrm{vc}\left(\mathcal{F},\alpha\right)$
and the difference can be infinite, as is the case for thresholds on the unit
interval for example. For finite domains $\mathcal{X}$, however, a reverse
bound is possible. We make use of the following result:

######  Lemma 23 (Lemma 21 from Block et al. [2022]).

Let $\mathcal{F}:\mathcal{X}\to[-1,1]$ be a function class and let
$\mathrm{fat}\left(\mathcal{F},\alpha\right)$ denote the sequential fat-
shattering dimension at scale $\alpha$. Then there exist universal constants
$C,c$ such that for any $\beta>0$, the following inequality holds:

$\displaystyle\mathrm{fat}\left(\mathcal{F},\alpha\right)\leq
C\cdot\mathrm{vc}\left(\mathcal{F},c\beta\alpha\right)\cdot\log^{1+\beta}\left(\frac{C\left|\mathcal{X}\right|}{\mathrm{vc}\left(\mathcal{F},c\alpha\right)\alpha}\right).$
(55)

In order to relate these notions of complexity back to the problem at hand, we
make use of the following result:

######  Proposition 24 (Corollary 18 from Block et al. [2021]).

Let $\mathcal{F}:\mathcal{X}\to[-1,1]$ be a function class. For any
distribution $P_{x_{1:T}}$, the following bound holds:

$\displaystyle\mathfrak{R}^{\mathrm{seq}}_{T}\left(\mathcal{F},P_{x_{1:T}}\right)\lesssim\inf_{\gamma>0}\gamma
T+\sqrt{T}\int_{\gamma}^{1}\sqrt{\mathrm{fat}\left(\mathcal{F},\delta\right)}d\delta.$
(56)

Combining Proposition 24 and Lemma 23 implies the following result from Block
et al. [2022]:

######  Lemma 25.

Suppose that we are in the situation of Proposition 24 and, furthermore,
$\left|\mathcal{X}\right|<\infty$. Then for any $P_{x_{1:T}}$, the following
holds:

$\displaystyle\mathfrak{R}^{\mathrm{seq}}_{T}\left(\mathcal{F},P_{x_{1:T}}\right)\lesssim\inf_{\begin{subarray}{c}\beta,\gamma>0\end{subarray}}\gamma
T+\sqrt{T\cdot\log^{1+\beta}(\left|\mathcal{X}\right|)}\int_{\gamma}^{1}\sqrt{\mathrm{vc}\left(\mathcal{F},c\beta\delta\right)\cdot\log^{1+\beta}\left(\frac{1}{\mathrm{vc}\left(\mathcal{F},c\delta\right)\delta}\right)}d\delta.$
(57)

##  Appendix D Proofs from Section 3

###  D.1 Upper Bounds

In this section, we prove the main upper bound, Theorem 3. We begin by stating
and proving the standard gaurantees for rejection sampling for the sake of
completeness.

######  Lemma 26.

Let $\mu,\nu$ be two measures on $(\mathcal{X},\mathscr{F})$ and suppose that
$X\sim\mu$. Suppose that $\mu,\nu$ satisfy the condition that for some
$M<\infty$, $\left|\left|\frac{d\nu}{d\mu}\right|\right|_{\infty}\leq M$. Let
$\xi$ be a binary-valued random variable such that, conditional on $X$, the
probability that $\xi=1$ is given by $\frac{1}{M}\frac{d\nu}{d\mu}(X)$. Then
$\mathbb{P}(\xi=1)=\frac{1}{M}$ and for any $A\in\mathscr{F}$, it holds that

$\displaystyle\mathbb{P}\left(X\in A|\xi=1\right)=\nu(A).$ (58)

Thus, if $X_{1},\dots,X_{n}$ are sampled independently from $\mu$ and
$\xi_{1},\dots,\xi_{n}$ are constructed as above, with probability at least
$1-e^{-\frac{n}{M}}$ at least one of the $\xi_{j}$ is equal to 1.

###### Proof.

To prove the first statement, by the tower property of conditional
expectation, we see that

$\displaystyle\mathbb{P}\left(\xi=1\right)=\mathbb{E}\left[\frac{1}{M}\frac{d\nu}{d\mu}(X)\right]=\frac{1}{M}$
(59)

by the definition of the Radon-Nikodym derivative. To prove the second
statement, we see that

$\displaystyle\mathbb{P}\left(X\in A|\xi=1\right)$
$\displaystyle=\frac{\mathbb{P}\left(X\in A\text{ and
}\xi=1\right)}{\mathbb{P}(\xi=1)}$ (60)
$\displaystyle=M\cdot\mathbb{P}\left(X\in A\text{ and }\xi=1\right)$ (61)
$\displaystyle=M\cdot\mathbb{E}\left[\mathbb{I}[X\in
A]\frac{1}{M}\frac{d\nu}{d\mu}(X)\right]$ (62) $\displaystyle=\nu(A)$ (63)

as desired. Finally, the last statement follows because

$\displaystyle\mathbb{P}\left(\xi_{j}=1\text{ for some }j\right)$
$\displaystyle=1-\mathbb{P}\left(\xi_{j}=0\text{ for all }j\right)$ (64)
$\displaystyle=1-\prod_{j=1}^{n}\left(1-\mathbb{P}\left(\xi_{j}=1\right)\right)$
(65) $\displaystyle=1-\left(1-\frac{1}{M}\right)^{n}$ (66) $\displaystyle\geq
1-e^{-\frac{n}{M}}$ (67)

as desired. ∎

Unfortunately, Lemma 26 requires a uniform bound on the likelihood ratio,
which is precisely what we are hoping to avoid. To proceed, we prove a key
change of measure lemma:

######  Lemma 27.

Let $\mu,\nu$ be probability measures on some set $\mathcal{X}$ and let
$Y\sim\nu$. For any $f$ satisfying the conditions in Definition 1 and for any
$M>1$, the following inequality holds:

$\displaystyle\mathbb{P}\left(\frac{d\nu}{d\mu}(Y)>M\right)\leq\frac{D_{f}\left(\nu||\mu\right)}{f^{\prime}(M)}.$
(68)

###### Proof of Lemma 27.

Note that Lemma 27 does not follow from Markov’s inequality because we are
interested in bounding the probability under $\nu$ that the likelihood ratio
is large, while the $f$-divergence is defined as an expectation under $\mu$.
Instead, we apply Fubini’s theorem to account for this change of measure.

If $f^{\prime}(M)=0$ then there is nothing to prove. Otherwise,
$f^{\prime}(M)>0$ by our assumptions and, as $f^{\prime}$ is monotone
increasing, we have that $f^{\prime}$ is injective on $[M,\infty)$. We now
note that the definition of a Radon-Nikodym derivative and Fubini’s theorem
ensure that

$\displaystyle\mathbb{P}\left(\frac{d\nu}{d\mu}(Y)>M\right)=\mathbb{E}\left(\mathbb{I}\left[\frac{d\nu}{d\mu}(X)>M\right]\frac{d\nu}{d\mu}(X)\right)=\int_{M}^{\infty}\mathbb{P}\left(\frac{d\nu}{d\mu}(X)>t\right)dt$
(69)

where $X\sim\mu$. We compute:

$\displaystyle f^{\prime}(M)\mathbb{P}\left(\frac{d\nu}{d\mu}(Y)>M\right)$
$\displaystyle=f^{\prime}(M)\int_{M}^{\infty}\mathbb{P}\left(\frac{d\nu}{d\mu}(X)>t\right)dt$
(70)
$\displaystyle\leq\int_{M}^{\infty}f^{\prime}(t)\mathbb{P}\left(\frac{d\nu}{d\mu}(X)>t\right)dt$
(71)
$\displaystyle\leq\int_{1}^{\infty}f^{\prime}(t)\mathbb{P}\left(\frac{d\nu}{d\mu}(X)>t\right)dt$
(72)
$\displaystyle\leq\int_{1}^{\infty}\mathbb{P}\left(f\left(\frac{d\nu}{d\mu}(X)\right)>u\right)du$
(73)
$\displaystyle=\mathbb{E}\left[f\left(\frac{d\nu}{d\mu}(X)\right)\mathbb{I}\left[\frac{d\nu}{d\mu}(X)\geq
1\right]\right]$ (74)
$\displaystyle\leq\mathbb{E}\left[f\left(\frac{d\nu}{d\mu}(X)\right)\right]$
(75) $\displaystyle=D_{f}\left(\nu||\mu\right)$ (76)

where the first inequality follows from the fact that $f^{\prime}$ is
nondecreasing for $t\geq M\geq 1$, the second inequality follows from the fact
that $f^{\prime}(t)\geq 0$ for $t\geq 1$, the equality follows by noting that
$f$ is nondecreasing for $t\geq 1$ and setting $u=f(t)$, the second equality
follows by Fubini’s theorem, the last inequality follows from the fact that
$f(t)\geq 0$ for all $t$ and the final equality follows from Definition 1.
Hence, proved. ∎

We are now ready to prove our main upper bound

###### Proof of Theorem 3.

Recall that for any $M\geq 1$, we define $\nu_{M}$ to be a measure on
$\mathcal{X}$ such that

$\displaystyle\frac{d\nu_{M}}{d\mu}(X)=\frac{1}{\mathbb{E}\left[\frac{d\nu}{d\mu}(X)\cdot\mathbb{I}\left[\frac{d\nu}{d\mu}(X)\leq
M\right]\right]}\cdot\frac{d\nu}{d\mu}(X)\cdot\mathbb{I}\left[\frac{d\nu}{d\mu}(X)\leq
M\right].$ (77)

Supposing that $Y\sim\nu$, we see that by construction and Lemma 27,

$\displaystyle\left|\left|\frac{d\nu_{M}}{d\mu}\right|\right|_{\infty}\leq\frac{M}{\mathbb{P}\left(\frac{d\nu}{d\mu}(Y)\leq
M\right)}\leq\frac{M}{1-\frac{D_{f}\left(\nu||\mu\right)}{f^{\prime}(M)}}=M^{\prime}.$
(78)

Thus, by Lemma 26, if we run rejection sampling on $\nu_{M}$ with samples from
$\mu$ for $n\geq M^{\prime}\log\left(\frac{1}{\delta}\right)$, it holds with
probability at least $1-\delta$ that we will have at least one accepted sample
and that accepted sample will be distributed according to $\nu_{M}$. By
representing total variation as half the $L^{1}$ distance between densities,
explicit computation tells us that if $E$ is measurable and $\nu^{E}$ denotes
the measure $\nu$ conditioned on the event $E$, then
$\operatorname{TV}\left(\nu,\nu^{E}\right)=\nu(E^{c})$. Combining this fact
with Lemma 27 and simplifying, we see that

$\displaystyle\operatorname{TV}\left(\nu_{M},\nu\right)=\mathbb{P}\left(\frac{d\nu}{d\mu}(Y)>M\right)\leq\frac{D_{f}\left(\nu||\mu\right)}{f^{\prime}(M)}.$
(79)

Setting

$\displaystyle
M=(f^{\prime})^{-1}\left(\frac{D_{f}\left(\nu||\mu\right)}{\varepsilon}\right)$
(80)

and noting that this implies that

$\displaystyle M^{\prime}=\frac{M}{1-\varepsilon},$ (81)

we conclude the proof. ∎

We remark here that our proof above actually proves a slightly stronger
statement, which is to say that for any $\delta>0$, there exists a “success”
event $E$ such that $\mu^{\otimes n}(E)\geq 1-\delta$ and the law of
$X_{j^{\ast}}$ conditioned on the event $E$ has total variation distance at
most $\varepsilon$ from the target measure $\nu$, as long as
$\delta,\varepsilon,n$ are such that

$\displaystyle
n\geq\frac{1}{1-\varepsilon}\log\left(\frac{1}{\delta}\right)(f^{\prime})^{-1}\left(\frac{D_{f}\left(\nu||\mu\right)}{\varepsilon}\right).$
(82)

In fact, it is this formulation of the upper bound that will be useful in our
applications.

###  D.2 Lower Bound

In this section, we prove our main lower bound, Theorem 5, as well as the
alternative version, Theorem 6. We begin by observing that any selection rule
$j^{\ast}$ has a Radon-Nikodym derivative that is bounded above with respect
to $\mu$:

######  Lemma 28.

Suppose that $X_{1},\dots,X_{n}\sim\mu$ are independent and let $j^{\ast}$ be
a selection rule such that $P_{X_{j^{\ast}}}=\widetilde{\nu}$. Then it holds
that

$\displaystyle\left|\left|\frac{d\widetilde{\nu}}{d\mu}\right|\right|_{L^{\infty}(\mu)}\leq
n.$ (83)

###### Proof.

Let $A\in\mathscr{F}$ be a measurable set and let $\widetilde{\nu}$ denote the
law of $X_{j^{\ast}}$. We then observe

$\displaystyle\widetilde{\nu}\left(A\right)$
$\displaystyle=\sum_{j=1}^{n}\mathbb{P}\left(X_{j}\in A\text{ and
}j^{\ast}=j\right)$ (84)
$\displaystyle=\sum_{j=1}^{n}\mu(A)\cdot\mathbb{P}\left(j^{\ast}=j|X_{j}\in
A\right)$ (85)
$\displaystyle=\mu(A)\cdot\sum_{j=1}^{n}\mathbb{P}\left(j^{\ast}=j|X_{j}\in
A\right)$ (86) $\displaystyle\leq n\cdot\mu(A).$ (87)

The above computation holds for all $A\in\mathscr{F}$ and so the result holds.
∎

With Lemma 28 proved, we see that it suffices to turn our attention to those
distributions with bounded likelihood ratios with respect to the base measure.
To prove our lower bounds, we will separate our analysis into two cases. The
easier case is that of linear $f$, i.e., those $f$ with bounded $f^{\prime}$.
We have the following bound:

######  Lemma 29.

Suppose that $f$ is a convex function as in Definition 1 satisfying

$\displaystyle\lim_{t\to\infty}f^{\prime}(t)=C<\infty.$ (88)

For any $0<\Delta\leq C+f(0)$, there exists some $\varepsilon>0$ depending
only on $C,\Delta$, and $f$ such that there exist distributions satisfying
$D_{f}\left(\nu||\mu\right)=\Delta$ and

$\displaystyle\inf_{\widetilde{\nu}\text{ such that
}\left|\left|\frac{d\widetilde{\nu}}{d\mu}\right|\right|<\infty}\operatorname{TV}\left(\widetilde{\nu},\nu\right)>\varepsilon.$
(89)

###### Proof.

Fix some nonatomic $\nu$ and, for some $\varepsilon<1$ to be determined, fix
$A\in\mathscr{F}$ such that $\nu(A)=\varepsilon$. Define $\mu$ such that

$\displaystyle\frac{d\mu}{d\nu}(X)=\mathbb{I}\left[Z\not\in
A\right]\frac{1}{1-\varepsilon}.$ (90)

Observe that this defines a valid likelihood ratio and note that by
definition,

$\displaystyle D_{f}\left(\nu||\mu\right)=f(1-\varepsilon)+\varepsilon
f^{\prime}(\infty)=f(1-\varepsilon)+\varepsilon C.$ (91)

As $f$ is continuous as $\varepsilon\downarrow 0$ and $f(1)=0$, it holds that
$D_{f}\left(\nu||\mu\right)$ traverses continuously between $C+f(0)$ and 0 as
$\varepsilon$ moves between $0$ and $1$. Thus, the intermediate value theorem
tells us that there exists some $\varepsilon$ such that
$D_{f}\left(\nu||\mu\right)=\Delta$. For this $\varepsilon$, we note that
$\widetilde{\nu}(A)=0$ for any $\widetilde{\nu}$ that is absolutely continuous
with respect to $\mu$. Thus,

$\displaystyle\operatorname{TV}\left(\widetilde{\nu},\nu\right)\geq\left|\widetilde{\nu}(A)-\nu(A)\right|=\varepsilon>0$
(92)

and the result follows. ∎

We can now state and prove the formal version of Proposition 4:

######  Theorem 30.

Suppose that $f$ is a convex function as in Definition 1 satisfying

$\displaystyle\lim_{t\to\infty}f^{\prime}(t)=C<\infty.$ (93)

For any $0<\Delta,\leq C+f(0)$, there exists some $\varepsilon>0$ depending
only on $C,\Delta,$ and $f$ such that there exist distributions $\mu,\nu$ with
$D_{f}\left(\nu||\mu\right)=\Delta$ satisfying the following property: if
$X_{1},\dots,X_{n}\sim\mu$ are independent, then

$\displaystyle\inf_{j^{\ast}}\operatorname{TV}\left(P_{X_{j^{\ast}}},\nu\right)\geq\varepsilon$
(94)

where the infimum is over all selection rules $j^{\ast}$.

###### Proof.

By Lemmas 28 and 29, it holds that

$\displaystyle\inf_{j^{\ast}}\operatorname{TV}\left(P_{X_{j^{\ast}}},\nu\right)\geq\inf_{\widetilde{\nu}\text{
such that
}\left|\left|\frac{d\widetilde{\nu}}{d\nu}\right|\right|<\infty}\operatorname{TV}\left(\widetilde{\nu},\nu\right)\geq\varepsilon.$
(95)

The result follows. ∎

Note that Theorem 30 implies that if $D_{f}\left(\cdot||\cdot\right)$ is too
coarse a notion of similarity then approximate sampling from $\nu$ using $\mu$
can be impossible.

We turn now to the more complicated case, that of superlinear $f$. We begin by
showing that the $\mathcal{E}_{\gamma}$-divergence, defined in Example 4,
provides a lower bound on the total variation between the law of a selection
rule and the target measure:

######  Lemma 31.

Let $\mu,\nu$ be measures and for some $\gamma\geq 1$, let
$\mathcal{E}_{\gamma}$ denote the divergence given in Example 4. Then it holds
that

$\displaystyle\inf_{\left|\left|\frac{d\widetilde{\nu}}{d\mu}\right|\right|_{L^{\infty}(\mu)}\leq\gamma}\operatorname{TV}\left(\widetilde{\nu},\nu\right)\geq\mathcal{E}_{\gamma}(\nu||\mu).$
(96)

###### Proof.

Observe that for any $\widetilde{\nu}$ satisfying
$\left|\left|\frac{d\widetilde{\nu}}{d\nu}\right|\right|_{\infty}\leq\gamma$,
it holds that

$\displaystyle\operatorname{TV}\left(\widetilde{\nu},\nu\right)$
$\displaystyle=\sup_{A\in\mathscr{F}}\left|\nu(A)-\widetilde{\nu}(A)\right|$
(97)
$\displaystyle=\sup_{A\in\mathscr{F}}\left|\mathbb{E}\left[\mathbb{I}[X\in
A]\left(\frac{d\nu}{d\mu}(X)-\frac{d\widetilde{\nu}}{d\mu}(X)\right)\right]\right|$
(98)
$\displaystyle\geq\mathbb{E}\left[\mathbb{I}\left[\frac{d\nu}{d\mu}(X)>\gamma\right]\left(\frac{d\nu}{d\mu}(X)-\gamma\right)\right]$
(99)
$\displaystyle=\mathbb{E}\left[\left(\frac{d\nu}{d\mu}(X)-\gamma\right)_{+}\right]$
(100) $\displaystyle=\mathcal{E}_{\gamma}\left(\nu||\mu\right).$ (101)

∎

We are now prepared to prove Theorem 5:

###### Proof of Theorem 5.

We observe that by comining Lemmas 28 and 31, it suffices to exhibit two
measures $\mu,\nu$ such that $\mathcal{E}_{n}(\nu||\mu)>\varepsilon$ and
$D_{f}\left(\nu||\mu\right)$ is bounded. We let $\mu=\operatorname{Ber}(q)$
and $\nu=\operatorname{Ber}(p)$, for

$\displaystyle q=\frac{\varepsilon}{n},$ $\displaystyle p=2\varepsilon.$ (102)

We observe that

$\displaystyle\frac{1-p}{1-q}=\frac{1-2\varepsilon}{1-\frac{\varepsilon}{n}}\in\left[\frac{1}{2},1\right]$
(103)

by the assumption that $\varepsilon\leq\frac{1}{4}$. Thus, for $n\geq 1$, we
see that

$\displaystyle\mathcal{E}_{n}(\nu||\mu)=q\left(\frac{p}{q}-n\right)=\varepsilon.$
(104)

We similarly compute that

$\displaystyle D_{f}\left(\nu||\mu\right)=q\cdot
f\left(\frac{p}{q}\right)+(1-q)f\left(\frac{1-p}{1-q}\right)\leq\frac{\varepsilon}{n}\cdot
f(2n)+f\left(\frac{1}{2}\right),$ (105)

where the inequality follows by the convexity of $f$ and the above
computation. We now observe that by convexity of $f$, we have

$\displaystyle 0=f(1)\geq f(x)+(1-x)f^{\prime}(x)$ (106)

implies that $\frac{f(x)}{x-1}\leq f^{\prime}(x)$ for all $x>1$. Thus,

$\displaystyle D_{f}\left(\nu||\mu\right)\leq 2\varepsilon
f^{\prime}(2n)+f\left(\frac{1}{2}\right).$ (107)

Note that if

$\displaystyle
n<\frac{1}{2}(f^{\prime})^{-1}\left(\frac{\delta}{2\varepsilon}\right),$ (108)

then $D_{f}\left(\nu||\mu\right)\leq\delta$ and so we have exhibited a pair
$(\nu,\mu)$ as desired. The result follows. ∎

We turn now to the proof of Theorem 6. As stated in the main paper, the method
is similar up to the point of exhibiting distributions $\mu,\nu$ with large
$\mathcal{E}_{n}\left(\nu||\mu\right)$. We have the following result:

######  Lemma 32.

Suppose that $f$ is a convex function as in Definition 1 such that
$f(0)<\infty$ and for some $\zeta>0$, the function

$\displaystyle t\mapsto\frac{tf^{\prime\prime}(t)}{(f^{\prime}(t))^{1+\zeta}}$
(109)

is decreasing for sufficiently large $t$ and tends to 0 as $t\uparrow\infty$.
Then for sufficiently large $n$, there exist distributions $\mu,\nu$ such that
$D_{f}\left(\nu||\mu\right)<\infty$ and

$\displaystyle\mathcal{E}_{n}(\nu||\mu)\geq\frac{1}{8}\cdot\left(\frac{\zeta
D_{f}\left(\nu||\mu\right)}{f^{\prime}(n)}\right)^{1+\zeta}.$ (110)

###### Proof.

We first provide a rough intuition for the result. Ideally, we want to
construct a pair of distributions such that $D_{f}(\nu\|\mu)<\infty$ and for
all $\gamma\geq\gamma_{0}$ we have

$\mathcal{E}_{\gamma}(\nu\|\mu)=\frac{C}{f^{\prime}(\gamma)}\,.$

Note that Polyanskiy [2010, (2.144)] shows that
$\frac{d}{d\gamma}\mathcal{E}_{\gamma}(\nu\|\mu)=-\mathbb{P}\left(\frac{d\nu}{d\mu}(X)\geq\gamma\right)$,
where $X\sim\mu$. Thus, we see that our goal is to construct a pair of
distributions such that

$\displaystyle\mathbb{P}\left(\frac{d\nu}{d\mu}(X)\geq\gamma\right)=C\cdot\frac{f^{\prime\prime}(\gamma)}{(f^{\prime}(\gamma))^{2}}.$
(111)

Though by a simple change of variable we see that the expression on the right-
hand side is integrable at $\infty$, it does not have to be monotone (hence
the extra assumption on $f$). Even if it is monotone, however, it can be seen
that $D_{f}(\nu\|\mu)$ is not finite. Thus, we slightly tweak this
construction below.

Fix $\delta,\beta,\zeta>0$ with $\delta<n$ and let

$\displaystyle F(t)=\begin{cases}0&t<0\\\ 1-\frac{\beta
f^{\prime\prime}\left((f^{\prime})^{-1}(\delta)\right)}{\delta^{2+\zeta}}&0\leq
t<(f^{\prime})^{-1}(\delta)\\\ 1-\frac{\beta
f^{\prime\prime}(t)}{(f^{\prime}(t))^{2+\zeta}}&t\geq(f^{\prime})^{-1}(\delta)\end{cases}.$
(112)

We claim that $F$ is a valid cumulative distribution function for properly
chosen $\beta,\delta,\zeta>0$. To begin with, we note that $F$ is right
continuous by construction. It is similarly clear that $F(t)\downarrow 0$ as
$t\downarrow 0$. If $\delta$ is sufficiently large such that

$\displaystyle t\mapsto\frac{tf^{\prime\prime}(t)}{f^{\prime}(t)^{2+\zeta}}$
(113)

is decreasing for all $t>\delta$ (such a $\delta$ always exists by the
assumption in the statement), we see that $F(t)$ is nondecreasing. Finally, to
see that $F(t)\uparrow 1$ as $t\uparrow\infty$, note that

$\displaystyle\int_{(f^{\prime})^{-1}(\delta)}^{\infty}\frac{\beta
f^{\prime\prime}(t)}{f^{\prime}(t)^{2+\zeta}}dt$
$\displaystyle=\lim_{N\uparrow\infty}\left(\frac{\beta}{(1+\zeta)\delta^{1+\zeta}}-\frac{\beta}{(1+\zeta)(f^{\prime})^{-1}(N)^{1+\zeta}}\right)$
(114) $\displaystyle=\frac{\beta}{(1+\zeta)\delta^{1+\zeta}}$ (115)

by the assumption that $f^{\prime}(t)\uparrow\infty$ as $t\uparrow\infty$. In
particular, it holds that

$\displaystyle\lim_{t\uparrow\infty}\frac{\beta
f^{\prime\prime}(t)}{f^{\prime}(t)^{2+\zeta}}=0$ (116)

and so $F(t)$ is a cumulative distribution function. Note further that if a
random variable on the nonnegative real line $Z$ is distributed according to
$F$, then by Fubini’s theorem,

$\displaystyle\mathbb{E}\left[Z\right]$
$\displaystyle=\int_{(f^{\prime})^{-1}(\delta)}^{\infty}\beta\frac{f^{\prime\prime}(t)}{(f^{\prime}(t))^{2+\zeta}}dt$
(117) $\displaystyle=\frac{\beta}{(1+\zeta)\delta^{1+\zeta}}.$ (118)

Thus if $\beta=(1+\zeta)\delta^{1+\zeta}$ then $\mathbb{E}[Z]=1$. Thus with
this choice of $\beta$, we let $\mu$ be nonatomic on some set $\mathcal{X}$
and let $\frac{d\nu}{d\mu}(X)$ be distributed according to $F$, where
$X\sim\mu$. We first compute the $f$-divergence between $\nu$ and $\mu$ using
Fubini’s theorem:

$\displaystyle D_{f}\left(\nu||\mu\right)$
$\displaystyle=\mathbb{E}\left[f\left(\frac{d\nu}{d\mu}(X)\right)\right]$
(119) $\displaystyle=\mathbb{E}\left[f(Z)\right]$ (120)
$\displaystyle=f(0)\mathbb{P}\left(Z=0\right)+\int_{(f^{\prime})^{-1}(\delta)}^{\infty}f^{\prime}(t)\mathbb{P}\left(Z>t\right)dt$
(121) $\displaystyle=f(0)\left(1-\frac{\beta
f^{\prime\prime}\left((f^{\prime})^{-1}(\delta)\right)}{\delta^{2+\zeta}}\right)+\int_{(f^{\prime})^{-1}(\delta)}^{\infty}\frac{\beta
f^{\prime\prime}(t)}{f^{\prime}(t)^{1+\zeta}}dt$ (122)
$\displaystyle=f(0)\left(1-\frac{\beta
f^{\prime\prime}\left((f^{\prime})^{-1}(\delta)\right)}{\delta^{2+\zeta}}\right)+\frac{\beta}{\zeta\delta^{\zeta}}$
(123) $\displaystyle\leq f(0)+\frac{1+\zeta}{\zeta}\cdot\delta,$ (124)

where we used the fact that the second derivative of a convex function is
nonnegative and out computation of $\beta=(1+\zeta)\delta^{1+\zeta}$ above. If
we take $\delta,\zeta$ such that $f(0)\leq\frac{1+\zeta}{\zeta}\cdot\delta$,
then we have

$\displaystyle D_{f}\left(\nu||\mu\right)\leq 2\frac{1+\zeta}{\zeta}\delta.$
(125)

Again by Fubini’s theorem, using the fact that $n>\delta$, we see that

$\displaystyle\mathbb{E}\left[\frac{d\nu}{d\mu}\mathbb{I}\left[\frac{d\nu}{d\mu}>n\right]\right]$
$\displaystyle=\int_{n}^{\infty}\frac{\beta
f^{\prime\prime}(t)}{(f^{\prime}(t))^{2+\zeta}}dt$ (126)
$\displaystyle=\frac{\beta}{(1+\zeta)f^{\prime}(n)^{1+\zeta}}.$ (127)

Finally, note that

$\displaystyle n\mathbb{P}\left(\frac{d\nu}{d\mu}>n\right)=\frac{n\beta
f^{\prime\prime}(n)}{f^{\prime}(n)^{2+\zeta}}.$ (128)

Putting everything together, we see that

$\displaystyle\mathcal{E}_{n}\left(\nu||\mu\right)$
$\displaystyle\geq\frac{\beta}{(1+\zeta)f^{\prime}(n)^{1+\zeta}}-\frac{n\beta
f^{\prime\prime}(n)}{f^{\prime}(n)^{2+\zeta}}$ (129)
$\displaystyle=\frac{\delta^{1+\zeta}}{f^{\prime}(n)^{1+\zeta}}-\frac{n(1+\zeta)\delta^{1+\zeta}f^{\prime\prime}(n)}{f^{\prime}(n)^{2+\zeta}}$
(130)
$\displaystyle=\left(\frac{\delta}{f^{\prime}(n)}\right)^{1+\zeta}\cdot\left(1-\frac{n(1+\zeta)f^{\prime\prime}(n)}{f^{\prime}(n)}\right)$
(131)
$\displaystyle\geq\left(\frac{\zeta}{2(1+\zeta)}\cdot\frac{D_{f}\left(\nu||\mu\right)}{f^{\prime}(n)}\right)^{1+\zeta}\cdot\left(1-\frac{n(1+\zeta)f^{\prime\prime}(n)}{f^{\prime}(n)}\right).$
(132)

By the assumption in the statement, for sufficiently large $n$, we have

$\displaystyle\frac{nf^{\prime\prime}(n)}{f^{\prime}(n)^{1+\zeta}}<\frac{1}{4}$
(133)

and thus the result holds. ∎

We remark that the requirement that $f(0)<\infty$ is relatively weak, but does
not hold for some important $f$-divergences. This requirement, however, could
be easily removed by placing the atom at $\frac{1}{2}$ instead of at 0 in the
above proof; for the sake of simplicity we do not expand on this here, as it
leads to a more intricate proof with little additional clarity. We now state
and prove a formal version of Theorem 6:

######  Theorem 33.

Let $f$ be a convex function as in Definition 1 with $f(0)<\infty$ and let
$\zeta>0$ be arbitrary. Suppose that there is some $t_{0}>0$ such that the
function

$\displaystyle t\mapsto\frac{tf^{\prime\prime}(t)}{(f^{\prime}(t))^{1+\zeta}}$
(134)

is non-increasing for all $t>t_{0}$ and

$\displaystyle\lim_{t\uparrow\infty}\frac{tf^{\prime\prime}(t)}{(f^{\prime}(t))^{1+\zeta}}=0.$
(135)

Then there exist distributions $\mu,\nu$ with
$D_{f}\left(\nu||\mu\right)<\infty$ such that if $X_{1},\dots,X_{n}\sim\mu$
are independent then

$\displaystyle\inf_{j^{\ast}}\operatorname{TV}\left(P_{X_{j^{\ast}}},\nu\right)\geq\frac{1}{8}\left(\frac{\zeta
D_{f}\left(\nu||\mu\right)}{f^{\prime}(n)}\right)^{1+\zeta}$ (136)

where the infimum is over all selection rules.

###### Proof.

The result follows by combining Lemmas 28 ,31, and 32. ∎

We observe that for essentially all common suplerlinear $f$-divergences, such
as KL-divergence and Renyi divergences, the assumptions on the function
defined in (134) hold.

##  Appendix E Proofs from Section 4

###  E.1 Proof of Proposition 8

Let $\mu$ denote the uniform measure on the unit interval and for each $t$,
let $p_{t}=(1-\delta)\mu+\delta q_{t}$ for some $q_{t}$ to be defined. Suppose
that $f^{\prime}(\infty)=C<\infty$. Note that independent of $q_{t}$, it holds
that

$\displaystyle D_{f}\left(\nu||\mu\right)\leq\delta f^{\prime}(\infty)=\delta
C$ (137)

Thus if the adversary samples $x_{t}$ from $p_{t}$, and $\delta\leq\sigma/C$,
the adversary is $(f,\sigma)$-smooth. Now, define $\bar{x}_{t}$ for $1\leq
t<\infty$ as follows. Let $\bar{x}_{1}=\frac{1}{2}$ and let
$\varepsilon_{1},\varepsilon_{2},\dots$ be independent Rademacher random
variables. Let

$\displaystyle\bar{x}_{t}=\frac{1}{2}+\sum_{s=1}^{t-1}\varepsilon_{s}2^{-s-1}$
(138)

and note that $\bar{x}_{t}\in[0,1]$ for all $t$ almost surely. Furthermore,
note that $\bar{x}_{t}\to\bar{x}_{\infty}$ almost surely and define
$\theta^{\ast}=\bar{x}_{\infty}$. Let
$y_{t}=\mathbb{I}[x_{t}\geq\theta^{\ast}]$ for all $t$ and note that this
adversary is realizable, i.e., there exists some $f\in\mathcal{F}$ that
attains zero regret. Let $q_{t}$ denote an atom at $\bar{x}_{t}$ and suppose
that the adversary plays $x_{t}\sim p_{t}$. As mentioned above, this adversary
is $f$-smooth. Note that whenever $x_{t}=\bar{x}_{t}$, it holds that
$y_{t}=\frac{1-2\varepsilon_{t}}{2}$. By independence of $\varepsilon_{t}$,
then, it holds for any $T$ that

$\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\mathbb{I}[y_{t}\neq\widehat{y}_{t}]\right]$
$\displaystyle\geq\sum_{t=1}^{T}\mathbb{P}\left(x_{t}=\bar{x}_{t}\right)\mathbb{P}\left(\widehat{y}_{t}\neq
y_{t}|x_{t}=\bar{x}_{t}\right)$ (139)
$\displaystyle=\sum_{t=1}^{T}\delta\cdot\frac{1}{2}$ (140)
$\displaystyle=\frac{\delta T}{2}.$ (141)

The result follows.

###  E.2 Proof of Lemma 9

We proceed as in Haghtalab et al. [2022b], Block et al. [2022], but apply our
Theorem 3 instead of the standard rejection sampling bound. We begin by
sampling $Z_{t,j}$ independently for all $1\leq t\leq T$ and $1\leq j\leq n$.
Applying Theorem 3 on the distribution of $x_{t}$ conditioned on the history
and then using Definition 7 to bound $D_{f}\left(P_{x_{t}}||\mu\right)$
concludes the proof.

###  E.3 Minimax Regret for $f$-Smoothed Online Learning

In this section we prove a generalization of Theorem 10 to arbitrary function
classes. We follow the proof technique of Block et al. [2022] with the
exception of using our new rejection sampling coupling from Lemma 9. We have
the following result:

######  Theorem 34.

Let $\mathcal{F}:\mathcal{X}\to[-1,1]$ be a real-valued function class and let
$\mathrm{vc}\left(\mathcal{F},\alpha\right)$ denote its scale-sensitive VC
dimension. Suppose that $\ell:[-1,1]\times[-1,1]\to[0,1]$ is a loss function
that is Lipschitz in the first argument. Further, let $f$ be a convex function
as in Definition 1 such that $f^{\prime}(\infty)=\infty$. If an adversary is
$(f,\sigma)$-smooth in the sense of Section 4, then there are universal
constants $c,C>0$ such that there exists an algorithm with
$\mathbb{E}\left[\operatorname{Reg}_{T}\right]$ bounded above by the following
expression:

$\displaystyle
C\cdot\inf_{\beta,\gamma,\varepsilon>0}(\varepsilon+\gamma)T+\sqrt{T\log^{1+\beta}\left(T(f^{\prime})^{-1}\left(\frac{1}{\sigma\varepsilon}\right)\right)}\int_{\gamma}^{1}\sqrt{\mathrm{vc}\left(\mathcal{F},c\beta\delta\right)\cdot\log^{1+\beta}\left(\frac{1}{\mathrm{vc}\left(\mathcal{F},c\delta\right)\delta}\right)}d\delta.$
(142)

###### Proof.

Applying Theorem 21, we see that it is enough to control
$\mathfrak{R}^{\mathrm{seq}}_{T}(\mathcal{F},\mathscr{D})$, where
$\mathscr{D}$ is the class of $(f,\sigma)$-smooth adversaries. Fix some
$\frac{1}{2}\geq\alpha,\delta>0$ and let $\Pi$ denote a coupling between
$x_{1},\dots,x_{T}$ and $\left\\{Z_{t,j}|1\leq t\leq T,1\leq j\leq n\right\\}$
guaranteed by Lemma 9 such that

$\displaystyle n\geq
2\log\left(\frac{T}{\delta}\right)(f^{\prime})^{-1}\left(\frac{1}{\alpha\sigma}\right),$
(143)

the $Z_{t,j}\sim\mu$ are independent, and with probability at least
$1-\delta$, there are selection rules $j^{\ast}_{t}$ such that
$\operatorname{TV}\left(P_{x_{t}},P_{Z_{t,j^{\ast}_{t}}}\right)\leq\alpha$.
Denote by $\mathcal{E}$ the event that these selection rules exist and note
that $\mathbb{P}(\mathcal{E})\geq 1-\delta$. We now fix some $P_{x_{1:T}}$ and
compute:

$\displaystyle\mathfrak{R}^{\mathrm{seq}}_{T}\left(\mathcal{F},P_{x_{1:T}}\right)$
$\displaystyle=\mathbb{E}_{\begin{subarray}{c}\rho_{P_{x_{2:T}}}\\\
\varepsilon\end{subarray}}\left[\sup_{g\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}g(\mathbf{x}_{t}(\varepsilon))\right]$
(144)
$\displaystyle=\mathbb{E}_{\Pi,\varepsilon}\left[\sup_{g\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}g(\mathbf{x}_{t}(\varepsilon))\right]$
(145)
$\displaystyle=\mathbb{E}_{\Pi,\varepsilon}\left[\mathbb{I}[\mathcal{E}]\sup_{g\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}g(\mathbf{x}_{t}(\varepsilon))\right]+\mathbb{E}_{\Pi,\varepsilon}\left[\mathbb{I}\left[\mathcal{E}^{c}\right]\sup_{g\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}g(\mathbf{x}_{t}(\varepsilon))\right].$
(146)

For the second term, note that almost surely,

$\displaystyle\sup_{g\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}g(\mathbf{x}_{t}(\varepsilon))\leq
T$ (147)

and thus

$\displaystyle\mathbb{E}_{\Pi,\varepsilon}\left[\mathbb{I}\left[\mathcal{E}^{c}\right]\sup_{g\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}g(\mathbf{x}_{t}(\varepsilon))\right]\leq\delta
T.$ (148)

For the other term, we observe that

$\displaystyle\mathbb{E}_{\Pi,\varepsilon}\left[\mathbb{I}[\mathcal{E}]\sup_{g\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}g(\mathbf{x}_{t}(\varepsilon))\right]$
$\displaystyle\leq\mathbb{E}_{\Pi,\varepsilon}\left[\mathbb{I}[\mathcal{E}]\sup_{g\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}g(\mathbf{x}_{t}(\varepsilon))-\varepsilon_{t}g\left(Z_{t,j^{\ast}_{t}}\right)\right]$
(149)
$\displaystyle+\mathbb{E}_{\Pi,\varepsilon}\left[\mathbb{I}[\mathcal{E}]\sup_{g\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}g\left(Z_{t,j^{\ast}_{t}}\right)\right].$
(150)

For thefirst term, we see that

$\displaystyle\mathbb{E}_{\Pi,\varepsilon}\left[\mathbb{I}[\mathcal{E}]\sup_{g\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}g(\mathbf{x}_{t}(\varepsilon))-\varepsilon_{t}g\left(Z_{t,j^{\ast}_{t}}\right)\right]$
$\displaystyle\leq\sum_{t=1}^{T}\mathbb{E}_{\Pi,\varepsilon}\left[\sup_{g\in\mathcal{F}}\varepsilon_{t}g(\mathbf{x}_{t}(\varepsilon))-\varepsilon_{t}g\left(Z_{t,j^{\ast}_{t}}\right)\right]$
(151) $\displaystyle\leq T\max_{1\leq t\leq
T}\operatorname{TV}\left(P_{\mathbf{x}_{t}(\varepsilon)},P_{Z_{t,j^{\ast}_{t}}}\right)$
(152) $\displaystyle\leq\alpha T$ (153)

by construction. For the second term, we use Jensen’s inequality and the tower
property of conditional expectations to compute:

$\displaystyle\mathbb{E}_{\Pi,\varepsilon}\left[\mathbb{I}[\mathcal{E}]\sup_{g\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}g\left(Z_{t,j^{\ast}_{t}}\right)\right]$
$\displaystyle\leq\mathbb{E}_{\Pi,\varepsilon}\left[\sup_{g\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}g\left(Z_{t,j^{\ast}_{t}}\right)\right]$
(154)
$\displaystyle=\mathbb{E}_{Z_{t,j}}\left[\mathbb{E}_{\varepsilon}\left[\sup_{g\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}g\left(Z_{t,j^{\ast}_{t}}\right)|\left\\{Z_{t,j}\right\\}\right]\right]$
(155)
$\displaystyle=\mathbb{E}_{Z_{t,j}}\left[\mathbb{E}_{\varepsilon}\left[\sup_{g\in\mathcal{F}_{\left\\{Z_{t,j}\right\\}}}\sum_{t=1}^{T}\varepsilon_{t}g\left(Z_{t,j^{\ast}_{t}}\right)|\left\\{Z_{t,j}\right\\}\right]\right].$
(156)

Noting that $\left|\left\\{Z_{t,j}\right\\}\right|=Tn$, we may now apply Lemma
25 to conclude that this last display is upper bounded by:

$\displaystyle\inf_{\begin{subarray}{c}\beta,\gamma>0\end{subarray}}\gamma
T+\sqrt{T\cdot\log^{1+\beta}(nT)}\int_{\gamma}^{1}\sqrt{\mathrm{vc}\left(\mathcal{F},c\beta\delta\right)\cdot\log^{1+\beta}\left(\frac{1}{\mathrm{vc}\left(\mathcal{F},c\delta\right)\delta}\right)}d\delta.$
(157)

Setting $\delta=\frac{1}{T}$ and combining (148), (153), and (157) concludes
the proof. ∎

###  E.4 Oracle-Efficient Algorithms

In this section, we turn to computationally tractable algorithms. In
particular, we are interested in algorithms that make only polynomially many
calls to an Empirical Risk Minimization (ERM) oracle defined below. Note that
ERM oracles are common models of computational access in the online learning
community [Kalai and Vempala, 2005, Hazan and Koren, 2016, Block et al., 2022,
Haghtalab et al., 2022a] due both to the fact that they suffice for learning
in the statistical setting (where data appear independently) and because there
are popular computational heuristics for implementing these oracles in many
problems of interest. We will consider two algorithms: an improper algorithm
requiring two oracle calls per round achieving regret that scales with the
Rademacher complexity (see (48)) and a proper algorithm requiring one oracle
call per round. Both of the algorithms were proposed in Block et al. [2022]
and we use a similar analysis to bound their regret, with the modification of
replacing the coupling from Block et al. [2022] with our more general version,
Lemma 9. We begin by defining the ERM oracle:

######  Definition 35.

We assume that the learner has access to $\mathsf{ERMOracle}$, which, given a
set of tuples $(x_{1},y_{1}),\dots,(x_{m},y_{m})\in\mathcal{X}\times[-1,1]$, a
list of weights $w_{1},\dots,w_{m}\in\mathbb{R}$, and a sequence of
$[0,1]$-valued loss functions $\ell_{1},\dots,\ell_{m}$, returns some
$\widehat{g}\in\mathcal{F}$ satisfying

$\displaystyle\sum_{i=1}^{m}w_{i}\ell_{i}\left(\widehat{g}(x_{i}),y_{i}\right)\leq\inf_{g\in\mathcal{F}}\sum_{i=1}^{m}w_{i}\ell_{i}(f(x_{i}),y_{i}).$
(158)

A slightly weaker assumption allows for some approximation, where
$\mathsf{ERMOracle}$ returns some $\widehat{g}$ that is $\varepsilon$-close to
the actual minimizer. For the sake of simplicity, we restrict our focus to
exact oracles here, but all of our results apply to the more general setting
up to an additive $\varepsilon T$ with essentially no modification of the
proofs.

####  E.4.1 Improper Algorithm through Relaxations

We now turn to the first oracle-efficient algorithm, motivated by the
relaxations framework of Rakhlin et al. [2012]. We closely follow the
presentation of Block et al. [2022]. To begin, we define a relaxation:

######  Definition 36.

For a fixed horizon $T$, function class $\mathcal{F}$, context space
$\mathcal{X}$, and measure $\mu$, we say that a sequence of relaxations
$\mathbf{Rel}_{T}\left(\mathcal{F}|x_{1},y_{1}\dots,x_{t},y_{t}\right):\mathcal{X}^{\times
t}\times[-1,1]^{\times t}\to\mathbb{R}$ is a relaxation if for any sequence
$x_{1},\dots,x_{T}$ and for any $1\leq t\leq T$, the following two properties
hold:

$\displaystyle-\inf_{g\in\mathcal{F}}\sum_{t=1}^{T}\ell(g(x_{t}),y_{t})$
$\displaystyle\leq\mathbf{Rel}_{T}\left(\mathcal{F}|x_{1},y_{1}\dots,x_{T},y_{T}\right)$
(159) $\displaystyle\sup_{p_{t}}\mathbb{E}_{x_{t}\sim
p_{t}}\inf_{q_{t}\in\Delta([-1,1])}\sup_{y_{t}^{\prime}\in[-1,1]}\left\\{\mathbb{E}_{\widehat{y}_{t}\sim
q_{t}}[\ell(\widehat{y}_{t},y_{t}^{\prime})]+\mathbf{Rel}_{T}\left(\mathcal{F}|x_{1},y_{1}\dots,x_{t}^{\prime},y_{t}^{\prime}\right)\right\\}$
$\displaystyle\leq\mathbf{Rel}_{T}\left(\mathcal{F}|x_{1},y_{1}\dots,x_{t-1},y_{t-1}\right)$
(160)

where the first supremum is over $(f,\sigma)$-smooth distributions with
respect to $\mu$ and infimum is over distributions on $[-1,1]$.

The key property of relaxations, as proven in Rakhlin et al. [2012,
Proposition 1], is that any strategy $q_{t}$ that guarantees the second
inequality in Definition 36 achieves regret bounded above by
$\mathbf{Rel}_{T}(\mathcal{F}|\emptyset)$. Our first result shows that, with
minor modifications, the relaxation proposed in Block et al. [2022] remains a
valid relaxation in the $f$-smoothed regime.

######  Lemma 37.

Suppose that the adversary is $(f,\sigma)$-smoothed and that the loss function
$\ell$ is convex and Lipschitz in the first argument. Let
$0<\alpha\leq\frac{1}{2}$ and suppose that

$\displaystyle n\geq
8\log(T)(f^{\prime})^{-1}\left(\frac{1}{\alpha\sigma}\right).$ (161)

Then

$\displaystyle\mathbf{Rel}_{T}\left(\mathcal{F}|x_{1},y_{1}\dots,x_{t},y_{t}\right)=\mathbb{E}_{\mu,\varepsilon}\left[2\sup_{g\in\mathcal{F}}\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-\sum_{s=1}^{t}\ell(g(x_{s}),y_{s})\right]+T\alpha+\frac{T-t}{nT}$
(162)

is a relaxation, where the expectation is with respect to $Z_{s,j}\sim\mu$ and
independent Rademacher random variables.

###### Proof.

We follow the proof technique of Block et al. [2022, Proposition 6], replacing
their Block et al. [2022, Lemma 14] with our Lemma 9. We introduce the same
convenient shorthand:

$L_{t}(g)=\sum_{s=1}^{t}\ell(g(x_{s}),y_{s})$ (163)

for all $g\in\mathcal{F}$. We now note that the first condition of Definition
36 is immediate as
$\mathbf{Rel}_{T}\left(\mathcal{F}|x_{1},y_{1}\dots,x_{T},y_{T}\right)$ is in
fact equal to the infimum on the left hand side of the defining inequality.
Thus it suffices to demonstrate that for all $t$ and all realizations
$x_{1},y_{1},\dots,x_{t-1},y_{t-1}$, the second inequality in Definition 36
holds. We fix some $(f,\sigma$)-smoothed $p_{t}$ and argue for this arbitrary
smoothed distribution. Because the loss function $\ell$ is convex in the first
argument, we may replace the distribution $q_{t}$ from which $\widehat{y}$ is
sampled by its expectation, i.e.,

$\displaystyle\inf_{q_{t}\in\Delta([-1,1])}$
$\displaystyle\sup_{y_{t}^{\prime}\in[-1,1]}\left\\{\mathbb{E}_{\widehat{y}_{t}\sim
q_{t}}[\ell(\widehat{y}_{t},y_{t}^{\prime})]+\mathbf{Rel}_{T}\left(\mathcal{F}|x_{1},y_{1}\dots,x_{t}^{\prime},y_{t}^{\prime}\right)\right\\}$
(164)
$\displaystyle=\inf_{\widehat{y}_{t}\in[-1,1]}\sup_{y_{t}^{\prime}\in[-1,1]}\left\\{\ell(\widehat{y}_{t},y_{t}^{\prime})+\mathbf{Rel}_{T}\left(\mathcal{F}|x_{1},y_{1}\dots,x_{t}^{\prime},y_{t}^{\prime}\right)\right\\}.$
(165)

Now, arguing as in Block et al. [2022], we see that for any
$x_{t}^{\prime}\in\mathcal{X}$,

$\displaystyle\inf_{\widehat{y}_{t}}$
$\displaystyle\sup_{y_{t}^{\prime}}\left\\{\ell(\widehat{y}_{t},y_{t}^{\prime})+\mathbb{E}_{\mu,\varepsilon}\left[\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t}(g)\right]\right\\}$
(166)
$\displaystyle=\inf_{\widehat{y}_{t}}\sup_{y_{t}^{\prime}}\mathbb{E}_{\mu,\varepsilon}\left\\{\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+\ell(\widehat{y}_{t},y_{t}^{\prime})-\ell(g(x_{t}^{\prime}),y_{t}^{\prime})\right\\}$
(167)
$\displaystyle\leq\inf_{\widehat{y}_{t}}\sup_{y_{t}^{\prime}}\mathbb{E}_{\mu,\varepsilon}\left\\{\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+\partial\ell(\widehat{y}_{t},y_{t}^{\prime})\left(\widehat{y}_{t}-g(x_{t}^{\prime})\right)\right\\}$
(168) $\displaystyle\leq\inf_{\widehat{y}_{t}}\max_{\gamma_{t}\in\\{\pm
1\\}}\mathbb{E}_{\mu,\varepsilon}\left\\{\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+\gamma_{t}(\widehat{y}_{t}-g(x_{t}^{\prime}))\right\\},$
(169)

where the first inequality follows from the fact that $\ell$ is convex in the
first argument and the second inequality follows from the fact that $\ell$ is
Lipschitz in the same. We now apply the minimax theorem, where we are forced
to invoke a supremum over distributions on $\\{\pm 1\\}$ due to the lack of
convexity of this set. Following again the argument of Block et al. [2022], we
let $d_{t}$ denote a distribution on $\\{\pm 1\\}$ and sample $\gamma_{t}\sim
d_{t}$. We compute:

$\displaystyle\inf_{\widehat{y}_{t}}$ $\displaystyle\max_{\gamma_{t}\in\\{\pm
1\\}}\mathbb{E}_{\mu,\varepsilon}\left\\{\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+\gamma_{t}(\widehat{y}_{t}-g(x_{t}^{\prime}))\right\\}$
(170)
$\displaystyle=\sup_{d_{t}}\inf_{\widehat{y}_{t}}\mathbb{E}_{\mu,\varepsilon,d_{t}}\left\\{\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+\gamma_{t}(\widehat{y}_{t}-g(x_{t}^{\prime}))\right\\}$
(171)
$\displaystyle\leq\sup_{d_{t}}\mathbb{E}_{\mu,\varepsilon,d_{t}}\left\\{\inf_{\widehat{y}_{t}}\mathbb{E}_{\gamma_{t}^{\prime}\sim
d_{t}}\left[\gamma_{t}^{\prime}\widehat{y}_{t}\right]+\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)-\gamma_{t}\cdot
g(x_{t}^{\prime})\right\\}$ (172)
$\displaystyle\leq\sup_{d_{t}}\mathbb{E}_{\mu,\varepsilon,d_{t}}\left\\{\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+\mathbb{E}_{\gamma_{t}^{\prime}\sim
d_{t}}\left[\gamma_{t}^{\prime}g(x_{t})\right]-\gamma_{t}\cdot
g(x_{t}^{\prime})\right\\}$ (173)
$\displaystyle\leq\sup_{d_{t}}\mathbb{E}_{\mu,\varepsilon,d_{t}}\left\\{\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+2\varepsilon_{t}\gamma_{t}\cdot
g(x_{t}^{\prime})\right\\}$ (174)
$\displaystyle\leq\mathbb{E}_{\mu,\varepsilon,d_{t}}\left\\{\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+2\varepsilon_{t}\cdot
g(x_{t}^{\prime})\right\\},$ (175)

where the penultimate inequality follows from symmetrization and the final
inequality follows from contraction. We now observe that because

$\displaystyle n\geq
8\log(T)(f^{\prime})^{-1}\left(\frac{1}{\alpha\sigma}\right),$ (176)

we have

$\displaystyle n\geq
4\log(nT)(f^{\prime})^{-1}\left(\frac{1}{\alpha\sigma}\right)$ (177)

by the fact that $2\log(n)\leq n$ for all $n>0$. We now apply Lemma 9 and note
that by the definition of $n$, we have a coupling between $x_{t}$ and
$Z_{t,j}$ for $1\leq j\leq n$ such that with probability at least
$1-(nT)^{-2}$, there exists some $j^{\ast}$ such htat
$\operatorname{TV}\left(p_{t},P_{Z_{t,j^{\ast}}}\right)\leq\alpha$; let
$\mathcal{E}$ denote the event that such a $j^{\ast}$ exists. We now use the
fact that $p_{t}$ is smooth and take expectations with respect to the
previously arbitrary $x_{t}^{\prime}\sim p_{t}$. The above work then implies

$\displaystyle\mathbb{E}_{x_{t}^{\prime}\sim p_{t}}$
$\displaystyle\inf_{q_{t}\in\Delta([-1,1])}\sup_{y_{t}^{\prime}\in[-1,1]}\left\\{\mathbb{E}_{\widehat{y}_{t}\sim
q_{t}}[\ell(\widehat{y}_{t},y_{t}^{\prime})]+\mathbf{Rel}_{T}\left(\mathcal{F}|x_{1},y_{1}\dots,x_{t}^{\prime},y_{t}^{\prime}\right)\right\\}$
(178) $\displaystyle\leq\mathbb{E}_{x_{t}^{\prime}\sim
p_{t}}\mathbb{E}_{\mu,\varepsilon,d_{t}}\left\\{\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+2\varepsilon_{t}\cdot
g(x_{t}^{\prime})\right\\}$ (179)
$\displaystyle=\mathbb{E}_{x_{t}^{\prime}\sim
p_{t}}\mathbb{E}_{\mu,\varepsilon,d_{t}}\left\\{\mathbb{I}[\mathcal{E}]\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+2\varepsilon_{t}\cdot
g(x_{t}^{\prime})\right\\}$ (180)
$\displaystyle+\mathbb{E}_{x_{t}^{\prime}\sim
p_{t}}\mathbb{E}_{\mu,\varepsilon,d_{t}}\left\\{\mathbb{I}[\mathcal{E}^{c}]\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+2\varepsilon_{t}\cdot
g(x_{t}^{\prime})\right\\}.$ (181)

Note that for the second term above, the expression in the integrand is at
most $n(T-t+1)$ and thus

$\displaystyle\mathbb{E}_{x_{t}^{\prime}\sim p_{t}}$
$\displaystyle\mathbb{E}_{\mu,\varepsilon,d_{t}}\left\\{\mathbb{I}[\mathcal{E}^{c}]\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+2\varepsilon_{t}\cdot
g(x_{t}^{\prime})\right\\}$ (182)
$\displaystyle\leq\mathbb{P}\left(\mathcal{E}^{c}\right)\cdot
n(T-t+1)\leq\frac{1}{nT}$ (183)

For the first term, we have

$\displaystyle\mathbb{E}_{x_{t}^{\prime}\sim p_{t}}$
$\displaystyle\mathbb{E}_{\mu,\varepsilon,d_{t}}\left\\{\mathbb{I}[\mathcal{E}]\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+2\varepsilon_{t}\cdot
g(x_{t}^{\prime})\right\\}$ (184)
$\displaystyle=\mathbb{E}_{x_{t}^{\prime}\sim
p_{t}}\mathbb{E}_{\mu,\varepsilon,d_{t}}\left\\{\mathbb{I}[\mathcal{E}]\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+2\varepsilon_{t}\cdot
g(Z_{t,j^{\ast}})+2\varepsilon_{t}(g(x_{t}^{\prime})-g(Z_{t,j^{\ast}}))\right\\}$
(185) $\displaystyle\leq
2\operatorname{TV}\left(p_{t},P_{Z_{t,j^{\ast}}}\right)+\mathbb{E}_{x_{t}^{\prime}\sim
p_{t}}\mathbb{E}_{\mu,\varepsilon,d_{t}}\left\\{\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+2\varepsilon_{t}\cdot
g(Z_{t,j^{\ast}})\right\\}.$ (186)

The first term above is at most $2\alpha$. For the second term, we apply
Jensen’s inequality and get

$\displaystyle\mathbb{E}_{x_{t}^{\prime}\sim p_{t}}$
$\displaystyle\mathbb{E}_{\mu,\varepsilon,d_{t}}\left\\{\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+2\varepsilon_{t}\cdot
g(Z_{t,j^{\ast}})\right\\}$ (187)
$\displaystyle\leq\mathbb{E}_{x_{t}^{\prime}\sim
p_{t}}\mathbb{E}_{\mu,\varepsilon,d_{t}}\left\\{\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+2\varepsilon_{t}\cdot
g(Z_{t,j^{\ast}})+\sum_{j\neq
j^{\ast}}2\mathbb{E}[\varepsilon_{t,j}g(Z_{t,j})]\right\\}$ (188)
$\displaystyle\leq\mathbb{E}_{x_{t}^{\prime}\sim
p_{t}}\mathbb{E}_{\mu,\varepsilon,d_{t}}\left\\{\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)\right\\}.$
(189)

Thus we see that

$\displaystyle\mathbb{E}_{x_{t}^{\prime}\sim p_{t}}$
$\displaystyle\mathbb{E}_{\mu,\varepsilon,d_{t}}\left\\{\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)+2\varepsilon_{t}\cdot
g(x_{t}^{\prime})\right\\}$ (190)
$\displaystyle\leq\mathbb{E}_{x_{t}^{\prime}\sim
p_{t}}\mathbb{E}_{\mu,\varepsilon,d_{t}}\left\\{\sup_{g\in\mathcal{F}}2\sum_{j=1}^{n}\sum_{s=t}^{T}\varepsilon_{s,j}g(Z_{s,j})-L_{t-1}(g)\right\\}+2\alpha+\frac{n(T-t+1)}{n^{2}T^{2}}.$
(191)

Plugging in the definition of our relaxation from the statement of the lemma
concludes the proof. ∎

While Lemma 37 provides an algorithm for achieving low regret, it is not clear
that it is oracle efficient, due to the necessity of evaluating the
expectation. Thus, as is done in Block et al. [2022], we use the random
playout idea of Rakhlin et al. [2012] to give an oracle efficient algorithm.
Before we proceed, we recall the classical observation that, due to the
convexity in the first argument of the loss function $\ell$, it suffices to
suppose that $\ell$ is linear; indeed, we can simply replace the loss by the
gradient of the loss at each time step and the regret of an algorithm with
this latter feedback upper bounds the regret with the original loss function
due to convexity. For more details on this classical argument, see, for
example, Rakhlin et al. [2012, Section 5] or Haghtalab et al. [2022a, Appendix
G.2]. Thus, we restrict our focus to linear loss and have the following
result:

######  Theorem 38.

Suppose that $\ell$ is a loss function convex and Lipschitz in the first
argument and let $\mathcal{F}:\mathcal{X}\to[-1,1]$ denote a function class.
Consider an algorithm that at each time $t$, samples $Z_{s,j}\sim\mu$ for
$t+1\leq s\leq T$ and $1\leq j\leq n$ and plays

$\displaystyle\widehat{y}_{t}=\operatorname*{argmin}_{\widehat{y}\in[-1,1]}\sup_{y_{t}\in[-1,1]}\left\\{\ell(\widehat{y},y_{t})+\sup_{g\in\mathcal{G}}\left[12\sum_{j=1}^{n}\sum_{s=t+1}^{T}\varepsilon_{s,j}g(Z_{s,j})-\sum_{s=1}^{t}\partial\ell(g(x_{s}),y_{s})\cdot
g(x_{s})\right]\right\\}.$ (192)

Suppose that

$\displaystyle n\geq
8\log(T)\cdot(f^{\prime})^{-1}\left(\frac{1}{\varepsilon\sigma}\right)$ (193)

and the adversary is $(f,\sigma)$-smoothed. Then the learner experiences

$\displaystyle\mathbb{E}\left[\operatorname{Reg}_{T}\right]\leq
2\mathbb{E}_{\mu}\left[\mathfrak{R}_{nT}(\mathcal{F})\right]+\varepsilon T+1.$