Oracle-Efficient Online Learning for Smoothed Adversaries
Authors: Nika Haghtalab
Yanjun Han
Abhishek Shetty
Kunhe Yang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Online learning
Computational Efficiency
Smoothed Analysis

Abstract: We study the design of computationally efficient online learning algorithms under smoothed analysis. In this setting, at every step, an adversary generates a sample from an adaptively chosen distribution whose density is upper bounded by $1/\sigma$ times the uniform density. Given access to an offline optimization (ERM) oracle, we give the first computationally efficient online algorithms whose sublinear regret depends only on the pseudo/VC dimension $d$ of the class and the smoothness parameter $\sigma$. In particular, we achieve \emph{oracle-efficient} regret bounds of   $ O (  \sqrt{T d\sigma^{-1}} ) $ for learning real-valued functions and $ O (  \sqrt{T d\sigma^{-\frac{1}{2}} }  )$ for learning binary-valued functions. Our results establish that online learning is computationally as easy as offline learning, under the smoothed analysis framework. 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 some settings with binary-valued functions and worst-case adversaries.  These include an oracle-efficient algorithm with $O ( \sqrt{T(d |\mathcal{X}|)^{1/2} })$ regret that refines the earlier $O ( \sqrt{T|\mathcal{X}|})$ bound of [DS16] for finite domains, and an oracle-efficient algorithm with $O(T^{3/4} d^{1/2})$ regret for the transductive setting.  

Oracle-Effcient Online Learning for Smoothed Adversaries
Nika Haghtalab, Yanjun Han, Abhishek Shetty, and Kunhe Yang
University of California, Berkeley
yjiika,,jjan,hhhtty
hrgpaa/llaaa..tttty..mmmarrrrrrr kunbeyang/bberkeleyy.eee
Abstract
We study the design of computationally efficient online learning algorithms under smoothed analysis. In this setting, every step an adversary generates a sample from an adaptively chosen distribution whose density is upper bounded by L/a times the uniform density. Given access to an offline optimization (ERM) oracle, we give the first computationally efficient online algorithms whose sublinear regret depends only on the pseudo/VC dimension d of the class and the smoothness pa- rameter a. particular, we achieve oracle-efficiens regret bounds of O(VTda-
for learning real-valued functions and O OdVTdo +) for learning binary-valued functions. Our results establish that online learning is computationally as easy as offline learning, under the smoothed analysis framework. 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 some settings with binary-valued functions and worst-case adversaries. These include an oracle-efficient algorithm with O (() regret that refines the earlier O ((VT(())) bound of [DS16] for finite domains, and an oracle-efficient algorithm with (/13/4 regret for the transductive setting.
Introduction
Adversarial online learning is cornerstone of modern machine learning and has led 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 Icarnability 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 Icarnability 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, ask
whether efficient offline learning algorithums lead to efficient online learning algo- rithms with comparable regret guarantees, under smoothed analysis?
In more detail, smoothed analysis is a perspective on algorithm design, introduced by [ST04] and formalized for online learning by [RSTI1, HRS20), in which the adversary is restricted to generating an instance at every round from distribution that is not overly concentrated, i.c., a distribution whose
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Regret Bound
Method
Reference
Statistical Upper Bound
Binary
Ó VaT (og((=)))
Prob, Coupling and c-Net
[HRS22, Thm 3.1]
Real-values
0 VdT loy(a-))
Thmn F.1
Computational Upper Bound
Binary
Ô VdTa-1/2
FIPL with Poissumizatio
orccle per mund
Thm 3.2
Real/Binary-valued
0 (Vdd'o-1
Relax-and--K Relax-and-Rmmdomizz Randomize oracle calls per round Construction
Thm 3.1
Alg-independent
2 (VTid//)3/
Thm 5.
runtime / d//a
Lower Bound
Algorithms I and 2
22 (VVTo 1/2
Thm E,
Small-domain
0 ( (V(())))
Cor 3.3
Classical Settings
PTPL. with Poissnnization
Transductive learning
0 (T*/*4//9)
Cor 3.3
Table 1:
In the above table, cl represents the pseudo dimension VC dimension of the hypothesis class H. is the smoothness parameter, and T the number of time steps.
density is upper bounded by 1/o times that of the uniform distribution'. The smoothness of the adversary's actions captures the noise and imprecision inherent in the real world. As 1/ar decreases, so does the uncertainty of the learner about the distribution of future instances. This gracefully captures the expressivity of worst-case instances while circumventing the overly pessimistic nature of the worst-case analysis.
The question of whether offline learning algorithms can lead to online learning algorithms is naturally captured by the oracle-eficiency framework (e.g.. [DHL+ 20, KV05, 16). In this setting, we have access to 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 (1)) computation. Efficient algorithms must then be designed to tap into the existing ERM oracle, using polynomial number of calls and computation.
We aim to design oracle-efficient online algorithms whose regret resemble the statistically optimal regret as much as possible. In particular, under smoothed analysis, these bounds must characterized by offline statistical complexity measures, such as the VC dimension pseudo dimension of 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. Designing algorithms that achieve this is the main contribution of this paper.
1.1
Main Results
We consider online learning under smoothed analysis and 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 hypotheses, as well as a parameter that captures the power of the adversary, i.e., We study both the real-values 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 real-valued case, we design an algorithm based on the Relax-and- and-Randomize principle of [RSS12] that achieves a regret bound of O d(V for smoothed online learning, where d is the pseudo ascudo-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 DoVTdo--/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 improved regret in the binary setting crucially leverages the fact that smoothness over the instance domain X' also implies smoothness over the instance- label pairs X' x v, when the label set is binary (or constant in size).
While we use the uniform distribution as the base measure for ease of exposition, our results also generalize arbitrary known base measures.

---

While these bounds demonstrate sublinear regret that only depends on d and σ. their dependence on does not match the (non-efficient) statistically optimal regret bound of ((VTdlu(L/o) 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 F.
Lower bounds. We further investigate the gap between the computational and statistical regret upper bounds. We present an -inrthhm-iddeeeddeent lower bound for the setting of smoothed online learning that shows that any algorithm with runtime of /d//)) will incur a 52( (2 (T(d/o)1/2 regret. We note that this lower bound demonstrates the same dependence on 1/a as our upper bound (for the binary classification setting under smoothed analysis). We also provide algorithn-depender lower bounds that demonstrate improved dependence on parameter d. and apply to all relax-and- randomize and FTPL-style algorithms.
regret
Improved Bounds for the Classical Settings. In addition to constrained adversaries, our algo- rithms and analysis also imply improved regret bounds for two classical settings, namely, online learning bounded domains with worst-case adversaries and traditional online transductive learn- ing. For worst-case adversaries in binary classification with domain size | we achieve a regret of O( ((T((d)))) improving upon the ((VT))) bound of [DS16]. For online transductive binary classification we achieve regret bound of (TT5/4///4 improving upon the O(T 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
Random Playout for Beyond Worst-Case Adversaries. Our algorithms are based on the random playout design principles, including the admissible relaxation framework of [RSS12] and the Follow- Perturbed-Leatde framework of VK5) We show that this framework useful for analyzing online learning algorithms in the beyond worst-case setting, especially in smoothed analysis. In this setting, smoothness captures a level of predictability about the future. This is made formal by technique from [HRS22] that shows that any sequence of T instances generated by adaptive smoothed adversaries can be seen as a subset of T/a uniformly random instances from X' with high probability. We implement this algorithmically by self-generating random instances and labels stand-in for the future. While the self-generated samples may not include adversary's 's next choice with some probability, these frameworks can be used account for the uncertainty in each step. Furthermore, we show that the inclusion of additional self-generated samples has a small impact on the achievable regret by proving that the regularized Rademacher complexity (which acts as an admissible relaxation) is monotone in the set of generated samples (Lemma 4.1). This monotonicity property leads to regret bounds that gracefully degrade as a small function of 1/a.
Stability, Poissonization and Generalization. To obtain even stronger regret bounds for the binary setting, analysis builds on the notion of stability, i.c., how little the distribution of learner's 's actions changes across time steps. A crucial ingredient in controlling stability is our novel Poissonization technique that randomly sets the number of samples, which appropriately chosen Poisson distribution. This allows us an additional degree of independence that is essential for controlling the loss from one step to the next using information theoretic techniques.
to be self-generated, from an
The stability analysis of the algorithm also depends crucially on a modified generulization error of the ERM, when it is trained uniformly generated training samples and tested on smoothly distributed fresh instances. To bound this, we show a strong conditional independence property satisfied by the coupling from [HRS22]. This is instrumental for bounding the generalization error by allowing to extract smooth variables from a set of uniform variables, which can then be used for symmetrization. We expect that this approach will be of independent interest for future work.
1.3 Related works
Our work relates to several paradigms and approaches to online learnability.
Offcie-Efficient Online Learning. Since the seminal work of [KV05] there has been long line of work elucidating the computational aspects of online learning. [KV05] proposed the influential
3

---

follow-the- follow-the-eeturbeed perturbed- algorithm. [KKL07] consider linear functions and study notions of regret when the learner is given access to an approximate optimization oracle. [KK05] study the transductive learning setting where instances (but not labels) are known in advance and give an oracle- efficient online algorithm. [RSS12] propose a general relaxation framework to develop efficient algorithms based on the upper bound of the value of the game. [DHL-+20] present the oracle-efficient Generalized- -TPL algorithm that is no-regret for a wide range of combinatorial and economics settings, On the flip size, [HK16] show that an Q ((VN) lower bound is unavoidable in general in order to obtain nontrivial regret where the N is the number of actions of the learner. This suggests that one needs to look beyond the worst-case in order to get truly efficient online algorithms.
Beyond Worst-case Approaches to Online Learning. Various notion of beyond worst-case behavior of online learning has been studied in the literature [RSTI1, HRS20, RS13b, DHJ+ BCKP20J. Most closely related are [RST11, HRS20, HRS22J. [RSTI1] studied smoothed analysis of online learning but only gave explicit regret bounds for simple classes such as thresholds. [HRS20, HRS22] both study the notion of smoothed analysis with adaptive adversary and show that statistically the regret bounded by (Toool(////) but do not provide efficient algorithms.
Concurrent Work. In concurrent and independent work, [BDGR22] also gives oracle-efficient algorithms for smoothed online learning. In the binary classification setting, [BDGR22] obtains a re- gret bound of Ö Ö(VTdo=1) using an FTPL-based algorithm. In comparison, our result (Theorem 3.2)
demonstrates a regret bound of Ō(VTTo-)) with strictly better dependence on a. Our regret bound's improved dependence parameter can be attributed to novel technical innovations, including the introduction and careful analysis of modified generalization error and stability via a new coupling- bousling-based argument, and Poissonization approach for relf-generating samples that can leverage information theoretic arguments. For the case of real-valued functions with pseudo-dimension d, [BDGR22] achieve regret Öla VVTd) with Ö(VT) calls to the oracle per round. In our paper, we obtain better regret of order Ö(VTdo using only 2 oracle calls per round ?. Our stronger regret bounds are due to the fact that their algorithm is constrained to self-generating T-long sequences as a stand-in for the future, while we are generating substantially longer sequences that allow us to leverage the monotonicity of Rademacher complexity. Importantly, these novel techniques for achieving improved dependence
also enable to improve on the small-domain result of [DS16] and the transductive learning result of [KK05].
2 Preliminaries
2.1 Smoothed Online Learning
Let X' be the space of instances, y = [-1,]] be the space of labels, and X y be the hypothesis class with pseudo dimension d (See definition B.1 or [AB99] for the definition of pseudo dimension). Let I y y + [0. 1] be a convex loss function with Lipschitz constant G in its first component. We also consider the special case where y {-1,+1] is binary and the hypothesis class H has VC dimension d. this case, we consider the classification loss ((). v) = 10 y)-
We work with the smoothed adaptive online adversarial setting from [HRS22]. We will consider o-smooth adversaries. where a distribution is o-smooth if its density is upper bounded by 1/a 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.
Detinition 2.1 (o-smoothness), Let X be a domain that supports uniform distribution U. A measure Iu on X is a-sooohh if for all measurable subsets C X, u(A) < u(A). The set of all o-smooth distributions on domain X is denoted by (x()))
In online learning with adaptive smoothed adversaries, the learner and the adversary plays a repeated game for T time steps. At each time step f. [T), the adversary chooses a o-smooth distribution Dj" E A A random instance Ia ~ D. is then drawn and presented to the learner. After receiving Tr, the learner predicts its label be Ø. V. while the adversary simultancously chooses y1 E y
SSubsequent to when the first versions of both papers were made available online, [BDGR22] improved their relaxation technique to achieve the same regret bound ours, while still using more oracle calls.

---

as its true label. The learner then suffers loss 1(t,, 31). The above protocol is equivalent to setting where the adversary chooses a distribution D, A(X x )) over labeled instances S, (Zt, yr whose marginal on X' is o-smooth, and the learner simultaneously chooses classifier h2 E E It is not hard see that this equivalence holds for both randomized and deterministic interactions, see [RS14, Section 7.6] for more detailed discussion. We will abbreviate De to Dr when it is clear from the context.
We allow the adversary to be adaptive, i.e., the choice of Dr can depend on the realization of previous instances {z 3/) as well as the learner's previous predictions. We denote with 9g the adaptive sequence of a-smooth distributions D,, Dr the instances. Accordingly, let 2 A()) denote the learner's prediction rule on instance 2t, and let 2 denote the adaptive sequence of distributions 21,... Qr. We denote the expected regret of learner with prediction rules 2 on the adaptive sequence So by
T Σ
E REGRET Do, 2)
E Lo
v.)
inf (((h(z)).
KCH
We remove 2, and 2 from this notation when they are clear from the context.
An important property of smoothness is that it implies a probability coupling between uniform and adaptive smooth processes as first observed by [HRS22]. We will describe these in more details in Section and 4.3. We use both the original result of [HRS22] (stated in Lemma B.1) and introduce a slightly strengthened version (in Lemma C.6).
2.2 Offfine 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.2 (ERM Oracle). For hypothesis class H and loss function I, the oracle OPT (opt)
takes set 3 of inputs S = {(I1, w)bee where (æi, W: E X x y for all E [1] and returns
OPTH,((S)
min NEW
((((z,),)) v.) and (p) E arg min MEH
Uh((z,)
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.3 (Real-valued optimization oracle). For hypothesis class H and two loss functions I" and (b, the oracle OPT takes two sets of inputs S and S' over X x y and returns
OPT H. ( (S; min bER
Σ (((()))))) +
Σ (h((a)))v)) (E'S
(x.8)ES
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 given directly by random process. For the binary setting where y = [+1} and [ 15 1 + v). the above optimization oracle is equivalent 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 1. Though the oracles as defined above are required work on arbitrary inputs, both Algorithms I and 2 from our work only call the optimization oracle instances 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.
The inputs the oracle multisets. Unless specified otherwise, all the sets in this paper refer multisets.
5

---

3 Oracle-Efficient Online Learning
3.1 Learning with Real-Valued Functions
In this section, we propose oracle-efficient algorithm for real-valued functions with regret O(VdT/o). We consider the optimization oracle defined in Definition 2.3 with the loss functions specified by 1" (ÿ y) 2G [ū. v) and (ū y) 1 + y)
We begin by describing our algorithm. At each time step [T], the algorithm draws Ô T==
fresh new instances from the uniform distribution, denoted with V(9, together with their random labels g()) that are drawn i.i.d. from the Rademacher distribution, and treat them as hints for the future. Let SXt) denote the set of labeled instances (V((), E()) Our algorithm then applies the offline optimization oracle two input sequences: one where the real history $1:1-1 mixed with two copies* of ((()) and the current instance is labeled +1, and another, where the current label is labeled -1 Formally, we consider
y1 =OTT (11=-1: S()) S U [(2, ((2,)11))) - OPT (s1=11: S.(( ((x). +1))) (I)
Since the two input sequences to the optimization oracle only disagree on one label, the difference in the optimal errors is always within [-1,+1], thus guarantees Tt E V. Intuitively, Dt. accounts for the gap between the errors of these two optimal classifiers so as to hedge the algorithm's 's bets against which instances will be played next. A formal description of the algorithm is given in Algorithm
The main motivation for the algorithm is the coupling lemma of [HRS22]. It states that sample from any o-smooth distribution can be thought of as generated by first sampling O (ar1) ") samples from the uniform distribution and then selecting one of them. The algorithm thus can be thought of as generating samples from the uniform distribution to account for the uncertainty in the adversary's choice. We will discuss this intuition and the proof of the following theorem in Section 4.3.
Theorem 3.1 (Regret Upper Bound). For any a-smooth adversary 2a, Algorithm I has expected regret upper bounded by (G ((G/Td//o) where Ô hides factors that are polynomial log(T) and log(1/o)) Here G is the Lipschitz constant of the loss and d is the pseudo-dimension dimension of the class. Furthermore, the algorithm oracle-efficiet: at every round I, this algorithm uses two oracle calls with histories of length (TT/o).
Algorithm 1:
Smoothed Online Learning for Real-valued Functions
Input: T
K + 100 100log7] T/o for t x-=1 1 to T do
Receive It. for 1+1,
K do Draw new Uik ~ L(x).
T; h: 1,
Draw new iik ~ [[(--1,+1]]
end
((())
(1:00
(1)
(ikk 1-:+1."
T. OPT (11-1:11) U u [(x,
((xx--1)) -1)) OPT (s S(t) us(() u ((x,, +1)})
10
Receive Ve, suffer loss l(Tr, vt).
11 end
3.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 1 1 * y) We present Algorithm 2 that achieves regret Ō Õ(VT 11/2) with better dependence on the smoothness parameter a compared Algorithm 1.
We use two copies to scale the loss appropriately.

---

Theorem 3.2 (Regret Bound for Efficient Smoothed Online Learning), In the setting of binary classification with o-smoothed adversaries. Algorithm 2 has expected regret that is at most
δ min {VTáo 1/2 ((aXX11))
(min
Furthermore, Algorithm 2 is a proper learning oracle-effccient algorithm: every round this algorithm uses a single ERM oracle call on a history that is of length + O(T/Vo) with high probability.
Unlike the algorithm for the real-valued case, the improved algorithm uses the FTPL framework. The algorithm itself is easy to describe: the algorithm generates random number N from the Poisson distribution with an appropriately chosen parameter, generates N uniformly random points along with random labels and then predicts using the hypothesis that has the lowest error the past data appended with the newly sampled data. On the surface, this algorithm seems similar to Algorithm 1. But there two key differences: unlike Algorithm which uses the difference in value of two optimizations, Algorithm 2 follows the prediction of the hypothesis with the lowest error. This makes Algorithm 2 a proper online learning algorithm. Secondly, unlike Algorithm I which uses decreasing number of random examples over time, Algorithm has the number of samples distributed according Poisson (with the same parameter in each step). The fact that the number of hints is drawn from the Poisson distribution is crucial for our analysis of the stability of the algorithm. We sketch the proof of the regret bounds in Section 4.4.
Algorithm 2: Smoothed Online Learning based on Poisson Number Hints
Input: time horizon T. smoothness parameter a, VC dimension d
+- / Vo, T (x1/dd;;
2 for ( <- to do
generate N7(0) ~ Poi(n) fresh hallucinated samples (3) 7 " ..0)), which are i.i.d. conditioned on with 7 ~ U(X) and V/ ~ ~({+1)); call the ERM oracle to compute h2 + opts,/ (((5)) V Hietoo U yr Breett))
observe Zt, predict Dt hy(xx)), and receive ye. end
While our main interest is on beyond the worst-case adversaries, our results improve upon existing results for worst-case analysis of online learning well. For finite domain and binary-valued loss settings where worst-case adversaries are vacuously o-smooth for 1/a = 12), Theorem 3.2 also achieves an oracle-efficient regret bound of bound of [DS16], because VC dimension d is at most X, and usually much smaller. Similarly, our bound can be instantiated in the setting of transductive learning with | = T, which improves ( vd) bound of [KK05] to 0(T3/4 /44)).
which is a refinement of ((VT)&))
Corollary 3.3 (Regret for Small Domain and Transductive Learning). There is an orucle-efficient algorithm for online learning with binary labels (in the worst-case) that achieves expected regret of O( O( T(d)x))) for any hypothesis class with VC dimension d domain X. For transductive learning with binary labels, there is oracle-efficient algorithm, with expected regret O (T3/>
Remark Both Algorithmss and 2 can adapted to deal with unknown a. In particular, the regret bounds hold for any approximation 5 that is lower bound of the real up constant multiplicative factors. This corresponds to settings where the world more smooth than we give it credit. Even when we have extremely poor upper and lower bounds, can use hedging to still get non-trivial regret with only a minor blow up in computation. We will provide more details in Appendix D) about working with knowledge of approximate ö.
4 Proof Sketches for Main Regret Bounds
Before discussing the proof sketches for the main regret bounds, we will first introduce two frame- works for designing efficient algorithms for online learning.
7

---

4.1 Relaxations and Admissibility
The proof of Theorem 3.1 relies on the admissible relaxation framework proposed in [RSS12]. relaxation Rely is sequence of functions (el)()))1 for each t [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 some relaxation, its expected regret can upper bounded in terms the value of the relaxation at the beginning of the game.
Definition 4.1 (Admissibility). In the smoothed online learning setting, let 2 be an algorithm that gives rise sequence of distributions Q1.-... 2r the predicted labels. We say 2 is admissible with respect to a relaxation (R 1814) 1T for any sequence of instances $1.7,
1. For all t [T].
sup E sup E ( (x) DE mey (i-Q:
" ve)] Rely 1 RHl 812-1),
where Do (X) is the set of a-smooth distributions on X; 2. The final value satisfies Relr(H) | 2 innnen L(h, 81.T).
The following proposition is the analog of the results of [RSS12] when the adversary is smooth. The full proof is presented in Appendix G.
Proposition 4.1 (Regret Bound via Admissibility). In the smoothed online learning setting, let 2 = -Q)..... ¹T) be an algorithm that is admissible with respect to relaxations Relr(H), then the following bound the expected regret holds regardless of the strategies 2, of the adversary:
E|REGRET (2,2 Rely (H (0) + O(VT).
4.2 Follow the Perturbed Leader
When the labels are binary, Algorithm 2 achieves an improved regret using the Follow the Perturbed Leader (FTPL) principle [K [KVO5]. An FTPL algorithm makes predictions by applying ERM oracle to the perturbed historics of the play. At every time step E [T]. the algorithm chooses a distribution
over labeled instances, from which it draws N random instances (z+ . ) (7 17.
-(0)
o00) The
predicted label then given by ÿr- = (zt), where
h - 1. 81:-11
((7)", Du DENN)
The standard analysis of FTPL bounds the expected regret follows:
T
N
E REEGET
<
E
(ho(ass)
v1) ( +
sup NEW im
Σ ((((2.)))) - -
Stability
Porturbation
where h- arg infReH Σn ((h(1)))))))))))))))())) 3t).
Note that the perturbation term is already well-understood from statistical learning theory since is essentially the Rademacher complexity of H for sample size N. Therefore, we will focus bounding the stability term by designing perturbations that can leverage the anti-concentration property of smoothed adversaries.
4.3 Proof Sketch of Theorem 3.1
Elaborating on the intuition laid out in Section 3, we will use the coupling technique introduced by [HRS22] (see Lemma B.I for complete description) to replace the sequence of T' random inputs (x), } generated by the adaptive adversary with T'K inputs ( generated d.i.d. from the uniform distribution over X, such that with high probability { .T)) C {=r* (e,r)_e//A,,AAA This implies that, up to small probability of failure, it is sufficient to consider simpler setting where the adversary is promised pick future instances from larger set of uniformly distributed samples (which we call the set of hints). This setting differs from the standard transductive
that are

---

learning setting [KK05, CbS11] in two significant ways: 1) The set of hints is not revealed to the learner beforehand: 2) the hint set is larger, by a multiplicative factor of K 1/a,, than the set of realized instances.
It turns out that both issues can be handled elegantly in the admissible relaxations framework of [RSS12]. For the first issue, note that the Algorithm 1 can be seen as self-generating hints and although they do necessarily correspond to the adversary's sample, the relaxation-basee argument guarantees that matching the randomness of hints at a distribution level suffices to bound the regret of the algorithm (see Appendix B.7 for more details). For the second issue, our relaxation will be based on a characterization of the uncertainty in the future that is monotone in the set of hints, which we call regularized Rademacher complexity. Formally, for set of unlabeled instances a function Φ H. + R. the Rademacher complexity for set Z regularized by & is defined as
x=){ and
2 2) =
E Ca:l (=1)
sup NEW
(,(2)) + (h))]
We show that regularized Rademacher complexity is monotone as function of the dataset. See Appendix B.2 for proof of Lemma 4.1.
Lemma 4.1 (Monotonicity of Regularized Rademacher Complexity). For any dataset 21.m E 2 and any additional data point X, we have Ri 21:m) I R ( 21mm U {x}).
This monotonicity ensures that using the hint set, which is a superset of possible instances, will still lead to no-regret algorithm.
Finally, the relaxation we use to analyze Algorithm is the expected Rademacher complexity of the union of future hints, regularized by the past total loss, i.e..
Relr(H s1:) = 2G
E V ((
RR-L s1t), v(0)] + 2GBB(T t),
where (h, s1:)) = = (h((x))), vi) for h E H. Here 3 10 o)* o(1/T) represents the penalty caused by the failure of coupling. Once admissibility established, we will obtain regret bound using Proposition 4.1. See Appendix B for a complete proof of the theorem. We remark that the final regret bound can also be stated in terms of the Rademacher complexity which is data dependent and adapts readily to benign structures of the instance domain.
4.4 Proof Sketch of Theorem 3.2
Let Qe be the distribution of the learner's action hy E H in Algorithm 2 and DD denote the distribution of the adversary at time f. The main quantity we will use to analyze the algorithm is the stability
Stability = E
( [L(he, 81) St/DD he
het1~Q.-1 (()h-11,8))).
We analyze this expression by breaking it down into sum of two quantities:
Stability - TV(Q,. E [Q++l)) s,NDD
e, D. [L st L(h411,
E
Mudified generalization errur
Here, R(t) is the fresh randomness generated by the algorithm at the beginning of time t.
In order to see where this expression comes from, note that the first term itself would be an upper bound on the stability, if neither of Q, and Q++1 depend on the new observation s; (I,, ye) at time t. However, while 2, is independent of st, Q does depend on s, because h is trained on st. To overcome this dependence, we introduce ghost sample s/ that allows us to decouple h441 Q and the new observation. This gives rise to the second term which we call modified generalization error. We formally discuss this decomposition in Appendix C.2.
The first term the total variation (TV) distance between Q. and the mixture distribution Ba,-D, [Q++]]. In order to bound this term, we closely use the independence properties of the Poisson distribution which allows us to write an explicit expression for the total variation distance which we can then bound using the -Suslia method. We formally prove this in Lemma C.4.

---

The intuitive idea behind bounding the second term is as follows. Consider the simpler setting of t 1 (i.e. no history) and D, U(X {+1}) (i.e. the new observation s, follows the same distribution as the self-generater samples). In this case, the generalization error is precisely the difference between the test error and the training error with N iid training data, and classical Rademacher complexity gives an upper bound O (vd/N), For general a-smooth D., we establish a strong conditional independence property of the coupling argument 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 realized uniform variables conditional 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 to extract smooth variables from set of uniform variables, which can then be used to for the purpose of symmetrization. We formally prove the upper bound on the modified generalization in Lemma C.5.
Using this bound on stability, we can get bound on the regret of the algorithm using analysis techniques for FTPL. For full proof, see Appendix C.
Remark 3. The proof the modified generalization needs the smoothness of both the covariates x and labels y. This can be ensured with loss of constant in the binary (and generally the finite label space) setting. This is the main reason that this proof does not generalize to the real valued setting.
5 Discussion, Additional Results, and Open Problems
Computational Lower Bounds Our main contribution is oracle-efficient online learning algo- rithms in the smoothed setting that achieve an O(V regret upper bound in the real-valued case, and an O(VdTo-11 upper bound for binary classification. However, neither of these upper bounds is statistically optimal; the statistically optimal regret here is @( / /dT log((//))) [HRS22]. 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 in Theorem E. that the regret of our current family of algorithms cannot be improved by tuning parameters. In addition, we also show the following general lower bound for computationally efficient algorithms. See Appendix E for the proofs and more details.
Theorem 5.1 (Computational Lower Bound for Smoothed Online Learning). For 1/ > d, any proper algoritium which only has access to the ERM oracle and achieves a regret o(min (dd/o)1/2)) for any a-smoothed online learning problem must have an w( ((Vd//o) total running time. Here, the total rumning time refers to the total number of operations performed by our algorithm, in which each oracle call takes unit time, and maintaining each element in the input to the oracle also takes unit time.
Theorem 5.1 implies exponential statistical-compuattiii gap in smoothed online learning: for exponentially small o, achieving the statistical regret Ö( / d (og((/o)) requires an exponential running time. However, Theorem 5,1 still exhibits gaps to our computational upper bounds. We discuss this further in the appendix and present the following open problem.
Open Question. For d/a > T in the smoothed setting, does any algorithm achieving o(T) regret require Opoly(TT.2 2d, 1/o)) computational time given access to the ERM oracle?
Other Constrained Adversary Models Online learning in presence of constrained adversaries is an active research area with several parallel proposed models. While the main focus of our work on the smoothed analysis framework, our techniques extend to several other frameworks and establish a connection between existing lines of work. In particular, our application of the probability coupling technique to hallucinate superset of future instances relates to an extension of the framework of transductive learning (and the literature on hints) to setting where the learner has access to K hints per time step in the future. We call this the K-hints transductive framework and formally address it in Appendix H. More broadly, smoothed analysis also related to a line of work on predictable sequences as it enforces notion of similarity between future instances that holds at the stochastic level. We believe exploring the connections between these various models of constrained and predictable adversaries in online learning is important research direction for the future.
10

---

Acknowledgments and Disclosure of Funding
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 foundattio 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 (COLTT) pages 1786-1786. PMLR, 2022.
[BDPSS09] Shai Ben-David, Dávid Pál, and Shai Chalev-Shwarte 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(51:172 1997.
[CAK17] Vincent Cohen-Addad and Varun Kanade. Online Optimization of Smoothed Piecewise Constant Functions. Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS), pages 412-420, 2017.
[CBS11] Nicolò Cesa-bianchi and Ohad Shamir. Efficient online learning via randomized round- ing. Advances in Neural Information Processing Systems, 24:343-351, 2011.
[DHJ+ 17] Ofer Dekel, Nika Haghtalab, Patrick Jaillet, et al. Online learning with a hint. Advances in Neural Information Processing Systems, 30:5299-53000 2017.
[DLL+20] 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.
[GK06] Evarist Giné and Vladimir Koltchinskii. Concentration inequalities and asymptotic results for ratio type empirical processes. The Annals of Probability, 34(3):1143-123 1216, 2006.
[GR17] Rishi Gupta and Tim Roughgarden. PAC approach to application-specffic algorithm selection. SIAM Journal on Computing, 46(3):992-1017, 2017.
[HK10] Elad Hazan and Satyen Kale, Extracting certainty from uncertainty: Regret bounded by variation in costs. Machine learning. 80(2):165-188 2010.
[НK16] 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 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-ft testing under Gaussian models, volume 169. Springer Science & Business Media, 2003.
[KAH+19 19] Akshay Krishnamurthy, Alekh Agarwal, Tzu-Kuo Huang, Hal Daumé III, and John Langford. Active learning for cost-sensitive classification. 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 Theory of Computing (STOC), page 546-555, 2007.
[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 -56.. PMLR, 2016.
[RS13a] Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. Proceedings of the Conference on Learning Theory (COLT), pages 993-1019. PMLR, 2013.
[RS13b] Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with pre- dictable sequences. Advances in Neural Information Processing Systems, 26, 2013.
[RS14] Alexander Rakhlin and Karthik Sridharan. Statistical learning and sequential prediction, September 2014.
[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.
[RSTII] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic, constrained, and smoothed adversaries. Advances in neural information processing systems, 24, 2011.
[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.
[ST04] Daniel A. Spielman and Shang- -ua 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 Nonparametric Estimation. Springer- Verlag. 2009.
6 Check List
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
12

---

(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "mOzoo8DfMVU", "reviewer": "Reviewer_dbrU", "summary": "\nThis paper considers online learning with smoothed adversaries, which is a special case of online learning. Online learning is a sequential setting in which in round $t = 1, \\ldots, T$ a learner issues a prediction, suffers a loss corresponding to that prediction, and subsequently observes some feedback. The goal is to control the regret, which is the difference between the cumulative losses of the learner and the cumulative losses of the best fixed prediction in hindsight. Normally, the losses are chosen by an adversary or sampled from a distribution. However, in this paper the authors consider a setting in which the adversary generates losses from a distribution that is bounded by $1/\\sigma$ times the uniform distribution. \n\nNon-efficient algorithms for this setting obtain regret bounds of order $\\sqrt{dT\\ln(\\sigma^{-1})}$, where $d$ is a problem specific parameter. The authors provide an efficient algorithm with $\\sqrt{d T \\sigma^{-1}}$ regret for real or binary losses and an algorithm with $\\sqrt{dT\\sigma^{-1/2}}$ for binary losses. \n\nLower bounds for any efficient algorithm are of order $\\sqrt{d^{1/2}T\\sigma^{-1/2}}$ and for algorithms in the same class of the algorithms that are used to obtain the new upper bounds are of order $\\sqrt{dT\\sigma^{-1/2}}$. \n", "questions": "See the weaknesses. ", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n\nThe paper is well written.\n\nThe techniques to obtain the upper bound are nice and could prove useful beyond this paper. \n\nThere are immediate consequences beyond the setting at hand: the regret bounds imply improvements in worst-case binary classification in terms of the domain size and in transductive binary classification. \n\nThe paper is well contextualised.\n\nThe jump in regret bounds from inefficient to efficient algorithms is explained by the lower bounds, although it is not clear whether these lower bounds are tight. \n\n\n\nWeaknesses\n\nThe setting seems to be a natural interpolation between adversarially and stochastically generated losses. However, it also seems to be quite a strong assumption to assume knowledge of $\\sigma$. Is there a reason why in general one can assume knowledge of $\\sigma$?\n\nThe algorithm needs knowledge of $\\sigma$ to draw samples from $1/\\sigma$ times the uniform distribution, which makes me believe that even having a slightly inaccurate $\\sigma$ would lead to profound consequences for the regret bound. Naively trying to learn $\\sigma$ choosing a grid of possible $\\sigma$ and then running an expert algorithm seems quite costly in terms of oracle calls. Is there a more clever approach?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_VOOMWKtTd", "reviewer": "Reviewer_4m7m", "summary": "This work provides so called oracle efficient algorithms for online learning, in the smoothed adversarial setting. This problem corresponds to: given access to an ERM oracle, to design an algorithm whose regret in the worst-case regret under distributions which are $\\sigma$-smooth, is as small at possible. The results of the paper provide $O(\\sqrt{T})$ regret algorithms in this setting, where also the noise parameter $\\sigma$, as well as the VC dimension $d$, appear in the bounds. The paper focuses in the setting of convex Lipschitz loses and binary cases separately. For the former, a relaxation framework (a technique tracing back to [RSS12]) is proposed, which also leverages a coupling technique that exploits the smoothness of the adversary to establish that any smooth sample will be contained who on a larger sample of iid uniform random variables. For the binary case, tighter bounds are obtained via a follow the perturbed leader (FTPL) approach, which also leverages the aforementioned coupling. Several other ideas, regarding the use of a form of regularized Rademacher complexity, stability analysis, etc.; are used. The paper also provides some computational lower bounds, showing that for small values of $\\sigma$, the improved regret bounds of previous work necessarily require polynomial running time in $1/\\sigma$.", "questions": "1. Can the authors add some references on transduction learning, just to point interested readers into relevant literature, to better grasp the results?\n2. Page 15, equation (5). ${\\cal Q}_t$ is used as notation in the equations before it is introduced. I suggest to mention this before the chain of equations, rather than after.\n3. Page 17, line 568. What is $I$? Also I am inferring (but it is not clear from the writing) that ${\\cal E}=(\\epsilon_1,\\ldots,\\epsilon_I)$?\n4. Page 22, Lemma C.6. It was unclear for me (until reading the proof), that $X_I$ is being conditioned on $E,X_{\\setminus I}$. I would suggest writing it instead as $X_I | (E,X_{\\setminus I})$.", "limitations": "Yes, I think limitations of the paper are discussed, and it even points out to an interesting open problem. Social impact is out of the scope of the paper.", "rating": 9, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n1. Strong results, that compare favorably even to concurrent works.\n2. Technically solid paper. Many interesting ideas which may be for independent interest.\n3. Although the motivating question is more conceptual than practical, I still think it is worth of the attention of the machine learning community.\n\nWeaknesses:\n\n1. I find the idea of an ERM oracle quite unappealing. The optimization problems that ERM entail can be quite difficult to solve (specially for binary classification). So, although I believe that the reduction question is interesting on its own, it is hard to believe this model has any concrete consequences for ML.\n2. Bounds depending on combinatorial parameters, such as VC dimension, can be quite pessimistic, and can be majorly improved by distribution dependent quantities, such as margin conditions. Maybe the results of the paper can easily transfer to these more benign characterizations, but it is not evident from the analysis.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5fWU8BiM6b9", "reviewer": "Reviewer_E2JM", "summary": "For online learning with smoothed adversaries, optimal statistical\nregret rates are known, but there are no efficient algorithms. Assuming\naccess to an offline ERM oracle, the present paper develops new\nonline algorithms that are computationally efficient (making 1 or 2\ncalls to the oracle per round, with the input size to the oracle also\nunder control). These algorithms achieve expected regret rates that are\noptimal except for their dependence on the parameter sigma that measures\nthe smoothness of the adversary. There is also a lower bound that holds\nfor the expected regret for any algorithm with run-time below a certain\nthreshold.\n", "questions": "* Could you give examples of offline oracles that are sufficiently\n  efficient to make your algorithms practically feasible?\n* For comparison with the result from Theorem 5.1: what is the running\n  time of Algorithms 1 and 2 in your model of \"running time\"?\n\n", "limitations": "* The efficiency of the algorithms relies on the availability of an\n  efficient offline oracle, but the paper does not discuss for which\n  hypothesis classes such offline oracles are available. In particular\n  for the binary classification case, this might be an issue, since\n  computing the ERM is NP-hard for many common classes.\n\n* The algorithms require knowledge of sigma, which would typically not\n  be available in practice.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* Smoothed adversaries are seeing a lot of recent interest, but to move\n  towards practically relevant results it is essential to have efficient\n  algorithms, which is what the current paper tries to address.\n* The algorithms are elegant reductions to calls to the oracle.\n* Their analysis is clean, and clearly explained.\n\nWeaknesses:\n* I am not sure that the proposed algorithms will be so efficient that\n  they can actually be used in practice, because implementing the oracle\n  might still be a bottleneck.\n* The lower bound in Thm 5.1 seems rather weak because the run-time\n  requirement of omega(sqrt{d/sigma}) does not grow with the total\n  number of rounds T.\n\nRemarks:\n* Line 125: mathcal{Y} cannot be an arbitrary subset of [-1,+1], because\n  the predictions of Algorithm 1 can span the whole range [-1,+1].\n\nMinor comments:\n* Line 101: \"unaviodable\"\n* Line 125: mathcal{Y} should not be an element of [-1,1], but a subset\n* Line 128: For Y = {-1,+1}, convexity and Lipschitzness make no sense.\n  (I assume these requirements do not apply in this case.)\n* Paragraph below Definition 2.1: Equivalence between the two versions\n  of the protocol is not obvious, because it seems to depend on whether the\n  adversary and the learner are allowed to randomize, which is not\n  specified explicitly.\n* Multiple uses of \"arginf\" throughout the paper. Use \"argmin\" instead,\n  because it only makes sense if the minimum is achieved.\n* Line 179: Please specify distribution of \\mathcal{E}^(t)\n* Line 181: \"labled\"\n* Multiple places: \"\\tilde{O} hideS factors\"\n* Theorem 3.2 and Corollary 3.3: regret -> expected regret.\n* Section 4.2: historically, the perturbations for Follow the Perturbed\n  Leader were not of the type described here, so perhaps clarify that\n  your description is a special case.\n* Line 282: please point out that beta is o(1/T). I initially thought it\n  was of order T.\n* Theorem 5.1: please explain how \"total running time\" is measured\n  (e.g., copy explanation from the appendix)\n* Line 522: I think you meant that beta = o(1/T) instead of o(T).\n* Line 841, \"both lower bounds\": there is no lower bound on the regret\n  in Theorem 5.1\n* Lemma E.2: \"supreme\" -> \"supremum\"\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1vjBDQ3vIP", "reviewer": "Reviewer_gcMM", "summary": "This paper considers the oracle-efficiency of smoothed online learning. In this setting, the output distribution of the nature is constrained to have a constant upper bound. Assuming an offline optimization oracle, they give an $O(\\sqrt{T d \\sigma^{-1}})$ regret bound for real valued loss and an $O(\\sqrt{T d \\sigma^{-1/2}})$ regret bound for binary valued loss as their main results. The algorithms achieving these regret bounds are based on FPL. ", "questions": "Can you give more justification on the smoothed analysis setting? Or any concrete example?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The results are sound and solid, and the algorithms and proof ideas are very intuitive. The Poissonization technique is novel and may be of independent interest.\n\nThe major concern I have is on the setting of smoothed online learning. There are many ways to characterize online learning beyond worst-case, and smoothed online learning doesn't seem natural to me. I don't see any practical scenario supporting the smoothed setting, and in theory there are other more intuitive ways: for example assuming noise or predictable sequences. The way that smoothed analysis restricts the distribution of the nature's outputs doesn't make much sense and the constant upper bound seems a very strong assumption.\n\nThe improvement over regret bounds of classical online learning doesn't seem significant: the dominating term $O(\\sqrt{T})$ isn't improved. One may expect a more significant improvement from the strong additional assumption. A (not very relevant) example is that one can improve the regret bound to $O(\\log T)$ assuming an abstention option.\n\nThe paper is well-written and easy-to-follow. It spells out the assumptions, algorithms and intuitions clearly.\n\nThough the results of this paper are solid, due to the concurrent work of BDGR22 which is already accepted at COLT2022, there doesn't seem to be enough improvement and novelty upon it. For this reason (along with my concern on the smoothed analysis setting), unfortunately I tend to reject this paper. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept