The Benefits of Implicit Regularization from SGD in Least Squares Problems
Year: 2022

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 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 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.

heading: 1 Introduction
text: Deep neural networks often exhibit powerful generalization in numerous machine learning applications, despite being overparameterized. It 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 in the absence of explicit regularizers [22, 29, 19]. This regularizing effect due to the choice of the optimization algorithm is often referred to as implicit regularization [22].
∗Equal Contribution
35th Conference on Neural Information Processing Systems (NeurIPS 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, `2-type 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 a vanishing penalty [29, 14]. Tangential evidence for this also comes from examining gradient descent, where a continuous time (gradient flow) analysis shows how the optimization path of gradient descent is (pointwise) closely connected to an explicit, `2-regularization [24, 1]. 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) is still lacking, especially when the hyperparameters (e.g., stepsize for SGD and regularization parameter for ridge regression) are allowed to 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 `2-regularizer, with a particular focus on the overparameterized regime.
Our Contributions. Due to recent advances on sharp, instance-dependent 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 instance-based risk comparison between SGD and ridge regression in several interesting settings, including one-hot distributed data and Gaussian data. In particular, for a 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-tuned 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 overparameterized least square problems, and, in fact, could be much better for some problem instances. As a special case (for the above two claims), our problem class includes a setting in which: (i) the signal-to-noise is bounded and (ii) the eigenspectrum decays at a polynomial rate 1/iα, for 0 ≤ α ≤ 1 (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 our sample size inflation bounds are sharp), we are able to provide nearly complete conditions that characterize when SGD generalizes better than ridge regression.
Notation. For two functions f(x) ≥ 0 and g(x) ≥ 0 defined on x > 0, we write f(x) . g(x) if f(x) ≤ c · g(x) for some absolute constant c > 0; we write f(x) & g(x) if g(x) . f(x); we write f(x) h g(x) if f(x) . g(x) . f(x). For a vector w ∈ Rd and a positive semidefinite matrix H ∈ Rd×d, we denote ‖w‖H := √ w>Hw.

heading: 2 Related Work
text: 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.
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 a 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 underparameterized regime, the excess risk bounds for ridge regression has been well-understood [16]. In the overparameterized regime, a 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 γ. 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 instance-dependent, 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 overparameterized 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.
Excess Risk Bounds for SGD. Risk bounds for one-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-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-independent) 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.

heading: 3 Problem Setup and Preliminaries
text: We seek to compare the generalization ability of SGD and ridge algorithms for least square problems. We use x ∈ H to denote a feature vector in a (separable) Hilbert spaceH. We use d to refer to the dimensionality ofH, where d =∞ ifH is infinite-dimensional. We use y ∈ R to denote a response that is generated by
y = 〈x,w∗〉+ ξ, where w∗ ∈ H is an unknown true model parameter and ξ ∈ R is the model noise. The following regularity assumption is made throughout the paper. Assumption 3.1 (Well-specified noise). The second moment of x, denoted by H := E[xx>], is strictly positive definite and has finite trace. The noise ξ is independent of x and satisfies
E[ξ] = 0, and E[ξ2] = σ2.
In order to characterize the interplay between w∗ and H in the excess risk bound, we introduce: H0:k := ∑k i=1λiviv > i , and Hk:∞ := ∑ i>kλiviv > i , where {λi}∞i=1 are the eigenvalues of H sorted in non-increasing order and vi’s are the corresponding eigenvectors. Then we define
‖w‖2 H−10:k = ∑ i≤k (v>i w) 2 λi , ‖w‖2Hk:∞ = ∑ i>k λi(v > i w) 2.
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:
L(w∗) = min w∈H
L(w), where L(w) := 1
2 E(x,y)∼D
[ (y − 〈w,x〉)2 ] . (3.1)
Moreover we have that L(w∗) = σ2. For an estimation w found by some algorithm, e.g., SGD or ridge regression, its performance is measured by the excess risk, L(w)− L(w∗).
Constant-Stepsize SGD with Tail-Averaging. We consider the constant-stepsize SGD with tailaveraging [4, 17, 18, 30]: at the t-th iteration, a fresh example (xt, yt) is sampled independently from the data distribution, and SGD makes the following update on the current estimator wt−1 ∈ H,
wt = wt−1 + γ · ( yt − 〈wt−1,xt〉 ) xt, t = 1, 2, . . . , w0 = 0,
where γ > 0 is a constant stepsize. AfterN iterations (which is also the number of samples observed), SGD outputs the tail-averaged iterates as the final estimator:
wsgd(N ; γ) := 2
N N−1∑ t=N/2 wt.
In the underparameterized 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-averaging in the overparameterized regime (d > N ), and establish instance-dependent, 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.i.d. samples {(xi, yi)}Ni=1, let us denote X := [x1, . . . ,xN ]> ∈ RN×d and y := [y1, . . . , yN ]> ∈ Rd. Then ridge regression outputs the following estimator for the true parameter [25]:
wridge(N ;λ) := arg min w∈H
‖Xw − y‖22 + λ‖w‖22, (3.2)
where λ (which could possibly be negative) is a regularization parameter. We remark that the ridge regression estimator takes the following two equivalent form:
wridge(N ;λ) = (X >X + λId) −1X>y = X>(XX> + λIN ) −1y. (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 a 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 on regime where SGD and ridge regression are “generalizable”, i.e, the SGD and the ridge regression estimators, with the optimally-tuned hypeparameters, can achieve excess risk that is smaller than the optimal population risk, i.e., σ2. The formal mathematical definition is as follows. Definition 1 (Generalizability). Consider an algorithm Alg and a least squares problem instance P. Let Alg(n,θ) be the output of the algorithm when provided with n i.i.d. samples from the problem instance P, and a set of hyperparameters θ (that could be a function on n). Then we say that the algorithm Alg with sample size n and hyperparameters configuration θ is generalizable on problem instance P, if
EAlg,P[L ( Alg(n,θ) ) ]− L(w∗) ≤ σ2,
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 = O(1), the ordinary least squares (OLS) solution (ridge regression with λ = 0), i.e., wridge(N ; 0) hasO(dσ2/N) excess risk, then we can say that the ridge regression with regularization parameter λ = 0 and sample size N = ω(d) is in the generalizable regime on all problem instances in d-dimension with ‖w∗‖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 instancebased 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.).

heading: 4 Warm-Up: One-Hot Least Squares Problems
text: Let us begin with a simpler data distribution, the one-hot data distribution. (inspired by settings where the input distribution is sparse). In detail, assume each input vector x is sampled from the set of natural basis {e1, e2, . . . , ed} according to the data distribution given by P{x = ei} = λi, where 0 < λi ≤ 1 and ∑ i λi = 1. The class of one-hot least square instances is completely characterized by the following problem set:{ (w∗;λ1, · · · , λd) : w∗ ∈ H, ∑ iλi = 1, 1 ≥ λ1 ≥ λ2 ≥ · · · > 0 } .
Clearly the population data covariance matrix is H = diag(λ1, . . . , λd). The next two theorems give an instance-based sample inflation comparisons for this problem class. Theorem 4.1 (Instance-wise comparison, one-hot data). Let wsgd(N ; γ) and wridge(N ;λ) 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 a choice of stepsize γ∗ for SGD such that
L [ wsgd(Nsgd; γ ∗) ] − L(w∗) . L [ wridge(Nridge;λ) ] − L(w∗) < σ2,
provided the sample size of SGD satisfies
Nsgd ≥ Nridge.
Theorem 4.1 suggests that for every one-hot problem instance, when provided with the same or 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 an one-hot least square problem instance satisfying ‖w∗‖2H = σ2, and a SGD solution with constant stepsize and sample size Nsgd, such that for any ridge regression solution with sample size
Nridge ≤ N2sgd
log2(Nsgd) ,
it holds that,
L [ wridge(Nridge;λ) ] − L(w∗) & L [ wsgd(Nsgd; γ ∗) ] − L(w∗).
Theorem 4.2 shows that for some one-hot least square instance, ridge regression, even with the optimally-tuned regularization, needs at least (nearly) quadratically more samples than that provided to SGD, in order to compete with the optimally-tuned 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 regularization 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 to 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.

heading: 5 Gaussian Least Squares Problems
text: In this section, we consider least squares problems with a Gaussian data distribution. In particular, assume the population distribution of the input vector x is Gaussian2, i.e., x ∼ N (0,H). We further make the following regularity assumption for simplicity: Assumption 5.1. H is strictly positive definite and has a finite trace. Gaussian least squares problems are completely characterized by the following problem set{ (w∗;H) : w∗ ∈ H } .
The next theorem give an instance-based sample inflation comparison between SGD and ridge regression for Gaussian least squares instances.
2We restrict ourselves to the Gaussian distribution for simplicity. Our results hold under more general assumptions, e.g., H−1/2x has sub-Gaussian tail and independent components [7] and is symmetrically distributed.
Theorem 5.1 (Instance-wise comparison, Gaussian data). Let wsgd(N ; γ) and wridge(N ;λ) 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 λ, there exists a choice of stepsize γ∗ for SGD such that
L [ wsgd(Nsgd; γ ∗) ] − L(w∗) . L [ wridge(Nridge;λ) ] − L(w∗),
provided the sample size of SGD satisfies
Nsgd ≥ (1 +R2) · κ(Nridge) · log(a) ·Nridge, where
κ(n) = tr(H)
nλmin{n,d} , R2 = ‖w∗‖2H σ2 , a = κ(Nridge)R √ N.
Note that the result in Theorem 5.1 holds for arbitrary λ. 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 λ). Besides, we would also like to point out that the SGD stepsize γ∗ in Theorem 5.1 is only a function of the regularization parameter λ and 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: R2 and κ(Nridge). In particular, R2 = ‖w∗‖2H/σ2 can be understood as the signal-tonoise ratio. The quantity κ(Nridge) characterizes the flatness of the eigenspectrum of H in the top Nridge-dimensional subspace, which clearly satisfies κ(Nridge) ≥ 1. Let us further explain why we have the dependencies on R2 and κ(Nridge) in the condition of the sample inflation for SGD.
A large R2 emphasizes the problem hardness is more from the numerical optimization instead of from the statistic learning. In particular, let us consider a special case where σ = 0 and R2 =∞, i.e., there is no noise in the least square problem, and thus solving it is purely a 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 be competitive with the risk of ridge regression, which is as predicted by Theorem 5.1. From a learning perspective, a constant or even small R2 is more interesting.
To explain why the dependency on κ(Nridge) is unavoidable, we can consider a 2-d dimensional example where
H = ( 1 0 0 1Nridge·κ(Nridge) ) , w∗ = ( 0 Nridge · κ(Nridge) ) .
It is commonly known that for this problem, ridge regression with λ = 0 can achieve O(σ2/Nridge) 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/λ2) = Ω ( Nridgeκ(Nridge) ) iterations/samples, which is consistent with our theory.
Then from Theorem 5.1 it can be observed that when the signal-to-noise ratio is nearly a constant, i.e., R2 = Θ(1), and the eigenspectrum of H does not decay too fast so that κ(Nridge) ≤ polylog(Nridge), SGD provably generalizes no 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. 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 R2 = Θ(1), d = O(Nridge), and λi = 1/iα for some α ≤ 1, then SGD, with a tuned stepsize γ∗, provably generalizes no worse than any ridge regression solution in the generalizable regime if
Nsgd ≥ log2(Nridge) ·Nridge.
We would like to 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 a 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 as 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 γ∗ provably generalizes no worse than any ridge regression solution in the generalizable regime if
Nsgd ≥ Nridge.
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 a Gaussian least square problem instance satisfying R2 = 1 and κ(Nsgd) = Θ(1), and an SGD solution with a constant stepsize and sample size Nsgd, such that for any ridge regression solution (i.e., any λ) with sample size
Nridge ≤ N2sgd
log2(Nsgd) ,
it holds that,
L [ wridge(Nridge;λ) ] − L(w∗) & L [ wsgd(Nsgd; γ ∗) ] − 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 or smaller excess risk using the same number of samples. The following theorem shows that this occurs when the signal-to-noise ratio R2 is a constant and there is only a 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 regression and k∗ = min { k : λk ≤ tr(H)Nridge log(Nridge) } , then if R2 = Θ(1), and
Nridge∑ i=k∗+1 λi(w ∗[i])2 . k∗‖w∗‖2H Nridge ,
for any ridge regression solution that is generalizable and any λ, there exists a choice of stepsize γ∗ for SGD such that
L [ wsgd(Nsgd; γ ∗) ] − L(w∗) . L [ wridge(Nridge;λ) ] − L(w∗)
provided the sample size of SGD satisfies
Nsgd ≥ Nridge.
Experiments. We perform experiments on Gaussian least square problem. We consider 6 problem instances, which are the combinations of 2 different covariance matrices H: λi = i−1 and λi = i−2; and 3 different true model parameter vectors w∗: w∗[i] = 1, w∗[i] = i−1, and w∗[i] = i−10. Figure 1 compares the required sample sizes of ridge regression and SGD that lead to the same population risk on these 6 problem instances, where the hyperparameters (i.e., γ and λ) are 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 to 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., w∗[i] = i−10). The empirical observations are pretty consistent with our theoretical findings and again demonstrate the benefit of the implicit regularization of SGD.

heading: 6 An Overview of the Proof
text: In this section, we will sketch the proof of main Theorems for Gaussian least squares problems. Recall that we aim to 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]3. In particular, we first provide the following informal lemma summarizing the aforementioned risk bounds of SGD and ridge regression.
3The lower bound of ridge regression in our paper is a tighter variant of 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 case and established a high-probability risk bound.
Lemma 6.1 (Risk bounds of SGD and ridge regression, informal). Suppose Assumptions 3.1 and 5.1 hold and γ ≤ 1/ tr(H), then SGD has the following risk upper bound for arbitrary k1, k2 ∈ [d],
SGDRisk . 1 γ2N2sgd · ∥∥ exp(−NsgdγH)w∗∥∥2H−10:k1 + ‖w∗∥∥2Hk1:∞︸ ︷︷ ︸
SGDBiasBound + (1 +R2)σ2 · (
k2 Nsgd +Nsgdγ 2 ∑ i>k2 λ2i ) ︸ ︷︷ ︸
SGDVarianceBound
. (6.1)
Additionally, ridge regression has the following risk lower bound for a constant λ̃, depending on λ, Nridge, and H, and k∗ = min{k : Nridgeλk . λ̃}
RidgeRisk &
( λ̃
Nridge
)2 ‖w∗‖2H−1
0:k∗ + ‖w∗‖2Hk∗:∞︸ ︷︷ ︸
RidgeBiasBound
+σ2 ·
( k∗
Nridge + Nridge λ̃2 ∑ i>k∗ λ2i ) ︸ ︷︷ ︸
RidgeVarianceBound
. (6.2)
We first highlight some useful observations in Lemma 6.1.
1. SGD has a condition on the stepsize: γ ≤ 1/ tr(H), while ridge regression has no condition on the regularization parameter λ.
2. Both the upper bound of SGD and the lower bound of ridge regression can be decomposed into two parts corresponding to the head and tail eigenspaces of H. Furthermore, for the upper bound of SGD, the decomposition is arbitrary (k1 and k2 are arbitrary), while for the lower bound of ridge estimator, the decomposition is fixed (i.e., k∗ is fixed).
3. Regarding the SGDBiasBound and SGDVarianceBound, performing the transformation N → αN and γ → α−1γ will decrease SGDVarianceBound by a 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∗ ∈ H. Therefore, by Observation 2, we can simply pick k1 = k2 = k∗ in the upper
bound (6.1). Then it is clear that if setting γ = λ̃−1 and Nsgd = Nridge, we have
SGDBiasBound ≤ RidgeBiasBound SGDVarianceBound = (1 +R2) · RidgeVarianceBound.
Then by Observation 3, enlarging Nsgd by (1 +R2) times suffices to guarantee
SGDBiasBound + SGDVarianceBound ≤ RidgeBiasBound + RidgeVarianceBound.
On the other hand, according to Observation 1, there is an upper bound on the feasible stepsize of SGD: γ ≤ 1/ tr(H). Therefore, the above claim only holds when λ̃ ≥ tr(H).
When λ̃ ≤ tr(H), the stepsize λ̃−1 is no longer feasible and instead, we will use the largest possible stepsize: γ = 1/ tr(H). Besides, note that we assume ridge regression solution is in the generalizable regime, then it holds that k∗ ≤ Nridge since otherwise we have
RidgeRisk & RidgeVarianceBound ≥ σ2.
Then again we set k1 = k2 = k∗ in SGDBiasBound and SGDVarianceBound. Applying the choice of stepsize γ = 1/ tr(H) and sample size
Nsgd = log(R2Nridge)
γλk∗ ≤ Nridge · κ(Nridge) · log(R2Nridge),
we get
SGDBiasBound ≤ (1−Nsgdγλk ∗)Nsgd
γ2N2sgdλ 2 k∗
· ‖w∗‖2H0:k∗ + ‖w ∗‖2Hk∗:∞
≤ σ 2
Nridge + ‖w∗‖2Hk∗:∞
≤ RidgeBiasBound + RidgeVarianceBound. (6.3)
Moreover, we can also get the following bound on SGDVarianceBound, SGDVarianceBound ≤ (1 +R2)σ2 · ( k∗
Nridge +
log(R2Nridge)
λk∗ tr(H) ∑ i>k∗ λ2i ) ≤ (1 +R2) log(R2Nridge) · RidgeVarianceBound,
where in the second inequality we use the fact that
Nridge λ̃2 ≥ 1 λk∗ λ̃ ≥ 1 λk∗ tr(H) .
Therefore by Observation 3 again we can enlarge Nsgd properly to ensure that SGDVarianceBound remains unchanged and SGDVarianceBound ≤ RidgeVarianceBound. Then combining this and (6.3) we can get
SGDBiasBound + SGDVarianceBound ≤ 2 · RidgeBiasBound + 2 · RidgeVarianceBound,
which completes the proof.
Proof Sketch of Theorem 5.3. Now we will investigate in which regime SGD will generalizes no worse than ridge regression when provided with same training sample size. For simplicity in the proof we assume R2 = 1. First note that we only need to deal with the case where λ̃ ≤ tr(H) by the proof sketch of Theorem 5.1.
Unlike the instance-wise comparison that consider all possible w∗ ∈ H, in this lemma we only consider the set of w∗ that SGD performs well. Specifically, as we have shown in the proof of 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 Nsgd can only be guaranteed to learn the first k∗sgd coordinates of w
∗, where k∗sgd = min{k : Nridgeλk ≤ tr(H)}. Therefore, in the instance-wise comparison we need to enlarge Nsgd to Nridge · κ(Nridge) to guarantee the learning of the top k∗ coordinates of w∗.
However, this is not required for some good w∗’s that have small components in the k∗sgd-k ∗ coordinates. In particular, as assumed in the theorem, we have ∑Nridge i=k̂+1 λi(w ∗[i])2 ≤ k̂‖w∗‖2H/Nridge, where k̂ := min{k : λkNsgd ≤ tr(H) · log(Nsgd)} satisfies k̂ ≤ k∗sgd ≤ k∗. Then let k1 = k̂ in SGDBiasBound, we have
SGDBiasBound = 1 γ2N2ridge · ∥∥ exp(−NridgeγH)w∗∥∥2H−1 0:k̂ + ‖w∗ ∥∥2 H k̂:∞
≤ (1−Nridgeγλk̂) Nridge · ‖w∗‖2H0:k∗ + ‖w ∗‖2H k̂:∞
(i) ≤ R 2σ2(k̂ + 1)
Nridge + ‖w∗‖2Hk∗:∞
≤ 2 · RidgeVarBound + RidgeBiasBound. where (i) is due to the condition that ∑Nridge i=k̂+1 λi(w ∗[i])2 ≤ k̂‖w∗‖2H/Nridge. Moreover, it is easy to see that given Nsgd = Nridge and γ = 1/ tr(H) ≤ 1/λ̃, we have SGDVarianceBound ≤ 2 · RidgeVarianceBound. As a consequence we can get
SGDBiasBound + SGDVarianceBound ≤ 3 · RidgeBiasBound + 3 · RidgeVarianceBound.
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∗[1] = 1 and w∗[i] = 0 for i ≥ 2 and a problem instance whose spectrum of H has a flat tail with∑
i≥Nridge λ 2 i = Θ(1) and ∑ i≥2 λ 2 i = Θ(1). Then according to Lemma 6.1, we can set the stepsize
as γ = Θ(log(Nsgd)/Nsgd) and get SGDRisk . SGDBiasBound + SGDVarianceBound
= O
( 1
Nsgd +
log2(Nsgd)
Nsgd
) = O ( log2(Nsgd)
Nsgd
) .
For ridge regression, according to Lemma 6.1 we have RidgeRisk & RidgeBiasBound + RidgeVarianceBound
= Ω
( λ̃2
N2ridge + Nridge λ̃2
) since ∑ i≥k∗ λ2i = Θ(1)
= Ω
( 1
N 1/2 ridge
) . by the fact that a+ b ≥ √ ab
Therefore, it is evident that ridge regression is guaranteed to be worse than SGD if Nridge ≤ N2sgd/ log 2(Nsgd). This completes the proof.

heading: 7 Conclusions
text: We conduct an instance-based risk comparison between SGD and ridge regression for a 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 optimallytuned ridge regression needs quadratically more samples to compete with SGD. This separation in terms of sample inflation between SGD and ridge regression suggests a 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 to 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 is supported in part by NSF CAREER grant 1652257, ONR Award N00014-18-1-2364 and the Lifelong Learning Machines program from DARPA/MTO. QG is supported in part by the National Science Foundation awards IIS-1855099 and IIS-2008981. SK acknowledges funding from the National Science Foundation under Award CCF-1703574. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.

Review summaries:
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:   - The SGD solution (with log(n) more samples) is at least as good as the one obtained by ridge regression.  - There exists a problem setting where the excess risk of the ridge regression solution is quadratically worse than the SGD solution.   The 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.  

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.

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.