# Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries††thanks:
An extended abstract of this work was published under the title “Oracle-
efficient Online Learning for Smoothed Adversaries” in the Proceedings of the
$36$th Conference on Neural Information Processing Systems [HHSY22]

Nika Haghtalab  University of California, Berkeley
<EMAIL_ADDRESS>Yanjun Han  University of
California, Berkeley
<EMAIL_ADDRESS>Abhishek Shetty  University of
California, Berkeley
<EMAIL_ADDRESS>Kunhe Yang  University of
California, Berkeley
<EMAIL_ADDRESS>
###### Abstract

In this paper, we study oracle-efficient algorithms for beyond worst-case
analysis of online learning. We focus on two settings. First, the smoothed
analysis setting of [RST11, HRS22] where an adversary is constrained to
generating samples from distributions whose density is upper bounded by
$1/\sigma$ times the uniform density. Second, the setting of $K$-hint
transductive learning, where the learner is given access to $K$ hints per time
step that are guaranteed to include the true instance. We give the first known
oracle-efficient algorithms for both settings that depend only on the pseudo
(or VC) dimension of the class and parameters $\sigma$ and $K$ that capture
the power of the adversary. In particular, we achieve oracle-efficient regret
bounds of $\widetilde{O}(\sqrt{Td\sigma^{-1}})$ and
$\widetilde{O}(\sqrt{TdK})$ for learning real-valued functions and
$O(\sqrt{Td\sigma^{-\frac{1}{2}}})$ for learning binary-valued functions. For
the smoothed analysis setting, our results give the first oracle-efficient
algorithm for online learning with smoothed adversaries [HRS22]. This
contrasts the computational separation between online learning with worst-case
adversaries and offline learning established by [HK16]. Our algorithms also
achieve improved bounds for worst-case setting with small domains. In
particular, we give an oracle-efficient algorithm with regret of
$O(\sqrt{T(d\mathinner{\\!\left\lvert\mathcal{X}\right\rvert})^{1/2}})$, which
is a refinement of the earlier
$O(\sqrt{T\mathinner{\\!\left\lvert\mathcal{X}\right\rvert}})$ bound by
[DS16].

##  1 Introduction

Adversarial online learning is a cornerstone of modern machine learning and
has led to significant advances in computer science broadly. A recent line of
work on “beyond the worst-case analysis” of online learning has brought into
light the overly pessimistic nature of standard characterizations of online
learnability [RST11, GR17, HRS20, HRS22]. This is exemplified by the results
of [HRS22] showing that adversarial online learnability is _statistically_ as
easy as PAC learnability, in presence of noise. That is, under _smoothed
analysis_ , online and offline learnability are both characterized by the
finiteness of the VC dimension of a hypothesis class as opposed to the much
larger Littlestone dimension that characterizes online learnability in the
worst-case [BDPSS09]. However, to fully deliver on the promise revealed by
these statistical insights, there needs to be an algorithmic framework for
realizing this connection between online and offline learnability. In this
paper, we ask

> _whether efficient offline learning algorithms lead to efficient online
> learning algorithms with comparable regret guarantees, when the adversary is
> not worst-case, such as under the smoothed analysis framework?_

##### Online Learning beyond the Worst-Case.

Smoothed analysis is a perspective on algorithm design, introduced by [ST04]
and formalized for online learning by [RSS12, HRS20], in which the adversary
is restricted to generating an instance at every round from a distribution
that is not overly concentrated, i.e., a distribution whose density is upper
bounded by $1/\sigma$ times that of the uniform distribution111 While we use
the uniform distribution as the base measure for ease of exposition, our
results also generalize to arbitrary known base measures.. The smoothness of
the adversary’s actions captures the noise and imprecision inherent in the
real world. A related perspective is that of _transductive_ learning that
constrains the adversary to producing its sequence from a known set of $T$
unlabeled instances. We work with a generalization of the transductive
learning framework, which we call _transductive learning with $K$ hints_, that
constrains the adversary to forming a $T$-long sequence from a known unordered
set of size $KT$. As $K$ and $1/\sigma$ decrease, so does the uncertainty of
the learner about the future instances or their distributions. These models
gracefully capture the expressivity of worst-case instances while
circumventing the overly pessimistic nature of the worst-case analysis.

##### Computation and Efficiency.

The question of whether offline learning algorithms can lead to online
learning algorithms is naturally captured by the _oracle-efficiency_ framework
(e.g., [DHL+20, KV05, HK16]). In this setting, we have access to an offline
learning algorithm or equivalently an _empirical risk minimization (ERM)_
oracle which can compute an optimal hypothesis given any history of the
actions of the adversary, using $O(1)$ computation. Efficient algorithms must
then be designed to tap into the existing ERM oracle, using polynomial number
of calls and computation.

Our main goal is to design oracle-efficient online algorithms whose regret
bounds resemble the statistically optimal regret bounds as much as possible.
In particular, under smoothed analysis and $K$-hint transductive learning,
these bounds must be characterized by offline statistical complexity measures,
such as the VC dimension or pseudo dimension of a hypothesis class.
Interestingly, [HK16] showed that such computationally algorithms cannot exist
for fully worst-case adversaries. Therefore, designing oracle-efficient online
algorithms for adversaries who are not fully worst-case, must _simultaneously
overcome both statistical and computational impossibilities._ This is what we
achieve by the main contributions of this paper.

###  1.1 Main Results

| Problem Class | Regret Bound | Method | Reference
---|---|---|---|---
Statistical Upper Bound |  Smoothed Online Learning | Binary | $\widetilde{O}\left(\sqrt{dT\ln(\sigma^{-1})}\right)$ |  $\epsilon$-Net and prob. coupling | [HRS22, Thm 3.1]
Real-values | $\widetilde{O}\left(\sqrt{dT\ln(\sigma^{-1})}\right)$ |  Thm G.1
$K$-hint Transductive Learning | Real/Binary | $\widetilde{O}\left(\sqrt{dT\ln(K)}\right)$ |  $\epsilon$-Net and property of hints |  Thm G.3
Conputational Upper Bound |  Smoothed Online Learning | Binary | $\widetilde{O}\left(\sqrt{dT\sigma^{-1/2}}\right)$ |  Poissonized FTPL (1 oracle call /round) |  Thm 4.2
Real/Binary | $\widetilde{O}\left(\sqrt{dT\sigma^{-1}}\right)$ |  Relax-and-Randomize (2 oracle calls/round) |  Thm 4.1
$K$-hint Transductive Learning | Real/Binary | $\widetilde{O}\left(\sqrt{dTK}\right)$ |  Thm 3.1
Conputational Lower Bound |  Smoothed Online Learning | Alg-independent | $\Omega\left(\sqrt{T(d/\sigma)^{1/2}}\right)$ |  Construction for runtime $o(\sqrt{d/\sigma})$ |  Thm 5.2
Algorithm (1,2) | $\Omega\left(\sqrt{dT\sigma^{-1/2}}\right)$ |  | Thm 5.1
$K$-hint Transductive Learning |  Algorithm (3) | $\Omega\left(\sqrt{dTK^{1/2}}\right)$
Classical settings | Small-domain | $O\left(\sqrt{T(d\mathinner{\\!\left\lvert\mathcal{X}\right\rvert})^{1/2}}\right)$ | Poissonized FTPL | Cor 4.3
Transductive learning | $O\left(T^{3/4}d^{1/4}\right)$
Table 1: This table summarized the main results of this paper for smoothed and
transductive adversaries. Here, $d$ represents the pseudo-dimension or VC
dimension of the hypothesis class $\mathcal{H}$, $\sigma$ is the smoothness
parameter, $K$ is the parameter for the number of hints in the transductive
learning, and $T$ is the number of time steps.

Our work considers two settings in the beyond worst case analysis of online
learning: Smoothed analysis of online learning and $K$-hint transductive
learning. In both cases, we give the first oracle-efficient online learning
algorithms whose regret is characterized by the statistical offline complexity
measures. In particular, we show that there are efficient algorithms, given
access to an ERM oracle, that achieve sublinear regret that depends only on
the pseudo- (or VC) dimension of a class of hypothesis, as well as a measure
of parameters of these models that capture the power of the adversary, i.e.,
$\sigma$ and $K$ respectively. We study both the real-valued and binary valued
losses and achieve nearly tight upper and lower bound for these settings. We
summarize our main results in Table 1.

##### Upper bounds and Algorithms.

For the general case, we design an algorithm based on the _Relax-and-
Randomize_ principle of [RSS12] that achieves a regret bound of
$O(\sqrt{TdK})$ for $K$-hint transductive learning and
$O(\sqrt{Td\sigma^{-1}})$ for smoothed online learning, where $d$ is the
pseudo-dimension of the hypothesis class. This algorithm uses $2$ oracle calls
per round. We improve these regret bounds for the binary classification
setting under smoothed analysis and achieve regret of
$O(\sqrt{Td\sigma^{-1/2}})$. The algorithm that achieves these improved bounds
is a variant of FTPL that uses Poisson random variables in the design of its
perturbations. This algorithm uses $1$ oracle call per round. The primary
reason we can achieve improved regret in the binary setting is that the
$\sigma$-smoothness over the instance domain $\mathcal{X}$ also implies
$\sigma/2$-smoothness over the instance-label pairs
$\mathcal{X}\times\mathcal{Y}$.

While these bounds demonstrate sublinear regret that only depends on $d$, $K$
and $\sigma$, their dependence on $K$ and $\sigma$ does not match the (non-
efficient) statistically optimal regret bound of
$\widetilde{O}(\sqrt{Td\ln(K)})$ and $\widetilde{O}(\sqrt{Td\ln(1/\sigma})$.
For the case of binary classification under smoothed analysis, the
statistically optimal regret bound is due to [HRS22]. For the other settings,
we provide the optimal statistical rates in Appendix G.

##### Lower bounds.

We further investigate the gap between the computational and statistical
regret upper bounds. We present an algorithm-independent lower bound for the
setting of smoothed online learning that shows that any algorithm with runtime
$o(\sqrt{d/\sigma})$ will incur a $\Omega(\sqrt{T(d/\sigma)^{1/2}})$ regret.
We note that this lower bound demonstrates the same dependence on $1/\sigma$
as our upperbound (for the binary classification setting under smoothed
analysis). We also provide algorithm-dependent regret lower bounds that
demonstrate improved dependence on parameters $K$ and $d$, and apply to all
relax-and-randomize and FTPL-style algorithms.

##### Improved Bounds for the Classical Settings.

In addition to constrained adversaries, our algorithms and analysis also imply
improved regret bounds for two classical settings, namely, _online learning in
bounded domains with worst-case adversaries_ and traditional _online
transductive learning_. For worst-case adversaries in binary classification
with domain size $\mathinner{\\!\left\lvert\mathcal{X}\right\rvert}$, we
achieve a regret of
$O(\sqrt{T(d\mathinner{\\!\left\lvert\mathcal{X}\right\rvert})^{1/2}})$,
improving upon the
$O(\sqrt{T\mathinner{\\!\left\lvert\mathcal{X}\right\rvert}})$ bound of
[DS16]. For online transductive binary classification we achieve a regret
bound of $O(T^{3/4}d^{1/4})$, improving upon the $O(T^{3/4}d^{1/2})$ bound in
[KK05]. Both improvements are enabled by our novel Poissonized FTPL analysis
and techniques which achieve stronger regret bounds in the binary
classification setting.

###  1.2 Technical Overview

##### Relaxations for Beyond Worst-Case Adversaries.

The design of our algorithms is based on the random playout technique and we
will use the _admissible relaxation_ framework of [RSS12] to analyze these
algorithms. Each of our algorithms generates and randomly labels instances as
a stand-in for the future. We show how this framework is especially useful for
analyzing online learning algorithms in the beyond worst-case setting. In
particular, the $K$-hint transductive setting, in contrast to the classical
transductive setting, includes hints that are never realized as part of the
sequence. To show that these hints have a small impact on the achievable
regret, we prove that the _regularized Rademacher complexity_ is monotone in
the set of provided hints (Lemma 3.2). This monotonicity allows us to leverage
existing relaxations that are admissible for highly predictable adversaries
and to show that the regret gracefully degrades as a function of the power of
the adversary.

##### Self Generation of Hints.

In the smoothed analysis setting, the algorithm does not have access to hints,
nevertheless, smoothness captures a level of predictability about the future.
This is captured by a technique from [HRS22] that shows that any sequence of
$T$ instances generated by adaptive smoothed adversaries can be seen being a
subset of set of $T/\sigma$ uniformly random instances from $\mathcal{X}$ with
high probability. We use this to self-generate hints and draw a parallel
between $K$-hint transductive learning and smoothed analysis. Though the next
instance given by the adversary is not guaranteed to be in this hint set, we
show that this process accounts for the uncertainty in each step.

Another key aspect is the distribution from which hints are self-generated. We
will crucially use the Poissonization technique in which we generate the
number of hints from an appropriately chosen Poisson distribution. This allows
us an additional degree of independence that is essential to controlling the
loss from one step to the next. Both of these properties are key in our
analyses of the admissibility of the corresponding relaxation.

##### Generalization, Stability, and Admissibility.

In addition, we make use of a connection between the traditional notion of
algorithmic stability and admissibility. Stability is a well-studied notion
capturing how little the distribution of the actions of the learner changes
across time steps and is used in the analyses of algorithms such as follow-
the-perturbed-leader and follow-the-regularized-leader. We show that the
admissibility of the relaxation in the smoothed online setting is implied by
the stability. This allows us to use information theoretic techniques that
crucially exploit the independence provided by Poissonization as discussed
earlier.

As we show, the stability analysis of the algorithm also depends crucially on
the generalization error of the ERM output when it is trained on uniformly
self-generated hints and tested on smoothly distributed fresh instances. In
order to bound the generalization error, we take advantage of a stronger
property implied by the coupling lemma from [HRS22]. This states that there
exists a coupling between uniform and adaptive smooth processes, such that
when the inclusion property is satisfied, the distribution of the uniform
variables realized in the inclusion _conditional on the unrealized uniform
variables_ is also identical to the smooth distributions given by the
adversary. This will be instrumental for bounding the generalization error by
allowing us to extract smooth variables from a set of uniform variables, which
can then be used to for the purpose of symmetrization. This result may be of
independent interest.

###  1.3 Related works

Our work relates to several paradigms and approaches to online learnability.

##### Oracle-Efficient Online Learning.

Since the seminal work of [KV05], inspired by application domains such as game
theory, there has been a long line of work elucidating the computational
aspects of online learning. [KV05] proposed the influential follow-the-
perturbed-leader algorithm. [KKL07] study notions of regret when the learner
is given access to an approximate optimization oracle. [KK05] study the
transductive learning setting and give an efficient algorithm that converts
offline learnablity to online learnability. [RSS12] propose a general
_admissible relaxation_ framework to develop efficient algorithms based on the
upper bound of the value of the game. This framework has also been built on
and extended in a variety of settings such as auctions [DHL+20], contextual
learning [SKS16, FR20, SLX21], and reinforcement learning [FKQR21]. On the
flip size, [HK16] show that an $\Omega(\sqrt{N})$ lower bound is unaviodable
in general in order to obtain nontrivial regret where the $N$ is the number of
actions of the learner suggesting that one needs to look beyond the worst-case
in order to get truly efficient algorithms.

##### Beyond Worst-case Approaches to Online Learning.

Various notion of beyond worst-case behavior of online learning has been
studied in the literature. [RST11] consider online learning where the
adversary is constrained and build a framework based on minimax analysis and
constrained sequential Rademacher complexity to analyze regret in these
scenarios. These techniques have been applied to other constrained settings
[KAH+19].

[GR17] consider smoothed online learning when looking at problems in online
algorithm design. They prove that while optimizing parameterized greedy
heuristics for combinatorial problems in presence of smoothing this problem
can be learned with non-trivial sublinear regret. [CAK17] consider the same
problem with an emphasis on the per-step runtime being logarithmic in $T$.
[HRS20, HRS22] both study the notion of smoothed analysis with adaptive
adversary and show that statistically the regret is bounded by
$O(\sqrt{Td\log(1/\sigma)})$.

Smoothed analysis has also been studied in a number of other online settings,
including linear contextual bandits, [KMR+18, RSWW18], but the focus has been
on achieving improved regret bounds for the greedy algorithm that is not no-
regret in the worst-case.

Another line of work has focused on the future sequences being predictable
given the past instances. [RS13b] incorporate additional information available
in terms of an estimator for future instances. They achieve regret bounds
depending on the path length of these estimators and can beat the worst-case
$\Omega(\sqrt{T})$ if the estimators are accurate. [HM07] models
predictability as knowing the first coordinate of loss vectors, which is
revealed to the learner before he chooses actions. Some other work model
predictability through hints which are additive estimate of loss vectors
[HK10, RS13a, SL14, MY16]. [DHJ+17, BCKP20] considers settings where the
learner has access to hints in form of vectors that are weakly correlated with
the future instances and show exponential improvement in the regret in some
cases. The literature on hints represents an active and growing subarea of
online learning (see [BCKP20] and references within).

##### Concurrent Work.

In a concurrent and independent work, [BDGR22] also gives oracle-efficient
algorithms for smoothed online learning. [BDGR22] obtains a regret bound of
$\widetilde{O}(\sqrt{Td\sigma^{-1}})$. In comparison, our main result (Theorem
4.2) concerning smoothed online learning demonstrates a regret bound of
$\widetilde{O}(\sqrt{Td\sigma^{-1/2}})$ with strictly better dependence on
$\sigma$. Our regret bound’s improved dependence on parameter $\sigma$ can be
attributed the following technical innovations of this work: 1) The
relationship between stability and relaxation-based methods, 2) the careful
analysis of _modified generalization error_ and _stability_ via a new
coupling-based argument, and 3) a Poissonization approach for _self-
generating_ hints that allow us to leverage information theoretic arguments.
Importantly, the novel techniques for achieving improved dependence on
$\sigma$ also enable us to improve on the small-domain result of [DS16] and
the transductive learning result of [KK05].

Interestingly, both our work and [BDGR22] use a relaxation-based algorithms as
a warmup achieving regret bounds of $\widetilde{O}(\sqrt{Td\sigma^{-1}})$ (our
Theorem 4.1) and $\widetilde{O}(\sigma^{-1}\sqrt{Td})$ [BDGR22, Theorem 8] for
learning real-valued functions. For the warmup, our regret bound’s improved
dependence on parameter $\sigma$ is due to our different approach to self-
generating hints that allow us to leverage the monotonicity of the Rademacher
complexity.

##  2 Preliminaries

Let $\mathcal{X}$ be the space of instances, $\mathcal{Y}=[-1,1]$ be the space
of labels, and $\mathcal{H}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{X}\to\mathcal{Y}$ be the hypothesis class with pseudo
dimension $d$ (See definition D.1 or [AB99] for the definition of pseudo
dimension). Let $l\mathrel{\mathop{\mathchar
58\relax}}\mathcal{Y}\times\mathcal{Y}\to[0,1]$ be a convex loss function with
Lipschitz constant $G$ in its first component.

In online learning with adaptive adversaries, the learner and the adversary
plays a repeated game for $T$ time steps. At each step $t\in[T]$, the
adversary chooses a distribution
$\mathcal{D}_{t}^{\mathcal{X}}\in\Delta(\mathcal{X})$. A random instance
$x_{t}\sim\mathcal{D}_{t}^{\mathcal{X}}$ is then drawn and presented to the
learner. After receiving $x_{t}$, the learner predicts its label to be
$\widehat{y}_{t}\in\mathcal{Y}$, while the adversary simultaneously chooses
$y_{t}\in\mathcal{Y}$ as its true label. The learner then suffers loss
$l(\widehat{y}_{t},y_{t})$. This is equivalent to a setting where the
adversary chooses a distribution
$\mathcal{D}_{t}\in\Delta(\mathcal{X}\times\mathcal{Y})$ over labeled
instances $s_{t}=(x_{t},y_{t})$ and the learner simultaneously chooses a
classifier $h_{t}\in\mathcal{Y}^{\mathcal{X}}$. We will abbreviate
$\mathcal{D}_{t}^{\mathcal{X}}$ to $\mathcal{D}_{t}$ when it is clear from the
context.

We allow the adversary to be adaptive, i.e., it can choose each
$\mathcal{D}_{t}$ based on the realizations of the inputs as well as the
learner’s predictions in previous time steps. Let $\mathscr{D}$ denote the
adaptive sequence of distributions $\mathcal{D}_{1},\cdots,\mathcal{D}_{T}$.
Accordingly, let $\mathcal{Q}_{t}\in\Delta(\mathcal{Y})$ denote the learner’s
prediction rule on instance $x_{t}$, and let $\mathscr{Q}$ denote the adaptive
sequence of distributions $\mathcal{Q}_{1},\cdots,\mathcal{Q}_{T}$. We denote
the expected regret of a learner with prediction rules $\mathscr{Q}$ on the
adaptive sequence $\mathscr{D}$ by

$\displaystyle\operatorname*{\mathbb{E}}[\textsc{Regret}(T,\mathscr{D},\mathscr{Q})]=\operatorname*{\mathbb{E}}_{\mathscr{D},\mathscr{Q}}\left[\sum_{t=1}^{T}l(\widehat{y}_{t},y_{t})-\inf_{h\in{\mathcal{H}}}\sum_{t=1}^{T}l(h({x_{t}}),y_{t})\right].$
(1)

We remove $\mathscr{D}$ and $\mathscr{Q}$ from this notation when they are
clear from the context.

##### Offline Optimization Oracle

We consider computationally efficient algorithms given access to an offline
optimization oracle. For the case of binary classification, the oracle outputs
the solution of empirical risk minimization on the input data.

######  Definition 2.1 (ERM Oracle).

For a hypothesis class $\mathcal{H}$ and a loss function $l$, the oracle
$\mathsf{OPT}$ ($\mathsf{opt}$) takes a set 222The inputs to the oracle are
multisets. Unless specified otherwise, all the sets in this paper refer to
multisets. of inputs $S=\\{(x_{i},y_{i})\\}_{i\in[I]}$ where
$(x_{i},y_{i})\in\mathcal{X}\times\mathcal{Y}$ for all $i\in[I]$ and returns

$\displaystyle\mathsf{OPT}_{\mathcal{H},l}({S})=\inf_{h\in\mathcal{H}}\sum_{i=1}^{I}l(h(x_{i}),y_{i})~{}\text{
and
}~{}\mathsf{opt}_{\mathcal{H},l}({S})\in\arg\inf_{h\in\mathcal{H}}\sum_{i=1}^{I}l(h(x_{i}),y_{i}).$
(2)

For the case of real-valued functions, we consider an oracle that can minimize
a mixture of binary and real-valued loss values defined below.

######  Definition 2.2 (Real-valued optimization oracle).

For a hypothesis class $\mathcal{H}$ and two loss functions $l^{r}$ and
$l^{b}$, the oracle $\mathsf{OPT}$ takes two sets of inputs $S$ and
$S^{\prime}$ over $\mathcal{X}\times\mathcal{Y}$ and returns

$\mathsf{OPT}_{\mathcal{H},l^{\mathrm{r}},l^{\mathrm{b}}}(S;S^{\prime})=\inf_{h\in\mathcal{H}}\Big{(}\sum_{(x,y)\in
S}l^{\mathrm{r}}(h(x),y)+\sum_{(x^{\prime},y^{\prime})\in
S^{\prime}}l^{\mathrm{b}}(h(x^{\prime}),y^{\prime})\Big{)}.$

We remark that these oracles are used in most previous works, including
[RSS12]. They constitute a special form of regularized loss minimization
oracles, where the regularization is given directly by a random process. For
the binary setting where $\mathcal{Y}=\\{\pm 1\\}$ and
$l^{\mathrm{r}}=l^{\mathrm{b}}=\mathbf{1}\\!\left\\{\widehat{y}\neq
y\right\\}$, the above optimization oracle is equivalent to ERM oracles.

We consider each call to the offline optimization oracle as having unit cost
plus the additional runtime needed for creating and inputting the set of
inputs that is linear in the length of the said histories. We note that our
approach and results directly extend to using ERM oracles with (arbitrarily
small) additive approximation error, such as those guaranteed by FPTAS
optimization algorithms, using standard techniques presented by [DHL+20,
Section 6].

######  Remark 2.1.

Though the oracles as defined above are required to work on arbitrary inputs,
both Algorithms 1 and 2 from our work only call the optimization oracle on
instances sampled from the smoothed distributions or the uniform distribution.
Thus, it suffices to have oracles that work for average-case instances. This
makes the design of such oracles easier both from theoretical and practical
points of view.

###  2.1 Smoothed Online Learning

We work with the smoothed adaptive online adversarial setting from [HRS22]. We
will consider $\sigma$-smooth adversaries, where a distribution is
$\sigma$-smooth if its density is upper bounded by $1/\sigma$ times the
density of the uniform distribution over the same domain. We remark that all
of our results generalize to arbitrary known base distributions as well.

######  Definition 2.3 ($\sigma$-smoothness).

Let $\mathcal{X}$ be a domain that supports a uniform distribution
$\mathcal{U}$. A measure $\mu$ on $\mathcal{X}$ is $\sigma$-smooth if for all
measurable subsets $A\subseteq\mathcal{X}$,
$\mu(A)\leq\frac{\mathcal{U}(A)}{\sigma}$. The set of all $\sigma$-smooth
distributions on domain $\mathcal{X}$ is denoted by
$\Delta_{\sigma}(\mathcal{X})$.

In online learning with adaptive smoothed adversaries, at each time step $t$,
the adversary chooses a distribution $\mathcal{D}_{t}$ whose marginal on
$\mathcal{X}$ is $\sigma$-smooth. The choice of $\mathcal{D}_{t}$ can depend
the previous instances $\\{(x_{i},y_{i})\\}_{i=1}^{t-1}$ as well as the
learner’s previous predictions. We denote with $\mathscr{D}_{\sigma}$ the
adaptive sequence of $\sigma$-smooth distributions on the instances. The
corresponding definition of regret in this setting is given by Equation 1 with
$\mathcal{D}_{\sigma}$ as the set of distribution for the adversary.

An important property of smoothness is that it implies coupling between
uniform and adaptive smooth processes. We will consider the original result
from [HRS22] in Lemma D.1 and a slightly strengthened statement in Lemma 4.7.
In Section 4, we will provide new insights on the properties of such
couplings.

###  2.2 Transductive Online Learning with $K$ Hints

In the traditional transductive setting, the adversary releases the sequence
of unlabeled instances $\\{x_{t}\\}_{t=1}^{T}$ to the learner before the game
starts. We generalize this setting and introduce a $K$-hint version of
transductive learning. In this setting, the exact sequence of instances is
replaced with a sequence of $K$ _hints_ per time step such that the set of
hints at each time step includes the instance at that time step. More
formally, before the interaction starts, the adversary releases $T$ sets
(multisets) of size $K$ to the learner. We denote these sets by
$\\{Z_{t}=\\{z_{t,1},\cdots,z_{t,K}\\}\\}_{t=1}^{T}$. On releasing these sets,
the adversary promises to always pick $\mathcal{D}_{t}$ supported only on the
elements of $Z_{t}$. The regret is defined by Equation 1 with the appropriate
restriction on the adversary.

###  2.3 Relaxations and Admissibility

Our algorithms for the general (real-valued) setting relies on the _admissible
relaxation_ framework proposed in [RSS12]. A relaxation $\textbf{Rel}_{T}$ is
a sequence of functions
$\textbf{Rel}_{T}(\mathcal{H}|s_{1\mathrel{\mathop{\mathchar 58\relax}}t})$
for each $t\in[T]$, which map the history of the play to real values that
upper bounds the conditional value of the game. We will make use of an
important algorithmic aspect of the relaxation framework, which states that
whenever an algorithm is _admissible_ with respect to some relaxation, its
expected regret can be upper bounded in terms of the value of the relaxation
at the beginning of the game.

######  Definition 2.4 (Admissibility).

In an online learning setting where the adversary is restricted to playing
$\mathcal{D}_{t}\in\mathfrak{D}_{t}\subseteq\Delta(\mathcal{X})$ at each time
$t$, let $\mathscr{Q}$ be an algorithm that gives rise to a sequence of
distributions $\mathcal{Q}_{1},\cdots,\mathcal{Q}_{T}$ on the predicted
labels. We say $\mathscr{Q}$ is admissible with respect to a relaxation
$\\{\emph{{Rel}}_{T}(\mathcal{H}\mid s_{1\mathrel{\mathop{\mathchar
58\relax}}t})\\}_{t=0}^{T}$, if for any sequence of instances
$s_{1\mathrel{\mathop{\mathchar 58\relax}}T}$,

  1. 1.

For all $t\in[T]$,

$\displaystyle\sup_{\mathcal{D}_{t}\in\mathfrak{D}_{t}}\operatorname*{\mathbb{E}}_{x_{t}\sim\mathcal{D}_{t}}\sup_{y_{t}\in\mathcal{Y}}\\!\left\\{\\!\operatorname*{\mathbb{E}}_{\widehat{y}_{t}\sim\mathcal{Q}_{t}}\\![l(\widehat{y}_{t},y_{t})]\\!+\\!\emph{{Rel}}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}\\!\cup\\!(x_{t},y_{t}))\\!\right\\}\\!\leq\\!\emph{{Rel}}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar 58\relax}}t-1});$ (3)

  2. 2.

The final value satisfies $\emph{{Rel}}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar
58\relax}}T})\geq-\inf_{h\in\mathcal{H}}L(h,s_{1\mathrel{\mathop{\mathchar
58\relax}}T}).$

In the smoothed online learning setting,
$\mathfrak{D}_{t}=\Delta_{\sigma}(\mathcal{X})$ is the set of $\sigma$-smooth
distributions on $\mathcal{X}$. In the $K$-hint transductive online learning
setting, $\mathfrak{D}_{t}$ is the set of distributions supported on $Z_{t}$.

The following proposition is the analog of the results of [RSS12] when the
adversary is smooth. The full proof is presented in Appendix A.

######  Proposition 2.1 (Regret Bound via Admissibility).

In the online learning setting where the adversary’s choice is restricted to
$\mathfrak{D}_{t}$ ($t\in[T]$), let
$\mathscr{Q}=(\mathcal{Q}_{1},\cdots,\mathcal{Q}_{T})$ be an algorithm that is
admissible with respect to relaxations $\emph{{Rel}}_{T}(\mathcal{H})$, then
the following bound on the expected regret holds regardless of the strategies
$\mathscr{D}$ of the adversary:

$\displaystyle\operatorname*{\mathbb{E}}[\textsc{Regret}(T,\mathscr{Q},\mathscr{D})]\leq\emph{{Rel}}_{T}(\mathcal{H}\mid\emptyset)+O(\sqrt{T}).$
(4)

###  2.4 Follow the Perturbed Leader

When the labels are binary, we design am algorithm which achieves improved
regret bounds using the Follow the Perturbed Leader (FTPL) principle [KV05].
An FTPL algorithm makes predictions by applying ERM oracle to the perturbed
histories of the play. At every time step $t\in[T]$, the algorithm chooses a
distribution over labeled instances, from which it draws $N$ random instances
$(\widetilde{x}_{1}^{(t)},\widetilde{y}_{1}^{(t)}),\cdots,(\widetilde{x}_{N}^{(t)},\widetilde{y}_{N}^{(t)})$.
The predicted label is then given by $\widehat{y}_{t}=h_{t}(x_{t})$, where

$\displaystyle
h_{t}\leftarrow\mathsf{opt}_{\mathcal{H},l}\left(s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}\cup\\{(\widetilde{x}_{i}^{(t)},\widetilde{y}_{i}^{(t)})\\}_{i\in[N]}\right).$
(5)

The standard analysis of FTPL bounds the expected regret as follows:

$\displaystyle\operatorname*{\mathbb{E}}[\textsc{Regret}]\leq\underbrace{\operatorname*{\mathbb{E}}\\!\left[\sum_{t=1}^{T}l\\!\left(h_{t}(x_{t}),y_{t}\right)-l\\!\left(h_{t\\!+\\!1}(x_{t}),y_{t}\right)\right]}_{\text{Stability}}+\underbrace{\operatorname*{\mathbb{E}}\\!\left[\sup_{h\in\mathcal{H}}\sum_{i=1}^{N}l(h(\widetilde{x}_{i}),\widetilde{y}_{i})-\sum_{i=1}^{N}l(h^{*}(\widetilde{x}_{i}),\widetilde{y}_{i})\right]}_{\text{Perturbation}},$
(6)

where $h^{*}=\arg\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}l(h(x_{t}),y_{t})$.

Note that the perturbation term is already well-understood from statistical
learning theory since it is essentially the Rademacher complexity of
$\mathcal{H}$ for sample size $N$. Therefore, we will focus on bounding the
stability term by designing perturbations that can leverage the anti-
concentration property of smoothed adversaries.

##  3 $K$-hint Transductive Learning

As a prelude, we will first look at the $K$-hint transductive learning with
real-valued labels, which highlights some challenges that are present in the
smoothed online setting while allowing us to discuss the required tools in a
simpler scenario. The statistical upper bound given by the inefficient
algorithm that simply plays Hedge on a covering of the projection of
$\mathcal{H}$ to the hint set is $O(\sqrt{dT\log(TK)})$, as shown in Theorem
G.3. We will show an oracle-efficient regret upper bound of $O(\sqrt{dTK})$ by
constructing an oracle-efficient algorithm based on the random playout
technique. We consider the optimization oracle defined in Definition 2.2 with
the loss functions specified by
$l^{\mathrm{r}}(\hat{y},y)=\frac{1}{2G}l(\hat{y},y)$ and
$l^{\mathrm{b}}(\hat{y},y)=\mathbf{1}\\!\left\\{\widehat{y}\neq
y\right\\}-\frac{1}{2}$.

Let us begin by describing our algorithm for the setting of $K$-hint
transductive learning. At each time step $t$, our algorithm applies the
offline optimization oracle to two input sequences: One where the real history
$s_{1\mathrel{\mathop{\mathchar 58\relax}}t-1}$ is mixed with two copies333We
use two copies to scale the loss appropriately. of randomly labeled set of all
hints corresponding to future time steps and the current instance is labled
$+1$, and another, where the current instance is labeled $-1$.

More specifically, with
$\mathcal{E}^{(t)}=\\{\epsilon_{i,k}^{(t)}\\}_{{i=t+1\mathrel{\mathop{\mathchar
58\relax}}T},{k=1\mathrel{\mathop{\mathchar 58\relax}}K}}$ denoting the set of
random labels and $S^{(t)}=(Z_{t+1\mathrel{\mathop{\mathchar
58\relax}}T},\mathcal{E}^{(t)})$ denoting the set of hints labeled by
$\mathcal{E}^{(t)}$, we consider

$\displaystyle\widehat{y_{t}}=$
$\displaystyle\mathsf{OPT}\left(s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1};S^{(t)}\cup
S^{(t)}\cup\\{(x_{t},-1)\\}\right)-\mathsf{OPT}\left(s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1};S^{(t)}\cup S^{(t)}\cup\\{(x_{t},+1)\\}\right).$ (7)

Since the two input sequences to the optimization oracle only disagree on one
label, the difference in the optimal errors is always bounded within
$[-1,+1]$, thus guarantees $\widehat{y}_{t}\in\mathcal{Y}$. Intuitively, the
reason $\hat{y}_{t}$ includes the gap between the error of these two optimal
classifiers is to make the algorithm hedge its bets against how the adversary
is going to label the current instance $x_{t}$. A formal description of the
algorithm is given in Algorithm 3. The following theorem provides an upper
bound on the regret.

######  Theorem 3.1 (Regret Bound for Efficient $K$-Hint Transductive
Learning).

In the setting of transductive learning with $K$-hints, the above algorithm
has expected regret bound of $O(\sqrt{dTK}).$ The algorithm can be implemented
using two calls to the optimization oracle per round.

The proof of Theorem 3.1 follows a similar approach to the work of [RSS12] and
uses the admissible relaxation framework. In this section, we provide an
overview of this approach and the modifications that allow us to incorporate a
larger set of hints. Specifically, we will show that the algorithm is
admissible with respect to the following relaxation:

$\displaystyle\textbf{Rel}_{T}(\mathcal{H}\mid s_{1\mathrel{\mathop{\mathchar
58\relax}}t})=\operatorname*{\mathbb{E}}_{\mathcal{E}^{(t)}}\left[\sup_{h\in\mathcal{H}}\left\\{2G\sum_{i=t+1\mathrel{\mathop{\mathchar
58\relax}}T\atop k=1\mathrel{\mathop{\mathchar
58\relax}}K}\epsilon_{i,k}^{(t)}h(z_{i,k})-\sum_{i=1}^{t}l(h(x_{i}),y_{i}))\right\\}\right],\qquad
t=0,\cdots,T.$ (8)

To simplify the notation, for a set of unlabeled instances
$Z=\\{z_{i}\\}_{i=1}^{I}$ and a function $\Phi\mathrel{\mathop{\mathchar
58\relax}}\mathcal{H}\to\mathbb{R}$, we define $\mathfrak{R}(\Phi,Z)$ as the
Rademacher complexity for set $Z$ regularized by $\Phi$, that is

$\mathfrak{R}({\Phi},Z)=\operatorname*{\mathbb{E}}_{\epsilon_{1\mathrel{\mathop{\mathchar
58\relax}}I}\overset{\text{iid}}{\sim}\mathcal{U}(\pm
1)}\Big{[}\sup_{h\in\mathcal{H}}\Big{\\{}\sum_{i\leq
I}\epsilon_{i}h(z_{i})+\Phi(h)\Big{\\}}\Big{]}.$

Then the relaxation at the end of time step $t$ can be written as the
Rademacher complexity for the union of future hints, regularized by the past
total loss. That is,

$\displaystyle\textbf{Rel}_{T}(\mathcal{H}\mid s_{1\mathrel{\mathop{\mathchar
58\relax}}t})=2G\cdot\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t}),Z_{t+1\mathrel{\mathop{\mathchar 58\relax}}T}),$ (9)

where $L^{\mathrm{r}}(h,s_{1\mathrel{\mathop{\mathchar
58\relax}}t})=\sum_{i=1}^{t}l^{\mathrm{r}}(h(x_{i}),y_{i})=\frac{1}{2G}\sum_{i=1}^{t}l(h(x_{i}),y_{i})$
for $h\in\mathcal{H}$.

We remark that while the original definition of relaxation keeps track of the
sequence of inputs that are already known at the end of each time step
($s_{1\mathrel{\mathop{\mathchar 58\relax}}t}$), the regularized Rademacher
complexity also explicitly emphasizes the instances
$Z_{t+1\mathrel{\mathop{\mathchar 58\relax}}T}$ denoting unknown future.
Between successive time steps, one extra data point $s_{t}$ will be added to
the set of known inputs, but the set of unknown future instances will shrink
by $K$.

To use the relaxation framework and Proposition 2.1, it suffices to establish
two claims: 1) the relaxation in Equation 12 is admissible in the $K$-hint
setting, 2) the value of this relaxation at the beginning of the game is not
too large.

For the second claim, we notice that
$\textbf{Rel}_{T}(\mathcal{H}\mid\emptyset)$ is equal to the unregularized
Rademacher complexity for the dataset that includes all the hints. Since there
are at most $TK$ hints, the Rademacher complexity is at most
$\widetilde{O}(\sqrt{dTK})$ according to Lemma D.3. That’s where we get the
extra $\sqrt{K}$ in the bounds compared to the standard transductive setting.

The first claim is the more technically interesting one. For admissibility,
here we will focus on proving the following bound

$\displaystyle\sup_{x_{t}\in
Z_{t}}\\!\underbrace{\sup_{y_{t}\in\mathcal{Y}}\\!\big{\\{}\\!\operatorname*{\mathbb{E}}_{\widehat{y}_{t}\sim\mathcal{Q}_{t}}[l^{\mathrm{r}}(\widehat{y}_{t},y_{t})]\\!+\\!\mathfrak{R}(\\!-\\!L_{t}^{\mathrm{r}},Z_{t+1\mathrel{\mathop{\mathchar
58\relax}}T}\\!)\\!\big{\\}}}_{\text{(a)}}\\!\leq\\!\sup_{x_{t}\in
Z_{t}}\\!\mathfrak{R}(\\!-\\!L_{t-1}^{\mathrm{r}},Z_{t+1\mathrel{\mathop{\mathchar
58\relax}}T}\\!\cup\\!\\{\\!x_{t}\\!\\}\\!)\\!\leq\\!\mathfrak{R}(\\!-\\!L_{t-1}^{\mathrm{r}},Z_{t\mathrel{\mathop{\mathchar
58\relax}}T}),$ (10)

where $L_{t}^{\mathrm{r}}(h)$ abbreviates for
$L^{\mathrm{r}}(h,s_{1\mathrel{\mathop{\mathchar 58\relax}}t})$.

Let us consider the L.H.S of the above inequality and note that for any fixed
$x_{t}$, the term (a) captures the standard transductive learning setting with
$Z_{t+1\mathrel{\mathop{\mathchar 58\relax}}T}$ being the set of unlabeled
instances for the future. In this case, the convexity of loss function
$l^{\mathrm{r}}$ together with the min-max theorem can be used to show that
the learner’s strategy $\mathcal{Q}_{t}$, which makes the two values inside
the supremum over $\mathcal{Y}$ equalize as $y_{t}$ takes value $-1$ and $+1$,
is indeed the optimal strategy. At a high level, this technique which is also
used by [RSS12], gives rise to the algorithm in Equation 7 and proves the
first inequality in Equation 10. We refer the readers to [RSS12, Lemma 12] for
more details about the proof.

The second transition in Equation 10 can be establishing the fact that
regularized Rademacher complexity is monotone in the dataset. See Section B.2
for a proof of Lemma 3.2.

######  Lemma 3.2 (Monotonicity of Regularized Rademacher Complexity).

For any dataset $z_{1\mathrel{\mathop{\mathchar
58\relax}}m}\in\mathcal{X}^{m}$ and any additional data point
$x\in\mathcal{X}$, we have $\mathfrak{R}(\Phi,z_{1\mathrel{\mathop{\mathchar
58\relax}}m})\leq\mathfrak{R}(\Phi,z_{1\mathrel{\mathop{\mathchar
58\relax}}m}\cup\\{x\\}).$

This monotonicity can be used recursively to add the extra set of hints
$Z_{t}$ to the relaxation. This implies $\sup_{x_{t}\in
Z_{t}}\mathfrak{R}(-L_{t-1},Z_{t+1\mathrel{\mathop{\mathchar
58\relax}}T}\cup\\{x_{t}\\})\leq\mathfrak{R}(-L_{t-1},Z_{t+1\mathrel{\mathop{\mathchar
58\relax}}T}\cup Z_{t})$.

##  4 Oracle-Efficient Smoothed Online Learning

In this section, we prove our main result for the case of smoothed analysis of
online learning and give the first oracle-efficient algorithms whose regret
are sublinear in $T$ and pseudo (or VC) dimension.

######  Theorem 4.1 (Regret Bound for Smoothed Online Regression).

For any $\sigma$-smooth adversary $\mathscr{D}_{\sigma}$, Algorithm 1 has
expected regret upper bounded by $\widetilde{O}(G\sqrt{Td/\sigma})$, where
$\widetilde{O}$ hide factors that are polynomial in $\log(T)$ and
$\log(1/\sigma)$. Here $G$ is the Lipschitz constant of the loss and $d$ is
the pseudodimension of the class. Furthermore, the algorithm is oracle-
efficient: at every round $t$, this algorithm uses two oracle calls with
histories of length $\widetilde{O}(T/\sigma)$.

######  Theorem 4.2 (Regret Bound for Smoothed Online Classification).

In the setting of online binary classification with $\sigma$-smoothed
adversaries, Algorithm 2 has regret that is at most

$\displaystyle\widetilde{O}\left(\min\left\\{\sqrt{\frac{Td}{\sigma^{1/2}}},\sqrt{T(d|\mathcal{X}|)^{1/2}}\right\\}\right).$
(11)

Furthermore, Algorithm 2 is a _proper_ learning oracle-efficient: at every
round $t$, this algorithm uses a single ERM oracle call a history that is of
length $t+O(T/\sqrt{\sigma})$ with high probability.

We note that Theorem 4.1 and Theorem 4.2 establishes that under smoothed
analysis online learning is as computationally efficient as offline learning.
This is in contrast with the results of [HK16] that showed a computational
separation between offline learning and online learning with worst-case
adversaries. It is worth noting that Theorem 4.2 also matches or improves upon
several existing results for worst-case online learning (without smoothed
analysis). For example, for finite domains where worst-case adversaries are
vacuously $\sigma$-smooth for $1/\sigma=|\mathcal{X}|$, Theorem 4.2 gives an
oracle-efficient regret bound of $O(T^{1/2}(d|\mathcal{X}|)^{1/4})$ which is a
refinement of [DS16] regret bound of $O(\sqrt{T|\mathcal{X}|})$ because
$d\leq|\mathcal{X}|$. Theorem 4.2 also implies the regret bound of
$\widetilde{O}(T^{3/4}d^{1/4})$ for the classical transductive learning
setting, which corresponds to finite domains with $\sigma=1/T$ parameter. This
improves the $\widetilde{O}(T^{3/4}d^{1/2})$ bound of [KK05]. See Corollary
4.3 for a precise statement.

######  Corollary 4.3 (Regret for Small Domain).

There is an oracle-efficient algorithm for online learning with binary labels
(in the worst-case) that achieves a regret of
$O(\sqrt{T(d|\mathcal{X}|)^{1/2}})$ for any hypothesis class with VC dimension
$d$ on domain $\mathcal{X}$. For transductive learning with binary labels,
there is an oracle efficient algorithm, with regret
$O\left(T^{3/4}d^{1/4}\right)$.

######  Remark 4.1.

Both Algorithms 1 and 2 can be adapted to deal with unknown $\sigma$. In
particular, the regret bounds hold for any approximation $\widetilde{\sigma}$
that is a lower bound of the real $\sigma$ up to constant multiplicative
factors. This corresponds to settings where the world is more smooth than we
give it credit. Even when we have extremely poor upper and lower bounds, we
can use hedging to still get non-trivial regret with only a minor blow up in
computation. We will provide more details in Appendix C about working with
knowledge of approximate $\widetilde{\sigma}$.

The key challenge with adapting our previous approach is that, unlike the
$K$-hint transductive setting, in smoothed analysis the learner no longer has
access to any hints. For finite domains, such as the above examples, our (and
existing) algorithms self-generate hints from every instance in $\mathcal{X}$,
using uniform or geometric random variables. But these choices do not directly
extend to large and infinite domains where most of the domain $\mathcal{X}$
will not be present in the hints. Therefore, for smoothed analysis with large
or infinite domains, our algorithms must self-generate hints that leverage the
_anti-concentration_ properties of smooth distributions. In Section 4.1, we
show how this can be done by taking $K=\widetilde{O}(1/\sigma)$ uniformly
random instances from $\mathcal{X}$ and using the techniques we developed in
Section 3 to achieve a regret bound of $\widetilde{O}(\sqrt{Td/\sigma})$.
Interestingly, the particular form of randomness used for producing hints is
consequential. In Section 4.2, we show that in the special case of binary
classification, the Poisson distribution over the size of the hint set is an
appropriate choice to leverage properties implied by the smoothness of the
distributions, while leading to relaxations that enjoy better admissibility
and stability guarantees.

Another important aspect of stability is the use of a modified definition of
generalization error, i.e., relating the performance of ERM trained with
uniform self-generated hints had we re-sampled the last smoothed adversarial
instance. We will provide insights about the coupling approach that allows us
to relate generalizability with respect to smooth distributions to that of the
uniform distribution directly.

###  4.1 Learning with Real-Valued Functions

In this section, we show how insights and techniques for the $K$-hint
transductive setting in Section 3 transition to the setting of smoothed online
setting and lead to $\widetilde{O}(\sqrt{Td/\sigma})$ regret. When the labels
are binary, we will further build upon this connection in Section 4.2 to
improve on the regret bound of this section.

The key challenge with adapting the previous techniques is to self-generate
hints that leverage the anti-concentration properties of smooth distributions.
In particular, we will use the coupling technique introduced by [HRS22] (see
Lemma D.1 for a complete description) to replace the sequence of $T$ random
inputs $x_{1\mathrel{\mathop{\mathchar 58\relax}}T}$ generated by the adaptive
adversary with $TK$ inputs $\\{z_{t,k}\\}_{t=1\mathrel{\mathop{\mathchar
58\relax}}T,k=1\mathrel{\mathop{\mathchar 58\relax}}K}$ that are generated
i.i.d. from the uniform distribution over $\mathcal{X}$, such that with high
probability
$\\{x_{1},\cdots,x_{T}\\}\subseteq\\{z_{t,k}\\}_{{t\in[T]},{k\in[K]}}$. This
property highlights the connection between a smoothed adaptive adversary and a
transductive adversary with $K$ uniform random hints.

From a computational point of view, this observation implies that a learner
can generate uniform random hints, denoted by
$\\{v_{i,k}^{(t)}\\}_{{i=t+1\mathrel{\mathop{\mathchar
58\relax}}T},{k=1\mathrel{\mathop{\mathchar 58\relax}}K}}$, and use them in
place of $\\{z_{i,k}\\}_{{i=t+1\mathrel{\mathop{\mathchar
58\relax}}T},{k=1\mathrel{\mathop{\mathchar 58\relax}}K}}$ in Algorithm 3. The
resulting algorithm is summarized in Algorithm 1 and leads to the regret upper
bound in Theorem 4.1.

Input: $T,\sigma$

1 $K\leftarrow{100\log T}/{\sigma}$.

2 for  _$t\leftarrow 1$ to $T$_ do

3 Receive $x_{t}$.

4 for  _$i=t\\!+\\!1,\cdots,T$ ; $k=1,\cdots,K$_ do

5 Draw new $v_{i,k}^{(t)}\sim\mathcal{U}(\mathcal{X})$.

6 Draw new $\epsilon_{i,k}^{(t)}\sim\mathcal{U}(\\{-1,+1\\})$.

7 end for

8
$S^{(t)}\leftarrow\left\\{(v_{i,k}^{(t)},\epsilon_{i,k}^{(t)})\right\\}_{\genfrac{}{}{0.0pt}{}{i=t+1\mathrel{\mathop{\mathchar
58\relax}}T\hfill}{k=1\mathrel{\mathop{\mathchar 58\relax}}K\hfill}}$.

9 $\widehat{y}_{t}\leftarrow\mathsf{OPT}\left(s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1};S^{(t)}\cup
S^{(t)}\cup\\{(x_{t},-1)\\}\right)\\!-\\!\mathsf{OPT}\left(s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1};S^{(t)}\cup S^{(t)}\cup\\{(x_{t},+1)\\}\right).$

10 Receive $y_{t}$, suffer loss $l(\widehat{y}_{t},y_{t})$.

11 end for

Algorithm 1 Oracle-Efficient Smoothed Online Learning for Real-valued
Functions

To prove Theorem 4.1, we adjust the relaxation we used in Section 3 and show
that it is admissible with respect to the algorithm. We use the following
relaxation in the smoothed learning setting,

$\displaystyle\textbf{Rel}_{T}(\mathcal{H}\mid s_{1\mathrel{\mathop{\mathchar
58\relax}}t})=2G\operatorname*{\mathbb{E}}_{V^{(t)}\overset{\text{iid}}{\sim}\mathcal{U}(\mathcal{X})}\left[\mathfrak{R}(-{L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t})},V^{(t)})\right]+2G\beta(T-t),$ (12)

where $K=100\log T/\sigma$ and $\beta=10TK(1-\sigma)^{K}$. This relaxation
incorporates two modifications to the relaxation in Equation 8. The first is
an expectation over the randomness of future hints. A subtle point here is
that this randomness crucially matches both random $V^{(t)}$ that the
algorithm has access to and the coupled variables $\\{z_{i,k}\\}$ at a
distribution level that are never revealed to the algorithm. To ensure that
our approach works with adaptive adversaries, it is essential that $V^{(t)}$s
are fresh samples per round. The second is an additional time dependent term
$\beta(T-t)$, which accounts for the total failure probability of the coupling
argument in the future $T-t$ time steps. Since the coupling argument shows
that $K={O}(\log(T)/\sigma)$, we use parameter $\beta=o(T)$ and achieve a
regret upper bound of
$\widetilde{O}(\sqrt{dTK})=\widetilde{O}(\sqrt{Td/\sigma})$. See Appendix D
for more details about the proof.

###  4.2 Improved Bounds for Binary Classification

In this section, we focus on the important special case where the labels are
binary and the loss function is the classification loss
$\mathbf{1}\\!\left\\{\widehat{y}\neq y\right\\}$. We present Algorithm 2 that
achieves regret $\widetilde{O}(\sqrt{{Td}{\sigma^{-{1}/{2}}}})$ with better
dependence on the smoothness parameter $\sigma$ compared to Algorithm 1.

This algorithm which is based on the the Follow-the-Perturbed-Leader (FTPL)
framework differs from the hint-based algorithm in two ways. First, instead of
accessing the ERM oracle twice and making a randomized decision at each round,
the new algorithm only calls the ERM oracle once and follows the prediction of
the output. Second, and importantly, the number of self-generated hints does
not shrink over time and follows an appropriate probability distribution (such
as Poisson). This _Poissonization_ is the key to establishing improved
stability of the algorithm.

A detailed description of the algorithm is illustrated below. At a high level,
at each time step the learner generates $N\sim\text{Poi}(n)$ to represent the
total number of self-generated hints it will be feeding itself, and then takes
$N$ samples $\widetilde{x}_{i}\sim\mathcal{U}(\mathcal{X})$, each labeled
independently by a Rademacher variable $\widetilde{y}_{i}$. The learner then
uses the ERM oracle on the history of the play so far and the hints to compute
a hypothesis $h_{t}$, which it uses for its prediction
$\widehat{y}_{t}=h_{t}(x_{t})$ at time $t$.

Input: time horizon $T$, smoothness parameter $\sigma$, VC dimension $d$

1 $n\leftarrow\min\\{T/\sqrt{\sigma},T\sqrt{|\mathcal{X}|/d}\\}$;

2 for  _$t\leftarrow 1$ to $T$_ do

3 generate $N^{(t)}\sim\text{Poi}(n)$ fresh hallucinated samples
$(\widetilde{x}_{1}^{(t)},\widetilde{y}_{1}^{(t)}),\cdots,(\widetilde{x}_{N}^{(t)},\widetilde{y}_{N}^{(t)})$,
which are i.i.d. conditioned on $N$ with
$\widetilde{x}_{i}^{(t)}\sim\mathcal{U}(\mathcal{X})$ and
$\widetilde{y}_{i}^{(t)}\sim\mathcal{U}(\\{\pm 1\\})$;

4 call the ERM oracle to compute
$h_{t}\leftarrow\mathsf{opt}_{\mathcal{H},l}\left(\\{(\widetilde{x}_{i}^{(t)},\widetilde{y}_{i}^{(t)})\\}_{i\in[N^{(t)}]}\cup\\{x_{\tau},y_{\tau}\\}_{\tau\in[t-1]}\right)$;

5 observe $x_{t}$, predict $\widehat{y}_{t}=h_{t}(x_{t})$, and receive
$y_{t}$.

6 end for

Algorithm 2 Smoothed Online Binary Classification based on Poisson Number of
Hints

In the remainder of this section, we present a proof of the regret upper bound
$\widetilde{O}(\sqrt{dT\sigma^{-1/2}})$ in Theorem 4.2 when $\sigma\geq
d/|\mathcal{X}|$. The proof of the other case $\sigma<d/|\mathcal{X}|$ is
slightly different and will be presented in Section 4.2.3. Similar to Section
3, we will provide a relaxation-based upper bound for the regret of Algorithm
2. Writing $s=(x,y)$ and $L(h,s)=l(h(x),y)=-yh(x)/2$, the relaxation is
defined as

$\displaystyle\textbf{Rel}_{T}(\mathcal{H}\mid s_{1\mathrel{\mathop{\mathchar
58\relax}}t})=\operatorname*{\mathbb{E}}_{R^{(t+1)}}\left[\sup_{h\in\mathcal{H}}\left(-\sum_{i=1}^{N^{(t+1)}}L(h,\widetilde{s}_{i}^{\,(t+1)})-\sum_{\tau=1}^{t}L(h,s_{\tau})\right)\right]+\eta(T-t),$
(13)

where

$\displaystyle\eta=\frac{1}{\sqrt{n\sigma}}+c\sqrt{\frac{d\log
T}{n\sigma}}+\frac{n\sigma}{4T^{2}\log
T}+e^{-n/8}\in\widetilde{O}\left(\sqrt{\frac{d}{n\sigma}}\right),$ (14)

with an absolute constant $c>0$ given in Lemma 4.6 later, and
$R^{(t)}=(N^{(t)},\\{\widetilde{s}_{i}\\}_{i\in N^{(t)}})$ is the fresh
randomness generated at the beginning of time $t$, which is independent of
$\\{s_{\tau}\\}_{\tau<t}$ generated by the adversary. The relaxation here is
similar to Equation 8 in the transductive setting, where the key difference is
a different generation process for the hint set and an additional term
$\eta(T-t)$ to account for the stability.

Let $\mathcal{Q}_{t}$ be the distribution of the learner’s action
$h_{t}\in\mathcal{H}$ in Algorithm 2, then the relaxation in Equation 13 is
admissible with respect to Algorithm 2 if the following two conditions hold:

$\displaystyle\sup_{\mathcal{D}_{t}\in\Delta_{\sigma}(\mathcal{X})}\operatorname*{\mathbb{E}}_{x_{t}\sim\mathcal{D}_{t}}\sup_{y_{t}}\left[\operatorname*{\mathbb{E}}_{h_{t}\sim\mathcal{Q}_{t}}[L(h_{t},s_{t})]+\textbf{Rel}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar 58\relax}}t})\right]$
$\displaystyle\leq\textbf{Rel}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar 58\relax}}t-1}),\quad\forall
s_{1\mathrel{\mathop{\mathchar 58\relax}}t-1}$ (15)
$\displaystyle\textbf{Rel}_{T}(\mathcal{H}\mid s_{1\mathrel{\mathop{\mathchar
58\relax}}T})$
$\displaystyle\geq-\inf_{h\in\mathcal{H}}L(h,s_{1\mathrel{\mathop{\mathchar
58\relax}}T}).$ (16)

According to Proposition 2.1, if both Equations 15 and 16 hold, the expected
regret of Algorithm 2 will satisfy

$\displaystyle\operatorname*{\mathbb{E}}[\textsc{Regret}(T)]$
$\displaystyle\leq\textbf{Rel}_{T}(\mathcal{H}\mid\emptyset)+O(\sqrt{T})=\operatorname*{\mathbb{E}}_{R^{(1)}}\left[\sup_{h\in\mathcal{H}}\left(-\sum_{i=1}^{N^{(1)}}L(h,\widetilde{s}_{i}^{\,(1)})\right)\right]+\eta
T+O(\sqrt{T})$ (17)
$\displaystyle\overset{\rm(a)}{=}O\left(\operatorname*{\mathbb{E}}_{N^{(1)}}\left[\sqrt{dN^{(1)}}\right]+\eta
T+\sqrt{T}\right)\overset{\rm(b)}{=}O\left(\sqrt{dn}+\eta T+\sqrt{T}\right),$
(18)

and Theorem 4.2 follows from the choices $n=T/\sqrt{\sigma}$ and
$\eta=O(\sqrt{d/n\sigma})$. In the above inequality, step (a) follows from
random labels and the upper bound $O(\sqrt{nd})$ on the Rademacher complexity
of $\mathcal{H}$ over $n$ points, and step (b) is due to Jensen’s inequality
and $\operatorname*{\mathbb{E}}[N^{(1)}]=n$.

Now it remains to verify Equations 15 and 16. It is not hard to verify
Equation 16: this follows from the fact that for any random variable
$\lambda$,
$\operatorname*{\mathbb{E}}[\sup_{\lambda}X_{\lambda}]\geq\sup_{\lambda}\operatorname*{\mathbb{E}}[X_{\lambda}]$
and $\operatorname*{\mathbb{E}}_{R}[L(h,\widetilde{s}_{i})]=0$. The key
technical difficulty is in the proof of Equation 15. To overcome this
challenge, we first draw a parallel between two types of analysis in online
learning, by showing that the _stability_ of learner’s distribution
$\mathcal{Q}_{t}$ implies the admissibility of the relaxation, where the
stability is measured via

$\text{Stability}=\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}(\operatorname*{\mathbb{E}}_{h_{t}\sim\mathcal{Q}_{t}}[L(h_{t},s_{t})]-\operatorname*{\mathbb{E}}_{h_{t+1}\sim\mathcal{Q}_{t+1}}[L(h_{t+1},s_{t})]).$

Note that here $s_{t}\sim\mathcal{D}_{t}$ denotes both the instance and its
label and $\mathcal{D}_{t}$’s marginal over $\mathcal{X}$ is $\sigma$-smooth.
We further upper bound stability (see Lemma 4.4) as follows:

$\text{Stability}\leq\text{\rm
TV}(\mathcal{Q}_{t},\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}[\mathcal{Q}_{t+1}])+\operatorname*{\mathbb{E}}_{s_{t},s_{t}^{\prime}\sim\mathcal{D}_{t};R^{(t+1)}}[L(h_{t+1},s_{t}^{\prime})-L(h_{t+1},s_{t})].$

Let us first describe the two terms in this bound further. The first term is
the total variation (TV) distance between $\mathcal{Q}_{t}$ and the mixture
distribution
$\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}[\mathcal{Q}_{t+1}]$.
Note that this TV distance would be an upper bound on the stability by itself,
if neither of $\mathcal{Q}_{t}$ and $\mathcal{Q}_{t+1}$ depend on the new
observation $s_{t}=(x_{t},y_{t})$ at time $t$. However, while
$\mathcal{Q}_{t}$ is independent of $s_{t}$, $h_{t+1}$ is trained on $s_{t}$
and thus distribution $\mathcal{Q}_{t+1}$ does depend on $s_{t}$. To overcome
this dependence, we introduce a ghost sample $s_{t}^{\prime}$ that allows us
to decouple $h_{t+1}\sim\mathcal{Q}_{t+1}$ and the new observation. This gives
rise to the second term which is a _modified generalization error_. In other
words, let $s_{t}^{\prime}$ be an independent copy of $s_{t}$ conditioned on
$s_{1\mathrel{\mathop{\mathchar 58\relax}}t-1}$. The expected loss of the
classifier $h_{t+1}$, which is trained on $s_{t}$ but not $s_{t}^{\prime}$, on
the ghost sample $s_{t}^{\prime}$ is denoted by
$\operatorname*{\mathbb{E}}_{s_{t},s_{t}^{\prime}\sim\mathcal{D}_{t};R^{(t+1)}}[L(h_{t+1},s_{t}^{\prime})].$
The expectation here is understood in the sense that ERM classifier $h_{t+1}$
is determined by the self-generated samples, the current observation $s_{t}$,
and the history $s_{1},\cdots,s_{t-1}$ (which are held fixed). The
generalization error is then defined to be the expected difference

$\text{Modified generalization error}\mathrel{\mathop{\mathchar
58\relax}}=\operatorname*{\mathbb{E}}_{s_{t},s_{t}^{\prime}\sim\mathcal{D}_{t};R^{(t+1)}}[L(h_{t+1},s_{t}^{\prime})-L(h_{t+1},s_{t})].$

The following lemma formalizes this discussion and shows that a small TV
distance and generalization error suffice to ensure the stability of the
algorithm, which in turn implies the admissibility of the relaxation. This
result could be of independent interest. The proof can be found in Section
E.2.

######  Lemma 4.4 (TV + Generalization $\Rightarrow$ Stability $\Rightarrow$
Admissibility).

Let $\mathcal{Q}_{t}$ denote learner’s distribution over $\mathcal{H}$ in
Algorithm 2 at round $t$, $\mathcal{D}_{t}$ be adversary’s distribution at
time $t$ (given the history $s_{1},\cdots,s_{t-1}$),
$s_{t}\sim\mathcal{D}_{t}$ be the realized adversarial instance at time $t$,
and $s_{t}^{\prime}$ be an independent copy
$s^{\prime}_{t}\sim\mathcal{D}_{t}$. It holds that

$\displaystyle\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}\left(\operatorname*{\mathbb{E}}_{h_{t}\sim\mathcal{Q}_{t}}[L(h_{t},s_{t})]+\emph{{Rel}}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar
58\relax}}t})\right)-\emph{{Rel}}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar 58\relax}}t-1})$ (19)
$\displaystyle\leq\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}\left(\operatorname*{\mathbb{E}}_{h_{t}\sim\mathcal{Q}_{t}}[L(h_{t},s_{t})]-\operatorname*{\mathbb{E}}_{h_{t+1}\sim\mathcal{Q}_{t+1}}[L(h_{t+1},s_{t})]\right)-\eta$
(20) $\displaystyle\leq\text{\rm
TV}(\mathcal{Q}_{t},\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}[\mathcal{Q}_{t+1}])+\operatorname*{\mathbb{E}}_{s_{t},s_{t}^{\prime}\sim\mathcal{D}_{t};R^{(t+1)}}[L(h_{t+1},s_{t}^{\prime})-L(h_{t+1},s_{t})]-\eta.$
(21)

Lemma 4.4 shows that, in order to prove the admissibility of the relaxation in
Equation 13, it remains to upper bound the TV distance and the generalization
error, respectively.

To upper bound the TV distance, we shall convert $\mathcal{Q}_{t}$ to a
simpler distribution to work with. For $t\in[T]\cup\\{0\\}$, let
$r^{t}\in\mathbb{Z}^{\mathcal{X}}$ be the $|\mathcal{X}|$-dimensional random
vector with $r^{t}(x)$ defined to be the difference between the number of $+1$
and $-1$ labels in the self-generated samples and the history up to time $t$
on instance $x$. Formally,

$\displaystyle
r^{t}(x)=\sum_{i=1}^{N^{(t+1)}}\widetilde{y}_{i}^{\,(t+1)}\cdot\mathbf{1}(\widetilde{x}_{i}^{\,(t+1)}=x)+\sum_{\tau=1}^{t}y_{\tau}\cdot\mathbf{1}(x_{\tau}=x).$
(22)

Let $\mathcal{P}^{t}$ be the distribution of $r^{t}$. The reason why we
introduce this notion is that $h_{t}$ in Algorithm 2 only depends on the
vector $r^{t-1}$, so the ERM objective could be written as a quantity
depending only on $r^{t-1}$ and $h\in\mathcal{H}$. We write
$h_{t}=\mathsf{opt}_{\mathcal{H},l}(r^{t-1})$ in the sequel, and then
$\mathsf{opt}_{\mathcal{H},l}(r^{t-1})\sim\mathcal{Q}_{t}$ as
$r^{t-1}\sim\mathcal{P}^{t-1}$. Therefore, the data-processing inequality
shows that

$\displaystyle\text{TV}(\mathcal{Q}_{t},\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}[\mathcal{Q}_{t+1}])\leq\text{TV}(\mathcal{P}^{t-1},\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}[\mathcal{P}^{t}]),$
(23)

and the following lemma provides an upper bound on the TV distance
$\text{TV}(\mathcal{P}^{t-1},\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}[\mathcal{P}^{t}])$.

######  Lemma 4.5 (Upper Bound of TV Distance).

Let $\mathcal{P}^{t}$ be the distribution over $r^{t}$ defined above. We have

$\displaystyle\sup_{\mathcal{D}_{t}\in\Delta_{\sigma}(\mathcal{S})}\text{\rm
TV}(\mathcal{P}^{t-1},\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}[\mathcal{P}^{t}])\leq\frac{1}{\sqrt{n\sigma}}.$
(24)

The key ingredient in the proof of Lemma 4.5 is the Poissonization, which
ensures the independence across the coordinates of $r^{t}$ and enables us to
write down the mixture distribution
$\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}[\mathcal{P}^{t}]$ in a
compact form. The proof of Lemma 4.5 is presented in Section 4.2.1.

The following lemma upper bounds the generalization error for any smooth
distribution $\mathcal{D}_{t}$.

######  Lemma 4.6 (Upper Bound of Generalization Error).

Under the notations of Lemma 4.4, it holds for an absolute constant $c>0$
(independent of $(n,d,T,\sigma)$) that

$\displaystyle\sup_{\mathcal{D}_{t}\in\Delta_{\sigma}(\mathcal{X})}\left\\{\operatorname*{\mathbb{E}}_{s_{t},s_{t}^{\prime}\sim\mathcal{D}_{t};R^{(t+1)}}\left[L(h_{t+1},s_{t}^{\prime})-L(h_{t+1},s_{t})\right]\right\\}\leq
c\sqrt{\frac{d\log T}{n\sigma}}+\frac{n\sigma}{4T^{2}\log T}+e^{-n/8}.$ (25)

The intuitive idea behind Lemma 4.6 is as follows. Consider the simpler
setting of $t=1$ (i.e. no history) and
$\mathcal{D}_{t}=\mathcal{U}(\mathcal{X}\times\\{\pm 1\\})$ (i.e. the new
observation $s_{t}$ follows the same distribution as the self-generated
samples). In this case, the generalization error is precisely the difference
between the test error and the training error with $N+1$ iid training data,
and classical Rademacher complexity gives an upper bound $O(\sqrt{d/n})$. For
general $\sigma$-smooth $\mathcal{D}_{t}$, a coupling argument essentially
shows that $n$ iid training data from $\mathcal{U}(\mathcal{X}\times\\{\pm
1\\})$ contain $n\sigma$ iid training data from $\mathcal{D}_{t}$, and
replacing $n$ by $n\sigma$ in the previous upper bound gives Lemma 4.6. The
rigorous treatment of the coupling and all details are presented in Section
4.2.2.

Now the claimed result of Theorem 4.2 when $\sigma\geq d/|\mathcal{X}|$
follows from Lemma 4.4, Lemma 4.5, and Lemma 4.6.

####  4.2.1 Upper Bounding TV Distance: Proof of Lemma 4.5

Let us first create a better understanding of the structures of the
distributions $\mathcal{P}^{t-1}$ and $\mathcal{P}^{t}$. Without loss of
generality we assume that $\mathcal{X}$ is discrete (the case of continuous
$\mathcal{X}$ can be dealt by analyzing the appropriate Poisson point
process). Let $n_{+}(x),n_{-}(x)$ be the numbers of $+1$ and $-1$ labels,
respectively, given instance $x$ in the self-generated samples:

$n_{+}(x)=\sum_{i=1}^{N}\mathbf{1}(\widetilde{x}_{i}=x,\widetilde{y}_{i}=+1)~{}~{}\text{
and
}~{}~{}n_{-}(x)=\sum_{i=1}^{N}\mathbf{1}(\widetilde{x}_{i}=x,\widetilde{y}_{i}=-1).$

As each $\widetilde{x}_{i}$ is uniformly distributed on $\mathcal{X}$ and
$\widetilde{y}_{i}\sim\mathcal{U}(\\{\pm 1\\})$, by the subsampling property
of the Poisson distribution, the $2|\mathcal{X}|$ random variables
$\\{n_{\pm}(x)\\}_{x\in\mathcal{X}}$ are i.i.d. distributed as
$\text{Poi}(n/2|\mathcal{X}|)$. This independence implied by the Poisson
distribution plays a key role in the analysis. Moreover,
$r^{0}(x)=n_{+}(x)-n_{-}(x)$, so $\mathcal{P}^{0}$ is determined by the joint
distribution of $\\{n_{\pm}(x)\\}_{x\in\mathcal{X}}$.

As we move to general $t$, note that the only contribution of the historic
data $\\{s_{\tau}\\}_{\tau<t}$ to both $\mathcal{P}^{t-1}$ and
$\mathcal{P}^{t}$ is a common translation independent of $\mathcal{P}^{0}$.
Since the TV distance is translation invariant, it suffices to upper bound
$\text{TV}(\mathcal{P}^{0},\operatorname*{\mathbb{E}}_{s_{1}}[\mathcal{P}^{1}])$.
Let $n_{\pm}^{1}(x)=n_{\pm}(x)+\mathbf{1}(x_{1}=x,y_{1}=\pm 1)$, it holds that
$r^{1}(x)=n_{+}^{1}(x)-n_{-}^{1}(x)$. Consequently, let $P$ and $Q$ be the
probability distributions of $\\{n_{\pm}(x)\\}_{x\in\mathcal{X}}$ and
$\\{n_{\pm}^{1}(x)\\}_{x\in\mathcal{X}}$, respectively, the data-processing
inequality implies that
$\text{TV}(\mathcal{P}^{0},\operatorname*{\mathbb{E}}_{s_{1}}[\mathcal{P}^{1}])\leq\text{TV}(P,Q)$.

As discussed above, the distribution $P$ is a product Poisson distribution:

$\displaystyle
P(\\{n_{\pm}(x)\\})=\prod_{x\in\mathcal{X}}\prod_{y\in\\{\pm\\}}\mathbb{P}(\text{Poi}(n/2|\mathcal{X}|)=n_{y}(x)).$
(26)

As for the distribution $Q$, it could be obtained from $P$ in the following
way: the smooth adversary draws $x^{\star}\sim\mathcal{D}$, independent of
$\\{n_{\pm}(x)\\}_{x\in\mathcal{X}}\sim P$, for some $\sigma$-smooth
distribution $\mathcal{D}\in\Delta_{\sigma}(\mathcal{X})$. He then chooses a
label $y^{\star}=y(x^{\star})\in\\{\pm 1\\}$ as a function of $x^{\star}$, and
sets

$\displaystyle
n_{y(x^{\star})}^{1}(x^{\star})=n_{y(x^{\star})}(x^{\star})+1,\qquad\text{and}\qquad
n_{y}^{1}(x)=n_{y}(x),\quad\forall(x,y)\neq(x^{\star},y(x^{\star})).$ (27)

Consequently, given a $\sigma$-smooth distribution $\mathcal{D}$ and a
labeling function $y\mathrel{\mathop{\mathchar
58\relax}}\mathcal{X}\to\\{\pm\\}$ used by the adversary, the distribution $Q$
is a mixture distribution
$Q=\operatorname*{\mathbb{E}}_{x^{\star}\sim\mathcal{D}^{\mathcal{X}}}[Q_{x^{\star}}]$,
with

$\displaystyle
Q_{x^{\star}}(\\{n_{\pm}(x)\\})=\mathbb{P}(\text{Poi}(n/2|\mathcal{X}|)=n_{y(x^{\star})}(x^{\star})-1)\times\prod_{(x,y)\neq(x^{\star},y(x^{\star}))}\mathbb{P}(\text{Poi}(n/2|\mathcal{X}|)=n_{y}(x)).$
(28)

To upper bound the TV distance between a mixture distribution $Q$ and a base
distribution $P$, we will rely on the smoothness properties of $\mathcal{D}$,
in particular, that the probability of collision between two independent draws
$x_{1}^{\star},x_{2}^{\star}\sim\mathcal{D}$ is small. To formally address
this, we make use of two technical lemmas, first to upperbound the TV distance
in terms of the $\chi^{2}$ distance, and second to use the Ingster’s method
for bounding the $\chi^{2}$ distance between a mixture distribution and a base
distribution. See Lemma E.1 and Lemma E.2 in the Section E.1 for more details.
Let $x_{1}^{\star},x_{2}^{\star}$ be an arbitrary pair of instance. Using the
closed-form expressions of distributions $P$ and $Q_{x^{\star}}$, it holds
that

$\displaystyle\frac{Q_{x_{1}^{\star}}(\\{n_{\pm}(x)\\})Q_{x_{2}^{\star}}(\\{n_{\pm}(x)\\})}{P(\\{n_{\pm}(x)\\})^{2}}=\frac{2|\mathcal{X}|n_{y(x_{1}^{\star})}(x_{1}^{\star})}{n}\cdot\frac{2|\mathcal{X}|n_{y(x_{2}^{\star})}(x_{2}^{\star})}{n}.$
(29)

Using the fact that $\\{n_{\pm}(x)\\}_{x\in\mathcal{X}}$ are i.i.d.
distributed as $\text{Poi}(n/2|\mathcal{X}|)$ under $P$, we have

$\displaystyle\operatorname*{\mathbb{E}}_{\\{n_{\pm}(x)\\}\sim
P}\left(\frac{Q_{x_{1}^{\star}}(\\{n_{\pm}(x)\\})Q_{x_{2}^{\star}}(\\{n_{\pm}(x)\\})}{P(\\{n_{\pm}(x)\\})^{2}}\right)=1+\frac{2|\mathcal{X}|}{n}\cdot\mathbf{1}(x_{1}^{\star}=x_{2}^{\star}).$
(30)

Now using the aforementioned lemmas (Lemma E.1 and Lemma E.2), we have

$\displaystyle\text{TV}(P,Q)$
$\displaystyle\leq\sqrt{\frac{\chi^{2}(Q,P)}{2}}=\sqrt{\frac{\chi^{2}(\operatorname*{\mathbb{E}}_{x^{\star}\sim\mathcal{D}}[Q_{x^{\star}}],P)}{2}}=\sqrt{\frac{|\mathcal{X}|}{n}\cdot\operatorname*{\mathbb{E}}_{x_{1}^{\star},x_{2}^{\star}\sim\mathcal{D}}[\mathbf{1}(x_{1}^{\star}=x_{2}^{\star})]}$
(31)
$\displaystyle=\sqrt{\frac{|\mathcal{X}|}{n}\sum_{x\in\mathcal{X}}\mathcal{D}(x)^{2}}\overset{\rm(a)}{\leq}\sqrt{\frac{|\mathcal{X}|}{n}\sum_{x\in\mathcal{X}}\mathcal{D}(x)\cdot\frac{1}{\sigma|\mathcal{X}|}}=\frac{1}{\sqrt{\sigma
n}},$ (32)

where (a) follows from the definition of a $\sigma$-smooth distribution. This
completes the proof.

####  4.2.2 Upper Bounding Generalization Error: Proof of Lemma 4.6

In the proof of Lemma 4.6, we shall need the following property of smooth
distributions which is a slightly strengthened version of the coupling lemma
in Lemma D.1.

######  Lemma 4.7.

Let $X_{1},\cdots,X_{m}\sim Q$ and $P$ be another distribution with a bounded
likelihood ratio: $dP/dQ\leq 1/\sigma$. Then using external randomness $R$,
there exists an index $I=I(X_{1},\cdots,X_{m},R)\in[m]$ and a success event
$E=E(X_{1},\cdots,X_{m},R)$ such that $\Pr[E^{c}]\leq(1-\sigma)^{m}$, and

$\displaystyle(X_{I}\mid E,X_{\backslash I})\sim P.$ (33)

Fix any realization of the Poissonized sample size $N\sim\text{Poi}(n)$.
Choose $m=4\sigma^{-1}\log T$ in Lemma 4.7, and without loss of generality
assume that $N$ is an integral multiple of $m$. Since for any $\sigma$-smooth
$\mathcal{D}_{t}$, it holds that

$\displaystyle\frac{\mathcal{D}_{t}(s)}{\mathcal{U}(\mathcal{X}\times\\{\pm
1\\})(s)}=\frac{\mathcal{D}_{t}(x)}{\mathcal{U}(\mathcal{X})(x)}\cdot\frac{\mathcal{D}_{t}(y\mid
x)}{\mathcal{U}(\\{\pm 1\\})(y)}\leq\frac{2}{\sigma},$ (34)

the premise of Lemma 4.7 holds with parameter $\sigma/2$ for
$P=\mathcal{D}_{t},Q=\mathcal{U}(\mathcal{X}\times\\{\pm 1\\})$. Consequently,
dividing the self-generated samples
$\widetilde{s}_{1},\cdots,\widetilde{s}_{N}$ into $N/m$ groups each of size
$m$, and running the procedure in Lemma 4.7, we arrive at $N/m$ independent
events $E_{1},\cdots,E_{N/m}$, each with probability at least
$1-(1-\sigma/2)^{m}\geq 1-T^{-2}$. Moreover, conditioned on each $E_{j}$, we
can pick an element
$u_{j}\in\\{\widetilde{s}_{(j-1)m+1},\cdots,\widetilde{s}_{jm}\\}$ such that

$\displaystyle(u_{j}\mid
E_{j},\\{\widetilde{s}_{(j-1)m+1},\cdots,\widetilde{s}_{jm}\\}\backslash\\{u_{j}\\})\sim\mathcal{D}_{t}.$
(35)

For notational simplicity we denote the set of unpicked samples
$\\{\widetilde{s}_{(j-1)m+1},\cdots,\widetilde{s}_{jm}\\}\backslash\\{u_{j}\\}$
by $v_{j}$. As a result, thanks to the mutual independence of different groups
and $s_{t}\sim\mathcal{D}_{t}$ conditioned on $s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}$ (note that we draw fresh randomness at every round), for
$E\triangleq\cap_{j\in[N/m]}E_{j}$ we have

$\displaystyle(u_{1},\cdots,u_{N/m},s_{t})\mid(E,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1},v_{1},\cdots,v_{N/m})\overset{\text{iid}}{\sim}\mathcal{D}_{t}.$
(36)

Consequently, for each $j\in[N/m]$ we have

$\displaystyle\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t},R^{(t+1)}}[L(h_{t+1},s_{t})\mid
E]$ (37)
$\displaystyle=\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t},\widetilde{s}_{1},\cdots,\widetilde{s}_{N}}\left[L(\mathsf{opt}(\widetilde{s}_{1},\cdots,\widetilde{s}_{N},s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1},s_{t}),s_{t})\mid E\right]$ (38)
$\displaystyle=\operatorname*{\mathbb{E}}_{v,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}\mid
E}\left(\operatorname*{\mathbb{E}}_{s_{t},u_{1},\cdots,u_{N/m}}\left[L(\mathsf{opt}(s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1},v,u_{1},\cdots,u_{N/m},s_{t}),s_{t})\mid
E,s_{1\mathrel{\mathop{\mathchar 58\relax}}t-1},v\right]\right)$ (39)
$\displaystyle\overset{\rm(a)}{=}\operatorname*{\mathbb{E}}_{v,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}\mid
E}\left(\operatorname*{\mathbb{E}}_{s_{t},u_{1},\cdots,u_{N/m}}\left[L(\mathsf{opt}(s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1},v,u_{1},\cdots,u_{j-1},s_{t},u_{j+1},\cdots,u_{N/m},u_{j}),u_{j})\mid
E,s_{1\mathrel{\mathop{\mathchar 58\relax}}t-1},v\right]\right)$ (40)
$\displaystyle\overset{\rm(b)}{=}\operatorname*{\mathbb{E}}_{v,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}\mid
E}\left(\operatorname*{\mathbb{E}}_{s_{t},u_{1},\cdots,u_{N/m}}[L(\mathsf{opt}(s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1},v,u_{1},\cdots,u_{N/m},s_{t}),u_{j})\mid
E,s_{1\mathrel{\mathop{\mathchar 58\relax}}t-1},v]\right)$ (41)
$\displaystyle=\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t},R^{(t+1)}}[L(h_{t+1},u_{j})\mid
E],$ (42)

where (a) follows from the conditional iid (and thus exchangeable) property of
$(u_{1},\cdots,u_{N/m},s_{t})$ after the conditioning, and (b) is due to the
invariance of the ERM output after any permutation of the inputs. On the other
hand, if $s_{t}^{\prime},u_{1}^{\prime},\cdots,u_{N/m}^{\prime}$ are
independent copies of $s_{t}\sim\mathcal{D}_{t}$, by independence it is clear
that

$\displaystyle\operatorname*{\mathbb{E}}_{s_{t},s_{t}^{\prime}\sim\mathcal{D}_{t},R^{(t+1)}}[L(h_{t+1},s_{t}^{\prime})\mid
E]=\operatorname*{\mathbb{E}}_{s_{t},s_{t}^{\prime}\sim\mathcal{D}_{t},R^{(t+1)}}[L(h_{t+1},u_{j}^{\prime})\mid
E],\quad\forall j\in[N/m].$ (43)

Consequently, using the shorthand $u_{0}=s_{t},u_{0}^{\prime}=s_{t}^{\prime}$,
we have

$\displaystyle\operatorname*{\mathbb{E}}_{s_{t},s_{t}^{\prime}\sim\mathcal{D}_{t},R^{(t+1)}}[L(h_{t+1},s_{t}^{\prime})-L(h_{t+1},s_{t})\mid
E]$ (44)
$\displaystyle=\frac{1}{N/m+1}\operatorname*{\mathbb{E}}_{s_{t},s_{t}^{\prime}\sim\mathcal{D}_{t},R^{(t+1)}}\left[\sum_{j=0}^{N/m}(L(h_{t+1},u_{j}^{\prime})-L(h_{t+1},u_{j}))~{}\bigg{|}~{}E\right]$
(45)
$\displaystyle\leq\frac{1}{N/m+1}\operatorname*{\mathbb{E}}_{u_{0},\cdots,u_{N/m},u_{0}^{\prime},\cdots,u_{N/m}^{\prime}\sim\mathcal{D}_{t}}\left[\sup_{h\in\mathcal{H}}\sum_{j=0}^{N/m}(L(h,u_{j}^{\prime})-L(h,u_{j}))\right]$
(46)
$\displaystyle\leq\frac{2}{N/m+1}\operatorname*{\mathbb{E}}_{u_{0},\cdots,u_{N/m}\sim\mathcal{D}_{t}}\operatorname*{\mathbb{E}}_{\epsilon_{1}\dots\epsilon_{N/m}}\left[\sup_{h\in\mathcal{H}}\sum_{j=0}^{N/m}\epsilon_{j}h(u_{j})\right]\leq
c_{0}\sqrt{\frac{d}{N/m+1}},$ (47)

where the last inequality is due to the classical $O(\sqrt{d/n})$ upper bound
on the Rademacher complexity, and $c_{0}>0$ in an absolute constant. Note that
the union bound gives

$\displaystyle\Pr[E^{c}]\leq\sum_{j=1}^{N/m}\Pr[E_{j}^{c}]\leq\frac{N}{mT^{2}},$
(48)

the law of total expectation gives

$\displaystyle\operatorname*{\mathbb{E}}_{s_{t},s_{t}^{\prime}\sim\mathcal{D}_{t},R^{(t+1)}}[L(h_{t+1},s_{t}^{\prime})-L(h_{t+1},s_{t})]$
(49)
$\displaystyle\leq\operatorname*{\mathbb{E}}_{s_{t},s_{t}^{\prime}\sim\mathcal{D}_{t},R^{(t+1)}}[L(h_{t+1},s_{t}^{\prime})-L(h_{t+1},s_{t})\mid
E]+\Pr[E^{c}]\leq c_{0}\sqrt{\frac{d}{N/m+1}}+\frac{N}{mT^{2}}.$ (50)

Finally, plugging the choice of $m=4\sigma^{-1}\log T$, taking the expectation
of $N\sim\text{Poi}(n)$, and using $\Pr[N>n/2]\geq 1-e^{-n/8}$ in the above
inequality completes the proof of Lemma 4.6.

####  4.2.3 Completing the Proof of Theorem 4.2

In this section we complete the proof of the
$O(\sqrt{T(d|\mathcal{X}|)^{1/2}})$ upper bound in Theorem 4.2 when
$\sigma<d/|\mathcal{X}|$ (and thus $n=T\sqrt{|\mathcal{X}|/d}$). The proof is
still through the same relaxation in Equation 13, though we will choose a
different parameter $\eta$ and prove a slightly modified version of Lemma 4.4:

######  Lemma 4.8 (Expected TV $\Rightarrow$ Admissibility).

Let $\mathcal{Q}_{t}$ denote learner’s distribution over $\mathcal{H}$ in
Algorithm 2 at round $t$, and $s_{t}\sim\mathcal{D}_{t}$ be the conditional
distribution of $s_{t}$ given the history $s_{1},\cdots,s_{t-1}$. It holds
that

$\displaystyle\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}\left(\operatorname*{\mathbb{E}}_{h_{t}\sim\mathcal{Q}_{t}}[L(h_{t},s_{t})]+\emph{{Rel}}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar
58\relax}}t})\right)-\emph{{Rel}}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1})\leq\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}[\text{\rm
TV}(\mathcal{Q}_{t},\mathcal{Q}_{t+1})]-\eta.$ (51)

Note that in Lemma 4.8, the expectation is outside the TV distance and no
smaller than the TV distance when the mixture distribution is inside the
expectation compared with Lemma 4.4. We can simply upper bound this expected
TV distance, with the worst case choice of $s_{t}$ and apply the data
processing inequality, i.e.,

$\displaystyle\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}[\text{\rm
TV}(\mathcal{Q}_{t},\mathcal{Q}_{t+1})]\leq\sup_{s_{t}}\text{TV}(\mathcal{P}^{t-1},\mathcal{P}^{t}).$
(52)

Using the similar independence property of Poissonization in Section 4.2.1,
the target TV distance is at most $\text{TV}(P,Q)$, where
$P\sim\text{Poi}(n/2|\mathcal{X}|)$, and $Q$ is a right-translation of $P$ by
one. Consequently,

$\displaystyle\text{TV}(P,Q)\leq\sqrt{\frac{\chi^{2}(Q,P)}{2}}=\sqrt{\frac{1}{2}\left(\operatorname*{\mathbb{E}}_{X\sim
P}\left[\left(\frac{X}{n/2|\mathcal{X}|}\right)^{2}\right]-1\right)}=\sqrt{\frac{|\mathcal{X}|}{n}},$
(53)

so the choice of $\eta=\sqrt{|\mathcal{X}|/n}$ and Lemma 4.8 again makes the
relaxation in Equation 13 admissible, and we complete the proof of Theorem
4.2.

##  5 Discussion, Additional Results, and Open Problems

##### Computational Lower Bounds.

Our main contribution is oracle-efficient algorithms that achieve an
$O(\sqrt{dTK})$ regret upper bound for $K$-hint transductive learning, an
$O(\sqrt{dT\sigma^{-1}})$ regret upper bound in the real-valued case of
smoothed online learning, and an $O(\sqrt{dT\sigma^{-1/2}})$ upper bound for
smoothed online binary classification. However, neither of these upper bounds
is statistically optimal; the statistically optimal regrets for these
scenarios are $\widetilde{\Theta}(\sqrt{dT\log K})$ and
$\widetilde{\Theta}(\sqrt{dT\log(1/\sigma)})$ [HRS22], respectively. We ask
the following question: is the above discrepancy an artifact of our regret
analysis, or an intrinsic limitation of our or all oracle-efficient
algorithms.

We show that no matter how we tune the parameters in Algorithm 2 and Algorithm
3, a lower bound $\Omega(\sqrt{dT\sigma^{-1/2}})$ or
$\Omega(\sqrt{dTK^{1/2}})$ is unavoidable for these algorithms in the
respective scenarios. In other words, our regret upper bound in Theorem 4.2 is
tight, and there is an $O(K^{1/4})$ gap compared to the upper bound of Theorem
3.1; importantly, neither algorithm could achieve the logarithmic dependence
on $1/\sigma$ or $K$ in the statistical upper bound. Formally, by parameter
tuning, we mean any choice of the parameter $n$ in Algorithm 2, and any number
$n$ of uniform samples from the $K$-hint set in Algorithm 3. The next theorem
formally states the lower bounds.

######  Theorem 5.1 (Limitations of Algorithms).

For any choice of the parameter $n$ in Algorithm 2, there exists a
$\sigma$-smoothed online learning instance such that Algorithm 2 suffers from
at least
$\Omega(\min\\{T,\sqrt{dT\sigma^{-1/2}},\sqrt{T(d|\mathcal{X}|)^{1/2}}\\})$
expected regret.

Similarly, for any choice of the parameter $n$ in Algorithm 3, there exists a
$K$-hint transductive instance such that Algorithm 3 incurs at least
$\Omega(\min\\{T,\sqrt{dTK^{1/2}}\\})$ expected regret.

For general efficient algorithms, we have the following computational lower
bound for smoothed online learning following similar ideas to [HK16].

######  Theorem 5.2 (Computational Lower Bound for Smoothed Online Learning).

For $1/\sigma\geq d$, any proper algorithm which only has access to the ERM
oracle and achieves a regret $o(\min\\{T,\sqrt{T(d/\sigma)^{1/2}}\\})$ for any
$\sigma$-smoothed online learning problem must have an
$\omega(\sqrt{d/\sigma})$ total running time.

Theorem 5.2 implies an exponential statistical-computational gap in smoothed
online learning: for exponentially small $\sigma$, achieving the statistical
regret $\widetilde{O}(\sqrt{Td\log(1/\sigma)})$ requires an exponential
running time. However, Theorem 5.2 still exhibits gaps to our computational
upper bounds.

  1. 1.

First, although both lower bounds of the regret and running time in Theorem
5.2 does not match the counterparts of Algorithm 2 in Theorem 4.2, the upper
and lower bounds share the same $\Theta(\sigma^{-1/4})$ dependence on
$\sigma$. This suggests that the improvement from $\Theta(\sigma^{-1/2})$ to
$\Theta(\sigma^{-1/4})$ thanks to Poissonization is not superfluous and might
be fundamental. We also conjecture that for all efficient algorithms with
runtime $\text{poly}(T,d,1/\sigma)$, the $\Theta(\sigma^{-1/4})$ dependence is
the best one can hope for in the regret of such algorithms, as opposed to the
$\Theta(\sqrt{\log(1/\sigma)})$ dependence in the statistical regret.

  2. 2.

Second, Theorem 5.2 shows a $\text{poly}(d,1/\sigma)$ computational lower
bound to achieve the statistical regret
$\widetilde{O}(\sqrt{Td\log(1/\sigma)})$, while the $\varepsilon$-net argument
in [HRS22] requires a $\text{poly}(\sigma^{-d})$ computational time. One may
wonder whether this exponential dependence on $d$ is in fact unavoidable, and
this is a missing feature not covered in [HK16]. We ask the following open
question:

##### Open Question.

_For $d/\sigma\gg T^{2}$ in the smoothed setting (or $dK\gg T$ in the $K$-hint
transductive learning setting), does any algorithm achieving $o(T)$ regret
require $\Omega(\text{\rm poly}(T,2^{d},1/\sigma(\text{ or }K)))$
computational time given access to the ERM oracle?_

## Acknowledgments

This work was supported in part by the National Science Foundation under grant
CCF-2145898, a C3.AI Digital Transformation Institute grant, and Berkeley AI
Research Commons grants. This work was partially done while authors were
visitors at the Simons Institute for the Theory of Computing.

## References

  * [AB99] Martin Anthony and Peter L Bartlett.  Neural network learning: Theoretical foundations, volume 9.  cambridge university press Cambridge, 1999.
  * [Bar06] Peter Bartlett.  Lecture notes in statistical learning theory, Spring 2006.
  * [BCKP20] Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit.  Online learning with imperfect hints.  In Proceedings of the International Conference on Machine Learning (ICML), pages 822–831. PMLR, 2020.
  * [BDGR22] Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin.  Smoothed online learning is as easy as statistical learning.  In Proceedings of the Conference on Learning Theory (COLT), pages 1716–1786. PMLR, 2022.
  * [BDPSS09] Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz.  Agnostic online learning.  In Proceedings of the Conference on Learning Theory (COLT), 2009\.
  * [BKP97] Peter L Bartlett, Sanjeev R Kulkarni, and S Eli Posner.  Covering numbers for real-valued function classes.  IEEE transactions on information theory, 43(5):1721–1724, 1997\.
  * [CAK17] Vincent Cohen-Addad and Varun Kanade.  Online Optimization of Smoothed Piecewise Constant Functions.  In Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), pages 412–420, 2017.
  * [DHJ+17] Ofer Dekel, Nika Haghtalab, Patrick Jaillet, et al.  Online learning with a hint.  Advances in Neural Information Processing Systems, 30:5299–5308, 2017.
  * [DHL+20] Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E Schapire, Vasilis Syrgkanis, and Jennifer Wortman Vaughan.  Oracle-efficient online learning and auction design.  Journal of the ACM (JACM), 67(5):1–57, 2020.
  * [DS16] Constantinos Daskalakis and Vasilis Syrgkanis.  Learning in auctions: Regret is hard, envy is easy.  In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), pages 219–228, 2016.
  * [FKQR21] Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin.  The statistical complexity of interactive decision making.  arXiv preprint arXiv:2112.13487, 2021.
  * [FR20] 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.
  * [GK06] Evarist Giné and Vladimir Koltchinskii.  Concentration inequalities and asymptotic results for ratio type empirical processes.  The Annals of Probability, 34(3):1143–1216, 2006.
  * [GR17] Rishi Gupta and Tim Roughgarden.  A PAC approach to application-specific algorithm selection.  SIAM Journal on Computing, 46(3):992–1017, 2017.
  * [HHSY22] Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang.  Oracle-efficient online learning for smoothed adversaries.  Advances in Neural Information Processing Systems, 36, 2022.
  * [HK10] Elad Hazan and Satyen Kale.  Extracting certainty from uncertainty: Regret bounded by variation in costs.  Machine learning, 80(2):165–188, 2010.
  * [HK16] Elad Hazan and Tomer Koren.  The computational power of optimization in online learning.  In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), page 128–141, 2016.
  * [HM07] Elad Hazan and Nimrod Megiddo.  Online learning with prior knowledge.  In Proceedings of the Conference on Learning Theory (COLT), pages 499–513, 2007.
  * [HRS20] 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.
  * [HRS22] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty.  Smoothed analysis with adaptive adversaries.  In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), pages 942–953, 2022.
  * [IS03] Yuri I. Ingster and Irina A. Suslina.  Nonparametric goodness-of-fit testing under Gaussian models, volume 169.  Springer Science & Business Media, 2003.
  * [KAH+19] Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, and John Langford.  Active learning for cost-sensitive classification.  J. Mach. Learn. Res., 20:65:1–65:50, 2019.
  * [KK05] Sham Kakade and Adam T Kalai.  From batch to transductive online learning.  Advances in Neural Information Processing Systems, 18, 2005.
  * [KKL07] Sham M. Kakade, Adam Tauman Kalai, and Katrina Ligett.  Playing games with approximation algorithms.  In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), page 546–555, 2007.
  * [KMR+18] Sampath Kannan, Jamie H Morgenstern, Aaron Roth, Bo Waggoner, and Zhiwei Steven Wu.  A smoothed analysis of the greedy algorithm for the linear contextual bandit problem.  In Advances in Neural Information Processing Systems (NeurIPS) 31, pages 2227–2236. 2018.
  * [KV05] Adam Tauman Kalai and Santosh Vempala.  Efficient algorithms for online decision problems.  Journal of Computer and System Sciences, 71(3):291 – 307, 2005\.
  * [MY16] Mehryar Mohri and Scott Yang.  Accelerating online convex optimization via adaptive prediction.  In Artificial Intelligence and Statistics, pages 848–856. PMLR, 2016.
  * [RS13a] Alexander Rakhlin and Karthik Sridharan.  Online learning with predictable sequences.  In Proceedings of the Conference on Learning Theory (COLT), pages 993–1019. PMLR, 2013.
  * [RS13b] Sasha Rakhlin and Karthik Sridharan.  Optimization, learning, and games with predictable sequences.  Advances in Neural Information Processing Systems, 26, 2013.
  * [RSS12] Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan.  Relax and randomize: From value to algorithms.  Advances in Neural Information Processing Systems, 25:2141–2149, 2012.
  * [RST11] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari.  Online learning: Stochastic, constrained, and smoothed adversaries.  Advances in neural information processing systems, 24, 2011.
  * [RSWW18] Manish Raghavan, Aleksandrs Slivkins, Jennifer Vaughan Wortman, and Zhiwei Steven Wu.  The externalities of exploration and how data diversity helps exploitation.  In Proceedings of the 31st Conference On Learning Theory (COLT), pages 1724–1738, 2018.
  * [SKS16] Vasilis Syrgkanis, Akshay Krishnamurthy, and Robert Schapire.  Efficient algorithms for adversarial contextual learning.  In International Conference on Machine Learning, pages 2159–2168. PMLR, 2016.
  * [SL14] Jacob Steinhardt and Percy Liang.  Adaptivity and optimism: An improved exponentiated gradient algorithm.  In Proceedings of the International Conference on Machine Learning (ICML), pages 1593–1601. PMLR, 2014.
  * [SLX21] 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.
  * [ST04] Daniel A. Spielman and Shang-Hua Teng.  Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time.  Journal of the ACM, 51(3):385–463, May 2004.
  * [Tsy09] A. Tsybakov.  Introduction to Nonparametric Estimation.  Springer-Verlag, 2009.

##  Appendix A Proof of Proposition 2.1

###### Proof.

To prove this lemma we break the expected regret into two parts:

$\displaystyle\operatorname*{\mathbb{E}}[\textsc{Regret}(T)]=\operatorname*{\mathbb{E}}_{\mathscr{D},\mathscr{Q}}\left[\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\widehat{y}_{t}\sim\mathcal{Q}_{t}}[l(\widehat{y}_{t},y_{t})]\\!-\\!\inf_{h\in\mathcal{H}}\\!L(h,s_{1\mathrel{\mathop{\mathchar
58\relax}}T})\right]+\operatorname*{\mathbb{E}}_{\mathscr{D},\mathscr{Q}}\left[\sum_{t=1}^{T}l(\widehat{y}_{t},y_{t})\\!-\\!\operatorname*{\mathbb{E}}_{\widehat{y}_{t}\sim\mathcal{Q}_{t}}\\![l(\widehat{y}_{t},y_{t})]\right].$
(54)

For the first part, we use an inductive argument to show that

$\displaystyle\operatorname*{\mathbb{E}}_{\mathscr{D},\mathscr{Q}}\left[\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\widehat{y}_{t}\sim\mathcal{Q}_{t}}[l(\widehat{y}_{t},y_{t})]-\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}l(h({x_{t}}),y_{t})\right]\leq\textbf{Rel}_{T}(\mathcal{H}\mid\emptyset).$
(55)

According to the definition of admissibility, we have

$\displaystyle\operatorname*{\mathbb{E}}_{\mathscr{D},\mathscr{Q}}\left[\sum_{t=1}^{T}\operatorname*{\mathbb{E}}_{\widehat{y}_{t}\sim\mathcal{Q}_{t}}[l(\widehat{y}_{t},y_{t})]\underbrace{-\inf_{h\in\mathcal{H}}\sum_{t=1}^{T}l(h({x_{t}}),y_{t})}_{\leq\textbf{Rel}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar 58\relax}}T})\text{ by 2nd condition of
admissibility}}\right]$ (56) $\displaystyle\leq$
$\displaystyle\operatorname*{\mathbb{E}}_{\mathscr{D},\mathscr{Q}}\left[\operatorname*{\mathbb{E}}\left[\left.\sum_{t=1}^{T-1}\operatorname*{\mathbb{E}}_{\widehat{y}_{t}\sim\mathcal{Q}_{t}}[l(\widehat{y}_{t},y_{t})]+\underbrace{\underset{x_{T}\sim\mathcal{D}_{T}}{\operatorname*{\mathbb{E}}}\Big{[}\operatorname*{\mathbb{E}}_{\widehat{y}_{T}\sim\mathcal{Q}_{T}}[l(\widehat{y}_{T},y_{T})]+\textbf{Rel}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar
58\relax}}T})\Big{]}}_{\leq\textbf{Rel}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar 58\relax}}T-1})\text{ by 1st condition of
admissibility}}\right|s_{1\mathrel{\mathop{\mathchar
58\relax}}T-1}\right]\right]$ (57) $\displaystyle\leq$
$\displaystyle\operatorname*{\mathbb{E}}_{\mathscr{D},\mathscr{Q}}\left[\operatorname*{\mathbb{E}}\left[\left.\sum_{t=1}^{T-1}\operatorname*{\mathbb{E}}_{\widehat{y}_{t}\sim\mathcal{Q}_{t}}[l(\widehat{y}_{t},y_{t})]+\textbf{Rel}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar
58\relax}}T-1})\right|s_{1\mathrel{\mathop{\mathchar
58\relax}}T-1}\right]\right]$ (58) $\displaystyle=$
$\displaystyle\operatorname*{\mathbb{E}}_{\mathscr{D},\mathscr{Q}}\left[\sum_{t=1}^{T-1}\operatorname*{\mathbb{E}}_{\widehat{y}_{t}\sim\mathcal{Q}_{t}}[l(\widehat{y}_{t},y_{t})]+\textbf{Rel}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar 58\relax}}T-1})\right],$ (59)

where the last step uses the tower property of conditional expectations.

Repeat this process for $(T-1)$ times and note that
$\textbf{Rel}_{T}(\mathcal{H}\mid\emptyset)$ is a constant that does not
dependent on $\mathscr{D}$ proves Equation 55.

Since the second part is the expected sum of a martingale difference sequence,
we apply the Azuma-Hoeffding inequality and obtain

$\displaystyle\operatorname*{\mathbb{E}}_{\mathscr{D},\mathscr{Q}}\left[\sum_{t=1}^{T}l(\widehat{y}_{t},y_{t})-\operatorname*{\mathbb{E}}_{\widehat{y}_{t}\sim\mathcal{Q}_{t}}[l(\widehat{y}_{t},y_{t})]\right]\leq\int_{0}^{\infty}\exp\left(-\frac{2t^{2}}{T}\right)dt\in
O(\sqrt{T}).$ (60)

Combining Equation 55 and Equation 60 completes the proof. ∎

##  Appendix B Transductive Online Learning with $K$ Hints

###  B.1 Efficient Algorithm for Transductive Online Learning with $K$ Hints

See Algorithm 3 for a description of the oracle-efficient algorithm in the
setting of transductive online learning with $K$ hints.

Input: $T,K,\\{Z_{t}\\}_{t=1}^{T}$

1 for  _$t\leftarrow 1$ to $T$_ do

2 Receive $x_{t}$. Assert that $x_{t}\in Z_{t}.$

3 for  _$i=t\\!+\\!1,\cdots,T$ ; $k=1,\cdots,K$_ do

4 Draw new $\epsilon_{i,k}^{(t)}\sim\mathcal{U}(\\{-1,+1\\})$.

5 end for

6
$S^{(t)}\leftarrow\left\\{(z_{i,k}^{(t)},\epsilon_{i,k}^{(t)})\right\\}_{\genfrac{}{}{0.0pt}{}{i=t+1\mathrel{\mathop{\mathchar
58\relax}}T\hfill}{k=1\mathrel{\mathop{\mathchar 58\relax}}K\hfill}}$,

7 $\widehat{y_{t}}\leftarrow\mathsf{OPT}\left(s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1};S^{(t)}\cup
S^{(t)}\cup\\{(x_{t},-1)\\}\right)-\mathsf{OPT}\left(s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1};S^{(t)}\cup S^{(t)}\cup\\{(x_{t},+1)\\}\right)$.

8 Receive $y_{t}$, suffer loss $l(\widehat{y}_{t},y_{t})$.

9 end for

Algorithm 3 Oracle-Efficient Online Transductive Learning with $K$ Hints

###  B.2 Monotonicity of Regularized Rademacher Complexity

Lemma 3.2 (Restated)._Let $Z=\\{z_{i}\\}_{i\in[m]}\in\mathcal{X}^{m}$ be a set
of unlabeled instances and $\Phi\mathrel{\mathop{\mathchar
58\relax}}\mathcal{H}\to\mathbb{R}$ be a mapping from the set of hypothesis to
real values. Recall that the Rademacher complexity for set $Z$ regularized by
$\Phi$ is defined as_

$\mathfrak{R}({\Phi},Z)=\operatorname*{\mathbb{E}}_{\epsilon_{1\mathrel{\mathop{\mathchar
58\relax}}m}\overset{\text{iid}}{\sim}\mathcal{U}(\pm
1)}\left[\sup_{h\in\mathcal{H}}\Big{\\{}\sum_{i=1}^{m}\epsilon_{i}h(z_{i})+\Phi(h)\Big{\\}}\right].$

_Then for any dataset $z_{1\mathrel{\mathop{\mathchar
58\relax}}m}\in\mathcal{X}^{m}$ and any additional data point
$x\in\mathcal{X}$, we have_

$\mathfrak{R}(\Phi,z_{1\mathrel{\mathop{\mathchar
58\relax}}m})\leq\mathfrak{R}(\Phi,z_{1\mathrel{\mathop{\mathchar
58\relax}}m}\cup\\{x\\}).$

###### Proof of Lemma 3.2.

Using
$\operatorname*{\mathbb{E}}[\sup_{\lambda}X_{\lambda}]\geq\sup_{\lambda}\operatorname*{\mathbb{E}}[X_{\lambda}]$,
we have

$\displaystyle\mathfrak{R}(\Phi,Z\cup\\{x\\})$
$\displaystyle=\operatorname*{\mathbb{E}}_{\epsilon_{1\mathrel{\mathop{\mathchar
58\relax}}m+1}}\left[\sup_{h\in\mathcal{H}}\left\\{\sum_{i=1}^{m}\epsilon_{i}h(z_{i})+\epsilon_{m+1}h(x)+\Phi(h)\right\\}\right]$
(61)
$\displaystyle=\operatorname*{\mathbb{E}}_{\epsilon_{1\mathrel{\mathop{\mathchar
58\relax}}m},\epsilon_{m+1}}\left[\sup_{h\in\mathcal{H}}\left\\{\sum_{i=1}^{m}\epsilon_{i}h(z_{i})+\epsilon_{m+1}h(x)+\Phi(h)\right\\}\right]$
(62)
$\displaystyle\geq\operatorname*{\mathbb{E}}_{\epsilon_{1\mathrel{\mathop{\mathchar
58\relax}}m}}\left[\sup_{h\in\mathcal{H}}\left\\{\sum_{i=1}^{m}\epsilon_{i}h(z_{i})+\operatorname*{\mathbb{E}}_{\epsilon_{m+1}}[\epsilon_{m+1}h(x)]+\Phi(h)\right\\}\right]$
(63) $\displaystyle=\mathfrak{R}({\Phi},Z),$ (64)

as desired. ∎

##  Appendix C Unknown Smoothness Parameters

Suppose we have upper and lower bounds $\sigma_{\max}$ and $\sigma_{\min}$ on
the exact value of $\sigma$, i.e., $\sigma_{\min}\leq\sigma\leq\sigma_{\max}$.
In this section, we introduce a meta algorithm that uses a geometric doubling
approach to incorporate knowledge of $\sigma_{\max}$ and $\sigma_{\min}$ into
the algorithms introduced in Section 4.

We start by constructing $\log(\sigma_{\max}/\sigma_{\min})$ experts, where
each expert $i$ runs a local version of our algorithm (can be either Algorithm
1 for the real-valued case or Algorithm 2 for the binary case) with parameter
$\sigma_{i}=2^{i}\cdot\sigma_{\min}$. We then run Hedge on these experts. Note
that the parameter $i^{\star}$ of the best expert satisfies
$\frac{\sigma}{2}\leq\sigma_{i^{\star}}\leq\sigma$, so the expected regret of
this expert matches the expected regret of the same algorithm running on true
$\sigma$ up to a constant factor. Therefore, the expected regret of this meta
algorithm is comparable to the bound in Theorem 3.1 and 3.2, with an additive
term of order at most
$O\left(\sqrt{T\log\log(\sigma_{\max}/\sigma_{\min})}\right)$. The number of
oracle calls also blows up only by $\log(\sigma_{\max}/\sigma_{\min})$ per
round. This could potentially be improved using a more aggressive step size
for the Hedge meta algorithm.

##  Appendix D Smoothed Online Learning with Real-valued Functions

###  D.1 Coupling Lemma

######  Lemma D.1 (Coupling, [HRS22]).

Let $\mathscr{D}_{\sigma}$ be an adaptive sequence of $t$ $\sigma$-smooth
distributions on $\mathcal{X}$. Then, there is a coupling $\Pi$ such that
$\left(x_{1},z_{1,1},\dots,z_{1,K},\dots,x_{t},z_{t,1},\dots,z_{t,K}\right)\sim\Pi$
satisfy

  * a.

$x_{1},\dots,x_{t}$ is distributed according $\mathscr{D}_{\sigma}$.

  * b.

For every $j\leq t$, $\\{z_{i,k}\\}_{{i\geq j},{k\in[K]}}$ are uniformly and
independently distributed on $\mathcal{X}$, conditioned on
$x_{1},\dots,x_{j-1}$.

  * c.

With probability at least $1-t\left(1-\sigma\right)^{K}$,
$\\{x_{1},\cdots,x_{T}\\}\subseteq\\{z_{t,k}\\}_{{t=1\mathrel{\mathop{\mathchar
58\relax}}T},{k=1\mathrel{\mathop{\mathchar 58\relax}}K}}$ .

###  D.2 Notions for Real-Valued Functions

In this section we introduce the notions that will be useful in analyzing
real-valued hypothesis classes, including pseudo dimension and covering
numbers.

######  Definition D.1 (Pseudo-dimension, [AB99]).

For every $h\in\mathcal{H}$, let $B_{h}(x,y)=\mathrm{sgn}(h(x)-y)$ be the
indicator of the region below or on the graph of $h$. The pseudo-dimension of
hypothesis class $\mathcal{H}$ is defined as the VC dimension of the subgraph
class $B_{\mathcal{H}}=\\{B_{h}\mathrel{\mathop{\mathchar
58\relax}}h\in\mathcal{H}\\}$.

We will see in the two following lemmas that pseudo dimension can be used to
characterize the magnitude of covering numbers and Rademacher complexity.

######  Lemma D.2 ($d_{L_{1}(\mathcal{U})}$-Covering Number Bound, [AB99]).

The $\epsilon$-covering number of $\mathcal{H}$ with respect to metric
$d_{L_{1}(\mathcal{U})}$, denoted by
$\mathcal{N}(\epsilon,\mathcal{H},L_{1}(\mathcal{U}(\mathcal{X})))$, is the
cardinality of the smallest subset $\mathcal{H}^{\prime}$ of $\mathcal{H}$,
such that for every $h\in\mathcal{H}$, there exists
$h^{\prime}\in\mathcal{H}^{\prime}$ such that
$d_{L_{1}(\mathcal{U})}(h,h^{\prime})\leq\epsilon$, where
$d_{L_{1}(\mathcal{U})}(f,g)=\operatorname*{\mathbb{E}}_{\mathcal{U}}[|f-g|]$.
If $d$ is the pseudo-dimension of $\mathcal{H}$, then for any $\epsilon>0$,

$\displaystyle\log\mathcal{N}(\epsilon,\mathcal{H},L_{1}(\mathcal{U}(\mathcal{X})))\in\widetilde{O}\\!\left(d\log\\!\left(\frac{1}{\epsilon}\right)\right).$
(65)

######  Lemma D.3 (Rademacher Complexity Bound, [Bar06]).

The Rademacher complexity of class $\mathcal{H}$ for a set of $n$ elements is
upper bounded by $O\\!\left(\sqrt{dn\log n}\right)$, where $d$ is the pseudo
dimension of $\mathcal{H}$.

###  D.3 Proof of Theorem 4.1

Theorem 4.1 (Restated)._For any $\sigma$-smooth adversary
$\mathscr{D}_{\sigma}$, Algorithm 1 has expected regret upper bounded by
$\widetilde{O}(G\sqrt{Td/\sigma})$, where $\widetilde{O}$ hide factors that
are polynomial in $\log(T)$ and $\log(1/\sigma)$. Here $G$ is the Lipschitz
constant of the loss and $d$ is the pseudodimension of class $\mathcal{H}$.
Furthermore, the algorithm is oracle-efficient: at every round $t$, this
algorithm uses two oracle calls with histories of length
$\widetilde{O}(T/\sigma)$. _

###### Proof.

To prove Theorem 4.1 we use the following relaxation:

$\displaystyle\textbf{Rel}_{T}(\mathcal{H}|s_{1\mathrel{\mathop{\mathchar
58\relax}}t})=$ $\displaystyle
2G\operatorname*{\mathbb{E}}_{V^{(t)}\overset{\text{iid}}{\sim}\mathcal{U}(\mathcal{X})}\left[\mathfrak{R}(-{L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t})},V^{(t)})\right]+2G\beta(T-t)$ (66) $\displaystyle=$
$\displaystyle
2G\operatorname*{\mathbb{E}}_{V^{(t)},\mathcal{E}^{(t)}}\left[\sup_{h\in\mathcal{H}}\left\\{\sum_{i=t+1\mathrel{\mathop{\mathchar
58\relax}}T\atop k=1\mathrel{\mathop{\mathchar
58\relax}}K}\epsilon_{i,k}^{(t)}h(v_{i,k}^{(t)})-L^{\mathrm{r}}(h,s_{1\mathrel{\mathop{\mathchar
58\relax}}t})\right\\}\right]+2G\beta(T-t),$ (67)

where $K=100\log T/\sigma$ and $\beta=10TK(1-\sigma)^{K}$. We will show in
Lemma D.4 that the above relaxation is admissible. Therefore, Proposition 2.1
gives us the following upper bound on the expected regret:

$\displaystyle\operatorname*{\mathbb{E}}[\textsc{Regret}(T)]\leq\textbf{Rel}_{T}(\mathcal{H}|\emptyset)\\!+\\!O(\sqrt{T})\\!=\\!2G\underbrace{\operatorname*{\mathbb{E}}_{V^{(0)},\mathcal{E}^{(0)}}\left[\sup_{h\in\mathcal{H}}\left\\{\sum_{i=1\mathrel{\mathop{\mathchar
58\relax}}T\atop k=1\mathrel{\mathop{\mathchar
58\relax}}K}\epsilon_{i,k}^{(0)}h(v_{i,k}^{(0)})\right\\}\right]}_{\text{(a)}}+2G\beta
T\\!+\\!O(\sqrt{T}).$ (68)

The first term (a) is the Rademacher complexity of the hypothesis class
$\mathcal{H}$ with respect to the uniform distribution for sample size $TK$.
By Lemma D.3, $\text{(a)}\leq O\left(\sqrt{dTK\log(TK)}\right)$. For the
second term, we have $\beta T\in o(1)$ because $\beta\lesssim TKe^{-\sigma
K}\lesssim T^{-99}\log T/\sigma=o(T)$. Plugging in
$K=O\left({\log(T)}/{\sigma}\right)$, we have the following bound:

$\displaystyle\operatorname*{\mathbb{E}}[\textsc{Regret}(T)]\leq{O}\left(G\sqrt{\frac{dT}{\sigma}\log
T\log\left(\frac{T}{\sigma}\right)}\right)\subseteq\widetilde{O}(G\sqrt{dT/\sigma}),$
(69)

where $\widetilde{O}$ hide factors that are polynomial in $\log(T)$ and
$\log(1/\sigma)$. ∎

###  D.4 Admissibility of the Relaxation

######  Lemma D.4.

The prediction rule $\mathscr{Q}=(\mathcal{Q}_{1},\cdots,\mathcal{Q}_{T})$
given by Algorithm 1 is admissible with respect to the relaxation defined in
Equation 67.

###### Proof.

Using the language of regularized Rademacher complexity, the above relaxation
can be written as

$\displaystyle\textbf{Rel}_{T}(\mathcal{H}|s_{1\mathrel{\mathop{\mathchar
58\relax}}t})=2G\operatorname*{\mathbb{E}}_{V^{(t)}\overset{\text{iid}}{\sim}\mathcal{U}(\mathcal{X})}\left[\mathfrak{R}(-{L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t})},V^{(t)})\right]+2G\beta(T-t),$ (70)

where $L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t})=\sum_{i=1}^{t-1}l^{\mathrm{r}}(h(x_{i}),y_{i})$. When $t=T$, the
relaxation becomes

$\displaystyle\textbf{Rel}_{T}(\mathcal{H}|s_{1\mathrel{\mathop{\mathchar
58\relax}}T})=-2GL^{\mathrm{r}}(h,s_{1\mathrel{\mathop{\mathchar
58\relax}}T})=-\inf_{h\in\mathcal{H}}\sum_{i=1}^{T}l(h(x_{i}),y_{i}),$ (71)

thus it satisfies the second condition of Definition 2.4. For the first
condition, we need to verify

$\displaystyle\sup_{\mathcal{D}_{t}\in\mathfrak{D}_{t}}\operatorname*{\mathbb{E}}_{x_{t}\sim\mathcal{D}_{t}}\sup_{y_{t}\in\mathcal{Y}}\\!\left\\{\\!\operatorname*{\mathbb{E}}_{\widehat{y}_{t}\sim\mathcal{Q}_{t}}\\![l(\widehat{y}_{t},y_{t})]\\!+\\!\textbf{Rel}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}\\!\cup\\!(x_{t},y_{t}))\\!\right\\}\\!\leq\\!\textbf{Rel}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar 58\relax}}t-1}).$ (72)

We first upper bound the LHS of Equation 72 by matching the randomness in
$V^{(t)}$ and applying Jensen’s inequality to the supremum function. This
gives us

$\displaystyle\sup_{\mathcal{D}_{t}\in\mathfrak{D}_{t}}\operatorname*{\mathbb{E}}_{x_{t}\sim\mathcal{D}_{t}}\sup_{y_{t}\in\mathcal{Y}}\\!\left\\{\\!\operatorname*{\mathbb{E}}_{\widehat{y}_{t}\sim\mathcal{Q}_{t}}\\![l(\widehat{y}_{t},y_{t})]\\!+\\!\textbf{Rel}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}\\!\cup\\!(x_{t},y_{t}))\\!\right\\}$ (73) $\displaystyle=$
$\displaystyle\sup_{\mathcal{D}_{t}\in\mathfrak{D}_{t}}\operatorname*{\mathbb{E}}_{x_{t}\sim\mathcal{D}_{t}}\sup_{y_{t}\in\mathcal{Y}}\operatorname*{\mathbb{E}}_{V^{(t)}\overset{\text{iid}}{\sim}\mathcal{U}(\mathcal{X})}\left[\operatorname*{\mathbb{E}}_{\widehat{y}_{t}\sim\mathcal{Q}_{t}(V^{(t)})}\left[l(\widehat{y}_{t},y_{t})\right]+2G\cdot\mathfrak{R}(-{L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t})},V^{(t)})\right]+2G\beta(T-t)$ (74) $\displaystyle\leq$
$\displaystyle\sup_{\mathcal{D}_{t}\in\mathfrak{D}_{t}}\operatorname*{\mathbb{E}}_{x_{t}\sim\mathcal{D}_{t}}\operatorname*{\mathbb{E}}_{V^{(t)}\overset{\text{iid}}{\sim}\mathcal{U}(\mathcal{X})}\left[\sup_{y_{t}\in\mathcal{Y}}\left\\{\operatorname*{\mathbb{E}}_{\widehat{y}_{t}\sim\mathcal{Q}_{t}(V^{(t)})}\left[l(\widehat{y}_{t},y_{t})\right]+2G\cdot\mathfrak{R}(-{L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t})},V^{(t)})\right\\}\right]+2G\beta(T-t)$ (75)

For every fixed input $x_{t}$ and hint set $V^{(t)}$, our prediction rule in
Equation 7, which we denote with $\mathcal{Q}_{t}(V^{(t)})$, is the same as
the transductive prediction rule in [RSS12, Equation (25)], with $V^{(t)}$
being the set of unlabeled future instances and
$s_{1\mathrel{\mathop{\mathchar 58\relax}}t-1}$ being the historical data with
labels.

According to [RSS12, Lemma 12], for all input $x_{t}$ and unlabeled sequence
$\mathscr{X}$ (which plays the role of $x_{t+1\mathrel{\mathop{\mathchar
58\relax}}T}$), the decision rule $\mathcal{Q}_{t}(\mathscr{X})$ satisfies

$\displaystyle\sup_{y_{t}\in\mathcal{Y}}\left\\{\operatorname*{\mathbb{E}}_{\widehat{y}_{t}\sim\mathcal{Q}_{t}(\mathscr{X})}[l(\widehat{y}_{t},y_{t})]+2G\operatorname*{\mathbb{E}}_{\mathcal{E}}\left[\sup_{h\in\mathcal{H}}\left\\{\sum_{x\in\mathscr{X}}\epsilon_{x}h(x)-L^{\text{r}}(h,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}\cup(x_{t},y_{t}))\right\\}\right]\right\\}$ (76)
$\displaystyle\qquad\qquad\qquad\leq
2G\operatorname*{\mathbb{E}}_{\mathcal{E}}\left[\sup_{h\in\mathcal{H}}\left\\{\sum_{x\in\mathscr{X}\cup\\{x_{t}\\}}\epsilon_{x}h(x)-L^{\text{r}}(h,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1})\right\\}\right].$ (77)

Therefore, if we choose the sequence $\mathscr{X}$ to be $V^{(t)}$, we obtain
the following inequality which is written in the language of regularized
Rademacher complexity:

$\displaystyle\sup_{y_{t}\in\mathcal{Y}}\left\\{\operatorname*{\mathbb{E}}_{\widehat{y}_{t}\sim\mathcal{Q}_{t}(V^{(t)})}\left[l(\widehat{y}_{t},y_{t})\right]+2G\cdot\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t}),V^{(t)})\right\\}\leq
2G\cdot\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup\\{x_{t}\\}).$ (78)

By adding the expectations over $V^{(t)}$ and $x_{t}$ on both sides, we obtain
the following upper bound:

$\displaystyle\eqref{eq:real-tmp1}\leq$
$\displaystyle\sup_{\mathcal{D}_{t}\in\mathfrak{D}_{t}}\operatorname*{\mathbb{E}}_{x_{t}\sim\mathcal{D}_{t}}\operatorname*{\mathbb{E}}_{V^{(t)}\overset{\text{iid}}{\sim}\mathcal{U}(\mathcal{X})}\left[2G\cdot\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup\\{x_{t}\\})\right]+2G\beta(T-t)$ (79)
$\displaystyle\leq$
$\displaystyle\operatorname*{\mathbb{E}}_{V^{(t)}\overset{\text{iid}}{\sim}\mathcal{U}(\mathcal{X})}\left[\sup_{\mathcal{D}_{t}\in\mathfrak{D}_{t}}\operatorname*{\mathbb{E}}_{x_{t}\sim\mathcal{D}_{t}}2G\cdot\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup\\{x_{t}\\})\right]+2G\beta(T-t).$ (80)

According to Lemma D.5, we can replace the $x_{t}$ sampled from the worst-case
smooth distribution by $Z_{t}$ sampled independently from the uniform
distribution, with the extra cost $\beta$. This gives

$\displaystyle\eqref{eq:real-tmp1}\leq$
$\displaystyle\operatorname*{\mathbb{E}}_{{V^{(t)}\overset{\text{iid}}{\sim}\mathcal{U}(\mathcal{X})}}\operatorname*{\mathbb{E}}_{Z_{t}\overset{\text{iid}}{\sim}\mathcal{U}(\mathcal{X})}\left[2G\cdot\left(\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup Z_{t})+\beta\right)\right]+2G\beta(T-t)$ (81)
$\displaystyle=$ $\displaystyle
2G\operatorname*{\mathbb{E}}_{V^{(t)}\overset{\text{iid}}{\sim}\mathcal{U}(\mathcal{X})}\left[\mathfrak{R}(-{L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1})},V^{(t-1)})\right]+2G\beta(T-t+1)$ (82) $\displaystyle=$
$\displaystyle\textbf{Rel}_{T}(\mathcal{H}|s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),$ (83)

which is precisely the RHS of Equation 72. ∎

######  Lemma D.5 (Replacing Supremum by Expectation).

For any $V^{(t)}\in\mathcal{X}^{K(T-t)}$, there exists a set of $K$ variables
$Z_{t}=\\{z_{t,k}\\}_{k\in[K]}$, such that

$\displaystyle\sup_{\mathcal{D}_{t}^{\mathcal{X}}\in\Delta_{\sigma}(\mathcal{X})}\operatorname*{\mathbb{E}}_{{x_{t}\sim\mathcal{D}_{t}^{\mathcal{X}}}}\left[\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup\\{x_{t}\\})\right]\leq\operatorname*{\mathbb{E}}_{Z_{t}\overset{\text{iid}}{\sim}\mathcal{U}(\mathcal{X})}\left[\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup Z_{t})\right]+\beta.$ (84)

###### Proof.

To establish the monotonicity property, we need to show that the random
instance $x_{t}$ drawn from a smooth distribution belongs to a set of uniform
i.i.d. hints with high probability. This is where the coupling lemma comes in.
For the smooth distribution $\mathcal{D}_{t}\in\Delta_{\sigma}(\mathcal{X})$
that achieves the supremum (assume the supremum is achievable), Lemma D.1
shows the existence of a coupling $\Pi$ on $(x_{t},z_{t,1},\cdots,z_{t,K})$
such that $x_{t}$ is distributed according to $\mathcal{D}_{t}^{\mathcal{X}}$
and $Z_{t}=\\{z_{t,k}\\}_{k\in[K]}$ are uniformly and independently
distributed. We thus have

$\displaystyle\sup_{\mathcal{D}_{t}\in\Delta_{\sigma}(\mathcal{X})}\operatorname*{\mathbb{E}}_{{x_{t}\sim\mathcal{D}_{t}}}\left[\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup\\{x_{t}\\})\right]=\operatorname*{\mathbb{E}}_{\Pi}\left[\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup\\{x_{t}\\})\right].$ (85)

This joint distribution $\Pi$ has the property that event the
$E_{t}\overset{\text{def}}{=}\\{x_{t}\in Z_{t}\\}$ happens with high
probability. We now upper bound the expected value by conditioning on $E_{t}$
and $\bar{E_{t}}$ respectively.

Conditioned on $E_{t}$, we apply the monotonicity of regularized Rademacher
complexity (Lemma 3.2) recursively and obtain

$\displaystyle\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup\\{x_{t}\\})\leq\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup Z_{t}).$ (86)

Conditioned on $\bar{E_{t}}$, we skirt the monotonicity issue by directly
using upper and lower bounds on the regularized Rademacher complexity. To be
more precise, we use Lemma D.6 in Section D.5 to show that

$\displaystyle\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup\\{x_{t}\\})\leq$ $\displaystyle TK\leq
TK+\left(\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup Z_{t})+{T}\right)$ (87) $\displaystyle\leq$
$\displaystyle\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup Z_{t})+2TK.$ (88)

Finally, we expand the right hand side of Equation 85 by conditioning on
$E_{t}$ and $\bar{E_{t}}$ respectively. Putting Equations 86 and 88 together,
we obtain

$\displaystyle\text{\eqref{eq:medium}}=$
$\displaystyle\Pr[E_{t}]\cdot\operatorname*{\mathbb{E}}_{\Pi}\left[\left.\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup\\{x_{t}\\})\right|E_{t}\right]$ (89)
$\displaystyle\qquad\qquad\qquad+\Pr[\bar{E_{t}}]\cdot\operatorname*{\mathbb{E}}_{\Pi}\left[\left.\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup\\{x_{t}\\})\right|\bar{E_{t}}\right]$ (90)
$\displaystyle\leq$
$\displaystyle\Pr[E_{t}]\cdot\operatorname*{\mathbb{E}}_{\Pi}\left[\left.\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup Z_{t})\right|E_{t}\right]$ (91)
$\displaystyle\qquad\qquad\qquad+\Pr[\bar{E_{t}}]\cdot\operatorname*{\mathbb{E}}_{\Pi}\left[\left.\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup Z_{t})+2TK\right|\bar{E_{t}}\right]$ (92)
$\displaystyle=$
$\displaystyle\operatorname*{\mathbb{E}}_{\Pi}\left[\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup Z_{t})\right]+\Pr[\bar{E_{t}}]\cdot 2TK.$ (93)

Since $\Pi$ has uniform marginal distribution on $Z_{t}$, and that
$\Pr[\bar{E_{t}}]\cdot 2TK\leq(1-\sigma)^{K}\cdot 2TK\leq\beta$, we further
obtain

$\displaystyle\eqref{eq:medium}\leq$
$\displaystyle\operatorname*{\mathbb{E}}_{Z_{t}\overset{\text{iid}}{\sim}\mathcal{U}(\mathcal{X})}\left[\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}),V^{(t)}\cup Z_{t})\right]+\beta,$ (94)

thus completes the proof. ∎

###  D.5 Upper and Lower Bounds on the Relaxation

######  Lemma D.6 (Upper and Lower Bounds on the Relaxation).

For all $t\in[T]$, all sequence $s_{1\mathrel{\mathop{\mathchar 58\relax}}T}$,
and all instance set $Z$ of size no larger than $(T-t)K$,

$\displaystyle-\frac{T}{2}\leq\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t}),Z)\leq TK.$ (95)

###### Proof.

By convexity of the supremum,

$\displaystyle\mathfrak{R}(-L_{t},Z)$
$\displaystyle=\operatorname*{\mathbb{E}}_{{\mathcal{E}\overset{\text{iid}}{\sim}\mathcal{U}(\mathcal{Y})}}\left[\sup_{h\in\mathcal{H}}\left\\{\sum_{i=1}^{I}\epsilon_{i}h(z_{i})-L^{\mathrm{r}}(h,s_{1\mathrel{\mathop{\mathchar
58\relax}}t})\right\\}\right]\geq\sup_{h\in\mathcal{H}}\left\\{\operatorname*{\mathbb{E}}_{{\mathcal{E}\overset{\text{iid}}{\sim}\mathcal{U}(\mathcal{Y})}}\left[\sum_{i=1}^{I}\epsilon_{i}h(z_{i})-L^{\mathrm{r}}(h,s_{1\mathrel{\mathop{\mathchar
58\relax}}t})\right]\right\\}$ (96)
$\displaystyle=\sup_{h\in\mathcal{H}}\sum_{i=1}^{t}\underbrace{(-l^{\mathrm{r}}(h(x_{t}),y_{t}))}_{\geq-1}\geq-{T}.$
(97)

For the upper bound, we notice that $\forall\mathcal{E},h$,

$\displaystyle\sum_{i=1}^{I}\epsilon_{i}h(z_{i})-L^{\mathrm{r}}(h,s_{1\mathrel{\mathop{\mathchar
58\relax}}t})\leq I+t\leq(T-t)K+t\leq TK.$ (98)

So the $\mathfrak{R}(-L^{\mathrm{r}}(\cdot,s_{1\mathrel{\mathop{\mathchar
58\relax}}t}),Z)$ also has an upper bound of $TK$. ∎

###  D.6 Remark on the Requirement of Fresh Dataset

In order to beat the adaptive adversary, the learner needs to sample fresh
random hints in each round. Otherwise, the adversary can enforce high regret
by correlating future labels with the history. More precisely, we will see
that the _matching randomness_ argument in Equation 74 uses the crucial fact
that $V^{(t)}$ is a _fresh_ dataset that is uniformly distributed independent
of the interactions in the past. If $V^{(t)}$ is reused, then the adaptive
adversary has the power to correlate $s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1}$ with $V^{(t)}$ such that $V^{(t)}$ is no longer unbiased
conditioned on the history. In this case, the algorithm fails to mimic the
randomization in the relaxation, and the matching-randomness argument breaks
down.

Another important property of the fresh self-generated hints $v^{(t)}_{i,k}$
is that they are identically distributed with the real hints $z_{i,k}$ in the
coupling. Nevertheless, the analysis has to unite the fact that the learner
can only access $v^{(t)}_{i,k}$s, and the monotonicity property (lemma D.5) is
based on $z_{i,k}$. This point is subtle because it is impossible for the
self-generated hints to really tell the future (i.e., ensure
$x_{t}\in\\{v_{t,k}^{(t-1)}\\}_{k\in[K]}$), since they are not controlled by
the coupling $\Pi$. This issue is taken care of by Equation 82. We can see
that it is sufficient for the uncoupled hints in $V^{(t-1)}$ to resemble the
coupled hints $Z_{t}$ at _distribution_ level. This distributional resemblence
is not achievable if $V^{(t-1)}$ were not independent with the past.

##  Appendix E Smoothed Online Learning with Binary-valued Functions

###  E.1 Information Theoretic Lemmas

For two probability distributions $P$ and $Q$ over the same domain
$\mathcal{X}$, let
$\chi^{2}(P,Q)=\sum_{x\in\mathcal{X}}\frac{P(x)^{2}}{Q(x)}-1$ be the
$\chi^{2}$-divergence. The following lemma upper bounds the TV distance by the
$\chi^{2}$-divergence; a proof could be found in [Tsy09, Chapter 2].

######  Lemma E.1 (From TV to $\chi^{2}$).

The following relations hold:

$\displaystyle\text{\rm TV}(P,Q)$
$\displaystyle\leq\sqrt{\frac{1}{2}\log(1+\chi^{2}(Q,P))}\leq\sqrt{\frac{\chi^{2}(Q,P)}{2}}.$
(99)

The following statement is the well-known Ingster’s $\chi^{2}$ method, and we
refer to the excellent book [IS03] for a general treatment.

######  Lemma E.2 (Ingster’s $\chi^{2}$ method).

For a mixture distribution
$\operatorname*{\mathbb{E}}_{\theta\sim\pi}[Q_{\theta}]$ and a generic
distribution $P$, the following identity holds:

$\displaystyle\chi^{2}\left(\operatorname*{\mathbb{E}}_{\theta\sim\pi}[Q_{\theta}],P\right)$
$\displaystyle=\operatorname*{\mathbb{E}}_{\theta,\theta^{\prime}\sim\pi}\left[\operatorname*{\mathbb{E}}_{x\sim
P}\left(\frac{Q_{\theta}(x)Q_{\theta^{\prime}}(x)}{P(x)^{2}}\right)\right]-1,$
(100)

where $\theta^{\prime}$ is an independent copy of $\theta$.

###  E.2  Proof of Lemma 4.4

Using the definitions of $\mathcal{Q}_{t},r^{t}$, and $\mathcal{P}^{t}$, the
following chain of inequalities holds for any fixed $s_{t}$:

$\displaystyle\operatorname*{\mathbb{E}}_{h_{t}\sim\mathcal{Q}_{t}}[L(h_{t},s_{t})]+\textbf{Rel}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar 58\relax}}t})$ (101)
$\displaystyle\overset{\rm(a)}{=}\operatorname*{\mathbb{E}}_{\mathcal{P}^{t-1}}[L(\mathsf{opt}_{\mathcal{H},l}(r^{t-1}),s_{t})]-\operatorname*{\mathbb{E}}_{R^{(t+1)}}\left[\sum_{i=1}^{N^{(t+1)}}L(\mathsf{opt}_{\mathcal{H},l}(r^{t}),\widetilde{s}_{i}^{(t+1)})+\sum_{\tau=1}^{t}L(\mathsf{opt}_{\mathcal{H},l}(r^{t}),s_{\tau})\right]+\eta(T-t)$
(102)
$\displaystyle=\operatorname*{\mathbb{E}}_{\mathcal{P}^{t-1}}[L(\mathsf{opt}_{\mathcal{H},l}(r^{t-1}),s_{t})]-\operatorname*{\mathbb{E}}_{\mathcal{P}^{t}}[L(\mathsf{opt}_{\mathcal{H},l}(r^{t}),s_{t})]+\eta(T-t)$
(103)
$\displaystyle\qquad-\operatorname*{\mathbb{E}}_{R^{(t+1)}}\left[\sum_{i=1}^{N^{(t+1)}}L(\mathsf{opt}_{\mathcal{H},l}(r^{t}),\widetilde{s}_{i}^{(t+1)})+\sum_{\tau=1}^{t-1}L(\mathsf{opt}_{\mathcal{H},l}(r^{t}),s_{\tau})\right]$
(104)
$\displaystyle\leq\operatorname*{\mathbb{E}}_{h_{t}\sim\mathcal{Q}_{t}}[L(h_{t},s_{t})]-\operatorname*{\mathbb{E}}_{h_{t+1}\sim\mathcal{Q}_{t+1}}[L(h_{t+1},s_{t})]+\eta(T-t)+\operatorname*{\mathbb{E}}_{R^{(t+1)}}\left[\sup_{h\in\mathcal{H}}\left(-\sum_{i=1}^{N^{(t+1)}}L(h,\widetilde{s}_{i}^{(t+1)})-\sum_{\tau=1}^{t-1}L(h,s_{\tau})\right)\right]$
(105)
$\displaystyle\overset{\rm(b)}{=}\operatorname*{\mathbb{E}}_{h_{t}\sim\mathcal{Q}_{t}}[L(h_{t},s_{t})]-\operatorname*{\mathbb{E}}_{h_{t+1}\sim\mathcal{Q}_{t+1}}[L(h_{t+1},s_{t})]+\eta(T-t)+\operatorname*{\mathbb{E}}_{R^{(t)}}\left[\sup_{h\in\mathcal{H}}\left(-\sum_{i=1}^{N^{(t)}}L(h,\widetilde{s}_{i}^{(t)})-\sum_{\tau=1}^{t-1}L(h,s_{\tau})\right)\right]$
(106)
$\displaystyle=\operatorname*{\mathbb{E}}_{h_{t}\sim\mathcal{Q}_{t}}[L(h_{t},s_{t})]-\operatorname*{\mathbb{E}}_{h_{t+1}\sim\mathcal{Q}_{t+1}}[L(h_{t+1},s_{t})]-\eta+\textbf{Rel}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar 58\relax}}t-1}),$ (107)

where (a) uses the definition of $\mathsf{opt}_{\mathcal{H},l}(r^{t})$, and
(b) is due to the fact that $R^{(t+1)}$ is an independent copy of $R^{(t)}$
conditioned on $\\{s_{\tau}\\}_{\tau<t}$. This implies the first inequality of
Lemma 4.4.

For the second inequality, we further take the expectation with respect to
$s_{t}\sim\mathcal{D}_{t}$, and note that $\mathcal{Q}_{t}$ and
$\textbf{Rel}_{T}(\mathcal{H}\mid s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1})$ are independent of $s_{t}$, while $\mathcal{Q}_{t+1}$ depends
on $s_{t}$:

$\displaystyle\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}\left(\operatorname*{\mathbb{E}}_{h_{t}\sim\mathcal{Q}_{t}}[L(h_{t},s_{t})]+\textbf{Rel}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar
58\relax}}t})\right)-\textbf{Rel}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar 58\relax}}t-1})$ (108)
$\displaystyle\leq\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}\operatorname*{\mathbb{E}}_{h_{t}\sim\mathcal{Q}_{t}}[L(h_{t},s_{t})]-\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}\operatorname*{\mathbb{E}}_{h_{t+1}\sim\mathcal{Q}_{t+1}}[L(h_{t+1},s_{t})]-\eta$
(109)
$\displaystyle\leq\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}\operatorname*{\mathbb{E}}_{h_{t}\sim\mathcal{Q}_{t}}[L(h_{t},s_{t})]-\operatorname*{\mathbb{E}}_{s_{t},s_{t}^{\prime}\sim\mathcal{D}_{t}}\operatorname*{\mathbb{E}}_{h_{t+1}\sim\mathcal{Q}_{t+1}}[L(h_{t+1},s_{t}^{\prime})]$
(110)
$\displaystyle\qquad+\operatorname*{\mathbb{E}}_{s_{t},s_{t}^{\prime}\sim\mathcal{D}_{t}}\operatorname*{\mathbb{E}}_{h_{t+1}\sim\mathcal{Q}_{t+1}}[L(h_{t+1},s_{t}^{\prime})]-\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}\operatorname*{\mathbb{E}}_{h_{t+1}\sim\mathcal{Q}_{t+1}}[L(h_{t+1},s_{t})]-\eta$
(111)
$\displaystyle\overset{\rm(c)}{=}\operatorname*{\mathbb{E}}_{s_{t}^{\prime}\sim\mathcal{D}_{t}}\operatorname*{\mathbb{E}}_{h_{t}\sim\mathcal{Q}_{t}}[L(h_{t},s_{t}^{\prime})]-\operatorname*{\mathbb{E}}_{s_{t}^{\prime}\sim\mathcal{D}_{t}}\operatorname*{\mathbb{E}}_{h_{t+1}\sim\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}[\mathcal{Q}_{t+1}]}[L(h_{t+1},s_{t}^{\prime})]$
(112)
$\displaystyle\qquad+\operatorname*{\mathbb{E}}_{s_{t},s_{t}^{\prime}\sim\mathcal{D}_{t}}\operatorname*{\mathbb{E}}_{h_{t+1}\sim\mathcal{Q}_{t+1}}[L(h_{t+1},s_{t}^{\prime})]-\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}\operatorname*{\mathbb{E}}_{h_{t+1}\sim\mathcal{Q}_{t+1}}[L(h_{t+1},s_{t})]-\eta$
(113)
$\displaystyle\overset{\rm(d)}{\leq}\text{TV}(\mathcal{Q}_{t},\operatorname*{\mathbb{E}}_{s_{t}\sim\mathcal{D}_{t}}[\mathcal{Q}_{t+1}])+\operatorname*{\mathbb{E}}_{s_{t},s_{t}^{\prime}\sim\mathcal{D}_{t};R^{(t+1)}}\left[L(h_{t+1},s_{t}^{\prime})-L(h_{t+1},s_{t})\right]-\eta,$
(114)

where (c) follows from the independence of $h_{t}\sim\mathcal{Q}_{t}$ and
$(s_{t},s_{t}^{\prime})$, and (d) is due to
$|\operatorname*{\mathbb{E}}_{X\sim P}[f(X)]-\operatorname*{\mathbb{E}}_{X\sim
Q}[f(X)]|\leq\text{TV}(P,Q)$ for every measurable function $f$ with
$\|f\|_{\infty}\leq 1$.

###  E.3 Proof of Lemma 4.7

The proof is essentially similar to [BDGR22, Lemma 12], and we include it here
for completeness. For each $i\in[m]$, compute the value
$p_{i}=\sigma\frac{dP}{dQ}(X_{i})$, which lies in $[0,1]$ due to the
likelihood ratio upper bound. Now we draw an independent Bernoulli random
variable $Y_{i}\sim\text{Bern}(p_{i})$, and define the random index $I$ and
success event $E$ as follows:

$\displaystyle E$ $\displaystyle\triangleq\cup_{i=1}^{m}\\{Y_{i}=1\\},$ (115)
$\displaystyle I$ $\displaystyle\triangleq\text{a uniformly random element of
}\\{i\in[m]\mathrel{\mathop{\mathchar 58\relax}}Y_{i}=1\\}.$ (116)

Note that $Y_{1},\cdots,Y_{m}$ are mutually independent, and for each
$i\in[m]$,

$\displaystyle\Pr[Y_{i}=1]=\operatorname*{\mathbb{E}}_{X_{i}\sim
Q}[p_{i}]=\operatorname*{\mathbb{E}}_{X_{i}\sim
Q}\left[\sigma\frac{dP}{dQ}(X_{i})\right]=\sigma,$ (117)

we conclude that $\Pr[E]=1-(1-\sigma)^{m}$. For the second statement, we
denote by $r_{i}$ the external randomness used in drawing
$Y_{i}\sim\text{Bern}(p_{i})$, and by $r$ the external randomness used in the
definition of $I$. Then for any measurable set $A\subseteq\mathcal{X}$,

$\displaystyle\Pr[X_{I}\in A\mid E,X_{\backslash I}]$ (118)
$\displaystyle=\sum_{i,r_{\backslash i},r}\Pr[X_{I}\in A\mid E,X_{\backslash
I},I=i,r_{\backslash i},r]\cdot\Pr[I=i,r_{\backslash i},r\mid E,X_{\backslash
I}]$ (119) $\displaystyle=\sum_{i,r_{\backslash i},r}\Pr[X_{i}\in A\mid
E,X_{\backslash i},I=i,r_{\backslash i},r]\cdot\Pr[I=i,r_{\backslash i},r\mid
E,X_{\backslash I}]$ (120)
$\displaystyle\overset{\rm(a)}{=}\sum_{i,r_{\backslash i},r}\Pr[X_{i}\in A\mid
Y_{i}=1,X_{\backslash i},r_{\backslash i},r]\cdot\Pr[I=i,r_{\backslash
i},r\mid E,X_{\backslash I}]$ (121)
$\displaystyle\overset{\rm(b)}{=}\sum_{i,r_{\backslash i},r}\Pr[X_{i}\in A\mid
Y_{i}=1]\cdot\Pr[I=i,r_{\backslash i},r\mid E,X_{\backslash I}]$ (122)
$\displaystyle\overset{\rm(c)}{=}\sum_{i,r_{\backslash
i},r}P(A)\cdot\Pr[I=i,r_{\backslash i},r\mid E,X_{\backslash I}]$ (123)
$\displaystyle=P(A),$ (124)

where (a) is due to the event $\\{E,I=i,X_{\backslash i},r_{\backslash
i},r\\}$ is the same as $\\{Y_{i}=1,X_{\backslash i},r_{\backslash i},r\\}$ as
long as the former event $\\{E,I=i,X_{\backslash i},r_{\backslash i},r\\}$ is
non-empty (note that empty events do not contribute to the sum), (b) follows
from the mutual independence of $(X_{i},r_{i},Y_{i})_{i\in[m]}$ and $r$, (c)
is due to

$\displaystyle\Pr[X_{i}\in A\mid Y_{i}=1]=\frac{\Pr[X_{i}\in
A,Y_{i}=1]}{\Pr[Y_{i}=1]}=\frac{1}{\sigma}\operatorname*{\mathbb{E}}_{X_{i}\sim
Q}\left[\mathbf{1}(X_{i}\in A)\sigma\frac{dP}{dQ}(X_{i})\right]=P(A).$ (125)

The above identity shows that the conditional distribution of $X_{I}$
conditioned on $(E,X_{\backslash I})$ is always $P$, as desired.

###  E.4 Proof of Lemma 4.8

The analysis is similar to the proof of Lemma 4.4. In fact, an intermediate
step of Lemma 4.4 gives

$\displaystyle\operatorname*{\mathbb{E}}_{h_{t}\sim\mathcal{Q}_{t}}[L(h_{t},s_{t})]+\textbf{Rel}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar 58\relax}}t})-\textbf{Rel}_{T}(\mathcal{H}\mid
s_{1\mathrel{\mathop{\mathchar
58\relax}}t-1})\leq\operatorname*{\mathbb{E}}_{h_{t}\sim\mathcal{Q}_{t}}[L(h_{t},s_{t})]-\operatorname*{\mathbb{E}}_{h_{t+1}\sim\mathcal{Q}_{t+1}}[L(h_{t+1},s_{t})]-\eta.$
(126)

Now using $|\operatorname*{\mathbb{E}}_{X\sim