Year: 2021

Abstract:
This paper studies the Stochastic Gradient Descent (SGD) algorithm in kernel regression. The main finding is that SGD with moderate and annealing step size converges in the direction of the eigenvector that corresponds to the largest eigenvalue of the gram matrix. On the contrary, the Gradient Descent (GD) with a moderate or small step size converges along the direction that corresponds to the smallest eigenvalue. For a general squared risk minimization problem, we show that directional bias towards a larger eigenvalue of the Hessian (which is the gram matrix in our case) results in an estimator that is closer to the ground truth. Adopting this result to kernel regression, the directional bias helps the SGD estimator generalize better. This result gives one way to explain how noise helps in generalization when learning with a nontrivial step size, which may be useful for promoting further understanding of stochastic algorithms in deep learning. The correctness of our theory is supported by simulations and experiments of Neural Network on the FashionMNIST dataset.

heading: 1 INTRODUCTION
text: In this paper, we study the Stochastic Gradient Descent (SGD) algorithm in a nonparametric regression model. Among nonparametric models, one popular choice in both statistics and machine learning communities is the kernel model that is generated by a Reproducing Kernel Hilbert Space (RKHS). When fitting kernel models to the data, SGD is computationally efficient as compared to Gradient Descent (GD) (Ma et al., 2018). This motivates us to analyze the properties of SGD in the kernel model, especially for SGD with a nontrivial step size for a practical reason. In particular, we aim to provide a fundamental explanation of why SGD estimators generalize well.
Our work is inspired by Wu et al. (2021), which shows that directional bias has a significant impact on the generalization property in the linear regression model. We adopt a similar concept of the directional bias, but generalize them to the nonparametric model. Our result is a non-trivial extension of their approach, due to the difference in our problem setting and our SGD algorithm design. To the best of our knowledge, we are the first to show the directional bias phenomenon of SGD and analyze how it helps generalization in nonparametric regression.
Our contributions are two folded. First, we study the directional bias of (S)GD in a nonparametric regression model. On the one hand, nonparametric regression is well studied in both statistics and machine learning. On the other hand, the directional bias is a relatively new concept (Wu et al., 2021) of an algorithm that affects the statistics properties, and there is no thorough understanding of the directional bias of (S)GD algorithms for the nonparametric regression model. Note that our result is closely related to those in Belkin et al. (2018); Liang & Rakhlin (2020): they prove that SGD and GD algorithms both converge to the minimum norm interpolate, where the same properties are discovered for SGD and GD; whereas we investigate the solution paths before their convergence, and show that SGD and GD have different solution paths that lead to different properties. Our result helps to explain why the SGD generalizes better than GD.
Our second contribution is to unify the conditions to show the directional bias of (S)GD sequences in nonparametric models. The main condition is the diagonal dominant gram matrix, which covers a large class of kernel functions and allows us to study their properties. Moreover, our SGD is
different from those in Wu et al. (2021): they define SGD in epochs while we define SGD in steps. The fundamental difference in the SGD algorithm requires us to develop different techniques for analyzing the SGD sequence and showing its directional bias, which has not yet been covered in the current literature.
Main Theorems of this paper can be divided into two parts, briefly summarized as follows:
First is the directional bias of SGD. Theorem 5 shows that for a two-stage SGD with a moderate step size in the first stage and a small step size in the second stage, an early-stopped estimator has a directional bias towards the eigenvector that corresponds to the largest eigenvalue of the gram matrix. Later we refer to this direction as the direction towards the largest eigenvector to simplify the statement.
As a comparison, Theorem 7 shows that GD with both moderate and small step sizes has a directional bias towards the eigenvector that corresponds to the smallest eigenvalue of the gram matrix (denote it as the direction towards the smallest eigenvector). From which, we conclude that SGD and GD have different direction biases in kernel regression.
Second is the implication of directional bias. The implication is very useful since it quantifies the effect of the directional bias on the generalization error. Theorem 9 considers a general problem of quadratic loss. It shows that the estimator biased towards the largest eigenvector of the Hessian (which is the gram matrix in our nonparametric regression) can have the smallest parameter estimation error, when compared with other estimators of the same loss.
With this high-level idea of directional bias helps generalization, Theorem 11 compares the generalization error of SGD and GD in our problem setting. In particular, it upper bounds the generalization error of SGD and lower bounds the generalization error of GD. By directly comparing the error bounds, we guarantee that the generalization error of the SGD estimator is smaller than that of the GD estimator with high probability.
We also point out that our result might shed new light on deep learning (Belkin et al., 2018). By the state-of-the-art mathematical theory of Neural Networks (NN), kernel and/or nonparametric methods can approximate the functional space of neural networks, see for example the NTK theory (Jacot et al., 2018), and the Radon bounded variance space description for ReLU NN (Parhi & Nowak, 2021). Our technique might allow one to characterize the SGD solution path and show the generalization property in those problem settings.
Paper organization. The rest of the paper is as follows: In Section 2, we review some relevant literature; In Section 3, we give the formulation of the nonparametric regression and define the optimization problem. We also formalize the algorithm that is considered in this work and make assumptions to analyze the algorithms; In Section 4, we state our main theory on the directional bias of SGD/GD in nonparametric regression, where we include both the directional bias result and the implication of the directional bias for generalization. Experiments are conducted to support our theory; In Section 5, we discuss the finding in this paper, and propose some future research topic. All the proof, experiment details, and more experiments are deferred to the appendix due to page limits.

heading: 2 LITERATURE REVIEW
text: In this section, we review some relevant works. For better understanding, we split into two subsections: Subsection 2.1 reviews the background of RKHS; Subsection 2.2 presents the state-of-the-art technique for analyzing the directional bias of the (S)GD algorithm.

heading: 2.1 RKHS
text: Kernel methods are among the core algorithms in machine learning and statistics (Bartlett et al., 2021). As proposed by Wahba (1990), the kernel method and RKHS serve as a unified framework of a group of nonparametric models, which extends the spline method. Later, kernel models become an important component in nonparametric models. In machine learning, the kernel-based method is always referred to as the “kernel trick”. By lifting the x variable to a high dimensional space via the kernel method, we can explore possibly nonlinear relationships between variables. Moreover, to
play the kernel trick, one can directly calculate the kernel function using original features. This is computationally efficient since we avoid calculating high dimension or infinite dimension features. For applications of kernel method in machine learning, one can see kernel regression for image processing (Takeda et al., 2007), for text mining (Greene & Cunningham, 2006), and for tasks in bioinformatics (Saigo et al., 2004).
Regarding deep learning, the kernel method is also important because it has implications for deep learning models. On the one hand, the kernel methods have similar benign overfitting behavior to neural network due to the implicit regularization and/or implicit bias phenomenon that we will review in the next subsection (Belkin et al., 2018). On the other hand, the RKHS itself is closely related to Neural Networks via the Neural Tangent Kernel theory (Jacot et al., 2018). This all indicates that to understand deep learning, one should first study kernel methods.

heading: 2.2 DIRECTIONAL BIAS
text: This paper analyzes the directional bias of SGD for the nonparametric regression. Directional bias, also referred to as implicit bias, of an algorithm refers to that its solution path is biased towards a certain direction. It works as that the algorithm prefers some directions over the others even though they may have the same objective function value. Since the algorithm selects a direction by itself, instead of explicitly required by any constraint, people use the term “implicit”. It is worth noting that the implicit regularization is related to implicit bias. The implicit regularization refers to that the converged point of an algorithm is like a regularized estimator, even if the objective function is not explicitly regularized. One can also interpret implicit regularization as the “final result” of implicit bias. In the recent work by Derezinski et al. (2020), implicit regularization is used to develop an exact bound for double descent in linear regression. In this way, implicit regularization/bias serves as a way to explain some deep learning phenomenons that could not be addressed by the classical empirical risk minimization (ERM) framework. Therefore, it is important to study directional bias.
State-of-the-art study on the directional bias of first-order algorithms can be divided into two categories by the technique they use:
The first category is the (stochastic) gradient flow method, by taking an infinitesimal step size in (S)GD, the parameter dynamic follows a (stochastic) differential equation. Studying the solution path and the stationary point of the underlying differential equation helps to reveal the property of the parameter estimation. We list some works that use the first method to show the directional bias result of the (stochastic) gradient descent. Liu et al. (2018) analyze the Momentum SGD (MSGD) with infinitesimal step size, and show that the solution path escapes from the saddle for a nonconvex objective function. It is worth noting that in their case, the associated stochastic differential equation defines a complicated stochastic process, thus they replace it with an appropriate diffusion process, and the analysis is done based on such diffusion approximation. If one analyzes a stochastic gradient flow and finds it intractable, one may consider using the technique of diffusion approximation. Ali et al. (2020) shows the stochastic gradient flow for the linear regression problem minw ‖Xw−y‖22 has a solution path close to the solution path of Ridge regression; Blanc et al. (2020) shows the stochastic gradient flow for a general loss function has a solution path close to the solution path of gradient flow on the objective function plus some extra penalty terms, and they explicitly identify the penalty terms; Smith et al. (2021) go one more step from the infinitesimal step size to small step size, and characterize the effect of small step size as an extra penalty term in the gradient flow.
Another category is analyzing the discrete (S)GD sequence. This technique in general just requires a moderate step size such that the algorithm converges (or nearly converges), thus it is more meaningful from a practical perspective. We also find some directional bias work that is based on this technique. Vaskevicius et al. (2019); Zhao et al. (2019); Fan et al. (2021) analyze Hadamard reparameterized GD in sparse regression. They divide the true parameter into strong, weak, and 0 parts, and for each part, they carefully develop the stepwise error bound for each step of GD. They finally show that an early-stopped estimator along the solution path achieves the minimax optimal error rate for sparse regression, which indicates that the solution path is in the direction that biased towards a sparse solution. Recently, Wu et al. (2021) show that for overparameterized linear regression, SGD with moderate step size converges to the minimum norm interpolant in the direction that corresponds to the largest eigenvalue of the design matrix, while GD converges in the direction that corresponds to the smallest eigenvalue. For Neural Networks in the ‘lazy training’ regime, ? shows
that GD also converges in the direction of the smallest eigenvalue of the Neural Tangent Kernel. Their result further reveal the mechanism of the directional bias as: GD fits the direction of a larger eigenvalue faster at the beginning of the training, left the smaller eigenvalue direction unfitted; later the direction of smaller eigenvalue is fitted, resulting in that the estimator goes in this direction.

heading: 3 PROBLEM FORMULATION
text: We give our problem formulation in this section. In Subsection 3.1 we define the kernel regression model and objective function; in Subsection 3.2, we give the SGD and GD algorithms; in Subsection 3.3, we state our assumption for later analysis. Due to the page limit, details of the nonparametric regression, RKHS and justifications for the assumption are deferred to Appendix A and B.

heading: 3.1 KERNEL REGRESSION
text: Suppose we are given n data pairs {xi, yi}ni=1 generated from an unknown model y = f(x), where xi ∈ X ⊂ Rp and yi ∈ R. The goal is to estimate the unknown model f from the data. To achieve the goal, one way is to find an f that minimizes the empirical risk function
min f
1
n n∑ i=1 `(yi, f(xi)) (1)
where ` is the loss function. For the regression task, we use the squared loss `(y,x) = 12 (y−f(x)) 2.
One can see that problem (1) is not well-defined, as there are infinitely many solutions to ∀i : f(xi) = yi, and some of them do not generalize for a new test data. One way to fix it is to restrict f ∈ H and add regularization term in ‖f‖H to problem (1) for smoothness, where H is a RKHS with reproducing kernel K(·, ·) and ‖ · ‖H is the Hilbert norm. Adding these restrictions and applying Representer Theorem, problem (1) with the squared loss becomes
min α∈Rn
1
2n n∑ i=1 (yi −KTi α)2
= 1
2n ‖y −Kα‖22
(2)
where KTi is the ith row of K := K(X,X) = (K(xi,xj))i,j . For a parameter α, the corresponding estimator inH is f(·) = ∑n i=1 αiK(xi, ·) := αTK(·, X).
Now when K is invertible, it is trivial that any algorithm on objective function (2) (if it converges) converges at the unique minimal, that is, α̂ = K(X,X)−1y, result in the RKHS functional estimator
f̂(x) = K(x, X)TK(X,X)−1y (3)
where K(x, X)T = (K(x,x1), . . . ,K(x,xn)). Estimator (3) is the minimum norm interpolant as given by following problem:
arg min f∈H {‖f‖H : f(xi) = yi, i = 1, . . . , n}
And its property has been studied in Liang & Rakhlin (2020).
In this paper, we compare the convergence direction of SGD and GD to α̂. Specifically, we consider a two-stage SGD with a phase transition from a larger step size to a decreased step size. Note that this matches the training scheme people always use in practice for SGD algorithms: decreasing the step size after training for a few epochs. For that purpose, in the following sections, we define the one-step SGD/GD update and state our assumptions and notations for analysis.

heading: 3.2 ONE STEP SGD/GD UPDATE
text: In this paper, we consider the SGD algorithm as follows. For objective function (2), denote the parameter estimation at tth step as αt, then SGD update αt+1 as
αt+1 = αt − ηt(KTitαt − yit) ·Kit (4)
where it is uniformly random sampled from {1, . . . , n}.
The GD update αt+1 as
αt+1 = αt − ηt n KT (Kαt − y) = αt − ηt n K(Kαt − y) (5)

heading: 3.3 ASSUMPTIONS AND NOTATIONS
text: We state our assumption on the gram matrix in a unified format. Later we show in Appendix B that some popular kernel families satisfy our assumption. Assumption 1 (Diagonal Dominant gram matrix). Denote by K = K(X,X) the gram matrix, we assume that K is diagonal dominant. Specifically, suppose w.l.o.g. that K1,1 ≥ K2,2 ≥ . . . ≥ Kn,n > 0, then we have for a small value τ that
|Ki,j | ≤ τ Kn,n,∀i 6= j Remark 2. Diagonal dominant gram matrix is common in kernel learning. Mathematically, one can justify that a gram matrix is diagonal dominant by imposing proper assumptions on the kernel function K(·, ·) and the data distribution. The following proposition shows diagonal dominance for bilinear kernel. We can check for some other popular kernel to be diagonal dominant, which we defer to Appendix B due to the page limit. Remark 3. Think of the kernel function as the inner product of high-dimensional features, the resulting gram matrix is diagonal dominant when the high-dimension features are sparse. This happens for a lot of practical problems (Schölkopf et al., 2002; Weston et al., 2003), for example, when linear or string kernels are applied to text data (Greene & Cunningham, 2006), when domainspecific kernels are applied to image retrieval (Tao et al., 2004) and bioinformatics (Saigo et al., 2004), and when the Global Alignment kernel is applied to most datasets (Cuturi et al., 2007; Cuturi, 2011). Proposition 4 (Lemma 1 in Wu et al. (2021)). Consider the bilinear kernel K(x,x′) := 〈x,x′〉. Assume the data xi, i = 1, . . . , n are i.i.d. uniformly distributed on the unit sphere Sd−1, where d n. When d ≥ 4 log(2n2/δ) for some δ ∈ (0, 1). Then with probability at least 1− δ, we have
|Ki,j | = |〈xi,xj〉| < τ̃ := Õ( 1√ d ) Kn,n = 1,∀i 6= j.
It is meaningful to note that the diagonal dominance is undesired in classification and clustering tasks. It indicates that the data pieces are dissimilar to each other as measured by the kernel function, and thus generates very little information for classification/clustering. One may find a lot of works on solving the issue of diagonal dominance in these cases, for example, Greene & Cunningham (2006); Kandola et al. (2003). But for the regression task, the diagonal dominance, in other words, the dissimilarity of data points, may have benefits. One can find similar conditions such as Restricted Isometry Property and s−goodness that describes linearly dissimilar features in a huge regression literature as Candes & Tao (2007); Candès (2008); Chen & Donoho (1994). Such conditions are required for proving minimax optimality or exact recovery of a sparse signal in sparse settings. In our case, we adopt the dissimilarity concept and apply it to data points in high-dimensional nonlinear feature space. Later we will see that in the existence of diagonal dominance, the directional bias drives SGD to select a good solution that generalizes well among all solutions of the same level of empirical loss. In this way, our SGD estimator benefits from the diagonal dominance.
Notations. We use the following notations throughout the remaining of this work. For the gram matrix K, denote Ki,j be the element at ith row jth column of K. Denote λi = Ki,i = K(xi, xi), and assume w.l.o.g. that λ1 ≥ λ2 ≥ . . . ≥ λn. Denote the ith column of K as Ki, let K−1 = [K2, . . . ,Kn]. Assume K is full rank, denote P−1 the projection onto column space of K−1, and P1 = I−P−1. And denote γ1 ≥ . . . ≥ γn > 0 eigenvalues of K in non-increasing order.

heading: 4 MAIN RESULT
text: The main results are presented in two subsections: Subsection 4.1 states the different directional bias result of SGD and GD estimators; Subsection 4.2 shows that directional bias towards a certain
directional leads to good generalization performance, and further applies this result to show that SGD generalizes better than GD.

heading: 4.1 DIRECTIONAL BIAS
text: Since we assumed that K is full rank, then SGD and GD algorithm on objective function (2) converges to α̂ = K−1y (when they converge). We are interested in the direction at whichαt converges to α̂, i.e. the quantity bt := αt − α̂ With assumption 1 that the gram matrix is diagonal dominant, we prove that a two-stage SGD has bt converge in the direction of the largest eigenvector of K. Theorem 5 (Direction bias of SGD estimator). Assume Assumption 1 holds, run a two-stage SGD with a fixed step size for each stage: stage 1 with step size η1 for steps 1, . . . , k1, stage 2 with step size η2 for steps k1 + 1, . . . , k2, such that
2
λ21 − C1 √ nτ
< η1 < 2
λ22 + C2 √ nτ
η2 < 1
λ21 + C3 √ nτ
where C1, C2, C3 are constants that are specified in the Appendix E. For a small > 0 such that nτ < poly( ) there exists k1 = O(log 1 ) and k2 such that
(1− 2 )γ1 ≤ E[‖KbSGDk2 ‖2] E[‖bSGDk2 ‖2] ≤ γ1
That is, bSGDk2 is close to the direction of the largest eigenvector of K. Remark 6. One should assume τ in Assumption 1 to be small enough for to be very small if one would like the resulting estimator bSGDk2 to have the direction that corresponds to the largest eigenvalue of K. Later we will see that if one only wants different directional bias of SGD and GD estimators, a moderate is allowed and then the assumption on τ is not that strong.
The proof of Theorem 5 is in Appendix E. Next, we see that GD has bt converge in the direction of the smallest eigenvector of K, which contrasts with the directional bias of SGD. Theorem 7 (Direction bias of GD estimator). Assume Assumption 1 hold, run GD with a fixed step size:
η < n
(λ1 + nτ)2 ,
for a small ′ > 0, run k = O(log 1 ′ ) steps of GD, we have
γn ≤ ‖KbGDk ‖2 ‖bGDk ‖2 ≤ √ 1 + ′γn
That is, bt is close to the direction of the smallest eigenvector of K. Remark 8. The assumption (on τ ) is mild for differentiating the directional bias of SGD and GD. Comparing Theorem 5 and 7, we see that as long as γn < (1− 2 )γ1, by taking k large enough we always have
‖KbGDk ‖2 ‖bGDk ‖2 < E‖KbSGDk2 ‖2 E‖bSGDk2 ‖2
That is, one may expect bSGDk2 to be in the direction of larger eigenvalue compared with b GD k . In the following subsection, we see that the directional bias towards a larger eigenvalue of the kernel is good for generalization, which leads to our title that directional bias helps SGD to generalize in kernel regression.
The proof of Theorem 7 is in Appendix F. Although there is assumption 1 in Theorem 7, it is just used to bound the step size so that GD converges; the diagonal dominant structure of K is not required for the directional bias for GD to hold. Moreover, the choice of ′ is independent of the assumption on τ , then for an arbitrarily small ′ > 0, we can always run GD long enough such that the theorem holds and the estimator bGDk is arbitrarily close to the smallest eigenvector.

heading: 4.2 EFFECT OF DIRECTIONAL BIAS
text: In this subsection, the estimator that has a directional bias towards the largest eigenvalue of the Hessian is shown to give the best parameter estimation error among all estimators that have the same squared in-sample loss, see Theorem 9. Later we define a realizable problem setting of kernel regression where the generalization error depends on a term similar to the parameter estimation error, and in this way, the directional bias helps SGD to generalize.
Theorem 9. Consider approximately minimizing the quadratic loss
L(w) = ‖Aw − y‖22 Assume there is a ground truth w∗ such that y = Aw∗, for a fixed level of the quadratic loss, the parameter estimation error ‖w −w∗‖22 has a lower bound
∀w ∈ {w : L(w) = a} : ‖w −w∗‖22 ≥ a
‖ATA‖2 Moreover, the equality is obtained when w − w∗ is in the direction of the eigenvector that corresponds to the largest eigenvalue of ATA.
Remark 10. Theorem 9 implies that the directional bias towards the largest eigenvalue is good for parameter estimation. As discussed in Remark 8, the SGD estimator is biased towards a larger eigenvalue compared to the GD estimator, then by Theorem 9 the SGD estimator better estimates the true parameter and thus generalizes better. We formalize this statement in the following paragraphs.
The proof of Theorem 9 is in Appendix G.1.
Suppose ∃f∗ ∈ H such that y = f∗(x). Consider the generalization error LD(f) := ‖f − f∗‖2H, for an algorithm output falg, we decompose its generalization error as:
LD(f alg)− inf
f∈H LD(f) = LD(f alg)− inf f∈Hs LD(f)︸ ︷︷ ︸ :=∆(falg), estimation error + inf f∈Hs LD(f)− inf f∈H LD(f)︸ ︷︷ ︸ approximation error
whereHs is the hypothesis class that the output of the algorithm is restricted to. By formulation (2), we have our hypothesis class as
Hs = {f ∈ H : f = αTK(·, X),α ∈ Rn}
We define the a−level set of training loss:
νa = {f ∈ Hs : f = αTK(·, X), 1
2n ‖Kα− y‖22 = a},
denote ∆∗a := inff∈νa ∆(f).
Note that the approximation error can not be improved by choice of algorithm unless we change the hypothesis class, which is, changing the problem formulation in our case. So we just minimize the estimation error for estimators that are in the a−level set. As shown in Appendix G.2, one can check the estimation error is given by
f ∈ Hs : ∆(f) = bTKb
where b = α − α̂. By similar reasoning as Theorem 9, the estimation error is minimized when b is in the direction of the largest eigenvalue of K, so the directional bias towards a larger eigenvalue helps to generalize in kernel regression. We formalize the statement for comparing the estimation error of SGD and GD in the following theorem.
Theorem 11 (Generalization performance). Follow Theorems 5 and 7, we have the following:
• The output of SGD has E[∆1/2(fSGD)] ≤ (1 + 4 )(∆∗a)1/2, where a is such that E[‖KαSGD − y‖2]2 = 2na and could be any positive small constant;
• The output of GD has ∆(fGD) ≥M∆∗a, where a is the training loss of GD estimator, and M = γ1γn (1− ′) > 1 is a large constant.
‖b‖22 (same as Theorem 5 and 7). The SGD indeed
converges in the direction of a larger RQ, which matches our Theorems 5 and 7. In the third plot we show the prediction error of the solution paths, and the SGD does have lower prediction error than GD, even GD has smaller training loss than SGD. This supports Theorem 11.
Remark 12. One read from the theorem that the SGD estimator is (8 + 16 2)−optimum, while GD estimator is (M − 1)−sub-optimum. Combine with Theorem 7 that ′ k→∞−→ 0, we can take in Theorem 5 such that (1 + 4 )2 < γ1/γn to have ∆(fSGD) < ∆(fGD) with high probability. This finishes our claim that the SGD estimator generalize better than the GD estimator.
The detailed proof of Theorem 11 is left to Appendix G.2.
Numeric Study. Figure 1 shows the simulation results of kernel regression, Figure 2 shows the results of a small ResNet-like Neural Network on FashionMNIST data (Xiao et al., 2017). Figure 1 and Figure 2a supports the directional bias results in Theorems 5 and 7, and Figure 2b validates Theorem 11. For details of the experiments and more experiments, see Appendix H. Remark 13. The purpose of experiment using a Neural Network (Figure 2) is as following: first, the Neural Network results support our finding on kernel regression, since Neural Network is related to kernel regression through NTK theory (Jacot et al., 2018); second, our experiment indicates that our result may be empirically true for the more general deep learning framework (Belkin et al., 2018), since this experiment uses a complicated network that may not be simply explained by the kernel method.

heading: 5 DISCUSSION AND FURTHER WORK
text: Our work takes one more step towards understanding the directional bias of SGD in kernel learning. Here we discuss some implications of our results to deep learning.
Implication for SGD scheme: Our result shows the directional bias applies to SGD with annealing step size. Specifically, the first stage of SGD with moderate step size should run long enough, then in the second stage by decreasing step size we have the directional bias towards the largest eigenvalue of the Hessian, which helps in benign overfitting. This explains a technique for tuning the learning rate that people use in practice: start with a large step size, run long enough until the error plateaus, then decrease the step size (He et al., 2016). Although this technique is always used to speed convergence, we show that it also helps in benign overfitting, which becomes even better.
Implication for deep learning: Our assumption for analysis implies certain structures for deep learning models. Per our examples in Appendix B and our discussion in Remark 3, our assumption holds when the feature space is high dimensional and/or when features are possibly sparse. This matches the deep learning scenario where we have a highly overparameterized model and when the trained parameter estimator becomes sparse. Besides, considering that some deep learning tasks can
be approximated by kernel learning (Jacot et al., 2018), our results help in explaining why the SGD estimator can benign overfitting in an overparameterized deep learning.
Just as stated in Belkin et al. (2018), to understand deep learning one needs to understand kernel learning. This work takes a step in understanding kernel learning, and we expect more steps that go beyond this work towards understanding deep learning, possibly for some complicated structure that could not be approximated by kernel learning.
Reproducibility Statement: For all theoretical results presented in this paper, we carefully state and justify the assumption, we also include the proof in Appendix. For all experiments, we state the implementation details in Appendix, and we include the necessary code and data for reproducing our result in the supplementary material.

heading: A BACKGROUND ON RKHS
text: This section details background on RKHS in two subsections. The first subsection includes notations, theorems, and an example of RKHS, the second section reduces the kernel regression in RKHS from infinite dimension to finite dimension, which gives our objective function (2) .
A.1 NONPARAMETRIC MODEL IN RKHS
In this subsection, we give the definition and notations for our model in RKHS, and its associated norms, basis, etc. The definitions are similar to those in Raskutti et al. (2012).
Given n data pairs {xi, yi}ni=1, where xi ∈ X ⊂ Rp and yi ∈ R, assume that yis are associated with xis through f(xi), where f(·) is some unknown function in the reproducing kernel Hilbert space (RKHS) of functions X → R, our goal is to estimate the function f(·) from the data.
Denote the RKHS where f lives as H, with reproducing kernel K : X × X → R+ (which is known to us). And we associate the functions in H with probability measure Q, assume w.l.o.g. that ∫ Rp f(a)dQ(a) = 0. By Mercer’s theorem, K has eigen-expansion:
K(a, b) = ∞∑ j=1 γjφj(a)φj(b)
Where {φj}∞j=1 are orthonormal basis in L2(Q), w.r.t. the usual inner product in L2(Q) as 〈g(·), h(·)〉L2(Q) = ∫ X g(a)h(a)dQ(a)
Now for any f ∈ H, we can expand f(·) = ∑∞ j=1 cjφj(·), where cj = 〈f(·), φj(·)〉L2(Q). And for
f(·) = ∑∞ j=1 cjφj(·), g(·) = ∑∞ j=1 c ′ jφj(·), by Parseval’s theorem
〈f(·), g(·)〉L2(Q) = ∞∑ j=1 cjc ′ j
And we have another inner product that is defined for RKHSH as
〈f(·), g(·)〉H = ∞∑ j=1 cjc ′ j γj
The reproducing property of RKHS says that ∀f ∈ H, we have 〈f(·),K(·,x)〉H = f(x)
Cubic Splines Formulate a RKHS. We go over an example of RKHS for better understanding. Consider the cubic spline of one dimension, we can show that the space of cubic splines is a RKHS. One can also find the cubic spline example in Hazimeh et al. (2021). For more details on the relationship between polynomial smoothing splines and RKHS, one can check Section 1.2 of Wahba (1990) .
Assume w.l.o.g. that xi ∈ X = [0, 1] ⊂ R. The cubic spline f on X is continuous, has a continuous first-order derivative and square integrable second order derivative. By Taylor’s theorem with remainder, we have
f(t) = f(0) + tf ′(0) + ∫ t 0 (t− u)f ′′(u)du
= f(0) + tf ′(0) + ∫ 1 0 (t− u)+f ′′(u)du
where (t − u)+ = max{0, t − u}. Let B be the set of cubic splines f on [0, 1] that satisfies the boundary condition f(0) = f ′(0) = 0, then for f ∈ B
f(t) = ∫ 1 0 (t− u)+f ′′(u)du
Let G(t, u) = (t− u)+, then we claim that B is RKHS with reproducing kernel
K(s, t) = ∫ 1 0 G(s, u)G(t, u)du
and inner product
〈f, g〉B = ∫ 1
0
f ′′(u)g′′(u)du
as one can check the reproducing property
〈f(·),K(·, t)〉B = ∫ 1
0
∂2K(u, t)
∂u2 f ′′(u)du
= ∫ 1 0 (t− u)+f ′′(u)du = f(t)
A.2 OPTIMIZATION PROBLEM CONSIDERED
This subsection gives problem formulation of kernel regression. Given data pairs {xi, yi}ni=1 and RKHS H, consider a loss function ` which is selected according to how y is connected with f(x), we may estimate the model by
min f∈H
1
n n∑ i=1 `(yi, f(xi)) (6)
= min cj
1
n n∑ i=1 `(yi, ∞∑ j=1 cjφj(xi))
Example for ` includes
• Squared error loss `(y, f) = (y − f)2, which is usually used in regression; • 0-1 loss `(y, f) = 1(y ∗ f > 0), for binary classification; • Logistic loss `(y, f) = log(1 + exp(−y ∗ f)), also a loss function for classification, can
be considered as a surrogate function of 0-1 loss, and is the same as negative log likelihood function in logistic regression.
Let us come back to the nonparametric model part, to control the model smoothness, the usual practice is to add a penalty to objective (6), result in
min f∈H n∑ i=1 `(yi, f(xi)) + λpen(f)
A popular choice of pen(f) is ‖f‖2H, or any strictly increasing function of ‖f‖2H. Such method is explicitly controlling the model smoothness, and by Representer Theorem, it has solution of the form
f(·) = n∑ i=1 αiK(·,xi) (7)
Plug equation (7) into objective (6), we have the problem becomes
min αi′
1
n n∑ i=1 `(yi, n∑ i′=1 αi′K(xi,xi′))
Which gives the formulation (2) under loss function `(y, f(x)) = (y − f(x))2/2.

heading: B DIAGONAL DOMINANCE OF SOME POPULAR KERNELS
text: In this section, we justify Assumption 1 by figuring out a problem setting where some popular kernels give a diagonal dominant gram matrix. For simplicity, we assume the following data distribution throughout this section:
xi ∈ Rd, i = 1, . . . , n, are normalized such that ‖xi‖22 = 1; (A.1) The direction of xis are i.i.d. uniformly distributed on the unit sphere Sd−1; (A.2) d n (overparameterized setting). (A.3)
Given assumption set (A), we can bound the inner product of data 〈xi,xj〉 with high probability as follows: Lemma 14 (Lemma 1 in Wu et al. (2021)). Under assumption set (A), let d ≥ 4 log(2n2/δ) for some δ ∈ (0, 1). Then with probability at least 1− δ, we have
|〈xi,xj〉| < τ̃ := Õ( 1√ d ),∀i 6= j
Proof. See proof of Lemma 1 in Wu et al. (2021).
The bound on the inner product 〈xi,xj〉 induces bound on K(xi,xj) for some popular kernels. We show the diagonal dominance for two groups of kernels in the following propositions, and list some examples for kernels in each group. Proposition 15 (Inner product kernel). The inner product kernel is defined as a smooth transformation of inner product. We can write it as:
K(xi,xj) = g(〈xi,xj〉)
Assume assumptions (A) hold, and assume the function g : [−1, 1]→ R satisfies:
g is convex; (B.1) g is L−smooth, that is,∇g is L−Lipschitz continuous; (B.2) |g(0)| ≤ cτ̃ for a constant c, g′(0) ≥ 0. (B.3)
we will have with probability 1− δ
|Ki,j | ≤ (c+ g′(0))τ̃ + L
2 τ̃2 for i 6= j (10)
where δ and τ̃ the same as in Lemma 14.When g′(0)τ̃+ L2 τ̃ 2 g(1) for a small enough τ̃ , the gram matrix is diagonal dominant.
Proof. We have the following with probability at least 1 − δ by Lemma 14. For any off-diagonal elements of K:
Ki,j = g(〈xi,xj〉) ≥ g(0) + g′(0)〈xi,xj〉 ≥ −(g′(0) + c)τ̃
and
Ki,j = g(〈xi,xj〉)
≤ g(0) + g′(0)〈xi,xj〉+ L
2 〈xi,xj〉2
≤ (c+ g′(0))τ̃ + L 2 τ̃2
Thus |Ki,j | ≤ (c+ g′(0))τ̃ + L2 τ̃ 2.
Remark 16. We list some examples of inner product kernels that give diagonal dominant kernel matrices:
• Bilinear Kernel: K(x,x′) = 〈x,x′〉, then
|K(xi,xj)| ≤ τ̃ K(xn,xn) = 1.
• Polynomial Kernel: K(x,x′) = (〈x,x′〉 + c)m for m ∈ N and c ∼ O(τ̃), then by Proposition 15
|K(xi,xj)| ≤ (1 +m)τ̃ + m ∗ exp((m− 1)τ̃)
2 τ̃2
when (1 +m)τ̃ + m∗exp((m−1)τ̃)2 τ̃ 2 (1 + c)m, we have diagonal dominant gram matrix.
• Hyperbolic Tangent Kernel (Sigmoid Kernel): K(x,x′) = tanh(α〈x,x′〉 + c), where α > 0, c ≥ 0. Note that Hyperbolic Tangent Kernel does not satisfy all the assumptions in Proposition 15, one can still calculate
|K(xi,xj)| ≤ tanh(ατ̃ + c)
and K(xk,xk) = tanh(α+ c)
When tanh(ατ̃ + c) tanh(α+ c) (which is the case when α is large, and c, τ̃ are small enough), we have |K(xi,xj)| K(xn,xn) and the gram matrix is diagonal dominant.
Proposition 17 (Radial Basis Function (RBF) kernel). Radial Basis Function kernel depends on two data points through their distance, which is of following form
K(xi,xj) = exp(−γ‖xi − xj‖22), γ > 0
Assume assumptions (A) hold, when γ = −c0 log(τ̃) for a constant c0, we have with probability 1− δ
|Ki,j | ≤ τ̃2c0(1−τ̃) Kn,n = 1, for i 6= j
where δ and τ̃ the same as in Lemma 14. That is, the Gram matrix is diagonal dominant.
Proof. Bound off-diagonal terms of K by Lemma 14:
Ki,j = exp(−γ‖xi − xj‖22) ≤ exp(2γτ̃ − 2γ) = τ̃2c0(1−τ̃)
Remark 18. We note some popular kernels that are related to Radial Basis Function kernel, and show that they lead to diagonal dominance:
• Gaussian Kernel: K(x,x′) = exp(−‖x−x ′‖22
2σ2 ). One can see that Gaussian Kernel is reparameterizing RBF Kernel by γ = 1/(2σ2). Thus Gaussian gram matrix is diagonal dominant when σ2 ∼ O(− 1log(τ̃) ).
• Laplace Kernel: K(x,x′) = exp(−‖x−x ′‖2
σ ) for σ > 0. The Laplace Kernel is very similar to Gaussian Kernel, and one can check by similar steps that when σ ∼ O(− 1log(τ̃) ), Laplace gram matrix is diagonal dominant.

heading: C LEMMAS
text: This section includes two useful lemmas for characterizing the eigenvalues of a symmetric matrix. Lemma 19 (Gershgorin circle theorem, restated for symmetric matrix). Let A ∈ Rn×n be a symmetric matrix. Let Aij be the entry in the i−th row and the j−th column. Let
Ri(A) := ∑ j 6=i |Aij |, i = 1, . . . , n
Consider n Gershgorin discs
Di(A) := {z ∈ R, |z −Aii| ≤ Ri(A)}, i = 1, . . . , n
The eigenvalues of A are in the union of Gershgorin discs
G(A) := ∪ni=1Di(A)
Furthermore, if the union of k of the n discs that comprise G(A) forms a set Gk(A) that is disjoint from the remaining n−k discs, then Gk(A) contains exactly k eigenvalues of A, counted according to their algebraic multiplicities.
Proof. See Horn & Johnson (2012), Chap 6.1, Theorem 6.1.1.
Lemma 20 (Cauchy interlacing theorem, restated for symmetric matrix). Let B ∈ Rm×m be a symmetric matrix, let y ∈ Rn and a ∈ R, and let A = [ B y yT a ] . Then
λ1(A) ≥ λ1(B) ≥ λ2(A) ≥ . . . ≥ λm(A) ≥ λm(B) ≥ λm+1(A).
Proof. See Horn & Johnson (2012), Chap 4.3, Theorem 4.3.17.

heading: D SPECTRUM OF GRAM MATRIX
text: This section analyzes the eigen structure of the gram matrix.
Lemma 21 (Characterizing K2). Under Assumption 1, we have
〈Ki,Ki〉 ∈ [λ2i , λ2i + (n− 1)τ2] (11) |〈Ki,Kj〉| ≤ [2λ1 + (n− 2)τ ]τ, i 6= j (12)
Proof. For 〈Ki,Ki〉
〈Ki,Ki〉 = K2i,i + ∑ l 6=i K2l,i
∈ [λ2i , λ2i + (n− 1)τ2]
And for 〈Ki,Kj〉, i 6= j
|〈Ki,Kj〉| = | n∑ l=1 Kl,iKl,j |
= |Ki,iKi,j +Kj,iKj,j + ∑ l 6=i,j Kl,iKl,j |
≤ |Ki,iKi,j |+ |Kj,iKj,j |+ ∑ l 6=i,j |Kl,iKl,j |
≤ [λi + λj ]τ + (n− 2)τ2
≤ [2λ1 + (n− 2)τ ]τ
Lemma 22 (Eigenvalue of K). Under Assumption 1, we have
γ1 ≤ λ1 + nτ (13) γn ≥ λn − nτ (14)
If we further assume λj + nτ < λj−1 − nτ , we will have
γj−1 ≥ λj−1 − nτ > λj + nτ ≥ γj .
Proof. Use Gershgorin circle theorem, calculate Ri(K) = ∑ j 6=i |Ki,j | ≤ nτ
then
Di(K) ⊂ [λi − nτ, λi + nτ ]. By Gershgorin circle theorem, the lemma claim holds.
Lemma 23 (Characterize P1K and P−1K). Recall our definition: P−1 is the projection on column space of K−1 = [K2,K3, . . . ,Kn], and P1 = I − P−1. We claim the following hold
P1K = [P1K1,0, . . . ,0] (15) P−1K = [P−1K1,K2, . . . ,Kn] (16)
Assume τ is small enough that nτ ≤ O(1), λn−nτ ≥ c1 > 0 and λ1 +nτ ≤ c2, let c3 := c2c21 , then we have the following:
‖P−1K1‖2 ∈ [ 0, c3(2λ1 + (n− 2)τ) √ nτ ]
(17) ‖P1K1‖2 ∈ [√ λ21 − c23[2λ1 + (n− 2)τ ]2nτ2, λ1 + √ nτ ] . (18)
Proof. For i 6= 1, we calculate P−1Ki = Ki
P1Ki = Ki − P−1Ki = 0 thus we have equations (15) and (16).
For ‖P−1K1‖2: ‖P−1K1‖2
=‖K−1(KT−1K−1)−1KT−1K1‖2 ≤‖K−1(KT−1K−1)−1‖2‖KT−1K1‖2
where
‖KT−1K1‖22
= n∑ i=2 (KTi K1) 2
(12) ≤ (n− 1)[2λ1 + (n− 2)τ ]2τ2
≤[2λ1 + (n− 2)τ ]2nτ2
and KT−1K−1 has all eigenvalues in [γ 2 n, γ 2 1 ] by Cauchy interlacing theorem (Lemma 20), that is, all singular values of K−1 are in [c1, c2] by our assumption. Then
‖K−1(KT−1K−1)−1‖2 ≤ c2 c21 := c3
So we have
‖P−1K1‖2 ≤ ‖K−1(KT−1K−1)−1‖2‖KT−1K1‖2 ≤ c3[2λ1 + (n− 2)τ ] √ nτ.
For ‖P1K1‖2: ‖P1K1‖2 ≤ ‖K1‖2 ≤(λ21 + (n− 1)τ2).5
≤λ1 + √ nτ
and
‖P1K1‖22 =‖K1‖22 − ‖P−1K1‖22 ≥λ21 − c23[2λ1 + (n− 2)τ ]2nτ2.
Lemma 24 (Spectrum of H−1 := P−1KKTP−1). Assume
c23[2λ1 + (n− 2)τ ]2nτ2 + 2[2λ1 + (n− 2)τ ]nτ ≤ λ2n We have the following:
• 0 is an eigenvalue of H−1, corresponding eigenspace is the column space of P1;
• Restricted to the column space of P−1, the eigenvalues of H−1 are all in the interval:( λ2n − [2λ1 + (n− 2)τ ]nτ, λ22 + [2λ1 + (n− 1)τ ]nτ ) .
Proof. The first claim is by construction of P1 and P−1.
For the second claim, note that H−1 has the same eigenvalues as
H ′−1 = (P−1K) TP−1K
Now the diagonal entries of H ′−1 are:
(H ′−1)ii = ‖P−1Ki‖22 = { ‖P−1K1‖22 ≤ c23[2λ1 + (n− 2)τ ]2nτ2 , i = 1 ‖Ki‖22 ∈ [λ2i , λ2i + (n− 1)τ2] , i 6= 1
And the off-diagonal entries of H ′−1 are:
|(H ′−1)ij | = |〈P−1Ki, P−1Kj〉| = |〈Ki,Kj〉| ≤ [2λ1 + (n− 2)τ ]τ
To use Gershgorin circle theorem, calculate
Ri(H ′ −1) = ∑ j 6=i |(H ′−1)ij | < [2λ1 + (n− 2)τ ]nτ
Thus the Gershgorin discs:
D1(H ′ −1) ∈ (‖P−1K1‖22 − [2λ1 + (n− 2)τ ]nτ, ‖P−1K1‖22 + [2λ1 + (n− 2)τ ]nτ) Di(H ′ −1) ∈ (‖Ki‖22 − [2λ1 + (n− 2)τ ]nτ, ‖Ki‖22 + [2λ1 + (n− 2)τ ]nτ)
when c23[2λ1 +(n−2)τ ]2nτ2 +[2λ1 +(n−2)τ ]nτ ≤ λ2n− [2λ1 +(n−2)τ ]nτ , the first Gershgorin discs does not intersect with the others, so we have n− 1 nonzero eigenvalues in
∪ni=2Di(H ′−1) ⊂ ( λ2n − [2λ1 + (n− 2)τ ]nτ, λ22 + [2λ1 + (n− 1)τ ]nτ ) .

heading: E DIRECTIONAL BIAS OF SGD WITH MODERATE STEP SIZE
text: This section gives formal proof of Theorem 5 and specifies the constants. The proof is done in four steps: Lemma 25 analyzes one update of SGD; Lemma 26 uses Lemma 25 to bound the first stage updates of SGD with moderate step size; Lemma 27 again uses Lemma 25, and bounds the second stage updates of SGD with small step size; finally, Theorem 28 combines Lemma 26 and Lemma 27 to formalize the directional bias of SGD, it is the same as Theorem 5, but restated using the constants defined therein.
Lemma 25 (One step update of SGD). Under Assumption 1, denote At := E[‖P1bt‖2], Bt := E[‖P−1bt‖2], fix a constant c4 ≥ (λ1 + √ nτ)(2λ1 + (n− 2)τ)c3, then we have:
At+1 ≤ q1(η)At + ξ(η)Bt (19) At+1 ≥ q1(η)At − ξ(η)Bt (20) Bt+1 ≤ q−1(η)Bt + ξ(η)At (21)
where
q1(η) = n− 1 n + 1 n |1− η‖P1K1‖22|
q−1(η) = √ 1 + ‖KP−1bt‖22 n‖P−1bt‖22 [η2(λ22 + (n− 1)τ2)− 2η]
ξ(η) = c4ηn −1/2τ.
Proof. One step of SGD update is: bt+1 = bt − ηKiKTi bt = [I − ηKiKTi ]bt where i is uniformly random sample from [1, . . . , n].
For inequalities (19) and (20), check P1bt+1 = P1[I − ηKiKTi ]bt
= P1bt − ηP1KiKTi (P1 + P−1)bt = [I − ηP1KiKTi P1]P1bt − η[P1KiKTi P−1]P−1bt
where P1Ki and P1bt are in the same 1 dimensional linear space, thus P1KiK T i P1P1bt
=‖P1Ki‖2‖P1bt‖2sign(〈P1Ki, P1bt〉)P1Ki =‖P1Ki‖22P1bt
⇒ [I − ηP1KiKTi P1]P1bt = [1− η‖P1Ki‖22]P1bt and
‖[P1KiKTi P−1]P−1bt‖2 ≤‖P1Ki‖2‖P−1Ki‖2‖P−1bt‖2.
Then E[‖P1bt+1‖2|bt] ≤ E[|1− η‖P1Ki‖22|]‖P1bt‖2 + ηE[‖P1Ki‖2‖P−1Ki‖2]‖P−1bt‖2 (22) E[‖P1bt+1‖2|bt] ≥ E[|1− η‖P1Ki‖22|]‖P1bt‖2 − ηE[‖P1Ki‖2‖P−1Ki‖2]‖P−1bt‖2 (23) where E[|1− η‖P1Ki‖22|]
= 1
n n∑ i=1 |1− η‖P1Ki‖22|
= n− 1 n + 1 n |1− η‖P1K1‖22|
:=q1(η)
and ηE[‖P1Ki‖2‖P−1Ki‖2]
=η 1
n n∑ i=1 ‖P1Ki‖2‖P−1Ki‖2
= η
n ‖P1K1‖2‖P−1K1‖2
≤ η n (λ1 + √ nτ)c3(2λ1 + (n− 2)τ) √ nτ ≤ η n c4 √ nτ := ξ(η) (24)
where the first inequality by upper bounds (17) and (18), second inequality by nτ ≤ O(1). Plug the term (24) into inequalities (22) and (23), take expectation on both sides, we get claims (19) and (20).
For inequality (21), check
P−1bt+1 = P−1[I − ηKiKTi ]bt = [I − ηP−1KiKTi P−1]P−1bt − η[P−1KiKTi P1]P1bt
Then we have
E[‖P−1bt+1‖2|bt]
≤ 1 n n∑ i=1 ‖[I − ηP−1KiKTi P−1]P−1bt‖2 + ηE[‖P−1Ki‖2‖P1Ki‖2]‖P1bt‖2
(24) ≤ 1
n n∑ i=1 ‖[I − ηP−1KiKTi P−1]P−1bt‖2 + ξ(η)‖P1bt‖2
where
1
n n∑ i=1 ‖[I − ηP−1KiKTi P−1]P−1bt‖2
= 1
n n∑ i=1 √ ‖[I − ηP−1KiKTi P−1]P−1bt‖22
= 1
n n∑ i=1 √ ‖P−1bt‖22 + η2‖P−1KiKTi P−1P−1bt‖22 − 2η〈P−1bt, P−1KiKTi P−1P−1bt〉
= 1
n n∑ i=1 √ ‖P−1bt‖22 + η2(KTi P−1P−1bt)2‖P−1Ki‖22 − 2η(KTi P−1P−1bt)2
= 1
n n∑ i=1
√ 1 + (KTi P−1P−1bt) 2
‖P−1bt‖22 (η2‖P−1Ki‖22 − 2η)‖P−1bt‖2
≤ √√√√1 + 1 n n∑ i=1 (KTi P−1P−1bt) 2 ‖P−1bt‖22 (η2‖P−1Ki‖22 − 2η)‖P−1bt‖2
where the last inequality from Jensen’s inequality. Now the term
1
n n∑ i=1 (KTi P−1P−1bt) 2 ‖P−1bt‖22 (η2‖P−1Ki‖22 − 2η)
(11) ≤ 1 n n∑ i=1 (KTi P−1P−1bt) 2 ‖P−1bt‖22 [ η2(λ22 + (n− 1)τ2)− 2η ] = ‖KP−1bt‖22 n‖P−1bt‖22 [ η2(λ22 + (n− 1)τ2)− 2η
] Let
q−1(η) := √ 1 + ‖KP−1bt‖22 n‖P−1bt‖22 [η2(λ22 + (n− 1)τ2)− 2η]
combine all three inequalities above, take the expectation w.r.t. bt, we have claim (21).
Lemma 26 (Long run behavior of SGD with moderate step size). Assume b0 is away from 0, λ2n > (2λ1 + (n− 2)τ)nτ + c4 √ nτ , λ22 + c6 √ nτ < λ21 − c5 √ nτ where c5, c6 are constants such that
c5 ≥ c23[2λ1 + (n− 2)τ ]2 √ nτ + c4
c6 ≥ √ nτ − c24n−.5τ/[λ2n − (2λ1 + (n− 2)τ)nτ ] + λ22c4/[λ2n − [2λ1 + (n− 2)τ ]nτ ]
1− c4 √ nτ/[λ2n − (2λ1 + (n− 2)τ)nτ ]
Consider first k1 steps of SGD updates with step size η:
2
λ21 − c5 √ nτ
< η < 2
λ22 + c6 √ nτ
Fix a β0 ≤ A0, then for 0 < < 1 and 0 < β < β0 such that √ nτ ≤ poly( β), there exists k1 = O(log 1 β ) satisfying:
• Bk1 ≤ β
• Ak1 ≤ ‖b0‖2 ∗ ρ k1 1 + β/2 for some ρ1 > 1
• Ak > β0 for k = 0, . . . , k1.
Proof. For this choice of η, denote q1 = q1(η), q−1 = q−1(η), ξ = ξ(η). By Lemma 21, we have
Ak ≥ q1Ak−1 − ξBk−1[ Ak Bk ] ≤ [ q1 ξ ξ q−1 ] [ Ak−1 Bk−1 ] Decompose the coefficient matrix as[
q1 ξ ξ q−1
] = [ cos θ − sin θ sin θ cos θ ] [ ρ1 0 0 ρ−1 ] [ cos θ sin θ − sin θ cos θ ] Assume w.l.o.g. that sin θ ≥ 0 ( since otherwise we can take θ → θ + π), then we have[
Ak Bk ] ≤ [ q1 ξ ξ q−1 ]k [ A0 B0 ] = [ cos θ − sin θ sin θ cos θ ] [ ρk1 0 0 ρk−1 ] [ cos θ sin θ − sin θ cos θ ] [ A0 B0
] = [ A0(ρ k 1 cos 2 θ + ρk−1 sin 2 θ) +B0(ρ k 1 cos θ sin θ − ρk−1 cos θ sin θ)
B0(ρ k −1 cos 2 θ + ρk1 sin 2 θ) +A0(ρ k 1 cos θ sin θ − ρk−1 cos θ sin θ) ] = [ A0ρ k 1 + (ρ k 1 − ρk−1) sin θ(B0 cos θ −A0 sin θ)
B0ρ k −1 + (ρ k 1 − ρk−1) sin θ(B0 sin θ +A0 cos θ) ] ≤ [ A0ρ k 1 + |ρk1 − ρk−1| sin θ √ B20 +A 2 0
B0ρ k −1 + |ρk1 − ρk−1| sin θ √ B20 +A 2 0 ] = [ A0ρ k 1 + |ρk1 − ρk−1| sin θ‖b0‖2
B0ρ k −1 + |ρk1 − ρk−1| sin θ‖b0‖2 ] We claim the following holds:
0 < ρ−1 < 1 < ρ1 ≤ q1 + ξ (25a) ρk1−1‖b0‖2 ≤ β/2 (25b) ρk11 ‖b0‖2 sin θ ≤ β/2 (25c) (B0 + β0/2)ξ < (q1 − 1)β0 (25d)
which we check later. Using inequalities (25), we can upper bound Bk1 as
Bk1 ≤ B0ρ k1 −1 + (ρ k1 1 − ρ k1 −1) sin θ‖b0‖2
≤ ‖b0‖2ρk1−1 + ρk11 sin θ‖b0‖2 (25b),(25c) ≤ β
In addition, for k = 0, . . . , k1

heading: Bk ≤ B0ρk−1 + (ρk1 − ρk−1) sin θ‖b0‖2
text: ≤ B0 + ρk11 sin θ‖b0‖2 (25c) ≤ B0 + β/2
We now lower bound Ak by mathematical induction. We have A0 ≥ β0, assume Ak−1 > β0, then
Ak ≥ q1Ak−1 − ξBk−1 ≥ q1β0 − ξ(B0 + β/2) (25d) > q1β0 − (q1 − 1)β0 = β0
For upper bound Ak1 , check
Ak1 ≤ A0ρ k1 1 + (ρ k1 1 − ρ k1 −1) sin θ‖b0‖2
≤ ‖b0‖2ρk11 + ρ k1 1 sin θ‖b0‖2
(25c) ≤ ‖b0‖2ρk11 + β/2
We have all lemma claims proved. Now it remains to check inequalities (25). First note that our choice of the upper bound on η guarantees that q−1 < 1.
For inequality (25a): By Gershgorin circle theorem, it suffices to show q−1 + ξ < 1, q1 − ξ > 1, then we have ρ1 ≥ q1 − ξ > 1 and ρ−1 ≤ q−1 + ξ < 1. In addition, we need the matrix to be positive definite so that ρ−1 > 0, we just need q1q−1 > ξ2 to make the matrix p.d..
q−1 + ξ < 1
⇐⇒ √ 1 + ‖KP−1bt‖22 n‖P−1bt‖22 [η2(λ22 + (n− 1)τ2)− 2η] < 1− c4ηn−1/2τ
⇐=‖KP−1bt‖ 2 2
n‖P−1bt‖22
[ η2(λ22 + (n− 1)τ2)− 2η ] < c24η 2n−1τ2 − 2c4ηn−1/2τ
Lemma 24⇐= 2c4ηn−1/2τ ≤ c24η2n−1τ2 + λ2n − [2λ1 + (n− 2)τ ]nτ
n
[ 2η − η2(λ22 + (n− 1)τ2) ] ⇐⇒λ 2 n − [2λ1 + (n− 2)τ ]nτ
n
[ λ22 + (n− 1)τ2 ] η − c24n−1τ2η
≤ 2λ 2 n − [2λ1 + (n− 2)τ ]nτ
n − 2c4n−1/2τ
⇐=η ≤ 2 1− c4 √ nτ/[λ2n − [2λ1 + (n− 2)τ ]nτ ]
λ22 + (n− 1)τ2 − c24τ2/[λ2n − [2λ1 + (n− 2)τ ]nτ ]
⇐⇒η ≤ 2 λ22 + (n−1)τ2−c24τ2/[λ2n−[2λ1+(n−2)τ ]nτ ]+λ22[c4 √ nτ/[λ2n−[2λ1+(n−2)τ ]nτ ]]
1−c4 √ nτ/[λ2n−[2λ1+(n−2)τ ]nτ ]
which is true by our choice of η.
q1 − ξ > 1
⇐⇒n− 1 n + 1 n |1− η‖P1K1‖22| − c4ηn−1/2τ > 1 ⇐⇒1 + c4η √ nτ < |1− η‖P1K1‖22|
⇐=η‖P1K1‖22 − 1 > 1 + c4η √ nτ
⇐=η > 2 ‖P1K1‖22 − c4 √ nτ (18)⇐=η > 2 λ21 − c23[2λ1 + (n− 2)τ ]2nτ2 − c4 √ nτ
which is true by our lower bound on η. q1q−1 > ξ 2
⇐=q2−1 ≥ ξ
⇐⇒1 + ‖KP−1bt‖ 2 2
n‖P−1bt‖22
[ η2(λ22 + (n− 1)τ2)− 2η ] > c4ηn −1/2τ
⇐=1− 2ηλ 2 2 + (2λ1 + (n− 1)τ)nτ
n > c4ηn
−1/2τ
⇐⇒η < n 2λ22 + 2(2λ1 + (n− 1)τ)nτ + c4 √ nτ
which is true.
For inequality (25b): It suffices to take
k1 = log( β/(2‖b0‖2)) log(ρ−1) = O(log 1 β )
For inequality (25c): We just need to show sin θ < (ρ−1/ρ1)k1 . Calculate that ξ/(q1 − q−1) = cos θ sin θcos2 θ−sin2 θ , then
sin θ < (ρ−1/ρ1) k1
⇐=ξ/(q1 − q−1) < 0.9(ρ−1/ρ1)k1
⇐=ξ < 0.9(q1 − q−1)( q−1 − ξ q1 + ξ )k1
⇐=ξ < 0.9(q1 − q−1)( β/(2‖b0‖2)) 1− log(q1+ξ) log(q−1−ξ)
⇐=ξ < (q1 − 1)poly( β) ⇐= √ nτ ≤ poly( β)
For inequality (25d): Suffice to show
ξ < (q1 − 1)β0 B0 + β0/2
⇐= √ nτ ≤ O(1)
Lemma 27 (Long run behavior of SGD with small step size). Under the same notations and assumptions as Lemma 26 unless otherwise specified. Consider another k2 − k1 steps of SGD update with step size
η′ < 1
λ21 + c7 √ nτ
where the constant c7 ≥ √ nτ + c4. Then we have for k > k1:
• Bk ≤ β • Ak ≤ { qAk−1 , Ak−1 > β β ,Ak−1 < β
where q := q1(η′) + ξ(η′) < 1.
Proof. Denote q′1 = q1(η ′), q′−1 = q−1(η ′), ξ′ = ξ(η′), then q = q′1 + ξ ′ , denote B = ‖b0‖2 ∗ ρk11 + β/2. We have by proof of Lemma 26 that q ′ −1 + ξ < 1. We claim the following holds:
q < 1 (26a)
ξ′B ≤ (1− q′1) β (26b)
Check inequality (26a):
q′1 + ξ ′ < 1
⇐=n− 1 n + 1 n |1− η′‖P1K1‖22|+ c4η′n−1/2τ < 1
⇐⇒|1− η′‖P1K1‖22| < 1− c4η′ √ nτ ⇐⇒c4η′ √ nτ < η′‖P1K1‖22 < 2− c4η′ √ nτ
⇐⇒ { c4 √ nτ < ‖P1K1‖22
η′ < 2‖P1K1‖22+c4 √ nτ ⇐= { √
nτ < O(1) η′ < 2
λ21+nτ 2+c4
√ nτ
which are true by assumption.
Check inequality (26b):
ξ′B ≤ (1− q′1) β
⇐⇒c4η′n−1/2τ(‖b0‖2 ∗ ρk11 + β/2) ≤ (1− n− 1 n − 1 n (1− η′‖P1K1‖22)) β ⇐⇒c4η′ √ nτ(‖b0‖2 ∗ exp(k1)log ρ1 + β/2) ≤ η′‖P1K1‖22 β
⇐= √ nτ ≤ poly( β).
With (26) we can prove the lemma by mathematical induction. Suppose Bk−1 ≤ β and Ak−1 ≤ Ak1 ≤ B, then check
Bk ≤ ξ′Ak−1 + q′−1Bk−1 ≤ ξ′B + q′−1 β (26b) ≤ β
and
Ak ≤ q′1Ak−1 + ξ′Bk−1 ≤ q′1Ak−1 + ξ′ β ≤ (q′1 + ξ′ ) max{Ak−1, β}
≤ { qAk−1 , Ak−1 > β qβ < β ,Ak−1 < β .
We recap Theorem 5 using our notations in previous lemmas as follows:
Theorem 28 (Directional bias of the two-stage SGD). Use the two stage SGD scheme as defined in Lemma 26 and 27. Assume nτ < poly( ), then there exists k1 = O(log 1 ) and k2 such that
(1− 2 )γ1 ≤ E[‖Kbk2‖2] E[‖bk2‖2] ≤ γ1
where γ1 is the largest eigenvalue of K.
Proof. In Lemma 26 let β = β0, then for k1 = O(log 1 ) we have Bk1 ≤ β0. For the 2nd stage, by Lemma 27 we can early stop at k2 such that Ak2 ≥ β0 and Ak2+1 < β0. We then have
Bk2 ≤ β0 ≤ Ak2
Then we check
E‖Kbk2‖2 E‖bk2‖2
= E √ ‖KP−1bk2‖22 + ‖KP1bk2‖22 + 2〈KT1 P−1bk2 ,KT1 P1bk2〉
E‖bk2‖2 ≥E √ ‖KP1bk2‖22 − 2‖P−1K1‖2‖P1K1‖2‖bk2‖22
E‖bk2‖2 ≥E √ ‖KP1bk2‖22 − E √ 2‖P−1K1‖2‖P1K1‖2‖bk2‖22
E‖bk2‖2
= E‖KT1 P1bk2‖2 − √ 2‖P−1K1‖2‖P1K1‖2E‖bk2‖2 E‖bk2‖2
(17),(18) ≥ √ λ21 − c23[2λ1 + (n− 2)τ ]2nτ2
E‖P1bk2‖2 E‖P1bk2‖2 + E‖P−1bk2‖2
− √ 2(λ1 + √ nτ)(c3(2λ1 + (n− 2)τ) √ nτ)
≥ √ λ21 − c23[2λ1 + (n− 2)τ ]2nτ2
β0 β0 + β0
− √ 2(λ1 + √ nτ)(c3(2λ1 + (n− 2)τ) √ nτ)
(13) ≥ (γ1 − nτ − c3(2λ1 + (n− 2)τ) √ nτ)(1− )− √ 2(λ1 + √ nτ)(c3(2λ1 + (n− 2)τ) √ nτ)
≥γ1(1− )− γ1 (By nτ < poly( )) =γ1(1− 2 )
And the upper bound in the theorem is by definition of γ1.

heading: F DIRECTIONAL BIAS OF GD WITH MODERATE OR SMALL STEP SIZE
text: This section includes the proof of Theorem 7. We first rewrite the GD updates as linear combination of eigenvectors. Then the theorem is proved using the transformed variables and finally transformed back to original parameters.
The directional bias of GD does not require diagonal dominant gram matrix.
Reloading notations Denote the eigen decomposition of K:
K = GΓGT ,Γ = diag(γ1, . . . , γn), G = [g1, . . . , gn]
where the eigenvectors gi’s are orthogonal. The GD update as
αt+1 = αt − η
n K(Kαt − y)
Denote wt := GT (αt − α̂), we can rewrite GD update in wt:
wt+1 = wt − η
n Γ2wt = (I −
η n Γ2)wt
We recap Theorem 7 to make reading easier as follows:
Theorem 29 (Direction bias of GD). Assume α0 is away from 0, λn + 2nτ < λn−1, GD with step size:
η < n
(λ1 + nτ)2
For a small > 0, take k = O(log 1 ), we have
γn ≤ ‖K(αk − α̂)‖2 ‖αk − α̂‖2 ≤ √ 1 + γn
Proof. For i = 1, . . . , n, we have
w (i) k = (1− ηγ 2 i /n) kw (i) 0
Denote qi = 1− ηγ2i /n, then 0 < q1 ≤ . . . ≤ qn < 1 since
0 < η < n
(λ1 + nτ)2
(13) ≤ n γ21 ≤ n γ2i
Since λn + nτ < λn−1 − nτ , we have γn < γn−1 by lemma 20, it follows that qn > qn−1. Denote q = qn−1/qn < 1, then ∑n−1
i=1 (w (i) k ) 2 (w (n) k ) 2
=
∑n−1 i=1 q 2k i (w (i) 0 ) 2
q2kn (w (n) 0 ) 2 ≤ ∑n−1 i=1 q 2k n−1(w (i) 0 ) 2
q2kn (w (n) 0 ) 2 =q2k ∑n−1 i=1 (w (i) 0 ) 2
(w (n) 0 ) 2
Let q2k ≤ γ 2 n (w (n) 0 ) 2 γ21 ∑n−1 i=1 (w (i) 0 ) 2 ⇐⇒ k ≥ 12
log γ2n (w (n) 0 ) 2
γ21 ∑n−1 i=1 (w (i) 0 ) 2
log q = O(log 1 ), we have∑n−1
i=1 (w (i) k ) 2 (w (n) k ) 2 ≤ γ 2 n γ21
Thus
‖K(αk − α̂)‖22 ‖αk − α̂‖22 = ‖Γwk‖22 ‖wk‖22
=
∑n i=1(w (i) k )
2γ2i∑n i=1(w (i) k ) 2
= (w
(n) k ) 2γ2n∑n i=1(w (i) k ) 2 +
∑n−1 i=1 (w (i) k )
2γ2i∑n i=1(w (i) k ) 2
≤ γ2n + ∑n−1 i=1 (w (i) k )
2∑n i=1(w (i) k ) 2 γ21
≤ γ2n + γ21 γ2n γ21 = γ2n(1 + )
thus ‖K(αk − α̂)‖2 ‖αk − α̂‖2 ≤ √ γ2n(1 + )
The lower bound of the theorem holds by definition of γn.

heading: G EFFECT OF DIRECTIONAL BIAS
text: In this section, we provide the proof for theorems in Section 4.2. There are two theorems there, so we split this section into two subsections. Subsection G.1 proves Theorem 9, for a general problem setting of squared error minimization, it provides a straightforward understanding for why directional bias towards the largest eigenvalue of the Hessian is good for generalization. Section G.2 proves Theorem 11 by giving concrete generalization bounds of SGD and GD estimators in kernel regression.
G.1 PROOF OF THEOREM 9
Denote v = w −w∗, rewrite the objective function as
min v
‖v‖22
s.t. ‖Av‖22 = a
Denote the eigen decomposition of ATA = QΓQT where Q = [q1, . . . , qn], QQT = QTQ = I and Γ = diag([ρ1, . . . , ρn]), ρ1 ≥ . . . ≥ ρn ≥ 0. Then
‖Av‖22 = n∑ i=1 ρi(q T i v) 2
So
‖Av‖22 ≤ ρ1[ n∑ i=1 (qTi v) 2] = ρ1v TQQTv = ρ1‖v‖22
The equality is achieved when v is in the direction of q1, and ρ1 = ‖ATA‖2. Take L(w) = ‖Av‖22 = a then the theorem holds.
G.2 PROOF OF THEOREM 11
Calculate ∆∗a: Denote f∗ = α̂TK(·, X) + f̃ , then we have for a f ∈ Hs, f = αTK(·, X), let b = α̂−α, then
‖f∗ − f‖2H =‖bTK(·, X) + f̃‖2H =‖bTK(·, X)‖2H + ‖f̃‖2H + 2〈bTK(·, X), f̃〉H
where we can check 〈bTK(·, X), f̃〉H = ∑ i=1 bi〈K(·,xi), f∗ − α̂TK(·, X)〉H
= ∑ i=1 bi[〈K(·,xi), f∗〉H − 〈K(·,xi), α̂TK(·, X)〉H]
= ∑ i=1 bi[f ∗(xi)− α̂TK(xi, X)](By reproducing property)
= ∑ i=1 bi[yi − yi] = 0
And we further calculate that
‖bTK(·, X)‖2H = 〈 n∑ i=1 biK(·,xi), n∑ j=1 bjK(·,xj)〉H
= n∑ i,j=1 bibj〈K(·,xi),K(·,xj)〉
= n∑ i,j=1 bibjK(xi,xj) = b TKb
That is,
LD(f) = b TKb+ ‖f̃‖2H
and
inf f∈Hs
LD(f) = ‖f̃‖2H
It follows that
∆(f) = LD(f)− inf f∈Hs LD(f) = b TKb
We claim that
∆∗a = min b: 12n‖Kb‖ 2 2=a
bTKb = 1
γ1 ‖Kb‖22 = 2na/γ1
where the equality is obtained when b is in the direction of the largest eigenvector of K. To see this, we check ‖Kb‖22 ≤ γ1bTKb. Recall the eigendecomposition of K = GΓGT where G = [g1, . . . , gn] has orthogonal columns and Γ = diag(γ1, . . . , γn). Then
‖Kb‖22 = n∑ i=1 γ2i (g T i b) 2
and
bTKb = n∑ i=1 γi(g T i b) 2
So we have
‖Kb‖22 ≤ γ1[ n∑ i=1 γi(g T i b) 2] = γ1b TKb
This finishes our claim on ∆∗a.
SGD output: By Theorem 5, the SGD output has
(1− 2 )γ1E[‖bk2‖2] ≤ E[‖Kbk2‖2]
Thus
E[∆1/2(fSGD)] = E √√√√ n∑ i=1 γi(gTi b SGD)2  ≤ √γ1E[(
n∑ i=1 (gTi b SGD)2)1/2]
= √ γ1E‖bSGD‖2 ≤ √γ1E[‖KbSGD‖2]/[(1− 2 )γ1]
= √ 2na/γ1/(1− 2 )
= 1
1− 2 (∆∗a) 1/2
< (1 + 4 )(∆∗a) 1/2
last inequality by let < 1/4.
GD output: By Theorem 7, the GD output has
‖KbGD‖22 ‖bGD‖22 ≤ (1 + ′)γ2n
Thus
∆(fGD) = n∑ i=1 γi(g T i b GD)2
≥ γn n∑ i=1 (gTi b GD)2
= γn‖bGD‖22 ≥ γn‖KbGD‖22/[(1 + ′)γ2n] = 2na/[(1 + ′)γn] = γ1
(1 + ′)γn ∆∗a
> γ1 γn (1− ′)∆∗a := M∆∗a
where M > 1 by taking ′ < 1− γn/γ1.

heading: H EXPERIMENTS
text: We list the implementation details of the experiments at the end of Section 4 and include more experiment results. For better presenting, we split into two subsections: Subsection H.1 includes the details of simulation; Subsection H.2 is about the NN experiment on FashionMNIST, including the data description, network structure, and algorithm details, also there are more experiment results in Subsection H.2 that are not listed in Section 4 due to page limit.
H.1 SIMULATION
This subsection is corresponding to Figure 1.
Data Generation. The training data is simulated as follows: Set n = 10, p = 100, simulate Xn×p where elements of X are i.i.d. N(0, 1); denote ith row of X as xi, normalize xi such that it has squared `2 norm in [.49, 1]; set yi = ∑p j=1 sin(xi,j) + i where i
i.i.d.∼ N(0, .01). The testing data is simulated in exactly the same way, except that we only simulate n = 5 testing data.
Kernel Function. We set the kernel function to be the polynomial kernel
K(x1,x2) = (〈x1,x2〉+ .01)2
SGD and GD implementation. Both SGD and GD is run for small and moderate step sizes. The moderate step size scheme for SGD is: η1 = .1 for the first 50 steps, and η2 = .01 for the next 1000 steps; for GD is: η1 = .5 for the first 50 steps, and η2 = .05 for the next 1000 steps. The small step size scheme for SGD is η = 0.01 for 1050 steps; for GD is η = 0.05 for 1050 steps. Note that the step size for SGD is a fraction of that for GD, this matches our Theorem 5 and 7 that the step size of GD is of magnitude n/2 times that of SGD.
H.2 NEURAL NETWORK ON FASHIONMNIST
This subsection is corresponding to Figure 2.
Dataset. The original FashionMNIST consist of 60, 000 training data and 10, 000 testing data. We randomly sample 1, 500 data from original training data for training, and use all 10, 000 original testing data for testing. All data entries are normalized to [0, 1].
Network structure. we use a 6-layer ResNet-like (He et al., 2016) Neural Network, and the structure is as follows
Input ⇒ 7× 7 Conv ⇒ BatchNorm⇒ ReLU⇒ 3× 3 MaxPool ⇒ ResBlock1⇒ ResBlock2⇒ Global AvePool⇒ FC⇒ output
The Residual Blocks are as Figure 7.6.3 in Zhang et al. (2021) (without 1 × 1 convolution). Note that each residual block contains two 3 × 3 convolutional layers, thus total number of layers is as stated.
Algorithm. We minimize the Cross Entropy Loss objective L(w) = 1n ∑n i=1 li(w), where li(w) is the loss function at ith sample. One step SGD is as follows:
wt+1 = wt − ηt 1 |I| ∑ i∈I ∇li(wt)
where I is a randomly sampled subset of {1, . . . , n} (uniform random sample without replacement). We choose the batch size |I| to be 25. One step GD is as follows:
wt+1 = wt − ηt∇L(wt) Both SGD and GD are run using two settings of step sizes ηt. The moderate step size setting is as follows:
ηt =
{ 0.2, t = 1, . . . , 5000
0.02, t = 5001, . . . , 20000
And the small step size setting has ηt = 0.02, t = 1, . . . , 20000.
Comparison of convergence direction. Since the loss surface is nonconvex and the Hessian varies, we follow Wu et al. (2021) to measure the convergence direction by Relative Rayleigh Quotient(RRQ), which normalizes the Rayleigh Quotient by the maximum eigenvalue of the Hessian as follows
RRQ(w) =
∇L(w)> ‖∇L(w)‖2 · ∇ 2L(w) · ∇L(w)‖∇L(w)‖2 ‖∇2L(w)‖2
whereL(w) is the loss function on the whole training set. A high RRQ indicates that the convergence direction of w is close to a larger eigenvector of the Hessian.
Comparison of test accuracy. We set 20 different random seeds. For each random seed, we run: SGD with moderate step size, GD with moderate step size, SGD with small step size, GD with small step size. For each algorithm, we evaluate its test accuracy once every 500 steps, and use the average of the last 5 values as its test accuracy. We list the test accuracy in Table 1.
We also use one-side Wilcoxon signed-rank test to check if the test accuracy of different algorithm are significantly different, the result is in Table 2. All the p-values are significant at 0.01 level, so we reject the null hypothesis and conclude that the SGD with moderate step size has test accuracy significantly higher than all other algorithms.
Additional experiments. We conduct more experiments using different step sizes. The initial step size is taken in {1, 0.5, 0.2, 0.1, 0.02, 0.01, 0.005, 0.001}, and the step size is divided by a factor of 10 after 5000 steps. The test accuracy is in Figure 3, where we see that SGD with step size 0.2 has the best test accuracy, and GD with step size 0.5 performs better than GD with any other step sizes, but is still worse than the best SGD.

Review summaries:
This paper studies the directional bias of SGD in kernel regression. In particular, this paper shows that when using moderate or small step size, GD converges along the direction corresponding to the smallest eigenvalue of the covariance matrix. In contrast, when provided with a moderate initial learning rate with annealing, SGD converges along the direction corresponding to the largest eigenvalue. Consequently, the authors show that such directional bias of SGD can result in an estimator that is closer to the ground truth, which further leads to better generalization. 

The paper studies the trajectory of GD and SGD for kernel regression, and the connection to generalization. The paper shows that, under some stepsize choices, SGD has a directional bias towards sharp eigendirections of the kernel matrix. The authors link this feature to generalization using the properties of quadratics.

This paper studies directional bias of SGD vs. GD in the setting of kernel regression. The presented results well-recover those for linear regression shown by prior work (Wu et al. 2021). Both theory and experiments are presented.