The PAC model [1]} constitutes the gold-standard learning framework.
A seminal result in learning theory [2]}, [3]} characterizes PAC learnability of
binary classes (\(k=1\) ) through the Vapnik-Chervonenkis (VC) dimension and provides a
clear algorithmic landscape 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 the number of classes
\(|\mathcal {Y}|\)  is bounded. The works of [4]}, [5]} and [6]}
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 for the expected prediction error)We mention that definition:multiclass pac learning essentially works in the probabilistic prediction model of [7]}. In this model, one does not require the hypotheses used for prediction to be represented in any specified way since the prediction for the test point \(x\)  is performed on the fly.
For instance, a valid classification rule
in this model is to memorize all the training points and
run an algorithm for every unlabeled instance \(x.\) 
In Valiant's PAC model,
we are interested in approximating a target hypothesis \(h \in \mathcal {H}\)  given an \(h\) -labeled sample and we must output a representation of a hypothesis in some hypothesis class \(\mathcal {F}\)  [7]}. Also, definition:multiclass pac learning deals with the expected error. To the best of our knowledge, in the realizable PAC learning setting with \(k\)  labels, the best upper bound for a high-probability result has an additional \(\log (n)\)  factor [9]}.
can be summarized in the following elegant equation for any \(n \in \mathbb {N}\) ,
which we explain right-after:
\(\inf _{\widehat{h}_n} \sup _{P \in \mathrm {RE}(\mathcal {H})} \mathop {\bf E}[\mathrm {er}(\widehat{h}_n)]= \min \left( \widetilde{\Theta }_{k}\left(\frac{\mathrm {Ndim}(\mathcal {H})}{n} \right), 1 \right)\,,\) 
