Risk Bounds of Multi-Pass SGD for Least Squares  in  the Interpolation Regime
Authors: Difan Zou
Jingfeng Wu
Vladimir Braverman
Quanquan Gu
Sham M. Kakade
Venue: NeurIPS 2022 Accept (2022)
Keywords: Stochastic gradient descent
generalization
least square
interpolation

Abstract: Stochastic gradient descent (SGD) has achieved great success due to its superior performance in both optimization and generalization. Most of existing generalization analyses are made for single-pass SGD, which is a less practical variant compared to the commonly-used multi-pass SGD. Besides, theoretical analyses for multi-pass SGD often concern a worst-case instance in a class of problems, which may be pessimistic to explain the superior generalization ability for some particular problem instance. The goal of this paper is to provide an instance-dependent excess risk bound of multi-pass SGD for least squares in the interpolation regime, which is expressed as a function of the iteration number, stepsize, and data covariance. We show that the excess risk of SGD can be exactly decomposed into the excess risk of GD and a positive fluctuation error, suggesting that SGD always performs worse, instance-wisely, than GD, in generalization. On the other hand, we show that although SGD needs more iterations than GD to achieve the same level of excess risk, it saves the number of stochastic gradient evaluations, and therefore is preferable in terms of computational time.

Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime
Difan Zou"
Jingfeng Wu* Johns Hopkins University auujfejhu. edu
Vladimir Braverman
The University of Hong Kong dzou@cs hku. hk
Johns Hopkins University vova@cs, jhu edu edu
Quanquan Gu University of California, Los Angeles qguêcs ucla.edu
Sham M. Kakade
Harvard University
sham@seas harvard. edu
Abstract
Stochastic gradient descent (SGD) has achieved great success due to its superior performance in both optimization and generalization. Most of existing general- ization analyses are made for single-pass SGD, which is a less practical variant compared to the commonly-used multi-pass SGD. Besides, theoretical analyses for multi-pass SGD often concern worst-case instance in class of problems, which may be pessimistic to explain the superior generalization ability for some particular problem instance. The goal of this paper is provide instance dettndeedeeennentt and algorithm- dependent excess risk bound of multi-past SGD for least squares the interpolation regime, which is expressed as function of the iteration number, stepsize, and data covariance. We show that the excess risk of SGD can be exactly decomposed into the excess risk of GD and positive fluctuation error, suggesting that SGD always performs worse, instance-wisele wiselly than GD, in generalization. On the other hand, we show that although SGD needs more iterations than GD achieve the same level of excess risk, it saves the number of stochastic gradient evaluations, and therefore is preferable in terms of computational time.
Introduction
Stochastic gradient descent (SGD) is one of the workhorses in modern machine learning due to its efficiency and scalability training and good ability in generalization to unseen test data. From the optimization perspective, the efficiency of SGD is well understood. For example, to achieve the same level optimization error, SGD saves the number of gradient computations compared to its deterministic counterpart, i.c., batched gradient descent (GD) 7 8), and therefore saves the total amount of running time. However, the generalization ability (e.g., excess risk bounds) of SGD is far less clear, especially from theoretical perspective.
Single-pass SGD, a less practical SGD variant where each training data used only once, has been extensively studied in theory. In particular, series of works establishes excess risk bounds of single-pass SGD for learning general smooth and convex objectives [32 24 26 as well as learning [3 42 (38.. In practice, though, one often runs SGD with multiple passes over the training data and outputs the final iterate, which is referred to as multi-pass SGD (or simply SGD in the rest of this paper when there is confusion). Compared single-pan -asesppsssss SGD that has limited number optimization steps, multi-pass SGD allows the algorithm to perform arbitrary
least squares 3 I0 18 19 27
* Equal Contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

number of optimization steps, which is more powerful in optimizing the empirical risk and thus leads to smaller bias error 22
Despite the extensive application of multi-pass SGD in practice, there are only a few theoretical techniques being developed study the generalization of multi-pass SGD. One is based the uniform stability [12 [6), which is defined as the change of the model outputs under a small change in the training data. However, the stability based generalization bound is a worst-case guarantee, which is relatively crude and does not show difference between GD and SGD (See, e.g., Chen et al. [9] showed GD and SGD have the same stability parameter in the convex smooth setting). On the contrary, one easily observes a generalization difference between SGD and GD even in learning the simplest least square problem (see Figure []. In addition, Lin and Rosasco [22]. Pillaud- -ivien et al. (28). Mücke et al. [25] explored the risk bounds for multi-pass SGD using the operator methods that are originally developed for analyzing single-pass SGD. Their bounds are sharp in the minimax sense for a class of least square problems that satisfy certain source condition (which restricts the norm of the optimal parameter) and capacity condition (or effective dimension, which restricts the spectrum of the data covariance matrix). Still, their bounds are uniform for class of problem instances, and cannot point-wisely adapt to each problem instance (e.g., a least square problem with a particular data covariance matrix). In particular their reults are pessimistic for the benign-overlitting 4 least square instances (see Theorem 4.2 and related discussions).
In this paper. our goal is to establish an algorithm-dependeee dependent and deaelem-depeddent excess risk SGD for least squares. Our focus is the interpolation regime where the training data can be perfectly fitted by linear interpolator (which holds almost surely when the number of parameter d exceeds the number of training data n). We assume the data has a Gaussan tail 4 Our main contributions are summarized as follows:
bound of
We show that for any iteration number and stepsize, the excess risk of SGD can be exactly decomposed into the excess risk of GD (with the same stepsize and iteration number) and the so-called fluctuation error, which is attributed to the accumulative variance of stochastic gradients in all iterations. This suggests that GD (with optimally tuned hyperparameters) always achieves a smaller excess risk than SGD for least square problems.
We further establish problem-depender bounds for the excess risk of GD and the fluctuation error, stated as function of the eigenspectrum of the data covariance, iteration number, training sample size, and stepsize. Compared to the bounds proved in prior works [22 28 25). our bounds allow a wider range of iteration numbers i, and correctly vanishes when + oo the benign overfitting regime [4]. In contrast, the prior results do not allow t + 0O.
We develop a new suite of proof techniques for analyzing the excess risk of multi-pass SGD, The key idea is considering the error in its matrix form and how it is updated based on the tensor operators defined by the second-order and fourth-order moments of the empirical data distribution (i.e., sampling with replacement from the training dataset), rather than the operators used in the single-par pass SGD analysis that are defined based on the population data distribution [88 together with sharp characterization on the properties of the operators.
Based on the excess risk upper bounds for SGD and GD, we make the following complexity comparison between SGD and GD: to achieve the same order of excess risk, while SGD may need more iterations than GD, it can have fewer stochastic gradient evaluations than GD. For example, consider the case that the data covariance matrix has a polynomially decaying spectrum with rate i 8-(++)), where > 0 is an absolute constant. In order to achieve the same order of excess risk, we have the following comparison in terms of iteration complexity and gradient complexity
Iteration Complexity: SGD needs to take Ö maxx(U.5, )) more iterations than GD, with optimally tuned iteration number and stepsize.
Gradient Complexity: SGD needs m0.
less stochastic gradient evaluations than GD.
Notation. For n > O, we use poly (n) to define some positive high-degree polynomial functions of n. For two positive-value functions f(x:) and g(x) we write f(x) & g(x) if f(x) < cg(z)) for some
constant e > O, we write fxx Z g(x) if g(x) S f(x), and f(x z g(x) if both f(x) S g(x) and g(x) S f()) hold, We use Ö(-) to hide some polylogarithmic factors in the standard big-O notation. For two matrices A and B, we denote (A, B) -E., Aij and A B as their Kronecker product.
We define the gradient complexity as the number of required stochastic gradient evaluations to achieve a target excess risk, which is closely related to the total computation time.

---

2
2
n-128
GD large
2
11-28
GD large
SGD small LR
SG0 small LR
SGD large
20
large
Risk
Risk
2-1
2-1
2
2-2
2-3
1024
2048 Steps
3072
4096
1024
2048
3072
4096
Steps
(a) A
log (1 + 10)
(h) X: f-2
Figure 1: Excess risk comparison between SGD and GD with large and small stepsizes. The true parameter w is randomly drawn from (O, I) and the model noise variance o² 1. The problem dimension is d = 256, and we randomly draw n = 128 training data. We consider two data covariance with eigenspectrum A; = 1-1 log " + 10) and X; i-? For SGD, the reported risk is averaged over 100 repeats of the algorithm's randomness. The large stepsize 1l 0.2 and the small stepsize is rj 0.02.
Related Work
Regarding optimization efficiency, the benefit of SGD is well understood 7 For example, for strongly convex losses (can be relaxed with certain growth conditions), GD has less iteration complexity. but SGD enjoys less gradient complexity 7 8. More recently. it is shown that SGD can converge at an exponential rate the interpolating regime 23
Optimization.
|8
23
5
34
35 26).
5 34 35]. therefore SGD can match the iteration complexity of GD. Nevertheless, all the above results are regrading the optimization performance; our focus in this paper to study the generalization performance of SGD (and GD).
[26
Risk Bounds for Multi-Pass SGD. The risk bounds of multi-pas palltt-passssss SGD are also studied from the operator perspective 30 22] 22, 25]. The work by Rosasco and Villa (30) focused on cyclic SGD, i.e., SGD with multiple passes but fixed sequence
the training data. Their results are limited to small stepsizes ( = (1 ((1/))). while ours allow constant stepsize. Similar to Lin and Rosasco et al. (8) Mücke al. 25 we decompose the population risk of SGD iterates into risk term caused by batch GD iterates and a fluctuation eтror term between SGD and GD iterates. But our methods of bounding the fluctuation error are different (see more Section (5). Moreover, our results are based on different assumptions: Lin and Rosasco [22], Hellaud-Viveee et al.
[22. Pillaud-Vivis
28 Mücke al. 255 assumed finiteness on the optimal parameter, and their results only apply to data covariance with a specific type of spectrum (nearly polynomially decaying ones); in contrast, our results assume Gaussian prior on the optimal parameter (which might not admit finite norm), and our results are stated as a function of the entire eigenspectrum of the data covariance, thus cover more general data covariance (including those with polynomially decaying spectrum). Lei et [21) studied risk bounds for multi-pass SGD with general convex loss. When applied to least square problems, their bounds are cruder than ours.
Uniform Stability. Another approach for characterizing the generalization of multi-pass SGD is through uniform stability [6 9 20 6). There are mainly two differences between this and our approach. First, we directly bound the excess risk of SGD; but the uniform stability can only bound the generalization error, there needs an additional triangle inequality to relate excess risk with generalization eтror plus optimization error (plus approximation error) this inequality can easily be loose (consider the algorithmic regularization effects). Secondly, the uniform stability bound is also crude. For example, in the non-strongly convex setting, the uniform stability bound for SGD/GD linearly scales with the total optimization length (i.e., sum of stepsizes), which grows as I
(this is minimaxly unavoidable according to Zhang et al. [41). Bassily et al. (6). Notably, Bassily et al. [6] extended the uniform stability approach to the non-convex and smooth setting. We left such an extension of our method as future work.
[16 9 20 41 6
3 Problem Setup
Let x be feature vector in a Hilbert space H (its dimension is denoted by d, which possibly infinite) and y IR be its response, and assume that they jointly follow unknown population

---

distribution D. In linear regression problems, the population risk of a parameter w is defined by
1 Lp(w) 2 (xxxy)) (x, w) -y)²
and the excess risk is defined by
L- min (o(w) = || - w W where == Ex|xx ],
(3.1)
w
where w = arg minw Lp (p(w) denotes the global minimizer of the population risk. Additionally, we assume that the data covariance matrix H is positive definite. In the unknown, and one is provided with a set of n training samples, S (x,, Ub) ) that are drawn independently random from the population distribution. We also use X = (X1,... xn) and y == (y),... ................................ Me.) to denote the concatenated features and labels, respectively. The linear regression problems aim to find a parameter based on the training set S that affords small excess risk.
following Zou al. 42 43
statistical learning setting, the population distribution
Multi-Pass SGD. We are interested in solving the linear regression problem using multi-pass stochastic gradient descent (SGD with a constant learning rate. The algorithm generates sequence of iterates (We)(21 according the following update rule: the initial iterate is Wp = 0 (which can be assumed without loss of generality): then at each iteration, an example (X . Vs,) is drawn from S uniformly at random, and the iterate is updated by
W (++1 W, 1 x, (x,, We -1.);
where 7) 0 is constant stepsize (i.e., learning rate).
GD. Another popular algorithm is gradient descent (GD). For the clarity of notations, we use (We) to denote the GD iterates, which follow the following updates:
W++1 W.
17
Σ 72
(x; We yi), Wo O,
where 7) >> 0 is constant stepsize.
Definitions and Assumptions. The eigenvalues of the population data covariance H denoted by (A:)221, sorted in non-increasing order. Given the training data (X,y). we define e y Xw" the collection of model noise, A = XX the Gram matrix, and Σ = n X X as the empirical covariance. Then minimum-none norm solution is defined by
= [ T X = X -yy
It is clear that in the interpolation regime, with appropriate stepsizes, both SGD and GD algorithms converge to w [14[]]
The assumptions required by our theorems are summarized in below.
Assumption 3.1 For the linear regression problem:
A The components of H-1/2x are independent and 1-subGaussian.
B The response y generated by y := (="",, x) + &, where w" is the ground truth weight vector and is a noise independent of x. Furthermore, the additive noise satisfies [g]]] = 0, E[g"] S o2.
C The ground truth w" follows Gaussian prior (O, w² I), where w² is constant.
D The minimum norm solution @ linearly interpolates all training data, i.e., y/ = w for i E [n].
Assumptions 3.1 3. and are standard for analyzing overparameterized linear regression problem in A is widely made in the analysis of [T]] [7]. However, Assumption A not standard 18, 42). We conjecture Assumption 3. can be relaxed and leave this as a future work. Moreover, Assumption 3.1 is also widely adopted in analyzing least square problems (see, e.g., Ali al. [2] Dobriban et al. [11, Xu and Hsu (39 ). There also many different conditions being made on the ground truth w in existing works 228 to study the generalization
the benign overfitting regime [4 (33] Note that Assumption
high-dimensional least squares estimations
for analyzing SGD 3 22
28
We focus on SGD with replacement in this paper. Extending our results to SGD without replacement is an important yet challenging future direction (see more discussions in Section

---

of SGD (e.g..
H 1//2 w l2 + oo for r 2 0). However, they are not directly comparable to Finally, Assumption 3. holdd almost surely when d n, i.e. the number of parameter exceeds the number of data.
Assumption B.
In the following, the presented risk bounds will hold (i) with high-probabilityy with respect the randomness of sampling feature vectors X, and (ii) in expectation with respect to the randomness of multi-pass SGD algorithm, the randomness of sampling additive noise and the randomness of the true parameter w as prior. For these purpose, we will use Ex, ESCD, lEw- to refer to taking expectation with respect to the randomness of sampling data (from the training set) at the f-th iteration, the randomness of the entire SGD algorithm (i.e., sampling data at each iteration, i1,..., .,,,... and the prior distribution of w", respectively.
4
Main Results
Our first theorem shows that, under the same stepsize and number of iterates, SGD always generalizes worse than GD.
Theorem 4.1 (Risk decomposition) Suppose that Assumption holds. Then the excess risk of SGD can be decomposed by
ESGD [E(w.)] = E(w,) FluctuattionErrrr((...
Moreover, the fluctuation error is always non-negative.
A Risk Comparison. Theorem 4.1 shows that, in the interpolation regime, SGD affords strictly larger excess risk than GD, given the same hyperparameters (stepsize n and number iterates t). Therefore, despite of possibly higher computational cost, the optimally tuned GD dominates the optimally tuned SGD in terms of the generalization performance. This observation is verified empirically by experiments in Figure [
Theorem 4. relates the risk SGD iterates to that of GD iterates. This idea has appeared in earlier literature 22 28 25 However, their decomposition is obtained via Young's inequality (see, e.g., Eq. (13) in Appendix A of Mücke et al. (25)), and is therefore stated as an upper bound on the SGD risk.
Our next theorem is to characterize the fluctuation error of SGD (with respect to GD).
Theorem 4.2 (Fluctuation error bound) Suppose that Assumptions 3.4 and all hold. Then for every n 2 1, & 2 1 and S c/ tr(H) for some absolute constant with probability at least 1 1/poly(n), it holds that
FluctnationEaror(( x
log(t): (r(H) log(n)
kyt log 5/2
1o2 (n) (1))
log (n)m n²/2
+
X i
min (1 tn [/
t
where kt 2 0 is arbitrary index (can be infinity).
We first explain the factor min { [| 12, by [| in our bound. First of all, when the interpolator w has a small f f-oom,, the quantity is automatically small. Furthermore, || S w² S 1 casily holds under mild assumptions factor with min [[[ 1I3, tr || W S W²t More interestingly, for SGD with constant stepsize and infinite optimization steps - oo), risk bound can still vanish, while all risk bounds in prior works (22 28 25 are vacuous. To see this, one can consider sequence of k e.g., kt = Vi, then it when + oo, so the fluctuation error vanishes.
w c.g., Assumption 3.1 Then, for finite f one can bound the
clear that ( Eis A
To complement the above results, we provide the following risk bound for GD. We emphasize that to obtain a risk bound for SGD.
any risk bound for GD can be plugged into Theorems 4.1 and 4.2
Theorem 4.3 (GD risk) Suppose that Assumptions
A
B and andCalll hold. Then for every n. 2 1,
t 2 and 1 < 1/ 2. with probability at least
(n)))((n). it holds that
1/
X
k-
Ew- [[(w))] w2
Σ d
+02.
Σ
2
n1
isc
k'
5

---

where k- == min(k: nd <
mt + + ESA Ar and x= n 1ft x Az. + Σ
The bound presented in Theorem 4.3 is comparable to that for ridge regression established by Tsigler and Bartlett [33] and will be much better than the bound of single-pass SGD when the signal-to-noise ratio is large 43 Theorem 5.1]. e.g., w² > o². In fact, Theorem 4.3 is proved via a reduction to ridge regression results. In particular, the quantity n//mnt for GD is analogy to the regularization parameter À for ridge regression [40] 29 36 21. As final remark, the assumption that w follows a Gaussian prior is the main concealing in Theorem 4.3 (which is not required by Tsigler and Bartlett B3].. The Gaussian prior on w" is known to allow a connection between early stopped GD with ridge regression
2
We conjecture that this assumption is not necessary and potentially removable.
Combining Theorems 4.1
4.2
and
4.3 we obtain the following risk bound for multi-pass SGD:
Corollary 4.4 Suppose that Assumptions 3. 4A 1- (/)oly((n)), it holds that
and D all hold. Then with probability at least
EsGD.w e [E(we)] S w?
X²
Σ 1>
+ +02.
k*
n
Σ
X
n
Ai
isk
')' log(()- (r(H) log(n) + kt log (2))
log
log 3/2 (m)tn
Σ N1 1
1/2
1/2
min {(br))+ (nw² + 0² tr( (AA- ,)= (r(H) + +z
where kt is an arbitrary index, K* minfk: nA S
22 Eish da3 and X ;= ott
Eisk do.
Tj
Comparison with Existing Results. We now discuss relationships between our bound and existing ones for multi-pass SGD 122 28 (5). First, we highlight that our bound is problem- deepedeed the sense that the bound is stated as function of the spectrum of data covariance; in contrast, existing papers only provide a minimax analysis for multi-pass SGD. Secondly, we rely on a different set of assumptions from the aforementioned papers. In particular, Pillaud-Vive
et al. (88 requires source condition on the data covariance (e.g. [I-//-rw" ||2 < oc for some constant 2 0), and Lin and Rosasco [22], Mücke et al. (25 require an effective dimension to be small, but our results are more general regarding the data covariance. Moreover, we assume w" follows a Gaussian prior (Assumption 3.1 which is also not directly comparable to the source condition in existing works.
Bartlett et al. 4 showed that OLS generalizes in the so called benign overfitting regime. Since when t 0o, SGD (with constant stepsize) converges to OLS, it would be interesting to compare the SGD solution with OLS in such a regime. We will do so with the following Corollary 4.5
Corollary 4.5 Suppose that Assumptions 3. B Gand D all hold. Assume the spectrum of H satisfies X = i- - log(i + 1)- for some absolute constant B > 1, then with probability at least 1 1- 1-1/poly(n), there exists choice of and y such that
ESGD, (<(((:) I w -log(n)) 0² log(n)=8.
Besides, for any fixed stepsize 17, we have
lim BSCD,."..(E(w.). S w2 log(n)) + o² log(n)-
As sanity check, our bound for ++ do matches the upper and lower bounds on the excess risk of OLS (which can be obtained by setting
in Tsigler and Bartlett (33). Moreover, Corollary 4.5 suggests that the excess risk achieved by multipass SGD is always no worse than that of OLS, and could be strictly smaller than that of OLS when 3 > 0.This demonstrates the benefit of multi-pass calli-ppss SGD over OLS.
Theorem and Lemmas
The following corollary characterizes the risk of multi-pass SGD for data covariance with a polyno- mially decaying spectrum.
Corollary 4.6 Suppose that Assumptions 3. B
and D all hold. Assume the spectrum of H decays polynomially, ie., X; = -i-1- for some absolute constant r > 0, then with probability at least 1 1/poly (n)), it holds that
Ew Ew<,([E(W.) S w² (tn) (r(x-1/(r+1) + 0². (tr)))(r+1)
n

---

2
G Hlg
411
Gradient Computation
Hog 20j
210
SGD, =;= 91+ 10)
215
SGD, A 10+
GD, Ai 1
GD, A/=/~
Steps
28
SGD, A -
222
SGD, -
2
2a
2
2
2²
23
2
20
1.4
1.2
1.0
0.8
0.6
0.4
0.2
1.4
1.2
1.0
0.8 Risk
0.6
0.4
0.2
Risk
(a) Iteration Complexity vs. Risk
(b) Gradient Complexity vs. Risk
Figure Iteration and gradient complexity comparison between SGD and GD. The curves report the minimum number of steps/gradients for each algorithm (with an optimally tuned stepsize) to achieve targeted risk.
Experiment setup the same as that in Figure
B S w² (In) -T((+1)) + o². (bn)2/(r+1)
n
log l (bn))/[++)) n1/2
(wr o²) log(t) log(n)
Corollary 4.6 provides concrete excess risk bounds for SGD and GD, based on which can make comparison between SGD and GD in terms of their iteration and gradient complexities. For simplicity, in the following discussion, we assume that wa x o² ~ 1. Then choosing by minimizes the upper bound for GD risk and yields the O(n-r/(r+1) rate. Here GD can employ constant stepsize. Similarly, SGD can match the GD's rate, O(n ((n=+((++)) by setting tnj ~ n and
1) S log (() (l)
min(log (n) न.. log 3 (m). -)))
(4.1)
The above implies that SGD (fixed stepsize, last iterate) can only cooperate with small stepsize.
Iteration Complexity. We first compare GD and SGD in terms of the iteration complexity. To reach the optimal rate, GD can employ constant stepsize and set the number of iterates be n. However, in order to shelve the fluctuation error, the stepsize of SGD cannot be large, as required by (4.1), More precisely, in order match the optimal rate, SGD needs to use small stepsize, 1) F n/t, with large number of iterates,
log(n)
. n (in)+
r> 1;
1og (.5 (n) 1. (5))
rs
It can be seen that the iteration complexity of SGD is much worse than that of GD. This result is empirically verified by (a)
Gradient Complexity. We next compare GD and SGD in terms of the gradient complexity. Recall that for each iterate, GD computes gradients but SGD only computes gradient. Therefore, reach the optimal rate, the total number of gradient computed by GD needs to be (n?2). )), but that computed by SGD is only of GD by a factor of (0mmin(0...1100-0) This result is empirically verified by Figure 2 (b).
Thus, the gradient complexity of SGD is better than that
Overview of the Proof Technique
In this section, will provide an overview of our proof technique and sketch the proof of Theorems The remaining proof is deferred to Appendix.
4.1
and 4.2
Our proof technique is inspired by the operator methods for analyzing single-pass pagge--aassaaa SGD 3 10 18
19
38 In particular, they track an error matrix, (w, w*) 6 (w; w*) that keeps richer information than the error norm ||w, w*1 For single-pass SGD where each data is used only once, the resulted iterates enjoy a simple dependence on history that allows an easy calculation of the expected error matrix (with respect to the randomness of data generation). However for
27
13

---

multi-pass SGD, data might be used multiple times, which prevents us from tracking the expected eтror matrix directly. Instead, trackable analogy to the error matrix is the empirical error matrix, (We W) & (w, W) where w is the minimum norm interpolator. More precisely, note that
Wi+1 w
w 71 (x,,X,, w. x. W) (I - 7/x,, x (w: w). (5.1)
Therefore the expected (over the algorithm's randomness) empirical error matrix updates as follows:
let Eg ESGD [ww - (w. w) ']. then Ex+1 = E,, [[T 7px, x, (I x,x,,..)]
Let Σ = _ x _ X be the empirical covariance matrix. We then follow the operator method 42 to
define the following operators symmetric matrices (e.g.. J):
G = (I .) - ,)=), Mo == ESGD (x,, xx,,xx,x,,) x.),, MoJ: = :JE.
Based on these operators, we can obtain close form update rule for E,:
E,
(M-M) E g' Eo + 2 Ei g--l- (M M) E₃-- (5.2)
92
n (w, ( w) is exactly the error matrix caused by GD iterates (with stepsize and iteration number t), and the second term O₂ is fluctuation matrix that captures the deviation of w, with respect to a corresponding GD iterate W.. We remark that the expected error matrix E, contains all information of w,.
Here the first term O
(I -I- n)--)
Risk Decomposition (Theorem 4.1 The following fact is clear from the update rule (5.1
Fact 5.1 The GD iterates satisfy We+1 w = (I - r/ W) and ESGD[W; w) = W. W.
Based on Fact 5.1 and 5. have
EscD| (W: w") (w: w
E, + (w w²) w")(w, w) + (W: w)( w²) + (w (w--"((f
w')( - w*)
① + (w w") w")(w, w) T + (W: w)(w w') (w w') -w") O₂
(w:- w (w: w*) O2
where O and O are defined in 5.2 and the last equality is due to θ = (w; - w) - W)
Also note that
EscD (Ew:)] = ESGD w:
[EsGD|(W: w") - w") 1.H).
2
2
Combining these two inequalities proves Theorem
LSSDDE = 11l w. w
EiD k= (gi-1-k (M- Ex, H)
(5.3)
2
eTTer
Fluctuation error
Finally, the fluctuation error is non-negative because both G and M M are PSD mappings.
Bounding the Fluctuation Error (Theorem 4.2). There are several challenges in the analysis of
fluctuation error: (1) it is difficult to characterize the matrix (M - -M) E, since the matrix Eg unknown: (2) the operator & involves an exponential decaying term with respect the empirical
covariance matrix E, which does not commute with the population covariance matrix H.
To address the first problem, we note that the operators M, G, M are PSD mappings and enjoy commutative property and then obtain the following result:
FluetuationEEroo x (Mo
H H,
(5.4)
Now, the input of the operator M gt-1-k will not be unknown matrix but fixed one (i.c., H). and the remaining effort will be focusing on characterizing M S o H. Applying the definitions of M and implies
Mo o - = -- [xx]] (I mE
(5.5)
8

---

Then our idea is to first prove an uniform upper bound on the quantity x (I (I-nž)) ) -I- )
for all E [n] (e.g,, denoted as U Uk, 77. n)), then it can be naturally obtained that
Mo G HH 3 U (k, 77, n)
[x, U 17, n) >,
(5.6)
then we will only need to characterize the inner product (Eg, Σ) in (.4). which can be understood as the optimization eπror at the k-th iteration.
In order to precisely characterize (k, 17. n),, we encounter the second problem that the population covariance H and empirical covariance E are not commute, thus the exponential decaying term
[-- will not be able to fully decrease H since some components of H may lie in the small eigenvalue directions of E. Therefore, we consider the following decomposition
x. (I - H(-
-1- (-
(H- -1-
Then for 11 it can be seen that the decaying term (I 17 )) is commute with E thus can successfully make it decrease. For 22, we will view the difference H Σ the component of H that cannot be effectively decreased by (I (I-10) =)))*, which will be small as n increases. More specifically, we can get the following upper bound on O).
Lemma 5.2 If the stepsize satisfies 7 S. e/tr/tr tr(H) for some small absolute constant c, then with probability at least - 1/ 1/poly(n), it holds that 11 S tr(H) llo(n)) - min { [K+1)m> || [2]
For O2 we will rewrite x, as e. X where e, E R and X E Raxd then
O 02=e,X(( x(I (1 E n e S lee X(I x(- 1 |H Ell2-
(5.7)
Then since and E have the same column eigenspectrum, we can fully unleash the decaying power of the term (I n² on X. Further note the that the row space of X is uniform distributed (corresponding to the index training data), which is independent of e;. This implies that we can adopt standard concentration arguments with covering on n fixed vectors {ei]=_ to prove sharp high probability upper bound (compared to the naive worst-case upper bound). Consequently, we state the upper bound O₂ in the following lemma.
Lemma 5.3 For every E [m] and he E [d]. it holds with probability at least 1 1/poly that (n)) n-72
2
[K+1)) + Eis ).).
6 Conclusion and Discussion
In this paper, we establish an instance-dependent excess risk bound of multi-pass SGD for inter- polating least square problems. The key takeaways include: (1) the excess risk of SGD is always worse than that of GD, given the same setup of stepsize and iteration number; (2) in order to achieve the same level of excess risk, SGD requires more iterations than GD; and (3) however, the gradient complexity of SGD can be better than that of GD. The proposed technique for analyzing multi-pase SGD could be of broader interest. The code and data for our experiments can be found on Github
Several interesting problems are left for future exploration:
A proplem-dependent excess risk lower bound could be useful to help understand the sharpness of our excess risk upper bound for multi-pass SGD and establish a clear separation between SGD and GD in terms of iteration and gradient complexity. The challenge here is mainly from the fact that the empirical covariance matrix Σ does not commute with the population covariance matrix H. In particular, one needs to develop an even sharper characterization on the quantity M o o o H (see
(5.5) ); more precisely, sharp lower bound on x (I - T) H(I - >/)))x x; is required.
SGD with decaying stepsizes could potentially improve the generalization performance of SGD with a constant stepsize. In this regard, most of our analysis can be extended to SGD/GD with decaying stepsizes. For example, Theorem 4.1 directly holds even for varying stepsizes, and Theorem 4.3 also holds under small modification, i.e., changing bn to k 7/k. However, our bounds on the fluctuation error may be more subtle to adapt. We conjecture that our analysis idea can still be applied, but the detailed calculations will depend on the particular stepsize scheduler of interests.

---

Multi-pass SGD without replacement is more practical SGD variant than the multi- pass SGD with replacement studied in this work. The key difference is that, the former does not pass training data independently (since each data must be used for equal times). In terms of optimization complexity, it has already been demonstrated in theory that multi-pass SGD without replacement (e.g., SGD with single shuffle or random shuffle) outperforms multi-pass, SGD with replacement [15 [ However, in terms of generalization, whether or not multi-pan SGD without replacement can outperform multi-pass SGD with replacement is still an open problem, as there lacks sharp excess risk analysis for multi-pass SGD without replacement. The techniques presented this paper can shed light on this direction.
Acknowledgments and Disclosure of Funding
We would like to thank the anonymous reviewers and area chairs for their helpful comments, This work was done when DZ was a Ph.D. student at UCLA. DZ is partially supported by Bloomberg data science Ph.D. fellowship and his startup funding in the institute of data science, the University of Hong Kong. JW and VB are supported by the Defense Advanced Research Projects Agency (DARPA) under Contract No. IR00112110130 QG is partially supported by the National Science Foundation award NSS-1906166 69 and 100-200 SK acknowledges funding from the Office of Naval Research under award N00014-22-1-41 22-77777777 and the National Science Foundation Grant under award CCF- 170354. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
References
[1] Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. Sgd with shuffling: optimal rates without component convexity and large epoch requirements. Advances Neural Information Processing Systems, 33:17526-17535 2020.
[2] Alnur Ali, J Zico Kolter, and Ryan Tibshirani. A continuous-time view of early stopping for least squares regression. In The 22nd international conference on artificial intelligence and statistics, pages 1370-1378. PMLR, 2019.
[3] Francis Bach and Eric Moulines. Non-strongly-comee smooth stochastic approximation with convergence rate o(1/n). Advances in neural information processing systems, 26:773-781, 2013.
[4] 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.
[5] Raef Bassily, Mikhail Belkin, and Siyuan Ma. On exponential convergence of sgd in non-convex over-parametrized learning, arXiv preprint 1rXiv:1811.000
2018.
[6] Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33:4381-4397 2020.
[7] Léon Bottou and Olivier Bousquet. The tradeoffs of large scale learning. Advances in neural information processing systems, 20, 2007.
[8] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-5 311,, 2018.
[9] Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint
2018
[10] Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger convergence rates for least-squares regression. The Journal of Machine Learning Research, 18 (1):3520-3570, 2017.
[11] Edgar Dobriban, Stefan Wager, et High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-279, 2018.
10

---

[12] Andre Elisseeff, Theodoros Evgeniou, Massimiliano Pontil, and Leslie Pack Kaelbing. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(1). 2005.
[13] 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.
[14] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, pages 1832-1841, PMLR, 2018.
[15] Jeff Haochen and Suvrit Sra. Random shuffling beats sgd after finite epochs. In International Conference on Machine Learning, pages 2624-2633. PMLR, 2019.
[16] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. International conference on muchine learning, pages 1225-1234. PMLR, 2016.
[17] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv:1903. 08560, 2019.
[18] 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). arXiv preprint arXiv:17100.04430. 2017.
[19] Prateek Jain, Praneeth Netrapalli, Sham Kakade, Rahul Kidambi, and Aaron Sidford. Paral- lelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification. The Journal of Machine Learning Research, 18(():8258-82)) 8299, 2017.
[20] Ilja Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In International Conference on Machine Learning, pages 2815-2824. PMLR, 2018.
[21] Yunwen Lei, Ting Hu, and Ke Tang. Generalization performance of multi pass stochastic gradient descent with convex loss functions. J. Mach. Learn. Res., 22:25-1, 2021.
[22] Junhong Lin and Lorenzo Rosasco. Optimal rates for multi-pass stochastic gradient methods. The Journal of Machine Learning Research, (811:3375--321, 2017.
[23] Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: effectiveness of sgd in modern over-parametrized learning. International Conference on Machine Learning, pages 3325-3334. PMLR, 2018.
Understanding the
[24] Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algo- rithms for machine learning. Advances neural information processing systems, 24, 2011.
[25] Nicole Mücke, Gergely Neu, and Lorenzo Rosasco. Beating sgd saturation with tail- tail-averaging and minibatching. Advances in Neural Information Processing Systems, 32, 2019.
[26] Deanna Needell, Rachel Ward, and Nati Srebro. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. Advances in neural information processing systems, 27, 2014.
[27] Gergely Neu and Lorenzo Rosasco. Iterate averaging as regularization for stochastic gradient descent. In Conference On Learning Theory, pages 3222-3242. PMLR, 2018
[28] Loucas Pillaud- Pillaud-Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes. Advances in Neural Information Processing Systems, 31, 2018.
[29] Garvesh Raskutti, Martin Wainwright, and Bin Yu. Early stopping and non-parametric regression: optimal data-dependent stopping rule. The Journal of Machine Learning Research, 151))3335-366 2014.
[30] Lorenzo Rosasco and Silvia Villa. Learning with incremental iterative regularization. Advances in Neural Information Processing Systems, 28, 2015.

---

[31] Itay Safran and Ohad Shamir. How good is sgd with random shuffling? In Conference on Learning Theory, pages 3250-3284. PMLR, 2020.
[32] Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. Advances in neural information processing systems, 23, 2010.
[33] Alexander Tsigler and Peter L Bartlett. Benign overfitting in ridge regression. arXiv preprint arXiv:2009. 14286, 2020.
[34] Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and an accelerated perceptron. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1195-1204. PMLR, 2019.
[35] Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste-Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. Advances in neural information processing systems, 32, 2019.
[36] Yuting Wei, Fanny Yang, and Martin J Wainwright. Early stopping for kernel boosting al- gorithms: general analysis with localized complexities. Advances Neural Information Processing Systems, 30, 2017.
[37] Denny Wu and Ji Xu. On the optimal weighted V regularization in overparameterrized lin- ear regression. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 10112-10123, Cur- ran Associates, Inc., 2020. /Rt/htttts:///rrcedding neurips httpr/ppp..../ppppp////////eeee [
[38] 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. arXiv preprint arXiv:21 10.06/ 98, 2021.
[39] Xu and Daniel Hsu. On the number of variables to use in principal component regression. Advances in neural information processing systems, 32, 2019.
[40] Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learning. Constructive Approximation, 26(2):289 2007.
[41] Yikai Zhang, Wenjia Zhang, Sammy Bald, Vamsi Pingali, Chao Chen, and Mayank Goswami. Stability of sgd: Tightness analysis and improved bounds. arXiv preprint arXiv:2102.05274, 2021.
[42] Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Benign overfitting of constant-stepsize sgd for linear regression. In Conference on Learning Theory, pages 4633 4635. PMLR, 2021.
[43] Difan Zou, Jingfeng Wu, Quanquan Gu, Dean P Foster, Sham Kakade, et al. The benefits of implicit regularization from sgd in least squares problems. Advances in Neural Information Processing Systems, 34, 2021.
12


Reviews:
[{"review_id": "uk1EAwaAG1e", "reviewer": "Reviewer_12me", "summary": "This paper studies the generalization properties of over-parameterized least squares with SGD. To be specific, the considered SGD works in a setting of multi-pass, one batch, last iterate, constant step-size SGD with replacement. By considering SGD with replacement, the analysis can be simplified due to the unbiased property of stochastic gradients, and accordingly, the iid data sampling strategy still holds under the multi-pass setting.\n", "questions": "1) Line 120: The expected covariance matrix H is required to be positive definite and A is full rank?\n\n2) Line 140: Running GD under the interpolation regime converges to the min-norm interpolator. This is a well-known result. However, the convergence of SGD path depends on the choice of the ground truth. It’s unclear to me on the convergence of SGD under the interpolation regime.\n\n3) Line 162: theorem 4.1, I like this theorem as well as (5.3) to show that, the excess risk of SGD is always worse than GD under the same iterations. I’m wondering that, this still holds true for other problem settings? e.g., different loss functions, over-parameterized neural networks. Besides, this result needs to be well discussed when compared to results on implicit bias of SGD.\n\n4) What’s the result under the exponential decay? As the authors mentioned in line 236, SGD with fixed size can only hold for small step-size under the polynomial decay. It seems that Corollary 4.5 allows for large step-size?\n\n5) albeit iid, the data are sampled from the empirical measure instead of the true (but unknown) population distribution \\mathcal{D}. Although the empirical measure converges to such true measure a.s. by the strong law of large numbers, it would be better to clarify this as the convergence rate of them needs to be estimated.\n\n6) Line 610: $\\Sigma$ is a random matrix, how does the choice of step-size can ensure $I – \\eta \\Sigma$ is PSD as $\\eta$ is in a deterministic upper bound.\n\nMinor issues:\n\n1) some notations are relatively confusing, e.g., $\\bf \\Theta_1$, $\\Theta_1$, and $\\Theta$.\n\n2) Line197: Lemma 5.2 requires the assumption $\\lambda_1 = \\Theta(1)$, please specify it.\n\n3) line 540: $nr$ -> $nr^2$ follows $\\chi^2(n)$ distribution. And why $r \\geq 1/2$ is satisfied?\n\nTypo:\n\nLine 272: $\\hat{\\bf w}_t$ is missing in ${\\bf \\Theta}_1$\n\nLine 675 and line 676 are repeated. \n", "limitations": "yes", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\nThis paper provides a solid analysis of multi-pass SGD of least squares in the interpolation regime. It provides nice results, e.g., 1) under this setting, the excess risk of SGD is always worse than that of GD; 2) the fluctuation error bound as well as the excess risk is based the eigenvalue decay of the data; 3) at the same level of excess risk, SGD requires more iterations but less gradient complexity than GD.\n\nCons:\n\nI think this work has no significant drawback, but it would better to clarify the theoretical results in several aspects:\n\n1) Line 261: what’s the difference between the expectation over “SGD” and $i_t$? According to the randomness definition of “SGD” in line 155, the randomness only comes from uniformly at random, i.e., “SGD”$=(i_1, i_2, …, i_t, …)$, right? This needs to be clear, especially on $\\mathbb{E}_{i_t} {x}_{i_t} {x}_{i_t}^{T}= {\\Sigma}$.\n\n2) What’s the benefit of multi-pass version as I don’t find very clear benefit in Corollary 4.5 under a relatively slow eigenvalue decay.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bbPKgBMjEjz", "reviewer": "Reviewer_BSbS", "summary": "This work studies the statistical aspects of empirical risk minimization (ERM) when solving it using SGD. The authors particularly focus on the (un-regularized) least squares objective where the minimum norm solution to the ERM problem can interpolate the empirical data. They show that the excess risk of SGD is exactly that of GD plus a non-negative fluctuation error under the same hyperparameters. This decomposition is used to give problem-dependent risk bounds for SGD and GD. These bounds show that GD achieves lower excess risk than SGD when given the same number of iterations, but SGD has a lower iteration cost so it can still be preferred in terms of computation.", "questions": "minor issues:\n\n- \"gram\" matrix should be spelled as \"Gram\" matrix\n- When comparing with existing results (page 6), it might be helpful to briefly introduce what a *source condition* is, for those who are less familiar with the related work.", "limitations": "I believe the authors have adequately addressed the limitations, such as lacking results for diminishing step sizes and the multi-pass SGD in the without replacement sampling regime. I agree with the authors on the foreseeable difficulties with these analyses and that they should be considered interesting future directions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well organized and highly polished. The claims are mostly sound, although I have only checked the proofs at a high level. I find the risk decomposition result interesting, and that giving problem-dependent risk bound is indeed desired to reflect the inherent difficulty of individual problems. Another strength is that the assumptions made in this paper are more general than existing works analyzing similar problems, although I have one issue regarding the combination of the assumptions together:\n\nAlthough the authors conjecture that the prior assumption on $w^*$ can potentially be removed, the results still rely on that to be true. However, it is unclear to me why, when a prior is assumed but the updates themselves are solving for an MLE rather than a MAP estimation. That is, if we know that the ground truth comes from Normal distribution with a known covariance that is a multiple of the diagonal, then the most natural thing to do for statistical accuracy is to incorporate that information by imposing a L2 regularization proportional to that multiple. However, if we do that, it'll be uncertain whether the interpolation condition can still easily hold. The minimum norm solution should also have an additional diagonal added to $X^TX$. To me this is a strange setting where a prior is assumed but never used in the algorithm, and I'm not sure how to interpret that, or whether it can be incorporated into the algorithm without contradicting the interpolation assumption. It would be great if the authors could elaborate on the reasoning behind throwing away the prior information, if I understood it correctly.\n\nLastly, although the authors have fully acknowledged that their results apply only to vanilla SGD in the with replacement setting, and the without replacement setting is set for future work, I still find the \"multi-pass SGD\" terminology somewhat misleading. In with replacement SGD a single pass does not guarantee a full pass of the training data - that is only guaranteed by some permutation-based SGD. This is not intended to nitpick (and was not a scoring factor in my evaluation) but I would like to encourage the authors to find an alternative expression. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "89gWIN9XS7u", "reviewer": "Reviewer_t7KM", "summary": "This work studies the generalization capability of multi-pass SGD for least squares problems under the interpolation regime. Specifically, the excess risk bound using the spectrum of data covariance achieved is provided under the assumptions: Gaussian prior to the true parameter and existence of interpolator. This result demonstrates the advantage of multi-pass SGD over OLS and GD under specific spectrum settings.\n", "questions": "- On lines 170-173: I am not sure if Young’s inequality (appearing in related works) is a weak point which should be noted. I think it does not slow down the convergence rate. What are the advantages of not using it?\n\n- What happens when taking limit $d\\to \\infty$ in proportion to $n$ as done in the context of random matrix theory? This question relates to a weakness stated (1) above. I am wondering if zero excess risk is achieved by taking limits of $n, d$, simultaneously.\n\n\n\n\n", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nA contribution of this work is that the excess risk bound described with the spectrum of data covariance is derived under the existence of an interpolator for examples, which seems to be new in the context of multi-pass SGD analysis (Pillaud-Vivien et al. [27], Line and Rosasco [21], and Mucke et al. [24]). Indeed, these studies assume specific decay rates of the spectrum and source conditions on the true parameter. \n\n\nAlthough direct comparison with these existing results is difficult in general, the authors show that multi-pass SGD achieves at least the comparable excess risk bound with OLS under a specific spectrum setting (Corollary 4.5) as a sanity check. \n\n\n**Weaknesses**\n\n(1) The existence of an interpolator limits the number of examples $n$ to e.g., $n<d$ (where $d$ is dimensionality.) This means we cannot take the limit $n\\to \\infty$ and cannot show the convergence to zero excess risk. I think this limitation seems unavoidable because the convergence $\\hat{w}\\to w_*$ (under $n\\to\\infty$) contradicts the assumptions where $\\hat{w}$ has finite norm and $w_*$ follows Gaussian prior. \n\n(2) On one hand, the assumption of the Gaussian prior is nice because it is a milder assumption compared to the source condition. On the other hand, this hinders characterizing learnable classes of target functions (e.g., Sobolev class et al.). \n\n\n**Other comments**\n\n- On line 86-87: ``More recently, ... an exponential rate in the interpolation regime [22,5,33,34]\" \nAn exponential convergence of SGD under the interpolation regime was also shown in Needell et al. [25].  Note that $\\sigma^2=0$ (in Theorem 2.1, [25]) which is attained in the interpolation regime yields an exponential rate.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3sXptVLafWY", "reviewer": "Reviewer_UZch", "summary": "The authors of the paper present their work on multipass SGD for least-squares. They show the following contributions:\n- The excess risk of SGD is the one of GD plus a positive fluctuation term\n- They show data-dependant bound consistent in the $t\\to\\infty$ regime, where $t$ is the number of iterations\n \n", "questions": "I have no question regarding the results.", "limitations": "- Hypothesis on the data to be subgaussian and indepedant.\n- Very similar to previous work.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### **Strengths**\n\n- The authors present a clear analysis of the setting they describe: an excess risk upper bound for multipass SGD for Least-squares. As far as I understood, they do so for the *final iterate*, which has been rarely considered. I guess that the authors' could stress on this idea a little bit more as previous analysis do not cover this case. \n- They provide bounds that are consistent in the so-called *benign overfitting regime*\n\n\n### **Weaknesses**\n\n- The main weakness is that the paper is largely overselling: e.g. the fact that the excess risk of SGD decomposes as GD and a fluctuation error cannot really be considered as a deep contribution even if previous work did not write it explicitly. In the same manner, comparison with existing literature is misleading: what the authors say about the novelty concerning the adaptivity to covariance structure is simply false.\n- Indeed, the authors claim that one of the main difference of their bound is that they are data dependant whereas previous work are not. I truly think that there is a confusion with the capacity and source conditions used by the mentioned authors: they correspond exactly to a nice framework showing how adaptive to the data SGD/GD/Ridge is. What is strange is that the authors, to exemplify their bound, take specific polynomial or polynomial + log decrease of eigenvalue of the covariance matrix: that is exactly a *capacity model* of the data.  Going further, it is said that the authors need a Gaussian prior over $w_*$. That condition is indeed not needed in the previous work. Here, the *source condition* could be a deeper look on how $w_*$ has been chosen (think about a *Gaussian process*) and would simply extend the authors' work.\n- The data assumptions on $H^{-1/2} x$ is strong (especially the independence of the coordinates). This almost corresponds to a gaussian model of the data. It may be necessary for the benign overfitting phenomenon to be exhibited but as far as the SGD optimisation is concerned, this is a very restrictive assumption compared to previous work.\n- Finally, I have to say that I find quite curious that the authors show bounds in the main theorem that necessitate a deep look to be understood (see corollary 4.4 for example). I understand that this appears to be one of the claimed strength of the authors but it is simply misleading for me. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept