Classification with multiple labels is extensively studied and, for the setting with bounded \(k\) , PAC learnability is well-understood [1]}, [2]}, [3]}, [4]}. The works of [5]}, [6]} provide a fundamental dichotomy/equivalence between the finiteness of the VC dimension and binary classification (PAC learnability). [7]} and [1]} extend the PAC framework to the multiclass setting by providing the notions of the Graph and the Natarajan dimension. When the number of labels \(k\)  is a finite constant, then these two dimensions both characterize PAC learnability since \(\mathrm {Ndim}(\mathcal {H}) \le \mathrm {Gdim}(\mathcal {H}) \le \mathrm {Ndim}(\mathcal {H}) \cdot O(\log (k))\)  [4]}. Afterwards, [2]} and [11]} provide a combinatorial abstraction which captures as special cases e.g., the Graph and Natarajan dimensions and Pollard's pseudo-dimension. In this general setting, [2]} identify the notion of \(\Psi \) -distinguishers that characterize PAC learnability when \(k\)  is bounded.
More to that, uniform convergence still applies when the number of classes is bounded and, so, PAC learning provides the ERM principle for algorithm design. We remark the situation gets much more complicated when the number of labels is not bounded [13]}, [14]}, [15]}, [4]}. For instance, [13]} show that the ERM principle does not apply in this case. In a recent breakthrough, [14]} show that the DS dimension captures learnability and the Natarajan dimension provably fails to achieve this.
