Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures

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.

heading: 1 Introduction
text: In modern machine learning, complex models such as 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 a 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 on the test data. A series of recent works [4, 20, 11, 2] theoretically studied how over-parameterization can achieve small population risk.
In particular in [2] the authors considered the setting where the data are generated from a ground-truth linear model with noise, and established a tight population risk bound for the minimum norm linear interpolator with a 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 are tight for a 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 over-parameterized 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 (NeurIPS 2021).
from a ground truth linear model with label flipping noise, and showed equivalence between the hardmargin support vector machine (SVM) solution and the minimum norm interpolator to study benign overfitting. [6, 25] studied the benign overfitting phenomenon in sub-Gaussian/Gaussian 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-)Gaussian mixture classification, they still have certain limitations. Unlike the results in the regression setting where the eigenvalues of the data covariance matrix play a key role, the current results for Gaussian/sub-Gaussian 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 µ and the sample size n, 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 than existing results on sub-Gaussian/Gaussian mixture models. The contributions of this paper are as follows:
• We establish a 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 to the setting studied in [6], our result gives a bound exp(−Ω(n‖µ‖42/d)), where n is the training sample size. Our bound is tighter than the risk bound exp(−Ω(‖µ‖42/d)) in [6] by a factor of n in the exponent. Our result also gives a tighter risk bound than that in [25]1 in the so-called “low SNR setting”: our result suggests that ‖µ‖42 = ω(d/n) suffices to ensure an o(1) population risk, while [25] requires ‖µ‖42 = ω((d/n)3/2).
• 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 a class of high-dimensional anisotropic sub-Gaussian mixture models, the maximum margin linear classifier on the training data can achieve small population risk under mild assumptions on the sample size n and mean vector µ. Specifically, suppose that the eigenvalues of Σ are {λk = k−α}dk=1 for some parameter α ∈ [0, 1), and treat the sample size n as a constant. Then our result shows that to achieve o(1) population risk, the following conditions on ‖µ‖2 suffice:
‖µ‖2 =  ω(d 1/4−α/2), if α ∈ [0, 1/2),
ω((log(d))1/4), if α = 1/2, ω(1). if α ∈ (1/2, 1).
More specifically, when α = 1/2, the condition on the mean vector µ only has a logarithmic dependency on the dimension d, and when α ∈ (1/2, 1), the condition on µ 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 in recent works. [3, 4] showed experimental results and provided theoretical analyses on some
1After 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 we covered the mixture of anisotropic sub-Gaussian, and we also proved a matching lower bound.
specific models to demonstrate that the risk curve versus over-parameterization has a double descent shape. These results can therefore indicate that over-parameterization can be beneficial to achieve small test risk. [11, 26] studied the double descent phenomenon in linear regression under the setting where the dimension d and sample size n can grow simultaneously but have a fixed ratio, and showed that the population risk exhibits a 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 over-parameterized logistic regression with the maximum margin classifiers for linear models.

heading: 2 Problem Setting and Notation
text: Notations. We use lower case letters to denote scalars, and use lower/upper case bold face letters to denote vectors/matrices respectively. For a vector v, we denote by ‖v‖2 the `2-norm of v. For a matrix A, we use ‖A‖2, ‖A‖F to denote its spectral norm and Frobinuous norm respectively, and use tr(A) to denote its trace. For a vector v ∈ Rd and a positive definite matrix A, we define ‖v‖A = √ v>Av. For an integer n, we denote [n] = {1, 2, . . . , n}.
We also use standard asymptotic notations O(·), Ω(·), o(·), and ω(·). Let {an} and {bn} be two sequences. If there exists a constant C > 0 such that |an| ≤ C|bn| for all large enough n, then we denote an = O(bn). We denote an = Ω(bn) if bn = O(an). Moreover, we write an = o(bn) if lim |an/bn| = 0 and an = ω(bn) if lim |an/bn| = ∞. We also use Õ(·) and Ω̃(·) to hide some logarithmic terms in Big-O and Big-Omega notations.
At last, for a random variable Z, we denote by ‖Z‖ψ2 and ‖Z‖ψ1 the sub-Gaussian and subexponential norms of Z respectively.
Sub-Gaussian Mixture Model. We consider a model where the feature vectors are generated from a mixture of two sub-Gaussian distributions with means µ and −µ and the same covariance matrix Σ. We assume that each data pair (x, y) are generated independently from the following procedure:
1. The label y ∈ {+1,−1} is generated as a Rademacher random variable.
2. A random vector u ∈ Rd is generated from a distribution such that the entries of u are independent sub-Gaussian random variables with E[uj ] = 0, E[u2j ] = 1 and ‖uj‖ψ2 ≤ σu for all j ∈ [d].
3. Let Σ be a positive definite matrix with eigenvalue decomposition Σ = VΛV>, where Λ = diag{λ1, . . . , λd} and V is an orthonormal matrix consisting of the eigenvectors of Σ. We calculate the random vector q based on u as q = VΛ1/2u. This ensures that q has mean zero and a covariance matrix Σ.
4. The feature is given as x = y ·µ+ q, where µ ∈ Rd is a vector. Clearly, the mean of x is µ when y = 1 and is −µ when y = −1.
We consider n training data points (xi, yi) generated independently from the above procedure, and denote
X = yµ> + Q,
where X = [x1, . . . ,xn]>,Q = [q1, . . . ,qn]> ∈ Rn×d, and y = [y1, . . . , yn]> ∈ {±1}n. For any θ ∈ Rd, the population risk of the linear classifier x→ 〈θ,x〉 is defined as:
R(θ) = P ( y · 〈θ,x〉 < 0 ) .
In this paper, we consider the maximum margin linear classifier θ̂SVM, i.e., the solution to the hard-margin support vector machine:
θ̂SVM = argmin ‖θ‖22, subject to yi · 〈θ,xi〉 ≥ 1, i ∈ [n],
and study its population risk R(θ̂SVM).
A recent work [6] has studied a similar sub-Gaussian mixture model under an assumption that tr(Σ) = Ω(d), and considered additional label flipping noises. In this paper, we 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 our model is not exactly the same as [6] because we don’t have additional label flipping noise, there is still noise in our model because of the nature of sub-Gaussian mixture model. For example, consider a mixture of two Gaussian distributions. The two Gaussian clusters have non-trivial overlap, and the Bayes optimal classifier has non-zero Bayes risk as long as ‖µ‖2 < ∞. 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.
Our model is rather general and covers the following examples.
Example 2.1 (Gaussian mixture model). The most straight-forward example is when the data are generated from Gaussian mixtures N(µ,Σ) and N(−µ,Σ). This is covered by our model when the sub-Gaussian vector u is a standard Gaussian random vector.
Example 2.2 (Rare/weak feature model). The rare-weak model is a special case of the Gaussian mixture model where Σ = I and µ is a sparse vector with s non-zero entries equaling γ.
The rare/weak feature model was originally investigated by [8, 14], and was recently studied by [6].
Connection to Over-parameterized Logistic Regression. Our study of the maximum margin classifier is closely related to over-parameterized logistic regression. In logistic regression, we consider the following empirical loss minimization problem:
min θ∈Rd
L(θ) := 1
n n∑ i=1 log[1 + exp(−yi · 〈θ,xi〉)].
We solve the above optimization problem with gradient descent
θ(t+1) = θ(t) − η · ∇L(θ(t)), (2.1)
where η > 0 is the learning rate.
In the over-parameterized setting where d n, it is evident that the training data points are linearly separable with high probability (for example, XX> is invertible with high probability and the minimum norm interpolator θ̂LS = X>(XX>)−1y separates the training data.). For linearly separable data, a series of recent works have studied the implicit bias of (stochastic) gradient descent for logistic regression [22, 13, 21]. 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 `2 margin. Such an implicit bias result is summarized in the following lemma.
Lemma 2.3 (Theorem 3 in [22]). Suppose that the training data set {(xi, yi)} is linearly separable. Then as long as η > 0 is small enough, the gradient descent iterates θ(t) for logistic regression defined in (2.1) has the following direction limit:
lim t→∞
θ(t)
‖θ(t)‖2 =
θ̂SVM
‖θ̂SVM‖2 ,
where θ̂SVM is the maximum margin classifier.
Lemma 2.3 suggests that our risk bound of the maximum margin classifier θ̂SVM directly implies a risk bound for the over-parameterized logistic regression trained by gradient descent.

heading: 3 Main Results
text: In this section, we present our main result on the population risk bound of the maximum margin classifier, and then give a lower bound result to demonstrate the tightness of our upper bounds. We also showcase the application of our results to isotropic and anisotropic sub-Gaussian mixture models to 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(θ̂SVM).
Theorem 3.1. Suppose that tr(Σ) ≥ C max { n3/2‖Σ‖2, n‖Σ‖F , n √ log(n) · ‖µ‖Σ } and ‖µ‖22 ≥ C‖µ‖Σ for some absolute constant C. Then with probability at least 1− n−1, the maximum margin classifier θ̂SVM has the following risk bound
R(θ̂SVM) ≤ exp
( −C ′n‖µ‖42
n‖µ‖2Σ + ‖Σ‖2F + n‖Σ‖22
) ,
where C ′ is an absolute constant.
Theorem 3.1 gives the population risk bound of the maximum margin classifier θ̂SVM. Based on the implicit bias of gradient descent for over-parameterized logistic regression (Lemma 2.3), we have that the gradient descent iterates θ(t) satisfy that
lim t→∞ R(θ(t)) = lim t→∞ R(θ(t)/‖θ(t)‖2) = R(θ̂SVM/‖θ̂SVM‖2) = R(θ̂SVM).
Therefore, the same risk bound in Theorem 3.1 also applies to the over-parameterized logistic regression trained by gradient descent.
Population Risk Lower Bound We further present lower bounds on 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 µ and −µ. Suppose that tr(Σ) ≥ C max { n3/2‖Σ‖2, n‖Σ‖F , n √ log(n) · ‖µ‖Σ } , and ‖µ‖22 ≥ C‖µ‖Σ for some constant C. Then there exist absolute constants C ′, C ′′, such that the following results hold:
1. If n‖µ‖2Σ ≥ C(‖Σ‖2F + n‖Σ‖22), then with probability at least 1− n−1,
R(θ̂SVM) ≥ C ′′ exp ( − C ′‖µ‖42/‖µ‖2Σ ) .
2. If ‖Σ‖2F ≥ Cn(‖µ‖2Σ + ‖Σ‖22), then with probability at least 1− n−1,
R(θ̂SVM) ≥ C ′′ exp ( − C ′n‖µ‖42/‖Σ‖2F ) .
Theorem 3.2 gives lower bounds for the population risk in two settings: (i) n‖µ‖2Σ ≥ C(‖Σ‖2F + n‖Σ‖22); and (ii) ‖Σ‖2F ≥ Cn(‖µ‖2Σ + ‖Σ‖22). Note that in the population risk upper bound in Theorem 3.1, there are three terms in the denominator of the exponent: ‖µ‖2Σ, ‖Σ‖2F , and n‖Σ‖22. Therefore, setting (i) and setting (ii) in Theorem 3.2 correspond to the cases when the first or the second term is the leading term, respectively. Moreover, it is also easy to check that under both settings, our 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.
Implications for Specific Examples. Theorem 3.1 holds for general covariance matrices Σ, and illustrates how the spectrum of Σ 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 d and the norm of the mean vector ‖µ‖2. In fact, when we specialize our general result to the isotropic setting, our result also provides a tighter risk bound than these existing results. Specifically, our population risk bound for the isotropic setting is given in the following corollary.
Corollary 3.3 (Isotropic sub-Gaussian mixtures). Consider the setting where Σ = I. Suppose that d ≥ C max { n2, n √ log(n) · ‖µ‖2 } and ‖µ‖2 ≥ C for some absolute constant C. Then with probability at least 1− n−1, the maximum margin classifier θ̂SVM has the following risk bound
R(θ̂SVM) ≤ exp ( − C
′n‖µ‖42 n‖µ‖22 + d
) ,
where C ′ is an absolute constant. Remark 3.4. [6] recently gave a risk bound of order exp(−Ω(‖µ‖42/d)) for sub-Gaussian mixture models under the condition that d = Ω(max{n2 log(n), n‖µ‖22}). In comparison, our result in Corollary 3.3 only requires the condition d = Ω(max{n2, n √ log(n) · ‖µ‖2}), which is milder. Moreover, when the stronger condition d = Ω(n‖µ‖22) holds, our risk bound becomes exp(−Ω(n‖µ‖42/d)), 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 Σ 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 ‖Σ‖2. In the over-parameterized setting where the dimension d is large, it is possible that for certain covariance matrices Σ with appropriate eigenvalue decay rates, tr(Σ) 1 while ‖Σ‖F , ‖Σ‖2 = O(1). This implies that for many anisotropic sub-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 θ̂SVM achieves o(1) population risk. We denote by λk the k-th largest eigenvalue of Σ, and consider a polynomial decay spectrum {λk = k−α}dk=1, where we introduce a parameter α to control the eigenvalue decay rate. We have the following corollary. Corollary 3.5 (Anisotripic sub-Gaussian mixtures with polynomial spectrum decay). Suppose that λk = k −α, n is a large enough constant, and one of the following conditions hold:
1. α ∈ [0, 1/2), d = Ω̃((‖µ‖Σ) 1 1−α ), and ‖µ‖2 = ω(1 + d1/4−α/2).
2. α = 1/2, d = Ω̃(‖µ‖2Σ), and ‖µ‖2 = ω((log(d))1/4).
3. α ∈ (1/2, 1), d = Ω̃((‖µ‖Σ) 1 1−α ), and ‖µ‖2 = ω(1).
Then with probability at least 1− n−1, the population risk of the maximum margin classifier satisfies R(θ̂SVM) = o(1).
Corollary 3.5 follows by calculating the orders of tr(Σ) = ∑d k=1 λk and ‖Σ‖2F = ∑d k=1 λ 2 k. Here we treat the sample size n as a constant for simplicity. A full version of the corollary with detailed dependency on n is given as Corollary C.1 in Appendix C together with the proof. Intuitively, when ‖µ‖2 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 ‖µ‖2 needs to be to ensure small population risk: when the {λk} decays faster (i.e., when α is larger), the maximum margin classifier can achieve o(1) population risk with a smaller ‖µ‖2. Corollary 3.5 also exhibits a certain “phase transition” regarding the eigenvalue decay rate and the conditions on ‖µ‖2. We can see that the eigenvalue decay rate can be divided into three regimes α ∈ [0, 1/2), α = 1/2 and α ∈ (1/2, 1). Under the condition that d = Ω̃((‖µ‖Σ) 1 1−α ), achieving o(1) risk in each of these regimes requires ‖µ‖2 = ω(d1/4), ‖µ‖2 = ω([log(d)]1/4), and ‖µ‖2 = ω(1) respectively. Specifically, when α ∈ (1/2, 1), the condition on µ is independent of the dimension d. This means that when α ∈ (1/2, 1), for any > 0, as long as ‖µ‖2 = Ω( √ log( )), we have
lim d→∞
R(θ̂SVM) ≤ .
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.1 is that it uses both ‖µ‖Σ and ‖µ‖2, and therefore the alignment between µ and the eigenvectors of Σ can affect the population risk bound. In our discussion above, we have mainly focused on the worst case scenario where the direction of µ aligns with the first eigenvector of Σ. In the following corollary, we discuss the case where µ is parallel to the eigenvector of Σ corresponding to the eigenvalue λk.
Corollary 3.6 (Risk bounds for µ along different directions). Suppose that Σµ = λkµ for some k ∈ [d], tr(Σ) ≥ C max { n3/2‖Σ‖2, n‖Σ‖F , n √ λk log(n) · ‖µ‖2 } and ‖µ‖22 ≥ Cλk for some absolute constant C. Then with probability at least 1− n−1, the maximum margin classifier θ̂SVM has the following risk bound
R(θ̂SVM) ≤ exp
( −C ′n‖µ‖42
nλk · ‖µ‖22 + ‖Σ‖2F + n‖Σ‖22
) ,
where C ′ is an absolute constant.
We can see that, when µ aligns with the eigendirections corresponding to a smaller eigenvalue of Σ, then Corollary 3.6 holds under milder conditions on tr(Σ) and ‖µ‖2, and the population risk achieved by the maximum margin solution is also better. This phenomenon perfectly matches the geometric intuition of sub-Gaussian mixture classifications, as is illustrated in Figure 1.
At last, we can also apply our risk bound to 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 ≥ C max{n2, γn √ s log(n)} and γ √ s ≥ C for some large enough absolute constant C. Then when n is large enough, with probability at least 1− n−1, the maximum margin classifier θ̂SVM has the following risk bound
R(θ̂SVM) ≤ exp ( − C ′nγ4s2
nγ2s+ d
) ,
where C ′ is an absolute constant.
By Corollary 3.7, we can see that our bound is tighter by a factor of n in the exponent compared with the risk bound in [6] for the rare/weak feature model. Under the setting where n and γ are 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 s = O(d2). Our result, on the other hand, demonstrates that when s = ω(d2), o(1) population risk is achievable.

heading: 4 Proof of the Main Results
text: 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 of 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, an explicit form of θ̂SVM 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 a first step. However, our proof works for a more general setting that covers both isotropic and anisotropic sub-Gaussian mixtures, and introduces a 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 an equivalence guarantee for the maximum margin classifier and the minimum norm interpolator. Note that the definitions of the minimum norm interpolator θ̂LS and the maximum margin classifier θ̂SVM are as follows:
θ̂LS := argmin ‖θ‖22, subject to yi · 〈θ,xi〉 = 1, i ∈ [n],
θ̂SVM = argmin ‖θ‖22, subject to yi · 〈θ,xi〉 ≥ 1, i ∈ [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, 12]. Here we derive such an equivalence result for sub-Gaussian mixture models. The result is as follows.
Proposition 4.1. Suppose that tr(Σ) ≥ C max{n3/2‖Σ‖2, n‖Σ‖F , n √
log(n) · ‖µ‖Σ} for some absolute constant C. Then with probability at least 1−O(n−2), θ̂SVM = θ̂LS.
The proof of Proposition 4.1 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 θ ∈ Rd, the following risk bound holds:
R(θ) ≤ exp ( − C(θ >µ)2
‖θ‖2Σ
) .
A 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 θ, we also have the following explicit calculation for θ̂SVM thanks to our analysis in Section 4. This is because the minimum norm interpolator θ̂LS has the explicit form θ̂LS = X>(XX>)−1y. Therefore by Proposition 4.1, we also have θ̂SVM = X>(XX>)−1y. Plugging this calculation into the risk bound in Lemma 4.2 and utilizing the model definition X = yµ> + Q, we are able to show the following risk bound for θ̂SVM.
Lemma 4.3. Suppose that tr(Σ) ≥ C max{n √
log(n), n3/2‖Σ‖2, n‖Σ‖F , n‖µ‖Σ} for some absolute constant C. Then with probability at least 1−O(n−2),
R(θ̂SVM) ≤ exp {
−C ′ · [y>(XX>)−1Xµ]2
(y>(XX>)−1y)2‖µ‖2Σ + ‖Q>(XX>)−1y‖2Σ
} ,
where C ′ is an absolute constant.
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
I1 = [y >(XX>)−1Xµ]2, I2 = (y >(XX>)−1y)2 · ‖µ‖2Σ, I3 = ‖Q>(XX>)−1y‖2Σ. This leads to our analysis in the next step.
Step 3. Bounds for I1, I2 and I3. In the following, we develop a lower bound for I1 and upper bounds for I2 and I3 respectively. The following lemma summarizes the bounds. Lemma 4.4. Suppose that tr(Σ) ≥ C max{n, n‖Σ‖2, √ n‖Σ‖F , n‖µ‖Σ} and ‖µ‖22 ≥ C‖µ‖Σ for some absolute constant C. Then when n is large enough, with probability at least 1−O(n−2), I1 ≥ C ′−1H(µ,Q,y,Σ) · n2 · ‖µ‖42, I2 ≤ C ′H(µ,Q,y,Σ) · n2 · ‖µ‖2Σ, I3 ≤ C ′H(µ,Q,y,Σ) · (n · ‖Σ‖2F + n2 · ‖Σ‖22), where H(µ,Q,y,Σ) > 0 is a strictly positive coefficient, and C ′ > 0 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 = ZΛ1/2V>, where Z ∈ Rn×d is a random matrix with independent sub-Gaussian entries, and Λ, V are defined based on the eigenvalue decomposition Σ = VΛV>. By some linear algebra calculation (see the proof of Lemma 4.4 in Appendix A.2 for more details), we have
I3 = a >(ZΛZ>)−1ZΛ2Z>(ZΛZ>)−1a, (4.1)
where ‖a‖22 = O(D−2n) with D = y>(QQ>)−1y · (‖µ‖22 − µ>Q>(QQ>)−1Qµ) + (1 + y>(QQ>)−1Qµ)2. The key observation here is that while the term D above has a very complicated form, it is not necessary to bound it. This is because D−2 is a common term that appears in all I1, I2 and I3 and therefore can be canceled out when calculating the ratio I1/(I2 + I3). 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 ZΛ2Z> and ZΛZ> respectively: ∥∥ZΛZ> − tr(Σ) · I∥∥
2 ≤ c1 ·
( n‖Σ‖2 + √ n‖Σ‖F ) ,∥∥ZΛ2Z> − ‖Σ‖2F · I∥∥2 ≤ c1 · (n‖Σ‖22 +√n‖Σ2‖F ),
where c1 is an absolute constant. Plugging the above inequalities and the bound ‖a‖22 = O(D−2n) into (4.1), we obtain with some calculation that
I3 ≤ c2H(µ,Q,y,Σ) · (n · ‖Σ‖2F + n2 · ‖Σ‖22) with H(µ,Q,y,Σ) = [D · tr(Σ)]−2, where c2 is an absolute constant. This gives the bound of I3. 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(µ,Q,y,Σ), which can be canceled out since our final goal is to bound the ratio I1/(I2 + I3). Lastly, Lemma 4.4 reveals the fact that the risk bound only depends on ‖Σ‖F and ‖Σ‖2, which can be small even though the assumption requires tr(Σ) to be large.
We are now ready to 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>)−1Xµ]2
(y>(XX>)−1y)2‖µ‖2Σ + ‖Q>(XX>)−1y‖2Σ ≥ c1 · n2‖µ‖42 n2‖µ‖2Σ + n · ‖Σ‖2F + n2 · ‖Σ‖22 ,
where c1 is an absolute constant. Therefore by Lemma 4.3 we have
R(θ̂SVM) ≤ exp
( −c2n‖µ‖42
n‖µ‖2Σ + ‖Σ‖2F + n‖Σ‖22 ) for some absolute constant c2. Note that by union bound, the above inequality holds with probability at least 1−O(n−2) ≥ 1− n−1 when n is large enough. This completes the proof.

heading: 5 Conclusion and Future Work
text: We have studied the benign overfitting phenomenon for sub-Gaussian mxiture models, and established a 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 is tighter than existing results. We have also studied a class of non-isotropic models which can be benign even for infinite-dimensional 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-2008981. MB acknowledges support from NSF IIS-1815697 and the support of the NSF and the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning through awards DMS-2031883 and #814639. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.

Review summaries:
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.

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.

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.