Improved Scaling Laws in Linear Regression via Data Reuse
Authors: Licong Lin
Jingfeng Wu
Peter Bartlett
Venue: NeurIPS 2025 poster ()
Keywords: Scaling laws
linear regression
multi-pass SGD
data reuse
Primary area: theory

Abstract: Neural scaling laws suggest that the test error of large language models trained online decreases polynomially as the model size and data size increase. However, such scaling can be unsustainable when running out of new data. In this work, we show that data reuse can improve existing scaling laws in linear regression. Specifically, we derive sharp test error bounds on $M$-dimensional linear models trained by multi-pass *stochastic gradient descent* (multi-pass SGD) on $N$ data with sketched features. Assuming that the data covariance has a power-law spectrum of degree $a$, and that the true parameter follows a prior with an aligned power-law spectrum of degree $b-a$ (with $a > b > 1$), we show that multi-pass SGD achieves a test error of $\Theta(M^{1-b} + L^{(1-b)/a})$, where $L \lesssim N^{a/b}$ is the number of iterations. In the same setting, one-pass SGD only attains a test error of $\Theta(M^{1-b} + N^{(1-b)/a})$ (see, e.g., Lin et al., 2024). This suggests an improved scaling law via data reuse (i.e., choosing $L>N$) in data-constrained regimes. Numerical simulations are also provided to verify our theoretical findings.

Improved Scaling Laws in Linear Regression via Data Reuse
Licong Lin UC Berkeley iicouggin@berkeley.yy edu
Jingfeng Wu UC Berkeley uuujf@berkeley. edu
Peter L. Bartlett
UC Berkeley and Google DeepMind peter@berkeley.com edu
Abstract
Neural scaling laws suggest that the test error of large language models trained online decreases polynomially the model size and data size increase. However, such scaling can be unsustainable when running out of new data. In this work, show that data Specifically, we derive sharp test error bounds on M -ddimensional linear models trained by multi-pass stochastic gradient descent (multi-pass SGD) N data with sketched features. Assuming that the data covariance has power-law spectrum of degree a, and that the true parameter follows prior with an aligned pawer-law spectrum of degree 6 - a (with > b > 1), we show that multi-pass SGD achieves a test error of ( + [11-b)/a b)/-), where L & Na/b is the number of iterations. In the same setting, one-pass SGD only attains a test error of O ((M2-b, + (21bb)/a) (see, e.g.. [in al. 2024). This suggests improved scaling law via data reuse (i.e., choosing T, N) data-constrained regimes. Numerical simulations are also provided verify our theoretical findings.
improve existing scaling laws in linear regression.
Introduction
Empirical studies reveal that the performance of large-scale models often improves in predictable manner as both model size (denoted by M) and sample size (denoted by N) increase (see, e.g., Hoffmann et al.) 2022 Besiroglu et al. 2024). These observations, known as neural scaling laws, suggest that the population risk (denoted by R) of large models decreases following a power-law formula, namely,
R(M,N) R* + G + C2 N
where R* denotes the irreducible error such the intrinsic entropy of natural language in the case of language modeling (Kaplan et al. 2020) and 01, 42, C1, 02 are positive constants. Neural scaling laws predict path for improving the state-of-the -fet------e--tttt models via scaling model and data size.
line of recent work establishes provable scaling laws simplified settings such as linear regression (see, e.g., Lin et al. 2024 Paquette et al.) 2024] other related works will be discussed later in Section Specifically, they consider an nnfnite-dimensionall linear regression problem, where an M didimnssionnl linear model is trained by one-pas, stochustic gradient descent (SGD) on N Gaussian-sketched samples. Under plwer-law assumptions on the spectra the data covariance and the prior covariance, they show power-law type scaling laws in linear regression. However, their results are limited one-pass SGD, where each sample is used once. In particular, Lin et al. (2024) attributed the nice, power-law type scaling laws to the implicit regularization effect of one-pass SGD
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(see Section I therein). It is unclear if scaling laws apply to other training algorithms, particularly those involving multiple passes of the data. Indeed, the scaling laws that only apply one-pass methods are not sustainable in a data-constrained regime.
There is evidence that data reuse improve existing scaling laws developed for one-pass training. Empirically, Muennighoff Muggniiih et al. (2023) showed that with up to four passes, scaling laws approximately hold if the reused data is new. From a theoretical perspective, the work by Pillaud- Vivien al. (0118) shows that in a class of linear regression problems, the sample complexity of one-pass SGD is strictly suboptimal; and it can be made minimax optimal by considering multiple passes. However, Pillaud- Vivien et al. (2018) did not discuss the effect of model size or sketching. These results motivate the study of scaling laws for multi-pass methods.
Contributions. In this work, we study scaling laws induced by multi-pass SGD in the same infinite- dimensional linear regression setting considered by Lin et al. (2024): Paquette et al. (2024). Our results suggest that in certain regimes, the test error of models trained by multi-par pass SGD scales strictly better with respect to the number of training samples compared to one-pass SGD.
We assume that the data covariance and the prior covariance exhibit aligned power-law spectra with exponents and b- a, respectively (see Assumption [C and ID) (Lin al. 2024 Paquette et al. 2024). We prove that multi-pass SGD achieves excess test error of order O(M
b17) when
b > 1 and the number of SGD iterations L S Na/hb, This improves over the ((M -
bound for one one-pass pass SGD (Lin et al. 2024) when > N. In particular, when choosing the optimal number of iterations L Na/b multimpaaaa pass SGD achieves an excess test error of order (( b)/)), in contrast to (1- b3/a) for one-pass SGD the data-constrained regime where N < M Our results thus suggest that, to a certain extent, reusing data can improve the test performance of linear models in data-constrained regimes.
Notation. Let f(x) and g(x) be two positive- positive-valued functions. We write f(x) g(x) (and f(z) = (g(())) if there exists some absolute constant (if not otherwise specified) c > 0 such that f(x) & eg(z) x) for all x. Similarly, fzx z g (and f(x) ((g(z))) means f(x) T> cg(x) for some constant c > O. We write fx) ~ g(x) (and f(x) = (g(())) when f(x) & g(x) S f(x). We also occasionally use Õ(-), (()) to hide logarithmic factors. In this work, log(-) denotes the base-2 logarithm. For two vectors u, v in a Hilbert space, we denote their inner product by (u, v) or u vv. We denote the operator norm for matrices by -- (or ||- Il22) and the f--norm for vectors by 1|22- For a positive semi-definite (PSD) matrix A and a vector v of compatible dimensions, we write | == V Av. For symmetric matrices, we denote the j-th eigenvalue of A by μz(A)) and the rank of A by r(A).
2 Setup
Let E H. denote a feature vector in a Hilbert space H (finite or countably -ifenteediimessional) with dimension d : dH), and y R denote its corresponding response. In linear regression, the test error (i.e., population risk) of the parameter w E HHI is measured by the mean squared error:
R(w)= (xx))> (xx, w) w) y)
for some distribution P on H x R. Given samples of the form (x, v). instead of fitting a d-dimensional linear model, we train an M-dimensional sketched linear model with M & d. Namely, we consider linear predictors with M parameters, defined as
fv H - R.
(v. Sx).
(1)
where RM are the trainable parameters, and Se Mx is some fixed sketching matrix. In this work, we consider Gaussian sketching, where the entries of are drawn independently from N(0, 1/M). Given set of N i..d. samples (x,, 2 from P. we train fy via multi-pas pasts stochastic gradient descent (multi mauls SGD), that is,
V2 == Vt-1 - 7+ (f (xx,) - vi.) V Vt- Sx, (0,,,,(,))) (x] (T. -)t))
(multi-pass SGD)
t t= 1,....

---

where is the number of total steps, i, sid uni]([ for [L], and (7)) are the stepsizes.
Without loss of generality, we assume zero initialization vo O. We consider geometric decaying stepsize scheduler (Ge et al. 2019 Wu al. 2022b Lin al. 2024).
7=
22/2" 70/2 for = I.....,,, where é= [t/(L/ log(L))
(2)
and to > 0 is the initial stepsize. The output of multi-pass SGD taken its last iterate VL. We emphasize that the algorithm we consider differs slightly from the standard SGD used in practice, where the samples without replacement. In contrast, we assume that at each step, sample is drawn independently from the training dataset, allowing for repeated sampling within an epoch. Moreover, our analysis applies to other stepsize schedules (such as polynomial decay), but we focus on geometric decay since it is known to yield near minimax optimal excess test error for the last iterate of SGD in the finiteddimensional regime (Ge et al.) 2019).
shuffled the beginning of each epoch (pass) and then processed sequentially
Conditioned sketching matrix S, the risk of V is computed
RM (Vr.) R(S' vr.) E (xx
vi.) (v)) -
where the expectation is over (x, 3) from P. As an important component of our analysis, we also consider the gradient descent (GD) iterates
N
0, = 0,
Σ
(fe. (xi) vi) V. (x.e...
N
(GD)
Tt SX (XS 1 -y)
01-1
L,
where X (Xi....,, (XI) . (yI...., yN)", Oo 0, and (7t) are the same stepsizes in N Conditioned on the sketching matrix S and the dataset (x, yt) y.), it can be verified by induction that VL is unbiased estimate of 0r, i... E[vz] Oz. where the expectation is the randomness of the indices (ie)/-1
Risk decomposition. We can decompose the risk (i.e., the test error) achieved by vz, the last iterate of (multi-pass SGD), into the sum of irreducible risk, approximation error, the excess risk of the last iterate of (GD), and fluctuation error:
RM (VL) min R(.) + min (.) - min R(-) + (0,) min RM(()) + RM(vV) - RM (0))
Irreducible
Approk
Excess
Fluc
Compared with Lin et al. (2024) (cf. Eq. 4), the decomposition in (3) includes an additional fluctuation error term arising from the randomness of the indices (fe) , in multi-pas SGD (Zou et al. 2022).
Note that the fluctuation error is non-negative by Jensen's 's inequality, as V,, is an unbiased estimate of Or.
3 Main results
In this section, we present our main result, showing that under certain power-law assumptions on the data covariance and the prior covariance, the expected risk of v from (multi-pass SGD) decays polynomially the number of training steps L and model size M. We begin by introducing the data assumption used throughout this work.
Assumption 1. Assume the following conditions on the data distribution P.
A. Gaussian design. The feature vector satisfies x ~ -N H).
B. Well-specified model. The response satisfies Efy x, w1 x w Define o² = E[(y x w+]]]
C. Power-law spectrum.
The eigenvalues of H satisfy X, i for all > 0 for some a 1.
D. Source condition. prior such that
Let (D4, vilszo be the eigenvalues and eigenvectors of H. Assume w* follows
for # j, EV w* (v3, w w* 0; and f i > 0, B[AKV, w > m zit rh for some b 1.
3

---

Assumptions IA and BB posit that the feature vector x follows Gaussian distribution and that well-specified, which are standard conditions in the analysis
the linear model y xx, w of linear regression. Assumptions IC and TD assume that both the covariance of and the prior on the true parameter w* have power-law spectra share the same eigenspace. In particular, the true parameter w follows an isotropic prior when a b. These conditions are common in theoretical analysis of scaling laws (Bordelon et al., 2024a| Lin et al., 2024 Paquette et al. (024)), and the power-law spectrum in Assumption [Ciis also empirically observed in real-world data, such as the frequency distribution words natural languages (Piantadosi 2014). We further note that Assumption matches the conditions of Theorem 4.2 in Lin al. (2024), which established scaling laws for one one-pass SGD under the same setup. This alignment allows a direct comparison between our results and those in Lin al. (2024), highlighting the benefits of data reuse in certain data-constrained regimes. Finally, we define the number of effective steps Tattt := |L/ log L.J.
Theorem 3.1 (Error bounds for multi-pass SGD). Suppose Assumption holds. Consider an M- dimensional linear predictor trained by (multi- palliippasssss SGD) on N samples. Recall the decomposition
in B. Assume the initial stepsize " min 1/[4 [Sx,l21] for some y S 1/ log N and the number of effective steps Lett & N Then with probability least -S(M)) over S
Irreducible R(w+*) = a2
2. w [Approx] = M
3. Suppose o² z 1. The expected excess risk (Excess) admits decomposition into a bias term (Bias) and a variance term (Var), namely,
E Excess ~ Bias + VaV,,,
where the expectation is over the randomness of w*, (x,, and (ie) Moreover, when > b 1, Bias and Var satisfy
Bias & max/M b
(Leert) (1-b)/n,
Bias ž (Iatt7) bbjaa (1-b)a when (Trate)) 1/a M/c for some constant 0,
Var ~ min (M, (Lezrt) 3/N/NN
Suppose a² and Latt & N(1-E)a by for some (0, 1]. The expected fluctuation error R[Fluc] satisfies
B[Fluc] y log N. [(battt) (boteT)
N and
B[Fluc] 2 (Latee)) Va-1 when Latt & N/y and (Latrr) M/c for some constant e >> 0,
where the expectation over w* (xi, yo and (i
In the results, the hidden constants depend only on (a, b) for part 1-3, and on (a, b, for part 4.
See the proof of Theorem 3.1 Appendix A.2.1 A few comments Theorem 3.1 are in order.
The results Theorem 3.1 are more general than those in Theorem 4.1 and 4.2 of Lin et al. (0224) Specifically, we derive matching upper and lower bounds for each term in the decomposition (3) for multi-pass SGD with an arbitrary number of steps L S Na, except for the lower bound the fluctuation error, which requires L s N. In contrast, [in et al. (2024) only considered one-pass SGD where L N. When a 2 b and L N, our bounds match those for one- pass SGD given in Theorems 4.1 and 4.2 of Lin al. (024) up to logarithmic factors (see Section 3.2 for more details).
Comparison with Lin et al. 2024)..
see that the fluctuation error term [llc vanishes as the stepsize y goes to zero. This is intuitive: when 7 is small, the noise from random sampling becomes negligible and multi-pass SGD closely approximates gradient descent. Moreover, when 2 b and Late Na/6 it can be verified that for any 7 $ 1/ log N, the fluctuation error dominated by the sum of the approximation error and excess risk (GD), i.e., EF[Fuc]] s Ewe [Approx] + [Exxeess].
The fluctuation error. From part 4 of Theorem 3.1

---

Choice of the stepsize. The assumption 1/log N ensures that the initial stepsize To = with high probability. However, guarantee the convergence GD iterates, it suffices to have
To & L/IXX / 1/ max; [x, are technical conditions needed for analyzing the fluctuation error term. We leave the problem of relaxing these assumptions to future work.
1 The additional log N factor and the assumption =
Constant-stepsize SGD with iterate averaging. Similar to Lin al. (022). the results in Theo- rem 3.1 also hold for the average of the iterates of multi-pass SGD with constant stepsize, with the only modification being that Lerr is replaced by in the bounds. We provide simulations supporting this claim in Section
Relaxation of Assumption I The Gaussian design in Assumption LA can be relaxed sub- Gaussian design when establishing the upper bounds for Bias, Var, Approx in Theorem 3.1 and the upper bounds subsequent corollaries. Moreover, the exact alignment of the eigenvectors of the prior and data covariance in Assumption ID can be relaxed. We refer to Appendix A.3 for more details.
Next, we discuss some implications of the error bounds in Theorem 3.1
3.1 Scaling laws for GD
To begin with, we present matching upper and lower bounds for the expected test error of the last iterate (D) (denoted by B[ (0,))). We note that the GD iterates have strictly smaller test error than the corresponding multi-pass SGD iterates when 7 > O, since the GD iterates (0:)- are the expectation of the multi-pass SGD iterates (vt) conditioned on the sketching matrix S and the dataset (x, 34 ) By combining part 1-3 of Theorem 3.1 have
Corollary 3.2 (Sealing laws for GD). Let Assumption 7 hold and a > b Consider an M-dimensional linear predictor trained
(GD) on N samples with stepsizes 70 min(y, tr trr(stttXXXX XS /Nj]} for some $ 1. Suppose o² a and Lost $ Nº/7. With probability at least - -Silid) over S, the expected risk of O,, satisfies
XS/NN)]
1 E[Rrr(0 = 0² Mb-T
+
(
e
mmin(M M, (LorrT)
(Larrr)
+
N
Approx+ Blas
Var
Here, ((-) hides constants that only depend on (a, b).
See the proof of Corollary 3.2 in Appendix A.2.2 From Corollary 3.2 we see that the variance error of GD is dominated by the sum of the approximation error and the bias error (i.e. Var & AApprox + Bias) when Teett? & No/b To achieve the optimal expected test error, we may choose y and the number of effective steps Lutt min(Na/6 Ma)// No, Under this choice, have
0 M
if & M.. if & M
E E Md (0.) 02
is worth mentioning that decreasing stepsize schedule as in is not necessary for our analysis. In fact, Corollary remains valid for the last iterate of constant-stepsiz GD (i.c., 7) when replacing Letr with the bounds. In addition, the GD iterate 0 achieves the same expected risk (up to logarithmic factors) as one one-pass SGD when I, = N, where the performance of one-pass SGD characterized Theorem 4.2 of Lin et al. (024)..
However, the computational cost of GD is substantially larger than that of one-pase mas- SGD, since each update requires computing gradients from all samples, resulting in a complexity of ((MN) compared to ((MN) for one-pass SGD. Nevertheless, the excess test error of GD serves always-valid lower bound for that of multi-pass SGD, and is also an upper bound (up to logarithmic factors) in certain regimes where the fluctuation error is dominated by the sum of the approximation error and the excess risk of GD.
'Ste (i) follows from e.g., Theorem 4 and in Koltchinski and Lounici 2017
5

---

3.2
Scaling laws for multi-pass SGD
We now analyze the expected test error of the last iterate of (multi-pass SGD). By Theorem 3. and Corollary 3.2 we have
Corollary 3.3 (Scaling laws for multi-pass SGD when a 2 b). Suppose the assumptions in Theo-
rem 3.1 are in force, o² ~ 1, and b 1. For any Latt $ &Na/b/a /7, we have
(M/-)
E [[RM(VE)] o² O M
(L
with probability at least 1 - -D(()) Here, all hidden constants depend only on (a, b).
In contrast, Theorem 4.2 in Lin et al. (2024) proved that one-pass SGD with vš 0, v?
vi-1 (x, S VTV. 31) for [N] satisfies
1
B[Ras(v3/) 0²
M + θ (Norr7)(6-1)1a
with probability at least - --M)) where Nost N/ log. N.
Several remarks on Corollary 3.3 are listed below.
Benefits of data reuse. When a 3 > 1, Corollary 3.3 shows that multi-pass SGD achieves an excess test error of order @(M (Leer)) when the number of effective SGD steps Lest S Na/h, while one-pass SGD achieves an excess test error of order ((M (Nerr?)) (1-b)/)) Therefore, the reused data across multiple passes (epochs) can be viewed as fresh data when the number of passes is smaller than Na/bb11 For example, when L kN for some constant & >> 1, the test error achieved by k-pass SGD matches that of one-pass SGD trained on &NV i.i.d. samples despite the training data being reused aligning with the empirical observations in Muennighofi et al. (2023).
Moreover, when the number of effective steps is choser as Latt aa/b M²)/y and the learning rate y 1/ log N, the excess test error of multi-pass SGD satisfies
[[R)((v))] o² = M2- ((L-))
while choosing < 1 for one-pass SGD yields
a[Ras (v&) 0² 1 Nett (1-b)/a
Therefore, in the data- cotstrrnntt regime where N < M reusing data and running multi-past -aass SGD for N epochs yields an improved rate of ((N(1-)) compared to the one-pass SGD rate of ((N(L-))/a) when a b.
Optimal compute allocation. Given a total compute budget C' L M, by Corollary 3.3 we can set L (CC/((+1) and M ((Cl/(+11) with stepsize y ~ 1/ log to achieve the optimal rate (() for the excess test error [[RAr(VL.] - o2. This matches the optimal rate for one-pass SGD (Lin et al. 2024) given the same compute budget, but requires only N (CC/(a++)) number of i.i.d. samples in contrast to N = ((C/(a+1)) for one-pass SGD.
Minimax optimal rate. When a > b> 2 and M >> 11/b, the improved rate 01-/// achieved by multi-pass SGD matches the minimax optimal rate for class of linear regression problems with similar spectral conditions (Pillaud- Vivien et al. 2018), to sub- nol-polyaoiil factors.
When
+ 1, similarly, we have the following corollary from Theorem 3.1 Corollary 3.4 (Scaling laws for multi-pass SGD when a
+ 1). Suppose the assumptions in Theorem 3.1 are in force and o² 1. When b + 1, for any Lest S NN/y, we have
min| M, (Iatt)) + E[Fluc]
[[Ras( = o²
min M, (LeerY) 1apo-1
N
NNote that this choice of Lutr (and therefore L) is optimal as it minimizes B|RM (Vz.)] -o to logarithmic factors for Lett Na

---

with probability at least 1 - e- e-(MM, where the fluctuation error satisfies E[Fluc] & y llog N. (Iete?) Va-1, and E[Fucc] 2 7 (Last?) 1/a-1 when (Lest7) 1/0 x M.
Therefore, in the data-constrained regime where N < M we have B[RMs(v))] - o² = (((orrr)) (1-b)a + >(Lorr>\Va-)) Choosing Lerr ~ N and the optimal learning rate 7 2 Lett" Lost a/b-1 that balances the excess test error of GD and the fluctuation error, we obtain a rate of ((N())))))) This matches the bound for one-pass SGD in Lin et al. (2024) (up to logarithmic factors) when a < <bca b<a+l.
4 Experiments
We also perform simulations to validate our theoretical findings. Namely, we train M-dimennional sketched linear predictors (I) via one-pass SGD and multi-pass SGD following the setup in Sec- tion 2 and 3 and analyze how their excess test errors scale with the number of samples N and the model size M. In each simulation, we generate N i.idd samples (x,, yt), from a linear model
yi (x;, w EG. where w* E _d is an unknown parameter vector and e; (N0 o²) are i.i.d. Gaussian noise. The covariates x; are drawn from N (0, H), and the true parameter vector w* is sampled from Gaussian prior (0, H where H == diag ...., ......,d)), d) Σx_ i and d........),)) d= for some a, b > 1. We set the dimension d to be sufficiently large relative to .M so that Assumption IC and ID are approximately satisfied. For simplicity, we imple- ment multi-pass SGD by reusing samples sequentially without replacement in each epoch, rather than sampling i.i.d. from the empirical distribution. In all experiments, we set = 10000, o² = 1 and (a. b)
H == diag(1, 1, 2n-b ................................
(2, 1.5).
Figure ma) compares the excess test error of one-pass SGD and multi-pass SGD with the number of steps = Na/bb11 We observe that multi-pass SGD achieves better scaling in the sample size N compared to one-pass SGD when N is relatively small (i.e., N < M³). Moreover, the fitted exponents are close to the theoretical predictions in Corollary 3.3 (i.e., 1-b = -0.25 and - = -0.33). Similar results hold for the average of the iterates of constant-stepsize SGD, as shown in Figure (t). On the other hand, when N M Figure [[c) shows that one-pass SGD and multi-pass SGD achieve the same scaling in the model size M with the exponent k: z b, consistent with Corollary 3.3] In addition, Figure (d)) illustrates that multi-pass SGD achieves the same excess test error as one-pass SGD on fresh data when the number of passes is below a certain threshold. Overall, the empirical observations align closely with our theoretical predictions.
2cm 332
mullicss 2m
mudi-non -a0 ane pess 224
one propess 2
and pess 2.5
- one pels 0m-3.51
tus
Excess
Namber effective samples
1P
Number
10"
Model
23t Number
(a) 0.1
(b) 0.1
(0) 0.5
(d) 0.5, 1000
Figure 1: Multi multi-passore SGD versus one- mass SGD. In (a) (c), multi-pass SGD is ran for L ~ No/6 steps. (a), (b), (d): SGD with geometrically decaying stepsizes; (c): SGD with constant stepsizes. We use linear functions to fit the excess test error in log-log scale. The fitted exponents (k) are close to the theoretical predictions in Corollary 3.3. The errorbars denote the +1 standard deviation of the expected excess test error over 100 i.i.d. samples of (S, w+). Parameters: o² = 1, d = 10000,
(a. b) = (2, 1.5). (a). (b), (d): M- = 1000; (c): N = 103.
7

---

Proof Overview
We provide an overview of the proof of Theorem 3.1 in this section. A full proof can be found in Appendix A.2.1 Let v* (SHS " and adopt the shorthand notations
Σ = SHS Σ = SX XST
N
can be verified by some basic algebra that
ERas(VL) TE. S vı) =)
+
w H
+E
02
v+1
+B
V1
O21
Irreducible
Approx
Excess
Fluc
where the expectations the R.H.S. are w (x,, v.) and (oe) and recall VL in (multi-pass pass SGD) and 0g in (D). ). From the above decomposition, we immediately have
1. Irreducible R(w") 0².
1-b with probability at least -0(M) over by Lemma C.5 in Lin et al. (2024) (see also Lemma E.7
w [Approx] E ST
~ M
The excess risk of GD can be further decomposed into the sum of bias and variance, namely.
[[Excess] Bias + Var,,,
where
Bias
E.
I [I
v*
x Var V(S
with := --- I (I- 11/ The bounds on the bias (Bias) and variance (Var) then respectively. Lastly, the bounds on the fluctuation
follow immediately from Lemma B.3 and C.2
eгror follow from Lemma D.5
The main technical difficulty of proving Theorem 3.1 lies in bounding the bias, variance, and fluctuation error terms. For bias and variance upper bounds, due to the non-commutativity of the population covariance Σ and the empirical covariance Σ, we apply covariance replacement trick (Lemma E.I] see also Lemma in Pillaud- et al. (2018)) replace the population covariance with the empirical covariance in the expressions of bias and variance, as well as concentration properties of sub-Gaussian covariance simplify their expressions. For the lower bounds, we show that a specific function of the empirical covariance commutes with the population covariance in expectation, and apply Von Neumann's 's trace inequality.
For the fluctuation error, we follow the standard practice as in Pillaud- Villaud-Vivien et al. (2018) and Aguech al. (2000) express the difference between the multi-pass SGD and GD trajectories, V. O, as 0z) through controlling the accumulated error of the stochastic process using Lemma D.2 and D.3 which involves novel leave-one-ors argument to control the model parameters. Although several upper bounds the fluctuation error have been established for infinite-dimensional linear models (Pillaud- Vivien et al. 2018 Zou et al. 2022), the interaction between the sketching matrix S and the samples (x,, y4 2 in our setup introduces additional technical challenges (Lin et al.) 2024). Moreover, we derive novel lower bound the fluctuation error that matches the upper bound up to logarithmic factor in certain regimes by carefully controlling the accumulated variance from random sampling (i.e. the accumulated variance induced by the random indices (it)/_)).
stochastic process (Eq. 18) We then bound the fluctuation error E Σ
Related Works
Empirical scaling laws. Scaling laws have been extensively studied in recent years as a way to understand and predict how model performance improves with increasing model size and data size (Hestness et al.) 2017 Rosenfeld et al.] 2019 Kaplan et al. 2020) Henighan et al. 2020 Hoffmann et al. 2022 Zhai et al. 2022 Muennighoff al. 2023). The seminal work by Kaplan al. (2020) introduced the concept of neural scaling laws, demonstrating empirically that the test

---

error of large transformer models decreases predictably following a power law with respect to the model size and data size. Subsequent works refined and extended these observations by proposing more accurate scaling formulas (Henighan et al. 2020 Hoffmann et al. 2022 Alabdulmohsin et al.
2022 Caballero et al. [022] Muennighoff et al. 2023) and extending them to other settings (Kumar
et al. 2024 Busbridg et al. 2025). In particular, Hoffmann et al. (022) proposed the Chinchilla scaling law, which advocates scaling the model and data size proportionally as compute budget increases. Muennighoff et al. (2023) investigated the effect of data reuse and multiple training epochs, introducing an empiricaly refined scaling formula that accounts for the number of training epochs. They demonstrated that reused data can be approximately viewed as fresh data when the number of epochs is small.
Theoretical studies of scaling laws. Although scaling laws have been observed across diverse
settings, their theoretical understanding remains relatively limited. A number of recent works have
attempted to formalize and explain the observed scaling behaviors in simplified settings (Sharma
and Kaplan| 2020 Bahri et al.] 202T, Maloney et al. 2022. Hutter, 202T]] Michaud et al., [2024]
Bordelon al. 2024a Atanasov et al.
2024] Paquette et al. [2024] Lin et al. 2024b] Ren et al.] (2025). For example, Bahri et al. (2021) considered a linear
2024 Dohmatob et al.
Bordelon et al.
teacher-student model with power- law spectrum and showed that the test error of the ordinary least squares estimator scales following a power law in N (or M) when the other parameter goes to infinity, Bordelon et al. (2024a) analyzed the test error of the solution found by gradient flow in linear random feature model and established power-law scaling in one of N, M and 7 (training time) while the other two parameters go to infinity. The results in these works are derived based on statistical physics heuristics and characterize scaling in only one variable in the asymptotic regime. More recently, Lin et al. (2024) analyzed the test error of the last iterate of one-pass SGD in sketched linear model and showed that the test error scales O(o² + M + N(1-b)/a) under the source condition (A [Assumption[]] [] This is the first work to establish a finite-sample joint scaling law (in M and N) for linear models that aligns with empirical observations (Kaplan et al., (200 [Hoffmann et al., 2022). Similarly, Ren et al. (2025) analyzed the complexity of one-pass SGD for learning two-layer neural networks in a teacher-student setup, and derived joint scaling laws for the test error under power-law assumptions on the teacher network. While previous works study the scaling behavior of the one-pass (online) SGD solutions, our work complements them by analyzing the effect of data reuse (i.e., multi-pas, ppass SGD) in fata-constrained regimes.
Risk bounds for SGD. The generalization behavior of stochastic gradient descent (SGD), partieu- larly in linear regression, has been extensively studied across both classical and high-dimensionall regimes (Polyak and Juditsky, 1992, Défossez and Bach 2015: Dieuleveut al., 2017 Jain et al.
2018
2017; Pillaud- Vivien et 2011 8 Ge et al. 2019 Dieuleveul and Bach, [2015] Berthier et al.
2021 2022] Wu et al. 2022b c Varre et al.) 2021). J. For one- SGD, several 2020 Zou al. 2023
tight test error bounds in overparameterized linear models (Zou et al. 2023 Wu et al. 2022a cp. For multi-pass SGD, early works (Lin and Rosasco [017;] Pillaud- Vivien et al.
works have deve
2018; Mücke et al. 2019; Zou et al.] (022) have established test error bounds for the average of its iterates in linear regression. Compared with prior works, our main technical contribution is to precisely control the effect of random sketching and to refine the characterization of fluctuation error (see Fluc in Eq. 3 in the multi-pass palti-pass setting. Under comparable regimes where the approximation error is zero, test error bounds match those derived in Pillaud- Vivien et al. (2018), which are minimax optimal for a specific class of linear regression problems in certain cases.
Conclusion
In this work, we provide theoretical analysis of multi-pass stochastic gradient descent (multi-pass SGD) in a sketched linear regression problem and establish refined scaling laws that characterize how the test error scales with the model size M, sample size N, and number of optimization steps L. Our results show that, under suitable power-law conditions on the true parameter and data distribution, data reuse via multi pass SGD improve model performance when the number of samples is limited. This offers a theoretical explanation for the empirical benefits of multiple passes in modern large-scale training.
Our analysis has several limitations. One limitation is the assumption that the eigenvectors of the prior and data covariance are aligned (implied by Assumption ID). While this assumption cannot be

---

fully removed without affecting the error rate. it would be interesting to investigate what alternative rates are achieved when the eigenvectors are not aligned. Another limitation is that our lower bound results require Gaussian design of the covariates (i.e., Assumption TA a next step is to extend them to non-Gaussian design.
Beyond the limitations, many other directions remain open for future research. First, our analysis focuses on multi-pass SGD with batch size one; would be worthwhile understand how the test error scales with the batch size and to develop corresponding batch size scaling laws (see Jain et al. 2017). Another important direction is study how data reuse interacts with other optimization algorithms, such as SGD with momentum or fg-regularization and Adam. In addition, it is valuable to extend our analysis non non-linear settings and classification problems, such as logistic regression. kernel methods, and neural networks. Notably, modern large language model pretraining is based on minimizing the cross-entropy loss for next-word prediction. Understanding the scaling behavior in logistic regression- the simplest classification model thus represents an important step toward unraveling the mysteries of LLM scaling.
Acknowledgements
We gratefully acknowledge the NSF's support of FODSI through grant DMS- 202-5502350 and of the NSF and the Simons Foundation for the Collaboration on the Theoretical Foundations of Deep Learning through awards DMS-2031883 and 181439 and the ONR through MURI award N000142112431.
Bibliography
Rafik Aguech, Eric Moulines, and Pierre Priouret On a perturbation approach for the analysis of stochastic tracking algorithms. SIAM Journal Control and Optimization, 39(3):872 1899299992288 2000.
Ibrahim M Alabdulmohsin, Behnam Neyshabur, and Xiaohua Zhai. Revisiting neural scaling laws in
language and vision. Advances in Neural Information Processing Systems, 35:22300-2233 2022.
Alexander B Atanasov, Jacob Zavatone- Veth,, and Cengiz Pehlevan. Scaling and renormalization in -igh-niiensional regression. arXiv preprint MXXi::405.005900 2024.
Yasaman Bahri, Ethan Dyer, Jared Kaplan, Jachoon Lee, and Utkarsh Sharma. Explaining neural scaling laws. arXiv preprint 1:Xiv:2102.0677: 2021.
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.
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.
Tamay Besiroglu, Ege Erdil, Matthew Barnett, and Josh You. Chinchilla scaling: A replication attempt. arXiv preprint 1mX1v:2404.10102, 2024.
Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. A dynamical model of neural scaling laws. arXiv preprint arXiv:2402.01009,, 2024a.
Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. How feature learning can improve neural scaling laws. arXiv preprint arXiv:2409. /7858, 2024b.
Dan Busbridge, Amitis Shidani, Floris Weers, Jason Ramapuram, Etai Littwin, and Russ Webb. Distillation scaling laws. arXiv preprint arXiv:2502.00866 2025.
Ethan Caballero, Kshitij Gupta, Irina Rish, and David Krueger. Broken neural scaling laws. arXiv preprint 1rXiv:2210.14280 2022.
Alexandre Défossez and Francis Bach. Averaged least-mean-qquares: Bias-variance trade-offs and optimal sampling distributions. In Artificial Intelligence and Statistics, pages 205-213, 2015.
10

---

Aymeric Dieuleveut and Francis R. Bach. Non-parametris stochastic approximation with large step sizes. The Annals of Statistics, 2015.
Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger con- vergence rates for least-squares regression. The Journal of Machine Learning Research, 18(1): 3520-3570, 2017.
Elvis Dohmatob, Yunzhen Feng, Pu Yang, Francois Charton, and Julia Kempe, A tale of tails: Model collapse as a change of scaling laws. arXiv preprint arXiv:2402.07043, 2024.
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.
Tom Henighan, Jared Kaplan, Mor Katz, Mark Chen, Christopher Hesse, Jacob Jackson, Heewoo Jun, Tom B Brown, Prafulla Dhariwal, Scott Gray, et al. Scaling laws for autoregressive generative modeling. arXiv preprint arXiv:2010.1477 14701, 2020.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Mostofa Ali Patwary, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically, arXiv preprint 1rXiv: 2017.
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.
Daniel Hsu, Sham Kakade, and Tong Zhang. tail inequality for quadratic forms of subgaussian random vectors. Electronic Communications in Probability, 17(none): 6, 2012. doi: 10.1214)
ECP.v17-2079. URL htt.:httts///dtt org/10..///. 10. 1214/ECP v17-2079
Marcus Hutter. Learning curve theory. arXiv preprint
2021.
Prateek Jain, Praneeth Netrapalli, Sham M Kakade, Rahul Kidambi, and Aaron Sidford. Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification. The Journal of Machine Learning Research, 18(1):8258 8299, 2017.
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Venkata Krishna Pillutla, and Aaron Sidford. A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares). 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017), 2018
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.
Vladimir Koltchinskii and Karim Lounici. Concentration inequalities and moment bounds for sample covariance operators. Bernoulli, pages 110-133, 2017.
Tanishq Kumar, Zachary Ankner, Benjamin F Spector, Blake Bordelon, Niklas Muennighoff, Man- sheej Paul, Cengiz Pehlevan, Christopher Ré, and Aditi Raghunathan. Scaling laws for precision. arXiv preprint htt.::2411.0433300 2024.
Junhong Lin and Lorenzo Rosasco. Optimal rates for multi-pass paulti-passsaee stochastic gradient methods. The Journal of Machine Learning Research, 18(1)33375-341, 2017.
Licong Lin, Jingfeng Wu, Sham M Kakade, Peter L Bartlett, and Jason D Lec. Scaling laws in linear regression: Compute, parameters, and data. arXiv preprint arXiv:2406. 084666 2024.
Alexander Maloney, Daniel A Roberts, and James Sully. A solvable model of neural scaling laws. arXiv preprint 20.. 2022.
Eric Michaud, Ziming Liu, Uzay Girit, and Max Tegmark. The quantization model of neural scaling. Advances in Neural Information Processing Systems, 36, 2024.
11

---

Nicole Mücke, Gergely Neu, and Lorenzo Rosasco. Beating sgd saturation with tail-averaging and minibatching. Advances in Neural Information Processing Systems, 32, 2019.
Niklas Muennighoff, Alexander M Rush, Boaz Barak, Teven Le Scao, Aleksandra Piktus, Nouamane Tazi, Sampo Pyysalo, Thomas Wolf, and Colin Raffel. Scaling cota-constr language models. arXiv preprini arXiv:2305. 16264, 2023.
Elliot Paquette, Courtney Paquette, Lechao Xiao, and Jeffrey Pennington. 4+ 3 phases of compute- optimal neural scaling laws. arXiv preprint 77Xi::2405.10744, 2024.
Steven T Piantadosi. Zipf's word frequency law in natural language: A critical review and future directions. Psychonomic bulletin & review, 21:1112211111 1130, 2014.
Loucas Fillaud-Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradi- ent descent hard learning problems through multiple passes. Advances in Neural Information Processing Systems, 31, 2018.
Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 30(4))838-855) 1992.
Yunwei Ren, Eshaan Nichani, Denny Wu, and Jason D Lee. Emergence and scaling laws in sgd learning of shallow neural networks. arXiv preprint arXiv:2504. 2et225444.999.. 19983, 2025.
Jonathan S Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit. A constructive prediction of the generalization error across scales. arXiv preprint arXiv:1909.12673 2019.
Utkarsh Sharma and Jared Kaplan. neural scaling law from the dimension of the data manifold.
arXiv preprint arXiv:2004. 10802, 2020.
Aditya Vardhan Varre, Loucas Pillaud- Vivien, and Nicolas Flammarion. Last iterate convergence of SGD for least-squares in the interpolation regime. In Advances in Neural Information Processing Systems, 2021.
Martin J Wainwright. High-dimensional statistics; non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Last iterate risk bounds of sgd with decaying stepsize for overparameterized linear regression. In International Conference on Machine Learning, pages 24280-24314, PMLR, 2022a.
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, 2022b.
Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham M. Kakade. The power and limitation of finttuiin for linear regression under covariate shift. The 36th Conference on Neural Information Processing Systems, 2022c.
Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer. Scaling vision transformers. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 12104-12113, 2022.
Nikita Zhivotovskiy. Dimension-free bounds for sums of independent matrices and simple tensors via the variational principle. Electronic Journal of Probability, 29:1-28, 2024.
Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, Dean Foster, and Sham Kakade. The benefits of implicit regularization from sgd in least squares problems. Advances in Neural Information Processing Systems, 34:5456-544 5468, 2021.
Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Risk bounds of multi-pass sgd for least squares in the interpolation regime. Advances in Neural Information Processing Systems, 35:12909-12922 2022.
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.
12

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
A summary of our results and contributions is provided in the introduction.
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 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: have discussed the limitations of our work in the paper.
13

---

Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on 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 a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
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 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]
Justification: it can be found from our theorem statements and the proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to 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 of whether the code and data are provided or not)?
Answer: [Yes]
Justification: we have discussed all experimental details for reproducing the simulation results in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
14

---

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. w
For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a 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 describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to 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?
Answer: [No]
Justification:
we do not release code and data for this paper at this time.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (nttps://nips.co cc/
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 NeurlPS code and data submission guidelines (https
/ 7/nips. /ttppp.cc/pblic/guideeee http://oeeuuiiiisooooooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
15

---

Providing as much information as 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 have specified all the training and test details in the paper.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
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 have reported error bars for all experiments in the paper.
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, or statistical significance tests, at least for the experiments that support the 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, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-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 errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
show in tables
If error bars are reported in tables or plots, The authors should explain 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 com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: the simulations in this paper do involve any large language models and can be reproduced on a personal computer.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
16

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htttp::/neurips.. htt.://www........oo...cccccaaaa
Answer: [Yes]
Justification: the authors have reviewed the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration 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: there is societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: not applicable
Guidelines:
The answer NA means that the paper poses such risks.
17

---

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 to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators 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: the paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.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 datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release 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 obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: this paper does not involve crowdsourcing research with human subjects.
18

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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 as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, 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 the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: this paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
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 NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration not required.
Answer: [NA]
Justification: the core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA
that the core method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy /ettps://neurr cc/ //oofffrencee/22255555 for what should or should be described.
19

---

Appendix
Table of Contents
A Preliminary
20
A. Comments additional notations
20
A.2 Proof of Theorem] and the corollanes
21
A.3 Relaxation of Assumption
22
Bias error
24
An upper bound
................................
24
B.2 A lower bound
................................
27
3 Bias error under the source condition
29
Variance error
31
C.I Upper and lower bounds
31
Variance emror under the source condition)
32
D
Fluctuation error
33
An upper bound
................................
33
D.2 A lower bound
............
35
D.3 3
Fluctuation error under the source condition
37
D.4 Proof Lemma
40
D.5
Proof Lemma
43
E
Auxiliary lemmas
45
E.1
General concentration hounds
45
Concentration bounds under power-law spectrum
46
A
Preliminary
A.1 Comments and additional notations
Comments on Assumption ID. Throughout the appendix (except for Appendix A.3
we assume
without loss of generality that the covariance matrix H diagonal, with diagonal entries given by the eigenvalues (A:) in non-increasing order. This reduction is justified by the rotational invariance of the Gaussian sketching matrix S. Under this diagonalization, Assumption ID can be restated more explicitly as follows:
Assumption 2 (Source condition), Suppose H (hij)ssa is diagonal matrix with non-increasing diagonal entries. Assume that the true parameter w* satisfies:
for all i + j, B[w:w]] = O; and all i > 0,
E[A for some b >> 1.
Given that H is diagonal, we adopt the following notation. For integers 0 & k* < ktt (allowing K 00), define
H = diag(Ap*41. Aat E ((*l=**)x(('
For example,
Hos diag(An, ........,,,,, Aah. Has diag, A..2....
Similarly, for any vector w IH, define
W == (W -I.... T =
In addition, we define Syeuet gt to the submatrix of the sketching matrix S consisting of the k* 1-th through ki-th columns.
20

---

A.1.1 Assumptions on the stepsize
In the proofs of the general upper and lower bounds on the bias, variance, and fluctuation error, we will require that the stepsize "yo: 7 satisfy certain conditions, which are summarized in the following assumption.
Assumption& 3 (Stepsize conditions). Under the notations in Theorem 3.7 and its proof, with proba- bility at least 1 exp( over the randomness S, we have
1. & minfc/ log N, N,e/tr
2. tr(E²) $ 1;
SM
(2) (((a)) & N/4;
the initial stepsize To = min(1/[4max [S (8) satisfies P(70 < <1/t) & N-d for all 3 1.
We will show that Assumption 3 holds when the conditions in Theorem 3.1 are satisfied.
A.2 Proof of Theorem
3.1 and the corollaries
A.2.1 Proof of Theorem
Proof of Theorem 3.1 Let v* (SHST) SHw* and adopt the shorthand
SX
Σ = SHS
:
N
Also, let D = (x,, v1) [1 denote the set of training samples. Then we have the decomposition
ERas(Vi) = E (xx, T vL> - v) "] = E (x S
VL w*> - - = =0 E (x, VL =
0² + B (x, S (vE vv*) S v* w }
① 02 E S y* -w "
x ST (vr. -
(x, S x* w + E (x, S ((02 -v*)>² + E S [vL -21)
S v*
E
0r, v + E Vv. 0r. 322
Irreducible
Approx
Excess
Fluc
where step (i) uses the fact that E[Sxx (ST v w*) E[SHS uses the fact that E[v,,|,, w". D 0,.
T v SHw*1 and step (ii)
Irreducible error.
From the above decomposition, we have Irreducible R(w*) σ².
Approximation error. We have from Lemma C.5 in Lin et al. (024)) that E Approx = Ews S * w* ~ M1-b with probability at least 1 e (I(M) over S.
Excess risk of GD) Let ē = - x ST verified that, conditioned on (S, w B(ēe] and independent of Sx,. Moreover.
v* for E [N] and write è = ( [N) It can be
v² := E[ o² + Ew w 1
= 0² E [w" TT H 1/2 ( - H 1/2 (SHS 'SH H) 2
& 0 B w+ 1 02.
Note that by definition of GD we have
0. V 0, - =
7t
SX
XS 0,-1 - y) 0 -
?t Sx (XS (XST(0,111 (0,- --)
N
N
-(I-715)
7t SX é, 0 v*)
N
21

---

and therefore
0L v" -11
-v) (00 2 (0, 11-0
(4)
1-1
where
I (I -12 x
V(E) = N 7
1I [I- 15
1=1
NΣ
i-1+1
As result, the excess risk of GD) satifies
L [I-
E [Excess]
+ + V( E
Σ
Bias + o Var,
where Bias == Ew [Bias( w*) }] and
Bias(w> Ex 11 [-1
(I (I-
21 E.
: v( ))
and step (iii) follows from the fact that SXT is independent of conditioned on S. The bounds the bias and variance follow immediately from Lemma B.3 and C.2 C.2
Fluctuation error. It follows from Lemma D.5 and the assumption 7 & c/ log N that
[[Fluc] & ry log N [(Latr)) Va-1 + (Less?)
with probability least - ------0000 -9(M) over the randomness of S. The lower bound on B[Fluc] also follows from Lemma D.5
A.2.2 Proof of Corollary 3.2
The proof follows immediately by combining parts 1-3 of Theorem 3.1 although we make a different
assumption the initial stepsize "Yo. In Theorem 3.1, we assume 7No min(7, 1/[4 max; |Sx |
for some ? & 1/ log N, while in Corollary 3.2 we assume Too = min(>, 1/[4 (SX T /))
for some 7 1. This modification is valid because Lemmas B.J B.2 and C.I used in the proof of
parts 1-3 of Theorem 3.1 continue to hold under the alternative choice of stepsize.
Specifically, their proofs mainly rely three properties: (1) I P(yu < 7/t) & -t for all > and (3) claim (15a) holds. Under the choice % min(7, 1/[4 ([AALXXXTTTTN]]] XST))]]] the first two properties are satisfied by definition and by the Hanson- Wright inequality (see, e.g., exercise 2.17 in (Wainwright (2019)). The third property follows from similar symmetry property for (o') == 1/ /N),, as used the proof of claim (aa).
0, (2)
A.2.3 Proof of Corollary 3.3 and 3.4
These two corollaries follow immediately from combining parts 1-4 of Theorem 3.1 and some basic algebra.
A.3 Relaxation of Assumption T
In this section, we show that some conditions in Assumption I can be further relaxed. Concretely, we have
(a). The exact alignment of the eigenvectors of the prior and data covariance in Assumption TD) is not necessary. All results in Section remain valid if Assumption ID is replaced by
22

---

Assumption 1D' (Approximate source condition). Let (A2, Vi)sso be the eigenvalues and eigenvectors of H and let H [[ Assume cHW H absolute constants d' a c > and Hw 2 such that for i $ J. V. Hw
c'HW for some
and for 0, Avv, V; for some b 1.
(b). To establish the upper bounds for Bias, Var, Approx in Theorem 3.1 and the upper bounds
in Corollary 3.2 3.4 Assumption IA can be relaxed to
Assumption 1A (sub-Gaussin Gaussian design). x = H where E [
] = I, and the vector
X is zero-mean and vector v and all e R.
i.e., E 0 and Xv E ex for any unit
We provide some justification of the two relaxations below.
Justification of (a). By checking the proof of Theorem 3.1 and its corollaries, it can
be seen that Assumption ID is used to (1) give matching upper and lower bounds on
1. (SHH"HHS ") for any k > 0 and i E [M] when control- ling the approximation and bias error (see Lemma C,5 in Lin et al. (2024) and Lemma B.3): (2) give matching upper and lower bounds on E[ w 1|2 when controlling the fluctuation error (see
Ew [[] Ew [[[ k:oo
Lemma D.5). Under the alternative Assumption ID it is readily verified that the same bounds on these quantities can be established up constant factors. Concretely, suppose there exists some parameter w* with prior E[w #T Hw. Then w satisfies Assumption ID and
w
W
tr (
tr H 0:k
E
O:k
E [
tr
k:00 tr
Hw
H
Ews W R:00 H...
2
0:00
1::00
pi (SHH HS 44 (SHH
tr (
H /2) (r( 2H (3)
BR H..
H
where step (i) follows from the fact that μus ()) & pa (B) for all and any 0 = A = B. Therefore,
the proof of Theorem and and its corollaries goes through under the alternative Assumption ID
Justification of (b). In short, for the upper bounds, the relaxation can be made since the Gaussian assumption is mainly used establish certain concentration bounds (e.g., Bernstein's 's inequality),
which also hold for sub-Gaussian vectors. More specifically, the Gaussian design in Assumption IA is
used in our proof mainly in three ways: (1) to establish concentration bounds the sample covariance
(e.g., Eq. Top: : (2) to allow the use of technical lemmas in Appendix (e.g.. Lemma and E.4 (3)
control the norm of sketched samples (e.g., control B, Eq. 20
Correspondingly, when x satisfies the alternative Assumption TA we can show that (1) the same
concentration bounds hold on the uub-Gaussian sample covariance by e.g., Theorem 6.5 in Wainwright (2019; (2) all technical lemmas in Appendix hold when the Gaussian sketching $ is replaced by a row-wise
matrix by concentration bounds on quadratic forms of sub-Gaussian vectors (e.g.. Theorem 1 in Hsu et al. (2012)), and on nub-Gaussian covariance matrices (e.g., Example 1.5 in Zhivotovskiy (2024)); (3) the norm of sketched samples satisfy the same concentration bounds by e.g., Theorem 6.5 in Wainwright (2019).
On the other hand, for the lower bounds, the Gaussian assumption is still required in order to establish the conditional independence of é; y/ x! ST v* and Sx, given (S, w*) in the proof of Theorem and LemmaD.44
In addition, we also conduct experiments to check our justification of (b). We generate data x (I1..... x2) from the distribution where 2; are independent and
P(z, = 1) = P(x, = -1)=
P(x, = 0) = 1-13 2 2 P(x, = 1),
Note that x satisfies Assumption IA' but not Assump- tion IA when d = cc. We run the experiment under the same setting and choice of hyperparameters as Figure a Similar to the Gaussian case, in Figure 2 we observe that the excess test error of one-pass SGD and multi-pass SGD both exhibit pawer-law scaling in the number of effective samples Natt. Moreover, the fitted slopes are both close to the theoretical prediction Corollary 3.3
with a 2, 1.5 and co -2E
1-0
(0.34 0.33 (1 b)/b for multi-pass SGD and 0.26 ~ 0.25 (1 b)/a for one-pass SGD).
23

---

multi pass (K- 0.34) one ens- (k=-0.26)
Excess
10-1
Number of effective samples (Ner)
Figure 2: Multi-pass SGD versus one-pass SGD for non-Gaussian design. Multi-pass SGD is run for Na/b steps. We use linear functions to the excess test error in log-log scale. The fitted exponents (k) are close to the theoretical predictions in Corollary 3.3 The errorbars denote the #1 standard deviation the expected excess test error over 100 i.i.d. samples of (S, w w"). Parameters: σ² 1. d 10000, M 1000, 0.1.
B
Bias error
B.1 An upper bound
Lemma B.1 (An upper bound on the GD bias term). Suppose Lott & No byy and Assumption and 3 hold. Under the notation in Theorem 3.1 and its proof. for any w E and & M// such that r(H) M, the bias lerm
Bias( w*) Ex
II 1=1
[I
--
v*
cl @@
(M/2(Ass HM (Ax)
+ BB | Ha.
Lest"
with probability at least -M(M) over the randomness of S, where A = Skize Ha Skvoo and
BB = of + [( +1]
/ (1
tr
tr E
k:00
E
N
N
N
for some constant c 0 and io = [N/2
Proof of Lemmal B. Without loss of generality, we assume the covariance matrix H
diag \1, A2,
Aa) where A > Xy for any > j. Let (A1, 7 1e....,A,, Ad)) denote the eigenval- ues of Σ non- con-increasing order. Moreover, we introduce Zı.... Nn
rid NN IM/N) and write
[z). ....... 2N) It can be verified that XST/VN Z conditioned on S. Throughout the proof, by union bound argument, we w.l.o.g. assume the conditions (1), (2), (3) and (4) in Assumption always hold.
Define M = I (I- EJ E and recall that v (SHS " SHw* Substituting
SH (So. Husk
S k Hg:oo)
into v we have
Bias(w*) = -Ex/v* Mv
= Ex w*
HS
27 2T2,
II & > A then Σ Ei 0.
24

---

where
T1 = Ex 0:k)
Ho:k D.. (HS
MMSSS
So: Ho: work
(5)
T2 = Ex (wi k:00
H H::00 S
(SHS)
Hose W Weod
(6)
leoz
We will show the following results at the end of the proof. First, with probability 1 e-R(M)
c/ dookkl
(M)2(AA)
Ti <
(7a)
Locty
(M
for some constant с 0. Moreover,
T2 < BB
W H
(7b)
Combining Eq. 7a and
(bb gives Lemma B.1
Proof of claim 7ap. By definition of Ti, we have
Ti
< Ho. S
H [
M 2 [(SHS)) So. 13 ||
for some constant c 0. By Eq. (23) in the proof of Lemma D.1 in Lin et al. (2024) we have
(SHS T S Ho.k & (M/2(As))
(8)
PM (A))
for some constant c with probability at least - Thus, it remains to show
Ex [x[[ &
LooftY
for some constant > 0.
Let be fixed value be specified later. Note that
|||2
11 [I 7. E
1/2
n
E
Al 1/2 + AIas) -1/2
[=1
t=1
EE
ALM) 1/2/2 -1( (Im) 1/2 -1/3) 1//213
1-1
(1
E) 3 + +*) -1( AIM) -12
1-1
(1)
+ 2)
(0 ALM)
1/2
Lorr
where step (i) uses the fact that || - 76 E1 & 1 by the stepsize assumption and step (ii) follows from
the stepsize assumption (2) that 7 to for t [Lare] combined with the fact that sup 10/1/ x=1- )o=)) 2hatt & c/(70 Tutrr) for some constant >
Recall that we assume P(10 < h/t) & - for some constant c > 0 and all t > 1. Thus, Eq. 9 follows immediately from choosing À 1/(Lerr7) in the last display, applying Cauchy-Schwartz inequality and Lemma E.1 and noting that (1 + Lese 3n² exp(-eN)) & 1 for Lese $ N
Proof of claim
7b
Let B
Ex
E
1/2 I1
(I
E (I- EEE 1/2
By definition
of 22 in Eq. 6 we have
T2
w 6::0
T
H
ST
Σ
1/2
BY 1/25
k:00 H Juzz k:z
B 2
H
S
1000
Σ
Skizz
H
1/2
|| kooo
H
25

---

B
|wicon He..
where the last line follows since
1/2 ST k:00 E
Sk:ce H
1::00
1/2
[
1:00 k:00
1/2 ST
Hu: So: + Sk:ce Hk:ce
Sk:co H
1/2 1x0 2
A
Sk:z
H k:o l2 $ 1.
1:00
k:0
In the following, we will show that B 2 & BB, which immediately yields claim (7b).
Let Σ XS SX /N. To compute
B 2. note that
L-1
L-1 I| 3
[[
I1 [I x
2-1
1-1
(80)
(I x
1 sx 7z
II (I -1- ( XST
1=1
I
SX T
Σ
7+t1 - X XS =: - C,
N
1=0
1=1
where step (iii) uses XS (I (I- on S, we can thus rewrite
(I (1-71. Σ) XS Recall that XS //N z conditioned
B Ez Σ
1/2
CJE((
CJE 1/2
21 + 2E Σ
1/2
CECE-I 1/2
21 2E
Z
7+
7
Σ
ZΣ
Z
7+ [I-= where Σ ZEZ
1=0
[=1
1=0
1=1
Introduce the shorthand R
Di
7++1 1 - R) and (k( = (I (I
ThIe 2 Lure) ) E for h [0, [log Latel - -I.. Note that [A)ll) & Lott +bb since
Vklest 12)) Lorr )/x] Loet II Therefore
supse(0.1/7e1.ar-
L-1
blog L-ee--1
[log Latel 1-1
M+
(I
(A)
Lott Velart1 & 2latt
t=1
where the last inequality follows from ( and the definition of no- We consider two cases.
Case 1: M N/2. In this case, have
Z 1 5. (ZEZT)
(10)
with probability least 1 e0(N) since P(Z M 1 e Q(N) by concentration of Guassian covariance matrix (see e.g. Theorem 6.1 in Wainwright 2019)). Moreover, since
tr 2 $ 1.
ZJ ZRRZZ'Z R₁Z = c. Z Z ZZ J R,Z RR IM
x c(Lerr?) 2 2 IM-
Therefore,
Ez R Z
< cE R Σ RRERR, + cE
Z 2/21121 z Ia (11) cEz IZ Z] + el c(Lotr exp(-c' N) Las 1 clM
for some constant C, I 11 7: 2|22
0, where the second line uses the fact that RR
< 1, concentration properties of the empirical covariance matrix Z Z, and E. EZ Z] M- As a result, |B]|2 2 + [R, R Z)]2 $
26

---

Case2: M > N/2. Let N/2. W.l.og,, we assume Σ is diagonal matrix with eigenvalues
A Aas in non-increasing order. With probability at least 1 6 -S(N), we have the decomposition
Z R, Z' R,Z x 2z R1 0..
D 0:k
Z
R2
Z + 2z
R,
(1(Z
Σ
Z
R
0:
10:00
K:00
1 cZ Rí 00.
20
R Z + 2z
R
ZZ
2
JR
0: 0:
2:00
1:
c( R. u. 2
0:k
1Z 1::0
k1:00
Z
1::00
12) Z
3 cl Ri (Z 2
112
|R. Σ13
+ 1
Z
22) 12) Z.
1:00
1:00
k:00
1:00
k:00
where the second line use Z 0:A o.. 2 1k/5 with probability at least
E
R((N) the last line follows
from triangle inequality. Since R1ll2 Lotty and R, E continuing the calculation, we obtain
7/6 E & 1,
Z R Z R,Z c((Lets))) ke: (
Ex:00 Z
12 +
k0:00
Σ Z
4:00 h:cn 12) ZT (12)
1:00
Since we have by Lemma that
tr( trool
tr tr(2)
Z k0o
Z 12 & Rear
+
EΣ 1k:00 l2
k:00
N
N
tr
2
loo
Σ
k:00
1::0
+
log
(13)
N
with probability at least 1-8, and tr argument that
$ tr Σマ
S 1. it can be verified by a standard truncation
Z 1:00
1:00
1:00
ZTZ)
Z
I
c
tr
(
N2
E
kooo
Σ
1::00
tr E
N
R:00
IM-
A similar bound can be established for [ the expectations into Eq. 12 we obtain
Z
Σ
Z [12].
Finally, substituting the bounds
1100
1:00
Bl2 < 2 + 2 E
R, Z, Z
(1 k:con]
tr Er
tr Ed
$ c 1+ [[ 1](
N2
Σ
10c0
12
+
N
R:00
+
N
B.2 A lower bound
Lemma B.2 (A lower bound on the GD bias term). Let Assumption TA and
3 hold. Define H
El w w* and Ew SHHWHS Under the notation in Theorem 3.1 and its proof, the bias
term satisfies
E (Bias(w*))
E I
I 1=1
[I I-
x
v
M
Pai Ew)
14 Σ)
2=27+1
with probability at least e -M(M where == Exi# [M] AcLecr > 1/4}] and (2)) are the eigenvalues of E.
Proof of Lemma B.2 Similar the proof of Lemma B.1 w.l.o.g., we assume the covariance matrix H diag (}1 A Xa) where X XÚ for any > j. Let (d1, Ag...., AM) denote the eigen- values of Σ in non-increasing order. Moreover, introduce 2,, 2N Z (Z)...., zN) T. It can be shown that XST //VVV d 1/ conditioned on S.
sid N( I M//N) and write
27

---

Let C2 == IT= (I -/ E). By definition,
Bias(wy wn) = Ex II (I 2: 2e
Ex|C
(14)
Adopt the shorthand Ew for SHH HS
Substituting the definition of v into the expression and
noting that E w* w* H we have
w Biass w )] +
+ [v"
Ex[C]
= tr(HS ) SHHH"
Ir(HS (SHS) B [X CC --HHH
Ew Σ-E-1/
where step (i) uses the fact that El B[
E YY for any random matrix Y. We claim that
Σ
1x | 1/2 [x[C1]. and
(15a)
1
PM PM-i+1 (Ex[ >
(15b)
2e
for all E [2F + M, where == Ex [M] X, > 1/4]].
The proof of these two claims will be given momentarily. Continuing the calculation using the claims and Von Neumann's trace inequality, obtain
w Bias(w** > [[]tr[E[[[]]
E, 1-11]
1/2 E Σ
M
( m+ 11//5 v. 1/22)
M
M
Σ
O (4--11/2 1/-1122
E---- --122)
Σ
p.(E 1/2 Σ 1/2).
(- 27++
i- 27
Since 14+5+1 (XY)= & M44 we have
for all i and any matrices X, Y of matching dimensions,
P2i-1 (2 1-12)
13i M3i-2 2
P3i (ww) (x
N4 SE
N4 (1/2)
11 [1/2)
Combining the last two displays yields the desired result.
Proof of claim [5a). Define the learning rate (T( = miin[1[fe max, [T.51 7 for any matrix
I' E M and define 7e(I') for all E [4] according to ( Let Σ = UTU be the singular value decomposition with U = Ia and I = diag(Aı..... Aas being diagonal matrix with
À > do 2 AM > 0. Note that SXT ///N á U/1/22T conditioned on S and U ÊU d
T Therefore
1
Ex Cx] = Ex
-
mS
UEx I (I- 7e 22) "
t=1
= UE [
(2T 1/2 12/2zzz2z1 2
Adopt the shorthand notation 24 that 7/ is equal to "o up to some k-dependent constant factor)
1/ and write 24 (fi,.... pN) It suffices to show (note
M Ez/oo(v (
is a diagonal matrix for any K > O. Consider the kl-entry Mg. It can be written as the sum of terms of the form Ph (12.d2 ... Migx Jak with j1 = kt J2K I, 1,m j2m+1; m E [K -K-1 When & s I, there exists some i E [N] such that Р., appears odd number of times in the product. Since flipping the sign of pi, does not change "oo (vNu ) and Mi.j are independent symmetric Gaussian variables. follows that P ( /Nu ) Piy.i Mig.j [ixx
Consequently, we conclude that
M for 1 and M is a diagonal matrix.
28

---

Proof of claim 76. Let ÜÍÔT be the singular value decomposition with f
diag (i,g, Am and d b ... 2 Am. Then we have
L [1a- x = (I 1-2705))uu fu = ÜÜ 27 hree Ü
(Ia Una U
where i := # i [M]] XeLeerr to 1/4). Here, the first inequality follows from I Dog
Ti=00
The Σ 2 I - 270 E since (1 - -1](1 - 12) 2 1 - t 12 for all t1, E [0, 1]; the second
inequality uses (1 x) baer e exp( (22Lee))))) De for x [0, [0,1/(2 [. Therefore,
Ex[C1] Ex - 20 -))
1
LM BIū U.cl].
Since (r 0 T 1, it follows that E(Ü d:t U.d has most 2 eigenvalues greater
than 1/2. Since X = Y 2 0M implies (4; (x( > (Y( for all [M, x,y RRM by Weyl's
inequality, follows that
PM PM-i+1 (Fx (C.]) > 2e
for all >> 2ix [M] 7. > 1/4)| +1.
B.3 Bias error under the souree condition
Lemma B.3 (Bias bounds under the source condition). Let Assumption hoold, >> b- and assume Lett S No /7.. Under the notation Theorem 3. and its proof, there exist some (a, b) dependent constants é 0 such that when 7 & c/ log N,
E * Biass w $ max (1 MM' when (Tatty)) & M/d.
B [Bias w *)] 2 ( (Tatt?)) (1-bt))(1-))/a b)/a (1-b)/a
with probability at least 1 -
over the randomness of S.
Proof of Lemmna B.3
The proof follows from applying Lemma B.I and Lemma B.2 under Assump- tion We begin by verifying the conditions required in these two lemmas.
Verification of conditions (1)-(4) in Assumption 3 First, by Lemma R.5 have (4 (E) j-
with probability at least 1 - exp( 10pp--2((M)) (2(M)) over the randomness S. Since a > 1, it follows that y S min(1, c/ tr(E)) and () & 1. Thus, conditions (1) and (2) in Assumption 3 are satisfied. Moreover, when L z No, we have
M
Σ
p4(2)
( + L((L)))
< # [M] (I)) 2 1/(Lest7)) + (Lese?)
Σ
Mi(E)
$ Ma + (Loett).
Σ
m+(E) $ (Lott?) 1/4 (Iatt?)
$ (Lesey) Va N/4,
where the last inequality follows since we may assume Latt & ZN /ry for some constant ē sufficiently small. Thus, condition (3) in Assumption is satisfied.
To verify condition (4) in Assumption we introduce Zı.... .Ny
(O. and write (2) (Z,...,, TN)T_ T. It can be shown that XST I/N 1/ conditioned on S. Therefore, have tr( Σ) tr ZEZ ), where Z E NxM is Gaussian sketching matrix. When (2E x i- for all
ZN
lid

---

i E [M]] (which happens with probability at least 1 - (xp(-9((MM) over S by Lemma E.5 we have by Hansen- Hansen-Wright inequality (see e.g., exercise 2.17 in Wainwright (2019) and union bound that
N max Zi EZ. [
v tr Σ +
اال (og(N/0)) + || F Vlogoo//// N/0) s 1 + log (6)).
with probability at least 1- 6 over the randomness of Z. Thus, there exist some a-dependent constants
c, c' such that when 7 $ c/ log N.
PP( < 7/0) P(t/(4n) < max Sx, 2 F(1/(4n) N max Z, EZ.,) & N
for all t 1. Therefore, condition (4) is also satisfied.
The upper bound.
By Lemma
E.5 we have BB in Lemma B.1 satisfies
BB c. (1+ Lest" 2 (N 2a
N
2a + N + N 20) & c (1 + 22)-2a)-
20) $
with probability at least 1 - cxp( 1 ((M), where the second inequality uses Loss & N Moreover, we have by Lemma E.6 that (An)
with probability least exp(-
Jar [M
Now, choosing & min(M/3, (Ioef?) M/] in Lemma B.1 using Assumption expectation over w yields
ID and taking
max(k" b+1 + 12-b s max(( (1-b)/a
w [Bias(w []]
(1- M
Lorry
with probability at least (ap((-((M)) over the randomness of S.
The lower bound.
By Lemma
B.2
we have
M
A33 Eww
E Bias w x
Σ 2-2
with probability at least 1 (MMM), where 7 = [i [M] Le > 1/4]] and (A,,
[M] are the eigenvalues of E. Since E L zΣZT conditioned on S by Lemma E.3 when H46 (Σ
i- for all [M] (which happens with probability least eep((-((MM) over S by Lemma B.5 we have by combining Lemma E.4 and E.3 with k = that that
S2j-1 (ZE
& My (Zoz Eo. Zioke) + M4 Zh:00 Ex:c kiooo)
+ log( 1/8)
(z)())= -NN-+ N log(1/0)
N2 2a + N 2a log (1/8)
$ [
N
No+1
N
log( log(1/6) 1/6)
.j + N N (1 log(1/6)
1og(1/6)
$ 1 +
(16)
N
N
N
for all j & lt with probability at least 1 over the randomness of Z. Therefore, it can be verified by a standard truncation argument that
t Exl#x E [M] AcLorr > 1/4]] & (La
Thus, when (Ioet (0) 1/2 & M/c for some sufficiently large constant 0, we have
Pail Ew)
M
Ews Bias(w*)
Σ
(2-b)/)
14
P4 (Farryy)))
27+1
(Fiwery)
with probability at least 1 - exp(- ((M)) over the randomness of S, where the third inequality uses Lemma B.5 (with replaced by HHwH).
30

---

C Variance error
C.1 Upper and lower bounds
Lemma C.I (An upper bound on the GD variance term). Suppose Assumption IA and hold and Lett No //y Under the notation in Theorem 3.1 and its proof, the variance term
D
D
Var ==
and
Var z
N
where
D = Ex #liE [M] Aebarr 1/43 + (Larr
Σ
T.
to 1/4
(i)
Dt = Ex (Iatte7))
Σ
p+(2): pa ( +
Σ
1/1 (x(1i)
bate
4: Leste no >
and (2
M are the eigenvalues of Σ.
Proof of Lemma C.1
Note that
1
7 II (I- (I-nE) x [I-II-- (I Σ)
v
i=++1
Adopt the shorthand V1 for
I (I 71 E) Reorganizing the terms, we have
Var N V[VV = [
Let Ai,... Par be the eigenvalues of in non-increasing order, and let À > 0 be some value which will be given later. We now derive an upper bound and a lower bound for the variance Var.
An upper bound.
Continuing the calculation, we further have
tr tr -V)
tr 1/2
S
AI)
1/2 [ + AI) 1/2 //>05/ AI) 1/] + 12 1/2V
Σ 1/2
S
AI)
1/2 [tr(V] -V-1V
Similar to the proof of claim 7b in Lemma B.2 it can be verified that V, = 1 - (I- 2 E Lats
under the condition to & 1 max, |Sx, ? < 1/[4tr [E)] and stepsize assumption ( Since
(1 - (1 Toz) brtt) )2 & min (xLerr 1) for x E [0, 122%) by Bernoulli's incquality and
suP|o.1/>o1(11
>02) best //r] Tott it follows that
(a- (1--(1-20 1(1 (1 2% Larrs )
urV2 + 1S-1 &
X
+ (LoerTo) 1 121l0rr7021/47
+ ((Latrro(((Latrr) (Rptarr7o) 1 1
Choosing 1/(Larr7) & 1/(Larr70) yields
tr(V2 + (V2)
#(i [M] A. 1/4) + (2
Σ
X + (LoerTo)
Σ
=; Du
$ #li [M] RoLoest > 1/4] + (LesrTa)
Σ
x =: Du
(17)
31

---

Applying Lemma E.1 and noting that tr(V2 + VΣ VV2) & N as Vz has at most N non-zero eigenvalues. we obtain
Ex(tr(EV, Ex #(iE [M] A > 1/4) + (Lese
Σ
to
lower bound.
Similarly, by Von-Neumann's 's trace inequality, we have
(2) 3
M
M2(M- 1)+ (V..5
tr VV)
p 11)
Σ ui
(M-i+1(E-1)
M
(6)
Σ pi(2)) ui (Σ) -
where step (i) uses Mi+jj+ (XY) & Mi+1 (X) for any matrices X, Y, and step (ii) uses the
fact that u1 (E) 1/ // 11 (E-1).
Note that V,, > I- (1 70 E Luu Since f(x) == (1 (1- (1 )
free 1 2 is decreasing when Toat 1/4; (2) f(x) > 1/(5z²)) when
function on [0. 1/1o] and (1) f(x) > (Tatt?70)
2/4 )
"0 2 1/4, we have
(VV\-=VV)) (L)
Σ
m((2) (0044(())
Σ
Ha Σ
:d :Achaer702114 M4(
Taking expectation over X yields the desired result.
C.2 Variance error under the source condition
Lemma C.2 (Variance bounds under the source condition). Let Assumption 7 hold and assume Lott No //t Under the notation in Theorem 3.1 and its proof, there exists some (a, dependent
constant e > 0 such that when 7 & c/ log N.
Var min (M, (Iast7) 1/a
N
with probability al least 1 exp( exp(-S((M) over the randomness S.
Proof of Lemma C.2
Similar to the proof of Lemma B.3 we can verify that conditions (1)-(4) in Assumption 3 Jare satisfied with probability at least 1 - expl ((M)) over the randomness of S. From
the expression of D it is straightforward to see that D < M. Moreover, applying Lemma Eq. (16) in the proof of Lemma B.3 and truncation argument, can show that
DU = Ex #(i E [M] Losts > 1/4] + (Lees
Σ
&
$ (Leee7)) Ex (LeerT)
Σ
S. $ (Lees7)
with probability at least - DV A min(M, (Fatt))
over the randomness of S. Thus, we have obtained
For the lower bound, when (Lart 1/a & M/cc c for some sufficiently large constant > conditioned on such that (Z) = ja for j [M] (which holds with probability at least 1 - e -R(M) by
Lemma E.5) we have by Lemma E.8 that (1 j jaa for j & Mi NN/ē with probability at
least 1 - - RMM for some 7> 0. Therefore,
DL Ex (L
Σ
H. (E) (5(
32

---

z (Loss7)3
Σ
1 2 (Lees?))//
t 1 (M,
where the last line follows since we assume (Lese?) Vo < M/c c for some sufficiently large constant > 0 and (T & N N/c.
On the other hand, similarly, when (Lo 3 M/c for some sufficiently constant c > O, conditioned on S such that Py [)(2))
n for E [M] (which holds with probability at least we have by Lemma E.8 that py (E) ~ j for j & with probability
1 - R(M) by Lemma E.5
at least 1/2. Therefore,
D Ex
Σ
U
Σ (
2 Ex
EE( fase fe (2)
Σ
2 M.
5
t.A.
To 1/4
#4
Putting pieces together yields the desired lower bound.
D Fluctuation error
D.1 An upper bound
Lemma D.I (An upper bound on the fluctuation error). For each E [N], define the leave-one-out GD process
0 1) - (I 76 ( )/ + xSS y-) with 0 O,
(LOO-GD)
where
((11) = = Sx,x] 3 ST /N and (SX y) Ejjr Sx,V./N.
Let Assumption IA IB
3
hold and assume Lott & N4/7. Under the notation in Theorem 3. and
its proof, for any E [0, a 1, there exists some (s, (1) dependent constant fluctuation error satisfies
0 such that the
Fluc = (x (X: (e..
Σ 1/2 11/2(V/ -
0r)
< c. E[F tr [ 7t// Latt 1/a-1
with probability at least 1 exp( (ep(--(((M)) over the randomness Sf where
= R
max iE(N]
x ST
v*
max 2?
(x.S (x]SSO( 0)) + max | |T E- BBA.
iE|N]
iE[NN]el|L]
N
(Lese?)) and
BA max
max [E[N]
Sx;l12 R.
[) + x ST (TTSTO--0 -(-0) A:=
Rt= + 1/2 12
Gmax
max le[M].te[L]
Losty
Moreover, if ( R j for & r(( r{E) for some a > 1, then
E [ Σ 1/2 (vV 0z)1 < dEFF] > Loes 1/a-1
for some a-dependent constant d'
Proof of Lemma D.I The proof of this lemma follows from similar ideas in the proof of Lemma in Pillaud-Vivien et al. (2018), but with more precise characterization on the magnitude of GD outputs. We start with overview of the proof. At high level, to bound the fluctuation error, express the difference between the multi-pass SGD and GD trajectories, V, 0,, as a stochastic process (Eq. (8) that fits into the framework of Lemma D.2 which provides an upper bound on the fluctuation error B[] 1// (v. (2) under certain conditions, up to mismatch between E and Σ. We verify that the required conditions hold with appropriate choices of parameters (Fq. 20). which are further bounded using a leave-one-out argument (Lemma DD.3). Applying Lemma D.2 with these
parameters and covariance replacement trick (Eq. 21 yields the desired bounds.
33

---

We now proceed to the proof. Define A == Vi 0, for t [0. L]. Recall that v* (SHST) and we have yi (Sx;) v + é, for all i E [N] with & independent of Sx; conditioned on (S, w*) under the Gaussian assumption in Assumption LA] Moreover,
B S w = 0 and E SS w* & o² + || H =: dw("). By the definition of v, and 0,
mulli-pass SGD) and (DD, we have
A (I NS,, x S م + 7o (51. + E2.1)
(18)
where
A 0, E :- - Sx, x STSTT ST - -0.
and E,, = Sx,, - SST E/N, Le [7]].
Note that conditioned on w*, S and the dataset DD (x;; y)) the noise terms E w*, D E[ w D] = 0. Next, we present the following two results.
Lemma D.2 (A modified Proposition 1 of Pillaud Vivien al. (2018) for the last iterate). Consider any recursion of the form
Mt = (1 (1-18 7/- 1ove))p ) + "t- Et, 1i = 0, E [E]L]
(19)
where the learning rates (r=) are as defined in Theorem are independent random vectors. Assume that Eluve = Ex, [[cc] = O. Elu,, Mu s BEE,
3.1 and Eq. (2). (vr, 6i)/-1 E RM x RM
E[E = L... and 9o B2 < 1/4. Then for any u e [0, 11. we have
E Σ. ur co y tr (Late))))
fot any a > and some o-dependent constant c > 0. Moreover, there exists some a-dependent constant d', ē such that when 22 (E,) マ jj for j min(M,N/ik we have
E| E μn 3 & o ((Leer)) 1/0-
for any u e fo, 1] and some a-dependent constant d' > 0.
See the proof of Lemma D.2 in Section D.4
Lemma D.3 (A leave-one-out bound on GD iterates). Under the assumptions and notation in
Lemma D. l for any [0, there exists some s-dependent constant c > O such that the (GD)
updates 0 ( satisfies
max [e[
(x]
S 0,) c.
max [e[]]
(x.STO( (5
max ie
x TT 2 2- BBA
See the proof of Lemma D33 in Section D.5
Let v Sx., E E1,e ε2, We claim that (Vi, Ex) satisfies the conditions in Lemma D.2 with
E, E, Bp
max [Sx, 2: a [
max [[x] [(x]ST (0,-1 v*))² + {
(20)
de[M]
Thus applying Lemma D.2 with u = 0, 1 to the stochastic process in (8) and letting X = Ieer yields
E /e///////////// 0z)1 = | + 1/ ( |e ( + A1) 1/2 1/ 1/2 0r)13
(21)
$ oo -1.1 AI 1/ (1k 1/2
tr E011 (Loc)) 1/a-1
Moreover,
max ie N
S v x²
+ max o ie
max
(x] ST TT)2² 0.)²
NN
ie ie[N]tte
max [N]
S
max [N
2
(x] S 0 00)0 max ie[N].te[L]
max
| [N
S T BB
where the second line follows from Lemma D.3 Putting the last two displays together and taking
expectation over (x; y)) w yields the first part of Lemma D.1 The second part of Lemma D.1
follows from the same argument by applying the second part of Lemma D.2
34

---

Proof of claim 20 Conditioned on S and (x,: W.) when choosing = , we
Σ, and E[u,v vuu & [[maxx[[]] | N [aX Sx 1 Σ B2 Σ. Thus we may let Σn = Σ and B, = [ |Sx In this case, we have BB & 1/4 by the assumption that y/ & [ ||Sx; 31. It remains to
have [[ ]
x
bound of in (20). Note that
E[E 1 22,
2 (01-1 - (0=1- v*) "V) 1+ +2E[Sxx (Sx.
= max (x -v=)= En + 2 max & Ex. [e[N]
[e[N]
where the second line uses Jensen's inequality. Therefore, we can set
( (0.-1-
max [E(N]
and the conditions required by Lemma D.2 satisfied.
D.2 lower bound
Lemma D.4 (A lower bound the fluctuation error). Let Assumption LA
TB
hold and assume
Lott $ No No/ry. Under the notation in Theorem 3.1 and its proof. with probability at least 1 exp(-Si(M)) over the randomness of
E 4, s. 1 1/2 1 - -0))
き (0² + | [t) (xx)eeet)
Em:(E)
(E) M/s (
10
is!
where Be : maxt N-1 4ot B2 03, B, [ [Sx and i = #li [M]
N
X:Loct70 > 1/83, and (2:) are the eigenvalues of E.
Proof of Lemma D.4 Define A, = 02 for t E [Z]. Similar to the proof of Lemma D.1 conditioned on and w*, we have
[I
7/ S. x ST ) + " (E1, + E2.1)
L.
7/
Σ (I (I-7,5x
Sx, x ST) (EI, + E2,)
(22)
j-itl
where
Ao 0, E1,1 == - Sx, x S (0 and E2,1 := Sx,,, SX SX E/N, [4],
and é; are i.dd N/O, 82 (w independent of Sx; conditioned on S and w", where (?(w")
²² + | 2 Let B, == [N] Sx; We claim that
(E R. R + (E1, + E2,)
(w E,
(23)
and we have Bg > 1/2 when (Turr?) B N 1/3. The proof of this claim is deferred the end of
the proof.
Since E1,e and E are zero-mean noise, conditioned on S, w and (x,, W. we have
E B. | 1/2 (vy (v2
0,)
II
(a-
(x-,,xx,xIss1
STS J
II (I Sx,,xx,ss)
( (2.) D)
j=i+1
j=i+1
35

---

L
=w²(")) )B
2/ tely [tr
II (I - ,)
II
(I
7,
s=++1
s
z (w (wwBB BE
v tr
11 (I- 27, j-i+1
where the last line follows from the fact that RR,, [(I - xx,
P( ((E) (2)--))))))) 2)²E) for any polynomial P. Continuing from the last line, we have
B, 1r (ENN)
1 (vL 12)1
2 "0((w" BE tr
Σ
2
I (I- - 27, E)
i-1
jmit1
[log 1-11
Tuack11 tr E I I--II-
-I-
2y +1 )
[log I-
(²(w*)BB
(I- 2 E Σ)
k=0
2ilee
f=++1
%o tr (AI (I- 2 27 Loess bee 0² (w*) ) B3g
47p Ed lists 2
llog 1-2 11)) bilt 30 (1 4400z) butt for x 1/(7)())) by the j-0
where the last line uses
stepsize definition (2. Since Mitj+1 (XY) & Mi+1 (X))s+1(() for any i and matrices X, Y of
matching dimensions, follows that for any j 7
(5((I - (I 11-2210 2% E) Lote ( 47 E) Lott Σ
M33-2((I (I - 2%0 Σ) Lote) (I 4/0 Σ) Litt (
M4 M (E (2-1)
(I 2%o 2% (r 470 S)
= -PM-((E) PM (M- U3i
Since f(x) (1 (1 2x02) Lorr) 4 /x satisfies f(x) Locr for
[o.1/(87o ], it follows that (I- (1-1-2%0) 2 (I-))(10 trtt has most i = #li [M] Σ
XeLoee 1/83 eigenvalues that are less than Lotr 10. Therefore, we have tr (II- (1--(1 (I (I- 2x0 (I-1I-270 2)
(orr) (( 4) herr Σ)
Σ Ui
(a- (I- 22 2) (a 470 E) Lote Σ
11-1111100
Lose
Σ (i( (())))())))
10
Putting pieces together and taking expectation over (xx) [N]], obtain
E(x))ett B(EaleetM)
|| 1/ 1/2((v - 0r.) 2 (²(w") E(x.)E
B Be 70
Σ
(x((i) (2) ps (i)
Ms
10
i>!
Proof of claim
23
By Eq.
the proof of Theorem 3.1 we have
(I x1 (I + vx(Esxx é
0, -
where
1
I -I (I 7x
Vi(E)
11
(1-
(I
N
NΣ
j=i+1
Let
-SX,
ST
V-
a (Sx, SX E/N)
36

---

E1, E2,s (Sx,, x,,"" Σ)
7: D)v.
Since Bi, te 0, it can be verified that
F2 Ey (et) + (E1,) + E2,x)
2 (w(
N 1 S - (Sx, xT,ST (Sx,,x,,5) -
-
I [Ti-1 E11
(Sx, x ST - _
N
NΣ
2 zw(
N - $ (Sxi xT,ST - 5
1 (I - 27o 2
2
(Sxi, S - -\)
N
NE
Since suP (1 [x B,E, we further have
25x)) 1/x < Late and Ei, [SSx xI," E)1 1
N - - EgE,, LEL],,,, + (E1,) + E2.1) E2.) ] o²(ww²)
470 Ei, (SS,,,x,. - -
N
N
(N (N-1
470bett B3) &
2 (w(
N
N
2 2 (w
5//2
when B2// < 1/3.
D.3 Fluctuation error under the source condition
Lemma D.5 (Fluctuation error under the source condition). Under the notation and assumptions in Theorem 3.1 and suppose that Less & N(1=t)//n for some small constant e [0, For any
s e [0, - I/a), there exists some (s, a) dedeendenn constant e > such that the (multi pass SGD) process satiisfees
[[Fluc] & ey log N. [1+ log² (Lote?))
(Latt))
N2
with probability at least exp( exp(-S((M)))) ((M) over the randomness of S. Consequently; choosing 8 = 1 11(((1111 e/2)) yields
[[[Flu]] $ 7og N [1+ log" ((arrr))
(Iater))
N2
& d 7 log N. [(Toecc)) + (Lees)) 1/a
for some (e, deeepenenntt constant > with probability at least 1 exp( exp(-S((M)).
Moreover, assume in addition that Lost & N/y. Then with probability at least - exp(-S((M)) over the randomness of we have
B[Fluc] > (T
for some a-dependent constant c > 0.
Proof of Lemma D.5 The proof follows from instantiating Lemma D.I and D.4 under the source
condition. We start by establishing concentration bounds some quantities that appear in the bounds in Lemma D. and [D.4
First, note that we have for any s [0, 1 - 1/a), conditioned on S and w*, with probability at least 1 over (x; y.)
max max(x (x] v*)² [E[N]
w H log(N//))
(24a)
37

---

22 N
max
$ (o² + | H log(NN/)),
(24b)
max N
x S
- $ tr( to
() log N/6) + v (1r(-2-2)) log( N/6) x (og(N/6),
(24c)
where Eq.
24a and
24b follow from union bound on concentration inequalities for Gaussian
random variables; Eq. 24c uses Hanson- Hanson-Wright inequality and Lemma E.5
Moreover, we will show that conditioned on S, w* and 0/- x,SSO 0, is zero-mean random Gaussian variable with covariance
[ 9) S, w 0 - -) -T s (TB + Tv) -0 + |w* (H:)
(25)
where
1 + log(1180 (1/()/ + t(6) (Tatt?)² log(1/5)/N)) when M & N/2,
TB =
BB (1 log (1/6)//)) + when M > N/2,
Tv == max [E[N]
(Σ(~)) + -1) 1/2 Σ 11 max èi / [
with BB defined in Lemma B.1 DU defined in Eq. and t(6) = [(oo((16)22)) Thus, we have by union bound that
Sx.STe
(x STSTe 0 0/-
0 T Σ0 log N
max [E
max (E
(T Tv) (0 + w ( log N//
(26)
with probability at least 1- 8 over the randomness of (x,, 9:), conditioned S and w*. Moreover.
we note that [ j j- for j E [M] with probability at least exp(-I((M)) by Lemma E.5
and conditioned on S and w*, we have M4 (2) ~ j_ for j & min (M, N/c) and My Σ S
otherwise with probability at least 1 expl - (Q(()) by Lemma E.8
Proof of the upper bound. Therefore, substituting Eq. 24a
24c and 26 into the expression
in mmax: BA and F, applying Eq. (16) bound D (and tr Σ //)
for some + a), using
part 2 of Lemma D. and taking expectation w.r.t. (x;, y1 2 conditioned on S and w it can be
verified that
E[Fluc S, w w & (o² + [w*1 log N. [1 log" ((aat17)2
(Iratr))
N
Taking expectation w.r.t. w yields the desired result.
Proof of the lower bound. Setting s = 0 in Eq. 24c). we have B& > 1/2 when PLett > 1/3, which happens with probability at least - N for some constant 01 > when 7y & 02f log N for some > O. Moreover, by the concentration properties on μ,,(E) {Σ) and (E)(E) in the previous discussion, the assumptions on 7 and a union bound, conditioned on such that ( (E) j for j [M] (which happens with probability at least - - CRMM)), we have with probability at least 1/2 over the randomness of (x,, M1 that
Mg Σ Ze for j & min(MM,N/a and
i (Leer?) Va, Be > 1/2, 2o 7
Thus, when (Leert) 1/a < M/ē < min M, N/c} for some ē, c > 0 sufficiently large, we have by Lemma that
BeYoLese
E Fluc]
E ((x))
Σ) ( (x(E)
10
'More specifically, we apply part of Lemma where conditions on Σ specified in Lemma E.8 hold, and apply part of Lemma D.1 for some a a otherwise.
D.1 the event with probability at least - eexp(-((N))
38

---

min(M,
2 Leee?? Σ
1 20
i-1+1
2 Lett?
- 2a z ((Lerr?) Va-1
with probability at least - ((M) over the randomness of S.
Proof of claim
25
Note that
00
Σv
* + (0
v*) Σ(0 -v)
v²)
E
1 + IV( (SXT
where step follows from the decomposition
0 v$
11
I ---20 (8- (( (Sx ()(-))
1-1
I (I 71 (1-) v* (SX
[=1
as similar to Eq. 4. where (SX (x (1) (-))
= Ejtr Sx,28/ N and
v( 1 n II (I- 7, (11) I- (I -00))
NE
j=i+1
Let w* == E Note that (o can be viewed as a (D) process on (X,, 3i) with
stepsize (N 1)n/N.
Following the proof of Lemma
B.1
[Eq. and 12 it can be verified that, conditioned on S and w
- 7 S
B
d
Zw $
2 + (Tate 7 IZ ZZ (zT Zalar/5) || when M & N/2,
BF
d
BF
Zw
w 112 when M > N/2,
where Z E (NN-))MM has i.i.d iV.. 1/N) entries and
BF3 (1 R:00 Σ
R000
Z
12
+ 1 +
1Z
E
Z 1l2
k:0
1::00
1::00
with k N/2. In addition, we have || log( 1/8)/N) with probability at least 1 - by concentration properties of chi-squared random variables. Therefore, putting pieces together, applying Lemma E.S. Eq. (13 and concentration properties of Gaussian covariance matrices (see e.g., Theorem 6.1 in Wainwright (2019),, we obtain with probability at least ô conditioned on and w*
1 & 1| and IZ
3 (2 +
I (=1
S D0
l (2 + log(1/))/N + t(6). (hatrr)² (2 + log(1/8)/N)3) when M & N/2, (BB (1+ /)) + +1) when M > N/2,
(27)
where t(0) 1 (1og1188) N) and Bg defined in Lemma B.1 with probability at least (1( over the randomness of S.
Adopt the shorthand vs for I- IT (I E) and R, for ((((-)) AI) 112 (x-() AI)
Similarly, following the proof of the upper bound in Lemma C.1 we have (choosing À 1/(Trett7)
[V(E()))sX* 1- (5
39

---

max E
Cr(V, -VV
N
[ E
tr(V +AΣ -SV- AV-1V(-012
R.
N
(6)
(18) R;
max &
DJd
x
max 2 Bu
(28)
N
[E[N]
N
[
where NU is defined in Eq.
17 and
D.J = #
M
Lotr > 1/4] + (Lo
Σ
1550
1:85-1 Lut 10/4
and 25- is the j-th largest eigenvalue of (-1), Here, step (ii) uses Eq. 17 and step (iii) uses the
fact that 25- < Zy for all j E [M] since Σ < Σ
D.4 Proof of Lemma D.2
D.2 follows from similar ideas in the proof of Proposition 1 of Pillaud Vivien et al. (018). We first state a few lemmas that contribute to the proof. These lemmas are modified versions of the lemmas in Pillaud-Vivien et al. (2088) but provide their proofs here for completeness.
The proof of Lemma
Lemma D.6 (Semi-stochastic SGD; Lemma in Pillaud- Vivien al. (2018)). Under the notation and assumptions Lemma 12.2 consider any stochastic process fút (I
- + " E. with jAo = 0, [L] and (E:) such that I8 [.] 0 and ELE,E/ = o2 En. Then for any u [0, 11. we have
E E < c 3o tr( (Leerro) 1/a-
for any a 1 and some a-dependent constant constant é', 1 such that when Hy (En) ~ j for j & min[M, N/2j, we have
Moreover, there exists some a-dependent
E EL F 1 & c' 7o (Lorr 1/a-u
for any E [O, 1].
See the proof of Lemma D.6 Section 1.4.1
Following the ideas in (Pillaud- Vivien et al.) 2018 Aguech et al.) 2000). we introduce a sequence of stochastic processes (p², T that connects the SGD process in (19 to the semi-stochastic SGD in Lemma D.6 Namely, for > 0, we define
μ (I - no Ev E + $/ P 0, te [4].
(29)
where 4 : & and t == (Ev v.v. MM for k 2 1. It can be verified that
[4 > p (-nr (M--1 Σ pl-) + Yo ghtt.
1=0
Lemma D.7 (Bounds the covariance; Lemma 2 in Pillaud- Vivien et al.
2018)). Under the notation
and assumptions in Lemma D.2 and its proof. for any k >> O, we have
B k o2
B2tk Σ, and El p = 0e k+
k+1 B2k I.
See the proof of Lemma D.7 in Section D.4.2
Lemma D.8 (SGD recursion: Lemma 3 in Pillaud-Viin Vivien et al. (018)). Under the notation and
assumptions in Lemma D.2 consider any stochastie process fù, (I "u.u, P % E., with
Po 0, = [T.] and (=))= such that [ and E( 1 E.. Then
2 f 1 & 20 B2 tr (EEE)) Lese-
for any E [0.
40

---

See the proof of Lemma D.8 in Section D.4.3
With these lemmas hand,
ready prove Lemma D.2
Performing decomposition
as the proof of Proposition in Pillaud- Vivien et al. (2018) and using Lemma D.6 on f4; for i E [0, k] and D.8 Mr. > Mi, we find
E M /2/
( 2 (pL Σ 1
x
Σ
(o B 7a tr
|
Laot 1/- + 2 k+1 B n2k+2+2u 20t (r((E)) (att))
< (oe 7o tr プリ ( //a
(1o BB) + (ažno
k+3 B2k+2+24 tr Eu Loss)
$ 2( 7o tr E
///1 ) (Lattr 70) 1/a + (o
k+3 + tr E L
where the last inequality follows as 7o B2 1/4 by the assumption in Lemma D.2 Finally, letting
k 00 and noting that o2no+ k+3 B2k+2+22 tr( T kn 0, obtain the desired result. The
second part of Lemma D.2 follows from similar arguments and therefore we omit the proof.
D.4.1 Proof of Lemma D.6
By definition T., we have
Fr.
?
(I
76
E.)
(-t+1
Thus,
[[[] 2 1
L I (I-
B 23 Yt'
73
Σ r tr[B I
2
imt+1
6-t+1
7t tr(
x ExE)" 122 2
[log
I (I Mruck+ +1 Ev )bbee
[log LJ-1
Mo tr Eltu
II j-k+1
(I
Meert Ex) )
2 Ex (Noorkt Ex)
[lng 2
Muskk+1 tr(E (I (I Meeck (2bett)) ) (k++ )xbeb
+ tn((
70
(I- L L)2Ler)))
(30)
T.
where the first inequality uses [E[ 1 o Ep.
Part 1 of Lemma D.6
Comtinuing the calculation in Eq. (30). have
E
[lg
02
kerrkt1
(I (I Lovek Ex)
+ 70 E,
(I (I 7o Ev/ / L)3bett)
(2 + Lu
L
k=0
blog r.| -2
1-u
$ 02
Taak41
tr( tr((TLank+1Lnn Eny 1/a) + 7o
L tr(()oZn))
Latt"
"
41

---

22 1- -.5%% tr(E), tr(E)//)) L 1/a-u
Letr
- og 70 tr( /1/ (Less 1/-a
02
where the first inequality uses supre(0.1/701 x² (1 - 7 2Lot: & 1/ Too for any u E [0, 1]. the second inequality follows from 1 - (1 - mmx) 2 & (2 ( 1/2 for any a 1 and [0. 1/70] by Bernoulli's ss inequality, and the last inequality follows from the stepsize definition (2). This gives the first part of Lemma D.6
Part 2 of Lemma D.6
Similarly, continuing the calculation in Eq. 30 and noting that
supre(0.1/-1 [1 (1 yz
2 1/2 & LeyLett, we obtain
Blog L1-2 Σ k-O
2Tatt Moack11 E,ta. (I (k++((+ E2) 2hat + 2 Σ
B[ Σ. pr
[3] $
o
tr
L
(31)
Denote the eigenvalues of En by Ri 3 2e .... > WN (let 23 0 for j > M). Choose t (I/ When M < N N/2, we have (En) ~ j for j & . and otherwise O. When
M > N/ē, we have i & N/2, R5 マ j for j & f and otherwise X; E ja by monotonicity of
Zy. In both cases, we have 2, j- (or 23 0) for & and 2, s for
Since f(x) > f(0) for any x E [0, 1/5] and f(z) = x t11
2 for any u [0. 1]. to obtain an upper bound on tr tr(_ttu. (I /2) 2) we can w.l.o.g. assume R3 ~ j for j &
and Nn $ j for > Under this assumption, for any 7 [0, 1/( (4)1)}.
tr tr( + (I - 2)2ker)
N
+u (1 - 31>yy /
/=1
++ (I - (I- 2)
2 +
Σ
Nt (I- (
j>b
k=
jElc/2+t1,
[log|++1
2ha
(1((++)
Σ
E
21 (1
22hrs
2L.rr
k=0
JE(,/2++1,122
$ %1 11(tta Σ (1/24) 1((1t)a
e-2ta
2ta
$ 1 1 (1 +
Σ
(((++))aa11 2200
$ 111_00+ = (L --
(32)
and 20 (r(EEtu)/11 $ 72/ Tiott- Substituting these into Eq. (1 yields
log L1-2
B Σ ur
Σ
Lotr (Lorr 1) + 70/ Lost
k=0
(Tote Va--u
c 70
D.4.2 Proof of Lemma D.7
We prove this lemma by induction. When ts = O, we have B[EPE!T] = E[EiE, = oe and
7/
(I-11 (I- B[E,,]
11 (I Ew)
-=1+1
j=i+1
1 oz 70
11 j-i+1
(I 21- E, < oe
I
11 (I- & oo
Now, assume the lemma holds for some k > 0, we show that it also holds for l + 1. For E ck+1, we have
+1
ck+1T
s E(E, T KT (E, px4T))
o *+1 B E[ p.N, }3]
42

---

3 o
21 Be
B[u,, mine = v0
++1 B2(ktt), Ev.
For Pt m we have
Blp
p
IT
(I - 73 Ex B|E
++ c,
+ 11 (I- ( j-i+1
IT
j-
2 o h+
2+ 12(k+1)
11
(I- (I- E 1 oz k+ B2 I.
7t-
j-i=1
This completes the induction.
D.4.3 Proof of Lemma D
By definition of fas, we have
L
E| 1 PL 12]
(I - (0,, 2
Yt-
I (I (I- (wun))
tr
Σ>
(I
(=1+1
1=1+1
L
L
|| (I mud )2u
11 (I- mum))) i=++1
Ir
i=++1
tr
Ex)
E &
2 B 77 (r(Ew) Lett,
where the last incquality follows since Σ < E p. nuu x BEEn and Σi= r2 & 2L
D.5 Proof of Lemma D.3
Let A (+i) == 0: - For any i [N]. t E [L], we have
(x] S 0.)² E 2(x ' 0 0)2 + 2(x S A
2(x, S
e
22 +
2|x S - -14 E
max (e(T))
TT 0
max iE[N]
X
S
max [E(
A (1) P.
It remains to bound max
f
1...
Adopt the shorthand notation af d(-))
y/ +
xJ S [ and recell 4max = max [L lak process and the (LOO-GD) process, we
(1)
By taking the difference between the
(G
ha (-i)
A (1=))=)))
na: N
Sx,
II (1 23 Sx.
N
j-++1
Therefore, for x~ 1/(Tatt7);
| B. = -I([x]T V VVV
= =tr(x² S V E'
E + 1 + XIK -12 + 11 (xx)
x²
$ sup
tr(x S V vr E Sx,
230 +
$ - 11- || + XI) 1/2 1Σ + AI) 12 tr(x. S S VV. + Sx)))
Note that
VI, + XIV,,, = V $ + XIJV max:
43

---

where
IT i= (I 7:21)
V
m00x
I (1 7; jmi+1
max
N
mmax
NE
Adopt the shorthand notation V, I-1 -I (I % E). Choosing X = 1/(Lor)?) in the last display and taking the supremum over / E [L], E [M]. we obtain
| + (1)-1/2(E 12
tr(x
S V-VV, + XIIV,E-'Sxx
max [e]
(Lott
N
Σ + AI) 1/1112(2)) + 12
Sx: 1 VE-IV AI)V
max ic[N]
(Lott7)'*
N2
Moreover, we have
Vー' + ADV. & IVS | + A. Vvel? (
Lott",
where step (i) follows from ||V < and supre[u,1//1 (1 -i- (1 - 7xx) z Lerry by the stepsize
definition Combining the last two displays, we find
Sx, 2 ||( XI) (122 + 22 (Larr))2
max
| |
a
max [[
de [E]
N2
This completes the proof.
44

---

E
Auxiliary lemmas
In this section, we provide some auxiliary lemmas that used in the proofs.
E.1 General concentration bounds
Lemma E.1. Let VI, V2....... ..... VN be i.i.d. samples from N(0, Σ) for some E E RRP,, Let E - /
/N. Assume that 2 k.l2)
& N/. Then with probability at least 1 - e--(N
p((3)
II (1p) -12))11- 2 E XI,) 1 + XI,)) 3.
Moreover, the expectation E [ + (I,))
1/2 (
< 100 +
for some
constant c. 0.
Proof of Lemma E. algebra, we have
Adopt the shorthand notation Σ, Σ+ AIp E사 = - AIp By some basic
1 (1,) XI
1/ < 1 -1/2 + ( 1/2 =
1 - -
=I(1,p - 1 - وンدز 1/2) 1|22
(33)
Let == - 1/2 Then we have |B1|2 & 1 and tr BB = >
(2)+ & N/4 by assump-
(:
tion. Therefore, by Theorem 4 and 5 in Koltchinkki and Lounici (017
(E- 1/2 & B max {V
tr(BB
tr(
t +
|BI
N
N
N
BBB)
t
t
+C
N
N
N
with probability at least 1 - - for any [1, MJ. Choosing t N/c for some sufficiently
large constant d' > 0 yields ( Σ)
& 2/3 with probability at least - e CNN()
Combining this with Eq. (33) yields the first part of Lemma E.
To establish the bound in expectation, we first use Eq. 33 to obtain an always-valid upper bound
A + |0|
IC + 11,) *
&
Mmin (Ip Σx
ΣΣ
1/2)
A
Combining this with the first part of Lemma E.1
we obtain
exp( -pp(-NN).
El( AI,) 1/2 + XI
1/2 < 100 +
||
X²
for some constant e > 0.
In the next three lemmas, we let (Ae) denote the cigenvalues of H in non-increasing order.
Lemma E.2 (Lemma G.1 in Lin et al. (2024)). Let S E RMddd xd be random sketching matrix with i.i.d. entries Si NO M Then there exists some absolute constant e such that for any
M > 1 and 0 & le z M, with probability at least 1 e -e- -D(k)) we have
for every j & M, Zz - (2++ Eish do ) &c <<c[v
-(>,
k MM <11 ARt1 + 1
Eisk X2
M
M
Consequently, ifk & M/2, then
for every M, }5 -(>s Eisede)
< {(2,
Eisidi de
[2++
+ c1dttt
M
M
where = c 2c
5d can be +00.
45

---

Lemma E.3 (Tail concentration; Lemma G.2 in Lin et al. (022)) and Lemma 26 in Bartlett et al. 2020 ) Let S RM æd be random sketching matrix with i..dd entries S, ~V(0, 1/M). ) For any
U, with probability at least 1 ô, we have
Ske Hivoo Sk:ac
Eisk A M
IM
x M
1
((xxx)x
AR+1 (Xet1
M + log 2)
Σ E>nk
x
M + log 2))
In particular, with probability at least - e -1(M)), we have
Eish di
Eish X?
Skece Ha ST.00
IM E ARti + V
M
M
Furthermore, the minimum eigenvalue of Skson HR Skoo0 satisfies
Pmia (Sk:0 H HA:00 Skioe) 2 AR+2M
with probability at least 1 - e
Lemma E.4 (Head concentration; Lemma G.3 in Lin et al. 20244). ) Let S E MR be random
sketching matrix with i.i.d. entries Sij NN 1/M). For any k 1, with probubility at least 1 we have
+ log(1/0)
for every j & k, |es (So:k Ho: Xu1 2
M
In particular, with probability at least - e0((k)
K V
for every j & k, |os (ookHHok X31 $
M ^j-
E.2 Concentration bounds under power-law spectrum
Lemma E.5 (Eigenvalues of SHST under power-law spectrum: Lemma G.4 in Lin et al. (2024)).
Let Assumption Coldd There exist some a-dependent constants C2 >> C1 such that
cjj a < My(HHS)) & c2j
with probability at least 1- (Q(M),
Lemma E.6 (Ratio of eigenvalues of Sk..e H S ST km under power-law spectrum; Lemma G.5 in Lin et al. 20244). Let Assumption TC hold. There exists some a-dependent constant e >> 0 such that for
any k O, the ratio between the M 22thh and M-th eigenvalues of Stea: H S kson satisfies
(M/2(S S Au. H HA S
1:00
&
Pa (S k0:00 H...S
with probability at least 1 - (Q(s))
Lemma E.7 (Bounds on Approx under the source condition; Lemma C.5 in Lin et al. (2024)). )
Suppose Assumption is force. Then with probability least e (MM) over S.
-1 S Ew [Approx] & M
Here, the hidden constants only depend on (a, b) in Assumption! 7
Lemma E.8 (Eigenvalues of E under power-law spectrum). Suppose Σ SHHS satisfies 21 (Z)
j-a for j E [M]. Then for some a-dependent constants c, C1, > 0, E N 21 Sx,x S satisfies
c1j < {,)( < c2j c2j for all & min(M,N/c), and
My ( c2j for all j (min Nc). Mi][
with probability at least 1 - over the randommess of (x conditioned on S.
46

---

Proof of Lemma E.8 Note that SX //VN _ E where Z RMMx has iid. entries Ziz
(0 1/N) conditioned on S. Thus, My (2) = P (ZEZ for & min M, N). Let (A:) denote the eigenvalues of ZEZ T non-increasing order. Using Lemma F.2 with N/c for some sufficiently large constant and noting that Σi>E 8 x kl-a have
2 G + 82 N
(j + N
M, m for some constants č, i e [2] with probability at least CR(()) Therefore, for all j & min M, / for some sufficiently large constant > have
for every j &
N5 E "ajj
with probability least e (9N) for some constants č3 C4 M,, /C3, min( M, N)J. by monotonicity of the eigenvalues, we have
0.
For j
Y & S (min(M.Naa & è (1([ (minn(M,N/a)) & Es min(M, a & ūsj
for some sufficiently large constant 0g č with probability at least - -Q(N))
47


Reviews:
[{"review_id": "lsaluK7aya", "reviewer": "Reviewer_6mRL", "summary": "The paper analyzes the scaling of test error under SGD on squared loss (regression) for linear models acting on sketched inputs. \nThe paper considers the setting of Gaussian inputs with a power-law spectrum and a specified source condition quantifying the alignment along the target. The main result shows that upon the re-use of data, i.e., under multi-pass SGD, the number of samples can be replaced by the number of iterations in the scaling law (for a sufficient number of samples). The result thus shows that re-using data provably reduces sample complexity over online SGD, or equivalently, leads to improved scaling laws.", "questions": "* Could you provide brief motivations for the introduction of the sketching matrix and the assumption $M<<d$?\n* Lines 151-153 appear unclear without looking into Koltchinskii and Lounici (2017). Could you provide a short, self-contained summary of the source of the condition on the initial step-size?\n* The parameter b is unspecified in the abstract and only defined later in the source condition.\n* What happens when $a<b$?\n* What are the central challenges introduced by the introduction of the sketching matrix while bounding the fluctuation error (lines 274-276)?\n* What motivates the choice of the geometrically-decaying step-size schedule?", "limitations": "The work is primarily theoretical and does not pose direct societal risks. The paper would benefit from a more detailed discussion of the limitations of their model listed under \"weaknesses\".", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "#  Strengths\n- Understanding scaling laws is a timely question of great interest in the community.\n- The paper is well-written with clear statements of the assumptions and theorems. The risk decomposition in (3) and the proof sketch improve the comprehensibility of the results and the proofs.\n- The results are supported by numerical simulations.\n\n# Weaknesses\n\n- The setting is limited and to some extent, appears artificial. In particular, the introduction of \"sketching matrix\" requires further motivation beyond it allowing the introduction of a \"model size\" parameter. Furthermore, for linear models, it is unclear if the sketching dimension \"M\" captures the model \"size\" since the capacity of the model does not grow once the sketching matrix becomes full-rank. The paper further assumes that $M << d$, which precludes the study of overparameterized regimes.\n- The analysis is of limited novelty and largely builds upon existing works, in particular the work of Pillaud-Vivien et al. 2018.\n- (minor) missing related work. Although for different reasons, another recent line of work also demonstrates improved sample complexity (and consequently, improved scaling laws by data reuse) in the feature learning regime for two-layer neural networks: \n\n  Dandi, Y., Troiani, E., Arnaboldi, L., Pesce, L., Zdeborova, L., &; Krzakala, F. The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents. In Forty-first International Conference on Machine Learning.\n\n  Lee, J. D., Oko, K., Suzuki, T., &amp; Wu, D. (2024). Neural network learns low-dimensional polynomials with sgd near the information-theoretic limit. Advances in Neural Information Processing Systems, 37, 58716-58756.\n\n  Arnaboldi, L., Dandi, Y., Krzakala, F., Pesce, L., &amp; Stephan, L. (2024). Repetita iuvant: Data repetition allows sgd to learn high-dimensional multi-index functions. arXiv preprint arXiv:2405.15459.", "was_revised": true, "final_justification": "The paper’s contributions are valuable with minor concerns regarding novelty and the scope of the setting.", "rebuttal": "We are grateful to Reviewer 6mRL for their thorough examination of our work and for their helpful comments. We hope to address all questions below.\n\n---\n> W1. The setting is limited and to some extent, appears artificial. In particular, the introduction of \"sketching matrix\" requires further motivation beyond it allowing the introduction of a \"model size\" parameter. Furthermore, for linear models, it is unclear if the sketching dimension \"M\" captures the model \"size\" since the capacity of the model does not grow once the sketching matrix becomes full-rank. The paper further assumes that $M\\ll d$ , which precludes the study of overparameterized regimes.\n\nA1.\nThe random sketching is introduced in our setting to control the dimension $M$ (or model size) of the linear models. We believe it is a basic and natural approach to introduce linear models with varying dimensions (model complexity) in regression problems. Similar random sketching approaches have been used to control model dimensions in many other works on the theoretical understanding of scaling laws [1,2,3].\n\nWe respectfully disagree with the reviewer's point that “the model size does not grow once the sketching matrix becomes full-rank.” Note that we consider an infinite-dimensional linear regression setting where the dimension $d = \\infty$ (see line 66 and e.g., Assumption 1C). Therefore, increasing the sketching dimension $M$ always increases the model capacity. Our setting does not preclude overparameterized regimes either, since our results hold for any finite sample size $N$ and model size $M$ (e.g., Corollary 3.2), covering both underparameterized regimes ($M \\leq N$) and overparameterized regimes ($M > N$).\n\n---\n> W2. The analysis is of limited novelty and largely builds upon existing works, in particular the work of Pillaud-Vivien et al. 2018.\n\nA2. We respectively disagree that our analysis has limited novelty. \nFor multi-pass SGD, we generalize the results of Pillaud-Vivien et al. (2018) [4] in two key aspects. \nFirst, the upper bound on the risk of multi-pass SGD in Theorem 1 of [4] is restricted to the regime $\\mu a \\leq b \\leq a$ for some $\\mu \\in (0,1]$. (It can be verified that our parameters $(a, b)$ equal  $(\\alpha, 2\\alpha r + 1)$ in  their work, and note that choosing $ \\mu = 0 $ in their Assumption A3 leads to $\\kappa = \\infty $, making the bound vacuous.) In contrast, our upper bounds in Corollaries 3.3 and 3.4 apply to a strictly broader regime $ a> b-1 $.\nSecond, [4] provides no lower bounds for the risk of multi-pass SGD. In contrast, we establish matching lower bounds in the regime $a>b-1 $, verifying the tightness of our upper bounds. We believe these generalizations are not possible without introducing technical innovations.  Note: the condition $b > a$ in lines 219–221 is a typo and should be revised to $b > a > b - 1$. Similarly, lines 129 and 169 should include the condition $a > b - 1$.\n\nMore specifically, for the fluctuation error, we follow the standard practice as in [4] and the early work by Aguech et al., 2000 [6] to express the difference between the multi-pass SGD and GD trajectories, $\\mathbf{v}_t -\\boldsymbol{\\theta}_t$ as a stochastic process (Eq. 17). We then bound the fluctuation error $\\mathbb{E}[\\\\|\\mathbf{\\Sigma}^{1/2}(\\mathbf{v}\\_L - \\boldsymbol{\\theta}_L)\\\\|^2]$ through controlling the accumulated error of the stochastic process using Lemma D.2 and Lemma D.3, which involves a novel leave-one-out argument to control the model parameters.\n Note that our Lemma D.2 also generalizes the corresponding results in [4], as the analysis in [4] does not apply when $a=b$ for infinite-dimensional problems. In addition, we derive a novel lower bound on the fluctuation error that matches the upper bound up to logarithmic factors in certain regimes (Lemma D.4 and D.5).\n\n---\n> W3. (minor) missing related work. Although for different reasons, another recent line of work also demonstrates improved sample complexity (and consequently, improved scaling laws by data reuse) in the feature learning regime for two-layer neural networks…\n\nA3. We thank the reviewer for pointing out the related works on improved sample convexity in two-layer neural networks via data reuse. We agree that data reuse can indeed improve sample complexity in many other regimes. However,  a key distinction in our work is the use of random sketching, which introduces additional technical challenges. We will discuss these works and their connections to our results in the paper. \n\n---\n> Q1. Could you provide brief motivations for the introduction of the sketching matrix and the assumption $M\\ll d$?\n\nA4. As explained in A1, we believe random sketching is a basic and natural approach to allow us to analyze a sequence of linear models with varying dimensions (model complexity) in regression problems [1,2,3]. The assumption $d=\\infty$ is made to mimic the real-world scenario where the true data distribution is highly complicated (e.g., in text data) and no model with a finite size $M$ can capture all information about the data.\n\n---\n\n> Q2. Lines 151-153 appear unclear without looking into Koltchinskii and Lounici (2017). Could you provide a short, self-contained summary of the source of the condition on the initial step-size?\n\nA5. Since gradient descent is known to converge when the learning rate $\\gamma \\leq 1/L$ for convex objectives that are $L$-smooth, it suffices in our linear regression setting to choose $\\gamma \\leq 1/L = 1/\\|\\mathbf{S}\\mathbf{X}^\\top\\mathbf{X}\\mathbf{S}^\\top/N\\|_2 \\asymp 1$. The final equivalence follows from concentration properties of Gaussian covariance matrices (see, e.g., Koltchinskii and Lounici, 2017).\n\n---\n> Q3. The parameter $b$ is unspecified in the abstract and only defined later in the source condition.\n\nA6. The parameter $b$ is introduced in the form of $b-a$ in the abstract. We will clarify this in the revision.\n\n---\n\n> Q4. What happens when $a<b$?\n\nA7. When $a<b<a+1$, as shown in Corollary 3.4 and the subsequent discussion, the optimal rate in $N$ is obtained when using the data once (i.e., $L_{\\mathsf{eff}}=N$) and the learning rate $\\gamma = L_{\\mathsf{eff}}^{a/b-1}$. In this case, we are able to obtain the same rate $\\widetilde{O}(N^{\\frac{1-b}{b}})$ as in [3] for one-pass SGD. The case $b\\geq a+1$ remains unclear to us and is left for future investigation.\n\n---\n> Q5. What are the central challenges introduced by the introduction of the sketching matrix while bounding the fluctuation error (lines 274-276)?\n\nA8. Sketching introduces additional difficulties when translating the general bounds on the fluctuation error to the setting where the source condition holds (Lemma D.5), as it requires precise characterization of the spectrum of the sketched covariance $\\mathbf{S}\\mathbf{H}\\mathbf{S}^\\top$ to control the terms in the general bound (line 750). We will further clarify this in the revision.\n\n\n\n---\n> Q6. What motivates the choice of the geometrically-decaying step-size schedule?\n\nA9. As discussed in our work (lines 82-85), our analysis applies to other stepsize schedules (such as polynomial decay) as well, but we focus on geometric decay since it is known to yield near minimax optimal excess test error for the last iterate of SGD in the finite-dimensional regime [5].\n\n---\n\n[1]. Bordelon, Blake, Alexander Atanasov, and Cengiz Pehlevan. \"A dynamical model of neural scaling laws.\" arXiv preprint arXiv:2402.01092 (2024)\n\n[2]. Paquette, Elliot, et al. \"4+ 3 phases of compute-optimal neural scaling laws.\" Advances in Neural Information Processing Systems 37 (2024): 16459-16537.\n\n[3]. Lin, Licong, et al. \"Scaling laws in linear regression: Compute, parameters, and data.\" Advances in Neural Information Processing Systems 37 (2024): 60556-60606.\n\n[4]. Pillaud-Vivien, Loucas, 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).\n\n[5]. Ge, Rong, et al. \"The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares.\" Advances in neural information processing systems32 (2019).\n\n[6]. R. Aguech, E. Moulines, and P. Priouret. On a perturbation approach for the analysis of stochastic tracking algorithms. SIAM J. Control and Optimization, 39(3):872–899, 2000."}, {"review_id": "Mjr715fhie", "reviewer": "Reviewer_Y8gi", "summary": "PAPER SUMMARY:\nThis paper provides a theoretical analysis of the effect of multiple SGD passes on scaling laws for linear regression.\n\nNeural scaling laws successfully predict test accuracy as a function of model and data size. Empirically, they proved successful and in the past few years several theoretical explantations of this phenomenon have been proposed.\nRecently, the theoretical work of Lin et al., (2024) characterized scaling laws of one-pass SGD for linear regression.\nEmpirically,  Muennighoff et al. (2023) showed that scaling laws hold for multi-pass SGD as if new data was used, granted that the number of passes is small.\n\nThis work explains the latter phenomenon by refining the analysis of Lin et al., (2024) to include multiple passes. In particular, this work retrieves the bounds of Lin et al., (2024) for one pass, and shows that multiple passes behave as if fresh data was used, as long as the number of passes is small enough.\n\nAlong with standard assumption in the analysis of GD for linear regression, this work's analysis assumes that the data covariance's and parameter's prior eigenspaces are aligned and both spectra follow a power law, as in Lin et al., (2024).", "questions": "No.", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Despite not being an expert in this field, I believe that this work makes progress towards explaining neural scaling laws.\nIndeed, this work explains an important phenomenon already observed empirically, extending and strengthening the illuminating result from Lin et al., (2024).", "was_revised": true, "final_justification": "I confirm my evaluation and recommend acceptance.", "rebuttal": "We thank reviewer Y8gi for their positive feedback on our work. We are glad that the reviewer found our work to make progress towards understanding neural scaling laws and to help explain empirical observations such as those in Muennighoff et al. (2023)."}, {"review_id": "fHUzkYEb6A", "reviewer": "Reviewer_inkZ", "summary": "The paper derives test error bounds when training an M-dimensional linear model on N samples with sketched features using multi-pass SGD of $\\Theta(M^{1-b}+L^{(1-b)/a})$ for $L$ iterations, under the standard assumption on data covariance having a power-law spectrum of degree $a$, and the true parameter having a prior with an aligned power-law spectrum of degree $b-a$. This bound holds for $L\\leq N^{a/b}$ and improves upon the prior result of $\\Theta(M^{1-b}+N^{(1-b)/a})$, for one-pass SGD ($N<L$).", "questions": "Some stylistic suggestions to further improve readability:\n\n- The notation paragraph can be moved to Section 2.\n- In Corollary 3.3, the part after ‘In contrast’ should be part of the text and not the result statement, since it only discusses a result from prior work.\n- In Fig. 1, the last part in the caption (values of M and N for the subfigures) can be included in the respective subcaptions.\n\nIn Section 5, the proof overview can be improved by including some more details. The headings in line 258 and 259 seem unnecessary and this part can be made more concise. In the paragraph discussing the main technical difficulty, currently, the details are helpful to contrast the technique with prior work, but some of the statements, such as the one about Lemma D.3, and the one about a ‘novel lower bound’, are not very informative. It would be helpful to include some mathematical expressions for these to make the proof overview easier to follow.", "limitations": "The paper does not have a limitations section. The authors can include a paragraph to discuss some limitations of the work.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This work makes an interesting and important contribution to the recent line of work on theory of scaling laws in simple settings. In particular, prior work considers one-pass SGD while this work considers multi-pass SGD, and shows that data reuse can be helpful to some extent in improving test performance.\n\nThe paper is very well-written overall. As someone who has not read other papers on provable scaling laws for simple settings, the paper contains sufficient background information, the authors thoroughly and clearly contrast their contributions, and (parts of) the proof technique with other related works, which was helpful, and discuss well the implications of their result.", "was_revised": true, "final_justification": "I maintain my recommendation to accept the paper based on the aforementioned strengths.", "rebuttal": "We  are grateful to Reviewer inkZ for their careful reading of our work and valuable feedback. Please find our responses to the comments below.\n\n---\n\n> Q1. Some stylistic suggestions to further improve readability:\n>* The notation paragraph can be moved to Section 2.\n>* In Corollary 3.3, the part after ‘In contrast’ should be part of the text and not the result statement, since it only discusses a result from prior work.\n>* In Fig. 1, the last part in the caption (values of M and N for the subfigures) can be included in the respective subcaptions.\n\n A1. We sincerely appreciate your stylistic suggestions and will revise our paper accordingly.\n\n---\n> Q2. \nIn Section 5, the proof overview can be improved by including some more details. The headings in line 258 and 259 seem unnecessary and this part can be made more concise. In the paragraph discussing the main technical difficulty, currently, the details are helpful to contrast the technique with prior work, but some of the statements, such as the one about Lemma D.3, and the one about a ‘novel lower bound’, are not very informative. It would be helpful to include some mathematical expressions for these to make the proof overview easier to follow.\n\n A2. Thanks for the suggestions! We will provide a more detailed proof overview in Section 5.\n\n---\n> Q3.\nThe paper does not have a limitations section. The authors can include a paragraph to discuss some limitations of the work.\n\nA3. We will expand our discussion of limitations in the conclusion section. One limitation of the paper is the assumption that the eigenvectors of the prior and data distributions are aligned (implied by Assumption 1D). While this assumption cannot be fully removed without affecting the error rate, it would be interesting to investigate what alternative rates  are achieved when the eigenvectors are not aligned. Another limitation is that our results are currently restricted to linear models; extending them to nonlinear settings such as logistic regression or two-layer neural networks remains an open question."}, {"review_id": "9ThB9HbEpy", "reviewer": "Reviewer_b6Gz", "summary": "The paper studies mulpi-pass SGD applied to linear regression. Under power-law spectrum assumptions of the features and the true model parameter, the authors prove scaling laws of the different components of the test error. The main contribution is extending the previous analysis to account for data reuse.", "questions": "1. Could you provide a high-level overview of how the fluctuation error is bounded?\n2. Would the analysis/results extend to SGD with l2 regularization?", "limitations": "yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "- Quality: the submission appears technically sound. The theoretical results are accompanied by experiments. However, some proofs are a bit hard to follow and I am not able to verify their correctness.\n- Clarity: the main paper is pretty clearly written. However, the proofs in the appendix sometimes are not that clear and detailed. E.g., from line 846-line 849, too many things are done at the same time. Also, nested lemmas (e.g., lemma D.2 and D.3 are stated in the proof of lemma D.1) makes the flow hard to follow. The clarity can be improved by providing a better high-level proof sketch of bounding the fluctuation error. (If I understand correctly, this is the key difference from the results in [1]).\n- Significance: The submission advances our understanding of scaling laws under data-reuse. While this is somewhat significant, the main limitation is that the analysis is limited to linear models. In addition, the Gaussian design matrix is a pretty strong assumption.\n- Originality: The submission extends previous results on scaling laws to multi-pass SGD. The proofs follow closely along the lines of [0].\n\nTypos:\n- Second line of equation after 521, missing a S?\n\n\n[0] Loucas Pillaud-Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes\n[1] Licong Lin, Jingfeng Wu, Sham M Kakade, Peter L Bartlett, and Jason D Lee. Scaling laws in linear regression: Compute, parameters, and data. arXiv preprint arXiv:2406.08466, 2024", "was_revised": true, "final_justification": "My previous concerns about clarity, originality, and significance are adequately addressed by the rebuttal. While this work focuses on the linear case, the upper bound can be extended to sub-Gaussian design. In addition, the lower bound is a novel contribution. I still believe the limitation to the linear case restricts the impact of works like this. I am maintaining my low confidence score since I am not super familiar with related works. Also, I did not verify the correctness of the proofs, but the agreement with experiments is a promising sign.", "rebuttal": "We  appreciate Reviewer b6Gz for their thorough review and constructive feedback on our work. Below, we hope to answer all questions raised in the review.\n\n---\n> W1 and Q1. Clarity: the main paper is pretty clearly written. However, the proofs in the appendix sometimes are not that clear and detailed. E.g., from line 846-line 849, too many things are done at the same time. Also, nested lemmas (e.g., lemma D.2 and D.3 are stated in the proof of lemma D.1) makes the flow hard to follow. The clarity can be improved by providing a better high-level proof sketch of bounding the fluctuation error. (If I understand correctly, this is the key difference from the results in [1]).\n\nA1. We thank the reviewer for the constructive comments on improving the clarity of our proof. We will include additional details and provide a high-level proof sketch for bounding the fluctuation error in the paper. For completeness, we present the sketch here.\n\nTo bound the fluctuation error, we express the difference between the multi-pass SGD and GD trajectories, $\\mathbf{v}_t - \\boldsymbol{\\theta}_t$, as a stochastic process (Eq. 17) that fits into the framework of Lemma D.2, which provides a bound on the fluctuation error $\\mathbb{E}[\\\\|\\mathbf{\\Sigma}^{1/2}(\\mathbf{v}_t - \\boldsymbol{\\theta}_t)\\\\|^2]$ under certain conditions, up to a mismatch between $\\widehat{\\mathbf{\\Sigma}}$ and $\\mathbf{\\Sigma}$. We verify that the required conditions hold with appropriate choices of parameters (Eq. 19), which are further bounded using a leave-one-out argument (Lemma D.3). Applying Lemma D.2 with these parameters and a covariance replacement trick (line 776) yields the bounds stated in Lemma D.1.\n\nMoreover, we emphasize that, in addition to bounding the fluctuation error, generalizing the one-pass SGD results from [1] to GD in our setting introduces additional challenges. Please see our response to your W3 below for further discussion.\n\n---\n\n> W2. Significance: The submission advances our understanding of scaling laws under data-reuse. While this is somewhat significant, the main limitation is that the analysis is limited to linear models. In addition, the Gaussian design matrix is a pretty strong assumption.\n\nA2.  Extending the results to nonlinear settings such as logistic regression or two-layer neural networks would be an interesting direction for future work. We will comment on this in the paper.\n That said, we believe our contribution, deriving finite-sample matching upper and lower bounds for multi-pass SGD in sketched linear models, has made substantial contributions to the theoretical understanding of scaling laws.\n\n\nIn fact, the Gaussian design is not necessary for all the upper bounds in Section 3. \n Namely, it can be shown that the Gaussian design assumption (Assumption 1A) can be relaxed to the following: $\\mathbf{x}= \\mathbf{H}^{1/2}\\mathbf{\\widetilde x}$, where $\\mathbb{E}[\\mathbf{\\widetilde x}\\mathbf{\\widetilde x}^\\top]=\\mathbf{I}$, and the vector $\\mathbf{\\widetilde x}$ is symmetric and  1-sub-Gaussian, i.e.,  $\\mathbf{\\widetilde x}\\overset{d}{=}-\\mathbf{\\widetilde x}$ and $\\mathbb{E}[e^{\\lambda\\langle \\mathbf{v},\\mathbf{\\widetilde x}\\rangle}]\\leq e^{\\lambda^2/2}$ for any unit vector $\\mathbf{v}$. In short, the relaxation can be made since the Gaussian assumption is mainly used to establish certain concentration bounds (e.g., Bernstein’s inequality), which also hold for sub-Gaussian vectors. On the other hand, for the lower bounds, the  Gaussian assumption is still required in order to establish the conditional independence in line 521 and 754.  We are happy to provide a more detailed explanation, should the reviewer have any concerns regarding the relaxation.\n\nIn addition, we run simulations to verify the claim. We generate data $\\mathbf{x}=(x_1,\\ldots,x_d)^\\top$ from the distribution where $x_i$ are independent and $\\mathbb{P}(x_i=1)=\\mathbb{P}(x_i=-1)\\propto i^{a-b}, \\mathbb{P}(x_i=0)=1-2\\mathbb{P}(x_i=1)$ with $a=2,b=1.5$ instead of Gaussian. Under the same setting and choices of hyperparameters as in Figure 1(a), similar to the Gaussian case, we observe that excess test error of one-pass SGD and multi-pass SGD both exhibit power-law scaling in the number of effective steps ($L_{\\mathsf{eff}})$. Moreover, the fitted slopes are both close to the theoretical prediction ($0.34\\approx0.33=(1-b)/b$ for multi-pass SGD and  $0.26\\approx0.25=(1-a)/b$ for one-pass SGD).\n\n> W3. Originality: The submission extends previous results on scaling laws to multi-pass SGD. The proofs follow closely along the lines of [0].\n\nA3. We respectively disagree that our analysis has limited originality. \nFor multi-pass SGD, we extend the results in [0] in two key aspects. \nFirst, the upper bound on the risk of multi-pass SGD in Theorem 1 of [0] is restricted to the regime $\\mu a \\leq b \\leq a$ for some $\\mu \\in (0,1]$. (It can be verified that our parameters $(a, b)$ equal  $(\\alpha, 2\\alpha r + 1)$ in [0], and note that choosing $\\mu = 0$ in their Assumption A3 leads to $\\kappa = \\infty$, making the bound vacuous.) In contrast, our upper bounds in Corollaries 3.3 and 3.4 apply to a strictly broader regime $a>b-1$.\nSecond, [0] provides no lower bounds for the risk of multi-pass SGD. In contrast, we establish matching lower bounds in the regime $a>b-1$, verifying the tightness of our upper bounds. We believe these generalizations are not possible without introducing technical innovations. Note: the condition $b > a$ in lines 219–221 is a typo and should be revised to $b > a > b - 1$. Similarly, lines 129 and 169 should include the condition $a > b - 1$.\n\n\n\nMore specifically, as mentioned in our response to your Q1 above,  for the fluctuation error of multi-pass SGD, we follow the standard practice as in [0] and the early work by Aguech et al., 2000 [2]  to express the difference between the multi-pass SGD and GD trajectories as a stochastic process (Eq. 17). We then bound the fluctuation error through controlling the accumulated error of the stochastic process using Lemma D.2 and Lemma D.3, which involves a novel leave-one-out argument to control the model parameters.\n Note that our Lemma D.2 also generalizes the corresponding results in [0], as the analysis in [0] does not apply when $a=b$ for infinite-dimensional problems. In addition, we derive a novel lower bound on the fluctuation error that matches the upper bound up to logarithmic factors in certain regimes (Lemma D.4 and D.5).\n\n\n---\n\n\n>Q2. Would the analysis/results extend to SGD with l2 regularization?\n\nA4. \nThis is an interesting question. We believe part of our results extend to multi-pass SGD with l2-regularization. We will comment on this as an interesting future direction. On the other hand, we would like to point out that, mult-pass SGD already provides sufficient implicit regularization, in which the achieved excess risk is minimax optimal for $a$ and $b$ such that $a>b>2$, (see [0]). Therefore, adding an l2-regularization might not provide additional benefits.\n\n---\n\n> Other: typos: Second line of equation after 521, missing a S?\n\nThanks for pointing this out! We have fixed it.\n\n---\n\n \n\n\n\n\n\n\n\n\n[0]. Loucas Pillaud-Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes \n\n[1]. Licong Lin, Jingfeng Wu, Sham M Kakade, Peter L Bartlett, and Jason D Lee. Scaling laws in linear regression: Compute, parameters, and data. arXiv preprint arXiv:2406.08466, 2024\n\n[2]. R. Aguech, E. Moulines, and P. Priouret. On a perturbation approach for the analysis of stochastic tracking algorithms. SIAM J. Control and Optimization, 39(3):872–899, 2000."}, {"review_id": "cSPh4ESjNd", "reviewer": "Reviewer_6YBu", "summary": "In this paper, the authors study the behavior of multi-pass SGD on task of linear regression with sketching. They \nassume that the inputs follow the Gaussian distribution $N(0, H)$ with the eigenvalues of $H$ following a power law with \nexponent $a$, the ground truth direction is $w^\\*$, and covariance matrix of the prior on $w^*$ share the eigenvectors \nwith $H$ and the eigenvalues follow a power law with exponent $b$. Under these assumptions, they show that the test \nloss of multi-pass SGD satisfies the scaling law $M^{1-b} + L^{(1-b)/a}$ with $M$ being the sketching dimension and \n$L \\lesssim N^{a/b}$ the number of steps, while the scaling law of single-pass SGD is $M^{1-b} + N^{(1-b)/a}$, where \n$N$ is the number of samples. Namely, multi-pass SGD is provably more sample-efficient than single-pass SGD (in this setting).", "questions": "See the weakness section. In particular, I'd like to know the following. \n* Is it true that in the isotropic prior case, the bounds are essentially the same as the ones in Lin et al. (2024), or I am missing something here?\n* What will happen if, instead of assuming the data distribution and the prior share the same eigenvectors, we only assume \n  they are correlated?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "### Strengths \n\n* This is a well-written paper and is easy to follow. The setting and results are clearly stated and described. \n* The analysis of multi-pass SGD is rather rare in this field, probably due to the additional dependence between iterations \n  introduced by the reuse of samples (most of the existing results about GD or online/single-pass SGD). It is nice to \n  have a result which proves that at least in certain scenarios, the reused samples behave similar to fresh samples and \n  multi-pass SGD can beat one-pass SGD in terms of sample complexity.\n* The authors also prove lower bounds on the errors, showing their bounds are not vacuous, and also verify their claims with \n  experiments. \n\n### Weaknesses\n\nMy main concern with this paper is that its contribution over [1-2] appears to be limited. \n\nWhen the prior of the ground truth is isotropic, we have $a = b$, and in this case, the results (cf. Corollary 3.3) in this \npaper do not give any improvement over the results in [1]. \n\nIn the regime where improvement can be obtained, the authors need to assume that the data distribution and the prior of \nthe ground truth share the same eigenvectors and the eigenvalues of the prior follow another power law, which is a rather \nstrong assumption (especially the first part). Moreover, the benefit of reusing samples in linear regression has been \nstudied in [2] and the results/observations are similar. To be fair, [2] does not analyze the dependence on the model \nsize, but that part is covered in [1].\n\n\n[1] Licong Lin, Jingfeng Wu, Sham M Kakade, Peter L Bartlett, and Jason D Lee. Scaling laws in linear regression: Compute, parameters, and data. 2024\n\n[2] Loucas Pillaud-Vivien, Alessandro Rudi, Francis Bach. Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes. 2018", "was_revised": true, "final_justification": "My original concern was that the contribution of this paper over [1-2] seems to be small, but I was convinced during the rebuttal that this is not the case. In addition, the authors also clarified that certain strong conditions are not needed for some of their results. Therefore, I raised my score from 3 to 4.", "rebuttal": "We appreciate Reviewer 6YBu for their careful review and valuable feedback. We hope to address all questions below.\n\n---\n\n> W1. My main concern with this paper is that its contribution over [1-2] appears to be limited. \n\nA1. We respectively disagree that our analysis has limited novelty. \nFor multi-pass SGD, we generalize the results of Pillaud-Vivien et al. (2018) [2] in two key aspects. \nFirst, the upper bound on the risk of multi-pass SGD in Theorem 1 of [2] is restricted to the regime $\\mu a \\leq b \\leq a$ for some $\\mu \\in (0,1]$. (It can be verified that our parameters $(a, b)$ equal  $(\\alpha, 2\\alpha r + 1)$ in  their work, and note that choosing $\\mu = 0$ in their Assumption A3 leads to $\\kappa = \\infty$, making the bound vacuous.) In contrast, our upper bounds in Corollaries 3.3 and 3.4 apply to a strictly broader regime $a>b-1$.\nSecond, [2] provides no lower bounds for the risk of multi-pass SGD. In contrast, we establish matching lower bounds in the regime $a>b-1$, verifying the tightness of our upper bounds. We believe these generalizations are not possible without introducing technical innovations. Note: the condition $b > a$ in lines 219–221 is a typo and should be revised to $b > a > b - 1$. Similarly, lines 129 and 169 should include the condition $a > b - 1$.\n\n\nCompared to the analysis in [1] for one-pass SGD, the non-commutativity between the empirical covariance and population covariance matrices introduces additional technical challenges, requiring new proof arguments.  For example, unlike for the bias upper bound (lines 267-270), the covariance replacement trick in Lemma 7 of [2] does not apply when establishing the bias lower bound (Lemma B.2). Instead, we derive the bound by showing that a specific function of the empirical covariance commutes with the population covariance in expectation. \n\n---\n\n> Q1. Is it true that in the isotropic prior case, the bounds are essentially the same as the ones in Lin et al. (2024), or I am missing something here?\n\nA2. \nYes, the bounds are the same in the regime where $a = b$. In fact, the rate  $O(N^{(1-a)/a})$ in this case   is minimax optimal for a class of linear regression problems with the same spectral conditions [2], and hence cannot be improved.\n\n\n--- \n\n> Q2. What will happen if, instead of assuming the data distribution and the prior share the same eigenvectors, we only assume they are correlated?\n\nA3. First, we emphasize that our general upper and lower bounds on the bias, variance, and fluctuation (Lemmas B.1, B.2, C.1, D.1, D.4) do not require either the power-law assumption or the alignment between the eigenvectors of the data distribution and the prior. These bounds hold under Gaussian design with an arbitrary data spectrum, as long as certain regularity conditions (Assumption 3) are satisfied. \n\nThe alignment of eigenvectors is assumed only to derive exact rates from the general bounds under the power-law setting. In fact, our main results in Section 3 still hold when the prior covariance $\\mathbf{H}^{\\mathbf{w}} := \\mathbb{E}[\\mathbf{w}^* \\mathbf{w}^{*\\top}]$ is bounded above and below (in Loewner order, up to constant factors) by a matrix $\\widetilde{\\mathbf{H}}^{\\mathbf{w}}$ that has a power-law spectrum and share the same eigenvectors as the data covariance $\\mathbf{H}$ as in Assumption 1D. \n\n--- \n[1]. Lin, Licong, et al. \"Scaling laws in linear regression: Compute, parameters, and data.\" Advances in Neural Information Processing Systems 37 (2024): 60556-60606.\n\n[2]. Pillaud-Vivien, Loucas, 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)."}]

Author rebuttal:

Meta-review: This paper advances the theory of scaling laws in simple settings, in this case sketched linear regression with power law source/capacity type conditions. The technical aspects of the paper appear sound, with new theoretical innovations and effective support from numerical simulations. The authors also provide lower bounds on errors, which give tight estimates.  The work makes an important contribution by extending the theory of scaling laws to multi-pass SGD, which requires new analysis beyond what was done in the one-pass case. It successfully shows the benefits of data reuse in improving test performance in one regime, which was enlarged in earlier work of Pillaud-Vivien et al. in kernel regression.

The paper is clearly written and easy to follow, with clear theorem statements. The comparison with related works was generally found to be complete.

The two closest existing works are those of Lin et al and Pillau-Vivien et al.  In comparison to the work of Pillaud-Vivien et al, which first established the benefits of data-reuse in a similar linear problem, this paper:
* covers a larger range of parameters, including the whole regime in which multipass-SGD is expected to improve over one-pass.  
* incorporates a random sketch matrix, which allows the model to have parameterized capacity at the cost of additional technical difficulty.
* provides instance-dependent upper and lower bounds.

The paper also extends existing work Lin et al, which focused on single-pass SGD, by working with multipass-SGD, in a nearly identical setup.
Decision: Accept (poster)