Anisotropic Random Feature Regression in High Dimensions
Authors: Gabriel Mel
Jeffrey Pennington
Venue: ICLR 2022 Poster (2022)
Keywords: random feature models
high dimensional asymptotics
generalization
learning curves
double descent
multiple descent
alignment

Abstract: In contrast to standard statistical wisdom, modern learning algorithms typically find their best performance in the overparameterized regime in which the model has many more parameters than needed to fit the training data. A growing number of recent works have shown that random feature models can offer a detailed theoretical explanation for this unexpected behavior, but typically these analyses have utilized isotropic distributional assumptions on the underlying data generation process, thereby failing to provide a realistic characterization of real-world models that are designed to identify and harness the structure in natural data. In this work, we examine the high-dimensional asymptotics of random feature regression in the presence of structured data, allowing for arbitrary input correlations and arbitrary alignment between the data and the weights of the target function. We define a partial order on the space of weight-data alignments and prove that generalization performance improves in response to stronger alignment. We also clarify several previous observations in the literature by distinguishing the behavior of the sample-wise and parameter-wise learning curves, finding that sample-wise multiple descent can occur at scales dictated by the eigenstructure of the data covariance, but that parameter-wise multiple descent is limited to double descent, although strong anisotropy can induce additional signatures such as wide plateaus and steep cliffs. Finally, these signatures are related to phase transitions in the spectrum of the feature kernel matrix, and unlike the double descent peak, persist even under optimal regularization.

Published as a conference paper at ICLR 2022
ANISOTROPIC RANDOM FEATURE REGRESSION IN HIGH DIMENSIONS
Gabriel C. Mel
Neurosciences Graduate Program Stanford University melde f fon& gma com
Jeffrey Pennington
Brain Team, Google Research jpennin@google com
ABSTRACT
contrast to standard statistical wisdom, modern learning algorithms typically find their best performance in the overparameterized regime in which the model has many more parameters than needed to fit the training data. A growing number of recent works have shown that random feature models can offer detailed theoretical explanation for this unexpected behavior, but typically these analyses have utilized isotropic distributional assumptions thereby failing to provide a realistic characterization of real- world models that are designed to identify and harness the structure in natural data. In this work, we examine the high-dimensional asymptotics of random feature regression in the presence of structured data, allowing for arbitrary input correlations and arbitrary alignment between the data and the weights of the target function. We define a partial order on the space of weight-data alignments and prove that generalization performance improves in response to stronger alignment. We also clarify several previous observations the literature by distinguishing the behavior of the sample- wise and parameter-wise learning curves, finding that sample-wise multiple descent can occur at scales dictated by the eigenstructure of the data covariance, but that parameter-win wise multiple descent is limited double descent, although strong anisotropy can induce additional signatures such as wide plateaus and steep cliffs. Finally, these signatures related phase transitions in the spectrum of the feature kernel matrix, and unlike the double descent peak, persist even under optimal regularization.
the underlying data generation process,
INTRODUCTION
While deep learning races ahead with its impressive list of practical successes. it has often done so by building larger models and training on ever larger datasets. For example, recent large language models leverage billions (Brown al., 2020) Raffel et al. 2019) or even trillions (Fedus al.. 2021) of parameters. As the state-of-the-ee pushes the computational frontier, model development, experimentation, and exploration become increasingly costly, both terms the computational resources and person-hours.
To facilitate the development of improved models, becoming ever more necessary to develop theoretical models that can help guide model development these high-dimensional scenarios. Indeed, our theoretical understanding is so limited that even linear regression, the most basic machine learning method of all, is still yielding surprises in high dimensions (Hastie al. 2019).
While linear regression can capture many salient features reasonable model for digh-simensional models. In particular, there is natural inteeindeeendent notion of model size: the number of parameters the model is intimately tied (usually equal) to the dimensionality of the datapoints. This limitation means that linear regression may not accurately
high-dimensional data, it is not a

---

Published as a conference paper at ICLR 2022
capture the effect of overparameeterization, which appears to be crucial ingredient in modern deep learning models (Zhang et al. 2016).
Beyond linear regression, the next simplest model is arguably the random feature model of Rahimi ct al. (2007), which turns out to be tractable in high dimensions while also allowing for a natural data-independent lever vary model size the number of random features. Random feature models have also gained independent interest through their relationship to neural kernels and Gaussian processes (Neal) 1996] Lee al., 2017 Novak et al. 2018 Lee et 2019 Jacot et al. 2018). While recent works have examined the asymptotic performance of random feature models, most have done so in the restricted setting of isotropic covariates and target functions (Mei & Montanari, 2019; a' Ascoli et al.] (2020] [Adlam & Penningtoon 2020a b). Based on the conjectured Gaussian equivalence principle of Goldt et al. (2020b), few recent works have begun relaxing these simplifying assumptions in an effort to describe more natural data distributions (Loureiro et al. [021] d' A'sooii et al. al.] (2021). In this work, we extend the high-dimensional random feature linearization technique of (ripurannn et al.) (202Ia to allow for anisotropic target functions, revealing a host of novel phenomena related to the alignment the data and the target weights.
1.1 CONTRIBUTIONS
Our primary contributions are to:
Derive theoretical predictions for the test error, bias, and variance of random feature re- gression for anisotropic Gaussian covariates under general linear target functions in the -ish-dimennional asymptotic limit (Section 3.I):
2. Prove that overparameterizztion reduces the total test error, bias, and variance, even in the presence of anisotropy (Section 3.2)
3. Define a partial order on the space of weight-data alignments and prove that generalization performance improves in response to stronger alignment (Definition 2.1 Section (.3):
4. Demonstrate that anisotropy can induce sample-wise multiple descent, but prove that parameter-wiss multiple descent is limited to double descent (Section (34):
5. Provide theoretical explanation for steep cliff's observed in parameter-wise learning curves that persist under optimal regularization, and relate them to phase transitions in the spectrum of the feature kernel matrix (Section 3.4)
1.2 RELATED WORK
Our analysis builds on series of works that have studied the exact eigh-dimessiona asymptotics of the test error for growing class of model families and data distributions. Early work in this direction examined minimum-norm interpolated least squares and ridge regression the high-dimensional
random design setting (Belkin et al. 2019 Dobriban et al.) 2018 Hastie et al. 2019). finding
surprising phenomena such as double descent and a negative optimal ridge constant (Kobak et al. 2020). These analyses were generalized in (Richards et al. 2021 Wu & Xu 2020 Hastie et al. (019) to allow for anisotropic covariance matrices and weights that generate the targets. This anisotropic configuration was studied in further detail in (Mel & Ganguli 202I), uncovering nuanced behavior such as sample-wise multiple descent and a sequence of phase transitions in the performance and optimal regularization.
While linear regression can provide insight into generalization performance in high dimensions, it can- not faithfully reproduce the features of non-linear models, such as the effects of overparameteriizatin.. Random feature models, on the other hand, can capture many such features while still maintaining analytical tractability. Recent results have developed a detailed understanding of isotropic random feature regression in the tigh-dimensional asymptotic limit, providing precise characterization of peaks in the test error and the benefits of overparameterization (Mei Montanari 2019 d' Ascoli et al. 2020 Adlam & Pennington 2020a). The origin of these peaks was explained by means of a tine-grained decomposition of the bias and variance in (Adlam & Pennington, 20206| Lin & Dobriban 2020). While most prior work examining the high-dimensional asymptotics of random feature models have leveraged isotropy of the covariate distribution. this assumption was recently relaxed in (Liao al. 2020) for random Fourier feature models, in (Tripuraneni et al. 2021a b) in the
2

---

Published as a conference paper at ICLR 2022
study of covariate shift, and in several works based on the Gaussian equivalence principle of Goldt jet al. (2020a b) (Gerace et al. [2200] Loureiro et al. (022).
Though most of these works did not pursue detailed investigation of the anisotropy itself, while finalizing this manuscript we became aware of concurrent work (d Ascoli et al. 202T) which does focus on the interplay of the anisotropic input features and target functions, as do here. Whereas d' d'Ascoli et al. (202T) leverage the Gaussian equivalence principle and the replica method from statistical physics, we use a completely different set of techniques stemming from the literature on random matrix theory and operator-valued free probability (Pennington & Worah, 2018 2019 Louart Louart al., 2018 Pécché al.] |01 9 Far et al. 2006, Mingo & (oricher[2017]] which provides complementary perspective that could be made completely rigorous. d' Ascoli et al. (202T) investigates the role of anisotropy not just under squared loss, as we do here, but also under logistic loss, and obtains good numerical support for the Gaussian equivalence conjecture in that setting. In contrast, our narrower and deeper focus on squared loss allows us not only to uncover host of novel phenomena, including multiple descent, steep error cliffs, and spectral phase changes, but also to rigorously prove several propositions about their existence and properties. We provide more in-depth discussion of these and other related works in App.
Adlam et al. 2019 Adlam Pennington 2020a]
Our work relies heavily on the concept of alignment (see Def. 2.I) between the data covariance and the target vector coefficients. An analogous definition appears in (Triprrnenii et al., 2021a ()) in the context of covariate shift, leading to a superficial similarity of results. However, the implications and interpretations are otherwise quite different, so we refrain from repeatedly commenting these recurring connections.
2 PRELIMINARIES
2.1 PROBLEM SETUP AND NOTATION
We study random feature regression RRahimi al. 2007) as model for learning unknown linear function of the data,
y(x,) 3 x /no + E
(I)
from m independent samples (x,, "o R. I...,, .....,,, m, where the covariates are Gaussian, X ~ (0, )) and where E, ~ (0, is additive noise (present on the training samples only).
We focus on the high-dimensional proportional asymptotics in which the input feature dimension the hidden layer size n1, and the number of samples m all tend to infinity at the same rate, with Au. := nu/ m and 10 := no/ nn held constant. The overparameterizatioo ratio o/vb n1/m is a measure of the normalized complexity of the random feature model.
Interestingly, under this model in our high-dimensional setup, any nonlinear component of the signal to be learned behaves like additive noise, so the linear function in Eq. T does not sacrifice generality (Mei & Montanari 2019: Adlam & Pennington 2020a).
Following many works high high-dimensiooal regression (see e.g. Dobriban et al. (2018), we assume the coefficient vector 3 is random, B ~ (0, E3), though allowing for deterministic 3 would be a straightforward extension and would simply involve replacing E3 - 3,33T throughout.
Denoting the training dataset as X = [xi..... xm.] and the test point as x, the random features are, F == (W (W and f == (Wo/ ///)//)))
(2)
where W e Xgn is a random weight matrix with i.i.d standard Gaussian entries, and af-) R R is an activation function that is applied elementwise. These random features define the kernel
-
1
K(x1, x2) == (Wx/Wx//Vee [xx//VnoTT o x2/ //n),
no
which can be used to compute the model's predictions on a point x as f(x) = YK--Ky
Here we have defined the training labels as Y : [,(()),.... ), and the regularized kernel matrix as K := K(X,X) X) + 7/m as well as Kx := K(X, x) for 20. 0.
The training emror is given by,
B((B X/ -K- F ExE((((X) -(x))
3

---

Published as a conference paper at ICLR 2022
and the test error (without label noise on the test point) can be written
Eg [[v() [(x))
of EE x/v -YMToo-KKKKK
(5)
where the outermost expectation over /3 has been suppressed since the quantity concentrates sharply around its mean and the inner expectation is computed over all the randomness from training, i.e. W, X, and The test error can be decomposed into its bias and variance components as
Ex
Ex E
([(()(()) xx))
Ex Ex [V(x())]
(6)
Bug
Vipp
The bias and variance are computed with respect to all the randomness from training, i.e. W, X, 6, which differs from common practice in the statistics literature. but which is necessary obtain decomposition that is intuitive and unambiguous when the predictive function relies on randomness from multiple sources (Adlam Pennington 2020b; Lin & Dobriban 2020).
As noted by (Hastie et al. 2019 Wu & Xu 2020 Mel & Ganguli 2021), the test error of linear
regression depends on the geometry of (Σ, Σ3) (or (,, B3 in the case of nonrandom f), and we will
find the same to be true for random feature regression. As such, we decompose the training and B
covariance matrices into eigenbases as Σ = E A,, and Σ3 = E X V. V. where the eigenvalues are in nondecreasing magnitude, i.e. A S A .... S An and X S X₂ S ... S Ano
Following (Tripuraneni et al., 2021a b), we then define the overlap coefficients as
70
:= v. Egv,
Σ j=1
to measure the alignment of Eg with the ith eigendirection of Σ. Note that for deterministic / this definition simply gives the square of the component of / in the ith eigendirection, i.e. qi (v. 3)
2.2 ASSUMPTIONS
In order to define the limiting behavior of the test error in Eq. it is necessary to impose some regularity conditions on and Σg As in Wu & Xu 2020 Tripuraneni al., 2021a b), the limiting spectra of these matrices cannot be considered independently because their eigenspaces may align. This alignment most conveniently described in an eigenbasis of Σ.
Assumption 1. We define the joint spectral distribution (JSD) as
1
Png
(8)
T&D
and assume converges in distribution some μ. distribution on IR2, as ngg - CO. refer to l as the limiting joint spectral distribution (LJSD), and emphasize that this defines the relevant limiting properties of the covariate and weight distribution
Often we use (X, for random variables sampled jointly from μ and denote the marginal of under with Adaaa Since the conditional expectation B[q] A] is an important object in our study, we assume the following for simplicity.
Assumption 2. μ is either absolutely continuous or a finite sum of delta masses and the expectations of X and 9 are finite. Moreover, E,, [x]] = 1.
The normalization condition E,, [pq] = is not necessary for our analysis, but, as Meel & Ganguli 202T), it enforces consistent signal-to-noise ratios across different target functions and thereby facilitates meaningful comparisons of the test error.
In fact, the necessary assumptions are identical those of Tripuraneni et al. 2021a since Eg plays an analogous role the test covariance E.* of that work.
'The JSD depends not only on Σ and Me but also on choice of cigendecomposition for 2 when it has repeated eigenvalues; however, as in (Tripuraneni al. 202 b), all possible choices lead to the same formulas and conclusions.
4

---

Published as a conference paper at ICLR 2022
As we will eventually consider the high-dimensional limit, it is convenient to define the asymp- totic covariance scale as $ = lim 1 tr(E)) = [yll under the limiting behavior specified in
Assumption |
One important case is when Dg Ino in which case the LJSD degenerates to μl defined by
Po(2. q) Pama (1))
we also enforce the following standard regularity assumptions on the activation functions ensure the existence of the moments and derivatives compute.
Following Trrpuurnneni et al. (202 b).
Assumption 3. The activation function a R IR is assumed be differentiable almost everywhere. We assume there exists a universal constant C' such that, (z) (x)] (cexp(Zz)).
2.3 A SIMPLE FAMILY OF ANISOTROPIC DISTRIBUTIONS
The assumptions above allow for a wide class of possible asymptotic covariance structures and spectra. To allow for concrete examples that have intuitive interpretations, we introduce the following simple family of distributions that capture multi-scale structure in the input, which we refer to as d-scale LJSDs. In particular, for d E N and real 0 <
and 0, we define
d-scalc Ha,0
= Σ d (Cai, (D
(10)
(11-a(0-11a) enforce the normalization conditions where C = 1 1--a" and D = C d1-afe
d = Migoi [A] = and E Audaa [g>] = 1. These simple covariance models capture the hierarchy of and 1, the distribution reduces to the isotropic case with identity covariance. For the nontrivial setting in which
scales that often characterize the structure of natural datasets. Note that by setting
the data exhibits sequence of d distinct scales where each scale is factor a smaller than the previous one. The exponent 0 parameterizes the strength of the weight-data alignment in an intuitive way. When 0, there is no alignment, and Ee proportional to the identity. When 0 > 0, there is strong alignment, as the large eigendirections of the training distribution correspond large eigendirections of Σ.g When O, there is anti-ali alignmenttt as the large eigendirections of the training distribution correspond to small eigendirections of Σg.
2.4 DEFINITION OF THE STRENGTH OF WEIGHT-DANE DATA ALIGNMENT
As the preceding discussion has suggested and as we will see explicitly in the following section, the LJSD μ captures all of the information about the pair of covariance matrices (E, Σn) that is relevant for describing the asymptotic test error, bias, and variance. As the alignment between Σ and Eg can vary in strength among the different eigendirections, the concept of alignment is inherently multi-dimensional. Nevertheless, by requiring strong alignment along the larger eigendirections, is possible define the following natural partial order on the space of possible weight-data alignments
Definition 2.1. Let μr and μ2 be LISDs with the same marginal distribution of X. If the asymptotic overlap coefficients are such that E,,, [íq[A] /E,z [Aq[>] = E,, X} /Ezu [q]A] is nondecreasing in X, we say that Yn is more strongly aligned than μt2 and write μn S p2- Comparing against the case of isotropic weight distribution, pig, we say bt is aligned when μ4 S su and anti-aligned when
#1 2 Ug.
The parameter 0 of the d-scale model in Eq. 10 provides a quantitative measure of alignment under Definition 1.1 formalizing the intuition given in Section 2.3 As we will see in Section 3.3 the asymptotic generalization performance of random feature regression is strictly ordered under this definition of alignment strength.
Note that this definition is nearly identical to that of Tripuraneni et al. 202 bJ with the concept of hardness replaced by alignment.
5

---

Published as a conference paper at ICLR 2022
(a)
(b)
(c)
Test error
Blas
Variance
Algremeec
0.1
-2
10
10'
10
10"
10"
10f Gveparameeerzatten
(d)
Overgarametentaaton
(e)
Overaarametertaaion
Test/train ratio
Brnar
10f
Ver.
1
10-1
Enerr
Bias 36
10
30-3
10P
10
2
Over Cverpraamtteiizionn d/v
Aigrment 6
Alignment
Figure 1: Test error, bias, and variance function of the overparameterizzatoon ratio (0/1) n1 /m) and the alignment for the 2-scale LJSD (Eq. (10) with & = Ro/m =
10 and o² 1/100. (a) The total test error exhibits the characteristic double descent behavior for all shift powers. (b) The bias is nonincreasing function of 6/16 for all shift powers, as in Proposition 3.1
(c) The variance the source of the peak, and nonincreasing function of 6/16 for all shift powers in the overparameterized regime, as in Proposition 3.2 Blue, orange, and green lines in (a,b,c) indicate locations of vertical and horizontal slices shown (d.e.f). (d) ID horizontal slices of (a.b,c) more clearly demonstrate the monotonicity in < predicted by Propositions 3.1 1 and 3.2 (e) ID vertical slices demonstrate the monotonicity
of the test error and the bias predicted by Proposition 3.3 and illustrate that the variance may not decrease in response to stronger alignment (solid green Eu+o
trace). (f) Test error, bias, and variance normalized by the training error (ie. Emin/ Emin (P=00) similarly for Bu Vy,). Same legend as (e). Constancy of the blue traces illustrates how the train and test error respond identically to alignment. Simulations for m 4000 (d,e; crosses) agree well with formulas.
MAIN RESULTS
Our main result characterizes the high-dimensional asymptotic limits of the test error, bias, and variance of the nonlinear random feature model Section 2 Before stating the result, we introduce some additional notation that captures the effect of the nonlinearity o,
1 = V V==NN(..)(0())) p== (: < ç: sp, wi= s(n/s-1)
(11)
where, as above, s = lim 00 no tr = [A]. The constant w 2 0 is measure of the degree of nonlinearity, with w = 0 corresponding to linear activation functions (see Lemma B.I). Analogously
Tripuraneni al. 202 la b), also introduce two functionals of μs, which capture all the relevant spectral information needed for describing the test loss.
Ia,b == ò Ep (X* ( and I = & Es (qx (0++22))))
(12)
3.1 FORMULAS FOR ASYMPTOTIC BIAS, VARIANCE, AND TEST ERROR
Theorem 3.1. Under Assumptions 7 no, ni, m - with no/m and vb no/ni held constant, the training error D tends toward the value of Elt where
Elt = - (2,(TIZfn)+ + +0 o20
(13)

---

Published as a conference paper at ICLR 2022
(a)
(b)
(c)
Testerar
Karnal matrix spactrum
Number spoctral companents
10
2
14
14"4
4
3/3
2/3
3/3 2/3
1/3
2/3
4 miho
Figure 2: Sample-wise multiple descent for anisotropic data function of nonlinearity strength w. All panels refer to 3-scale covariance model with a = 10", and a =, 8 p-=-p--- p= = 10
and o² = 10. (a) Error exhibits multiple peaks as a function of the the sampling density o As increased, peaks are attenuated and eventually disappear in sequence starting from those due to the weakest data scales (at m = n2) to those due to the strongest data scales (at m n3) (b) Limiting spectral density the kernel matrix [(X,
F" //n, Vertical slices correspond to the spectral density at the corresponding value of Φ- for in (a) occur critical values m 3 To no where a new spectral component first appears. (c) Consistent with this, sample-wisg wise learning curves exhibiting multiple descent at low w pass through several transitions in the number of spectral components, while those at higher w with fewer peaks pass through fewer component transitions.
10 10-10 Peaks in the error curves
and the bias, variance, and test error Brng VEg, Frig tend toward Bu, Vas Feg with
E 7277
E,
Bp = 4I and Vj = =p==p B
(14)
where p; w are defined in III. Ia,by I are defined in
12 and æ is the unique nonnegative real v (1b 07 4mm00r/
root of x w4T1111
1-VEL with Ti
200
Remark 3.1. As noted in (Adlam & Pennington 2020a Hastie et al. 2019) for isotropic covariates, the test error is simply related the training error through the generalized cross- pooss-alidation (GCV) formula (Golub al. 1979). Curiously, because is independent of B, it follows that the test error depends on 3 entirely through its effect on the training error; in contrast, the bias-variance decomposition retains explicit 3 dependence, even conditional on the training error.
The results in Theorem 3.1 depend on single scalar self-consistent equation for x. x= 1-yyr
w+I
which is in fact the same as the one appearing in Tripuraneni al. (2021a b), and which significantly simplifies the expressions relative to those recently obtained using the replica method (d' Ascoli al. 2021). Owing to its simplicity, this equation admits straightforward analysis that we pursue in the Appendix, yielding numerous inequalities and bounds that ultimately prove the propositions presented throughout this section. We will occasionally refer the ridgeless limit of Theorem 3. which is given in Corollary G.I Finally, as consistency check, taking (xx) a and v 0 in Theorem 3.1 yields an expression for the test error, bias, and variance for linear regression that agrees with the results of (Wu & Xu 2020 Mel & Ganguli 2021) (see Section
3.2 THE BENEFITS OF OVERPARAMETERIZAATUR
While there is abundant empirical evidence that overparameterization can improve the generalization performance of practical models (sec e.g. (Zhang et al., 2016)). rigorous explanations for this behavior therefore
have been offered solely in the setting of isotropic covariates and target functions. natural wonder whether the benefits of overparmeterization persist in the presence of anisotropy, and indeed recent theoretical work has provided numerical evidence hinting that overparameterization beneficial (d' Ascoli et al. 2021). The following two results prove this to be the case.
First, we show that the bias decreases (or stays constant) in response to an increase in the number of random features, regardless of any anisotropy in the covariates or target function weights.
7

---

Published as a conference paper at ICLR 2022
Proposition 3.1. In the setting of Theorem 3.7 the bias By is a nonincreasing function of the overparameterizatioo ratio 6/vb
The same is true for the variance in the overparameterized regime. Note that our proof requires the ridgeless setting, but numerical simulations suggest that the result may hold generally (see Fig. D
Proposition 3.2. In the ridgeless limit and in the overparameterized regime (vb < Φ), the variance V is nonincreasing function of overparameterization ratio 6f 1/1b.
In Fig. D Propositions 3.1 and 3.2 are illustrated. Moving left to right in panels (a)-(d) leads to models with more parameters. The monotonicity of the bias across the whole range of parameterization evident, as is the monotonicity of the variance in the overparmaeterized regime.
3.3 WEIGHT-DATA ALIGNMENT REDUCES THE BIAS AND TEST ERROR
number of recent works have confirmed the intuition that generalization performance should improve if the weights of the target function align with the large eigendirections of the training covariance, with formal theoretical arguments in the case of linear regression (Hastie et al.) 2019 Mel & Ganguli 202I), and with informal numerical simulations for random feature models (d' Ascoli et al. 2021p. The following result proves that this informal observation holds in full generality, not only for the total test error, but for the bias and the -o---an-v ratio well.
Proposition 3.3. Let 11, M2 be two LJSDs such that μ1 P2 (see Definition 2.7 Then Bp Bp Ep, S Epg. and Bp, VV S Ppo./Aw
We illustrate Proposition 3.3 Fig. for the 2-scale LISD of Eq. (0)). Following vertical lines upward in panels (a-c) or the x-axis left-to-right in (e,f) yields stronger alignment and a corresponding decrease in the bias and test error. Panel (f) shows the alignment-dependee and test error when normalized by the training error. As suggested by Remark [3.]] the normalized test error is independent of the alignment strength, and as intuition would suggest and as predicted by Proposition 3.3 the normalized bias decreases in response stronger alignment.
of the bias, variance,
3.4 ANISOTROPY INDUCES STRUCTURED LEARNING CURVES
Strong anisotropy has been observed to induce structured learning curves in the context of linear regression (Mel & Ganguli (202I)) It is natural wonder whether these effects generalize the case of nonlinear random features. Figure 2 shows that this is indeed the case for sample-wise learning curves, where a- m/no varied while z Mo/nn 1 is held fixed. Horizontal slices through Fig. (a) exhibit hample-wise multiple descent. Fig. 2 (b) and (c) show that these peaks are associated with phase transitions at critical values o where the spectrum of the kernel matrix _ Fx acquires a new component. Increased nonlinearity w attenuates this effect.
In contrast, the following proposition shows that parameter-wise multiple descent does not occur even in the presence of strong anisotropy, as long as p is aligned.
Proposition 3.4. If μ is aligned (see Definition 2.7y. then, in the ridgeless limit, the test error has at most two interior critical points as a function of the overparameterizzatin ratio o/tb.
Remark 3.2. Since k-fold descent requires at least k critical points, we conclude that multiple (k > 2) descent does not occur, even in the presence of covariate anisotropy. long μ is aligned.
Fig. Bj.b) shows parameter-wise learning curves for various values of 0 in the 2- and 3-scale models. As predicted by Proposition]] 3.4 the curves for aligned LJSDs (0 Z 0) have at most two critical points (not shown). In fact, even for anti- anti-aligned LJSDs (0 < 0), most curves also have at most two critical points; however, for small enough 6, an additional critical point emerges, and indeed the upper-most traces in Fig. 3 bbb showcase a second peak in the learning curves.
Even though parameter-wise multiple descent is not possible for aligned LJSDss, strong anisotropy can nevertheless induce other signatures, including wide plateaus and steep cliffs. To understand the origin of these effects, consider the ridgeless limit, for which the self-consistent equation for x is,
A
+
E
min 1,
(15)
8

---

Published as a conference paper at ICLR 2022
(a)
(b)
(c)
(d)
Tesn: DFTO
Tast arior
Test ener opemmll V
Kemai matrix spectrum
10P
13a1
10a
10:11
10
10
0g
10t4
0g22
10"
n.2
0.4
14
$1p
6rg
Test:
Komel mabrix spectrum
10"0
10
10
10
/v/ 2ny/3
A//3
9md P1/fg
Figure 3: Strong anisotropy causes steep cliffs in the test error as function of the overparameteri-
zation ratio //v = n1 n m. & 5/6, 10 , p 1, = 10 and o² 10 Top row: d 2-scale model with exhibits the characteristic peak at the interpolation threshold, but additionally displays steep cliffs at critical values of n corresponding to multiples of ro/d / (b, dashed lines; also shown). The value associated to each trace is indicated by the colored ticks in (a). (c) Unlike the peak at the interpolation threshold, cliffs in the error traces in (b) persist under optimal regularization (error values from analytical formulas were numerically optimized over ?). (d) The spectrum of the kernel matrix K x)
10 5; bottom row: 3-scale model with 10 (a.b) Test error
n1 F F undergoes phase transition at each of the critical values of n1 where 1r
cliff occurs (dashed lines). The phase transition associated to the interpolation threshold at nı m also visible in the lower panel, but is out of range (at Ro 10- 10-17) in the upper panel.
For small w, the left side becomes relatively insensitive to changes in x whenever A_ < 6// < d for some wide spectral gap with boundary (4). It follows that, in the underparamettrizee regime (ó < v)), the derivative 0( / /////z /ox small, or, equivalently, (00 v) is large. This strong sensitivity of z to changes in the overparameterizatioo ratio 0/1 induces similarly strong changes to the error because a /Or is bounded. As a result, the parameter- wise learning curves exhibit sharp downward cliffs in the underparameterized regime for sufficiently small w and sufficiently large spectral gaps X / We make this argument more precise in Appendix
Fig. (a) illustrates these cliffs in the context of the d 2- and 3-scale LJSD. Along horizontal slices, the error turns sharply downward as a function of n x 6//b at integer multiples of no/d. dd As can be seen in Fig. b)) when the alignment is increased and / overlaps more with large As, the first error cliff, corresponding to the largest scales in the data, strengthens relative to others (cliff at Φ/v 1/2 the 2-scale model and d/ / 1/3 in the 3-scale model). Fig. C)) shows that, unlike the peak the interpolation threshold, cliffs persist under optimal regularization. Finally, Fig. 3) illustrates how steep decreases in the error are associated with the appearance of a new component in the spectrum of the kernel matrix at critical values of 6/1.
4 CONCLUSIONS
We presented an exact calculation of the limiting test eттоr, bias, and variance for random feature kernel regression with anisotropic covariates and target function weights. We defined a partial order over weight-data alignments and proved that stronger alignment decreases the bias and test error. We also proved that the benefits of overparameterization persist in the anisotropic setting, and that weight-data alignment limits parameter-win multiple descent to double descent. In contrast, demonstrated that anisotropy can induce sample-wing wise multiple descent, and parameter- wise cliffs, and that their structure is dictated by the eigenstructure of the data covariance. Future directions include extending our results to the non-asymptotic regime, accommodating feature learning and more general neural network models, and investigating the impact of anisotropy for other loss functions.

---

Published as a conference paper at ICLR 2022
REFERENCES
Ben Adlam and Jeffrey Pennington. The neural tangent kernel in high dimensions: Triple descent and multi-scale theory of generalization. In International Conference on Machine Learning, pp- 74 84. PMLR, 2020a.
Ben Adlam and Jeffrey Pennington. Understanding double descent requires a finegraiiee bias- variance decomposition. arXiv preprint UrXiv:2011.0332) 2020b.
Ben Adlam, Jake Levinson, and Jeffrey Pennington. A random matrix perspective on mixtures of nonlinearities for deep learning. arXiv preprint WrXXv::912.00822 2019.
Mikhail Belkin, Daniel Hsu. Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical birs-variance trade-off. Proceedings of the National Academy of Sciences, 116632):1584--185444 2019.
Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et Language models few-shot learners. arXiv preprint arXiv:2005. 10t.:00005.4115, 2020.
Stéphane d' Ascolli Levent Sagun, and Giulio Biroli.
Triple descent and the two kinds of overfitting: Where & why do they appear? arXiv preprint arXiv:2006. 03509, 2020.
Stéphane d' Ascoli, Marylou Gabrié, Levent Sagun, and Giulio Biroli. On the interplay between data structure and loss function in classification problems, 2021.
Edgar Dobriban, Stefan Wager, al. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-279, 2018.
Reza Rashidi Far, Tamer Oraby. Wlodzimierz Bryc, and Roland Speicher. Spectra of large block matrices. arXiv preprint es/050005, 2006.
William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. arXiv preprint arXiv:2101.0396. 2021.
Federica Gerace, Bruno Loureiro, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Generali- sation error learning with random features and the hidden manifold model, 2020.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Limitations of lazy training of two-layers neural networks, 2019.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods?, 2021.
Sebastian Goldt, Mare Mézard, Florent Krzakala, and Lenka Zdeborová. Modeling the influence of data structure on learning in neural networks: The hidden manifold model. Physical Review X, 10 (4):041044, 2020a.
Sebastian Goldt, Galen Reeves, Mare Mézard, Florent Krzakala, and Lenka Zdeborová. The gaussian cquivalence of generative models for learning with two-layer neural networks. arXiv e-prints, pp. arXiv-2006, 2020b.
Gene H Golub, Michael Heath, and Grace Wahba. Generalized cross-validation as a method for choosing good ridge parameter. Technometrics, 21(2):215-223, 1979.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv:1903.08560 2019.
J. William Helton, Scott A. McCullough, and Victor Vinnikov. Noncommutative convexity arises from linear matrix inequalities. Journal of Functional Analysis, 240:105 145:105-191, 2006.
Hong Hu and Yue M. Lu. Universality laws for high-dimensional learning with random features, 2021.
10

---

Published as a conference paper at ICLR 2022
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. arXiv preprint arXiv: 2018.
Noureddine El Karoui. The spectrum of kernel random matrices. Annals of Statistics, 38:1-50, 2010.
Dmitry Kobak, Jonathan Lomond, and Benoit Sanchez. The optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization. Mach. Learn. Res., 21:169-1,
Jachoon Lee, Yasaman Bahri, Roman Novak, Samuel S Schoenholz. Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprint arXiv: 1.00165, 2017.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neural information processing systems, 32.8572-8583, 2019.
Zhenyu Liao, Romain Couillet, and Michael W Mahoney. random matrix analysis of random fourier features: beyond the gaussian kernel. precise phase transition, and the corresponding double descent. arXiv preprint arXiv:2006.0500 05000 2020.
Licong Lin and Edgar Dobriban. What causes the test error? going beyond bias-variance via anova. arXiv preprint arXiv:2010.05170, 2020.
Cosme Louart, Zhenyu Liao, Romain Couillet, et al. A random matrix approach to neural networks. The Annals of Applied Probability, 28(2):1190-1244 2018.
Bruno Loureiro, Cédric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mézard, and Lenka Zdeborová. Learning curves of generic features maps for realistic datasets with a teacher-student model, 2021.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprint 1908 2019.
Gabriel Mel and Surya Ganguli. A theory of high dimensional regression with arbitrary correlations between input features and target functions: sample complexity, multiple descent curves and a hierarchy of phase transitions. In International Conference Machine Learning, pp. 7578-7587.
PMLR, 2021.
James A Mingo and Roland Speicher. Free probability and random matrices, volume 35. Springer, 2017.
Radford M Neal. Priors for infinite networks. In Bayesian Learning for Nearal Networks, pp. 29-53. Springer, 1996.
Roman Novak, Lechao Xiao, Jaehoon Lee, Yasaman Bahri, Greg Yang, Jiri Hron, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Bayesian deep convolutional networks with many channels are gaussian processes. arXiv preprint 18100: 148, 2018.
Péché al. A note on the pennington-wort worah distribution. Electronic Communications in Probability, 24, 2019.
Jeffrey Pennington and Pratik Worah. The spectrum of the fisher information matrix of single- hidden-layer neural network. In NeurIPS, pp. 5415-5424, 2018
Jeffrey Pennington and Pratik Worah. Nonlinear random matrix theory for deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2019(12):124005 2019.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint arXiv:1910. 10683, 2019.
Ali Rahimi, Benjamin Recht, et al. Random features for large-scale kernel machines. In NIPS, volume 3, pp. 5. Citeseer, 2007.
11

---

Published as a conference paper at ICLR 2022
Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. Asymptotics of ridge(less) regression under general source condition. In Arindam Banerjee and Kenji Fukumizu (eds.). Proceedings of The 24th International Conference Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 3889-3897. PMLR, 13-15 Apr 2021. URL http:://rrceeeiingg ngs. www.l...rrs/ssii htt.rrrraaa///3///rccrrrr////// htmmm
Nilesh Tripuraneni, Ben Adlam, and Jeffrey Pennington. Covariate shift in high- sigh-dimensioall random feature regression. arXiv preprint arXiv:2111.08234, 2021a.
Nilesh Tripuraneni, Ben Adlam, and Jeffrey Pennington. Overparameterization improves robustness to covariate shift high dimensions. Advances Neural Information Processing Systems, 34, 2021b.
Denny Wu and Ji Xu. On the optimal weighted & regularization in overparameterized linear regression. arXiv preprint arXiv:2006.05800 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: 16.00533, 2016.
12

---

Published as a conference paper at ICLR 2022
Supplementary Material: Anisotropic Random Feature Regression in High Dimensions
TABLE OF CONTENTS: SUPPLEMENTARY MATERIAL
Additional discussion of related work
A.1
Asymptotic enror formulas and Theorem 3.1
A.2 Gaussian equivalents
A.3
Weight-data alignment
Useful inequalities
B.
Basic properties of the self-consistent equation for
B.2 and Z" inequalities/
Weight-data alignment partial order
D Proofs of propositions
D.I Proposition 3.1
D.2 Proposition 3.2
D.3 Proposition 3.3
D.4 Proposition 3.4
Linear regression limit
10
E. Comparison Mcl & Ganguli (2021)
10
E.2
Comparison to Wu & Xu (2020)
Structured learning curves
12
Effect of spectral gap
12
F22
Analysis of the D-scale model in the separated limit
14
Proof of Theorem 3.1
15
G.1
Decomposition the test loss
15
G.2
Decomposition of the bias and total variance
16
G.3
Summary of linearized trace terms
17
4
Calculation of error terms
18
G.5
Final result for bias, variance, and error
31

---

Published as a conference paper at ICLR 2022
A ADDITIONAL DISCUSSION OF RELATED WORK
Since preparing the initial version of this manuscript, we became aware of several related recent and concurrent works. Our main contribution relative to these works is the detailed phenomenology explored throughout the main text, but here we provide more detailed discussion of some of the connections between the current paper and other work, highlighting the main similarities and differences.
A.1 ASYMPTOTIC ERROR FORMULAS AND THEOREM 3.1
Alternative asymptotic formulas for the test error of anisotropic random feature regression have been presented in a set of concurrent works, yielding overlapping results with Theorem [31] The result that is most closely related is that of Ascoli et al. (2021). who also study the random feature model with anisotropic input data and target function. They derive formulas for arbitrary convex loss function (generalizing our setup) and then focus
specialized learning scenarios: (1) linear target function with additive noise and quadratic loss, corresponding to the case studied here; and (2) discrete class labels sign(83 x/ /////////)) with label-flipping noise and logistic cost function. Their main results rely on a Gaussian equivalence theorem for anisotropic data, which they derive assuming the Gaussian equivalence principle of Goldt al. (2020a b). and then proceed via standard replica calculation. Another salient paper is that of Loureiro et al. (202I), who study generic feature maps for student-teacher models. A Gaussian covariate model is proposed and rigorous asymptotic solutions are derived for it using Gaussian comparison inequalities, which are shown to agree with calculations from the replica method. The model is general enough to facilitate comparisons to realistic datasets, and numerical evidence and universality arguments support the utility of the model for exactly describing the random feature model we examine here, among many other applications.
Our technical approach proceeds in a substantially different manner, using tools from random matrix theory and operator-valued valued free probability, rather than statistical physics techniques or the replica method. The results could be made entirely rigorous, though here we simply present the pertinent calculations and defer justification of the underlying linearization techniques to future work and to (Tripuraneni al.] 2021a b). Our analysis ultimately yields final expressions with relatively simple form, involving only a single scalar self-consistent equation, which lends itself to more straightforward downstream calculations and analysis (e.g. Propositions [. 3.1 and Corollary G.I. Finally, beyond the total error, we also derive formulas for the bias and variance, which aid significantly in the interpretation of the phenomenology, and are novel results. Interestingly, the order parameter Q from d' Ascoli et al. (202T) (and others) is interpreted as the variance of the student's outputs, but actually differs from the variance defined in Eq. (6). The reason that the bias-variance decomposition is defined conditionally on Because the conditional mean is nonzero, ie. E[ xx] & 0, Q actually corresponds to an uncentered second moment, and corresponds to our term E3 (defined in Eq. (S147)) which differs from the total variance by the non-trivial additive term Ea = Ex [E[ [x] (defined in Eq. (S162). A more thorough discussion of these and related concepts is given by AAdam & Pennington (2020b).
A.2 GAUSSIAN EQUIVALENTS
Our calculations utilize the concept of Gaussian equivalents, in particular
saatt-siinaa-llu--noee surrogate Frln for the random feature matrix F. This approach originates from Karoui (2010) in the context of kernel random matrices of the form KG, = oX, Xz/ng) K₁; aI| X, 12 /no) and from Pennington & Worah ;); Adlam et al. (2019;; Péché et al. 2019) for the covariance matrices F F/R2 studied here. This linearization technique was further developed by Adlam et al.. (2019) for anisotropic covariates (and in the presence of bias), where it was shown to be sulficient for predicting the training error for random feature ridge regression with isotropic linear target functions. In the setting of spherical data and weights. Mei & Montanari] (2019) extended these results to cover the test error as well. In this case, many of the main technical results could build directly from Karoui (2010) owing to decomposition of kernel inner product matrices (Mei & Montanari 2019 Section C.4) that ultimately relies on the orthogonality of Gegenbauer polynomials and cannot (immediately) be extended to the Gaussian settings studied here and elsewhere. For random feature regression with the neural tangent kernel (which subsumes the standard random feature setting), a proof of the linearization outlined for the test error in the setting of isototropic Gaussian covariates by Adlam
2

---

Published as a conference paper at ICLR 2022
& Pennington (2020a). As mentioned previously, extension to anisotropic Gaussian covariates was later developed by Tripuraneni et al. (2021a b), which is the basis for our analysis in this work.
In a parallel and largely independent line of work stemming from Goldt et al. (2020a), nearly identical approach is developed under the name of the Gaussian equivalence property, under which replaced with simple linear Gaussian
possibly nonlinear target function and/or prediction equivalents. This is a crucial step in the analysis in Goldt et al. (2020b): /eerace et al. 2020):(" Ascolii Ceaampe,,Grraee al. (222)) and related work. For example, Gerace et al. (2020)) use this principle (in fact, stronger version they refer to as "replicated Gaussian equivalence" in order to perform their replica analysis of the isotropic random feature model. Subsequently, in the isotropic setting, this principle was rigorously justified using the Lindeburg exchange method under a variety of technical assumptions on the data distribution, weight distributions, nonlinear activation function, and target function (Hu) & Lu (021). Goldt et al. (2020b) relaxes some of these conditions and provides extensive tests of the resulting formulas on real-world datasets. To perform the analysis for anisotropic input data and target function weights, as is pursued in Ascoli et al. [202I), 1), an anisotropic extension of the Gaussian equivalence theorem is required. Substantial numerical evidence and theoretical arguments presented by d' Assooli et al. (2021); Loureiro et al. (202T) for the validity of this extension, but to
the best of our knowledge a rigorous proof in this context has not been established.
A.3 WEIGHT-DAT DATA ALIGNMENT
One of the basic conclusions of our study of anisotropy is that weight-data alignment generally improves performance. Similar observations appear in several recent works, albeit slightly different contexts. For example. Ghorbani et al. (2019) study the random feature model with isotropic inputs, but anisotropic weights, in the case of a fixed quadratic target function and derives an asymptotic formula for the test error in the population limit (ie. >> Ro, R1). For wide networks, n1 > no. the error simplifies and is exactly proportional to a simple measure of alignment between the random feature weights and the target, that is loosely related to the measure we propose in Definition 2.1.
Ghorbani et al. (2021) also study the random feature model in the population limit, and makes the assumption that the target function is sensitive to a much lower dimensional subspace of the input by positing sub-linear sealing of the dimensionality of the relevant subspace. They show that increasing the power of the input data in this subspace generally decreases test error and the number of random features required to learn a function of fixed complexity. Although the learning contexts and the final scaling limits for m, no, n are distinet, these phenomena parallel our main result on alignment (see e.g. Fig. 3b for illustration in the context of the d-scale model).
main contribution of the current paper is the partial order on the space of weight-datz aligmments, which allows us to prove that the total eтror and the bias decrease in response to stronger alignment (Proposition 3.3 Our results in this vein are most directly related to those d' Ascoli et al. (2021), who informally observe a basic relationship between weight-data alignment and performance, though the impact of alignment is also investigated elsewhere, e.g. Loureiro et al. (022 Fig. 2). While these works informally examine concept of alignment, the conclusions about it derive from numerical evaluation of the formulas, and as such the generality of some of the results remains unclear and some of the underlying phenomena are partially obfuscated. For example, it is not clear why the "isotropic" and "misaligned" curves cross each other in of Ascoli et al. 2021 I Fig. 2c): naively, one might expect the misaligned model to always perform worse. Our results provide a nice perspective this behavior: owing to the differing covariate distributions, the two forms of alignment are incomparable under the partial order.
B USEFUL INEQUALITIES
Here we include the statements and proofs of several auxiliary inequalities that we use throughout the Supplementary Material.
B. BASIC PROPERTIES OF THE CONSISSNSI EQUATION FOR
We begin by reviewing the basic inequalities, first given in Tripuraneni et al. 202 b). The definitions of the following quantities can be found in Theorem 3.1
3

---

Published as a conference paper at ICLR 2022
Lemma B.1 (Adapted from w, 71, 2,, ba I 2 0 and
Tripuraneni al. 2021a b)). We have the following bounds:
07 0
0n
Proof. As shown in (Pennington & Worah 2018 for the unit-variance case, simple Hermite expansion argument establishes the relation 2 C. which implies w s(n/C - 1) 0. From Appendix [ and are traces of positive cemi-definite matrices and are therefore nonnegative. From the same equations, it follows that x = F1 2 0. Nonnegativity of æ implies Ia, 2 0 and Ih 2 0 from their definitions in 12 Finally, using the nonnegativity of w, Tl, I. and Ia,b. the immediately gives,
in Theorem expression for By
Or
x 7 p + Fi)(w + 2I1,2)
S 0.
(S1)
0y
Next we show that the self-consistent equation
(S237) admits unique positive real solution for w42 appearing in Theorem 3.1 and defined in
1-77
Lemma B.2 (Adapted from (Tripuranení al. 2021a b)). There a unique real 2 satisfying
Proof. Let 1/x 2 and define,
h(t) (( p( ②) + (1b 6)² + 4yppbb/ -1) + w (1/t))
(S2)
2prh
which is rewriting of eqn. (237 so suffices to show that admits a unique real positive root. To that end, first observe that lim (1/tt) 0 and lim In, (1/t) so that
((0) = w > 0
and
lim h(t)/t = min 6/4) < 0, 100
(S3)
which together imply that has an odd number of positive real roots. Next, we show that is concave for t. 2 0:
2Φ 13 (p=(t 6)² + (xp0//1)377 + I2,(11/t)
p2p
(t)
(S4)
50,
(S5)
which implies that h has at most two positive real roots. Therefore, we conclude that h has exactly one positive real root. To provide bounding interval for this root, we first observe that,
7Φ
lim h(t) mmmmm, + 100
0,
(S6)
p/p plp- 60
so that lt(() can be upper- and lower-bounded by linear functions.
min (1.6) < h(t) sw+s+
pl ol m1,/// 0/b/t.
(S7)
The roots of these linear functions bound the root of h, so we have
min 0/v0
min 1, 6/v}
76 tw+8 + Zx
(S8)
4

---

Published as a conference paper at ICLR 2022
B.2 I AND 7d INEQUALITIES
We now establish some useful properties of the I and I functionals defined in (12 To begin, note that simple algebraic manipulations establish the following raising and lowering identities:
Ia-1,b-1 - + z.a.b and I T 0I2-15
xI
(S9)
Next, we consider how the partial order of LJSDS given in Definition 2.1 leads to inequalities on the I functionals. Letting (I and (I to denote the corresponding functionals with the LJSDs ja and 2l2 respectively, we can establish the following useful lemma.
Lemma B.3 (Adapted from (Tripuraneni et al., 2021a(b)). Let jn 12, so jay is more strongly aligned than H2 (recall Definition 2.7j. Suppose the functions J.9. h + R are such that f()) = (A) and (()) is nonincreasing for all O, then
y (a)( M2 [(((
E,g [X9(
S
(S10)
Eag [A)
Proof. By the law of iterated expectation, we have
Eug (A)lA) En [e Epp [X) E ( 1(1)
E [9]( Ew [A)]
(SI1)
Note that the expectation E, in (SII) over À is the same under μi and #2 by assumption. More- over, the function h(A) is nonincreasing in À by assumption. Finally, observe that the factor Ey (rg(())) [rg( defines change in distribution for the random variable X, since tak-
ing its expectation over À yields 1. Denote a new random with this distribution by A. Then, we may apply the Harris inequality to see
E Jay [g] X
Ep,, [a)] Eus (A)]
(()
(S12)
E3 [9] |
1F [0]
I ENg [A)
1Ex [M(A)]
(S13)
IF Ma [x]
E 142 [99 (A)
Bug, [912]]
E 19g
(A) (A))
ENN (A)
E Engl (A) h((A)
(S14)
Eyra (A)
Eygg [a|A]
Ep,, [A]( Fyp (A)]
Ewa (a]]
(S15)
Corollary B.1. Let μn S p2 and (I == = By, (a)* ( x2)-)) ")
Then, for a S 1 and b b 0,
Eys [gq (1ub)2 E,, [Xq]
(Ta)) 2 0.
(S16)
xd)- is nonincreasing function of X 2 0. Then, setting g = and gh in Lemma B.3 gives the desired result.
Proof. Note that h A @o
Lemma B.4. Suppose the functions f.g. .R + R are such that f()) {g(A)h(A) and h(X) is nonincreasing for all X > 0. Then, if the LJSD is aligned (see Definition 2.1 then Eg [, $
E,, [x
5

---

Published as a conference paper at ICLR 2022
Proof.
E = EplgAgh
(S17)
Ex
(S18)
9(A)
Ex
(M
(S19)
Eulgi
9(A)
((A)
S E
Ex
(())
(S20)
Eu[g]
Ep
Ex[g] BallAg|EAlf),
(S21)
where E2 [qA]\]]] is nondecreasing in À because μ is aligned, so the inequality again follows from the Harris inequality.
Corollary B.2. If p is aligned, IT, 0.6 S II-11, 1+1.8"
Proof. Take g : A (x zA) and h A + 1/A in Lemma B.4
C WEIGHT-DATA ALIGNMENT IS A PARTIAL ORDER
We restate Definition 2.1 for reference, and prove that it defines partial order. The definition and proof are identical to those of Tripuranen et al. (2021a b). but differ in notation so we repeat them here for clarity.
Definition C.1 (Restatement of Definition 2.1p. Let μn and μ2 be LSDDs with the same marginal distribution of X. the asymptotic overlap coefficients are such that E,g [Aq]A] /EEz [Ag[A] ER, [q] /E,, [g|A] is nondecreasing in X, we say that μr is more strongly aligned than #2 and write H1 S P2- Comparing against the case of isotropic weight distribution, pé, we say μn is aligned when Jn1 S Mg and anti-aligned when μ4 2 μég-
Proposition C.1. Definition 2.1 is partial order over over weight- alignments p.
Proof. Reflexivity is satisfied [.,.g///// [g] is nondecreasing for all μ.
For antisymmetry, we see μ1 S P2 and #/2 S imply Ey,, [g/A//BB Bug [g is constant in À as it is
nonincreasing and nondecreasing. However, setting E,,, [g|2] cE [ and taking expectation over À and rearranging yields 1 E,,, (e)/Bxxa [g] C, in fact E,,, [g E,ca [q] Assuming that μi and μr are absolutely continuous (the case where they are sum point masses is similar), we can write their densities as (). ps (A)p,(q(A) By assumption P1 (A) P2 (A), so it suffices to show Pı (g/A) = P2(g[A) almost everywhere. Next note
E,, [g|A] [ = f Je
(pi(gl))) (2( dy,
(S22)
we have that pi (g(A)) - (2( = 0 almost everywhere.
Finally, for transitivity assume μl S #2 and
#12 14,, then
E [g|A]
E,, [g|A] [a|i
Eus A pua [
(S23)
E
so Ep,, /q ig|A] is the product two nondecreasing, positive functions and is thus also nonde- creasing.
D PROOFS OF PROPOSITIONS
D.1 PROPOSITION 3.1
Proposition D.1 (Restatement of Proposition 3.I. In the setting of Theorem 3.1 the bias B, is nonincreasing function of overparameterizatiinn ratio d/bb.

---

Published as a conference paper at ICLR 2022
Proof. Recall from Theorem 3.1 that the bias is given by
B₁ = o
(S24)
where r is the unique positive real root of the self- equation,
- 7
(S25)
+ IT,1
Differentiating (S24) with respect to 0/v gives,
0Bp 1/2 a 0(0/0)
dx 2vh²
I
(S26)
Oup
Since Lemma B.1 gives I
0, it suffices show 20
S 0, which immediately follows by
implicitly differentiating (S25) and simplifying the expression.
dr Oy
pat I1,1)
50,
(S27)
s γ + m) + vII,)))
where the inequality also follows from Lemma B.1
Therefore we conclude that 0(5/6)
aB
S 0.
L
D.2 PROPOSITION 3.2
Proposition D.2 (Restatement Proposition 3.2 the setting of Corollary G.7 Jnd the overpa- rameterized regime (1 < Φ), the variance V is nonincreasing function of overparamettriization ratio 6/ vb.
Proof. In the overparameterizee regime, Corollary G.1
gives the expression for the variance as,
II2 (o? I1,2)
(o? + +
(S28)
and, since the self-consistent equation x w+I1 is independent of 1/s we have dz Dy
0 and,
OV, 0o + 20,
(S29)
v6-
which implies that the variance is nonincreasing in the overparamettrrized regime.
D.3 PROPOSITION 3.
Proposition D.3 (Restatement of Proposition 3.3). Let Pı, u2 be two LJSDs such that pr S #12 (see Definition 2.7 Then Bi, < Buy En, < Epg and B /V < Buz/Vag.
Proof. For the bias, Corollary B.1 implies (I),2) S (I)2)2 and therefore B,, S B
For the test error, we use the explicit expression for the variance from Eq. (S378) and the identity I222 = 1If E which follows from Eq. (S) to write,
E, = Co + C. + C2I
(S30)
7

---

Published as a conference paper at ICLR 2022
where the C 2 0 and depend j only through the marginal À (i.e. they are independent of the weight distribution):
Co
p
Φ 07
v dz
2
(w 2I I1,1) + - ( 20
(S31)
0
p
v dz
(w +
وI, (w + I1.1) + - + eII,2)) 20
(S32)
① 07
dr
0²
0 x
C2 Φ dn
(w + (I1.2)
(S33)
1 dx
0²
07
6²
p ① 07
I2
(w + (I1,2)
(S34)
du
x
B7
pi 0y
dr
WT (w 0I112) +
(1 + p(T1/// Riw + 2I,2))
(S35)
x
pz
dr
① (1+ pr
17 oy -
I2 +
(S36)
pa
2 0.
(S37)
It is now straightforward to write.
Eu2 - EE,, =
(S38)
= C1
+2 (4
(S39)
20,
(S40)
where the inequality follows from Corollary
B.1 Similarly, write,
Bag Esp - Emg = Co
(4f2)
(II
+ +
(T + C2(T1.)) - Co - CI --
-2(TT,)
B,n
(I,2)2
(Ii,)2
(S41)
(I
(I12)
Col
- 1) + +1
[I 1,1 )2 - (1
(S42)
(I
(
00,
(S43)
where the inequality follows from Corollary B.1 and from Lemma B.3 with g Gi( + Az)-1
and h A > (Ø + 1x)-1. Finally, using Ey,. = BR, + Va., the above implies B /V., S B Buz/ V
/
p2
D.4 PROPOSITION
Proposition D.4 (Restatement of Proposition 3.4.. If the LJDD is aligned (see Definition 2.1 then, in the setting of Corollary G.Il the test error has at most two interior critical points as a function of the overparameterization ratio d/v.
Proof. From Corollary G.1 there is critical point at the interpolation threshold d/v = 1. Therefore suffices show that there at most one additional interior critical point. Focusing first on the overparameterized regime Φ > 4h, the test error reads,
II22 (o? I122),
Ep II +
( + +II1) +
(S44)
w ΦI,,
and, since 25
dE
1/22 (o² + I > 0
(S45)
(6
which implies that the test emrrr is monotone decreasing in the overparameterized regime.
8

---

Published as a conference paper at ICLR 2022
Next, let us consider the case ø < vb. In this case,
E oI
3 w6 (0 (02 IT,1) + 2I2,21
(S46)
so that,
E
Oub
1 Oy dz
Ox i_
I
1.2
(vb 6)² (0e + I
Φ
+
1/ Φ rr
Φ
Ox
dr
0
I 1.1
+
Jri dz
dx 0
(xI
(S47)
(02 + I + dr
Φ dr
I 1,2
Φ
0
3
+
(rIg 2,2
(S48)
(v 6)
db
1 dz
dr
0)² (o? + 1 + dr
(v
-20I2
1
2,2
+
I
2.2
2xI3
3.3
(S49)
(0 0) (0g + )
dx
1 I
(S50)
0b 1 Φ
2,2
8
2 + 1
+
$
2.2
(S51)
(0 2)²
1Φ 6) w + 611
Therefore we see that
DE by
= implies
0. + I
= x(w + I1,1) =1 (w + 2I1,2)
(S52)
I
or, equivalently, g(x) = 0 for
of + I xlw + I211.
g(x) = 1 - (
(S53)
I
First we note that has at most one real root since its derivative is never positive,
0((x)= = 20I o² I
1-2 0² + +
1,1
+ (w +II,))
(w + 2II,1) + xI222
(S54)
2,2
3,3
0² + 9
0² + I
-
111
2((w + +0I112)
(S55)
I
3.3
=2 0² 1
1,1
2 - (w + 2II
(S56)
(I 2
2 0² I
(D2Ia (w + +Iz12 x
(S57)
(T22)² 2
2 02 I
(0 ( (w (w+ (
(S58)
(I 2
S 20² of + +29
1,1
TI I1
(S59)
2
00,
(S60)
where the last line follows from Corollary Binssince since we assuming y is aligned.
Next, regarding x as a function of 6/v, we consider the interval xx) for x- = (0///- = 0) and x4 2/0/vb 1). From the self-consistent equation for x, we immediately see that x4 (w + +1,1(x4)) = 1 and x_ = 0 so that
+I
g(0+) = (w + +II122
(S61)
I/1
< O.
(S62)
9

---

Published as a conference paper at ICLR 2022
and
0- + B 1911)
g(x-) = - (w + B2 [
(S63)
1x
Observe that,
[= w + E
g(-)>
0e oe
En 19
(S64)
Therefore, from the intermediate value theorem, we conclude that has no real roots in (a:,, 2x+) for o oe and exactly one real root if of < o².
E LINEAR REGRESSION LIMIT
To reduce to the linear case, we need to take tb - 0 and (zz - x, in which case we have that ? = ( = p - and w + 0, so that
1 f1 +
T1 + and
(S65)
7
so that
7
I1.1
(S66)
& pun Φ + x5
(S67)
E. COMPARISON TO MEL & GANGULI 2021
To compare with Mel & Ganguli 2021 note that Φ = 1/a,7 1/01, == = = -/,, so we have
22i00
x ② E
(S68)
À + 52
2 x
A Elg prppless
(S69)
$2
which is the expression appearing in Eq. (8) in MMel & Ganguli 2021 the test error, note that
To compare expressions for
8x
(S70)
07
7 + ΦI
and so,
O% Pf OX 06/r ddy 1 dr
(S71)
(S72)
(S73)
x² By
(S74)
x(7 + xI1,2)
10

---

Published as a conference paper at ICLR 2022
so that.
E == + 1
(II,, oz.) I²I22
(S75)
Pʃ
1
oI 1 (2 x + Le I2
2
o 1,2 +
(S76)
Ps
PJ
2IH,2 + 6I 21 - x(7 + +0I1,2) + - I2,
(S77)
Pf
Pj
2Iو;2 + oI 1,2 (1 - p,) + o2
1
I212
(S78)
Pf
Pf
[T o
(S79)
In contrast our conventions, the error F in (Mel & Ganguli 2021) does include an additive constant E+a?
induced by the label noise, and also normalizes by the total output variance i.c. F = Varls]
Taking
this relation into account and using the definitions of I and I", and finally translating the notation
via the substitutions & 1/a, Aq v (SU" w)² o²
|vl"
fn:
+ fa. we find
Vargl]
Vargl
JF E + 2f Var [y]
(S80)
o² Var y
2
o²
A (GAN))
+
Ey,
+
En
(S81)
Pf
Var
[
+ A
Var [
27
(()
1
= fn +
E
2
+ fn
Ep
(S82)
Ps
+ A
which is Eq. (6) of (Mel Ganguli
2021).
E.2 COMPARISON TO WU & Xu
2020
Wu & Xu 2020) study the case of anisotropic regularizer:
Bx = (x + XΣw) X y
(S83)
with n samples. p features, X E RxPP and p/ n + 7. After simplifying the error expression they arrive at eq. 3.1:
1 E (o - x B.) = 82
1 -tr (Ea/m XNo + +1) - -En// (N +
(S84)
22 + tr
Enjwr XNu + +A1) Eng (X /wu + AT) -
(S85)
Setting Enp + must give the expression for isotropic regularization, thus the effect of the weighting matrix Enr can be accounted for by just changing the parameters of the isotropic model. The effective feature covariance is Σ + En/w and the effective weight covariance is Eg + Ews.
The error expression given in eqs. 4.1.4.3 is
E
(g ( x T.))
m' (-))
1B
+02 x² (h- m (-A) + 1)2
gh
+
(S86)
m² (-X)
where
X 1 >E h m (-2)
h
(S87)
m (->)
122
=
7E
ml (-2)
(S88)
m² (-X)
(h. m (- + 1)2
11

---

Published as a conference paper at ICLR 2022
In our notation, the predicted output input is
1
(
3
X + Ecr
F F 7mm
= F I (x)
(S89)
VTo
111
111
(1 xxX
1 X r
B X + +
X X + 7mm
(S90)
mn
na
n00
-1
B X + ctr
x-
xx + +nIno
-x x
(S91)
nno
n2
" T (XXT + dn
-1
T
(S92)
where X has
normalization. Thus translating our notation involves setting Φ + 7,
V samples
7 1/7, E + De/ws + h, Eg TEuo, and q - >g. In this new notation, our equation for reads
2 x
h
x
y
(S93)
+ h
which shows + +ym (-A), and therefore
Hym! -
22m (-)). Next, note that
0A/7
dx
22
7 + $I1,2 I22
(S94)
07
IT.1 - -0I1.
(S95)
7+ +0112
It,1 +7
(S96)
7 7+ 2I1,
1/x
(S97)
7 + 0I1,
Ox
(S98)
x2 07
So the full error is
dr
E 6I
2I2,I22.2 + J2I22
(S99)
Oy
1 dr
dr I2
07 12
I1,2
0e 0g
(S100)
1 Or
2I + 022
1 dr
1
(S101)
x² Jy
x2 dy
Ox
(0I) + +o2)
(S102)
x2 0yy
m'( (-
hg
710
+ +0²
-22
(S103)
(->-
(1 m( ))
which, after removing the additive shift, matches the expressions given in (Wu Xu 2020) eq. 4.1.
F STRUCTURED LEARNING CURVES
F.1 EFFECT OF SPECTRAL. GAP
Here we demonstrate that a large gap in the spectrum of Σ can induce steep cliffs in the learning curves as a function of the overparameterization Φ/v/ v/:
Suppose there is gap in the spectrum of Σ of size g. That is, there are X_ < A_ such that there is no cigenvalue À (A_, A+) and d x
g. Assuming ø and μ is aligned, and working in the
12

---

Published as a conference paper at ICLR 2022
noiseless ridgeless limit, will show the slope of the learning curve ((//) negative for small
log Eg becomes arbitrarily
From Theorem
3.1 2, T1 satisfy
1 1I
(S104)
W + 21 Φイスλ
V( - x)² + 4m +
(S105)
207
min(1.
Since S
(Eq.
S8
for a > stays finite in the ridgeless limit y 0,
YT, - b/b Φ
-
(S106)
24
We have the numerator
7TT + min(1, 2/v),, and
= min 11, Φ
w + ΦR
(S107)
+ xd
Since x is not solution for 1/ Φ oc, we can change variables to giving
min 1, Ø
(S108)
which implies is a continuous decreasing function of 6/v (keeping ø fixed). Taking the limit of (S108) directly shows that Tmax = lim 7 = oc, while Tmin == limø/e-4s 7 satisfies
+ E
(S109)
7iin
Ymin
By the intermediate value theorem, y takes all values in the interval (fiiin 20). For & < 1, using Smin + < 1 we obtain 7min S w 1-60
We assume that w م $ X_ so the previous bound gives Amin I A_ and thus y attains all values (A_, In particular, there some < Φ/v < such that 7 (0/vb) A At this point, differentiating (S108) gives
0 05
1
W E
(S110)
7
( X)²
1
d
__ (5 x x p -
S マ/
+7
P (A A+)
(S111)
(5 + x4)
1
Vg
(S112)
(Vg 1)²
Since - 1
@loga ((0/v)
we get
1
d log x
(S113)
W
V
3 (0/b)
(v5-1)"
For large spectral gap y this tends toward
A+A
i log x
2
(S114)
0 (b/v)
13

---

Published as a conference paper at ICLR 2022
If the nonlinearity w is small compared to the middle of the spectral gap V undergoes large fractional change as a function of the overparameterization ratio 1/vb.
To see how this affects the test error, we can use the lowering identity Iz- 1.-1,6-11 = 6 a-1. 1,6 + xI to write the ridgeless error expression from Eq.
SS46) as
F
+ II2.2
(S115)
1.2
1
1
+
1,1-
(S116)
1/
V
④
So write
0
a (6/b)
log
F
1
00/ v))
log
I
1.1
(S117)
+
log 7
(S118)
a (0/
For general a, b, we have
2 (7+2)0+1 g
a (6/v)
2 log. (
E
log I -b
(S119)
(0/
E
(5+
Specializing to a 1, and using the fact that A Ey [g|A] is a nondecreasing function of (guaranteed since q is aligned), we may apply the Harris inequality to obtain
7+4
By [c1x1)
① O1p
(
Ölog.r x
Ex
log IT,1
(S120)
a (0/1b)
Ex
Ey 19/A1)
(+++))
dog a (0/0))
A
EA
(S121)
2 log a (0/
p(A X+)
(S122)
X4),
(S123)
which implies
2 log (6/v)
w
0
Fry
2
log I
(S124)
1b
4 Φ
3 (0/v)
v))
/b
A
2
+
P (A x+)
(S125)
In particular, of = 0, then
boo E i (6/+)
2b
1
((>>
(S126)
Thus as w + 0 the learning curve becomes arbitrarily steep at the critical value x = 6/ /24A
F.2 ANALYSIS OF THE D-SCALE MODEL IN THE SEPARATED LIMIT
We will consider the d-scale covariance model:
An = Ca"
Pn d'
n n= 0,1,
(S127)
where C' is chosen so that
d-1
Ca = 0 11-a" a
1 1=s [ = 7 Σ
(S128)
d d 1
n=0
14

---

Published as a conference paper at ICLR 2022
We will obtain expressions for in the limit of small X. Consider the ridgeless limit of := 6/2:
An
w Σ
Pn
(S129)
An
max (Ø, 16)
Suppose, w sits between the scales Ca2, Cos+1 To enforce this constraint, we will take w - was+ where @ is constant independent of a.
The a scaling of Ý will depend on the value of max(á, 10). Discarding the second term in (S129) we obtain max (Ø, 1)) w S 5, and thus the lowest possible scaling for is CJ+ 1 Substituting
this ansatz into ( $129 and taking the limit O, we obtain
1
Σ
Ca
(S130)
max (0, v)
Cj+galt + Ca"
a00
1 j j+1
(S131)
Solving for Ý gives 5
1-max(0, w. For other values of max(á) rb), 7 may have higher scaling,
max( (..))
ie. 7 Cga with k S j. Substituting and solving for y we obtain द max( (
max(0,0)) Ag. Thus we
obtain the following self-consistent solutions for 5:
max(c.e)
W
max (o, v- < J+1
max(da 1. L+1 max(
9
(S132)
AR
K+I < max (db, 1b)
max(
Thus 7 takes on the scale of a single eigenvalue A for a range of overparameterization ratios corresponding to I+I < max
[ -.4 To understand what happens at the transitions between
these regimes, we can apply the results from the previous subsection F. for generic Σ with large spectral gap. In the notation of F.T the D-scale model has a spectral gap between each pair of consecutive scales of size g = / = Caa /Ca 1/a and as a consequence, 7 will exhibit near infinite slop as it passes through the middle of a gap A = Cai+1. Comparing to the d self-consistent solutions 31122 these transitions must happen at the critical values max(ó, e)) = x+1 for k < j. At these transition points, the error exhibits steep cliffs in the parameter regime descried
G PROOF OF THEOREM
The proof closely follows the methods described in (Adlam et al. 2019 Adlam & Pennington 2020a b Tripuraneni et al. 2021a]b). Indeed, precisely the same techniques from operator operator-valued free probability used in those works apply here. The main and only difference is the anisotropic weight covariance Σg, which changes the details of the computations but not the arguments justifying the linearized Gaussian equivalents and the application of operator-valued free probability. We therefore refer the reader to those previous works for an in-depth discussion of methods and merely focus here the details of the requisite calculations. Throughout this section, we use tr to denote the commension-normallinn trace, i.e. (r(A)= (rA) for a matrix E Roxn
G. DECOMPOSITION OF THE TEST LOSS
The test loss be written as.
Ex. (1xx)(1-((x)) = E1 Es + Es
(S133)
with
E, (xxx))r(((x))((x]]
(S134)
Fg = 2 tT) KJ K (r-yTTy(x)
(S135)
Eg K -
(S136)
15

---

Published as a conference paper at ICLR 2022
Recall the kernels K ((X,)) and Kx = [XX,,x x) given by, Kx - F f.
F + 7Im
K
and
(S137)
R1
Using the cyclicity and linearity of the trace, the expectation over x requires the computation of
Ex Xx
Exy(x)
(x)(x)u(x)
(S138)
As described in detail in (Tripuraneni et al. 2021a Adlam al., 2019 Adlam & Pennington 2020aa Mei & Montanari 2019), asympotically the trace terms E1, E2, and E3 are invariant to linearization of the random feature vector /.
f+1 Ain
Wx V 11
(S139)
V 740
where 0 R vector of iid standard normal variates. Similarly, we will take the linearization of the training features be V WXW++ + vn - (Ô where 1g"1xm has standard normal components. yTo The expectations over are now trivial and we readily find,
K 2 P WEWT
FT
+ (),,
(S140)
ni
no
Exv(x) vp
3 WWTF F
(S141)
non 1
[x)(x)x(x) - -T
(S142)
no
Next, we recall the definition, Y = TT X/ no + e, and, using the above substitution, we find
Ex [y = X ExX + I
(S143)
vp
Ee Y Exy(x)
X E
(S144)
3/2
ng n2
Putting these pieces together, we have
E1 tr(ExE
(S145)
En Ez21
(S146)
Eg Es1 E32
(S147)
where,
vp
Ez = -2
Etr (x [ FK
(S148)
3/2
no nh1
E31 = af 1tr KK 11 1zドー1
(S149)
1
Etr (K
L'gK" K 1x" Σ
(S150)
n1
and,
P F
WWW F+ 71 7- F
Σg
(S151)
m
G.2 DECOMPOSITION OF THE BIAS AND TOTAL VARIANCE
Note that is sufficient to calculate the bias term given the total test loss, since the total variance be obtained Vy Ex; By. Following the total multivariate bias-variance decomposition
16

---

Published as a conference paper at ICLR 2022
of (Adlam & Pennington 2020b), for each random variable in question we introduce an iid copy of it
denoted by either the subscript or 2. We can then write,
By E(x.a) (y E ( e))
(S152)
E(w X1.e1) Be B.ss
i(x; W1, Ew 0(x; W2: (2))
(S153)
tr(EgE)
+ E21 + Hooo
(S154)
710
where an expression for E21 was given previously and Hooo satisfies
Hooo = Ex;(;; W1, (x; W2, 62)
(S155)
where the expectations are over x, W1, E1, W2, X2, and 62. Recalling the definition of g.
(x: X,, ==
X; w) (X), xX;
(S156)
and the techniques described in the previous section, it is straightforward to analyze the above term. First note we can write,
Ex K (x
X2;
PI W W.W,, Pr non
(S157)
Here we have defined F11 F(W1, X1) and F22 F(W2, X2). Now proceed to calculate Hooo as
H0or : 62)
(S158)
= =x,(x, X2; (2) W2) (/K (, W;; W)
(S159)
=Btr(K(X2, X2; W2) X X, K X1;W) x; W)K(x, W2))
(S160)
P Etr (K2² X2 E X Kj F W, WW,, F22)
(S161)
nin
=E4,
(S162)
where in the second-to-last line we have defined K11 Xi; and K22 =
K(X,,Xy, X2; W2).
G.3 SUMMARY OF LINEARIZED TRACE TERMS
We now summarize the requisite terms needed compute the total test error, bias, and variance after using cyclicity of the trace to rearrange several of them. In the following. we slightly change notation in order make explicit the dependence on the covariance matrix Σ. To be specific, whereas above we assumed that the columns of X, and X2 were drawn from multivariate Gaussians with covariance Σ, below assume that they are drawn from multivariate Gausssians with identity covariance. This change is equivalent to replacing X1
X, and X₂ E1/2X, in the above expressions. We utilize this definition so that X2, X2, W1, W2, and all have iid standard Gaussian entries. From the previous computations, we can now write the requisite terms as,
Σg =
P non?
F. W.WW
FT Fi F11 +
(S163)
nf
vp
En = 2
tr X x T Fn
(S164)
3/2
no
Es1 = ,ttr (Kil ΣzK
(S165)
1 Iir (Kjz Eg K X T x
Eaz =
(S166)
nip
Fa
moni
z
F K 22
X m / S
K F
(S167)
Es = tr (Σ'')) + Eز + E' + Laa
(S168)
1
By = tr (Σii} E2 EA
(S169)
Ti0
Vs: Fx Bs
(S170)
17

---

Published as a conference paper at ICLR 2022
G.4 CALCULATION OF ERROR TERMS
To compute the test error, bias, and total variance, we need to evaluate the asymptotic trace objects appearing in the expressions for E21, E31, E2g. and E4, defined in the previous section. As these expressions are essentially rational functions of the random matrices X, W. θ Σ, and Σg. these computations can be accomplished by representing the rational functions as single blocks of suitably- defined block matrix inverse the so-called linear pencil method (see Far ct al. 2006) and then applying the theory of operator- valued free probability (Mingo Speicher 2017). These techniques and their application to problems of this type have been well-established elsewhere (Adlam et al.)
2019; Addam Pennington 2020a b), we only lightly sketch the mathematical details, referring the reader to the literature for a more pedagogical overview. Instead, we focus presenting the details of the requisite calculations.
Relative prior work, the main challenge in the current setting is generalizing the calculations to include an arbitrary weight covariance matrix Eg. This generalization is facilitated by the general theory of operator-valued free probability, and in particular through the subordinated form of the operator-valued self-consistent equations that we first present in eqn. (S20T). The form of this equation enables the simple computation of the operator-valued R-transform of the remaining random matrices, W, X, and O which are all iid Gaussian and can therefore be obtained simply by using the methods of (Far al. 2006). The remaining complication amounts to performing the trace in eqn. (S201). which asymptotically becomes an integral over the LJSD μ.. While this might in general lead complicated coupling of many transcendental equations, turns that the trascendentality can be entirely factored into single scalar fixed-pon equation, whose solution we denote by (see eqn. (S237)) and the remaining equations are purely algebraic given J. To facilitate this particular simplification, it is necessary to first compute all of the entries in the operator-valued Stieltjes transform of the kernel matrix K, which we do in Sec. G Using these results, we compute the remaining error terms in the subsequent sections.
As matter of notation, note that throughout this entire section whenever a matrix X, X1, 1, or X2 appears it is composed of iid (0, 1) entries as in Appendix G.3 This differs from the notation of the main paper, but we follow this prescription to case the already cumbersome presentation. This definition of X allows us explicitly extract and represent the training covariance Σ in calculations.
G.4.1 K-1
The NCAlgebra Mathematica package (NCRealization method; algorithm described in Helton et al.. was used to generate the following matrix pencil QK k=?
2006
m
V NyR1
TPX
0
0
0
0
Ty/o
VPW
7
0
0
0
0
VRi
0
0
I 100
1/2
0
0
0
0
W
Lno
0
Es
0
QK-1
VP
0
O
0
Tno
11/
0
0
0
0
0
Ino
0
0
0
T
-11/2
0
0
0
0
Ino
X
mmg
0
0
Im
(S171)
This matrix specifically chosen so that inverting [Q* "QT and taking the normalized trace of its first block gives exactly 7 frk-1, the quantity of interest. Computing the full inverse of [Q T via repeated applications of the Schur complement formula and taking block-wise traces shows that
GK 7 (1(K-1)
(S172)
ò tr (5554/2XK
G =
(S173)
no
K-1
(S174)
18

---

Published as a conference paper at ICLR 2022
Vptr Σ 12 FK XX)
GK-1
3,3
G
1
(S175)
Vnoii
vp (LWTFKK-- PK-1X]
GK
= GK
(i(21/2)
(S176)
Vnoui
/vp ET/ R- R-IW))
GK-1
G
G
(S177)
m EWTR--W R-!W)
T/ptr
GK-1
G
(S178)
n1 fr (E FK-IX
tr(2g21122
G
(S179)
Vngun
VP
ir (EgEWW T FK- T E1/2)
(T
G
(S180)
Vnou1
VP
Vptr (FK- (T
GK-1
3,4
5,6
(S181)
/p tr (TVPWTFK* FK-
GK-1
4,4
=
Gk
(S182)
Vngui
Tvptr fr k (
GK-1
(S183)
tr (I K K-'W))
((()))
GK
(S184)
7,
Vnoni
VP
fr (E FK FK-1X
fr(EE
G
(S185)
n
vp
Vptr (X -XT)
G
GK
(S186)
no Vptr tr [EXK-IXX
K-1
(S187)
no tr (2 /2XK X 1 1/2)
GK-1
(S188)
no
& (EşEXK- 1x (11222
KK-
8,5
(S189)
no vp fr (K-1X" XT- X)
GK-1
(S190)
3,6
nnc G ( -OKK-1X 1XT)
KK1
G7.6
(S191)
P0p fr 1/ -XX-IXxT!! (x1112
G
(S192)
no
GK-
GK-
GK- =1
(S193)
G = 122
(S194)
where GK = id, @ & K ')TI- E Mc(C) is scalar 9 matrix whose i.j entry G.K is the normalized trace of the (i.j)-block of the inverse of [Qx=']] We have also defined K FFT + TTn (note that K is m while R is n n1). It straightforward to verify that when R1
19

---

Published as a conference paper at ICLR 2022
the ng. n1,
limit is eventually taken, each entry of G is properly scaled and will tend toward a finite value.
We aim to compute the limiting values of these trace terms no. R1, 00, as they will be related to the error terms of interest. To proceed, recall that the asymptotic block-wise traces of the inverse of QK can be determined from its operator-valued valued Stieltjes transform (Mingo & Speicher, 2017). The simplest way apply the results of (Far et al. 2006 Mingo & Speicher, 2017) to augment Q to form the the self-adjoint matrix Q"
104
QK-L
(S195)
QK
and observe that we can write QK
as,
QK² Z
Q w.eee
(
0 19
0
12 1
)
1
(S196)
19
0
Q
Q
where
VT C 7yn
VOX TVRO
vPW T
0
0
WT
0
0
0
Qw.xe
(S197)
0
X
0
1000
0
0000
000
0
000
0
1000
1//2
0
0
0
Q
0
0
0
1/2
00000
0
(S198)
0
00000
0 00000
0
1//2
0
0
and the addition in (S196) performed block-wise. Note that we have separated the iid Gaussian matrices W, X, θ from the constant terms and from the E'dependent terms. Denote by GK- e (C) the block matrix
OK- ck-==(c
[G*-y]] (R--
O GK-1
idis @ ir (Qx-1))
(S199)
and by O E Mis(C) the operator-valued Stieltjes transform of Q Using S196) and the definition of the operator-valued Stieltjes transform G Gog-1 + we can write
ak- idis क Q
@K Qw.
Q
- + - (2)
(S200)
Thus using the subordinated form of the equations for addition of free variables (Mingo & Speicher 2017, section 9.2 Thm. 11), and the defining equation for Gk the operator-valued theory of free probability shows that in the limit no; n1, m co, the Stieltjes transform GK- satisfies the
20

---

Published as a conference paper at ICLR 2022
following 18x x 18 matrix equation:
nK-1 GK- - - N., (G
= id @ tr 2 RK x Q 15- '7
(S201)
where RK- W. ( (GK*) E M1s(C) is the operator-valued R- R-transform of Q W.e. Note that (S201) a coupled set of 18 x 18 scalar equations and thus eliminates all reference to large random matrices. To see this, note that Z, G RK W.,.e @ ") are all scalar-entried 18 x 18 matrices. The right- hand side of (S201) is defined by expanding the inverse to obtain 18 x 18 block matrix whose blocks involve various rational functions of Σ, E. and the scalar entries of Z, GK- R..xe x (GK"). Finally one computes the normalized traces of these blocks, giving scalar values and eliminating all reference to random matrices. Below, when writing out these equations explicitly, we will use the fact that traces of rational functions of Σ, Mp tend toward expectations of the corresponding rational functions over the LJSD μ.. Both here and in the sequel, to ease the already cumbersome presentation, we use G to also denote the limiting value satisfying (S201).
As described in Adlam & Pennington 2020a b), since 1 is a block matrix whose blocks are iid Gaussian matrices (and their transposes), an explicit expression for RK-1 (G"")) can be obtained through covariance map, denoted by (Far et al., 2006). In particular, 1) Ma(CC) - M2(C) is defined by.
[n(P)] Σ (i, ((),
(S202)
where ag is dimensionality of the kth block and (i,, 1; denotes the covariance between the entries of the blocks ij block of @ and entries of the kl block of Q W.xe0 Here d = 18 is the number of blocks. When the constituent blocks are iid Gaussian matrices and their transposes. as is the case here, then RK-1 wxe. = (Mingo & Speicher 2017 section 9.1 and 9.2 Thm. 11), and
therefore the entries of RK W.xe can be read off from eqn. (S195). To simplify the presentation, we only report the entries of RK e. ( (G*")) that are nonzero, given the specific sparsity pattern of GK The latter follows from eqn. (S201) in the manner deseribed in (Mingo Speicher 2017 Far et 2006). Practically speaking, the sparsity pattern can be obtained by iterating an eqn. (S201). starting with an ansatz sparsity pattern determined by Z, and stopping when the iteration converges to a fixed sparsity pattern. In this case (and all cases that follow in the subsequent sections), the number of necessary iterations is small and can be done explicitly. We omit the details and instead simply report the following results for the nonzero entries:
RK-1 R....
(Gx
0 (RK
RK- RK-
(S203)
RK
"
where,
GK (5- - vpGk
- 7
)11
(S204)
= VDGks=
[
[
)
(S205)
7
= vGK (5-
|
1)22
+
V
(S206)
7
1145
= vpG
(S207)
vpG
[RK-1
")
(S208)
7Φ
= VDCK
-K-1
)1833
(S209)
7Φ
21

---

Published as a conference paper at ICLR 2022
zero Owing to the large degree of sparsity, the matrix inverse in (220T) can be performed explicitly and yields relatively simple expressions that depend on the entries of Gk and the matrices Σ and Vig. For example, the (16, 4) entry of the self-consistent equation reads,
and the remaining entries of R (GK (
G
id @ fr 2 RK (G -)- ')''
R
(S210)
16,4
= tr vD
Ei (Ino
+ LG G25 2)
1,1
(S211)
9/vP
00
Eu 11+ 2
(S212)
(S213)
VP
where to compute the asymptotic normalized trace we moved to an eigenbasis of Σ and recalled the definition of the LJSD μ and the definition of I in Eq. (12). The remaining entries of the (S201) can be obtained in a similar manner and together yield the following set of coupled equations for the entries of GK
G
(S214)
G (- 1) P)
pG
VDG K-1
7
GK-
70
222
(S215)
JG (n - 5) - -06 (V 1,5 -1)
VPG
GK-
G3,6
Ep
(S216)
ApGR. G35 - 70
AVDG
GK
Ep
(S217)
ApG G 96
GK
En
(S218)
AppGIT G 70
TAVD0GI2
G3
(S219)
ApGGTT G - 700
GK-
Ey
97p
(S220)
vp (Mpoti -1 GK- + 7
aVACK,
G
(S221)
ApGRT - G +
GK-
8.3
Ep
vp (ApofT G + +
(S222)
GK- = Ep ApCkT GK- +
(S223)
G
1
Ey [V
(S224)
G
(S225)
-GK- (-C + 17 + p) + pC VOCk- -7
VAGGK GK-
G
GK-1 = =1E,.
(S226)
-pOK " 700
VApPOKT
G3
CK!
G = -By
(S227)
ApG Gk2, +
22

---

Published as a conference paper at ICLR 2022
7V
1,3
G655
GK
Ap
622 70
(S228)
TVADOOLE -1
GK
5,3
6,4
CK
Ap G 770-
(S229)
gyVAΦ
G733
GK
485
GK
(S230)
(ApGT 22 + 76)
GK
1
(S231)
8.6
ApG '22,2 + 70
G7,7
8
kK-1
G9
=1
(S232)
GK-
3,3
44,4
GK-
5,5
GK- 6,6
E
70 -,pG - - -761
G
(S233)
where we have used the fact that, asymptotically, the normalized trace becomes equivalent to an ex- pectation μ. After eliminating G and G from the first two equations, it is straightforward to show that
V 6) + 4rpdn P 10 -
1 7 = ti(K = - G1,1
=
2017y
(S234)
1
1
1 2 ( - }
f ti(k 11)
? 222
+
(S235)
7
Φ
T2 = ir( x no
1/ E/ K-k)--1- 1) = TI
(S236)
where have used the notation Ti and 72 from (Adlam & Pennington 2020a b), and is the companion transform of Tı, and where x satisfies the self-consistent equation,
(v- 4npdrr////// v-
7TL
2
(S237)
J,1
w + IT,1
Here utilized the two-index set of functionals of μ., La,s defined in Eq. 12) Note that the product 71 is simply related to I,
I o
(S238)
so that, given æ, the equations for the remaining entries of GK completely decouple. In particular,
In,1 VpCK,
KK
G3,6
(S239)
7Φ
VPGkiT I1.1
K-
(S240)
7Φ
CK-1 -K1
VpGkt Io.
(S241)
G
VDG 'I
(S242)
Io
G
(S243)
Vp
T GKS
G
2.1
(S244)
G
1.1
(S245)
23

---

Published as a conference paper at ICLR 2022
I 2.1
G1,1
(S246)
70
I 0
G87
(S247)
VpGr,1 Ggg
Gg1
GK-1
(S248)
7
rZ 4.1
33
GK
(S249)
Φ
kpGk I
GK-
GK -1 =
(S250)
7
OK-
4,3
6,3
K 111
(S251)
Gk
533
6,4
-1
v 2, 2,2
I
3.1
(S252)
I
GK-
= GK
2.1
(S253)
VP
7 G. GK-
GK-1
773
K-
8,6
(S254)
?Φ
G
Gg
-1
Gg.9 =
(S255)
44 GK
G6 6,6
K1
Io.
(S256)
which will be important intermediate results for the subsequent sections. Finally, we note that these results are sufficient to compute the training emoo. The expected training loss can be written as,
Euain
m -
((X))
(S257)
2 Etr(y TYK
(S258)
L - (X - /1/""/1)1'1//111/ + o0?lm)
1
(S259)
= (0,12+
(S260)
= +
(S261)
G.4.2 Ez1
The calculation of E,1 proceeds exactly as in (Tripuraneni et al. 202 b) with the simple modification of including an additional factor Σg inside the final trace term, yielding
Ex -2 Φ 2.1
(S262)
G.4.3 Eg1
The calculation of F31 proceeds exactly as in (Tripuraneni et al. 2021a by with no modifications since there is no dependence on Σg The result is,
vb dr 0o (w (2((w>> Ex pp 0.
(w In,1) of $2h122))
(S263)
24

---

Published as a conference paper at ICLR 2022
G.4.4 Es2
Define the block matrix Q
522
202 by,
In
Va=ge
T
Vn-ce
Ty
TV"0
V
0
Ing
2//2
0
0
Oy
Ing
0
0
Fwo
x2//2
0
Ino
V/10
0,
0
0
0
Ing
0
0
0
0
0
0
0
0
0
0
0
0
0
W
0
0
(S264)
and,
VIT
0
Q2
(5265)
TV"0
I
1///
0
Ing
100
Ing
1/2
0
0
0
Ino
0
Ing
1//2
Ing
Then block matrix inversion (i.e. repeated applications of the Schur complement formula) shows that,
G =
G
G11,14
G
G = 1
(S266)
G = G
(S267)
2 = F2g
GK-
(S268)
Gla = G
(S269)
G
Fxz
G
Gf2,1
G
G
Ea
=
G
3,3
(S270)
G
Exp
G
G
G3.4
(S271)
G
Esg
GEn
GK
(S272)
Bap
Esp
G3
-1
(S273)
Eaa
G
Eap
Er2
GK"
(S274)
Faz
G13,10
GK
(S275)
G
G
G
G
G
5
(S276)
GB
G
10,13
G 1
(S277)
G
GEs2
G6,3
-1
(S278)
GL4
G
G7,3
Kー
(S279)
25

---

Published as a conference paper at ICLR 2022
G
G7,4
(S280)
G
G -
(S281)
115,12
G
(S282)
G16,10
GK
(S283)
115,14
G8.7
GK
(S284)
G
G9,1
GK-
(S285)
GK
14,11
G
9,1
(S286)
Φ
G
Es2
(S287)
where G denotes the normalized trace the (i, bllock of the inverse of (Q T For brevity, have suppressed the expressions for the other non-zero blocks.
To compute the limiting values of these traces, we require the asymptotic block-wise traces of Q Faz, which may be determined from the valuud Stieltjes transform. To proceed, we first augment E to form the the self-adjoint matrix Q Baa
[Qusa]
Eaz
(S288)
Q Baa
0
and observe that can write D as,
Quin Z
Bsa
W.x.e
(
0
I16
)
1Q
Eag W,xee 0
T
0
[Q T
)
(S289)
/16
0
Que W.X,
Q
Eaa
0
where Q
[1Q
Eag
IQ
Esg
2222 and,
W.X.0
=
W.X.0
VEX
Va=ze (c-m)
JoW 0
W
[Q =
0
WT
(S290)
Vn T/TT
0
0
W
0
Val VTTT
1QFxx.ol =-
-
VaXT
(S291)
D
0000000000000000
26

---

Published as a conference paper at ICLR 2022
0
0
321/22
1/1/
0
0
E1/2
Ep
0
0 0 U
0
1//2
0
U
-/1/2
0
00000
00000
00000
0
O
0
0
VP
00 000
E1/2
DU
(S292)
The operator-valued Stieltjes transforms satisfy,
Faz G (% ( (GRoz)
(S293)
= id 6 ir 7 R W. (G
where R e (G the operator-valued R-transform of @W,x, As discussed above, since QRe w. is block matrix whose blocks are iid Gaussian matrices (and their transposes), explicit expression for B can be obtained from the covariance map which can be read off from eqn. (2288). As above, we utilize the specific sparsity pattern for G that induced by Eq. S293 to obtain,
RE R... (
B W. (Griaa)
(S294)
(
0
where,
(1Es G5 (S- -1)
vpG63
Esg
G (C 11) (S -n)
(GBa2)]
1,1
(S295)
?
G7,2 (S -11) 11)
VpGfL3
C - 11) (C - n
[n
1 (G
11
(S296)
VpG15,3
[R
W (G
Faz
(S297)
1,16
Fag
(5 - 11)
(G
+
V
(S298)
7Φ
VG (S 1)
G (S - n) (C - 7))
(GEs2)) [
11
VpDC + VppGBa
7Φ
7Φ
(S299)
G F52y)
11.5
VpG22
Eyg
(S300)
VPG
(S301)
4,10
[R
x
(G
10.
(S302)
7Φ
VpGg.r
(G W.x.0
(GEs2
(S303)
6.12
7Φ
GG (S - 11)
+ G
(S304)
7Φ
VG (S 1)
GG Esz (5
- 1)) (C - 17)
[R
(GBs)))
8. + Pa
7Φ
7Φ
(S305)
27

---

Published as a conference paper at ICLR 2022
[ 0
(G
1855
2
(S306)
W. (G
11
(S307)
8,10
222 (S -n) n1)
V
[R
[BW.x,o (GEx2)),
M1.1
(S308)
7
G G7,7(5 (-1))
(5-) 11)
W. (G
M9
(S309)
7
vpGf3.1
[R 0 (G
(S310)
9,16
vDG1
[ ,0 (G
11
(S311)
11,3
70
W,
(G
B12))
11.12
(S312)
7Φ
W (G
F22)
Fa2
(S313)
13,5
(G
Fa2))
vpC
(S314)
13,10
vp0f.10
Feg
(GEs2))
115.3
(S315)
VDGg.16
[ o (F22))
(S316)
15,12
7Φ
and the remaining entries of R o (G are zero As above, plugging these expressions into eqn. (S293) and explicitly performing the block-matrix inverse yields the following set of coupled equations,
V 1) +
7 n) (C 17)
G.,3- 22 VPPpVEE +22 VPPVPf +
Φ
(S317)
YTI I.P
Ge3 = I 15 - I 1117
(S318)
5 = IT, (pT1 (5 - 11) + op)
(S319)
IT,1 (pT 1/ (5 nnn) + ap)
G
(S320)
Vpúó
VpT (1 (1II,,15 - I 11 17 - IT.
Ghn
(S321)
4/26
G
yr G Fag (S - 17) - 7 / Fag + + - 1) (5 (5)
(S322)
! (-viI + + + + ITI
G = VoOG 222
2,2 - 12 G I
1/
(S323)
22 V (pT (5- 17 + op)
G = Vp Eas To. - 7
I,2
(S324)
9.1
I2 ( dop xnds 2247))
GBg
G E
pn
7,2 1,2
pp. GBa Es2 II
(S325)
e
p2 20
G = -P I1 1.2
P I 2 +
r. 4.2 (1 ()
(S326)
+b
28

---

Published as a conference paper at ICLR 2022
-- + 1II.27 + (F:1222))
Gh13 = vpO0 BogGLIII 7p 3/2 9 G I2.2
(S327)
7² PPPTfz L (pT) (5- 11) xp)
G - Vpb07, 2.2 // G Ig.2
(S328)
I (TTp + xbC - -x/n)
G = 0 G
I2 2.2 - pī G I Ig
(S329)
v
PpmpfP + x² (5-
G
1.2 přz Gr Enp
[222 + Iz
(S330)
Pas Ig
Ig (7p² oी T7 (S -1) + xxp)
G
7.2
(S331)
Φ
Vpuios
S 0.2
G L
7p Ti 1 (5 -n)- - 122200
(S332)
7
Φ
VPb
P
G = prl
G
Ex
I
3.2 - G G.
x1 +IZz22 (1 - C)
(S333)
(8pM77P0 x² x2(5 (5-1)) 1)
Fag
G G. 1,2
pǏ: G Bss I, + 12
(S334)
VpGg.
1
112 G 12
122 1 (5 - -n) + xpp))
133,5
(S335)
7
Vpla
VpG Egg I
p
//
E 7.2
I
7p Ig. 2 (5 - 11)
Faa
9,1
(S336)
vpb
xI1,1
Fag
(S337)
I
3.2 (S (5-11 11) - 7² prz 1p.0 0.20 9.26
G
V Is
G
Egg
+
Ppr
Ih
+
(S338)
2.2
4.2
VPv
2,2 (72 pm गी pp + vbo? - x/x211)
V G14,4
G72
Fsz
V
Fr
Egg
(S339)
VPV0
2
Exa
Iz
22
G
+
(S340)
Φ
P
2 2
I Gap
p 2.2 G7.
?p²
(1
()
2.200. ?
2.2
G
(S341)
pQ
G
(S342)
Vpø
4.1
G
(S343)
Φ
0.1
Giti
(S344)
Vp
I2 (S - 11 - -m2pm 7 22
G = Vpr I Emp
I +
(S345)
Vpp
I (22 7f + w/ - v/x2n)
G = V
G + I
(S346)
3.2
29

---

Published as a conference paper at ICLR 2022
I
p Baa
3.2 (T0² (S - 11) xbb))
3.2
3.2
1555
(S347)
7
puj
yp r 51 (m - () + x 2
1.2 G
pri p 77
G
(S348)
Φ
pp
1
115,8
(S349)
Vpb
7
115,10
E
1
(S350)
15,12
R52
(S351)
I
G15,11
(S352)
G = +f I G (C 1))
v + t 11) (5 -6n) G
(S353)
G16 I
(S354)
G = Egg =
(S355)
G G
77
(S356)
G
(S357)
1pTII1
G
13,10
Egg
(S358)
G
11,11
I1
(S359)
- PF + p T2
G
Fag
- G
+ xI1, (1 C)
(S360)
12,3
G
G
(S361)
Φ
7
G14,12
Es2
15,13
7.1
(S362)
vp
G = 10,8
Enp
= G
Io.
(S363)
I
G
G
Ega
Eng
G
(S364)
G
G
G
G In
(S365)
Gg
G1i,1
Fag
G15,15
GEgg
16,16
Egg
1
(S366)
IT 7.1
3,4 = Egg
= G
G1,88
Eg2
12,13
(S367)
G Exg
5.3 6,4
Exa
= G
12,12
Egp
G
T
1
(S368)
G
Ega =
Exp
G = G = G G
=G = In,1
(S369)
Here we have used the relations in eqns. S266 S287 the definition of I as well as the results in Sec. G.4. to simplify the expressions. It is straughtlorward algebra to solve these equations for the undetermined entries of E and thereby obtain the following expression for Ez2.
(1
A) + pB32
Exg
(S370)
D
30

---

Published as a conference paper at ICLR 2022
where,
A32 hw
2I 1I,,III1222i " ()
+
rD(s - n))
+ + 1, + nyls - -1))
11))
- + 2 11) B2 = p'vx -
(S371)
201r 2I,,225,,21 - 5)
22p 2 I + p² Vo oIg II,
+ 2I 1
+
+ 1
11)
piit b 1 (6-1))
px (po an 11) puba 11 p 2,2 + x155 -1))
- -² I I
13 1( - -n)² -p-2))
(S372)
2p² D32 - p'v +
+ + $ I1, pI Φ) p (z -
(S373)
Further simplifications are possible using the raising and lowering identities in eqn. S9 as well as the results in Sec. G to obtain,
E32 = I
x² 3
② 3.2
p 0y
1b dx
[T (w (w + II.1)
Ø² I2, + mn + 2I12)
T
(S374)
where
dr
(S375)
0y 7 1 7w +I1,2)
G.4.5 E1
The calculation of E, proceeds exactly as in Tripuraneni et al. 202 la b) with the simple modification of including an additional factor Eg inside the final trace term, yielding
2 = 3,2
E =
(S376)
G.5 FINAL RESULT FOR BLAS, VARIANCE, AND TEST BRROR
Putting the above pieces together, we have,
B, ΦI 0x
(S377)
I 2II (w +I11) +ww 6² = FTZZIIIa0 + yT I2 + 2I1,2)
V/ p x On
+ 0² ( 2I + Ir,1+ 2
(S378)
(S379)
Some algebra shows that
Fpp BB Vp
(S380)
31

---

Published as a conference paper at ICLR 2022
(T + I2,1)
0
(S381)
7i
Euain 7
(S382)
Corollary G.1. In the setting of Theorem
3.1
the ridge regularization constant 7 + 0, En
Bp + Vi with B,, - = and Vn given by
2 min Φ. 2b) 2 O + +1+ +
if <
(S383)
(o
+1,2)
otherwise
where I is the unique positive real root of x
m/v(
32


Reviews:
[{"review_id": "xgl6_EBxRHi", "reviewer": "Reviewer_6qzE", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In general, the paper is written clearly with enough technical details to understand the arguments. The motivation to study data with anisotropic covariances is good. The findings on the error curve structures and the correspondence between phase transition and induced kernel matrix spectrum are interesting. In all, I think the significance and contribution of this paper meet the bar of ICLR.\n\nHowever, one thing that may weaken the significance of this work is that, as a theoretical paper, the proof techniques of the main results is almost the same as previous works studying the case of identity covariance. The only difference is the changing in the covariance, which only changes some calculations. Thus, from the technical perspective, the paper does not provide much new insight.\n\nQuestions and detailed comments:\n\n1. What is the motivation to consider random model weights and what is a good practical implication of this setting and related results (e.g., the covariance alignment)? I notice that the analysis in Liao et. al NeurIPS 2020 also does not require that the data has identity covariance matrix, and do not assume random weights either. I think that setting could be more practical. How does the results in this paper compare with theirs?\n\n2. The analytical figures are plotted using the data model described in Section 2.3. Does the observations hold for more general data distributions?\n\n3. What is s in equation (12)? In Figure 3 c), what is the optimal regularization parameter lambda? Seems that it is not described.\n\n4. In Figure 2 a), the multiple descent is more obvious for small \\omega, which is the linear model. Is that correct? Then why is it stated as an observation for random feature regression?\n\nSome plots in Figure 2 and 3 needs to be better clarified. I'm a little bit confused about some plots and find it hard to get what the curves represent. There is a typo in the caption of Figure 2, 3rd line. ", "summary_of_the_paper": "The paper studies random feature regression in high dimensional setting, when the data and model weights are assumed to be normal with anisotropic covariances. By an error decomposition argument, the exact formulas for the bias, variance and total error are provided. The results motivates the discussion on the multiple descent effect of the sample-wise test error curve, and the authors also prove that the error against overparametirazation only exhibits double descent. The phase transition is associated with the spectral structure of the approximated kernel matrix. Also, the error is improved when the data covariance aligns more with the model weight covariance.", "summary_of_the_review": "In the sub-field of high-dimensional random feature regression, the paper present good contribution and results to consider the anisotropic data distribution, though the proof techniques mostly follow from previous works. Therefore, I think the paper has its pros and cons, depending on the \"weight\" of technical novelty. In all, I feel the paper is above the borderline of acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "rdnsDZ3G_qR", "reviewer": "Reviewer_3RfG", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "My main concern with this work is the total disconnection with the relevant literature in the topic. Different flavours of anisotropic random features have been previously studied in the literature: on the first layer weights [1], on the input features $x_{i}$ [2, 3], on both the target function weights $\\beta$ and on the input features $x_{i}$ [4, 5], with **NONE** of these works cited in this manuscript. \n\nMoreover, in the isotropic case it has been proven that the asymptotic generalisation and training errors of RF in the proportional regime studied in this manuscript are equivalent to the error of an equivalent Gaussian model with correlated inputs [3, 6, 7, 8, 9]. This Gaussian equivalence was conjectured to hold also in the the anisotropic case of correlated inputs and target function weights, with extensive numerical evidence supporting it [3, 5]. Under this conjecture, the asymptotic formulas in this manuscript follow from previous works studying anisotropic ridge regression [10], and were generalised to generic convex losses and penalties in [5]. Therefore, it is no surprise that the effects of anisotropy in this work are similar to the ones reported in [11]. \n\nI don't think this completely voids the interest of the discussion in this manuscript: even though the formulas might not be new, it unveils some interesting phenomenology. However, I do believe it would be much more interesting if it was put in perspective with the aforementioned related literature. For instance, how does the phenomenology induced by anisotropy compare with the results reported in [1,2,4]? What insights the RMT proof provide on the extent the Gaussian equivalence holds? etc. \n\n[1] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, Andrea Montanari, *Limitations of Lazy Training of Two-layers Neural Networks*, arXiv: arXiv:1906.08899 [stat.ML].\n\n[2] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, Andrea Montanari, *When do neural networks outperform kernel methods?*, arXiv:2006.13409 [stat.ML].\n\n[3] Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Marc Mézard, Lenka Zdeborová, *The Gaussian equivalence of generative models for learning with shallow neural networks*, arXiv:2006.14709 [stat.ML].\n\n[4] Stéphane d'Ascoli, Marylou Gabrié, Levent Sagun, Giulio Biroli, *On the interplay between data structure and loss function in classification problems*, arXiv:2103.05524 [cs.LG]\n\n[5] Bruno Loureiro, Cédric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mézard, Lenka Zdeborová, *Learning curves of generic features maps for realistic datasets with a teacher-student model*, arXiv:2102.08127 [stat.ML]\n\n[6] Song Mei, Andrea Montanari, *The generalization error of random features regression: Precise asymptotics and double descent curve*, arXiv:1908.05355 [math.ST]\n\n[7] Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mézard, Lenka Zdeborová, *Generalisation error in learning with random features and the hidden manifold model*, arXiv:2002.09339 [math.ST].\n\n[8] Hong Hu, Yue M. Lu, *Universality Laws for High-Dimensional Learning with Random Features*, arXiv:2009.07669 [cs.IT].\n\n[9] Pennington and P. Worah, *Nonlinear random matrix theory for deep learning*, in Advances in Neural Information Processing Systems, 2017, pp. 2637-2646.\n\n[10] Denny Wu and Ji Xu. *On the optimal weighted $\\ell_2$ regularization in overparameterized linear regression*. arXiv:2006.05800 [stat.ML]\n\n[11] Gabriel Mel, Surya Ganguli, *A theory of high dimensional regression with arbitrary correlations between input features and target functions: sample complexity, multiple descent curves and a hierarchy of phase transitions*, Proceedings of the 38th International Conference on Machine Learning, PMLR 139:7578-7587, 2021. ", "summary_of_the_paper": "This work studies random features regression on a setting where data $(x_{i}, y_{i})\\in\\mathbb{R}^{n_{0}+1}$, $i=1, \\cdots,n$ is generated from a noisy linear model $y_{i}=\\beta^{\\top}x_{i}+\\epsilon_{i}$ with correlated covariates $x_{i}\\sim\\mathcal{N}(0, \\Sigma)$, planted weights $\\beta\\sim\\mathcal{N}(0,\\Sigma_{\\beta})$ and independent Gaussian noise $\\epsilon_{i}\\sim\\mathcal{N}(0,\\sigma_{\\epsilon}^2)$. Estimation is given by $\\hat{y}(x) = \\hat{\\beta}^{\\top}\\sigma\\left(Wx\\right)$ with $\\sigma$ a real-valued activation function and $W\\in\\mathbb{R}^{n_{1}\\times n_{0}}$ a Gaussian matrix with iid $\\mathcal{N}(0, 1/n_{0})$ entries, and $\\hat{\\beta}\\in\\mathbb{R}^{n_{1}}$ minimising the ridge regression risk on the features $f = \\sigma\\left(Wx\\right)\\in\\mathbb{R}^{n_{1}}$.\n\nIts main theoretical contribution is to provide an asymptotic characterisation of the test MSE, the bias and the variance on the proportional regime $m,n_{0}, n_{1}\\to\\infty$ with fixed ratios $\\phi=n_{1}/m, \\psi=n_{0}/n_{1}$, as a function of the asymptotic spectral statistics of $(\\Sigma, \\Sigma_{\\beta})$, the ratios $(\\phi,\\psi)$, the $\\ell_2$ penalty strength $\\gamma>0$, the noise variance $\\sigma_{\\epsilon}^2$ and the constants $\\rho = \\mathbb{E}\\left[z\\sigma(z)\\right]$, $\\eta = \\rm{Var}\\left[\\sigma(z)\\right]$, $z\\sim\\mathcal{N}(0,1)$, characterising the activation $\\sigma$. \n\nIt provides numerical experiments confirming the validity of their formulas for finite but large dimension, and discusses the implications of the anisotropies $(\\Sigma, \\Sigma_{\\beta})$  on the bias, variance and test error in different regimes. In particular, it shows that alignment between $\\beta$ and the leading eigenvectors of $\\Sigma$ reduces the test MSE, and that anisotropy can induce double-descent like behaviour in the learning curves. \n ", "summary_of_the_review": "This work provides some interesting insights on the effects of anisotropy in the RF ridge regression setting, but would strongly benefit from a major rewriting to account for a discussion of the relevant literature in this topic.\n\n---------------------------------------------\n**Update after the discussion period**\n\nMy main concern with this work was the disconnection with the existing literature dealing with anisotropic features on the asymptotic proportional regime. At first, I was surprised the authors had missed a long line of works based on a different approach than RMT to treat the same regime (Gordon inequalities), and the corresponding Gaussian equivalence discussion in a subset of these works. However, given their engament during the discussion period and their willingness to acknowledge this gap, I believe they have acted in good faith.\n\nThe revised manuscript from 23.11.2021 (including the revised appendix A) goes in the right direction. However, I join reviewer *ot31* in the opinion that it could be further improved by:\n\n- Including the explicit connection with [5] in the case of the square loss with $\\ell_2$ penalty (which the authors said they are already working on). This would be an interesting result in itself, bridging a gap between the two approaches in the existing literature and opening a possible direction of future research consisting of exploring whether the alignment discussion in this work hold for other losses. \n- Being more explicit about the linearisation assumption (c.f. *ot31* updated review). \n\nAssuming these suggestions will be incorporated in the final manuscript, I am changing my recommendation to an accept.\n\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "aubg5-FSvw", "reviewer": "Reviewer_bozT", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The major contribution of this work is to extend the high-dimensional characterization of random feature (kernel) regression model to the case of anisotropic data. This improves previous efforts of [Mel & Ganguli, 2021] by considering nonlinear random features models, and of [Mei & Montanari, 2021] by considering anisotropic data.\n\nI think this paper makes a solid contribution to the understanding of high-dimensional random feature models.  Many insights (multiple descents due to data and model structure, steep cliffs, etc.) offered by the proposed analysis are valuable in the future (and improved) design of large-scale machine learning models more generally.\n\n", "summary_of_the_paper": "This paper evaluates the training and generalization errors of the random feature (ridge) regression model, in the regime where the number of samples $m$, the input feature dimension $n_0$, and the hidden layer size $n_1$ tend to infinity at the same rate. More precisely, the authors consider\n* Gaussian data with zero mean and general covariance $x_i \\sim \\mathcal{N}(0, \\Sigma)$;\n* label generated by $y(x_i) = \\beta^\\top x_i/\\sqrt{n_0} + \\epsilon_i$, for some additive noise $\\epsilon_i \\sim \\mathcal{N}(0, \\sigma_\\epsilon^2 ) $ and coefficient vector $\\beta \\sim \\mathcal{N} (0, \\Sigma_\\beta)$;\n* (random feature) kernel regression on $K(x_i, x_j) = \\frac1{n_1} \\sigma(W x_i/\\sqrt{n_0})^\\top \\sigma(W x_j/\\sqrt{n_0})$;\n\nand evaluate the training and test performance as a function of the dimensionality, the nonlinear function (via a few scalar parameters), as well as the spectral behavior of $\\Sigma$ and $\\Sigma_\\beta$.\n\nAs a consequence of this theoretical evaluation, the authors characterize sample-wise multiple descents, steep cliffs, and how they relate to, e.g., the spectrum of the (random feature) kernel matrices and the structure of coefficient vector $\\beta$. ", "summary_of_the_review": "Some detailed typos and remarks:\n* page 3 on the model: I do not understand why one needs to consider the setting of random coefficient vector $\\beta \\sim \\mathcal{N}(0, \\Sigma_\\beta)$ instead of, e.g., considering deterministic $\\beta$, as in previous efforts. I find it somewhat confusing since the authors say after Equation (6) that \"the outer expectation over $\\beta$ has been suppressed since ...\" Could the authors comment on this?\n* page 3 \"namely $\\beta \\sim \\mathcal{N} (0, \\Sigma_\\beta)$..\" \n* page 5: after (11) there should be more discussions and intuitions to help the readers understand the definition of $d$-scale LJSDs introduced here, which turns out to be of crucial significance in this paper.\n* page 5 Equation (14): perhaps add a few words to define the (partial) derivative.\n* page 7 Figure 2 covariance model with $\\alpha = 10^3$: a typo here? Also, we see the sample-wise multiple descents appear for relatively small values of $\\omega$, which, I imagine, implies a close-to-linear regime, could the authors comment on this?\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "akhphkIiH6y", "reviewer": "Reviewer_ot31", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**:\n\t\n- To my knowledge this is a novel contribution that broadens the understanding of overparameterization, a topic of interest to the ICLR readership\n\t\n- The asymptotic formulas are exact and relatively simple.\n\t\n- This paper introduces an interesting notion of alignment between the covariance matrix of the covariates and that of the parameter, and it is shown how this alignment affects the test error\n\t\n- The main paper is well-organized, clear, and has interesting, illustrative figures.\n\t\n**Concerns**: \n\n- I am mainly concerned with the rigor and clarity of the derivation of the main theorem, Theorem 3.1. Please see the section \"Proof of Theorem 3.1\" below.\n\n- To my understanding, Figures 1--3 are generated by plotting the asymptotic formulae from Theorem 3.1. It would strengthen the paper to confirm these plots with simulations on synthetic data.\n\n\n**Proof of Theorem 3.1**\n\nMy points below mostly concern Section F to the end of Section F.4.1 in the Supplement. The proof happens in two steps: (i) linearization of random features and (ii) application of free-probability theory to compute the trace of some complicated matrices. \n\t\n(i) *Linearization*: This paper claims without proof that the test error is unchanged by an appropriate linearization of the non-linear random features. Of the given references on pg.13, I could only find a proof of the invariance of test error under linearization in Mei--Montanari '19, which only studies the case of random spherical (that is, isotropic) covariates. This requires justification in the anisotropic case.\n\t\nAlso a minor point: after linearization, the definition of $F$ changes I think. Please make this clear in the text \n\n(ii) *Free probability*:  Most of Section F relies on computations of various traces of matrix products involving covariance matrices and iid Gaussian matrices.\n\n*Major issues with (ii)*\n\n-  pg 13: There is no explanation of the construction of the $Q^{K^{-1}}$, which I believe is the *linear pencil*. A short, precise description of the linear pencil methodology would improve the paper since it is crucial to the proof.\n\n-  pg 17: \"We aim to compute the asymptotic values...\" I am concerned about the looseness in taking limits described here. How can the limit in $n_0, n_1, m$ be taken in two stages? Once these go to infinity, there should be no dependence of any expressions on $n_0, n_1, m$. It is also not clear at what point limits are taken in the computation in Section F.4.1. \n\n-  pg 18: Formula (S200) is crucial. Please give a reference to the precise section and theorem in Mingo--Speicher '17. \n\n-  pg 19: The R-transforms in (S202)--(S208) depend on indices of $G^{K^{-1}}$ that go out of range. For example there is a $(3, 15)$ entry in (S203).\n\n-  pg 19: The details of R-transform computations are omitted. I find this acceptable, but please cite the specific chapter in Mingo--Speicher that describes the technique for computing them\n\n-  pg 19: How is (S200) used to derive equations (S209)--(S228)? I would appreciate if in the discussion period the authors can explain how to derive (S209) from (S200) and the various R-transforms. In particular, I would like to understand the details of why the expectation over $\\mu$ shows up and what happened to all of the random matrices.\n\n-  pg 19: The appearance of $\\mu$ in (S209)--(S228) suggests that limits with respect to $n_0, n_1, m$ have been taken. So how is it that the terms $n_1, n_0, m$ still appear in these expressions?\n\n-  pg 22: The calculation in Section F.4.4 involves the system (S312)--(S364) consisting of ~50 equations that spans 3 pages. It is hard to verify the end result. Are all of these equations necessary for the derivation? If a simpler explanation isn't possible, I recommend giving a computer-assisted proof citing Mathematica or other algebra software. \n\n*Minor issues with (ii)*\n\n-  pg 13: $K$ appears to be regularized in (S137), but later $\\hat K$ is introduced that has the same formula. Should $K$ be non-regularized in Section F?\n\n-  pg 13: $\\theta$ is not defined and seems to sometimes be written as $\\Theta$ or $\\Theta_F$. \n\n-  pg 18: \"Here the normalized trace... acts on the space of 18x18 matrices.\" Should it be 9x9 matrices?\n\n-  For readability, I suggest re-organizing lists of equations with indices listed in lexicographic order ( for example in (S172)--(S194) )\n\n-  pg 19: The terms in (S209, S210) have no expectation over $\\mu$, but the remaining ones do. Is this a typo?\n\n**Minor issues/typos in the main text**\n\n- For consistency, use either \"total error\" throughout or \"test error\" throughout\n\n- pg 2: \"... in the relatively trivial case of isotropic covariates...\" Please replace this with \"... in the case of isotropic covariates...\" It is clear that isotropy is a simpler case, but I think it's good to avoid referring to prior works as relatively trivial. \n\n- pg 3, Eq (5, 6): The expectation over $\\beta$ appears and then disappears; for consistency please make a choice whether or not to include the expectation over $\\beta$ in the error metric.\n\n- pg 3: \"...the test error of linear regression depends on the geometry of $(\\Sigma, \\beta)$.\" This is confusing since $\\beta$ is random. Perhaps it should be the geometry of $(\\Sigma, \\Sigma_\\beta)$\n\n- pg 4, Eq (9): Usually the term \"empirical spectral distribution\" is reserved for the random measure given by the eigenvalues of a *random* matrix. Since $\\Sigma, \\Sigma_\\beta, \\mu_{n_0}$ are deterministic, perhaps just saying \"joint spectral distribution\" suffices?\n\n- pg 5, Definition 2.1: \"If the asymptotic coefficients are such that $\\mathbb{E}^{\\mu_1}[\\lambda q| \\lambda]/\\mathbb{E}^{\\mu_2}[\\lambda q| \\lambda]$...\" I think it should be $\\mathbb{E}^{\\mu_1}[ q| \\lambda]/\\mathbb{E}^{\\mu_2}[ q| \\lambda]$ instead (otherwise the value is independent of $\\lambda$)\n\n- pg 5, Theorem 3.1: The main result is hard to parse because the definitions of parameters are scattered throughout pgs 1--5. A short recap or pointer to prior definitions could help with this.\n\n- pg 5, Theorem 3.1: It took me a while to understand the meaning of  \"the training error $E_{train}^{\\Sigma} \\to E_{train}^{\\mu}$ where *insert Eq (14)*\".  A clearer rephrasing is \"the training error $E_{train}^{\\Sigma}$ tends to the value $E_{train}^{\\mu}$, where *insert Eq (14)*\".\n\n- pg 6, Figure 1: (f) is missing a legend\n\n- pg 6, Figure 1: In (d, e), it took me a while to understand what the black solid and dashed lines correspond to in the plots. I recommend just making a slightly bigger legend of the form \" Total error ($\\theta$ = 1), Bias ($\\theta$ = 1), Variance ($\\theta$ = 1), Total error ($\\theta$ = -1), Bias ($\\theta$ = -1), Variance ($\\theta$ = -1)\" \n\n- pg 6, Figure 1: What do the blue dashed/solid lines indicate in (a)? What do the gold dashed/solid lines indicate in (b, c)? Are these necessary?\n\n- pg 7, Figure 2: There is not much color variation in (b). Is this intentional?\n\n- pg 7, Figure 2: Please add to the caption that (b) plots the limiting spectral density of the kernel matrix\n\n- pg 8, Figure 3: The tick marks in (a) are very small and hard to read\n\n- pg 8, Figure 3: In (b, c), it is hard to see the color gradient. Different textures for each curve would improve this. \n\n", "summary_of_the_paper": "This paper studies nonlinear random feature regression of a linear response in the *anisotropic* setting where both the covariates and parameter have arbitrary covariance matrix. The training error and test error are computed explicitly as the dimension, sample size, and number of features jointly tend to infinity. The proof method relies on linearization and a technique from free probability involving the construction of linear pencils. The asymptotic formulas are used to theoretically describe (i) the beneficial effect of overparameterization on the bias and variance components of the test error and (ii) the number of critical points of the test error as a function of overparameterization. This paper graphs the asymptotic formulas for some specific models to demonstrate parameter-wise and sample-wise multiple descent phenomena. ", "summary_of_the_review": "The topic of this theoretical paper is of interest to the machine learning community, and the contributions given would extend understanding of the generalization behavior of high-dimensional, overparameterized models. My current recommendation to reject is because of the concerns mentioned above about the correctness, rigor, and clarity of the proof of the main theorem, Theorem 3.1. \n\n======================\n\nUpdate on review (11/29)\n\nFollowing the discussion and revision, my confidence has improved on the correctness of the results. Further the surrounding literature that was overlooked is now addressed, especially in Appendix A. \n\nThis work does have some lack of novelty since versions of Theorem 3.1 were known and multiple descent phenomena and some effects of alignment had been recognized in anisotropic random feature regression. Still the main contribution of this paper is the new phenomenology that it identifies, which to my knowledge include the behavior of the bias and variance under overparameterization and (mis)alignment, steep cliffs in the learning curves and their relation to spectral gaps in the covariance matrix, and that parameter-wise descent is limited to double descent. This in itself is a noteworthy contribution. \n\nThis paper would be further strengthened by establishing the equivalence of the formulas here with those of d'Ascoli et al '21 and Loureiro et al '21. This would help compensate for the loss in novelty. Also, while the relationship with d'Ascoli et al '21 seems well explained, not as many details are given about the connections with Loureiro et al '21. I also think that this paper needs to be careful regarding claims that it sets these prior works on rigorous footing because (i) the proof of the linearization invariance in Theorem 3.1 is not contained in this paper,  and (ii) to my understanding, the formulas of d'Ascoli et al '21 and Loureiro et al '21 are rigorous modulo linearization invariance. To summarize, the manuscript would benefit from further revision to clarify its contributions and their place in the literature.\n\nAll things considered, I am now slightly leaning toward acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper extends recent and very active literature on analyzing learning algorithms in the simplified setting of Gaussian data and model weights, with the main generalization being to allow for non-isotropic covariance matrices.  The main technical results seem to be correct and slightly novel, though reviewers feel they are not innovative or unexpected enough to stand on their own.  However, the main contributions of the paper are then to interpret these results to give phenomenological results (regarding double descent, etc.), and reviewers were unanimously happy with these. In the end, all reviewers were positive about the paper.

The largest reviewer criticisms of the paper were technical issues (ot31) and lack of context of recent literature (3RfG). Both of these concerns were mostly addressed by the revision/rebuttal. The reviewers still had specific comments on improvement, but found no major faults.
Decision: Accept (Poster)