Model, sample, and epoch-wise descents: exact solution of gradient flow in the random feature model
Authors: Antoine Bodin
Nicolas Macris
Venue: NeurIPS 2021 Poster (2021)
Keywords: Random Feature Model
Gradient Flow
Gradient Descent
Double Descent
Epoch-wise Double Descent
Random Matrix
Linear Pencil
Cauchy Integrals
High-dimensional Limits
Stieltjes Transform

Abstract: Recent evidence has shown the existence of a so-called double-descent and even triple-descent behavior for the generalization error of deep-learning models. This important phenomenon commonly appears in implemented neural network architectures, and also seems to emerge in epoch-wise curves during the training process. A recent line of research has highlighted that random matrix tools can be used to obtain precise analytical asymptotics of the generalization (and training) errors of the random feature model. In this contribution, we analyze the whole temporal behavior of the generalization and training errors under gradient flow for the random feature model. We show that in the asymptotic limit of large system size the full time-evolution path of both errors can be calculated analytically. This allows us to observe how the double and triple descents develop over time, if and when early stopping is an option, and also observe time-wise descent structures. Our techniques are based on Cauchy complex integral representations of the errors together with recent random matrix methods based on linear pencils. 

Model, sample, and epoch-wise descents: exact solution of gradient flow in the random feature model
Antoine Bodin
&
Nicolas Macris
Communication Theory Laboratory, School of Computer and Communication Sciences,
Ecole Polytechnique Fédérale Lausanne antoine bodingepfl... ch, nicolas. macris@epf1.ch
Abstract
Recent evidence has shown the existence of so-called double-descent and even triple-descent behavior for the generalization error of deep-learning models. This important phenomenon commonly appears in implemented neural network ar- chitectures, and also seems to emerge in epoch-wiss curves during the training process. recent line of research has highlighted that random matrix tools can be used to obtain precise analytical asymptotics of the generalization (and training) errors of the random feature model. In this contribution, we analyze the whole temporal behavior of the generalization and training errors under gradient flow for the random feature model. We show that the asymptotic limit of large system size the full time-evolution path of both errors can be calculated analytically. This allows us to observe how the double and triple descents develop over time, and when early stopping an option, and also observe time-wise descent structures. Our techniques are based on Cauchy complex integral representations of the errors together with recent random matrix methods based on linear pencils.
Introduction
Deep learning models have vastly increased in terms of number of parameters in the architecture and data sample sizes with recent applications using unprecedented numbers with as much as 175 billions parameters trained over billions of tokens [I]. Such massive amounts of data and growing training budgets have spurred research seeking empirical power laws to scale model sizes appropriately with available resources 2) and nowadays is common wisdom among practitioners that "larger models are better". This ongoing trend has been challenging classical statistical modeling where it is thought that increasing the number of parameters past an interpolation threshold (at which the training error vanishes while the test error usually increases) is doomed to over-fit the data (3]. We refer to 4 for recent extensive discussion on this contradictory state of affairs. Progress towards rationalizing this situation came from series of papers [ 6 8 9 10 [I evidencing the existence of phases where increasing the number of parameters beyond the interpolation threshold can actually achieve good generalization, and the characteristic U curve of the bias variance tradeoff is followed by "descent" of the generalization error. This phenomenon has been called the double descent and was analytically corroborated in linear models [12 13
15 16 as well as random feature (RF) (or random feature regression) shallow network models 17
14
18 19 20) Many of these works provide rigorous proofs with precise asymptotic expressions of double descent curves. Further developments have brought forward rich phenomenology, for example, a triple-descent phenomenon [21] linked to the degree of non-linearity of the activation function. Further empirical evidence [22] has also shown that a similar effect occurs while training (ResNet 8s on CIFARIO trained using Adam) and has been
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

called epoch-wise double descent. Moreover the authors of [22] extensively test various CIFAR data sets, architectures (CNNs, ResNets, Transformers) and optimizers (SGD, Adam) and classify their observations into three types of double descents: (i) model-wise double descent when the number of network parameters is varied; (ii) sample-wise double descent when the data set size varied; and (iii) epoch-wise double descent which occurs while training. We wish to note that sample-wise double descent was derived long ago in precursor work on single layer perceptron networks [23] [2). An important theoretical challenge is to unravel all these structures in unified analytical way and understand how generalization error evolves in time.
In this contribution we achieve a detailed analytical analysis of the gradient flow dynamics of the RF model (or regression) in the high- -igh-simeniinaa asymptotic limit. The model was initially introduced in (2 as an approximation of kernel machines; more recently it has been recognized as an important playground for theoretical analysis of the model-wise double descent phenomenon, using tools from random matrix theory 17 18 26]. Following 117 we view the RF model as 2-layer neural network with fixed-random-fisse wiriooom---ssttee----.aee less--layr-wwightt and dynamical second layer learned weights. The data given by training pairs constituted of d-dimensional input vectors and output given by a linear function with additive gaussian noise. The data is fed through N neurons with a non-linear activation function and followed by one linear neuron whose weights we learn by gradient descent over quadratic loss function. The nigh-dimensional asymptotic limit is defined as the regime n, d, N - +o0 while d - v and à + 6. As the training loss is convex the least-squares predictor (with Moore-Penrose inversion) gives the long time behavior of gradient descent. This has led to the calculation of highly non-trivial analytical algebraic expressions for training and generalization errors which describe (model-wise and sample-wise) double and triple descent curves 11 21). However, the best of our knowledge, there is no complete analytical derivation of the whole time evolution of the two errors.
the ratios tend to finite values N
expects that
We analyze the gradient flow equations in the high-dimensional regime and deduce the whole time evolution of the training and generalization errors. Numerical simulations show that the gradient flow is an excellent approximation of gradient descent in the high-dimensional regime as long as the step
size is small enough (see Fig. Main contributions presented in detail in Sect. 3 comprise:
a. Results 3.1 and give expressions of the time evolution of the errors in terms of one and two-dimensional integrals over spectral densities whose Stielijes transforms are given by a closed set of purely algebraic equations. The expressions lend themselves to numerical computation as illustrated in Fig. [ and more extensively in Sect. and the supplementary material.
b. Model and sample-wise double descents develop after some definite time at the interpolation threshold and are preceded by dip or minimum before the spike develops. This indicates that early stopping is beneficial for some parameter regimes. A similar behavior also occurs for the triple descent. (See Figs. and the 3D version Fig. D..
c. We observe two kinds of epoch-wise "descent" structures. The first is a double plateau monotonously descending structure at widely different time scales in the largely overparameter- ized regime (see Fig. 3.. The second is an epoch-wise double descent similar to the one found in [22). In fact, as in [22] rather than spike, this double descent appears to be an elongated hump over wide time scale (see Fig. aaa the 3D version Fig. []
Let us say few words about the techniques used in this work. We first translate the gradient flow equations for the learned weights of the second layer into a set of integro-differential equations for generating functions, as in (27). involving the resolvent of a random matrix (constructed out of the fixed first layer weights, the data, and the non-lineat activation). The solution of the integro- differential equations and the time evolution of the errors can then be expressed in terms of Cauchy complex integral representation which has the advantage to decouple the time dependence and static contributions involving traces of algebraic combinations of standard random matrices (see (2 for related methods). This is the content of propositions 220. (2..2) With a natural concentration hypothesis in the -igendimensional regime, it remains to carry out averages over the static traces involving random matrices. This is resolved using traces of sub-blocks from the inverse of a larger nontrivial block-matrix, a so-called linear pencil. To the best of our knowledge linear pencils have been introduced in the machine learning community only recently in (29). This theory is developed in the context of random matrix theory [30 BT and [32] using operator valued free- rreb-brobability. A side-contribution in the SM is also an independent (but non non-rigorous) derivation of a basic result of this theory (a fixed point equation) using a replica symmetric calculation from statistical physics.

---

The non non-linearity of the activation function is addressed using the gaussian equivalence principle Finally, our analysis is not entirely mathematically controlled mainly due to the concentration hypothesis in Sect. 2.3 but comparison with simulations (see Fig. 2 and SM) confirms that the analytical results are exact.
33
29
In the conclusion we briefly discuss possible extensions of the present analysis and open problems among which is the comparison with dynamical mean-field theory approach.
22
1467
18
5-
2.5
MSS
1.5
0.5
12
105
10
100
80
0.5
107
10
time
Figure 1: 3D plot of analytical test error evolution. See Figs.
5 and 4 (on the right) for parameter values.
2 Random feature model
2.1 Model description
Generative model and neural network: We consider the problem of learning linear function fa(x) = d' 2,3T x with x, 3 E Rd column vectors. The vector x is interpreted as a random input and B as a random hidden vector; both with distribution (0, Ia). La the d x identity matrix. We assume having access to the hidden function through the noisy outputs y = fa(()) + e with additive gaussian noise ~ NN00 s2), 8 E RR.. We suppose that have n data-points (Ir4, 1.) This data can be represented as the x matrix X E Rnxd where x! is the i-th row of X, and the column vector vector E T with i-th entry y/- Therefore, we have the matrix notation d X + where Ş ~ (0, s² TT)) and 7 the
identity matrix.
We learn the data with a shallow 2-layer neural network. There are N hidden neurons with weight (column) vectors 0, E RR,, i 1, 1,. each connected to the d input neurons. Out of these we form the matrix (of the first layer connecting input and hidden neurons) θ R where 0f is the i-th row of θ Its entries are assumed independent and sampled through standard gaussian distribution (O, 1); they are not learned but fixed once for all. The data-points in X are applied linearly to the parameters θ, and the output Z E R=* N of the first layer is the pointwise application of an activation function R + R. 2 = (d ( We use the notation 2! to express the i-th row of Z. The second layer consists in weight (column) vector a E R.N to be learned, indexed by time 2 with components initially sampled at 0ii. e R4. The prediction vector expressed as Y, N Za..
We assume that the activation function belongs to (e 3 dx) with inner product denoted ( ). It can be expanded on the basis of Hermite polynomials, so a E Span ((Hee )=2o), where Hog (z) =
d' of (so (x) = 1, He, (x) = 2, He, (x) = x2 1, Heg (x) = x3 3x, ...). (-1)ke dare Furthermore we take a centered with (a, He,) = 0, and set μ = (a. H ), = (0,0) 12, For instance, a = has (n,r) = (1, while a = Relu V2= has (4. = ( 2 2)1/2) (0.5, 0.3). Finally, parameters N, n, d tend to infinity with the ratios N + and 2 + c.
recall that are interested in the high dimensional regime where the
3

---

Training and test errors: For a new input zo E RS, we define the predictor (e())) VN
J (=0))" a, where 2(zo) a va @xa). We will further define the standard training and test
errors with a penalization term À > 0 and the quadratic loss:
2
Htrin (a = y Y
|all" (a) = Exo- [(u(2)) ((x)))
(I)
Note that because the >-penalization term, in this context, the training error can be above the test error in some configurations of parameters. Also, we will slightly abuse this notation throughout the paper by using M. H,t to designate Httin (at). (1p)
Minimizing the training error of this Shallow-network equivalent to a standard Tikhonov regularization problem with design matrix Z for which the optimal weights are given by Gx = E N >> 2" Y. The errors generated by the predictors with weights doo have been VN analytically calculated in the high-dimensional regime in [77 and further analyzed [2I]. Here we study the whole time evolution of the gradient flow and thus introduce additional time dimension in our model. Of course as + +oo one recovers the errors generated by the predictors with weights agc. The output vector a, is updated through the ordinary differential equation da. -n Hthai (at) with fixed learning rate parameter 7) > 0. As y can be absorbed in the time parameter, from now on we consider without loss of generality that v) = z. Setting N we find that the gradient flow for a, is first order linear matrix differential equation,
Gradient flow:
ar
da di
Z N + +ŌIN
ZTY
dt +
VN
Recall the initial condition ag a vector with i.idd N r²) components.
2.2 Cauchy integral representations of the training and test errors
An important step of our analysis is the representation of utrai and Hiett in terms of Cauchy contour integrals in the complex plane. To this end we decompose both errors in elementary contributions and derive contour integrals for each of them. Details are found in section 4 and the SM.
We begin with the test error which is more complicated. We have
H = 1 + s² 2pg(t) + + 1²2((t) + r²((t) + (1
where lim +o (1) with high probability, and g(t) 8T
TT a vil v vN* h(t) -| 11 and v vN
(tt) = || 1l To describe Cauchy's integral representation of the elementary functions g. h, I we introduce the resolvent R(2)=
Z =IN) for all E )
Proposition 2.0.1 (Test error) Let R2 be the functional acting holomorphic functions f Sp( - + C as R. [=][(=)) = - fr - 2mg f(z) over a contour I encircling the spectrum Sp( ZTZ in the counterclockwise direction. Similarly, let Ray be the functional acting on two-variable dz dy 2 2 f(x, y)- Let
N
holomorphic functions! f : (C) Sp( Sp(""² 2=222)2
+ C as (x y)} = fr fr
8" e Gx(z) = Va Va R(z) a and K(x) Va Va R(=) Y We have for all 2 0 IN
BT 97
N
s(1) R2 { 1(x++) + 1 - t(2+0)
K(z1]
(4)
Let T=(2)= = a
VN R(=) t and Uz(z)= = YTz R(2)
a and V(=)= VN
YTZ R(2)
N For all 1 2
N
1(t)= [0) R2 { -2((=+)) Lo(z)+ +2 ((x+6)
(1-e
1 (1-e-(bta)
8 + (1-0+z
Uo(2)+
v(e)). (5)
8 8+2

---

Let H,(x,)) -x R(x)
R())
90 R(y) vN
Qr(z.y)
of VN
R(xx .6 R(y) z and W(r,y)
d
Y R(x) -0" RRyy) z N. For all 0
N
((((++)) -
c((0+a) - 1 20((v }
h(t) R2,
1128+2+))
Q0(x, ++
8 8+y
1 e
e ( (()+8) W(x,)) + Row fo fo (0 Ho(z,1) (6)
+ Roy
+
y +
similar but much simpler representation holds for the training error.
Proposition 2.0.2 (Training error) With the same definitions than in proposition 2.0.1 we have
| 1 R-R (2 (2+ () 20(2+5) Lo(2) 2e -2(=-000+) - - e -2((6+))
v(t)) (7)
+
8+
2.3 High- framework
The Cauchy integral representation involves set of one-variable functions S1
(Go, K, Lo, Uo. V) : C Sp( (D(222) C and set of two-variable functions S2 (Ho, W. Qo} C) () 1)2) + C so that g. h. and thus also Hiest and Httain actually functions of (t: (1 S2) Thus write for instance: H (ay) 7 (t; S1, S2). We simplify the problem by considering the high-dimensional regime where N, n. - with ratios a - v), à - & tending to fixed values of order one. In this regime we expect that the functions in S and Sy concentrate and can therefore be replaced by their averages over randomness. These averages can be carried out using recent progress in random matrix theory [30]. (3. and we are able to compute pointwise asymptotic values of the functions in S1, S2, and eventually substitute them in the Cauchy integral representations for the training and test error. In general, rigorously showing concentration of the various functions involved is not easy and we will make the following assumptions:
Assumptions 2.1 In the high dimensional limit with d, N, n - co and + 1/. Φ:
1. The random functions in S₁, S2 are assumed to concentrate. We let S1 (Go, Lo, Un. V) and S ( (Ho, : W, Qo) be the pointwise limit of the functions.
2. There exists bounded subset C B.+ such that the functions in Si and S2 are holomorphic on I \ C and (C \ C)² respectively
3. The gaussian equivalence principle (see sect. 4.2 can be applied to the limiting quantities.
It is common that the closure of the spectrum of suitably normalized random matrices concentrates on deterministic set. Thus the bounded set C can be understood as the limit of the finite interval [0, lim, max Sp( 2 2²2 }]. In the sequel we will distinguish the theoretical high-dimensional regime from the finite dimensional regime using the upper-bar notation.
Definition 2.1 cal test error Hiea H (t; S1, S2) and the theoretical training error Hmma H St, S2)
framework) Under the assumptions 2.1
we define the theoreti-
We conjecture that lim Hm Htrain and lim His Hisst all times / R. We verify that this conjecture stands experimentally for sufficiently large d on different configurations (see additional figures the SM). This also lends experimental support on the assumption| 2.1 Furthermore we conjecture that the d + too and & + oc limits commute, namely lim, lim, 7. lim, Hi and lim lim, Heest lim, test
3 Results and insights
3.1 Main results
In this section we provide the main results of this work: analytical formulas tracking the test and training errors during gradient flow of the random feature model for times the high-dimensional theoretical framework.
5

---

Result 3.1 Under the assumption 2.1 the theoretical test and training envors of definition 2.7 are given for all times 2 0 by the formulas
Hrth =1+ -uug(t) + +p
p=h(t)++ =2((t).
+
(8)
Hitron 1 32 +- / (6+ (6+ ())--uu-ttt PLo (w) 1 - e-20()+w)
Pp (w)) dw,
(9)
8 + w
with
2 vo
8 == cd, and the functions li, given by
g(t) / 1 1- (
PR pk(w)
(10)
1
T(t)= = [ 21(w40)
PLo (w)(w) + 1 e1-e-tuutty 2
pv po(w)) du,
(11)
h(1)= = /|ee
e (tuttt-20 PAo ( (u, 1 ((ve-())
((v+5)
Pw (u, v) dudu,
(12)
u u+
+ 5
where the measures PR: Pio: PV-PAo Pwr (are possibly signed) are characterized by their Stieltjes transforms given by K, Lo, V, Ho,
(x)) = ti, -o(x)= = = V(a)= s2 (1+ xggi) + (c 1(),,
(13)
Ho(z, v) = raq W(z.v) = 5² cqq +
where for each z. E C+ (the upper half complex plane) g h2 ti. Ri N2 and qu 92 qa. Is (which depend symmetrically on (z, y), e.g., q1 = qी = q are solutions of a purely algebraic system of equations (see SM for the criterion to select the relevant solution)
= pung h
t
pin h t
(c 1 rgi (c- (c-1200 (2 ch
0 (c 1 yo!) ) (c
1-12
ch
0 = - oi (n²hi + +(c -cc-l- x )² x
= 9 (12 (c-c ygt v2
1 02 +/2h + #ight + pg 44
cg. cg"qqu² u2² 9 -9i + qi (c
g x 1)
(6 vi -) (-1u( + pblg]
+ gi (4 ogaa (1
-m( Q2
- o (1-1tf1-)p +
+ 12 (c giy
1) v² 02 644 + q1²² (Φ vo - vp)
( 2 ogggg9 - - (1 (1-1 p (c H.x 1) Qs
We can also deduce the limiting training error and test errors in the infinite time limit:
Result 3.2 In the limit - 0o we find:
lim -1t0-144 -1 - (2W())))- + 22 (-0), lim HiTaii - 1 - 8-000
dv
2-000
Interestingly, in the limit + co, the expressions become simpler and completely algebraic in the sense that we do not need to compute integrals (or double-integrals) over the supports of the eigenvalue distributions. It is not obvious to see the analytical expressions that the result is the same as the algebraic expressions obtained [17] but Fig. P shows an excellent match with simulation experiments. We note here that checking that two sets of complicated algebraic equations are equivalent is in general non-trivial problem of computational algebraic geometry [35].
3.2 Insights and illustrations of results
The set of analytical formulas allows to compute numerically the measures PK PLo: PV, PHo PW and in turn the full time evolution of the test and training errors. The result matches the simulation of a large random feature model where d is taken large as can be seen limit (experimental check of result and additional figures in the SM (experimental check of result Below we illustrate numerical computations obtained with analytical formulas of result 3.]
Figs. 2 for the infinite time
3.1.

---

compute the expectations of for various sets of parameters (t, H. 19, Ø. r. S. A). For instance, we can freely choose two of these parameters and plot the generalization enror in 3D as in Fig. [ or as a heat-map the following. We describe three important phenomena which are observed with our analysis.
Double descent and early-stopping benefits: while 17 mostly analyze the minimum least-squares estimator of the random feature model which displays the doublc-descent at 3 = o. we are predicting the whole time evolution of the gradient flow as in Fig. 3
We clearly observe the double-descent curve at t = 1010 for 1/ Φ; but we now notice that if we stop the training earlier, say at times 1 < t < 10, the generalization error performs better than the minimum least squares estimator. Actually, in the time interval t E (1, 10) for &b ~ á the test eπror even has a dip or minimum just before the spike develops. We also notice two-steps descent structure with the test error which is non- non-existent in the training error and materializes long after the training error has stabilized in the overparameterized regime 1o > Φ. This is also reminiscent but not entirely similar to the abrupt grokking phenomenon described in [36].
Triple descent: We can observe a triple descent phenomenon materialized by two spikes as seen in Fig. 2 t-= = oc (we also check that the theoretical result matches very well the empirical prediction of the minimum least squares estimator both for training and test errors). This triple descent phenomenon is already contained in the formulas of [77 (although not discussed in this reference) and has been analyzed in detail in 22 The test error contains so-called linear spike for
(n d) and a non-linear spike for to Φ (N = n.). The two spikes are often not seen together as this requires certain conditions to be met, and they tend materialize together for specific values p., V of the activation function where >> v. Here we further observe the evolution through time of the triple descent and the two spikes and how they develop in Fig. There, we notice that the linear-spike seems to appear earlier than the non-linear one.
Epoch-wise descent structures: Important phenomena that uncover here are two time-wise "descent structures". (i) As can be seen in Fig. 3 the test error develops a double plateau structure widely different time scales in the over-parameterized regime (1 >> ()) while there seems to be only one time scale for the training error. This kind of double plateau descent is different from the "usual" double-descent. (ii) Moreover, on Fig. 5 for well chosen parameters (in particular for noises with s and r "larger" and &o 26), we can also observe an elongated bump (rather than a thin spike) for small X's. Notice the logarithmic time-scale which clearly shows that here we need to wait exponentially longer to attain the "second descent" after the bump. This is very reminiscent of the epoch- wise double descent described in 22 for deep networks (which happens on similar time scales).
B. H
20
ei.. A2m
exp.
1.5
MB2
0.08
0.06
1.0
0.04
0.5
0.02
0.00
0.0
0.55
1.00
1.25
2.00
0.75
1.00
1.50
1.75
Figure 2: Large time limit Analytical training error and test error profile with parameters (μ, v4 r, X) (10, 1, 0.5, 0.01) compared with experimental least squares MSE with 40 data-points with df = 5000 (average of 10 instances with confidence bar at 20r
4 Sketch of proofs and analytical derivations
The analysis is threefold. Firstly, we decompose the training and test errors in elementary terms and establish Cauchy's integral representation for each of them, as provided in proposition 2.0. A crucial advantage of this form is that it dissociates scalar time-wise component and static matrix terms. Secondly, we switch to the high-dimensional framework where the matrix terms are substituted by their limit using the gaussian equivalence principle. Thirdly,
7

---

10
10"
2.3
10
1.5
105
109
06
10P
10
TO
time
time
Figure 3: Model-wise double descent. Analytical training error and test error evolution with parameters (e, s, (0.5, 3, 2. 0.4, 0.001). Note that we vary the number of model parameters (1²).
3.8
0.5
10
10
10
10
10
1o
Time
Sim
Figure 4: Sample-wise descents.
Analytical training and test enoor evolution with parameters 10, (0.9,0.1,22 1,8.8 0.0001). Note that we vary the number of samples (Ø).
Train
Test
MBE
10"
10"
1.
10
10P
10
10
10a
10
Figure 5: Epoch-wise descent structures. Analytical test evolution with respect different values of (p, v. (. = (0.5, 2,3.2.0000 Here ratio number of parameters and samples fixed.
matrix terms thanks to random matrix technique based on linear pencils. In this section we only sketch the main ideas for each step and provide details in the supplementary material.
4.1 Cauchy's 's integral representation
We sketch the derivation for the test error and leave details to appendices. The derivation for the training emror is entirely found in the SM. Expanding the square in Equ.
( and carrying averages r" as h(t) = 0 ar 1|? and I(t) = - I| (see SM
we find Equ. (5) for H. with g(t) for this derivation).
8T
va NN
We show how to derive the Cauchy integral representation for g(t). For h(t), I(t) the steps similar and found in SM. Let us consider the function 21) + G.(z) as in 2.0. Then we have the relation
(t) -1
2 f.. (z) where I is loop in C enclosing the spectrum of zTz seen by decomposing the symmetric z"2 in orthonormal basis uI,..., UN with the eigenvalues N
N This easily be

---

8 8 AN: then we have Gr(z) = Ei A,=
va va iiia
oz vN
and because X are all encircled
by r, we find - fr दम: G) = -i= va Vi iiin
S e²
g().. Now, the ODE derived for az in (2)
vN
can be written slightly differently using the fact that Namely,
z R(z) / for any outside Sp( 2 N
da. dt VN R(=) -aa - (z 8)a, Then, we can derive an integro-differential equation
z²
for Gz(z) involving gt) and K()):
O,G. ((2) -x (2)
(14)
Ōt
In the following, we let & be the Laplace transform operator (Lf)() dte- Rep large
enough. Note that the contour integral is performed over compact set I' for Re kep large enough, by Fubini's theorem, the operations & and Rg commute. Applying L to (14) and rearranging terms we find for Re(p + 5) o O:
Go(z) [zp(2) p 2 p(p 2 8)
K(2)
Lg(p) p 2
(15)
Now, always choose I' such that - (p++)) is outside of the contour if we assume Re(p+d) > 0 (since min; X; 2 0). Thus, applying R, to (15) nullifies the last term because the pole is outside I, and using commutativity R. LR. Gp-
R,LGp = LRg { (e10 Go(z)
1- e-2-0))
k(x) = Lg(p).
(16)
2 2
Finally, using the inverse Laplace transform leads
4.2 Gaussian equivalence principle
The matrix terms must be estimated in the limit d + 2o with {3, 10,00, 0n. E, 0, X) all independently distributed. As per assumptions 2.1 the matrix terms in S1, S2 are assumed to concentrate. So for in-
stance we assume that the following limit exists R(=) lim K(2) lim E (
Using cyclicity of the trace we easily perform averages over 3, { find
T
33" 7T X N
1 lim F
O
ZT X
(2)) lim Exe. TT
R(=)
(17)
After these reductions, the expressions of all functions in S1 essentially involve products of random matrices θ, X and pointwise applications of the non-linear activation a. This can be further reduced to simpler algebraic expressions using the gaussian equivalence principle. This principle states that: there exists a standard gaussian random matrix Q E R independent of {X, θ} such that in the infinite dinensional limit
make the substitution Z (d- -/"
1d2 x vla the expressions of all functions in S2, This approach is quite general and is well described in (29 [7) (and formerly in [33 and (34). Thus it remains to compute expectations of traces containing only products, and inverses of products and sums, of gaussian matrices.
4.3 Expectations over random matrices using linear pencils
We explain how compute the limit of once the gaussian equivalence principle has been applied. powerful approach is to design so-called linear pencil. In the present context this is a suitable block-matrix containing gaussian random matrices and multiples of the identity matrix, for which full block-inversion gives back the products of terms in the traces that being sought. This approach has been described in [30 31 38). We have found suitable linear pencil which contains fortuitously all the terms required in St, Sz. It is described by the 13 x 13 block-matrix M, and pursuing with

---

our example, we get for instance with the block (7, 12) that limg (v)) = lima TT
(2.13))
ml
e
0
0
0
0
Va
xx
0
0
0
0
0
0
0
0
0
0
V
0
0
0
D
0
0
0
0
0
0
I
M
0
0
vā
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1000
1000
0
0
1000
0
0
00000
0000
0
0
VN
-1
0
0
200
1
0
1000
1 6T
va
0
11
0
-y
31 38 it allows write Next, the great advantage of the linear pencil is that (as descrihed in 30
fixed point equation F(G) = G for a "small" 13 x 13 matrix G with scalar matrix elements. We also provide in the SM an independent derivation the fixed point equations using the replica method (a technique from statistical physics (39)). The components of G are linked to the limiting traces of the blocks of -1 in [G]2.7 K (z). The action of F can be completely described as an algebraic function leading to (a priori) 13 x 13 = 169 equations over the matrix elements of G. The number of equations can immediately reduced 39 because many elements vanish, and with the help of computer algebra system the number of equations can be further brought down to 10. We refer to the SM for all the details about the method.
Conclusion
We believe that analysis could be extended to study the learning of non-linear functions, the effect of multilayered structures, and potentially different layers such as convolutions, as long as they are not learned. A challenging task is to extend the present methods to learned multilayers. A further question the application of our analysis in teacher-student scenarios with realistic datasets (See 40 37))
Finally we wish to point out that a comparison of the approach of the present paper (and the similar but simpler one of (27)) with the dynamical mean-field theory (DMFT) approach of statistical physics remains to be investigated. DMFT has a long history originating (turbulent fluids, spin glasses) where one eventually derives set of complicated integro-differential equations for suitable correlation and response functions capturing the whole dynamics of the system (we refer to the recent book [41] and references therein). This is powerful formalism but the integral equations must usually be solved entirely numerically which itself is not trivial task. For problems close to the present context (neural networks, generalized linear models, phase retrieval) DMFT has been developed in the recent works 42 this formalism with the present approach is interesting open problem. It would be desirable to connect the DMFT equations to our closed form solutions for the training and generalization errors expressed in terms of set of algebraic equations of suitable Stieltjes transforms.
studies of complex systems
networrssgenerraiized
45 46). We think that comprehensively comparing
Acknowledgments and Disclosure of Funding
The work of A. B has been supported by Swiss National Science Foundation grant no 200020 182517.
10

---

References
[1] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1877-1901. Curran Associates, Inc., 2020.
[2] 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, page 101108861v1, 2020.
[3] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning. Springer Series in Statistics. Springer New York Inc., New York, NY, USA, 2001.
[4] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. ICLR 2017, arXiv abs/161 1.03530, 2016.
[5] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias-varianee trade-off. Proceedings of the National Academy of Sciences, 11:2201903070, 07 2019.
[6] Mikhail Belkin, Siyuan Ma, and Soumik Mandal, To understand deep learning we need to understand kernel learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 541-549. PMLR, 10-15 Jul 2018.
[7] Mikhail Belkin, Alexander Rakhlin, and Alexandre B. Tsybakov. Does data interpolation contradict statistical optimality? In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 1611-1619, PMLR, 16-18 Apr 2019.
[8] Mikhail Belkin, Daniel Hsu, and Xu. Two models of double descent for weak features. SIAM Journal Mathematics of Data Science, 2(4): Jan 2020.
[9] S Spigler, M Geiger, S d' Ascoli, L Sagun, G Biroli, and M Wyart. A jamming transition from under- to over-par parametrization affects generalization in deep learning. Journal of Physics A: Mathematical and Theoretical, 42447):474001, Oct 2019.
[10] Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d' Ascoli, Giulio Biroli, Clément Hongler, and Matthieu Wyart. Scaling description of generalization with number parameters in deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2020(2)0023401, feb 2020.
[11] Madhu S. Advani, Andrew M. Saxe, and Haim Sompolinsky. High-dimensional dynamics of generalization error in neural networks. Neural Networks, 132:428-446, 2020.
[12] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in High- Dimensional Ridgeless Least Squares Interpolation. arXiv e-prints, page arXiv:1903.c 1903.086,,, March 2019.
[13] Michal Derezinski, Feynman T Liang, and Michael W Mahoney. Exact expressions for double descent and implicit regularization via surrogate random design. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 5152-5164. Curran Associates, Inc., 2020.
[14] Vidya Muthukumar, Kailas Vodrahalli, Vignesh Subramanian, and Anant Sahai. Harmless interpolation of noisy data in regression. IEEE Journal on Selected Areas Information Theory, 1(1):67-83, 2020.
11

---

[15] Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):30033-30070 2020.
[16] Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for nigh-dimensional binary linear classification. Information and Inference: A Journal of the IMA, 04 2021. iaab002.
[17] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptoties and double descent curve. arXiv e-prints, page arXiv:1908.055: 1908.0535,, August 2019.
[18] Zhenyu Liao, Romain Couillet, and Michael W Mahoney. A random matrix analysis of random Fourier features: beyond the Gaussian kernel, a precise phase transition, and the corresponding double descent. In 34th Conference on Neural Information P Processing Systems (NeurIPS 2020), Vancouver, Canada, December 2020.
[19] Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mezard, and Lenka Zdeborova. Generalisation eπror in learning with random features and the hidden manifold model. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 3452-3462. PMLR, 13-18 Jul 2020.
[20] Stéphane D' Ascoli, Maria Refinetti, Giulio Biroli, and Florent Krzakala. Double trouble in double descent: Bias and variance(s) in the lazy regime. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 2280-2290. PMLR, 13-18 Jul 2020.
[21] Stéphane d' Ascoli, Levent Sagun, and Giulio Biroli. Triple descent and the two kinds of overfitting: where and why do they appear? In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 3058-3069 Curran Associates, Inc., 2020.
[22] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Nya Sutskever. Deep double descent: Where bigger models and more data hurt. In International Conference on Learning Representations, 2020.
[23] Manfred Opper. Statistical Mechanics of Generalization, pages 922 -25. MIT Press, Cambridge, MA, USA, 1998.
[24] A. Engel and C. Van den Broeck. Statistical Mechanics of Learning. Cambridge University Press, 2001.
[25] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. Platt,
D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2008
[26] Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clement Hongler, and Franck Gabriel. Implicit regularization of random feature models. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 4631-4640. PMLR, 13-18 Jul 2020.
[27] Antoine Bodin and Nicolas Macris. Rank-one matrix estimation: analytic time evolution of gradient descent dynamics. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 635-678. PMLR, 15-19 Aug 2021.
(28) Zhenyu Liao and Romain Couillet. The dynamics of learning: A random matrix approach. In International Conference on Machine Learning, pages 3072-3081. PMLR, 2018
[29] Ben Adlam and Jeffrey Pennington. The neural tangent kernel in high dimensions: Triple descent and a multi-scale theory of generalization. In Hal Daume III and Aarti Singh, edi- tors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 74-84. PMLR, 13-18 Jul 2020.
12

---

[30] Reza Rashidi Far, Tamer Oraby, Wlodzimierz Bryc, and Roland Speicher. Spectra of large block matrices. arXiv e-prints, page cs/0610045, October 2006.
[31] W. Helton, R. Far, and R. Speicher. Operator-valued semicircular elements: Solving quadratic matrix equation with positivity constraints. International Mathematics Research Notices, 2007()) mm0086-mm086 2007.
[32] J William Helton, Tobias Mai, and Roland Speicher. Applications of realizations (aka lineariza- tions) to free probability. Journal of Functional Analysis, 274(1):1-79, 2018.
[33] Jeffrey Pennington and Pratik Worah. Nonlinear random matrix theory for deep learning. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 2637-2646, 2017.
[34] S. Péché. note on the Pennington- Worah distribution. Electronic Communications in Probability, 24(none): 7, 2019.
[35] David A. Cox, John Little, and Donal O' Shea. Ideals, Varieties, and and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3/e (Undergraduate Texts in Mathematics). Springer- Verlag, Berlin, Heidelberg, 2007.
[36] Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra. Grokking: Generalization beyond overfitting on small algorithmic datasets. In ICLR MATH-AI Workshop, 2021.
[37] Ben Adlam, Jake Levinson, and Jeffrey Pennington. A Random Matrix Perspective on Mixtures of Nonlinearities for Deep Learning. arXiv e-prints, page arXiv: 191.:191..0082., December 2019.
[38] James A Mingo and Roland Speicher. Free probability and random matrices, volume 35. Springer, 2017.
[39] Samuel F Edwards and Raymund C. Jones. The eigenvalue spectrum of a large symmetric random matrix. Journal Physics A: Mathematical and General, 9(10):1595, 1976.
[40] Bruno Loureiro, Cédric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mézard, and Lenka Zdeborová. Capturing the learning curves of generic features maps for realistic data sets with teacher-student model. arXiv preprint drXiv:2102.08127, 2021.
[41] G. Parisi, P. Urbani, and Zamponi. Theory of Simple Glasses: Exact Solutions in Infinite Dimensions. Cambridge University Press, 2020.
[42] H. Sompolinsky, A. Crisanti, and H. Sommers. Chaos in random neural networks. Phys. Rev. Lett., 61:259 262, Jul 1988.
[43] A. Crisanti and H. Sompolinsky. Path integral approach to random neural networks. Phys. Rev. E, 98:062120, Dec 2018.
[44] Elisabeth Agoritsas, Giulio Biroli, Pierfrancesco Urbani, and Francesco Zamponi. Out-of- cquilibrium dynamical mean-field equations for the perceptron model. Journal of Physics A: Mathematical and Theoretical, 51(8):085002, Jan 2018.
[45] Francesca Mignacco, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborová. Dynam- ical mean-field theory for stochastic gradient descent in gaussian mixture classification. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 9540-9550. Curran Associates, Inc., 2020.
[46] Francesca Mignacco, Pierfrancesco Urbani, and Lenka Zdeborová. Stochasticity helps to navigate rough landscapes: comparing gradient-descent- based algorithms in the phase retrieval problem. Machine Learning: Science and Technology, 2021.
13


Reviews:
[{"review_id": "wiR3qNSZ40R", "reviewer": "Reviewer_wJHk", "summary": "This paper presents an analytical derivation of the train and test loss curves of the random feature model. The main novelty lies in the fact that the authors not only capture the behavior at final times, but also the dynamics. This leads to various interesting observations, since such models have been shown to exhibit epoch-wise double descent.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I recommend the acceptance of this paper to NeurIPS.\n\nStrengths: \n- First analysis of epoch-wise double descent I know of for RF models\n- Paper is well organised, results are presented clearly\n- The authors clearly state the non-rigorous hypothesis used\n- The phase space plots are informative and reveal new phenomena such as the exponentially elongated bump in the epoch-wise phase space as we regularise too little (this is particularly interesting in my opinion)\n- The authors do a good job to provide a sketch of proof, and even include an alternative proof using a different technique from statistical physics\n- The derivations in the SM are thorough and detailed\n\nWeaknesses: \n- Could be viewed as slightly incremental to the non-initiated community, but the complexity of the analytical derivations justify the novelty of the paper\n- Fig. 2, which overlays the theoretical and experimental results, is plotted at final time as a function of phi/psi, but the late-time error was already derived in previous works; it would be better to have the numerical confirmation as a function of time, since time-dependency which is the key novelty of this paper.\n- I think more space should be devoted to the phenomenology observed, as the analytical results are nearly impossible to parse for the reader.\n\nNits:\n- Fig 1: a bit confusing that the t axis are inverted in the two panels\n- Line 114: Hermite polynomials should be indexed by n\n- “we notice that the linear-spike seems to appear earlier than the non-linear one” : this was observed already in reference 21.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "X_No6IB72j9", "reviewer": "Reviewer_Crju", "summary": "In this paper, authors proposed an analytical model to understand the multiple-descent curves in generalization errors of over-parameterized models (random feature models optimized over gradient flow). More specifically, they provided exact solutions to interpret the model-wise, epoch-wise and sample-wise double descent phenomenon. \n\nIn Section 2., authors define the learning problem of over-parameterized models with random features as a regression problem of Ridge-alike, then define the optimization procedure as an ODE. In Section 2.2., authors represent  training and testing errors with  Cauchy integral representations with assumptions prespecified. They report the result as the solution of ODE under assumptions while providing some simulation results to backup their theoretical results. The sketched proofs are attached. ", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The work provides asymptotic results on the generalization performance I might be wrong, the main results of this work looks the combination of existing results on gradient flows (to run OLS or Ridge) with some results on random matrix theories (to model the sample covariance established by random features) via Cauchy integral. Authors are encouraged to discuss their results with \"Just Interpolate: Kernel ''Ridgeless'' Regression Can Generalize\" at Annals of Stats 2020. Of-course, in Ridgeless paper, they did not cover the optimization issue. With gradient flow for OLS and Cauchy integral, it seems possible to obtain the exact solution of or tight approximation to the gradient flow for OLS at continuous-time t. It looks authors obtained their results through combination. Some simulations could be improved using real-world datasets.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It helps us understand why over-parameterized models work and interpret their generalization performance. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "5hrs"}, "extra_text": {}}, {"review_id": "BdRlRNn0zAU", "reviewer": "Reviewer_b8CN", "summary": "This article provides, modulo some important technical assumptions, computationally tractable formulas for the test and train error of a random features model trained by gradient flow on \\ell_2-regularized MSE during the entire course of training. The features are those computed by the first layer of a randomly initialized neural network and the regime of interest for this article is a triple scaling limit in which the input dimension, dataset size, and hidden layer width tend to infinity but their ratios remain order 1. Unlike prior work this article provides formulas for the evolution in time of both the training and test error, instead only of only their behaviors are t = \\infty. While the results are not completely rigorous (they assume concentration for spectral statistics of certain random matrices), I found them intriguing and am fairly convinced by plots in which the predictions fit empirics quite well. The main weakness for me is a lack of further formulation of takeaways from the theoretical results (see weakness #2). Overall, I thought this was a solid paper. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. Understanding the regime where input dimension, dataset size and the number of model parameters are all large is clearly relevant to modern ML. \n\n2. The techniques in this article give what is, at least to me, a nice approach to understanding the behavior in time for train and test error in random feature models. While these models are linear in the trainable parameters, they are not linear in the inputs and understanding the resulting training curves seems hard and interesting. \n\n3. If I understood correctly, the plots in Figure 3,4,5 were generated by analytically computing the test and train error from the formulas in Result 3.1. Assuming these match empirics, this is very useful indeed. I particularly liked “seeing” the epoch-wise, model-wise, and sample-wise descents appear and the phase transitions between double descent, triple descent, and other behaviors. \n\n4. I thought the main body of the article was well-written and was able to follow the logic. \n\nWeaknesses:\n1. The formulas in Result 3.1, while seemingly analytically computable, are sort of horrendous at first glance. It would be nice if some intuition could be provided for what is going on. \n\n2. An amplification of #1: I feel that the techniques in this article are sophisticated but the interpretation of the results is a bit lackluster. Concretely, since the formulas themselves are hard to grok, it would have been very useful to me as a reader if the discussion in section 3.2 were amplified. (I understand that space is an issue, but I am not sure anyone really needs to see the exact structure of the linear pencil on page 9?) For example:\n\n2a. When exactly do we expect that early stopping is useful? Are any of these situations surprising? \n2b. I am intrigued by the double plateau. Can you explain it intuitively? When should one expect it to occur?\n2c. Can you explain more about the interaction of the non-linearity via its first few Hermite coefficients and the simultaneous appearance of the linear and non-linear spike?\n\n\nMinor:\n1. “passed an interpolation” should probably be “past an interpolation”\n\n2. For equation (1) in the definition of H^{train} either H^{train} should be evaluated at a instead of a_t or the right hand side should contain ||a_t||^2 instead of ||a||^2. \n\n3. Line 179 page 5 “time” should probably be “times”\n\n4. It might be useful for the reader if the extra empirical validation of the results in Figures 13-15 were highlighted in the main body.\n\n5. I am not an expert in the developments of this kind of high-dimensional RMT for random feature generalization, but I have the feeling that the article of Adlam-Pennington “The neural tangent kernel … “ is kind of given short shrift. Maybe I’m missing the point, but it seems that the use of linear pencils is key for doing the computations related to spectral curves and the algebraic relations in Result 3.1. And if I am not mistaken these techniques were used for first time in this context in that article. More broadly, as a non-expert, it would have been very useful to have a bit more context comparing the present work to the various different strands of work on double and triple descent in high dimensional models.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations were discussed. Societal impact was not addressed, but it is not clear to me that this kind of article has any serious potential societal impacts. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "-hkiJtZoUZT", "reviewer": "Reviewer_U78k", "summary": "The authors analytically study model, sample, and epochwise descents of the random feature model. Model descent meaning how the test error changes as the model complexity is varied; sample descent meaning how the test error changes as the number of samples are varied; and epochwise descent meaning how the test error changes as the model trains. They derive analytic expressions for the test and train errors and study what happens when the number of neurons $N$, the number of samples $n$, and the sample dimensionality $d$ all tend to infinity. Since this can be done in varying ways, they study when $\\frac{N}{d} \\rightarrow \\psi$ and $\\frac{n}{d} \\rightarrow \\phi$ for fixed values of $\\psi$ and $\\phi$. They observe double descent which is beneficial (lower test error when $\\psi \\gg \\phi$) if training is performed for a long time. On the other hand, if training is cut short (early stopping) the test error is low and even has a dip where later there develops a peak. The authors also observe triple descent if the training time tends to $\\infty$.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n\nThe idea of studying the analytic expressions for test and train error as training evolves is not particularly novel. However, the authors use some very sophisticated mathematical techniques which bring novelty to the work in a way that is not typical. Good job.\n\nQuality:\n\nThis paper is extremely well written and flushed out. The authors did a great job.\n\nClarity:\n\nThe paper is mostly clear. It is hard to read because of the notation; however, that is to be expected for such a theoretical paper.\n\nSignificance:\n\nThis work is very interesting and important for the continued understanding of more complex models such as deeper neural networks.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations:\nAs the authors mention on line 88, the work is not completely rigorous because of their concentration hypothesis. However, this is not an issue for me as they provide supporting empirical evidence to support their work.\n\nPotential negative societal impacts:\nNone", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an asymptotically exact formula for the time-dependence of the training and test error of random feature regression in high dimensions. The reviewers all maintain a favorable view of the results, but there was some concern about the credit afforded to prior work.

Indeed, operator-valued free probability and linear pencils (and the linearizations required to utilize them in the context of nonlinear random feature models) were introduced to the machine learning community in prior work with the express purpose of facilitating the kind of analysis undertaken here. Furthermore, it appears that the main results and methods of this paper, namely those derived via the Cauchy integral formula, have been obtained and advertised elsewhere (though apparently only in talks and never published). As such, it seems there is limited technical novelty in the current paper, and it is imperative that the discussion is modified to more properly reflect this prior work and to emphasize that the contributions of this paper are not the techniques themselves, but rather the results.

On the other hand, there is of course significant value in actually carrying through the calculations in detail, presenting concrete results, and analyzing their implications. As such, this paper will be of value to the community, irrespective of related prior work. Therefore I believe this paper is a good addition to NeurIPS and recommend acceptance.
Decision: Accept (Poster)