Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The authors aim to establish the equivalence of multiple loss functions in training and to analyse the conditions for benign overfitting in the rigime of multiclass classification. The paper proposes a crucial condition under which the solutions of multiclass SVM, one-vs-all SVM and min-norm interpolating (MNI) classifier are equivalent. It is proven that this condition holds in high probability in both Gaussian mixture model and multinomial logistic model. Finally, the paper gives the genalization bound of the MNI classifier based on its equivalence with SVM, as well as the condition for benign overfitting.
main_review: ## Originality
Although the paper applies some techniques of former work, it is the first to propose a sufficient condition for the equivalence of multiclass SVM and the MNI classifier and the generalization of the MNI classifier.
## Quality
The analysis in the main body of the paper is strong and convincing. However, the authors claim in the introduction part that **square loss is equivalent or even superior to cross-entropy loss**. The main body only proves the equivalence of the loss based on margin and the square loss. Cross-entropy loss, which is deserves more concern as a common choice in deep learning, is not sufficiently discussed.
## Clarity
The paper is well organized from the equivalence of SVM and MNI to the generalization of MNI and benign overfitting. Readers may find it easy to follow the flow.
## Significance
This paper studies benign overfitting for the task of multiclass classification, which is an important topic that has not been touched upon. The paper would be of much more significance if cross-entropy loss were carefully studied.
limitations_and_societal_impact: This part does not apply to this paper.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: “Benign overfitting” is a recently revealed phenomenon that high-dimensional models achieving zero training loss can still have good generalization. Existing works studying benign overfitting are mostly focused on the regression setting or the binary classification setting. In this paper, the authors establish benign overfitting guarantees for multi-class classification problems. It is shown that empirical risk minimization with cross-entropy loss is equivalent to the min-norm interpolating (MNI) solutions and the one-vs-all SVM classifier, and then derive error bounds on the accuracy of the MNI classifier. 
main_review: I think the analysis in this paper is interesting. Although I did not fully check all the proofs, the results in this paper seem to be sound. However, I have the following concerns about this paper.

- I am not sure if the results in this paper are novel enough. In fact, the difference between this paper and previous works, i.e., multi-class classification versus binary classification, may be quite incremental. The proof technique in this paper seems to be quite similar to previous works on binary classification as well. Moreover, it is in fact not very clear whether there is any advantage of using the multi-class cross-entropy loss. It seems that if one solves multiple binary classification problems separately, and derive error bounds using the results in [WT20], the result could be better: the (k-1) factor in the bound of Theorem 5 won’t change, and the k in the bound will simply be improved to a constant. For these reasons, I feel that the contribution of this paper may be limited to the extension to the multinomial logistic model.

- It is also not very convincing whether the conditions in Theorem 2 are tight in k. The condition p = \Omega(k^3 n) requires a very large dimension p, and since n is already the total number of training data (not the number of data per class), the dependency of p on k is quite bad. In the experiments in Figure 2, the authors only checked the tightness of the second condition in (16).

limitations_and_societal_impact: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the problem of multiclass classification in the overparameterized regimes. The work derives a sufficient condition under which multiple multiclass SVM classifiers converge to the min-norm interpolating (MNI) solution, extending a recent result ([MNS+ 20]) beyond the binary classification setting. The paper then shows that for certain configurations of the Gaussian mixture model and multinomial logistic model, this condition holds under high enough effective overparameterization. Finally, the paper derives non-asymptotic bounds on the error of the MNI classifier with multinomial logistic data and discusses sufficient conditions for the multiclass SVM to satisfy benign overfitting.

main_review: **Quality and Clarity**: 

- The paper is that it is very well-written and well organized. The ideas are presented clearly with intuitive explanations, and the proofs are rigorous. The authors are careful in evaluating the strengths/weaknesses of their work. The work seems to be built upon established literature and the review of related works is informative. 

- The technical parts of the paper are of very high quality


**Originality**: 

- The central part of the paper is built upon existing results for binary classification. All main messages of the work are affirmative answers to the main ideas outlined by [MNS+ 20] and [HMX20], i.e., in overparameterized regimes, all losses lead to the min-norm interpolating solution, and all data points are (in a sense) support vectors. 

- On the other hand, it is worth noting that several parts of the extension to multiclass are non-trivial (with varying degrees) and some require significantly new technical treatments:
   - The most important point of novelty of the paper is the derivation of Condition (8), which is a generalization of Equation (22) of [MNS+ 20]. For multiclass settings, the complementary slackness condition does not directly imply interpolation (as in the binary case) and the condition needs to be designed to ensure that a set of symmetric constraints also hold. Both the formulation and the technical proof of Theorem 1 are new and meaningful. 
   - The results of Theorem 2, 3, 4, 5, albeit are of high quality and are non-trivial, mostly follow the framework of [MNS+ 20] and [HMX20] with technical adjustments. 


**Significance**:

- As stated previously, all main messages of the work are affirmative answers to the main ideas outlined by [MNS+ 20] and [HMX20], thus the result themselves do not make as strong of an impact on the way people think about overparameterized regimes.

- The technical contributions of the paper are highly specialized to highly specific models of data (Gaussian mixture model with equal energy, Multinomial logistic model with orthogonal means). This lack of generality is likely to hinder the use of the work in more general settings. 

limitations_and_societal_impact: n/a
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors study benign overfitting in multiclass linear classification. They show the equivalence between one-vs-all SVM and multiclass SVM with either cross entropy or squared loss under a sufficient condition. Furthermore they show that when overparametrization occurs, the sufficient condition holds with high probability. 
main_review: The authors explore the literature of benign overfitting for multiclass classification. For this purpose they use SVMs.  They consider the space of linearly separable data. In particular they show that under a deterministic sufficient condition, one-vs-all  SVM, is equivalent to multiclass SVM classifier using both squared loss and cross entropy loss. This is the first case to show that these two loss functions can be equivalent. 

Furthermore, they show that for GMM or MLM, the aforementioned sufficient condition is satisfied with high probability under overparametrization based on the number of classes and quantities related to the data covariance. They also then provide experimental results to back up this claim. 

Moreover, they provide error bounds for data generated under these conditions. This shows that benign overfitting happens irrespective of the loss function chosen. 

After Rebuttal

Increased score after reading author response and other reviews. Please find the details in the comments.
limitations_and_societal_impact: I like this paper overall. Here are my main concerns
* The authors assume linearly separable data in the their work. However, that is not true in most cases. I would like to know about their thoughts regarding what would happen in such a case.
* Building on the previous question, I am wondering if it is possible to show some experimental results on non linearly separable data?
* Most of the classifiers use DNNs this days. It has been shown that the generalization for DNNs are very different from that of other classifiers. I am wondering if it possible to extend the results from this paper to DNNs. I would like to know the authors thoughts on this.
review_title: null

Meta-review: This paper proves the equivalence between multi-class logistic regression and multi-class SVM, based on which it proves the benign overfitting for multi-class interpolator. The main concern from one of the reviewers is that the results derived for multi-class benign overfitting are worse than using the standard technique (i.e., converting $k$-class classification to $k(k-1)/2$ 1 vs. 1 binary classification problems.) The authors have made a great effort to address the reviewers’ questions and concerns. After the author response and reviewer discussion, the paper gathers enough support from the reviewers. Thus, I recommend acceptance. 
Decision: Accept (Poster)