Scaling Laws in Linear Regression: Compute, Parameters, and Data
Authors: Licong Lin
Jingfeng Wu
Sham M. Kakade
Peter Bartlett
Jason D. Lee
Venue: NeurIPS 2024 poster (2024)
Keywords: learning theory
scaling law
deep learning
SGD
optimization
Primary area: learning_theory

Abstract: Empirically, large-scale deep learning models often satisfy a neural scaling law: the test error of the trained model improves polynomially as the model size and data size grow. However, conventional wisdom suggests the test error consists of approximation, bias, and variance errors, where the variance error increases with model size. This disagrees with the general form of neural scaling laws, which predict that increasing model size monotonically improves performance.

We study the theory of scaling laws in an infinite dimensional linear regression setup. Specifically, we consider a model with $M$ parameters as a linear function of sketched covariates. The model is trained by one-pass stochastic gradient descent (SGD) using $N$ data. Assuming the optimal parameter satisfies a Gaussian prior and the data covariance matrix has a power-law spectrum of degree $a>1$, we show that the reducible part of the test error is $\Theta(M^{-(a-1)} + N^{-(a-1)/a})$. The variance error, which increases with $M$, is dominated by the other errors due to the implicit regularization of SGD, thus disappearing from the bound. Our theory is consistent with the empirical neural scaling laws and verified by numerical simulation.

Scaling Laws in Linear Regression: Compute, Parameters, and Data
Licong Lin UC Berkeley Liconglin@berkelly edu
Jingfeng Wu UC Berkeley
Sham M. Kakade
Harvard University
wuujf@berkeley.oo edu
sham@seas hhwvard. edu
Peter L. Bartlett
Jason D. Lee
UC Berkeley and Google DeepMind peter@berkeley. edu
Princeton University
jasonlee@princeton.. edu
Abstract
Empirically, large-scale deep learning models often satisfy a neural scaling law: the test error of the trained model improves polynomially the model size and data size grow. However, conventional wisdom suggests the test error consists of approximation. bias, and variance errors, where the variance error increases with model size. This disagrees with the general form of neural scaling laws, which predict that increasing model size monotonically improves performance.
We study the theory of scaling laws an infinite dimensional linear regression setup. Specifically,
consider model with M parameters linear function of sketched covariates. The model trained by one-pass stochastic gradient descent (SGD) using N data. Assuming the optimal parameter satisfies Gaussian prior and the data covariance matrix has a power-law spectrum of degree > 1, we show that the reducible part of the test error is O(M (a-1) + N (a- 1//).. The variance emror, which increases with M, is dominated by the other errors due to the implicit regularization of SGD, thus disappearing from the bound. Our theory is consistent with the empirical neural scaling laws and verified by numerical simulation.
Introduction
Deep learning models, particularly those large scale, pivotal in advancing the state-of-the- art across various fields. Recent empirical studies have shed light on the so-called neural scaling laws [see 26, 21, for example], which suggest that the generalization performance of these models improves polynomially as both model size, denoted by M, and data size, denoted by N, increase. The neural scaling law quantitatively describes the population risk
R(M, N) R' +
C1
C2
Ma
Na
where R" is positive irreducible risk and C1, C22 01, G2 are positive constants independent M and N. For instance, by fitting the above formula with empirical measurements in standard large- language benchmarks, Hoffmann et al. [21] estimated a RJ 0.34 and a2 ze 0.28, while Besiroglu al. [7] estimated that a 0.35 and d2 0.37. Though the exact exponents depend the tasks, neural scaling laws in (1) are observed consistently in practice and are used as principled guidance to build otate-of-the-art models, especially under compute budget [21].
From the perspective of statistical learning theory, (1) is rather intriguing. Standard statistical learning bounds [see 30, 41, for example] often decompose the population risk into the sum of irreducible
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

3-1.5
a=2.0
1.6
1.35
102
1.30
1.5
Model size (M)
1.25
1.4
R
Model size
102
1.20 19
1.3
1.15
1.10
1.2
1.05
101
10a
10'
10
10- Number of effective samples (Nan)
10a
Number of effective samples (Nat)
The expected risk (Risk) of the last iterate of (SGD) versus the effective sample size Natt and the model size M for different power-law degrees The expected risk is computed by averaging over 1000 independent samples of (w", .). We fit the expected risk using the formula Risk o² + cı r/ c2/N22 a 1.5, d 20000, the fitted exponents are (as, a2) (0.54, 0.34) x (0.5, 0.33). Right: For a = 2, d 2000, the fitted exponents are (01, 02] = (1.07, 0.49) = (1.0, 0.5). Note that the values of (01, 02) are close to our theoretical predictions (a (a-1,77 1/a) in both cases, verifying the sharpness of our risk bounds. More details can be found in Sections 4 and
Figure 1:
via minimizing the Huber loss as in [21]. Parameters: a 1, 0.1. Left:
error, approximation error, bias error, and variance error (some theory replaces bias and variance errors by optimization and generalization errors, respectively) as in the form of
c(M) Nos
R(M, = R +
+
+
M
No2
approximation
hias
where @1, d22 ag are positive constants and c(M) is measure of model complexity that typically increases with the model size M. In (2), the approximation error is induced by the mismatch of the best-in-class predictor and the best possible predictor, hence decreasing with the model size M. The bias error is induced by the mismatch of the expected algorithm output and the best-in-clate predictor, hence decreasing with the data size N. The variance error measures the uncertainty of the algorithm output, which decreases with the data size N but increases with the model size M (since the model complexity (M) increases).
A mystery. The empirical neural scaling law (1) is incompatible with the typical statistical learning theory bound (2). While the two eтror terms in the neural scaling law (1) can be explained by the approximation and bias errors in the theoretical bound (2) respectively, it is not clear why the variance error is unobservable when fitting the neural scaling law empirically. This difference must be reconciled, otherwise, the statistical learning theory and the empirical scaling law make conflict predictions: as the model size M increases, the theoretical bound (2) predicts an increase of variance error that eventually causes increase of the population risk, but the neural scaling law (1) predicts a decrease of the population risk. In other words, remains unclear when to follow the prediction of the empirical scaling law (1) and when to follow that of the statistical learning bound (2).
Certain prior works provided risk upper bounds that not grow with model size [see for example 36, 12]. Still, their results are insufficient for studying scaling law as those bounds require large model size such that the approximation error ignorable. Moreover, they do provide instance- wise matching lower bounds to verify the tightness of the upper bounds. See detailed discussion in Section 2.
Our explanation. We investigate this issue in an infinite dimensional linear regression setup. We only assume access M dimmennsional sketched covariates given by a fixed Gaussian sketch and their responses. We consider linear predictor with M trainable parameters, which is trained by one-pass stochastic gradient descen! (SGD) with geometrically decaying stepsizes using N sketched data. Assuming that the spectrum of the data covariance matrix satisfies a power-law of degree a > 1 and that the optimal model parameters satisfy a Gaussian prior, we derive matching upper and lower bounds on the population risk achieved by the SGD output (see Theorem 4..). Specifically, we show

---

that
R(M, N) R² + θ 1 ( +
1
min { [M, (Na)
Var θ
(NV))a-
N
leading order given by the sum Approx and Bias
higher order, unobservable
where y = (1) is the initial stepsize used in SGD and ((-) hides log(N) factors. In our bound, the sum of the approximation and bias errors determines the order of the excess risk, while the variance error is of strietly higher order and is therefore nearly unobservable when fitting R(M, N) function of M and N empirically, In addition, our analysis reveals that the small variance error is due to the implicit regularization effect of one-pass SGD [47]. Our theory suggests that the empirical neural scaling law (1) is a simplification of the statistical learning bound (2) in a special regime when strong regularization (either implicit or explicit) is employed.
Moreover, we generalize the above scaling law to (1) constant stepsize SGD with iterate average (see Theorem F.6), (2) cases where the optimal model parameter satisfies anisotropic prior (see Theorem 4.2), and (3) where the spectrum of the data covariance matrix satisfies a logarithmic power law (see Theorem 4.3).
Emprical evidence. Based on our theoretical results, we conjecture that the clean neural scaling law (1) observed in practice is due to the disappearance of variance error caused by strong regularization. Two pieces empirical evidence to support our understanding. First, large language models that follow the scaling law (1) are often underfitted, as the models trained over single pass few passes over the data [27, 31, 9, 39]. When models are underfitted, the variance error tends to be smaller. Second, when language models trained with multiple passes (up to 7 passes), Muennighoff et al. [31] found that the clean scaling law in (1) no longer holds and they proposed more sophisticated scaling law explain their data. This can be explained by relatively large variance error caused by multiple passes.
Notation. For two positive-valued functions f(z) and g(z). we write f(x) S g(x) (and f() (()())) or f()) Z g(x) (and fx) = ((g(r)) if f(z) I cg(z) or f(x) 2 cg(z) holds for some absolute (if not otherwise specified) constant >> O respectively. We write f(z) ~ g(x) (and f(*) = ()(r))) if f(x) S g(x)) S [(x) For two vectors u and v in a Hilbert space, we denote their inner product by (u, v) or u v. For two matrices and B of appropriate dimensions, we define their inner product by (A, B) := tB) We use ||- to denote the operator norm for matrices and fz-norm for vectors. For positive semi-definite (PSD) matrix A and a vector v of appropriate dimension, we write ||v == v T Av. For symmetric matrix A, we use pyy (A) to refer to the j-th eigenvalue of A and r(A) to refer to its rank. Finally, log(-) refers to logarithm base 2.
2 Related work
Empirical scaling laws. In recent years, the scaling laws of deep neural networks in compute. sample size, and model size have been widely studied across different models and domains [20, 35, 26, 19, 21, 46, 31]. The early work by Kaplan et al. [26] first proposed the neural scaling laws of waasforrer--bsee models. They observed that the test loss exhibits power-law decay in quantities including the amount of compute, sample size, and model size, and provided joint formulas in these quantities to predict the test loss. The proposed formulas were later generalized and refined in subsequent works [19, 21, 1, 10, 31J. Notably, Hoffmann et al. [21] proposed the Chinchilla law, that is, (1) with 01 x 0.34 and d2 0.28. The empirical observation guided them to allocate data and model size under a given compute budget. The Chinchilla law is further revised by Besiroglu et al. [7]. Motivated by the Chinchilla law, Muennighoff et al. [31] considered the effect of multiple passes over training data and empirically fitted a more sophisticated scaling law that takes account of the effect of data reusing.
Theory of scaling laws. Although neural scaling laws have been empirically observed over a broad
spectrum of problems, there is relatively limited literature understanding these scaling laws
from a theoretical perspective [37, 4, 28, 22, 42, 29, 23, 8, 2, 32, 17]. Among these works, [37]
showed that the test loss scales as 4//d for regression on data with intrinsic dimension d. Hutter [22]
studied toy problem under which non-trivial power of N arises in the test loss. Jain et al. [23]
3

---

considered scaling laws in data selection. Bahri et al. [4] considered a linear teacher-studen model under power-law spectrum assumption on the covariates, and they showed that the test loss of the ordinary least square estimator decreases following a power law in sample size N (resp. model size M) when the model size M (resp. sample size N) is infinite. Bordelon et al. [8] considered linear random feature model and analyzed the test loss of the solution found by (batch) gradient flow. They focused on the bottleneck regimes where two of the quantities N, M, T' (training steps) are infinite and showed that the risk has power-law decay in the remaining quantity. The problem in Bahri et al. [4], Bordelon et al. [8] can be viewed as a sketched linear regression model similar to ours. It should be noted that both Bahri al. [4] and Bordelon et al. [8] only derived the dependence of population risk on one of the data size, model size, or training steps in the asymptotic regime where the remaining quantities go to infinity, and their derivations are based on statistical physics heuristics. In comparison, we prove matching (ignoring constant factors) upper and lower risk bounds jointly depending on the finite model size M and data size N.
Implicit regularization of SGD. One-pass SGD in linear regression has been extensively studied in both the classical finit-ddimensional setting [34, 3, 14, 16, 25, 24, 18] and the modern high- dimensional setting [15, 6, 48, 47, 44, 45, 40]. In particular, Zou et al. [47] showed that SGD induces an implicit regularization effect that is comparable to, and in certain cases even more preferable than, the explicit regularization effect induced by ridge regression. This is one of the key motivations of scaling law interpretation. From technical perspective,
utilize the sharp saaite and
dimension-fin --ee analysis of SGD developed by Zou et al. [48], Wu et al. [44, 45]. Different from them, we consider sequence of linear regression models with increasing number of trainable parameters given by data sketch. Our main technical innovation is to sharply control the effect of data sketch. Some of our intermediate results, for example, tight bounds the spectrum of the sketched data covariance under the power law (see Lemma 6.2), might be of independent interest.
Prior works investigated linear regression with random features [36, 12]. which can be viewed as a kind of sketched features via random coordinate selection. They mainly focused on the small approximation error regime, where the model size (or the number of features) is much larger than the data size. In comparison, we treat both model size and data size as free variables. Morcover, we provide matching upper and lower bounds while prior works mainly focused on upper bounds. These two innovations are crucial for studying scaling laws that predict test error as a function of both model size and data size. Finally, in the comparable regimes with small or zero approximation error, our excess risk bounds recover the bounds in prior works [36, 12, 33, 15, 13].
3 Setup
We use x E Hi to denote feature vector, where H is finite d-dimensional or countably infinite dimensional Hilbert space, and y E R to denote its label. In linear regression, we measure the population risk of a parameter E Hi by the mean squared error,
R (w) := B (xx w) v)² w W H.
where the expectation is over (x y) P for some distribution P on H x R.
Definition 1 (Data covariance and optimal parameter). Let H == E[xx be the data covariance. Assume that tr(H) and all entries of are finite. Let (At)s20 be the eigenvalues of H sorted in non-increasing order. Let w" arg minw R(w) be the optimal model parameter', Assume that || = (w*)T Hw" is finite.
We only assume access to A -ddimensional sketched covariates and their responses, that is, (Sx, 8). where S E AM x H is a fixed sketch matrix. We focus on the Gaussian sketch matrix?, that is, entries of S are independently sampled from (0, 1/M). We then consider linear predictors with M trainable parameters given by
: R, x x (v. Sx).
where v E R are the trainable parameters. Varying M should be viewed as a linear analog of varying the neural network model size. Our sketched linear regression setting is comparable to the teacher-student setting considered by Bahri et al. [4], Bordelon et al. [8].
If arg min R(-) is not unique, we choose w" to he the minimizer with minimal H-norm.
2 OOr results can be extended to other sketching methods [see 43, for example].

---

We consider the training of fv via one-pass stochastic gradient descent (SGD), that is,
Vi-1 1x V.-1 Vi-1 s Sxi,
V4) v
(SGD)
t= N,
where (Xe: Me) are independent samples from P and (7t) are the stepsizes. We consider popular geometric decaying stepsize scheduler [18, 44],
for fort=1 = N, 7t = 7/2', where l (N///N/ogg///
Here, the initial stepsize is hyperparameter for the SGD algorithm. Without loss of generality, assume the initial parameter Vo = O. The output proof techniques apply other stepsize schedulers (e.g.. polynomial decay) as well, but we focus geometric decay as is known to achieve near uumimax-optimal excess risk for the last iterate of SGD [18].
SGD algorithm last iterate vN. Our
Conditioning on sketch matrix S E M through x > (S vi'vv x), and we denote its risk by
M x H., each parameter v E RM induces a sketched predictor
(M((v)== = R(S v) = ={((s, - VER..
By increasing and N, we have a sequence of datasets and trainable parameters of increasing sizes, respectively. This prepares us to study the scaling law (1) in the sketched linear regression problem, that is, to understand RM A (Vn) as function of both and N.
Risk decomposition. In a standard way, we decompose the risk achieved by the last iterate of (SGD), to the sum of irreducible risk, approximization error, and excess risk as follows,
RvN( min R()) min RM(() min R(.) RRM(v)) min RM (.)
Approx
We emphasize that the irreducible risk is independent of M and and thus can be viewed as a constant; the approximation error is determined by the sketch matrix S, thus depends M but is independent of N; the excess risk depends on both M and N as it is determined by the algorithm.
4 Scaling laws
We first demonstrate scaling-law behavior when the data spectrum satisfies power law. Assumption (Distributional conditions). Assume the following about the data distribution.
A. Gaussian design. Assume that ~ N(,
w". B. Well-specified model. Assume that Ely|x] =ww. Define o² := B(y x w²)²
C. Parameter prior. Assume that w" satisfies prior such that E(w E(w*)@2 =
Assumption 2 (Power-law spectrum). There exists a > such that the eigenvalues of H satisfy
A ARi
Theorem 4.1 (Scaling law). Suppose that Assumptions 1 and 2 hold. Consider M-dimensional sketched predictor trained by (SGD) with samples. Let Nett := N/ log(N) and recall the risk decomposition in (4). Then there exists some a-dependent constant > 0 such that when the initial stepsize 7 S with probability at least ( over the randomness of the sketch matrix S, we have
1. Irreducible = R(w*) o².
2. Approx ~ 1-0
3. Suppose in addition o² Z 1. The expected excess risk (Excess) can be decomposed into a bias error (Bias) and a variance error (Var), namely.
BExcess Bias + +o Var.
5

---

where the expectation is over the randomness of w" and (x,, Wi) Moreover, Bias and Var satisfy
Bias S max {M!-0, (Norry))/a
Bias Z (Narr7) //-1 when (Natr)) S M/c for some constant >> O,
Var min (M, (Neer)))/aa//a /Ness.
In all results, the hidden constants only depend on the power-law degree a. As a direct consequence, when o² x 1, it holds with probability at least 1 - e (2(M) over the randomness of the sketch matrix that
(a-i (MOTT + 0
(Norrt)(a- (1
ERM (VN) - 0²
where the expectation over the randomness of w and (xi, 91))
Theorem 4.1 shows a sharp (up to constant factors) scaling law risk bound under an isotroptic prior assumption and the power-law spectrum assumption. We emphasize that the scaling law bound in Theorem 4.1 holds for every N 2 1. We also remark that the sum of approximization and bias errors dominates ER (vN) - o², whereas the variance error is of strict higher order in terms of both MM and N, and is thus disappeared in the population risk bound.
Optimal stepsize. Based on the tight scaling law in Theorem 4. we can calculate the optimal stepsize that minimizes the risk. Specifically, the optimal stepsize is x when Nort X M and can be anything such that M / S y S when Neir 2 M In both cases, choosing y is optimal. When the sample size is large such that Nott Z M", the optimal stepsize is relatively robust and can be chosen from range.
Allocation of data and model sizes. Following Hoffmann et al. [21]. we measure the compute complexity by MN as (SGD) queries M M-dimensional gradients for N times. Given total compute budget of M = C, from Theorem 6.1 and N := N/ log(NN), we see that the best population risk is achieved by setting setting data size slightly larger than the model size when the compute budget the bottleneck.
@(1), M ((C))(a-1)) and N = O(C*/(a+1)), Our theory suggests
Comparison with [8]. The work by Bordelon et al. [8] considered the scaling law of batch gradient descent (or gradient flow) on teacher-student model (see their equation (14)). Their teacher-student model can be viewed as our sketched linear regression model. However, we consider one- me-paass SGD, therefore our setting the number of gradient steps equivalent to the data size. When we equalize the number of gradient steps and the data size in their equation (14) and set the parameter prior as Assumption IC, their prediction consistent with ours. However, our analysis shows the computational advantage of SGD over batch GD since each iteration requires only 1/N the compute. Bordelon et al. [8] obtained the limit the population risk as two out of the data size, model size, and the number of gradient steps go to infinity based on statistical physics heuristics. In comparison, obtain upper and lower risk bounds that hold for any finite M and N and match ignoring a constant factor depending only on the spectrum power-law degree
Average the SGD iterates Results similar to Theorem 4.1 can also be established for the average of the iterates of online SGD with constant stepsize [34, 16, 25, 24, 48). All results will be the same once replacing the effective sample size Nott in Theorem 4. the sample size N. For more details see Theorem F.6 in Appendix F.
4.1 Scaling law under source condition
The isotropic parameter prior condition (Assumption 1C) in Theorem 4.1 can be generalized the following anisotropic version []]].
Assumption (Source condition). Let (As; vi)isa be the eigenvalues and eigenvectors of with (Miioo in non-increasing order. Assume w" satisfies a prior such that
for # j. E(y;, w w w²) O; and for > O, Eds(y,, w zi for some b 1.

---

A larger exponent b implies faster decay of signal w* and thus corresponds to simpler task [[1]] Note that Assumption IC satisfies Assumption with b a.
Theorem 4.2 (Scaling law under source condition). In Theorem 4.1, suppose Assumption 1C is replaced by Assumption with < b < a a Then there exists some a-dependent constant c > such that when y S c, with probability least 1 -9(M) over the randomness of the sketch matrix S, we have
min { M,, (Nerr
ERM((VN) = o² +
+ +
+
Mb-1
(6
Netr
Blas
Var
where the expectation is over the randomness of w" and (x, v:) and @(-) hides constants that may depend (a.b). b).
When 1 < S a, the tasks are relatively hard (compared to when = a), and the variance error is dominated by the sum of approximation and bias errors for all choices of M, N, and 1. In this case, Theorem 4.2 gives the same prediction about optimal stepsize and optimal allocation of data and model sizes under compute budget Theorem 4.1.
When a < < + the tasks are relatively easy (compared to when b a), and variance remains dominated by the sum of approximation and bias error if the stepsize is optimally tuned. Recall that Y S 1, thus we can rewrite the risk bound in Theorem 4.2 as
min { (M, (Nesr7) 1/a
ERas(VN) 0²
min M, (Natr))//a)--
Notr
min { M, (Narr 1/ |/Norr
M 2 N1/b and Na/b-1 2 2 1,
min { (M, (Norr7)
M S N//h or S Na/b-1
Therefore the optimal stepsize and the risk under the optimal stepsize is
~ Na/bb1 if M Z 1/bb and M / S S 1if Neft
Under the optimally tuned stepsize, the population risk is in the form of
min, ER x² + @(N b)/" + @(M1-b),
which is again in the scaling law form (I). This is expected since optimally tuned stepsize controls the variance error by adjusting the strength of the implicit bias of SGD. Under a fixed compute budget
C' MN, our theory suggests assign M ((C2/(++1) and N @(C*/(++1), and set the
stepsize to 7 ~ ([C(lab)/((+-))
When 2 + 1, the tasks are even simpler. We provide upper and lower bounds in Appendix D.3. However, there exists gap between the bounds, fixing which is left for future work.
Moreover, we note that in the comparable regimes where M is large, the results in Theorem 4.2 match existing bounds on the risk of SGD iterates and ridge estimators [33,
4.2 Scaling law under logarithmic power law
We also derive the risk formula when the data covariance has logarithmic power-law spectrum [5]. Assumption (Logarithmic power-law spectrum). There exists 1 such that the eigenvalues of H satisfy X; = i-1 log (i 1), i O.
Theorem 4.3 (Scaling law under logarithmic power spectrum). Theorem 4.1, suppose Assumption replaced by Assumption 4. Then with probability at least (Q(M over the randomness of the sketch matrix S. we have
min (M,
Nece
ERM (vx) = o² + 0
+ +
Var =
log" (Aaree
log"-1(M)
(ogga=((oorr)))
Nott
where the expectation is over the randomness of w" and (xi, W
7

---

1015
E-4311
0.5
0.46
11.t
Dodkte rege
to-1
sampls
(a) 1.5
(b)
(c) a
The expected risk of the last iterate of (SGD) minus the irreducible risk versus the effective sample size and model size. Parameters a = 7 0.1. (a). (b): = 1.3, d = 10000; (c), (d): a = 2, 1000. The error bars denote the 1 standard deviation of estimating the expected risk using 100 independent samples of (w", S). We use linear functions to fit the expected risk under the log-log scale and report the slope of the fitted lines (denoted by k).
Figure 2:
Theorem 4.3 provides a scaling law under the logarithmic power-law spectrum. Similar to Theo- rem 4.1, the variance error is dominated by the approximation and bias errors for all choices of M, N, and and thus disappeared from the risk bound. Different from Theorem 4.1, here the population risk is a polynomial of (M) and log(NNett?).
Experiments
In this section, we examine the relation between the expected risk of the (SGD) output, the data size N, and the model size M when the covariates satisfy a power-law covariance spectrum. Although our results in Section 4 hold with high probability over S, for simplicity, we assume the expectation of the risk is taken over both w* and S in our simulations. We adopt the model in Section 3 and train using one-pass (SGD) with geometric decaying stepsize (3). We choose the dimension sufficiently large to approximate the infinite-dimensione dimensional case, and the data are generated so that Assumption is satisfied. Moreover, we choose the covariance H E Rdxd to diagonal with for some > 1. From Figure 1, we observe that the risk indeed follows
Нü 1 and tr(H) power-law formula jointly the number of samples and the number of parameters. In addition, the fitted exponents are aligned with our theoretical predictions (a - 1, 1/a) in Theorem 4. Figure shows the scaling of the expected risk in data size (or model size) when the model size (or data size) is relatively large. We see that the expected risk also satisfies power-law decay with exponents matching our predictions. It is noteworthy that our simulations demonstrate stronger observations than the theoretical results in Theorem 4. which only establishes matching upper and lower bounds up to constant factor. Additional simulation results on the risk of the average (SGD) iterates can be found in Appendix F.
Risk bounds under general spectrum
In this section, present output of (SGD). Due to the rotational invariance of the sketched matrix S, without loss generality, assume the covariance H is diagonal with non-increasing diagonal entries. Our main results in Section are directly built on the general bounds introduced here.
general results the upper and lower bounds of the risk of the
Assumption 5 (General distributional conditions). Assume the following about the data distribution.
A. Hypercontracctivtty There exists a 2 1 such that for every PSD matrix A it holds that
Exx AxxT 3 LaIr(H))H.
Misspecified model. There exists o² > O such that B(y - x w xxx H
It is clear that Assumption 1 implies Assumption 5 with 3.
Excess risk decomposition. Conditioning on the sketch matrix S, the training of the sketched linear predictor can be viewed M -ddimensional linear regression problem. We can therefore

---

invoke existing SGD analysis [44, 45] to sharply control the excess risk by controlling the bias and variance errors. Specifically, let define the (w* ddeeendddd) bias error as
N II t=1
Bias w/)
[I SHS
SHw", where v (SHS "''
(5)
SSHS
and the variance error
# (2 2 1/(Natr7)) (Nott7)² Ex,er)(Nnn((( X3
Var
Nots := N/ log(NN,
(6)
Nett
M where (2n) j=1 are eigenvalues of SHST We also let Bias == BBias,w"), where the expectation is over the prior of w Using the existing results on the output of (SGD) in Wu et al. [44, 45], we show that the excess risk in (4) can be exactly decomposed as the sum of bias and variance errors under weak conditions.
Theorem 6.1 (Excess risk decomposition), Conditioning on the sketch matrix S, consider the excess risk in (4) induced by the output of (SGD). Assume vo 0. Then for any w E H,
1. Under Assumptions 5A and 5B and suppose 7 S 1/(ca )) for some constant c >> 0, we have
EExcess S Bias(w") + (ax||w" o
some Under the stronger Assumptions IA and IB and suppose 7 S / //(cotrrSSSS) )) some constant
> O, we have
EExcess Z Bias(w") + Var.
In both results, the expectations of Excess are taken over (Xe: Vt M
Assuming that the signal-to-noise ratio is upper bounded, that is, |/""l///" S variance decomposition of the excess risk is sharp up to constant factors.
then the bias-
The variance error is a nice form and can computed using the following important lemma on the spectrum of SHST. Similar results for logarithmic power-law are also established in Lemma G.6 in Appendix G.
Lemma 6.2 (Power law). Under Assumption 2, it holds with probability at least - -S( that
My (HHSH (H) j j j=1....;,u M.
For any kn < ktt oc, let S M denote the matrix formed by the k +1 kt-th columns of S. We also abuse the notation kt oo for kt d when d is finite. We let H E ((*'="")x("-=S" be the submatrix of H formed by the k- approximation and bias error, we use the following upper and lower bounds to compute their values. Theorem 6.3 (A general upper bound). Suppose Assumption 5 holds. Assume vo 0, r(H) 2 2M and the initial stepsize satisfies ? < 1/(ca tr(SHS for some constant 0. Then for any k1, .2 < M/3, with probability at least 1 e R(M))
&t-th eigenvalues. For the
Eisks di M
Eisey X? M
Approx $
|| 11
Ak+ +
| 11
||
Mary2 Sks Hosr Stg:oo) Mas ( (Sk Ho S st
Bias(w")
l| ///oooo Higiooo
Notty
Theorem 6.4 (A general lower bound). Suppose Assumption holds. Assume vo = 0, r(H) 2 M and the initial stepsize y < <1/(ct((SHS))) for some constant c 0. Then
(
Ew- Approx 2
Ais Ey- Bias(w") 2
Σ
Aa (SHHST)
(A
almost surely, where ( are eigenvalues of H in non-increasing order. (Ra) eigenvalues of SHST in non-increasing order.

---

7 Conclusion
We analyze neural scaling laws in anfnite-dimensionall linear regression. We consider a linear predictor with .M trainable parameters the sketched covariates, which is trained by one-pass stochastic gradient descent with N data. Under Gaussian prior assumption on the optimal model parameter and a power law (of degree derive matching upper and lower bounds on the population risk minus the irreducible error, that is, ((M-(e11) + N (=-a)))/a) In particular, we show that the variance error, which increases with M, is of strictly higher order compared to the other errors, thus disappearing from the risk bound. We attribute the nice empirical formula the neural scaling law to the non-domination of the variance error, which ultimately is an effect of the implicit regularization of SGD.
1) assumption the spectrum of the data covariance, we
Many directions remain open for future study. First, our work limited to the linear model; would be interesting to see whether similar scaling laws can be derived in more complex models, such as random feature models or two-layer networks. Second, we focus on one-pass SGD training, and it is unclear if similar results hold for other optimization methods like accelerated SGD or Adam. Additionally, from a technical perspective. many results in our work depend on the Gaussian assumption and the source condition of the data. Investigating how these assumptions can be relaxed would also be valuable.
Acknowledgements
We gratefully acknowledge the support of the NSF for FODSI through grant DMS-2023505, of the NSF and the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning through awards RMS-2031882 and #8 14639, and of the ONR through MURI award N000142112431. JDL acknowledges support of the NSF CCF 2002272, NSF IIS 2107304, and NSF CAREER Award 2144994. SMK acknowledges gift from the Chan Zuckerberg Initiative Foundation to establish the Kempner Institute for the Study of Natural and Artificial Intelligence; support from ONR under award N000142212377, and NSF under award IIS 2229881.
Bibliography
[1] Ibrahim M Alabdulmohsin, Behnam Neyshabur, and Xiaohua Zhai. Revisiting neural scaling laws in language and vision. Advances in Neural Information Processing Systems, 35:22300- 22312, 2022.
[2] Alexander B Atanasov, Jacob A Zavatone- Veth, and Cengiz Pchlevan. Scaling and renormaliza- tion in high-dimensional regression. arXiv preprint 240.:22005005992 2024.
[3] Francis Bach and Eric Moulines. Non-strongly-convex smooth stochastic approximation with convergence rate o(1/n). Advances in neural information processing systems, 26:773-781, 2013.
[4] Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jachoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. arXiv preprint arXiv:2102.06701, 2021.
[5] Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 2020.
[6] Raphaël Berthier, Francis Bach, and Pierre Gaillard. Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model. Advances in Neural Information Processing Systems, 33:2576-2586, 2020.
[7] Tamay Besiroglu, Ege Erdil, Mathew Barnttt, and Josh You. Chinchilla scaling A replication attempt. arXiv preprint arXiv:2404. 10102, 2024.
[8] Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. dynamical model of neural scaling laws. arXiv preprint arXiv:2402.01092. 2024.
10

---

[9] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1 33:1877-1901, 2020.
[10] Ethan Caballero, Kshitij Gupta, Irina Rish, and David Krueger. Broken neural scaling laws. arXiv preprint arXiv:2210.14882 148991 2022.
[11] Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7:331-368, 2007.
[12] Luigi Carratino, Alessandro Rudi, and Lorenzo Rosasco. Learning with sgd and random features. Advances neural information processing systems, 31, 2018.
[13] Leonardo Defilippis, Bruno Loureiro, and Theodor Misiakiewicz. Dimension-free free deterministic equivalents for random feature regression. arXiv preprint arXiv:240S. 15699, 2024.
[14] Alexandre Défossez and Francis Bach. Averaged least-mean-square: Bias-variance trade-offs and optimal sampling distributions. In Artificial Intelligence and Statistics, pages 205-213, 2015.
[15] Aymeric Dieuleveut and Francis R. Bach. Non-parametric stochastic approximation with large step sizes. The Annals of Statistics, 2015.
[16] Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger convergence rates for least-squares regression. The Journal of Machine Learning Research, 18 (1):3520-3570, 2017.
[17] Elvis Dohmatob, Yunzhen Feng, Pu Yang, Francois Charton, and Julia Kempe. tale of tails: Model collapse as a change of scaling laws. arXiv preprint arXiv:2402.070433 2024.
[18] Rong Ge, Sham M Kakade, Rahul Kidambi, and Praneeth Netrapalli. The step decay schedule: near optimal, geometrically decaying learning rate procedure for least squares. Advances in neural information processing systems, 32, 2019.
[19] Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun, Tom B Brown, Prafulla Dhariwal, Scott Gray, al. Scaling laws for autoregressive generative modeling. arXiv preprint arXiv:2010. 1120000...77,,, /4701, 2020.
[20] Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou. Deep learning scaling predictable, empirically. arXiv preprint arXiv: 1712.0007 2017.
[21] Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv:2203. 2tt.:22203.555666 15556, 2022.
[22] Marcus Hutter. Learning curve theory. arXiv preprint arXiv:2102.04074 2021.
[23] Ayush Jain, Andrea Montanari, and Eren Sasoglu. Scaling laws for learning with real and surrogate data. arXiv preprint arXiv:2402.044 043766, 2024.
[24] Prateek Jain, Praneeth Netrapalli, Sham M Kakade, Rahul Kidambi, and Aaron Sidford. Paral- lelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification. The Journal of Muchine Leurning Research, 18(1):8258-829, 2017.
[25] Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Venkata Krishna Pillutla, and Aaron Sidford. A Markov Chain Theory Approach to Characterizing the Minimax Optimal- ity of Stochastic Gradient Descent (for Least Squares). In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017), 2018.
[26] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836/ 2020.
[27] Aran Komatsuzaki. One epoch is all you need. arXiv preprint (XXi:1906006660 2019.
11

---

[28] Alexander Maloney, Daniel A Roberts, and James Sully. A solvable model of neural scaling laws. arXiv preprint arXiv:2210.16859, 2022.
[29] Eric Michaud, Ziming Liu, Uzay Girit, and Max Tegmark. The quantization model of neural scaling. Advances in Neural Information Processing Systems, 36, 2024.
[30] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[31] Niklas Muennighoff, Alexander M Rush, Boaz Barak, Teven Le Scao, Aleksandra Piktus, Nouamane Tazi, Sampo Pyysalo, Thomas Wolf, and Colin Raffel. Scaling data-constrained language models. arXiv preprint (at::2305.16644 2023.
[32] Yoonsoo Nam, Nayara Fonseca, Scok Hyeong Lee, and Ard Louis. An exactly solvable model for emergence and scaling laws. arXiv preprint 2XXv:2444.175633 2024.
[33] Loucas 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.
[34] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 30(4):838-855, 1992.
[35] Jonathan S Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit. A constructive prediction of the generalization error across scales. arXiv preprint 19Xiv:1909.12673 2019.
[36] Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. Advances in neural information processing systems, 30, 2017.
[37] Utkarsh Sharma and Jared Kaplan. A neural scaling law from the dimension of the data manifold. arXiv preprint arXiv:2004. 10802, 2020.
[38] William Swartworth and David Woodruff. Optimal eigenvalue approximation via sketching. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 145-155,
2023.
[39] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971 2023.
[40] Aditya Vardhan Varre, Loucas Pillaud-Vivie and Nicolas Flammarion. Last iterate convergence of SGD for least-squares in the interpolation regime. In Advances in Neural Information Processing Systems, 2021.
[41] Martin J Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48.
Cambridge University Press, 2019.
[42] Alexander Wei, Wei Hu, and Jacob Steinhardt. More than a toy: Random matrix models predict how real-world neural representations generalize. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, 2022.
[43] David P Woodruff et al. Sketching as a tool for numerical linear algebra. Foundations and Trends@ in Theoretical Computer Science, 10(1-2):1-157, 2014.
[44] Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham M. Kakade, Last iterate risk bounds of sgd with decaying stepsize for overparameterized linear regression. The 39th International Conference on Machine Learning, 2022.
[45] Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham M. Kakade. The power and limitation of pretraining- finetunigg for linear regression under covariate shift. The 36th Conference Neural Information Processing Systems, 2022.
12

---

[46] Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer. Scaling vision transform- ers. Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. pages 22104-12113, 2022.
[47] Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, Dean P Foster, and Sham Kakade. The benefits of implicit regularization from sgd in least squares problems. Advances in Neural Information Processing Systems, 34:5456-5460 2021.
[48] 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-5,, 2023.
13

---

Appendix
Table of Contents
A Preliminary
14
Additional notations comments on data assumptions
A.2 Approximation error
A.3 Bias-variance decomposition
16
A.4 Proof of Theorem 6.1
17
A.5 Proofs of Lemma 6.2, Theorem 6.3 and 6.4
18
B Proofs in Section 4
18
B.1 Proof of Theorem 4.1
18
B.2 Proof of Theorem 4.2
19
B.3 Proof of Theorem 4.3
19
C Approximation error
19
C.I. An upper bound
20
A lower bound
................................
22
C33 A lower bound under Assumption
23
C.4 Examples matching bounds for Approx
24
D Bias error
26
D.1 An upper bound
26
A lower bound
................................
28
D.3 Examples matching hounds for Bias(w")
29
E Variance error
32
F Expected risk the average (SGD) iterates
32
F.1 Matching bounds for the average (SGD) iterates under power-law spectrum
F2 Proofs
34
G Concentration lemmas
38
G.1 General concentration results
38
G.2 Concentration results under power-law spectrum
42
G.3 Concentration results under logarithmic power-law spectrum ................................
43
A Preliminary
In this section, we provide some preliminary discussions and a proof of Theorem 6.1. Concretely, in Section A.1 we discuss our data assumptions and introduce additional notations. In Section A.2, A.3 we derive intermediate results that contribute to the proof of Theorem 6.1. Finally, a complete proof of Theorem 6.1 is contained in Section A.4.
A.1
Additional notations and comments on data assumptions
Tensors. For matrices A, B, D, and X of appropriate shape, holds that
(B = AXB,
and that
(D
C) B
A) (D B & (CA)) X
14

---

CAXBD.
For simplicity, we denote
A 02 = AOA.
Comments on Assumption 2, and Due to the rotational invariance of the Gaussian sketched matrix S. throughout the appendix, we assume w.l.o.g. that the covariance of the input covariates H is diagonal with the (i, i)-th entry being the i-th eigenvalue. Specifically, Assumption 3 can be rewritten as
Assumption 6 (Source condition). Assume H = (he)) is a diagonal matrix with diagonal entries in non-increasing order, and w" satisfies prior such that
for + j, Bw?w" 0; and i 0, WX,, zi for some b > 1.
Now that we assume H diagonal. We make the following notations. Define Hg ==
Agt) E RR(K -A")²
where 0 S k < kt are two integers, and we allow k = cc. For example,
Ho:k diag(A d1 A Ai), Ha diag(
Similarly, for a vector w E H. we have
W +W w E R
A.2 Approximation error
Recall the risk decomposition in (4),
RM(YN) min R(-) + min RM()) min R(-) RM(vN) min RM (.)
Irreducible
Approx
Excess
Lemma A.1 (Approximization error). Conditional on the sketch matrix the minimizer of R (v) is given by
v == (SHST)-ISHW'
and the approximation error in (4) is
Approx min RM (.) min R(-)
(I
I H (SHS ) '''SHH H w
(7)
Moreover, Approx < | almost surely over the randomness S.
Proof of Lemma A. Recall that the risk
R(w) = ((xx, w) - y)²
a quadratic function and that w is the minimizer of R(.), so we have
[xx 62 w Exy + Hw" Exy,
and
R(w) = E((x, w) (x, w²)) 2+ R(w")
H (ww w1 + R(w").
Recall that the risk in restricted subspace
RM R(ST v) E((Sx, v) y)²
also a quadratic function, so its minimizer is given by
v = -E(SS) ESxy
15

---

(SHS)) "Hww"
Therefore, the approximation error is
RM((v*) R(w") Approx
= R(S --)
- RR(w")
(ST v'' ww) )|2
-||H (S (SHS -' "Sww" - w2]l
= =|| s (SHS ''H SSH H w
Finally, since
(I- (SHST) SH ) = I H (SHS -'st' = I,
it follows that Approx < ||w w ll:
A.3 Bias-variance decomposition
The excess risk in (4) can be viewed as the SGD excess risk in an M-dimensional (misspecified) linear regression problem. We will utilize Corollary 3.4 [45] to get bias-variance decomposition of the excess risk. The following two lemmas check the related assumptions for Corollary 3.4 in [45] in our setup.
Lemma A.2 (Hypercontractivity and the misspecified noise under sketched feature). Suppose that Assumptions and 5B hold. Conditioning on the sketch matrix for every every PSD matrix A MRMM
we have
O( A(X) arr (SHS A)SHS
Moreover. for the minimizer of R (v). that is, v defined in Lemma A.I, we have
Ely- -yy-(v* (v" Sx) (Sx) 3 2(a² + ||]W"||H)SS""
The expectation in the above is over (x. y)-
Proof of Lemma A.2. The first part is a direct application of Assumption 5A:
[(Sx) 02 (Sx) 02 (Exx (S AS)xx S
= S (a (HS HSS
a tr (SHST A)SHST.
For the second part, we first show that
E(v - (v", Sx)) x 32
= 2E (w", x) )x)""xx 02 2E w
S ST
x/
= 2 H 2a HH (w" S
H.
where the last inequality is by Assumptions 5A and 5B. From the proof of Lemma A.I, we know that
(H, (w" - ST v*) Approx < ||w'| almost surely.
So we have
E(y- (v', Sx)) 82 2(0 + al|w" H.
Left and right multiplying both sides with S and ST, we obtain the second claim.
Lemma A.3 (Gaussianity and well-specified noise under sketched features). Suppose that Assump- tions IA and 1B hold. Conditional on the sketch matrix S, we have
Sx ( (..S..
Moreover, for the minimizer of RM (v), that is, v* defined Lemma A.I, we have
Ely [x] (Sx,v"), v"), Ely (Sx, v²))² o² Approx 2 o.
16

---

Proof of Lemma A.3. The first claim is a direct consequence of Assumption 1A.
For the second claim, by Assumption 1A and Lemma A. have
E|y/x] = (x, w")
(x.S v²) + (x, w ST
(x,STv") + (x, |-
w*)
(H- H... (H- [ ( HH'w""" (SH + (I-- T
( SHE H H²w"). (8)
Notice that
H H(0,),
by Assumption 1A and that
SH I - - H (SHST)-'SH? = 0,
therefore
Sx SH=SH ix is independent of [I H ( H H
Taking expectation over the second random vector in (8), we find
Ely [Sx]
E[E[y| (SHEH xx, v²) = (Sx, v*).
remains show
Bly (Sx, v²))² = 0² + Approx.
This follows from the proof of Lemma A.1. Specifically,
[v (Sx, v²)) R(S v*)
Approx + R(w")
Approx + o2
o²,
where the second equality is by the definition of Approx and the third equality is by Assumption IB. We have completed the proof.
A.4 Proof of Theorem 6.1
We now use the results in [44, 45] for SGD to obtain the following bias-variance decomposition on the excess risk.
Theorem A.4 (Excess risk bounds). Consider the excess risk in (4) induced by the output of (SGD). Let
Natt N/ log(N), SNR == (l]w*l) I1: |
Then conditioning the sketch matrix for any w E H
1. Under Assumptions 5A and 5B, we have
N II
Datt
BExcess
CU--SSSS (vo v*)
+ (1 + aSNR)o²
Nert
1=1
SHST
when < tr(SSSTTT) for some constant 0.
2. Under Assumptions IA and IB, we have
N
+ + Dott
Excess
2
II - S SSST - v*)
Nott
SHS
when S otr(SHST) for some constant e >> 0.
17

---

In both results, the expectation is over (x,, Be) and
Des: # 2 1/(Ner)))) + (Norr7)² Xy<1/(Norr))
Σ
X3.
where (Az)ā=1 are eigenvalue of SHST. Theorem 6.1 follows immediately by Lemma A.1 and by setting Vo = 0 and plugging the definition of Bias(w) w*) and Var into Theorem A.4.
Proof of Theorem A.4. This follows from Corollary 3.4 in [45] for linear regression problem with population data given by (Sx, y). Note that the data covariance becomes SHS and the optimal model parameter becomes v*.
For the upper bound, Lemma A.2 verifies Assumptions 1A and 2 in [45], with the noise level being x² = 2 + allw"]|(:)
Then apply the upper bound in Corollary 3.4 in [45] (setting their index set IK 0) to get
+ (Ilv" vol SHST + +02) Dott
EExcess &
II (I 7 SHS (vo v*)
Nott
1=1
SHST
We verify that
1|v - vol vollsHST H v 112 2 voll sollsssT
2 H (SHS ) SHw 11 vo SHST
- 2 H 2 + 2 vo SHS
2||w"
1 + 2| /
which implies that
- vollsHs + +
< 2 w I + 2 Vollsss + 2(0² +allw"
< (1 + aSNR)o²
Substituting, we get the upper bound.
For the lower bound, Lemma A.3 shows Sx is Gaussian, therefore it satisfies Assumption IB in Wu et al. [45] with 3 1. Besides, Lemma A.3 shows that the linear regression problem well-specified, with the noise level being
x² = 0² + Approx 2 o².
Although the lower bound in Corollary 3.4 in Wu et al. [45] is stated for Gaussian additive noise (see their Assumption 2'), it is easy to check that the lower bound holds for any well-specified noise as described by Lemma A.3. Using the lower bound in Corollary 3.4 in Wu et al. [45]. obtain
N
Dort
BExcess
[I 7HS (vo - v*)
+
Nott
t=1
SHST
Plugging in 82 2 x² gives the desired lower bound.
A.5 Proofs Lemma 6.2, Theorem 6.3 and 6.4
Lemma 6.2 is proved in Lemma G.4. Theorem 6.3 follows from Lemma C.I and D.I. Theorem 6.4 follows from Lemma C.2 and D.2.
B Proofs in Section 4
B.1 Proof of Theorem 4.1
Proof of part 1. By Assumption 1B and the definition of R(-), we have
R R(w)= TE( (x, w) - -y)² = B((x, w) Ely x)) EE(x,, w) (x. w=))² の² > 2²
B(y BRly xx)²
Note that the equality holds if and only if w w.. Therefore we have min R(.) R(w") =
18

---

Proof of part 2. Part of Theorem 4.1 follows immediately from Lemma C.2.
Proof of part 3. We choose Bias(w") (,",, Var as defined in Eq. (5) and (6) and let Bias Ew Bias(w"), ). Part 3 of Theorem 4. follows directly from the decomposition of the excess risk in Theorem 6.1 (note that ElJw" / x 1), and the matching bounds in Lemma D.3 and E.1.
remains to verify the stepsize assumption required Lemma D.3, Since we have from Lemma G.4 that
2 C3
tr SHS
ΣN
2i=1
for some a-dependent constants C1, C2, C3 with probability at least e (MM, it follows that for any constant Therefore, we have verified the stepsize assumption.
choose 7 S cp for some a-dependent co such that y S ctr(SHST)
Finally, the last claim in Theorem 4.1 follows directly from combining the previous three parts and Theorem 6.1, noting a² X 1. and
Var min M, (Natt7)
(Natez)
X
S (Natt7)) x Bias + Approx
Nost
Nost
under the stepsize assumption S 1. Here the hidden constants may depend on a.
B.2 Proof of Theorem 4.2
Similar to the proof of Theorem 4.1, we have min R(-) o² under Assumption IB. Moreover, by Lemma C.5, D.4 and E. we have with probability at least e (M( that
E Approx !
Bias S max [ (bb1)))
Bias ž (Narry) when (Necry) 1/a < M/3.
Var min (M, (Natr))/a///NN
when the stepsize S. c for some a-dependent constant >> 0. Here the hidden constants in the bounds may depend only on (a, Combining the bounds on Approx, Bias, Var and noting
Var min M, (Na
24 (Natt))
I ([Nrrr))1-b))) x Bias + Approx
Natt
Natt
yields Theorem 4.2. Here in the second inequality, we use the assumption b < a.
B.3 Proof of Theorem 4.3
Similar to the proof of Theorem 4.1, we have min R(-) o² under Assumption IB. Notice that we have < 1 implies y S 1/(tr(SHST) with probability at least 1 - e -Q(s by Lemma G.6. It follows from Lemma C.6, D.5 and E.2 that
E Approx ~ log logo-a M,
Bias < max log--a M, (og""((Nots))))
Bias 2 log 1 (NNrr?) when (Nerr) < M for some small constant > O,
Var ~ min (Norr?) (Necc?)) S (Norrt)/ log" (Narr7) log logg~((rrii (Natr?) Natty
Natt
with probability at least 1 - ( when the stepsize S for some a-dependent constant e > 0. Since Var S Bias and log 1og1~" (ogl="(Narr)) $ log--4 aa M when ( (Na 2 M putting the bounds together gives Theorem 4.3.
C Approximation error
In this section, we derive upper and lower bounds for the approximation error in (4) (and 7). We will also show that the upper and lower bounds match up to constant factors in several examples.
19

---

C.1 An upper bound
Lemma C.1 (An upper bound on the approximation error). Given any S such that r(H) 2 k M, the approximation ervor in (4) (and 7) satisfies
Approx E |/Wiow He.. + (Ho. S. Su.k] Whs Work T)
almost surely, where A = Skone HADo Stroo If in addition & S M/2, then with probability 1 -Q(M)
Eishd + Ak+1 +
Eisk X2 M
Approx S Whooo Ii +
M
where (DiYe= eigenvalues of H in non-increusing order.
Proof of Lemma C.I. Write the singular value decomposition H UAU where A diag (11 >2....} with a 2 >₂ 2 ... 2 and UUT = I. Define $ SU, w U w
Then by Lemma A.1 the approximation error Approx = Approx(S, H, w") satisfies
Approx(S. S, H. w") =
- H (SHST)
SSH Haw w-
I UA (SAS
SAAUT U w
JU(1 - A (SAST) 'SA A w'll "w'l'"
(I- A T (SAST) SSA & Approx A, w").
Since S d. S by rotational invariance of standard gaussian variables, suffices to analyze the case where H = A is diagonal matrix, as the results may transfer to general H by replacing w with
Therefore, from now on we assume w.l.o.g. that H is a diagonal matrix with non-increasing diagonal entries. Define A = SHS
By definition Approx, we have
Approx = [ S (SHS) )
-1 -'SH' H w | 'SH" 1/2 - I, 1/2 w w" H 12)).
= <HH T A
Moreover, for any l E [p]
H 1/22ST Dokk
/ A - 1/ - I,
A
(S H1/
Sk H 1:00
1p
H ST
1:00
1::00
H1/22 S
-1 S H 1/2 I
H H1/2 1/2 A -'
H 1/2
S..
kin0
1:00
H 1:0e
S
A -1
"Sokk H
H 1/2 S S
A
Sk:
H
1/2
Ia-k
1:00
0:k
1:00
1:00
VT
W
(9)
Therefore
U2 + VTT
UV VW
12 VVT
H 1'SSAA'SST
-I, 82 -2
32
W =++VVV)
VTU+ WVT
W2 VTV)
0
and hence
12 U Approx 2
W +
H 1/2 " w 1/2
20

---

= + VV,, 1/2
D.k w., w. w.w.w. 000kk H + 2(W + VVV, H 1/2
Wx, ko00 W W H/
k:0o
We claim the following results which we will prove at the end of the proof.
(W2 VTV, H 1/2 1100 Aooe W.
H
H
1:00
Wx:0 Haxe?
(10)
(U2 VV
1/2 U.k w. u.A.
H 1/2
(H
0:l S A So.al= wou Wo:k: 7
(11)
0..
Note that in claim (11) the inverse A= exists almost surely since r(H 2 r(H) - k 2
by our assumption and Se:c0 E IR IR Mx is random gaussian projection onto RM, First part of Lemma C.I follows immediately from combining claim (10) and (11).
To prove the second part of Lemma C.I, first note that with probability 1 - 1-e-R(Md (Q(M) we have
Pmin ( (A = | c/ Eish d + Au+1 +
Eish X M
M
fore some constant > 0 by Lemma G.2. Moreover, by the concentration of the Gaussian variance matrix (see e.g., Theorem 6.1 in [41]), we have So. 2 1x/5 with probability -M(MM when M/k 2 2. Combining the last two arguments, we obtain
Eised dc
Eise X7 M
So. A 2 Spa
+ AR+1 +
M
Eissdi M
Eiso X7 M
2 l3/
AR+1 +
and therefore
(H + A Sox -1 Woi: Work 1) (1S A -Suo) -1 Work Wo:k ))
< 0:k + + A AoiNo -
24 Lisk dr
Eish X7 M
+ ARtI +
||
(12)
M
with probability 1 - (MM) Combining Eq. (12) with the first part of Lemma C.1 completes the proof.
Proof of claim (10) Note that
L 3 W H H1/3 S Skoo A
K: H.! H!!3 La-k
H k:oc
1/2 S 000 (Su:k ST. +
k:00 St ) - Skicc H 1/2 La-k
3 H 1/2 S S (S H He:00 St ST.oo kko
1/2
Ia < 08-ko
k:ce
1:00
where the last inequality uses the fact that the norm of projection matrices no greater than one. Therefore, we have ||W]|2 < 1. Now, it remains to show
W + V-VV==-V
(13)
as claim (10) is direct consequence of Eq. (13) and the fact that || S 1.
By definition of W in Eq. (9), have
W = =(H)/ 1/2 T - H k:00
1/2
I
12
k:00
1:00
I 2H
1/2 S Stine A
S
ko
1/2
H 1oo0
S
K A
-
HA:00 S 1:00
A -k H H/2
ko0c
k:00
1:00
- 2H
2
k:ok
1/2 S ST. A -S H
1:00
1/2
H 1/2
$:00
S
koo A
- -AAAA -' H k100
By definition of V in Eq. (9), we have
VTV 1 ST
Ho ) A Sk: H h:00
Since So.k S. + A₁ = A, it follows that
0.k
W + VTV
la-k
2H S A
0000
Skoo 1/2
H 1/2
k:00
ST A A-1 'AAA AA-'SS -SSkie H/2
k:00
-a-k
H
1:00 1x0
1/2 S
A
S
kv0e
H
Ri00
1/2
W.
21

---

Proof of claim (11) It suffices to show VVV of U in Eq. (9), we obtain
H S. A S
Using the definition
- H 0:k ST A S.
ST
H
I
0:
S 0.k: k
S 0:k
H
1/2
0:k
H
H
S
0.k
A
Sokk H 0.4
+ So. S - Ao H
0.k
I
H
S A
Su:A
0.k
A S
H 0.4 H 1/2 L
where the second line uses Woodbury's matrix identity, namely
-- S S.. + AA A
S Hp:k + SU. - -S. A
Continuing the calculation of U, have
U Hork ST A So.k
S. A
So:k
Hook 1/2 1
0:k:
H (S
0:1: Sox
H 0:k:
S
So.k]
I H 1/2
Ho 1/2 H
A
So:k]
H 1/2
Dzk
Usk
0:k:
0:k
Therefore,
U2 HHH Hou Hoi: + A [S:kk]
1/2
H 0.k
Ho S. "Sok]]
(14)
Since
S A -11/2 A # 0i
H S. A
S
Sook Ho.k + A
So:k]
ST.AA
-H H + S Soo S A
by Woodbury's matrix indentity, it follows from the definition of V in Eq, (9) that
VV
H 11/2
A S H ST A A H //2 A S
0:k
D.k
= Ho. 1/2 H 0:k
+ S...
S AT
(S H ST. ) So.k H 0:k +
S
A
So:k]
1/2
0.k
= - 1/2 [ S A *So: " A So.(Ho + S.A., A So:k]]
Hog
1/2
(15)
Combining Eq. (14) and (15) yields
U2 + V
112 H + A5 -H 1/2 Hoik
(16)
and therefore
(U2 + W
H 1122 W. aa
W. w 0,0%
122)
(H
ST S 11, wor work ))
C.2 A lower bound
For the approximation error Approx, we have the following result. Lemma C.2 (Lower bound the approximation error). When r(H) 2 M, under Assumption 1C, the approximation error (4) (and 7) sutisfies
Ew Approx
A
where (Aa)dm are eigenvalues of H in non-increasing order.
Proof of Lemma C.2. For any d, following the proof of Lemma C.I, we have
Approx [ /22T A -H'SH
102 H 1/2 (w") H H/2))
and
1/2ST A -SH -
H 1/2 S A 1
0zk D.kk
H 1/2
0:k
Is
H ST A -
0:k
0ik
-1Skioo H 1/2
H 1 S A
k:0c
So:
H
0ck
1/2
H
/2 kooe
S A
kooc
-
H
k:00
1/2
I 1
22

---

(vv Uu w
(17)
Therefore
U2 VVT V WV
UV + VW W VVV
H A S-SH' Lal 122
and
Ew Approx = Ew (U² VV H 1/2
Dik Work Work H 1/2) + Bw (W2 + VVV O:k
Wh:00 Wi:00 H
1/2 1:00/
0:k
+ + (UV + VW, H dik Wosk Wi:00 H
k:00/
= =tr((U²+ W Ho:k) + tr(( + V V)
where the last line uses the fact that Ba (w*)32 Lemma C.I, we further obtain
Ia- Using Eq. (13) and (16) in the proof of
1/2 Ho + So. A So:k oo 1/2 Ho:k) kr:HH) B Approx tr(H 0.k
tr((H + ST. A - So. 11))----- (WH
2 -r((WH =: T3.
where A = Sk:00 H4: S For Ts. we further have
T3 tr(H 1/2
-a-k H
1/2 S A -'
kkoc
1/2
1/2
kiod
1:00
1:o
1:00
kood
2 tr(H
1/2
La-k 1/2 S
S
Skece
k:0c
1:00
k:oe
d-k
44 (LI-
H 1/2
k:oe
k:0e
A
SSHoo H
k:00
1/2
Md++ 1-4-1----0 ( (Hoo)))
where the second line due A Σ A (and hence
-A-1 A ), the third line follows from Von-Neuman's 's inequality. Since M La= H S kine A A S 1/2
kino is projection matrix
such that 2 = M and tr(L.- M) = M, it follows that M has M eigenvalues 0 and d k - M eigenvalues Therefore, we further have
d-k
Ta 2 Σ (M p
A
A=R++MM
for any 1 S d. Letting k = 0 maximizes the lower bound and concludes the proof.
C.3 A lower bound under Assumption
Lemma C.3 (Lower bound on the approximation error under Assumption 3). Under Assumption the approximation error (4) (and 7) satisfies
Ew Approx
A a-b
M=M
where (Di)a= are eigenvalues of H in non-increasing order and the inequality hides some (a, b)- dependent constant.
Proof of Lemma C.3. The proof essentially the same as the proof of Lemma C.2 but we include here for completeness. Let H : [[ be the covariance of the prior on w Following the proof of Lemma C.2, we have
Ey- Approx = Ew- (U² + VT H 1/2 W w H 0:k + Ew- (W2 VTV,H//
Osk Whooe w 1n
1/2
H./ 1/2
+ 2F SVV + VW. H 1/2
H 1/2
W
w 1000
0:k
= =tr((U2 VV
Ho H tr((W? + V V)H HW 1
23

---

where the last line uses Assumption 3 and notice that H. Hw are both diagonal. Next, similar to the proof of Lemma C.2, using Eq. (13) and (16), we derive
B Approx tr(H 1/2
H u:k + A Ho:k 1/2 Ho. H..)) tr tr(WH H
0ik
tr H 0: + So.k A Su:k]" Ho.k) tr(WH k:00 H
2 - tr( H = T3s
where A = Sh:oHHes Stooe For T3, following the same argument for T3s in the proof of
Lemma C.2, we have
k
2 14 (Ta-k
H/22
1:00 S A Sk: 1/2) pd+1-k-i H
N4 (HHH))
Σ
1=++
k=
for any & S d where the last inequality uses Assumption Setting & 0 maximizes the lower bound and concludes the proof.
C.4 Examples on matching bounds for Approx
In this section, we derive matching upper and lower bounds for Approx (defined in Eq. 4 and 7) in three concrete examples: power-law spectrum (Lemma C.4), power-law spectrum with source condition (Lemma C.5) and logarithmic power-law spectrum (Lemma D.5).
Lemma CA4 (Bounds on Approx under the power-law spectrum). Suppose Assumption 1C and hold. Then with probability at least - e (B((M) over the randomness of S
M S (Ew Approx S M
Here, the hidden constants only depend on the power-law degree a.
Proof of Lemma C.4. For the upper bound, by Lemma C.I and noting Ew;? for all i, we have with probability at least -M(M)
Eisk, d M
Eistr 12
Approx x
Σ d
Ab +
kn
M
k>ki
1.1-a
11-2a
1k-a +
k +
An
M
M
k1
+
k
M
for any given h < M/2. Here the hidden constants depend on a. Therefore, letting K = M in the upper bound yields
E Approx S M
with probability at least e ((M))
For the lower bound, we have from Lemma C.2 that
Ew Approx Z
Σ Fraz M i=
This completes the proof.
Lemma C.5 (Bounds on Approx under the source condition).
Suppose Assumption 3 hold. Then with
probability at least (1(M)) over the randomness of S
M1-b S T Approx & M
Here, the hidden constants only depend the power-law degrees a, b.
24

---

Proof of Lemma C.S. For the upper bound, by Lemma C.1 and noting Ew,? g--b for all i, we have with probability at least 1 - (-((M)
E Eisks d
Eisky 12)
M )
Approx
x d,20=b=
Σ
+
AkI+1 +
-klta-b
M
1
Ri
1.l-2a 22
2 k)
1h
+
+
k
+
kj
+ta=b
M
M
hi
k
+
M
for any given hn S. M/2. Here the hidden constants depend on o, b. Moreover, choosing ky = M/2 the upper bound gives
B Approx S M
with probability at least e-0(M)
For the lower bound, we have from Lemma C.3 that
W Approx 2
Σ i=
> M11
This completes the proof.
Lemma C.6 (Bounds on Approx under the logarithmic power-law spectrum), Suppose Assumption hold. Then with probability at least -B(M) over the randomness of
log" 1-a M S Approx 2 log" 1-a log''" M.
Here, the hidden constants only depend on the power-law degree a.
Proof of Lemma C.6. For the upper bound, by Lemma C.I and noting Ew; 1 for all i, we have
with probability at least - e -9(M))
Eisky dr
Eish 12
Approx $
Σ A
+ A +
V
K1
M
M
logg log--a ki
ki
1-
S log 1-0 -1 +
logt-oke
+ kj
log
ki +
ki
M
M
hn
h M
+
log2-a Kı
M
log kn
log ki
S log" 1-a ki
for any given h $ M/2, where the third line uses Eish, X3 S 1/(k1 log k1). Choosing k
M/ M/2, we obtain
E Approx log--aM M
with probability at least - -I(M) Here the hidden constants depend on b. For the lower bound, we have from Lemma C.2 that
Ew Approx
log
2 log 1-a M.
T=M
i=M
Therefore, have established matching upper and lower bounds for Approx.
25

---

D
Bias error
In this section, derive upper and lower bounds for Bias(w*) defined in Eq. (5). Moreover, we show that the upper and lower bounds match to constant factors in concrete examples.
D.1 An upper bound
Lemma D.1 (Upper bound on the bias term). Suppose the initial stepsize 7 ctr(SHST) for some
constant e > 1. Then for any w E H and E [d] such that r(H) 2 k + M, the bias term in (5) satisfies
Bias(w" (()) ) 2 Norry ||v*
Moreover, for any &s S M/3 such that r(H) 2 k + M, the bias term satisfies
|| Nose"
[MM)2(A))] (M
Bias(w") x
+ 1/ IPA
with probability - e-(M), where A& == Sk:oe Hi:o St k:00r (ms(As)) denote the eigenvalues of Ag in non-increasing order for some constant > 1.
Proof of Lemma D.I. Similar the proof of Lemma C.I, can without loss of generality assume the covariance matrix H d λz...., ... Aa) where X; 2 Xÿ for any i 2 j. Let SH 1/2 Ú (A2/2 0) V be the singular value decomposition of SHST where Á == diagf>1. Ag..... da} a diagonal matrix diagonal entries in non-increasing order. Define A == Sa: HA ST.20 Then it follows from similar arguments in Lemma C.1 that A is invertible.
Since
SHS ||2 = 7i 7
SI
for constant by the stepsize assumption, follows that SHS Ohr for all t e [N]. Therefore, it can be verified that
N
II [IN SHS SHHS I [=1
TLM-~NSHST SHS (IM - -HSHS Nai SHS (IM SHS ) =; M,
t=1
and by definition of Bias(w" in Eq. (5), we have
Not 2
Bias(w") ~
II (I im1
SHS )v
(I->SHS*
SHST
SHS
(M. v 02).
(18)
Note that the eigenvalues of are {A,(1 2N J.M Since the function f(x) = xx1 1e(1-19 ) 2Na
is maximized at 20 1/[(2N 1)>] for E [0, 1/7] with f(xo) S 1/(Narr7), it follows that
||M]|2 < (Natt))
(19)
for some constant e 0. The first part of Lemma D.1 follows immediately.
Now we prove the second part of Lemma D.1. Recall that (SHST) -1 "SHw". Substituting
SH
(So: Hock
Sk:zo HA: into v*, we obtain
(M, v 82 (M, ( "SSH"")
w HS (SHST) "''SH
< 2T + 2T2,
26

---

where
Ti = (Work)
So 0.4
(SHS*)
MM((SS - W.k.
(20)
T2 (witod
1:00 (SHS)
( "M(SHS) 1 o Winoo
(21)
We claim the following results which we prove later. With probability 1 (1
C cl
(a
Ti S
(22a)
Nost?
(Ax)
for some constant c > 0.
T3 S
|| orooollli I
(22b)
Combining Eq. (22a), (22b) gives the second part of Lemma D.1.
Proof of claim (22a) By definition of Ti, we have
T <
H 0:k
(SHS ( MMHSS "S. |/
Moreover,
Ho.u:
S How
||M]|2
[SSSS] - Ho.
[[SSS y Ho:
Nott
for some constant e 0, where the last line uses Eq. (19). It remains to show
PM/2 (Ak)
((SHST)-'S Ho: S
(23)
μM MM (As)
for some constant > O with probability 1 Q((M), Since SHS
So... Ho. 0.h + Ag. we have
(SHST)-SS) S Ho. (A,²1 - A S H 0.k
S A S
SS A S Ho.k
A A 0: A S 0:k
+ 0.1 A So -1s
S. A 1
So. Hos
A So. H 0:k
+ S A So.1] - 0:k Ho:k
A So. H S A So
(24)
where the second line uses Woodbury's 's identity. Since
H=1 0:k
So.k ST.AA. A 2 S A Sock:
A
it follows that
H 0:k
+ ST A So.k] 1 < T A Soox]
Therefore, with probability least -D(M)
|A Sus Ho.k
ATAAA Soox1=
S |A ||2 Sack ll2
b.t
S A
Su:
< | # ||2 S llz
||[S A SSuk] -1
| 1|2 So.
| 1|2
Mmin
(S A So.x)
Amin (T A So.
where the last inequality follows from the fact that ||So:1l12
|IST So.kl2 for some constant
> O when & & M/2 with probability least 1 e (MMM) Since Soze is independent of A and the distribution of So. is rotationally invariant, we may write ST, - = E AM-
27

---

where S; #d /M and ( are eigenvalues A₁ in non-increasing order. Therefore, for k - M/3
M
M/2
M/2
cl
So Su:k
S
Σ 5.S
(25)
AM-
AM
XM/2
Aa4/2
;=1
for constant 0 with probability at least e R(M), where in the last line again the concentration properties of gaussian covariance matrices (sec c.g., Theorem 6.1 in [41]). As direct consequence, have
(M/)(AA)
|| | Sock H.. + A 112 S c
(Ax)
with probability at least e (M(M) for some constant c > 0. This concludes the proof.
Proof of claim (22b) By definition of 72 in Eq. (21), we have
T2 = W Ho S
(SHS)
) 1/2 (I SHS 2No (SHS) )-18///1/000 Sk:oc H Winso
I Woo0 Hiv 1:00
(SHS) ) Sko. 1: Wi:
< H k:00 T (SHS)) Sno
1/2
1/20 |
[ 8:00
12 H
where the last line follows from
1/2 ST (SHST) S tnoo kiod
8000 1:
1/2
2 = -|H
1/2 Ho. + Skooe HA:oo Sk:0c) ) Spooo H
kine
1:00
k:na ll
1/2
1/2 ST
1:00 1000 - H2
k:00 1.
D.2 lower bound
Lemma D.2 (Lower bound on the bias term). Suppose w follows some prior distribution and the initial stepsize 7 S ctr(SHST for some constant e Let H = Ew =wT==T Then the bias term in Eq. (5) satisfies
((HHHHHH
Ew Bias(w")
(SHST)
4d,, (1/(NNa)
almost surely, where MN SHS - (122SHHTT 2N11
Proof of Lemma D.2. Adopt the notations in the proof of Lemma D.1. By definition of the bias term, have
Bias(w*)
II
SHS
SHST
(SHS I[ [I
- SHS T) 2N
N
IV (SHS (I
Σ 7SSS
2Nes v*
M SSHS (I- SHS ) 2N 82 = (Mv, v' 82
(26)
where the third line uses IM T 2H > 0w for E [N] established in the proof of Lemma D.I, EN Ti < 2yNarr. and the fact that (1 (1 - v) 2 1 - w for w, v > O. Substituting the definition of v² Eq. (5) into the expression, obtain
Ew Bias(w") 2 Ew- (Mv, 822) Ew- (MN, (SHSS)-'SS 'Hw'' SSW*)63 (82)
28

---

tr(HS (SHS
tr((SS ) ((SHH"HH
PM SM-441(SHH
where the last line Von Neumann's trace inequality. Continuing the calculation, have
HSHH"HHS))
Nu.-Bias(we) w
(SHS MM -
p. ((HSH*HST
Hi (SHST) - 2No.:
((HSHHHSTT)
A
Σ
(SHST
where the first inequality uses Par+i-1l (A) = u4 (A-2) for any positive definite matrix A E RMXxM and the second line follows from the definition of MN and the fact that (1 Ny -2 x when À N/(r)
D.3 Examples matching bounds for bias(w")
In this section, we derive matching upper and lower bounds for Bias(w") in (5) in three scenarios: power-law spectrum (Lemmaa D.3), power-law spectrum with source condition (Lemma D.4) and logarithmic power-law spectrum (Lemma D.5). Recall that we define Bias := Ew (ias(w")..
Lemma D.3 (Bounds on Bias under the power-law spectrum). Suppose Assumption IC and 2 hold and the initial slepsize S etr(SHST) for some constant c > 2. Then with probability at least
1 - e SMM) over the randomness of S
E Bias( w') S max (Narrt))//11, M Ml-a1.
and
En Bias(w") 2 (Nast))
when (a <. for some constant e >> O. Here, all the (hidden) constants depend only on the power-law degree a.
Proof of Lemma D.3. For the upper bound, using Lemma G.5, D.1 and the assumption that Ew?? 1 for all > 0, with probability at least - e-M(M) we have
||
E Bias(w wn) S Eww
+
+|| [ Hegin
Notty
+
Σ A
NarrY
kg
+
hig
1ll-a
Narty
S max (Neer)) 1/a-1 1/-1,, M M
where in the last inequality, we choose h [M/3] (Neer?) 1/a to minimize the upper bound.
When (Nerr)) < M/3, combining Lemma D.2 and G.4 gives the lower bound
(SHHHHHTT)
A4 (SHSST
Ew- Bias(w")) >
Σ
Σ
(SHSTT
14 (SHST)
(Neert((eerr))
(Nec)((Ne))
29

---

2-
AZ
E
(Natrz)
i-a
with probability at least -0()) Here, the hidden constants depend only on a.
Lemma D.4 (Bounds on Bias under the source condition). Suppose Assumption 3 hold and the initial stepsize Y S ctr(SHS for some constant > 2. Then with probability at least 1 - e -1())) over the randomness of
Ew Bias(w") S max (N (1-b)/a M--0},
and
E Bias(w") Z (Notr?) (Natrt) (1-b)/a
when (Natr))2/a < Mo some constant e > 0. In both results, the hidden constants depend only on a, b.
Proof of Lemma D.4. For the upper bound, using Lemma G.5, D.1 and the assumption that (w.l.o.g.)
Ew? 2 2 b for all >> O, with probability at least - - e-((M), we have
[wo. Notty
E Bias(w") S Ew
+
I k2z0o Hegio
k 1lta-b
Σ
Ai ia.ba-b
Nosty
kD
h +lta-b
+ kg-b
Nest?
max
{
(1 M Mb
when b < 1, where the last inequality, we choose l22 [M/3] (Note7) minimize the upper bound.
When (Neze?) 1/2 & M/c for some large constant > 0, combining Lemma D.2 and G.4 yields the lower bound
(((SHHHHST)
(SSH(o+))
Ew Bias w/) 2
(SHST
p. (SHSS
#A, <l/(Nerr)
(a+b)
Σ
Σ
z (Nate7) (1-b//
bb/aa
i-a
(
with probability at least - R(M)
Here, the hidden constants depend only on a, b.
Upper bound when b 2 a a probability at least 1 - -(((M
Following the previous derivations, when b 1, have with
|
w Bias( w*) S Ew
+ || wwo:oo Pltte
Notty
log K2
kig
Notey
log(Narr7))
+ 1-
Notty
where the last line follows by setting [M/3] A (Nott7) When > we have with probability least 1 e (M(M)
Ew Bias(w") S Ew
+ +|| |[ 11 Hagio
Nosty
30

---

1
+ hi2
1-b
Nest
1
M 1-b.
Natry
where the last follows by chooing l/2 M/3 to minimize the upper bound.
Note that there exist non-constant gaps between the upper and lower bounds the bias term in the simple regime where à 2 a + 1. We leave a more precise analysis the bias term for future work.
Lemma D.5 (Bounds on Bías under the logarithmic power-law spectrum). Suppose Assumption 4 hold and the initial stepsize 7 S ctr(SHST) for some constant e 2. Let k := inf(k k log" k 2 NotiT).
Then with probability at least e (M(M) the randomness of
E Bias( (as(("))) ") max 1-a (Nost?), (Ioo"""NNee""" log' 1-a M].
and
Ew Bias(w") ž (Nerr7)
when (Nott7) S M for some sufficiently small constant > 0. Here, all constants depend only on the power-law degree a.
Proof of Lemma D.5. For the upper bound, using Lemma G.7, D.1 and the assumption that Ew?? = 1 for all i > O, with probability at least 1 - --MMM) we have
[|
E Bias(w") S Ew
+
+|| |/Whooo 1ag
Norsy
lz2
+
Σn d kDdAz
Nesty
lo
+ logg lig
NeseT
S max { Dog"""(Neser))) log 1-a M),
where in the last inequality, we choose kn = [M/3] A (N) log" (N to minimize the upper bound.
Recall K" ~ M/ log M (for example we may define inf ls llog 2 M)) in Lemma G.6.
Combining Lemma D.2 and G.6 gives the lower bound
(SSH"HSS) (SHST)
(SH
E Na--Bias(w)) w
Σ
Σ
pi (SHST
tA <1)(Ne))))
t (Nerr)
2 log log -ai
2
Σ
Σ
log i
Ac<I/(Nrt)sskk
1- -loo
2 log 1-1 (Norr?) log (kk)
2 log (Natr?) - Ci log 1-a (M)
with probability at least 1 - e RRM) for some constant C₁ > O. Here, the (hidden) constants depend only on a. Therefore, when (Neer?) 1/a < M for some sufficiently small constant c > O, we have
E Bias(w") 2 (Narrr - e 1og)-((M) 2 logt-a(N) (Norcc)
with probability at least - (Q(M)
31

---

E Variance error
In this section, we present matching upper and lower bounds on the variance term Var defined in (6) under the power-law or logarithmic power-law spectrum.
Lemma E.1 (Matching bounds on Var under power-law spectrum), in Eq. (6) satisfies
Under Assumption 2, Var defined
Var min(M, (Natt7)
Nest
with probability at least 1 1- e -Q(M) over the randomness of S. Here, the hidden constants only depend on
Proof of Lemma E.I. By the definition of Var in Eq. (6) and Lemma G.4, we have
Var #1i, 2 1/(NNer7)) + (Neet?)² Σx, <1/((Nerr) X3
Nott
min
{M, (Nezr?) + (Notc7)) (Nocr))
Natt
min M, (Na
Nott
with probability at least 1 e ((() over the randomness of S. Here the hidden constants may depend on a.
Lemma E.2 (Matching bounds on Var under logarithmic power-law spectrum). Under Assumption Var defined in Eq. (6) satisfies
Var min
{ M, k}
min(M, log (ogr7)))o"((Narr))) (Norry))
Nott
Nott
with probability at least - e-Q(M over the randomness of S, where k == inf & log" k 2 (Net77)) and = hides constants that only depend on a.
Proof of Lemma E.2. Define k* = inf(k: k log 2 M) and let D = #(I, 2 1/(Narr7)) + (Natt7)² Σi, (i)enn(Nen)) 23. By the definition of Var in Eq. (6) and Lemma G.6, we have
Var #1 2 1/(Nerr)) (Notet)² Exye1/(Narr) X3
Nerr
min min
Ness
Nots
with probability at least e- ((M) over the randomness of S, where the second line follows from
NotrY
D # # 2 1/(NNer)))
and
(Nerrr))
か$ Nosty
(Nerr))
Σ
1
Nosty log"(Nerr?)
log" (Narr)))))
20 (Norrr)
johy ())e))(NNer))
when & S M.
Expected risk of the average of (SGD) iterates
In this section, we study the expected risk of the average of (SGD) iterates. Namely, consider a fixed stepsize (SGD) procedure where 7/s y and define vx = Σi v./N. Our goal is to derive matching upper and lower bounds R(vx) in terms of the sample size N and model size M.
32

---

Compared with the last iterate of (SGD) with geometrically decaying stepsizes, we show that the average of (SGD) iterates with fixed stepsize achieves better risk, in the sense that the effective sample size Nett is replaced by N in the bounds (c.f. Theorem 4.1). This may give improvement up logarithmic factors.
We start with invoking the following result in [48].
Theorem E.1 (A variant of Theorem 2.1 and 2.2 in [48]). Suppose Assumption hold. Consider an M -iddeennio sketched predictor trained by fixed stepsize (SGD) with N samples. Let N Zi=o v,/N be the average of the iterations of SGD. Assume vo 0 and o² 2 1. Conditional then there exist
S and suppose the stepsize 7 1/(ctr(SHST)) for some constant Approx, Bias, Var such that
ERM(VN) - 0² Ew- Approx + Bias Vaa,
where the expectation of RM is over w" and V:) and
Approx:= == : Egg
(1 (I- H (SHS) 'SH' H
Ew (Ti + Ta) x Bias S Ew (T2 + T4),
DettN
Var N
and
1
SSSI--SSSSSSS w//) (SHS )-
Ti =
tr
(27a)
N2
1
Ir (II-II-sSH) yM) 2 (SHST)-"Ba )-"Bo)
Te N2
(27b)
1
(II-II-SSH)) /// Bo) tr ((I -I- SSSS )
(//)))).
T3 = N2 tr
(27c)
-I--7SHS N Bo - (SHST DEH.N
T1 ?
tr (Bo
(27d)
B, == vTv
(27c)
DaN. = # #(,, 2 1/(N7)) (2y)²
Σ X3.
(27f)
\s<1/(N<)
where (2g) eigenvalue of THST
See Section F.2.1 for the proof.
For Ti = 1,2,3,4) we also have the following upper (and lower) bounds.
Lemma F.2 (Lower bound on Ti). Under the assumptions and notations in Theorem F.,, we have
(SH'S
E Ti
P4 (SHS
BA.<1/(NN)
almost surely, where ( are eigenvalues of SHS in non-increasing order.
See the proof in Section F.2.2.
Lemma F.3 (Upper bound on T2). Under the assumptions and notations in Theorem F.1, for any k & M/3 such that r rHH) Z + M, we have with probability at least e (Q(M) that
1 (A))(AA)
Te S No MM (Ax)
|Wokkl + // 112 1
where A = Skice H Ho ST.
33

---

See the proof in Section F.2.3. Lemma F.4 (Lower bound on T3). Under the assumptions and notations Theorem F.I, we have
Deff.N
(:(SH'ST)
W T3 2
Σ
N
(.(SHS)
(X,11/(N)
almost surely, where (1e) are eigenvalues of SHS non- non-increasing order.
See the proof in Section F.2.4. Lemma FS (Upper bound on T4). Under the ussumptions and notations in Theorem and assume r(H) 2 M, we have
Dea
T4 2 |
almost surely, where A Sk:00 Hiso 1:00
See the proof in Section F.2.5.
With these results at hand, we ready to derive upper and lower bounds for the risk of the average of (SGD) iterates.
F.1 Matching bounds for the average of (SGD) iterates under power-law spectrum
In this section, we derive upper and lower bounds for the expected risk under the power-law spectrum. Our main result (Theorem F.6) follows directly from Theorem F.l and the bounds on Ti(i 2, in Lemmas F.2 to F.5.
for average iterates of SGD). Suppose Assumption and hold and x² < 1. Then there exists some a-dependent constant e >> O such that when with probability at least -D(() over the randomness of the sketch matrix S, we have
Theorem F.6 (Scaling
ERM (Vx) = o² + O(M2-0) + (((N)))/a-1)
where the expectation is over the randomness of w and (x; 9: )) and ((-) hides constants that may depend on
See the proof in Section F.2.6.
Compared with Theorem 4.1, Theorem F.6 suggests that the average of (SGD) achieves a smaller risk in the sketched linear model-tte the (Norry) is replaced by (Ny) in the bound for the bias term. This is intuitive since the sum of stepsizes E, 7i x Nerry for the geometrically decaying stepsize scheduler while Σ. ?t ~ Nvy for the fixed stepsize scheduler.
We also verify the observations in Theorem F.6 via simulations. We adopt the same model and setup as in Section 5 but use the average of iterates of fixed stepsize (SGD) (denoted by v as the predictor. From Figure 3 and 4 we see that the expected risk ER(vx) also scales following power-law relation both sample size and model size M. Moreover, fitted exponents match our theoretical predictions in Theorem F.6.
F.2 Proofs
F.2.1 Proof of Theorem F.1
Similar to the proof of Theorem A.4, we have the decomposition
R(vN) = x² + Approx + || - v 1
Note that (va) can also be viewed as the SGD iterates on the model y = (Sx, v²) + c, where the noise satisfies
E(E c)² R(v")(())))))) = = +
Therefore, the upper and lower bounds on Bias, Var follow directly from the proof of Theorem 2.1, 2.2 and related lemmas (Lemma B.6, B.11, C.3, C.5) in [48].
34

---

3-1.5
a=2.0
1.30
1.5
1.25
Model size (M)
Model size (M)
102
1.4
1.20
RiSk
102
1.3
1.15
1.2
1.05
101
101
10
10"
10a
10-
10*
Number of samples (N)
Number of samples (N)
Figure The expected risk (Risk) of the average of iterates of (SGD) versus the sample size N and the model size M for different power-law degrees The expected risk is computed by averaging over 1000 independent samples of (w", SS). We the expected risk using the formula Risk -² / + / via minimizing the Huber loss in [21]. Parameters:
1 0.1. 20000, the fitted exponents are (a1: Q2) = (0.59, 0.33) F (0.5, 0.33). Right:
Left: For a = 1.5,
For 2, 2000, the fitted exponents are (a1,az) a2) (1.09, 0.49) (1.0, 0.5). Note that the
values of (a1, (2) are close to our theoretical predictions (a 1, 1 1/a /a) both cases.
km
121
Model viee
Nanter s0nte000
Mode
(a) 1.5
(b) a = 1.5
(c) a = 2
(d) a= 2
Figure 4: The expected risk of the average of iterates of (SGD) minus the irreducible risk versus the effective sample size and model size. Parameters = 1, 0.1. (a), (b): a 1.5, 10000;
(c), (d): a = 2, d = 1000. The errobars denotes the =1 standard deviation estimating the expected risk using 100 independent samples of (w",S) We use linear functions fit the expected risk under log-log scale and report the slope of the fitted lines (denoted by k)).
F.2.2 Proof of Lemma F.2
for any positive definite matrix RMXM Let fi(A) (I (I -1
Since y 1/(ctt(SHSTT) )), have (SHST) ž 0. By definition of Ti and recalling v* -SSS"" have with probability at least (Q(M) that
Ew Ti Ew [w" HS (SHS fi (SSSSHSSSSSSSSSSSSS
= =r ([(SHS f (SHSS) -
Following the proof of Lemma D.2 (by Von Neumann's trace inequality), we have
(*(SH"ST)
Ew- Ti
(S
(SHHST
(A/41/((N) M4 (S
14 (SH'ST
2
Σ
N4 (SHST]
35

---

where the third inequality is due to
N2
N2
\/f((N) (1- (1- 71/4 2
2 (1 (1- 21
(Ei=
1 (1 -2)02
when À < 1/(N)).
F2.3 Proof of Lemma F3
By definition of T2, the fact that 1 N.N = (1 (11x)) Σ En
N-1 x², and recalling v (SHS) )) SHHw.
we have
T2 w HS' A(SHS JSHw',
2 Wook
T b2 So. Howwow + Who H H S S J ) Hivoo Whooh
221
Tb2
where f2(A) = 1 (I 7A)1?/A/N2 for any symmetric matrix e RMM Moreover, have
T21 wo:k H2 SSo. Ho.
[|HHSHS (SHS ) ||(SHST) So.
'S. Ho. Wo.
Using the assumption the stepsize that y 1/(ctr )), we have
N-1
( (SHS
max XE(U.1/71
N
(1 71)
x=0
Σ (1
-1-
max
AE(0.1/1)
N27
==
1
- Ny
(28)
N2,
Combining Eq. (28) with Eq. (23) in the proof of Lemma D.I (note that we assume k S. M/3), obtain
T2 S (M/2(AA))
Nº
Par (Ax)
for some constant c with probability at least (R(M) For T22, we have
T22 Whooo H ) kk:0 H o:00 W ko00
< (SASSSST
(SSS y
112 (Sk:oc H
1/2
H
1/2
inoo ||
1:00
1:00
< |/2(SS T
|SHS |[SSS > - Sko00
1/2
2
w 1:00 HAss"
1100
Since [SHSSSS SHS 1/(ctr(SHST)) )), and
||
N- HHSST
1 by the assumption <
[((HST))1/2s 1o00 H 1122 12 || S 1::0
(SHS - S 1/2
| 1:00 1:00 (So. ST + Skine H S 1:00 )-1 Sk: 1/2
S
k:00
< 1/2 S (Strcc H S )
-'S
1/2 1,
1:00
follows that T22 & || 1 He.. Combining the bounds on T21, T22 completes the proof.
F22.4
Proof of Lemma E44
Let fa(A) = (I 1I-(I-AAM (/-/7)///)/////) for any positive definite matrix A E M Following the
same arguments as the proof of Lemma F.2, we have (SHSS > 0 and
En
>N2 tr ((1
[ N/4 Bo
36

---

Ew (w" HS S (SHS
tr((SHS (SS"
Moreover,
Ew Ti 2 ((HH'S
i= M4 (fs
(SHHST
(
BA<<1/((N) M4
(
2V
Σ
(29)
(SHSS
where the third inequality is due to
NyN2
N2
N
a/fa(A) - - 7A)N/4
2
(1 (1->AJN S SN
Σ -
N/4-1
(1 72);
when À < <1/(N7). Note that
1- (1 x2,) 8 2
- (1 -
1)
2 c 2 5
A 1
7.
1 m 1}.
N
1 72; N(N-4)
728 2
A < 7N1
32
(30)
We thus have
tr (1I (I-(II~SHST)y))
Σ (1- 2
min (Nv),)) 13
i=1
1 N292
= # Ny
} +
Σ
xp= DeatN (31)
{s<1/(N5)
Combining Eq. (31) and (29) completes the proof.
F2.5 Proof of Lemma F.5
HHW in the expression of T4 and noting vo = 0, we have Substituting v (SHS 1 SHw'
T4 tr (Bo - (I - -i-SSHHHTT Bo )M) Dott.N
7N 1
N
DER_N
tr (w" HS (SHST)-'( (I -S-SSHSTTR ( (SHST)-'SHW')
7N
N
tr (w" HS S4SSHS (((SH)))SHw)) DeH.N
(32)
N
where f4(A) = A - (I - ( (A for any symmetric matrix A E M Moreover,
tr (w" HS (SHS SHH"))
< (IA(SSSTTSSE || |[SSS 1S -|w, 1
< (OSSSS)SSHS || [[w,|R
Since
1 2N
(SHS YSHS 1
1 Σ (I- SHS Sy 2
by our assumption on the stepsize, it follows that (w" HS (SHS SSHW*) S w. Combining Eq. (32) and (33) we find
(33)
Ta < W. 2 DaHN
37

---

F.2.6 Proof of Theorem F6
First, by Lemma G.4 we have 1/ 1/tr(SHST) 2 for some a-dependent > 0 with probability at least 1 - e e Therefore we may choose sufficiently small so that y I implies S 1/ /r(SSHS)) with probability at least 1 - e -M((), Now, suppose we have y X 1/ tr(rSSHS ) Following the notations in Theorem F.1, we claim the following bounds on Approx, Bias, Var:
EApprox = M
(34a)
Var min {M, (Na)
(34b)
Bias $ max {M'-s (N>)
(34c)
Bias 2 (Ny))/a-1 when M/ z M/c for some constant 0,
(34d)
with probability at least e R(M) Putting the bounds together yields Theorem F.6.
Proof of claim (34a) Note that our definition of Approx in Thereom F.1 is the same as that in Eq. (4) (and 7). Therefore the claim follows immediately from Lemma C.4.
Proof of claim (34b) This follows from the proof of Lemma E. with Nott replaced by N.
Proof of claim (34c)
By Theorem F.1, Lemma F.3 and F.5, have
2
12
MM//2SS (S Hog ky:oo)
+ Ew / W22000 Hegi + + Dea.N
Bias
S
Ny
PM 02:00 H 122000
k2:00)
N
h2
PM/2 SS Sex:cc H Ho S S
2
kg 1 DeHtN
Ny
PM (S 100 H4 Skg:o0)
with probability at least e- (MM for any l/2 I M/3. Choosing 12 = Mmin and using Lemma G.4 and claim (34b), obtain
Bias S max { {M'- (N7) min {M, (Nv) 1/4
S max { (M''0, (N~) + (N-)
S max { (M'-0, (N7)
with probability at least e C(((M)
Proof of claim (34d) By Theorem F.1 and Lemma F.2, we have
(SH'S (SHST)
Ew Bias
k)<<1/(<N)
When (N>) < M/c for some large constant e >> O, we have from Lemma G.4 that
E E Bias
Σ
Σ
i- > ((N7)
(N-)
i-a
=A:<1/((NN)
CASI1/GN)
with probability at least - e-
G Concentration lemmas
G.1 General concentration results
Lemma G.1. Suppose that S IR is such that
S ~ (0, 1/M).
We allow d
38

---

Let (Ad)s1 be the eigenvalues of H in non-increddt con-increasing order. Let (X:);=1 be the eigenvalues of SHS' in oon-increasing order. Then there exists a constant e 1 such that for every M 2 0 and every O S k < M, with probability 2 1 e e-M(M)) we have
A (1 (2y+
Di M
(V
k X3 + Akt1 +
Eisk 12 M
for every j & M,
c
V
As a direct consequence, for K S MM/c2, we have
for every j S SM, 130- 13-(2,+)
(2
Eisa
Eisk Ao
1
(xg
Eish + M
2
Akt1,
M
where 61 c 2c²..
Proof of Lemma G.I. We have the following decomposition motivated by Swartworth and Woodruff [38] (see their Section 3.4, Proof of Theorem 1).
SHST
So. Ho ST.k + Sk: 1:00
Ho. + Eiskde .I Skere Hisoo
Eizk d
ST 1:00
IM-
M
M
We remark that this decomposition idea has been implicitly used Bartlett al. [5] to control the eigenvalues of Gram matrix. In fact, we will use techniques from Bartlett et al. [5] obtain sharper bound than that presented in Swartworth and Woodruff [38].
For the upper bound, we have
Eisk di
Eish di
My (SHS
s Ms So +
IM +
Sp:00 Ho
M I
M
Ensh A M
Eish A,
رD (Sa: Ha.kS
IIs +
H1:00
II
M
Eisk d
Eiso A7
S 54 (So
IM +
M
where the last inequality is by Lemma G.2. For j I k using Lemma G.3, we have
k Ho s X c V M
Ag-
For <j M, we have
Ms So.k Ho. ST,) = S X3 + +
V
Aj-
M
Putting these together, we have the following for every = 1...,,::
Essr M
(Neti + $1
Eish X2 M
Ms (SHST) S p4 (Sor Ho: +
IM +
Eish d
(V
k
Eish X? M
< A₂ +
IM + c-
A
M
M
Similarly, we can show the lower bound. By the decomposition, we have
My (SHST) 2 Mi Sp. Eise di
Eish di
IM
S Sknce KnDo
ST
IM
M
Eist d; M
Σish do
= μ. Ho STt) +
IM
Skice 11:00
T
IM
k:0c
M
39

---

2 pa (o + Eish>; di
(Mes + v Eish 22
IM c1
M
M
where the last inequality is by Lemma G.2. For j S k, using Lemma G.3, we have
(S,x So: 2 >3 - C2
M Az-
For A: < S M, we have
My Ho S. = =0 A3 Abt1 C2
Xz+
where the last inequality due to X S Ax for 2 k. Putting these together, we have
My (SHS 2 ps Ho.
Σisk d
IM - -1 ( + +1
Σ
Eisk X3
M
M
Eist> M
(Vir V/.iA
Σ Eisk X2 M
2 2
IM c.
>3 + Ak+1 +
M
So far, we have proved the first claim. To show the second claim, we simply apply
for s M/C:
M
2
and
Eisk X²
Eish di
c.
c.
Aut1
M
M
1
Eish> As
M 22²2.
Aut1,
2
in the first claim.
Lemma G.2 (Tail concentration, Lemma 26 in Bartlett et al. [5]). For any k 2 1, with probability at least 1 -IMM),
have
Eish dr
Eise X7 M
Sk Ho SToo
IM
S Abt1 +
M
Moreover, the minimum eigenvalue of S ke HK Stooe satisfies
Pmin (S k:00 HAsoe ST T.oo)) 2 Ak+2M
with probability at least 1 1 (M(M)
Proof of Lemma G.2. The first part of Lemma G.2 is a version of Lemma 26 in [5] (see their proof). We provide proof here for completeness.
We write S
IR MP
(8)
sp), S; ~ N
I
M
1 IM
i i 1.
Since Gaussian distribution rotational invariance, without loss of generality, we may assume
H diag .p...
Then we have
S 1000 H S $1000
Σ X,s,ss
40

---

Fixing unit vector E R", then
Skoce Ho Stice
1>k
where each s vs -LsMM)ssuuauussinnn By Bernstein's inequality, have, with probability 11-8. 8,
Σ (s 12ck
Eish X
2 1
(Me+2
log
1
X
log
1
M
M
By a union bound and net argument on SM, we have, with probability 2 6, for every unit vector v E R.M.
Σ vsT i>k
Eised A
1
(At+I (M + log 2)
+11
Σ x3
(M log 1/2 ))
M
M
So with probability least -((d)), we have
Eisk d;
S Ho
S1:00
Ia
2 M
(ott2 .M +
Σ A3 M
M
2
Σ Eisk A7
Ak+1 +
M
which completes the proof of the first part of Lemma G.2.
To prove the second part of Lemma G.2, it suffices note that
2M
2M+
Sje:0 He ST.00
Σ A > 222+4
Σ
s.ss 2 cd2M+4 IM
ø=++1
i=++
for some constant with probability at least 1 eMMM) where the last line follows from
concentration properties of Gaussian covariance matrices (see e.g., Thereom 6.1 [41]).
Lemma G.3 (Head concentration). With probability at least - c -M(M) we have
for every j S k;
Ho - 211 S
M X
Proof of Lemma G.3. Note that the spectrum of Sa. S is indentical the spectrum of H2/2S] ST
22/2 We will bound the latter. We start with bounding the spectrum of S To 0:k 0sk Su. 0ik
this end, we write 0:k
E k M
as
ss s
1 M I1 :.). 1= M.
$ (S1
SM)
Then repeating the argument in Lemma G.2, we have, with probability 2 ō, for every unit vector R
M
v & So.V - =
Σ
s v)
-1
1. (k log 1 + M (k (K+ log 1 - 8
< M
k: + log(1/5))
M
So have, with probability 2 ((WN),
S(M)
k
| So.k
-1ll2 S M
41

---

This implies that
My (Hgls o. So.
js (Hol
k
(H
+ c1
V
M
My
k M
=
and that
My (H S Su.k H (12) 2 Héj 2
c1 V k
2
= - >z.
We have completed the proof.
G.2
Concentration results under power-law spectrum
Lemma G.4 (Eigenvalues SHST under power-law spectrum). Suppose Assumption 2 hold. There exist a-dependent constants C2 >> 4 > 0 such that
cij S (,(SSS S c2j
with probability at least CR((M))
Proof of Lemma G.4. Let Mf denote the eigenvalues of SHS in an non-increasing order. Using
Lemma G.1 with l = M/c c for some sufficiently large constant and noting that E i' = k- have
- ( 02 M S X3 S ( + M
for every j E [M] for some constants c;, E [2] with probability at least 1 Q(MM) Therefore, for all j < M/e ē for some sufficiently large constant ē > we have
Xj [esj "
with probability at least 1 - e - for some constants č3 24 > O. For j [M/ M). by mono- tonicity the eigenvalues, we have
d $ ÅLMa I Eo (L
M
I Es
C5j
for some sufficiently large constant F > Eअ with probability at least 1 - e R(M), Moreover, using Lemma G.2 with & = obtain
x z AM 2 umin (S Ho T 2 čaλeM 2 (M/2)) ögj
with probability at least e (((M) for some constants Co ē7, C3 > Combining the bounds for j < M/C and L/2 M] completes the proof.
Lemma G.5 (Ratio of eigenvalues of Sk: H ST. under power-law spectrum). Suppose As- sumption 2 hold. There exists some a-dependent constant between the M/ 2-th and M-th -th eigenvalues
O such that for any k 2 1, the ratio
PM/2 1OOD ST.O))
MM (S knoc H S
with probability at least 1 1- (9MM)
42

---

Proof of Lemma G.5. We prove the lemma under two scenarios where ls is relatively small (or large) compared with M.
Let c > 0 be some sufficiently large constant. Applying Lemma G. with Hg replacing H, for kn M/c, we have
3
(AM/2HH + Disko dethle ) + c1 Ako+1+ks
PM/2(Sken (S H HanDo $1:00
2
M
M
k)) * (ko + +:))
+ (ko + +1++0 k-
2
M
V M) - + (k V M) -a (1 V
+ (k V M) aa
M
2 (k (1 M
(35)
with probability at least
e -2))) for some constant Ci > 0.
Case 1: k S M
From Lemma G.2, we have
Umin (S 1000 H Assoo S 2 A4+2M 2 (k M)
with probability at least e (-M)) Therefore
|M/2 Sk:cc H 1:000 S k:00
S
FM (S 1: Ho:00 k:00
with probability at least e (QM) when k/M 1
Case 2: 2 M On the other hand, when is relatively large, using Lemma G.1 with H Hooo replacing H again, obtain
AM+++ + Σisko Aoth
MM (St: HEDD STOO
2 2
C1
M
02 (M + k) - + (Kip + k) 1)1-a
C3 (Ko + +1+
M
with probability at least 1 1 CR(M), where C1, C22 C3 > 0 are some universal constants. Choosing
ku = M/c² for some sufficiently large constant > 0, we further obtain
k
Mad (St: HA Foon) 2 ca
ca(M M + +)
cs (M + k)
M
k
2 c M V k)
L
cr(M V k)
(36)
M
with probability at least 1 - -9((), where (c:) are a-dependent constants. Since
co (M lv
A ez (M (V 2
CB (k (k M
M
when ls is large, i.e., k/M ē for some sufficiently large a-dependent constant 0 that may depend on (ci) we have from Eq. (35) and (36) that
PM/2(S (S 1000 HA ST STOR)
(k ( + & (KV a (1V
$1
MM (S ko H 1:00
M
with probability at least - (9(M)
G.3
Concentration results under logarithmic power-law spectrum
Lemma G.6 (Proof of Theorem 6 in [5]). Suppose Assumption 4 hold. Then there exist some a-dependent constants e, č such that, with probability at least -D(M)
My (SHST E [c jー log "(j + L), j-1 log "(j + 1)]
j Skk,
[c M - log' lo (M), ē. - (M)""((M)
k" < < M,
43

---

where k- ~ MM/log(M Also, there exists some a-dependent constants C1, C2 > 0 such that
C1 S (SH
z j jlog [og"((+11
jlog"(i++)
with probability at least 1- (R(())
Proof of Lemma G.6. The proof is adapted from the proof of Theorem 6 in [5]. We include it here for completeness.
First part of Lemma G.6, In Lemma G.I, for some constant c > 1, choose
Σ A c. M .E.11 }
kt == min 2 0:
i>k
Then with probability -M(M), we have:
1. (2x
Σisk di ) S 5i, 5c
Σisk do M
for every S M,
C1
M
where 61 > 1 is a constant.
When X ~ a=j-llo "(j + 1), we have
kt M/ log(M);
and
Σ A log (kt) ~ log 1-a (M). (M)) i>k
Therefore, we have
Σisk A
2, X3 +
M
log "(++1) jsk,
M log (MM) k' <js M,
where k" x M//og(MM)
Second part of Lemma G.6. Let X denote the i-th eigenvalue of SH²ST for i E [M]. Using Lemma G.1 with k = M/c for some sufficiently large constant co and noting that Eisk Af
EiSh - loo (i S -ー log
2a k. we have
. 2 log
20 + 1) - ट2 M log
2a M
S (j
2a (j + 1) o M M- log 2a M) + δ2 -M log 2a M 2
for every E [M] for some constants o; E [2] with probability least 1 -M(MM) Therefore, for all j s M/ē for some sufficiently large constant ē > 1, we have
À E J0 j log
20 (j++)) + 1)] 2a (j + 1), 2 2 log
with probability least e ((M) for some constants C3, E₁ O. For j [M/ MY. by mono- tonicity of the eigenvalues, we have
x s A S de (1 log 2a
(1) S 8s log 2a M S āe j 2 20 (j + 1)
for some constants C5 > 0 with probability at least 1 - (MMM) Moreover, using Lemma G.2 with = 0, we obtain
X, 2 Am 2 Punin (S H H T 2 č772M 2 ds j log 2a 2" + 1)
with probability least 1 - R(M) for some constants ê7 when [M/2, M]. Combining the bounds for M/ and j LM/ē, M] completes the proof.
44

---

Lemma G.7 (Ratio of eigenvalues of Skice o S under logarithmic power-law spectrum). Suppose Assumption hold. There exists some a-dependent constant such that for any k the ratio between the M/ 22tth and Mith eigenvalues
PM/2 (S 1o HA:00 K:00 Sc
Mad (S k:00 HA:00
11:00)
with probability at least 1 - -
Proof of Lemma G.7. Similar to the proof of Lemma G.5, we prove the lemma under two scenarios where & is relatively small (or large) compared with M.
Let > 0 be some sufficiently large constant. Applying Lemma G.I with Ha replacing H, for
Kn = M/c, we have
Eisko Aitk
HM/2(Sk::e HA 1 -
(AM/2+* +
+ C1 Ako+1+Ks
2
M
M
.M
log" 1-a log' "(Ko +k)
log - "(ko + +1++ +1+1 k)
+ k)
log
+ k) +
2
2
M
kn + k.
log
"MM + k)
log' 1-0 (M + k)
log 1 "M + +k)
(37)
(M + kk)
M
M
with probability at least 1 ((M) for some constant 0i
> 0.
Case 1: S M.
Applying Lemma G.I with HANOO replacing H, for ko = M/c, c, we have
1 2
(AN+** + Σisho Arth
(A (Skoo HASSO ST To
C1 Ako
M
log" "(ko + k))
log "(ko + 1 1-1+ 1))
(M + k)
log (M + -k) +
M
ko 1 + k:
log (M + +k)
log'->(M "M + k)
log ((M)
(M + k)
M
M
log 1-a M
2V
M
with probability at least e A(M) Therefore,
PM/22 ko00 HK: S ST.O)
log 1 (M + k)) 1-
/
log 1-a M
<
Pas (St H KsooS )
M
M
with probability at least e ((M))) when k/M S 1.
Case 2: k P M. On the other hand, when k is relatively large, using Lemma G. with Ha replacing H and ky M/c again, we obtain
par(S HAS (..0 2 2 (ANTH +
Eisko Aith
- cc Ako+1+Rt
M
log--a(ko + k))
log 22 (kio + +1+ k)
2 [ + k) log (M + +k)
C2
M
ko + +1+k k
log 1- 1-a (M + k)
log a "(M + k))
k log aa (k) +
M
M + k
log
(M + k)
M
with probability least R(M),
where c1, C2 Cg > 0 are some a-dependent constants. Therefore,
PM/2( (S (kt H 1:00 ST 1:00)
log 1og--a (M k)) 1 k)
S
PM (Skoo H S )
M
M
with probability at least - e ((M) when k/M 2 1.
45

---

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

---

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

---

Answer: [No]
Justification:
Our experiments are numerical simulations and easy to reproduce.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.o cc/
Soaeeee/ssoSSSemissiieeeeeees wwwmiisssoooooooooooooooooi for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //nips. wttpccccpppccccceeececccccccccct httpa//gggiieee/eeeuuuuiiiiiii /CodeSubmic ssionnollll onPolicy))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide the details for our experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We provide error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
48

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our experiments are numerical simulations and can run with light compute resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https //te:////nnuuee /ttp///eerrrpeeeeeeeeeeeeeeeeeee ctcpppulic//thicccuuudieoooccd
Answer: [Yes]
Justification:
We conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations in their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Our paper is theoretical and we do not expect direct societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
49

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper is theoretical and we do not expect risk of such.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: Our paper is theoretical and does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/dataseta has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
50

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper is theoretical and does not create new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper is theoretical and does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper is theoretical and does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such as the institution conducting the review.
51


Reviews:
[{"review_id": "BdvTphyiRo", "reviewer": "Reviewer_zAqY", "summary": "This paper proves that the scaling laws that occur in deep learning also occur when solving linear regression with SGD.\n\nNamely, suppose:\n* that covariates x are Gaussian with  a power-law spectrum\n* the true labels are given by <w^*, x> for unknown w^*\n* we run one-pass SGD to do linear regression on an M-dimensional sketch of the covariates x\n* we have N data points\n\nThen the risk is upper-bounded by an expression that depends only on the \"bias\" and \"approximation\" terms, with inverse polynomial dependence as observed in neural scaling laws. The \"variance\" term is of lower order (provided the appropriate large step sizes are used).\n\nExtensions to when the data follows a logarithmic power spectrum are also explored.", "questions": "1. How dependent are the results on a geometric step-size schedule? What if a constant schedule, or schedule decreasing as gamma_t = t^{-c} is used instead?\n\n2. In line 232, it is stated that when $1 \\leq b \\leq a$ the tasks are \"relatively hard\", and in line 236 that when $a < b < a+1$ the tasks are \"relatively easy\". Is what is meant here that these tasks are \"relatively harder/easier\" than when a = b?", "limitations": "Yes", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The result is timely and I think will be of high interest to the community, since it sheds insight on why neural scaling laws might occur in practice.\n\nThe paper is well-presented, and the proofs are neatly written and easy to follow.\n\nAs opposed to previous works, this paper provides risk bounds for any network width M, and any number of data points N, instead of taking one of the parameters to infinity and deriving a scaling law in the other parameter.", "weaknesses": "Typo: \"optimally tunned\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for supporting our work! We will fix the typo. We address your concerns as follows. \n\n> Q1. How dependent are the results on a geometric step-size schedule? What if a constant schedule, or schedule decreasing as $\\gamma_t = t^{-c}$ is used instead?\n\nA1. The geometrically decaying stepsize scheduler is known for the last iterate of SGD to achieve a nearly (up to logarithmic factors) minimax optimal excess risk [Ge et al., 2019] in linear regression. Therefore we focus on the geometrically decaying stepsize scheduler. The last iterate of SGD would suffer from a constant variance error if used with a constant stepsize. Moreover, a polynomially decaying stepsize scheduler leads to a worse risk bound compared to a geometrically decaying stepsize scheduler as shown in [Wu et al., 2022a]. We will clarify this in the revision. \n\n---\n\n> Q2. In line 232, it is stated that when $1 \\leq b \\leq a$ the tasks are \"relatively hard\", and in line 236 that when $a < b < a+1$ the tasks are \"relatively easy\". Is what is meant here that these tasks are \"relatively harder/easier\" than when a = b?\n\nA2.  You are correct. We will clarify this in the revision. \n\n---\n**References:**\n\n- Rong Ge, Sham M Kakade, Rahul Kidambi, and Praneeth Netrapalli. The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares. Advances in neural information processing systems, 32, 2019.\n\n- Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham M. Kakade. Last iterate risk bounds of sgd\nwith decaying stepsize for overparameterized linear regression. The 39th International Conference on Machine\nLearning, 2022.", "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": "H5GTZSELBe", "reviewer": "Reviewer_v1rx", "summary": "Motivated by the recent neural scaling law literature, this work investigates the generalization error rate of a sketched linear regression model trained on Gaussian covariates with power-law spectrum under one-pass SGD.\n\nThe main result are lower and upper bounds with matching rates, providing a detailed characterization of the different contributions to the generalization error.", "questions": "- L43-48:\n\n> \"*This difference must be reconciled, otherwise, the statistical learning theory and the empirical scaling law make conflic predictions: as the model size increases, the theoretical bound (2) predicts an increase of variance error that eventually causes an increase of the population risk, but the neural scaling law (1) predicts a decrease of the population risk. In other words, it remains unclear when to follow the prediction of the empirical scaling law (1) and when to follow that of the statistical learning bound (2).*\"\n\nGiven our current understanding of random features regression, this claim is inflated. Several of the works mentioned above [4,6,7], as well as many other works in the random features literature have made the observation that increasing the \"width\" $M$ does not necessarily lead to an increase of variance / overfitting, thanks to the implicit regularization.   \n\n\n- L273-275:\n\n> \"*It is noteworthy that our simulations demonstrate stronger observations than the theoretical results in Theorem 4.1, which only establishes matching upper and lower bounds up to a constant factor.*\"\n\nWhat do you exactly mean in this sentence? What in Figure 2 is stronger than the exponents reported in Theorem 4.1?", "limitations": "The assumptions under which the Theorems hold are clearly stated, but I miss an explicit discussion of the limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and easy to parse. The topic is of interest to the NeurIPS community, and the contribution is timely.", "weaknesses": "In my reading, the two main weaknesses are:\n1. The lack of a wider context. While it makes precise connections to other recent works on the \"*\"theory of neural scaling laws\"*\" such as [Bahri et al., 2021, Maloney et al., 2022, Bordelon et al., 2024], it ignores that the study of generalization error rates in least-squares / ridge regression under source and capacity conditions is a classical topic with an extensive literature. For instance:\n\n     - [1,2,3] have studied both single and multiple pass SGD for least squares regression on Hilbert spaces under source and capacity conditions. This corresponds to the kernel limit $M\\gg N$ in this work. Borrowing the notation from [3] for concreteness, after a quick comparison with the identification of the capacity $\\alpha = a$ and source $r=\\frac{b-1}{2a}$, I believe the \"hard\" and \"easy\" rates from Theorems 4.1 and 4.2 can be retrieved from the one-pass rates in [3].\n     - [4] extends the discussion of [1-3] to the random features approximation of kernels.\n     - The rates from one-pass SGD on least squares can be identified with the rates of ridge regression with an appropriately chosen regularization, which has been exactly characterized in [7]. For example, the blue and orange regions in Figure 1 from [7] correspond to rates in Theorem 4.2 with $\\ell = 1$.\n     - A recent extension of the above to RFs case appeared in [6] (though note some of these rates were known from [7]).\n\n     From the discussion above, it is not really clear what rates are new in this submission. I am willing to change my evaluation if this can be clarified with an in-depth comparison with these works.  \n\n2. The organization of the manuscript in Theorems with \"settings of increasing generality\" can come through as deceptive. Aren't Theorems 4.3, 4.2 and 4.1 corollaries of Theorems 6.3 and 6.4?\n\n\n**References**\n\n- [1] Yao, Y., Rosasco, L. & Caponnetto, A. On Early Stopping in Gradient Descent Learning. Constr Approx 26, 289–315 (2007). https://doi.org/10.1007/s00365-006-0663-2\n- [2] Ying, Y., & Pontil, M. (2008). Online gradient descent learning algorithms. Foundations of Computational Mathematics, 8, 561-596.\n- [3] Pillaud-Vivien, L., Rudi, A., & Bach, F. (2018). Statistical optimality of stochastic gradient descent on hard learning problems\nthrough multiple passes. Advances in Neural Information Processing Systems, 31.\n- [4] Luigi Carratino, Alessandro Rudi, Lorenzo Rosasco. Learning with SGD and Random Features.  Part of Advances in Neural Information Processing Systems 31 (NeurIPS 2018).\n- [5] Hugo Cui, Bruno Loureiro, Florent Krzakala, Lenka Zdeborová. Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime. Part of Advances in Neural Information Processing Systems 34 (NeurIPS 2021).\n- [6] Leonardo Defilippis, Bruno Loureiro, Theodor Misiakiewicz. Dimension-free deterministic equivalents for random feature regression. arXiv:2405.15699.\n- [7] Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. In Advances in Neural Information Processing Systems, pages 3215–3225, 2017.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. We will cite and discuss the relationship between the pointed papers and our work in the revision. However, there are several potential misunderstandings about our results, which we would like to clarify below. \n\n> Q1. [1,2,3] have studied both single and multiple pass SGD for least squares regression on Hilbert spaces under source and capacity conditions. This corresponds to the kernel limit $M\\gg N$ in this work. \n\nA1. There are three major differences that clearly separate our work for studying scaling laws from the prior works. First, as you mentioned, [1,2,3] focused on the kernel limit case where $M \\gg N$, while our work treats both $M$ and $N$ as free variables — this is a key feature to allow studying scaling laws, which are functions of both $M$ and $N$. Second, we establish matching upper and lower bounds for SGD while [1,2,3] only focused on the upper bound. Without a matching lower bound, it is unclear whether the derived scaling law is the true behavior, or just a mathematical artifact of a loose upper bound. Finally, our work also establishes scaling laws under logarithmic power law spectrums (see Section 4.2), which is beyond the scope of capacity condition.\n\n---\n\n> Q2. Borrowing the notation from [3] for concreteness, after a quick comparison with the identification of the capacity $\\alpha=a$ and source $r=\\frac{b-1}{2a}$, I believe the \"hard\" and \"easy\" rates from Theorems 4.1 and 4.2 can be retrieved from the one-pass rates in [3].\n\nA2. Our results cannot be recovered from [3]. As we discussed above, our Theorems 4.1 and 4.2 prove instance-wise matching upper and lower bounds as functions of both $M$ and $N$, while Theorem 1 in [3] only covers upper bounds as function of $N$.  \n\n---\n\n> Q3. [4] extends the discussion of [1-3] to the random features approximation of kernels.\n\nA3. We hope our A1 and A2 have clarified the relationship between our work and [1,2,3], hence also clarifies this question. \n\n---\n\n> Q4. The rates from one-pass SGD on least squares can be identified with the rates of ridge regression with an appropriately chosen regularization, which has been exactly characterized in [7]. For example, the blue and orange regions in Figure 1 from [7] correspond to rates in Theorem 4.2 with $\\ell=1$. A recent extension of the above to RFs case appeared in [6] (though note some of these rates were known from [7]).\n\n\nA4. We hope our A1 and A2 have clarified the relationship between our work and [1,2,3], hence also clarifies this question. Moreover, we would like to point out SGD is a more practical algorithm than ridge regression. \n\n---\n\n> Q5. The organization of the manuscript in Theorems with \"settings of increasing generality\" can come through as deceptive. Aren't Theorems 4.3, 4.2 and 4.1 corollaries of Theorems 6.3 and 6.4?\n\nA5.  Theorems 4.3, 4.2 and 4.1 are derived based on Theorems 6.3 and 6.4, however,  we believe the derivations are non-trivial and Theorems 6.3 and 6.4 can be viewed as the building blocks of the proof of our main results. Therefore, we put Theorem 6.3 and 6.4 after Theorems 4.3, 4.2 and 4.1.  \n\n--- \n\n> Q6. L43-48… Given our current understanding of random features regression, this claim is inflated. Several of the works mentioned above [4,6,7], as well as many other works in the random features literature have made the observation that increasing the \"width\"  does not necessarily lead to an increase of variance / overfitting, thanks to the implicit regularization. \n\nA6. This is a nice comment. We will rewrite this part to emphasize the differences between our results and prior results as discussed before. \n\n---\n\n> Q7. L273-275… What do you exactly mean in this sentence? What in Figure 2 is stronger than the exponents reported in Theorem 4.1?\n\nA7. While our theorems provide upper and lower bounds of matching rates, the exact constant factors do not match. Our experiments suggest that the constant should also match, as indicated by the linear trend and small standard deviation in e.g. Figure 2,  which is stronger than our theoretical prediction. \n\n---\n\n> Q8. The assumptions under which the Theorems hold are clearly stated, but I miss an explicit discussion of the limitations.\n\nA8. Thanks for the suggestion. Most of our assumptions are standard in literature, however, we will discuss the limitations of our assumptions (e.g., gaussian design, source condition) in the revision.", "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": "klrv5oL7BZ", "reviewer": "Reviewer_iyfq", "summary": "This paper sheds new light on the bounds of linear regression by framing them in terms of scaling laws.", "questions": "No question", "limitations": "No", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 1, "strengths": "- The set-up is very clear, the story is well-narrated and the model, including some sketch matrix to play the role of the model-size, is well-thought.\n\n- The authors try to be exhaustive with the assumptions: by including in a second time, (i) the assumptions that make everything work (Assumptions A and B) and that allow to go beyond Gaussian data ; (ii) source condition, (iii) some other spectrum decay.", "weaknesses": "It is difficult to talk about a weakness: the paper is self-contained, the results are solid and the context very well explained. \n\nPerhaps the authors should put emphasis on the fact that there is **absolutely no technical novelty and that the contribution relies in re-framing known bounds under the perspective of scaling laws**.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the feedback. Below is our response to your question.\n\n> Q1. Perhaps the authors should put emphasis on the fact that there is absolutely no technical novelty and that the contribution relies in re-framing known bounds under the perspective of scaling laws.\n\nA1. We respectfully disagree with the claim that our results are re-framing of known bounds. As discussed in lines 129-133, compared to the existing SGD analysis, we consider an additional data sketch, which leads to a new approximation error. Moreover, a direct application of existing SGD analysis only leads to sketch-dependent bias and variance errors, whereas we establish matching upper and lower bounds on these errors that also control the effects of data sketch. To achieve these, we develop several new concentration results (such as Lemma 6.2) and make novel uses of Von-Neuman’s inequality (see for example the proof of Lemma C.2). Therefore, we believe we have made novel technical contributions.", "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": "9gvaBv36O2", "reviewer": "Reviewer_9pNW", "summary": "This work examines neural scaling laws, in the simplified setting of linear regression trained by one-pass SGD. In particular, it attempts to explain the apparent mismatch between the statistical theory on one hand, which predicts that variance error increases with model size, and neural scaling laws on the other, which state that predictive performance should increase with model size. By considering sketched covariates of an infinite dimensional linear regression model with Gaussian prior under mild spectral assumptions, scaling laws are derived while keeping track of a variance term that increases with model complexity and corrects for a mismatch between the best-in-class predictor and the best possible predictor. However, this term is of higher order than the usual approximation and bias terms appearing in scaling laws, accounting for the empirical accuracy of scaling laws in practice. Numerical examples are provided for synthetic data.", "questions": "Can you please address the weaknesses outlined above?\nHow do you think this work can this be generalized to other settings of interest?\nUnder which settings should the variance term be accounted for?", "limitations": "Some discussion of the assumptions of their work and their limitations would be helpful. Broader societal impact is mostly not applicable.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a good paper that addresses an important theoretical inconsistency, and provides progress towards more general results.\nThe paper is generally well written and communicated.", "weaknesses": "It is not clear when the variance term is first given on page 2 that it is of higher order than the other terms. The reader has to find the more precise presentation in Theorem 4.1 in order to verify this for themselves. Clarification of this when the term is first introduced would be helpful and improve the paper.\nWhile the paper's contribution is primarily theoretical, the only examples given are synthetic. Validation of the theory on a large benchmark dataset, even if modified to make it appropriate to the assumptions, would strengthen the paper significantly.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful feedback and comments. \n\n> Q1. It is not clear when the variance term is first given on page 2 that it is of higher order than the other terms. The reader has to find the more precise presentation in Theorem 4.1 in order to verify this for themselves. Clarification of this when the term is first introduced would be helpful and improve the paper. \n\nA1. We note that the display on page 2 already suggests variance error is of higher order. Notice that $\\gamma = O(1)$, so we have\n\n\n$$ \\mathrm{min} \\\\{ M, (N \\gamma)^{1/a} \\\\} / N\n\\le\\mathrm{min} \\\\{ M, (N \\gamma)^{1/a} \\\\} / (N\\gamma) \n\\le \\\\begin{cases}\n\\frac{M}{N \\gamma} \\le M^{1-a} & M <  (N \\gamma)^{1/a}, \\\\\\\\\n(N \\gamma)^{1/a-1}  & M \\ge  (N \\gamma)^{1/a}.\n\\\\end{cases}\n$$\n\n\nThis implies that the variance error is of higher order compared to the sum of the other terms. We will make this more clear in the revision. \n\n---\n\n> Q2. While the paper's contribution is primarily theoretical, the only examples given are synthetic. Validation of the theory on a large benchmark dataset, even if modified to make it appropriate to the assumptions, would strengthen the paper significantly.\n\nA2. The power-law relations predicted by our theory are aligned with empirical findings in many other works [e.g., Hoffmann et al., 2022]. However, the hyper-parameter $a,b$ in our work are oracle properties of the data distribution, and it is a challenging problem to estimate them in practice.  Nevertheless, we believe this is an interesting problem to  study.\n\n---\n\n> Q3. How do you think this work can this be generalized to other settings of interest? Under which settings should the variance term be accounted for?\n\nA3. We believe the intuition carried from our theory, where the scaling laws are due to the disappearance of the variance error due to the implicit regularization, can be generalized to other settings. For instance, the practical LLM training often makes only one pass of the data, so less noise is fitted which implicitly regularizes the variance error. We believe this is an important reason for the observed scaling law.\n\n---\n\n**References**\n\n- Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv:2203.15556, 2022.", "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": "xVDf5wsVck", "reviewer": "Reviewer_8LLD", "summary": "Large models often empirically satisfy the neural scaling law i.e. the error decreases when the number of data and the model size increase, however, this contradicts with the widely accepted belief in learning theory that the variance error (one of the decomposed errors) should increase with the model size. Authors investigate this in the infinite-dimensional linear regression setting and show that the variance error is dominated by other errors because of the implicit regularization of SGD. Authors also support their claim with numerical simulations.", "questions": "- I am confused about the sketch matrix setting? Is the fixed sketch matrix analogous to the neural net with size M and why the teacher-student model in previous work can be viewed as sketched linear regression model\n- I am also confused about the Hypercontractivity assumption in Assumption 5, what's its intuition and why it is required in the proof?\n- What's the purpose for setting geometric decaying stepsize, what happens if it is fixed or it is polynomial decaying?\n- Is the regularization effect of SGD determined by the choice of stepsize, where the optimal choice controls the strength of the implicit bias of SGD?", "limitations": "See weakness", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The authors reconcile empirically observed scaling law and the classical statistical learning theory, and offers a novel viewpoint to understand and explain their original \"conflictions\", which is novel and should be interesting for both learning theory and LLM community. \n- The authors offer a general framework in section 6 to incorporate the general spectrum case of data covariance matrix, and it gives a novel technical innovations to sharply control the effect of data sketch.\n- The paper is very well written and it is easy to understand", "weaknesses": "- The assumptions of the paper might be too strong with linear regression setting and Gaussian design assumption, is it possible to extend to the kernel setting and with relaxed assumption on features [1]?\n- While the current analysis is focusing on one-pass SGD, which is not often used in LLM training, can the result be extended to Adam?\n- The result is not very surprising \n\n[1] Barzilai et al.,  Generalization in Kernel Regression Under Realistic Assumptions", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for supporting our paper! We address your comments as follows. \n\n> Q1. The assumptions of the paper might be too strong with linear regression setting and Gaussian design assumption, is it possible to extend to the kernel setting and with relaxed assumption on features [1]?\n\nA1. The Gaussian design assumption enables us to derive matching lower bounds for linear regression under data sketch. Note that our upper bound does not require Gaussian design. We will clarify this in the revision. Extending our results to kernel settings following relaxed assumptions in [1] is an interesting future direction. However, we think the obtained guarantee might be weaker. For instance, Theorem 2 in [1] only provides constant probability guarantees while our results, albeit using stronger assumptions, hold with high probability. \n\n---\n\n> Q2. While the current analysis is focusing on one-pass SGD, which is not often used in LLM training, can the result be extended to Adam?\n\nA2. Our SGD analysis cannot be directly extended to Adam because the structure of the randomness becomes convoluted in Adam. Nonetheless we think this is an important question and we will comment on this in the revision. \n\n---\n\n> Q3. The result is not very surprising.\n\nA3. We respectfully disagree. Typical risk bounds only involve upper bounds, but an upper bound is insufficient to characterize scaling laws, since an upper bound can be loose and the implied scaling law might be just an artifact. Our results, by establishing matching upper and lower excess risk bounds, rigorously characterizes scaling laws. Results of such kind are quite rare to the best of our knowledge. Thus we believe our results are significant. \n\n---\n\n> Q4. I am confused about the sketch matrix setting? Is the fixed sketch matrix analogous to the neural net with size M and why the teacher-student model in previous work can be viewed as sketched linear regression model\n\nA4. You are correct that our sketched data model is an analog to a two-layer network of size $M$ with fixed inner layer and linear activation. Although prior works formulated their problem as a teacher-student model, they (taking [Bordelon et al., 2024] as an example) assumed that the teacher model is an infinite dimensional linear model and the student model is another linear model using features projected by a random matrix $A$ (see their equations 1 and 3). Therefore their teacher-student model is effectively a sketched data model.  \n\n---\n\n> Q5. I am also confused about the Hypercontractivity assumption in Assumption 5, what's its intuition and why it is required in the proof?\n\nA5. The hypercontractivity condition requires the fourth moment tensor to be controlled by the second moment tensor. This is known to be weaker than subGaussainity while still allowing a sharp SGD analysis [Zou et al., 2023]. The intuition is that the expected risk of the SGD output involves at most the fourth moment information of the data, therefore some fourth moment condition is necessary to derive an expected risk bound. \n\n---\n\n> Q6. What's the purpose for setting geometric decaying stepsize, what happens if it is fixed or it is polynomial decaying?\n\nA6. The geometrically decaying stepsize scheduler is known for the last iterate of SGD to achieve a nearly (up to logarithmic factors) minimax optimal excess risk [Ge et al., 2019] in linear regression. Therefore we focus on the geometrically decaying stepsize scheduler. The last iterate of SGD would suffer from a constant variance error if used with a constant stepsize. Moreover, a polynomially decaying stepsize scheduler leads to a worse risk bound compared to a geometrically decaying stepsize scheduler as shown in [Wu et al., 2022a]. \n\n---\n\n> Q7. Is the regularization effect of SGD determined by the choice of stepsize, where the optimal choice controls the strength of the implicit bias of SGD?\n\nA7. You are correct that the regularization of SGD is determined by the choice of stepsize. The optimal stepsize can be solved from the instance-wise sharp risk bounds. However, this requires certain knowledge of the task parameter and the spectrum of the data covariance. Additionally, $1/(\\gamma n)$ in the SGD risk bound is comparable to $\\lambda$ in the known ridge regression risk bound. This is explained in depth in [Zou et al., 2021].\n\n**References**\n\n- Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. A dynamical model of neural scaling laws. arXiv preprint arXiv:2402.01092, 2024.\n\n- Rong Ge, Sham M Kakade, Rahul Kidambi, and Praneeth Netrapalli. The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares. Advances in neural information processing systems, 32, 2019.\n\n- Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham M. Kakade. Last iterate risk bounds of sgd with decaying stepsize for overparameterized linear regression. The 39th International Conference on Machine Learning, 2022a.\n\n- Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, Dean P Foster, and Sham Kakade. The benefits of implicit regularization from sgd in least squares problems. Advances in Neural Information Processing Systems, 34:5456–5468, 2021.\n\n- 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.", "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:

Meta-review: **Summary** The paper contains an analysis of a random features model trained with SGD.  It assumes an underlying infinite-dimensional linear regression problem.  The decay of the variances of the infinite dimensional problem and the target are both powerlaw type, denoted by parameters $(a,b)$ respectively.  

The data is is projected into finite dimensions by means of a finite-dimensional (isotropic Gaussian) sketching matrix having $M$ dimensions, and then this sketched data and a noisy target (with noise level $\sigma^2$) is released to the optimizer.

Sharp upper and lower bounds for the risk (less its irreducible part) are given over a range of parameters $(a,b,\sigma^2)$, as the number of samples $N$ (hence number of steps of one-pass SGD) tend to $\infty$.  

The new theoretical results leverage existing general risk bounds for one-pass SGD.  Novel bounds for the sketched problem are deduced which are needed to get the sharp dependence on the number of random features $M$. 

**Limitations.**
The risk bounds are not sharp for all parameters in the phase space.  
* $\sigma^2 = 0$ is not covered, nor are the estimates uniform as we take $\sigma^2 \to 0$.  (To the authors: please make it clear in Theorems 4.2,4.3 if this is the case; this was inferred from how you write Theorem 4 and from the $\Theta$ bound on the variance, which otherwise would seem too large.)  

    Hence we are constrained to an asymptotic regime in which we have a fixed irreducible loss level, say $42$.  We are then trying to get to $42 + 10^{-x}$ risk, and we get an accurate picture of how to achieve this risk as $x\to\infty$.  
    
    It seems to me that $\sigma^2$ should be small as a function of $M$, to be relevant to the scaling laws of Hoffman et al or Kaplan et al.  (Note that both these papers increase $M$ by $1000$ without seeing something like $\sigma^2$)

* In the range $b \geq a+1$, the estimates are not sharp.  So, the theoretical results are not quite all in place for the regime they consider.  


**Novelty** The reviewers have raised the concern of novelty of these results.  The opinion of the AC is that the risk bounds are new in the regimes they consider (in contrast to the concerns raised by the reviewers);  the key differentiator between the results of (13551) and existing work is that one must make estimates for the spectrum of the sketched covariance (c.f. Lemma 6.2).  Having done so, one has a finite-dimensional approximation of a kernel problem, which requires effective SGD risk bounds.

Now on the other hand, it is also true that the role of $M$ is very slight in this whole picture.  And one can take $M\to\infty$ first in this picture, the bounds are consistent with existing kernel regression bounds at $M=\infty$.  Hence it is also true that the random sketch is not doing very much, which may be the source of this confusion.  (Indeed Lemma 6.2 in some sense is the statement the random sketch is just a truncation of the infinite kernel problem, in a relatively strong sense).  

So the novelty in this paper is indeed the sharp analysis of a particular random least squares problem, especially eigenvalue/eigenvector estimates.

**Requests for modifications.**

* The reviewers have pointed out literature on source/capacity conditions, especially the list of v1rx.  You have written in the openreview comments how some of your bounds compare to existing ones.  These comparisons to the existing kernel regression literature will greatly contextualize these results, and would improve the manuscript.

**Recommendation**
This paper addresses a recent topic of interest (scaling laws, esp. compute constrained scaling laws) by sharpening and extending existing bounds, in particular giving bounds for powerlaw random features problems which are not in the existing literature.  It should be accepted as a poster.
Decision: Accept (poster)