Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: As a purely theoretical work, this paper aims to study the generalization of overparameterized linear models (i.e. minimum-norm interpolator) for multi-class classification in an asymptotic setting where both the number of underlying features and the number of classes scale with the number of training points. Specifically, it considers a bi-level overparameterized linear model with a data generating model with Gaussian features (i.e., $1$-sparse noiseless model). Technically, the survival/contamination analysis framework is adapted to this setting with some novel arguments. Theoretically, the results offer several insights, especially showing that the multiclass problem is “harder” than the binary problem because there are fewer positive training examples per class.
strengths_and_weaknesses: I am not an expert in the area of overparameterized regimes and benign overfitting-related topics, but I think this work is solid based on my familiar related literature although I may not be familiar with some detailed techniques.

### Originality
The results for multi-class classification in an asymptotic setting are novel although the main techniques are adapted from the binary one [55]. Besides, it considers the asymptotic setting while the related work [75] considers the non-asymptotic setting.

### Quality
This work is of high quality and sound. Besides, it clearly discusses the difference with the related work [75,55]. I have not carefully checked the proofs and it seems sound. My main concerns are the connections (or insights ) of these theoretical results with the experimental phenomena. Besides, although this is a purely theoretical work, it is better to add some experimental results to support the theory. Moreover, this paper considers the overparameterized linear model, and the non-linear model setting (including deep neural networks) can be discussed more.

### Clarity
This paper is well written and organized.

### Significance
This work considers the generalization of the overparameterized linear model regime and should be of interest to the community of modern deep learning theory, which is fundemental in the understanding of the success of modern deep learning in practice.

questions: 1. Can the theoretical results be connected with some experimental phenomena in practice? Please give more discussions.
2. This work is the first one (as I know) to study the multiclass classification in an asymptotic setting, and it is enough to consider the overparameterized linear model. As for the non-linear model, more discussions can be added.
limitations: Although this is a purely theoretical work, it is better to add some experimental results to support the theory.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper derives scaling conditions under which the test error of min-norm interpolation for linear k-class classification goes to zero. The analysis is done for Gaussian features, a noiseless model with orthogonal 1-sparse "true" parameter vectors for each class and a bilevel covariance model. The derived scaling conditions are then used to compare k-class classification to binary and to regression.
strengths_and_weaknesses: Strenghts
-----------------------
* The paper is nicely written and relatively easy to follow 
* Good comparison to related work and contextualization of results
* Compared to previous work [55] on binary classification, new technical challenges arise in multiclass settings and the authors do a good job in explaining them, as well as, how they resolve
* Compared to previous work [76] on linear multiclass classification, the bounds have a tighter dependence on the number k of classes. In particular k is allowed to scale with n
* While I did not have time to check the proofs in details, the results appear correct 

Weakness
-------------------------
* The paper follows along the lines of recent line of work that compares classification to regression, but is not made clear what is it that we learn from this comparison.
* The discussion on interpretation of results + proof challenges is somewhat heavily using the notions of survival/contamination, which might make the presentation less accessible to wider audience (eg those not familiar with [55]). Perhaps at least define those? (hence "3" on Presentation)
* The model is quite oversimplified. While much related work uses Gaussianity, the 1-sparse assumption together with the bilevel ensemble appears more stringent. It is also somewhat disheartening that even in this setting, the full regime (Conjecture 6.1) is not characterized.

Overall, I value this a solid set of rather non-trivial result that continue recent investigations on overparameterized linear classification. While the set of tools and ideas is perhaps not particularly new (compared to eg [4,54,55,76]) there are certain non-trivial technical challenges that are being addressed
questions: * What do we learn from comparing regimes for classification and regression? To certain extent, the fact that classification is less challenging is somewhat to be expected. At the end of the day, the metrics are different, so what is the value of the comparison? Specifically, what is the lesson learnt (perhaps algorithmic?) by such accurate characterizations (in terms of the bilevel ensemble parameter) regimes? While I appreciate the hard work in deriving the bounds that lead to say Figure 2, could the authors comment on what (if any) the take-away message is (beyond multiclass can be harder than binary which can be harder than regression).

* Can the analysis be extended to other models? Eg logistic, Gaussian mixture etc? Could the authors comment on the possible challenges?
limitations: yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies the phenomena of benign-overfitting of interpolating minimum norm linear classifiers. The authors consider the case where the number of classes grows with the number of examples. They study a simplified case in which the ground-truth classifier is obtained by the weight matrix (I_k 0) and under the "bi-level ensemble" condition. The results show benign-overfitting can be achieved when the data contain a sufficient number of relevant features and a large number of irrelevant features, and the relevant features have a larger norm than the irrelevant ones.


strengths_and_weaknesses: Strength:
- The paper is well-written.
- The topic is relevant to the ML community.
- The results are, to the best of my knowledge, sound.

Weakness:
- The ground-truth model is simple, and it is unclear how to generalize it to more realistic models.
- The results are stated in the asymptotic regime where the number of examples approaches infinity.


questions: The 1-sparse noiseless model is very limiting. Do you think the results can easily be generalized to more general settings (e.g., the Gaussian mixture Wang let. al. [76] or general orthogonal matrix instead of (I_k 0) )?

Is it possible to provide finite-sample bounds on the probability of error?

limitations:
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors present a setup for multiclass classification with specific assumptions. It requires certain assumptions, e.g. the features are drawn from a gaussian distribution, the labels are a deterministic function of the dimension which has largest feature value. 

They consider a setup where certain parameters depend polynomially on the sample size, that is the number of dimensions, the number of upscaled dimensions, the number of classes and the feature weights. They present a theorem which shows that the generalization error goes asymptotically to zero for a certain relationship between these parameters.  

They show that for some settings multiclass classification converges, but regression does not, conditioned on the specific setup.
strengths_and_weaknesses: strength:
a novel theoretical result.

weaknesses: 
it is a very specific setting.
Readability of the paper is a bit challenging, though it comes from the complexity of the topic itself .
questions: Lemma B.1 is adapted from which result in Bartlett [4] ?
limitations: na
review_title: null

Meta-review: metareview: The paper makes a solid progress in our understanding of generalization in overpametrized models
confidence: Certain
Decision: Accept