Dimension-free deterministic equivalents and scaling laws for random feature regression
Authors: Leonardo Defilippis
Bruno Loureiro
Theodor Misiakiewicz
Venue: NeurIPS 2024 spotlight (2024)
Keywords: random features
deterministic equivalents
error rates
random matrix theory
scaling laws
Primary area: learning_theory

Abstract: In this work we investigate the generalization performance of random feature ridge regression (RFRR). Our main contribution is a general deterministic equivalent for the test error of RFRR. Specifically, under a certain concentration property, we show that the test error is well approximated by a closed-form expression that only depends on the feature map eigenvalues. Notably, our approximation guarantee is non-asymptotic, multiplicative, and independent of the feature map dimension---allowing for infinite-dimensional features. We expect this deterministic equivalent to hold broadly beyond our theoretical analysis, and we empirically validate its predictions on various real and synthetic datasets. As an application, we derive sharp excess error rates under standard power-law assumptions of the spectrum and target decay. In particular, we provide a tight result for the smallest number of features achieving optimal minimax error rate.

Dimension-free deterministic equivalents and scaling laws for random feature regression
Leonardo Defilippis
Bruno Loureiro
Département d' I'Informatiuue
Département d' d'Informatique
École Normale Supérieure PSL & CNRS leonardo. def dwwilippissens paw.eeessssss..... psl.eu
École Normale Supéricure PSL & CNRS bruno loureirodens. p eu
Theodor Misiakiewicz
Department of Statistics and Data Science Yale University
theodor theodor.misiakeeee www.miiiiiiiizzyaal.... edu
Abstract
In this work we investigate the generalization performance of random feature ridge regression (RFRR). Our main contribution is a general deterministic equivalent for the error of RFRR. Specifically, under a certain concentration property, we show that the test error is well approximated by closed-form expression that only depends on the feature map eigenvalues. Notably, our approximation guarantee non-asymptotic, multiplicative, and independent of the feature map dimension- allowing for infenitedimeniioonll features. We expect this deterministic equivalent to hold broadly beyond our theoretical analysis, and we empirically validate its predictions on various real and synthetic datasets. As an application, we derive sharp excess error rates under standard power-law assumptions of the spectrum and target decay. particular, we provide a tight result for the smallest number features achieving optimal minimax error rate.
Introduction
At odds with classical statistical intuition, overparametrized neural networks are able to generalize while perfectly interpolating the training data. This observation, which defies the canonical mathemat- ical understanding of generalization based on complexity measures and uniform convergence, appears surprising at first [Zhang et al., 2017]. However, recent progress in our mathematical understanding of generalization has taught us that this benign overfitting property of overparametrrized neural networks is shared by plethora of simpler learning tasks [Bartlett et al., 2021, Belkin, 2021]. Among them, the investigation of the following class of rundom feature models has been the forefront of this progress:
FRF {f(z;a) = Σ (,)(,,,))))))) a= aa(aj)je(n) E RR)
Vp
jElp
Here X' denotes the inputs and W (wy) a set of weight vectors which are taken to be random wy W [d riid pw- Hence, as the name suggests the feature map ip : X' x W + R defines a random function. A few examples of random feature maps include the fully connected neural network features saxx, w) a(w,, x)), R R, and the convolutional features with global average pooling sf w) = 1/a Ee ((w, (ww.ge ge x)) where a - and
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

St x (2e+1) Zd. 21, 2............................... ..)) is the E-shift operator with eyclic boundary conditions (both with X'= = ) -.
Random features [Balcan et al., 2006, Rahimi and Recht, 2007] were originally introduced computationally efficient approximation for the limiting kernel:
(ax, x²) = Emery [sp( u w))((a' w)]
Although this can reduce the computational cost of kernel methods, introduces an approximation error. Rahimi and Recht [2008] showed that in supervised setting with samples, p (()) features are sufficient to achieve an excess risk (nn>))). Rudi and Rosasco [2017] improved this result under standard power-law assumptions on the asymptotic kernel spectrum, showing that for fast decays, less features are needed to achieve the minimax rate. In Section 4 we will revisit this question, where we will derive tight result for the minimum number of features.
More recently, the random feature model has gained in popularity as proxy model for studying the generalization properties of two-layer neural networks in the lazy regime of training [Jacot al., 2018, Chizat et al., 2019]. Indeed, for particular choices of feature maps such as p(æ w) o ((w x)). it can also be seen as a two-layer neural network with fixed first-layer weights. Exact asymptotic results for the generalization error of eq. (1) were derived for different supervised learning tasks under the proportional scaling regime n. p = (d) in [Mei and Montanari, 2022, Gerace et al., 2021, Dhifallah and Lu, 2020, Hu and Lu, 2023, Goldt et al., 2022, Loureiro et al., 2022, Bosch et al., 2023b,a, Schröder al., 2023, 2024] and under more general polynomial scaling n.P ((d*) in [Simon et al., 2023b, Aguirre- played a fundamental role in our current mathematical understanding of the relationship between overparametrization and generalization, demystifying different phenomena such as double descent Belkin et al. [2019] and benign overfitting Bartlett et al. [2020]. It also led to fundamental separation results between lazy and trained networks [Ghorbani al., 2019, 2020, Mei et al., 2022], recently motivating the investigation of corrections to the random limit [Ba et al., 2022, Dandi et al., 2023, Moniri et al., 2024, Cui et al., 2024].
al., 2024, Hu et al., 2024]. As discussed above, these works
With the exception of [Simon et al., 2023b), which based on non-rigorous arguments, the results in all the works cited above are derived in the asymptotic limit of large data dimension. However, the relative scaling of the n, p, is fundamentally artificial, and in practice it hard to unambiguously define the regime of interest. Our main goal in this manuscript is to provide dimension- free characterization of the generalization error allowing us to give tight answers to questions which cannot be addressed asymptotically, More precisely, our main contributions are:
(i) Under a concentration assumption on the feature map eigenfunctions, we prove non-asymptotie deterministic approximation for the RFRR risk Riest Ra,p which is independent of the feature map dimension. More precisely, with high-probability over the input data and random weights:
Russt Rn,pl= S Ö(p 1/2 n -2 1/23) Rn.p-
where the deterministic equivalent Ru.p be computed by solving set of self-consistent equations of the type x = f(x), with f a contractive map. This result unifies the long list of asymptotic formulas in the RFRR literature, and proves conjecture by Simon et al. [2023b]. We numerically validate the results on various real and synthetic datasets. The precise statement of the theorem and the assumptions are discussed in Section 3.
(ii) Leveraging our formula, we investigate the error scaling laws in a setting where the target function and feature spectrum decay as a power-law, also known as source and capacity conditions. We provide full picture of the different scaling regimes and the cross-overs between them, summarized in Figure 2. Our result is closely related to the neural scaling laws literature [Kaplan et al., 2020], and provides the first rigorous, non-linear extension of [Bahri al., 2024, Maloney al., 2022].
(iii We provide sharp expression for the minimum number of features required to achieve the minimax optimal decay rate of Caponnetto and De Vito [2007], closing the gap of previous lower-bounds in the literature [Rudi and Rosasco, 2017].
Further related works - Deterministic equivalents have been derived for wide range of learning problems, such as ridge regression [Dobriban and Wager, 2018 Hastie et al., 2022, Cheng and Montanari, 2022, Wei et al., 2022], kernel regression [Misiakiewicz and Saced, 2024], shallow [Liao

---

and Couillet, 2018, Mei and Montanari, 2022, Chouard, 2022, Bach, 2024, Atanasov et al., 2024] and deep random feature regression [Fan and Wang, 2020, Schröder et al., 2023, 2024, Chouard. 2023] and spiked random features [Wang et al., 2024]. Scaling laws under source and capacity conditions were studied by several authors in the context of kernel ridge regression [Bordelon et al., 2020, Spigler et al., 2020, Cui et al., 2022, Simon et al., 2023a, Li et al., 2023, Misiakiewicz. and Mei, 2022, Favero et al., 2021, Cagnetta al., 2023, Dohmatob et al., 2024] and classification [Cui et al., 2023].
2 Setting
In this work, we focus on the generalization properties of the random feature class FRI defined in eq. (1) in a supervised regression setting. More precisely, consider data D { Vi ke()) composed of n independent and identically distributed samples from a joint distribution Payy on X' x R. Let (=) Elyy a: denote the target function. We assume f L2( where par the marginal distribution over A'. Moreover, we assume the noise = f. (æ) has zero mean and finite variance [[=²] of oc. Note this is equivalent
y: fx,) t
f. E L2(p2).
(4)
Given the training data, we are interested the properties of the minimiser:
ax arg min acRP
Σ AE(m]
yt
f(zx;))) A|lall3 (z (z" z A1,) ZT
(5)
where we have defined the feature matrix Zij =p p(p;; wy) and the label vectors y = (e))) In particular, we are interested in its capacity generalising to unseen data, as quantified by the excess population risk:
R(F.. X, E, == = ( ((= ).
(6)
It will be convenient to decompose the excess risk above in terms of the standard bias and variance:
R(fxiX x, W, A) == Es X W. B(, W
P W,,,
(7)
where:
(f((z) -fe(t)-Eel((z EElf((; ax))) ")
B(f:: W, A) = Egpropes
(8)
V(X, W. A) = Exwp Vare (f(;;; ax))
Note that to simplify the exposition, we have explicitly taken an expectation over the training data noise (En)) Indeed, can be shown that the excess risk eq. (6) concentrates on its expectation over under mild assumptions (see for example Misiakiewicz and Saeed [2024]).
3 Deterministic equivalents
The excess risk eq. (6) is a function of the covariates X and the weights W. and therefore it is random quantity. Our main result in what follows is a sharp characterization the bias and variance in terms of deterministic equivalent depending only the model parameters and spectral properties of the features. Consider a square-integrable E Lz(X' x W), and define the Fredholm integral operator T [2(X)) - V C L2(W):
Th(w)= = / plx; w) ()()))),
vh E L2(X),
(10)
where we define V (T)) This a compact operator, and therefore can be diagonalized:
20
T
(11)
3

---

where (cx)a21 _ R are the eigenvalues and (1b))21 and (0x) are orthonormal bases of (2()) and V respectively:
(Wh, L2(x) = OKR,, (Øk, (he (w) 6RR.-
(12)
Without loss of generality, we assume the eigenvalues are ordered in non-inereasing absolute values [1l | 2 .... and for simplicity of presentation assume that all eigenvalues non-zero, Ie., (T) = {0}. Denote
diag(Ei .2....) E xx the diagonal matrix of the squared eigenvalues. Similarly, since E [2((2)), it admits the following decomposition in (1²)x21
f. f.=E.,.
=EB, 3.
(13)
Our formal results will assume the following concentration property over the eigenfunctions.
Assumption 3.1 (Concentration of the eigenfunctions). Denote the (infnite-dimensioona)) random vectors' 3/ (Ex (2) 1)))211 and Φ := (frōz(w))22) There exists constant C₂ >> 0 such that for any deterministic p.s.d. matrix A E x i.e. a linear operator acting on an infinite- dimensionl Hilbert space, with Tr EA) < oc, we have
16 T Aup TT(EA)
2
E2/2
S C2 exp (-1/Ca):
(14)
IP
O AΦ TEEA
2t
|/ 1
S C2 exp (-t/Ca)
(15)
While Assumption 3.1 is restrictive and will not be satisfied by many non-linear settings, it covers a number of popular theoretical models studied in the literature: 1) independent sub-Gaussian entries, 2) verifying log-Soboley inequality or convex Lipschitz concentration (see Cheng and Montanari [2022]. We expect that Assumption 3.1 can be relaxed using the same procedure as in Misiakiewicz and Saced [2024] to cover classical examples such as data and weights uniformly distributed on the sphere hypercube. Such relaxation is involved and we leave it to future work. We will further assume that:
Assumption 3.2. There exists N such that
PS
(16)
k= 111
Furthermore, we will assume that for some C, > 0 that we have
Tr(E +2) & C., Tr ThE (E+
(B. ( + 12)
S C.. 32 ( 112) -23.)
(17)
Assumption 3.2 is technical, and we believe it can be removed at the cost of more involved analysis. For instance, eq. (16) is always satisfied for < x k we take m = O(p²). Condition (17) was also considered in Cheng and Montanari [2022], and is satisfied in many settings of interest, for example under source and capacity conditions Sg x h-9 and 2 = k- considered in Section
Our main result concerns dimension-free characterization of the risk eq. (6) in terms of deterministic equivalents. We start by defining them.
Main result
Definition 1 (Deterministic equivalents). Given integers n. p, covariance matrix E and regularization parameter À 2 O. Consider the parameter 122 E Rş0 defined as the unique solution of the self- consistent equation:
R
1
n
4
2 (E(E p
( +2)
(18)
p
p
Dv2
and vi E Ry is given by:
2
U2
n
n
V1 =
+
+ 4
(19)
2
Note that we can consider both ab and & random elements of the Hilbert space é with distribution induced by x far and Mue. where E[up>" BB@Φ"
E and Tr(E)

---

We introduce the short-hand:
(2), == p
1 111
2
11
2
Tr > + 122
+
(20)
V/
1/2
p Tr(E 21
x(12)= = Tr(E + 12)
(21)
p- p- (Σ 12))
Then, the deterministic equivalents for the bias, variance and test error are defined as:
1/
B Bn.p 1- (11, U2)
(2+ +.)) D(E 3..)
(22)
((,1,22) 1/2)
(A == o² 1 T(11, 122)
(23)
(3.. :B..))BBrrp(...... + Vn.p(A).
(24)
Our main result provides precise conditions for when the deterministic equivalents defined in defini- tion I are a good approximation for the test error eq. (6), as a function of the dimensions n. p. feature covariance Σ, and regularization À > O. More precisely, the approximation rates will depend on them through the following quantities:
(k) = Σjzk S
Mx(k) = T>([n. k)) V h
log (rx(Ln- kJ) V k),
(25)
c2
k
p- 1l Mx(p),
Px(p) = 1 +
(26)
n no
(x = 1+ 1mm S p/n.l
ml
n
pa(p) Mz(n),
(27)
p
Below we denote Cai.....,, constants that only depend on the values of {as (ai)eels) We use a; '6' to denote the dependency on the constants in Assumptions 3.1 and 3.2.
Theorem 3.3 (Test error of RFRR). Under Assumptions 3.1, 3.2 and for any D, K > 0, there exist constants 17. 1/2) and C..DKK > O such that the following holds. For any n,p 2 C.D.KK. regularization > 0, and target function fx E LL((zx), if
A n K
p1 2/ S KVn. log
(28)
p)(n,p)2 Pr, - logg(p)) - Kvp,
(29)
then with probubility at least 1 - n- pp-- we have [R( X, W,W,, A) - (n,, A)I S C.D,KK . E(n,p) (n A),
(30)
where Rn, A) has been defined in eq. (24) and:
72
pd
30
7+ = pul Σ
06
Sk.
(31)
n
k=m+1
k=
and the approximation rate given by
E(n.p) p) 7/2
px(m.))2 pr+ (p) log 7/2
(32)
Vn
vp
For typical settings, with regularly varying spectrum, (x(P) S log(p) C/ /1 and Prx (n. p) S log(n p)C/kx /k. In this case, the approximation rate scales as E p) = Ö( + +p -1/2), which matches the optimal rates expected from local law fluctuations. A few remarks on this theorem are in order:
(a) Theorem 3.3 provides fully non-asymptotic approximation bounds for the population risk and its deterministic equivalent. They hold pointwise and for a large class of functions. In particular, they do not require probabilistic assumptions over the target function coefficients B as for instance in [Dobriban and Wager, 2018, Richards et al., 2021, Wu and Xu, 2020].
5

---

10a
A-
A
Amp
10
10-1
200 400
600 800
1000
1200
200 400 600 800
1000
Figure 1: Excess risk eq. (6) of RFRR function of the number of features p for fixed number of samples n. Solid lines are obtained from the deterministic equivalent Theorem 3.3, and points are
numerical simulations, with the different curves denoting different regularization strengths À > 0. (Left) Training data (z;; ys ke()) n = 500, sampled from a seacher-sttuden model y; = erf ( (3, xz))
&c. o = 0.1, Ry wiid. N (0, Ia), with a spiked random feature map pa w) = tanh( + wo, a)) where v e Rd has a fixed overlap 7 = (w, (3) with the teacher vector, w ~ (O, I.). u ~ 300, sub-sampled from the FashionMNIST data [Xiao et al., 2017], with feature map given by so(;; w) erf( ((w, and pm: (0, la).
(0, 1). (Right) Training data (æ,, yo [e]]
(b) They are not explicitly dependent on the feature map dimension.
(c) They are multiplicative, and therefore relative to the scale of the risk. In particular, they hold even R n, which will be crucial to the discussion in section 4.
(d) Theorem 3.3 is considerably more general than previous results. First, it extends the dimension free results of Cheng and Montanari [2022] for well-specified ridge regression and Misiakiewicz and Saeed [2024] for KRR (see > oo discussion below) to the case of feature maps : X' x W R, which, discussed in Section 2, comprises several cases of interest in machine learning. Moreover, the deterministic equivalent recovers as particular cases the asymptotic results derived under proportional
n.p (d) [Mei and Montanari, 2022, Loureiro al., 2022, Schröder al., 2023] and polynomial n. (d') [Xiao et al., 2022, Hu et al., 2024, Aguirre-López et al., 2024] scaling.
(e) The bounds depend on X-1 and >=1 1 Following similar arguments as in Cheng and Montanari [2022], Misiakiewicz and Saeed [2024], this assumption could be removed at the cost of lengthier analysis and worse rates +p with C 1/2.
Figure 1 illustrates Theorem 3.3 in two different settings with real and synthetic data. On the left, show the population risk of learning single-index target function with spiked random features model. This model was recently shown to be equivalent to the first-step of training in fully-connected two-layer network [Ba et al., 2022], and was recently studied by several authors [Moniri et al., 2024, Cui et al., 2024, Wang et al., 2024]. On the right, we apply our formulas directly real data set. both cases, the theoretical curves show excellent agreement with the numerical simulations. In Appendix we present additional plots, together with a discussion of how these plots were generated.
Particular limits We now discuss some particular limits of interest of the deterministic equiv- alent eq. (24). First, note that at the interpolation threshold n = p, we have T(2, 122) ~ VX. Therefore, the risk Rn.p ~ 112 diverges as À - 0+,, a well-known behaviour known as the interpolation peak in the random feature literature [Hastie et al., 2022, Mci and Montanari, 2022, Gerace et al., 2021] and observed neural networks [Spigler et al., 2019, Nakkiran et al., 2021].
Another limit of interest is - oo where, in the generic case, the features span an infinie-dimensionall RKHS. Typically, the resulting kernel will be universal, implying can approximate any function in Lg (p()). In this limit, the risk bottleneck is given by the finite amount of data

---

Corollary 3.4 (Kernel limit). In the - 3o limit both Vi and V/2 converge to a single uk which is the unique positive solution to the following celf-consistent equation
Tr(E(> + ux)
(33)
Moreover, the bias eq. (22) and variance eq. (23) terms simplify to:
Tr + vx) (K.n(3.:)) 1 Tr 3 - + ux) (k,n(A) = o² n Tr-TrE> (5 2x)
1 (B... E + xx)
(34)
We denote the corresponding lest error Rk (B., A) Bk (K,, (), (A)
Note that eq. (23) exactly agrees with the dimension-free deterministic equivalents for kernel methods in Cheng and Montanari [2022], Misiakiewicz and Saeed [2024]. Finally, the third limit of interest is the n - 3O where data is abundant. In this case, the empirical risk eq. (5) converge to the population risk. and therefore the bottleneck in the risk is given by the capacity of the random feature class FRE eq. (1) to approximate the target S..
Corollary 3.5 (Approximation limit), In the n + oo limit, we have DI + 0 and D2 + UA satisfying the following simplified self-consistent equation:
= Tr Tr<E(E+ VA)
(35)
Moreover, the bias eq. (22) and variance eq. (23) terms simplify to:
(A.,(3.) = VA (B., vA) 1 B,),,
VA - 0.
(36)
We denote the risk in this case (5.) = (3.) which as expected does not depend X.
4
Scaling laws
Our exact characterization of the excess risk Theorem 3.3 shows that the bottleneck in the model performance stems either from its approximation capacity (as measured by the "width" p) and the availability of data (as measured by the number of samples n). other words, for fixed data budget n, increasing might not improve the error besides certain point, yielding waste of computational resources. This raises an important question: given a fixed data budged ni, what is the optimal choice of model size p.?
Context This is fundamental question in the random feature literature, and was investigated already in the pioneering works of Rahimi and Recht [2007, 2008], who showed that to achieve an excess risk of O(n-1/2) requires at most p = O(n) features. This upper bound was considerably refined by Rudi and Rosasco [2017] under classical power law scaling assumptions, also known as source and capacity conditions in the kernel literature:
T/ < 00,
ΣΣ / < co.
(37)
where E o1) and E o0,, with the case 1/2 corresponding to f. belonging to the RKHS of the asymptotic random feature kernel eq. (2). The optimal minmax rate O 20r-1 for
ridge regression under source and capacity conditions were obtained by Caponnetto and De Vito [2007]. Rudi and Rosasco [2017] showed that this optimal rate can be attained by the random feature hypothesis eq. (1) with > Po = O
11=2" 1120r
features. However, this is only an upper bound, and understanding how tight it is, as well as the full picture in the hard regime E (0, 1/2), remains an open question. In this section, we leverage our tight characterization of the excess risk in Theorem 3.3 to provide a sharp answer to this question.
Results- Without loss of generality, we can assume the covariance is diagonal matrix Σ diag(E)) 1211 and we consider the case where the exponents exactly saturate the source and capacity conditions eq, (37);
k
Ba, k- 1+2ar
(38)
Further, we assume relative scaling of the number of features p and the regularization À with the number of samples n:
p= n=
A A= (6--),
(39)
with g 0 and f 220. 0.
7

---

9
20(r 1)
2,r
9x
1
1 1-6
q
1-1 t +
q+
aq
20er
4
a
8
α
Figure 2: Excess error rate y in the regime n > de 1/(m((-90-7700--0)) as function of (4, g). defined in eq. (40) and eq. (39) for 2 1/2 (Left) and r E [0, 1/)) (Right). The explicit crossover points Ex, fx.9e.0 i are defined in eq. (43) as a function of the source r and capacity a exponents.
Theorem 4.1 (Excess risk rates). Under source and capacity conditions eq. (38) and scaling assump- tions eq. (39), the deterministic equivalent (24) rate is given by: Rn.p(3..1) O (n(nnn(ttg) o = (n-
(40)
where ((, (s(e, (f,(e q) for non-zero noise variance o² + O otherwise (L, Y (f. g). The exponents "I8 and "y are respectively the decay rates of the bias and variance terms eqs. (22) and (23), and are explicitly given by
[[(20 Fn -
1B = 2a AApAl (CAL))
(41)
( (aAAA)).
e
TV =
(42)
Remark 4.1. Under the scaling in eqs. (38) and (39), one can check that the approximation rates E(n, p) in Theorem 3.3 are vanishing for f S a 1/12 if 2 and for q((a 1/16) 1/16(a 1)) if q < 1, which includes the optimal vertical line Theorem 3.3 readily implies that the excess risk eq. (6) indeed has the decay rates described in Theorem I. As discussed in the previous section, we expect that these approximation guarantees can be improved to include larger region decay rates, but leave future work.
l,- Hence, for these regions of scaling,
detailed derivation of the result above from the deterministic equivalent characterization from Theorem 3.3 is discussed in Appendix D. The expressions in eq. (41) are easier to visualise a diagram. Figure 2 shows the excess risk exponent ((,, q) as a function of the parameters l and q, in the case where o² * 0 for r 2 1/2 (left) and r < 1/2 (right). Note that the key difference between the diagrams is the presence of an additional region for 2 1/2.² Defining the following shorthand:
1
4. 2 A 11++ 1)++1
g. = 1- A 1),
q = a +1)+1 = 9. V
(43)
a +
we can identify two main regions in the (L) plane, corresponding trade-off between the bias 7/ and variance "Vy terms:
(a) Variance dominated region (7 < <B): if > l.. > q and X. the excess risk is dominated by the variance term, provided the number of samples is large enough n de -V/rre -v))))))))))(((0)))) Inside this region it is possible to further distinguish between two regimes:
RRecall that these two cases correspond to target function f. belonging (r 2 1/2) or not < 1/2) to the RKHS spanned by the asymptotic kernel
"The noise dominated regime where n < a. -1/(gg(t.w) Ty((-))) and the corresponding cross-over was studied by Cui et al. [2022]. A similar phenomenology hold here, but for simplicity we focus the discussion on the data dominated regime.

---

slow decay regime (orange and brown): for & < a and q < (p < n), n 1 (4a A q), hence the decay depends on the interplay between regularization strength and number of random features and it is slower as (4/a A q) increases;
plateau regime (red): for 8 2 and 1 (p 2 n) the excess risk converges to constant value and does not decay as n. increases.
(b) Bias dominated region (Yy > "BB): if < l. 9 < 9 and p < X, the excess risk is dominated by the bias term, whose decay is faster as (4/a increases (cyan, emerald and teal).
Note that the limit of large number of random features p - oc, we recover the same rates found by Cui et al. [2022] for kernel ridge regression. Of particular interest is the rate for which the excess risk decays the fastest with the number of samples n, and what is the minimum number of random features p, required to achieve this rate.
Corollary 4.2 (Optimal rates). The optimal excess risk rate achieved by the random features hypoth- esis eq. (1) under source and capacity conditions eq. (38) and scaling assumptions eq. (39):
20r(r A 1)
7/x = max 7),
(44)
t.
2a(r 1) +1'
and it is attained
A = X = n ((.--1
for r 2 1/2,
(45)
p P. = - Xa
(A= X.
or S d. p p. (2,²
for < 1/2
(46)
p P. (2.²2)
1/4
corresponding to the bold red line (-) in Fig. 2. In particular, the minimal number of random features p. nn required to achieve the optimal rate 7/x is given by:
(2r A 1)
9. = = 2a(r A 1) +1
(47)
and corresponds to the bold red dot (+) in Fig. 2.
A few comments on Corollary 4.2 are in place. 1) The optimal excess error rate eq. (44) is consistent with the minimax optimal rates for ridge regression from Caponnetto and De Vito [2007], as also discussed by Rudi and Rosasco [2017]. 2) The minimal number of random features p. = n in eq. (47) achieving the optimal rate eq. (44) in the 2 1/2 regime is strictly smaller than the lower bound p > Po of Rudi and Rosasco [2017]. More precisely, letting pa n for P/2,
2(1 - (a - 1) > 0, for all > 1.
Φo 9.
(48)
2ar +
Relationship to scaling laws The empirical observation that the performance of large scale neural networks decreases as power law with respect to the number of samples, parameter and computing time has sparked renewed wave of interest in the theoretical investigation of power laws [Kaplan et al., 2020]. Despite being a mature topic in the statistical learning literature, different recent works have turned to the study of linear models under source and capacity conditions playground to understand the emergence of different bottlenecks in the excess error rates [Bahri et al., 2024, Maloney et al., 2022].
The model studied in these works is given by ridge regression on data y: (B_, with (O, diag(( (()+)())))))) and B_ ~ (0, 1/aI.) with a linear projection model f(x, a) = (a, Wæ). where W is i.i.d. Gaussian matrix. Note this model is particular case of the one studied here, corresponding to a linear feature map and random target function. Moreover, since the variance of the target is constant, the source is entirely determined by the capacity of the asymptotic kernel, here controlled by the decay of the covariance of the input data.
The approximation limit from Corollary 3.5 and the kernel limit from Corollary 3.4 are known in this literature as Variance and Resolution limited regimes, respectively [Bahri et al., 2024]. They correspond precisely to the bottlenecks in the excess risk arising from the limited approximation

---

u-35. u=15//11.
10
t=0.1
Excess fisk
(-t. 0.44
10a4
(-2.5
d=12.
n-
0.6.55
0-08
0,53
n-
10
0
10"
10.
10
10"
107
10
10a
Figure 3: Excess risk eq. (6) of RFRR function of the number of samples under source and capacity conditions eq. (37) and power-law assumptions À = (f-11) n with noise variance of = 0.1. Solid lines are obtained from the deterministic equivalent Theorem 3.3. In the figure on the left, points finite size numerical experiments. Dashed and dotted lines are the analytical rates from Theorem 4. stated in the legend. The colour scheme corresponds to the regions Fig. 2.
capacity of the random feature model or the limited availability of training data. As this model is particular case of ours, the rates in the variance limited regime can also be obtained from Theorem 4.1, and correspond to particular cases Fig. 2, see Appendix E for a detailed discussion. Contemporary to our work, Atanasov et al. [2024] has extended the analysis in this linear model to the case where 3, also has a power-law decay, and provided comprehensive discussion of the different scaling regimes for this model. Their rates can be put in one-to-on to-eee correspondence with the rates derived in section 4. We refer the interested reader to Section VI.6 of Atanasov al. [2024] for detailed discussion of this relationship. We stress, however, that beside being rigorous, our results hold for features in infinit-diimensional Hilbert spaces and are not restricted to a particular asymptotic limit in the dimensions.
Complementary to the sample and model complexity bottlenecks, Kaplan et al. [2020] also observed the emergence of computational scaling laws in the risk as function of flops used in training. A recent line of work has investigated this question on the aforementioned linear random feature model under different training algorithms, such as gradient flow [Bordelon et al.. 2024] and SGD [Paquette al., 2024, Lin et al., 2024]. Due to the simplicity of this setting, the risk of ridge regression with particular choice of regularization À is closely related to the risk of different descent algorithms for least-squares fixed running horizon [Ali al., 2019, 2020, Sonthalia al., 2024]. similar analogy allows to compare our results to the ones obtained in [Paquette et al., 2024, Lin et al., 2024]. particular, our setting cover three of the phases identified by Paquette et al. [2024], and correspond to the result in Theorem 4.1 with X = (e 1). Similarly, the rates of Lin et al. [2024] are obtained by taking À to be the inverse of the learning rate. detailed connection to this line of work is discussed in Appendix E.
5 Conclusion
In this paper, we have investigated the generalization properties of random feature models, deriving non-asymptotic deterministic equivalent for the risk of random feature ridge regression- which recovers (and unifies) previous asymptotic findings as special limits. Our results provide a rigorous multiplicative approximation rate, enabling us analyze error scaling laws under source and capacity conditions, and offers a complete view of the different scaling regimes and their cross-overs. Our anal- ysis relies on Assumption 3.1 which, while popular in theoretical investigations, excludes more realis- tic random feature models, such spxx, w) (xx w) with æ, w Gaussian vectors and non-linear Although restrictive, this assumption allowed to derive tight multiplicative approximation bounds for generic random feature model with siinite-dimessional features whiih which was essential for ob- taining the rigorous excess risk rates that are the primary motivation of our work. We further note that numerical simulations in Figure I and Appendix C suggest that the predictions of Theorem 3.3 remain accurate much beyond Assumption 3.1. We consider lifting this technical condition-e, e.g., s., by follow- ing the approach in Misiakiewicz and Saced [2024] to be an important direction for future research.
10

---

Acknowledgements
We would like to thank Yasaman Bahri, Hugo Cui and Florent Krzakala for stimulating discussions. BL LD acknowledges funding from the Choose France CNRS Al Rising Talents program.
References
Fabián Aguirre-Lópz., Silvio Franz, and Mauro Pastore. Random features and polynomial rules. arXiv preprint arXiv:2402.10166 2024.
Alnur Ali, J Zico Kolter, and Ryan Tibshirani. continuous-time view of early stopping for least squares regression. In The 22nd international conference artificial intelligence and statistics, pages 1370-1378. PMLR, 2019.
Alnur Ali, Edgar Dobriban, and Ryan Tibshirani. The implicit regularization of stochastic gradient flow for least squares. In International conference on machine learning, pages 233-244. PMLR, 2020.
Alexander B. Atanasov, Jacob A. Zavatone-Veth, and Cengiz Pehlevan. Scaling and renormalization in high-dimensional regression. arXiv preprint arXiv:2405.00592, 2024.
Jimmy Ba, Murat Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High- dimensional asymptotics of feature learning: How one gradient step improves the representation. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 37932-37946. Curran Associates, Inc., 2022. URL https: h/ppro/e/////ooeeenngee neurips cc/ cappaper__. aaapprrrflleeeeeeeelrr/arpppppee files/leeppppl tttee//ppprr222//111ee. TTeeraaoraaaf00633322222fff Paper- Comper--eo pdf.
Francis Bach. High-dimensional analysis of double descent for linear regression with random projections. SIAM Journal on Mathematics of Data Science, 6(1): 2024. doi: 10.1137/ 23M1558781. URL https://ddddd org/ 10. 1 22M1158781.
Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jachoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. Proceedings of the National Academy of Sciences, 121(27):22111771221 July 2024. doi: 10.1073/pnas.2. 2311878121. pnas m 2311878121.
URL https: h/wp::://wwwww/// pnas . org htt///oi//bbb/b/ httoo//aaa/...../a 1073/
Maria-Florina Balcan, Avrim Blum, and Santosh Vempala. Kernels as features: On kernels, margins, and low-dimensional mappings. Machine Learning, 65(1):79-944 2006.
Peter I.. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):300633300) 2020. doi: pnas. 190737877
1903378117 URL https::/tt/ett pnas. http://pa...........o///oo aabo///ab//////
Peter L. Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: a statistical viewpoint. Acta Numerica, 30:87-201, 2021. doi: 10.1017/000624222210000007
Mikhail Belkin. Fit without fear: remarkable mathematical phenomena of deep learning through the
prism of interpolation. Acta Numerica, 30:203-248, 2021. doi: 00.10177809624999200000000
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical biai-variance trade-off. Proceedings of the National Academy of August 2019. doi: 10.107//paa..19000700 16. URL https: 1070///3sss 1903070116.
Sciences, 18893)) //www. www..ppaa.....m.mmm
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 https: http:pp://ppoceeeee /ptpc//eecc....... mlr. wttps//v19//oordeee/epopooooooee
html.
Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. dynamical model of neural scaling laws. arXiv preprint 2rXiv:2402.01092,200 2024.

---

David Bosch, Ashkan Panahi, and Babak Hassibi. Precise asymptotic amalysis of deep random feature models. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 4132-4179. PMLR, 12-15 Jul 2023a. URL www.hhtss//ppceeeeeeeee waw.innng..........mm.m.m.mm.mmm .mlr wwwpppresssv...... http//v11///ooa/ bwwph/ss.cccccceeeee///e/aaaaaea html.
David Bosch, Ashkan Panahi, Ayca Ozcelikkale, and Devdatt Dubhashi. Random features model with general convex regularization: A fine grained analysis with precise asymptotic learning curves. In Francisco Ruiz, Jennifer Dy, and Jan- Min-Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 11371 13311-1444, PMLR, 25-27 Apr 2023b. URL mlr. www.spressseeeee v2tp//o0c002..aaaaaaooo html.
Francesco Cagnetta, Alessandro Favero, and Matthieu Wyart. What can be learnt with wide convolu- tional neural networks? 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 3347-3379. PMLR, 23-29 Jul 2023. URL wwtph:tpps/// htttttsss//prrceddingnegoo
mlr, press/ /atass/vv22/oea cag22///ageetaa2aaa... html.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
Chen Cheng and Andrea Montanari. Dimension free ridge regression. arXiv preprint arXiv:2210.08571, 2022.
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable program- ming. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https: / https::s//proocedinggs neurips. apaper_fileee wtt.:ie/e//pppe///////e/11
aeci6655a8811133660666222244 Paper pdf.
Clément Chouard. Quantitative deterministic equivalent of sample covariance matrices with a general dependence structure. arXiv preprint arXiv:2211.13344 2022.
Clément Chouard. Deterministic equivalent of the conjugate kernel matrix associated artificial neural networks. arXiv preprint arXivv2306.058850 2023.
Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kernel regression: the crossover from the noiseless to noisy regime. Journal of Statistical Mechanics: Theory and Experiment, 2022(11):114000)) nov 2022. doi: 110088/1742-5468/c99588 URL attps://dxx doi. org/ 1088/..177 5468/446690
Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Error scaling laws for kernel classification under source and capacity conditions. Machine Learning: Science and Technology, (3):035033, aug 2023. doi: 10. (0088/2632-2153/actt0 URL https: ///xx.xxooo//// www.sddoo..g///eoo 10. 1088/ 2632 200--2113//aa0 acf041.
Hugo Cui, Luca Pesce, Yatin Dandi, Florent Krzakala, Yue Lu, Lenka Zdeborova, and Bruno Loureiro. Asymptotics of feature learning in two-layer networks after one gradient-step. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 4/ International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 9662-9695. PMLR, 21-27 Jul aeress/2335//
2024. URL https: http://pooceeeeeeeeeeee/ee/e mml.innnn.........mmmmmmm.mmmmmm press/ v235/ cui 24d.24d.oo html.
Yatin Dandi, Florent Krzakala, Bruno Loureiro, Luca Pesce, and Ludovic Stephan. How two-layer neural networks learn, one (giant) step at a time. arXiv preprint arXiv:2305. 18270, 2023.
Oussama Dhifallah and Yue M. Lu. A precise performance analysis of learning with random features. arXiv preprint arXiv:2008. 10200008.19900 11904, 2020.
Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-279, 2018. ISSN 00905364, 21688966. URL https: :/ //www/ jstor. arg/sstable2264278..4
12

---

Elvis Dohmatob, Yunzhen Feng, and Julia Kempe. Model collapse demystified: The case of regression. arXiv preprint arXiv:2402.07712, 2024.
Zhou Fan and Zhichao Wang. Spectra of the conjugate kernel and neural tangent kernel for linear- width neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 7710-7721. Curran As- sociates, Inc., 2020. URL pttppe///pooeeeeinggg wew.rediiinnnnnnnnpn..ee.m neurips cc/paper_filese (tapereffiles//pee//2000 file/572201a44555 0000004400000002277000000000 Papee pdf.
Alessandro Favero, Francesco Cagnetta, and Matthieu Wyart. Locality defeats the curse of dimensionality in convolutional teacher-student scenarios. In M. Ranzato, A. Beygelz- imer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neu- ral Information Processing Systems, volume 34, pages 9456-9467. Curran Associates, Inc., 2021. URL https: httpps://proceeddnggs neurips. wttppp...cpppppeeeee secepaper_fiiie files/ fateerffflleppppppeeeeeeeeee httpp/ppppp/////////// Paper.pd..
Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mézard, and Lenka Zdeborová. Generali- sation error in learning with random features and the hidden manifold model. Journal of Statistical
Mechanics: Theory and Experiment, 2021 120113, dec 2021. doi: 10.1088/1742 10.108//742--466ccceee 546///33666/.. ac3ae6.
URL cattpss//dxx doi. hwe.ddddi.oog/////./e 1tt/:/....01////11 10w./1081111411
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Limitations of lazy training of two-layers neural network. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https: http:::://///cceedinneee neurips cc/ Paper.ddf..
paper
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neu- ral networks outperform kernel methods? In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 14820-14830. Curran Associates, Inc., 2020. URL htsphttts:/pppoceediiee hewp:/occeeeiinnneeeee.......pp meurips. cc/ paper_files wttpe//pppppeeee///eepem http:////...///22222222222222220
Paper. .df.
Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Marc Mezard, and Lenka Zdeborova. The gaussian equivalence of generative models for learning with shallow neu- ral networks. In Joan Bruna, Jan Hesthaven, and Lenka Zdeborova, editors, Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, volume 145 of Pro- ceedings of Machine Learning Research, pages 426-471. PMLR, 16-19 Aug 2022. URL https: httpps//prooeeddngs mlr. wtt.saaww........eeee..em wasess/vv4/goolll/
html.
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.1214/21-A0S2112
URL https: /ttp://:ti..o////////// 1214/21-
Hong Hu and Yue M. Lu. Universality laws for high-dimenssional learning with random features. JEEE Transactions on Information Theory, 69(3): 69(3):1932-1194, 2023. doi: TT.1100/1..2222..2..2111
Hong Hu, Yue M. Lu, and Theodor Misiakiewicz. Asymptotics of random feature regression beyond the linear scaling regime. arXiv preprint vrXiv:2403.08//6 2024.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and general- ization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Cur- ran Associates, Inc., 2018. URL https: 2018
neurips. Paper. .
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001_088 008661, 2020.
Yan I Lecun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278- 22224, 1998. doi: 10..19./..72679
13

---

Yicheng Li, haobo Zhang, and Qian Lin. On the asymptotic learning curves of kernel ridge regression under power-law decay. In Oh, Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 11341149364. Cur- ran Associates, Inc., 2023, URL hwwph:ttpt/ttt S hewpseddddnnnnnnnnneeeeeeeeeeeee neurips....... cc/paper..... files/el//ellellll es/ wallspppprr////// htt.a///aaaaaaa.0044440000000010
Pww.raapperrrrreeeeeeeeeeeeeeeee .df.
Zhenyu Liao and Romain Couillet. On the spectrum of random features maps of high dimensional data. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3063-3071. URL http:/:://pcpedd/peeeee mlr press / /v0///80/////// / httle/aallll/ 18a html.
PMLR, 10-15 Jul 2018.
Licong Lin, Jingfeng Wu, Sham M Kakade, Peter I. Bartlett, and Jason D) Lee. Scaling laws in linear regression: Compute, parameters, and data. arXiv preprint wwXiv:2406.08466, 2024.
Bruno Loureiro, Cédric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mézard, and Lenka Zdeborová. Learning curves of generic features maps for realistic datasets with a teacher- student model. Journal of Statistical Mechanics: Theory and Experiment, 2022 14001, nov 2022. doi: (L1188/1742-54665c956655 URL https: www.xx.doi..roooo 1111/////00001110220001001000 ac9825.
Alexander Maloney, Daniel A. Roberts, and James Sully. A solvable model of neural scaling laws. arXiv preprint arXiv:22 16.6599, 2022.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, wtw.:/r0rr//.0.00//aaa.a.. wiley. wtt.cooo//oo/c htt//dii/abbs/ /ta.bb..... 1002/ 22008,
75(4)6667-766, 2022. doi:
URL https: / //n/////llll///l inelibrary.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Generalization error of random fea- ture and kernel methods: Hypercontractivity and kernel matrix concentration. Applied and Computational Harmonic Analysis, 59:3-84, 2022. ISSN 1063-5203. doi: https://doi.org// 100. 10166j.acha.22211122000 URL https:://// htt////w.scieeee www.eceeieeeett.......... www.cooccccccooc http/sccenceeeee /araaccceepplii $1063520321001044, Special Issue on Harmonic Analysis and Machine Learning.
Theodor Misiakiewicz and Song Mei. Learning with convolution and pooling operations in kernel methods. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 29014-29025. Curran As- sociates, Inc., 2022. URL httttts::/ppocceeiiiie neurips . pc/ppapr___. fiw.fllelppppl wwweee/apeeeeeeeeeeeeeaaaaaaeeee /202p/2022/ #110//888e7744000111008283444444 Paper- -aare-oont Conferennceeeeoe pdd.
Theodor Misiakiewiez and Basil Saeed. A non-asympiotic theory of kernel ridge regression: deter- ministic equivalents, test error, and gev estimator, arXiv preprint urXiv:2403.08938, 2024.
Behrad Moniri, Donghwan Lee, Hamed Hassani, and Edgar Dobriban. A theory of non-linear feature learning with one gradient step in two-layer neural networks. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp. editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages ftttps://proceedngg mlr. press v255 moni r html.
PMLR, 21-27 Jul 2024. URL
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, 202) 24003, dec 2021. doi: https://dx. doi. orgoo////// 10. 1088/ 10/e//172-5555500
URL
Elliot Paquette, Courtney Paquette. Lechao Xiao, and Jeffrey Pennington. 4+3 phases of compute- optimal neural scaling laws. arXiv preprint arXiv:2405.1500 2024.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007. URL wtt.tttttt/////oeeeeeeiiiii
http:///pppoeeeeeeeneeeeepepppp. neurips.ce. cc/paper_ wttp://ppprooooo//////aaaacaccee Patpl/555-Pppppppep Paper.pdf. pdf.
14

---

Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: Replacing minimiza- tion with randomization in learning. In D. Koller, D. Schuurmans, Y. Bengio, and Bottou, editors, Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2008. URL https::/pproceeeeeee Oef (ttee///90207150000sceee6oo----0 .df..
Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. Asymptotics of ridge(less) regression under general source condition. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 3889-3897. PMLR, 13-15 Apr 2021. URL attps://proceediin
mlr. www.ppresssveee htt///vv00rrrii hwt3///rcarrs11111 html.
Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random fea- tures. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran As- sociates, Inc., 2017. URL htttps::/ppocceediiiiiii #ll0//0bree882220119999666622222
neurips. httppscccpppoee ww/ppppr.p..../..p httpl/aaaeee//ppaeealpppppaaeeep wtwess/pappeee217/ pdf.
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: httpp::/proceeeeee //tp//eeercee..... mlr. wwwppreeevvviee /ctp//eroooreeereo html.
aalrppess//e
Dominik Schröder, Daniil Dmitriev, Hugo Cui, and Bruno Loureiro. Asymptotics of learning with deep structured (Random) features. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the s1st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 11862-438942 PMLR, 21-27 Jul 2024. URL attps://proceeding mlr. gress/v235/ httsssccoorre22 html.
James B. Simon, Madeline Dickens, Dhruva Karkada, and Michael R. DeWeese. The eigenlearning framework: A conservation law perspective on kernel regression and wide neural networks. arXiv preprint arXiv:2 /0. 03922, 2023a.
James B. Simon, Dhruva Karkada, Nikhil Ghosh, and Mikhail Belkin. More is better in modern machine learning: when infinite overparameterization is optimal and overlitting is obligatory. arXiv preprint ar arXiv22311.14646 2023b.
Rishi Sonthalia, Jackie Lok, and Elizaveta Rebrova. On regularization via early stopping for least squares regression. arXiv preprint arXiv:2406. 04425, 2024.
S Spigler, M Geiger, S d' Ascoll, L Sagun, G Biroli, and M Wyart. A jamming transition from over over-vvranenn peremaaamttiinnoonnn affects generalization in deep learning. Journal of Physics A: Mathematical and Theoretical, 47447):474001, oct 2019. doi: 10. (0.1088/1751-8122aabaa https://dxx.. .wt./ooggg////o/ 10. 1088/ 1751 -1121/1b4211
under-
URL
Stefano Spigler, Mario Geiger, and Matthieu Wyart. Asymptotic learning curves of kernel methods: empirical data versus teacher staudet--tudent paradigm. Journal of Statistical Mechanics: Theory and Experiment, 122001, dec 2020. doi: (00088/1742-5488//6 URL https: //dx: doi. .rg. 10. 1088/1742 54022254488//00 5468/446661//// abc61d.
Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends@ in Machine Learning, 8(1-2):1-230, 2015.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.300) 2010.
Zhichao Wang, Denny Wu, and Zhou Fan. Nonlinear spiked covariance matrices and signal propaga- tion in deep neural networks. arXiv preprint 1011: 2024.
15

---

Alexander Wei, Wei Hu, and Jacob Steinhardt. More than toy: Random matrix models predict how real-world neural representations generalize. In Kamalika Chaudhuri, Stefanie Jegelka. Le Song. Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 23549-23588 PMLR, 17-23 Jul 2022. URL httpp:://proceeeeeeeeeeeee wei22a. html.
mlr, press/ /v1ss/
Denny Wu and Ji Xu. On the optimal weighted 'ell 2 regularization in overparameterized lin- regression. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 10112-10123. Curran As- sociates, Inc., 2020. URL httptttt///oooceeellliie fttp:/22662255..00022222cc002222 .dd.. pdf.
www..ps.cc/papprrrr..... pec/paper_fiiie files/ www.ffieeeseeeeeeee httpsppppppr///////////
Han Xiao, Kashif Rasul, and Roland Vollgraf. mashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07744 2017.
Lechao Xiao, Hong Hu, Theodor Misiakiewicz, Yue Lu, and Jeffrey Pennington. Precise learning curves and higher-order scalings for dot-product kernel regression. In S. Koyejo, S. Mohamed, Agarwal, D. Belgrave, Cho, and Oh, editors, Advances Neu- ral Information Processing Systems, volume 35, pages 4558-4570. Curran Associates, Inc., 2022. URL https: httpss://rroeeednngg nwwrips. wwcpppppr_fiileeeeeeeeeeeeeeeeee wtt.f//sppaaee//22//iii.../ (4220006776000032224666778888888 eonereeeeeeccccceeeeeeeeeeeeeeee pdf.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL htttps://openrevieet net bet/fon /fot//urm? i SyggddxX.
16

---

Appendix
A Background on deterministic equivalents
We consider a feature vector f E RR, q E Nu with covariance matrix Σ = =E[ff'] We denote di 2 1/ 2 2 the cigenvalues of Σ in non non-increasing order. In the case of infinit-dimensionall features = oo, we will further assume that Tr(E) < oo, ie., we consider to be a trace-class self-adjoint operator.
We assume that the feature f satisfies the following assumption. Assumption A.1 (Feature concentration). There exist C,, C, > such that for any p.s.d. matrix A g2xa with Tr (rAAA)= < oo, we have
P P Af - Tr(AA) 2t E AE 1/2 (F) C. cxptt)
(49)
Recall that we denote Ca.....az constants that only depend on the values of {asbsetk). We use = 's" denote the dependency on the constants C.; C. from Assumption A.
We will further define the following two quantities.
Definition 2 (Effective regularization). For integer covariance E, and regularization X 2 0. we define the effective regularization X, associated to model (n, Σ, X) to the unique non-negative
solution to the equation
n -+(E(++))))
(50)
Throughout this appendix, assume that O. The existence and uniqueness follow from noticing that the left-hand side monotonically increasing in A while the right-hand side is monotonically decreasing. We consider the change of variable phx (A A/dr, such that μ., is the unique non-negative solution
H1. + T 2)-1)*
(51)
Both μr, and X are increasing functions with A.
Definition 3 (Intrinsic dimension). For a covariance matrix Rax4 with eigenvalues in nonin- creasing order o 2 22 2 33 ...,, we define the intrinsic dimension rz(k) at level k E N of E to be the intrinsic dimension of the covariance matrix Σz diag(1k 72 .......) i.e. the covariance matrix projected orthogonally to the top h eigenspaces, which is given by
(k) = Tr Exx) Σ 23
7
The intrinsic dimension of Σ> captures the number of dimensions of Σg that have significant spectral content, i.e., 73 Ez lp (see [Tropp al., 2015, Chapter for further background).
We are given n i.i.d. features (ff ffeeei and we denote F [f....., f,,'" IT R=*0 the feature matrix. The train and test errors are functionals of the feature matrix F. In particular, they depend on the following resolvent matrix
R + In this section we consider functionals that depend on products of F, R and deterministic matrices.
For general p.s.d. matrix A E R9x9, define the functionals
Φ (F; A, = Tr AΣ 1/2 ( + -) -11
FFF
D2(F:A) : Tr
F - ( (
n
(F (LFFAA,) A, := Ir
1/ X) =F
F FTF
F
(F
(,(F;A,A):=11
17

---

These functionals are well approximated by quantities proportional to
V (i(A. A) Tr (AΣ( 1)
V2(A.) = 1 Tr TT<EEE + X.) 1)
1 TrA > + X.))
(a(A:: n n Tr Tr(E(()) x.)
Without loss of generality, we can assume that Tr( < for $ otherwise 0; A. X) 1 (1:; A, A) = xo almost surely, and Tr( Tr(AE²) < 0o for $3 and 1 as otherwise (F; (ye; A, X) = oo, j = 3, 4, almost surely.
Our relative approximation bound will depend on the covariance matrix E through
(x
n1)) V n log (re(In- - n.) V vn]].
pa(n) = Me
1+
(52)
where 77. 1/2) is constant that will only depend on c. C, and we used the convention that 2 [n = 0 if [%/ n]
The following theorem gathers the approximation guarantees for the different functionals stated above, and is obtained by modifying [Misiakiewicz and Saeed, 2024, Theorem 4].
Theorem A.2 (Dimension-free deterministic equivalents). Assume the features (f (fe)) satisfy Assumption A.I with some constants Czi Czy 3 >> O. For any D, K > 0, there exist constants 1 The (0, 1/2) (only depending Cxt Cz. 8). CD.K 0 (onty depending K, D), and CzDD >> (only depending on Cz₁ Cz. n., D, K), such that the following holds. For all n 2 CD.K
and X > 0, if it holds that
X (x)x(n) 2 1 n
px(n) log S SKVR,
(53)
then for any p.s.d. matrix A, we have with probability at least n-D that
1 (F; d (A+: C..D.K P2(n)5/2 log" (2)
A (i.iiA))
(54)
Vn (2( V2(A.)] S C.DD (2 5/2 log
3/2 (n) (2(A,):
(55)
Vn Va(u A\y Ca,D.K px(n) log 8/gg/((n)
(nd+
/nd
(F;;;; A,A)
Va(uu; A, A),
VTi
(56)
(F(F; Va(A.; A)) s Ca Px
1/2 3/2 (n)
(12 Vz(A,;A), A).
(57)
Vn
Proof of Theorem A.2. The only difference between this theorem and [Misiakiewicz and Saeed, 2024, Theorem 4] comes from the definition of px (x)... This new definition is obtained by slightly modifying the proof bounding the operator norm of Σ 1/2 R/1/2 from [Cheng and Montanari, 2022, Lemma 7.2] and [Misiakiewicz and Saeed, 2024, Lemma 1]. In particular, we will simply modify step in the proof
of [Misiakiewicz and Saeed, 2024, Lemma 1]. Consider F+ [f [f....... f+,n _ (=
where f+, correspond to the projection orthogonal the top k. [n-n] eigenspaces with covariance matrix
Σ = -E E + = diag( 2............ 70)
Then, denoting S [ S, with S; f.iLT we have with probability at least 1 - n for any E [nx].
|S I Tr(E+) CT.D (og(n))/ RR. Tr(E+) & Tr(E.) (1+C.D
log(n)
=: Ln-
Vrz(ki))
18

---

Denoting S = EiE(n] S; with S; == S. Sill so that S = S with probability at least
1 n D. we obtain
S I nLn =: Un
|B| op n n =..
Therefore, applying the matrix Bernstein's 's inequality with intrinsic dimension [Tropp al., 2015, Theorem 7.3.1J to gives that with probability at least 1 1-
|S S nnk + CDD (Vrn + (m) (log(r=(k.)))
S nnk.
+ CDIn log((r<(:.))))
{
{ 1 rko))
1 + C..D log(n)
(ps(r=((ia)))) }
S nikk
vrx(kk)
Note that by the condition of our theorem. log(n) S K KVT,, and therefore
{ I+ (k,)
2 || I C..DDKK mik
n2 1
log(rss (kx)))
rx(k))
1+ (x(k)) V log(rs(k.) V m)
$ C..,D .nk.
Following the rest of the argument [Misiakiewicz and Saeed, 2024, Lemma 1] we obtain pa (n) in Eq. (52).
B Proof of the deterministic equivalent for RFRR
In this appendix, we prove the approximation guarantees stated in Theorem 3.3 between the test erro of RFRR and its deterministic equivalent. We start in Section B.1 by introducing background and notations that we will use throughout the proof. Section B.2 introduces key results on the covariance matrix and the fixed points. We then leverage these results prove deterministic equivalents for different functionals
Z = (a (ar,, ()))))s(())))) E R conditional on (Wy))E(p) in Section B.3, and functionals of F = (E (w))))E(p)A22 E IRxx in Section B.4. Given these deterministic equivalents, we prove our approximation guarantees for the variance term in Section B.5, and for the bias term in B.6. Finally, we deffer the proof of some technical results to Section B.7.
B.1 Preliminaries
Recall that throughout the paper, will keep track of the parameters of the problem (n, p, E, X, o.). For the other constants C,, K, D, we will denote Ca..ag....o of {a, hx(())- We a; '*' to denote the dependency the constant C, appearing in Assumption 3.1 and Assumption 3.2.
oz constants that only depend on the values
Throughout this appendix, we will directly work in the 'feature space'
g: = (vh (v:(( (m;)))<21
and
f; (Eud))(w;))
with distribution induced by æ, ~ Per and my ~ pmn- We will denote the covariate feature and weight feature matrices by
G G= gg....... In1 E R
F== -=.... .pl E 8x000
We denote the random feature weight vector
2; = jo((w) (( xx))]
Fg. RP,
vp
and the associated feature matrix
Z = [2],,,.... 2n
GFT E aaap.
vP
Note that f has covariance matrix
: E==Efff diag (E. 27.62.5 E
19

---

We will further introduce the covariance matrix of x conditional on the weight feature matrix F (i.e., conditional on (wy)se(m)
I -FFF E ERAXP
=p:=Ea 22 F
(58)
Note that under Assumption 3.1, the features z and f satisly the following assumption. Assumption B.1 (Concentration of the features z and f). There exists a constant C. > such that for any weight feature matrix F E TRpxx and deterministic p.s.d. matrix A E RRxx with Ar < co, we have
F2/F 2 A Tr(EFA] A)
1/21 11) 11 12 AΣF
< exp
(59)
for any deterministic p.s.d. matrix B 2o with Tr(BB) <c.
Py ( Bf tt | (1) - C. exp (-t/Ca).
(60)
We will assume in the rest of this appendix that Assumption B.1 holds. Using the notations introduced above, we restate our setting below. Recall that we consider learning target function ht (g) g B, from i.dd samples (y: 9: (e) with
y/1 g. B. E
where 8 are independent noise with Eee.] 0 and Elee] of. Denote y (. Un) the vector containing the labels. We this data using a random feature model with i.i.d. random weight features (f Jelel
f(0)
g F
1 vp"
E RR.
(61)
We fit the parameter a using random feature ridge regression (RFRR)
á^ = arg min {1y - Zall2 + 2|[a|13] = (Z 2 + A) Z
(62)
aERP
The test error is then given by
Reest (he: G,F,A):== Ee Eg ( - /p
F FTax)
(63)
BBG F,) V(G,F,))
where the bias and variance terms are given explicitly by
B(G,: G, F, 113, 1-2 T Z Z + V(G, F,A) =
G3.11.
(64)
Tr T 2 ( -
(65)
Note that both the bias and variance terms are random quantities that depend on the random matrices F. F. The goal of this appendix is to prove non-asymptotic and multiplicative approximation guarantees between these two terms and deterministic quantities that only depend on the parameters of the model (n. p. Σ, B., X, o?), i.e., we will show that with high probability
I, A) - BR, (B., A)I = Ō (2 1211122 p -/2) (B.p(B.,)) 1/2
((G,F,A) Vn,p Ō 00n (n-1/2 + 1/2) V (n.,(A),,
where B (B,, A) and (A) are defined in Eqs (22) and (23), and the approximation rates Ö(-)
are explicit in terms of the model parameters.
The proof of these approximation guarantees will proceed in two steps. We first show that the bias and variance terms conditional on F are well approximated by functionals that only depend on F, i.e.
B(B.G.,F. -B Ō 1/2) B(B.F.A)).
(66)
= o n ( Vv(FA)) A)
20

---

We then show that B(B,; F. and V(F, A) are well approximated by (n.,( A) and Vn Vn,((A)
with
BiB,; F) - Bn 21 = Ō ( 11-)/2))))))))( (3,, X),
(67)
((F,A) - Vnn((A) = δ (p-1/2) Vn.p(A).
For each of these two steps, we will apply general results showing deterministic equivalents for functionals of (possibly infiite-dimensional) random matrices proved in Misiakiewicz, and Saeed [2024] (see Appendix and in particular Theorem A.2 for some background). Note that when writing the proof, we will directly show Eq. (66) assuming that F is in some good event F E AAy, where (A(A=) 2 1 D so that we can immediately write functionals with regularization parameter that does not depend on Er, and therefore the rate will be directly Ô (n- 1/2 + +p 1//)) However, we can reorganize the proof to indeed get the separate contributions (66) and (67) to the approximation сπrо rate.
The rest of Appendix B is devoted to implementing this proof strategy. We start in the next three sections by introducing key technical results which we will use in the analysis of the bias and variance terms.
B.2
Fixed points, feature covariance matrix, and tail rank
Recall that our deterministic equivalents will depend on the fixed points (21)2)) ) R3 stated in Definition 1. Furthermore, our approximation guarantees will depend on the covariance matrix E through Px (p) and pw (n,p)) which we restate below for convenience
My(k) 14 r=([n. kJ) V k
log (r>(In+ kl) V Vk),
(68)
k
p. pl My((),
C2
Px(p) =1+
(69)
n
ix (n. = 1 1 In S p/v=
19. ml
po(D) Mz(m),
(70)
K
p
where 7)- E (0, 1/4) is a constant that only depends on C, appearing in Assumption B.I, and (x))) the intrinsic dimension of at level (see Definition 3)
E) 5 4
r=(k)
Observe that Pr. (n. p) is well defined for n - 00 while p stays constant with pr. (oc, p) and for + do while stays constant with (n, oo) (n(n) (under the conditions in our setting that (p) < vp for some constant K).
In this section, we introduce and prove properties on the fixed point (V1, (2), 123 and the weight feature matrix F which we will use to prove deterministic equivalents.
Feature covariance matrix. The features z; E IRP conditional on F are i.i.d. random vectors with covariance Σr FF /p. We first show that with high probability over F, this feature covariance matrix has eigenvalues and intrinsic dimensions bounded by the ones Σ.
Denote & (
the p eigenvalues of ΣF in nonincreasing order. Applying the definition of the intrinsic dimension at level k to Er, , we have for any I,...,P.
TS (k)
j=
(71)
Applying Theorem A.2 directly to functionals of Z conditional on F, the approximation guarantees depend on
22 n
r (1 - n2.) V
(x(n) 1+
(
1
log (TS, (1% nl) vn)
(72)
A
n
21

---

which simply corresponds to Px defined in Eq. (52) applied to Σp where we recall that e [ = 0 if [n, n] p. The next lemma shows that with high probability over F, have pa (n) & PA (A for all n E N.
Lemma B.2 (Feature covariance matrix), Assume the feature vectors {f, Hjeeel satisfy Assumption B. Then for any D, K > there exist constants v/+ (0, (041 and C.D,KK > such that the following holds. For any 2 C.,D.K. the event
A FERPXO
1 1E 2 2' Ōx(n) S S...D.K Tx(n,)), VEEN, (73)
holds with probability at least p-P
We defer the proof of this lemma to Section B.7.1.
High-degree part of the feature matrix F. Recall that (11, B2 the solutions to the fixed point equations stated Definition In order to get approximation guarantees when pV1 - oc, will analyze separately the top eigenspaces of F from the rest. For integer N, we split the feature vector f, = fo. (o.ff+. with covariance
JJ] where fou E TR. corresponds to the top m coordinates
Σg = BI==B[oo. B.f.ojooooo..... = diag(Eř, e...... <m),
and f E R corresponds to the high degree features orthogonal to the top m eigenspaces. We denote their covariance
Σ Ef= + diag(Sm+1 2 2m......)
We split the weight feature matrix intro F Fo. F F+1, where
Fp = [f,11- So.pl" E Rpxm
F [f+11
S S+ppl e Rex
We will use that for m chosen such that Em+1 << Tr(E.), we have with high probability
| [. Tr(E+) Ipllop & vp. Em+ Tr(E+) < Tr(E+),
and therefore
FF + FoF (n)),
where we defined the function
7(k) = x
To simplify the final statement of our results, we assume that can choose such that p² 3 S (pp/nn). Note that 1 2 A/n from the fixed point equations and (pA/n) I (pv)) (e.g., see Equation (76)). For convenience, will further denote
7+ 7= (prn)
:= (p)/n).
(74)
Lemma B.3 (Concentration of high-degree part of F). Assume that (ʃ (. satisfy Assumption B. I and N chosen such that p² S (p2//n) Then for any O, there exists a constant
C.DD > such that with probability at least 1 1-p" p-pD
log (p)
(p)
log (p) vP
F F+F - -TrE4) Ipllop I C.,D
TA S C.,
7+.
vp
This lemma follows directly from [Misiakiewicz and Saeed, 2024, Proposition 9].
Effective regularization and fixed points. Conditional on F, the bias and variance functionals of the random matrix Z which has i.i.d. rows with regularization parameter and covariance Σr. The deterministic approximations to these functionals depend on an "effective regularization" D associated to (n, Σr, A) (see Definition 2 in Appendix A for background) which is given as the unique non-tegative solution to the equation
A
-Tr 11))-1)
n
=
i7
22

---

Note that the right-hand side can be rewritten as
TFF(FF((FF' - Tr =
+ph))
(75)
which is itself of functional of the random matrix F which has p i..d. rows with regularization parameter pid and covariance Σ. Note that in1 is a random variable depending itself on F. However will show that it concentrates a deterministic value V1. We therefore introduce second effective regularization V/2 associated to (p, Σ. pu)) given as the unique non-negatice solution of the equation
pvi Tr 12) P2
The functional (75) is then well approximated by
T((FF((FF)
pD)) (1 +pr((() (o..r(1))TT(300 + +1)
This motivates to define (11,22) R3.0 as the unique non-negative solutions the coupled fixed point equations
n Tr (1(
V1
(76)
pvd Tr (E + +2
1/2
Writing #1 as a function of 12 indeed produces the equations stated in Definition 1.
To show that in concentrates on V1, we define the following fixed points (T (2) E R3 to be the unique positive solutions to the random equations
A =
(77)
p Tr (E((EE(+
pDl D2
The following proposition shows that (01, 02) is well approximated by (V1, v2) with high probability.
Proposition B.4 (Concentration of the fixed points), Assume that (f j)se() satisfy Assumption B.I. Then for any D. K O. there exist constants n7, E (0, 1/4) and C.,D.K holds. Let Pie (p) and Pio (n, p) be defined as per Eqs. (26) and (25), and 7x and 7+ as per Eq. (74). For any p C.DD and X > if holds that
such that the following
7A A2P=
K
(x(np))PPxi (p) log lo) S K //D
(78)
then with probability at least 1 - pp" pDD,
D. we have
102 V2
< C.DD.K Ex( 11 v1
max
112
V1
where defined
Ep) = (x(1.p) P.+ (p) log (p)
Vp
The proof of this proposition can be found in Section B.7.2.
To study functionals of Z conditional on F, we will assume that F belonds to the good event
AF = Ax {F Rox00 : - vıl < C.D.K (p) v1).
(79)
where Äy is defined in Lemma B.2, In particular, as long p C.D.KK and condition (78) hold, then IP(AF) 2 1 2p- by Lemma B.2 and Proposition B.4.
23

---

Truncated fixed point. As mentioned above, we will separate the analysis of the low-degree part of the feature matrix Fo o and the high-degree part F+. For the high-degree part, we will simply use the concentration stated in Lemma B.3. For the low degree part, we will study functional of Fo
with regularization 7+ pu + +T We therefore introduce an effective regularization V2,0 associated to the model (p. Co. )+), i.e., the unique positive solution to the equation
p 7+
Tr(Eo Zo + v2,0) 12,0)=")
(80)
V20
Intuitively, V2, will be closed to as soon as Amaa [+) & V2 as
p
Tr Eol Eo + v2) 1) + Tr(E+)
1/2
1/2
and uniqueness the positive solution 22,0- This is formalized in the following lemma.
Lemma B.5 (Truncated fixed point). Let m be chosen such that p² p²mm+1 S Y/a, then
|2.00 1/2
(81)
Furthermore, there exists an absolute constant C' > such that
Tr(Eo (En + 12) + Tr(E-) Tr (I(EEE+)))T
C -
(T())+)))~)))
(82)
V2,0
Proof of Lemma B.5. The first bound (81) follows directly from [Misiakiewicz and Saeed, 2024, Lemma 6]. For the second inequality, we decompose this difference into
Ir Ir(Eo (2o + 12)0))+)++ + Tr(E+) Tr + 12)
12,0
112,0 - U2| Tr(Eo(En (2200 + 12) 12) + 22
112.0 Val Tr(E+ + 12)
12.0
c2 Sm+1
112,0 - 1/2
(T<E(E+
1/20
V20
TT(E + u2)
12)
where we used that f S (p2 S 1/p by the assumption on and identity (80).
B.3 Deterministic equivalents for functionals of conditional on F
As mentioned in Section B.I, we will first show that the test error concentrates over Z conditional on F on some quantity that only depends on Σr. The bias and variance terms can be written in terms of the following three functionals of the feature matrix Z: for general p.s.d. matrix A RPxx and positive scalar
0, define
Z (Z ( (+)
22(Z:n) Tr
n
23 A, x) == Tr
AΣF (Z Z + 1))
1/2
'SP
(83)
(Z;
A 1/2 A
z
Z z 2 x)) -1 1/2
n
where we recall that Z has i.i.d. rows with covariance Ep = FFT /p. We show that these functional are well approximated by functionals of F that can be written in terms of the following functionals:
F F OF -FFFE++)-1)
(=) =r
(84)
5.(F;A, k) = n oo n
T A, k) = Tr (A(FFT) (T) + 2
24

---

The following proposition gather the approximation guarantees for 22 P3. P2 listed in Eq. (83).
Proposition B.6 (Deterministic equivalents for $ (()) conditional on F). Under Assumption B.I and assuming that F E Ay deftned in Eq. (79), for any D. O. there exist constants n, (0, 1/4), CD. > O, and C.DDKK > O such that the followings holds. Let p px(p)) and Pe((n,1)) p) be defined as per Eqs. (26) and (25). For any n 2 CD. and regularization parameter > 0, if it holds that
x
Tx(n, // log 3/2 (n) S K Kvn,
(85)
(n. Pa~ (p) (p) S KVP.
then for any p.s.d. matrix A E RPxP (independent of F) with probability at least 1 nD on Z conditional on F, we have
$2
P 2 2 F pwn)
C.D.KK ((1 (2
(86)
n
nP1 2
(VV 2 $F A, pvi),
D3 (Z; A,
$ (F; A, pui)
s SC..k Ei(
(87)
(Z; - A, pvi)
S SC..D.K E((p.)-E((np))))))) (F; A, pv1):
(88)
where the approximation rate is given by
E, p) = px p) log
(n) + (x(n,1)) PT+ (p)5/2 log"()) /p
(89)
Vn
Proposition B.6 is consequence of [Misiakiewicz and Saeed, 2024, Theorem 4] (see Appendix A and Theorem A.2 for background) and Proposition B.4. We defer its proof to Section B.7.3. Note that the term 0pp11/2) in the approximation rate & (n. p) defined in Eq. (89) comes from comparing pel with pig and is equal to (x (n, where (n: p) is defined in Proposition B.4. If instead, we compared to functionals with regularization pūj, then the approximation rate in Proposition B.6 would scale (n121/2) expected.
In the analysis of the bias term, we will further need to show deterministic equivalents in the case where A is itself random matrix uncorrelated (but not independent) to F. The following proposition gather these approximation guarantees and is a consequence of [Misiakiewicz and Saeed, 2024, Lemma 10] and Proposition B.4.
Proposition B.7 (Deterministic equivalents for (Z), uncorrelated numerator). Assume the same setting as Proposition B.6 and the same conditions (85). Consider deterministic vector R" and a random vector u = (u:) [e)) with i.i.d, entries and Elu,] = O, B[u]] = 1, and E[ F) = 0.
Then with probability at least 1 n- D on Z conditional on F, we have
(u, z( Z + x) E xr 2 Z + 1) z'u) u) - (F; S C...D -..DDK-E22. E2(,,),
(90)
(n, Z Z + 2) Σr E (T z + 2) 2)- S S...D.K (2
ny v Vāg(F: OF. (pe)), (91)
A
where we denoted = -5P' 1/2
v and the approximation rate is given by
Ez(n, p) = p5 (n. p) log 7/2 (2) px(n,p) ()2 p++ 6/2 log (p)
(92)
Vn
VP
We defer the proof of Proposition B.7 to Section B.7.3.
B.4 Deterministic equivalents for functionals of F
After replacing the bias and variance terms by their deterministic equivalents over the randomness in Z F. we obtain functionals in terms of & (2(Fppr)) and (F; pP1) listed in Eq. (84). As mentioned in Section B.2, we will analyze the low-degree and high degree part of the feature matrix separately. Using Lemma B.3, we can replace the high-degree part F, F. FT by a deterministic matrix, which results in regularization parameter (pv1) pV1 + Tr
25

---

The functionals of Fo can be written in terms of the following quantities: for any deterministic matrix B mm define
1 (Fo =
(F
F Fu (F) (F +x())))
(Fonk) Ir
(93)
(Foo BKk) Tr
BooD 1/2 (F Fo +x())) EF (
(k)) (x)))
F Fo p
1 Fo: 0: B K)
BE /2 (F) Fu 7k))
(FF + (())))
We show that these functionals can be well approximated by the deterministic fuunctions that can be written in terms of
v (v; = Tr
(BE Eo +1)
(2((1) Tr [Eo] Eg + D) )
p
(94)
Tr BE Eg 22
M3(v; =
p Tr Eo -))
Recall that for K pM1, denote 7+ 7(m4) and V2.0 the effective regularization associ- ated to model (p, Eo. 74). The following proposition gather the approximation guarantees for 11, 22 23 D, listed in Eq. (93).
Proposition B.8 (Deterministic equivalents for Fu). Under Assumption B.1. for any D.K K 0, there exist constants E (0, 1/4), CD.K >> O, and C..D.K >> O such that the followings holds. Let Pi (p) be defined as per Eq. (26). For any p 2 CD,K and
if holds that
72p
3/2 (p) S KVD. Pr+ (p) 5/2 2/2
(95)
then for any deterministic p.s.d. matrix B mmxm with probability at least pp,, have
i (Fo; B, pv1)
V2,0 v
(V2.0; B)
< SC.DD Es(p) V2.0 v (u2.05 B),
(96)
7+
7+ < SC..D Es(p) V2(22,))
(Foipul) (2(
(97)
p1/2.0 V3(1200 B)
(2/200
D3 Fo: B, B.1v))
SCD.K Es(p)
(3 B),
(98)
7+
7+
(FFFF; B,
V3(22,0 B)
SC.,D, Eg(p) Va(U2,0; B),
(99)
where the approximation rate is given by
Ex(p) Pr+ (p) logo(p) (p)
(100)
This proposition is obtained by directly applying Theorem A.2 with no modifications.
Again, in the analysis of the bias term, because separated the analysis of the low-degree and high- degree parts Fo and F+, we will further need deterministic equivalents when B is itself a random matrix uncorrelated but not independent to F. We gather the associated deterministic equivalents in the following proposition.
Proposition B.9 (Deterministic equivalents for Fo, uncorrelated numerator). Assume the same setting as Proposition B.8 and the same conditions (95). Consider a deterministic vector v E IRm and random vector (u,)}ε(H) with i...d. entries and E[u,] 0, E|u3]] 1, and EB o. uy] 0.
26

---

Then with probability at least 1 p-, we have
1
iu (FoFo + (pv2,0)² 1 - ( Eo + 12,0
S SC.. E1(D)
7
(101)
puzo [ (u, (u, Fo + Foo) S...D.K Es(p) = 7
v V=
(102)
where we denoted f. == -- Eo and the approximation rate is given by
Ex(p) Pr+ (1) log" (0gg)((p)
(103)
vP
This proposition is a direct consequence of [Misiakiewicz and Saced, 2024, Lemma 10].
Throughout the proofs, with a slight abuse of notations, we will denote functionals $; x), [4]. the functionals listed in Eq. (93) applied to the truncated feature matrix Fo. with covariance Eg. regularization (xx), and deterministic matrix E m_ and 2 (F; B, x).. i E [4], the functionals applied to the full feature matrix F E 1 where Eo is replaced by E, the regularization parameter k, and the deterministic matrix B E R Similarly, we will us the notation Vi (V2,0 B), E [3] for the truncated deterministic funetionals (94), and the notation V (1y B), [3] to denote the full functionals with Σg replaced by Σ and B E XXxx
B.5 Approximation guarantee for the variance term
Recall the expressions for the variance term
V(G, F, A) = oz 2((50"Z((222+)1""
and its associated deterministic equivalent
T(,, 122)
(A) = -² 1 - (1),
(104)
T(1, = p n
(1-"0 V1
11 ThEE' + +2) -2) p Tr Tr [ -2)
+
(105)
We prove in this section an approximation guarantee between VIG, F, X) and V Vn (A). For conve- nience, we state separate theorem for this term.
Theorem B.10 (Deterministic equivalent for the variance term). Assume the features (2i)ie(m) and (fg)) satisfy Assumption B. and the covariance Σ and largel coefficients B, satisfy Assumplion
3.2. Then, for any D. K > 0, there exist constants T)+ (0, 1/2) and C..D.K > 0 such that the following holds. Let Pw. and Pu. be defined as per Eqs. (26) and (25). For any n, Z C..D.K and
A 0, if it holds that
A A K
pA(n,))5/2 log log 2 < KVT. px(n,))² Pr+ (p)7 log S K KVD
(106)
then with probability least 1 - n - have
[VG, Vnn((A) C. (v Vn,((A),
where the approximation rate is given by
(v () 5/2(m) Vn
px(n.)) p) P7+ (p)7 log (p)
(107)
vp
Proof of Theorem B. 10. First, note that V(G, F, X) can be written in terms of the functional Φ4 defined in Eq. (83):
V(G, F, A) = of no (Z:
27

---

Recall that Ay is the event defined in Eq. (79). Under the assumptions of Theorem B.10, we can apply Lemma B.2 and Proposition B.4 to obtain
P(Ar) 121pp-
Hence, applying Proposition B.6 for F E As and via union bound, we obtain that with probability at least 1 n
n n - (
s C,,,D, Ei n) (F;
(108)
where & (n,p) defined in Eq. (89) and we recall the expressions
T6 FI pm1)
(F;
(FFFII, = Tr((FF")(FFF' p
n1 - 26 F; I, pvn)
Let us decompose Fo into
T (FFFL I, pm)) = Tr(FF' (FFT + ppn)) - ppr, Tp:TT(FFF (FFFFFFFFF + )
From Lemma B.11 stated below, we have with probability at least 1 p
(FFF'FFFF' + + 22((22) s S...D.K Ea(p) V2((2),
1 TT(FF + pmn) Vz((22 -ー
< C.D..K Prr (p) Vz(u2; )
p
where (p) is the approximation rate defined Eq. (100). Note that
" TYEEE++1)
(V2) p²u 2 E ) +2))
12) (-+)
P
1
11
1T
< [ + 112
1/1
111
p
1/2
1/2
(2))))
Tr
(2+
E
p
1
+
1/2
V/
p
+1)
=n),
Combining the above displays, we deduce that
P P [IFI, I, pt.) n T((, m2)
C.D,KK Pr+ (p))s(p) [pT2(12) + 12 ( Σ Σー
S S..,D,K Pr+ (p) [n 1/2) 2p²21 U Σ }}
Using Eq. (120) in Lemma B.14 stated in Section B.7, we conclude that with probability at least 1 p D.
(FF1, - ((T, C.D,,K Pr+ (p))s(p) (2),
(109)
Finally, by simple algebra, we have
(2)
n (F::(FII,puu) 1 T(1,, V22
n (F:), + +1] T F; FFI,pT)) - n (11,
n T(11,
{ n (F;; 1, pv1) 1- Y(i, P2)
T(v1.22) 22)
T(11, 12)
C. Pr. (p)
1- (()) )
T(m, v2) (110)
Note that by Eq. (119) in Lemma B.,4, we have
T2),
S (1 -
((),,)))) (1-T(Vn,
SC Px(n.)).
1 1- {2)
28

---

Hence rearranging the terms in Eq. (110) and using from conditions (106) and that p 2 C.D.KK. we obtain with probability at least -pp that
(2) n (F; 1- T(MI, U2)
((,,
S C...D,K Px(n,)) (p) 1 (2)
(111)
Using union bound and combining bounds Eqs. (108) and (111), we obtain with probability at least 1 n D - p ppp that
D(G,F, - (n)
T(u,,
$ ViG, )) - of I.,) + +o2
(F; 1 1_
C... (p, + (x(m,)) ()) [o2 nw FF; I, pmr) + Vn
C.C,D. (p, + -x(n, (p)) Vn,(A),
where we used Eq. (111) and conditions (106) in the last line. Replacing the rates Eg by their expressions conclude the proof this theorem.
Lemma B.11. Under the setting of Theorem B. 10 and assuming the same conditions (106), we have with probability at least 1 p= D.
Tr(FFT (FFT + -2) - =2((12)
s S...K. Ex(p) (2()),
(112)
Tr(FFT (FF + ) 33( Σー S..,D, By (1)Ea(p) Va(1z;E-1)
(113)
p
where Ep(p) is the approximation rate defined in Eq. (100).
The proof of this lemma can be found in Section B.7.4.
B.6 Approximation guarantee for the bias term Recall the expression for the bias term
B(B,; G, F, -
and its associated deterministic equivalent
x(22) = TrEE(E
p TT 12) 12)-2)
(B. 1 T(v,, v2)
(B., (E+ + (B E(E + v2) ?B..
-2)-
We prove in this section an approximation guarantee between B(B,; G, F, A) and (n. A). For convenience, we state a separate theorem for this term.
Theorem B.12 (Deterministic equivalent for the bias term). Assume the features (Zi)te(n) and jjell satisfy Assumption B. and that there exists m N such that p2 S (mD/p)). Then, for any D. K > O, there exist constants Th 1/2) and C..D.K > 0 such that the following holds. Let Pie and Pix be defined as per Eqs. (26) and (25), and recall that Tx = (mD/pD and 7+ == (p())))
For any n. p 2 C.DD.K and 0, if holds that
A
PA PAPP
(n p) 5/2 log log
3/2 2/22222())))) < KVn.
(114)
px(n p)2 P (p)8 log (p) < KVp,
then with probability least 1 n -p- have F, |B(B G, F. A) (B. X)1 < C.D.KK Ep(n, (,, X),
where the approximation rate given by
Ep(n.p) pn p0 log 7/2 (m)
p)(n,))2 py, (v)5 log 7/2 (p)
(115)
n
vp
29

---

Before starting the proof, let us introduce some notations. First, define PF the projection onto the span F, and L. F the projection orthogonal to the span of F, i.e.
PF == (F
-LF=I-1 Pp.
We can decompose the feature ! with respect to the orthogonal sum of these two subspaces
= PFg + +L.FF9 vD(F F) F PL.Fg.
We define = P. and R [ri, ri..... Tnl rn. E R Similarly, decompose the target function
hg) (B..g) (3 2) (.,
where we introduced
BF = VDF(FF)FF F F:)=FFFFFF) 3,,
f1. = PI.FB..
Note that in particular ([ B_. 0 by orthogonality.
Proof of Theorem 1. Step Decomposing the bias term.
Note that using the notations introduced above, we can decompose the bias term into
G, || F (Z' 2
1 F Br 2zz + - (Z3r RB _B_,F))) FF) 11, 1
Ti 2Tp + T3 + |3 |
where we denoted
T 12 F. -
T3 = A/3
(5, 1B,
T3 = (B
R 2 + z - 22 + a) 1) 2) RBL,F).
proceed similarly to the proof for the variance term, by first considering the deterministic equivalent over Z conditional on F, and then over F. We omit some repetitive details for the sake of brevity.
Step 1: Deterministic equivalent over Z conditional on F.
First note that, denoting A. --P 1/1 3 1/2
we have
T = (Z:
Furthermore, Ty and T-2 correspond respectively to the terms (90) and (91) in Proposition B.7 with 3r and 123 F where
[ (r,, 31,+)]=11 0,
E
|11,r
Thus, under the assumptions of Theorem 1., we can apply Propositions B.8 and B.7 to obtain (via union bound) that with probability at least - -
Ti (nv) 2 (F; A. pv))
C.,D.K - (p) (nm) 20: AM1))))
Th s C.DDKK E2(,,)) v VIB 1 ) Au,
T3 1-111,1111 .n (F: (F: s C..D.K E2(p,n) |B1,F112.
Hence deduce that
G. F, (nv) (n A., ||/3 11,1,111. n [F; I, pv))
|1/3 112
S S...K. (m, + Es(n, [ ;F; A.. + |1,3 -1,3__F
30

---

Let us simplify these terms. Recall that
n (F; A.. L F; Ar, Ar, pv1)
(F; pm)) Lo F; pv))
n 26 1, pv1)
n ( pv1)
For the term involving A., rewrite
oF A., pv,)) = vf(B Σx (F FF + ppp)=ppp)
(pr)) (F (F (F T F + pp)) p FF ()(FFF)) F)
(per) (B.)) (F ( |
Hence the terms involving 1/1,Fl1 cancel out and we obtain
+1 (m (F; pm1) 11 n [,), + +1 1, = (pw)) (3, (F F + pud) -3am)
1 (F; (F;1,
Combining the above displays, we deduce that with probability at least 1 n pp-
G, (p (B., (F) F (ppp))
1 - "
1 (F:FFI,,. pv1)
(116)
S. - (E) (n, (p (B., F + pm)) 233.)
1 1 (F; p01)
Step 2: Deterministic equivalents over F.
Following the same steps as Eq. (110) in the proof of Theorem B.10, we have with probability at least 1 p p-D
(1 - n T (F:L. -(1 (1- ((11, s C.,D (C
Furthermore, from Lemma B.13 stated below, with probability at least pD
(pmn) (F (F F pr)) BB.) (G.. S C.D,,K P++ Ep)) (B.,, (),
where (3,, A) is defined Eq. (118). Combining these two bounds and recalling conditions (114), obtain
(prr) (B., (F. F + (p))-333)
B (3.,(3,.A)
1 2. F: p1)))
1 T(,1, 12)
BB.p S C.DD.KK (2 p)p+, (p) + Pr+ (p))
1- (2)
Noting that (B,, A) = Bn. A)/(L (1- T(1 12)). we can combine this bound with Eq. (116) to obtain via union bound that with probability at least 1 1 n PP-
|BGG; - (B.,
D. (E)(n,)) + (n, + (1)Es())))))) + P.+ Ex(p)) (n.p(
Replacing the rates E by their expressions conclude the proof of this theorem.
Lemma B.13. Under the setting Theorem B. 12 and assuming the same conditions (114), we have with probability at least p--
(pmr)²((B.)) (FT TTT p-p))=+ 33) (3., S C..D.K Pyi E4 (n,, A), (117) where Ex(p) and Ex(p) are the approximation rates defined in Eqs. (100) and (103), and we denoted
(n. : - (E (B E(E v2) -22))_1)))))) 23.)
(118)
The proof of Lemma B. can be found in Section B.7.5.
31

---

B.7 Technical results
In this section, we prove the technical results that were deferred from the previous sections. We start with lemma that gathers useful bounds on the deterministic functionals.
Lemma B.14. There exists constant C. such that
(M, v2)) -1 S C. p)(
(119)
where we recall that T(v,,v) is defined per Eq. (105). Furthermore, under Assumption 3.2, we huve
pVl TY(EEE + 12)
p Tr(E ( + 122) 2) SC, (CC,,1, 12),
(120)
p [3,, 3 +()+)) 12) -3,)
Th ( + +2) SC. (B.
(121)
where (B, A) is defined as per Eq. (118) in Lemma 1..
Proof of Lemma B.14. Step 1: Equation (119). Note that we have
(1), & 1 T< 02) P.
In particular, if 2 p/m,, then we can simply write
1 = C..
(1 (1- (-)( <
1- 17-
For S p/u,. note that using the first identity in Eq. (76), we have
(1 (2)) - 1 1 n2
T+ (12))
n/1
S C.px(n).
x
Combining the previous two displays, we obtain Eq. (119). Step Equation (120).
We rewrite the left-hand side as Tr(E + v2)
Tr<EE + 12)
pud p Tr Σ +2) 2)
p p- D--TrEE(E+T) (((E+t)))]
-Tr(E(E 122 -1) Tr (Σ 22) -2
(1- Tr +2)
where we uses the second of the identities (76) in the second line, and Assumption 3.2 in the third line. Hence,
12)) I (C. 1) (TE pvd
Tr<E + v2)
pid p- (E+
Tr 12)
= (C. - 1) . (
Step 3: Equation (121).
Similarly, we get again using Eq. (76) and Assumption 3.2 that
p (3 (2)+
p E + u2 (B,,, (2+ - EI 12)
1 (1) 12 (B., ( (2+ BB))
and therefore
(G,, (0. < (C. 1) 1) { 12 ( 12) pvl ((.
pvi p- p (+
p P- ( + -2)
Bn (B,
which concludes the proof of this lemma.
32

---

B.7.1 Feature covariance matrix
Proof of Lemma B.2. Recall that we consider = p FFT with F = If 1..., f E Rexx and the f; are i..d. random vectors satisfying Assumption B.1. For any integers k2 h1 2 we split the weight feature matrix into F [F,, F2, Fa), where Fi [ I....... I E R with 1, f1, the first & coordinates of the feature vector f. F2 [f21..... 2 IJ RXx with f2. the next 222 1 coordinates of f. and F3 = (f........ s.pp R contains the rest of the coordinates. In other words, we split the feature vector into f, = 1f f25 fa,l. Denote
T
Σ [BI fl diag(Li .......... 2k RRIx6
Σ₂ Elj ..... E b()=-))((k2-1))
Σ3 E diag(Eh, +1 C +2....... E Roxx
We decompose the feature covariance matrix into
FF FIF
F2F F3F
(122)
P
Step 1: Bounding the eigenvalues of F1 and F2.
Introduce the whitened matrices
F = F1E) 1/2 [f1,1..
F 1
F = F2E2 1/2
- F2pll
so that the feature vectors figs and F2.5 have covariance Ix, and Ikg respectively, We have
|F 1/p lop
(. (o,))))²-1
sup vER [|=
P jELy
Denote Zy:= := (v, J F1,)²² 1. Then we have from Equation (60) applied B= Ej 1/2 vv ET for any integer q 1,
B Z & qC, / t cst C,q!
c
Hence we can apply Bernstein's 's inequality for centered sub-exponential random variable and obtain
IP
2 e/2
2exp { {-c.p- min(=?,e))
(123)
jE(p]
Following the proof of [Vershynin, 2010, Theorem 5.39], we deduce that there exist constants C., C..D such that with probability at least 1pp--
F/F1/P- lop S C.
hi + C..D
log(p)
In particular, there exists 7/. E (0, 1/4) and C..D > 0 such that for 2 C..D and via union bound, we have with probability least - p- (reparametrizing D), that for any ky I [n. pl.
F Fi/p Ix, llop 1/2.
From Eq. (122), we deduce that the k -thh eigenvalue of Σx for h < [m= pl is lower bounded by
F F P
F F
2
22 Sky
2
Amin
Sky
Amin
(124)
P
2
and
F FIFT
3
3
Amax
2
2
2
33

---

Similarly for F2, we have with probability at least 1 pp' 1 that for any h1 < k2 S 17, pl.
F2/p F 2
1k b llop S 1/22.
and therefore
F2F P
3 2 S
Amax
25k++1'
(125)
Step 2: Bounding the eigenvalues of F.
Equation (124) provides a lower bound on the eigenvalues & of EF up to k < [n= pl. Let's upper bound the p eigenvalues of Ep. From now set k2 p+ where p+ := L1/= p].
For the contribution of |+l. we use the matrix Bernstein's inequality as [Misiakiewicz and Saeed, 2024, Lemma 1] (see proof of Theorem A.2 in Appendix A) and obtain that for 2 Ck, with probability least 1 p
FlFaF'le S C.,D.K Sp. {I+ rx(p=) Vp log (rz(p.) V }
By the min-max theorem, we have with probability at least 1 p- for all hi < - 1,
F2F p
F3F3 P
3 2 11 CC.,, 22 { 1 rx(p.) Vp
22 Ska+1 S Amax
Sh 2
log (Px()))V)))))
p
where we used Eq. (125). For k 2 pa, we simply use that
- op
3 + C.D.K S.. { (1+ rx(p.)
log (rx(p.) vD)
2
P
We deduce from the above two displays that with probability at least 1 p-D DD we have for any S p
- C.KKDD
{52 + e2. MM(p)}
(126)
where we recall that we defined
My(k) 1+ rr(n v)) k
log (r>(In k]) V k).
Step 3: Bounding Ss (k) for k S p.
Recall that the intrinsic dimension rsp (k) at level k $ p is given by
Σ
TSP (k)
First note that for 2 k 2 [7 PP. we simply use that and the eigenvalues are nonincreasing to get
Σ < (p+1-k k) < C(1 11111))pp S C 1 17 k.
77
For k px - 1, we use that from Eq. (124) with probability at least
PD
E
2
3
hn-p--1
Σ
22
2
デ= Pl
Let's bound the second term on the right-hand hand side. Notice that
= min min Tr T
VVT)) < TT
34

---

where the minimization is over V E () with V V = ps- and the second inequality is obtained by taking V orthogonal to the matrix [F1, F2). We can rewrite
1 Σ
Tr(FFFF Tr(Es) p
1f, Tr(Es).
p
jelp
|| Tr(Eg). By Assumption B.1 with B = diag(0, I) (identity on the subspace Eg and O otherwise), we have
Introduce Zj ==
c C. Tr(Ea) o!
E || < qC, Eall'
c
We therefore we can apply Bernstein's inequality (123) again and we get
P
Σ
2 t.. Tr(2s) 2t-1(s)
< 2eepp(-c, min(pt.,ph)
P JE[N
Hence, for any p 2 C.DD with probability at least 1 1 p-
1 [T(FFF))) S 2Tr(Ea).
Combining the above display with the previous inequalities yields with probability at least p that for any k S [7, pl.
SS (k) = E
I SC
&
We deduce that there exist a constant C. such that with probability at least p-D we have for any = [n. n. S
(n,) Vn S C. . rx((n)) n,
(127)
where Tx (n) is the effective rank associated to E.
Step 4: Concluding the proof.
For any n. [n-- n1 p, we have (n) (x( 1. Hence, only need consider the
case n. < Using Eqs. (126) and (127), we get
(n) =1 1+
n
1 1+
SS
(nx)
Vn
log (TS (mm) (m)) vn))
X
n
p Epr Msrlo) Mx(1)
11+ 11+0 C.D
p
+ n p
pall)) My(n),
$ C1+C..
A
which concludes the proof.
B.7.2
Concentration of the fixed points
Proof of Proposition B.4. Recall that (Ø,, (2) E RR are the unique solution to the random fixed point equations (77). From the first equation, we have the following bounds on D1:
pd < pi
pl EF + pd
From Lemma B.2, we have with probability at least - p that |E S C..D.K S p. Hence, by the uniform concentration over [pλ/n, (n² pA)/n] in Lemma B. stated below and an union bound, we deduce that with probability at least 1 ppp-p.
Pa_ 5/2 1og((n)
TT(FF' (FFT + -p - (X(I+++)) < C.
Tr (E(E+)))
=: ())
35

---

Therefore, we can rewrite the fixed equations (77) as
A
Σ + (2) ;2) (1 + O(F),
V
PVd
Tr (Σ(>)))))))))))) + b2)
p
82
where with probability at least p n, we have (6(F) - Ep). Therefore, by condition (78) and 2 D.D.KK
C.D 1 log(p) S
and we can directly use Lemma B.17 stated below to obtain with probability at least - p
i mil < C. (p) (n,p))
1 v2l
I C. Eg(p) px(n. p).
V2
This concludes the proof of this proposition.
For any K 2 0, denote (K) E Ro the unique positive solution
K
(2)))))))))))))
(128)
(K)
We will further define analogously to Eq. (80) the truncated fixed point
(x)
P
Tr Tr (Eo (2,0()))
(129)
122,((()
where we recall that we denoted
7(k) + Tr (+)) will be convenient to recall the notations
55 (F;
*Tr(FFT(FF)) +))
p
! TT TFFF (FoF) + *xx))
22 (F: =
and the deterministic equivalents
(2(v2(k)) = - Tr
p
1
(22(22,((k)) Tr TToEo(Eo (22(()))
p
The next lemma show that (F x) concentrates (2((22):) uniformly
interval of k.
Lemma B.15. Under the setting of Proposition B.4 and for any D, K 2 0, there exist constants The (0, 1/4) and C..D.K such that the following holds. For any p 2 C..D.K and 0. if holds that
aA === (p>/n)) 2 p
Prx (p) 5/2 log (p) < KVP.
(130)
then with probability least 1 p D. we have for any N [p1/ n, p(p² + 2)/nl,
(2(FF)) M2((2(K)) s C.D.KK (x(a) log (p)
(p)
1 (12(k)))
(131)
vP
Proof of Lemma B.15. Throughout the proof we assume that we are working on the event
log (p)
[F, - (00)) S SC..D
Vp 7pp//n).
which happens with probability least 1 pp by Lemma B.3 via union bound. Note that (()) 2 7(AAn)) for all the E IpA/n, + A)/n]. Furthermore, we assume that 2 C. chosen large enough so that | F. (0) llop < 1/2 7(p//n) so that
FFT k 2 (15)
36

---

The proof will proceed via standard union bound argument over x in the interval ipA/n, p(p" + +)/mi) Let us first prove Eq. (131) for fixed K. We first simplify the functional by rewriting it as
(c)
=
M Tr ((FFT + +k)=
p
= 1
K
Tr (FOF) +x(x))) + A
where we denoted
A
TT((FF" + +k)-1) - TT +((()))
-IT((FFT + (x - (166))))
(p) TT((FoFFT + +(()))
SC.,D
vp
Using again the above identity, we rewrite
1 ( (1))) 1 1
2 Fo: (x))
P
7(k) 7(k)
We can now apply Eq. (55) in Theorem A.2: under the assumption of Proposition B.4 and recalling the conditions (130), we have with probability at least 1-pp" p
(F(o::((1)) - V2((2,0(1)) s S...D.K Pr(m) (D) (v) log (p)
V2((220(()))
vp
Combining the above displays, we obtain that with probability at least 1 - -p-D
(++)+)
22 kR) W2(v22((1)) DV2,0
$ L2 (o:)))(()))) - (2((2,0(1))) + +K/AI
K (xx)
Pr(ne 5/2 1/g3/2(0) SC.,D,K
(o)
(2()2,0(1)) + C.DD
K "r +1)))-
vp where we used in the first inequality identity (129) get
vp p
(1 Tr 02.0) 0)))))))))) = Tr(E+)
K
7(x)
p
p1/2.0
Further note that using condition (130), we can simplify the hight-hand side iTT((FFFTT (xx))
(k) 1 - V2((220(1))] + C.DD.K K (2(220(()))
S C...D.K V2((220(x))+ Tr(E+)
21/20
We can now use Eq. (82) in Lemma B.5 applied to (2))) and (1)) to concluded that with probability at least 1
E(p) = C.D (p) log)(p)
(2; (2((2(k)) < E(p) (2(22(N)),
(132)
vD
We now consider - p- Pn, of the interval k E [pA/n, + A)/nJ. which contains at most p P+3 points. We can use union bound over Pn, and reparametrizing D' D P + 3, so that with probability at least 1 p- D Equation (132) holds for any κ E Pn. Then for any point
N1 (pA/n,p(Kp² + A)/n), denote Kig E Pn, its closest point. Then by Lemma 16 stated below.
we have
(2 k1) (2(22(K1))
(FF; R1) - -T, nO) (F:: - (2((2((o))) + (22((((5))) ( (2((2(())))
CK |81 Nol 50 (F;50) E(p) (2((2((0)) + OK |m - N
p CK-P + E(p)) (1 CK- +E(w) V2((2((1)).
37

---

where we used that |K1 - Kol S P Taking P = CK + 1 concludes the proof.
Lemma B.16. Under the setting of Proposition B.4 and for any D, K 2 O, there exist constants
Mh 1/4), C > 0 and C..D > O such that the following holds. For any 2 and X > 0, it holds that
((2/n)) = pd + +Tr(+)22)
(133)
then for any Ko, K1 2 pd/n, we have
(2((2(x1)) M2 (2((())))
Spox |161 kol.
(134)
Furthermore, ifp C.DD. then have with probability 1 ppD that for any K1, K2 pd/n.
(F:1)) s p CK 161 Kul.
(135)
(o))
Proof of Lemma B. Using the identity (128), we can decompose the first difference into
(12(1)) (25(2(()0)
ae (no)
(2(11)
pd (12(())))
U2 (25) (x(1
31
[K1 Kol +
M2(Ku) pV (v2(())
From condition (133) and the proof of [Misiakiewicz. and Saeed, 2024, Lemma 11], we have
S p 342K
(NO) (V2((12(o)))
(2((50) -1
S Sp 242K |11
Kol-
(22(61)
Combining the above inequalities, we deduce that there exists constant C > 0 such that
(2(((m))) - S s CK Is kol-
(2((2(()))
For the second inequality (135), we rewrite the difference as
(F: 11)
Tr TrFF (FF + +1)) + ko)
161 Kig
(2 Ko)
(FFF + +Ko)
< [FF
-Kol.
Hence, recalling Lemma B.3 and condition (133), for any DD get with probability least
1 and for all Kı, K2 2 pd/n,
T F; R1) 22 F; KD)
S
7(k1) |81 Kol S "6 [m1 Kol-
which concludes the proof of this lemma.
We consider Dz) E Ryzo the unique positive solutions of the perturbed equations:
n
= Tr
(X
(1+,),
(136)
(137)
38

---

Lemma B.17. Let 17, E (0,1 be chosen as in Proposition B.4. Then there exists C.. C² > 0 such that for any E R with
lel.C. . (..n,, - 2
then
uf - v of
v - 1 SCC (x, lel
S C. px(m.p)
1/2
Proof of Lemma B.17. For convenience, we introduce the notations
81 = 1/
o
62 = V/ 1/2
vf
We first consider the second equation (137) and subtract the identities for (V5, and (g) to obtain
0
1/
+ Tr
[ + (
1
82
L1
+ +
= O.
1
Hence, we obtain the first identity
(WE/v5)
52 = 81
(138)
M Tr<E(>))))))) (2) (up/v4)
p
We now turn to the first equation (136): we obtain similarly
ト = (x
(E(E (X(E))+)))))))))))))))
vi
 = 62 Tf + - ETr
ETr (Σ + -1)
Hence, rearranging the term and recalling the first identity (136), we get the second identity
(v//v8) =Tr (Σ =1)) (139)
81 vP +1++)
(v9/22) p 2
From this identity, we directly have
v X
8 S |E]
+ TEEE(E+1)))
Note that for 2 p/n.. we simply have by Eq. (136) that
S A
(
+ < p <
n7. 17+
n TrE + -1)
n p
where we use that Tr + x S p by Eq. (137). For n S p/n,, let's denote ps X/v9. Rewriting Eq. (136), we get that
n N4 1+ T+ E +
Hence
"
= Tr E < n) [u/=<im + +1((2))1) + Tr(E 2/m In m/ + +1(2))-1)
A
< 174
Tr Σ [2(
21
< n, (1 + Tr
39

---

where we use in the last inequality that x//122 I and the definition of the effective rank. Rearranging the terms we obtain
1
{
Tr( Tr(22lnon)
+ Combining the above bounds we deduce that
|611 S C.lel { 1 Insp/n.
Tr Tr(D2(nnn) S SC. (C.ppx(n,1) -s).
A
By assumption C. -.(,,) p) - |E| S 1/2 and therefore of I 2vf. We conclude the first inequality
vf
v
of S C. (n(pp) |c]-
Recalling Eq. (138), we have directly
12
1/
vf v
1021 S |01
<
v
V1
which concludes the proof.
B.7.3 Proof of deterministic equivalents for functionals on Z
Proof of Proposition B.6. Recall that (n) defined in Eq. (72) and that for F Ar, have (x(n)= S Px,,,KPA(n, for all n E N. Under the assumptions of Proposition B.6, we can apply Theorem A.2 to Z conditional on F to obtain that with probability at least 1 - n
(x 5/2
5/2 log (/23222())
(2(Z
P (FFpp))
S S...D.K
P 2 Fūr))
n
n
no A
2
$ CC.DD.K (n p) log
5/2 (n)
D3 [2 (2
(F (F: A, pin)
(F; A, pin).
S S...D.K Px p)8
3/2 3/2 log
i A,
33 F; A. pi))
(FF A, po1):
Vn
where 1/1 is the solution of the fixed point equation (77). We conclude the proof using Lemma B.18 stated below and that by condition (85), we have C.,D.K (x(m.))) S C.D.KKK.
Proof of Proposition B.7. Again, under the assumptions of the proposition and for F E Ar, we can apply [Misiakiewicz and Saeed, 2024, Lemma 10] to get
p)(n, log b 712
|u,
(2 + TTu) n F; I.:)) S C..DDK
vn
< C..,D,K p)(n, log (1)
(u, 15
2
nu
(F
F; vo pūr).
vn
A
We conclude by combining these inequalities with Lemma B.18.
Lemma B.18. For F AF, we have
52 (p:(F)))) 5z F: (F:
S SC.,,, - F2
(140)
(o(F; (,,i) Te F; (F;AF A, ArI)
(F (F; A, pv1).
(141)
and
nin A
2
T (F; A,pūT) - nan 2 (F; A, p,
(142)
S S.D.K.K (x)))
nP1
$5 (F; A. A.Pr)).
X
40

---

Proof of Lemma 1. For convenience, we denote x := 11, k² := in. and T = Ep. For Eq. (140),
we simply use that p (ip))) pF = Tr (T( - Tr (I(T + +x)
| - I'I (T + * + x))
Ik' rl Ir (T(T + +
C..D,KK - Ex( p p(n).
Similarly, by simple algebra, we have
(F(F; A, pi1) To F; A, pv))
|r(Ar? T + N2)
Ir ( (T + k))
2 Ir [AT [T + (T + 2) + 1K2 - (T) xx)
k - n'l {
| w+*l n'|
R¹ 2
Tr (T+
n¹
S S..,D Ev(p) (F; pm1)
(143)
Furthermore, note that by the identity (77),
I. (n (n- Fi; pin)
S (F: (n-
22 (F:
D1 (F::)
Furthermore, we have from the previous computation and simple algebra that
1 (F:p))) < (1 C.D,KEE,()) 51 + I C.D.K. P.D.K.PAAAA PA(n.)).
A
where we used the same argument as in the proof of Lemma B.17 in the last inequality as well as condition (85). The proof of Eqs. (142) and (141) from simple algebra from the above displays and (143).
B.7.4 Proof of Lemma B.11
Proof of Lemma I. For convenience, we introduce the notations
Gr = (FFT + p Go = FF + +
R Ro= + +1 (144)
where we recall that we denoted 7+ = ((w)) = pud +r Recall that for the first approximation guarantee, denote
(=(Fipm) = 1 Gr(F
1 (F = Tr Tr(FoFFGo).
p
p
and the deterministic equivalents
(2(v2) 1 (r((EE+))))
22 Tr Eo + v220) v2.0)
p
For the second approximation guarantee, recall that we denote
(F ,v1)
[I(FFF GZ)
TF pv1)
p
p
and their associated deterministic equivalents
1 Tr<E + 122) -2) p "1'"""""""">>> }
1
Tr(Eo ED + 12.0) -2))
(2 E
13(22 Eg
p ppp- - TF E E> + 12,0) 12)
We separate the analysis of the low-degree part Fo from the high-degree part F.. To remove the dependency on the high-degree part F+, we recall that by Lemma B.3, we have with probability at least 1 1- p=
log (p)
A llop S C..D
7+
(145)
vD
41

---

where we denoted A : F+FF+++ - Tr(E+) ) Ip and we recall that 7+ 7(p1)) = pn + Tr(E+)
In particular, taking 2 Ct,D, we have || P op S + and therefore
2
|G S 2 Go lop
(146)
Step 1: Bound on ( (F:(): (2(222) First note that we have the identity
(2(F; 1 TT = -1 -1- + 11
where we denoted θ = Tr(Go) - -Ir(GF). By Eqs. (145) and (146), we have
|0| = |Tr(GrAGo) S C..D (p)
Tr(Go).
(147)
v/
Using again the above identity, we have
! Tr = -
1
2
(148)
P
7+
7+
Under the assumption of the lemma, we can apply Proposition B.8 and obtain with probability at least 1 - p- D that
22 (F:: - W2(v2,)) s C.D.KK Ealp) V2(220),
(149)
where Ep( is defined in Eq. (100). Furthermore note that using identity (80), we have
Tr(E+)
pv1 v2(120) = V2((20)) + Tr(E+)
7+
7+
pv2,0
and that by Eq. (82) in Lemma B.5,
Tr Tr(E+) 1/2(22)
C I (2((2))
V/ 42((200)
(150)
pV2,0
p
Thus combining Eqs. (147), (149) and (150), we obtain
(F:p1)) (2(212) S v / + 7+
pdl
FF pv)) V2(2220)
V2((220) + Tr(E+)
(2((22
pv2.0
log"(()
pul V2(22.0 + V2(12) + Es(p) + 1) [nTT((G)) Vp
< C.C.D.K
7+
with probability at least 1 p-D via union bound. Using condition (106), can simplify the right-hand side using identity (148) and bounds (149) and (150) to get
Ki Tr - p |1 v2(22,0)
KC.,D.K
S C...D,K V12(1220) Tr(E+)
< C.D.K..
p1/2,0
This concludes the proof of the first part of this lemma.
Step 2: Bound on 1 (F; -1 ,p1) - (a )ー
We proceed similarly as in the first part and omit some repetitive details. First note that we rewrite
(F .wn)
TT(GF) Tr(
p
IT(GG) - Tr( +
Tr(E,)
-- ( (Fo: + 7+
pvl (Foo En ,pv) + O
2
42

---

where
|0| Tr(GF) - - pu) - pul pul p
(151)
S C..D lo)
TT + +
vp
Again, by Proposition B.8, we get that with probability at least p D that
क2 (F(Fo: - v2((2,0) - C.,D.K Ea(p) V2(U2,0)
(152)
(F; En pm1) - V3 (3(22,0 - S C....K Es(p) 23(22,0 2n
Furthermore, note that by Lemma 1. stated below, we have
Tr(E+) (1 V2((2,)) + p (32,00 Σク²) - V3 (3 Σー S <CP++l) V. Ve(ug )) (153)
(P)
7+
p
Combining Eqs. (151), (152) and (153), we deduce via union bound that with probability at least
1 1-p
(F pV))
- ,pm) V3(12;
S C.DDk Ex(p) [T. + +u TT(G + Tr(E.)²
V (12,0) + p 1 (2(22 Eo + 32 xー1) --1):
7
7+
Let us simplify the right hand side. First, from the proof of Lemma B.19, we have
Tr(E+)² V2((2,0) pal (2(1200 Eg¹) s Cp (p) 3 E )
7
7+
Combining the above two displays with Ep( S from conditions (106) yields Tr( C..D.K (p) U3(12:E-1 Finally, note that using Eq. (152) and again E3(p) < K that
Tr(G.)
P
V1 (r
pVi L (F; ET 1/2 pp)) Co.
7+
which concludes the proof of this lemma.
Lemma B.19. Assuming that p¹ c2 S 74. we have
T
(1 V2(2220)) + pdd (2(2200 ET Vs(12; s <0Pr (p)
Uz(2s )
7
Proof of Lemma B. For convenience, we introduce
1 Tr Ep + =2,))
1 TT +22)
T(v2.)) =
T(v2) = p
p
Using that
Tr(En Eo + +2,00
= (V2(220) ((22n)),
12.0
obtain by simple algebra and using identity (80) that
(2(2200) + Tr(E.) (v2,0)
Tr Tr(-.) (1 V2(v2,0) +
PVl V (22,0 b)
pv2.0
7+
V2
p(1 ((2,,))
Following the proof of [Misiakiewicz and Saced, 2024, Lemma 7], we get that
(VV2,0) T(v2) < 10 2
C
<
7/
p'
(1 ---(u2n))- < (1 V2( = PV2,0 < Cp (p). 7+
Recalling Eq. (82) in Lemma B.5, we can conclude the proof using simple algebraic manipulations similarly to [Misiakiewicz and Saced, 2024, Lemma 7].
D
43

---

B.7.5 Proof of Lemma B.13
Proof of Lemma B.1 We will follow similar steps as in the proof of Lemma B.11. For the sake of brevity, we omit some repetitive details. Recall that we introduced the notations (144). We decompose the coefficient vector 3, [B,, B_.] with 30 E I the first m coordinates of B, (aligned with the
top m eigenspaces), while 3+ Rx corresponds to the rest of the coordinates. Further introduce the matrices
A, = Σ 1/2 B. 1/2 and recall the expressions of the functionals
Ao = Σσ 1/2 12113BB8 B0.30200 1/2
1 AF; Tr RE "T
$ (Fo pun) Ir Ro 2/
as well
(F;; A.. pM1)
Tr 1
-r.TT(AA. A. A.AE11 RF FFFFFFFF FRE
, 0: Ao. pV1)
-T 1/2 20
p We further recall the expressions of the deterministic equivalents
v (v2; A.) = TTA
V (V2,0; Ao) = To Eo + v220)
and
(/2; A.) 1 Tr E + 1/2) 1)
p TrEE*
Σ + 112 -2)
Tr
Σg v2.0) -2)
(3(22,0 Ao)
Tr(E [
En + 12200) -2
We first rewrite our functionals into
(pm) (B.. R² B2) = (pv)) (B.) (pdn) RF FR)
= (pvr) [F)(F: A.. pp. ( (F; A.. pun)
and study each term separately.
Step 1: Bounding term き, (F; A.,pp))
Let us start by removing the dependency on the high degree part F+ the denominator, Note that we can rewrite the matrix R in block matrix form
F
Fg + pV1
F.F+ F. F.F.+pu.)
)
Roo Rot R++/
Rot
R = (pr))
F.
so that
(F;:) = 33 3o + +23, R., + + RT
Let us study each of these terms separately. Denote G. == F.F.. + pvy. By simple algebra, we have
RooB, = =33 LF.G..Fo+]) B,= = 7 (Fo; Ao. pV1) + Ooo.
where
10 = 1+36 RoB3 - 3/ (F Fo fo+)) B.
< C
R 1/2 F! (I 7
/2
Ro,
Ro,3
opp
< CC.D log 3 (v)
11 (Fo: Au.pr1)
vp
Furthermore, from Proposition B.8, we have with probability at least - -D that
74 1+ (Fo; Ao. - 22 V (V2.0 Ao) S Cu.D.K Es(p) 12 42 (22.0 Ao).
44

---

Hence, combining the previous two displays and using that Ep(p) S K by conditions (114) we have
| RooB. -2.0 ( Ao) S C.
log (p)
+ Es(o)
} 12,0 (u2,0; Ao). (154)
vp
Similarly, denoting Go (FoFi) + +p1)) we can rewrite the third term
B 3+ = F F +1) B = -12 O++
where with probability at least 1 - D
FT G2 Go = = B.
Go F+ FFF
1/2
1/2
+1)
Go F+
1/2
|[ F + G 3 op
F1
||
(155)
- /2 3+12
1+122
74
where we used the same concentration argument as in Step 3 of the proof of Lemma B.2.
Finally, we rewrite
3 3o+ = -
(F + +p)) 3+
Hence, using Eqs. (154) and (155) well conditions (114), obtain
Ro+ C.DD.K Vp
{12,0 v (12,0; Ao) + [
(156)
Finally, note that by Lemma B.20 stated below, we have
C 122.0 (Bp. (Eo 12.0) BB) + +11++12 12 ( A.)l ( A.). (157)
Combining Eqs. (154), (155), (156), and (157), we deduce that with probability at least 1 - p- v2 V (u2; A.) < C.,D,K
log"(p) Vp
+ +Es(o) } 12201 A.). (158)
(pr)) ) (F;; A., pv))
Step Bounding term (F )M
We rewrite this term as
B RF FR3.) FB. F.F.) +
where
|
(B., F (G& F3.)
log log
(B., FT Go (-2AGF + AG GoFB.) C.D..K
(B,, F.. T...FB.).
(159)
Let us decompose
FB.FFTG.FF (By, F.G.F + + F. + 1B.. G.F For the first term, we have directly from Proposition B.8 that
|B: F. G. (V2.00 Ao) s C.D.K Es(p) pV2 Ao).
(160)
For the two other terms, notice that they correspond to the terms (101) and (102) in Proposition B.9 with e = Bn and u F+B where
(f 0,
Elu
||
1/2 B. 1.2.2
45

---

Hence, by Proposition B.9, we have with probability at least - p- that
| 1
p| 3
(0+. F 2 p Tr(E Eo 12,0)
S C.D.KK Es(p)
7
pV220 /V3(1200:Ao)
(0+, F. s C.D.KK Ex(p)
74
(161)
Furthermore, by Lemma B.20 stated below
(Bo, Eu Eg + - Bb) + (B_, B+) pv (12; A.)
S C.r+ (p)
pVV3(12 A.).
p Tr Ei + 22
P
(162)
Combining Eqs. (154), (155), (156), and (157), we deduce that with probability at least 1 1 -pp-.
[F; (F; A., pm1) - 3Vu A.) S C.D.KK Pry Ep) pV A.).
(163)
where we used that
P12.0
p|
|||=""",
pV Ao) Cp (p)
Tr( En + 22 + +DV3(120: Ao) }
|| 1=//3111//22
7-
7
1/2 Σ
1411
|/ 3. 111/2/22
Cprt (v) p p- E Eo 12.00 -2))
7
Step 3: Combining the terms.
From Eqs. (158) and (163), we have with probability at least 1 - p-D that
(B, R²B - u2 (12; A.) + (pV) (pw))pVa(us) A.)l C.C.D.K Py: Ep)
A.) + (pm (VV A.)].
First, it straightforward verify that indeed
1/ (1/2 A.) (pv))pVa(t A.) = (B..
Then by Eq. (121) in Lemma B. 14, we conclude that with probability at least 1 - p DD
(pwn (B,, R² R²BB) (B., 2) S C.D,KK Pri (1)) (B,,
which concludes the proof of this lemma.
Lemma B.20. Assuming that p² S 7+, we have
C
|220 (By Eo + v2 B,) + 1|3 - 12 A.)l s 1 A.),
p
(Bg, Eol En + 12 + 1 34
" (p)
pVaauuz A.)
Tr ( En + 22
p
Proof of Lemma B.20. This lemma follows from the same arguments as in the proofs of Lemma B.5 and Lemma B.19.
C Details of the numerical illustration
In this section we provide further examples of comparison between the excess risk computed using the deterministic equivalent Theorem 3.3 and numerical simulations, together with details about their realization. Results from numerical experiments are obtained averaging over 20-50 seeds. The data dimension d 100, with the exception of experiments involving real data (see Appendix C.4) and the ones realized considering the Gaussian design described in Appendix C.2.
46

---

10
109
errrr
10"1
12
10-1
Figure 4: Relative difference between the excess risk (eq. (6)) of random features ridge regression from numerical simulation and its deterministic equivalent (Theorem 3.3), with regularization strength A 0.1, and noise variance of 0. 1. The relative error is (((nA))(
in agreement with eq, (32). The simulations are made following the procedure described in appendix C.2, with & 1111 and _r,k k 1,46, (left) p 3000 fixed (right) 3000 fixed.
C.1 Self-consistent equations
To solve Equations 18 and 19 numerically, the following approach has been employed. From equation
19,
(
X
4
2
1 +
(164)
pV22
122
p
Substituting this expression in equation 18, we obtain
21 (1
2
Tr(E + 11)
(165)
v2
P
12>0
1/2 = 11
+
1/2
TrEE + + 11).
(166)
p
Therefore, the parameters V and 1/2 have been computed by iterating
2
2/2
21
- +
(167)
2
PV
5/ 1/ = u
p+1
2/2 +
Tr + 11)-1),
(168)
p
until chosen tolerance was reached.
C.2
Gaussian design
Figures 3, 4 and 9 have been realized considering Gaussian design for the vectors in "feature space' defined in Appendix B.I. In particular, fixed Σ and B., we have drawn
(g. Mid. I), {f,)eeb) mid. (O, E),
and consequently (v, = 3. 9 [eenj- Then the random feature estimator can be computed according to eqs. (61) and (62). In the figures produced with this setting, the elements of G3, and diag( Σ) follow power-laws truncated at the component 10a
C.3 Empirical diagonalization
Whenever the data probability distribution far the weights distribution pa are unknown (e.g. in all cases involving real data), we estimated the matrix Σ and the vector B3, following the procedure described in this section and summarized in Algorithm 1. Consider a data set of N covariates
47

---

(arhee[N drawn from Ma and N noiseless labels {vs = fe: and a set of P weights he()) In Figures 1, 5, 6, 7, 8, for which this procedure was used, we take both P P = 10 (with the exception of Fig. (right), where P = 8000) and approximate be and Ma respectively with the empirical distributions jr Ei= N- N-(5 mx) and i. = Σド= P- ō(w -wz). Then eq.
(2) becomes
P Σ 1=1
K (x,x²') = Ewwar ( u u))pppr w)]
p- yax, pll w w w
(169)
and since eq. (11) implies K (a, yen (x) (t))("") defining the Gram matrix KPuP N with elements Ka K( (æ) xp N and the vectors 45 (vx(x1),...... ".......,,.../ (x(xN)) T,
we can write
the following eigenvalue problems, for & E [N]:
K tb. v4
(170)
We then constructed the matrix Σ diag(E? E .... EN and used it as an approximation of Σ. One should note that in this situation t'x ya (x)) = òE corresponds to 1b 1by = Nr
Similarly, eq. (13) implies B.,t Ex [fa (x: (z)))((2))) which can be approximated by
B. = N N $4.
(171)
Algorithm 1 Empirical diagonalization
Require: {æ;) HEIN "iid. Pizi {y S. (x;)))EEE() (wg]sEtPy mia Pwe Ensure: E, Gr, (B,,
i, 1' E {1...., NJ do
Kir (NP) Ej= s0 w. w,)pp(a,
end for
(EEx, k
eig(K)
D Sw 1 NN0
for K E (1, (I....,.1 N do
3R N N T end for
Σ + diag (51 .1....
B, + , BN)
Iterate eqs. (167-168) up to tolerance e
Compute the deterministic equivalent for the excess risk (22-24)
C.4 Real data
We performed numerical simulations sampling the training data from the MNIST data set Lecun et al. [1998] and the FashionMNIST data set Xiao et al. [2017], standardizing both covariates and labels, reshaping the images into vectors with d 748. Results are shown in Figures 1 (right) and 7 (left).
C.5 Trained network
In Figure (right), we upply the procedure described in Appendix C.3 to the trained weights of two layer neural network with hidden layer of size
1
f(æ; W, a)
a w))).
At initialization, the weights randomly drawn; then, after sampling training dataset X u R Yur E R the weights of the first layer are trained using gradient descent, iterating for = 1, ,....,T the following
W 2+1 W,
17 x
j((x; (o)
(172)
Mer
where 7 is the learning rate, c the Hadamard product, f and y are applied component-wise; finally, the weights of the second layer are minimized using ridge regression, as in eq. (5).
48

---

1-10"
A-10
1-0
1-102
10a
200
400
600
800
1000
1200
200 400
600
800
1000
1200
Figure 5: Excess risk eq. (6) of random features ridge regression. Solid lines are obtained from the deterministic equivalent in Theorem 3.3, and points are numerical simulations, with the different curves denoting different regularization strengths X 2 0. Training data (04, sampled from teacher-student model Y/4 tanh((B, x))) + Ei. of 0.1, with random feature map p(z, [ w) ReLU(((w, x)). Both covariates {z;} and weights [w: are uniformly sampled from the d-dimensional spheres respectively with radius v and 1. (Left) Excess risk as a function of n, with p 600 fixed. (Right) Excess risk function of p. with 500 fixed.
10a
1=
10002
10-1
200
400 600
800
1000
1200
200
400
600
800
1000
1200
Figure 6: Excess risk eq. (6) of random features ridge regression. Solid lines obtained from the deterministic equivalent in Theorem 3.3, and points are numerical simulations, with the different curves denoting different regularization strengths À 2 0. Training data (æ,, yt)xe(n)- sampled from teacher-student model y taah( ((3, a.))) Ei, of 0.1, 3; Midd. (00, Ia), with spiked random feature map sæ(x, w) erf((w + æ)) where A200, I.), Rd d(0,d-11a) and u (o, 1). (Left) Excess risk as function of n, with = 500 fixed. (Right) Excess risk as function of with 300 fixed.
49

---

A-
RF
1- 10
6D step
10-
10
GD
Excess Risk
10a
200 400 600 800
1000
25
50 75 100
125
150
175
200
P
Figure 7: (Left) Excess risk eq. (6) of random features ridge regression. Solid lines are obtained from the deterministic equivalent in Theorem 3.3, and points are numerical simulations, with the different curves denoting different regularization strengths 2 O. Training data (æ,, [e]]] 300, sub-sampled from the MNIST data Lecun al. [1998], with feature map given by aa w) = erf((w: (w)x)) and f (0 d Ia). (Right) Excess risk eq. (6) of random features ridge regression. Solid lines are obtained from the deterministic equivalent in Theorem 3.3, and points are numerical simulations, with the different curves denoting different number of total iterations of gradient descent on the weight of the first layer with learning rate 7j = 10-2, before training the second layer with regularization strength X 10-4 (details in Appendix C.5). Zero iterations corresponds to random feature regression (RF). Training data (æ,, ke)) sampled from a teacher- student model ys (3, x4), with random feature map (a w) ReLU((w a)) and p 8000 fixed. Both covariates {a;} and initialization weights {w;} are uniformly sampled from the d- dimensional spheres respectively with radius v and 1.
10"3
10
1.0
Excess Risk Rt
0.8
0.4
Figure 8: Excess risk eq. (6) random features ridge regression. Solid lines are obtained from the deterministic equivalent in Theorem 3.3, and points are numerical simulations, with the different curves denoting different regularization strengths 2 0. Training data (æ,, V)) sampled from a teacher-student model yt = tanh Lanh((3, ((3,x;)) + ei, o = 0.1, with random feature map given by the convolutional features with global average pooling s( w) 1/8 D/
F-1 ReLU((w, gr x)) where Sr s (#141;... Ld, I1 2i,..., xt) the E-shift operator with cyclic boundary conditions. Both covariates (æ,) and weights (w,) are uniformly sampled from the d-dimensional spheres
respectively with radius vd and 1. (Left) Excess risk function of n, with p 500 fixed. (Right) Excess risk as a function p. with n 500 fixed. The discrepancy between theoretical results and numerical experiments R R/VRAp, compatible with the approximation rate eq. (32).
50

---

D Derivation of the rates
In this appendix we present a sketch of the derivation of the decay rates for the excess error given in Section 4. We choose
p n2, == n= (e-1), with q, 2 0
and we assume
B. = A
with ar > 1, r>> 0,
which follows the source and capacity conditions stated in (37). In order simplify the derivation of the rates, we introduce the following notation:
8cx
(V)
8 0, 0505
u)
For 8 + a(8 - -7) < 1 and in the limit v + O. this term can be written as Riemann sum as follows
(v) v 7464%
(173)
((ku)//)- 1)7
k=
x x-
-ー 8) -1 01-0
=0
(174)
wu
(r- + 1)7
Otherwise, 8 + ar66 7) 1, we can write:
1//
k a 6a
k k-s-ba
T2-(1)
(k- + 1/
(k- + v)
A=Lutaj+t
x x- 80
(1-6)- +1 + O(1)
01))
140//0 (x-a + 1)7
Hence, for v + 0,
(v,(v) 0 (1/6
(175)
Rewriting (18-19) as follows, we study the dependence of the positive parameters 1/2 and i with n
12 = " (12) +
1/1 (22)
In the limit - oc, we can distinguish the following regimes
Th < n,p
122 1// <n = (<a(11g)
V1 w==n (1 11+00 (TH) (1z)m 1== x (1 11+0 (())))))))))1
==)0()
vi
2 V2 22 n
(11 <p
U2 < n
V1 Xn -1
vi > n
9 19> 19>11>0 1>a
(1( n (nnn) 122 11 +0
1/2 1/4 0 (n (n
111 R 1/2 n
0 (12)p ))
U2 = v (1+)(1))
(12) < n
0/2 1/ <n
<< (1A y Rt
P1 < 1/2
<
i - (1+ (Ti TR =
V1 (1 1 o
1/2 x ag
"5 -///- = n - o(1)
In (a) we have used the fact that, for d2 constant or diverging with n, To (12) is respetively ((1) or infinitesimal, while we have that T (22) is diverging in both cases. Hence, V2 must be infinitesimal,
51

---

allowing us to use (173). In conclusion, as n 00,
50 [n 11 ~ Int
for > and
(176)
otherwise
12 R 0 (n (n
(177)
in particular
1 1 0 (155//n0 (=)))
11
for q > 1A 6/a
(178)
10 (0(n-trng = (1) otherwise
D.1 Variance term
Considering the results (176-178), we can write (20) as
U2) p (1 Ki1
11
2
Th (p2)
+
(179)
1/2
122
T2p (12)
n 11g 1/a) = O (n - (1-((1)))))
for > A 6/a
(180)
n1 (1-9)) o(1)) otherwise
One could notice, using the integral approximation of the Riemann sum 7 (V2) given in (173), that 1 ((1, U2) = 0(1) for any choice of and q. Hence, the variance term given by (23) decays with with rate
(v(, = - (--=@aan)
D.2 Bias term
Using again (176-178), we can compute the rate of x(122 defined in eq. (21), as n + oo:
x(v2)= (12)
nt 90 (12 11)0 (1 n 90 (D2 v))
p - (v2))
=n 40 1/2 1111
Using the integral approximation given in (173), one could verify that (12) = O(p) for any choice of l and q. The deterministic equivalent for the bias term, given in eq. (22). can be written as
Bn,p (B,, A)
+ x(P2)
(181)
1- T-VT,,, v2)
0 (12) O 1/2 ((r-11))
+ 9 1- 1/o (2r-
(182)
0 ( ( 2(r1)) + //
(183)
where we have used (175) to compute the scalings of the terms T T and the fact that - (V1, U2) O(1).
From eq. (183), and using the result (177), it straightforward to that the decay rate of the bias term is given by
2a [ ( ( (r (nau] (AAA))(AA)]])))
a [[2a (r (ra2) - (2((Ann +9]
7'
(184)
Examples of the results of Theorem 4.1 and Corollary 4.2 shown in Fig. and 9,
52

---

10
5w3.0 84, 04.0- 0.96
f-6-
10"4
2-055
Q=0.55
10
(optima)
Figure 9: Excess risk eq. (6) of random features ridge regression function of the number of samples n under source and capacity conditions eq. (37) and power-law assumptions À n (f-11) p = n1, with noise variance o² = 1, obtained from the deterministic equivalent Theorem 3.3. Dashed and dotted lines are the analytical rates from Theorem 4.1, stated in the legend. The colour scheme is following: variance dominated region: orange and brown the slow decay regime; cyan for bias dominated region; shades of green for the optimal decay (red lines in Fig. (right). In particular we show: (left) the crossover between the orange and teal regions in Fig. 2 at fixed regularization and 1/2: (right) the optimal decay rate along the horizontal red line line in Fig. q q. and
r < 1/2, for any X. included the non regularized case.
D.3 Details of Remark 4.1
In order to extend the results of Theorem 4.1 and Corollary 4.2 to the excess risk defined in (6), in this section compute the intervals for E and such that the assumptions of Theorem 3.3 hold and the approximation rates E(n, p) are vanishing, under source and capacity conditions.
Given n, = n2, (-(1-) and Us as in (177) assumption 3.2 is verified for m = not4 and C. = Ovv5 ). In fact
(m + 11)
a
(185)
k=m+1
m+1
and the inequality in (16) holds if
24 m + 1)-a < n (m ++ 1)
> n 1)
(186)
The inequalities in (17) be written
C. T:0 (12) O(1)
(187)
T2 (p2)
T1 (12)
C, 2 U/ Ty 2r (12)
(v,
((0v(2r ((VV()--
(188)
53

---

Then, introducing nh E (0, 1/2). we can compute the following quantities of interest (introduced in eqs. (25) to (27)):
Tr 21 +1)
r2(( k]]=
O(
kJ]) =k()
(189)
|| ووا 22 llop
My(k) = 1 + x2 [1 k]) Vk
k
log (r k]] V k) = + Ollog kt)
(190)
h
p-
fm pl Mx(() 11
n2(2-a) log
Pk(()) = 1 +
(191)
K
16
n22
} Mz(r)
(n = =1+ 1[n S <p/n,l
+- n
(192)
p
"2n 1/1- +)
nn'aa
1 1 1 2 110
logn)
(193)
xi
Similarly, considering 1/1 scaling as in eq. (176), we have that eq. (31)
7A- pd
S =0 =0000==0000000000 (
(194)
k=m+1
2 = 0 (1/4 2 1]n0 (era) + 1/g < 1|n + +((0+0)(1-0))
74
pvl +
(195)
k=++1
= 0 (100 2 1| (ena) + 1
(-saa
8 1 a) s sy< n g- +1 1
q < (2 - a))
n(0+0)(1a))
a
(196)
The last step is a consequence of
q- (eA > (1+ - -a) = 9> - (1
l
A1)
a)
+
(197)
a
<0
l (2 ac)
q ( 0) - a) - q >
(198)
a
Fixing K >>0 0 and considering the we consider condition (28): 22n nーー ls
(199)
( (1+K)
E g(+ aa)
22 2 p-k K
(200)
q (2-08
q 12-0] g
a aa tt)
px(n.p)5/2 5/2 log (n) S KVnn = l> 1(9 2 1|
(201)
and, similarly, condition (29) is satisfied if, for q 2 1
(1+0 a logn))² (0 [1 n (ena) (0gg)))))0)) 8 "log" n S Kn 2/2
))
(202)
2) v0 3/2 = 1 <<> +a,
(203)
while, for q < if
1 1>1 2 L22 a))
v {q 5 a)
V (1+0 (nt()-111) (1+ "log* n S Kn
(1+0 (n ))²² q glog* n S Kn
(204)
11 92 12
q < [ a)
V
(205)
l < aq + 1
[e < 16(a-1)
((+ 1
-l<
v
4
(206)
16
16(a - 1)
54

---

where the last step is consequence of This work
Bahri al. [2024]
Maloney al. [2022]
Atanasov al. [2024]
Input dimension
d
d
M
D
Number of features
p
N
Number of samples
n
D
T
P
Capacity
a
+ ō
1 + ā
a
Source
r 1/2 1/(a+1)) + 1/2 1/2 + aa
1/2(1 1/(+1)) 1/2 + a)
r
Target decay (in L2)
or + 1/2
Table I: Dictionary of notation between the source and capacity conditions defined in eq. (38) and the scalings in different neural scaling laws works. Note that since Bahri et al. [2024], Maloney et al. [2022] also employ the greek letter "a", we denote theirs by â to avoid confusion.
1
15 + v553
2 I a
+
for a 2 a ==
2 1.05588,
(207)
16
16(a 1)"
32
1
a+
for < a.
(208)
2 a
16
16(a= 1))
Finally, the approximation rate defined remark 4.1
E(n,p) = (n- + 1/ 2 1jō (=())-a))1))) +
(209)
nn- + 1[g 1 (n2((-0)~0/3 ) (1 δ nn (=(01-a))
(210)
where the second term vanishes under the conditions in (203) and (206), and the first term vanishes by further assuming, for q 2
<< a<a+ 1
(211)
12
E Comparison with neural scaling laws
In this appendix we discuss the relationship between our results and the recent literature of the theory of neural scaling laws with linear models. We adopt notation close to ours, with dictionary to their notation given in Table and Table 2.
Bahri et al. [2024] and Maloney et al. [2022] have considered a model where with Gaussian input data and linear target function:
fa(;;) (G,,
2; (0,0 A),
E [n]
(212)
The covariance matrix A power-law scaling:
is taken be diagonal, with eigenvalues following
d
d
k e [d]
(213)
with a and the target weights are assumed be random Gaussian vectors B, (0, 1/ala). In particular, note that TrA ~ d for d + xo. Given the training data, they consider least-squares regression in the class of linear random features predictor:
f(x; a) (a, W
(214)
where W E R is a Gaussian random matrix elements in NN 1/laa)
2 a 1/10, both inequalities (199) (200) are satisfied. In [Maloney et al., 2022], 33, has variance a//a, the spectrum has a scale X_ and the random projection W has variance dn/d. Here take aw X_ au since it is irrelevant the discussion.
Under this condition,
55

---

This work
Bordelon al. [2024]
Lin al. [2024]
Paquette al. [2024]
Input dimension
d
D
d
v
Number of features
p
M
Number of samples
n
P
N
Capacity
a
b
a
20
Source
r
(a- (a-1)/2 11/26
(b-1) 11/2
(2x
1//4
larget decay (in L2)
+ 1/2
0/2
1/2
+ 3
Table 2: Dictionary of notation between the source and capacity conditions defined in eq. (38) and the scalings in different neural scaling laws works. Note that since Paquette et al. [2024] also employs the greek letter "a", we denote theirs by ā to avoid confusion.
This setting is particular case of the one introduced in Section 2. In particular, it satisfies particular source and capacity conditions eq. (38). see this, note that the feature population covariance is identical to the input data covariance:
E W aa W [ = 1/4A
(215)
Therefore, can identify Σ 1/aA which has TrΣ < oo for 1 in the limit d - Therefore, the features satisfy capacity condition with scaling a. Moreover, the asymptotic kernel is simply the linear kernel:
K<x, x²) Ew (ww, æ)) (wx, .²)] (ar, Since the target variance is constant, this equivalent to source condition with:
(216)
d
2211-11 11-11 ax
(217)
2
Since a E oo), we are always in the hard regime r E (0, 2/2) where the target does not belong to the RKHS H Rd. Indeed, since 3_ No0 1/ala), we have:
d
Σ S da
(218)
which indeed diverges as d + oc. Moreover, note that least-squares regression correspond to the case DO.
From the discussion above, the bias term scalings from Bahri et al. [2024] (resolution limited regime)
and Maloney et al. [2022] (underparametrizeed regime > p. i.e. q and overparametrized regime n & p. i.e. >> 1), correspond to a vertical cross-section on the large l region of Fig. (Right). Indeed, we recover exactly the rate of the label term in eqs. (167)-(168) of Maloney et al. [2022]:
B(f..X, W, E,, = =0 -2-rrr) =0 (p-(a-1)
n >>>> P.
(219)
B(f., X, W. E, A) O (n (a-2aa)) 0 (a-(a-1)
n p.
(220)
Similarly, is possible recover the rates for the noise term (first results in eq. (86) of Maloney et al. [2022]) as the vertical cross-section on the large E region of Figure for the rates of the variance term. particular:
A) 10 (o - (1-0)) (o??) n>p
10
V(S., X, e,
10 (0 (o2 p p>n n
(221)
Comparison with the SGD rates from Paquette et al. [2024], Lin et al. [2024] Furthermore, in the linear noiseless target setting, lifting the condition eq. (217), possible to compare our results to the compute-optimas rates for the risk obtained through stochastic gradient descent in Paquette et al. [2024]. In particular, we consider unitary batch-size and the correspondence between the number of iterations of stochastic gradient descent and the number of samples n in ridge regression. Then, defining Ý the decay rate of the compute-optimat curves for the risk R x in Paquette et [2024], corresponding to the compute-optimal number of features p x p =: n
'Note that this quantity is denoted d, in Paquette al. [2024].
56

---

coincides with 7s(e 1. g) in Theorem 4.1, i.e. with fixed regularization parameter À = 1 (E = 1).
In particular, consider the following regions in the phase diagram provided in their work:?
Phase la (r 1/2):
② =
(222)
9 = 2r 2adr = (B(1, 9):
(223)
Phase II (r > 1/2 and < 1 1/20 < 1):
0 == + 20r - a < 1,
(224)
2r a
q = (1.
(225)
Phase IIII (r > 1/2 and
1 1/2a):
i = 1
(226)
2a 1
a +==7B((.1
9 a
(227)
a
We emphasize that, in Phases la and II, f = max, Ys (1. while, in Phase III. 9 S max, 7B 7s q). Hence, the compute-optimal decay rate of the risk for stochastic gradient descent is equal or smaller than the largest rate achievable by RFRR with fixed regularization À = and therefore always smaller than the optimal one in Corollary 4.2.
similar setting has been investigated by the recent work Lin et al. [2024], providing scaling laws for the excess risk obtained by stochastic gradient descent with stepsize schedule 17: -1/2" log n/nn for t == I,... n. Under the same source and capacity conditions, assuming r E (0, 1/2) and 17 ( the result in their Theorem 4.2 may be rephrased as follows:
Ex R(f.R X, W, E, 17) x n (1.P)))))))
(228)
logn " + 1llo
1
1 logn A logn p1 ))
>SGD(1.P) = 2ar
A logn
A
(229)
a
Hence, choosing p x n and 7 x n² i.e. x-1 provided 17 O(1) f< 1, this result recovers precisely the same rates as in our Theorem 4.1.
"The Phases lb, and correspond to i.e. to an activation o & L2. 'The stepsize in Lin et al. [2024] is denoted by the greek letter 7, which we changed to to avoid confusion with the symbol use for the risk decay rate.
57

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All claims in the abstract and introduction are supported by mathematical proof' numerical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: All mathematical proofs include clear assumptions reflecting the scope of applicability. Numerical results are replicated for different data sets and choices of feature maps.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
58

---

Answer: [Yes]
Justification:
Clear assumptions are provided in an "assumption environment".
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We have included detailed discussion of how all the numerical experiments were conducted in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
59

---

reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: We judge the code is too simple to be released, and that we give enough information for the reproducibility the numerical plots. All data sets used in the numerical experiments are either synthetic or open source.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/CodeSubmissseeeeee //niss... wwtpcc/ppplccccceeeccc haabli//guiddes/oddeubbiiii onnooiccy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permirted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have added detailed discussion of the experiments in the captions and in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: The numerical agreement between theory and experiments good that error bars are unnecessary.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
60

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: The experiments are simple illustrations of the theorems. They are simple
enough to be ran on a standard laptop in a few hours.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: bttt:::///eurrppte httppp..cccpbbllp cc/public//eieecccccccccccc Ceeeiic///iiiieeeeeeeeeeeeeee csGuidelines"
Answer: [Yes]
Justification: This work is of theoretical nature, and therefore has major ethical implica- tions.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: impacts.
This work is of theoretical nature, and therefore has no relevant socictal
Guidelines:
61

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This work is of theoretical nature, and therefore has risk of misusage. Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All resources used from other works are properly acknowledged.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
62

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswitae thode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets introduced in this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This work does not involve crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector:
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This work is of theoretical nature and does not have potential risks to the people involved.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
63

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
64


Reviews:
[{"review_id": "W6KsG6JqN0", "reviewer": "Reviewer_b7dx", "summary": "The paper studied the non-asymptotic generalization error for random feature ridge regression (RFRR) models. By considering the eigendecomposition of random features with respect to data distribution and weight distribution, the authors proved a feature-dimension-free deterministic equivalence for the generalization error of RFRR, where the sample size and number of features bound the approximation error. From this deterministic equivalence, fixing the number of data points, this paper presented the minimal number of features for the optimal decay rate of the excess risk of RFRR when considering power law assumptions for data covariance and target. This analysis provides a clear picture of the generalization error scaling law for source and capacity conditions of RFRR.", "questions": "1.  In the simulation, the authors provide an empirical diagonalization method for estimating $\\Sigma$ and $\\beta$ by considering $N=P\\gg n,p$ and computing the eigendecomposition of the empirical feature covariance. Is there any theoretical guarantee for this approximation? This approximation seems to indicate that we can still apply the asymptotic results for empirical feature covariance under the proportional or polynomial scaling regime for $n, p$, e.g. [Mei and Montanari, 2022, Gerace et al., 2021, Dhifallah and Lu, 2020, Hu and Lu, 2023, Hu et al., 2024], to analyze the deterministic equivalence and the generalization errors. \n\n2. In (10), do you need to assume the subsets $\\mathcal{X}$ and $\\mathcal{W}$ in $\\mathbb{R}^d$ are compactly supported?\n\n3. Typo (7): $h_*\\to f_*$\n\n4. What is $\\nu_2$ in (17) in Assumption 3.2? You did not introduce this notation until Definition 1.\n\n5. You did not introduce intrinsic dimension around (25).\n\n6. In line 147, why do you assume assumption 3.2 again?\n\n7. Line 183, typo: spam; Line 230: (37) $\\to$ (38)?\n\n8. In Definition 3, typo in the definition $r_\\Gamma(k)$: $p \\to q$. Line 546, $\\Sigma\\to \\Gamma$.\n\n9. In Theorem A.2, what is the typical order of $\\rho_\\lambda (n)$? From (53), we cannot claim the error term in (54) will be vanishing.\n\n10. How do you prove the last equation on page 16, for the upper bound the $||S_i||_{op}$? Can you explain it? And in the same proof, how do you apply the matrix Bernstein inequality for infinite dimension $\\tilde S$?\n\n11. Below Line 587, typo in $f_j$: $j\\ge 1\\to k\\ge 1$; typo in (60): $A\\to B$.\n\n12. In Line 634, you consider $\\eta_*\\in (0,1/4)$ but in the main results, you have $\\eta_*\\in (0,1/2)$. Can you clarify it?\n\n13. How do you prove $||\\hat \\Sigma_F||_{op}\\ge 1/2$?\n\n14. Below Line 800 and in Line 1033, you use $G$ to denote the resolvent which has been used as the data feature matrix as well.", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-motivated, and the mathematics appears correct to me. The writing is clear, and the authors do a good job of presenting results with many discussions and comparisons of related works.  \n\n2. The authors provide various empirical simulations to justify the theorems, including random synthetic data, real-world data, random weights, and weights trained by gradient descents. This offers more insights into theoretic results and the generality of the results in this paper.", "weaknesses": "1. One concern is how we can check Assumptions 3.1 and 3.2 for specific nonlinear feature models with some concrete data and weight distributions. The results of this paper rely on the eigen decomposition in (11) but can we get some specific examples of eigenvectors $\\psi_k$ and $\\phi_k$? For instance, in a classical high-dim statistics setting, if we consider a nonlinear RFRR model with i.i.d. sub-Gaussian dataset and weight matrix and a certain nonlinear teacher model, can we justify Assumptions 3.1 and 3.2 in this case?\n\n2. There should be more clarification for the notations and conditions of the main results, Theorem 3.3. For instance, what would be the meaning of (25-27) and (28-29)? Are these bounds and approximation rates necessary or due to some technical reasons? If we apply the bounds in (28-29) to (32) for the error bound of the deterministic equivalence, the bound of $\\mathcal{E}(n,p)$ seems to be loose and cannot get $\\tilde O(n^{-1/2}+p^{-1/2})$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation of our work and for the suggestions which will help improving it. The typos raised (2, 5, 6, 7, 8, 11, 14) will be corrected in the revised version of the manuscript. \n\nBelow, we address the other specific comments and questions.\n\n> \"*One concern is how we can check Assumptions 3.1 and 3.2*\"\n\nPlease see general rebuttal. \n\n> \"*[... ] the bound of $\\mathcal{E}(n,p)$ seems to be loose and cannot get $\\tilde{O}(n^{-1/2}+p^{-1/2})$*\"\n\nThe bounds in (28-29) are technical conditions used in intermediate steps of the proof to ensure the multiplicative bounds. If conditions (28-29) are verified, then the approximation guarantee (30) is satisfied with $\\mathcal{E} (n,p)$ rate given in (32). Conditions (28-29) are not meant to ensure that $\\mathcal{E}(n,p)$ is small, but that the bound (30) holds (and indeed, $\\mathcal{E}(n,p)$ might not be vanishing).\n\nThe conditions (28-29) and rate $\\mathcal{E}(n,p)$ depend explicitly on $n,p,\\lambda,\\Sigma$ and should be applied to specific settings. We will add the details of how to compute these bounds in the case of source and capacity conditions in Corollary 4.1., to illustrate the use of this theorem (and provide a full proof of Remark 4.1).\n\nSome dependency in $\\Sigma$ and $\\lambda$ in the multiplicative bounds are unavoidable, and therefore are not technical. However, in most relevant examples (e.g. regularly varying spectrum), $\\rho_\\kappa (p)$ and $\\tilde \\rho_\\kappa (n,p)$ will be of order $\\log (\\max (n,p))^C/\\kappa$, and $\\mathcal{E} (n,p)$ will indeed be of order $p^{-1/2} + n^{-1/2}$ up to log factors. We further believe that the dependency on $\\lambda$ could be improved, at the cost of a worst dependency $p^{-c} + n^{-c}$, $c <1/2$, and further assumptions (see for example [Cheng, Montanari, 2022]). We will add this discussion to the revised version.\n\n> \"*Is there any theoretical guarantee for this approximation?*\"\n\nFirst, we would like to clarify that Figures 1 and 2, 5, 6 are intended as an illustration of the scope of the theory to settings that might go beyond the technical assumptions. The ``empirical diagonalization'' procedure is therefore only a tool to obtain the spectrum in cases which it is not available analytically (e.g. real data), and has been inspired from other works in the literature, e.g. [Bordelon et al., 2020; Loureiro et al., 2020; Simon et al., 2023a].\n\nIndeed, when estimating the spectrum empirically  the quality of the theoretical predictions will depend on the choice $N,P$. The convergence rates for the empirical estimation of the spectrum were studied in [Koltchinskii and Giné, 2000; Braun, 2006], and in the worst-case are given by the usual CLT rates. In practice (e.g. Figs. 1 and 2), we observe that $N,P = 10^{4}$ was enough for a very good agreement with finite size simulations in the range of $n,p$ considered.    \n\nHowever, it is important to stress that this is unrelated to the proportional asymptotics (after estimating $\\Sigma,\\beta_*$, we use the deterministic equivalents in Definition 1). It just implies that to go to larger $n,p$ (e.g. a polynomial scaling) ones requires a finer estimation of the spectrum. \n\n-[Koltchinskii and Giné, 2000] *Random matrix approximation of spectra of integral operators*.\n    \n-[Braun, 2006] *Accurate error bounds for the eigenvalues of the kernel matrix*.\n\n> \"*In (10), do you need to assume the subsets $\\mathcal{X}$ and $\\mathcal{W}$ in $\\mathbb{R}^{d}$ are compactly supported?*\"\n\nWe introduce an abstract random feature model $\\varphi : \\mathcal{X} \\times \\mathcal{W} \\to \\mathbb{R}$, but we only require that it is diagonalizable. It is sufficient for $\\mathcal{X}$ and $\\mathcal{W}$ to be Polish probability spaces and $\\varphi$ to be square integrable, so that $\\varphi$ is diagonalizable (by the spectral theorem of compact operators). For Theorem 3.3, we only use Assumption 3.1 that is an assumption directly on the eigenfunctions of the activation.\n\n> *What is $\\nu_{2}$ in (17) in Assumption 3.2? You did not introduce this notation until Definition 1.*\n\nIndeed, the parameter $\\nu_2$ is the solution of (23) in Definition 1. Following the reviewer's remark, we will move Assumption 3.2 after Definition 1 in the revised version.  \n\n> \"*In line 147, why do you assume assumption 3.2 again?*\"\n\nThis is a typo. Thank you for pointing it out!\n\n> \"*In Theorem A.2, what is the typical order of $\\rho_{\\lambda}(n)$? From (53), we cannot claim the error term in (54) will be vanishing.*\"\n\nFor most cases of interest, $\\rho_{\\lambda}(n)$ will be of order $\\log (n)^C/\\lambda$ (see response above). We further insist that these bounds are non-asymptotic (they depend explicitly on finite $n$) and do not need to be vanishing: if they are equal to $1/2$, it is enough to pinpoint the scale of the functionals.\n\n> \"*How do you prove the last equation on page 16? How do you apply the matrix Bernstein inequality for infinite dimension $\\tilde{S}$?*\"\n\n$||S_i|| = ||x_{+,i}||^{2}=  x_{+,i}^T I x_{+,i}$. We can therefore apply Assumption A.1 with $A= I$ and do an union bound on $i \\in [n]$, which results in the $\\log(n)$ factor.\n\n$S_i$ can be seen as a trace class operator, and many tools from matrix theory extend to this setting. The matrix Bernstein inequality only depends on the operator norm and the intrinsic dimension of the matrix, and not on the size of the matrix,  and  its proof extends to infinite dimensional operators. See for example [Rudi, Rosasco, 2017] and references therein.\n\n> \"*In Line 634, you consider $\\eta\\in(0,1/4)$ but in the main results, you have $\\eta\\in(0,1/2)$?*\"\n\nThis is a typo. Thank you for pointing it out!\n\n> \"*How do you prove $||\\hat{\\Sigma}||_{op}\\geq 1/2$*\"\n\nIn the proof in section B.7.1, we have $|| \\hat{\\Sigma} || \\geq || F_1 F_1^T /p || $ and by equation (124), we proved that the top eigenvalue of $F_1 F_1^T /p$ (i.e., $k_1 = 1$) is lower bounded by $\\hat \\xi_1^2/2$, where $\\hat\\xi_1^2 = || \\Sigma || = 1$ by assumption.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bKrJbWNrVD", "reviewer": "Reviewer_tRLP", "summary": "Prior work on random feature (ridge) regression study the test error in the high-dimensional asymptotic. However, ideally one would hope for a non-asymptotic deterministic characterization of the test error.   In this paper, the authors tackle this problem and show that under a concentration assumption,  the test error is well approximated by a closed-form expression that only depends on the feature map eigenvalues. They use this result to study various problem in random features regression.", "questions": "The paper is very well written and I have no particular question.", "limitations": "The authors have adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- This paper rigorously solves an important problem in the analysis of random features regression. I think Theorem 3.3 will be of independent interest as well.\n- The main result of the paper does not require the random regression coefficient assumption and hold for deterministic beta_star.\n- Theorem 3.3 has a very clean form. The bounds in Theorem 3.3 are multiplicative. Thus, they scale correctly with the risk. Taking particular limits (e.g., p \\to \\infty or \\lambda \\to zero), we easily recover already known phenomenon.\n-  The authors derive sharp excess error rates under power-law assumptions and provide a tight result on the smallest number of features needed to achieve optimal minimax rate.\n- The proofs seem correct and rigorous.\n\nAll in all, I really enjoyed reading this paper and I recommend acceptance.", "weaknesses": "I suggest the authors expand the discussion around Assumption 3.1 and provide more detailed examples for which this assumption holds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation of our work and for the suggestion which will help improving it. \n\n\n> \"*I suggest the authors expand the discussion around Assumption 3.1 and provide more detailed examples for which this assumption holds.*\"\n\nWe will expand the discussion around Assumption 3.1 (see the general rebuttal for a discussion).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tvq8ByzMjg", "reviewer": "Reviewer_Gqjy", "summary": "EDIT: updated my score after rebuttal. \n\nThe authors investigate the excess risk in random feature ridge regression. They give a deterministic expression that approximates the excess risk, with a controlled relative error. The dependence of the deterministic \"equivalent\" w.r.t. to key quantities in the problem is examined.", "questions": "* Item 4 in my major comments.", "limitations": "This is fundamental work and does not have any immediate potentially harmful impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* Understanding the generalization ability of simple models is important, especially as our intuition of generalization has been challenged by recent results on overparametrized neural networks. Therefore, the paper is potentially impactful. \n* The proposed result generalizes and refines a string of previous results in a single deterministic equivalent, and the dependence of this equivalent to problem parameters yields interesting conclusions, e.g. on the minimal number of features needed to achieve a statistically satisfying rate.\n* There is clearly a lot of work that has gone in obtaining such a general result.", "weaknesses": "## General comments\nMy main concern is the format of the paper, which I think is more suited to a mathematical-minded ML/stats journal than a conference. The main paper is very dense but misses key details such as proofs or proof outlines, while the full proof of the main result is 28 pages long, which makes the full paper 50 pages long (i.e., appendices included). It is not reasonable to expect reviewers to go through such a long technical proof in the context (short time span and heavy workload) of NeurIPS reviews. As a journal submission, I would have the time required to go through the proofs and get to the heart of the proposed (interesting) result. \n\n## Major\n1. Eqn 4: don't you want $\\epsilon$ to be zero-mean as well?\n2. p3 L104; \"we define wlog $\\mathcal{V} = Im(T)$\": if this is indeed a definition, I don't see why we need to add \"wlog\". If this is a statement about the image of $T$ being the whole of $\\mathcal{V}$, we need to define $\\mathcal{V}$ beforehand.\n3. Eqn 13 is only true in $L^2(\\mu_x)$ so I would avoid involving $\\mathbf{x}$ in the statement of the equation, which suggests you mean a pointwise equality and requires a quantifier. If you actually meant a pointwise equality, then this should be explained, and further assumptions should likely be made on $\\varphi$.\n4. Assumption 3.1. I am unsure what is meant by an infinite matrix $A$. Especially when one needs to talk about the trace of $\\Sigma A$, so that I assume we want to guarantee that $\\Sigma A$ is a trace-class operator. Can you rephrase the assumption in terms of operators? \nSimilarly, the Frobenius norm for operators should be defined. \n5. p4 L117: can you give more details on why cases 1) and 2) are covered by your assumption? Same for p4 L128: can you detail why these power decays satisfy Assumption 3.2?\n6. Definition 1: For easier reading, I would define $\\nu_1, \\nu_2$ first, then $\\Upsilon$, and then only $B$ and $R$. Otherwise, the reader has to wait until Eqn (24) to understand Eqn (18), which requires a lot of buffer memory from the reader's brain.\n7. p5 L156 is there an implicit dependence on the feature map dimension? Can you explain where? \n8. Figure 1: I would keep the caption short and descriptive, and move the definition of the data generating process to the main text. This would allow to explain more, for instance, what you mean by $v$ has a fixed overlap with the teacher vector\".\n9. The bibliography needs to be harmonized. There are many missing journal/conference names (if it's an arxiv preprint, say so and give the arxiv number), and a few initials mixed with full first names.\n10. p9 A short discussion section summarizing the main points and limitations of the paper would be a good addition.  \n\n## Minor\n* p1 L23: here and in the rest of the paper, you use the notation $\\mu_w(\\mathcal{W})$ to indicate that $\\mu_w$ is a probability measure on $\\mathcal{W}$. I would say that is not standard notation, and I would rather keep $\\mu_w(\\mathcal{W})$ for the measure of the whole space $\\mathcal{W}$, i.e. 1. \n* p1 L25: I think $\\sigma$ has not been defined yet.\n* p2 L46 \"demystifying phenomena such as double descent and benign overfitting\". I would give a reference for each concept.\n* p2 L55 no need to boldface \"our main contributions\".\n* Eqn 9: I would write $\\mathrm{Var}$ instead of $\\mathrm{Cov}$.\n* p4 L127: settings\n* p4 L135: what is a \"self-consistent\" equation?\n* p5 L142 \"we use $a_i = '*'$ to denote [...]\": I don't understand the exact meaning of this statement.\n* Eqn 30: I would remind the reader that $R_{n,p}$ has been defined in Definition 1.\n* p5 L151 \"in place\" reads strangely. \"In order\", maybe?\n* p5 L152 what does \"fully\" mean in \"fully non-asymptotic\"?\n* p6 L171 what do you mean by \"single-index\"?\n* p6 L183 span, not spam!\n* p6 L183 infinite-dimensional\n* p7 L216 understanding\n* p8 L255 decays\n* Figure 3 is too small to read.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation of our work and for the suggestions which will help to improve it.  The issues (9, 10) and the typos raised in the minor comment section will be addressed and/or corrected in the revised version. Due to the space constraint in the rebuttals, will answer your questions in the \"Minor\" in a comment.\n\nBelow, we address the \"General\" and \"Major\" comments and questions.\n\n> *My main concern is the format of the paper, which I think is more suited to a mathematical-minded ML/stats journal than a conference.*\n\nRandom feature is a major research topic for the theory community at NeurIPS, with many papers about it every year. Our work is in direct dialogue with previous NeurIPS works, e.g. [Rahimi and Recht 2007, 2008; Rudi and Rosasco 2017; Cui et al. 2021; Xiao et al., 2022], and therefore our choice of venue simply reflects the interest we believe our results can rouse in this community. \n\nMoreover, the main message of this work is simple, and we believe is well conveyed in 9 pages: we derive a deterministic, non-asymptotic characterization of the test error which generalizes previous results and can be used to derive new insights, such as the different power-law scalings of interest to both the kernel and neural scaling law communities. Indeed, due to the generality of the results the proof involve long and technical arguments with are left in the Appendix, but we politely disagree that this stands out from the NeurIPS practice, see e.g. proofs in the Appendices of [Rudi and Rosasco 2017; Loureiro et al., 2021; Xiao et al., 2022].\n\n> *Eqn 4: don't you want $\\epsilon$ to be zero-mean as well?*\n\nIndeed, the noise is intended to be zero-mean. We will explicitly state this assumption in the revised version of the paper\n\n> *p3 L104; \"we define wlog $\\mathcal{V} = {\\rm Im}(\\mathbb{T})$ \": if this is indeed a definition, I don't see why we need to add \"wlog\". If this is a statement about the image of $\\mathbb{T}$ being the whole of $\\mathcal{V}$, we need to define $\\mathcal{V}$ beforehand.*\n\nIndeed, we will remove ``wlog'' here, as we simply define $mathcal{V} = {\\rm Im}(\\mathbb{T})$.\n\n> *Eqn 13 is only true in $L^2(\\mu_x)$*\n\nFollowing the reviewer's suggestion, we will avoid any ambiguity by rewriting $f_\\star = \\sum_{k\\geq 1}\\beta_{\\star,k}\\psi_k$ in the revised version.  \n\n> *Assumption 3.1. I am unsure what is meant by an infinite matrix $A$.\n\nThe matrix notation $A\\in\\mathbb{R}^{\\infty\\times\\infty}$ is here used to represent a linear operator $A$ acting on an infinite-dimensional Hilbert space $\\mathcal{H}$. In particular, given a basis ($\\psi_k$) of $\\mathcal{H}$, we define the $kk'-$th element of $A$ as $\\langle \\psi_k, A \\psi_{k'}\\rangle_{\\mathcal{H}}$. The expression $Tr(\\Sigma A)<\\infty$ ensures that $\\Sigma A$ is trace-class, as correctly stated by the reviewer. More generally, the infinite dimensional matrices that appears in the paper (e.g., $\\Sigma$, $F^T F$, or $ff^T$) are understood to be linear operators $\\mathcal{H} \\to \\mathcal{H}$. \n\nFollowing the reviewer's suggestion, we will rephrase Assumption 3.1 in order to improve its clarity and add a remark on our notations in terms of linear operator for completeness.\n\n> \"*p4 L117: can you give more details on why cases 1) and 2) are covered by your assumption? Same for p4 L128: can you detail why these power decays satisfy Assumption 3.2?*\"\n\nAssumption 3.1 is a slight relaxation of Hanson-Wright inequality, which is satisfied by 1) and 2), see [Adamczak, 2014] (note that the inequality is stated in finite dimension, however it also holds for $d = \\infty$, as noted in Remark 2.1 in [Cheng, Montanari, 2022]).\n    \nConcerning the second part of the question, we consider the power decays $\\xi_k^2 \\asymp k^{-\\alpha}$ and $\\beta_{\\star,k}\\asymp k^{-\\beta}$. Since we are considering square-integrable target function and feature map, we have that $2\\beta, \\alpha > 1$. \n    \nWe notice that:\n$$\n    \\sum_{k={\\rm m}+1}^\\infty \\xi^2_k >  \\int_{\\rm m+1}^\\infty x^{-\\alpha} = \\frac{({\\rm m}+1)^{1-\\alpha}}{\\alpha - 1}\n$$\n    and the inequality in (16) holds if\n$$\n    p^2({\\rm m}+1)^{-\\alpha}\\leq \\frac{p\\lambda}{n}\\cdot\\frac{({\\rm m+1})^{1-\\alpha}}{\\alpha - 1} \\implies {\\rm m} \\geq \\frac{pn}{\\lambda}(\\alpha - 1) - 1.\n$$\n    The inequalities in (17) may be written as\n$$\n        \\frac{\\sum_{k\\geq 1} k^{-\\alpha}(k^{-\\alpha} + \\nu_2)^{-1}}{\\sum_{k\\geq 1} k^{-2\\alpha}(k^{-\\alpha} + \\nu_2)^{-2}}\\leq C_*, \\qquad \\frac{\\sum_{k\\geq 1} k^{-2\\beta}(k^{-\\alpha} + \\nu_2)^{-1}}{\\sum_{k\\geq 1} k^{-2\\beta}(k^{-\\alpha} + \\nu_2)^{-2}}\\leq C_*.\n$$\n    Therefore, by applying the integral test for convergence, it is easy to show that all the series involved in the inequalities are bounded by a positive constant term dependent on $\\alpha, \\beta, \\nu_2$ (where the latter depends itself on $\\alpha, \\beta$ and $n, p, \\lambda$). For instance \n$$\\sum_{k\\geq 1} \\frac{k^{-\\alpha}}{(k^{-\\alpha} + \\nu_2)^{-1}} < \\int_{0}^\\infty \\frac{x^{-\\alpha}}{(x^{-\\alpha} + \\nu_2)^{-1}}{\\rm d}x = \\nu_2^{-1/\\alpha}\\frac{\\pi}{\\alpha}\\csc\\left(\\frac{\\pi}{\\alpha}\\right) =: C_{\\alpha,\\nu_2}.$$\n\n[Adamczak, 2014] *A note on the Hanson-Wright inequality for random vectors with dependencies.*\n\n> *Definition 1: For easier reading, I would define $\\nu_1,\\nu_2$ first, then $\\Upsilon$, and then only $B$ and $R$.*\n\nWe thank the reviewer for raising this issue, which will be addressed in the revised version of the paper.\n\n> *p5 L156 is there an implicit dependence on the feature map dimension?*\n\nIndeed, this remark is confusing and we will rephrase it. There is no dependency on the feature map dimension. The covariance $\\Sigma$ might depend indirectly on the feature map dimension (however the key quantity is the intrinsic dimension $r_\\Sigma$ and our results hold for infinite dimensional feature maps).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RC7NfFodto", "reviewer": "Reviewer_gFLF", "summary": "This paper provides a non-asymptotic bound (Theorem 3.3) on the test error of random feature ridge regression (RFRR) using dimension-free (in the sense of the feature space) deterministic equivalents, which are the solutions to some self-consistent equations, under a concentration assumption (Assumption 3.1) on the features. As a result, they recover (Corollary 3.5) the deterministic equivalents result on the test error of kernel ridge regression (KRR) from previous literature, and they prove the exact decay rate of the neural scaling law (Corollary 4.1), filling the gap from previous literature.", "questions": "Regarding the above comments, \n\n1. Could the authors explain more how different it is to implement the deterministic equivalents techniques in RFRR than in KRR?\n\n2. How difficult it would be to relax Assumption 3.1 as in [Misiakiewicz2024]? And what datasets and random feature model could satisfy Assumption 3.1 empirically?\n\n3. Despite not essential, but it could help the readers a lot if the authors could explain more on the quantities and their intuitions in the paper, like Eq (21-27). From my point of view, Theorem 3.3 is not the easiest to read.\n\nBesides the questions, I found some potential typos in the appendix:\n\n- A paragraph (line 536 - 540) seems misplaced: they should be directly after Eq (50). \n\n- The equation below line 587 should be $\\mathbf{f}\\_j = ((\\xi\\_k\\phi\\_k(\\mathbf{w}\\_j)))\\_{j\\geq1}$ instead of $\\mathbf{f}\\_j = ((\\xi\\_k\\psi\\_k(\\mathbf{w}\\_j)))\\_{j\\geq1}$. \n\n- a ``\\rangle`` is missing in the equation under line 590: it should be $\\sigma(\\langle \\mathbf{w}\\_p,\\mathbf{x}\\_i \\rangle)$ instead of  $\\sigma(\\langle \\mathbf{w}\\_p,\\mathbf{x}\\_i )$.", "limitations": "This paper is theoretical paper and the authors have addressed the assumptions and conditions explicitly in the paper.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "This paper improves the results from previous literature in multiple ways: non-asymptotic over asymptotic bounds [Loureiro2022], RFRR over KRR [Misiakiewicz2024], more precise neural scaling law [Rudi2017, Cui2022]. The phase diagram (Figure 2) is novel, as far as I know, and it offers great insights for the test error in RFRR. \n\nReference:\n- *Bruno Loureiro, Cédric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mézard, and Lenka Zdeborová. Learning curves of generic features maps for realistic datasets with a teacher student model. Journal of Statistical Mechanics: Theory and Experiment, 2022(11):114001, nov 2022.*\n- *Theodor Misiakiewicz and Basil Saeed. A non-asymptotic theory of kernel ridge regression: deterministic equivalents, test error, and gcv estimator, 2024.*\n- *Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.*\n- *Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization error rates in kernel regression: the crossover from the noiseless to noisy regime. Journal of Statistical Mechanics: Theory and Experiment, 2022(11):114004, nov 2022.*", "weaknesses": "My main concern, however, is the significance of the theoretical contribution of this paper. From the first sight, this paper is merely an extension of the paper [Misiakiewicz2024] with same techniques of deterministic equivalents. \n\nAlso, the result holds only under the strong concentration Assumption 3.1. As mentioned in the paper (line 119-121), I think that this paper could have been more significant if Assumption 3.1 had been relaxed in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their appreciation of our work and for the suggestions which will help to improve it. The typos in the appendix raised in the review will be corrected in the revised version of the manuscript. \n\n> *My main concern, however, is the significance of the theoretical contribution of this paper. From the first sight, this paper is merely an extension of the paper [Misiakiewicz2024] with same techniques of deterministic equivalents.*\n\nIndeed, our paper uses the deterministic equivalents for the functionals listed in Theorem A.2 from [Misiakiewicz, Saeed, 2024]. However, we politely disagree that this is ``merely an extension with same techniques''. It requires a significant amount of work to ensure that we can indeed achieve multiplicative bounds that applies to the regime with optimal rates under source and capacity conditions. As noted by reviewer Gqjy, the proof is 28 pages despite not repeating previous results. \n        \nWe further emphasize that it was not clear a priori that such a multiplicative bound---with optimal rates---for general $n$ and $p$ is achievable. Indeed, compared to the kernel case, the covariance over $z$ is a finite-rank random matrix $FF^T/p$, which does not concentrate (in particular, it has rank $p < n$ in the underparametrized case) and the model presents a double descent with a diverging peak at $n = p$ as $\\lambda \\to 0$.\n\n[Misiakiewicz, Saeed, 2024] only considers kernel ridge regression, while we consider random feature ridge regression which involves many more terms.  In particular, the following parts only appear in the RF case:\n\n- Controlling the covariance matrix $\\hat \\Sigma_F$ of the feature $z$ (Lemma B.2).\n\n- Showing concentration of the fixed points to the deterministic fixed point of Definition 1 (Proposition B.4, which requires a careful perturbation analysis and a uniform bound).\n\n- While the deterministic equivalent over $z$ corresponds to the same computation as in the kernel ridge regression case with covariance $\\hat \\Sigma_F$ (with an added projection term), the deterministic equivalents over $F$ involves many more terms that are not covered by Theorem A.2. These terms need to be decomposed carefully in order to show that we can indeed obtain multiplicative bounds with optimal rates and control the dependencies on $\\Sigma,\\lambda,\\gamma_+$.\n\n> *Also, the result holds only under the strong concentration Assumption 3.1.* \n\nWe refer the reviewer to the general rebuttal for a more detailed discussion.\n\nBesides Theorem 3.3, our paper offers the following contributions: 1) the statement of the general non-asymptotic deterministic equivalents which unifies existing asymptotic predictions, 2) the complete and precise decay rates under source and capacity conditions, which improves over [Rudi, Rosasco, 2017], 3) numerical simulations in various settings that show that Theorem 3.3 apply beyond its formal assumptions.\n\nAs discussed above and in the response to reviewer b7dx, we consider Theorem 3.3 to be an interesting and challenging result to obtain even under Assumption 3.1. It is the first non-asymptotic (dimension-free) result with multiplicative approximation bounds for random feature regression. We acknowledge that Assumption 3.1 is restrictive, but such assumptions are common in the theoretical literature (e.g., it corresponds to the assumption in [Cheng, Montanari, 2022] for the infinite dimension case, or to [Bach, 2023] for linear asymptotics). \n    \nWe consider relaxing this assumption to be an important direction, which we leave to future research. For instance, we believe that the approach in [Misiakiewicz, Saeed, 2024] could be applied here (see response below). However, this would significantly increase the complexity of the proof---which is already 28 pages---while marginally contributing to the main message of the paper (Definition 1 and Corollary 4.1).\n\n- *How difficult it would be to relax Assumption 3.1 as in [Misiakiewicz2024]? And what datasets and random feature model could satisfy Assumption 3.1 empirically?*\n\nFor the first question, [Misiakiewicz, Saeed, 2024] considers a relaxation of Assumption 3.1 by dividing the features into a low and a high-frequency components. The low-frequency features follow a Hanson-Wright type inequality similar to Assumption 3.1, while the high-frequency features are only assumed to be nearly orthogonal. Such a relaxation can be applied in the case of random feature ridge regression to both $(\\psi_k)$ and $(\\phi_k)$.  However, note that the random feature matrix corresponds to the product $FG^T$ and therefore it is not straightforward to separate these two parts. Although we believe an analysis differentiating between the underparametrized and overparametrized regimes will work, we believe that it is beyond what can be expected from a conference paper.\n\nSee general rebuttal for a discussion of the second question.\n\n> *Despite not essential, but it could help the readers a lot if the authors could explain more on the quantities and their intuitions in the paper, like Eq (21-27). From my point of view, Theorem 3.3 is not the easiest to read.*\n\nWe will add a longer discussion on these terms in the revised version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**Assumption 3.1**:  We acknowledge Assumption 3.1 can be restrictive, as mentioned in the paragraph 116-122. In fact, it will not be satisfied by some standard examples of random feature models, such as $\varphi (x,w) = \sigma ( \langle x, w\rangle)$ with non-linear activation $\sigma :\mathbb{R} \to \mathbb{R}$ and $x,w $ Gaussian vectors. 

This is a general challenge when studying deterministic equivalents for non-linear random feature and kernel models. The eigenfunctions are not independent and contain functions of arbitrary high frequency (heavy tailed), which are far from the standard setting of RMT (see discussions in [Misiakiewicz, Saeed, 2024]). Hence, most existing results for kernel methods have either been restricted to linear asymptotics (thanks to the linearization trick [El Karoui, 2010], [Hu, Lu,2020], [Bartlett, Montanari, Rakhlin, 2021]), or polynomial asymptotics for restricted settings (namely inner-product kernels or activations on the sphere [Xiao, Hu, Misiakiewicz, Lu, Pennington, 2022], [Hu, Lu, Misiakiewicz, 2024]). The notable exception is [Misiakiewicz, Saeed, 2024], which provides abstract assumptions (satisfied by inner-product kernels on the sphere) under which non-asymptotic multiplicative bounds can be proven (see response to reviewer gFLF).

We consider the primary motivation of our work to be the rigorous derivation of the excess risk rates in Corollary 4.1, which requires infinite dimensional features, general target functions (not restricted to the RKHS), and multiplicative bounds. 

In order to make progress on this question, we made the following choice: 1) introduce an abstract random feature model $\varphi (x, w)$; 2) present the general non-asymptotic deterministic equivalents; and 3) show a sufficient assumption (Assumption 3.1) where we can show tight multiplicative approximation bounds.

We believe our choice is justified by the following:

- These deterministic equivalents recover all the known asymptotic results for random feature models as special limits. We believe there is value in stating these general formulas along with a proof, albeit under a restricted assumption.

- This is further motivated by our numerical simulations which show these theoretical predictions are remarkably accurate across various synthetic and real datasets. Note that the simulations include the case of $\sigma (\langle x, w\rangle)$ with $w,x$ Gaussian vectors. This indicates that the validity of Theorem 3.3 extends way beyond Assumption 3.1.

- These deterministic equivalents allow to derive tight rates (both lower and upper bounds) under source and capacity conditions, which display a phase diagram richer than previously known (Figure 2). In particular, our derived optimal parametrization improves on [Rudi and Rosasco, 2017]. 

- Assumption 3.1 is satisfied by some toy models that are popular (and often necessary) in theoretical investigations. For example, if $x$ and $w$ are (possibly infinite dimensional) vectors with independent sub-Gaussian entries (by Hanson-Wright inequality, which extends to the infinite dimensional case) and $\varphi (x,w) = x^T w$ (e.g., infinite dimensional linear regression [Cheng, Montanari, 2022]). In this model, our results vastly extends the asymptotic results in the linear scaling $n \asymp p \asymp d$ of [Hastie, Montanari, Rosset, Tibshirani, 2022] and [Bach, 2023], to $d = \infty$, general $n,p$, and multiplicative approximation bounds. Another example (with non-independent entries) is $\varphi (x,w) = f(x)^T g(w)$ with $x,w$ Gaussian random vectors and $f,g$ Lipschitz functions (by Lipschitz concentration of Gaussian vectors).






Note that already obtaining Theorem 3.3 under current assumptions is an interesting (and challenging) result: the features are infinite dimensional, the covariance does not have bounded conditioning number, and there is no reason to expect that the deterministic equivalents will remain accurate under the scalings considered here (source and capacity conditions, vanishing regularization, no restriction on the scaling between $p$ and $n$). We further expect the obtained multiplicative approximation rates $\tilde O (p^{-1/2} + n^{-1/2})$ to be optimal, based on the local law fluctuations of the empirical feature matrix.

We believe that showing deterministic equivalents under more realistic assumptions is an important and challenging direction, which we leave to future research.

We will add further discussions on Assumption 3.1 in the main text, with added references and the examples described above.

- [El Karoui, 2010] *The spectrum of kernel random matrices*.

- [Hu, Lu,2020] *Universality Laws for High-Dimensional Learning with Random Features*.

- [Bartlett, Montanari, Rakhlin, 2021] *Deep learning: a statistical viewpoint.*

- [Hastie, Montanari, Rosset, Tibshirani, 2022] *Surprises in high-dimensional ridgeless least squares interpolation.*

- [Bach, 2023] *High-dimensional analysis of double descent for linear regression with random projections.*

Meta-review: The paper investigates the generalization performance of random feature-based ridge regression by providing a deterministic equivalent for the test error. The key contribution is that this approximation result is non-asymptotic, multiplicative, and independent of the feature map dimension allowing for infinite-dimensional features. As an application, this result is employed in random feature-based kernel ridge regression to provide a tight bound on the smallest number of random features needed to achieve the optimal minimax error rate, thereby improving the result in the literature. The paper is well-written and the contribution is solid. All the reviewers are positive about the paper's novelty and contributions, which I agree with. Based on the discussion with the reviewers, I think the paper is a nice contribution to the literature and therefore I am recommending acceptance. I strongly urge the authors to incorporate all the reviewer comments along with any clarifications they provided in the rebuttal into the camera-ready version.
Decision: Accept (spotlight)