Smoothed Online Classification can be Harder than Batch Classification

Authors: vinod  raman
unique  subedi
ambuj  tewari
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-11 17:30:02

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.

Main paper: 
 introduction: 
 Classification is a canonical machine learning task where the goal is to classify examples in X into one of the possible classes in Y. There are two common classification settings based on how the data is available to the learner: batch and online. In the batch setting, the learner is provided with a fixed set of training samples that are used to train a classifier, which is then deployed to make predictions on new, real-world examples [Vapnik and Chervonenkis, 1971, Natarajan, 1989 ]. On the other hand, data arrives sequentially in the online setting and predictions need to be made in each round [Littlestone, 1987 , Daniely et al., 2011] . The batch setting is often studied under the iid assumption, whereas the stream can be fully adversarial in the online setting.For binary classification (i.e. |Y| = 2), the batch learnability of a hypothesis class H ⊆ Y X 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 , Ben-David et al., 2009] . As Haghtalab et al. [2020] remark, the latter characterization is often interpreted as an impossibility result because even simple classes like 1-dimensional thresholds have infinite Littlestone dimension. This hardness result arises mainly because the adversary can deterministically choose hard examples, even possibly adapting to the learner's strategy. One way to circumvent this hardness result is to consider a smoothed online model, where the adversary has to choose and draw examples from sufficiently anti-concentrated distributions [Rakhlin et al., 2011 , Haghtalab, 2018 , Haghtalab et al., 2020 , Block et al., 2022] . This idea is inspired from the seminal work by Spielman and Teng [2004] , who showed that the smoothed analysis of the simplex method yields a polynomial time complexity in the input size, instead of the known worst-case exponential time complexity.In smoothed online classification, a learner plays a game with the adversary over T ∈ N rounds. Before the game begins, the adversary reveals a base measure µ over X and an anti-concentration parameter σ > 0 to the learner. The distribution µ can be fairly non-informative such as uniform when applicable for X . Then, in each round t ∈ [T ], the adversary picks a labeled sample (x t , y t ) ∈ X × Y, where x t is drawn from a σ-smooth distribution ν t with respect to µ. That is, ν t (E) ≤ µ(E)/σ for all measurable subsets E in X . The adversary then reveals x t to the learner, who makes a prediction ŷt ∈ Y. Finally, the adversary reveals the true label y t ∈ Y and the learner suffers the loss 1{ŷ t ̸ = y t }. Given a hypothesis class H ⊆ Y X , the goal of the learner is to minimize the regret, the difference between its cumulative loss and the best possible cumulative loss over hypotheses in H.The smoothed online model interpolates between the iid setting (σ = 1) and the adversarial setting (σ = 0). When |Y| = 2, Haghtalab [2018] and Haghtalab et al. [2020] showed that all VC classes are learnable in the smoothed setting with the regret O( T VC(H) log (T /σ)). Extending this result to real-valued regression, where Y = [-1, 1], with the absolute-value loss, Block et al. [2022] showed that the finiteness of the fat-shattering dimension [Bartlett et al., 1996 , Alon et al., 1997 ] of H ⊆ Y X 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 be as easy as batch learning.In this work, we study smoothed online classification for arbitrary label spaces Y under oblivious adversary -one that picks σ-smooth distirbutions ν 1 , .., ν T , samples x 1 ∼ ν 1 , ..., x T ∼ ν T independently, and finally picks the labels y 1 , ..., y T , all before the game begins. This obvlious model has been studied in the past Wu et al. [2023] , but is slightly different than the one studied by [Haghtalab, 2018 , Haghtalab et al., 2020 , Block et al., 2022] (see Section 2.1 for more details). For this model, we show that smoothed online classification continues to be as easy as batch classification when |Y| < ∞. However, when |Y| is not finite, we show that smoothed online classification can be harder than batch classification. We note that there has been recent interest in studying multiclass learnability when |Y| is unbounded [Brukhim et al., 2022 , Hanneke et al., 2023 , Pabbaraju, 2024] . 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.Theorem (Informal) Let X = [0, 1]. Then, there exists H ⊆ Y X that is PAC learnable but not learnable in the smoothed online setting with µ = Uniform(X ) and σ = 1.We also provide a quantitative version of this theorem that shows a regret lowerbound linear in T even when |Y| < ∞ but bigger than 2 T log (T ) . Note that this is tight up to a factor of log T because we prove a sublinear upperbound as long as |Y| = 2 o(T ) in Section 4. To prove these results, we exploit the large size of the label space to construct a hypothesis class H ⊆ Y X such that for every h ∈ H, its output on a finite subset of X effectively reveals its identity. We then show that such a hypothesis class has a sample compression scheme of size 1. Then, the result "compression implies learning" by David et al. [2016] shows that 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 is inspired by the hypothesis class from [Hanneke et al., 2024, Claim 5.4 ]. However, a key challenge in our construction is the fact that the adversary does not have full control over the sequence of examples the learner will observe (due to σ-smoothness) whereas the adversary in Hanneke et al. [2024] can pick hard examples deterministically.In light of this hardness result, we identify a sufficiency condition for smoothed online learnability. To do so, let B(µ, σ) denote the set of all σ-smooth distributions with respect to µ. For any x 1 , . . . , x n ∈ X , let us define an empirical metric on d n on H asd n (h 1 , h 2 ) = n -1 n i=1 1{h 1 (x i ) ̸ = h 2 (x i )}. Define N (ε, H, d n ) to be the covering number of H under metric d n .Then, H is said to have uniformly bounded expected empirical metric entropy(UBEME) if sup n∈N sup ν1:n∈B(µ,σ) E x1:n∼ν1:n [N (ε, H, d n )] < ∞ for every fixed ε > 0. We showthat if H has the UBEME property, then it online learnable under smoothed adversaries. [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 |Y| < ∞, we generalize the packing lemma to show that N (ε, H, 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 |Y| < ∞.Theorem (Informal) If sup n∈N sup ν1:n∈B(µ,σ) E x1:n∼ν1:n [N (ε, H, d n )] < ∞ for every fixed ε, σ > 0, then H is smoothed online learnable under the base measure µ. When |Y| = 2, Haussler's packing lemma implies that N (ε, H, d n ) ≤ 41 ε -1 VC(H)d n ) ≤ ( 22 |Y| ε ) G(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 H with respect to the base measure µ. That is, ford µ (h 1 , h 2 ) = P x∼µ [h 1 (x) ̸ = h 2 (x)], we have N (ε, H, d µ ) < ∞ for every fixed ε > 0.Then, we use algorithmic ideas from Haghtalab [2018] that involve running multiplicative weights using the cover of H under d µ . Unfortunately, when |Y| is unbounded, the sufficiency condition (the UBEME of H) is not necessary. This is demonstrated by constant functions H = {x → a : a ∈ N} that is easy to learn butN (ε, H, d 1 ) = ∞.Given our separation and sufficiency results, it is natural to ask for a characterization of learnability for smoothed online classification. Any meaningful characterization must be a joint property of both H and µ. This is because choosing µ to be a Dirac distribution will make any H, even the set of all measurable functions from X to Y, trivially learnable. Since the most natural joint complexity measure of H and µ is N (ε, H, d µ ), one might ask whether N (ε, H, d µ ) < ∞ for every ε > 0 is necessary and sufficient for smoothed online learnability of H 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. 
preliminaries: 
 Let X denote the instance space and Y denote the label space. We assume that (X , Σ) is a measurable space and let Π(X ) denote the set of all probability measures on (X , Σ). Let H ⊆ Y X denote an arbitrary hypothesis class consisting of predictors h : X → Y. For any T ∈ N, we use the notation z 1:T to denote the sequence {z t } T t=1 . Finally, we let [N ] := {1, 2, . . . , N }.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 µ ∈ Π(X ) and a scalar σ > 0 to the learner. As mentioned before, µ can be non-informative measures such as uniform if X is totally-bounded. Then, in each round t ∈ [T ], an adversary picks a labeled sample (x t , y t ) ∈ X × Y, where x t is drawn from a distribution ν t ∈ Π(X ) that satisfies ν t (E) ≤ µ(E) σ for every E ∈ Σ. The adversary then reveals x t to the learner A. Using all the past examples (x 1 , y 1 ), . . . , (x t-1 , y t-1 ), the learner then makes a potentially randomized prediction A(x t ). The adversary then reveals the true label y t ∈ Y and the learner suffers the loss 1{A(x t ) ̸ = y t }. Given a hypothesis class H ⊆ Y X , the goal of the learner is to output predictions A(x t ) 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(µ, σ) := {ν ∈ Π(X ) : ν(E) ≤ µ(E)/σ ∀E ∈ Σ} denote the set of all σ-smooth distributions on X with respect to µ. Given H ⊆ Y X , the worst-case expected regret of an algorithm A is defined asR µ,σ A (T, H) := sup ν1,...,ν T ∈B(µ,σ) E x 1:T ∼ν 1:T sup y 1:T T t=1 E A [1{A(x t ) ̸ = y t }] -inf h∈H T t=1 1{h(x t ) ̸ = y t } .Note that as σ → 0, the set B(µ, σ) contains all Dirac distributions on X . This amounts to replacing sup ν1,...,ν T ∈ B(µ,σ) E x 1:T ∼ν 1:T [•] operator in the definition of regret above by sup x 1:T , which yields the expected regret of A in the fully adversarial model under an oblivious adversary. Thus, our adversary is a generalization of the online oblivious adversary for the smoothed setting. Given this definition of expected regret, we adopt the minimax perspective to define the learnability of a hypothesis class.Definition 1 (Smoothed Online Learnability). The class H ⊆ Y X is learnable in the smoothed online setting if and only if for every σ > 0 and µ ∈ Π(X ), we have infA R µ,σ A (T, H) = o(T ).Our worst-case expected regret is defined with respect to an oblivious adversary that picks the entire stream (x 1 , y 1 ), . . . , (x T , y T ) before the game begins. Moreover, the sequence of distributions ν 1 , . . . , ν T has to be chosen upfront before the sampling step (x 1 , . . . , x T ) ∼ (ν 1 , . . . , ν T ). That is, the distribution ν t cannot depend on the realization of previous instances x 1 , . . . , x t-1 . This ensures that the instances x 1 , . . . , x T are independent random variables. One can also consider an oblivious adversary, where ν t can depend on the past instances (x 1 , . . . , x t-1 ) sampled from (ν 1 , . . . , ν t-1 ).Since the primary contribution of this work is the hardness result in Section 3, we only focus on the case where ν 1 , . . . , ν T are chosen upfront. As the first adversary is a special case of the second adversary, our hardness result also applies for the second adversary. The fully general setting of adaptive adversaries where ν t can depend on the entire history of the game up to time point t -1 has been studied extensively in [Haghtalab et al., 2020 , Block et al., 2022] , where the dependence among x 1 , . . . , x T is handled through coupling.There are three natural choices for how y t may be selected by an oblivious adversary. In the first choice, y t may depend only on the x t ∼ ν t . In the second choice, y t may depend on prefix on x 1 ∼ ν 1 , ..., x t ∼ ν t . Finally, in the last choice, y t may depend on the entire samplex 1 ∼ ν 1 , ..., x T ∼ ν T .The first choice is considered in Haghtalab [2018] and the second by Haghtalab et al. [2020] , Block et al. [2022] . In this work, we focus on the third choice, which has been considered by Wu et al. [2023] . This choice is natural because σ-smoothness is just a property of the instances and should not impact how the labels are selected. Since the third choice is the strongest, our sufficiency result in Section 4 holds for the first two choices. However, establishing the separation result for the first two choices remains an open question.In contrast to existing work, we establish a separation between smoothed online learnability and batch learnability. The notion of batch learnability we consider is PAC learnability, a canonical model in statistical learning theory. See Appendix A for a complete definition. To prove the agnostic PAC learnability of hypothesis classes, we use the relationship between learnability and the existence of sample compression schemes.A compression scheme (κ, ρ) consists of a compression function κ and a reconstruction function ρ. The compression function κ : ∪ i≥1 (X × Y) i → ∪ i≥1 (X × Y) i maps a sample S = {(x 1 , y 1 ), . . . , (x n , y n )} to a subsample S ′ ⊆ S. The reconstruction function ρ : ∪ i≥1 (X × Y) i → Y X takes S ′ as input and outputs a function f ∈ Y X . We define the size of the compression scheme (κ, ρ) on a sample S to be |S ′ |, where κ(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 ⊆ Y X has a compression scheme (κ, ρ) of size k(n) if for every sample S = {(x 1 , h(x 1 )), . . . ,(x n , h(x n ))} for some h ∈ H, we have f = ρ(κ(S)) such that f (x i ) = h(x i ) for all i ∈ [n].The compression scheme in David et al. [2016] is slightly more general as their compression function κ can output (S ′ , b) where b is a finite bitstring. However, the restricted notion of a compression scheme without b is sufficient for our purpose. The following Theorem shows that the existence of sample compression schemes for H implies agnostic PAC learnability of H. Theorem 2.1 (Compression =⇒ Learnability [David et al., 2016] ). Let (κ, ρ) be a sample compression scheme for H ⊆ Y X of size k(n) and define f S = ρ(κ(S)) for any S ∈ (X × Y) n .Then, for every D on X × Y and n ∈ N such that k(n) ≤ n/2, with probability at least 1 -δ over S ∈ D n , we haveE (x,y)∼D [1{f S (x) ̸ = y}] ≤ inf h∈H E (x,y)∼D [1{h(x) ̸ = y}] + 100 k(n) log n k(n) + k(n) + log 1 δ n .In Section 4, we provide conditions for which a hypothesis class H is online learnable under smoothed adversaries. While sufficient conditions for learnability are typically established via combinatorial dimensions, our sufficient conditions will be in terms of covering/packing numbers of H using a distance metric that depends on the base measure µ. This discrepancy with existing literature is due to a simple observation: any parameter of H alone cannot characterize smoothed online classification. Indeed, if one takes the base measure µ to be a Dirac measure, then every H ⊆ Y X is trivially online learnable under a smoothed adversary. Accordingly, any meaningful characterization of smoothed online classification must be in terms of both H and µ.To start, we first define ε-covering numbers for generic metric spaces (G, d).Definition 2 (Covering Number). Let (G, d) be a bounded metric space. A subset G ′ ⊆ G is an ε-cover for G with respect to d if for every g ∈ G, there exists ang ′ ∈ G ′ such that d(g, g ′ ) ≤ ε. The covering number of G at scale ε, denoted N (ε, G, d), is the smallest n ∈ N such that there exists an ε-cover of G with cardinality n. That is, N (ε, G, d) := inf{|G ′ | : G ′ is an ε-cover for G}.The metric entropy for (G, d) at scale ε > 0 is defined as log N (ε, G, d). In this paper, we consider the metric space (H, d µ ) where H ⊆ Y X is a hypothesis class andd µ (h 1 , h 2 ) = P x∼µ [h 1 (x) ̸ = h 2 (x)]for some µ ∈ Π(X ). The key complexity measure in this work isC ε,σ (H, µ) := sup n∈N sup ν1:n∈B(µ,σ) E x1:n∼ν1:n [N (ε, H, d μn )] ,where μn denotes the empirical measure over x 1:n . At a high-level, C ε,σ (H, µ) measures the complexity of H in terms of its average empirical covering number, where the average is taken over processes from B(µ, σ). Using C ε,σ (H, µ), we define the property of uniformly bounded empirical metric entropy. Definition 3 (Uniformly Bounded Empirical Metric Entropy). A hypothesis class H ⊆ Y X has the Uniformly Bounded Empirical Metric Entropy (UBEME) property with respect toµ if C ε,σ (H, µ) < ∞ for every ε, σ > 0.In Theorem 4.1, we show that H is online learnable under smoothed adversaries if H enjoys the UBEME property with respect to the base measure µ.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: In the introduction, we discuss that our work does not provide a 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 are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are 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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 |Y| < ∞. Here, we show that this is not the case when |Y| is unbounded by constructing a PAC learnable hypothesis class that is not smoothed online learnable. In fact, we prove a stronger result. Theorem 3.1. There exists a hypothesis class H ⊆ Y X such that following holds:(i) H has a compression scheme of size 1.(ii) For µ = Uniform(X ) and σ = 1, we haveinf A R µ,σ A (T, H) ≥ T 2 .The part (i) of Theorem 3.1, together with Theorem 2.1, shows that H is agnostic PAC learnable witherror rate ε(δ, n) = O log n + log(1/δ) n. On the other hand, based on Definition 1, part (ii) shows that H is not smoothed online learnable. Together, we infer the following corollary. Corollary 3.2 (Agnostic PAC Learnability ⇏ Smoothed Online Learnability). There exists H ⊆ Y X such that H is agnostic PAC learnable but not learnable in the smoothed setting under µ = Uniform(X ) and σ = 1.When |Y| < ∞, the existence of a O(1)-size compression schemes and agnostic PAC learnability are equivalent [David et al., 2016] . Thus, there is no qualitative difference between Theorem 3.1 and Corollary 3.2. However, when |Y| = ∞, a recent work has shown that the multiclass PAC learnability does not imply the existence of O(1)-size compression schemes [Pabbaraju, 2024] . Thus, Theorem 3.1 is a qualitatively stronger result than Corollary 3.2. Moreover, our proof of Theorem 3.1 below provides an explicit PAC learner for H.Proof. (of Theorem 3.1) Let X = [0, 1]. Given a bitstring θ = (θ 1 , . . . , θ n ) ∈ {0, 1} n , define θ ≤t := (θ 1 , . . . , θ t ) and θ <t := (θ 1 , . . . , θ t-1 ) for any t ∈ {1, . . . , n}. Fix an n ∈ N and ordered sequence (x 1 , x 2 , . . . , x n ) ∈ X n such that x i ̸ = x j for all i ̸ = j. For every θ ∈ {0, 1} n , defineh θ (x1,...,xn) (x) := ((x 1 , . . . , x n ), θ ≤t ) if ∃t ∈ [n] such that x = x t ((x 1 , . . . , x n ), ⋆) otherwise Let O n := {(x 1 , x 2 , . . . , x n ) ∈ X n : x i ̸ = x j }be the set of all ordered sequences of length n with distinct elements. Then, we define our hypothesis class to beH := n∈N (x1,...,xn)∈On θ∈{0,1} n h θ (x1,...,xn) .Here, the label space is Y := ∪ h∈H {image(h)}. For any y ∈ 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] ∈ O m for some m ∈ N and y[2] ∈ {0, 1} t for some t ≤ m.Proof of (i). We now define a compression scheme (κ, ρ) of size 1 for H.• Define a compression function κ :∪ i≥1 (X × Y) i → X × Y as follows. Given any realizable sample S = {(x 1 , y 1 ), . . . , (x n , y n )} of size n ∈ N, the function κ outputs κ(S) = {(x 1 , y 1 )} if y i [2] = ⋆ for all i ∈ [n].On the other hand, if there exists a y i such thaty i [2] ∈ {0, 1} t for some t ∈ N, then κ(S) = {(x ℓ , y ℓ )}. Here, ℓ ∈ [n] is the index such that y ℓ [2] is the longest binary string among all i ∈ [n] for which y i [2] ̸ = ⋆.• Define a reconstruction function ρ : X × Y → H as follows. Given an output of the compression function {(x, y)}, the reconstruction function outputsρ({(x, y)}) = h 0 y[1] ∈ H if y[2] = ⋆.Here, 0 is all 0's bitstring of length equal to that of the tuple y[1]. On the other hand, if y[2] ∈ {0, 1} t for some t ≤ |y[1]|, then output ρ({(x, y)}) = h θ y[1] ∈ H, where θ is an arbitrary bitstring of length y[1] such that θ ≤t = y[2]. Next, we show that (κ, ρ) is a valid compression scheme for H. Let S = {(x 1 , y 1 ), . . . , (x n , y n )} ∈ (X × Y) n denote any sample of size n that is realizable by H. We want to show that f = ρ(κ(S)) satisfies f (x i ) = y i for all i ∈ [n]. Since S is realizable by H, there exists m ∈ N, (z 1 , . . . , z m ) ∈ X m such that z i ̸ = z j for all i, j ∈ [m] and β ∈ {0, 1} m such that h β (z1,...,zm) (x i ) = y i for all i ∈ [n]. By definition of H, for all i ∈ [n], we have y i [1] = (z 1 , . . . , z m ) and y i [2] ∈ {⋆, β ≤t } for some t ≤ m. Given a realizable sample S, there are two cases to consider: (a)y i [2] = ⋆ for all i ∈ [n] and (b) there exists i ∈ [n] such that y i [2] ̸ = ⋆.If we are in case (a), then we know that x i / ∈ {z 1 , . . . , z m } for all i ∈ [n]. Moreover, we have κ(S) = {(x 1 , y 1 )} where y 1 [1] = (z 1 , . . . , z m ) and y 1 [2] = ⋆. By definition of the reconstruction function, ρ({(x 1 , y 1 )}) = h 0 (z1,...,zm) . Since x i / ∈ {z 1 , . . . , z m }, by definition of h 0 (z1,...,zm) , we have h 0 (z1,...,zm)(x i ) = (z 1 , . . . , z m ), ⋆ = y i for all i ∈ [n]. Thus, (κ, ρ) is a valid compression scheme for H in this case. Suppose (b) is true. Define I S := {i ∈ [n] : y i [2] ̸ = ⋆}. Since h β (z1,...,zm) is consistent with the sample S, we must have y i [2] = β ≤|yi[2]| for each i ∈ I S . Here, |y i [2]| is the length of bitstring y i [2]. Let ℓ ∈ I S such that |y ℓ [2]| ≥ |y i [2]| for all i ∈ I S . By definition of the compression function κ, we have κ(S) = {(x ℓ , y ℓ )}, where y ℓ [1] = (z 1 , . . . , z m ) and y ℓ [2] = β ≤|y ℓ [2]| . Let θ ∈ {0, 1} m be the completion of y ℓ [2] such that the reconstruction function returns ρ({(x ℓ , y ℓ )}) = h θ (z1,...,zm). By definition of ρ, we haveβ ≤t = θ ≤t for t = |y ℓ [2]|. To complete our proof, it suffices to show that h θ (z1,...,zm) (x i ) = y i for all i ∈ [n].There are two cases to consider: i ∈ I S and i / ∈ I S . When i / ∈ I S , we have x i / ∈ {z 1 , . . . , z m } and thus h θ (z1,...,zm) (x i ) = ((z 1 , . . . , z m ), ⋆) = y i . As for the index i ∈ I S , we must have that x i ∈ {z 1 , . . . , z m }. Otherwise, y i [2] would be equal to ⋆, contradicting the fact that i ∈ I S . In fact, by definition of h β (z1,...,zm) , we havex i = z |yi[2]| . This implies that, for all i ∈ I S , we have h θ (z1,...,zm) (x i ) = h θ (z1,...,zm) (z |yi[2]| ) = ((z 1 , . . . , z m ), θ ≤|yi[2]| ) = ((z 1 , . . . , z m ), β ≤|yi[2]| ) = y i . Here, we use that |y i [2]| ≤ |y ℓ [2]| for all i ∈ I S and the fact that θ ≤t = β ≤t for all t ≤ |y ℓ [2]|. Therefore, we have shown that h θ (z1,...,zm) (x i ) = y i for all i ∈ [n]. Proof of (ii). Let µ = Uniform([0, 1]). We now specify the stream {(x t , y t )} T t=1 to be observed by the learner. For the instances, we take x 1 , . . . , x T ∼ µ to be iid samples from µ. Note that x 1 , . . . , x T are distinct with probability 1. Moreover, as all the instances are drawn from the same distribution µ, this adversary is σ-smooth for σ = 1. To specify y 1 , . . . , y T , we first draw θ ∼ Uniform({0, 1} T ) and define y t = ((x 1 , . . . , x T ), θ ≤t ) for all t ∈ [T ]. Given distinct x 1 , . . . , x T , for any algorithm A, we first show thatE θ∼Uniform({0,1} T ) T t=1 E A [1{A(x t ) ̸ = y t }] -inf h∈H T t=1 1{h(x t ) ̸ = y t } ≥ T 2.(1)The probabilistic method implies the existence of a θ ∈ {0, 1} T such that the claimed bound of T /2 holds. This subsequently implies that, for a distinct x 1 , . . . , x T , we have supy 1:T T t=1 E A [1{A(x t ) ̸ = y t }] -inf h∈H T t=1 1{h(x t ) ̸ = y t } ≥ T 2 .Finally, using the fact that x 1 , . . . , x T ∼ µ are distinct with probability 1, we obtain the boundinf A R µ,σ A (T, H) ≥ E x1,...,x T ∼µ sup y 1:T T t=1 E A [1{A(x t ) ̸ = y t }] -inf h∈H T t=1 1{h(x t ) ̸ = y t } ≥ T 2 .To complete our proof, it now suffices to prove Equation (1). Fixing distinct x 1 , . . . , x T , the lowerbound on the expected cumulative loss of the algorithm A isT t=1 E θ∼Unif({0,1} T ) E A [1{A(x t ) ̸ = y t }] = T t=1 E E θt 1{A(x t ) ̸ = ((x 1 , . . . , x T ), θ ≤t )} | A, θ <t = T t=1 E 1 2 1 A(x t ) ̸ = (x 1:T ), (θ <t , 0) + 1 2 1 A(x t ) ̸ = x 1:T , (θ <t , 1) ≥ T t=1 1 2 = T 2 .At a high-level, we use the fact that θ t is sampled uniformly at random from {0, 1} and is independent of A as well as θ i for all i ̸ = t. Thus, on each round, the algorithm cannot do any better than randomly guessing the value of θ t . Next, we upperbound the expected loss of the best-fixed function in hindsight. Given distinct x 1 , . . . , x T and θ ∈ {0, 1} T , we can pick the hypothesis h θ (x1,...,x T ) . By definition of this hypothesis, we have h θ (x1,...,x T ) (x t ) = ((x 1 , . . . , x T ), θ ≤t ) = y t . Thus, for every distinct x 1 , . . . , x T , we haveE θ∼Unif({0,1} T ) inf h∈H T t=1 1{h(x t ) ̸ = y t } ≤ E θ∼Unif({0,1} T ) T t=1 1{h θ (x1,...,x T ) (x t ) ̸ = y t } = 0.Finally, equation (1) follows upon combining the lowerbound on the cumulative loss of A and the upperbound on the cumulative loss of the optimal hypothesis in hindsight.To prove the qualitative separation between PAC and smoothed online learnability in Theorem 3.1, we required |Y| to be unbounded. The following theorem, proved in Appendix C, shows the quantitative dependence of the regret on |Y| when it is bounded. Theorem 3.3. For every K ∈ N, there exists H ⊆ Y X with |Y| = K such that H has a compression scheme of 1, but inf A R µ,σ A (T, H) ≥ log K 24 log log K for µ = Uniform(X ) and σ = 1.Theorem 3.3 shows that one can get quantitative separation whenever K ≥ 2 T log T .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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs 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 to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
a sufficient condition for smoothed online classification: 
 In this section, we provide a sufficient condition for smoothed online classification. Our main result provides a quantitative upperbound on the expected regret in terms of C ε,σ (H, µ).Theorem 4.1. For every H ⊆ Y X , µ ∈ Π(X ) and σ > 0, we have thatinf A R µ,σ A (T, H) ≤ 6 inf ε>0 εT σ + T log(C ε 2 ,σ (H, µ)) .Theorem 4.1 shows that as long as H satisfies the UBEME condition with respect to µ, it is online learnable under a smoothed adversary. As a corollary, we also establish the following sufficient condition in terms of the Graph dimension, a combinatorial dimension characterizing PAC learnability when |Y| < ∞ (see Appendix A for a complete definition) [Natarajan, 1989] . Corollary 4.2. For every H ⊆ Y X , µ ∈ Π(X ) and σ > 0, we have thatinf A R µ,σ A (T, H) ≤ 6 inf ε>0 εT σ + T G(H) log 41|Y| ε 2 ≤ 12 T G(H) log 41 T |Y| σ 2 ,where G(H) denotes the Graph dimension of H.Corollary 4.2, whose proof is in Appendix E, shows that PAC learnability of H is sufficient for smoothed online classification whenever |Y| < ∞. When |Y| = 2, this bounds, up to a constant factor, recovers that from Haghtalab [2018] . We now proceed with the proof of Theorem 4.1.Proof. (of Theorem 4.1) Let ν 1 , . . . , ν T ∈ B(µ, σ) denote the sequence of σ-smooth distributions picked by the adversary. Fix a ε > 0. Then, by Lemma B.2, we have thatN (ε, H, d µ ) ≤ C ε 2 ,σ (H, µ). Let H ′ ⊂ H denote an ε-cover with respect to d µ of size at most C ε 2 ,σ (H, µ).Let A denote the online learner that runs the Randomized Exponential Weights Algorithm (REWA) on the the data stream (x 1 , y 1 ), ..., (x T , y T ) using H ′ as its set of experts. By the guarantees of REWA,E A T t=1 1{A(x t ) ̸ = y t } ≤ inf h ′ ∈H ′ T t=1 1{h ′ (x t ) ̸ = y t } + 2T log(|H ′ |) ≤ inf h ′ ∈H ′ T t=1 1{h ′ (x t ) ̸ = y t } + 2T log(C ε 2 ,σ (H, µ)) ≤ inf h∈H T t=1 1{h(x t ) ̸ = y t } + sup h∈H inf h ′ ∈H ′ T t=1 1{h ′ (x t ) ̸ = h(x t )} + 2T log(C ε 2 ,σ (H, µ))where the expectation is only taken with respect to the randomness of the REWA and the last inequality follows by the triangle inequality. Taking an outer expectation with respect to the processx 1:T ∼ ν 1:T , we have E T t=1 1{A(x t ) ̸ = y t } is at most E x 1:T ∼ν 1:T inf h∈H T t=1 1{h(x t ) ̸ = y t } + E x 1:T ∼ν 1:T sup h∈H inf h ′ ∈H ′ T t=1 1{h ′ (x t ) ̸ = h(x t )} + 2T log(C ε 2 ,σ (H, µ)). It remains to bound E sup h∈H inf h ′ ∈H ′ T t=1 1{h ′ (x t ) ̸ = h(x t )} .We provide a sketch of the proof here and defer the full details to Appendix D. Consider the class G = {x → 1{h ′ (x) ̸ = h(x)} : h ∈ H}, where h ′ ∈ H ′ denotes the ε-cover of h with respect to d µ , and note thatE x 1:T ∼ν 1:T sup h∈H inf h ′ ∈H ′ T t=1 1{h ′ (x t ) ̸ = h(x t )} ≤ E x 1:T ∼ν 1:T sup g∈G T t=1 g(x t ) .By standard symmetrization arguments, we getE x 1:T ∼ν 1:T sup g∈G T t=1 g(x t ) ≤ sup g∈G E x 1:T ∼ν 1:T T t=1 g(x ′ t ) + 2T E x 1:T ∼ν 1:T R(G, x 1:T )where R(G, x 1:T ) is the Rademacher complexity of G (see Appendix A). Note that G ⊆ H∆H where H∆H := {x → 1{h 1 (x) ̸ = h 2 (x)} : h 1 , h 2 ∈R(H∆H, x 1:T ) ≤ ε+ 2 log N (ε, H∆H, ρ µ T ) T ≤ ε+ 2 log N (ε 2 , H∆H, d µ T ) T ≤ ε+2 log N ( ε 2 2 , H, d µ T ) T .Plugging in the upperbound on the Rademacher complexity and using the change of measure, σ-smoothness, and the definition of H ′ on the first term givesE x 1:T ∼ν 1:T sup g∈G T t=1 g(x t ) ≤ εT σ + 2ε T + 4 T log E x 1:T ∼ν 1:T N ε 2 2 , H, d µ T .Using the definition of C ε,σ (H, µ) to getE x 1:T ∼ν 1:T sup h∈H inf h∈H ′ T t=1 1{h ′ (x t ) ̸ = h(x t )} ≤ εT σ + 2ε T + 4 T log C ε 2 2 ,σ (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 a simple example, letX = [0, 1], µ = Uniform(X ),and consider the binary hypothesis classH = {x → 1{x ∈ A} : A ⊂ Q, |A| < ∞}. It's not too hard to see that VC(H) = ∞.On the other hand, C ε,σ (H, µ) = 1 since for every n ∈ N, the sample x 1:n ∼ µ does not lie in Q almost surely, and whenx 1:n / ∈ Q, d μn (h 1 , h 2 ) = 0 for all h 1 , h 2 ∈ H.To prove Theorem 4.1, we show that the UBEME implies a bound on the metric entropy N (ε, H, d µ ).It is natural ask whether the finiteness of N (ε, 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 ⊆ {0, 1} X such that N (ε, H, d µ ) = 1 for every ε > 0 but R µ,σ A (T, H) ≥ T 2 for every σ > 0.(ii) There existsH ⊆ N X such that N (ε, H, d µ ) = ∞ for every ε > 0 but inf A R µ,σ A (T, H) = O( T log(T )) for every σ > 0.Proof. We first prove (i). Consider the hypothesis class H = {x → 1{x ∈ S} : S ⊂ X , |S| < ∞}.1 , h 2 ∈ H, we have that d µ (h 1 , h 2 ) = P x∼µ [h 1 (x) ̸ = h 2 (x)] = 0 since h 1 and h 2 disagree on at most a finite number of points in X . Thus, for every ε > 0, H is trivially coverable using exactly one hypothesis in H. To show that R µ,σ A (T, H) ≥ T 2 for every σ > 0, consider the adversary that picks ν t = µ for all t ∈ [T ]. The process x 1:T ∼ ν 1:T is then an iid draw from µ of length T . Consider the data stream (x 1 , y 1 ), ..., (x T , y T ) where x 1:T ∼ µ T and y t ∼ Unif({0, 1}) for every t ∈ [T ]. Such a stream is realizable by H almost surely since the the sequence of instances x 1:T are all distinct with probability 1 and there can be at most a finite number of timepoints where y t = 1. On the other hand, any learning algorithm A must make at least T /2 mistakes in expectation (with respect to all sources of randomness), since the labels y t ∼ Unif({0, 1}). Thus, by the probabilistic method, for every learning algorithm A, there must exist a sequence of labels y 1:T , such that A's expected regret is T /2.We now prove (ii). Let H = {x → a : a ∈ N} be the class of constant functions. Note that for every h 1 , h 2 ∈ H, we have that d µ (h 1 , h 2 ) = 1 since h 1 and h 2 disagree everywhere on X . Thus, for every ε < 1, we have that N (ε, H, d µ ) = ∞ since |H| = ∞. On the other hand, the Littlestone dimension of H is 1. Thus, by Theorem 4 from Hanneke et al. [2023] , we get thatinf A R µ,σ A (T, H) = O( √ T log T ) for every σ > 0.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [NA] Justification: The paper does not include experiments.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be 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 a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. 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 or 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 to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 to 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
discussion: 
 In this work, we show a separation between the learnability of H ⊆ Y X in the PAC setting and the smoothed online setting when |Y| is unbounded. We also provide a sufficient condition for smoothed online learnability under any base measure µ. However, as noted in Section 4, our sufficient condition is not necessary for the smoothed learnability of H. Thus, an important open question is to find a condition that is both necessary and sufficient for smoothed online learnability. Traditionally, in learning theory, learnability is characterized in terms of a combinatorial property of just the hypothesis class H ⊆ Y X . However, the property of H alone cannot provide a characterization of learnability in the smoothed online setting. Choosing µ to be a Dirac distribution will make any H, even the set of all measurable functions from X to Y, trivially learnable. Thus, the characterization of learnability must necessarily be a property of the tuple (H, µ). To that end, we pose the following question.Given (H, µ), is there a complexity measure that characterizes the smoothed online learnability of H with base measure µ?We begin by defining the agnostic PAC framework, a canonical learning model in the batch setting. Definition 4 (Agnostic PAC Learnability). A hypothesis class H ⊆ Y X is agnostic PAC learnable if there exists a function m : (0, 1) 2 → N and a learning algorithm A : ∪ i≥1 (X × Y) i → Y X with the following property: for every ε, δ ∈ (0, 1) and for every distribution D on X × Y, A running on n ≥ m(ε, δ) i.i.d. samples from D outputs a predictor A S such that with probability at least 1 -δ over S ∼ D n , E(x,y)∼D [1{A S (x) ̸ = y}] ≤ inf h∈H E (x,y)∼D [1{h(x) ̸ = y}] + ε.The VC and Graph dimension characterize PAC learnability when |Y| = 2 and |Y| < ∞ respectively. ⊆ Y X , let ℓ • H := {(x, y) → 1{h(x) ̸ = y} : h ∈ H} ⊆ {0, 1} (X ×Y) denotes its loss class. The Graph dimension of H is defined as G(H) := VC(ℓ • H).Our proof of this result relies on bounding the Rademacher complexity, a canonical complexity measure used to establish generalization bounds in the batch setting [Bartlett and Mendelson, 2002] . Definition 7 (Empirical Rademacher Complexity). Let F ⊆ R X and x 1 , ..., x n ∈ X n . The empirical Rademacher complexity of F with respect to x 1:n is defined asR(F, x 1:n ) = 1 n E τ sup f ∈F n i=1 τ i f (x i )where τ 1 , ..., τ n are independent Rademacher random variables.The following upperbound on the empirical Rademacher complexity follows by a simple application of Massart's lemma [Shalev-Shwartz and Ben-David, 2014, Lemma 28.6 ].Lemma A.1 (Discretization Bound). For every F ⊆ R X and x 1 , ..., x n ∈ X n , we have thatR(F, x 1:n ) ≤ inf ε>0 ε + sup f ∈F E μn [f 2 ] 2 log N (ε, F, ρ μn ) nwhere μn denotes the empirical measure on the sample x 1:n and ρ µ is the distance metric defined asρ μn (f 1 , f 2 ) := E x∼μn [(f 1 (x) -f 2 (x)) 2 ].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 ′ ⊆ G is an ε-packing with respect to d if for every g i , g j ∈ G ′ we have that d(g i , g j ) > ε. The packing number of G at scale ε, denoted M(ε, G, d), is the largest n ∈ N such that there exists an ε-packing of Gwith cardinality n. That is, M(ε, G, d) := sup{|G ′ | : G ′ is an ε-packing G}.Lemma B.1 (Covering-Packing duality [Anthony and Bartlett, 1999] ). For any metric space (G, d) and ε > 0, we have thatM(2ε, G, d) ≤ N (ε, G, d) ≤ 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 µ ∈ Π(X ), hypothesis class H ⊆ Y X , and ε > 0, we have thatN (ε, H, d µ ) ≤ sup m∈N E x1:m∼µ m N ε 2 , H, d μm .Proof. Fix ε > 0. By the Covering-Packing duality, we have thatsup m∈N E x1:m∼µ m [M(ε, H, d μm )] ≤ sup m∈N E x1:m∼µ m N ε 2 , H, d μm .Thus µ (h i , h j ) > ε + δ for every i ̸ = j.Fix m ∈ N and consider a samplex 1:m ∼ µ m . Let S ij = m t=1 1{h i (x t ) ̸ = h j (x t )} denotethe random variable counting the number of samples on which h i and h j differ. Note thatS ij ∼ Binom(m, d µ (h i , h j )). Let E m be the event that S ij > ε m for all i < j. Then,P x1:m∼µ m E m = 1 -P x1:m∼µ m ∃i < j such that S ij ≤ ε m ≥ 1 - i<j P x1:m∼µ m S ij ≤ ε m ≥ 1 - i<j exp -2m (d µ (h i , h j ) -ε) 2 ≥ 1 - i<j exp{-2m δ 2 } ≥ 1 -n 2 exp{-2m δ 2 },where the second inequality follows by Hoeffding's inequality. Moreover, under event E m , we have that M(ε, H, d μm ) ≥ n, where d μm is the empirical measure on x 1:m . Finally, note thatsup m∈N E x1:m∼µ m [M(ε, H, d μm )] ≥ sup m∈N E x1:m∼µ m [M(ε, H, d μm )|E m ] P x1:m∼µ m E m ≥ n sup m∈N P x1:m∼µ m E m ≥ n sup m∈N 1 -n 2 exp{-2m δ 2 } = n.Since n > c and c = sup m∈N E x1:m∼µ m [M(ε, H, d μm )], we arrive at a contradiction.For any H ⊆ Y X , ε > 0, and sequence x 1 , ..., x n ∈ X n , we have thatN (ε, H∆H, μn ) ≤ N ε 2 , H, μn 2where μn is the empirical measure on x 1:n andH∆H := x → 1{h 1 (x) ̸ = h 2 (x)} : h 1 , h 2 ∈ H .Proof. Fix ε > 0. Let H ′ be an ε-cover for H with respect to d μn . It suffices to show that H ′ ∆H ′ is an 2ε-cover for H∆H with respect to d μn . To see this, pick a g ∈ H∆H.Then by definition, we candecompose g(x) = 1{h 1 (x) ̸ = h 2 (x)} for some h 1 , h 2 ∈ H. Let h ′ 1 , h ′2 ∈ H ′ be the elements that cover h 1 , h 2 respectively. Then, observe that we have 1 n n i=1 1{1{h ′ 1 (x i ) ̸ = h ′ 2 (x i )} ̸ = 1{h 1 (x i ) ̸ = h 2 (x i )}} ≤ 1 n n i=1 1{h 1 (x i ) ̸ = h ′ 1 (x i )} + n i=1 1{h 2 (x i ) ̸ = h ′ 2 (x i )} ≤ 2ε. Thus, x → 1{h ′ 1 (x) ̸ = h ′ 2 (x)} is 2ε-close to x → 1{h 1 (x) ̸ = h 2 (x i )}. Since x → 1{h ′ 1 (x) ̸ = h ′ 2 (x)} ∈ H ′ ∆H ′ andThe proof here is similar to the proof of Theorem 3.1. Thus, we only provide a high-level sketch of the arguments here.Proof. Fix m ∈ N, and take X = {1, 2, . . . , m 2 }. For every ordered sequence (x 1 , x 2 , . . . , x m ) ∈ X m such that x i ̸ = x j for all i ̸ = j and a bitstring θ ∈ {0, 1} m , define a hypothesis Here, the label space is Y := ∪ h∈H {image(h)}. Thus, the size of the label space ish θ (x1,...,xm) (x) := ((x 1 , . . . , x m ), θ ≤t ) if ∃t ∈ [m] such that x = x t ((x 1 , . . . , x m ), ⋆) otherwise Let O m := {(x 1 , x 2 , . . . , x m ) ∈ X m : x i ̸ = x j }|Y| = m 2 m m! 2 m = m 2 ! (m 2 -m)! 2 m = m 2 (m 2 -1) . . . (m 2 -(m-1)) 2 m ≤ (m 2 ) m 2 m ≤ m 3m , when m ≥ 2. This implies that m ≥ 1 3 log |Y| log log |Y| .Note that the Proof of (i) in Theorem 3.1 can be used verbatim to show that H has a compression scheme of size 1. Thus, H is PAC learnable with error rate O log n + log(1/δ) n.Therefore, we now focus on establishing regret lowerbound for H. Let µ = Uniform({1, 2, . . . , m 2 }).Let m ≤ T . We now specify the stream {(x t , y t )} T t=1 to be observed by the learner. For the instances, we take x 1 , . . . , x m ∼ µ to be iid samples from µ. Note that x 1 , . . . , x m are distinct with probability≥ 1 - m m 2 m = 1 - 1 m m ≥ 1 4 ∀m ≥ 2.Moreover, as all the instances are drawn from the same distribution µ, this adversary is σsmooth for σ = 1. E θ∼Uniform({0,1} m ) T t=1 E A [1{A(x t ) ̸ = y t }] ≥ E θ∼Uniform({0,1} m ) m t=1 E A [1{A(x t ) ̸ = y t }] ≥ m 2 .Here, we use the fact that bitstrings θ t are sampled uniformly randomly, so no algorithm can do better than randomly guessing. Moreover, conditioned on the event that x 1 , . . . , x m are distinct, we haveE θ∼Uniform({0,1} m ) inf h∈H T t=1 1{h(x t ) ̸ = y t } ≤ E θ∼Uniform({0,1} m ) T t=1 1{h * θ (x t ) ̸ = y t } = 0.Since x 1 , . . . , x m are distinct with probability at least 1/8, we obtaininf A R µ,σ A (T, H) ≥ m 8 ≥ 1 24 log |Y| log log |Y| .D Proof of Theorem 4.1Proof. Let ν 1 , . . . , ν T ∈ B(µ, σ) denote the sequence of σ-smooth distributions picked by the adversary. Fix a ε > 0. Then, by Lemma B.2, we have thatN (ε, H, d µ ) ≤ C ε 2 ,σ (H, µ). Let H ′ ⊂ H denote an ε-cover with respect to d µ of size at most C ε 2 ,σ (H, µ).Let A denote the online learner that runs the Randomized Exponential Weights Algorithm (REWA) on the data stream (x 1 , y 1 ), ..., (x T , y T ) using H ′ as its set of experts. By the guarantees of REWA,E A T t=1 1{A(x t ) ̸ = y t } ≤ inf h ′ ∈H ′ T t=1 1{h ′ (x t ) ̸ = y t } + 2T log(|H ′ |) ≤ inf h ′ ∈H ′ T t=1 1{h ′ (x t ) ̸ = y t } + 2T log(C ε 2 ,σ (H, µ)) ≤ inf h∈H T t=1 1{h(x t ) ̸ = y t } + sup h∈H inf h ′ ∈H ′ T t=1 1{h ′ (x t ) ̸ = h(x t )} + 2T log(C ε 2 ,σ (H, µ))where the expectation is only taken with respect to the randomness of the MWA and the last inequality follows by the triangle inequality. Taking an outer expectation with respect to the process x 1:T ∼ ν 1:T , we get thatE T t=1 1{A(x t ) ̸ = y t } ≤ E inf h∈H T t=1 1{h(x t ) ̸ = y t } + E sup h∈H inf h ′ ∈H ′ T t=1 1{h ′ (x t ) ̸ = h(x t )} + 2T log(C ε 2 ,σ (H, µ)). It remains to bound E sup h∈H inf h ′ ∈H ′ T t=1 1{h ′ (x t ) ̸ = h(x t )} .To do so, consider the class G = {x → 1{h ′ (x) ̸ = h(x)} : h ∈ H}, where h ′ ∈ H ′ denotes the ε-cover with respect to d µ of h, and note thatE sup h∈H inf h ′ ∈H ′ T t=1 1{h ′ (x t ) ̸ = h(x t )} ≤ E sup g∈G T t=1 g(x t ) .By standard symmetrization arguments, we get thatE x 1:T ∼ν 1:T sup g∈G T t=1 g(x t ) -E x ′ 1:T ∼ν 1:T T t=1 g(x ′ t ) ≤ E x 1:T ,x ′ 1:T ∼ν 1:T sup g∈G T t=1 g(x t ) -g(x ′ t ) = E x 1:T ,x ′ 1:T ∼ν 1:T E θ 1:T sup g∈G T t=1 θ t g(x t ) -g(x ′ t ) ≤ 2 E x 1:T ∼ν 1:T E θ 1:T sup g∈G T t=1 θ t g(x t ) ≤ 2T E x 1:T ∼ν 1:T R(G, x 1:T )where θ 1:T are independent Rademacher random variables. Note that G ⊆ H∆H where H∆H := {x → 1{h 1 (x) ̸ = h 2 (x)} : h 1 , h 2 ∈ H}, and thus R(G, x 1:T ) ≤ R(H∆H, x 1:T ). Using LemmaA.1 we can pointwise upperboundR(H∆H, x 1:T ) ≤ ε+ 2 log N (ε, H∆H, ρ µ T ) T ≤ ε+ 2 log N (ε 2 , H∆H, d µ T ) T ≤ ε+2 log N ( ε 2 2 , H, d µ T ) T .The first inequality follows by takingρ µ T (g 1 , g 2 ) = 1 T T t=1 1{g 1 (x t ) ̸ = g 2 (x t )} for any two functions g 1 , g 2 ∈ H∆H.The second inequality follows from the fact that N (ε, H∆H,ρ µ T ) ≤ N (ε 2 , H∆H, d µ T ).The last inequality follows after using Lemma B.3. Plugging in the upperbound on the Rademacher complexity, we get thatE x 1:T ∼ν 1:T sup g∈G T t=1 g(x t ) ≤ sup g∈G E x ′ 1:T ∼ν 1:T T t=1 g(x ′ t ) + 2ε T + 4 E x 1:T ∼ν 1:T T log N ε 2 2 , H, d µ T ≤ sup g∈G T t=1 E x ′ t ∼νt [g(x ′ t )] + 2ε T + 4 T log E x 1:T ∼ν 1:T N ε 2 2 , H, d µ T ≤ sup g∈G T t=1 E x ′ t ∼µ g(x ′ t ) σ + 2ε T + 4 T log E x 1:T ∼ν 1:T N ε 2 2 , H, d µ T ≤ εT σ + 2ε T + 4 T log E x 1:T ∼ν 1:T N ε 2 2 , H, d µ T ,where the third and fourth inequality follow by change of measure, σ-smoothness, and the definition H ′ respectively. By the definition of C ε,σ (H, µ), we get thatE sup h∈H inf h∈H ′ T t=1 1{h ′ (x t ) ̸ = h(x t )} ≤ εT σ + 2ε T + 4 T log C ε 2 2 ,σ (H, µ),implying thatE T t=1 1{A(x t ) ̸ = y t } ≤ E inf h∈H T t=1 1{h(x t ) ̸ = y t } + εT σ + 2ε T + 4 T log C ε 2 2 ,σ (H, µ) + 2T log C ε 2 ,σ (H, µ) ≤ E inf h∈H T t=1 1{h(x t ) ̸ = y t } + 3εT σ + 6 T log C ε 2 2 ,σ (H, µ).Since ν 1 , . . . , ν T ∈ B(µ, σ) and ε > 0 were chosen arbitrarily, we have thatR µ,σ A (T, H) ≤ inf ε>0 3εT σ + 6 T log C ε 2 2 ,σ (H, µ) ≤ 6 inf ε>0 εT σ + T log C ε 2 ,σ (H, µ) .The following lemma from Haghtalab [2018] , which uses the seminal packing lemma by Haussler [1995] , will be useful. Lemma E.1 (Haussler [1995] , Haghtalab [2018] ). For any H ⊆ {0, 1} X and µ ∈ Π(X ), we have thatN (ε, H, d µ ) ≤ 41 ε VC(H).Lemma E.1 together with Definition 6 implies that for any multiclass hypothesis class H ⊆ Y X , we have thatsup μ∈Π(X ×Y) N (ε, ℓ • H, d μ) ≤ 41 ε G(H), ×Y) denotes the loss class of H. We now begin the proof of Corollary 4.2.where ℓ • H := {(x, y) → 1{h(x) ̸ = y} : h ∈ H} ⊆ {0, 1} (XProof. (of Corollary 4.2) It suffices to show thatC ε,σ (H, µ) ≤ sup μ∈Π(X ×Y) N 2ε |Y| , ℓ • H, d μ , for every ε, σ > 0. Fix ε, σ > 0. Recall that C ε,σ (H, µ) := sup n∈N sup ν1:n∈B(µ,σ) E x1:n∼ν1:n [N (ε, H, d μn )] ,where μn denotes the empirical measure over x 1:n . We will actually show something stronger, that isEQUATIONFix n ∈ N and let c := sup μ∈Π(X ×Y) N ( 2ε |Y| , ℓ • H, d μ). To see why Inequality (2) is true, consider a sequence x 1:n ∈ X n and let μn denote the empirical measure on x 1:n . Let μn ∈ Π(X × Y) be the joint measure over X × Y defined procedurally by first sampling x ∈ μn and then sampling the label y ∼ Uniform(Y). Since μn ∈ Π(X × Y), by definition of c, there exists a subset H ′ ⊆ H of size at most c such that ℓ • H ′ is an 2ε|Y| -cover for ℓ • H with respect to μn . It suffices to show that H ′ is an ε-cover for H with respect to μn . Fix a h ∈ H and let h ′ be the element inH ′ such that d μn (ℓ • h, ℓ • h ′ ) ≤ 2ε|Y| . Then, by definition, we have that2ε |Y| ≥ d μn (ℓ • h, ℓ • h ′ ) = E (x,y)∼μn [1{ℓ • h(x, y) ̸ = ℓ • h ′ (x, y)}] = 1 n n i=1 1 |Y| |Y| j=1 1{1{h(x i ) ̸ = j} ̸ = 1{h ′ (x i ) ̸ = j}} = 2 n|Y| n i=1 1{h(x i ) ̸ = h ′ (x i )} = 2 |Y| d μn (h, h ′ ).Therefore h ′ is ε-close to h with respect to d μn . Since h was chosen arbitrarily, this is true for all h ∈ H. Accordingly, H ′ is an ε-cover for H with respect to d μn , implying that N (ε, H, d μn ) ≤ c.Since n and x 1:n was also chosen arbitrarily, we have that sup n∈N sup x1:n∈X n N (ε, H, d μn ) ≤ c, completing the proof.Finally, upperbound 6 infε>0 εT σ + T G(H) log 41|Y| ε 2 ≤ 12 T G(H) log 41 T |Y| σ 2 fol- lows by picking ε = σ √ T .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 a sufficiency condition for smoothed online classification. The first claim is proven in 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 in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in 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 to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
safeguards: 
 Question: Does the paper describe 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)?Answer: [NA] Justification: The paper poses no risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 a 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 is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was 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. 
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 to 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS 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. 
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 crowdsourcing nor research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• 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. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.

Furthermore, 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.
strength_weakness: strength_weakness: same as above.
questions: questions: Minor comments:
\Sigma is not defined in line 118.
limitations: limitations: same as above.
paper_summary: paper_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.
strength_weakness: strength_weakness: While I do like the philosophical message delivered by this paper, from a purely technical standpoint, it feels somewhat half-baked.

I outline some specific comments below:

1. 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.

2. 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.

3. 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.
questions: 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.)

2. 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?

3. 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: limitations: N/A
paper_summary: paper_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
 learnability of a hypothesis class is sufficient for its smoothed online learnability.
strength_weakness: strength_weakness: My main concern is about the significance of the work. 

The learning model studied in this paper competes with a non-adaptive adversary. 
Though 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.

On 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.
questions: questions: I would like the authors to comment on the weakness pointed out above.
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
questions: questions: N/A
limitations: limitations: N/A

Comments: comment: Thank you for the correction. I misunderstood the definition of PAC learnability.
I will keep my current score, but other reviewers probably have better understanding of the paper.
We thank the reviewer for their response.

We would like to point out that the smoothed online learning model was first studied by [1] in NeurIPS 2011 with the goal of bridging theory and practice. In addition, there is also a long history of NeurIPS papers studying classification with extremely large label spaces. This line of work is known as ``Extreme Classification" [2-7]. So, we think that our work is still of interest to the NeurIPS community.

[1] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic, constrained, and smoothed adversaries. Advances in neural information processing systems, 24, 2011.

[2] K. Bhatia, H. Jain, P. Kar, M. Varma, and P. Jain, Sparse Local Embeddings for Extreme Multi-label Classification, in NeurIPS 2015.

[3] D. Hsu, S. Kakade, J. Langford, and T. Zhang, Multi-Label Prediction via Compressed Sensing, in NeurIPS 2009.

[4] Y. Chen, and H. Lin, Feature-aware Label Space Dimension Reduction for Multi-label Classification, in NeurIPS, 2012.

[5] M. Cisse, N. Usunier, T. Artieres, and P. Gallinari, Robust Bloom Filters for Large Multilabel Classification Tasks , in NIPS, 2013.

[6] I. Evron, E. Moroshko and K. Crammer, Efficient Loss-Based Decoding on Graphs for Extreme Classification in NeurIPS, 2018.

[7] R. You, S. Dai, Z. Zhang, H. Mamitsuka, and S. Zhu, AttentionXML: Extreme Multi-Label Text Classification with Multi-Label Attention Based Recurrent Neural Network, in NeurIPS 2019.

[11] S. Kharbanda, A. Banerjee, R. Schultheis and R. Babbar, CascadeXML : Rethinking Transformers for End-to-end Multi-resolution Training in Extreme Multi-Label Classification, in NeurIPS 2022.
We thank the reviewer for their response. 

We would like to point out that the smoothed online learning model was first studied by [1] in NeurIPS 2011 with the goal of bridging theory and practice. In addition, there is also a long history of NeurIPS papers studying classification with extremely large label spaces. This line of work is known as ``Extreme Classification" [2-7]. So, we think that our work is still of interest to the NeurIPS community.

[1] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic, constrained, and smoothed adversaries. Advances in neural information processing systems, 24, 2011.

[2] K. Bhatia, H. Jain, P. Kar, M. Varma, and P. Jain, Sparse Local Embeddings for Extreme Multi-label Classification, in NeurIPS 2015.

[3] D. Hsu, S. Kakade, J. Langford, and T. Zhang, Multi-Label Prediction via Compressed Sensing, in NeurIPS 2009.

[4] Y. Chen, and H. Lin, Feature-aware Label Space Dimension Reduction for Multi-label Classification, in NeurIPS, 2012.

[5] M. Cisse, N. Usunier, T. Artieres, and P. Gallinari, Robust Bloom Filters for Large Multilabel Classification Tasks , in NIPS, 2013.

[6] I. Evron, E. Moroshko and K. Crammer, Efficient Loss-Based Decoding on Graphs for Extreme Classification in NeurIPS, 2018.

[7] R. You, S. Dai, Z. Zhang, H. Mamitsuka, and S. Zhu, AttentionXML: Extreme Multi-Label Text Classification with Multi-Label Attention Based Recurrent Neural Network, in NeurIPS 2019.

[11] S. Kharbanda, A. Banerjee, R. Schultheis and R. Babbar, CascadeXML : Rethinking Transformers for End-to-end Multi-resolution Training in Extreme Multi-Label Classification, in NeurIPS 2022.
We thank the reviewer for their response and would like to respond to some of their concerns.

> "Still not very convinced about the significance of the work"

Both smoothed learning and multiclass classification with infinite labels are recent but well-established topics. Smoothed analysis originated in the analysis of one of best known problem in CS, viz. linear programming. In recent years, smoothed analysis has been extended to learning problems. Multiclass classification  is one of the most fundamental ML problems. The significant of infinite labels is both theoretical and practical. Theoretically, it was the infinite labels setting that led to the recent complete characterization of multiclass learnability. From a practical point of view, infinite labels is a means to study what happens with extremely large label spaces. This is relevant to work in NLP (large vocabularies) and in extreme multiclass classification (e.g., recommender systems).

> "how much interest the setting … could attract from the NeurIPS community”

We note that there have been several NeurIPS papers regarding smoothed online learning, even dating back to 2011 [1-4]. There is also a long history of NeurIPS papers studying classification with extremely large label spaces. This line of work is known as ``Extreme Classification" [5-11]. Thus, we think studying the intersection of these two settings is natural and of interest to the NeurIPS community.

> "this setting is not a simple combination of smoothed online learning and multiclass classification with infinite labels”

We respectfully disagree with this criticism. Yes, the setting is simple — it combined smoothed online learning with multiclass classification with infinite labels. But the analysis is far from simple and our conclusions are far from obvious. We think that a simple setting with non-obvious analysis and conclusions should be of interest to NeurIPS. We think that the simplicity of the setting should not be a drawback of our contribution. 

[1] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Stochastic, constrained,
and smoothed adversaries. Advances in neural information processing systems, 24, 2011.

[2] Nika Haghtalab. Foundation of Machine Learning, by the People, for the People. PhD thesis, Carnegie
Mellon University, 2018.

[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
2020.

[4] Adam Block, Yuval Dagan, Noah Golowich, and Alexander Rakhlin. Smoothed online learning is as
easy as statistical learning. In Conference on Learning Theory, pages 1716–1786. PMLR, 2022

[5] K. Bhatia, H. Jain, P. Kar, M. Varma, and P. Jain, Sparse Local Embeddings for Extreme Multi-label Classification, in NeurIPS 2015.

[6] D. Hsu, S. Kakade, J. Langford, and T. Zhang, Multi-Label Prediction via Compressed Sensing, in NeurIPS 2009.

[7] Y. Chen, and H. Lin, Feature-aware Label Space Dimension Reduction for Multi-label Classification, in NeurIPS, 2012.

[8] M. Cisse, N. Usunier, T. Artieres, and P. Gallinari, Robust Bloom Filters for Large Multilabel Classification Tasks , in NIPS, 2013.

[9] I. Evron, E. Moroshko and K. Crammer, Efficient Loss-Based Decoding on Graphs for Extreme Classification in NeurIPS, 2018.

[10] R. You, S. Dai, Z. Zhang, H. Mamitsuka, and S. Zhu, AttentionXML: Extreme Multi-Label Text Classification with Multi-Label Attention Based Recurrent Neural Network, in NeurIPS 2019.

[11] S. Kharbanda, A. Banerjee, R. Schultheis and R. Babbar, CascadeXML : Rethinking Transformers for End-to-end Multi-resolution Training in Extreme Multi-Label Classification, in NeurIPS 2022.
I went through the other reviews and responses, and I agree that a more theoretically oriented venue like ALT/COLT might be a better fit. I keep my current score.
I would like to thank the authors for making comments on my review and providing related references. However, I am still not very convinced about the significance of the work and I am not sure how much interest the setting smoothed online learning with infinite labels could attract from the NeurIPS community. I think more work should be done and included to convince readers that this setting is not a simple combination of smoothed online learning and multiclass classification with infinite labels. For this reason, I will keep my current rate.
I thank the authors for the clarification on the realizability. However, I still feel this work is not quite "complete"; perhaps a more theoretically oriented conference (such as COLT/ALT) will better appreciate it. Anyway, I have adjusted my rating to 6, but I will not fight for acceptance.