Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation
Authors: Ke Wang
Vidya Muthukumar
Christos Thrampoulidis
Venue: NeurIPS 2021 Poster (2021)
Keywords: interpolation
multiclass classification
SVM
generalization bounds
Gaussian mixture model

Abstract: The growing literature on "benign overfitting" in overparameterized models has been mostly restricted to regression or binary classification settings; however, most success stories of modern machine learning have been recorded in multiclass settings. Motivated by this discrepancy, we study benign overfitting in multiclass linear classification. Specifically, we consider the following popular training algorithms on separable data: (i) empirical risk minimization (ERM) with cross-entropy loss, which converges to the multiclass support vector machine (SVM) solution; (ii) ERM with least-squares loss, which converges to the min-norm interpolating (MNI) solution; and, (iii) the one-vs-all SVM classifier. Our first key finding is that under a simple sufficient condition, all three algorithms lead to classifiers that interpolate the training data and have equal accuracy. When the data is generated from Gaussian mixtures or a multinomial logistic model, this condition holds under high enough effective overparameterization. Second, we derive novel error bounds on the accuracy of the MNI classifier, thereby showing that all three training algorithms lead to benign overfitting under sufficient overparameterization. Ultimately, our analysis shows that good generalization is possible for SVM solutions beyond the realm in which typical margin-based bounds apply.

Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation
Ke Wang
Department of Statistics and Applied Probability University of California, Santa Barbara Santa Barbara, CA 93106 kewang01 kewangO1@ucsb.. @ucsb.
Vidya Muthukumar
School of Electrical and Computer Engineering & Industrial and Systems Engineering Georgia Institute of Technology
Atlanta, GA 30332
vmuthukkuar8@gaatech edu
Christos Thrampoulidis Department of Electrical and Computer Engineering
University of British Columbia Vancouver, BC Canada V6T 1Z4 cthrampo@ece ubc.
Abstract
The growing literature on "benign overfitting" in overparameterized models has been mostly restricted to regression or binary classification settings; however, most success stories of modern machine learning have been recorded in multiclass set- tings. Motivated by this discrepancy, we study benign overfitting in multiclass linear classification. Specifically, we consider the following popular training algo- rithms on separable data: (i) empirical risk minimization (ERM) with tross-entropp loss, which converges to the multiclass support vector machine (SVM) solution; (ii) ERM with least-squares loss, which converges to the min min-norm interpolating (MNI) solution; and, (iii) the one-vs-all SVM classifier. Our first key finding is that under simple sufficient condition, all three algorithms lead to classifiers that interpolate the training data and have equal accuracy. When the data is generated from Gaussian mixtures or a multinomial logistic model, this condition holds under high enough effective overparameterizzaton.. Second, we derive novel error bounds on the accuracy of the MNI classifier, thereby showing that all three training algo- rithms lead benign overfitting under sufficient overparameterization. Ultimately, our analysis shows that good generalization is possible for SVM solutions beyond the realm in which typical margin- based bounds apply.
Introduction
Modern deep neural networks are overparameterized with respect to the amount training data and achieve zero training eиrоr, yet generalize well on test data. Recent analysis has shown that fitting of noise in regression tasks can fact be relatively benign for sufficiently high-dimensional linear models [BLLT20, BHX20, HMRT19, MVSS20, KLS20J. However, these analyses do not
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

directly extend to classification, which requires separate treatment. In fact, very recent progress on sharp analysis of interpolating binary classifiers [MNS 20, CL21, WT21, CGB21] revealed high- dimensional regimes in which binary classification generalizes well, but the corresponding regression task does not work and/or the success cannot be predicted by classical margin- margin-based bounds.
In an important separate development, these same high-dimensional regimes admit an equivalence of loss functions used at training time. The support vector machine (SVM), which arises from minimizing the logistic loss using gradient descent [SHN*18 18, JT19], was recently shown to sat- isfy a preo-prbbbbility equivalence to interpolation, which arises from minimizing the squared loss [MNS 20, HMX21]. This equivalence suggests that interpolation is ubiquitous in very overpar- maeterized settings, and can arise naturally as a consequence of the optimization procedure even when this is not explicitly encoded or intended. Moreover, this equivalence to interpolation and corresponding analysis implies that the SVM can generalize even in regimes where classical learning theory bounds are not predictive. In the logistic model case [MNS+20] and Gaussian binary mixture model case [CL.21, WT21, CGB21J, it is shown that good generalization of the SVM possible beyond the realm in which classical margin-based bounds apply. These analyses lend theoretical grounding to the surprising hypothesis that squared loss can be equivalent to, or possibly even superior, to the cross-entropy loss for classification tasks. This hypothesis was supported empirically on kernel machines in Ryan Rifkin's 's doctoral dissertation work [Rif02, RK04], and more recently in overparameterized neural networks [HB20, PL20].
These compelling perspectives have thus far been limited to regression and binary classification settings. In contrast, most success stories and surprising new phenomena of modern machine learning have been recorded in multiclass classification settings, which appear naturally in a host of applications that demand the ability to automatically distinguish between large numbers of different classes; for example, the popular ImageNet dataset [RDS+ 15] contains on the order of 1000 classes. Whether a) good generalization beyond effectively low-dimensional regimes where margin-based bounds are predictive is possible, and b) equivalence of squared loss and cross-entropy loss holds in multiclass settings remained open problems.
This paper makes significant progress towards a complete understanding of the optimization and gener- alization properties of dineensina linear multiclass classification. both for unconditional Gaus- sian covariates (where labels are generated via multinomial logistic model), and high-dimensional Gaussian mixture models. Our contributions are listed in more detail below.
1.1 Our Contributions
We establish deterministic sufficient condi- tion under which the multiclass SVM solution has a very simple and symmetric structure: is identical to the solution of the One-vs-All (OvA) SVM classifier that uses the one-hot encoded la- bels. Moreover, the constraints at both solutions are active. Geometrically, this means that all data points are support vectors.
(XXXXX
Tin.
GMM//ML vuffcient oxmpanaattniiniionnn
Vile 14]
True
ovenfining SVM
Thmn.
This implies a surprising equivalence be- tween traditionally different formulations of multiclass SVM, which in turn are equivalent interpolating (MNT) clas-
constrains
Mrlncso-SVM DoA.SVM
Cor
P. Wass)) P.(Wo.)) P.(Wass)
Both Insopodian
to the minimum- sifier on one-hot label vectors. Thus, the out- comes of training with cross-entropy (CE) loss and squared loss are identical.
(.Woo))
Figure I: Contributions and organization.
Next, for data following Gaussian-mixture model (GMM) or a Multinomial logistic model (MLM), we show that the above sufficient condition is satisfied with high-probabilityy under sufficient effective overparameterization depending on the number of classes, and on quantities related the data covariance. Our numerical results show excellent agreement with our theoretical findings
Subsequently, we provide novel bounds on the error of the MNI classifier for data generated either from the GMM or the MLM and characterize overparmeterization conditions under which benign overfitting occurs. A direct outcome of our results that benign overfitting occurs under these conditions regardless of whether the cross-entropy loss squared loss is used during training.

---

Figure 1 describes our contributions and their implications through a flowchart. To the best of our knowledge, these are the first results characterizing a) equivalence of loss functions, and b) generalization of interpolating solutions in the multiclass setting. The multiclass setting poses several challenges over and above the recently studied binary case. When presenting our results in later sections, we discuss in detail how our analysis circumvents these challenges.
1.2 Related Work
Multiclass classification and the impact of training loss functions. There is a classical body of work on algorithms for multiclass classification, e.g., [WW98, BB99, DB95, CSO2, LLW04J and several empirical studies of their comparative performance [RK04, F02, ASSOI] (also see [HYS16 16, GCOZ17. KS18, BEH20, DCO20, HB200, PL20] for recent such studies in the context of deep nets). Many of these (c.g. IRK04, HB20, BEH20 have found that Ieast-squares minimization yields competitive test classification performance to cross-entropy minimization. Our proof of equivalence of the SVM and MNI solutions under sufficient overparameterization provides theoretical support for this line of work. This is a consequence of the implicit bias of gradient descent run on the CE and squared losses leading to the multiclass SVM [SHN+ 18, JT19] and MNI [EHN96] respectively. Numerous classical works investigated consistency [Zha04, LLW04, TB07, PGS13, PS16] and finite- sample behavior, e.g., [KP02, CKMY16, LDBK15, Maul6 LDZK19) of multiclass classification algorithms in the underparameterized regime. contrast, our focus is on the highly overparameterized regime, where the typical uniform convergence techniques cannot apply.
Binary classification error analyses in overparameterized regime. The recent wave of analyses -nomm
of the minimum- -orm interpolator (MNI) in high-dimensional linear regression (an incomplete list is [BLLT20, BHX20, HMRTI9, MVSS20, KLS20J) prompted researchers to consider to what extent the phenomena of benign overfitting and double descent [BHMM19, GJS 20] can be proven to occur in classification tasks. Even the binary classification setting turns out to be significantly more challenging study owing to the discontinuity of the 0 - 1 test loss function. Sharp asymptotic formulas for the generalization error of binary classification algorithms in the linear high-dimenniioal regime have been derived in several recent works [Hual7, SC19, MLC19, SAH19, TPT20, TPT21, DKT21, MRSY19, KA21, LS20, SAH20, AKI AKL7200 Lol20, 21. These formulas are solutions to complicated nonlinear systems of equations that typically do not admit closed-form expressions. A separate line of work provides non-asymptotic error bounds for both the MNI classifier and the SVM classifier [CL21, MNS+ WT21, CGB21]; in particular, [MNS 20] analyzed the SVM in a Gaussian covariates model by explicitly connecting its solution to the MNI solution. Subse- quently, [WT21] also took this route to analyze the SVM and MNI in mixture models, which turn out to be more technically involved. Even more recently, [CGB21] provided extensions of the result by [WT21] to sub- GabbGausiian mixtures. While these non- asn-asymtooiic analyses are only sharp in their dependences on and they provide closed-form generalization expressions in terms of easily interpretable summary statistics. Interestingly, these results imply good generalization of the SVM beyond the regime in which margin-based bounds are predictive. Specifically, [MNS+20 20] identifies a separating regime for Gaussian covariates in which corresponding regression tasks would not generalize. In the Gaussian mixture model, margin-basee bounds [SFBL98, BM03] (as well as corresponding recently derived mistake bounds on interpolating classifiers [LR21]) would require the intrinsic signal-to gegnal-to-noisse to-noise-ratin (SNR) to scale at least as w(p'/2 for good generalization; however, the analyses of [CL21, WT21, CGB21] show that good generalization is possible for significantly lower SNR scaling as w/1 The above eтror analyses are specialized to the binary case, where closed-form error expressions are easy to derive [MNS+ + 20]. The only related work applicable to multiclass settings is [TOS20], which also highlights the numerous challenges of obtaining a sharp error analysis in multiclass settings. Specifically, [TOS20] derived sharp generalization formulas for multiclass least-squares in underparameterized settings; extensions to the overparameterized regime and other losses beyond least-squares remained wide open. Finally, [KT21] recently derived sharp phase-transition thresholds for the feasibility of OvA-SVM on multiclass Gaussian mixture data in the linear high-dimensional regime. However, their result does not cover the more challenging multiclass-S SVM that we investigate here.
The number of support vectors in binary SVM has been characterized in low- dimensional separable and non-separable settings [DOS99, BG01, MO05] and scenarios have been
Other SVM analyses.
3

---

identified in which there is vanishing fraction of support vectors, as this implies good generalization via PAC-Bayes sample compression bounds [Vap13]. In the highly overparameterized regime that we consider, perhaps surprisingly, the opposite behavior occurs: all training points become support vectors with high probability [DOS99, BG01, MO0S, MNS+20. 20, HMX21J. particular, [HMX21] provided sharp non-asymptotic sufficient conditions for this phenomenon for both isotropic and anisotropic settings. The techniques in [MNS*20, HMX21] are highly specialized to the binary SVM and its dual, where a simple complementary slackness condition directly implies the property of interpolation. In contrast, the complementary slackness condition for the case of multiclass SVM does not directly imply interpolation; in fact, the operational meaning "all training points becoming support vectors" is unclear in the multiclass SVM. Our proof of deterministic equivalence goes beyond the complementary slackness condition and uncovers surprising symmetric structure" by showing equivalence of multiclass SVM to a symmetric OvA classifier.
Notation For vector v IR",, let |v|l2 VVi= |Ivl], = Ei= leall | = max; {|:
> 0 is interpreted elementwise. 1/0 denote the all-ones / all-zeros vectors and e; denotes the i-th standard basis vector. For a matrix M. || denotes its - 2 operator norm and ||M]] denotes the Frobenius norm. @ denotes the Hadamard product. [n] denotes the set
n).
We also use standard "Big O" notations (.). w(.), e.g., see [CLRS09, Chapter 3). Finally, we write N ((,, Σ) for the (multivariate) Gaussian distribution of mcan μ and covariance matrix Σ, and, Q(x) = P(Z > x), ~ (0, 1) for the Q-function of a standard normal. Throughout, constants refer to numbers that do not depend on the problem dimensions or p.
2 Problem setting
We consider the multiclass classification problem with & classes. Let x E RRP denote the feature vector and y E [k] represent the class label associated with one of the h classes. We assume that the training data has n feature/ /label pairs {x,, 3= We focus on the overparameterized regime, i... p > Cn, and will frequently consider p > n. For convenience, one-hot coding vector y; E g², where only the y:-th entry of y; is I and all other entries are zero, i.., y; Cy. With this notation, the feature and label matrices are given in compact form follows:
express the labels using the
x= = [1 X2 ... Xn] E R2'n and Y = ly Y2 ... ynl [v1 V2 v..''' E Rkxn
where we have defined V. E R",Ca E [k]] to denote the e-th row of the matrix Y.
2.1 Data models
We assume that the data pairs (xx, M/ )-=1 are generated IID. We will consider two models for the distribution of (x, y). For both models, we define the mean vectors { 1/ E IR,, and the mean
matrix is given by M := [M] H2
[y] E RP**
Gaussian Mixture Model (GMM), In this model, the mean vector μt; represents the conditional mean vector for the i-th class. Specifically, each observation (x,, y/) belongs to to class e E [k] with probability Te and conditional on the label ys, follows multivariate Gaussian distribution. In summary, we have
P(y = c) = ne and x = M, + q, q ~ NN Σ).
(I)
In this work, we focus on the isotropic case Σ = Ip- Our analysis can likely be extended to more general settings, but we leave this to future work.
Multinomial Logit Model (MLM). In this model, the feature vector x E R follows N00, E), and the conditional density of the class label y is given by the soft-max function. Specifically, we have
(0, Σ) and P(y c/x) = exp(μ
Σ exp(ux,x))
(2)
jE(N]
For this model, we analyze both the isotropic and anisotropic cases.
"In this context, the fact that [MNS* 20, WT21] provide good generalization bounds in the regime where support vectors proliferate particularly surprising. In conventional wisdom. a proliferation of support vectors was associated with overfitting but this turns out to not be the case here.
"This symmetric structure is somewhat reminiscent of the recently observed neural collapse phenomenon in deep neural networks [PHD20]. although the details of the obtained solutions quite different.

---

2.2 Data separability
wx)" RR Given input feature vector x, the classifier is function that maps x into an output of k via² x Wx E R We will operate in a regime where the training data are linearly separable. In multiclass settings, there exist multiple notions of separability. Here, focus one-vs-all (OvA) separability, and, recall their definitions below.
We consider linear classifiers parameterized by W [W1 W2
multiclass/k-class separability (ii)
Definition (multiclass and OvA separability). The dataset (xi, ya NEjn) is multiclass linearly sepa-
rable when EW [w,, W2,- - ... w&]" R (Wy. -We)² Tx; 2 1, Ve + Vi, E [R]), and Vi E
[n]. The dataset is one-vs-all (OvA) separable when =W = =[11, W2. Wal" E Rxxp w x 2 1
if y; = and w"
wxxx x; I if y + c, Ve E [ks], and Vi [n].
In the overparameterizee regime p > with Gaussian data, we have rank almost surely, which implies OvA separability. It turns out that OvA separability implies multiclass separability, but not vice versa (sce [BM94] for counterexample).
2.3 Classification error
Consider linear classifier W and a fresh sample (x, y) generated following the same distri- bution the training data, As is standard, we predict ý by "winner takes all strategy". ie.. V = arg maXje(k] W Then, the classification error conditioned on the true label be- ing c, which we refer to as the class-wise classification error, is defined as Pele := PP * ply
P(WTx I maxfze w x). In turn, the total classification error is defined as F. Fÿ + y) P(arg ma W/ x + y) P(W, x S maxj W]xx) x).
2.4 Classification algorithms
Next, review several different training strategies for which we characterize the total/class-wise classification error in this paper.
Multiclass SVM. Consider training W by minimizing the popular cross-entropy (CE) loss L(W) == log (e">," /Eme(M) e w with the gradient descent algorithm (with constant step size 11)- In the separable regime that we consider, the CE loss L(W) can be driven to zero. Moreover, [SHN+18, Thm. 7] showed that the normalized iterates (W"r22 converge as lim;-xo W WsvM 0, where Wsvm is the solution of the multiclass SVM [WW98] given by
Wsvm == arg min W| sub. to (wy. W.) 1, Vi [n], [k] s.t. c yi.
One-vs-all SVM. contrast to Eqn. (3) that optimizes the hyperplanes {Wa)oe[s jointly, the one-
vs-all (OvA)-SVM classifier solves l separable optimization problems maximizing the margin of each class with respect to all the rest. Concretely, the OvA-SVM solves for all [k]:
WOvA. == arg min [w|]2 sub. to wTx; x; 2
if ys w < -1
if 11
+ c, Vi V (4)
In general, the solutions to Equations (3) and (4) are different. While the OvA-SVM does not have an obvious connection to any training loss function, its relevance will become clear Section 3. Perhaps surprisingly, we will prove that in the highly overparameterized regime the multiclass SVM
solution is identical to slight variant of (4).
Min-norm interpolating (MNI) classifier. An alternative to the CE loss is the square loss L(W)= 2n Σn= Wx, - 1.. While the square-loss appears to be more tailored to regression, it in fact has competitive classification accuracy the CE loss in practice [Rif02, HB20, PL20]. Since rank(X) X) = n almost surely, the data can be lincarly interpolated, i.c. the square-loss
1 Y W 12 1
2n
3 For simplicity, we ignore the bias term throughout. "Note that the scaling factor log t here does not depend on the class label; hence, in the limit of GD iterations. the solution a decides the same label as multiclass SVM for any test sample.
5

---

can be made zero. Then, it is well-known [EHN96] that gradient descent with sufficiently small step size and appropriate initialization converges to the minimum -ormmmmm-oonm norm -interpolating (MNI) solution:
WNNI := arg min W sub. to X²w w = Ve. VC E [K]]
(5)
W
Since x X is invertible, the solution above is given in closed form as W MNI X(X"X) From here on, we refer to (5) as the MNI classifier.
3 Proliferation of support vectors
In this section, we show equivalence of the solutions of the three classifiers defined above,
3.1 A key deterministic condition
We first establish a key deterministic property of SVM that holds for generic multiclass datasets (X, Y) (not necessarily generated by either the GMM or MLM), as long as rank(X) = n. Specif- ically, Theorem 1 below derives sufficient condition (ef. (8)) under which the multiclass SVM solution has a surprisingly simple structure. First, the constraints are all active at the optima (cf. (9)).
Second, and perhaps more interestingly, the equality of the constraints is satisfied in very symmetric way such that (ef. (10)) for all E [m].c E [k:], we have
(k 1)/k
, y/i
W x Zei
(6)
111
.C ys
Theorem 1. For a multiclass separable dataset with feature matrix X = [x X2....... ....... x,, E R and label matrix Y = [V1, V2...., V&]T E R&xn, let W
[11, W2..... w be the multiclass
SVM solution in (3). For each class c E [k] define vectors Ze E I2" such that
2e = Ve (1/k))n, CE [k]]
Assume that the Gram matrix X2 X invertible and that the following condition holds
Ze O (x" xx"'x)-+2. >0, O, Vc E [K]]
(8)
Then, the SVM solution W svM is such that all the constraints in (3) are active. That is,
(wy. w.)x x; = 1, Wc + yo [k], and Vi [m].
(9)
Moreover, it holds that
X W. =c, Vc E [k).
(10)
For classes, it can be checked that Eqn. (8) reduces to the condition in Eqn.(22) of [MNS+ 20] for the binary SVM. Compared to the binary setting, the conclusion for multiclass is richer: provided that Eqn. (8) holds, not only do we show that all data points are support vectors, but also, that they satisfy set of symmetric OvA-type constraints. The proof of Eqn. (10) is particularly subtle and involved: unlike in the binary case, it does not follow directly from a complementary slackness condition on the dual of the multiclass SVM. We provide short proof sketch in Section 3.1.1 and defer details to the supplementary material (SM).
We make the following additional remarks on the interpretation of Eqn. (10). First, our proof shows a somewhat stronger conclusion: when inequality (8) holds, the multiclass SVM solutions Wey c E [k] are same as the solutions to the following symmetric OvA OvA-type classifier (cf. Eqn. (4)):
min We
/ell2
sub. to x We
(k 1)/k
Ii C, Vi [n],
(11)
< 1/k
3344 + c,
for all e E [b]. The OvA-type classifier above can be interpreted binary cost-sensitive SVM classifier [IMSV19] that enforces the margin corresponding to all other classes to be (A- - 1) times smaller compared to the margin for class c.
The second remark regarding (10) is crucial for the rest of this paper. Precisely, (10) shows that when (8) holds, then the multiclass SVM solution W Wsv has the same classification error as that of the minimum-norm interpolating solution. This conclusion, stated as a corollary below, drives our classification error analysis in Section 4.

---

Corollary (SVM-MND. Under the same assumptions as in Theorem 1, and provided that the inequality in Eqn. (8) holds, it holds that Peje[W sVM) P. cl (W MNI) for all e [k]. Thus, the total classification errors of both solutions are equal: Pe( (W SVM) P.( MNT).
Proof sketch. First, it follows from Eqn. (10) that We, C E [k:] coincides with the unique solution of a MNI classifier on shifted labels, given by We = We == X(X")) ''ze. Second, using the affine relation between Ze and Ve in Eqn. (7), we get Pejo( (W = Pejel WMNI), where we denote
W MNI Wi,...., WE]. This completes the proof of the corollary. More details given in the SM. M
3.1.1 Proof sketch of Theorem
To prove Theorem 1, we constructed a new parameterization of the dual of the multiclass SVM (given in Eqn. (14)). Letting dual variables (Ac.s) for every [m], E [R] : c # yi corresponding to the constraints on the primal form in (3), the standard form of the dual of multiclass SVM is written as
max 2
Σ
Σ
Σ
d )ess)x
Σ
de,0x:112
(12)
2
(E(n)
(E(K)
(E(m]
Let do, be the maximizers in Eqn. (12). By complementary slackness, we have
de = (wy, - w.) Tx; 1.
(13)
Thus, to prove Eqn. (9), it will suffice showing that A 0, Vi E [n], c y: provided that Eqn. (8) holds. The challenge is that is hard to work directly with (12) because the variables Ae.; are coupled within the objective. Our key idea is to re- ee-prameeteiize the dual objective in terms of new variables Be, and of coefficients involving the vectors z. we introduced in Eqn. (7). Deferring the detailed derivations to the SM, we can show that (12) is equivalent to the following program:
max B.ERR
ΣBT
|xBa112
(14)
2
CE|K]
sub. to
Bosd --
-
Bess Vi [m] and 0.02.3 2....000 0, Vc [A),
where, for each E [k] we let B, are related to the original ones that
Ponl E R.. Moreover, the new dual variables
Be, > 0 + de, > 0, for all c E [k] and i E [m] : yo + c.
(15)
The next step is to consider the unconstrained maximizer in (14), that is 3. = (X*X)-12,, -ee Ve E [k], [k]] is feasible in (14). Skipping the detailed argument here, by doing so, we prove that Ba, c E [k] in fact the unique optimal solution of (14). But now, realizing that Eqn. (8) is equivalent to 2, @ B, > O, we have found that 3,, E [k] further satisfies the n strict inequality constraints in (14). Thus, from Eqn. (15), the original dual variables { (Xe,e) are also all strictly positive, which completes the proof of the first part of the theorem (Eqn. (9)).
and show that Ber c E
Next, we outline the proof of Eqn. (10). We consider the OvA-classifiee in (11). The proof has two steps. First, using similar arguments to what was done above, we show that when Eqn. (8) holds, then all the inequality constraints in (11) are active at the optimal. That is, the minimizers Wsym-OwA,c of (11) satisfy Eqn. (10). Second, to prove that Eqn. (10) is satisfied by the minimizers w. of the multiclass SVM in Eqn. (3), need to show that Wsym-OvA.e w. for all
[k]. We do this by showing that, under Eqn. (8), the duals of (3) and (11) are equivalent. By strong duality, the optimal costs of the primal problems are also the same. Then, because the objective is the same for the two primals and because w is feasible and (3) is strongly convex, we can conclude with the desired.
3.2 Connection effective overparameterization
Theorem I establishes deterministic condition that applies to any multiclass separable dataset as long as the data matrix X is full-rank. In this subsection, we show that the inequality (8) occurs with high- probability under both the GMM and MLM models for data, with sufficient overparameteriiaaton..
7

---

Fracsin support veotteeectte
Fradiio oi sapeee S
Erecton suppon
140
191 0.3
[k
(a)
(b)
Figure 2: Fraction of support vectors satisfying Eqn. (10). (a) GMM: k 4 and 7, (b) MLM: 3, 4, 6. In (a), "(4) 0.2" means 4 classes and || vp= 0.2. The curves nearly overlap when plotted versus 11.6n11.5 | 1l as predicted by the second condition in Eqn. (16) of Theorem 2. In (b), the curves overlap when plotted versus 2 log( wkn)/r pp as predicted by Thm. 4.
3.2.1 Gaussian mixture model
We focus on an equal-energy, equal-prior setting for ease of exposition. Our proofs extend rather naturally to more general settings, but the results are more complicated to state and offer no new insights for our purpose.
Assumption (Equal energy/prior). The mean vectors have equal energy and the priors are equal, i.e. we have ||l| == lll and ग.e = π = 1/k, for all c E [k:].
Theorem 2. Assume that the training set follows a multiclass GMM with Σ Ip and Assumption and that the number of training samples n. is large enough. There exist constants C2, C3 > 1 and C1, C2 >
such that inequality (8) holds with probability at least 9 c2ke ogh? provided that
p C2 log(kn) +n -n-1 and p p> 5 1|
(16)
Our theorem establishes a set of two conditions under which inequality (8) and the conclusions of Theorem 1 hold, i.e. Wsvm W MN.. The first condition requires sufficient overparameterization p = 2 (og(k))), while the second one requires that the signal strength is not too large. Intuitively, we can understand these conditions as follows. Note that inequality (8) is satisfied provided that the inverse Gram matrix (X= is "close" to identity, or any other positive-definit diagonal matrix. (This is the proof strategy that is also followed in [MNS 20] for the of Gaussian features; here, we show this for the more difficult mixture-ou of Gaussians case.) Recall from Eqn. (1) that = MY - Q = Ej= v3 + Q where Q is p X standard Gaussian matrix. Our theorem's 's first condition sufficient for (Q"Q)-1 have the desired property; the major technical challenge is that (X" involves additional terms that intricately depend on the label matrix Y itself. Our key technical contribution is showing that these extra terms do not drastically change the desired behavior, provided that the norms of the mean vectors are well controlled. At high-level we accomplish this with recursive argument as follows. Denote X Q and X; = ブj= 1 M4 v + Q for i E [k].
Then, at each stage of the recursion, show how to bound quadratic forms involving (X?X,)
using bounds established previously at stage i 1 on quadratic forms involving (xf, x11) A critical property for the success of our proof strategy is the observation that the rows of Y are always orthogonal, that is, vf vf'v = 0, for + j. The complete proof of the theorem is given in the SM.
Next, we present numerical results that confirm our theoretical statement. We also discuss the tightness of the two sufficient conditions in Eqn. (16). Throughout the paper, in all our figures, we show averages over 100 Monte-Carlo realizations. In Fig. 2(a), we plot the fraction of training points in the multiclass SVM satisfying Eqn. (10) as function of training size n for h = 4 and k = 7 classes (please see SM for other experiment details and more results). To verify the second condition in Eqn. (16), Fig. 2(a) also plots the same set of curves over re-scaled axis ks' 1-15%,1-1/pp 1///l//pp.... The curves corresponding to different settings nearly overlap in this new scaling, which suggests the correct order of the corresponding condition. We conjecture that our second condition is tight up to an extra /n factor which we believe an artifact of the analysis. We also believe that the 1.3 factor in the first condition be relaxed slightly to 2 (as is done for the MLM case; see Fig. 2(b)).

---

3.2.2 Multinomial logistic model
We now consider the MLM data and the anisotropic setting. The eigendecomposition of the covariance matrix is given by Σ = Ei=1 uu where À = , .. Ap]. Following [HMX21], we also define the effective dimensions d2 == [AIl/||A|B and d := | The following result contains sufficient conditions for the SVM and MNI solutions to coincide.
Theorem 3. Assume a training samples following the MLM defined in (2). There exist constants
and C₁, C2 > such that inequality (8) holds with probability at least (1 - a.) provided that doe > C,k2n log(kn) and d2 > C2 (log(kn) + n). In fact, the only conditions we require on the generated labels conditional independence.
The sufficient conditions in Theorem require that the spectral structure in the covariance matrix E has sufficiently slowly decaying eigenvalues (corresponding to sufficiently large d2), and that it is not too "spiky" (corresponding to sufficiently large doe)). For the special case of k 2 classes, our conditions reduce to those in [HMX21] ] for binary classification; in fact under the MLL model we can leverage a more sophisticated deterministic equivalence to Eqn. (8) provided in that work. The dominant dependence on k, given by h?, is a byproduct of the "unequal" margin in (6). Fig. 2(b) empirically verifies the tightness of this factor. For the isotropic case Σ Ip. we can prove slightly sharper result in logarithmic factors, which we state next.
Theorem 4. Assume samples from the MLM with Σ = =Ip There exist constant > 1 such that inequality (8) holds with probability at least (1 :.) provided that p > 10k2nlog V kn) + n 1.
Our numerical results Fig. 2(b) suggest that this sufficient condition is order-wise tight. Specifically, in Fig. 2, we fixed = 1000, varied n from 10 to 100 and the numbers of classes from k = 3 to k 6. We chose orthogonal mean vectors for each class with equal energy | = p. Fig. 2(b) shows the fraction of training points in the multiclass SVM satisfying Eqn. (10) as function of n. Clearly, smaller & results in higher proportion of support vectors for the same number of measurements n. To verify the condition in Theorem 4, Fig. 2(b) plots the same curves over re-scaled axis n log( /kn//p /p (as suggested by 4hm.4). These curves nearly overlap.
4 Generalization bounds and benign overfitting
In this section, we derive non-asymptotic bounds on the error of the MNI classifier, and discuss sufficient conditions for the multiclass SVM to satisfy benign overfitting. We focus the case of GMM data due to space constraints, and discuss corresponding results on MLM data in the SM.
4.1 Generalization bounds for the MNI classifier
We present classification error bounds under the additional assumption of orthogonal means for ease of exposition this can be relaxed with some additional work as described in the SM.
Assumption 2 (Orthogonal means). In addition to Assumption 1, assume that the means are orthog- onal, that is p.d μt 0, for all + E [k)].
Theorem Let Assumption and condition in (1n.(16) hold. Further assume constants
C1,C2, C3 > 1 such that (1 C1 -CCm || > C3Vi. Then, there exist additional constants
C2,02,Cs and C2 > 1 such that Pelc S (k - 1)exp (- |1 (a1 C1 ve
- -Cal)) with prob-
Calllaal 52)
ability at least classification error P.
ozke egk? ,ar2,for every E [k]. Moreover, the same bound holds for the total
For large enough and finite n, our bound reduces to the results in [WT21, CGB21] when k 2 (with slightly different constant numbers). There are two major challenges in the proof, which is presented in the SM. First, in contrast to the binary case the classification error does not simply reduce to bounding correlations between vector means H. and their estimators w.. Second, just in the proof of Theorem 2, technical complications arise from the multiple mean components X. We use variant of the recursion-based argument described in Section 3.2.1 I to obtain our final bound.

---

4.2 Conditions for benign overfitting
In our results thus far, we have studied the classification error of the MNI classifier (Theorem 5). and shown equivalence of the multiclass SVM and MNI solutions (Theorems 1, 2 and Corollary 1). Combining these results, we now provide sufficient conditions under which the classification error of the multiclass SVM solution (also of the MNI) approaches 0 as model size p increases.
Let the same assumptions as in Theorem 5 hold. Then, for finite number of classes and finite sumple size n, there exist positive constants 's and C,'s s >> 1, such that the multiclass SVM classifier SVM in (3) satisfies the symmetric interpolation constraint in (10) and its total
Corollary 2.
classification error approaches 0 as p with probability at least 1 S -o2ke ogk? provided (1/4,1).
||al|2 ) for
We compare our result with the binary case result in [CL21, WT21, CGB21J. When it and n are both finite, condition | = O(r") for 3 E (1/4, 1) is the same as the bi- nary result. Note that, like in the binary case, Corollary 2 applies beyond the regime which margin-bounds would be predictive of good gen- cralization, which would require 3 E (1/2, 1).
Fracton of support vedorr
Cesstiaan eroo
0.30
04
250
7.00
1003
400
1000
We now present numerical illustrations validat- ing our results. We set the number of classes k 4, fix = 40, and vary p 50..... 1200 to guarantee sufficient overparameterization. We consider the case of orthogonal and equal- norm mean vectors ||1||2 = MvD, with μ = 0.2, 0.3 and 0.4. In Fig. 3. we plot the classi- fication error as a function of p for both MNI estimates (solid lines) and multiclass SVM solutions (dashed lines). As dashed curves almost overlap. Further, as p increases, we see that the classification error decreases towards zero. Fig. 3 shows the fraction of support vectors satisfying (10) among all the constraints in (3). We see that the classification error goes to zero very fast when μ is large, but the proportion of support vectors increases at slow rate. In contrast, when μ is small, the proportion of support vectors increases fast, but the classification error decreases slowly.
Figure 3: The plot shows the classification error and fraction of support vectors with k 4. We can see the classification errors approach 0 and the fractions support vectors approach 1 as p gets larger. Different colors correspond to different mean norms.
expect, the solid and
Conclusion and future work
Our work provides, to the best of our knowledge, the first results characterizing a) equivalence of loss functions, and b) generalization interpolating solutions in multiclass settings. Like almost all benign overfitting analysis,
techniques are tailored to high-dimensional linear models with Gaussian or independent sub-Gaussian features. Extending these results to kernel machines and other nonlinear settings is of substantial interest. It would also be interesting explore the potential connections of the symmetric structure shown in Theorem with the recently discovered neural collapse phenomenon on deep nets [PHD20].
6
Acknowledgements
This work is partially supported by the NSF under Grant Number CCF-2009030 and by a CRG8 award from KAUST. C. Thrampoulidis would also like to recognize his affiliation with the University of California, Santa Barbara. The authors would like to thank the anonymous reviewers for helpful discussion and suggestions.
References
[AKLZ200]
Benjamin Aubin, Florent Krzakala, Yue Lu, and Lenka Zdeborová. Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances
10

---

in Neural Information Processing Systems, volume 33, pages 12199-12210 Curran Associates, Inc., 2020.
[ASS01] Erin L. Allwein, Robert E. Schapire, and Yoram Singer. Reducing multiclass to binary: unifying approach for margin classifiers. Journal of Machine Learning Research, 1:1 1:113-141, September 2001.
[BB99] Erin Bredensteiner and Kristin Bennett. Multicategory classification by support vector machines. In Computational Optimization, pages 53-79. Springer, 1999.
[BE220] Anna Sergeevna Bosman, Andries Engelbrecht, and Mardé Helbig. Visualising basins of attraction for the cross-entropy and the squared error neural network loss functions. Neurocomputing. 400:113-136, 2020.
[Ber09] Dennis S Bernstein. Matrix mathematies: theory, facts, and formulas. Princeton university press, 2009.
[BG01] Arnaud Buhot and Mirta B Gordon. Robust learning and generalization with support vector machines. Journal of Physics A: Mathematical and General, 34(21)443774338 May 2001.
[BHMМ19] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-leaming practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 118(32):15449-1553) 158544 2019.
[BHX20] Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4): (47:11177-1180, 2020.
[BLLT20] Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):3003330000 2020.
[BM94] Kristin P. Bennett and O.L. Mangasarian. Multicategory discrimination via linear programming. Optimization Methods and Software, 3(1-3):27-39, 1994.
[BM03] Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463 482, March 2003.
[CGB21] Yuan Cao, Quanquan Gu, and Mikhail Belkin. Risk bounds for over-parametterized max- imum margin classification on sub-Gaussian mixtures. arXiv preprint arXiv:2104.13625 2021.
[CKMY16] Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, and Scott Yang. Structured predic- tion theory based on factor graph complexity. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
[CL21] Niladri S Chatterji and Philip M Long. Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. Journal of Machine Learning Research, 22(129):1-30, 2021.
[CLRS09] Thomas H. Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Intro- duction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009.
[CS02] Koby Crammer and Yoram Singer. On the algorithmic implementation of multiclass kernel-based vector machines. Journal of Machine Learning Research, 2:265-292, March 2002.
[DB95] Thomas G. Dietterich and Ghulum Bakiri. Solving multiclass learning problems via error-correcting output codes. Journal of Artificial Intelligence Research, 2(1):263-286, January 1995.
11

---

[DCO20] Ahmet Demirkaya, Jiasi Chen, and Samet Oymak. Exploring the role of loss functions in multiclass classification. In 2020 54th Anmual Conference on Information Sciences and Systems (CISS), pages 1-5, 2020.
[DKT21] Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high-dimensional binary linear classification. Information and Inference: A Journal of the IMA, April 2021.
[DI.20] Oussama Dhifallah and Yue M Lu. A precise performance analysis of learning with random features. arXiv preprint arXiv:2008. 1904, 2020.
[DOS99] Rainer Dietrich, Manfred Opper, and Haim Sompolinsky. Statistical mechanics of support vector networks. Physical Review Letters, 02:2975-2978 Apr 1999.
[EHN96] Heinz Werner Engl, Martin Hanke, and Andreas Neubauer. Regularization of inverse problems, volume 375. Springer Science & Business Media, 1996.
[F02] Johannes Fürnkranz. Round robin classification. Journal of Machine Learning Research, 2:721-747, March 2002.
[GCOZ17] Krzysztof Gajowniczek, Leszek J. Chmielowski, Arkadiusz Orlowski, and Tomasz Zabkowski. Generalized entropy cost function in neural networks. In Alessandra Lintas, Stefano Rovetta, Paul F.M.J. Verschure, and Alessandro E.P. Villa, editors, Artificial Neural Networks and Machine Learning - ICANN 2017, pages 128-136, Cham, 2017. Springer International Publishing.
[GJS+20) Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d' Ascolii Giulio Biroli, Clément Hongler, and Matthieu Wyart. Scaling description of generalization with number of parameters in deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2020(2):024011, February 2020.
[HB20] Like Hui and Mikhail Belkin. Evaluation of neural architectures trained with square loss vs cross-entropy in classification tasks, arXiv preprint arXiv:2006.077 2020.
[HJ12] Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, USA, 2nd edition, 2012.
[HMRT19] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation. arXiv preprint arXiv:1903.08566 2019.
[HMX21] Daniel Hsu, Vidya Muthukumar, and Ji Xu. On the proliferation of support vectors in high dimensions. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statisties, volume 130 of Proceedings of Machine Learning Research, pages 91-99. PMLR, 13-15 Apr 2021.
[Hua17] Hanwen Huang. Asymptotic behavior of support vector machine for spiked population model. Journal of Machine Learning Research, 18(45):1-21, 2017.
[HYS16] Le Hou, Chen-Ping Yu. and Dimitris Samaras. Squared earth mover's distance-basel loss for training deep neural networks. arXiv preprint arXiv:1611.059) 2016.
[IMSV19] Arya Irammehr, Hamed Masnadi- -hirrazi,, and Nuno Vasconcelos. Cost-sensitive support vector machines. Neurucomputing, 343:50-64, 2019.
[JT19] Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 1 1772-1798, Phoenix, USA, 25-28 Jun 2019. PMLR.
[KA2]] Abla Kammoun and Mohamed-So Slim Alouini. On the precise error analysis of support vector machines. IEEE Open Journal of Signal Processing, 2:99-118, 2021.
12

---

[KLS20] Dmitry Kobak, Jonathan Lomond, and Benoit Sanchez. The optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization. Journal of Machine Learning Research, 21 2020.
[KPO2] V. Koltchinskii and D. Panchenko. Empirical Margin Distributions and Bounding the Generalization Error of Combined Classifiers. The Annals of Statistics, 30(1):1 - -50, 2002.
[KS18] Himanshu Kumar and S. Sastry. Robust loss functions for learning multi-class classifiers. In 2018 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 687-692, 2018.
[KT21] Ganesh Ramachandra Kini and Christos Thrampoulidis. Phase transitions for one-vs- one and one-vs-all linear separability in multiclass gaussian mixtures. In ICASSP 2021 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4020-4024, 2021.
[LDBK15] Yunwen Lei, Urun Dogan, Alexander Binder, and Marius Kloft. Multi-class svms: From tighter data-dependent generalization bounds to novel algorithms. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[LDZK19] Yunwen Lei, Ürün Dogan, Ding-Xuan Zhou, and Marius Kloft. Data-dependent gen- eralization bounds for multi-class classification. IEEE Transactions on Information Theory, 65(5):2995-3021, 2019.
[LLW04] Yoonkyung Lee, Yi Lin, and Grace Wahba. Multicategory support vector machines. Journal of the American Statistical Association, 99(465))67-81, 2004.
[Lo]20] Panagiotis Lolas. Regularization in high-dimennsional regression and classification via random matrix theory. arXiv preprint arXiv:2003.13723, 2020.
[LR21] Tengyuan Liang and Benjamin Recht. Interpolating classifiers make few mistakes. arXiv preprint 0rXiv:210I.11811 2021.
[LS20] Tengyuan Liang and Pragya Sur. A precise high sigh-dimensional asymptotic theory for boosting and min-ll-non interpolated classifiers. arXiv preprint arXiv:2002.0155 2020.
[Mau16] Andreas Maurer. A vector-contraction inequality for rademacher complexities. In Ronald Ortner, Hans Ulrich Simon, and Sandra Zilles, editors, Algorithmic Learning Theory, pages 3-17, Cham, 2016. Springer International Publishing.
[MLC19] Xiaoyi Mai, Zhenyu Liao, and Romain Couillet. A large scale analysis of logistic regression: Asymptotic performance and new insights. In ICASSP 2019 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages
[MNS+20] Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification vs regression in overparameterized regimes: Does the loss function matter? arXiv preprint arXiv:2005.08054 2020.
[MO05] Dörthe Malzahn and Manfred Opper. statistical physics approach for the analysis of machine learning algorithms on real data. Journal of Statistical Mechanics: Theory and Experiment, 2005(11):P) 11101-1P1111111110 1001, nov 2005.
[MRSY19] Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan. The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime. arXiv preprint arXiv: 19110559 2019.
[MVSS20] Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harm- less interpolation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory, 2020.
13

---

[PGS13] Bernardo Avila Pires, Mohammad Ghavamzadeh, and Csaba Szepesvári. Cost-sensitive multiclass classification risk bounds. Proceedings of the 30th International Confer- ence on International Conference on Machine Learning- Volume 28, ICML' page I11-1391-111-133 Jorg. 2013.
[PHD20] Vardan Papyan, X. Y. Han, and David L. Donoho. Prevalence of neural collapse during the terminal phase deep learning training. Proceedings of the National Academy of Sciences,
24663, 2020.
[PL20] Tomaso Poggio and Qianli Liao. Explicit regularization and implicit bias in deep network classifiers trained with the square loss. arXiv preprint arXiv:2101.0007 2020.
[PS16] Bernardo Ávila Pires and Csaba Szepesvári. Multiclass classification calibration func- tions. arXiv preprint arXiv: 1rXiv:1609.00 (e0e:::090005500 669906683, 2016.
[RDS 15] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-253 2015.
[Rif02] Ryan Michael Rifkin. Everything old is new again: a.fresh look at historical approaches in machine learning. PhD thesis, MaSSachuSettS InStitute of Technology. 2002.
[RK04] Ryan Rifkin and Aldebaro Klautau. In defense of one-vs-all classification. Journal of Machine Learning Research, 5:101-141, 2004.
[RV+13] Mark Rudelson, Roman Vershynin, al. Hanson wright inequality and sub-gaussian concentration. Electronic Communications in Probability, 18, 2013.
[SAH19] Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The impact of regularization on high- nigh-dimensional logistic regression. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Bue, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[SAH20] Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The performance analysis of generalized margin maximizers separable data. In International Conference on Machine Learning, pages 8417-8426. PMLR, 2020.
[SC19] Pragya Sur and Emmanuel Candès. A modern dimensional logistic regression. Proceedings of the National Academy of Sciences, 116129):4511-11455, 2019.
theory for high-
[SFBL98] Robert E Schapire, Yoav Freund, Peter Bartlett, and Wee Sun Lec. Boosting the margin: A new explanation for the effectiveness of voting methods. The Annals of Statistics, 1665)11651-1666 1998.
[SHN+ 18] Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 191):2222-288 2018
[TB07] Ambuj Tewari and Peter L Bartlett. On the consistency of multiclass classification methods. Journal of Machine Learning Research, 8336;1007-1025,, 2007.
[TB20] Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. arXiv preprint arXiv:2009. 14286, 2020.
[TOS20] Christos Thrampoulidis, Samet Oymak, and Mahdi Soltanolkotabi. Theoretical insights into multiclass classification: high-dimensional asymptotic view. In Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural In- formation Processing Systems, volume 33, pages 8907-8920. Curran Associates, Inc., 2020.
14

---

[TPT20] Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis. Sharp asymptotics and optimal performance for inference in binary models. In Silvia Chiappa and Roberto Ca- landra, editors, Proceedings of the Twenty Third International Conference Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 3739-3749. PMLR, 26-28 Aug 2020.
[TPT21] Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis. Fundamental limits of ridge-regularized empirical risk minimization in high dimensions. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 2773-2781. PMLR, 13-15 Apr 2021.
[Vap13] Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
[Wai19] Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, vol- ume 48. Cambridge University Press, 2019.
[WT21] Ke Wang and Christos Thrampoulidis. Binary classification of gaussian mixtures: Abundance of support vectors, benign overfitting and regularization. arXiv preprint arXiv:201 1.09/48, 2021.
[WW98] Jason Weston and Chris Watkins. Multi-class support vector machines. Technical report, Citeseer, 1998.
[Zha04] Tong Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1):56-85, 2004.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the pa- per's contributions and scope? [Yes] We provide a point-by-point description of our contributions in Section 1.1 that reflect the abstract and introduction.
(b) Did you describe the limitations of your work? [Yes] We introduce the background and list all the assumptions in the paper. We also discuss limitations and scope for future work in context with the main results as well as the conclusion.
(c) Did you discuss any potential negative societal impacts your work? [N/A] This paper contains purely theoretical analysis that aims to explain the performance of modern ML models, and does not contribute new methodology. Thus, it is unlikely to have either positive negative social impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Our assump- tions stated in Sections and 4.
(b) Did you include complete proofs of all theoretical results? [Yes] We present a proof sketch in the main text and include the complete proofs in the supplementary material.
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
URL)? [Yes] We include the code that creates the figures in our paper and will submit it as supplementary material. We note that the main contributions of our paper theoretical, and our simulations on synthetic are intended to support these results rather than constitute results.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? YYs]] We specify our model settings and how we design the experiments, ie.. number of random samples, parameter values, in paper.
15

---

(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] We report the results with standard deviation in the supplementary material.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
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 cite the creators? [N/A] Not using existing assets or releasing new assets.
(b) Did you mention the license of the assets? [N/A] Not using existing assets or releasing
new assets.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A] Not using existing assets releasing assets.
(d) Did you discuss whether and how consent was obtained from people whose data you're you're using/curating? [N/A] Not using existing assets or releasing new assets.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] Not using existing assets or releasing new assets.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A] We did not crowdsourcing conduct research with human subjects.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] We did use crowdsourcing or conduct research with human subjects.
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A] We did not use crowdsourcing or conduct research with human subjects.
16


Reviews:
[{"review_id": "taWWKWW0Z6c", "reviewer": "Reviewer_k5ri", "summary": "“Benign overfitting” is a recently revealed phenomenon that high-dimensional models achieving zero training loss can still have good generalization. Existing works studying benign overfitting are mostly focused on the regression setting or the binary classification setting. In this paper, the authors establish benign overfitting guarantees for multi-class classification problems. It is shown that empirical risk minimization with cross-entropy loss is equivalent to the min-norm interpolating (MNI) solutions and the one-vs-all SVM classifier, and then derive error bounds on the accuracy of the MNI classifier. ", "questions": "", "limitations": "", "rating": 5, "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": "I think the analysis in this paper is interesting. Although I did not fully check all the proofs, the results in this paper seem to be sound. However, I have the following concerns about this paper.\n\n- I am not sure if the results in this paper are novel enough. In fact, the difference between this paper and previous works, i.e., multi-class classification versus binary classification, may be quite incremental. The proof technique in this paper seems to be quite similar to previous works on binary classification as well. Moreover, it is in fact not very clear whether there is any advantage of using the multi-class cross-entropy loss. It seems that if one solves multiple binary classification problems separately, and derive error bounds using the results in [WT20], the result could be better: the (k-1) factor in the bound of Theorem 5 won’t change, and the k in the bound will simply be improved to a constant. For these reasons, I feel that the contribution of this paper may be limited to the extension to the multinomial logistic model.\n\n- It is also not very convincing whether the conditions in Theorem 2 are tight in k. The condition p = \\Omega(k^3 n) requires a very large dimension p, and since n is already the total number of training data (not the number of data per class), the dependency of p on k is quite bad. In the experiments in Figure 2, the authors only checked the tightness of the second condition in (16).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "rk0BSqSmHE-", "reviewer": "Reviewer_YfRx", "summary": "In this paper, the authors study benign overfitting in multiclass linear classification. They show the equivalence between one-vs-all SVM and multiclass SVM with either cross entropy or squared loss under a sufficient condition. Furthermore they show that when overparametrization occurs, the sufficient condition holds with high probability. ", "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": "The authors explore the literature of benign overfitting for multiclass classification. For this purpose they use SVMs.  They consider the space of linearly separable data. In particular they show that under a deterministic sufficient condition, one-vs-all  SVM, is equivalent to multiclass SVM classifier using both squared loss and cross entropy loss. This is the first case to show that these two loss functions can be equivalent. \n\nFurthermore, they show that for GMM or MLM, the aforementioned sufficient condition is satisfied with high probability under overparametrization based on the number of classes and quantities related to the data covariance. They also then provide experimental results to back up this claim. \n\nMoreover, they provide error bounds for data generated under these conditions. This shows that benign overfitting happens irrespective of the loss function chosen. \n\nAfter Rebuttal\n\nIncreased score after reading author response and other reviews. Please find the details in the comments.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I like this paper overall. Here are my main concerns\n* The authors assume linearly separable data in the their work. However, that is not true in most cases. I would like to know about their thoughts regarding what would happen in such a case.\n* Building on the previous question, I am wondering if it is possible to show some experimental results on non linearly separable data?\n* Most of the classifiers use DNNs this days. It has been shown that the generalization for DNNs are very different from that of other classifiers. I am wondering if it possible to extend the results from this paper to DNNs. I would like to know the authors thoughts on this.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "fhQK4SiHZxn", "reviewer": "Reviewer_BFAo", "summary": "The authors aim to establish the equivalence of multiple loss functions in training and to analyse the conditions for benign overfitting in the rigime of multiclass classification. The paper proposes a crucial condition under which the solutions of multiclass SVM, one-vs-all SVM and min-norm interpolating (MNI) classifier are equivalent. It is proven that this condition holds in high probability in both Gaussian mixture model and multinomial logistic model. Finally, the paper gives the genalization bound of the MNI classifier based on its equivalence with SVM, as well as the condition for benign overfitting.", "questions": "", "limitations": "", "rating": 5, "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": "## Originality\nAlthough the paper applies some techniques of former work, it is the first to propose a sufficient condition for the equivalence of multiclass SVM and the MNI classifier and the generalization of the MNI classifier.\n## Quality\nThe analysis in the main body of the paper is strong and convincing. However, the authors claim in the introduction part that **square loss is equivalent or even superior to cross-entropy loss**. The main body only proves the equivalence of the loss based on margin and the square loss. Cross-entropy loss, which is deserves more concern as a common choice in deep learning, is not sufficiently discussed.\n## Clarity\nThe paper is well organized from the equivalence of SVM and MNI to the generalization of MNI and benign overfitting. Readers may find it easy to follow the flow.\n## Significance\nThis paper studies benign overfitting for the task of multiclass classification, which is an important topic that has not been touched upon. The paper would be of much more significance if cross-entropy loss were carefully studied.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This part does not apply to this paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "6b_diGsAoz9", "reviewer": "Reviewer_Cuyv", "summary": "The paper studies the problem of multiclass classification in the overparameterized regimes. The work derives a sufficient condition under which multiple multiclass SVM classifiers converge to the min-norm interpolating (MNI) solution, extending a recent result ([MNS+ 20]) beyond the binary classification setting. The paper then shows that for certain configurations of the Gaussian mixture model and multinomial logistic model, this condition holds under high enough effective overparameterization. Finally, the paper derives non-asymptotic bounds on the error of the MNI classifier with multinomial logistic data and discusses sufficient conditions for the multiclass SVM to satisfy benign overfitting.\n", "questions": "", "limitations": "", "rating": 7, "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": "**Quality and Clarity**: \n\n- The paper is that it is very well-written and well organized. The ideas are presented clearly with intuitive explanations, and the proofs are rigorous. The authors are careful in evaluating the strengths/weaknesses of their work. The work seems to be built upon established literature and the review of related works is informative. \n\n- The technical parts of the paper are of very high quality\n\n\n**Originality**: \n\n- The central part of the paper is built upon existing results for binary classification. All main messages of the work are affirmative answers to the main ideas outlined by [MNS+ 20] and [HMX20], i.e., in overparameterized regimes, all losses lead to the min-norm interpolating solution, and all data points are (in a sense) support vectors. \n\n- On the other hand, it is worth noting that several parts of the extension to multiclass are non-trivial (with varying degrees) and some require significantly new technical treatments:\n   - The most important point of novelty of the paper is the derivation of Condition (8), which is a generalization of Equation (22) of [MNS+ 20]. For multiclass settings, the complementary slackness condition does not directly imply interpolation (as in the binary case) and the condition needs to be designed to ensure that a set of symmetric constraints also hold. Both the formulation and the technical proof of Theorem 1 are new and meaningful. \n   - The results of Theorem 2, 3, 4, 5, albeit are of high quality and are non-trivial, mostly follow the framework of [MNS+ 20] and [HMX20] with technical adjustments. \n\n\n**Significance**:\n\n- As stated previously, all main messages of the work are affirmative answers to the main ideas outlined by [MNS+ 20] and [HMX20], thus the result themselves do not make as strong of an impact on the way people think about overparameterized regimes.\n\n- The technical contributions of the paper are highly specialized to highly specific models of data (Gaussian mixture model with equal energy, Multinomial logistic model with orthogonal means). This lack of generality is likely to hinder the use of the work in more general settings. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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