Our work provides two theoretical perspectives complementing and extending the standard multiclass PAC learning.
For the universal rates, the seminal work of [1]} provided a similar trichotomy for the binary setting (we obtain their results by setting \(k=1\) ). The gap between exponential and linear rates was studied by [2]} in some special cases. Also, [3]} 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.
In the exponential rates setting, a first idea would be to consider for the class \(\mathcal {H}\subseteq [k]^\mathcal {X}\)  the binary restrictions \(\mathcal {H}|_i = \lbrace  h_i : h \in \mathcal {H}\rbrace ,\)  where \(h_i\)  denotes the \(i\) -th bit of the output of \(h\) . In order to obtain the desired result for exponential rates, one has to prove that if \(\mathcal {H}\)  does not have an infinite multiclass Littlestone tree, then every \(\mathcal {H}|_i\)  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 [1]}. We note that the existence of multiple labels requires various novel ideas compared to the binary setting. We introduce novel Gale-Stewart games (see algorithms:universal1, algorithms:universal2) 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 a sufficient condition for learnability at a 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). In general, the idea of “universal learning” has been studied in various concepts such as universal consistency [5]}, [6]}, [7]}, [8]}, [9]}, [10]}, [11]}, [12]}, [13]} and active learning [14]}, [15]}, [16]}, [17]}. For an extended discussion, we refer to [1]}.
For the partial concepts setting, our work builds on the seminal work [19]} and uses tools from [20]}. The work of [19]} 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 [22]}, [23]}, [24]}, [20]} which we define formally in appendix:one-inclusion, the Sauer-Shelah-Perles lemma [26]} and recent breakthroughs in the intersection of graph theory and complexity theory concerning the Alon-Saks-Seymour problem [27]}, [28]}, [29]}, [30]}, [31]}, [32]}, [19]}, [34]}.
