Representation Preserving Multiclass Agnostic to Realizable Reduction
Authors: Steve Hanneke
Qinglin Meng
Amirreza Shaeiri
Venue: ICML 2025 poster (2025)
Keywords: PAC Learning
Agnostic to Realizable Reduction
Unified PAC Framework
Multiclass Learning
List Learning
Multilabel Learning
Noise Models
Partial Concept Classes
Primary area: theory->learning_theory

Abstract: We study the problem of multiclass classification when the number of labels can be unbounded within the PAC learning framework. Our main contribution is a theory that demonstrates a *simple* and *elegant* agnostic to realizable reduction for this framework. This resolves an open problem raised by the recent work of (Hopkins et al., 2022). Notably, our result is the first *representation preserving* multiclass agnostic to realizable reduction, in contrast with the compression based approach of the work of (David et al., 2017). Furthermore, our main theorem is stated in an abstract framework, called ``Unified PAC Learning'', which encompasses a range of frameworks, including multiclass PAC learning, list PAC learning, and multilabel PAC learning. In addition, we explore representation preserving reductions to the realizable setting for two noise models, namely Massart noise and Tsybakov noise, in the multiclass PAC learning framework. We believe our technique may find other applications in ensuing studies of theoretical machine learning.

Representation Preserving Multiclass Agnostic to Realizable Reduction
Steve Hanneke'
Qinglin Meng' Amirreza Shaeiri
Abstract
unified theory that underlies these equivalences? Even more optimistically, could there exist simple and elegant unified theory, both in terms of the analysis and reduction properties, that accounts for these equivalences?
We study the problem of multiclass classification when the number of labels can be unbounded within the PAC learning framework (Valiant, 1984). Our main contribution is a theory that demonstrates a simple and elegant agnostic to realizable reduction for this framework. This re- solves an open problem raised by the recent work of (Hopkins et al., 2022). Notably, our result is the first representation preserving multiclass ag- nostic to realizable reduction, in contrast with the compression based approach of the work of (David et al., 2016). Furthermore, our main the- orem is stated in an abstract framework, called "Unified PAC Learning". which encompasses a range of frameworks, including multiclass PAC learning, list PAC learning, and multilabel PAC learning, In addition, we explore representation preserving reductions to the realizable setting for two noise models, namely Massart noise and Tsy- bakov noise, the multiclass PAC learning frame- work. We believe our technique may find other applications in ensuing studies of theoretical ma- chine learning.
The seminal work of (David et al., 2016) provides a basis for developing a unified theoretical framework. In fact, for almost a decade, their sample compression scheme based ap- proach, which involves boosting, serves the only tool for theorists to prove agnostic learnability in frameworks such as partial PAC learning, multiclass PAC learning, and list PAC learning, where the number of labels can be unbounded in the latter two cases. However, this approach can produce more complex functions than those outputted by a realiz- able learner due to its reliance on the boosting technique, which combines multiple realizable learners. In particular, consider the space of possible outputting functions in the realizable setting. Then, in the agnostic setting, the resulting functions based on this approach do not necessarily belong to that space.
In addition to the mentioned reduction, the recent work of (Hopkins al., 2022) provides an affirmative answer to the aforementioned questions across various frameworks. More specifically, they introduced three-line algorithm accompanied by relatively simple proof technique, which effectively demonstrates the existence of reductions in many frameworks. Moreover, their algorithm uncovers some pre- viously unknown equivalences between realizable and ag- nostic learnability. However, despite these advancements, their approach does not extend to important problems, such multiclass PAC leaning with possibly unbounded label space framework. We suggest readers refer to section 2 for detailed discussion on the significance of this setting. Con- sequently, they posed the following open question: Is there a unifying yet still simple and elegant technique that can also address multiclass PAC learning with possibly infinite label space framework?
1. Introduction
In many frameworks within the field of statistical learning theory, surprising equivalence emerges between realiz- able and agnostic learnability, where both are character- ized by the same quantity despite their inherent difference. This phenomenon encompasses fundamental frameworks, including binary PAC learning, multiclass PAC learning, list PAC learning, binary online learning, and multiclass online learning, among others. Nonetheless, the proof techniques employed to establish the realizable and agnostic results can differ significantly in many of these frameworks. This observation raises an intriguing question: Do we possess
In this work, we provide POSITIVE ANSWER to their open question. Specifically, we demonstrate that clever mod- ification of their three-line algorithm indeed effectively reduces agnostic learnability to realizable learnability in frameworks such as multiclass learning with potentially unbounded label spaces.
'Department of Computer Science, Purdue University, West Lafayette, IN, USA. Correspondence to: Steve Hanneke <steve.hannckeG waw.aannnkkgggllmmmm..mm..... gmai..com>.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
'This is discussed formally in Appendix A.

---

Representation Preserving Multiclass Agnostic to Realizable Reduction
Additionally, our algorithm possesses UNIQUE PROPERTY inherited from the algorithm of (Hopkins et al., 2022). To il- lustrate, consider the space of possible outputting functions in the realizable setting. Our reduction always outputs a function that belongs to that space, which is in sharp con- trast to the approach of (David et al., 2016) as we discussed. Going further, our reduction even preserves data-dependent properties of the output function of the realizable setting, such as the geometric margin used in Support Vector Ma- chines, rather than merely producing a function from the mentioned space. As a result, our work relates to the line of research focused on learning with simple predictors that has gained sigmificant attention in recent years. For instance, the work of (Hanneke et al., 2021) explored this topic in the context of online learning, while (Aden-Ali al., 2024: Bousquet et al., 2020) studied this topic in the context of binary PAC learning. Therefore, our technique provides valuable new tool for theorists to utilize in their problems when required.
1.1. Overview of the Main Result and Technique
In the following subsection, we provide an overview of our main result along with summary of the primary proof technique in our work. Before proceeding, let us informally deñie the Unified PAC Learning framework.
In the Unified PAC Learning framework, we have an in- stance space X. an output space y/ an action space A. and a loss function L A x y + {0, 1}. A predictor is function from X' to A. Moreover, we have set of predictors C' as a concept class. In addition, we have another set of predictors H. as hypothesis class. As result, 6-tuple consisting of X, ), A. L, C, and H specifies an instance of this frame- work. Importantly, both the output space y' and the action space A can be unbounded.
Furthermore, in this framework, learning algorithm maps sequence of instance-output pairs of any size to a predictor. Also, data distribution is defined on X' x V. Based on these, we adopt the definitions of loss for given data distri- bution and predictor, realizable data distribution, realizable PAC learnability, and agnostic PAC learnability within this framework. Importantly, in both the definitions of realizable PAC learnability and agnostic PAC learnability, we require that the image of the learning algorithm be a subset of H. See section 3 for formal notations and definitions.
In fact, we state our main theorem within a new abstract framework, which we call UNIFTED PAC LEARNING. This framework encompasses range of frameworks, multiclass PAC learning (for instance, see the work of (Brukhim al., 2022)), list PAC learning (for instance, see (Charikar & Pab- baraju, 2023)), and multilabel PAC learning. As a result, our finding reveals some new previously unknown equivalences and offers new insights into the relationship between realiz- able and agnostic learnability. We believe that Unified PAC Learning offers a promising avenue for further exploration of realizable learnability in future research.
In this paragraph, we provide a concise explanation of how our framework can be utilized to encompass various settings, illustrated through two examples. For instance, by defining
y as a set of labels and A as {a a S J. |a| I L} for some L E N. L S 13% we can effectively capture the list PAC learning framework of (Charikar & Pabbaraju, 2023). Indeed, A can also be interpreted as set of labels. then by specifying ) as {v y S A. S L) for some L E N, L S [A], it becomes possible to accommodate the multilabel PAC learning framework. It is worth noting that this definition is a special case of the general multilabel setting in practice, which we find particularly interesting as it serves as dual formulation of list learning. For further details, refer to section 4.
Subsequently, we delve into the exploration of NOISE MOD- ELS, which occupy an intermediate position between the realizable and agnostic settings; see (Tsybakov, 2004; Mas- sart & Nédélec, 2006; Agarwal, 2013; Hanneke & Yang, 2015) for more details. In particular, we focus on two very popular noise models, namely Massart noise and Tsybakov noise, for the multiclass PAC learning framework. Using almost the same technique, we demonstrate that focusing on noise models, rather than the agnostic setting, allows for an improvement in the sample complexity.
Now, we informally present our main theorem in the current work.
Finally, we extend our main theorem on the Unified PAC Learning framework to address PARTIAL CONCEPT CLASSES well. We recommend readers refer to the work of (Alon et al., 2022) for a comprehensive discussion on the importance of this setting. While the same algorithm can be applied to partial concept classes, the analysis becomes more involved. Notably, the work of (Hopkins et al., 2022) also addresses this setting; however, they adopt a different definition of agnostic learnability. In contrast, we employ the definition provided in the recent work of (Alon et al., 2022) on partial concept classes, which is more favorable in this context.
Theorem 1.1 (Realizable Unified PAC Learnability Agnostic Unified PAC Learnability). Let Q (X,Y, A, L.C, H) be an instance of the Unified PAC Learn- ing framewoook. If Q is realizable PAC learnable, then Q is agnostic PAC learnable.
The key idea behind the proof of the above theorem is to run the realizable learning algorithm on each subset of samples, followed by applying empirical risk minimization (ERM) on the resulting finite collection of predictors (1). More- over, by applying a concentration bound to this finite set
2

---

Representation Preserving Multiclass Agnostic to Realizable Reduction
of predictors, combined with the error rate guarantee from the realizable PAC learnability for the predictors generated from each subset, we can get the guarantee of agnostic leamability. See section 4 for more details.
setting via combinatorial parameter called the VC dimen- sion. This result was later extended to the agnostic setting by (Haussler, 1992). Since then, PAC learning has been extensively studied in various learning theoretic settings.
As a direct corollary of the above theorem, one can derive a reduction from agnostic PAC learnability to realizable PAC learnability for the multiclass PAC learning framework, as described in subsection 4.2. Additionally, our result reveals new equivalences, including previously unknown equiva- Ience between the realizable multilabel PAC learnability and the agnostic multilabel PAC learnability, as discussed in subsection 4.4.
Multiclass Classification. A large body of theoretical re- search has been devoted to studying multiclass classifica- tion in different frameworks. This includes contributions from (Natarajan & Tadepalli, 1988; Natarajan, 1989; Ben- David et al., 1992; Haussler & Long. 1995; Rubinstein et al., 2006; Daniely et al., 2011; 2012; Daniely & Shalev-Shwand 2014; Brukhim et al., 2021). Nevertheless, the combinato- rial characterization of multiclass classification, when the number of labels can be unbounded, within Valiant's 's PAC learning framework, has remained an open question until recently, even in the realizable setting. The seminal work of (Brukhim et al., 2022) addressed this gap. Furthermore, the same dimension also characterizes the agnostic version of this problem (David et al., 2016). Also, see the recent work of (Hanneke et al., 2023).
Furthermore, building upon the work of (David et al., 2016), we establish another reduction for the Unified PAC Learning framework. While this reduction is more favorable from the sample complexity perspective, crucially, it does not retain properties such as representation preserving. In particular, given an accuracy parameter e E (0, 1), our agnostic result involves a factor of 1/c², compared to the more desirable factor of 1/e² that can be obtained using a sample com- pression scheme based proof. For further details, refer to section& 4 and Appendix C. However, for every n, m E N, give an example of an instance of the Unified PAC Learn- ing framework Q = (X, y, A, L, C, H) such that |X|| n, |) = |A| = |C| = [7| = m where we have: for every 5, E 1). there exists a S2(1/e²) gap between the opti- mal sample complexity of the realizable PAC learning with parameters and and the optimal sample complexity of the agnostic PAC learning with the same parameters. In particular, this example is within multiclass PAC learning framework. Moreover, it builds upon the concept class of the countably infinite collection of constant functions over some domain. For further details, refer to section 6.
There are several reasons motivating this interest in multi- class classification when the number of labels can be un- bounded. First, in multiclass settings, guarantees should ideally not depend on the number of labels, even when fi- nite. Second, mathematical concepts that involve infinity often offer clearer and more elegant insights. Finally, from a practical standpoint, many critical machine learning tasks require classification into very large label spaces. This in- cludes the image object recognition task.
3. Preliminaries
In this section, we introduce the necessary notations and definitions that will be used throughout the remainder of this work.
1.2. Organization
3.1. Notations
The remainder of this paper is structured as follows. In sec- tion 2, we discuss a broader range of related works. Then, in section 3, we present the formal notations and defini- tions. Subsequently, in section 4, we establish our main reduction along with some corollaries. Following this, in section 5, we explore noise models in the multiclass PAC learning framework. Finally, in section 7, we conclude the manuscript.
We begin by introducing some necessary notation before describing and analyzing our algorithm. Fix a non-empty set X' equipped with o-algebra specifying the measurable subsets as an instance space. Fix a non-empty set ) as an output space. Also, fix non-empty set A as an action space. In addition, fix loss function L A x ) - {0, 1}. A predictor is function from X' to A. With this in mind, fix a non-empty set of predictors C as a concept class. Ad- ditionally, fix another set of predictors H. as a hypothesis class. Notably, we implicitly assume standard measura- bility assumptions on C and H. In particular, a 6-tuple @ = (X.Y,A C, C, H) presents an instance of the Uni- fied PAC Learning framework. A learning algorithm A is mapping from (X' x ) to a predictor h. Also, data distribution D is a probability measure on (X' x Y)). Finally, we use (-), o(),, S(--,, w--), and O(-) as standard nota- tions of them in the theoretical computer science. We also
2. Related Work
PAC Learning. The Probably Approximately Correct (PAC) learning framework, introduced by (Valiant, 1984), has been a cornrrsone in the field of statistical learning theory. (Blumer et al., 1989; Vapnik & Chervonenkis, 2015; Valiant, 1984; Vapnik, 2006) characterizes learnable classes within the binary PAC learning framework in the realizable
3

---

Representation Preserving Multiclass Agnostic to Realizable Reduction
use O(), Q()), (()) to exclude logarithmic factors well as constant coefficients.
Algorithm 1 Agnostic to Realizable Reduction
Input: Concept Class C, Hypothesis class H. Realizable PAC-Leamer A, Labeled Sample S.
3.2. Definitions
1: Divide S into two parts V and T.
2: Run A over all subsets of V to get:
Given the above notations, we make the definitions for true risk and empirical risk. For data distribution D and predictor h, define the true risk of h with respect to the data distribution D as follows,
Hy (A(S') 5 CV)
3: Return the hypothesis in Hy with lowest empirical error over T.
(h) =- P ((())))(((((()))))))))))))))))))
Based on this, we say that a data distribution D is realiz- able by a concept class C if there exists c² E C such that (c(c") 0. Similarly, say that a data distribution D is real- izable by hypothesis class H. if inf (h) holds. For simplicity, we will suppose the infimuum infeee Lp(c) is actually achieved by concept c* C.
where c* is the optimal concept in the concept class C. The value MAG (e, 6) is called the sample complexity of A, and the optimal sample complexity is the minimum achievable value of (A 5) for every given c,
4. Reduction
Next, a data set of size m for some m E E is a sub- set of (X' x y) of size m. For such a data S = {(11,31) v1), (12,,3)).... y2),... [mm, and predictor h, define the empirical risk of with respect to the data distribution S as follows,
We present the unified agnostic-to- to-realizable reduction in subsection 4.1. The applications of this reduction will be discussed in subsections 4.2, 4.3, and 4.4.
4.1. General Reduction
Ls(h):- = Σ c(h(a)))
The following theorem demonstrates a representation pre- serving reduction from agnostic to realizable setting within the unified PAC learning framework.
We say a data set is realizable by a predictor h if (h) O. Subsequently, we present the definitions of realizable and agnostic PAC learnability for this framework.
Theorem 4.1 (Agnostic + Realizable ). Let A be an unified realizable learner for learning instance Q .X C, C, H) with sample complexity (RF Then Algorithm I is also an unifted agnostic learner for Q = (, A, C, C, H) with sample complexity: MAG 8) =
Definition 3.1 (Unified PAC Learning). We say that Q = (X,J', A, C, H) is realizable Unified PAC learnable, if
for every 5 E 1), there exists finite E 5) E N and a learning algorithm A with Im(A) S H such that, for every distribution D on (X' x y) realizable w.r.t. C, for S ~ (e,5), with probability at least 1 8,
(RF(cE/2H)) + log
1 F
O 2
max MEL//2.1]
We emphasis that Theorem 4.1 presents the first representa- tion preserving reduction from agnostic to realizable within unified PAC learning regime. Its key application to multi- class learning further highlights the first such reduction in this domain.
Lp(A(S)) c.
The value (e, is called the sample complexity of A, and the optimal sample complexity" is the minimum achievable value of (R 5) for every given e, 6.
Definition 3.2 (Unified Agnostic PAC Learning). We say that @ (x A. C, C, H) is agnostic unified PAC learnable, if for every d (0, 1). there exists fi- nite (c, N and learning algorithm A with Im) C H such that, for every distribution D on (X's x V),, for S (c.,) with probability at least 5, 5,
With this settled, we now proceed to prove Theorem 4.1. The analysis naturally divides into two parts, corresponding to steps 2 and 3 of Algorithm 1, respectively. In the first part, we will show that Hy, the set of output hypothesis corresponding to running the realizable learner over all subsets S' of V. contains a hypothesis ht' which is close to the optimal concept c* in C. More formally, have the following lemma.
LD(A(S)) LD(c')++
Lemma 4.2. For any distribution D over (X x y), with probability at least 1 25/3, there exists h' E Hy which satisfies:
2If not, for any fixed 6 > 0, we can choose e' such that To (c") S infeec Tp(c)) + r/2.
'oor brevity, refer to the optimal sample complexity as sample complexity.
I.D(N') S TT((e)) t/2,

---

Representation Preserving Multiclass Agnostic to Realizable Reduction
where e' is the optimal concept in C.
to draw cMRE (e/ (2p"),6/3) /²" data points to achieve this for some constant > 0. Since we do not know je, we need to draw c emaxpe[e/2a]] (- (M (e)()),, 0/3)/u} data points to ensure this claim holds (if μx" < e/2, note that any hypothesis will give a valid solution). By a union bound, we have that this overall process holds with probability at least 26/3.
Once we prove this lemma, the second part is to show that Step 3, empirical risk minimization process on Hv over labeled sample T, gives the desired agnostic hypothesis. Since Hy is finite, standard Chernoff bound gives that with probability at least 1 - 5/3, the empirical risk (r) of every hypothesis h in Hy is e/4-close to its true risk (D))), as long as sufficiently large. Combining these two parts, Algorithm 1 returns a hypothesis with most Lo(c") + e error rate with high probability.
Proof of Theorem 4.1. By Lemma 4.2, with probability at least 25/3, Hv contains a hypothesis las. such that
LD - T.D(c") + c/2..
It remains to prove Lemma 4.2. The key observation is that the output ASS)) of running A over the subset S* realizable by et is close c".
We can now use standard empirical risk minimization bounds on Hy to find a hypothesis with true risk at most LD(c*) E. A Chernoff and union bounds imply that with probability at least 1 6/3, the empirical risk of every hypothesis in Hy is at most c/4 away from its true risk on a sample of size (log( (a (/)) Since hg- has true risk Lp(hs ) at most (c*) + e/2, its empirical risk Lr (hs-) is at most Lp(c") + 3e/4. Then we can be sure there cxists a hypothesis in Hy with empirical risk at most LD(c") + 3c/4, and by the above guarantee any hypothesis in Hy with empirical risk at most Lo(c") + 3 /4 has true risk at most LD(c*) + E.
Proof of Lemma 4.2. Since the optimal concept c* may not be realizable with respect to distribution D over (X' x ))).
We divide the sample space (Xxx) x)) into two parts according to whether realizable with respect to e" and D. Let (X (x''))) ) denote the realizable part and let D' denote the restriction of D over it. Similarly, let D' denote the restriction of DD over the complement, that is (X' x (2 x 2))" With this in mind, let μ denote the probability mass of D on (X' x y))" Since we are restricting our attention to classification error, we can decompose the true risk of c* over D as:
Combining Lemma 4.2 and the above analysis of empir- ical risk minimization, we have that with probability at least 1 - 5 over the entire process, the output of Algo- rithm 1 is a desired agnostic learner. The sample com- plexity follows from noting that |Hy is at most 2 with ([maxxele2..) (MRE (c/(2)),8/3) due to Lemma 4.2.
LD(c*) = 12' LD (c*) + (1- (1-)")<D-
where the second step is by the decomposition of the sample space (X'))),, and the last step follows from the observation and T-p (c*) = 1 always hold by defini- tion. To get hypothesis within c/2 true risk of LD(c"), ), we claim that it is sufficient to prove Hv contains some h with true risk e/2 over D*, that is some h satisfying:
V
that L. (c")
4.2. Multiclass Learning
Building on Theorem 4.1, we can readily adapt it mul- ticlass Icarning setting with the action space A equal to the infinite label space V, and L represents the classifica- tion error. In this way, unified PAC learning instance Q = V, L, C, H) can be specified as a multiclass learning instance (X,), C, H). Then Theorem 4.1 can be applied to this learning setting, together with Theorem and Algorithm in Brukhim al. (2022) we have the following corollary.
LD- (h) S e/22)")
(2)
This follows from a similar analysis of LD((")) above. We can decompose (h) as:
LD(h) = LD (h) + (1- (h) S e/2 LD(c").
It remains to prove the claim that Hy contains a hypothesis satisfying Equation(2) with high probability. Notice that S* can be seen as drawn from the distribution D=. Then, by the definition of the realizable learning, on the labeled sam- ple S* ~ D of size (MB(ee(2xx)) 6/3), the realizable leamer A will output hg- satisfying:
Corollary 4.3 (Agnostic + Realizable (Multiclass I Learn- ing)). If H has finite DS dimension d, Algorithm I is an agnostic multiclass learner with sample complexity:
MAG(E,)) = -ō( =
-
LD- (hs-) S (2(1"))
e3
with probability at least 1 - 8/3.
4.3. List Learning
Then we just need to draw a large enough sam- ple V to make sure that the size of S* is at least MRE (c/(((())" 5/3). By a Chernoff bound, it is enough
We can also adapt Theorem 4.1 to L-list learning setting with the action space A = (Y C y,|r < L}. The con- cept class C consists of functions c X > A', where
5

---

Representation Preserving Multiclass Agnostic to Realizable Reduction
-'= -Y; 1). Similarly, the hypothesis class H consists of functions h: X - A. By definition, there is bijection between J' and A' mapping each y to a corre- sponding Y such that Y. According to this bijection, the loss function & can be defined on (AA x A') such that ((h(z),c(x)) = if and only if c(x) C ((x). In this way, a unified PAC learning instance Q (xx J A, L, C, H) can H).
X y such that f C and
fly=f(<x))ar max (++1(x)
P - v/1z) > A
(3)
holds almost surely, where I is the Bayes optimal classifier.
Definition 5.2 (Tsybakov Noise). For a E oo) and a E (0, 1), define TN(a, a) as the collection of joint distri- butions Pxy over X' x ) such that f E C and Vy > 0,
be specified as L-list learning instance (V, Thus, Theorem 4.1 can be applied this learning setting, together with Theorem 2 and Algorithm 1 in Charikar & Pabbaraju (2023), we have the following corollary.
Px (a: (
P(y = >/11=))) mT) (+
max
I <d)a/(1-a)
Corollary 4.4 (Agnostic - Realizable (L-List Learning)). H. has finite L-DS dimension d, Algorithm 1 is an agnostic list learner with sample complexity:
(4)
where d' (1 -1-ol -)220)/((- /2/11/ and f is the Bayes optimal classifier.
(c, = L_ + 118)
The following theorem shows the reduction from Massart noise to realizable.
e3
Theorem 5.3 Realzableel (Multiclass Learning)). If has finite DS dimension d, Algorithm 1 is an agnostic multiclass learner with sample complexity
+
4.4. Multilabel Learning
With Theorem 4.1 in mind, we can also adapt it to multi- label learning setting where the action space is defined as A (Y S y/ | S L]. The concept class C consists of functions c: X' + A. Similarly, the hypothesis class H consists of functions h : X' + A', where A'' = (Y S y, |Y| = 13. By definition, there is a bijection between V and A' mapping each y to a corresponding Y such that y E Y. According to this bijection, the loss function L can
MaNNaa((E = -ō d +logoog1/101 100(1/00)
Ae2
Before providing the proof of Theorem 5.3, we state useful lemma that will be used in the proof.
Lemma 5.4. For any distribution D over X' x D, with probability at least 1 5, we have:
be defined on (A x A') such that L(c(z), h(x)) = 0 if and only if h((x) C c(x). In this way. unified PAC learning instance Q (X, A, A, C, H) can be specified as a mul- tilabel learning instance (X,Y, A, C, H), and thus, we can apply Theorem 4.1 to this learning setting.
TD((h) T.D(')) - e/2 S log( Hv 1/8)/T| + +c & (x)) + 2 log (1vv
where Hy is the hypothesis class generated in step 2 of Algorithm 1, and h is the hypothesis output by ERM in step of Algorithm 1, and c* E C the Bayes optimal classifier. and is some positive constant.
5. Noise Models
In this section, we provide the sample complexity of our mul- ticlass classification reduction algorithm under two noise models: Massart Noise (Massart & Nédélec, 2006) and Tsybakov noise (Tsybakov, 2004). We use MD(e, 5) to denote the agnostic sample complexity constrained by the distribution D E D. Since multiclass learnability can be characterized by DS dimension d, which means hypothe- sis class H. is PAC learnable if and only if it has finite DS dimension, we restricted our reduction on the hypothesis classes with finite DS dimension. For the realizable learner A, we use the one- incinncusionn graph algorithm introduced by Brukhim et al. (2022).
Proof of Lemma 5.4. By uniform Bernstein inequality, for all h, h' E Hv, and distribution D over (X x })), with probability at least 1 - 5/3 we have:
LD(h) LD(h') s log( Hy 1/5)
T
log( (/vv
V P(h(x) # M((), E (Mx),
(x))))
[7]
(5)
For h, hs- E H and c* eC, we have the following inequal- ity:
Before present our result, we first give the definition of these two noise models.
P(hs- & ((x) e (z)))
Definition 5.1 (Massart Noise), For A E (0,1). define MN(A) as the collection of joint distributions Pxy over
< P(h(a) (c) (x))),
(6)
+ P(hs-(x) $ c² (x). (z))
6

---

Representation Preserving Multiclass Agnostic to Realizable Reduction
We can furthur upper bound (x) + cxxx),y y E (his (a); c² (x))) by c/2 due to the construction of hi. in Lemma 4.2. Then combining Equation (5), Equation (6)
with probability least 1 8, we have
T.D(h) - IDD(c") e/2 - log( My 1/6)
and Lemma 4.2, we can get the desired conclusion.
(T)
+ +c (a(Lo(i) - LD(Ct)) + +//2)
log( log(
With the above lemma in mind, we start the proof of Theo- rem 5.3.
[T]
(11)
where c is some positive constant. For [
>
Proof of Theorem 5.3. For all distribution D E MN(A) and h E &y², with probability 1, we have
e" (og((Hvl/0)//20 with probability at least 1 Equa- tion (11) holds with Lp(h) Lp((")) S e, where c" is some positive constant. In this way, we have that the output of Algorithm is a desired learner under Tsybakov noise. The sample complexity follows from noting that [Hv] is at most 2 with |V| O (maxpple/22.1) (M (eeee222)//)////// due to Lemma 4.2.
(h - LD(C") 2 AP(h(z) + cz)))))
(7)
Combining Lemma 5.4 and Equation (7), with probability at least 1 - 6, we have
lh(h) LD(C') - 5/25 log((Hvl/0)
(T]
6. Lower Bound
(8)
+ +g ((Lo())-b(cc)) + t\/2
log( My 1/8)
In this section, we demonstrate that although our sample complexity upper bound includes an additional 1/c term compared to the upper bound obtained via compression scheme, this extra factor is sometimes unavoidable due to the
(T)
where c is some positive constant. Transferring Equation (8) such that the term [h) (D(e") only appears in the left side of the inequality, with probability at least 1 6, we have
property maintained by our algorithm. Formally, we state the following theorem:
Theorem 6.1. For every n, m E N, there exist an example
Lo(h)- s <e' log( Hv //8)
of an instance of the Unified PAC Learning framework Q =
T
2'
(X. A, L. C, H) such that |X| = n, | = | = |C| =
[7] = m for which we have:
where e' is some positive constant. Further upper bound Equation (9) with and solve for [T), we have when (T] 2 (ooog(/v///0//A with probability at least 1 5, the output of Algorithm 1 is a desired learner un- der Massart noise. The sample complexity follows from noting that [Hvl is at most 2 with [V] = (mmaxpeje/22)) 4.2.
MRE
V (0,1), MAG((, E @((1/22)
where M (C and M M 8) are optimal sample com- plexity of the realizuble PAC learning and the agnostic PAC learning, accordingly.
(/33///)) due to Lemma
Proof. Let X (1.2....,m) .n.. Also, let y A (1.2....,,m) m). In addition, let C H ===a0 (cg Icy X' + (v).y E 2). Additionally, define L as the multi- class classification loss 4.2. Now, observe that Q is realiz- able PAC learnable with only one sample. Therefore, we have: Ve, E (0,1), MM RE (c,6) E O()). Also, we have: Ve,ō E (0, 1), MAG d) E 2(1/²). This follows from the standard technique based on the slightly unbiased coin; for instance, see (Daniely et al., 2011). As a result, we have: Ve, 8 (0. MRE ( (c, E ((1/c2). We note that it is possible to construct similar example using partial concept classes B. This finishes the proof.
The following theorem shows the reduction from Tsybakov noise to realizable.
Theorem 5.5 (Tsybakov - Realizable (Multiclass Learn- ing)). H has finite DS dimension d, Algorithm I is an agnostic multiclass learner with sample complexity:
(I,(G,o)(e.0) -6((0)
(6
(aa(d/2/ log((18))
3-a
proof of Theorem 5.5. For all distribution D TN(a,a) and h E xxx, we have
Remark 6.2. Indeed, it is preferable to provide an exam- ple of an instance of the Unified PAC Learning framework where the aforementioned result holds true but we also have an ((1/e) c) lower bound on the optimal sample complexity of the realizable PAC learning for every e, E (0, 1) as the
P(h(x) # c (x)) s (hL LD(C")), (10)
which also refers to Bernstein class condition (Hanneke &
Yang, 2015). Combining Lemma 5.4 and Equation (10),
7

---

Representation Preserving Multiclass Agnostic to Realizable Reduction
parameters. However, this claim holds if and only if there is sublinear proper sample compression scheme for given hypothesis class, which is an interesting and important topic to explore. Actually, if we have proper sample compres- sion scheme of size k(n) = O (n//3/ llg n), then we can get an agnostic proper sample compression scheme with the same size kn)). An agnostic proper sample compression scheme of size (()) implies proper agnostic learner with error rate
(1 k(n) log λंnj + k(n) + log?
e(n, 0) -
In other words, the sample complexity of this agnostic learner would be MMA((E, O(1/e),, which matches the sample complexity upper bound of algorithm. How- even in the binary case, the existence of such proper sample compression scheme remains unproven. We leave this as an open question for further exploration.
7. Conclusion
In this work, we established simple and elegant agnostic realizable reduction within the Unified PAC Learning framework. In particular, our result leads to the first repre- sentation preserving agnostic to realizable reduction within the multiclass PAC learning framework, especially when the number of labels can be unbound. Also, we explored representation preserving reductions in the realizable setting for two noise models the multiclass PAC learning frame- work. In addition, showed similar results for the Unified PAC Learning framework with partial concept classes. We believe that our techniques could have applications in future studies in the field of statistical learning theory.
Impact Statement
This paper presents work whose goal advance the field of Statistical Learning Theory. There many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
8

---

Representation Preserving Multiclass Agnostic to Realizable Reduction
References
David, O., Moran, S., and Yehudayoff, A. Supervised learn- ing through the lens of compression. Advances in Neural Information Processing Systems, 29, 2016.
Aden-Ali, I., Hoandgsgaard, M. M., Larsen, K. G., and Zhivotovskiy, N. Majority-of-thene -fethe The simplest optimal learner? In The Thirty Seventh Annual Conference on Learning Theory, pp. 22-45. PMLR, 2024.
Hanneke, S. and Yang, L. Minimax analysis of active learn- ing, J. Mach. Learn. Res., 16(1):3477-302,, 2015.
Agarwal, A. Selective sampling algorithms for cost- sensitive multiclass prediction. In International Con- ference on Machine Learning, pp. 1220-1228. PMLR, 2013.
Hanneke, S., Livni, R., and Moran, S. Online learning with simple predictors and a combinatorial characterization of minimax in 0/1 games. In Conference on Learning Theory, pp. 2289-2314. PMLR, 2021.
Alon, N., Hanneke, S., Holzman, R., and Moran, S. A theory of pac learnability of partial concept classes. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 658-671. IEEE, 2022.
Hanneke, S., Moran, S., and Zhang, Q. Universal rates for multiclass learning. In The Thirty Sixth Anmual Confer- ence on Learning Theory, pp. 5615-5681. PMLR, 2023.
Haussler, D. Decision theoretic generalizations of the pac model for neural net and other learning applications. In- formation and computation, 100(1):78- 1992.
Ben-David, S., Cesa-Bianchi N., and Long, P. M. Charac- terizations of learnability for classes of (O...., -vvauud functions. In Proceedings of the fifth annual workshop on Computational learning theory, pp. 333-340, 1992.
Haussler, D. and Long, P. M. A generalization of sauer's lemma. Journal of Combinatorial Theory, Series A, 71 (2):219-240, 1995.
Blumer, A., Ehrenfeucht, A., Haussler, D., and Warmuth, M. K. Learnability and the vapnik-chervonenkis dimen- sion. Journal of the ACM (JACM), (0664)):999-655) 1989.
Hopkins, M. Kane, D. M., Lovett, S., and Mahajan, G. Realizable learning is all you need. In Conference Learning Theory, pp. 3015-3069. PMLR, 2022.
Bousquet, O., Hanneke, S., Moran, S., and Zhivotovskiy, N. Proper learning, helly number, and an optimal svm bound. In Conference on Learning Theory, pp. 582-609. PMLR, 2020.
Massart, and Nédélec, A. Risk bounds for statistical learning, Annals of statistics, 34(5):3326-2366, 2006.
Brukhim, N., Hazan, E., Moran, S., Mukherjee, I., and Schapire, R. E. Multiclass boosting and the cost of weak learning. Advances in Neural Information Processing Systems, 34:3057-3067, 2021.
Natarajan, B. K. On learning sets and functions. Machine Learning, 4:67-97, 6667-97,111 1989.
Natarajan, B. K. and Tadepalli, P. Two new frameworks for learning. In Machine Learning Proceedings 1988, pp. 402-415. Flsevier, 1988.
Brukhim, N., Carmon, D., Dinur, I., Moran, S., and Yehu- dayoff, A. A characterization of multiclass learnability. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 943-955. IEEE, 2022.
Rubinstein, B., Bartlett, P., and Rubinstein, J. Shifting, one- inclusion mistake bounds and tight multiclass expected risk bounds. Advances in Neural Information Processing Systems, 19, 2006.
Charikar, M. and Pabbaraju, C. A characterization of list learnability. In Proceedings of the 55th Annual ACM Symposium Theory of Computing, pp. 1713-1726, 2023.
Tsybakov, A. B. Optimal aggregation of classifiers in sta- tistical learning. The Annals of Statistics, 32(1):135-166 2004.
Daniely, A. and Shalev-Shwartz, S. Optimal learners for multiclass problems. In Conference on Learning Theory, pp. 287-316. PMLR, 2014.
Valiant, L. G. A theory of the learnable. Communications of the ACM, 27(1 27(11):1134-142) 1984.
Daniely, A., Sabato, S., Ben-David, S., and Shalev-Shwartz S. Multiclass learnability and the erm principle. Pro- ceedings of the 24th Annual Conference on Learning Theory, pp. 207-232. JMLR Workshop and Conference Proceedings, 2011.
Vapnik, V. Estimation of dependences based on empirical data. Springer Science & Business Media, 2006.
Vapnik, V. N. and Chervonenkis, A. Y. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity: festschrift for alexey chervonenkis, pp. 11-30. Springer, 2015.
Daniely, A., Sabato, S., and Shwartz, S. Multiclass learning approaches: A theoretical comparison with implications. Advances in Neural Information Processing Systems, 25, 2012.
9

---

Representation Preserving Multiclass Agnostic to Realizable Reduction
A. Failure of Hopkins et al. (2022) in Infinite-Labe Multiclass Learning
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 X' [0, 1]. denote by F(X) the collection of all finite subsets A S X.
Let the label space y F(X) U{*), where * is a special label (not to be confused with "*" from the partial concept
classes section). For every A S X, define fa : X + 3' as follows:
fa(2) = + if
otherwise.
Let the concept and hypothesis class be C (fa AE U.) 2}. Then, there is realizable learner Agood that returns fx unless a label A E F(X) appeared in the sample, in which case it returns fA. Let D have marginal on X' the uniform distribution over Xt and let the labels be always (i.e., realizable with target fx). Now, consider the algorithm of Hopkins et al. with this scenario and realizable learner Agood- Let the unlabeled dataset be Sy = { {2, , .nn), and the labeled dataset be S2 = ((In=1, *), (2 *), *),... (In+m, and with probability one these x's are all distinct. Denote A = {In+1: 1, 2 ... [n+m] ( Then their algorithm would run Agood on all realizable labelings of Sy: in particular, one of these (Se. (Su)) { A)..... (In, A]}, and the output hypothesis of (So fa(Se) )) would be fA- By the definition of fA. know that the empirical error of fA on St is O. Their algorithm then outputs any ERM on Sy from these functions produced by Aguod, which means their algorithm can output fA. However, the true error rate of fA is 1, while the best error in the concept class is O. Thus, their algorithm fails for this concept class (for essentially the same reason ERM fails for this concept class). In contrast, our algorithm returns fx, hence achieves error O.
B. Partial Concept Classes
We discuss the reduction for partial PAC learning in this section.
B.1. Notations
We first develop some necessary notation for partial PAC learning. partial predictor is a function from to A UUA (*). With this in mind, fix a non-empty set of partial predictors C as a concept class. Additionaly, fix another set of predictors H. hypothesis class. The support of partial predictor h is the set supp(h) h (-A). A loss function L is map
C: AU (+) x y - (0. 1), with [(x,)) -) = 0. Similar to unified PAC learning, a 6-tuple Q presents an instance of Unified Partial PAC Learning framework. A learning algorithm A is mapping from (X' x )) a partial predictor h.
Given the above notations, we make the following definitions for realizability. A probability distribution, D, over the product space of instance space and label space (X' x y). is realizable by a partial concept class C. if almost surely (i.e., with probability 1), a sample S = ((zi, v;)) ~ D (for any n E N) is realizable by some partial concept c E C: that is {o C supp(c) and [(c(z,). = 0 for all S n. For a partial concept c and a distribution D on X' x V, we define the true risk: (c) == ( (C(((x), y)]. true risk of a hypothesis can also be defined as (((h)))))(((()),....)))()))))>)) LD (h) := ((,,)))Dl ([(((x),, w)]. Given the above notation and definition, we define Unified Partial PAC learning, which can be easily adapted to a specific learning regime.
Definition B.1 (Unified Partial PAC Learning). We say that Q = A, H) is unified partial PAC learnable, if for every , E (0, 1). there exists a finite MR 5) E N and a learning algorithm A with Im(A) S H such that, for every distribution D on X' x y' realizable w.n.t. C, for S ~ (M. (c.8), with probability at least 1 5- 5.
Lo(A(S)) S.
The value (c, is called the sample complexity of A, and the optimal sample complexity* is the minimum achievable value of MRE (E, ô) for every given e, 8.
For any n E N and data sequence S E (X x 2)n, define the empirical risk of any partial concept e as Ls(c) 1 " En [(((z)), vt). For a distribution D on X Y. define the approximation error of C as LD(C)
lim Eg-Di (mincec Ls(c)).
*For brevity, we refer to the optimal sample complexity as sample complexity.
10

---

Representation Preserving Multiclass Agnostic to Realizable Reduction
Definition B.2 (Unified Agnostic Partial PAC Learning). We say that PAC learnable, if for every 6, (0, 1), there exists finite MAG (c,6) E N and learning algorithm A with Im(A) H such that, for every distribution D on x V. for DM (c,6), with probability at least
(X, L,,, H) is agnostic unified partial
Lp(A(S)) & LD(C)+C +
The value MAG 6) is called the sample complexity of A, and the optimal sample complexity is the minimum achievable value of MAG (e, 6) for every given e,
B.2. General Reduction
Given the definition above, we provide the unified partial agnostic to realizable reduction in the following theorem.
Theorem B.3 (Agnostic + RRealizable (Partial Learning) ). Let A be realizable unified partial learner for learning instance Q = (X, A. C, H) with sample complexity (R Then Algorithm I is an agnostic unified partial learner for (X A. L, C, H) with sample complexity:
MMR (c/22.66))) log(1/6)
max maxpel(/2.1)
(E, O
Theorem B.3 is also the first representation preserving reduction within unified partial PAC learning regime. However, compared to a max (M/ (c/2p, 5/3)/m} term, which can scale 1/c. This raises an open question:
technique of David et al. (2016), Theorem B.3 incurs an extra
Although Theorem B.3 achieves the same sample complexity as Theorem 4.1, the proofs differ significantly, there is optimal concept c* in C under the framework of agnostic partial PAC learning. Before presenting the proof, introduce the following notations. Let h be the output hypothesis in step 3 of Algorithm 1. For a given sample T, let c² = arg min (c). According to ct, let S* C S be the largest realizable sample set in S, i.c. S { v) E () (x) = v)}. Also, let hg. = ASS).. With these notations in mind, we we now present the proof of Theorem B.3.
Proof of Theorem B.3. Leveraging a standard Chernoff bound over Hss for any E Hs. with probability at least - 6/4. we have
LD(h)= I Lr(h) ci Hoc//oo((Hs///)/11))
for some positive constant c₁. Specially, for the output hypothesis h in step of Algorithm 1, with probability at least 1 - 8/4, we have
(h) S (h((h)
(og(Hss/0))/1)
By the construction of h, we have (h) s (h) for all h E Hs. Since hs- Hss have Lr(h) S L1 (hs-), ), which futhur leads to
(h(h)= < Lr(hs:) ci c log( |//////
(12)
holds with probability at least - 8/4. On the other hand, since function Lr(h) is bounded noise with constant bound 1/[r], leveraging McDiarmid's incquality, with probability at least 1 8/4, we have
(r(c") < ([Lr(c")] e
for some postive constant C.. Since [c") is non decreasing in the size of sample T, (see Lemma 39 in Alon et al. (2022)) we have LE (c+)] < (C) for any T sampled from distribution D. Thus, with probability at least 6/4, we have
Lr(c*) S LD(C) + 62 (10)
(13)
for some positive constant (2. we can further bound the difference LT - with high probability, combining Equation (12) and (13), we can get the desired conclusion. natural idea to divide T into two parts: T the realizable part according to c², and T", the complementary of T Then, we can decompose Lr(c*) as
Lr((')= = 1¹ ..r (c)) + (1 p² TTp = =1-p"
(14)

---

Representation Preserving Multiclass Agnostic to Realizable Reduction
where 1/|o| denote the portion of realizable samples of ct in T. Similarly, we can decompose Ly (hg-) as
(1s-) = μ LT- (hs-) - - L1- (bs-)
f 11 - μ¹ + pt" (hs-)
(15)
LT(c*) + p LT- (hg=),
where the inequality comes from L7- (hg.) ) < 1, and the last equality is due to Equation (14). Since both S and T are realizable by c², as long as | M (e 22" 6/4), with probability at least - 5/4, we have LT- (h - e/2. Leveraging a standard Chernoff bound, when |S] = <3 max maxx/e|//211 ( (c/21t 8/4)/u), with probability at least - 6/4, we have | 2 MM (c/2ppp 5/4).
Choosing T = (Holg(HHs//5))
by a union bound across the whole process, we
have, with probability least 6,
Lh(h) S LD(C) +.
In this way, we prove Algorithm is an agnostic partial unified leaner. The sample complexity comes from [Hss = 2 with [S] = C3 max,ma//2.1)..e ( (c 8/4)/u} ) for some positive constant C3-
B.3. Multiclass Learning
With Theorem B.3 in mind, we can readily adapt it to multiclass learning setting with the action space A = (*). and L represents the classification error. In this way, a unified PAC learning instance Q (X.V, A, L, C, H) can be specified as a multiclass learning instance (X, C, H).
Corollary B.4 (Agnostic - Realizable (Partial Multiclass Learning)). Let be a realizable partial multiclass learner for learning instance (X,Y.C C, H) with sample complexity (E, Then Algorithm I an agnostic partial multiclass learner for (X,YC, H) with sample complexity:
[MRR (c/2g.6/)) + log(1/6)
maxpeel/2.11
Moreover, H has finite DS dimension d, Algorithm only needs:
(e, 0 /d%/2+log(1//
log
c3
labeled samples.
B.4. List Learning
Building on Theorem B.3, We can adapt L-list learning setting with the action space A (Y V. Y L}. The
concept class C consists of functions X A'U (*), where A' (Y C V = Similarly, the hypothesis class H consists of functions h X' + AU BB definition, there is bijection between y and AA' mapping each to corresponding Y such that y E Y. According to this bijection, the loss function L can be defined on (A U (x) x A'U
such that [(h(z), c(z)) = if and only if c(x) C h(x). In this way, unified PAC learning instance Q A, can be specified as a L-list learning instance (X', A,
Corollary B.5 (Agnostic > Realizable (Partial List Learning)). Let A be a realizable partial list learner for a learning instance (x A,A,C H) with sample complexity (RE(e, Then Algorithm is an agnostic partial list learner for (X.Y, A. C, H.) with sample complexity:
max max,ue(e/21]] ( [MRE (c/2u.83)) log(1/8)
MAG -
(c.
Moreover, H has finite L,DS dimension d, Algorithum I needs only:
MAG 8) 0 L L,,33/2 (og(1/0)
3
labeled samples.
12

---

Representation Preserving Multiclass Agnostic to Realizable Reduction
B.5. Multilabel Learning
We can also adapt Theorem B.3 to multilabel learning setting where the action space is defined A (Y CV. L) The concept class C consists of functions X' A. Similarly, the hypothesis class H. consists of functions h h A', 1). By definition, there is bijection between Y and A'' mapping each Y such that E Y. According to this bijection, the loss function L can be defined on (A (+) A' U {+}) such that [(c(x), ) = 0 if and only if h(x) C c(x).. In this way, a unified PAC learning instance @ = (K,,,, L, C, H) can be specified as a multilabel learning instance (X, V, A,C,H,,
where A' {Y C C.
corresponding
Corollary B.6 (Agnostic -> Realizable (Partial Multilabel Learning)). Let A be realizable partial multilabel learner for M, C, H) with sample complexity (E, Then Algorithm I is an agnostic partial multilabel learner for (X. V. H) with sample complexity:
MRE (e/21.8/3) + log(1/0)
maxx/e/e/211
MAG
1
C. Reduction via Compression Scheme
For completeness, state the sample complexity of reduction via compression method in this section.
The following theorem presents the sample complexity of the agnostic to realizable reduction achieved through a compression scheme.
Theorem C.1 (Agnostic-> Realizable (Compression)). IfC is unified PAC learnable with sample complexity (R (), then it is unified agnostic PAC learnable with sample complexity:
(A, - - M ( log (1/c) (oge)//o/(1///////// log(1/))
2
Proof of Theorem C.I. The proof follows directly from Theorem 3.1 and Theorem 3.2 in David al. (2016).
The following theorem presents the sample complexity of the Massart noise to realizable reduction achieved through compression scheme.
Theorem C.2 (Massart-> Realizable (Compression)). If a multiclass concept class is learnable with sample complexity MR (e, 8), then also learnable under Massart noise with sample complexity:
(M ME (M (1/3, 1/3) log2 (0/) log(1/6)
MaaNca)(e,8)-
Proof of Theorem C.2. According to Theorem 3.2 in David et al. (2016), have: If C can be learned with sample complexity RE
(c, 8), there is sample compression scheme of size k(m) O log(m) log(do log(m))) where 1/3). Furthermore, a sample compression scheme of size k(m) implies an agnostic sample compression scheme of size k(m). Denote this sample compression scheme by ASS), where S is the sample with size |S] = m. Due to the upper bound on the size comparison scheme is k(m), the size the class compression functions [Hel can be upper bounded by
du = MRR (1/3, (1/3,
k(m)
Σ
(((m))
k(m))
(16)
k((m)
Then universal Bernstein inequality gives that: for all de E He. with probability at least 6, have
(h))()) - - - LD(c)))
log( log((H)e1/8)
log( (og())))//))
(17)
s <cy Po ( (c((), (h(x),
|S]
[
13

---

Representation Preserving Multiclass Agnostic to Realizable Reduction
where c* is the Bayesian optimal classifier in C. Specially, for the agnostic compression scheme (()), with probability
least. 1 5, have
log Log(HH./0)
log [o (o
(D(A(S))- - ID(e)) s
( (A(S))), / PD (A(())()) # (x).
+
(18)
[|]
[S]
due to the definition of agnostic compression scheme. Combining Equation (18) and Equation (7), probability least
1 8, we have
LD(A(S)) LD(c") s v [ log( log((Hol/5) Hcl/5)
log((Hel1
- LD(ct))
+
(19)
|S|
S
Combining Equation (19) and Equation (16) and solve, we have LD(A(S)) - LD(( s,
|S| = o MRE ( (133, log (A/e) log(1/6)
A
In this way, prove that the compression scheme is learner under Massart noise and also prove the upper bound on sample complexity.
The following theorem presents the sample complexity of the Tsybakov noise to realizable reduction achieved through compression scheme.
Theorem C.3 (Tsybakov-+ Realizable (Compression)). If a multiclass concept class C is learnable with sample complexity MRE (e, 8), then it is also learnable under Tsybakov noise with sample complexity:
MTN(a.0) (c. = - [a(MBB(1/3) ( 1/3) log (1/e) + log
2-
Proof of Theorem C.3. The proof closely mirrors the argument Theorem C.2, with the key difference being the substitution of the Massart noise condition (i.e. Equation (7)) by the Tsybakov noise condition (i.e. Equation (10)) in Equation (19).
D. Concentration Inequalities
In this section, we list the concentration inequalities used in our paper without providing proofs. Theorem D.1 (Generic Chernoff Bound). For random variable X, and positive number and any we have
P(X S M(t) exp(-ta).
where M() = [[exp(LX)) is the moment generating function of X.
Theorem D.2 (Uniform Bernstein Inequality). For all h h E H and distribution D over x Y, with probability at least 1 8, we have
(Ls(t))-ss(h') - (hD L LD(h))
Po(h(*) S ( + (((), e ((()), log(1H1/8)
+ log( (4/8)
S
(S]
where H. is a multiclass hypothesis class, and is some positive constant.
Theorem D.3 (McDiarmid's Inequality). Let f X x X2 x ... x Xn -> TR satisfy the bounded differences property with bounds C12 o2,..., Cr. Consider independent random variables X1, X2...., Xn where X; E X, for all Then, for any
0,
26
P(f(X1,Xp X2,..., X.) -E[S(X, X2, Xe..... X.)) 2 6) S exp
Σ1
G
-2c
X( -E[f(X, X2, X,))
Xx)) < < exp
Σ o
14


Reviews:
[{"review_id": "tD60yFpGiY", "reviewer": "Reviewer_rut2", "summary": "This paper studies the PAC learning of the problem of multiclass classification with unbounded numbers of labels. The primary contribution is a novel reduction from the agnostic learning setting to the realizable setting that preserves the structure of the output space, which resolves an open problem posed by Hopkins et al., 2022. The authors introduced \"unified PAC learning\" which encompasses multiclass, list, ad multilabel PAC learning. Additionally, they explores reductions under Massart and Tsybakov noise and extend their results to partial concept class.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nWe would be happy to provide additional clarification on any aspect of the paper that could help inform the review score.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "It's very related.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "The paper is well written. The mathematical development is clear and concise.", "other_comments_or_suggestions": "No.", "questions_for_authors": "No.", "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": "FJ9IM76J3f", "reviewer": "Reviewer_N7MP", "summary": "The authors study agnostic learning with black-box realizable learners, extending the work of Hopkins et al. (2022). \nThey adapt the simple reduction from Hopkins et al. in a very general PAC learning setting (encompassing list learning and many more). They prove that their reduction algorithm achieves a sample complexity of roughly $\\frac{\\text{realizableAlgo}(\\epsilon,\\delta) + \\log(1\\delta) }{\\epsilon^2}$. They prove that the $1/\\epsilon^2$ is in general unavoidable.\nTheir algorithm resolves the open problem of Hopkins et al., of providing such a back box reduction for the multi-class case with infinite labels. \nFurthermore, they also study particular noise settings.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**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. \n 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.\n\n**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:\n$$\nf_{A}(x) = \\begin{cases}\n\t\t      \\star & \\text{if } x\\in A \\\\\\\\\n              A & \\text{otherwise}.\n\t\t   \\end{cases}\n$$\nLet 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.\n\n**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.).\n\n**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.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "N/A.", "theoretical_claims": "Proofs are mostly standard and correct.", "experimental_designs_or_analyses": "N/A.", "relation_to_broader_scientific_literature": "Some clearer distinction with Hopkins et al. (2022) would be nice. See below.", "essential_references_not_discussed": "All good.", "other_strengths_and_weaknesses": "The paper is nice, continues an important line of work, and should be interesting for the theoretical ICML community. It is somewhat incremental and the new achievements compared to Hopkins et al. (2022) are not fully clear. Please, see questions below.\n\nSome more discussion with other recent attempts combining learners to achieve optimal learners would be nice. The cited Aden-Ali et al paper and others. While not necessarily related to agnostic learning, the general theme of trying to combine basic learners in a simple way seems is quite common nowadays (in contrast with boosting, sample compression, one-inclusion graph-based, etc. techniques).", "other_comments_or_suggestions": "Please check your usage of \\citep vs \\citet. E..g, use \"work of Hopkins et al. (2022)\"  instead of \"work of (Hopkins et al, 2022)\".\n\nTypos:\n* \"an unified\" --> \"a unified\"\n* \" (Agnostic → Realizable ).\" remove space after realizable\n* Inconsistent \"class vs Class\" in \"Concept Class C, Hypothesis class H\" in Algorithm 1.", "questions_for_authors": "There seems to be a significant difference to Hopkins et al (2022). Note how the reduction calls the algorithm $A(\\cdot)$ with potentially non-realizable subsamples. Standard realizable algorithms cannot necessarily handle these. E.g., the Perceptron algorithm might not even stop when run on a non-realizable sample. In some sense you are assuming that the realizable algorithm can detect that the sample is not realizable and then just returns some default hypothesis. Please make this distinction clearer in the next version. Or is there an easy fix? E.g., in Hopkins et al (2022) an unlabeled sample is used an labeled only with hypotheses, hence realizability is guaranteed. \n\nIt is not really clear from the paper if the new results (e.g., reduction for the $|Y|=\\infty$ case) require the adapted blackbox reduction or if an new analysis of the original algorithm of Hopkins et al. (2022) would suffice. Please clarify. Are the changes necessary? \n\nAlso, Theorem 2.2 states that their reduction needs overall $1/\\epsilon^2$ samples for VC classes (instead of the worst-case $1/\\epsilon^3$). Is this also possible here? Corollary 4.3 here says that the new reduction requires $1/\\epsilon^3$ overall at least for the DS dimension case. What about finite or binary $Y$?\n\nThe tightness proof is not very satisfactory. It only holds for the $O(1)$ vs $1/\\epsilon^2$ case. In particular it is not shown that an $1/\\epsilon^3$ can ever be required for this reduction (in some natural case like multi-class, preferably with finite labels).", "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": "zzwOTqYMMi", "reviewer": "Reviewer_eCfp", "summary": "The paper studies a representation preserving agnostic to realizable reduction. The reduction can nicely be described as, splitting the training data into two parts $V$ and $T$. Now on the first part of the training data $V$ the learner runs on all subsets the realizable learning algorithm, getting $ 2^{|V|} $ my outputs of the realizable learning algorithm. Now using $ T $ as a validation set the learner picks the best of the $ 2^{|V|} $ hypotheses, created in the first step of the process. The proof follows from a high level from first considering $V$ samples from a mixture of a distribution realizable/labelled by the best reference hypothesis $ c^* $ and a part not realizable by $c^*$. Since the first step runs the realizable algorithm on all subsets, it especially runs on the largest subset $ S' $ of $ S $ that is labelled by $ c^*.$ Thus on this subset the realizable learner gets a good preformance on the part of the distribution labelled by $ c^* $  and since the agnostic algorithm has to compete with $ c^* $ and it fails on the other part of the distribution, the output of the realizable learner is close to the preformance of $ c^* $ on the true distribution. Now to ensure that the output of the realizable learner on the distribution realizable by $ c^* $ is small, the paper makes sure that $ |V| $ is large enough such that the largest subset $ S' $ of $ S $ label by $ c^* $ contains sufficently many examples to get small error under the part of the true distribution realizable by $c^*$.     The next step is to extract this good hypothesis from the $ 2^{|V|},$ hypothesis created in the first step of the algorithm. By Chernoff and a union bound over the $ 2^{|V|} $  hypothesis, the true risk is close to the empirical risk for all the $ 2^{|V|} $ hypotheses and the hypothesis with the smallest empirical risk can be chosen as the final classifier. The above algorithm is related to that presented in Hopkins et al. 2022, but can handle infinite labelspaces as with for instance multiclass classification, which was left as an open problem in Hopkins et al. 2022. Furthermore the framework also works for list learning and multilabel PAC learning (again with infinite labels). Furthermore, the paper shows that the sample complexity of the framework is better when considering the multiclass classification problem (with infinite labels) with Tsybakov and Massart Noise.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**1. Other comments or suggestions:**\n\n* It is $\\epsilon/(2 \\mu^*)$.\n* There should be a $\\epsilon/2$ on the right-hand side of equation 9.\n\n\n**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).", "claims_and_evidence": "Most of the proofs of the claims are in the main, and to the best of my knowledge, these are sound. I did not check the proofs in the appendix.", "methods_and_evaluation_criteria": "No experiments are included in the paper, so I did not know how to evaluate this question.", "theoretical_claims": "I checked the proofs in the main and to the best of my knowledge they are sound. I did not check the proofs in the appendix.", "experimental_designs_or_analyses": "No experiments are included in the paper, so I did not know how to evaluate this question.", "relation_to_broader_scientific_literature": "The paper presents related work, where the most related is the work by David et al. 2016 and Hopkins et al. 2022. They solve an open problem stated in Hopkins et al. 2022 about giving an agnostic to realizable reduction of the infinite labels multiclass classification setting.", "essential_references_not_discussed": "I think it would be good to add a remark about the samples complexity obtained in Brukhim et al. 2022 when presenting corollary 4.3 and the sample complexity obtained in Charikar and Pabbaraju, 2023 when presenting corollary 4.4, since they are a $ 1/\\varepsilon $ polynomial factor better. Also, is there any work on multilabel classification, that would also be nice to add.", "other_strengths_and_weaknesses": "The paper is well written. The paper solves an interesting open problem from Hopkins et al. 2022, extending the agnostic to realizable framework to the channeling infinite label space setting, in an elegant way.", "other_comments_or_suggestions": "Congratulations on your nice paper, here are some notes that I took while reading.\n\n- page 3 second column line 131-133 Vapnik 2006, the date might be of?\n- page 3 second column line 160 and proof of lemma 4.2, the notation  $ (\\mathcal{X} \\times \\mathcal{Y})^* $ is used differently, as respectively all possible sequences and examples where $ c^{*} $ is realizable.\n- page 5 first column line 254-255 is it $ \\varepsilon/(2\\mu^*) $   or is it $ \\varepsilon \\mu^*/2 $? That was a general question I had for this proof. \n- page 7 first column, from equation 8 to equation 9, where did the $ \\epsilon/2 $ from the left side of equation 8 go?", "questions_for_authors": "1. I was a bit confused about some of the motiviation but was not able to make it concise, here was my thoughts: Page 2 first column line 055-073: Looking at David 2016 and the proof of their theorem 3.3, my understanding of the agnostic sample compression scheme they use is that it is the realizable sample compression run on the largest sub sample $ S' $ of $S$ which is realizable by a hypothesis in $C$. Thus, the output space of their agnostic sample compression scheme is the same as the output space of the realizable sample compression scheme, so representation preserving in terms of the output of the realizable sample compression scheme. Jumping to page 5 second column line 254-268, the framework is applied with algorithm 1 in Brukhim et al. 2022, which from my understanding is an algorithm/realizable sample compressions scheme(please correct me if i am wrong), thus the output of the algorithm 1 presented in this paper is the output of algorithm 1 in Brukhim et al. 2022, so a realizable sample compressions scheme run on some subset of the data set $ S,$. Now again going to Brukhim et al. 2022 and considering their proof of the agnostic case, it uses theorem 3.3. in David 2016, thus it runs the algorithm 1 in Brukhim et al. 2022/the sample compressions scheme on the largest sub sample $ S' $ realizable by the hypothesis in $C$, thus essentially having the same output of hypothesis?. Thus, going back to page 2, first column line 055-073 I don't quite get the motivation for outputting simple learners? It is also known from, for instance, \"Optimal Learners for Multiclass Problems\" Amit Daniely, Shai Shalev-Shwartz, theorem 1 that in for instance the multiclass learning setting that simple learners/proper learners can not guarantee to learn. My understanding is that the picture is the same for list learning, and that the proof of Charikar and Pabbaraju, 2023 goes through a similar sample compression technique, this understanding is from their section 7.2 I did not check their appendix B. I get that the reduction presented in the paper, in the case that the learner is simple, proper, or close to proper, the reduction will output something simple. However, from my understanding, the cool thing about this paper is that it captures cases with infinite label spaces that the work of Hopkins et al. 2022 did not, e.g., Multiclass classification as a prime example. Thus i don't get this motivation on page 2 first column line 055-073 about necessarily being related to simple learners. I apologize in advance if I have misunderstood some of the previous works since they are not simple for me to grasp. I also understand that the motivation of a work is somewhat surjectiv so as written above I most likely are misunderstanding something. \n\n2. page 5 second column line 265-268 and page 6 first column line 287-292, in both place i think it would be worth mentioning the agnostic abounds obtained in respectively Brukhim et al. 2022 and Charikar & Pabbaraju, 2023, which from my understanding is a $ 1/\\varepsilon $ factor smaller.\n\nI would like to keep my score. I also hope that the authors will add a the comment to corollary 4.3 and 4.4 about the worse sample complexity compared to these works and that they in these two cases output the same as the sample compression scheme of David et al. 2016.", "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": "vZQDrmd9cI", "reviewer": "Reviewer_ajtt", "summary": "In the PAC learning model, one is trying to learn a function f over a distribution D. One is given samples and attempts to return a hypothesis h so that Pr_{x ~ D}(f(x) neq h(x)) is small. In the realizable setting, one obtains samples of the form (x,f(x)) where f is guaranteed to be in some function class C and x ~ D. In the agnostic model, one obtains samples of the form (x,y) from some arbitrary distribution (with marginal x ~ D) and tries to output a hypothesis h where Pr(h(x) neq y) is competitive with the best Pr(f(x) neq y) over the best f taken from the class C.\n\nThere are many variations of this setting where the existence of a learner in the realizable setting implies the existence of an agnostic learner. [Hopkins et al '22] found a relatively simple reduction that can be used to show in a fairly wide variety of settings that a learning algorithm in the realizable setting can be used to construct an agnostic learner. Their primary focus was on the distribution-family model where the x-marginal D is taken from a known but arbitrary family of distributions. In this context, their construction provided the first known realizable to agnostic reduction but only when the space of values of y was finite (as otherwise the reduction is false without extra assumptions).\n\nThis paper shows that a simple modification of the reduction of [Hopkins et al '22] can be used when the space of y's is infinite in the distribution-free model (i.e where D can be taken to be *any* distribution over the domain X). In fact, they prove this in a slightly more general context that includes list-decodable and multi-valued learning problems.\n\nWhile many of these reductions were already known in [David et al., 2016], the resulting reduction in this paper is substantially simpler and guarantees that the returned hypothesis of the agnostic learner comes from the same class of functions returned by the realizable learner (albeit this is all at the cost of somewhat worse sample complexity than [David et al., 2016]).", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for dedicating their time to assess our work. Below, we address the comments provided by the reviewer.\n \n**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}$.\n\n**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.\n\n**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$.\n\nWe hope this rebuttal convinces you of the significance and novelty of our contributions, and addresses your concern about the correctness of Theorem A.3.", "claims_and_evidence": "Yes. They are supported by mathematical proof.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "Although I didn't read proofs in detail, I was able to convince myself that the results in the main body could all be proved using techniques similar to those mentioned. Although the full proofs may contain small errors, they should be easily fixable.\n\nOn the other hand, I believe that Theorem A.3 is wrong.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This work expands on the ideas of [Hopkins et al] and produces results similar to those of [David et al] but with some advantages and disadvantages over that work.", "essential_references_not_discussed": "Not that I know of.", "other_strengths_and_weaknesses": "While the main result of this paper is nice, the technique is a relatively simple extension of [Hopkins et al] and the headline result was basically already known by [David et al], and I do not think that this result is central enough for this simplified proof to be publishable on its own.\n\nThe discussion of the reduced sample complexity in the case of Massart noise was cute, but not enough to save the paper.", "other_comments_or_suggestions": "Unless I am misunderstanding the definitions (your definition of partial learners is hard to follow), I believe that Theorem A.3 is wrong.\n\nIn particular, let X={a,b}, Y=A={0,1}, L(y,z) = 0 if y=* or y=z and 1 otherwise. C=H consists of two functions:\nf(a) = 0, f(b) = *\ng(a) = g(b) = 1\n\nThen a 1-sample realizable learning algorithm takes (x,y) and returns g if x = b or y = 1 and f otherwise. This has error 0 since if the true function is f, then D must be supported on (a,0).\n\nHowever, consider the agnostic learning problem where D is supported on (b,0). Then Algorithm 1 running on this produces only the hypothesis g, which has error 1.", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a simple reduction scheme from agnostic to realizable learning for multiclass classification with potentially infinite label space. The approach is also applied to list PAC model and multi-label learning. While the work shares high level insights with Hopkins et al, this paper presents new techniques that lead to much simpler analysis and more general applications of the meta theorem (for example, the main results hold for any distribution and while Hopkins et al needed certain distributional assumptions).
Decision: Accept (poster)