The Benefits of Implicit Regularization from SGD in Least Squares Problems
Authors: Difan Zou
Jingfeng Wu
Vladimir Braverman
Quanquan Gu
Dean Foster
Sham M. Kakade
Venue: NeurIPS 2021 Poster (2021)
Keywords: stochastic gradient descent
implicit regularization
ridge regression
overparameterization

Abstract: Stochastic gradient descent (SGD) exhibits strong algorithmic regularization effects in practice, which has been hypothesized to play an important role in the generalization of modern machine learning approaches. In this work, we seek to understand these issues in the simpler setting of linear regression (including both underparameterized and overparameterized regimes), where our goal is to make sharp instance-based comparisons of the implicit regularization afforded by (unregularized) average SGD with the explicit regularization of ridge regression. For a broad class of least squares problem instances (that are natural in high-dimensional settings), we show: (1) for every problem instance and for every ridge parameter, (unregularized) SGD, when provided with \emph{logarithmically} more samples than that provided to the ridge algorithm, generalizes no worse than the ridge solution (provided SGD uses a tuned constant stepsize); (2) conversely, there exist instances (in this wide problem class) where optimally-tuned ridge regression requires \emph{quadratically} more samples than SGD in order to have the same generalization performance. Taken together, our results show that, up to the logarithmic factors, the generalization performance of SGD is always no worse than that of ridge regression in a wide range of overparameterized problems, and, in fact, could be much better for some problem instances. More generally, our results show how algorithmic regularization has important consequences even in simpler (overparameterized) convex settings.

The Benefits of Implicit Regularization from SGD in Least Squares Problems
Difan Zou" University of California, Los Angeles knowzouêcs. ucla. edu
Jingfeng Wu* Johns Hopkins University uuujf hu...eeu...e. edu
Vladimir Braverman Johns Hopkins University vova@cs. juu. edu
Quanquan Gu
Dean Foster
University of California, Los Angeles qguêcs. ucla.edu
Amazon
dean@foster net
Sham M. Kakade
University of Washington & Microsoft Research sham@cs washington.ede edu
Abstract
Stochastic gradient descent (SGD) exhibits strong algorithmic regularization ef- fects practice, which has been hypothesized to play an important role the generalization of modern machine learning approaches. In this work, we seek to understand these issues in the simpler setting of linear regression (including both underparameterized and overparameterized regimes), where our goal is make sharp instance-basee comparisons of the implicit regularization afforded by (unregularized) average SGD with the explicit regularization of ridge regres- sion. For broad class of least squares problem instances (that are natural in high-dimensional settings), we show: (1) for every problem instance and for ev- ery ridge parameter, (unregularized) SGD, when provided with logarithmically more samples than that provided to the ridge algorithm, generalizes no worse than the ridge solution (provided SGD uses tuned constant stepsize); (2) conversely, there exist instances (in this wide problem class) where optimally-tunee ridge regression requires quadratically more samples than SGD in order to have the same generalization performance. Taken together, our results show that, up to the logarithmic factors, the generalization performance of SGD is always worse than that ridge regression a wide range of overparameterized problems, and, in fact, could be much better for some problem instances. More generally, results show how algorithmic regularization has important consequences even simpler (overparamettrizze)) convex settings.
1 Introduction
Deep neural networks often exhibit powerful generalization in numerous machine learning applica- tions, despite being overparameterized. has been conjectured that the optimization algorithm itself, e.g., stochastic gradient descent (SGD), implicitly regularizes such overparameterized models [29]; here, (unregularized) overparameterized models could admit numerous global and local minima (many of which generalize poorly [29, 21)), yet SGD tends to find solutions that generalize well, even the absence of explicit regularizers [22, 29, 19]. This regularizing effect due to the choice of optimization algorithm is often referred as implicit regularization [22].
"Equal Contribution
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Before moving to the non-convex regime, we may hope to start by understanding this effect in the (overparameterized) convex regime. At least for linear models, there is a growing body of evidence suggesting that the implicit regularization of SGD is closely related to an explicit, t2-tye of (ridge) regularization [25]. For example, (multi-pass) SGD for linear regression converges to the minimum-norm interpolator, which corresponds to the limit of the ridge solution with vanishing penalty [29, 14]. Tangential evidence for this also comes from examining gradient descent, where continuous time (gradient flow) analysis shows how the optimization path of gradient descent is (pointwise) closely connected to an explicit, fg-regularization [24, 1J. Similar results [2] have been further extended to SGD, where a (early-stopped) continuous- time SGD is demonstrated to perform similarly to ridge regression with certain regularization parameters.
However, as of yet, a precise comparison between the implicit regularization afforded by SGD and the explicit regularization of ridge regression (in terms of the generalization performance) still lacking, especially when the hyperparameters (e.g., stepsize for SGD and regularization parameter for ridge regression) are allowed be tuned. This motivates the central question in this work:
How does the generalization performance of SGD compare with that of ridge regression in least square problems?
In particular, even in the arguably simplest setting of linear regression, we seek to understand if/how SGD behaves differently from using an explicit fz-regularizer, with a particular focus on the overparameterized regime.
Our Contributions. Due to recent advances on sharp. cestance-dependen excess risks bounds of both (single-pass) SGD and ridge regression for overparameterized least square problems [26, 30], a nearly complete answer to the above question is now possible using these tools. In this work, we deliver an iustance-based risk comparison between SGD and ridge regression in several interesting settings, including one-hot distributed data and Gaussian data. particular, for broad class of least squares problem instances that are natural in high-dimensional settings, we show that
For every problem instance and for every ridge parameter, (unregularized) SGD, when provided with logarithmically more samples than that provided to ridge regularization, generalizes no worse than the ridge solution, provided SGD uses a tuned constant stepsize.
Conversely, there exist instances in our problem class where optimally- ridge regression requires quadratically more samples than SGD to achieve the same generalization performance.
Quite strikingly, the above results show that, up to some logarithmic factors, the generalization performance of SGD is always no worse than that of ridge regression in a wide range of overpa- rameterized least square problems, and, in fact, could be much better for some problem instances. As special case (for the above two claims), our problem class includes setting in which: (i) the signal-to-noise is bounded and (ii) the eigenspectrum decays at polynomial rate 1/t", for 0 S a (which permits a relatively fast decay). This one-sided near-domination phenomenon (in these natural overparameterized problem classes) could further support the preference for the implicit regularization brought by SGD over explicit ridge regularization.
Several novel technical contributions are made to make the above risk comparisons possible. For the one-hot data, we derive similar risk upper bound of SGD and risk lower bound of ridge regression. For the Gaussian data, while a sharp risk bound of SGD is borrowed from [30], we prove a sharp
lower bound of ridge regression by adapting the proof techniques developed in [26, 7]. By carefully
comparing these upper and lower bound results (and exhibiting particular instances to show that sample size inflation bounds are sharp), we able to provide nearly complete conditions that characterize when SGD generalizes better than ridge regression.
Notation, For two functions fxx 2 0 and g(z) 2 0 defined on x > 0. we write f(x) S g(x)
if f(x S g(x) for some absolute constant >> 0; we write f(x) Z g(z) if g(z) S f(z);
write (xx R g(x) if f(x) S g(x:) $ (zx). For a vector w E Rd and a positive semidefinite matrix H [Rdxd we denote ||w|| == Vw WTTH. Hw.
Related Work
In terms of making sharp risk comparisons with ridge, the work of [10] shows that OLS (after a PCA projection is applied to the data) is instance-wise competitive with ridge on fixed design problems.
2

---

The insights in our analysis are draw from this work, though there are a number of technical challenges in dealing with the random design setting. We start with brief discussion of the technical advances in the analysis of ridge regression and SGD, and then briefly overview more related work comparing SGD to explicit norm-based regularization.
Excess Risk Bounds for Ridge Regression. In the underparameterizee regime, the excess risk bounds for ridge regression has been well-understood [16]. In the overparameterized regime, large body of works [12, 15, 28, 27] focused on characterizing the excess risk of ridge regression in the asymptotic regime where both the sample size N and dimension d go to infinite and d/N + ? for some finite 7. More recently, Bartlett et al. [7] developed sharp non-asymptotic risk bounds for ordinary least square in the overparameterized setting, which are further extended to ridge regression by Tsigler and Bartlett [26]. These bounds have additional interest because they are in particular, depending on the data covariance spectrum. The risk bounds of ridge regression derived in Tsigler and Bartlett [26] is highly nontrivial in the overparameterizer setting as it holds when the ridge parameter equals to zero or even being negative. This line of results build one part of the theoretical tools for this paper.
eestance-dependenns
Excess Risk Bounds for SGD. Risk bounds for mie-pass, constant-stepsize (average) SGD have been derived in the finite dimensional case [4, 9, 17, 18, 11, 1]. Very recently, the work of [30] extends these analyses, providing sharp instance-dependent risk bound applicable to the overparameterized regime; here, Zou et al. [30] provides nearly matching upper and lower excess risk bounds for constant-stepsize SGD, which are sharply characterized in terms of the full eigenspectrum of the population covariance matrix. This result plays a pivotal role in our paper.
Implicit Regularization of SGD vs. Explicit Norm-based Regularization. For least square problems, multi-pass SGD converges to the minimum morimum-normmaao norm solution [22, 29, 14], which is widely cited as (one of) the implicit bias of SGD. However, in more general settings, e-g., convex but non-linear models, a (distribution-indeeeneen) norm-based regularizer is no longer sufficient to characterize the optimization behavior of SGD [3, 8, 23]. Those discussions, however, exclude the possibility of hyperparameter tuning, e.g., stepsize for SGD and penalty strength for ridge regression, and are not instance-based either. Our aim in this paper is to provide instance-based excess risk comparison between the optimally tuned (one-pass) SGD and the optimally tuned ridge regression.
3 Problem Setup and Preliminaries
We seek to compare the generalization ability of SGD and ridge algorithms for least square problems. We use x E H to denote a feature vector in a (separable) Hilbert space H. We use d to refer to the dimensionality of H. where oo if H. is dnfinite-dimensione We use y E E denote a response that is generated by
y = (x, w*) + E
where w H is unknown true model parameter and & E R is the model noise. The following regularity assumption is made throughout the paper.
Assumption 3.1 (Well-specffied noise). The second moment of x. denoted by H = E[xx J,, is strictly positive definite and has finite trace. The noise & is independent of x and satisfies
Elg] = 0, and E(ça] oZ
In order to characterize the interplay between w and H in the excess risk bound, we introduce:
Ho: == k Avwy, and H == EisAAve
where (2 are the eigenvalues of H sorted in non-increasing order and v;'s are the corresponding eigenvectors. Then we define
(v. w)
[
2 H
Σ A, w)².
B.k
A
1>
The least squares problem is to estimate the true parameter w Assumption 3.1 implies that w is the unique solution that minimizes the population risk:
1
L( I(w*)=
min L(w), where L(w) = 2 B [10 x).. wEH
(3.1)
3

---

Moreover we have that L(w") o². For an estimation w found by some algorithm, e.g., SGD or ridge regression, its performance measured by the excess risk, L(w) L(w").
Constant-Stepsize SGD with Tail-Averaging. We consider the constant-steper SGD with tail- averaging [4, 17, 18, 30]; at the t-th iteration, a fresh example (x, yo) is sampled independently from the data distribution, and SGD makes the following update the current estimator W,-1 H.
W. Wi-1 + 7 (y: (Wr-1; 1; xz)) Xx, I - 1,2,...,
Wo = 0,
where > O is a constant stepsize. After N iterations (which is also the number of samples observed), SGD outputs the tail-averaged iterates the final estimator:
N-1
Wagd (N:))
2
Σ Wt-
N
N=N/2
In the underparameterizeed setting (d < N), constant-stepsize SGD with tail-averaging is known for achieving minimax optimal rate for least squares [17, 18). More recently, Zou et al. [30] investigate the performance of constant-stepsize SGD with tail- -aeragiggg in the overparameterized regime (d N), and establish mistance-dependees nearly-optimal excess risk bounds under mild assumptions on the data distribution. Notably, results from [30] cover underparameterized cases (d < N) as well.
Ridge Regression. Given N i..d. samples {(x,, y: J.) let us denote X := R RgN' and := 1y......U.. UN| E Rd. Then ridge regression outputs the following estimator for the true parameter [25]:
xy] E
Wridge (NV; A) == arg min Xw y11 + A/|w||
(3.2)
weH
where À (which could possibly be negative) is a regularization parameter. We remark that the ridge regression estimator takes the following two equivalent form:
Wridge NN; A) (X X
x XX
+ xIN)
(3.3)
The first expression is useful in the classical, underparameterized setting (d N) [16]; and the second expression is more useful in the overparameterized setting (d > N) where the empirical covariance X X is usually not invertible [20, 26]. As final remark, when 0, ridge estimator reduces to the ordinary least square estimator (OLS) [13].
Generalizable Regime. In the following sections we will make instance-based risk comparisons between SGD and ridge regression. To make the comparison meaningful, we focus regime where SGD and ridge regression are "generalizable", i.c, the SGD and the ridge regression estimators, hypeparameters,
with the optimally-tune population risk, i.c., o². The formal mathematical definition is as follows.
achieve excess risk that is smaller than the optimal
Definition 1 (Generalizability). Consider an algorithm Alg and least squares problem instance P. Let (ng , 0) be the output of the algorithm when provided with n i.i.d. samples from the problem instance P. and set of hyperparameters O (that could be a function on n.. Then we say that the algorithm Alg with sample size and hyperparameters configuration is generalizable on problem instance P, if
Eag. (Algg(,, 0))] L(w") 50
where the expectation is over the randomness of Alg and data drawn from the problem instance P.
Clearly, the generalizable regime is defined by conditions on both the sample size, hyperparameter configuration, the problem instance, and the algorithm. For example, in the d-dimensional setting with |w") ||2 = O11) the ordinary least squares (OLS) solution (ridge regression with À = 0), i.c., Wridge (N:0) 0) has Odoo /N) excess risk, then can say that the ridge regression with regularization parameter À = 0 and sample size N = (()) is in the generalizable regime on all problem instances in d-dimension with [w 1|2 O(1)
Sample Inflation vs. Risk Inflation Comparisons. This work characterizes the sample inflation of SGD, i.e., bounding the required sample size of SGD to achieve an instance- based comparable excess risk as ridge regression (which is essentially the notion of Bahadur statistical efficiency [5, 6]). Another natural comparison would be examining the risk inflation of SGD, examining the instance- based increase in risk for any fixed sample size. Our preference for the former is due to the relative instability of the risk with respect to the sample size (in some cases, given a slightly different sample size, the risk could rapidly change.).

---

Warm-Up: One-Hot Least Squares Problems
Let us begin with simpler data distribution, the one-hot data distribution. (inspired by settings where the input distribution is sparse). In detail, assume each input vector is sampled from the set of natural basis {el, ..,...,......................... ea} according to the data distribution given by [ ei = A where 0 < A and 2, A 1. The class of one-hot least square instances is completely characterized by the following problem set:
{(w": '.. Ad): w' H. -,
\1
... > 0}.
Clearly the population data covariance matrix is H diag(A1.... (..... Xa). The next two theorems give an instance- based sample inflation comparisons for this problem class.
Theorem 4.1 (Instance-wic comparison, one-hot data). Let Wage and Wridge A) be the solutions found by SGD and ridge regression when using N training examples. Then for any one-hot least square problem instance such that the ridge regression solution is generalizable and any there exists choice of stepsize 7 for SGD such that
L L[ (Nagd: 7²)] L(w") S L[Weidge WWeidge(Niidgee A)] L(w") <²
provided the sample size of SGD satisfies
Nagd 2 Nridge-
Theorem 4.1 suggests that for every one-hot problem instance, when provided with the same more number of samples, the SGD solution with a properly tuned stepsize generalizes at most constant times worse than the optimally tuned ridge regression solution. In other words, with the same number of samples, SGD is always competitive with ridge regression.
Theorem 4.2 (Best-case comparison, one-hot data). There exists one-hot least square problem instance satisfying ||w" l| = o², and a SGD solution with constant stepsize and sample size Nagd such that for any ridge regression solution with sample size
N2
Nridge
'gdd
log (Naga)
holds that,
L [[WidgeeNNas 2)] L(w")(W>""))) 2 L (Wegd(Negal
L(w").
Theorem 4.2 shows that for some one-hot least square instance, ridge regression, even with the aptimally-tuune regularization, needs at least (nearly) quadratically more samples than that provided to SGD, in order to compete with the optimally-tunee SGD. In other words, ridge regression could be much worse than SGD for one-hot least squares problems.
Remark 4.3. The above two results together indicate a superior performance of the implicit regular- ization of SGD in comparison with the explicit regularization of ridge regression, for one-hot least squares problems. This is not the only case that SGD is always no worse than ridge estimator. In fact, we will next turn compare SGD with ridge regression for the class of Gaussian least square instances, where both SGD and ridge regression exhibit richer behaviors but SGD still exhibits superiority over the ridge estimator.
Gaussian Least Squares Problems
In this section, we consider least squares problems with Gaussian data distribution. In particular, assume the population distribution of the input vector x is Gaussian", i.c., x ~ NO0, H). We further make the following regularity assumption for simplicity:
Assumption 5.1. H is strictly positive definite and has finite trace.
Gaussian least squares problems are completely characterized by the following problem [ww": w* E H}.
The next theorem give instance-based sample inflation comparison between SGD and ridge regression for Gaussian least squares instances.
We restrict ourselves to Gaussian distribution for simplicity. Our results hold under more general assump- tions, e.g., e. H 11/ x has GausGin tail and independent components [7] and is symmetrically distributed.
5

---

Theorem 5.1 (Instance-wise comparison, Gaussian data). Let Wagd(N:)) and Wridge (N; X) be the solutions found by SGD and ridge regression respectively. Then under Assumption 5.1, for any Gaussian least square problem instance such that the ridge regression solution is generalizable and any X, there exists a choice of stepsize 7"" for SGD such that
L [Waad Trssg(NNagge (NNaddi" y") L(w")) S L WVridge(Nidgee 2)] -L(w))
provided the sample size of SGD satisfies
Nagd 2 (1 + R22) k ((Niddg)) log(a) Nridgo
where
Hr(
<(n)
R²
< KNNridg)
(n,d)
Note that the result in Theorem 5.1 holds for arbitrary X. Then this theorem provides a sufficient condition for SGD such that it provably performs no worse than optimal ridge regression solution (i.e., ridge regression with optimal X). Besides, we would also like to point out that the SGD stepsize 7" in Theorem 5.1 is only a function of the regularization parameter À and tr tr(H), which can be easily estimated from training dataset without knowing the exact formula of H.
Different from the one-hot case, here the required sample size for SGD depends on two important quantities: St and x(Nridge). In particular, 1t2 [|w*lii /o² can be understood as the signal-to- noise ratio. The quantity <(Nniidge) characterizes the flatness of the eigenspectrum of H in the top Neidee-dimensine dimensiimenii subspace, which clearly satisfies nu x(Nridge) 2 Let us further explain why we have the dependencies on R² and xc( (Nridge) in the condition of the sample inflation for SGID.
A large R² emphasizes the problem hardness is more from the numerical optimization instead of from the statistic learning. In particular, let us consider special case where o and R² oc, i.e. there is no noise in the least square problem, and thus solving it is purely numerical optimization issue. In this case, ridge regression with À 0 achieves zero population risk so long as the observed data can span the whole parameter space, but constant stepsize SGD in general suffers a non-zero risk in finite steps, thus cannot competitive with the risk of ridge regression, which as predicted by Theorem 5. From a learning perspective, a constant or even small R² is more interesting.
To explain why the dependency on x(Nridge) unavoidable, we can consider 2-d dimensional example where
0 1 H H-6 Niidge IN (Naake))
w -(Nidgss
NNidge HC( (e(Nesde))
is commonly known that for this problem, ridge regression with À = 0 can achieve O /Nridger excess risk bound [13]. However, this problem is rather difficult for SGD since it is hard to learn the second coordinate of w" using gradient information (the gradient in the second coordinate is quite small). In fact, in order to accurately learn w [2]. SGD requires at least ((1/A2) 2 (Neiddge (NNrgge)) iterations/samples, which is consistent with our theory.
Then from Theorem 5.1 it can be observed that when the signal-to- to-niee ratio is nearly constant, i.c., R = 0(1) ,, and the eigenspectrum of H does not decay too fast so that k( (Nidge) S polylog(Nridge) worse than ridge regression, provided with logarithmically more samples than that provided to ridge regression. More specifically, the following corollary gives a family of problem instances that are in this regime.
SGD provably generalizes
Corollary 5.1. Under the same conditions as Theorem 5.1, let Nridge be the sample size of ridge regression. Consider the problem instance that satisfies H² = ((1), d = O(Nrige)) and X = 1/i2 for some < L, then SGD, with tuned stepsize T", provably generalizes worse than any ridge regression solution in the generalizable regime if
Nopd 2 logg (Nridge) Neidge-
We would like further point out that the comparison made in Corollary 5.1 concerns the worst-case result regarding w' (from the perspective of SGD), while SGD could perform much better if w" has a nice structure, For example, considering the same setting in Corollary 5.1 but assuming that the ground truth w* is drawn from prior distribution that is rotation invariant, SGD can be no worse than ridge regression provided the same or larger sample size. We formally state this result in the following corollary.

---

Corollary 5.2. Under the same conditions Corollary 5.1, let Nridge be the sample size of ridge regression. Consider the problem instance with random and rotation invariant w", then SGD with a tuned stepsize 7 provably generalizes no worse than any ridge regression solution in the generalizable regime if
Nagd 2 Niidgee
The next theorem shows that, in fact, for some instances, SGD could perform much better than ridge regression, as for the one-hot least square problems.
Theorem 5.2 (Best-case comparison, Gaussian data). There exists Gaussian least square problem instance satisfying R² = 1 and Kc ((Naaa) = (11), and an SGD solution with constant stepsize and sample size Nagd- such that for any ridge regression solution (f.e., any X) with sample size
N2
agd
Nridge
log (og"(N
it holds that,
L (Nridgge }) Low"((W>))) 2 L WWsgd (Negdi >")] L(w").
Besides the instance-wise comparison, it is also interesting to see under what condition SGD can provably outperform ridge regression, i.e., achieving comparable smaller excess risk using the same number of samples. The following theorem shows that this occurs when the signal-to-noise ratio R2 is constant and there is only small fraction of w living in the tail eigenspace of H.
Theorem 5.3 (SGD outperforms ridge regression, Gaussian data). Let Nridge be sample size of ridge tr(H) Niigge log( Neago)
regression and k-
min {1: AR S
}. then if R (()), and
Neidon
(eww
Nridge
imA+
for any ridge regression solution that is generalizable and any X, there exists choice of stepsize ? for SGD such that
L [ (Nagd 7*)] - L(w") S L [Wridge (Nridge: A)] L(w")
provided the sample size of SGD satisfies
N
Nridge-
Experiments. We perform experiments Gaussian least square problem. We consider 6 problem
instances, which are the combinations of 2 different covariance matrices H: X = i- and X = i-? and 3 different true model parameter vectors w w [t] 1, w [i] i and w [t] ; 100 Figure I compares the required sample sizes of ridge regression and SGD that lead to the same population risk these 6 problem instances, where the hyperparameters (i.e., 7 and A) fine-tuned to achieve the best performance. We have two key observations: (1) in terms of the worst problem instance for SGD (i.e., w [i] 1), its sample size is only worse than ridge regression up nearly constant factors (the curve is nearly linear); and (2) SGD can significantly outperform ridge regression when
the true model w* mainly lives in the head eigenspace of H (i.e., (*[i] i-10). The empirical observations are pretty consistent with our theoretical findings and again demonstrate the benefit of the implicit regularization of SGD.
An Overview of the Proof
In this section, we will sketch the proof of main Theorems for Gaussian least squares problems. Recall that we aim show that provided certain number of training samples, SGD is guaranteed to generalize better than ridge regression. Therefore, we will compare the risk upper bound of SGD [30] with the risk lower bound of ridge regression [26]*. In particular, first provide the following informal lemma summarizing the aforementioned risk bounds of SGD and ridge regression.
'The lower bound of ridge regression in our paper a tighter variant the lower bound in Tsigler and Bartlett [26] since we consider Gaussian case and focus on the expected excess risk. Tsigler and Bartlett [26] studied the sub- Gaussian and established a high- probability risk bound.
7

---

6000
6000
w [0]
w [1]
5000
5000
='
4000
w [[]
=/-10
4000
w -'[i==/-1
Nodag
Nidgg
3000
3000
2000
2000
1000
1000
500
1000
1500
2000
0
500
1000 Nagd
1500
2000
Nagd
(a) X
(b) X 8-
Figure 1: Sample size comparison between SGD and ridge regression, where the stepsize y and regularization parameter À are fine-tuned to achieve the best performance. The problem dimension 200 and the variance of model noise is x² = 1. We consider 6 combinations different covariance matrices and 3 different ground truth model vectors. The plots averaged over 20 independent runs.
Lemma 6.1 (Risk bounds of SGD and ridge regression, informal). Suppose Assumptions 3.1 and 5.1 hold and 7 S 1/ tr(H), then SGD has the following risk upper bound for arbitrary ky, lo E [d].
SGDRisk
N2 agd
1
1| ||epp(
Na w
11 0:11 +
||
Ha
SGDBiasBound
+ (1+ (1)22)02
+
Σ Xp
(6.1)
N Sggd
i>
SCDVarianceBound
Additionally, ridge regression has the following risk lower bound for a constant X, depending on X Nridge and H, and k = minfk: Nridge S X}
k-
Nridge
RidgeRisk Z
||
H +
|| || Ha +o²
x?
(6.2)
Nridge
N Nridge X2
RidgeBlasBound
RarieVaarinneeeBonne
We first highlight some useful observations in Lemma 6.1.
1. SGD has a condition on the stepsize: S 1/ lr(H), while ridge regression has no condition on the regularization parameter X.
2. Both the upper bound of SGD and the lower bound of ridge regression be decomposed into two parts corresponding to the head and tail eigenspaces of H. Furthermore, for the upper bound of SGD, the decomposition arbitrary (kj and ko are arbitrary), while for the lower bound of ridge estimator, the decomposition is fixed (i.e., k" is fixed).
3. Regarding the SGDBiasBound and SoDdadianceBouund performing the transformation N + aN and & a - will decrease SGDVaarianeeBound by factor of while the SGDBiasBound remains unchanged.
Based on the above useful observations, we can now interpret the proof sketch for Theorems 5.1, 5.2, and 5.3. We will first give the sketch for Theorem 5.3 and then prove Theorem 5.2 for the ease of presentation. We would like to emphasize that the calculation in the proof sketch may not be the sharpest since they are presented for the ease of exposition. A preciser and sharper calculation can be found in Appendix.
Proof Sketch of Theorem 5.1. In order to perform instance-wise comparison, we need to take care of all possible w* E H. Therefore, by Observation 2, we simply pick k2 -22 k* in the upper

---

bound (6.1). Then it is clear that if setting 7 = =x and Nagd Nridge, we have
SGDBiasBound < RiiggeBiaBBound
SGDVarianceBound = + R²) Ridge VarianceBound.
Then by Observation 3, enlarging agd by (1 R times suffices to guarantee
SGDBiasBound SGDVarianceBound RidgeBBisBoundd + Ridgeeeaiaann Variance
On the other hand, according to Observation 1, there is an upper bound on the feasible stepsize of SGD: < 1/ (r(H). Therefore, the above claim only holds when 2 tr tH()).
When I tr (H)),, the stepsize X-1 is no longer feasible and instead, we will use the largest possible stepsize: 7 = 1/ Ir(H), Besides, note that we assume ridge regression solution is in the generalizable regime, then it holds that k* s Nridge since otherwise we have
RidgeRisk
2 0².
Then again we set 11 = 1/ h" in SGDBiasBound and SGDVarianceBoumd Applying the choice of stepsize 7 1/ tr H) and sample size
log( R² (eNidge))
N agd
S Nridge Ki :((Niidge) log( Neidgee
Nridge);
get
(1 - Yg- Noga 722 N22 A2-
SGDBiasBound
//| || + ||
o²
+ || Ha
Nridge
RidgeBiasBound + RidgeVariancceonnd.
(6.3)
Moreover, also get the following bound SGDVarianceBound,
SGDVarianceBound < (1 R²)0² ( Nridge
k*
log [R² Neidge)
(Nri
+
AR- tr(H)
s (1 + R²²) log(Ie Nridge) RidgeVarianceeBonn,,
where in the second inequality we use the fact that
Nridge X
AR-
A4- tr(H)
Therefore by Observation again we can enlarge Nesd properly ensure that SGDVarianceBound remains unchanged and SGDVarianceBoound S VartgeeVaaanneBonndd Then combining this and (6.3) we can get
SGDBiasBound + SGDVarianceBound 2 2.RiidgBiasBoonnd + 2 VidgeearianceBound,
which completes the proof.
Proof Sketch of Theorem 5.3. Now will investigate in which regime SGD will generalizes worse than ridge regression when provided with same training sample size. For simplicity in the proof we assume R² = 1. First note that we only need to deal with the case where < tr(H) by the proof sketch of Theorem 5.
Unlike the instance-wise comparison that consider all possible w E H. in this lemma we only consider the set of w* that SGD performs well. Specifically, Theorem 5.1. in the worst-case comparison (in terms of w*), we require SGD to be able to learn the first k* (where K* < Nridge) coordinates of w* in order to be competitive with ridge regression, while SGD with sample size Nagd can only be guaranteed to learn the first kidd coordinates of w', where ka minfk: Ne S tr(H)). Therefore, in the instance- comparison we need to enlarge Negd to Nridge x(Nridge) to guarantee the learning of the top k* coordinates of w".
have shown in the proof of

---

However, this is not required for some good w 's that have small components in the kaga-k -k" coor- dinates. In particular, as assumed in the theorem, we have Σ Nedge As A S k] w I| /Nidge where k == min(k: A S (r(H) log((sgd)) satisfies 7o S kagd k Then let k 7 in SGDBiasBound, we have
SGDBiasBound
Lexp(-NNutt H H)w"
H ock
+ ||w"
22
ridge
(1 Neidge 7>p) )xx) Nziake /| Ila + +1lw"ll
2222 +
+ ||w" H
Nridge
I 2- Ridge Bar + RidgeBBissBound.
where (i) is due to the condition that Σ Neagu (= [i])² S k|| w/ww ll Moreover, it is easy
2;=841
to see that given Nagd Nridge and y 1/ (r(H)) < 1/X, we have SGDVarianceBound s 2 ValggeVarianceBounn.. As consequence we can ger
SGDBiasBound SGDVariancBBound s RidgeBiasBound + RidgeVarianneBound.
Proof Sketch of Theorem 5.2. We will consider the best w" for SGD, which only has nonzero entry in the first coordinate. For example, consider a true model parameter vector with w'[l] = 0 for > 2 and problem instance whose spectrum of H has flat tail with Σ Nudge X = (1) and Σizz X² @(1) Then according to Lemma 6.1, 1, we can set the stepsize / / /Ngaa) and get SGDRisk & SGDBiasBound SGDVarianceBound
1 and [i
as 7 = @ sgga
(0(11 Nagd +
log" (Naga) = o loog (Nagd)
Nagd
Nagd
For ridge regression, according to Lemma 6.1 we have
RidgeRisk 2 RidgeBiasBound + VadgeearrinneeBundd
=
X²
Nridge
since
N2
X2
ridge
12
1
Ω
by the fact that a + b 2 Vab
1/2
Therefore, evident that ridge regression is guaranteed to be worse than SGD if Nridge I N2 log" (Naga). This completes the proof.
7 Conclusions
We conduct an instance-based risk comparison between SGD and ridge regression for broad class of least square problems. We show that SGD is always no worse than ridge regression provided logarithmically more samples. On the other hand, there exist some instances where even optimally- tuned ridge regression needs quadratically more samples to compete with SGD. This separation in terms of sample inflation between SGD and ridge regression suggests provable benefit of implicit regularization over explicit regularization for least squares problems. In the future, we will explore the benefits of implicit regularization for learning other linear models and potentially nonlinear models.
Acknowledgments and Disclose of Funding
We would like thank the anonymous reviewers and area chairs for their helpful comments. DZ is supported by the Bloomberg Data Science Ph.D. Fellowship. JW is supported in part by NSF CAREER grant 1652257. VB supported in part by NSF CAREER grant 1652257, ONR Award N00014-18 1--188111-1 1-3644 and the Lifelong Learning Machines program from DARPA/MTO. QG is sup- ported part by the National Science Foundation awards IIS- 1855999 and IIS- 200881. SK acknowledges funding from the National Science Foundation under Award 173-1703574. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
10

---

References
[1] Alnur Ali, J Zico Kolter, and Ryan Tibshirani. A continuous-time view of early stopping for least squares regression. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1370-1378. PMLR, 2019.
[2] Alnur Ali, Edgar Dobriban, and Ryan Tibshirani. The implicit regularization of stochastic gradient flow for least squares. In International Conference on Machine Learning, pages 233- 244, PMLR, 2020.
[3] Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization, arXiv preprint urXiv:1900) 13655, 2019.
[4] Francis Bach and Eric Moulines. Non-strongly-convee smooth stochastic approximation with convergence rate o(1/n). Advances in neural information processing systems, 26:773-781, 2013.
[5] R. R. Bahadur. Rates of convergence of estimates and test statistics. Annals of Mathematical Statistics, 38:303-324 1967.
[6] R. R. Bahadur. Some Limit Theorems in Statistics. Society for Industrial and Applied Mathe- matics, 1971.
[7] 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.
[8] Assaf Dauber, Meir Feder, Tomer Koren, and Roi Livni. Can implicit bias explain general- ization? stochastic convex optimization as a case study. arXiv preprint arXiv:2003.06/55. 2020.
[9] Alexandre Défossez and Francis Bach. Averaged -eat---u-----rss: Bias-nariance trade-offs and optimal sampling distributions. In Artificial Intelligence and Statistics, pages 205-213, 2015.
[10] Paramveer Dhillon, Dean P Foster, Sham M Kakade, and Lyle H Ungar. A risk comparison of ordinary least squares vs ridge regression. The Journal of Machine Learning Research, 14(1): 1505-1511, 2013.
[11] 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-353 3570, 2017.
[12] Edgar Dobriban, Stefan Wager, et High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-277) 2018.
[13] Jerome Friedman, Trevor Hastie, Robert Tibshirani, et al. The elements of statistical learning, volume 1. Springer series in statistics New York, 2001.
[14] Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference Machine Learning, pages 1832-1841. PMLR, 2018
[15] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv: 085600 2019.
[16] Daniel Hsu, Sham M Kakade, and Tong Zhang. Random design analysis of ridge regression. In Conference on learning theory, pages 9-1. JMLR Workshop and Conference Proceedings, 2012.
[17] Prateek Jain, Sham M Kakade, Rahul Kidambi, Praneeth Netrapalli, Venkata Krishna Pillutla, and Aaron Sidford. markov chain theory approach characterizing the minimax optimality of stochastic gradient descent (for least squares). arXiv preprint 1rXiv:1710.094300 2017.

---

[18] Prateek Jain, Praneeth Netrapalli, Sham M Kakade, Rahul Kidambi, and Aaron Sidford. Paral- lelizing stochastic gradient descent for least squares regression: mini-batching, averaging, and model misspecification. The Journal of Machine Learning Research, (00:2288-8299 2017.
[19] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batte batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv: 04836, 2016.
[20] Dmitry Kobak, Jonathan Lomond, and Benoit Sanchez. The optimal ridge penalty for real- world high-dimennional data can be zero or negative due to the implicit ridge regularization. Journal of Machine Learning Research, 21(169):1-16, 2020.
[21] Shengchao Liu, Dimitris Papailiopoulos, and Dimitris Achlioptas. Bad global minima exist and sgd can reach them. arXiv preprint arXiv: 2019.
[22] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: the role of implicit regularization in deep learning. arXiv preprint arXiv: /412.6614 2014.
[23] Noam Razin and Nadav Cohen. Implicit regularization in deep learning may not be explainable by norms. arXiv preprint 2005:060905068 2020.
[24] Arun Suggala, Adarsh Prasad, and Pradeep K Ravikumar. Connecting optimization and regularization paths. Advances in Neural Information Processing Systems, 31: 16608-106,,, 2018.
[25] Andrei Nikolajevits Tihonov. Solution of incorrectly formulated problems and the regularization method. Soviet Marh., 4:
1963.
[26] Alexander Tsigler and Peter L. Bartlett. Benign overfitting in ridge regression. arXiv preprint 1eXi::0009.12286, 2020.
[27] Denny Wu and Xu, On the optimal weighted |ell.2 regularization in overparameterized linear regression. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 101 1201233.. Curran Associates, Inc., 2020.
[28] Ji Xu and Daniel Hsu. On the number of variables to use in principal component regression. arXiv preprint arXiv:1906 01 139, 2019.
[29] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03550 2016.
[30] Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham M Kakade. Benign overfitting of constant-stepsize sgd for linear regression. arXiv preprint 2rXiv:2103.1266 2021.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This paper focuses on theoretical explanations of the implicit regularization of SGD and its comparison to explicit regularization in ridge regression. has no potential negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "zcArnWe6IUz", "reviewer": "Reviewer_P3AS", "summary": "This paper shows that for a class of least-squares problems, unregularized SGD generalizes no worse than ridge estimate given additional logarithmically more samples. On the other hand, for certain data sets, ridge estimate (positive regularization) may require quadratically more samples than SGD to achieve the same generalization performance. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall it is an interesting paper. The main contribution is to show the advantage of unregularized SGD. On the other hand, I have some concerns about how important the contribution is and whether the comparisons are fair.\n1) While the logarithm factor does not sound large, it often changes the problem from an over-parameterized regime to an under-parameterized regime.  For example in corollary 1, while the ridge problem is over-parameterized with d=O(n), the SGD problem is very under-parameterized with $d/n\\rightarrow 0$. It feels a bit weird to compare two methods within two different regimes. \n2) The error bounds are compared with the constant factor being omitted. So I would not claim SGD outperforms ridge based on Theorem 5.2 or Theorem 5.3 because the constant factor could be less than 1 until I read the proof. I think the authors should make it more clear why the risk of ridge estimate is worse than SGD. In addition, the term $||w^*||_H$ with subscript $k:\\infty$ seem to be missed in both risk calculation in the proof of Theorem 5.2. If this term is constant (which is very likely), then this term is the dominant term of the risk.\n3) Overall, it seems like comparing ridge with SGD is to compare risk at $d/n\\rightarrow \\gamma$ at different $\\gamma$. I am not entirely convinced that SGD generalizes no worse or better than ridge is because of SGD. The results are just giving another example that we need to tune the ratio $d/n$. Specifically, Theorem 5.1 looks like comparing risk with $\\gamma=0$ with $\\gamma>1$, and we know given the constant signal-to-noise ratio, the two risks are comparable within a constant factor.  For Theorem 5.2 and 5.3, we know when the sample covariance matrix is very spiky, the best risk is achieved at $\\gamma=0$. Adding more samples can make $d/n\\rightarrow 0$, or I would suggest doing a PCR and achieve $d/n\\rightarrow 0$ by decreasing d.\n4) The problem is specific to linear regression which limits the contribution. Further, as shown in [26], in some cases, the optimal ridge parameter is negative. To make the results more convincing, the authors should explore this direction as well.\n\nOverall, I have concerns about the contribution of the paper.\n  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It is a theoretical paper. I think the main limitation is that for some regression problems, the sample size is limited. It is easier to select the number of features and the authors have not covered this part. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "uDqo8VSQpU", "reviewer": "Reviewer_zkCv", "summary": "Prior work showed that SGD has implicit regularization. This paper comperes the generalization performance of the implicit regularization (namely SGD without regularization) versus $ \\ell_2 $ regularization (i.e. ridge regression), which is a popular explicit regularization technique. The generalization performance is measured in excess risk. Using bounds on the excess risk, the authors show that SGD without regularization generalize at least as ridge regression, if not better.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The article is well written and well organized.\nHere are my comments:\n\n1.\tThe comparison made in the paper between single pass SGD and ridge regression is not impartial. Specifically, single pass SGD sees each sample only once and does not minimize the empirical risk. In contrast, for ridge regression, the authors considered the unique minimizer of the regularized risk. This equivalent to multi pass SGD with explicit regularization. In other words, for unregularized objective they use single pass SGD, and for regularized objective they use multi pass SGD. Why?\n2.\tThe implicit regularization of multi pass SGD for overparametrized linear regression is well understood. In this case, the obtained solution minimizes the Euclidean distance from initialization (this also cited by the authors). Considering my first remark, I think that the article could have been more convincing if they show advantages of implicit regularization over explicit in the simple (and well understood) case of multi pass SGD.\n3.\tIt is quite popular in statistical learning to use bounds that hold for some absolute coefficient. However, I am not sure to what extent these bounds meaningful.\n\nI note that due to time limitations, I have not checked the proofs.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 Hours"}, "extra_text": {}}, {"review_id": "kc8DBUlN20H", "reviewer": "Reviewer_uG8V", "summary": "The paper considers the problem of understanding implicit regularization of SGD for the problem of linear regression. The authors compare the excess risk guarantees of SGD solution to the one obtained by solving ridge regression exactly. The main contribution is to identify some conditions on the data distribution and the optimal solution under which: \n\n- The SGD solution (with log(n) more samples) is at least as good as the one obtained by ridge regression. \n- There exists a problem setting where the excess risk of the ridge regression solution is quadratically worse than the SGD solution. \n\nThe above separation result between SGD and ridge regression is obtained by explicitly computing **instance dependent** upper and lower bounds on their respective excess risk guarantees, and by comparing them under various assumptions on the data distributions. The presented results are shown for the setting when the feature vectors are one-hot or Gaussian. \n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I am a bit unsatisfied with the results and do not support acceptance. My reasons are: \n(1. ) Nature of the results: \nFor now, let us restrict to the Gaussian case (Main section of the paper, Section 5). The authors show that there are some conditions (call them A) such that for any learning problem that satisfies A: \n        -SGD is almost as good as Ridge regression. \n        -There exists a problem setting that satisfies A for which ridge regression is quadratically worse than SGD. \n\nAs a result, the authors conclude that SGD has a better implicit regularization than ridge regression. However, this jump is wrong !!! \n\nThe results presented in the paper do not rule out the following: There exists some other conditions B (different from A) on the data distribution such that for any learning problem that satisfies B: \n        -Ridge regression is almost as good as SGD \n        -There exists a problem that satisfies B (but not A) for which SGD is quadratically worse than ridge regression. \n\nB could be as natural / realistic as A, and the results in Theorem 5.1 shows that this may be possible. Thus, there could be some other conditions where the solutions obtained by ridge regression are better (or as good as) that of SGD. \n\nIn order to claim that SGD is better than ridge regression, one needs to show that (a) SGD works as well as ridge regression whenever ridge regression works, (b) there exists some problem when ridge regression is strictly worse than SGD. \n\nNote: the experiments shown in Figure 1 in the appendix support the above claim and show that there exist settings where ridge regression requires much less samples than SGD (see the blue line). This shows that the conditions B above may also be easy to characterize. \n\n(2.)  Step size for SGD: \nThe step size required for SGD to match the performance of ridge regression (as in Corollary 5.1 and Theorem 4.1) depends on the data distribution. It is not clear how to estimate it from data. Thus, it is not clear how to run SGD algorithm in practice to match the rates of ridge regression; limiting the scope of this result. \n\nThe choice of step size should not depend on the data distribution. If one has access to the distribution, we can simply run the following trivial algorithm: Given a distribution D, choose the starting point w_0 as the optimal solution for the test loss w.r.t. D. Set the step size to be 0 and run SGD. Here, the final output will be the optimal solution and always better than ridge regression. \n\n(3.) What about other regularizers? One can have regularizers (potentially data dependent) such that the RERM solution with this regularizer generalizes as well as SGD. I think the classical results which compare SGD solutions with ridge regression solutions are for the worst case distributions only. \n\n(4.) While the paper is technically rich, many of the instance dependent upper / lower bounds presented in the paper were known in earlier papers (or at least their proof techniques) (e.g. [29], [6]). Thus, the new technical contributions are limited. \n\nMinor issues / typos: \n       - Line 118 has a typo in H_{k: \\infty} in the aligned equation. \n       - Line 209 has a typi in the definition of a. What is N? \n       - The illustrative example from lines 222-228 is circular and uses k(N_{ridge}) in the definition. \n\nRest of the paper is well written! ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8-10 hours"}, "extra_text": {}}, {"review_id": "3l1UJS_lhFU", "reviewer": "Reviewer_dmQy", "summary": "This paper compares the excess risk of averaged SGD with that of ridge regression. The comparison is in the setting where the expected noise is zero and also the excess risks of the optimally tuned algorithms are smaller than the optimal population risk. The overall conclusion is that the performance of SGD is close to ridge regression in every problem in the class of interest and can even be better than ridge regression based on the eigenspectrum of the input and the signal-to-noise ratio.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I'm voting to accept the submission as these results can be a step towards understanding optimization and generalization of overparameterized models with SGD. The reliance of the results on signal-to-noise ratio also matches the previous observation that the behavior of SGD can be vastly different on real data versus random labels [28]. The main weakness is that, although the paper mentions that SGD requires at most logarithmically more samples, the constants in the bound can be huge.\n\nIn the instance-wise comparison (Theorem 5.1), the difference between SGD and ridge regression depends on the inverse of the smallest eigenvalue of the input. If the data is not well-conditioned, this factor can easily dominate the bound. The paper then correctly mentions that the constant cannot be removed, but still, with a large multiplicative factor, given the current bound, SGD can vastly underperform ridge regression. Do the authors have any empirical evidence that the smallest eigenvalue is large enough in common datasets?\n\nThe paper motivates its results as a study of implicit regularization and generalization of SGD, yet as l215 clarifies, there is an interplay of optimization and generalization at work, and the convergence rate and generalization ability together determine the risk. I suggest that the authors mention the role of convergence rate in the introduction and in other parts of the paper, for example in l256 that describes when SGD \"generalizes better\" than ridge regression. \n\nMinor comments:\n\nThe Gaussian assumption and Assumption 5.1 are made for simplicity yet it is not clear to me how relaxing these assumptions would change the results and if extra factors would be introduced.\n\nWhat is lambda in Theorem 5.1. Does the result hold for any lambda?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are addressed. Societal Impact is not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of understanding if SGD can be seen as a solution to implicit regularized empirical risk minimizer for the problem of  linear regression. The authors compare the excess risk guarantees of SGD solution to the one obtained by solving ridge regression exactly. The authors show that SGD solution is always almost as good as the one obtained by ridge regression. But on the other hand, there exists a problem setting where the excess risk of the ridge regression is substantially worse than the SGD solution. This shows that SGD cannot be seen as implicitly regularized ridge regression.

This paper generated a large number of discussions between the reviewers and also between reviewers and authors. While for some points there isnt total agreements, given the reviews and the discussion, it seems clear to me that the paper should be accepted first because despite some of the mentioned possible shortcomings the paper still is interesting and second, the subtler discussion points are exactly why we need to accept the paper so these issues are more widely discussed.
Decision: Accept (Poster)