Precise asymptotic generalization for multiclass classification with overparameterized linear models
Authors: David Xing Wu
Anant Sahai
Venue: NeurIPS 2023 spotlight (2023)
Keywords: overparameterized
multiclass
classification
theory
generalization
interpolation
bi-level
Gaussian model

Abstract: We study the asymptotic generalization of an overparameterized linear model for multiclass classification under the Gaussian covariates bi-level model introduced in Subramanian et al. (NeurIPS'22), where the number of data points, features, and classes all grow together. We fully resolve the conjecture posed in Subramanian et al. '22, matching the predicted regimes for which the model does and does not generalize. Furthermore, our new lower bounds are akin to an information-theoretic strong converse: they establish that the misclassification rate goes to 0 or 1 asymptotically. One surprising consequence of our tight results is that the min-norm interpolating classifier can be asymptotically suboptimal relative to noninterpolating classifiers in the regime where the min-norm interpolating regressor is known to be optimal. 

The key to our tight analysis is a new variant of the Hanson-Wright inequality which is broadly useful for multiclass problems with sparse labels. As an application, we show that the same type of analysis can be used to analyze the related multi-label classification problem under the same bi-level ensemble.

Precise Asymptotic Generalization for Multiclass Classification with Overparameterized Linear Models
David X. Wu
Anant Sahai Department of EECS UC Berkeley
Department of EECS UC Berkeley Berkeley, CA 94720 david_ wu@berkeer edu
Berkeley, CA 94720 sahai berkeley edu
Abstract
We study the asymptotic generalization of an overparameterizee linear model for multiclass classification under the Gaussian covariates bi-level model introduced Subramanian al. (2022), where the number of data points, features, and classes all grow together. We fully resolve the conjecture posed in Subramanian et al. (2022), new lower
matching the predicted regimes for generalization. Furthermore, bounds are akin to an information--heoretic strong converse: they establish that the misclassification rate goes to 0 or asymptotically. One surprising consequence of our tight results is that the min-norm interpolating classifier can be asymptotically suboptimal relative to noninterpolating classifiers the regime where the min-norm interpolating regressor is known to be optimal.
The key to our tight analysis is new variant of the Hanson- Wright inequality which is broadly useful for multiclass problems with sparse labels. As an application, we show that the same type of analysis can be used analyze the related multilabel classification problem under the same bi-level ensemble.
Introduction
In this paper, we directly follow up on a specific line of work initiated by Subramanian al. (2022); Wu and Sahai (2023). For the sake of self-containedness, we briefly reiterate the context, directing the reader to Subramanian al. (2022) and the references cited therein for more. broader story can be found in Bartlett et al. (2021); Belkin (2021); Dar et al. (2021); Oneto et al. (2023).
Classical statistical learning theory intuition predicts that highly expressive models, which interpolate random labels (Zhang et al., 2016; 2021), ought not to generalize well. However, deep learning practice has seen such models performing well when trained with good labels. Resolving this apparent contradiction has recently been the focus of a multitude of works, and this paper builds one particular thread of investigation that be rooted in Bartlett al. (2020); Muthukumar et al. (2020) where the concept of benign/harmless interpolation was crystallized in the context of overparameterized linear regression problems and conditions given for when this can happen. In Muthukumar et al. (2021), a specific toy "bi-level model" with Gaussian features was introduced to study overparameterized binary classification and show that successful generalization could happen even beyond the conditions for benign interpolation for regression. Following the introduction of the corresponding multi-class problem in Wang al. (2021) with a constant number of classes, an asymptotic setting where the number of classes can grow with the number of training examples was introduced in Subramanian et (2022) where conjecture was presented for when minimum-norm interpolating classifiers will generalize. We are now in position to state our main contributions; afterwards, we expand on the related works.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Our contributions
Our main contribution is crisply identifying the asymptotic regimes where an overparameterized linear model which performs minimum-norm interpolation does and does not generalize for multiclass classification under a Gaussian features assumption, thus resolving the main conjecture posed by (Subramanian et al., 2022). We improve on the analysis of Subramanian et al. (2022); Wu and Sahai (2023), covering all regimes with the asymptotically optimal misclassification rate. When the model generalizes, it does so with misclassification rate o and show matching "strong converse" establishing when it misclassifies, it does so with rate 1 - o(1), where the explicit rate is nearly identical to that of random guessing. The critical component of our analysis is new variant of the Hanson- Wright inequality, which applies to bilinear forms between a vector with subgaussian entries and vector that is bounded and has soft sparsity, notion will define in Section 4.2. We show how this tool can be used to analyze other multiclass problems, such as multilabel classification.
1.1 Brief treatment of related work
Our thread begins with a recent line of work that analyzes the generalization behavior of overparame- terized linear models for regression (Hastie et al., 2022; Mei and Montanari, 2022; Bartlett et al., 2020; Belkin et al., 2020; Muthukumar et al., 2020). These simple models demonstrate how the capacity to interpolate noise can actually aid in generalization: training noise can be harmlessly absorbed by the overparameterized model without contaminating predictions on test points. In effect, extra features can be regularizing (in the context of descent algorithmss' implicit regularization (Soudry et al., 2018; Ji and Telgarsky, 2019; Engl al., 1996; Gunasekar et al., 2018)), but an excessive amount of such regularization causes regression to fail because even the true signal will not survive the training process. Although works in this thread focus on very shallow networks, Chatterji and Long (2023) established that deeper networks can behave similarly. Note that recently, Mallinar et al. (2022) called-out an alternative regime (behaving like --nearest-neighbor learning) called "tempered" overfitting in which training noise is not completely absorbed but the true signal does survive training.
The thread continues in a line of work that studies binary classification (Muthukumar et al., 2021; Chatterji and Long, 2021; Wang and Thrampoulidis, 2021) in similar overparameterized linear models. While confirming that the basic story is similar to regression, these works identify a further surprise: binary classification can work in some regimes where the corresponding regression problem would not work' due to the regularizing effect of overparameterization being too strong. Just as in the regression case, the results here are sharp in toy models: we can exactly characterize where binary classification using an interpolating classifier asymptotically generalizes.
With binary classification better understood, the thread continues to multiclass classification. After all, the current wave of deep learning enthusiasm originated in breakthrough performance in multiclass classification, and we have seen decade of ever larger networks trained on ever larger datasets with ever more classes Kaplan et al. (2020). Using similar toy models (Muthukumar et al., 2020; 2021; Wang et al., 2022), the constant number of classes case was studied in Wang et al. (2021) to recover results similar to binary classification and subsequently generalized to general convex losses with regularization in Loureiro et al. (2021) and student-teacher networks in Cornacchia et al. (2023).
Subramanian et al. (2022) further introduced model where the number of classes grows with the number of training points and proved an achievability result on how fast the number of classes can grow while still allowing the interpolating classifier asymptotically generalize. While Subramanian et al. (2022) gave a conjecture for what the full region should be, there was no converse proof, and they could not show generalization in entire conjectured region. Wu and Sahai (2023) proved a partial weak converse; they showed that the misclassification rate is bounded away from 0 - rather than tending to 1 in some of the predicted regimes.
The model, formally defined in the following section, is a stylized version of the well-known spiked covariance model (Johnstone, 2001; Donoho et al., 2018). On the theoretical front, it is related to several problems such as PCA variants (Montanari and Richard, 2015; Richard and Montanari, 2014)
'Regression failing in the overparameterized regime is linked to the empirical covariance of the limited data not revealing the spiked reality of the underlying covariance (Wang and Fan, 2017). See Appendix of Subramanian et al. (2022). When regression doesn't 't generalize, we also get "support-vector proliferation" in classification problems (Muthukumar et al., 2021; Hsu et al., 2021) which is also intimately related to the phenomenon of "neural collapse" (Papyan et al., 2020) discussed, for example, in Xu et al. (2023).

---

and community detection in the stochastic block model (Abbe, 2017). These models have also been applied in practice for climate studies and functional data analysis (Johnstone, 2001). At a high level, spiked covariance models can be interpreted as linearized version of the manifold hypothesis.
Problem setup
The following exposition is lifted from Subramanian et al. (2022), which we include for the sake of staying consistent and self-contained. In Appendix K, we include an alternative high level framing of the problem which readers may find helpful for intuition.
We consider the multiclass classification problem with & classes, The training data consists pairs {æ,, & ) where 2; E I are i.i.d standard Gaussian vectors?. We assume that the labels & E [k] are generated as follows.
Assumption (I-sparse noiseless model). The class labels & are generated based on which of the first k dimensions of a point æ; has the largest value,
4 = arg max 2. [m]]
mE(k]
Let us emphasize at this point that the classifier that analyze only observes the training data, and does not use any of the data-generating assumptions.
For vector we index its jth entry with æ dbj] Hence, under Assumption 1, a; [m] can be interpreted as how representative of class m the ith training point is.
For clarity of exposition in the analysis, we make explicit a feature weighting that transforms the training points:
</ Aynasli Vj E [d].
Here E IRd contains the squared feature weights. The feature weighting serves the role of favoring the true pattern, something that is essential for good generalization. Again, emphasize that the classifier does not do any reweighting of features; this explicit step is purely syntactic."
The weighted feature matrix X t E Ra is given
X
[VA1
Vazza
where we introduce the notation zj E R² to contain the jth feature from the n training points. Note that 2j (0, are i.i.d Gaussians. We use one-hot encoding for representing the labels the matrix Yoh Raxk
1,
if = m
yoh
y
yh
where
y
(4)
0,
otherwise
Since we consider linear models, we center the one-hot encodings and define
ym
1. k
(5)
Following previous work, we staying within Gaussian features framework. However, develop- ments have confirmed that these models are actually predictive when the features arise from nonlinearities lifting, as long as there is enough randomness underneath (Hu and Lu, 2022; Lu and Yau, 2022; Goldt et al., 2022; Misiakiewicz, 2022; McRae et al., 2022; Pesce et al., 2023; Kaushik et al., 2023).
1 "Our weighted feature model is equivalent other works (e.g. Muthukumar et al. (2021)) that assume that the covariates come from a d- dimensional anisotropic Gaussian with a covariance matrix that favors the truly important directions (Wei et al., 2022). These directions do not have to be axis axis-aligned assumption only for notational convenience. In reality, the optimizer will never know these directions priori.
make that

---

Our classifier consists of k coefficient vectors fm for m E [K]] that are learned by minimum- norm interpolation (MNI) of the zero-mean one-hot variants using the weighted features:*
fm arg min ll
(6)
s.t. x ymn
(7)
We can express these coefficients in closed form as
fm (X""* (x" (X"))"
Ym
(8)
On a test point Teest ~ N(0, Ia) we predict a label as follows: First, we transform the test point into the weighted feature space to obtain Weest where Frest = Vajaresli] for j E [d]. Then we compute & scalar "scores" and assign the class based on the largest score as follows:
i = arg max anaeess
(9)
15msk
By assumption, a misclassification event Eerr occurs whenever
arg max Ørest [m] igmgk
* arg max fr. Diest
(10)
Igmgk
We study where the MNI generalizes in an asymptotic regime where the number of training points, features, classes, and feature weights all scale according to the bi-level ensemble model":
Definition 1 (Bi-level ensemble). The bi-level ensemble is parameterized by p. P. and t where > I, O < r < 1, O <9< (p r)) and 0 S <ttt Here, parameter controls the extent of overparameterization, T determines the number of favored features, q controls the weights on favored features and controls the number of classes. The number of features (d), number of favored features (s), and number of classes (k) all scale with the number of training points (n) as follows:
[n"], = [n"], a,a= n nn k = cs cn d=nn"],-
==
(11)
where is positive integer. Define the feature weights by
15i58
VAg-
(12)
Ilaad d-s
otherwise
We introduce the notation Xp & ed and du A to distinguish between the favoredd
(1-aid d
and unfavored weights, respectively.
We visualize the bi-level model in Fig. 1, reproduced from Subramanian et al. (2022). Intuitively, the bi-level ensemble captures simple family of overparameterized problems where learning can succeed. Although there are d = n² features where d >> n, there is low dimensional subspace of favored, higher weight features of dimension = n², and & n. From this perspective, the bi-le model can be viewed as parameterized version of an approximate linear manifold hypothesis. Depending on the signal strength, the noise added from the d unfavored features can either help generalization ("benign overfitting)) overwhelm the true signal and cause the classifier to fail.
3
Main results
In this section we state our main results and compare them what was known and conjectured previously. Subramanian et al. (2022) use heuristic calculations to conjecture necessary and sufficient conditions for the bi-level model to generalize; we restate the conjecture here for reference.
"The classifier learned via this method is equivalent to those obtained by other natural training methods (SVMs or gradient-descent with exponential tailed losses like cross-entropy) under sufficient overparameterizztton (Wang et al., 2021; Kaushik et al., 2023). Recently, Lai and Muthukumar (2023) showed via an extension of Ji and Telgarsky (2021) that much broader category of losses also asymptotically result in convergence to the same MNI solution for sufficiently overparameterized classification problems.
'Such models are widely used to study learning even beyond this particular thread of work. For example, Tan al. (2023) uses this to understand the privacylgeneraaizaaton tradcoff of overparameterizee learning.

---

ad
Feature weight, v
(l-a)d
n
d = np
Feature index, j
Bi-level feature weighting model. The first features have higher weight and are favored during minimum-nore interpolation. These can be thought of as the square-roots of the eigenvalues of the feature covariance matrix E in Gaussian model for the covariates in Bartlett et al. (2020).
Figure 1:
Conjecture 3.1 (Conjectured bi-level regions). Under the bi-level ensemble model (Definition 1), when the true data generating process is 1-sparse (Assumption 1), TL - the probability of misclassification Pr[Eer)] for MNI as described in Eq. (6) satisfies
0, if < min r,p + +
max {1,9+ +
Pr[Eam]
(13)
1,
if > min - r, + - max (1,9+r) +3]
Our main theorem establishes that Conjecture 3.1 indeed captures the correct generalization behavior of the overparameterized linear model.
Theorem 3.2 (Generalization for bi-level-model). Under the bi-level ensemble model (Definition 1), when the true data generating process is I I-sparse (Assumption 1), Conjecture 3.1 holds.
For comparison, quote the best known previous positive and negative results for the bi-level model, which only hold in the restricted regime where regression fails (q + 1).
Theorem 3.3 (Generalization for bi-level model (Subramanian et al., 2022)). In the same setting as Conjecture 3.1, in the regime where regression fails (q r 1), as - сo we have Pr(Eem] > 0 if
t min (1 [1-r,p+ 1 +))+r), 2, 2- 2].
(14)
Theorem 3.4 (Misclassification bi-level model (Wu and Sahai, 2023)). In the same setting as Conjecture 3.1, in the regime where regression fails (q + 1), as co have Pr[Een]
1 >> min (1 r,p 2(g + r)).
(15)
Let us interpret the different conditions in Conjecture 3.1. To interpret the condition t < 1 first rearrange to + < 1. Recall that the parameter r controls the number of favored features, and hence is proxy for the "effective dimension" of the problem. On the other hand, the parameter t controls the number of classes, so in a loose sense there are n²* parameters being learned. From this perspective, the condition
says that the problem is "effectively underparameterized".
The other condition on p +11 features. To see why, recall that the squared favored feature weighting is X -=----_ So for fixed p. the quantity q + controls the level of favored feature weighting. When g + > 1, the favored feature weighting small enough that regression fails, and the empirical covariance becomes flat. In this case, the condition becomes t < p + 2(g + r) = (p q - r) increases, the amount of favoring decreases, making harder to generalize.
max {1. + r) comes from looking at the noise from the unfavored
(g + r). As q +
For ease of comparison between our main result and Theorems 3.3 and 3.4, we visualize the regimes in Fig. 2, as in Subramanian et al. (2022): Wu and Sahai (2023). In particular, the blue starred and dashed regions in Fig. indicate how Theorem 3.3 only applies where regression fails. contrast, our new result holds regardless of whether regression fails not, as in the the green diamond region and light blue triangle regions. The regions are also completely tight; the looseness between the prior Theorem 3.3 and our result can be seen in the light blue square region.
5

---

The weak converse in the prior Theorem 3.4 captures some of the correct conditions for misclassifica- tion, but again only when + > As depicted in the maroon X region for < 0.25 in Fig. 2b, our main theorem gives strong converse, whereas Theorem 3.4 has nothing to say because q ++ Theorem 3.4 also only proves that the misclassification rate is asymptotically at least 2 In the red circle and maroon X regions, we illustrate how our result pushes the misclassification rate to 1 ((), which requires a more refined analysis. We elaborate on this further Section 4.
1.
We remark that it is simpler to analyze the case where regression fails, as the random matrices that arise in the analysis are flat, i.e. approximately equal scaled identity matrix. However, in the regime where regression works, the same matrices have a spiked spectrum, which complicates the analysis. To smoothly handle both cases, we leverage a new variant of the Hanson- Wright inequality to show concentration of certain sparse bilinear forms; see Section 4.1 for more details.
(26) 0=7.5 (= 0.00
1.0
(2b] g=0.555 p=
10
(2c) p==
0.
0.8
0.4
0.4
02
0.2
b.
0.2
0.4
0.6
9.8
1.0
0.
Ein in 1, favwayy i 0. Emuar [Subramenian et al.22)
Poum - (Theorem 3.2)
Erg D, Paiaay O. Eroi (Theorem 3.2)
Crum 0 (Subramanian et al.22)
Greg 1, Painar - Emai (Theorem
Guuii +1 (Theorem 3.2)
King - farwry + 1, Emas (Theorem 3.2)
Figure 2: Example of regimes for multiclass/binary classification and regression. The white regions correspond to invalid regimes under the bi-level model. The entirety of 2b and all the light blue regions new this paper, showing that the error tends to 1 in the maroon regions.
Technical overview
We now sketch out the proof for our main theorem. As in Subramanian et al. (2022); Wu and Sahai (2023), the starting point is writing out the necessary and sufficient conditions for misclassification.
Assume without loss of generality that the test point Frest No0, La) has true label for some [k:]. Let west be the weighted version of this test point. From (10), an equivalent condition for misclassification is that for some 3 + a, B E [k], we have fl x < <g x i.c. the score for B outcompetes the score for a. Define the Gram matrix A A X"(XXX (ww) (("""" the relative label vector Ay A yo Ya E (-1,0,13", and the relative survival vector ha,5 E Rd which compares the signal from and B:
h [5] 2 1/2 (/ fabl))
(16)
= A-1Ay:
(17)
where to obtain the last line we have used (8). By converting the misclassification condition into the unweighted feature space we see that we will have errors when
da ha, (ai Frest [a] - A (3reest [3]
Σ
Xy
(18)
(
Define the contamination term CNa,3:
CN
x((aa..))))..
(19)
(E(
Note that CNa.9 normalizes the RHS of (18) into standard Gaussian. Indeed, define
z() A
Σ
a ~ NO0 1).
(20)
CN
(e(a,))

---

Since 3 E [k] are favored, we have Aa = Ag Ap. Hence, an equivalent condition for misclassification that there exists some + a, 8 E [k] such that
XF CNa.3
fla [a] [ Z(0).
(21)
We now translate the above criterion into sufficient conditions for correct classification and misclassi- fication and analyze these two cases separately.
Correct classificatton:: For correct classification, it suffices for the minimum value of the LHS of
Eq. (21) to outcompete the maximum value of the RHS, where the max is taken over 3 E [Ki], B + Some algebra, as in Subramanian et al. (2022), shows that we correctly classify if
ming d ((c)
h (a)
12 (3]
min (Frest [a]
Prest (3)
max teest [9]]
max
max; CNa,3
h (a)
SU/CN ratio
closest leature margin
largest competing feature
survival variation
max 2 (9)
(22)
9
normalized contamination
We will show that under the conditions specified in Conjecture 3.1, with high probability, the relevant survival to contamination ratio SU/CN grows at a polynomial rate n" for some v >> 0, whereas the term in the parentheses shrinks at a subpolynomial rate w(n for any 8 > O. Further, by standard subgaussian maximal inequalities, the magnitudes of the normalized contamination no more than O( / logí (nk)) with high probability. Thus, with high probability the LHS outcompetes the RHS, leading to correct classification. See Section 4.1 for more discussion on how we prove tight bounds on the nurvival-oo-contaminatin ratios.
Misclassífication: On the other hand, for misclassification it suffices for the maximum abso- lute value of the LHS of Eq. (21) to be outcompeted by the maximum value of the RHS. Some manipulations yield the following sufficient condition for misclassification:
max Af [ + hag.a [
max (E
Prest [7]]
max (
(23)
ming CNa,8
SU/CN ratio
largest label defining fenture
normalized contamination
We show that within the misclassification regimes in Conjecture 3.1, the aurvival-oo-conaamination ratio SU/CN shrinks at polynomial rate n w for some >> 0. By standard subgaussian maximal inequalities, the largest label-defining feature is O O(Vlog(nk)) with high probability. Gaussian anticoncentration implies that for some 3 af a, 3 E [k:]. Z(() outcompetes the LHS with probability at least _ ol)) Hence, conclude that the model will misclassify with rate at least & asymptotically,
Let us now describe how to boost the misclassification rate to 1 o(1). Notice that the above argument only considered the competition between the LHS of Eq. (23) and one of the Z on the RHS instead of the maximum ( It's not hard
from the definition of 7(3) in Eq. (20) that the (() are jointly Gaussian. For intuition's 's sake, assuming the (8) were independent, then max, (99) would outcompete with probability (1 (11)
In reality, the Z(8) are correlated, but are able to show that the maximum correlation between the (()) is 7 + o(1) with high probability. An application of Slepian's 's lemma (Slepian (1962)) and some explicit bounds orthant probabilities (Pinasco et al. (2021)) implies that max (3) 0 with probability least 1 ---00 Another application of anticoncentration implies that maxę ( > - with probability o11) which finishes off the proof.
4.1 Bounding the survival- ratio
Note that the critical involved part of the proof is nailing down the correct order of growth of the survival to contamination ratio; similar analysis tightly bounds the survival variation and the correlation structure of the (9).
to-contamiination ratio appears in both Eqs. (22) and (23). The most
7

---

To understand the relative survival and contamination, we must analyze the bilinear forms ha,e = =j A Ay. Similarly, to control the correlation of the Z(9), we must understand the correlation between the ha.8 vectors, which reduces to understanding the bilinear forms 2, A Ya for j E [d]. E [k]. The main source of inspiration for bounding these bilinear forms is the heuristic style of calculation carried out in Appendix K of Subramanian al. (2022) that leads to Conjecture 3.1.
To simplify the discussion, we temporarily restrict to the regime where regression fails (q + > 1). However, main technical tool seamlessly generalizes to the regime where regression works (q+r< 1). In the regime where regression fails, A turns out to have a flat spectrum: A x al for some constant a O. Assume for now that A-1 is exactly equal to scaled identity matrix. Then the survival is proportional to 2 Ay, which is a random inner product. Similarly, to bound the contamination terms we must control the random inner product 2j Ay for j & {a, 3}.
Since Ay is a sparse vector - only has 2n nonzero entries in expectation - a quick computation K reveals that B[=] Ay] Ō and E[z] Ay] O. The deciding factor, then, is how tightly these quantities concentrate around their means. A naive application of Hoeffding implies concentration radius of order (Vv)). which would lead to looseness in the overall result. The hope is to exploit sparsity to get a concentration radius of order Ö(Vn/k). This is where our new technical tool Theorem 4.1 comes in, which may be of independent interest; we present it in the following section.
4.2 A new variant of the Hanson- Hanson-Wright Wright inequality
In reality, even in the regime where regression fails, A-1 is not actually perfectly flat. Even worse, in the regime where regression works, A- is actually spiked. Thus, we cannot simply reduce the bilinear form 2 A Ay to an inner product. Instead, we turn the well-known Hanson- Wright inequality (Rudelson and Vershynin, 2013), which tells us that quadratic forms of random vectors with independent, mean zero, subgaussian entries concentrate around their mean. It was used extensively to study binary classification (Muthukumar et al., 2021), and multiclass classification (Subramanian et al., 2022; Wu and Sahai, 2023).
However, just as Hoeffding is loose, so too is the standard form of Hanson-Wing Wright, because it also does not exploit sparsity. This motivates a new variant of Hanson- Wright which fully leverages the (soft) sparsity inherent to multiclass problems with an increasing number of classes. We now formally define the notions of soft and hard sparsity.
Hanson-Wright
Definition 2 (Soft and hard sparsity). For x 1, we say that random vector y = (Vi) has soft sparsity at level æ |Y.] S 1 almost surely and Var(Y:) S n for all On the other hand, we say that y has hard sparsity at level π if at most т fraction of the Y; are nonzero.
In particular, our variant Theorem 4.1 below requires that one of the vectors in the bilinear form has soft sparsity at level æ. Throughout, one should think of π = o(1), and for us indeed π = O One can check that bounded random vector y with hard sparsity level π must also have soft sparsity at level ( so soft sparsity is more general for bounded random vectors. In Table we compare our variant with several variants of Hanson- Wright which have appeared in the literature, some of which involve hard sparsity.
Define the subgaussian norm |elles. (Vershynin, 2018) as I| 1k inf {K: Eexp(s2 ( 22],
(24)
K>0
Theorem 4.1 (Hanson-Writs Wright for bilinear forms with soft sparsity). Let x = (XI....,X) Xx,) Th and y E (Yi,..., Y.).....) E IR" be random vectors such that (X,, Y.) are independent pairs of (possibly correlated) centered random variables such that || I K and Y, has soft sparsity at level n, iee
|Y] S 1 almost surely, and E S n. Assume that conditioned on Y,, ||X, K. Then there exists an absolute constant 0 such that for all M E Ruxa and é we have
}) (25)
Pr x My E|æ My
E] < 2exp
-emin
| K|M
The full proof of Theorem 4.1 deferred to Appendix G. The main proof techniques are heavily inspired by those of Rudelson and Vershynin (2013); Zhou (2019); Park et al. (2022). However, the
8

---

Variant
Assumptions on y
Concentration radius
Classic quadratic*; x² Mæ
same
Ó(I (F)
Sparse bilinear": x: M (-y0 y
Y Ber(T). indep. of X, but not Y; % Ber(T). indep. of Y, but not X; Y a.s., EY, <
0(V M P
Sparse bilinear":: x (M y)
Ó M P)
Theorem 4.1: x: xMMy My
O(V M
Table 1: Comparison of different variants of the Hanson- Wright inequality. In all variants, we assume
that (xt y) = (X,, Y)) are subgaussian, centered, and the pairs (X;, Y.) are independent across i. We use denote elementwise multiplication. which allows to express hard sparsity with the sparsity mask 7 E {0, 1]" The concentration radius corresponds to the size of typical fluctuations guaranteed by the concentration inequality, i.e. the needed for high probability guarantees. (Rudelson and Vershynin, 2013, Theorem 1.1); (Park et al., 2022, Theorem I); (Wu and Sahai, 2023,
Theorem
proof of Theorem 4.1 actually simpler than in Park et al. (2022); Wu and Sahai (2023), as bounded with soft sparsity turns out to be easier to work with than subgaussian with hard sparsity. We refer readers to Wu and Sahai (2023) for a more in-depth discussion of how these new "sparse" variants overcome the limitations of previous proof techniques used to study classification problems.
We briefly illustrate how Theorem 4.1 can be used to get tighter results throughout our analysis. A quick calculation reveals that the label vectors Ay and yo both have soft sparsity at level π = O(1/k). However, Ya does not have hard sparsity as required by the variants in Park al. (2022); Wu and Sahai (2023). Since || 1 S n n||M we obtain concentration radius c which scales like v n//k rather than v (obtained via vanilla Hanson-We Hanson-Wright)
Wright) or n/v (obtained via Sauchy-Schwaryy This gain is crucial tightly analyzing the survival, contamination, and correlation structure.
4.3 Completing the proof' sketch
Theorem 4.1 and the above insights about sparsity and independence allow us to prove the following bounds the relative survival and contamination terms which are tight up to log factors; see the Appendix for more details. For brevity's 's sake, we introduce the notation μ _ ngtr-1.
Proposition 4.2 (Bounds relative survival). Suppose at least (1/nn)
in the bi-level model. With probability
A Xpha,glo) min {u-t, 1 min ) logk.
Next, state bounds contamination.
Proposition 4.3 (Bounds on contamination). Suppose we are in the bi-level model. Then with probability at least - O(1/n), the contamination satisfies
CN. min {M-), 10
(
(26)
favored features
unfavored features
Translating the parameters Propositions 4.2 and 4.3 we see that (i) the relative survival is diminished by factor 1/k as long as k = on)),, and a factor 1/ for i = (2 (this looseness ends up being negligible for the final result) and (ii) the contamination is diminished by factor of 1/ /k. This essentially matches the expected behavior from the heuristic calculation Subramanian et al. (2022). Together with some straightforward algebra, Propositions 4.2 and 4.3 allow to compute the regimes where the survival-to servival-to-contanee contamination ratio SU/CN grows or decays polynomially. This yields the stated regimes in Conjecture 3.1; see Appendix A. 1 for more details.
For technical reasons, the analogous bounds Subramanian et al. (2022) are loose, giving rise to unnecessary conditions for good generalization such as < p 2 and / < 2y + 2. Moreover, we are able to give both upper and lower bounds on the survival and contamination terms, whereas they only give one-sided inequalities for each quantity.

---

5 Discussion
In this paper we resolve the main conjecture of Subramanian et al. (2022). identifying the exact regimes where an overparameterized linear model succeeds at multiclass classification. Our tech- niques also lay the foundation for investigating related generalization for other multiclass tasks and nonlinear algorithms. We hope that by bringing the rigorous proofs closer to the heuristic style of calculation, we open the path for analyzing more complicated and realistic models.
An important next step is to extend our results to more realistic spiked covariance models. For example, one typically observes power-law decay for the extreme eigenvalues in applications. We expect that the bi-level model can be relaxed to allow for constant deviations in the weightings for the favored, non-label defining features and power law decay for the unfavored features. The former change would likely only affect constants in certain areas of the argument that do not crucially depend on the exact constants involved, whereas the latter would likely just change the effective degree of overparameterization (Bartlett et al., 2020). However, even constant fluctuations in weighting for the label-defining features can lead to significant subtleties, as these constant deviations manifest as polynomially large variations in the number of examples of each class. Such heterogeneity between label-defining directions would likely lead to significantly messier conditions for generalization.
Another future direction is to move beyond Gaussian features. It is plausible that similar results would hold for vector subgaussian features which are rotationally invariant, allowing us to rotate into the basis where the features have diagonal covariance. One place where Gaussianity is crucially used is to obtain an explicit lower bound on the margin between the features.
As an example application, we sketch out how our proof techniques imply precise conditions for a variant of the learning task called multilabel classification. In a simple model for multilabel classification, each datapoint can have several of k possible labels - corresponding to the positive valued features but in the training set only one such correct label is provided at random for each datapoint. We deem that the model generalizes if for any queried label it successfully labels test inputs as positive or negative. We can use the MNI approach here to learn classifiers.
Some thought reveals that the main difference between multilabel classification and multiclass classification from a survival and contamination perspective is that positive features no longer need to outcompete other features. Thus, the main object of study would be the bilinear forms x; A A''ya which is possible thanks Theorem 1. The survival and contamination terms are only affected by the expected values of these bilinear forms, but the expected values match the multiclass behavior up to log factors, which do not affect the regimes where SU/CN will grow or shrink polynomially. A similar analysis thus reveals that MNI will generalize in exactly the same regimes as in Conjecture 3.1. Here, the model generalizes in the sense that with high probability over the labels the model will correctly classify, and failure to generalize means that the model will do no better than a coin toss.
"Ye.
Perhaps surprisingly, resolving Conjecture 3.1 also implies that MNI is asymptotically suboptimal compared to a natural non-interpolative approach: simply make f... equal to the average of all positive training examples of class m. A straightforward analysis, detailed in the supplementary material, reveals this scheme fails to generalize exactly when L < min (1 - - 2(g + r)}. even in the regime where regression succeeds (q + < 1). This is particularly interesting because we have shown that in the regime where regression succeeds, MNI generalizes only when t < min [1 r, p- 1). which is a smaller region. In light of this gap. it would be interesting identify the cntemmatiin-thhoreet barrier for multiclass classification, especially within the broader context of statistical-oompuaatie gaps (see e.g. Wu and Xu (2021); Brennan and Bresler (2020)).
Acknowledgments and Disclosure of Funding
DW acknowledges support from NSF Graduate Research Fellowship DGE-2146752. We acknowledge funding support from NSF AST-2132700 for this work. DW appreciates helpful discussions with Sidhanth Mohanty and Prasad Raghavendra.
'Note that Frei et al. (2023) point out that even leaky ReLU networks trained with a gradient flow can behave like averages of training examples.
10

---

References
Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446-653) 6531, 2017.
Robert Adler, Jonathan E Taylor, et al. Random fields and geometry, volume 80. Springer, 2007.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, (77448):3006333077 2020.
Peter L. Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: statistical viewpoint.
Acta numerica, 30:87-201, 2021.
Mikhail Belkin. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation. Acta Numerica, 30:203-248, 2021. 2021.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4): 167-111671188,, 2020.
Matthew Brennan and Guy Bresler. Reducibility and statistical caaisticllcommpuuationnll gaps from secret leakage. In Conference on Learning Theory, pages 648 148-847.7 PMLR, 2020.
Niladri S Chatterji and Philip M Long. Finite-sample analysis of interpolating linear elassifiers in the overparameterized regime. Journal of Machine Learning Research, 22(129):11333 2021.
Niladri S Chatterji and Philip M Long. Deep linear networks can benignly overfit when shallow ones do. Journal of Machine Learning Research, 24(117):1-39, 2023.
Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. Comparison and anti-concentration bounds for maxima of gaussian random vectors. Probahility Theory and Related Fields, 162(1):
47-70, 2015.
Elisabetta Cornacchia, Francesca Mignacco, Rodrigo Veiga, Cédric Gerbelot, Bruno Loureiro, and Lenka Zdeborová. Learning curves for the multi-class teacher-student perceptron. Machine Learning: Science and Technology, 4(1 4(1):015019, 2023.
Yehuda Dar, Vidya Muthukumar, and Richard G Baraniuk. A farewell to the bias- bias-variance tradeoff? an overview of the theory of overparameterized machine learning. arXiv preprint arXiv:2109.02355, 2021.
David L Donoho, Matan Gavish, and lain M Johnstone. Optimal shrinkage of eigenvalues in the spiked covariance model. Annals of statistics, 46(4):1742, 2018.
Heinz Werner Engl, Martin Hanke, and Andreas Neubauer. Regularization of inverse problems, volume 375. Springer Science & Business Media, 1996.
Spencer Frei, Gal Vardi, Peter L Bartlett, and Nathan Srebro. Benign overfitting in linear clas- sifiers and leaky relu networks from kkt conditions for margin maximization. arXiv preprint arXiv:2303.01462, 2023.
Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Mare Mézard, and Lenka 7de- borová. The Gaussian equivalence of generative models for learning with shallow neural networks. In Mathematical and Scientific Machine Learning, pages 426-471. PMLR, 2022.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias terms of optimization geometry. In International Conference on Machine Learning, pages 1832-1841, 2018.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):999-98. 2022.
Roger Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
Daniel Hsu, Vidya Muthukumar, and Xu. the proliferation support vectors high dimensions. In International Conference on Artificial Intelligence and Statistics, pages 91-99, PMLR, 2021.

---

Hong Hu and Yue M Lu. Universality laws for high-dimensional learning with random features. IEEE Transactions on Information Theory, 2022.
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference on Learning Theory, pages 1772-1798, 2019.
Ziwei and Matus Telgarsky. Characterizing the implicit bias via primal-dual analysis. In Algorithmic Learning Theory, pages 772-804, PMLR, 2021.
lain Johnstone. On the distribution of the largest eigenvalue principal components analysis. The Annals of statistics, 29(2):295-322) 2001.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0883 2020.
Chiraag Kaushik, Andrew McRae, Mark A Davenport, and Vidya Muthukumar. New equivalences between interpolation and svms: Kernels and structured features. arXiv preprint arXiv:2305.00 02304,
2023.
Kuo-Wei Lai and Vidya Muthukumar. General loss functions lead to (approximate) interpolation in high dimensions. arXiv preprint XXiv:23333007475 2023.
Bruno Loureiro, Gabriele Sicuro, Cédric Gerbelot, Alessandro Pacco, Florent Krzakala, and Lenka Zdeborová. Learning gaussian mixtures with generalized linear models: Precise asymptoties in high-dimensions. Advances in Neural Information Processing Systems, 34:10144-101577 2021.
Yue M Lu and Horng-Tzer Yau. An equivalence principle for the spectrum of random inner-product kernel matrices. arXiv preprint arXiv:2205.06330 2022.
Neil Mallinar, James Simon, Amirhesam Abedsoltan, Parthe Pandit, Misha Belkin, and Preetum Nakkiran. Benign, tempered, or catastrophic: Toward a refined taxonomy of overfitting, Advances in Neural Information Processing Systems, 35:1182:1111 15::1182-1199 1195, 2022.
Andrew D McRae, Santhosh Karnik, Mark Davenport, and Vidya K Muthukumar. Harmless inter- polation in regression and classification with structured features. In International Conference on Artificial Intelligence and Statistics, pages 5853-5875. PMLR, 2022.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75 (4):667-766, 2022.
Theodor Misiakiewicz. Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression. arXiv preprint arXiv:2204. J0425, 2022.
Andrea Montanari and Emile Richard. Non-negative principal component analysis: Message passing algorithms and sharp asymptotics. IEEE Transactions on Information Theory, 1450::148-444 2015.
Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpo- lation of noisy data in regression. IEEE Journal on Selected Areas in Information Theory, 1(1): 67-83, 2020.
Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel J. Hsu, and Anant Sahai. Classification vs regression overparameterized regimes: Does the loss function matter? Journal of Machine Learning Research, 22:222:1-222:68 2021.
Luca Oneto, Sandro Ridella, and Davide Anguita. Do really need new theory to understand over-paramettrrizatonn? Neurocomputing, page 126227, 2023.
Vardan Papyan, XY Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117(40): 24652-24663, 2020.
12

---

Seongoh Park, Xinlei Wang, and Johan Lim. Estimating high- sigh-dimensional covariance and precision matrices under general missing dependence. Electronic Journal of Statistics, 15(2):4868 4915, 2021.
Seongoh Park, Xinlei Wang, and Johan Lim. Sparse Hanson- Wright inequality for a Bilinear Form of Sub-Gaussian variables. arXiv preprini urXiv:2209.05663 05680, 2022.
Luca Pesce, Florent Krzakala, Bruno Loureiro, and Ludovic Stephan. Are gaussian data all you need? extents and limits of universality in tigh-dimensional generalized linear estimation. arXiv preprint arXiv:2302.08923, 2023.
Damián Pinasco, Ezequiel Smucler, and Ignacio Zalduendo. Orthant probabilities and the attainment of maxima on vertex of simplex. Linear Algebra and its Applications, 610:785- 80855-03, 2021.
Emile Richard and Andrea Montanari. A statistical model for tensor pea. Advances in neural information processing systems, 27, 2014.
Mark Rudelson and Roman Vershynin. Non-asymptotis theory of random matrices: extreme singular values. In Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II-IV: Invited Lectures, pages 1576-1602. World Scientific, 2010.
Mark Rudelson and Roman Vershynin. Hanson- Hanson-Wright Wright inequality and sub-Gaussian concentration. Electronic Communicutions in Probubility, 18:1-9, 2013.
David S. Slepian. The one-sided barrier problem for gaussian noise. Bell System Technical Journal, 41:463-501, 1962.
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.
Vignesh Subramanian, Rahul Arya, and Anant Sahai. Generalization for multiclass classification with overparameterizze linear models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL
Jasper Tan, Daniel LeJeune, Blake Mason, Hamid Javadi, and Richard G Baraniuk. A blessing of dimensionality in membership inference through regularization. In International Conference on Artificial Intelligence and Statistics, pages 10968-10993. PMLR, 2023.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
Guillaume Wang, Konstantin Donhauser, and Fanny Yang. Tight bounds for minimum ε--mrrm interpolation of noisy data. International Conference on Artificial Intelligence and Statistics, PMLR, 2022.
pages
Ke Wang and Christos Thrampoulidis. Benign overfitting in binary classification of Gaussian mixtures. In ICASSP 2021-202 IEEE International Conference on Acousties, Speech and Signal Processing (ICASSP), pages 4030-4034. IEEE, 2021.
Ke Wang, Vidya Muthukumar, and Christos Thrampoulidis. Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation. arXiv e-prints, art. arXiv:2106.10866 June 2021.
Weichen Wang and Jianqing Fan. Asymptotics of empirical eigenstructure for high dimensional spiked covariance. Annals of statistics, 45(3):1342, 2017.
Alexander Wei, Wei Hu, and Jacob Steinhardt. More than toy: Random matrix models predict how real-world neural representations generalize. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Leurning, volume 162 of Proceedings of Machine Learning Research, pages 23549-23588. PMLR, 17-23 Jul 2022. URL https::t//. hattps::/ppoottt http:///doo/o......// mlr. press/vv62/ wei22a. html.
13

---

David X Wu and Anant Sahai. Lower bounds for multiclass classification with overparameterizze linear models. In International Symposium on Information Theory, 2023.
Yihong Wu and Jiaming Xu. Statistical problems with planted structures: Information-theorrtica and computational limits. Information-Theerett Methods in Data Science, 383:13, 2021.
Mengjia Xu, Akshay Rangamani, Qianli Liao, Tomer Galanti, and Tomaso Poggio. Dynamics in deep classifiers trained with the square loss: Normalization, low rank, neural collapse, and generalization bounds. Research, 6:0024, 2023.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint 1rXiv:1611.03552 2016.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Shuheng Zhou. Sparse Hanson-Wrigee inequalities for subgaussian quadratic forms. Bernoulli, 25 (3): 2019.
14

---

Contents
1
Introduction
1.1 Brief treatment related work
2 Problem setup
3 Main results
4 Technical overview
4.1
Bounding the survival-to-cootaannntioo ratio
4.2 A new variant of the Hanson- -Wrigtt inequality
8
4.3 Completing the proof sketch
5
Discussion
10
A Preliminaries and notation
17
A.I Proof of Theorem 3.2
18
B Main tools
22
B.I Hanson-Wrighh Inequality
22
B.2 Gram matrices and the Woodbury formula
22
B.3 Concentration of spectrum
24
Utility bounds: applying the tools
25
D Bounding the survival
28
Bounding the contamination
29
E.1 Upper bounding the contamination from label-defining-ffvordd features
30
E.2 Lower bounding the contamination from label-deffming--fvored features
31
E.3 Bounding the unfavored contamination
32
F
Obtaining tight misclassification rate
34
F.1
Main results for tight misclassification rates
35
F.2
Lower bounding the denominator
36
F3
Upper bounding the numerator: the unnormalized correlation
36
F.3.1
Bounding the favored correlation
36
F.3.2
Bounding the unfavored correlation
39
G A new variant of the Hanson- Harghn-Wright inequality with soft sparsity
40
G.1 Diagonal terms
40
G.2 Offdiagonal terms
H Proofs of main lemmas for concentration of spectrum
42
15

---

I Miscellaneous lemmas
45
Comparison the straightforward non-interpolative scheme
46
K Alternative framing of bi-level ensemble
47
16

---

A Preliminaries and notation
For positive integers n, we use the shorthand [n] _ {1...., n.. For a vector v E R" ||o|l2 always denotes the Euclidean norm. We index entries by using square brackets, v[j] denotes the jth entry of V. For any matrix M m2 we denote its ijth entry by maj. | denotes the spectral norm, and ||
(FMM' M) denotes the Frobenius norm. We use max (M) and miin (M) ) to denote the maximum and minimum singular values of M, respectively. If M E R is symmetric, we write #1 (M) Z (2(M 2 ... 2 pn (M) denote the ordered eigenvalues of M. Given two vectors V, u E R", we write o E R to denote the entrywise product of and u.
We make extensive does not depend on n, and all statements hold for sufficiently large n. If f(m) = O(g(n)). then (n) S. cg(n) for some c. If fn) O(g(n)), then f(n) S cg(n) poly log(n) for some c. If f()) = ((g(n)) then for all e > we have (n) I cg(n). We write f(n) ((g(n) if f(n) Z cg(n) for some c. Finally, we write f(n) (n)) if there exists positive constants e₁ and such that (ng(n) $ f(n) S c2g(n).
of big-O notation. In this paragraph, refers to positive constant which
Table 2: Notation
Symbol
Definition
Dimension
Source
k
Number of classes
Scalar
Sec. 2
Number of training points
Scalar
Sec. 2
Dimension of each point the total number of features
Scalar
Sec.
The number of favored features
Scalar
Def.
a
The constant controlling the favored weights
Scalar
Def.
P
Parameter controlling overparameterizztion (d = n²))
Scalar
Def.
r
Parameter controlling the number of favored features (s = n²)
Scalar
Def.
g
Parameter controlling the favored weights (a n 9)
Scalar
Def.
t
Parameter controlling the number of classes (k = cxn²)
Scalar
Def.
Ck
The number of classes when 0 (k cyn')
Scalar
Def.
y
Squared weight of the jth feature ith training point (unweighted) Class label of ith training point ith training point (weighted)
Scalar
Def.
Length-d vector
Sec. 2
Scalar
Eqn. I
un;
Length-d vector (n x d)-matrix Length-n vector
Eqn. 2
X"
Weighted feature matrix The collected jth features of all training points
Eqn. 3
Eqn. 3
goh
One-hot encoding of all the training points for label m One-hot label matrix
Length-n vector
Eqn. 4
y
(n x ka-matrix Length-n vector
Eqn. 4
ym
Zero-mene mean encoding of the training points for label m
Eqn. 5
fm
Learned coefficients for label m using min-norm interpolation
Length-d vector Length-d vector
Eqn. 8
Prest
A single test point A single weighted test point
Sec.
Length-d vector
Sec. 2
test
A
Gram matrix A X X""""
(n X n)-matrix
Sec. 4
(A)
The ith eigenvalue of matrix A, sorted in descending order Squared favored feature weights: XF ad
Scalar
App.
AF
Scalar
Def.
Squared unfavored feature weights: AF (1-a)d
Au
Scalar
Def.
d-s
ha.8
Relative survival hooelil X, ( fobl)
Length-d vector
Eqn. 16
Normalizing factor (Na.3 / /E >3 (3(
CNa.9
Scalar
Eqn. 19
The subgaussian norm a scalar random variable The subexponential norm of a scalar random variable
Scalar
Eqn. 24
Scalar
Eqn.
Factor controlling whether regression works, 2 ?-r-- Unweighted subset of favored features, where T [s] Weighted subset of favored features, WT VA ZT
Scalar
App- A.1
ZT
(n -ma)mixtrx
App. B.2
WT
(n -
App. B.2
A_T
Leave-T -out Gram matrix, where T' C [s], A A WrWT
(n n n)-matrix
Eqn. 74
H
Hat matrix, H, Wt A
(k x k)-matrix
Eqn. 53
17

---

Let us now describe the organization of the appendix. In Appendix A.I, we give more detailed proof sketch and introduce the main propositions that complete the proof of Theorem 3.2. In Appendix B, we introduce the main tools that allow us to prove that the critical bilinear forms 2, A- Ay concentrate: our new variant of the Hanson- Wriiht inequality, the Woodbury inversion formula, and Wishart concentration to bound the spectra of the relevant random matrices that appear. In Appendix C we apply these tools to bound some useful quantities that repeatedly appear in the rest of the proofs. After that, we proceed to bound the survival, contamination, and correlation structure in Appendices D to F. In Appendix J, we present the analysis for the averaging scheme described in Section 5. Finally, prove new variant of Hanson-Wright Wright (Theorem 4.1) in Appendix G.
A.1 Proof of Theorem 3.2
In this section, we fill some of the details of the proof sketch of Theorem 3.2. After recalling the beginning of the proof, we will split up the proof into two subtheorems: one for the positive result where MNI generalizes (Theorem A.2), and another for the negative result where MNI misclassifies (Theorem A.4).
Assume without loss of generality that the test point Brest No, La) has true label for some [k]. Let ztest be the weighted version of this test point. From (10), an equivalent condition for misclassification is that for some + a, B [k), have fa x < f a i.e. the score for outcompetes the score for a. Define the Gram matrix A X (X")" "T, the relative label vector Ay A Yo y/ E (-1,0,1)", and the relative survival vector Ra Rd which compares the signal from a and B:
h [i] A X, (fa fabi))
(27)
= = A Ay.
(28)
where to obtain the last line have used the explicit formula for the MNI classifiers (8). By converting the misclassification condition into the unweighted feature space we see that we will have errors when
Aa
[a] (3 Frest [3]
Σ
Xyheg,alilaeeen [i]-
(29)
2E(0,8)
Define the contamination term CNa.s:
CNa.8 8
A
Σ
(30)
jEta,9
Note that CNa,9 normalizes the RHS of (29) into standard Gaussian. Indeed, define
z(A)=
Σ
Xyhe,ali ~ N 1).
(31)
CNa j#(a,3)
Since a, 3 E [k]] are favored, we have dr = Ag = Ap. Hence an equivalent condition for misclassifi-
cation is that there exists some 3 & a. 3 [k] such that
d CN...
saa]arat [a] (8) [8]) < 2
(32)
We will translate the above criterion into sufficient conditions for correct classification and misclassi- fication and analyze these two cases separately.
First, let us present our tight characterization of the survival and contamination terms, which will be useful for both sides of the theorem. Recall our definition of μ & n whether this quantity polynomially shrinks or decays directly determines if regression works or fails.
Proposition 4.2 (Bounds on relative survival). Suppose we are in the bi-level model. With probability at least O(1/n), X Xpha,glaj min {u 1,=1,11600
1) min ( Vlgkk
18

---

Proposition 4.3 (Bounds on contamination). Suppose we are in the bi-level model. Then with probability least O(1/n), the contamination satisfies
CNa.3 min {u 01
(
(26)
favored featuees
unfavored features
We defer the proof of Proposition 4.2 to Appendix 1) and the proof of Proposition 4.3 to Appendix E. Combining Propositions 4.2 and 4.3 yields the following sufficient conditions for when the SU/CN ratio grows or shrinks polynomially.
Proposition A.1 (Regimes for corivvalto--onttainntionnn Under the bi-level ensemble model (Def- inition 1), when the true data generating process is 1-sparse (Assumption 1), as n + Jc, with probability at least O(/nn) the survivl-to-contamnnatoo ratio satisfies
ming xla
2 n for some v > 0 ift < min - 11--;;7 p 2 max (1,9+ (33)
max, CN.,.
maxg AF [a]
In- for some > 0 ift min (1 r.p max (1, +]] (34)
ming CNa.8
Here, the max and min are being taken over 3 # a. 3 E [k].
Proof. We do casework on whether we want to prove an upper bound or lower bound on SU/CN. First, suppose we want to prove the lower bound, so assume < min {1 r, p + 2 max {1, q + r]]. Since t r by the definition of the bi-level ensemble (Definition 1), we have that < 2- So by union bounding over 3, Proposition 4.2 implies that with probability - 0(1/n)
min X [aa 2 min 1 Vogk k.
(35)
Then from Proposition 4.3, by union bounding over 3 see that with probability 1 O(Ln).
max CN S min 1
features
unfavored features
Let us combine these two bounds. If we compare the survival to the contamination coming from favored features, we obtain
min {u 1, 11,,,111000 3/ooooooo min (--1, 1)0(n (0))
n
(36)
log nss)
n
(37)
log(nsk)
where we have included the explicit poly log factors for precision. Hence, if t < 1- r, the numerator grows polynomially and dominates the denominator. Now let's compare the survival to the contamination coming from unfavored features. This yields
min {n 1 .13n Vlog K min
(38)
Ö(n -
log (og())))
n max 1,0r--100). n
(39)
log(nsk)
p+ 1- 2 max
(1att)-
n
(40)
log(nsk)
Hence, by union bounding, we see that with probability (1/n))
Xptin,e(a]
min
nn"
(41)
CNa.9
19

---

where V - } (min {1 -1 r,p+1 1- max {1, + + t) > 0 by assumption.
For the upper bound, suppose i min {1 --p+ 2 max {1,9 +r)]. Hence union bounding we conclude that with probability at least 0(1/n),
0, and by
max Ap [a]] min {a 10:0nn /llg/ log
(42)
and
min CNa,3 2 min (ur) 11=",1)06m - + 2(n =
(43)
D
Combining these and union bounding yields that with probability 1 O(1/n),
Apha,,aaa]
min
S
(44)
CNa,8
where w A [t min (1 - mmax (1, > 0 by asssumption.
We now sketch a proof of both the positive and negative sides of Theorem 3.2. We point out that the regimes for generalization and misclassífication exactly match the regimes above for where the SU/CN ratio grows or shrinks polynomially.
Theorem A.2 (Positive side of Theorem 3.2). Under the bi-level ensemble model (Desinition 1). when the true data generating process is 1-sparse (Assumption 1), as n + 0c, the probability of misclassification for MNI satisfies Pr[Eer] + 0 if
min [1 r. p. max {1. +r]
Proof sketch. For correct classification, it suffices for the minimum value of the LHS of Eq. (32) to
outcompete the maximum value of the RHS, where the max is taken over 3 E [k],, B K a. Some algebra, as in Subramanian et al. (2022), shows that we correctly classify if
ming Xphos Xpho
h [a]
hgg [3]
min (Zrest [a] Frest [3])
max Erest [8]|
max
max3 CN..3
h [a]
SU/CN ratio
closest feature margin
largest competing feature
survival variation
max Z (3)
(45)
normalized contamination
By our lower bound the survival to contamination ratio (Proposition A.1), assuming
min [1 arl-r,++1-- 2(q + r)), then with probability least 1 - ((Ln)) we have that Apha.glo CNa.9
n" for some constant 0. By Lemmas B.2 and B.3 in Subramanian et (2022) for every > with probability at least - e, we have ming Frest [a] Frest [8] 2 Q Vlogk!
Next, by standard subgaussian maxima tail bounds we have that | [3]] S 2 2olo and
2 < 2 (log(nk) with probability at least O(1/kk). Finally, applying our upper bound on the relative survival variance (Proposition A.3, which we prove below), the survival variation is at most a polynomially decaying
with probability least 1 O(1/nk).
By union bounding, we see that with probability least 1 O(1/n) - e, the LHS outcompetes the RHS, implying that the model correctly classifies.
In fact, given Proposition 4.2, it is straightforward to bound the survival variation.
Proposition A.3 (Upper bound on the survival variation). Suppose that t r. With probability at least - 2/n,, we have
h [a]
hg [3]
S ein "
(46)
ha (a]
where e₁ and both positive constants.
20

---

Proof. Since we have ha,pla] = 2, A-1 Ay. the survival variation is
ha h [3] 2/ A-1 Ay + 23 Ay
[aa
2 A-
Since t < 1- and < r by definition, we know that < and we can apply Proposition 4.2 to see that with probability least 2/n we have
2, A A Ay max {u- . (1 ( On
log -
A Ay
Hence we have
ha.a [a] h
I kn
(47)
ha.gla]
where is an appropriately defined positive constant.
Theorem A.4 (Negative side of Theorem 3.2). Under the bi-level ensemble model (Definition 1). when the true data generating process is 1-sparse (Assumption 1), as n. + oc, the probability of misclassification for MNI satisfies Pr[Cer] + if
1> min [1 p + max {1, +3)
Proof sketch. On the other hand, for misclassification it suffices for the maximum absolute value of the LHS of Eq. (32) be outcompeted by the maximum value of the RHS. Some manipulations yield the following sufficient condition for misclassificatio:
max3 \F [Ma.ola) + [2g.a 181)
max EE(K]
Frest (yll
max ( 3
(48)
ming CNa.8
SU/CN ratio
largest label defining Teature
normallized contamination
Within the misclassification regimes in Conjecture 3.1, Proposition A.1 implies that the survival- to-contamination ratio SU/CN shrinks at a polynomial rate n-w for some w > By standard subgaussian maximal inequalities, the largest label-defining feature O ((olog(nk) with high probability. Gaussian anticoncentration implies that for some 3 * a, 8 E [k], Z (a) outcompetes the LHS, which is bounded above by n w with probability least 2/2 o(1) Hence, conelude that the model will misclassify with rate least & asymptotically.
Let us now describe how to boost the misclassification rate to 1 - o(1). Notice that the above argument only considered the competition between the LHS of Eq. (48) and one of the (0))s on the RHS instead of the maximum ( It's not hard to see from the definition of Z in Eq. (31) that the (B) are jointly Gaussian. For intuition's sake, assuming the (0) were independent, then max; (9) would outcompete with probability (} =11))=-1.
In reality, the ((9) are correlated, but we are able to show that the maximum correlation between the (3) is 1/2 + o(1) with high probability. An application Slepian's 's lemma (Slepian (1962)) and some explicit bounds on orthant probabilities (Pinasco et al. (2021)) implies that max Z > with probability at least 1 . An application anticoncentration for Gaussian maxima (Chernozhukov et al., 2015) implies that max, (8) > nw with probability 1 1 o(1, which finishes off the proof.
To fill in the details of the above proof sketch, we will prove the following proposition in Appendix F.
Proposition A.5 (Correlation bound). Assume we in the bi-level ensemble model (Definition l), the true data generating process 1-sparse (Assumption 1), and the number of classes scales with n. (i.e. t 0). Then for every O, we have
- (
Pr
max 3
Z > n
2 21-6
[1+o(1))
(49)
for sufficiently large and any > 0.
21

---

B
Main tools
In this section we introduce our suite of technical tools that allow us to prove the desired rates of growth for survival, contamination, and correlation.
B.1 Hanson- Hanson-Wright Inequality
As established in Section 4, we need the Hanson-Wrightt inequality to prove our tight character- ization of generalization. For the sake of precision, we explicitly state our definitions of subgaussian and subexponential which
throughout the of the paper.
The subgaussian norm ||E|| da of random variable & is defined as Rudelson and Vershynin (2013),
|| |1 = inf {K: Eexp (52 //²) 23. K>0
(50)
The sub-exponential norm p| is defined as in Vershynin (2018, Definition 2.7.5):
| inf {K (x /K)/////////// s 2).
(51)
K30
We will occassionally need use the following variant of Hanson Hanson-Wright for nonsparse bilinear forms, first proved in Park et al. (2021).
Theorem B.1 (Hanson- Wright for bilinear forms without sparsity). Let x (X....., X,)
In and E (Yi,..., Yn) be random vectors such that the pairs (X,, Yi) are all independent of each other (however X; and Y; can be correlated). Assume also that [E[,,] = E.Y.] = and
max { ||XxIllu2 [1Villes.) } S K. Then there exists an absolute constant M 1xxx and 2 0 have
such that for all
KII K2I ))-
Pr 1 My E|Ø² Myll
> E| < 2exp
-cmin
(52)
Finally, we restate our new version of Hrnson-Wright for bilinear forms with soft sparsity, which prove in Appendix G.
Theorem 4.1 (Hanson-Wirt Wright for bilinear forms with soft sparsity). Let x = (Xi....,X, R and y E (Yi,..., Ya) E Rn be random vectors such that (X;, Y:) are independent pairs of (possibly correlated) centered random variables such that X S and Y; has soft sparsity at level n, iee
[Y S 1 almost surely, and E[Y,") S л. Assume that conditioned on Y,, [|X S K. Then there exists an absolute constant
O such that for all M Buxa and we have
K|M 1)
Pr [ My E[x Myl c 2exp
-cmin
(25)
|2
B.2 Gram matrices and the Woodbury formula
In order apply Hanson-Wright to the bilinear form x: My. need have deterministic matrix M such that the hypotheses are satisfied. However, in our setting we study bilinear forms such as 2/ A Ag. Here, the inverse Gram matrix A is not independent of zj or Ay, so we cannot simply condition on A1 The way around this to cleverly decompose A- using the so-called Woodbury inversion formula (stated formally below), which generalizes the leave-one-out trick and Sherman-Morrson
Morrison used to study binary classification Muthukumar et al. (2021). To that end, we will explicitly decompose the Gram matrix A e Ejed > based on whether the features 2j are favored or not.
We now introduce some notation to keep track of which matrices contain or leave out which indices. In general, we use subscripts to denote which sets of features we preserve or leave out; we use minus sign to signify leaving out. The k label-defining features are represented with a subscript k whereas the s favored but not label defining features are represented with a subscript F. The rest of the d - unfavored features are represented with a subscript U.
22

---

For notational convenience, we introduce some new notation for the weighted features, as the superscript w denote weighted features is rather cumbersome. We denote the weighted label- defining feature matrix by W _ [w] denote the weighted observations for feature i. Define the unweighted label-defning feature matrix žk| E R=*k Similarly, define Wp [wa+1
wx E R where the vectors w; _ VA,z, TR
Zy A [z]
w. [=*((==)), which
contains the rest of the weighted favored features and the corresponding unweighted version Zp.
Let A-k - EigRK waw. denote the leave-k-out Gram matrix which removes the k label-defining features. Similarly, let A-F - EigloNi wm E [R to denote leave-(s - ouu Gram matrix which removes the favored but not label-defining features. Finally, let A Σ ig[a) u.w. E R denote the leave-s-out matrix which only retains the unfavored features. We will also sometimes write A_, instead of Ay to emphasize that the favored features have all been removed.
Define the so-called hat matrices by
H W A W E R
(53)
Hr W Wr E (R+
(54)
These hat matrices appear in the Woodbury inversion formula. For the sake of notational compactness, define
M₁ & W + Ha) R
(55)
Mp A Wp(I. Hp) W E ER'
(56)
The Woodbury inversion formula yields
A-1 (W W + A-x
(57)
A k A WI + H Ha) A
(58)
A - A M,
(59)
Left multiplying (58) by W yields
W A - W. A HH H
W A (I HH(TT + H₂) H))- A-1
(60)
(61)
(I& + Ha)-"W, A
(62)
We can derive completely analogous identities using A instead of A-1 1 The above exposition is summarized by the following lemma.
Lemma B.2. We have
WT A Ay (L, + H - A
(63)
WJ A Ay = (I,- Hp) HP) WT A A
(64)
Lemma B.2 is quite powerful. Indeed, consider the action of the linear operator W. A-1 R R on Ay. The action is identical to that of the linear operator W. A T R up some invertible transformation. This new linear operator is nice because A & is independent of Wx and Ay, as it removes all of the label-defining features. Reclaiming independence sets the stage for using our variant of Hanson-Wright,
How does the invertible operator (I + H+)) act? Our general strategy is to show that Hg is itself close to a scaled identity matrix, i.c. H2 se vIs for an appropriately defined v. Then for any i [k]. we have that
w Ag (1+ A
Of course, there will be some error this approximation, as H₁ not exactly equal vIg- Nevertheless, can bound away the error that arises from this approximation.
23

---

B.3 Concentration of spectrum
As foreshadowed in the previous section, we will leverage the fact that the hat matrices such as H are close to scaled identity. To formalize this, we appeal to random matrix theory and show that the spectra of various random matrices are very close to being flat (i.e. all eigenvalues are within 1 + o(1) of each other). To that end, present the following standard characterization of the spectrum of standard Wishart matrix, which is Equation 2.3 in Rudelson and Vershynin (2010).
Lemma B.3 (Concentration of spectrum for Wishart matrices). Let M E Mm with M > m be a real matrix with iid (0,, 1) entries. Then for any 2 O, we have with probability at least 1 - 2e - that
VM Vm E min (M) S max (M) S VM + mm t.
(65)
In other words, the singular values of M satisfy subgaussian concentration.
Since pm Mm (M M) min (M)² and μı (M M) Omax (M)?, we can conclude that if m
o(M), then for any > O we have
M M-22/Mm-e-o(V Mm) S pm (M M) S <M M) S M-22MMMtttt(/MMM (66)
with probability at least 2e 2212
On the other hand, consider MM TM E R.M.M Its spectrum is just that of M M E Rmxm with an additional M m zeros corresponding to the fact that m < M.
We can use Lemma B.3 to prove concentration of the spectrum of the various matrices introduced in Appendix B.2. Let us summarize some convenient forms of these results; their proof' are deferred to Appendix H.
Proposition B.4 (Gram matrices have a flat spectrum). Recall that Au = Rexn is the unfavored Gram matrix and A_k Ej>ı> }z2z2] RRax is the leave-k-out Gram matrix.
A- Ejza }z E
Then the following hold with probability at least 1 - 2 -
(a) For all i E [m], we have μa M.(Au) = nP (*)))
(b) For all i E [s kt), we have
na( (nAA (1
(())))),
(67)
where Kg is a positive constant. Moreover, for all E [n] \/s k]. we have
=A = O(n O(n]))) *T)),
(68)
where K7 is positive constant.
As simple corollary, we can obtain the following cruder bounds on the trace and spectral norm of A and A=
Corollary B.5 (Trace and spectral norm of A In the bi-level model, with probability at least 1 - ne we have
Tr(A7)) n² -P P1 + O(n xy 3) log Tr(A nn' 1P + O(n -X3) l/ogg./
(69)
(70)
and
max {| || || |1] S c2n P.
(71)
where cz N7, and K3 are all positive constants.
Proof. We prove the claim for A b the proof for A similar or easier because A 1 has flat spectrum (Proposition B.4).
24

---

If t < 1, the upper bound for the spectral norn similarly follows. For the trace bounds, we can apply Proposition B.4, we have
Tr(A = (n n² + "n"""""( On ()) + (n" - -n') (1)((11))) (1 P "nn")nn P(1 + O(n (o))
(72)
= n 01
(73)
where
R1 min {r 1,2 q- -223 0,
q + 2r < 2(q + r) < 2 by assumption.
On the other hand, the claim is obviously true when q + 1, as the entire spectrum of A x is (1 + ((n=*2))m² with an appropriately defined positive constant K2- The spectral norm bound follows by defining 0g to be any positive constant greater than which absorbs the o(1) deviation terms in the spectrum.
The proof concludes by setting K3 min K2),
Finally, we have the following proposition which controls the spectrum of hat matrices such as H₂ W A R W E BAxk, The intuition is that even though the spectrum of A may be spiked, the spectrum of WT A We ultimately flat because we are taking an extremely low dimensional projection which is unlikely to see significant contribution from the spiked portion of A
In fact, we can prove more general statement, which will be useful for us in the proof. Let Ø & T C S [s]; here 7 and S index nonempty subsets of the favored features. Then we can define Wr to be the matrix of weighted features in T and the leave-T -out Gram matrix
A-T
Σ Nz21z]] JØT
(74)
Now define the ST hat matrix as HT.S WT A Wr. Evidently we have H = H [6],[K]] our notion more general. The full proof is deferred to Appendix H.
WT.
Proposition B.6 (Generalized hat matrices are flat). Assume we are in the bi-level ensemble Defini- tion For any nonempty T C C [s], with probability least 1 2e vn eigenvalues lightly controlled:
2e"", n, we have all the
p(((I + HT.s)= = min {u, 1) (1 + er,sn
(75)
where er.s and Ky are positive constants that depend on [T] and |S].
C Utility bounds: applying the tools
Wishart concentration allows us to tightly bound the hat matrix and pass to studying bilinear forms of the form w A Ay rather than w, A-1 "Ay. Since A_ is independent of W₁ and Ay, we can Wright (Theorem 4. to these bilinear forms for every realization of A In this section, we will explicitly calculate the scaling of the typical value of these bilinear forms using the bi-level ensemble scaling; these will prove to be useful throughout the rest of the paper.
condition on A and then apply Hanson- -riigt
We first state the following proposition which bounds the correlation between the relevant label- defining features and the label vectors; it is a combination of Propositions D.5 and D.6 in (Subrama- nian et al., 2022).
Proposition C.I. For any distinct ar, 3 [k)], we have
1
n K
Vink < Elz vol
/2 n
Vlnk
(76)
1n2
and
2
n1
Ink S B(2 yal
n
Vink
(77)
k
k
V 1n2
k k -
25

---

With the above proposition in hand, we can prove the following lemma which gives concentration of the bilinear forms that we study.
Lemma C.2. Let i E [d] and Ay yo Vg where 3 E [k] and 3 & a. Let M E R be (random) matrix which independent of z, and Ay. Then conditioned on M. with probability at least 1 1/nk,
T.MAy E[z, M S cay k
| (lol/))
and the same holds with Ay replaced with yo- Here, 03 is an appropriately chosen universal positive constant.
Moreover, we have
(1) For any distinct a, 3 E [k], we have
Vlog K MEy = 67
(r(M)
-Ezz MAy)
(78)
k
B My M = Vlog Lr(M),
(79)
k
where CT and 0₁ are positive constants.
(2) For [d] (a, we have
Eiz MAy M O.
(80)
(3) Fori [d] \ {a), we have
log K -Cs k:k
Bi2 My. M
(81)
where C3 is a positive constant.
Proof. Let us check the conditions for our new variant of Hanson-Wright with soft sparsity (The- orem 4.1). want to apply it to random vectors (z,, Ay) (z, Ay(;)) Some of hypotheses are immediate by definition. Evidently, (z; [j]. A Ayll)) are independent across j. and are mean zero. Since [ N (0, 1), it is subgaussian with parameter at most K 2. For the bounded and y.us < almost surely. Also, since Similarly, E3ya11 (1 1)2 + (1 1 I ?.
and soft sparsity assumption, we clearly have ا S Aylj]² ~ Ber(")) we have E| [
The more complicated condition is the subgaussianity of 2; [s] conditioned on the value of Aylj] or 1.]. Regardless of whether we're re conditioning Ay or yo it suffices to instead prove that z; [j]] subgaussian conditioned on whether feature won the competition for datapoint j. First, suppose i won, i.e. y0th [] = 1. Then the Borell-TIS inequality (Adler et al., 2007, Theorem 2.1.1) implies that x satisfies a subgaussian tail inequality. By the equivalent conditions for subgaussianity conditionally has
Vershynin (2018, Proposition 2.5.2). follows that 2; [j] []] g1.h [
subgaussian norm bounded by some absolute constant K. If i doesn" win (or doesn't 't participate in the
competition),, then Proposition D.2 in Subramanian et al. (2022) implies that 2; [ E[z, [J] yg [j]
0) conditionally has subgaussian norm bounded by 6.
Finally, since M is independent of and Ay, the bilinear form for every realization of M.
condition M and apply Theorem 4.1 to
Hence, we conclude that with probability least 1 - 1/nck we have
x M - F[=,T M M M| S cs K
| Vlo((nk),
(82)
where cs is an appropriately chosen absolute constant based on and the constant defined in Theorem 4.1.
Now compute E[z, M MAy M to prove the rest of the theorem. If a, have
E E MAy M| tr (ME Ayz
26

---

Let us now compute E[Ayz]] From Eq. (76) in Proposition C.I, we have Elya
C4 yllg k I
where Volg I S v2. Similarly, we have El y Cc k(k follows that yz T =
ylogk In where v= S C5 S 22
lox k
In
For E [d] {a, 8). by symmetry we obtain Efya = Elzg2; J. This implies E Ayy
Elyo 2 [y = 0, so we obtain
B M = (r(ME|Ay=²]
(83)
(84)
Plugging in the bi-level scaling, we obtain the following corollary.
Corollary C.3 (Asymptotic concentration of bilinear forms). In the bi-level model, for any i [A]]
we have with probability at least 1 - O(1/nk) that
A Ay F A Av]l S cgn '=' -P (Vooo(kk).
Moreover, we have
(1) For any distinct a, 3 [k:],
A_ A Au) = 07n frmttt-((11 + O(n (()))))) log = A
-E|z
(85)
The same statements hold (with different constants) if we replace A with A_
Proof. From Corollary B.5, we have | I c&n P, where c is appropriately chosen universal positive constant based on c3. Recall that A- & is obtained by removing the k label-defining features, so in particular A_ is independent of (z,, Ay) for E [k]. Hence, the conditions for Lemma C.2 are satisfied. Then applying the union bound for the spectral norm bound on A_ that with probability least 1 (11/nk), the deviation term from Manson-Wright is at most cgn2 -P /log(nk).
We now turn to calculating the asymptotic scalings for the expectations. From Lemma C.2, we know that B[= A Ay A C7 ylog tr (A_))- Applying the high probability bound on tr (r(A_))
from Corollary B.5, obtain that with probability least 1 O(1/nk) that
[2 A A
E
A = Cyn 'n 1 (1 + O( (m))) Vlogk
(86)
17n + O( 63
Tog
(87)
where in the second line we have applied Corollary B.5 and is appropriately chosen positive constant. This proves (85).
With Corollary C.3 in hand, we are now in a position to do some straightforward calculations and bound some quantities which will pop up the survival and contamination analysis.
Proposition C.4 (Worst-case bound based on Hanson- Hanson-Wright). Let T S [s] be a subset of favored features such that {a, 33 T. Assume that [2'] n² for some 1 - O(L/nk), we have
Then with probability least
7 A 1 Av/l2 S cs 1-1-P 1 Plo())kk((T)))
(88)
Proof. WLOG, suppose and B By Corollary C.3 have with probability at least
1 1/n that
1-n Vlg K C7n 1-m1-1-p Vlog can L Vlog(nk)
ZJ. ATAーTAy <
(89)
Cgn L Mog(nk)
27

---

Hence, the norm of this vector is at most
7 -ー Aull - 20mn' 1- VVlo k + n con 1-f -
(90)
(cs(n 1o + 1 P) Vlog(nk),
(91)
where is positive constant.
D Bounding the survival
Recall that the relative survival was defined to be Xpha,sla] = A- The strategy is to apply our variant of Hanson-Wrin or Ay, so we need to use Woodbury to extract out the independent portions and bound away the dependent portion. As we'll see shortly, the error from the dependent portions can also be controlled using Hanson-We Hanson-Wright. Let now recall Proposition 4.2 for reference.
to 2,] A Ay. Unfortunately, A is not independent of z
Proposition 4.2 (Bounds on relative survival). Suppose we are in the bi-level model. With probubilitt at least - (1/nn)
Ae gla) min {u 100 min (1.)))))))))) Vlog..
[a] = 2 A-1 We first observe that for i E [A).. the dependence between A and z, as well as A and Ay only comes through the k label defining features. Hence, we can use the Woodbury identity to extract out the independent portions of A-1.
Proof. Recall that ha,
Indeed, our "push through" lemma for Woodbury (Lemma B.2) and concentration the hat matrix (Proposition B.6) implies that with extremely high probability
z
A A-'AyA Au = (I + H₂) 2 A A
(92)
min (14 1) (T+ Z A Av.
(93)
where [EI12 O(n -11)K)1).
Let RA E & denote the oth row vector in E, and let u E h denote the subvector of ua without index By reading off the oth row of Eq. (93), we see that
za T A A min {u, 1) (z. A + (ua. Z A_A
(94)
Since U/u
l12
S
E 2 = (n 11] ), it follows from Cauchy- Schwarz that
2 A Ay min {u. 1] 1 A Ayl S min (M, 1n -N
A
2' (95)
Let us pause for a moment and interpret Eq. (95). The term min {u, 1} is merely capturing the difference in behavior when regression works and fails; if regression works (g + r < 1) then becomes na, and if regression fails (g + > 1), then it becomes 1. This behavior should be expected: in the regression works case, we expect the effect of interpolation to be a regularizing one: the signals are attenuated by a factor of μ. The RHS of Eq. (95) is an error term, capturing how differently z,7 A Ay behaves from the expected behavior min {M. 2 A_
Let us now bound the error term. From Proposition C.4 we have with probability at least - 0(1/nk) that
| A S (n t-p + n -) Ilg((kk2)
(96)
Let us do casework on f. For 1 1. have - - p. so we conclude that the error term min {A, 1)0(n n- *4) /lo(nk??), where K4 is positive constant.
On the other hand, our Hanson-Wright calculations imply (Corollary C.3) that with probability at least 1 ((1/n)) that
- A 11 cnn 00 (x)=*))) log k
S can 1 - Vlog(nk).
28

---

Again, since t < 1 the deviation term is o(n' logk.
2'
Hence conclude that with probability ((1/nk))))))))) /nk) have
A
Ay A--Ayy
cy min {u, 13n 10pn----Ppp_ 01 ((n=M))) Vlogk,
where кş is positive constant.
Completely analogous logic handles the bounds for 2/ A Let us now return back to the quantity of interest, Ala)a, We can compute
ApZ 10-A-110 Ay n--9-" or min {u, 13n 11nninnnn(P1 0 ) log
c.p min {u, 1 |m ( + (n \\ogkkk log
Cy min {1, μ In '1 = O(n NS )
On the other hand, if 2 1 the terms all dominate, and replace n nl-t-p with n -p everywhere. We conclude that with probability at least O(1/nk),
2/2 Ayyl
$ 0g min {u, 1nn -P, Vlog(nk).
(97)
where is positive constant. Plugging in the scaling for Xp yields the desired result.
E Bounding the contamination
In this section give tight analysis of the contamination term. First, we rewrite the squared contamination term and separate it out into the contamination from the 2 label-defining features which not B, the rest of the features. From Eq. (30), we have
favored features, and the remaining d unfavored
CN 0, = Σ
2j(=]A4 A-TTA-AA An)
(98)
HE)))a..)
Ay A-1
Σ
A A- Ag
(99)
jE(d)((..8)
AyTA-
A-
Σ
A A- Ay A-
TYTA-!
Σ X2252J
A-'Ay
A
JE
jELTNNA
ACNZ
ACN
(100)
Ag A-
Σ XZ j>8
A-
(101)
ACNE 3.0
Here, C. corresponds to contamination from label defining features, CNa,8,r corresponds to contamination from favored features, and CN.. corresponds to contamination from unfavored features. The reason for separating out the contamination into these three subterms is that we will need slightly different arguments bound each of them, although Hanson-Wrigee Wright and Woodbury central to all of the arguments. In Appendix E.1 we prove the upper bound on CN + CNo.8, in Appendix E.2 we prove the lower bound. Finally, in Appendix E.3 we bound CNa.9,u After putting these bounds together, we will obtain the main bounds on the contamination, which we restate here for reference.
Proposition 4.3 (Bounds on contamination). Suppose we are in the bi-level model. Then with probability at least O(1/n), the contamination satisfies
CNa = min {p-1 1]
(26)
features
features
unfavored features
29

---

E.1 Upper bounding the contamination from label-definnng--fvored features
In this section, we upper bound the contamination coming from the favored features which are not or B. This culminates in the following lemma.
Lemma E.1. In the same setting as Proposition 4.3, we have with probability 1 - ((1/nk) that
CN CN + CNa 3.F S c12 min {1, M, 3nnn Inn log(nsk))
where 012 is positive constant.
Proof. Let Wn E (x- the weighted feature matrix which includes all of the 2 favored features aside from a, We can then define A-R - A WRWR R and H W R A R
Wn.
Using Woodbury, an analogous computation to Lemma B.2 implies that
WRA-1 Ay = (1,-2 W
(102)
The contamination from all of the - 2 favored features that are not or 8 satisfies
CN2 3, CN2 CN AF T A
Σ
w A A Ay
jElsiMa,Bt
>> T A WR W A A
= =A A W 2 HR)- A
Since Proposition B.6 implies that (1,-2222 HR) S C10 min {u²,1) 11 with extremely high probability where 6io is a positive constant, we know the contamination with extremely high probability upper bounded by the following quadratic form:
e10 min (n² 11 A WRWW A Ay
(103)
c10 min (u², 1
Σ
Ah)
(104)
Ma
We still cannot apply Hanson -rriht,,, because A_ 1 is not independent of Ay. However, we can use Woodbury again take out Za, Z, from A-]
R
Define Wa.9 = [w, W and H (s) 0.3
W a. A W a,s. Then Woodbury implies that
A R
A=1 A & [22 + H (t)
0.
WT A_1
0r,
(105)
Hence
2,
= A 2/ A A 0. (I2 H
a.
W A.
(106)
We will use Hanson- Hanson-Wright and Cauchy- Sauchy-Schwarz to argue that the second term in Eq. (106) above will be dominated by the first term. Indeed, Corollary C.3 implies that 2, A Ay S cGn - dominated by - We will show that its contribution for each j is min {1, (1, - By Cauchy- -chhwar, the magnitude of the second term of Eq. (106) is at most
with probability at least 1 100 so it suffices to show that the other term
[1 + Ha.e) -1 a A
WT A.
(107)
a..9
S ei AF min {u, 1) 1 -p log(nsk) n 1-t-p Vlog
(108)
S cn min 1 |n - log(nsk)).
(109)
where C11 is a positive constant. In the second line, we have used Proposition B.6 to upper bound
(I2 H -11 S Ommin {u, 1}) and we have used Theorem B. and Proposition B.4 deduce that that |z] A= < O(n /lg with probability at least O(1/nsk). Similarly, used the scaling from Corollary C.3 to deduce that I A A & O(n)-(-P) Vlog ki and similarly for B.
30

---

Hence 2, AA is O(n Onn'5'~p -P)) (og(nss) with probability - O(1/nsk). By union bounding over j and plugging our upper bound back into Eq. (104), we conclude that with probability least 1 - 1-O(1/nk)
CN
0.8.L + CN F. S C10 min {u² 1
log(nsk)
(110)
= min {1² 1
(111)
S S min { [1, Jn 1 log(nsk),
(112)
where 012 is positive constant, concluding the proof.
E.2 Lower bounding the contamination from label-defiinng-favrred features
In this section, we upper bound the contamination coming from the 2 favored features which are or 3. This culminates in the following lemma.
Lemma E.2. In the same setting Proposition 4.3, if > O with probability at least ((1 D(1/nk), we have
CN² 8.L.L +
CN2 CNa
a. 2 ei min {1, 10,222nn""" Jn-
where 014 is positive constant.
Proof. Following the beginning of the proof of Lemma E. and what we know about the flatness of the spectra of hat matrices from Proposition B.6, deduce that there is some positive constant C13 such that with extremely high probability
CN² 3.1. + CN2 a, 2 C13 min {u²,1}23 1}27
Σ
(3)
(113)
fE(+))fa.8)
We will further lower bound this by throwing out all label-defining j. other words, the goal now is to lower bound
Σ (z), A SE(A|\A)
(Z A
2
(114)
The main idea is to use Bernstein's inequality, but unfortunately A is not independent of Ay, so we will again resort to Woodbury to take out 2, and z3.- As in the proof for upper bounding the favored contamination, we have Wa.s [w,, Wa] and H 0. W a A-W Wa,8. Then we can deduce from another application of Woodbury that
A A Ay 2.J A 2/ A Wo. (22 + Ha,p)
TWT 0. A.
(115)
Again, we can argue that with probability O11/nsk), the second term is upper bounded in magnitude by
min {1, Jn Ploggnnn = min 70 P. ==),
(116)
where Kg is positive constant because > 0. Since Hanson-Wright (Corollary C.3) implies that
zJ A Ay Ö(n / -p)) this implies that 2. A n Ay Ö(n + -P, and similarly for B. Hence we have
(2] Any) (z] T=]_=:Ar + min [1, 10 -
(117)
(2] A- A( =(2/ Ay)) min (1
Ay)² min 11, (1, 0000
(118)
(119)
We are now in a position to analyze the contribution from the first term Eq. (119) to Eq. (114): its contribution is (Z A A_! Ay, 2J. A_ Ayy. This does have all the independence required to apply Bernstein, because (A_) Ay) are independent of Z Hence conditioned on A-} and Ay. ( ! A.A Ay) is sum of k subexponential variables, and by Lemma 2.7.7 of Vershynin (2018) each of these random variables conditionally has subexponential norm at most
A= Ay ? and conditional mean (A Ag, A Av).
31

---

We can use Hanson- Wright (Theorem 4.1) to bound both of these quantities. Indeed, it implies that with probability at least O1/nnk),
A 2 A - 0(n'' (t-2p
(120)
Let us now compute the Hanson- Hanson-Wright bound for (A Ay. A Av). Note that A - is indepen-
dent of Ay, so can condition A A_ and conclude that with probability least O(1 /21k)))
A
2 El
v A Av) A 0(n - A log(nk)
(121)
= TT A
O(n - A= log(nk)
(122)
TT (n ' || loggnkk),
(123)
where we have used the fact that Ay mean zero and A Ber( it)
From Proposition B.4, we obtain the scaling for Tr Tr(A and || -Aحي
This implies that with
probability least 1 - (1//kk)
A Ay. A 2 1nnn-tt2ppp - O(n 00n=='--- -p)) " Iog(nk)
(124)
2 (0(m!-122))
(125)
as < 1.
Bernstein and the union bound implies that with probability at least O(1/nk).
a(n ((1)-
-O(n3 (11--1-(-20)
(126)
jELNNA 2 Q2 (n 21)
(127)
0.
To wrap up, we will need to upper bound the contribution of the error term in Eq. (119). Its contribution
from summing over j E [s] [A] is min {1, (1,,=220 (o==))((n*n-11=->00 Bernstein term, which as we just proved is (2(=+11))-2p) Hence ( (Z A- A Ay. Z A> > that
which is negligible compared to the
(11=t1t(2 with high probability, and inserting this back into our lower bound Eq. (113), we see
CN a.S.L + CN2,
C13 min {n², 1 1322
(128)
= 013 min {u² 1)
(129)
2 2a min f1 --1-1
(130)
where C11 is positive constant.
E.3 Bounding the unfavored contamination
Finally, we wrap up the section by proving matching upper and lower bounds for the unfavored contamination CNa,9.U-
Lemma E.3 (Bounding unfavored contamination). In the same setting as Proposition 4.3, ift > with probability 1 O(L/nk), the contamination from the unfavored features satisfies
CN.. = o
where Cis is positive constant.
On the other hand, ift O, then with probability 1 1-0((/nnk)) the unfavored contamination satisfies
CN2 5 eie min (1,x= Ind 1- log(nsk).
32

---

Proof. By Woodbury, we have
A = Aü' Au M,A
(131)
where
M, a WI, HHH
(132)
and H & W A
Now we have
CN 0,B
Ay A A AAA Ay
(133)
Ay (AT - (2 - A A )
(134)
Av (AT -22 M, A + Av A,,A, MM,Ay'M,AAJ' A Av.
(135)
By Theorem 4.1, we have with probability at least O(1/nk)
Ay Ay= = o(1))
(136)
where C15 is positive constant. On the other hand, we have that
A,A M. = W.(I,+
+ +H.) W
W.(,, H.) H.) W
W.(1, + -H,,)-H,(,,, + H.,
W. - (1,+ H..+ + H.) WW
W.((I, + HH, -H,---
Due to Proposition B.6, ML((I, + H²) min fp. (1 + o(l)) for all i with very high probability. Hence to handle the error terms that are not Ay Au Ay, it suffices to asymp- totically bound Ay AT M,A, Ay. In turn, can couple this to the quadratic form min {1r 1) (1 + A(1)) AT W, W. A Ay. By Proposition C.4, we have with probability least 1 - ((1nnk)
min 1] Ay T AJ W.W,W
(137)
I A min {e. 1) (1 + o (1)) + n n= log(nsk)
(138)
- c min (1, (1 + of 1 + p)) log(nsk)
(139)
For > 0, we claim that the term in Eq. (139) is '(n'-t-)) because 2t - < 1- p and
t < 1-t -t- p. Hence if t 0 then by union bound have with probability at least
1 - 0(1 (1/kk) that
CN2 CNa = (l)))
(140)
as desired.
On the other hand, if t O, we only have an issue if + r < so that min {1. 1. In this case, the deviation term n 1-2rpp l-t-p, However, this won't affect the fact that the upper bound on contamination will still be ((n)- More precisely, this bound concludes by arguing that
CN² CNa,3,U S cie min (1, Inn log(nsk)),
(141)
where Cie is an appropriately defined positive constant.
It turns out we don't have to worry about this edge case at all for the lower bound on CNa.a.v. because the stated conditions for misclassification imply that >> 0 anyway. This completes the proof of the lemma.
33

---

F
Obtaining tight misclassification rate
In this section, we will prove Proposition A.5. Let restate the main proposition and sketch out its proof more formally.
Proposition A.S (Correlation bound). Assume we are in the bi-level ensemble model (Definiton 1), the true data generating process is 1-sparse (Assumption 1), and the number of classes scales with n. (i.e. t 0). Then for every >> O, we have
)
1 k1+o11
Pr
max (
Z
2 21-0
0
(49)
for sufficiently large n and any u. > 0.
Proof sketch. Note that the 7(0)s that must outcompete the decaying survival to contamination ratio jointly Gaussian, they are projections of standard Gaussian vector Ftest E TR.. Hence if we want to study the probability that max3 (( outcompetes n", we have to understand the correlation structure of the ((9)ss.
We will argue that for Y,7 E [k] with a, 8, y pairwise distinct, the correlation between 2(0) and Z(1) is + o(1) with high probability. To that end, we want to look the correlation (inner product) between the vectors \ (yyha, for j $ {a, and { {>yha,; [5l for j & {a, 7). However, note that by independence of the components of Besst from every other random variable and the fact that they are mean zero, we have
E(h 177.al hi) [t) sor 0.
Hence it suffices to look at the correlation for & fa, 8.7)
We assume WLOG that a = 1, = 2, 3. Let
Na,3 A diag(1 - j-- - 1 j= o diag(A)))e(a E Rdddd
represent the diagonal matrices containing the squared feature weights with indices a, 3 zeroed out. Next, let Va,3 E Rd denote the vector with Va.a(a] = va.el3] [8] = 0 and Va.elil = Xyh [i] for j E [d].j & {a, B3.. Hence va,3 = A 1/2 the correlations between 2 and Z(h), it suffices to analyze u,,g- Indeed, we will show that the weighted halfspaces A 2 E Rd and A E Rd are asymptotically orthogonal.
fa). Since Z(0) (Ma,3, Ttes)), in order to analyze
In other words, need show that
A1 2, cs a.
1/2
o(1)
1/2-
1/2 a.8
with probability at least 1 - O (1//k)); most technically involved part of the proof, and the content of Proposition F.I.
then union bound against all choices of B3. This is the
This in turn will imply (see Lemma F.2) that the maximum (and minimum) correlation between the Va. for different / is + o(1) Let (Zz) be equicorrelated gaussians with correlation p= _ (1). and (Ek))e be equicorrelated gaussians with correlation 1 o(1). By
Slepian's 's lemma, for any u >> O, the probability of max 7(3) losing to n a sandwiched as
Pr max 2. < < Pr max (9)
< n
< Pr max 3g n
where we have adopted the shorthand maxş to denote max
Theorem 2.1 of Pinasco et al. (2021) shows that that jointly gaussian vectors R with equicorrelation lie the positive orthant with probability @(k2-1/P)) In particular, applied to Zg with correlation
p = + o(1), we find that
Pr
max 7, s 0 = O(k 10(--1-(11)
8
34

---

Combining Proposition F.1 with Lemma F.2 yields the following formal statement about the correla- tions between the (8)) and similarly for g- Anticoncentration for Gaussian maxima (Chernozhukov et al., 2015, Corollary 1) implies that we can transfer over the bound Pr maxx Zo S 0| bound on Pr mmxx gg I n "] to show that for every e > O, we have
0(k-1-01))
Pr max Z
(O(-lto()) +e
(142)
for sufficiently large n. Taking the complement of the above event concludes the proof.
F1 Main results for tight misclassification rates
The main result in this section is the following proposition, which states that the halfspace predictions are asymptotically orthogonal. Its proof deferred to the subsequent sections.
Proposition F.1. Assume we are in the bi-level ensemble model (Definition 1), the true data generating process is -spaass (Assumption 1), and the number of classes scales with n (i.e. >> 0).
For any distinct a, B E [ki], with probability least O(1/nk), we have
A 1/2 a. ar
A
1/2 a.
o(1)
A 1/2
1/2
a.
0,,
2
Given Proposition F.I, show that the Z(S) have correlations that approach 1. The intuitive reason that this correleation approaches & is that the contribution from is common. The following lemma formalizes this intuition.
Lemma F22 (Correlation of relative differences almost orthogonal vectors). Suppose that we have unit vectors .1..... I, E IRd such that (x,, 2zy) I y for y > 0. Then any distinct i, j.k k [n]] we have
(x) 2., xx.)
1
2
| x; a3 xx
2
Proof. For any + j. we have | 2. 1| = 2 (xi,, ..)). Hence we have
2 27 S |r x. 1| 2 2
Also
2 2-27 5 |2 xx|l
= |2 11 + [ - Z4 2 - (xz
2; x2 σk
< 4 4r 2 (a. T; 3; Tk)
Since ||x; - x.5l 2 22 - 27, we can rearrange and obtain that
(x) 24 x2 23)
1 37
x 36
2 27
Similarly we can reverse the inequalities and get
2 + 2y 2 4 - 4y 2 2
Dis I, Ek)
(x) 2₁, 32 xxa)
1- 37
|0; - x. xt; 33
2 + 27
35

---

Lemma F.3 (Asymptotic correlation of relative survivals). For any distinct a. 3.3. E [k], under the same assumptions as Proposition F.I, as n - co, with probability least (1/nn, we have
E ( (
S o(1)
As consequence, the asymptolic correlation between the relative survivals approaches 1/2 polynomial rate.
Proof. Plugging in the result of Proposition F.1 into Lemma F.2, obtain the stated result.
F.2
Lower bounding the denominator
Let us now begin to prove Proposition F.1. The first step is to bound the denominator of the normalized correlation. Writing out the definitions, we have
11.35 1|=
Σ
Xly, A
Zzzz
A A Ya
jæ (0.8)
x
Ya A- 2 A Ya + X Σ Yn A y j>8
JE(
Note that these terms are respectively analogous CN a.3.L + CN2 a. and CN² a.9.0- In fact, the proofs of the lower bounds for contamination essentially transfer over verbatim to the lower bounds on the denominator, because Hanson- Hanson-Wright implies that we can show that || concentrates the same way that | Atyl2 does. In essence,
able show the following proposition.
Proposition F44 (Lower bound norm of scaled halfspaces). Under the same assumptions as Proposition F.I, for any a, 3 E [k). with a + 3, with probability at least 1 - O(1/nk), we have
0. Po
2 min -0
F.3 Upper bounding the numerator: the unnormalized correlation
We now turn to the more involved part of the bound: proving an upper bound on the numerator. As before, we can bound the split up the numerator into favored and unfavored terms, For each term, we will show that it is dominated by the denominator, in the precise sense that each term
o(min {1. 31_=p"3n"""-
Inn n
Now, let's look at the numerator, which is the bilinear form
A2.
Σ
Ya A
2 A A- ys +
X
Σ ya
A
A
232 A A
(143)
j>8
2
Z
A
ya.
2 A Uイ
X
7 A
yo
2J
A
X Σ ya A
A
A-1 ys
528
cot..0.2
000,,
cDr,.0.0
(144)
We refer to the the first term as the label defining correlation cora, L. the second term as the favored correlation co and the last term as the unfavored correlation cor,, Here, abuse terminology slightly and refer to these inner products as correlations, even though strictly speaking, they are unnormalized.
E.3.1 Bounding the favored correlation
We now bound the correlation coming from the favored features; will ultimately show that its contribution is min
Recall that WR e (=x((-2) is the weighted feature matrix
36

---

for the s 2 favored features aside from and 3. Then the label cor,, a,, can be written succinctly as ya. A.. A
correlation
(145)
Why should we be able to bound this better than Cauchy-Schwarc Intuitively, although there is mild dependence between Ye and yas it is not strong enough cause Z A A'yya Ya and 2 A - ys to
point in the same direction.
To formalize this argument, will first follow the strategy to bound the favored contamination. In particular, using the push-through form of Woodbury (Lemma B.2) we see that
yo. Z A yy)) yo A 2 + HR) 2Z A n98 h
(146)
Now, we can apply Proposition B.6 to replace (I,-2 + H with min (1²,1} (Is-2 + E), where [ = On xx1) with extremely high probability. Cauchy-Schward yields that
k A Yn: A A 'y3))
(147)
S min (,²,1} (Z A Ry A
Ry0) A
(148)
+ min {1², || R ARAA n 12 Z A 1- A-
(149)
The term in Eq. (149) can be bounded in the same way that we bounded the favored contamina- tion. Indeed, since we can swap in yo and ys with Ay. the argument that proved the bounds on A 2 port over immediately. After using the scaling for Ay and the fact that || = (k1), ), we conclude that this Cauchy-Schwarz error term is most min { 11, with probability at least O(1nkk).
{ Jo(n"-(-1)
Let us now turn to the term in Eq. (148). As the proof for the lower bound for favored contamination Lemma E.2, to get better concentration than Cauchy-Schwarz, we want to use Bernstein. We can rewrite it suggestively as
Σ (z) A (E.8)
(150)
We cannot immediately power through with the calculation, because A R is not independent of yo ys- The main idea is again use Woodbury and show that the dependent portions contribute negligibly 2, A k-a Therefore the dependent contributions get dominated by the lower bound on the correlation.
Ws] As in the proof for bounding the favored contamination, we can further define Wa, [wo and (())) 3
a.3 A_ W., W. Then we can deduce from another application of Woodbury that WT
=, AA R =/ A_yy. =J A a, (I2 + Ho..) WT 0. A-yy.. Again, we can argue that the second term is bounded in magnitude by
(151)
min (1, 'nn -tp
1e2-t-Plog(an log(ns) min "0(n 1-t - pnu))
(152)
because > 0. Since Hanson Wright Hanion-Wright (Corollary C.3) implies that 2. A = Ö this
implies that x, -2 0 - -D), and similarly for B. Hence we have
(z] A 1 v. ) (z A hhys)
(153)
(z, A A ya + min (1, -n A
min (1, 10n't'
(154)
< [z) A ya (z}] A : us) + min 10 - xz
(155)
< (z] A (x)) A !
yy) + min (1, Jo(n (0-2))
(156)
This implies that we can rewrite Eq. (150) as
Σ
(xJAAlya) Aby0)) + min (1, "o(nntt----
(157)
HEld)
37

---

Let us argue that the second term in Eq. (157) will be negligible compared to the denominator, which min 2__===]((n""=-11 Tracing back up the stack, we see that its contribution the favored correlation will be at most
XB. min {a² 11 min {1, p 1o 20) s م min {u² u,,, a- (o(n"-(-1)
(158)
I min ( [1, jo(n
(159)
x min (1, J0(nn
(160)
Turning back to first term, we are now in a position to apply Bernstein. Note that (A_ ya Us) are independent of RR. Hence conditioned on A Yo. and yo. ( [Z A Bee, Z A is sum of subexponential variables, and by Lemma 2.7.7 of Vershynin (2018) each of these random variables conditionally has subexponential norm at most A ya
A ye and conditional
mean 1/ A A _33)
We can use Hanson Wright (Theorem 4.1) to bound both of these quantities. Indeed, it implies that with probability at least O(//nk),
Hannghn-Wright
|| || ya ||2|| A - (tn--t-2p)
(161)
Let us now compute the Hanson- Hanson-Wright bound for (A of Yo and ys so we can condition on A_ and conclude that with probability at least 1 O(1/nk)
ya. A_ A_,ys) ys) Note that A=! is independent
y ys)) < E(AAA. ya. A y A con ||A 2 2 log(nk).
(162)
We can rewrite the expectation as
Tr(A,"Elysu.)
(163)
Clearly, Ely diagonal, and each diagonal entry is equal to Let p k. implies y/ -p and vice versa, we get
1.
Then since yo 1 1 p
yo [y [i]l 2(1 p)(-p) Priya 1i] = 11 pl Pr[ya[d yoli pl s -p - p) + p² Pr(yali-= = -
(164)
(165)
$ -p- p).
(166)
In other words, the expectation is negative, so we can neglect it in our upper bound.
On the other hand, the deviation term with very high probability at most
Cgn
1-f A
log(nk) S cgn 1-1 -2p
aoy/oggle vlo((nk).
(167)
Combining all of our bounds, Bernstein yields
( A <
2y can 1 -2 1el--//oooe Vlog(nk)
(168)
HE
S n r+ 1 2p Vlo(nnk) + n -
(169)
Again, let's trace all the way back to Eq. (148) and then the favored correlation bound. We have shown that [T] A A 2 A A yys)'s contribution to the favored correlation is at most
C17\3 min (1²: 1 (n L -p-22 Vlog(nk) n -nž-++1 -241-2p)
(170)
cia min {ui² 1} (n- 41 -1 Vlo(nnk) -
(171)
c17 min (1, / 2) (n --1--11:: 14 / Tog(nk) + -1-1
(172)
Snn min (1. μ )
(173)
where the last line follows becuase 0 < t < and C17 is positive constant.
38

---

F.3.2 Bounding the unfavored correlation
Now, let us show that the unfavored correlation s,,, is negligible; more precisely, we'll show that it's min (1, 3u-23oo J((nn=n(== + onn'nnnnnn (t)) We can rewrite cor 3,,,, as
yu A- ys:
and play the same game with using Woodbury replace A- with A- - AT M, where recall that
M. - W. H.) W. E R
This yields
Ya A y3 2y A M, M,AU ys + ya A M,AJ M,Aj'us us.
(174)
Let us first focus on the first term of Eq. (174). Mrnson-Wriigh implies that with probability at least 1 - O(1/n),
y Au ys
Ely. A ye 4 ~
Vlogn.
(175)
Also, Ely, Au ys A
Onn'~2t- with high probability, and | 2 1 n with extremely high probability. Hence we see that yo A y S O(n - -
T Elv.y..l)
o(n (nn as O.
Next, let's turn to the second and third terms of Eq. (174). We claim that only the second term will be relevant to bound asymptotically, and moreover that they are both min {1, 1 -2 )o(n"((=)) Since
M,AT'M, W. + HHH H. + H.)
W. +
H,) H.) (I, + H.) ")
the second and third term can be rewritten as
2y T A W. H W A ys
+ AT W. W.( H.) - (I, + H.) - Ai ys.
As going to use Hanson- Hanson-Wright Wright bound the entries of Z A Ya it follows that only the second term of Eq. (174) is relevant asymptotically.
To bound the second term, we will use Cauchy-Schwarc We see that
y. AJ M.AT' ys & Ap + H.) Z__ Aij yallz
2, AJ 1oll
(176)
- Ar min {v+ (n ++1 2p) log(ns)
(177)
$ - min {M, 1)0(n==1-) log(ns)
(178)
I min (1, P) log(ns),
(179)
where in the second line we have used Proposition B.6.
Now, note that if regression works, this yields upper bound of O(n"-t-P) log(ns). But since
> 1, this is o(n"-(1), ) which means this contribution is dominated by the denominator.
On the other hand, if regression fails, then the upper bound is now -0=00nn log(ns), which we claim on--2n" -(- Indeed, from the definition of the bi-level ensemble Definition we have p > 9 +
min {1, -n--t-p < -- .n
/ 10nn---11 1-1--12---1 -----r) μ 2
as desired.
Let us now go back to Eq. (174) and combine our two bounds. Since Ao = O1), we have just shown that
cor A,U I min {1, 111,p~21orr 20((n"+t11 + t(pp-)-))
(180)
as desired,
39

---

G A new variant of the Hanson-Wright inequality with soft sparsity
In this section, prove Theorem 4.1. First, we outline high level idea of the proof. The starting point of the proof is to explicitly decompose the quadratic form into diagonal and off-diagonal terms
x My E|æ² My)
Σ
may X.Y, Σ mc.E(x.Y.
(181)
f
mis mX(XY B[X,) + Σ
Σ i
mig XiX
(182)
Suftaii
where in the first line we have used the fact that for i J. X2 and Y are independent and mean to conclude that IE| X;Y, Yj = 0.
We can start with the upper tail inequality P(x T My Eix Tyy and conclude the lower tail inequality by replacing M with -M. To bound Sdiag and Softding, we will proceed by explicitly bounding the MGF and applying Chernoff's inequality.
G.1 Diagonal terms
For the diagonal terms, we want to bound the MGF of Sding = E. C.mss.VV E[X,Y.)). For
X² < 20, K2 max, m3." we obtain
Eexp(ASdiag)
Ex,. exp(Amus(XXY) E(XY)))
(183)
By Ex, XXX, EXX,IX
(184)
I Ey, exp K i=1
(185)
where have applied Jensen's inequality in the second line and the subgaussian assumption X; conditioned on Y; in the last line. Here, C₁ is a universal positive constant relating the equivalent formulations of subgaussianity Vershynin (2018). Continuing with our calculation, have
E Exxp(ASdiag)
II
Ey, [1 2C
(186)
1=1
s II (1 2C TT 222
(187)
1m1
1
$ Sexp 20 22
Σ
m
(188)
1=1
where in the first line we have used the inequality exp(x) 1 + 2x valid for S J. in the second line we have used the soft sparsity assumption on Y, and in the last line we have used the inequality I + & exp(x), valid for all s.
Now Markov's 's inequality yields for e that
E Eexp(ASaing) exp(Ae)
PriSalag > cl
(189)
S exp
- de + 2T
Σ m
(190)
and optimizing À in the region X <
2C1 K2 max; mi! yields
A min
(191)
22, En m 20, K max; mm
40

---

Plugging in this value of X into the Markov calculation yields the desired upper tail bound. We can repeat the argument with M to get the lower tail bound. A union bound completes the proof.
G.2 Offdiagonal terms
Following Rudelson and Vershynin (2013), for the offdiagonal terms we can decouple the terms the More precisely, the terms in Sofdding involving indices i and j are precisely m,y.X,Y, m +m; Y, The issue is that Y, can be correlated with X,, which complicates the behavior of this random variable. Decoupling ensures that for any E [n]] will have exactly one which involves either X, or Y, so in particular we will regain independence of the terms, allowing us to bound the MGF more easily.
Let (er) denote iid Bernoulli's with parameter 1/2, which are independent of all other random variables.
Let
S8 -
Σ miyd((1 (
Since B[,,(1 -5,] = we have
Sotding = 4Es[S5]]
Hence, Jensen's 's inequality yields
Exy exp exp(ASoddaa)) S E exp(4)Ss).
where we have used the independence of and all other random variables. It follows that it suffices to upper bound the MGF of Ss.
Define the random set As e [n] 8, 1} to denote the indices selected by 6. For vector u E IR" we also introduce the shorthand UAS to denote the subvector of u where 6; = and uxg to denote the subvector of where 6; 0.
Hence, we can rewrite Sb A EiEASHJESS my M,Y, For [V] S 20,K||M,3 we have
E Exxx(ASSftding
I Eexp(4A58)
(192)
$ Es
II
Exr, May (exp(Am,,XxXI,)
(193)
XEAgJEAA
Now we can use the fact that the X; and Y, are mean zero and independent because i E As and j E Ag. show that
II
Ema, Uag X,3,) <
II (xngloxp(C>>>3>n
(194)
I KEASJEAS
iEΛs.JENG
II SEA,JEAA
Eggg +12G m 1?2
(195)
II *EΛrJEAA
(1 22
(196)
<
II exp (2 C222
(197)
iEAS.JAAS
S <exp(2 (2P22GGAK221111
(198)
In the first line, we have used the subgaussianity of X;; in the second line, we have used the assumption X, in the third line, we have used the variance bound Yj.
Again, we can apply Markov's 's inequality and to see that for e > 0,
Pr(Saing > c) S Eexp(ASeing)
(199)
exp(Ac)
exp ->e 1 +2CCK332(1111)
(200)
41

---

Picking
1
A min
(201)
20 |0|K2
2 201 K| M
yields the desired result.
H Proofs of main lemmas for concentration of spectrum
The goal of this section is ultimately to prove Proposition B.6, which asserts that for valid (T, S), the hat matrix Hr.s is flat matrix whose spectrum is min {μ, 1] (1 o(1) with extremely high probability. First, let us recall some notation. For any Ø + T C [s], we can define the (T, S) hat matrix Hr.s & W A_ Wr. Here, WT is the [T] matrix of weighted features in I, and A-T A Wr WTI is the leave-T-out Gram matrix.
First, Wishart concentration applied to W WT yields the following result. Lemma H.1. Recall that μ f n and W WT E T| For any nonempty T S [s). with probability at least 2e- vn we have that for all E [[T]]
(W WT) = + . (T) n p='n"
(202)
Proof. We can apply Lemma B.3 with M Zr E Rex with M =n, m. [T] o(n), and = nd o( V TT). Hence have
n - T| olv [T) & M1T1 Z ZT) S (7 ZT) Sn
+((v
Pluagging in the scaling A5 = nー .- and dividing through by n yields the desired result. Here, we define er be appropriately defined positive constant which only depends [T] (as the favored features are identically distributed).
Next, we can use Wishart concentration bound the spectrum of Au-
Lemma H.2 (Concentration of spectrum for unfavored Gram matrix). Throughout this theo- rem, assume are in the bi-level model (Definition 1). Define μ - notr-1 Recull Au =
AU Ej>e 2,2] E Raxx, With probability at least 2e for" E [n]] we have
pa (Au)) = +1 +1 cign"?)n"
(203)
where 0ig and Bi are positive constants. other words, the spectrum of the unfavored Gram matrix Au is flat.
Proof. Note that AG du E 2z²,. Under the bi-level model, d =1+ o(1. Now we can apply Lemma B.3 with M Ej>s 2,2 M d nd n", o(d), and /2n to conclude that with probability at least
2e -e_", we have
d - 2v + 2n S pal Σ
マイ 11
Σ 5 2v dn + V2n. (204)
f>8
We obtain the spectrum of Ar by multiplying through by
(1 a1d
Au
(205)
d -
+ n max [-qrr-p + max
max (-qr-p)),
(206)
where in the last line we have used the power series expansion for --E = =1 o(x). Preserving only first order terms for d and the spectrum of Σソ>0プコz] in Eq, (204) yields
(Av)) + cian max ('=",r-p-- yn
(207)
42

---

In fact, we know 1-p > 1-p > p- p, since r < 1 and > 1. This means we can neglect the r
term in the max, define K7 min { { 9} and Cis to be appropriately defined positive constant.
[s],2" we can apply Lemmas H.1 and H.2 to control the spectrum of A We show that there a (potentially) spiked portion of the spectrum corresponding to the taken out, whereas the rest of the
Since AT Au + W M Wii
[T' favored features which are flat.
[7' eigenvalues
Lemma H.3. Recall that A-T E R For any nonempty C
[s]. with probability at least
1 2e vn 2e we have that for all i E [s |
TI (((AT) = (1 + er
n² + (1 + Cisn (18n~M1)nt ) n="n"
(208)
For all i i [n] {ss [T]], we have
Mi(A cish
cisc c n..
(209)
Proof. We can write
A-r WAJ W [+]VT Av.
(210)
Weyl's incquality (Horn and Johnson, 2012, Corollary 4.3.15) implics that for any E [rx]. we have
p4 W [JVT W ( (Ar) S p=(A- S 14 (W (eVTT W (+)T)) + ( (Av).
(211)
Then applying Lemmas H.l and H.2, for E [s - [T]] we conclude that
p((Ar) = 1 cr
1 n2 + (1 + C1sh -
(212)
which proves Eq. (208).
For i > [T), applying Lemma H.2 and the fact that #4 (W 11)T W W (ijz)) = 0 to Eq. (211) yields
(A(Tr) = (1 + Cisn N7) "7)n".
(213)
which proves Eq. (209).
L
By inverting the bounds proved above, we can also control the spectrum of A= Corollary H.4. Recall that A-T E guxn For any nonempty T S [s]. with probability at least
1 Vn 2e-", we have that for all E (n - 8 + ITI),
Mi A 7) (1 + Cign "7 "n)n"
(214)
For all i [n] [m 8 + [T]], we have
Ma (x(A min (μ. 1) (1 + cann "Ma)n
(215)
where Ki is a positive constant depending on (T].
Proof. By inverting the bounds in Lemma H.3, using the fact that μ4 (A(A))) that for i In + [T]]
An-isi(A_7))
we see
M1 (A-1)
=
+ Cignt-r P
(216)
= =(1 C1971 -N7 ) n
(217)
where we have used the power series expansion i-r
+ + o(x²)
and C19 is positive constant.
43

---

On the other hand, fori> n - + [T],
we get
1
(A(A
n n
(218)
1 CTV p-
[
c181
= -min (u. 1) + c20' "
(219)
where C20 and Ky are positive constants defined as follows.
If q + r < i.e. regression works, T + p(1 c1sn (1)) Then, since 1 1 CT
then μ (11., the denominator becomes μ
[T| < n²,, that pick
1 1- 1-1
Kg min
On the other hand, if i.e. regression fails, then pr م o(1), and define
min {N7, -
Hence to cover both cases we can pick
Kg min
1 --
K7,
rl
The choice of C20 is picked by again using the power series expansion for
1 T-z'
Note that Corollary H.4 immediately implies Proposition B.4, with Kg defined based on picking in position prove that the generalized hat matrices Hr,s, and hence the Woodbury terms [ + Hy have flat spectrum well.
T = [k). We
Proposition B.6 (Generalized hat matrices are flat). Assume we are in the bi-level ensemble Defini- tion I. For any nonempty T C S - [s). with probability at least 1 - 2e-Va /v eigenvalues tightly controlled:
2e we have all the
Pe((TTT =r)s))")= min 11,1) (1 + er,sn R11).
(75)
where cr, and 8i1 are positive constants that depend on [T] and (S].
Proof. We seek to control the spectrum the hat matrix HT,s WTJ. A Wr. We cannot directly use naive eigenvalue bounds to bound the minimum and maximum eigenvalue, as this does not rule out the possibility that Hr.s has a spike. Instead, we control the spectrum from first principles.
s is symmetric, it has an cigendecomposition VDVT where V is orthogonal matrix. Because Wy, is weighted subset of only the (equally) favored features, its law is rotationally invariant. Furthermore, since A= is independent of WT (as T S S), can absorb the rotation V into WT reduce to the case where A D. Here, have
The spectrum of Hr,s flat: Since A_1
(1(AA
Ditat
D
E RRn
(220)
D Dspiked
Pn (A
where Diat [(n=s+(7))x(x----11 and Depiked (g(e-IT)x(s-111 correspond to the flat and (downwards) spiked portions of the spectrum of can also correspondingly decompose
B Cr
ZT
(221)
where By E (T==0+17)xIII and Cr E R(+-I21)xITI, Note that each entry of these matrices are iid. (0, 1) variables.
44

---

By direct computation we have
Z DZT Dra By CT Depiked Cr
(222)
We thus have by using standard eigenvalue inequalities that
4m DZr) 2 Mr (B, Dra:Br) + Hyr (C7 D spiked CT)
(223)
2 M| B Br Br) ( (4_5) + MTT (C7 (r)
(224)
MMr] [ BT 1 (A A
(225)
where in the last line we have used μnn [A N O.
Since > 8, we have 7 + [7|| [T] so we can apply Wishart concentration (Lemma B.3) to B,J Br to obtain that with probability at least 1 - 2e- v we have
Mirl B Br)
2 n - |T| - 2 (n 1 [2D + ol (n + [
(226)
2 12(1-n"-1 1
021 IT)
(227)
where 021 is positive constant.
On the other hand, we can deduce that
N1 (z, DZr) S (1 ZT) (A (ACs).
(228)
Lemma H.1 implies that with probability at least 2c VR
pn (Z) ZT) n(1 CT
(229)
Similarly, Corollary H.4 implies that with probability at least 2e 2e ~e- i (A and Mn-s+177 (A are both (1 + c2om ) P. Since [T] < s = n², Eqs. (227) and (229) together demonstrate that for all i E [[Z']]
(4 - n DZ)
+ C22n M10). "100
(230)
Here, 622 and K10 are positive constants defined as follows. Since [7' < n". Then K10 min {1 - r, 1=r (88) and 622 is constant chosen appropriately based C20 and c21- Plugging in the scaling Ay p-- conclude that with extremely high probability, for all i [[T].
#4 (T,,s)) = μ (1 + 022m (10).
(231)
From here, it is easy to compute the spectrum of (T/ + HT,s) Indeed, reading off our result from Eq. (231) yields
1
pa((T + HT.s)
(232)
1+ Pn-it1 HT)
min {u, 1) (1 + cr,sn=
(233)
Here, the positive constant CT,s is picked appropriately and K11 min (K10, - -1-11----0 - 0. This completes the proof.
I Miscellaneous lemmas
Lemma L.1 (Coupling of quadratic forms). Let B E RRxx be an arbitrary real matrix and M Raxx be PSD matrix. Then for any vector x E R.m we have
(M T B Bæ < x T B MB S (M) B Bx.
(234)
Proof. For any PSD matrix C. the matrix B CB is PSD. In particular, C has a unique square root C122 Rax with 1/2 (C1/2)T 1/2 C. We thus have
CBC x 1 Bx
(235)
C1/2 Ba 2 0.
(236)
45

---

Hence
A1 (M) "B Bæ BB MBr x B (N) M) Ba Since M 3 I,, by definition, (1 - -M is PSD matrix. Hence by applying Eq. (236), conclude that
(237)
(M)) J
B Bx - x T MB 20,
(238)
which gives the upper bound in Eq. (234). Similarly, M 2 An (M)
analogous argument
An (M) B Bæ - x''BB'' MB S0,
(239)
which gives the lower bound in Eq. (234).
Next, we prove the elementary anti- anti-concentration result that we will need.
Proposition 1.2 (Gaussian anticoncentration). Let x (O, Ia) be a standard Gaussian vector, and let Rdd be arbitrary deterministic vector. Then
2
Pr[l(x, u\ s
/ u|12
Proof. Note that (z. v) is a linear projection of a standard multivariate Gaussian, so it is itself one-dimensional Gaussian. It also clearly zero mean, and its variance is just give by the squared norm of v. So v) (0, [|ol2)) Now have
1
x²
2E
Pr|K w) S =
exp
dr <
V 2
|
v
2T
Comparison to the straightforward non-interpolative scheme
In this section, we quickly give calculations for how well straightforward non-interpolating scheme for learning classifiers can work asymptotically. However, a similar analysis using the tools developed to prove our main results should give rigorous proof of the below derivation.
This scheme simply uses the sum/average of all positive training examples of class as the vector take an inner-product with to generate scores for classifying test points. For m E [k]. define
fm Σ
x
(240)
To understand how well this will do asymptotically, is easy to see that the for the true label- defining direction, the positive exemplars in the bi-level model will be tightly concentrating around 2/ log k AF which, keeping only the polynomial-order scaling, will be like -- There will be roughly n positive examples for every class with high probability. For simplicity, let just
look at m = 1 and consider à fi n² 1-1 fi. We see
n2
n' t- [[] O(n !
(241)
For the other directions that are not true-label defining, we will just have random Gaussians. The favored directions will be Gaussian with variance Äp n while the unfavored directions will essentially be Gaussian with unit variance. By averaging over 1-f examples, those variances will be reduced by that factor. This means that for the n" favored directions, the variance of the average will be nd- g-r--(1)))) each and for the essentially np unfavored directions, the variance of the average will be f each.
test point, we are going to take the inner product of ff with an independent random draw of " For classification to succeed, need this inner product to be dominated by the true
46

---

m-th feature-definigg direction. When that happens, the correct label will win the comparison. One can easily see that the contribution from the true feature-defining direction will be Gaussian with mean O and variance Ap (n -2
X n 22p-2n-22 2r Meanwhile, the favored features will have their scaled variances sum up in the score to give total variance of n" Ap np-g-r-(1-1) 222-24----1-2 And finally, the unfavored features will also have their variances sum up in the score give total variance of n? 1 n -
For the trueffeature-definng direction to dominate the contamination from other favored directions, we need
2p 2q 2r > 2p - 2q - -
(242)
which immediately gives the condition --
For the true-feature-denee direction to dominate the contamination from other unfavored directions, we need
2p- 2q - 2r > p
(243)
which gives the condition f < x 1 2(g r..
Here, there is difference between regimes in which regression works does not work. The condition for classification to asymptotically succeed is / < min(1 -r r, + 2(1 + r)).
Notice that when MNI regression does not work q 1, this is identical to the tight characterization given for MNI classification in (13). But in the regime where MNI regression does work q + r < 1, this is different. For MNI classification, (13) tells us that require < min(1 -r, 1). Consider 0.1, r 0.5 and = 1.1. MNI classification can only allow < 0.1. Meanwhile, the non- of pwwpppovteeaampppeeee the potential for significant suboptimality (in terms of the number of distinct classes that can be learned) of MNI classifiers in this regime of benign overfitting for regression.
interpolating average-of-p
classifier will work as long as < 0.5. This demonstrates
K
Alternative framing of bi-level ensemble
In this section we provide an alternative exposition for the bi-level ensemble, which may be more intuitive for some readers.
The high level conceptual picture of the setup is as follows. The learner simply observes high dimensional jointly Gaussian zero-mean features with unknown covariance Σ E Rdxd It then performs min-norm interpolation of (essentially) one-hot-encoded labels to learn the score functions for the & different classes. These score functions used at test-time do multiclass classification.
Note that the learning algorithm has no knowledge of Σ, nor does it even know that the features are jointly Gaussian - all it has is the training data. For analysis purposes, we parameterize Σ. In the spirit of spiked covariance models, where a low-dimensional subspace has higher variance, we study the case that the cigenvalues of Σ follow the simplified bi-level model parameterized by (p. r.
The bi-level model stipulates that the number of features variance levels for the Gaussian features. The higher variance component resides in a low-dimensional subspace of dimension style results telling us when successful generalization will happen. Here, the number of classes also matters, and that is where the parameter enters.
n² and (ii) there are two discrete
n". For this bi-level model, we are able to prove sharp phase-transition
To simplify notation for analysis in the paper, Subramanian et al. (2022) just assume that Σ is diagonal to begin with, instead of explicitly rotating coordinates to the eigenbasis of a general Σ. Because Gaussianity is preserved under rotations and min- norm interpolation only cares about norms, this transformation without loss of generality. We reiterate that the learner is agnostic to all of these choices and does not know Σ at any point.
47


Reviews:
[{"review_id": "7lqnZc61VG", "reviewer": "Reviewer_BQHA", "summary": "By resolving the conjecture posed by Subramanian et al. (2022), the authors address the asymptotic generalization for overparameterized minimum-norm interpolation (MNI) linear multi-class classifiers under two assumptions: (1) features are Gaussian vectors and labels are generated from $1$-sparse noiseless model; (2) the scaling follows bi-level ensemble. This paper can be seen as a completion to the previous result of Subramanian et al. (2022) since it captures the generalization for both the regime where the regressor fails and regime where it works. The technical contribution appears to be a new variant of the Hanson-Wright inequality.", "questions": "Line 165: \"it suffices for the maximum value of the LHS ......'' Is it the maximum instead of minimum here?", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "A sound completion to the previous theoretical result.\n", "weaknesses": "The setting of bi-level ensemble seems a bit weird to me, especially the eq (12). Maybe the authors can offer more explainations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions.\n\n> The setting of bi-level ensemble seems a bit weird to me, especially the eq (12). Maybe the authors can offer more explainations.\n\n- See the general comment for an overview of the bi-level model. The bi-level model is a set of simplifying assumptions to more general spiked covariance models which distills out a minimal set of assumptions for theoretical tractability while being able to call out interesting phenomena.\n- The choice of the feature weights in eq (12) reflects a relatively natural normalization of the covariance of the feature vector so that $\\mathrm{tr}(\\Sigma) = d = n^p$. For example, this kind of trace would arise if each feature on its own had unit variance but there was some interesting correlation structure among the features. (Of course, we do all our analysis in the underlying rotated eigenbasis coordinates for $\\Sigma$ for notational simplicity.)\n\n> Line 165: \"it suffices for the maximum value of the LHS ......'' Is it the maximum instead of minimum here?\n- This is indeed a typo and we have fixed this in the revised version. \n"}, {"review_id": "8H6nWRc96O", "reviewer": "Reviewer_PSb6", "summary": "In this paper, the authors analyze the generalization of the linear multiclass classifiers in the overparametrized regime under the bi-level model with Gaussian covariates. In particular they prove a conjecture made in a previous paper about the region (characterized by the paramters of the bi-level model) under which the generalization error can go to zero. In fact, they establish a `0-1` law for generalization error: depending upon the parameter regime the probability of error either converges to zero or one. In the process of proving  this result the authors also establish a generalization of the usual Hanson Wight inequality for quadratic forms to exploit \"soft sparsity\". \n\nOverall, I feel that this paper contains a technically rigorous analysis of the overparametrized classification problem somewhat restrictive model assumptions. ", "questions": "1. Can you include a discussion of some practical tasks where the bi-level model arises naturally? \n\n2. Regarding the second point in the weaknesses section, can you discuss (at least informally) the effect of model misspecification on the generalization guarantees. More generally, do you think that the same performance guarantees as Theorem 3.2 (i.e., probability of error converging to zero for the same parameter ranges) can be achieved adaptively without using the knowledge of model parameters ($p, q, r, t$) to construct the classifier? Or there is a price to pay for achieving zero generalization adaptively? ", "limitations": "I think that the strong model assumptions used in this paper might reduce the practical utility of the results of this paper. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": " The paper is well written, and while the material is quite technical, the authors do make an effort to provide sufficient context and explanations to motivate them. In particular, the detailed overview of the argument used in proving the main result (Theorem 3.2) is quite helpful in getting the idea used in the proof. ", "weaknesses": "1.  While this paper does not seem to have any obvious flaws, I feel that the model analyzed in this paper is a bit too restrictive. In a footnote on page 4, the authors mention that \"such models are widely used to study learning even beyond this particular thread of work\". It would be very helpful, if the authors include a detailed discussion of at least one such practical application, which is naturally modeled by the bi-level model studied in this paper.  \n2. Besides the model, even the construction of the classifier makes some strong assumptions. In particular, the classifier is constructed after reweighting the features with weights $(\\lambda_i)_{i \\geq 1}$ that  are tuned to the specific bi-level model.  Since in most practical problems, there is at least some level of misspecification, I feel that this reduces the practical utility of the results in this paper. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and suggestions.\n> While this paper does not seem to have any obvious flaws, I feel that the model analyzed in this paper is a bit too restrictive. In a footnote on page 4, the authors mention that \"such models are widely used to study learning even beyond this particular thread of work\". It would be very helpful, if the authors include a detailed discussion of at least one such practical application, which is naturally modeled by the bi-level model studied in this paper.\n- Please see the general comment for an overview and motivation of the bi-level model. To repeat the key takeaway here, the bi-level model is a stylized version of the spiked covariance model. \n- Spiked covariance models have been extensively studied in the statistics literature (see e.g. [1], [2]), and are a common assumption for many statistical applications. Some concrete theoretical models related to the spiked covariance model include the sparse/nonnegative/tensor PCA problems and stochastic block model. For real life applications, some examples (lifted from [1]) include climate studies and functional data analysis. \n\n>Besides the model, even the construction of the classifier makes some strong assumptions. In particular, the classifier is constructed after reweighting the features with weights $(\\lambda\\_i)\\_{i \\ge 1}$ that are tuned to the specific bi-level model. Since in most practical problems, there is at least some level of misspecification, I feel that this reduces the practical utility of the results in this paper.\n\n- As mentioned above, we tried to stay as consistent as possible with the notation and setup of Subramanian et al., who used this explicit reweighting procedure in the exposition of the setup so that their analysis would be notationally simpler. We would like to emphasize that this explicit reweighting is done purely for analysis purposes, and in reality the actual classifier does *not* do any reweighting of features. The classifier observes jointly Gaussian features with labels during training and does min-norm interpolation to learn the score functions. At test time, the test vector is fed into the $k$ score functions to produce the labeling by looking for the highest score. The classifier has no dependence on the $\\lambda_i$, or $p, q, r, t$. It just sees the training data.\n- In the real world, misspecification is absolutely a real concern, so the reviewer’s concern about the role of misspecification is certainly warranted. So, an interesting question is to what extent is this classifier robust to distribution shift at test time? Roughly speaking, our intuition is that with small enough (non-adversarial) shifts, the margin that the classifier currently leverages to succeed would allow the classifier to still generalize.  This is because our analysis is largely tied to the training distribution (establishing appropriate concentration, etc.).  Quantifying this robustness is an interesting future direction and is in fact related to the fact that the min-norm interpolator generalizes for multi-label classification as well. We did not discuss the connection to misspecification in the paper at all, but if you think it is important please let us know and we will be sure to mention it in the revision.\n\n> Can you include a discussion of some practical tasks where the bi-level model arises naturally?\n- See the above discussion about spiked covariance models, and we will add some into the revision as well. Certainly, the bi-level model, being a simplified caricature model, has its own limitations which make it a little unrealistic. For example, the bi-level structure implies that the training dataset has balanced classes, which is often unrealistic in real world scenarios with lots of classes. Relaxing some of these assumptions is an interesting direction for future work.\n- The bi-level model is a tractable linear proxy for the more widely accepted manifold hypothesis about real-world high-dimensional data. \n\n> Regarding the second point in the weaknesses section, can you discuss (at least informally) the effect of model misspecification on the generalization guarantees. More generally, do you think that the same performance guarantees as Theorem 3.2 (i.e., probability of error converging to zero for the same parameter ranges) can be achieved adaptively without using the knowledge of model parameters $(p, q, r, t)$ to construct the classifier? Or there is a price to pay for achieving zero generalization adaptively?\n\n- The model parameters $(p, q, r, t)$ are only used to parameterize the data generating assumptions (the bi-level model), and the min-norm-trained classifier itself does not need to know any of these parameters to learn the score functions. Hence, the classifier defined in the paper will achieve the stated performance guarantees.\n- Of course, it receives $d = n^p$ dimensional features and knows that there are $k = n^t$ classes, but it is hard to think of a situation where a learning algorithm would not know these ahead of time. On the other hand, the classifier definitely does not need to know $q$ or $r$. One of the interesting results of our paper is that multiclass classification can succeed even in the regime $q+r>1$, where the empirical covariance is completely flat, despite the spike being present in the true covariance. Put differently, although the data approximately lies on a low dimensional manifold, you can’t see it from the empirical covariance given the limited amount of data available, so that it is naively impossible to recover $q$ and $r$. \n\n[1] Johnstone, I. M. (2001). On the distribution of the largest eigenvalue in principal components analysis. Annals of Statistics, 29(2), 295-327.\n\n[2] Donoho, David L., Matan Gavish, and Iain M. Johnstone. \"Optimal shrinkage of eigenvalues in the spiked covariance model.\" Annals of Statistics 46.4 (2018): 1742.\n"}, {"review_id": "Sr06vGJnrK", "reviewer": "Reviewer_ggP8", "summary": "In their main result, Theorem 3.2, the authors establish Conjecture 3.1 which is a conjecture posed in 2022 describing the asymptotic misclassification probability of the bi-level ensemble model (Definition 1) under a sparsity assumption (Assumption 1).  They provide a rigorous and tight analysis, with very clear explanations both in-text and in the appendix.  ", "questions": "There are two little details, which I didn't fully follow, so let me ask:\n\n- Perhaps a silly question, but in equation (182), are you using a Brascamp–Lieb inequality (or something simpler which I'm possibly missing)?\n\n- In equation (240) do you mean $n^{t-1}\\hat{\\boldsymbol{f}}_1[1]$ is $\\Theta(n^{(p-q-2)/2})$?", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is clearly written and explained wonderfully, the proofs are detailed, and the contributions are interesting.  The proofs are sound and clearly articulated.  \n\n\nMinor point, the appendix is also very neatly organized which makes proofreading nice.\n\n**Update:** My questions and concerns have been addressed. ", "weaknesses": "Overall the paper is rigerous and clear, so I do not really have any significant weakness worth reporting; only a few minor comments.\n\n* Only minor comments:*\n\n - In equations (36)-(40) could you explicitly write the polylogarithmic terms in the denominator, or at the very least, precisely defined them after the equation environments.\n\n- Could you formally state that all r.v. are defined on the same probability space, at the beginning of the paper; for rigor.\n\n- Very minor point, above equation (219), I guess $\\boldsymbol{A}_{-\\boldsymbol{S}}^{-1}$ is *block diagonal* not diagonal.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback and suggestions.\n\n> In equations (36)-(40) could you explicitly write the polylogarithmic terms in the denominator, or at the very least, precisely defined them after the equation environments.\n- Yes, we will include the explicit polylog factors. For clarity, all of these terms are at most $\\log(nsk)$. \n\n> Could you formally state that all r.v. are defined on the same probability space, at the beginning of the paper; for rigor.\n- We will add this to the paper as requested. The probability space for training can be viewed as being $n \\times d$ iid standard Gaussians, and extended for each test point by another $d$ iid standard Gaussians. All random variables for us are either linear combinations of the underlying iid Gaussians or functions of those random variables. There is no other randomness in the setup. \n\n> Very minor point, above equation (219), I guess $\\boldsymbol{A}\\_{-S}^{-1}$ is block diagonal not diagonal.\n\n- We see how there might be some confusion with the wording of the argument here. We will explicitly add the definition of the matrices into the notation table. We will also replace the text leading up to (219) with the following:\n\nSince $\\boldsymbol{A}\\_{-S}^{-1}$ is symmetric, it has an eigendecomposition $\\boldsymbol{V} \\boldsymbol{D} \\boldsymbol{V}^\\top$, where $\\boldsymbol{V}$ is an orthogonal matrix. Because $\\boldsymbol{W}\\_T$ is a weighted subset of only the (equally) favored features, its law is rotationally invariant. Furthermore, since $\\boldsymbol{A}\\_{-S}^{-1}$ is independent of $\\boldsymbol{W}\\_T$ (as $T \\subseteq S$), we can absorb the rotation $\\boldsymbol{V}$ into $\\boldsymbol{W}\\_T$ to reduce to the case where $\\boldsymbol{A}\\_{-S}^{-1} = \\boldsymbol{D}$..\n\n> Perhaps a silly question, but in equation (182), are you using a Brascamp–Lieb inequality (or something simpler which I'm possibly missing)?\n- There is a typo here (thank you so much for pointing it out); there should be an expectation on the LHS: it should be $$\\mathbb{E} \\exp(\\lambda S_{\\mathrm{diag}}) = \\prod_{i=1}^n \\mathbb{E}\\_{X\\_i, Y\\_i} \\exp(\\lambda m\\_{ii} (X\\_iY\\_i - \\mathbb{E}[X\\_iY\\_i])),$$ which is just using independence of the $(X\\_i, Y\\_i)$ pairs. After that, we apply Jensen’s inequality to get to the next line. \n\n> In equation (240) do you mean $n^{t-1}\\hat{\\boldsymbol{f}}_1[1]$ is $\\Theta(n^{(p-q-2)/2})$? \n- Yes, that is correct, we will fix the notation in the revision. \n"}, {"review_id": "XiDiTfYTbF", "reviewer": "Reviewer_S1af", "summary": "This is a theoretical paper that gives insight into how and when an overparametrized linear classification model, for multi-class classification, can be successfully generalized.    In particular, they look at multiclass classification under the Gaussian covariates bi-level model introduced by Subramamian et al. in 2022, and fully resolve a conjecture from that paper.  The key to their analysis is a new variant of the Hanson-Wright inequality.", "questions": "\nNone.", "limitations": "\nIt would be helpful to comment on the limitations of the bi-level model studied.   ", "rating": 8, "confidence": 1, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper builds on previous work to give tight bounds on the regions where generalization is possible, improving significantly on previous partial results.  It also makes rigorous previous analyses based on heuristic calculations.\nThis is a very well-written paper.\nBased on the proof sketch given in the main paper, the technical level of the proofs seems high, involving both the use of existing techniques as well as the proof of a new version of the Hanson-Wright inequality,.", "weaknesses": "No significant weaknesses were noted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review. \n\n> It would be helpful to comment on the limitations of the bi-level model studied.\n- As mentioned in the general comment, because the main contribution of our paper is resolving the conjecture of Subramanian et al., we chose to adopt the same model and notation for ease of comparison.\n- Certainly, the bi-level model, being a simplified caricature model, has its own limitations which make it a little unrealistic. For example, the bi-level structure implies that the training dataset has balanced classes, which is often unrealistic in real world scenarios with lots of classes. Relaxing some of these assumptions is an interesting direction for future work. See also our rebuttal to Reviewer V1nE for a more in depth discussion of how one might be able to relax the assumptions of the bi-level model. \n\n"}, {"review_id": "X4L8CRkFCi", "reviewer": "Reviewer_V1nE", "summary": "The paper titled \"Asymptotic Generalization of Overparameterized Linear Models for Multiclass Classification under Gaussian Covariates Bi-level Model\" presents a study on the asymptotic generalization of overparameterized linear models for multiclass classification under the Gaussian covariates bi-level model. The authors provide an asymptotic characterization of the generalization of a linear model for multiclass classification in an idealized Gaussian setting where a) the number of data points, b) the dimension, and c) the number of classes diverge while their ratio remains fixed. An interesting result, in particular, is that the min-norm interpolating classifier can be suboptimal in this regime.", "questions": "How realistic is the  Bi-level feature weighting model ? I am thinking instead of the source/capacity setting where I would expect a more power-law-like behavior. How different would the conclusions be?", "limitations": "The paper is theoretical in nature and its limitations are stated in the theorems", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper present many strong analytical results.\n\nIn particular, the authors have successfully resolved a conjecture posed in a previous works  (Subramanian et al. '22,) and established new lower bounds that demonstrate the misclassification rate either goes to 0 or 1 asymptotically.  The paper also introduces a new variant of the Hanson-Wright inequality, a tool used in high-dimensional probability, that is particularly useful for multiclass problems with sparse labels. Sparse labels refer to situations where only a small number of classes are represented in the dataset.\n", "weaknesses": "   ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and feedback. \n> How realistic is the Bi-level feature weighting model ? I am thinking instead of the source/capacity setting where I would expect a more power-law-like behavior. How different would the conclusions be?\n\n- Because our paper focuses on resolving the conjecture of Subramanian et al., we chose to adopt the same model and notation for ease of comparison. \n- You are correct that in applications for spiked covariance models, one typically sees power-law like behavior. We expect that the bi-level model can be relaxed to allow for constant deviations in the weightings for the $s-k$ favored features that are not label defining, and a power law decay for the $d-s$ unfavored features. The former change would likely only affect constants in certain areas of the argument that do not crucially depend on the exact constants involved, whereas the latter would likely just change the effective degree of overparameterization (à la Bartlett et al.). In this type of more relaxed bi-level setup, we expect an analogous result to hold, but ironing out these details is definitely an important next step. \n- However, even allowing for constant fluctuations in weighting for the label-defining features can lead to many subtleties. Even constant fluctuations in label defining weightings manifest as polynomial variations in how many examples of each class there are. Hence the heterogeneity between label-defining directions would likely lead to much messier condition for generalization.\n- On that note, if one is able to analyze the heterogeneity in label-defining features, one would naturally also capture a setup with imbalanced classes, which is more representative of real-life applications. We leave this as an interesting direction for future work.\n\n\n"}, {"review_id": "kGVvyWGgZf", "reviewer": "Reviewer_qo1L", "summary": "The paper studies the asymptotic generalization error behavior of an overparameterized linear model and under the Gaussian covariates bi-level model. In this setup, the number of data points, features, and classes all grow together. The authors manage to fully characterize the regimes of the generalization error, which is surprisingly “polarized”. This solves the conjecture posed by Subramanian et al. (2022).", "questions": "\n-  It would be useful to provide more intuition about the considered “bi-level ensemble” model. In this model, it seems that while we are considering $n^p$ dimensions, the ``effective dimensions’’ is the favored ones; meaning that the features in the rest of the dimensions (and their relative magnitude) somehow either add a “useful noise injection” or become dominant with respect to the “signal” which makes the prediction impossible. This might be inexact, but this is just to give an example of what kind of intuition I refer to.\n \n-  Similarly, it would be extremely useful to discuss the different regimes of the theorems. Why having $r$ close to 1 would fail the learner? Why having a small $p-(q+r)$ would do so?\n \n-   Finally, the scope of the paper remains a bit narrow (and purely technical) and the authors could probably use the intuitions derived from their results to discuss some potential understanding that these results could give about some more realistic setups. This is shortly done in the discussion section, but it would be appreciated to be extended.\n\n", "limitations": "As discussed above, and I guess the authors would also agree, the considered model is quite restrictive.", "rating": 7, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "Both the achieved theoretical result and also the used technical tools (like the newly established Hanson-Wright inequality) are highly novel and strong. Even though I am not familiar with the literature, I estimate that the work is quite valuable.", "weaknesses": "\n- The considered assumptions for the distribution of features are very simplistic. Both independence and having identical Gaussian distributions are very restrictive; which highly influences the practicality of the results.\n \n-  The paper studies the generalization error of linear models; which are far from the deep neural networks. In this sense, there is still a big gap in the practical aspects of the paper (and also the previous literature on this). However, it is totally understandable that these are the first steps toward that goal.\n\n- The paper lacks providing the needed intuitions about the obtained results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive review and detailed feedback. \n> The considered assumptions for the distribution of features are very simplistic. Both independence and having identical Gaussian distributions are very restrictive; which highly influences the practicality of the results.\n- Because our paper focuses on resolving the conjecture of Subramanian et al., we chose to adopt the same model and notation for ease of comparison. \n- With respect to independence, we agree that it is a strong simplifying assumption. However, it is not essential for every part of the argument. In several places, we use union bound, so independence is not really needed. Furthermore, in the Gaussian world, independence is assumed mainly just for exposition. As long as we assume the labels are being determined by a subspace of the features, we can do a basis change for the sake of analysis to make the covariance diagonal (and the learning algorithm need not know about this basis change). \n- Generally speaking, we made these simplifying assumptions for the sake of tractability. Of course, there is a need to move beyond flat covariances, but it requires more work. As we explain in the response to reviewer V1nE, we think that many of the same results hold if we allow the covariance to be heterogeneous along the non-label defining directions, but the situation likely becomes much more complex if the label-defining directions are allowed to be heterogeneous. \n- We think that going from Gaussian to subgaussian distributions will be fine if we use an appropriate vector notion of subgaussianity that allows us to perform basis changes. One place where the Gaussianity assumption is used explicitly is the margin computation, where we needed to use the fact that the gap between the max and second max decays at a logarithmic rate. It is certainly of interest to precisely identify where else we actually need the Gaussian assumption and where we can relax it. \n\n> The paper studies the generalization error of linear models; which are far from the deep neural networks. In this sense, there is still a big gap in the practical aspects of the paper (and also the previous literature on this). However, it is totally understandable that these are the first steps toward that goal.\n- We agree that like many other papers in the field, our work is just one of the first steps towards a more robust theory for deep networks. However, in finetuning settings where a nonlinear network is massively overparameterized with respect to the finetuning data, one can use the NTK approximation to study the finetuning behavior with overparameterized generalized linear models. Here, the pretraining of the model creates an implicit nonlinear lifting of the inputs into a high dimensional space, where every parameter of the model corresponds to one nonlinear feature in the lifting (via the first-order Taylor expansion of the model with respect to the finetunable parameters). It is an interesting question to determine whether real systems actually have the type of behavior predicted by our results. (In fact, the nature of our results point to the need for work in this direction because simply looking at the empirical eigenvalues of the training data might not reveal the existence of the underlying spiked structure that helps generalization work.)\n\n> The paper lacks providing the needed intuitions about the obtained results.\n- We will try to add some more intuition along the lines of your suggestion below.\n\n> It would be useful to provide more intuition about the considered “bi-level ensemble” model. In this model, it seems that while we are considering dimensions, the \"effective dimensions\" is the favored ones; meaning that the features in the rest of the dimensions (and their relative magnitude) somehow either add a “useful noise injection” or become dominant with respect to the “signal” which makes the prediction impossible. This might be inexact, but this is just to give an example of what kind of intuition I refer to.\n- Thanks for the suggestion about discussing the theorem. Your intuitions about the bi-level model are essentially correct. Below we answer your questions more directly.\n- The intuition for $ r \\approx 1 $ being a failure mode is that the model is effectively severely overparameterized, even after restricting to the favored features. In particular, since there are $n^t$ classes, the failure condition $t + r > 1$ precisely captures the right sense of bad overparameterization restricted to the subspace of $n^r$ favored features. \n- The other condition about $ p - (q+r) $  is about the feature weighting for favored features: if the favoring is too small, classification will not succeed because the noise/contamination from the unfavored features will dominate the signal. We will include this discussion in the revision. \n- The paper's discussion of the \"just average positive exemplars\" (non-interpolating) classifier should also help give a complementary intuition for the failure conditions. \n\n> Finally, the scope of the paper remains a bit narrow (and purely technical) and the authors could probably use the intuitions derived from their results to discuss some potential understanding that these results could give about some more realistic setups. This is shortly done in the discussion section, but it would be appreciated to be extended.\n- We agree that the main contribution of our paper is technical. However, one consequence of the technical work is that it justifies the style of heuristic calculation that led to the conjecture in the first place (carried out in the appendix of Subramanian et al.). We believe that a similar type of heuristic reasoning can be more widely applied in more realistic settings, with tools such as our sharpened Hanson-Wright inequality potentially being useful to justify those calculations.\n"}]

Author rebuttal:
We thank all of the reviewers for their comments and feedback. Below, we highlight some high level takeaways which address a set of questions shared across multiple reviewers.
## Bi-level model
- Because the main contribution of our paper is fully resolving the conjecture of Subramanian et al. from NeurIPS 2022, we chose to adopt the same model and notation in the paper for ease of comparison. 
-  The high level conceptual picture of the setup is as follows: The learner simply observes jointly Gaussian zero-mean features with some **unknown** covariance structure $\Sigma$ in a very high dimensional space, and performs min-norm interpolation of essentially one-hot-encoded labels to learn the score functions. These score functions are used at test-time to do multi-class classification. 
- Note that the learning algorithm has no knowledge of $\Sigma$, nor does it even know that the features are jointly Gaussian. *All the learning algorithm has is the training data.*
- For analysis purposes, $\Sigma$ is parameterized. In the spirit of spiked covariance models, where a low-dimensional subspace has higher variance, we study the case that the *eigenvalues* of $\Sigma$ follow the simplified bi-level model parameterized by $(p, q, r)$. The bi-level model stipulates that there are two discrete variance levels, the higher of which lies in the low-dimensional subspace. For this bi-level model, we are able to prove sharp phase-transition style results telling us when successful generalization will happen. Here, the number of classes also matters, and that is where the parameter $t$ enters. 
- This bi-level model is a stylized linear version of the well-known manifold hypothesis, which stipulates that real-world high dimensional data actually approximately lie on a low rank manifold that is unknown to the learning algorithm.
- To simplify notation in the paper, Subramanian, et. al. just assume $\Sigma$ is diagonal to begin with instead of explicitly rotating coordinates to the eigenbasis of a general $\Sigma$. Because min-norm interpolation only cares about norms, this is without loss of generality. 

The camera-ready version will make this setup clearer.


Meta-review: Some very nice and surprising results on a topic of wide interest.

We noted that many of the reviewers had low confidence.  The authors are encouraged to write for a wider audience.
Decision: Accept (spotlight)