Information-theoretic Limits of Online Classification with Noisy Labels
Authors: Changlong Wu
Ananth Grama
Wojciech Szpankowski
Venue: NeurIPS 2024 poster (2024)
Keywords: Online classification
noisy label
pairwise testing
Hellinger divergence
Le Cam-Birge testing
Primary area: learning_theory
TL;DR: We provide nearly matching lower and upper bounds for online classification with noisy labels across a wide range of hypothesis classes and noise mechanisms, using the Hellinger gap of the induced noisy label distributions.

Abstract: We study online classification with general hypothesis classes where the true labels are determined by some function within the class, but are corrupted by *unknown* stochastic noise, and the features are generated adversarially. Predictions are made using observed *noisy* labels and noiseless features, while the performance is  measured via minimax risk when comparing against *true* labels. The noisy mechanism is modeled via a general noisy kernel that specifies, for any individual data point, a set of distributions from which the actual noisy label distribution is chosen. We show that minimax risk is *tightly* characterized (up to a logarithmic factor of the hypothesis class size) by the *Hellinger gap* of the noisy label distributions induced by the kernel, *independent* of other properties such as the means and variances of the noise. Our main technique is based on a novel reduction to an online comparison scheme of two hypotheses, along with a new *conditional* version of Le Cam-Birgé testing suitable for online settings. Our work provides the first comprehensive characterization of noisy online classification with guarantees that apply to the *ground truth* while addressing *general* noisy observations.

Information-theoreti Limits of Online Classification with Noisy Labels
Changlong Wu
Ananth Grama
Wojeiech Szpankowski
CSol. Purdue University edu, layg, Spurruue edu
Abstract
We study online classification with general hypothesis classes where the true labels are determined by some function within the class, but are corrupted by unknown stochastic noise, and the features are generated adversarially. Predictions are made using observed noisy labels and noiseless features, while the performance is mea- sured via minimax risk when comparing against true labels. The noisy mechanism is modeled via a general noisy kernel that specifies, for any individual data point, a set of distributions from which the actual noisy label distribution is chosen. We show that minimax risk is tightly characterized (up to logarithmic factor the hy- pothesis class size) by the Hellinger gap of the noisy label distributions induced by the kernel, independent of other properties such as the means and variances of the noise. Our main technique is based on novel reduction to online comparison scheme of woophyytteeees, along with a new conditional version Le Cam- Cam-Birgé testing suitable for online settings. Our work provides the first comprehensive characterization for noisy online classification with guarantees that apply to the ground truth while addressing general noisy observations.
Introduction
Learning from noisy data is fundamental problem in many machine learning applications. Noise can originate from various sources, including low-precision measurements of physical quantities, communication errors, noise intentionally injected by methods such differential privacy. In such cases, one typically learns by training on noisy (or observed) data while aiming to build a model that performs well on the (or latent) data. This paper focuses on online learning (20) from noisy labels, where one receives noiseless, adversarially generated features and corresponding noisy labels sequentially, and predicts the true labels as the data arrive.
Online learning has been primarily studied in the agnostic setting I 19 71 where one receives the labels in their plain (noise-free) form and the prediction risk is evaluated on the observed labels. is typically assumed that both the features and observed labels are generated adversarially, and prediction quality measured via the notion of regret, which compares the actual cumulative risk incurred by the predictor with the minimal cumulative risk incurred by the best expert in hypothesis class. While this approach is mathematically appealing, it does not adequately characterize online learning scenarios when our goal is to achieve good performance with respect to grand truth data that may be different from the observed (noisy) ones.
This paper considers an online learning scenario that differs from classical agnostic online learning in two aspects: (i) we assume that the noisy labels are derived from (semi-) stochastic mechanism rather than from pure adversarial selections; (ii) our prediction risk is evaluated on the true labels, not noisy observations. To better motivate the study of such scenario, we consider the following example first introduced by Ben-David et al.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Example 1. Let H. C. 10.1} be finite hypothesis class. Consider the following online learning game between Nature/Adversary and Learner that played over a time horizon T. At the start, Nature fixes ground truth classifier h E H. At each time step I. S T, Nature adversarially selects feature xt E X and reveals to the learner. The learner makes a prediction ÿt based on prior features x² = {x1,'.,, ,Xx] and noisy labels jf' = (ū1.-. 1- Nature then selects (unknown) noise parameter T E [0, n) for some given yj (known to learner), and generates
xxx
j/ Bernoulli(m)) yt.
where @ denotes binary addition and Yr = hxxe) is the true label. It was shown in 1 Thm 15] that there exists predictor g"" such that:
T
log 171|
sup NEH EXT
E
Σ 1(0 + h(xi)}
S 1- 2 n1L -1)
(I)
Note that the risk in is significant, as the error introduced by noise to the true labels increases linearly as ryT. yet the risk remains independent of the time horizon T. This mirrors the fast rates known in the PAC learning literature when benign noise is present. Despite its foundational nature, the understanding of this phenomenon beyond simple Massart's 's noise has been largely unexplored.
This paper introduces a novel online learning framework for modeling general noisy mechanisms. In partieular, it encompasses (T) as very specific instance and provides clear and comprehensive characterization of the underlying paradigm. Formally, let be the set of true (latent) labels and y be the set of noisy (observed) labels, which we assume are finite and of size N, M, respectively, Let X' be the feature space. We model the noisy mechanism by a noisy kernel:
K. X y - 2000)
(2)
where D(J) is the set of all distributions over V. That is, the kernel K. maps each pair (x, y) to subset 2% : K(x, y) C. D())) of distributions over Y: Observe that the noisy kernel provides compact way of modeling noisy label distributions without explicitly referring to the noise. This is more convenient for our discussion, as ultimately the statistical information is solely determined by the noisy label distributions.
For any given H. C y and kernel K, we consider the following robust (noisy) online classification scenario: Nature first selects h H: at each time step f. Nature chooses (adversarially) x, E X' and reveals it to the learner; the learner then makes prediction ft. based on the features x' and noisy labels ; an adversary then selects a distribution Pe. E hix,)" samples ÿt ~ fe and reveals ÿe to the learner. Let t and be the strategies of the learner and Nature/adversary. respectively. The goal of the learner is to minimize the following expected minimax risk:
Pr (H,, inf sup E v
Σ 1(h(x)) + 01}
where de Dxx', Note that the adversarial selection of distribution P. from the kernel set (h(x,) provides more flexibility for modeling scenarios when the noisy label distribution changes even with the same true label, such as the Massart's noise in Example We refer to Section for more complete specification of our setting.
1.1 Main Contributions
Our main contributions in this paper establish the fundamental limits of minimax risk in (3) by providing nearly matching lower and upper bounds across wide range of hypothesis classes H and noisy kernels K. Observe that, to allow for non-trivial prediction rules, the induced noisy label distributions must be statistically distinguishable for distinct true labels. To formalize this intuition, we define, for any noisy kernel K. and feature X E X, the Hellinger gap as (i(x)) = eyy infpe (H² (p. 4) where H² (2) 9) = Em=1 (MMr(Vplmi
M
/q(m])² is the squared
Hellinger distance. That is, (x(x) measures the minimal squared Hellinger distance of the induced noisy label distributions over all distinct true labels.
Our main result (see also Theorem 2 can be summarized as follows:
'Tis is also known Massart's noise in the literature.

---

Theorem 1. Let C. VVx be any class, and K. be any noisy kernel such that infxex (x(x) 2 7/1
for some "iu > O, and 2 C DD)) is closed and convex for all x, Then:
logg 174]
(H,, S
Y/u
Moreover, for any K E N and any kernel IC with at least log K features x E & for which (x((x) S 7mn
there exists class H of size K that satisfies: ir (T, KC) 2 Ω
log/H]]
log
7M
Theorem shows that the Hellinger gap is the right characterization for the minimax risk upto at most logarithmic factor. Moreover, the risk bound depends solely on the gap parameter "he and log (H), independent of time horizon T, the size of Y and V, and the properties of noise such as means and variances. For the bounded Bernoulli noise in Example ! the set 2r corresponds to Bernoulli distributions with parameters in [0, n) if y 0 and in [1 77, if 1, leading to the 77). This matches the dependency
Hellinger gap "/n 1 - -2vnn( our result holds for any noisy kernel. For instance, if we shift 2 to Bernoulli distribution with parameter 0 and 27 with parameters in 1 27, 1), then "nu
r) in Example 1 However,
v 22 O 2r)) This is tighter
than the dependency on 17 in Example (for 17 - 2), since
2 n7(1 17) = e((1 2n)
Our main proof technique for establishing Theorem T is based on a novel (black box) reduction to an online comparison scheme of two-tyyos wwo-hypotheses in H. as demonstrated in Theorem This allows us to reduce the noisy online classification problem to a hypothesis testing problem, which effectively decouples the adversarial property of the features from the stochastic property of the noisy labels. However, due to the adversarial selection of the noisy label distributions, the classical hypothesis testing techniques does not apply. To resolve this issue, we establish in Theorem generalization of the Le Cam-Birgé Test with varying conditional marginals for handling pairwise testing via the Hellinger gap, which a result of independent interest.
Tight dependency on log [7]. Although the lower and upper bounds in Theorem I differ by a log [H| factor, this is compensated by the fact that and kernels. This can be tightened for various special cases. Indeed, for a class with binary true labels and arbitrary noisy labels, demonstrate in Theorem 5 that the minimax risk is upper bounded by 16 log /6log/Hl where "i. is the ggp that substitutes the Hellinger distance with Ldddistance in Theorem [ This is proved via a novel reduction to online conditional distribution estimation under ['-dditance. Moreover, we demonstrate in Appendix G (Theorem 6) that the (optimal) O log [?d upper bound holds if | 1 for all x, y, i.e., the noisy label distribution is determined by data.
dealing with the most general classes
1.2 Related Work
Online learning with noisy data was discussed in (), which specifically considers generalized linear functions with zero-mean and bounded variance noises. Our work differs in that we focus on classification instead of regression. Moreover, our noisy model does not require that the noise be zero-mean. To the best of our knowledge. [T] is the only work that has specifically considered the classification task, but this was limited to bounded Bernoulli noise. From a technical standpoint, analogous ideas of pairwise comparison have been considered in diffcrential privacy literature, such as in [TT. but only in batch settings. The reduction to online conditional probability estimation was also explored in [10] within the context of online decision making. However, distinguishing feature of our work is that our conditional probability estimation problem necessarily misspecified, as our noisy label distributions are selected adversarially and are unknown a priori to the learner. Our problem setup is further related to differentially private conditional distribution learning, as in 26). and robust hypothesis lesting, discussed in 17 Chapter 16). Online conditional probability estimation has been widely studied, see [T8 3
2
25|
24 Conditional density estimation in the
batch setting has also been extensively studied, see [2] for KL-divergence with misspecification
and [9] for 2 loss. Learning from noisy labels in the batch case was discussed in [16] (see also the references therein) by leveraging suitably defined proxy losses. There has been long line of research
on online prediction with adversarial observable labels in the agnostic formulation, see 5
77.
"To the best of our knowledge, this Hellinger interpretation is not known in literature: the proof in !| based on induction without explaining on how the factor 2 77) is obtained.
3

---

2 Notation and Preliminaries
Let X' be of features (or instances). y be set of labels, and y be a set of noisy observations. We assume throughout the paper that | N and [ .M for some integers N, .M 2 2. We denote D(V) as the set of all probability distributions over y
Let H. C yMV be a hypotheses class and I. be a noisy kernel in 2 We consider the following robust online classification scenario: (1) Nature first selects some h H: (2) At time Nature adversarially selects X E X:; (3) Learner predicts ÿt E y, based on (noisy) history observed thus far (i.e., x', 5/ )); (4) An adversary then selects pt E 2i(x.)) and generates noisy sample ÿr Pc.
The goal of the learner is to minimize the cumulative enror: Et= 1(h(xx) + )t)-
Note that the cumulative error a random variable that depends on all the randomness associated with the game. To remove the dependency on such randomness and to assess the fundamental limits of the prediction quality, we consider the following two measures
Definition 1.
Let H C yd be set of hypotheses and K. : X' xx y + 2P)) be a noisy kernel. We denote by t the (possibly randomized) strategies of the learner. The expected minimax risk is:
Fr (H1, inf
sup NEH.xT EXT
Q ST
L1((())) + ve)
(4)
where Q
Bpr and de 4(x', (xx',it-1)) 1)-
sup Pa E ((())
sup Pr preO
By skolemization [19], the operator Of is equivalent to sup, Egr~g. where runs over all (joint) distributions over yT such that vt E [T]. Vo E 5 the conditional marginal Ps. Pa- (g- E 2xx.))
Definition 2. Let H. Kc, and & be as in Definition
7
For any 5 > O, the high probability minimax KC) z such that there exists a predictor
risk at confidence is the minimum quantity B (H. satisfying:
Σ Il((())
# in) 2 Bd (HL 56
sup NEH,"" x
Prgt~p. -p.
(5)
where P is selected as in the discussion above and it (x 5ー
Note that the kernel map K. is generally known to the learner when constructing the predictor t However, the induced kernel sets 0x (xxx) are not, since they depend on the unknown ground truth classifier h and adversarially generated features xT. In certain cases, such as Theorem and Example 4 the kernel map IC is also not required to be known.
For any x E X and y E y, we denote by 2% the set induced by a kernel. We can assume, w.l.o.g.. that the 0 are conver and closed sets, since the adversary can select arbitrary distribution from OKs at each time step, including randomized strategies that effectively sample from mixture (i.e., convex combination) of distributions in 27...
One must introduce some constraints on the kernel KC in order to obtain meaningful results. To do so, we introduce the following well- well-separation condition:
Definition 3. Let L 2 > 2R20 be any divergence, we say kernel IC is well-separated w.E.t. L at scale > 0, if E X. Vy, y' E y with y + y/ we have L(2 2%)
def inf L(p, q) 2 7. Example 2. For any y E Y, specify canonical distribution Py D(Î). A natural noisy kernel would be define 2 = {p D()") TV(p,p)) S E), where TV denotes total variation. In this case, the kernel well-separated with the gap 7 under total variation if mingtwey TV(py.Pr) Py') Z + 2e. In particular, this subsumes Example 7 if. for y E {0, h we define Py as the distribution that assigns probability to y, and take e = 17. where the TV-gap equals y = 11 1-22n
*We assume here the selection of p" and x" are oblivious to the learner's action for simplicity. This is equivalent to the adaptive case if the learner's 's internal randomness are independent among different time steps by standard argument from [5] Lemma 4.1], see also Appendix

---

3
Main Results
We begin by stating our main result of this paper.
Theorem 2. Let C yx be a finite class of size K, and K. be kernel that well-separated at scale "in w.r.t squared Hellinger divergence (Definition 3) Then, the high probability minimax risk (Definition) 2 with confidence > O is upper bounded by:
8 8log(4K/0) log K + log(2/0).
Bd (H, KC) S
(6)
"/u
Moreover, for any kernel IC such that there exist least L distinct features E X for which ynfyvvey (2 2.y) S "/a one can find a class H of size such that:
PT (H, 20 [min log K)
Observe that, the upper bound holds with high probability and the risk is independent the time horizon (i.e., the so-called fast rates known in the PAC-learning literature). Moreover, the bound is in- dependent of the size of Y and ) A simple integration argument yields the expected risk upper bound which matches the lower bound upto only a log K factor. This demonstrates that, the Hellinger gap of the induced noisy label distributions is the right characterization for the minimax risk. Moreover, the Hellinger distance can be transformed from other f-divergences (such total variation) without depending on the size of y [17 Chapter 7.6].
F(H, K.) & O log" K
Example 3. Let K be the kernel in Example 2 Let X = mingey'e"" [V(py,Py) Ps Hence, the kernel sell-separated with TV-gap X - 2e. Since H² q)
TV(p, q)² []7 Eq. 7.22], the Hellinger we have for any hypothesis class H. the
gap is lower bounded by (2 2c)2. Invoking Theorem
2
following risk upper bound holds: B (HL,K) S S0
log
P4 log (14116))
(A-2e)²
The rest of this section is devoted to establishing Theorem 2 novel reduction to pairwise testing of two hypotheses as developed in Section 3.1 along with explicit testing rules in Section 3.2 based on a novel conditional version of Le Cam-Birgé testing.
Our main proof technique is based on
3.1 Reduction to Pairwise Comparison: Generie Approach
We first introduce the following key technical concept. Recall that our robust online classification problem is completely determined by the tuple KC,.
Definition 4. A problem KH) is said be pairwise testable with confidence 8 0 and error bound C(8) 2 0 if. for any pair h4 ha,h; h E H. the sub-problem (fh;, h J. admits a predictor (i.e., pairwise lester) Pij that achieves cumulative risk < C(8) w.p. 2 1 (see Defimition 2
Clearly, any prediction rule for (H, K.) serves pairwise testing rule for all the sub-problems ((h,, h,), K.) with h,, hy E H. Perhaps surprisingly, we will show this section that any pairwise testing rules for the sub-problems can also be converted into prediction rule for (H, K.), incurring only an additional logarithmic factor on the risk bounds.
To this end, suppose that the tuple (H. KC) is pairwise testable and the class H. = {hi, hu is finite with size K. Let D,,, be the testing rule (will be constructed in Section 3.2) for h4 by with error bound C()) and confidence
0. Let T 5" be any realization of problem KC). We define, for any h4 E H. and t E [T), surrogate loss vector:
Vj [K]. vili 1( (x' "0' # hx(x)))
(x', f differs from hx(x,). Given access to That is, the loss vili = 1 if and only if the test i (x', . testers Di our prediction rule for (H, K.) is then presented Algorithm ]
*hii is very mild assumption. For instance, if the kemee is independent the features (such as Example we have L |.2 The lower bound gives ②2( log long | log K. "M
5

---

Algorithm 1: Predictor via Pairwise Hypothesis Testing
Input: Class H (h1,-.. ,bk), pairwise testers Pa, for i.j [K] and error bound C
Set S [K,..,,K
for f = 1, ,,,.,,,2 do
Receive X
Sampling index ky from St uniformly and make prediction: Dr hgg (x5:);
Receive noisy label de: Set s*+1 0:
for i E 8 do
Compute 12 ja Er= vili,, where vi[il is defined in 7 if 13 < C' then Update 5 Stt1 U
Theorem 3. Let H C y² be any hypothesis class size K and K. be any noisy kernel. (f, K.) pairwise testable with error bound C(5) as Definition 4 then for any O, the predictor in Algorithm 7 with C = (()) achieves the high probability minimax risk (Definition) 2
(CL S 2(1 + (C(5/(2K)) log K) log(2/5).
88)
Sketch of Proof. At high level, our goal is to identify the ground truth classifier hig using the testing results of Ps.ys. Note that pairwise testability implies, w.p. 2 1-66, 6, the errors made by tester &K on hg- is upper bounded by C(8/2K) for all & E [K] simultaneously. However, for any other pair i & k", the tester Pi, does not provide any guarantees, since the samples used to test h4, hy originate from hg. and is not realizable for Di.j The key technical challenge is to extract the testing results for &R from the other irrelevant tests (i.e., Pi.j with k & {i,j]), even when the k* is unknown. This is resolved by our definition of Iē Algorithm [ which computes for each the maximum testing loss over all of its competitors. This ensures that, for the ground truth k", the loss 14" I ((6/2K). While for any other i * k², we have I3 2 Σt v²[k*] 2 Ef= (x,; o hu. (x,)) ((8/2).. Therefore, any hypothesis h; for which 4 > C(6/2K) cannot be the ground truth. Algorithm I then maintains an index set 5t that eliminates all h; for which > C(6/2K), and makes prediction de- = hgg, (Xx) with he sampling uniformly from St.
To derive the risk bound, we use a potential- based analysis that relates the size of S's with the prediction error 1 1 (x,) * de). The intuition behind the analysis is that if [E[ [1e (xx) # d is large, then there will be many elements E St for which h, (xx) * hg- (xx). and thus the loss I will (potentially) increase. Since Algorithm [ constructs 5t by eliminating all i St for which : > C(8/2K). one can therefore bound the prediction error by the change in the size of Sts. The key technical challenge here is to control the hypotheses that differ from k- but for which the tester PR errs, which is resolved by carefully defining a potential function. The claimed upper bound then follows by a similar argument as Thm 2). See Appendix B for complete proof.
Note that, the reduction of Theorem is general and does not rely on specific properties of the kernel K. (such as the well-separation condition). It provides black box reduction that converts any pairwise testing rule for two-hypotheses to a general online classification rule that introduces only a logarithmic factor on the risk bounds. This effectively decouples the adversarial property of features from the stochastic property of the noisy labels.
To understand how Theorem 3 oppratess we consider the following example:
Example 4. Let H C {0, 1 and K. be the bounded Bernoulli noise kernel with parameter nj in Example 7 For any hú hj E H, we construct the following testing rule. We may assume, w.l.o.g. that h (x) # hx(x) for all x E X, since any x for which hx(x) = h do not affect our testing- Moreover, by relabeling. we can assume that h = and hy (x) = for all x E X. At time step t, after observing the noisy labels ijt-1, we compute j+: - E Dr- If ju 2 2. the tester predicts Ur = 1; else, it predicts dr = 0. By Azuma's 's inequality, the probability of making an error at step t is upper bounded by e (t Thus, for any T. the probability of making any errors after

---

step n is upper bounded by Σizn -11-20) < e-0-2n8812 (1-20)² Taking n = 2log(1/6f1
(1-2n)²
one can upper bound the probability by 8. Therefore, the tuple (H, K.) is pairwise testable with
(()) < 2lug(1/6(1221) Invoking Theorem 3 we have:
(1-2n)²
log | (gg)611666111 2n)))
(H, SO
(9)
(1 2n)²
Note that the risk bound in 2 recovers the risk in Example upp to a logarithmic factor, though it employs a completely different approach (cf. (]. Moreover, that the risk holds with high probability and at a fast rate, which is known to be non-trivial for cumulative errors (see, c.g., [22 21)). To our knowledge, it remains unclear whether the approach proposed in [ admits a high probability guarantee.
the key advantage
3.2 Proof of Theorem 2 the conditional Le Cam-Birgé Testing
As demonstrated in Section 3.1 the risk of noisy online classification can be reduced to the pairwise lesting of two hypotheses. However, we still need to construct the explicit pairwise testing rules. This section devoted to providing generic testing rule for general kernels.
Let hg and h2 be any two hypotheses, We may assume, w.l.o.g., that (x) * h (x) for all x E X. since the features for which ho and hı agree do not affect the testing. We now provide a more compact characterization of the kernel without explicitly referring to true labels. Let x" be any realization of features. For any E {0, 1). t [T], and kernel K, we write e := K(x,, hx:)))
We define Q and o as the sets of all (joint) distributions over yM induced by the kernel upto time step J for ho, h1, respectively. Equivalently, for i E {0, 1}. we have p E O if and only if for all t E [J] and 5"- E D the conditional marginal Pg. gr E O
The pairwise testing of ho, hi time step J + 1 then equivalent to the (robust) hypothesis testing w.r.t. sets L and 2/ This is typically resolved using Le Cam-Birgé testing [17 Chapter 32.2] if the distributions are of product form. However, this does not hold for our purpose, since the distributions in 2f can have highly correlated marginals. Our main result for addressing this issue is conditional version of Le Cam- Cam-Birgé testing, as stated in Theorem 4 below. To the best of our knowledge. this conditional version is novel.
Theorem 4 (conditional Le Cam- Bain-Biré Testing). Let Q and Q be the classes induced by a kernel upto time J as defined above. For any t J, we denote 7 H2 2 2T:) and assume that Q is convex all E {0, 13. Then, there exists testing rule Vb yJ + {0, 1} such that
(Prga (VT') # 0]
# 11} $ II (1 7/2) S 2e 2--1 -1
sup pe neo!
Sketch of Proof. The proof requires suitable application of the minimax theorem by expressing the testing error as a linear function and arguing that the Q are convex. The error bound is then controlled by careful upplication of the chain-rule of Rényi divergence. See Appendix
Theorem immediately implies the following cumulative risk bound:
Propusition 1. Let hg. h4 be any hypotheses, x be any realization of features and Q., Øx² be defined as above with 7t (12(2% 2T Then, there exists tester jj" such that for all å > i E {0, 1) and p Of, w.p. 2 1 over 8/" p. we have:
1
Σ [(bx(x)) # vn) < arg min R
n N Σ n 2llg(22))
Proof. Let ni* be the minimal number satisfying the RHS. If l < n² (this can be checked at each time step using only x and K),, we predict arbitrarily. If n² + 1, we use the tester v in Theorem 4 with J = n² to produce an index i E [0, 1} and make the prediction h;(x;) for all following time steps. That is, only use the tester at step n² 1 and reuse the same testing result for all following
7

---

time steps. By Theorem 4 the probability of making errors after step n²" + 1 is upper bounded by 8. Therefore, the cumulative risk is upper bounded by n² with probability 2 1 8.
Proof of Theorem 2 Let ho. h1 E H be any two-hypotheses. For any time step such that hg (x:) o Consider the following testing rule: for any time step such that hı (x,) = h2(x)), we predict the agreed label; else, we predict the same way as in Proposition
h1 (xx), we have, by the well-separation condition, that the gap "/t 2 "Iu in Proposition |
[
Clearly, we only make errors for the second
case. Invoking Proposition with 7/2 = "/u for all E (7), we have n < 2log(2/6)) Therefore, the
TM
tuple (H, K.) is pairwise testable with C()) 2 2lo((/66) The upper bound on classification risk then
THE
follows by Theorem 3 The lower bound follows by Le Cam's 's two point method and constructing
hard hypothesis class using an epoch approach. We refer to Appendix D for the complete details. 0
Note that our techniques be easily extended to infinite classes using the covering techniques from 0 22]. Moreover, by applying Proposition ! our results can be extended to scenarios where the gap parameters "it not uniformly bounded, such as in the case of Tsybakov- type noise 18), which would lead to risk bounds that scale sublinearly with T, in contrast to the We leave the details and extensions for a longer manuscript [23].
Remark 1.
constant risk in Theorem 2
4 Tighter Bounds for Binary Labels via 1,2 Gap
We have demonstrated in Theorem 2 that the minimax risk is tightly characterized by the Hellinger gap induced by the kernel. However, the dependency on log [H] remains sub-optimal, We show in this section a tight dependency on log [7] for classes with binary true labels via the L2 gap.
Theorem 5. Let H C 10, x be any finite binary valued class, K. be any noisy kernel that is well-separated at scale "t. w.r.. the L'-distance $ (Definition 3). Then, the expected minimax risk, as in Definition! is upper bounded by: (H, S 16 [H]
We begin with the following simple geometry fact that crucial to our proof.
Lemma 1. Let Q C D(Ý) be convex and closed set, p be point outside of Q with yy def gng (p q). Denote by q" E Q the (unique) point that attains (²)) = 7. Then for any (²(p,4")=1,
q E Q we have (L2 22(
Proof. By the hyperplane separation theorem, the hyperplane perpendicular to line segment p 9" at q" separates Q and p. Therefore, the degree 0 of angle formed by p q" q is greater than π 7/2. By the law of cosines, L² L²(g,9") + L² p) = L² 4" 7
Our key idea of proving Theorem 5 is to reduce the robust (noisy) online classification problem to a suitable conditional distribution estimation problem, as discussed next.
Online conditional distribution estimation. Let F C D(5) be a class of functions mapping X to distributions in D()). Online conditional distribution estimation is a game between Nature and an estimator that follows the following protocol: (1) at each times step f, Nature selects some X, X' and reveals it to the estimator; (2) the estimator then makes an estimation f. E D()), based on x", - (3) Nature then selects some ýr E D()),, samples ÿt ~ pt and reveals ÿt. to the estimator. The goal is to find a (deterministic) estimator & that minimizes the regref:
Regr (F, 1)
sup
Σ T(pr,tt) Tipe, 1 (xx)))
(10)
F T
where P. = (x', ; Q" is the operator specified in Definition I by setting 27 = D()") for all
x, y. and L is any divergence. We emphasize that the distributions pd are not necessarily realizable
by f and are selected completely arbitrarily. This contrasts with the well-specified cases employed in [10 4 and is the key that enables us handle the unknown noisy label distributions.
We now establish the following key technical lemma, see Appendix for proof.
Recall that L L 9) -|p- - def MM (p/m) q(mr))2
8

---

Lemma 2. Let F C. D(D) be finite iestribbutionvvaleee function function class. Then, for the L divergence, there exists an estimator 4, i.e., the Exponential Weight Average (EWA) algorithm, such that
Regr (F, S log [FI-
Moreover, estimation Pt is convex combination of (f(x)) : FE.
Proof Sketch of Theorem 5 We provide the high level ideas and refer to Appendix F for complete details. We define the following noisy kernel K. For any x E X. we denote by Q and O the sets of noisy label distributions corresponding to labels 0 and respectively. Since the kernel K. is well-separated at scale 7t. under 1,a divergence, we have, by the hyperplane separation theorem, that there must be T E 2 and oी 2 such that T.2 (16 o (2 21) 2 Tt. We now define for any h E H the function fn such that Vx E X, (x) = (xx) Let J {fr h E H. and & be the estimator from Lemma with class F and L divergence (using x" 5" from the original noisy classification game). Our classification rule is defined as O arg miny (1,2 .i)) y E {0, 1]}. That is, we predict the label that of is closer to P. under L divergence, where Pa (xx', ()-
iitribbttion-vallee function class F using hypothesis class H. and
Let h* E H be the underlying true classification function. We have by Lemma that
O XTEXT
sup
Jn- Σ (p. P.) fn-
< 4 [F| < 4og [H].
(11)
where Q is the operator in Definition
Now, our key technical goal is to show that ( Pc) lse o h² (xx)3 via Lemma [ and a geometric argument,
L2 ( fn- (xx) 2 L² fn- (xx)) Z
as illustrated in the figure below:
2 V4h22
fn- (xx)
G - (xi)
Pt
Pe
1i (x.)
O (x (xi)
The expected minimax risk bound
El= 1(ū # hxx)))))
16log H|| then follows from 11
70
Although both our proofs and those provided in [ based on the EWA algorithm, the analysis and resulting algorithms are fundamentally different. For instance, in [. the learning rate of EWA depends the parameter 7), while we set it to 1/4 (see Appendix Eb. More importantly, our proof applies to any noisy kernel that satisfies the well-separation condition (including cases where أ > 2), which benefits from our geometric interpretation of the kernels. Interestingly, for the specific setting investigated in [ (i.e., Example T). our result yields the same order up to a constant factor, since
1 - 2 711 7)) O((1 - 2n))²) for 1) E [0, 1)) general, we have 47,, S 7n S VT..
5
Discussion
In this paper, we provide nearly matching lower and upper bounds for online classification with noisy labels via the Hellinger gap of the induced noisy label distributions. Our approach works for wide range of hypothesis classes and noisy mechanisms. We expect our results to have wide range of applications, such online learning under (local) differential privacy constraints and online denoising tasks involving data derived from (noisy) physical measurements (such as learning from quantum data (15) The main open problem remaining is to close logarithmic gap in Theorem for general kemels. While our work primarily focuses on the informationn-heorrtiiii minimax risks, we believe that finding computationally efficient predictors (including oracle-efficient methods in [4] would also be of significant interest.
achievable

---

Acknowledgements
This work was partially supported by the NSF Center for Science of Information (CSol) Grant CCF-0939370, and also by NSF Grants CCF-2006440, CCF-2007238, and CCF-2211423.
References
[1] Shai Ben-David, Dávid Pál, and Shai Shalev-Shwartz. Agnostic online learning. In Conference on Learning Theory, volume 3, 2009.
[2] Alankrita Bhatt and Young-Han Kim. Sequential prediction under log-loss with side information. In Algorithmic Learning Theory, pages 340-344. PMLR, 2021.
[3] Blair Bilodeau, Dylan Foster, and Daniel Roy. Tight bounds on minimax regret under logarithmic loss via self-concordance. In International Conference on Machine Learning, pages 919-929. PMLR, 2020.
[4] Blair Bilodeau, Dylan Foster, and Daniel M Roy. Minimax rates for conditional density estimation via empirical entropy. arXiv preprint arXiv:2109. 10461, 2021.
[5] N. Cesa-Bianche and G. Lugosi. Prediction, Learning and Games. Cambridge University Press, 2006.
[6] Nicolo Cesa-Bianchi, Shai Shalev-Shwartz, and Ohad Shamir. Online learning of noisy data. IEEE Transactions on Information Theory, 57(12):7077-7733 2011.
[7] Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the erm principle. J. Mach. Learn. Res., 16(1):2377-2404, 2015.
[8] Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Efficiently learning halfspaces with tsybakov noise. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 88- 08-101, 2021.
[9] Sam Efromovich. Conditional density estimation in regression setting. The Annals of Statistics, 35:2504-2555 2535, 2007.
[10] Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:21 13487, 2021.
[11] Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu, and Huanyu Zhang. Locally private hypothesis selection. In Conference Learning Theory, pages 1785-1816. PMLR, 2020.
[12] Peter D Grünwald and Nishant A Mehta. Fast rates for general unbounded loss functions: from erm to generalized bayes. The Journal of Machine Learning Research, 21(1):2040-2119 2119, 2020.
[13] Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-325, 2016.
[14] Sham Kakade and Adam T Kalai. From batch to transductive online learning. Advances in Neural Information Processing Systems, 18, 2005.
[15] Abram Magner and Arun Padakandla. Fat shattering, joint measurability, and pac learnability of povm hypothesis classes. arXiv preprint arXiv:2308. /2304, 2023.
[16] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar, and Ambuj Tewari. Learning with noisy labels. Advances neural information processing systems, 26, 2013.
[17] Yury Polyanskiy and Yihong Wu. Information Theory: From Coding to Learning. Cambridge University Press, 2022.
[18] Alexander Rakhlin and Karthik Sridharan. Sequential probability assignment with binary alphabets and large classes of experts. arXiv preprint arXiv:1501.07340, 2015.
10

---

[19] Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Random averages, combinatorial parameters, and learnability. Advances in Neural Information Processing Systems, 2010.
[20] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[21] Dirk van der Hoeven, Nikita Zhivotovskiy, and Nicolò Cesa-Bianchi High-probability risk bounds via sequential predictors. arXiv preprint wrXi::2308.07788. 2023.
[22] Changlong Wu, Ananth Grama, and Wojeiech Szpankowski. Online learning in dynamically changing environments. In Conference on Learning Theory, pages 325-358, PMLR 195, 2023.
[23] Changlong Wu, Ananth Grama, and Wojciech Szpankowski. Robust online classification: From estimation to denoising. arXiv preprint arXiv:2309.016524 2023.
[24]
Changlong Wu, Mohsen Heidari, Ananth Grama, and Wojciech Szpankowski. Expected worst case regret via stochastic sequential covering. arXiv preprint arXiv:2209.044117 2022.
[25] Changlong Wu, Mohsen Heidari, Ananth Grama, and Wojeiech Szpankowski. Precise regret bounds for log-loss via a truncated bayesian algorithm. In Advances Neural Information Processing Systems, volume 35, pages 26903-269 14, 2022.
[26] Changlong Wu, Yifan Wang, Ananth Grama, and Wojeiech Szpankowski. Learning functional distributions with private labels. In International Conference on Machine Learning (ICML), volume 202 of PMLR, pages 17724437744. PMLR, 23-29 Jul 2023.
[27] Tong Zhang. Mathematical analysis of machine learning algorithms. Cambridge University Press, 2023.

---

A Martingale Concentration Inequalities
In this appendix, we present some standard concentration results for martingales, which will be useful for deriving high probability guarantees. We refer to [27 Chapter 13.1] for the proofs.
Lemma (Azuma's Inequality). Let XI, ,xr be an arbirary random process adaptive to some filtration (Feh such that [X,] M for all t < T. Let Y2 E[X, Ft-1) be the conditional
expected random variable of Xt. Then for all > 0, we have
Pr
Σ
Y
Σ
X,
M MV
21-6 -,
1=1
and
T
T
Pr Σ
Y Σ t=1
-,- M (T/2)
2 -1- 6.
The following lemma provides a tighter concentration when X, 2 0, which can be viewed as an Martingale version of the multiplicative Chernoff bound.
Theorem 13.5D. Let XI.... XT be an arbitrary random process adaptive to some filtration (Fehest such that 0 < X, S M for all S T. Let Y, = E[ Fi-1l be the conditional expected random variable of X4. Then for all > 0 we have
Lemma 127
T
Pr
Σ
Y2
<
Xx
2M 2-222 log(11))) 2 21-8,
and
T
Pr
Y
Σ
X, - (M/2)
2 1 5.
2
t=1
Proof. Applying [27 Thm 13.5] with & X,/M and in the theorem.
B Proof of Theorem 3
Let hg- E H. be the underlying true classification function and x" be the realization features. We take C = (66/2K in Algorithm [ By definition of pairwise testability and union bound, we have w.p. 2 1 6/2 over the randomness of vj" and the internal randomness of & k that for all
k E [K].
Σ 16h (xx) &. (x', (x"")""-)) < C(8/(2K)).
(12)
Note that for any other (i.j} z k., equation 12 may not hold for predictor t However, our following argument relies only on the guarantees for predictors t which effectively makes our pairwise testing realizable.
We now condition on the event defined in 12) Let v with & E [K] and E [2] be the surrogate loss vector, as defined in 77). We observe the following key properties
1. We have for all i [T] that
max JELK
C((/(2)))
(13)
2. For any k*, have for all / E [T]:
max K
(xx(xx) + hx-() C(6/(2K))
(14)
12

---

The first property is straightforward by the definition of v and 12 The second property holds since the lower bound is attained when k.
We now analyze the performance of Algorithm 1
By property 13 we know that k" E St for all t [T], i.e., S 2 Let N₂ |5 We define for all t E [T] the potential:
max 0, 0,2C(6/(2K)) - Σ ((x((x)) o hu- (x.))
E =
RESt
Clearly, we have E, S (2K) Let D. = - 8t hx(x)) & hys (xx))). We have:
D. S No+1 Es Ect1,
(15)
since for any St such that hy (x,) # hg- (xx). either &s removed from St+1 (which contributes at most N; N++1) or its contribution to Ex+1 is decreased by 1 when compared to E, (this is because by our construction of Algorithm and property (14) once the contributions of l: to E, equals O it must be excluded from 11+1). We have, by definition of dt, that:
De
N. No+1 + E. E1+1
E [1 (x.) + J
(16)
|S4
N₂
By standard argument
Thm 21, we have:
N N411
1
+
N
N
N.
-1
No+1 +1
S log K.
Moreover, we observe that
E.
Es+1
2C(6/(2K)) Eg
T E. E1t1
Σ
N₂
N1
N₂
1=1
1=2
(b)
(C( -N2)
N1
(C(6/(2K)) Es
I
E, E1t1
Σ
N2
N₂
- (C(6/(2K))
N₁
N+1
N₂
< 2C(6/(2K)) log K,
where (a) and (b) follow by E, < (C(6/(2K)) and N, 2 N441 (c) follows by repeating the same argument for another T - 1 steps.
Therefore, we conclude
T
E
1hx (xx) + ir} (1 2C()((k)) log K, Σ
where the randomness is on the selection of he St. Since our selection of k are independent (conditioning on 5t for different f, and the indicator is bounded by 1 and non-negative, we can invoke Lemma 4 (second part) to obtain high probability guarantee of confidence 6/2 by introducing extra (2/5) additive term. The theorem now follows by a union bound with the event (22).
C Proof of Theorem
We start with application of the minimax theorem to hypothesis testing 6
This result was mentioned in 77 Chapter 32.2], without providing proof.
13

---

Lemma 5. Let Po and P1 be two sets of distributions over a finite domain Q. Po convex under Ln distance (i.e., total variation), then
Po and Pi are
min [t-)(0,11] PoEPo.PIEP
sup
(Bws-pol - [[w)] + Ruwppi [o(W]]] = =1
inf PPPPomME
IIPo
pi TV-
Moreover. if O- is the function attains minimal, then the tester 2i (w) = 1(0'(w) < 0.5) achieves
sup
inf (Prwwpul (w) # 0] + PTwwpI (w)(W) * 11} S 2(1 PoEPo.M
IPpo PıllTv).
PoEPo.PLEP:
Proof. Observe that the function ø can be viewed vector in [0, 1J2 Moreover, the distribu-
tions over S can be viewed as vectors in [0, 1J as well. Therefore, we have Eu- [1 - d(w)]
Eu-pp [o(w]] (po, Φ) + (),, which is linear function w.r.t. both (po.P) and ø. Since the
both Po P1 and [0, 1J are convex and [0, 1J is compact, we can invoke the minimax theorem [
Thm 7.1] to obtain
sup 12+(0.11] pu PoPPLEPP
min
[ [1 [(w)) + Euwpp [o(w)]]
sup
min
(Le [(w]] + Euwps (d())]
PoEPo EP1 é (0.1
sup PoEPo-riEP
{1 - IIpo - pi ||]]
where the last equality follows by Le Cam's two point lemma 17 Theorem 7.7]. Let d= be the
function attains minimal and vi (w) = 1 f (w) < 0.5). We have 1 1f (w) * i S 2(1 - i 0- (w)) 0.5, thus
for all E {0, 13. To see this, for i 0, we have v6 (w) of only if (w)
6= (w) 2
0.5 (the case for = 1 follows similarly). Therefore, we have for all po E Po. E Pi
Prw-po [ (w) A 0] + Prampi [w) + 1] S 2(B [1
o (w)) + Ew-p, 1 (w))).
This completes the proof.
We now establish the following key property, which demonstrates that the distribution classes constructed in Theorem 4 satisfy the condition of Lemma
Lemma 6. Let 2 and Of be the sets in Theorem 4 Then Oo and of are convex under Ln distance.
Proof. Let Pl. P2 E Q for i {0, 13 and E [O, 1]. We need show that p Ap1 + (1 A)p2
of as well. For any given E [T], we have
Ap1 (i") + (1 - (T))
p(ue -ー
Ap + (1 - ()pp((tt11)
pi 1( Pi (De (5(-))+(( -
P2 (jr 1 10--1
E o
p(
where the last inclusion follows by convexity of O as assumed in Theorem Therefore, we have p E Q by definition of O.-
Now, main technical part is to bound the total variation TV(Q), Qt). The primary challenge comes from controlling the dependencies of conditional marginals of the distributions. To this end, we introduce the concept of Renyi divergence. Let p1, be two distributions over the same finite domain Ω the a-Renyi divergence is defined as
Pr (w) Pi (w)
(a P2) a
log Ea
If p, are distributions over domain 22 x G2 and r is distribution over 2n then the conditional a- a-Renyi divergence is defined
Dalo. a
log EwInr wr
Σ
p(uz g w1)² 1-a
Luo Lwo
The following property about Renyi divergence is well known 17 Chapter 7.12]:
14

---

Lemma 7. Let be two distributions over 92 x G2 and p! and d be the restrictions of p. on Qr respectively. Then the following chain rule holds
(abp)))>D((D))..om Da(p.9) Da(p ( Da(p.qlr).
where r(wi) - (w1) (an))
)) is a distribution over Ω2
The following key result bounds the Renyi divergence between O and Q Proposition 2. Let 2 and 2 be the sets in Theorem all t S J. Then
i Pc PER NE Du 4) 2 th holds for
inf PER/
Do (p, 4) 2
Σ m
Proof. We prove by induction on J. The base case for J - is trivial since 2 = - and 2 = o We now prove the induction step with 2 2. For any pair E Q and E 2 we have by Lemma 7 that (a(p. = Da (p(1) (()) + (p, r), where p( 1 g(t) are restrictions p. on n- and r is distribution over yJ--1 By definition of a-Renyi divergence, we have
Da(p.glr) 2 inf 1 g'd
log Σ
plūs 18" 1 1--1---
inf Du (Pas 8f (8,11555111
(b) inf (p 2 172
where (a) follows since P--1 E 2 and 4 E O by the definition of o and Q/: (b) follows by assumption. The result then follows by induction hypothesis Da (p(1) (())) E J-1 since (() E o and (22) E -/-1.
The following result converts the Renyi divergence based bounds that with Hellinger divergence.
Proposition Let 2 and Qf be the sets Theorem 4 If H2 2 2 n 2 holds for all
t E [J]. Then
inf H2 q) 22
1 - III
(1--1112)) 7t/2))
t=1
Proof. Observe that, for any distributions p, we have (² q) 2(1 e Pira(na)))
(17)
Specifically, for give p Og and g 2/. we have
e
tmc II t=1
(1- 72/2),
t=1
where S are the constants Proposition 2 and the last inequality follows by im S 1 - 72/2 due
(17) again. This completes the proof.
Proof Theorem We have, by Lemma that the testing error is upper bounded by 2(1 inf mE lpp <llTv). Fix any such p. q. we have by [17] Equation 7. 7.22] that - 1p c| 5
1 - 1/2 (1 q). The result then follows by Proposition
15

---

D Proof of Theorem 2 (Lower Bound)
We denote S log K with K = [7H,, and XI, ,Xt be I. distinct elements in X' satisfies the condition of the theorem. We deñiee for any b 10. function ho such that for all i E [L] and (x,) = y otherwise, where yi * y E y are the elements that (x;) = y/ if bii] (V) Th. Let H be the class consisting of all such lis Let gi E 2% satisfy inf
and q E 2 be the elements satisfying H g.) S Tia- We now partition the features x" into epochs, each of length L,L, such that each epoch has constant feature x,. Let h be a random function selected uniformly from H. We claim that for any prediction rule ÿ and any epoch i we have
(++1Y//L Σ
En,
1h(x)) # 0t) 2
(18)
1-/T/L11
where ie ~ 9: if h(xx) - ye and io ~ of otherwise. The proposition now follows by counting the errors for all L epochs.
We now establish (18) using the Le Cam's two point method. Clearly, for each epoch i, the prediction performance depends only on the label = h(x;), which is uniform over {Vt, V/} and independent for different epochs by construction. For any time step j during the ith epoch, we denote by gz and j the samples generated from and g/. respectively. By the Le Cam's 's two point method [1 Theorem 7.7] the expected error at step j is lower bounded by
- TV 1.
1 -
V H 8 )1 H
1/44)
(19)
2
where the inequality follows from 11 Equation 7.22]. Note that the RHS of 19 is monotone decreasing w.r.t. H0' .gg51 since H q) < 2 for all p.
By the tensorization of Hellinger divergence [17 Equation 7.23], we have
2 - 2(1 - -12 d)/22/ 2
2(1 - 2
7/1/2)²-
where the last inequality is implied by (2 ④h) S in- Using the fact log(1 x) ス _ we have if The < 1 and j - < + 19 is lower bounded by an absolute positive constant for all j - < 1 and hence the expected
"M then 2 - 2(1 22) < 2(1 2 < 2. Therefore, the RHS of
cumulative error will be lower bounded by 12(1/"/u during epoch i. This completes the proof.
E Proof of Lemma 2
Before presenting a formal proof, we first develop some technical concepts. Let 5 be the noisy label set and D()) be the class of distributions over D. We say a function é: 5 x D()) + Rt is a-exp-concave for any ÿ E y, the function e -of(5rr)) is concave w.r.. p for some a E R20.
Proposition 4. The function E(g. p) = |leg - -Pli 144-Exp-concave, where eg denotes distribution assigning probubility 1 on ÿ-
Proof. We have by
13 Lemma 4.2] that function f is a-Exp-concave if and only if
a [V(()) = fp).
For any q E D()), we denote f(p) 1p Al1. We have vf(p) 2(p - q) and (2f(p) = 21, where I is the identity matrix. Taking any u E RJ, we have {u, 2(p g))² S 11
21|u|13 = 2u Lu, where the first inequality follows by Schhar-S inequality and the second inequality follows by:
1p 211 Σbmi -
Σ 5e
max 1
Σ gey
pl7T + 2 2,
5E
since p.q D(Ò). This completes the proof.
16

---

We now introduce the Exponential Weighted Average (EWA) algorithm and its regret analysis under the Exp-concave losses, which is mostl standard [5] Chapter 3.3] and we include it here for completeness. Let F (fi,.... .fk c D())* x be a D(V)- function class and e x D()) - R 22 be a-Exp-coneave. The EWA algorithm is presented in Algorithm
Algorithm 2: Exponential Weighted Average (EWA) estimator
Input: Class F (/1,
JK} and a-Exp-concave loss
Set w [1,.... ,1] E R
for t = 1......... do
Receive X,;
Make prediction:
> R w (x)))
D:
ΣK=1 w((k]
Receive noisy label Me: for & E [K] do Set [ w (((e))a)))()))))))))))
Algorithm 2 provides the following regret bound:
Proposition (15) Proposition 3.1]). Let F c D())* be any finite class and l be a- a-Exx-concave
loss. ft is the estimator Algorithm 2 then for any x E X2T and oJ E SST we have
(().. - f(xt)) log [
sup fer
Proof of Lemma 2 Let & be the EWA estimator as in Algorithm 2 with input class F, loss ( p) ("(ee, p) and a = 1/4. Let ÿ² be any realization of the noisy labels. We denote et as the standard base of RM with value 1 at position j and zeros otherwise. By 1/4-Exp-concavity of loss (Proposition 4 and the regret bound from Proposition 5
we have:
T Σ
sup TTX EYT t=l
(e), - ((x,)) S log [F]
(20)
Note that, this bound holds point-wise w.r.t. any individual x" and "²
Fix any x and (joint) distribution ý over ÿT We denote E, as the conditional expectation on ÿe over the randomness of ÿ" conditioning أ²' and denote Pe as the conditional marginal. By the elementary identity EXL'(X,p) p) (² q)] = L²([((), p) L2(E[X), q) for any random variable
X over D()), we have for all E [T] that:
E, [E' p.) (e f(xx))] L' P:) L ( f(x:)),
since Ee[es] = pe for De ~ 5. and P. depends only on 8/-11 We now take E,r on both sides of (20). By sup IE < E sup and the law of total probability (i.c., Egr [X1 + ... +X7 Eg E [1] +
Ey [X,]] for any random variables x),, we have:
T Σ
sup sup Eggap TEXT
L' Dr) L3 ((xi))
< 4og [Fl,
where Φ runs over all (joint) distributions over 5Th The lemma then follows by the equivalence
between operators of sup; Eyr when taking the kernel set Qx = D(5)) for all x, (see the discussion following Definition Tp. The last part follows by the fact that the EWA estimator automatically ensures is convex combination of {f(x)) f E F} for all t [T].
D
17

---

F Proof of Theorem 5
We define the following distribution valued function class F using hypothesis class H and noisy kernel K. For any x E X. we denote by 26 and 2 the sets of noisy label distributions corresponding labels 0 and 1, respectively. Since the kernel is well-separated
scale 7, under L divergence, we have, by the hyperplane separation theorem, that there must be q E 2 and of E Oi such that L (g6 of
( ( 2 Ti. We now define for any h H the function fa such that VX E X, (x) = (x)))) Let F = {fr h E H. and Φ be the estimator from Lemma 2 with class
F and 2 divergence (using xT 57 from the original noisy classification game). Our classification
predictor is as follows:
d = arg min LL2 (1g pr) E (0,1)).
(21)
ạ/ That is, we predict the label that oz is closer to ja under 2 divergence, where P: +(x',
-)-1).
Let ht E H be the underlying true classification function and x be the realization of features. We have by Lemma and 1/ 1/4-Exp-comme e/--exxcconcavity of I,2 divergence that
Σ I (p: Pe) - ( fn. (xx)))
< <4log [Fl,
(22)
where Q% the operator in Definition
For any time step L, we denote by = 11" (x:) the true label. Since df E 2 are the elements satisfying (g a (2 2 2 ".. and q: is a convex combination of % and ot
(Lemma 2p. we have qrt the closest element in 2%: P.. under I,² divergence. Note that, we also
have P:: E 2xx Invoking Lemma[] we find
L L' b.) - (p,,,, G. 2 (P(
(23)
Denote a₁ (pr, Po) Ia (p fn- (xx)). Therefore:
L L (xx)). We have, by (23 and fn- (xx) 9 that at
Z
1. For all E (T), az 2 0, since Vp, q, 13(p, 0:
2. If De * yc. then a 2 //4.. This is because the event {de # ye3 implies that 2 97)
L (f( - Hence, ( fn- (xx)) (p,,,, 4g.) Z %/. Here, we used the following
geometric fact:
2V I. 2 v L2 (pt, qui + I. (pc.
L (a - 2 Vi.
This implies that Vt [T], 2 110e # ye), therefore:
T Σ Huee + w < 4 Σ (3. - L L (pr, Sr. (x+)).
The expected minimax risk now follows from 22
G Tight Bounds for Kernel Sets of Size One
In this appendix, establish an upper bound for the when the kernel set size Q 1 for all x, y. This includes, for instance, the case when the parameter т) is known in Example
Theorem 6. Let H. C. yx be any finite class and K. be any noisy kernel that is well-separated at scale in w.r.t. squared Hellinger distance such that [ for all x, y. Then the high probability minimax risk at confidence 8 0 is upper bounded by
log log( (1H11/8)
(²H, <
Yh
Since QE (T(F(TT)) ) for any kernel I. and function F. where OTT is the unconstrained operator (00)
18

---

Proof. Our proof follows similar path as in the proof of Theorem 5 but replacing the L loss with log-loss. Specifically, for any H, we define (x) (x(x)) where Th(x) is the unique element in D Denote F = (ʃx h E H}. We run the EWA algorithm (Algorithm 2 over F with a = 1 and being the log-loss and produce an estimator p² The classifier then given by
de arg min If2 (1 (
yEy
Now, our key observation is that the noisy label distribution Pr (x; well-specified (since [2 = I. the only choice for pr is fnx())) where he is the ground truth classifier. Therefore, invoking [TO] Lemma A. A.14], we find
Pr
H (P. Dr) log [F] 2 log 11-6.
We claim that 1 (se + htt (x+)) S 4 (pr, pe). Clearly, this automatically satisfies if h- hx(x)). For Dc o h² (xx), we have (f - Dt) I (1 (x.)) D1) - (fr by definition of dr. This implies that
7u
( 2 H H (x))
where the first inequality follows by triangle inequality Hellinger distance (the factor 1/ comes from the conversion form squared Hellinger distance to Hellinger distance), and the second inequality follows by definition of Ya. Therefore, we have w.p. 2 that
Σ 16 + h² (x()) S
(log [F + log((1))))
7/u
This completes the proof since [||] Fl.
Observe that the key ingredient in the proof of Theorem 6 is the realizability of fr. by fur (i.e., well-specified) due to the property 2% 1, which does not hold for general kernels.
H Adaptive v.s. Oblivious Adversaries
In this appendix, we explain how the guarantees for oblivious adversaries can be extended to adaptive adversaries. This primarily follows from (3] Lemma 4.1], but needs careful adaptation to fit our needs. We consider the following abstract treatment: we assume that the adversary performs any operation Qr at time step i and produces an action 2,. For any randomized prediction rule ÿ²" the adaptive risk can be expressed as
T E(Zr, Ut)
Q1 En ... Qr
Σ
Assume now that the randomness of dr 's is independent and that De. depends only on z', We claim that
QiEy ... Er
Σ llz,, it)
Q
Egr
Σ (lzz, Ut)
We prove the case for T demonstrate the ideas; the general case follows by induction. Observe that
Eg Q2E (((z 01) + l(zz, 92)l
Q E. [[( 01) + Qg ((zz, 02)]
Eg [[(z)) 01 Eg Q2 El2, 02)1
[Bg.
12)
E3 ( Q2 E. [8(z) (1) l 02)
Qo
19

---

where (a) follows since E(z1, D1) is independent of g2 (6) follows by the linearity of expectation; (c) follows by the independence of Ùn and 1/2. since the term 22 (zz, (2) has nothing do with the realization of ÿ1: (d) follows since Egg [f(21, vn) )] is independent of 22: (e) follows by the linearity of expectation.
Observe that, all the predictors constructed in this paper have independent internal randomness (in fact, the only place where randomness is introduced is in Algorithm I]: thus, our derived risk bounds hold for adaptive adversaries as well.
20

---

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:
The abstract and introduction is accurate to reflect the paper's contributions.
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to 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: Limitation is discussed in the Discussion section
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 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 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 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 images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
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 't acknowledged in 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.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
21

---

Justification:
The assumptions are accurate and the proofs are complete.
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 referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch 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.
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 affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: This is pure theory paper.
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 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 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 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 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 are 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) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either 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).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, 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 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?
22

---

Answer:
[NA]
Justification:
This is pure theory paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ cppppi.ccppulli//uuuii wwwiiicgguie//eeeeeeeeeic CoodeSubeiiie ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how 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. If 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 as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code 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 to understand the results?
Answer: [NA]
Justification: This is pure theory paper.
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, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is pure theory paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
23

---

It is OK to report 1-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 enrors 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 are out 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 to reproduce the experiments?
Question:
Answer: [NA]
Justification: This is pure theory paper.
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 of 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: htttps:/ //te:r:////.i...eeeee wwweeerris.cccpppppppoooo https///ccpppccccccccccceeeeeeee
Answer:
[Yes]
Justification:
We confirm the paper meets the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a 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: This is pure theory paper, we do not any direct societal impacts.
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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out 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.
there are negative socictal 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 a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This is pure theory paper.
Guidelines:
The answer NA means that the paper poses no 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 challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators 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?
Question:
Answer: [NA]
Justification:
This is pure theory paper.
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 dataset.
The authors should state which version of the asset is used and, if possible, include 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 (c.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, wwppppswpptseeee whworeeswthhhe....c. com/ 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 has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
25

---

Answer: [NA]
Justification:
This is pure theory paper.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/coddemoodll as part 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 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 to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This is pure theory paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included 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.
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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This is pure theory paper.
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 expect authors to adhere 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.
26


Reviews:
[{"review_id": "2C6AeZLRxV", "reviewer": "Reviewer_JscE", "summary": "The paper generalized an agnostic online learning setting from [1]: Nature sequentially produces arbitrary feature vectors, and a noiseless label chosen from an arbitrary hypothesis within a given class. The learner observes the feature vector (exactly), and a noisy label chosen from a distribution chosen from a class of distributions, where the identity of the class depends on the noiseless label. The goal of the learner is to minimize the expected cumulative risk. The paper's main result (Theorem 2, also presented in a simplified form in Theorem 1) is characterization of the high probability (upper bound) and expected risk (lower bound) in terms of the Hellinger gap. The result follows from a proposed learning algorithm, which is based on pairwise testing. In addition, assuming a positive $L_2$ gap, tighter upper bounds are obtained w.r.t. the cardinality size of the hypothesis class (Theorem 5).", "questions": "1. What is the conclusion from Example 1? From the paragraph that precedes it, it appears that it meant to justify either the semi-stochastic setting or the evaluation of the risk on the true labels, but it is not discussed how. From reading the rest of the paper, it appears that the analysis in this paper is a generalization of the result in Example 1, but this is not an intrinsic motivation. \n\n2. Proof of Theorem 2: To the best of my knowledge, such problem is called *composite* hypothesis testing (rather than robust), and this was extensively studied in the information-theoretic literature. In this regard, the error in hypothesis testing is related to the KL divergence, for which chain rule is much more suitable to distributions that are not in product form via the standard chain rule. My question is why can't the analysis be made in terms of the KL divergence ? \n\nFinally, regarding line 41, what is differential piracy ? Only attacking some ships ? :-)", "limitations": "The paper properly discusses limitations throughout.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. Theorem 2 captures the exact dependence on the Hellinger distance $\\gamma_H$, by providing upper and lower bounds whose dependence on that parameter is $\\Theta(1/\\gamma_H)$.\n\n2. An additional result based on $L_2$ distance, which is tight also in the log-cardinality of the hypothesis class. \n\n3. The introduction of the surrogate pairwise loss function and evaluating the loss by its maximum over all competing hypothesis, as well as the resulting reduction of online learning to binary hypothesis testing is interesting.", "weaknesses": "My main issue with the paper is that given the separation condition and finite hypothesis class, the resulting learning task is “easy”:\n\n1. The assumption of a strictly positive Hellinger distance significantly eases the learning task. The immediate consequence of this is that the cumulative risk is bounded in $T$, and also hints the ease of the learner's task. As the algorithm also suggests, the problem is reduced to a composite binary hypothesis testing using $T$ samples, followed by static play of that decision. \n\n2. Given that the problem is interesting, it is worth to already address the infinite class setting, and noises that are not uniformly bounded. While the technical details *might* be routine, the dependency of the risk bounds should be interesting, and, in relation to the previous comment, might also lead to elaborated risk bounds, with interesting dependency on the function class (parametric/a-parametric) and the noise conditions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed review and helpful comments. We now address the main concerns raised below:\n\n**Non-triviality of problem setup:** We would like to clarify that the non-triviality of our pairwise testing scheme lies in how to *use* the testing results in an *online* fashion, as the testing results are not reliable (only the tests involving the ground truth are reliable, but it is *unknown* a priori). Moreover, the pairwise testing is not actually \"static\" since the composite distribution sets depend on the features, which are unknown as well. In fact, even for the Bernoulli noise case, the proof (c.f. Ben-David et al., Theorem 15 [1]) relies on quite non-trivial *backward induction*. It is not clear at all from their proof how the denominator $1-2\\sqrt{\\eta(1-\\eta)}$ arises. One of our primary contributions is to figure out the *precise* complexity measure (i.e., the Hellinger gap) that determines the learning complexity and to provide a clearer characterization of the underlying paradigm.\n\nWe would like to emphasize that the Hellinger gap (and the noisy kernel formulation) is not actually an \"assumption\" but a *consequence* of our characterization. It is our kernel formulation that allows us to approach the noisy online classification problem in such a clean manner, considering that prior proof techniques (c.f. [1]) are quite obscure even for Bernoulli noise.\n\n**Non-uniform gap and infinite classes:** In fact, as  mentioned in Remark 1, our technique also works for *infinite classes* and *non-uniform* gaps. Indeed, for any class $\\mathcal{H}$ of finite Littlestone dimension $\\mathsf{Ldim}(\\mathcal{H})$, we can apply our algorithm on the *sequential* experts constructed in Section 3.1 of [1] (specifically the multi-class version) to arrive at an upper bound $O(\\frac{\\mathsf{Ldim}^2(\\mathcal{H})\\log^2 (NT)}{\\gamma_H})$. For binary-valued classes, Theorem 5 also implies an $O(\\frac{\\mathsf{Ldim}(\\mathcal{H})\\log T}{\\gamma_L})$ upper bound. Moreover, for the *non-uniform* gaps, such as Tsybakov noises of order $\\alpha$ as in [8], our results (primarily Proposition 1 and Theorem 3) implie a risk of order $\\tilde{O}(T^{\\frac{2(1-\\alpha)}{2-\\alpha}})$, and this is tight up to poly-logarithmic factors.\n\nWe have chosen to omit these results in the submission due to limited space and their incremental nature, but we are happy to include them in the final version (given the additional page).\n\n**Questions:**\n\n1. Example 1 is meant to provide a concrete instance of how stochastically generated labels (i.e., with Massart noise) can lead to non-trivial risk bounds on true labels that are independent of the time horizon, even though the noise rate is linear in T. Therefore, it is natural to investigate to what extent such a phenomenon can occur in more general noisy settings and to find the precise complexity measure that characterizes learnability. See also our global rebuttal for examples on differential privacy.\n\n2. We thank the reviewer for clarifying the terminology. Our Hellinger-based testing error bound is essentially a *conditional* version of the Theorem 32.8 from [17]. We are unaware of any (general) analysis based on KL-divergences (we would greatly appreciate it if the reviewer could point it out to us). Since the KL-divergence is *not* symmetric, it is not well-suited to our case since we need to measure the *distance* between *sets*.\n\n**Typos:** We thank the reviewer for catching the typo; the correct term should be \"differential privacy.\"", "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": "oREMqtUTfP", "reviewer": "Reviewer_crkZ", "summary": "This paper studies online classification where the features are chosen adversarially, but the labels are corrupted by some unknown stochastic noise. The learner makes predictions using the true features and noisy labels, but is evaluated against the true labels (noiseless) in the minimax sense. The authors consider a very general noise generation mechanism specified by a kernel, which for every (feature, true label) pair, outputs a subset of distributions over the noisy label space. The adversary generates the noisy label by picking a distribution output by the kernel and sampling from it. The authors study the minimax risk under this setting and derive upper and lower bounds on the minimax risk in terms of the Hellinger gap of the noisy distributions output by the kernel and the cardinality of the hypothesis class. The upper and lower bounds differ only by a log factor in the cardinality of the hypothesis class, showing that (up to log factors), the Hellinger gap is the correct complexity measure of the kernel that characterizes the minimax rates. The authors prove these results by developing a novel reduction from noise online classification to hypothesis testing. Along the way, they provide guarantees for a new conditional version of Le Cam-Birge testing in the online setting.", "questions": "- Is my interpretation of the minimax value correct? If so, I think it would be nice to make this explicit in text. \n- Can you give me some concrete learning problems for which your results provide new insights (i.e can you justify the generalization of the noise mechanism)?\n- Can you comment about universal lower bounds in your setting? \n- Can you comment on the generalization of your results to infinite hypothesis classes? Is it true that using your results with existing covering arguments would result in factors of N and M (the cardinalities of true and noisy label spaces) appearing in your bounds?\n- Right now, your bounds are written in terms of two separate complexity measures - one on the hypothesis class (i.e its cardinality) and one on the kernel (i.e. well-separated). Could there be a single complexity measure, a function of both the hypothesis class and kernel, that better captures the minimax value? If so, do you have any intuition on what this might be or what difficulties arise when trying to do so? \n- Your existing results assume that the kernel outputs sets of distributions that are convex and closed. It would be nice if you can make explicit where exactly this assumption is being used in the main text. In addition, what can be said if you are guaranteed that the kernel always outputs a finite set of distributions (say of size at most G)? Can you comment on how would the minimax rates would scale with G?", "limitations": "No limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and easy to follow\n- The problem of noisy online classification is well-motivated (but also see weakness below)\n- The technical contributions are interesting and the proof techniques are novel. In particular, I found the reduction to pairwise hypothesis testing to be nice\n- Overall, I think this paper makes a solid contribution to the literature on online classification", "weaknesses": "- More clarification is needed about the problem setup beyond just stating the minimax value. From what I can get, the adversary is oblivious and must pick the entire sequence of features, true labeling hypothesis, and noisy labels before the game begins. However, there seems to be some subtlety in the choice of how the adversary can pick the noisy labels which I feel requires explanation in the main text. In particular, the adversary can select noisy label distributions based on the realized values of the previous nosy labels. This contrasts from a weaker adversary which has to pick the entire sequence of noisy label distributions up front, and then samples the entire sequence of noisy labels. \n\n- Lack of motivation for generalization. While it is nice to provide results for a generalized noise mechanism, ideally there is some sort of justification for the generalization beyond theoretical curiosity (i.e why should I care). It would be nice if you can provide concrete example of real-world situations (i.e. specifying the instance space, label, space, noisy label space, kernel etc.) which are captured by your generalization, but not by previous noise models. As far as I can tell, applications to privacy, online denoting, and physical measurements are mentioned, but not expanded upon. Overall, I think it would be nice to provide more motivation behind why I should care about generalizing the noise mechanism. \n\n- Lack of universal lower bounds. While the upper bounds are stated for every (finite) hypothesis class, the lower bounds are of the form \"there exists a hypothesis class such that the minimax value is at least...\". It would nice to have universal lower bounds of the form \"for every hypothesis class, the minimax value is at least...\". \n\n- Finite Hypothesis Class. This paper currently only studies the minimax rates for finite hypothesis classes. There is a remark indicating that the results extend to infinite hypothesis classes via covering techniques from [1, 21], however neither the proof of this statement, nor the resulting minimax rates are provided. I am not super convinced that these existing covering techniques can give you bounds on the minimax value that are independent of the sizes of the true and noisy label spaces (like your existing bounds are). For example, for the simply hypothesis class $H = \\{ x \\mapsto a: a \\in [N] \\}$, to cover a single point $x \\in X$, you need the entire hypothesis class $H$.  It would be nice if you can give the upper and lower bounds on the minimax value for infinite hypothesis classes that your results imply along with a proof sketch. \n\nPlease see questions below regarding each of these weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed review and helpful comments. We now address the main concerns raised below:\n\n**Adaptivity w.r.t. Noisy Labels:** Indeed, in our setup, the noisy label distributions are selected *adaptively*, while the features are selected obliviously w.r.t. the realization of noisy labels. In fact, the features can also be made adaptive to noisy labels for the risk bound in Theorem 5. However, oblivious features are required in our *conditional* Le Cam Birgé testing, i.e., Theorem 4 (although we believe this can be resolved using a more tedious minimax analysis that involves both $x^J$ and $y^J$). Therefore, for the clarity of presentation, we have assumed that the features are generated obliviously w.r.t. noisy labels. We will make this clearer.\n\nPlease note that the oblivious assumption for noisy label distributions and features w.r.t. the *learner's prediction* is not essential by a standard argument (c.f. Appendix H), provided the predictions have *independent* internal randomness among different time steps (which is satisfied by our algorithms).\n\n**Motivation for Generalization:** One of the primary motivations for generalization is to deal with cases with multi-class labels, where prior techniques based on EWA algorithms do not apply. A concrete example is that of Example 2. Note that we can instantiate Example 2 to the multi-class *randomized response mechanism* in differential privacy by specifying the $p_y$ as the singleton distribution that assigns probability 1 on $y\\in \\mathcal{Y}$ (with $\\mathcal{Y}=\\tilde{\\mathcal{Y}}$)  and the TV-radius is $\\frac{N}{e^{\\epsilon}-1+N}$ (to achieve $(\\epsilon,0)$ local differential privacy).  To our knowledge, the risk bound implied by our result is novel for this particular differential private online setting. Please refer to our global rebuttal for more details.\n\n**Universal lower bounds:** Indeed, our lower bound only holds in the minimax sense. Although, an $\\Omega(\\frac{1}{\\gamma_H})$ lower bound holds for *any* non-trivial classes (i.e., there exist at least two distinct functions).\n\n**Infinite Classes:** Indeed, for any class $\\mathcal{H}$ of finite Littlestone dimension $\\mathsf{Ldim}(\\mathcal{H})$, we can apply our algorithm on the experts constructed in Section 3.1 of [1] (specifically the multi-class version) to arrive at an upper bound $O(\\frac{\\mathsf{Ldim}^2(\\mathcal{H})\\log^2 (NT)}{\\gamma_H})$ (independent of the noisy label set size $M$). Note that a logarithmic dependency on $N$ is necessary for finite Littlestone dimension classes (in the worst case). To see this, consider the class $H$ constructed by the reviewer. It is easy to see that the class has Littlestone dimension 1. However, one can assign the noisy label distributions to each $a\\in \\mathcal{Y}$ with constant pairwise KL-divergences (using, e.g., distributions of the form $p[m]=\\frac{1\\pm \\epsilon}{M}$ for $m\\in \\tilde{\\mathcal{Y}}$ with $M \\sim\\log N$). The $\\Omega(\\log N)$ lower bound will then follow by Fano's inequality. This is in contrast to the noiseless setting where the regret is independent of label set size.\n\n**Unified measure:** As mentioned above, we conjecture that the correct growth might be $O(\\frac{\\mathsf{Ldim}(\\mathcal{H})\\log(NT)}{\\gamma_H})$ for any \"non-trivial\" class $\\mathcal{H}$ and kernels independent of features. However, a general unified measure seems to be far from being achievable using our current techniques. This is due to the complicated structure of $\\mathcal{H}$ and the weakness of Le Cam's two-point method (used in our lower bound proof). We believe investigating such a unified complexity measure would be of significant interest for future research.\n\n**Convexity Assumption:** The convexity assumption is used in the Le Cam Birgé testing (for the minimax theorem to work). Please note that the convexity is *without loss of generality* in our setting, since the adversary is allowed to choose the distribution arbitrarily, including a randomized strategy that is effectively selected from the convex hull. Therefore, any distributional strategy that the adversary might choose can be represented within this convex framework.", "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": "iJ6rHBSJF3", "reviewer": "Reviewer_GopC", "summary": "This paper studies online classification with stochastic label noise, where a hypothesis $h^*$ is drawn from some hypothesis class $H$ and the learner wants to learn $h^*$ by observing the noisy labels of the online data.\nThe standard mistake bound used in online learning counts the number of predictions different from the true labels. In this paper, instead, the mistake bound counts the number of predictions that disagree with the target $h^*$.\nThis paper proposes Noisy Kernel, a new framework to model the label noise, which generalizes the bounded noise setting studied by prior work. The main result of this paper is to show that the Hellinger gap of the noisy kernel gives a good characterization of the min-max mistake bound of learning a finite hypothesis class under their model. Specifically, they design a learner with mistake bound $\\log^2(|H|)/\\gamma_H$, where $\\gamma_H$ is the Hellinger gap of the noise kernel. On the other hand, for any fixed noisy kernel, they design a hypothesis class $H$ such that every learner has a mistake bound at least $\\log(|H|)/\\gamma_H$ to learn $H$. For the binary classification problem, the author further designs a learner with a mistake bound $\\log(|H|)/\\gamma_L$, where $\\gamma_L$ is the $L^2$ gap of the noisy kernel, improving the dependence on $\\log(|H|)$.", "questions": "1. The model of the noisy kernel is not as intuitive as the prior noisy models such as Massart noise. In section 5, the authors mention that the noisy kernel model has many applications such as learning with privacy constraints or learning from quantum data. What would be the noisy kernels for these types of problems?\n\n2. To run the learner designed by the paper, one has to know the error bound of the pairwise hypothesis testing problem. How can one know such an error bound before running the online learning algorithm? If we do not know such a bound, would it be possible to get any data-driven algorithm?\n\n3. I would like the authors to comment on the weakness pointed out above.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper proposes a novel framework that models the label noise for the online classification problem. This generalizes the previous model for bounded label noise.\n2. To prove the upper bound for the mistake bound, the paper introduces a novel reduction from the classification problem to the pairwise hypothesis testing problem, which could potentially be useful for designing algorithms for other learning problems.\n3. A matching lower bound on the dependence on the Hellinger gap of the noisy kernel is proved.", "weaknesses": "1. Though the framework proposed by the paper models a large class of noise models, the learner designed by the paper only works for learning finite hypothesis classes.\nPrior work, Agnostic Online Learning by Ben-David et al. proves a mistake bound that depends on the Littlestone dimension of the hypothesis class. There is a big gap between hypothesis classes with finite Littlestone dimension and finite hypothesis classes. For example, the class of singleton functions is infinite but has Littlestone dimension 1. Such a simple class is not learnable using the learner designed by the paper because it is impossible to do pairwise hypothesis testing for an unbounded set of hypotheses.\nFrom this point of view, I do not think the paper fully answers which class is learnable under their noisy model. \nPerhaps, this might be because the noise model studied by the paper is too general and is thus hard for one to design algorithms that make use of the structure of the hypothesis class.\n\n2. Though the paper gives a tight bound on the dependence on the Hellinger gap of the noise kernel, the upper bound and the lower bound differ by a $\\log(|H|)$ factor, which is sometimes linear in the dimension of the input and thus cannot be ignored in general. Though the paper shows that for binary classification, they can close this gap, a new gap on the dependence of the divergence gap is created.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed review and helpful comments. We now address the main concerns raised below:\n\n**Infinite Classes:** In fact, as mentioned in Remark 1, our techniques also work for *infinite classes*. Indeed, for any class $\\mathcal{H}$ of finite Littlestone dimension $\\mathsf{Ldim}(\\mathcal{H})$, we can apply our algorithm on the *sequential* experts as in Section 3.1 of [1] (specifically the multi-class version from Daniely et al., 2015, Thm. 25) to arrive at an upper bound $O(\\frac{\\mathsf{Ldim}^2(\\mathcal{H})\\log^2 (NT)}{\\gamma_H})$. This follows because our pairwise testing framework works for the *sequential experts* as well, which is *finite* and of size $(NT)^{\\mathsf{Ldim}(\\mathcal{H})+1}$. By construction of the experts, any risk achieved against the (finite) sequential experts implies the same risk for the (infinite) class $\\mathcal{H}$. See also our general rebuttal and responses to reviewers crkZ and JscE for further consequences.\n\n**Tightness on $\\log |\\mathcal{H}|$:** Indeed, our logarithmic factor can result in an additional factor for Littlestone dimension. This is introduced by the aggregating of pairwise testings in Algorithm 1. We would like to emphasize that pairwise testing is an essential technique for dealing with *multi-class* label classes. We are unaware of any prior technique that can even lead to *sublinear risk* for the multi-class cases. Therefore, we view our result as significant even with a suboptimal logarithmic factor, as it provides the first known systematic treatment of this problem.\n\n**Questions:**\n\n1. Consider the general template in our Example 2, which can be viewed as a \"generalized\" Massart noise in the multiclass case. For the multi-class *randomized response mechanism* in differential privacy, please refer to our global rebuttal for a concrete construction. To realize the quantum setting, one may consider the task of classifying quantum states into certain classes (i.e., our true labels). Here, the kernel set for any given label would be the collection of all distributions induced by certain measurement on the quantum states corresponding to that class.\n\n2. Indeed, Algorithm 1 needs to know the upper bound of the pairwise testing error $C$. This error bound is completely determined by the Hellinger gap of the kernel and not the realization of the data; please refer to our proof of Theorem 2. Since the Hellinger gap is an intrinsic complexity measure of the problem, it can be used as an input for the algorithm. We believe that investigating a data-dependent way of selecting the parameter $C$ is also of significant interest. In fact, using a multiplicative weighted majority algorithm with a substantially more complicated potential-based analysis, we can show that an $O(C^2+C\\log(CK))$ risk bound holds without the knowledge of $C$. However, it is unclear to us whether this bound is tight for unknown parameter $C$.\n\n[DSBS15]  A. Daniely, S. Sabato, S. Ben-David, and S. Shalev-Shwartz. Multiclass Learnability and the ERM Principle. JMLR 2015.", "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": "I0dbdRcUG1", "reviewer": "Reviewer_uBfk", "summary": "The paper addresses the problem of online classification where the true labels are corrupted by unknown stochastic noise and the features are adversarially generated. The main contributions of this paper include: 1. Establishing fundamental limits of minimax risk in online classification with noisy labels by nearly matching lower and upper bounds across various hypothesis classes and noisy kernels; 2. Introducing a reduction to an online comparison scheme of two hypotheses and a new conditional version of Le Cam-Birgé testing suitable for online settings; 3. Characterizing the minimax risk using the Hellinger gap of noisy label distributions.", "questions": "1. How do the assumptions regarding the noise model and hypothesis class impact the generality of the results? Can the methods be adapted to other types of noise or broader hypothesis classes?\n2. Have you considered any practical applications or scenarios where your theoretical findings could be applied? If so, what are the potential challenges in these applications?", "limitations": "- Limitations: In the discussion section, the discussion on the limitations is not sufficient. It's difficult for readers to find this part.\n- Societal Impact: As this is a pure theory paper, there are no direct societal impacts. However, the authors could briefly mention potential positive impacts, such as improved robustness in machine learning models dealing with noisy data, and any negative implications if misapplied, such as in adversarial settings.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "+ The theoretical analysis is rigorous, providing clear bounds and demonstrating their tightness through detailed proofs. The paper systematically addresses various aspects of the problem, ensuring a comprehensive exploration.\n+ The paper is well-structured, with clear definitions and thorough explanations of the concepts and results. Theorems and proofs are presented in a logical sequence.", "weaknesses": "- While the theoretical contributions are good, the paper could benefit from discussing practical implementations and real-world applications of the proposed methods.\n- Some assumptions, such as the nature of the noise and the hypothesis class, might be restrictive. A more detailed examination of these assumptions' impact on the results' generality would strengthen the paper.\n- The paper lacks experimental validation of the theoretical results. Providing empirical evidence, even in simulated settings, would enhance the credibility and applicability of the findings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed review and helpful comments. We address the main concerns raised below:\n\n**Real-World Application:** Our theoretical work is motivated by a number of important real-world applications. These applications involve, e.g., learning under measurement imprecision, estimation and communication error, and noise introduced for differential privacy. For instance, in a differential privacy setting, noise can arise from certain privacy mechanisms, and our noise kernel for a given label corresponds to the collection of all distributions when passed through the privacy mechanism. Additionally, in quantum learning, one may consider the task of classifying quantum states into certain classes. Here, the kernel set for any given label is the collection of all distributions induced by measurements on the quantum states corresponding to that class. Finally, in the context of genome sequencing—where the raw output from the sequencer must be classified into one of four bases (A, T, C, G)—this is done using a base-calling process that is inherently noisy. These problems can be cast within our framework. We refer the reviewer to our global rebuttal for a concrete construction that demonstrates how our theory applies in the context of differential private online learning.\n\n**Assumptions:** We would like to clarify that our work is not intended to introduce any specific noise models. Rather, our main focus is to provide a *characterization* to determine, for any given noise model, the *best achievable* minimax risk. Since our formulation of noise kernels is *general* and we do not make structural assumptions on the class (except finiteness), our result is applicable to a wide range of noisy online classification problems (such as those highlighted above). Although our results are stated for uniformly bounded gaps and finite classes, they can be extended to *non-uniform* gaps and *infinite* classes (see our global rebuttal and responses to Reviewers JscE and crkZ).\n\n**Experiments:** Our work is primarily focused on theoretical aspects (particularly the *worst-case* minimax risk), and experiments are typically not expected for such pure theory contributions in the literature. For example, Ben-David et al. (2009) and many other foundational works in our references do not include experiments. Our results are established via rigorous proofs, ensuring that the worst-case risk bounds will hold for real data, provided the noisy data follow the prescribed kernel. While empirical validation is valuable, it lies beyond the scope of our current theoretical investigation and could be a potential avenue for future work to complement our findings.\n\n**Limitations:** We appreciate the reviewer's feedback regarding the discussion of limitations. We would be grateful if the reviewer could specify any particular limitations, and we will be happy to address them.", "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:
We thank all of the reviewers for their helpful comments. We would like to clarify the following two concerns shared by most of the reviewers:

**Infinite Classes:** As mentioned in Remark 1, our techniques also work for *infinite classes*. Indeed, for any class $\mathcal{H}$ of finite Littlestone dimension $\mathsf{Ldim}(\mathcal{H})$, we can apply our algorithm on the *sequential experts* as constructed in Section 3.1 of [1] (specifically the multi-class version from Daniely et al., 2015, Thm 5) to arrive at an upper bound $O(\frac{\mathsf{Ldim}^2(\mathcal{H})\log^2 (NT)}{\gamma_H})$. This is because, for any finite Littlestone dimensional class, we can always find a *finite* sequential cover of size $(NT)^{\mathsf{Ldim}(\mathcal{H})+1}$; therefore, it can be effectively reduced to the finite classes case resolved in our work.

**Real-World Applications:** We would like to clarify that our work is not intended to introduce any specific noise models. Rather, our main focus is to provide a *characterization* to determine, for any given noise model, the *best achievable* minimax risk. Since our algorithmic approach is general, it will serve as a baseline for various application scenarios.

To give a clear exposition on how this works, we consider the following *online local differential privacy* setting. Let $\mathcal{H}$ be a hypothesis class with label set $\mathcal{Y}$ of size $N$. The *randomized response mechanism* works as follows: for any $y \in \mathcal{Y}$, we generate $\tilde{y}$ being $y$ with probability $1-\eta$ and generate *uniformly* from $\mathcal{Y}$ with probability $\eta$, where $\eta \le \frac{N}{e^{\epsilon}+N-1}$ (which achieves $(\epsilon, 0)$-local differential privacy). In this case, the noisy label set equals the true label set and the *noisy kernel* maps each $(x, y)$ to the distribution set $\\{(1-\eta)e_y + \eta u : \eta \leq \frac{N}{e^{\epsilon} + N - 1}\\}$ where $e_y$ assigns probability 1 to $y$ and $u$ is uniform over $\mathcal{Y}$. It is not hard to verify that the Hellinger gap of the kernel is $\Theta(\frac{\epsilon^2}{N})$ (for sufficiently small $\epsilon$). Our Theorem 2 then implies the risk bound $O(\frac{N\log^2|\mathcal{H}|}{\epsilon^2})$. To our knowledge, the implied risk bound is original for this particular differentially private multi-class online setting.

[DSBS15]  A. Daniely, S. Sabato, S. Ben-David, and S. Shalev-Shwartz. Multiclass Learnability and the ERM Principle. JMLR 2015.

Meta-review: A borderline paper. It is a theory paper on online classification with a very general stochastic label noise corruption and the input features can be generated adversarially. The paper characterizes learning rates by a notion of Hellinger gap and reduction to a testing problem. The reviews agree that the paper is well-written and the contribution interesting, especially the reduction to pairwise testing and the fact that the model can be seen as a generalization of previous noise models (eg Massart noise). On the other hand, the results for now only apply to the case of a finite hypothesis class, and while the authors discussed convincingly that their results could be extended to infinite classes (using Littlestone dimension), they recognize that the complexity of the class (or log-cardinality in the case of a finite class) only appears in the upper bound and not the lower bound, resulting in a significant theoretical gap. The request for experimental validation by one reviewer seems out of place given that the paper's focus is precise theory. 

Overall weak accept recommendation.
Decision: Accept (poster)