Information-theoretic Limits of Online Classification with Noisy Labels

We thank the reviewer for the detailed review and helpful comments. We address the main concerns raised below:

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.

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

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.

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.

We thank the reviewer for the detailed review and helpful comments. We now address the main concerns raised below:

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.

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.

Questions:

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

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

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

We thank the reviewer for the detailed review and helpful comments. We now address the main concerns raised below:

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.

Please 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).

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.

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

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.

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.

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.

We thank the reviewer for the detailed review and helpful comments. We now address the main concerns raised below:

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.

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

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.

We 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).

Questions:

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

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

Typos: We thank the reviewer for catching the typo; the correct term should be "differential privacy."