The $\varphi$ Curve: The Shape of Generalization through the Lens of Norm-based Capacity Control
Authors: Yichen Wang
Yudong Chen
Lorenzo Rosasco
Fanghui Liu
Venue: NeurIPS 2025 poster ()
Keywords: generalization
norm-based capacity
deterministic equivalence
Primary area: theory
TL;DR: We provide a precise description on how the test risk scales with a suitable norm-based capacity when compared to a classical metric of model size.

Abstract: Understanding how the test risk scales with model complexity is a central question in machine learning. Classical theory is challenged by the learning curves observed for large over-parametrized deep networks. Capacity measures based on parameter count typically fail to account for these empirical observations. To tackle this challenge, we consider norm-based capacity measures and develop our study for random features based estimators, widely used as simplified theoretical models for more complex networks. In this context, we provide a precise characterization of how the estimator’s norm concentrates and how it governs the associated test error. Our results show that the predicted learning curve admits a phase transition from under- to over-parameterization, but no double descent behavior. This confirms that more classical U-shaped behavior is recovered considering appropriate capacity measures based on models norms rather than size. From a technical point of view, we leverage deterministic equivalence as the key tool and further develop new deterministic quantities which are of independent interest.

The & Curve: The Shape of Generalization through the Lens of Norm-based Capacity Control
Yichen Wang
Yudong Chen Department of Computer Sciences University of Visconsin-Madisee US yudong. chen@wisc.
Department of Computer Sciences University of Aasconsin-Madison US yi richen. wang@wisc edu
Lorenzo Rosasco
Fanghui Liu
Malga - DIBRIS, University of Genova, Istituto Italiano di Tecnologia, IT lorenzo.. rosascoounige. it
School of Mathematical Sciences Institute of Nature Sciences Shanghai Jiao Tong University DCS, University of Warwick fanghui liu@s tu. edu, cn
Abstract
Understanding how the test risk scales with model complexity is central question in machine learning. Classical theory is challenged by the learning curves observed for large weer-parmettrieed deep networks. Capacity measures based parameter count typically fail to account for these empirical observations. To tackle this challenge, consider norm-based capacity measures and develop our study for random features based estimators, widely used as simplified theoretical models for complex networks. In this context, we provide precise characterization of how the estimator's ' norm concentrates and how it governs the associated test error. Our results show that the predicted learning curve admits phase transition from under- to over-parameterizzaion,, but no double descent behavior. This confirms that more classical U-shaped behavior is recovered considering appropriate capacity measures based models norms rather than size. From technical point of view, we leverage deterministic equivalence as the key tool and further develop new deterministic quantities which are of independent interest.
Introduction
How the test risk scales with the data size and model size is always central question in machine learning, both empirically and theoretically. This is characterized as the shape of generalization, i.e., learning curves, that can be formulated as classical U-shaped curves (54), double descent [5]. and
scaling laws [27 59).
In these learning curves, the model size, i.e., the number of parameters, provides a basic measure of the capacity of machine learning (ML) model. However it is well known that model size cannot describe the "true" model capacity 2 633, especially for over wver-parameterized neural networks 4 62] and large language models (LLMs) 8. The focus the number of parameters results in an inaccurate characterization of the learning curve, and consequently. an improper data-parameter configuration in practice. For instance, even for the same architecture (model size), the learning curve
Most of this work was done when Yichen visiting student University of Warwick. Correspondence Fanghui (fanghui. li (sjtu.edu.en, warwick.ac.uk))
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

dee BILLE
61-
60 1009
(a) Empirical observations from Figure 8.12 of 43
(b) Our theory
Figure 1: Fig. ((a) presents previous empirical observations from 43 Fig. 1.12 in the random feature
model. Fig. precisely characterize the learning curve from theory and perfectly matches our experiments (shown by points) with training data {( y4 Hi=1, with n = 300, sub-sampled from the MNIST [30 with d = 748. The feature map is defined (p w) erf (xx, w)) with random initialization w (0, I). Note that whether the curve is finally lower than before is different
between Fig. ((a) and Fig. 1(b) mainly because of data,
discussion in Appendix G.3
be totally different, e.g., double descent may disappear 39 40) A natural question raises that: What is the shape of generalization under the lens of suitable model capacity than model size?
In ML model, its parameters can be represented as vectors, matrices, tensors, and hence the model size is characterized by their dimensions. However, to evaluate the "size" of parameters, suitable metric is their norm. This is termed as normed based capacity, perspective pioneered in the classical results indicated by (2). Indeed, norm based capacity/complexiy are widely considered to be more effective in characterizing generalization behavior; see c.g. 42 (22
16 B3
and references therein. For instance, path-norm based model capacity empirically demonstrates quite strong correlation generalization while other metrics of model capacity may not (26).. Additionally, minimum norm-based solution received much attention as a possible way to understand the learning performance of pver-parameterized neural networks in the interpolation regime; see e.g.
31 55
40).
Empirical observations the learning curve under norm-based capacity have been discussed in the lecture notes [43] Fig. 8.12], as shown in Fig. I(a) when changing the model capacity from model size parameters' norm, the learning curve is changed from double descent to "p"-shaped curve.
However, precise mathematical framework on Aektiiinng/undestanndiinn this curve is still lacking.
The goal of this paper is investigate this curve by addressing the following fundamental question:
What is the relationship between test risk and norm- based model capacity, and how can be precisely characterized?
In this work, we take the first step toward answering this question, as illustrated Fig. T(b) Compared to the classical double descent curve w.r.t. model size p, we quantitatively characterize the relationship: test risk vs. norm-based capacity. Our theoretical predictions (shown as curves) precisely predict the empirical results (shown as points), and the curve is more close the "y""shaped curve. More broadly, our results address how the learning curve behaves under more suitable model supacities-specificcat
whether classical phenomena such the U-shaped curve, double descent, or scaling laws persist or are fundamentally altered. We believe this opens the door to rethinking the role of model capacity and the nature of learning curves (e.g., scaling laws) in the era of LLMs.
1.1 Contributions and findings
We consider linear and random features models (RFMs) regression to precisely characterize the relationship between the test risk and the capacity measured by the estimator's norm. The key technical tool we leverage is the deterministic equivalence technique from random matrix theory 100 [4]. where the test risk R (depending data X, target function f*, and the regularization parameter X) can be well approximated by a deterministic quantity R (with data size n and model size p). i.e.,
asymptotically or non con-asyyptotically where R(E,,,, A.) is the exact deterministic characterization only depends on f", expected data covariance E, "re-scaled" regularization parameter X, other deterministic quantities. In our work.
R(X, fr, A) = (1+0(n -1)00((nn)))01111/11 (2)-)))))
R(E.

---

Table 1: Summary our main results for RFMs on deterministic equivalents and their relationship.
Type
Results
Regularization
Deterministic equivalents N
Relationship between R and N
Theorem
3.1
Asymptotic
Deterministic equivalence
Curollary
3.2
À + 0
Asymptotic
Theorem
E.2
>
Non-asymptotic
Proposition 4.1
À -
Over-purameterized regime
Corollary
À +
Under 4m (n < m <
oo)
Relationship
Curollary 4.2
À 0
Under Assumption power-law)
Proposition
Under Assumption
power-law)
aim to build the deterministic equivalents N of the estimator's lg norm N,, both asymptotically and non asypptospoll,..lyy and derive a corresponding relationship between R and N, allowing a precise characterization, i.e.
Our target
= R = gN) for some function
The main results given by Table D for RFMs, which covers random features ridge regression as well as min-norm estimator (A = 0). Results for linear regression are deferred to Appendix due to page limit. Deriving results N on norm-based capacity is more chandelling than for test risk. This is because, we need to explore new deterministic quantities, which are independent interest and more broadly useful. Specifically, we derive the deterministie equivalents w.r.t. Tr X(X X A) for any positive semi-definite (PSD) matrix A while previous work only handled A == I 0 37 14] Moreover, non-asymptotic results, those valid for finite n, p 12(1) rather than in the asymptotic regime n, - 00, on norm-based capacity require more technical conditions. In particular, they involve non-asymptotic bounds deterministic equivalents of differences between random quantities. Due to the complexity of the formulations, we present these results in the appendix.
After that, establish the characterization of R g(N) under isotropic features and further illustrate the scaling law under classical power law scaling assumptions. The derivation requires non-trivial calculation and integral approximation by eliminating the model size p. We have the following findings from this characterization.
Norm-based capacity suffices to characterize generalization, whereas effective dimen- sion and smoother do not: Our results on deterministic equivalence demonstrate that the estimator's norm includes the information of the test risk') 's bias and variance") respectively. In contrast, typical model capacity, e.g., effective dimension [63 and smoother [12) can only characterize the test risk's variance and thus are insufficient to characterize generalization.
Phase transition exists but double descent does not exist: There exists phase transition from under- to over-verreee wer-parameterizee regime, as shown in Fig. [(b] In the under-parameterized regime, we still observe the same U-shaped curve, whether consider the norm N model size as the model capacity. This curve can be precisely described as a hyperbola for the min-norm interpolator (linear regression) under isotropic features.
But in the over- preemearamteri regime, when the norm N increases, the test risk R also increases (almost linearly if the regularization is small). This differs from double descent: when the model size p increases, the test risk decreases. Our empirical results on Fig. verify this theoretical prediction. More importantly, this curve aligns more with classical statistical intuition-a U-shaped curve-rather than the double descent phenomenon. We conclude that with suitably chosen model capacity, the learning curve closely follows a U-shape curve than double descent, potentially observable in more complex models and real-world datasets, see Appendices H.2 and H.3 respectively.
'Strictyy speaking, it also requires knowing whether the model is mnder-parameterizer or over parametteriee the self-consistent equations differ between these regimes.
3

---

Scaling law is not monotone in norm-based capacity: We study the scaling law of RFMs under norm-based capacity in a multiplication style by taking model size p := n (q 2 0), leading to R = Cn with a 2 0, b E IR, and C'> O. Note that b E IR can be positive or negative, resulting in different behaviors
R. This differs from the classical scaling law that is monotonically decreasing in the model size.
Controlling norm-based capacity can be achieved by the tuned regularization param- eter A: Norm-based capacity appears less intuitive used in practice when compared to model size. Our results demonstrate that the norm decreases monotonically with increas- ing A, and both under- and aver-parameterized regimes. Accordingly, such one-to-one correspondence allows for controlling norm via X, related to the known L-curve (1].
We remark that, our theory cannot fully recover the "p""-cure" shown in Fig. [(a) where the curve in some wer-parametterize regimes is above that in the mnder-parameterized regime. This is because, some real-world datasets may not satisfy the well-behaved data assumption in Assumption [I] We also emphasize that we do not claim that l norm-based capacity (or other norm-based capacity) is the best metric of model capacity. Rather, this work aims to show how the test risk behaves when a more suitable model capacity than model size is used to measure capacity. For completeness, discuss the "cr"- under real-world dataset as well as other metrics of model capacity evaluated in Appendix H. All code and replication materials (including our reproduction of OpenAI's deep double-descent results [40]) are available at giggttu.b...... cwwmcimmmii....
Notations: In this paper we generally adopt the following convention. Caligraphic letters (e.g.. Nx, Rx, BA VR.A.) denote random quantities, and upright letters (e.g., N,, Rx, BN,A, VR.*) denote their deterministic equivalents. The letters N, R, B, V above (in any font) signify quantities related to the solution norm, test risk, bias, and variance, respectively. With denoting the fz-regularization parameter, setting À 0 corresponds to the min-norm interpolator. The superscripts LS and RPM denote quantities defined for linear regression and random feature regression, respectively.
We denote by Y the ratio between the parameter size and the data size. i.e., == d/n n in ridge regression and y := p/n in RFMs. For asymptotic results, we adopt the notation U, meaning that the ratio 8/v tends to one the dimensions d (p for RFMs) tend to infinity. A complete list notations can be found in Appendix(A)
1.2 Related work
The relationship between the test risk, the data size, and the model size is classically characterized by the U-shaped curve [54] larger models tend to overfit. This can not explain the success of deep learning (with even more parameters than data), leading
new concept: double descent (5), where the test risk has a second descent when transitioning from under- to over-parameterized regimes. Moreover recent scaling law 277 shows that the test risk is monotonically decreasing with model size, typically in the under-parann pareeerrrrmeterizede regime for LLMs.
Model capacity metrics: Beyond model size as a capacity measure, there is considerable effort to define alternative capacity measures, e.g. degrees of freedom from statisties [17
effective The norm's asymptotic characterization given specific settings (25) but the risk-norm relationship
18
47
dimension/rank [63 3. smoother [12. flatness 48]. as well as norm-based capacity 42 33
is not directly studied. Besides, training strategies can be also explained as implicit regularization
[61 41), affecting the model capacity as well. We refer to the survey (26) for details.
Random matrix theory (RMT) provides powerful mathematical tools to precisely characterize the relationship between the test risk R and n, p, d via deterministic equivalence,
Deterministic equivalents:
in an asymptotic regime (n, d + 20, B5 20 57 60 I), or non-asymptotic regime [22 10 37).
We refer the reader to [ for further details. Complementary to RMT approaches, techniques from statistical physics are also possible to derive the deterministic equivalence, e.g., replica methods
19 34
and dynamical mean field theory 28
38
2
Preliminaries
We overview RFMs via deterministic equivalents here; see more details in Appendix (B with additional preliminaries on linear regression.
Random features models (RFMs)
can be regarded two-layer neural networks with vp Ej= (1), wyy) where yp Rd x Rdd - is a nonlinear activation function. The
49
32
f(x;; a) = 1

---

first-layer parameters Yw are sampled i..d. from probability measure f/o and kept unchanged during training. We only train a by solving the following random features ridge regression
= arg min agRr
(y) ((z;a)) + A|lall 2z x+) Zyy y Z Rex,,
2==(zzz
(1)
where the feature matrix is 2 1p11p11/ppp pa,;; w)) and À 2 is the regularization parameter. We also consider min-l2-norm solution = 0), i.e., Ami arg min, ||a||2, 8.1. Za y-
Following 14], under proper assumptions on +p (e.g., hounded, quuarediintegrable, we can define a compact integral operator T: (1xx - V I,2 (1ww) for any f L2( such that
(Tf) = [ p(:: w) (x()de gdd
T= Σ SArLR
where (Ex)a21 R are the eigenvalues and (vx)) and (Øx (02) are orthonormal bases of L (px) and V for spectral decomposition respectively. We denote A == diag(E?, .....) E I8 xx and assume all eigenvalues are non-zero and arranged in anninccrasing order.
Accordingly, the covariate feature matrix can be represented as G = [9......................... gnl I R with g : (ab)(a) and the weight feature matrix is = [f [fi,...; Spl
E Rexx with fj = I
(w, ))21)))221
121- Then the feature matrix can be denoted by Z vF
G Raxp, Note that f has
covariance matrix [ A, and we further introduce AF == E3
[zz
F
| FF E Ro*P.
Assuming that fo L (1x) admits f+(x) 222 0r,x2/((2)) we have Stasinarance decomposi- tion of the excess risk
RPN
Ee 0
= 0.
F E. [a]
+ Tr (A))
VP
where the first RHS term is the bias, denoted by BREM and the second term is the variance, denoted R,A- Similarly, under proper assumptions (to be detailed later), they admit the following deterministic equivalents, asymptotically [53] and non-asymptotically [14]
by VAEK
BEN
BEN
(0., (A + 1211-~2.) + X(22) A(A -20)
1-T P2) 0² T² - T(m, 12)
RPY R.A
VR
(2)
where (2) satisfy the self-consistent equations
n
X TrAA(A + +
pn 1/2
T + +11)
(3)
V1
and P2), and x(22 are defined
p (1 (211 n +
2 Tr (A -
Tr (A(A + +12)
P1
X(v2):=
1/2 p- TT (A? + u2)
p - Tr (A2 + +2)-22
Deterministic equivalents under norm-based capacity
To mathematically characterize the phenomena in Fig. I Tunder norm- based capacity, in this section, we firstly derive the bias variance decomposition for the norm E =: .ARFF B VAEM (with definition later), then relate 13REM and A.A to their respective deterministic equivalents B and VAPH In the next section, we aim to precisely characterize the learning curves under norm-based capacities via deterministic equivalence.
To derive the deterministic equivalence, we need the following assumption on well-behaved data and random features.
5

---

Assumption (Concentration of the eigenfunctions 14)) Recall the random vectors v := (E&Ve()))E>) and Φ = (ELL)(W)))21 There exists C. 0 such that for any PSD matrix A E Rooxxee with Tr(AA) < oo and any /. 2 O, we have
P 1 Ar TT(AA) E||A AA
(p) C.e
P [ AΦ Tr(AA) A AA 1/ l1 S CCe
This assumptions holds for sub-Gaussian distributions and more generally, distributions that satisfy log-Sobolev convex Lipschitz concentration inequality [T]. Next present the deterministic equivalence results of NA deferring the proof to Appendix E.1
Theorem 3.1 (Deterministic equivalence of N Given RFMs in Section
the bias bias-variance
decomposition of its norm Be [åll VN are defined as
given by E. @ =: N NNA
ViEh N.
where N and
N. = (0., GZ X1I GO.),
REE NA = :
Z Z 2 21)
Under Assumption ! we have the following asymptotic deterministic equivalents N.N BEEM
RFH
N,
N,X and thus NAPM
N BREN + VAEM
p0.., A(A + 1) 0.) II (A (A + x21)-2)
Px(12)
0.. (A 12 (.) + +x (0. A(A 12 -
REW
n
1 ((1,
px(U2)
APN
(4)
7T (21,, 12)
T(v1,22) 22)
VAPN
Remark: This theorem establishes asymptotic equivalence; more complex non non-asymptotic analysis developed in Appendix E.2] Numerical validation is provided through experiments on synthetic and real-world datasets in Appendix H.I and Appendix H.2 respectively.
By comparing Eq. (test risk) and Eq. (norm) via deterministic equivalence, we conclude that
Bias: the test risk's bias in Eq. has been included the the second term BRFM N,A
(see the
red area in Eq. (4 with rescaled factor px((s)
Variance: we find that the variance term of the norm VANN N,A equals the variance term of the
test risk VRX (see the blue area in Eq. (4.) in Eq. multiplied by a factor px(#2)
Hence norm-based capacity (on the second layer) suffices to characterize the test risk in RFMs. Here we discuss whether other classical metrics of model capacity can characterize the generalization.
Effective dimension 633 It is defined as Tr(A(A + (1(2) ()=²) similar formulation, e.g.. Tr (2) 2). These effective dimensions increase monotonically with p, thus exhibit double descent.
defined as nTTrA ZT Z 2 Z + 2)-2), which corresponds to the variance of the test risk WREN scaled by the factor _.. Therefore, it first increases and then decreases with p, reaching a peak near at the interpolation threshold (p = 12).
Smoother [12]
The above two metrics offer variance-bass based measure of model capacity: they capture the variance component of test risk but contain no information about the target function 0", and thus cannot fully characterize generalization. In summary. norm-based capacity suffices to characterize generalization, whereas effective dimension and smoother do not.
Norm-based capacity over different layers: In RFMs, if we use the norm of the first layer, i.e., ||]] F as model capacity, we will obtain a reshaped double descent curve as Fig. 15 This is because, the first layer's parameters are with random Gaussian initialization and then untrained, directly

---

V ~ /dp-3 increasing with p. For two-layer neural networks with both trained layers, path norm is empirically verified the most suitable (data-inde) independent) model capacity for neural networks. We find that the curve aligns more closely with the norm- based capacity in RFMs of the second-layer parameters, rather than that of the first layer, see more discussion in Appendix H.3
have E||l W
For better illustration, we consider a special case of Theorem 3.1 the min-norm estimator (A = 0), which will be used later, and derive its deterministic equivalence; see the proof in Appendix E.
Corollary 3.2 (Asymptotic deterministic equivalence of )g Under Assumption for the min-l2- norm estimator aminn in the umder-parameteriizn regime (p < n), we have
p(O,, A(A + X, a)) + p(0., (A + 1) 0.)
o²p
BREK
BEH N.O
Tr + Ap1)-
Xp(n p)
where Xp is from TT(A(A + Xp
In the over-parameterized regime (p > n), we have
p(O., (A + 1) D Ap m)
o²p
NN.0
p-n where An is defined by Tr(A(A + 1)
VREM admits the similar formulation in mnder//over-paramettriie regimes but differs in An and Ap- An interesting point to note is that, in the over-varamee per-parameterized regime, X, is a constant when n constant. Therefore, 8%% and VYY are proportional to each other.
Remark:
We need to analyze RFMs separately in the mnder//over-paraettriii regimes when À + 0, leading to different self-consister equations in these two settings.
In the under-parameteriinn regime, in1 converges to 0, and V/2 converges to a value Ap satisfying Tr(A(A + 1))
In the over-parameterrized regime, 1/2 converges 1) = ni, and e) converges to 12 - "/p).
constant A, satisfying Tr(A(A
These differing asymptotic behaviors of 1 and 12 between the regimes enable a more precise characterization of the risk-norm relationship, which will be described in the next section.
4 Characterization of learning curves
By giving the deterministic equivalents of the norm, we are ready to plot the learning curve under norm-based capacity, see Fig. [(b) for illustration. In some special cases, the mathematical formu- lation of learning curves can be given. Accordingly, in this section, we firstly discuss the shape of learning curves from the lens of norm-based capacity in Section [..] Then we take the example of interpolator, and precisely characterize the learning curve by reshaping scaling laws in
Section
4.1 The shape description of learning curves
Here we conduct the bias-variance decomposition, and track how bias and variance behave w.r.t. model size, norm, and the regularization parameter X, as shown Fig. which will provide a more detailed deseription and understanding learning curves.
Reshape bias-variance trade-off's and double descent: We plot the bias and variance components of the test risk over model size p and norm, Fig. 2(a) and Fig. 2(b) respectively. Note that, our theory (shown in curve) can precisely predict experimental results (shown by points). Fig. 2(a) aligns closely with 33| Figure 6] on the double descent when increasing the model size from the under- to over- over-parametenn parameterized regimes. However, even in the classical under- under- parameterized setting, the conventional bias-variance trade-off no longer holds: the bias follows a U-shaped curve, whereas the variance grows monotonically. This was discussed recently by [56] 50 on "whether we should remove bias-variance trade-offs from ML textbooks".
When examining bias-variance vs. norm (see Fig.((()) 2(b).. we observe that: i) in the under-parameterized regime, bias exhibits U-shaped dependence on norm, while variance increases monotonically. This
7

---

0.24
0.330
0.45
0.30
0.45
Origiical te12
0.10
0.15
0.15
10
0.12
0.08
100
200
200
400
50
120
180
240
10
25
50
75
(a) Risk vs.
(b) Risk vs. Norm
Norm vs. (varying A)
(d) Risk vs. Nocm Ivarying À1
Figure 2: The curves bias and variance RFMs are over model size p in Fig. ((a) and over norm E.g f=llã|12 2 in Fig. 2(b) respectively. Fig. 2(c) establishes one-to-one correspondence between the norm and À for a fixed p across varying À values. Fig. 2(d) examines the relationship between risk and norm under the same conditions. Training data {(x,, 3 hie(m) . 100, sampled from the model
y/ = g. 0. + E,, o² 0.04, g, (O, ((00, A), with (A) - and 0..k k-1
result matches with that for model size in Fig. 2(a) ii) in the over-parameterized regime, both bias and variance increase monotonically with norm. These findings reshape the traditional understanding of bias-variance trade-off's and double descent.
Since the self-consistent equation differs from under- pareee--rrmeteieeddd to ver-parameterized regimes, the learning curve plotted against the norm (see Fig. [[b]]and and Fig. 2(d) is not single-valued because of such phase transition: single norm value may correspond to two distinct error levels in the under- and over over-paranin parameterized regimes. However, when analyzed separately, each regime exhibits a one-to-one relationship between test risk and norm. Notably, our analytical and empirical findings suggest that i) sufficient veeetarramttiizaatoon is always better than muder-parameterization in terms of lower test risk, which also coincides with [53]. ii) More importantly, this curve aligns more with classical statistical intuition- U-shaped curve-rather than the double descent phenomenon. We conclude that with suitably chosen model capacity, the learning curve more closely follows U-shape than a double descent. We conjecture that this behavior is universal in more complex models and real-world datasets; see Appendices H.2 and H.3 for details.
Control the norm via regularization. Norm-based capacity appears less intuitive used in practice when compared to model size. To control model norm, one can either fix the regularization parameter and vary the model size p or fix and constrain the weight norm, The latter approach is mathematically equivalent to tuning the regularization parameter À random feature ridge regression, as evidenced by the equivalence to the constrained optimization problem: minş yyy
Za | s.t. ||a|| = B. This (Z" Z + XI) 'Tyy subject to ||اl|2 B, where À is uniquely
yields ridge-type solution: determined by the norm constraint B (with Ø a /// < 0 guaranteeing a one-to-one mapping). We empirically verified this in the random feature model by fixing the training sample size n and ratio 7, and varying to control the estimator norm. As shown in Fig. 2(c) (under-parameteriie) with y 0.5) and Fig. 2(d) pareeeearaeetrrizedd with 7 1.5), the norm decreases monotonically with increasing X, and in both under- and wver-parameterized regimes, the test risk exhibits a U-shaped dependence on norm capacity, consistent with the known L-curve behavior (1.. Further discussion can be found in Appendix G.1
4.2 Mathematical formulation of learning curves
Firstly, we show that the risk-norm relationship is linear in over-parameterrized regime, see the proof in Appendix E.
Proposition 4.1 (Linear learning curve). The deterministic equivalents RAPM and NRFN in over- parameterized regimes (p > n)) admit the linear relationship with the constant slope Xn.
BPP
>,,
REW
+ -Co..A...
(5)
where An satisfying Tr(A(A + dependent on f., A, n, and a, as defined in Appendix E.3
-1) and Co Ann are two constants independent of but
Characterizing the relationship between risk and norm for ridge estimators (A > 0) becomes partieularly challenging. shown in Eq. (3) the parameters p, X, V1, and 122 are intricately coupled, making it extremely difficult to solve for 21 and Pellet alone derive an explicit (even approximate)
Remark:

---

Ye
7a
1 -u
Yv
Yu
Fu
!
3.00
22
Yn
6+1 6+1
tost
Yu
Zer
0.00
Yu
27
1.00
30002
0.000
Zeer
(a) 0 2.5, m0 0.2
(b) a = 1.5, 0.8
(c) Scaling law
Figure 3: Fig. 3(a) and Fig. 3(b); Validation of Corollary 4.2 The solid line represents the result of the deterministic equivalents, well approximated by the red dashed line of Eq. (6) in the over- parameterized regime, and the blue dashed line of Eq. (6) when - n the pnder-parameterized regime. Fig. 3(c); The value of exponents Yn and "/N in different regions (divided by q and é) for r E (0, 4). Variance dominated region colored by orange, yellow and brown, bias dominated region colored by blue and green.
relationship between risk and norm. In the case of linear regression, a complete description of the risk-norm relationship under ridge regularization be established, presented in Appendix [
The relationship in the under-parann pader-parameterizeed regime also complicated as well. We consider the special case of isotropic features in Corollary En3 and give an approximation in Corollary 4.2 under the power-law assumption, given as below.
Assumption (Power-law, [4]..
We assume that ( in and 0. satisty
k-
= k-
0
2
1+2ez with a > 1, r > 0.
The assumption coincides with the source condition |A 0. < 0o (r > 0) and capacity condition Tr(A < do (a > 1) [9]. Under power-law, we need to handle the self-consistent equations to approximate the infinite summation. We have the following approximation.
Corollary 4.2 (Relationship for min-lz norm interpolator under power law). Under Assumption 2 the deterministic equivalents RRFN and N admit the following relationship with Cn,a.r.1 < Cn,a.r.2
Cn.... Cnar3
if p n. if p - n
RREH (1/c.)
where (2,).r,1(2) are constants (see Appendix E.3 for details) that only depend on n, and r. The notation + n. means that p approaches to in the cader-parameterized regime (p < n2.
Remark: In the werrpaaameetrrize regime, the relationship between R and No is mono- tonically increasing linear function, with growth rate controlled by the factor decaying with In the under- under-parante parameterized regime, as p - n (which also leads to R and N + 00), R still grows linearly w.r.t NAPN with the same growth rate factor decaying with n. Furthermore, since Cn,a.r,1 < Cn,a.r:,, the test risk curve shows that over-parameteriiztion is better than under- parameterization. This approximation is also empirically verified to be precise in Fig. 3
To study scaling law, we follow the same setting of [4] by choosing q. I O. We have the scaling law as below; see the proof in Appendix F
n and À = (e-1) with
Proposition 4.3. Under Assumption for r E (0, 3) taking no and = n (f-1) with 1 2 0, we formulate the scaling law under norm-hased capacity in different areas
RREM = + (n
(N ON)
7n S, IN ER,
where the rate (ins " in different areas is given in Fig. 3(c)
Thee symbol zz here denotes using integral approximate infinite when calculating ITr(-).

---

Remark: In all regions of Fig. 3(c) I O, which aligns with the classical scaling law that increasing the number of training samples leads reduction test risk. As for "N in regions @ @ @ and @ "N > O, indicating that when 4 is large (i.e., p is large), the test risk increases monotonically with the norm. In contrast, in region @) "N < O, meaning that when g is small (i.e., p is small), the risk decreases monotonically with the norm. This again resembles the traditional U-shaped curve. These findings highlight the dual role of model norm in generalization: while a larger norm can be beneficial in low-complexity regimes, it becomes detrimental when the model is already sufficiently complex.
5 Conclusion and future work
This paper derives precise characterization the learning curve under the é2-norm based capacity for both linear models and RFMs. It implies that, with suitably chosen model capacity, the learning curve more closely follows U-shape than a double descent, and accordingly reshapes scaling laws. One limitation may be that the studied model is relatively simple, however, deterministic equivalence on complex models requires more exploration
13
In future work, we will investigate the relationship between test risk and model complexity under (stochastic) gradient descent training. Leveraging recent advances in characterizing learning dynamics 45 71. we aim to precisely analyze the evolution of model norms and establish rigorous theoretical connections between norm dynamics and generalization behavior. Besides, our new deterministic quantities provide possible way to study distribution shift and outoof-distrbuution (OOD) [6] with precise estimation, which requires the deterministic equivalence of Tr(A(X X + AI) B(X X - for two matrices A and B.
Acknowledgment
Y. C. was supported in part by National Science Foundation grants CCF-2233152. E. L. was supported by Royal Society KTP R1 241011 Kan Tong Po Visiting Fellowships and Warwick-SJTU seed fund. L. R. acknowledges the financial support of: the European Commission (Horizon Europe grant ELIAS 101 1202377,, the Ministry of Education. University and Research (FARE grant ML4IP R205T7J2KP) the European Research Council (grant SLING 819789), the US Air Force Office of Scientific Research FF88655-22-1 1-7-444,) the Ministry of Education, the grant BAC FAIR PE00000013 funded by the EU - NGEU and the MIUR grant (PRIN 202244A7YL). This work represents only the view of the authors. The European Commission and the other organizations are not responsible for any use that may be made of the information it contains. We thank Zulig for the project organization tool, and Suli for GPU computation resources.
References
[I] Francis Bach. High-dimensional analysis of double descent for linear regression with random projections. SIAM Journal on Mathematics of Data Science, 6(1):26-50, 2024.
[2] Peter Bartlett. The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE Transactions on Information Theory, 44(2):525-553 536,, 1998.
[3] Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117643):00033-0077 2020.
[4] Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. In International Conference on Machine Learning, pages 541-549. PMLR, 2018.
httpa://zulip.com
10

---

[5] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bari-vari trade-off. the National Academy of Sciences, 1 (16(32):1584--158544 2019.
[6] Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, pages 1024-1034. PMLR, 2020.
[7] Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. How feature learning can improve neural scaling laws. arXiv preprint arXiv:2409. 1785. 2024.
[8] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. In Advances in Neural Information Processing Systems, pages 1877-1901, 2020.
[9] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7:331-368, 2007.
[10] Chen Cheng and Andrea Montanari. Dimension free ridge regression. arXiv preprint arXiv:2210.08571, 2022.
[11] Romain Couillet and Zhenyu Liao. Random matrix methods for machine learning. Cambridge University Press. 2022.
[12] Alicia Curth, Alan Jeffares, and Mihaela van der Schaar. A u-turn double descent: Rethinking parameter counting in statistical learning. Advances in Neural Information Processing Systems, 36, 2024.
[13] Yatin Dandi, Luca Pesce, Hugo Cui, Florent Krzakala, Yue Lu, and Bruno Loureiro. A random matrix theory perspective the spectrum of learned features and asymptotic generalization capabilities. In International Conference on Artificial Intelligence and Statistics, 2025.
[14] Leonardo Defilippis, Bruno Loureiro, and Theodor Misiakiewicz. Dimension-free deterministic equivalents for random feature regression. arXiv preprint arXiv:2405. 15699, 2024.
[15] Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of prediction: Ridge regres- sion and classification. The Annals of Statistics, 46(1):247-279, 2018.
[16] Carles Domingo-Enrich and Youssef Mroueh. Tighter sparse approximation bounds for relu neural networks. In International Conference on Learning Representations, 2022.
[17] Bradley Efron. How biased is the apparent error rate of a prediction rule? Journal of the American statistical Association, 81(394):461-470 1986.
[18] Bradley Efron. The estimation of prediction error: covariance penalties and cross-validation. Journal of the American Statistical Association, 99(467))619-632. 2004.
[19] Federica Gerace, Bruno Loureiro, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Generalisation error in learning with random features and the hidden manifold model. In International Conference on Machine Learning, pages 3452-3462. PMLR, 2020.
[20] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Lincarized two-layers neural networks in high dimension. The Annals of Statistics, 49(2), 2021.
[21] Per Christian Hansen. Analysis discrete ill-posed problems by means of the l-curve. SIAM review, 34(4):561-58, 1992.
[22] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. Annals of statistics, 50(2):949, 2022.
[23] Trevor J Hastie. Generalized additive models. Statistical models in S, pages 249-307. Routledge, 2017.

---

[24] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[25] Hong Hu, Yue M Lu, and Theodor Misiakiewiez. Asymptotics of random feature regression beyond the linear scaling regime. arXiv preprint (xXiv:2403.0816) 2024.
[26] Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. arXiv preprint arXiv:1912.02117 2019.
[27] 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 urXiv:2001.08666 2020.
[28] Gabriel Kotliar, Sergej Y Savrasov, Kristjan Haule, Viktor Oudovenko, O Parcollet, and CA Marianetti. Electronic structure calculations with dynamical mean-field theory. Reviews of Modern Physics, 78(3):865-955 951, 2006.
[29] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[30] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 86(11):227-23244 1998.
[31] Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. The Annals of Statistics, 48(3), 2020.
[32] Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan AK Suykens. Random features for kernel approximation: A survey on algorithms, theory, and beyond. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(10):7 122-7148, 2021.
[33] Fanghui Liu, Leello Dadi, and Volkan Cevher. Learning with norm constrained, over- parameterized, two-layer neural networks. Journal of Machine Learning Research, 25(138): 1 1-42, 2024.
[34] Bruno Loureiro, Gabriele Sicuro, Cédric Gerbelot, Alessandro Pacco, Florent Krzakala, and Lenka Zdeborová. Learning gaussian mixtures with generalized linear models: Precise asymp- totics in high-dimessions. Advances in Neural Information Processing Systems, 34:10144- 10157, 2021.
[35] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-766, 2022.
[36] Francesca Mignacco, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborová. Dynamical mean-field theory for stochastic gradient descent in gaussian mixture classification. In Advances in Neural Information Processing Systems, volume 33, pages 9540-9550, 2020.
[37] Theodor Misiakiewiez and Basil Saeed. A non-asymptotic theory of kernel ridge regression: deterministic equivalents, test error, and gev estimator. arXiv preprint arXiv:2403.08938, 2024.
[38] Andrea Montanari and Pierfrancesco Urbani. Dynamical decoupling of generalization and overfitting in large two-layer networks. arXiv preprint arXiv:2502.21269) 2025.
[39] Preetum Nakkiran, Prayaag Venkat, Sham Kakade, and Tengyu Ma. Optimal regularization can mitigate double descent. arXiv preprint arXiv:2003.01897, 2020.
[40] 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 Mechanies: 2021.
Theory and Experiment,
[41] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv:1412.6614, 2014.
12

---

[42] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. Conference on Learning Theory. pages 1376-1401, PMLR. 2015.
[43] Andrew Ng and Tengyu Ma. CS229 lecture notes. 2023. URL edu/main_notes, pdff
[44] Courtney Paquette, Elliot Paquette, Ben Adlam, and Jeffrey Pennington. Homogenization of sgd in high-dimensions: Exact dynamics and generalization properties. Mathematical Programming. pages 1-90, 2024.
[45] Elliot Paquette, Courtney Paquette, Lechao Xiao, and Jeffrey Pennington. 4+ 3 phases of compute-optimal neural scaling laws. arXiv preprint 1xXi:22405.10044,, 2024.
[46] Pratik Patil, Jin-Hong Du, and Ryan J Tibshirani. Optimal ridge regularization for out-of- distribution prediction. arXiv preprint arXiv:2404.01233, 2024.
[47] Pratik Patil, Jin-Hong Du, and Ryan J Tibshirani. Revisiting optimism and model complexity in the wake of overparameterized machine learning. arXiv preprint arXiv:2410.01559, 2024.
[48] Henning Petzka, Michael Kamp, Linara Adilova, Cristian Sminchisescu, and Mario Boley. Relative flatness and generalization. In Advances in Neural Information Processing Systems, volume 34, pages 18420-18432, 2021.
[49] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, 2007.
[50] Benjamin Recht. Overfitting to theories of overfitting. https://wwe argmin net/p/ overfitting- senriitting-tt-theriieee -fheories-ooooverrffie
2025. Accessed: 2025-02-21.
[51] Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. Asymptotics of ridge (less) regression under general source condition. In International Conference on Artificial Intelligence and Statistics, pages 3889-3899 PMLR, 2021.
[52] Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Conference on Learning Theory, pages 2667-2690. PMLR, 2019.
[53] James Simon, Dhruva Karkada, Nikhil Ghosh, and Mikhail Belkin. More is better: when infinite overparameteriiztion optimal and overfitting is obligatory. The Twelfth International Conference on Learning Representations, 2024.
[54] Vladimir N. Vapnik. The Nature of Statistical Learning Theory. Springer, 1995.
[55] Guillaume Wang, Konstantin Donhauser, and Fanny Yang. Tight bounds for minimum 1- norm interpolation of noisy data. In International Conference Artificial Intelligence and Statistics, pages 10572-10602. PMLR, 2022.
(56) Andrew Gordon Wilson. Deep learning is not so mysterious or different. arXiv preprint 1rXiv:2503.02113, 2025.
[57] Denny Wu and Ji Xu. On the optimal weighted VL_ regularization in overparameterized linear regression. In Advances in Neural Information Processing Systems, volume 33, pages 10112-10123, 2020.
[58] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for henchmarking machine learning algorithms. arXiv preprint arXiv: 11X8:07708.07777,, 2017.
[59] Lechao Xiao. Rethinking conventional wisdom in machine learning: From generalization to scaling, arXiv preprint arXiv:2409. 15156, 2024.
[60] Lechao Xiao, Hong Hu, Theodor Misiakiewicz, Yue Lu, and Jeffrey Pennington. Precise learning curves and bigher-order scalings for dot-product kernel regression. In Advances in Neural Information Processing Systems, volume 35, pages 4558-4570, 2022.
13

---

[61] Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learning. Constructive Approximation, 26(2):289-315, 2007.
[62] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3); 107-115, 2021.
[63] Tong Zhang. Effective dimension and generalization of kernel learning. In Advances in Neural Information Processing Systems, volume 15, 2002.
14

---

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 proofs or numerical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in 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.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We clearly discuss the limitations of this work in the conclusion section.
Guidelines:
The answer NA means that the paper has no 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 a separate "Limitations" section 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 how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low 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 of 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 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.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

We clearly state all of the required assumptions, and provide the complete and correct proof in the appendix.
Justification:
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 the statement of any theorems.
The proofs 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 short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be 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 of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
The complete experimental setup clearly described, and experiments are faithfully reproduced accordingly.
Justification:
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 make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all 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 a 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 instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe 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 or verifying the results.
5. Open access to data and code
16

---

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?
Question:
Answer: [Yes]
The code is included in the supplemental material and can be used to reproduce the experiments.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not 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 rum to reproduce the results. See the NeurIPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they 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 much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
We have added a detailed discussion of the experiments in the captions and Appendix H
Justification:
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 level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Our experiments are used to validate our theory instead of providing promising performance when compared to previous algorithms. Therefore, the error bar and statistical significance are not required.
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.
17

---

htt.aiiieeethiccccceeeeeeeeeee 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 or the standard error of the mean.
OK to report 1-sigma error bars, but one should state 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 out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures 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 reproduce the experiments?
Question:
Answer: [Yes]
The experiments are straightforward illustrations the results. They are lightweight enough to be run on standard laptop with CPU (16 GB memory) within a few hours, without requiring GPU acceleration.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well 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 into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in the paper complies with the NeurlPS Code of Ethics in every respect.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a 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: This theoretical study aims improve foundational understanding in machine learning. While may inform future system design, we do not foresee direct positive or negative societal impacts.
18

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious 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 a 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 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 as 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.
If there 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 system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a 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 to 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 is 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
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?
Question:
Answer: [Yes]
Justification: We explicitly cited the sources of the relevant data and other materials used in the paper.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
19

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular 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 not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not introduce new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an 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 participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
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 to the NeurlPS 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 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 paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
20

---

Depending on 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.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to 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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [No]
Justification: LLMs were not used any part that affects the core methodology, scientific rigor, originality of the research.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (https://neurl)) httt::://earrpppcccoooffeerreeee /c/////oeeeeeeccc//22////1. for what should or should not be described.
21

---

Contents
Notations
24
B
Preliminary and background
25
B.1
Asymptotic deterministic equivalence
25
B.2
Deterministic equivalence for ridge regression
26
B.3
Deterministic equivalence for random feature ridge regression
27
................................
B.4
Non-asymptotic deterministic equivalence
27
Scaling law
30
Proofs on additional non-asymptotic deterministic equivalents
30
Main results and proofs for linear regression
34
D.I
Asymptotic deterministic equivalence for ridge regression
35
D.2
Non-asymptotic analysis on the deterministic equivalents of estimator's 's norm
37
D.3
Characterization of learning curves
39
D.3.1
The shape description of learning curves
39
D.3.2
Mathematical formulation of learning curves
39
Proofs for random feature ridge regression
45
Asymptotic deterministic equivalence for random features ridge regression
46
Non-asymptotic deterministic equivalence for random features ridge regression
52
E.2.1
Proof on the variance term
52
Discussion on the bias term
53
E.3
Proofs relationship in RFMs
54
E.3.1
Proof for min-norm interpolator the over wer-parameterized regime
54
E.3.2
Isotropic features with finite rank
54
E.3.3
Proof features under power law assumption
56
Scaling laws
63
Variance term
63
F2
Bias term
64
Discussion
65
G.1
Discussion on the shape of the generalization curve in Fig.
66
G.2 Discussion on approaches modifying the norm
67
G.3
Discussion with other model capacities)
68
H
Experiment
70
H.I
Experiment on synthetic dataset
70
H.2
Experiment on real-world dataset
70
H.3
Norm-based capacity in two-layer neural networks
71
22

---

Norm-basee capacity in deep neural networks
75
23

---

A
Notations
Table 2 summarizes the notations used throughout the main text and appendices.
Table 2: Core notations used the main text and appendix.
Notation
Dimension(s)
Definition
A/
Ea norm regression under regularization AV
regression
Bi
The variance of NV12
N
The deterministic equivalent of N
B
The deterministic equivalent of B
Vi.A
The determanistic equivalent of 1s
N.
|ollz
Baelidean norms vectors
vll
Ev
Number of training samples
Dimension the data for linear regression
Number of features for random feature model
Regularization parameter
X.
Effective regularization parameter for Lincar ridge regression
in M2
Effective regularization parameters for random feature ridge regression
(MM
The k-th eigenvalue of M
Rd 3n
The data
The data matrix The covariance matrix of
Rdxd
The label
12
The label vector
9.
Rd
The target function for linear regression
Rd
The estimator of ridge regression model The min- non-m estimator of ridge regression model
8min
Rd
The noise
55
The i-th noise
The noise vector The variance
2
The i-th weight vector for randorn feature model Nonlincar activation function for random feature model
R2"
The i-th feature for random feature model Feature matrix for random feature model
2
R"XP
R²
The ostimator of random feature ridge regression model
Amin
The min & norm estimator randorn feature ridge regression model
f-))
The function
The distribution of The distribution of An integral operator defined by (w)) = Jgd so(;; f(m)dde Vf Lig(tt))
T
V
The image of T
Es
The fe-th cigenvalue of T, defined by T Σr Eutiedi
The & eigenfunction in the space [2(pa), defined by the decompoxition Σe Ea 14 The k-th eigenfunction of T the space V, detined by the decomposition spectral
de
poooxe oc
diag((f ( 42....) .) xgoxxxx 9: (We((x))e21
9:
R
1000
(Sud)(w;)))2))
RBX
G:
9n 2x with g; (vr(0s)))21
P P= ih....
ERPX
Ar
RPXP
Ar xz
FF RPX
The coefficients associated with cigenfunction
expansion of f=(x) Et>1 (.
0. (0.,x)a21
Replacinn N with R. (N with R), get the notations associated to the test risk. Replacing À with 0, get the notations associated to the min-E2-norm solution. Replacing with we get the notations associated to random feature regression.

---

B Preliminary and background
We provide an overview of the preliminary results used in this work. For self-contained completeness. we include results on asymptotic deterministic equivalence in Appendix [.I results on ridge regres- sion in Appendix [8.2] and results on random feature ridge regression Appendix [33] Additionally, Appendix [.44 presents results on non-asymptotic deterministic equivalence, along with definitions of quantities required for these results. Finally, Appendix introduues key results for deriving the scaling law.
B.1 Asymptotic deterministic equivalence
For the ease of description, we include preliminary results on asymptotic deterministic equivalence here. In fact, these assumptions and results can be recovered from non-asymptotic results, e.g., [37]
For linear regression, the asymptotic deterministic equivalence aim to find B R V VL where B and VR., are some deterministic quantities. For asymptotic results, series of assumptions in high-dimensional statistics via random matrix theory are required, well-behaved data, spectral properties of Σ under nonlinear transformation in high-dimensional regime. We put the assumption from [ here that also widely used in previous literature [I5 51
Assumption 3. [ Well-behaved data] We assume that:
(A1) The sample size n and dimension d grow to infinity with A4 + > 0.
(A2) X T2 where T E Raxd has i..dd sub-Gaussian entries with zero mean and unit variance.
(A3) Σ is invertible with Eiloo < oo and its spectral measure 1/ Ein do, converges to a compactly supported probability distribution j on IR+
(A4) || 12 mass, where v; is the unit-norm eigenvector of Σ related to its respective eigenvalue o; Definition B.1 (Effective regularization), For n, Σ, and 2 O, we define the effective regularization A_ to be the unique non-negative solution to the self-consistent equation
and the measure Ei (o) 25, converges to measure with bounded
(+(EE+AA)))
Definition B.2 (Degrees of freedom).
dfi (A.) (((E(+AA.)T df2(A.) TTE" + X.)
Proposition B.3. 11 Restatement of Proposition 1J Assume (AI), (A2). (A3). we consider A and B with bounded operator norm, admitting the convergence of the empirical measures, i.e. Ed= v.. Av So; + VA and Σd v. Bu; 8a, + uB with bounded total variation, respectively. Then, for > > O, with X, satisfying Eq. (7). we have the following asymptotic deterministic equivalence
TrAX X x BX BXT TrAX XXXXX
(8)
-
+X.)
+XT A.) BT) Σ n
df.
(9)
TMA X X+ TH ((EE+A,))))) 1.)-
(10)
X
TI(AXX + B x +X)-1)~
Tr(A X.) BB + X.)-1)
X
TH(A
Tr + - -
2
(11)
25

---

Proposition B.4. M Restatement of Proposition 2] Assume (AI), (A2), (A3), we consider A and B with bounded operator norm, admitting the convergence the empirical measures, i.e,, Ei= v Av;
da: - VA and Ei= v. Bo; bg: + UB with bounded total variation, respectively. Then, for X e CackslashR+, with Xa satisfying Eq. 77) have the following asymptotic deterministic equivalence
Tr(AT" (ET +T) Tr + A,)
(12)
Tr(TT (EE + TBB (ETT" TT) ~ Tr + X,) B + X.) X.)
+* + (.) Tr + A.) n dfz
(13)
Note that the results in Proposition B.3 B.4 still hold even for the random features model. We will explain this in details in Appendix
B.2 Deferministic equivalence for ridge regression
We consider samples {x,}"= sampled i..d. from distribution Ps over Fd with covariance matrix E == E[ax E Rdxd The label is generated by linear target function parameterized by G._ E R i.e., 1/s x. B, + E,, where 6; is additive noise independent of æ; satisfying B[e,] = 0 and var 0². We can write the model in a compact form as y X 3, + E, where the data matrix E R The estimator of ridge regression is given by 3 (x X + AI) -1 X y. We also consider min-(2-none solution in the over- weer-parameterized regime, i.e., Buni arg min, || s.t. X y. The excess risk of 3 admits a bias variance decomposition
X Raxd the label vector y IR" and the noise vector
RLB = 113. 3 = E + TTCO
where the first RHS term is the bias, denoted by B and the second term is the variance, denoted by R. Accordingly, the bias-variance decomposition is given by
VLS
BLS = 1|3. - Be [ x (B., (X X + AT) E(X X + - B.), R Tr (ECov: = TTX X(X X +
(14)
(15)
Under proper assumptions (to be detailed later), we have the following deterministic equivalents, asymptotically (1 and non-asymptotically [10
E(E
T'T + -
B B i- T=
V n TT +
(16)
where X, is the non-negative solution to the self-consistent equation X Tr(E X.I)-1).
Accordingly, the risk admits the following deterministic equivalents via bias decomposition.
Proposition B.5. 77 Restatement of Proposition 3] Given the bias variance decomposition Eg. (1)
and Eq. 15 X, E and B, satisfy Assumption 3 we have the following asymptotic deterministic
equivalents R5. R := BLS
R + VR. such that RLS R. ~ B VAS
VR. where BR,,, and V
are defined by Eg. T6).
Proposition B.6. M Restatement of results in Sec 5] Under the same assumption Proposition B.5
for the minimum -n-nr estimator Bmins we have for the under-parameterd regime (d < n):
d
B = O, VR.00 ~ σ² n d
In the over-parameterizee regime (d > n)), we have
BLS (3, E(E + X,, -23
0² TTr + 1) n T + 1)
LI
1 1 X3 I) -2)
where Xn defined by Tr +,, 1)
26

---

B.3 Deterministic equivalence for random feature ridge regression
Recall Eq. T the parameter can be learned by the following empirical risk minimization with an l regularization
vp Σ asp(ar, un)) aaso(a,us)) + Allal12 (Z
à arg min aERP
y1
Assuming that the target function fa E (px))) admits f.(x) - Σnz1 0,, (z), the excess risk
REPM = Eg
0.
FTà à
admits the following bias-variance decomposition
v
R.A
0.
F EE
= 0. -.p11/22 (Z Z + + GO.
(17)
VP
2
DREX R.
=
Ir (ApCov
= =O z(z z (
(18)
Accordingly, the risk admits the following deterministic equivalents via viri-variance decomposition.
Proposition B.7. (14 Asymptotic version of Theorem 3.3] Given the bias variance decomposition
in Eq. (17) and Eq. (8)) under Assumption 7 we have the following asymptotic deterministic
equivalents RRF REER
R + VBFM such that BR BREK DRP
VRFM where BRFN and
R.
VR. are defined by Eq.
Note that the above results delivered in non-asymptotic way [4], but more notations and technical assumptions are required. We give an overview of con-asymptotic deterministic equivalence below.
B.4 Non-asymptotic deterministic equivalence
Regarding non-asymptotic results, we require series of notations and assumptions. We give a brief
introduction here for self-comples self-completeness. More details can be found in [10 37 [4].
Given E Rd with d N. the associated covariance matrix is given by Σ E[xx) J. We denote the eigenvalue of Σ in non-increasing order as σ 2 2 03 2 ... 2 σd-
We introduce the non-asymptotic version of Eq.
below.
Definition B.8 (Effective regularization). Given n. E, and 2 the effective regularization X, is defined as the unique non-negative solution of the following self-consistent equation
Tr(E(E +
X
Remark:
Existence and uniqueness of X, are guaranteed since the left-hand side the equation is monotonically increasing in X while the right-hand side is monotonically decreasing,
In the next, introduce the following definitions "effective dimension". metric to describe the model capacity, widely used in statistical learning theory.
Tr(E>+) Di oj as the intrinsic dimension, we require the following definition [Egllop
Define rk( =
px(n) = 14 Ln- 1 T2(17- n!) V n
log (rE((m- nl) V n) }
(19)
A
n
where 7/. E 1/21 is constant that will only depend on C. defined Assumption the convention that [n.-n] if [nx n) > d.
And we used
27

---

In this section we consider functionals that depend on X and deterministic matrices. For a general PSD matrix A E Rd define the functionals
2 X A, A) == TI | X +
(20)
22 X:; A, A) = Tr (AX X X 1)
(21)
4 X:; A, A) = Tr (A
X X) E X + 1) 11112)
(22)
X X
2 (x = Tr
[A x +
(x x 1) 11/2
(23)
n
These functionals can be approximated through quantities that scale proportionally to
" 1 A) == Tr (A + x.1)="),
(24)
22 (A.: A) == 1 Tr (A + x.1) n n
(25)
2)
The following theorem gathers the approximation guarantees for the different functionals stated above, and is obtained by modifying [14, Theorem A.2]. We generalize Eq. (28) for any PSD matrix A. which will be required for our results on the deterministic equivalence of le norm. The proof can be found in Appendix C
Assume the features Theorem B.9 (Dimension-free deterministic equivalents, Theorem A.2 of 14)
{ar Jue()] satisfy Assumption with a constant C. > O. Then for any D, K O, there exist constants
m. (0, 1/2,, CD.K > 0 and C.D.KK > 0 ensuring the following property holds. For any n 2 CD.K
and x > 0, if th following condition is satisfied:
A (n) 2 M olp
Px(n) log (n) S KVn,
(26)
then for any PSD matrix A, with probability least n n-, we have that
X ()(ii:)) S C..DDK P2(n) 2/2 log (n)) (X: A,
d (A.::::)
(27)
VTi
A
px(n) log (n)
(x;11111) V., (A.; S C.D
V (}.;
(28)
Vn.
(x;;;AA1 - nnd
2
V2(A.;; S C.DD.K pa (x log (n)
11d 2
(2(A,:;),
(29)
Vn
px(n) (2)
T (X; A) V2(A,; A)I S C.D,KK
T2(A. A).
(30)
vn
Next, we present some of the concepts to be used in deriving random feature ridge regression. Similar to how ridge regression depends on X., as defined in Definition B.8 the deterministic equivalence of random feature ridge regression relies on 21 and v2, which are the solutions the coupled equations
n
A Tr (A(A + +1) p
ped
Tr (A(A + 12)
(31)
1/
1/2
Writing 21 as a function of 1/2 produces the equations as below
n 2
2
n 1+
2Tx
, 122
n
n
+4 pvz
+
4
p
2
p
pv
(32)
For random features, our results also depend on the capacity of A. Recall the definition of T (k) : Tr(A>k) as the intrinsic dimension of A at level k, we sequentially define the following quantities TA2k|opp that can be found in (37 [4]
28

---

Mk(k) 1+ ra([ kj)) V
log (1a V k).
(33)
Px(p) =1+ p. pn- MA(P),
(34)
ne n po(t)) Ma(n),
pc(n.p) 1(n S p/ma)
(35)
1i
where the constant E (0,1/2) only depends on C. introduced in Assumption 1
For an integer N, split the covariance matrix A into low degree part and high degree part as
Au diag(E? 2.. .
2 A diag(s ( S:
After we define the high degree feature covariance A+, Tr(A4). To simplify the statement, we assume that we can choose m such that p² S (pA/n)) which is always satisfied under Assumption For convenience, will further denote
define the function 7()) ==
7+ (pvr),
7A = rpA/n))
(36)
For random feature ridge regression, we will first demonstrate that the &g norm concentrates around quantity that depends only Ar. To this end, define the following functionals with respect Z.
2 Z; A, K) = Tr 1/2 z z +
AF Z x) -
Z Z
(37)
44 A, k) = Tr 1/2 z Z
+
z z + x) 1/2
Given that Z consists of i.i.d. rows with covariance Ar aforementioned functionals can be approximated by those of F, which, in turn, can be represented using the following functionals:
FF /p. we will demonstrate that the
1 (FFAA, K)
T F; A. x)
N n L F; KK)
(38)
$ F: A. x) = (A (FFF +x)-2).
Proposition B.10 (Deterministic equivalents for $ conditional on F, Proposition B.6 of [14)
Assume [zibse and hielpl satisfy Assumption 7 with a constant C, 0, and F AF defined
in (14] Eq. (79)]. Then for any D, K there exist constants nJ. (0, 1/2), CD.K > and
C....K > 0 ensuring the following property holds. Let (p) and (n. p) be defined as per Eq. (34
and Eq. 35 74 be defined as Eq. 36). For any n 2 CD.K and 0, if the following condition
satisfied:
A2 n
(n 5/2 log log (2) S Kvn, (x(n.)) P.+ (p) log log" S KVP.
then for any PSD matrix A RPxP (independent of Z conditional on F), have with probability at least n that
1 (2; A,A) nP1 2 $5 A, A,p
S S.., (i (TM) 2 Po A, pvi),
(39)
(1 A, -5; A, pm))
S..,K (n,
(F; A. pv1);
(40)
where the rate Eg (n. p) is given by (1(n = (a(m Ing (12
P (x(mp)) (p) 22 log
+
/p
29

---

B.5
Scaling law
For the derivation of the scaling law, we use the results in 14 Appendix DJ. We define (V) as
(v)
( S 05659
1=1
Under Assumption 2 according to 14 Appendix DJ. we have the following results
T3, (v) = 0 ( (2" ()])00
(41)
Next, we present some rates of the quantities used in the deterministic equivalence of random feature ridge regression. The rate of is given by
~ O (n n (n-a(lnonsja))
(42)
and in particular, for T(P1, 12) and ((2)). have
1 T(21, O(1),
(43)
= = n (1z1-Vo).
(44)
C Proofs on additional non-asymptotic deterministic equivalents
In this section, we aim to generalize Eq. (8) for any PSD matrix A, i.e.
(x: A) W2(44 A) s (m -)). V2((u;
that is required to derive non-asymptotic deterministic equivalence for the bias term of the l norm.
By introducing a change of variable μl, == -- (A) = A/h., we find that μa, satisfies the following fixed- point equation:
n μ4. I+
(45)
We define and T as follows
Σ Σー V0,
T XE -/-
And the following resolvents are also defined
R = [X + 11 : (m.E (w.E : 4/ M %
Since the proof relies on a lcave-one-out argument, we define X_ ()xd) 1)xd as the data matrix obtained by removing one data. We also introduce the associated resolvent and rescaled resolvent:
R_ = x__x+MM (X RR = (1 ( =+>=++>) .M- = = M = =
R.:
where k = Tr(MM- )}.
For the sake of narrative convenience, we introduce functional used in 37
v VI Tr(AE(,, +)-1).
Next, we give the proof of Eq.
28
We consider the functional
4 (x; A)
Tr AΣ
x x
Ir(ATTTM),
Remark: Note that, to align more closely with the proof in (37, the xx A) defined here differs slightly from the @2(X; ;; A, X) Eq. (28). However, the two definitions are equivalent we take A here as A Σ 1/3 B which recovers the formulation in Eq. (28).
We show that Ø2 A) is well approximated by the following deterministic equivalent:
2 A) Tr(Au, E + +)= Tr AE + +
30

---

Theorem C.1 (Deterministic equivalent for Ar(AT TM)). Assume the features (e())) satisfy
Assumption with constant C, > 0. Then for any D.K K >> O, there exist constants E (0, 1/2), CD.K and C.DD.K > 0 ensuring the following property holds. For any n Z CD.K and if the following condition is satisfied:
A px(xm) 2 n
Px(n)² log (m) S K Kyn,
(46)
thenfor any PSD matrix A, with probability at least n2 -D, we have that
82 A) V2 (2(u;; & C...D. Px(m) log (n) V2(u; A).
(47)
Remark: Theorem C.I generalizes Eq.
28 Note that there are some differences between ps as
defined in Eq. (9) and VA as defined in 37. However, based on the discussion in [14] Appendix A],
Va can be easily adjusted to match p)- Therefore, while we follow the argument in [37] we use Ps
directly in this work to minimize additional notation.
Following the approach outlined in [37, proof involves separately bounding the deterministic and martingale components. This is accomplished in the following two propositions.
Proposition C.2 (Deterministic part of Tr(ATT )))). Under the same assumption as Theorem C.I
there exist constants CK and C.,k. such that for all 2 Ck and X > satisfying Eq. (46). and for
any PSD matrix A, we have
Px(n) Vn
2 A)] V2(u:: A) C.,K
V2(u-; A).
(48)
Proposition C.3 (Martingale part of Tr (T(AATTTM there exist constants CK.D and C..D, K. such that for all n 2 CK.D and X >> O satisfying Eq. (46) and for any PSD matrix A, we have with probability at least 1 n- that
Under the same assumption as Theorem C.1
PA (2 log (n)
2 x;
A)
E 02 (X;
A)] S C.DD.K
V2(u:; A).
(49)
Vn
Theorem C.I obtained by combining the bounds 488 and above separately.
449
Next, we prove the two propositions
Proof of Proposition
First, by Sherman- Shermon-Morrison identity
M_ tt M_
M_t
M = M_
and Mt
1 E M_t
1 E M_t
decompose E[ A)] as
T M-M At
E [Tr(A TM) nF
1+S
IE (T
K-S
+ nE
t M At (1+ S)
1+
(1
where we denoted 5 = t M_ Therefore, bounding the following two terms is sufficient
2 X; A)] (2(;;;
nE (TA.T.. V2(u:: A) + nE
K-S
E M At
(50)
1
(1+
(1
For the first term, recall that ū. the solution of the equation and ش_ n)(1+*). By [37] Proposition 2], we have
45
where we replaced by n
E TY(MMM))) v (ū.; A)l S (D)
( A),
31

---

where Ei,--1 C.,K pa(n))/2 va-T
For n 2 C, we have E S C and by 37
Lemma 3], we
have
(i A) - VI(Ns; A)I S cPa(m)
v (mii A).
n
Combining the above bounds, we obtain
[BTT((MM)) )] v (u=; A)I 5 1,n
e(D)
v (M+i A).
Furthermore, from the proof of 37 Proposition 4, Claim 31, we have
p. -4-1 D-
Pa(n)8/2
S O+
vn
Then we conclude that
114, - P-1 C. PA(1)3/2 //2
Vn
Pa(n)5/2
C1+ Pa(n)8/2
K
Vn
vn
ur
PA PA
S C.
Ma.
Vn
where we use condition (46) in the last inequality.
Combining this inequality with the previous bounds, we obtain
nF TreMMM T (p=; A)
= | (MT) )] - n4, (1, A)1
1 1+K K
$ レー | AM )] (i A)) + 1i5 Mal
Mh 1t (Mr: A)
s cef μ4 v (m=:A)
Ce(D) V2(uu; A).
In the next, we aim to estimate the second term in Eq. 50 Here reduce A to be rank-one matrix A : vo following (37 Eq. (77)). We simply apply Hölder's inequality and obtain
E M_MAt At
7
(1 + ++) + 5)
K S
nE
tT M uU
(1 +1+ xL + S)
Ex [is-S)²] 1/2
E. [(t" M_v [) 1/2
< n.E
E. [Iss -=) 1/2 EM- [E, [(E M_ vo t)²
< nEM
[R [(s- 5) / EMM Ee [(t M m) R, [(w T 2) 1/2
< nEM
Each of these terms can be bounded, according to the proof of 37 Proposition 2], for the first term,
we get
pa(n) Vn
Eg [t M_t (+]t->)31) x)]]] C.
EM
For the second term, first according to [37 Lemma 2], we have
E, [t M o) 1/2 s u. MEv
E, [(0 t) < Co
32

---

Thus we have
Ee (tt M M Es [(v ((TT))97/a]
1/2
SEM [C, u 2) w//02
E EM_
= C. [TrAMM A))
Then according to
37 Lemma 4.(b)), we have
EM_ TT AM A)] I C. ( A) (I
where the last incquality holds due AM being rank-1 matrix. Combining the bounds for the second term, we have
Ex [t M "M""" B. [(0 1) v/) S CCXPA(()T((AM CC.NPRU))TAA
EM
By combining the above bounds for the first and second term, we have
S T M-AT
S C..K (a(1)
Vn (TM(AM)
(1+ (1
(1(1)
C.C.K
p. TrAM)
Vn
where we use (M))
according to [37 Lemma 3] in the last incquality.
(n)
Combining the above bounds concludes the proof.
Proof of Proposition Proposition C.3 The martingale argument follows a similar approach to the proofss of (37, Propositions 3 and 5]. The key remaining steps adjust Step 2 in (37 Proposition 3] and establish high-probability bounds for each term the martingale difference sequence.
We rewrite this term martingale difference sequence
S == Tr(AT TM) - ([TT(ATTMMM = Σ (B, E.-- Tr TM) =: Σ A
2
where E, is denoted as the expectation over {#141,' '.. Fn
We show below that A I R with probability at least - n with
PA (n)² log(n) V 22(u, A).
R= C.,
(51)
n
For Step 3 and bounding R4-1 B4-1 [ observe that with probability at least n- by 37 Lemma 4.())
(t M_ At)
E,11/4,1%6 < 2E,-1
(1 + S)²
(2(n) log (2(
S C..D.K
H1. (TAM)
S...D.K (x(n) log 1/2
V2( A).
establish high-probabilltyy bound for A, by first decomposing and strategically adding and subtracting carefully chosen terms. Observing that
A, = (E,- - E,-1) Tr(TT TM) = (E,- E,-1) (Tr(AT TM) Tr(TT T,M,)). where M; is the rescaled resolvent removes T; and we used that E, [AT] T.M.]
E,-1 ATŞ T.M.]. and we'll write (recall that S, = t. M,t,)
Tr(ATTTM) TM) TAAT T.MA) Tr(A(t,t + +T; T)MM TRAT T,M))
-t At, + Tr(TT) T.M) TH(T T,M,)
M,,, T.MLI, M.)
(1+ S.)
Th(t, M.A - T.T.M.
(1 S.)
33

---

our main results for Observing that
= TMM, X M,, we can write for j {i 1,1). with probability least n-
E
1 St)
Tr(t,t M,A(I T, T.M.))
SAE, [1t M, AE MM
E, [1t, M.A.
$ C.DD log(n) [Tr(AM))
3 DPA (1) log(n)T((AM)
S C..D ps p2(n) log(n)
14 T((MM)
n = CC, pa (a(n)² log(n)
V2((14; A);
n
where we used that M, < Σ/λ by definition in the second inequality, fourth inequality, and μr. T+(M(M 2px(n] in the last inequality.
37 Lemma 4.(b)] in the
Applying union bound and adjusting the choice of D, we conclude that with probability least 1 - n 1-- the following holds for all i E [n]:
A S C.D..K Px(m) log(n)
V2(M;; A).
D Main results and proofs for linear regression
In this section, we study the asymptotic and non-asymptotic deterministic equivalent the (ridge/ridgeles)) estimator norm for linear regression. Based on these results, able to mathe- matically characterize the test risk under norm-based capacity. linear regression.
Table 3: Summary of our main results for Linear Regression.
Type
Results
Regularization
Deterministic equivalents
Relationship between R and
Proposition D.4
À
Asymptotic
Deterministic equivalence
Corollary D.5
À +
Asymptotic
Theorem
D.6
À
Non-asymptotic
Proposition
D.7
À 0
Under Σ I
Relationship
Proposition
D.9
À
Under-parameterized regime
Corollary D&8
À +
Under Σ = La
Proposition
D.10
A
Under Assumptton law)
To deliver our results, we need the following lemma for the bias-variance decomposition of estimator's ss norm.
Lemma D.1 (Bias-variance decomposition NV We have the bias-variance decomposition
1 =: A = B + N_ where B and N.N are defined
B (B., X
X X -
VLS : x X X
And we present the proof of Lemma D.I as below.
Proof of Lemma D.1 Eg || is given by Eg |||
Here we give the bias-variance decomposition of EE || The formulation of
(XT
+ X v1
34

---

which can be decomposed as
Bel1 1 = RRel (x x XT) X (X + +
=1l(X X + M1)
X x,3 + + (X x + XI) El
-3., (X x x - 33.) + - x x (X' x X
=: BN + V
Accordingly, we can see that it shares the similar spirit with the bias-variance decomposition.
Our first goal is to relate B and V. to their respective deterministic equivalents. And next, will present the results for both asymptotic and non-asymptotic regime separately.
D.1 Asymptotic deterministic equivalence for ridge regression
In this section, we establish the asymptotic approximation guarantees for linear regression, focusing on the relationships between the &2 norm of the estimator and its deterministic equivalent. These results can be recovered by our non-asymptotic results, but we put them here just for completeness.
Before presenting the results on deterministic equivalence for ridge regression and their proofs, begin by introducing a couple of useful corollaries from Propositions B.3 and B.4
Corollary D.2. Under the same condition of Proposition B.3
we have
Tr AE + 1.11)
Tr(X X(XXX(XXX X +)
(52)
df2(1.)
Specifically, if A E, we have
dx.
Tr X(X + +1)
(53)
n (Xx)
Corollary D.3. Under the same condition of Proposition B.4 we have
Tr(A(E X.)
Tr(AT (TET + +) 2T)
(54)
n n (f.())
Using the equation
(IX(AXXXXXXXXXX TrXX X(X XXXXXXXX++XX (Ir(AX X(X x - -T(A) X X + ))-3))
we can directly obtain Corollaries D.2 and D.3 from Propositions and B.4
Now ready derive the deterministic equivalence, i.e., 6 1 under the bias-variance decomposition. Our results can handle ridge estimator Proposition D.4 and interpolator 3min in Corollary D.5] respectively.
Proposition D.4 (Asymptotic deterministic equivalence of A/ Given the bias variance decompo-
sition 1f E | in Lemma D.1 under Assumption 3 we have the following asymptotic deterministic + VLa
equivalents N ~ N4
LS
N.A such that BiS
BL
VLS where these N,
N.A
W.A
quantities are from Lemma D. and Eq. (55).
TEEEE+N1)-2
X2 E(E X. 1) 2B.)
BLS
(B., (E -3.)) +
n
+ A.
B
VL3 THEEE -
(E
(55)
T>EE
+ 22
+
35

---

We remark that, by checking Eq. (16) and Eq. (55). norm-based capacity suffices to characterize generalization while effective dimension can not. where effective dimension defined as Tr Tr(E
-- 63 or similar formulation, e.g., Tr( X-
Bias: for the bias term, find that the second term of B rescales B in Eq. (6) by
factor T),7)
we find that the variance term of the norm N,A equals the variance term of the test risk VR. in Eq. 16 multiplied by factor E+ 2) That means, under isotropic (TE 2).
Variance:
features Σ La they are the same.
Accordingly, the norm-based capacity is able to characterize the bias and variance the excess risk. We provide a quantitative analysis of this relationship in Appendix D.3.2 Below, we present the proof of Proposition D.4
Proof of Proposition D.4 We give the asymptotic deterministic equivalents for B and A respectively. For the bias term B we use Eq. (9) by taking A 3.,3.. and B I and thus obtain
B = (3x, (X XXXXXXXXXXXXXXXX
-Tr(B,B. X) 3)
~T(33,3 E' X.1) 3)
+ +X2Ir(B,6 E(E X-11 3) TTrEEEE X,1) 3)
n -
TrEE + X.1) X -(
(B,, Σ + x
=: =.B
For the variance term VAS we use Eq.
52
by taking
= I and obtain
σ TrE + X.T)
D = X X
n (E)
N.A
The deterministic equivalent of the norm for the min-l2-non estimator. We have the following results on the characterization of the deterministic equivalence of [|@miin
Corollary D.5 (Asymptotic deterministic equivalence of the norm of interpolator). Under Assump-
tion 3 for the minimum f2-norm estimator Bmino we have the following deterministic equivalence: for the inder-parameterizer regime (d < n2), we have
0²
B
||3. 11
Tr
N.O
n1
In the over-parameterrzze regime (d > n)) we have
B ~ (3., E(E + An -1
"2Tr E(E + An 1m
0²
N.U Tr(E² A, 1)2)
where Xn defined by Tr(E + -) ~ n.
Remark: The asymptotic behavior of X, differs between the under-parameterrized and over- parameterized regimes as À + 0, though the ridge regression estimator & converges to the min- estimator Amin- To be specific, in the to 0 as
regime, X, converges > O; while in the over-parameterized regime, X, converges to a constant that admits Tr X, -))1 ~ n when À - O. Accordingly, for the minimum to-norm estimator, it is neces- sary to analyze the two regimes separately. And we show that the solution X, to the self-consistent equation Tr(E(E I) -1) can be obtained from the variance VLS o² //n-
36

---

Proof of Corollary D.5 regimes.
We separate the results in the under under-parameen parameterized and over-parameterized
In the under-parameltriized regime (d nt), for minimum norm estimator Bmin. we have (for X X is invertible)
Bmin (x x)
y (x
x = (x
X'e.
Accordingly, we can directly obtain the bias-variance decomposition as well as their deterministic equivalents
B N. = 2 N,o = XXXXX ~ 0² Tr
d
where Eq. 52 and take À -> 0 for the variance term.
In the over- parameterized regime (d > n). we take the limit - within ridge regression and use n, we have for the bias term
Proposition D.4 Define A, as Tr [>> + An
Tr Tr<EE> + An
( E(E + 1)
B
(B., (E (E+ X, B.) +
1 TT 1n
(B., E(E 1n 3.) (n. E + X.. 3.)
Tr(EEE 1)
(B, E(E X, -p,
n
I- (x
BB. E(E X, 1) B1)).
For the variance term, have
LL T'Tr(E(E + 1n1)-- NO
n n- Tr E 1n
Finally we conclude the proof.
D.2 Non-asymptotic analysis on the deterministic equivalents of estimator's norm
To derive the -onmpptptooiic results, make the following assumption well-behaved data. Assumption 4 (Data concentration B7)). There exist C, > 0 such that for any PSD matrix A E Rddd with Tr(EA) < co and 2 we have
x AX Tr(EA)) 2 1/2 /| A0111110) S &
Assumption
(144)
There exists C >
(B., E 13. (G,, E' - X.) SC.
This assumption holds in many settings of interest, such as power law assumptions like those in Assumption 6 since under this assumption the numerator and denominator are bounded sums of finite terms. It is technical assumption used to address the difference between two deterministic equivalents that are needed in our work for norm- capacity. In fact, this assumption is used for RFMs in [14] as the authors also face with the issue on the difference between two deterministic equivalents.
Remark:
Based on the above two assumptions, we are ready to deliver the following result, our results can also numerically validated by Fig. Min in Appendix H.2
Theorem D.6 (Deterministic equivalents of the norm of the estimator.). Assume well-behaved
data { (x; {x satisfy Assumption & and Assumption 5 Then for any D, K > O, there exist constants
n. 1/2) and C. C. > O ensuring the following property holds. For any 2 C.D,,K, X if the following condition is satisfied:
A n K
1/23) S K Vn,
37

---

then with probability at least 1 - n2 D, we have that
Pa(n)
10 (n)
B A
B I CZ.DDK
N
vn
log pa(n)"log") 3/2 (n)
VLS N.A
I Cz.D.K
Vn
N,A
Next, we give the proof of Proposition D.4 below.
Proof of Theorem D.6 Part 1: Deterministic equivalents for the bias term.
Here prove the deterministic equivalents of B and V First, decompose B A
into
B Ir (3.88
X X + () AIR X
(2 A nx [X: A2 A)
where A = B.B. A == Σ 1/233333 Σ 1/2, Therefore, using Theorem
B.9 with probability at
least 1 have
- - Ai) s CZ.DDK p2(n) log 3/2
(2(X;
V (Ae; At),
Vn (X; A2, A) nAV Aa)l SZ.D,K pa(n) log 3/2
(A0; A2). (T)
Vn
Combining the above bounds, we deduce that
B
(>.( - nAVV Az)]
Pa(n) log (m)
(Vi(A.:: An) + nAV Ao)) Vn
S C.D...K
Note that
v Vi(A. A (A. A2) = B
For nAA A2), recall that (A,; A) = 1 TH - and according to Definition B.8 and Assumption 3 we have
nAVa A2)
n - (E)
(
(1- T3
and therefore
1 V (A(A:;A + (A A²) S 2 - Ir I(E+,))EE+++)))
< (2C _ D(E
1
< (2C-1) 1) A1) nAV (m))
Then we conclude that
Pa(n)6 log 3/2 (n)
BBS
-BLE S Ca.D.K
Vni
N.
with probability at least - -D
38

---

Part 2: Deterministic equivalents for the variance term. Next, we prove the deterministic equivalent of V First, note that V can be written in terms of the functional 22 defined in Eq. (3
L N (X;
Thus, under the assumptions, we can apply Theorem B.9 to obtain that with probability at least 1 n
no 2 no ( & C2.D px(n) 3/2
20 (A+;
vn
Recall that 22(A++ A)
then we have
N. V C2.D.K pa(n) log
3/2 (n) l/g
VN..
Vn
N.A
with probability at least 1 1-n- P.
D.3 Characterization of learning curves
By deriving deterministic equivalents for the norm in linear regression, we can now analyze learning curves through the lens of norm-based capacity. In certain cases, these learning curves can even be expressed in closed form.
In this section, we first examine the general characteristics of learning curves from a norm-based capacity perspective in Appendix D We then provide precise characterization of these curves in Appendix D.3.2
D.3.1
The shape description of learning curves
We plot the bias and variance components of the test risk over y and norm, Fig. 4(a) and Fig. 4(b] respectively. Note that, our theory (shown in curve) can precisely predict experimental results (shown by points).
Fig. ((a reveals clear
tradeoff in the over weerparameterizee regime (where 7 > 1, as shown in the right portion of Fig. 4(a). Specifically, observe that: The bias exhibits a strictly increasing relationship with the parameter y. ii) The variance demonstrates a corresponding strictly decreasing trend.
However, the under-paranin parametrratttei regime (7 < 1), both bias and variance increase monotonically with y. therefore the bias-variance tradeoff does not exist. In particular, for the min-&2-nome interpolator, since bias equals O, the risk is entirely composed variance.
Because the self-consistent equation differs between the under- and over weer-paaameterized regimes, the learning curve plotted against the norm (see Fig. 4(b) is not single-valued this is due the phase transition between regimes. Specifically, single norm value can correspond to two distinct error levels, depending on whether the model under- or over-parameterized. However, when examined separately, each regime displays one-to-one relationship between test risk and norm.
D.3.2 Mathematical formulation of learning curves
In this section, we give the mathematical formulation of learning curves in several settings of interest. First we give some concrete examples on the relationship between R and N in terms of isotropic features.
Proposition D.7 (Isotropic features for ridge regression, see Fig. 5). Consider covariance matrix Σ La the deterministic equivalents R and N satisfy
[1 - -N()) (19 12 R/ -/--))) NT) a 21211.111 (119112 NR)² - 113311185) A-2 (R -N,)² -119111 do².
Remark: R and S formulates third-order polynomial. When À + 0o, it degenerates to RLS (116.112 / ) when NIS < |1..122 Hence R is monotonically decreasing with respect
do² which is the optimal to NJS, empirically verified by Fig. Besides, if we take X = TB.
39

---

empirical theory
0,0010
Bx
0,0008
risk
0.0006
risk
0,0006
0.0004
0.0004
0.0002
0.0002
0.0000
1.2
1.3
1.5
Y(
norm
(a) Test risk vs. Y (4)
(b) Test risk vs. Norm
Figure 4: The relationship between the risk R. norm N, their bias and variance (BR, VR. BN VN), and the ratio 7 for linear regression model. Training data {(x,, ye) he(m)- sampled from linear model ys x! B_ E,, o² 0.0004, æ; (O, E). with 0y (E) k 1 G2.k: k-//2, The ridge À 0.005. Note that in the padder-prameterized regime (d n), the bias of the test risk is zero.
1000,
regularization parameter discussed in [57 [3], the relationship in Proposition D.7 will become R =1,3-11 - which corresponds to straight line. This is empirically shown in Fig. 5 with == 50. In addition to isotropic features, further examine the relationship under the power-law assumption for the data.
Apart from sufficiently large X and optimal X mentioned before, below we consider min-(2-norn estimator. Note that when À - O, the ridge regression estimator & converges to the min-l2-none estimator Amin- However, the behavior of X, differs between the patemetrrramttrizeee and over- parameterized regimes as - 0. Thus, the min-lz-norm estimator requires separate analysis of the two regimes.
20
rdge aat
1-2
15
10
10
15
20
NJS
Figure 5: Relationship between R and S under the linear model = x 3. + t; with d = 500,
-Ia, 13 10, and の² 1. The dashed line corresponds to the ridgeless regression curve.
Proof of Proposition D.7
According to the formulation of BLS and N,A. in Eq.
55 for Σ la-
we have
(1+ 2.)2 13.112 +
d
X2
(1+
1
113.113
VLS
(1+A.)
B
n11 X.)2
N.A
d
m(1+A.]=
n
(1+A.)
X2
11.3
N
(1 + X_ ) 1.3-112
11+
(I+A.)' 1
n11 + X²)²
m(14A)z
(1+X.)²
40

---

where Xa admits a closed-fome solution
d d
A
n2
4An + (n d 2)
2n
Recall the formulation R and VR. (for test risk) in Eq. 16 for = Ia we have
BLS R (1+A.) 13.12
2
VLS 0² d
X [T+3.)
B.
0² [1+A,)
(1+A.)
R
R,
m(1+X_)²
n
(1+A))
[1+X,)"
Accordingly, to establish the relationship between R and N we combine their formulation and eliminate n to obtair
2( - ) |13. 13)112)d0 = -1133-11 R 11 + R - 2
+ 2. (12 12 + R N 1113
Corollary D.8 (Isotropic features for min-e2-norm interpolator, see Fig. 5 Consider covariance ma- trix Σ Is the relationship between R and NJ from under--arameteritee over-parameterized regimes admit
S 11..1 if d < (underr-parameterizee]]] ( 31. 0²)]² + 1/.02 - ,
R
,0/
For the variance part of R and Ng.. we have VLS Vis For the respective bias part, have
BLS + -B, 1.3.112.
In the under- paader-prameterizeedd regime, the test error R a linear function of the norm N In the wver-parameteriize regime, R4s and N formulates rectangular hyperbola: R decreases with N ND < |3.13 o² while R/ increases with N0o if S/o > 3|3.112
Remark:
Proof of Corollary D.8 According Proposition B.6 and Corollary D.S. for minimum norm estimator and Σ Id for the under-parrameterized regime (d < ni), we have
add
o²d
L 0,
VLS
B |13.112 V
n
n
From these expressions, can conclude that
a2d
o²d N.o
R
=
D
v R.0
d
N B + VLS. = ||8.1|
d
Finally, in the under- paddeerprraeeeeizeedddeee regime, it follows that
R N 1|3.112.
In the wer-parameterized regime (d n), the effective regularization X. will have an explicit formulation as X d-n thus for the bias and variance of the test error, have
13 E A 2B.)
X2
113. (I+A,))
B
||3.
1
Tr An) 2)
d
1
(1+An)²
d
VL8
(
[1+A]
R.0
n1 Tr Tr A,
dl
n
(1+Am]²
and combining the bias and variance, we have
RLS = BSS
R.0
+
VLS R.
||
n
2
dl
12
(56)
'Due to the complexity of the calculations, use Mathematica Wolfram to eliminate n. The same approach applied later whenever elimination is required.
41

---

For the bias and variance of the norm, we have
1
BN. (Bx, 2 Xn1) B.)
113.112
1|..1127
1 An
T'T + VL8
0² (1+>,)
n
71 - Tr( An
[1+Aa]
and combining the bias and variance, we have
N,O
N,O 113.1122 +
(57)
d
Finally, combining Eq. 56) and Eq. (57p. we eliminate n and thus obtain
R V ( o2) oz) +
(113.18+02)2007
By taking the derivative of Rb with respect to N we get
ORLS ON
N (113.113 0²) 3.
(N 2( 3.
0 N + (113.13 + 02)2
From the derivative function, observe that R decreases monotonically with S when Nos |3.113 o², and increases monotonically with N/ when N > 1|3.113 o2.
Relationship for min-62-norm interpolator in the under- under-parameterized regime. Next, we con- sider the min-norm estimator, and we find that for the min-norm estimator, in the mnder-parameterized regime, the relationship between risk and norm linear, and this linearity independent of the data distribution.
Proposition D.9 (Relationship for min-ly-norm interpolator in the under- parameterized regime). The deterministic equivalents R and 5 in under-parameterizze regimes (d n) admit the linear relationship
R = d (N. /TrEE>
Proof of Proposition D.9 According Proposition B.6 and Corollary D.5 for minimum f2-norm estimator, in the under-parameterized regime (d < nt), we have
o²d
T2Tr(E
B
0,
B
1|0.112
VLS N.0
n d
From these expressions, we can conclude that
o2d n d
σ T'
R = R
VL8
N = B + VN = 1|3.
d
Finally, combing the above equation and eliminate n. in the mnder-parameterized regime, it follows that
R d
Tr(E-1) (Nb 113.
(58)
The relationship in the over- peeepaaramteri regime is more complicated. We present it in the special case of isotropic features in Corollary of Proposition D.7 and we also give an approximation in Proposition D.10 under the power-lave assumption.
Assumption 6 (Power-law assumption). For the covariance matrix Σ and the target function G.., we assume that T2. Σ) = aa
and B., k -8/2 E R.
This assumption is close to classical source condition and capacity condition 9 and is similarly used in 45) Assumption 1].
42

---

Relationship under power-law assumption. Instead of assuming Σ = Id. we next consider power-law features in Assumption O and characterize the relationship.
Proposition D.10 (Power-law features for min-ly norm estimator). Under Assumption o in the over-parumeterized regime (d > ni), we consider some special cases for analytic formulation: if and B = O, when d, we have"
VLS
2(V
N.O7
R,0
2 (d
N.o
N.
N. N,O
d=o
d²
Remark: The relationship between Ro and N is still linear in the under--arameteriiedd regime, but quite complex in the wver-parameterized regime.
Proof of Proposition D.10 In the over- pareaaatamtteeeee regime (d > n),, according to Proposition B.6 and Corollary D.5 under Assumption we have
(B,, Σ A, B.)
2 Tr (E,
BR,0
1- n (x x,,))
- TE
T x2,))
R.0
Tr (E=
N,O (B., E(E + X 1) ( Tr 48 E \n1))
o T Σ 1n
VL5
- Tr 2 ②Σ 1n
To compute these quantities, here we introduce the following continuum approximations to eigensums.
d+1
d dk - Σ -,,
(" d k dk
(59)
k-a
o; Am
Jo k-a
An
due to the fact that the integrand is non-increasing function of k. Similarly, also have
d+1
k h22
n
k k-20
ak An) 1 dk < Tr(E (.)
Σ
dk. (60)
o An
(k + An
We consider some special cases that are useful for discussion. When a 1. we have
log(1 dAn + An) log(1 + An) < (N(EE+AA)) log(1 + ddn). An
(61)
An
d
< Tr(E? ( An)
(o + An I + dln
(62)
And + An +
An -
Recall that An is defined by Tr(E + X -1 n. Using Eq.
59
we have
log(1 + ddn)) 2 n.
An
Observe that as n d, An O, allowing to apply Taylor expansion: log(1 ( + ddmn) d {dd2))
2 d
Xn
An
Based on this approximation, An can be expressed as
2(d n) An
d'
TThe symbol z here represents two types of approximations: i) approximation for self consisten equations; ii) Taylor approximation of logarithmic function around (related d).
43

---

In the following discussion, we consider the case n + d. Thus, we have the approximation
d
TrE (,)
THE E An)
=
1 dAn
Then have
V Tr E + Ap 1)
d
0²d
14d.
n2 Tr An
11 14dhn + d(nin 1)
TT (E Am.
(d d An 1tdr
0² (dhn -)
V N,0
An
(E +
2(n d(nin - -1)
n I+dAn
Use these two formulation to eliminate n, we obtain
N,0) )2
R.O
dVLs d2oz
Next we discuss the situation under different 3.
For 3 = 0, we have
+ 1)
An(d- - Jdl
An
d T+dAn
BLS
n2
1- 1--n'Tri TrE 1) 1)-))
a(I+d),)
N Tr<E(E + X, d d
Use these two formulation eliminate n, obtain
2 BW,o)
BLS ~
d2
For 8 1, we have
(E
X I+dAa
nd1
B 1-n TE A An 2) 2
nx1 + ddn))
a(1+dAm)
B.. "=<>' Tr A TrE ( TT(E) ndn
Use these two formulation climinate n, we obtain
2 B/N, )2 2T> Tr(E)2
2 N,O Tr(E))
DLS R d 2dB 2d=Tr(E)
d 2Tr(E)
For 8 = 11, we need to use another two continuum approximations to eigensums
L'd k- + An
dAn log(1 11 + ddn)
Tr((E + 2n Σ
dk
0i An
Tr((E + X,,) = Σ
1
dk
d (2+dA.) 1+dda
2log(1 ddp))
a + Nx,²
ak-a + A,
i=1
Once again, we apply the Taylor expansion, but this time expanding to the third order
1 log(1 + ddn)) x dAn, (d2))) 2 + 3 (din))
Then we have
Tr((E + -1n) ~ dd, log(1 + ddn)
1
d2
3 Xa
~
X2
2
3
44

---

(2+
2log(1 + d)
- _ddt)
TT + X..) ~
1+dAa
A
1 + dAn
Using the approximation sated above, we have
(2 + An, 3)
(2 -3dd -3dd)nn (1+daa))
B R.O
1- 1n
n(l+dA.)
BLS
T+ 1) 2 3
d
Use these two formulation eliminate n, we obtain
216(B (0 - 3 )a 1126d (BN.)) N.o t
N.O 5d
B =
2d (6B d²)
Here we present some experimental results check the relationship between B and N, as well as RR. and VN.0 see Fig. We can see that our approximate relationship on variance (see the red line in ((d)) provides the precise estimation. For the bias (see the left three figures of Fig. 6 our approximate relationship is accurate if BN, is large.
8/4
1/10
1.100
5.0
40
(a) 8 =
(b) 8
(c)
(d) R.0 vs. VIS
Figure 6: The left three figures (a) (b) (c) show the relationship between BR. and BLS when
and 3 takes on different values. The figure (d) shows the relationship between Vž. and VN, when 1. The blue line the relationship obtained by deterministic equivalent experiments, and the red line is the approximate relationship we give.
E Proofs for random feature ridge regression
this section, we provide the proof deterministic equivalence random feature ridge regression in both the asymptotic (Appendix EE.I) and non-asymptotic (Appendix E.2) settings. Additionally, we provide the proof of the relationship between test risk and the E norm given in the main text, as detailed in Appendix E.3
Though the results are for linear regression, we can still use the results for RFMs, which requires some knowledge from Eqs. (27) and (28).
We firstly confirm that Assumption in Appendix B.1 used derive all asymptotic results, can be
replaced by the Hanson-Ve Wright assumption employed in the non-asymptotic analysis. It is evident
that Eqs. (8) and (TOp are obtained directly by taking the limits of Eqs. (27 and (28) oo.
Additionally, a key step in the proof of Eqs. surely negligible, where A is defined
and in involves showing that almost
- 2I) 1
Σ =I)
I+ (n (n=_
m -1; -
with E - E a,o. E_ n E and 2 E R.
In the analysis of (T]. the negligibility of A arises from the assumption that the components of æ; follow a sub-Gaussian distribution, which leads to the Hanson- Wright inequality
P | n, - ur(>) s e <<| + v([Eia)) 2 2e
45

---

In this way, Assumption 4 is also sufficient to establish the negligibility of A.
After obtaining Eqs. (8) and (T0) and the negligibility of A, follow the argument of [ and
derive the rest asymptotic deterministic equivalence.
Finally, with these observations, solely on Assumption 4 to derive all the asymptotic results.
eliminate the reliance Assumption and instead rely
E.1 Asymptotic deterministic equivalence for random features ridge regression
In this section, we establish the asymptotic approximation guarantees for random feature regression in terms of its form based capacity. Before presenting the proof Theorem 3.1 we firstly give the proof of the bias-variance decomposition.
Proof. Here we give the biri-nari decomposition of E. given by
The formulation of E. is
Eg | = E.g |1 Z XT) z yll2.
which admits a similar bias-variance decomposition
E=|lāl = E. Z Z + - (GB, + +
|1 + A1) 2' &
+ 2 E/1 (0., G' Z(Z Z AT) CO.) Tr Z(z' Z (
2(z'
BA APM
Accordingly, we conclude the proof.
Now ready to present the proof of Theorem 3.1 as below.
Proof of Theorem 3.1 We give the asymptotic deterministic equivalents for the norm from the bias
B and variance REE . respectively. provide asymptotic expansions in two steps, by first
considering the deterministic equivalent over G. and then over
Under Assumption T the proof below.
we can apply Propositions B.3 and B.4 B.4and and Corollaries D.2 and D.3 directly in
Deterministic equivalent over G: For the bias term, we use Eq. 13 in Proposition B.4 with T G. Σ F F. A 0.0,, and B F F and obtain
BREN (0.. G Z Z XI) - 2 Ge.)
- =PIr(0,0, (GF FG +pdI GF FG (GF FG +PAI)
Tr(O, G Z(Z Z + AI) -2z GO.)
~ "''r(0,,0, (F" F+ F FFF
(63)
1
+ pu? (F F F(F F(F F+
n df
:11
where U1 defined by 11 (1 ddf (12))
pd (11) and (v1) are degrees of freedom associated
to F F in Definition B.2
For the variance term, use Eq. 54 with in Proposition B.4 A F. F. F and obtain
o2Ir L z Z + A1) 3) = I (zz (zz +X)=
N.
= pP GFF FG (GF FG + pAI) -)
03, Tr(F F(F F F+N1)-2
n -f2((())
46

---

Deterministic equivalent over F: In the next, we aim to eliminate the randomness over F in
Eq. 63 from the bias part. First our result depends on the asymptotic equivalents for df (21) and
(v)
For df, (21). we use Eq. 8 in Proposition B.3 with X F and obtain
( = F F F
F -
( + = - (v2)
where V2 defined by 122(1 (v2))
21 Hence V1 can be defined by 7/1 1 n (v2)) PA
from Eq.
For (v1). we use Eq. 9 in Proposition B.3 with X = F, A B and obtain
d(2(v1)= Tr(F' F(F F - F(F F+GI)=
1
+ p dl2(u2)
=: =:nT(u,,,s))
(64)
For 1= = TT( F F + +411) 3). we use Eq. 52 with F and obtain
Tr(F' F(F F 11 Ta(A v2l) p-
(65)
Then we use Eq. 52 again with X F, 02 0! to obtain the deterministic equivalent of 1
Tr(0.0. [ F + I
v 1) Tr(0.0..' F F +1
1
Ar( v2I) 3)
p df2(12)
1
A_ v21) 0.
p df2(v2)
Further, for I2, use Eq.
11 with A 0.0 and B I, we obtain
2
(F F F (F
1r.0000 (A + +x21)
1
Tr 0 (A + 12 Tr((A + (2))
p dl2(v2)
Finally, combine the above equivalents, for the bias, we obtain
RREM A.A
p0_ A(A + 12 -20
p d
2 Tr 0_ (A 121)
v22 Tr(0.0
Tr((A + v21) -
p
121) (22
p p- d(2((2
TTrAAA + 12 -2).
1
1
p dfz(vz) n (n((v
-0_ A(A 1) -20
p- (V222
P
U20 (A +22 20. 0 A(A + v2l) 20,
Tr(A(A +121
n
p- dfz(U2)
1
1
THAAAA + 121)
p- df2(12)
1- T(v1,12)
00.. A(A + 121) -20m)
p TI (A? + +121)
px(12) 1 (0., (A + 12
+x))) +
1 --((1,
47

---

Similarly, for the variance. using Eq. (64 and Eq. (65 for I3, we have
VN ~ PTY(A vzd)= 9). p- df2(v2) - --n((u
Ex(22)
1 122,
Accordingly, we finish the proof.
In the next, we present the proof for min-&2-now -nom interpolator under RFMs.
Proof of Corollary 3.2 Similar to linear regression, we separate the two regimes p < n and > n well. For both of them, we provide asymptotic expansions in two steps, first with respect to G and then F the under- mnder-parameterizae regime and vice-versa for the over-parameterizes regime.
paramtttraeterriize regime: Deterministic equivalent over For the variance term, we can use Eq. 54) with T = G, Σ = A F F and obtain
DAPK = 0² . Z Z(Z Z A1)
-2 FT GF (FG GF + 2
= =² FIr(F FG (GF FG -PM)
0² TT F(F X1)
n n-p
2² TTFF n p
P
where À defined by
À(1 1 di (A)) pd
(66)
where df, (A) and (ā) are degrees freedom associated to F F. In the under-parammeeriized regime (p < nt), when goes to zero, we have À + and df, (Ā) - p M.
For the bias term, we use Eq. 113 with T
F F. 0.0.. B F" F and then obtain
B%% Tr(O,G Z Z 2 GO.)
PTTOO, GF (FG GF + +pA1) 2F FO.
=yTT(O.0, (GF FG +pXI) GF FG (GF FG +pX))-
+pATTH(0.000 F - - F(F P(F
n-P
~P (FF) PT).0 F (FF
F)) (FF
p
In the next, we are ready to eliminate the randomness over F.
Under- mnder-parameterriee regime: deterministic equivalent over F For the variance term, from []] Sec 3.2] we know that 1/>, is almost surely the limit of Tr (r(FFF")))) thus we have
TY((FFT)-)
1
Xp"
where Ap defined by df, (Ap) = p, where dfi (Ap) and dfg (Ap) are degrees of freedom associated to A. Hence can obtain
d²p
REP N.O
p
A> n P
An p)
48

---

For the bias term, denote D : FA 1/2, we first use Eq. (54) with T = D, E = A
A1/20.0, A 1/2 and obtain the deterministic equivalent of the first term in N
Tr(0.0, F (FF = Tr(A 1/2 T00 D (DAD") ) D)
T
n dl2(Ap)
Then we use Eq. 13 with = D, A, == 0/00 A 1/2 and obtain Tr F (FF')
F) )F)
TTA'' A (DAD") ) D) Tr A(A + +1p)
Then the deterministic equivalent of the second term in 5 is given by
Tr(0.0. - F (FF")-1F) ~ Xp (A + 10.
Finally, combine the above equivalents and we have
NN AAA(A + Xx) 0
P
0 (A + Xp)
0.
p
n (Ap
n p
p(O., (AA + Xp) '..) n TA + A,,
p(O.. (A + Xp) 10.) n - p
Over-parameterized regime: deterministic equivalent over F Denote : A G for the variance term, use Eq. (54) with T = D. D = K and obtain
=
BPP 0² pTr(FF GF (FG GF 3)
02 pT (DKD +
0² PTr(K + AX)
1
p-n n
TT((GAG))+))
p
p-1
where is defined by
1 di (A)) À(1-
pd
(67)
where di, (Å) and (ā)( are degrees of freedom associated to K. In the over-parameterrized regime (p > n),, when goes to zero, we have Î - and d)z(()) - M.
For the bias term, obtain
Eq. (54) with T D. E K, A A G GA and
PTr(O, GF (FG + pAT) - FFG GO.)
N.
-PTr(A GO.0O GJ G2
" + +pX - 2D)
~PTT(A GO.0 G K + AX) -2). 1
p-n n
~ ~TrO0 GT (GAG )
G
p p-n
Over-parameterizee regime: deterministic equivalent over G
For the variance term, we have
IREN N,O
02
p
An
An(p - n)
For the bias term, we have
RRE N.D
Tr(0.0 0_ (A + Amn -
p
-A + An) -
0,
p
p(O,. (A + An) 0-)
p-1 7
Finally, we conclude the proof.
49

---

To build the connection between the test risk and norm for the min- -or-m estimator for random features regression, we also need the deterministic equivalent the test risk below.
Proposition E.1 (Asymptotic deterministic equivalence of the test risk of the min-(z-norm inter- polator). Under Assumption [ for the minimum 22-norm estimator Ouiin we have the following deterministic equivalence: for the muder-parameterieer regime (p < n2), we have
p2 (A + X²1) -0.)
o²p
BPM
R.O
R.O
n n-p p
n n-p p
where >o is defined by TM(A + 1)) ~ p. In the over-parameterized regime (p > n),, we have n2,,, (O., (A + )x11) an11--2,)
ndn (0,, (A + 1, 00)
BREM
+
" Tr(A2(A + 1)n))-2)
p p-n n
T (A + +2,1)
BRR R.0
+
(r(Aa(A 1-11)==1
p p-n
where An defined by Tr(A(A + 1), ~n. n.
For the proof, we separate the two regimes p < n and > n. For both of them, we provide asymptotic expansions two steps, first with respect G and then F in the under-parameteriieed regime and vice-versa for the over-parameterized regime.
Proof of Proposition E.
Under-parameterizer regime: deterministic equivalent over G For the variance term, in the under-parameterized regime, when X 0, the variance term will become yaEM
a²
R.0
Tr(ā F Z t)- Accordingly, using Eq. (12)), we have
DPP o Tr (T(Ap(2 Z Z)
= o² TT(FFF (FG' GF
d² Tr(FF (FF
p
o²p P
For the bias term, it can be decomposed into
|00 - 1/2 F (Z Z+ (Z'
R
0. 2p 1/20p (2'
+ GT Z(Z - 2 AT) -2 GO..
For the second term:
--1/20_ F (Z + -1)-1z GO,, we can use Eq. 12 with T = G,
Σ F F.
A 0.0, F F and obtain
p 1/ F [Z Z \1 Z GO. Tr(0.0 00 F FG (GF FC G
Tr(0.0, F F(F F F+
Tr(000 F (FF) F),
where the implicit regularization parameter À is defined by Eq. 66).
For the third term: 0 GJ Z(z" Z + -1) A Z Z + XI)
Z GO., we can use Eq.
13 with
T = G. Σ F F. A 0.0,, B = F FF and obtain
G.G 2+ (Z Z +
GO,
Tr(0.0, GF GF - FF (FG GF +
G)
=Tr(0.0,G ( FG - GF FF FG (GF FG +G
~Tr(0,0, F F FF F(F F
1
+ F+ Tr(F FF F(F F
F
n p
~ ~T.00,, F + Tr (1 F F
p
p
50

---

Combining the above equivalents, we have
R,0
0 0, Tr(0.0_FF F -
(FFF") F
p n- P
0- 0. 72
p- F (FF n-
Under-parameterized regime: deterministic equivalent over F For the bias term, we can use Eq. 12 with = D FA- 1/2 A = A A 1/2 and obtain
Tr(0.0, (FF)) ) = Tr(A3 D (DADT)-'D) ~ ~Tr(A T 0 (2 + +
0.
Thus, we finally obtain
R,0 0.0. p-P P
A Xp)
0. 10
p
= xpO (A + -p) 0 P
12 (A + Xp O.)
Over-parameterized regime: deterministic equivalent over F For the variance term, with D = FA-1/2 1/2 and K A G/ GA 1/2 we can obtain
RPP = 0² Tr(A Z(z Z +
= TT(FFF FG GF (FG' GF +
a² Tr(DAD DA (2 (DA GTGGA + 3) (DKD + -
= = TT (DKD +pAI)
then we directly use Eq.
(13 with T = --E-K, A, B K and obtain
Tr(DD (DKD + P DKD (DKD +pd1)-1
~ Tr(AK + A + 2) + STAAAA + 21) Tr(K( + (X)
p-n G ( G (GAG GA (T(GA""
1
p-
where the implicit regularization parameter À is defined by Eq. 67
For the bias term, first we have
1/20 g F
Z Z
2 G8. Tr(0,0, F (FG GF + - G) -
AI
-TrA G0,0 A 1/2 (DKK' + +PAI)-1 -D),
then we use Eq. 12 with = D A- A GA.0, 4/2 and obtain
1/22 GB.0. 1/2 DJ (DKD +
(-
Furthermore, we use Eq.
13 with = D, = 4 A/2G G0.0, GJ GA B = A and
obtain
2 Z AF
GO.
=THA GT GO.0 G D DDD -AD' (DKD +PXI)-
~THA GO.0. G G2 + +X1) A(K +\1)-1)
+ + G GO.0. 2/ + -1)-2)
TT((KK+ -
1
p-n
Tr(e.0 TT - (GAG -GG)
+ +Tr(0,0, GJ (G T G (GAGT)-
p
In the next, ready to climinate the randomness over G.
51

---

Overmttrretr regime: deterministic equivalent over G For the variance term, we use to obtain
Eq. (44
df2(An)
Tr(A²G TAAAG"(GAG") n2 (Am)
Then we use Eq.
12 to obtain
+ )n) Tr (GAG GG (T
where A is defined by df, (>m) Hence we have
Tr(A(I G (GAG)) ~ ndn.
Combine the above equivalents, we have
DRRT R.0
df + +0²2 n
df2(2n)
p-
0 Tr + And) -2
Q²n
Tr(A? + Xn -2)
p-n
For the bias term, we first use Eq. 12)
to obtain
Tr(O.0_AG' " ((N)))))(
Moreover, we use Eq. (13 to obtain
Tr(0.0 G
df2(Am)
Tr(O00) (A+ 2 n df2(An)
Accordingly, we finally conclude that
BPP
0 (A + An 1) 20
A, (A + An -10 n
n dl2(An)
ndn (0,. (A -10,) - n1
nA? (0., , (A + 1) -20.)
n Tr (A + 1)
n
E.2
Non-asymptotic deterministic equivalence for random features ridge regression
Here we present the proof for the non-asymptotic results on the variance and then discuss the related results on bias due to the insufficient deterministic equivalence.
E.2.1 Proof on the variance term
Theorem E.2 (Deterministic equivalence of variance part of the lg norm). Assume the features
(Zi)ve(n) and (fi)eem) satisfy Assumption with a constant C. > 0. Then for any D K > there exist constant T7 (0, 1/2) and C. K ensuring the following property holds. For any n.P 2 C.DDKK. X > 0, if the following condition is satisfied:
2 22p (x(n, 3/2 log 3/2 (m) < KVn, px(n,p)2 (0) (o)) log s K K/D,
then with probability least 1 -D p p-D we have that
M AFN CT.D.K Ev(n,p) V..
where the approximation rule given by
(n, p) (x 6 log 52(
px(n,p) pri (p)7 log)(p)
VT
vp
52

---

Proof of Theorem E.2
First, note that N' can be written in terms of the functional 4 defined in
Eq. 37
V A
(Z;
Recall that AF is the event defined in 14
Eq. (79)]. Under the assumptions, we have
P(Ar) 2 21
Hence, applying Proposition B.10 least 1 p
for for F E Ar and via union bound, we obtain that with probability
n (Z:AZ.A A) (F; Ap) pu))
C.D (p. nF: pv1), (68)
and we recall the expressions
= T A pv1) n 4b F; I, pv1)
s (F; (F:AF) ppr)
FF; p()) pTr(FFF (FF + +prr)
From 14 Lemma B.11]. we have with probability at least 1 - p
|PT((FF (FF" + pm1) 2 (u2 --1 s C.D.KK Pry (p) Ea(p) V3 A A-1),
where the approximation rate (p) is given by
Ea(p) P++ (o) (p)
Vp
Furthermore, from the proof of [1 Theorem B.12], we have with probability at least 1 - p-D.
(1 n LF
(1 (2)1
s C.D.rral..pp...000//--TTTT......
Combining those two bounds, we obtain
(F A= pM))
p² 7- (21
p² 2 A A-1 n n (v1,
S S...K. () ())
66 (FFLFFFK 1,1))
Finally, we can combine this bound with Eq. (68) to obtain via union bound that with probability least 1 - n p
n A A) p² p' SC.D..K (E((, +) (D)
1" Va A -1) n - TI
n T(1, 12)
Replacing the rate E, by their expressions conclude the proof of this theorem.
E.2.2 Discussion the bias term
We present the deterministic equivalence of the bias term an informal result, without a Existing deterministic equivalence results appear insufficient to directly establish this desired bias result. While we believe this is doable under additional assumptions, complete proof is beyond the scope of this paper..
In the proof of the bias term, deterministic ciiterrainsticeeuuvvlleeeee for functionals of the form
Tr A (x (x x) X X X
are required. However, such equivalences are currently unavailable, necessitating the introduction of
technical assumptions to leverage the deterministic equivalences of (x; A, X) and (x A, A).
Furthermore, the proof of the bias term in [4] suggests that deriving deterministic equivalences for the bias of the & norm, analogous [14] Proposition B.7], is also required but remains unresolved.
Addressing these gaps in deterministic equivalence is an important direction for future work, particu- larly to establish rigorous proofs for the currently missing results.
53

---

E.3
Proofs on relationship in RFMs
To derive the relationship between test risk and norm for the random feature model, we first examine the linear relationship in the werpparameterize regime. Next, we analyze the case where A = Im with n < m < oo (finite rank), followed by the relationship under the power-law assumption.
E.3.1 Proof for min-norm interpolator in the over-parameterized regime
According to the formulation in Corollary 3.2 and Proposition F. we have for the under- paramcterized regime (p < n),, we have
p(O., A(A 1) -..) Tr(A? (A + 1-
p(O,, (A Ap 1) -0.)
BREH
RAPK N.O
~
p
o²p
REE NOO
VARN
N,O
Xp(n - p)
2 (A + 1p 10))
DAPN ~ RFH o²p
RFN
RRN
n P
In the over-parameterizeed regime (p n1), have
p(O., (A + 1) -..)
02p
DRY
VREM
N,O
p p- 72
A, (p - n)
2 (0,, (A + A, 1)--011 20-)
ndA (z,, (A + 1)
KRPN R,0
DRP R,O
Tr(A? 2 Aa -2)
p
Q²n σ TT IT
DREN R,0
AFK R,U
Tr(A>(A + -
p p-
With these formulations we can introduce the relationship between test risk and norm in the over- parameterized regime as follows.
Proof of Proposition 4.1 In the over- over-parameterized regime (p > n),, we have
N
REHH
p(O.. (A + I
o²p
(0., 1n)) 0²
p
N.a
p-n n
An n)
An
p n
nA (0., (A A. T) -2))
ndn (0, (A + AnI) -
o² O"TH(A?(A + -)
0²n
RPN
+
+
Tr(A? (A 1
p p-n
n Tr(A? + Am p
n2 (0., (A A, (AA (A+
(0.,.. (A x. + +
Tr(A 1),
p-
Then we eliminate p and obtain that the deterministic equivalents of the estimator's test risk and norm, RBP and NBFM in wwerpparameterized regimes (p >> n.) admit
R N (0.. (A 1) - 0.) + o n2 2 (0., (A + A, 1) 20.) + T + Xn
n Tr(Aa An
E.3.2 Isotropic features with finite rank
Corollary E.3 (Isotropic features for min-62-norm interpolator). Consider covariance matrix A Im (n < m < oc), in the pee-parameterized regime (p > n1), the deterministic equivalents REPN and Ngen specifies the linear relationship Eq. 55) as R wn-n NBFM + 2n-m g²
m-n
While in the mnder-parameterizer regime (p- T1), we focus on bias and variance separately
mo²
Variance:
(VRFM)
R.0 N.O +
VAEN
n
n RFN
Bias: (m n B BBN n n0|10~11
n 0.10)_1 (1] ||e. 113) (m + n2| |. || BaF
nm RFM
2n |n| 111)
54

---

Remark: In the under- under-parament parameterized regime,
R.0 and Noo are related by hyperbola, the asymptote Further, for p -> n, have BRFN 2 m= BFMM
of which is VRR == VAN
m--n
2(m-n) m
||0_ 12. see discussion in Appendix E.3
Next we present the proof of Corollary with A Im
Proof of Corollary E.3 Here we consider the case where A = Im. Under this condition, the m definitions of Xp and An above are simplified 1 = and m 1+ n, respectively. Consequently, mn respectively.
Ap and An have explicit expressions given by > = and An n P
First, in the over-parameteriizd regime (p > n), we have
RPH N,0
P PTTx 10.12
ntp
100 11
APN N,O
oanp
p
mp
n))
An(p 1)
(m np 11
nX? (1+A,)
10,12
n 1+
10..1
p(m= - n2)
BRFN R
0, 0.11
[I+A.,]²
p
mlp m1)
0²
m (1+A,)*
Q²n
n2n
V
RFM
R,0
π
(1+AA,)
m
)2
p-
m
n
+
n2
We eliminate p and obtain that the relationship between and
R.0
N,O is
VAEN
71
VAEH
2n
12
m
n
similarly, the relationship between BREM and
NND
BAF
m 72
N.
n
Combining the above two relationship, we obtain the relationship between test risk R and norm Ng as
R
77
71
NRFN
2n m 0²
Accordingly, in the under-parameterizeen regime (p < n), we have
10.11
P PI+Ap 10.11
DAFK
(1++,) 1z
p
p²
P
110.112.
(1+A,)²
m
Nm - p2
Opp
p²p2
RPX N,O
Ap n)
(m
(n p)
n2 1+bp
1011
m - p)
o²p
RFN
0. 12
REM R.0
R
p m(n
n p
Then we eliminate and obtain that, in the undaee-arameterrized regime (p < n), the relationship between VREM and VARK is R.u
N,0
(m 12)
VRRN N.O
((m (m)-n)((VRP)) N.0) 4nmo=
N,0
AFM R.0
2n
which can be further simplified as hyperbolic function
m 2
RRNN RDO)
RRF RFN N.D
VRFX
n
and the asymptote of this hyperbola is R.0
RFN N.O
55

---

Besides, we eliminate and obtain the relationship between R,0
and BN,0 as
|10
1l2n
2/ 112
BN.0
(R.0)
Tt
(BR,0)2100.
( (10.112 11..12n
BN,
4110-112n
BREK
77a
771
Y74
511..13.
B
0| 10.1Bmn
11
BNO
(B
-B
2 11
NN0 m
which can be simplified to
N (m - n (m 8P - n n 02 (m)
BBMM n n210.112) 2m
RRF nm R
(
2m|10.11 1. l1 + n|10. 11
We can find that in this case, the relationship can be easily written
rum (B 10.1 (m( 2n 0. 11 + 72 0, 13
REW
(m n (m,
R n/ ( R,0
0100+11))
Next we will show that when p - n, which also implies that N oc and BRFK oc, this relationship approximately linear.
Recall that the relationship between BAFH and BN.0 is given by BRPK (m-
RRPM and equivalent
n
to RRFK
BBFM = (B We then do a difference and get (m--
nm (BAK - 0.. 10.1 (m,(
(BBFH) R.0
2n 0. 11 + n 0. 2
BREM
f(
RPN R
N,0
(m n) Bm RFX n n (m (m nz
n2 (
m 71
then take R,0
and we get
2n
lim
RPK N,0
((
0
B
+00
771
Finally, organizing this equation and we get
B
REH R.D
RJ
m
72
RPM N_u
2(m - n2)
10.11
E.3.3 Proof on features under power law assumption
Proof of Corollary 4.2 First, we use integral approximation to give approximations to some quanti- ties commonly used in deterministic equivalence to prepare for the subsequent derivations.
According to the integral approximation in 53 Lemma 1]. we have
())++++))) (r(A Can 7) C2) (69)
where Cj and C2 are
π T(a
G sin (5/a)
C2
with C C2.
(70)
a² sin (*/a)*
Besides, according definition of T(v) Appendix B.5
have
(0., (A 12) -1 0.)) Ty. (12) 2 (2r-1)A0
(0. A(A + - = T 1 (12) 2 Cuul (2r-1)A0
When E (0, }), according to the integral approximation, we have
C3 sin((2
π
C4 a sin(2Tr)
2nr
with C3 > Ca.
(71)
56

---

Otherwise, i E E12, 00), we have
1
a(2r 11 < C3 <
((r - +1,
< C4 <
+ 1, with C3 > C4.
a(2r - 1)
a(2r - 1)
For (0., (A + v2) -.)) we have to discuss its approximation in the case r E (0, 2), E [ 1) and
E 12, 00) separately.
(Ca - (Ca-Ca)uB Czus 2r-2 Co.
i E (0, 2);
(0., (A + 12) 12+ -0)) =
if E 2 1): i [1,00).
where 10( Co 20(r-1] + 1.
With the results of the integral approximation above, we next derive the relationship between R and M separately over-parameterized regime (p > n)) and under-parameterized regime (p < n²).
The relationship in over-parameterized regime (p n)
According to the self-consistent equation
1 1+ p
n
V(
n2
+
4X
2
Tr
A (A 12) +12)
p
pv2
p
1/2
2
41 pv2
VI
+
p
4 will approach 0, and In the weerpparamteriieed regime (p n.,, as X 0, for the first equation, puz
Tr(A(A + =2 will converge to n. Consequently, by Eq. (69), 12 will converge to the constant Furthermore, from the second equation, 1/1 will converge to 12211 }). Thus, according to
Eq.
669
have
TT + +2) n, TH(A² + +1)
C2 n, C1
" jatl Tr(A(A + +22 ~ (C1 C2)
~
C
Thus, in the over-parameterized regime
2
Tr (A?(A + v2)
1/
11
12) =
1/2
1/2
Tr (A + 122 2)
n2
+ (1
n
Tr (A2 + 12) -2)
P
p
p
Tr (A (A + -2)
C,
2 + n
p n
x(22) TH<AAA 22)
(C² C2) )))+t
Tr(A2(A + +12)
C2 c n
According to the approximation, we have the deterministic equivalents of variance terms
RPY 0² T(21,22)
002 (C1 (C1 2C2)n + Cap
T()1,2))
(C1 - C2)(2 - n)
= -² 2 x(V2)
n1 )'P
VAEN N,O
23 0²
n 1 T(m,, 12)
p-
Then recall Eq. 770..
we eliminate p and obtain
REN
n
VAF N,O
+ 0² 202- - C
n
VREW + (a 2).
(72)
R.0
C
C-
For the bias terms, due the varying approximation behaviors of the quantities containing 0, for different values of we have to discuss their approximations in the conditions r E (0, 1), E [ and [ oo) separately.
57

---

Condition 1: r. E (0, 2)
1/2
(0, + +x( 12) -0))
R,0
1
T (V1,, 12)
-2ar
n Ci
((C1C--C5C3)) - -
-
(C1- C2) n)
\ Xu3 (0,, (A U2) -0,) x(12) A(A +2)
BPPM
U/ (0., (A 12) 100)
1/1
n 2
T(1,, 122)
1/2
(0,, (A (22) 0.))
11
-2(2r-1) 1)
Csp
Ci
p n
Then we eliminate p and obtain
-a
-2ar
C2C₃ C1Ca
R,,0
C
N,0
C1
C C2
(73)
Condition 2: E 1)
1/2
RPM
[(0.. (A + +2) -2,)) + +x(12)(0..A(A + -12) -20,)
BR,
1 ((11, Uz)
25
C₁
C4n C4n+ +
25
-a(2r-1)
-Cn
C4 C3 (2))
[
-a(2r-1)
(C1- (2) n))
DAFN NNO
= (0., A(A + +222
-20.) 112222200
p
p p- df
+ 2 (10,, (A 12) -2,) + x(12)
A(A 12) -0.)))
x(12)
1 v2)
-a(2r-1)
Ca+ Co
p-n n1
Then we eliminate p and obtain
-1(r-11
RRF
R ~
71
RRY N,O
+
11
C1
C1
C1-C2
-a C..
RFN B
N.O
C₁
-a(2r-1)
The last "R8" holds because
= =((1).
58

---

Condition 3: r E (0)
DRFM R,0
[(0, (A + 12) -2)-)-)) +((u)) A(A + +2) (2))
(V1, V2)
20
Ci
a Can
+ Cap) C2n Co + C2 o1
(C1 Cp) - n)
NN,
(0.. A(A +22) 20.)
p
- df2(12)
x(12)
2 ((0,: (A (A+u) -
0.) + x(22) A(A + -0)))
12)
C4 Co
p
Then we eliminate p and obtain
-a
-C-C + C2C4 C2Cs
RFM R.0
72
RFN N,O
+
π1
ci
C1
C1 - C2
-a
BAFH N,O
C4.
C1
o (2
The last "z=" holds because
o(1).
Combining the above condition E [ 1) and E [1, oo), we have for r E lg. o0)
REF R,O
RM
11
REN N,O
C1.
(74)
C2
C1
From Eqs. 72 to 74). we know that the relationship between R and N in the wer-parameterized
regime can be written as
RF = (*/c.) -a NRPN + C,...,.1
The relationship in param--arameterrize regime (p < n) While in the mnder-parameterized regime (p < n2), When À - 0, Tr(A(A + 12) will converge to which means will converge to (g) and 1 will converge to O, with A +
Accordingly, in the mnder-parameterized regime
(2). p
(1- 11
1/
Tr (A² + 12)
P
+
-
1/2
p
Tr (A? +12) -2)
Tr (A(A + 12) -2)
((12)
2 P ja C1
p- Tr (A + 12) -2)
Then further obtain that, for the variance
T(11,
0² 1- T(V1,
0²
R.0
11 n-p p
RPV 22 ((12)
0+1 n n-p
0²0 0²
n T(u,
For the relationship in the under-parametterized regime, we separately consider two cases, i.e. p < n and p -
59

---

First, we derive the relationship in the under- padre-parameterized regime (p < n) as p - n, based on the relationship in the over over-paramen pre-pparaeteriieed regime. Recall the relationship between VR and VN in the over-parameterizedd regime, as presented in Eq. (72.. given by
VR R
y2
V
APH N,O
+ o² 2) =: hLV
C1
Substituting the expression for N,O0 in the under--parametetized regime into this relationship, we obtain
pa+1
VREH R,0
~
n n-p + +o² 2): 0²
o
C1
then we compute VaEw R,0
?((VEE) and obtain N.D
aa
0² (a 2) pat1
h )
0² p
0²C c-aa n-p p
R,
n P
C1
0² p pa n p p
0² (a -2).
Taking limits on the left and right sides of the equation, we get
lim (VR.0 h(VN,8) 202 p-
Then when p + n,, have
-a
VAEH R.O
~
71
VARY + 0²a.
(75)
C₁
For p < n, we have
n-p n then
RAF 0² T())
2 Q2P
T(11,12)
n
APH 2 x(12) N,O
pa+1
2 2 0
n 1 T(1, U2)
n
Eliminate p and we have
VAPN (0²)
uीI C C++
Next, for the bias term we have
v
DRFN R20
[(0,, (A + 122 -00))= -x(12) + -22)-20))
1
T(11 122
1/2
(0., (A + -10.)
1 ((11 12)
Czugr
n -
1
p(0 A(A + 122 20))
N,O
p dl2(12)
P _x(12) 1 T(u U2)
[10., + (A+,(A+12))
+ x(x -2)
A(A + 122 -00).
p( A(A + +2) -00.)
+ L
Ex(u2)
12
(0,, (A -2)
- dfz(vz)
n
1 T(u, U2)
P
Cau 2ar
12r-1)n0
p Czuz
(2r-1)A0 1jA0
+
&pp
n p
C₁C
p
C3
U2
(2A-1)A0
C
C2
n-P
Then we use the approximation U2 R
( -a and obtain
-a(2rA1)
BRFM
R3
Cg
2A
n
C3
P
n P
C
60

---

B
C1C₁ C1 C2
n p C3
p
V/
(2r-1)
1]A0
CiC₁ C
C3
P
a((2r 1}^0
C2
n-p
Similarly the bias term, we derive the relationship in the mnder-parameteriized regime (p < n) as p - n, based on the relationship in the over-parameterized regime. And we discuss the relationship when (0, 5) and E
[ 20) separately.
Condition 1: Trr E (0, Recall the relationship between RR, and NN, in the over-parameterized regime, as presented in Eq. (73), given by:
RPP
R2O
11
n
B
REH N,O
+
C₁
12
-2or
C2Cs-CiCa f(BN.o)
C2
Substituting the expression for BN,0 in the under- parameterized regime into this relationship,
obtain:
(( N,O
CiC4
P n-p
Ccss
P
-2(2r-1)
+
(
-2ar
C2C3 -
C1
C2
C1
C1 C1
then we compute BRP
f(BN.6) and obtain
R R2O
[(B = Clar
n Cap 2ar
n1
C₁Cs a(3r -((3r-1)n
C1 - C2
C2C3 Cs -2ar
Cap a(2r-1) 1)
n p
Ci C2
To simplify this equation, we begin by computing
Czp
20r
p Cap -a(2-a(r-1)
1. and obtain
n-p
n-p
Csp
p Czp a n) Czp C3p-aapa) -2(2--1)
11 p p
p n
11 p
n1 - p
71 - p
Csp a
np
a pm
n
where ap" ap""-pm is monotonically decreasing in p (monotonicity can be obtained by simple deriva- n-p
tives), and by applying L L'Hôpital's rule, we have:
np pm
amp
lim pn
lim p
(a + 1)n
n
Thus have
lim Csp a
np
pn
(a +)03n 20r
pn
n n-
Thus we have
lim CRar
(Csp- (app00(2-1))0 np ap pn
CiC4
p -a(2r-1) -a
C2Cs CCCs
C1 C2 n 20r
p-
n - p
C1 - C2
-Caor (aa (aa+1)Csm* -2ar
C1
2ar
C2C3 - CiCs -20r
C1 C2
C1 C2
C2
-Caar Cyn
CanarCnn -2ar
2ar
(a++)) C C2
Recall that from Eq.
70 we have
π (aa
C1
C2
ain (7/a)*
a sin (T/a)
thus
x(a-1) sin(%/o)
C2
(a + 1)
(1+
2.
C1
C2
7
77/)
61

---

Finally, we have
-aar
lim p
[BR,0
(BN,)))
20 Czn
Can-2rr =203
22r
C₁
and then the relationship between R,O and BAFN
-a
2
C2CB CiC4
-2
BAFM
N,0
+
C₁
C1 - C2
2C3
C1
(76)
11
REFN N,0
+
2ar
20103 C2Cs - C1C4
Ci
C1 C2
Condition 2: E 0o). In this condition, the approximation of R2o and can be simplified
N,O
to
-a(2A11)
BR
n
Czug
C3
P
C3
n p
n
-
C1
n-
C1
RREM
CiC4
+
p
1/2
(2
1)50
C1 C2
n n
CC
+
PCs
P
Cs
p
-a((2r-1)A0
C
C2
n n-
Ci
C1C
p C3
G C2
n-p
Recall the relationship between B given by:
and B in the over-parameterized regime is presented in
Eq. 74
a C4 =:
B
N,0
C )o)
8FM
C₁
Substituting the expression for BRFK in the under--arameterrized regime into this relationship, obtain:
RFM g g(B,,))
=
n
C1CA
+ p Css PCss -
n
C1.
C
C1-
C2
n p
C1
then we compute R,0
g N.u) and obtain
RPY R2O
g
(B
CsCa
np
pm a
11 C1
(
C1 C2- )
C2C
p
Thus we have
-2
C2C₁
lim
(BRPM
((BN,))
(a+1)Cs
pn
C1
C1 C2
n
(a+1)Ca
C₂ C.
C1
C1 C2
-a
n C
2C4:
and the relationship between
RAN R.0
and BRFM is
a
-a
RFM
R,O
R
C
BND
C
n
C
+
C
2C
(77)
n
Ca.
C
N,0
When p & n, we discuss cases (0, F) and E (1) 2o) separately.
62

---

Ifr E (0, 2) we have n-p = 1 and
____ n-p
= 0, then
a2r
RAH
R Cz
2M11
2 C3
P
Ci
RPH N,O
~
C₁CA
2
1)A0
CiC₁
p
-a(2r-1)
C1
C2
C1
C2
Ci
Then we eliminate p and obtain
BAH
2 C3
C1 C2
21/(2-11) 1)
BBAM 31/(2r-1)
C₁C₁
2r 2 1, we have
n
p a
R
Czvz
C3
n P
n1 -
C2
C₁C₁
p
NNO
C3.
C₁ C2
11
Then we eliminate p and obtain
RREM N,U
C₁C, C1-C2
(C,Cs-CaCs -2CCs C2Cs--CC
Cc,Cs
RFN R,0
RPN
C1-C2
C
BRFM C3
C C1
we know that the relationship between RaP and N in the under- parameterized regime when p + be written
From Eqs.
75 to 77
R ss (1/c.)
N + Cn.a..2
Scaling laws
To derive the scaling laws based on norm-based capacity, we first give the decay rate of the lg norm w.r.t. n.
The rate of the deterministic equivalent of the random feature ridge regression estimator's l norm is given by
N
+ (n Toux + o²n T.... =0 -0 (Ting
where TNrees == Tege A Viey for 0² + 0.
F.1
Variance term
Using Eqs.
42
to
we have
VRFN N,A
= 2D 1 - T(v,, uz)
x(12) ng 100 (u51-14 (0551-11
0 (1-1o(++1(/))///))
Hence, the variance term of the norm decays with with rate
TVp (L. 1 (a + ( man1)
63

---

F.2
Bias term
First, one could notice, using the integral approximation and Eqs. (41 and (42) that
p Thus for the bias term, using Eqs.
(1 (1+ n '0 (15 v= (1+0 9n
(1 (==g(lngg)))))) =0 (1).
p p-df2(12)
(41 to (44)
we have
RFX N.A
O0,A(A + 20.)
p
p (22
x(v2)
+ 2 ((..: (A v22 0.) + x(v2) A(A + u2) 20.1)
1 - T(1,, U2)
2 (12) + n m2 (T
(T (12) + x( ) (122)2++122222) x(12)
1/2 1)A0
n--1111 1001 1/2
(2r-2)A0
n2
0122
- 1- (2)
70 (//1-
1/2
(2r- 1)40
+ 2
1/2
2m12 112 1/022x11) 0 1/2 1//0
0
+ +0
=0
+ 4000::000000000-0444440000000-00
0 (n
Hence, the bias term of the norm decays with n with rate
Te (l.g) = (1A11ggg44 4/a) 12) A).
Recalling that we have
7
Yigy
Tiva N.A
according to which, we obtain the norm exponent NNar as function of and g, showing in Fig. 7 As observed in Fig. 7 Thege is non- non-positive across all regions, indicating that the norm either increases or remains constant with v in every case.
[((2 1)
(a 1)r
(a 13g
a(2r11)+
((t - 1)A
a(Zr
Figure 7: The norm rate "NN""" as a function of (e, q). Variance dominated region colored by orange, yellow and brown, bias dominated region colored by blue and green.
Next for the condition r E (0, 1), we derive the scaling law under norm-based capacity.
Region 1: f and g >>> In this region, according to 14 Corollary 4.1], we have
R θ (n 0) θ (1)
64

---

and according to Fig. we have
N + (n
combing the above rate, we can obtain that
RX
(n a N
Region 2: 20r+1 < a and q
In this region, according 14
Corollary 4.1], we have
R + n 1 (1-
and according Fig.
we have
N (1- (
combing the above rate, we can obtain that
R θ (n- (N
Region 3: 2ar+1 < q < and 9 <
In this region, according to [4 Corollary 4.1], we have
RRP + (1-1))
and according to Fig. we have
(n nn- (1=(t=(a+)))))
N
combing the above rate and eliminate ạ. we can obtain that
REFH - (N u|r
Region 4: 2ar+I and q
In this region, according to 14 Corollary 4.1], we have R θ (n -26))
and according to Fig. we have
N θ (n (2-((1)-1)
combing the above rate, we obtain that
RAFN 2 (n- N
Region 5: < Tar+I and <
In this region, according to [14] Corollary 4.1], we have RRPM θ (n 20gr)
and according to Fig.
we have
N + (n-ag(2)-1))
combing the above rate, we can obtain that
REEV θ (n" (NRFK) - 2-
G Discussion
In this section, we discuss several issues related to the shape of generalization curves, norm control, and model complexity. In Appendix G.I. we examine the shape of generalization curves under various settings, emphasizing when theoretical predictions align with or diverge from empirical observations, particularly across synthetic and real-world datasets. In Appendix G.2, we analyze practical approach to modifying norm by fixing the parameter count and imposing norm constraint, and demonstrate its equivalence to adjusting the regularization strength. Finally, in Appendix G.3 we compare norm-hased capacity with alternative complexity measures, including smoother-based metrics and degrees of freedom, and highlight their limitations in capturing test risk behavior.
65

---

Table Generalization eurves (test loss vs. & norm) under different activation functions in RFMs. Training data {z,, Vi) hie[n] are generated from a ieacher-student model y; ttanh (B, x;)). where 2; wi.d. (0,, Ia) with d = 100. The number of training samples is fixed at n = 300. The random feature map defined as p(æ, w) şo( (w, æ)) with random Gaussian initialization w NO, Ia). where the activation function cp(.) is chosen from ReLU, erf, tanh, or sigmoid. sigmoid
ReLU
erf
tanh
2010
With ridge
2211
2133
A47
130
0.1
0.01
0.1
À 0.1
Ridgeless
= 0.01
10 2 = 10
10
G.1 Discussion on the shape of the generalization curve in Fig.
As illustrated in Fig. (a) and based on empirical observations from 43 Figure 1.12, the test risk in the wer-parameterized regime initially exceeds that of the paraee-ara regime. However, as prrraetattttiiitioonnn increases, the test risk begins to decrease. Eventually, in a sufficiently over- parameterized regime, the test risk becomes lower than in the
case iese-inicaating
that sufficient over- pereaaaamtttiiiiioonnn can outperform under-paramen aaade--prramterizationn
In contrast, our experimental results in Fig. ((b) reveal a slightly different behavior: the learning curve in the pee-paarameteriee regime consistently remains below its under- ander-parameetrized counterpart throughout. This phenomenon presents an intriguing contrast, and the central question we address this section is: What underlying factors cause this fundamental difference in behavior - where in some cases the over-parameterized curve initially above then crosses the under-parameteriized curve, while others it stays strictly lower?
We first conduct experiments on synthetic datasets to validate our theoretical findings. We generate training samples ((x,, yt) he]ae( using a teacher-student model: y: tanh( xx)), where input
features 2; i.id (0, Ia) with dimension d = 100. As demonstrated in Table 4 our experimental results reveal that when the input features follow Gaussian distribution, the test loss curves in the over-parannn pver-parameterized regime consistently lie below those in the under-parameterizee regime, regardless of the activation functions ridge parameter values. This observation aligns perfectly with theoretical predictions.
We further conducted experiments on the FashionMNIST data set [58]. In this practical setting, we observed discrepancy between our experimental results and theoretical predictions.
As in Table 5 for cases with substantial ridge regularization, the test error curves in the over- parameterized regime remained below those in the under- aaader-prrmmterizeee regime, consistent with our synthetic data experiments, However, in the ridgeless case (corresponding to minimum-ly-none interpolators), we discovered different phenomenon:
Initially, the over-parameterized regime exhibited higher test error than the under- parameterized regime.
As the number of parameters increased, the over-parameterized curve crossed under the mndee-parameterized curve. And this interaction formed a distinctive sh-shaped learning curve.
66

---

We attribute this behavior to the non-Gaussian distribution of input images æ in FashionMNIST, which may violates our theoretical assumption like Assumption
Table 5: Generalization curves (test error l2 norm) under different activation functions. Training
data {x y4 [e[n) are sampled from the FashionMNIST data set [58], with imput vectors normalized and flattened to [-1, 1] for = 748. The random feature map is defined as s( w) = ( x)) with random Gaussian initialization from ReLU, erf, tanh, or si iimoodd. The number of training samples is fixed at n 300.
NO0 Ia), where the activation function go(-) is chosen
ReLU
erf
tanh
sigmoid
4:00
With ridge
078
6.0
À 10
X x= 10-1
À = 10
10-3
10
Ridgeless
33
750
X30
65.8 6755
X 10
2 10
10
In summary, while our theoretical framework may not fully capture the generalization behavior when the dataset or activation functions deviate significantly from our assumptions, this does not undermine the core contributions of our work. When the data is well-behaved and aligns with our assumptions, our theory provides highly accurate and effective characterization of the generalization curves under norm-based capacity control in the under-paramettrrized regime.
G.2 Discussion on approaches to modifying the norm
Regarding approaches to controlling model norm, one method involves fixing the regularization strength while varying the model parameter count p. which serves as the primary focus of this paper. Alternatively, one can fix and constrain the weight norm to specific magnitudes. We later show that this approach mathematically equivalent to fixing the parameter count while varying the regularization strength. In this section, we primarily focus the latter approach.
We consider the problem of minimizing the squared loss under an f--nrrm constraint the coeffi- cients:
min y Zall subject to
||l| = B².
To incorporate the constraint, we introduce a Lagrange multiplier À and define the Lagrangian:
C(a, A) = 1ly Za - -²
Taking the gradient of L with respect to a and setting to zero yields the first-order optimality condition:
= y + 22 Za + 2Aa = 0.
Solving this equation gives the solution:
à Z Z + ----- -T subject to
y,
|| B².
Relation to Ridge Regression:
The solution resembles ridge regression, but À is chosen to strictly
satisfy ||á]|| B rather than being hyperparameter. À corresponds one-to-one with B, since
and || |/ are in one-to-one correspondence if X A 0 الlاl
-2y z Z -3 < 0).
DX
67

---

Therefore, we can say that changing the constraint B (the restriction on ||a||2) is equivalent to changing the regularization strength X.
We conducted experiments on the random feature model by fixing the number of training samples and
the aspect ratio 7, and varying the regularization parameter to control the norm of the estimator. We
then plotted the curves showing the relationships among test risk, norm, and À as in Fig. 8 (Figs.
((a)
to wBBc)) for under-paramenn paadteeprameeer regimes and Figs. (8d) to [(f) for over-parameterized regimes), We
can find that the norm is monotonically decreasing with the increasing A, see Figs. 8(b) and ((c) In
fact, the relationship between the estimator's 's norm and the regularization parameter is called C-rurve
21 in both under- and over parameterized (A < 1 or À curve of the regularization parameter À or norm, see Figs. 8(a) and 8(c) and Figs. 8(d) and 8(1)
1). the test risk is always a U-shaped
respectively.
To validate these observations on real data, also conducted complementary experiments using the MNIST data set [30] As shown in Fig. 9 all of the above phenomena persist.
Moreover, in modern ML practice, capacity can be stecred by standard regularization- e.g. weight decay and early stopping-whichs explicitly or implicitly constrain model norms. Optimization itself also induces implicit regularization, notably with SGD. Recent work has begun to precisely characterize test risk under SGD for linear models [45] 44). Extending our deterministic-equui framework to incorporate such optimization effects is both important and challenging, and we leave this for future work.
Estimator
Risk (y=
0.56
Leaice
6.14
inoncil
Rathix
2.24
0.54
0.02
0.50
6.38
10
21
(a) Test risk vs.
(b) Norm vs.
(c) Test risk vs. Norm
Test Risc fy 1.5)
Estimator Norm fly 1.5)
Text Risk vs. Norm (y 1.5)
0.54
0.14
0.12
0.12
6.10
0:36
6:34
16 20 230 "B"""""""""""" '20"
15 15 10""20
(d) Test risk vs. A
(e) Norm vs.
(1) Test risk Norm
for random feature ridge regression. Points in these figures are given by our experimental results, centering around the curves given by deterministic equivalents we derive. Training data { 11) iijjj. n 100, sampled from the model y/i 9. 0. + Eis a² 0.01, 9: N/ I), fa NN A) (g: and f, is defined in Section 2 with (A) = - and 0..k = k 1/100 given by a 1.5, 0.4 in Assumption 2
Figure 8: Relationship between test risk, l norm, and X for different
G.3 Discussion with other model capacities
In this section. we discuss two other model capacities: generalized effective number of parameters and degrees of freedom, which are widely used describe a model's generalization ability. From this discussion, we conclude that these two capacities are less suitable compared to form-based model capacity.
assess model complexity from the perspective of smoother by introducing a variance- based effecciiee-prrmmeee measure, termed the generalized effective number of parameters. In the context of ridge regression, this measure is
Generalized Effective Number of Parameters: The authors 12
68

---

The Greee
375
15.0
12-
(a) Test risk vs.
(h) Norm vs.
Test risk Norm
Figure 9: Relationship between test risk, lp norm, and for different 7 for random feature ridge regression. Points in these figures are given by our experimental results, centering around the curves given by deterministic equivalents we derive. Training data {(x,, y4 hi(m)) 300, sub-sampled from the MNIST data set [30], with feature map given by (zx w) erl ((ar, w)) and N0,
given by
Jest P8
X x)
Tres
where {2fx* JeI. is the set of test inputs. Taking the expectation with respect to the test set yields
Pg Jest = n Ra || X X A) x 113 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" -
which corresponds to the variance of the test risk For the random feature ridge regression, the generalized effective number of parameters can be similarly given by
R scaled by the factor 3.
mlE Ioe ||, lest Z + 1) z = nII= z( z()
P
which corresponds to the variance of the test risk 1BPM scaled by the factor a.
The connection between variance and p enables it to effectively capture the variance of test risk. However, due to the lack of information about the target function (without label information y). this model capacity cannot fully describe the behavior of test risk, as neglects the bias component. This limitation becomes apparent when the test risk is dominated by bias.
Degrees freedom "degrees of freedom"
For linear ridge regression, another measure of model capacity, known as the is defined
9 23
df, (A.) = (EEEEE))) df2(A.) = EE
df, (Ax) and (A.( measures the number "effective" parameters the model can fit. As the regularization strength À increases, model complexity decreases. From Detinition B.8 we have Tr(E(E + A.)=1), implying that an increase in raises X., leading to reduction in df (A.) and (A.).. This suggests that degrees of freedom can, to extent, represent model complexity.
However, it is worth noting that since in linear ridge regression we only vary the number of training data n. according to the self-consistent equation x + we can tell that X. decreases monotonically as n increases, which leads to df, and df, increasing monotonically as n increases. This monotonic relationship with n suggests that when using degrees of freedom measure of model capacity, the double descent phenomenon still exists, as the effective capacity of the model continues increase even beyond the interpolation threshold.
Similar to the generalized effective number of parameters mentioned above, these degrees of freedom also lack information about the target function, making them insufficient for accurately capturing the model's 's generalization ability.
Fig. 10 illustrates the relationship between test risk and different model capacity for linear ridge regression. shows that double descent persists for degrees freedom df, and dí2, indicating that degrees of freedom is not appropriate measure of model capacity.
69

---

200135
18110
500m1
1850
080005
220
4003
810
1032
275
920
1970
(a) Test Risk vs. Norm
(b) Test Risk vs. df1
(c) Test Risk vs. df2
Figure Relationship between test risk and different model capacities. Training data ((2,, yc) he(n) = 1000, sampled from a linear model y/ x B, + Es. o² = 0.0004, æ; ~ NO, Σ), with
Th (E) = k Br,
H
Experiment
To systematically validate our theoretical findings, we conduct comprehensive empirical study across three distinct settings: (1) synthetic datasets (Appendix [H.T). (2) real-world datasets
(MNIST F0saasoiMMIIISSSTSSSSSSS
with random features (Appendix H.2) and (3) two-layer neu-
ral networks with various norm-based capacity measures (Appendix H.3 All experiments can be
conducted on a standard laptops with 16 GB memory.
H.1 Experiment on synthetic dataset
To validate our theoretical framework, we conduct comprchensive experiments synthetic datasets on linear regression Fig. 11 and RFMs in Fig. [2 respectively. The strong agreement between theoretical predictions and empirical results confirms the accuracy of our theoretical analysis.
1064
53005
(a) Risk vs.
(c) Risk Eg
(d) Risk 0.055
Figure 11: Results for the ridge regression estimator. Points in these four figures are given by our experimental results, and the curves are given by our theoretical results via deterministic equivalents. Training data {w,, 31)
wi)hej Jiejjj. d 1000, sampled from a linear model = x B_ E;, o² = 0.0004,
2; (0, E), with on (E) k- B.
H.2 Experiment on real-world dataset
To complement the synthetic experiments presented in Appendix H. we additionally conducted experiments on the MNIST (Fig. 13) and FaShionMNIST (Fig. 14p datasets [30 (58). We applied the empirical diagonalization procedure introduced in [44 Algorithm I] to estimate the key quantities and 0, required for our analysis. The results on these real-world datasets are largely consistent with those observed on the synthetic data: in the mnder-parameterizee regime, the curve of test risk versus norm exhibits U-shape, while in the over pver-parameterzeed regime, the test risk increases monotonically with the norm and is approximately linear for ridge-less regression.
Notably, our random features model can interpreted as a two-layer neural network with fixed first-layer weights W, where the random features sa w:) correspond to the hidden layer activations. This connection motivates our investigation of the Frobenius norm |W| Fig. 15 which captures
the effective capacity of the frozen hidden layer. Furthermore, Fig. 16 examines the path norm
70

---

Hikk
34.
theary
620
0.33
imporial
2.1g
600
nom
(a) Test Risk vs. = p/n
(b) E2 norm vs. 7
(c) Test Risk vs. EG norm
(d) Risk vs. norm (A = 0.001)
Figure 12: Relationship between test risk, ratio Y := p/n, and lg norm of the random feature ridge regression estimator (the regularization parameter is defined in Section Points in these four figures are given by our experimental results, centering around the curves given by deterministic equivalents we derive. Training data {<,; y1) [ejn))
100, sampled from the model y; g 0, + Es.
d² = 0.01, 9i (0, I), f. (o A) (g: and fi is defined in Section 2 with (A) = 9/ and 0., k 1/110 given by 1.5, 0.4 Assumption
natural complexity measure for neural networks that sums over all input-output paths and is defined as
Heath-norm Σ
a w w
This quantity can be interpreted as the product of the norms of the first-layer and second-layer weights. Prior empirical work by (26) demonstrates that among various norm-based complexity measures, the path norm shows the strongest correlation with generalization performance in neural networks. Motivated by this finding, we investigate the relationship between test risk and path norm in our
setting.
Comparing Fig. 13 Fig. 15 and Fig. [6 we observe that the test risk curve aligns more closely with the norm-based capacity of the second-layer parameters in the random feature model, rather than with that of the first-layer weights. Therefore, it is meaningful study the relationship between the test risk and the norm of the RFM estimator, i.c., the second-layer parameters, as this quantity plays a central role in determining the model's effective capacity and generalization behavior.
200
Test ridk
100.0
JOEEE VS.
This thll hinom
115
31.00
15.00
$2.5
3
3932
200
155
5.0
2900
5.0
25
250
500
753
(0é0
1251 1961 1hs 2010
230 530
150
1306 1886 1968 1992 2063
2303 5003 100001500 1750053000
(a) Test risk P
(b) Ey norm p
Test risk l2 norm
Figure 13: The relationship between test risk, l norm and the number of features p. Solid lines are obtained from the deterministic equivalent, and points are numerical simulations, with the different curves denoting different regularization strengths. Training data { 2/) hejn) 300, sub- sampled from the MNIST data set [30), with feature map given by (xx w) = erf( w)) and w (0, I I/d), where 748.
H.3 Norm-based capacity in two-layer neural networks
In this section, we investigate the relationship between test loss and different norm- based capacities for two-layer fully connected neural networks. Specifically, we evaluate four norm-based capacities: Frobenius norm, Frobenius distance, spectral complexity, and path norm. Our empirical results indicate that the path norm the most suitable model capacity among these three norm-based capacities, which coincides with (26).
71

---

Test 1ak
Test
14
18-
500
150
1007
1250 1387
1750
250
502
750
1000
1253
1500 3750 2002
2.0
244
(a) Test risk P
(b) Norm vs.
(c) Test risk vs. Norm
The relationship between test risk, E norm and the number of features Solid lines are obtained from the deterministic equivalent, and points are numerical simulations, with the different curves denoting different regularization strengths. Training data {(z;, 3/) Hi))
Figure 14:
300, sub- sampled from the FashionMNIST data set [58]] with feature map given by co w) erf((2, w)) and NO0 I/d), where d 748.
Fisten nom
230
Text rlat www.errobbaaaacoo
1250
15.-
830
12.0
430
7.5
Hrobetius FOrT of
(a) Test risk vs. p
(b) Frohenius norm vs.
(c) Test risk vs. Frohenius norm
Figure 15: The relationship between test risk, Frobenius norm of W (the weights in the hidden layer) and the number of features p. Training data {[ iiee MNIST data set [30], with feature map given by paxx w) = erf ((x, w) and w ~ NO, I I/d), where 748.
300, sub-sampled from the
200
Tead risk x5.
Path
315
12.
3300
Path
50
25-
256
5.0
1557 3150
1000 1250
m9m
(a) Test risk vs. p
(b) Path norm vs. p
(c) Test risk vs. Path norm
Figure 16: The relationship between test risk, Path norm and the number of features p. Training data ((x, y:) vi)nven)) n 300, sub-sampled from the MNIST data set [30], with feature map given by fp(x, w) cxx((x, w)) and ~ NN I/d), where d 748.
In our experiments, samples from all the 10 classes. To simulate real-world noisy data, a noise level r7 is introduced, meaning 77 100% of the training labels are randomly corrupted.
balanced subset of the MNIST data set [30], consisting of 4,000 training
The model is chosen as two-layer fully connected neural network with parameters including a bias term. The network is initialized using the Xavier initialization scheme and trained using the Stochastic Gradient Descent (SGD) optimizer with a learning rate of 0. and momentum 0.95 over 2,000 epochs. During training, batch size of 128 is used.
72

---

To control model complexity, we vary the number of neurons in the hidden layer, thereby adjusting the number of model parameters. To ensure the robustmess of the results, each experiment is repeated 10 times for each hidden layer dimension. The model's performance is evaluated using the Mean Squared Error (MSE) loss on both the training and test sets.
Frobenius norm: The parameter Frobenius norm is defined as for such two-layer neural networks
2
Mit(fw) =
W 1
where Wj is the parameter matrix of layer j.
Fig. 17 illustratss the relationship between test loss, Frobenius norm Pius and the number of parame- ters p. As the number of model parameters increases, the test loss exhibits the typical double descent phenomenon. However, the Frobenius norm consistently increases monotonically (with a slowdown in the growth rate in the peeepaaraeterizee regime). Consequently, when using the Frobenius norm as a measure of model capacity, the double descent phenomenon remains observable.
more
(a) Test (training) Loss
(b) Miro P
(c) Test Loss Piro
Experiments on two-layer fully connected neural networks with noise level 0.2. The left figure shows the relationship between test (training) loss and the number of the parameters p- The middle figure shows the relationship between the Frobenius norm pho and p. The right figure shows the relationship between the test loss and Uíoo
Figure 17:
Frobenius distance: The Frobenius distance is defined as for such two-layer neural networks
dino-dis( = Σ IW, 1
1=1
where D is the initialization of W
Marnh Cotoo and Bart namber Inameeoo
Vien and 28 Prbberiu water harrerd
Tert Lus Trbenku Oatanns
Namber
2000 2000
12200
200
Rumber ofoormeeer
1000
Friten Dotores
(a) Test (training) Loss vs.
(b) Pizo-di dis VS.
(c) Test Loss VS. Piro
Figure 18: Experiments on two-layer fully connected neural networks with noise level 0.2. The left figure is the same as Fig. 17(a) The middle figure shows the relationship between the Frobenius distance Mfrroddi and p. The right figure shows the relationship between the test loss and (ltro-dis
Fig. 18 illustrates the relationship between test loss, Frobenius distance jiro and the number of parameters p. Different from Frobenius norm, Frobenius distance monotonically increases in the under padder-araettrizeed regime, but shows a decrease the over perammamtteeeized regime. However, since the change of Frobenius distance in the over-pat pee--paramtterieed regime is gentle and even eventually appears to rise, using Frobenius distance as the model capacity does not reflect the generalization capacity of the model.
Spectral complexity: The spectral complexity is defined as for such two-layer neural networks
2
2
W
2/3
3/2
(
Will
2/3
73

---

where || 1.1 denote the spectral norm, and || llp. denotes the (p, q)-momm of a matrix, defined as M p-g = (I ||M llp) llg for M e Rdxm
Mear Cod Leverve fambher heeeetee
Kapn enc Snd Sperre Cora onty Peerstion
Text: u0o Sperre Compledy
250 2000 100
1500
12300
280
100
2007
2000 1256
30
180
(a) Test (training) Loss vs.
(b) Mapee VS.
(c) Test Loss VS. Mapec
Figure 19: Experiments on two-layer fully connected neural networks with noise level 0.2. The left figure is the same as Fig. [7(a) The middle figure shows the relationship between the path norm Mspec and p. The right figure shows the relationship between the test loss and Hspec-
Fig. 19 illusttrates the relationship between test loss, Spectral complexity Mapee and the number of parameters p. We can see that Mspe increases monotonically with p, so the same double descent phenomenon occurs with spectral complexity as model capacity.
Path norm: The path norm is defined
Mpath-nom (fw) E Suo (1)[i).
where w² = w w is the element- wwie square of the parameters, and for all-one vector. The path norm represents the sum the outputs the neural network after squaring all the parameters and inputting the all-one vector.
Fig. 20 illustrates the relationship between test loss, Path norm /ppath and the number of parameters p. Path norm increases monotonically in the under-parameterizer regime and decreases monotonically in the over- wer-parameterized regime. This behavior resembles that of the & norm of random feature estimators. Additionally, the relationship between test loss and path norm forms U-shaped curve in the under-paree paremettraaeeee regime and increases monotonically in the werr-parameterized regime. This pattern is strikingly similar to the relationship between test loss and the &a norm in random feature models.
3
Sambe
Ravar
(a) Test (training) Loss VS.
(b) (path-nomm VS. P
(c) Test Loss Vs. Aputhh-nom
Figure 20: Experiments on two-layer fully connected neural networks with noise level r 0.2. The left figure is the same as Fig. 17(a) The middle figure shows the relationship between the path norm poath-norm and p. The right figure shows the relationship between the test loss and the path norm.
3...
maspetio
Nember
Hamorr
Test (training) Loss vs.
/lpach nomm VS.
(c) Test Loss vs. M4pth nomm
Figure 21: Experiments on two-layer fully connected neural networks with noise level 17 0.1.
Besides, we also conduct experiments with the noise level y = 0.1 and v = 0.3 in Figs. and 22 respectively. We can see that, when the noise level increases, observe stronger peaks in the test
74

---

2001
(a) Test (training) Loss P
(b) /lpachnurmm VS. P
(c) Test Loss VS. Myuth-noom
Figure 22: Experiments on two-layer fully connected neural networks with noise level 7j 0.3.
loss for double descent. However, the trend of test loss is similar at different noise levels with Path norm Mpath-norm as the model capacity, ie.. shows U-shape the pader-parameterized regime and an almost linear relationship at the aver-parameterized regime.
These observations demonstrates the relationship between the test loss and norm, which is general, not limited to RFMs in the main text.
H.4 Norm- based capacity in deep neural networks
To assess whether norm-based capacity view extends beyond lincar/RFM models and two-layer neural networks, we study the relationship between generalization and norm-based capacity on three deep families: (i) 3-layer MLP trained on MNIST with 15% symmetric label noise (varying hidden width), (ii) a 3-layer CNN trained on MNIST with 15% symmetric label noise (varying channels), and (iii) ResNet18 24 trained
110AR-10 with 15% noise (uniform width scaling across blocks). We train to (near) zero training error when feasible, then compute the path norm of the trained network and report test error the clean test set. All runs are reproducible on standard laptop with GB memory. Code, scripts with pinned versions, and trained models are released at g github. com
to facilitate verification and reuse.
MLP. We use MNIST dataset 330 with 16,000 samples and a 25% training split (Muain 4,000, Whest 12,000). The test set remains clean, while the training labels corrupted with 15% symmetric noise: with probability 0.15, each label is replaced by a random class drawn uniformly from {0. (0.....9) .9 \ {y}. The model is a three-layer MLP with ReLU activations, trained with SGD (momentum 0.9). learning rate 0.01, batch size 100, and CrossEntropyLoss for up to 500 epochs.
As shown in Fig. [3 plotting test error against width reproduces the familiar double-descent shape under label noise. W When we instead index model capacity by the path norm of the trained network
(also following 26 as in Appendix H.3).
Ppath norm (Sw) = Σ Sw (1)[1).
and plot test error against path norm (Fig. 23 the curve exhibits a clear phase transition: a U-shaped trend in the under-parameterized regime, followed by a joint decrease of risk and norm once sufficiently over paramttrried.. These observations are consistent with our findings in random feature models.
Training
Tal Ereee Path Norm
Ter Diier
Toe:Ere Erner 25)
2504
Patl Nerm
(a) Test error vs. Width
(b) Path norm vs. Width
(c) Test error vs. Path norm
Figure 23: Experiments on 3-layer MLP.
75

---

We next study three-block CNN on MNIST with the same split and noise. Each block is Convid-Rell with stride and kernel size 3 (the first layer uses kernel size 5), followed by linear classifier; we vary the number of channels to control capacity. We flatten each 28 28 image into 1D signal before applying Convld. Results are qualitatively similar with Conv2d. Training uses the same optimizer and schedule as the MLP.
CNN.
As shown Fig. 24(a) test error as a function of channel count again shows double descent. In contrast, plotting against the path norm (Fig. 24(c) produces the same pattern observed in the MLP: a U-shaped curve in the under- pateerrpaaeteeizee regime and co-decrease of risk and norm when sufficiently over weer-paaameterized, reinforcing the consistency of norm- warm-based capacity across architectures.
Training
Tal Ereee Pulh Norm
10000
Tosk whice
Tee Etrerrrrrao 2013
1000
2504
Chancia
Chunnia
Nera
(a) Test error vs. Channels
(b) Path norm vs. Channels
(c) Test error vs, Path norm
Figure 24: Experiments on 3-layer CNN.
Ercor
Prfh Nerma
Ercor Path
6.
Toal 0.00
(a) Test vs. width
(b) Path norm width
(c) Test vs. path
Figure 25: Experiments on ResNet18.
ResNet18. We further evaluate ResNet18 on CIFAR-10 dataset 29 with 15% label noise, following the setup of OpenAI's deep double descent [40]. In addition to reproducing the reported deep double-descent behavior, we compute the path norm. Fig. 25 shows results across different widths. Based on Fig. 25 we can find that, in the sufficiently over-parameterized regime, the test risk and norm decrease together, ultimately aligning with the şo-curve. This suggests that double descent is a transient phenomenon, whereas the phase transition and the yo-shaped trend reflect more fundamental behavior a suitable model capacity is used.
These results consistently demonstrate the existence of phase transitions, while double descent does not always occur partirraaullllrlly under sufficient over-parameterization. Notably, the şo curve exhibits a U-shaped trend, aligning with our theoretical predictions. All code and replication materials (including our reproduction of OpenAl's deep double-descent results) are available at github. com/yichenblue haceeeeeoooomoooee norm-capacity
76


Reviews:
[{"review_id": "ZNrLSwPmPM", "reviewer": "Reviewer_miNz", "summary": "For the problem of understanding how the test risk scales with model complexity in machine learning, this paper studies the shape of the generalization curve through a norm-based capacity measure. This paper uses deterministic equivalence as a key theoretical tool to characterize the relationship between risk and norm. In addition, this paper verifies that capacity control based on the $\\ell_2$ norm can recover the classic U-shaped curve in RFM, which challenges the double descent behavior. Validation on synthetic data and MNIST shows that the theoretical predictions are consistent with the empirical results.", "questions": "Please refer to the Weaknesses for details.", "limitations": "This work does not seem to have any potential negative societal impact.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. This paper argues that when using a norm-based capacity metric, the learning curve of an over-parameterized deep learning model changes from a \"double-descent\" shape to a U-shaped curve that is more in line with classical statistical intuition. The authors verify this view through theoretical analysis and experiments using random feature models (RFMs).\n\n2. Another key finding of this paper is that in the over-parameterized region, the test risk increases monotonically with the norm capacity. This seems to confirm the conclusion of classical learning theory to some extent: small-capacity models have better generalization performance. This finding is very interesting and seems to suggest that the current mainstream view that \"classical learning theory is not applicable to deep learning\" is a misunderstanding, that is, people's understanding of capacity is not in place.\n\n3. This paper clarifies the essential connection between norm capacity and generalization, reveals the monotonic relationship between the regularization parameter $lambda$ and norm capacity, and provides a new perspective for model tuning.\n\nWeaknesses:\n\nI really appreciate this work, especially some of the insights it brings to the table through experimental phenomena, which, although not new in some ways, have been controversial in the learning theory community. The consistency between the theoretical analysis and experimental verification in this paper has answered some controversies very well. My only concern is the universality of the conclusions of this paper, because the analysis and verification involved are limited to RFM and linear models, lacking empirical evidence for deep models (more than 2 layers), so supplementary experimental verification in deep cases is necessary. In addition, it is necessary to discuss how to apply the control of norm capacity to actual model selection or training strategies (such as early stopping, weight decay).", "was_revised": true, "final_justification": "The additional experiments provided by the authors in their feedback address my concerns about the limitations of their experimental validation. I recommend acceptance on the condition that the authors include more discussion of the relationship between norm capacity control and actual model selection in the final version, as the authors promised in their feedback, because this is very important.", "rebuttal": "We thank the reviewer for the thoughtful feedback and appreciate the recognition of the theoretical-experimental consistency and the insights into generalization. Below, the concern regarding the universality of the conclusions and their applicability to model selection is addressed.\n\n>**Q1:** The conclusions may not be universally applicable, as the analysis is limited to RFM and linear models, lacking empirical evidence for **deep models** (more than 2 layers), so supplementary experimental verification in deep cases is necessary.\n\n**A1:** To validate our theory, according to the reviewer's suggestion, we conducted comprehensive experiments on ResNet18, a three-layer MLP, and a CNN, respectively. \n\nFirstly, we reproduced OpenAI's results [S1] for deep double descent using ResNet18 on CIFAR-10 with 15% label noise, and simultaneously computed the path norm following the definition in [S2]. The table below summarizes the results for various widths in each layer of ResNet:\n\n| ResNet18 Width | 1      | 2      | 4      | 8      | 12     | 16     | 20     | 24     | 28     | 32     | 64     |\n|----------------|--------|--------|--------|--------|--------|--------|--------|--------|--------|--------|--------|\n| Test Error | 0.4405 | 0.2905 | 0.2291 | 0.3203 | 0.3322 | 0.3011 | 0.2695 | 0.2381 | 0.2389 | 0.2317 | 0.1814 |\n| Path Norm      | 245.01 | 149.48 | 119.41 | 249.93 | 514.35 | 691.31 | 612.41 | 537.77 | 442.29 | 390.63 | 248.85 |\n\nBased on this, we can plot test error vs. path norm (we cannot put the figure here due to the NeurIPS rebuttal policy).\nWe can find that, in the sufficiently over-parameterized regime, **the test risk and norm decrease together, ultimately aligning with the** $\\varphi$ **curve**. This suggests that double descent is a transient phenomenon, whereas the phase transition and the $\\varphi$-shaped trend reflect more fundamental behavior if a suitable model capacity is used.\n\nSecondly, we also conducted experiments on a 3-layer MLP and a 3-layer CNN trained on the MNIST dataset with 15% label noise, varying the model width (or number of channels) to study the relationship between test error and path norm. For the MLP, when plotting test risk vs. path norm, we can observe $\\varphi$ curve, which aligns with our findings on RFMs.\n\n| MLP Width         | 2     | 3     | 4     | 5     | 7     | 9     | 12    | 27     | 47     | 61     | 80     | 300    |\n|-------------------|-------|-------|-------|-------|-------|-------|-------|--------|--------|--------|--------|--------|\n| Test Error (%)    | 68.43 | 64.48 | 60.98 | 56.72 | 56.48 | 48.90 | 49.30 | 50.90  | 52.66  | 51.62  | 51.42  | 45.48  |\n| Path Norm         | 216.28| 359.70| 389.95| 537.58| 417.88|1189.49|1230.08|2756.54 |8625.63 |15918.52|8996.63 | 581.03  |\n\n\nSimilarly, in the CNN setting, we have the same observation as below.\n\n| CNN Channels      | 2     | 4     | 6     | 8     | 10    | 12    | 14    | 16    | 20     | 45     | 60    | 80    | 90    | 100   |\n|-------------------|-------|-------|-------|-------|-------|-------|-------|-------|--------|--------|-------|-------|-------|--------|\n| Test Error (%)    | 58.00 | 36.00 | 21.00 | 18.00 | 20.00 | 23.00 | 22.00 | 27.00 | 31.00  | 29.00  | 29.00 | 26.00 | 28.00 | 28.00  |\n| Path Norm         | 9846  |25203  |41980  |61969  |99322  |63675  |45474  |74785  |126608  |19764   | 6198  | 2523  | 1784  | 1338   |\n\n**Conclusion:** These results consistently demonstrate the existence of phase transitions, while double descent does not always occur—particularly under sufficient over-parameterization. Notably, the $\\varphi$ curve exhibits a U-shaped trend, aligning with our theoretical predictions. These findings will be included in the updated version. Besides, we will **release the code, model parameters, and visualizations to foster further research in the community**, which would be helpful to understand the interplay between data, model complexity, and computational resources in modern ML. We will include these results in our updated version.\n\n\n---\n\n>**Q2:** It is necessary to discuss how to apply the control of norm capacity to **actual model selection** or training strategies (such as early stopping, weight decay).\n\n**A2:** Norm capacity can be controlled in practice via standard regularization techniques such as weight decay and early stopping, which implicitly or explicitly constrain model norms. As shown in Figure 2 of our paper, increasing the $\\ell_2$ regularization strength leads to a monotonic decrease in the estimator norm.\n\nTo guide model selection, one can plot **the empirical risk vs. weight decay (i.e., estimator's norm)** as the regularization parameter (in weight decay) varies. This typically yields an **L-curve** [S3], where the “corner” reflects an optimal trade-off between data fitting and model complexity. Selecting the regularization parameter at this corner provides an effective strategy for balancing generalization and capacity. We will include more discussion in our updated version.\n\n---\n\n>Reference\n\n[S1] Preetum Nakkiran, Gal Kaplun, et al. \"Deep Double Descent: Where Bigger Models and More Data Hurt.\" ICLR'20\n\n[S2] Yiding Jiang, Behnam Neyshabur, et al. \"Fantastic generalization measures and where to find them.\" ICLR'20.\n\n[S3] Hansen, Per Christian. \"Analysis of discrete ill-posed problems by means of the L-curve.\" SIAM review 34.4 (1992): 561-580."}, {"review_id": "gn8x8VJCn2", "reviewer": "Reviewer_arei", "summary": "To tackle the challenge of characterizing the double descent learning curve based on the number of model parameters, this paper propose using the $l_2$ norm of the estimator's weights as a more suitable measure of capacity. When the learning curve is plotted against this norm-based capacity, the double descent disappears and is replaced by a more traditional U-shaped curve, aligning with classical statistical intuition. To prove this, the paper uses a mathematical tool from random matrix theory called deterministic equivalence to derive precise formulas for the test risk and the estimator's norm. This analysis is performed for linear regression and Random Feature Models (RFMs), which serve as theoretical stand-ins for two-layer neural networks. The theoretical results are shown to be in excellent agreement with experiments on both synthetic and real-world data.", "questions": "1.\tCan you provide some intuition on how to generalize these results to deep, multi-layer neural network where all parameters are trained?\n2.\tHow can the analyses be generalized to other norms? Are other measures like the \"path norm\" more suitable for complex models?\n3.\tHow do these insights into norm-based capacity translate to tasks beyond regression, such as classification?", "limitations": "1.\tThe theoretical analysis is restricted to linear models and Random Feature Models (RFMs), and does not extend to end-to-end trained deep neural networks.\n2.\tThe study only considers models with closed-form solutions and overlooks the implicit regularization effects introduced by optimization methods such as Stochastic Gradient Descent (SGD). In practice, the choice of optimizer can significantly influence the model norm, which is not captured in the current analysis.\n3.\tThe theoretical guarantees rely on strong assumptions about data structure, such as power-law eigenvalue decay. The paper also shows that when these assumptions are not satisfied—e.g., on real-world datasets—the empirical results can deviate from theoretical predictions.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1.\tStrong Theoretical Foundation: The paper uses the deterministic equivalence in random matrix theory to provide precise, non-asymptotic characterizations of the relationship between estimator norm and test risk. A key strength is the development of new, more general deterministic quantities, which is a technical contribution of independent interest. The study is thorough, covering various model settings, including regularized $(\\lambda>0)$ and min-norm interpolating $(\\lambda=0)$ solutions.\n2.\tClean Result: The key idea that a more appropriate capacity measure (norm) resolves the double descent puzzle is compelling and intuitive. It provides a clear explanation for the success of over-parameterized models without discarding classical statistical result.\n3.\tConvincing Validation: The paper's theoretical predictions are meticulously validated with experiments. The plots consistently show a near-perfect match between the derived theoretical curves and the empirical data points, lending strong support to the analysis.\n\nWeaknesses\n\n1.\tLimited Scope of Models: The primary weakness, which the authors acknowledge, is that the theoretical analysis is confined to linear models and Random Feature Models (RFMs). The result also only holds for the second layer of RFMs, which is far from modern deep neural networks.\n2.\tPracticality of the Findings: The paper suggests that the model norm can be controlled via the regularization parameter, $\\lambda$. However, it also points out that the behavior is different in the under- and over-parameterized regimes, meaning one must know which state the model is in to properly control the norm, which is a practical challenge.\n3.\tDependence on Assumptions: The theoretical results rely on specific assumptions about the data, such as power-law eigenvalue decay (Assumption 2). The authors show that on real-world datasets like FashionMNIST, where these assumptions may not hold, the observed learning curve can deviate from the main theoretical prediction.\n4.\tNovelty Concern: The paper's contribution, while valuable, can be viewed as an incremental extension of the very recent work in reference [14]. The paper heavily leverages the framework, assumptions, and theorems from [14] for its analysis. The core methodological novelty is extending the tools from [14] to derive the deterministic equivalent for the estimator's norm—a different quantity than the test risk studied in [14]. This makes the contribution an insightful application and extension of an existing framework rather than the introduction of a fundamentally new one.", "was_revised": true, "final_justification": "The authors have addressed my concerns. I maintain my original evaluation score for this submission.", "rebuttal": "We thank the reviewer for the constructive feedback and appreciate the recognition of the theoretical depth, clarity of insight, and empirical validation. Below, we provide our point-by-point responses to the comments.\n\n>**Q1:** The analysis is restricted to linear models and RFMs, focusing only on the second layer and lacking applicability to deep neural networks.\n\n**A1:** We acknowledge the theoretical focus on linear models and RFMs. Extension to nonlinear neural networks is non-trivial and remains an open question except for some extremely special cases [S1, S2].\n\nTo validate our theory, we conducted experiments on ResNet18 by reproducing OpenAI's results [S3] on CIFAR-10 with 15% label noise and computing the path norm as defined in [S4] as below.\n\n| ResNet18 Width | 1      | 2      | 4      | 8      | 12     | 16     | 20     | 24     | 28     | 32     | 64     |\n|----------------|--------|--------|--------|--------|--------|--------|--------|--------|--------|--------|--------|\n| Test Error | 0.4405 | 0.2905 | 0.2291 | 0.3203 | 0.3322 | 0.3011 | 0.2695 | 0.2381 | 0.2389 | 0.2317 | 0.1814 |\n| Path Norm      | 245.01 | 149.48 | 119.41 | 249.93 | 514.35 | 691.31 | 612.41 | 537.77 | 442.29 | 390.63 | 248.85 |\n\nBased on this, we can plot test error vs. path norm (we cannot put the figure here due to the NeurIPS rebuttal policy).\nWe can find that, in the sufficiently over-parameterized regime, **the test risk and norm decrease together, ultimately aligning with the** $\\varphi$ **curve**. This suggests that double descent is a transient phenomenon, whereas the phase transition and the $\\varphi$-shaped trend reflect more fundamental behavior.\n\nBesides, we also conducted experiments on a 3-layer MLP and a 3-layer CNN. These results demonstrate similar $\\varphi$-shaped trends in test error versus path norm and further confirm the generality of our findings. For detailed results, please refer to our answer to Reviewer miNz’s Q1.\n\n**Conclusion:** These results concide with our theory by demonstrating the existence of phase transitions, while double descent does not always occur—particularly under sufficient over-parameterization. Notably, the $\\varphi$ curve exhibits a U-shaped trend, aligning with our theoretical predictions. These findings will be included in the updated version. Besides, we will **release the code, model parameters, and visualizations to foster further research in the community**, which would be helpful to understand the interplay between data, model complexity, and computational resources in modern ML. We will include these results in our updated version.\n\n---\n\n>**Q2:** The model norm can be controlled via $\\lambda$. However, the behavior is different in the under- and over-parameterized regimes, meaning one must know which state the model is in to control the norm, which is a practical challenge.\n\n**A2:** Identifying whether a model is under- or over-parameterized is straightforward in practice, as it depends on knowing the number of model parameters and the training sample size. Thus, determining the regime is practically feasible.\n\nTo guide model selection with the proper regularization parameter $\\lambda$ in practice, for under/over-parameterized regimes, one can plot the empirical risk vs. the estimator norm as the regularization parameter (in weight decay) varies, i.e., **L-curve** [S5], respectively. The “corner” of L-curve reflects an optimal trade-off between data fitting and model complexity. **Selecting the regularization parameter at this corner** provides an effective strategy for balancing generalization and capacity. We will include more discussion on practical guidelines in our updated version.\n\n---\n\n>**Q3:** Theoretical results rely on specific assumptions (e.g., power-law eigenvalue decay), which may not hold in real-world datasets.\n\n**A3:** We acknowledge that our theoretical results rely on assumptions such as power-law eigenvalue decay, which may not hold universally. However, these assumptions are standard in the theoretical literature [S6–S8], as they ensure the hypothesis class is well-behaved (e.g., trace-class kernels).\n\nWhile relaxing these assumptions is technically challenging, our empirical results on shallow and **deep** neural networks as mentioned before remain consistent with our theory: double descent is a transient phenomenon, whereas the phase transition and the $\\varphi$-shaped trend reflect more fundamental behavior.\n\n---\n\n>**Q4:** The work mainly extends prior results from [14] to estimator norm, making it an incremental contribution rather than a fundamentally new framework.\n\n**A4:** While we build on the analytical tools developed in [14] for deriving deterministic equivalents, the techniques in [14] are **insufficient to obtain the deterministic equivalent of the estimator norm**. For instance, we generalize their results by deriving expressions of the form $Tr(A X^\\top X (X^\\top X + \\lambda)^{-1})$ \nfor arbitrary PSD matrices $A$, whereas [14] only considered the special case $A = I$.\n\nMoreover, establishing a quantitative relationship between test risk and estimator norm requires nontrivial analysis, including eliminating explicit model size dependence—a key challenge not addressed in [14].\n\nWe do not claim to introduce a completely new proof framework, but our contribution aims to address the fudemental question: how test risk evolves with a suitable model capacity? We provide both theoretical and empirical evidence, and offer new insights beyond prior results.\n\n---\n\n>**Q5:** How can the analyses be generalized to other norms? Are other measures like the path norm more suitable for complex models?\n\n**A5:** Generalizing our analysis to other norms is technically challenging, as it relies heavily on the resolvent structure specific to linear and random feature regression. While recent work has begun to explore deterministic equivalents for general loss functions [S9], the analysis remains considerably more complex and less mature.\n\nHowever, according to the reviewer's suggestions, we have empirically evaluated the path norm in deep networks, as given in **Q1**. This trend closely mirrors our theoretical findings for the $\\ell_2$ norm, suggesting that the norm–risk relationship may generalize beyond $\\ell_2$ and hold for more complex architectures.\n\n---\n\n>**Q6:** How do these insights into norm-based capacity translate to tasks beyond regression, such as classification?\n\n**A6:** Extending the theory from regression to classification is analytically non-trivial due to differences in loss functions and optimization dynamics. A rigorous treatment would require new techniques beyond our current framework.\n\nNonetheless, we present empirical results on classification tasks in Table 5, located in Appendix G (page 65), showing that test error (i.e., classification error rate) exhibits the same qualitative behavior as in regression: a U-shaped curve in the under-parameterized regime and a monotonic increase in the over-parameterized regime. These observations suggest that norm-based capacity control remains relevant and informative for understanding generalization in classification.\n\n---\n\n>**Q7:** The study only considers models with closed-form solutions and overlooks the implicit regularization introduced by optimization methods such as SGD.\n\nA7: Thanks for the reviewer pointing out this. Our work requires closed-form solutions and does not address the effects of optimization dynamics. Some recent studies [S10–S13] precisely charecterize the test risk under SGD for linear models. Extending our deterministic equivalent framework to incorporate such optimization effects is an important and challenging direction, which we leave for future work. We will include these references and discuss the possiblity for study.\n\n---\n\nWe hope our responses provide a better understanding on this work in terms of problem settings, technical contributions, and practical guidelines. We're happy to discuss more if the reviewer has any concerns.\n\n---\n\n>Reference\n\n[S1] Behrad Moniri, Donghwan Lee, et al. \"A Theory of Non-Linear Feature Learning with One Gradient Step in Two-Layer Neural Networks.\" ArXiv:2310.07891.\n\n[S2] Yatin Dandi, Luca Pesce, et al. \"A Random Matrix Theory Perspective on the Spectrum of Learned Features and Asymptotic Generalization Capabilities.\" ArXiv:2410.18938\n\n[S3] Preetum Nakkiran, Gal Kaplun, et al. \"Deep Double Descent: Where Bigger Models and More Data Hurt.\" ICLR'20\n\n[S4] Yiding Jiang, Behnam Neyshabur, et al. \"Fantastic generalization measures and where to find them.\" ICLR'20.\n\n[S5] Hansen, Per Christian. \"Analysis of discrete ill-posed problems by means of the L-curve.\" SIAM review 34.4 (1992): 561-580.\n\n[S6] Leonardo Defilippis, Bruno Loureiro, and Theodor Misiakiewicz. \"Dimension-free deterministic equivalents and scaling laws for random feature regression.\" NeurIPS'25. \n\n[S7] James B. Simon, Dhruva Karkada, et al. \"More is Better in Modern Machine Learning: when Infinite Overparameterization is Optimal and Overfitting is Obligatory.\" ICLR'24.\n\n[S8] Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. \"Asymptotics of Ridge (less) Regression under General Source Condition.\" AISTATS'21\n \n[S9] Kiana Asgari, Andrea Montanari, and Basil Saeed. \"Local minima of the empirical risk in high dimension: General theorems and convex examples.\" ArXiv:2502.01953. \n\n[S10] Courtney Paquette, Kiwon Lee, et al. \"SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality.\" COLT'21.\n\n[S11] Courtney Paquette, Elliot Paquette. \"Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models.\" NeurIPS'21.\n\n[S12] Courtney Paquette, Elliot Paquette, et al. \"Homogenization of SGD in high-dimensions: Exact dynamics and generalization properties.\" Mathematical Programming, 2024.\n\n[S13] Elliot Paquette, Courtney Paquette, et al. \"4+3 Phases of Compute-Optimal Neural Scaling Laws.\" NeurIPS'24."}, {"review_id": "ZqCSQFh2Tm", "reviewer": "Reviewer_nNYU", "summary": "This paper studies the relationship between norm-based capacity and test risk by applying the deterministic equivalent technique from random matrix theory. Using random feature models, the authors precisely characterize this relationship both theoretically and through empirical validation.", "questions": "1. In line 246, can you further explain as to why the bias follows a U-shaped curve, as opposed to the monotonic decrease shown in the classical bias-variance trade-off explanation? Specifically, what is the mechanism that causes a model's attempt to fit training data more closely to result in higher bias? The references shown in the sentence do not seem to discuss this in detail.\n2. A natural question to ask is that, under what conditions does the test error curve in the overparameterized regime transition from being consistently below its underparameterized counterpart to above it ( $\\varphi$ -shaped curve) and vice versa? It would be interesting to touch on this point.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths\n1. The paper is clearly written and is methodically presented. The author's claim are sufficiently supported by formal mathematical proofs and are validated through empirical testing via synthetic and real-life datasets.\n2. The proposed theory reveal that, under specific assumptions about the data, the test curve in the overparameterized regime consistently below the underparameterized test curve. This finding is novel in my opinion as it differs from the standard double descent phenomenon, where a \" $\\varphi$ \" shaped test curve is typically observed.\n\nWeaknesses\nNA", "was_revised": true, "final_justification": "Thank you for your response. The author has addressed all my questions, and I am keeping my score.", "rebuttal": "We thank the reviewer for the positive evaluation and are pleased that the clarity, theoretical rigor, and empirical validation of our work were well received. Below, we provide our point-by-point responses to the comments.\n\n>**Q1:** Further explain as to why the bias follows a U-shaped curve, as opposed to the monotonic decrease shown in the classical bias-variance trade-off explanation? Specifically, what is the mechanism that causes a model's attempt to fit training data more closely to result in higher bias?\n\n**A1:** We thank the reviewer for the insightful question. The U-shaped behavior of the bias in the under-parameterized regime arises due to the interaction between model capacity and the conditioning of the feature representation. To be specific,\n\n- **In the low-capacity regime** ($p \\ll n$), increasing the number of random features improves the model’s ability to approximate the target function $f^\\star$. Each additional feature offers a new direction in function space, leading to better alignment with $f^\\star$ and reducing bias.\n- **Around $p = O(\\sqrt{n} \\log n)$**, this number of random features is theoretically proved to be sufficient for appromating $f^\\star$ well [S1], yielding the lowest bias.\n- **As $p \\to n$** (high-capacity regime), the kernel matrix becomes ill-conditioned. The model starts amplifying high-frequency components and fitting noise in the feature space, which degrades the alignment with $f^\\star$ and increases bias.\n\nThis intuition can be also formalized in our deterministic equivalence analysis. Under Assumption 2 (power-law spectrum) and the scaling $p = n^q$, $\\lambda = n^{-(\\ell - 1)}$ with $q, \\ell > 1$, we derive the following asymptotic expressions (Appendix E.3.3):\n\n- **When $p \\ll n$**, $\\text{Bias} \\approx C_3 \\left( \\frac{p}{C_1} \\right)^{-2\\alpha r}$, which decreases with $p$, as expected.\n\n- **When $p \\to n$**, $\\text{Bias} \\approx \\frac{n}{n - p} \\cdot C_3 \\left( \\frac{p}{C_1} \\right)^{-\\alpha(2r \\wedge 1)}$, with a positive derivative w.r.t. $p$ near $p = n$, indicating a **monotonic increase** in bias as the model becomes nearly interpolating.\n\nThus, while classical bias-variance trade-offs assume monotonic bias decay, our setting reveals a **bias increase near interpolation threshold**, due to kernel ill-conditioning and projection distortion—resulting in a **U-shaped curve** in the under-parameterized regime.\n\n\n---\n\n>**Q2:** Under what conditions does the test error curve in the overparameterized regime transition from being consistently below its underparameterized counterpart to above it (\"$\\varphi$\"-shaped curve) and vice versa?\n\n**A2:** This is an interesting question! As shown in Appendix G.1, the transition to a “$\\varphi$”-shaped curve depends on the data distribution, regularization, and to a lesser extent, the activation function.\n\nFor Gaussian inputs (synthetic data), the over-parameterized test error consistently stays below the under-parameterized regime, aligning with our theory. On real data like FashionMNIST, we observe a $\\varphi$-shaped curve in the ridgeless case, where test error initially rises before decreasing. With sufficient ridge regularization, the over-parameterized curve remains below throughout.\n\nThese results suggest that deviations from our theoretical assumptions (e.g., independent feature inputs) play a key role in shaping the test error curve. Extension to the setting of correlated features requires additional efforts and new technical tools, leaving as a future work.\n\n---\n\n>Reference\n\n\n[S1] Alessandro Rudi, Lorenzo Rosasco. \"Generalization Properties of Learning with Random Features.\" NeurIPS'17."}, {"review_id": "WlSFv78ef0", "reviewer": "Reviewer_1YVx", "summary": "The paper explains the double descent phenomenon for RFM from a theoretical perspective. Specifically, a simple neural network model was considered and the relationship between test error and network norm was calcualted.", "questions": "(1): The network and data used in the paper is simple, even close to a linear model, because the author only analyzed the linear function in the output layer of RFM, which can directly help derive the optimal formula (1) and simplify the calculation. And the label $y$  is also selected by linear with noise. However, commonly used neural networks and data are highly nonlinear, does your conclusion help us understand the  phenomenon of double decline in general situation?\n\n(2): Is RFM being used in some field nowadays? Some examples?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe theory presented in this article is novel and undoubtedly has helped us further understand the double descent  phenomenon for RFM. \n\nWeakness:\n\n$The\\ writing\\ is\\ not\\ good\\ enough,$ the author has placed too much basic settings in the appendix, which is not good, if only read the  main text, it will be hard to understand the paper.\n\n$The setting is too simple.$ From the author's perspective, this is essentially a variant of a linear problem. The author needs to discuss how this differs from the classical linear problems?\n\n$Need\\ more\\ References$, such as:《On the Double Descent of Random Features Models Trained with SGD》,nips2022.", "was_revised": true, "final_justification": "I will keep my score.", "rebuttal": "We thank the reviewer for acknowledging the novelty of our contribution. Below, we provide our point-by-point responses to the comments.\n\n>**Q1:** The writing is not good enough, too much basic settings is places in the appendix, which is not good, if only read the main text, it will be hard to understand the paper.\n\n**A1:** We thank the reviewer for checking the appendix. According to the reviewer's suggestions, we will include more preliminaries and proof sketches from the appendix into the main text for better readability, while keeping technical details in the appendix. We also plan to enhance the overview in the introduction to better guide the reader through the paper's structure.\n\n---\n\n>**Q2:** The setting is too simple. From the author's perspective, this is essentially a variant of a linear problem. The author needs to discuss how this differs from the classical linear problems?\n\n**A2:** The results for RFMs differ from those of linear models in two key aspects: i) the structure of the deterministic equivalents; ii) the nature of the risk-norm relationship.\n\nFirstly, different from classical linear models only involving with data randomness, the random feature model (RFM) involves the random nonlinear feature mapping, leading to two sources of randomness—**data sampling and random feature initialization**. This makes deriving deterministic equivalents substantially more challenging with two self-consistency equations, leading to two effective regularization ($\\nu_1$, $\\nu_2$) for each source of randomness in the derivation of deterministic equivalence.\n\nFor comparison, we have provided theoretical results for linear regression in Appendix D. To illustrate the differences in structure and complexity, we take the bias term of the risk and the norm as an example. To be specific, \n\n$B^{RFM}\\sim\\frac{\\nu_2^2}{1-\\Upsilon(\\nu_1,\\nu_2)}[\\langle\\theta_*,(\\Lambda+\\nu_2I)^{-2}\\theta_*\\rangle+\\chi(\\nu_2)\\langle\\theta_*,\\Lambda(\\Lambda+\\nu_2I)^{-2}\\theta_*\\rangle],$\n\n$B^{LS}\\sim\\frac{\\lambda_*^2\\langle\\beta_*,\\Sigma(\\Sigma+\\lambda_* I)^{-2}\\beta_*\\rangle}{1-n^{-1}Tr(\\Sigma^2(\\Sigma+\\lambda_*I)^{-2})},$\n\nSimilarly, for the bias term of the estimator norm, we have:\n\n$B^{RFM}\\sim\\frac{p\\langle\\theta_*,\\Lambda(\\Lambda+\\nu_2I)^{-2}\\theta_*\\rangle}{p-Tr(\\Lambda^2(\\Lambda+\\nu_2I)^{-2})}+\\frac{p\\chi(\\nu_2)}{n}\\cdot\\frac{\\nu_2^2\\left[\\langle\\theta_*,(\\Lambda+\\nu_2I)^{-2}\\theta_*\\rangle+\\chi(\\nu_2)\\langle\\theta_*,\\Lambda(\\Lambda+\\nu_2I)^{-2}\\theta_*\\rangle\\right]}{1-\\Upsilon(\\nu_1,\\nu_2)},$\n\n$B^{LS}\\sim\\langle \\beta_*,\\Sigma^2(\\Sigma+\\lambda_* I)^{-2}\\beta_*\\rangle+\\frac{\\lambda_*^2\\cdot\\langle\\beta_*,\\Sigma(\\Sigma+\\lambda_* I)^{-2}\\beta_*\\rangle\\cdot Tr(\\Sigma(\\Sigma+\\lambda_* I)^{-2})}{ n-Tr(\\Sigma^2(\\Sigma+\\lambda_* I)^{-2})}.$\n\nIn the $p\\to\\infty$ limit, $\\nu_1$ and $\\nu_2$ in the RFMs converge to a single value $\\nu_\\kappa$. Consequently, $\\Upsilon \\to n^{-1} Tr\\left( \\Lambda^2(\\Lambda + \\nu_\\kappa I)^{-2} \\right)$, and $\\chi \\to 0$. Under this limit, the expressions for both the risk and the norm in RFMs reduce to those of linear regression, with the feature covariance matrix $\\Sigma$ effectively replaced by $\\Lambda$. This highlights that despite the structural differences, RFMs reduce to linear regression in the kernel limit, revealing a fundamental connection between the two models.\n\nSecondly, both RFMs and linear regression exhibit U-shaped trends in their risk–norm curves, but their behaviors in different regimes are exactly reversed: RFMs show a U-shape in the under-parameterized regime and monotonic increase in the over-parameterized regime, whereas linear regression shows the opposite.\n\nTo illustrate this contrast, we refer to Proposition 4.1 for RFMs, which shows a linear relationship\n\n$R=\\lambda_n N + C$\n\nfor min-norm estimator within the over-parameterized regime (fully characterizing the curve in the under-parameterized regime remains analytically intractable). And for linear regression, Proposition D.8 (Appendix D.3.2) provides a closed-form expression for the risk–norm curve:\n\n$R=\\begin{cases}N-{||\\beta_*||}^2,&\\text{if} d<n\\\\\\\\\n\\sqrt{[N-({||\\beta_*||}^2-\\sigma^2)]^2+4{||\\beta_*||}^2\\sigma^2}-\\sigma^2,&\\text{otherwise}\\end{cases},$\n\nwhich is linear in the under-parameterized regime and takes the form of a hyperbola in the over-parameterized regime. \n\nDespite these differences, **the core findings remain consistent across both models**: phase transitions are present, double descent does not occur, and the learning curves exhibit a U-shaped trend. This suggests that our conclusions are not limited to linear settings, but extend to more complex models as well.\n\n---\n\n>**Q3:** Need more references, such as:《On the Double Descent of Random Features Models Trained with SGD》,nips2022.\n\n**A3:** We thank for the reviewer for pointing out this paper that provides a nice upper bound for RFF with SGD. Our current work does not tackle the optimization dynamics. Providing a **precise charecterization** of the test risk under (S)GD via deterministic equivalence, is highly nontrivial and often requires significantly more complex techniques. For instance, recent work [S1,S2] precisely charecterize the test risk under SGD in linear regression settings. We will cite these references and leave the SGD analysis as future work.\n\n---\n\n>**Q4:** The network and data used in the paper is simple, even close to a linear model. However, commonly used neural networks and data are highly nonlinear, does your conclusion help us understand the phenomenon of double decline in general situation?\n\n**A4:** To validate our theory, apart from the existing experimental validation for two-layer neural networks in Appendix H.3, we also conducted comprehensive experiments on ResNet18, a three-layer MLP, and a CNN, respectively. \n\nFirstly, we reproduced OpenAI's results [S3] for deep double descent using ResNet18 on CIFAR-10 with 15% label noise, and computed the path norm following the definition in [S4]. The table below summarizes the results for ResNet:\n\n|ResNet18 Width|1|2|4|8|12|16|20|24|28|32|64|\n|-|-|-|-|-|-|-|-|-|-|-|-|\n|Test Error |0.4405|0.2905|0.2291|0.3203|0.3322|0.3011|0.2695|0.2381|0.2389|0.2317|0.1814|\n|Path Norm|245.01|149.48|119.41|249.93|514.35|691.31|612.41|537.77|442.29|390.63|248.85|\n\nBased on this, we can plot test error vs. path norm (we cannot put the figure here due to the NeurIPS rebuttal policy).\nWe can find that, in the sufficiently over-parameterized regime, **the test risk and norm decrease together, ultimately aligning with the** $\\varphi$ **curve**. This suggests that double descent is a transient phenomenon, whereas the phase transition and the $\\varphi$-shaped trend reflect more fundamental behavior.\n\nBesides, we also conducted experiments on a 3-layer MLP and a 3-layer CNN. These results demonstrate similar $\\varphi$-shaped trends in test error versus path norm and further confirm the generality of our findings. For detailed results, please refer to our answer to Reviewer miNz’s Q1.\n\n**Conclusion:** These results concide with our theory by demonstrating the existence of phase transitions, while double descent does not always occur—particularly under sufficient over-parameterization. Notably, the $\\varphi$ curve exhibits a U-shaped trend, aligning with our theoretical predictions. These findings will be included in the updated version. Besides, we will **release the code, model parameters, and visualizations to foster further research in the community**, which would be helpful to understand the interplay between data, model complexity, and computational resources in modern ML. We will include these results in our updated version.\n\n---\n\n>**Q5:** Is RFM being used in some field nowadays? Some examples?\n\n\n**A5:** Random Feature Models (RFMs) were originally proposed to accelerate large-scale kernel methods by approximating kernels via low-rank random projections [S5]. This idea was later adopted in linear attention mechanisms for Transformers, where the softmax function is closely related to an exponential kernel; see [S6, S7] for details. A survey [S8] provides an overview of this connection.\n\nMore recently, the concept of low-rank random projection has also been applied to parameter-efficient fine-tuning techniques such as LoRA [S9] and its variants [S10]. For instance, [S10] leverages random features and learns their combination coefficients for fine-tuning. Notably, these random features can be generated on-the-fly using random number generators, significantly reducing memory overhead.\n\nWe contend that RFMs retain both theoretical significance and practical relevance, even in the current era dominated by large language models.\n\n---\n\n>Reference\n\n\n[S1] Courtney Paquette, Elliot Paquette, et al. \"Homogenization of SGD in high-dimensions: Exact dynamics and generalization properties.\" Mathematical Programming, 2024.\n\n[S2] Elliot Paquette, Courtney Paquette, et al. \"4+3 Phases of Compute-Optimal Neural Scaling Laws.\" NeruIPS'24.\n\n[S3] Preetum Nakkiran, Gal Kaplun, et al. \"Deep Double Descent: Where Bigger Models and More Data Hurt.\" ICLR'20\n\n[S4] Yiding Jiang, Behnam Neyshabur, et al. \"Fantastic generalization measures and where to find them.\" ICLR'20.\n\n[S5] Ali Rahimi, Benjamin Recht. \"Random features for large-scale kernel machines.\" NeurIPS'07\n\n[S6] Krzysztof Choromanski, Valerii Likhosherstov, et al. \"Rethinking attention with performers.\" ICLR'21\n\n[S7] Hao Peng, Nikolaos Pappas, et al. \"Random feature attention.\" ICLR'21\n\n[S8] Fanghui Liu, Xiaolin Huang, et al. \"Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond.\" IEEE Transactions on Pattern Analysis and Machine Intelligence 44.10 (2021): 7128-7148.\n\n[S9] Edward J. Hu, Yelong Shen. \"LoRA: Low-Rank Adaptation of Large Language Models.\" ICLR'22.\n\n[S10] Koohpayegani, Soroush Abbasi, et al. \"NOLA: Compressing LoRA using Linear Combination of Random Basis.\" ICLR'24."}]

Author rebuttal:

Meta-review: The paper revisits the problem of scaling of the test risk with the model complexity adopting a new norm-based capacity measure. By means of such a new measure, a more traditional U-shaped curve for the risk is found and the double-descent phenomenon disappears. The analysis, performed for linear regression on a random feature model, is verified by means of numerical experiments on both synthetic and real data. The paper has been appreciated for its clear and strong theoretical arguments, but suffer some limitations, such as the very simple set-up and strong theoretical assumptions on both the architecture and the data structure. Nevertheless, the Reviewers expressed unanimous appreciation for the work in light of the fact that it offers new insights on the problem, and the theoretical arguments are supported in more general settings by numerical experiments: I therefore recommend the authors to integrate in the paper such experiments. I recommend therefore its acceptance.
Decision: Accept (poster)