Definition 4 (Multiclass Partial PAC Learnability [1]}) 

A partial concept class \(\mathcal {H}\subseteq \lbrace 0,1,...,k,\star \rbrace ^\mathcal {X}\)  is PAC learnable if for every \(\epsilon , \delta \in (0,1)\) , there exists a finite \(\mathcal {M}(\epsilon , \delta ) \in \mathbb {N}\)  and a learning algorithm \(\mathbb {A}\)  such that, for every distribution \(P\)  on \(\mathcal {X}\times \lbrace 0,1,...,k\rbrace \)  realizable with respect to \(\mathcal {H}\) , for \(S \sim P^{\mathcal {M}(\epsilon , \delta )}\) , it holds that
\(\mathop {\bf Pr}_{S} \left[ \mathrm {er}_P(\mathbb {A}(S) ) \le \epsilon \right] \ge 1-\delta \,.\) 
The sample complexity of \(\mathbb {A}\)  is the value \(\mathcal {M}(\epsilon , \delta )\)  and the optimal sample complexity is the minimum possible value of \(\mathcal {M}(\epsilon , \delta )\)  for any given \(\epsilon , \delta \) .

