# Smoothed Online Classification can be Harder than Batch Classification

Vinod Raman Equal contribution  Unique Subedi††footnotemark:  and Ambuj Tewari

###### Abstract

We study online classification under smoothed adversaries. In this setting, at
each time point, the adversary draws an example from a distribution that has a
bounded density with respect to a fixed base measure, which is known apriori
to the learner. For binary classification and scalar-valued regression,
previous works (Haghtalab et al., 2020; Block et al., 2022) have shown that
smoothed online learning is as easy as learning in the iid batch setting under
PAC model. However, we show that smoothed online classification can be harder
than the iid batch classification when the label space is unbounded. In
particular, we construct a hypothesis class that is learnable in the iid batch
setting under the PAC model but is not learnable under the smoothed online
model. Finally, we identify a condition that ensures that the PAC learnability
of a hypothesis class is sufficient for its smoothed online learnability.

##  1 Introduction

Classification is a canonical machine learning task where the goal is to
classify examples in $\mathcal{X}$ into one of the possible classes in
$\mathcal{Y}$. There are two common classification settings based on how the
data is available to the learner: batch and online. In the batch setting, the
learner is provided with a fixed set of training samples that are used to
train a classifier, which is then deployed to make predictions on new, real-
world examples (Vapnik and Chervonenkis, 1971; Natarajan, 1989). On the other
hand, data arrives sequentially in the online setting and predictions need to
be made in each round (Littlestone, 1987; Daniely et al., 2011). The batch
setting is often studied under the iid assumption, whereas the stream can be
fully adversarial in the online setting.

For binary classification (i.e. $|\mathcal{Y}|=2$), the batch learnability of
a hypothesis class $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ under the
PAC model (Valiant, 1984) is characterized in terms of a combinatorial
parameter called the Vapnik-Chervonenkis ($\operatorname{VC}$) dimension of
$\mathcal{H}$. On the other hand, the Littlestone dimension characterizes the
learnability of $\mathcal{H}$ under the adversarial online model (Littlestone,
1987; Ben-David et al., 2009). As Haghtalab et al. (2020) remark, the latter
characterization is often interpreted as an impossibility result because even
simple classes like $1$-dimensional thresholds have infinite Littlestone
dimension. This hardness result arises mainly because the adversary can
deterministically choose hard examples, even possibly adapting to the
learner’s strategy. One way to circumvent this hardness result is to consider
a smoothed online model, where the adversary has to choose and draw examples
from sufficiently anti-concentrated distributions (Rakhlin et al., 2011;
Haghtalab, 2018; Haghtalab et al., 2020; Block et al., 2022). This idea is
inspired from the seminal work by Spielman and Teng (2004), who showed that
the smoothed analysis of the simplex method yields a polynomial time
complexity in the input size, instead of the known worst-case exponential time
complexity.

In smoothed online classification, a learner plays a game with the adversary
over $T\in\mathbb{N}$ rounds. Before the game begins, the adversary reveals a
base measure $\mu$ over $\mathcal{X}$ and an anti-concentration parameter
$\sigma>0$ to the learner. The distribution $\mu$ can be fairly non-
informative such as uniform when applicable for $\mathcal{X}$. Then, in each
round $t\in[T]$, the adversary picks a labeled sample
$(x_{t},y_{t})\in\mathcal{X}\times\mathcal{Y}$, where $x_{t}$ is drawn from a
$\sigma$-smooth distribution $\nu_{t}$ with respect to $\mu$. That is,
$\nu_{t}(E)\leq\mu(E)/\sigma$ for all measurable subsets $E$ in $\mathcal{X}$.
The adversary then reveals $x_{t}$ to the learner, who makes a prediction
$\hat{y}_{t}\in\mathcal{Y}$. Finally, the adversary reveals the true label
$y_{t}\in\mathcal{Y}$ and the learner suffers the loss
$\mathbbm{1}\\{\hat{y}_{t}\neq y_{t}\\}$. Given a hypothesis class
$\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$, the goal of the learner is to
minimize the regret, the difference between its cumulative loss and the best
possible cumulative loss over hypotheses in $\mathcal{H}$.

The smoothed online model interpolates between the iid setting ($\sigma=1$)
and the adversarial setting ($\sigma=0$). When $|\mathcal{Y}|=2$, Haghtalab
(2018) and Haghtalab et al. (2020) showed that all VC classes are learnable in
the smoothed setting with the regret
$O(\sqrt{T\,\operatorname{VC}(\mathcal{H})\,\log{(T/\sigma)}})$. Extending
this result to real-valued regression, where $\mathcal{Y}=[-1,1]$, with the
absolute-value loss, Block et al. (2022) showed that the finiteness of the
fat-shattering dimension (Bartlett et al., 1996; Alon et al., 1997) of
$\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ is a sufficient condition for
smoothed online learnability. Since the finiteness of $\operatorname{VC}$ and
fat-shattering dimensions are characterizations of learnability under the PAC
model, these results suggest that smoothed online learning may be as easy as
batch learning.

In this work, we study smoothed online classification for arbitrary label
spaces $\mathcal{Y}$ under _oblivious_ adversary – one that picks
$\sigma$-smooth distirbutions $\nu_{1},..,\nu_{T}$, samples
$x_{1}\sim\nu_{1}$, …, $x_{T}\sim\nu_{T}$ independently, and finally picks the
labels $y_{1},...,y_{T}$, all before the game begins. This obvlious model has
been studied in the past Wu et al. (2023), but is slightly different than the
one studied by (Haghtalab, 2018; Haghtalab et al., 2020; Block et al., 2022)
(see Section 2.1 for more details). For this model, we show that smoothed
online classification continues to be as easy as batch classification when
$|\mathcal{Y}|<\infty$. However, when $|\mathcal{Y}|$ is not finite, we show
that smoothed online classification can be _harder_ than batch classification.
We note that there has been recent interest in studying multiclass
learnability when $|\mathcal{Y}|$ is unbounded (Brukhim et al., 2022; Hanneke
et al., 2023; Pabbaraju, 2024).

######  Theorem.

_(Informal)_ Let $\mathcal{X}=[0,1]$. Then, there exists
$\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ that is PAC learnable but not
learnable in the smoothed online setting with
$\mu=\text{Uniform}(\mathcal{X})$ and $\sigma=1$.

We also provide a quantitative version of this theorem that shows a regret
lowerbound linear in $T$ even when $|\mathcal{Y}|<\infty$ but bigger than
$2^{T\log(T)}$. Note that this is tight up to a factor of $\log{T}$ because we
prove a sublinear upperbound as long as $|\mathcal{Y}|=2^{o(T)}$ in Section 4.
To prove these results, we exploit the large size of the label space to
construct a hypothesis class $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$
such that for every $h\in\mathcal{H}$, its output on a finite subset of
$\mathcal{X}$ effectively reveals its identity. We then show that such a
hypothesis class has a sample compression scheme of size $1$. Then, the result
“compression implies learning” by David et al. (2016) shows that $\mathcal{H}$
is PAC learnable. However, we show that even the adversary that generates iid
samples from $\text{Uniform}(\mathcal{X})$ can construct a difficult stream
for the learner. Our construction is inspired by the hypothesis class from
(Hanneke et al., 2024, Claim 5.4). However, a key challenge in our
construction is the fact that the adversary does not have full control over
the sequence of examples the learner will observe (due to $\sigma$-smoothness)
whereas the adversary in Hanneke et al. (2024) can pick hard examples
deterministically.

In light of this hardness result, we identify a sufficiency condition for
smoothed online learnability. To do so, let $\operatorname{B}(\mu,\sigma)$
denote the set of all $\sigma$-smooth distributions with respect to $\mu$. For
any $x_{1},\ldots,x_{n}\in\mathcal{X}$, let us define an empirical metric on
$d_{n}$ on $\mathcal{H}$ as
$d_{n}(h_{1},h_{2})=n^{-1}\sum_{i=1}^{n}\mathbbm{1}\\{h_{1}(x_{i})\neq
h_{2}(x_{i})\\}$. Define $\mathcal{N}(\varepsilon,\mathcal{H},d_{n})$ to be
the covering number of $\mathcal{H}$ under metric $d_{n}$. Then, $\mathcal{H}$
is said to have uniformly bounded expected empirical metric entropy (UBEME) if
$\sup_{n\in\mathbbm{N}}\sup_{\nu_{1:n}\in\operatorname{B}(\mu,\sigma)}\mathbbm{E}_{x_{1:n}\sim\nu_{1:n}}\left[\mathcal{N}(\varepsilon,\mathcal{H},d_{n})\right]<\infty$
for every fixed $\varepsilon>0$. We show that if $\mathcal{H}$ has the UBEME
property, then it online learnable under smoothed adversaries.

######  Theorem.

_(Informal)_ If
$\sup_{n\in\mathbbm{N}}\sup_{\nu_{1:n}\in\operatorname{B}(\mu,\sigma)}\mathbb{E}_{x_{1:n}\sim\nu_{1:n}}\left[\mathcal{N}(\varepsilon,\mathcal{H},d_{n})\right]<\infty$
for every fixed $\varepsilon,\sigma>0$, then $\mathcal{H}$ is smoothed online
learnable under the base measure $\mu$.

When $|\mathcal{Y}|=2$, Haussler’s packing lemma implies that
$\mathcal{N}(\varepsilon,\mathcal{H},d_{n})\leq\left(41\,\varepsilon^{-1}\right)^{\operatorname{VC}(\mathcal{H})}$
(Haussler, 1995). That is, every class with finite VC satisfies UBEME, and
thus our sufficiency condition recovers the result from Haghtalab (2018) on
the smoothed learnability of VC classes. For $|\mathcal{Y}|<\infty$, we
generalize the packing lemma to show that
$\mathcal{N}(\varepsilon,\mathcal{H},d_{n})\leq(\frac{22\,|\mathcal{Y}|}{\varepsilon})^{\operatorname{G}(\mathcal{H})}$,
where $\operatorname{G}(\mathcal{H})$ is the graph dimension of $\mathcal{H}$.
This inequality shows that PAC learnability of $\mathcal{H}$ is sufficient for
its smoothed online learnability when $|\mathcal{Y}|<\infty$.

A key contribution of our sufficiency result is going beyond VC and Graph
dimension and giving the weaker sufficiency condition than the worst-case
empirical entropy. Indeed, in Section 4, we show that our sufficiency
condition still provides meaningful upperbounds even when the VC and Graph
dimensions are infinite. To prove our sufficiency result, we show that UBEME
implies the bounded metric entropy of $\mathcal{H}$ with respect to the base
measure $\mu$. That is, for
$d_{\mu}(h_{1},h_{2})=\mathbb{P}_{x\sim\mu}[h_{1}(x)\neq h_{2}(x)]$, we have
$\mathcal{N}(\varepsilon,\mathcal{H},d_{\mu})<\infty$ for every fixed
$\varepsilon>0$. Then, we use algorithmic ideas from Haghtalab (2018) that
involve running multiplicative weights using the cover of $\mathcal{H}$ under
$d_{\mu}$. Unfortunately, when $|\mathcal{Y}|$ is unbounded, the sufficiency
condition (the UBEME of $\mathcal{H}$) is not necessary. This is demonstrated
by constant functions $\mathcal{H}=\\{x\mapsto a:a\in\mathbb{N}\\}$ that is
easy to learn but $\mathcal{N}(\varepsilon,\mathcal{H},d_{1})=\infty$.

Given our separation and sufficiency results, it is natural to ask for a
characterization of learnability for smoothed online classification. Any
meaningful characterization must be a joint property of both $\mathcal{H}$ and
$\mu$. This is because choosing $\mu$ to be a Dirac distribution will make any
$\mathcal{H}$, even the set of all measurable functions from $\mathcal{X}$ to
$\mathcal{Y}$, trivially learnable. Since the most natural joint complexity
measure of $\mathcal{H}$ and $\mu$ is
$\mathcal{N}(\varepsilon,\mathcal{H},d_{\mu})$, one might ask whether
$\mathcal{N}(\varepsilon,\mathcal{H},d_{\mu})<\infty$ for every
$\varepsilon>0$ is necessary and sufficient for smoothed online learnability
of $\mathcal{H}$ under $\mu$. Surprisingly, we show that this condition is
neither necessary nor sufficient (see Theorem 4.3). These results highlight
the difficulty of characterizing learnability in the smoothed setting.

##  2 Preliminaries

Let $\mathcal{X}$ denote the instance space and $\mathcal{Y}$ denote the label
space. We assume that $(\mathcal{X},\Sigma)$ is a measurable space and let
$\Pi(\mathcal{X})$ denote the set of all probability measures on
$(\mathcal{X},\Sigma)$. Let $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$
denote an arbitrary hypothesis class consisting of predictors
$h:\mathcal{X}\rightarrow\mathcal{Y}$. For any $T\in\mathbb{N}$, we use the
notation $z_{1:T}$ to denote the sequence $\\{z_{t}\\}_{t=1}^{T}$. Finally, we
let $[N]:=\\{1,2,\ldots,N\\}$.

###  2.1 Smoothed Online Learning

In the smoothed online model, an adversary plays a sequential game with the
learner over $T$ rounds. Before the game begins, the adversary reveals a base
measure $\mu\in\Pi(\mathcal{X})$ and a scalar $\sigma>0$ to the learner. As
mentioned before, $\mu$ can be non-informative measures such as uniform if
$\mathcal{X}$ is totally-bounded. Then, in each round $t\in[T]$, an adversary
picks a labeled sample $(x_{t},y_{t})\in\mathcal{X}\times\mathcal{Y}$, where
$x_{t}$ is drawn from a distribution $\nu_{t}\in\Pi(\mathcal{X})$ that
satisfies $\nu_{t}(E)\leq\frac{\mu(E)}{\sigma}$ for every $E\in\Sigma$. The
adversary then reveals $x_{t}$ to the learner $\mathcal{A}$. Using all the
past examples $(x_{1},y_{1}),\ldots,(x_{t-1},y_{t-1})$, the learner then makes
a potentially randomized prediction $\mathcal{A}(x_{t})$. The adversary then
reveals the true label $y_{t}\in\mathcal{Y}$ and the learner suffers the loss
$\mathbbm{1}\\{\mathcal{A}(x_{t})\neq y_{t}\\}$. Given a hypothesis class
$\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$, the goal of the learner is to
output predictions $\mathcal{A}(x_{t})$ that minimizes the regret, which is
the difference between its cumulative loss and the best possible cumulative
loss over hypotheses in $\mathcal{H}$. To formally define the regret, let
$\operatorname{B}(\mu,\sigma):=\\{\nu\in\Pi(\mathcal{X})\,:\nu(E)\leq\mu(E)/\sigma\quad\forall
E\in\Sigma\\}$ denote the set of all $\sigma$-smooth distributions on
$\mathcal{X}$ with respect to $\mu$. Given
$\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$, the worst-case expected
regret of an algorithm $\mathcal{A}$ is defined as

$\operatorname{R}^{\mu,\sigma}_{\mathcal{A}}(T,\mathcal{H}):=\sup_{\begin{subarray}{c}\nu_{1},\ldots,\nu_{T}\in\operatorname{B}(\mu,\sigma)\end{subarray}}\,\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\sup_{y_{1:T}}\left(\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\mathcal{A}}\,[\mathbbm{1}\\{\mathcal{A}(x_{t})\neq
y_{t}\\}]-\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\mathbbm{1}\\{h(x_{t})\neq
y_{t}\\}\right)\right].$

Note that as $\sigma\to 0$, the set $\operatorname{B}(\mu,\sigma)$ contains
all Dirac distributions on $\mathcal{X}$. This amounts to replacing
$\sup_{\begin{subarray}{c}\nu_{1},\ldots,\nu_{T}\in\,\operatorname{B}(\mu,\sigma)\end{subarray}}\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}[\cdot]$
operator in the definition of regret above by $\sup_{x_{1:T}}$, which yields
the expected regret of $\mathcal{A}$ in the fully adversarial model under an
oblivious adversary. Thus, our adversary is a generalization of the online
oblivious adversary for the smoothed setting. Given this definition of
expected regret, we adopt the minimax perspective to define the learnability
of a hypothesis class.

######  Definition 1 (Smoothed Online Learnability).

The class $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ is learnable in the
smoothed online setting if and only if for every $\sigma>0$ and
$\mu\in\Pi(\mathcal{X})$, we have

$\inf_{\mathcal{A}}\,\operatorname{R}^{\mu,\sigma}_{\mathcal{A}}(T,\mathcal{H})=o(T).$

Our worst-case expected regret is defined with respect to an _oblivious_
adversary that picks the entire stream $(x_{1},y_{1}),\ldots,(x_{T},y_{T})$
before the game begins. Moreover, the sequence of distributions
$\nu_{1},\ldots,\nu_{T}$ has to be chosen upfront before the sampling step
$(x_{1},\ldots,x_{T})\sim(\nu_{1},\ldots,\nu_{T})$. That is, the distribution
$\nu_{t}$ cannot depend on the realization of previous instances
$x_{1},\ldots,x_{t-1}$. This ensures that the instances $x_{1},\ldots,x_{T}$
are independent random variables. One can also consider an oblivious
adversary, where $\nu_{t}$ can depend on the past instances
$(x_{1},\ldots,x_{t-1})$ sampled from $(\nu_{1},\ldots,\nu_{t-1})$. Since the
primary contribution of this work is the hardness result in Section 3, we only
focus on the case where $\nu_{1},\ldots,\nu_{T}$ are chosen upfront. As the
first adversary is a special case of the second adversary, our hardness result
also applies for the second adversary. The fully general setting of adaptive
adversaries where $\nu_{t}$ can depend on the _entire_ history of the game up
to time point $t-1$ has been studied extensively in (Haghtalab et al., 2020;
Block et al., 2022), where the dependence among $x_{1},\ldots,x_{T}$ is
handled through coupling.

There are three natural choices for how $y_{t}$ may be selected by an
oblivious adversary. In the first choice, $y_{t}$ may depend only on the
$x_{t}\sim\nu_{t}$. In the second choice, $y_{t}$ may depend on prefix on
$x_{1}\sim\nu_{1},...,x_{t}\sim\nu_{t}$. Finally, in the last choice, $y_{t}$
may depend on the entire sample $x_{1}\sim\nu_{1},...,x_{T}\sim\nu_{T}.$ The
first choice is considered in Haghtalab (2018)and the second by Haghtalab et
al. (2020); Block et al. (2022). In this work, we focus on the third choice,
which has been considered by Wu et al. (2023). This choice is natural because
$\sigma$-smoothness is just a property of the instances and should not impact
how the labels are selected. Since the third choice is the strongest, our
sufficiency result in Section 4 holds for the first two choices. However,
establishing the separation result for the first two choices remains an open
question.

###  2.2 PAC Learning and Sample Compression Schemes

In contrast to existing work, we establish a separation between smoothed
online learnability and batch learnability. The notion of batch learnability
we consider is PAC learnability, a canonical model in statistical learning
theory. See Appendix A for a complete definition. To prove the agnostic PAC
learnability of hypothesis classes, we use the relationship between
learnability and the existence of sample compression schemes.

A compression scheme $(\kappa,\rho)$ consists of a compression function
$\kappa$ and a reconstruction function $\rho$. The compression function
$\kappa:\cup_{i\geq 1}(\mathcal{X}\times\mathcal{Y})^{i}\to\cup_{i\geq
1}(\mathcal{X}\times\mathcal{Y})^{i}$ maps a sample
$S=\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\}$ to a subsample
$S^{\prime}\subseteq S$. The reconstruction function $\rho:\cup_{i\geq
1}(\mathcal{X}\times\mathcal{Y})^{i}\to\mathcal{Y}^{\mathcal{X}}$ takes
$S^{\prime}$ as input and outputs a function $f\in\mathcal{Y}^{\mathcal{X}}$.
We define the size of the compression scheme $(\kappa,\rho)$ on a sample $S$
to be $|S^{\prime}|$, where $\kappa(S)=S^{\prime}$. We let the quantity $k(n)$
denote the maximum size of the compression scheme on all samples $S$ such that
$|S|=n$. A hypothesis class $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$
has a compression scheme $(\kappa,\rho)$ of size $k(n)$ if for every sample
$S=\\{(x_{1},h(x_{1})),\ldots,(x_{n},h(x_{n}))\\}$ for some $h\in\mathcal{H}$,
we have $f=\rho(\kappa(S))$ such that $f(x_{i})=h(x_{i})$ for all $i\in[n]$.

The compression scheme in David et al. (2016) is slightly more general as
their compression function $\kappa$ can output $(S^{\prime},b)$ where $b$ is a
finite bitstring. However, the restricted notion of a compression scheme
without $b$ is sufficient for our purpose. The following Theorem shows that
the existence of sample compression schemes for $\mathcal{H}$ implies agnostic
PAC learnability of $\mathcal{H}$.

######  Theorem 2.1 (Compression $\implies$ Learnability (David et al.,
2016)).

Let $(\kappa,\rho)$ be a sample compression scheme for
$\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ of size $k(n)$ and define
$f_{S}=\rho(\kappa(S))$ for any $S\in(\mathcal{X}\times\mathcal{Y})^{n}$.
Then, for every $\mathcal{D}$ on $\mathcal{X}\times\mathcal{Y}$ and
$n\in\mathbb{N}$ such that $k(n)\leq n/2$, with probability at least
$1-\delta$ over $S\in\mathcal{D}^{n}$, we have

$\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[\mathbbm{1}\\{f_{S}(x)\neq
y\\}]\leq\inf_{h\in\mathcal{H}}\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[\mathbbm{1}\\{h(x)\neq
y\\}]+100\sqrt{\frac{k(n)\log{\frac{n}{k(n)}}+k(n)+\log{\frac{1}{\delta}}}{n}}.$

###  2.3 Covering Numbers, Metric Entropy, and Complexity Measures

In Section 4, we provide conditions for which a hypothesis class $\mathcal{H}$
is online learnable under smoothed adversaries. While sufficient conditions
for learnability are typically established via combinatorial dimensions, our
sufficient conditions will be in terms of covering/packing numbers of
$\mathcal{H}$ using a distance metric that depends on the base measure $\mu$.
This discrepancy with existing literature is due to a simple observation: any
parameter of $\mathcal{H}$ alone cannot characterize smoothed online
classification. Indeed, if one takes the base measure $\mu$ to be a Dirac
measure, then every $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ is
trivially online learnable under a smoothed adversary. Accordingly, any
meaningful characterization of smoothed online classification must be in terms
of both $\mathcal{H}$ and $\mu$.

To start, we first define $\varepsilon$-covering numbers for generic metric
spaces $(\mathcal{G},d)$.

######  Definition 2 (Covering Number).

Let $(\mathcal{G},d)$ be a bounded metric space. A subset
$\mathcal{G}^{\prime}\subseteq\mathcal{G}$ is an $\varepsilon$-cover for
$\mathcal{G}$ with respect to $d$ if for every $g\in\mathcal{G}$, there exists
an $g^{\prime}\in\mathcal{G}^{\prime}$ such that
$d(g,g^{\prime})\leq\varepsilon$. The covering number of $\mathcal{G}$ at
scale $\varepsilon$, denoted $\mathcal{N}(\varepsilon,\mathcal{G},d)$, is the
smallest $n\in\mathbbm{N}$ such that there exists an $\varepsilon$-cover of
$\mathcal{G}$ with cardinality $n$. That is,
$\mathcal{N}(\varepsilon,\mathcal{G},d):=\inf\\{|\mathcal{G}^{\prime}|:\mathcal{G}^{\prime}\text{
is an }\varepsilon\text{-cover for }\mathcal{G}\\}.$

The metric entropy for $(\mathcal{G},d)$ at scale $\varepsilon>0$ is defined
as $\log\mathcal{N}(\varepsilon,\mathcal{G},d).$ In this paper, we consider
the metric space $(\mathcal{H},d_{\mu})$ where
$\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ is a hypothesis class and
$d_{\mu}(h_{1},h_{2})=\mathbb{P}_{x\sim\mu}\left[h_{1}(x)\neq h_{2}(x)\right]$
for some $\mu\in\Pi(\mathcal{X}).$ The key complexity measure in this work is

$C_{\varepsilon,\sigma}(\mathcal{H},\mu):=\sup_{n\in\mathbb{N}}\,\,\sup_{\nu_{1:n}\in\operatorname{B}(\mu,\sigma)}\,\,\operatorname*{\mathbb{E}}_{x_{1:n}\sim\nu_{1:n}}\left[\mathcal{N}(\varepsilon,\mathcal{H},d_{\hat{\mu}_{n}})\right],$

where $\hat{\mu}_{n}$ denotes the _empirical_ measure over $x_{1:n}.$ At a
high-level, $C_{\varepsilon,\sigma}(\mathcal{H},\mu)$ measures the complexity
of $\mathcal{H}$ in terms of its average empirical covering number, where the
average is taken over processes from $\operatorname{B}(\mu,\sigma)$. Using
$C_{\varepsilon,\sigma}(\mathcal{H},\mu)$, we define the property of uniformly
bounded empirical metric entropy.

######  Definition 3 (Uniformly Bounded Empirical Metric Entropy).

A hypothesis class $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ has the
Uniformly Bounded Empirical Metric Entropy _(UBEME)_ property with respect to
$\mu$ if $C_{\varepsilon,\sigma}(\mathcal{H},\mu)<\infty$ for every
$\varepsilon,\sigma>0$.

In Theorem 4.1, we show that $\mathcal{H}$ is online learnable under smoothed
adversaries if $\mathcal{H}$ enjoys the UBEME property with respect to the
base measure $\mu$.

##  3 PAC Learnability is Not Sufficient for Smoothed Online Learnability

In Section 4, we show that the PAC learnability of $\mathcal{H}$ is sufficient
for its smoothed online learnability when $|\mathcal{Y}|<\infty$. Here, we
show that this is not the case when $|\mathcal{Y}|$ is unbounded by
constructing a PAC learnable hypothesis class that is not smoothed online
learnable. In fact, we prove a _stronger_ result.

######  Theorem 3.1.

There exists a hypothesis class
$\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ such that following holds:

  * (i)

$\mathcal{H}$ has a compression scheme of size $1$.

  * (ii)

For $\mu=\text{Uniform}(\mathcal{X})$ and $\sigma=1$, we have
$\inf_{\mathcal{A}}\,\operatorname{R}^{\mu,\sigma}_{\mathcal{A}}(T,\mathcal{H})\geq\frac{T}{2}$.

The part (i) of Theorem 3.1, together with Theorem 2.1, shows that
$\mathcal{H}$ is agnostic PAC learnable with error rate
$\varepsilon(\delta,n)=O\left(\sqrt{\frac{\log{n}\,+\,\log(1/\delta)}{n}}\right)$.
On the other hand, based on Definition 1, part (ii) shows that $\mathcal{H}$
is not smoothed online learnable. Together, we infer the following corollary.

######  Corollary 3.2 (Agnostic PAC Learnability $\nRightarrow$ Smoothed
Online Learnability).

There exists $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ such that
$\mathcal{H}$ is agnostic PAC learnable but not learnable in the smoothed
setting under $\mu=\text{Uniform}(\mathcal{X})$ and $\sigma=1$.

When $|\mathcal{Y}|<\infty$, the existence of a $O(1)$-size compression
schemes and agnostic PAC learnability are equivalent (David et al., 2016).
Thus, there is no qualitative difference between Theorem 3.1 and Corollary
3.2. However, when $|\mathcal{Y}|=\infty$, a recent work has shown that the
multiclass PAC learnability does not imply the existence of $O(1)$-size
compression schemes (Pabbaraju, 2024). Thus, Theorem 3.1 is a qualitatively
stronger result than Corollary 3.2. Moreover, our proof of Theorem 3.1 below
provides an explicit PAC learner for $\mathcal{H}$.

###### Proof.

(of Theorem 3.1) Let $\mathcal{X}=[0,1]$. Given a bitstring
$\theta=(\theta_{1},\ldots,\theta_{n})\in\\{0,1\\}^{n}$, define $\theta_{\leq
t}:=(\theta_{1},\ldots,\theta_{t})$ and
$\theta_{<t}:=(\theta_{1},\ldots,\theta_{t-1})$ for any
$t\in\\{1,\ldots,n\\}$. Fix an $n\in\mathbb{N}$ and ordered sequence
$(x_{1},x_{2},\ldots,x_{n})\in\mathcal{X}^{n}$ such that $x_{i}\neq x_{j}$ for
all $i\neq j$. For every $\theta\in\\{0,1\\}^{n}$, define

$h_{(x_{1},\ldots,x_{n})}^{\theta}(x):=\begin{cases}((x_{1},\ldots,x_{n}),\theta_{\leq
t})\quad\text{ if }\exists t\in[n]\text{ such that }x=x_{t}\\\
((x_{1},\ldots,x_{n}),\star)\quad\quad\text{ otherwise }\par\end{cases}$

Let $O_{n}:=\\{(x_{1},x_{2},\ldots,x_{n})\in\mathcal{X}^{n}\,:\,x_{i}\neq
x_{j}\\}$ be the set of all ordered sequences of length $n$ with distinct
elements. Then, we define our hypothesis class to be

$\mathcal{H}:=\bigcup_{n\in\mathbb{N}}\,\,\bigcup_{(x_{1},\ldots,x_{n})\in
O_{n}}\,\,\bigcup_{\theta\in\\{0,1\\}^{n}}\left\\{h_{(x_{1},\ldots,x_{n})}^{\theta}\right\\}.$

Here, the label space is
$\mathcal{Y}:=\cup_{h\in\mathcal{H}}\\{\text{image}(h)\\}$. For any
$y\in\mathcal{Y}$, let us define $y[1]$ and $y[2]$ to be the first and the
second entry of the tuple $y$ respectively. Note that $y[1]\in O_{m}$ for some
$m\in\mathbb{N}$ and $y[2]\in\\{0,1\\}^{t}$ for some $t\leq m$.

Proof of (i). We now define a compression scheme $(\kappa,\rho)$ of size $1$
for $\mathcal{H}$.

  * •

Define a compression function $\kappa:\cup_{i\geq
1}(\mathcal{X}\times\mathcal{Y})^{i}\to\mathcal{X}\times\mathcal{Y}$ as
follows. Given any realizable sample
$S=\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\}$ of size $n\in\mathbb{N}$, the
function $\kappa$ outputs $\kappa(S)=\\{(x_{1},y_{1})\\}$ if $y_{i}[2]=\star$
for all $i\in[n]$. On the other hand, if there exists a $y_{i}$ such that
$y_{i}[2]\in\\{0,1\\}^{t}$ for some $t\in\mathbb{N}$, then
$\kappa(S)=\\{(x_{\ell},y_{\ell})\\}$. Here, $\ell\in[n]$ is the index such
that $y_{\ell}[2]$ is the longest binary string among all $i\in[n]$ for which
$y_{i}[2]\neq\star$.

  * •

Define a reconstruction function
$\rho:\mathcal{X}\times\mathcal{Y}\to\mathcal{H}$ as follows. Given an output
of the compression function $\\{(x,y)\\}$, the reconstruction function outputs
$\rho(\\{(x,y)\\})=h_{y[1]}^{\bf{0}}\in\mathcal{H}$ if $y[2]=\star$. Here,
$\mathbf{0}$ is all $0$’s bitstring of length equal to that of the tuple
$y[1]$. On the other hand, if $y[2]\in\\{0,1\\}^{t}$ for some $t\leq|y[1]|$,
then output $\rho(\\{(x,y)\\})=h_{y[1]}^{\theta}\in\mathcal{H}$, where
$\theta$ is an arbitrary bitstring of length $y[1]$ such that $\theta_{\leq
t}=y[2]$.

Next, we show that $(\kappa,\rho)$ is a valid compression scheme for
$\mathcal{H}$. Let
$S=\\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\\}\in(\mathcal{X}\times\mathcal{Y})^{n}$
denote any sample of size $n$ that is realizable by $\mathcal{H}$. We want to
show that $f=\rho(\kappa(S))$ satisfies $f(x_{i})=y_{i}$ for all $i\in[n]$.
Since $S$ is realizable by $\mathcal{H}$, there exists $m\in\mathbb{N}$,
$(z_{1},\ldots,z_{m})\in\mathcal{X}^{m}$ such that $z_{i}\neq z_{j}$ for all
$i,j\in[m]$ and $\beta\in\\{0,1\\}^{m}$ such that
$h_{(z_{1},\ldots,z_{m})}^{\beta}(x_{i})=y_{i}\quad\text{for all }i\in[n].$ By
definition of $\mathcal{H}$, for all $i\in[n]$, we have
$y_{i}[1]=(z_{1},\ldots,z_{m})$ and $y_{i}[2]$ $\in\\{\star,\beta_{\leq t}\\}$
for some $t\leq m$. Given a realizable sample $S$, there are two cases to
consider: (a) $y_{i}[2]=\star$ for all $i\in[n]$ and (b) there exists
$i\in[n]$ such that $y_{i}[2]\neq\star$.

If we are in case (a), then we know that $x_{i}\notin\\{z_{1},\ldots,z_{m}\\}$
for all $i\in[n]$. Moreover, we have $\kappa(S)=\\{(x_{1},y_{1})\\}$ where
$y_{1}[1]=(z_{1},\ldots,z_{m})$ and $y_{1}[2]=\star$. By definition of the
reconstruction function,
$\rho(\\{(x_{1},y_{1})\\})=h_{(z_{1},\ldots,z_{m})}^{\mathbf{0}}$. Since
$x_{i}\notin\\{z_{1},\ldots,z_{m}\\}$, by definition of
$h_{(z_{1},\ldots,z_{m})}^{\mathbf{0}}$, we have
$h_{(z_{1},\ldots,z_{m})}^{\mathbf{0}}(x_{i})=\big{(}(z_{1},\ldots,z_{m}),\star\big{)}=y_{i}$
for all $i\in[n]$. Thus, $(\kappa,\rho)$ is a valid compression scheme for
$\mathcal{H}$ in this case.

Suppose (b) is true. Define $I_{S}:=\\{i\in[n]:y_{i}[2]\neq\star\\}$. Since
$h_{(z_{1},\ldots,z_{m})}^{\beta}$ is consistent with the sample $S$, we must
have $y_{i}[2]=\beta_{\leq|y_{i}[2]|}$ for each $i\in I_{S}$. Here,
$|y_{i}[2]|$ is the length of bitstring $y_{i}[2]$. Let $\ell\in I_{S}$ such
that $|y_{\ell}[2]|\geq|y_{i}[2]|$ for all $i\in I_{S}$. By definition of the
compression function $\kappa$, we have $\kappa(S)=\\{(x_{\ell},y_{\ell})\\}$,
where $y_{\ell}[1]=(z_{1},\ldots,z_{m})$ and
$y_{\ell}[2]=\beta_{\leq|y_{\ell}[2]|}$. Let $\theta\in\\{0,1\\}^{m}$ be the
completion of $y_{\ell}[2]$ such that the reconstruction function returns
$\rho(\\{(x_{\ell},y_{\ell})\\})=h_{(z_{1},\ldots,z_{m})}^{\theta}$. By
definition of $\rho$, we have $\beta_{\leq t}=\theta_{\leq t}$ for
$t=|y_{\ell}[2]|$. To complete our proof, it suffices to show that
$h_{(z_{1},\ldots,z_{m})}^{\theta}(x_{i})=y_{i}$ for all $i\in[n]$. There are
two cases to consider: $i\in I_{S}$ and $i\notin I_{S}$. When $i\notin I_{S}$,
we have $x_{i}\notin\\{z_{1},\ldots,z_{m}\\}$ and thus
$h_{(z_{1},\ldots,z_{m})}^{\theta}(x_{i})=((z_{1},\ldots,z_{m}),\star)=y_{i}$.
As for the index $i\in I_{S}$, we must have that
$x_{i}\in\\{z_{1},\ldots,z_{m}\\}$. Otherwise, $y_{i}[2]$ would be equal to
$\star$, contradicting the fact that $i\in I_{S}$. In fact, by definition of
$h_{(z_{1},\ldots,z_{m})}^{\beta}$, we have $x_{i}=z_{|y_{i}[2]|}$. This
implies that, for all $i\in I_{S}$, we have
$h_{(z_{1},\ldots,z_{m})}^{\theta}(x_{i})=h_{(z_{1},\ldots,z_{m})}^{\theta}(z_{|y_{i}[2]|})=((z_{1},\ldots,z_{m}),\theta_{\leq|y_{i}[2]|})=((z_{1},\ldots,z_{m}),\beta_{\leq|y_{i}[2]|})=y_{i}.$
Here, we use that $|y_{i}[2]|\leq|y_{\ell}[2]|$ for all $i\in I_{S}$ and the
fact that $\theta_{\leq t}=\beta_{\leq t}$ for all $t\leq|y_{\ell}[2]|$.
Therefore, we have shown that $h_{(z_{1},\ldots,z_{m})}^{\theta}(x_{i})=y_{i}$
for all $i\in[n]$.

Proof of (ii). Let $\mu=\text{Uniform}([0,1])$. We now specify the stream
$\\{(x_{t},y_{t})\\}_{t=1}^{T}$ to be observed by the learner. For the
instances, we take $x_{1},\ldots,x_{T}\sim\mu$ to be iid samples from $\mu$.
Note that $x_{1},\ldots,x_{T}$ are distinct with probability $1$. Moreover, as
all the instances are drawn from the same distribution $\mu$, this adversary
is $\sigma$-smooth for $\sigma=1$. To specify $y_{1},\ldots,y_{T}$, we first
draw $\theta\sim\text{Uniform}(\\{0,1\\}^{T})$ and define
$y_{t}=((x_{1},\ldots,x_{T}),\theta_{\leq t})$ for all $t\in[T]$. Given
distinct $x_{1},\ldots,x_{T}$, for any algorithm $\mathcal{A}$, we first show
that

$\operatorname*{\mathbb{E}}_{\theta\sim\text{Uniform}(\\{0,1\\}^{T})}\left(\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\mathcal{A}}\,[\mathbbm{1}\\{\mathcal{A}(x_{t})\neq
y_{t}\\}]-\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\mathbbm{1}\\{h(x_{t})\neq
y_{t}\\}\right)\geq\frac{T}{2}.$ (1)

The probabilistic method implies the existence of a $\theta\in\\{0,1\\}^{T}$
such that the claimed bound of $T/2$ holds. This subsequently implies that,
for a distinct $x_{1},\ldots,x_{T}$, we have

$\sup_{y_{1:T}}\left(\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\mathcal{A}}\,[\mathbbm{1}\\{\mathcal{A}(x_{t})\neq
y_{t}\\}]-\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\mathbbm{1}\\{h(x_{t})\neq
y_{t}\\}\right)\geq\frac{T}{2}.$

Finally, using the fact that $x_{1},\ldots,x_{T}\sim\mu$ are distinct with
probability $1$, we obtain the bound

$\inf_{\mathcal{A}}\,\operatorname{R}^{\mu,\sigma}_{\mathcal{A}}(T,\mathcal{H})\geq\operatorname*{\mathbb{E}}_{x_{1},\ldots,x_{T}\sim\mu}\left[\sup_{y_{1:T}}\left(\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\mathcal{A}}\,[\mathbbm{1}\\{\mathcal{A}(x_{t})\neq
y_{t}\\}]-\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\mathbbm{1}\\{h(x_{t})\neq
y_{t}\\}\right)\right]\geq\frac{T}{2}.$

To complete our proof, it now suffices to prove Equation (1). Fixing distinct
$x_{1},\ldots,x_{T}$, the lowerbound on the expected cumulative loss of the
algorithm $\mathcal{A}$ is

$\begin{split}\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\theta\sim\text{Unif}(\\{0,1\\}^{T})}\left[\operatorname*{\mathbb{E}}_{\mathcal{A}}\,[\mathbbm{1}\\{\mathcal{A}(x_{t})\neq
y_{t}\\}]\right]&=\sum_{t=1}^{T}\operatorname*{\mathbb{E}}\left[\operatorname*{\mathbb{E}}_{\theta_{t}}\big{[}\,\mathbbm{1}\\{\mathcal{A}(x_{t})\neq((x_{1},\ldots,x_{T}),\theta_{\leq
t})\\}\big{]}\mid\mathcal{A},\theta_{<t}\right]\\\
&=\sum_{t=1}^{T}\operatorname*{\mathbb{E}}\left[\frac{1}{2}\mathbbm{1}\left\\{\mathcal{A}(x_{t})\neq\big{(}(x_{1:T}),(\theta_{<t},0)\big{)}\right\\}+\frac{1}{2}\mathbbm{1}\left\\{\mathcal{A}(x_{t})\neq\big{(}x_{1:T},(\theta_{<t},1)\big{)}\right\\}\right]\\\
&\geq\sum_{t=1}^{T}\frac{1}{2}=\frac{T}{2}.\end{split}$

At a high-level, we use the fact that $\theta_{t}$ is sampled uniformly at
random from $\\{0,1\\}$ and is independent of $\mathcal{A}$ as well as
$\theta_{i}$ for all $i\neq t$. Thus, on each round, the algorithm cannot do
any better than randomly guessing the value of $\theta_{t}$. Next, we
upperbound the expected loss of the best-fixed function in hindsight. Given
distinct $x_{1},\ldots,x_{T}$ and $\theta\in\\{0,1\\}^{T}$, we can pick the
hypothesis $h_{(x_{1},\ldots,x_{T})}^{\theta}$. By definition of this
hypothesis, we have
$h_{(x_{1},\ldots,x_{T})}^{\theta}(x_{t})=((x_{1},\ldots,x_{T}),\theta_{\leq
t})=y_{t}.$ Thus, for every distinct $x_{1},\ldots,x_{T}$, we have

$\operatorname*{\mathbb{E}}_{\theta\sim\text{Unif}(\\{0,1\\}^{T})}\left[\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\mathbbm{1}\\{h(x_{t})\neq
y_{t}\\}\right]\leq\operatorname*{\mathbb{E}}_{\theta\sim\text{Unif}(\\{0,1\\}^{T})}\left[\sum_{t=1}^{T}\mathbbm{1}\\{h_{(x_{1},\ldots,x_{T})}^{\theta}(x_{t})\neq
y_{t}\\}\right]=0.$

Finally, equation (1) follows upon combining the lowerbound on the cumulative
loss of $\mathcal{A}$ and the upperbound on the cumulative loss of the optimal
hypothesis in hindsight. ∎

To prove the qualitative separation between PAC and smoothed online
learnability in Theorem 3.1, we required $|\mathcal{Y}|$ to be unbounded. The
following theorem, proved in Appendix C, shows the quantitative dependence of
the regret on $|\mathcal{Y}|$ when it is bounded.

######  Theorem 3.3.

For every $K\in\mathbb{N}$, there exists
$\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ with $|\mathcal{Y}|=K$ such
that $\mathcal{H}$ has a compression scheme of $1$, but
$\inf_{\mathcal{A}}\,\operatorname{R}^{\mu,\sigma}_{\mathcal{A}}(T,\mathcal{H})\geq\frac{\log{K}}{24\log{\log{K}}}$
for $\mu=\text{Uniform}(\mathcal{X})$ and $\sigma=1$.

Theorem 3.3 shows that one can get quantitative separation whenever $K\geq
2^{T\log{T}}$.

##  4 A Sufficient Condition for Smoothed Online Classification

In this section, we provide a sufficient condition for smoothed online
classification. Our main result provides a quantitative upperbound on the
expected regret in terms of $C_{\varepsilon,\sigma}(\mathcal{H},\mu)$.

######  Theorem 4.1.

For every $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$,
$\mu\in\Pi(\mathcal{X})$ and $\sigma>0$, we have that

$\inf_{\mathcal{A}}\,\operatorname{R}^{\mu,\sigma}_{\mathcal{A}}(T,\mathcal{H})\leq
6\inf_{\varepsilon>0}\Biggl{\\{}\frac{\varepsilon
T}{\sigma}+\sqrt{T\log(C_{\varepsilon^{2},\sigma}(\mathcal{H},\mu))}\Biggl{\\}}.$

Theorem 4.1 shows that as long as $\mathcal{H}$ satisfies the UBEME condition
with respect to $\mu$, it is online learnable under a smoothed adversary. As a
corollary, we also establish the following sufficient condition in terms of
the Graph dimension, a combinatorial dimension characterizing PAC learnability
when $|\mathcal{Y}|<\infty$ (see Appendix A for a complete definition)
(Natarajan, 1989).

######  Corollary 4.2.

For every $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$,
$\mu\in\Pi(\mathcal{X})$ and $\sigma>0$, we have that

$\inf_{\mathcal{A}}\,\operatorname{R}^{\mu,\sigma}_{\mathcal{A}}(T,\mathcal{H})\leq
6\inf_{\varepsilon>0}\Biggl{\\{}\frac{\varepsilon
T}{\sigma}+\sqrt{T\,\operatorname{G}(\mathcal{H})\,\log\Bigl{(}\frac{41|\mathcal{Y}|}{\varepsilon^{2}}\Bigl{)}}\Biggl{\\}}\leq
12\sqrt{T\,\operatorname{G}(\mathcal{H})\,\log\Bigl{(}\frac{41\,T\,|\mathcal{Y}|}{\sigma^{2}}\Bigl{)}},$

where $\operatorname{G}(\mathcal{H})$ denotes the Graph dimension of
$\mathcal{H}$.

Corollary 4.2, whose proof is in Appendix E, shows that PAC learnability of
$\mathcal{H}$ is sufficient for smoothed online classification whenever
$|\mathcal{Y}|<\infty$. When $|\mathcal{Y}|=2$, this bounds, up to a constant
factor, recovers that from Haghtalab (2018). We now proceed with the proof of
Theorem 4.1.

###### Proof.

(of Theorem 4.1) Let $\nu_{1},\ldots,\nu_{T}\in\,\operatorname{B}(\mu,\sigma)$
denote the sequence of $\sigma$-smooth distributions picked by the adversary.
Fix a $\varepsilon>0$. Then, by Lemma B.2, we have that
$\mathcal{N}(\varepsilon,\mathcal{H},d_{\mu})\leq
C_{\frac{\varepsilon}{2},\sigma}(\mathcal{H},\mu)$. Let
$\mathcal{H}^{\prime}\subset\mathcal{H}$ denote an $\varepsilon$-cover with
respect to $d_{\mu}$ of size at most
$C_{\frac{\varepsilon}{2},\sigma}(\mathcal{H},\mu)$. Let $\mathcal{A}$ denote
the online learner that runs the Randomized Exponential Weights Algorithm
(REWA) on the the data stream $(x_{1},y_{1}),...,(x_{T},y_{T})$ using
$\mathcal{H}^{\prime}$ as its set of experts. By the guarantees of REWA,

$\displaystyle\operatorname*{\mathbb{E}}_{\mathcal{A}}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{A}(x_{t})\neq
y_{t}\\}\right]$
$\displaystyle\leq\inf_{h^{\prime}\in\mathcal{H}^{\prime}}\sum_{t=1}^{T}\mathbbm{1}\\{h^{\prime}(x_{t})\neq
y_{t}\\}+\sqrt{2T\,\log(|\mathcal{H}^{\prime}|)}$
$\displaystyle\leq\inf_{h^{\prime}\in\mathcal{H}^{\prime}}\sum_{t=1}^{T}\mathbbm{1}\\{h^{\prime}(x_{t})\neq
y_{t}\\}+\sqrt{2T\,\log(C_{\frac{\varepsilon}{2},\sigma}(\mathcal{H},\mu))}$
$\displaystyle\leq\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\mathbbm{1}\\{h(x_{t})\neq
y_{t}\\}+\sup_{h\in\mathcal{H}}\inf_{h^{\prime}\in\mathcal{H}^{\prime}}\sum_{t=1}^{T}\mathbbm{1}\\{h^{\prime}(x_{t})\neq
h(x_{t})\\}+\sqrt{2T\,\log(C_{\frac{\varepsilon}{2},\sigma}(\mathcal{H},\mu))}$

where the expectation is only taken with respect to the randomness of the REWA
and the last inequality follows by the triangle inequality. Taking an outer
expectation with respect to the process $x_{1:T}\sim\nu_{1:T},$ we have
$\mathbb{E}\Big{[}\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{A}(x_{t})\neq
y_{t}\\}\Big{]}$ is at most

$\begin{split}\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\mathbbm{1}\\{h(x_{t})\neq
y_{t}\\}\right]+\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\sup_{h\in\mathcal{H}}\inf_{h^{\prime}\in\mathcal{H}^{\prime}}\sum_{t=1}^{T}\mathbbm{1}\\{h^{\prime}(x_{t})\neq
h(x_{t})\\}\right]+\sqrt{2T\,\log(C_{\frac{\varepsilon}{2},\sigma}(\mathcal{H},\mu))}.\end{split}$

It remains to bound
$\mathbb{E}\left[\sup_{h\in\mathcal{H}}\inf_{h^{\prime}\in\mathcal{H}^{\prime}}\sum_{t=1}^{T}\mathbbm{1}\\{h^{\prime}(x_{t})\neq
h(x_{t})\\}\right]$. We provide a sketch of the proof here and defer the full
details to Appendix D. Consider the class
$\mathcal{G}=\\{x\mapsto\mathbbm{1}\\{h^{\prime}(x)\neq
h(x)\\}:h\in\mathcal{H}\\}$, where $h^{\prime}\in\mathcal{H}^{\prime}$ denotes
the $\varepsilon$-cover of $h$ with respect to $d_{\mu}$, and note that

$\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\sup_{h\in\mathcal{H}}\inf_{h^{\prime}\in\mathcal{H}^{\prime}}\sum_{t=1}^{T}\mathbbm{1}\\{h^{\prime}(x_{t})\neq
h(x_{t})\\}\right]\leq\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\sup_{g\in\mathcal{G}}\sum_{t=1}^{T}g(x_{t})\right].$

By standard symmetrization arguments, we get

$\displaystyle\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\sup_{g\in\mathcal{G}}\sum_{t=1}^{T}g(x_{t})\right]$
$\displaystyle\leq\sup_{g\in\mathcal{G}}\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\sum_{t=1}^{T}g(x^{\prime}_{t})\right]+2T\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\hat{\mathfrak{R}}(\mathcal{G},x_{1:T})\right]$

where $\hat{\mathfrak{R}}(\mathcal{G},x_{1:T})$ is the Rademacher complexity
of $\mathcal{G}$ (see Appendix A). Note that
$\mathcal{G}\subseteq\mathcal{H}\Delta\mathcal{H}$ where
$\mathcal{H}\Delta\mathcal{H}:=\\{x\mapsto\mathbbm{1}\\{h_{1}(x)\neq
h_{2}(x)\\}:h_{1},h_{2}\in\mathcal{H}\\}$, and thus
$\hat{\mathfrak{R}}(\mathcal{G},x_{1:T})\leq\hat{\mathfrak{R}}(\mathcal{H}\Delta\mathcal{H},x_{1:T})$.
Using the discretization-based upperbound (Lemma A.1) on the empirical
Rademacher complexity and a relation between the covering numbers of
$\mathcal{H}$ and $\mathcal{H}\Delta\mathcal{H}$ (Lemma B.3), we have

$\hat{\mathfrak{R}}(\mathcal{H}\Delta\mathcal{H},x_{1:T})\leq\varepsilon+\sqrt{\frac{2\log\mathcal{N}(\varepsilon,\mathcal{H}\Delta\mathcal{H},\rho_{\mu_{T}})}{T}}\leq\varepsilon+\sqrt{\frac{2\log\mathcal{N}(\varepsilon^{2},\mathcal{H}\Delta\mathcal{H},d_{\mu_{T}})}{T}}\leq\varepsilon+2\sqrt{\frac{\log\mathcal{N}(\frac{\varepsilon^{2}}{2},\mathcal{H},d_{\mu_{T}})}{T}}.$

Plugging in the upperbound on the Rademacher complexity and using the change
of measure, $\sigma$-smoothness, and the definition of $\mathcal{H}^{\prime}$
on the first term gives

$\displaystyle\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\sup_{g\in\mathcal{G}}\sum_{t=1}^{T}g(x_{t})\right]\leq\frac{\varepsilon
T}{\sigma}+2\varepsilon\,T+4\sqrt{T\,\log\left(\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\mathcal{N}\left(\frac{\varepsilon^{2}}{2},\mathcal{H},d_{\mu_{T}}\right)\right]\right)}.$

Using the definition of $C_{\varepsilon,\sigma}(\mathcal{H},\mu)$ to get

$\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\sup_{h\in\mathcal{H}}\inf_{h\in\mathcal{H}^{\prime}}\sum_{t=1}^{T}\mathbbm{1}\\{h^{\prime}(x_{t})\neq
h(x_{t})\\}\right]\leq\frac{\varepsilon
T}{\sigma}+2\varepsilon\,T+4\sqrt{T\,\log
C_{\frac{\varepsilon^{2}}{2},\sigma}(\mathcal{H},\mu)},$

substituting into the regret bound for $\mathcal{A}$, and doing some algebra
completes the proof sketch. ∎

Our upperbounds in terms of expected empirical covering numbers can be
meaningful even when VC and Graph dimension of $\mathcal{H}$ is infinity. As a
simple example, let $\mathcal{X}=[0,1]$, $\mu=\text{Uniform}(\mathcal{X})$,
and consider the binary hypothesis class
$\mathcal{H}=\\{x\mapsto\mathbbm{1}\\{x\in
A\\}:A\subset\mathbb{Q},|A|<\infty\\}$. It’s not too hard to see that
$\operatorname{VC}(\mathcal{H})=\infty$. On the other hand,
$C_{\varepsilon,\sigma}(\mathcal{H},\mu)=1$ since for every $n\in\mathbb{N}$,
the sample $x_{1:n}\sim\mu$ does not lie in $\mathbb{Q}$ almost surely, and
when $x_{1:n}\notin\mathbb{Q}$, $d_{\hat{\mu}_{n}}(h_{1},h_{2})=0$ for all
$h_{1},h_{2}\in\mathcal{H}.$

To prove Theorem 4.1, we show that the UBEME implies a bound on the metric
entropy $\mathcal{N}(\varepsilon,\mathcal{H},d_{\mu}).$ It is natural ask
whether the finiteness of $\mathcal{N}(\varepsilon,\mathcal{H},d_{\mu})$ for
every $\varepsilon>0$ alone is necessary and sufficient for smoothed online
learnability. Unfortunately, it is neither sufficient nor necessary.

######  Theorem 4.3.

Let $\mathcal{X}=[0,1]$ and $\mu=\operatorname{Uniform}(\mathcal{X})$. Then,

  * (i)

There exists a $\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$ such that
$\mathcal{N}(\varepsilon,\mathcal{H},d_{\mu})=1$ for every $\varepsilon>0$ but
$\operatorname{R}_{\mathcal{A}}^{\mu,\sigma}(T,\mathcal{H})\geq\frac{T}{2}$
for every $\sigma>0.$

  * (ii)

There exists $\mathcal{H}\subseteq\mathbb{N}^{\mathcal{X}}$ such that
$\mathcal{N}(\varepsilon,\mathcal{H},d_{\mu})=\infty$ for every
$\varepsilon>0$ but
$\inf_{\mathcal{A}}\operatorname{R}_{\mathcal{A}}^{\mu,\sigma}(T,\mathcal{H})=O(\sqrt{T\log(T)})$
for every $\sigma>0.$

###### Proof.

We first prove (i). Consider the hypothesis class
$\mathcal{H}=\\{x\mapsto\mathbbm{1}\\{x\in
S\\}:S\subset\mathcal{X},|S|<\infty\\}$. Note that for every
$h_{1},h_{2}\in\mathcal{H}$, we have that
$d_{\mu}(h_{1},h_{2})=\mathbb{P}_{x\sim\mu}\left[h_{1}(x)\neq
h_{2}(x)\right]=0$ since $h_{1}$ and $h_{2}$ disagree on at most a finite
number of points in $\mathcal{X}$. Thus, for every $\varepsilon>0$,
$\mathcal{H}$ is trivially coverable using exactly one hypothesis in
$\mathcal{H}$. To show that
$\operatorname{R}_{\mathcal{A}}^{\mu,\sigma}(T,\mathcal{H})\geq\frac{T}{2}$
for every $\sigma>0$, consider the adversary that picks $\nu_{t}=\mu$ for all
$t\in[T]$. The process $x_{1:T}\sim\nu_{1:T}$ is then an iid draw from $\mu$
of length $T$. Consider the data stream $(x_{1},y_{1}),...,(x_{T},y_{T})$
where $x_{1:T}\sim\mu^{T}$ and $y_{t}\sim\text{Unif}(\\{0,1\\})$ for every
$t\in[T]$. Such a stream is realizable by $\mathcal{H}$ almost surely since
the the sequence of instances $x_{1:T}$ are all distinct with probability $1$
and there can be at most a finite number of timepoints where $y_{t}=1$. On the
other hand, any learning algorithm $\mathcal{A}$ must make at least $T/2$
mistakes in expectation (with respect to all sources of randomness), since the
labels $y_{t}\sim\text{Unif}(\\{0,1\\})$. Thus, by the probabilistic method,
for every learning algorithm $\mathcal{A}$, there must exist a sequence of
labels $y_{1:T}$, such that $\mathcal{A}$’s expected regret is $T/2$.

We now prove (ii). Let $\mathcal{H}=\\{x\mapsto a:a\in\mathbb{N}\\}$ be the
class of constant functions. Note that for every $h_{1},h_{2}\in\mathcal{H}$,
we have that $d_{\mu}(h_{1},h_{2})=1$ since $h_{1}$ and $h_{2}$ disagree
everywhere on $\mathcal{X}$. Thus, for every $\varepsilon<1$, we have that
$\mathcal{N}(\varepsilon,\mathcal{H},d_{\mu})=\infty$ since
$|\mathcal{H}|=\infty.$ On the other hand, the Littlestone dimension of
$\mathcal{H}$ is $1$. Thus, by Theorem 4 from Hanneke et al. (2023), we get
that
$\inf_{\mathcal{A}}\operatorname{R}_{\mathcal{A}}^{\mu,\sigma}(T,\mathcal{H})=O(\sqrt{T\log
T})$ for every $\sigma>0.$ ∎

##  5 Discussion

In this work, we show a separation between the learnability of
$\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ in the PAC setting and the
smoothed online setting when $|\mathcal{Y}|$ is unbounded. We also provide a
sufficient condition for smoothed online learnability under any base measure
$\mu$. However, as noted in Section 4, our sufficient condition is not
necessary for the smoothed learnability of $\mathcal{H}$. Thus, an important
open question is to find a condition that is both necessary and sufficient for
smoothed online learnability. Traditionally, in learning theory, learnability
is characterized in terms of a combinatorial property of just the hypothesis
class $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$. However, the property
of $\mathcal{H}$ alone cannot provide a characterization of learnability in
the smoothed online setting. Choosing $\mu$ to be a Dirac distribution will
make any $\mathcal{H}$, even the set of all measurable functions from
$\mathcal{X}$ to $\mathcal{Y}$, trivially learnable. Thus, the
characterization of learnability must necessarily be a property of the tuple
$(\mathcal{H},\mu)$. To that end, we pose the following question.

Given $(\mathcal{H},\mu)$, is there a complexity measure that characterizes
the smoothed online learnability of $\mathcal{H}$ with base measure $\mu$?

## References

  * Alon et al. [1997] Noga Alon, Shai Ben-David, Nicolo Cesa-Bianchi, and David Haussler.  Scale-sensitive dimensions, uniform convergence, and learnability.  _Journal of the ACM (JACM)_ , 44(4):615–631, 1997.
  * Anthony and Bartlett [1999] Martin Anthony and Peter L. Bartlett.  _Neural Network Learning: Theoretical Foundations_.  Cambridge University Press, 1999.  doi: 10.1017/CBO9780511624216.
  * Bartlett and Mendelson [2002] Peter L Bartlett and Shahar Mendelson.  Rademacher and gaussian complexities: Risk bounds and structural results.  _Journal of Machine Learning Research_ , 3(Nov):463–482, 2002.
  * Bartlett et al. [1996] 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.
  * Ben-David et al. [2009] Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz.  Agnostic online learning.  In _Conference on Learning Theory_ , volume 3, page 1, 2009.
  * Block et al. [2022] Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin.  Smoothed online learning is as easy as statistical learning.  In _Conference on Learning Theory_ , pages 1716–1786. PMLR, 2022.
  * Brukhim et al. [2022] Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff.  A characterization of multiclass learnability.  In _2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 943–955. IEEE, 2022.
  * Daniely et al. [2011] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz.  Multiclass learnability and the erm principle.  In _Conference on Learning Theory_ , volume 19, pages 207–232. PMLR, 2011.
  * David et al. [2016] Ofir David, Shay Moran, and Amir Yehudayoff.  On statistical learning via the lens of compression.  In _Proceedings of the 30th International Conference on Neural Information Processing Systems_ , pages 2792–2800, 2016.
  * Haghtalab [2018] Nika Haghtalab.  _Foundation of Machine Learning, by the People, for the People_.  PhD thesis, Carnegie Mellon University, 2018.
  * Haghtalab et al. [2020] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty.  Smoothed analysis of online and differentially private learning.  _Advances in Neural Information Processing Systems_ , 33:9203–9215, 2020.
  * Hanneke et al. [2023] Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, and Ambuj Tewari.  Multiclass online learning and uniform convergence.  _Conference on Learning Theory_ , 2023.
  * Hanneke et al. [2024] Steve Hanneke, Shay Moran, and Jonathan Shafer.  A trichotomy for transductive online learning.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Haussler [1995] David Haussler.  Sphere packing numbers for subsets of the boolean n-cube with bounded vapnik-chervonenkis dimension.  _Journal of Combinatorial Theory, Series A_ , 69(2):217–232, 1995.
  * Littlestone [1987] Nick Littlestone.  Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.  _Machine Learning_ , 2:285–318, 1987.
  * Natarajan [1989] B. K. Natarajan.  On learning sets and functions.  _Machine Learning_ , 4(1):67–97, 1989.
  * Pabbaraju [2024] Chirag Pabbaraju.  Multiclass learnability does not imply sample compression.  In _Proceedings of The 35th International Conference on Algorithmic Learning Theory_ , 2024.
  * Rakhlin et al. [2011] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Online learning: Stochastic, constrained, and smoothed adversaries.  _Advances in neural information processing systems_ , 24, 2011.
  * Shalev-Shwartz and Ben-David [2014] Shai Shalev-Shwartz and Shai Ben-David.  _Understanding Machine Learning: From Theory to Algorithms_.  Cambridge University Press, USA, 2014.
  * Spielman and Teng [2004] Daniel A Spielman and Shang-Hua Teng.  Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time.  _Journal of the ACM (JACM)_ , 51(3):385–463, 2004.
  * Valiant [1984] Leslie G. Valiant.  A theory of the learnable.  In _Symposium on the Theory of Computing_ , 1984.
  * Vapnik and Chervonenkis [1971] Vladimir Naumovich Vapnik and Aleksei Yakovlevich Chervonenkis.  On uniform convergence of the frequencies of events to their probabilities.  _Teoriya Veroyatnostei i ee Primeneniya_ , 16(2):264–279, 1971.
  * Wu et al. [2023] Changlong Wu, Mohsen Heidari, Ananth Grama, and Wojciech Szpankowski.  Expected worst case regret via stochastic sequential covering.  _Transactions on Machine Learning Research_ , 2023.

##  Appendix A PAC Learnability, Combinatorial Dimensions, Complexity Measures

We begin by defining the agnostic PAC framework, a canonical learning model in
the batch setting.

######  Definition 4 (Agnostic PAC Learnability).

A hypothesis class $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ is agnostic
PAC learnable if there exists a function $m:(0,1)^{2}\to\mathbb{N}$ and a
learning algorithm $\mathcal{A}:\cup_{i\geq
1}(\mathcal{X}\times\mathcal{Y})^{i}\to\mathcal{Y}^{\mathcal{X}}$ with the
following property: for every $\varepsilon,\delta\in(0,1)$ and for every
distribution $\mathcal{D}$ on $\mathcal{X}\times\mathcal{Y}$, $\mathcal{A}$
running on $n\geq m(\varepsilon,\delta)$ i.i.d. samples from $\mathcal{D}$
outputs a predictor $\mathcal{A}_{S}$ such that with probability at least
$1-\delta$ over $S\sim\mathcal{D}^{n}$,

$\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\,\left[\mathbbm{1}\\{\mathcal{A}_{S}(x)\neq
y\\}\right]\leq\inf_{h\in\mathcal{H}}\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\,[\mathbbm{1}\\{h(x)\neq
y\\}]+\varepsilon.$

The VC and Graph dimension characterize PAC learnability when
$|\mathcal{Y}|=2$ and $|\mathcal{Y}|<\infty$ respectively.

######  Definition 5 (Vapnik-Chervonenkis (VC) Dimension).

A set $S=\\{x_{1},\ldots,x_{d}\\}\subset\mathcal{X}$ is shattered by a binary
function class $\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$ if for every
$\tau\in\\{0,1\\}^{d}$, there exists a hypothesis $h_{\tau}\in\mathcal{H}$
such that for all $i\in[d]$, we have $h_{\tau}(x_{i})=\tau_{i}$. The VC
dimension of $\mathcal{H}$, denoted $\operatorname{VC}(\mathcal{H})$, is the
size of the largest shattered set $S\subseteq\mathcal{X}$. If $\mathcal{H}$
can shatter arbitrarily large sets, we say that
$\operatorname{VC}(\mathcal{H})=\infty$.

######  Definition 6 (Graph Dimension).

For any multiclass hypothesis class
$\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$, let
$\ell\circ\mathcal{H}:=\\{(x,y)\mapsto\mathbbm{1}\\{h(x)\neq
y\\}:h\in\mathcal{H}\\}\subseteq\\{0,1\\}^{(\mathcal{X}\times\mathcal{Y})}$
denotes its loss class. The Graph dimension of $\mathcal{H}$ is defined as
$\operatorname{G}(\mathcal{H}):=\operatorname{VC}(\ell\circ\mathcal{H}).$

Our proof of this result relies on bounding the Rademacher complexity, a
canonical complexity measure used to establish generalization bounds in the
batch setting [Bartlett and Mendelson, 2002].

######  Definition 7 (Empirical Rademacher Complexity).

Let $\mathcal{F}\subseteq\mathbb{R}^{\mathcal{X}}$ and
$x_{1},...,x_{n}\in\mathcal{X}^{n}$. The empirical Rademacher complexity of
$\mathcal{F}$ with respect to $x_{1:n}$ is defined as

$\hat{\mathfrak{R}}(\mathcal{\mathcal{F}},x_{1:n})=\frac{1}{n}\operatorname*{\mathbb{E}}_{\tau}\left[\sup_{f\in\mathcal{F}}\left(\sum_{i=1}^{n}\tau_{i}f(x_{i})\right)\right]$

where $\tau_{1},...,\tau_{n}$ are independent _Rademacher_ random variables.

The following upperbound on the empirical Rademacher complexity follows by a
simple application of Massart’s lemma [Shalev-Shwartz and Ben-David, 2014,
Lemma 28.6].

######  Lemma A.1 (Discretization Bound).

For every $\mathcal{F}\subseteq\mathbbm{R}^{\mathcal{X}}$ and
$x_{1},...,x_{n}\in\mathcal{X}^{n}$, we have that

$\hat{\mathfrak{R}}(\mathcal{\mathcal{F}},x_{1:n})\leq\inf_{\varepsilon>0}\Bigg{\\{}\varepsilon+\Biggl{(}\sup_{f\in\mathcal{F}}\sqrt{\operatorname*{\mathbb{E}}_{\hat{\mu}_{n}}\left[f^{2}\right]}\Biggl{)}\sqrt{\frac{2\log\mathcal{N}(\varepsilon,\mathcal{F},\rho_{\hat{\mu}_{n}})}{n}}\Bigg{\\}}$

where $\hat{\mu}_{n}$ denotes the empirical measure on the sample $x_{1:n}$
and $\rho_{\mu}$ is the distance metric defined as

$\rho_{\hat{\mu}_{n}}(f_{1},f_{2}):=\sqrt{\operatorname*{\mathbb{E}}_{x\sim\hat{\mu}_{n}}\left[(f_{1}(x)-f_{2}(x))^{2}\right]}.$

Finally, we define the packing number for generic metric spaces.

######  Definition 8 (Packing Number).

Let $(\mathcal{G},d)$ be a bounded metric space. A subset
$\mathcal{G}^{\prime}\subseteq\mathcal{G}$ is an $\varepsilon$-packing with
respect to $d$ if for every $g_{i},g_{j}\in\mathcal{G}^{\prime}$ we have that
$d(g_{i},g_{j})>\varepsilon$. The packing number of $\mathcal{G}$ at scale
$\varepsilon$, denoted $\mathcal{M}(\varepsilon,\mathcal{G},d)$, is the
largest $n\in\mathbbm{N}$ such that there exists an $\varepsilon$-packing of
$\mathcal{G}$ with cardinality $n$. That is,
$\mathcal{M}(\varepsilon,\mathcal{G},d):=\sup\\{|\mathcal{G}^{\prime}|:\mathcal{G}^{\prime}\text{
is an }\varepsilon\text{-packing for }\mathcal{G}\\}.$

##  Appendix B Helper Lemmas

######  Lemma B.1 (Covering-Packing duality [Anthony and Bartlett, 1999]).

For any metric space $(\mathcal{G},d)$ and $\varepsilon>0$, we have that

$\mathcal{M}(2\varepsilon,\mathcal{G},d)\leq\mathcal{N}(\varepsilon,\mathcal{G},d)\leq\mathcal{M}(\varepsilon,\mathcal{G},d).$

Using the Covering-Packing duality, we prove the following technical Lemma.

######  Lemma B.2 (UBEME $\implies$ Bounded Metric Entropy with respect to
$\mu$).

For any $\mu\in\Pi(\mathcal{X})$, hypothesis class
$\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$, and $\varepsilon>0$, we have
that

$\mathcal{N}(\varepsilon,\mathcal{H},d_{\mu})\leq\sup_{m\in\mathbb{N}}\operatorname*{\mathbb{E}}_{x_{1:m}\sim\mu^{m}}\left[\mathcal{N}\left(\frac{\varepsilon}{2},\mathcal{H},d_{\hat{\mu}_{m}}\right)\right].$

###### Proof.

Fix $\varepsilon>0$. By the Covering-Packing duality, we have that

$\sup_{m\in\mathbb{N}}\operatorname*{\mathbb{E}}_{x_{1:m}\sim\mu^{m}}\left[\mathcal{M}(\varepsilon,\mathcal{H},d_{\hat{\mu}_{m}})\right]\leq\sup_{m\in\mathbb{N}}\operatorname*{\mathbb{E}}_{x_{1:m}\sim\mu^{m}}\left[\mathcal{N}\left(\frac{\varepsilon}{2},\mathcal{H},d_{\hat{\mu}_{m}}\right)\right].$

Thus, it suffices to show that
$\mathcal{N}(\varepsilon,\mathcal{H},d_{\mu})\leq\sup_{m\in\mathbb{N}}\mathbb{E}_{x_{1:m}\sim\mu^{m}}\left[\mathcal{M}(\varepsilon,\mathcal{H},d_{\hat{\mu}_{m}})\right]$.
Suppose, for the sake of contradiction, we have that
$\mathcal{N}(\varepsilon,\mathcal{H},d_{\mu})>\sup_{m\in\mathbb{N}}\mathbb{E}_{x_{1:m}\sim\mu^{m}}\left[\mathcal{M}(\varepsilon,\mathcal{H},d_{\hat{\mu}_{m}})\right]$.
Then by the Covering-Packing duality, we have that
$\mathcal{M}(\varepsilon,\mathcal{H},d_{\mu})>\sup_{m\in\mathbb{N}}\mathbb{E}_{x_{1:m}\sim\mu^{m}}\left[\mathcal{M}(\varepsilon,\mathcal{H},d_{\hat{\mu}_{m}})\right]=:c.$
By the definition of $\varepsilon$-packing, we can find $n>c$ hypothesis
$h_{1},...,h_{n}\in\mathcal{H}$ and $\delta>0$ such that
$d_{\mu}(h_{i},h_{j})>\varepsilon+\delta$ for every $i\neq j$.

Fix $m\in\mathbbm{N}$ and consider a sample $x_{1:m}\sim\mu^{m}$. Let
$S_{ij}=\sum_{t=1}^{m}\mathbbm{1}\\{h_{i}(x_{t})\neq h_{j}(x_{t})\\}$ denote
the random variable counting the number of samples on which $h_{i}$ and
$h_{j}$ differ. Note that $S_{ij}\sim\text{Binom}(m,d_{\mu}(h_{i},h_{j})).$
Let $E_{m}$ be the event that $S_{ij}>\varepsilon\,m\text{ for all }i<j$.
Then,

$\displaystyle\mathbb{P}_{x_{1:m}\sim\mu^{m}}\Bigl{[}E_{m}\Bigl{]}$
$\displaystyle=1-\mathbb{P}_{x_{1:m}\sim\mu^{m}}\Bigl{[}\exists i<j\text{ such
that }S_{ij}\leq\varepsilon\,m\Bigl{]}$ $\displaystyle\geq
1-\sum_{i<j}\mathbb{P}_{x_{1:m}\sim\mu^{m}}\Bigl{[}S_{ij}\leq\varepsilon\,m\Bigl{]}$
$\displaystyle\geq
1-\sum_{i<j}\exp\left\\{-2m\left(d_{\mu}(h_{i},h_{j})-\varepsilon\right)^{2}\right\\}$
$\displaystyle\geq 1-\sum_{i<j}\exp\\{-2m\,\delta^{2}\\}$ $\displaystyle\geq
1-n^{2}\exp\\{-2m\,\delta^{2}\\},$

where the second inequality follows by Hoeffding’s inequality. Moreover, under
event $E_{m}$, we have that
$\mathcal{M}(\varepsilon,\mathcal{H},d_{\hat{\mu}_{m}})\geq n$, where
$d_{\hat{\mu}_{m}}$ is the empirical measure on $x_{1:m}$. Finally, note that

$\displaystyle\sup_{m\in\mathbb{N}}\operatorname*{\mathbb{E}}_{x_{1:m}\sim\mu^{m}}\left[\mathcal{M}(\varepsilon,\mathcal{H},d_{\hat{\mu}_{m}})\right]$
$\displaystyle\geq\sup_{m\in\mathbb{N}}\operatorname*{\mathbb{E}}_{x_{1:m}\sim\mu^{m}}\left[\mathcal{M}(\varepsilon,\mathcal{H},d_{\hat{\mu}_{m}})|E_{m}\right]\mathbb{P}_{x_{1:m}\sim\mu^{m}}\Bigl{[}E_{m}\Bigl{]}$
$\displaystyle\geq
n\sup_{m\in\mathbb{N}}\mathbb{P}_{x_{1:m}\sim\mu^{m}}\Bigl{[}E_{m}\Bigl{]}$
$\displaystyle\geq
n\sup_{m\in\mathbb{N}}\Bigl{(}1-n^{2}\exp\\{-2m\,\delta^{2}\\}\Bigl{)}$
$\displaystyle=n.$

Since $n>c$ and
$c=\sup_{m\in\mathbbm{N}}\operatorname*{\mathbb{E}}_{x_{1:m}\sim\mu^{m}}\left[\mathcal{M}(\varepsilon,\mathcal{H},d_{\hat{\mu}_{m}})\right]$,
we arrive at a contradiction. ∎

######  Lemma B.3 (Covering Number of Symmetric Differences).

For any $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$, $\varepsilon>0$, and
sequence $x_{1},...,x_{n}\in\mathcal{X}^{n}$, we have that

$\mathcal{N}(\varepsilon,\mathcal{H}\Delta\mathcal{H},\hat{\mu}_{n})\leq\Bigl{(}\mathcal{N}\left(\frac{\varepsilon}{2},\mathcal{H},\hat{\mu}_{n}\right)\Bigl{)}^{2}$

where $\hat{\mu}_{n}$ is the empirical measure on $x_{1:n}$ and
$\mathcal{H}\Delta\mathcal{H}:=\Bigl{\\{}x\mapsto\mathbbm{1}\\{h_{1}(x)\neq
h_{2}(x)\\}:h_{1},h_{2}\in\mathcal{H}\Bigl{\\}}.$

###### Proof.

Fix $\varepsilon>0.$ Let $\mathcal{H}^{\prime}$ be an $\varepsilon$-cover for
$\mathcal{H}$ with respect to $d_{\hat{\mu}_{n}}$. It suffices to show that
$\mathcal{H}^{\prime}\Delta\mathcal{H}^{\prime}$ is an $2\varepsilon$-cover
for $\mathcal{H}\Delta\mathcal{H}$ with respect to $d_{\hat{\mu}_{n}}$. To see
this, pick a $g\in\mathcal{H}\Delta\mathcal{H}$. Then by definition, we can
decompose $g(x)=\mathbbm{1}\\{h_{1}(x)\neq h_{2}(x)\\}$ for some
$h_{1},h_{2}\in\mathcal{H}$. Let
$h_{1}^{\prime},h_{2}^{\prime}\in\mathcal{H}^{\prime}$ be the elements that
cover $h_{1},h_{2}$ respectively. Then, observe that we have

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbbm{1}\\{\mathbbm{1}\\{h_{1}^{\prime}(x_{i})\neq
h_{2}^{\prime}(x_{i})\\}\neq\mathbbm{1}\\{h_{1}(x_{i})\neq h_{2}(x_{i})\\}\\}$
$\displaystyle\leq\frac{1}{n}\Bigl{(}\sum_{i=1}^{n}\mathbbm{1}\\{h_{1}(x_{i})\neq
h_{1}^{\prime}(x_{i})\\}+\sum_{i=1}^{n}\mathbbm{1}\\{h_{2}(x_{i})\neq
h_{2}^{\prime}(x_{i})\\}\Bigl{)}$ $\displaystyle\leq 2\varepsilon.$

Thus, $x\mapsto\mathbbm{1}\\{h_{1}^{\prime}(x)\neq h_{2}^{\prime}(x)\\}$ is
$2\varepsilon$-close to $x\mapsto\mathbbm{1}\\{h_{1}(x)\neq h_{2}(x_{i})\\}$.
Since $x\mapsto\mathbbm{1}\\{h_{1}^{\prime}(x)\neq
h_{2}^{\prime}(x)\\}\in\mathcal{H}^{\prime}\Delta\mathcal{H}^{\prime}$ and
$h_{1},h_{2}\in\mathcal{H}$ were chosen arbitrarily, it follows that
$\mathcal{H}^{\prime}\Delta\mathcal{H}^{\prime}$ is a $2\varepsilon$-cover for
$\mathcal{H}\Delta\mathcal{H}$ with respect to $d_{\hat{\mu}_{n}}$. Finally,
note that
$|\mathcal{H}^{\prime}\Delta\mathcal{H}^{\prime}|\leq|\mathcal{H}^{\prime}|^{2}.$
Since $\varepsilon>0$ is arbitrary, this completes the proof. ∎

##  Appendix C Proof of Theorem 3.3

_The proof here is similar to the proof of Theorem 3.1. Thus, we only provide
a high-level sketch of the arguments here. _

###### Proof.

Fix $m\in\mathbb{N}$, and take $\mathcal{X}=\\{1,2,\ldots,m^{2}\\}$. For every
ordered sequence $(x_{1},x_{2},\ldots,x_{m})\in\mathcal{X}^{m}$ such that
$x_{i}\neq x_{j}$ for all $i\neq j$ and a bitstring $\theta\in\\{0,1\\}^{m}$,
define a hypothesis

$h_{(x_{1},\ldots,x_{m})}^{\theta}(x):=\begin{cases}((x_{1},\ldots,x_{m}),\theta_{\leq
t})\quad\text{ if }\exists t\in[m]\text{ such that }x=x_{t}\\\
((x_{1},\ldots,x_{m}),\star)\quad\quad\text{ otherwise }\par\end{cases}$

Let $O_{m}:=\\{(x_{1},x_{2},\ldots,x_{m})\in\mathcal{X}^{m}\,:\,x_{i}\neq
x_{j}\\}$ be the set of all ordered sequences of length $m$ with distinct
elements. Then, we define our hypothesis class to be

$\mathcal{H}:=\bigcup_{(x_{1},\ldots,x_{m})\in
O_{m}}\,\,\bigcup_{\theta\in\\{0,1\\}^{m}}\left\\{h_{(x_{1},\ldots,x_{m})}^{\theta}\right\\}.$

Here, the label space is
$\mathcal{Y}:=\cup_{h\in\mathcal{H}}\\{\text{image}(h)\\}$. Thus, the size of
the label space is

$|\mathcal{Y}|=\binom{m^{2}}{m}\,\,m!\,\,2^{m}=\frac{m^{2}!}{(m^{2}-m)!}2^{m}=m^{2}(m^{2}-1)\ldots(m^{2}-(m-1))\,2^{m}\leq(m^{2})^{m}2^{m}\leq
m^{3m},$

when $m\geq 2$. This implies that

$m\geq\frac{1}{3}\frac{\log{|\mathcal{Y}|}}{\log{\log{|\mathcal{Y}|}}}.$

Note that the Proof of (i) in Theorem 3.1 can be used verbatim to show that
$\mathcal{H}$ has a compression scheme of size $1$. Thus, $\mathcal{H}$ is PAC
learnable with error rate
$O\left(\sqrt{\frac{\log{n}\,+\,\log(1/\delta)}{n}}\right)$.

Therefore, we now focus on establishing regret lowerbound for $\mathcal{H}$.
Let $\mu=\text{Uniform}(\\{1,2,\ldots,m^{2}\\})$. Let $m\leq T$. We now
specify the stream $\\{(x_{t},y_{t})\\}_{t=1}^{T}$ to be observed by the
learner. For the instances, we take $x_{1},\ldots,x_{m}\sim\mu$ to be iid
samples from $\mu$. Note that $x_{1},\ldots,x_{m}$ are distinct with
probability

$\geq\left(1-\frac{m}{m^{2}}\right)^{m}=\left(1-\frac{1}{m}\right)^{m}\geq\frac{1}{4}\quad\quad\forall
m\geq 2.$

Moreover, as all the instances are drawn from the same distribution $\mu$,
this adversary is $\sigma$-smooth for $\sigma=1$. To specify
$y_{1},\ldots,y_{m}$, we first draw $\theta\sim\text{Uniform}(\\{0,1\\}^{m})$
and define $y_{t}=((x_{1},\ldots,x_{m}),\theta_{\leq t})$ for all $t\in[m]$.
Conditioned on the fact that $x_{1},\ldots,x_{m}$ are distinct, there will be
a hypothesis class $h_{\theta}^{*}\in\mathcal{H}$ such that
$h_{\theta}^{*}(x_{t})=y_{t}$ for all $t\in[m]$. For $m\leq t\leq T$, sample
$x_{t}\sim\mu$ and define $y_{t}=h_{\theta}^{*}(x_{t})$. Note that for _any_
$x_{1},\ldots,x_{m}$, we have

$\begin{split}\operatorname*{\mathbb{E}}_{\theta\sim\text{Uniform}(\\{0,1\\}^{m})}\Bigg{[}\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\mathcal{A}}\,[\mathbbm{1}\\{\mathcal{A}(x_{t})\neq
y_{t}\\}]\Bigg{]}\geq\operatorname*{\mathbb{E}}_{\theta\sim\text{Uniform}(\\{0,1\\}^{m})}\Bigg{[}\sum_{t=1}^{m}\operatorname*{\mathbb{E}}_{\mathcal{A}}\,[\mathbbm{1}\\{\mathcal{A}(x_{t})\neq
y_{t}\\}]\Bigg{]}\geq\frac{m}{2}.\end{split}$

Here, we use the fact that bitstrings $\theta_{t}$ are sampled uniformly
randomly, so no algorithm can do better than randomly guessing. Moreover,
conditioned on the event that $x_{1},\ldots,x_{m}$ are distinct, we have

$\operatorname*{\mathbb{E}}_{\theta\sim\text{Uniform}(\\{0,1\\}^{m})}\left[\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\mathbbm{1}\\{h(x_{t})\neq
y_{t}\\}\right]\leq\operatorname*{\mathbb{E}}_{\theta\sim\text{Uniform}(\\{0,1\\}^{m})}\left[\sum_{t=1}^{T}\mathbbm{1}\\{h_{\theta}^{*}(x_{t})\neq
y_{t}\\}\right]=0.$

Since $x_{1},\ldots,x_{m}$ are distinct with probability at least $1/8$, we
obtain

$\inf_{\mathcal{A}}\,\operatorname{R}^{\mu,\sigma}_{\mathcal{A}}(T,\mathcal{H})\geq\frac{m}{8}\geq\frac{1}{24}\,\frac{\log{|\mathcal{Y}|}}{\log{\log{|\mathcal{Y}|}}}.$

∎

##  Appendix D Proof of Theorem 4.1

###### Proof.

Let $\nu_{1},\ldots,\nu_{T}\in\,\operatorname{B}(\mu,\sigma)$ denote the
sequence of $\sigma$-smooth distributions picked by the adversary. Fix a
$\varepsilon>0$. Then, by Lemma B.2, we have that
$\mathcal{N}(\varepsilon,\mathcal{H},d_{\mu})\leq
C_{\frac{\varepsilon}{2},\sigma}(\mathcal{H},\mu)$. Let
$\mathcal{H}^{\prime}\subset\mathcal{H}$ denote an $\varepsilon$-cover with
respect to $d_{\mu}$ of size at most
$C_{\frac{\varepsilon}{2},\sigma}(\mathcal{H},\mu)$. Let $\mathcal{A}$ denote
the online learner that runs the Randomized Exponential Weights Algorithm
(REWA) on the data stream $(x_{1},y_{1}),...,(x_{T},y_{T})$ using
$\mathcal{H}^{\prime}$ as its set of experts. By the guarantees of REWA,

$\displaystyle\operatorname*{\mathbb{E}}_{\mathcal{A}}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{A}(x_{t})\neq
y_{t}\\}\right]$
$\displaystyle\leq\inf_{h^{\prime}\in\mathcal{H}^{\prime}}\sum_{t=1}^{T}\mathbbm{1}\\{h^{\prime}(x_{t})\neq
y_{t}\\}+\sqrt{2T\,\log(|\mathcal{H}^{\prime}|)}$
$\displaystyle\leq\inf_{h^{\prime}\in\mathcal{H}^{\prime}}\sum_{t=1}^{T}\mathbbm{1}\\{h^{\prime}(x_{t})\neq
y_{t}\\}+\sqrt{2T\,\log(C_{\frac{\varepsilon}{2},\sigma}(\mathcal{H},\mu))}$
$\displaystyle\leq\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\mathbbm{1}\\{h(x_{t})\neq
y_{t}\\}+\sup_{h\in\mathcal{H}}\inf_{h^{\prime}\in\mathcal{H}^{\prime}}\sum_{t=1}^{T}\mathbbm{1}\\{h^{\prime}(x_{t})\neq
h(x_{t})\\}+\sqrt{2T\,\log(C_{\frac{\varepsilon}{2},\sigma}(\mathcal{H},\mu))}$

where the expectation is only taken with respect to the randomness of the MWA
and the last inequality follows by the triangle inequality. Taking an outer
expectation with respect to the process $x_{1:T}\sim\nu_{1:T}$, we get that

$\begin{split}\mathbb{E}\Big{[}\sum_{t=1}^{T}&\mathbbm{1}\\{\mathcal{A}(x_{t})\neq
y_{t}\\}\Big{]}\\\
&\leq\mathbb{E}\left[\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\mathbbm{1}\\{h(x_{t})\neq
y_{t}\\}\right]+\mathbb{E}\left[\sup_{h\in\mathcal{H}}\inf_{h^{\prime}\in\mathcal{H}^{\prime}}\sum_{t=1}^{T}\mathbbm{1}\\{h^{\prime}(x_{t})\neq
h(x_{t})\\}\right]+\sqrt{2T\,\log(C_{\frac{\varepsilon}{2},\sigma}(\mathcal{H},\mu))}.\end{split}$

It remains to bound
$\mathbb{E}\left[\sup_{h\in\mathcal{H}}\inf_{h^{\prime}\in\mathcal{H}^{\prime}}\sum_{t=1}^{T}\mathbbm{1}\\{h^{\prime}(x_{t})\neq
h(x_{t})\\}\right]$. To do so, consider the class
$\mathcal{G}=\\{x\mapsto\mathbbm{1}\\{h^{\prime}(x)\neq
h(x)\\}:h\in\mathcal{H}\\}$, where $h^{\prime}\in\mathcal{H}^{\prime}$ denotes
the $\varepsilon$-cover with respect to $d_{\mu}$ of $h$, and note that

$\mathbb{E}\left[\sup_{h\in\mathcal{H}}\inf_{h^{\prime}\in\mathcal{H}^{\prime}}\sum_{t=1}^{T}\mathbbm{1}\\{h^{\prime}(x_{t})\neq
h(x_{t})\\}\right]\leq\mathbb{E}\left[\sup_{g\in\mathcal{G}}\sum_{t=1}^{T}g(x_{t})\right].$

By standard symmetrization arguments, we get that

$\displaystyle\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\sup_{g\in\mathcal{G}}\Biggl{(}\sum_{t=1}^{T}g(x_{t})-\mathbbm{E}_{x^{\prime}_{1:T}\sim\nu_{1:T}}\left[\sum_{t=1}^{T}g(x^{\prime}_{t})\right]\Biggl{)}\right]$
$\displaystyle\leq\operatorname*{\mathbb{E}}_{x_{1:T},x^{\prime}_{1:T}\sim\nu_{1:T}}\left[\sup_{g\in\mathcal{G}}\sum_{t=1}^{T}\Bigl{(}g(x_{t})-g(x^{\prime}_{t})\Bigl{)}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{x_{1:T},x^{\prime}_{1:T}\sim\nu_{1:T}}\left[\mathbbm{E}_{\theta_{1:T}}\left[\sup_{g\in\mathcal{G}}\sum_{t=1}^{T}\theta_{t}\Bigl{(}g(x_{t})-g(x^{\prime}_{t})\Bigl{)}\right]\right]$
$\displaystyle\leq
2\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\operatorname*{\mathbb{E}}_{\theta_{1:T}}\left[\sup_{g\in\mathcal{G}}\sum_{t=1}^{T}\theta_{t}\,g(x_{t})\right]\right]$
$\displaystyle\leq
2T\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\hat{\mathfrak{R}}(\mathcal{G},x_{1:T})\right]$

where $\theta_{1:T}$ are independent Rademacher random variables. Note that
$\mathcal{G}\subseteq\mathcal{H}\Delta\mathcal{H}$ where
$\mathcal{H}\Delta\mathcal{H}:=\\{x\mapsto\mathbbm{1}\\{h_{1}(x)\neq
h_{2}(x)\\}:h_{1},h_{2}\in\mathcal{H}\\}$, and thus
$\hat{\mathfrak{R}}(\mathcal{G},x_{1:T})\leq\hat{\mathfrak{R}}(\mathcal{H}\Delta\mathcal{H},x_{1:T})$.
Using Lemma A.1 we can pointwise upperbound

$\hat{\mathfrak{R}}(\mathcal{H}\Delta\mathcal{H},x_{1:T})\leq\varepsilon+\sqrt{\frac{2\log\mathcal{N}(\varepsilon,\mathcal{H}\Delta\mathcal{H},\rho_{\mu_{T}})}{T}}\leq\varepsilon+\sqrt{\frac{2\log\mathcal{N}(\varepsilon^{2},\mathcal{H}\Delta\mathcal{H},d_{\mu_{T}})}{T}}\leq\varepsilon+2\sqrt{\frac{\log\mathcal{N}(\frac{\varepsilon^{2}}{2},\mathcal{H},d_{\mu_{T}})}{T}}.$

The first inequality follows by taking
$\rho_{\mu_{T}}(g_{1},g_{2})=\sqrt{\frac{1}{T}\sum_{t=1}^{T}\mathbbm{1}\\{g_{1}(x_{t})\neq
g_{2}(x_{t})\\}}$ for any two functions
$g_{1},g_{2}\in\mathcal{H}\Delta\mathcal{H}$. The second inequality follows
from the fact that
$\mathcal{N}(\varepsilon,\mathcal{H}\Delta\mathcal{H},\rho_{\mu_{T}})\leq\mathcal{N}(\varepsilon^{2},\mathcal{H}\Delta\mathcal{H},d_{\mu_{T}}).$
The last inequality follows after using Lemma B.3. Plugging in the upperbound
on the Rademacher complexity, we get that

$\displaystyle\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\sup_{g\in\mathcal{G}}\sum_{t=1}^{T}g(x_{t})\right]$
$\displaystyle\leq\sup_{g\in\mathcal{G}}\operatorname*{\mathbb{E}}_{x^{\prime}_{1:T}\sim\nu_{1:T}}\left[\sum_{t=1}^{T}g(x^{\prime}_{t})\right]+2\varepsilon\,T+4\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\sqrt{T\,\log\mathcal{N}\left(\frac{\varepsilon^{2}}{2},\mathcal{H},d_{\mu_{T}}\right)}\right]$
$\displaystyle\leq\sup_{g\in\mathcal{G}}\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{x^{\prime}_{t}\sim\nu_{t}}\left[g(x^{\prime}_{t})\right]+2\varepsilon\,T+4\sqrt{T\,\log\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\mathcal{N}\left(\frac{\varepsilon^{2}}{2},\mathcal{H},d_{\mu_{T}}\right)\right]}$
$\displaystyle\leq\sup_{g\in\mathcal{G}}\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{x^{\prime}_{t}\sim\mu}\left[\frac{g(x^{\prime}_{t})}{\sigma}\right]+2\varepsilon\,T+4\sqrt{T\,\log\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\mathcal{N}\left(\frac{\varepsilon^{2}}{2},\mathcal{H},d_{\mu_{T}}\right)\right]}$
$\displaystyle\leq\frac{\varepsilon
T}{\sigma}+2\varepsilon\,T+4\sqrt{T\,\log\operatorname*{\mathbb{E}}_{x_{1:T}\sim\nu_{1:T}}\left[\mathcal{N}\left(\frac{\varepsilon^{2}}{2},\mathcal{H},d_{\mu_{T}}\right)\right]},$

where the third and fourth inequality follow by change of measure,
$\sigma$-smoothness, and the definition $\mathcal{H}^{\prime}$ respectively.
By the definition of $C_{\varepsilon,\sigma}(\mathcal{H},\mu)$, we get that

$\mathbb{E}\left[\sup_{h\in\mathcal{H}}\inf_{h\in\mathcal{H}^{\prime}}\sum_{t=1}^{T}\mathbbm{1}\\{h^{\prime}(x_{t})\neq
h(x_{t})\\}\right]\leq\frac{\varepsilon
T}{\sigma}+2\varepsilon\,T+4\sqrt{T\,\log
C_{\frac{\varepsilon^{2}}{2},\sigma}(\mathcal{H},\mu)},$

implying that

$\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}\mathbbm{1}\\{\mathcal{A}(x_{t})\neq
y_{t}\\}\right]$
$\displaystyle\leq\mathbb{E}\left[\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\mathbbm{1}\\{h(x_{t})\neq
y_{t}\\}\right]+\frac{\varepsilon T}{\sigma}+2\varepsilon\,T+4\sqrt{T\,\log
C_{\frac{\varepsilon^{2}}{2},\sigma}(\mathcal{H},\mu)}+\sqrt{2T\,\log
C_{\frac{\varepsilon}{2},\sigma}(\mathcal{H},\mu)}$
$\displaystyle\leq\mathbb{E}\left[\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}\mathbbm{1}\\{h(x_{t})\neq
y_{t}\\}\right]+\frac{3\varepsilon T}{\sigma}+6\sqrt{T\,\log
C_{\frac{\varepsilon^{2}}{2},\sigma}(\mathcal{H},\mu)}.$

Since $\nu_{1},\ldots,\nu_{T}\in\,\operatorname{B}(\mu,\sigma)$ and
$\varepsilon>0$ were chosen arbitrarily, we have that

$\operatorname{R}^{\mu,\sigma}_{\mathcal{A}}(T,\mathcal{H})\leq\inf_{\varepsilon>0}\left\\{\frac{3\varepsilon
T}{\sigma}+6\sqrt{T\,\log
C_{\frac{\varepsilon^{2}}{2},\sigma}(\mathcal{H},\mu)}\right\\}\leq
6\inf_{\varepsilon>0}\left\\{\frac{\varepsilon T}{\sigma}+\sqrt{T\,\log
C_{\varepsilon^{2},\sigma}(\mathcal{H},\mu)}\right\\}.$

∎

##  Appendix E Proof of Corollary 4.2

The following lemma from Haghtalab [2018], which uses the seminal packing
lemma by Haussler [1995], will be useful.

######  Lemma E.1 (Haussler [1995], Haghtalab [2018]).

For any $\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$ and
$\mu\in\Pi(\mathcal{X})$, we have that

$\mathcal{N}(\varepsilon,\mathcal{H},d_{\mu})\leq\Bigl{(}\frac{41}{\varepsilon}\Bigl{)}^{\operatorname{VC}(\mathcal{H})}.$

Lemma E.1 together with Definition 6 implies that for any multiclass
hypothesis class $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$, we have that

$\sup_{\tilde{\mu}\in\Pi(\mathcal{X}\times\mathcal{Y})}\mathcal{N}(\varepsilon,\ell\circ\mathcal{H},d_{\tilde{\mu}})\leq\Bigl{(}\frac{41}{\varepsilon}\Bigl{)}^{\operatorname{G}(\mathcal{H})},$

where $\ell\circ\mathcal{H}:=\\{(x,y)\mapsto\mathbbm{1}\\{h(x)\neq
y\\}:h\in\mathcal{H}\\}\subseteq\\{0,1\\}^{(\mathcal{X}\times\mathcal{Y})}$
denotes the loss class of $\mathcal{H}$. We now begin the proof of Corollary
4.2.

###### Proof.

(of Corollary 4.2) It suffices to show that

$C_{\varepsilon,\sigma}(\mathcal{H},\mu)\leq\sup_{\tilde{\mu}\in\Pi(\mathcal{X}\times\mathcal{Y})}\mathcal{N}\left(\frac{2\varepsilon}{|\mathcal{Y}|},\ell\circ\mathcal{H},d_{\tilde{\mu}}\right),$

for every $\varepsilon,\sigma>0.$ Fix $\varepsilon,\sigma>0$. Recall that

$C_{\varepsilon,\sigma}(\mathcal{H},\mu):=\sup_{n\in\mathbbm{N}}\sup_{\nu_{1:n}\in\operatorname{B}(\mu,\sigma)}\operatorname*{\mathbb{E}}_{x_{1:n}\sim\nu_{1:n}}\left[\mathcal{N}(\varepsilon,\mathcal{H},d_{\hat{\mu}_{n}})\right],$

where $\hat{\mu}_{n}$ denotes the empirical measure over $x_{1:n}.$ We will
actually show something stronger, that is

$\sup_{n\in\mathbbm{N}}\sup_{x_{1:n}\in\mathcal{X}^{n}}\mathcal{N}(\varepsilon,\mathcal{H},d_{\hat{\mu}_{n}})\leq\sup_{\tilde{\mu}\in\Pi(\mathcal{X}\times\mathcal{Y})}\mathcal{N}\left(\frac{2\varepsilon}{|\mathcal{Y}|},\ell\circ\mathcal{H},d_{\tilde{\mu}}\right).$
(2)

Fix $n\in\mathbb{N}$ and let
$c:=\sup_{\tilde{\mu}\in\Pi(\mathcal{X}\times\mathcal{Y})}\mathcal{N}(\frac{2\varepsilon}{|\mathcal{Y}|},\ell\circ\mathcal{H},d_{\tilde{\mu}})$.
To see why Inequality (2) is true, consider a sequence
$x_{1:n}\in\mathcal{X}^{n}$ and let $\hat{\mu}_{n}$ denote the empirical
measure on $x_{1:n}$. Let
$\tilde{\mu}_{n}\in\Pi(\mathcal{X}\times\mathcal{Y})$ be the joint measure
over $\mathcal{X}\times\mathcal{Y}$ defined procedurally by first sampling
$x\in\hat{\mu}_{n}$ and then sampling the label
$y\sim\operatorname{Uniform}(\mathcal{Y}).$ Since
$\tilde{\mu}_{n}\in\Pi(\mathcal{X}\times\mathcal{Y})$, by definition of $c$,
there exists a subset $\mathcal{H}^{\prime}\subseteq\mathcal{H}$ of size at
most $c$ such that $\ell\circ\mathcal{H}^{\prime}$ is an
$\frac{2\varepsilon}{|\mathcal{Y}|}$-cover for $\ell\circ\mathcal{H}$ with
respect to $\tilde{\mu}_{n}.$ It suffices to show that $\mathcal{H}^{\prime}$
is an $\varepsilon$-cover for $\mathcal{H}$ with respect to $\hat{\mu}_{n}.$
Fix a $h\in\mathcal{H}$ and let $h^{\prime}$ be the element in
$\mathcal{H}^{\prime}$ such that $d_{\tilde{\mu}_{n}}(\ell\circ h,\ell\circ
h^{\prime})\leq\frac{2\varepsilon}{|\mathcal{Y}|}.$ Then, by definition, we
have that

$\displaystyle\frac{2\varepsilon}{|\mathcal{Y}|}$ $\displaystyle\geq
d_{\tilde{\mu}_{n}}(\ell\circ h,\ell\circ h^{\prime})$
$\displaystyle=\operatorname*{\mathbb{E}}_{(x,y)\sim\tilde{\mu}_{n}}\left[\mathbbm{1}\\{\ell\circ
h(x,y)\neq\ell\circ h^{\prime}(x,y)\\}\right]$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{|\mathcal{Y}|}\sum_{j=1}^{|\mathcal{Y}|}\mathbbm{1}\\{\mathbbm{1}\\{h(x_{i})\neq
j\\}\neq\mathbbm{1}\\{h^{\prime}(x_{i})\neq j\\}\\}$
$\displaystyle=\frac{2}{n|\mathcal{Y}|}\sum_{i=1}^{n}\mathbbm{1}\\{h(x_{i})\neq
h^{\prime}(x_{i})\\}$
$\displaystyle=\frac{2}{|\mathcal{Y}|}d_{\hat{\mu}_{n}}(h,h^{\prime}).$

Therefore $h^{\prime}$ is $\varepsilon$-close to $h$ with respect to
$d_{\hat{\mu}_{n}}$. Since $h$ was chosen arbitrarily, this is true for all
$h\in\mathcal{H}$. Accordingly, $\mathcal{H}^{\prime}$ is an
$\varepsilon$-cover for $\mathcal{H}$ with respect to $d_{\hat{\mu}_{n}},$
implying that $\mathcal{N}(\varepsilon,\mathcal{H},d_{\hat{\mu}_{n}})\leq c$.
Since $n$ and $x_{1:n}$ was also chosen arbitrarily, we have that
$\sup_{n\in\mathbbm{N}}\sup_{x_{1:n}\in\mathcal{X}^{n}}\mathcal{N}(\varepsilon,\mathcal{H},d_{\hat{\mu}_{n}})\leq
c,$ completing the proof.

Finally, upperbound $6\inf_{\varepsilon>0}\Biggl{\\{}\frac{\varepsilon
T}{\sigma}+\sqrt{T\,\operatorname{G}(\mathcal{H})\,\log\Bigl{(}\frac{41|\mathcal{Y}|}{\varepsilon^{2}}\Bigl{)}}\Biggl{\\}}\leq
12\sqrt{T\,\operatorname{G}(\mathcal{H})\,\log\Bigl{(}\frac{41\,T\,|\mathcal{Y}|}{\sigma^{2}}\Bigl{)}}$
follows by picking $\varepsilon=\frac{\sigma}{\sqrt{T}}.$ ∎