The aim of this paper is to develop (i) a distribution-dependent learning theory for multiclass classification and (ii) a learning theory for partial multiclass concept classes in the distribution-independent settingWhile we believe that one could design a unified learning theory addressing the two questions at once, we prefer to provide two separate theories, since they are both interesting in their own.. We comment that we focus on the realizable setting that already poses important challenges and requires novel ideas and we believe that our results can be extended to the agnostic case, which is left for future work. We remark that such theories for binary classification were recently developed [1]}, [2]}. However, in various practical applications, such explanations may not suffice,
since it is rarely the case that there are only two classes. As it is already evident from the PAC setting, moving from binary classification to multiclass classification is not trivial [3]}.
We now discuss obs1 and REF ; we underline that our goal is not to replace, but to build upon and complement, the traditional PAC model, which constitutes the bedrock of learning theory.
