Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures
Authors: Yuan Cao
Quanquan Gu
Misha Belkin
Venue: NeurIPS 2021 Poster (2021)
Keywords: maximum margin classification
over-parameterization
benign overfitting

Abstract: Modern machine learning systems such as deep neural networks are often highly over-parameterized so that they can fit the noisy training data exactly, yet they can still achieve small test errors in practice. In this paper, we study this "benign overfitting" phenomenon of the maximum margin classifier for linear classification problems. Specifically, we consider data generated from sub-Gaussian mixtures, and provide a tight risk bound for the maximum margin linear classifier in the over-parameterized setting. Our results precisely characterize the condition under which benign overfitting can occur in linear classification problems, and improve on previous work. They also have direct implications for over-parameterized logistic regression. 

Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures
Yuan Cao
Quanquan Gu
Department of Statistics & Actuarial Science Department of Mathematics The University of Hong Kong yuancaoOhku.ht hk
Department of Computer Science University of California, Los Angeles Los Angeles, CA 90095, USA qguêcs ucla, edu
Mikhail Belkin
Halicioglu Data Science Institute University California San Diego La Jolla, CA 92093, USA mbelkin@ucad.cem
Abstract
Modern machine learning systems such as deep neural networks are often highly wverppaametterized that they can fit the noisy training data exactly, yet they can still achieve small test errors in practice. In this paper, we study this "benign overfitting" phenomenon of the maximum margin classifier for linear classification problems. Specifically, we consider data generated from sub-Gaussian mixtures, and provide tight risk bound for the maximum margin linear classifier in the over parameterizeed setting. Our results precisely characterize the condition under which benign overfitting can occur in linear classification problems, and improve on previous work. They also have direct implications for over-parameterized logistic regression.
Introduction
In modern machine learning, complex models such deep neural networks have become increasingly popular. These complicated models are capable of fitting noisy training data sets, while at the same time achieving small test errors. In fact, this benign overfitting phenomenon is not unique feature of deep learning. Even for kernel methods and linear models, [5] demonstrated that interpolators on the noisy training data can still perform near optimally the test data. A series of recent works [4, 20, 11, 2] theoretically studied how wer-parameterizztton can achieve small population risk.
In particular in [2] the authors considered the setting where the data generated from ground-tree -ruth linear model with noise, and established a tight population risk bound for the minimum norm linear interpolator with matching lower bound. More recently, [23] further studied benign overfitting in ridge regression, and established non-asymptotic generalization bounds for over-parametrized ridge regression. They showed that those bounds tight for range of regularization parameter values. Notably, these results cover arbitrary covariance structure of the data, and give a nice characterization of how the spectrum of the data covariance matrix affects the population risk in the perapmaramtterieed regime.
Very recently, benign overfitting has also been studied in the setting of linear classification [6. 19, 25]. Specifically, [19] studied the setting where the data inputs are Gaussian and the labels are generated
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

from a ground truth linear model with label flipping noise, and showed equivalence between the hard- margin support vector machine (SVM) solution and the minimum norm interpolator to study benign overfitting. [6, 25] studied the benign overfitting phenomenon in Doo--GausinnnGauusiia mixture models and established population risk bounds for the maximum margin classifier. [6] leveraged the implicit bias of gradient descent for logistic regression [22] to establish the risk bound. [25] established an equivalence result between classification and regression for isotropic Gaussian mixture models. While these results have offered valuable insights into the benign overfitting phenomenon for (sub-) Guu-)Gaassiian mixture classification, they still have certain limitations. Unlike the results the regression setting where the eigenvalues of the data covariance matrix play key role, the current results for Gaussian/sub- naussian/sbb-Gausiian mixture models do not show the impact of the spectrum of the data covariance matrix on the risk.
In this paper, we study the benign overfitting phenomenon in a general sub-Gaussian mixture model that covers both the isotropic and anisotropic settings, where the d-dimensional features from two classes have the same covariance matrix Σ but have different means μ and - respectively. We consider the over-parameterized setting where d is larger than the sample size n, and prove a risk bound for the maximum margin classifier. We show that under certain conditions on eigenvalues of Σ, the mean vector 4 and the sample size the maximum margin classifier for this problem is identical to the minimum norm interpolator. We then utilize this result to establish a tight population risk bound of the maximum margin classifier. Our result reveals how the eigenvalues of the covariance matrix Σ affect the benign property of the classification problem, and is tighter and more general mixture models. The contributions of this paper
than existing results uub-Gaussian/Gain as follows:
We establish tight population risk bound for the maximum margin classifier. Our bound works for both the isotropic and anisotropic settings, which is more general than existing results in [6, 25].
When reducing our bound the setting studied in [6], our result gives bound exp(-S((n) | / /d)). where n is the training sample size. Our bound is tighter than the risk bound
/2) in
[6] by factor of in the exponent. Our result also gives a tighter risk bound than that in [25]' in the so-called "low SNR setting": our result suggests that || w(d/n) suffices to ensure an
o(1) population risk, while [25] requires || = ((d/n)88/)
We establish population risk lower bounds achieved by the maximum margin classifier under two different settings. In both settings, the lower bounds match our population risk upper bound up to some absolute constants. This suggests that our population risk bound is tight.
Our analysis reveals that for class of nigh-dimensional amisotropic nab-Gaussian mixture models, the maximum margin linear classifier on the training data can achieve small population risk under mild assumptions on the sample size and mean vector μu. Specifically, suppose that the eigenvalues of Σ are (Ae = k- === for some parameter E [0, 1), and treat the sample size as constant. Then our result shows that to achieve o(1) population risk, the following conditions on ||//|/2 suffice:
w(dl/4-0/2) ((lg(()))) w1).
if (0,1,2), if a = 1/2, if E (1/
||al|22 =
More specifically. when a 1/2. the condition on the mean vector 4 only has logarithmic dependency on the dimension d, and when E (1/2, 1), the condition on fa for benign overfitting is dimension free.
Our proof of the population risk bound introduces some tight intermediate results, which may be of independent interest. Specifically, our proof utilizes the polarization identity to establish equivalence between the maximum margin classifier and the minimum norm interpolator. This is, to the best of our knowledge, the first equivalence result between classification and regression for anisotropic sub-Gaussian mixture models.
Additional Related Work Our study is closely related to the phenomenon of double descent studied recent works. [3, 4] showed experimental results and provided theoretical analyses on some
I After we posted our paper on arXiv, we noticed that the authors of [25] updated their paper a week later to include the results for mixture of anisotropic Gaussians and sharpened their bounds. Our results are still more general as covered the mixture of anisotropic Gau-Gausiinn, and we also proved matching lower bound.

---

specific models to demonstrate that the risk curve versus over parameterizationn has a double descent shape. These results can therefore indicate that over-varamann paraaeterizziioonn can be beneficial achieve small test risk. [11, [1] studied the double descent phenomenon in linear regression under the setting where the dimension and sample size can grow simultaneously but have fixed ratio, and showed that the population risk exhibits double descent curve with respect to the ratio. More recently, [17, 15, 18] further extended the setting to random feature models and studied double descent when the sample size, data dimension and the number of random features have fixed ratios.
Our work is also related to the studies of implicit bias, which analyze the impact of training algorithms when the over- parameterized models have multiple global minima. Specifically, [22] showed that if the training data are linearly separable, then gradient descent on unregularized logistic regression converges directionally to the maximum margin linear classifier on the training data set. [13] further
studied the implicit bias of gradient descent for logistic regression on non-separable data. [9] studied the implicit bias of various optimization methods for generic objective functions. [10, 1] established implicit bias results for matrix factorization problems. More recently, [16] showed that gradient flow for learning homogeneous neural networks with logistic loss maximizes the normalized margin on the training data set. These studies of implicit bias offer a handle for us to connect the aver-parameterized logistic regression with the maximum margin classifiers for linear models.
2 Problem Setting and Notation
Notations. We use lower case letters denote scalars, and use lower/upper case bold face letters to denote vectors/matrices respectively. For vector we denote by ||v|12 the f--norm of v. For matrix A, we use ||. ||
denote its spectral norm and Frobinuous norm respectively, and use tr(A) to denote its trace. For a vector E I and positive definite matrix A, we define ||v]|A = vv Av. For an integer ni, we denote [n] = 21,,2....,..
We also use standard asymptotic notations O(-), (?(), o(-), and w(-). Let {an} and {6,} } be two sequences. If there exists a constant C' > 0 such that |a,l S Clbul for all large enough n, then we denote a, (b²)). ). We denote On = (bb,)) if 6, O(az). Moreover, we write an o(b,) if lim /b, 0 and a. wbb,) if lim a,,/bb. = We also use Ō(-) and 52(.) to hide some logarithmic terms in Big-O and Big-Omege notations.
At last, for random variable Z, we denote by || and | the Lub-Gaussian and sub- exponential norms of Z respectively.
Sub-Gaussian Mixture Model. We consider a model where the feature vectors are generated from mixture of two sub-Gaussian distributions with means f and -4 and the same covariance matrix Σ. We assume that each data pair (x, y) are generated independently from the following procedure:
1. The label y E (+} is generated as a Rademacher random variable.
A random vector [ is generated from a distribution such that the entries of u are independent SabbGaussian random variables with E(u,] = 0, B|uÿ] = 1 and ||u I o, for all E [d].
3. Let Σ be positive definite matrix with eigenvalue decomposition Σ VAVT, where A (ilag>>1-.. Ad} and V is an orthonormal matrix consisting of the eigenvectors of Σ. We calculate the random vector q based on u as q = 1/2 This ensures that q has mean zero and covariance matrix Σ.
4. The feature is given y = and is 1a when = 11
y u 11+--+1 q, where μ Rdd is vector. Clearly, the mean of x is f when
We consider n training data points (xi, vi) generated independently from the above procedure, and denote
x= y/² + Q.
where X [x Q (qi...., qnl T E Ru and y = (y,,..., yn] T E {+1)². For any O Rdd, the population risk of the linear classifier x + (0, x) is defined as:
R(0) = Ply (0. x) < 0).
3

---

In this paper, we consider the maximum margin linear classifier 9svM. i... the solution to the hard-margin support vector machine:
9wv = argmin 011, subject to yı (0,00, 2 E [n].
and study its population risk R(0svM).
recent work [6] has studied a similar sub- uub-Gaussian mixture model under an assumption that tr(E)= D(d). and considered additional label flipping noises. In this paper, do not introduce the label flipping noises for simplicity, but we consider a general covariance matrix Σ to cover the general anisotropic setting. It is worth noting that although we don't have additional label flipping noise, there is still noise in our model because of the nature of sub-Gaussiag mixture model. For example, consider mixture of two Gaussian distributions. The two Gaussian clusters have non-trivial overlap, and the Bayes optimal classifier has non-zero Bayes risk long as ||||| co. Therefore, the Bayes optimal classifier and the interpolating classifier are generally quite different. In general, a model is appropriate for the study of benign overfitting whenever the optimal classifier has non-zero Bayes risk.
model is not exactly the same [6] because
Our model is rather general and covers the following examples.
Example 2.1 (Gaussian mixture model). The most straight-forwand example is when the data are generated from Gaussian mixtures N (p,, Σ) and (- μ,, E). This covered by our model when the sub-Gaussian vector is a standard Gaussian random vector.
Example 2.2 (Rare/weak feature model). The rare-weak model is special case of the Gaussian mixture model where Σ = and 1a a sparse vector with non-zero entries equaling 7,
The rare/weak feature model was originally investigated by [8, 14), and was recently studied by [6].
Connection to peeemparamteri Logistic Regression. Our study of the maximum margin classifier is closely related wver-parameterized logistic regression. In logistic regression, consider the following empirical loss minimization problem:
min I(()) OER4
Σ log(1 exp(- (0, (0,x,))
We solve the above optimization problem with gradient descent
e ((+1) (()) VI(((()).
(2.1)
where 7) > the learning rate.
In the over-parameterized setting where >> n, it is evident that the training data points are linearly separable with high probability (for example, XXT invertible with high probability and the minimum norm interpolator 0.s = X (
separates the training data.). For linearly
separable data, series of recent works have studied the implicit bias of (stochastic) gradient descent for logistic regression [22, 13, 21J. These results demonstrate that among all linear classifiers that can classify the training data correctly, gradient descent will converge to the one that maximizes the l2 margin. Such an implicit bias result is summarized the following lemma.
Lemma 2.3 (Theorem 3 in [22]). Suppose that the training data set {xx,, y4)} is linearly separable.
Then as long as > 0 is small enough, the gradient descent iterates (4) for logistic regression defined in (2.1) has the following direction limit:
(
θSVM
lim t
|001|
|10svMll2*
where 0svm is the maximum margin classifier.
Lemma 2.3 suggests that our risk bound of the maximum margin classifier θSVM directly implies risk bound for the over-parameterizze logistic regression trained by gradient descent.

---

3 Main Results
In this section, we present our main result on the population risk bound of the maximum margin classifier, and then give lower bound result to demonstrate the tightness of upper bounds. We also showcase the application of our results to isotropic and anisotropic sub-Gaussian mixture models study the conditions under which benign overfitting occurs.
The main result of this paper is given in the following theorem, where we establish the population risk bound for the maximum margin classifier R(0svM)
Theorem 3.1. Suppose that tr [)] 2 C' C'ax {n E11 n Σ F. (nll,,//ll)))) ||||| and ll Z
C/|lu|| for some absolute constant C. Then with probability at least n -1 the maximum margin classifier Osvm has the following risk bound
-C'
R(0svM)= & exp
p
3
+
Σ 7
+ n
Σ
where C" is an absolute constant.
Theorem 3.1 gives the population risk bound of the maximum margin classifier θWMM- Based on the implicit bias of gradient descent for over-parameterized logistic regression (Lemma 2.3), have that the gradient descent iterates (()) satisfy that
lim ((((())= lim R(O()) ||0())))))2)) R((0vv// (0sMM/22) = R((SvM).
Therefore, the same risk bound in Theorem 3.1 also applies to the over-parameteriied logistic regression trained by gradient descent.
Population Risk Lower Bound We further present lower bounds the population risk achieved by the maximum margin classifier, which demonstrate that our population risk upper bound in Theorem 3.1 is tight. We have the following theorem.
Theorem 3.2. Consider Gaussian mixture model with covariance matrix Σ and mean vectors a and -.. Suppose that tr()) 2 C' max (n²/2 |/ n|[E][ ny / /log(n) |||||| and || 2 C|
for some constant C. Then there exist absolute constants C", C", such that the following results hold:
1. If f n| > C(| + nl E))), then with probability at least 1 n
R((svM) C" exp C' 12/1m/))))))
2. If E 2 Cn(1
+ ( then with probability at least 1 - n
R((SvM)) 2 C" exp ( 12)
Theorem 3.2 gives lower bounds for the population risk in two settings: (i) n nl|pe 2 C n| [113) and (ii) | 2 Cn(luu|
| Note that in the population risk upper bound in Theorem 3.1, there are three terms in the denominator of the exponent: |||| |Σ| P. and n |Σ when the first the second term is the leading term, respectively. Moreover, it is also easy to check that under both settings, lower bound in Theorem 3.2 matches the upper bound in Theorem 3.1. This suggests that our population risk bound in Theorem 3.1 is tight.
Therefore, setting (i) and setting (ii) in Theorem 3.2 correspond to the
Implications for Specific Examples. Theorem 3.1 holds for general covariance matrices Σ, and illustrates how the spectrum Σ affects the population risk of the maximum margin classifier. This makes our result more general than the recent results in [6, 25], where the population risk bounds are given only in terms of the sample size n, dimension and the norm of the mean vector |//1||2 In fact, when we specialize our general result to the isotropic setting, our result also provides tighter risk bound than these existing results. Specifically, our population risk bound for the isotropic setting given in the following corollary.
5

---

Corollary 3.3 (Isotropic Gau-sans mixtures). Consider the setting where Σ = I. Suppose that d 2 C' max {n², / log(n) ||æl|l)) and || 2 C for some absolute constant C. Then with probability at least 1 - n 1, the maximum margin classifier 2svm has the following risk bound
C' C' n| p
R((svM) S exp
where CM is an absolute constant.
Remark 3.4. [6] recently gave risk bound of order exp( 22 (2/l//d))) for sub-Gaussian mixture models under the condition that d = (mmax {n² log(n). |4 In comparison, our result in Corol- lary 3.3 only requires the condition d = Mmmax(n2 n2 (n) [|lll))), which is milder. Moreover, when the stronger condition d (2(12 | ( holds, our risk bound becomes exp(=Q((illull//)) which is better than the result of [6] by a factor of n in the exponent.
Besides being tighter than previous results when reduced to the isotropic setting, Theorem 3.1 covers both the isotropic and anisotropic settings. In the following, we provide some case studies under the anisotropic setting and show how the decay rate of the eigenvalues of the covariance matrix E affects the population risk.
It is worth noting that the assumption of Theorem 3.1 requires that tr()) is large enough, while the risk bound in Theorem 3.1 only depends on ||>]| F and E1 2. In the over-parameterized setting where the dimension d is large, it is possible that for certain covariance matrices E with appropriate O(1). This implies that for many anisotropic nub-Gaussian mixture models, the assumptions in Theorem 3.1 can be easily satisfied, while the risk bound can be small at the same time. Following this intuition, we study the conditions under which the the maximum margin interpolator 9SVM achieves o(1) population risk. We denote by A the k-th largest eigenvalue of Σ, and consider a polynomial decay spectrum {^2 = k k- (ddd -= ")=-1 where we introduce parameter to control the eigenvalue decay rate. We have the following corollary.
eigenvalue decay rates, tr(E) > while | F. |E||
Corollary 3.5 (Anisotripic sub- Gaussian mixtures with polynomial spectrum decay). Suppose that , n is a large enough constant, and one of the following conditions hold: A = k =m
1. E 1/2) d = ĀC(( ( Tix), and داا|| w(1 + d4/2-1/2)
a = 1/2, d = ((11)))) and 1 = w(log( 1/4).
a (1/2, 1). @(((1 ) and ||ااا| = w1).
Then with probability at least 1 - n the population risk of the maximum margin classifier satisfies R(0SvM) o())
=E= Corollary 3.5 follows by caleulating the orders of tr tr(E) = k== d and - we treat the sample size n as a constant for simplicity. A full version of the corollary with detailed dependency on is given Corollary C. in Appendix C together with the proof. Intuitively, when ||лl|| is large, the two classes are far away from each other and therefore linear classifiers can achieve small population risk. From Corollary 3.5, we can see that the decay rate of the eigenvalues of the covariance matrix Σ determines how large ||ą4||2 needs to be to ensure small population risk: when the { decays faster (i.e., when a larger), the maximum margin classifier can achieve (1)) population risk with a smaller ||||||2-
X3. Here
Corollary 3.5 also exhibits a certain "phase transition" regarding the eigenvalue decay rate and the conditions on || We can see that the eigenvalue decay rate can be divided into three 1/2 and E (1/2, 1). Under the condition that d = (2(([ achieving o(1) risk in each of these regimes requires || = w(d ||14|| = w (loog dd) / and ||ll|| = (1) respectively. Specifically, when E (1/2, 1), the condition on ş is independent of the dimension d. This means that when a E (1/2, 1), for any > O, as long as || = 22( /log())), we have
regimes E [0, 1/2),
lim R(@SvM) Sc d

---

Therefore, our result covers the infinite dimensional setting when the eigenvalues of the covariance matrix Σ have an appropriate decay rate, i.e., (1/2.1).
Another interesting observation in Theorem 3. is that uses both || and // and therefore the alignment between l and the eigenvectors of Σ can affect the population risk bound. In discussion above, we have mainly focused on the worst case scenario where the direction of şe aligns with the first eigenvector of Σ. In the following corollary, we discuss the case where μ parallel to the eigenvector of E corresponding to the eigenvalue Ap-
Corollary 3.6 (Risk bounds for μ along different directions). Suppose that Σμ Aape for some k E [d], tr(E) 2 C' Cax {n>/3 | |2 Ei,,, na / / log(n) || and || 2 2 C²A for some
absolute constant Then with probability at least n -1 the maximum margin classifier θSvm has the following risk bound
C' Cn
R(OsvM) S exp
n1
||
where C" is absolute constant.
We can see that, when aligns with the cigendirections corresponding to smaller eigenvalue of E. then Corollary 3.6 holds under milder conditions on tr(E) and || and the population risk achieved by the maximum margin solution is also better. This phenomenon perfectly matches the geometric intuition of sub- Gau-Gansian mixture classifications, as illustrated in Figure 1.
(a) aligns with
(b) points at random direction
(c) aligns with
Figure 1: A 2-dimensional illustration of Sab-Gausisan mixture classification problems with different directions of μ.. We consider the setting where Σ E R2x2 has two eigenvalues ê1 >> X2 with the corresponding eigenvectors V1, V2- (a) shows the setting where fe aligns with V2. (b) shows the setting where μa points at random direction. (c) is for the when fe aligns with vı. These figures clearly show that (a) is the easiest case for classification and (c) is the hardest case. This matches the result in Corollary 3.6.
At last, also apply our risk bound the rare/weak feature model defined in Example 2.2. We have the following corollary.
Corollary 3.7 (Rare/weak feature model), Consider the rare/weak feature model (Example 2.2). Suppose that d 2 C max(n?, / log(n)} and 7 2 C' for some large enough absolute constant C. Then when n is large enough, with probability at least - n -1 the maximum margin classifier θsvM has the following risk bound
R( S exp (-
ny2 (-
C'ny+
where C" is absolute constant.
By Corollary 3.7, we can see that our bound is tighter by factor of n in the exponent compared rare/weak feature model. Under the setting where n and y are
with the risk bound [6] fixed constants, our bound can also be compared with the negative result in [14], which showed that achieving a small population risk is impossible when & O(2). Our result, on the other hand, demonstrates that when w(d?), o(1) population risk is achievable.

---

Proof of the Main Results
In this section, we explain how we establish the population risk bound of the maximum margin classifier, and give the proof of Theorem 3.1.
For classification problems, one the key challenges is that the maximum margin classifier usually does not have an explicit form solution. To overcome this difficulty, [6] utilized the implicit bias results (Lemma 2.3) to get a handle on the relationship between the maximum margin classifier and the training data. More recently, [25] showed that for isotropic Gaussian mixture models, explicit form of Osvm can be calculated by the equivalence between hard-margin support vector machine and minimum norm least square regression. Notably, it was shown that such an equivalence result holds under the assumptions of [6] and no any additional assumptions are needed. In this paper, we also study the equivalence between classification and regression as first step. However, our proof works for more general setting that covers both isotropic and anisotropic sub- Gaussin mixtures. and introduces novel proof technique based on the polarization identity that leads to a tighter bound. We present this result in Section 4.
Step 1. Equivalence Between Classification and Regression. Here we establish equivalence guarantee for the maximum margin classifier and the minimum norm interpolator. Note that the definitions of the minimum norm interpolator OLs and the maximum margin classifier θSVM are as follows:
ØLs == argmin |0 12 subject to yi (0, 1, E [m]]
θsvm = argmin 1 subject to y: (0, x;) 2 1, E [n]]
We can see that the two optimization problems have the same solution when all the training data are support vectors, i.e., all the inequalities become equalities in the constraints [19, 121. Here we derive such an equivalence result for ua-GGausiian mixture models. The result follows.
Proposition 4.1. Suppose that tr( (r(E)= 2 C max mmx((3322 3n |||,, n Σ|| r. ny/log()) [|]]| for some absolute constant C. Then with probability at least On 1),, dwMm
01s-
The proof of Proposition 4. utilizes an argument based on the polarization identity to give a tight bound, which may be of independent interest. The details are given in Appendix 4.1.
Step 2. Population Risk of the Maximum Margin Classifier. We derive the population risk bound for the maximum margin classifier and provide the proof of Theorem 3.1. We first present the following lemma on the risk bound of linear classifiers for sub-Gaussian mixture models.
Lemma 4.2. There exists an absolute constant C' such that, for any O e Rd, the following risk bound holds:
C( 4)² 0
R(0)= S exp
similar result is given in [6] where Σ is replaced by I. Our result here depends on the full spectrum of the covariance matrix and is sharper than [6] when Σ has decaying eigenvalues.
The proof of Lemma 4.2 is given in Appendix A.2. In addition to this risk bound for general vector 0, we also have the following explicit calculation for θsvM thanks to our analysis in Section 4. This is because the minimum norm interpolator 0Ls has the explicit form oLS x (XX ) yy. Therefore by Proposition 4.1, we also have ØsVM = X (XXT)- Plugging this calculation into the risk bound in Lemma 4.2 and utilizing the model definition X yμ following risk bound for ŌSMM-
Q, we are able show the
Lemma 4.3. Suppose that tr(E)= 2 C max (n Tog(n), n, n 3/22 solute constant C. Then with probability at least - (n
Σ
12 72
Σ
n [|]]) for some ab-
CC [y
X11 22
R(0SVM) S <exp
{
( (
XXX (ATT)-1)
where C² is absolute constant.
8

---

Lemma 4.3 utilizes the structure of the model to divide the denominator in the exponent into two terms. Motivated by this result, we define
12 (y TyT(xxx) (xx | I3 This leads to our analysis in the next step.
/1 ly (Xx")=
Q|Q T (XX 1
Step 3. Bounds for 1T, 1a and 13. In the following, we develop a lower bound for 17 and upper bounds for 1z and /3 respectively. The following lemma summarizes the bounds, Lemma 4.4. Suppose that tr( tr(E) 2 C max E vn| F. 12 ||| and || > Cl > for some absolute constant C. Then when n is large enough, with probability at least O( ?),
1 2 C' (H,, Q.y. E) -) -n² ||2
1 S C" (H, Q, Σ) n² |
13 S CHH(H, Q, .). (n | + 2 |E|2)
where Hj,, Q, Σ) > 0 is strictly positive coefficient, and C" > is an absolute constant.
The proof of Lemma 4.4 is given in Appendix A.2. To illustrate the key idea in the proof of Lemma 4.4, we take I3 as an example. Based on our model in Section 2, we have Q = ZA 1/2VT where Z "xdd is random matrix with independent based on the eigenvalue decomposition Σ VAVT. By some linear algebra calculation (see the proof of Lemma 4.4 Appendix A.2 for more details), we have
entries, and A, V are defined
I3 a (ZAZ") ZAZZ (ZAZ)) where |al]] O(D Pn) with (112112 μ Q (QQQQ-QQuu + (1+ (
(4.1)
D D=yT(QQT))
The key observation here that while the term above has a very complicated form, it is not necessary to bound it. This is because D-2 is common term that appears in all I, I2 and Is and therefore can be canceled out when calculating the ratio / Iz). With the calculation in (4.1), we are able to invoke the following eigenvalue concentration inequalities (see Lemma A.4 and Lemma A.7 for more details) to give upper and lower bounds regarding the matrices ZAZZ" and ZAZ respectively:
ZAZ T (r(E) S
(nl E||
+ vn F),
> S ct
2 + vnl Σ I|F),
where ej is an absolute constant. Plugging the above inequalities and the bound ||a| O(D-2n) into (4.1), we obtain with some calculation that
I3 (2 Q,y, (n | 1 n
|E
with Hp,, Q.y, -)
tr()) where c2 is an absolute constant. This gives the bound of Iz-
Lemma 4.4 is significant in three-fold. First of all, the result does not have an explicit dependency on d, which makes it applicable to infinite dimensional data. Second, Lemma 4.4 gives bounds with great simplicity, and shows that the three bounds share a same strictly positive factor H H(s, Q. y: E), which can be canceled out since our final goal is to bound the ratio T 71/(12 + Iz). Lastly, Lemma 4.4 reveals the fact that the risk bound only depends on Σ and |2]2, which can be small even though the assumption requires tr tr(E) be large.
We are now ready present the proof of Theorem 3.1.
Proof of Theorem 3.1. Clearly, under the assumptions of Theorem 3.1, the conditions in Lemma 4.3 and Lemma 4.4 are both satisfied. By Lemma 4.4, we have
y (XX
n
p
2
(XX where Cj is an absolute constant. Therefore by Lemma 4.3 we have
Q ( -
n² 14
+
n
Σ
7
Σ
C2n 14 1
R(0svm) < exp
n Il|
2
Σ
+
for some absolute constant c2. Note that by union bound, the above inequality holds with probability at least 1 - O(n -2) ) n-1 when n is large enough. This completes the proof. L

---

Conclusion and Future Work
We have studied the benign overfitting phenomenon for nab-Gaassian mxiture models, and established population risk bound for the maximum margin classifier. Our population risk bound is general and covers both the isotropic and anisotropic settings. When reduced to the isotropic setting, our bound tighter than existing results. We have also studied a class of non-isotropic models which can be benign even for infiniteddimensional data.
An interesting future work direction is to study the relation between the dimension and the population risk and verify the double descent phenomenon. Studying benign overfitting for more complicated learning models such as neural networks is another important future work direction.
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for their helpful comments. This work was done when YC was a postdoctoral researcher at UCLA. YC and QG are partially supported by the National Science Foundation award IIS 1903202 and IIS 100-200. MB acknowledges support from NSF IIS- SSS-1815697 and the support of the NSF and the Simons Foundation for the Collaboration on the Theoretical Foun- dations of Deep Learning through awards DMS-203 1883 and #8 1464939. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
References
[1] ARORA, S., COHEN, N., HU, W. and Luo, Y. (2019). Implicit regularization in deep matrix factorization, Advances in Neural Information Processing Systems 32.
[2] BARTLETT, P. L., LONG, P. M., LUGOSI, G. and TSIGLER, A. (2020). Benign overfitting in linear regression, Proceedings of the National Academy of Sciences.
[3] BELKIN, M., HSU, D., MA, S. and MANDAL, S. (2019). Reconciling modern machine-learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences 116 15849-15854.
[4] BELKIN, M., HSU, D. and Xu, J. (2019). Two models of double descent for weak features. arXiv preprint arXiv: 1903.07571.
[5] BELKIN, M., MA, S. and MANDAL, S. (2018). To understand deep learning need to understand kernel learning. In International Conference on Machine Learning. PMLR.
[6] CHATTERJI, N. S. and LONG, P. M. (2020). Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. arXiv preprint arXiv:2004. 12019.
[7] CôTÉ, F. D., PSAROMILIGKOS, I. N. and GROSS, W. J. (2012). A chernoff-yye lower bound for the gaussian q- g-function. arXiv preprint arXiv:1202 6283..4......
[8] DONOHO, D. and JIN, J. (2008). Higher criticism thresholding: Optimal feature selection when useful features are rare and weak. Proceedings of the National Academy of Sciences 105 14790-14795.
[9] GUNASEKAR. S., LEE, J., SOUDRY, D. and SREBRO, N. (2018). Characterizing implicit bias terms of optimization geometry. International Conference on Machine Learning.
[10] GUNASEKAR, S., WOODWORTH, E., BHOIANAPALLI, S., NEYSHABUR, B. and SREBRO, N. (2017). Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems.
[11] HASTIE, T., MONTANARI, A., ROSSET, S. and TIBSHIRANI, (2019). Surprises in high-dimensional ridgeless least squares interpolation. arXiv preprint arXiv: 1903.08500.
[12] HSU, D., MUTHUKUMAR, V. and Xu, J. (2020). On the proliferation of support vectors in high dimensions. arXiv preprint vrXiv:2009.1067.
[13] J1, Z. and TELGARSKY, M. (2019). The implicit bias of gradient descent on nonseparable data. In Conference on Learning Theory.
10

---

[14] JIN, J. (2009). Impossibility of successful classification when useful features are rare and weak. Proceedings of the National Academy of Sciences 106 8859-
[15] LIAO, Z., COUILLET, R. and MAHONEY, M. (2020). A random matrix analysis of random fourier features: beyond the gaussian kernel, precise phase transition, and the corresponding double descent. In 34th Conference on Neural Information Processing Systems (NeurIPS 2020).
[16] LYU, K. and LI, (2019). Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint arXiv: 1906.05890.0.....
[17] MEI. S. and MONTANARI, A. (2019). The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprint (et.::9990.0535555
[18] MONTANARI, A. and ZHINNG, Y. (2020). The interpolation phase transition in neural networks: Memorization and generalization under lazy training. arXiv preprint arXivv2007.1282
[19] MUTHUKUMAR, V., NARANG, A., SUBRAMANIAN, V., BELKIN, M., HSU, D. and SAHAI, A. (2020). Classification vs regression in overparameterizee regimes: Does the loss function matter? arXiv preprint arXiv:2005.08054.
[20] MUTHUKUMAR, V., VODRAHALLI, K., SUBRAMANIAN, V. and SAHAL, A. (2020). Harmless interpolation of noisy data regression. IEEE Journal on Selected Areas in Information Theory 1 67-83.
[21] NACSON, M. S., SREBRO, N. and SOUDRY, D. (2019). Stochastic gradient descent on separable data: Exact convergence with fixed learning rate. In The 22nd International Conference on Artificial Intelligence and Statistics.
[22] SOUDRY, D., HOFFER, E., NACSON, M. S., GUNASEKAR, S. and SREBRO, N. (2018). The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research 19 2822-2222 2878.
[23] TSIGLER, A. and BARTLETT, P. L. (2020). Benign overfitting in ridge regression. arXiv preprint arXiv:2009. 142866
[24] VERSHYNIN, R. (2010). Introduction the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027
[25] WANG, K. and THRAMPOULIDIS, C. (2020). Benign overfitting in binary classification of gaussian mixtures. arXiv preprint arXiv:201 1.09148.
[26] WU, D. and Xu, J. (2020). On the optimal weighted &g regularization in overparameteriize linear regression. Advances in Neural Information Processing Systems 33.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The focus of this paper is on theoretical analysis. The results do not have any negative social
impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]

---

(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A] The experiments are to verify tigh-probabilityy guarantees
on synthetic data.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A] This paper does not focus on computing cost. All experiments can be run very efficiently on standard PC.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "whAFJQR76kL", "reviewer": "Reviewer_1ykL", "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.\n\nThe 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.\n\nSome complementary lower bounds are given.", "questions": "", "limitations": "", "rating": 9, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Overall Impression\nThis paper was a pleasure to read, and I confidently recommend it for publication.\nFurther, I verified much of the math in the appendix and found no errors.\n\n### Detailed Review\n\nThe 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.\n\nThe 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.\n\nI do have some questions and feedback for the authors:\n1. 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?\n1. 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$.\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$?\n1. Consider removing the line about logistic regression from your abstract. You don't really provide any new guarantee there.\n1. You should mention in the body of the paper that there are experiments in the appendix.\n1. 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:\n    - At the beginning of *every* proof in the appendix, fully restate the lemma/theorem/corollary.\n    - When you state a lemma without proof, link to its proof.\n    - 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.\n    - 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?\n1. 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).\n\nSome typos and smaller confusions:\n1. [Line 64] \"our result shows that to achieve $o(1)$ population risk\" If $n$ is constant, what is this little-o depending on? $d$?\n1. [Line 293] The details are in Appendix A.1, not Appendix 4.1.\n1. [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.\n1. [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?\n1. [Line 612] I don't think $v_i$ was defined anywhere.\n1. [Line 642] Unmatched parenthesis in the definition of $J_2$.\n1. [Line 733] \"the dependency of\" should be removed\n1. [Line 747] Should read \"holds\" not \"hold\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations discussed are fine and sufficient. Admittedly, they are not particularly creative or interesting.\n\nSocietal Impact: Not applicable.", "review_text": "", "extra_scores": {"ethical_concerns": "Not Applicable", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "XPKaPAx6u4K", "reviewer": "Reviewer_nXks", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nThis 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)$. \n\nOverall, 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.\n\nMy 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$.\n\nAnother 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please see the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "4Czf1Pq_m4Z", "reviewer": "Reviewer_1YJ4", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nSome questions/comments: \n\n- In the introduction, the results are presented without the dependence on $\\Sigma$, stating rates that are not scale invariant as one would expect.\n\n- 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.\n\n- Please give the formal definition of the sub-gaussian/exponential norms, or at least state an appropriate reference where they are mentioned (line 104).\n\n- Is the condition $||\\mu||_2 \\geq C||\\Sigma||_2$ in Lemma 4.4 correct? It is not scale invariant.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "0O57raFrAc4", "reviewer": "Reviewer_GwQP", "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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nTight 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:\n\n(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.\n\nhttps://arxiv.org/pdf/1812.08078.pdf\n\nhttps://arxiv.org/pdf/2006.14062.pdf\n\nand many other references therein.\n\n\n\n(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). \n\nOverall, my recommendation is weak accept - any comments and clarifications from the authors are welcome.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"ethical_concerns": "-", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

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)