Generalization for multiclass classification with overparameterized linear models
Authors: Vignesh Subramanian
Rahul Arya
Anant Sahai
Venue: NeurIPS 2022 Accept (2022)
Keywords: overparameterized
multiclass
classification
theory
generalization
interpolation
bi-level
Gaussian model

Abstract: Via an overparameterized linear model with Gaussian features, we provide conditions for good generalization for multiclass classification of minimum-norm interpolating solutions in an asymptotic setting where both the number of underlying features and the number of classes scale with the number of training points. The survival/contamination analysis framework for understanding the behavior of overparameterized learning problems is adapted to this setting, revealing that multiclass classification qualitatively behaves like binary classification in that, as long as there are not too many classes (made precise in the paper), it is possible to generalize well even in settings where regression tasks would not generalize. Besides various technical challenges, it turns out that the key difference from the binary classification setting is that there are relatively fewer training examples of each class in the multiclass setting as the number of classes increases, making the multiclass problem ``harder'' than the binary one.

Generalization for Multiclass Classification with Overparameterized Linear Models
Vignesh Subramanian
Department of Electrical Engineering and Computer Sciences
University California Berkeley
Berkeley, CA-94720, USA
wignesh.subramanainn subramanian@eecs. ber.eeeeey.bb..eyy..............
Rahul Arya
Department of Electrical Engineering and Computer Sciences
University California Berkeley Berkeley, CA-94720, USA
rahularya@berkelly.cco
Anant Sahai
Department of Electrical Enginecring and Computer Sciences University of California Berkeley Berkeley, CA CA-94720, USA
sahai@eecs werkeley. edu
Abstract
Via an overparameterized linear model with Gaussian features, we provide con- ditions for good generalization for multiclass classification of minimum-norm interpolating solutions in an asymptotic setting where both the number of under- lying features and the number of classes scale with the number of training points. The survival/contamination analysis framework for understanding the behavior of overparameterized learning problems adapted to this setting, revealing that multiclass classification qualitatively behaves like binary classification in that, as long as there are not too many classes (made precise in the paper), it is possible to generalize well even in some settings where the corresponding regression tasks would not generalize. Besides various technical challenges, turns out that the key difference from the binary classification setting is that there are relatively fewer positive training examples of each class in the multiclass setting as the number of classes increases, making the multiclass problem "harder" than the binary one.
Introduction
Multiclass classification on standardized datasets where the current deep- revolution really made the community take notice with previously unattainable levels of performance. Contemporary systems have demonstrated tremendous success at these tasks, typically using gigantic models with parameters that vastly exceed the (also large) number of data points used to train these models. In defiance of traditional statistical wisdom regarding overfitting, these big models can be trained to achieve training error even with noisy labels, but still generalize well practice 84 28
To better understand this empirical phenomenon, one line work uses appropriate high- nigh-dimensional linear models for regression problems to show how benign fitting of noise in training data is possible Essentially, the model must have enough "non-preferred" degrees of freedom to he able to absorb the training noise without contaminating predictions by much. Simultaneously; there has to be enough preference for degrees of freedom that can capture the true pattern to enable survive the learning procedure and be well represented in the final learned model.
31 52
D (55
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

A subsequent line of work studies binary classification [56 1E 76 and shows that binary classification can generalize well beyond what can be proved by classical margin- based bounds [3] and there exist regimes where binary classification can even succeed in generalizing where regression fails - less preference is required for the degrees of freedom that capture the true pattern [56]. Very recently, the generalization of multiclass classification in similar models was studied in Wang et al.
777 but the analysis was limited to a fixed finite number of classes. In practice, we see that larger datasets often come with more classes and are tackled with even bigger models and so it is important to see what happens to generalization when everything scales together. To have a crisply understandable approach that allows everything scale, this paper also adopts the bi-level covariance model with Gaussian features that is used in Muthukumar et al. [55 56
Wang et al. 77 Wang et al.
To understand classification, we must understand the role of training loss functions in determining what is learned. Empirical evidence shows that least-squares can yield classification performance
competitive to cross-entropy minimization 64 35
Muthukumar al. (56]. Hsu al. [K]
show that indeed with sufficient overparameterizatioo, the support vector machine (SVM) solution, which also arises from minimizing the logistic loss using gradient descent 68 36 is identical to
that obtained by the minimum-none interpolation (MNI) of binary labels what would be obtained
by gradient descent while minimizing the squared loss. A similar equivalence holds for different
variations of multiclass SVMs and the MNI of one- one-hot-encodee labels (77) Consequently, this paper focuses on the MNI approach to overparameterized learning for multiclass classification.
2 Our contributions
Our study provides asymptotic analysis of the error of the minimum-norm interpolating clas- sifier for the multiclass classification problem with weighted Gaussian features. We consider an overparameterized setting using a bi-level feature weighting model where the number of features, classes, favored features, and the feature weights themselves all scale with the number of training points. Under this model, Theorem 5. provides sufficient conditions for good generalization in the form of a region in which as the number of training points increase, the number of classes grows slowly enough, the total number of features (i.e. level of overparameterization) grows fast enough, the number of favored features grows slowly enough, and the amount of favoring of those favored features sufficient to allow for asymptotic generalization. We assume that our labels are generated noiselessly based on which of the first k features is the largest
To prove our main result, Theorem 5.I we present a novel typicality-style argument featuring the feature margin (gap between the largest and second-largest feature) for computing sufficient conditions for correct classification utilizing the signal- signal-processing inspired concepts of survival and contamination from Muthukumar et al. 155 [56] and leveraging the madoom-marii, analysis tools sharpened in Bartlett et al. The survival concept relates to the shrinkage induced by the regularizing effect of having lots of features in the context of min-norm interpolation survival captures what is left of the true pattern after shrinkage. Contamination reflects the consequence of overparameteriizaion when training via optimization: in addition to the true pattern, there is an infinite family of other false patterns (aliases) that also happen to explain the limited training data, and the optimizer ends up hedging its bet across the true pattern and these other competing false explanations. The learned false patterns contaminate the predictions on test points, and this can be quantified by the relevant standard deviation.
The key is analyzing what happens with multiclass training data where there are relatively fewer positive examples of each class, and where the training data for a particular class is not independent of the features corresponding to other classes. The analysis shows that as a result of having fewer positive exemplars for a class relative to the total size of the training data, the survival drops by a factor of (the number of classes), while the contamination only drops by a factor of Vk. As in binary classification, the ratio of the relevant survival to contamination terms plays the role of the effective signal-to to-noise ratio and shows up as a key quantity in our error analysis (Equation 22 from
For an interesting alternative perspective on this equivalence as an indication of a potential bug instead of as a promising feature, see Shamir [7]
"This assumption is without loss of generality for the bi-level model as long the classes defined by orthogonal directions as in Wang et al. 777.
'This is related to what is called the challenge of "uunderspecification"" in ML 19 and this in turn is also one
aspect of the challenge of covariate shifts 73
2

---

Section 5.1). When this ratio grows asymptotically to oc, multiclass classification generalizes well. To the best of our knowledge, this is the first work that quantifies this effect of fewer informative samples per class and in what sense that makes multiclass classification harder than binary classification. The closest related work ((77) only considers multiclass classification in the fixed finite class setting and consequently, doesn't 't compute exact dependencies on the number of classes k. We provide a more
detailed comparison of our work with Wang et al. 777 and Muthukumar et al. [56] in Appendix Hf the Supplemental material.
3 Related Work
The present work is situated within larger stream of theoretical research trying to understand why overparameterized learning works and its limits. The limited page budget here forces brevity, but we recommend the recent surveys Bartlett et al. [51. Belkin
[6] Dar et al. 200 for further context.
Classically, by either operating in the underparameterizee regime or by performing explicit regular- ization, we can force the training procedure to average out the harmful effects of training noise and thereby hope to obtain good generalization. The present cycle of seeking deeper understanding began after it was observed that modern deep networks were overparameterized, capable of memoriz- ing noise, and yet still generalized well, even when they were trained without explicit regularization 59 [4] Experiments in Geiger et al. [28] Belkin et al. [ observed double-descent behavior of the generalization error where in addition to the traditional U-shaped curve in the underparameterized regime, the error decreases in the overparameterized regime we increase the number of model pa- rameters. This double descent phenomenon is not unique to deep learning models and was replicated for kernel learning 77. Further, the good generalization performance in the overparameterized regime cannot be explained by traditional worst-case generalization bounds based on Rademacher complexity or VC-dimension since the models have the capacity to fit purely random labels. Overparameterized models must therefore have some fortuitous combination of the model architecture with the training algorithm that leads us to particular solution that generalizes well.
To understand the phenomenon better, several works study the simpler setting of overparameterized linear regression. The minimum- norm interpolator is of particular interest since gradient descent on the squared loss has an implici f bias towards this solution in the overparameterized regime and has been studied extensively. (An incomplete list is Hastie et al. B1. Mei and Montanari
24
52
Bartlett et al. 4 Belkin et al. [9], Muthukumar et al. (55), Bibas et al. [T,, Kobak et al.
.) To generalize well, the underlying feature family must satisfy a balance between having a few important directions that sufficiently favor the true pattern, and large number of unimportant directions that can absorb the noise in harmless manner.
41 Wu and Xu I Richards et al. [
3.1 High dimensional binary classification
Both concurrently with and subsequent to the wave of analyses on overparameterized regression, researchers turned their attention to binary classification. A line of work poses the overparameterized binary classification problem as an optimization problem and analyzes it directly to obtain precise asymptotic behaviours of the generalization error 66 37
The key technical tool employed in these works is the Convex Gaussian Min-max Theorem and the resultant error formulas involve solutions to system of non-linear equations that typically do not admit closed-form expressions. The generalization error of the max-margin SVM has also been analyzed directly by studying the iterates of gradient descent in K and leveraging the implicit regularization perspective of optimization algorithms.
69
5
38
However, although the above works did significantly enhance our understanding of binary classifica- tion in the overparameterized regime, a fundamental question was not answered: "Is classification easier than regression?" While the classification task easier than the regression task at test time (regression requires us to correctly predict a real value while binary classification requires us to only predict its sign correctly), the training data for classification is less informative than that for regression
"The minimum-é, norm interpolator has also been studied in Muthukumar et al. (5 Mitra 53 Li and Wei (SN, Wang et al. (nh) and while sparsity-secking hehavior helps preserve the true signal (if the true pattern indeed depends only on few features), it poses a challenge for the harmless absorption of noise since the
desired averaging behaviour is not achieved fully [55].
"In fact, there is an important complementary literature that brings out the implicit regularization performed by training methods, especially variants of gradient descent and stochastic gradient descent, and how the
underlying architecture of the model shapes this implicit regularization 30
68
36
SC
57
2 32
3

---

since the labels are also binary. As described earlier, this question was answered in Muthukumar al. [56], by exhibiting an asymptotic regime where binary classification error goes zero, but the regression error does not. This was shown using Gaussian features with a bi-level covariance model. turns out that the level of anisotropy (favoring of true features) required to perform regression correctly is significantly higher than that required for binary classification.
The key to the result in Muthukumar al. [56] was the signal-processing inspired survival/contami nation framework introduced in Muthukumar et al. [55] as a reconceptualization of the "effective ranks" perspective of Bartlett et al. [. For binary classification succeed, what matters is that the survival exceed the contamination so that the sign of the prediction remains correct. Meanwhile, regression harder since for regression succeed, the survival must also tend to 1.
3.2 Multiclass classification and the role of training loss function
There is large classical body of work multiclass classification algorithms 79 12
18
46).
with further works giving computationally efficient algorithms for extreme multiclass problems with huge number of classes [15]
Numerous theoretical works investigate the consistency
of classifiers [85 60 61 771, 14. Finite-sample analysis of the generalization error in multiclass
classification problems in the underparameterizeed regime has been studied in Koltchinskii and
Panchenko 42). Guermeur [29]. Allwein et al. M. Li et al. [49], Cortes et al. [6], Lei et al.
47. Maurer [51. Lei et al. 48 Kuznetsov et al. 44 451 and includes both data dependent
bounds using Rademacher complexity, Gaussian complexity and covering numbers as well as data- independent bounds using the VC dimension. Recent work (72) leverages the Convex Gaussian Min-max Theorem to precisely characterize the asymptotic behaviour of the least-squares classifier in underparameterized multiclass classification.
So, how different is multiclass classification from binary classification? The test time task is more difficult and for the same total number of training points, we have fewer positive training examples from each class. Several empirical studies comparing the performances of multiclass
classification via learning multiple binary classifiers have been undertaken 64 25 1. The effects
of the loss function while using deep nets to perform classification has also been investigated
32
33 3y
Empirical evidence of squares minimization yielding competitive
test classification performance to cross-entropy minimization has been presented in Rifkin and Klautau
641
Hui and Belkin 35 Bosman al.
More recently, Wang et al. 7 makes progress towards bridging the gap between empirical ob- servations and theoretical understanding by proving that in certain overparameterizee regimes the solution to a multiclass SVM problem is identical to the one obtained by minimum-norm interpolation of one-hot encoded labels (equivalently, that gradient descent on squared loss leads the same solution as gradient descent on cross-entropy loss as a result of implicit bias of these algorithms In addition, Wang al. 77 extends the analysis presented in Muthukumar et al. [56] for the binary classification problem to the multiclass problem with finitely many classes via an interesting reduction to analyzing a finite set of pairwise competitions, all of which must be won for multiclass classification to succeed. (We give further comments on the relationship of the present in Appendix H of the Supplemental material.)
24
36 68
paper with Wang et al. [in
Problem setup
We consider the multiclass classification problem with & classes. The training data consists of pairs {x; & i= where 2; E Rd are i.i.d Gaussian vectors drawn from distribution,
X; ~
N=, Ia).
(1)
We make the following assumption on how the labels 4 E [k] are generated. Assumption 4.1. Orthogonal classes noiseless mode | The class labels &, are generated based on which of the first k dimensions of point x; has the largest value,
E = argmaxx([m], mE(k)
(2)
'A more generic model is 6, = argmax mEt M,,,, x; where the p., are unit norm orthogonal vectors. we further assume the bi-level DedeinDennn (.2) and that the vectors μm have no support outside of the favored features then it suffices to consider the simplifid setting where Mm, are 1-sparse unit vectors like we do here. due the indifference of minimum norm interpolation to orthogonal transformations.

---

We use the notation [m] to refer to the m element of vector x, For clarity of exposition, we make explicit feature weighting that transforms the training points as follows:
xx
e [d].
(3)
Here À IRd contains the squared feature weights. The feature weighting serves the role of favoring the true pattern, something that essential for good generalization
The weighted feature matrix X R is given by,
[
Aazz
Valaa]
(4)
where 2j E IR contains the j features from the n training points. Note that 2j ~ NN( In) are i.d
Gaussians. We use a one-hot encoding for representing the labels as the matrix Yoh. E R
Y
yyhh
yoh
Yk
(5)
where,
1,
if = m
uoh [i]
(6)
(0
otherwise
zero-mean variant of the encoding where we subtract the mean from each entry denoted:
1
yo Ym
1. k
Our classifier consists of & coefficient vectors f. for mn E [k] that are learned by minimum-nomm norm interpolation of the zero-mean one-hot variants using the weighted features
f... = arg min ||f||2
(8)
s.t. X = ot -1 1.
(9)
k
We can express these coefficients in closed form as,
f... = (X (X (X"))
ym-
(10)
On a test point Xtest ~ (O0 Ia) we predict a label as follows: First, we transform the test point into the weighted feature space to obtain x where ="<=eli] = Aysreell for E [d]. Then we compute & scalar "scores" and assign the class based on the largest score as follows:
= argmax f x
(11)
1gmgk
The true label of the test point is frest argmax Smgk [t]. A misclassification event Egrr occurs iff
argmax Itest [m] * argmax x x
(12)
Smmsk
15mSk
In our work determine sufficient conditions under which the probability of misclassification (computed over the randomness in both the training data and test point) goes to zero in an asymptotic regime where the number training points, number of features, number of classes and feature weights scale according to the bi-level ensemble model.
"Ou weighted feature model is equivalent the used in other works (e.g. (56 that assume that the covariates come from an anisotropic Gaussian with a covariance matrix that favors the truly important directions. 'The classifier learned via this method is equivalent to those obtained by other natural training methods under sufficient overparameterizaaton (77).
5

---

Definition 4.2. (Bi-level ensemble): The bi-level ensemble is parameterized by p. p.9.r and t where p 1, r 1, 9 (p-r) and < <tt Here. parameter p controls the extent of overparumeterization r determines the number of favored features, controls the weights favored features and controls the number of classes. The number of features (d), number favored features (8), number of classes (k) and feature weights ( (v)) all scale with the number of training points (n) as follows:
d d=
[n"
cx Ln'
(13)
where is positive integer: The feature weights are given by,
ad
15i58
(14)
1-aad
otherwise
We provide visualization of the bi-level model in Figure
od
Feature weight, y
(1- d-
72"
= n2
Feature index, j
Bi-level feature weighting model. The first features have a higher weight and are favored during minimum norm interpolation. These can be thought of the square-roots of the eigenvalues of the feature covariance matrix in Gaussian model for the covariates as in Bartlett et al. 4.
Figure I:
Main result
Theorem 5.1. (Asymptotic classification region in the bi-level model): Under the bi-level ensemble
model 4.2 when the true data generating process is 1-sparse (Assumption 4.1) the probability of misclassifccation P(E - as + oc the following conditions hold:
< min (r, r. 2(( 2,24 -
(15)
g+r>l.
(16)
Note that from Muthukumar et al. [56], the condition q + corresponds to the regime where the corresponding regression does not generalize well and thus our result shows that multiclass classification generalize in regimes where the corresponding regression problem does not. In this challenging regime, the empirical eigenstructure does not reveal the true nature of underlying features illustrated in Appendix !
Figure 2 visualizes the regimes by considering slices of the four dimensional scaling parameter space of p. g. and l. (1a) and (2a) fix the value of y to 0.75 and 0.95 respectively and contrast the multiclass problem with a fixed finite number of classes (t = 0) to the binary classification and regression problems. From these plots we observe that if we fix p, q, and increase i.c. increasing how many features are favored (and thereby favoring each of them less), we transition from the regime where both regression and binary classification work, into the regime where binary classification works but regression does not, then the regime where this paper can prove multiclass classification works and finally to the regime where neither regression nor binary classification works.
In Figure 2 subplots (Ib).(cc)((2)) and (2c) each visualize a slice along the r and (class scaling) dimensions with fixed p and The axis itself in these plots corresponds to fixed finite classes setting. From (1b) we observe that the right-hand boundary of the region where multiclass classifica- tion generalizes well contains two slopes. These slopes arise from the two conditions t < 1 r and

---

(1a) q=0.75, t= 0
(1b) q=0.75, 2.3
(1c) q=0.75, p 3.7
0.5
0.5
0.4
0.4
4
0.3
0.3
0.2
0.2
0.1
0.1
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
(1d) Conjectured q=0.75, ==
0.5
(le) Conjectured q=0.75, p= 2.3 (1f) Conjectured q=0.75, p 3.7.7
0.5
0.4
0.4
4
0.3
0.3
0.2
0.2
2-
0.1
0.1
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.2
0.6
0.8
(2a) 0=9.95, t= 0
(2b) q=0.95,
2.3
(2c) q=0.95, p 3.7
0.4
0.4
4
0.3
0.3
0.2
0.2
0.1
0.1
0.0
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
100
(2d) Conjectured q=0.95, t=
0.5
(2e) Conjectured q=9.55, p= 2.3
0.5
Conjectured q=9.95,
p= 3.7
0.4
0.4
4
0.3
0.3
0.2
0.2
2
0.1
0.1
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
r
Ereg + 0, Epinary + 0
Emulti + 0 (conjectured)
Ereg Ebinary 0
Ereg 0, Ebinary 0, Emutii 0 (conjectured)
Ereg 1, Epinary
0, Emulti
Ereg 1, Ebinary O, Emuti 0 (conjectured)
Ereg 1, Ebinary
Emulti + 1 (conjectured)
Emulti +
Figure 2: Visualization of the bi-level regimes four dimensions p, q, (la) and (2a) contrast multiclass classification with finite classes to binary classification and regression. The horizontal lines p 2.3 and p 3.7 correspond to the slices visualized (Ib), (Ic), (2b) and (2c). The conjectured regimes are visualized in (1d), (1e), (1f), (2d), (2e) and (2f).
<<p+1- 2(g + in Theorem and are result of either contamination from favored (but not true) features dominating contamination from the unfavored features dominating. In (1c)

---

in the regime where binary classification works for all values of r < 1. However, we increase t, eventually multiclass classification stops working
When we go from the binary problem to multiclass problem with & classes, the survival drops by a factor of & as consequence of having only fraction of positive training examples per class. This is because the one-hot labels we interpolate while training have fewer large values close to that are able to positively correlate with the true feature vector. Having fewer positive exemplars also reduces the total energy in the training vector by factor of k. and because of the square-root relationship of the standard deviation to the energy, the contamination only shrinks by factor of
Vk. The overall survival/contaminatio ratio decreases by factor of V making the multiclass classification task more difficult [0] An interesting observation here the amount of favoring required for good generalization is linked the number of positive training examples we consider a setting where the binary classification problem generalizes well, and we switch to the & class multiclass problem, then by increasing the number of training samples &: fold (and thus matching the number of positive training examples per class in the multiclass case to the binary case) and keeping the number of features and feature weights constant multiclass classification. (Appendix [ of the Supplemental material elaborates on this phenomenon, well why it is somewhat surprising.)
class. Indeed, if
generalize well for
Next, we present a brief overview of our proof that utilizes the survival/contamination analysis framework from Muthukumar et al. (56) along with a typicality-inspieed argument where the feature margin (difference between largest and second largest feature) on the test point plays a key role. The complete proof is provided in Appendices B and of the Supplemental material.
5.1 Proof sketch
Assume without loss of generality that for the test point Xtest NN, Ia), the true class for some E [k]. Let x be the weighted version of this test point. A necessary and sufficient condition for classification error is that for some / # a, 3 [k].
fa [aa)xtssh [a] + fa 13 + Σ
Falilatesii fo Talaawa [a]
j
fg10] xest [8] +
Σ
iE(o,0)
(17)
By converting into the unweighted feature space obtain
[ajaaala] - 2 [8]<
Σ
(18)
j#(0,9)
where
ha xx folil).
(19)
Performing some algebraic manipulations and because Aa Xg À since both a and B are favored features, we can rewrite this
Nha.sla) [a] CNa.g
Na. Tig.a [3]
(Irestlaa - Drest (3)) + Ireat [3]
Tra [aa]
Σ
Xyhssalllateeelll (20)
CNa.8 jK(a,))
"To be precise, what the region actually illustrates is that our proof approach stops being able to show that multiclass classification works. In the Conclusion section. we conjecture where we believe that multiclass classification actually stops working. The conjectured regions
illustrated (1f..()))(22) and (2f).
1This is also responsible for contamination due to favored features being able to cause emror.. For binary classification, because the true feature survival is constant (depending only the level of label noise), the survival always asymptotically overcome any contamination from other favored features (6).

---

where
(
Σ 23Che.al1)) jEfa,99
C =
(21)
We divide by 8 to normalize the RHS above to have standard normal distribution. Next, by removing the dependency on 3, we obtain a sufficient condition for correct classification:
ming stal maxy .
8 [a]
h [3]
min [Zteat(a]
Itest [3])
max [3]]
max B
ha
[a]
SUICN ratio
closest feature margin
largest competing feature
survival variation
1
Σ
max B CNa.
($(0,8)
normalized contamination
(22)
Here the min and max over all competing features: 1 1 K, and the sum is all feature indices except a and B, but we simplify the notation for convenience. We show via intermediate lemmas introduced in Appendix[Boo the Supplemental material that under the conditions specified in Theorem 5.1 with sufficiently high probability [1] the relevant survival to contamination SU/CN ratio grows polynomial rate n² for some > O, the closest feature margin shrinks at cos-thann-polyoone
rate 1/ //vIn nk, the survival variation decays at polynomial rate n for some >> 0. Further, the magnitudes of the largest competing feature and the normalized contamination are no more than In(kk)..
This implies that the left-hand side of Equation logarithmic terms) and dominates the right-hand side which grows at the much slower rate vIn nı. survival/contamination ratio also plays key role in the analysis of the binary classification problem in Muthukumar et al. [56] but in the multiclass setting, we additionally have the survival variation term and feature margin playing important roles since we are comparing different scores while predicting the class label. For correct classification, the survivalicontaminttion ratio must be sufficiently large, the survival variation must be small enough and the feature margin must be sufficiently large.
22 grows at a polynomial rate n² (ignoring
Conclusion
In this work we compute sufficient conditions for good generalization of multiclass classification in bi-level overparameterized linear model with Gaussian features. We observed that multiclass classification can generalize even when the regression problem does not generalize (for q + >> 1). Further, the multiclass problem is "harder" than the binary problem because we have fewer positive training examples per class. The nature of the training data complicates our analysis in the multiclass setting since the true class labels are generated by comparing & features and thus no longer have independence of the encoded class label with any of these features. This becomes relevant when we compute bounds the survival and contamination quantities since the Hanson- Hanson-Wright inequality [65] no longer applicable directly on the quantities of interest as was the case for the binary classification problem in prior work [56]. As consequence of working around this non-independence that our sufficient conditions for good generalization in the regime + r > 1 are loose.
believe
Even though in our work we focus the regime where regression does not work, q r > 1, we can extend the analysis to the regime where q + < by grinding through the expressions for survival and contamination in this regime. Even in this regime, for multiclass training data, survival is of the order & while contamination scales similarly to the regime + > Thus, while is true that for
This where we leverage the idea of sppicalitysstlle proofs information theory loose union bounds that end up being dominated by the atypical behavior of quantities. In our case, by pulling the feature margin out explicitly, we can just deal with its typical behavior. Similarly, the typical behavior of the largest competing feature and the true feature is all that matters.
avoid unnecessarily

---

binary classification or a fixed number of classes, the regime where regression works is regime where classification also works, this need be true if there are too many classes.
We conjecture that the following is a set of necessary and sufficient conditions for asymptotically good generalization (We elaborate on this in Appendix F in the Supplemental material):
Conjecture 6.1. (Conjectured bi-level regions): Under the bi-level ensemble model 4.2 when the true data generating process is 1-sparse (Assumption 4.7V as + oc, the probability of misclassification event P(Eer)) behaves as follows:
00 if < min (r; 1 r, + 1- 2- m + r))
P(Eer))
(23)
11
if min (r. r. + 1 - max(1, +
The conjectured regions are visualized in (1)) and (2f) in Figure Subfigures (Id) and (2d) illustrate that we believe multiclass classification with finitely many classes works if binary classification works. Further, comparing (Ie) to (2e) when we increase q, the conjectured parameter region where multiclass classification works shrinks since we decrease the amount of favoring of true features. Interestingly, the nature of the looseness in our approach is such that proof technique is able to recover a larger fraction of the conjectured region for larger which intuitively a result of less favoring leading to stronger concentration of certain random quantities. Tightening the potential looseness in our analysis and proving the converse result by computing sufficient conditions for poor generalization of multiclass classification are interesting avenues of future work.
Further, although the present analysis focuses on solutions that exactly interpolate the training data, we can extend our results to account for additional ridge regularization by viewing ridge regularization as minimum-norm interpolation using augmented contamination-fres features as the Appendix of Muthukumar et al. 55 and computing bounds leveraging tools from Tsigler and Bartlett [74). Our assumption of the strict bi-level weighting model is largely to simplify the calculations and by substituting terms appropriately in lemmas from Appendix B in the Supplemental material, should be possible to compute results for other weighting models. Finally, exploring the new phenomena that can be encountered direction for future work.
go beyond the 1-sparse noiseless model is exciting
Acknowledgments and Disclosure of Funding
We are grateful to our earlier collaborators Vidya Muthukumar, Misha Belkin, Daniel Hsu, and Adhyyan Narang. In addition, we want to thank the students and course staff for the Fall 2020 iteration of Berkeley's s CS189/289A machine learning courses, where we had adapted ideas from Muthukumar et al.
55 56 in teaching the foundations of modern machine learning the need for the present paper became more clear during this process.
We gratefully acknowledge the support from ML4Wireless center member companies and NSF grants AST-2132700 and AST-2037852 for making this research possible.
References
[1] Erin Allwein, Robert E. Schapire, and Yoram Singer. Reducing multiclass to binary: unifying approach for margin classifiers. Journal of Machine Learning Research,
2000.
[2] Navid Azizan, Sahin Lale, and Babak Hassibi. A study of generalization of stochastic mirror descent algorithms on overparameterized nonlinear models. ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3132- 3136. IEEE, 2020.
[3] Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-493 482, 2002.
[4] 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):30063-3007) 2020.
[5] Peter Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: a statistical viewpoint. Acta numerica, 30:87-201, 2021.
10

---

[6] Mikhail Belkin. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation. Acta Numerica, 30:203-248, 2021.
[7] Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning need to understand kernel learning. ICML, 2018.
[8] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical variance tradc-off. Proceedings of the National Academy of Sciences, 11663):15849-1555
2019.
[9] Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics Data Science, 2(4): 117--180, 2020.
[10] Koby Bibas, Yaniv Fogel, and Meir Feder. A new look at an old problem: universal learning approach to linear regression. CoRR, abs/ 19050,4708, 2019. URL http://:://axii orgo /bs/ 1905. 04708
[11] Anna Bosman, Andries Engelbrecht, and Mardé Helbig. Visualising basins of attraction for the cross-entropy and the squared error neural network loss functions. Neurocomputing, 400, 03 2020. doi: 10. 10.1016/j.neucom www.w/www............1 2020.02.113.
[12] Erin J. Bredensteiner and Kristin P. Bennett. Multicategory classification by support vec- tor machines. Computational Optimization and Applications, 12, 1999. doi: 10.1023/A:
100866362962..
[13] Niladri S Chatterji and Philip M Long. Finite-sample analysis of interpolating linear elassifiers in the overparameterized regime. Journal of Machine Learning Research, (2(129)11330 2021.
[14] Di-Rong Chen and Tao Sun. Consistency of multiclass empirical risk minimization methods based on convex loss. Journal of Machine Learning Research, 7:2435-2447, dee 2006. ISSN 1532-4435.
[15] Anna Choromanska, Alekh Agarwal, and John Langford. Extreme multi class classification. In NIPS Workshop: eXtreme Classification, submitted, volume 1, pages 2013.
[16] Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, and Scott Yang. Structured prediction 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, Cur- ran Associates, Inc., 2016. UtL http:ttttptp/oceeiiiiiieeee http:://pooceeeeeeeeeeeee wewpeeeddinnnnuuuuiiiie neurips... www.eeis..c.ppapee//2...... httpsccaaaaeee21//ieeeee 53la7661012026222226668888-888
.pdf
[17] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory 2nd Edition (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, July 2006. ISBN 0471241954.
[18) Koby Crammer, Yoram Singer, Nello Cristianini, John Shawe-taylor, and Bob Williamson. On the algorithmic implementation of multiclass kernel-based vector machines. Journal of Machine Learning Research, 2:265-292, 2001.
[19] Alexander D' Amour, Katherine Heller, Dan Moldovan, Ben Adlam, Babak Alipanahi, Alex Beutel, Christina Chen, Jonathan Deaton, Jacob Eisenstein, Matthew Hoffman, et al. Under- specification presents challenges for credibility in modern machine learning. arXiv preprint arXiv:2011.03330 2020.
[20] Yehuda Dar, Vidya Muthukumar, and Richard G Baraniuk. A farewell to the bias-variance tradeoff? an overview of the theory of overparameterized machine learning. arXiv preprint arXiv:2109.02355, 2021.
[21] Ahmet Demirkaya, Jiasi Chen, and Samet Oymak. Exploring the role of loss functions in mul- ticlass classification. In 2020 54th Annual Conference on Information Sciences and Systems (CISS), pages 1-5, 2020. doi: 10. 10.1100/CIS44331.000.00000220111

---

[22] Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for nigh-dimensional binary linear classification. Information and Inference: A Journal of the IMA. (14 2021. ISSN 2049-8772. doi: 10. 10.1093/iaiia//aaab022 URI. https: org/10. 1093/
imaiai/iaab002 iaab002.
[23] Thomas G Dietterich and Ghulum Bakiri. Solving multiclass learning problems via enror- correcting output codes. Journal of Artificial Intelligence Research, 2(1):263-286) 1994. ISSN 1076-9757.
[24] Heinz Werner Engl, Martin Hanke, and Andreas Neubauer. Regularization of inverse problems. volume 375. Springer Science Business Media, 1996.
[25] Johannes Fürnkranz. Round robin classification. Journal of Machine Learning Research, 2: 721-747,
[26] Krzysztof Gajowniezek, Leszek Chmielewski, Arkadiusz Orlowski, and Tomasz Ząbkowski. Generalized entropy cost function in neural networks. In International Conference on Artificial Neural Networks, pages 128-136, 10 2017. ISBN 978-3-319-68611--. doi:
[27] Robert G Gallager. Information theory and reliable communication, volume 588. Springer, 1968.
[28) Mario Geiger, Stefano Spigler, Stéphane d' A'sooi,, Levent Sagun, Marco Baity-Jesi, Giulio Biroli, and Matthieu Wyart, Jamming transition as a paradigm understand the loss landscape of deep neural networks. Physical Review E, 100(1):012115, 2019.
[29] Yann Guermeur. Combining Discriminant Models with New Multi-Class SVMs. Pattern Anal. Appl., 5:168-179, 06 2002. doi: (0.1007/s10044420001
[30] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias terms optimization geometry. In International Conference on Machine Learning, pages 1832-1841, 2018.
[31] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv: 1903.0990... 2019.
[32] Le Hou, Chen-Ping Yu, and Dimitris Samaras. Squared Earth Mover's Distance-based Loss for Training Deep Neural Networks. arXiv e-prints, art. arXiv:161 .05916, November 2016.
[33] Daniel Hsu, Vidya Muthukumar, and Ji Xu. On the proliferation of support vectors in high dimensions. In International Conference on Artificial Intelligence and Statistics, pages 91-99. PMLR, 2021.
[34] losif Pinelis https://maaaoovrrrooreeee/ssssss and anti-concentration of gap between largest and second largest value in gaus- sian iid sample. MathOverflow. URL https://nathoverfioo. http://wwwrrrio..eee/////333388 URLLatpps//aattoerroooweee/////.
pinelis). Concentration
(version: 2020-12-25).
[35] Like Hui and Mikhail Belkin. Evaluation of Neural Architectures Trained with Square Loss vs Cross-Entropy in Classification Tasks. arXiv e-prints, art. arXiv:2006.07322, June 2020.
[36] Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference on Learning Theory, pages 1772-1798, 2019.
[37] Abla Kammoun and Mohamed-Slim AlouiniFellow. On the precise error analysis of support vector machines. IEEE Open Journal of Signal Processing, 2:99-118. 2021.
[38] Ganesh Ramachandra Kini and Christos Thrampoulidis. Analytic study of double descent in bi- nary classification: The impact loss. 2020 IEEE International Symposium on Information Theory (ISIT), pages 2527-2532. IEEE, 2020.
12

---

[39] Ganesh Ramachandra Kini, Orestis Paraskevas. Samet Oymak, and Christos Thrampoulidis. Sabbllimballanced and group-sensitive classification under overparamettrrizttonn In M. Ran- zato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 18970-18983, Curran As-
sociates, Inc., 2021. URL. httpps:/pproceeddnggg neurips cc httprr/pps.cc.ppppr//////eeeeeee patpr//02//ettell 9df of htt.cc/ffoaooeeeeeeeeeeaaaaaaaa2
pdf
[40] Doug M. Kline and Victor L. Berardi. Revisiting squared-errol and cross-entropy functions for training neural network classifiers. Neural Computing & Applications, 14:310-318, 2005.
[41] 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:169-1 2020.
[42] Vladimir Koltchinskii and Dmitry Panchenko. Empirical margin distributions and bounding the generalization error of combined classifiers. The Annals of Statistics, 30(1):1-50, 2002. ISSN 009053644 URL htRphtt::/// //ttt:::/wwww.. jstor wttp//table/27/0000000
[43] Himanshu Kumar and P. Shanti Sastry. Robust loss functions for learning multi-class classifiers. 2018 IEEE International Conference on Systems, Man, and Cyberneties (SMC), pages 687- 692, 2018.
[44] Vitaly Kuznetsov, Mehryar Mohri, and Umar Syed. Multi-class deep boosting, In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, ed- itors, Advances in Neural Information Processing Systems, volume 27. Curran As- sociates, Inc., 2014. URL http://///eeeennnnnniii..spppss sagroceedingennuurppss www.nneeuueepppppeeeee wwtpppppee///4//iaa.... pdf
[45] Vitaly Kuznetsov, Mehryar Mohri, and Umar Syed. Rademacher complexity margin bounds for learning with large number of classes. In ICML Workshop on Extreme Classification: Learning with a Very Large Number Labels, 2015.
[46] Yoonkyung Lee, Yi Lin, and Grace Wahba. Multicategory support vector machines: Theory and application to the classification of microarray data and satellite radiance data. Journal of the American Statistical Association, 99(465) 81, 2004. doi: 10.
URL
[47] Yunwen Lei, Urun Dogan, Alexander Binder, and Marius Kloft. Multi-class SVMs: From Tighter Data- Dett--eeenndet Generalization Bounds 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. URL /tpp neurips pdf
cc/paper/2015//ine http:///hh.hhaaa0aooooaoaaa//aaa
[48] Yunwen Lei, Ürtin Dogan, Diag Zhou, and Marius Kloft. Data-dependent generalization bounds for multi-class classification. IEEE Transactions on Information Theory, 65(5):2995- 3021, 2019. doi: 10. 10.1109/T..201192289991
[49] Jian Li, Yong Liu, Rong Yin, Hua Zhang, Lizhong Ding, and Weiping Wang. Multi-class learning: From theory algorithm. In S. Bengio, H. Wallach, H. Larochelle, K. Grau- man, N. Gesa-Bianchi and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL -wwpeebbbba---p--.e.aae pdf
neurips
[50] Yue Li and Yuting Wei. Minimum 4ormm interpolators: Precise asymptotics and multiple descent. arXiv preprint http:///00.1111111202222222221.0
2021.
[51] Andreas Maurer. A vector-contraction inequality for Rademacher complexities. In Hans Ulrich Simon Ronald Ortner and Sandra Zilles, editors, Algorithmic Learning Theory, pages 3-17. Springer International Publishing, 2016.
[52] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprint arXiv:
1it::19900 1908 000800535, 2019.
13

---

[53] Partha P Mitra. Understanding overfitting peaks in generalization error: Analytical risk curves for lg and 6 penalized interpolation. arXiv preprint arXiv:1906.0366) 2019.
[54] 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: 1911191110000 191.5444 2019.
[55] Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpolation of noisy data in regression. IEEE Journal on Selected Areas Information
Theory, 1(1):67-33, 2020.
[56] Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel J. Hsu, and Anant Sahai. Classification vs regression in overparameterized regimes: Does the loss function matter? Journal of Machine Learning Research, 22:222:1 2021.
[57] Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pages
2019.
[58] Preetum Nakkiran. More Data Can Hurt for Linear Regression: Sample wise Double Descent. arXiv e-prints, art. 1r2:v:191..07242, December 2019.
[59] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv:1412.6614 2014.
[60] Bernardo Ávila Pires and Csaba Szepesvári. Multiclass Classification Calibration Functions. arXiv e-prints, art. arXiv: 003355, September 2016.
[61] Bernardo Ávila Pires, Mohammad Ghavamzadeh, and Csaba Szepesvári. Cost-sensitive mul- ticlass classification risk bounds. In Proceedings of the 30th International Conference on International Conference on Machine Learning- Volume 28, pages 1391-1399 2013.
[62] Ankit Singh Rawat, Jiecao Chen, Felix Xinnan X Yu, Ananda Theertha Suresh, and Sanjiv Kumar. Sampled softmax with random fourier features. Advances in Neural Information Processing Systems, 32, 2019.
[63] Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. Asymptotics of ridge (less) regression under general source condition. International Conference on Artificial Intelligence and Statistics, pages 3889-3897. PMLR, 2021.
[64] Ryan Rifkin and Aldebaro Klautau. In defense of one-vs-all classification. Journal of Machine Learning Research, 5: 101-1,,, 12 2004.
[65] Mark Rudelson and Roman Vershynin. Hanson- Wright incquality and sub-Gaussian concentra- tion. Electronic Communications Probability, 18:1-9, 2013.
[66] Fariborz Salehi, Ehsan Abbasi, and Babak Hassibi. The impact of regularization on high- dimensional logistic regression. Advances in Neural Information Processing Systems, 32, 2019.
[67] Ohad Shamir. The implicit bias of benign overfitting. arXiv preprint arXiv:2201. 2022.
[68] 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, 19 (1):2822-2878. 2018.
[69] Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis. Sharp asymptotics and op- timal performance for inference in binary models. In International Conference on Artificial Intelligence and Statistics, pages 3739-3749. PMLR, 2020.
[70] Hossein Taheri, Ramtin Pedarsani, and Christos Thrampoulidis. Fundamental limits of ridge- regularized empirical risk minimization in high dimensions. International Conference on Artificial Intelligence and Statistics, pages 2773-2781. PML.. 2021.
14

---

[71] Ambuj Tewari and Peter Bartlett. On the consisteney of multiclass classification methods. Journal of Machine Learning Research, 8:143-157, 01 2005.
[72] Christos Thrampoulidis, Samet Oymak, and Mahdi Soltanolkotabi. Theoretical in- sights into multiclass classification: A nigh-dimensional asymptotic view. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin. editors, Advances in Neural Information Processing Systems, volume 33, pages 8907-8920. Curran As- sociates, Inc., 2020. URL Paper.. 1447788.ca455022422222222228
neurips htt..arppp....pppa/////000/000 cc/ppaperr/222//11eeee
[73] Nilesh Tripuraneni, Ben Adlam, and Jeffrey Pennington. Overparameterization improves robustness to covariate shift in high dimensions. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 13883-1899,, Curran Associates, Inc., 2021. URL bttsttss: Paper. pdf
[74] Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. arXiv preprint arXiv:2009.12286 2020.
[75] Guillaume Wang, Konstantin Donhauser, and Fanny Yang. Tight bounds for minimum &n-nrmm interpolation of noisy data. arXiv preprint arXiv:2111 1.0911 2021.
[76] Ke Wang and Christos Thrampoulidis. Benign overfitting in binary classification of Gaussian mixtures. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4030-4034. IEEE, 2021.
[77] Ke Wang, Vidya Muthukumar, and Christos Thrampoulidis. Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation. arXiv e-prints, art. arXiv:2106.1088 June 2021.
[78] Weichen Wang and Jianqing Fan. Asymptotics of empirical eigenstructure for high dimensional spiked covariance. Annals of statistics, 45(3):1342, 2017.
[79] Jason Weston and Chris Watkins. Multi-class support vector machines. Technical report, 1998.
[80] Blake Woodworth, Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Kernel and deep regimes in overparametrized models. arXiv preprint arXiv: 1.XXiv:990..08222 2019.
[81] Denny Wu and Ji Xu. On the optimal weighted & regularization in overparameterized linear regression. Advances in Neural Information Processing Systems. 33:10112-1011 2020.
[82] Jingfeng Wu, Difan Zou, Vladimir Braverman, and Quanquan Gu. Direction matters: On the implicit bias of stochastic gradient descent with moderate learning rate. arXiv preprint urXiv:2011.02533. 2020.
[83] Ian En-Hsu Yen, Xiangru Huang, Pradeep Ravikumar, Kai Zhong, and Inderjit Dhillon. Pd- sparse: A primal and dual sparse approach extreme multiclass and multilabel classification. In International conference on machine learning, pages 3069-3077. PMLR, 2016.
[84] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint Mi.iv:6611.035.2.. 2016.
[85] Tong Zhang. Statistical analysis of some multi-category large margin classification methods. Journal of Machine Learning Research, 5:1225- 2004.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] In the conclusion as well in the statements of the theorems.
15

---

(c)
Did you discuss any potential negative societal impacts of your work? [No] Because this a purely theoretical puper elucidating the foundations of overparameterized learning. The negative societal impacts are largely matter of opinion whether theoretical insights from idealized models are useful. Because they are useful in teaching, we believe this is a positive social impact. However, some might believe that theoretical results for key ideas can end up having a gatekeeping effect in teaching that disadvantages populations with less access to advanced mathematics, and their mere existence therefore empowers would-be gatekeepers. However, we have attempted to mitigate this risk by building this theory together with more intuitive explanations that, while still mathematical, believe reduce the barrier to accessing the core insights. Since this debate is orthogonal to the specific claims in this paper, didn't feel that it needed to be addressed in the paper itself.
(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]
(b) Did you include complete proofs of all theoretical results? [Yes] But in the Supplemen- tal material since they are too long to fit.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as URL)? [N/A] Not really relevant since there are no empirical experiments, only plots of the regions defined by the theorems which are themselves given by simple linear inequalities.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (c.g., with respect the random seed after rumning ex- periments multiple times)? [N/A] Not applicable since no plots are random any way.
(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] Not applicable since everything could be done by hand.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We cited the papers that inspired us and whose results we are building upon.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "s6KR8U56kLv", "reviewer": "Reviewer_P5J7", "summary": "The paper derives scaling conditions under which the test error of min-norm interpolation for linear k-class classification goes to zero. The analysis is done for Gaussian features, a noiseless model with orthogonal 1-sparse \"true\" parameter vectors for each class and a bilevel covariance model. The derived scaling conditions are then used to compare k-class classification to binary and to regression.", "questions": "* What do we learn from comparing regimes for classification and regression? To certain extent, the fact that classification is less challenging is somewhat to be expected. At the end of the day, the metrics are different, so what is the value of the comparison? Specifically, what is the lesson learnt (perhaps algorithmic?) by such accurate characterizations (in terms of the bilevel ensemble parameter) regimes? While I appreciate the hard work in deriving the bounds that lead to say Figure 2, could the authors comment on what (if any) the take-away message is (beyond multiclass can be harder than binary which can be harder than regression).\n\n* Can the analysis be extended to other models? Eg logistic, Gaussian mixture etc? Could the authors comment on the possible challenges?", "limitations": "yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts\n-----------------------\n* The paper is nicely written and relatively easy to follow \n* Good comparison to related work and contextualization of results\n* Compared to previous work [55] on binary classification, new technical challenges arise in multiclass settings and the authors do a good job in explaining them, as well as, how they resolve\n* Compared to previous work [76] on linear multiclass classification, the bounds have a tighter dependence on the number k of classes. In particular k is allowed to scale with n\n* While I did not have time to check the proofs in details, the results appear correct \n\nWeakness\n-------------------------\n* The paper follows along the lines of recent line of work that compares classification to regression, but is not made clear what is it that we learn from this comparison.\n* The discussion on interpretation of results + proof challenges is somewhat heavily using the notions of survival/contamination, which might make the presentation less accessible to wider audience (eg those not familiar with [55]). Perhaps at least define those? (hence \"3\" on Presentation)\n* The model is quite oversimplified. While much related work uses Gaussianity, the 1-sparse assumption together with the bilevel ensemble appears more stringent. It is also somewhat disheartening that even in this setting, the full regime (Conjecture 6.1) is not characterized.\n\nOverall, I value this a solid set of rather non-trivial result that continue recent investigations on overparameterized linear classification. While the set of tools and ideas is perhaps not particularly new (compared to eg [4,54,55,76]) there are certain non-trivial technical challenges that are being addressed", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "otrgGaTHj6", "reviewer": "Reviewer_xQfF", "summary": "The authors present a setup for multiclass classification with specific assumptions. It requires certain assumptions, e.g. the features are drawn from a gaussian distribution, the labels are a deterministic function of the dimension which has largest feature value. \n\nThey consider a setup where certain parameters depend polynomially on the sample size, that is the number of dimensions, the number of upscaled dimensions, the number of classes and the feature weights. They present a theorem which shows that the generalization error goes asymptotically to zero for a certain relationship between these parameters.  \n\nThey show that for some settings multiclass classification converges, but regression does not, conditioned on the specific setup.", "questions": "Lemma B.1 is adapted from which result in Bartlett [4] ?", "limitations": "na", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "strength:\na novel theoretical result.\n\nweaknesses: \nit is a very specific setting.\nReadability of the paper is a bit challenging, though it comes from the complexity of the topic itself .", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ejLF8MToQ38", "reviewer": "Reviewer_u3HB", "summary": "This paper studies the phenomena of benign-overfitting of interpolating minimum norm linear classifiers. The authors consider the case where the number of classes grows with the number of examples. They study a simplified case in which the ground-truth classifier is obtained by the weight matrix (I_k 0) and under the \"bi-level ensemble\" condition. The results show benign-overfitting can be achieved when the data contain a sufficient number of relevant features and a large number of irrelevant features, and the relevant features have a larger norm than the irrelevant ones.\n\n", "questions": "The 1-sparse noiseless model is very limiting. Do you think the results can easily be generalized to more general settings (e.g., the Gaussian mixture Wang let. al. [76] or general orthogonal matrix instead of (I_k 0) )?\n\nIs it possible to provide finite-sample bounds on the probability of error?\n", "limitations": " ", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The paper is well-written.\n- The topic is relevant to the ML community.\n- The results are, to the best of my knowledge, sound.\n\nWeakness:\n- The ground-truth model is simple, and it is unclear how to generalize it to more realistic models.\n- The results are stated in the asymptotic regime where the number of examples approaches infinity.\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CQUoKm67-G0", "reviewer": "Reviewer_Spga", "summary": "As a purely theoretical work, this paper aims to study the generalization of overparameterized linear models (i.e. minimum-norm interpolator) for multi-class classification in an asymptotic setting where both the number of underlying features and the number of classes scale with the number of training points. Specifically, it considers a bi-level overparameterized linear model with a data generating model with Gaussian features (i.e., $1$-sparse noiseless model). Technically, the survival/contamination analysis framework is adapted to this setting with some novel arguments. Theoretically, the results offer several insights, especially showing that the multiclass problem is “harder” than the binary problem because there are fewer positive training examples per class.", "questions": "1. Can the theoretical results be connected with some experimental phenomena in practice? Please give more discussions.\n2. This work is the first one (as I know) to study the multiclass classification in an asymptotic setting, and it is enough to consider the overparameterized linear model. As for the non-linear model, more discussions can be added.", "limitations": "Although this is a purely theoretical work, it is better to add some experimental results to support the theory.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I am not an expert in the area of overparameterized regimes and benign overfitting-related topics, but I think this work is solid based on my familiar related literature although I may not be familiar with some detailed techniques.\n\n### Originality\nThe results for multi-class classification in an asymptotic setting are novel although the main techniques are adapted from the binary one [55]. Besides, it considers the asymptotic setting while the related work [75] considers the non-asymptotic setting.\n\n### Quality\nThis work is of high quality and sound. Besides, it clearly discusses the difference with the related work [75,55]. I have not carefully checked the proofs and it seems sound. My main concerns are the connections (or insights ) of these theoretical results with the experimental phenomena. Besides, although this is a purely theoretical work, it is better to add some experimental results to support the theory. Moreover, this paper considers the overparameterized linear model, and the non-linear model setting (including deep neural networks) can be discussed more.\n\n### Clarity\nThis paper is well written and organized.\n\n### Significance\nThis work considers the generalization of the overparameterized linear model regime and should be of interest to the community of modern deep learning theory, which is fundemental in the understanding of the success of modern deep learning in practice.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept