Learning Curves for Deep Structured Gaussian Feature Models
Authors: Jacob A Zavatone-Veth
Cengiz Pehlevan
Venue: NeurIPS 2023 poster (2023)
Keywords: random feature models
generalization
deep networks
ridge regression

Abstract: In recent years, significant attention in deep learning theory has been devoted to analyzing when models that interpolate their training data can still generalize well to unseen examples. Many insights have been gained from studying models with multiple layers of Gaussian random features, for which one can compute precise generalization asymptotics. However, few works have considered the effect of weight anisotropy; most assume that the random features are generated using independent and identically distributed Gaussian weights, and allow only for structure in the input data. Here, we use the replica trick from statistical physics to derive learning curves for models with many layers of structured Gaussian features. We show that allowing correlations between the rows of the first layer of features can aid generalization, while structure in later layers is generally detrimental. Our results shed light on how weight structure affects generalization in a simple class of solvable models.

Learning Curves for Deep Structured Gaussian Feature Models
Jacob A. Zavatone-Vethh and Cengiz Pehlevan 3.2.4 DDpparmment of Physics, Center for Brain Science, 'John A. Paulson School of Engincering and Applied Sciences, *Kempner Institute for the Study of Natural and Artificial Intelligence,
Harvard University
Cambridge, MA 02138, USA
jaavatonevethhg harvard. edu, cpehl opehlevan@seas harvard. edu
Abstract
In recent years, significant attention in deep learning theory has been devoted to analyzing when models that interpolate their training data can still generalize well unseen examples. Many insights have been gained from studying models with multiple layers of Gaussian random features, for which one can compute precise generalization asymptotics. However, few works have considered the effect of weight anisotropy; most assume that the random features are generated using independent and identically distributed Gaussian weights, and allow only for structure in the input data. Here, we use the replica trick from statistical physics to derive learning curves for models with many layers of structured Gaussian features. We show that allowing correlations between the rows of the first layer of features can aid generalization, while structure in later layers is generally detrimental. Our results shed light on how weight structure affects generalization in simple class solvable models.
Introduction
Characterizing how data structure and model architecture affect generalization performance is among the foremost goals of deep learning theory [1, 2]. A fruitful line of inquiry has focused on the properties of a class of simplified models that asymptotically solvable: neural networks in which only the readout layer trained and other weights are random, which are known as random feature models (RFMs) [3-21]. Though RFMs cannot capture the effects of representation learning generalization in richly-trained neural networks [13, 22, 23], they have substantially advanced our understanding of how data structure and model architecture interact to give rise wide array of generalization phenomena observed in deep learning [1-5, 7-19, 24, 25].
Of particular interest is the question of when models overfit benignly, that is, when they generalize well despite having been trained to perfectly interpolate their training data. Here, much intuition has been gained by studying minimum-norm kernel interpolation-tthe that is, the ridgeless limit of kernel ridge regression-with RFM kernels, for which precise generalization asymptotics can be computed using tools from random matrix theory. These asymptotics lead to precise picture of how the spectrum of the random feature kernel and the structure of the task interact to determine generalization. These analyses are facilitated by universality results, often termed Gaussian equivalence theorems. that state that the generalization error of a nonlinear RFM is asymptotically equal to that of a linear Gaussian model with an effective noise term resulting from nonlinearity [3. 7, 10, 25, 26]. In the past few years, Gaussian equivalence theorems for ever more general classes of RFMs have been established: within this year Schröder et [20] and Bosch al. [21] have established Gaussian equivalence theorems
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

for deep nonlinear RFMs with unstructured feature weights, while Cui et al. [27] have extended some of these results the setting of deep Bayesian neural networks when the target of the same architecture.
However, these analyses consider the effect only of correlations in the data, and do not address the possibility of correlations between the random weights. It is standard to assume that the elements of the weight matrices at each layer are independent and identically distributed Gaussian random variables, and to our knowledge all existing Gaussian equivalence theorems make use of this assump- tion [3-15, 19-21]. As result, how weight anisotropy affects generalization in deep RFMs in particular, if it can affect the asymptotic scaling of generalization error with dataset size and network width [16, 19, remains unclear.
In this note, we take the first step towards filling that gap in our theoretical understanding of RFMs by computing the asymptotic generalization error of the simplest class of deep RFMs with anisotropic weight correlations: models with linear activations. Our primary contributions are as follows:
Using the replica method from statistical mechanics [29], we compute the asymptotic generalization error of deep linear random feature models with weights drawn from general matrix Gaussian distributions. This computation is closely related to prior replica approches to product random matrix problems [13,3]]. 30].
We show that, in the ridgeless limit, structure in the weights beyond the first layer is detrimental for generalization.
We next consider the special case of power-law spectra in the weights and in the data, which was classically studied in kernel interpolation the form of source-capacits conditions [3 11], and has recently attracted substantial interest in deep learning due to approximate power-law spectra present in real data [16, 19, 28, 32]. Using approximations for required spectral statisties derived in past works [19], we show that altering the power laws of the weight covariance spectra do not affect the scaling laws of generalization.
We finally show how our results can be extended from the ridge regression estimator to the Bayesian Gibbs estimator, object of classic study in the statistical physics of learning [13, 33, 34]. For sufficiently large prior variance, structure can be beneficial for generalization with this estimator.
Taken together, these results are consistent with the intuition that representation learning at only the first layer of deep linear model is sufficient to recover a single teacher weight vector [13, 35-37J.
2 Preliminaries
We consider depth-T. linear RFMs with input E To and scalar output given by
1
fxx:v,F)
/no (Fv) x,
(1)
where the feature matrix E R is fixed and the vector V E Th is trainable. If J. = 0. corresponding standard linear regression, the feature matrix is simply the identity: F F-Inng If L >> 0, we take the feature matrix to be defined by product of L factors U, E R=c-1xm;;
F
U -U..
(2)
TT
We draw the random feature matrices independently from matrix Gaussian distributions
U. MN n.-1 MN
Xx, xn, Iz, Eg)
(3)
for input covariance matrices Рe E 1.=e-1xmm and output covariance matrices Σ, E R such that ([(U2), (Ue) dee (E)) Subject to the constraints of layer-wise independence and separability-wii which are required for the factors to be matrix-Gauseee most general covariance structure one could consider. One might wish to relax this to include non-separable covariance tensors (Ue))) y = dge (x but this would spoil the matrix- Gaussianity of the factors, and to knowledge does not appear to be addressable using standard
distributed -ths the

---

methods [30, 38]. We generate training datasets according to a structured Gaussian covariate model, with p i.i.d training examples (x,s 8n)) generated as
X Mid. (00 Eo),
w. X + Eus
(4)
V
where the teacher weight vector w. is fixed and the label noise follows
Eμ Mi.d N0,,, 17²).
(5)
We collect the covariates into a matrix X E RRxxo, and the targets into vector E TRP.
As in most works on RFMs [3-5, 8-21, 25], our focus is on the ridge regression estimator
>I| + II vIl.
arg min L for I. T0
XFV
M
(6)
v
where the positive-definite matrix TL+1 E R x controls the anisotropy of the norm and the ridge parameter sets the regularization strength. This minimization problem has the well-known closed form solution
1 -
F - XF
F F
Vno
73g
As motivated the Introduction, we are chiefly interested in the ridgeless limit À 0, which ridge regression solution gives the minimum & norm interpolant of the training data. We measure performance of this estimator by the generalization error
Ex (g(x; v, F) E&g (xx))(x)))*
/ (FV 113
fp. dg
70g
which is random variable with distribution induced by the training data and feature weights.
This leads us to a simple, but important observation: including structured input-input covariances is equivalent to transforming the fature--eatture covariances. We state this formally as:
Lemma 2.1. Fix sets of matrices (Te / and { [E and target vector Let Ep.na.....ng mg be the resulting generalization error as defined in (8), Let
r I
for i ,,...,, L+
L
(9)
Σ. T 1/2 1/2 E.RETI
for l = O...., L,, and
(10)
E41 E+1
W, 1 1/2
(11)
Lel fp.ng.....n be the generalization error for these transformed covariance matrices and larget. Then, for any À > O, we have the equality in distribution Ep. Ep.o.....n..
Proof of Lemma 2.1. As the features and data are Gaussian, we can write X d 1 and
U. A // "/ for unstructured Gaussian matrices (Ze)ss Widd. NO 1). Substituting these representations into the ridge regression solution (7) and the generalization error (8), the claim follows.
Therefore, we may take D, = In-- without loss of generality. Moreover, thanks the rotation- invariance of the isotropic Gaussian factors Ze, we may in fact take the remaining covariance matrices Eg to diagonal without loss generality, so long as we then express w. in the basis of eigenvectors of Eg. An important qualitative takeaway of this result is that changing the covariance matrix of the inputs of the first layer Ij equivalent to modifying the data covariance matrix, which was in simpler form observed in the shallow setting (I = 1) by Pandey et al. [39].
3 Asymptotic learning curves
Having defined the setting of our problem, we can define our concrete objective and state our main results, deferring their interpretation to the following section. We consider the standard proportional asymptotic limit
p, 140 ... AL 0o, with napp az $0,0000 oo),
(12)
3

---

which we will refer to as the thermodynamic limit. Our goal is to compute the limiting generalization error:
1 1 /2 (Fv -w.)l.
lim
Ep
(13)
P.N0
n0
where Ep denotes expectation over all sources of quenched disorder in the problem, i.c., the training data and the random feature weights. In the thermodynamic limit, we expect the generalization error to concentrate, which is why we compute its average in (13) [3-5, 8-21].
To have well-defined thermodynamic limit, the covariances Eg and the teacher we must be in some sense sufficiently well-behaved. We consider the following conditions, which are the generalization to our setting of those assumed in previous work [4-7, 16-18, 40]:
Assumption& 3.1. We assume that we are given deterministic sequences of pesittive-effitie matrices (ne) and vectors w. (no) indexed by the system size, such that the limiting (weighted) spectral moment generating functions
M (2) lim 1 71-+00 ThE
tr(Ee(=In, E1 and xb(2=
lim n0-000 110
W. Eo(zIng En)
lw.
(14)
are well-defined for all é = O....,L L.
We can now state our results. As a preliminary step, we first give an expression for the generalization error for a fixed teacher w, at finite ridge A. Then, we pass to the ridgeless limit, on which we focus for the remainder of the paper. At finite ridge, we have the following:
Proposition 3.1. Assume Assumption 3.1 holds, For À > 0, let ( solve the self-consistent equation
1- L A =
5 M (-5)
(15)
C 8=
at
at
In terms of G, let Re(S) solve
1 (~ne(() 5
Ea,
(16)
KE(() + σe
ag
for O,..., L, where Es, [h(r))] nim ni Eie h(ōr,)) denotes expectation of a function h with respect the limiting spectral distribution of Et, for ōe. its eigenvalues at finite size, and let
27
01 Me(C) 5 Re(s)M (-Re(S)) = - a1 Eai
(Me(() + oz
(17)
S
Then, the learning curve (13) at finite ridge for a fixed target is given by
[1 + (Eto me ) 5) c= c- 1 )
Nā (1B) + EE
1-#1 )n?
(18)
po
Me
Proof of Proposition 3.1. We defer the derivation of (18) to Appendix A. To compute the disorder average in (13), we express the minimization problem in (6) as the zero-temperature limit 8 oo of an auxiliary Gibbs distribution p(v) e 9L and evaluate the average over the random data random feature weights using the non-rigorous replica method from the statistical mechanics of disordered systems [29, 33]. This computation is lengthy but standard, and is closely related to the approach used in our previous works on deep linear models [13, 30]. All of our results are obtained under replica-symmetre Ansalz; as the ridge regression problem (6) is convex, we expect replica symmetry to be unbroken [29, 41, 42].
From the self-consistent equation (15), recognize that is is up to sign the spectral moment generating function of the feature Gram matrix K = XFF X /no,. which a Wishurt random matrix [30]:
((A) Mk((-).
(19)
This dependence falls out of the replica computation of the generalization error using auxiliary Gibbs distribution; we emphasize that one could take an alternative approach in which the general- ization error is first expressed in terms of MK- for instance, in Gerace et al. [25] Hastic et al.

---

[5] and then use results on the spectra of product- Wishart matrices to conclude the claimed result [30]. This approach would potentially have the advantage giving a fully rigorous proof, rather than one that depends on the replica trick. However, one would still then be faced with the task of solving the self-consistent equation for the spectral moment generating function, and therefore would end up in the same place insofar quantitative predictions are concerned.
In principle, could now directly proceed study how weight structure affects (18) for some fixed ridge A. However, as long as there is structure in the weights and/or the data, the self-consistent equation (15) must generally be solved numerically [14, 30]. To allow us make analytical progress, we therefore focus on the ridgeless limit À & 0 for the remainder of the present paper, and leave careful analysis of the À 0 case to future work. This follows the path of most recent studies of models with linear random features, and also the fundamental interest in interpolating models [3-17, 19-21]. We therefore emphasize that we state Proposition 3.1 merely as preliminary result.
Before giving our result for the generalization error in the ridgeless limit, we warn the reader of an impending, somewhat severe abuse of notation: in Proposition 3.2 and for the remainder of the paper, we will re-define Kę to be given by its value for the solution for Ç appropriate in the regime of interest. Moreover, will simply write for eimx
Proposition 3.2. Assume Assumption 3.1 holds, and let Omain min .LL). For = ....., L, in the regime 0₂ 1, let Kg be given by the unique non-negative solution to the implicit equation
1 - Ms (-Ke) = -Bae
(20)
Ofe
Kr + Ōz
In terms of Kg, les
(
(
27
He = 0r (-Ke) = arEas
(21)
Ri
In the regime amin < og. let Kmin be the unique non-negative solution to the implicit equation
Ommin - M
(-Kmin) =
Egg
(22)
Fimin + ōo
Then, the learning curve for a fixed target in the ridgeless limit À 4 O is given by
(Et-) 1- (oO)(Ko) ru v (Ko) + (Eto 1- )r?
Org Ommnn >
Kanin (D5min)
Omin I-aen
11²
Olmin < 1, Olmin < o0
(23)
-- --ggnn
Oo 17
ag < 1,00 amin
Proof of Proposition 3.2. We derive (23) the zero-ridge limit of Proposition 3.1 in Appendix A.
Before we analyze the effect of weight anisotropy in detail Section 4, we note several simplifying special cases of Proposition 3.2 which recover the results of prior works. To facilitate this comparison, we provide a notational dictionary Appendix D. The first important special case is
Corollary 3.1. If L we have
A e (Ko) nn
1-pa 172, No
ag
(24)
1-00 n
on
< 1.
This recovers the known, rigorously proved result for linear ridgeless regression [4-7, 16-18]. For larger depths, an important simplifying case of Proposition 3.2 that in which the data and features are unstructured, in which case the generalization emrrr is given by
Corollary 3.2. Σf In, for 0. ..... we have, for any target satisfying [..l| no.
Di=
) 1) + EE - ,
ag Ouain > 1
ag Ormin/ /on + Amiin 1/,
6
Qmin < 1, Qmin < 000
(25)
aaja
amio
Og < 0g < Omnnn
0g
5

---

(a)
(b)
n= 7=1/2
n=0 1-1/2
40
0
%
1/a
Figure 1: Phase diagram of generalization in deep linear RFMs. For simplicity, we consider a model with a single hidden layer (L- = 1): the picture for deeper models is identical if one considers the narrowest hidden layer [13]. (a). Generalization error for unstructured data and features from (25) as function of training data density 1/00 and hidden layer width 0n /oo in the absence of label noise (1) 0: left) and the presence of label noise (1) 0.5; right). (b). As in (a), but for power law structured data and weights, with wo wi 1, and given by (31). See Appendix F for numerical methods.
Proof of Corollary 3.2. We have Mr,, (2) = 1/(z - 1), hence Kg = ag 1, Me = 1/ag, and Einin 01// no/amin 1. Finally, for any fixed teacher vector satisfying l/w.112 112 = no, we have (2) = 1/(2 + 1) if Eg Ino- Substituting these results into (23), obtain (25).
This recovers the result obtained in our previous work [13], and in the single-layer case L = 1 recovers results obtained by Rocks and Mehta [14, 15], and by Hastie et [5] (see Appendix D). In the slightly more general case of unstructured weights but structured features, we have
Corollary 3.3. If Ee Ing for 1...., but Eg + Ing. we have, for any target satisfying |2 = noo
EE= or (No))
22 (K(o) Po
L1 140
+ Ei=1 - )
Cgs A'in
==
Nmin (HMmi))
Omin
1/?
Onuin 1, Omyin og
1-Qui 00
auin
11
ag < 1,00 < O'min-
1-cx
(26)
Proof of Corollary 3.3. (26) follows from substituting the results of Corollary 3.2 into (23).
In the special case L = 1, this recovers the result obtained using rigorous methods in contemporaneous work by Bach [40], posted the arXiv one day after the first version of work [43]. Here, the data spectrum and target vector enter the generalization eπror in nearly the same way as in the case of linear regression, all of the intuitions developed in that case can be carried over [4-7, 16-18].
Another useful simplification can be obtained by further averaging over isotropically-distibbueed teachers W. (O, Ing), which gives Corollary 3.4. Let Ew (..... Then, have
(1+
1 No +
1- ); On Omin >> de
E
Aminnfiminn /ag amin
Omin < 1, Orgin < Og
(27)
1 Oygi
< 1, O'min-
Proof of Corollary 3.4. Observing that Es, (6() -Ms (-2), the claim follows from (23).
In the special case of single layer of unstructured feature weights (L = 1, ΣS = I,,), ) this recovers the result of recent work by Maloney et al. [19], who used planar diagram method to the generalization error single-hidden-laye linear RFMs with unstructured weights (see Appendix D).
Another important simplifying case of Proposition 3.2 is the limit in which the hidden layer widths are large, which the generalization error of the deep RFM reduces that of shallow model, as given by Corollary 3.1. More precisely, we have a large-width width expansion given by:

---

Corollary 3.5. In the large-width regime a....., an > finite moments, the generalization error (23) expands as
1, assuming that the weight spectra have
Aa / (Ko)
1-10 12 (E
Es E
(HO))(RO) n²² O ..... a
(28)
in the regime Cu > 1; ag < 1 the generalization error does not depend on the hidden layer widths so long as they greater than 1.
Proof of Corollary 3.5. See Appendix E.
4 How does weight structure affect generalization?
The first salient feature of the learning curves given by Proposition 3.2 is that the addition of weight structure does not alter the phase diagram of generalization, which is illustrated in Figure 1. There are three qualitatively distinct phases present, depending on the data density and minimum layer width: the overparameterized regime cko, Omin > 1, the bottlenecked regime Omin < 1, Qmin < 0o, and the overdetermined regime op < Og < Ominn This dependence on the narrowest hidden layer matches our previous work on models with unstructured weights [13]', and can be observed in the solutions to the ridge regression problem for fixed data (Appendix C). As ag Ke 0 and μe 4 O. and the generalization eπror diverges. Similarly, the generalization error diverges as amin 1 1, og f 1 in the presence of label noise. However, there are not multiple descents in these deep linear models, consistent with the qualitative picture of the effect of nonlinearity given by previous works [9, 10].
The second salient feature of Proposition 3.2 is that the matrices Σ, enter the generalization error independently; there no 'interaction' terms involving products of the correlation matrices for different layers. This decoupling is expected given that the features are Gaussian and independent across layers [30]. Moreover, under the rescaling Σn Eg for Te > O, we have Ky = Tyte and 1 = jeg (we show this explicitly Appendix B). Therefore, (23) is sensitive only to the overall scale of E. not to the scales of Ei....; Σ,, This scale-invariance can be observed directly from the ridgeless limit of the ridge regression estimator (7).
We can gain intuition for the effect of having Ee * Ince for l 2 1 through the following argument: Lemma 4.1. Under the conditions of Proposition 3.2, the regime Olg, Ominn > 1, we have
1 2 (Et - - (o04((0)))))))
ná. (no) + (~- Et -
(29)
That is, the generalization error for given ET, Σg, is bounded from below by the generalization error for Σg = In, for E 1,..., L.
Proof of Lemma 4. 1.1. In Appendix B, we show that μ4 1/oor for any weight spectrum, which implies that (1 me)/ Ee 2 1/(ag - 1).. Substituting these bounds in to the general expression for the generalization error this regime from (23), the claim follows.
Therefore, having Σn * In, for = 1..... cannot improve generalization in the ag. Omin 1 regime. This is consistent with the large-width expansion in Corollary 3.5, where we can apply Jensen's inequality to bound the weight-dependence of the correction as 1R,,, equality only when the weights are unstructured. other regimes, Σ.. Σg do not affect the generalization error. contrast, a similar argument shows that anisotropy in Eg can be beneficial in the target-averaged case, at least in the absence of label noise. We formalize this
2 1, with
Lemma 4.2. Under the conditions of Corollary 3.4, in the absence of label noise (1) = 0), we have
11 Ele 1-Me (1 1)]]. Oi,, O'in >
Aeann/ Dol B(oo),
Omnn < 1, Omiin < Okg
(30)
0.
0g 1, Co ammin
That is, E for a given Eo is bounded from above by the generalization error for a flat spectrum
Σn = El
Prrevious works on deep RFMs have used several different parameterizations of the thermodynamic limit [3-17, 19-21]. We detail the conversion between these conventions in Appendix D.
7

---

Proof of Lemma 4.2. In Appendix B, we show that Ko S (ag- 1) As its defining equation (22) of the same form as (20), the corresponding bound for mimi follows immediately: Kmin S
(00/ [o] Substituting these bounds into (27) with 1j = 0, the claim follows.
If [l is not finite, then this bound is entirely vacuous: È S oo. we do not average over
crroopicall--ditribute targets, then the effect of anisotropy in Σg is harder to analyze. Previous works have, however, analyzed the interaction of data structure with fixed target in great detail for models with L 0 L 1, showing that targets that align with the top eigenvectors of Eg easier to learn [5. 16, 17, 42, 44].
5 Power law spectra
We can gain further intuition for the effect of weight structure by considering an approximately solvable model for anisotropic spectra: power laws [16, 19, 28]. Power law data spectra have recently attracted considerable attention
possible model for explaining the scaling laws of generalization observed in large language models [16, 19, 28, 32]. Maloney et al. [19] proposed a single-hidden- data and unstructured weights as a model for neural scaling laws. Does introducing power law structure into the weights affect the scaling laws predicted by deep linear RFMs? We have the following result:
layer (L 1) linear RFM with power-law-struetunn
Corollary 5.1. At finite size, define each covariance matrix Ee such that its j-th eigenvalue is ōt.j (m) +we for some fixed scale factor & 0 and exponent we O. Then, the limiting target-averaged generalization error is approximately
(1 + St. + Ei
x + (wo + Ut + Et= -/-)'²;
00, Ommin > 1
x/aa/ ((mmm)))))))
Crein 71
Omin < 1, Amin < 000
1-Oing -imin
-Ommn
1-00
00
17,
ag < 1,00 < Ouuin
(31)
where U2 = Eta and for z > we have X(2) ~ - (z)/ given by x(2) =
So [k(2"00 - + 12+ wo( k)] (1 - 1/2)] { for k = sinc|T + wo)l wo)] (1+wo)
Proof of Corollary 5.1. Using the dictionary of notation Appendix D, we can plug the approximate solutions for Ką and μı derived by Maloney et al. [19] into (27) to obtain (31).
Therefore, the power law exponents W1, , of the weight covariances beyond the first layer, which enter only through their sum flg, do not affect the scaling laws of the generalization error with the dataset size and network widths. In particular, in the absence of label noise (1) = 0) we can approximate the scaling of (31) in the regimes of large small hidden layer width by
0 ? E~ { (av/ (rmin)
O'min 1, ag >> 1,
(32)
O'min < 1, 0u/ /mnn > 1,
which recovers the results found by Maloney et al. [19] for I 1 with unstructured weights. This behavior, and the agreement of (31) with numerical experiments, is illustrated in Figure 2. Consistent with Lemma 4.1, generalization with power-law weight structure is never better than with unstructured weights, as can be seen by comparing (31) with (25).
6 Bayesian inference and the Gibbs estimator at large prior variance
Thus far, we have focused on ridge regression (6). Though this is the most commonly-considered estimator in studies of random feature models [3-17, 19-21]. one might ask whether our qualitative findings-in particular, that feature weight structure beyond the first layer is generally harmful for generalization carry over to other estimators. Our approach to Proposition 3.2 is easily extensible to the setting of temperatue Bayesian inference, which has recently attracted substantial interest [13, 27, 34, 37, 45-47], sparked by work from Li and Sompolinsky [34]. In this case, we take seriously the Gibbs distribution p(v) xx e -BL which in the ridge regression case was simply a convenient tool, and interpret it as the Bayes posterior for Gaussian likelihood of variance 1/8 and a Gaussian prior with covariance T /1+1/(8 (83). is in this context conventional to fix = 1/9, such that the prior variance does not scale with B. We can then study the average of the generalization error
8

---

(a)
(b)
(c)
n=
1=1/2
1=1/2
30
30
a
a
0.50
0.50
0.50
0.75
0.75
1.00
1.00
1.00
2.00
8 15
1.25
15
1.25
& 15
3.00
1.50
1.50
4.00
1.75
1.75
2.00
2.00
0
0
1
0
1
1/0
1/0
1/0
Figure 2: Generalization for power-law spectra. (a). Target-averaged generalization error function of training data density 1/00 for shallow models (L = 1) of varying hidden layer width 0n 01/0g in the absence of label noise (n) 0). Here, the data and weight spectra have identical power law decay wo (b). but for fixed hidden layer width 01 01/00
= 1. (b). As in (a). but in the presence of label noise (1) = 1/2). (c). As in
4, fixed data exponent wi 1, and varying weight exponents wi. In all cases, solid lines show the predictions of (31), while dots with error bars show the mean and standard error over 100 realizations of numerical experiments with ng 1000. See Appendix F for details of our numerical methods.
(13) under this posterior in the zero-temperature limit 3 + co, which we refer to as the generalization error of the Gibbs estimator. We emphasize that this is not identical to the Bayesian minimum mean squared error (MMSE) estimator given by the posterior mean, which would coincide with the ridgeless estimator in the zero-temperature limit (see Appendix A).
For a deep RFM, this simply has the effect of adding "thermal" variance term to the generalization of the ridgeless estimator, which we describe in detail in Appendices A and C. We have:
Proposition 6.1. With the same setup in Proposition 3.2, the generalization error of the Gibbs estimator for a RFM is
CARF Eridgeless + Th Rr Omin >
az?
(33)
10,
otherwise,
where Eridgeless is given by Proposition 3.2, and Ke is defined as in (20).
Proof of Proposition 6.1. We derive (33) alongside Proposition 3.2 in Appendix A.
The Gibbs estimator is sensitive the scale of the random feature weight distributions through Re, while as noted above the ridgeless estimator is not sensitive to their overall scale. This direct dependence Ri means that the simple argument of Lemma 4. cannot be applied. Indeed, in the limit of large prior variance, where the thermal variance term dominates, structure can improve the performance of the Gibbs estimator. We make this result precise in the following lemma:
Lemma 6.1. In the setting of Proposition 1, consider Bayesian RFMs with weight covariances scaled as Te Ee for f = =,..... L. Then, in the non-trivial regime arg, Omin > 1 where the thermal variance non-vanishing, we have
lim
EBRF Il
II t=
Kt
Ki
) t=1
(34)
ar
a9
where the scalars Kę defined in terms of the un-scaled covariances Σ. as in (20) and 2² Ea, Therefore, in the limit of large prior variance, including structure in the weight priors is generically advantageous for generalization. If Ea, is not finite, then the bound is vacuous.
[āx]
The first part of (34) follows from (33) using the scaling properties of ngg while the bound follows from the bounds on Kę derived as part of Lemma 4.2.
Proof of Lemma 6.1.
In contrast, weight structure is generally harmful for the Bayesian RFM the limit of small prior variance, as its performance then coincides with the ridgeless RFM, can be seen from the scaling

---

of Kg. This example illustrates that there are cases in which, depending on the estimator used, weight structure in deeper layers can sometimes be helpful for generalization. However, whereas the ridgeless estimator is commonly used in practice, the Gibbs estimator is less standard, and the limit of large prior variance is certainly artificial. Therefore, we emphasize that we give this example to show that the behavior of the ridgeless estimator is not entirely general, not to show that weight structure can be helpful in practical settings.
Discussion
We have computed learning curves for models with many layers of structured Gaussian random features learning a linear target function, showing that structure beyond the first layer is generally detrimental for generalization. This result is consistent with the intuition that in deep linear models learning a single target direction it is sufficient to modify the representation only at the first layer [13, 36]. will be interesting investigate whether this intuition carries over to nonlinear networks learning complex tasks, particularly including multi-index targets [35, 48J. Moreover, we have con- sidered only linear, Gaussian models. As mentioned in the Introduction, past works have established Gaussian equivalence theorems for nonlinear RFMs with unstructured Gaussian feature weights. will be important investigate the effect of feature weight structure on Gaussian equivalence in future work, and determine whether our qualitative results carry over to nonlinear RFMs in the proportional limit.
Though our results are obtained using the replica trick, and we do not address the possibility of replica symmetry breaking, they should be rigorously justifiable given the convexity of the ridge regression problem [29, 33, 41J. We note that the replica approach makes it straightforward to handle models of any finite depth [30]. The relevant averages could of course be computed with alternative random matrix theory techniques, which could allow for a fully rigorous proof [5, 19-21]. Another more challenging setting to study with either the replica trick or rigorous techniques would be that in which one allows for correlations between weights in different layers. This setting could qualitatively capture aspects of feature learning deep networks, which induces couplings across depth [45].
In closing, we note that RFMs with structured weights may also have relevance for biological neural networks. A recent study by Pandey al. [39] considered RFMs with single layer of random features (L 1) with correlated rows (T1 * I. In several biologically-insprred settings, they showed that introducing this structure could improve generalization, consistent with our results. More broadly, biological neural networks are imbued with rich priors [49]; investigating what insights deep structured models afford for neuroscience will be interesting subject for further study.
Acknowledgments and Disclosure of Funding
We thank Alexander Atanasov, Blake Bordelon, Benjamin S. Ruben, and James B. Simon for helpful discussions and comments on draft of our manuscript. JAZ.VV and CP were supported by NSF Award DMS-2134157 and NSF CAREER Award 11S-2239780. CP received additional support from a Sloan Research Fellowship. This work has been made possible in part by a gift from the Chan Zuckerberg Initiative Foundation to establish the Kempner Institute for the Study of Natural and Artificial Intelligence.
10

---

References
[1] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconeiling modern machine- learning practice and the classical has-variance trade-off. Proceedings of the National Academy of Sciences, 116(32)11889-11 15854, 2019. dotthups://doi.orgg http:://doooooo...1..1
1ttp/100.07/paaas.. 19030701 16.
[2] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still)) requires rethinking generalization. Communications of the ACM, 64(3): 107-115, 2021. doi:10.1 Noo:1001145/344661 145/3446776.
[3] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75, 2019, doi:10. 10. 1ol:1001002/cpp 220088.
[4] Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30063-300770 2020. pnas. 1907378117.
1907378117. URL https: pnas. pwwps.ogg/ooiaab//1..o.o
[5] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. The Annals of Statisties, 50(2):949 986,
2022. doi: 10.211421-A02223333 URL https: : /ttp::/://oo//oo.o../.... 12111111-11111111
[6] Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "Ridgeless" regression can generalize. The Annals of Statistics, 48(3):1329 1347, 2020. doi: 100.10.2214191A001111 URL https://doi.
http////o..or/////////////////// 1214/19-A0S8844
[7] Hong Hu and Yue M. Lu. Universality laws for high-dimensional learning with ran- dom features. IEEE Transactions on Information Theory, 1932)1193,, 2023.
200:00.1099/TTT2222..22..
[8] Stéphane d' Ascoli, Maria Refinetti, Giulio Biroli, and Florent Krzakala. Double trouble in double descent: Bias and variance(s) in the lazy regime. In International Conference on Machine Learning, pages 2280-2290. PMLR, 2020. URL htttps:/proccediie d-ascoli20s html.
mlr press/v119/
[9] Stéphane d' Ascoli, Levent Sagun, and Giulio Biroli. Triple descent and the two kinds of overfitting: where why do they appear? In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 3058-3069, Curran Associates, Inc., 2020. URL https: httpps://prcceddiiii http://ooceeiin.nenrrreere neurips.. //tppp///00//f//e//ettffffeeeee (a11E/980.0..3540000022222211111
Paper .df.
[10] Ben Adlam and Jeffrey Pennington. The neural tangent kernel in high dimensions: Triple descent and multi-scale theory of generalization. International Conference on Machine Learning, pages 74. PMLR, 2020. URL https://proceeddnng mlr press/v119/ ad1am20a. html.
[11] Ben Adlam and Jeffrey Pennington. Understanding double descent requires a fine-grained bias- variance decomposition. In Advances in Neural Information Processing Systems, volume 33, pages 11022-1 2020. URL https:t:::: httpp:::/prooceedinnnge/eo//
wtwpiiinnnnn...uiiineeeee. newnienrisp.. www.ips..c/papeerereeeeee pttcc//pppe//2/////ee// /aahh///hhhh//////// 7o4200222293772201e0000447722222 htw.044477aabe11--bbbbbrrattttt Abstract html.
[12] Gabriel Mel and Jeffrey Pennington. Anisotropic random feature regression in high dimensions.
In International Conference Learning Representations, 2022. URL https::/oppeereeiiee
net/forum? ad=Jf
[13] Jacob A. 7 Veth, William I. Tong, and Cengiz Pehlevan. Contrasting random and learned features in deep Bayesian linear regression. Physical Review E, 105:064118 18, Jun 2022. 10 www..111////yyee........... PhysRevE. 105. 064118.
Veth,
URL https://link. aps owpp.orrg/oo/100 1103/
[14] Jason Rocks and Pankaj Mehta. Memorizing without overfitting: Bias, variance, and in- terpolation in overparameterized models. Physical Review Research, 4:013201, Mar 2022. 1oi: 000:000110/PPyyeeeRsseeeee... PhysRevReseaach. 013201. 1.12200..
URL atttps://inmt aps wwwpppppp.../....././/p/ 1103/

---

[22] Jachoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: an empirical study. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Ad- vances in Neural Information Processing Systems, volume 33, pages 15156-15172. Cur- Associates, Inc., 2020. URL https:/ htttps::/prooeeeinggs weurrpp..ccppppr//O00... wwtppappe/000//1122. wwppr..ppp... [15] Jason W. Rocks and Pankaj Mehta. Bias-variance decomposition of overparameter ized regression with random linear features. Physical Review E, 106:025304, Aug 2022. 10.1:00.110000000000110000111110 wwwp///ysee...1...00.0 PhysRevE. 106. 025304.
URL https:///ingg aps ors.org/doi/10 1103/
[16] Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1024-1034. PMLR, 13-18 Jul 2020. URL www.:mw......//.e.mm.e.mmm
https::/pproceedingg mlr wwwps/eeeaeeepe.p viness/viiii http///////oodeeo..aaaooo html..
[17] Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model alignment explain generalization in kernel regression and infinitely wide neural networks. Nature Communications, 12(1):2914, 14, May 2021. ISSN 2041-1723. doi: 101./0001100-1-00000 23103-1. URL https: / //woi. http://ti...oor/./////ee org/10. 1038/s41467-022 -21-14177-22---10-----
[18] James B. Simon, Madeline Dickens, Dhruva Karkada. and Michael R. WeWeese. The Eigen- learning framework: A conservation law perspective on kernel regression and wide neural networks. arXiv, 2022.
200004488850001122200002222 10.03922.
[19] Alexander Maloney, Daniel A. Roberts, and James Sully. A solvable model of neural scaling laws. arXiv, 2022. doi: 10. 48.54///RXXX.222000000
[20] Dominik Schröder, Hugo Cui, Daniil Dmitriev, and Bruno Loureiro. Deterministic equivalent and error universality of deep random features learning. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 30285-30320. PMLR, 23-29 Jul 2023. URL https: / //proceedings... mlr, press seress/v222/see /222///crr/eee22... html..
[21] David Bosch, Ashkan Panahi, and Babak Hassibi. Precise asymptotic analysis of deep random feature models. arXiv, 2023. doi: 0tt::0/48550/AAXX22200...666 URL https:/ //tpx///a.v.////////aa/eaaaaaaa org/ abs/2302. 06210.
[23] Alexander Atanasov, Blake Bordelon, Sabarish Sainathan, and Cengiz Pehlevan. The onset of variance-limited behavior for networks in the lazy and rich regimes. International Conference on Learning Representations 2023. URL htttps://openreviett www.urvviieeene/forrr... net/forum? id=JLINxPPVTh7.
[24] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment 2021 12 2021. 100000008//74255458/333322 https: //ts:///xxx doi. org 10. 1088/10811111 10w111088111----1 11///774--555 1772--462/2200- (468//cc3774
URL
[25] Federica Gerace, Bruno Loureiro, Florent Krzakala, Mare Mezard, and Lenka Zdeborova. Generalisation error in learning with random features and the hidden manifold model. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3452- 3462. PMLR, 13-18 Jul 2020. URI. utt.httss:// httpp:///////oeeeep/e//// mlr. www.mmml....m...eemmmmmmmmm ppwss/vvi9 http///111//geeeeeaeeee gerace20a.. html.
[26] Andrea Montanari and Basil N. Saeed. Universality of empirical risk minimization. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 4310-4312, PMIR, 02-05 Jul 2022. URL https: /ttp:////scccccoss...mm mlr, wwwpseeeeivvii
i22a. html.
12

---

[27] Hugo Cui, Florent Krzakala, and Lenka Zdeborova. Bayes-optimal learning of deep random networks of extensive-wide Ennellhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages (468-65211 PMLR, 23-29 Jul 2023. URL https: petttss:/pprett //proceed/ocs/gsss mlr. wwwpperssss00
Andreas Krause. Emma Brunskill, Kyunghyun Cho, Barbara
cui23b. html.
[28] Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jaehoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. arXiv, 2021. 4.0110048550AAAXX222222..6777 URL https:///aaaiiii htggabbs/212..07000
[29] Mare Mézard, Giorgio Parisi, and Miguel Angel Virasoro. Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications. World Scientific Publishing Company, 1987. dotthttps://doi..org orgp://///ooooo/.... O. 142/0271.
[30] Jacob A. Zavatone- Veth and Cengiz Pehlevan. Replica method for eigenvalues of real Wishart product matrices. SciPost Physics Core, 6:026, 2023,
URL https://scipppsst org/10. 0ee.221441ssiie SciiostPhysCore..oooo. 6. 2.002
[31] A. Caponnetto and E. De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 07 2007. ISSN 1615-3383, doi:
URL https: //ti: org/ /trgg//...0 10. 1007 00000//10200000000 0196-8.
[32] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv, 2020. 000110445500ARXX.2000..... 2001. 2001.08361. 08361.
URL https://aaat org/ abs/
[33] Andreas Engel and Christian van den Broeck. Statistical Mechanics of Learning. Cambridge University Press, 2001. doi.https://oii.org// http:///...//11111////999333 139164542
[34] Qianyi Li and Haim Sompolinsky. Statistical mechanics of deep linear neural networks: The backpropagating kernel renormalization. Physical Review X, 11:031059, 09 2021. 10.: 100.
[35] Adityanarayanan Radhakrishnan, Daniel Beaglehole, Parthe Pandit, and Mikhail Belkin. Feature learning in neural networks and kernel machines that recursively learn features. arXiv, 2022.
145:0044550//RXX..222222
URL https: org/ /2212//22222222 13881.
[36] Haozhe Shan and Haim Sompolinsky. Minimum perturbation theory of deep perceptual learning. Physical Review E, 106:064406, Dec 2022. 10. 10 11w.11/yyyycc...00..64.000 URL
https://link aps org//oi/10 LO3/PhysRevE....m 106. 064406.
[37] Boris Hanin and Alexander Zlokapa. Bayesian interpolation with deep linear net- works. Proceedings of the National Academy of Sciences, 120023):e200334512,, 2023. 10...01000pppaa.311111 2301345120.
URL https: bttps://www..r pnas wttppppp.......pp/ooooooopoooaps http://o//abb//1.17////////
[38] Zdzistaw Burda, Jerzy Jurkiewicz, and Bartlomiej Wactaw. Spectral moments of correlated
Wishart matrices. Physical Review E, 71:026111, Feb 2005. 1oi: 1tw.1111///yysRee.1..00000
URL https://linm //link. weaink.aps..om org/ooi////// /103/PhysRev.......
72.011111.
[39] Biraj Pandey, Marius Pachitariu, Bingni W. Brunton, and Kameron Decker Harris. Structured random receptive fields enable informative sensory encodings. PLOS Computational Biology, 18(10):1-28, 10 2022. doi: 1....7///oummmal.pcb.i 100. 1010484. URL https::/:/ooo htt.//ooooor////// 1371/ journal. pcbi. 1010484.
[40] Francis Bach. High-dimensional analysis of double descent for linear regression with random projections. arXiv, 2023.
[41] Jean Barbier, Dmitry Panchenko, and Manuel Sáenz. Strong replica symmetry for high- dimensional disordered log-concave Gibbs measures. Information and Inference: A Journal of the IMA, 2021. ISSN 2049-8772, doi: 10. 10.11///maaa///aab02., URI. https://////.... //doi. oorg/
10. 1093/ iiaaiiiia/////m..aaa..iiiiiaaiaa iaaii0..... iaab027.
13

---

[42] Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Mare Mezard, and Lenka Zdeborova. Learning curves of generic features maps for realis- tic datasets with teacher-student model. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Sys- tems, volume 34, 2021. URL https: pttpc//e/occceesssoeeoooe.s.//.s www.rdiiinnnnnnnn.nn.eee.m wwt..ps.cc.paaerr//eeeea (oo0acffcaaettecccccccffffrfrrr Abstract .html.
[43] Jacob A. Zavatone- Veth and Cengiz Pehlevan. Learning curves for deep structured Gaussian feature models. arXiv, 2023. http::////bbbooog/000455555///// 005644
[44] Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Out-of-distribution generalization in kernel regression. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 12600-12612. Curran Associates, Inc., 2021. URL https: htttpp::/pproceednng neurips.ccoom cc/ Paper. pdf.
[45] Jacob Zavatone-Vethh Abdulkadir Canatar, Benjamin Ruben, and Cengiz Pehlevan. Asymp- totics of representation learning in finite Bayesian neural networks. Journal of Statisticul Me- chanics: Theory and Experiment, 2022(1 1): 14008, nov 2022. 111111088/174-546688aa URL tistts::/dxx doi. org/10..// 10. 1088/174822222 011422254666880 00042-5566////8a.6. ac98a6.
[46] Jacob A Zavatone- Veth and Cengiz Pehlevan. Depth induces scele-averaging in overparam- eterized linear Bayesian neural networks. In Asilomar Conference on Signals, Systems, and Computers, volume 55, 2021. doi: 10.1 100100//EEECON5535500000000
[47] S. Ariosto, R. Pacelli, M. Pastore, Ginelli, M. Gherardi, and Rotondo. Statistical mechanies of deep learning beyond the infinite-wddth limit. arXiv, 2022. doi: 100100000500//AX..2000000 URL https: http://aaavvvvo///e org/ abs/2209 04882.
[48] Jacob Zavatone- Veth, Sheng Yang. Julian Rubinfien, and Cengiz Pehlevan. Neural networks learn to magnify areas near decision boundaries. arXiv, 2023. doi: 00011044550AAAX...300..1
URL https:tt/aaaate wwwpiiv.org//bb.e /30b///2331.0 11375.
[49] Lukas Braun, Clémentine Carla Juliette Dominé, James Fitzgerald, and Andrew M Saxe. Exact learning dynamics of deep linear networks with prior knowledge. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, volume 35, 2022. URL /ttps://openreete wtt.iieweeeeeeeeeeeeeeeeee..eeee www./ee/foooooooo foormmiddiiix2e
Kic.
[50] Robb J Muirhead. Aspects of Multivariate Statistical Theory. John Wiley & Sons, 2009. doi: 10. 1080000997797733665999
14

---

A Derivation of Proposition 3.2
In this Appendix, we sketch our replica-theory approach computing the learning curves, which leads to Proposition 3.2. Many of the steps of this calculation are all but identical to our previous works on replica approaches to the spectra of product Wishart random matrices [30], and on unstructured deep Gaussian random feature models [13], so we will sketch the major steps rather than spelling out all the details of the algebra.
A.1 Gibbs distribution and replica free energy
We start by introducing Gibbs distribution at fictitious inverse temperature & associated with the ridge regression loss
== 2 V1o
1 LXF y
2 +
1/2 2 1+11
v
(A.1)
with partition function
Z(BDD) f dive-br(v.))
(A.2)
where we denote by D all randomness in the problem. For any X > O, in the zero-temperature limit + oo, this Gibbs distribution concentrates around the unique minimum the loss [29, 33].
For the purpose the replica computation, is convenient to consider instead the partition function of the posterior of related Bayesian model, which corresponds to absorbing BA into redefinition of TL+1, and treating the ridge penalty as a Gaussian prior
prior N(0, FL+1).
(A.3)
We can then recover the partition function of the ridge regression model by undoing the rescaling: TL+1 +- F 1++1/ T1+1/(3X ((A)). Without this re-scaling- in the case in which the prior variance is held fixed as the temperature goes to zero zero-this is the Gibbs estimator in the cero-eepperauure limit, i.e., Bayesian model with Gaussian likelihood of vanishing variance [13, 34, 37, 45, 46].
This gives us the partition function
Z Ev- exp
Elo(x, yul?
(A.4)
which is the extension to structured priors of the Gibbs estimator partition function considered in [13]. By standard arguments, we expect the quenched free energy
lim
log Z,
(A.5)
P.Ro
be self-averaging in the thermodynamic limit, i.e., Epf almost surely [29, [29,33]. 33]. To compute the limiting quenched average, we use the replica trick, and write
f lim lim
log EpZ".
(A.6)
m -0 Po +000 pm
where we evaluate the moments ? for positive integer and assume that they can be analytically
continued to m - O.
Following previous work [13, 30], we can compute the quenched averages and integrate out the weights by introducing order parameters
1 - (Fv
(Co)at
T. [Fv2 - -w.)
(A.7)
n0
for f 0,
(Cz)ab
1
TU U.UeUUer U.vb
(A.8)
...... 12
S1

---

for ( = 1, I,..., L
and
1 (vo) (Ct)
_
(A.9)
Rr
along with corresponding Lagrange multipliers Č₁, which yields
E /
mm(m=1) (
dC dCo
(4Ti/n1)
dC1 dÈ2
/
(4ri/ng)m(mtt)))
dC2 dC,
exp
pm
2 (A.10)
s
for
mS log [I + 3Co + 1mp
( 3 _o]lmmmo C₁C, & Po]-1 Eol-'v(W.11.)) v(w.1m))
00
Σ
1 Of (r(CCCc)+ + log (eg C2+1 C4 8 Ex)
(A.11)
t=
where we let CL+1
I and
Σ, =1 8+1 E/T//2
(A.12)
for = O,...,, L. We note that X here denotes the Kronecker product, and we use the convention that the standard matrix product has higher precedence than the Kronecker product, i.e., AB & C = (AB) & C. Importantly, the quantity of interest-the the generalization error-is simply given by the diagonal elements of Ca, i.e., (Co)oo, Therefore, if we solve for the order parameters at temperature, we will obtain the generalization error.
In the thermodynamic limit, the integral over these order parameters can be evaluated using the method of steepest descent. make replica symmetric Ansalz, and seek saddle points the form
C2 = 4m + cel 1 m.
(A.13)
Č₁ qm 2
(A.14)
Under this Ansatz, have
B(co + 1/²)
S log(1 (40)
,9qu
1 (w,
EIIIno - -0 -1 ww)
ag
n10
+
Of
qede quét + cofe + Rs, log(1 1041)(0)))
t=0
ōe
- (q + ce+1ge)
- q:+1
(())
(A.15)
leading order in m, where recall the boundary condition gr+ c1. [30]. The resulting saddle point equations can be simplified to give a closed system for the replica non-uniform components.
auqu
(A.16)
1 -90
T
aeqi -at-19r--
B3g
(L = 1, I,...,
(A.17)
10
12-1
q:
(L O....,.))
(A.18)
1 98+19:08
S2

---

with the boundary condition 4L+1 = 1, and a linear system for the replica uniform components, (Ccoo + )
agco
(A.19)
(1+ + Bqo)²
1 (w, [T
01
o00 no
- 90:00 -w.
[1-
ōu
27 -)
+ 00
Boo
+ (1120 + c1d0)0oBo.
(A.20)
1 0000000
910000
OE 8 ct- litee
δt-1
01-1
(
2
σe-1
(1rêe-1 + codp- 1)0- Biie
(e (6=2, 2e.,,...,
1191--10-11
(A.21)
(w. E0(Inn
91 90 Z0) -2w
CD 70
50
(T-
To
cilBao
+ (giê0 + c100))iBB
(A.22)
1 -000
σz
Ce+1 LBae
+ Q0op
(
27
oz
(qe+10t + c++1 (e+11))20+1B.
(1-
(6= -- (.=.,..., (A.23)
92+11 Q10e
with the boundary condition CL+11 =
A.2 Converting between the Gibbs and maximum-likeliben estimators
As our primary aim is to study ridge regression, we must now account for the fact that the prior over the readout weights scales with the inverse temperature In particular, we have prior with scaled covariance I (L+11(8X) where F does not scale with 3. If we perform this rescaling in (A.16 and (A.16), we can see that the re-scaled order parameters
Adg
(A.24)
g =
a\ qe
(A.25)
(A.26)
(Bx)² c
(A.27)
obey an identical system of equations to the original order parameters in the Bayesian case inverse temperature
(A.28)
Therefore, if we can solve the saddle point equations for the Gibbs estimator in the rero-temperature limit, we can simply read off the corresponding result for the ridge regression estimator in the ridgeless limit. The important difference is that the replica nonuniform component do of Co is (L1/3) in the ridge regression case, hence only the replica uniform component co contributes to the generalization error. We note that this allows one read off the generalization error of deep linear RFM with unstructured features from the results of our previous work [13] simply by setting the Bayesian prior variance o² to zero.
A.3 Solutions for the generalization error
The replica-symmetric saddle point equations in (A.16) and (A.19) are nearly identical to those analyzed our computation of the maximum eigenvalue of structured Wishart product matrix [30],
S3

---

which in turn are related to those in our original paper unstructured deep linear RFMs [13] by the replacement of the spectral moment generating function of the identity matrix with the appropriate spectral generating functions. Given this similarity, and the fact that we have provided extensive exposition of how to solve such systems in those previous works, we will merely state the results for the order parameters relevant to the computation of the generalization error.
Let
Mc. (z) lim 1 tr|Ee(=Inn Σz)
(A.29)
Tig
be the moment generating function of Eg, with functional inverse M [ Then, at finite temper- ature, after eliminating the Lagrange multipliers, the replica nonuniform components of the order parameters are given by
A M-1
A aj)
(A.30)
aj
j=
for 8 = .g...; y L, where
3go
- =
A
(A.31)
1 3q0
satisfies the closed equation
A
A
M Σ, at
(A.32)
From [30], we recognize this as the self-consistent equation for the moment generating function M = of the feature kernel K XFF X x XT/no. evaluated at -1/3. Even the unstructured case, this equation must in general be solved numerically at finite temperature [30].
Given solution to this equation, we can solve the system of linear equations (A.19) for co, mirroring the computation of the extremal eigenvalues of structured product Wishart matrices in [30]. After eliminating the Lagrange multipliers, this calculation boils down to solving a three-term recurrence relation, which is detailed in previous works [13, 30]. We therefore simply state the result of this computation here. Let ( -A, which then satisfies
A 1-
1.
S M=1
(-5)- at
(A.33)
<
at
E=
For = ... L,, let
-M -
(A.34)
Of
so that fig satisfies
5 Eae
σz Ke + Ōe_
(A.35)
0f
Viewing as a function of Ç, we may alternatively write the self-consistent equation for Ç as
1 1 1
S kr(())
(A.36)
3
E= O2
In terms of Kg. let
M'
(-rie)
(A.37)
5
ai
5e
1
Exi
(A.38)
Kig + 0:
S4

---

We then finally have
ue
(1 5)
co
1 1 (w.
E. -0)
Ho 14p
ue
( Ea(Koono + -'o)-wwa) "w.NNo
14
710
1=1
1 - Hi
(A.39)
μi
Using the mapping of Appendix A.2 and again defining the weighted generating function
1 _w,
(1)
lim Ro-00 no
Ez(zIno Ea)
(A.40)
this yields Proposition 3.1.
We now want extract the zenottemperaturrrrdgggllss limit. As 3 - oo, the self-consistent equation for S admits the solution
C 5= 1,
(A.41)
valid for ar for all l, which gives qo 0(1), the solution
< = ao:
(A.42)
valid for og <1,00 00 01,...; ag, which gives go ~ 01133), and, for e, O,..., T, the solutions
(A.43)
valid for ar, < 1, az, < az, < for all + L,, which also give (L1B)). These solutions mirror those found in the unstructured setting [13]. We remark that, as [13], we can determine the regimes in which each solution is physical by demanding that the order parameters da are nen-negative
For the Ç + 1 solution, we immediately have
1 1
Co
(w,
Eio + 200--2w )mO
Pg
72
L
+
1-ke
ue
[ -o)
(w,
n1
L
+
(A.44)
He
Fm
where by minor abuse of notation we simply write Ke and μr for the corresponding quantities evaluated at Ç = 1.
If Ç + Olg, then Kę + 0 and #g J O. We can then apply I L'Hôóitall's rule to evaluate the limit in A.39, which corresponds to extracting the most divergent terms on each side of A.39, For the ( = ao solution, one finds that
Og 2 Co 1 OX
(A.45)
Finally, for the solutions with Ç = at, for l, = 1.... L. one finds that
1
(w] (nipttn + -o - )ko
=
O'g Tlu
at. n Ote
(A.46)
where we must be careful to recall that now satisfies
Ct
E.g
(A.47)
ag
Ku
S5

---

But, we recognize that ac, = Omin min min............. al,,.....,, so we will write
Kiiin
Kg
(A.48)
to avoid clashing with our notation for the Ç solution.
Therefore, recalling from Appendix A.2 that the generalization error for the ridge regression estimator in the ridgeless limit is simply given by co. we have
(Etz 1-me (15))
~3 v' + (Eiz 1-me) ) Cg. Ommin >
He
no
rriggeesss
Emin ('mmin
amin v/2
O'mnn 1, mmin 0g0
1- Crpin On 17, 1-00
amm
ag < 1, 0g < Omin
(A.49)
as reported in (23), where we again define the weighted generating function
(2) = lim no +20 no
w. E= + Eo) 'w..
(A.50)
To obtain the average generalization error for the Gibbs estimator in the zero-temperature limit, we must account for the effect of go in the regime ar 1, in all other regimes it is qo O(133) But, we recognize that
L Q0 = II
M
=
II 2=
Ke
(A.51)
at
j=0
from the definition above, hence we conclude that
I
ag. Omin >
CBRFM Eridgeless
Qmin < 1, O'min am
(A.52)
0,
ag < 1, 0g < amin-
A.4 Physical interpretation of the order parameters and thermal bias-variance decomposition
With these results in hand, we now comment on the interpretation of the replica uniform and replica non-uniform contributions
C = Iu + colm 1.
(A.53)
At the saddle point, have
(Co)ab = Ep ( (Fv -w,) 110
Ep - w.))
(A.54)
where (-), denotes the expectation with respect the replicated Gibbs measure at inverse temperature
3. Under the replica-symmetric Ansatz, considering off-ddagonna elements a &f b, we can use the fact that the replicas are initially uncoupled and identical to write
Co Cbb
(A.55)
Ep no
(F(v")
13 -.) TE, W.
(A.56)
Ep no
(F w.) T., -w.)
(A.57)
1 1/2 /22(2F(v)])))))))))))))))))))))) w.)ll
EE Tig
(A.58)
S6

---

Similarly, we have
Qu
o
Clb
(A.39)
1
Ep
(v W.) ED - w.) -c
(A.60)
R2
1
(Fòv F(v)3 -w.) E. +FF))+F(v)) - w.) 00
Ep
(A.61)
140
1
Ep
(Föv) Eo(
+ +ED no
(F(v) w.) Eo((vv)) - -w.) (A.62)
n2
1
ED
(Fòv)
Eo(Fāv)
(A.63)
n2p
ED
1
2 Fovl?)
1/2
(A.64)
n2
where we write óv v (v) Therefore, the saddle point, co and qo correspond exactly the bias and variance terms in the thermal birs-variance decomposition of the generalization error:
ED
1 | 1/2 2FV
(Fv-
ED ny
E (F w.)l + ED ED
E F5v 1
720
12p
8
(A.65)
This makes concrete argument which presented only intuitively in [13]. As result, if one considered the Bayesian MMSE estimator v = -v) the zero-temperature generalization error would simply coincide with that for the ridgeless estimator.
B Properties of the inverse generating functions
Here, we record few useful properties of the inverse spectral generating functions
1
ōe Kiz + oz.
Ms, (-Ke) Ezg
(B.1)
and their relatives
μe = a-ke (-Ke) = a.li
(B.2)
Rit + Tt.
These results are used in the proofs of Lemmas B.1 Dependence on width
Implicitly differentiating the self-consistent equation defining Re, we have
dkg
1
(B.3)
d(1/az)
Ed (met
showing that is a decreasing function of 1/ac. As 1/ar + O, should have me while as 1/az 1, we should have Kę 4
B.2 Behavior under rescaling
Consider the re-scaling Σ/ Ee for > 0. Then, we have Ke and Ry given by
Ms. (-Ke) = Esg
(B.4)
+ ōz
and
Ma; (-ni) = Es,
(B.5)
at
1/ + T(
respectively. We can then see that we should have
A/C TeRE-
(B.6)
S7

---

B.3 Bound on Kg in terms of isotropic spectrum
now prove that
Kr S (at
[)
(B.7)
in the relevant regime og 1. For any >> 0,
o σz
(B.8)
ot)
is concave function of oz 2 0, hence Jensen's 's inequality implies that
Oe (z + Te)
B
Erz
(B.9)
2 + 1E
Then, note that
Ōz
++ Es,
(B.10)
2 ōt
and
E E
2 ト
(B.11)
2 + E
are both decreasing functions of 2 0, and both are equal to 1 when 0. Thus, if kz >> 0 solves
Eog
(B.12)
af
Ki + oz
as specified by its definition and R2 > solves
E
(B.13)
Re + E. 1(
we must have
Kg Rg.
(B.14)
But, we can easily see that Ri = (az 1))( hence the claim follows.
B.4 Bound on μ terms of isotropic spectrum
We next prove that
1
Pe S
(B.15)
Oi
in the relevant regime og 1. By definition, have
27
δe Ki + ōi
Pe = 1 acLo
(B.16)
By Jensen's inequality and the definition of Ke, we have
Ō: Ki + T
Ō:
EE,
> Es,
(B.17)
Kig + Fe
(B.18)
o
As az > 1 by assumption, this bound is always positive. Therefore, conclude the desired claim.
S8

---

C Simplifying the generalization error for fixed data
In this appendix, show how the ridgeless generalization error can be simplified in each regime for fixed data. Using the solution to the ridge regression problem (6),
F XF)
F F
(C.1)
T
70
we have
lim
lim
ED
1/2 2 w.)ll
(C.2)
1,0 P.
TAp
lim
ED X PB T0p
lim
2 / VTo
(AIzI L+1
+ 1 x XF
F F
1/2 w.
no
(C.3)
Following our discussion in the main text, we may set F FI+1- Inc. without loss of generality, as otherwise may re-define Σz. Then, have
= lim XJO
lim
ED no
2 2 AAnz Tho
+ 1 F F E// 1/2 w.
no
(C.4)
In the subsequent sections, we will simplify this expression in each regime.
For the Gibbs estimator, we must account for the additional contribution to the generalization error from thermal variance. Following our previous work [13], we may compute the bias and variance terms directly from the posterior moment generating function of the readout weight vector,
Z(j) / dv exp
(-2
3 1/2 XFv y112 mlo
1
I 1/2 vIl +JTv)
(C.5)
2
L+1
exp (8n0
1122 (8n
XF 1+1 + Bmg 'F' X X -j
+ JJ + Bm x
(C.6)
yielding
(v) = vno (1 1 ('rrL
B L+1 + F XF
F
(C.7)
and
3 F x
- -v) = T +
XF
(C.8)
n0
We then can see that
(
(C.9)
A=1/B
which precisely in agreement with the conversion Appendix A.2. Considering the thermal bias-variance decomposition of the generalization error for the Gibbs estimator,
Ep
1 2 -w))l? ) =ED (Fv
1 =E 1 (F ww)]| ED no
2
ED
12
1/222
1//2Fövl''
110
no
8
(C.10)
we can then see that the bias term at zero temperature coincides exactly with the generalization error of the ridgeless estimator, found in Appendix A. The variance term is
lim ED 80000
| 1/2 F5vll
lim Ep B
1
E
Tzh
3 F F
x
-1 XF
FT
no
no
no
(C.11)
S9

---

In both the bias and variance terms, we can see that we may set TL+1 La. without loss of generality, as otherwise we may simply re-scale Σr as discussed in Lemma 2.1. Then, we need only consider the thermal variance term
lim ED 8-000
1 ng
1
Föv 12)
lim ED 3-000
1 EgF
Ing
+
f F XF no
F
7g
(C.12)
Here, we leave the thermodynamic limit implicit to allow the expression to fit on a single line.
C.1
The overparameterized regime
First, consider the regime p < min (no........ : n1).
Here, expect the kemnll
K XFF X
(C.13)
no
be invertible with probability one in the thermodynamic limit, and with overwhelming probability at large but finite size [50]. Applying the push-through identity and passing to the ridgeless limit, we have
lim
lim
ED
E 1/2 21 X
1 XFF x (AI, (AI++
y
2n
1/2
X10
P.
+00
no
/mo
n1
(C.14)
lim
Ep no
FFF
1/
FF X (XFF' x xT)
E 1/2
W.
12
(C.15)
Averaging over label noise, have
(XFF x -1 Xw. E// W. m Σ FF
lim
ED R2g
p,0g
17 lim Pe
Ep
FF
X (XFF -1.
(C.16)
Turning our attention to the Gibbs estimator, we can use the Woodbury identity to write the thermal variance term as
ED
Fòv
77
8
3 F XF) no
ED
tr F
Inz.
+
FT
(C.17)
ng
EnFF X (I-Inn. + no
1 XFF x
=ED
tr FF
ED
tr
XFFT
no
710
(C.18)
Ep no
tr FF ED tr EFFF X XFFFFXT no
XFFT
+O(B-)),
no
(C.19)
where the thermodynamic limit is implied [13]. Therefore, in this regime do not expect the thermal variance term to vanish, consistent with Proposition 6.
C.2 The bottlenecked regime
If mi.......... ...., n min p}. then the situation is slightly more complicated. Let
Lmin min T2g
(C.20)
S10

---

be the index of the narrowest hidden layer. Then, let
U
Uemin E R Mmiin
(C.21)
mh ... Mami
and
F2
Up
Unmintt .... Ur Pmin XRL
(C.22)
/ .... -.L
such that
F-FFF2
(C.23)
Then, the matrices F X xF, and F2F2 are invertible with probability one, and upon passing to the ridgeless limit we have
lim ED
ll 1o
1 F1
(F
XF
w
(C.24)
P,00 Averaging over the label noise,
T1o
lim
ED
D
XF
Xw,
2,,',,112
w.
100
720
lim P. m
Ep
F
X
XF
F
(C.25)
Focusing on the label noise term, we have
Epl E FXF
ED
E X
(C.26)
Then, using the fact that
x X Wng(Eo:P))
(C.27)
we have
F F.X x XF Wamn E..1.)
(C.28)
Then, expect the matrix F, En be invertible with overwhelming probability, the standard formula for the mean of an inverse- Wishart distribution [50] gives
1
[F (
FF FoF
(C.29)
p Ammin
so
lim PL-
ED EoFi XF
lim
Phnin
(C.30)
+000 p
Mmmin
Omin
(C.31)
1
Omin
This proves that, in this regime, the label noise term does not depend on data structure, matching the result of our replica computation.
Considering the Gibbs estimator, we can see immediately that the thermal variance term is 0(3-1) because the fact that F. x T XF, and F2F are invertible with probability one. This is consistent with Proposition 6.1.
C.3 The overdetermined regime
Finally, consider the regime in which no min(p, ni...., nL). Then, both X T and FFT invertible with probability one, and we can easily compute
c =
lim
lim Ep
1
Σ
1/2
(AIn,
+
F x
X
FF
X y w. w.l (C.32)
P +00
ALO
120
no
/Ro
lim
ED EDIEE
1/2 X x 1x E
(C.33)
Pi D00
1
lim
Ep Ex X) -1-
(C.34)
S11

---

Then.
(x
(x"x)-1 W=, p),
(C.35)
so using the formula for the mean of the inverse- inverse-Wishart [50] we have
c
1f
lim
Ep tr Eo X
(C.36)
P: TL +00
110
lim
(C.37)
P. +00 p ng
11
(C.38)
00
as we found using replicas.
Here, again, that the thermal variance term for the Gibbs estimator is O(B-1), matching Proposition 6.1.
D A notational dictionary
In this appendix, show that special cases of general result recover the results reported in previous works. This is largely a matter of translating notation, as the conventions used in different communities are often odds with each other.
D.1 Shallow ridgeless regression
In the shallow case L = 0, our general result for a fixed target (23) reduces to
Ki +
e/ (K5)
nf,
ag
Ma
(D.1)
0g 1
ag
<
where, writing expectation with respect the limiting spectral distribution Eg as Egg we recall
that Kg is determined by the implicit equation
-ME (-Ho)
Boo
(D.2)
Ko +
ao_
in terms of which we have
- a0.oo (
2
ao
(D.3)
+ dy
and that
(2) lim Ti0
w, Eo(iIno En) Eo)-'w..
W..
(D.4)
Working in the eigenbasis of Eg and assuming that l|w, 1|2 ny, we introduce the weighted density
p(ao) = lim 1
(w. (0,0300000 -o,)
(D.5)
70 1=1
in terms of which we have
Oo
(b(2) = Eoorp
(D.6)
50.
and
3 (z) Eropp
00
(D.7)
(2+
We can now make contact with the result of Hastie et [5]. We note that those authors use an opposite definition for and n: following the convention in the statistics literature, they use p for
$12

---

the dimensionality and n for the number of examples, while we follow the convention in the physics literature of using no for the dimensionality and p for the number of examples. Then, Hastie et al. [5]'s y, defined such that, in our terms, na/p y, is precisely our 0gp- Moreover, they use H()) to denote the limiting spectral law of Σg, and G(z) to denote the law corresponding the weighted density we define above as p. We note also that their o² is our rz². In these terms, their Theorem 2 gives the generalization error in the overparameterized regime ag > 1 as
Eco (
Egg (Loo00
1 + a0co
Borwe (1 + co0000)
do
+ tn 27oc
(D.8)
Bgg (I+epdggo))
where is defined by the implicit equation
E
(D.9)
0g
Subtracting one from both sides, the implicit equation for co gives
Cookgoo
= Eog
(D.10)
1 + Cyag0u
from which we can see that
1
Cg00g
(D.11)
Ki
Then, have
Eogrp
N 2 Boomp
do
(D.12)
30
(No + o0)
ROv! (No)
(D.13)
and
(000000) )2
E
E
To )
0g0
(D.14)
B (I+Coaodo)*
E
(I+oy00d0)
E
too)
(D.15)
E
(oo+
140
(D.16)
Ogp Eg
Kodo
(No
140
(D.17)
o7
ong
to0
t00
1- 140
(D.18)
140
which proves the equivalence of our results. This also shows that we recover the results of other works on ridgeless kernel interpolation [4, 6, 7, 16, 17] that are in this setting equivalent to the results of Hastie et al. [5].
D.2 Two-layer linear random feature models with unstructured weights and isotropic targets
Another special case in which we can make contact with prior work that of a single hidden layer (L 1) and with target averaging. In this case, our general result (27) reduces to
x(a0)
1 Pb
140
1 au
1 ,),p
n?
ag 01
Q1
1
C0
+
a1
n7²
a 1, 0i < 0g
(D.19)
a1
a1
a1
00
0g 1,00 0g 01
0g
S13

---

where in this case we find it convenient to write ko/ au and ang /mmi in terms of x(2), which solves
-2MMs, S. =xx(2]]
(D.20)
āo
Es.
(D.21)
[x(2) 5o
is then easy to show that our result agrees with that of Maloney et al. [19]. Their notation is:
M no
(D.22)
N n21
(D.23)
T p.
(D.24)
When M > N, their result is, in the absence label noise,
N/T A (N, N <T
(D.25)
M
T/N (I, N
where A solves
tr Er/oo(A ( M)IM + NI
(D.26)
and similarly for A (T,(T,M). To map this our results, let us de-ineene
A (N = M (N,
(D.27)
which then satisfies
1
1 =
tr EE (A (N, M)L + (N/M)Eo))*)
(D.28)
M
or
M
M = -ME
A (N.
(D.29)
N
Then, we can see that, in our notation,
Á (N, =
= X
0
(D.30)
N
while
M ( x(ao).
A- =x
(D.31)
Then, noting that
1
(D.32)
T-N
1-
1/a1
a1
01
1'
we can see that we recover their result in these regimes. We can also map their Ag to our 14g For T < M, they let
A
M
To?
(D.33)
1
A
(To
1=1
M
of
(D.34)
T j=1
(0, + M AM/T
hence we can see that
A
(D.35)
1 Ao
S14

---

(a)
(b)
(1)
(3)
a, (3)
1-
(1)
(2)
(2)
0
2
1 1/a,
Figure D.I: Phase diagrams in different parameterizations of the thermodynamic limit. (a). Phase diagram in the (ao, 01) plane. Region (orange) is the overparameterized regime, Region (yellow) the bottlenecked regime, and Region 3 (green) the overdetermined regime. (b). As in (a), but in the (1/a0, / (v)) / plane, matching the parameterization used in our previous work [13]. Note that the plane is divided identically, but the locations of the phases are swapped.
This mapping also enables application of their interpolating approximate solutions for A and Ao in the case of power law spectra. For a finite-size spectrum
0+ ju
(D.36)
with
0+
M 11
(D.37)
where we denote the exponent by rather than as Maloney et al. [19] do to avoid clashing with our notation elsewhere, they obtain the approximate solution
M N
+ 12+ w01 - k)] (1 (M }
N
A M) M
1
k
-
N < M
(D.38)
N M
for
1t
T 1+.
(D.39)
sin
T I+w
sinc
T I+w
which leads to the expression
1(2 - + (1 -b)] (1-2)
X(=)=
0
2
=>1
(D.40)
Moreover, for T M, they give the approximate solution
(T, = M/T-1
(D.41)
By applying these results, obtain the result claimed in the main text. (31). We note that we fix o_ to be constant rather than 04 as Maloney et al. [19] do, which ensures normalizability the limiting eigenvalue distribution at the expense of diverging moments.
D.3 Deep linear models with unstructured weights and data
In [13], we studied deep Bayesian linear models with unstructured features and data.2 There, and in very recent work by Schröder et al. [20]. a different parameterization for the thermodynamic limit
In [13]. we focused on the Gibbs estimator rather than on the ridgeless maximum-likelihood estimator (MLB). However, given the average generalization error for the Gibbs estimator, it is easy to obtain the generalization emor for the MLE. We discuss this point in detail in Appendix A.
$15

---

was used:
P. nl. ................................
,L RL - 00, with - a,
70 (e=1,..... D)
(D.42)
110 110
where we decorate à and te with tildes to avoid confusion with parameters used elsewhere in the present work. The conversion to the parameterization used in the present work and in [30] is then given by
ā 1
(D.43)
0x0 (f= (0=,...., L).
0g
(D.44)
Og
Though these parameterizations are mathematically equivalent, it is important to distinguish between them as they give phase diagrams that divide the plane identically but swap the locations of the phases, as is shown in Figure D. Moreover, though the parameterization used here is more convenient for the replica computation [30], that given in (D.42) conceptually useful, as it closer what one does in practical machine learning settings: the input dimension no is fixed by the task, and one can vary the dataset size p and the network widths ng. This why we plot the phase diagrams in Figure in the (1 /oo: 01/00) plane.
E Large-width expansions
In this appendix, we consider the limit of large width, i.c., the limit in which 01 ar - oo for fixed og. Our first task is to determine how the quantities Kg behave in this limit, as it through these inverse generating functions that the hidden layer widths enter the generalization error.
Starting from the defining equation
Ea
(E.1)
+ oz
we can see that Ke should tend to infinity linearly with ar as ae + co. In particular, we should have
Kit + Es, [ōe]
(E.2)
a
at large widths. Then, pr has limiting behavior
(
δe Ke + oz
He = 1 -xEE,
(E.3)
(E.4)
From this, model in Proposition 3.2 reduces to that of shallow ridgeless regression as in Corollary 3.1, as we would expect.
that in the infinite-wiee limit the generalization error of the random feature
We now want to compute the leading correction to this result. the unstructured case, this easy, because we have (az 1)ōg, hence there is ((1) correction and nothing else. More generally, we assume Laurent series bchavior the form
Kg agtt 1o
-K² +....
(E.5)
aF.
Expanding, we have
σ
ōz(ār + x:) am(
+ O(a
(E.6)
hence, we integrate term-by-term, we have
1
E2,
E,, 15
Es, [0 + O(a
-
Oreti
(x
(E.7)
S16

---

If we solve order-by-order, we again find that
1og Es, [öt]
(E.8)
while the coefficients of all higher-order terms in 1/ar must vanish. In particular, this gives
E5, [o Kig Es, [0
(F.9)
This computation assumes that the spectrum has finite moments, which not the case for the heavy-tailed power law spectra considered in Corollary 5.1.
Then, have
2
N4 arEEs
(E.
Esg [d?]
Es, [6
Es,
(0 m2
+ +(()))
(E.
a<(x))) )2
(x))s
E,, [o]]
1
+ +O(a; 2).
(E.12)
Bie [o,]
az
Collecting our results, we have
Ea [o
Kig BR [ōr]uxe
+ O(a
(E.13)
Esg ( 2 a8
and
Ex,
+ 3)
1E.14)
E,
[ Oz
Each term in these expansions has the expected behavior under rescaling: we Σ = Te Ee for Te > O, have Ri Tyfe and μl μtg.
Then, substituting these expansions into (23), we find that the generalization error of an RFM in the ridgeless limit expands at large widths as
Kă 1/ (Ko)
1 po 1,2
Ho
110
Esg [021
(HOW)(NO) + 77
Es, [ā,]3 ae
(a ....,.777)
(E.15)
the regime au > 1; if ary < the generalization error does not depend on the hidden layer widths so long as they greater than 1.
For an RFM trained using the Gibbs estimator, as considered in Proposition 6.1, we find that
2 +
ve (mo)
1 1- 140 1
Kip
$2
BBRPM =
11
110
4
Es, [
Ko 1 (Ko)((m)) 11 _
+
axe
+ Oww
(E.16)
where we have defined
2² =
Es, [ōd)
(E.17)
8m
S17

---

uodn expanding the thermal variance term
L
L
II
Ko
Bøg [ōt]
ax
ag
8=
===1
1
Er, [o 1
Ri [iee]
0kg
Es,,
[āz]
8=1
O ( 2).
(F.18)
Here, denote by Ow all terms of O(a,7) 2) for given layer 1,..., L terms of O(a "pp)) for two different layers e,
F Numerical methods
In this appendix, we describe the numerical methods used to produce Figures 1, 2. All simulations were performed using MATLAB 9.13 (R2022b; The Math Works, Natick MA, USA; https: //www. mathworks. wwwccoo/////// http//rrduc//////ooooo /matlab html) desktop workstation (CPU: Intel Xeon W-2145, 64GB RAM). They were not computationally intensive, and required less than an hour of compute time in total. Code to reproduce the figures is archived as part of the online supplemental material. Numerical computation of solution to ridgeless regression problem-the minimum-norm interpolant- was performed using the lsqminnorm solver (https: //www//www/////// mathworks. com/help/ matlab/ref/ /tt/rrff/sssmmm /ls/mminmmmnmmmmmmmm html), which uses an algorithm based on the complete orthogonal decomposition of the design matrix.
S18


Reviews:
[{"review_id": "NSP8dWFkqL", "reviewer": "Reviewer_bdDi", "summary": "The paper derives the learning curves (generalization error vs number of samples) for random linear deep networks with Gaussian weights with non-trivial correlations. The correlations at the first layer control the performance of those networks, while all other layers (possibly of different widths) are equivalent to a single layer of minimal width among them.", "questions": "* Can the minimal generalization error be achieved at a finite lambda value?\n * Is there any effect of depth when alpha_min is kept fixed?", "limitations": "The authors are clear about the limitations of their work, where only the behaviour for the ridgeless case is studied (and hence the behaviour under noise is not well understood), and only linear networks are studied (and hence the depth does not play an effect), with random initialization (and hence there is no training).", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "*\tQuality: the main result that in the noiseless case, correlations at the first layer improve performance, while correlations in the other layers degrade it (Lemmas 4.1 and 4.2) is interesting (and is not fully captured by the summary “representation learning at only the first layer of a deep linear model is sufficient to achieve optimal performance”). The additional result for generalization error of scale-free correlations, which converge with previously known results for uncorrelated weights, is very nice.", "weaknesses": "*\tQuality: it is not justified why the authors focus on the “ridgeless limit”; can’t the minimal generalization error be achieved at a finite value of lambda? Why not?\nThe model studied seems to collapse for large alpha0 (figure 1 a vs b), but the phenomena is not explained.\n *\tClarity: as a theory-heavy paper, the authors could have done a better job in keeping the notation clear. p was not properly defined; I assumed it was the number of samples. The spectral moments generating function from eq 15,17 is introduced only at eq 19. The functions (or scalars) phi and phi bar (evaluated at k0) are not introduced. The important “expectation with respect to the limiting spectral distribution” is not properly defined (“is defined in eq X of the SM” would have been fine as well). \n *\tSignificance: the results of sections 4 and 5 seem to suggest the depth of the network does not contribute anything, as only alpha_min enters the results. This is probably a limitation of the linear model, and thus the discussion on the behaviour of deep networks seems empty. Also, the focus on the noiseless case makes it hard to extrapolate what (if any) of the results hold under noise at an optimal finite lambda.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### Strengths:\n*Quality: the main result that in the noiseless case, correlations at the first layer improve performance, while correlations in the other layers degrade it (Lemmas 4.1 and 4.2) is interesting (and is not fully captured by the summary “representation learning at only the first layer of a deep linear model is sufficient to achieve optimal performance”). The additional result for generalization error of scale-free correlations, which converge with previously known results for uncorrelated weights, is very nice.*\n\nThank you for your careful reading of our paper, and for your positive assessment of its results. We will revise the summary sentence in the Introduction to: “These results are consistent with the intuition that representation learning at only the first layer of a deep linear model is sufficient to recover a single teacher weight vector..” We hope the referee agrees that this more clearly describes our result.\n\n### Weaknesses:\n\n- *Quality: it is not justified why the authors focus on the “ridgeless limit”; can’t the minimal generalization error be achieved at a finite value of lambda? Why not? The model studied seems to collapse for large alpha0 (figure 1 a vs b), but the phenomena is not explained.* \n\nThank you for this question. Please see our detailed discussion of this point in the common response to referees. The ‘collapse’ observed by the reviewer in Figure 1b reflects the fact that the generalization error of the model with power-law features diverges as $\\alpha_{\\ell} \\downarrow 0$, which results from the fact that these spectra have diverging mean. \n\n- *Clarity: as a theory-heavy paper, the authors could have done a better job in keeping the notation clear. p was not properly defined; I assumed it was the number of samples. The spectral moments generating function from eq 15,17 is introduced only at eq 19. The functions (or scalars) phi and phi bar (evaluated at k0) are not introduced. The important “expectation with respect to the limiting spectral distribution” is not properly defined (“is defined in eq X of the SM” would have been fine as well).*  \n\nThank you for this suggestion. \n1. We note that $p$ was defined in Line 50 of the submitted manuscript (“...with $p$ i.i.d. training examples…”). We recognize that there are varying conventions for the number of training samples in the literature, with $p$ being the common convention in physics and $n$ the usual choice for statisticians. We will add a footnote to emphasize this convention. \n2.  The spectral generating functions are introduced in Equation 14, under Assumption 3.1 (Lines 89-92). \n3. The function $\\psi$ is defined in (14) as part of Assumption 3.1. Can the reviewer point us to where we have failed to define $\\phi$?\nWe will replace Lines 98-99 of the submitted manuscript with the following clarification: “...where $\\mathbb{E}\\_{\\tilde{\\sigma}\\_{\\ell}}[h(\\tilde{\\sigma}\\_{\\ell})] = \\lim\\_{n\\_{\\ell} \\to \\infty} \\frac{1}{n\\_{\\ell}} \\sum\\_{j=1}^{n\\_{\\ell}} h(\\tilde{\\sigma}\\_{\\ell,j})$ denotes expectation of a function $h$ with respect to the limiting spectral distribution of $\\tilde{\\mathbf{\\Sigma}}_{\\ell}$, for $\\{\\tilde{\\sigma}\\_{\\ell,j}\\}$ its eigenvalues.” \nWe hope these clarifications address your concerns. We will carefully go over the paper to address further points of clarification.\n\n- *Significance: the results of sections 4 and 5 seem to suggest the depth of the network does not contribute anything, as only alpha_min enters the results. This is probably a limitation of the linear model, and thus the discussion on the behaviour of deep networks seems empty. Also, the focus on the noiseless case makes it hard to extrapolate what (if any) of the results hold under noise at an optimal finite lambda.*\n\nThank you for this comment. It is not correct to say that only $\\alpha_{\\mathrm{min}}$ enters the generalization error. This can be seen from the formula for the generalization error given in Proposition 3.2, equation (23): in the overparameterized regime, the relative widths $\\alpha_{\\ell}$ for the other layers enters into the functions $\\mu_{\\ell}$ defined in equation (21). Most simply, consider the isotropic case given in Corollary 3.2, equation (25): in the overparameterized regime $\\alpha_{0}, \\alpha_{\\mathrm{min}} > 1$, the generalization error has explicit, obvious dependence on $\\alpha_{\\ell}$. This is also true of the subsequent corollaries in Sections 4 and 5. It is true that only the narrowest layer determines whether the model is overparameterized or bottlenecked, but the other layers have a definitely non-trivial effect. We elaborate on this issue under your subsequent Question regarding this issue. In regards to finite regularization, please see our common response.\n\n### Questions:\n- *Can the minimal generalization error be achieved at a finite lambda value?*\n\nPlease see our common response for a discussion of finite-$\\lambda$ properties. In short, for the deep models we consider here it is challenging to analytically determine the optimal ridge..\n\n- *Is there any effect of depth when alpha_min is kept fixed?*\n\nThank you for this question. As mentioned above, there is most definitely an effect of depth even if $\\alpha_{\\mathrm{min}}$ is held fixed. To potentially see this more clearly, consider the case in which all layers have the same width $\\alpha_{1} = \\alpha_{2} = \\cdots = \\alpha_{L}$. Then, in the overparameterized regime $\\alpha_{0}, \\alpha_{1} > 1$, we have $$\\epsilon = \\left(1 + \\frac{L}{\\alpha_{1} - 1}\\right) \\left(1 - \\frac{1}{\\alpha_{0}} \\right) + \\left(\\frac{1}{\\alpha_{0} - 1} + \\frac{L}{\\alpha_{1} -1}\\right) \\eta^2$$ Therefore, if one fixes $\\alpha_{\\mathrm{min}} = \\alpha_{1}$ and increases the depth $L$, the generalization error will in this case increase linearly. Conceptually, this is due to the fact that increasing depth increases the variance of the random feature kernel. We will elaborate on this point in our updated manuscript. "}, {"review_id": "CTyrw79FFH", "reviewer": "Reviewer_hUXg", "summary": "This work studies the asymptotic risk of deep linear random features models (RFMs), with a high dimensional analysis based on the replica method. It extends previous work on this topic by relaxing the standard i.i.d assumption for the Gaussian weights in each layer. \n\nSeveral consequences of their anaysis are discussed: (i)  several known results in linear regression, isotropic models, infinite width RFM, are recovered as special cases ; (ii) it is shown that feature anisotropy is detrimental, in the sense that the risk of the isotropic model  lowerbounds the risk of the general model ; (iii) it is shown that feature anisotropy does not affect the scaling laws of the risk ;  (iv) going beyond ridge regression, the analysis allows for the derivation of the risk of the Gibbs estimator, where feature anisotropy is shown to be generally beneficial (resp detrimental) for  large (resp small) prior variance.", "questions": "* As the authors mention in the conclusion,  Gaussian equivalence theorems could potentially extend these results to more general activations (and losses).  Including this extension would considerably increase the paper's scope. Could the authors provide a bit more details about the extent of the technical gaps to be filled to achieve this ?\n\n* Could the authors comment on the comparisons with the results of Gerace et al, which seem to address the case of general RFMs with any (fixed) feature matrix F satisfying the balance condition (1.7)?\n\n**References**\n\nGerace et al, 2020.  Generalisation error in learning with random features and the hidden manifold model. https://arxiv.org/pdf/2002.09339.pdf", "limitations": "Adequately acknowledged.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* Sound piece of theoretical work. \n\n* Relaxing the standard feature isotropy assumption seems to be a natural extension of the recent line of work on deep RFMs. Since the learned features of deep learning models often exhibit complex correlations, it could also provide insights on the effects of feature learning of deep networks in a controlled setting. \n\n* The paper is very clearly written and enjoyable to read.", "weaknesses": "My main reservation regarding this paper is related to its scope -- and the significance of the results. \n\n* While the analysis presented in the paper is novel and fills a gap in the literature by relaxing a standard assumption, the technical innovations appear to be somewhat limited and incremental compared to previous work, such as References [28].\n\nI believe some related references were missed, see e.g., Mel & Pennington (ICLR 2022) -- which also investigates the effect of feature anisotropy  in random feature regression. I understand the main technical difference is that they work with shallow models with a Gaussian feature matrix, whereas the current paper work with Gaussian products (one may argue that the first setting is sufficient to capture the effects of anisotropy in RFMs). \n\n* The insights gained from this analysis also seem to have certain limitations. For instance, considering  that in setting (13), the risk is studied in expectation over rotation invariant Gaussian matrices $Z_\\ell$ at each layer, the result of Section 4 on the optimality of the isotropic case appears rather unsurprising to me. \n\nMoreover I believe that the studied setting may not allow for  significant insights into representation learning (not that the authors claim otherwise, but this is one of the motivations for the work i.m.o).  For example , the assumption of Gaussians requires layerwise independence, while in feature learning scenarios, one would expect learned features in different layers to be correlated with each other -- and with the underlying data structure. So from that poinf of view, I feel the assumptions underlying this work are still quite restrictive. \n\nOn a minor related note, the general-sounding statement found in Section 1, \"these results are consistent with the intuition that representation learning at only the first layer of a deep linear model is sufficient to achieve optimal performance\" is a bit puzzing, as it seems to contradict known results in the topic, e.g. those on the implicit sparsity bias in deep linear networks (which requires representation learning in multiple layers, see e g., Woodworth et al, 2020).\n\n**References**\n\nMel & Pennington (ICLR 2022). Anisotropic Random Feature Regression in High Dimensions. https://openreview.net/forum?id=JfaWawZ8BmX. \nWoodworth et al, 2020. Kernel and rich regimes in overparametrized models, https://arxiv.org/abs/2002.09277.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the referee for their careful and favorable assessment of our work. We hope that they find that our revisions will strengthen the paper. \n\n### Weaknesses:\n\n*My main reservation regarding this paper is related to its scope [...]*\n\nThank you for this comment. As we acknowledge, our work is a direct application of the formalism discussed in Ref. 28, which reflects the fundamental relationship between the generalization error of kernel ridge regression and the spectral statistics of the kernel matrix. However, our solutions in the ridgeless limit and detailed study of large-width properties are even in the context of the spectral properties novel. \n\n*I believe some related references were missed, see e.g., Mel & Pennington (ICLR 2022) [...]*\n\nWe regret that we missed this reference in the submitted manuscript, and will add it to the revised version of our manuscript as part of an extended discussion of prior work on RFMs. To the best of our understanding, Mel and Pennington allows for anisotropic input correlations while still assuming uncorrelated weights, as defined in the prose between equations (2) and (3) of their ICLR paper. Moreover, they assume isotropic regularization in the definition of the regularized kernel matrix between equations (3) and (4). Therefore, if one has even a single layer of random features with anisotropic row and column correlations, our setting is more general. \n\n*The insights gained from this analysis also seem to have certain limitations [...] the result of Section 4 on the optimality of the isotropic case appears rather unsurprising to me.*\n\nWe agree that rotation-invariance makes the optimality of isotropic weight spectra intuitive; this rotation-invariance also makes it intuitive why the dependence of the generalization error on the spectra should decouple across layers. We propose to add the following comment to Section 4 under Lemma 4.1 to note that “The fact that we study generalization in expectation over matrix-Gaussian random features makes the optimality of isotropic spectra intuitive. Since we can represent each structured weight matrix as a product of fixed covariance matrices multiplying an unstructured, rotation invariant Gaussian matrix, it makes sense that there should be no preferred directions along which variance can be concentrated to reduce error.” We hope that this addition will make this limitation of our analysis more explicit. \n\n*Moreover I believe that the studied setting may not allow for significant insights into representation learning [...].* \n\nWe agree that the setting of our work is restricted, which facilitates our analytical progress. Moreover, we agree wholeheartedly that it would be interesting to address the case of correlated weights across layers. As a first step, this could perhaps be addressed within a model in which the weights are jointly Gaussian across layers. However, even if the weights within layers are uncorrelated, this is not directly addressable within the formalism used here, which relies heavily on the assumption of layer-wise independence. This limitation is shared by other physics-style approaches to product random matrix problems. We would therefore suggest that detailed study of such a model could be an interesting topic for future work, with the results presented here as a first step towards understanding RFMs with maximally general weight correlations within and across layers.  \n\n*On a minor related note, the general-sounding statement found in Section 1 [...] seems to contradict known results in the topic [...].*\n\nWe acknowledge that this statement, as written, is not sufficiently precise. We will revise it to read, “these results are consistent with the intuition that representation learning at only the first layer of a deep linear model is sufficient to recover a single teacher weight vector.” We appreciate the referee’s feedback on whether this revision addresses their concern, and will also cite Woodworth et al. in our updated manuscript. We note also that Woodworth et al. focus on optimization with gradient flow. \n\n### Questions:\n*[...] Gaussian equivalence theorems could potentially extend these results to more general activations (and losses). [...]*\n\nExisting Gaussian equivalence theorems for deep nonlinear random feature models from Schröder et al. and Bosch et al. (both from 2023) depend on certain concentration and approximate orthogonality assumptions for feature Gram matrices (see eq. 11 of Schröder et al, https://arxiv.org/pdf/2302.00401). When the weights are independent across features, these properties can be verified. For weights drawn from a general matrix Gaussian, this does not obviously follow. To prove Gaussian equivalence for nontrivial covariance matrices, one would need to determine the class of matrices and of nonlinearities for which the required orthogonality conditions can be established. We would be happy to add a comment on this point to the discussion.\n\n*Could the authors comment on the comparisons with the results of Gerace et al [...]?*\n\nThank you for this question. The results of Gerace et al depend on the solution to the set of self-consistent equations (2.4), which in turn depend on the limiting Stieltjes transform of the feature matrix. Thus, to apply their results to our setting, one would need to verify the balance condition holds for Gaussian product matrices with sufficiently high probability, and then compute the Stieltjes transform. The computation of the Stieljtes transform is a bottleneck: Gerace et al. focus on settings in which it is known. In our case, the Stieljtes transform of the random feature matrix would be determined by the solution to a non-trivial self-consistent equation of the form (15). Therefore, our replica theory approach in principle offers an alternative route to obtain what should be the same result. We will make sure to cite Gerace et al. in our updated manuscript, and to comment on this point. \n"}, {"review_id": "Fpv3vWshzL", "reviewer": "Reviewer_cGDX", "summary": "The authors introduce correlations to weights of linear RFMs and study the generalization error.\n\nThis is done under the assumption data follows Gaussian distribution and linear model.\n\nThe authors provide a general expression for the limiting generalization error that recovers results from previous works as special cases.", "questions": "Do solutions (15) and (16) always exist? Can you elaborate on their form?\n\nDo you have any intuition how quickly convergence to (13) happen?\n\nDo you have any intuition about the limits when p is fixed?", "limitations": "N/A", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The present results present appear to be very general and well linked to previous research.\n\nThe introduction and preliminaries section are relatively clear.", "weaknesses": "The proofs could be included in the supplementary material which would allow for more text interpreting the results and providing the intuition for their importance.\n\nThe authors should explain the solutions (15) and (16).\n\nThe authors should explain in more detail their result, i.e. (18). \n\nThe authors should be more explicit about the notation, e.g. carefully check the use of /tilde or $\\kappa_0$.\n\nIn my opinion, the clarity of the paper could be improved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful assessment of our work; we hope that our revisions to the Introduction further enhance its clarity. \n\n### Weaknesses:\n*The proofs could be included in the supplementary material which would allow for more text interpreting the results and providing the intuition for their importance.*\n\nThank you for this suggestion. We will defer all proofs to the Appendix, and expand the discussion around each result accordingly. \n\n*The authors should explain the solutions (15) and (16). The authors should explain in more detail their result, i.e. (18).* \n\nThank you for these suggestions regarding the need to elaborate on our finite-ridge results. As mentioned in our common response, we will add more discussion on this point. Also, with regards to the interpretation of (15), we note that we point out in Lines 108-114 of the submitted manuscript that this solution is precisely the self-consistent equation for the limiting spectral moment generating function of the kernel matrix. This object is discussed in detail in previous works on the limiting spectra of product random matrices, e.g. ref. [28] in the submitted manuscript and references therein. \n\n*The authors should be more explicit about the notation, e.g. carefully check the use of /tilde or $\\kappa_{0}$.*\n\nWe will carefully proofread the manuscript to correct any notational issues. \n\n*In my opinion, the clarity of the paper could be improved.*\n\nThank you for these suggestions regarding the clarity and explicitness of our manuscript. We hope the changes mentioned in the global response and elsewhere will help address your concerns; the extra page allowed for the camera-ready version will allow us to better unpack our results.\n\n### Questions:\n\n*Do solutions (15) and (16) always exist? Can you elaborate on their form?*\n\nSolutions to these equations should exist for all covariance matrices with well-behaved limiting spectral densities, but they may not be writable in closed form. In the isotropic case, (16) is easily solvable; see the proof of Corollary 3.2. More generally, it must be solved numerically, as in previous works on ridge regression. Solving (15) is more challenging still; see the work of Penson and Zyczkowski referenced in our common response, and also ref. [28] in the submitted manuscript.\n\n*Do you have any intuition how quickly convergence to (13) happen?*\n\nTo our knowledge, the best error estimates in the case (13) are known in the shallow setting from work by Cheng and Montanari (https://arxiv.org/abs/2210.08571), which shows convergence of generalization error with a multiplicative error that is roughly of order $1/n^{1-\\epsilon}$ for some small positive $\\epsilon$. We would conjecture, but have not attempted to prove, that a similar statement would hold in our setting. \n\n*Do you have any intuition about the limits when p is fixed?*\nThank you for this question. If one considers a limit in which the widths of the hidden layers $n_{1}, \\ldots, n_{L}$ are taken to infinity for a fixed number of training examples $p$, then the generalization error of the deep linear model should tend simply to that of the shallow model. This is shown by the large-width expansion in Corollary 3.5. "}, {"review_id": "UNVVcRgowR", "reviewer": "Reviewer_nhrG", "summary": "The authors investigate the exact asymptotics characterization of deep Gaussian feature models. They analyze depth-L linear Random Feature Models where the feature matrix is built as a product of L factors, each drawn from a matrix Gaussian distribution. Thanks to the replica method, they compute the generalization error learning curves for the ridge regression estimator. They study the influence of the weight structure on the test performance, presenting numerical experiments backing up the theoretical claims.", "questions": "1) The abstract is very concise. I would expand this section to help guide the reader, e.g., mention that you focus on interpolators,  describe what exactly solvable model for anisotropic spectra you considered (power law), briefly explain that the proposed formalism allows as well to cover analysis of Bayesian setting. \n2) On a similar note to the first point, the introduction section is too short. There is little explanation of why RFMs are interesting, e.g., it is not mentioned explicitly their relation with the limiting kernel. The analysis of power-law spectrum decay is standard in the kernel literature and goes under the name of source-capacity conditions [1]. There is no mention of the technique which is going to be used for the computation (the replica trick). Please mention why the interpolating (ridgeless) regime is interesting, with associated reference, e.g. ref [5] in the main text. There is no citation to previous work on the Bayesian settings, the reference [42] mentioned in the conclusion could be introduced as well there. A justification should be given for the Gaussian data assumption, e.g., by referring to the extensive line of work on the Gaussian Universality property, see [2]. \n3) Please before introducing the preliminaries and the setting on page 2, include a summary of your main contributions. \n4) Why is it untractable to study the $\\lambda > 0$ case? A numerical investigation of the behavior at finite regularization I believe would enhance the manuscript, if the problem is not untractable. If this is the case, please mention why in the main text. \n5) The results are nice but I believe some work is needed to glue them together. The authors may think to move in the appendix some proof and substitute them with explanations in plain words to help the reader build intuition, as the notation is quite heavy.\n6) In Sec. 4 remind the reader in which theorem are defined $(\\alpha_{min},\\mu)$. \n7) Can the authors explain in more detail why the exponents $(\\omega_1,\\dots,\\omega_L)$ do not affect the scaling laws if they enter only with the sum (Sec. 5)?\n\n[1] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm, 2007.\n\n[2] Montanari, A. and Saeed, B. N. Universality of empirical risk minimization, 2022. ", "limitations": "The limitations are addressed in the manuscript. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "The authors consider the interesting case of deep RFMs with weight anisotropy. They compute the performance for both ERM and Bayes estimators in the high-dimensional proportional regime. They present numerical simulation and release the code to reproduce the main experiments.  ", "weaknesses": "The primary weakness of this paper is the clarity of the presentation, more precisely I believe more effort should be put into guiding a non-expert reader with a more detailed introduction, and by creating connections between the different main results presented. See below for a more detailed discussion. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the referee’s feedback on the clarity of our submitted manuscript, and will revise our manuscript in accordance with their valuable suggestions. \n\n### Questions:\n1. *The abstract is very concise. I would expand this section to help guide the reader, e.g., mention that you focus on interpolators, describe what exactly solvable model for anisotropic spectra you considered (power law), briefly explain that the proposed formalism allows as well to cover analysis of Bayesian setting. *\n\nAs mentioned in our common response, we will revise the Abstract following your suggestions.\n\n2. *On a similar note to the first point, the introduction section is too short. There is little explanation of why RFMs are interesting, e.g., it is not mentioned explicitly their relation with the limiting kernel. The analysis of power-law spectrum decay is standard in the kernel literature and goes under the name of source-capacity conditions [1]. There is no mention of the technique which is going to be used for the computation (the replica trick). Please mention why the interpolating (ridgeless) regime is interesting, with associated reference, e.g. ref [5] in the main text. There is no citation to previous work on the Bayesian settings, the reference [42] mentioned in the conclusion could be introduced as well there. A justification should be given for the Gaussian data assumption, e.g., by referring to the extensive line of work on the Gaussian Universality property, see [2].*\n \nThank you for these suggestions. As mentioned in our common response, we will expand the Introduction to address each of these points in detail. We particularly appreciate the referee’s reference suggestions, which we unfortunately missed in the submitted manuscript.\n\n3. *Please before introducing the preliminaries and the setting on page 2, include a summary of your main contributions.*\n \nAs mentioned in our common response, we will add a bulleted list of our primary contributions. In short, this list is: \n\n- Using the replica method from statistical mechanics, we compute the asymptotic generalization error of deep linear random feature models with weights drawn from general matrix Gaussian distributions. \n- We show that, in the ridgeless limit, structure in the weights beyond the first layer is detrimental for generalization. \n- Focusing on the approximately solvable special case of power-law spectra in the weights and in the data, we show that the weight spectrum power laws do not affect the scaling laws of generalization. \n- We show how our results can be extended from the ridge regression estimator to the Bayesian Gibbs estimator. For sufficiently large prior variance, structure can be beneficial for generalization with this estimator.\n\n4. *Why is it untractable to study the $\\lambda > 0$ case? A numerical investigation of the behavior at finite regularization I believe would enhance the manuscript, if the problem is not untractable. If this is the case, please mention why in the main text.*\n \nWe wholeheartedly agree that a careful investigation of the $\\lambda > 0$ case would be interesting. Please see our common response regarding this concern. We reiterate from there that to the best of our knowledge a detailed numerical investigation at large depths ($L>2$) would be challenging, based on analogy with work on product random matrices. \n\n5. *The results are nice but I believe some work is needed to glue them together. The authors may think to move in the appendix some proof and substitute them with explanations in plain words to help the reader build intuition, as the notation is quite heavy.*\n\nThank you for this suggestion. We will move the proofs to the appendix, and use the space thusly freed to add expanded discussions of each result. Please see our common response to comments for a detailed plan of revisions.\n\n6. *In Sec. 4 remind the reader in which theorem are defined ($\\alpha_{\\mathrm{min}}, \\mu$).*\n \nThank you, we will fix this. \n\n7. *Can the authors explain in more detail why the exponents $(\\omega_{1}, \\ldots, \\omega_{L})$ do not affect the scaling laws if they enter only with the sum (Sec. 5)?*\n\nThank you for this question. Our reasoning here is that the weight exponents do not affect the scaling when $\\alpha_{0} \\gg 1$, as in equation (32). Here, we are using the convention from Maloney et al. (2022) that the scaling law is determined asymptotically. Therefore, we discard all sub-leading contributions and also neglect the exponent-dependent constant multiplying $\\alpha_{0}^{\\omega_{0}}$. \n"}, {"review_id": "cqzTGX4uNN", "reviewer": "Reviewer_VEZW", "summary": "This work focuses on the generalization performance of models utilizing multi-layered Gaussian random features. The study evaluates the impact of feature anisotropy, which is often overlooked due to common assumptions that features are generated using independent, identically distributed Gaussian weights. The findings demonstrate that correlations within the first layer of features can enhance generalization, but any structure beyond the initial layer proves generally detrimental. These insights provide valuable perspective on how weight structure affects generalization in random feature models with linear activations.\n", "questions": "1. Would figure 2 vary a lot if we modified the number of data points?  In particular, would the theory behaves differently under over-parameterized or under-parameterized regime?\n\n2. The theorems analyze the asymptotic learning curve, where the numerical experiments are conducted under a relatively small number of datapoints. Will this cause a gap between the theory and the experimental results?\n\n3. The constraint on the norm of the teacher vector (line 142) is not very intuitive. Can you briefly explain this?\n\n\n4. Does the result approximately hold for setting without closed form such as Lasso-regression?\n\n", "limitations": "The authors did discuss the limitation and there is no obvious negative societal impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and the theorems are constructed with a solid use of mathematical rigor.\n\n2. The idea is interesting, where how correlation between the rows of the first layer of features can improve generalization is a new theoretical result, which could be very interesting to the community.\n\n3. Visualization and numerical experiments are conducted along with the theoretical results. For instance, the experiments in Figure 2 nicely summarize the theoretical finding, implying the bounds are generally non-vacuous.", "weaknesses": "1. The discussion to previous works are limited. There are many RFM works recently. Although they may focus on a different perspective, such as inductive biases or behavior under SGD, but it would still be valuable to briefly discuss the relationship to these works.\n\n2. At the first glimpse, it is hard to parse how the structure can improve the generalization in some of the theorem or corollary. In particular, there are many constants and it is non-trivial to interpret their numerical property. Adding a simple sentence after the theorem to briefly summarize it could help reader better parse the results.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful assessment of our work, and are gratified by their favorable comments. \n\n### Weaknesses:\n\n1. *The discussion to previous works are limited. There are many RFM works recently. Although they may focus on a different perspective, such as inductive biases or behavior under SGD, but it would still be valuable to briefly discuss the relationship to these works.*\n\nThank you for this suggestion. As mentioned in our common response to referees, we will add a more extensive discussion of related works on RFMs to the Introduction. \n\n2. *At the first glimpse, it is hard to parse how the structure can improve the generalization in some of the theorem or corollary. In particular, there are many constants and it is non-trivial to interpret their numerical property. Adding a simple sentence after the theorem to briefly summarize it could help reader better parse the results.*\n\nThank you for this helpful suggestion. We will defer most proofs to the Appendix, and will add expository sentences to summarize each. \n\n### Questions:\n\n1. *Would figure 2 vary a lot if we modified the number of data points? In particular, would the theory behaves differently under over-parameterized or under-parameterized regime?*\n\nThank you for this question. Figure 2 shows precisely a sweep over the number of datapoints: $1/\\alpha_{0}$ is the ratio of the number of datapoints to the input dimensionality. Therefore, as the abscissa of each of the panels of Figure 2 increases, the number of datapoints increases. These figures, and also the general form of our results, include the transition from over-parameterized to under-parameterized regimes.\n\n2. *The theorems analyze the asymptotic learning curve, where the numerical experiments are conducted under a relatively small number of datapoints. Will this cause a gap between the theory and the experimental results?*\n\nFinite-size experiments should certainly deviate by some amount from the asymptotic approximation. As illustrated by Figure 2, the rate of convergence is sufficiently fast such that the agreement is good even at these sizes. \n\n3. *The constraint on the norm of the teacher vector (line 142) is not very intuitive. Can you briefly explain this?*\n\nThe constraint on the norm of the teacher weight vector is a matter of convenience, and amounts to a choice of units for the label noise and generalization error. The important assumption is that $\\Vert \\tilde{\\mathbf{w}}\\_{\\ast} \\Vert^2 / n\\_{0}$ tends to a constant as $n_{0} \\to \\infty$. If this constant is $C$ rather than 1, the generalization error for isotropic spectra (as in Corollary 3.3) would be the same as that for $C = 1$ if we re-normalize the noise strength as $\\eta^2/C$ and the generalization error as $\\epsilon/C$. Thus, this convention is a matter of convenience. \n\n4. *Does the result approximately hold for setting without closed form such as Lasso-regression?*\n\nThank you for this question. We have not tested other settings, but we certainly agree that extending these results to other convex regularizers would be an interesting topic for future work. \n"}]

Author rebuttal:
We thank the reviewers for their careful assessment of our work. A commonly-expressed concern was that the Abstract and Introduction were too terse to provide adequate guidance and context to the reader, and that the paper would be clearer if we provided more discussion of each result. For our revised manuscript, we will take advantage of the additional space freed up by deferring some of the proofs to the Appendix and the additional content page allowed for the camera-ready version to address these concerns.

In brief, we will make the following changes: 
- We will expand the Abstract to explicitly mention the replica formalism and its applicability to the Bayesian setting, as well as our focus on interpolators and the power-law spectrum model. (Reviewer nhrG)  
- We will add a more detailed description of previous work on random feature models to the Introduction, including the additional references suggested by Reviewers hUXg, nhrG, and VEZW. In particular, we will discuss the relevance of minimum-norm interpolation (i.e., the ridgeless limit $\lambda \downarrow 0$) with RFMs for questions of generalization in overparameterized models more generally, including deep networks. We will also expand our discussion of Gaussian equivalence results to better motivate our setup. 
- We will add a discussion of the replica method and its applications to computing the generalization error of regression models to the Introduction. (Reviewer nhrG)  
- We will convert our summary of contributions into a more readable bulleted list. 
- In Section 3, when we introduce the general form for the generalization error that results from the replica computation (Proposition 3.1), we will expand our discussion of why we focus on the ridgeless limit. See below for a detailed discussion of this point.


We would like to elaborate on a common concern: our focus on ridgeless interpolators with $\lambda \downarrow 0$. Following the suggestions of Reviewer nhrG, we will discuss the relevance of minimum-norm interpolation with RFMs in the Introduction. In brief, recent interest in deep learning has focused on when interpolating regressors display benign overfitting properties, i.e., when they generalize well despite interpolating the training data. Moreover, we will add a discussion of the finite-$\lambda$ setting to Section 3 and to the Discussion. In brief, we agree with the referees (particularly Reviewer bdDi) that it is likely that the optimal generalization could be achieved at some non-zero value of $\lambda$. It is of course well-known from previous works that this holds for shallow ridge regression or a RFM with a single hidden layer is often finite and can even be negative, see for instance Wu and Xu, NeurIPS 2020 or Kobak et al., JMLR 2020. We will add a detailed discussion of this point to the updated manuscript. 

However, how to obtain a clean form for the optimal ridge analytically is in the general-depth case less clear. If one considers differentiating the expression for the generalization error in Proposition 3.1 with respect to the explicit ridge, one would have terms corresponding to the derivatives of each of the inverse moment generating functions with respect to the self-consistently determined variable $\zeta$, and then the implicitly determined derivative of $\zeta$ itself from equation (15). It is not immediately clear to us whether a useful simplification immediately presents itself; we therefore are inclined to leave this question to more detailed investigation in future work. We remark also that the issue of solving (15) is related to a long line of previous work on finding the spectra of product random matrices. Here, even in the case in which all factors are isotropic, exact solutions are known only in the special case in which all factors are square (see Penson and Zyczkowski, Phys. Rev. E 2011). Even numerically, few detailed results are known for depths $L$ greater than 2 or 3. We therefore suggest to leave a detailed numerical investigation of optimal ridge to future work. 

Meta-review: The paper deals with the generalization of deep random feature models in the ridge regression setting. While the contribution is novel and interesting, the reviewers raised some limitations of the work, regarding its readability and its potential impact on the community in light of previous works. While the paper can be improved to be more impactful, its contribution is appreciated.
Decision: Accept (poster)