Representation Preserving Multiclass Agnostic to Realizable Reduction

We thank the reviewer for dedicating their time to assess our work. Below, we address the comments provided by the reviewer.

1. The significance of our work: We establish the first representation-preserving reduction from agnostic to realizable learning for multiclass classification with an infinite label space, in addition to various other learning settings. Notably, this type of reduction was not presented in the work of David, Moran, and Yehudayoff (2016). This is because their approach relied on a compression-based reduction using boosting, which increases the complexity of the agnostic learner’s hypothesis class compared to that of the realizable learner. In contrast, our algorithm is representation-preserving, meaning the agnostic learner’s hypothesis class remains the same as that of the realizable learner. Thus, our algorithm and results are fundamentally different from theirs. In particular, ours is the first proof that a class $\mathcal{C}$ is agnostically learnable with hypothesis class $\mathcal{H}$ if and only if $\mathcal{C}$ is realizably learnable with hypothesis class $\mathcal{H}$.

2. The novelty of our work: Of course we take inspiration from the work of Hopkins et al., but the key ingredient in our algorithm is novel. In particular, the algorithm of Hopkins et al. runs a realizable learner on an unlabeled sample with all possible labelings, which can only apply to learning settings with a finite effective label space. However, our algorithm runs a realizable learner on all the subsets of a labeled sample, which can handle learning problems with an infinite label space, i.e. multiclass PAC learning with an infinite label space. Moreover, the analysis of the algorithm is also different, as we must account for the variable size of the optimal subset present in this initial labeled data set. Therefore, we designed a novel algorithm with crucial technical differences compared to previous works. This answers an open problem mentioned in the work of Hopkins et al.

3. Correctness of Theorem A.3: Thank you for your skepticism, but as we will explain the result in Theorem A.3 is correct (though we should note there is a typo on page 11 line 558, where it should say $L(*,\cdot)=1$). In the example you constructed, we suspect there may be a typo in your definitions, since if the distribution $\mathcal{D}$ is supported on $(b,0)$, then according to your loss definition this distribution would be realizable by hypothesis $g$, since $L(g(b),0) = L(1,0) = 0$ (your loss has $L(1,0)=0$). We suspect your intention in the construction might have been to construct a scenario where the realizable learner always returns a function with loss $1$. Such cases can indeed occur, and are compatible with our result, since then the best-in-class loss $L_{\mathcal{D}}(\mathcal{C}) = 1$, and we trivially satisfy the agnostic learning guarantee $L_{\mathcal{D}}(A(S)) \leq 1 \leq L_{\mathcal{D}}(\mathcal{C}) + \epsilon$.

We hope this rebuttal convinces you of the significance and novelty of our contributions, and addresses your concern about the correctness of Theorem A.3.

We thank the reviewer for dedicating their time to assess our work. In particular, we thank the reviewer for taking the time to verify that the work is technically sound. We are delighted that the reviewer found that we solved an interesting open problem in an elegant way, and moreover mentioned that our paper is well written. We will make sure to correct the typos and incorporate minor suggestions mentioned by the reviewer for the camera-ready version. Below, we address the major comments provided by the reviewer.

1. Other comments or suggestions:

• It is $\epsilon/(2 \mu^*)$.
• There should be a $\epsilon/2$ on the right-hand side of equation 9.

2. Question about representation preserving property: Thank you for this insightful discussion. Your understanding of the prior literature is accurate. For multiclass classification, if we use Algorithm 1 from Brukhim et al. (2022) as our input realizable learner, our approach will yield the same hypothesis class as presented in their paper. And indeed, since that algorithm is compression-based, the reduction of David et al. will be representation-preserving. However, a key advantage of our reduction algorithm lies in its flexibility. For instance, if a realizable learner with simpler hypotheses is available for a given problem, our Algorithm 1 can directly leverage it to produce a correspondingly simpler agnostic learner, which is not necessarily achievable with prior methods. As another interesting example, our reduction would be applicable, and representation-preserving, for realizable learners based on optimally orienting the one-inclusion hypergraph (which we generally would not expect to be compression-based), and in fact would return a predictor which itself is expressed as such an orientation using a subset of the data $V$. The fact that we return a predictor produced by the realizable learner is itself another notion of simplicity (e.g., a predictor based on an orientation of the realizable-case one-inclusion hypergaph is simpler than majority votes of such predictors, and the simplicity is even more apparent compared to a predictor based on an orientation of the agnostic one-inclusion hypergraph).

We thank the reviewer for dedicating their time to assess our work. In particular, we thank the reviewer for taking the time to verify that the work is technically correct. We are delighted that the reviewer found our work nice and important, and moreover mentioned that our paper should be interesting to the theoretical ICML community. We will make sure to correct the typos and incorporate minor suggestions mentioned by the reviewer for the camera-ready version. Below, we address the major comments provided by the reviewer.

1. Running realizable learner on unrealizable sets: Thank you for pointing this out. In this work, our definition of learning algorithm requires it to always return a function. However, for learners that only satisfy this for realizable input data sets, we can still apply our reduction by simply modifying line 2 of our algorithm to only run $A$ on all subsets of $V$ that are realizable by $\mathcal{C}$ (which could be identified using a "weak consistency" oracle for $\mathcal{C}$). The theorem and proof remain valid.

2. The algorithm of Hopkins et al. does not work for multiclass classification with an infinite effective label space: Thank you for this insightful question. We address it by noting the Hopkins et al. reduction fails for the well-studied "stars and sets" concept class, namely Example 4.1 of Daniely et al. (2011). Specifically, consider $\mathcal{X} = [0,1]$, denote by $\mathcal{F}(\mathcal{X})$ the collection of all finite subsets $A\subseteq \mathcal{X}$. Let the label space $\mathcal{Y} = \mathcal{F}(\mathcal{X}) \bigcup \lbrace\star\rbrace$, where $\star$ is a special label (not to be confused with "$*$" from the partial concept classes section). For every $A\subseteq \mathcal{X}$, define $f_{A}:\mathcal{X}\rightarrow\mathcal{Y}$ as follows:

Let the concept and hypothesis class be $\mathcal{C} = \mathcal{H} = \lbrace f_A: A\in \mathcal{F}(\mathcal{X}) \cup \mathcal{X}\rbrace$. Then, there is a realizable learner $\mathcal{A} _ {\text{good}}$ that returns $f_{\mathcal{X}}$ unless a label $A \in \mathcal{F}(\mathcal{X})$ appeared in the sample, in which case it returns $f_A$. Let $\mathcal{D}$ have marginal on $\mathcal{X}$ the uniform distribution over $\mathcal{X}$, and let the labels be always $\star$ (i.e., realizable with target $f_{\mathcal{X}}$). Now, consider the algorithm of Hopkins et al. with this scenario and realizable learner $\mathcal{A} _ {\text{good}}$. Let the unlabeled dataset be $S_U = \lbrace x_1, x_2,\cdots, x_n\rbrace$, and the labeled dataset be $S_L =\lbrace(x_{n+1},\star),(x_{n+2},\star),\cdots,(x_{n+m},\star)\rbrace$, and with probability one these $x$'s are all distinct. Denote $A = \lbrace x_{n+1},x_{n+2},\cdots,x_{n+m}\rbrace \in \mathcal{F}(\mathcal{X})$. Then their algorithm would run $\mathcal{A} _ {\text{good}}$ on all realizable labelings of $S_U$; in particular, one of these is $(S_U,f_A(S_U)) = \lbrace (x_{1},A),\ldots,(x_{n},A)\rbrace$, and the output hypothesis of $\mathcal{A} _ {\text{good}}(S_U,f_A(S_U))$ would be $f_A$. By the definition of $f_A$, we know that the empirical error of $f_A$ on $S_L$ is 0. Their algorithm then outputs any ERM on $S_L$ from these functions produced by $\mathcal{A} _ {\text{good}}$, which means their algorithm can output $f_A$. However, the true error rate of $f_A$ is 1, while the best error in the concept class is 0. Thus, their algorithm fails for this concept class (for essentially the same reason ERM fails for this concept class). In contrast, our algorithm returns $f_{\mathcal{X}}$, hence achieves error 0.

3. Sample complexity when we have a finite effective label space: Thank you for pointing this out. For multiclass classification with a finite effective label space size $|\mathcal{Y}| _ {\text{eff}}$, the sample complexity of our reduction can be reduced to $\tilde{O}(1/\epsilon^2)$ rather than $\tilde{O}(1/\epsilon^3)$. More specifically, in this case learnability of $\mathcal{C}$ is equivalent to finite Natarajan dimension $d$, and we can use a similar argument as above, only running the realizable learner on the maximal realizable subsets of $V$, of which there are at most $|V|^d |\mathcal{Y}|^{2d}_{\text{eff}}$ using Natarajan's generalization of the SSP Lemma, so that this bounds the size of $\mathcal{H}_V$ (rather than $2^{|V|}$), leading to a refinement of the final bound (though this analysis then becomes much closer to that of Hopkins et al.).

4. Sample complexity lower bound: We note that in the case of a finite effective label space, we are able to prove an improved sample complexity of $\tilde{O}(1/\epsilon^2)$. On the other hand, we agree with the reviewer that exploring the possibility of sharpness of the $\tilde{O}(1/\epsilon^3)$ bound in future work would be interesting.

We thank the reviewer for dedicating their time to assess our work. We are delighted that the reviewer found our algorithm novel, and mentioned that our paper is well written.

We would be happy to provide additional clarification on any aspect of the paper that could help inform the review score.