Lower Bounds for Multiclass Classification with Overparameterized Linear Models

Subramanian et al. [1] introduced an asymptotic Gaussian-features model for overparameterized multiclass classification in which the number of classes, training points, and parameters all go to infinity. They provided some achievable regions where min-norm interpolating classifiers successfully asymptotically generalize as well as conjecturing the full form of the region based on a heuristic analysis. Here, we introduce a converse for such min-norm interpolating classifiers in their model which fully matches their conjectured regions. The key technical tool is a variant of the Hanson-Wright concentration inequality that applies to the sparse bilinear forms that arise.