# Smoothed Online Learning is as Easy as Statistical Learning

Adam Block
MIT  Yuval Dagan
MIT  Noah Golowich
MIT  Alexander Rakhlin
MIT

###### Abstract

Much of modern learning theory has been split between two regimes: the
classical _offline_ setting, where data arrive independently, and the _online_
setting, where data arrive adversarially. While the former model is often both
computationally and statistically tractable, the latter requires no
distributional assumptions. In an attempt to achieve the best of both worlds,
previous work proposed the smooth online setting where each sample is drawn
from an adversarially chosen distribution, which is _smooth_ , i.e., it has a
bounded density with respect to a fixed dominating measure. Existing results
for the smooth setting were known only for binary-valued function classes and
were computationally expensive in general; in this paper, we fill these
lacunae. In particular, we provide tight bounds on the minimax regret of
learning a nonparametric function class, with nearly optimal dependence on
both the horizon and smoothness parameters. Furthermore, we provide the first
oracle-efficient, no-regret algorithms in this setting. In particular, we
propose an oracle-efficient improper algorithm whose regret achieves optimal
dependence on the horizon and a proper algorithm requiring only a _single_
oracle call per round whose regret has the optimal horizon dependence in the
classification setting and is sublinear in general. Both algorithms have
exponentially worse dependence on the smoothness parameter of the adversary
than the minimax rate. We then prove a lower bound on the oracle complexity of
any proper learning algorithm, which matches the oracle-efficient upper bounds
up to a polynomial factor, thus demonstrating the existence of a statistical-
computational gap in smooth online learning. Finally, we apply our results to
the contextual bandit setting to show that if a function class is learnable in
the classical setting, then there is an oracle-efficient, no-regret algorithm
for contextual bandits in the case that contexts arrive in a smooth manner.

##  1 Introduction

Modern learning theory has primarily focused on two regimes: batch and
sequential settings. In the former, data are independent and learning is easy
while in the latter, Nature has the power to adversarially choose data to make
learning as difficult as possible. Much of the empirical success in machine
learning has derived from assuming that independence is satisfied and applying
the Empirical Risk Minimization (ERM) principle in the batch (offline)
setting, for which algorithms such as gradient descent have been highly
successful even with complex function classes. However, in many settings
independence is likely to fail, and the sequential regime is attractive due to
the minimal assumptions made on the data generating process. Unfortunately, it
suffers from poor algorithmic efficiency and an inability to learn some of the
most basic function classes.

A typical example of the gap in difficulty of learning in these two settings
is furnished by threshold functions on the unit interval. Classical theory
tells us that in the batch setting, due to the combinatorial simplicity of the
function class, a simple ERM approach efficiently and optimally learns the
class of thresholds; in contradistinction, an adversarial data generation
process precludes sequential (online) learning entirely (Lit, 88). One way to
escape the difficulty of adversarial learning is to apply the technique of
_smoothed analysis_ introduced in a now-famous paper by ST (04), which focused
on solving linear programs with the simplex algorithm. In this regime, one
analyzes worst case inputs that are perturbed by a small amount of stochastic
noise. Smoothed analysis in the setting of online learning was first
introduced in RST (11), where the authors showed non-constructively that
thresholds again become learnable in this setting. More recently, a series of
papers (HRS, 20, 21) has demonstrated that the stochastic perturbation has
beneficial effects in far greater generality than the class of thresholds; in
fact, any classification task that is possible in the batch setting is also
statistically tractable in the smoothed online setting.

In the more modern formulation of the smoothed paradigm studied in HRS (20,
21), instead of choosing an input that is then perturbed, the adversary
chooses a distribution that is restricted to be sufficiently anti-concentrated
so as to not put too much mass on the set of “hard” instances. This anti-
concentration (referred to as _$\sigma$ -smoothness_; Definition 1) is
quantified by a parameter $\sigma\leq 1$ that governs how far from independent
the adversary can be. When $\sigma=1$, we are in the batch setting where the
data arrive i.i.d.; as $\sigma$ tends to $0$, the adversary is given more and
more power to choose bad instances, with the limit of $\sigma=0$ being
entirely adversarial.

While we provide a rigorous definition of the problem setting below, we
outline the broad strokes here. We consider learning over the course of $T$
rounds where, at each round, Nature reveals a context $x_{t}$ sampled in a
$\sigma$-smooth manner, the learner reveals a prediction $\widehat{y}_{t}$,
and then Nature reveals $y_{t}$. Given a loss function, the objective of the
learner is to minimize regret to the best predictor in some function class
$\mathcal{F}$. When $\mathcal{F}$ is binary-valued and has finite VC dimension
$d$ (i.e. is learnable in the batch setting), HRS (21) proved that
$O\left(\sqrt{dT\log\left(T/\sigma\right)}\right)$ regret is achievable,
albeit with an inefficient algorithm. Two natural questions arise: can we
extend these results to nonparametric, real-valued classes? and, more
importantly, are there efficient algorithms that can achieve comparable
regret? In this paper, we answer both questions. With regard to the first
question, the natural extension of the covering-based argument in HRS (21)
would yield suboptimal dependence on $\sigma$ in the nonparametric regime;
instead, we obtain a nonconstructive proof through careful application of
combinatorial inequalities and an adaptation of the coupling lemma of HRS
(20).

For the question of practical algorithms, we need to more carefully consider
what we mean by efficiency. Certainly the algorithm of HRS (21) is not
efficient as it requires constructing an $\varepsilon$-net of $\mathcal{F}$ as
a first step, which is exponential in the VC dimension of $\mathcal{F}$. A
natural choice is to look to the batch setting and try to leverage the success
of ERM-based approaches to achieve reasonable runtime, as is done in KV (05);
HK (16); this approach is supported further by the empirical success of
various heuristics for ERM (GBC, 16). As such, we suppose the learner has
access to an _ERM oracle_ (Definition 2) that can efficiently optimize some
loss over our function class $\mathcal{F}$ given as input a dataset; we
analyze the time complexity of our algorithms in terms of the number of calls
to this oracle.

In our algorithmic results, we distinguish between _proper_ and _improper_
learners. Proper learners are required, before seeing $x_{t}$, to output a
hypothesis $\widehat{f}_{t}\in\mathcal{F}$ that is used to produce the
prediction $\widehat{y}_{t}:=\widehat{f}_{t}(x_{t})$, whereas improper
learners can make any prediction $\widehat{y}_{t}$ based on knowledge of
$x_{t}$. There are many settings in which proper (as opposed to improper)
online learning may be desirable for downstream applications, such as learning
in games (DG, 21) and reinforcement learning with function approximation
(FKQR, 21). For proper learners, our oracle time complexity results are
optimal up to a polynomial factor in all parameters; the question of
optimality for improper learning remains an interesting open question.

We now briefly describe our key contributions (which are summarized in Table
1):

  * •

In Section 3 we give tight upper bounds on the statistical rates of learning a
real-valued function class in the smoothed online setting without regard to
computational efficiency, while extending and providing a new proof to the
case of binary classification treated in (HRS, 21, Theorems 3.1 & 3.2). Our
bounds are tight both in their dependence on $T$ and $\sigma$, up to
logarithmic factors, showing that the regret in the smooth setting is only a
factor $\log(T/\sigma)$ away from that in the i.i.d. setting (Theorem 3). In
the process of doing this, we provide in Lemma 14 a more general and much
simpler proof of the key technical step of coupling from HRS (21).

  * •

In Section 4 we present an _improper_ algorithm based on the relaxation method
of RSS (12) with tight dependence on the horizon $T$ but suboptimal dependence
on $\sigma$: in particular, the regret in the smooth setting scales as
$\sigma^{-1/2}$ times that in the i.i.d. setting (Theorem 7). Our algorithm is
efficient in the sense that it requires only $O\left(\sqrt{T}\log T\right)$
oracle calls per round in general and only $2$ oracle calls per round in the
classification setting. We then show in Proposition 8 that the polynomial
dependence on $\sigma$ is not an artifact of our analysis, but rather inherent
to the method.

  * •

In Section 5 we present a _proper_ algorithm based on Follow the Perturbed
Leader (FTPL) that exhibits optimal dependence on $T$ for classification and
suboptimal dependence on $T$ in general (Theorem 10). Further, the algorithm
requires only $1$ oracle call per round. We use a Gaussian white noise with
intensity approximated by $\mu$ as our perturbation, which allows for
optimization without enumeration of experts; to establish correctness, we
overcome a major technical hurdle introduced by the complicated dependence
structure of this perturbation.

  * •

In Section 6 we show that the suboptimality of the FTPL learner is inherent
for oracle-efficient algorithms: in particular, we provide a lower bound based
on the method of HK (16) that demonstrates that any _proper_ algorithm with
access to an ERM oracle requires
$\widetilde{\Omega}\left(\sigma^{-\frac{1}{2}}\right)$ time. Combined with the
upper bound of $\log 1/\sigma$ of Theorem 3, this implies that there exists an
exponential statistical-computational gap in smoothed online learning.

  * •

Finally, in Appendix A, we apply our results to the problem of Contextual
Bandits. We show in Theorem 13 that whenever a function class $\mathcal{F}$ is
learnable offline, we can get vanishing regret in the smooth contextual bandit
setting with an oracle-efficient algorithm.

Reference | Algorithm | Iterations | Oracle calls | Total time
---|---|---|---|---
Theorem 3 |  Non-constructive, _proper_ |  Cls111This bound was shown in HRS (21), though with slightly different log factors.: $\varepsilon^{-2}d\log(1/\sigma)$ Reg: $\varepsilon^{-2}\log(1/\sigma)$ | NA | NA
Theorem 7 |  Relaxation-based, _improper_ |  Cls: $\varepsilon^{-2}d\sigma^{-1}$ Reg: $\varepsilon^{-2}\sigma^{-1}$ |  Cls: $\varepsilon^{-2}d\sigma^{-1}$ Reg: $\varepsilon^{-3}\sigma^{-3/2}$ |  Cls: $\varepsilon^{-4}d^{2}\sigma^{-3}$ Reg: $\varepsilon^{-4}\sigma^{-5/2}$
Theorem 10 |  FTPL, _proper_ |  Cls: $\varepsilon^{-2}d\sigma^{-1}$ Reg: $\varepsilon^{-3}\sigma^{-1}$ |  Cls: $\varepsilon^{-2}d\sigma^{-1}$ Reg: $\varepsilon^{-3}\sigma^{-1}$ |  Cls: $\varepsilon^{-4}d^{2}\sigma^{-5/2}$ Reg: $\varepsilon^{-7}\sigma^{-3}$
Theorems 11 & 52, Corollaries 12 & 53 |  Computational lower bound for any _proper_ alg. | NA |  Cls: $\max\left\\{\sigma^{-1/2}\zeta^{2},\varepsilon^{-2}d\right\\}$ with $\zeta$-approx. oracle |  Cls: $\max\left\\{\sigma^{-1/2},\varepsilon^{-2}d\right\\}$ with exact oracle
Theorem 3.2 from HRS (21) |  Statistical lower bound for any algorithm |  Cls: $\varepsilon^{-2}d\log(1/\sigma)$ Reg: $\varepsilon^{-2}\log(1/\sigma)$ | NA | NA
Table 1: Overview of our main results. For each algorithm/lower bound, the
number of iterations $T$ after which the algorithm achieves regret
$\leq\varepsilon T$ is shown for two cases: (a) Cls: the case of binary
classification for a class $\mathcal{F}$ of VC dimension $d$; (b) Reg: the
case of regression for a class $\mathcal{F}$ with scale-sensitive VC dimension
bounded as $\mathsf{vc}(\mathcal{F},\alpha)\lesssim\alpha^{-p}$, for some
$0<p<2$ (our results extend to the case of $p\geq 2$, which may be found in
the theorem statements). We take $L=1$ and suppress logarithmic factors where
possible.

In an independent and concurrent work, HHSY (22) established several results
similar to our own. In particular, they provided an analysis of an _improper_
algorithm similar to our oracle-efficient improper learner from Section 4, as
well as computational lower bounds similar to those presented in our Section
6. Additionally, they presented an oracle-efficient _proper_ learner in the
case of binary classification that, while based on the principle of FTPL, has
a substantially different analysis than our own in Section 5; note that our
algorithm also applies for general, real-valued function classes in the
nonparametric regime.

We discuss further related work in Appendix B.

##  2 Problem Setup and Notation

In this section we formally define the smoothed online learning setting. We
then introduce some concepts and notation we use throughout the paper.

#### Miscellaneous notation.

For distributions $p,q$ on a measure space $\mathcal{X}$, we write $p\ll q$ if
$p$ is absolutely continuous with respect to $q$. For a positive integer $m$,
let $[m]=\\{1,2,\ldots,m\\}$. For expressions $f,g$ we say $f\lesssim g$ if
there is some universal constant $C$ such that $f\leq Cg$. We also use
$f=O(g)$ to signify the same thing.

###  2.1 Smoothed Online Learning

We consider the setting of smoothed online learning, following HRS (21).
Consider a space $\mathcal{X}$ of covariates equipped with some sigma-algebra.
Let $\mathcal{F}\subset[-1,1]^{\mathcal{X}}$ be a function class and
$\ell:[-1,1]\times[-1,1]\to[0,1]$ be an $L$-Lipschitz, convex loss function
for some $L>0$. Fix some $T\in\mathbb{N}$ denoting the number of rounds of
learning. We consider the following learning setting, making a distinction
between _improper learning_ and _proper learning_ :

  1. 1.

For each $t\in[T]$, nature samples $x_{t}\sim p_{t}$ for some distribution
$p_{t}$ that may depend in any way on the past samples $x_{s}$ for $s<t$ and
the algorithm’s past predictions. Nature also chooses $y_{t}\in[-1,1]$
adversarially (perhaps depending on $x_{t}$) in a similar manner.

  2. 2.

The learner makes a (possibly random) prediction as follows:

     * •

Improper learner: The learner observes $x_{t}$ and makes a prediction
$\widehat{y}_{t}\in[-1,1]$.

     * •

Proper learner: The learner chooses a hypothesis
$\widehat{f}_{t}\in\mathcal{F}$, and its prediction is defined as
$\widehat{y}_{t}:=\widehat{f}_{t}(x_{t})$; the learner then observes $x_{t}$.

  3. 3.

Nature reveals $y_{t}\in[-1,1]$ to the learner, and the learner incurs loss
$\ell(\widehat{y}_{t},y_{t})$.

With no restrictions on $p_{t}$, the above online learning problem has been
extensively studied, and essentially tight rates are known (RST15b, ; BDR,
21); furthermore, exponential lower bounds are known for oracle-efficient
proper learning algorithms (HK, 16). To circumvent these lower bounds, we
consider the smooth setting. Our fundamental assumption (Definition 1 below)
is that there is a distinguished distribution $\mu$ on $\mathcal{X}$,
accessable to the learner through efficient sampling, so that the adversary is
constrained to choose covariates $x_{t}$ according to some distribution with
bounded Radon-Nikodym derivative with respect to $\mu$. This assumption, which
follows that of HRS (20, 21), has been used extensively as well in the
smoothed analysis of local search algorithms (Man, 20) and discrete
optimization problems (BV, 04). We emphasize the assumption that in all cases
the learner has access to $\mu$ through efficient sampling; note that a
typical example to keep in mind is that $\mu$ is uniform on some set, so the
efficient sampling assumption is not very restrictive.

######  Definition 1 (Adaptive smooth distributions).

Let $p,\mu$ be probability measures on a set $\mathcal{X}$. We say that $p$ is
_$\sigma$ -smooth_ with respect to $\mu$ if $p\ll\mu$ and

$\operatorname{ess\,sup}\frac{dp}{d\mu}\leq\frac{1}{\sigma}.$ (1)

Let $\mathfrak{P}(\sigma,\mu)$ denote the class of all distributions $p$ that
are $\sigma$-smooth with respect to $\mu$. We denote this class simply by
$\mathfrak{P}$ when $\sigma,\mu$ are clear from the context. For any
$T\in\mathbb{N}$, we let $\mathfrak{P}_{T}({\sigma},{\mu})$ denote the space
of joint distributions $\mathscr{D}$ on $x_{1},\ldots,x_{T}\in\mathcal{X}$
satisfying the following property: letting $p_{t}$ denote the law of $x_{t}$
conditional on $x_{s}$ for all $s<t$, for all $t\in[T]$,
$p_{t}\in\mathfrak{P}(\sigma,\mu)$ almost surely. Similarly, we let
$\widetilde{\mathfrak{P}}_{T}({\sigma},{\mu})$ denote the space of joint
distributions $\mathscr{D}$ on
$(x_{1},y_{1}),\ldots,(x_{T},y_{T})\in\mathcal{X}\times[-1,1]$ such that if
$p_{t}$ is the law of $x_{t}$ conditional on $(x_{s},y_{s})$ for $s<t$, then
$p_{t}\in\mathfrak{P}(\sigma,\mu)$ almost surely. Note that no constraints are
placed on the distribution of $y_{t}$.

For $\sigma=1$ we recover the notion of the data $x_{1},\ldots,x_{T}$ being
sampled iid from $\mu$; as $\sigma$ tends to zero, the notion of
$\sigma$-smoothness becomes weaker and thus we consider $\sigma$-smoothness as
interpolating between the favorable situation of i.i.d. data and the
unfavorable adversarial situation.

###  2.2 Minimax value

The goal of the learner is to minimize expected regret to the best function in
$\mathcal{F}$, defined as

$\mathbb{E}\left[\operatorname{Reg}_{T}(\mathcal{F})\right]=\mathbb{E}\left[\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})\right]$
(2)

with the expectation taken over both the sampling of $x_{t}\sim p_{t}$ and the
learner’s possibly randomized predictions. For any function class, we consider
the minimax regret for proper and improper learners, respectively, to be the
values
$\mathcal{V}_{T}^{\textrm{prop}}(\mathcal{F},\mathfrak{P}({\sigma},{\mu}))$
and
$\mathcal{V}_{T}^{\textrm{improp}}(\mathcal{F},\mathfrak{P}({\sigma},{\mu}))$,
respectively, where

$\displaystyle\mathcal{V}_{T}^{\textrm{prop}}(\mathcal{F},\mathfrak{P}({\sigma},{\mu}))$
$\displaystyle=\left\langle\inf_{q_{t}\in\Delta(\mathcal{F})}\sup_{p_{t}\in\mathfrak{P}(\sigma,\mu)}\mathbb{E}_{x_{t}\sim
p_{t}}\sup_{y_{t}\in[-1,1]}\mathbb{E}_{\widehat{f}_{t}\sim
q_{t}}\right\rangle_{t=1}^{T}\left[\sum_{t=1}^{n}\ell(\widehat{f}_{t}(x_{t}),y_{t})-\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}\ell(f(x_{t}),y_{t})\right]$
(3)
$\displaystyle\mathcal{V}_{T}^{\textrm{improp}}(\mathcal{F},\mathfrak{P}({\sigma},{\mu}))$
$\displaystyle=\left\langle\sup_{p_{t}\in\mathfrak{P}(\sigma,\mu)}\mathbb{E}_{x_{t}\sim
p_{t}}\inf_{q_{t}\in\Delta([-1,1])}\sup_{y_{t}\in[-1,1]}\mathbb{E}_{\widehat{y}_{t}\sim
q_{t}}\right\rangle_{t=1}^{T}\left[\sum_{t=1}^{n}\ell(\widehat{y}_{t},y_{t})-\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}\ell(f(x_{t}),y_{t})\right].$

where $\left\langle\cdot\right\rangle_{t=1}^{T}$ denotes iterated application
of the enclosed operators. It is straightforward to see that
$\mathcal{V}_{T}^{\textrm{prop}}(\mathcal{F},\mathfrak{P}(\sigma,\mu))\geq\mathcal{V}_{T}^{\textrm{improp}}(\mathcal{F},\mathfrak{P}(\sigma,\mu))$.

###  2.3 ERM oracle model

To capture the notion of computational efficiency, we consider the following
_ERM oracle model_ :

######  Definition 2 (ERM oracle).

For $\zeta>0$, a _$\zeta$ -approximate (weighted) empirical risk minimization
(ERM) oracle_ takes as input a sequence
$(x_{1},y_{1}),\ldots,(x_{m},y_{m})\in\mathcal{X}\times[-1,1]$ of data, a
sequence $w_{1},\dots,w_{m}\in\mathbb{R}$ of weights, and a sequence
$\ell_{1},\dots,\ell_{m}$ of $[-1,1]$-valued loss functions and outputs some
$\widehat{f}\in\mathcal{F}$ satisfying

$\displaystyle\sum_{i=1}^{m}w_{i}\ell_{i}(\widehat{f}(x_{i}),y_{i})\leq\inf_{f\in\mathcal{F}}\sum_{i=1}^{m}w_{i}\ell_{i}(f(x_{i}),y_{i})+{\zeta}\cdot{\sum_{i=1}^{m}|w_{i}|}.$
(4)

We remark that while Definition 2 allows for an arbitrary sequence
$\ell_{1},\ldots,\ell_{m}$ of loss functions, all of our algorithms will set
each $\ell_{i}$ equal to either $\ell$ (the given loss function of the
learning problem) or $\ell^{\textrm{Id}}$, where
$\ell^{\textrm{Id}}(\widehat{y},y):=\widehat{y}$.

We will measure the computation cost of algorithms via the following two
metrics: first, the _number of calls to the ERM oracle_ , and second, the
_total computation time_. To define the latter, we must specify the manner in
which our algorithm interacts with the ERM oracle: in particular, we assume
that there is a certain region of memory on which the algorithm lists tuples
$(x_{i},y_{i},w_{i})$. Listing (or modifying) any such tuple takes unit time,
as does calling the ERM oracle, which performs the optimization in (4) in unit
time. This convention mirrors that of oracle machines in complexity theory
(AB, 09). We refer to the case that $\zeta=0$ the _exact ERM oracle model_ ,
and the case that $\zeta>0$ the _approximate ERM oracle model_.

###  2.4 Statistical complexities

For a space $\mathcal{X}$, an $n\in\mathbb{N}$, and a function class
$\mathcal{F}\subset[-1,1]^{\mathcal{X}}$, the Rademacher complexity,
$\mathcal{R}_{n}({\mathcal{F}})$, and Gaussian complexity,
$\mathcal{G}_{n}({\mathcal{F}})$, conditional on $x_{1},\dots,x_{n}$, are
defined as follows:

$\displaystyle\mathcal{R}_{n}({\mathcal{F}}):=\operatorname{\mathbb{E}}_{\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{i=1}^{n}\varepsilon_{i}f(x_{i})\right],\qquad\mathcal{G}_{n}({\mathcal{F}}):=\operatorname{\mathbb{E}}_{\gamma}\left[\sup_{f\in\mathcal{F}}\sum_{i=1}^{n}\gamma_{i}f(x_{i})\right],$

where the $\varepsilon_{i}$ are i.i.d. Rademacher random variables, and the
$\gamma_{i}$ are i.i.d. standard normal random variables. It is a well-known
fact that there is a universal constant $C$ so that
$\frac{1}{C}\cdot\mathcal{R}_{n}({\mathcal{F}})\leq\mathcal{G}_{n}({\mathcal{F}})\leq
C\log n\cdot\mathcal{R}_{n}({\mathcal{F}})$ for all $\mathcal{F}$ and $n$.

Furthermore, we consider the notion of scale-sensitive VC dimension from KS
(94); BLW (96) that characterizes learnability of $\mathcal{F}$ in a batch
setting. For any $\alpha>0$ and points $x_{1},\dots,x_{m}\in\mathcal{X}$, we
say that $\mathcal{F}$ is shattered by the $x_{i}$ at scale $\alpha$ with
witness $s_{1},\dots,s_{m}\in\mathbb{R}$ if for all
$(\varepsilon_{1},\dots,\varepsilon_{m})\in\\{\pm 1\\}^{m}$ there is an
$f_{\varepsilon}\in\mathcal{F}$ such that

$\varepsilon_{i}(f_{\varepsilon}(x_{i})-s_{i})\geq\frac{\alpha}{2}\qquad\text{for
all }i$ (5)

We define the VC dimension of $\mathcal{F}$ at scale $\alpha$, denoted by
$\mathsf{vc}(\mathcal{F},\alpha)$ to be the largest $m$ such that there exists
a shattering set of size $m$. We let
$\mathsf{vc}(\mathcal{F})=\lim_{\alpha\downarrow
0}\mathsf{vc}(\mathcal{F},\alpha)$ denote the VC dimension of $\mathcal{F}$.

##  3 Minimax Value

In this section, we provide tight bounds on
$\mathcal{V}_{T}^{\textrm{prop}}(\mathcal{F},\mathfrak{P}(\sigma,\mu))$
without regard to oracle efficiency. While our proof is nonconstructive, we
emphasize that our results in Section 6 demonstrate that any proper algorithm
based on ERM oracle calls which achieves the optimal dependence on $\sigma$
cannot be computationally efficient. Our results show that
$\mathcal{V}_{T}^{\textrm{prop}}(\mathcal{F},\mathfrak{P}({\sigma},{\mu}))$ is
always a $\mathrm{poly}(\log(T/\sigma))$ factor away from the optimal
statistical rates achievable in the batch setting. We now present our bound:

######  Theorem 3.

Let $\mathcal{F}:\mathcal{X}\to[-1,1]$ be a real-valued function class and
denote by $\mathsf{vc}(\mathcal{F},\delta)$ the scale-sensitive VC dimension
of $\mathcal{F}$ at scale $\delta>0$. Then, for some $c>0$

$\mathcal{V}_{T}^{\textrm{prop}}(\mathcal{F},\mathfrak{P}(\sigma,\mu))\lesssim
L\log^{3/2}(T)\cdot\log\left(\frac{T}{\sigma}\right)\inf_{\alpha>0}\left\\{T\alpha+\sqrt{T}\int_{\alpha}^{2}\sqrt{\mathsf{vc}\left(\mathcal{F},c\delta\right)}d\delta\right\\}$
(6)

In particular, if $\mathsf{vc}(\mathcal{F},\delta)\leq
d\log\left(\frac{1}{\delta}\right)$ for all $\delta>0$, then

$\mathcal{V}_{T}^{\textrm{prop}}(\mathcal{F},\mathfrak{P}(\sigma,\mu))\lesssim
L\log^{\frac{3}{2}}(T)\log\left(\frac{T}{\sigma}\right)\sqrt{dT}$ (7)

and if $\mathsf{vc}(\mathcal{F},\delta)\lesssim\delta^{-p}$ for some
$p<\infty$, then

$\mathcal{V}_{T}^{\textrm{prop}}(\mathcal{F},\mathfrak{P}(\sigma,\mu))\lesssim
L\log^{\frac{3}{2}}(T)\log\left(\frac{T}{\sigma}\right)T^{\max\left(\frac{1}{2},1-\frac{1}{p}\right)}$
(8)

Our result extends (HRS, 21, Theorem 3.1) to the cases of real-valued and
nonparametric function classes. In that paper, in order to prove their regret
bounds for smoothed online classification, the authors introduced the clever
approach of coupling, showing that if a distribution $p$ is smooth with
respect to the uniform distribution on a discrete set, then in expectation we
may pretend the data comes independently from the uniform distribution. In
Appendix C, we generalize their result in Lemmas 14 and 24 with a dramatically
simpler proof222Already in the case of discrete distributions, the proof of
(HRS, 21, Theorem 2.1) first demonstrates their claim for uniform measures and
then proceeds to apply convex analysis for the general case. They then claim
that Choquet’s Theorem (CM, 63, Corollaire 8) implies the general case when
$\mathcal{X}$ is not discrete; however, it is not _a priori_ obvious that
$\mathfrak{P}(\sigma,\mu)$ is compact in the relevant topology.. Namely, for
any $k\in\mathbb{N}$ we construct a coupling between
$(x_{1},\dots,x_{T})\sim\mathscr{D}\in\mathfrak{P}_{T}(\sigma,\mu)$ and
$\\{Z_{t}^{j}\\}_{\begin{subarray}{c}1\leq t\leq T\\\ 1\leq j\leq
k\end{subarray}}\sim\mu^{\otimes kT}$ such that
$\\{x_{1},\dots,x_{T}\\}\subset\\{Z_{t}^{j}\\}_{\begin{subarray}{c}1\leq t\leq
T\\\ 1\leq j\leq k\end{subarray}}$ with probability at least $1-e^{-\sigma
k}$.

Curiously, our proof of Theorem 3 is quite different from that of (HRS, 21,
Theorem 3.1), although we still use the coupling. In that paper, the authors
apply the coupling to analyze covering numbers with respect to $L^{2}(\mu)$
(i.e. in the i.i.d. sense); the natural extension of this technique would be
to apply chaining (Dud, 67) and bound
$\mathcal{V}_{T}^{prop}(\mathcal{F},\mathscr{D})$ by
$\mathbb{E}_{\mu}\left[\mathcal{R}_{T}(\mathcal{F})\right]$. Unfortunately,
Proposition 8 in the sequel shows that such a bound is not possible without a
suboptimal, polynomial dependence on $\sigma$. We instead go by a different
approach, which is based on the observation that the sequential fat-shattering
dimension (see Definition 19) is bounded above by the scale-sensitive VC
dimension times a logarithmic factor in the domain size (Lemma 21). Though the
true domain $\mathcal{X}$ may be infinite, we show that it is possible adapt
the coupling lemma of HRS (21) to bound an “effective” domain size. In
combination with the non-constructive bounds using distribution-dependent
sequential Rademacher complexity from RST (11); BDR (21), this provides a
tight characterization of the minimax regret’s dependence on the horizon $T$,
the complexity of the function class, and the smoothness parameter $\sigma$. A
full proof is in Appendix C. Combining Theorem 3 with (HRS, 21, Theorem 3.2),
we have a complete characterization of the statistical rates of smooth online
learning. We further note that our proof applied to the results of RS (15)
immediately extends to nonconstructively show that the dependence of the
minimax value on $T$ for squared loss are the expected “fast rates” from RST
(17). Unfortunately, our efficient algorithms below do not provably achieve
these rates; resolving this disparity is an interesting future direction with
applications to the study of contextual bandits, as described in Appendix A.

Finally, before we proceed to consider oracle-efficient algorithms, we note
that the requirement that the learner has access to $\mu$ cannot be dropped
without a substantial loss in the regret. In particular, we have the following
result:

######  Proposition 4.

There exists a function class $\mathcal{F}:[0,1]\to\\{\pm 1\\}$ with
$\mathsf{vc}(\mathcal{F})=1$ and an adversary that is $\sigma$-smooth with
respect to some unknown $\mu$ such that, no matter how the learner chooses
$\widehat{y}_{t}$, it holds for $T\leq\frac{1}{\sigma}$ that

$\mathbb{E}\left[\operatorname{Reg}_{T}\right]\geq\frac{T}{2}.$ (9)

Proposition 4 is proved by letting $\mathcal{F}$ be thresholds on the unit
interval and allowing the $\mu$ with respect to which the adversary is
$\sigma$-smooth adapt to the data sequence. The details can be found in
Appendix C. In particular, the result shows that for the learner to be able to
ensure regret scaling as in Theorem 3, he needs to have access to $\mu$ in
some way. Critically, the size of the set of possible $\mu$ in the lower bound
of Proposition 4 is growing exponentially with $T$; indeed, if we know that
our adversary is $\sigma$-smooth with respect to some $\mu\in\mathscr{P}$, a
finite class of distributions, then we can use Hedge (FS, 97) to aggregate
predictions assuming smoothness with respect to each $\mu\in\mathscr{P}$ and
add an additive term of size
$O\left(\sqrt{\log(\left|\mathscr{P}\right|)T}\right)$ to our regret.

##  4 Relaxations and Oracle-Efficient Algorithms

In333In an earlier version of the paper, we used a slightly different
relaxation with a worse rate. With a minor modification, we get a quadratic
improvement in the dependence of the regret on $\sigma$. While our improvement
was independent of other work, we note that HHSY (22) present the same final
relaxation and analysis. the previous section, we derived sharp bounds for the
minimax regret in the smoothed online setting, with sharp dependence on the
key parameter $\sigma$. A natural next step is to design an algorithm that
achieves these bounds. One possibility, suggested in HRS (21), constructs a
$\frac{1}{\sqrt{T}}$-net on $\ell\circ\mathcal{F}$ with respect to
$L^{2}(\mu)$ and runs Hedge (FS, 97) on the resulting covering. Unfortunately,
in the nonparametric case, after optimizing $\delta$ this approach yields
suboptimal rates, corresponding to one-step discretization. Ideally, an
algorithm achieving optimal regret would construct nets at multiple scales and
aggregate the resulting predictions in some way. While there has been some
progress on how to do this (CBL, 99; GG, 15; DG, 21), optimal rates are not
yet achievable; in any case, relying on the construction of $\delta$-nets is
inefficient as these can be exponentially large.

Thus in order to bring the smoothed online learning paradigm from the world of
theory into that of practice, we need more efficient algorithms. Presently, we
describe an oracle-efficient improper learning procedure. As we shall see, the
algorithm has regret with optimal dependence on the horizon, $T$, but
suboptimal dependence on $\sigma$. We will improve the dependence on $\sigma$
with a proper learning algorithm in the following section, at the cost of
worse dependence on $T$ in general. Here, we leverage the relaxation approach,
studied in RSS (12).

######  Definition 5.

Fix $T\in\mathbb{N}$. A sequence of real valued functions
$\mathbf{Rel}_{T}(\mathcal{F}|x_{1},\dots,x_{t}):\mathcal{X}^{t}\to\mathbb{R}$,
$t\leq T$, is a relaxation if for any $x_{1:T}\in\mathcal{X}$, we have the
following two properties:

$\displaystyle\sup_{p_{t}\in\mathfrak{P}(\sigma,\mu)}$
$\displaystyle\mathbb{E}_{x_{t}^{\prime}\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},y_{t}^{\prime})]+\mathbf{Rel}_{T}(\mathcal{F}|x_{1},y_{1},\dots,x_{t}^{\prime},y_{t}^{\prime})\right]$
(10)
$\displaystyle\leq\mathbf{Rel}_{T}(\mathcal{F}|x_{1},y_{1},\dots,x_{t-1},y_{t-1})$
(11) $\displaystyle-\inf_{f\in\mathcal{F}}\sum_{t=1}^{T}\ell(f(x_{t}),y_{t})$
$\displaystyle\leq\mathbf{Rel}_{T}(\mathcal{F}|x_{1},y_{1},\dots,x_{T},y_{T})$
(12)

As established in (RSS, 12, Proposition 1), a relaxation gives rise to both an
algorithm and an associated regret bound; indeed, any $q_{t}$ guaranteeing
(10) at each time $t$ yields a regret at most $\mathbf{Rel}_{T}(\mathcal{F})$;
the challenge, of course, is to define the relaxation. We have the following
result:

######  Proposition 6.

Suppose that $\mathscr{D}\in\mathfrak{P}(\sigma,\mu)$. Then, for any function
class $\mathcal{F}$ and $L$-Lipschitz, convex loss function $\ell$, and any
$k\in\mathbb{N}$,

$\mathbf{Rel}_{T}(\mathcal{F}|x_{1},y_{1},\dots,x_{t},y_{t})=\mathbb{E}_{\mu,\varepsilon}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-\sum_{s=1}^{t}\ell(f(x_{s}),y_{s})\right]+(T-t)^{3}e^{-\sigma
k}$ (13)

is a relaxation, where the expectation is over independent $x_{s,j}\sim\mu$
and Rademacher random variables $\varepsilon_{s,j}$ for $s>t$.

We provide a proof in Appendix D that uses the minimax theorem, symmetrization
and Lemma 14. Applying (RS, 14, Lemma 5.1) to reduce to deterministic
predictions, Proposition 6 gives rise to an algorithm that plays

$\widehat{y}_{t}=\operatorname*{argmin}_{\widehat{y}\in[-1,1]}\sup_{y_{t}\in[-1,1]}\ell(\widehat{y},y_{t})+\mathbb{E}_{\mu,\varepsilon}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t}(f)\right]$
(14)

where we drop the additive constant from (13) because it does not depend on
$f$ and we let $L_{t}(f)=\sum_{s=1}^{t}\ell(f(x_{s}),y_{s})$. After optimizing
the resulting regret bound with respect to $k$, we get that the regret of this
algorithm is $O\left(\mathcal{R}_{T\frac{\log
T}{\sigma}}(\mathcal{F})\right)$, which has an optimal dependence on $T$ up to
logarithmic factors, but is suboptimal with respect to $\sigma$. Note that
while the supremum inside of the expectation in (13) can be solved with an ERM
oracle by letting $\ell_{s}(f(x_{s,j}),y_{s})=f(x_{s,j})$ for $x>t$, we still
require a costly integration in order to find $\widehat{y}_{t}$. We can
compute this expectation by sampling from $\mu$ and applying concentration but
this approach requires many calls to the ERM oracle. Motivated by the random
playout idea in RSS (12), we propose a much more efficient algorithm:

######  Theorem 7.

Suppose that $\mathscr{D}\in\mathfrak{P}(\sigma,\mu)$,
$\mathcal{F}:\mathcal{X}\to[-1,1]$ is a function class, and $\ell$ is an
$L$-Lipschitz, convex loss function. At each time $t$, for $1\leq j\leq k$,
sample $x_{t+1,j},\dots,x_{T,j}\sim\mu$ and
$\varepsilon_{t+1,j},\dots,\varepsilon_{T,j}$ independently. After observing
$x_{t}$, predict

$\widehat{y}_{t}=\operatorname*{argmin}_{\widehat{y}\in[-1,1]}\sup_{y_{t}\in[-1,1]}\left\\{\ell(\widehat{y},y_{t})+\sup_{f\in\mathcal{F}}\left[6L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t}(f)\right]\right\\}$
(15)

Then the expected regret against any smooth adversary is

$\mathbb{E}\left[\operatorname{Reg}_{T}\right]\leq
6L\mathbb{E}_{\mu}\left[\mathcal{R}_{kT}(\mathcal{F})\right]+\sqrt{T}+T^{3}e^{-\sigma
k}$ (16)

Moreover, this regret can be achieved with $O\left(\sqrt{T}\log T\right)$
calls to the ERM oracle per round in general and only $2$ calls per round in
the special case that $\ell(\widehat{y},y)=\frac{1-\widehat{y}y}{2}$. In
particular, when $\mathsf{vc}(\mathcal{F},\delta)\lesssim\delta^{-p}$ for some
$p>0$, we have

$\mathbb{E}\left[\operatorname{Reg}_{T}\right]\lesssim
L\left(\frac{T\log\left(T\right)}{\sigma}\right)^{\max\left(\frac{1}{2},1-\frac{1}{p}\right)}$
(17)

Theorem 7 is proved in Appendix D. To understand why (15) is oracle-efficient,
note that we can discretize the interval $[-1,1]$ at scale
$\frac{1}{L\sqrt{T}}$ to produce a set $S$ of size $2L\sqrt{T}$. For each
$\widehat{y}\in S$, we can exhaustively search $S$ for the optimal $y_{t}$
with $O(\sqrt{T})$ calls to the (value of the) ERM oracle. Because the problem
is convex in $\widehat{y}$ (due to the convexity of $\ell$), we can run zeroth
order optimization as in AFH+ (11) to find $\widehat{y}_{t}$ up to
$\frac{1}{\sqrt{T}}$ error in $O\left(\sqrt{T}\log T\right)$ calls to the
oracle. If the losses are linear, then the problem is convex in $y_{t}$ and is
thus extremized on the boundary; further leveraging the linear loss allows the
problem to be solved in 2 oracle calls per round. Note that in the case of $y$
being binary-valued, we can think of
$\ell(\widehat{y},y)=\frac{1-\widehat{y}y}{2}$ as the indicator loss when
guessing $\widehat{y}\in\\{\pm 1\\}$ and thus, for classification, we can get
optimal regret with 2 oracle calls per round.

While Theorem 3 demonstrates that regret can depend on $\sigma$ only through a
logarithmic factor, our relaxation-based algorithm has a polynomial dependence
on $\sigma$. Unfortunately, this polynomial dependence cannot in general be
eliminated for any relaxation relying on the classical Rademacher complexity.
To see this, note that the regret of any algorithm is bounded below by
$\mathcal{V}_{T}^{improp}(\mathcal{F},\mathfrak{P}(\sigma,\mu))$. The
following proposition shows that the value is in turn bounded below by a
polynomial factor of $\sigma$.

######  Proposition 8.

For any $\sigma\leq 1$ and $0<p<2$, there exists a measure $\mu$ and a
function class $\mathcal{F}$ satisfying
$\mathsf{vc}(\mathcal{F},\delta)\lesssim\delta^{-p}$ such that for all
$T\gtrsim\frac{1}{\sigma}\log\left(\frac{1}{\sigma}\right)$ with $\ell$ the
absolute loss,

$\sigma^{-\frac{p}{4}}\mathbb{E}_{\mu}\left[\mathcal{R}_{T}(\mathcal{F})\right]\lesssim\mathcal{V}_{T}^{improp}(\mathcal{F},\mathfrak{P}(\sigma,\mu))$
(18)

We construct a measure such that the learning problem is easy when the
population distribution is $\mu$ by having $\mu$ concentrate a lot of mass on
a distinguished point $x^{\ast}$ on which all the functions in $\mathcal{F}$
agree; thus, a sample from $\mu$ will include many copies of $x^{\ast}$, which
incur no regret. We then consider an i.i.d. adversary and let $p_{t}$ be
uniform over a set of points that shatters $\mathcal{F}$ at scale
$\sqrt{\sigma}$; in this way, we make it so a sample from $p_{t}$ will incur
high regret and the gap between the performance on samples from $p_{t}$ and
$\mu$ is relatively large. A complete proof can be found in Appendix C. Note
that Proposition 8 is not in conflict with Theorem 3 because the example
described above makes $\mathcal{R}_{T}(\mathcal{F})$ polynomially small in
$\sigma$ for a carefully designed $\mu$; in essence, the separation is created
by making the Rademacher complexity much smaller than expected based on the
complexity of the function class $\mathcal{F}$.

In the improper procedure (15), we have our first efficient algorithm for the
smoothed online learning setting that works for a generic function class and
achieves an optimal regret dependence on the horizon $T$. There are three
drawbacks to Theorem 7. First, $\widehat{y}_{t}$ is _improper_. Second, our
dependence on $\sigma$ is significantly worse than the optimal statistical
dependence explored in Section 3. Third, while the algorithm is efficient, we
may hope to have an algorithm that makes only $1$ oracle call per round in
general. We address these issues in the following section.

##  5 Follow the Perturbed Leader and Oracle-Efficient Proper Learning

In the previous section, we provided an improper oracle-efficient algorithm
that achieves optimal dependence on the horizon $T$, but is improper and
requires more than one oracle call per round; here we demonstrate that a
proper learner can have similar regret in some situations with only 1 oracle
call per time step. In the following section, we will show that our
algorithm’s regret is optimal up to a polynomial factor for any oracle-
efficient algorithm.

In RSS (12), the authors make use of the connection between relaxations,
random playout, and the Follow the Perturbed Leader (FTPL) style algorithms
pioneered in KV (05) to make the relaxation approach more efficient in some
cases. We expand upon this approach, using Theorem 7 as a starting point.
Indeed, the prediction $\widehat{y}_{t}$ in (15) is cosmetically very similar
to that of FTPL, were we recall that the FTPL approach introduces a noise
process $\omega(f)$ and, at each time step, sets

$f_{t}\in\operatorname*{argmin}_{f\in\mathcal{F}}L_{t-1}(f)+\eta\omega(f)$
(19)

for some real-valued parameter $\eta$. The perturbation $\eta\omega(f)$ acts
to regularize the predictions; typically, the noise $\omega$ is independent
across functions, with the classic example being exponential noise in KV (05).
On the other hand, up to a sign, the supremum in (15) returns the optimal
value of $L_{t}(f)+\eta\omega(f)$ with appropriate values of $\eta$ and
letting $\omega$ be the Rademacher process. It is natural to wonder, then, if
the min-max problem that is the source of the extra oracle calls is really
necessary; we show below that it is not in the sense that FTPL provides an
efficient, proper algorithm.

Were we to apply existing FTPL results, using independent perturbations for
each $f$, we would require the enumeration of representative “experts,” which
would preclude the desired oracle-efficiency. Above, we saw that a Rademacher
process perturbation is motivated by the relaxations of the previous section,
but analysis is much easier with a Gaussian process. We first treat the case
of binary classification:

######  Theorem 9.

Suppose that $\mathcal{F}:\mathcal{X}\to[-1,1]$ is a function class and $\ell$
a loss function that is Lipschitz in both arguments. Suppose further that we
are in the smoothed online learning setting where $x_{i}$ are drawn from a
distribution that is $\sigma$-smooth with respect to some distribution $\mu$
on $\mathcal{X}$. Let

$\hat{\omega}_{t,n}(f)=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\gamma_{t,i}f(Z_{t,i})$
(20)

where the $Z_{t,i}\sim\mu$ are independent and the $\gamma_{t,i}$ are
indpendent standard normal random variables. Suppose that $\zeta\geq 0$ and
consider the algorithm which uses the approximate ERM oracle to choose $f_{t}$
according to444Note that we have not included the total weight multiplying
$\zeta$ in (21), as in (4); thus we are technically using a
$\frac{\zeta}{T+\log(1/\delta)\cdot n}$-approximate ERM oracle with
probability $1-O(\delta)$.

$L_{t-1}(f_{t})+\eta\hat{\omega}_{t,n}(f_{t})\leq\inf_{f\in\mathcal{F}}L_{t-1}(f)+\hat{\omega}_{t,n}(f)+\zeta$
(21)

and let $\widehat{y}_{t}=f_{t}(x_{t})$. If $\mathcal{F}$ and $y_{t}$ are
binary valued, $\mathsf{vc}(\mathcal{F})\leq d$, then for appropriate choices
of $n$ and $\eta$555Specified in Proposition 40 in Appendix E.3

$\mathbb{E}\left[\operatorname{Reg}_{T}(f_{t})\right]\lesssim\sqrt{\frac{dT\log
T}{\sigma}}+\zeta T$ (22)

More generally, if we let

$\hat{\omega}_{t,n}(f)=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\gamma_{t,i}\ell(f(Z_{t,i}),y_{t,i})$
(23)

with $y_{t,i}$ drawn uniformly from $\varepsilon\mathbb{Z}\cap[-1,1]$ and
$\mathsf{vc}(\mathcal{F},\delta)\lesssim\delta^{-p}$ for some $p<2$, then for
appropriate choices of the parameters666Given in Corollary 44 in Appendix
E.3., if $f_{t}$ is chosen according to (21),

$\mathbb{E}\left[\operatorname{Reg}_{T}(f_{t})\right]\lesssim
T^{\frac{3}{4}}\sigma^{-\frac{1}{4}}\log\left(\frac{T}{\sigma}\right)+\zeta T$
(24)

In order to improve the regret for the case of real-valued labels, we
introduce a second, stabilizing perturbation. The following result bounds the
regret of the resulting algorithm:

######  Theorem 10.

Suppose that $\mathcal{F}:\mathcal{X}\to[-1,1]$ is a function class and
$\ell:[-1,1]\times[-1,1]\to[0,1]$ is a loss function that is $L$-Lipschitz in
_both_ arguments. Suppose further that we are in the smooth online learning
setting where $x_{t}$ is chosen from a distribution that is $\sigma$-smooth
with respect to some $\mu$. Fix $\varepsilon>0$ and consider the following two
processes:

$\displaystyle\hat{\omega}_{t,m}(f)=\frac{1}{\sqrt{m}}\sum_{i=1}^{m}\gamma_{t,i}f(Z_{t,i})$
$\displaystyle\hat{\omega}_{t,n}^{\prime}(f)=\sum_{j=1}^{n}\gamma_{t,j}^{\prime}\ell(f(Z_{t,j}^{\prime}),y_{t,j}^{\prime})$
(25)

where $\gamma_{t,i},\gamma_{t,j}^{\prime}$ are independent standard normal
random variables, $Z_{t,i},Z_{t,j}^{\prime}\sim\mu$, and $y_{t,j}^{\prime}$
are independent and uniform on $\varepsilon\mathbb{Z}\cap[-1,1]$. Suppose that
$f_{t}$ is chosen according to

$L_{t-1}(f_{t})+\eta\hat{\omega}_{t,m}(f_{t})+\hat{\omega}_{t,n}(f_{t})\leq\inf_{f\in\mathcal{F}}L_{t-1}(f)+\eta\hat{\omega}_{t,m}(f)+\hat{\omega}_{t,n}(f)+\zeta$
(26)

If there is some $p<2$ such that
$\mathsf{vc}(\mathcal{F},\delta)\lesssim\delta^{-p}$ then for appropriate
choices of the parameters777Outlined in Corollary 43 in Appendix E.3., we
have:

$\displaystyle\mathbb{E}\left[\operatorname{Reg}_{T}(f_{t})\right]\lesssim\frac{T^{\frac{2}{3}}\log
T}{\sigma^{\frac{1}{3}}}+\zeta T$ (27)

If $2\leq p<\infty$, then there are appropriate choices of parameters such
that $\mathbb{E}\left[\operatorname{Reg}_{T}(f_{t})\right]=o(T)$.

In Appendix E.3 we provide a slightly more general form of the above regret
bounds, including in the case when the labels are smooth with respect to a
known measure. Further, we give the precise dependence of our regret bounds on
$n$ and $\eta$; the optimal values of these parameters are polynomial in
$L,T,1/\sigma$, and the complexity of the function class. Interestingly, we
can still achieve regret with the same dependence on $T$ by setting the
parameters independently of $\sigma$ and $L$; this is useful for applications
where we can assume $\sigma$-smoothness but do not know what $\sigma$ is.

The proofs of Theorems 9 and 10 proceed similarly. First, we apply a variant
of the classic “Be-the-Leader” approach (CBL, 06, Lemma 3.1), which leads to a
regret decomposition into a perturbation term and a stability term. The
perturbation term is easily controlled with classical empirical process
theory. For the stability term, we further decompose the regret into a term
quantifying the difference in losses of $f_{t}$ and $f_{t+1}$ on a tangent
sequence and another quantifying the dependence of $f_{t+1}$ on $x_{t},y_{t}$.
For the former term, we prove a novel anti-concentration inequality for the
infimum of a Gaussian process, which may be of independent interest, and apply
this inequality to control the Wasserstein distance between $f_{t}$ and
$f_{t+1}$. We bound the latter term in the case of linear loss in a similar
way as HHSY (22) did for the corresponding term in their algorithm. This
suffices for the binary labels case, but to extend to the more general
setting, we use a discretization scheme to reduce to the case that the labels
are also chosen in a smooth manner with respect to some distribution; we then
reduce this setting to the case of linear loss and apply our earlier bound.
The details can be found in Appendix E.

The stability estimate was a significant technical challenge due to the
complex dependence structure of $\hat{\omega}_{t,n}$ accross $\mathcal{F}$;
most regret bounds for FTPL-style algorithms are simplified by independent
perturbations. To the best of our knowledge, Theorem 10 constitutes the first
proof of an FTPL regret bound where the algorithm uses a generic Gaussian
process as the perturbation.

##  6 Computational Lower Bounds

Comparing the results of Theorem 3 and Theorem 10, we notice that the
requirement of oracle efficiency incurs an exponential loss in the regret’s
dependence on $\sigma$. In this section, we show that this exponential gap is
necessary for any oracle-efficient algorithm.

######  Theorem 11.

Fix any $T\in\mathbb{N}$ and $\sigma\in(0,1]$. In the ERM oracle model, any
randomized algorithm cannot guarantee expected regret smaller than
$\frac{T}{200}$ against a $\sigma$-smooth online adversary over $T$ rounds and
any binary $\mathcal{F}$ with $|\mathcal{F}|\leq 1/\sigma$ in total time
smaller than $\widetilde{O}(1/\sqrt{\sigma})$.

Theorem 11 is proved in Appendix F by constructing a family of function
classes on a space $\mathcal{X}$ of size $1/\sigma$ and noting that a worst-
case adaptive adversary is $\sigma$-smooth in this setting. The construction
then mirrors that in HK (16), which reduces from Aldous’ problem (Ald, 83);
the main difference being that Definition 2 allows for negative weights in the
ERM oracle, which complicates the proof.

As an immediate corollary of Theorem 11, we obtain the following regret lower
bound for computationally efficient algorithms in the ERM oracle model, i.e.,
those whose total time after $T$ time steps is $\textrm{poly}(T)$:

######  Corollary 12.

Fix any $\alpha\geq 1$, $\varepsilon<1/200,\sigma\in(0,1]$, and $d\geq\log
1/\sigma$. Any algorithm whose total time in the ERM oracle model over $T$
rounds is bounded as $T^{\alpha}$ requires that
$T\geq\widetilde{\Omega}\left(\max\left\\{\frac{d}{\varepsilon^{2}},\sigma^{-\frac{1}{2\alpha}}\right\\}\right)$
to achieve regret $\varepsilon T$ for classes $\mathcal{F}$ of VC dimension
$d$ against a $\sigma$-smooth adversary.

Corollary 12 and Theorem 3 show that there is an exponential statistical-
computational gap for smoothed online learning in the ERM oracle model: for
general classes $\mathcal{F}$, it is possible to achieve regret proportional
to $\log(1/\sigma)$, but the regret must be polynomial in $1/\sigma$ if the
algorithm is required to be oracle-efficient. While Theorem 11 and Corollary
12 get a lower bound only on the total computation time, as opposed to the
number of oracle calls, we provide analogous results obtaining lower bounds on
the number of oracle calls with an _approximate_ ERM oracle in Theorem 52 and
Corollary 53 in the appendix. In particular, we show that any algorithm with
$T^{O(1)}$ oracle calls with a $1/T^{O(1)}$-approximate ERM oracle needs
$T\geq\max\\{d,1/\varepsilon,1/\sigma\\}^{\Omega(1)}$ to obtain sublinear
regret against binary classes of VC dimension $d$.

## Acknowledgements

AB acknowledges support from the National Science Foundation Graduate Research
Fellowship under Grant No. 1122374. NG is supported by a Fannie & John Hertz
Foundation Fellowship and an NSF Graduate Fellowship. AR acknowledges support
from the ONR through awards N00014-20-1-2336 and N00014-20-1-2394, from the
NSF through awards DMS-2031883 and DMS-1953181, and from the ARO through award
W911NF-21-1-0328.

## References

  * Aar [06] Scott Aaronson.  Lower bounds for local search by quantum arguments.  SIAM Journal on Computing, 35(4):804–824, 2006.
  * AB [09] Sanjeev Arora and Boaz Barak.  Computational complexity: a modern approach.  Cambridge University Press, 2009.
  * AFH+ [11] Alekh Agarwal, Dean P Foster, Daniel J Hsu, Sham M Kakade, and Alexander Rakhlin.  Stochastic convex optimization with bandit feedback.  Advances in Neural Information Processing Systems, 24:1035–1043, 2011.
  * AGH [19] Naman Agarwal, Alon Gonen, and Elad Hazan.  Learning in non-convex games with an optimization oracle.  In Conference on Learning Theory, pages 18–29. PMLR, 2019.
  * Ald [83] David Aldous.  Minimization algorithms and random walk on the $d$-cube.  The Annals of Probability, 11(2):403–413, 1983.
  * ALST [14] Jacob Abernethy, Chansoo Lee, Abhinav Sinha, and Ambuj Tewari.  Online linear optimization via smoothing.  In Conference on Learning Theory, pages 807–823. PMLR, 2014.
  * ALT [15] Jacob Abernethy, Chansoo Lee, and Ambuj Tewari.  Fighting bandits with a new kind of smoothness.  arXiv preprint arXiv:1512.04152, 2015.
  * AV [06] David Arthur and Sergei Vassilvitskii.  Worst-case and smoothed analysis of the icp algorithm, with an application to the k-means method.  In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 153–164, 2006.
  * BDR [21] Adam Block, Yuval Dagan, and Alexander Rakhlin.  Majorizing measures, sequential complexities, and online learning.  In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 587–590. PMLR, 15–19 Aug 2021.
  * BKM [20] Shant Boodaghians, Rucha Kulkarni, and Ruta Mehta.  Smoothed efficient algorithms and reductions for network coordination games.  In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 73:1–73:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * BLW [96] Peter L Bartlett, Philip M Long, and Robert C Williamson.  Fat-shattering and the learnability of real-valued functions.  journal of computer and system sciences, 52(3):434–452, 1996.
  * BV [04] Rene Beier and Berthold Vöcking.  Typical properties of winners and losers in discrete optimization.  In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’04, page 343–352, New York, NY, USA, 2004. Association for Computing Machinery.
  * CBCG [04] Nicolo Cesa-Bianchi, Alex Conconi, and Claudio Gentile.  On the generalization ability of on-line learning algorithms.  IEEE Transactions on Information Theory, 50(9):2050–2057, 2004\.
  * CBL [99] Nicolo Cesa-Bianchi and Gábor Lugosi.  On prediction of individual sequences.  The Annals of Statistics, 27(6):1865–1895, 1999.
  * CBL [06] Nicolo Cesa-Bianchi and Gábor Lugosi.  Prediction, learning, and games.  Cambridge university press, 2006.
  * CH [15] Alon Cohen and Tamir Hazan.  Following the perturbed leader for online structured learning.  In Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 37, ICML’15, page 1034–1042. JMLR.org, 2015.
  * CM [63] Gustave Choquet and Paul-André Meyer.  Existence et unicité des représentations intégrales dans les convexes compacts quelconques.  In Annales de l’institut Fourier, volume 13, pages 139–154, 1963\.
  * DG [21] Constantinos Daskalakis and Noah Golowich.  Fast rates for nonparametric online learning: From realizability to learning in games.  arXiv preprint arXiv:2111.08911, 2021.
  * DHL+ [17] Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E Schapire, Vasilis Syrgkanis, and Jennifer Wortman Vaughan.  Oracle-efficient online learning and auction design.  In 2017 ieee 58th annual symposium on foundations of computer science (focs), pages 528–539. IEEE, 2017.
  * DLN [13] Luc Devroye, Gábor Lugosi, and Gergely Neu.  Prediction by random-walk perturbation.  In Conference on Learning Theory, pages 460–473. PMLR, 2013.
  * Dud [67] Richard M Dudley.  The sizes of compact subsets of hilbert space and continuity of gaussian processes.  Journal of Functional Analysis, 1(3):290–330, 1967.
  * ER [17] Michael Etscheid and Heiko Röglin.  Smoothed analysis of local search for the maximum-cut problem.  ACM Trans. Algorithms, 13(2), mar 2017.
  * Fer [75] Xavier Fernique.  Regularité des trajectoires des fonctions aléatoires gaussiennes.  In Ecole d’Eté de Probabilités de Saint-Flour IV—1974, pages 1–96. Springer, 1975.
  * FKQR [21] Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin.  The statistical complexity of interactive decision making.  arXiv preprint arXiv:2112.13487, 2021.
  * FR [20] Dylan Foster and Alexander Rakhlin.  Beyond ucb: Optimal and efficient contextual bandits with regression oracles.  In International Conference on Machine Learning, pages 3199–3210. PMLR, 2020.
  * FRSLX [20] Dylan J Foster, Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu.  Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective.  arXiv preprint arXiv:2010.03104, 2020.
  * FS [97] Yoav Freund and Robert E Schapire.  A decision-theoretic generalization of on-line learning and an application to boosting.  Journal of computer and system sciences, 55(1):119–139, 1997.
  * FS [99] Yoav Freund and Robert E Schapire.  Adaptive game playing using multiplicative weights.  Games and Economic Behavior, 29(1-2):79–103, 1999.
  * GBC [16] Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  Deep learning.  MIT press, 2016.
  * GG [15] Pierre Gaillard and Sébastien Gerchinovitz.  A chaining algorithm for online nonparametric regression.  In Conference on Learning Theory, pages 764–796. PMLR, 2015.
  * Han [16] James Hannan.  4\. approximation to rayes risk in repeated play.  In Contributions to the Theory of Games (AM-39), Volume III, pages 97–140. Princeton University Press, 2016.
  * HHSY [22] Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang.  Oracle-efficient online learning for beyond worst-case adversaries.  arXiv preprint arXiv:2202.08549, 2022.
  * HK [16] 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.
  * HRS [20] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty.  Smoothed analysis of online and differentially private learning.  arXiv preprint arXiv:2006.10129, 2020.
  * HRS [21] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty.  Smoothed analysis with adaptive adversaries.  arXiv preprint arXiv:2102.08446, 2021.
  * HW [07] David P. Helmbold and Manfred K. Warmuth.  Learning permutations with exponential weights.  In COLT, 2007.
  * KM [72] Victor Klee and George J Minty.  How good is the simplex algorithm.  Inequalities, 3(3):159–175, 1972.
  * KS [94] 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.
  * KV [05] Adam Kalai and Santosh Vempala.  Efficient algorithms for online decision problems.  Journal of Computer and System Sciences, 71(3):291–307, 2005.
  * Lit [88] Nick Littlestone.  Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.  Machine learning, 2(4):285–318, 1988.
  * Man [20] Bodo Manthey.  Smoothed Analysis of Local Search, pages 285–308.  Cambridge University Press, United States, December 2020.
  * Men [02] Shahar Mendelson.  Rademacher averages and phase transitions in glivenko-cantelli classes.  IEEE transactions on Information Theory, 48(1):251–263, 2002.
  * Rou [21] Tim Roughgarden, editor.  Beyond the Worst-Case Analysis of Algorithms.  Cambridge University Press, 2021.
  * RS [13] Alexander Rakhlin and Karthik Sridharan.  Online learning with predictable sequences.  In Shai Shalev-Shwartz and Ingo Steinwart, editors, Proceedings of the 26th Annual Conference on Learning Theory, volume 30 of Proceedings of Machine Learning Research, pages 993–1019, Princeton, NJ, USA, 12–14 Jun 2013. PMLR.
  * RS [14] Alexander Rakhlin and Karthik Sridharan.  Statistical learning and sequential prediction.  Book Draft, 2014.
  * RS [15] Alexander Rakhlin and Karthik Sridharan.  Online nonparametric regression with general loss functions.  arXiv preprint arXiv:1501.06598, 2015.
  * RSS [12] Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan.  Relax and randomize: From value to algorithms.  Advances in neural information processing systems, 25, 2012.
  * RST [11] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Online learning: Stochastic, constrained, and smoothed adversaries.  Advances in neural information processing systems, 24:1764–1772, 2011.
  * [49] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Online learning via sequential complexities.  J. Mach. Learn. Res., 16(1):155–186, 2015.
  * [50] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Sequential complexities and uniform martingale laws of large numbers.  Probability Theory and Related Fields, 161(1-2):111–153, 2015.
  * RST [17] Alexander Rakhlin, Karthik Sridharan, and Alexandre B Tsybakov.  Empirical entropy, minimax regret and minimax risk.  Bernoulli, 23(2):789–824, 2017.
  * RV [06] Mark Rudelson and Roman Vershynin.  Combinatorics of random processes and sections of convex bodies.  Annals of Mathematics, pages 603–648, 2006.
  * Sau [72] Norbert Sauer.  On the density of families of sets.  Journal of Combinatorial Theory, Series A, 13(1):145–147, 1972\.
  * She [72] Saharon Shelah.  A combinatorial problem; stability and order for models and theories in infinitary languages.  Pacific Journal of Mathematics, 41(1):247–261, 1972.
  * SLX [21] David Simchi-Levi and Yunzong Xu.  Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability.  Mathematics of Operations Research, 2021.
  * SS+ [11] Shai Shalev-Shwartz et al.  Online learning and online convex optimization.  Foundations and trends in Machine Learning, 4(2):107–194, 2011\.
  * SST [10] Nathan Srebro, Karthik Sridharan, and Ambuj Tewari.  Smoothness, low noise and fast rates.  Advances in neural information processing systems, 23, 2010.
  * ST [04] Daniel A Spielman and Shang-Hua Teng.  Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems.  In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 81–90, 2004.
  * Sud [71] Vladimir Nikolaevich Sudakov.  Gaussian random processes and measures of solid angles in hilbert space.  In Doklady Akademii Nauk, volume 197, pages 43–45. Russian Academy of Sciences, 1971.
  * TW [02] Eiji Takimoto and Manfred K. Warmuth.  Path kernels and multiplicative updates.  In Proceedings of the 15th Annual Conference on Computational Learning Theory, COLT ’02, page 74–89, Berlin, Heidelberg, 2002. Springer-Verlag.
  * VC [74] Vladimir Vapnik and Alexey Chervonenkis.  Theory of pattern recognition.  Nauka, Moscow, 1974.
  * Wai [19] Martin J Wainwright.  High-dimensional statistics: A non-asymptotic viewpoint, volume 48.  Cambridge University Press, 2019.

##  Appendix A Applications to Contextual Bandits

We apply our results to the study of contextual bandits. A series of recent
papers [25, 55, 26] has focused on reducing the contextual bandit framework to
that of online learning, with [25] introducing an efficient and optimal
reduction, SquareCB, that turns an online regression oracle into a fast, no-
regret contextual bandit algorithm. One of the key advantages of this
reduction is the fact that the learner “only” has to design algorithms that
have small regret in the full-information setting, thought to be an easier
task than one that requires a careful balance of exploration and exploitation.
Unfortunately, there is still a dearth of oracle-efficient online algorithms
with provably good regret in general, limiting the broader application of
these results. In [55], the authors use a similar reduction, but with an
offline regression oracle, for which there are many practical algorithms;
unfortunately, the result requires the contexts to arrive in i.i.d. fashion,
unlike the more general result of [25]. Here, we show that whenever a function
class is learnable in the offline setting, we can still use the SquareCB
reduction to get a no-regret algorithm that is efficient with respect to an
ERM oracle in the smooth contextual bandit setting.

We consider the setting described in [26] with the modification that contexts
arrive in a $\sigma$-smooth manner. Formally, at each $1\leq t\leq T$, Nature
selects a $\sigma$-smooth distribution $p_{t}$, and samples $x_{t}\sim p_{t}$,
then samples a loss function $\ell_{t}$ independently from some distribution
depending on $x_{t}$. The learner selects an action $a_{t}\in[K]$ and observes
$\ell_{t}(a_{t})$. We are given a function class
$\mathcal{F}:\mathcal{X}\times[K]\to[0,1]$ and suppose that there is some
unknown $f^{\ast}\in\mathcal{F}$ such that
$\mathbb{E}\left[\ell_{t}(a)|x_{t}=x\right]=f^{\ast}(x,a)$ for all
$x\in\mathcal{X}$ and $a\in[K]$. The goal is to minimize regret to the best
policy induced by $\mathcal{F}$, where for any $f\in\mathcal{F}$, we define
$\pi_{f}(x)=\operatorname*{argmin}_{a\in[K]}f(x,a)$, i.e., we wish to minimize

$\operatorname{Reg}_{CB}(T)=\sum_{t=1}^{T}\ell_{t}(a_{t})-\ell_{t}(\pi_{f^{\ast}}(x_{t}))$
(28)

We have the following result:

######  Theorem 13.

Suppose we are in the $\sigma$-smooth Contextual Bandit setting described
above. If we run SquareCB with the relaxation-induced online regressor from
(15), we can achieve

$\mathbb{E}\left[\operatorname{Reg}_{CB}(T)\right]\leq 12\frac{K\log
T}{\sqrt{\sigma}}\sqrt{T\mathcal{R}_{T}(\mathcal{F})}$ (29)

with $O\left(\sqrt{T}\log T\right)$ calls to the ERM oracle per round. If we
instead instantiate SquareCB with the FTPL algorithm from Theorem 10 and
$\mathcal{R}_{T}(\mathcal{F})=o(T)$, then
$\mathbb{E}\left[\operatorname{Reg}_{CB}(T)\right]=o(T)$ as well with only $1$
call to the ERM oracle per round.

To prove Theorem 13, we observe that if the contexts arrive in a
$\sigma$-smooth manner with respect to $\mu$, then the context-action pairs
can be taken to be $\frac{\sigma}{K}$-smooth with respect to
$\mu\otimes\text{Unif}([K])$. We then apply [25, Theorem 1]. The details and
precise rates in the case of the FTPL instantiation can be found in Appendix
G.

Note that the regret bound does not have optimal rates with respect to either
$T$ or $K$. In order to recover optimal rates with respect to $T$, we would
need to find an algorithm that exhibits fast rates with square loss in the
smoothed-online setting. This is an interesting further direction in its own
right, in addition to the practical implications on better rates for efficient
algorithms for contextual bandits.

##  Appendix B Related Work

Here we describe some recent of the recent literature and how it relates to
our work.

Smoothed Analysis. Smoothed analysis was first introduced in [58], where it
was proposed as an explanation for the gap between theoretical lower bounds
and excellent empirical performance of the simplex algorithm [37]. Since then,
smoothed analysis has been applied to analyze the performance of algorithms
for many other problems which are known to be hard in the worst-case, such as
the $k$-means algorithm for clustering [8], the flip algorithm for finding a
local max-cut [22], and more generally better-response algorithms for finding
Nash equilibria in network coordination games [10] (see also [43] for a more
comprehensive overview).

In the context of learning theory, [48] gave a nonconstructive proof
demonstrating its utility for the specific case of threshold functions, while
[34, 35] proved that the minimax regret of binary classification in smoothed
online learning is governed by VC dimension.

Online Learning. The optimal statistical rates attainable by online learning
algorithms was shown to be characterized by sequential complexity measures of
the function class in [50, 44, 49]. This characterization was extended to the
case of constrained adversaries (including the special case of smoothed
adversaries) in [48]. Several subsequent papers have established further
refined regret bounds [9, 46]. The profusion of publications relating to
algorithmic questions about online learning is too large to enumerate here,
but notable relevant work includes [33], which provides lower bounds on
oracle-efficiency and [47] which introduces a general framework for
constructing algorithms.

Follow The Perturbed Leader. Our proper learning algorithm is motivated by
Follow the Perturbed Leader (FTPL) [39, 31]. FTPL has been successful for many
problems, including learning from experts [39], multi-armed bandits [7], and
online structured learning [16], which includes as special cases problems such
as online shortest path [60] and online learning of permutations [36]. There
is a similar diversity in methods of proving regret bounds for FTPL style
algorithms, including potential-based analysis [6, 16] and relaxation methods
[48]. A common approach, which we adopt, is to show that the algorithm is
stable [39, 4, 20, 3]. One of the primary advantages of our FTPL approach is
the fact that we do not generate independent noise for each function in our
class. In [19], the authors present an FTPL-style algorithm which aims to do
something similar, mitigating the computational burden by sharing randomness
between functions. Their method, however, is very different from ours in that
they rely on their new notions of _admissability_ and _implementability_ of a
matrix to transform low-dimensional independent noise into a more structured
form; in contradistinction, we directly use a Gaussian Process on the function
class to ensure stability of our algorithm.

Contextual Bandits. There is a rich history of studying contextual bandits.
Most relevant to our work is the series of papers [25, 55, 26] which provides
a reduction from contextual bandits to an online learning oracle. See these
papers for further references.

##  Appendix C Proofs from Section 3

###  C.1 Proofs Related to the Coupling

We first extend [35, Theorem 2.1] by providing a simpler and more general
proof of the coupling between $\mathscr{D}\in\mathfrak{P}_{T}(\sigma,\mu)$ and
independent random variables drawn according to $\mu$. While we use a slightly
different version (Lemma 24) in the proof of Theorem 3, the following lemma is
both simpler for exposition and is used in the proofs of the results in
Section 4.

######  Lemma 14.

Suppose that $\mathscr{D}\in\mathfrak{P}_{T}({\sigma},{\mu})$. Then for any
$T$ there exists a measure $\Pi$ with random variables
$(x_{t},Z_{t}^{j})_{\begin{subarray}{c}1\leq t\leq T\\\ 1\leq j\leq
k\end{subarray}}$ satisfying the following properties:

  1. 1.

$x_{t}$ is distributed according to $p_{t}(\cdot|x_{1},\dots,x_{t-1})$ induced
by $\mathscr{D}$.

  2. 2.

$\\{Z_{t}^{j}\\}_{\begin{subarray}{c}1\leq t\leq T\\\ 1\leq j\leq
k\end{subarray}}$ are iid according to $\mu$

  3. 3.

With probability at least $1-Te^{-\sigma k}$, we have
$x_{t}\in\\{Z_{t}^{j}\\}_{1\leq j\leq k}$ for all $t$

###### Proof.

We construct the coupling recursively. For any $t$, suppose that
$Z_{s}^{j},x_{s}$ has been constructed for $s<t$. If $t=0$ then this is the
empty set. Now, sample $Z_{t}^{j}$ iid according to $\mu$. Let
$\pi_{t}^{j}=\sigma\frac{dp_{t}}{d\mu}(Z_{t}^{j})$. Note that $\pi_{t}^{j}\leq
1$ by the assuption of $\sigma$-smoothness. Construct the random set
$S_{t}\subset[k]$ by adding $j$ to $S_{t}$ iwth probability $\pi_{t}^{j}$
independently for each $1\leq j\leq k$. If $S_{t}$ is nonempty, then sample
$x_{t}$ uniformly from $S_{t}$. Otherwise, sample $x_{t}$ independently from
$p_{t}$. We now show that this process exhibits the desired properties.

It is clear form the construction that $Z_{t}^{j}$ are iid according to $\mu$.
To verify that $x_{t}\in\\{Z_{t}^{j}\\}$, we note that for any $t,j$, we have

$\displaystyle\mathbb{P}(Z_{t}^{j}\in
S_{t})=\mathbb{E}_{\mu}\left[\sigma\frac{dp_{t}}{d\mu}(Z_{t}^{j})\right]=\sigma$
(30)

Because the $Z_{t}^{j}$ are added to $S_{t}$ independently, the probability
that $S_{t}$ is empty is $(1-\sigma)^{k}$. Thus, by a union bound, the
probability that there exists some $t\leq T$ such that any $S_{t}$ is empty is
bounded by $T(1-\sigma)^{k}\leq Te^{-\sigma k}$.

Finally, to see that $x_{t}$ are distributed according to $p_{t}$, let
$A\subset\mathcal{X}$ be measurable and $\chi_{A}$ denote the indicator for
$A$. We compute:

$\displaystyle\mathbb{P}(Z_{t}^{j}\in A|Z_{t}^{j}\in S_{t})$
$\displaystyle=\frac{\mathbb{P}\left(Z_{t}^{j}\in A\text{ and }Z_{t}^{j}\in
S_{t}\right)}{\mathbb{P}\left(Z_{t}^{j}\in S_{t}\right)}$ (31)
$\displaystyle=\frac{\mathbb{P}\left(Z_{t}^{j}\in A\text{ and }Z_{t}^{j}\in
S_{t}\right)}{\sigma}$ (32)
$\displaystyle=\frac{\mathbb{E}_{\mu}\left[\chi_{A}\sigma\frac{dp_{t}}{d\mu}(Z_{t}^{j})\right]}{\sigma}$
(33) $\displaystyle=\mathbb{E}_{p_{t}}\left[\mathbf{1}_{A}\right]=p_{t}(A)$
(34)

where the second equality follows from (30), the third equality follows from
the construction of $S_{t}$, and the penultimate equality following from the
definnition of the Radon-Nikodym derivative. The result follows. ∎

We further note that the coupling in Lemma 14 is optimal with respect to the
dependence on $k$ in the third requirement, as seen in the following
proposition.

######  Proposition 15.

For any $\sigma<1$ and non-atomic measure $\mu$ on $\mathcal{X}$, there exists
a measure on $\mathcal{X}$, $p$ such that $p$ is $\sigma$-smooth with respect
to $\mu$ and the following property holds. For any coupling $\Pi$ which has
random variables $Z^{j}$ for $1\leq j\leq k$ and $X$ such that $Z^{j}\sim\mu$
are independent and $X\sim p$, the probability that $X\in\\{Z^{j}\\}$ is
bounded below by $1-(1-\sigma)^{k}$.

###### Proof.

Given $\mu$, let $A\subset\mathcal{X}$ denote a measurable set such that
$\mu(A)=\sigma$. Let $p$ be a measure on $\mathcal{X}$ such that
$\frac{dp}{d\mu}=\frac{1}{\sigma}\chi_{A}$. Then $p$ is $\sigma$-smooth with
respect to $\mu$. Note that if $Z^{j}\sim\mu$ then with probability
$1-\sigma$, $Z^{j}\not\in A$. Thus with probability $(1-\sigma)^{k}$, none of
$Z^{j}$ are in $A$. Thus with probability at least $(1-\sigma)^{k}$,
$X\not\in\\{Z^{j}|1\leq j\leq k\\}$ if $X\sim p$. The result follows. ∎

###  C.2 Preliminaries on Distribution-Dependent Sequential Rademacher
Complexity

In this section, we recall the definition of the distribution-dependent
sequential Rademacher complexity from [48] and how it relates to the minimax
regret. To begin, we formally construct a measure $\rho_{\mathscr{D}}$ used in
the definition of distribution-dependent sequential Rademacher complexity from
[48].

Throughout, we follow [50, 48] and introduce as our basic object in analyzing
sequential complexities a tree. Specifically, we consider complete binary
trees ${\mathbf{z}}$ of depth $T$ with each vertex of the tree labelled by
some element of $\mathcal{X}$. We associate each $\varepsilon\in\\{\pm
1\\}^{T}$ to a path in the tree from the root to a leaf, where the path is
constructed recursively by beginning at the root and at each level going to
the left if $\varepsilon_{t-1}=1$ and to the right otherwise. For a given tree
${\mathbf{z}}$, we denote by ${\mathbf{z}}_{t}(\varepsilon)$ the label of the
$t^{th}$ vertex along the path $\varepsilon$.

Let $\mathscr{D}$ be the joint distribution of
$z_{1},\dots,z_{T}\in\mathcal{Z}$. Define $p_{t}(\cdot,|z_{1},\dots,z_{t-1})$
as the distribution under $\mathscr{D}$ of $z_{t}$, given $z_{s}$ for $s<t$.
We recursively construct the measure $\rho_{\mathscr{D}}$ on pairs of binary
trees as follows. We first construct the roots of each tree by sampling
${\mathbf{z}}_{0}(\varepsilon),{\mathbf{z}}_{0}^{\prime}(\varepsilon)\sim
p_{0}$ independently. Suppose we have
${\mathbf{z}}_{1:t-1},{\mathbf{z}}^{\prime}_{1:t-1}$ already constructed. For
any $s<t$, let

$\chi_{s}(\varepsilon)=\begin{cases}{\mathbf{z}}_{s}(\varepsilon)&\varepsilon_{s}=1\\\
{\mathbf{z}}_{s}^{\prime}(\varepsilon)&\varepsilon_{s}=-1\end{cases}$ (35)

then sample
${\mathbf{z}}_{t}(\varepsilon),{\mathbf{z}}_{t}^{\prime}(\varepsilon)$
independently from
$p_{t}(\cdot|\chi_{1}(\varepsilon),\dots,\chi_{t-1}(\varepsilon))$. In this
way, we can recursively construct the measure $\rho_{\mathscr{D}}$.

With the definition of $\rho_{\mathscr{D}}$ completed, we can now define the
key notion of complexity.

######  Definition 16 (Definition 2 from [48]).

Given a space $\mathcal{Z}$, a function class
$\mathcal{F}\subset[-1,1]^{\mathcal{Z}}$, and a joint distribution
$\mathscr{D}$, let $\rho_{\mathscr{D}}$ be the measure on an ordered pair of
binary trees of depth $T$ with values in $\mathcal{Z}$, defined above. Then,
we define the distribution-dependent sequential Rademacher complexities as

$\displaystyle\mathcal{R}_{T}^{seq}(\mathcal{F},\mathscr{D})=\mathbb{E}_{({\mathbf{z}},{\mathbf{z}}^{\prime})\sim\rho_{\mathscr{D}}}\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}f({\mathbf{z}}_{t}(\varepsilon))\right]$
(36)

If $\mathfrak{P}$ is a class of distributions $\mathscr{D}$, we define

$\mathcal{R}_{T}^{seq}(\mathcal{F},\mathfrak{P})=\sup_{\mathscr{D}\in\mathfrak{P}}\mathcal{R}_{T}^{seq}(\mathcal{F},\mathscr{D})$
(37)

for any class of distributions $\mathfrak{P}$.

Intuitively, depending on the nature of the class $\mathfrak{P}$,
$\mathcal{R}_{T}^{seq}(\mathcal{F},\mathfrak{P})$ interpolates between the
classical batch Rademacher complexity (if we force $\mathscr{D}$ to be iid)
and the fully adversarial sequential Rademacher complexity from [50]. In the
special case that $\mathfrak{P}=\mathfrak{P}(\sigma,\mu)$, we see that we are
much closer to the classical Rademacher complexity than to the fully
adversarial analogue. Indeed, using Lemma 24, which is an extension of the
coupling result contained in Lemma 14 above, we can bound the distribution-
dependent sequential Rademacher complexity by that of the classical Rademacher
complexity:

######  Lemma 17.

Let $\mathcal{F}\subset[-1,1]^{\mathcal{X}}$ be a function class. Then, for
any $k\in\mathbb{N}$,

$\mathcal{R}_{T}^{seq}(\mathcal{F},\mathfrak{P}(\sigma,\mu))\leq\left(\frac{4}{\sigma}\log
T\right)\mathbb{E}_{\mu}\left[\mathcal{R}_{kT}(\mathcal{F})\right]+2T^{2}e^{-\sigma
k}$ (38)

In particular, in the case that $\mathsf{vc}(\mathcal{F})\leq d$, we have:

$\mathcal{R}_{T}^{seq}(\mathcal{F},\mathfrak{P}(\sigma,\mu))\lesssim\sqrt{Td\log\left(\frac{T}{\sigma}\right)}$
(39)

and in the case that $\mathsf{vc}(\mathcal{F},\delta)\lesssim\delta^{-p}$, we
have:

$\mathcal{R}_{T}^{seq}(\mathcal{F},\mathfrak{P}(\sigma,\mu))\lesssim\left(T\log\left(\frac{T}{\sigma}\right)\right)^{\max\left(\frac{1}{2},1-\frac{1}{p}\right)}$
(40)

###### Proof.

Let $A$ be the high probability event in Lemma 24 below, i.e., the event that
$x_{t}\in\left\\{Z_{t}^{j}\right\\}_{1\leq j\leq k}$ for all $t$. We have for
any $\mathscr{D}\in\mathfrak{P}(\sigma,\mu)$,

$\displaystyle\mathcal{R}_{T}^{seq}(\mathcal{F},\mathscr{D})$
$\displaystyle=\mathbb{E}_{({\mathbf{z}},{\mathbf{z}}^{\prime})\sim\rho_{\mathscr{D}}}\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}f({\mathbf{z}}_{t}(\varepsilon))\right]$
(41)
$\displaystyle=\mathbb{E}_{\Pi}\mathbb{E}_{\varepsilon}\left[\chi_{A}\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}f({\mathbf{z}}_{t}(\varepsilon))\right]+\mathbb{E}_{\Pi}\mathbb{E}_{\varepsilon}\left[\chi_{A^{c}}\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}f({\mathbf{z}}_{t}(\varepsilon))\right]$
(42)
$\displaystyle\leq\mathbb{E}_{\Pi}\mathbb{E}_{\varepsilon}\left[\chi_{A}\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}f({\mathbf{z}}_{t}(\varepsilon))+\sum_{j\text{
such that
}Z_{t}^{j}\neq{\mathbf{z}}_{t}(\varepsilon)}\mathbb{E}_{\varepsilon_{t,j}}\left[\varepsilon_{t,j}f(Z_{t}^{j})\right]\right]+2T^{2}e^{-\sigma
k}$ (43)
$\displaystyle\leq\mathbb{E}_{\Pi}\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{j=1}^{k}\sum_{t=1}^{T}\varepsilon_{t,j}f(Z_{t}^{j})\right]+2T^{2}e^{-\sigma
k}$ (44) $\displaystyle\leq 2T^{2}e^{-\sigma
k}+\mathbb{E}_{\mu}\left[\mathcal{R}_{kT}(\mathcal{F})\right]$ (45)

where $\Pi$ is the coupling in Lemma 24, the first inequality follows because
$\varepsilon_{t}$ is mean zero, the second inequality follows by Jensen’s, and
the lastfollows by definition of Rademacher complexity. Setting
$k=\frac{2}{\sigma}\log T$ concludes the proof. ∎

As is the case in both the fully adversarial and classical regimes, we see
that $\mathcal{V}_{T}^{prop}(\mathcal{F},\mathfrak{P})$ is determined up to
constants by $\mathcal{R}_{T}^{seq}(\mathcal{F},\mathfrak{P})$:

######  Proposition 18 (Theorem 3 and Lemma 20 from [48]).

For any $\mathcal{F}$, we have

$\mathcal{V}_{T}^{\textrm{prop}}(\mathcal{F},\mathfrak{P}(\sigma,\mu))\leq
2\sup_{\mathscr{D}\in\widetilde{\mathfrak{P}}_{T}({\sigma},{\mu})}\mathcal{R}_{T}^{seq}(\ell\circ\mathcal{F},\mathscr{D}).$
(46)

where we recall from Definition 1 that
$\widetilde{\mathfrak{P}}_{T}({\sigma},{\mu})$ is the class of distributions
on $(x_{t},y_{t})$ such that the $x_{t}$ are chosen in a $\sigma$-smooth way
and the $y_{t}$ are adversarial. In the special case where $\ell$ is absolute
loss, we also have

$\sup_{\mathscr{D}\in\widetilde{\mathfrak{P}}_{T}({\sigma},{\mu})}\mathcal{R}_{T}^{seq}(\ell\circ\mathcal{F},\mathscr{D})\leq\mathcal{V}_{T}^{\textrm{prop}}(\mathcal{F},\mathfrak{P}(\sigma,\mu))$
(47)

In the statement of Proposition 18, $\ell\circ\mathcal{F}$ denotes the class
of functions in $[0,1]^{\mathcal{X}\times[-1,1]}$ of the form
$(x,y)\mapsto\ell(f(x),y)$, for $f\in\mathcal{F}$. By Proposition 18, it
suffices to provide upper and lower bounds on
$\mathcal{R}_{T}^{seq}(\ell\circ\mathcal{F},\widetilde{\mathfrak{P}}_{T}({\sigma},{\mu}))$,
which is significantly more tractable than working with the iterated operators
involved in $\mathcal{V}_{T}^{\textrm{prop}}(\mathcal{F},\mathfrak{P})$.

In the proof below, we will also need a sequential analogue of
$\mathsf{vc}(\mathcal{F},\alpha)$:

######  Definition 19 (Definition 7 from [50]).

We say that a $\mathcal{X}$-valued binary tree of depth $T$, ${\mathbf{x}}$,
is shattered by $\mathcal{F}$ at scale $\delta\geq 0$ if there exists an
$\mathbb{R}$-valued binary tree $\mathbf{s}$ of depth $T$ such that for all
$\varepsilon\in\\{\pm 1\\}^{T}$, there exists an
$f_{\varepsilon}\in\mathcal{F}$ such that

$\varepsilon_{t}\left(f({\mathbf{x}}_{t}(\varepsilon))-\mathbf{s}_{t}(\varepsilon)\right)\geq\frac{\alpha}{2}$
(48)

Define the sequential fat-shattering dimension of $\mathcal{F}$,
$\mathsf{fat}_{\delta}(\mathcal{F})$ as the maximal $T$ such that there exists
a tree of depth $T$ shattering $\mathcal{F}$ at scale $\delta$.

Finally, we require a structural result showing that worst-case sequential
Rademacher complexity contracts with Lipschitz loss functions:

######  Lemma 20 (Lemma 13 from [50]).

Let $\mathcal{F}$ be a function class with values in $[-1,1]$ and let $\ell$
be $L$-Lipschitz. Then,

$\sup_{\mathscr{D}\in\Delta\left(\mathcal{X}^{\times
T}\right)}\mathcal{R}_{T}^{seq}(\ell\circ\mathcal{F},\mathscr{D})\lesssim
L\log^{\frac{3}{2}}(T)\sup_{\mathscr{D}\in\Delta\left(\mathcal{X}^{\times
T}\right)}\mathcal{R}_{T}^{seq}(\mathcal{F},\mathscr{D})$ (49)

Because the supremum in Lemma 20 is taken over all distributions on the
product space $\mathcal{X}^{\times T}$, the above distribution-dependent
sequential Rademacher complexities are reduced to the adversarial sequential
Rademacher complexities of [50]. In the following section, we show that on
small domains, we can control $\mathsf{fat}_{\delta}(\mathcal{F})$ by
$\mathsf{vc}(\mathcal{F},\delta)$.

###  C.3 Sequential and Batch Complexities

In this section, we prove the following lemma, which bounds the sequential
fat-shattering dimension by the scale-sensitive VC dimension when the domain
is small:

######  Lemma 21.

Let $\mathcal{F}$ be a function class from $\mathcal{X}$ to $[-1,1]$ and let
$\mathsf{fat}_{\delta}(\mathcal{F})$ denote the sequential fat-shattering
dimension of $\mathcal{F}$ (Definition 19). Then, for any $\alpha>0$,

$\mathsf{fat}_{\delta}(\mathcal{F})\lesssim\mathsf{vc}\left(\mathcal{F},c\alpha\delta\right)\log^{1+\alpha}\left(\frac{C\left|\mathcal{X}\right|}{\mathsf{vc}\left(\mathcal{F},c\delta\right)\delta}\right)$
(50)

In order to prove this result, we require a generalization of the Sauer-Shelah
lemma [53, 54]. We first define covering numbers with respect to the $\sup$
norm:

######  Definition 22.

Let $\mathcal{F}$ be a class of functions on $\mathcal{X}$. A set $S$ of
functions on $\mathcal{X}$ is a $\delta$ covering if for all
$f\in\mathcal{F}$, there exists a $s_{f}\in S$ such that

$\sup_{x\in\mathcal{X}}\left|s_{f}(x)-f(x)\right|\leq\delta$ (51)

We let $N(\mathcal{F},\delta)$ to be the minimal size of a $\delta$-covering
of $\mathcal{F}$.

In order to bound $\mathsf{fat}_{\delta}(\mathcal{F})$ by
$\mathsf{vc}(\mathcal{F},\delta)$, we first recall a result that bounds
$N(\mathcal{F},\delta)$ by $\mathsf{vc}(\mathcal{F},\delta)$:

######  Theorem 23 (Theorem 4.4 from [52]).

Let $\mathcal{F}$ be a function class on $\mathcal{X}$, a finite set, to
$[-1,1]$. Then for any $\alpha>0$, there are constants $c,C>0$ such that

$\log
N(\mathcal{F},\delta)\lesssim\mathsf{vc}(\mathcal{F},c\alpha\delta)\log^{1+\alpha}\left(\frac{C\left|\mathcal{X}\right|}{\mathsf{vc}(\mathcal{F},c\delta)\delta}\right)$
(52)

The above theorem is an intermediate result, so our bound will come down to
comparing $\mathsf{fat}_{\delta}(\mathcal{F})$ to the covering numbers. We can
now provide the main proof in the section.

###### (Lemma 21).

We first note that $2^{\mathsf{fat}_{\delta}(\mathcal{F})}\leq
N\left(\mathcal{F},\frac{\delta}{3}\right)$. To see this, let
$d=\mathsf{fat}_{\delta}(\mathcal{F})$ and let ${\mathbf{x}}$ denote a depth
$d$ tree that shatters $\mathcal{F}$ at scale $\delta$ with witness tree
$\mathbf{s}$. Let $S$ be a $\frac{\delta}{2}$ net for $\mathcal{F}$. For each
$\varepsilon\in\\{\pm 1\\}^{d}$, let $f_{\varepsilon}$ be the function that
realizes the shattering on path $\varepsilon$. If
$v_{f_{\varepsilon}}\in\mathcal{F}$ is the projection into $S$, then we note
that the function $\varepsilon\mapsto v_{f_{\varepsilon}}$ is injective.
Indeed, if there are two different $\varepsilon,\varepsilon^{\prime}$ mapping
to the same $v\in S$, then there is some $t$ such that
$\varepsilon_{t}=-\varepsilon_{t}^{\prime}$ but
$\varepsilon_{s}=\varepsilon_{s}^{\prime}$ for $s<t$. Thus
${\mathbf{x}}_{t}(\varepsilon)={\mathbf{x}}_{t}(\varepsilon^{\prime})$ and
$\mathbf{s}_{t}(\varepsilon)=\mathbf{s}_{t}(\varepsilon^{\prime})$. We know,
however, that

$\left|f_{\varepsilon}({\mathbf{x}}_{t}(\varepsilon))-f_{\varepsilon^{\prime}}({\mathbf{x}}_{t}(\varepsilon^{\prime}))\right|\leq\left|f_{\varepsilon}({\mathbf{x}}_{t}(\varepsilon))-v({\mathbf{x}}_{t}(\varepsilon))\right|+\left|v({\mathbf{x}}_{t}(\varepsilon))-f_{\varepsilon^{\prime}}({\mathbf{x}}_{t}(\varepsilon))\right|\leq\frac{2\delta}{3}$
(53)

Thus we have by the shattering assumption,

$\displaystyle\frac{\delta}{2}$
$\displaystyle\leq\varepsilon_{t}\left(f_{\varepsilon}({\mathbf{x}}_{t}(\varepsilon)-\mathbf{s}_{t}({\mathbf{x}}_{t}(\varepsilon)))\right)$
(54)
$\displaystyle=-\varepsilon_{t}^{\prime}\left(f_{\varepsilon}({\mathbf{x}}_{t}(\varepsilon)-\mathbf{s}_{t}({\mathbf{x}}_{t}(\varepsilon)))\right)$
(55)
$\displaystyle\leq-\varepsilon_{t}^{\prime}\left(f_{\varepsilon^{\prime}}({\mathbf{x}}_{t}(\varepsilon)-\varepsilon_{t}^{\prime}\frac{2\delta}{3}-\mathbf{s}_{t}({\mathbf{x}}_{t}(\varepsilon)))\right)$
(56) $\displaystyle\leq-\frac{\delta}{2}+\frac{2\delta}{3}$ (57)
$\displaystyle\leq\frac{\delta}{6}$ (58)

Thus we have a contradiction and the mapping is injective. But this means then
that $2^{d}\leq N\left(\mathcal{F},\frac{\delta}{2}\right)$ as desired. By
Theorem 23, for any $\alpha>0$, we have

$\displaystyle\mathsf{fat}_{\delta}(\mathcal{F})$
$\displaystyle\lesssim\log\left(2^{\mathsf{fat}_{\delta}(\mathcal{F})}\right)\lesssim\log\left({N\left(\mathcal{F},\frac{\delta}{3}\right)}\right)$
(59)
$\displaystyle\lesssim\mathsf{vc}\left(\mathcal{F},c\alpha\delta\right)\log^{1+\alpha}\left(\frac{C\left|\mathcal{X}\right|}{\mathsf{vc}\left(\mathcal{F},c\alpha\delta\right)\delta}\right)$
(60)

as desired. ∎

We are now ready to prove the main results from Section 3.

###  C.4 Proof of Theorem 3

By Proposition 18, it suffices to control the distribution-dependent
sequential Rademacher complexity of Definition 16, specialized to the case
that $\mathcal{Z}=\mathcal{X}\times[-1,1]$, and
$\mathscr{D}\in\mathfrak{P}_{T}({\sigma},{\mu})$. We first adapt Lemma 14 to
construct a coupling with $\varepsilon,\rho_{\mathscr{D}}$ and independent
samples from $\mu$; this will allow us to move from sequential Rademacher
complexity to standard Rademacher complexity. The lemma is again a variant of
the coupling in [35], albeit simpler to describe and preserving independence
between $\varepsilon$ and $Z_{t}^{j}$. We have the following lemma:

######  Lemma 24.

Suppose that $\mathscr{D}\in\widetilde{\mathfrak{P}}_{T}({\sigma},{\mu})$.
Then for any $T$ there exists a measure $\Pi$ with random variables
$(\varepsilon_{1:T},{\mathbf{z}}(\varepsilon),{\mathbf{z}}^{\prime}(\varepsilon),Z_{t}^{j},Z_{t}^{j^{\prime}})_{\begin{subarray}{c}1\leq
t\leq T\\\ 1\leq j\leq k\end{subarray}}$ satisfying the following properties,
where we write
${\mathbf{z}}(\varepsilon)=({\mathbf{x}}(\varepsilon),{\mathbf{y}}(\varepsilon)),{\mathbf{z}}^{\prime}(\varepsilon)=({\mathbf{x}}^{\prime}(\varepsilon),{\mathbf{y}}^{\prime}(\varepsilon))$
to separate the $\mathcal{X}$\- and $[-1,1]$-components of
${\mathbf{z}}(\varepsilon)\in\mathcal{Z}$:

  1. 1.

$\varepsilon_{1:T}$ are iid Rademacher random variables.

  2. 2.

$({\mathbf{z}},{\mathbf{z}}^{\prime})$ is distributed according $\rho$.

  3. 3.

$\\{Z_{t}^{j},Z_{t}^{j^{\prime}}\\}$ are iid according to $\mu$

  4. 4.

$\\{\varepsilon,Z_{t}^{j},Z_{t}^{j^{\prime}}\\}$ are independent

  5. 5.

With probability at least $1-2T(1-\sigma)^{k}$,
${\mathbf{x}}_{t}(\varepsilon)\in\\{Z_{t}^{j}\\}_{1\leq j\leq k}$ for all $t$

###### Proof.

Given $\mathscr{D}$, let:

  * •

$p_{t}(\cdot|(x_{1},y_{1}),\ldots,(x_{t-1},y_{t-1}))$ denote the distribution
of $x_{t}$ under $\mathscr{D}$ given $(x_{s},y_{s})$ for $s<t$ (since
$\mathscr{D}\in\widetilde{\mathfrak{P}}_{T}({\sigma},{\mu})$, $p_{t}$ is
$\sigma$-smooth with respect to $\mu$ a.s.);

  * •

$q_{t}(\cdot|(x_{1},y_{1}),\ldots,(x_{t-1},y_{t-1}),x_{t})$ denote the
distribution of $y_{t}$ under $\mathscr{D}$ given $(x_{s},y_{s})$ for $s<t$
and $x_{t}$.

We construct the coupling recursively. For any $t$, suppose that
$Z_{s}^{j},Z_{s}^{j^{\prime}},\varepsilon_{s},{\mathbf{z}}_{s}(\varepsilon)$
has been constructed for $s<t$. If $t=0$ then this is the empty set. Now,
sample $Z_{t}^{j},Z_{t}^{j^{\prime}}$ iid according to $\mu$ and
$\varepsilon_{t}$ a Rademacher random variable. Let
$\pi_{t}^{j}=\sigma\frac{dp_{t}}{d\mu}(Z_{t}^{j})$. Note that $\pi_{t}^{j}\leq
1$ by the assumption of $\sigma$-smoothness. As in the proof of Lemma 14,
construct the random set $S_{t}$ by adding each $Z_{t}^{j}$ to $S_{t}$ with
probability $\pi_{t}^{j}$. If $S_{t}$ is nonempty, then sample
${\mathbf{x}}_{t}(\varepsilon)$ independently from $S_{t}$ uniformly at
random; if $S_{t}$ is empty, sample ${\mathbf{x}}_{t}(\varepsilon)$ from
$p_{t}(\cdot|{\mathbf{z}}_{1}(\varepsilon),\ldots,{\mathbf{z}}_{t-1}(\varepsilon))$.
Then sample ${\mathbf{y}}_{t}(\varepsilon)$ independently from
$q_{t}(\cdot|\mathbf{z}_{1}(\varepsilon),\ldots,\mathbf{z}_{t-1}(\varepsilon),{\mathbf{x}}_{t}(\varepsilon))$,
and set
$\mathbf{z}_{t}(\varepsilon)=({\mathbf{x}}_{t}(\varepsilon),{\mathbf{y}}_{t}(\varepsilon))$.

We may construct the ${\mathbf{z}}_{t}^{\prime}(\varepsilon)$ similarly by
constructing a set $S_{t}^{\prime}$ in the same way, using
$Z_{t}^{j^{\prime}}$ instead of $Z_{t}^{j}$. Finally sample $\varepsilon_{t}$
independently.

It is clear from the construction that $\varepsilon_{t}$, $t\in[T]$, are
independent Rademacher random variables. Similarly, it is clear that
$Z_{t}^{j},Z_{t}^{j^{\prime}}$ are iid according to $\mu$ and independent of
$\varepsilon$. The remainder of the properties are proved in the same way as
in Lemma 14. ∎

We are now ready to prove the theorem.

###### Proof.

(Theorem 3) By Theorem 18, it suffices to bound the distribution-dependent
sequential Rademacher complexity. Let $\Pi$ be the coupling in Lemma 24 and
let $A$ denote the event that
${\mathbf{x}}_{t}(\varepsilon)\in\\{Z_{t}^{j}\\}_{1\leq j\leq k}$ for all $t$
(we continue to write
${\mathbf{z}}_{t}(\varepsilon)=({\mathbf{x}}_{t}(\varepsilon),{\mathbf{y}}_{t}(\varepsilon))$).
Then we compute for a fixed $k$,

$\displaystyle\sup_{\mathscr{D}\in\mathfrak{P}}\mathbb{E}_{\rho_{\mathscr{D}},\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}\ell(f({\mathbf{x}}_{t}(\varepsilon)),{\mathbf{y}}_{t}(\varepsilon))\right]$
(61)
$\displaystyle\leq\mathbb{E}_{\Pi,\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}\ell(f({\mathbf{x}}_{t}(\varepsilon)),{\mathbf{y}}_{t}(\varepsilon))\right]$
(62)
$\displaystyle\leq\mathbb{E}_{\Pi,\varepsilon}\left[\chi_{A^{c}}\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}\ell(f({\mathbf{x}}_{t}(\varepsilon)),{\mathbf{y}}_{t}(\varepsilon))\right]+\mathbb{E}_{\Pi,\varepsilon}\left[\chi_{A}\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}\ell(f({\mathbf{x}}_{t}(\varepsilon)),{\mathbf{y}}_{t}(\varepsilon))\right]$
(63) $\displaystyle\leq 2T^{2}e^{-\sigma
k}+\mathbb{E}_{\Pi,\varepsilon}\left[\chi_{A}\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}\ell(f({\mathbf{x}}_{t}(\varepsilon)),{\mathbf{y}}_{t}(\varepsilon))\right]$
(64)

By the tower property of expectations, denoting by
$\mathcal{F}|_{\\{Z_{t}^{j}\\}}$ the restriction of $\mathcal{F}$ to the set
of all $Z_{t}^{j}$, we have

$\displaystyle\mathbb{E}_{\Pi,\varepsilon}\left[\chi_{A}\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}\ell(f({\mathbf{x}}_{t}(\varepsilon)),{\mathbf{y}}_{t}(\varepsilon))\right]$
$\displaystyle=\mathbb{E}_{Z_{t}^{j}\stackrel{{\scriptstyle
iid}}{{\sim}}\mu}\left[\mathbb{E}_{\Pi}\left[\chi_{A}\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}\ell(f({\mathbf{x}}_{t}(\varepsilon)),{\mathbf{y}}_{t}(\varepsilon))\bigg{|}\\{Z_{t}^{j}\\}_{\begin{subarray}{c}1\leq
t\leq T\\\ 1\leq j\leq k\end{subarray}}\right]\right]$ (65)
$\displaystyle=\mathbb{E}_{Z_{t}^{j}\stackrel{{\scriptstyle
iid}}{{\sim}}\mu}\left[\mathbb{E}_{\Pi}\left[\chi_{A}\sup_{f\in\mathcal{F}|_{\\{Z_{t}^{j}\\}}}\sum_{t=1}^{T}\varepsilon_{t}\ell(f({\mathbf{x}}_{t}(\varepsilon)),{\mathbf{y}}_{t}(\varepsilon))\bigg{|}\\{Z_{t}^{j}\\}_{\begin{subarray}{c}1\leq
t\leq T\\\ 1\leq j\leq k\end{subarray}}\right]\right]$ (66)
$\displaystyle\lesssim L\log^{\frac{3}{2}}(T)$
$\displaystyle\sup_{\left\\{Z_{t}^{j}\right\\}_{\begin{subarray}{c}1\leq t\leq
T\\\ 1\leq j\leq
k\end{subarray}}}\sup_{{\mathbf{x}}}\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}|_{\\{Z_{t}^{j}\\}}}\sum_{t=1}^{T}\varepsilon_{t}f({\mathbf{x}}_{t}(\varepsilon))\right]$
(67)

where the last inner supremum is over all ${\mathbf{x}}$ such that
${\mathbf{x}}$ is a $\\{Z_{t}^{j}\\}$-labelled binary tree of depth $T$; the
last inequality follows, then, from Lemma 20. Let
$\mathsf{fat}_{\delta}(\mathcal{F})$ denote the sequential fat-shattering
dimension in Definition 19. We may apply [9, Corollary 10 and Proposition 15],
which bounds the worst-case sequential Rademacher complexity by the sequential
fat-shattering dimension to get

$\displaystyle\sup_{\left\\{Z_{t}^{j}\right\\}_{\begin{subarray}{c}1\leq t\leq
T\\\ 1\leq j\leq
k\end{subarray}}}\sup_{{\mathbf{x}}}\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}|_{\\{Z_{t}^{j}\\}}}\sum_{t=1}^{T}\varepsilon_{t}f({\mathbf{x}}_{t}(\varepsilon))\right]\lesssim\sup_{\left\\{Z_{t}^{j}\right\\}_{\begin{subarray}{c}1\leq
t\leq T\\\ 1\leq j\leq k\end{subarray}}}\inf_{\alpha>0}\left\\{\alpha
T+\sqrt{T}\int_{\alpha}^{1}\sqrt{\mathsf{fat}_{\delta}\left(\mathcal{F}_{\\{Z_{t}^{j}\\}}\right)}d\delta\right\\}$
(68)

By Lemma 21, we have for any $\beta>0$,

$\mathsf{fat}_{\delta}\left(\mathcal{F}_{\\{Z_{t}^{j}\\}}\right)\lesssim\mathsf{vc}(\mathcal{F},c\beta\delta)\log^{1+\beta}\left(\frac{C\left|\\{Z_{t}^{j}\\}_{\begin{subarray}{c}1\leq
t\leq T\\\ 1\leq j\leq
k\end{subarray}}\right|}{\mathsf{vc}\left(\mathcal{F},c\beta\delta\right)\delta}\right)\lesssim\mathsf{vc}(\mathcal{F},c\beta\delta)\log^{1+\beta}\left(\frac{CkT}{\mathsf{vc}\left(\mathcal{F},c\beta\delta\right)\delta}\right)$
(69)

independent of the realization of $Z_{t}^{j}$. Thus we have

$\displaystyle\mathbb{E}_{Z_{t}^{j}\stackrel{{\scriptstyle iid}}{{\sim}}\mu}$
$\displaystyle\left[\mathbb{E}_{\Pi}\left[\chi_{A}\sup_{f\in\mathcal{F}|_{\\{Z_{t}^{j}\\}}}\sum_{t=1}^{T}\varepsilon_{t}\ell(f({\mathbf{x}}_{t}(\varepsilon)),{\mathbf{y}}_{t}(\varepsilon))\bigg{|}\\{Z_{t}^{j}\\}_{\begin{subarray}{c}1\leq
t\leq T\\\ 1\leq j\leq k\end{subarray}}\right]\right]$ (70)
$\displaystyle\lesssim L\log^{\frac{3}{2}}(T)\inf_{\alpha>0}\left\\{\alpha
T+\sqrt{T}\int_{\alpha}^{1}\sqrt{\mathsf{vc}(\mathcal{F},c\beta\delta)\log^{1+\beta}\left(\frac{CkT}{\mathsf{vc}\left(\mathcal{F},c\beta\delta\right)\delta}\right))}d\delta\right\\}$
(71)

Putting everything together, we have

$\displaystyle\sup_{\mathscr{D}\in\mathfrak{P}}$
$\displaystyle\mathbb{E}_{\rho_{\mathscr{D}},\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{t=1}^{T}\varepsilon_{t}\ell(f({\mathbf{x}}_{t}(\varepsilon)),{\mathbf{y}}_{t}(\varepsilon))\right]$
(72) $\displaystyle\lesssim 2T^{2}e^{-\sigma
k}+L\log^{\frac{3}{2}}(T)\inf_{\alpha>0}\left\\{\alpha
T+\sqrt{T\log^{1+\beta}\left(\frac{3kT}{\mathsf{vc}\left(\mathcal{F},c\beta\alpha\right)\alpha}\right)}\int_{\alpha}^{1}\sqrt{\mathsf{vc}(\mathcal{F},c\beta\delta)}d\delta\right\\}$
(73)

Setting $k=\frac{2\log T}{\sigma}$ and $\beta=1$ concludes the proof.

∎

###  C.5 Proof of Proposition 4

Let $\mathcal{F}$ be the class of thresholds on the unit interval, i.e.,

$\mathcal{F}=\left\\{x\mapsto\operatorname{sign}(x-\theta)|\theta\in[0,1]\right\\}$
(74)

It is well-known that $\mathsf{vc}(\mathcal{F})=1$. Consider an adversary that
sets $x_{1}=0$, $x_{2}=1$, $y_{1}=-1$, $y_{2}=1$ and for all $t>2$, sets

$\displaystyle x_{t}=x_{t-1}-y_{t-1}2^{-(t-2)}$ (75)

and the $y_{t}$ are independent Rademacher random variables. Note that by
construction, the adversary is realizable with respect to $\mathcal{F}$ in the
sense that for any realization of the $(x_{t},y_{t})$, there is some
$f\in\mathcal{F}$ with $f(x_{t})=y_{t}$ for all $t$. Also by construction, we
see that the expected number of mistakes in $T$ rounds is $\frac{T}{2}$. For
fixed $T$, let

$\mathscr{P}_{T}=\left\\{\frac{1}{T}\sum_{t=1}^{T}\delta_{x_{t}}\right\\}$
(76)

be the set of empirical distributions generated by the contexts over all
realizations of $x_{1},\dots,x_{T}$. Note that for each
$\mu\in\mathscr{P}_{T}$, the support has size $T$ and thus the adversary
constructed above is $\left(\frac{1}{T}\right)$-smooth with respect to some
$\mu\in\mathscr{P}_{T}$. The result follows by noting that if
$T\leq\frac{1}{\sigma}$ then the adversary is $\sigma$-smooth with respect to
some $\mu\in\mathscr{P}_{T}$.

##  Appendix D Proofs from Section 4

###  D.1 Proofs Related to Relaxations

###### Proof.

(Proposition 6) It suffices to prove (10) as the other property follows
immediately from the construction. For the sake of convenience, we denote

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

We begin by noting that [45, Lemma 5.1] tells us that due to the convexity of
$\ell$ in the first argument, it suffices to replace distributions $q_{t}$
over $[-1,1]$ with values $\widehat{y}_{t}\in[-1,1]$. In particular,

$\displaystyle\inf_{q_{t}\in\Delta([-1,1])}$
$\displaystyle\sup_{y_{t}\in[-1,1]}\mathbb{E}_{q_{t}}\left[\ell(\widehat{y}_{t},y_{t})\right]+\mathbb{E}_{\mu,\varepsilon}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t}(f)\right]$
(78)
$\displaystyle=\inf_{\widehat{y}_{t}\in[-1,1]}\sup_{y_{t}\in[-1,1]}\ell(\widehat{y}_{t},y_{t})+\mathbb{E}_{\mu,\varepsilon}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t}(f)\right]$
(79)

Now, omitting the feasible set for $\widehat{y}_{t},y_{t}$ to ease the
notational load, we plug in our relaxation:

$\displaystyle\inf_{\widehat{y}_{t}}$
$\displaystyle\sup_{y_{t}}\ell(\widehat{y}_{t},y_{t})+\mathbb{E}_{\mu,\varepsilon}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t}(f)\right]$
(80)
$\displaystyle=\inf_{\widehat{y}_{t}}\sup_{y_{t}}\mathbb{E}_{\mu,\varepsilon}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)+\ell(\widehat{y}_{t},y_{t})-\ell(f(x_{t}),y_{t})\right]$
(81)
$\displaystyle\leq\inf_{\widehat{y}_{t}}\sup_{y_{t}}\mathbb{E}_{\mu,\varepsilon}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)+\partial\ell(\widehat{y}_{t},y_{t})(\widehat{y}_{t}-f(x_{t}))]\right]$
(82)
$\displaystyle\leq\inf_{\widehat{y}_{t}}\sup_{y_{t}}\sup_{g_{t}\in[-L,L]}\mathbb{E}_{\mu,\varepsilon}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)+g_{t}(\widehat{y}_{t}-f(x_{t}))\right]$
(83)
$\displaystyle=\inf_{\widehat{y}_{t}}\max_{g_{t}\in\\{-L,L\\}}\mathbb{E}_{\mu,\varepsilon}\left[g_{t}\widehat{y}_{t}+\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)-g_{t}f(x_{t})\right]$
(84)

where we let $\partial\ell$ denote a subgradient of $\ell$ with respect to the
first argument. The first inequality follows by convexity, the second
inequality follows by Lipschitzness, and the last equality follows because the
inner expectation is convex as a function of $g_{t}$ and so obtains its
maximum on the boundary. Let $d_{t}$ denote a distribution on $\\{-L,L\\}$;
the $y_{t}$ vanishes because it only appeared in the
$\partial\ell(\widehat{y}_{t},y_{t})$ and this was bounded by $g_{t}$. Then by
the minimax theorem, we have

$\displaystyle\inf_{\widehat{y}_{t}}$
$\displaystyle\max_{g_{t}\in\\{-L,L\\}}\mathbb{E}_{\mu,\varepsilon}\left[g_{t}\widehat{y}_{t}+\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)-g_{t}f(x_{t})\right]$
(85) $\displaystyle=\sup_{d_{t}}\inf_{\widehat{y}_{t}}\mathbb{E}_{g_{t}\sim
d_{t}}\mathbb{E}_{\mu,\varepsilon}\left[g_{t}\widehat{y}_{t}+\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)-g_{t}f(x_{t})\right]$
(86) $\displaystyle\leq\sup_{d_{t}}\mathbb{E}_{g_{t}\sim
d_{t}}\mathbb{E}_{\mu,\varepsilon}\left[\inf_{\widehat{y}_{t}}\mathbb{E}_{g_{t}^{\prime}\sim
d_{t}}[g_{t}^{\prime}\widehat{y}_{t}]+\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)-g_{t}f(x_{t})\right]$
(87)
$\displaystyle\leq\sup_{d_{t}}\mathbb{E}_{\mu,\varepsilon}\mathbb{E}_{g_{t}\sim
d_{t}}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)+(\mathbb{E}_{g_{t}^{\prime}\sim
d_{t}}[g_{t}^{\prime}]-g_{t})f(x_{t})\right]$ (88)
$\displaystyle\leq\sup_{d_{t}}\mathbb{E}_{\mu,\varepsilon}\mathbb{E}_{g_{t},g_{t}^{\prime}\sim
d_{t}}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)+\varepsilon_{t}(g_{t}^{\prime}-g_{t})f(x_{t})\right]$
(89)
$\displaystyle\leq\sup_{d_{t}}\mathbb{E}_{\mu,\varepsilon}\mathbb{E}_{g_{t}\sim
d_{t}}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)+2\varepsilon_{t}g_{t}f(x_{t})\right]$
(90)
$\displaystyle=\mathbb{E}_{\mu,\varepsilon}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)+2L\varepsilon_{t}f(x_{t})\right]$
(91)

Now, it would seem that we are done, but note that $x_{t}\sim p_{t}$ while
$x_{s}\sim\mu$ for $s>t$. We thus apply
$\sup_{p_{t}\in\mathfrak{P}_{t}}\mathbb{E}_{x_{t}\sim p_{t}}$ to all of the
preceding equations and, adding back in the additive constant, we have shown

$\displaystyle\sup_{p_{t}\in\mathfrak{P}}$ $\displaystyle\mathbb{E}_{x_{t}\sim
p_{t}}\inf_{q}\sup_{y_{t}}\left[\mathbb{E}_{\widehat{y}_{t}\sim
q}[\ell(\widehat{y},y)]+\mathbf{Rel}_{T}(\mathcal{F}|x_{1},y_{1},\dots,x_{t},y_{t})\right]$
(92) $\displaystyle\leq\sup_{p_{t}\in\mathfrak{P}}\mathbb{E}_{x_{t}\sim
p_{t}}\mathbb{E}_{\mu,\varepsilon}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)+2L\varepsilon_{t}f(x_{t})\right]+(T-t)^{3}e^{-\sigma
k}$ (93)

Now, applying the coupling $\Pi$ from Lemma 14, we have

$\displaystyle\mathbb{E}_{x_{t}\sim p_{t}}$
$\displaystyle\mathbb{E}_{\mu,\varepsilon}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)+2L\varepsilon_{t}f(x_{t})\right]$
(94)
$\displaystyle=\mathbb{E}_{x_{t}\sim\Pi}\mathbb{E}_{\mu,\varepsilon}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)+2L\varepsilon_{t}f(x_{t})\right]$
(95)
$\displaystyle=\mathbb{E}_{x_{t}\sim\Pi}\mathbb{E}_{\mu,\varepsilon}\left[\chi_{A^{c}}\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)+2L\varepsilon_{t}f(x_{t})\right]$
(96)
$\displaystyle+\mathbb{E}_{x_{t}\sim\Pi}\mathbb{E}_{\mu,\varepsilon}\left[\chi_{A}\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)+2L\varepsilon_{t}f(x_{t})\right]$
(97)

where $A$ is the event that $x_{t}\in\\{Z_{t}^{j}\\}$ for $1\leq j\leq k$ and
$\chi_{A}$ is the indicator. For the first term, we have

$\displaystyle\mathbb{E}_{x_{t}\sim\Pi}$
$\displaystyle\mathbb{E}_{\mu,\varepsilon}\left[\chi_{A^{c}}\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)+2L\varepsilon_{t}f(x_{t})\right]$
(98) $\displaystyle\leq\mathbb{P}(A^{c})(n-t+1)\leq(n-t+1)^{2}e^{-\sigma k}$
(99)

For the second term, we have

$\displaystyle\mathbb{E}_{x_{t}\sim\Pi}$
$\displaystyle\mathbb{E}_{\mu,\varepsilon}\left[\chi_{A}\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)+2L\varepsilon_{t}f(x_{t})\right]$
(100)
$\displaystyle\leq\mathbb{E}_{\Pi,\mu,\varepsilon}\chi_{A}\sup_{f\in\mathcal{F}}\left[2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)+\sum_{j=1}^{k}\varepsilon_{t,j}f(Z_{t}^{j})\right]$
(101)
$\displaystyle=\mathbb{E}_{\mu,\varepsilon}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)\right]$
(102)

Putting this back together, we have

$\displaystyle\sup_{p_{t}\in\mathfrak{P}_{t}}$
$\displaystyle\mathbb{E}_{x_{t}\sim
p_{t}}\inf_{q}\sup_{y_{t}}\left[\mathbb{E}_{\widehat{y}_{t}\sim
q}[\ell(\widehat{y},y)]+\mathbf{Rel}_{T}(\mathcal{F}|x_{1},y_{1},\dots,x_{t},y_{t})\right]$
(103)
$\displaystyle\leq\mathbb{E}_{\mu,\varepsilon}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)\right]+(T-t+1)^{2}e^{-\sigma
k}+(T-t)^{3}e^{-\sigma k}$ (104)
$\displaystyle\leq\mathbb{E}_{\mu,\varepsilon}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)\right]+(T-t+1)^{3}e^{-\sigma
k}$ (105)
$\displaystyle=\mathbf{Rel}_{T}(\mathcal{F}|x_{1},y_{1},\dots,x_{t-1},y_{t-1})$
(106)

as desired. Thus we have an admissable relaxation. ∎

###### Proof.

(Theorem 7) It suffices to show the following claim:

$\displaystyle\sup_{p_{t}\in\mathfrak{P}}$ $\displaystyle\mathbb{E}_{x_{t}\sim
p_{t}}\left[\sup_{y_{t}\in[-1,1]}\ell(\widehat{y}_{t},y_{t})+\mathbb{E}_{\mu,\varepsilon}\left[\sup_{f\in\mathcal{F}}2L\sum_{s=t+1}^{T}\sum_{j=1}^{k}\varepsilon_{s,j}f(x_{s,j})-L_{t}(f)+(T-t)^{3}e^{-\sigma
k}\right]\right]$ (107)
$\displaystyle\leq\mathbf{Rel}_{T}(\mathcal{F}|x_{1},y_{1},\dots,x_{t-1},y_{t-1})$
(108)

Indeed, if this is the case, then $\widehat{y}_{t}$ is admissable with respect
to $\mathbf{Rel}_{T}(\mathcal{F}|\cdot)$, for which we already have a regret
bound in Proposition 6. To prove the stated claim, we have

$\displaystyle\sup_{y_{t}}$
$\displaystyle\mathbb{E}_{\mu,\varepsilon}\left[\ell(\widehat{y}_{t},y_{t})+\sup_{f\in\mathcal{F}}\left[2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t}(f)\right]\right]$
(109)
$\displaystyle\leq\mathbb{E}_{\mu,\varepsilon}\left[\sup_{y_{t}}\ell(\widehat{y}_{t},y_{t})+\sup_{f\in\mathcal{F}}\left[2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t}(f)\right]\right]$
(110)
$\displaystyle=\mathbb{E}_{\mu,\varepsilon}\left[\inf_{\widehat{y}}\sup_{y_{t}}\ell(\widehat{y},y_{t})+\sup_{f\in\mathcal{F}}\left[2L\sum_{s=t+1}^{n}\sum_{j=1}^{k}\varepsilon_{s,j}f(x_{s,j})-L_{t}(f)\right]\right]$
(111)

where the inequality follows by Jensen’s and the equality follow from the
construction of $\widehat{y}_{t}$ in (15). Now we may apply the proof of
Proposition 6 with the expectation with respect to $\mu,\varepsilon$ taking
place outside of the minimax operation. This shows that

$\displaystyle\mathbb{E}_{\mu,\varepsilon}$
$\displaystyle\left[\inf_{\widehat{y}}\sup_{y_{t}}\ell(\widehat{y},y_{t})]+\sup_{f\in\mathcal{F}}\left[2L\sum_{s=t+1}^{n}\sum_{j=1}^{k}\varepsilon_{s,j}f(x_{s,j})-L_{t}(f)\right]\right]+(T-t)^{3}e^{-\sigma
k}$ (112)
$\displaystyle\leq\mathbb{E}_{\mu,\varepsilon}\left[\sup_{f\in\mathcal{F}}2L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)\right]+(T-t+1)^{3}e^{-\sigma
k}$ (113)
$\displaystyle=\mathbf{Rel}_{T}(\mathcal{F}|x_{1},y_{1},\dots,x_{t-1},y_{t-1})$
(114)

as desired and the claim holds.

To prove the oracle efficiency claims, for a fixed $\delta$, let $S$ be a
$\delta$-discretization of $[-1,1]$ of size $\frac{2}{\delta}$. If we solve
the minimax problem (15) over $S$, then by the assumption of $\ell$ being
$L$-Lipshitz, we the regret bound for our approximate solution is greater than
that of the exact solution by at most an additive constant of $L\delta T$. In
general, for any fixed $\widehat{y}$, we can optimize

$\sup_{y_{t}\in
S}\left\\{\ell(\widehat{y},y_{t})+\sup_{f\in\mathcal{F}}\left[6L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t}(f)\right]\right\\}$
(115)

with $\left|S\right|$ calls to the ERM oracle. Now, note that (115) is convex
in $\widehat{y}$ by the assumption of convexity in the first argument of
$\ell$. By a simple three point method from zeroth order optimization [3],
which we prove as Lemma 25 for the sake of completeness below, we can minimize
(115) with respect to $\widehat{y}\in S$ with $O(\log\left|S\right|)$
evaluations of the supremum. Each evaluation of the supremum requires
$O(\left|S\right|)$ calls to the ERM oracle so we require
$O\left(\left|S\right|\log\left|S\right|\right)$ calls in total. Noting that
$\left|S\right|\leq\frac{1}{\delta}$, we can get

$\operatorname{Reg}_{T}(\widehat{y})\leq
2L\mathcal{R}_{kT}(\mathcal{F})+T^{3}e^{-\sigma k}+LT\delta$ (116)

with $O\left(\frac{T}{\delta}\log\left(\frac{1}{\delta}\right)\right)$ calls
to the ERM oracle. Setting $\delta=\frac{1}{L\sqrt{T}}$ recovers the bound in
the theorem statement. The last statement, on linear losses, is proven in
Lemma 26, where we give an explicit representation of the solution using only
2 oracle calls. Optimizing $k$ concludes the proof. ∎

######  Lemma 25.

Let $f:[0,1]\to\mathbb{R}$ be a convex function and let $S\subset[0,1]$. Then

$x_{0}\in\operatorname*{argmin}_{S}f$ (117)

can be found with $O(\log\left|S\right|)$ calls to a value oracle that returns
$f(x)$ given input $x\in S$.

###### Proof.

Motivated by [3], we describe the following recursive algorithm that shrinks
$S$ until it contains only one point, yet always includes the minimizer. Let
$S_{0}=S$. To construct $S_{i+1}$ from $S_{i}$, order the points
$x_{1},\dots,x_{m}\in S_{i}$ such that $x_{i}<x_{j}$ for all $i<j$. Let
$z_{1},z_{2},z_{3}$ be the $\frac{1}{4}$, $\frac{1}{2}$, and $\frac{3}{4}$
quanatiles of $S$ respectively and evaluate $f(z_{1})$, $f(z_{2})$, and
$f(z_{3})$ with three calls to the value oracle. There are several cases:

#### $\mathbf{f(z_{1})>f(z_{2})<f(z_{3})}$

If the middle point is smaller than either point on the end, then be the
convexity of $f$ we know that the minimum must occcur for some $x$ such that
$z_{1}<x<z_{3}$. In this case let $S_{i+1}$ contain all the points $x\in
S_{i}$ such that $z_{1}<x<z_{3}$. Note that
$\left|S_{i+1}\right|\leq\frac{1}{2}\left|S_{i}\right|$.

#### $\mathbf{f(z_{1})<f(z_{2})>f(z_{3})}$

This case corresponds to the middle point being higher than the end points.
This is not possible, however, as $f$ is convex.

#### $\mathbf{f(z_{1})<f(z_{2})<f(z_{3})}$

In this case, convexity assures us that the minimizer cannot be at any point
$x\geq z_{2}$ and so we let $S_{i+1}$ to be the set of all points $x\in S_{i}$
such that $x<z_{2}$. Note that
$\left|S_{i+1}\right|\leq\frac{1}{2}\left|S_{i}\right|$.

#### $\mathbf{f(z_{1})>f(z_{2})>f(z_{3})}$

This is the mirror image of the previous case and can be handled similarly.

#### $\mathbf{f(z_{1})=f(z_{2})=f(z_{3})}$

In this case, convexity ensures that the minimizer must have $x\leq z_{1}$ or
$x\geq z_{3}$ and so we let $S_{i+1}$ be the set of $x\in S_{i}$ satisfying
this constraint. Again,
$\left|S_{i+1}\right|\leq\frac{1}{2}\left|S_{i}\right|$.

In any case, with three calls to the value oracle, we reduce the size of
$S_{i}$ by a factor of 2. Thus we can find $x_{0}$ in $O(\log\left|S\right|)$
calls as claimed. ∎

######  Lemma 26.

Suppose we are in the situation of Theorem 7 and the loss
$\ell(\widehat{y},y)=\frac{1-\widehat{y}y}{2}$. Then the problem (15) can be
solved with two calls to the ERM oracle. In fact, $\widehat{y}_{t}$ is given
by

$\displaystyle\frac{1}{2}$
$\displaystyle\sup_{f\in\mathcal{F}}\left[6L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)-\ell(f(x_{t}),1)\right]$
(118)
$\displaystyle-\frac{1}{2}\sup_{f\in\mathcal{F}}\left[6L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t-1}(f)-\ell(f(x_{t}),-1)\right]$
(119)

###### Proof.

We are trying to minimize with respect to $\widehat{y}\in[-1,1]$.

$\sup_{y_{t}\in
S}\left\\{\ell(\widehat{y},y_{t})+\sup_{f\in\mathcal{F}}\left[6L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t}(f)\right]\right\\}$
(120)

Independent of $\widehat{y}$, if $\ell$ is linear in $y$, then the expresion
over which we are taking the supremum in (120) is convex in $y$ and thus
$y_{t}\in\\{\pm 1\\}$. For the sake of simplicity, suppose that

$\sup_{f\in\mathcal{F}}\left[6L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f(x_{s,j})-L_{t}(f)\right]$
(121)

is maximized by functions $f_{+}$ and $f_{-}$ depending on if $y_{t}=1$ or
$y_{t}=-1$ (in the general case, we could take a sequence of functions
attaining the supremum). Let

$\displaystyle a_{+}$
$\displaystyle=6L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f_{+}(x_{s,j})-L_{t}(f_{+})$
(122) $\displaystyle a_{-}$
$\displaystyle=6L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f_{-}(x_{s,j})-L_{t}(f_{-})$
(123)

Then the solution to (15) is given by

$\min_{\widehat{y}\in[-1,1]}\max\left(\frac{1-\widehat{y}}{2}+a_{+},\frac{1+\widehat{y}}{2}+a_{-}\right)$
(124)

The maximum is taken over two linear functions of $\widehat{y}$ with opposite
slope and so the minimax result is where they intersect, assuming they
intersect somewhere in $[-1,1]$, which they do if
$\left|a_{+}-a_{-}\right|\leq 1$. Note that

$\displaystyle a_{+}$
$\displaystyle=6L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f_{+}(x_{s,j})-L_{t}(f_{+})$
(125)
$\displaystyle=6L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f_{+}(x_{s,j})-L_{t-1}(f_{+})-\ell(f_{+}(x_{t}),1)+\ell(f_{+}(x_{t}),-1)-\ell(f_{+}(x_{t}),-1)$
(126) $\displaystyle\geq
6L\sum_{j=1}^{k}\sum_{s=t+1}^{T}\varepsilon_{s,j}f_{-}(x_{s,j})-L_{t}(f_{-})-\ell(f_{+}(x_{t}),1)+\ell(f_{+}(x_{t}),-1)$
(127) $\displaystyle\geq a_{-}-1$ (128)

By symmetry, $\left|a_{-}-a_{+}\right|\leq 1$. Thus,

$\widehat{y}_{t}=\frac{a_{+}-a_{-}}{2}\in[-1,1]$ (129)

solves the minimax problem with two calls to the ERM oracle. ∎

###  D.2 Proof of Proposition 8

In order to prove Proposition 8, we consider the following setting. Fix an
$\alpha>0$, suppose that $\mathsf{vc}(\mathcal{F},\alpha)=m$ and let
$x_{1},\dots,x_{m}$ shatter $\mathcal{F}$ at scale $\alpha$. We let $p_{t}$ be
uniform on $x_{1},\dots,x_{m}$ and let $\mu=(1-\sigma)\delta_{x^{\ast}}+\sigma
p_{t}$, where $x^{\ast}$ is a distinguished point satisfying $f(x^{\ast})=0$
for all $f\in\mathcal{F}$. Note that $p_{t}$ is $\sigma$-smooth with respect
to $\mu$. We compare the expected Rademacher complexity sampling $n$ points
according to $\mu$ to that when sampling according to $p_{t}$. We require two
lemmata.

######  Lemma 27.

Suppose we are in the above setting and $X_{1},\dots,X_{T}$ are sampled
independently according to $\mu$. Then, with probability at least $1-\delta$,
the number of indices $i$ such that $X_{i}\neq x^{\ast}$ is at most $2\sigma
T$ if $T\geq\frac{3}{\sigma}\log\left(\frac{1}{\delta}\right)$.

###### Proof.

Let $Y_{i}=\mathbf{1}[X_{i}\neq x^{\ast}]$. Then $Y_{i}$ are independent
Bernoulli random variables with parameter $\sigma$ and the number of such
indices is the sum of $Y_{i}$. Applying Chernoff’s inequality, we have

$\mathbb{P}\left(\sum_{i=1}^{T}Y_{i}\geq 2\sigma T\right)\leq e^{-\frac{\sigma
T}{3}}$ (130)

The assumption of $T$ large enough concludes the proof. ∎

######  Lemma 28.

Suppose that we are in the setting described above and $X_{1},\dots,X_{T}$ are
sampled according to $p_{t}$. Suppose that $T\geq
8m\log\left(\frac{m}{\delta}\right)$. Then with probability at least
$1-\delta$, for each $1\leq j\leq m$, there are at least $\frac{T}{2m}$
indices $i$ such that $X_{i}=x_{j}$.

###### Proof.

Fix $j$ and let $Y_{i}=\mathbf{1}[X_{i}=x_{j}]$. Then the $Y_{i}$ are
independent Bernoulli random variables with parameter $\frac{1}{m}$. Letting
$S_{T}$ denote the sum of the $Y_{i}$, which is the desired number of indices,
we may apply Chernoff’s inequality to get

$\mathbb{P}\left(S_{T}\leq\frac{1}{2}\frac{T}{m}\right)\leq e^{-\frac{T}{8m}}$
(131)

and so with probability at least $1-\frac{\delta}{m}$, there are at least
$\frac{T}{2m}$ indices $i$ such that $X_{i}=x_{j}$. Applying a union bound
concludes the proof. ∎

We may now adapt an argument from [42] and [57, Lemma A.2] to lower bound the
Rademacher complexity according to $p_{t}$:

######  Lemma 29.

Suppose that we are in the above setting and suppose that $T\geq 8m\log(2m)$.
Then,

$\mathbb{E}_{p_{t}}\left[\mathcal{R}_{T}(\mathcal{F})\right]\geq\frac{\alpha}{8}\sqrt{\mathsf{vc}(\mathcal{F},\alpha)T}$
(132)

###### Proof.

Let $\chi_{A}$ denote the indicator of the high probability event $A$ from
Lemma 28. Consider any fixed choice of $X_{1},\ldots,X_{T}$ so that the event
$A$ holds. For each $j\in[m],k\in[T/(2m)]$, let $\phi(j,m)\in[T]$ denote the
$k$th smallest value of $i$ so that $X_{i}=x_{j}$ (that all such $\phi(j,m)$
exist is guaranteed by $A$). Furthermore let $\Phi\subset[T]$ denote the image
of $\phi$, so that $|\Phi|=T/2$. Next, for any $\varepsilon\in\\{-1,1\\}^{n}$,
define
$f^{\varepsilon}:=\operatorname*{arg\,max}_{f\in\mathcal{F}}\sum_{j=1}^{m}\sum_{k=1}^{T/(2m)}\varepsilon_{\phi(j,m)}f(x_{j})$.888If
the argmax does not exist, we may instead consider a sequence of functions
that approximates the argmax to arbitrarily small precision.

$\displaystyle\mathbb{E}_{p_{t}}\left[\mathcal{R}_{T}(\mathcal{F})\right]$
$\displaystyle=\mathbb{E}_{p_{t}}\left[\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{i=1}^{T}\varepsilon_{i}f(X_{i})\bigg{|}X_{1},\dots,X_{T}\right]\right]$
(133)
$\displaystyle\geq\mathbb{E}_{p_{t}}\left[\chi_{A}\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{i=1}^{T}\varepsilon_{i}f(X_{i})\bigg{|}X_{1},\dots,X_{T}\right]\right]$
(134)
$\displaystyle\geq\mathbb{E}_{p_{t}}\left[\chi_{A}\mathbb{E}_{\varepsilon}\left[\sum_{i=1}^{T}\varepsilon_{i}f^{\varepsilon}(X_{i})\bigg{|}X_{1},\dots,X_{T}\right]\right]$
(135)
$\displaystyle\geq\mathbb{E}_{p_{t}}\left[\chi_{A}\mathbb{E}_{\varepsilon}\left[\sum_{j=1}^{m}\sum_{k=1}^{\frac{T}{2m}}\varepsilon_{jk}f^{\varepsilon}(x_{j})\bigg{|}X_{1},\dots,X_{T}\right]\right]+\mathbb{E}_{p_{t}}\left[\chi_{A}\mathbb{E}_{\varepsilon}\left[\sum_{i\not\in\Phi}\varepsilon_{i}f^{\varepsilon}(X_{i})\bigg{|}X_{1},\dots,X_{n}\right]\right]$
(136)
$\displaystyle\geq\mathbb{E}_{p_{t}}\left[\chi_{A}\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{j=1}^{m}\sum_{k=1}^{\frac{T}{2m}}\varepsilon_{\phi(j,k)}f(x_{j})\bigg{|}X_{1},\dots,X_{T}\right]\right]$
(137)
$\displaystyle=\mathbb{P}(A)\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{j=1}^{m}\sum_{k=1}^{\frac{T}{2m}}\varepsilon_{\phi(j,k)}f(x_{j})\right]$
(138)

where (134) follows by Jensen’s inequality coupled with the fact that the
$\varepsilon_{i}$ are mean zero, and (137) follows since $\\{\varepsilon_{i}:\
i\in\Phi\\}$ are independent of $\\{\varepsilon_{i}:\ i\not\in\Phi\\}$ (so
that
$\mathbb{E}_{p_{t}}\left[\chi_{A}\mathbb{E}_{\varepsilon}\left[\sum_{i\not\in\Phi}\varepsilon_{i}f^{\varepsilon}(X_{i})\bigg{|}X_{1},\dots,X_{T}\right]\right]=0$),
and by definition of $f^{\varepsilon}$. By the triangle inequality and
symmetry of the $\varepsilon_{i}$, $i\in[T]$, we have

$\displaystyle\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{j=1}^{m}\sum_{k=1}^{\frac{T}{2m}}\varepsilon_{\phi(j,k)}f(x_{j})\right]$
$\displaystyle\geq\frac{1}{2}\mathbb{E}_{\varepsilon}\left[\sup_{f,f^{\prime}\in\mathcal{F}}\sum_{j=1}^{m}\sum_{k=1}^{\frac{T}{2m}}\varepsilon_{\phi(j,k)}(f(x_{j})-f^{\prime}(x_{j}))\right]$
(139)
$\displaystyle\geq\frac{1}{2}\mathbb{E}_{\varepsilon}\left[\sum_{j=1}^{m}\sum_{k=1}^{\frac{T}{2m}}\varepsilon_{\phi(j,k)}(f_{\varepsilon}(x_{j})-f_{\varepsilon}^{\prime}(x_{j}))\right]$
(140)

where $f_{\varepsilon},f_{\varepsilon}^{\prime}$ are chosen so that

$\displaystyle\operatorname{sign}\left(\sum_{k=1}^{\frac{T}{2m}}\varepsilon_{\phi(j,k)}\right)\left(f_{\varepsilon}(x_{j})-s_{j}\right)\geq\frac{\alpha}{2}$
$\displaystyle\operatorname{sign}\left(\sum_{k=1}^{\frac{T}{2m}}\varepsilon_{\phi(j,k)}\right)\left(f_{\varepsilon}^{\prime}(x_{j})-s_{j}\right)\leq-\frac{\alpha}{2}$
(141)

for some $s_{1},\dots,s_{m}\in\mathbb{R}$. Note that there exist such
$f_{\varepsilon},f_{\varepsilon}^{\prime}\in\mathcal{F}$ by the assumption
that $x_{1},\dots,x_{m}$ shatter $\mathcal{F}$ at scale $\alpha$. We thus have

$\displaystyle\mathbb{E}_{\varepsilon}\left[\sum_{j=1}^{m}\sum_{k=1}^{\frac{T}{2m}}\varepsilon_{\phi(j,k)}(f_{\varepsilon}(x_{j})-f_{\varepsilon}^{\prime}(x_{t}))\right]$
$\displaystyle\geq\frac{1}{2}\mathbb{E}_{\varepsilon}\left[\sum_{j=1}^{m}\left|\sum_{k=1}^{\frac{T}{2m}}\varepsilon_{\phi(j,k)}\right|\alpha\right]$
(142)
$\displaystyle\geq\frac{m}{2}\alpha\mathbb{E}_{\varepsilon}\left[\left|\sum_{i=1}^{\frac{T}{2m}}\varepsilon_{i}\right|\right]$
(143) $\displaystyle\geq\frac{m}{2}\alpha\sqrt{\frac{T}{4m}}$ (144)
$\displaystyle=\frac{\alpha}{4}\sqrt{Tm},$ (145)

where (144) follows from Khintchine’s inequality. By Lemma 28,
$\mathbb{P}(A)\geq\frac{1}{2}$. Thus, putting everything together, we have

$\mathbb{E}_{p_{t}}\left[\mathcal{R}_{T}(\mathcal{F})\right]\geq\frac{\alpha}{8}\sqrt{mT}$
(146)

We finally recall that $m=\mathsf{vc}(\mathcal{F},\alpha)$ and conclude the
proof. ∎

The last thing we need to do is provide an upper bound on
$\mathbb{E}_{\mu}\left[\mathcal{R}_{T}(\mathcal{F})\right]$. We can do this
using chaining and Lemma 27.

######  Lemma 30.

Suppose we are in the setting above and suppose that
$T\geq\frac{3}{\sigma}\log T$. Then there is an absolute constant $C$ such
that

$\mathbb{E}_{\mu}\left[\mathcal{R}_{T}(\mathcal{F})\right]\leq C\sqrt{\sigma
T}$ (147)

###### Proof.

Let

$A=\left\\{\left|\\{i|X_{i}\neq x^{\ast}\\}\right|\leq 2\sigma T\right\\}$
(148)

and let $\chi_{A}$ denote the indicator for this event. By Lemma 27,
$\mathbb{P}(A)\geq 1-\frac{1}{T}$. Note that as $\mathcal{F}$ is uniformly
bounded by $1$, we always have the trivial upper bound of
$\mathcal{R}_{T}(\mathcal{F})\leq T$ on any data set. We can thus compute

$\displaystyle\mathbb{E}_{\mu}\left[\mathcal{R}_{T}(\mathcal{F})\right]$
$\displaystyle=\mathbb{E}_{\mu}\left[\chi_{A}\mathcal{R}_{T}(\mathcal{F})\right]+(1-\mathbb{P}(A))T\leq\mathbb{E}_{\mu}\left[\chi_{A}\mathcal{R}_{T}(\mathcal{F})\right]+1$
(149)

By the definition of the event $A$, we have:

$\displaystyle\mathbb{E}_{\mu}\left[\chi_{A}\mathcal{R}_{T}(\mathcal{F})\right]$
$\displaystyle=\mathbb{E}_{\mu}\left[\chi_{A}\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{X_{i}\neq
x^{\ast}}\varepsilon_{i}f(X_{i})+\sum_{X_{i}=x^{\ast}}\varepsilon_{i}f(X^{\ast})\bigg{|}X_{1},\dots,X_{T}\right]\right]$
(150)
$\displaystyle=\mathbb{E}_{\mu}\left[\chi_{A}\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{X_{i}\neq
x^{\ast}}\varepsilon_{i}f(X_{i})\bigg{|}X_{1},\dots,X_{T}\right]\right]$ (151)
$\displaystyle\leq\sup_{X_{i}}\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{i=1}^{2\sigma
T}\varepsilon_{i}f(X_{i})\right]$ (152)

We may now apply [52] to get that

$\sup_{X_{i}}\mathbb{E}_{\varepsilon}\left[\sup_{f\in\mathcal{F}}\sum_{i=1}^{2\sigma
T}\varepsilon_{i}f(X_{i})\right]\leq C\sqrt{2\sigma
T}\int_{0}^{1}\sqrt{\mathsf{vc}(\mathcal{F},\alpha)}d\alpha$ (153)

Because $\mathsf{vc}(\mathcal{F},\alpha)\leq C\alpha^{-p}$ for some $p<2$, the
result follows. ∎

We are now ready to prove the main bound.

###### Proof.

(Proposition 8) Let $\alpha=\sqrt{\sigma}$ and set
$\mathcal{F},\mu,p_{t},\mathcal{X}$ as above. By Lemma 29 and Lemma 30, we
have

$\displaystyle\frac{\mathbb{E}_{p_{t}}[\mathcal{R}_{T}(\mathcal{F})]}{\mathbb{E}_{\mu}[\mathcal{R}_{T}(\mathcal{F})]}$
$\displaystyle\geq\frac{c\sqrt{\sigma\mathsf{vc}(\mathcal{F},\sqrt{\sigma})T}}{C\sqrt{\sigma
T}}=c\sqrt{\mathsf{vc}(\mathcal{F},\sqrt{\sigma})}\geq c\sigma^{-\frac{p}{4}}$
(154)

where the last inequality follows from the assumption on the complexity of
$\mathcal{F}$. We may now apply the lower bound in Proposition 18 with
$\mathscr{D}$ just independent copies of $p_{t}$. The result follows. ∎

##  Appendix E Proof of Theorem 10

In this section we prove Theorem 10, which gives a regret bound for the
follow-the-perturbed-leader (FTPL) algorithm (21) with respect to general
classes $\mathcal{F}$ for convex, Lipschitz loss functions. This result bounds
the regret of an FTPL style algorithm by a stability term and a term
corresponding to the size of the perturbation. In particular, we bound the
stability term by controlling the Wasserstein distance between the laws of
$\widehat{y}_{t}$ and $\widehat{y}_{t+1}$. The techniques involved are of
independent interest as we develop a novel Gaussian anti-concentration
inequality that applies even when the labels are not assumed smooth. We begin
by stating and proving the relevant variant of the BTL lemma. Then, in
Appendix E.1 we provide the stability bound, using our Gaussian anti-
concentration approach. We continue in Appendix E.2 by controlling the final
stability term in the below decomposition, in the special case of linear loss.
Finally, we conclude the proof in Appendix E.3 by extending from linear loss
to general loss in the case of smooth labels and applying a discretization
approach to recover full generality.

We consider the smoothed online setting with distribution $\mu$. More
specifically, we consider the following setting: for some parameter
$n\in\mathbb{N}$, for each time step $t\in[T+1]$, consider points
$X_{t,1},\ldots,X_{t,n}\in\mathcal{X}$, and define

$\displaystyle\forall
f\in\mathcal{F}:\qquad\hat{\omega}_{t,n}(f):=\frac{1}{\sqrt{n}}\cdot\sum_{i=1}^{n}\gamma_{t,i}\cdot
f(X_{t,i}),$ (155)

where $\gamma_{t,1},\ldots,\gamma_{t,n}$ are i.i.d. standard normal random
variables. We define $\hat{\mu}_{t,n}$ to be the distribution
$\hat{\mu}_{t,n}:=\frac{1}{n}\sum_{i=1}^{n}\delta_{X_{t,i}}$, where
$\delta_{X_{t,i}}$ denotes the point mass at $X_{t,i}$. In what follows we
will consider iterates $f_{t}$, $1\leq t\leq T+1$, satisfying, for some
$\zeta>0$,

$L_{t-1}(f_{t})+\eta\cdot\hat{\omega}_{t,n}(f_{t})\leq\operatorname*{argmin}_{f\in\mathcal{F}}L_{t-1}(f)+\eta\cdot\hat{\omega}_{t,n}(f)+\zeta.$
(156)

We begin with a classic regret decomposition based on the well-known “Be-the-
Leader” Lemma [39, 15]. We first prove a related, auxiliary result that allows
us to deal with different perturbations at each time step:

######  Lemma 31.

Suppose $f_{t}$, for $t\in[T]$, is defined as in (156), for any (adaptively
chosen) sequence