{'fraction_non_alphanumeric': 0.04831379495187266, 'fraction_numerical': 0.011420048010814086, 'mean_word_length': 4.08147797252487, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Benefits of Implicit Regularization from SGD in Least Squares Problems

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.


Introduction
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].
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) . For a vector w ∈ R d and a positive semidefinite matrix H ∈ R d×d , we denote w H := √ w 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.
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.

Problem Setup and Preliminaries
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 space H. We use d to refer to the dimensionality of H, where d = ∞ if H 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. In order to characterize the interplay between w * and H in the excess risk bound, we introduce: are the eigenvalues of H sorted in non-increasing order and v i 's are the corresponding eigenvectors. Then we define 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: 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 (x t , y t ) is sampled independently from the data distribution, and SGD makes the following update on the current estimator w t−1 ∈ H, After N iterations (which is also the number of samples observed), SGD outputs the tail-averaged iterates as the final estimator: In the underparameterized setting (d < N ), constant-stepsize SGD with tail-averaging is known for achieving minimax optimal rate for least squares [17,18] where λ (which could possibly be negative) is a regularization parameter. We remark that the ridge regression estimator takes the following two equivalent form: 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 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., w ridge (N ; 0) has O(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.).

Warm-Up: One-Hot Least Squares Problems
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 {e 1 , e 2 , . . . , e d } according to the data distribution given by P{x = e i } = λ 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: 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 w sgd (N ; γ) and w ridge (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 provided the sample size of SGD satisfies 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 * 2 H = σ 2 , and a SGD solution with constant stepsize and sample size N sgd , such that for any ridge regression solution with sample size it holds that, 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.

Gaussian Least Squares Problems
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 Gaussian 2 , 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.
Theorem 5.1 (Instance-wise comparison, Gaussian data). Let w sgd (N ; γ) and w ridge (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 provided the sample size of SGD satisfies 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: R 2 and κ(N ridge ). In particular, R 2 = w * 2 H /σ 2 can be understood as the signal-tonoise ratio. The quantity κ(N ridge ) characterizes the flatness of the eigenspectrum of H in the top N ridge -dimensional subspace, which clearly satisfies κ(N ridge ) ≥ 1. Let us further explain why we have the dependencies on R 2 and κ(N ridge ) in the condition of the sample inflation for SGD.
A large R 2 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 R 2 = ∞, 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 R 2 is more interesting.
To explain why the dependency on κ(N ridge ) is unavoidable, we can consider a 2-d dimensional example where .
It is commonly known that for this problem, ridge regression with λ = 0 can achieve O(σ 2 /N ridge ) 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 ) = Ω N ridge κ(N ridge ) 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., R 2 = Θ(1), and the eigenspectrum of H does not decay too fast so that κ(N ridge ) ≤ polylog(N ridge ), 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 N ridge be the sample size of ridge regression. Consider the problem instance that satisfies R 2 = Θ(1), d = O(N ridge ), 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 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 N ridge 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 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 R 2 = 1 and κ(N sgd ) = Θ(1), and an SGD solution with a constant stepsize and sample size N sgd , such that for any ridge regression solution (i.e., any λ) with sample size it holds that, 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 R 2 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 N ridge be sample size of ridge regression and k * = min k : for any ridge regression solution that is generalizable and any λ, there exists a choice of stepsize γ * for SGD such that provided the sample size of SGD satisfies 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 * : 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.

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 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.
Additionally, ridge regression has the following risk lower bound for a constant λ, depending on λ, N ridge , and H, and k * = min{k : N ridge λ k λ} 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 (k 1 and k 2 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 k 1 = k 2 = k * in the upper bound (6.1). Then it is clear that if setting γ = λ −1 and N sgd = N ridge , we have Then by Observation 3, enlarging N sgd by (1 + R 2 ) times suffices to guarantee 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 * ≤ N ridge since otherwise we have Then again we set k 1 = k 2 = k * in SGDBiasBound and SGDVarianceBound. Applying the choice of stepsize γ = 1/ tr(H) and sample size Moreover, we can also get the following bound on SGDVarianceBound, where in the second inequality we use the fact that N ridge Therefore by Observation 3 again we can enlarge N sgd properly to ensure that SGDVarianceBound remains unchanged and SGDVarianceBound ≤ RidgeVarianceBound. Then combining this and (6.3) we can get 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 R 2 = 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 * ≤ N ridge ) coordinates of w * in order to be competitive with ridge regression, while SGD with sample size N sgd can only be guaranteed to learn the first k * sgd coordinates of w * , where k * sgd = min{k : N ridge λ k ≤ tr(H)}. Therefore, in the instance-wise comparison we need to enlarge N sgd to N ridge · κ(N ridge ) 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 where (i) is due to the condition that Moreover, it is easy to see that given N sgd = N ridge 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≥N ridge λ 2 i = Θ(1) and i≥2 λ 2 i = Θ(1). Then according to Lemma 6.1, we can set the stepsize as γ = Θ(log(N sgd )/N sgd ) and get SGDRisk SGDBiasBound + SGDVarianceBound For ridge regression, according to Lemma 6.1 we have RidgeRisk RidgeBiasBound + RidgeVarianceBound by the fact that a + b ≥ √ ab Therefore, it is evident that ridge regression is guaranteed to be worse than SGD if N ridge ≤ N 2 sgd / log 2 (N sgd ). This completes the proof.

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

A.1 Excess risk bound of SGD
In this part we will mainly follow the proof technique in Zou et al.
[30] that is developed to sharply characterize the excess risk bound for SGD (with tail-averaging) when the data distribution has a nice finite fourth-moment bound. However, such condition does not hold for the one-hot case so that their results cannot be directly applied here.
Before presenting the detailed proofs, we first introduce some notations and definitions that will be repeatedly used in the subsequent analysis. Let H = E[xx ] be the covariance of data distribution. It is easy to verify that H is a diagonal matrix with eigenvalues λ 1 , . . . , λ d . Let w t be the t-th iterate of the SGD, we define η t := w t − w * as the centered SGD iterate. Then we define η bias t and η variance t as the bias error and variance error respectively, which are described by the following update rule: Accordingly, we can further define the bias covariance B t and variance covariance C t as follows Regarding these two covariance matrices, the following lemma mathematically characterizes the upper bounds of the diagonal entries of B t and C t .
Proof. According to (A.1), we have Note that x t = e i with probability λ i , then we have

Then if only look at the diagonal entries of both sides, we havē
where in the first equation we use the fact that diag(HB) = diag(BH) = HB and the inequality follows from the fact that bothB t and H are diagonal and γ ≤ 1.
Similarly, regarding C t the following holds according to (A.1), where we use the fact that E[ξ t |x t ] = 0. Similar to deriving the bound forB t , we have Besides, under Assumption 3.1 we also have E[ξ 2 t x t x t ] = σ 2 H, which is a diagonal matrix. Based on these two results, we can get the following upper bound forC t , This completes the proof.
Proof. The first conclusion of this theorem can be directly proved via Young's inequality.
Note that H is a diagonal matrix, and thus (I − γH) k−t is also a diagonal matrix for all k and t. Therefore, by Lemma A.2, it is clear that in order to calculate the upper bound of the bias and variance error, it suffices to consider the diagonal entries of B N +t and C N +t , denoted byB N +t and C N +t (which are obtained by setting all non-diagonal entries of B N +t and C N +t as zero). Then by Young's inequality, Lemma A.2 implies that Now we are ready to precisely calculate the above two bounds. In particular, by Lemma A.1 we havē where in the second inequality we use the fact that 1]. Then for all i we have where we use the fact that γ ≤ 1 ≤ 1/λ i for all i. This further implies that Plugging the above results into (A.6) leads to Then we will deal with the variance error. Plugging (A. 5 We then use the inequality (1 − x) N ≥ min{0, 1 − xN } again and thus the above inequality further leads to

A.2 Excess risk bound of ridge regression
Lemma A.4. Let X ∈ R N ×d be the training data matrix and w ridge (N ; λ) be the solution of ridge regression with parameter λ and sample size N , then for any λ > 0 where the expectations are taken over the randomness of the training data matrix X.
Proof. Recall that the solution of ridge regression takes form where X is the data matrix and y is the response vector. Then according to the definition of the loss function L(w), we have where the last equation is by Assumption 3.1. Then regarding E[ w ridge (N ; λ) − w * 2 H ], let ξ = y − Xw * be the model noise vector, we have where in the last inequality we again apply Assumption 3.1 that E[ξ|X] = 0. More specifically, the bias error can be reformulated as In terms of the variance error, note that by Assumption 3.1 we have E[ξξ |X] = σ 2 I, then where RidgeBias max where k * = min{k : N λ k ≤ 1}.
Proof. In the one-hot case, it is easy to verify that X X = n i=1 x i x i is a diagonal matrix. Let µ 1 , µ 2 , . . . , µ d be the eigenvalues of X X corresponding to the eigenvectors e 1 , e 2 , . . . , e d respectively. Then by Lemma A.4, we have the following results for the bias and variance errors of ridge regression.
where the expectation in the first equation is taken over the training data X and in the second inequality the expectation is equivalently taken over the eigenvalues µ 1 , . . . , µ d . Since x i can only take on natural basis, the eigenvalue µ i can be understood as the number of training data that equals e i . Note that the probability of sampling e i is λ i , then we can get that µ i has a marginal distribution Binom(N, λ i ), where N is the sample size. Then in terms of each expectation in (A.8), we first have where the first inequality is by applying Jensen's inequality to the convex function f (x) = 1/(x+λ) 2 . On the other hand, we also have Therefore, combining the above two lower bounds, we can get the following lower bound on the bias error by (A.8) Therefore, a trivial lower bound on the bias error of ridge regression is Additionally, note that (1−λ i ) N ≥ 0.25 if λ i ≤ 1/N and N ≥ 2. Then let k * = min{k : N λ k ≤ 1}, (A.9) further leads to This completes the proof of the lower bound of the bias error.
By Lemma A.4, we have Regarding the variance error, we cannot use the similar approach since the function g(x) = x/(x+λ) 2 is no longer convex. Instead, we will directly make use of property of the binomial distribution of µ i to prove the desired bound. In particular, note that µ i ∼ binom(N, λ i ), by Bernstein inequality, we have Therefore, in this case, we can get (A.11) Then we consider the case that N λ i < 6. In particular, we have Note that µ i follows Binom(N, λ i ) distribution, which implies that

Plugging this into (A.12) gives
(A.13) Therefore, let k * = min{k : N λ k ≤ 1}, then for all i ≤ k * , combining (A.11) and (A.13) gives For all i > k * , we can directly apply (A.13) to get the lower bound. Therefore, according to (A.10), the variance error can be lower bounded as follows, This completes the proof of the lower bound of the variance error.
Next, we will show that the excess risk of SGD can be provably upper bounded (up to constant factors) by the excess risk of ridge regression respectively, given the sample size of ridge regression N ridge (which we will use N in the remaining proof for simplicity). In particular, we consider two cases regarding different λ: Case I λ < 1 and Case II λ ≥ 1.
For Case I, (A.15) gives the following bias lower bound for ridge regression, where in (i) we use the fact that N λ i + λ N λ i for all i ≤ k * .
Then let R 2 = w * 2 2 /σ 2 denotes the signal-to-noise ratio, let's consider the following configuration for SGD: Then by (A.14) and setting k 1 = 0 and k 2 = k * , we get Therefore, given such choice of N sgd and γ, we have For Case II, we can define k * = min{k : N λ k ≤ λ}, then (A.15) implies where (i) and (ii) are due to the fact that for every i ≤ k * , we have Therefore, we can apply the following configuration for SGD: Then by (A.14) and set k 1 = k 2 = k * , we have Combining the results for these two cases completes the proof.

A.4 Proof of Theorem 4.2
Proof. For simplicity we define N := N sgd in the proof.
• The data covariance matrix H has the following spectrum • The true parameter w * is given by Then it is easy to verify that tr(H) = 1. For SGD, we consider setting the stepsize as γ * = N −1/2 . Then by Lemma A.3 and choosing k 1 = 1, we have the following on the bias error of SGD, For variance error, we can pick k 2 = 1 and get Now let us characterize the excess risk of ridge regression. In terms of the bias error, by Lemma A.5 we have 16) where k * = min{k : N ridge λ k ≤ 1}. Then it is clear for ridge regression we must have λ N ridge log(N )/N 1/2 since otherwise RidgeBias σ 2 SGDRisk. Regarding the variance, we have Then we will consider two cases: (1) N ridge N and (2) N ridge N . In the first case we can get k * = 1 and then .
In this case, we can get k * = 1 and thus where (i) is due to we require λ N ridge log(N )/N 1/2 to guarantee vanishing bias error and (ii) is due to in this case we have N ridge N . As a result, ridge regression cannot achieve smaller excess risk than SGD in this case.
In the second case we can get k * = N and then where the second inequality is due to k * = N . We will again consider two cases: where k 1 , k 2 ∈ [d] are arbitrary.
This theorem is a simple extension of Theorem 5.1 in Zou et al. [30]. In particular, we observe that though the original theorem is stated for some particular k * and k † , based on the proof, their results hold for arbitrary k 1 and k 2 , as stated in Theorem B.  (N ; λ)) − L(w * ) = RidgeBias + RidgeVariance, and there is some absolute constant b > 1, such that for the following holds: B.2 Proof of Theorem 5.1 Proof. For simplicity, let us fix N := N ridge and k := k ridge , we will next locate γ such that the risk of SGD competes with that of Ridge. Denote λ := λ + i>k λ i . Then Then for SGD we can set Next we discuss two cases: Case I, λ · (1 ∨ κ log a) ≥ tr(H). For SGD, let us set k sgd = k and that Thus we obtain that

RidgeRisk.
Case II, λ · (1 ∨ κ log a) < tr(H). For SGD, let us set k sgd = k and that We obtain that SGDRisk ≤ SGDBias + SGDVariance The second and the third terms match those of ridge error. As for the first term, notice that by the choice of γ and that λ k ≥ λ N , we have that RidgeRisk. and These complete the proof.

B.4 Proof of Corollary 5.2
Proof. Note that given random w * , the expected risk considered in our paper will be including the expectation over both random data x and random ground-truth w * . Since the distribution of w * is rotation invariant, the expectation of w * [i] will be the same for all i ∈ [d]. Therefore, let , the following holds according to (6.2) where k * = min{k : N ridge λ k ≤ λ}. Then note that λ i = i −α , we have k * = (N ridge / λ) 1/α , which implies that where we use the fact that d = Θ(N ). Note that constant SNR R = Θ(1) implies that Then by (6.1) and set N sgd = N ridge = N and k 1 = k 2 = N ridge , we have Note that we have Then we can set γ 1/ tr(H) N α−1 and get This implies that SGD can be no worse than ridge regression as long as provided same or larger sample size, which completes the proof.

B.5 Proof of Theorem 5.2
Proof. For simplicity we fix N := N sgd . Let us consider the following problem instance: • The data covariance matrix H has the following spectrum where we require the dimension d ≥ N 2 . We note that tr(H) = 1 + N/ log N N/ log N .
• The true parameter w * is given by Then for SGD, we choose stepsize as γ = log(N )/(2N ) ≤ 1/ tr(H). By Lemma B.1, we have the following excess risk bound for w sgd (N ; γ * ), L w sgd (N ; γ) − L(w * ) ≤ SGDBias + SGDVariance, where where we use the fact that i>1 λ 2 i = 1 log 2 N . This implies that SGD with sample size N achieves at most O(σ 2 /N ) excess risk on this example.
This completes the proof.
B.6 Proof of Theorem 5.3 Proof. The proof of Theorem 5.3 is similar to that of Theorem 5.1. In particular, we still consider two cases: (1) λ tr(H) and (2) λ tr(H). For the first case, we can use the identical proof in Theorem 5.1 and get that SGD with sample size N sgd (1 + R 2 ) · N ridge to achieve better excess risk than ridge regression. Note that we have assumed R 2 = Θ(1), therefore, we can claim that SGD outperforms ridge regression, as long as the sample size is at least in the same order of N ridge .
For the second case that λ tr(H), for simplicity we denote N := N ridge and we can directly set γ = 1/ tr(H) and N sgd = N . Let k * = min k : λ k ≤ tr(H) log(N ) N , then by the definition of k * ridge in Lemma B.2 and the assumption that ridge regression is in the generalizable regime, we have k * ≤ k * ridge ≤ N ridge . Therefore, applying Lemma B.1 with k 1 = k * , we have the following bound on the effective bias of SGD, Then by our assumption that we further have where in the second inequality we use the fact that k * ≤ k * ridge ≤ N ridge . Regarding the variance of SGD, applying Lemma B.1 with k 2 = k * ridge gives where the last inequality is due to the fact that λ tr(H). Combining the above upper bounds for the bias and variance of SGD, we have that the output of SGD, with sample size N sgd = N and learning rate γ = 1/ tr(H), satisfies where the last equality holds since we assume that w 2 H /σ 2 = Θ(1). Note that the R.H.S. of (B.1) is exactly the lower bound of the excess risk of ridge regression. Therefore, we can conclude that as long as N sgd = N , SGD with a tuned stepsize γ will be no worse than ridge regression for all λ (up to constant factors). This completes the proof.

C Proof of Theorem B.2
In this section we always make Assumption 5.1. The results and techniques are either explicitly or implicitly presented in [7,26]. For self-completeness, we provide a formal proof here.
• Let A := XX = d i=1 λ i z i z i ∈ R n×n . Let A := A + λ n I n = XX + λI n . • Let A k := X k:∞ X k:∞ = i≤k λ i z i z i ∈ R n×n . Let A k := A k + λI n = X k:∞ X k:∞ + λI n .
• Let A −j := i =j λ i z i z i ∈ R n×n . Let A −j := A −j + λI n .
• Let ρ k := • We use E X [·] and E [·] to denote the expectation with respect to the randomness of drawing X and the randomness of noise, respectively.
Under the above notations and from [7,26] RidgeBias := (w * ) Bw * , RidgeVariance := C . We next provide lower bounds for each terms respectively. Lemma C.1 (Variant of Lemma 10 in [7]). There are constants b, c ≥ 1 such that for every k ≥ 0, with probability at least 0.1, which completes the proof by letting b > 4c 2 and c ≥ 1