Gradient flow in the gaussian covariate model: exact solution of learning curves and multiple descent structures
Authors: Antoine Bodin
Nicolas Macris
Venue: Submitted to ICLR 2023 (2023)
Keywords: Gaussian Covariate Model
Gradient Flow
Gradient Descent
Double Descent
Epoch-wise Double Descent
Random Matrix
Linear Pencil
Cauchy Integrals
High-dimensional Limits
Stieltjes Transform
Random Feature Model

Abstract: A recent line of work has shown remarkable behaviors of the generalization error curves in simple learning models. Even the least-squares regression has shown atypical features such as the model-wise double descent, and further works have observed triple or multiple descents. Another important characteristic are the epoch-wise descent structures which emerge during training. The observations of model-wise and epoch-wise descents have been analytically derived in limited theoretical settings (such as the random feature model) and are otherwise experimental. In this work, we provide a full and unified analysis of the whole time-evolution of the generalization curve, in the asymptotic large-dimensional regime and under gradient-flow, within a wider theoretical setting stemming from a gaussian covariate model. In particular, we cover most cases already disparately observed in the literature, and also provide examples of the existence of multiple descent structures as a function of a model parameter or time. Furthermore, we show that our theoretical predictions adequately match the learning curves obtained by gradient descent over realistic datasets.
Technically we compute averages of rational expressions involving random matrices using recent developments in random matrix theory based on "linear pencils". Another contribution, which is also of independent interest in random matrix theory, is a new derivation of related fixed point equations (and an extension there-off) using Dyson brownian motions.

Under review as a conference paper at ICLR 2023
GRADIENT FLOW IN THE GAUSSIAN COVARIATE MODEL: EXACT SOLUTION OF LEARNING CURVES AND MULTIPLE DESCENT STRUCTURES
Anonymous authors Paper under double-blind review
ABSTRACT
A recent line of work has shown remarkable behaviors of the generalization error curves in simple learning models. Even the least-squares regression has shown atypical features such the model-wise double descent, and further works have observed triple or multiple descents. Another important characteristic are the epoch-wise descent structures which emerge during training. The observations of model-wise and epoch-wiss wise descents have been analytically derived in lim- ited theoretical settings (such as the random feature model) and are otherwise experimental. In this work, we provide full and unified analysis of the whole time-evolution of the generalization curve, in the asymptotic dimensiameiiinal regime and under gradient-flow, within wider theoretical setting stemming from a gaussian covariate model. In particular, we cover most cases already disparately observed in the literature, and also provide examples of the existence of multiple descent structures as a function of a model parameter or time. Furthermore, we show that our theoretical predictions adequately match the learning curves obtained by gradient descent over realistic datasets. Technically we compute averages of rational expressions involving random matrices using recent developments in dom matrix theory based on "linear pencils". Another contribution, which is also of independent interest in random matrix theory, a new derivation of related fixed point equations (and an extension there-off) using Dyson brownian motions.
INTRODUCTION
1.1 PRELIMINARIES
With growing computational resources, it has become customary for machine learning models to use huge number parameters (billions of parameters in Brown et al. (2020), and the need for scaling laws has become of utmost importance Hoffmann et al. (2022) Therefore it is of great relevance to study the asymptotic (or "thermodynamic" limit of simple models in which the number of parameters and data samples sent infinity. A landmark progress made by considering these theoretical limits, is the analytical (oftentimes rigorous) calculation of precise double-desced curves for the generalization error starting with Belkin al. (2020); HHstie al. (2019); Mei & Montanari (011)), Advani Advani et al. (2020), d' Ascoli et al. (2020), Gerace et al. (2020), Deng et al. (2021), Kini & Thrampoulddis (2020) confirming in precise (albeit limited) theoretical setting the experimental phenomenon initially observed in Belkin et al. (2019), Geiger et al. (2019); ; Spigler et al. (2019).
Nakkiran et al. (2020a). Further derivations of triple or even multiple descents for the generalizatio
error have also been performed d' Ascoli et al. (2020); Nakkiran et al. (2020b); Chen et al. (2021):
Richards et al. (2021): )): Wu & Xu Xu220)2). Other aspects multiples descents have been explored in
Lin & Dobriban 22211x & Pennington (2000) also for the Neural tangent kernel in Adlam & Pennington| (2020a). The tools in use come from modern random matrix theory Pennington & Worah (2017): Rashidi Far al. (2006); Mingo & Speicher (2017), and statistical physics methods such as the replica method Engel & Van den Broeck (2001).
In this paper we concerned with a line of research dedicated to the precise time-evolution of the generalization error under gradient flow corroborating, among other things, the presence of epoch-wise descents structures Crisanti & Sompolinsky (2018: Bodin & Macris (202T) observed in

---

Under review as a conference paper at ICLR 2023
Nakkiran al. (2020a). We consider the gradient flow dynamics for the training and generalisation errors in the setting of a Gaussian Covariate model, and develop analytical methods to track the whole time evolution. In particular, for infinite times get back the predictions of the least square estimator which have been thoroughly described in a similar model by Loureiro et al. (2021).
In the next paragraphs we set-up the model together with list of special realizations, and describe our main contributions.
1.2 MODEL DESCRIPTION
Generative Data Model: In this paper, we use the so-called Gaussian Covariate model in teacher- student setting. An observation in our data model is defined through the realization of gaussian vector 2 ~ (0, L.). The teacher and the student obtain their observations (or two different views of the world) with the vectors E RP and & E IR respectively, which are given by the application of two linear operations on z. In other words there exists two matrices B E RRdxps and A E Rdxpa such that x B² and å = A 2. Note that the generated data can also be seen as the output of generative 1-layer linear network. In the following, the structure of A and B is pretty general long as it remains independent the realization 2: the matrices may be random matrices or block-matrices of different natures and structures to capture more sophisticated models. While the models we treat are defined through appropriate A and B, we will often only need the structure of U AAT and =BB.
direct connection can be made with the Gaussian Covariate model described in Loureiro et al. (021 which suggests considering directly observations ã. (x*" " (0, Σ) for given covarincee structure Σ. The spectral theorem provides the existence of orthonormal matrix O and diagonal D such that > O² DO and D contains d non-zero eigenvalues in a squared block D1 and PA + Pg - d zero cigenvalues. We can write D = J D2J with J = (Ial0pa
Therefore
& JJOE which has variance à Ldd then upon noticing JJ Ia and defining (A] = vdo² yf DJ we find (AIB)*² ~ N/ E).
if we let va
The Gaussian Covariate model unifies many different models shown in Table These special cases are all discussed in section aa Appendix D
Table I: Different matrices and corresponding models
Target Matrix B
Estimator Matrix A
Corresponding Model
V 0pmp
Ridgeless regression with signal and noise
Lop
v 1 Inp O:z-noxnd Ouxed
Mismatched ridgeless regression withz signal and noise and mis- match parameter y with y +
12d L's
oRd I
Iaa
or Ind
0
0
non-isotropic ridgless regression noiseless with a polynomial dis- torsion of the inputs scalings
1,6
Iaa
Tndd
PV féw
Random features regression of noisy linear function with W the random weights and (H, deserib- ing a non-linear activation function Further Kernel methods
Opxe
Nxp
Naa d I
vy IN
yKP
V VW2
Vwa
ywal
Learning task:
We consider the problem of learning a linear teacher function fa(x) = B x with and & sampled defined above, and with 3 IRP column vectors. This hidden vector 1
2

---

Under review as a conference paper at ICLR 2023
(to be learned) can potentially be deterministic vector. We suppose that we have data data-points (2), Viliginn with D₁ = B2,, á. = Az,. This data can be represented as the n x d matrix Z E Raxd where of is the i-th row of Z, and the column vector vector E R" with i-th entry y/. Therefore, we have the matrix notation Y ZB3 We can also set X = ZB so that Y = X
In the same spirit, we define the estimator of the student ()(²) = 3 = =² A,3 We note that in general the dimensions of B and 9 (i.e., PA and рω) not necessarily equal as this depends on the matrices B and A. We have Y ZA3 X B for X 7A.
Training and test error: We will consider the training error Egai and test errors Egen with a regularization coefficient R_ defined as
Urain (3) - rIl + + 1131
(I) is well known that the caast-squres estimator 3 = arg min H(3) is given by the Thikonov regression formula 3> = (X"x X + + and that in the limit À - O, this estimator converges towards the fo given by the Moore-Penrose inverse 30 = (XT x) XTY.
(g) B sn 4 (<*AA3 =
Gradient-flow: We use the gradient- floww algorithm to explore the evolution of the test error through time with 05 = 2 a (8,). In practice, for numerical calculations we use the discrete-timg version, gradient-descent, which known converge towards the aforementioned least-squares estimator provided a sufficiently small time-step (in the order of Amax where Xmax is the maximum
ăt
eigenvalue of X 8). The upfront coefficient n on the gradient is used so that the test error seales with the dimension of the model and allows for considering the evolution in the limit d, PA. PB - to0 with fixed ratios 3, Ra_
d Le. We will note @ =
1.3 CONTRIBUTIONS
1. We provide general unified framework covering multiple models in which we derive, in the asymptotic large size regime, the full time-evolution under gradient flow dynamics the training and generalization errors for teacher- our equations reduce to those of Loureiro et al. (2021) (as should be expected). But with our results we now have the possibility explore quantitatively potential advantages of different stopping times: indeed our formalism allows to compute the time derivative of the generalization curve at any point in time.
settings. In particular, in the infinite time-limit we check that
2. Various special cases are illustrated in section and among these simpler re- re-derivation of the whole dynamics the random features model Bodin & Macris (202I), the full dynamics for kernel methods, and situations exhibiting multiple descent curves both function of model parameters and time (See section 3.2 and Appendix [D.2p. In particular, our analysis allows to design multiple descents with respect to the training epochs.
Bodin
3. We show that equations can also capture the learning curves realistic datasets such as MNIST with gradient descent (See section 3.4
(cction[3.4amm and Appendix D.55). extending further the results of Loureiro al. 12021) to the time dependence of the curves. This could be an interesting guideline for deriving scaling laws for large learning models.
We use modern random matrix techniques, namely an improved version of the linear- penail method recently introduced in the machine learning community by/Adlam et al. (2019) to derive asymptotic limits of traces of rational expressions involving random matrices. Furthermore we propose new derivation an important fixed point equation using Dyson brownian motion which, although non rigorig,,, should be of independent interest (See Appendix E
Notations: We will use Tra [-] = limz+++0 1 Tr [-] and similarly for Tr, [-]. We also occasionally use Na(o) lim 1 ||ll| for vector (when the limit exists).
MAIN RESULTS
We resort the high-dimensional assumptions (see Bodin & Macris 2021 for similar assumptions).
3

---

Under review as a conference paper at ICLR 2023
Assumptions 2.1 (High-Dine) (High-Dimensional assumptions) In the high-dineensional limit, i.e, when - to0 with all ratios n. PA. R. fixed, we assume the following d' d' d
1. All the traces Tra [.. Tr, concentrate on a deterministic value.
2. There exists a sequence of complex contours I'd C C enclosing the eigenvalues of the random matrix X E IRddd but not enclosing -X, and there exist also a fixed contour I' enclosing the support of the limiting (when d + +o0) eigenvalue distribution of X X but not enclosing -X.
With these assumptions in mind, we derive the precise time evolution of the test enror in the high- dimensional limit (see result (2T) and similarly for the training error (see result (.4). We will also assume that the results are still valid in the case À 0 as suggested in Mei & Montanari 2209)).
2.1 TIME EVOLUTION FORMULA FOR THE TEST ERROR
Result 2.1 The limiting test error time evolution for a random initialization So such that Na(Bo) ro and [P]]] is given by the following expression:
Egen (1) = co + +r]
with V = 3hT Bd and Co Tra [V*] and:
-1 $ $ (1 e ( - =-(tt))) fi fI y)drdy
1 j 1 1- --(((=+)))
(i(()
2 ft Jr.
f2(2)dz
(x A] A)
= +
(3)
(t(t) -1 21(++t) f fo(z)dz
2it JT
e
(4)
where f1(x,1) f2(x) + f2(1) fi( co and:
f y) Tra (OU ( (G= + (), (6
(5)
f2(2) = co - Tra ( + 1=1)-
(6)
fo(2) = 1 Sz
and Se given by the self-consistent equation:
S. = Tra (OU ( + (+T)=
The former result can be expressed in terms of expectations w.r.t the joint limiting eigenvalue distributions of U and 4 when they commute with each other.
Result 2.2 Besides, when U and V* commute, let u, v be jointly-distributed according to U and V* eigenvalues respectively. Then:
GaGnr" + (1 u)ou? (cuu + (ou + Gy)
22 ou + Co
f( v) Bue,
f2(2) co
Eu,,
Cuu ou + Cz
So =-= Ey
(10)
Notice also that in the limit / + oc:
Bi (+oo) fi(-1, - f1 co.
Bo(+o0) =0
(11)
which leads to the next result.
Result 2.3 In the limit -> oc, the limiting test error is given by Egen (+00)) =
=
4

---

Under review as a conference paper at ICLR 2023
Remark Notice that the matrix V is of rank depending the hidden vector 3 However, is also possible to calculate the average generalization (and training) error over a prior distri-
bution 3* P Averaging Ez--p- [egnn] propagates the expectation within Ea--p- (t)] and
Eg--p- (t)), which propagates further into the traces of Eg--p- [fi] and E3--P- [f]. In fact we find:
Ep- (f- v)] Tra (OU + C.
Ep- (2.))) Ty
(12)
B. [f([2]] co Tra Ep. [OU + (c
(13)
In conclusion, we find that Eg-wp- (ggall follows the same equations as Egen in result 2.1 with E3--p- [V*] instead of V*. In the following, will consider V without any distinction whether comes from a specific vector 3 or averaged through a sample distribution p
Remark 2
In the particular case where U is diagonal, the matrix V* can be replaced by the following diagonal matrix V which, in fact, commutes with U:
[V
[
22 1
V
(14)
[Va]aa|3*13
This comes essentially from the fact that given diagonal matrix D and non-diagonal matrix A, then [DA]a = [D]a[A]a. This is particularly helpful, and shows that in many cases the calculations of fi or f2 remain tractable even for a deterministic f (see the example in Appendix D.3)
Remark Sometimes U AAT and V BB" are difficult to handle than their dual counterparts U. oA A and V. = OB" B together with the additional matrix E = oATB. B. The following expressions are thus very useful (See Appendix(C
(1 Tr, (U+ + (E 12(2) Tr, [(E3* 3h (U.
f1 V)U,) +
(15)
(16)
5= = - Tr
(17)
In fact, when x y = -> (which corresponds the limit when oo), these are the same expressions as (59) in Loureiro et al. 2221 with the appropriate change of variable +11+V) 7 and fi p 2m.
2.2 TIME EVOLUTION FORMULA FOR THE TRAINING ERROR
Result 2.4 The limiting training error time evolution is given by the following expression:
80 e (t) co + +t)))tt)+++1 + Ht(t)
(18)
with:
-1 f o
(1 e - (1 ddddy +
1 of 1 1- ((=+AA)
Hi(t)
h2
(2)2d2
4 Jr
(x A)(++
in Jr 2 A
(19)
-1 $ ho(z+)))o(()d
Holl)
2im pr
(20)
where h (x. v) (2)2)) h2(1) + h (z. v) - co and with 72 = =
1n v) = n, (xx w), h2(z) = n) (cooo((()) + + f2(2)), ha(z) = n=/[(=)
(21)
Eventually, in the limit we find:
222(-21 Hi (+00) 11( (-, - --2--222-222 - --,,
-co: Ho(+ =0
(22)
5

---

Under review as a conference paper at ICLR 2023
Result 2.5 In the limit - oo, we have the relation Ejrii (+00) n/² Egen((00)
We notice the same proportionality factor 2 however interestingly. in the time evolution of the training error, such a factor is not valid as we have h2(2) # M=f2(2).
already stated in Loureiro et al. (2021
5(
APPLICATIONS AND EXAMPLES
We discuss some of the models provided in table and some others in Appendix D
3.1 RIDGELESS REGRESSION OF A NOISY LINEAR FUNCTION
Target function Consider following noisy linear function y(æ) = rx Sg + ae for some constant E R and é (0, 1), and hidden vector S (0, Ip)) Assume we have data matrix X Rx In order to incorporate the noise in our structural matrix B, we consider an additional parameter (d)) that grows linearly with d and such that d p + 9. Let
P' Therefore d = p = Φorb. Also, we let 3*T = (8T ~ NN Ip+g) and we consider an average V over 9 We construct the following block-matri B and compute the averaged V* as follow:
I
V (12
B
2 T-8 115
(23)
0
Now let's s consider the random matrix Z E R and split it into two sub-blocks Z ( The framework the paper yields the following output vector:
Y ZB3 r B6 of
(24)
where & = Σ is used as a proxy for the noise e.
Estimator Now let's consider the linear estimator Ù xT.B, To capture the structure of this model, we use the following block-matrix A and compute the resulting matrix U:
V VoTT = -- - Opxp
-
A =
(25)
09xq
Therefore, is straightforward to check that we have indeed: Y, = 2A3, = XB,.
Analytic result In this specific example, U and V* obviously commute and the result 2.2 can thus be used. First we derive the hint-distribution of the eigenvalues:
2
P pu=0,
+b
(26)
+b
In this specific example, we focus only on rederiving the high-dimensional generalization error without any regularization term (A 0) for the minimum least-squares estimator. So we calculate
Ç -(0) as follows: Ç Ç tb 5 + 0 implies ç² + 0o5 Ç so Ç E {0, - Φo). For f1 we get:
+
22
C
0² g
(1 v)) 1 v (C)
(27)
$ c)
2)
1b ()+
In fact, the expression can be simplified as follow (without the constants Φ v)):
[
d
2
+ +o²
(28)
( c)2
(ou c)
Using both solutions ( = or < = 1 do yields the same results in Hastie et al. (2019) Belkin
et al. 2020 using 2.3
02
de do
(c=0) 0) (c=1-60
Egen (+00) = =1 ,2
(29)
Φ0)
+
1
oo)
1-60

---

Under review as a conference paper at ICLR 2023
3.2 NON-ISOTROPIC RIDGELESS REGRESSION A NOISELESS LINEAR MODEL
Non-isotropic models have been studied in Dobriban & Wager (0118) and then also Wu & Xu (022);; Richards et al. (2021); y Nakkiran et al. (220bb;; Chen al. (2021) where multiple-descents curve have been observed or engineered. In this section, we extend this idea to show that any number of descents can be generated and derive the precise curve of the generalization error as in Figure []
Target function We use the standard linear model (z) 2² 3 for random 3 ~ (a)
Therefore, we consider the matrix B La and thus V La such that 2B3 = -3
Following the structure provided in table 1 the design matrix A is a scalar matrix with P E No sub-spaces of different scales spaced by a polynomial progression a 3. In other words, the student is trained on dataset with different scalings. We thus have U A and Y; ZA3,
Estimator:
Analytic results We refer the reader to the Appendix D.2 for the calculation. Depending if o is above or below 1, Ç is the solution of the following equations: Ç = 0 or = / Di कFa*. In the wverpparameterized regime (Φ < 1), the generalisation error is fully characterized by the equation:
atc ( + a
Egen (+00) = 601 ())
(30)
In the asymptotic limit a + 00, < can be approximated and thus we can derive an asymptotic expansion of (-o((+ for @ E [0. 1] \ & where clearly, the multiple descents appear as roots of the denominator of the sum:
p
Φb1 Φ)
Egen (+o0+
1 2 (0) Φ 0a(1)
(31)
p k=
④ - })
h+1 ②)
Figure 1: Example of theoretical multiple descents in the least-squares solution for the non-isotropic ridgeless regression model with 3, A 10 (left) and p 4, A = 10 (right), and a 10 in both of them.
Interestingly, we can see how these peaks are being formed with the time-evolution of the gradient flow as in Figure 2 with one peak close to e and the second one at -.2 (Note that small requires more computational resources to have finer resolution at long times, hence here the second peak develops fully after t 10a). is worth noticing also the existence of multiple time-descent, in particular at ø = with some "ripples" that can be observed even in the training error.
10
15-
02
2011
30-1
10
1
13:
16"
Figure 2: Example of theoretical multiple descents evolution in the non-isotropic ridgeless regression model
with p == 3, 10 a 100 with on the left and range & E (0, 1) on the right heatmap.
7

---

Under review as a conference paper at ICLR 2023
The eigenvalue distribution (See Appendix D.2.1
phenomena. As seen in Figure 3] the emergence provides insights on the existence of these spike is related to the rise of a new "bulk" of cigenvalues, which can be clearly seen around ø and ø = here. Note that there is some analogy for the generic double-descent phenomena described in Hastie et al. (2019) where instead of two bulks, there is mass in 0 which is arising. Furthermore, the existence of multiple bulks allow for multiple evolution at different scales (with the e (=+-A) terms) and thus enable the emergence of multiple epoch-wee wise peaks.
10
005
04
-11
01
0.00
00
Figure Theoretical (log-)eigenvatue distribution the non-isotropic ridgeless regression model with p= 3, À = 10 = 100 with ø = on the left and a range & E (0,1) on the right hcatmap.
3.3 RANDOM FEATURES REGRESSION
In this section, show that can derive the learning curves for the random features model introduced in Rahimi & Recht (2008), and we consider the setting described in Bodin & Macris (202)) In this setting, define the random weight-matrix W RexN where 4/o N such that Wi NO0, })) and d
N and ó 2. セ 2. and Φu = 2 ad = (1 + ()) So with Z = /VXxj V /
(thus
d p
F.). using the structures A and B from table | we have: ZA pXW + Ula and ZB X + of. hence the model:
f ZA3 (μXW + x22)
(32)
Y = ZB3
X + oE
(33)
With further calculation that can found in Appendix D.4 a similar complete time derivation of the random feature regression can be performed with much smaller linear-pencil than the one suggested in Bodin Macris (202T). stated in this former work, the curves derived from this formula track the same training and test error in the high-dimensional limit the model with the point-wise application of a centered non-linear activation function f E (e o dz) with Ý 1= (VF More precisely, with the inner-product defined such that for any function vp
E (e 2² dr), (f.g) = EE-N((,1) (f (x))g())) we derive the equivalent model parameters (p, v) with (f, He,), 2² (f.f) - while having the centering condition (f. He,) = 0 where (He..) the Hermite polynomial basis.
This transformation is dubbed the Gaussian equivalence principle and has been observed and rig- orously proved under weaker conditions Pennington & Worah (2017); Péché (2019); Hu Lu (2022). and since then has been applied more broadly for instance in Adlam & Pennington (2020a).
3.4 TOWARDS REALISTIC DATASETS
As stated in Loureiro et al. 202 the training and test error of realistic datasets can also be captured. In this example we track the MNIST dataset and focus on learning the parity of the images (y +1 for even numbers and = -1 for odd-numbers). We refer to Appendix DD. for thorough discussions of Figures 4 and 5 as well technical details obtain them, and other examples. Besides the learning curve profile at = +oo, the full theoretical time evolution is predicted and matches the experimental runs. In particular, the rise of the double-descent phenomenon is observed through time.
8

---

Under review as a conference paper at ICLR 2023
and
288
Figure 4: Comparison between the analytical and experimental learning profiles for the minimum least-squares
estimator at À = 10-3 on the left (20 runs) and the time evolution at À = 10 700 on the right (10 runs).
Training error
Test error
10"
15
13
11
10P
18
08
Figure 5: Analytical training and test heat-maps for the theoretical gradient flow for A 10
CONCLUSION
The time-evolution can also investigated using the dynamical mean field theory (DMFT) from statistical mechanics. We refer the reader to the book Parisi et al. (2020) and a series of recent works Sompolinsky et al. (1988); Crisanti & Sompolinsky 2018); Agoritsa et al. (2018); Mignacco et al. (2020) 2021) for an overview of this tool. This method is a priori unrelated ours and yields set of mon-linear integro-differene not solvable analytically and one has resort numerical solution. It would be interesting to understand if for the present model the DMFT equations can be reduced to our set of algebraic equations. We believe
equations for time correlation functions which are in general
be fruitful endeavor compare in detail the approaches: the based on DMFT and the one based on random matrix theory tools and Cauchy integration formulas.
Another interesting direction which came to our knowledge recently is the one taken in Lu & Yau (2022): Hu & Lu (2022) and in Misiakiewicz (2022); Xiao & Pennington (2022), who study the high-dimensional polynomial regime where d for fixed K. In particular, it is becoming notorious that changing the scaling can yield additional descents. This regime is out of the scope of the present work but it would be desirable explore the linear-pencils and the random matrix tools that we extensively use in this work can extend to these cases.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ben Adlam and Jeffrey Pennington. The neural tangent kernel in high dimensions: Triple descent and multi-scale theory of generalization. In Hal Daume IIII and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 74 84. PMLR, 13-18 Jul 2020a. URL http::/pprcceediiiieeee press/vi19) 20tp://1111/aaaa22..a.aaaa html
mll
Ben Adlam and Jeffrey Pennington. Understanding double descent requires a fine- fine-grained bias- variance decomposition. Advances in neural information processing systems, 33:11022 15:11022-11000 1032, 2020b.
Ben Adlam, Jake Levinson, and Jeffrey Pennington. A Random Matrix Perspective on Mixtures of Nonlinearities for Deep Learning. arXiv e-prints, art. arXiv: 1.X.:19912.00827, December 2019.
Madhu S. Advani, Andrew M. Saxe, and Haim Sompolinsky. High-dimensional dynamics of generalization enror in neural networks. Neural Networks, 132:428-4444 2020. ISSN 0893-6080. doi: https://ooo.rr////.0oloo....eeet
022. URL https: http://wwwwccinnncieeeeee
com/ http://cccooooerrreeeee/////////
Elisabeth Agoritsas, Giulio Biroli, Pierfrancesco Urbani, and Francesco Zamponi. Out-of-equilirrimm
dynamical mean-field equations for the perceptron model. Journal of Physics A: Mathematical and Theoretical,, 5 (1(8):00000 Jan 2018. ISSN 1751-8121. doi: 10. 10-088/1751-812//aa
URL
http: doi org 1088 11t.:/11111111111111111 8121/ aaaa6d
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, (16:201903770, 07 2019, doi: 10. 10.1073/pnas. /tt.//aa...100001111.1 19030701 16.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4): 2020.
Antoine Bodin and Nicolas Macris. Model, sample, and epoch-wise descents: exact solution of gradient flow in the random feature model. Advances in Neural Information Processing Systems, 34, 2021.
Blake Bordelon, Abdulkadir Canatar, and Cengiz Pehlevan. Spectrum dependent learning curves in kernel regression and wide neural networks. In International Conference on Machine Learning, pp. 1034-1034. PMLR, 2020.
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, Ben- jamin 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 (eds.), Advances in Neural Information Processing Systems, volume 33, neuripps...e..ss. pdf
1877-1901. Curran Associates, Inc., 2020. URL (cc/appe//222//ELee1111766666632 96741 Bbwbaacc14eeeaa-22111
Johl Bun, Jean-Philippe Bouchaud, and Marc Potters. Cleaning large correlation matrices: tools from random matrix theory. Physics Reports, 666:1-109, 2017.
Lin Chen, Yifei Min, Mikhail Belkin, and Amin Karbasi. Multiple descent: Design your generalization curve. Advances in Neural Information Processing Systems, 34, 2021.
A. Crisanti and H. Sompolinsky. Path integral approach to random neural networks. Phys. Rev. E. org
98:062120, 220 Dec 2018. doi: 10. 10.1103/PhsseevE.988 E...0........012....... URL doi/10. 1103/11100Peeeee
08.0621222 02120
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 (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 3058 3069. Curran Associates, Inc., 2020. URL URJ/ttpps.//prceednnng new.eeeedddiinneeeeeeeeeee..eeee cctpppppeeccccpppe/e/eeee / F000
10

---

Under review as a conference paper at ICLR 2023
Zeyu Deng, Abla Kammoun, and Christos Thrampoulidis. A model of double descent for high- dimensional binary linear classification. Information and Inference: A Journal of the IMA, 11(): 435-495, 04 2021. ISSN 2049-8772. doi: 00.1099/imaiia/iaaa0022. BRLhhtpps: httLhtts:///o..oo0 http://ooooorroooo 10. 1093/ ma a aab002
Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1 46(1):247-279, 2018.
Stéphane d' Ascoli, Maria Refinetti, Giulio Biroli, and Florent Krzakala. Double trouble in double descent: Bias and variance (s) in the lazy regime. In International Conference on Machine Learning, pp. 2280-2290. PMLR, 2020.
Andreas Engel and Christian Van den Broeck. Statistical mechanics of learning. Cambridge University Press, 2001.
Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d' A'Ascoli, Giulio Biroli, Clément Hongler, and Matthieu Wyart. Scaling description of generalization with number of parameters deep learning. CoRR, abs/1901.01608, 2019. URL ltttp://rxxiv
orq/ 1901. 01608
Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mézard, and Lenka Zdeborová. General- isation error in learning with random features and the hidden manifold model. In International Conference on Machine Learning, pp. 3452-3462. PMLR, 2020.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in High- Dimensional Ridgeless Least Squares Interpolation. arXiv e-prints, art. 1rXiv:1903.08560, March 2019.
J William Helton, Tobias Mai, and Roland Speicher. Applications of realizations (aka linearizations) to free probability, Journal of Functional Analysis, 274(1):1-79, 2018.
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXiv preprint (.xXiv:2233.155555 2022.
Hong Hu and Yue M Lu. Sharp asymptotics of kernel ridge regression beyond the linear regime. arXiv preprint arXiv:2205.0677 2022.
Ganesh Ramachandra Kini and Christos Thrampoulidis. Analytic study of double descent in binary classification: The impact of loss. In 2020 IEEE International Symposium on Information Theory (ISIT), pp. 2527-2532, 2020. doi: 10. 1109///TT44448..00001117777
Licong Lin and Edgar Dobriban. What causes the test error? going beyond bias-variance via anova. J. Mach. Learn. Res., 22: 22:155-1, 2021.
Bruno Loureiro, Cédric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Mare Mézard, and Lenka Zdeborová. Capturing the learning curves of generic features maps for realistic data sets with a teacher-student model. arXiv preprint 202.:::022.0880 2021.
Yue M Lu and Horng- -zzrr Yau. An equivalence principle for the spectrum of random inner-product kernel matrices. arXiv preprint arXiv:2205.063008 2022.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv e-prints, art. 1xXiv:1908.05300 August 2019.
Francesca Mignacco, Florent Krzakala, Pierfrancesco Urbani, and Lenka Zdeborová. Dy- namical mean-field theory for stochastic gradient descent in gaussian mixture classifica- tion. In H. Larochelle, M. Ranzato, R. Hadsell, M. E. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 9540- 9550. Curran Asso- ciates, Inc., 2020. URL hec.:/DDOOnllittttaaapppooeeoee wwwp:eediiinnnnnniiss..r.eom Shceleeeeeeeeoo05555504445552522 /ttp:////ecpooauuu....o..ooaaaar

---

Under review as a conference paper at ICLR 2023
Francesca Mignacco, Pierfrancesco Urbani, and Lenka Zdeborová. Stochasticity helps navigate rough landscapes:
comparing gradient- descent- based algorithms in the phase retrieval problem. Machine Learning: Science and Technology, 2021.
James A Mingo and Roland Speicher. Free probability and random matrices, volume 35. Springer, 2017.
Theodor Misiakiewicz. Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression. arXiv preprint arXiv:2204. 10425, 2022.
Prectum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang. Boaz Barak, and lyya Sutskever. Deep double descent: Where bigger models and more data hurt. In International Conference Learning Representations, 2020a.
Preetum Nakkiran, Prayaag Venkat, Sham M Kakade, and Tengyu Ma. Optimal regularization can mitigate double descent. International Conference on Learning Representations, 2020b.
G. Parisi, P. Urbani, and F. Zamponi. Theory of Simple Glasses: Exact Solutions in Infinite Dimensions. Cambridge University Press, 2020. ISBN 9781 107191075. URL http:::tp//.......t.. //books woooooooooolleee.....ooooooooo..
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 (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, neurips cc/ /ppper// Abstract html
CA, USA, pp. 2637-2646, 2017. URL 2017/hash/ OF 3eeede01eee33333333333 httt://eeccccccaaaaaaeaaaaaaaaa0
Mare Potters and Jean- phi-PPilippe Bouchaud. First Course Random Matrix Theory: For Physicists, Engineers and Data Scientists. Cambridge University Press, 2020.
S. Péché. A note the Pennington- -Worah
Worah distribution. Electronic Communicationns in Probabil- ity. 24(none):1 - 7, 2019. doi: 10.1214/1--ECP26. URL 19- ECP
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2008 URL httpstts//oocceeiinnnnsss neeeennuuuii spsripp.... ec/ .pdf]
Reza Rashidi Far, Tamer Oraby, Wlodzimierz Bryc, and Roland Speicher. Spectra of large block matrices. arXiv e-prints, art. cs/0610045, October 2006.
Dominic Richards, Jaouad Mourtada, and Lorenzo Rosasco. Asymptotics of ridge (less) regression under general source condition. In International Conference on Artificial Intelligence and Statistics, pp. 3889-3897. PMLR, 2021.
Francisco Rubio and Xavier Mestre. Spectral convergence for general class of random matrices. Statistics & probability letters, (5):559 602, 201
H. Sompolinsky, A. Crisanti, and H. J. Sommers. Chaos in random neural networks. Phys. Rev. Lett., org/
61:259 262,, Jul 1988. doi: 10. 10.1103/PhyReeeLett......33 61.259
URL
#b.//00.1103/Piyseeeieettt
Stefano Spigler, Mario Geiger, Stéphane d' Ascoli, Levent Sagun, Giulio Biroli, and Matthieu Wyart. A jamming transition from under-to aver-parametrizattoon affects gemeralization in deep learning. Journal of Physics A: Mathematical and Theoretical, ( 52(47))474001, 2019.
Denny Wu and Ji Xu. On the optimal weighted 12 regularization in overparameterized linear regression. Advances in Neural Information Processing Systems, 33: 101 101 2020.
Lechao Xiao and Jeffrey Pennington. Precise learning curves and higher-order scaling limits for dot product kernel regression. arXiv preprint arXiv:2205.14846 2022.
12

---

Under review as a conference paper at ICLR 2023
A GRADIENT FLOW CALCULATIONS
In this section, we derive the main equations for the gradient flow algorithm, and derive and set of Cauchy integration formula involving the limiting traces of large matrices. The calculation factoring out in the limit d - oc is pursued in the next section. First, we recall and expand the training error function [
Grain (3e)
1
I
8
1811
(34)
71
71
1
2 |
2
8 + -ー7 111,112
(35)
71
n
1
|2B3*
12
2
233 T B² ZA 3f A" ZAB, + 111.112
(36)
7
n
Let K (XTX +
(A ZA A1) which is invertible for 0. Therefore, can
write the gradient of the training error for any / as:
Erain (3) X - + AB = (X + +1) - - XTY
(37)
The gradient flow equations reduces to a first order ODE
0
n2 0 2
ed train (3x) = x - K- 1-tBt
(38)
The solution can be completely expressed using L, (1 exp( -tK 11 as
B. exp( 1opp-tk- + (I exp(-ttp 1) y
(39)
(I- L
(40)
In the following two subsections, will focus deriving expression of the time evolution of the test error and training error using these equations averaged over the a centered random vector 8o such that r 2
A.1
TEST ERROR
As above, the test error can be expanded using the fact that on No, = -0, 2), we have the identity EzwNo [2=]] Ld:
Egen (3,) = Ez-No [(2 A3, - 2² B
(41)
(A3r- B3 " (1A, -
(42)
1 U UB: - 2
g. g'T BT AB: + 1 g
d B7
BJ ""BB"B B3
(43)
So expanding the first term yields
UB. (9) (I L,) + 3 X" L.) + LKX"X
(44)
3% (1 - (.)LL)(I--A LI
(45)
+ 2B"" LA ZB)
(46)
+ 2 (1- (A 2B)3
(47)
while the second term yields
8 BT AB TT BT A((T 1.) L
(48)
= -T BT A(T L.)30 + TT (A zt 2B)3
(49)
Let's consider now the high- nigh-dimensional limit Egen(t) (t) = lim Egen (3t). We further make the underlying assumption that the generalisation error concentrates on its mean with Sy that say: Egen (L) lima- Es,, [Egem()))] Let V B,3 3 Bd and co- = Tra [V*], then using the former expanded terms in 41 we find the expression
Egen (t) co + Tra [AT
AA (
(50)
+ Tra [TT (ZZAALL zv* 2Tra (AL.KAZZ'ZV'
(51)
13

---

Under review as a conference paper at ICLR 2023
So Egen(t) cu rtt((t) + B1 (t) with:
(t( Tea [A" -e) A] (t) = Tra [Z" LAKLLLKA ZV*] 2Tr [ALKKA 8 z2 2V4
(52)
(53)
Let ((2) - =1)-
the resolvent of X X, and let's have the convention K (-x)
-
to remain consistent with the previous formula. Then for any holomorphic functional f: U + C
defined on an open set U which contains the spectrum X with a contour in enclosing the spectrum X X but not the poles of f. we have with the extension of f onto C"xa; f(X*
=1 21r fr (=)) (=)dz. For instance, we can apply it for the following expression:
KL = LiK = (1 - exp( sxp(-tt"Xx + tX)) X1)
(54)
-1 1 - -((+A)
(X
21)- K(z)dz
(55)
2im Jr 2
-1
-1=+
(56)
2im
Jr
So we can generalize this idea to each trace and rewrite B1 (t) and (t( with
-1 of $f (1 - - -- Bi(t)
fi fI yrdd + 1 - ((=-))
1 Jr 2+
fz(2)dz
4 Jr
(x + 1) + A)
(57)
-1 $ e 21(++)) ( fo(z)dz
(t( 21tT Jr
(58)
where we introduce the set of functions (a, y). f2(2) and fo(2)
f1 9) Tra (() 2 ZV*]
(59)
f2(=) = Tra A===="""²²zV"
(60)
fo(=) = Tra [AK(=)A*]
(61)
Let = =-)- using the push-through identity, it is straightforward that AK(2) This help us reduce further the expression of fi into smaller terms which will be easier to handle with linear-pencils later on
S1 (x, Tra [ ZUG((=) GW)
(62)
Tra [(G(=)-) (((d0"""*+"((((d))))))()))0)"11) +V]
(63)
-Ta [(T (T++ ((++)
(64)
co + yTr [[()) [Ga zyTra (GT))
(65)
Similarly with fz and for they can be rewritten as
fa(=) = Tra [G(=)Uz"Zvy]
(66)
Tra [G())
(67)
= co + TTra [G(=)V" [()))
(68)
fa(z) Tr. [G(=)U]
(69)
Hence in fact the definition f1 y) = TyTTa G(y)) such that
f( fe(2) + fe()) + (x. co
(70)
At this point, the equations provided by 57e valid for any realization Z in the limit d + co. We will see in the next section how to simplify these terms by factoring out Z.
14

---

Under review as a conference paper at ICLR 2023
A.2 TRAINING ERROR
Similar formulas can be derived for the training error. For the sake of simplicity, we provide a formula
to track the training error without the regularization term, that is say E (3.) (as in Loureiro
et al. (2021) ) while still minimizing the loss E (Bt). So using the expanded expression 34 and
considering the high-dimensional assumption with concentration E (t) = lim Eainn
lim E8 [Erain (3e) we have
E (t) Trn [2-'VV' + Tr,
-e) + Tr, Z' ZALL ZV
(71)
(72)
2Tr,, 2 ZALLKAAZZZ IV*
(73)
First of all, standard random matrix results (for instance see Rubio & Mestre (2011) assert the result Tra 1Z" ZV*] Tra |z" 2] Tra [V*]= = pog- This result can also be derived under our random
matrix theory framework, for completeness we provide this calculation in C.2 Therefore, we can
define (t) and H. (t) such that
Garai (t) = co + +2Ho(()++00 + Ht(t)
(74)
where we have the traces
Ho(t) = Tr, ZAI - [.)
(75)
(t) = Tr, (Z"Z z" (" 2Tr, "ZAL,KAZ""ZZ"
(76)
And using the functional calculus argument with Cauchy integration formula over the same contour r we find
(t(()) = 2 f..
f
e (11 ---(())))
(x + + 11 (drdy + in f.
1 (1 (1-o-d(+t))
ha(2)dz
(=+
(77)
(t
2it f
-1 (222(
(78)
Where we the traces (which only contain algebraic expression of matrices):
h1(2,)) = Tr. [ (AT ZAT K (w)AT h2(2) Tr, IzT ZAK(3)A"=""ZZ) zv*]
(79)
(80)
ho(2) -Tr, [ ZA""K2)AA"
(81)
The expression of h1 can be reduced to smaller terms as before with fi
σh (z, v) Tra
(82)
Tra [(C""""=t11(dd])]"777])))'C v
(83)
= Tra [z"ZV*]+xll [G(x) 7" [G(=)"Z"ZV'] + yTra zG(
(84)
+ zy/Tra [z" C(())
(85)
-oo xTrxxTraa =Tra + yTta l VG
(86)
+ TyTra 1 [zT
(87)
and similarly with h2
xh2(2) Tra ( 2V
(88)
= Tra ([(=))))(())+++111)(
(89)
-Tra [Z"=ZzZ'' + TTTr, (2" VG(2)V"
(90)
=cu TTa [7' [G(=)V"
(91)
and similarly with ho
<ho(=)= = Tra [2d
(92)
Tra [C(=)
(93)
= -1 1++Tra|G(s))
(94)
We can also define the term h1 v) myTr, G(=))"" so that:
hn (x, h2(x)) ha(v) + h, (z, Co
(95)
15

---

Under review as a conference paper at ICLR 2023
B TEST ERROR AND TRAINING ERROR LIMITS WITH LINEAR PENCILS
In this section we compute a set of self-consistent equation to derive the high-dimensional evolution of the training and test error. We refer to Appendix for the definition and result statements concerning the linear pencils.
We will derive essentially two linear sheear-pnncils of size 6 and 4 which will enable to calculate the limiting values for fi, f2. fo for the test error, and h1, h2, ho for the training error. Note that these motticmtt are derived essentially by observing the recursive application of the block-matrix inversion formula and manipulating it so as obtain the desired result.
Compared to other works such as Bodin & Macris (2021 Adlam & Pennington 2020a). our approach yields smaller sizes linear-pencils handle, which turn yields smaller set of algebraic equations. One of the ingredient of our method consists in considering multiple-stage approach where the trace of some random blocks can be calculated in different parts (See the random feature model for example in Appendix D.4). However, the question of finding the simplest linear-pencil remains open and interesting to investigate.
B.1 LIMITING TRACES OF THE TEST ERROR
LIMITING TRACE FOR f1 AND fo
We construct a linear- peecrrpencil... M1 as follow (with Z the random matrix into consideration)
0
0
0
yI
0
Z
0
0
Z
0
0
0
1
0
M1
(96)
rl
0
U
ryy
0
0
Z
1
0
0
Z
0
0
The inverse of this block-matrix contains the terms in the traces of and fo. To see this, let's calculate the inverse of M1 by splitting it first into other "flattened" blocks:
0
BTT D
(-
B DD
B-1
M1
M
(97)
B
BT
Where B, and D are given by
xI
0
U
VVV*
B
7T
T
==
0
0
(98)
1
0
then to calculate the inverse of Br, notice first its lower right-hand sub-block has inverse
7
(99)
Which lead to the following inverse using the block-matrix inversion formula (the dotted terms aren't It required):
G(x)
-G(xJU
G(rUUZ
B
-ZG(z)
In - ZG(T)UZZ
(100)
ZG(()(
(9) With 94 the trace of the squared sub-block (M- divided by the size of the block (ij), we find the desired functions
[r v)
d -9d
lim (11)
(101)
fo(x)=
lim d+++00
-9
(15)
OR
fo(y)
lim
-9
(51)
(102)
d
16

---

Under review as a conference paper at ICLR 2023
Let's now consider the limiting value of gd, and calculate the mapping n(g):
0
0
0
(g(20)
0
0
0
0
0
(15)
0
0
0
0
0
7(9)= =
(103)
0
0
0
0
0
og (62)
0
0
0g
(22)
0
((5))
0
0
0
g
(11))
So we can calculate the matrix (T) ) such that the elements of are the limiting trace of the squared
sub-blocks of (TT( (divided by the block-size) following the steps of the result in App.
0
0
yl
og (26)
0
0
(1
((5)))
0
0
0
U
I
0
(11 =
(104)
-II
U
-xyV*
0
(02))
(62)
(22)
0
(1-
g
((1)))
Therefore, there remains to compute the inverse of 11(M)). We split again I1(M)) sub-blocks to make the calculation easier
flattened
B
B D 1
B
11(M)) B2
D
1((M)--
(B,1)
(105)
With the three block-matrices
-xl
U
xl By
B₂ =
(62)
g (26) Φl 0
I
(106)
(51)))
(1
و
((s)
)
0
ryy V
0
g (22)
1a
(107)
straightforward application of the block matrix inversion formula yields inverse of B
B- (øg (22)
U- -xx=-= -Uló (02) - xI)
(1 - ((51))-11
(108)
(bg (22) (og
(2)) xf)-
(62) (62) xT)
Therefore, retrieve the following close set of equations:
(1)) Tra (g (22) (2
ΦU x1) - (ayV* + 9 222) ( (g)
(U yy
(109)
22) g (11) (1 (16)) 11 (51))-1
(110)
(26) = (1 - g (51))-1
(111)
g (15) = Tra Ui (62) Φl - x1-
(112)
These equations can be simplified slightly by removing g (22), (266) and introducing (13))
(1))) -Tra (OU -xg 1) (ryg (5)) (51) y + 9 oU>) yg 1-
(113)
(15) Tra (OU xa I q 16) U 21) (1] 1|
(114)
g (1s) y (15)
(115)
Let G. = - (15), or by symmetry Cy = - then using the fact that (z, -- and
fo(x) (15) we find the system of equations
[ Tra (OU + CoT) (S.G,V' + {(2,,))03) (1
(116)
fo(x) 11 Sxe
(117)
I
==-22 - Tra (oU [=T)
(118)
17

---

Under review as a conference paper at ICLR 2023
Remark:
As byproduct of this analysis, notice the term g( (g(16))-1
In fact
have:
(22) = Tra nn - [G(=)U2"
(119)
1 -rn, -= =I"
x1)
(120)
1 Trn (ZAA ""AAA"===I>> -211--AAA'
(121)
Trn [XX* - -x1) -x1) xla + xln)
(122)
= ITnn (XXT- -xl)
(123)
So if we let m(x) = Tra
(XX* -x)-1111)1 the trace of the resolvent of the student data matrix, we
find that mxx) Cz This can be useful for analyzing the eigenvalues as in Appendix D.2.1
LIMITING TRACE FOR
As before, we construct second linear- seear-penncll M2 with Z the random matrix component into consideration
0
0
0
>V*
-z1
0
U
M2
(124)
0
z
I
Z
0
The former flattened block B₃ can be recognized in the lower right-hand side of M2, thus we can use the block matrix-inversion formula and get:
=G(2)V*
Mr ZZG(()
(125)
B=²
x2 >Z"zZG(2\V'
Now it is clear that we can express f2(2) = + lima-+ 9d calculate the mapping
(21) Following the steps of App. E we
0
0
0
7(g) =
0g
(34
(126)
g (23)
Which in returns enable us to calculate (T(M2)
I
0
0
zV+
=T
0
U
[(M2))
0
((34)
01
0
(127)
(1 (1-
(1-g(28)
(28))
0/
To compute the inverse of (TM2)), the block-matrix is first split with the sub-block B2 defined as follow
U
B,
(300
(I(M))
(128)
B
(1 (23) T
straightforward application of the block-matric inversion formula yields the inverse of B3:
(g (34) pl -11
-U(g((44 ol =1)-1
B-
(1 g (23)
((23))-21
-
(129)
(30 34) SU =T)-1
(3)
(34) BU =1)-1
Hence we can derive the inverse
x34( Ø =1) - -1
IIM -
(130)
B.
zg (34) (34))((((()))))))))))))))) ((g((4))))) Φl z1) -Iv
18

---

Under review as a conference paper at ICLR 2023
Eventually, using the fixed-poins result on linear- tinea-ppnncils, we derive the set of equations
g(21) Tra
2V (34) (g( ΦU - =1)=
(131)
g (24 (1 g (2)))
(132)
9 23) -ra U(( (34) ΦU =1)-1
(133)
g (4)) Tra
2g (24) (0g
(34) ΦU 2v-
(134)
g (2 Tra [g (1)) DÙ 21) =1)-1
(135)
(136)
In fact, straightforward to see that g f223) g ((04) follows the same equations as the former g g(1o), . (20) in the previous subsection, therefore g(23) g (15) = g(15) + $g and thus
g(oe) C. Eventually we get g(2 Tra (OU + (=1) so in the limit d + co:
f2(=) = cg Tra [c. (BU + []
(137)
B.2 LIMITING TRACES FOR TRAINING ERROR
LIMITING TRACE FOR h1
A careful attention to the linear-pencil M1 shows that the terms in the trace of h2 are actually given by the location g(22) We have to be careful also of the fact that (Mr+) is block matrix of size n X n, so is already divided by the size n (and not d). Hence we simply have with 7/2 = 7.
Tn (a. u) -g -g (22)
y f1 v) (
(138)
Se. Sy
LIMITING TRACE FOR h2
In the case of h2, need the specific term provided by the linear-pencil M2 by the location ( with @z2(z) coo + ((4))
For h2 we use the linear pencil for f2. but instead of using ((2 we use ho eoch g(1)) We find:
(41) ToTra [V* (oU + (=1)-11
(139)
z Tra [Se (oU + [.
(140)
G2
Φ - (co - [2(2))
2
(141)
Hence:
h2(2) co
(1-
-2
+ -2 f2(2) (Caf((()))++ f((z))
(142)
5e
LIMITING TRACE FOR ho
Finally for ho we use again the linear pencil M2 with:
Tra [=G(=)] = zg
Tra (= 11
+
(143)
- Tra [(Ss + OU - (0U + -1
(144)
1 + оTTA [U(OU + (c
(145)
1 + Tra (OU + [
(146)
1
(C= + 2)
(147)
Therefore:
ho(z) =
1 -1-
= 1
-2 = =)))(²)
(148)
-,
-2
19

---

Under review as a conference paper at ICLR 2023
C OTHER LIMITING EXPRESSIONS
In this section we bring the sketch of proofs of additional expressions seen the main results.
C.I EXPRESSION WITH DUAL COUNTERPART MATRICES U, AND V.
The former functionals /2 and can be rewritten as:
[2) co Tra (OU
(149)
Co Tra [(S=] + @U GU)V + +
(150)
= Co - Tra [V]] + Tra (
(131)
= co + Tra (0 38" AUU +
(152)
Tr, [E (U. +6
(153)
With similar steps using:
(S
(154)
We find:
(2 -co - Tra (
(155)
+ Tra [OO + ( 611)-
(156)
c f2(x)) - f2(1)
(157)
+ Trn (U,
3 "(. (,
(158)
Hence in fact:
f1 = Tr, (U. G + (, +
(159)
Finally, we have using the push- through identity and the eyclicity of the trace:
Sa - - Tra (OAA" + +
(160)
= + Tra
(161)
+ Tra [S.U. (.1)=
(162)
C.2 LIMITING TRACE OF ZT ZV*
Here we show another way which our random matrix result can be used infer the result on the limiting trace Tra [ zV* To this end, we can design the linear- lincar-pencil:
V*
0
0
0
I
z
0
M3
(163)
Z
0
0
T
is straightforward to calculate the inverse of the sub-matrix:
1
z
0 2
- 2
ZT
200
1
-7
(164)
0
1
0
1
So that:
I
V
V -F
M5
0
I
-
ZT
7
(165)
0
0
1
-6
0
0
1
20

---

Under review as a conference paper at ICLR 2023
At this point, it clear that the quantity of interest is provided by the term ((14) of the linear- linear-pencil
Mg. We find calculate further:
0
(33)
(1
(166)
0
(42)
0
0
Based the inverse of M3. can already predict that g(oa)
and g
Hence:
I
V
0
V
0
ΦV*
0
-61
ΦI
(TMaa)=
(TMM))
(167)
0
1
0
0
T
0
0
Finally we obtain (144) Tra [øV*], and hence Try "2"'V")
TTa [V*].
D APPLICATIONS AND CALCULATION DETAILS
D.1 MISMATCHED RIDGELESS REGRESSION OF A NOISY LINEAR FUNCTION
Target function Here we consider a slightly more complicated version of the former example where let 01)
and still averaged over 8o NO, Inp) and 31 ~ (0, ((->))) with zo E RRP, 21 E R(1-t)p, We let again d = p + q and sb = 2 and Φp P. Therefore the former relation still holds & = = dor. Similarly, we derive a block-matrix B and compute V
(x) S8 2 (ī)
pp
0
0
B
d TV
0
V
0
(1-9)9
(168)
p
0
oV
0
I-
So that with the splitting { ΣØ;;
(V 2 X T.). and 3+H
(36 13 (357). and with
== ZB3 = x + +1 + of
(169)
Estimator Following the same steps, we construct and U with
TP Lyp
L
L pp
0
0
A
=
(11-)pp7d
-
0
0
0 0
(170)
Opxyd
0
0
So that we get the linear estimator Y
Y, ZA8
Xo33
(171)
V
Analytic result U and V commute again, the joint probability distribution can be derived:
1
V
7Φ
(172)
76b
16
2
p u = 0,
(1 - 7)
(173)
+
u 0,
(174)
(1 +b)
do calculation leads to the following result (dubbed the Therefore, in the regime with k:
"mismatched model" Hastie et al. 2019
(02 + (1- (R>1) 1) x x-1
Egen( (000) =
(175)
22 (1 - x) <
21

---

Under review as a conference paper at ICLR 2023
D.2 NON ISOTROPIC MODEL
We have the joint probabilities Then:
a = 1) = - - for i E (O.....P - 1] and x = 0.
1 p-1
f f (a
(176)
(0 + of)?
P E0
1
(177)
P i=U
p-1 Sa
f2 = co
(178)
Φ + a
So either Ç = and thus f1 = 0, or 5 + and:
p-1 1
(a'()2
f =
1
(179)
+ a C)2
(0 +
==0
==0
1
1
1=
(180)
p i=0
0+ aa6
Writing further down (a²()² = (a'S + Φ - x) = (a'5 + x)2 - -2ø(a'5 + 6) + Φ² we get:
(a
= -1-20 20 Σ
1 p-1
+ +
p-1
(181)
P
( a((2
Φ + a²5
(o+
i=0
=1-26 + 0
1
(182)
P i=0
1- 1 p-1
=1 3)
(183)
p
So:
(1-1 1 p-l
Σ
h = (1 Φ)
-
(184)
1=0
Now injecting the expression for Ç:
p-1
Φ
(185)
( c
(o (
E
atc
(186)
Hence the formula
-1
( a²c
= (1- b)
(187)
(o+ otc)
Asymptotic limit: Let's consider the behavior of the generalisation enror when a + 00. Let's consider the potential solution for some k E (O......P - 1}:
*== = at
Ck (1 + oa
(188)
for some constant ck. Then:
p l
p = Σ
δ +
*(1 + -
1
(1++oa11) (1))
=
Φ + ck
1
+ k + oa (1)
(189)
0=
22

---

Under review as a conference paper at ICLR 2023
Hence choose:
Ck
(190)
po k
Because Egen (0o) 2 O, we need to enforce 5*
> 0 which leads to the condition pa-k 2 0, that is
1
1 2 pó 0. So fact it implies o E
k-1
so 5* can only be solution for in this range.
p
Therefore we can consider the solution ((Ø)
Σ
| # (0)
(Ø). Then notice:
Σ (0 1 + atth)
Ck
+ +0a = =p²
Φ k 1 (1)
(191)
(ok + t)?
p
and thus for @ [0. zz:
p-1
6(1 σ)
Egon (20)
Σ
1 11:
- - oa(
(192)
k+1 ②
k=0 p
So we clearly see that in the limit of a large, the test error approaches function with two roots at the denominator.
Evolution:
((x,y)= = 1 p-1
_
() + ar
(193)
p p0
a' +
1
5=
-2+ +
(194)
P 1=0
Φ a
a'C=
fe(z) =
Σ
(195)
Φ
+ c
In particular is given by:
fa(2) co- p a'c, co 1 o6o (1 Eo
(196)
and fi is given by:
1 Diz (ota' (ot
2 CoCy
(197)
D. (ata Mota""ootttG
D.2.1 EIGENVALUE DISTRIBUTION
In our figures, we look at the log-eigenvalue distribution of the student data Plog as it provides the most natural distributions on log-scale basis. So in fact, if we plot the curve y(x) Plog (x) have:
y(r) = Plog a (x) = P(log xx)
(198)
gx
P(A S e²)
(199)
e" P> (x(ee)
(200)
So in log-scale basis we have Plog a (log x) xxx(x)) It is interesting to notice the connection with T for running computer simulations:
2² lim m(x x + ic) π +
1 lim
r+ ic <(x
Plog A (log r)
lim Matte
(201)
+
ie)
c
is work mentioning that the bulks are further "detached" as a grows as it can be seen in figure 6 Furthermore, bigger makes the spike more distringuisable.
23

---

Under review as a conference paper at ICLR 2023
10-
05
0.15
0.8
05
4
0.6
0.3
02
04
01
02
01
0.00
0.0
10 13
10"2
10"7
10:33
10:9
10"7
10-3
10'2
10"4
10-
Pra
Figure 6: Theoretical (log- boggeeeieeevllue distribution in the non-isotropic ridgeless regression model
with = 3, = 10 a 10t with ø on the left and a range (0, 1) on the right heatmap.
D.3 KERNEL METHIOSS
Kernel methods are equivalent to solving the following linear regression problem:
T1
B arg min Σ
(0% (()) - 3 (xx:)) ||31|
(202)
Where x(x) = (6:(x))eEN = (vw)ee(()) for some orthogonal basis (ex)EEN. In fact we can consider:
W1
0
0
W2
= B
(203)
and 2, (c)( (x;))) Then let's consider the following linear regression problem:
ß arg min 1| (B3* 2 +|
(204)
Egen (B) E3
( -
B3
(205)
This problem is identical to the kernel methods in the situation with specific 3-2 = (0o1..... 0na). Although V* and U don't commute with each other, Notice that with y ー, due to the diagonal structure of U:
fi Tra [(OU +CT) (OU +C)-1
(206)
Σ 1 + f10U)) + +1
(207)
7 Σ
(208)
So in fact we find the self-consistent set of equation with Egon (+oo) = Fr:
(wi
< = x
(209)
Dui +
1=1
+ 620
h d
(210)
(ow; + C)2
1=1
This is precisely the results from equation (78) in Loureiro et al. (2021) (see also Bordelon al. (2020)) with the change of variables X(1 V) ( and p + 2m
24

---

Under review as a conference paper at ICLR 2023
D.4 RANDOM FEATURES EXAMPLE
We get the following matrices U, V with j72
12
222 W
_²
[1++00
WWW jOWT
küW
0
12 1
0
0
U=
0
V
(211)
0
0
///
In fact, the matrices U and V do not commute with each other, so we have more involved calculations.
First we consider the subspace F Ker(V - -² Let's define the matrices:
VF 1 p
UF
0
(212)
D2
Upl (0)
=
(213)
Then, although U and V can't be diagonalized in the same basis, they still both block-diagonal matrices in the same direct-sum space Rd = = @ F+, so in fact the following split between the two subspaces F' and Trr holds:
fi Tra (6 (oUn 1,1)
+
(214)
+ Tra [(0Up= + SuSy (oUps + 1-
(215)
+ Tra [(oU + (T f + 1)
(216)
Now let's define K1, K2, Rig such that:
=1 r2 + fi(1 kig ) + o² K3
(217)
That is to say, we get directly /1 = (F2k) + k2)2 and by definition:
r² K1
Tra [[0UF (21) (2 Vo (FUU + +
(218)
Tra [[OU + 1) -00 + 1-
(219)
0Kk Tra [(
(dUpL (,1))
(220)
So we already know that K3 = 1. Let's focus on we can deal with a linear pencil M such that we would get the desired term. First we define similarly AT, the restriction of A on the subspace F:
@WW VIN
Af
Up ApA
(221)
Then, following the structure of M1 construct the following linear linear-pencil M:
I
AF
Bg
AF
M =
GI
Ap
=
B
CCC,
VF
0 0
(222)
A
0
So that:
Sa Vr
B-1
B-1
M-1
0
0
y
(223)
By
where:
B= B--- (='-(1(00)) (ØUF 10UF+CAr (xT)
6(0Up +
AFO(OUF + Gol) (- #
(224)
In the above matrices, the sub-blocks Ap and Vp are implicitly flattened, so in fact M is given completely by:
0
0
AW
00
0
0
0
GTT
DT
0
0
O
aWT
Dl
11
M
I.
O
AW
-P
O
0
(225)
0
C.I
DI
0
WWT
&T
-1T
0
25

---

Under review as a conference paper at ICLR 2023
and therefore, one has to pay attention the quantity of interest which is given by sum of two terms:
N (Zoin) + g000)) v(gg + +og (22)) d
lim
(226)
Using Computee-AAgeera-SSyeeeee we get the equations with Ye Yy, du, By defined such that g
(6 76 6₂ (14 bg Lug(41)
4g (11) (SoSu) (6, SaLu + 1² Vog (33))
(227)
Vi 222 = à (7x7)) (b0 (11) 1=2203)
(228)
g (3)) (GaGo)
(229)
6y = (1 + 7oll vho)
(230)
TV = (226, + 00 Sy + +22--1
(231)
So:
(1 /
= (6x)
(232)
and:
vg " 11)) + vorig (22) = =(1 (1+ 2 (1)
(233)
Hence the result:
+ 2² 12 (g)
(234)
1 μ vi 5
Also there remain to use the last equation regarding So using the fact that:
Su + -Tra (SU + G]
(235)
Notice that have
g (63) -1 -TYN [--11
_ A/AP
(236)
Sy
So because ATA = A:
Suyy = TIN [0AA" A + 1
(237)
TOTTN [(0A" A + C,l @A" A -
A+
(238)
TIN
-AT A
(239)
do (1 Trn [s(OU + +,y))
(240)
du Tra (SU + 1111-11
do 1
(241)
Φo
(Gy + y)
(242)
Therefore:
T'y Cy =
+ y)
(243)
Φ
tho
Ep
26

---

Under review as a conference paper at ICLR 2023
For K2 calculate the following expression -which in fact is general and doesn't 't depend on the specific design of U:
Tra [[OU + - +6
+
(244)
Tra [(OU + +..1) + 121 CUU
(245)
Tra - (
(246)
Tra [U(OU + -111)1
+ (o 'JU(UU + 1111
(247)
6n (U( + (11) - - + (21)-1)
Tra VGU + +1+1)= 2w 5x
(248)
Tra (GUUUUU + -111)---Guli CoU + :col)
(249)
1
(Gy y 22 x.)
(250)
Su C
y σ
(251)
by Se
Hence the general formula:
K2 Su
Cz x
(252)
One can check that the same formula applies for instance for the mismatched ridgeless regression. Also, we assume that it can be replaced by its continuous limit in y + in the situation r =
Finally for f2, we find
fa = co - Tra
+ [ co- -Tra VoV + (21) - Tra [<VvslUU=+ (
(253)
(254)
co- 0² -
lim
ggau + d g(22))
P y
N
(255)
d++00
c0 0² ( )
(256)
where we use associated a slightly different linear- linear-pencil M:
0
I
M
(257)
Lal
AF
Ce VF
0
Af.
from which we get using a Compute-Algebe Algebra--aaarbatyttteee System
( ()oug(22 22
(258)
Another more straightforward way for obtaining the same result without the need for an additional
linear-pencil is to notice that if we let E, (4p OpxN)) such that VF 122 ET. then we have:
Tra [rrVr + -- -Tra [C, Ff (ØUF + -
(259)
TT, [Ef (ØUF -
(260)
Therefore reusing the definition o, and the former linear-pencil M:
Tra ISe (OUF + (a1)="] -² VGang (14) r 65
(261)
Conclusion we have the following equations
fx (- Co Crr )
(22
1 n² ( (5x5g) + +022
(262)
fe(z) Co (r2 222 + 0²)
(263)
8 = (1 + 721 20))
(264)
= (n 02 + 25 -1 SE + -2)
(265)
Ty G = 1 Φ0
1 +
(266)
do
Sy
27

---

Under review as a conference paper at ICLR 2023
D.5 REALISTIC DATASETS
For the realistic datasets, we capture the time evolution for two different datasets: MNIST and Fashion-MNIST. To capture the dynamics over a realistic dataset X E I Ih it is more convenient to use the dual matrices U., V. We only need to estimate U, and E3" with U, = L X and EB L X In both cases, we sill sample a subset of < Thot data-samples for the training set. The scope of the theoretical equations is still subject to the high-dimensional limit assumption, in other words we need n and d "large enough", that is to say 1 < n. At the same time, the approximation of U. and E hints Thor sufficiently large compared to the number of considered samples n. Hence we need also n < Rua.
Numerically, for the two following datasets and as per assumptions 2.1 the theoretical prediction rely on a contour enclosing the spectrum Sp(XT X) of X X, but not enclosing -X. Therefore, in order to proceed with our computations, we take a symmetric rectangle around the x-axis crossing the axis at the particular values - -ेz and 1.2 max Sp(X" X) after a preliminary computation of the spectrum. For the need of our experiments, we commonly discretized the contour and ran a numerical integration over the discretized set of points.
MNIST Dataset: we consider the MNIST dataset with Roo = 70'000 images of size 28 x 28 of numbers between 0 and 9. In our setting, we consider the problem of estimating the parity of the number, that is the vector Y with Y; = if image i represents an even number and Y, = -1 for an odd-number. The dataset X RR "d is further processed by centering each column to its mean, and normalized by the global standard-deviation of X (in other words the standard deviation of X seen as a flattened Rux x d vector) and further by vd (for consistency with the theoretical random matrix Z).
x
The results that obtain are shown in Figure 4 On the figure on the left side we show the theoretical prediction of the training and test error with the minimum least-squares estimator (or alternatively the limiting errors l +00). We make the following observations which in fact relates to the same ones as in Figure 4 in Loureiro et al. (202I):
There is an apparent larger deviation in the test error for smaller n which tends to heal with increasing number of data samples
A bias between the mean observation of the test error and the theoretical prediction emerges around the double-descent peak between n = 100 and n = 1000, in particular, the ex- periments are slightly above the given prediction. We notice that this bias is even more pronounced for smaller values of X.
Although is not visible on the figure, increasing n further tends to create another divergence between the theoretical prediction and the experimental runs- as it is expected with n getting closer to Thot-
Besides the limiting error, we chose to draw the time-evolution of the training and test error around at n = 700 around the double descent on the right side of Figure 4 This time, a gradient descent algorithm is executed for each 10 experimental runs with a constant learning-rate di 0.01. Due to the log-scale of the axis, it is interesting to notice that with such a basic ada-aiipiive learning- each tick on the graph entails 10 times more computational time to update the weights. By contrast, the theoretical curves can be calculated at any point in time much farther away. Overall we see good agreement between the evolution of the experimental runs with the theoretical predictions. However, as it is expected around the double-descent spike, learning-curvee of the experimental runs appear slightly biased and above the theoretical curves.
Fashion-MNIST Dataset: We provide another example with MNIST-Fashion dataset with d 784 and P4mt = 70'000. The dataset X is processed as for the MNIST dataset. We take the output vector for items above the waist, and Y. = -1 otherwise. We provide the results in Figure 7 where the training set is sampled randomly with n elements in nex and the test set is sampled in the remaining examples. As can be seen, the test error is slightly above the prediction for n < 10 but fits well with the predicted values for larger Furthermore, the learning curves through time Figure are different compared to the MNIST dataset in Figure we still observe good match with the theoretical predictions. However the mismatch in the learning curves seems to increase in the specific case when is lower, increasing thereby the effect of the double descent.
Y such that Y;
28

---

Under review as a conference paper at ICLR 2023
175
Lost (PM
1.75
Lzsk 8ie
tho textt (erp)
1.25
1.00
1.00
0190
0.0
0.0
Figure 7: Comparison between the analytical and experimental learning profiles for the minimum least-squares estimator at À 10 on the left (average and 2-standard-deviations over 20 runs) and À 10 2 n 700 on the right.
fram (hh ted seupl tran (eig)
2.2
Figure 8: Comparison between the analytical and experimental learning evolution at À = 10-2, 700 (10
runs).
E
FIXED POINT EQUATION
In general, traces of algebraic expressions of large random matrices can be difficult to compute (See for instance appendix in |Pnniington & Worah (017)). modern approach consists assembling block of large random matrices such that the biock-inversion formula (otherwise called the Schur complement) yields the desired algebraic expression of random matrices in some sub-blocks. Then, using the correlation structure of the sub-blocks of the assembled block-matrix, fixed-point equation can be derived that yields a set of algebraic equations whose solutions provide the traces of the sub-blocks of the inverted block-matrix. This idea initially emerged in Rashidi Far et al. (2006), then has been described further in Mingo & Speicher (2017) andHon et al. (2018) which coined the term "Linear-Pencils"" Since then, has recently been introduced in the machine learning community in more geneal form in Adlam & Pennington (2020a), and also recently in Bodin & Macris (2021) where non-rigorous proof provided using the replica symmetry tool from statistical physics.
Here we propose to generalize even further the fixed-point equation where we let the sub-blocks be potentially of any form, and provide a non-rigorous proof of the proposition following the steps proposed in Bun et al. (2017); Potters & Bouchaud (2020) using Dyson brownian motions and Itô Lemma derive the fixed-point equation.
E. NOTATIONS AND MAIN STATEMENT
Let's consider an invertible self-adjoint complex block matrix M E CN with N = + + such that M (6) is the sub-matrix of size ps X Py. We assume that Pi...., + oo when N + co such that we have the fixed ratios % = lim p:
N and let's define the inverse = M
Now let S
{ijlp: p.}. We define for (ij) S (and defined to 0 outside of this set):
(1)
Tr [
(267)
kk
k=
29

---

Under review as a conference paper at ICLR 2023
We further decompose M the sum of two components M Mo + VN H with Mo and H both self-adjoint, Mo also invertible and where H is a block of random matrices independent of Mo- In particular, Re(H) and Im H) are independent element- wise with each-other, and we leave the possibility that the sub-blocks of Re(H) and Im (H) be either a Wigner random-matee
Wishart random matrix, the adjoint of Wishart random matrix, or (real-)weighted sum of any of the three. ue
(0) within the block ij For the sake of simplicity, we will consider that the elements Re H (5)) Im H Ha
are gaussian and identically distributed although the gaussian assumption can certainly be weakened.
Now let's define k! the covariance between the elements of the sub-matrices H ( and H (kt), that is for (il,jk) E & on the off diagonal position ue on transposed element-locattons:
(kt) = Re (()) Re (ki) - E Imm H Im Hihh))
E
(268)
zj
Also, there can be some covariances on similar locatint-ocations which we define with ō for (ik, E S
E
9 4v
H
( (1 bB
(269)
uu
Re Hi) Re (ki) + E
Im
H 2e
Im
(k)))
(270)
Notice that ot o and ot olk by symmetry, and also when H is real, we always have of = /. So overall the random matrix H has satisfy the following property at any off-diagonal locations (wv). (zy) and blocks (ij, kl):
8ga (jk, il) el) + dga (ik, (1), dop = IE
(63) H
(271)
Finally we define the mapping 7) Cuxn - CaXn:
[n(g)] Σ No
(272)
kIES
then let IIMM Mo 17(9) & I with the notation (n(() D)s n(g))fh, when ij S and
(nr(g) & Dis 0p. xg, the null-matrix when új & S. Similarly as G, with (T(G) I[MM) and with:
g00)
lim IN N
(0)
(273)
Ttp. [360]]
1
Tr c(5))
lim
(274)
700 pi
we state that:
g (0 = Trps [TG])(()]
(275)
Remark 1: When Mo = 2 @ 7 such that Zij 0i & S, then we get (MM = ((g) Ø I,
then - = (Z - n(g)) @ I. Therefore: g (Z ((g)) -1 or re- re- adjusting the terms, we find back the equation from Adlam & Pennington (020aa) Bodin & Macris (2021):
Zg = 4, n(g)
(276)
Remark 2: When considering the linear pencil of a block-matrix M, such this is not necessarily self-adjoint however still invertible, the amplified matrix M can be considered:
M,
M
(277)
M
0
This implies that:
(MZ))
-1
M-1
(278)
M-
0
So g will also be of the form:
0
g-
(60) = ( 0
T(.)T
(279)
((g.))
(i5) = Trp, [[C, - ,7(9-) @ 1)68 and thus, the
So in fact, the same equation still holds with g. self-adjoint constraints can be relaxed.
30

---

Under review as a conference paper at ICLR 2023
E.2
PROOF VIA DYSON BROWNIAN MOTIONS
In order to show the former result, extend the sketch of proof provided in Bun al. (017)): Potters & Bouchaud 2020). First we introduce a time i and a matrix Z E C with M 2)
7. 8 + Mo + VN (t()) with H Dyson brownian motion. Therefore, the matrix that
interested in is actually M = M(1, Owxn). In order for (1) to satisfy the property 271 we must have:
(K0) ( (1) 2y = (dgz (0) vy oi + ōga ( dt
(280)
Itō's lemma provides the stochastic differential equation
aG
aG (5)) OM 0M
dG aGlatt)
(1)) dM (85) $
+E
M aal
d dMM
(281)
sjkl vozy
Using simple algebraic manipulations and the fact that G is analytic in M as a rational function, we can rewrite the above partial derivatives
8G
(a1))
G
G
G
Glag)
(282)
0M
aM
(8
And applying the same formula twice:
aGpo (a3) (5)
Giad) ((ll) G(i))) pa
+ G(ao)
G(ik) ((3)) ((3)) ex
(283)
iM aM
(kl)
gu
og
pm
99
Injecting it in
281
get for p =9
dG pp
Glad) GB3) pa
(284)
op
au
1
Σ
(lakk
(: G153)
+ Glai) G(ik) (lik)) ((L))
Lk dk
(285)
2N
pu
uu
up
up
(ik,i))E8?
ur
1
Σ
Σ
(laak G G(13) G
G(A ((1B)
o
dt
(286)
2N
pm
(il.jk)
So considering dg
(a3) = +/ d
(a3)
Ep
((0B) Gpp
we
dadgi (ao)
66 2N
(119)
Σ Σ
(U00)
1p +[alat) ((11))
(1))
pp 759N
(R)
o de
(sL,k)
(287)
where:
EN
(a.)
ΣΣΣ
(as) pu
GliB) dH we
(6))
(288)
N
1j
+
Σ
ΣΣ P
Glack (lll)) ((i8) + Glaa ((i ((U8) G( pu
Gep
_ dt
(289)
2N2
(ik,)l)ES2
The matrix Z is now helpful upon noticing that (using again the analyticity of G)
aG
-
8M
(a.)
-GG(EE & n - (((() ((383)
G
=
(290)
aZkj
pp
pp
31

---

Under review as a conference paper at ICLR 2023
Hence (using the fact that of
o kil
aG
8G/m0
Ta JadgN
(a0))
EN
(a.)
(1))
159h (5k)
0
o
(291)
2N
ÖZ
iZil
P
(a8)
Ogy (aB)
CNN
(a9)
Ya
2
Σ
NNN
(16)
OgN
ŌZus
Jef
kt
(3k)
84
df
(292)
(AL,)A)E52
OgN
0g
(a8)
EN
(a.)
Ya
2
Σ (n(aN))e Mai
Σ [n(gN)]y
87a
dt
(293)
jREB
Ogin
(a.)
CN
(ad)
Yaa
Σ
[n(
aZyk
dt
(294)
GRE3
As would require more in-depth analysis, we make the following two assumptions:
1. We assume that 9N (a.)
concentrates towards a constant value g ((o8) when - 00
(a8) 2. That EN concentrates towards 0 when N + 20
With these assumptions in mind we obtain the partial differential equation:
0g
0glas)
En(o))
=0
(295)
Ot
aZij
iEES
Finally, using the change of variable
((s) g(((s), (()) g(t 8, Z sn(g(t, Z)))
find:
dg
0g (a di
aas) aZij
(296)
ds
0t
Os
θZij
Ôs
ij
(g(08)
0g(a0)
[n(g(t, 2))]u =
(297)
01
8Zi
So (((0) (8) constant so: (( (-1) = (((0)) (0) which implies:
s00, 7 1n(g(1 Z))) 2)
(298)
Hence for Zt) -1,0nxx) we have:
9(0, ((0,n((((1,0)) = 9(1,0)
(299)
Hence the expected result:
(0) ()(1 1g(0, -n(o(1,0))) Trp [[(Mo - ()(_-)))(11))))))))))))) [((M)=((((),)) 1) (0)
Trp, [(G) (m))
(300)
E.3 EXAMPLES
WIGNER SEMICIRCLE LAW
Let's 's consider n and the symmetric random matrix H R and M H
VN - zl. We find that
((g) 9 and using (276) we find directly
zg 1 g²
(301)
32

---

Under review as a conference paper at ICLR 2023
MARCHENKO PASTUR LAW
Let's consider 2 and the random matrix X Mxd with AV.
21
and
71
N+ 72
N
72
N4d and the random symmetric block matrix:
ZIN
=INN
x vN+a Id
M
N
V
(302)
Id
V'I /N+d
Using Schur complement, it can be seen that UN
(11)
N Tr
(
xTx
=Ix)
}
which is precisely
the trace that is being looked for.
careful analysis shows that 012 22 71
22 while the rest is null and thus [n(())
g
"1
a (22) and [m(]]222 ( With (276) we obtain the system of algebraic equations
(1)) + 1 120) g("l)
(303)
9 22) 1 (11) g g222)
(11))
(304)
Therefore, injecting the solution of the second equation g(22)
14g in the first equation
(2g = 1 1 ((1))
(305)
g(1l)
Hence the Marcheko Pastur result:
2 + (x+1 - ④
g (())) -1
(306)
33


Reviews:
[{"review_id": "jlEMGbNCED", "reviewer": "Reviewer_utMN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies gradient descent for linear regression under the high dimensional framework. Under certain conditions, the authors study the generalization error in such gradient descent, and show that there exists multiple descent in the generalization error of the linear model during training. The authors also conduct experiments on the random feature models and realistic data sets.", "summary_of_the_review": "In summary, this paper gives solid and interesting results. However, as discussed above, several parts of the paper can still be improved.", "strength_and_weaknesses": "Strengths:\n\n1.  Multiple descent and learning in high dimensions is an important and interesting topic. This paper proposes some timely and interesting results.\n\n2. The paper provides rigorous proof of the generalization error in the gradient descent flow, and also provides some simulations and experiments.\n\nWeaknesses: \n\nMy major concern is that there seem to be some confusing/vague statements. Below are some examples: \n\n1. Given existing analyses on double/multiple descent in linear models and the regularization effect of early stopping, the technical contribution of the paper may be limited. \n\n2. Recently, there are some papers related to multiple descent (arXiv:2204.10425, arXiv:2205.14846, arXiv:2208.09897). The connection between this paper and existing works is not discussed very thoroughly.\n\n3. The theory applies to the high dimensional setting, so setting $p=3$ in the experiments may not be very reasonable. The authors should provide simulation results with larger $p$.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "exXSXBk1gnn", "reviewer": "Reviewer_amF8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study the evolution under gradient flow of the training and test errors in the setting of Gaussian covariate models, which encompasses several other well studied settings. Using tools from random matrix theory, in particular the linear pencil, they calculate the exact asymptotic behavior of several quantities in the high-dimensional limit. The authors show how multiple descent phenomena can arise as a function of both number of parameters and training time. The paper also includes results on real datasets and shows good agreement between simulations and theoretical predictions.", "summary_of_the_review": "The paper contains nice results that unify and extend previous work. The paper's main claims are supported by proofs and illustrative experiments. Overall the paper is clearly written and covers a lot of material. ", "strength_and_weaknesses": "**Strengths**\n\n- The setting of Gaussian covariates is nice and generalizes many other models.\n- Early stopping is important in practice. This theory gives some results on how to choose the stopping to avoid multiple-descent peaks.\n- The analysis connecting the peaks in Fig 2 to the spectrum in Fig 3 is nice.\n- The use of Dyson’s Brownian motion to derive the self-consistent equation (276) is cool.\n\n\n**Weaknesses**\n\n- No significant new machine learning implications from the results are derived in the paper. This might limit the paper’s interest to the wider ICLR community.\n- I couldn’t find any details of how numerical predictions are generated from the equations of Result 2.1. In particular, how are the contour integrals calculated? Which contour is used? How do you avoid spurious solutions to the self-consistent equation?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "_y1xVE5gzt", "reviewer": "Reviewer_FVzp", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This submission computes the asymptotic training and test error of linear estimators optimized by gradient flow on the least squares objective, under the student-teacher setting with Gaussian covariates studied in [Loureiro et al. 2021]. The analysis generalizes the earlier linear pencil calculation for random features model in [Bodin and Macris 2021], and recovers the performance of the ridge regression estimator when the time $t$ is large. The authors present a few examples of solvable models, and also demonstrate empirically that the Gaussian covariate predictions can be accurate for certain real-world datasets. ", "summary_of_the_review": "My current evaluation is that this is a borderline submission: I believe the random matrix analysis is a solid contribution, but the authors need to thoroughly discuss prior works and present the results in a more accessible way for the ICLR community. I will consider updating my score if the authors can adequately address the above concerns.", "strength_and_weaknesses": "## Strength\n\nThe studied problem is well motivated: most existing works on the precise asymptotics of training/test error only consider the empirical risk minimizer (instead of the entire gradient flow trajectory), and the time-evolution of the error reveals some interesting phenomena such as epoch-wise double descent. While the results are only derived for Gaussian features, we may expect wider applicability due to the Gaussian equivalence (universality) property. Moreover, the linear pencil construction and the Dyson Brownian motion derivation of the self-consistent equations could be useful in future random matrix-related research. \n\n## Weaknesses\n\nMy main concern is that many relevant prior results are not discussed.  \n\n- Asymptotics of the least squares estimator in Section 3.2 (anisotropic features, isotropic teacher coefficients) was first rigorously studied in [Dobriban and Wager 2018]. This result was then extended to general teacher models using the Stieltjes transform approach in [Wu and Xu 2020] [Richards et al. 2020], where the authors already showed that the multiple descent risk curve can be engineered using eigenvalues of different scales. Also note that the self-consistent equations in these works are identical to the infinite time-limit in this submission. \n\n- The discussion of the Gaussian equivalence principle in Section 3.3 is insufficient and non-rigorous. The cited [Peche 2019] only implies the (weak) equivalence in the kernel spectrum, which does not guarantee the equivalence in the training and test error. The authors should look into [Hu and Lu 2020] and references therein. \n\n- Asymptotics of the gradient flow dynamics can also be analyzed using alternative approaches such as dynamical mean-field theory. In this submission, the squared loss gives a closed-form expression of the trajectory which simplifies the computation, but it would still be nice to briefly discuss and compare these different method. \n\nDobriban and Wager 2018. High-dimensional asymptotics of prediction: ridge regression and classification.  \nWu and Xu 2020. On the optimal weighted $\\ell_2$ regularization in overparameterized linear regression.  \nRichards et al. 2020. Asymptotics of ridge (less) regression under general source condition.  \nHu and Lu 2020. Universality laws for high-dimensional learning with random features. \n\nIn addition, it is not entirely clear of how ML theory researchers can benefit from knowing these asymptotic formulae. Currently, the application seems to be limited to plotting good-looking risk curves; this does not provide quantitative characterization of the reported phenomena. For example, to rigorously establish epoch-wise double descent, the authors need to check the time derivative of the error to show non-monotonicity. Such analysis would strengthen the theoretical contribution of this submission. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "SCeBWj5joQ", "reviewer": "Reviewer_RBfi", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper looks at the regularized linear regression where the data is generated using a Gaussian Covariate model and the regression targets are linear functions of the data. the paper starts by showing the that the setting is fairly general and captures many other set ups. In this set up, under some assumptions the paper then obtains a formula (albeit a complicated one) for the training and test error as time evolves. \n\nThen they specialize to specific instances and re-discover known results from prior work. \n\n", "summary_of_the_review": "In summary the paper is a nice theoretical contribution however, the insights that can be readily obtained seem lacking. I think significant work would be required to simply the formulas or some work should be done to help understand the formulas (at heuristically) would go a long way to improving the paper. ", "strength_and_weaknesses": "**Strengths**\n---\n\n1) The set up is fairly general and captures many existing models that have been analyzed. \n2) The method provides the whole training curve and not just the limiting distribution. \n3) The paper re-captures known results/\n4) The idea of evolutions of the eigenvalues and the ``bulk'' in section 3.2 is interesting. \n\n**Weaknesses**\n---\n\n1) I think the results are very hard to parse specially Result 2.1 and result 2.4. Further in result 2.1 the terms depend on equations $\\tilde{f}$ which is very complicated term which itself terms on equation (8) which is a complicated implicit equation (both sides depend on the quantity). Hence while the formulas might be true, it is not clear how informative they are. **That is, do they actually tell us much more than $\\beta^\\lambda = (\\hat{X}^T\\hat{X} + \\lambda I )^{−1} \\hat{X}^T Y$ and then just writing down the test error.**\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject