Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes
Authors: Alkis Kalavasis
Grigoris Velegkas
Amin Karbasi
Venue: NeurIPS 2022 Accept (2022)
Keywords: multiclass classification
universal learning rates
partial concept classes
learning theory

Abstract: In this paper we study the problem of multiclass classification with a bounded number of different labels $k$, in the realizable setting. We extend the traditional PAC model to a) distribution-dependent learning rates, and b) learning rates under data-dependent assumptions. First, we consider the universal learning setting (Bousquet, Hanneke, Moran, van Handel and Yehudayoff, STOC'21), 
for which we provide a complete characterization of the achievable learning rates that holds for every fixed distribution. In particular, we show the following trichotomy: for any concept class, the optimal learning rate is either exponential, linear or arbitrarily slow. Additionally, we provide complexity measures of the underlying hypothesis class that characterize when these rates occur. Second, we consider the problem of multiclass classification with structured data (such as data lying on a low dimensional manifold or satisfying margin conditions), a setting which is captured by partial concept classes (Alon, Hanneke, Holzman and Moran, FOCS'21). Partial concepts are functions that can be undefined in certain parts of the input space. We extend the traditional PAC learnability of total concept classes to partial concept classes in the multiclass setting and investigate differences between partial and total concepts.

Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes
Alkis Kalavasis*
Grigoris Velegkas"
National Technical University of Athens kelavasissalkis@mall ntua.gr gr
Yale University
vrigoriis.ellegas@@yall. edu
Amin Karbasi Yale University, Google Research amin. tarbasi@yale.o
Abstract
In this paper we study the problem of multiclass classification with a bounded number of different labels k, in the realizable setting. We extend the traditional PAC model to a) distribution-dependeen learning rates, and b) learning rates under data-dependent assumptions. First, we consider the universal learning setting (Bousquet, Hanneke, Moran, van Handel and Yehudayoff, STOC'21), for which we provide a complete characterization of the achievable learning rates that holds for every fixed distribution. In particular, we show the following trichotomy: for any concept class, the optimal learning rate either exponential, linear or arbitrarily slow. Additionally, we provide complexity measures of the underlying hypothesis class that characterize when these rates occur. Second, we consider the problem of multiclass classification with structured data (such data lying on a low dimensional manifold or satisfying margin conditions), setting which is captured by partial concept classes (Alon, Hanneke, Holzman and Moran, 20CS'21). Partial concepts are functions that can be undefined in certain parts of the input space. We extend the traditional PAC learnability of total concept classes to partial concept classes the multiclass setting and investigate differences between partial and total concepts.
Introduction
Classifying data into multiple different classes is fundamental problem in machine learning that has many real-life applications, such as image recognition, web advertisement and text categorization. Due to its importance, multiclass classification has been attractive field of research both for theorists [NT88, BCHL95, RBR09, Nat89, DSBDSS11, DSS14, SSBD14) and for practitioners [SSKS04, Co104, Aly05]. Essentially, it boils down to learning classifier from a domain X' to label space V, where | 2 2, and the error is measured by the probability that l1(x) is incorrect. In this work,
focus the setting where the number of labels is finite and identify with }} for some constant & E N.
:=]==(0 (0. 1.
I..... 1........
Multiclass PAC Learning. The PAC model [Va184] constitutes the gold-standan standard learning framework. A seminal result in learning theory [VC71, BEHW89] characterizes PAC learnability of binary classes (VC) dimension and provides clear algorithmic landscape (k: 1) through the Bapnik-Chervonen
with the empirical risk minimization (ERM) principle yielding (almost) optimal statistical learning algorithms. The picture established for the binary setting extends to the case of multiple labels when
Equal contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the number of classes [3/] is bounded. The works of INT88, Nat89] and [BCHL95] identified natural extensions of the VC dimension such as the Natarajan dimension whose finiteness characterizes multiclass learnability in this setting. Moreover, the ERM principle still holds and achieves the desired learning rate by essentially reducing learnability to optimization. The fundamental result of the multiclass PAC learning (in the realizable setting) can be summarized in the following elegant equation for any n E N which we explain right-after:
inf sup B(er(in)) = min (@x (Ndim((H) B. PERE(H)
1) )
n
where Ndim (H) stands for the Natarajan of H and O₂ subsumes logarithmic factors and dependencies on k. In words, assume that n is the number of training samples and let H C [X/] be a set of multiclass classifiers mapping the elements of the domain X' to [K]] that the learner has access to. The learner observes n labeled examples (x. E X' x [K] generated i.i.d. from some unknown distribution P with the constraint that P is realizable with respect to H. i.e., there is some h E H that has (almost surely) zero classification error. The learner then outputs guess hypothesis Tin X - [k:]. The fundamental theorem of PAC learning, as shown above, controls the expected error Eler(h,)]] where er er(n..) == (r # y), in a minimax sense, i.e., it controls the performance of the best algorithm R. (inf) against the worst-case realizable distribution P E RE(H) (sup) and states that the following dichotomy occurs: if the Natarajan dimension Ndim (H) is finite, the error rate decreases as, roughly. 1/n, so H is PAC learnable at a linear rate; otherwise, the class H. is not PAC learnable. Additionally, this theory provides clean algorithmic landscape: the ERM principle, which means outputting some classifier in H. that best fits the training set, achieves the rates of Eq. (1).
Towards Novel Learning Theories. While the PAC model provides solid and attractive theoretical framework, it fails to (fundamentally) capture the real-world behavior of various applied ML problems. In this work, we focus on the following two points of criticism for the standard PAC model. The first natural point concerns the supremum over all realizable distributions in Eq. (1).
Observation 1. The PAC model is distribution- disstibution-inlepeedeen and captures the worst-case learning rate. Is it possible to design learning theory that provides siriiuution-dependee learning rates?
Another critique is that one cannot express natural data-dependent assumptions through the PAC framework. For instance, tigh-dimmesional data may lie in a low-dimensional manifold. To be more specific, consider the task of classifying images of vehicles. The representation of such images corresponds a low-dimensional subset of the space of all possible images, most of which do not correspond to vehicles. A prominent way to capture such assumptions is via partial concepts: these are functions which can be undefined on a subset of X, a departure from the traditional model.
Observation 2. The PAC model only considers total concept classes, i.e H. S [k]]* which cannot express data-dependent constraints. Is it possible to design a learning theory for partial concepts h {0, 1,... k *), where h((z) means that h is undefined at x??
The aim of this paper is to develop (i) classification and (ii) learning theory for partial multiclass concept classes in the distribution- independent setting?. We comment that we focus on the realizable setting that already poses important challenges and requires novel ideas and we believe that our results can be extended to the agnostic case, which is left for future work. We remark that such theories for binary classification were recently developed [BHM* + 21, AHHM22]. However, in various practical applications, such explanations may not suffice, since it is rarely the case that there are only two classes. As it is already evident from the PAC setting, moving from binary classification to multiclass classification is not trivial [DSBDSSI1]. We now discuss Observation 1 and 2; we underline that our goal is not to replace, but to build upon and complement, the traditional PAC model, which constitutes the bedrock of learning theory. cetiibbution-epeddeeee Learning Rates. In many modern machine learning applications the generalization error E(er(T..)] drops exponentially fast as a function of the sample size [CT90, CT92, Sch97, VL21J. However, the traditional PAC learning theory predicts merely Ö(d/n) rates in the realizable setting, where d is the complexity measure of the underlying concept class that the algorithm is trying to learn. A possible explanation for this discrepancy between the theoretical
siwrriutiiondependded learning theory for multiclass
While we believe that one could design unified learning theory addressing the two questions at once, we prefer to provide two separate theories, since they are both interesting in their own.

---

guarantees and the empirical performance of the learning algorithms is the worst-case nature of the PAC guarantees. Notice that in Eq. (1), for any fixed learning algorithm, one considers its performance against the worst distribution for it. In particular, this means that as the sample size increases and new classifiers h, are produced, the distribution that is used as benchmark can differ. However, in many practical applications, one considers some fixed distribution P and measures the performance of the classifier as n Oo without changing P. Hence, there is an important need to study mathematical models that capture this behavior of learning algorithms and not just the minimax one. One such approach that was recently proposed by [BHM+21] 21] is to study universal learning rates, which means that the learning rates guarantees hold for every fixed (realizable) distribution P, but there is not uniform bound over all of the distributions. To be more precise, H. is learnable at rate R (where lim R(n)= = 0) in the universal setting if'
She VP E RE(H). 3C C(P), c(P) > 0 so that E[er(h..)] S C. R(c- m), Vn E N. (2)
Note that the above equation is the same in the PAC model with the exception of change between the existential quantifiers: in PAC, the focus is on the case where 3C, > 0 : VP E RE(H) the guarantee holds (which expresses uniformity), while in the universal setting distribution-dependen constants are allowed. This subtle change in the definition can make the error-rate landscape vastly different. As an example, consider the case where for h., we have that er(h,) ) S C(P)e ((P)e-e(P)n for every distribution P. where C(P), c(P) are some distribution-dependeee the pointwise supremum over all of these infinitely many distributions, it can be the case that the resulting function drops as C" /n, where C" is a distribution-indeeendent constant [BHM+21] 21].
constants. When we take
Partial Concept Classes. The motivation behind Observation 2 is that, in various practical learning tasks, the data satisfy some special properties that make the learning process simpler. For instance, it is a common principle to use classification with margin where the points in the dataset have safe gap from the decision boundary. Such properties induce dete-dependnnt assumptions that the traditional PAC learning theory framework provably fails to express. In fact, existing data-dependent analyses diverge from the standard PAC model WA98, HW01] and provide problem- specific approaches. Thus, there is need for formal framework that allows to express such data-dependent restrictions and study these problems in a unified and principled way. Recently. [AHHM22] proposed an elegant extension of the binary PAC model to handle such tasks via the framework of partial concept classes. As an intuitive example, a halfspacc with margin is a partial function that is undefined inside the forbidden margin and is a well-defined halfspacc outside the margin boundaries.
1.1 The Traditional Multiclass Learning Problem
Let [k:] = {0, 1, ..... k} for some fixed positive integer k E N. We consider a domain X' and a concept class H C [k]** A classifier is a universally measurable' function h X - [k]. The error rate of a classifier h with respect to a probability distribution P on X' x [k] is equal to er(h) erp (h) = Pr(r.))-((((z) # y). We focus on the setting where P is realizable, i.c.. infnex er (h) = O. Formally, a (deterministicc) learning algorithm is sequence of universally measurable functions, which take as input sequence of n independent pairs (X,, Yi) ~ P (training set) and output classifier hig X + y. The goal is to come up with algorithms whose E(er(h,)) admits fast decay as a function of n, where the expectation is over the training set.
1.2 Universal Multiclass Learning: Our Results
The aim of our first theory is fully characterize the admissible universal rates of learning, i.e., Efer(h,,) ), in the multiclass classification setting with a bounded number of labels. The following defi- nition formalizes this notion of achievable rate in the (realizable) universal learning model [BHM*21].
Definition 1 21D. Let H C [K]] and let R N + [0, 11, with R(n) - O, be rate function. We say that H. is learnable at rate R if there exists learning algorithm hn such that for every realizable distribution P on X x [k] with respect to H. there exist cetrribution-eepended C, c > 0 for which E(er(h,)) < CR((en) for all n E N. Also, H is not learnable at rate faster than R for any learning algorithm h., there exists a realizable distribution P on X [Bi] with respect to H and
e We discuss measurability formally in Appendix B.5
We focus for simplicity on deterministic learners. Our results extend to randomized algorithms.
3

---

distribution-depeddent dependent C, C >> 0 for which E(er(h.)) 2 CR((cn) for infinitely many E N. H. is learnable with optimal rate R if it learnable at rate R. and not learnable faster than R. Finally, H requires arbitrarily slow rates if. for every R(n) + 0, H is not learnable at rate faster than R.
In the universal multiclass setting, we show that the following fundamental trichotomy occurs (in comparison with the dichotomy witnessed in the uniform PAC model). This result is a theoretical justification of the exponential error rates observed in practice.
Theorem 1. Fix constant & E N. Consider hypothesis class H C [k]x with [H] > k + 2. Then, exactly one of the following holds for the learning rate of H in the realizable case:
H. is learnable at an optimal rate e
H. is learnable at an optimal rate 1/n.
H. requires arbitrarily slow rates.
We mention that [H] > k + 2 comes without loss of generality." In contrast to the standard PAC model, any concept class is learnable in the universal rates setting (HKSW20). The analogue of non-lcarnability in the uniform setting is the case of arbitrarily slow rates. Our second result is the specification of some combinatorial complexity measures of H. that characterize the optimal learning rate of this class. Let first provide some informal definitions of these measures. We begin with the notion of multiclass Littlestone trees, which extends the binary Littlestone trees from [BHM+21].
Definition 2 (Informal (see Definition 11)). A multiclass Littlestone tree for H C [K]x is complete binary tree of depth d S co whose internal nodes are labeled by X, and whose two edges connecting a node to its children are labeled by two different elements in [K], such that every path of length at
most d emanating from the root is consistent with a concept h E H. We say that H. has an infinite multiclass Littlestone tree if there is a multiclass Littlestone tree for H of depth d oc.
For some intuition we refer the reader to Figure 1. The above complexity measure appears in the definition of the multiclass Littlestone dimension [DSBDSSI In fact, class H. S [A] has multiclass Littlestone dimension d if it has multiclass Littlestone tree of depth d but not of depth +11. 1. We underline that having an infinite multiclass Littlestone tree not the same having an unbounded multiclass Littlestone dimension. A class H. has unbounded Littlestone dimension if for every d E N there is some tree of depth d. However, this does not mean that there is single infinite tree. This is a fundamental conceptual gap between the uniform and the universal settings.
The next definition is novel and is moti- vated by the fundamental notion of the Natarajan dimension from the multiclass
(0)
F00
PAC setting (see Detinition 7). We first need some terminology:
tuple
3h E H.:
201
(s1,,.., Te, 81 5 3 88
(0)
(1)) E
h(*z) = 10)
X' x [K]e [K]] with 8, 4 (1) for
(0)
(0)
any i E [4] is N-consistent with the edge (y.,...; V/) E {0, 1)e and the concept h E H if h(x;))
100
h(x1) = ((0)
M(110) 400
o (ax) for any i E [t]. Recall that if the tuple is N-consistent with any binary pattern y E 13', (x1,..., 2x) N-shattered. More gener- ally, a path is Ncconsistent with con- cept h E H. if each node of the path is N W-consistent with the edge connecting the node with its child across the path and h. Since the next definition might be hard to parse, we refer the reader to Figure 2 for some intuition.
11
, we say that
Figure I: A multiclass Littlestone tree of depth 3. Each
node Fy has two children e(0) * {()) where el e [k] for any i E 1) and u E {0, i... the set of binary strings of arbitrary length. Every branch is consistent with some concept h E H. The figure is adapted from [BHM+21].
Definition 3 (Informal (see Definition 12)). A Natarajan-Litteesorn (NL) tree for H. C [ba]* complete tree of depth d < that every level 1 < S d has branching factor 2' and nodes that
x is a
'The constraint [H|
le + 2 rules out some degenerate scenarios, kindly refer Appendix A.2.

---

are labeled by X' X [KY X [R]' (so that for all i E [t] the two labels in [1c] x [k] are different) and whose 2 edges connecting node to its children are labeled by the elements of {0, 13.. It must hold that every path of length at most d emanating from the rool is N-consistent with a concept h E H. We say that H has an infinite Natarajan-LLitlestonn tree there is an NI. tree for H of depth d = co.
(=0,00 $0,00 $0,00 T0,00 0,00 $0,00 26,00 0,,00 $0,00)
O(0) 0(1)
(0) 1(1) 2(0) 2(1)
3h H
h(#0) = 8g
(1)
8
M(a4) = 81
0(0) hh(x)()))))))){)))) - 81
1(0)
01
h(29,00) $1,000 h(2),00) $i.00 h(2
o(1)
1(0)
$1,00
2(0)
(1)
8
0(0)
0(1)
0
1
90
1(0)
90
1(1)
10
11
000
(0) (1)
(og. 5g ,88
000
010
$1,00
((0) 0(1)
81,00 o
i,,00~
$1,00
1(0) 1(1)
$1,00
x
1,000
81,00
2(0)
$1,00
2(1)
011
100
00
(of
(ff.01 $1,11
0(0)
$,01
0(1)
100 1,01
1(0)
1101
1(1)
-
1,01 $1,01
2(0) 2(1)
110
0(0) ( , 81
0(1)
10)
1(1)
01
111
1 81 ,
10
(ff,
10
$1,10
0(0)
1,10
0(1
- 10
$,100
100]
1,10
1(1)
2
1,
10
$1 1,10 8,100
2(0) 2(1)
(xf, $1,11
0(0) 0(1)
$1,11,
- $1,11
100) 10)
9111
200) 201)
1.11 $1.11)
Figure 2: A Natarajan-Littlestun tree of depth 3. Every branch is consistent with a concept h E H. This is illustrated here for one of the branches. Due to lack of space, not all nodes and external edges are drawn. The figure is adapted from [BHM 211. The root of the tree is the point (0)
(zz) with two colors 88 * $8 In this example, the branch picks the string '1' and hence the node of the second
level contains the two points (z.. x1) and the associated colors. We proceed in a similar manner.
An NL tree looks like multiclass Littlestone tree whose branching factor increases exponentially with the depth of the tree and where each node at depth / in the NL tree contains points æ ..., Te of X' and two colorings (0),,(1)) so that (z;) * s()) (a:)) for all E [t]. Crucially, this structure encapsulates the notion of N N-shattering in the combinatorial structure of a Littlestone tree. Intuitively, along each path in the NI tree, we encounter N-shattered sets of size increasing with the depth. Using these two definitions, we can state our second result which is a complete characterization of the optimal rates achievable for any given concept class H [k]*
Theorem 2. Then, one of the following holds for any n E N in the realizable case:
Fix a constant positive integer k. Consider hypothesis class H. S [b] with [H] > k
H does not have infinite multiclass Littlestone tree, then it is learnable an optimal rate e em
If "H has an infinite multiclass Littlesooee tree but does not have an infinite Natarajan- Littlestone tree, then it is learnable at an optimal rate 1/n.
. If has an infinite Natarajon-Littestoon tree, then it requires arbitrarily slow rates.
It is clear that the above result implies Theorem 1. We remark that not only the achievable rates are different compared to the uniform setting, but also the algorithms we use to get these rates differ vastly from ERM. We sketch the main techniques in Section 2. For the formal proof, see Appendix C. We briefly summarize our main technical contributions in this setting: using the pre-described complexity measures of H. we introduce novel Gale- Stewart games (see Section 1.4 for a definition) which lead to new learning algorithms that achieve the optimal learning rates. For the exponential rates setting, the algorithm that we obtain through the Sale-Stewart game cannot be directly used to make predictions, since it takes as input two labels and it outputs the correct one. Hence, our predictor, essentially, plays tournament between all the potential labels using this function we just mentioned. The case of linear rates is also more technically involved compared to its binary counterpart and
5

---

this is related to the fact that the Natarajan Littlesstt tree has a more complicated structure than the VCL tree (for example, we need check all the possible mappings from some given points to labels). The Gale-Stewart game that handles the case of linear rates goes as follows: the adversary presents to the learner a tuple of points x; and two (different) colorings for these points. Similarly as before, we could not use simpler game to obtain the result. Also, we extend the lower bounds from [BHM 21J that hold for binary classification to the multiclass setting using our combinatorial measures. Ensuring the realizability of the distribution in the case of arbitrarily slow rates is bit delicate and it raises questions about how the equivalence between various combinatorial dimensions, like the Graph dimension and the Natarajan dimension, which is established in the PAC setting translates to the universal setting. For further details, we refer to Section 2 and Appendix C.5.
1.3 Partial Multiclass Learning: Our Results
As we mentioned carlier, traditional PAC learning cannot capture data-dependent assumptions.
Inspired by [AHHM22], we slightly modify the basic multiclass learning problem in a quite simple manner: instead of dealing with concept classes H C
kj where each concept h E H is
total function h: X' + {0, I,..., k}. we study partial concept classes H. S {0, I,... k, x, }x where each concept h is now a partial function and ((z) means that the function h is undefined at x. We define the support of h as the set supp(h) = {- E X h(z) J *}. To illustrate the power of partial classes, we comment that the fundamental class of d-dimensional halfspaces with margin y > and A labels can be cast as a partial class H. = {lw W E kx) J. where hw (x) = E [k] (W; W)). x: 2 y for all j A and hw (2) = otherwise [AHHM22]. As another example, we can express the constraint that the data have to be in a low-dimensional space by considering the partial concept class H. = {h: R2 + {0, I,..., } dim (h) < d). where (S) captures the dimension of the set of points in S. We characterize multiclass PAC learnability of partial concepts in the realizable setting. A distribution P on X x 1. k} is realizable by H if, almost surely, for any n, a training set (x,, se) ~ pm is realizable by some partial concept h E H. i.e., {ax sej)) S supp(h) and h(x+) = yi for all S n. For partial concept h and a distribution P on X x 10 k), we let p = Pr(zzg)--P (x(x)= * y]. i.e. whenever h outputs it is counted as a mistake. We mention that the standard combinatorial measures such as the VC or the Natarajan dimension naturally extend the partial setting; e.g., a partial class H VC shatters set of points
any binary pattern is realized by H. (we forget about +).
Definition 4 (Multiclass Partial PAC Learnability [AHHM22]). A partial concept class H C
{0, I....,,, x}* is PAC learnable if for every e,8 E 10, there exists a finite M(e, E N
and a learning algorithm A such that, for every distribution P on X x {0,,, I,..., k} realizable with respect for S ~ PMl(e.6), it holds that Prg (Ar S t] > 1 8. The sample complexity
of la is the value M(e. 5) and the optimal sample complexity is the minimum possible value of M(e, 8) for any given e, ò.
We provide a combinatorial characterization of multiclass PAC learnability in the partial setting with a bounded number of labels. We additionally give bounds for M(e, 8) in our more general Theorem 6.
Theorem 3. Fix a positive constant N. For any partial concept class H C {0, 1, .,.,,...... k, })* holds that H is PAC learnable if and only if (ddim(H) (H) < Co.
Here, Ndim(H) is the Natarajan dimension of H (see Definition 7 and Remark 2). At first sight this result may not seem surprising. However, its proof is different from the standard multiclass PAC learning (for constant k), which goes through uniform convergence and ERM. In fact, such tools provably fail [AHHM22). For a sketch, see below Theorem 6. We complement the above structural result with some additional insight which sheds light towards the, perhaps unanticipated, complexity of partial concept classes. To this end, we discuss the question of disambiguation [AKM19, AHHM22]: Can a partial Natarajan class (i.e., with finite Ndim) be represented by total Natarajan classes? To address this task, the notion of disambiguation is required: roughly, a total class H disambiguates the partial class H if every partial concept h E H can be extended to some total concept T E H. i.e., T agrees with in the support of and assigns to the undefined points some labels. For formal definition of disambiguation, see Definition 15. For the case h = 1, [AHHM22] provided an easy-to-learn partial class that cannot be represented by any total class of bounded VC dimension using, surprisingly, some recent results from communication complexity and graph theory (see e.g., [BBDG+22] 22)) We extend this result to the multiclass setting using Sauer's 's lemma, which provides a bound on the growth function [SSBD14], and tools from the binary impossibility result.

---

Theorem 4 (Informal, see Theorem 16). Fix k E N. For any E N. there exists a class H. S {0, 1,........... ..,, k 1 with (H) = O2 (1) such that any disambiguation H. of H. has Ndim (H) = cc.
We denote with (1) constant that depends k. Via Theorem 3, the above partial class H. is PAC learnable; however, any disambiguation of H. causes a blow-up to the Natarajan dimension. This result showcases the complexity of partial concepts. We briefly outline the main technical contributions in this regime: we extend the main results of [AHHM22] for binary classification to the multiclass setting using appropriate complexity measures. Recall that the combinatorial
(SSP) lemma [Sau72, SSBD14) bounds the size of a (total) class H S {0, 13"h by Σi= Evc (*)) Notably, [AHHM22] showed that this lemma does not hold true for partial concept classes. To obtain our disambiguation result, we prove that the second variant of the SSP lemma, which uses the growth function of the class [SSBD14], does hold in the partial regime, which may be of independent interest.
1.4 Preliminaries and Related Work
Preliminaries. In this section, we discuss some important preliminaries for this paper. Due to space constraints, we refer the reader to Appendix B for a more extensive discussion. Gale-Stewart Games. An important tool we leverage to establish our results in the universal learning setting is the theory of Gale-Stewarl (GS) games [GS53]. Every such game consists of two players, learner PL and an adversary PA. and is played over an infinite sequence of discrete steps. In each step, the adversary presents some point 2, E Nr to the learner and the learner picks a response y/ E V,. If some predefined condition gets violated at some step f. the game terminates and the learner wins. On the other hand, if the condition does not get violated during the infinite sequence of these time-steps, the adversary wins. The main property which characterizes the GS game is that the winning strategy of the learner is finitely -eeiial-de i.e., she knows that she has won the game after playing a finite number of rounds. [GS53, 12, HW* 93] proved that either Pr. or PA has a winning strategy, i.e., playing that strategy makes them win regardless of the opponents actions. Similar to [BHM 21], the main reason we use GS games in this work is to obtain functions that are eventually correct. Related Work. As we mentioned in the introduction, we focus on the well-studied problem of multi- class classification [Nat89, BCHL95, RBR09, DSBDSSIL, 1, DSS14, SSBD14, BCD 222, For more detailed overview, see Appendix A. Our work provides two theoretical perspectives complementing and extending the standard multiclass PAC learning. For the universal rates, the seminal work of [BHM 21] provided a similar trichotomy for the binary setting (we obtain their results by setting I- 1). The gap between exponential and linear rates was studied by [Sch97] in some special cases. Also, [AL98] showed that there exist concept classes for which no improvement on the PAC learning rate is possible in the universal setting. A natural approach to obtain results for the multiclass setting is via reductions to the binary setting. the exponential rates setting, a first idea would be to consider for the class H C [x]] the binary restrictions H|: { : h E H). where h, denotes the i-th bit of the output of h. In order to obtain the desired result for exponential rates, one has prove that if H. does not have infinite multiclass Littlestone tree, then every H., does not have an infinite binary Littlestone tree. However, it is not clear how to obtain such a result. This is why we design statistical learning algorithms for the multiclass setting from scratch, following the conceptual roadmap introduced in [BHM+211 We note that the existence of multiple labels requires various novel ideas compared to the binary setting. We introduce novel Gale-Stewart games (see Algorithm 1, Algorithm 2) in order to provide winning strategies for the learning player both in the exponential and the linear rates settings. Finally, in terms of reductions for the linear rates setting, we provide sufficient condition for learnability at linear rate using a reduction to the binary setting; however, it is again not clear how to use these complexity measures in order to obtain lower bounds (see Open Question 1). In general, the idea of "universal learning" has been studied in various concepts such as universal consistency [Sto77, DGL13, Han20, HKSW20. BC21, Han22, Bla22, BJ22, BCH22] and active learning [Han09, BHV 10, Han 1, HY15]. For an extended discussion, we refer to [BHM 21]. For the partial concepts setting, our work builds on the seminal work [AHHM22] and uses tools from [BCD* 22]. The work of [AHHM22] shows that the algorithmic landscape behind partial concept classes is quite elusive. We extend some of their results to learning scenarios where one deals with more than two labels. Our contributions draw ideas from various directions, namely the one-inclusion hypergraph algorithm [HLW94, RBR09, DSS BCD+222 which we define for- mally in Appendix B.2, the Sauer-Shelah-Perles lemma [Sau72] and recent breakthroughs in the intersection of graph theory and complexity theory concerning the Alon-Saks-Seyman -SssSmo--Se problem [HS 12, Amal4, Goö15, SA15, BDHT17, GPW18, AHHM22, BBDG-22 22].
7

---

Remark 1 (Connection between Universal Rates and Partial Concept Classes), There is an interesting connection between universal rates and partial concepts: in the universal learning setting, the first step of the approach is to use the data to simulate some Gale-Stewar gumes and show that, with high probability, most of them will have "converged", ie., the function that corresponds to the learning strategy of the learner will be correct. In turn, this defines some data-dependent constraints. For instance, assume that g is a successful NL pattern avoidance function, i.e., a function which takes as imput any l points Ei..... .. and any two (everywhere different) mappings s("), , from points to labels and returns an invalid pattern, i.e., a binary pattern y of length that is not compatible with the definition of the Natarajan dimension (i.e., there is no function h E H. such that if y: = 1 then h(z,) = s()) (xza) and if y) = O then h(z;) = 5(0) (xx), for all i E [e). Then, we can define a partial concept class H', the set of all functions from X to {1...., .....,,,+ {,+ that satisfy the constraint of this pattern avoidance function, and it has two important properties: its Natarajan dimension is bounded by l and learning algorithm for H' also learns H. Hence, understanding the learnability of partial concept classes is an essential step in coming up with more natural learning strategies in the universal learning setting. importantly, in both of these settings, ERM is not an optimal learning algorithm and the one-inclusion graph predictor is an essential part in deriving results in both theories.
2 Technical Overview & Proof Sketches
In this section we briefly discuss the technical details and provide proof sketches of our main results.
Technical Overview of Universal Multiclass Learning. In the universal multiclass setting, we provide three lower bounds and two algorithms in order to get the desired trichotomy of Theorem 1. The first lower bound states that no class H is learnable at rate faster than exponential (see Proposi- tion 1). Our first essential contribution is that any H C [k] x is learnable at (optimal) rate e n if and only it has no infinite multiclass Littlestone tree. For this task, we provide Algorithm that achieves this rate. Our approach uses tools from infinite game theory (Gale-Steware games) and set theory (ordinals) in order to show that there exists an online learning algorithm that makes only a finite number of mistakes. We denote this key subroutine with ge in Algorithm 1. This subroutine 9i is obtained by using the winning strategy of the game, which given the correct label and an incorrect one outputs the correct one, to play tournament between all the labels. Our final algorithm runs the above subroutine 9t. on multiple batches using data-splitting techniques and then takes a majority vote: the intuition behind this step is that the majority vote of various executions of our algorithm will be much better concentrated than a single execution and will achieve the desired exponential rate. The main technical challenge is to construct 9t-
Algorithm 1 Exponential Rates Algorithm for Universal Multiclass Learning
Exponential Rates
Exponential GS Game
Let 9: : X' - Y be an eventually correct label- ing function (Theorem 5).
For any E N:
PA picks = (E,, (0) v1")) E X'
Let VI........ Xn, Yn) be the training set. Estimate i, such that Pr[er )] < 3/8. Break the training set into N = nt/E, batches. Create N copies of g: g'.....'' gN where the i-th copy is trained on the i-th batch.
PA reveals Ke to the learner PL.
Pr. chooses 7/- E {0, 1).
Py. wins the game if for some E N
{h H ::Ee(E)) v (nc) Vl [1.t]} 0.
To predict the label of some I E X. take the majority vote over all oz
Our approach to construct the eventually correct function 9: passes through the adversarial on- line learning setting. As a first step, we introduce the standard multiclass online learning game [DSBDSSI between an adversary and a learner. In this game, the adversary picks a point Ie E X' and the learner guesses its true label yt E [k]] In the standard mistake bound model [Lit88, DSBDSS I], the learner's goal is to achieve a uniformly bounded number of mistakes (and this is associated with the multiclass Littlestone dimension and the Standard Optimal Algorithm). We extend this model to the case where we can guarantee a finite number of mistakes for each realizable sequence, but without priori bound on the number of mistakes, i.c., this number is not uniformly
8

---

bounded. This is the motivation behind Definition 2. We prove that when H. does not have an infinite multiclass Littlestone tree, there exists an online learning algorithm for this setting which makes finitely many mistakes. This is exactly the eventually correct function Ir of Algorithm 1. To be precise, the function It corresponds to the tournament that we run using the winning strategy after round of the learning player in the above game.
Theorem 5 (Informal, see Theorem 9). For any H S [M]], Hf does not have an infinite multiclass Littlestone tree, there is strategy gt, t E N. for the learner that makes only finitely many mistakes. Otherwise, the adversary has winning strategy.
To prove this result, we invoke the theory of Gale-Stewart games. We introduce a novel two-player game, the Exponential GS Game outlined in Algorithm 1. The structure of this game looks like the standard multiclass online learning game but has some evident differences; the adversary not only reveals point & but also two colors for it. Then, the learner should choose between these two. The structure of this game (while unaccustomed) is crucial and generalizes the game of [BHM
The learner wins if the class of consistent hypotheses He He..m.......... = {h H h((e)) = (me) VE [1..t]] becomes empty after a finite number of rounds. If the game continues indefinitely, the adversary wins. The intuition behind the definition of the class in Algorithm is that the adversary wins as long as there is always a hypothesis in H that is consistent with the examples (this is in parallel with the definition of an infinite path in the multiclass Littlestone tree). Using tools from Gale-Stewart games (Appendix B.6), we manage to show that the learning player Pt. has a winning strategy if and only if H. does not have an infinite multiclass Littlestone tree. This winning strategy is in fact the ordinal Standard Optimal Algorithm. Recall that it is possible to have unbounded multiclass Littlestone dimension while not having an infinite multiclass Littlestone tree.
In order to quantify this intermediate state (between uniformly bounded and truly infinite). we invoke the theory of ordinal numbers and introduce the ordinal multiclass Littlestone dimension, which quantifies "how infinite" the multiclass Littlestone dimension is. Hence, the learner's 's strategy is to play according to the SOA where the standard Littlstone dimension is replaced by the ordinal one (see Appendix C.I.1). We note that the analysis of the above game constitutes an important technical contribution in the exponential rates setting. More that, we believe that the link between the multiclass SOA and ordinals' theory is an interesting conceptual step. For further details concerning the exponential rates, we refer to Appendix C.I. Our next result (Theorem 11) is a lower bound indicating a sharp transition in the learning rate: A class H C [M]] that has an infinite multiclass Littlestone tree is learnable no faster than 1/n. Its proof uses the probabilistic method and shows that for any learning algorithm h, there exists a realizable distribution P over X' x [A] such that E(cr(h,,)] 2 ((1/n) for infinitely many n, when H has an infinite multiclass Littlestone tree.
We can now move to the linear rates setting where the situation is significantly more involved technically. In this setting, we show that any H C. [x:] is learnable at rate 1/n if and only if it has no infinite NL tree. The structure of an NL tree indicates that the notion of the Natarajan dimension (which characterizes Icarnability in the uniform setting) is invoked in order to control the complexity/eprresivity of our concept class. Compared to the exponential rates setting, we shift our goal from hoping for finite number of mistakes to looking for a control over the model complexity. This model complexity is quantified by the notion of an NL. pattern in the data (see Definition 13). Conceptually, the design of the algorithm for the linear rates follows similar path as in the exponential case; we first develop an infinite game which makes use of the structure of the NL trees. This Linear GS Game is also original and can be found in Algorithm 2. The precise structure of the game quite important for our results and various modifications of it seem to fail.
In the Linear GS Game, the adversary picks points and two colorings for these points which are everywhere different. Then the learner responds with an NL pattern 1): E {0, 1)' with the goal that there is no h E H. that is N-consistent with the ad adversary's 's input. Hence, the learner aims to find forbidden NL patterns in the data. The finiteness of the NL tree implies the existence of a winning strategy for the learner in the game and, hence, an algorithm (which one can construct) for learning to rule out NL patterns. Then, we show how to simulate this game using any H-realizable sequence and utilize the learner's 's strategy to, eventually, find forbidden NL patterns in the data. The simulation of the game is another novel part for the linear rates (see Figure 7). Intuitively, there exists some finite number m, which depends on the data sequence, such that for any collection of m + 1 points, there exists some invalid NI. pattern. The definition of the NL patterns then indicates that we cannot N -hattter any collection of m + 1 points and hence we can work, in some sense, with
9

---

Algorithm 2 Linear Rates Algorithm for Universal Multiclass Learning
Linear Rates
Linear GS Game For any E E:N:
Let gt: : :2 x [k]' x [k]* - {0, 1 be an even- tually correct NL-patter avoidance function. Let (X,,,,,.... Xn. Yn) be the training set. Estimate in such that Pr(er(gr,)) )] S 3/8.
PA picks = (0))) e((-1) (0)
86 :88 (
g. St
where (i) & X [R]] x [k]' and
(ii) ot 81 s.t. (0) (St # s (s! Vi.
Break the training set into N = n//n batches.
Create N copies of g: "",.....''* where the i-th copy is trained the i-th batch.
PA reveals & the learner Pt.
PL chooses a pattern n/e E {0. 1)
Create N copies of the one- inclinclusion graph predictor, each copy is equipped with of To predict the label of x. take the majority vote over all the one- me-inclusion graph predictors.
PL wins the game if for some E N
{ h H s.t. M(S )= =8 2
(1)
(44%) (5
}
D.
for Si < 2, E [1..]] S
class whose Natarajan dimension is m. We can then use the one-inclusion hypergraph algorithm [HLW94, RBR09, D4S14, BCD 22] (see Appendix B.2) to get good predictor for the data. Again single execution of the above strategy is not sufficient, we have to use data-splitting and aggregate our collection of predictors using the majority vote. Algorithm 2 achieves an optimal rate of 1/n. Finally, we prove that a class with infinite NL tree requires arbitrarily slow rates.
Technical Overview of Partial Multiclass Learning. In the partial multiclass setting with a bounded number of labels, we first characterize learnability in terms of the Natarajan dimension. For the proof of Theorem 3, it suffices to show the following more fine-grained Theorem
Theorem 6. For any partial class H C 1, ......,, k, }} with Nd)mmH) S oo, the sample complexity of PAC learning H satisfies C1 (18 M(c, 8) S C2- Ndim( (H) log(k) log(1/8) .for some constants C1 Cz. In particular, if (dim( = oc, then H is not PAC learnable.
For the upper bound, we have to employ the one-inclusion hypergraph algorithm (see Appendix B.2). Following the methodology of [AHHM22], we extend its guarantees (which hold for total concept classes) to the partial setting. This algorithm guarantees an expected error which can be boosted to a high probability result using standard concentration and boosting techniques. To show that the partial concept class H C 1, ..., k, *} is not learnable if it has infinite Natarajan dimension, we reduce the problem to classification with total concepts and invoke the existing (standard) lower bound. The main twke from Theorem 6 is that the algorithmic landscape of partial concept classes is provably elusive, as already indicated by the seminal work of [AHHM22]. To this end, we provide a second result that shows when one can apply the well-understood ERM principle (which is valid when the number of labels is bounded) with partial concepts. For details, we refer to Proposition 2. To conclude, we address the task of disambiguation [AKM19, AHHM22) of partial concepts (see Definition 15). Our proof of Theorem 4 relies on an interesting observation: the seminal work of [AHHM22) showed that the combinatorial variant of the SSP lemma [Sau72] does not hold in this setting. This lemma has a second variant that uses the growth function [SSBD14] instead of the size of the class. We show that natural extension of this variant for partial classes is still correct (see Lemma 13). Using this tool and techniques from [AHHM22],, we obtain our impossibility result.
Acknowledgments and Disclosure of Funding
Alkis Kalavasis is supported by the Hellenic Foundation for Research and Innovation (H.F.R.I)). Project BALSAM, ARRIFM17-1424 Grigoris Velegkas is supported by NSF (1IS-1845032), an Onassis Foundation PhD Fellowship and a Bodossaki Foundation PhD Fellowship. Amin Karbasi acknowledges funding in direct support of this work from NSF (IIS-1845032, ONR (N00014- 19-1-2406), and the Al Institute for Learning-Fnai Enabled Optimization at Scale (TILOS). The authors would like to thank the anonymous reviewers for helpful comments and suggestions.
10

---

References
[AHHM22]
Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of pac learnabil- ity of partial concept classes. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 658-67 671. IEEE, 2022.
[AKM19] Idan Attias, Aryeh Kontorovich, and Yishay Mansour. Improved generalization bounds for robust learning. In Aurélien Garivier and Satyen Kale, editors, Proceedings of the 30th International Conference on Algorithmic Learning Theory, volume 98 of Proceedings of Machine Learning Research, pages 162-183. PMLR, 22-24 Mar 2019.
[AL98] András Antos and Gábor Lugosi. Strong minimax lower bounds for learning. Machine learning, 30( (0011:333 3):3-66,, 1998.
[Aly05] Mohamed Aly. Survey on multiclass classification methods. Neural Neww, 19(1-)):2 2005.
[Ama14] Kazuyuki Amano. Some improved bounds communication complexity via new decomposition of cliques. Discrete Applied Mathematics, 166:249-22 2544, 2014.
[BBDG+22] Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, and Robin Kothari. Unambiguous dnfs and alon-saks-seymouu. In 202/ IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 116-124. IEEE, 2022.
[BC21] Moïse Blanchard and Romain Cosson, Universal online learning with bounded loss: Reduction to binary classification. arXiv preprint arXiv:21 14666 2021.
[BCD+22] Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characterization of multiclass learnability. arXiv preprint arXiv:2203.015500 2022. //attttts://rxttttt org/odg/oo. pdf/ 22003. 01550.pdf.
[BCH22] Moise Blanchard, Romain Cosson, and Steve Hanneke. Universal online learning with unbounded losses: Memory is all you need. arXiv preprint arXiv:2201.0880 2022.
[BCHL95] Shai Bendavid, Nicolo Cesabianchi, David Haussler, and Philip M Long. Characteri- zations of learnability for classes of (O.... valuud functions. Journal of Computer and System Sciences, 50(1):74-8)) 1995.
[BDHT17] Shalev Ben-David, Pooya Hatami, and Avishay Tal. Low-sensitivity functions from unambiguous certificates. In 8th Innovations in Theoretical Computer Science Confer- ence (ITCS 2017). Schloss Dugstuhl--eibniz-Zznn Zentrum fuer Informatik, 2017.
[BKK*22] Olivier Bousquet, Amit Daniely, Haim Kaplan, Yishay Mansour, Shay Moran, and Uri Stemmer. Monotone learning. arXiv preprint arXiv:2202.05246, 2022.
[BEHW89] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapnik-chervonenkis dimension. Journal of the ACM (JACM), 36(4):929 965, 1989.
[BHM 21] Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon Van Handel, and Amir Yehu- dayoff. A theory of universal learning. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 332-541, 2021.
[BHV10] Maria-Florina Balcan, Steve Hanneke, and Jennifer Wortman Vaughan. The true sample complexity of active learning. Machine learning, 80(2):111-139, 2010.
[BJ22] Moïse Blanchard and Patrick Jaillet. Universal regression with adversarial responses. arXiv preprint arXiv: 05067, 2022.
[Bla22] Moïse Blanchard. Universal online learning: an optimistically universal learning rule. arXiv preprint arXiv:2201.059477 2022.
[Co104] Michael Collins. Parameter estimation for statistical parsing models: Theory and practice of distribution-free methods. New developments parsing technology, pages 19-55, Springer, 2004.
11

---

[CT90] David Cohn and Gerald Tesauro. Can neural networks do better than the vapnik- chervonenkis bounds? Advances in Neural Information Processing Systems, 3, 1990.
[CT92] David Cohn and Gerald Tesauro. How tight are the vapnik-chervonenkis bounds? Neural Computation, 4(2):249-269 1992.
[Del77] Claude Dellacherie. Les dérivations en théorie descriptive des ensembles et le théoreme de la borne. In Séminaire Probabilités XI, pages 34-46. Springer, 1977.
[DGL13] Lue Devroye, László Györfi, and Gábor Lugosi. A probabilistic theory of pattern recognition, volume 31. Springer Science & Business Media, 2013.
[DSBDSS11] Amit Daniely, Sivan Sabato, Shai Ben-Davic and Shai Shalev-Shwartz. Multiclass learnability and the erm principle. In Proceedings of the 24th Annual Conference on Learning Theory, pages 207-232. JMLR Workshop and Conference Proceedings, 2011.
[DSS14] Amit Daniely and Shai Shalev-Shwartz. Optimal learners for multiclass problems. In Conference Learning Theory, pages 287-316. PMLR, 2014.
[G6615] Mika Göös. Lower bounds for clique vs. independent set. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1066-1076. IEEE, 2015.
[GPW18] Mika Goos, Tomiann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. SIAM Journal on Computing, 47(6): 2018.
[GS53] David Gale and Frank M Stewart. Infinite games with perfect information. Contribu- tions to the Theory of Games, 2(245-266):2-6,, 1953.
[Han09] Steve Hanneke. Theoretical foundations of active learning. Carnegie Mellon Univer- sity, 2009.
[Han11] Steve Hanneke. Rates of convergence in active learning. The Annals of Statistics, pages 333-361, 2011.
[Han20] Steve Hanneke. Learning whenever learning is possible: Universal learning under general stochastie processes. 2020 Information Theory and Applications Workshop (ITA), pages 1-95. IEEE, 2020.
[Han22] Steve Hanneke. Universally consistent online learning with arbitrarily dependent responses. In International Conference on Algorithmic Learning Theory, pages 488- 497. PMLR, 2022.
[HJ99] Karel Hrbacek and Thomas Jech. Introduction to set theory, revised and expanded. Crc Press, 1999.
[HKSW20] Steve Hanneke, Aryeh Kontorovich, Sivan Sabato, and Roi Weiss. Universal bayes consistency in metric spaces. In 2020 Information Theory and Applications Workshop (ITA), pages 1-33. IEEE, 2020.
[HL95] David Haussler and Philip M Long. A generalization of sauer's lemma. Journal of Combinatorial Theory, Series A, 7 71(2):21-240, 1995,
[HLW94] David Haussler, Nick Littlestone, and Manfred K Warmuth. Predicting {0, 1}- functions on randomly drawn points. Information and Computation, 115(2):248-292, 1994.
[HS12] Hao Huang and Benny Sudakov. counterexample to the alon-saks, alon-saks-seymour seymour conjec- ture and related problems. Combinatorica, 32(2):205 219, 2012.
[HW+93] Wilfrid Hodges, Hodges Wilfrid, et al. Model theory. Cambridge University Press, 1993.
[HW01] Ralf Herbrich and Robert C Williamson. Algorithmic luckiness. Advances Neural Information Processing Systems, 14, 2001.
12

---

[HY15] Steve Hanneke and Liu Yang. Minimax analysis of active learning. J. Mach. Learn. Res., 16(12):34773362, 2015.
[Kec12] Alexander Kechris. Classical descriptive set theory, volume 156. Springer Science Business Media, 2012.
[Lit88] Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear- threshold algorithm. Machine learning, 2(4):285-318, 1988.
[Nt889] Balas K Natarajan. On learning sets and functions. Machine Learning. 4(1):67-97,
1989.
[NT88]
Balaubramaniam Kausik Natarajan and Prasad Tadepalli. Two new frameworks for learning. In Machine Learning Proceedings 1988, pages 402-415. Elsevier, 1988.
[RBR09] Benjamin IP Rubinstein, Peter L Bartlett, and J Hyam Rubinstein. Shifting: One- inclusion mistake bounds and sample compression. Journal of Computer and System Sciences, 75(1):37-59, 2009.
[SA15] Manami Shigeta and Kazuyuki Amano. Ordered biclique partitions and communica- tion complexity problems. Discrete Applied Mathematics, 084:248-252. 2015.
[Sau72] Norbert Sauer: On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1):145-147, 1972.
[Sch97] Dale Schuurmans. Characterizing rational versus exponential learning curves, journal of computer and system sciences, 55(1):140-160, 1997.
[Sie58] Waclaw Sierpinski. Cardinal and ordinal numbers, volume 470. Warszawa, 1958.
[SSBD14] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[SSKS04] Shai Shalev-Shwartz, Joseph Keshet, and Yoram Singer. Learning to align polyphonic music. In In Proceedings of the 5th International Conference on Music Information Retrieval. Citeseer, 2004.
[STBWA98] John Shawe-Taylor, Peter I. Bartlett, Robert C Williamson, and Martin Anthony. Structural risk minimization over data-dependent hierarchies. IEEE transactions on Information Theory, 4465):192611940, 1998.
[Sto77] Charles J Stone. Consistent nonparametric regression. The annals of statistics, pages 595-620, 1977.
[Va184] Leslie G Valiant. A theory of the learnable. Communications the ACM, 27(1):11333 1142, 1984.
[VC71] V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264-280, 1971.
[VL.2]] Tom Viering and Marco Loog. The shape of learning curves: review. arXiv preprint arXiv:2103. 10948, 2021.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We have explained future research directions that will further improve this work, see Appendix A.3.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We have discussed that in Lines 405-408.
13

---

(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] We have specified the theoretical models we are working on, see e.g. Section 1.
(b) Did you include complete proofs all theoretical results? [Yes] Due to space con- straints we have included the full proof' of the results in the appendix/suppleeenntay material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals. applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "agsJuVFU_cz", "reviewer": "Reviewer_FfZM", "summary": "This paper studies the problem of multiclass classification with a bounded number of different labels. It mainly extends the main results of [1] and [2] to the multiclass case.\n\nFirstly, the paper provides a complete characterization of the achievable learning rates that holds for every fixed distribution in the universal learning setting and shows that for any concept class, the optimal learning rate is either exponential, linear or arbitrarily slow.\n\nSecondly, the paper considers the structured data, which is captured by partial concept classes proposed by [2].\n\n[1] Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon Van Handel, and Amir Yehudayoff. A theory of universal learning. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 532–541, 2021.\n[2] Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of pac learnability of partial concept classes. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 658–671. IEEE, 2022.", "questions": "1. As a theoretical work, some of the extensions in the paper just follow the standard idea that generalizing definitions from the binary case to multiclass case (For example, the extension from the Littlestone dimension to the multiclass Littlestone dimension is similar to the standard extension from the VC dimension to the Natarajan dimension. It is similar for the definition of NL tree) and the main results are very similar to those in [1] and [2], hence I have some concerns regarding the technical novelty of this paper. I would appreciate it If the authors can list out some techniques that do not appear in [1] or [2], except for the old-fashioned generalization trick mentioned above. I may adjust the rating according to the quality of the list.\n2. Since some characterizations of hypotheses may be very intractable when we extend the binary setting to the multiclass setting. For example, we can exactly calculate the VC dimension of linear binary classifiers, yet we can only bound the order of Natarajan dimension of linear multiclass clasifiers. As a result, I am wondering the practicality of the proposed definitions. Specifically, is it traceable to calculate the Natarajan/multiclass Littlestone tree of some common multiclass hypothetical classes, e.g. linear multiclass classifier class? \n\n\n[1] Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon Van Handel, and Amir Yehudayoff. A theory of universal learning. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 532–541, 2021.\n[2] Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of pac learnability of partial concept classes. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 658–671. IEEE, 2022.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper extends the main works of [1] and [2] to multi-class classification case. The total work has a good contribution to introducing new frameworks beyond the PAC framework in the multiclass setting. I do like the definition of Natarajan-littlestone tree, which is used to generalize the main results of universal learning framework to the multiclass setting.\n3. This paper describes the technique overview and proof sketches to help understanding the main tools and techniques used in this paper.\n\nWeaknesses:\n1. Some proofs of the main results, e.g. results in Section 1.3, seem to be an adaption of that in [2], except for the difference between the binary setting and multi-class setting. Hence I have some concerns regarding the novelty of this paper.\n\n\n[1] Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon Van Handel, and Amir Yehudayoff. A theory of universal learning. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 532–541, 2021.\n\n[2] Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran. A theory of pac learnability of partial concept classes. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 658–671. IEEE, 2022.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "U9ek9M0M6S-", "reviewer": "Reviewer_EhpP", "summary": "The authors relax multiclass PAC learning in two directions:\n1) Allow the sample complexity to depend on the distribution (whereas in classical PAC learning the sample complexity shall hold for _all_ distributions over the domain).\n2) Allow hypotheses to be partial functions, i.e. be defined not everywhere in the domain (in contrast to the classical PAC, where hypotheses must always be total functions).\n\nIn direction 1), which the authors call the theory of _universal_ learning, the work of [Bousquet et al. (STOC 2021)](https://dl.acm.org/doi/abs/10.1145/3406325.3451087) is generalized from binary to multiclass classification, namely:\n- The learning rate trichotomy is shown: learning occurs either at an exponential or linear or arbitrarily slow rate (in sample size).\n- Characterization of learnability in terms of Littlestone and Natarajan-Littlestone trees is given.\n- The optimal algorithms for each of the learning rates are presented, while they are not ERMs.\n\nIn direction 2), which the authors refer to as the PAC theory of learnability of _partial_ concept classes, the authors generalized the work of [Alon et al. (FOCS 2021)](https://ieeexplore.ieee.org/abstract/document/9719837) again from the binary case to the multiclass one:\n- The definition of the Natarajan dimension in the case of partial classes is introduced, and through it a characterization of the learnability of partial classes and (lower & upper) bounds on sample complexity are given.\n- It is shown that the learnability of a partial class $\\mathbb{H}$ does not imply the learnability of a total class $\\bar{\\mathbb{H}}$ that _disambiguates_ $\\mathbb{H}$.\n- The connection between $k$-class partial learnability and $(k + 1)$-class total learnability (when the value \"undefined\" is treated as an additional label) is established.", "questions": "Have you tried to find a less obfuscated partial class to prove Theorem 16? Your class relies on the class from Alon et al. (2021), which in turn relies on the superpolynomial separation between the chromatic number and the biclique partition number, which in turn is based on a series of 4 reductions in graph theory and complexity theory ...", "limitations": "Understanding the paper requires familiarity with the two previous works on which it is based (and beyond).", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n\n- A solid work that generalizes the recent two theories from the binary case to the multiclass one. That said, these two recent theories were built in an attempt to bridge the gap between learning theory and applied machine/deep learning practices.\n\n*Weaknesses*\n\n- I am most concerned about the presentation of the material: the density of the narrative is highly heterogeneous throughout the text of the paper. The introduction is well-written, and the motivation of the two proposed theories is immediately clear to the reader. The part about the universal theory of learning is already denser, and by the end of this part it is already difficult to understand what is at stake without looking into the Appendix and googling. The part about partial classes is the most dense, and I personally had to familiarize myself with the binary case first (Alon et al., FOCS 2021) before I could understand anything in this part. My impression is that this submission is an attempt to compress a journal article to the size of a conference paper, and the compression was done very unevenly.\n- Although both theories try to fill the gap between the theory and practice of machine learning, I honestly did not understand the connection of one theory with another. More precisely, I can imagine a setup where both theories are combined, but this will be a separate framework.\n- In the theory of partial classes, (yet) there is no such simple and clear principle as ERM (This is more about the original work of Alon et al. (2021), but nonetheless). I understand that (for example) in applied deep learning, SGD is not an arbitrary ERM. But after all, SGD is ubiquitous and extremely successful _approximate_ ERM in deep learning. If this theory claims to be an extension of the classical PAC theory explaining modern learning phenomena, I would like to have a simple and understandable learning principle (rather than resorting to improper learning with a transductive algorithm).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MIgl4PBXcNQ", "reviewer": "Reviewer_XbtE", "summary": "This paper considers an extension of the work by Bousquet, Hanneke, Moran, Van Handel, and Yehudayoff on universal learning, and the work by Alon, Hanneke, Holzman, and Moran on the partial concept classes to the multiclass classification problems. \nIn the first part of the paper, the authors consider the same setting as in the universal learning paper, and aim for finding the distribution-dependent rates for the decay of the risk. Similar to the universal learning paper, they show that a trichotomy occurs. More precisely, they show that by replacing the VC dimension with the Natarjan dimension in the universal learning paper, one can prove similar results.\nIn the second part of the paper, the authors consider the problem of partial concept classes. In this section, the authors, by recent results on the performance of the one-inclusion graph algorithm for multi-class problems, propose a learning algorithm for partial concept classes. More precisely, they show that the learnability in this setting can be identified by natural extension of Natarjan dimension to partial concept classes.\n", "questions": "1- The authors should discuss why they do not consider other dimensions such as Graph dimensions, the Pseudo-dimension, etc. \n\n2- What are the obstacles for obtaining the high probability versions of the bounds for the universal learning problems?\n\n3- Is the dependence of your results on the number of classes optimal? In light of recent results for infinite classes in characterization of multiclass learnability by Brukhim, Carmon, Dinur, Moran, and Yehudayoff, how can one extend the results to infinite classes?\n\n4- For partial concept classes, in prop 2 the authors provide a sufficient condition for success of ERM. How about the necessary condition? \n\n5- In the partial concept classes paper, the authors also present results for the agnostic case. What are the obstacles for proving such a result in the multi-class setting?\n \n", "limitations": "The authors provide a list of open problems and future directions.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In general, I find this paper very interesting. To me, it seems that the authors follow very closely the results in “a theory of universal learning “ and “A Theory of PAC Learnability of Partial Concept Classes “ to obtain the results. I think this does not affect the quality of the paper. Having said that, I think the authors should discuss with more details the new ideas and techniques beyond the existing ones that they use in the paper. I have checked the proof of the learning algorithm for the partial concept classes, and it follows very closely from the existing results. Therefore, I think 1) the authors should highlight the technical challenges for extending the existing techniques, 2) the authors should discuss why the other dimensions instead of Natarjan dimensions such as graph dimension do not work for these problems.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept