For the upper bound, we have to employ the one-inclusion hypergraph algorithm (see appendix:one-inclusion). Following the methodology of [1]}, we extend its guarantees (which hold for total concept classes) to the partial setting. This algorithm guarantees an expected error which can be boosted to a high probability result using standard concentration and boosting techniques. To show that the partial concept class \(\mathcal {H}\subseteq \lbrace 0,1,...,k,\star \rbrace \)  is not learnable if it has infinite Natarajan dimension, we reduce the problem to classification with total concepts and invoke the existing (standard) lower bound. The main take-away from theorem:partial-pac-learning-sc is that the algorithmic landscape of partial concept classes is provably elusive, as already indicated by the seminal work of [1]}. To this end, we provide a second result that shows when one can apply the well-understood ERM principle (which is valid when the number of labels is bounded) with partial concepts. For details, we refer to theorem:equivalence-total-partial. To conclude, we address the task of disambiguation [3]}, [1]} of partial concepts (see definition:disambiguation). Our proof of theorem:disambiguation-inf relies on an interesting observation: the seminal work of [1]} showed that the combinatorial variant of the SSP lemma [6]} does not hold in this setting. This lemma has a second variant that uses the growth function [7]} instead of the size of the class. We show that a natural extension of this variant for partial classes is still correct (see lemma:ssp).
Using this tool and techniques from [1]}, we obtain our impossibility result.
