# Precise Asymptotic Generalization for Multiclass Classification with
Overparameterized Linear Models

David X. Wu
Department of EECS
UC Berkeley
Berkeley, CA 94720
<EMAIL_ADDRESS>
Anant Sahai
Department of EECS
UC Berkeley
Berkeley, CA 94720
<EMAIL_ADDRESS>

###### 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. (2022), where the number of data points,
features, and classes all grow together. We fully resolve the conjecture posed
in Subramanian et al. (2022), matching the predicted regimes for
generalization. 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 multilabel classification problem under the same bi-level ensemble.

##  1 Introduction

In this paper, we directly follow up on a specific line of work initiated by
Subramanian et al. (2022); Wu and Sahai (2023). For the sake of self-
containedness, we briefly reiterate the context, directing the reader to
Subramanian et al. (2022) and the references cited therein for more. A 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 can 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 on one particular thread of investigation that can be
rooted in Bartlett et 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 et 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 al. (2022) where a conjecture was presented for when minimum-
norm interpolating classifiers will generalize. We are now in a position to
state our main contributions; afterwards, we expand on the related works.

### Our contributions

Our main contribution is crisply identifying the asymptotic regimes where an
overparameterized linear model that 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 a
misclassification rate $o(1)$, and we show a 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 a new variant of the Hanson-Wright inequality,
which applies to bilinear forms between a vector with subgaussian entries and
a vector that is bounded and has _soft sparsity_ , a notion we 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 overparameterized 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 algorithms’ implicit regularization (Soudry et al.,
2018; Ji and Telgarsky, 2019; Engl et 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
1-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 work111Regression 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 J of Subramanian et al. (2022). When regression
doesn’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) as discussed, for example, in Xu et al. (2023). 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 a 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 a 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 to 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 the 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) 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 a linearized version of the manifold hypothesis.

##  2 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 $k$ classes. The
training data consists of $n$ pairs $\\{{\bm{x}}_{i},\ell_{i}\\}_{i=1}^{n}$
where ${\bm{x}}_{i}\in\mathbb{R}^{d}$ are i.i.d standard Gaussian
vectors222Following previous work, we are staying within a Gaussian features
framework. However, recent developments have confirmed that these models are
actually predictive when the features arise from nonlinearities in a 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).. We assume that the labels $\ell_{i}\in[k]$
are generated as follows.

######  Assumption 1 (1-sparse noiseless model).

The class labels $\ell_{i}$ are generated based on which of the first $k$
dimensions of a point ${\bm{x}}_{i}$ has the largest value,

$\displaystyle\ell_{i}=\operatorname*{arg\,max}_{m\in[k]}{\bm{x}}_{i}[m].$ (1)

Let us emphasize at this point that the classifier that we analyze only
observes the training data, and does not use any of the data-generating
assumptions.

For a vector ${\bm{x}}$, we index its $j$th entry with ${\bm{x}}[j]$. Hence,
under Assumption 1, ${\bm{x}}_{i}[m]$ can be interpreted as how representative
of class $m$ the $i$th training point is.

For clarity of exposition in the analysis, we make explicit a feature
weighting that transforms the training points:

$\displaystyle{\bm{x}}^{w}_{i}[j]=\sqrt{\lambda_{j}}{\bm{x}}_{i}[j]\quad\forall
j\in[d].$ (2)

Here $\bm{\lambda}\in\mathbb{R}^{d}$ contains the squared feature weights. The
feature weighting serves the role of favoring the true pattern, something that
is essential for good generalization. Again, we emphasize that the classifier
does not do any reweighting of features; this explicit step is purely
syntactic. 333Our weighted feature model is equivalent to other works (e.g.
Muthukumar et al. (2021)) that assume that the covariates come from a
$d-$dimensional anisotropic Gaussian with a covariance matrix $\Sigma$ that
favors the truly important directions (Wei et al., 2022). These directions do
not have to be axis-aligned — we make that assumption only for notational
convenience. In reality, the optimizer will never know these directions a
priori.

The weighted feature matrix ${\bm{X}}^{w}\in\mathbb{R}^{n\times d}$ is given
by

where we introduce the notation ${\bm{z}}_{j}\in\mathbb{R}^{n}$ to contain the
$j^{th}$ feature from the $n$ training points. Note that ${\bm{z}}_{j}\sim
N(0,{\bm{I}}_{n})$ are i.i.d Gaussians. We use a one-hot encoding for
representing the labels as the matrix
${\bm{Y}}^{\mathsf{oh}}\in\mathbb{R}^{n\times k}$

$\displaystyle{\bm{Y}}^{\mathsf{oh}}$
$\displaystyle=\begin{bmatrix}{\bm{y}}^{\mathsf{oh}}_{1}&\cdots&{\bm{y}}^{\mathsf{oh}}_{k}\end{bmatrix},\quad\quad\text{where}\quad\quad{\bm{y}}^{\mathsf{oh}}_{m}[i]=\begin{cases}1,&\text{if}\
\ell_{i}=m\\\ 0,&\text{otherwise}\end{cases}.$ (3)

Since we consider linear models, we center the one-hot encodings and define

$\displaystyle{\bm{y}}_{m}\triangleq{\bm{y}}^{\mathsf{oh}}_{m}-\frac{1}{k}{\bm{1}}.$
(4)

Our classifier consists of $k$ coefficient vectors $\widehat{{\bm{f}}}_{m}$
for $m\in[k]$ that are learned by minimum-norm interpolation (MNI) of the
zero-mean one-hot variants using the weighted features:444The 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 overparameterization (Wang et al., 2021;
Kaushik et al., 2023). Recently, Lai and Muthukumar (2023) showed via an
extension of Ji and Telgarsky (2021) that a much broader category of losses
also asymptotically results in convergence to the same MNI solution for
sufficiently overparameterized classification problems.

$\displaystyle\widehat{{\bm{f}}}_{m}$
$\displaystyle=\arg\min_{\bm{f}}\|{\bm{f}}\|_{2}$ (5) s.t.
$\displaystyle{\bm{X}}^{w}{\bm{f}}={\bm{y}}_{m}.$ (6)

We can express these coefficients in closed form as

$\displaystyle\widehat{{\bm{f}}}_{m}=({\bm{X}}^{w})^{\top}\left({\bm{X}}^{w}({\bm{X}}^{w})^{\top}\right)^{-1}{\bm{y}}_{m}.$
(7)

On a test point ${\bm{x}}_{\mathsf{test}}\sim N(0,{\bm{I}}_{d})$ we predict a
label as follows: First, we transform the test point into the weighted feature
space to obtain ${\bm{x}}_{\mathsf{test}}^{w}$ where
${\bm{x}}_{\mathsf{test}}^{w}[j]=\sqrt{\lambda_{j}}{\bm{x}}_{\mathsf{test}}[j]$
for $j\in[d]$. Then we compute $k$ scalar “scores” and assign the class based
on the largest score as follows:

$\displaystyle\hat{\ell}=\operatorname*{arg\,max}_{1\leq m\leq
k}\widehat{{\bm{f}}}_{m}^{\top}{\bm{x}}_{\mathsf{test}}^{w}.$ (8)

By assumption, a misclassification event ${\mathcal{E}}_{{\textsf{err}}}$
occurs whenever

$\displaystyle\operatorname*{arg\,max}_{1\leq m\leq
k}{\bm{x}}_{\mathsf{test}}[m]\neq\operatorname*{arg\,max}_{1\leq m\leq
k}\widehat{{\bm{f}}}_{m}^{\top}{\bm{x}}_{\mathsf{test}}^{w}.$ (9)

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 model555Such models are widely used to study learning
even beyond this particular thread of work. For example, Tan et al. (2023)
uses this to understand the privacy/generalization tradeoff of
overparameterized learning.:

######  Definition 1 (Bi-level ensemble).

The bi-level ensemble is parameterized by $p,q,r$ and $t$ where $p>1$, $0\leq
r<1$, $0<q<(p-r)$ and $0\leq t<r$. Here, parameter $p$ controls the extent of
overparameterization, $r$ determines the number of favored features, $q$
controls the weights on favored features, and $t$ 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:

$\displaystyle d=\lfloor n^{p}\rfloor,s=\lfloor
n^{r}\rfloor,a=n^{-q},k=c_{k}\lfloor n^{t}\rfloor,$ (10)

where $c_{k}$ is a positive integer. Define the feature weights by

$\displaystyle\sqrt{\lambda_{j}}=\begin{cases}\sqrt{\frac{ad}{s}},&1\leq j\leq
s\\\ \sqrt{\frac{(1-a)d}{d-s}},&\mathrm{otherwise}\end{cases}.$ (11)

We introduce the notation $\lambda_{F}\triangleq\frac{ad}{s}$ and
$\lambda_{U}\triangleq\frac{(1-a)d}{d-s}$ to distinguish between the (squared)
favored 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 a simple family of
overparameterized problems where learning can succeed. Although there are
$d=n^{p}$ features where $d\gg n$, there is a low dimensional subspace of
favored, higher weight features of dimension $s=n^{r}$, and $s\ll n$. From
this perspective, the bi-level model can be viewed as a parameterized version
of an approximate linear manifold hypothesis. Depending on the signal
strength, the noise added from the $d-s$ unfavored features can either help
generalization (“benign overfitting”) or overwhelm the true signal and cause
the classifier to fail.

Figure 1: Bi-level feature weighting model. The first $s$ features have a
higher weight and are favored during minimum-norm interpolation. These can be
thought of as the square roots of the eigenvalues of the feature covariance
matrix $\Sigma$ in a Gaussian model for the covariates as in Bartlett et al.
(2020).

##  3 Main results

In this section, we state our main results and compare them to 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.

######  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), as $n\rightarrow\infty$, the
probability of misclassification $\Pr[{\mathcal{E}}_{{\textsf{err}}}]$ for MNI
as described in Eq. 5 satisfies

$\displaystyle\Pr[{\mathcal{E}}_{{\textsf{err}}}]$
$\displaystyle\rightarrow\begin{cases}0,&\ \mathrm{if}\
t<\min\quantity{1-r,p+1-2\max\quantity{1,q+r}}\\\ 1,&\ \mathrm{if}\
t>\min\quantity{1-r,p+1-2\max\quantity{1,q+r}}\end{cases}.$ (12)

Our main theorem establishes that 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 1-sparse (Assumption 1), 3.1 holds.

For comparison, we quote the best previously known positive and negative
results for the bi-level model, which only hold in the restricted regime where
regression fails ($q+r>1$).

######  Theorem 3.3 (Generalization for bi-level model (Subramanian et al.,
2022)).

In the same setting as 3.1, in the regime where regression fails $(q+r>1$), as
$n\rightarrow\infty$ we have $\Pr[{\mathcal{E}}_{{\textsf{err}}}]\to 0$ if

$\displaystyle t<\min\quantity{1-r,p+1-2(q+r),p-2,2q+r-2}.$ (13)

######  Theorem 3.4 (Misclassification in bi-level model (Wu and Sahai,
2023)).

In the same setting as 3.1, in the regime where regression fails $(q+r>1$), as
$n\rightarrow\infty$ we have
$\Pr[{\mathcal{E}}_{{\textsf{err}}}]\geq\frac{1}{2}$ if

$\displaystyle t>\min\quantity{1-r,p+1-2(q+r)}.$ (14)

Let us interpret the different conditions in 3.1. To interpret the condition
$t<1-r$, first rearrange it to $t+r<1$. Recall that the parameter $r$ controls
the number of favored features, and hence is a 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^{t+r}$ parameters being
learned. From this perspective, the condition $t+r<1$ says that the problem is
“effectively underparameterized”.

The other condition on $p+1-2\max\quantity{1,q+r}$ comes from looking at the
noise from the unfavored features. To see why, recall that the squared favored
feature weighting is $\lambda_{F}=n^{p-q-r}$. So for fixed $p$, the quantity
$q+r$ controls the level of favored feature weighting. When $q+r>1$, the
favored feature weighting is small enough that regression fails, and the
empirical covariance becomes flat. In this case, the condition becomes
$t<p+1-2(q+r)=(p-q-r)+1-(q+r)$. As $q+r$ increases, the amount of favoring
decreases, making it harder to generalize.

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. 2 indicate
how Theorem 3.3 only applies where regression fails. In contrast, our new
result holds regardless of whether regression fails or not, as in 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.

The weak converse in the prior Theorem 3.4 captures some of the correct
conditions for misclassification, but again only when $q+r>1$. As depicted in
the maroon X region for $r<0.25$ in Fig. 2b, our main theorem gives a strong
converse, whereas Theorem 3.4 has nothing to say because $q+r<1$. Theorem 3.4
also only proves that the misclassification rate is asymptotically at least
$\frac{1}{2}$. In the red circle and maroon X regions, we illustrate how our
result pushes the misclassification rate to $1-o(1)$, which requires a more
refined analysis. We elaborate on this further in Section 4.

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 to a 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.

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 are new to this
paper, as is showing that the error tends to $1$ in the maroon regions.

##  4 Technical overview

We now sketch out the proof for our main theorem. As in Subramanian et al.
(2022), the starting point is writing out the necessary and sufficient
conditions for misclassification.

Assume without loss of generality that the test point
${\bm{x}}_{\mathsf{test}}\sim N(0,{\bm{I}}_{d})$ has true label $\alpha$ for
some $\alpha\in[k]$. Let ${\bm{x}}_{\mathsf{test}}^{w}$ be the weighted
version of this test point. From (9), an equivalent condition for
misclassification is that for some $\beta\neq\alpha,\beta\in[k]$, we have
$\widehat{{\bm{f}}}_{\alpha}^{\top}{\bm{x}}_{\mathsf{test}}^{w}<\widehat{{\bm{f}}}_{\beta}^{\top}{\bm{x}}_{\mathsf{test}}^{w}$,
i.e. the score for $\beta$ outcompetes the score for $\alpha$. Define the Gram
matrix ${\bm{A}}\triangleq{\bm{X}}^{w}({\bm{X}}^{w})^{\top}$, the relative
label vector
$\bm{\Delta}y\triangleq{\bm{y}}_{\alpha}-{\bm{y}}_{\beta}\in\quantity{-1,0,1}^{n}$,
and the relative survival vector
$\widehat{{\bm{h}}}_{\alpha,\beta}\in\mathbb{R}^{d}$ which compares the signal
from $\alpha$ and $\beta$:

$\displaystyle\widehat{{\bm{h}}}_{\alpha,\beta}[j]$
$\displaystyle\triangleq\lambda_{j}^{-1/2}(\widehat{{\bm{f}}}_{\alpha}[j]-\widehat{{\bm{f}}}_{\beta}[j])$
(15) $\displaystyle={\bm{z}}_{j}^{\top}\bm{A}^{-1}\bm{\Delta}y,$ (16)

where to obtain the last line we have used (7). By converting the
misclassification condition into the unweighted feature space we see that we
will have errors when

$\displaystyle\lambda_{\alpha}\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]{\bm{x}}_{\mathsf{test}}[\alpha]-\lambda_{\beta}\widehat{{\bm{h}}}_{\beta,\alpha}[\beta]{\bm{x}}_{\mathsf{test}}[\beta]<\sum_{j\notin\\{\alpha,\beta\\}}\lambda_{j}\widehat{{\bm{h}}}_{\beta,\alpha}[j]{\bm{x}}_{\mathsf{test}}[j].$
(17)

Define the contamination term $\mathsf{CN}_{\alpha,\beta}$:

$\mathsf{CN}_{\alpha,\beta}\triangleq\sqrt{\sum_{j\notin\\{\alpha,\beta\\}}\lambda_{j}^{2}(\widehat{{\bm{h}}}_{\beta,\alpha}[j])^{2}}.$
(18)

Note that $\mathsf{CN}_{\alpha,\beta}$ normalizes the RHS of (17) into a
standard Gaussian. Indeed, define

$Z^{(\beta)}\triangleq\frac{1}{\mathsf{CN}_{\alpha,\beta}}\sum_{j\notin\\{\alpha,\beta\\}}\lambda_{j}\widehat{{\bm{h}}}_{\beta,\alpha}[j]{\bm{x}}_{\mathsf{test}}[j]\sim
N(0,1).$ (19)

Since $\alpha,\beta\in[k]$ are favored, we have
$\lambda_{\alpha}=\lambda_{\beta}=\lambda_{F}$. Hence an equivalent condition
for misclassification is that there exists some $\beta\neq\alpha$,
$\beta\in[k]$ such that

$\displaystyle\frac{\lambda_{F}}{\mathsf{CN}_{\alpha,\beta}}(\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]{\bm{x}}_{\mathsf{test}}[\alpha]-\widehat{{\bm{h}}}_{\beta,\alpha}[\beta]{\bm{x}}_{\mathsf{test}}[\beta])<Z^{(\beta)}.$
(20)

We now translate the above criterion into _sufficient_ conditions for correct
classification and misclassification and analyze these two cases separately.

##### Correct classification:

For correct classification, it suffices for the minimum value of the LHS of
Eq. 20 to outcompete the maximum value of the RHS, where the max is taken over
$\beta\in[k],\beta\neq\alpha$. Some algebra, as in Subramanian et al. (2022),
shows that we correctly classify if

$\displaystyle\underbrace{\frac{\min_{\beta}\lambda_{F}\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]}{\max_{\beta}\mathsf{CN}_{\alpha,\beta}}}_{{\textsf{SU}}/\mathsf{CN}\text{
ratio}}\Bigg{(}\underbrace{\min_{\beta}\left({\bm{x}}_{\mathsf{test}}[\alpha]-{\bm{x}}_{\mathsf{test}}[\beta]\right)}_{\text{closest
feature
margin}}-\underbrace{\max_{\beta}|{\bm{x}}_{\mathsf{test}}[\beta]|}_{\text{largest
competing feature}}$
$\displaystyle\cdot\underbrace{\max_{\beta}\left|\frac{\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]-\widehat{{\bm{h}}}_{\beta,\alpha}[\beta]}{\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]}\right|}_{\text{survival
variation}}\Bigg{)}$
$\displaystyle>\underbrace{\max_{\beta}Z^{(\beta)}}_{\text{normalized
contamination}}.$ (21)

We will show that under the conditions specified in 3.1, with high
probability, the relevant survival to contamination ratio
${\textsf{SU}}/\mathsf{CN}$ grows at a polynomial rate $n^{v}$ for some $v>0$,
whereas the term in the parentheses shrinks at a subpolynomial rate
$\omega(n^{-\delta})$ for any $\delta>0$. Further, by standard subgaussian
maximal inequalities, the magnitudes of the _normalized contamination_ are no
more than $O(\sqrt{\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
survival-to-contamination ratios.

##### Misclassification:

On the other hand, for misclassification it suffices for the maximum
_absolute_ value of the LHS of Eq. 20 to be outcompeted by the maximum value
of the RHS. Some manipulations yield the following sufficient condition for
misclassification:

$\displaystyle\underbrace{\frac{\max_{\beta}\lambda_{F}\quantity(\absolutevalue{\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]}+\absolutevalue{\widehat{{\bm{h}}}_{\beta,\alpha}[\beta]})}{\min_{\beta}\mathsf{CN}_{\alpha,\beta}}}_{{\textsf{SU}}/\mathsf{CN}\text{
ratio}}\cdot\underbrace{\max_{\gamma\in[k]}\absolutevalue{{\bm{x}}_{\mathsf{test}}[\gamma]}}_{\text{largest
label-defining
feature}}<\underbrace{\max_{\beta}Z^{(\beta)}}_{\text{normalized
contamination}}.$ (22)

We show that within the misclassification regimes in 3.1, the survival-to-
contamination ratio ${\textsf{SU}}/\mathsf{CN}$ _shrinks_ at a polynomial rate
$n^{-w}$ for some $w>0$. By standard subgaussian maximal inequalities, the
largest label-defining feature is $O(\sqrt{\log(nk)})$ with high probability.
Gaussian anticoncentration implies that for some
$\beta\neq\alpha,\beta\in[k]$, $Z^{(\beta)}$ outcompetes the LHS with
probability at least $\frac{1}{2}-o(1)$. Hence, we conclude that the model
will misclassify with rate at least $\frac{1}{2}$ 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. 22 and one of the $Z^{(\beta)}$’s on the RHS instead of the maximum
$Z^{(\beta)}$. It’s not hard to see from the definition of $Z^{(\beta)}$ in
Eq. 19 that the $Z^{(\beta)}$ are jointly Gaussian. For intuition’s sake,
assuming the $Z^{(\beta)}$ were _independent_ , then $\max_{\beta}Z^{(\beta)}$
would outcompete with probability $(\frac{1}{2}-o(1))^{k-1}$.

In reality, the $Z^{(\beta)}$ are correlated, but we are able to show that the
maximum correlation between the $Z^{(\beta)}$ is $\frac{1}{2}+o(1)$ with high
probability. An application of Slepian’s lemma (Slepian (1962)) and some
explicit bounds on orthant probabilities (Pinasco et al. (2021)) implies that
$\max_{\beta}Z^{(\beta)}>0$ with probability at least
$1-\frac{1}{k^{1+o(1)}}$. Another application of anticoncentration implies
that $\max_{\beta}Z^{(\beta)}>n^{-w}$ with probability $1-o(1)$, which
finishes off the proof.

###  4.1 Bounding the survival-to-contamination ratio

Note that the critical _survival-to-contamination_ ratio appears in both Eqs.
21 and 22. The most involved part of the proof is nailing down the correct
order of growth of the survival to contamination ratio; a similar analysis
tightly bounds the survival variation and the correlation structure of the
$Z^{(\beta)}$.

To understand the relative survival and contamination, we must analyze the
bilinear forms
$\widehat{{\bm{h}}}_{\alpha,\beta}[j]={\bm{z}}_{j}^{\top}\bm{A}^{-1}\bm{\Delta}y$.
Similarly, to control the correlation of the $Z^{(\beta)}$, we must understand
the correlation between the $\widehat{{\bm{h}}}_{\alpha,\beta}$ vectors, which
reduces to understanding the bilinear forms
${\bm{z}}_{j}^{\top}\bm{A}^{-1}{\bm{y}}_{\alpha}$ for $j\in[d],\alpha\in[k]$.
The main source of inspiration for bounding these bilinear forms is the
heuristic style of calculation carried out in Appendix K of Subramanian et al.
(2022) that leads to 3.1.

To simplify the discussion, we temporarily restrict to the regime where
regression fails ($q+r>1)$. However, our main technical tool seamlessly
generalizes to the regime where regression works ($q+r<1$). In the regime
where regression fails, $\bm{A}^{-1}$ turns out to have a _flat_ spectrum:
$\bm{A}^{-1}\approx\rho{\bm{I}}$ for some constant $\rho>0$. Assume for now
that $\bm{A}^{-1}$ is _exactly_ equal to a scaled identity matrix. Then the
survival is proportional to ${\bm{z}}_{\alpha}^{\top}\bm{\Delta}y$, which is a
random inner product. Similarly, to bound the contamination terms we must
control the random inner product ${\bm{z}}_{j}^{\top}\bm{\Delta}y$ for
$j\not\in\quantity{\alpha,\beta}$.

Since $\bm{\Delta}y$ is a sparse vector — it only has $\frac{2n}{k}$ nonzero
entries in expectation — a quick computation reveals that
$\mathbb{E}[{\bm{z}}_{\alpha}^{\top}\bm{\Delta}y]=\tilde{O}(\frac{n}{k})$ and
$\mathbb{E}[{\bm{z}}_{j}^{\top}\bm{\Delta}y]=0$. The deciding factor, then, is
how tightly these quantities concentrate around their means. A naïve
application of Hoeffding implies a concentration radius of order
$\tilde{O}(\sqrt{n})$, which would lead to looseness in the overall result.
The hope is to exploit sparsity to get a concentration radius of order
$\tilde{O}(\sqrt{n/k})$. This is where our new technical tool Theorem 4.2
comes in, which may be of independent interest; we present it in the following
section.

###  4.2 A new variant of the Hanson-Wright inequality

In reality, even in the regime where regression fails, $\bm{A}^{-1}$ is not
actually perfectly flat. Even worse, in the regime where regression works,
$\bm{A}^{-1}$ is actually spiked. Thus, we cannot simply reduce the bilinear
form ${\bm{z}}_{j}^{\top}\bm{A}^{-1}\bm{\Delta}y$ to an inner product.
Instead, we turn to 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).

However, just as the classic Hoeffding inequality is loose, so too is the
standard form of Hanson-Wright, because it also does not exploit sparsity. We
restate the classic version of Hanson-Wright below.

Define the subgaussian norm $\|\xi\|_{\psi_{2}}$ (Vershynin, 2018) as

$\displaystyle\norm{\xi}_{\psi_{2}}$
$\displaystyle=\inf_{K>0}\quantity{K:\mathbb{E}\exp(\xi^{2}/K^{2})\leq 2},$
(23)

######  Theorem 4.1 (Hanson-Wright for quadratic forms, from Rudelson and
Vershynin (2013)).

Let ${\bm{x}}=(X_{1},\ldots,X_{n})\in\mathbb{R}^{n}$ be a random vector
composed of independent random variables that are zero mean with
$\norm{X_{i}}_{\psi_{2}}\leq K$. There exists universal constant $c>0$ such
that for any deterministic ${\bm{M}}\in\mathbb{R}^{n\times n}$ and
$\epsilon\geq 0$,

$\displaystyle\Pr\left[|{\bm{x}}^{\top}{\bm{M}}{\bm{x}}-\mathbb{E}[{\bm{x}}^{\top}{\bm{M}}{\bm{x}}]|>\epsilon\right]\leq
2\exp(-c\min\quantity{\frac{\epsilon^{2}}{K^{4}\norm{{\bm{M}}}_{F}^{2}},\frac{\epsilon}{K^{2}\norm{{\bm{M}}}_{2}}}).$

The original Hanson-Wright inequality quoted above only applies to quadratic
forms, and moreover assumes that the matrix ${\bm{M}}$ is deterministic. In
our setting, we have a bilinear form
${\bm{z}}_{j}^{\top}\bm{A}^{-1}\bm{\Delta}y$, where $\bm{A}^{-1}$ is random.
One can condition on the realization of $\bm{A}^{-1}$, but this removes
independence and alters the distributions of the random variables involved. Of
course, if we condition on a random matrix which is independent of the random
vectors, then there is no issue.

Assuming a way around the independence issue, one could decompose the bilinear
form with the identity

$\displaystyle 4{\bm{z}}_{j}^{\top}\bm{A}^{-1}\bm{\Delta}y$
$\displaystyle=({\bm{z}}_{j}+\bm{\Delta}y)^{\top}\bm{A}^{-1}({\bm{z}}_{j}+\bm{\Delta}y)-({\bm{z}}_{j}-\bm{\Delta}y)^{\top}\bm{A}^{-1}({\bm{z}}_{j}-\bm{\Delta}y).$
(24)

This trick is used in both Muthukumar et al. (2021); Subramanian et al.
(2022). In the binary classification case, one regains complete independence
by using a leave-one-out trick. More precisely, define the leave-one-out
matrix ${\bm{A}}_{-j}=\sum_{i\neq
j}\lambda_{i}{\bm{z}}_{i}{\bm{z}}_{i}^{\top}$ and let
${\bm{y}}\in\quantity{\pm 1}^{n}$ be the binary label vector. Then
${\bm{A}}_{-j}$ is evidently independent of ${\bm{z}}_{j}$ and ${\bm{y}}$, and
the Sherman-Morrison formula implies that
${\bm{z}}_{j}^{\top}\bm{A}^{-1}{\bm{y}}=\frac{{\bm{z}}_{j}^{\top}{\bm{A}}_{-j}^{-1}{\bm{y}}}{1+{\bm{z}}_{j}^{\top}{\bm{A}}_{-j}^{-1}{\bm{z}}_{j}}$.
Because the denominator is a scalar which concentrates well due to Hanson-
Wright, this allows for a completely tight characterization of binary
classification.

However, this trick does not immediately work in the multiclass setting,
because the labels depend on all of the $k>1$ label-defining features. Here,
one needs to potentially remove $\omega(1)$ features from the Gram matrix
${\bm{A}}$ to regain independence. In Subramanian et al. (2022), they eschew
Sherman-Morrison entirely and directly exploit the fact that $\bm{A}^{-1}$ is
flat (as $q+r>1$). More precisely, they decompose
$\bm{A}^{-1}=\rho{\bm{I}}_{n}+{\bm{E}}$, where $\norm{{\bm{E}}}_{2}\ll\rho$.
This essentially shoves all the dependencies into ${\bm{E}}$. While the
$\rho{\bm{I}}_{n}$ portion reduces to the inner product calculation discussed
in Section 4.1, they must use Cauchy-Schwarz to handle the dependent
${\bm{E}}$ portion. This leads to inevitable looseness in the regimes for
Theorem 3.2, as Cauchy-Schwarz is a _worst-case_ bound. Interestingly, their
Cauchy-Schwarz bound leverages the sparsity of the label vectors to gain a
factor of $\sqrt{k}$, but the bound is still loose by a factor of $\sqrt{n}$.

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 first formally define the notions of soft and hard sparsity.

######  Definition 2 (Soft and hard sparsity).

For $\pi\leq 1$, we say that random vector ${\bm{y}}=(Y_{i})_{i=1}^{n}$ has
soft sparsity at level $\pi$ if $\absolutevalue{Y_{i}}\leq 1$ almost surely
and $\mathrm{Var}(Y_{i})\leq\pi$ for all $i$. On the other hand, we say that
${\bm{y}}$ has hard sparsity at level $\pi$ if at most a $\pi$ fraction of the
$Y_{i}$ are nonzero.

In particular, our variant Theorem 4.2 below requires that one of the vectors
in the bilinear form has _soft sparsity_ at level $\pi$. Throughout, one
should think of $\pi=o(1)$, and for us indeed $\pi=O(\frac{1}{k})$. One can
check that a bounded random vector ${\bm{y}}$ with _hard sparsity_ level $\pi$
must also have soft sparsity at level $O(\pi)$, so soft sparsity is more
general for bounded random vectors. In Table 1 we compare our variant with
several variants of Hanson-Wright which have appeared in the literature, some
of which involve hard sparsity.

######  Theorem 4.2 (Hanson-Wright for bilinear forms with soft sparsity).

Let ${\bm{x}}=(X_{1},\ldots,X_{n})\in\mathbb{R}^{n}$ and
${\bm{y}}\in(Y_{1},\ldots,Y_{n})\in\mathbb{R}^{n}$ be random vectors such that
the pairs $(X_{i},Y_{i})$ are independent pairs of (possibly correlated)
centered random variables with subgaussian norm at most $K$. Suppose
${\bm{\gamma}}=(\gamma_{1},\ldots,\gamma_{n})\in\quantity{0,1}^{n}$ is an
i.i.d. Bernoulli vector with bias $\pi$. Assume that ${\bm{\gamma}}$ is
independent of ${\bm{y}}$, $\gamma_{j}$ is independent of $X_{i}$ for $i\neq
j$, and finally _conditioned on $\gamma_{j}=1$_, $X_{j}$ has subgaussian norm
at most $K$. Then there exists an absolute constant $c>0$ such that for all
${\bm{M}}\in\mathbb{R}^{n\times n}$ and $\epsilon\geq 0$ we have

$\displaystyle\Pr\quantity[|{\bm{x}}^{\top}{\bm{M}}({\bm{y}}\circ{\bm{\gamma}})-\mathbb{E}[{\bm{x}}^{\top}{\bm{M}}({\bm{y}}\circ{\bm{\gamma}})]|>\epsilon]\leq
2\exp(-c\min\quantity{\frac{\epsilon^{2}}{K^{4}\pi\norm{{\bm{M}}}_{F}^{2}},\frac{\epsilon}{K^{2}\norm{{\bm{M}}}_{2}}}).$

Variant | Assumptions on ${\bm{y}}$ | Concentration radius
---|---|---
Classic quadratica: ${\bm{x}}^{\top}{\bm{M}}{\bm{x}}$ | same as ${\bm{x}}$ | $\tilde{O}(\norm{{\bm{M}}}_{F})$
Sparse bilinearb: ${\bm{x}}^{\top}{\bm{M}}({\bm{\gamma}}\circ{\bm{y}})$ |  $\gamma_{i}\sim\mathsf{Ber}(\pi)$, indep. of $X_{i}$ but not $Y_{i}$ | $\tilde{O}(\sqrt{\pi}\norm{{\bm{M}}}_{F})$
Theorem 4.3: ${\bm{x}}^{\top}{\bm{M}}({\bm{\gamma}}\circ{\bm{y}})$ |  $\gamma_{i}\sim\mathsf{Ber}(\pi)$, indep. of $Y_{i}$ but not $X_{i}$ | $\tilde{O}(\sqrt{\pi}\norm{{\bm{M}}}_{F})$
Theorem 4.2: ${\bm{x}}^{\top}{\bm{M}}{\bm{y}}$ |  $\absolutevalue{Y_{i}}\leq 1$ a.s., $\mathbb{E}Y_{i}^{2}\leq\pi$ | $\tilde{O}(\sqrt{\pi}\norm{{\bm{M}}}_{F})$
Table 1: Comparison of different variants of the Hanson-Wright inequality. In
all variants, we assume that $({\bm{x}},{\bm{y}})=(X_{i},Y_{i})_{i=1}^{n}$ are
subgaussian, centered, and the pairs $(X_{i},Y_{i})$ are independent across
$i$. We use $\circ$ to denote elementwise multiplication, which allows us to
express hard sparsity with the sparsity mask
${\bm{\gamma}}\in\quantity{0,1}^{n}$. The concentration radius corresponds to
the size of typical fluctuations guaranteed by the concentration inequality,
i.e. the $\epsilon$ needed for high probability guarantees. a (Rudelson and
Vershynin, 2013, Theorem 1.1); b (Park et al., 2022, Theorem 1)

The full proof of Theorem 4.2 is deferred to Appendix H. The main proof
techniques are heavily inspired by those of Rudelson and Vershynin (2013);
Zhou (2019); Park et al. (2022). However, the proof of Theorem 4.2 is actually
simpler than in Park et al. (2022), as bounded with soft sparsity turns out to
be easier to work with than subgaussian with hard sparsity. To actually apply
Hanson-Wright, we carefully isolate the dependent portions using the Woodbury
inversion formula, which generalizes the Sherman-Morrison formula for
arbitrary rank updates.

For the sake of completeness, in Appendix J we also prove a variant of Theorem
4.2 where we assume that ${\bm{y}}$ has subgaussian entries with hard
sparsity.

######  Theorem 4.3 (Sparse Hanson-Wright for bilinear forms).

Let ${\bm{x}}=(X_{1},\ldots,X_{n})\in\mathbb{R}^{n}$ and
${\bm{y}}\in(Y_{1},\ldots,Y_{n})\in\mathbb{R}^{n}$ be random vectors such that
the pairs $(X_{i},Y_{i})$ are independent pairs of (possibly correlated)
centered random variables with subgaussian norm at most $K$. Suppose
${\bm{\gamma}}=(\gamma_{1},\ldots,\gamma_{n})\in\quantity{0,1}^{n}$ is an
i.i.d. Bernoulli vector with bias $\pi$. Assume that ${\bm{\gamma}}$ is
independent of ${\bm{y}}$, $\gamma_{j}$ is independent of $X_{i}$ for $i\neq
j$, and finally _conditioned on $\gamma_{j}=1$_, $X_{j}$ has subgaussian norm
at most $K$. Then there exists an absolute constant $c>0$ such that for all
${\bm{M}}\in\mathbb{R}^{n\times n}$ and $\epsilon\geq 0$ we have

$\displaystyle\Pr\quantity[|{\bm{x}}^{\top}{\bm{M}}({\bm{y}}\circ{\bm{\gamma}})-\mathbb{E}[{\bm{x}}^{\top}{\bm{M}}({\bm{y}}\circ{\bm{\gamma}})]|>\epsilon]\leq
2\exp(-c\min\quantity{\frac{\epsilon^{2}}{K^{4}\pi\norm{{\bm{M}}}_{F}^{2}},\frac{\epsilon}{K^{2}\norm{{\bm{M}}}_{2}}}).$

We briefly illustrate how Theorem 4.2 can be used to get tighter results
throughout our analysis. A quick calculation reveals that the label vectors
$\bm{\Delta}y$ and ${\bm{y}}_{\alpha}$ both have soft sparsity at level
$\pi=O(1/k)$. However, ${\bm{y}}_{\alpha}$ does not have hard sparsity as
required by the variants in Park et al. (2022) or Theorem 4.3. Since
$\norm{{\bm{M}}}_{F}^{2}\leq n\norm{{\bm{M}}}_{2}^{2}$, we obtain a
concentration radius $\epsilon$ which scales like $\sqrt{n/k}$ rather than
$\sqrt{n}$ (obtained via vanilla Hanson-Wright) or $n/\sqrt{k}$ (obtained via
Cauchy-Schwarz). This gain is crucial to tightly analyzing the survival,
contamination, and correlation structure.

###  4.3 Completing the proof sketch

Theorem 4.2 and the above insights about sparsity and independence allow us to
prove the following bounds on the relative survival and contamination terms
which are tight up to log factors; see Section A.1 for more details. For
brevity’s sake, we introduce the notation $\mu\triangleq n^{q+r-1}$. [Bounds
on relative survival]propositionsurvivalacc Under the bi-level ensemble model
(Definition 1), when the true data generating process is 1-sparse (Assumption
1), if $t<\frac{1}{2}$, then with probability at least $1-O(1/nk)$

$\displaystyle\lambda_{F}\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]=c_{\ref{const_alpha}}\min\quantity{\mu^{-1},1}n^{-t}(1\pm
O(n^{-\kappa_{\ref{kappa_survival}}}))\sqrt{\log k},$

where $c_{\ref{const_alpha}}$ and $\kappa_{\ref{kappa_survival}}$ are positive
constants.

If $t\geq\frac{1}{2}$, then

$\displaystyle\lambda_{F}\absolutevalue{\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]}\leq
c_{\ref{const_rel_survival_upper}}\min\quantity{\mu^{-1},1}n^{-\frac{1}{2}}\sqrt{\log(nk)},$

where $c_{\ref{const_rel_survival_upper}}$ is a positive constant. Next, we
state our bounds on contamination. [Bounds on
contamination]propositioncontaminationacc Under the bi-level ensemble model
(Definition 1), when the true data generating process is 1-sparse (Assumption
1), with probability at least $1-O(1/nk)$,

$\displaystyle\mathsf{CN}_{\alpha,\beta}\leq\underbrace{\min\quantity{\mu^{-1},1}O(n^{\frac{r-t-1}{2}})\log(nsk)}_{\text{favored
features}}+\underbrace{O(n^{\frac{1-t-p}{2}})\sqrt{\log(nsk)}}_{\text{unfavored
features}}.$

Furthermore, if $t>0$, then with probability at least $1-O(1/nk)$,

$\displaystyle\mathsf{CN}_{\alpha,\beta}\geq\underbrace{\min\quantity{\mu^{-1},1}\Omega(n^{\frac{r-t-1}{2}})}_{\text{favored
features}}+\underbrace{\Omega(n^{\frac{1-t-p}{2}})}_{\text{unfavored
features}}.$

Translating the parameters above, we see that (i) the relative survival is
diminished by a factor $1/k$ as long as $k=o(\sqrt{n})$, and a factor
$1/\sqrt{n}$ for $k=\Omega(\sqrt{n})$ (this looseness ends up being negligible
for the final result) and (ii) the contamination is diminished by a factor of
$1/\sqrt{k}$. This essentially matches the expected behavior from the
heuristic calculation in Subramanian et al. (2022). With some straightforward
algebra, we can compute the regimes where the survival-to-contamination ratio
${\textsf{SU}}/\mathsf{CN}$ grows or decays polynomially. This yields the
stated regimes in 3.1; see Section A.1 for more details.

For technical reasons, the analogous bounds in Subramanian et al. (2022) are
loose, giving rise to unnecessary conditions for good generalization such as
$t<p-2$ and $t<2q+r-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 techniques 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
${\bm{z}}_{j}^{\top}\bm{A}^{-1}{\bm{y}}_{\alpha}$, which is possible thanks to
Theorem 4.2. 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
${\textsf{SU}}/\mathsf{CN}$ will grow or shrink polynomially. A similar
analysis thus reveals that MNI will generalize in exactly the same regimes as
in 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.

Perhaps surprisingly, resolving 3.1 also implies that MNI is asymptotically
_suboptimal_ compared to a natural _non-interpolative_ approach: simply make
$\widehat{{\bm{f}}}_{m}$ equal to the average666Note that Frei et al. (2023)
point out that even leaky ReLU networks trained with a gradient flow can
behave like averages of training examples. of all positive training examples
of class $m$. A straightforward analysis, detailed in the supplementary
material, reveals this scheme fails to generalize exactly when
$t<\min\quantity{1-r,p+1-2(q+r)}$, even in the regime where regression
succeeds ($q+r<1$). This is particularly interesting because we have shown
that in the regime where regression succeeds, MNI generalizes only when
$t<\min\quantity{1-r,p-1}$, which is a smaller region. In light of this gap,
it would be interesting to identify the _information-theoretic_ barrier for
multiclass classification, especially within the broader context of
statistical-computation 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.

## References

  * Abbe (2017) Emmanuel Abbe.  Community detection and stochastic block models: recent developments.  _The Journal of Machine Learning Research_ , 18(1):6446–6531, 2017.
  * Adler et al. (2007) Robert J Adler, Jonathan E Taylor, et al.  _Random fields and geometry_ , volume 80.  Springer, 2007.
  * Bartlett et al. (2020) Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler.  Benign overfitting in linear regression.  _Proceedings of the National Academy of Sciences_ , 117(48):30063–30070, 2020.
  * Bartlett et al. (2021) Peter L Bartlett, Andrea Montanari, and Alexander Rakhlin.  Deep learning: a statistical viewpoint.  _Acta numerica_ , 30:87–201, 2021.
  * Belkin (2021) Mikhail Belkin.  Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation.  _Acta Numerica_ , 30:203–248, 2021.
  * Belkin et al. (2020) Mikhail Belkin, Daniel Hsu, and Ji Xu.  Two models of double descent for weak features.  _SIAM Journal on Mathematics of Data Science_ , 2(4):1167–1180, 2020.
  * Brennan and Bresler (2020) Matthew Brennan and Guy Bresler.  Reducibility and statistical-computational gaps from secret leakage.  In _Conference on Learning Theory_ , pages 648–847. PMLR, 2020.
  * Chatterji and Long (2021) Niladri S Chatterji and Philip M Long.  Finite-sample analysis of interpolating linear classifiers in the overparameterized regime.  _Journal of Machine Learning Research_ , 22(129):1–30, 2021.
  * Chatterji and Long (2023) 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.
  * Chernozhukov et al. (2015) Victor Chernozhukov, Denis Chetverikov, and Kengo Kato.  Comparison and anti-concentration bounds for maxima of gaussian random vectors.  _Probability Theory and Related Fields_ , 162(1):47–70, 2015.
  * Cornacchia et al. (2023) 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):015019, 2023.
  * Dar et al. (2021) Yehuda Dar, Vidya Muthukumar, and Richard G Baraniuk.  A farewell to the bias-variance tradeoff? an overview of the theory of overparameterized machine learning.  _arXiv preprint arXiv:2109.02355_ , 2021.
  * Donoho et al. (2018) David L Donoho, Matan Gavish, and Iain M Johnstone.  Optimal shrinkage of eigenvalues in the spiked covariance model.  _Annals of statistics_ , 46(4):1742, 2018.
  * Engl et al. (1996) Heinz Werner Engl, Martin Hanke, and Andreas Neubauer.  _Regularization of inverse problems_ , volume 375.  Springer Science & Business Media, 1996.
  * Frei et al. (2023) Spencer Frei, Gal Vardi, Peter L Bartlett, and Nathan Srebro.  Benign overfitting in linear classifiers and leaky relu networks from kkt conditions for margin maximization.  _arXiv preprint arXiv:2303.01462_ , 2023.
  * Goldt et al. (2022) Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Marc Mézard, and Lenka Zdeborová.  The Gaussian equivalence of generative models for learning with shallow neural networks.  In _Mathematical and Scientific Machine Learning_ , pages 426–471. PMLR, 2022.
  * Gunasekar et al. (2018) Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro.  Characterizing implicit bias in terms of optimization geometry.  In _International Conference on Machine Learning_ , pages 1832–1841, 2018.
  * Hastie et al. (2022) Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani.  Surprises in high-dimensional ridgeless least squares interpolation.  _The Annals of Statistics_ , 50(2):949–986, 2022\.
  * Horn and Johnson (2012) Roger A Horn and Charles R Johnson.  _Matrix analysis_.  Cambridge university press, 2012.
  * Hsu et al. (2021) Daniel Hsu, Vidya Muthukumar, and Ji Xu.  On the proliferation of support vectors in high dimensions.  In _International Conference on Artificial Intelligence and Statistics_ , pages 91–99. PMLR, 2021.
  * Hu and Lu (2022) Hong Hu and Yue M Lu.  Universality laws for high-dimensional learning with random features.  _IEEE Transactions on Information Theory_ , 2022.
  * Ji and Telgarsky (2019) Ziwei Ji and Matus Telgarsky.  The implicit bias of gradient descent on nonseparable data.  In _Conference on Learning Theory_ , pages 1772–1798, 2019.
  * Ji and Telgarsky (2021) Ziwei Ji and Matus Telgarsky.  Characterizing the implicit bias via a primal-dual analysis.  In _Algorithmic Learning Theory_ , pages 772–804. PMLR, 2021.
  * Johnstone (2001) Iain M Johnstone.  On the distribution of the largest eigenvalue in principal components analysis.  _The Annals of statistics_ , 29(2):295–327, 2001\.
  * Kaplan et al. (2020) Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei.  Scaling laws for neural language models.  _arXiv preprint arXiv:2001.08361_ , 2020.
  * Kaushik et al. (2023) Chiraag Kaushik, Andrew D McRae, Mark A Davenport, and Vidya Muthukumar.  New equivalences between interpolation and svms: Kernels and structured features.  _arXiv preprint arXiv:2305.02304_ , 2023.
  * Lai and Muthukumar (2023) Kuo-Wei Lai and Vidya Muthukumar.  General loss functions lead to (approximate) interpolation in high dimensions.  _arXiv preprint arXiv:2303.07475_ , 2023.
  * Loureiro et al. (2021) Bruno Loureiro, Gabriele Sicuro, Cédric Gerbelot, Alessandro Pacco, Florent Krzakala, and Lenka Zdeborová.  Learning gaussian mixtures with generalized linear models: Precise asymptotics in high-dimensions.  _Advances in Neural Information Processing Systems_ , 34:10144–10157, 2021.
  * Lu and Yau (2022) Yue M Lu and Horng-Tzer Yau.  An equivalence principle for the spectrum of random inner-product kernel matrices.  _arXiv preprint arXiv:2205.06308_ , 2022.
  * Mallinar et al. (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–1195, 2022.
  * McRae et al. (2022) Andrew D McRae, Santhosh Karnik, Mark Davenport, and Vidya K Muthukumar.  Harmless interpolation in regression and classification with structured features.  In _International Conference on Artificial Intelligence and Statistics_ , pages 5853–5875. PMLR, 2022.
  * Mei and Montanari (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.
  * Misiakiewicz (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.10425_ , 2022.
  * Montanari and Richard (2015) Andrea Montanari and Emile Richard.  Non-negative principal component analysis: Message passing algorithms and sharp asymptotics.  _IEEE Transactions on Information Theory_ , 62(3):1458–1484, 2015.
  * Muthukumar et al. (2020) Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai.  Harmless interpolation of noisy data in regression.  _IEEE Journal on Selected Areas in Information Theory_ , 1(1):67–83, 2020.
  * Muthukumar et al. (2021) Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel J. Hsu, and Anant Sahai.  Classification vs regression in overparameterized regimes: Does the loss function matter?  _Journal of Machine Learning Research_ , 22:222:1–222:69, 2021.
  * Oneto et al. (2023) Luca Oneto, Sandro Ridella, and Davide Anguita.  Do we really need a new theory to understand over-parameterization?  _Neurocomputing_ , page 126227, 2023.
  * Papyan et al. (2020) 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.
  * Park et al. (2021) Seongoh Park, Xinlei Wang, and Johan Lim.  Estimating high-dimensional covariance and precision matrices under general missing dependence.  _Electronic Journal of Statistics_ , 15(2):4868–4915, 2021.
  * Park et al. (2022) Seongoh Park, Xinlei Wang, and Johan Lim.  Sparse Hanson-Wright inequality for a Bilinear Form of Sub-Gaussian variables.  _arXiv preprint arXiv:2209.05685_ , 2022.
  * Pesce et al. (2023) Luca Pesce, Florent Krzakala, Bruno Loureiro, and Ludovic Stephan.  Are gaussian data all you need? extents and limits of universality in high-dimensional generalized linear estimation.  _arXiv preprint arXiv:2302.08923_ , 2023.
  * Pinasco et al. (2021) Damián Pinasco, Ezequiel Smucler, and Ignacio Zalduendo.  Orthant probabilities and the attainment of maxima on a vertex of a simplex.  _Linear Algebra and its Applications_ , 610:785–803, 2021\.
  * Richard and Montanari (2014) Emile Richard and Andrea Montanari.  A statistical model for tensor pca.  _Advances in neural information processing systems_ , 27, 2014.
  * Rudelson and Vershynin (2010) Mark Rudelson and Roman Vershynin.  Non-asymptotic theory of random matrices: extreme singular values.  In _Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II–IV: Invited Lectures_ , pages 1576–1602. World Scientific, 2010.
  * Rudelson and Vershynin (2013) Mark Rudelson and Roman Vershynin.  Hanson-Wright inequality and sub-Gaussian concentration.  _Electronic Communications in Probability_ , 18:1–9, 2013\.
  * Slepian (1962) David S. Slepian.  The one-sided barrier problem for gaussian noise.  _Bell System Technical Journal_ , 41:463–501, 1962.
  * Soudry et al. (2018) 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.
  * Subramanian et al. (2022) Vignesh Subramanian, Rahul Arya, and Anant Sahai.  Generalization for multiclass classification with overparameterized linear models.  In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, _Advances in Neural Information Processing Systems_ , 2022.  URL https://openreview.net/forum?id=ikWvMRVQBWW.
  * Tan et al. (2023) 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.
  * Vershynin (2018) Roman Vershynin.  _High-dimensional probability: An introduction with applications in data science_ , volume 47.  Cambridge university press, 2018.
  * Wang et al. (2022) Guillaume Wang, Konstantin Donhauser, and Fanny Yang.  Tight bounds for minimum $\ell_{1}$-norm interpolation of noisy data.  In _International Conference on Artificial Intelligence and Statistics_ , pages 10572–10602. PMLR, 2022.
  * Wang and Thrampoulidis (2021) Ke Wang and Christos Thrampoulidis.  Benign overfitting in binary classification of Gaussian mixtures.  In _ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 4030–4034. IEEE, 2021.
  * Wang et al. (2021) Ke Wang, Vidya Muthukumar, and Christos Thrampoulidis.  Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation.  _arXiv e-prints_ , art. arXiv:2106.10865, June 2021.
  * Wang and Fan (2017) Weichen Wang and Jianqing Fan.  Asymptotics of empirical eigenstructure for high dimensional spiked covariance.  _Annals of statistics_ , 45(3):1342, 2017.
  * Wei et al. (2022) Alexander Wei, Wei Hu, and Jacob Steinhardt.  More than a 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 Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 23549–23588. PMLR, 17–23 Jul 2022.  URL https://proceedings.mlr.press/v162/wei22a.html.
  * Wu and Sahai (2023) David X Wu and Anant Sahai.  Lower bounds for multiclass classification with overparameterized linear models.  In _International Symposium on Information Theory_ , 2023.
  * Wu and Xu (2021) Yihong Wu and Jiaming Xu.  Statistical problems with planted structures: Information-theoretical and computational limits.  _Information-Theoretic Methods in Data Science_ , 383:13, 2021.
  * Xu et al. (2023) 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.
  * Zhang et al. (2016) Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization.  _arXiv preprint arXiv:1611.03530_ , 2016.
  * Zhang et al. (2021) 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\.
  * Zhou (2019) Shuheng Zhou.  Sparse Hanson–Wright inequalities for subgaussian quadratic forms.  _Bernoulli_ , 25(3):1603–1639, 2019.

###### Contents

  1. 1 Introduction
    1. 1.1 Brief treatment of related work
  2. 2 Problem setup
  3. 3 Main results
  4. 4 Technical overview
    1. 4.1 Bounding the survival-to-contamination ratio
    2. 4.2 A new variant of the Hanson-Wright inequality
    3. 4.3 Completing the proof sketch
  5. 5 Discussion
  6. A Preliminaries and notation
    1. A.1 Proof of Theorem 3.2
  7. B Main tools
    1. B.1 Hanson-Wright Inequality
    2. B.2 Gram matrices and the Woodbury formula
    3. B.3 Concentration of spectrum
  8. C Utility bounds: applying the tools
  9. D Bounding the survival
  10. E Bounding the contamination
    1. E.1 Upper bounding the contamination from label-defining+favored features
    2. E.2 Lower bounding the contamination from label-defining+favored features
    3. E.3 Bounding the unfavored contamination
  11. F Obtaining tight misclassification rate
    1. F.1 Main results for tight misclassification rates
    2. F.2 Lower bounding the denominator
    3. F.3 Upper bounding the numerator: the unnormalized correlation
      1. F.3.1 Bounding the favored correlation
      2. F.3.2 Bounding the unfavored correlation
  12. G Comparison to the straightforward non-interpolative scheme
  13. H A new variant of the Hanson-Wright inequality with soft sparsity
    1. H.1 Diagonal terms
    2. H.2 Offdiagonal terms
  14. I Proofs of main lemmas for concentration of spectrum
  15. J Hanson-Wright inequality for sparse subgaussian bilinear forms
    1. J.1 Diagonal terms
    2. J.2 Offdiagonal terms
  16. K Alternative framing of bi-level ensemble

##  Appendix A Preliminaries and notation

For positive integers $n$, we use the shorthand
$[n]\triangleq\quantity{1,\ldots,n}$. For a vector
${\bm{v}}\in\mathbb{R}^{n}$, $\norm{{\bm{v}}}_{2}$ always denotes the
Euclidean norm. We index entries by using square brackets, so ${\bm{v}}[j]$
denotes the $j$th entry of ${\bm{v}}$. For any matrix
${\bm{M}}\in\mathbb{R}^{m\times n}$, we denote its $ij$th entry by $m_{ij}$,
$\norm{{\bm{M}}}_{2}$ denotes the spectral norm, and
$\norm{{\bm{M}}}_{F}=\Tr({\bm{M}}^{\top}{\bm{M}})$ denotes the Frobenius norm.
We use $\sigma_{\max{}}({\bm{M}})$ and $\sigma_{\min{}}({\bm{M}})$ to denote
the maximum and minimum singular values of ${\bm{M}}$, respectively. If
${\bm{M}}\in\mathbb{R}^{n\times n}$ is symmetric, we write
$\mu_{1}({\bm{M}})\geq\mu_{2}({\bm{M}})\geq\ldots\geq\mu_{n}({\bm{M}})$ to
denote the ordered eigenvalues of ${\bm{M}}$. Given two vectors
${\bm{v}},{\bm{u}}\in\mathbb{R}^{n}$, we write
${\bm{v}}\circ{\bm{u}}\in\mathbb{R}^{n}$ to denote the entrywise product of
${\bm{v}}$ and ${\bm{u}}$.

We make extensive use of big-$O$ notation. In this paragraph, $c$ refers to a
positive constant which does not depend on $n$, and all statements hold for
sufficiently large $n$. If $f(n)=O(g(n))$, then $f(n)\leq cg(n)$ for some $c$.
If $f(n)=\tilde{O}(g(n))$, then $f(n)\leq cg(n)\operatorname{poly}\log(n)$ for
some $c$. If $f(n)=o(g(n))$, then for all $c>0$ we have $f(n)\leq cg(n)$. We
write $f(n)=\Omega(g(n))$ if $f(n)\geq cg(n)$ for some $c$. Finally, we write
$f(n)=\Theta(g(n))$ if there exists positive constants $c_{1}$ and $c_{2}$
such that $c_{1}g(n)\leq f(n)\leq c_{2}g(n)$.

Table 2: Notation Symbol | Definition | Dimension | Source
---|---|---|---
$k$ | Number of classes | Scalar | Sec. 2
$n$ | Number of training points | Scalar | Sec. 2
$d$ | Dimension of each point — the total number of features | Scalar | Sec. 2
$s$ | The number of favored features | Scalar | Def. 1
$a$ | The constant controlling the favored weights | Scalar | Def. 1
$p$ | Parameter controlling overparameterization ($d=n^{p}$) | Scalar | Def. 1
$r$ | Parameter controlling the number of favored features ($s=n^{r}$) | Scalar | Def. 1
$q$ | Parameter controlling the favored weights ($a=n^{-q}$) | Scalar | Def. 1
$t$ | Parameter controlling the number of classes ($k=c_{k}n^{t}$) | Scalar | Def. 1
$c_{k}$ | The number of classes when $t=0$ ($k=c_{k}n^{t}$) | Scalar | Def. 1
$\lambda_{j}$ | Squared weight of the $j$th feature | Scalar | Def. 1
${\bm{x}}_{i}$ |  $i$th training point (unweighted) | Length-$d$ vector | Sec. 2
$\ell_{i}$ | Class label of $i$th training point | Scalar | Eqn. 1
${\bm{w}}_{i}$ |  $i$th training point (weighted) | Length-$d$ vector | Eqn. 2
${\bm{X}}^{w}$ | Weighted feature matrix |  $(n\times d)$-matrix | Eqn. LABEL:eq:weightedxmatrix
${\bm{z}}_{j}$ | The collected $j$th features of all training points | Length-$n$ vector | Eqn. LABEL:eq:weightedxmatrix
${\bm{y}}^{\mathsf{oh}}_{m}$ | One-hot encoding of all the training points for label $m$ | Length-$n$ vector | Eqn. 3
${\bm{Y}}^{\mathsf{oh}}$ | One-hot label matrix | ($n\times k$)-matrix | Eqn. 3
${\bm{y}}_{m}$ | Zero-mean encoding of the training points for label $m$ | Length-$n$ vector | Eqn. 4
$\hat{{\bm{f}}}_{m}$ | Learned coefficients for label $m$ using min-norm interpolation | Length-$d$ vector | Eqn. 7
${\bm{x}}_{\mathsf{test}}$ | A single test point | Length-$d$ vector | Sec. 2
${\bm{x}}_{\mathsf{test}}^{w}$ | A single weighted test point | Length-$d$ vector | Sec. 2
${\bm{A}}$ | Gram matrix ${\bm{A}}={\bm{X}}^{w}({\bm{X}}^{w})^{\top}$ | ($n\times n$)-matrix | Sec. 4
$\mu_{i}({\bm{A}})$ | The $i$th eigenvalue of matrix ${\bm{A}}$, sorted in descending order | Scalar | App. A
$\lambda_{F}$ | Squared favored feature weights: $\lambda_{F}=\frac{ad}{s}$ | Scalar | Def. 1
$\lambda_{U}$ | Squared unfavored feature weights: $\lambda_{F}=\frac{(1-a)d}{d-s}$ | Scalar | Def. 1
$\widehat{{\bm{h}}}_{\alpha,\beta}$ | Relative survival $\widehat{{\bm{h}}}_{\alpha,\beta}[j]=\lambda_{j}^{-1/2}(\hat{f}_{\alpha}[j]-\hat{f}_{\beta}[j])$ | Length-$d$ vector | Eqn. 15
$\mathsf{CN}_{\alpha,\beta}$ | Normalizing factor $\mathsf{CN}_{\alpha,\beta}=\sqrt{\left(\sum_{j\notin\\{\alpha,\beta\\}}\lambda_{j}^{2}(\widehat{{\bm{h}}}_{\beta,\alpha}[j])^{2}\right)}$ | Scalar | Eqn. 18
$\norm{\cdot}_{\psi_{2}}$ | The subgaussian norm of a scalar random variable | Scalar | Eqn. 23
$\norm{\cdot}_{\psi_{1}}$ | The subexponential norm of a scalar random variable | Scalar | Eqn. 49
$\mu$ | Factor controlling whether regression works, $\mu\triangleq n^{q+r-1}$ | Scalar | App. A.1
${\bm{Z}}_{T}$ | Unweighted subset of favored features, where $T\subseteq[s]$ |  $(n\times\absolutevalue{T})$-matrix | App. B.2
${\bm{W}}_{T}$ | Weighted subset of favored features, ${\bm{W}}_{T}=\sqrt{\lambda_{F}}{\bm{Z}}_{T}$ |  $(n\times\absolutevalue{T})$-matrix | App. B.2
${\bm{A}}_{-T}$ | Leave-$T$-out Gram matrix, where $T\subseteq[s]$, ${\bm{A}}_{-T}={\bm{A}}-{\bm{W}}_{T}{\bm{W}}_{T}^{\top}$ |  $(n\times n)$-matrix | Eqn. 72
${\bm{H}}_{k}$ | Hat matrix, ${\bm{H}}_{k}={\bm{W}}_{k}{\bm{A}}_{-k}^{-1}{\bm{W}}_{k}$ |  $(k\times k)$-matrix | Eqn. B.2

Let us now describe the organization of the appendix. In Section A.1, we give
a 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
${\bm{z}}_{j}^{\top}\bm{A}^{-1}\bm{\Delta}y$ concentrate: our new variant of
the Hanson-Wright 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 G, we present the analysis for the averaging scheme
described in Section 5. Finally, we prove our new variants of Hanson-Wright
(Theorems 4.2 and 4.3) in Appendices H and J, respectively.

###  A.1 Proof of Theorem 3.2

In this section, we fill in 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
${\bm{x}}_{\mathsf{test}}\sim N(0,{\bm{I}}_{d})$ has true label $\alpha$ for
some $\alpha\in[k]$. Let ${\bm{x}}_{\mathsf{test}}^{w}$ be the weighted
version of this test point. From (9), an equivalent condition for
misclassification is that for some $\beta\neq\alpha,\beta\in[k]$, we have
$\widehat{{\bm{f}}}_{\alpha}^{\top}{\bm{x}}_{\mathsf{test}}^{w}<\widehat{{\bm{f}}}_{\beta}^{\top}{\bm{x}}_{\mathsf{test}}^{w}$,
i.e. the score for $\beta$ outcompetes the score for $\alpha$. Define the Gram
matrix ${\bm{A}}\triangleq{\bm{X}}^{w}({\bm{X}}^{w})^{\top}$, the relative
label vector
$\bm{\Delta}y\triangleq{\bm{y}}_{\alpha}-{\bm{y}}_{\beta}\in\quantity{-1,0,1}^{n}$,
and the relative survival vector
$\widehat{{\bm{h}}}_{\alpha,\beta}\in\mathbb{R}^{d}$ which compares the signal
from $\alpha$ and $\beta$:

$\displaystyle\widehat{{\bm{h}}}_{\alpha,\beta}[j]$
$\displaystyle\triangleq\lambda_{j}^{-1/2}(\widehat{{\bm{f}}}_{\alpha}[j]-\widehat{{\bm{f}}}_{\beta}[j])$
(25) $\displaystyle={\bm{z}}_{j}^{\top}\bm{A}^{-1}\bm{\Delta}y,$ (26)

where to obtain the last line we have used the explicit formula for the MNI
classifiers (7). By converting the misclassification condition into the
unweighted feature space we see that we will have errors when

$\displaystyle\lambda_{\alpha}\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]{\bm{x}}_{\mathsf{test}}[\alpha]-\lambda_{\beta}\widehat{{\bm{h}}}_{\beta,\alpha}[\beta]{\bm{x}}_{\mathsf{test}}[\beta]<\sum_{j\notin\\{\alpha,\beta\\}}\lambda_{j}\widehat{{\bm{h}}}_{\beta,\alpha}[j]{\bm{x}}_{\mathsf{test}}[j].$
(27)

Define the contamination term $\mathsf{CN}_{\alpha,\beta}$:

$\mathsf{CN}_{\alpha,\beta}\triangleq\sqrt{\sum_{j\notin\\{\alpha,\beta\\}}\lambda_{j}^{2}(\widehat{{\bm{h}}}_{\beta,\alpha}[j])^{2}}.$
(28)

Note that $\mathsf{CN}_{\alpha,\beta}$ normalizes the RHS of (27) into a
standard Gaussian. Indeed, define

$Z^{(\beta)}\triangleq\frac{1}{\mathsf{CN}_{\alpha,\beta}}\sum_{j\notin\\{\alpha,\beta\\}}\lambda_{j}\widehat{{\bm{h}}}_{\beta,\alpha}[j]{\bm{x}}_{\mathsf{test}}[j]\sim
N(0,1).$ (29)

Since $\alpha,\beta\in[k]$ are favored, we have
$\lambda_{\alpha}=\lambda_{\beta}=\lambda_{F}$. Hence an equivalent condition
for misclassification is that there exists some $\beta\neq\alpha$,
$\beta\in[k]$ such that

$\displaystyle\frac{\lambda_{F}}{\mathsf{CN}_{\alpha,\beta}}(\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]{\bm{x}}_{\mathsf{test}}[\alpha]-\widehat{{\bm{h}}}_{\beta,\alpha}[\beta]{\bm{x}}_{\mathsf{test}}[\beta])<Z^{(\beta)}.$
(30)

We will translate the above criterion into _sufficient_ conditions for correct
classification and misclassification 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 $\mu\triangleq n^{q+r-1}$; whether this quantity
polynomially shrinks or decays directly determines if regression works or
fails. We defer the proof of Section 4.3 to Appendix D and the proof of
Section 4.3 to Appendix E. Combining Sections 4.3 and 4.3 yields the following
sufficient conditions for when the ${\textsf{SU}}/\mathsf{CN}$ ratio grows or
shrinks polynomially.

######  Proposition A.1 (Regimes for survival-to-contamination).

Under the bi-level ensemble model (Definition 1), when the true data
generating process is 1-sparse (Assumption 1), as $n\rightarrow\infty$, with
probability at least $1-O(1/n)$, the survival-to-contamination ratio satisfies

$\displaystyle\frac{\min_{\beta}\lambda_{F}\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]}{\max_{\beta}\mathsf{CN}_{\alpha,\beta}}\geq
n^{v}\text{ for some }v>0\text{ if }$ $\displaystyle
t<\min\quantity{1-r,p+1-2\max\quantity{1,q+r}}$ (31)
$\displaystyle\frac{\max_{\beta}\lambda_{F}\absolutevalue{\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]}}{\min_{\beta}\mathsf{CN}_{\alpha,\beta}}\leq
n^{-w}\text{ for some }w>0\text{ if }$ $\displaystyle
t>\min\quantity{1-r,p+1-2\max\quantity{1,q+r}}$ (32)

Here, the max and min are being taken over $\beta\neq\alpha,\beta\in[k]$.

###### Proof.

We do casework on whether we want to prove an upper bound or lower bound on
${\textsf{SU}}/\mathsf{CN}$. First, suppose we want to prove the lower bound,
so assume $t<\min\quantity{1-r,p+1-2\max\quantity{1,q+r}}$. Since $t<r$ by the
definition of the bi-level ensemble (Definition 1), we have that
$t<\frac{1}{2}$. So by union bounding over $\beta$, Section 4.3 implies that
with probability $1-O(1/n)$

$\displaystyle\min_{\beta}\lambda_{F}\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]\geq\min\quantity{\mu^{-1},1}\Omega(n^{-t})\sqrt{\log
k}.$ (33)

Then from Section 4.3, by union bounding over $\beta$ we see that with
probability $1-O(1/n)$,

$\max_{\beta}\mathsf{CN}_{\alpha,\beta}\leq\underbrace{\min\quantity{\mu^{-1},1}\tilde{O}(n^{\frac{r-t-1}{2}})}_{\text{favored
features}}+\underbrace{\tilde{O}(n^{\frac{1-t-p}{2}})}_{\text{unfavored
features}}.$

Let us combine these two bounds. If we compare the survival to the
contamination coming from favored features, we obtain

$\displaystyle\frac{\min\quantity{\mu^{-1},1}n^{-t}\sqrt{\log
k}}{\min\quantity{\mu^{-1},1}\tilde{O}(n^{\frac{r-t-1}{2}})}$
$\displaystyle\geq\frac{n^{-t-\frac{r-t-1}{2}}}{\log(nsk)}$ (34)
$\displaystyle\geq\frac{n^{\frac{1-r-t}{2}}}{\log(nsk)},$ (35)

where we have included the explicit $\operatorname{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

$\displaystyle\frac{\min\quantity{\mu^{-1},1}n^{-t}\sqrt{\log
k}}{\tilde{O}(n^{\frac{1-t-p}{2}})}$
$\displaystyle\geq\frac{\min\quantity{\mu^{-1},1}n^{-t-\frac{1-t-p}{2}}}{\log(nsk)}$
(36) $\displaystyle\geq\frac{n^{-\max\quantity{q+r-1,0}}\cdot
n^{\frac{p-t-1}{2}}}{\log(nsk)}$ (37)
$\displaystyle\geq\frac{n^{\frac{p+1-2\max\quantity{1,q+r}-t}{2}}}{\log(nsk)}.$
(38)

Hence, by union bounding, we see that with probability $1-O(1/n)$,

$\displaystyle\min_{\beta}\frac{\lambda_{F}\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]}{\mathsf{CN}_{\alpha,\beta}}\geq
n^{v},$ (39)

where
$v\triangleq\frac{1}{4}\quantity(\min\quantity{1-r,p+1-2\max\quantity{1,q+r}}-t)>0$
by assumption.

For the upper bound, suppose $t>\min\quantity{1-r,p+1-2\max\quantity{1,q+r}}$.
Hence $t>0$, and by union bounding we conclude that with probability at least
$1-O(1/n)$,

$\displaystyle\max_{\beta}\lambda_{F}\absolutevalue{\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]}\leq\min\quantity{\mu^{-1},1}O(n^{-\frac{1}{2}})\sqrt{\log
k}$ (40)

and

$\displaystyle\min_{\beta}\mathsf{CN}_{\alpha,\beta}$
$\displaystyle\geq\min\quantity{\mu^{-1},1}\Omega(n^{\frac{r-t-1}{2}})+\Omega(n^{\frac{1-t-p}{2}}).$
(41)

Combining these and union bounding yields that with probability $1-O(1/n)$,

$\displaystyle\min_{\beta}\frac{\lambda_{F}\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]}{\mathsf{CN}_{\alpha,\beta}}\leq
n^{-w},$ (42)

where
$w\triangleq\frac{1}{4}\quantity(t-\min\quantity{1-r,p+1-2\max\quantity{1,q+r}})>0$
by asssumption. ∎

We now sketch out a proof of both the positive and negative sides of Theorem
3.2. We point out that the regimes for generalization and misclassification
exactly match the regimes above for where the ${\textsf{SU}}/\mathsf{CN}$
ratio grows or shrinks polynomially.

######  Theorem A.2 (Positive 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\rightarrow\infty$, the
probability of misclassification for MNI satisfies
$\Pr[{\mathcal{E}}_{{\textsf{err}}}]\to 0$ if

$\displaystyle t<\min\quantity{1-r,p+1-2\max\quantity{1,q+r}}.$

###### Proof sketch.

For correct classification, it suffices for the minimum value of the LHS of
Eq. 30 to outcompete the maximum value of the RHS, where the max is taken over
$\beta\in[k],\beta\neq\alpha$. Some algebra, as in Subramanian et al. [2022],
shows that we correctly classify if

$\displaystyle\underbrace{\frac{\min_{\beta}\lambda_{F}\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]}{\max_{\beta}\mathsf{CN}_{\alpha,\beta}}}_{{\textsf{SU}}/\mathsf{CN}\text{
ratio}}\Bigg{(}\underbrace{\min_{\beta}\left({\bm{x}}_{\mathsf{test}}[\alpha]-{\bm{x}}_{\mathsf{test}}[\beta]\right)}_{\text{closest
feature
margin}}-\underbrace{\max_{\beta}|{\bm{x}}_{\mathsf{test}}[\beta]|}_{\text{largest
competing feature}}$
$\displaystyle\cdot\underbrace{\max_{\beta}\left|\frac{\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]-\widehat{{\bm{h}}}_{\beta,\alpha}[\beta]}{\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]}\right|}_{\text{survival
variation}}\Bigg{)}$
$\displaystyle>\underbrace{\max_{\beta}Z^{(\beta)}}_{\text{normalized
contamination}}.$ (43)

By our lower bound on the survival to contamination ratio (Proposition A.1),
assuming $t<\min\quantity{1-r,p+1-2(q+r)}$, then with probability at least
$1-O(1/n)$ we have that
$\frac{\lambda_{F}\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]}{\mathsf{CN}_{\alpha,\beta}}\geq
n^{u}$ for some constant $u>0$. By Lemmas B.2 and B.3 in Subramanian et al.
[2022] for every $\epsilon>0$, with probability at least $1-\epsilon$, we have
$\min_{\beta}{\bm{x}}_{\mathsf{test}}[\alpha]-{\bm{x}}_{\mathsf{test}}[\beta]\geq\Omega(\frac{1}{\sqrt{\log
k}})$.

Next, by standard subgaussian maxima tail bounds we have that
$\absolutevalue{{\bm{x}}_{\mathsf{test}}[\beta]}\leq 2\sqrt{\log(nk)}$ and
$Z^{(\beta)}\leq 2\sqrt{\log(nk)}$ with probability at least $1-O(1/nk)$.
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 $n^{-w}$ with probability at least $1-O(1/nk)$.

By union bounding, we see that with probability at least $1-O(1/n)-\epsilon$,
the LHS outcompetes the RHS, implying that the model correctly classifies.

∎

In fact, given Section 4.3, it is straightforward to bound the survival
variation.

######  Proposition A.3 (Upper bound on the survival variation).

Suppose that $t<1-r$. With probability at least $1-2/n$, we have

$\absolutevalue{\frac{\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]-\widehat{{\bm{h}}}_{\beta,\alpha}[\beta]}{\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]}}\leq
c_{\ref{const_variance}}n^{-w},$ (44)

where $c_{\ref{const_variance}}$ and $w$ are both positive constants.

###### Proof.

Since we have
$\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]={\bm{z}}_{\alpha}^{\top}\bm{A}^{-1}\bm{\Delta}y$,
the survival variation is

$\frac{\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]-\widehat{{\bm{h}}}_{\beta,\alpha}[\beta]}{\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]}=\frac{{\bm{z}}_{\alpha}^{\top}\bm{A}^{-1}\bm{\Delta}y+{\bm{z}}_{\beta}^{\top}\bm{A}^{-1}\bm{\Delta}y}{{\bm{z}}_{\alpha}^{\top}\bm{A}^{-1}\bm{\Delta}y}$

Since $t<1-r$ and $t<r$ by definition, we know that $t<\frac{1}{2}$,and we can
apply Section 4.3 to see that with probability at least $1-2/n$ we have

$\displaystyle{\bm{z}}_{\alpha}^{\top}\bm{A}^{-1}\bm{\Delta}y$
$\displaystyle=\max\quantity{\mu^{-1},1}n^{-t}(1\pm
O(n^{-\kappa_{\ref{kappa_survival}}}))\sqrt{\log
k}=-{\bm{z}}_{\beta}^{\top}\bm{A}^{-1}\bm{\Delta}y$

Hence we have

$\absolutevalue{\frac{\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]-\widehat{{\bm{h}}}_{\beta,\alpha}[\beta]}{\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]}}\leq
c_{\ref{const_variance}}n^{-\kappa_{\ref{kappa_survival}}}$ (45)

where $c_{1}$ 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\rightarrow\infty$, the
probability of misclassification for MNI satisfies
$\Pr[{\mathcal{E}}_{{\textsf{err}}}]\to 1$ if

$\displaystyle t>\min\quantity{1-r,p+1-2\max\quantity{1,q+r}}.$

###### Proof sketch.

On the other hand, for misclassification it suffices for the maximum
_absolute_ value of the LHS of Eq. 30 to be outcompeted by the maximum value
of the RHS. Some manipulations yield the following sufficient condition for
misclassification:

$\displaystyle\underbrace{\frac{\max_{\beta}\lambda_{F}\quantity(\absolutevalue{\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]}+\absolutevalue{\widehat{{\bm{h}}}_{\beta,\alpha}[\beta]})}{\min_{\beta}\mathsf{CN}_{\alpha,\beta}}}_{{\textsf{SU}}/\mathsf{CN}\text{
ratio}}\cdot\underbrace{\max_{\gamma\in[k]}\absolutevalue{{\bm{x}}_{\mathsf{test}}[\gamma]}}_{\text{largest
label-defining
feature}}<\underbrace{\max_{\beta}Z^{(\beta)}}_{\text{normalized
contamination}}.$ (46)

Within the misclassification regimes in 3.1, Proposition A.1 implies that the
survival-to-contamination ratio ${\textsf{SU}}/\mathsf{CN}$ _shrinks_ at a
polynomial rate $n^{-w}$ for some $w>0$. By standard subgaussian maximal
inequalities, the largest label-defining feature is $O(\sqrt{\log(nk)})$ with
high probability. Gaussian anticoncentration implies that for some
$\beta\neq\alpha,\beta\in[k]$, $Z^{(\beta)}$ outcompetes the LHS, which is
bounded above by $n^{-w}$, with probability at least $\frac{1}{2}-o(1)$.
Hence, we conclude that the model will misclassify with rate at least
$\frac{1}{2}$ 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. 46 and one of the $Z^{(\beta)}$’s on the RHS instead of the maximum
$Z^{(\beta)}$. It’s not hard to see from the definition of $Z^{(\beta)}$ in
Eq. 29 that the $Z^{(\beta)}$ are jointly Gaussian. For intuition’s sake,
assuming the $Z^{(\beta)}$ were _independent_ , then $\max_{\beta}Z^{(\beta)}$
would outcompete with probability $(\frac{1}{2}-o(1))^{k-1}$.

In reality, the $Z^{(\beta)}$ are correlated, but we are able to show that the
maximum correlation between the $Z^{(\beta)}$ is $\frac{1}{2}+o(1)$ with high
probability. An application of Slepian’s lemma (Slepian [1962]) and some
explicit bounds on orthant probabilities (Pinasco et al. [2021]) implies that
$\max_{\beta}Z^{(\beta)}>0$ with probability at least
$1-\frac{1}{k^{1+o(1)}}$. An application of anticoncentration for Gaussian
maxima [Chernozhukov et al., 2015] implies that
$\max_{\beta}Z^{(\beta)}>n^{-w}$ with probability $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 are in the bi-level ensemble model (Definition 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 $\epsilon>0$, we have

$\displaystyle\Pr[\max_{\beta\in[k],\beta\neq\alpha}Z^{(\beta)}>n^{-u}]\geq
1-\Theta\quantity(\frac{1}{k^{1+o(1)}})-\epsilon$ (47)

for sufficiently large $n$ and any $u>0$.

##  Appendix 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-Wright Inequality

As established in Section 4, we need to use the Hanson-Wright inequality to
prove our tight characterization of generalization. For the sake of precision,
we explicitly state our definitions of subgaussian and subexponential which we
use throughout the rest of the paper.

The subgaussian norm $\|\xi\|_{\psi_{2}}$ of a random variable $\xi$ is
defined as in Rudelson and Vershynin [2013],

$\displaystyle\norm{\xi}_{\psi_{2}}$
$\displaystyle=\inf_{K>0}\quantity{K:\mathbb{E}\exp(\xi^{2}/K^{2})\leq 2}.$
(48)

The sub-exponential norm $\norm{\xi}_{\psi_{1}}$ is defined as in Vershynin
[2018, Definition 2.7.5]:

$\displaystyle\norm{\xi}_{\psi_{1}}$
$\displaystyle=\inf_{K>0}\quantity{K:\mathbb{E}\exp(\absolutevalue{\xi}/K)\leq
2}.$ (49)

We will occasionally need to use the following variant of Hanson-Wright for
nonsparse bilinear forms, first proved in Park et al. [2021].

######  Theorem B.1 (Hanson-Wright for bilinear forms without sparsity).

Let ${\bm{x}}=(X_{1},\ldots,X_{n})\in\mathbb{R}^{n}$ and
${\bm{y}}\in(Y_{1},\ldots,Y_{n})$ be random vectors such that the pairs
$(X_{i},Y_{i})$ are all independent of each other (however $X_{i}$ and $Y_{i}$
can be correlated). Assume also that $\mathbb{E}[X_{i}]=\mathbb{E}[Y_{i}]=0$
and $\max\quantity{\norm{X_{i}}_{\psi_{2}},\norm{Y_{i}}_{\psi_{2}}}\leq K$.
Then there exists an absolute constant $c>0$ such that for all
${\bm{M}}\in\mathbb{R}^{n\times n}$ and $\epsilon\geq 0$ we have

$\displaystyle\Pr\quantity[|{\bm{x}}^{\top}{\bm{M}}{\bm{y}}-\mathbb{E}[{\bm{x}}^{\top}{\bm{M}}{\bm{y}}]|>\epsilon]\leq
2\exp(-c\min\quantity{\frac{\epsilon^{2}}{K^{4}\norm{{\bm{M}}}_{F}^{2}},\frac{\epsilon}{K^{2}\norm{{\bm{M}}}_{2}}}).$
(50)

Finally, we restate our new version of Hanson-Wright for bilinear forms with
soft sparsity, which we prove in Appendix H.

See 4.2

###  B.2 Gram matrices and the Woodbury formula

In order to apply Hanson-Wright to the bilinear form
${\bm{x}}^{\top}{\bm{M}}{\bm{y}}$, we need to have a deterministic matrix
${\bm{M}}$ such that the hypotheses are satisfied. However, in our setting we
study bilinear forms such as ${\bm{z}}_{j}^{\top}\bm{A}^{-1}\bm{\Delta}y$.
Here, the inverse Gram matrix $\bm{A}^{-1}$ is not independent of
${\bm{z}}_{j}$ or $\bm{\Delta}y$, so we cannot simply condition on
$\bm{A}^{-1}$. The way around this is to cleverly decompose $\bm{A}^{-1}$
using the so-called Woodbury inversion formula (stated formally below), which
generalizes the leave-one-out trick and Sherman-Morrison used to study binary
classification in Muthukumar et al. [2021]. To that end, we will explicitly
decompose the Gram matrix
${\bm{A}}\triangleq\sum_{j\in[d]}\lambda_{j}{\bm{z}}_{j}{\bm{z}}_{j}^{\top}$
based on whether the features ${\bm{z}}_{j}$ 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 a minus sign to signify leaving out.
The $k$ label-defining features are represented with a subscript $k$, whereas
the $s-k$ favored but not label defining features are represented with a
subscript $F$. The rest of the $d-s$ unfavored features are represented with a
subscript $U$.

For notational convenience, we introduce some new notation for the weighted
features, as the superscript $w$ to denote weighted features is rather
cumbersome. We denote the weighted label-defining feature matrix by
${\bm{W}}_{k}\triangleq\matrixquantity[{\bm{w}}_{1}&\cdots&{\bm{w}}_{k}]\in\mathbb{R}^{n\times
k}$ , where the vectors
${\bm{w}}_{i}\triangleq\sqrt{\lambda_{i}}{\bm{z}}_{i}\in\mathbb{R}^{n}$ denote
the weighted observations for feature $i$. Define the unweighted label-
defining feature matrix
${\bm{Z}}_{k}\triangleq\matrixquantity[{\bm{z}}_{1}&\cdots&{\bm{z}}_{k}]\in\mathbb{R}^{n\times
k}$. Similarly, define
${\bm{W}}_{F}\triangleq\matrixquantity[{\bm{w}}_{k+1}&\cdots&{\bm{w}}_{s}]\in\mathbb{R}^{n\times(s-k)}$,
which contains the rest of the weighted favored features and the corresponding
unweighted version ${\bm{Z}}_{F}$.

Let ${\bm{A}}_{-k}\triangleq\sum_{i\not\in[k]}{\bm{w}}_{i}{\bm{w}}_{i}^{\top}$
denote the leave-$k$-out Gram matrix which removes the $k$ label-defining
features. Similarly, let
${\bm{A}}_{-F}\triangleq\sum_{i\not\in[s]\setminus[k]}{\bm{w}}_{i}{\bm{w}}_{i}^{\top}\in\mathbb{R}^{n\times
n}$ to denote leave-$(s-k)$-out Gram matrix which removes the favored but not
label-defining features. Finally, let
${\bm{A}}_{U}\triangleq\sum_{i\not\in[s]}{\bm{w}}_{i}{\bm{w}}_{i}^{\top}\in\mathbb{R}^{n\times
n}$ denote the leave-$s$-out matrix which only retains the unfavored features.
We will also sometimes write ${\bm{A}}_{-s}$ instead of ${\bm{A}}_{U}$ to
emphasize that the $s$ favored features have all been removed.

Define the so-called hat matrices by

$\displaystyle{\bm{H}}_{k}$
$\displaystyle\triangleq{\bm{W}}_{k}^{\top}{\bm{A}}_{-k}^{-1}{\bm{W}}_{k}\in\mathbb{R}^{k\times
k}$ (51) $\displaystyle{\bm{H}}_{F}$
$\displaystyle\triangleq{\bm{W}}_{F}^{\top}{\bm{A}}_{-F}^{-1}{\bm{W}}_{F}\in\mathbb{R}^{(s-k)\times(s-k)}.$
(52)

These hat matrices appear in the Woodbury inversion formula. For the sake of
notational compactness, define

$\displaystyle{\bm{M}}_{k}$
$\displaystyle\triangleq{\bm{W}}_{k}({\bm{I}}_{k}+{\bm{H}}_{k})^{-1}{\bm{W}}_{k}^{\top}\in\mathbb{R}^{n\times
n}$ (53) $\displaystyle{\bm{M}}_{F}$
$\displaystyle\triangleq{\bm{W}}_{F}({\bm{I}}_{s-k}+{\bm{H}}_{F})^{-1}{\bm{W}}_{F}^{\top}\in\mathbb{R}^{n\times
n}.$ (54)

The Woodbury inversion formula yields

$\displaystyle\bm{A}^{-1}$
$\displaystyle=({\bm{W}}_{k}{\bm{W}}_{k}^{\top}+{\bm{A}}_{-k})^{-1}$ (55)
$\displaystyle={\bm{A}}_{-k}^{-1}-{\bm{A}}_{-k}^{-1}{\bm{W}}_{k}({\bm{I}}_{k}+{\bm{H}}_{k})^{-1}{\bm{W}}_{k}^{\top}{\bm{A}}_{-k}^{-1}$
(56)
$\displaystyle={\bm{A}}_{-k}^{-1}-{\bm{A}}_{-k}^{-1}{\bm{M}}_{k}{\bm{A}}_{-k}^{-1}.$
(57)

Left multiplying (56) by ${\bm{W}}_{k}^{\top}$ yields

$\displaystyle{\bm{W}}_{k}^{\top}\bm{A}^{-1}$
$\displaystyle={\bm{W}}_{k}^{\top}{\bm{A}}_{-k}^{-1}-{\bm{H}}_{k}({\bm{I}}_{k}+{\bm{H}}_{k})^{-1}{\bm{W}}_{k}^{\top}{\bm{A}}_{-k}^{-1}$
(58)
$\displaystyle=({\bm{I}}_{k}-{\bm{H}}_{k}({\bm{I}}_{k}+{\bm{H}}_{k})^{-1}){\bm{W}}_{k}^{\top}{\bm{A}}_{-k}^{-1}$
(59)
$\displaystyle=({\bm{I}}_{k}+{\bm{H}}_{k})^{-1}{\bm{W}}_{k}^{\top}{\bm{A}}_{-k}^{-1}.$
(60)

We can derive completely analogous identities using ${\bm{A}}_{-F}^{-1}$
instead of ${\bm{A}}_{-k}^{-1}$. The above exposition is summarized by the
following lemma.

######  Lemma B.2.

We have

$\displaystyle{\bm{W}}_{k}^{\top}\bm{A}^{-1}\bm{\Delta}y$
$\displaystyle=({\bm{I}}_{k}+{\bm{H}}_{k})^{-1}{\bm{W}}_{k}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y$
(61) $\displaystyle{\bm{W}}_{F}^{\top}\bm{A}^{-1}\bm{\Delta}y$
$\displaystyle=({\bm{I}}_{s-k}+{\bm{H}}_{F})^{-1}{\bm{W}}_{F}^{\top}{\bm{A}}_{-F}^{-1}\bm{\Delta}y.$
(62)

Lemma B.2 is quite powerful. Indeed, consider the action of the linear
operator ${\bm{W}}_{k}^{\top}\bm{A}^{-1}:\mathbb{R}^{n}\to\mathbb{R}^{k}$ on
$\bm{\Delta}y$. The action is identical to that of the linear operator
${\bm{W}}_{k}^{\top}{\bm{A}}_{-k}^{-1}:\mathbb{R}^{n}\to\mathbb{R}^{k}$, up to
some invertible transformation. This new linear operator is nice because
${\bm{A}}_{-k}^{-1}$ is independent of ${\bm{W}}_{k}$ and $\bm{\Delta}y$, 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 $({\bm{I}}_{k}+{\bm{H}}_{k})^{-1}$ act? Our
general strategy is to show that ${\bm{H}}_{k}$ is itself close to a scaled
identity matrix, i.e. ${\bm{H}}_{k}\approx\nu{\bm{I}}_{k}$ for an
appropriately defined $\nu$. Then for any $i\in[k]$, we have that

${\bm{w}}_{i}^{\top}\bm{A}^{-1}\bm{\Delta}y\approx(1+\nu)^{-1}{\bm{w}}_{i}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y.$

Of course, there will be some error in this approximation, as ${\bm{H}}_{k}$
is not _exactly_ equal to $\nu{\bm{I}}_{k}$. Nevertheless, we can bound away
the error that arises from this approximation.

###  B.3 Concentration of spectrum

As foreshadowed in the previous section, we will leverage the fact that the
hat matrices such as ${\bm{H}}_{k}$ are close to a 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, we present the following standard
characterization of the spectrum of a standard Wishart matrix, which is
Equation 2.3 in Rudelson and Vershynin [2010].

######  Lemma B.3 (Concentration of spectrum for Wishart matrices).

Let ${\bm{M}}\in\mathbb{R}^{M\times m}$ with $M>m$ be a real matrix with iid
$N(0,1)$ entries. Then for any $\epsilon\geq 0$, we have with probability at
least $1-2e^{-\epsilon^{2}/2}$ that

$\sqrt{M}-\sqrt{m}-\epsilon\leq\sigma_{\min{}}({\bm{M}})\leq\sigma_{\max{}}({\bm{M}})\leq\sqrt{M}+\sqrt{m}+\epsilon.$
(63)

In other words, the singular values of ${\bm{M}}$ satisfy subgaussian
concentration.

Since $\mu_{m}({\bm{M}}^{\top}{\bm{M}})=\sigma_{\min{}}({\bm{M}})^{2}$ and
$\mu_{1}({\bm{M}}^{\top}{\bm{M}})=\sigma_{\max{}}({\bm{M}})^{2}$, we can
conclude that if $m=o(M)$, then for any $\epsilon>0$ we have

$M-2\sqrt{Mm}-\epsilon+o(\sqrt{Mm})\leq\mu_{m}({\bm{M}}^{\top}{\bm{M}})\leq\mu_{1}({\bm{M}}^{\top}{\bm{M}})\leq
M+2\sqrt{Mm}+\epsilon+o(\sqrt{Mm}),$ (64)

with probability at least $1-2e^{-\epsilon^{2}/2}$.

On the other hand, consider ${\bm{M}}{\bm{M}}^{\top}\in\mathbb{R}^{M\times
M}$. Its spectrum is just that of
${\bm{M}}^{\top}{\bm{M}}\in\mathbb{R}^{m\times m}$ 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 Section B.2. Let us summarize some convenient forms of
these results; their proofs are deferred to Appendix I.

######  Proposition B.4 (Gram matrices have a flat spectrum).

Recall that
${\bm{A}}_{U}={\bm{A}}_{-s}=\sum_{j>s}\lambda_{j}{\bm{z}}_{j}{\bm{z}}_{j}^{\top}\in\mathbb{R}^{n\times
n}$ is the unfavored Gram matrix and
${\bm{A}}_{-k}=\sum_{j>k}\lambda_{j}{\bm{z}}_{j}{\bm{z}}_{j}^{\top}\in\mathbb{R}^{n\times
n}$ is the leave-$k$-out Gram matrix.

Then the following hold with probability at least $1-2e^{-n}-2e^{-\sqrt{n}}$,

  1. (a)

For all $i\in[n]$, we have $\mu_{i}({\bm{A}}_{U})=n^{p}(1\pm
O(n^{-\kappa_{\ref{kappa_au}}}))$.

  2. (b)

For all $i\in[s-k]$, we have

$\displaystyle\mu_{i}({\bm{A}}_{-k})=(1+\mu^{-1})n^{p}(1\pm
O(n^{-\kappa_{\ref{kappa_ak_spiked}}})),$ (65)

where $\kappa_{\ref{kappa_ak_spiked}}$ is a positive constant. Moreover, for
all $i\in[n]\setminus[s-k]$, we have

$\displaystyle\mu_{i}({\bm{A}}_{-k})=n^{p}(1\pm
O(n^{-\kappa_{\ref{kappa_au}}})),$ (66)

where $\kappa_{\ref{kappa_au}}$ is a positive constant.

As a simple corollary, we can obtain the following cruder bounds on the trace
and spectral norm of ${\bm{A}}_{-k}^{-1}$ and ${\bm{A}}_{-s}^{-1}$.

######  Corollary B.5 (Trace and spectral norm of ${\bm{A}}_{-k}^{-1}$).

In the bi-level model, with probability at least $1-2e^{-n}$, we have

$\displaystyle\Tr({\bm{A}}_{U}^{-1})$ $\displaystyle=n^{1-p}(1\pm
O(n^{-\kappa_{\ref{kappa_au}}}))\sqrt{\log k}$ (67)
$\displaystyle\Tr({\bm{A}}_{-k}^{-1})$ $\displaystyle=n^{1-p}(1\pm
O(n^{-\kappa_{\ref{kappa_akinv_trace}}}))\sqrt{\log k}$ (68)

and

$\max\quantity{\norm{{\bm{A}}_{-k}^{-1}}_{2},\norm{{\bm{A}}_{U}^{-1}}_{2}}\leq
c_{\ref{const_akinv_spectral_norm}}n^{-p},$ (69)

where $c_{\ref{const_akinv_spectral_norm}}$, $\kappa_{\ref{kappa_au}}$, and
$\kappa_{\ref{kappa_akinv_trace}}$ are all positive constants.

###### Proof.

We prove the claim for ${\bm{A}}_{-k}^{-1}$; the proof for ${\bm{A}}_{U}^{-1}$
is similar or easier because ${\bm{A}}_{U}^{-1}$ has a flat spectrum
(Proposition B.4).

If $q+r<1$, the upper bound for the spectral norm similarly follows. For the
trace bounds, we can apply Proposition B.4, we have

$\displaystyle\Tr({\bm{A}}_{-k}^{-1})$
$\displaystyle=(n-n^{r}+n^{t})n^{-p}(1\pm
O(n^{-\kappa_{\ref{kappa_au}}}))+(n^{r}-n^{t})\cdot(1+\mu^{-1})n^{-p}(1\pm
O(n^{-\kappa_{\ref{kappa_ak_spiked}}}))$ (70) $\displaystyle=n^{1-p}(1\pm
O(n^{-\kappa_{\ref{kappa_akinv_intermediate}}}))$ (71)

where

$\kappa_{1}=\min\quantity{r-1,2-q-2r}>0,$

as $q+2r<2(q+r)<2$ by assumption.

On the other hand, the claim is obviously true when $q+r>1$, as the entire
spectrum of ${\bm{A}}_{-k}^{-1}$ is $(1\pm
O(n^{-\kappa_{\ref{kappa_akinv_regression_fails}}}))n^{-p}$ with an
appropriately defined positive constant $\kappa_{2}$. The spectral norm bound
follows by defining $c_{2}$ to be any positive constant greater than 1 which
absorbs the $o(1)$ deviation terms in the spectrum.

The proof concludes by setting
$\kappa_{3}=\min\quantity{\kappa_{\ref{kappa_akinv_intermediate}},\kappa_{\ref{kappa_akinv_regression_fails}}}$.
∎

Finally, we have the following proposition which controls the spectrum of hat
matrices such as
${\bm{H}}_{k}\triangleq{\bm{W}}_{k}^{\top}{\bm{A}}_{-k}^{-1}{\bm{W}}_{k}\in\mathbb{R}^{k\times
k}$. The intuition is that even though the spectrum of ${\bm{A}}_{-k}^{-1}$
may be spiked, the spectrum of
${\bm{W}}_{k}^{\top}{\bm{A}}_{-k}^{-1}{\bm{W}}_{k}$ is ultimately flat because
we are taking an extremely low dimensional projection which is unlikely to see
significant contribution from the spiked portion of ${\bm{A}}_{-k}^{-1}$.

In fact, we can prove a more general statement, which will be useful for us in
the proof. Let $\varnothing\neq T\subseteq S\subseteq[s]$; here $T$ and $S$
index nonempty subsets of the $s$ favored features. Then we can define
${\bm{W}}_{T}$ to be the matrix of weighted features in $T$ and the
leave-$T$-out Gram matrix

$\displaystyle{\bm{A}}_{-T}\triangleq\sum_{j\not\in
T}\lambda_{j}{\bm{z}}_{j}{\bm{z}}_{j}^{\top}.$ (72)

Now define the $(T,S)$ hat matrix as
${\bm{H}}_{T,S}\triangleq{\bm{W}}_{T}^{\top}{\bm{A}}_{-S}^{-1}{\bm{W}}_{T}$.
Evidently we have ${\bm{H}}_{k}={\bm{H}}_{[k],[k]}$, so our notion is more
general. The full proof is deferred to Appendix I.

######  Proposition B.6 (Generalized hat matrices are flat).

Assume we are in the bi-level ensemble Definition 1. For any nonempty
$T\subseteq S\subseteq[s]$, with probability at least
$1-2e^{-\sqrt{n}}-2e^{-n}$, we have all the eigenvalues tightly controlled:

$\displaystyle\mu_{i}(({\bm{I}}_{\absolutevalue{T}}+{\bm{H}}_{T,S})^{-1})=\min\quantity{\mu,1}(1\pm
c_{T,S}n^{-\kappa_{\ref{kappa_hatts_final}}}).$ (73)

where $c_{T,S}$ and $\kappa_{\ref{kappa_hatts_final}}$ are positive constants
that depend on $\absolutevalue{T}$ and $\absolutevalue{S}$.

##  Appendix 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
${\bm{w}}_{i}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y$ rather than
${\bm{w}}_{i}^{\top}\bm{A}^{-1}\bm{\Delta}y$. Since ${\bm{A}}_{-k}^{-1}$ is
independent of ${\bm{W}}_{k}$ and $\bm{\Delta}y$, we can condition on
${\bm{A}}_{-k}^{-1}$ and then apply Hanson-Wright (Theorem 4.2) to these
bilinear forms for every realization of ${\bm{A}}_{-k}^{-1}$. 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.

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 [Subramanian et al., 2022].

######  Proposition C.1.

For any distinct $\alpha,\beta\in[k]$, we have

$\displaystyle\frac{1}{\sqrt{\pi\ln 2}}\cdot\frac{n}{k}\cdot\sqrt{\ln
k}\leq\mathbb{E}[{\bm{z}}_{\alpha}^{\top}{\bm{y}}_{\alpha}]\leq\sqrt{2}\cdot\frac{n}{k}\cdot\sqrt{\ln
k}$ (74)

and

$\displaystyle-\sqrt{2}\cdot\frac{n}{k}\cdot\frac{1}{k-1}\cdot\sqrt{\ln
k}\leq\mathbb{E}[{\bm{z}}_{\alpha}^{\top}{\bm{y}}_{\beta}]\leq-\frac{1}{\sqrt{\pi\ln
2}}\cdot\frac{n}{k}\cdot\frac{1}{k-1}\cdot\sqrt{\ln k}$ (75)

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\in[d]$ and $\bm{\Delta}y={\bm{y}}_{\alpha}-{\bm{y}}_{\beta}$ where
$\alpha,\beta\in[k]$ and $\beta\neq\alpha$. Let
${\bm{M}}\in\mathbb{R}^{n\times n}$ be a (random) matrix which is independent
of ${\bm{z}}_{i}$ and $\bm{\Delta}y$. Then conditioned on ${\bm{M}}$, with
probability at least $1-1/nk$,

$\absolutevalue{{\bm{z}}_{i}^{\top}{\bm{M}}\bm{\Delta}y-\mathbb{E}[{\bm{z}}_{i}^{\top}{\bm{M}}\bm{\Delta}y|{\bm{M}}]}\leq
c_{\ref{chansonwright}}\sqrt{\frac{n}{k}}\norm{{\bm{M}}}_{2}\sqrt{\log(nk)},$

and the same holds with $\bm{\Delta}y$ replaced with ${\bm{y}}_{\alpha}$.
Here, $c_{\ref{chansonwright}}$ is an appropriately chosen universal positive
constant.

Moreover, we have

  1. (1)

For any distinct $\alpha,\beta\in[k]$, we have

$\displaystyle\mathbb{E}[{\bm{z}}_{\alpha}^{\top}{\bm{M}}\bm{\Delta}y|{\bm{M}}]$
$\displaystyle=c_{\ref{const_alpha}}\frac{\sqrt{\log
k}}{k}\tr({\bm{M}})=-\mathbb{E}[{\bm{z}}_{\beta}^{\top}{\bm{M}}\bm{\Delta}y]$
(76)
$\displaystyle\mathbb{E}[{\bm{z}}_{\alpha}^{\top}{\bm{M}}{\bm{y}}_{\alpha}|{\bm{M}}]$
$\displaystyle=c_{\ref{const_ya}}\frac{\sqrt{\log k}}{k}\tr({\bm{M}}),$ (77)

where $c_{\ref{const_alpha}}$ and $c_{\ref{const_ya}}$ are positive constants.

  2. (2)

For $i\in[d]\setminus\quantity{\alpha,\beta}$, we have

$\displaystyle\mathbb{E}[{\bm{z}}_{i}^{\top}{\bm{M}}\bm{\Delta}y|{\bm{M}}]$
$\displaystyle=0.$ (78)

  3. (3)

For $i\in[d]\setminus\quantity{\alpha}$, we have

$\displaystyle\mathbb{E}[{\bm{z}}_{i}^{\top}{\bm{M}}{\bm{y}}_{\alpha}|{\bm{M}}]$
$\displaystyle=-c_{\ref{const_zi_ya}}\frac{\sqrt{\log k}}{k(k-1)},$ (79)

where $c_{\ref{const_zi_ya}}$ is a positive constant.

###### Proof.

Let us check the conditions for our new variant of Hanson-Wright with soft
sparsity (Theorem 4.2). We want to apply it to the random vectors
$({\bm{z}}_{i},\bm{\Delta}y)=({\bm{z}}_{i}[j],\bm{\Delta}y[j])_{j=1}^{n}$.
Some of the hypotheses are immediate by definition. Evidently,
$({\bm{z}}_{i}[j],\bm{\Delta}y[j])$ are independent across $j$, and are mean
zero. Since ${\bm{z}}_{i}[j]\sim N(0,1)$, it is subgaussian with parameter at
most $K=2$. For the bounded and soft sparsity assumption, we clearly have
$\absolutevalue{\bm{\Delta}y[j]}\leq 1$ and ${\bm{y}}_{\alpha}[j]\leq 1$
almost surely. Also, since $\bm{\Delta}y[j]^{2}\sim\mathsf{Ber}(\frac{2}{k})$,
we have $\mathbb{E}[\bm{\Delta}y[j]^{2}]=\frac{2}{k}$. Similarly,
$\mathbb{E}[{\bm{y}}_{\alpha}[j]^{2}]=\frac{1}{k}(1-\frac{1}{k})^{2}+(1-\frac{1}{k})\frac{1}{k^{2}}\leq\frac{2}{k}$.

The more complicated condition is the subgaussianity of ${\bm{z}}_{i}[j]$
conditioned on the value of $\bm{\Delta}y[j]$ or ${\bm{y}}_{\alpha}[j]$.
Regardless of whether we’re conditioning on $\bm{\Delta}y$ or
${\bm{y}}_{\alpha}$, it suffices to instead prove that ${\bm{z}}_{i}[j]$ is
subgaussian conditioned on whether feature $i$ won the competition for
datapoint $j$. First, suppose $i$ won, i.e. ${\bm{y}}^{\mathsf{oh}}_{i}[j]=1$.
Then the Borell-TIS inequality [Adler et al., 2007, Theorem 2.1.1] implies
that ${\bm{z}}_{i}[j]$ satisfies a subgaussian tail inequality. By the
equivalent conditions for subgaussianity Vershynin [2018, Proposition 2.5.2],
it follows that
${\bm{z}}_{i}[j]-\mathbb{E}[{\bm{z}}_{i}[j]|{\bm{y}}^{\mathsf{oh}}_{i}[j]=1]$
conditionally has subgaussian norm bounded by some absolute constant $K$. If
$i$ doesn’t win (or doesn’t participate in the competition), then Proposition
D.2 in Subramanian et al. [2022] implies that
${\bm{z}}_{i}[j]-\mathbb{E}[{\bm{z}}_{i}[j]|{\bm{y}}^{\mathsf{oh}}_{i}[j]=0]$
conditionally has subgaussian norm bounded by $6$.

Finally, since ${\bm{M}}$ is independent of ${\bm{z}}_{i}$ and $\bm{\Delta}y$,
we can condition on ${\bm{M}}$ and apply Theorem 4.2 to the bilinear form for
every realization of ${\bm{M}}$.

Hence, we conclude that with probability at least $1-1/nk$ we have

$\displaystyle\absolutevalue{{\bm{z}}_{i}^{\top}{\bm{M}}\bm{\Delta}y-\mathbb{E}[{\bm{z}}_{i}^{\top}{\bm{M}}\bm{\Delta}y|{\bm{M}}]}\leq
c_{\ref{chansonwright}}\sqrt{\frac{n}{k}}\norm{{\bm{M}}}_{2}\sqrt{\log(nk)},$
(80)

where $c_{3}$ is an appropriately chosen absolute constant based on $K$ and
the constant $c$ defined in Theorem 4.2.

Now we can compute
$\mathbb{E}[{\bm{z}}_{i}^{\top}{\bm{M}}\bm{\Delta}y|{\bm{M}}]$ to prove the
rest of the theorem. If $i=\alpha$, we have

$\mathbb{E}[{\bm{z}}_{\alpha}^{\top}{\bm{M}}\bm{\Delta}y|{\bm{M}}]=\tr({\bm{M}}\mathbb{E}[\bm{\Delta}y{\bm{z}}_{\alpha}^{\top}]).$

Let us now compute $\mathbb{E}[\bm{\Delta}y{\bm{z}}_{\alpha}^{\top}]$. From
Eq. 74 in Proposition C.1, we have
$\mathbb{E}[{\bm{y}}_{\alpha}{\bm{z}}_{\alpha}^{\top}]=c_{\ref{const_ya}}\frac{\sqrt{\log
k}}{k}{\bm{I}}_{n}$, where $\frac{1}{\sqrt{\pi\log 2}}\leq c_{4}\leq\sqrt{2}$.
Similarly, we have
$\mathbb{E}[{\bm{y}}_{\beta}{\bm{z}}_{\alpha}^{\top}]=-c_{\ref{const_zi_ya}}\frac{\sqrt{\log
k}}{k(k-1)}{\bm{I}}_{n}$ where $\frac{1}{\sqrt{\pi\log 2}}\leq
c_{5}\leq\sqrt{2}$. It follows that
$\mathbb{E}[\bm{\Delta}y{\bm{z}}_{\alpha}^{\top}]=\Theta\quantity(\frac{\sqrt{\log
k}}{k}){\bm{I}}_{n}$.

For $i\in[d]\setminus\quantity{\alpha,\beta}$, by symmetry we obtain
$\mathbb{E}[{\bm{y}}_{\alpha}{\bm{z}}_{i}^{\top}]=\mathbb{E}[{\bm{y}}_{\beta}{\bm{z}}_{i}^{\top}]$.
This implies
$\mathbb{E}[\bm{\Delta}y{\bm{z}}_{i}^{\top}]=\mathbb{E}[{\bm{y}}_{\alpha}{\bm{z}}_{i}^{\top}]-\mathbb{E}[{\bm{y}}_{\beta}{\bm{z}}_{i}^{\top}]=0$,
so we obtain

$\displaystyle\mathbb{E}[{\bm{z}}_{i}^{\top}{\bm{M}}\bm{\Delta}y|{\bm{M}}]$
$\displaystyle=\tr({\bm{M}}\mathbb{E}[\bm{\Delta}y{\bm{z}}_{i}^{\top}])$ (81)
$\displaystyle=0.$ (82)

∎

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\in[k]$, we have with probability at least
$1-O(1/nk)$ that

$\absolutevalue{{\bm{z}}_{i}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y-\mathbb{E}[{\bm{z}}_{i}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y]}\leq
c_{\ref{const_asymptotic_bilinear}}n^{\frac{1-t}{2}-p}\sqrt{\log(nk)}.$

Moreover, we have

  1. (1)

For any distinct $\alpha,\beta\in[k]$,

$\displaystyle\mathbb{E}[{\bm{z}}_{\alpha}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y]=c_{\ref{const_alpha}}n^{1-t-p}(1\pm
O(n^{-\kappa_{\ref{kappa_akinv_trace}}}))\sqrt{\log
k}=-\mathbb{E}[{\bm{z}}_{\beta}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y]$ (83)

The same statements hold (with different constants) if we replace
${\bm{A}}_{-k}^{-1}$ with ${\bm{A}}_{-s}^{-1}$.

###### Proof.

From Corollary B.5, we have $\norm{{\bm{A}}_{-k}^{-1}}_{2}\leq
c_{\ref{const_asymptotic_bilinear}}n^{-p}$, where $c_{6}$ is an appropriately
chosen universal positive constant based on $c_{\ref{chansonwright}}$. Recall
that ${\bm{A}}_{-k}$ is obtained by removing the $k$ label-defining features,
so in particular ${\bm{A}}_{-k}^{-1}$ is independent of
$({\bm{z}}_{i},\bm{\Delta}y)$ for $i\in[k]$. Hence, the conditions for Lemma
C.2 are satisfied. Then applying the union bound for the spectral norm bound
on ${\bm{A}}_{-k}^{-1}$, we see that with probability at least $1-O(1/nk)$,
the deviation term from Hanson-Wright is at most
$c_{\ref{const_asymptotic_bilinear}}n^{\frac{1}{2}-p}\sqrt{\log(nk)}$.

We now turn to calculating the asymptotic scalings for the expectations. From
Lemma C.2, we know that
$\mathbb{E}[{\bm{z}}_{\alpha}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y|{\bm{A}}_{-k}^{-1}]=c_{\ref{const_alpha}}\frac{\sqrt{\log
k}}{k}\tr({\bm{A}}_{-k}^{-1})$. Applying the high probability bound on
$\tr({\bm{A}}_{-k}^{-1})$ from Corollary B.5, we obtain that with probability
at least $1-O(1/nk)$ that

$\displaystyle-\mathbb{E}[{\bm{z}}_{\beta}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y]=\mathbb{E}[{\bm{z}}_{\alpha}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y]$
$\displaystyle=c_{\ref{const_alpha}}n^{-t}n^{1-p}(1\pm
O(n^{-\kappa_{\ref{kappa_akinv_trace}}}))\sqrt{\log k}$ (84)
$\displaystyle=c_{\ref{const_alpha}}n^{1-t-p}(1\pm
O(n^{-\kappa_{\ref{kappa_akinv_trace}}}))\sqrt{\log k}$ (85)

where in the second line we have applied Corollary B.5 and $c_{7}$ is an
appropriately chosen positive constant. This proves (83). ∎

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 in
the survival and contamination analysis.

######  Proposition C.4 (Worst-case bound based on Hanson-Wright).

Let $T\subseteq[s]$ be a subset of favored features such that
$\quantity{\alpha,\beta}\subseteq T$. Assume that $\absolutevalue{T}=n^{\tau}$
for some $\tau\leq r$. Then with probability at least $1-O(1/nk)$, we have

$\displaystyle\norm{{\bm{Z}}_{T}^{\top}{\bm{A}}_{-T}^{-1}\bm{\Delta}y}_{2}\leq
c_{\ref{const_norm_bilinear}}(n^{1-t-p}+n^{\frac{1+\tau-t}{2}-p})\sqrt{\log(nk\absolutevalue{T})}.$
(86)

###### Proof.

WLOG, suppose $\alpha=1$ and $\beta=2$. By Corollary C.3 we have with
probability at least $1-1/n$ that

$\displaystyle\absolutevalue{{\bm{Z}}_{T}^{\top}{\bm{A}}_{-T}^{-1}\bm{\Delta}y}\leq\matrixquantity[c_{\ref{const_alpha}}n^{1-t-p}\sqrt{\log
k}\\\ c_{\ref{const_alpha}}n^{1-t-p}\sqrt{\log k}\\\
c_{\ref{const_asymptotic_bilinear}}n^{\frac{1-t}{2}-p}\sqrt{\log(nk)}\\\
\vdots\\\
c_{\ref{const_asymptotic_bilinear}}n^{\frac{1-t}{2}-p}\sqrt{\log(nk)}].$ (87)

Hence, the norm of this vector is at most

$\displaystyle\norm{{\bm{Z}}_{T}^{\top}{\bm{A}}_{-T}^{-1}\bm{\Delta}y}_{2}$
$\displaystyle\leq 2c_{\ref{const_alpha}}n^{1-t-p}\sqrt{\log
k}+n^{\frac{\tau}{2}}c_{\ref{const_asymptotic_bilinear}}n^{\frac{1-t}{2}-p}\sqrt{\log(nk)}$
(88) $\displaystyle\leq
c_{\ref{const_norm_bilinear}}(n^{1-t-p}+n^{\frac{1+\tau-t}{2}-p})\sqrt{\log(nk)},$
(89)

where $c_{8}$ is a positive constant.

∎

##  Appendix D Bounding the survival

Recall that the relative survival was defined to be
$\lambda_{F}\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]=\lambda_{F}{\bm{z}}_{\alpha}^{\top}\bm{A}^{-1}\bm{\Delta}y$.
The strategy is to apply our variant of Hanson-Wright to
${\bm{z}}_{\alpha}^{\top}\bm{A}^{-1}\bm{\Delta}y$. Unfortunately,
$\bm{A}^{-1}$ is not independent of ${\bm{z}}_{\alpha}$ or $\bm{\Delta}y$, 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-Wright. Let us now recall Section
4.3 for reference.

*

###### Proof.

Recall that
$\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]={\bm{z}}_{\alpha}^{\top}\bm{A}^{-1}\bm{\Delta}y$.
We first observe that for $i\in[k]$, the dependence between $\bm{A}^{-1}$ and
${\bm{z}}_{i}$ as well as $\bm{A}^{-1}$ and $\bm{\Delta}y$ only comes through
the $k$ label defining features. Hence, we can use the Woodbury identity to
extract out the independent portions of $\bm{A}^{-1}$.

Indeed, our “push through” lemma for Woodbury (Lemma B.2) and concentration of
the hat matrix (Proposition B.6) implies that with extremely high probability

$\displaystyle{\bm{Z}}_{k}^{\top}\bm{A}^{-1}\bm{\Delta}y$
$\displaystyle=({\bm{I}}_{k}+{\bm{H}}_{k})^{-1}{\bm{Z}}_{k}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y$
(90)
$\displaystyle=\min\quantity{\mu,1}({\bm{I}}_{k}+{\bm{E}}){\bm{Z}}_{k}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y,$
(91)

where $\norm{{\bm{E}}}_{2}=O(n^{-\kappa_{\ref{kappa_hatts_final}}})$.

Let ${\bm{u}}_{\alpha}\in\mathbb{R}^{k}$ denote the $\alpha$th row vector in
${\bm{E}}$, and let ${\bm{u}}_{\alpha}^{-}\in\mathbb{R}^{k-1}$ denote the
subvector of ${\bm{u}}_{\alpha}$ without index $\alpha$. By reading off the
$\alpha$th row of Eq. 91, we see that

$\displaystyle{\bm{z}}_{\alpha}^{\top}\bm{A}^{-1}\bm{\Delta}y$
$\displaystyle=\min\quantity{\mu,1}({\bm{z}}_{\alpha}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y+\expectationvalue{{\bm{u}}_{\alpha},{\bm{Z}}_{k}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y})$
(92)

Since
$\norm{{\bm{u}}_{\alpha}}_{2}\leq\norm{{\bm{E}}}_{2}=O(n^{-\kappa_{\ref{kappa_hatts_final}}})$,
it follows from Cauchy-Schwarz that

$\displaystyle\absolutevalue{{\bm{z}}_{\alpha}^{\top}\bm{A}^{-1}\bm{\Delta}y-\min\quantity{\mu,1}{\bm{z}}_{\alpha}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y}\leq\min\quantity{\mu,1}O(n^{-\kappa_{\ref{kappa_hatts_final}}})\norm{{\bm{Z}}_{k}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y}_{2}.$
(93)

Let us pause for a moment and interpret Eq. 93. The term
$\min\quantity{\mu,1}$ is merely capturing the difference in behavior when
regression works and fails; if regression works ($q+r<1$) then it becomes
$\mu$, and if regression fails ($q+r>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 $\mu$. The RHS of Eq. 93 is an error term, capturing how differently
${\bm{z}}_{\alpha}^{\top}\bm{A}^{-1}\bm{\Delta}y$ behaves from the expected
behavior
$\min\quantity{\mu,1}{\bm{z}}_{\alpha}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y$.

Let us now bound the error term. From Proposition C.4 we have with probability
at least $1-O(1/nk)$ that

$\displaystyle\norm{{\bm{Z}}_{k}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y}_{2}$
$\displaystyle\leq
c_{\ref{const_norm_bilinear}}(n^{1-t-p}+n^{\frac{1}{2}-p})\sqrt{\log(nk^{2})}.$
(94)

Let us do casework on $t$. For $t<\frac{1}{2}$, we have $\frac{1}{2}-p<1-t-p$,
so we conclude that the error term is $\min\quantity{\mu,1}O(n^{1-t-p}\cdot
n^{-\kappa_{\ref{kappa_worst_case_error}}})\sqrt{\log(nk^{2})}$, where
$\kappa_{4}$ is a positive constant.

On the other hand, our Hanson-Wright calculations imply (Corollary C.3) that
with probability at least $1-O(1/nk)$ that

$\displaystyle\absolutevalue{{\bm{z}}_{\alpha}^{\top}{\bm{A}}_{-k}^{-1}\bm{\Delta}y-c_{\ref{const_alpha}}n^{1-t-p}(1\pm
O(n^{-\kappa_{\ref{kappa_akinv_trace}}}))\sqrt{\log k}}\leq
c_{\ref{const_asymptotic_bilinear}}n^{\frac{1}{2}-p}\sqrt{\log(nk)}.$

Again, since $t<\frac{1}{2}$, the deviation term is $o(n^{1-t-p})\sqrt{\log
k}$.

Hence we conclude that with probability $1-O(1/nk)$ we have

$\displaystyle{\bm{z}}_{\alpha}^{\top}\bm{A}^{-1}\bm{\Delta}y=c_{\ref{const_alpha}}\min\quantity{\mu,1}n^{1-t-p}(1\pm
O(n^{-\kappa_{\ref{kappa_survival}}}))\sqrt{\log k},$

where $\kappa_{5}$ is a positive constant.

Completely analogous logic handles the bounds for
${\bm{z}}_{\beta}^{\top}\bm{A}^{-1}\bm{\Delta}y$. Let us now return back to
the quantity of interest,
$\lambda_{F}\widehat{{\bm{h}}}_{\alpha,\beta}[\alpha]$. We can compute

$\displaystyle\lambda_{F}{\bm{z}}_{\alpha}^{\top}\bm{A}^{-1}\bm{\Delta}y$
$\displaystyle=n^{p-q-r}\cdot
c_{\ref{const_alpha}}\min\quantity{\mu,1}n^{1-t-p}(1\pm
O(n^{-\kappa_{\ref{kappa_survival}}}))\sqrt{\log k}$
$\displaystyle=c_{\ref{const_alpha}}\mu^{-1}\min\quantity{\mu,1}n^{-t}(1\pm
O(n^{-\kappa_{\ref{kappa_survival}}}))\sqrt{\log k}$
$\displaystyle=c_{\ref{const_alpha}}\min\quantity{1,\mu^{-1}}n^{-t}(1\pm
O(n^{-\kappa_{\ref{kappa_survival}}}))\sqrt{\log k}.$

On the other hand, if $t\geq\frac{1}{2}$ the error terms all dominate, and we
replace $n^{1-t-p}$ with $n^{\frac{1}{2}-p}$ everywhere. We conclude that with
probability at least $1-O(1/nk)$,

$\displaystyle\absolutevalue{{\bm{z}}_{\alpha}^{\top}\bm{A}^{-1}\bm{\Delta}y}$
$\displaystyle\leq
c_{\ref{const_rel_survival_upper}}\min\quantity{\mu,1}n^{\frac{1}{2}-p}\sqrt{\log(nk)},$
(95)

where $c_{9}$ is a positive constant. Plugging in the scaling for
$\lambda_{F}$ yields the desired result. ∎

##  Appendix E Bounding the contamination

In this section we give a tight analysis of the contamination term. First, we
rewrite the squared contamination term and separate it out into the
contamination from the $k-2$ label-defining features which are not $\alpha$ or
$\beta$, the rest of the $s-k$ favored features, and the remaining $d-s$
unfavored features. From Eq. 28, we have

$\displaystyle\mathsf{CN}_{\alpha,\beta}^{2}$
$\displaystyle=\sum_{j\in[d]\setminus\quantity{\alpha,\beta}}\lambda_{j}^{2}({\bm{z}}_{j}^{\top}\bm{A}^{-1}\bm{\Delta}y)^{2}$
(96)
$\displaystyle=\bm{\Delta}y^{\top}\bm{A}^{-1}\quantity(\sum_{j\in[d]\setminus\quantity{\alpha,\beta}}\lambda_{j}^{2}{\bm{z}}_{j}{\bm{z}}_{j}^{\top})\bm{A}^{-1}\bm{\Delta}y$
(97)
$\displaystyle=\underbrace{\bm{\Delta}y^{\top}\bm{A}^{-1}\quantity(\sum_{j\in[k]\setminus\quantity{\alpha,\beta}}\lambda_{j}^{2}{\bm{z}}_{j}{\bm{z}}_{j}^{\top})\bm{A}^{-1}\bm{\Delta}y}_{\triangleq\mathsf{CN}_{\alpha,\beta,L}^{2}}+\underbrace{\bm{\Delta}y^{\top}\bm{A}^{-1}\quantity(\sum_{j\in[s]\setminus[k]}\lambda_{j}^{2}{\bm{z}}_{j}{\bm{z}}_{j}^{\top})\bm{A}^{-1}\bm{\Delta}y}_{\triangleq\mathsf{CN}_{\alpha,\beta,F}^{2}}$
(98)
$\displaystyle\quad\quad+\underbrace{\bm{\Delta}y^{\top}\bm{A}^{-1}\quantity(\sum_{j>s}\lambda_{j}^{2}{\bm{z}}_{j}{\bm{z}}_{j}^{\top})\bm{A}^{-1}\bm{\Delta}y}_{\triangleq\mathsf{CN}_{\alpha,\beta,U}^{2}}.$
(99)

Here, $\mathsf{CN}_{\alpha,\beta,L}$ corresponds to contamination from label
defining features, $\mathsf{CN}_{\alpha,\beta,F}$ corresponds to contamination
from favored features, and $\mathsf{CN}_{\alpha,\beta,U}$ 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 to bound each of them, although Hanson-Wright and Woodbury
are central to all of the arguments. In Section E.1 we prove the upper bound
on $\mathsf{CN}_{\alpha,\beta,L}+\mathsf{CN}_{\alpha,\beta,F}$; in Section E.2
we prove the lower bound. Finally, in Section E.3 we bound
$\mathsf{CN}_{\alpha,\beta,U}$. After putting these bounds together, we will
obtain the main bounds on the contamination, which we restate here for
reference.

*

###  E.1 Upper bounding the contamination from label-defining+favored features

In this section, we upper bound the contamination coming from the $s-2$
favored features which are not $\alpha$ or $\beta$. This culminates in the
following lemma.

######  Lemma E.1.

In the same setting as Section 4.3, we have with probability $1-O(1/nk)$ that

$\displaystyle\mathsf{CN}_{\alpha,\beta,L}^{2}+\mathsf{CN}_{\alpha,\beta,F}^{2}\leq
c_{\ref{const_cnf_cnl}}^{2}\min\quantity{1,\mu^{-2}}n^{r-t-1}\log(nsk)^{2},$

where $c_{\ref{const_cnf_cnl}}$ is a positive constant.

###### Proof.

Let ${\bm{W}}_{R}\in\mathbb{R}^{n\times(s-2)}$ as the weighted feature matrix
which includes all of the $s-2$ favored features aside from $\alpha,\beta$. We
can then define
${\bm{A}}_{-R}\triangleq{\bm{A}}-{\bm{W}}_{R}{\bm{W}}_{R}^{\top}$ and
${\bm{H}}_{R}={\bm{W}}_{R}^{\top}{\bm{A}}_{-R}^{-1}{\bm{W}}_{R}$. Using
Woodbury, an analogous computation to Lemma B.2 implies that

$\displaystyle{\bm{W}}_{R}\bm{A}^{-1}\bm{\Delta}y=({\bm{I}}_{s-2}+{\bm{H}}_{R})^{-1}{\bm{W}}_{R}{\bm{A}}_{-R}^{-1}\bm{\Delta}y.$
(100)

The contamination from all of the $s-2$ favored features that are not $\alpha$
or $\beta$ satisfies

$\displaystyle\mathsf{CN}_{\alpha,\beta,L}^{2}+\mathsf{CN}_{\alpha,\beta,F}^{2}$
$\displaystyle=\lambda_{F}\bm{\Delta}y^{\top}\bm{A}^{-1}\sum_{j\in[s]\setminus\quantity{\alpha,\beta}}{\bm{w}}_{j}{\bm{w}}_{j}^{\top}\bm{A}^{-1}\bm{\Delta}y$
$\displaystyle=\lambda_{F}\bm{\Delta}y^{\top}\bm{A}^{-1}{\bm{W}}_{R}{\bm{W}}_{R}^{\top}\bm{A}^{-1}\bm{\Delta}y$
$\displaystyle=\lambda_{F}\bm{\Delta}y^{\top}{\bm{A}}_{-R}^{-1}{\bm{W}}_{R}({\bm{I}}_{s-2}+{\bm{H}}_{R})^{-2}{\bm{W}}_{R}^{\top}{\bm{A}}_{-R}^{-1}\bm{\Delta}y.$

Since Proposition B.6 implies that
$\mu_{1}(({\bm{I}}_{s-2}+{\bm{H}}_{R})^{-2})\leq
c_{\ref{const_hatr_coarse}}\min\quantity{\mu^{2},1}$ with extremely high
probability where $c_{10}$ is a positive constant, we know the contamination
is with extremely high probability upper bounded by the following quadratic
form:

$\displaystyle
c_{\ref{const_hatr_coarse}}\min\quantity{\mu^{2},1}\lambda_{F}\bm{\Delta}y^{\top}{\bm{A}}_{-R}^{-1}{\bm{W}}_{R}{\bm{W}}_{R}^{\top}{\bm{A}}_{-R}^{-1}\bm{\Delta}y$
(101)
$\displaystyle\quad\quad=c_{\ref{const_hatr_coarse}}\min\quantity{\mu^{2},1}\lambda_{F}^{2}\sum_{j\in[s]\setminus\quantity{\alpha,\beta}}\expectationvalue{{\bm{z}}_{j},{\bm{A}}_{-R}^{-1}\bm{\Delta}y}^{2}.$
(102)

We still cannot apply Hanson-Wright, because ${\bm{A}}_{-R}^{-1}$ is not
independent of $\bm{\Delta}y$. However, we can use Woodbury again to take out
${\bm{z}}_{\alpha},{\bm{z}}_{\beta}$ from ${\bm{A}}_{-R}^{-1}$.

Define
${\bm{W}}_{\alpha,\beta}=\matrixquantity[{\bm{w}}_{\alpha}&{\bm{w}}_{\beta}]$
and
${\bm{H}}_{\alpha,\beta}^{(s)}={\bm{W}}_{\alpha,\beta}^{\top}{\bm{A}}_{-s}^{-1}{\bm{W}}_{\alpha,\beta}$.
Then Woodbury implies that

$\displaystyle{\bm{A}}_{-R}^{-1}={\bm{A}}_{-s}^{-1}-{\bm{A}}_{-s}^{-1}{\bm{W}}_{\alpha,\beta}({\bm{I}}_{2}+{\bm{H}}_{\alpha,\beta}^{(s)})^{-1}{\bm{W}}_{\alpha,\beta}^{\top}{\bm{A}}_{-s}^{-1}.$
(103)

Hence

$\displaystyle{\bm{z}}_{j}^{\top}{\bm{A}}_{-R}^{-1}\bm{\Delta}y={\bm{z}}_{j}^{\top}{\bm{A}}_{-s}^{-1}\bm{\Delta}y-{\bm{z}}_{j}^{\top}{\bm{A}}_{-s}^{-1}{\bm{W}}_{\alpha,\beta}({\bm{I}}_{2}+{\bm{H}}_{\alpha,\beta}^{(s)})^{-1}{\bm{W}}_{\alpha,\beta}^{\top}{\bm{A}}_{-s}^{-1}\bm{\Delta}y.$
(104)

We will use Hanson-Wright and Cauchy-Schwarz to argue that the second term in
Eq. 104 above will be dominated by the first term. Indeed, Corollary C.3
implies that ${\bm{z}}_{j}^{\top}{\bm{A}}_{-s}^{-1}\bm{\Delta}y\leq
c_{\ref{const_asymptotic_bilinear}}n^{\frac{1-t}{2}-p}\sqrt{\log(nsk)}$ with
probability at least $1-O(1/nsk)$, so it suffices to show that the other term
is dominated by $n^{\frac{1-t}{2}-p}$. We will show that its contribution for
each $j$ is $\min\quantity{1,\mu^{-1}}\tilde{O}(n^{\frac{1}{2}-t-p})$. By
Cauchy-Schwarz, the magnitude of the second term of Eq. 104 is at most

$\displaystyle\norm{({\bm{I}}_{2}+{\bm{H}}_{\alpha,\beta})^{-1}}_{2}\norm{{\bm{W}}_{\alpha,\beta}^{\top}{\bm{A}}_{-s}^{-1}{\bm{z}}_{j}}_{2}\norm{{\bm{W}}_{\alpha,\beta}^{\top}{\bm{A}}_{-s}^{-1}\bm{\Delta}y}_{2}$
(105) $\displaystyle\quad\quad\leq
c_{\ref{const_label_defining_deviation}}\lambda_{F}\min\quantity{\mu,1}n^{\frac{1}{2}-p}\sqrt{\log(nsk)}\cdot
n^{1-t-p}\sqrt{\log k}$ (106) $\displaystyle\quad\quad\leq
c_{\ref{const_label_defining_deviation}}\min\quantity{1,\mu^{-1}}n^{\frac{1}{2}-t-p}\log(nsk),$
(107)

where $c_{11}$ is a positive constant. In the second line, we have used
Proposition B.6 to upper bound
$\norm{({\bm{I}}_{2}+{\bm{H}}_{\alpha,\beta}^{(s)})^{-1}}_{2}\leq
O(\min\quantity{\mu,1})$ and we have used Theorems B.1 and B.4 to deduce that
that $\absolutevalue{{\bm{z}}_{j}^{\top}{\bm{A}}_{-s}^{-1}{\bm{z}}_{a}}\leq
O(n^{\frac{1}{2}-p})\sqrt{\log(nsk)}$ with probability at least $1-O(1/nsk)$.
Similarly, we used the scaling from Corollary C.3 to deduce that
$\absolutevalue{{\bm{z}}_{\alpha}^{\top}{\bm{A}}_{-s}^{-1}\bm{\Delta}y}\leq
O(n^{1-t-p})\sqrt{\log k}$, and similarly for $\beta$.

Hence ${\bm{z}}_{j}^{\top}{\bm{A}}_{-R}^{-1}\bm{\Delta}y$ is
$O(n^{\frac{1-t}{2}-p})\log(nsk)$ with probability $1-O(1/nsk)$. By union
bounding over $j$ and plugging our upper bound back into Eq. 102, we conclude
that with probability at least $1-O(1/nk)$

$\displaystyle\mathsf{CN}_{\alpha,\beta,L}^{2}+\mathsf{CN}_{\alpha,\beta,F}^{2}$
$\displaystyle\leq
c_{\ref{const_hatr_coarse}}\min\quantity{\mu^{2},1}\lambda_{F}^{2}n^{r}\cdot
O(n^{1-t-2p})\log(nsk)^{2}$ (108)
$\displaystyle=\mu^{-2}\min\quantity{\mu^{2},1}O(n^{r-t-1})\log(nsk)^{2}$
(109) $\displaystyle\leq
c_{\ref{const_cnf_cnl}}^{2}\min\quantity{1,\mu^{-2}}n^{r-t-1}\log(nsk)^{2},$
(110)

where $c_{12}$ is a positive constant, concluding the proof. ∎

###  E.2 Lower bounding the contamination from label-defining+favored features

In this section, we upper bound the contamination coming from the $s-2$
favored features which are not $\alpha$ or $\beta$. This culminates in the
following lemma.

######  Lemma E.2.

In the same setting as Section 4.3, if $t>0$, with probability at least
$1-O(1/nk)$, we have

$\displaystyle\mathsf{CN}_{\alpha,\beta,L}^{2}+\mathsf{CN}_{\alpha,\beta,F}^{2}\geq
c_{\ref{const_cnl_cnf_lower}}^{2}\min\quantity{1,\mu^{-2}}n^{r-t-1},$

where $c_{\ref{const_cnl_cnf_lower}}$ is a positive constant.

###### Proof.

Following the beginning of the proof of Lemma E.1 and what we know about the
flatness of the spectra of hat matrices from Proposition B.6, we can deduce
that there is some positive constant $c_{13}$ such that with extremely high
probability

$\displaystyle\mathsf{CN}_{\alpha,\beta,L}^{2}+\mathsf{CN}_{\alpha,\beta,F}^{2}\geq
c_{\ref{const_hatr_lower}}\min\quantity{\mu^{2},1}\lambda_{F}^{2}\sum_{j\in[s]\setminus\quantity{\alpha,\beta}}\expectationvalue{{\bm{z}}_{j},{\bm{A}}_{-R}^{-1}\bm{\Delta}y}^{2}.$
(111)

We will further lower bound this by throwing out all label-defining $j$. In
other words, the goal now is to lower bound

$\displaystyle\sum_{j\in[s]\setminus[k]}\expectationvalue{{\bm{z}}_{j},{\bm{A}}_{-R}^{-1}\bm{\Delta}y}^{2}=\expectationvalue{{\bm{Z}}_{F}^{\top}{\bm{A}}_{-R}^{-1}\bm{\Delta}y,{\bm{Z}}_{F}^{\top}{\bm{A}}_{-R}^{-1}\bm{\Delta}y}.$
(112)

The main idea is to use Bernstein’s inequality, but unfortunately
${\bm{A}}_{-R}^{-1}$ is not independent of $\bm{\Delta}y$, so we will again
resort to Woodbury to take out ${\bm{z}}_{\alpha}$ and ${\bm{z}}_{\beta}$. As
in the proof for upper bounding the favored contamination, we have
${\bm{W}}_{\alpha,\beta}=\matrixquantity[{\bm{w}}_{\alpha}&{\bm{w}}_{\beta}]$
and
${\bm{H}}_{\alpha,\beta}^{(s)}={\bm{W}}_{\alpha,\beta}^{\top}{\bm{A}}_{-s}^{-1}{\bm{W}}_{\alpha,\beta}$.
Then we can deduce from another application of Woodbury that

$\displaystyle{\bm{z}}_{j}^{\top}{\bm{A}}_{-R}^{-1}\bm{\Delta}y={\bm{z}}_{j}^{\top}{\bm{A}}_{-s}^{-1}\bm{\Delta}y-{\bm{z}}_{j}^{\top}{\bm{A}}_{-s}^{-1}{\bm{W}}_{\alpha,\beta}({\bm{I}}_{2}+{\bm{H}}_{\alpha,\beta})^{-1}{\bm{W}}_{\alpha,\beta}^{\top}{\bm{A}}_{-s}^{-1}\bm{\Delta}y.$
(113)

Again, we can argue that with probability $1-O(1/nsk)$, the second term is
upper bounded in magnitude by

$\displaystyle\min\quantity{1,\mu^{-1}}n^{\frac{1}{2}-t-p}\log(nsk)=\min\quantity{1,\mu^{-1}}O(n^{\frac{1-t}{2}-p}\cdot
n^{-\kappa_{\ref{kappa_bernstein_error}}}),$ (114)

where $\kappa_{6}$ is a positive constant because $t>0$. Since Hanson-Wright
(Corollary C.3) implies that