Smoothed Online Classification can be Harder than Batch Classification
Authors: Vinod Raman
Unique Subedi
Ambuj Tewari
Venue: NeurIPS 2024 poster (2024)
Keywords: Online Learning
Smoothed Analysis
Primary area: online_learning
TL;DR: We show that online classification under smoothed adversary is as easy as iid batch classification when the size of the label space is bounded, but can be harder than iid batch classification when the size of the label space is unbounded.

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

Smoothed Online Classification can be Harder than Batch Classification
Vinod Raman Department of Statistics University of Michigan Ann Arbor, MI 1840 vkramanQumich edu
Unique Subedi
Ambuj Tewari
Department of Statistics University of Michigan Ann Arbor, MI 48 104 subedi @umi ch. edu
Department of Statistics
University of Michigan Ann Arbor, MI 48 104 tewaria@umi ch edu
Abstract
We study online classification under smoothed adversaries. In this setting, at each time point, the adversary draws example from distribution that has bounded density with respect to fixed base measure, which is known apriori to the learner. For binary classification and scalar-valued regression, previous works (Haghtalab) et al. 2020 Block et al., 2022] have shown that smoothed online learning is as easy as learning the iid batch setting under PAC model. However, we show that smoothed online classification can be harder than the iid batch classification when the label space is unbounded. In particular, we construct a hypothesis class that is learnable in the iid batch setting under the PAC model but is not learnable under the smoothed online model. Finally, we identify condition that ensures that the PAC learnability of hypothesis class is sufficient for its smoothed online learnability.
Introduction
Classification is canonical machine learning task where the goal to classify examples X' into one of the possible classes in V. There are common classification settings based on how the data is available to the learner: batch and online. In the batch setting, the leamner is provided with fixed set of training samples that used to train classifier, which is then deployed to make predictions on new, real-world examples [Vapnik and Chervonenkis, 1971 Natarajan 1989.. On the other hand, data arrives sequentially in the online setting and predictions need be made in each round [Littlestone] 1987 Daniely et al. [011]. The batch setting often studied under the iid assumption, whereas the stream
be fully adversarial in the online setting.
For binary classification (i.e. | = 2), the batch learnability of hypothesis class C y under the PAC model |Valiant 1984]] is characterized in terms of a combinatorial parameter called the Vapnik- Chervonenkis (VC) dimension of H. On the other hand, the Littlestone dimension characterizes the learnability of H under the adversarial online model [Littlestone] 1987 David et al. 2009). As Haghtalab et al. 2020) remark, the latter characterization is often interpreted as an impossibility simple classes like 1-dimensional thresholds have infinite Littlestone dimension. This hardness result arises mainly because the adversary can deterministically choose hard examples, possibly adapting to the learner's strategy. One way eircumvent this hardness result is to consider a smoothed online model, where the adversary has to choose and draw examples from sufficiently anti-concentrated distributions [Rakhlin al. [011] [Haghtllb]] 20188] Haghtalab et al. 2020 Block et al. (2022). This idea is inspired from the seminal work by SSpielaan and Teng [2004]. who showed that the smoothed analysis of the simplex method yields polynomial time complexity in the input size, instead of the known worst-case exponential time complexity.
result because
Equal Contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In smoothed online classification, a learnr plays a game with the adversary over T E N rounds. Before the game begins, the adversary reveals a base measure μ over X' and an mnticonncetration parameter > 0 to the learner. The distribution je can be fairly non-informative such as uniform when applicable for X. Then, in each round E (T), the adversary picks a labeled sample (Iz, yt) E XXX; where 22 is drawn from a amsooohh distribution it with respect to p.. That is, (B) S p(E)/a for all measurable subsets E' in X. The adversary then reveals 2t to the learner, who makes a prediction Un E V. Finally, the adversary reveals the true label y/: E y and the learner suffers the loss ( + 3. Given a hypothesis class H C y the goal of the learner is to minimize the regret, the difference between its cumulative loss and the best possible cumulative loss over hypotheses in H.
The smoothed online model interpolates between the iid setting (a = 1) and the adversarial setting (a = 0). When | 2. | (2018) and Haghtalab et al. [2020] showed that all VC classes are learnable in the smoothed setting with the regret O(yT' VC(H) log (T/a)). Extending this
result to real-valued regression, where y = [-1, 1J, with the absolute-value loss, Block et al. [002] showed that the finiteness of the fat- fat-shattering dimension (Bartlett al., 1996 Alon et al.) 1997| of
H. S yd is a sufficient condition for smoothed online learnability. Since the finiteness of VC and fat-shattering dimensions are characterizations of learnability under the PAC model, these results suggest that smoothed online learning may he as easy as batch learning.
In this work, we study smoothed online classification for arbitrary label spaces y under oblivious adversary- - one that picks o-smooth distirbutions V1, .., Vr, samples 21 ~ V/..... 2T ~ VT indepen- dently, and finally picks the labels .1..... yr, all before the game begins. This obvlious model has been studied in the past Wu et al. 2023]. but is slightly different than the one studied by (Haghtalab) 2018 Haghtalab et al. 2020 Block et al. 2022 (see Section 2.1 for more details). For this model, we show that smoothed online classification continues to be as easy as batch classification when [}]] < co. However, when | is not finite, we show that smoothed online classification can be harder than batch classification. We note that there has been recent interest in studying multiclass learnability when [)'] is unbounded [Brukhim et al. 2022 Hanneke et al. 2023 Pabbaraju 2024]. Studying infinite label spaces is important for understanding when one can establis lish learning guarantees independent of the label size. This is quite a practical question many modern machine learning paradigms have massive label space, such as in face recognition and protein structure prediction, where the dependence of label size in learning bounds would be undesirable.
Theorem (Informal) Let X' = [0. Then, there exists H. C y that is PAC learnable but not learnable in the smoothed online setting with μ = Uniform(X') and o 1. 1.
We also provide a quantitative version of this theorem that shows a regret lowerbound linear in T even when | Do but bigger than 2 log(T), Note that this is tight up to a factor of log T because we prove a sublinear upperbound long as | = 20(T) in Section 4 To prove these results, we exploit the large size of the label space to construct a hypothesis class H C y such that for every h E H. its output on a finite subset of X' effectively reveals its identity. We then show that such hypothesis class has a sample compression scheme of size 1. Then, the result "compression implies learning" by David et al. 2016) shows that H. is PAC learnable. However, we show that even the adversary that generates iid samples from Uniform (X) can construct a difficult stream for the learner. Our construction inspired by the hypothesis class from [Hanneke et al., [024 Claim 5.4]. However, a key challenge in our construction is the fact that the adversary does not have full control over the sequence of examples the learner will observe (due to a s-moothhess)) whereas the adversary in Hanneke et al. [2024] can pick hard examples deterministically.
In light of this hardness result, we identify sufficiency condition for smoothed online learnability. To do so, let B(U,,) denote the set of all a-smooth distributions with re- spect to n.. For any T1,--.,Iy, d, (.h,,, h2) =n= n Ei=1 (x.) # h2(x,)). Define (=, H. d,) to be the covering number of H. under metric dz.- Then, H. is said to have uniformly bounded expected empirical metric entropy (UBEME) if n sup,,... EB(,,o) Bra-vrn [N(s, H. d,)] < oc for every fixed > O. We show that if H has the UBEME property, then it online learnable under smoothed adversaries.
X, let define an empirical metric on d, on H as
Theorem (Informal) If sup,eN sup E((..) Ezi...... (e, H. dw)) < oo for every fixede, > 0, then H smoothed online learnable under the base measure μ.
2

---

When [ 2, Haussler's packing lemma implies that (ie, H, dn) S (41=-1) VC(R)
[Haussler 1995]. That is, every class with finite VC satisfies UBEME, and thus our sufficiency condition recovers the result from Haghtalab [2018] on the smoothed learnability of VC classes. For [ oc, we generalize the packing lemma to show that.W(e, H. dm)) < ( 22 1i GG(H) where G(H) is the graph dimension of H. This inequality shows that PAC learnability of H is sufficient for its smoothed online learnability when [ < oc.
A key contribution of our sufficiency result is going beyond VC and Graph dimension and giving the weaker sufficiency condition than the worst-case empirical entropy. Indeed, in Section 4 we show that our sufficiency condition still provides meaningful upperbounds even when the VC and Graph dimensions are infinite. To prove our sufficiency result, we show that UBEME implies the bounded metric entropy of 76 with respect to the base measure μ. That is, for (g h2)
Ph [() (x)) jf h2(x)). we have (e, H, dy.) < oo for every fixed é >> 0. Then, we use algorithmic ideas from [aghtalab| 2018) that involve running multiplicative weights using the cover of H under dy- Unfortunately, when |>| is unbounded, the sufficiency condition (the UBEME of H) is not necessary. This is demonstrated by constant functions H = {i + a: :::00 a E N} that is easy to learn but (s, H. d1) 80.
Given our separation and sufficiency results, it is natural to ask for characterization of learnability for smoothed online classification. Any meaningful characterization must be joint property of both H. and μ.. This is because choosing ya to be a Dirae distribution will make any H. even the set of all measurable functions from X' to V. trivially learnable. Since the most natural joint complexity measure of H and μ is (ee, H. d,)., one might ask whether (ee H. dy)
for every ε >> 0 is necessary and sufficient for smoothed online learnability of HH under μ.. Surprisingly, we show that this condition is neither necessary nor sufficient (see Theorem 4.3) These results highlight the
difficulty of characterizing learnability in the smoothed setting.
2
Preliminaries
Let X' denote the instance space and y denote the label space. We assume that (X' Σ) is a measurable space and let II(X) denote the set of all probability measures on (X, Σ). Let H. S yd denote an arbitrary hypothesis class consisting of predictors : X + y. For any T E N. we use the notation N).
21.r to denote the sequence {2, [T)) Finally, we let [N] =
2.1 Smoothed Online Learning
In the smoothed online model, an adversary plays a sequential game with the learner over T rounds. Before the game begins, the adversary reveals a base measure l E IT()') and a scalar a > 0 to the learner. As mentioned before, ja can be non-informative measures such as uniform if 2 is totally-bounded. Then, in each round f E [?']. an adversary picks a labeled sample (Iz, 3t) E X' x ), where x; is drawn from distribution V E II(2') that satisfies (E) < k(E) for every E E E. The adversary then reveals 2, to the learner A. Using all the past examples
(5)),,,,,,,,,1,,,)))) the learner then makes potentially randomized prediction A(xx). The adversary then reveals the true label y/ E y and the learner suffers the loss (AA(z)) * ye). Given hypothesis class H C y the goal of the learner is to output predictions A(v,,) that minimizes the regret, which is the difference between its cumulative loss and the best possible cumulative loss over hypotheses in H. To formally define the regret, let B(H, o) := {u 11(x)= : =vE)) < u(E)/o VE' E Σ} denote the set of all a-smooth distributions on X' with respect to Given H C ) the worst-case expected regret of an algorithm A is defined as
1).
]
Σ EBI(A(E + v0l inf Σ (h(x)) + wi) KEH
Rd (T,H): == sup
E My..... B(H.a) FITMET
sup MLT
Note that + O, the set B(μ, σr) contains all Dirac distributions on X. This amounts replacing supm.... B(p.o) Ex Exrrr<rr [-] operator in the definition of regret above by sup which yields the expected regret of A the fully adversarial model under an oblivious adversary. Thus, our adversary is generalization of the online oblivious adversary for the smoothed setting. Given this definition of expected regret, we adopt the minimax perspective to define the learnability of hypothesis class.
3

---

Definition 1 (Smoothed Online Learnability). The class H _ y* is learnable in the smoothed online setting if and only for every a and μ II(X), we have inf R (T, H) = o(T).
Our worst-case expected regret is defined with respect to an oblivious adversary that picks the entire stream (I1, y1), (Ir, 1/r) before the game begins. Moreover, the sequence of distributions Ui,..., Mr has to be chosen upfront before the sampling step (Z1,...,,yy ,T) ~ (V2,.... pr). That is, the distribution V/2 cannot depend on the realization of previous instances 21:-... 24-1- This ensures that the instances 21...... 2T are independent random variables. One can also consider an oblivious adversary, where it can depend on the past instances (a1,--. - sampled from (#1,... 4t 1). Since the primary contribution of this work is the hardness result in Section 3 we only focus on the case where P1:...; MT are chosen upfront. As the first adversary is special case of the second adversary. our hardness result also applies for the second adversary. The fully general setting of adaptive adversaries where V4 can depend on the entire history of the game up to time point has been studied extensively in [Haghtalab et al. 2020 Block et al. 2022]. where the dependence among F1, ....... Tr handled through coupling.
There are three natural choices for how ye may be selected by an oblivious adversary. In the first choice, Yt may depend only the xt vt. In the second choice, yt may depend on prefix 21 U1,,,,, 3y. ~ V/. Finally, in the last choice, 1/+ may depend on the entire sample 41 <> V1, .... TT ~v My. The first choice is considered in Haghtalab| (2018)am) and the second by Haghtalab al. (2020), Block ct al. 2022]. In this work, we tocus on the third choice, which has been considered by Wu et al. 2023 This choice is natural because a-smoothness is just property of the instances and should not impact how the labels are selected. Since the third choice is the strongest, our sufficiency result in Section 4 holds for the first two choices. However, establishing the separation result for the first two choices remains an open question.
2.2 PAC Learning and Sample Compression Schemes
In contrast to existing work, we establish a separation between smoothed online learnability and batch learnability. The notion of batch learnability we consider PAC learnability, a canonical model in statistical learning theory. See Appendix A for complete definition. To prove the agnostic PAC lcarnability of hypothesis classes, we use the relationship between lcarnability and the existence of sample compression schemes.
compression scheme (n., p) consists of a compression function K. and a reconstruction func- Up>1 (X x y) + U:21 x 2) maps a sample 5 = U (X' x 3/1 y takes 5" as input and outputs a function f E y We define the size of the compression scheme (Is, p) on a sample 5 to be [.',, where x(S) S'. We let the quantity k(n) denote the maximum size of the compression scheme on all samples S such that |S] = n. A hypothesis class H C ) has a compression scheme (x. p) of size k(n) if for every sample S = {x) ((xx)))))) )),))) ..... (In, h(r,)) })} for
tion p. The compression function ((11,31), (In,yhh } to a subsample S' C S. The reconstruction function
some h E H. we have f p({(S) such that
f(x:) = l(x:)) for all E [r]].
The compression scheme in David et al. 2016 is slightly more general their compression function i can output (S', b) where b is a finite bitstring. However, the restricted notion of a compression scheme without b is sufficient for purpose. The following Theorem shows that the existence of sample compression schemes for H implies agnostic PAC learnability of H.
Learnability [David et al. 2016). Let (R., p) be a sample compression scheme for H S yx of size k(n) and define Is p(st()) for any S (X x )) Then, for every D on X x y) and n. E N such that k(n) S n/2, with probability at least - 8 over S E D", we have
Theorem 2.1 (Compression
k(m) log a k(n)
+ k(n) + log 1
E [1(ss()) # Fu]] S inf E (1((x) # vl1 100g bEH (x.))D
(2.0)
n
2.3 Covering Numbers, Metric Entropy, and Complexity Measures
In Section we provide conditions for which a hypothesis class H is online learnable under smoothed adversaries. While sufficient conditions for lcarnability are typically established via combinatorial

---

dimensions, our sufficient conditions will be in terms of covering/packing numbers of H. using distance metric that depends on the base measure μ. This discrepancy with existing literature is due to simple observation: any parameter of H. alone cannot characterize smoothed online classification. Indeed, if one takes the base measure ja to be a Dirac measure, then every H _ yx is trivially online learnable under smoothed adversary. Accordingly, any meaningful characterization of smoothed online classification must be in terms of both and p.
To start, we first define e-covering numbers for generic metric spaces (G,d).
Definition 2 (Covering Number). Let (g, d) be a bounded metric space. subser G' C G is an c-cover for with respect to d for every g E 9, there exists an g' E E such that d(g. g') S The covering number of G at scale e, denoted M(s, G, d), is the smallest n E IN such that there exists an E-cover of & with cardinality n. That is, [e, G. d) == inl [19] G' is an 6-cover for 9}.
The metric entropy for (G, d) at scale E >> is defined as log W(s, G. d). In this paper, we consider the metric space (H. d,) where H. _ y²* is a hypothesis class and (h1, h2) Pezp [hr(x) # (z))) for some (Tx).. The key complexity measure in this work is
Co (H, ()) == sup sup neN EB.B)) VI
E
[We,, H, d
where Pu denotes the empirical measure over Zim- At a high-level, (2, μ1) measures the com- plexity of H. in terms of its average empirical covering number, where the average is taken over processes from B(H, or. Using Ce (H. p)), we define the property of uniformly bounded empirical metric entropy.
Definition 3 (Uniformly Bounded Empirical Metrie Entropy). A hypothesis class H. C y has the Uniformly Bounded Empirical Metric Entropy (UBEME) property with respect to μ if Ce (H, μ)) < oo for every E, 0.
In Theorem we show that H is online learnable under smoothed adversaries if H enjoys the UBEME property with respect to the base measure J..
3 PAC Learnability is Not Sufficient for Smoothed Online Learnability
In Section 4 we show that the PAC learnability of H is sufficient for its smoothed online learnability when | co. Here, we show that this is not the case when [ is unbounded by constructing a PAC learnable hypothesis class that is not smoothed online learnable. In fact, prove stronger result.
Theorem 3.1. There exists a hypothesis class H. C y such that following holds:
(i) H has a compression scheme of size
(ii) For μ = Uniform((X) X) and a = 1, we have inf R (T, 7. 2 T 2
The part (i) of Theorem 3.1 together with Theorem 2.1 shows that H is agnostic PAC learnale with
error rate E(5, n) = O log 1og(1/6) On the other hand, based on Definition 1 part (ii) shows
that is not smoothed online learnable. Together, we infer the following corollary.
Corollary 3.2 (Agnostic PAC Learnability t> Smoothed Online Learnability). There exists S )x such that H. is agnostic PAC learnable but not learnable in the smoothed setting under μ Uniform( (X) and a
When D/| < 0o. the existence of a ((1)-size compression schemes and agnostic PAC learnability are equivalent (David et al. 2016). Thus, there no qualitative difference between Theorem and Corollary 3.2 However, when | oc, recent work has shown that the multiclass PAC learnability
does not imply the existence of (()-ssiee compression schemes (Pabbaraju 2024]. Thus, Theorem 3.1 is a qualitatively stronger result than Corollary 3.2 Moreover, our proof of Theorem 3.1 below provides an explicit PAC learner for H.
Proof. (of Theorem 3.1 Let X = [0,1]. 1). Given a bitstring = (0),... 0,) E {0. 1)x) define 0st == (0....., 01) and Ozt = (0) 0c-1) for any t {l...., n). Fix N and ordered
5

---

sequence (21, F2, kn) E x such that 2, # 2, for all o j. For every 0 E {0, define
h1 (.. (x) = { (II).... ,, 0n),
if Et E [n] otherwise
such that 3t
((01 ((#1....., In),
Let On == ,( ,2,...,,T.) E X" I, # t be the set of all ordered sequences of length n with distinct elements. Then, we define our hypothesis class to be
H = U MEN (EL (E(0.))"
U
U
{ (
Here, the label space is y : UhEN (ree((iage(h)] For any y E Y, let us define y/1] and y|2] to be the first and the second entry of the tuple y respectively, Note that y(1] E Om for some m E N and v(2) {0, 13 for some & S m.
Proof of (i). We now define a compression scheme (K, p) of size 1 for H.
(2' x D/ - X' x y as follows. Given any realizable sample = { (x1, 21 91), ..... (In, Un)} } of size n E N, the function k outputs x(S) = (111.1) if yx2
Define a compression function
for all E [n]. On the other hand, if there exists yi such that y/ E {0, 13 for some E N. then x(S) = (e)) Here, E [r]] the index such
that yo [2] is the longest binary string among all i [r] for which y.(2] /
Define reconstruction function x
x y - H. as follows. Given an output of the
compression function {(x, y)}, the reconstruction function outputs p (1 y}}) 0 y[1] E H if y|2] = Here, O is all O's bitstring of length equal to that of the tuple y|4]. On the other hand, if r/2] E {0, 1}. for some t S [y[1]], then output p p(f(2, 8)1) = h [[1
E H. where
is an arbitrary bitstring of length s(1] such that 0g.- = =2]]
Next, we show that (K, p) is valid compression scheme for H. Let S= (111 v1), (2n Dn)) (X x y)" denote any sample of size n that is realizable by H. We want to show that f= (( satisfies fxxx) = yı for all i E [n]] Since S is realizable by H. there exists m E N, (Z1, 7m xm such that 2, * 2j for all j. E [m]] and 3 E {0. } such that h.8
(s (x:)= = y for all [n]. By definition of H. for all i E [na]. we have yu [1] = (Z1..... : 2m) and [2] E {+, 8c1} for some
(1:)
t $ m. Given a realizable sample S, there are two cases to consider: (a) [2 * for all [n] and
(b) there exists i E [1)) such that [x] #
If we in case (a), then we know that v, & {=1,..., 2m) for all i E [m]. Moreover, have k(S) = ((11, }1}} where y1 [1] = (Z1,.... .i....,,,, 2m) and yı = *. By definition of the reconstruction function, ((((11))1))
h "m)) Since I, & { 3m by definition of he hes........" we
have 1.0 (e).......) (I:a)= = ((=1...., km);*) yi for all i E [m]. Thus, (K, p) is valid compression scheme for H in this case.
Suppose (b) true. Define Is = {i E [n] 91 [2] + x). Since h/@ ((z.......)) is consistent with the
sample S, we must have y [2] = 3e [2] for each E Is. Here, [2]2]] is the length of bitstring y [x]
Let E Is such that [ye[2] 2 [ for all E Is. By definition of the compression function K, we have x(5)= { y4)) }. where de [1] (#1,.... ... 2m) and y [2] [g] Let 0 E {0, 1)"h be the completion of y [2] such that the reconstruction function returns p(((ze, (c)}) h (s........) By definition of p. we have Agt = 0c. for L = 1 [2]. To complete our proof, it suffices to show that 1 (..........
(xra) = Yi for all é E [m). There are two cases to consider: i E Is and i $ Is. When & Is. we have I, & {21,..., } and thus hleammeee (z.) = (2)).....mm).*) = y/- As for the index i E Is. we must have that I E {zI...., ... 2m Otherwise, y4[2] would be equal to *, contradicting the fact that E Is. In fact, by definition of h that, for all i E Is. we have ((
(ZT...)))) we have I; = 2/1.1211 This implies
h6 (s (2)122) = ((21, 2m), (gl =
((21,..., 2,)), B51. (1]) = y/. Here, we use that [2: S | for all i E Is and the fact that 8gi= Ber for all t [2]] Therefore, we have shown that ( (z:) y, for all i E [n].
Proof of (ii). Let f Uniform((0, 1)). We now specify the stream ((r,, ye )) to be observed by the learner. For the instances, we take Z1, ...., .T is to be iid samples from p. Note that 21...., PT

---

are distinct with probability 1. Moreover, as all the instances are drawn from the same distribution μz this adversary o-smooth for To specify y1..... Mr, we first draw 0 Uniform( ((0. 1] ) and define y/+ ((11.... TT), Qee) for all & (7]. Given distinct .1,..., ..,,.,, Tr, for any algorithm A.
we first show that
EEN(A(O) # uil
T
E frJUniform( (0.1)7)
inf bEH
Σ (M(a)) vn) 1
(1)
The probabilistic method implies the existence of A E 10" such that the claimed bound of T/2 holds. This subsequently implies that, for distinct ,
RT, we have
T Σ EELH((())) + #
T
T
inf Σ MER
11((z,) + vit
sup UITT
2
t=1
Finally, using the fact that I1,
FT ~ a are distinct with probability 1, we obtain the bound
inf RM tha (T,
2
E
sup UITT
Σ B (A(())))) #ill
inf Σ MEN
(h(x)) + vi
2
T
2
To complete our proof, it now suffices to prove Equation [I. lowerbound on the expected cumulative loss of the algorithm A is
Fixing distinct F1,...,I1, the
E
E e (0..7))))) [(((((()))) + #nll
E
E D2
[[{((x)) # (III...,,,)).0 A
1 _ {A(x)) # (#121 (0 1))3
2 (A(x)) +
T
2 2
At a high-level, we use the fact that 0g is sampled uniformly at random from {0, 1} and is independent of as well as for all i # Thus, on each round, the algorithm cannot do any better than randomly guessing the value of 6, Next, we upperbound the expected loss of the best-fixed function in hindsight. Given distinct æ1,..., FT and {0, 13", we can pick the hypothesis "[ (()....Zr)" By
definition of this hypothesis, we have h/ (r) (xx) ((21...., ZT), A.e) distinct F1, 2T, have
yc. Thus, for every
E inf Σ (h(())) # #vd KEH
5
E 6n.Uni(((
Σ 11 ( # vi3 0.
Finally, equation 11 follows upon combining the lowerbound the cumulative loss of A and the upperbound on the cumulative loss the optimal hypothesis in hindsight.
To prove the qualitative separation between PAC and smoothed online learnability in Theorem 3.1 required y to be unbounded. The following theorem, proved in Appendix shows the quantitative dependence of the regret | when it is bounded.
Theorem 3.3. For every K N, there exists H. C yx with |)] K such that H. has a compression log K scheme of 1, but A R (T, H) 24 log K for μ Uniform(XX) and =
Theorem 3.3 shows that one can get quantitative separation whenever K > 2Tgog
4 A Sufficient Condition for Smoothed Online Classification
In this section, we provide a sufficient condition for smoothed online classification. Our main result provides a quantitative upperbound on the expected regret in terms of Cs,o (H, μ).
7

---

Theorem 4.1. For every H _ y", E (I() and o > O, we have that
inf R (T, S inl 620
eT
+ Moog(Ce (H,
0
Theorem 4.1
shows that as long as H satisfies the UBEME condition with respect to μe, is online learnable under smoothed adversary. As corollary, we also establish the following sufficient condition in terms of the Graph dimension, a combinatorial dimension characterizing PAC learnability when | oo (see Appendix A for complete definition) (Natarajan 1989 Corollary 4.2. For every H. S EV (T())) and a >> 0, we have that
cT + + G(H) log 62
4111
41T |
inf R (T,H) S 6 inf E>0
= 12 T G(H) log /
o²
where G(H) denotes the Graph dimension H.
E shows that PAC learnability of H is sufficient for smoothed online classification whenever y
Corollary 4.2 whose proof is in Appendix
oo. When |J] 2, this bounds, up to constant
factor, recovers that from Haghtalab [2018]. We now proceed with the proof of Theorem 4.1
Proof. (of Theorem 4.1 Let ....... MT E B(u, or) denote the sequence of o-smooth distributions picked by the adversary. Fix a >> O. Then, by Lemma B.2 we have that N(s, H. dyy) S o. (H, p). Let 7'' C H denote an E-cover with respect to du of size at most C5.0(H. μ). Let A denote the online learner that runs the Randomized Exponential Weights Algorithm (REWA) on the the data stream (21, y1),..., (2r.8r) using H1' as its set of experts. By the guarantees of REWA,
Σ (A(x)) # mm
inf NEW
(M(()) # me + v 2T log((?t')
S inf NEW
1(1(zs)) + v1 + 2T log(CC
Σ 1(((,)) + MEH
inf
we 33 + sup inf Σ (1t((x)) + h(xz)) + 2 log(O (H, (H, m)) NEW N'W
t=1
where the expectation is only taken with respect to the randomness the REWA and the last inequality follows by the triangle inequality. Taking an outer expectation with respect to the process
FiT ~ VI,T, we have ΣT 1(A(x)) + vib] is at most
Σ (h)())) * Maa) + 2T log(C (H, (H,,)).
E
inf REH
1fh(r)) + ve
+
E P1I
sup inf NEW EH
SLTOMET
It remains to bound E
suPnem inf Σi (1 # Mxxa)] We provide sketch of the
proof here and defer the full details to Appendix D Consider the class G = {x (1h((z) + h(z)) E H., where h E H' denotes the s-cover of with respect to dus and note that
T
sup inf NEW N'EW
((
S
E BLTTOET
sup gEn
Σ g(an)
By standard symmetrization arguments, we get
E
sup gEG
g(xz)
S sup gEg SITTET
Σ g(tt)
+ 2T
((G, 21TrreT
21-~~11
where "(G) is the Rademacher complexity of G (see Appendix Note that 9 C HAH where HAH == (I + (z)1(z) * h2(x)) h1, h2 H}. and thus RG I RHHHH, x Using
8

---

the discretization-biie based upperbound (Lemma A.1) on the empirical Rademacher complexity and relation between the covering numbers of H. and H.H (Lemma B.3 we have
2 log (e, HAH, Ppr)
2 log N(e, HAH, d
log.N H, dwr)
((HAH, S
SEtV
S
T
T
T
Plugging in the upperbound on the Rademacher complexity and using the change of measure, a-smoothness, and the definition of H' on the first term gives
ET
E² H, (
dyr dyr ))
E
sup 9E9 t=1
(at))
<
2 + 4 T log
E FITMUTT
N
Using the definition of Ce.o (H, 14) to get
E F1
sup inf bEH NEW! t=1
(1)(()) # Maxe)
ET + 2: 4 log C2 2.0 (H,
substituting into the regret bound for A, and doing some algebra completes the proof sketch.
Our upperbounds in terms of expected empirical covering numbers can be meaningful even when VC and Graph dimension of H. is infinity. As simple example. let X' = [0. 1]. l Uniform(X'), and consider the binary hypothesis class H. {ar + 1fx E A} hard to see that VC(H) = oc. On the other hand, C. (H. μ)) = 1 since for every n E N, the sample Fi:n ~ y does not lie in Q almost surely, and when F1:m & Q. da., (h1, h2)
C Q |A| < oo It's not too
for all h1, lr H.
To prove Theorem 4.1 we show that the UBEME implies a bound on the metric entropy (e, H. d,)). is natural ask whether the finiteness of (s, H. d.). for every ε 0 alone is necessary and sufficient for smoothed online learnability. Unfortunately, it is neither sufficient nor necessary.
Theorem 4.3. Let X = [0, 1] and μ = Uniform(X)) Then,
(i) There exists a H S {0, 13x such that (s, H. d,) 1 every > 0 but R (T, H) for every 0.
(ii) There exists H S N such that (e, H, d,) 0o for every but inf R (T, H)
O (og()) for every a 0.
< )c). Note that for every h1, h2 H. have that d,, (h,, h2) PP P2-z (x) # h2(2)] since h; and h2 disagree on at most finite number of points in X. Thus, for every > 0, H is trivially coverable using exactly one hypothesis in H. To show that R (T, H) _ for every a O, consider the adversary that picks 1/2 for all t E [T]. The process F1.T ~ V1.r is then an iid draw from p of length T. Consider the data stream (æ1, 11), .... (2T. where F1.7 ~ 1t" and y/ Unif( (0. 1)) for every t E [T'. Such a stream is realizable by H almost surely since the the sequence of instances F1.7 are all distinct with probability 1 and there can be at most finite number of timepoints where y/ 1. On the other hand, any learning algorithm A must make at least T 7/2 mistakes in expectation (with respect all sources of randomness), since the labels ye Unif( (0, 1)). Thus, by the probabilistic method, for every learning algorithm A, there must exist a sequence of labels V1.7, such that AAs expected regret is T/2.
Proof. We first prove (i). Consider the hypothesis class H = (x+ fx E S::
We now prove (ii). Let H - ( teaaa E N} be the class of constant functions. Note that since hı and hą disagree everywhere on X. Thus, for every < 1, we have that WiE H. d = oc since HH| oc. On the other hand, the Littlestone dimension of H is 1. Thus, by Theorem from Hanneke et al. [2023), we get that inf R (T, H) ( /logg T)) for every > 0.
for every bı h2 E H. we have that du du f2)
5 Discussion
In this work, we show a separation between the learnability of Hf S y in the PAC setting and the smoothed online setting when [}] is unbounded. We also provide a sufficient condition for smoothed

---

online learnability under any base measure However, as noted in Section 4 not necessary for the smoothed learnability of H. Thus, an important open question to find condition that is both necessary and sufficient for smoothed online learnability. Traditionally, in learning theory, learnability is characterized in terms of a combinatorial property of just the hypothesis class H C y However, the property of HH alone cannot provide a characterization of learnability in the smoothed online setting. Choosing μ to be Dirac distribution will make any H. even the set of all measurable functions from X' to Vi trivially learnable. Thus, the characterization of learnability must necessarily be a property of the tuple (H, u). To that end, we pose the following question.
our sufficient condition
Given (H. p), is there complexity measure that characterizes the smoothed online learnability of H with base measure μ
Acknowledgments and Disclosure of Funding
VR acknowledges the support from the NSF Graduate Research Fellowship Program.
References
Noga Alon, Shai Ben-David, Nicolo Cesa-Bianchi, and David Haussler. Scale-sensitive dimensions, uniform convergence, and learnability. Journal of the ACM (JACM), 44(4))615-631, 1997.
Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999. doi: 10. (0.107/CBB99700// 1620009911111122166 1624216.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482 2002.
Peter L. Bartlett, Philip M. Long, and Robert C. Williamson. Fat-shattering and the learnability of real-valued functions. Journal of Computer and System Sciences, 52(3):434-45, 1996.
Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz. Agnostic online learning. In Conference on Learning Theory, volume page 1, 2009.
Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as easy statistical learning. In Conference Learning Theory, pages 1716-1786. PMLR, 2022.
Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Ychudayoff. A characterization of multiclass lcarnability, In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 943-955. IEEE, 2022.
Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the erm principle. In Conference on Learning Theory, volume 19, pages 207-232. PMLR, 201 1.
Ofir David, Shay Moran, and Amir Yehudayoff. On statistical learning via the lens of compression. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 2792-2800, 2016
Nika Haghtalab. Foundation of Machine Learning, by the People, for the People. PhD thesis, Carnegie Mellon University. 2018.
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differ- entially private learning. Advances Neural Information Processing Systems, 33:9203-9215, 2020.
Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, and Ambuj Tewari. Multiclass online learning and uniform convergence. Conference on Learning Theory, 2023.
Steve Hanneke, Shay Moran, and Jonathan Shafer. A trichotomy for transductive online learning. Advances in Neural Information Processing Systems, 36, 2024.
David Haussler. Sphere packing numbers for subsets of the boolean n-cube with bounded vapnik- chervonenkis dimension. Journal of Combinatorial Theory, Series A, 69(2)2117-32,, 1995,
10

---

Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning. 2:285-318, 1987.
B. K. Natarajan. On learning sets and functions. Machine Learning, 4(1):67-97, 1989.
Chirag Pabbaraju. Multiclass learnaillity does not imply sample compression. In Proceedings of The 35th International Conference on Algorithmic Learning Theory, 2024.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic, constrained, and smoothed adversaries. Advances in neural information processing systems, 24, 2011.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA, 2014.
Daniel A Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 51(3):85-463,, 2004.
Leslie G. Valiant. A theory of the learnable. In Symposium on the Theory of Computing, 1984.
Vladimir Naumovich Vapnik and Alcksei Yakovlevich Chervonenkis. On uniform convergence of the frequencies of events to their probabilities. Teoriya Veroyatnostei i ee Primeneniya, 16(2):264-279, 1971.
Changlong Wu, Mohsen Heidari, Ananth Grama, and Wojciech Szpankowski. Expected worst case regret via stochastic sequential covering. Transactions Machine Learning Research, 2023.
A PAC Learnability, Combinatorial Dimensions, Complexity Measures
We begin by defining the agnostic PAC framework, a canonical learning model in the batch setting. Definition (Agnostic PAC Learnability). A hypothesis class C yd is agnostic PAC learnable if (0, 1)2 + N and learning algorithm A U221 1 x y) - yd with
there exists function the following property: for every E, (0, 1) and for every distribution D on x y, A running on m(e, 8) i.i.d. samples from D outputs a predictor As such that with probability at least 1 over S ~ D
E (w
[1{As(z) + ylll
inf REW
E (R.
[1(h(x) # yll +.
The VC and Graph dimension characterize PAC learnability when | = and | < co respectively. Definition 5 Waapik-Chervonneti
(VC) Dimension). A set = (21...., .a) C X is shattered by binary function class H. S {0. 1)x for every r E (0. there exists hypothesis h, E H such that for all E [d], we have htr (xx) = Tr, The VC dimension of H, denoted VC(H), is the size of the largest shattered set 5 C X. If H can shatter arbitrurily large sets, say that VC(H) cc.
Definition 6 (Graph Dimension). For any multiclass hypothesis class H. S y* let f H. == ((x, y) - (h(x:) # y}: h E H. C {0, (0, ((xx)) denotes its loss class. The Graph dimension of H defined G(H) VC(E H).
Our proof of this result relies bounding the Rademacher complexity, canonical complexity measure used to establish generalization bounds in the batch setting [Bartlett and Mendelson 2002).
Definition (Empirical Rademacher Complexity). Let F S R and I1, In X The empirical Rademacher complexity of F with respect to Iim is defined as
/EF E
R(F Iim) = E sup
where Ti...., are independent Rademacher random variables.
The following upperbound on the empirical Rademacher complexity follows by simple application of Massart's Jemma Shalev-Shwartz and Ben-David 2014 Lemma 28.6].

---

Lemma A.1 (Discretization Bound). For every F - R and 21, 11.... In E X", we have that
2 2log Fe,FF
R(F Fin) S inf
c+
sup fEF
E Am
e>0
n
where Pn denotes the empirical measure on the sample Tian and Pp is the distance metric defined as
Pp.. (f). = V E ((f((z) - f((x))) s/mpp
Finally, we define the packing number for generic metric spaces.
Definition 8 (Packing Number). Let (G, d) be a bounded metric space. A subset G' C G is an e-packing with respect d for every 96-9j E G we have that d(gs 93) > The packing number of G at scale e, denoted M(E,G, G. d). is the largest E NN such that there exists e-packing of G with cardinality n. That M(E. G, (.d) == supllg') G' is an e-packing for g}.
B Helper Lemmas
Lemma B.1 Leveerig-PPckiing duality (Anthony and Bartlett 1999 For any metric space (G, d) and E > 0, we have that
M(2e, G. S (N,,, M(,,G,,d)
Using the Covering-Packing duality, we prove the following technical Lemma.
Lemma B.2 (UBEME = Bounded Metric Entropy with respect to μ.). For any E IT)),, hypothesis class H S yxx and O, we have that
N(e, H. d,) sup E
(N H. dp.
N
mEN Fm " "ap
Proof. Fix E >>>>>>>> 0. By the Govering-Packinng duality, we have that
E MEN Zimm mmm
sup
[M(E, H. dim)) sup E mEN From ma
[ (22
H. dp... dp.
Thus, suffices to show that (e, H. dp) S "sup Ba (M(e, H. dā., )} Suppose, for the sake of contradiction, we have that (s, H. dr)) > supmen Eny spmn [Mie, H. dj ) Then by the Covering- Packnng duality, we have that M(s, H, dy) > supmen Exim mm [M(s, (ss, H. dp... ) =: c. By the definition of e-packing, we can find n > hypothesis h1..., hn H and 8 > 0 such that (hi, h2) > e + for every i j.
Fix E N and consider sample Fi:m nTm Let Sij = E ((ha(z)) (z())) denote the random variable counting the number samples on which h4 and hy differ. Note that S.y Binom (h, h2)). Let Em be the event that Sig > E m for all i < Then,
PRIm Pamm
Em
Tim mum 3i < j such that S.y S em
2
Prim m
Sig S mm
Σ
-2m (du hz) - =)²}
exp
Σ
exp(-2nm 2m 82)
Kjj
2 1 - n exp(- -2m 62)
12

---

where the second inequality follows by Hoeffding's inequality. Moreover, under event Em, we have that M(e, H. dp 2 n, where di.. is the empirical measure on 21mm- Finally, note that
sup
[M(E, H. dpm )1
sup
[M,,, H. dp )m P. Fr ropern Em
mEN Flim mmp
mEN Flom mmmp
n sup Px Pxim mm MEN
Em
1 n² expl-2mm 82})
n sup mER
n.
Since n > c and - sup mEN E Exim [M(s, H, di,.. )} we arrive at contradiction.
Lemma B.3 (Covering Number of Symmetric Differences). For any H S JNx, E > 0, and sequence Tl, In E X", we have that
(ee HAH, (..) = (N H. pmm )
{ 1 (1)(1)) # h2(0)) In. h2 E H}.
where Pn the empirical measure on Fi:n and HAH
Proof. Fix 0. Let H' be an e-cover for H with respect dp.. It suffices show that H' A'' is an 25-cover for HAH with respect to da.. To see this, pick g E HAH. Then by definition, we can decompose g(x) 1(h1 (z) & h2(3)) for some h h2 E H. Let H4, h22 E H' be the elements that cover h1, f2 respectively. Then, observe that we have
a
(M(.)) # (1)(a)) # h2)))))))
S
(Mx)) + Σ (h2(1.)) # (b(aa)))
n
25.
Thus, (x) + hn(x)3 is 22-close to H 1 [ (x) h2(x;)). Since x (x)((x) * h2(x)} E H'AH' and h1, h2 E H. were chosen arbitrarily, it follows that H' AH' is 25-cover for HAH with respect da.. Finally, note that HH'AH" |H'12 Since 0 arbitrary, this completes the proof.
C Proof of Theorem 3.3
The proof here is similar the proof of Theorem 3.1 Thus, only provide high-level sketch of the arguments here.
Proof. Fix E N, and take X' (1, m²]. For every ordered sequence (æ x such that vi o x, for all i + and bitstring 0 E {0, 1 define a hypothesis
(x) = ((11, Fm),
if 31 E [m] such that J = 2t
he
#m),
otherwise
Let O.. == (21,, Fm) E xm I; # x.J be the set of all ordered sequences of length m with distinct elements. Then, define our hypothesis class to be
H
U
U 05f0,13m
mm)
Here, the label space is y = UhE H (image(h)). Thus, the size of the label space is
|/ = (m"
m!
m! 2m
2m m (m2 2-1 (m2 -m (m-11) 1)) 2 S (m?)m2m - m3
(m² - m)!
13

---

when m 2 2. This implies that
2 log [>]]
3 log log [
Note that the Proof of (i) in Theorem 3.1 can be used verbatim to show that H has compression
scheme of size Thus, H. is PAC learnable with error rate O (V log log(1/6)
Therefore, we now focus on establishing regret lowerbound for H. Let Uniform ([1, ....., m }). Let m I T. We now specify the stream {(re: yt) ]t)]?= to be observed by the learner. For the instances, we take #1,- #1,-..;; I' ~ jo to iid samples from Jr. Note that 21,--. Zm are distinct with probability
m
1 m
1 4
vm 2
Moreover, as all the instances are drawn from the same distribution 14, this adversary is a- smooth for = 1. To specify y1...., we first draw 0 Uniform (00, 1)m) and define Vt = ((z1,...,mm)) 0g)) for all E [m]. Conditioned on the fact that Z....... Im are distinct, there will be a hypothesis class hg H such that (z(x)) = Ye for all E [m]. For m s
sample 24 μ and define yt (z4). Note that for any 21, . Im. we have
I Σ ER((A + wI]] 2
E O~UUnifonm (0.1)
(E(()( + #
2 m
O~UUmifonm(( (0.1)m))
2
Here, we use the fact that bitstrings O₂ are sampled uniformly randomly, so no algorithm can do better than randomly guessing. Moreover, conditioned on the event that 21....;20 Zm are distinct, we have
T
T Σ
inf Σ [((()) # v. S NEH t=1
E
(1) # v. = O.
8~UUniform( (0.))m))
e~-Uniform((O ((0.))
Since Ti. Ti are distinet with probability least 1/8, obtain
log |
inf
R (T)
A
24 log log [
D Proof of Theorem 4.1
Proof. Let vi.-.., VT E B(u, denote the sequence of a-smooth distributions picked by the adversary. Fix a > O. Then, by Lemma B.2 we have that (N(E, H, d,) S C$ (H, nt). Let H' C. H denote an e-cover with respect to d of size at most C Cg.o (H, μ). Let A denote the online learner that runs the Randomized Exponential Weights Algorithm (REWA) on the data stream (I1, yr),... (Dr,3r) using H'' as its set of experts. By the guarantees of REWA,
T 1 [((xz)) # ve
S inf NEW!
l(h((zz) # v1 + 2T log (H'))
inf NER
((h((z)) #v + 2T log(C (H,, 11)
t=l
T
< inf NCH
Σ
1(((zz)
+ vo + sup inf Σ (1(((a)) + Max)) + 2T log(C 11) NEWNER
where the expectation only taken with respect to the randomness of the MWA and the last inequality follows by the triangle inequality. Taking an outer expectation with respect to the process T1.7 VI:T.
14

---

we get that
E
(A(z)) + wil
inf KER
1(((x)) 31
+E
sup inf nEw h N'ER
Σ (1 + M(x))) + /2 2T log(C's (H, p)).
remains to bound supnen infwew Et= (x,) + h(z))) To do so, consider the class fir + (x) # h(x)) h H), where h' E H6' denotes the e-cover with respect d₂ of h, and note that
E
Σ (M)()) M(x) NeW MEW t=1
sup inf
$ E
sup Σ gEE t=1
By standard symmetrization arguments, get that
1)
T
E ELTOOET
sup gEg
g(xx)
Σ g(ott)
E
sup
((xz) s(xi))
1=1
un an mue
9E9
1=1
E
Eoir
sup
Σ 0 (g((z)) s(ot))
BED t=1
E
sup
Oe ((g(()))
01r
gEE
2T
E
(2(9,arr)
31 F mm
where 01. are independent Rademacher random variables. Note that 9 S HAH where HAH := {x +> 1[h, (x) + h2))) h1, h2 E H}. and thus R(G. 21.7) - (1 Using Lemma
A. we can pointwise upperbound
2 2log 2logN(e, (e, HAH, Ppr)
2oo N(E2, 2logN HAH, der)
log log.N($ H. d
IHAH, S S
<EtV
<E+2
T
T
T
The first inequality follows by taking Pur (g1. / - (g)(21) # g2(xz)} for any two functions 91-92 E HAH. The second inequality follows from the fact that N(e, HAH, Ppr) < (s HAH, ). The last inequality follows after using Lemma B.3 Plugging in the upperbound on the Rademacher complexity, get that
EE2 T log.N
E ELTOMET
sup gEG
g(
sup E gEg of PiTTUT
Σ g(1t)
+ +2T +4
E
( H, dur
1=1
(E2 E2 H7, dnurr
< sup gEg
[g(x))]
2E + +41
log E Bispoui
N
2
T
g((()
( 62
sup
E
+ T + 4
$
log
E Serr
N
H,, dyr
gEg
x/
2
ET
62
+ T + 4
T log E
N
H. daw
0
15

---

where the third and fourth inequality follow by change of measure, a-smoothness, and the definition Ht' respectively. By the definition of Ce (H. pt). we get that
ET 2 4 VVT log C22 4,0 S
E sup inf New NEW!
Σ (1))))) +
(H, 1b),
implying that
cT
[(((z))
+
SE E
inf NEW
11h(z)) + 44
+ 2 + 1 / log C.
(H, v 2T log (H,
a
3=T
inf NEH
Σ
(((())) # mm)
6 / Tlog
Fogg C2z (H,
2
Since U/. E B(J4, σ) and & > were chosen arbitrarily, we have that
T
ET /I I log (H,
R (I)
inf E>0
T log (2,0H..))
6 inf E>0
a
E Proof of Corollary 4.2
The following lemma from Haghtalab 2018). which uses the seminal packing lemma by Haussler 1995], will be useful.
Lemma E.1 (Haussler 19955] Haghtalab 2018 ) For any H S 10 and II()), we have
that
41 (-))
VC(K)
M(s, H. d,)) <
Lemma E.1 together with Definition implics that for any multiclass hypothesis class H. S y we have that
41 G(H)
sup x))I((())
N(e,Eo H. =
where o H := {xx y) + (((x)) + by} h H) C (0, 1] denotes the loss class of H. We
now begin the proof Corollary
Proof. (of Corollary
4.2 It suffices to show that
2E (o..e... H,
Ce.r S sup N REn((())
for every E, >> O. Fix 0.0 0. Recall that
(H. = sup sup n un EB( PInNRI
E
W(e, H, dp..)
where fnn denotes the empirical measure Zinn. We will actually show something stronger, that is
16

---

sup sup M(s, H. dp.)) neN RimE
sup N (En(a())
2E lo (D).
Fix n E and let c == sup 2c e H, dp). To see why Inequality 2 is true, consider [y)
sequence Ji:n n and let ihn denote the empirical measure 21m- Let jr, E I )) be the joint measure over X' x y defined procedurally by first sampling I E fú, and then sampling the label Uniform())). Since ün [I( x V), by definition of there exists subset H' S H of size at most such that H²' an 25 DJT cover for & o H with respect to A. It suffices to show that
H' is s-cover for H with respect A. Fix h E H and let h be the element in H' such that dz., (f h, & h I 2e Then, by definition, we have that ["]
2x |
2 dR, (Loh,
(a.y)rup
1(1(((z)) * i11
n
5=1
n
(h(x)) + ((x)))
y
|J] dan 1))
Therefore h is e-close to h with respect to dæ.,- Since was chosen arbitrarily, this is true for all H. Accordingly, H' an e-cover for H with respect to dj..: implying that ((, H. dp.) c. Since and Finn was also chosen arbitrarily, we have that suPNEN sup EX ((e, H, dp..) S C, completing the proof.
Finally, upperbound Ginle20 T +
G(H) log
app
< 12 T G(H) log
417 fol-
lows by picking VT
17

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our abstract and introduction state that (i) we show that smoothed online classification can be harder than batch classification and (ii) we provide sufficiency condition for smoothed online classification. The first claim proven Section 3 of the paper and the sufficiency condition is proven in Section 4.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In the introduction, discuss that our work does not provide complete characterization of learnability in the smoothed setting. We reiterate this limitation in the Discussion section of the paper, highlighting difficulties for complete characterization in the smoothed online model. Finally, we pose an open question regarding the complete characterization.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
18

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Although our Theorems do not have any assumptions, our results hold under formal learning models, namely the PAC model and the smoothed online model. Both are standard frameworks in learning theory, and we define them in the Preliminaries and Appendix. Moreover, we provide detailed proofs of all our theoretical claims.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
19

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cc
wwt.ssicinnooooooioooooooooooili for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips. wttps/cccppcccguuiiieeaeeec /otpe///ggideee/eocuubbbiiii wtttdd//e/ooeeeeaeiiiiiimoo
assionPoicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
20

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httptp/////eerrss...cccc/bp//e//
Answer: [Yes]
Justification: Our work conforms with NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is theoretical and contributes to our understanding of machine learn- ing algorithms. Beyond theoretical insights that can be used develop better algorithms, our work does not have direct socictal impacts.
21

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
22

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.com//aaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
23

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
24


Reviews:
[{"review_id": "KnKO1C9XlG", "reviewer": "Reviewer_7N9e", "summary": "They consider the problem of smoothed online classification under oblivious adversaries. From earlier work it is known that this problem is as easy as batch classification when the label space is bounded. However, when the label space is unbounded they provide a lower bound and show that this problem can be harder than batch classification in PAC model.\n\nFurthermore, they provide a sufficient condition for smoothed online learnability. Their conditions are in terms of covering/packing numbers of the hypothesis class using a distance metric that depends on the base measure $\\mu$. However, their sufficient condition is not a necessary condition for the smoothed learnability. They leave it as an open question to find a condition that is both necessary and sufficient for smoothed online learnability.", "questions": "Minor comments:\n\\Sigma is not defined in line 118.", "limitations": "same as above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I did not go through all the proofs, but overall this paper is well-written and seems to be sound.", "weaknesses": "same as above.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for finding our paper well-written. We will make sure to define $\\Sigma$ in the camera-ready version.", "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": "", "extra_scores": {}}, {"review_id": "hpsvTvTHLG", "reviewer": "Reviewer_jMfw", "summary": "This paper studies the problem of distinguishing batch learning from smoothed online learning when the label set size is unbounded. It shows that there exists a class that can be PAC-learned but does not admit sublinear regret, even with features generated i.i.d. The paper then provides a sufficient condition based on an empirical covering number that guarantees sublinear regret for smoothed adversarial learning.", "questions": "1. It seems all your hard instances boil down to dealing with *adversarial* labels. Can the authors comment on what happens for *realizable* labels? Does the separation still hold? (Note that in this case, you will have to use properties of smooth adversaries, as i.i.d. features are trivial.)\n\n2. It seems the failure in Theorem 4.3 (ii) is due to the non-sequential nature of your empirical cover. Can a similar notion, such as the stochastic sequential cover from Wu et al., [2023] (perhaps using the approximate variant from Hanneke et al., [2023]), be sufficient to characterize the learnability?\n\n3. Does the learnability of smoothed adversarial in the realizable case imply learnability in the adversarial label case, perhaps using a similar sequential cover construction from Hanneke et al., [2023]?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The contribution of this paper is primarily conceptual. It demonstrates that while the learnability of hypotheses with bounded label sets is fairly well understood, there can be mysterious behavior in the unbounded label case that requires further attention. From a technical standpoint, this paper constructs several instances that demonstrate separations which may be of independent interest. Overall, this is an interesting paper in a niche area that is suitable for the NeurIPS community.", "weaknesses": "While I do like the philosophical message delivered by this paper, from a purely technical standpoint, it feels somewhat half-baked.\n\nI outline some specific comments below:\n\n1. While the title indicates \"Smoothed Online Classification can be Harder than Batch Classification,\" the real separation here is actually between batch learning and *adversarial* (label) online learning. The example constructed employs no property of the smoothed adversarial setting.\n\n2. While the paper provides a sufficient condition for smoothed online learning, it does not demonstrate how strong this condition is. Is it necessary as well? Theorem 4.3 (ii) seems to indicate this is not the case.\n\n3. There are many relevant problems that should have been studied in this paper but are unfortunately omitted or left to future work. See the Questions section below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewers for their comments and address their concerns below.\n\n**Weaknesses**\n1.  In online classification, smoothness is only an assumption on the instances $x_1, ..., x_T$, and the labels can still be adversarial. This is the standard smooth model considered in \n[1,2,3,4]. If by 'adversarial labels' the reviewer means noisy labels, then we would like to clarify that our hardness result is actually derived in the realizable setting. This is established in the math display between lines 280 and 281, where we show the existence of a hypothesis that perfectly labels the data and achieves $0$ cumulative loss.\n\n2. The reviewer is correct in that the sufficient condition is not necessary. We mention this fact in lines 97-99 and formalize it in Theorem 4.3. As noted in the Discussion section, the smoothed model allows some pathological edge cases that make characterizing learnability difficult. \n\n**Questions**\n\n1. We would like to clarify that our hardness result is in the realizable setting. This is established in the math display between lines 280 and 281, where we show the existence of a hypothesis that perfectly labels the data and achieves $0$ cumulative loss.\n\n2. The notion of stochastic sequential cover provided in  Definition 1 of (Wu et al. 2023) does not characterize smoothed learnability. In fact, this can be established using the same examples used in the proof of Theorem 4.3. To see why it is not sufficient, consider  $\\mathcal{X}=[0,1]$ and $\\mathcal{H}= \\lbrace{ x \\mapsto 1[x \\in S]\\, : S \\subset \\mathcal{X} \\text{ and } |S|<\\infty\\rbrace}$. Let $\\mathcal{P}$ denote set of all distributions on $\\mathcal{X}^{T}$ such that for any $\\nu \\in \\mathcal{P}$, its marginal at each $t$ is $\\sigma$-smooth with respect to $\\mu=\\text{Uniform}(\\mathcal{X})$ for some fixed $\\sigma>0$. It is easy to see that the size of the stochastic sequential cover of $\\mathcal{H}$ with respect to $\\mathcal{P}$ under $0$-$1$ metric is $1$ (see proof of Theorem 4.3 (i) for details). However, as shown in Theorem 4.3 (i), this class is not learnable under the smoothed model. On the other hand, the class $\\mathcal{H} = \\lbrace{x \\mapsto a: a \\in \\mathbb{N}\\rbrace}$ shows that the stochastic sequential cover is not necessary, as its size of sequential cover for any distribution family $\\mathcal{P}$ is $\\infty$. \n\n3. Realizable and agnostic learnability are equivalent for smoothed online classification even when the label space is unbounded. We have some ongoing work that establishes this result using an adaptation of Theorem 11 in [6] for infinite label spaces.\n\n[1] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic, constrained, and smoothed adversaries. Advances in neural information processing systems, 24, 2011.\n\n[2] Nika Haghtalab. Foundation of Machine Learning, by the People, for the People. PhD thesis, Carnegie Mellon University, 2018.\n\n[3] Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis of online and differentially private learning. Advances in Neural Information Processing Systems, 33:9203–9215,379\n2020.\n\n[4] Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as\neasy as statistical learning. In Conference on Learning Theory, pages 1716–1786. PMLR, 2022.\n\n[5] Wu C, Heidari M, Grama A, Szpankowski W. Expected Worst Case Regret via Stochastic Sequential Covering. Transactions on Machine Learning Research, 2023.\n\n[6] Raman, Vinod, Unique Subedi, and Ambuj Tewari. \"A Characterization of Multioutput Learnability.\" arXiv preprint arXiv:2301.02729 (2023).", "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": "", "extra_scores": {}}, {"review_id": "ZzbQmKUYX5", "reviewer": "Reviewer_ercW", "summary": "This paper studies online learning under the smoothed analysis framework. Under the smoothed analysis framework, the example that is presented to the learner in each round is not chosen adversarially but instead is drawn from some distribution that is close to a known based distribution. Previous works have shown that for binary classification or regression tasks if a hypothesis class can be learned under the PAC learning model, then it can also be learned under the smoothed online learning model. In this work, the authors consider multi-class classification against a non-adaptive adversary. They show that if the label class $\\mathcal{Y}$ is unbounded, then one can construct a hypothesis class $H$, which has a finite sample compression scheme (and is thus PAC learnable) but is not smoothed online learnable. On the other hand, the paper extends previous results on binary classification and proposes a sufficient condition that ensures the PAC\n learnability of a hypothesis class is sufficient for its smoothed online learnability.", "questions": "I would like the authors to comment on the weakness pointed out above.", "limitations": "N/A", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper studies a well-defined learning problem that combines multiclass classification with smoothed online learning and gives several results on the learnability of the problem. These results enhance our understanding of the smoothed online learning problem. The hardness result for the case where the label class $\\mathcal{Y}$ is unbounded is interesting and non-trivial.", "weaknesses": "My main concern is about the significance of the work. \n\nThe learning model studied in this paper competes with a non-adaptive adversary. \nThough the paper generalizes the condition for the learnability of the problem from binary classification to multi-class classification, the high-level idea of the proof seems to be a straightforward extension of the analysis used in Haghtalab's thesis (though a more complicated analysis is needed due to the more complicated setting). Furthermore, for binary classification/regression, as mentioned in the introduction of the paper, there are results that can compete with an even stronger adaptive adversary. Given these, I am not quite convinced about the importance of the sufficient condition on the learnability proposed by the paper.\n\nOn the other hand, the hard instance is constructed based on a not very extensively studied learning model, multiclassification with infinite label sets. Though the author points out several very recent papers that study this setting, it is still not very clear to me the motivation for studying the setting and how such a hardness result would inspire new theories or algorithms for related problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for noting that our results \"enhance our understanding of the smoothed online learning problem.\" We address their concerns below. \n\n- Our sufficiency condition strictly improves the sufficiency condition presented in Haghtalab's thesis, as noted in lines 312-316. Specifically, there are classes where the VC dimension is infinite and the upper bounds in Haghtalab's thesis are therefore vacuous, but our sufficiency condition still provides a meaningful upper bound. We believe that the significance of our sufficiency condition is more conceptual than technical.  Our upper bound highlights that distribution-dependent complexity measures quantify the rates more precisely than distribution-independent complexity measures. This is an important point worth highlighting because any complexity measure that characterizes smoothed online learnability has to be a joint property of both $\\mathcal{H}$ and $\\mu$ (as noted in the Discussion section). Lastly, we only considered non-adaptive adversaries because the primary focus of our work is the hardness result. However, our upper bounds can be extended to adaptive adversaries using the coupling argument from [1].\n\n-  We note that Theorem 3.3 shows that, in terms of regret bound, the separation between PAC learnability and smoothed online learnability holds even for finite label spaces as long as the size of the label space is $\\geq 2^{T \\log(T)}$. More precisely, for any time horizon $T$, there exists a class $\\mathcal{H}_T \\subseteq \\mathcal{Y}^{\\mathcal{X}}$ with $|\\mathcal{Y}|\\geq 2^{T \\log{T}}$ for which its PAC error bound is $O\\left(\\sqrt{\\frac{\\log{n}}{n}} \\right)$, but its regret is $\\Omega(T)$ (or average regret is $\\Omega(1)$). That is, $\\mathcal{H}_T$ has a vanishing PAC upper bound (independent of $T$) but a constant non-vanishing average regret lower bound. The infinite label space is required only to show a separation of \\emph{learnability}. In particular, showing that the class is non-learnable according to Definition 1 requires establishing $\\Omega(1)$ average regret for every $T$ even as $T \\to \\infty$.\n\n\n- Finally, we disagree with the reviewer that multiclass classification with infinite label sets is not ``a not very extensively studied learning model.\" This setting has been studied in several seminal works in learning theory in the last 40 years beginning with [2,3] and more recently in [4,5,6] to name a few. Studying infinite label spaces is important for understanding when one can establish learning guarantees independent of the label size. This is quite a practical question as many modern machine learning paradigms have massive label space, such as in face recognition and protein structure prediction, where the dependence of label size in learning bounds would be undesirable. \n\n\n[1] Haghtalab, Nika, Tim Roughgarden, and Abhishek Shetty. ``Smoothed analysis with adaptive adversaries.\" Journal of the ACM 71.3 (2024): 1-34.\n\n\n[2] Balas K. Natarajan. Some results on learning. 1988.\n\n[3] B. K. Natarajan. On learning sets and functions. Machine Learning, 4:67–97, 1989.\n\n[4] A. Daniely, S. Sabato, S. Ben-David, and S. Shalev-Shwartz. Multiclass learnability and the ERM principle. In Proceedings of the 24th Conference on Learning Theory, 2011.\n\n[5] A. Daniely and S. Shalev-Shwartz. Optimal learners for multiclass problems. In Proceedings of the 27th Conference on Learning Theory, 2014.\n\n[6] N. Brukhim, D. Carmon, I. Dinur, S. Moran, and A. Yehudayoff. A characterization of multiclass learnability. In Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science, 2022.", "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": "", "extra_scores": {}}, {"review_id": "cEdIAen79R", "reviewer": "Reviewer_SmVy", "summary": "The paper studied online classification under smoothed adversaries. They constructed a hypothesis that is learnable under batch learning (PAC learning) but not learnable under smoothed online learning. They also showed that a sufficient condition that a hypothesis class learnable under the PAC learning is also learnable under the smoothed online learning.", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The result that smoothed online learning can be more difficult than PAC learning is interesting as it changes the conventional ideas in the community. As smoothed (non-adversarial) online learning gets more important as large models are emerging, the result may also contribute the theoretical insights for such models.", "weaknesses": "- They didn’t show a necessary and sufficient condition that a hypothesis class learnable under the PAC learning is also learnable under the smoothed online learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. \n\nWe are unsure what the reviewer meant by \"They didn’t show a necessary and sufficient condition that a hypothesis class learnable under the PAC learning is also learnable under the smoothed online learning.\" We would like to point out that the main result of our work shows that PAC learnability is provably not sufficient for smoothed online classification for unbounded label spaces. However, PAC learnability is certainly necessary for smoothed online classification for unbounded label spaces.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: During the discussion, the reviewers agreed that the paper is solid overall. However, concerns were raised about whether the theoretical framework of multiclass online classification with an infinite label space is properly justified within the paper. The reviewers emphasized the importance of the authors addressing this issue honestly and thoroughly in the final version to ensure the soundness of the work.
Decision: Accept (poster)