where \(\mathrm {Ndim}(\mathcal {H})\)  stands for
the Natarajan dimension of \(\mathcal {H}\)  and \(\widetilde{\Theta }_{k}\)  subsumes dependencies on \(k\)  (the lower bound of order \(\mathrm {Ndim}(\mathcal {H})/n\)  is from [1]} and
the upper bound \(\mathrm {Ndim}(\mathcal {H}) \log (k)/n\)  comes from an application of the one-inclusion
hypergraph algorithm [2]}). In words, assume that \(n\) 
is the number of training samples and let \(\mathcal {H}\subseteq [k]^\mathcal {X}\)  be a set of multiclass classifiers mapping the elements of the domain \(\mathcal {X}\)  to \([k]\)  that the learner has access to. The learner observes \(n\)  labeled examples \((x,y) \in \mathcal {X}\times [k]\)  generated i.i.d. from some unknown distribution \(P\)  with the constraint that \(P\)  is realizable with respect to \(\mathcal {H}\) , i.e., there is some \(h \in \mathcal {H}\)  that has (almost surely) zero classification error. The learner then
outputs a guess hypothesis \(\widehat{h}_n : \mathcal {X}\rightarrow [k]\)  (potentially, without an explicit description). The fundamental theorem of PAC learning, as shown above, controls the expected error \(\mathop {\bf E}[ \mathrm {er}(\widehat{h}_n) ]\) , where \(\mathrm {er}(\widehat{h}_n) := \mathop {\bf Pr}_{(x,y) \sim P}[\widehat{h}_n(x) \ne y]\) , in a minimax sense, i.e., it controls the performance of the best algorithm \(\widehat{h}_n\)  (inf) against the worst-case realizable distribution \(P \in \mathrm {RE}(\mathcal {H})\)  (sup) and states that
the following dichotomy occurs: if the Natarajan dimension \(\mathrm {Ndim}(\mathcal {H})\)  is finite, the error rate decreases as, roughly, \(1/n\) , so \(\mathcal {H}\)  is PAC learnable at a linear rate; otherwise, the class \(\mathcal {H}\)  is not PAC learnable.
Additionally, this theory provides a clean algorithmic landscape: the ERM principle, which means outputting some classifier in \(\mathcal {H}\)  that best fits the training set, (roughly) achieves the rates of definition:multiclass pac learning.
