We denote with \(O_k(1)\)  a constant that depends on \(k.\) 
Via theorem:partial-pac-learning, the above partial class \(\mathcal {H}\)  is PAC learnable; however, any disambiguation of \(\mathcal {H}\)  causes a blow-up to the Natarajan dimension.
This result showcases the complexity of partial concepts. We briefly outline
the main technical contributions in this regime: we extend the main
results of [1]} for binary classification to the
multiclass setting using appropriate complexity measures. Recall that the combinatorial Sauer-Shelah-Perles (SSP) lemma [2]}, [3]} bounds the size of a (total) class \(\mathcal {H}\subseteq \lbrace 0,1\rbrace ^n\)  by \(\sum _{i = 0}^{\mathrm {VC}(\mathcal {H})} \binom{n}{i}\) . Notably, [1]} showed that this lemma does not hold true for partial concept classes. To obtain our disambiguation result, we prove that the second variant of the SSP lemma, which uses the growth function of the class [3]}, does hold in the partial regime, which may be of independent interest.
