Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studied the classification error of max margin linear classifier in high dimensional Sub-Gaussian mixtures. Tight upper and lower bounds are derived, which generalizes the prior works on Gaussian Mixtures.

main_review: This paper studied the classification error of max margin linear classifier in high dimensional Sub-Gaussian mixtures. This is an important problem, due to its connection to the implicit bias of first order algorithms, interpolation and the double descent phenomena. 

Tight upper and lower bounds are derived, which generalizes the prior works on Gaussian Mixtures. Overall, this paper is well-written, the results are solid and I enjoyed reading it. A few comments are in order:

(1) It might be better to expand the prior works section to include some relevant papers on high dimensional Gaussian Mixture. For example, the exp(- |mu|^4/(|mu|^2+d/n)) -type risk bounds also appeared in high dimensional Gaussian clustering literature, e.g.

https://arxiv.org/pdf/1812.08078.pdf

https://arxiv.org/pdf/2006.14062.pdf

and many other references therein.



(2) A major limitation I see from this work, is that its analysis heavily relies on the equivalence between max margin classifier and min-norm interpolator, see [19]. As the authors already mentioned in this paper (e.g. corollary 3.3), for example, in the text book example of isotropic Gaussian mixture with a constant separation, this can only happen when d > n^2, or the number of samples n is at most sqrt(d). In contrast, the n/d = constant setting is much more standard, and in certain sense more interesting. In my opinion, the results in this paper are far from a complete picture about max margin classifier - In other words, they are really about min-norm interpolator, which happens to be equivalent to max-margin classifier in the small sample regime (and therefore the title is a little bit misleading). 

Overall, my recommendation is weak accept - any comments and clarifications from the authors are welcome.
limitations_and_societal_impact: -
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proves new risk bounds for overfitting in the over-parameterized linear classification setting when the data is generated by a sub-Gaussian mixture. In certain regimes, the results show that overfitting can be benign, that is, overfitting still leads to a good test error. An important property of the proposed upper bound on the risk is that it is not directly dependent on the dimension, but rather on certain norms of the covariance matrix. This is useful because, as shown in the paper, if the eigenvalues of the covariance matrix decay fast enough, then requirements for benign overfitting become dimension independent.
main_review: This paper proves new risk bounds for overfitting in the over-parameterized linear classification setting when the data is generated by a sub-Gaussian mixture. In certain regimes, the results show that overfitting can be benign, that is, overfitting still leads to a good test error. An important property of the proposed upper bound on the risk is that it is not directly dependent on the dimension, but rather on certain norms of the covariance matrix. This is useful because, as shown in the paper, if the eigenvalues of the covariance matrix decay fast enough, then requirements for benign overfitting become dimension independent.

This paper is good step towards understanding benign overfitting, even though the paper only considers linear classification in sub-Gaussian mixture setting. Corollary 3.5 proves that even if the eigenvalues of the covariance matrix do not decay very fast, the requirement for small test error scale sub-linearly with dimension. In particular, as long as the the number of samples is a large enough constant, and the means of the classes are separated by $d^{1/4}$, the risk of maximum margin classifier is $o(1)$. 

Overall, the paper is well written, and the usefulness of the theorem is well illustrated with examples. The intuition is explained well and the theorem proof in the main paper is also helpful.

My first concern about the results is that the requirement $\text{tr}(\mathbf{\Sigma})\geq C \max (n^{3/2}||\mathbf{\Sigma}||_2,n||\mathbf{\Sigma}||_F)$, which in the isotropic Gaussian case implies that the theorem requires $d\geq n^2$. Thus, the result is only applicable to extremely over-parameterized setting. Is this requirement a necessary condition for such results? In the mild over-parameterized setting (say $d\geq 100 n$), would overfitting no-longer be benign? This can be the case, for example, if we keep the data distribution fixed and keep increasing the number of samples $n$.

Another concern that I have is whether these results can be transferred to the setting of deep learning. In the linear classification setting considered in this paper, the results are essentially for the maximum margin classifier, with the motivation being that asymptotically, SGD converges to the maximum margin classifier. This is not the case for deep learning, where if we just benignly overfit the data, then there still are adversarial examples. Hence, overfitting in deep learning does not lead to maximum margin classifiers usually. Given that benign overfitting still leads to a good test accuracy for deep networks, an important question is whether the explanation offered by this paper is still valid for deep learning.
limitations_and_societal_impact: Please see the main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies risk bounds for the hard-margin SVM binary classification problem in the over-parametrized regime, where the number of samples is much smaller than the dimension of the instance space. It is assumed that the samples follow a distribution corresponding to a mixture of two sub-gaussian components, one component for each label. These components are assumed to have the same covariance matrix Sigma and opposing means mu and -mu. The main results of the paper are upper and lower bounds for the risk of the SVM classifier as trained on the data. By previous results, this also has implications to the minimum norm solution learned by gradient decent. The derived bounds are tighter than previous bounds and extend to the anisotropic setting. The lower bound derived matches the upper bound in some regimes of the parameters, suggesting optimality. They also discuss in some detail the role played by the eigenvalues of Sigma in the risk bounds, showing a nice separation to two regimes.
main_review: The paper is well written and easy to follow and the results seem technically correct. The results, however, are somewhat incremental as compared to previous work on the subject, hence my relatively low score.

Some questions/comments: 

- In the introduction, the results are presented without the dependence on $\Sigma$, stating rates that are not scale invariant as one would expect.

- You assume that the distribution is centered. How does your bounds change when one also needs to estimate the center of the mixture, or equivalently, learn an additional bias parameter in the SVM classifier.

- Please give the formal definition of the sub-gaussian/exponential norms, or at least state an appropriate reference where they are mentioned (line 104).

- Is the condition $||\mu||_2 \geq C||\Sigma||_2$ in Lemma 4.4 correct? It is not scale invariant.

limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 9: Top 15% of accepted NeurIPS papers, strong accept
review_content: summary: The paper studies maximum-margin classifiers in the setting where the dimension of the data is much larger than the number of samples. This data is assumed to come from a mixture of two subgaussians under a standard generative model. Notably, prior work shows that max-margin classifiers (i.e. Support Vector Machines) return the same estimator as the minimum-norm solution to an underconstrained least squares problem. The research mostly pertains to analyzing that least squares solution.

The paper focuses on providing sharper guarantees on when exactly the SVM is equivalent to the LS solution, and when this LS solution has low risk/misclassification probability. Their guarantees depend exclusively on the sub-gaussian data's true covariance matrix, the distance between the two subgaussian modes, and the number of samples. Notably, this does *not* depend explicitly on the dimension of the data. So, we can better understand how the spectrum of the covariance matrix impacts the misclassification probability.

Some complementary lower bounds are given.
main_review: ### Overall Impression
This paper was a pleasure to read, and I confidently recommend it for publication.
Further, I verified much of the math in the appendix and found no errors.

### Detailed Review

The setting of the paper is interesting. The focus on characterizing as-much-as-possible in terms of the covariance matrix is solid and pays off well. The structure of the paper is very clear and easy to read, providing intuitive interpretations of the core theorems along with a high-level overview of the proof.

The background information in the introduction is also well presented. While I am familiar with all the technical tools used in this paper, I had not read papers on benign overfitting in the past. Nevertheless, I was able to quickly understand the core ideas and felt comfortable reading this paper.

I do have some questions and feedback for the authors:
1. How fundamental is the covariance matrix's trace lower bound assumption(s)? You mention that the core theorems only assume the trace is large enough, but that the risk bound itself does not depend directly on this trace. Do we have reason to think this trace assumption is fundamental or necessary? Of all metrics, why is trace meaningful here?
1. Intuitively parse the hard constraints on the trace of the covariance matrix in Theorem 3.1 [Line 167]. What kinds of covariance matrices fail this check? Do they have a flat spectrum? Does the sample complexity $n$ limit how flat the spectrum can be? [Lines 209 - 233] get close to discussing this, but fall short of explaining what covariance matrices / sub-gaussian structures fail this test, and how that depends on $n$.
    - For example, Theorem 3.1 requires $n \leq \frac{tr(\Sigma)}{\\|\Sigma\\|_F}$ amongst other constraints. Is this a reasonable way to interpret the hard constraint? What does this really say about $\Sigma$?
1. Consider removing the line about logistic regression from your abstract. You don't really provide any new guarantee there.
1. You should mention in the body of the paper that there are experiments in the appendix.
1. The appendix is ordered in a hard-to-read way. I constantly found myself flipping back-and-forth between pages to remember what Lemma X.X refers to. Further, finding the proof of a specific lemma takes a while. Lastly, the order of proofs makes it hard to jump to the proofs that interest me. I would recommend a few changes:
    - At the beginning of *every* proof in the appendix, fully restate the lemma/theorem/corollary.
    - When you state a lemma without proof, link to its proof.
    - List all defined symbols at the beginning or end of the appendix. There's a lot of symbols, and some like $\varepsilon_\lambda$ are defined within some lemma statements, which is easy to skip over on accident.
    - Consider just reordering the entire appendix to be fully bottom-up? Just start with the lemmas that requires no other lemmas, and build up from there?
1. All experiments in this paper would benefit from error bars. Consider highlighting the area between $25^{th}$ and $75^{th}$ quartiles on each plot? Figure 2(d) at $\\|\mu\\|_2^2 = 4,6$ might be a bit non-linear, and some error bars would dissuade my concern, for example. It would also resolve the weird bump at $\\|\mu\\|=2,\alpha=0.8$ on Figure 2(b).

Some typos and smaller confusions:
1. [Line 64] "our result shows that to achieve $o(1)$ population risk" If $n$ is constant, what is this little-o depending on? $d$?
1. [Line 293] The details are in Appendix A.1, not Appendix 4.1.
1. [Line 319] Consider trying to unify the $Q=Z\Lambda^{1/2}V^\intercal$ notation with the content of [Line 120]. Maybe introduce the $Z$ notation there as an equivalent characterization? It's a little confusing as written, since this notation hasn't been introduced earlier, so it takes extra effort to verify. It would be more clear if I thought about this characterization when $Q$ was first defined and fresher in my memory.
1. [Line 605] Consider justifying $\\|\mu\\|_2^2 \geq \mu^\intercal Q^\intercal (QQ^\intercal)^{-1} Q\mu$, which I believe follows from $Q^\intercal (QQ^\intercal)^{-1} Q$ being a hat matrix?
1. [Line 612] I don't think $v_i$ was defined anywhere.
1. [Line 642] Unmatched parenthesis in the definition of $J_2$.
1. [Line 733] "the dependency of" should be removed
1. [Line 747] Should read "holds" not "hold"
limitations_and_societal_impact: The limitations discussed are fine and sufficient. Admittedly, they are not particularly creative or interesting.

Societal Impact: Not applicable.
review_title: null

Meta-review: This paper is favored by two reviewers and is acceptable by all. Reviewers agree that it is clearly written and organized, even enjoyable to read, and that the results are solid on their own. Throughout the various exchanges between reviewers and authors, some valid suggestions emerged that may strengthen the paper, for instance:

* Discussing the possibility that d > n^2 is required and situating that relative to assumptions in related work (from discussion with GwQP and nXks), namely highlighting the sense in which this is comparatively mild.

* Considering commenting on how to approach an extension to data that is not centered (from discussion with 1YJ4). This may be more of an optional suggestion, but again may be useful to understanding the setup and analysis.

Overall the paper makes a number of technical contributions to the actively developing topic of studying benign overfitting. Together with mostly favorable reviews, I recommend it for acceptance.
Decision: Accept (Poster)