Generalization for multiclass classification with overparameterized linear models
Via an overparameterized linear model with Gaussian features, we provide
conditions for good generalization for multiclass classification of
minimum-norm interpolating solutions in an asymptotic setting where both the
number of underlying features and the number of classes scale with the number
of training points. The survival/contamination analysis framework for
understanding the behavior of overparameterized learning problems is adapted to
this setting, revealing that multiclass classification qualitatively behaves
like binary classification in that, as long as there are not too many classes
(made precise in the paper), it is possible to generalize well even in some
settings where the corresponding regression tasks would not generalize. Besides
various technical challenges, it turns out that the key difference from the
binary classification setting is that there are relatively fewer positive
training examples of each class in the multiclass setting as the number of
classes increases, making the multiclass problem "harder" than the binary one.