4+3 Phases of Compute-Optimal Neural Scaling Laws
Authors: Elliot Paquette
Courtney Paquette
Lechao Xiao
Jeffrey Pennington
Venue: NeurIPS 2024 spotlight (2024)
Keywords: scaling laws
compute-optimal curves
high-dimensional probability/statistics
random matrix theory
stochastic optimization
Primary area: learning_theory

Abstract: We consider the solvable neural scaling model with three parameters: data complexity, target complexity, and model-parameter-count. We use this neural scaling model to derive new predictions about the compute-limited, infinite-data scaling law regime.  To train the neural scaling model, we run one-pass stochastic gradient descent on a mean-squared loss.  We derive a representation of the loss curves which holds over all iteration counts and improves in accuracy as the model parameter count grows.  We then analyze the compute-optimal model-parameter-count, and identify 4 phases (+3 subphases) in the data-complexity/target-complexity phase-plane.  The phase boundaries are determined by the relative importance of model capacity, optimizer noise, and embedding of the features. We furthermore derive, with mathematical proof and extensive numerical evidence, the scaling-law exponents in all of these phases, in particular computing the optimal model-parameter-count as a function of floating point operation budget. We include a colab notebook https://tinyurl.com/2saj6bkj, nanoChinchilla, that reproduces some key results of the paper.

4+3 Phases of Compute-Optimal Neural Scaling Laws
Elliot Paquette' McGill University
Courtney Paquette Google DeepMind & McGill University courtney paquette@mcgill. ca
elliot. www.:ppuuuueeeenggll.ccc
Lechao Xiao
Jeffire Pennington Google DeepMind
Google DeepMind
Abstract
We consider the solvable neural scaling model with three parameters: data com- plexity, target complexity, and model-parameterrcomm We use this neural scaling model to derive new predictions about the compute-limited infinite-data scaling law regime. To train the neural scaling model, descent on a mean-squared loss. We derive a representation of the loss curves which holds over all iteration counts and improves accuracy as the model param- eter count grows. We then analyze the compute-optimal moodel-parameter-cmme and identify 4 phases (+3 subphases) in the httee--oommeeiittttttttoooom phase-plane. The phase boundaries are determined by the relative importance model capacity, optimizer noise, and embedding of the features. We furthermore derive, with mathematical proof and extensive numerical evidence, the scaling- law exponents in all of these phases, in particular computing the optimal model- parameter-coun as a function of floating point operation budget. We include a colab notebook nanoChinchilla? that reproduces some key results the paper.
one-pass stochastic gradient
Introduction
The advent of large language models (LLMs) has changed our perceptions of the landscape of optimization and is resulting the emergence new interesting questions related to scaling. Prior to LLMs and other large models, we often viewed the large-scale optimization problems as being limited by the amount of data. training language models, in contrast, data can be effectively infinite. Thus, compute budgets can be the limitation. This leads to the following natural question: given an architecture, given fixed compute budget, and having unlimited data, how should one select the model size to minimize loss?
To formally address this question, let us consider the general learning problem,
min { (0) = (((:x))) where Rdd IR
BER
the number of parameters d is large, and the data vector is drawn from unknown distribution. We solve (1) using stochastic algorithms, such as stochastic gradient descent (SGD) with batch size B. under various parameter sizes d, that produce sequence of iterates {0r). A standard formula used in practice to measure compute is the "6ND" formula [26), that is,
Compute (flops"f) (iterations of alg. (r) batch size (B)) parameters (d).
(2)
Coorreponniigg author; website: https://elliottaqquetts git.ub.ithh..o.. io/.
The authors contributed equally to the paper.
Availlble at: https: http://tinyuulloo//ssssse/e
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Therefore, we can plot the loss curve (0,; = (r; (f/(d- d):d) as function of flops (see Fig. 1). The question now is: given a fixed number of flops f and given batch size B. how should we choose the parameters d so that we get the best loss, i.e. find dt solving the constrained problem
d' (f) E arg m
3 (d'gid) = arg min, (0,;; d) subj. to f f= (r x B) x d}.
(3)
Main contributions. In this work, we analyze a three parameter simple model, which we call power- law random features (PLRF) [30, 5]. The three pa- rameters in the PLRF are the data complexity (a)) target complexity (3) and Using this model, we derive a deterministic equiva- lent for the expected loss, as a fuucciion of a, 3, and d, that captures the training dynamics of one-pass SGD. This can be used to derive numerical predictions for the scaling laws. We also extract exact expressions for the compute-optinat scaling laws and the optimal parameter d' (f) E argmin, P (2.1g d) for large" d, and give some estimates on the order of necessary for these scaling laws to take hold.
alpha =0.4, beta =0.4
1,600
3,200
10a
6,400
count d.
12,800
loss, P(flops)
25,600
51,200
compute optimal
Fised compute
10
10
10"
10a
1043 1044
flops
Figure 1: Toy scaling problem. We plot the loss function, (0,; d) as a function of flops using (2). Consider fixed number of flops = 10" (dashed line). If we had chosen, e.g.. d = 1600, we can run for a long time, but our model does not have lot of capacity and thus the value of the loss function remains high. On the hand, we can increase capac- ity by choosing a large number of parameters (e.g., d= 51, 200), but because our compute is fixed long. Thus the loss value is still large. The optimal choice is d Rs 6, 400. When done for every choice of f gives the compute-optimal curve (red line). This choice of (a, (Phase I) is an example of where model capacity con- trols the compute-optimal curve, but it is not the only behavior we show. In other phases the compute-optimal is controlled by poor model embedding (Phase II, III) and SGD noise (Phase III. IV).
We also observe for large portion of the (a,, 3)- phase plane, the optimal parameter is (f) f2/2, suggesting regime of universal scaling behavior
(see Fig. 4a and Table 2). This verifies theoretically the Chinchilla scaling [24].
The PLRF is not only analyzable, but also exhibits a rich behavior of compute-optimal curves/loss curves, which qualitatively and quantitatively different depending on the strengths of the data (a) vs. target (3) complexity. Particularly, we show that there are 4 distinct (+3 sub phases) compute-optimal curve/loss curve behaviors.
not
algorithm for very
Model constrained compute-optimad curves. In two of the phases (Phase Ia,b,c and Phase II), it is the under- lying model that dictates the curves. The algorithm has little/no impact. This appears in two forms. The first behavior are compute-optimal curves controlled by the capacity of the model (Phase la,b,)). Here once the algorithm reaches the limiting risk value possible (capacity), it is better increase the model-parameter d. Another type of loss dynamics is due to poor model feature embedding (Phase II). Here the features are embedded in a way which is difficult to train. After an initial large decrease the loss value, this feature embedding distortion frustrates the algorithm and training slows, but it continues to solve. However, solving to capacity wastes compute, in that it is compute-favoree to increase the model parameter count d.
Algorithum constrained the noise produced by the SGD algorithm that ultimately controls the tradeoff. Here the algorithm matters. Indeed, another algorithm could change the compute-optimal curves for these phases.
curves. For some choices of (a., B) (Phase III and IV), it is
Related work. The key source of inspiration for this work are [24, 26]. which identified compute optimality as a fundamental concept in scaling large language models and made a substantial empirical exploration of it. The problem setup was formulated by [30], where additionally data-limited scalings were considered, but compute optimality was not (nor indeed any algorithmic considerations); see also [8] where gradient flow is considered in the same setting.
* 'Here and throughout we flops to mean "floating point operations" and not the rate floating point operations per second. We also drop the prctfr in "6ND" formula for simplicity. 'e discuss how large is large, but the truth is somewhat complicated and also quite dependent on the desired precision. If +.005 on the achieved scaling laws is tolerable, flat d > 1000 seems suftice across all phases.

---

Phase la, lb, Ic
Phase II
Phase III
compute
compute optimal
compute optimal
optimal
loss curve
F yp
loss curve
F pp
loss curve
Kpp
Fac
Fac
F
Fo
Fo
flops
flops
flops
Phase IVb
Phase IVa
compute
compute optimal
optimal
pentuple point
m
loss curve
T yp
loss curve
F ppp
high-dim. line
IVa
v2
Kpp
Kpp
0.25
1c
Fo
Fo
Vh
3
flops
flops
(a) Phase Diagram
Figure Phase Diagram and Cartoon Plots of Loss Curves in Different Phases. (a) Phase
Diagram. Colored regions represent where the training of the risk/compute-optimal curves look qualitatively and quantitatively different depending on a and B. This, in term, yields different scaling law (1)) and parameter count (ς) exponents for each of the phases. Critical point at 3 1/2 where all behaviors are observed. The other plots illustrate the components
(via Fo, Fpp Jac) and Xpp which dominate the loss curve for each phase (see Sec. C.4.1 & Sec. C.4.1 for proofs); tradeoff between the functions where the compute-optimg point occurs also indicated (see Sec. 2.1 for definitions and Sec. 3.1 & Sec. D for proofs).
There is substantial body of work considering scaling laws of losses (trained to minimum-loss) of dataset size vs parameter count, in a variety of settings (linear, random features, deep networks). See especially: [5, 39, 41], wherein that as we consider one-pass SGD, some cataset/parameter-coo scaling laws are implicit from the results here; however, the training method (one-pass SGD) is, in some regimes, suboptimal given unlimited compute.
model is considered for the data. We note
For additional related work on random features models (and sample complexity), random matrix theory machine learning. and other deterministic equivalents for SGD, see Section A. We note that while this paper is fundamentally about computation, but the novel mathematical contributions could also be recast terms of generalization bounds of one-pass SGD, some of which are new. For detailed comparison of the convergence rates and sample complexity, see Table 4.
1.1 Problem Setup: SGD on Power-law Random Features
In this work, we analyze the three parameter power-law random features (PLRF) model, that is,
(0) def E., E.(((TTT x. (x, (11)))
min OER
(4)
We embed the data vector x E R in d through the matrix W E Rud and construct noiseless targets" by dotting a fixed b R" with the sample The use of the matrix W allows the model to have variable capacity (d) independent of the data set size. The samples x E RR" and labels b E IR" have power law dependence, whereas the matrix W has entries distributed as N (0, 1/d).
'Wit label noise, the scaling laws are the same we report here, to scale at which the label noise is the limiting factor in the optimization and further increase of compute budgete-budgett or d does not yield any benefits.

---

tur Mele Dhip
Vilrs
Lan Frelo
15
Papux
(c) Optimal Model Size
(a) Compute-optimal Front
(b) IsoFLOP
Figure 3: Compute-Optimal Front in Phase II-III boundary. (a) The Volterra equations perfectly
captures the training dynamics of SGD when model-parameter count ranges from = 200 - 12800.
(b) We apply IsoFLOP approach [24] to our toy model to extract the optimal-compute front: (compute- optimal loss) (highlighted in red (a)) and the optimal model size: (compute-optimal model size) (scattered in purple in (c)). Power-law fitting compute-optinal front gives measurement of the scaling law exponent 0.648 (vs. theoretical prediction 0.643 in Table 2). In (c), we power-law the relation between compute and (empirical) optimal model size via Approach I and used in [24]: d x 40.00s and d= x f0.525 resp. (vs. theory, d' x fo.s). See Sec. J for details.
Assumption 1 (Data and labels, a and 3). The samples x E I= are distributed according to (xz) =j j-"22 2 for all 1 S j S v and {2y}5=1 NO, 1). The labels are scalars constructed by dotting the sample x with a signal b E R2 whose entries (b;)=
Without the random matrix W. the 8 B are related to what is known in the literature as source and capacity conditions [10, 11, 20, 36]. For a detailed comparison of the parameters and related work, see Section A and Table 3.
The dimensions we consider throughout are always such that Cd for C' > Throughout both and d need to be large, but for some choices of a and B, the v will need to be comparable to d.
Definition 1.1 (Admissible and d). We assume that v 2 Cd with C >> 1 and v, d co. Above the high--dimensionl line, which is when 2a > 1, we suppose v/d + r (1, oc) U [oo). On the other hand, below the sigh-dimensiona line (2xx < 1) we limit be v/d d r E (1,
One can rewrite the expression in (4) using the convenient form:
(0) = (D(WO b), (We 6)}}- where = diag(j- 20) E Rexe DER
min
(5)
Algorithmic set-up. To solve the minimization problem in (5), one-pass SGD with mini- batches of size B (independent of d'' and constant learning rate y > O: letting 0g = 0, we iterate
drawing { fresh iid samples and 0,+1 0, W (W x4, (zt bi}
(6)
The learning rate and batch size will need to satisfy condition ensure convergence (Prop. 2.1).
Main goal. Under this setup, our main goal is to characterize the compute-optimal frontier. Pre- cisely, we want to find the parameter count exponent & and scaling law exponent 7, such that,
d' (f) = and
D d" x =
Notation.
We use (0,)) = (r) when we want to emphasize the iteration counter r. We say of vr,v,d) A(r, v, d) for functions (r, d), A(r, d,d) > 0 if for every E 0 and for all admissible u and d, there exists an ro, do such that for all > do and r 2 to
(1-e)A(r, v d) S a (r, < (1 + (,,
"n fact, we may take y oo for 2a 'Indeed one can, the former case, take d S 2111220) but for simplicity of presentation focus the proportional regime when 2a < 1.
"One can study batch size B growing with d, but for simplicity we let B = 1. Thus we only consider B independent of d setting.

---

Table
Large d behavior of the foreing function and kernel function. See Sec. H for proofs.
Function
*T()) is the Gamma function
Fo(r) d 2n max (8))
5 Fpp(r) (2a) x 11
2n + 1) x (2yB x (2) (1+5/)))114)))))/////
(14.//)4112/)
x Fo(r),
2 > 1, 2ax <1
Fac(r) - 10
for C > 0, independent of
2 <
2 1, 1, F om
ンド=1 j (2a) (2a) 2
d-1
ppp(r) (2x)) x ( 1 (2 B 22-1/22))))
We write x the upper and lower bounds hold with some constants c, place of I F respectively and S. 2 if only one inequality holds.
2 Learning Dynamics of SGD
Compute-optimal curves (3) for the random features model (4) rely on accurate predictions for the learning trajectory of SGD. Similar to the works of [33, 35], we show that the expected loss under SGD satisfies convolution-type Volterra equation (for background on Volterra equations, see Section C.3)
forcing fune.
r- Σ 1 s))ss) (7)
E (0,) W]
X E (0,) where (X+ f)())
grad.
noise
The forcing function (r) and kernel function X(rr are explicit functions of the matrix K D1/2WWT D1/2, where Diag(j -22a, S S v), and T C contour enclosing the spectrum of k E [0,
F(r) def
"0) 2 de -k) 21 B2 27 1)=?)" dz)
$
2Ti J
(8)
and (() del -1 Tr (K
(R==)))
2Ti
Intuitively, the forcing function is gradient descent on the random features model and the kernel function is the excess risk due to 1 unit of SGD noise.
Deterministic equivalent. The forcing function F(r) and kernel function (xr are random functions depending on the random matrix K. Indeed, it is the resolvent of K. (K z)-1, which plays a significant role in & and X. We remove this randomness from the expression by using deterministic equivalent - a technique from random matrix theory.
Formally, we define the deterministic equivalent for the resolvent of K, denoted by R(2), implicitly via fixed point equation
where R(z) = Diag ( 220m22) :15550). (9)
m(2)
1 1 Σ.
Lj=1 m())=
This deterministic equivalent R(2) is viewed, roughly, as Ew Ewl(K [[K 2 = R(z); though it is not formally the expectation over W. By replacing the resolvent of K with R(z), there exists
5

---

1.0
Parura Exponant (Thaer))
Parára Equaent (thenchils azaraach
42
BL Expenent (Thece)
Parama Eqonent (Chinoilic apassach
<>
Meesurement
Exponents
0.6
0.4
la
61
0.2
0.6
1.0
B
(a) Scaling Law Exponent
(b) Empirical vs Theory (a = 0.7)
Figure 4: (a) Scaling Law Exponents. The heatmap displays scaling law exponents (r)) in the (a. pl-pne Hatched lines represent region with universal scaling behavior, d x f0.5, independent of (a, 3). (b) Exponent Measurements. Compare empirical exponents (following [24]; see Sec.J for details) to theoretical predictions, traversing the phase diagram horizontally at a 0.7 from Phases la- + - III as f
deterministic function P(r) which solves a convolution Volterra equation, matching (7):
forcing Func.
P(r) = F(r)
+ (K (P)
(10)
descent
SGD noise
where F(r) 2 f (()(2) (2)))))))))))))))))))))))))))))) (1112))) 22 B 1)= de
-1
(11)
and K(r) def 2 Tr
-1 2 J. 2,,))
dz)
(12)
The solution to the Volterra equation with deterministic equivalent (10) numerically exactly matches the training dynamics of SGD, see Fig. 3. A discussion of the deterministic equivalent for (K =)- can be found in Sec. All our mathematical analysis will for the deterministic equivalents, going forward. 10 The derivation of the Volterra equation for the expected loss can be found in Sec. B.
An immediate consequence of (10) that for convolution Volterra equations bounded solutions occur if and only if the forcing function is bounded and the kernel norm ||C]| def E K(s) < 1. This directly translates into sufficient condition on the batch size and learning rate of SGD.
Proposition 2.1 (Sufficient conditions on learning rate and batch). Suppose learning rate 7 and batch B satisfy ||]|| < and yB + 1) < 2. Then P(r) is bounded.
Remark 2.1. Below the line 2a 1, the kernel norm diverges with for fixed constant ", and must take 7 - 0 to ensure bounded solutions. Thus, provided 2 then
|
20
1-20
is order I.
2(1 (12)
Thus, the kernel norm, ||]]], is always constant order for all a.
The batch B and 7 can depend on d. For simplicity, we only consider B order I in this work. For proof of the necessary and sufficient conditions on y and B, see Prop. C.2, and see Cot. G.I for the asymptotic on ||]]]]
The Volterra equation in (10) can be analyzed to give more explicit formula for P (see Section C.3.2 for proof).
Theer good numerical evidence that the deterministic equivalent captures interesting features of the PLRE There is vast random matrix theory literature on making precise comparisons between resolvents and their deterministic equivalents. It seems a custom analysis will be needed for this problem, given the relatively high precision required, and do not attempt resolve this mathematically here.

---

84
69
ad13
Data oxp
Step
Dum. (4)
Figure 5: Finite-size effects. (a) The ratio of the exact solution of eq. (10) to the estimate in eq. (17) bounded by constants for all r. confirming the validity of eq. (17): shown here is (a, 3) = (0.7, (b) For non-asymptotic d, the estimate in eq. (17) (solid curves) predicts both the magnitudes and trends of the measured exponents of the empirical compute-optimal frontier (points), shown here for (a, () (0.7, 1.2) computed using Approach O (see Appendix J) to capture the instantancous slope; the dashed lines show the asymptotic exponents from Table (c) The finite-size behavior relaxes to the asymptotic predictions over horizons whose length can grow exceedingly large, especially in the vicinity of the phase transition, shown here for B 0.7 approaching the Phase 4a->4b boundary.
Theorem 2.1 (Approximation solution for P). Suppose " and B are most half the convergence 4. 1.11 There exists an M >> O large and a constant C C(o, B, M). independent of so that for all admissible and d. for all Br M,
threshold and 2a - 2B > 1, a >
F(r) + (K+ s P(r) s 3(r) + C F)))..
(13)
The convolution K * F further simplifies
forcing fune.
kernel func.
ē (F(r) + BB
X(r)) S (X s 5Ōx F(r)
K(r) SGD noise
(14)
B
grod. descent
for some constants ē= ö( 3, M) and Č = C B, M) > 0 independent of d.
Remark 2.2. we were to run gradient descent instead of SGD (i.e., Y small), then we would only have the forcing term, that is, P(r) F(r). The measurable effect of SGD comes from the second term that contains the kernel function. For this reason, we refer to SGD noise as 7B K(r)..
In light of (13) and (14), we have trapped the training loss between the sum of IF and K, so it suffices now to understand the forcing and kernel functions.
2.1 Forcing function and kernel function
We decompose the forcing function (11), F, and the kernel function, (12), K, into
F(r) = Fo(r) + (rc + Jpp (r) + errorsy (r) and K(r) = Kpp (r) + errorsy (r).
(15)
Each term is explicit and has an asymptotic equivalence (when 1 Br S a given by Fr(r, d),Kpp (r, d) ~ x r* x d for some constants e, T, 0 (see Table 1).
(16)
The two error terms are such that for large d with 2 Br & d lerrors (r)l < C x (r)(r) + (r) + F (r)) and |errors & C x (r),,,
for some constant C' > 0. For > Br Z dza the forcing function F(r) Fo(r), the limiting risk value. The terms arise from different parts of the spectrum of the deterministic equivalent for K (see Fig. 6).
1. Point mass at 0: (0) Fr( is the limiting value of PP() x d 2mxx as + It occurs because the loss is irreducible (d < v), that is a component the target is not in the image of the RF model (or cquivalently that Æ has kernel).
"In spite of Theorem 2.1 holding only for 1. expect this hold for all 2a 2/3 as supported numerically. When a < 1. the kernel function stops being power law and, as result, requires different set of tools to prove the result.
7

---

2. Aligned features: The function ppp (r) represents gradient descent on the components of features which are aligned to the underlying population features. Indeed, if we ran gradient descent on the population loss without a random features map (or a diagonal W), this would be the loss curve.
3. Distorted features: The function (r) is the result of feature distortion, where the matrix W leads to an embedding where a small component of the leading features is distributed across many different eigenmodes. These are still solvable, and given enough compute these will eventually be used, but they are much slower to solve.
Aligned kernel: (r) the excess risk due to 1 unit of SGD noise, which is then solved according to population gradient descent.
Out of brevity, we relegate the exact definitions of Fo. 3 Fpp. Facs and Kpp and all proofs of the asymptotics in Table and analyses of the functions to Section F, G, and H.
3 The 4 Phases
We now put together a coherent picture of the effect of different choices of a (data complexity) and (target complexity) and their impact on the compute-optimal frontier. By Theorem 2.1, we estimate
P(r, d) x 3 (r) + Fac (r) + Fo(r) + 1 K2pppi
7 pp(r).
(17)
Explicitly, show that the functional form, or scaling law for the PLRF model is
P(r, d) x
where oi, T3 >> 0 and explicit, see Table 1. (18)
(rp(r)
Fo(r)
Fuc(r)
B (r)(r)
Fig. 5a. shows empirically that this equivalence of ((()) is quite good. The first two terms 3 (r) (i.c., r r1) and To(() (i.c., ") are often called in the literature as time and model bottlenecks respectively. The functional form using only these two components, i.e., P(r, d) x r- + d were used to find compute-optimal exponents in [24, 9] and in concurrett work [28]. Because the functional form considered in [9, 28] are missing the two other terms (cross-term Fac and SGD noise Kpp), the compute-optimal curves in [9, 28] agree only in Phase la with our results. Importantly, we show that the cross-term, i.e., (r), and SGD noise, prp (r), can indeed affect the compute-optimal exponents. (The cross-term also appeared in concurrent work on ridge regression [18].)
The distinct phases (see Fig. 2a) decompose the (a, -plane based on the shape of the loss curve P(r), that is, which of the distinct components of the forcing function (i.e., To.T pp. T (aes) and/or kernel function (i.e., Kpp) dominate the loss curve at a given iteration r. See Table 2 for loss description in each phase. Cartoon pictures of the different features of the loss curves are shown in Fig. 2. For each phase, we derive a compute-optima curve in Section 3.1.
The high-dimg high-dimensional line, which occurs where 2a = 1, distinguishes the phases where the e- dimension can be big and independent of d (Phase Ia, II, III, 2ox 1) and the phases where d and must be related to each other (Phase lb, Ic, IVa, IVb, 2o < 1). When 2a - 23 < 1, the loss does not (purely
exhibit any power-law decay the limit level stops going 0 as d of having selected the regime > d). Moreover, there exists an interesting critical point = 3 = 1 where all the parts of the forcing function and kernel mix and interact with each other. The behavior of the loss at the pentuple point (see Fig 2a) we leave for future research. Across each of the phase boundaries the compute-optingg curves are continuous, but not necessarily differentiable; in contrast, d' is discontinuous across some phase boundaries.
consequence
3.1 Compute-optimal Curves
To simplify the computations for compute-optimal curves, we introduce the following curve
p(r)
def max (r.) (,, (r))
(19)
The function P(r, d) achieves the same power law behavior as the original compute-optimal curve P(r, d) (i.e., the slope of the compute-optimal curve is correct) and deviates from the true curve by an absolute constant (independent of d and f). Note that some of the terms in the max function
8

---

Table 2: Loss description for P(r) and compute-optimal curves for Pl a.B. d) across the 4 phases.
Loss P(r)
Trade off
Compute-optimall Curves
- (1)011100-11/20))
fo- Phase la (f) 2041
dhase x fl (1/(2++1)
Ib
P Phase lb (f) x --
Phase I
ppp(r) Fo(r)
Tpp Fo
Phasse lb x f
a(2a+28-11
Po. Phase lc (f)
fa 3122--3)-29+ 2941
1-2(a+9)
denase 1o
2(aa(2p33)
20+22-1
Phase II
Frp(r) Tac(r) +ro(r)
Fpp Foe
Jo+
Phase 11 (f) x 2(a+3)
dpnase 1I x (1/0)/(1--//)
Fac(r)+ Fo(r))
Jo+ Phase II (f) x ((1-aa)/(1a)
Phase III
1 Fac
1 (pp((r)
dennce III x fl/2
Pr. Phase IVa (f) x f-a
IVa
Kpp 50
dphase IVa x f2/2
T (r)(r) Fo(r) (pp(r)
Phase IV
11-20
Pr
Phuse IVb ( x (21268 201)
IVb
BB Kpp
F
dphase IVb x ( ()/(2a
(19) should be taken to be O when not defined for the different phases. Therefore, we derive the compute-optimal curves by solving the problem
min P ((.f..d) d), and if d' (f) def
arg min, P f d),
d.
(20)
jo* (f) del q (ZT) d (f)).
then the compute-optimal curve is
See Table for the exact expressions for d' (f) and the compute-optingg curve JP* (f) for each phase. more detailed description with proofs can be found in Section C.4 and Section D.
Now to derive d' and . we recall that the functions Fo, pp: FacsKKp take the form e x d= ( (16). Therefore, 5 (f/(d" - B), d must occur at corner point where two functions meet. These tradeoff's between the functions for which the compute-optimal point occurs are shown in Fig. 2 and Table 2.
Details for each phase. We describe the qualitative and quantitative properties of compute-optimal curves for each phase. These are broken down into model constrained (Phase II) vs. algorithm constrained (Phase III, IV), i.e., whether the PLRF model or SGD is the constraining feature.
Phase Ia, lb, Ic. Capacity constrained. Phase (2a 1,23 1). Ib (2a 1,28 2(a
3) >> 1), Ic are characterized by having the simplest loss description, P(r) x FF pp) + (r)).. Here the SGD noise is irrelevant and one would have the same loss (and thus compute-optimal curve) as gradient descent on the population loss. Compute optimality is characterized by training the model completely (to its limit loss) and choosing the model parameter count large enough so that at the end of training, the smallest loss is attained. The main distinctions between Phase Ia. Ib, Ic are the model capacities (i.c., Fo (r, d) = 2a+11-2 229 Ia, Ib, and Fo d) da Ic) and the dependence of dimension in the learning rate due to Ib,Ic being below the high- tigh-dimensional line. Consequently, while the qualitative features of the loss curve are the same for la, Ib, and Ic, the actual values of the compute-optimal curve vary across the different regions. Notably, in Phase Ib, the compute-optimal parameter is d' f1/2 and it is independent of and B.

---

> 1, < a) has a loss curve where the Fae is important, that is, P(r) x 3 (r) + F Fac(r) (r)r.. The F term becomes the dominant term after running for some intermediate amount of time d in fact it is compute-optina to stop at this point, and then select the number of model parameters so to mínimize the loss with this early stopping criterion. It transpires that across all phases, it never pays to solve through the F the loss curve it is always better to just increase the number of model parameters.
Phase II. Distortion constrained. Phase II (2a > 1. 23..311100
ac part of
Phase III. SGD frustrated, distortion constrained. In this phase (2a > 1,23 > 1,3 1,3>00 a), SGD noise is important. The loss curve is P(r) x Fac(r) Folr) + "B (p) Notably, in this phase, the compute-optinal parameter is d' (f) fA/2, which is independent of a and B. PLRF that fall within this phase have the same scaling law regardless of data complexity and target complexity. Moreover, the tradeoff occurs, like in Phase II, once the optimizer reaches the F -om-innndtedd part of the loss curve. Unlike in Phase II, the optimization is slowed by SGD noise (Xpp) leading up to that point. We note that there is dimension dimension-indeeendeer independent burn-in period required for SGD noise to dominate, and for small numerical simulations, one may actually observe an (F (Fpp, Fuc) tradeoff.
Phase IV. SGD frustrated, capacity constrained. Like Phase III, SGD noise is important. The SGD algorithm in Phase IV will be distinguished from gradient descent. As one approaches the high-dimensional line (2x= = 1) in Phase III. the (r) disappears. It becomes too small relative to ppp and Kpp. Moreover at the nigh-dimensional line. Fpp becomes important again. Thus, the loss curve in Phase IV (a and b) look like P(r, d) x Fpp(r, d) + Fo(r, d) + 7B K (r, d). The distinction
<a < 0.5, 23 > 1) and Phase IVb C <a < / 23 > 1) is where the compute-optimal tradeoff occurs. It changes from Kpp Fo (Phase IVa) to pD Kpp (Phase IVb). In particular it can be (Phase IVb) the SGD noise is so large that increasing the model parameter count compute-optimal We note that in this phase d must be taken very large (in particular larger than we could numerically attain) to get quantitative agreement between the exponents and theory.
between Phase IVa (1 J2
Other observations. In Phase III, Ib, and IVa, the optimal parameter d' = f1/² (see dashed lines in Fig. 4a). These phases, taken together, encompass large section of the (a, B--hhaee plane. This suggests that there is a potential universal scaling law. Moreover using A100-GPU of compute, one reaches scales of d where the observed exponents in the scaling laws SGD, the pooretically-deriver Volterra equation eq. (10), and the equivalence of P(r) eq. (17) are still changing (see Fig. 5b and c). This serves as a potential warning for empirically derived scaling laws. Additionally, although we have identified the lower-left of the phase diagram (a + 3 < 1/2) as "no power-law", this designation relies on the assumption e d, which could be relaxed interesting effect in more realistic (e.g. non-linear) models.
Compute- optiimll learning rate and batch. Previously, we have used B and the maximal learning rate allowed. One can also consider finding the compute-optimal curves with respect to batch size and learning rate, i.e., find d", 7", B² such that
(d","", B*) E arg min din,, E arg min.( d d, s.t. > < 1 and |xypll < 1.
(21)
In Section I, we show that P( (L 7, is monotonic B and therefore B is optimal. Similarly for 7, in Phases I, II, III, the loss IP( d Y, d) is monotonic and thus the maximally stable learning rate is optimal. For Phase IV, this is not true. There does exist an optimal 7" (with = =1),
(a)-0 4n +88-T
-2x 220020+28-1) d'(() x 200++0028-1, and P*( x 4n 2n 2
2a+28-1
where the tradeoff occurs between (p = Fo(r) and Phase IVa and IVb collapse to a single phase. This is proven in Proposition I.
Conclusion. We analyze simple three parameter model, PLRF and derive deterministic expressions for the training dynamics (see Volterra equation (10)). We then extract compute-optimal scaling laws for large d. We identify 4 phases (+3 subphases) in the (a, (a,3))phi 3)-sh plane, corresponding to different compute-optimat relative importance of model capacity (Phase I, IV), poor embedding of the features (Phase II. III), and the noise produced by the SGD algorithm (Phase III, IV). The latter suggesting that another stochastic algorithm might change the compute-optimal curve; we leave this interesting direction to future research. We also show evidence of a universal sealing law which we also leave for future research to explore.
curve/loss behaviors. These phase boundaries are determined by the
10

---

Acknowledgments and Disclosure of Funding
C. Paquette is a Canadian Institute for Advanced Research (CIFAR) AI chair, Quebec Al Institute
(MILA) and Sloan Research Fellow in Computer Science (2024). C. Paquette was supported by Discovery Grant from the Natural Science and Engineering Research Council (NSERC) of Canada, NSERC CREATE grant Interdisciplinary Math and Artificial Intelligence Program (INTER- MATH-AI), Google research grant, and Fonds de recherche du Québec Nature et technologies (FRQNT) New University Researcher's Start-Up Kart-Up Program. Research by E. Paquette was supported by a Discovery Grant from the Natural Science and Engineering Council (NSERC). Additional revenues related to this work: C. Paquette has 20% part-time employment Google DeepMind.
References
[1] Luca Arnaboldi, Ludovic Stephan, Florent Krzakala, and Bruno Loureiro. From high- dimensional & mean-field dynamics to dimensionless odes: A unifying approach to sgd in two-layers networks. In The Thirty Sixth Annual Conference on Learning Theory (COLT), pages 1 1199-1227. PMLR, 2023.
[2] Søren Asmussen, Soren Asmussen, and Sren Asmussen. Applied probability and queues. volume 2. Springer, 2003.
[3] Krishna B Athreya, Peter E Ney, and PE Ney. Branching processes. Courier Corporation, 2004.
[4] Francis Bach. High-dimensional analysis of double descent for linear regression with random projections. SIAM Journal on Mathematics of Data Science, 6(1):26-550 60,60,00500 2024.
[5] Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jachoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. Proc. Natl. Acad. Sci. USA, 121(27):Paper No. e2311878121, 8, 2024.
[6] Zhidong Bai and Jack W Silverstein. Spectral analysis of large dimensional random matrices, volume 20. Springer, 2010.
[7] Tamay Besiroglu, Ege Erdil, Matthew Barnett, and Josh You. Chinchilla Scaling: A replication attempt. arXiv preprint arXiv:2404.10102 2024.
[8] Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. A Dynamical Model of Neural Scaling Laws. In Proceedings of the 41st International Conference on Machine Learning (ICML), volume 235 of Proceedings of Machine Learning Reseurch, pages 4345-4382, PMLR, 2024.
[9] Blake Bordelon and Cengiz Pehlevan. Learning Curves for SGD on Structured Features. In International Conference Learning Representations (ICLR), 2022.
[10] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized squares algorithm. Foundations of Computational Mathematics, 7:331-368, 2007.
[11] Luigi Carratino, Alessandro Rudi, and Lorenzo Rosasco. Learning with sgd and random features. Advances in Neural Information Processing Systems, 31, 2018
[12] Chen Cheng and Andrea Montanari. Dimension free ridge regression. arXiv preprint arXiv:2210.08571. 2022.
[13] Elizabeth Collins-Woodfn,, Courtney Paquette, Elliot Paquette, and Inbar Seroussi. Hitting the high-dimensional notes: an ODE for SGD learning dynamics on GLMs and multi-index models. Inf. Inference, 13(4):Paper No. iaac028, 107, 2024.
[14] Romain Couillet and Zhenyu Liao. Random Matrix Methods for Machine Learning. Cambridge University Press, 2022.
[15] D. Cruz-Uribe and C. Neugebauer. An Elementary Proof of Error Estimates for the Trape- zoidal Rule. Math. Mag., 76(4))303-306, 2003.

---

[16] Hugo Cui, Bruno Loureiro, Florent Krzakala, and Lenka Zdeborová. Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime. Advances Neural Information Processing Systems, 34, 2021.
[17] Stéphane d' Ascoli, Marylou Gabrié, Levent Sagun, and Giulio Biroli. On the interplay between data structure and loss function in classification problems. Advances in Neural Information Processing Systems, 34:8506-8517, 2021.
[18] Leonardo Defilippis, Bruno Loureiro, and Theodor Misiakiewicz. Dimension-free deterministic equivalents for random feature regression. arXiv preprint arXiv:2405. 15699, 2024.
[19] Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal Distributed Online Prediction Using Mini-Batches. Journal of Machine Learning Research, 13(1), 2012.
[20] Aymeric Dieuleveut and Francis Bach. Nonparametric stochastic approximation with large step-sizes. The Annals of Statistics, 44(4):1363 1399, 2016.
[21] Cedric Gerbelot, Emanuele Troiani, Francesca Mignacco, Florent Krzakala, and Lenka Zde- borova. Rigorous dynamical mean-field theory for stochastic gradient descent methods. SIAM Journal on Mathematics of Data Science, 6(2):400-427, 2024.
[22] Gustaf Gripenberg. On the resolvents of nonconvolution Volterra kernels. Funkcial. Ekvac., 23(1):83-95, 1980.
[23] Walid Hachem, Philippe Loubaton, and Jamal Najim. Deterministic equivalents for certain functionals of large random matrices. Ann. Appl. Probab., 17(3):875-930, 2007.
[24] Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbi, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Oriol Vinyals, Jack Rae, and Laurent Sifre. An empirical analysis of compute-optimal large language model training. In Advances in Neural Information Processing Systems, volume 35, 2022.
[25] Hong Hu, Yue M. Lu, and Theodor Misiakiewicz. Asymptotics of Random Feature Regression Beyond the Linear Scaling Regime. arXiv preprint arXiv:2403.081666 2024.
[26] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B. Brown, Benjamin Chess, Rewon Child, Scott Gray, Alex Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint 20t::2000.0886. 2020.
[27] Kiwon Lee, Andrew Cheng, Elliot Paquette, and Courtney Paquette. Trajectory of mini-batch momentum: batch size saturation and convergence in high dimensions. Advances in Neural Information Processing Systems, 35:36944 36954,,367,,,,- 2022.
[28] Licong Lin, Jingfeng Wu, Sham M Kakade, Peter L Bartlett, and Jason D Lee. Scaling Laws in Linear Regression: Compute, Parameters, and Data. arXiv preprint arXiv:2406.0844 08466 2024.
[29]
Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Mare Mezard, and Lenka Zdeborová. Learning curves of generic features maps for realistic datasets with teacher-student model. Advances in Neural Information Processing Systems, 34:18137-18151, 2021.
[30] Alexander Maloney, Daniel A. Roberts, and James Sully. A Solvable Model of Neural Scaling Laws. arXiv preprint arXiv:22 10. 16859, 2024.
[31] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667-766, 2022.
[32] Gabriel Mel and Jeffrey Pennington. Anisotropic random feature regression in high dimensions.
In International Conference on Learning Representations, 2021.
12

---

[33] Courtney Paquette, Kiwon Lee, Fabian Pedregosa, and Elliot Paquette. SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality. In Proceedings of Thirty Fourth Conference Learning Theory (COLT), volume 134, pages 3548-3628 2021.
[34] Courtney Paquette and Elliot Paquette. Dynamics of stochastic momentum methods on large- scale, quadratic models. Advances in Neural Information Processing Systems, 0199229-2240 2021.
[35] Courtney Paquette, Elliot Paquette, Ben Adlam, and Jeffrey Pennington. Homogenization of SGD in high-dimensions: exact dynamics and generalization properties. arXiv preprint arXiv:2205.07069 2022.
[36] Loucas Pillaud- Pillaud-Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes. Advances in Neural Information Processing Systems, 31, 2018.
[37] Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. Advances in Neural Information Processing Systems, 30, 2017.
[38] Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International conference on machine learning, pages 71-79. PMLR, 2013.
[39] Utkarsha Sharma and Jared Kaplan. A neural scaling law from the dimension of the data manifold. arXiv preprint arXiv:2004. 10802, 2020.
[40] Jack W Silverstein and Zhi Dong Bai. On the empirical distribution of eigenvalues of a class of large dimensional random matrices. Journal of Multivariate analysis, 54(2):175-192, 1995.
[41] James B. Simon, Dhruva Karkada, Nikhil Ghosh, and Mikhail Belkin. More is better in modern machine learning: when infinite overparameteriizaton is optimal and overfitting is obligatory. In International Conference on Learning Representations (ICLR), 2024.
[42] Aditya Vardhan Varre, Loucas Pillaud-Viiee Vivien, and Nicolas Flammarion. Last iterate convergence of SGD for Least-Squares in the Interpolation regime. In Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 21581-21591, 2021.
[43] Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham M Kakade. Benign overfitting of constant-stepsize SGD for linear regression. Journal of Machine Learning Research, 24(326): 1-58, 2023.
13

---

4+3 Phases of Compute-Optimal Neural Scaling Laws
Supplementary material
Broader Impact Statement. The work presented this paper is foundational research and it is not tied to any particular application. The set-up is simple well-studied random features model with synthetic data and solved using a commonly deployed algorithm stochastic gradient descent. We present (theoretical) compute-optimal curves for this model. The results theoretical and do not anticipate any direct ethical and societal issues. We believe the results will be used by machine learning practitioners and encourage them to
build more just, prosperous world.
Outline of the paper. The remainder of the article is structured as follows: in Section A, we provide additional related work. In Section B, derive the convolution-type Volterra equation for the expected risk under SGD, (7). In Section C.I, we analyze the Volterra equation under the deterministic equivalent. discussion on the convergence threshold for P(r) including necessary and sufficient condition for bounded solutions of (10) (Proposition C.2) and a proof of Proposition 2.1 are provided in Section C.2. Some background on Volterra equations and their solutions are provided in Section C.3. 1 followed by the proof of Theorem 2.1 in Section C.3.2. We finish this section with detailed description and proofs for the risk curves all phases, Section C.4. Section D is devoted to deriving and proving the compute-optimal curves in Table 2. We follow this by Section E which analyzes the deterministic equivalent for the resolvent of K. Here examine the spectrum of K from a random matrix point of view. In particular, this section, we prove estimates on fixed point equation,
eq. (9). We then give explicit descriptions of the components of the forcing function, pp. To. F pp. Jaes as contour integrals and show that the error terms errory are small, see Section F. We
do the same with the kernel function K and kernel norm in Section G. In Section H, we derive the asymptotic formulas for the components of the forcing and kernel functions (see Table 1) used the compute-optimal curve derivations. Finally, their experimental setups) as well as detailed descriptions of the different approaches to estimating the exponents in the scaling law and optimal model-parameter, Section
end with some additional numerical experiments (and
Contents
1 Introduction
1.1
Problem Setup: SGD Power-law Random Features
2
Learning Dynamics of SGD
2.1
Forcing function and kernel function
3
The 4 Phases
3.1
Compute-optimal Curves
8
Additional Related Work.
16
B Derivation of Volterra equation
18
Analysis of Volterra Equation
21
C.I Deterministic equivalent of the loss under SGD
22
C.2 Convergence threshold
23
C.3 Simplification of the Volterra Equation
24
C.3.1 Background on Volterra equations
24
C.3.2 Proof of Theorem 2.1
26
14

---

C,4 Details of risk curves for the phases
27
C.4.1 Above the high-dimensional line (Phases la, 11, III)
28
C.4.2 Below the high-dimensional line (Phases IVa, IVb, lb, Ic)
Compute-optimal curves
33
D.1
Compute-optimal curves: Above the high-dimensional line (Phases la, II, III).
34
D.1.1 Phase la
35
D.1.2 Phase
35
D.1.3 Phase III
36
D.2
Compute-optimal curves: Below the high- ligh-dimmesionall line (Phase IV, lb, Ic), 2a
37
D.2.1
Phase IV (a) and (b)
37
D.2.2 Phase lb
39
D.2.3 Phase Ic
39
E Spectrum of K: random matrix theory
40
E.1
Self-consistent approximation for (K - -) (DI/2WW2 DI/2 1112-=2--
=)
40
E.2
The region near and the spectral bulk
44
E.3 The mesoscopic region
E,4 The large region
53
Approximation the forcing function
54
G Estimation of Kernel function
58
H Asymptotics of forcing function and kernel function
61
H.l Pure point forcing term, 3pp (r)
62
H.2 Model misspecification, point mass at 0, Fo(r)
H.3 Absolutely continuous forcing function, For (r)
64
H.4 Kernel function asymptotic...
66
I Optimizing batch and learning rate
69
LI Optimal batch size
70
1.2 Optimal learning rate
70
J
Experimental Results
70
J.1
Measuring the Scaling Law Exponent
71
J.2
Measuring Parameter Count Exponent: Approach 0
................................
71
J.3
Measuring Parameter Count Exponent: Approach
72
J.4
Measuring Parameter Count Exponent: Approach 2
72
J.5
Exponents comparison: Theory Measurement.
73
J.6
Instantaneous slope
73
J.7
Negative 8.
74
15

---

J.8 Additional plots for different phases
74
A
Additional Related Work.
Table 3: Comparison of the source/capacity parameters various related work. We note this table taken from Table 1 in [DLM244] with the addition of [Lin+24].. We note that both [DI.M24] and [Iin+24]] appeared concurrently with this article.
This work
[DLM24]
[Bahri+21]
[MRS22]
[BAP24]
[Lin+24]
Input dimension
d
d
M
M
M
# of features
p
P
N
N
Iterations/samples
Y1
D
T
Capacity
20
1 +
1 + a
b
Source
2a-+281 -1
[ )
1 {1
)))
e-1
h-1
b
25
2a
Target decay
a + 3
or +
0
0
(in L2)
[DLM24] L. Defilippis, B. Loureiro, T. Misiakiewicz. Dimension-free deterministic equivalents for random
feature regression. 2024
[Bahri21] Y. Bahri, D. Dycr, Kaplan, J. Lee, and U. Sharma. Explaining neural scaling laws. 2024.
[MRS22] A. Maloney, D.A. Roberts, J. Sully. solvable model neural scaling laws
[BAP24] B. Bordelon, A. Atanasov, C. Pehlevan. A dynamical model of neural scaling laws. 2024.
[Lin24] L. Lin, J. Wu, Kakade, Barlett, J.D. Lee. Scaling Laws Linear Regression: Compute. Parameters, and Data. 2024
Random features and random matrices. This paper uses random matrix theory to analyze a random features problem, which in statistical language would be the generalization error of the one-pass SGD estimator. Random matrix theory has played an increasingly large role in machine learning (see for [14] for modern introduction).
The imput need for our random matrix analysis is for sample covariance matrices with power-law population covariance (i.e. linear random features). The analysis of sample covariance matrices precedes their usage in machine learning (see e.g. [6]), but our knowledge, detailed study of all parts of the spectrum of sample covariance matrices with power-law population covariances has not appeared before. The narrower study of ridge regression has been extensively investigated (see for e.g. [4, 12]), and the concurrent work [18] provides complete analysis of the ridge regression However, while (roughly speaking) ridge regression requires analysis of resolvent (4 - =Id)-1 statistics for negative spectral parameter (which might be very close to 0), the analysis this work requires resolvent statistics for essentially all 2.
problem when 2a
There is a larger theory of nonlinear random features regression, mostly in the case of isotropic random features. Including nonlinearities in this model natural future direction; for isotropic random features with proportional dimension asymptotics this has been explored in works such as [31] and for some classes of anisotropic random features [32, 17, 29] (we mention that lots of the complexity of the analysis of power-law random features arises from the analysis of the self-consistent equations- indeed the self-consistent equations we use date to [40], but the analysis of these equations may still be novel). This strongly motivates con-proportional scalings (which would be inevitable power-law random features with nonlinearities); in the isotropic case, the state the art is [25].
Random features regression, 'source/capacity" conditions, and SGD. A large body of kernel regression and random features literature is formulated for "source/capacity" conditions, which are power-law type assumptions that contain the problem setup here, when 2a 1 (the diw-dimensional regime). For convenience, we record the parameters
2a 23
assarce 2a and
4a
16

---

Table 4: (Nonexhaustive) Comparison of sample-complexity results. Let p def 2a 23 We use our Phases with n. = sample size, d = parameters. We will include derivation of these results the appendix our paper: M222') can also be done with RR+oppimal-ridge, which yields same in Phase la, but different in that is, they capture the Fpp. but not Fac.
Phase II/III [VPF2IJ obtain 9 < n The minimax optimal rates never achieve any the rates (always worse), which can connected to overly conservative, small stepsizes. For derivation of the minimax rates, we used Cor. 2 from [DB18]'. [Lin+24]] requires label noise order 1 and also very small learning rate.
This work
[DLM24)
Algorithm
one pass SGD
RR O(1--ridge
O(n ((n=p/(a))d
Phase
same ours same as ours (n 2nn nn
O( (0((a/ Vd n - -141/(20)
Risk, p(n (n)
Phase II
Phase III
O(n 21111/122 vo n
20-1
20 vd 20)
20-1
2a V Vdd2ay
Minimax optimal
[Lin+24]] one-pass SGD, very small stepsize
one-pass SGD, very small stepsize
Algorithm
Phase Ia
0 +22))))))
Odd +m -m ( ( (2,12332(2220) -+41/(20))
Risk, S (n)
Phase II
0 n 22(2)+28)
does not cover does not cover
Phase III
0 (4/(4))))
Carratino, Rudi, Rosasco. Learning with sgd and random randomfeatures. 2018
Dieuleveut and Bach. Nonparametric stochastic approximation with large stepsizes. 2016.
Pillaud-Vivien, Rudi, Bach. Statistical optimality of SGD on hard learning problems through multiple passes. 2018.
Varre, Pillaud- Vivien, Flammarion. Last iterate convergence of SGD for least squares in the interpolation regime 2021.
Here we have taken r as the limit of those r's for which the source/capacity conditions hold (see Table 3). We note that in this language r is often interpreted as 'hardness' (lower is harder), and that r E (0, 0.5), r (0.5, 1.0) and r E (1.0, oo) correspond appeared previously (see the citations below); they are also precisely the 3 phases Ia, II, and III.
regimes of difficulty which have
The authors of [37] establish generalization bounds for random feature regression with power-law structures in 2o > case. These bounds were sharpened in [16] and extended in [18] (see also the earlier [10] which shows kernel ridge regression is 'minimax optimal' under various "source-capacity conditions') ); we give a comparison to these bounds in Table 4, but we note that the problem setup we have is not captured by 'minimax optimality' (in particular minimax optimality worst-case behavior over a problem class, and our problem setup is not worst-case for the traditional source/capacity conditions)
We note that this paper is fundamentally about computation, but the novel mathematical contributions could also be recast in terms of generalization bounds of one-pass SGD, some of which are new. The work of [11] compares SGD to kernel ridge regression, showing that one-pass SGD can attain the same bounds kernel ridge regression and hence is another minimax optimal method (again under 'source-capacity" conditions). See also [20] which considers similar statements for SGD with iterate averaging and [36] for similar statements for multipass SGD; see also [38, 19] which also prove the single-batch versions of these. These bounds attain the minimax-optima rate, which are worse than the rates attained in this paper (see Table for comparison).
Using the deterministic equivalents for random matrix resolvents [23], we in turn derive deterministic equivalents for the risk curves of SGD.
Dynamical deterministic equivalents, Volterra equations and ODEs.
The method of analysis of the risk curves in this paper is by formulation of a convolutional Volterra equation [33]. This can be equivalently formulated as system of coupled difference equations for weights of the SGD residual in the observed data covariance, which generalizes beyond the
17

---

least-squares context [13]; in isotropic instances, this simplifies to tinteeddmeesional family of ODES [1]. This can also be generalized to momentum SGD methods [34] and large batch SGD methods [27]. wwwoolutionVoolteee equations are convenient tools, as they are well-studied parts of renewal theory [2] and branching process theory [3].
Another method of analysis is dynamical mean field theory. The closest existing work to this one in scientific motivations [8], which uses this technique. This formally can be considered as a type of Gaussian process approximation, but for finite family of observables ("order parameters") In instances of one-pass SGD (including in anisotropic cases), this rigorously shown to hold in [21]. The analysis of the resulting self-consistent equations is nontrivial, and [8] does some of this analysis under simplifying assumptions on the structure of the solutions of these equations.
Besides these works, there is a large theory around generalization error of SGD. The work of [42] gives direct analysis of risks of SGD under "source/capacity" type assumptions which formally capture the Fpp parts of the Phase Ia/ll loss curves. The risk bounds of [43] give non-asymptotic estimates which again reproduce tight estimates for the Fep parts of the loss (note that to apply these bounds to this case, substantial random matrix theory needs to be worked out first); see also concurrent work [28] where some of this is done.
B Derivation of Volterra equation
We begin by deriving a Volterra equation for the population loss (0), (5). Fix quadratic q Rd + R. ie.. function ((z) x= Ar + e x + for fixed matrix A E Rdxd vector e R and constant с E R. Let us consider the filtration F, = oWW (o,.,,)..,, which conditions on W and the past iterates. Then we have from Taylor theorem,
1 EV(Y' (0++1- - 0,) [F.]. (22)
[la(0,+1) - ((0.) B ((VV)(()) 0,41 - 0,) [F,]+
We need to plug the expression for SGD in (6) into the above. The first thing we observe is that we need moments of Gaussians via Wick's formula: for fixed vectors o RR i 2, 3, and ~ NO0 D)
E. (a v1)l = Eg Tr(x 2)]01 Do
Ex [2, (I, v2) valo,, u4)l (D, 0 @ 02) (D, U3 @ es) + (D, @ va) 8 v4) (23)
+ (D,v) 01 (D) 02 v3).
Here we recall that the (u x -m-mati D def Diag(j 20 calculations, can compute explicitly each of the terms in (22).
1 S j < v). Using these moment
Gradient term. First, we consider the gradient term in (22). A simple computation yields
E((V((0)), - 0,) 0,) 1F] -
(V) E W x ((W" x3 0,) (2) (x), [F]))
jEB.
(24)
BVV(()) W DWe, W Db).
Quadratic term.
We now turn to the quadratic term in (22). Supposing and & are independent
samples,
(V2 q. (0r+1-0,)))
0,) 02) [F,]
1VV29 9:
Σ T I'( -' - (12.61) 8 (( Σ WT WTTTRWWTT',ON (ot (04,01)) jEBr
KEB,
= LB Σ ( q.
Σ W اي (WT x200) - -00 (0,,611 [F.
02
jeBr
JeBr
72
g g.2 Σ
W WTT 2 - (orl bi) 2 W x..0) (0t (ot.01))
+ 2
Br
(25)
18

---

Continuing, we have
1 B 9. (0/+1 - 0,) [r]
2 (V', (z) [..]
(2,
0,) (z, b)1) & (W (W" (2) [.]] (26)
(("", 0.) - (z. ()) 20) [.
7 - E EV 4, (WT x (WT 0,) (z, b|l) & (WT (2,001))1A
Let 42g = -ド 1/j 8 8g. Now we note the following
((W7 2. 0.0,) - (x,,)) q: (WTx) 1)02)
= =(-" 2) (WV x, 0,)² - x, 0,) b) + (a, 6)2]
(27)
E (c, (w, (z, Wo x, 02)² - 2(z, WO, (z. b) + ()9.)
This, after taking expectations, is in the form for us to apply the moment computations in (23). Using these moments, we get the following expression:
E
Σ lr We,) Wo,M 2, -, - (8,) (z, b
(V',, Dw D' b)]l
+2 +2Σ [1, We, @ Wo, & (D, Wey @ (D,) Wē, b)
(28)
+ +D, Wu, 8 b) (D, (D, 0b) - Wi, @ (B,) We, 8b)
= -V WT DW) /2 (WO,- - 2)
+2 Σ Wo, 2 (WO, (D, 8 (WO, - -)).
Now we simplify the 2nd term in the summand
We, @ (WO,- - b))D,WW @ (WO, - b))
DWTD, @ (WO, - b)) D, ūg @ (WO, b))
(29)
Σ D)niiii (WO, - b): Dimeūj (WO, - -b)e
= (DDW(V'OWTD, (WO, - 2)
Moreover, as x and â are independent, we see that
E E((V2g q, (W x x, 0,) b)) @ (W ( 2, 2,0,) - (4, (B)1
= =E[(W8, b)"'z="' WV 21" (WO, - b) Fr1
(30)
= (We, " D(WA,- b).
As a result, we deduce by combining (27), (28), (29), and (30) with (26) gives the following representation for the expected quadratic term
} B (0,41 - = (V2
q, WT DW) (WW, - b)]l
(31)
+ BBB(+ (WW DWW,, - 6))
(W0,-6)84
19

---

Volterra equation. Using the simplified gradient and quadratic terms, we can now state the ex- pected change in any quadratic q R + R evaluated an iterate of SGD (6):
Elg(0,+1)- ((,,) Fr] - W DW 0, - W Db)
3 q. w' D b)ll
(32)
B((++ (DW (V D. (WO, b)02). 2
We can write R= Im(W) @ W Thus, there exists b E I and E I= such that one can write b Wb+ b, that is, something in the image of W and something in the co-ker of W, i.e.
= Wb +b, b, where W Db = 0.
(33)
One-step update formula. Using this observation, we have a formula for the expectation of the quadratic : R2d -> TR,
Elg(0,+1) - ((,,) F = - W DW - b))
2 (V'g, T DWNILD (Wo, b)]l 2
(34)
( B(
DW DW'')"W" DW, (0, -0.--p1 -B) B)
We observe that all the terms on the right hand side of the above (34) involve the matrix W DW e Rdxd Consequently, let (Aj, wy) for j = 1....,d d be the eigenvalue-eigenvector of W DW with
||mس|| 1. Now define
(r) def (w (0, - (ea-b832 2) for all j = 1,...,d
(35)
We will write our Volterra equation in terms of P 's. Note we can express the loss (0,,)
||D 12 (wW,, b)] by
d (0,)) = 1DD b) Σ
xrp ||D1/26/22
(36)
j=1
We can now plug 03 into (34). For this, we need compute p3 and V2
0)(r) - ( 0, 2 Vop}(r) 2w, 0, - b), and V² pr) 2w, 0 wj.
Then we have that
dr) = -22 Or () TT DW b))
+ +By2(ws @ W) W DW) (WO, - b)]l2
(37)
B(B (WT (w, @ w; w/) DW, (0, - 8)82)
p2, + + BX,IID'
b)1l + B(B + 1)23p3(r)
Using an integrating factor, we can implicitly solve this expression
dp3 (k) = BA + BBB 1) + 72 1D/2 b)ll?
(38)
and thus, we have a discrete Volterra equation
(r(r) -r = -]()) (1 + 7 +BB((B1))
(39)
+ B > - 2yB22 + 2 B(B + 1 11'' 6)]1?
==0
Let us define K def TT DW. Using the expression in (36).
((,) W = Σ
10)3(0)(1 BYBA, + + 1)A3)" + ||21/281222
j=l
r-1
+
Bx
Σ (1 B2 + BBB + E ((.) 1. W).
j=1
==0
20

---

Let us define the kernel
(r) def 2
Discrete volterra equation for the loss for K = W DW. Let r be the number of iterates of SGD. Then
E (0,) W| (K(I- - 2yBK + 1) (6. b)02) + |1/22112
r-1
Σ
X (r ( -
d
(40)
23 By + + B(B + 1)13)* where (())= - B >
j=1
7 Tr (1 -BBK BBB + 1))
and D Diag(j 2a 15)50).
We can also write (40) in terms of K def DI/"WW" D2/ To see this, set DV/2W VVSUT where K UNUT and K VΩVT Then that
(6u - b)02) (poly(52)9, (U(6) - -))
(Vpoly(D))V (V (("())")VVVVVVVV (VVRU((B - b))
Discrete volterra equation for the loss with K D'/2 D1/2 Let be the number of iterates SGD. Then
(,,) W ((I 22,BK - ") (D'/ -)) |
r-1
Σ
- 1 B( W].
d
where - B Σ
B + 1)23)*
j=1
= x (r( 2r B + 1))
and D= ==Diagjj 1 u)
(41)
C Analysis of Volterra Equation
From now we consider the setting where the initialization of SGD is 0 0. Let introduce the forcing function:
+ + (T--,"=--788--0)37200000-0-----0 112//
(r) def
(42)
and recall the kernel function X (s):
(s)
While these representations are easy to see from the derivation of the Volterra equation, a more useful representation of the forcing function and the kernel function is through contour integrals over the spectrum of K. With this in mind, let I' be contour containing [0, 1]. Note that by the assumptions
21

---

on K, the largest eigenvalue is normalized to be 1; hence I' contains the spectrum of K. Then the forcing function takes the form
-1 2Ti
f ((R -)
- dz.
(43)
and the kernel function
$ 2τ Jr
* (r) -r Tr
1211-2 (1 -2)) dz)
(44)
Then can write the Volterra equation (41) as the forcing function plus convolution with the kernel and the expected loss, i.e.,
E B[ = ( (x E[(((t.) W(),
where (X * (l.) W]) = Σ x - (()
(45)
==0
C.1 Deterministic equivalent of the loss under SGD
The forcing functions Fr) and kernel function X (r) random functions they depend the random matrix W. Moreover the expressions via contour integration show that both of these functions can be described in terms of the random matrix K = D'/2WWT D1/2, Indeed is the resolvent of K,
(K, 2) def = (k-2)-1
which plays a significant role in & and . and thus in the expected loss ((,)(),) W]. To analyze the power law behavior of the expected loss, it would be helpful to remove the randomness in K, i.e., W. We do this by finding a deterministic equivalent for the resolvent of K, IK, 2) (K - =)-1, using techniques from random matrix theory. Intuitively, we want to take the expectation over the random matrix W; though not formally true.
Formally, we define the deterministic equivalent for the resolvent (KK, 2), by R(x) implicitly via fixed point equation
(z))
where R(=) = Diag 1-20m(2)) -15ss). (46)
1j=1 20m()))
As mentioned earlier, this deterministic equivalent, R(z) can be viewed, roughly as.
Ewi(R - =) = Ew (K, R(z);
though it is not formally the expectation over W.
Using this deterministic expression for the resolvent of K, defined deterministic expressions for the forcing function via the contour representation of I (r) in (43)
forcing function (
def -1 2 f. (x(2), (D)))) 2y
F(r)
dz, (47)
deterministic equivalent
and the kernel function in (44)
kernel function
) K(r) del B.Tr
-1 21 dz 2ti f.
deterministic equivalent
(48)
Using the deterministic expressions for the forcing function F and kernel function K, we define the deterministic function P(r) N I as the solution to the (discrete) convolution-type Volterra
cquation:
7-1
+ (XC PP)r), where (K * P)) Σ - 1 s)P(s)
(49)
==0
22

---

We note the similarity with the Volterra equation for SGD. We conjecture that the two processes are close: for } the sequence of iterates generated by SGD with 8g and any 0,
E 9 (
(1 - S sup
- (1+
P(r)
for all admissible v, d with probability going to I as d + oc.
We leave this for future research; we suspect it is true based upon existing of deterministic equivalence theory for random matrices and numerical evidence.
C.2 Convergence threshold
A natural question is: for what choices of batch B and learning rate does T converge? To answer this, we introduce an additional quantity, the kernel norm defined as
(kernel norm)
||]|||
def
K(s).
(50)
Proposition C.I (Kernel norm). The kernel norm satisfies
20x
||C|||
7j -2x
2ox > 1, then be taken to equal oc, that is,
j j-2a
||
7
2
Yj* 20
In the case that 2o < 1, we have
|K|||
2a
2a:) 0² 1-2a
2(1
In all cases, we choose ry so that the kernel norm is asymptotic to a strictly positive constant.
A well-known result about convolution-tyen type Volterra such (49) is that the solution of convolution- type Volterra equation bounded if and only the forcing function F(r) is bounded and the kernel norm ||]]|| < 1. This naturally leads to conditions for specific forcing function and kernel function.
Remark C.1 (Convergence threshold conditions.). The forcing function F is bounded and the kernel norm |[]]| < for (47) and (48), respectively, if and only
(i). 11-22-1 By, + 2 B(B 1) 1, for all X3 E [0, and (ii). kernel norm ||3]]| 1. (51)
The first term ensures that the forcing function of the Volterra equation in (49) goes to O (i.e., bounded) and the second condition is the same kernel norm bound. Moreover, we can think of condition (i). as the same condition needed for gradient descent to converge while the kernel norm the effect of noise from SGD. We also note that in light of Proposition C.I the kernel norm does not involve the batch size B. Therefore the condition ||3]| 1 only places a condition on the learning rate (see below).
We state necessary/sufficient conditions the batch size and learning rate (51) (Proof of Prop. 2.1).
Proposition C.2 (Necessary/Sfffiieent conditions on learning rate and batch size). The learning rate, y and batch size, B 0, satisfy
| 1,
1) 1) <.
(52)
if and only if the solution P(r) to the convolution-type Volterra equation (10) is bounded.
23

---

Proof. From (51), we need that | |1 B < 1, for all Ay E [0, 1). For this, we consider cases.
First, suppose that - 2 B2 +
< for all x E [0, 1]. We have that
By +
<0 + x( 2 + B(B + 1)x)
(53)
The roots are precisely x = 0 and x -[B+1]
( + 1)) 1, then the inequality in (53)
always holds. Therefore, we need that 7B +) <2
Now suppose -1 22 - + 1)x² 1, Then have
-2 2 (B + 1)x² < 0, for x E [0, 1]. The roots of the left-hand side are complex and thus the inequality always holds.
(54)
Remark C.2. Below the high-dimensional line, 20 < 1, the kernel norm diverges with u for fixed constant and so we must take 7y - 0 to ensure bounded solutions. Furthermore, with y - 0 (at any rate depending on v) we have the asymptotic equivalence
|
Y
22-20
2(1 - -2a)
1=1
For a proof of the asymptotic for ||3[]], see Covollary G.I.
Remark C.3. Similar results hold for the expected SGD loss (via the Volterra equation (45)) by replacing ||C]|| with || ||.
C.3 Simplification of the Volterra Equation
While convolution-type Volterra equation such (49) quite nice and well studied in the literature (e.g., [22]), we need an approximation of the solution to it to have better understanding of compute- optimal curves. In this section, show that bound (above and below) P(r) by constant multiple of the forcing function I and kernel function K.
C.3.1 Background on Volterra equations
To do this, need some background general convolution-type Volterra equations of the form:
Σ
P(t) = f(t) + (K (t),, where (K * Pt)
K(s)P(t- - s).
(55)
S=U
where f(t) is a non-negative forcing function and K(t) a monotonically decreasing non-negate non-negative kernel function.
Let us define K def
K
K
K * (t), the n-fold convolution of K where K K(t).
times
Under mild assumptions such as K then there exists unique (bounded) solution P(t) to (55) and the solution given by repeatedly convolving the forcing function with K (sec, c.g., [22, Theorem 3.5]),
Ere to= K(L) < 1 and the forcing function f is bounded,
P(t) f(t) + Σ K f(t)
j=1
= f() + (K (t) + (K ft) + (K
* f)(t) +....
This representation of the solution to (55) enables us get good bounds on P(t). First, state and prove a lemma attributed to Kesten's 's Lemma [3, Lemma IV.4.7).
Lemma C.1 (Kesten's Lemma). Suppose the kernel function K is positive and monotonically decreasing and K|| < co. Moreover suppose for some > O, there exists a T(s) > 0 such that
Σ K(s) 2(1 (()((( for all & 8=0
(56)
24

---

Then for all n 2 0,
((O) K(T) +1) (2)1 + +.))"
sup
((t)
Proof. Define
(1)(1)
def
On
sup
[(t] 1|)=
t50
Then 01 = 1, and we are trying to prove
((0) K(T) +1) (1 +
On
By definition of the convolution, we have that
(1)++1(L)
K(s)K(I- -3) x K(t (2]0s)(2][]]] k|]m-
K (1 - 8)
((s)K(1- 8)
I an x
2 1
2||
K|
5
By the hypothesis (56),
(+(
for 2 T,
S a, (1+ + (1).
(57)
K2)
For < T, we have
(+++
(t - s)
(2) I|)*
(2 1)
==0
(K monotonically decreasing)
< ((0)
(1)
a=0
|
$ K(0) (2)
(())
where the last equality follows by the equality conclusion, by monotonicity, we have that
|K**|
= || ". [22, Theorem 2.2()).
K ()+))(
LST an (1++1) T2T.
K(0)
2 K
22| (())
Hence we have that
K(0) K(T)2²
an+1 v
+ (1 + t)aa.
Developing the recursion,
(1 (1+))((())
1 n-j
1
K(0) K(T)
an+1
1=0 K(T)
2
+1++))" S (1 +8)"
1/2
+ (1 + e)".
The result is proven.
Remark C.4. If the assumption (56) holds only for T > t T, then the statement of Lemma C.I still holds with
K Kx(+t1())
K(T) + +1) (2))).
((0)
K(t)
We now give non-asymptotic bound for the general convolution-type Volterra equation.
25

---

Lemma C.2 asymtoyy Volterra bound). Let K and f be non-negative functions. Suppose K monotonically decreasing and some O, there exists a T()) > 0 such that
Σ K(s)K((t - s) s 221
for all 2 T.
Moreover, suppose the convergence threshold condition 2(1 + | < 1 holds. Then f(t) (K f)(t) P(t) - f(t) + x (K f)(t,
K(0) K(T) + +1) (-2]][((+5]
where C' =
Proof. We consider the upper and lower bound separately.
Lower bound: Since K and f is non-negative, then Σj= (K*) ((()) (K*1 () 2 (K ft), Recall the solution the convolution-type Volterra equation takes the form,
P(t) = f(t) +
Σ (K*5 f)t). 1=1
It immediately follows from Σj= * ()() 2 (K ()) the lower bound.
Upper bound: The solution to Volterra equation (in is
P() f(() + Σ (K f)(t..
By Lemma C.I and the hypothesis, there exists T > 0 and > 0 such that
(
(*) S ((s)
K(T) + (I]] + +
and (2| + +))) 1. Hence, we have that
Σ ( * 5(
Σ
Σ ())()))))))
==1
F=1
((O))
+1
[ (1 + + (K* (t)
((T))
,=1
K(0)
(1 +
(1-2]]((([++)) ) (K * ft).
K(T)
The result is shown.
C.3.2 Proof of Theorem 2.1
We are now ready to show one the main tools used to analyze the loss function, Theorem 2.1. The result relies approximations for the kernel and forcing functions found in Section F and Section G. We restate the theorem statement to remind the reader of the result.
Theorem C.1 (Approximation solution for P). Suppose Y and B at most half the convergence threshold and a > 1. There exists an M > 0 large and constant C = =(a, B, M), independent of so that for all admissible and d, for all M BBr,
F(r) + (X * (r) S P(r) 5F() + x (X * Fr))
(58)
The convolution further simplifies. For any 0. there exists an M 0 and constant C' C(a,, B, MM independent of so that for all M < Br.
1
(1 |]]| -F() + Cx
K(r) < (K (r) C (||9I F(r) + BB
-(())) (59)
26

---

Proof of Theorem C.1 / Theorem 2.1. Note for all yBr > 1/Md we have that co S K(() I (T) for some C. > O. This is where the limiting level starts dominate. We begin by showing (58). Fix & > 0. From Proposition G.2, we have that there exists an M >> 0 sufficiently large so that the hypothesis for Kesten's Lemma, i.e.,
X(s))C(( - 8) s 2(1 + {)||)]))(()), for all d /M BBr > M.
Therefore, we get (58) by Lemma C.2. To prove (59), we begin by
r/2 Σ K(r (c(r-8832 s) - (3)-)) + Σ x(r- s xK()) 8=//2
f/2
r/2
F(5) +(5)
F(s)
Σ K(s)
where we used monotonicity of and K.
Using Proposition H.2 and Proposition H.4, for large d²a /M 2 BBr 2 M, we have that F(5) x F(r) since F is power law for large (see also Corollary F.1). The same holds for X, using Proposition H.5 and Proposition G.2, ( = K(r) for d²d /M 2 BBr 2 M for some M > 0.
For small BBr & M, we have that F(r/2) < C and K(r 22 < C for some C >> 0. Since F and K are monotonic, we can choose a constant so that F(r/2) S F() and X(r/2) S X(r) for y Br S M.
Now using Proposition C.I and Proposition H.6, we have that
r/2
r/2
Σ K(r s))(s) S x())
Σ +
+
Σ K(s) - _ K(r) - [[]]|
BB
==0
For the lower bound, we have that
x/2
Σ F(s) + F(r) r/2
r/2
Σ K(r - ()(r)))F(s)) ==0
Ex( ())-)) +
Σ amr/2
K(r 8)5(}) 2 x(())
Σ x(s),
a=0
where we used monotonicity of K and F.
We note that F(s) C' for yBs < M for all M > 0. Therefore,
r/2
M/(2BB)
Σ T(s) N
J(s) 2 B
On the other hand, by Proposition C.1, for any e > 0, there is an M so that for any yBr 2 M,
r/2
Σ ==0
x((s) 2 (1 - |3||
This proves the lower bound.
C.4 Details of risk curves for the phases
We put together coherent picture of the effect of different choices of and 3 and their impact on the Pareto frontier. We will have 4 distinct phases where the expected loss will exhibit a power law decay and 1 region (a + B < 0.5) for which the expected loss has no power law decay (see Figure 2a). We will describe each of the 4 power law phases below marked by their boundaries.
First, we recall the forcing function I and kernel function K. introduced in Section 2.1.
27

---

Table Decomposition the forcing and kernel functions. We express the forcing function F()) as the sum of three functions, F pp. Fac- up to errors and kernel function X(r) as pp((), up to errors. These functions arise from the different parts of the spectrum of the deterministic equivalent for the resolvent of K.
Part of spectrum
Function
Fo(r) -1
2 Sr. (R(x), (D(x), -1 2 1)22)" dæ; see (84)
Point mass at 2 (Prop. F.1)
j
2-2-22
(1+ O(d where solves for dd
Fo(r) Σ
=1
20d x(v/d
+ x2a
Σ Eد
2f (Prop. H.3)
Fo(r) ~ d' d1-2(a40) pefil 28
du,
2f
(p)(r) 1 ('' u (38- (2)0) exp( Bru) du: see (85)
2a / (pp(r) ~ (2a) (2 1/1201122200001 x1 ( 2a +1) xr (1+3/00++1))
Pure point
(Prop. H.2)
(rc(r) 2a d-2a
1/122) d exp(-2yBru) du, where co = プj=1J 2B
Abs. con't I
and otherwise 0: see (85) If 2a 1 and 28 1,
Fac(r) c2 (2 1- 1101))20122222000000000 - 20) x - -
d d (Prop. H.4)
Xpp (r) del 2B
2n Jo u 1 1-1022) (xpp1120eeppppp111) 2y du, 1/4; see (86)
Pure point
Kpp ~ ~ (2a) 22/1)2)) x r(2 - 2 x r 2+1/ (Prop. H.5)
Forcing function. For the forcing function,
F(r) = Fo() + (p) + Fre(r) + errors.
(60)
The function Fo(r) is the component of the forcing function corresponding to the point mass at O, (r)(r) is the component of the foreing function corresponding to the pure point part of the spectrum, and lastly, the most complicated part of the spectrum, the forcing function corresponding to the distorted features. In particular, we will show Section F the exact definitions of T 3 pp Fac and |errory| are small, and, in Section H, we derive asymptotic-like behaviors for these functions. See Table 5 for definitions and asymptotics.
Kernel function.
Similarly, the kernel function K is
K(r) = kr) errorsk.
Note here that the kemel function has multiplication by the eigenvalue of K and the point mass at will not contribute. In Section G, we will give an explicit definition of Kpp and show error terms small and, in Proposition H.5, give the asymptotic- like behavior of Kpp-
Now we deseribe in detail the different risk curves that arise for the different phases.
C.4.1 Above the high-dimensional line (Phases Ia, II, III)
This setting is commonly known as the trace class. It is characterized by four components:
learning rate 7 can be picked independent of dimension;
loss curve does not self average, that is, the loss curve does not concentrate around deterministic function:
V 2 d, but e has no upper bound and so we can take u - oc;
batch, B, is constrained be small (see Proposition C.2).
When 2a 1, or the trace class phase, the loss will exhibit 3 different phases. We described these phases in detail below.
28

---

Phase la: (23 < 1, 20 > 1). In this phase, it notable for three characteristics:
absolutely continuous part of the foreing function does not participate: level at which SGD saturates is affected by P:
SGD noise does not participate.
In this case, the loss curve is just a constant multiple of gradient flow. Hence, we have that P(r) = Fxp Fo(r).
Proposition C.3 (Phase la: 23 1, 2a > 1). Suppose 2B < and 2a > Suppose the learning rute y and butch B > 0 satisfy at most half the convergence threshold in Proposition C.2. Then there exists an 0 large and constants = C(a, B, M) and = c(a, M), independent of d. so that for all admissible and d, for all ABr > M
Cx (F + Fo(r)) - P(r) S C' x (Fmp(r) Fo(r))
(61)
Proof. By Theorem C.I. know that it suffices look the forcing function F and kernel function K. Moreover, in this regime, we have that y and B are constant (see Proposition C.2).
The rest of the argument relies the bounds found in Proposition H.2, (Fpp), Proposition H.4 (Fac), Proposition H.3, (Fo), and Proposition H.5 (Kpp).
For the forcing function, Foc (r) 0 as 23 < (Proposition H.4). Therefore the forcing function is composed of 3 (p) and Fr(r).
First, we have that (r) 2+1/(2a) < (r (148)))(14+//)111(2)) Proposition H.2 and Proposition H.5, for BBr > M, where M is some constant, we have that (r) C x 3 (r) for some C 0. Hence the result is shown.
a in this phase. Thus, using
As consequence of the argument above, know that
(rp((),
fr S Do Br 2 Do
P(r)
for some Do that depends on d.
Fo(r),
Phase II: (23 1, 2a 1,3 < a) For this phase, we see that
limit level is unaffected by 8::
absolutely continuous spectrum takes over for r (Md", (2/M for some M;
SGD noise does not participate.
Therefore, in this case, have that
P(r) = Jpp Fac(r) + Fo(r).
Proposition C.4 (Phase II: 2/3 > 2a > 1, a). Suppose 23 > 1, 2o > 1, and B < a. Suppose the learning rate and batch B > 0 satisfy at most half the convergence threshold in Proposition C.2. Then there exists an M. > 0 large and constants C C(a, 3, M) and c c(u,, B, M), independent of d, that for all admissible and d, for all 7 Br > M
c x (5 pp (r) + (r) + Fo(r)) & P(r) < x (Fyp(r) + Foc Fo(r))
(62)
Proof. By Theorem C.I, know that it suffices to look the forcing function F and kernel function K. Moreover, in this regime, we have that y and B are constant (see Proposition C.2).
The rest of the argument relies the bounds found in Proposition H.2, (F (ppp), Proposition H.4 (Fac), Proposition H.3, (Fo), and Proposition H.5 (Kpp).
BBr < Mo. for some Mo: First, have that Kpp (r) Co F (r) (Proposition H.5) and Fac(r) S Co x (r) (Proposition H.4) for some constant Co >> The constant Mg is where the asymptotic of J pp starts to apply.
29

---

Mo & BBr I M1, for some Mo and for all M1 > Mo: We see that (yBr) 1++1((2m) < (r (1BBr)((+///)11/222 as 3 < in this phase. Thus, using Proposition H.2 and Proposition H.5, 7B pp S C1 3 (r) for some C1 0. quick computation shows that Faa(r) $ 5. pr)()).
we have that 1
M1 S BBr I M2d2a, for any M1 and some M2: The M2 is the smallest of the two endpoints for the asymptotics of 'yp and Fac. As in the previous regime, we have that J Kpp(r) S (T)
In this region, Fro(r) x d (1 -1+1((2a) and 5 ppp(r) (r) x (r (1tt-)(())))))1(22)) We see at (r = da that (yBr) I (d (p((r x (r)(r) and started, i.e., when Mi with Fac(r) x (r).)) Therefore, must change in this regime to being Fac dominate.
d 28 I d=1 as 2/3 > Therefore, at yBr = dd=
M2da BBB for all M2: In this case, all terms are bounded above by Fo
As consequence of the argument above, know that
(r),,, BB - Do
P(r) ~
(re(T), if Do S Brr s Di yB 2 Dr
for some Do, Dj that depend on d.
(63)
Fo(r),
Phase III: SGD noise appears, (23 1, 2a 1,83a) In this case, we see that SGD changes the dynamics over gradient flow. In particular,
limit level is unaffected by 3;
absolutely continuous forcing function takes over for iterations r E (Md, da /M) for some
M;
SGD noise regulates convergence.
Thus, we have that
P(r) x Jno(r) + + (p)
(64)
Proposition C.5 (Phase III: 23 1, 2a > 1, B a). Suppose 23 > 1, 20 and 3 Suppose the learning rate and batch B > 0 satisfy at most half the convergence threshold in Proposition C.2. Then there exists an M > O largge and constants C C(a, 3) and
c = c(a, M), independent of d, so that for all admissible v and d, for all BBr > M
cx (F Fo(r) + (p)))))) < P(r)
SCx (Fac(r) + Fo(r) + (r)()))
(65)
Proof. By Theorem C.I. know that it suffices to look the forcing function F and kernel function K. Moreover, in this regime, we have that y and B are constant (see Proposition C.2).
The rest of the argument relies the bounds found in Proposition H.2, (I (Fpp), Proposition H.4 (Fac). Proposition H.3, (Jn). and Proposition H.5 (Kpp).
BB < Mo. for some Mo: First, we have that (pp S C. -B Kpp (Proposition H.5) and Fac(r) S Co x 1 (rp()) (Proposition H.4) for some constant Co > 0. The constant Mo is where the asymptotic of Kpp starts to apply.
Mo S Br < Mr, for some Mo and for all M1 > Mo: We see that (7 > (1BBr)-(443/))11/00) as B > in this phase. Thus, using Proposition H.2 and Proposition H.5, we have that Fpp S Ct x (pp((r for some C > A quick computation shows that (ro(r) < (T).
Mj S Brr S Myddn, for any Mj and some M2: The My the smallest of the two endpoints for the asymptotics of Kyp and Fac- As in the previous regime, we have that 1 7B (pp(rr S (r). In this region, Foe(r) x 1-1p-141/(20) and (rp x r 2+1/(2o), We see at BBr = -2a that Br S (d2a)-1 d2-2 S d as 2a > 1. Therefore, at (r = Lea Kpp (r) S Fae(r) and started, i.c., when Mi with Fac & (r) Therefore, must change this regime to
30

---

being Fac dominate.
M2daa 1 By for all M2: In this case, all terms are bounded above by Fo(r).
As consequence of the argument above, we know that
(r)()), if BBr Do
P(r)
Fac(r), if Do S 1r I D1 for some Do, D1 that depend on d. Br 2 D1
(66)
Fo(r),
C.4.2 Below the high-dimensional line (Phases IVa, IVb, lb, Ic)
One of the main differences between the previous regime and this regime that V can not be taken independent of d. As result, we call this below the high-dimensional line and it is precisely bounded by whether 2a is summable or not.
The four main characteristics of this regime are:
learning rate y scales like u -1++2a
SGD loss, i.e., (0,)) self-concentrates;
U can not be too large, i.e., d and v are proportional;
batch can be large (i.e., BB < 1) since the learning rate is small (y ~ 1422)
2a In Phases IV, Ib, and Ic, because j-2a is not summable, the summation of the depends on the dimension v. Thus, the kernel norm is
|
v² 1-2a
2(1 2a)
==1
where the learning rate y is chosen so that ||] is constant, i.e., 7
where 7 > 0 a constant.
Phase IV, (2/3 > 1, < < })) this phase, we have the following
limiting value of the loss that SGD converges to is unaffected by 8;
pure point forcing function plays role;
absolutely continuous part of the spectrum does not contribute to the forcing function;
SGD noise affeett the loss curves.
In this phase, the loss curve is
P(r) x Fpp(r) Fo(r) - 7/ Kpp
The following gives the precise statement.
Proposition C.6 (Phase IV: 23 > 1, 1 < < 1)) Suppose 23 > 1 and a Suppose the learning rate y and batch B satisfy at most half the convergence threshold Proposition C.2. Then there exists an M > 0 large and constants C = C(a, 8, M) and e c(a, 3)M, independent of d, so that for all admissible v and d, for BBr > M
c x (Fpp(r) + Fo(r) + (p) S P(r) S SC (F Fo(r) + 7B (r)
(67)
Proof. By Theorem C.I, we know that it suffices to look the forcing function F and kernel function K. Moreover, in this regime, we have that y decreases like 220-1 I (see Proposition C.2).
The rest of the argument relies the bounds found in Proposition H.2, (F (Fpp), Proposition H.4 (F
Proposition H.3, (Fo), and Proposition H.5 (Kpp).
We first note there is no (ro(r) S Fo and therefore it is too small contribute.
31

---

yBr I Mo. for some Mp: First, we have that BB Kp (r) I Co x F pp((r) for some constant Co >> 0. The constant Mo is where the asymptotic of J pp starts apply.
Mo V 7Br < M1. for some Mo and for all M1 > Mo: We see that ( 2+1/(2m) <
(r:rr) (133))((++)))++1(((a))) since x d and 2a < in this phase. Thus, using Proposition H.2 and Proposition H.5, we have that 1 pp)) S C1 pp for some C1 > 0.
Mi S yBr & M2d for any M1 and some M2: The M2 is the smallest of the two endpoints for the asymptoties of Kpp and F ppp. In this region, (pp(r) x (r:Br)
and Y x BB (r)r x x (r 2+1/(2a) x da-i x (r 2+ 2+1/(22). We see at r = d that daa- (2a-1(22))) (n d= 1-1 2 d 2-20 (d2n)_//o, Thus pp((r) X
1 (p)()) and we started, i.e., when == M1 with (p)(r) x 9 (r)... Therefore, we must change in this regime to being Kpp dominate.
7B"
M2da < for all M2: this case, all terms are bounded above by Fo(r).
As consequence of the argument above, we know that
g (pp(r), 78 (pp (r),
if yr - Do
P(r) ~
if Do S BBr S D1 for some Do. D1 that depend on d.
(68)
Fo(r).
Br 2 D1
Phase lb, (23 < 1.2.5 < < < 0.5, 2(a + B) > 1). Phase la, Ib, and Ic are quite similar as the dynamics of SGD only depend on the foreing function pure point and limiting value. In this phase, the learning rate y is dimension dependent, unlike Phase la, and the following hold
limiting value of the loss that SGD converges is d d-2a++-28;
absolutely continuous part of the spectrum does not contribute to the forcing function;
SGD noise not does affect the loss curves.
In this phase, the loss curve is
P(r) x x (r) + Fr(r).
Although did not prove the statement for < 0.25 function, we believe that statement still holds. We believe that the kernel function stops becoming power law when 0.25, but the forcing function is still power law.
do not have estimates for the kernel
The following gives the precise statement.
<a< 2. 2(a + 3) 1). Suppose 23 1, 2( 3) Proposition C.7 (Phase lb: 23 < 1, <a
and 1 < 1. Suppose the learning rate n and batch B 0 satisfy most half the convergence threshold in Proposition C.2. Then there exists an M > 0 large and constants C' = C(a, B, M) and c = ca, M), independent of d, so that for all admissible u and d, for all BBrr M
CX (F (F) + Fo(r)) I P(r) C (Fpp(r) ( Fo((r).
(69)
Proof. By Theorem C.I, we know that it suffices to look at the forcing function F and kernel function K. Morcover, in this regime, we have that 7 decreases like d (see Proposition C.2).
The rest of the argument relies on the bounds found in Proposition H.2, (Fpp), Proposition H.4 (Fac). Proposition H.3, (Fo), and Proposition H.5 (Kpp).
We first note there is no Fr.
y BBr S Mo. for some Mo: First, we have that 1 7B (p) S Co x (p)(r) for some constant Co > 0. The constant Mo is where the asymptotic of Fpp starts to apply.
Mo I 7Br S ddd any Mo and some Mi; The Mi is the smallest of the two endpoints for the asymptoties of Kyp and F Fpp. In this region, Frp(r) (2BB))((4//))+12220) and
? (r) 7 x (rBr) 22+1/(2a))
d (7Br) (7BBr)2411((aa) 2+1/((2), We see at r dea that
da (yBr)- d1 s d22 (d/a)-B/a Thus (r) S Fpp (r) and we started, i.c., when
32

---

r == M1 with Kpp(r) & ppp(r). Therefore, Ppp must dominate.
Mida Br for all M1 In this case, all terms are bounded above by Fo(r).
We expect Prop. C.7 to hold with the same conclusions for 2/3 2a 1, and 2(a B) 1.
As consequence of the argument above, we know that
I (rp(r), [o(r),
if Br Do BB 2 Do
P(r)
for some Do that depends on d.
(70)
Phase Ic, (2 > 1,0 a J.
<
Lastly, consider Phase Ic, which is similar to Phases la and Ib.
The following holds in this phase.
limiting value of the loss that SGD converges is d d-2a+1125,
absolutely continuous part of the spectrum does not contribute to the forcing function;
SGD noise not does affect the loss curves.
In this phase, the loss curve is
P(r) = (p(rr + Fo().
Under the assumption that Theorem C.1 holds for
1/4, we get the following.
Proposition C.8 (Phase Ic: 28 > 1, 0 < a < 1)). Suppose 25 > and < a < 1 and
Theorem C.I holds. Suppose the learning rate " and batch B > O satisfy at most half the convergence threshold in Proposition C.2. Then there exists an M > 0 large and constants C = C(a, B, M) and c(a, B, M). independent of d, that for all admissible and d, for all ,Br M
C CX (Fpp + Fo(r)) S {(() s C' x (rpp(r)+ + +Fo(r))
(71)
We can not prove this statement as we do not have sharp bounds on the kernel function in this region. We believe that the kernel function stops becoming power law, but the foreing function is still power law. Thus, it should become even more forcing function dominate.
We believe the loss follows similar behavior to Phase la and Phase Ib, that is,
(r), BB < Do P(r) ~ Fol(),
for some Do that depends on d.
(72)
if yr 2 Du
D Compute-optimal curves
Throughout this section, consider the deterministic equivalent loss function P(r) Prr d). Moreover as batch size B is order 1, it only effects the compute-optima curves by a constant. Therefore, we set B 1. For each iteration r, the SGD costs d flops, equivalently r/d flops, The goal is to find the optimal compute line as a function of the number of flops f:
min (4..)) d).
d' (f) def arg min, P(I, d), the optimal compute line is precisely P(a-( d' df)).
To do this, we simplify the loss curve P( [ d). While is possible to minimize this a function of an alternative function considered is the following
p(r, d) def (rp d) Fae(r, d) V (r,, (r,
(73)
which achieves the right power law behavior as the true compute-optimal curve and deviates from this true curve by an absolutely constant (independent of d, f) (see Theorem C. Note here some of the terms should be taken when not defined for the different phases.
Using this alternative loss function, P(rr, d), the compute-optimal line must occur at one of the corner points, i.e., where any pair of functions equal each other. The following lemma gives a useful characterization of these points.
33

---

Table 6: Summary of the compute-optinal curves for Pig d) for above the high-dimensional line, 2a > 1. This includes Phases Ia, II, and III.
Trade off
Compute-optimal Curves
Phase Ia (Prop. D.1)
Pease ia (f) pl2at1 -1) (1+8/o-1/(2a)
Fpp - Fo
d'nise x ff/2241))
2or
Phase II (Prop. D.2)
3pp Fac
Pr Pease (f) 1 2(a+8)
dphise X (18/a)/1++B/a
Phase III (Prop. D.3)
F Plase m (f) x ((1-da)((1a)
1 Kyy pp = Fac
dhhsse III fl/2
Lemma D.1. Suppose Co, e₁ > 0 are constants and yo: 7/1 Po.PP. > 0 exponents such that a function P(r, d) equals
P(r, d) max {Cor 7o ed
Then replacing d' def arg min, (P) (e:
+ 4 the minimizer in d satisfies
and the optimal value is
min P(f, d) Co 70 (P
Proof. The proof is straightforward computation. The minimizer of P(f, d) in d must occur where the two terms in the maximum are equal, i.e.,
Co ( 2 po Ci( - Pt
PP
Solving for this d gives d". Plugging in the value of d' into P(f d) gives the optimal value.
Remark D.1. The possible minimal values of (73), i.e. where pairs of functions in the max are equal, can be reduced further. For instance, if I Faclr, d) exist for the phase, then for some O < < r2
F (p)(r, nB Kpp(r.
0 S To
J(r, d) =
To < r S m
(r,
< 72 T2
Fo(r,d),
Thus, there only maximum of three points to check in order find the optimal compute curve. Remark D.2. In view of Lemma D.1, to find the optimal compute curves, we first find the potential curves (i.e,, all the possible combinations of two functions in the loss curve are equal while still lying on the loss curve). Then the curve which has the smallest exponent on the flops, f, is the optimal compute curve.
D.1 Compute-optimal curves: Above the high-dimensional line (Phases Ia, II, III).
To ease notation, we introduce several constants that will be used only in this Section D.1:
Fym (po(r, d) x (r -1+ (11B/)+11(22) 1 K yB (r, (r, d)
Fao d) x d d' (r
Br)
1212 (r2r)-2+1/22a)
and Fo(r, d) d 20x
where the asymptotics only hold in specific regions of the space of Br. For additional details on the derivation of these asymptotics and the constraints on BBr where asymptotics hold, see Section H.
Remark D.3. The constants in the asymptotics are dimension independent and only depend on a, B.
The compute-optimal curves are summarized in Table 6.
34

---

D.1.1
Phase la
In this case, the approximate loss curve is given by
3(5.c) d) ma (5, d), Fo d)} = max (ax((()) -1+4//44+1122)
.x xd 20-2a++-220
(74)
With this, we give a description of the optimal compute curve.
Proposition D.1 (Phase la: Compute-optimal Curve). Suppose we are in Phase la, that is, 23 < 1 and 2o > The compute-optimal curve using P(2.d) in (74) occurs when Fpp (2p(2.0) d) Fo d). Precisely, the optimal d' which minimizes P( d) is
Eprase x fl f1/120+1)
and the compitte-ptiinal curve is
1 Phase (f) x (Z00II (220+T1))(44//00001111
Proof. We apply Lemma D.1 with
Cu = 1, 7o = - 3//a 10---14 1/(2a), = 0
and C1 = 1, n1 0,
p1 = 2a 23..3
D.1.2 Phase II
In this case, the approximate loss curve has three terms (Proposition C.4 with (63))
((4.4) d) max (Fppld, d). Fac (1 d), Fo ())
(75)
max {(2) (148/00441/220) (1) -1+1/(20) x dd [d-3
Proposition D.2 (Phase II: Compute-optimal Curve). Suppose we are in Phase II, that is, 2,3 > 1, 2a > 1, and B < a. The compute-optimal curve using P(Z,d, d) in (75) occurs when T Fppl (2: d) = (2 d). Precisely, the optimal d' which minimizes (( is
d'rrae 11 x {(B/a)/(++2/a)
and the compute-optimal curve
2a-+2881
Jor
Ph u
x
2(a+B)
Proof. Using the Remark D.2 after Lemma D.1 and Proposition C.4 with (63), we only need to check two intersections: Fpp = Fac and Fac = Fo. The curve which has the smallest (i.e., largest negative) exponent (i.e, steepest curve on log-log plot) is the compute-optine curve.
Case 1: Consider F (pp( d) Fac (1 d). We apply Lemma D.1 with
Cn 1, 70 1 3/a 1/(2a), Po
and e, = 1, = 1/(2a), = 1
to get that the minimum
di (B//a)((++3/a)
and the optimal value is
2a-22-1 2(a+B)
()(() x
Case 2: Consider Facl (,, Fold, d). As before, we apply Lemma D.1 with
Co 1,
T0 0, Po = 2a
and e, = 1, 71 11111/(2)) =
35

---

to get that the minimum is and the optimal value is One can check that
d2 x f1/(2a+1)
(f( x x (-22a/(aat))
2a + 2,3
-2a
for all 23 > 1, 1,,,>188555 <a.
2(a + ()
2a + +1'
Therefore, Case is the optimal overall.
D.1.3 Phase III
In this case, the approximate loss curve has three terms (Proposition C.5 with (66))
P( d) max Xpp d. d), Fac d), Fo d)}
(76)
{1) 12
(2) -1+1/(2))) x d= d
Proposition D.3 (Phase III: Compute-optimal Curve). Suppose we are Phase III, that is, 23 > 2a > 1, and B > a. The compute-optimad curve using P 2 d) in (76) occurs when yB Kpp d) =
F d). Precisely, the optimal d' which minimizes P is
d'phase III
f2/2
and the compute-optimal curve is
Ipr Phose i (f) g() (1)44)/(4a).
Proof. Using the Remark D.2 after Lemma D.1 and Proposition C.5 with (66), we only need to check two curves: Kp Fac and F Fo. The curve which has the smallest (i.e., largest negative) exponent (i.e, steepest curve on a loog-log plot) is the compute-optimal curve.
Case 1: Consider Fac(d, d) Fo( d). We did this for Phase II in the proof of Proposition D.2. Thus, we have
Co 1,
To 00 Po = 2a
and e1 = 1, = - 1--1-11 1/(2a), =
to get that the minimum is
di x p/(22+11
and the optimal value is Case 2: Consider 1
(f( x 1f 22201(2a+))
7B 7Bx Xppl () = - d). We apply Lemma D.1 with
En L, 70 1/(2a), Po
and e₁ = 1, = - 1/(2x), =
to get that the minimum is and the optimal value is One can check that Therefore, Case is the optimal overall.
d3 8112
Pt(() (1122a/
1-4a 4a
-2a
for all 23 > 1, 2a > 1. B > a
4a
2a
+ 1'
36

---

Table 7: Summary of the compute-optinal curves for P d) for below the high- dimensional line, 2a < 1. This includes Phases IV, Ib, and Ic.
Trade off
Compute-optimal Curves
Phase IVa (Prop. D.4)
P Phase IVa ( x f
1 Kpp = Fo
yB
Phasc IV = f1/2
Po
Phase lvb (f)
Phase IVb (Prop. D.5)
1 Kpp Fyp 7B
Phase IVb x -
Phase Ib (Prop. D.6)
Pr Phase Ib (f) x p1/2-00-
3pp = F0
dhase tb x fl122
a(2a+28-1)
Phase Ic (Prop. D.7)
Pr Phase to (f) x f)
Jpp = Fo
1-2(a
Phaso x 2(a(23-3)-20+1)
D.2
Compute-optimal curves: Below the high-dimensional line (Phase IV, Ib, Ic), 2a
This section main distinction with above the high-dimensional line section is the dependency of the learning rate on v. In deed, we have that v/d + c (0, 20) and the learning rate is chosen so that the kernel norm is constant, i.e.,
7 2(1 2a]||[[[l
22a-1
where y is the positive constant so that = fy x 22a-1. Consequently, we also need to keep track of the learning rate in the various terms.
In this section, we assume that v/d - E (1, 00) as u, 0o.
We state for completeness the d and r dependency on the forcing and kernel function, including the learning rate 7. We note that these asymptoties only hold for a set of Br values which depend on the spectral properties of K (see the propositions listed next to the terms for details).
F (r) x (7 x r) (1+8/00+11120)
22 dio-1
-(1+8/a)+1/(20) (daa-1 (133(44)))41//2a))
x (d 2- r) -) (1+8//)+11/20 (see Proposition H.2)
V2a-1 -1+1/(2g)
1 K Kpp (r) x 7 1+1/(2a) x x--1/1
(5
x 2211/(2a) x xr 2241/(22)
BB
d
x d² f 2a x - - (see Proposition H.5)
Fo(r) x (0 1 122a22)) x (2/(2))) 2ax 23)
* 1-1)(2))
mmx (0.1 2.9
d 2a max//0001122
11(22))
20 + max (0.1 1 23)
(see Proposition H.3)
D.2.1 Phase IV (a) and (b)
In these cases, the approximation loss curve is given by (Proposition C.6 with (68))
P(f. d) x max pp 1. d), 1 K (1. d), Fo d)}
max (1) (1+ (1+8//)++1 x dB0--D(-14-000+11220
(77)
2-1/ 20 (!) 12x) d 2a].
As one crosses the 2a 1, line the Fac disappears and F pp emerges. Consequently, there leaves two possible corners where the compute-optimal value could oceur at. When a goes below a = 1/4, the Kpp decreases.
37

---

The difference between IVa and IVb is simply where the compute-opiimal occurs, In IVa, the tradeoff occurs between pp and Fo, whereas in IVb, the tradeoff occurs pp and Xpp
We give the compute-optimal curve for Phase IVa.
Proposition D.4 (Phase IVa Compute-optimal Curve). Suppose we are in Phase IVa, that is, 23 and -²-1 d2-2aJK pp d) Fold. f, d). Precisely, the optimal d' which minimizes P (
z. The compute-optimal curve using PP d) in (77) occurs when
V2
d'phare IVee x gL/2
and the compute-optimal curve is
Plaaee
Phase IV (f) x x
Using the Remark D.2 after Lemma D.1 and Proposition C.6 with (68), we only need check two curves: Fpp = d2-2a x Xpp and d'-2a x Kpp = To- The curve which has the smallest (i.e., largest negative) exponent (i.e, steepest curve on log-log plot) is the compute-optimat curve.
Proof.
Case 1: Consider Tpp L. d) (2-2aX (2 d). We apply Lemma D.I with
Co- = 1, = - 3/a 1/(2a), Po = (2a - 1) + 3/a - 1/(aa))
and
e1 1, 71 1/(2a), Pi - 12((((a)) + 20,
to get that the minimum is and the optimal value is
di x plo aa--ppp (2000)((208+0022))
(f)
Cypp
ErSpe Cpp
(1 (1-aa (1==))2c420-111(004000---3- x g(t
Case 2: Consider d= 22xK (g,c) d) = =Fold d). We apply Lemma D.1 with
Co 1, To 0, Po 2a
and 11
2 1/(2a),
pt - + 1/(2a) + 20.
get that the minimum is and the optimal value is In this region of a's and I's, Case 2 has smaller exponent on than in Case
di x x2/2
x1
As for Phase IVb, we have the following.
Proposition D.5 (Phase IVb:
Compute-optimal Curve). Suppose in Phase IVb, that is, The compute-optimal curve using PC d) (77) occurs when - 20 ( = cjJ vo d). Precisely, the optimal d' which minimizes P(L, d) is
2,3 and < a <
V2-1,
V2
d'paase IVb x (0=88//2aBtaa-2)
and the compute-optimal curve
got Phase IVb (f) p(2 (222202224+22-111222223
Proof. The computations are exactly the same as in Proposition D.4. For the a's and I in this region, we see that Case I has the smaller exponent on f than Case 2.
D
38

---

D.2.2 Phase lb
In this case, the approximate loss curve is given by (Proposition C.7 with (70))
P(d d) x max ( pp d), Fo
(78)
x max ((2) (1+-8)/ x ((a=I1(-0+8//H///00)) dd-2a+11220
Note this is true for 1/4, but expect this to hold without this extra assumption. With this, we give a description of the optimal compute curve.
Proposition D.6 (Phase lb: Compute-optimal Curve). Suppose we are in Phase Ib, that is, 2B < a < 2' and + > 1. The compute-optiner curve using P(g.d) d) in (78) occurs when ppp(2. d) = =Fo (5(2aa) d). Precisely, the optimal d' which minimizes P( d) is
2'
d'hase tb x f2,
and the compute-optimal curve
Pr
Phase 1o (f) = x2 18-8--8
Proof. We apply Lemma D.1 with
Co- = 1, 70 = + 3/a- 1 1/(aa)
Po = p2a - -
and C1 1, "1 0,
P1 2a 1828.
We expect the conclusions of Prop. D.6 to hold for the (a, 3) pairs where 23 < 1, 2a < 1, and 2(a + B) 1.
D.2.3
Phase Ic
In this case, the approximate loss curve is given by (Proposition C.8 with (72))
P(g. d) = max (3pp Fo d))
(79)
max (1) 1140/)) ([aa-MM--444//)+1((aa)) d d-2aj.
Note again that this is speculative believe that this is correct. With this, we give a description of the compute-optimal curve.
do not have the bounds for the kernel. However do
Proposition D.7 (Phase Ic: Compute-optimat Curve). Suppose we are Phase Ic, that is, 23 > and ( < a < and suppose (79) is true. The compute-optimal curve using P P(G,,)) d) in (77) occurs when F pp ( d)- Fo(3. d). Precisely, the optimal d' which minimizes T P(4,d)
1-2(a+8)
d'phase lc x 20(23-3)-2041
and the compute-optimal curve
a(2a+28-1)
T Phase te x -2)22)3)-22841
Proof. We apply Lemma D.I with
Co 1, no 1 B/a 1/(2a),
Po (2a - 1)(1 3/a 1/(2a))
and C₁ = 1,
71 = 0,
P1 = 2a.
39

---

Figure 6: Spectra of empirical and theory weighted by D1/2 3. Empirical spectra (blue) averaged over 100 ran- domly generated matrices W E Roxd Point mass at = 0 was manually re- moved. Theory (orange) computed us- ing the resolvent formula (9) and solved with Newton method (10 iterations for each 2; 2- e-values were spaced at 0.1d 20 with an imaginary part at d' dd-2). There is continuous part that evolves into a pure point outliers.
-lpha
umophiaa pani
1sad part
20 spo.ba inighted in D11ze hobbats
E Spectrum of K: random matrix theory
In this section, analyze the spectrum of = DI/2WWWTT DV/2, For this, standard tools from random matrix theory to derive a fixed point equation for the Stieljes transform of K. Indeed, by knowing the Stieljes transform of K, one can recover the spectral properties.
In partieular, will need the spectra of K decomposes into 3 parts:
1. Point mass 0: There will be point mass 0 of mass d for trivial reasons since v >> d.
2. Pure point outliers: There will be set of outliers, the pure point spectra, which are constant order and nearly equal to j- for j = 1,2,....
3. Absolutely continuous part: The spectral bulk, the absolutely continuous part, which form density on a shrinking window.
In fact, we will not need to give a complete picture about all the spectra.
E.1 Self-consistent approximation for (k- WD
In this section, we state the deterministic equivalent for the random matrix (R- (K-z)* -1= and give some properties of its "self-consistent spectra." The starting point for this is the self-consistent equation
1
m(=) 1 ビド=
where (D1/WWWTDX 12 2) j 2m2)
(80)
The identification <> can be made rigorous by showing that
[T(AA(D)?WW D2/2 =)- - Tr( 20ag(i-20mt 2: ()))
Pr
0,
d-+00
for deterministic sequences of test matices {A} with bounded nuclear norm and generally with very high probability in d. We note that would need more precise quantification of errors to be useful for establishing the scaling law for the actual random matrices. In Figure 6, we solve the theoretical spectrum by solving the fixed point equation for m=2) using a Newton method grid of complex z.
The function m can also be related to the trace of (R -)_ From the definition of m, we can derive the explicit representation theorem.
Lemma E. For any v, and z E with Im(m(2)) > 0
- + (1 m2))d
20m((2)
40

---

Proof. Multiplying through by 2 we should evaluate
2a m(2) 2
Adding and subtracting j-2mm m(z)
j= 20
11 m(2)
20 2am
-2
20 m(2) - j
j=1
j=1
Using the definition of m,
j j- (2) d
m((z) -
Substituting this in completes the proof.
While an explicit solution of m unavailable, we can derive many properties of m, starting with: Proposition E.1. Suppose X is real random variable compactly supported in [0, oc). For every E H {z E C Im > 0}. there unique solution of (80) satisfying Im m(z) Moreover, this solution is an analytic function, and it can be solved by iterating the fixed point map
(1
(m(x) : H!) +
1 :2 H
1
Xmi
initialized with m 1. Furthermore, if we consider the equation for 2 E H
F(m;z) def y
Xm 8mm=
1,
d
then this is solved uniquely by m(2) and moreover it is stable in that Fm F * 0 in neighborhood of the solution.
Proof. Let G be the mapping
G(m; 2) def
1+ E
Xm(=)=s
For each fixed z E Hi,, this is a strict self map into the lower half-plane of m. Self-maps are strict contractions in the hyperbolic metric (from the Schwarz-Pick lemma), and thus there is a unique solution of m=)) = G(m(z);z).
We now introduce F according to the formula
Xm
F(m; 2) = m +
Xm
so that F(m; =) = m/G(m; 2). Introduce the stability operator
Xx
OmF d
E
(Xm 2)2
Then we have
mdmG
Om
G By the Schwarz-Pick lemma (in the half-plane version), we have
G Imm G(m; Im ml
and hence in some sufficiently small neighborhood of G(m(2)) m()), we therefore have
Gl < 1.
Hence also, a sufficiently small neighborhood of m(2)
1- G.
G -
3m F m
40.
C2
G2
41

---

While this proposition does not state what happens on the real line, in regions of the line where m has finite, real-valued limit, agrees with its reflection in the lower half-plane, Hence in any open subset of IR where lim m(æ + in) exists and is real, m will be analytic.
From Proposition E. deriving the estimates on the forcing and kernel functions. We summarize these properties in the following:
derive some explicit estimates m, which will be sufficient for
Proposition E.2. Let X be any random variable with support in (0, 1]. Then the following hold:
1. Near 0: Suppose that a < 0 is a real-valued solution of
Xa
Xa - =1.
Then m is analytic in a neighborhood of 2 = and m(z) = az + +x22). furtherrrr if for some interval [0, 2o] the equation
Xa
+
E
Xa xt--1
=1
is solvable for a < 0, then m is analytic in a complex neighborhood of the whole interval
[0, zo].
2. Far away: Let uo(2) be the distance of [0, 1). Suppose that is such that 16 X s
eo(2)?. Then for some absolute constant 0,
[m(2) 1 < 8 v EX
d 20(2)
Moreover suppose that
E
X
S
7.. and suppose that
def
V
X2
V
X|2|
sup
E
$
and
sup
d
[Xm
2/2
d
[Xm
- 2/2
mi/m- |m
1| 2e
m: m
$2 ||
Then
X
X
m(2) - 1
EE'
28
E
X
X
We need a lemma on stability of solutions.
Lemma F.2. Suppose an analytic map of - C, Suppose there a e, 8 > 0 and mo - so that for all m -HI with [m mal & and < Im mob
00m Fm,, 2)1 2 <> 0
If my is an approximate solution of F F(m)
that satisfies
F ((mo)) < co,
then there is an solution m E -lil with F(m) = 1 so |m - mg! <
Proof. We introduce ODE (which is the continuous limit of the damped Newton's 's method)
dm; - F(m) where melc=o mo-
dt Om (m))
Then we note that along this ODE
d(1 ((1-Fi) F(m)) 8m F (m:)) dt
dm: -(1 F(m,, 2)).
dt
Hence we have (1- (mm))) = (1 - F(ma))e= for however long the ODE exists. In particular, we have that on some open set of admissible m containing ma that
10 Fmm) 2
42

---

then provided the ODE does not exit U,
m mal
|mae mol - [11 F(mo)) e /c- (11 F(ma))l/e.
Hence there is a neighborhood of mn of size d on which 8m F (m))] 2 e then [(1 F(mo, < eó we have
m - [1 F(mo, 2))l/c= 8.
Proof of Proposition. Part 1, Near O: For the component near 0, we consider a change of variables and look at g(2) = m22)/2 which is therefore the unique solution the fixed point equation:
F(a(=), 2) = 29()) y
Xq(=) Xx(=)
Then by hypothesis, we have solution solution to neighborhood of (a, 0), and so it would suffice to know that the differential equation
0 given by F(a, 0) 1. We wish to continue this
dy d=
FgF 2)
has a solution in a neighborhood of the point. Solving for the derivative of g,
dg -9
X where 0gF(g.2) = d (Xg(z) 1)2
" E
dz
a, (q.)))
We note that if we solve the equation along the real line, then g stays vallev. Furthermore, for all q with g < O have
0 Fl 2) = = v
X
(Xq(2)
By analyticity, we can extend this solution into a neighborhood in the upper half plane and on an interval of the real line where this solvable. Hence m is analytic in this neighborhood and has boundary values given by m(=)/= a.
Part 2, Far away: For the other parts, we use that m is the solution of
Xm(=) Xm(z) - 1.
F(m(z), = m(z)
Hence we have
Xm(z)
dm
-m,F(m,2) -
(Xm())-2}²
dz 0mL(m;2) 1- E
Xs
(Xm(=)-=)²
Define distance
fe(z) = == inn()==mf[[[mmm 2| Im - 1/ 6, X. [0,
Provided that |m- 1/ < 5 and (EXX) - e(2)2/2 (which is trivially satisfied if (BX)/o(()) ))
dm
E(X)
< 2
dz
e(z)²
For any with g(2) > O, we can find unit speed geodesic (t) connecting to co so that g(a(t)) e(2) & (this will just straight line). Then along this geodesic, g (())))a( (1) since
((EX))o(() < [E ({=++)))+ < {[xx)(= < (0t)){((H//(0))))>000))))+
Hence along the geodesic, and provided that |m - 1| S 6, we conclude
dm dz (ot))
E(X)
< 2(1 + 5) (e(z) + 1)2
43

---

Integrating along this line segment from infinity, we conclude that provided the right hand side is less than 6,
1 dm dz (o(t)) dt - 2(1 + d
EX
m(z) -
JU
For the second conclusion, we Lemma F.2 with this F (holding fixed). We let mo 1 (X [x-s) ), and we consider an 2c neighborhood of 1, 4 By assumption, on L
v
X2
Om Fm, 2)
d 1B
(Xm(z>= - x)²
satisfies 10m F 2 3. 4'
We also have that
X² mo) [ - F(mo: 2)1 = d (Xmolz) - (x - 2)
Hence applying Bauchy-Schwarr
[1 F Fm 2)1 S [1 mpl6 cd.
The conclusion now follows from Lemma E.2.
F,2 The region near and the spectral bulk
We now bound the contribution of the region near O.
Proposition E.3. The function ml()) is analytic in a neighborhood of = 0 of radius c(a)dd 20 for some c(a) >> O. Furthermore, is negative on (0, cd) vanishes at O, and has |m (m'(0) + k(v/dydka Cdpa-1 for all d sufficiently large where
forr
gold kd
k(v/d)
solves
1.
+ x2a
Moreover, we introduce [zz V/d) where J : TH - -T which solves
f(z;a) f0 f(=;a) dr
1.
[(z;u) 20x 222
This extends analyfically to the interval [0, c). Then f and m are close in that for any compact subset K C. (C ([c, [oo,,)))) we have
[m(2d 2n) - [(z)] S C(K)/a
We furthermore have that in the case 233 < 1
j 2a 29
28 dr
11-23
SC(K),
m2dddddd-dm (2d 20
2d
0 f(2) 20
and in the case 2,3 >
22-23
C3 f(z)
<((K)d
j 2mm (and2222) 2d
2a
Proof. For the first part, we look to apply Proposition E.2 part 1. The equation we need to solve is
2a a
-za +
1,
20
1=1
for < O. We change variables by setting -fa and d-2a, in terms of which
2n x (j/d)-2nx
+
1.
(81)
(j/d) -20
44

---

By monotonicity. for x positive,
J
v/d
xdx
(j/d) (id) 2a x+1
w/d
x
1/8 x 12a
+ x2a
and moreover the lower bound is only less than the upper bound by at most the case that 2x < can bound for x [0,1]
uniformly in x > 0. In
x 1 (v/d)20 3 1ndd x
(w/d)
(v/d)1-2a
x S 1 2ax
Hence there there is interval [0, co) (bounded solely in terms of (v/d)) which (81) is solvable and is uniformly bounded away from O over all d. Hence, the solution of k of pa/d sd xtrla
1
satisfies
(j/d)
El 1 d
(/d) 2a 2xx
j=1
Following the same bounds on (81) with 0 satisfies x K| In the that 2x
///d
shown above, we conclude that the true solution x of (1/d). This concludes the proof when 2a < 1.
di
K
1,
w/d
dx
1
x x
dx
x + 20
x
220
1 ++220
On the other hand for x E
[0, 1]
o/d
x + 22 2 x x2/(2a)
x
(v/d)xx 1/(20)
+ x2 2 2/(22)
dæ
((//a) dx Jo
+ 20
and hence once more there is an interval [0, col independent of V/d on which this is solvable and morcover the conclusions now follow in the same way as in the case that 2a < 1.
Convergence The existence and uniqueness of f follows from Proposition E.I, where define
2(f:2) del f+ 1 f f 222
f =
(making appropriate choices of u/d and X).
We further have, from the previous part, that f takes negative values on an the interval (0, c). In what follows we fix a compact set K C (C') (Ic, [-,00))))) Further, we claim the stability operator
0, = /-- ((2;a)=x200
x 20 dr
nonvanishing on K in a neighborhood of f. Off of the real line, this follows from Proposition E. On the real line, it follows from monotonicity of F for f < O.
Hence it follows that on K, there is constant C(K) and 6, 0 so that if K and m satisfies
[F(m; 2) - 1 < 80.
then
mm - [(5]( 2)
Define
j j-2a-3 2-2--2 23
S(m; 2) def
2a m 2d 2a
==1
Then with / =
1
j-2a
2 5(m; 2, 0)
Σ
7
j
20mm
zd
j=1
45

---

We will define = v/d, and we will define A as the separation
def
min mmin(t E [0, (u/d)²a) |m - zt }.1}
Then by bounding the emrors in trapezoid rule approximation
/ m zz
dr
(m; 2,0)
d
d
where we have used bound on the derivative of the integrand
|z|20z dæ
m 2x22
A
(which relies on z being bounded away from 0 and on being bounded in modulus). Hence m(zd-22 20) is the solution of
m + d S(m; 2, 0) = 1
then we have
m /"
m dx
mld-1 m)
[F(m; =) -
mn
2z.a 20
provided m is bounded.
To see that m remains bounded, we let On F be the stability operator of the equation
1 = Fmm; 2) m + m
S(m; 2, 2).
d
Then once more
F d s(m,;,0)) Om S(m;
Approximating the sum for Sm.
m
Fm 2) Fm 2)1 E d=
A
A3
Differentiating the fixed point equation, we have the differential equation for
dm m 1 3m (m;;)) Om F(m; 2)
d=
As the same equation holds for f and is non-degenerate in neighborhood of f (as the stability operator does not vanish in a neighborhood of the solution), we conclude that
dm ((ad-2a)
d-1
O(1) and [F(m; 2) 1/ A(m)
uniformly on compact sets for all d sufficiently large
Sum formula. Hence having approximated f, we can turn estimating 5mm;,,3 3). When 23 we may repeat the Riemann sum approximation argument. Specifically, we have
23 dx 10- m zz2a
23 2 5mm; 2, B)
d
where to bound the errors, must estimate
229-1 S"
x 2a 29
dæ S d28-1 /"
x 2a 28-22-1- 28-1
x 4a 42-28-1111 28-1 m
dx.
dr x 20 zd
x 22 zd-
(x 20m =dd 2012
Setting wd. arrive
/0
x 20 dr
< d ra
())
w 288-1
w 22 2 mm
23 10-ss(m;,,)))
(m 20 )2 dr
m 222a
(1/d)
m
2a
[m]
+
2
46

---

π We may subsequently replace in this expression m by f. In the that 2,3 1, subtract from the divergence caf //m and then express
j 20-23
j j-20- 2--28
(m: 2, 2) 1/m
20
2
2d-2n 2n
j 20m
j=l
Bounding the difference leads to
[S(m; 2, - - 2 cgd / + d²-20 10-22//ml
Remark E.1. There is an exactly solvable case where even more can be said. Note that when 20 >> and t/d oc, the equation for becomes
f dæ
f+
1.
f f- x2az
Changing variables (which requires a contour deformation which restricts the branches considered) by letting 2a - - so that x (-112)² Then
f [+(-1/=) lo
dx
1
Hence with co -Jo0 I have that is the solution of
+ (-
If for example a 1, then with = (-) we have satisfies the quadratic equation
9² gz 1/2 1/2c1 =,
solving
g= z 1/2 11/2g
2 1/4-114-1,
with + chosen so that Im g 2 and Re g > 0. We note that 6₁ and conclude that
1
f = 1 (T/4)²
with the branch chosen to ensure Im f < 0 when Im 2 >
E.3 The mesoscopic region
We will need the following technical estimate sums over lattice points. Lemma E.3. Suppose that and complex numbers and -z/w Z
cot cot(TTz/w).
(82)
w
Moreover, if we suppose Im(2//w) 2 Re(z/w) then there is aboslute constant C > 0 so that for any N
N
C 2
pv
<
Wn +
WT +
|
Proof. Note that we may remove factor 1 from all statements and instead look at the case (with
y z//w)
pv
pv
um +
2
W
72
47

---

Then by residue computation (applied to the function π cot( (T2) z-w
pv
=
cot(TT) = π
cot(T2/Ww)
11 w
where we have used that cot is odd. Now by pairing terms, we have
Σ
WT
10n +
11 +
n=
N
n=N +1
Making a common fraction, we have
N
2z
pv
+
(wn)² 22
n=-N N
N
2z
-n2
(z/w)²
R=N+1
Now Re(z/w)² < O, and hence the claim follows.
Proposition E.4. Let a, 3 2 0 with neither equal to We further assume 2a + B + 2. For U, a, consider with
ib
A+iB Σ
in + j 20 m
for real A, B. We suppose that the b, u, and satisfy
1. 1 al 2
2. + ub < e'u
3. 0 0. b,
4. log log(1/e)u² 2 S cn.
5. 17 cu,
6. 0 u ucc.
Then there is an en > 0, O, and C> O so that if E (0, <o) such that
2(u/a))/a-1/220
(1 ub)u--260 22
20a
CB a
0a+
2 2a. 2/3)
0 EU 8/a-1/(2a) + c + b)u log (l/u) + E0a+0 (n + ub)u 1 12 20c 28
where 03 = E 28 ( > 1/ or ca = 0 otherwise and where 0a-3 is the indicator function of
a+ 3 < 2. Furthermore, let A A(u + in)) be the same with 1. Then
A - A < C al 1 1//0//111200 + cs + Oa+BE
11 1-2a--24
and moreover
1-220 203
5 11/001/(20) + +cg + Oat0 u
Proof. We look to estimate the expression
j j-2o 2a--23 288
A+iB
11
in) J 20 20
j=1
48

---

on the regime considered, where m a - ib. The dominant contribution of the sum will either come from j --2a a = u or possibly, when 23 1, from small j. So the analysis will be done by separately considering windows around the transition window j- a R and another analysis for large/small j. We use the notation for C (1,2,... f) that A, and By are the restrictions of this sum to the range of j E T.
The transition window. We begin by setting jo to be the integer which minimizes 100 2a a w/- We estimate this difference, noting that
2 a u| v max 10 (jo 1) |a] = C(a)s 2a - C(a))u
(83)
We can estimate j j- by Taylor approximation, giving
2a-1 j = jo 20 2a(j - jo)jo 20 + O(j - 30) 20-
Now we divide j according to whether
(j6 a -
jaa-j-aa 20 a)² S M(n+ + 1o 20
or if not, for large M Mc) = 1/e². Let I the largest possible symmetric interval of j around jo that satisfies the above display.
On this interval, we would like to justify that the Taylor approximation holds. For this, we shall require that /M + ju 20 S c. Note under this condition
- j - jol + -((--oo) jo x Lio 20 - j-
20 20 S V 2)) nm Se.
Thus the largest difference of زا jul on I is bounded above, up to constants, by VM(n + ub)u 12-1((2))), Hence the Taylor approximation is justified in that on I
1i- ju 2 (2a) - -jol ( + 11 (1-1000 O(e),,
with the implied constants bounded in terms of [1 - al and c. It follows that for terms outside of I, we have (Jo (n a - j- a)² > (n + jo z for some absolute c' (provided c(a) was picked sufficiently small).
The contribution of I terms now follows the same path as was done in the first case:
j-2a 28
j-28
Σ JEL
Σ
ib) (u + in + jo) 2a 12)) +
2b (u+ in)
JEI
The error terms ε1 are bounded by
in)
2a 2a-215 jj- (b+ )=
jol2
(n) + ub)3
L $ Jo 28
z
(b (b+
jET
< M (n + //
We then do second replacement, freezing the j-23
29 in the numerator, and so we need to estimate
j-28 jo 2,
JET (a - ib) (u (i)
18 + (j 10-000 2a 22)
which we do simply by
|j 1 jul2
1 S Jo
21-1
max jer
b b+ n/u
< M + ub)
Thus with M x 1/e" and using the second assumption of the lemma, we get
1g + K2 S 1/
where we have expressed
j-2a- 22-2- 28
Jo 22
2 = a ib - (u + in) 20x
+11 E2
where
jel (a- (b)j 22
(u in)
+ w(j jo)
w = (u + +in)j0 2a- 1
jel
49

---

The sum we can now evaluate using Lemma E.3. Note this makes nearly -i(b n/2i+ and w nearly (22)) (2a), and hence z/w is almost purely imaginary. Thus the error estimate in the Lemma applies and we have (using (17 + bu))-llljaa 1/200) 2 log(1/c) and nj < cu)
j 2a--29 29
i 9/a 1/(2a)
Σ
S Ceu (/
(a =b)j 20 in+ JET
2a
The small regime, imaginary part. Recall the terms of small j. which is say those with j less than those in I, are denoted S. For these terms, have j-2a ev MMn + ub). For the real and imaginary parts of the sum we have
20- 28
2-22-2 (-u + i(n + j j-) (-u+j + (1 + b²)
As iBs
Σ
jES -ut
20 i(n j j-bb)
jES
We shall focus the imaginary part first. We introduce approximation for this sum, coming from approximating the denominator by d2. Thus we introduce
def 20 23 ( iB's
a²
JES
Let ca be in the statement of the Proposition. Then
BB's (ibb/a²)) 2 Ju
- 14 |/ + 3o (b) S 3/a-1/222
We turn to estimating the difference of Bs - iB's. Using that (j-2 (-u+t-z0 j-20 s 2ulj a), we can estimate
uj (1 2ab) (-u+ j 2
Bs B'yl S
jES
To estimate these differences, we break these sums into scales. We let Sy to be those j for which
S {n7 + ub)2*-1 S aa S (1 + ub)2*}.
Then estimate the number of terms in each of these k by
S < C(a)(1 + ub)2 (u+ (n + =b)22)-1112 11-1/220)
For small k i.e. those for which ub)+* I u. we can estimate |S S +())0) Call the small & terms S" and the remainder S" Then for larger S" terms,
| S C(a) + ub))2)-11(220)
For the difference of the imaginary parts on small k. we may bound j 22 as a multiple of jo -- and so we arrive at
1SA (n + ub)
Bs B'rl S (u (/3/1)))
21 + ub)? S (12/o-1/(20)
Σ 2h S 1/1122 1/(20)
Then for the difference of the imaginary parts on large k
[Sa((1((n + ub)2* f/a b((1 + 2b 8/a+11)
BSr - B'grr S Σ
u
22 + ub)2
This we further estimate
Bg B'g. S a Σ n((n + 2b/2t)8/o-2-1122)) b((n ub)2f)8/o-111//20
In the event that the exponents are neg-negative, which can only occur when 23 > 1, we may lose a factor which is boundable by the largest & term (which is constant order) by logarithm in the case the exponent O. If either exponent is negative, the expression is dominated by its smallest term, for which (17 + ub)2 x u. In all we have
Bs B'sl S eu 1/(aa) + (n + ub) ub)u 8/a-1 + cn + b)u log(u))).
50

---

The large j regime, imaginary part. We break the sum into two parts L' and L", those with j < 1.1jo and those with j 2 1. For the terms in L' we again break into scales, much like in the small j regime. We let L to be those j for which
L {(n + ub)2² S u j j
2a a S (1 + ub)2*}.
Then we estimate the number of terms in each of these k by
| S C(a)(n ub)2 (u) 1/(())
Then for the imaginary part
wB/a+1 L1x (17 + ub)
BE S
22h + ub)²
w 0/a-1/100 1/(2a)
2
This sum is always dominated by the smallest k. and so we have
|Brr S eu2/a-1((2a)
As for larger j. we first remove a potentially divergent term, and so define
2a 29 (n ub)
BIy Σ
JEL"
In the case that a + 1/2, we have that (comparing to an integral and using monotonicity)
BB" (n + 11)
Jo
22-23 22
2a-28 22
S (n + ub)
S (17 + ub)u 1+///a11((2))
w² 2a 23)
4²
42
S cu 3/-11122))
Otherwise,
[B2-0| S (1 ub) 11880-11//2) S 0/0/011/(2a)
As for comparing the this divergence with the sum, we have
22 28 (j 20 (n/u / b))
j
28
((n + ub))
By ---BB'l S
2
(-u -u+jja 22
JEL
JEL
Then if 2a + > 1/2, this leaves
|Br' S (n
S 2/00/-1/100 1/(2a)
or in the case 2a + 3 < 1/2
[Brd| $ (1 ub)u 3 3-1-40-28 < (1 ub) (o s////i" 22-- 20 28
The real part. For the real part, we shall prove a comparison with
j j-2a 22-2.
A = Re Σ
in
which we note special case of with a = The arguments are now very similar in all regimes to the imaginary parts, and so we just give summary of the arguments.
The main difference is for j = jo. Note that using the previous bounds on the transition window, we may discard interval of - jol / VM
-1+2a from A and incur an error of only 2//11(((22)
On a larger interval, J. given by those j with
ni .1+2a
< lj - jol S Ejo.
by pairing jo + with jo r, can bound
|rr + |Aاl
S Ejo
.1 28 S eu 8/0 1/(a))
51

---

Moreover, the difference we can bound by
4a 28
[1 11-a| a w f//aa-1// (a-1/(2a)
|A, - A a
2a u)(j
2a
u)
JEJ
For small j. where we redefine S as those j smaller than those in we further divide hose j with Ij - Jol - Jo/2 22 and those S' which are further from Jo-
[As Ass- S
1
a
23 Ju
11-2
+ +11
j-2
JES
Hence we arrive
[As Asl S c///111((2))
+ cal al-
For the large terms, we redefine I. those j larger than those in J. Again dividing to those with |j - Jul S jo/2 2 and otherwise, we arrive at
[A A 11-2 1-
Σ
j
4, 2,
30
al
122
jEL
This, as in the large terms for the imaginary part, leads to
AA - A
1 1--a|
al Jo
11 + +1 - 8/0 1/(20) +
11-20-2,8
Finally, we observe that A satisfies an estimate of the form
y 2a 2,
A|| S / + cg 0a+B
which arise from the transitionary region, the small j region and the large region.
Proposition E.5, Assume a + 1 and a + 1 2
With u in(u), with
7 (log(I/e)/c) max { (11((20)
u² (22a)
2a d
there is a > and an 6g so that for all E (0,c)) there is a cc > 0 for all E (d-20 20 /ce, cel (with A as in Proposition E.4)
(m(2(u)) 11 d' A(u + -
in) + π 1/(2m) d d' < C(a)eu 1/(2n) d-
2a
Proof. We claim that m is approximately equal to
der
A(u + in)
nu 1/(2))
mg
20d
where m is the solution of
Xm(z)
F(m(z),;) == m())
_ R
1,
d Xm(()
with Im m < 0. Hence the result boils down to checking:
[F(mg 2) -1| 1/ 5 Ce u- 1/(aa
and secondly that
11 - (F) <
in neighborhood of mo. using Lemma E.2.
52

---

For showing that [F(m.. 2) - 1 chosen sufficiently small
we first observe that on the contour selected, a < and co. Ce is
ul-2a
(1 + ub) S T 1/(2a)
u²d
d
Moreover the claimed estimates on F now follow directly from Proposition E.4. For the stability, we have that
j-2az
1 Om
(j 2n m 2)2
Taking modulus, we have
j j-20 2a + 17)
- Pm S
X
2 u)² 2 + (j-2abb 17)2
2a
Now we break the estimation of the into regions of j. as in the proof of Proposition E.4. We let jo be the integer which minimizes (jo 2a u) We define S, L, I, to be the sets where
< 8jo, j> jo/6, ( u)² = (ub + +)²
and the rest in J, we let XA be the restriction of the sum to the set of indices A. For the terms in s,
(u ( 1) Xs S d a1 0(6) JES
u 1/2x
Σ
g1+2a
d
with the final sum holding for all 0 > 0 sufficiently small. For the terms in
j 20 u n)
1/220
v 1-22a
X
Σ
2
22 Oa
r2 0())
d
u2 + np
jEL
where on is the indicator of 2a < 1. For the terms in I we have
2a + n) (ub + n)²
1 1u (1(22(2a) (u n)
X1 x d
S d (ub 11)
jEs
where we have used that the number of terms in this regions on order of jØ 20+1 (ub + 17). Now taking 7) a sufficiently large multiple of u,3, we conclude that the terms X₁ S E/4 For the terms
2- + n) (j-20 u)2 2 C(0)
E Σ ud +1)
X S
J0 2a-11 (r)
JEJ
-22a- (r) x (ub + 1)), and so we arrive at here the range of r is such that at its smallest value jo 2a
1 u 1/(20) + X, S C(8)
(ub bb++))
Hence picking sufficiently small that Xs, Xx both less than 1. and subsequently increasing the lower bound on 17(ub) sufficiently far, we conclude that all four components can be made less than and hence that
0m <
E.4 The large z region
Proposition E.6. For any compact set C C of distance at least 8 > frrrmm [0, and any a # 1/2 there is C(a) such that
C(a)
[m(2) - 1 S min (d, d2a
53

---

and such that
j 2a
S C(a)
m(2) -1+ 1
d
20
8 min(dd d
]=
Furthermore, on the same set
2a 28-28
j j= 2a-2222 28
C(a) 8 8 (din|d, d2a)
20 (u + in)
j 2a (u + in)
Proof. We apply Proposition E.2 part 2.
We have
d |
1
EX
d
min(d, dayj'
and the result follows directly from Proposition E.2. We turn to evaluating the sum
2a 22
S(m, u in) def
j
2a m - (u + in)
j=1
Then taking the partial derivative in m,
j- 2-
Sm in)
(j m - (u + in))
j=1
which is uniformly bounded on U and on the set m so m 1 < 8/2. 2. It follows that on U
[S(m, u in) - S(1, u + in) x min d, )
For the second part, we start by observing that we can estimate
U E
X
j j-2a 2a
S
d
X
-
d
in
8 Sminfdd d=
1=1
We further have
X²
E
5
5ーー de 182
(Xm 2)2
82 min dta}
Hence, combining all these errors we conclude the claim.
Approximation of the forcing function
We now apply the technical estimate find good approximations for the function F. Recall
F(r) del 2Ti rtro
of (D 2 (1 - By + 7 + dz,
2a2a
where
R(z)= Diag
1 i1sjs
and m(2)
j-2 20 -
1 D) 5 -
We decompose the forcing function into sum of three functions
F(r)= (r) F
Fac (r) Fo(r) + errors,
which will be introduced in the course of the approximation.
54

---

111
Im(z)
d
1/c)
1/(20)
(op(1/e)
RR
F1
T
ed 2a
spectrum of K
Re(2)
d'
Md 20
d
To
T2
I caps = L + R
Te = 1 + 2
T= C + T caps
Dew
Figure 7: Contour of r + To- This is used to estimate the m and derive expressions for the forcing function and kernel function. The important part of the contour is Tu, which contains the point mass (blue) and T (purple) which contains the bulk of the spectrum of deterministic equivalent of K. There is a left spectral gap which occurs at d22a, Moreover we have a change of behavior at d' in the contour to account for the change of behavior from pure point absolutely continuous bulk part of the spectrum.
The contour we select will come in three parts. The contour To an arbitrarily small contour enclosing 0. The contour T will be in three parts which is symmetrie under the reflection The main part will be I parameterized by 2 = u + im(u) with 17(1) as Proposition E.5 for [uo, ui] where un uo (d) Cd-2a for some large C >> 0 and ij a small positive constant. This is connected by two curves, one which is smooth curve Fr which is on scale d- and which is reflection symmetric, connects un + (no)) to its conjugates and crosses the imaginary axis [0, cd cd-2a] (with as in Proposition E.3). The other I' connects tn + in(u1) to its conjugate by smooth curve which avoids an neighborhood [0. 1].
For To using Proposition E.3, we have
Fo(r) -1 of (R(=), (2) 2, 2 1)22)" dz. 2xi Jr.
(84)
This can be evaluated explicitly in terms of residue at O. Proposition F.I. The function Fo(r) is constant and
j 28
Fo( Σ 1 Pa
< Cd (208-)+21-1)
Proof. From Proposition E.3, we can apply the residue formula. Evaluating the residue and bounding the sum produces the statement.
The contours I' and rr both contribute emor terms. Define the sum of the two as
def -1 f
T caps
2 8 JratTe
(R(2), 2, + + + 2) dz.
55

---

Proposition F.2. There are positive functions f(r) and g(r) satisfying f(r) S C Cex 2n) and g(r) I Cexp(-cyy11 so that
3 craps(r) & Cf(r)d 20+ (1-3)))3)) + Cg(r).
Furthermore, for any M we can choose un T" and u₁ 1/T with sufficiently large that F caps(r) (r) satisfies for yBr S M and Brr 2 Md and some other C > 0
I Feape 2 f(Cr)d 21 28)+ /C gr)///
Hence this will appear as essentially constant on the loss curves. When combined with Fo we have that Fo(r) + "apppp() is bounded above and below by constants times d' 22-(22-1)--
Proof. Both the contributions from L and In give exponentially decaying errors, albeit at much different scales and lead to the f and terms respectively. For the I'R terms, we simply bound, using Proposition E.6,
[m(z) - 1 d min(2a.1).
On the Fa contour, having picked the contour sufficiently close to [0, 1] (independent of u d), have for some 8 > 0
((1 By +² 1) < 2yB B Re
Then we have
-1 &
2 j 2a-22
2 f $ d min(2a.1)
(B()).
(1 BB 1)22 de
j-2a 2
of
Re
|dz
Prx
Hence this decays exponentially.
By construction of the I'R contour, we can close the contour with additional (nearly vertical) segment Fv with real part u and height eu. Moreover this can be chosen to evenly divide two poles (--2a,, ). by adding small horizontal segments. Then we can estimate on I'v (essentially by Proposition E.4, with an extension for very small imaginary part when we split two poles)
2a 29
S 8/a-1/(20)
Then integrating over I',, we get
-1 f 2 Prv
Σ _
j- 2,
(1- + 1)22y' de S cui
1+8/a 1/(20)) -
Having enclosed the poles, apply the residue formula, and we have
-1 f
e 22--20
L
(1 (1-2)B2+ 1)22 dz
2T Jry+In
j 2a
j=1
jo
Σ
2a 28
1--yBBj- 2a BBB 1
for some jo with jo x u appropriate choice of 8, C.
11((2))
Hence both contributions of Tv and TR decay like g(r) for an
56

---

For I', we use similar arguments. We use Proposition E.3 to replace the summation by a d- independent quantity, which also requires rescaling the contour by 2n Then have
L 2Ti Jz
(R(z), (D)12)) d' 228
f(zd2a) 2222222 (1 - 2y B(B 1) da
x 2 dr
S d 2a of
Bod
[dal
Hence are left with a dominant contribution of
-1 f
(Jo
x x-29 dz
d' 23 2a
exp(-22,Bra 2n) da
2xi Jz
f(z) zx2a
In the case that 23 we instead left with
cæd -1 { 2xi Jr,d3a [[())
(TTE)
1epp(-2Bradd 20g dz.
As the spectral support of f has left edge, these decay exponentially. In either case, we can then deform the contour to rum twice along the real axis and then vertically to the ends of the Fz contour. The component along the vertical portion can be estimated by
Od -2))+ (ub (111((2a)) /d)) exp( (2 5) Bruu))
(and using the boundedness of 1/1/D) This can be made to decay faster than the contribution from f.
Finally, the dominant contributions arise from the contour Tc. We define:
F (r) del 1
u (20-1)/(2a)
du,
20:
(85)
F (r)(r) del C3
u 11(22))
exp(-2y- (oxpp(22yBBu Bru) du,
2a
d-20
where Cy is as in Proposition E.5. Then this gives us the principal contribution to the limit: Proposition F.3. Set for 20
Je(r) de 2xi ff (3(2), (DI/26) 22 -
of
1)22y' de.
Then Fo(r) is real-valued and satisfies for some constant C. independent of u1, uo, B
[Fc(r)) s C(Fpp(r) + Fac(r)).
Moreover, there is an M = M(u0, u1) > 0 and a positive bounded function C(r) that if y BB [M, a /M] then
C(r) (F + ( 3o((r ((r)(Tppr) +uc(r))
Furthermore, for any e there is a M(e, un, u1) large enough that C(r) S 1 e for BBr e [M, aa MM).
Proof. These follow in a similar way to the earlier Propositions, and so we do not enter the details. Instead, we give a brief overview, using the estimates given in Proposition E.5 and Proposition E.4.
Along Fc, approximate uniformly by
m(2(u)) (1 (c(u) + 1) 2a
1/(2a) x-1) s -1/121))
57

---

where e is real-valued and bounded and M = (c). Hence using Proposition E.4.
j 20-23 28
8/a 1////-1/(2)))) 12(2))
(1+0(e)) + i(1 + O(e))
1=1 in + m(=(())
2a
i(1 (()+0()))cc 2a
1/(22)dd
for real valued A and C3 = - if > 1/2 or 0 otherwise as in Proposition E.4. Integrating each of these imaginary terms over Te produces I pp and Fac respectively. The real part is negligible, as the contour close to the real axis (in particular the imaginary part of the contour is smaller than the real part by factor of e).
Combining all of these propositions, we have the following conclusion
Corollary F.I. For any a, B with a, B # 1/2 and above for all so that
1/ there is a function C(r) bounded
city (5 (Fp(ppl( + J (r) (r) + Fo(r)) S F(r) S pp + + +
Moreover, for any > 0 there is M() large enough that C(r) < 1 + y E [M, da/M and for BBr Md
Proof. This follows directly from Proposition F.3, F.2 and F.1, and needs that the curve is monotone fill the gaps on which the approximations are made. Theree are potentially two windows on which the various approximations do not overlap: when BBr is a large constant and when it is on order d2a)
G Estimation of Kernel function
We can now give the approximation of the kernel function, which represented by
K(r) def BB f
2xi Jr+to
- -
)) dz,
with the same contours that were used for the forcing function.
Using Lemma I. therefore can represent the kernel function
22 f Jrtro 2ri
K(r) def
=(-u+
(1
1)=2)" de.
By the residue theorem, the contribution from Ig disappears, as does the V2 term. Hence we are left with the representations
Bd
K(r)
1) dz.
2ii
When 7. the dominant contribution comes more from the contour To for which get
(r) def 72B / u²-1/((a) exp(-27Bur) du.
(86)
2a
It now follows swiftly from the estimates on m: Proposition G.I. Suppose a > 1. There a positive function C(r) so that
Kpp(r) S K(r) S C(r)
and C(r) bounded independent of by a function of M for all r coa Moreover for any > 0 there is an M sufficiently large that for B E [M, La /M), C(r) < +e
58

---

Proof. By reflection symmetry, the real part of contour integral for X(r) vanishes. Also, for a given contour I A. we will define
- Im Ka(r)
π JA =(1 m(=))d(1 - -2 + B y)= dz,
and we will estimate each piece of I = I'R + l'c + I'r, separately.
We begin with the contributions from R'.. Using Proposition E.6, we have that on I'R
BBB $ /(110/ -(])d
=(1-m(=))d
j j-
B 1) dz (1 (1-2yB=+1) (
2xi Jra
20
- d miu(1, Bexp(-xx
Following the same steps as in proof of Proposition F.2, we can extend the F' contour by straight line Vv to enclose some residues, which leads to
-22B
$
j-20 g j-2n
(1 11-2yB2-1 2 1) de
2τi
2
TR+TV
j0
2 B
j ta B-2yBB-a + B + 1)j-
-1((2a) Moreover, the contribution the Iv contour can be estimated (for some >
with ju x ii
which can be made small by increasing U1)
(ur 2-1/(20) exp(-27 8))).
Meanwhile making a Riemann approximation (and changing variables by j j-2a = u)
j0
1 1-1a(22) exp(-2y
/
40 - By + B + 4ay
u
2ox Jn
for ByBr < 1. Hence by taking i1 sufficiently small, we conclude that for Br <
1
my
B²B [' u 11/(2)))) 2y du,
Kx(r)
2a
and also that [3((()) S e Br (1-6) for larger (2yBr).
The contributions from I give, in a similar way for 2y Br 41
and By u1
(c(r) x 72 B
u 1-1((2)) exp(-22 du
uo
Moreover for any >> there is an M sufficiently large that when (2yBr) is in (2 da /
7²B
u 1/(a) exp(-2yBruu du < 1 +
1-c<
2a
by first choosing >>> then choosing the contour in Proposition E.5 sufficiently far, and then possibly shrinking [uo, ui]. For larger r, it further satisfies an estimate that for some ō > 0, which can be made smaller by increasing up, (r) S (1))
Finally, the contributions from l'z, we have after changing variables
(r. - dl-40 Im f =(1 m( 22 Bzd + dr
dz.
This can be compared to the same expression with m(zd?a) + f(z) and replacing (1 (1- 11-2y22d 20 This gives for 2 Br S d2a
BBB + 1)22d-4ay + exp(-2 BRe 2 z)d-2a),
undd
Kr(r) = 22 4aa
uf(u) exp( - 2 Brud 20 du,
59

---

where f(u) =1 lim f(u + ic) is the spectral density corresponding to f. Hence follows that for Br S dda0
Kx x BB f do
_1-1/(20) exp(-22,ru) du.
Remark G.1. In contrast, when a < 3. the dominant contribution to K is from Kt, so that
7dd=B {- uf(u) uf(u))xp(-22 exp(-27) BruBrud-220 du,
X(r) x Bd=
and moreover the density f(u) 1/(o2) so that the integral is convergent (which is implicit in Proposition E.5)
We conclude with noting that for ther of K directly evaluate it using contour integral. Summing the contour integral expression
Bd -1²
z(1 m(2)) 2ti fr 2y 72 B(B + 1)22 4 Pr 2 + 1)
d= -7d f. (1 (1- 11mm))) dz.
||]||| x(())
We udditionally can more generally evaluate a partial norm
x -yd of 4wi Jr 1- 1)2 2, ))²?)" dz.
(1 m(2))
Combining this with Proposition E.6, this leads directly to tight estimates for the kernel norm. Corollary G.1. When 2a 1 and (B 1) 2
2 Σ 2 j 2 2
j-20 (1 + o(1)
|
When 2a 1 (and recalling that we take 7 on the order da-l in this case).
Y 2--2a
|||||
(1 o(1)).
21 2a
Furthermore, for any 0 there is an M that BBr >> M then
Σ K(s) <c
Proof. For the first case with 2a 1, Proposition E.6 gives on I'R
V
j 20
m d
Σ j=1
j- - + o(1/d)
Using this, and completing the F contour via a vertical line, we get a residue contribution which matches the claim, up some number of terms jo (which can be made large as desired). Proposition E.5 and E.3 can be used to control the parts the contour near 0 and the middle.
For the second case 2a < 1, since 7 is small, we may deform the contour to be at fixed distance from [0, 1), and then once more we can use Proposition E.6 which gives step that
j-2a
|
O 40).
2
1j 20 (B+11)
For the final statement, under the conditions given
(1 B2 + +2 1)= <e
uniformly over the contours, and the estimate follows directly.
60

---

From here, we can derive the "sub-exponentia" property of K.
Proposition G.2. Suppose a 4. For any there is an M sufficiently large so that for yBr [M, da dd/M) /M]
X(s)X(r- - 5) S (2+ +)|3(((()))
Proof. We note that in the range of given, we can conclude that for any 5,6 O, by increasing M
8
Σ
K(s) +||>C||
furthermore that for > r/2
(1 - (sp)))) <x((s) < (1 + p))xxp(s);
and that finally for 8 >> r/2
2² [ (1/ (2 (1+ <)pp))))(()))
p)-c)Xppp pp ())
2a
where the final estimate follows by estimating
J. 11(20))
/ u ul-1/(2a) exp(-2yBur) du,
du x once ,Br > M, and moreover their ratio tends to as M + 00.
With these estimates in place, can break the estimate up
ró
r(1-8)
Σ K(s)K((r 8) <
K(s) - -)) Σ
K(s)K(( - 8).
==0
s=ri
The final sum is bounded by
r(1 5)
K(s)x(r - 8) S <( (1 1/
Mcanwhile, for the first sum.
Σ K(s)K((r 8) 2(1 +(0)))1)
where we have used that K Kpp (r(1 8)) S (1 01000)
H Asymptotics of forcing function and kernel function
With this, often rely on a result about how close a Riemann sum is to its integral. We state below the main result of this nature that we used:
analyze the asymptotics of each of these terms individually. These asymptotics
Proposition H.1 (Trapezoidal Rule, [15]). If is continuous, then for each integer n > 0, the integral of on (a, b] approximated by
def b (f(zo) + 2f((11) +...+ (f(xn-1) f(an))
(f(())
2n
where x, =a +ib an/n, < i n. Define the error in the trapezoid rule
( T.( - 1 f()) di
T
If f has an integrable first derivative improper integral, thens
F. (f) S [f'(t) dt.
61

---

H.1 Pure point forcing term, pp
In this section, we prove an asymptotic for the pure point forcing term, see (85),
|/1 L' (28 (28-11/(20) exp(-27Bru) du.
pp - 2a
Proposition H.2 (Pure point forcing term). Suppose 20x +23 1. For any > 0, there is M so that for BBr 2 M,
F (rp(r) g(r) <x (()
where
g(r) (2a)-1(2,;)) (2,) x r 2a
1 1) r (1+88//)+1//22
Furthermore, for any M. > 0, there exists some constants C, C c > 0 independent of so that
c3 SC if < M,
and if Ma
Fyp(r) s č Fo(r).
Proof. First, a simple computation shows that
/ w (22--1) exp(-w) dw.
g(r) (2a) (200)
Let p= (1 A simple computation, using the change of variables w 2n Bru, yields
/ w (2(2a)) exp(-w) de.
2rBr
F (r) = (2a) x
Then have that
(B w128-1)/(22) exp(- w) dw
pp) g(r)] S (2a))
2yBr
$ (2
(23 (22))))((2)) (xpp1(pp (xp(-w) dw.
2M
Since 10º (22--1)((2a) exp(- w) dw, there exists M large so that
ne (28- (222-1)/(2)) exp(-w) dw <
2M
Thus the first result is shown. If yr < M, then
F (p)()) S (2a)-1 S/' (228-1)/(2a) du S.
Moreover, have that exp(-2 2 exp((22M) Therefore, we get that
exp(-2M7 /
F Fp (r)
u (28 12/(a) du =c c.
2
Now suppose Br > 20 By the previous part, we know that (p) $ (1 + c)g(r) Moreover, we see that g is decreasing. As result, we see that up to constants
g < ((M = C x d 2a < Ō x
for some constants C, C > 0. Hence the result is shown.
62

---

H.2 Model misspecification, point mass at O, Fo(r)
Recall, from Proposition F.I, the forcing function point mass at 0, satisfies
Fo(r) Σ 1+ j 20 2a d2axd (v/d) (1 [1+0 O(d")) where x(v/d) solves 1 = po/d
2nx 2/3
K u2a du.
(87)
In this section, we provide an asymptotic for Fo(r) (see Proposition H.3) which represents the limiting value the loss obtains as r + Unlike the pure point process above, this asymptotic depends on whether 233 > 1.
We begin by showing that the k. defined implicitly in (87) is uniquely determined and dimensionless.
Lemma H.1. Suppose and d are admissible such that the ratio à > Then the equation
po/d
K
du
# u2a
has unique solution K such that 0 K < oc.
Proof. Let w def = k and F(w) def fo² 2 du and set
To solve the fixed point equation, we want to find G(w)) = 1. First, it is clear that lim (wr) = O. Second, we see that as lim G(w) = > As G(w) is continuous, it follows that there exists solution k to G(k)=1 1.
To show that & unique, amounts to showing that G(w) is strictly increasing for w 2 First, we see that
o/d
20 20x
20
G(w) 2o
du.
W + 22a
w
+ u 20
We note that w + w+ is strictly decreasing in w. So w + 1
2
is strictly increasing in w.
wtuze
Hence G(v) is strictly increasing and there is a unique solution to G(R)=
1
Now we give an asymptotic for To- Proposition H.3 (Asymptotic for To). Suppose u and d are admissible such that the ratio v/ > 1 and suppose 2a + 23 1. Let 0 k(v/d) oo be the unique solution to
w/d
1
du.
K + 2a
Then as d +
d 20
Σ
5
28
if
Folr) ~
dl 21=2(a+ puld u
ktuza du, 2 < 1.
Proof. We consider cases. Let k k= k(v/d).
Case 1: Suppose 2B > 1: Let Č 2j=1 28
j-28 which is finite as 283 >> 1. Consider the following
(r) def Ej=1 Td
20
Lond
To handle the large values, that there exists a ju large that
Ej j +1
Σ j 28 <e,
1230
where we used that -aa + 1 > 1. For the small j, we use that can be large. Hence,
28
23
jo
<
2c
Ked 2ox
Jn
pa
+
Jo
2o
+
63

---

For sufficiently large d, we can make the right- right-hand-sin hand-side small. Therefore, (r(r) is small for sufficiently large d and hence, the result holds.
Case 2: Suppose 2B 1: To show this case, define the following errors
f== g 20 d dl-2(aa+0) J1/a u 20 du
-- -
(r) der
8412
(1-2(a+0) So
a-28 du k4u2a
(1-2((a+() 53/4 y-20 du of 21-2()00) fold u da atuth
(22(r) del
d (1-2(a+0) sold 28
It is clear, for sufficiently large d, (r) is small. For the first error term, Riemann approximation, that is,
j 2(a+8)
Σ (j/d) 2(
20 Ro +1 = 22=2(()+)) x d j=1 (j/d) 20 +1
Letting 1/d, b v/d, J.- 1/d + j/d, and f(x) x- 2(a+8) the summation with integral. Using Prop. H.1,
x-2ax+11 approximate
1/2 x S%/ [x(x)) dx
(r) <
fold 2- da Ko
1o/é (x()
One can check that
< C where C independent of For sufficiently large
Jo poyd u 22 du
44130
1/ x S1jd
pold (5)z)) de
E21(r) <
<Cx 6E6
gu/d u-26 du xt
Hence, Case 2 is shown.
H.3 Absolutely continuous forcing function, Fac(r)
We now turn the absolutely continuous forcing function, defined
Fac(r) = 2a Ja u 1/(22))) exp( exp(-27Bru) du,
C3
where 6g
28 if 23 > 1 and otherwise. From this, we derive a simple asymptotic j
formula.
Proposition H.4. There exists a constant C(a, 9) > such that
[C x Fo(r), i > 1, 2a < 1 Jod(r) < 10.
(88)
2 < 1.
Suppose now 20 and 2/3 > For any 6 0, there is an M > so that for 7 Br (M
(r) 5exg(1)
where g(r) j (22 (2a) -t)(i-T((11 2 r 1+1/((2)) x d=
(89)
Furthermore, for any M > 0, these exists some constants C, > 0 independent of d so that
[Cxd',
if < M Br > Md
Fac(r) <
64

---

Proof. We proceed by cases. The case 2 < is immediate as eg is only non-zero for 23 > 1. Case: 2B >> and 2a 1. In this case, just bound directly bound Fac(r). Dropping the exponential, we get
u 1111(2)) du = add (d' - d1/2-a
Fro(r) 5
CB
CB
x d 20
2a J
20
- 20
2n
We know that (r) d 2a+ max and thus the result is shown.
Next we show (89).
Case: 23 > 1 and 2ox 1. First, we make the following observation. The integral is
C3
u --1/(20))-- exp( (x. du g(r).
2a J
Define C = Let consider the following
def
pd
e-2Buur u -1/(2a) d du C / Bur 11((2) d du
C
d-20
First, we see
d 20
By u- -1((2)) du 27 2-2 11/120 d= du C 00
8
C
Case: & Suppose yBr I 1/Mdaa. Here we can just use directly the u and disregard the exponential:
ByBuur u 11/(2)) du S 1 p 11(22)) du = ē x 2a
for some constant č. Now we have that 20x
d- (7) = d 20 (T)) & dd
(1/M) pa-1 M -M1+1/(20)
By choosing M large, this be made small.
Case: &g. Suppose BBr 2 M. Let us consider
E SC S. d 22 du < (y expeeeppp200
follows that
dr exp(-p220 -y) (yBr)-1/(2a) -1/(2a) exp( 1:p(-22-Brd- d (r) 1+1/(2a)
< 3xxp(22M)MM) e -1(2a).
Therefore, by choosing M large, we have that this can small. This proves (89). To finish the proof, let us first suppose that Br S M. Then we have that
Fao(r) S C3 u -1/(22) du S 1
2a -
When Br 2 MrR we have that
Fac(r) 2 S/' exp(-2y du < 22 Bool-2-Mdd'' d-20) S Folr).
65

---

H.4 Kernel function asymptotic.
recall the term Xpp defined as
2 S (/11/(2a) exp(-27Bur) du
B²B
ppp(r)
2a
We now give an asymptotic such function. Proposition H.5 (Kpp asymptotic). Suppose a > 1/4. For any e > O, there an M so that for BB M.
[Kpp(r) g(() <cx
(90)
where
g(r)= del
r ) 2+11((2)))
Moreover, for any M > O, there exists constants c, C, Ć > 0, such that when 2a > 1,
( SC ir S M
and when 2a 1,
Kpp (r) S Ć x da- BB S M. Furthermore, for any M > O, there exist a constant Ö > 0, such that
Krp(r) S Ć x Fo(r), Bf Ma
Proof. The first part of the argument, (90), follows immediately from the proof of F Prop. H.2. 2ox > 1, then we always have ²²B is constant order. Therefore, using the same argument as 3pp (see Prop. H.2), we get that there exists constant c, C > such that e < (r) S C for yBr S M.
If 2ax < 1, then y x d2-1 Therefore, for BBr < M, we have that
²B (' 21-1/(2a)
du 2a-1 yB ( 11-1/(2a)
du d2a-CC.
2a
2a
The later inequality follows using the same bounding argument as I (r).
As 72 < C, then the same argument in (pp(r) shows for yBr 2 Md that Kpplr) S CFo(r).
We now turn to the last quantity that appears in the Volterra equation. Proposition H.6 (Forcing function norm). Provided 233 1, we have that
M ((BB)
Σ
F(s) < B
(91)
for some constant M > 0.
Nexi, suppose 23 < 1. Then there exists M M 0 such that
Md ((
K(r)
Σ
F(s) F(r) for all M BrB S MaRa
(92)
M/GBB
and it follows for all BB < Mda
M ((;
K(r) x
Σ
F(s) S F(r) + x K(r).
(93)
7B
66

---

Proof. Suppose 23 1. First note that in this region Σ 2010 Ma (6BB) Fo(r) 2 7 for any fixed M Proposition H.3.
Next, let us consider the pure point part of J, i..., ppp Choose M and M that Fpp is behaving like the asymptotic in Proposition H.2, i... for BB 2 M,
F pr) (r) = (r (1+.9/)4411(22))
and for yBr S M, pr) & C for some constant C > 0 independent of d. It follows then that
Σ (r) x B
To handle the rest of the sum, we see that
Md B(7B)
Md ((TB)
Md BB
Σ
J (r) x
Σ
(144//00+11/22)
M)(BB)
r= M/(BB
r= M
Ma
1
Σ
(1+8/a)+1/(2a)) d2a
BB
d2a
T=M
(daa) ((a))-//aa)) 8//a+1/(2a))))) M
M+Mi
x. -11+9/a))-1/00 da
BB
(day - 8//a/ 3//+11(22)) M2a
x x -8/a+11(2a)
M
BB
1 - --23
K /dpa
2/
BB
Here we use that the Riemann sum approximation with = (1+B/=
53 d2a
b
M
+
As d2a
Md and
Using a similar argument for Fre(r) (Proposition H.4)when 2a > (otherwise we do not need to worry about Fac), we have that
Md (g
d-1
2d
M
Mr
-1+1/(2a)
Σ
Fac(r) x
Σ
1+1/(2a)
d
2a
B M=
BB
d2n
M
<
M
MM
1++1/(20) dr B
1
B
J
1 When r S M/(rB), we have that Fae (r) S d=1 Hence, /11(11 Fac(r) $ 78 The first result, (91), then follows from Corollary F.I.
Consider 28 and 2a 1. We do not need to worry about Fac in this region because it does exist in this region. Choose M and M so that both Kyp and Fpp are in their asymptotic regions and, using Proposition G.1, K(r) (r). Using a similar argument as above, we estimate the summation of I ppp as an integral. For any r E B), Md2
(B 1/(o)) M2a
-B/o+1/(20) 1r B
Tpp(s) S
B
1 1-23
M
== M/M(BB)
1
(Trr) 3/a 1/2aa)
BB
67

---

Using the asymptotic for Xpp (Proposition H.5).
X(()) x
Σ ppp()) S x (rBr) (r 2//41/222)))) x (rBrr) 2+1/(2a)
M/(BB)
We will show that this less than (r). Using the asymptotic for ppp (r) (Proposition H.2), let us suppose
? x (rBr) x 1/(2a) < (r
7 7 (r Br)
In this region, the learning rate is y x da-1 Thus, we see that
22-1 S (r (20-1)/(2a))
(2--1) 1) 2a 1 2 (r
20
2a-1 20x
2a 2a-1
+
La 2 (7 Br)
This is true and so we have that
K(r) x Σ
ppp(r) S pp))),
for all E ( ((yB)
M B
For Fo. with E [M/ Ma (xy
Σ
2a x BB Fo S (yBr) x d22-28220
e=M/(;B
Therefore, we get that
X(r) x
Jo(r) S (n x 222 x 7 x (rBr)- -2+1/(20)
()
<d <d 20- (2
We will show that this is less than Jpp- For this, we see
d 23 Br) 1+2) - $ (rr -8/a 3//a -1/-111/222 1+1/(20)
+ 23 $ ((BBr) -3/0 Br) d29
+ (r S d
Hence, we have that
K(r) x
Σ
Fo < F (r)(), for all r E [M/(7B), /(>B)).
M)
Since there is no Fac in this region, we immediately get from Corollary F.1
X(r) X
F(r) S (r), for all e M (TBB
== B)
For E [0, ())), we have that F(s) S C. Thus we immediately get that
M/(BB)
1
X(r) x Σ F(s) K(r) BB'
for all r.. This proves the result for 23 < 1 and 2a < 1.
68

---

Consider 2 < and 2a > 1. As in the previous case, we do not need to consider Foe as it does not exist here. The proof will be similar to the previous case. Choose M and M so that both Xp and pp are in their asymptotic regions and, using Proposition G.I, K(() x (r)
First, by the same argument as in 2B < and 2a 1, we immediately have for 8 E [0, M (B)),
we have that (s)) S C,
M M/(BB)
K(r) x
Σ
F(s) (
1
7B"
for all r. As before, have for any r ( /(>
x(r) x
Σ (s) E x (x 9/a41/(22) x (r (xBrr)2+1/(2a),
M/(BB
Note here that y is constant. We will show that this is less than 3pp (r). Using the asymptotic for Jpp pr) (Proposition H.2), let us suppose
(rBr) 8/a+1/(2a)) x (,Br))2+1((2a) < (7
5 (7Br)
Hence, we have that
K(r) x Σ (pp(r) S (rp(r),
all (TBB)
M B
For Fo. with r [M/(7B), Ma /cyB]]
Σ
Fo Fo (7 228-2a 1
7B
s= s//B(y))
Therefore, we get that
K((r) To(r) $ (yBr) 229-222 (yBBr)-2+1((20) 22a/(2n)
B=M/(rB)
S 2d (y
We will show that this is less than F For this, we see
d 21+1 2/7 1r)--111(22)) (2a0) $ (Tr (0/B)-B/0-000 -8/0-1411122
d 2a+1-22 $ (1 Br) -B/a
B/ca
(1/r)//a 8/a S 2 20
Now we see that (rBr) S dB < 20 Hence, we have that
K(r)
To S 9 (r), for all r Md& ((yB))
M=M/(BB
The result is thus shown in this case.
I Optimizing over batch and learning rate
The previous sections batch size B 1 and the maximal learning rate allowed. In this section, we consider optimizing compute-optimal curves with respect to batch size and learning rate, i.e., find d 7- B² such that
(d' "C,T","" B²) E arg min E arg min dB d, s.t. B 1 and Kyplll < 1. (94)
69

---

I.1
Optimal batch size
We see that batch essentially scales out of the problem and therefore the batch has no effect on the compute-optimal curves. To see this, we observe from Table 5 that
ppp(r) x (rBr) (1+B))((4+)))+11(((()
7 Jpp i x (2))
Fac(r) = Br) 111))111/(2)) x xd=
Foe ( ( 1 d=
(95)
1 xp (r) x (->
= Kpp = > (2))-211/2))
immediately follows that the batch size has no effect on the compute-optimal curves. Therefore any batch size (e.g., B 1) that satisfies the necessary and sufficient condition for convergence
(Prop. C.2), that is, y(B + 1) < 2, will yield the same compute-optimal curves.
This is not necessarily true for the learning rate as we will see in the next section.
1.2 Optimal learning rate
Without loss of generality, we let the batch size B 1. From the expressions in (95), Tp and Tac are monotonically decreasing in learning rate y. Moreover in Phase III, - 5B Kpp. is also monotonically decreasing in the learning rate. Therefore, in Phases I, II, and III, the optimal learning rate choice is to choose y maximally. In the cases of Phase la, II, and III, this would mean y constant (see Prop C.2) and in Phase lb, Ic, 7 2a-1, It remains to understand the effect of the learning rate in Phase IV.
that
From Proposition C.6, we know that the loss is given by
P(4. d 7) x Fo(g) ( (2) + 1 xp (
(2) + + -221)2211(22) = d- 20
where p By taking derivatives, we see that
_ 11
7" (d. ja/0-1 and d' g0 (0-)
We need to check that y" is feasible, i.e. 7t < (which it is) and yr < d For the later, simple check shows that
4
d 220+28-1 < 2-
when a > 1/4 and 2B > 1, i.c., precisely Phase IV, The compute-optimal curve in Phase IV with optimal stepsize is the following. Proposition L.1 (Phase IV, optimal y, compute-optimal eurve). Suppose 1/4 a 1/2 and 23 1. Then
2a(a-8) 22
20
-2a22a+23-1)
7 The trade off occurring where >B Kpp To-
d' df f la 2a
and J (f) x HaJ+2++22-1
We note that there is only one Phase IV (and no sub-phases).
J Experimental Results
To measure the exponents of the scaling law and parameter count, we follow approach'2 and from [24]. We explain the method below using (a, 3) = (0.5, 0.7) as an example. The theoretical 17 0.5 and & 0.5,
prediction of the scaling law and parameter count exponents for this example resp. (see Table 2). We then repeat this procedure for total of 32 pairs of (a,,9) in the phase diagram; Fig. 15 and Fig. 16. The theoretical predictions of these exponents are shown in the heatmaps Fig. 8.
First, we run SGD for parameter counts
d E [200, 300, 400, 600, 800, 1200, 1600, 2400, 3200, 4800, 6400, 9600, 12800). The SGD learning curves for (a. 3) = (0.5, 0.7) with parameters d E [800, 1600, 3200, 6400, 12800] are shown Fig. 9a.
We did not use approach 3 in [24], which is more subtle than the other [7].
70

---

14
02
1
10
104
14
Nv
14
16
12
Amorae Sclns
-04
-35
(a) Parameter Count Exponents (E)
(b) Scaling Law Exponents (n)
Figure 8: Theoretical predictions of parameter count and scaling law exponents.
J.1 Measuring the Scaling Law Exponent
We follow Sec 3.1 in [24]. First, we choose an IsoFLOP window [fmins fmax] and construct fy's using geometric spacing between fı fmin and fn fmax. For each IsoFLOP slice, fy. (c.g.. f = 2e7 is the vertical line in Fig. 9a), we find the minimum loss across all d. We denote this minimum value by (f,) and the associated optimal parameter by d' (f;). As an example, in Fig. 9a,
3ot (f,) 1.6e - 3 and the associated optimal parameter d' (f,) 6400.
We obtain the compute-optional frontier (highlighted in red in Fig. 9b) by plotting
[0,, 9h (fs)ssssns
(96)
and the optimal parameter count
[fa d' (f:)lisisn
(97)
We then fit power-law curve (f) = a x f- to predict the relationship between the compute f and optimal loss "a, This is shown as the dashed line in Fig. 9b. For (a, 3) = (0.5, 0.7), this gives
(f) = 22.61 x f 0.515
whereas our theoretical result predicts
Pd (f) x f 0.5
J.2 Measuring Parameter Count Exponent: Approach 0
One benefit of our theoretical framework is that the solution of the Volterra equation (eq. 10) is deterministic. As such, precise numerical evaluation can determine the instantaneous slope of the compute-optimal curves using a new approach that is not necessarily feasible when dealing with noisy
Scaling Law Exponent: 0, 1.515 (Measurement) vs 0,500 (Theary)
4-602
d-12820
4-1600
IsoFiop:
10"1
6:2200
Compute-Dptim Optimal
Isoloss: 1 lee
10"1
Trasiin losk
Training Lose
10
10'
10
962 lo. (0.5.
Compute-Optinal Fronter
10
Prediction (ix) 22, 61x
Flaps (SND)
Floos (6ND)
IsoFLOP
(b) Compute- Optimal Frontier Figure 9: Measuring the scaling law exponent for (a. .) = (0.5. 0.7).
71

---

Optinel Meproash 1)
(Popecech
0.25x
Approac1 0.15yA00
Parans
10
reapele
10
10a
10'
10'
10a
10
10
10"
10"
10
Flops (6ND)
Flops (SND)
(a) IsoFLOP Window [1e6, le8]
(b) IsoFLOP Window [2e6, 0.5e8]
Figure 10: 2 different IsoFLOP windows for measuring the parameter count exponent with Approach 1 for (a, 8) (0.5, 0.7).
SGD curves. Specifically, we search for the unique tangent line that intersects the loss-versus- flops curves for adjacent values of d, i.e. we numerically solve the following system for fi and f2:
p((A) = P/(22) P2( - ((i)
(98)
where Pi is the loss curve for d d1 and P3 the loss curve for d d2. When dj and d2 are close, we obtain an accurate estimate of the parameter count exponent by measuring the discrete logarithmic derivative, (log(d2) ( log(ff)).
J.3
Measuring Parameter Count Exponent: Approach
To predict the optimal parameter count exponent, we fit the function dt = a x fb, a, b constants, to the measurements in (97) (see e.g., Fig. 10a). For the example (a, B) (0.5, 0.7) (Fig. 10a), this approach gives
d' .25 x p..511
(99)
Note that the fit of the exponent is very sensitive the choice of IsoFLOP window. When we change the window from [1e6, 1e8] to [2e6, 0.5e8], the parameter count exponent changes from 0.51 to 0.58, as shown in 10b. The theoretical prediction of this exponent is 0.5.
J.4 Measuring Parameter Count Exponent:
Approach
For each IsoFLOP slice, fj. we obtain a set of training loss values depending on d, (I d<)ss In our running example, d1 = 200 and d,,. 12800 (see Fig. 9a). We then fit parabola (quadratic
(Thecry)
-1.00
Oytimal Param Count
Approact (x) 0.17x
-155
-150
Logt0 (Tre0 (o8)
-1.55
Params
-2.00
-228
1005
-2.00
1.267
2275
2,267
+3.00
10a
2.3
2/75
3.00
3.29
3.37
3.75
4.00
4.25
430
Logt0 68)
(a) IsoFLOP Quadratic fit
Flops Flops
(b) Approach
Figure 11: Measuring parameter count exponent with Approach 2 for (a. B) = (0.5,
72

---

B-0, Skee
10
C3
10
12
94
83
03
64
4270
IsoFLOP Window [1e6, Sc8
(b) IsoFLOP Window [1e6, 5e8]
(c) IsoFLOP Window [1e6, 5c:8
08
Sqpeert Chorpy
06
0.6
200
68
32
84
34
10
0.4 055
12
00
0.
32
12
(d) IsoFLOP Window [1e6, 1e8]
(c) IsoFLOP Window [1e6, 1e8]
(f) IsoFLOP Window [1e6, 1e8]
Figure 12: The empirical measurements of the scaling law exponent and parameter count exponent are sensitive to the choice of the IsoFLOP windows. Top: larger IsoFLOP window [1e6, 5e8] Bottom:
smaller IsoFL.O window [1e6, 1e8].
function) to {(lg (f,,, de), log di)) i.e., we find (a, b, c) such that
log (fs. de) = a log di + bog de c.
This is shown in Fig. 11. After solving for (a, b, c). we find the dJz))) that minimizes a² log" d - b log d + c. Repeating this procedure for all f 's gives a set of pairs {(f), djj)sssn In the final step, we power-law fit this set. For the example (a, 3) (0.5, 0.7) (see Fig. 11b), this gives
d' 0.17 x po.565
J.5 Exponents comparison: Theory Measurement
We compare the empirical measurements of the exponents against their theoretical predictions in Fig, 12. We chose three slices across the phase diagram
1. a 0.7 Slice (Fig. 12a), in which (a,, 3) goes from Phase Ia, Il and III.
2. 0 0.27 Slice (Fig. 12b), in which (a, 3) goes from Phase Ib to Phase IVb.
3. 3 0.7 Slice (Fig. 12c)., in which (a, 3) goes from Phase Ic, IVb, IVa, III and to II.
For the scaling law exponents, the empirical measurement agrees with the theoretical prediction quite well. For the parameter count, the agreement is good but not as good as that of the scaling law exponents. Noticeably, there is disagreement between Approach disagreement is not surprising, empirical measurements are sensitive to the choice of the IsoFLOP windows and we use the same IsoFLOP window [1e6, 5e8] for all (a, B). This is clearly suboptimal. We briefly discuss this in the next subsection.
and Approach 2. Such
J.6 Instantaneous slope
In this section, we demonstrate that there can be strong finite-size d effects in the measurements of the scaling law and parameter count exponents. We measure the instantaneous slope as a function of parameter count for the Volterra equation (10). See Fig. 13. To do so, we generate the Volterra solutions for a geometrically spaced sequence of d's with ratio 1.05. We then apply Approach I with a very dense IsoFLOP window (100 IsoFLOP Slices between [2e4, 2e7)). We then slide smaller IsoFLOP window (20 IsoFLOP slices) from left to right to generate a sequence of scaling law (parameter count) exponent, as shown in the middle (right) plot Fig. 13. These exponents varying slowly when the window slides from small flops regime to a large flops regime. For example, the scaling law exponent rj changes from 1) = 0.440 to rj = 0.413 from left right, while the parameter count exponent changes from = 0.450 - 0.575. Using the global window (100 IsoFLOP) to measure these exponents, we have 1) = 0.42 and & = 0.52 which are very close to their average over all small windows: 0.418 and & = 0.526.
73

---

10
0.440
0.455
meen
0.550
(1ee01
Triiting Loss
10"
0.430
0.425
0.500
10"
[tx)-20.00
0.400
0.475
-V
100]-14.37 375 410.412
Large ftt
0,15
10'
10
12'
10
4.5
5.0
5.5
0.0
4.5
3.0
5.5
((Fops
Log(o()Flop))
Figure 13: Instantaneous Slope. (Left)) Volterra equation (10) dynamics for a highly dense grid of d. We also plot the compute-optimal front obtained from using the left small window (small flops regime) and the right window (larger flops regime). (Middle) Shows the evolving measurements of scaling exponents when the flops increases. (Right) Shows the evolving measurements of parameter count exponents when the flops increases.
J.7
Negative 3.
In Fig. 14, we show that our theoretical results work well for f < 0.
(a. 80--)-7--002 0.2)
(a. (0-08))--0001111 0.155
[a. 8)-(0)7.-00 -0.1)
4x10f
2x
Theie
30
2x10
6 10
10F
(a, ()- 0.05)
ta, 8)-00)0-0000 0.0)
la, ()- 0.2)
D-063
D-163
DH-03
C-663
10P
6110000
11:00
E-12800
D410000
Thou
D-1600
10
D-100
Theve
10
10'2
10
10
10
10
10
10
10a
10a
10
Figure 14: Negative 8. Sweeping 3 0.2 to 3 0.2. We see good agreement between Volterra
(theory) dynamics and SGD dynamics.
J.8 Additional plots for different phases
We summarize the measurement scaling law exponents and optimal parameter count exponents in Fig. 15 and Fig. 16, resp.
74

---

Expeet 1183 Neerrveri ef 2222 meesi
Duzwno 3M (Marrseeed v (Theety
Eppent 2:43 (eszered it 2.25 (Thenn)
Diperr 20 (eer un 120 Thanri
10-10 2,
S0ll -t 10.25003
530 Bi- 26, vohara
9.251
lobera
12'
Ourguut totpetttttttttiii onder
Compereditial Harder Prid 6.30
Computttigiiii higgiiiiihhett Frddiko 50 6.43
Prodicico 4.20
Praticiion
15
10
Expeort16672 MMN00rae 6..0 Thers)
Ou (Mpesemmen 150 Mhoor.
Eorizt Massurrett IS (oses)
Baneno MMZIA www Mhoood.
3'
1F
500 1s,
F2B Bi- 18.27. 9.1
522 Fi- (0.77
SEE:12, Al 10.27.
1F
WXD
Compundaiiral Torder Prol fast 4.41
Conaace Optiral Trander
Redici 100 2.7x
Fedirka Eo 5,74
Procitann fMS- 6.77
IP
WP
IP
1P
12'
IP
(eszeret)
302 1s, Rt-00000 27. 071
58B fh 15.27. 8 Veam
50 ls. F.. 00 10.27.0 5% Voharo
S00: 21 10.27. 3.41
tobara
Compertizira sarder did fell 7.26
12"
hrdd 2.34
13
Proickn Eri 7.50
Protitaon dx) - 2.33x
1P
1P Equeett 243 (loesred (Teen))
1P
Exgaret 283 Mouerssed 288 (hhar))
Fxrwen 772 (Meazaeeee 200 (Theory
Dugseen eM) Meee wreettee (o0T
Triiing
522 In, 50-10 27.22.2 1.30
55 ft- 18.2. 0.1)
522 F0-0003 O.1.
12
22:-0 21- 10.4 C.T
WDrD
Wee
Oparal
Catpeta Toele Prdd stae fud B.
Greach
R50 1.30
Podrska 5o 8.50r
Podtrann f5) 12 23.33x
16-
bspent 2:215 (Massesed es 2:30 (thwe))
12 50th (ftesnneen 1.03 (thoxy)
Eipedd4433 (Massered is 6.12 (1wen))
13"
01
30'
Jr. (0.55 D.7
(i (8..0.0)
52t [t. (0330
Strij,)) (I 102.0A)
13"
Pho
Ert 7.72
155
Exgoeet 535 Mare reeedi en 283 (heas)
172
n DE (eeuseeeee sed $15 Thwaay
Eq0 [eweneeed 6:43 (Twens)
13"
Dxgarenn 55/ (derr wwwel (Ttheer)
12"
137
Fi- (.0
13*
S0tr 51 107.00)
101
13*
12
12"
Espeirt 162 Mooseered es (Ther))
135
St.00 (Meeseooee 10. (Thoor)
Expeirt Ml (esosereet es 0.43 (Teees)
Exg KTT 952 (Morss to No (1ao)))
135
Trarng
101
12"
Sompas-pprrul Cotaaa-pptaallteeee Fresee 5x0 1922-191)
Compura horder
Frander
17.53-
19755
12"
Menzereri en (Tees))
Chumeet 997 (Menssrran Theary
Fqueet 7E5 Waanerred E.7E (Taen))
Oagaerr Thany)
12
19.
0.71
at (6.5.0.)
(r.P) CL.0 0.7)
Kobirs
12*
harter
Cangu Roater
Drepate Opraan- Forder
Prddiis Ru) 20
12
24
12
Eet 21. 404
107
(900
Tage (850)
Figure 15: Theory vs. empirical scaling law across different phases.
75

---

10
Qallnd Pi
opecd
Cead agreeat Ear scpette
1ppeant 501
10
13
Appcca
2.00
Apractt Ea Gocett
'0'
1P
10'
12'
10
13'
T0'
10'
13"
aoinal Connttopaa
apprent:
12
20
10
Io Pear One Acreeh 14
Optind From Cort
Cn Oree
12
13"
opean
optned
Appsach 100
spranh (its Odg
Appccsh t.t
Agrnect Kree Ligenn
Phee No 21ee00 Theee
Dhe 1333 Deres
Firdt SCC Erpese Three
Prem (1 fremmf
Aspuadi ESt outee
Commel faon seprss
13
10
Spinai hear Captapann
Plac La sopaedtiion 2o0
Mostera St- soseeer neeee
Mata 55 -Q.1..d iupreet (eee)) 2017
lppronnt tic
Sptinal
Acreet fut
13"
00"
12
Appoch Say
Aireerk Ex Eer
18
10
Porc RU moreet 2.477
hypore (heert 2.30
Mourth uo RIc car
Mesii 10.0 1222 ag reuare Thear 2
Jpmn hean Cort appoeen
ogina Paem Oue oprashi
Commel fays
Apreeh 2o1
12"
12'
Appoont lo 2a.
1
1P
101
10
12
12
107
157
Sptiall Crpaent (hrert 6.000
Theeet 650
Phay
15"
Calter Fa
aptmall Corsthoppen
oginn Coattippe opoich Soo- seget
Coltell bose
Roa :-to 2000
Aspasch for-- do
17'
10
18'
13*
16
Spirnl rr
17"
Colted
qoark's Crtwi
grmaa hear #preeh 2113
Opend Froe Copt Appocit
Appocth U: 22
10
157
70
Rage
Figure 16: Theory vs. empirical optimal parameter count across different phases.
76

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All the statements stated in the abstract and in the introduction are proven explicitly in the remainder of the paper with most proven in the Appendix. We clearly state that we are studying a simple model with the exact description described Section 1.1.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We clearly state in Section 1.1 that we are working on simple quadratic power law random features model with assumptions on the data and targets. The algorithmic set-up follows that section. We indicate that we are only considering fixed stepsize SGD, All the results are proven in the Appendix. We also make note that we only prove our main result for 1/4.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All theorems and results are proven in the Appendix. We make sure to clearly state any assumptions and limitations. For example, do not prove the setting for < 4 but we clearly state this (see c.g., remark after Theorem 2.1).
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
each the figures, we provide an explicit description of how the image was generated including the numerical set-up. In this case, the experiments are simple and they do not require significant coding datasets. This is mainly a theory paper and the data was synthetically generated. The model has already been used before in other papers and the data comes from Gaussians. This is all clearly stated in our set-up, Section 1.1. We intend to release the code for the numerical computation of the Volterra equation and how it matches the loss curves under SGD.
Justification:
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
The paper does not include experiments that require significant code. The model we analyze is a simple random features model with power law applied to synthetic data. As such, the code can be readily reproduced by following the set-up seen in the caption of the figures. We intend to release the code for the numerical computation of the Volterra equation and how it matches the loss curves under SGD.
Justification:
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
77

---

Justification: The experimental design, including the power law exponents, fixed stepsizes, choices of and v, and the numerical simulations for solving Volterra equations are all written in the captions of the figures. We also intend to release the code for numerically computing the Volterra equation.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Ye]]
Justification: We provide (and explain) in the figures/captions the error bars across multiple runs of SGD. We record how we generate the empirical compute-optimat exponents using statistical tools that were first deployed in other papers such as [24]. We are careful to explain when and why the theory deviates from the numerical simulations. Often this is due to finite d and effects and the slow behavior of the theory to the asymptotics.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: As this paper is about compute-optimas curves, we provide details on the exact number of flops required to perform the experiments. Since the model we study is simple least squares model, the compute resources are also well known in by the community.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the Eppuulcc/EticsSuieeeee
NeurlPS Code of Ethics https:
Answer: [Yes]
Justification: We have reviewed the code of ethics. We have made our utmost attempt to adhere to the guidelines provided by NeurIPS. We do not use any human subjects nor any datasets. We did our best to cite all the relevent related work. Given that our work is in the foundational research, it is difficult to mitigate all the risks as the downstream effects of theory are long, but we have done our best. The model completely synthetic using the standard SGD algorithm; thus we don't, the best of our knowledge, anticipate any risks.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
The work presented is purely foundational research and is not directly tied to any particular application. We study simple random features model with power law data and target and we solve the model using a common algorithm SGD. Given the theoretical nature of this work, we do not anticipate any direct ethical and societal issues. See our Broader Impact Statement in the appendix.
Justification:
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper poses no such risks. The work is purely theoretical and uses only synthetic data generated from a normal distribution. The models employed are standard statistical model (c.g., least squares) which are textbook learning problems.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
78

---

Answer: [Yes]
Justification: We acknowledge via citations that the model we study was introduced before by others (e.g., Maloney, Roberts, and Sully paper). We using any datasets other assets beyond numpy and thus do not need to name any license or cite any dataset.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: do not intend to release any new assets. The work theoretical analysis of SGD random features model.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects. The work is purely theoretical on simple model.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The work does not involve crowdsourcing nor research with human subjects. The data used in this work is generated synthetically.
79


Reviews:
[{"review_id": "gQ8FYrJ1cg", "reviewer": "Reviewer_HQ3F", "summary": "This paper studied a solvable neural scaling law model (the power-law random features, PLRF) that involve three parameters (data complexity: $\\alpha$, target complexity: $\\beta$ and the number of parameters: $d$). The PLRF model here is trained by applying the stochastic gradient descent (SGD) algorithm to the mean-squared loss. For different choices of the parameters $\\alpha$ and $\\beta$, the optimal number of parameters $d$ is solved by minimizing the expected loss. A corresponding phase diagram is drawn with respect to $(\\alpha,\\beta)$. An extensive set of numerical experiments is also conducted to justify the main theoretical results.", "questions": "Overall, the reviewer enjoyed reading both the proof and the experiments presented in the paper a lot. One possible broad question that the reviewer is interested in is how the theoretical results presented here can be linked to previous work on the learning of timescales in two-layer neural networks [3] (In general, the key question is also to address which features get learned at which stage).", "limitations": "It seems that the authors didn't perform experiments on large-scale language models (LLMs). One possible way to make the work more impactful is to do some empirical investigation on LLMs to see if certain parts of the theoretical results still hold when the model complexity drastically increases. \n\nReferences:\n\n[1] Jain, A., Montanari, A., & Sasoglu, E. (2024). Scaling laws for learning with real and surrogate data. arXiv preprint arXiv:2402.04376.\n\n[2] Lin, L., Wu, J., Kakade, S. M., Bartlett, P. L., & Lee, J. D. (2024). Scaling Laws in Linear Regression: Compute, Parameters, and Data. arXiv preprint arXiv:2406.08466.\n\n[3] Berthier, R., Montanari, A., & Zhou, K. (2023). Learning time-scales in two-layers neural networks. arXiv preprint arXiv:2303.00055.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This is a technically solid paper with rigorous mathematical proof. For each of the transition boundaries in the phase diagram, an intuitive explanation is provided to help the readers understand the key idea behind. \n2. An extensive set of numerical experiments are included to justify the theoretical results.", "weaknesses": "One possible drawback of the current version of this paper is that the list of references is incomplete. It seems to the reviewer that the discussion on related work is incomplete and ignores many recent and concurrent work on the theoretical aspects of neural scaling law. See for instance [1,2].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their report, for their comments on directions of improvement, and for the questions. \n\n**Response to weakness:** Yes we agree, the comparison to existing work should be expanded.  We will include a more detailed discussion of existing work and how it compares (see comments to all reviewers).  The suggestions for references are helpful – thank you – and we have made an attempt to integrate them (see the proposed related works section).  We’re happy to have feedback if you believe the works considered are still inappropriate. We provided a comparison with the concurrent work \\[2\\] (see Table attached in pdf) which was released after NeurIPS submission.  \n\n**Response to question (2-layer Neural Network):** With regards to the question, the reference \\[3\\] is very interesting.  It is the first time this author is reading it, but it’s very close to my interests and I will dig back into it after NeurIPS. \n\nIn \\[3\\], if one takes the single-index model to have a suitable decay rate of its Hermite expansion (which I believe is power-law decay of its Hermite coefficients), the gradient flow loss curve would have power-law decay.  That seems like it should open the door to an analysis of one-pass SGD that exhibits similar phenomenology to what we’ve done.   I’m not bold enough to speculate how similar it would be to what we’ve done, because I don’t have a good picture of what the SGD-noise looks like in this setup.  If the SGD noise behaves similarly to the quadratic problem we study, then it could fit naturally as a line through our phase diagram parameterized by the exponent $\\\\beta$ (which would come from the decay rate of the target function).\n\nThat would be a beautiful theorem\\!\n\n\\[2\\] Lin, L., Wu, J., Kakade, S. M., Bartlett, P.L., & Lee, J.D. (2024) Scaling laws for learning with real and surrogate data. arXiv preprint arXiv:2402.04376.\n\n\\[3\\] Berthier, R., Montanari, A., & Zhou, K. (2023) Learning time-scales in two-layers neural networks. arXiv preprint arXiv:2303.00055.\n\n**Response to limitation:** A deeper empirical investigation of LLMs would also interest this author, who hopes it can be done.  This is certainly a limitation; also estimating the alpha (and worse) estimating beta are serious obstructions in using the results of this paper quantitatively to do optimal model-parameter decision making.  However, as a matter of better understanding the training and optimization of LLMS, we agree this is an important direction of investigation.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rB1AL9IcPB", "reviewer": "Reviewer_ahLt", "summary": "This submission studies the generalization error dynamics of one-pass SGD in a sketched linear regression setting, where the data and target signal are distributed according to certain power laws, and SGD optimizes a linear model on top of a Gaussian random projection. Using random matrix theoretical tools, the authors precisely computed the asymptotic generalization error of the SGD iterates in high dimensions; this reveals various scaling laws and allows the authors to characterize the compute (flop) optimal frontier.", "questions": "See Weaknesses.", "limitations": "See Weaknesses.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is an emergency review, so I shall simply state that this is probably the most interesting submission in my batch and should be accepted.", "weaknesses": "My main concern is that the authors do not adequately discuss the overlap with prior results.\n\n1. Generalization error of the random features model under various source and capacity conditions has been extensively studied. For instance, (Rudi and Rosasco 2016) derived scaling laws of random features regression with respect to the model width and number of training data, and this result is later extended to SGD in (Carratino et al. 2018), taking into account the scaling of iteration number. The authors should explain the similarity and differences in the findings to highlight the advantage of a precise analysis.  \n* (Rudi and Rosasco 2016) *Generalization Properties of Learning with Random Features.*  \n* (Carratino et al. 2018) *Learning with SGD and Random Features.*  \n\n2. If we do not take optimization into account, then neural scaling laws in the form of $(\\text{data}^{-\\beta} + \\text{param}^{-\\gamma})$ have been established in many prior works on nonparametric regression (Schmidt-Hieber 2017) (Suzuki 2018) -- these are rigorous versions of the hand-wavy arguments in (Bahri et al. 2021) which the authors cited. \nIf we interpret the number of training data to be the same as the iteration number, can we obtain similar plots on the compute-optimal front as reported in Figure 2(a)(b)?  \n* (Schmidt-Hieber 2017) *Nonparametric regression using deep neural networks with ReLU activation function.*  \n* (Suzuki 2018) *Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality.*  \n\nSome additional questions:\n\n1. In light of empirical findings that training small models for a longer time can be beneficial, can the authors comment on the possibility of extending this analysis to the multiple-pass setting? In the kernel regression literature, it is known that multi-pass SGD has statistical superiority (Pillaud-Vivien et al. 2018).  \n* (Pillaud-Vivien et al. 2018) *Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes.*\n\n2. Does the sample size scaling match the minimax optimal rate in (Caponnetto and de Vito 2007) in certain regimes?  \n* (Caponnetto and de Vito 2007) *Optimal rates for regularized least-squares algorithm*. \n\n3. What are the technical challenges to show the asymptotic equivalence between the SGD dynamics and the deterministic equivalent description that the authors analyze?\n\n4. Can the authors comment on the restriction to proportional $v,d$? Why is there a sharp transition at $2\\alpha=1$ that decides the scaling of $d$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments which were very helpful. We address these below. Because there was a lot of depth in the questions raised, we needed additional characters to respond adequately so below is the first part of the response. *There will be an additional “Official Comment” with the remaining response.* \n\n**Response to weakness:** Yes we agree, the comparison to existing work should be expanded.  We will include a more detailed discussion of existing work and how it compares.  We will also include a section detailing how these SGD-generalization bounds compare to optimized non-algorithmic bounds (especially to optimal ridge regression).  The suggestions for references are super helpful – thank you – and we have made an attempt to integrate them.   We’ll outline the results of our attempt to answer your question in the points below.  We’re happy to have feedback if you believe the works considered are still inappropriate.  \n\nRegarding the specific suggestions, thanks, many are new to us.  We will formulate our response partly based upon the concurrent article \\[1\\], which features a sharp analysis of ridge regression on a problem with the capacity/source conditions and which improves over Rudi-Rosasco.  Note the source/capacity conditions are not meaningful for $2\\\\alpha \\< 1$, so we restrict the discussion to phases Ia/II/III ($2\\\\alpha \\> 1$).\n\nDirectly addressing the points you have made below:\n\n1. ***Ridge regression comparison.*** The bounds for ridge regression agree with SGD in phases Ia/II, which is to say that if one takes ridge regression with r-samples, computes the generalization error with the ridge estimator with a O(1) ridge parameter; then the SGD risk curve we compute agrees with the generalization error and the ridge error agree up to constants.  (Using Corollary 4.1 of \\[1\\]).\n\nTo match notation with the source/capacity literature, we'll use our $\\alpha$ parameter (so the capacity is $2\\alpha$) and we'll use the source parameter $r = (\\\\alpha+\\\\beta-0.5)/(2\\\\alpha)$; see also Table 1 in the pdf attached to OpenReview.   We note that phases Ia/II/III correspond to previously observed hardness regimes ($r \\\\in (0,0.5), (0.5,1.0), (1.0, \\\\infty)$)  \n\n   A few comments about this: from \\[1\\], one recovers that the ridge-generalization-error equals the SGD-generalization-error in Phase 1a/II, at all points in the risk curve.  In Phase III, ridge regularization with O(1) ridge has better generalization error than SGD.  The comparison to the Rudi-Rosasco bounds can be seen in (48) of \\[1\\].  They match the generalization errors in Phase Ia, but are not optimal in Phase II/Phase III.\n\n   The Carratino et al. bounds (Corollary 1 of that paper) match the minimax-optimal rates attained by kernel ridge regression, and they effectively show that there are parameter choices for one-pass SGD which match those rates.  We discuss below minimax optimal rates.  \n     \n2. ***Regarding non-parametric regression***: thanks for these references.  Bahri et al. and Maloney et al are indeed not mathematics papers.  We still believe they are quite valuable scientifically to this paper.  We’re happy to clarify how we view their contributions.    \n* Regarding your main question Figure 2, it is **not possible to get this figure by identifying steps with samples.**  It’s super important to plot the x-axis of the curve in FLOPs, or there is no compute-optimal frontier (i.e. each iteration has a cost which is d-dependent).  So without choosing an algorithm which attains the regression bounds in the papers you list and assigning them a computational cost, the problem is not well-posed. \n\n    \n  Now if we are talking about ridge regression with $O(1)$ ridge, then we could assign a computational cost of ($n \\\\times d$), for example using conjugate gradient (CG) (up to log factors).  One could also do this by considering vanishing ridge parameter, but then (since the condition numbers of these matrices grow like $d^{2\\\\alpha}$), the computational cost of computing using CG will increase to $n \\\\times d \\\\times (\\\\min\\\\{ d^{\\\\alpha}, \\\\sqrt{1/ridge}\\\\})$.\n\n    \n  Let’s suppose we continue with ridge parameter $O(1)$, which is morally comparable to one-pass SGD, in that they use the same amount of compute – it’s also comparable in the sense that a non-optimized algorithm like gradient descent on the ell2-regularized-least-square objective will be similar in complexity (and vanilla SGD is surely a non-optimized algorithm).\n\n  In Phase Ia/II, the optimal ridge estimates in \\[1\\] (which agree with Rudi-Rosasco in Phase 1a but not in II) would indeed yield the same curves, treating computational complexity as $n \\times d$ (with $n$ the number of samples and $d$ the dimension).  In Phase Ia, you get the same loss curves as SGD with O(1) ridge regularization, and so you get the same compute-optimal frontiers for CG+O(1)-ridge as SGD.  Incidentally, here you gain nothing by increasing the amount of ridge regularization.\n\n    \n  In Phase III, CG+O(1)-ridge performs better than SGD for small sample counts.  However, if you run SGD to the stopping criteria for which it is compute optimal, it performs the same as CG+O(1)-ridge *with the same choices of parameters/sample counts*.  Now, on the other hand, it could be (and should be) that using CG+O(1)-ridge there is a different compute-optimal frontier curve.\n\n\n  We’re very happy to add the details (and some of the computations) of the comparison of SGD and ridge regression in an appendix, showing how these curves agree/do not agree.  We will also improve the discussion surrounding how compute plays a role, and link it to kernel regression literature.\n\n\n\\[1\\] Defillips, Loureiro, Misiakiewicz. Dimension-free deterministic equivalents for random feature regression.  arXiv: May, 2024", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "O8IH3uBMwq", "reviewer": "Reviewer_wrFd", "summary": "The paper studies a linear random feature model trained on power law data under online SGD. By using a Volterra approach and leveraging deterministic equivalence, they characterize the loss in the high dimensional limit. From this, they extract scaling laws for this model, that determine compute optimality. The show that depending on the spectral decay of the covariates and the task vector, SGD noise as well as finite width effects can effect the scaling of the loss curves with time. A consequence of this is that the optimal allocation of compute can change. By systematically studying finite width and time effects, the authors characterize the scaling laws one should expect in this model.", "questions": "1. It is not obvious without going deep into the appendix why these terms are called $K_{pp}$, $F_{ac}$, etc. It would be much better if you explained this sooner rather than later. \n\n2. If I am not mistaken, the limit that isn't high-dimensional, $2 \\alpha < 1$, would never be encountered for a kernel trained on natural data.  Although there do indeed seem to be interesting phenomena below that line, I am wondering why the authors have decided to so carefully study this? Is is purely out of a desire to characterize the entire $\\alpha, \\beta$ plane? \n\n3. Further, $\\beta > 1$ corresponds to tasks that are ``in the Hilbert space'' of the original $v$ dimensional space. Again, this is never the case for natural data, where the spectral decay is much much slower. If anything this paper seems to tell us that SGD has very little effect on the scaling laws on realistic data.  Please let me know if I am incorrect in this characterization. Otherwise, given the discussion of scaling laws, there will likely be some practitioners that read this paper who are confused about how to interpret $\\alpha$ and $\\beta$. I think the authors would do well to state clearly the relationship between the regions in the $\\alpha$ and $\\beta$ plane and the values one would expect in real datasets.\n\n4. Why are you using the term `SGD frustrated'? In the statistical physics literature this is taken to mean something else entirely. \n\n5. As a smaller comment, the notation for the exponents is quite different from other works. In linear regression its standard to report things in terms of the \"source and capacity\" exponents, where $\\alpha$ is the decay exponent of the spectrum. Of course the authors don't need to change their notation but a table comparing notations with other works would be very useful and go a long way.", "limitations": "Given that this is a toy model of neural scaling laws, I do not expect major societal implications. However, the principled understanding of such scaling properties may well have important impacts on the future of the field.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "The paper investigates an important problem. The reviewer has checked much of the math in the (extensive) appendix. The derivations are technically sound. The conclusions of this paper certainly add meaningfully to the present machine learning literature and our understanding of the role of the optimizer on neural scaling laws. The experiments are beautifully done and add meaningfully to the presentation of the paper. I commend the authors on the care put into the experiments and encourage them to make the code public.", "weaknesses": "There are two primary weakness:\n\n1. The paucity of citations in this work is stunning\n\nMany authors have studied random feature models before and concurrently with the Maloney paper. The set of random feature model papers that deserve a citation are many, and I leave it to the authors to do a thorough review. Certainly Mei and Montanari https://arxiv.org/abs/1908.05355, as well as Bach's paper that also derives the same scalings as Maloney: https://epubs.siam.org/doi/abs/10.1137/23M1558781\nBefore all of this, Hastie et al in their original paper studied random projections on structured data as well:\nhttps://arxiv.org/abs/1903.08560\nAlthough not explicitly calculated, the results of Mel and Pennington give as a special case the generalization error formula in Maloney et al  and was published much earlier. They just didn't calculate the scaling law exponents. \nhttps://openreview.net/forum?id=JfaWawZ8BmX\nSimilar models were studied and exactly solved by Loureiro and colleagues in several papers, for example\nhttps://arxiv.org/abs/2102.08127\n\nMoreover, although I have not read all of the Bordelon paper due to lack of familiarity with DMFT, I can see that they explicitly treat the case of SGD noise. Given the substantial overlap in model and problem studied I think it is worth clarifying sharply what this paper puts forward beyond the initial studies of that one.\n\nI think this work is important. Putting it in the context of works that came before is also important. The authors are hurting the reception of their paper in the broader community by citing so sparsely. \n\n2. Although the readability of this paper in the main text is reasonable, the accessibility of the appendix is quite poor. \n\nThe first section deriving the Volterra equation is written quite clearly and accessibly. From there forward, it becomes increasingly impossible to read. \n\nBy hopping around the theorems and propositions one can eventually recover your bounds on the forcing function and the kernel function. I strongly recommend restructuring the order of your theorems and propositions. I also strongly encourage an \"overview of proofs\" to start the appendix off so that a reader can navigate the dense math more carefully. \n\nThe contour presented in Figure 7 comes out of nowhere. Even after reading most of this paper several times over I still have no idea how the authors arrived at it. I've managed to reproduce most of the results and I don't need this type of analytic contour argument at all. \n\n\nIf these two concerns can be addressed, I will be happy to raise my score. Specifically, I would like the authors to list all of the relevant papers that they will cite in the revised draft, and I would strongly encourage them to follow through.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments and suggestions. We address below questions and concerns raised by the reviewer. Because there was a lot of depth in the questions raised, we needed additional characters to respond adequately so below is the first part of the response. *There will be an additional “Official Comment” with the remaining response.*\n\n**Responses to Weaknesses:**  \n\n1. *(Related Work)* We are very happy to add discussion regarding random feature generalization (especially the relations to generalization error bounds which were developed for source/capacity conditions) and SGD complexity on power-law problems, which are absolutely related to this work. **See response to the ‘General Reviewers’ and the attached pdf** for comparison of our notation to source/capacity conditions. \n\n2. *(Accessibility)*  \n   * We will add an introduction to the appendix to guide how the proofs are done.  \n   * The contour is \\`what works.’  We do not believe the contour is absolutely necessary to proving the result; it is a nice technical tool, but not essential.   Indeed – we heuristically derived all the arguments long before we found the contour in the process of formulating the proof.\n\n     The origin of the contour is solving the fixed point equation for $m$.  The ‘kink’ in the contour occurs at real-part $x \\\\approx d^{-\\\\alpha}$. This corresponds to a point of transition in the spectrum of the PLRF matrix: for smaller scales, the self-consistent spectrum forms a spectral bulk.  For larger scales, the self-consistent spectra forms outliers, roughly located at $j^{-2\\\\alpha}$ for integer $j$. In the self-consistent spectra, these outliers actually have densities of width approximately $O(1/sqrt(d))$.\n\n     Now the contour is basically chosen as the closest contour to this axis that makes this transition invisible, which means the imaginary part of the contour is just a bit larger than the inter-eigenvalue spacing, and it means we see a clean power-law everywhere along the contour.  \n\n     One *could* instead not put the kink, but then would have an absolutely continuous part and an \\`\\`approximately’’ pure point part of the spectrum, which is more annoying than anything (mostly because the m function undergoes some relatively high-frequency changes near each outlier, and all this high-frequency excitement turns out to be completely invisible and unimportant to the larger picture).  The method we use to approximate the m is fundamentally perturbative, so matching all the high-frequency changes in m is super-hard; so it’s easier to change the contour and then have a good, smooth ansatz for m.  \n       \n3. *(Comparison with Bordelon et al. \\[1\\])*  \n   We highlight below the main differences between our work and Bordelon et. al \\[1\\]:  \n* Bordelon et. al assumes the functional form for the loss is $n^{-\\\\tau} \\+ d^{-\\\\sigma}$ (see Appendix N, Eq. (153)). Then they use DMFT to find the exponents $\\\\tau$ and $\\\\sigma$. *We prove that the functional form for the loss of power-law random features is* \n\n  $$ P(n,d) \\\\asymp \\\\underbrace{n^{-\\sigma\\_1}}\\_{F\\_{pp}} \\+ \\\\underbrace{n^{-\\sigma\\_2}}\\_{K\\_{pp}} \\+ \\\\underbrace{d^{-\\tau\\_1}}\\_{F\\_0} \\+ \\\\underbrace{ d^{-\\tau\\_2} n^{-\\sigma\\_3}}\\_{F\\_{ac}} $$\n   \n  Note the cross-term $\\\\underbrace{ d^{-\\tau\\_2} n^{-\\sigma\\_3}}\\_{F\\_{ac}}$ which is missing from the functional form for Bordelon and plays an important role in Phase II and III for the compute-optimal curves. Additionally, Bordelon et. al. do not consider phase III, and  the impact of the SGD algorithm through the term $K\\_{pp}$.\n\n* Our work holds for any $\\\\alpha$ and $\\\\beta$ and  Bordelon et. al. only work for the trace class setting, i.e., $2 \\\\alpha \\> 1$. Moreover Bordelon et. al. compute-optimal result agrees with our compute-optimal exponents when $2\\\\beta \\< 1$. This is consistent since the loss curves in Phase Ia only depend on $F\\_{pp}$ and $F\\_0$. The cross term $F\\_{ac}$ and the impact of SGD $K\\_{pp}$ do not appear until Phase II-IV. \n\n  Comparison of $(a,b)$ and $(\\\\alpha, \\\\beta)$ between the two papers\n\n\n\n  ----------------------------------\n  \n        Bordelon, et. al. |   This paper\n  ----------------------------------\n\n\n            b             |    $2\\alpha$ \n\n            a             |    $2\\beta + 2\\alpha$ \n\n\n  We will add a comparison to the text (see also Table 1 in attached pdf of revision). \n\n\\[1\\] B. Bordelon, A. Atanasov, and C. Pehlevan. *A Dynamical Model of Neural Scaling Laws.* arXiv preprint arXiv:2402.01092, 2024\\.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wpkJUB8oh6", "reviewer": "Reviewer_rEuG", "summary": "This submission studies the Power Law Random Feature (PLRF) that depends on three parameters: data complexity, target complexity, and model parameter count. They derive a deterministic closed expression for the dynamics of SGD using a clever mapping to Volterra equations. They are able to determine the compute-optimal frontier for different learning scenarios. The theoretical claims are supported by extensive numerical simulations.", "questions": "As mentioned above, a large part of my concerns resides in the presentation of the results and the framing of the present submission in terms of the related literature. See below for some examples of needed citations/explanations. \n\n\n- Deterministic equivalent at page 2, what is it and how is it used in machine learning theory? Cite reference for this, e.g., [1].\n- What is a \"neural scaling model\". This appears in the first line of the abstract. \n- When introducing PLRF there is no mention to what classical RF looks like [2]. Many works could be cited that use also Random Matrix Theory tools to connect at the previously described deterministic equivalent, e.g. [3] among many others. \n-  [4,5] are two papers that drew phase diagrams for the training dynamics of SGD. Although they do not seem related to the present submission, they deal with the optimal tuning of SGD from a theoretical point of view. \n\nThe setting presented in the manuscript has many limitations-- which is completely acceptable for a primarily theoretical work. However, the technical challenges that the authors would face if they were to lift them are never discussed. For example, square loss, lack of non-linearity in the PLRF, deterministic teacher vector $b$, need for $v>d$, etc. All these assumptions are reasonable, but must be compared to related works on the subject and why it is difficult to lift them. \n\n### Minor points\n- Explain in deeper detail footnote number 6. Why is this the case? \n- The mapping to Volterra equations is nice and I believe it would deserve more space in the main body. \n- Different subfigures might have different aspect ratios (see e.g. Figures 2 and 3). \n### References \n\n- [1] Random Matrix Methods for Machine Learning. Coulliet & Liao 2022, Cambridge University Press. \n- [2] Random Features for Large-Scale Kernel Machines. Rahimi & Recht. NeurIPS 2007. \n- [3] The generalization error of random features regression: Precise asymptotics and double descent curve. Mei & Montanari. Communications on Pure and Applied Mathematics 2021. \n- [4] Online Learning and Information Exponents: On The Importance of Batch size, and Time/Complexity Tradeoffs. Arnaboldi et al. ICML 2024.\n- [5] Dissecting the effects of SGD noise in distinct regimes of deep learning. Sclocchi et al. ICML 2023.", "limitations": "The suggestions for improving the description of the theoretical limitations are given above.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The main strength of this paper stands clearly in being both theoretically and numerically exhaustive. The numerical illustrations and details backing up the theoretical claims are explored in detail both in the main and appendices. Moreover, the questions addressed are of great interest to the theoretical machine learning community.", "weaknesses": "The strong weakness of this submission is the presentation. It is challenging for a non-expert reader to navigate the related literature with only thirtheen references and eleven lines devoted to the related works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Responses to Weaknesses and questions:**  Thank you for your comments.  We will definitely add a more thorough evaluation of related works.  Great catch about Footnote number 6 – it’s actually not true – we’ve removed it.  We’d be very happy to hear any other comments about the content of the paper – time allowing, we will add some discussion in the appendix about batch size, which was a not-fully-explored thread of this paper.\n\nRegarding the questions (square loss, lack of non-linearity in PLRF, deterministic teacher vector $b$, need for $v \\> d$). \\`\\`All these assumptions are reasonable, but must be compared to related works on the subject and why it is difficult to lift them.’’  \n\n1. Extending to square loss and adding a nonlinearity are both very interesting directions of future research, and it would certainly be reasonable to do them after considering the square loss – linear case\\!    \n2. The deterministic teacher vector could be replaced by a random one with neither an increase in complexity, but also no change in phenomenology (if it has the same behavior as $b$).  Perhaps we can add: the goal here isn’t really theory-building, in the sense of covering as wide a class of kernel regression problems as possible.  The goal is to map out as much phenomenology as possible.  So generalizations of the problem-setup which are not expected to change this phenomenology were not prioritized.    \n3. The case of $v\\>d$ is for simplicity and also because we broadly believe it aligns with what one sees in neural scaling laws.  Indeed you can consider another phase when ($2\\\\alpha \\+ 2\\\\beta \\< 1$) with $v \\< d$, but we suspect it is another ‘Phase I’.  The same comment goes for negative $\\\\beta$.\n\nWe agree with the reviewer that more references and a more thorough discussion of background and related work would improve the accessibility of this paper. For that reason we have included 32 references and proposed changes to the related work and background sections (see the general response). In light of these changes, we hope the reviewer will reconsider their score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UQXUiUP0Nc", "reviewer": "Reviewer_9ixz", "summary": "The authors consider a simple scaling model and derive scaling laws for one pass SGD in an asymptotic limit. From the scaling laws they identify several phases and subphases where certain components of the loss dominate and the compute-optimal model parameter count is affected. The loss components are related to the model capacity, SGD noise, and feature embedding. Detailed calculations are performed to completely characterize the behaviors in different regimes and are accompanied by simulations to give supporting evidence. Interestingly large regions of the phase space result in a \"universal scaling\" independent of the problem parameters.", "questions": "1. Is there potential for a more general explanation for universality since the same scaling appears to hold in the Chinchilla scaling law? \n2. Can any of the techniques be extended to analyze more complex models?\n3. Are there any lessons for practical LLM scaling?", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Understanding scaling behavior of learning models is of great theoretical and practical importance. This work provides a very thorough and comprehensive analysis of the simplest, non-trivial model. Despite the simplicity of the model a rich variety of behavior is observed which requires effort to analyze and catalogue. The observations of universality and effects of finite size are interesting and potentially relevant to more realistic settings.", "weaknesses": "1. It is unclear how novel the mathematical techniques are and how general purpose they are, some discussion would be helpful.\n2. It is unclear how related the simple model is to observations about more realistic models so some more commentary could be useful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments and suggestions which were very helpful. We address these below. \n\n1. ***Novelty of Techniques.***  \n   * *Analysis of learning rates via Volterra equations in concert with random matrix theory has appeared before (say \\[10\\]/\\[11\\] in the paper).*  Volterra analysis is not widespread, and it remains to be seen how general purpose they are.  For precise risk curve analysis of stochastic algorithms, they seem useful, including momentum methods \\[1\\].  A more general point of view is needed for analysis of non-quadratic problems, but there is an equivalent system of ODEs reminiscent of mean field theory (this is equivalent to the Volterra description in the least-squares case) which has been used as well \\[2\\].  Generalizing the type of results in this paper to a non-linear setting would require understanding how these systems of ODEs evolve without appealing to convolution-Volterra-theory; these look quite similar for the linear and nonlinear cases, so I would be cautiously optimistic that the risk curve analysis could be adapted to nonlinear PLRF\n\n\n     \\[1\\] Paquette et al. Dynamics of stochastic momentum methods. 2021  \n     \\[2\\] Collins-Woodfin et al.  Hitting the high-dimensional notes: An ODE for SGD learning dynamics on GLMs and multi-index models. 2023\\.  \n       \n\n   * Random matrix theory analyses of generalization errors in random features models are now pretty well-developed, and this paper certainly fits within that tradition. The majority of the technical work and mathematical novelty in this paper is the analysis of the PLRF resolvent, which is a pure random matrix theory question.  After that, there’s a fair bit of asymptotic analysis which is needed, which will probably be common to all analyses of power-law scaling law problems. \n\n     \n\n2. ***Regarding applications to realistic models.*** We’ve also been asking ourselves this question.  Probably the quantitative predictions of this model will be impossible to fit to anything like Chinchilla; one would need to have a way to estimate both $\\\\alpha$ and $\\\\beta$, which is approaching science fiction.  \n\n   Now on the other hand, it is possible (as in Chinchilla) to measure the resulting scaling laws.  One may attempt to vary parameters that could influence  $(\\\\alpha,\\\\beta)$, and see if the scaling laws respond in the way one would expect from this paper.  One might also look for a phase plane of LLM parameters in which the optimal scaling $d^\\* \\= \\\\sqrt{f}$ with $f = $flops changes; we saw that this is possible in some parts of the $(\\\\alpha, \\\\beta)$ plane.\n\n   Another possible complexity is that adaptive and preconditioned methods are all but necessary for training LLMs, and so some effort should be made to establish to what extent the phase diagram we described is affected by different optimizers.\n\n**Responses to Questions:** \n\n1. ***(Deeper pattern to where $d^\\* \\= \\\\sqrt{f}$).***  This is a great question and perhaps one of the biggest mysteries of the phase diagram, given that it appears in 3 distinct regimes.  I can share some possible speculations, but I don’t really know.    \n   * One possible answer is that real-life is closest to $\\\\alpha=\\\\beta$ (or perhaps autoregressive problems are always somewhere close to $\\\\alpha=\\\\beta$), and along this line it just so happens $d^\\*= \\\\sqrt{f}$.    \n   * Potentially, regimes where $d^\\* \\= \\\\sqrt{f}$ are not optimal are a reflection of the algorithm ‘failing’ in some sense, and one should be looking to improve it. Conversely, existing work suggests that Phase Ia might be algorithmically unimprovable – see the discussion above.  \n2. ***(Extensions to more complex models).***  Of course the proof will be \\`\\`in the pudding,’’ but we would guess that the answer is yes – nonlinear power-law-random-features, anisotropic weight matrices, models with some level of feature learning in mean-field scaling.   Existing work on random features regression and 2-layer networks strongly suggests that the extension to the nonlinear case should be solvable.  The case of anisotropic weight matrices should be quite similar mathematically to this work (it mostly comes to mind as a way to better understand the effect of using preconditioned algorithms on scaling laws).  \n3. ***(Practical lessons for LLM scaling).***  We have a few possible lessons:  \n   * We give some further evidence that $d^{\\\\star} \\= f^{½}$ is justified.  \n   * The ‘functional form’ of the scaling laws of the risk curves which is empirically fit to scaling laws should be updated to be $Risk(n,d) \\= c \\+ a\\_1 n^{-b\\_1} \\+ a\\_2 d^{-b\\_2} \\+ a\\_3 d^{-b\\_2} n^{-b\\_3}.$.  The last term looks like $F\\_{ac}$, and is usually dropped.  But it is needed even in this simple setting to get the correct scaling law behavior (in our setting $b\\_2$ is always $1$).  \n   * Finite-dimensional effects in size of parameters (d) exist and potentially have a huge impact on the compute optimal exponents. We see even in our simple model (see Fig. 4). If one is doing empirical scaling laws, then one can easily see measured exponents that change by something like $0.05$ as one increases the FLOP-budget by a factor of $10^9$.  In LLM scaling, this $0.05$ is the same order of magnitude as the observed scaling law itself, and it is not (per se) related to a breakdown of the scaling laws.    \n   * Speculatively: with some hypotheses about which phase one is in, one may be able to determine what is the dominant feature of the loss curve ($F\\_{ac}$ dominated, $F\\_{pp}$ dominated, $K\\_{pp}$ dominated).  This could allow one to determine if in future training runs, how to increase parameter counts or compute.  (Roughly $F\\_{ac}$ is expensive from a compute point of view, and it is cost efficient to increase scale – or reserve compute for other parts of the model when one enters this regime).   Of course, this heuristic is just a hypothesis, based on the work here and needs to be tested.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for all the constructive comments and suggestions for comparison.  All the reviewers requested additional discussion of related work.   
 
We will do the following.

1. Expand our discussion of related work and background in the main text and add a section in the Appendix. A draft of some of these additions is visible here on OpenReview.  *See the “Official Comment” below.*  
2. Add an appendix with quantitative comparisons of the risk curves we derive and related risk curves from the random features literature *(Table 2/3 in attached pdf)*, including a table bridging the notation *(Table 1 attached in pdf)*.

We have responded to each of you with a discussion of the points that you have raised.

**Novelty/Comparison to existing work.**  

* We emphasize that the motivation of the work is *not* kernel/random features regression, but rather explaining *compute scaling laws.* This is why we consider the full $\\alpha, \\beta$-plane.   
* When this work is compared to sample-complexity bounds, it is important to also remember that the estimator has an algorithmic cost. This algorithmic compute cost is what we are capturing in this work. Some works on sample-complexity are not explicit about their algorithm and so some additional work is needed to produce compute scaling laws.  *In response to Reviewer ahLt*, we have done this comparison for ridge regression. We plan to add an appendix containing these comparisons. *See attached pdf*
* While it may not be true in general, for this work the compute scaling laws happen to be corollaries of precise risk curves as a function of samples.  Many of our risk curves are new; they cannot be derived from existing estimates on SGD.  We discuss these in the response to *Reviewer ahLt (in re Caponetto et al.),* the improved works-cited (see *new Related Work section in 'Official Comment to All Reviewers' below*), and **included** a table of comparisons in the PDF.  
* From a mathematical point of view, this paper also contains new random matrix theory: we analyze the (long-established) self-consistent equations for the resolvent of the power-law-random-features covariance matrix.  This has to be done for spectral parameters (the argument of the resolvent) all throughout the spectrum; in contrast, ridge regression requires negative spectral parameters, and this leads to different challenges. *(See also discussion to Reviewer 9ixz)*

*We will add an additional "Official Comment" with the new proposed related work section.*

Meta-review: This paper will become an influential paper of understanding the scaling law research. I would recommend a solid accept.
Decision: Accept (spotlight)