Directional Bias Helps Stochastic Gradient Descent to Generalize in Nonparametric Model
Authors: Yiling Luo
Xiaoming Huo
Yajun Mei
Venue: ICLR 2022 Submitted (2022)
Keywords: directional bias
SGD
RKHS
nonparametric regression

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. 

Under review as a conference paper at ICLR 2022
DIRECTIONAL BIAS HELPS STOCHASTIC GRADI- ENT DESCENT TO GENERALIZE IN NONPARAMETRIC MODEL
Anonymous authors Paper under double-blind review
ABSTRACT
This paper studies the Stochastic Gradient Descent (SGD) algorithm in kernel re- gression. The main finding that SGD with moderate and annealing step size converges in the direction of the eigenvector that corresponds to the largest eigen- value 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 larger eigenvalue of the Hessian (which is the gram matrix in our case) results in an estimator that is closer to the ground truth. Adopt- ing this result kernel regression, the directional bias helps the SGD estimator generalize better. This result gives one way to explain how noise helps in gen- eralization when learning with nontrivial step size, which may be useful for promoting further understanding of stochastic algorithms in deep learning, The correctness of our theory supported by simulations and experiments of Neural Network on the FNSSionMNIST dataset.
INTRODUCTION
In this paper, we study the Stochastic Gradient Descent (SGD) algorithm in nonparametric re- gression model. Among nonparametric models, one popular choice in both statisties and machine learning communities is the kernel model that is generated by Reproducing Kernel Hilbert Space (RKHS). When fitting kernel models to the data, SGD computationally efficient as compared to Gradient Descent (GD) (Ma et al., 2018). This motivates us 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 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 similar concept of the directional bias, but generalize them to the nonparametric model. Our result is a non-trivial extension of their approach, due the difference in our problem setting and 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 nonparametrie 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 statisties 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 Belkin al. (2018); Liang & Rakhlin (2020): they prove that SGD and GD algorithms both converge 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 large class of kernel functions and allows us to study their properties. Moreover, SGD is

---

Under review as a conference paper at ICLR 2022
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 parts, briefly summarized as follows:
First is the directional bias of SGD, Theorem shows that for a two-stage SGD with a moderate step size in the first stage and small step size in the second stage, 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 the direction towards the largest eigenvector simplify the statement.
As comparison, Theorem 7 shows that GD with both moderate and small step sizes has directional bias towards the eigenvector that corresponds to the smallest eigenvalue of the gram matrix (denote it 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 considers general problem of quadratic loss. shows that the estimator biased towards the largest eigenvector of the Hes- sian (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 gener- alization error of SGD and GD in our problem setting. particular, upper bounds the generaliza- tion 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-ther arrt 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 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 those problem settings.
Paper organization. The rest of the paper as follows: In Section 2, we review some rele- vant literature; In Section 3, we give the formulation of the nonparametric regression and define the optimization problem. We also formalize the algorithm that 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 theory: In Section 5, we discuss the finding 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.
conducted support
2 LITERATURE REVIEW
In this section, we review some relevant works. For better understanding, we split into two subsec- tions: 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.
2.1 RKHS
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 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 'kemel 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
2

---

Under review as a conference paper at ICLR 2022
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, can see kernel regression for image processing (Takeda et al., 2007), for text mining (Greene & Cunningham, 2006), and for tasks in bioinformatics (Saigo al., 2004).
Regarding deep learning, the kernel method is also important because it has implications for deep learning models. On the one hand, the kemel 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.
2.2 DIRECTIONAL BIAS
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". 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 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.
worth noting
State-of the-terrrt study on the directional bias of first-order algorithms can be divided into two cate- gories 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 (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 min || -yll has a solution path close to the solution path of Ridge regression; Blanc et al. (2020) shows the stochastic gradient flow for 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 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 mean- ingful 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 repa- rameterized GD in sparse regression. They divide the true parameter into strong, weak, and 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 overparameterizee linear regression, SGD with moderate step size converges to the minimum norm interpolant in the direction that cor- responds 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
3

---

Under review as a conference paper at ICLR 2022
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 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.
PROBLEM FORMULATION
We give our problem formulation in this section. In Subsection 3.1 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.
3.1 KERNEL REGRESSION
Suppose we are given n data pairs (I,, y4 ) generated from an unknown model y f(x), where 2; X' c. R² and E R. The goal is to estimate the unknown model f from the data. To achieve the goal, one way is to find f that minimizes the empirical risk function
min Σ f(x:))
(1)
1=1
where is the loss function. For the regression task, we use the squared loss E(y, x)) = { ( f(=))²
One can see that problem (1) is not well-defined, as there are infinitely many solutions to Vi : f(z,) = y/s and some of them do not generalize for a new test data. One way to fix it is to restrict E H. and add regularization term in || to problem (1) for smoothness, where H is RKHS with reproducing kernel ((::)) and || || is the Hilbert norm. Adding these restrictions and applying Representer Theorem, problem (1) with the squared loss becomes
min aER 2n
Σ yu KT a))
i=1
1
Ka
2n
where KF is the ith row of K := ((X,X)= (K xz )ay For parameter a, the correspond- ing estimator in H is f(.) -m= 0g K( a K(, X).
Now when K is invertible, it is trivial that any algorithm objective function (2) (if it con- verges) converges at the unique minimal, that is, á = (( y. result in the RKHS functional estimator
K(x, )). Estimator (3) is the minimum norm interpolant as f(x) = K(x, X) ((X,))-1
where K ((x,, X)T (K(x, 21), given by following problem:
arg min + f(x:) ye, i = =1, 1,...,n] FEH
And its property has been studied in Liang & Rakhlin (2020).
In this paper, we compare the convergence direction of SGD and GD to â. Specifically, 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, define the one-step SGD/GD update and state our assumptions and notations for analysis.
3.2 ONE STEP SGD/GD UPDATE
In this paper, we consider the SGD algorithm as follows. For objective function (2), denote the parameter estimation čth step a,, then SGD update 0x
at+1 at
T1 (TTK.. a: V4.)) Ki.
(4)

---

Under review as a conference paper at ICLR 2022
where & is uniformly random sampled from [I,....n].
The GD update a 1++110 as
2ht K (Ka, -y) = =a; - "KKK - y)
04+1 =
(5)
3.3 ASSUMPTIONS AND NOTATIONS
We state our assumption on the gram matrix a unified format. Later we show in Appendix that some popular kernel families satisfy our assumption.
Assumption (Diagonal Dominant gram matrix). Denote by K ((X, X) the gram matrix, we assume that K is diagonal dominant. Specifically, suppose w.l.o.g. that K1,1 2 K2.2 Z Kn,n O, then we have for a small value T that
Kiyl S Kinniiii
Remark 2. Diagonal dominant gram matrix is common in kernel learning. Mathematically, one can justify that gram matrix is diagonal dominant by imposing proper assumptions on the kernel function (-.-) 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 the inner product of nigh-dimensional features, the resulting gram matrix is diagonal dominant when the high-dimension features are sparse. This happens for lot of practical problems (Schölkopf al., 2002; Weston al., 2003), for example, when linear or string kernels are applied to text data (Greene & Cunningham, 2006), when domain- specific kernels are applied image retrieval (Tao et al., 2004) and bioinformaties (Saigo et al., 2004), and when the Globul Alignment kernel is applied to most datasets (Cuturi et al., 2007; Cuturi, 2011). I).
Proposition 4 (Lemma in Wu et al. (2021)). Consider the bilinear kernel K(x, x') := (x, x'). Assume the data 34, i 1.....P. are i.id. uniformly distributed on the unit sphere Sd-1 where d > n. When d 2 4 log (2n (2n²/8)
some E 10. Then with probability at least 1 - 8, we have
| = [(,, 23,I < = 0 Vd Kn,n =1,
V. j.
It is meaningful to note that the diagonal dominance is undesired in classification and clustering tasks. indicates that the data pieces are dissimilar to each other as measured by the kernel function, and thus generates very little information for blassffiation/clusternng One may find lot of works on solving the issue of diagonal dominance 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); Candès (2008); Chen & Donoho (1994). Such conditions in sparse settings. In our case, we adopt the dissimilarity concept and apply it to data points in high-dimensional nonlinear feature space. Later 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.
these cases, for example, Greene &
required for proving minimax optimality exact recovery of sparse signal
will see that in the existence of diagonal
Notations. We use the following notations throughout the remaining of this work. For the gram matrix K, denote Kij be the element at ith row jth column of K. Denote X, = K,,; = K (zx, az), and assume w.l.o.g. that X > X2 2 > An- Denote the ith column of K as K, let K_1 K Kn]. Assume is full rank, denote P-1 the projection onto column space of K-1, and P1 I- P-1. And denote 71 .... Yn eigenvalues of K in non-increasing order.
4 MAIN RESULT
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
5

---

Under review as a conference paper at ICLR 2022
directional leads to good generalization performance, and further applies this result to show that SGD generalizes better than GD.
4.1 DIRECTIONAL BIAS
Since assumed that K is full rank, then SGD and GD algorithm objective function (2) con- verges to á = K y (when they converge). We are interested in the direction at which a, converges ax i.e. the quantity
by 0z &
With assumption 1 that the gram matrix is diagonal dominant, we prove that two-stage SGD has be converge the direction of the largest eigenvector of K.
Theorem 5 (Direction bias of SGD estimator). Assume Assumption holds, run a two-stage SGD with a fixed step size for each stage: stage with step size nn for steps 1,... K1, stage 2 with step size 1/2 for steps k1 + l,..., K2, such that
< m < X3 + C2VRT
A - CIVIT
1
72 X2 +
where C1, C2 C3 constants that specified in the Appendix E. For small 0 such that nt < poly(c) there exists kn = =logg L) and l2 such that
Kbl LKKDSGD
(1- S EIIbS [2]
That is, 5SGD close to the direction of the largest eigenvector of K.
Remark 6. One should assume in Assumption I to be small enough for to be very small if one would like the resulting estimator bSGD 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 T is not that strong.
The proof of Theorem 5 is in Appendix E. Next, we see that GD has b, converge in the direction of the smallest eigenvector of K, which contrasts with the directional bias of SGD.
Theorem (Direction bias of GD estimator). Assume Assumption I hold, run GD with fixed step size:
n
1 < (A1 + nT)
for a small é' O, run k Ollo 4) steps of GD, we have
1KbE GD 112
S vi1ddn
in
6 1
That is, be is close to the direction of the smallest eigenvector of K.
Remark 8. The assumption (on T) is mild for differentiating the directional bias of SGD and GD. Comparing Theorem 5 and 7, we see that as long as 7/n < (2-2c) by taking is large enough we always have
KKGP
EIIKbSGDI
That is, may expect SGD be in the direction of larger eigenvalue compared with PCD, In the following subsection, we see that the directional bias towards a larger eigenvalue of the kernel is good for generalization, which leads to title that directional bias helps SGD generalize in kernel regression.
The proof of Theorem 7 is in Appendix F. Although there is assumption I 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 r. then for an arbitrarily small é' > O, we can always run GD long enough such that the theorem holds and the estimator CD is arbitrarily close the smallest eigenvector.

---

Under review as a conference paper at ICLR 2022
4.2 EFFECT OF DIRECTIONAL BIAS
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 the parameter estimation enror and in this way, the directional bias helps SGD to generalize.
Theorem 9, Consider approximately minimizing the quadratic loss
L(w) = -[.Aw - y1
Assume there is ground truth w² such that y = Aw", , for a fixed level of the quadratic loss, the parameter estimation error ||w0 w= 112 has lower bound
Vwu E {w L(w) =a} || w
a
||
All2
Moreover, the equality is obtained when w w is in the direction of the eigenvector that corre- sponds the largest eigenvalue of AT A.
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 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 Theorem 9 Appendix G.1.
Suppose 3f H such that y (z). Consider the generalization error LD(f) = llf 1 for algorithm output falg, decompose its generalization error as:
LD( inf LD( Lp( inf LD()) inf LD inf LD()
SEN
JEH,
JEH,
JEN
:=A(fat)), estimation error
approximation emror
where H. is the hypothesis class that the output of the algorithm restricted to. By formulation (2), we have our hypothesis class as
H. (K,
We define the levevel set of training loss:
Ve = (f E H. f aK, KKa -112 = a}.
2n
denote A; := inf sev. A()).
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 So we just minimize the estimation eтror for estimators that are in the a aelevel set. As shown in Appendix G.2, one can check the estimation error given by
f E H. A(F) = 6t Kb
where b a &. By similar reasoning as Theorem 9, the estimation error is minimized when is in the direction of the largest eigenvalue of K, so the directional bias towards a larger eigenvalue statement comparing the estimation
helps to generalize in kernel regression. We formalize enorr of SGD and GD in the following theorem.
Theorem 11 (Generalization performance). Follow Theorems 5 and 7, we have the following:
The oulput of SGD has ([A < (1 + 1/2 where a is such that Ka y112]² = 2na and could be any positive small constant;
The output of GD has ((FGD) 2 MA, where a is the training loss of GD estimator, and M 21 e') > large constant.
Tn

---

Under review as a conference paper at ICLR 2022
1.4
step
step
step
13
GD, small step size
GD. small step size
3,950
GD, small step size
1.2
SGD, moderate step
SCD, mederate step size
SGD, moderate soep size
Rayleigh Quotient
SGD,
6
SGD, small step
SGD, small step size
1.1
3,900
1.0
Training
4
Prediction
3.875
0.9
3.
3.850
0.8
0.7
2-
3.825
1
0.6
3.800
0.5
200
400
600 Iterations
800
1000
200
400
600
800
1000
3.775
0
200
4000
600 800
1000
Iterations
ltterations
Figure 1: Kernel regression on synthetic data. We simulate data from a nonlinear regression model with Gaussian additive noise and fit kernel regression using polynomial kernel. We both SGD and GD for two step size schemes, see details in Appendix H.1. the first plot, we show the directional bias by Rayleigh Quotient(RQ):= converges in the direction of a larger RQ. which matches our Theorems and 7. In the third plot we show the prediction eπrоr 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.
kbb
T|bil (same as Theorem and 7). The SGD indeed
Remark 12. One read from the theorem that the SGD estimator is (8e + - while
GD estimator is (M (u)))su--ae subooptimmm Combine with Theorem 7 that e' k= O, take in Theorem such that (1 + 4c)2 < "/n/"nn
in to have ((SSD < (ffGD) 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 shows the simulation results of kernel regression, Figure 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.
The purpose of experiment using a Neural Network (Figure 2) as following: first, the Neural Network results support our finding 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 complicated network that may not be simply explained by the kernel method.
Remark 13.
DISCUSSION AND FURTHER WORK
Our work takes
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 technique for tuning the learning rate that people use in practice: start with large step size, run long enough until the error plateaus, then decrease the step size (He al., 2016). Although this technique 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 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
8

---

Under review as a conference paper at ICLR 2022
84
0.0020
Relerive Rayleigh Quaten
80
SGD,
0.0010
moder ete step size
78
SGD small step size
step size
0.0005
S003 moderate size 86, 66.21)
CD, moderate step size
82 92.43)
72
2012 smell step size 180 to 99)
-0.0005
small (78 80.451
2500
5000
7500 10000 12500 15000 17500 20000 Iterations
2500
5000
7500 10000 12500 15000 17500 20000
(a) Relative Rayleigh Quotient.
(h) Test accuracy FashionMNIST
The experiment of small ResNet-like Neural Network on FashionMNIST. (a), we follow Wu et al. (2021) to use the Relative Rayleigh Quotient(RRQ) the mcasurement of the convergence direction, where higher RRQ means that the convergence direction is closer to the larger eigenvalue direction of the Hessian. The SGD with moderate step size has higher RRQ than the GD with either moderate step size or small step size, which supports the theory in Theorems and 7. It is also interesting to observe SGD with small step size also has a different directional bias compared with SGD with moderate step size. In (b). we plot the testing accuracy from 20 repetitions of experiments, the test accuracy (inside bracket) of SGD with moderate step size higher than the other cases, and we have Wilcoxon signed-rank test to confirm that the difference is significant at 0.01 level. The test accuracy validates Theorem 11. For more details of the experiments, the rank test, and more experiments, see Appendix H.2.
Figure 2:
be approximated by kernel learning (Jacot et al., 2018), our results help in explaining why the SGD estimator benign overfitting in an overparameterized deep learning.
Just as stated in Belkin et al. (2)18) to understand deep learning one needs to understand kernel learning. This work takes step 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 Appendix, and we include the necessary code and data for reproducing our result in the supplementary material.
REFERENCES
Alnur Ali, Edgar Dobriban, and Ryan Tibshirani. The implicit regularization of stochastic gradient flow for least squares. In International Conference on Machine Learning, pp. 233-244. PMLR, 2020.
Peter L. Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: statistical viewpoint. arXiv:2103.09177 2021.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning need to under- stand kernel learning. In International Conference on Machine Learning, pp. 541-549. PMLR, 2018.
Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by an omstein -bblebbeek like process. In Jacob Abemnethy and Shiv- ani Agarwal (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 483-513. PMLR, 09-12 Jul 2020. URI. http: / http://pooceeeee ngs www.mrrr..... mnlsspress v125/blaneee
.tml.
Emmanuel Candes and Terence Tao. The dantzig selector: Statistical estimation when p is much larger than The annaly of Statistics, 35(6)2331--331,, 2007.

---

Under review as a conference paper at ICLR 2022
Emmanuel J. Candès. The restricted isometry property and its implications for compressed sensing. Comptes Rendus Mathematique, 346(9):589-59 2008. ISSN 1631-073X. doi: http://o.orrr//0....oooooaomam.. science/articlee/ (116511110000 631007308000064.
URL https:/ www.sciienediree.. com/
Shaobing Chen and David Donoho. Basis pursuit. In Proceedings of 1994 28th Asilomar Conference on Signals, Systems and Computers, volume 1, pp. 41-44. IEEE, 1994.
Marco Cuturi. Fast global alignment kernels. In Proceedings of the 28th international conference on machine learning (ICML-II), pp. 929-936, 2011.
Marco Cuturi, Jean-Philippe Vert, Oystein Birkenes, and Tomoko Matsui. A kernel for time series based on global alignments. In 2007 IEEE International Conference Acoustics, Speech and Signal Concessiin-ICAASSE 07, volume 2. pp. 11.4.3. IEEE, 2007.
Michal Derezinski, Feynman T Liang, and Michael W Mahoney. Exact expres- sions for double descent and implicit regularization via surrogate random design. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neurul Information Processing Systems, volume 33, pp. 5152-5164. Curran Asso-
ciates, Inc., 2020. URL https:t/p/// http/ppoeddnnssssee/eeeee / neurip....rss..... wwtpuurps.ccppppppeeeepepppp wwtpc//ppppe////////eeoppp 37740d5 wbw0deebbbbbbbbee hat.00/e277443332222eeee222222 Pooooopaper...dd
Jianqing Fan, Zhuoran Yang, and Mengxin Yu. Understanding implicit regularization in over- parameterized nonlinear statistical model. 20t1:20007,03222, 2021.
Derek Greene and Pádraig Cunningham. Practical solutions to the problem of diagonal dominance in kernel document clustering. In Proceedings the 23rd international conference Machine learning, pp. 377-384, 2006.
Hussein Hazimeh, Rahul Mazumder, and Peter Radchenko. Grouped variable selection with discrete optimization: Computational and statistical perspectives. #rXiv:2104.07084 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: https:://roceddiinni /ttpe//ecoceeeeeceoeoeop meurips.com pdf.
paper/2018 httee///....teeeeaeee3eeeeeeeee.
Jaz Kandola, Thore Graepel, and John Shawe-Taylor. Reducing kernel matrix diagonal domi- nance using semi-definite programming. In Learning Theory and Kernel Machines, pp. 388-302. Springer, 2003.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "Ridgeless" regression can gener- alize. The Annals of Statistics, 4803):1329-134,, June 2020. doi: 10.1214/19-A0S18499
Tianyi Liu, Zhehui Chen, Enlu Zhou, and Tuo Zhao. A diffusion approximation theory of momen- tum sgd in nonconvex optimization. arXiv:1802.051:3 2018
Siyuan Ma. Racf Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern ovrrmaaraet learning. arXiv.1712.06559, 2018
Rahul Parhi and Robert D. Nowak. What kinds of functions do deep neural networks learn? insights from variational spline theory. arXiv:2105.033 033611, 2021.
Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Minimax-optimal rates for sparse additive models over kernel classes via convex programming. Journal of Machine Learning Research, 13 (2), 2012.
10

---

Under review as a conference paper at ICLR 2022
Hiroto Saigo, Jean- Phillppp Vert, Nobuhisa Ueda, and Tatsuya Akutsu. Protein homology detection using string alignment kernels. Bioinformatics, 20(11):1682 1689, 2004.
Bernhard Schölkopf, Jason Weston, Eleazar Eskin, Christina Leslie, and William Stafford Noble. A kernel approach for learning from almost orthogonal patterns. In European Conference on Machine Learning, pp. 511-528. Springer, 2002.
Samuel L Smith, Benoit Dherin, David Barrett, and Soham De. On the origin of implicit regular- ization stochastic gradient descent. International Conference on Learning Representations, 2021. URL httph:ttp/..mmm http::///ppppeeeeeeeeeeeeeeeeerr httpe/nwwwwwweeeeeeeeeeeeeeeeeee
Hiroyuki Takeda, Sina Farsiu, and Peyman Milanfar. Kernll regression for image processing and reconstruction. IEEE Transactions on image processing, 16(2):349-333 -6634,6,,,,,, 2007.
Qingping Tao, Stephen Scott, NV Vinodchandran, Thomas Takeo Osugi, and Brandon Mueller. An extended kernel for generalized multiple-instance learning. 16th IEEE International Confer- ence on Tools with Artificial Intelligence, pp. 272-277. IEEE, 2004.
Tomas Vaskevicius, Varun Kanade, and Patrick Rebeschini. Implicit regularization for optimal sparse recovery.
Wallach, Larochelle, Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran As- sociates, Inc., 2019. URL https: /pp.ceeeeg.cccccciggg.....s neurips cc/paperr2019//lee pdf.
Grace Wahba. Spline models for observational data. SIAM, 1990.
Jason Weston, Bernhard Schölkopf, Eleazar Eskin, Christina Leslie, and William Stafford Noble. Dealing with large diagonals in kernel matrices. Annals of the institute of statistical mathematics, 55(2):391-408, 2003.
Jingfeng Wu, Difan Zou, Vladimir Braverman, and Quanquan Gu. Direction matters: On the im- plicit bias of stochastic gradient descent with moderate learning rate. In International Confer- ence on Learning Representations, 2021. URL https: wwwprevveeeeeeeeeooe/p net/ forum? id= 3X64RI.ZZ600.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms.
2017.
Aston Zhang, Zachary C. Lipton, Mu Li, and Alexander J. Smola. Dive into deep learning. arXiv:2106.1 11322, 2021.
Peng Zhao, Yun Yang, and Qiao-Chu He. Implicit regularization via hadamard product over- parametrization in high-dimensional linear regression. arXiv: /03.00670 2019.

---

Under review as a conference paper at ICLR 2022
A BACKGROUND ON RKHS
This section details background on RKHS in two subsections. The first subsection includes no- tations, 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 RKHS
In this subsection, give the definition and notations for model in RKHS, and its associated norms, basis, etc. The definitions are similar to those Raskutti et al. (2012).
Given data pairs { Mi J where æ. E X' C R2 and E R, assume that y&S are as- sociated with a,s through f(:;), 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 lives as H. with reproducing kernel K X x X - R+ (which known to us). And we associate the functions in with probability measure Q, assume w.l.o.g. that JR² / (a) O. By Mercer's ' theorem, K has eigen-expansion:
K(a, b) = (1))
Where ( are orthonormal basis in I,²(Q), w.r.t the usual inner product I,((Q)= as (o()),(())))T00)) = / gla))(a)d(((a)
Now for any E H. we can expand f(.) Ej= (-))(), where cj (S()), ()))())))))))))))))) And for
f() = 1005))00)))..00 = Σラ= c,)s(-). by Parseval's theorem
((0)0()) = Σ ejdy
And we have another inner product that is defined for RKHS H
(()),())) = Σ 9C'
/=1 7
The reproducing property of RKHS says that Vf E H. we have
K(,), = f(x)
Cubic Splines Formulate a RKHS. We go over an example of RKHS for better understanding. show that the space of cubic splines is 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).
Consider the cubic spline of one dimension,
Assume w.l.o.g. that 2; X' = [0, 1] c R. The cubic spline f X' is continuous, has contin- uous first-order derivative and square integrable second order derivative. By Taylor's theorem with remainder, we have
5(1) -00)(((00)))))) I (u- (
[ ()-
where (t-u)+ max(0. u). Let B be the set of cubic splines on [0, 1] that satisfies the boundary condition f(0) (0) = 0, then for f E B
f(t) //' (t- (f- (u)du
12

---

Under review as a conference paper at ICLR 2022
Let G(t,, u) =. then claim that B is RKHS with reproducing kernel
K(s,t) L. G(s, ((s, u)du
and inner product
(f. (f L ("(u)""(u)do
as one can check the reproducing property
UO) //- 82 (2,(t, t)
("(u)du
Ouz
1 (t - u)) f(t)
A.2 OPTIMIZATION PROBLEM CONSIDERED
This subsection gives problem formulation of kernel regression. Given data pairs {æ,, yr Ji=1 and RKHS H. consider a loss function l which is selected according to how is connected with fxx), we may estimate the model by
n
min JEH
Ein f(x;))
(6)
min G
f(ys.
cody(xx))
71
f=1
Example for l includes
Squared error loss E(y, f) (y f)². which is usually used in regression;
0-1 loss f( = 1 * f > 0), for binary classification;
Logistic loss &Vy log(1 exp(-y f)), also loss function for classification, be considered as 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 penalty to objective (6), result in
Evn, f(x:)) Apen(s)
A popular choice of pen(f) is | any strictly increasing function of || Such method explicitly controlling the model smoothness, and by Representer Theorem, has solution of form
R
f(-) Σ x()
(7)
Plug equation (7) into objective (6), we have the problem becomes
72
min Ogr
Oz K(x;, mz))
Which gives the formulation (2) under loss function Ely, f(x)) (y f(x)))
13

---

Under review as a conference paper at ICLR 2022
B DIAGONAL DOMINANCE OF SOME POPULAR KERNELS
In this section, we justify Assumption 1 by figuring out problem setting where some popular ker- nels give diagonal dominant gram matrix. For simplicity, assume the following data distribution throughout this section:
X; E R 10, n, are normalized such that || ll 1;
(A.1)
The direction of æ,s are i.i.d. uniformly distributed on the unit sphere 5d
(A.2)
n (overparameterized setting).
(A.3)
Given assumption set (A), we can bound the inner product of data (æ1, 22) with high probability as follows:
Lemma 14 (Lemma 1 in Wu et al. (2021)). Under assumption set (A), let d 2 4log(2n²) /6) for some 8 E (0, 1). Then with probability at least 1 - 8, we have
Ka,, x,y1 < F : Ō
Proof. See proof of Lemma 1 in Wu et al. (2021).
The bound on the inner product (æ., xty) induces bound on K (æ;; 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 transforma- tion of inner product. We can write it
K K(v,, æz,) = I( (a:; æ;,)
Assume assumptions (A) hold, and assume the the function g [[-1,1] + R satisfies:
is convex;
(B.1)
g I, smooth, that is, Vg is I, Lipsscse continuous:
(B.2)
g()) S cf for a constant c, (0) 20.
(B.3)
will have with probability 1 5
|K,l S g 42 for #
(10)
where å and i the same as in Lemma 14. When (0)F+ < for small enough F, the gram matrix is diagonal dominant.
Proof. We have the following with probability least - 8 by Lemma 14. For any off off-diagonal elements of K:
K2 = g((x,,, xz,)
2 (0)) + +g (x),
2 (0' c)F
and
Ki g((2; (1),
$ g() + g g0(( (x,, xz) + I. 2 (xx xz,)
< of (0) م2
Thus |Kaz S (c g (0)))
Remark 16. We list some examples of inner product kernels that give diagonal dominant kernel matrices:
14

---

Under review as a conference paper at ICLR 2022
Bilinear Kernel: K xx,x')= (x, x²), then
[x x,)1 S < (In, In) =1
Polynomial Kernel: K( (x) ((x, c) for N and O(7), then by Proposition
[K(x, xz)] (1 m+) m * exp((m-1)))
when (1+m)f++ m=exp((m-11)]] < (1+c)", we have diagonal dominant gram matrix.
Hyperbolic Tangent Kernel (Sigmoid Kernel): (( x') = tanh(a x²) + c). where a > 0, 2 Note that Hyperbolic Tangent Kernel does not satisfy all the assumptions in Proposition 15, one still calculate
| (x x2 tanh(a7 +c)
and
K (xk, x&) = tanh(a + c)
When tanh(af + c) & tanh(a c) (which is the case when large, and c, small enough), we have (2;, < K (a., æn) 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(x;, x;) = exp(-7|laz - =,,12),7>>
Assume assumptions (A) hold, when 7 loglog(F) for constant co. have with probability
Kiyl S 2200(1-9) < Kn,, 1, for #
where 5 and i the same as in Lemmna 14. That is, the Gram matrix is diagonal dominant.
Proof. Bound off-diagonal terms K by Lemma 14:
K, exp(->/|az xz 11)1))
S exp(227 27))
(1
Remark 18. We note some popular kernels that are related Radial Basis Function kernel, and show that they lead to diagonal dominance:
Gaussian Kernel: K(x, x') exp( 20
One can see that Gaussian Kernel is reparameterizing RBF Kernel by 7 1/(20²). Thus Gaussian gram matrix is diagonal
dominant when o² O O log(s))
Laplace Kernel: K(x,x') expl م for 0. The Laplace Kernel is very similar to Gaussian Kernel, and one can check by similar steps that when O0 Tog(F) Laplace gram matrix is diagonal dominant.
C
LEMMAS
This section includes two useful lemmas for characterizing the eigenvalues of symmetric matrix. Lemma 19 (Gershgorin circle theorem, restated for symmetric matrix). Let A Raxx be sym- metric matrix. Let Aij be the entry in the i-th row and the j-th column. Let
Ra(A) = Σ Aggle 1 1,....n
j
15

---

Under review as a conference paper at ICLR 2022
Consider Gershgorin discs
D.(A) :- E 12 A&l - R.(A)), -,,,,,,. ,,..,,
The eigenvalues of A are in the union of Gershgorin discs
Furthermore, if the union of lo of the n discs that comprise G(A) forms a set (A) that is disjoint from the remaining n k discs, then (A(A) contains exactly & 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 E Ruxm be symmetric matrix, let y E R" and a E R, and let
y
Then
3 a
(A) 2 (B) 2 (2 ... 2 Am (A) 2 Am (B) 2 Am)1
Proof. See Horn & Johnson (2012), Chap 4.3, Theorem 4.3.17.
D SPECTRUM OF GRAM MATRIX
This section analyzes the eigen structure of the gram matrix.
Lemma (Characterizing Ka). Under Assumption we huve
(K, K;) E [}] x + - 1
(11)
KK, K2)1 S 22 + (n 2)
(12)
Proof. For (K,, Ki)
(K,, Ki) K2,- + Σ K7,
E [A X3 + (n-1)
And for (K K2), i5)
(K, K2)l=
Σ Ki,l 1=1
= Kij + Kj Kis + Σ Kirkisl
1925
$ |K + |K K5 + Σ
(
< + (n
< [2\1 + (n 2)
Lemma 22 (Eigenvalue of K). Under Assumption 1, we have
mn S A1 + nr
(13)
Jn An NT
(14)
we further assume X3 + < Aj-1 nt, will have
7--1 Aل no > Aラ no 2g
16

---

Under review as a conference paper at ICLR 2022
Proof. Use Gershgorin circle theorem, calculate
[((K)
Σ
|Ki S nt
then
D((K) C. -
nT, A + nr].
By Gershgorin circle theorem, the lemma claim holds.
L
Lemma 23 (Characterize P,K and P-IK), Recall our definition: P-1 is the projection on column space of K-1 [K2, Ka...., Kn and I P-1- 1. We claim the following hold
PKK- = 1 0
(15)
P-1K [ 2.... K2
(16)
Assume T small enough that no 1 (1)), An nt 2 c1 0 and X1 + no c3, let c3 we have the following:
9 then
||- Kill2
[0, (2)) + (n 1 2)T)
(17)
|| K |
/ 2222 (n 2)7] A vnT
(18)
Proof. For i + 1, we calculate
P-IK; K; P.K: K; - P- =
thus have equations (15) and (16).
For 1PP1KK) 2|:
|| PP-KK K1ll2
= K (K (K-))1113 K 12
< K- (K ||2 K K
K-1,
where
|K_, 1
Σ (K? K2)
(12)
$ (n 1)(2X ()
<(2>) + 2
and K has all eigenvalues in |/ 71 by Cauchy interlacing theorem (Lemma 20), that is, all singular values of K_1 are in [c1, by our assumption. Then
|| (K3 112
S C2 2
:
So we have
|P-1K
K (K? ( (K< 122 Kill2
cg (2 (n 2)T]
For [|P K2Ki
K K2l2 S |
< <11 + (n 1)
<> + Vnt
17

---

Under review as a conference paper at ICLR 2022
and
| K K1l1
K1, -1
zx - og(22s + (n -2)
Lemma 24 (Spectrum H-1 == P-1 P-1KK 1-1PP-1.. Assume
2 + (n 2)7]2n² 22221 + (n-2)r/nrt S 22
We have the following:
0 is an eigenvalue of H1,, corresponding eigenspace is the column space of Pi:
Restricted to the column space of P-1. the eigenvalues of H-1 are all in the interval:
(> - [2X] + (n - 2)T X3 + [2d1 + (n 1)r(nr).
Proof. The first claim by construction of and P-1- For the second claim, note that H-1 has the same eigenvalues as
H' (P-K)*P_1K
Now the diagonal entries of H²_ are:
111 G + 2)7
,i=1
(H'1)a = |P- K. 112
K 1 E (X] X + (n-1)7
.
And the off-diagonal entries of H' are:
(HH'))< ((P K, P-, K2), (K, K2)1 - [2 + -
To use Gershgorin circle theorem, calculate
R&(HL')) Σ 1(HL))1 < [2 + 2)
8#1
Thus the Gershgorin discs:
Di(HLL) E (I)P,K K, 11 [2)1 + (n- 2)r]nn, PP,, Kg [/ + [2>1 + (n 2)r(nr)
D;(I'L)) (1) 2 - [2A] (n 2)7] | + [2 + (n 2)T(nT)
(n-2)7)np | the first Gershgorin dises does not intersect with the others, so we have n nonzero eigenvalues in
when c3 (( (n-2)) 2)n [2Ar + (n 2)r S - -2X1 +
(L C (2, - [2A1 + (n 22))2r,, X3 + 22 + (n 1)r]ar).
E DIRECTIONAL BIAS OF SGD WITH MODERATE STEP SIZE
This section gives formal proof of Theorem 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 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.
18

---

Under review as a conference paper at ICLR 2022
Lemma 25 (One step update of SGD). Under Assumption 1, denote A, P 12]. B,
b fix a constant 01 2 (A1 + (2X) + (n ( 2)T)C3, then we have:
A++1 S 91 (1) 4, + B
(19)
A++1 2 (1(1) E(7)
(20)
Bi+1 S q-1 B: + E(n)At
(21)
where
(1(1)
n
- [| - 1j P1 K 1
1
11.
|KP-bb;ll
g-1(n) 1
[<2 + (n 1))²) - -2n
n1l r
{(n) c17m 1/2T.
Proof.
One step of SGD update is:
bi+1 b K b, [T K
where is uniformly random sample from n.]. For inequalities (19) and (20), check
P b
[ nK RK bb,
P.b. RP,K (P: + P-1)b;
= - K K.)P,bb -
P-1.P-1b-
where K;K; and P,b, are in the same 1 dimensional linear space, thus
K. P.b.
P1 |12121111 P. belllsiig(((P111 (.b.))
P. PIbb, [ TLIKKK P.P.KK [1 17 P. P 113)
and
||P P-1le-bbell
< PI 11
Then
< E||1 - 7/ P1 111k://||||10000011/11///1///323
(22)
bb 2 E|[1 7/ P K 1PPP://--PEE|PPPKKk//////1111111
(23)
where
El
7/
P. Pr 11
1
Σ
n/ Pi K ||
71 i=1
n
+
|1
( (1)
and
1
11
PP 12 K
Pi K1 || P-1 K1l12
(>1 + Vnr)cs + - 2)))mm
(n
< T
"caVro E(n)
(24)
19

---

Under review as a conference paper at ICLR 2022
where the first inequality by upper bounds (17) and (18), second inequality by I O1). 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_ P-1b+t1 = P-1 K 1b,
= =II- K, K P- P-IPP_18 b. -n|P_, Pi)P,b.
Then we have
F||| [ 1bt+1|12/bb [22
||| _P-,K, - 1 Piblll2
(2) 1 R
|I| - 1_ b.1l2 P/bbll
7
where
[ K_- P.
VIIL - nP-KKk P-1K--1--
KK P- P-Ib-
2n)l|P_bbell
P
K P- P- )2 (17 P_ K
27) b-1bl12
P b
where the last inequality from Jensen's 's inequality. Now the term
K.P..PP. P_ b2)
PP-1bell (1'11- - 2n)
72
(I)
(KPP P_ P- P_)b,²²
[17 (x2 + +(n (112) 2n]
71
|P--bbll13
|KP_ 1
[72 + (n - 1)72) 2n]
n
P by 2
Let
KPP b. 12 n|| P.
(n)
[np( + -n-117 2nl
combine all three inequalities above, take the expectation w.r.t. b,, we have claim (21).
Lemma 26 (Long run behavior of SGD with moderate step size). Assume by is away from 0. X (2)) + (n - -2))) + C4 /nTT X3 + covner < X² - cs VuT where os CB are constants such that
c5 G22 (n - 2) +
20

---

Under review as a conference paper at ICLR 2022
C6 2 VnT enn 2/n-0//112, (2) + (n 2)r )r] + X3ea/ (A,
(2X, + +(n 2)r/n7
1 CAV/T/ (2 + (n - 2)
Consider first kn steps of SGD updates with step size
2
< 11 < X3 CBV/TT
-
Fix 30 Ag. then for 0 and
< Bo such that /nr poly(e3), there exists
k1 = Ollog (5) satisfying:
Bag EeB
Ak liboll2 p + for some P1 > 1
As > for k- 0, O.....k1.. k1.
Proof. For this choice of in, denote 91 (1)) 9-1())) E(n). By Lemma 21, we have
A A
B
Ax BR
91
8
A
I
9-1
B
Decompose the coefficient matrix as
in
cos 0 sin 0
-in 0
[
0
cos
sin
q-1
cos 0
p-
-
sin 0 cos 0
Assume w.l.o.g. that sin 0
2 0 ( since otherwise we can take 0 - + T), then we have
Ak
Ao Bo
B&
E
Q-1
coos
sin 0
Tp
cos 0
sin 0
[A
sin 0
cos
[0
- sin
cos 0
[B
Ao(ph cos? 0 pt: sin 0) + Bolof cos O sin 0 - p* cas 0 sin 0)
BolpE cos? 0 + pî sin? 2 0) + Ao cos 0 sin 0 - p=_ cos 1 sin 0)
Aupt + (pf p²: sin A( Bu cos Ag sin 0)
Bop 1 + (p) p²n) sin 01 Bp sin 0 + Ao cos 0)
Anpi + 10t /²= sin / B3 A
Bop + lpt p² 12"I|sn sin BB AQ
Anpi + lot p² sin 0 bool2
Bop 1et
sin 0 bulle
We claim the following holds:
0 < p< p-1 < 1 <
(25a)
/ |bol2 S cB/2
(25b)
/ |boll sin 0 < cB/2
(25c)
(Bo + eBo < (gi 1)80
(25d)
which we check later. Using inequalities (25), we can upper bound BR,
BR, S _ + (pt - م² sin
sin bullz
< |bollap + p sin 0||bol12
(250)
21

---

Under review as a conference paper at ICLR 2022
In addition, for 1: O,...,K3 K1
By S Bop + (0 - ) boll2
S Bg + p\ sin 0|lbol12
(25e)
B + cB/2
We now lower bound A₃ by mathematical induction. We have Ao 2 Bu. assume Ak-1 > Bo. then
A 2 41 -
2 2180 -E(Bo + eB/2)
(25)
91 - (4) - 1),30 = 3o
For upper bound Ak,, check
Ak S Aopt + (pf - -0 sin 6 |bbll
|0ollz0 to + p sin 0 bool2
|bbll2p1 k: + eB/2
We have all lemma claims proved. Now it remains to check inequalities (25). First note that our choice of the upper bound 1) guarantees that g-1 < 1.
For inequality (25a): By Gershgorin circle theorem, it suffices to show q-1 + & < 1,,9 - >>> 1, then we have p1 2 F1 - & > 1 and p-1 S 9-1 + & < 1. In addition, we need the matrix to be positive definite so that p-1 > O, we just need 919-1 <² to make the matrix p.d..
9-1 + E < 1
|KP b
(n + (n 1)r2) 2n] < 1 cann -1/2g
11 P-1 b
|KP_ b 11
[n2 + (n- - 1)72) - 2n] < 22n1"n-177 - -2camm 1/2
n bb
22017m 1/2 S 2 112 + 1a - 12 + (n - 2)r|nT
Lemma
[2n- 12m-12(A3 (n 1)7?)]
22- -121 + (n 2)T nT NUT
[1g + (n 1) 1 cnn 22n
n
X2
1221 + (n 2)T|ur
< n2=
2r.m 1/27
n
1 1- C4 C / 1\ - 12\1 + (n - 2)TT|T7]
[1) S 2
1/ + (n - 1) - c272 [22 - 12>1 + (n 2) |nr]
2
+1 S
X3 (n-1)r=- -3 24,+(n 22////2/ + 13 / 1A 12 -2 [r]]]]]]]]
1-CeVRr/ 1A% 12 +(n 2)5 [T]
which is true by our choice of n-
41 -->1 1
n 1
+ -1 1- || cpnn- 1/2, > 1
n
n
+ C/T///TT
< 11 - 7|| P1 K |
< P |
1>> 1 + canVnn
2
<1>
PP,Ki K,KK1'3
12
C4 C4V
2
X
22
(n (1-2)7P272 CAVTT
22

---

Under review as a conference paper at ICLR 2022
which is true by our lower bound 7)-
919-1 > E
9 _5
|KPP-bbll 12
=1
[ (n- ( - -2n] > camm=11 1/27
n|PP_bbelE
23 + (2)1 + (n 1)T)NT
211
c47m 1/
n
+1 2X + 2(22) + (n 1)T)NT + CaNTIT
which is true.
For inequality (25b): It suffices to take
1 eB Ollog
k1 = log(p-1)
For inequality (25c): We just need to show sin < (p-1/p1)5.
Calculate that
E/(g1 - q-1)
ons 0- 0-sin p then
cos
sin 0 (p-1/p1)*h
- </ - 9-1) < /09(p-1/p1)) #1
= < <0.9(g) -9-1)( 9-1 -
5 ybu
41 +
= f 0.99g1 -- 1 (e8/ 112)
1-610-1-8)
{ < (11 - 11)ool((e8)
nT S poly(ee)
For inequality (25d): Suffice to show
(a) - 1)30
8 Bo + eBo/2
- v S 0(1)
Lemma 27 (Long run behavior of SGD with small step size). Under the same notations and as-
sumptions as Lemma 26 unless otherwise specified. Consider another k2 - k1 steps of SGD update with step size
+T
where the constant 07 Vnt + C4. Then we have fore kii
By EB
As 5 { {
9Ak-1 Ag-1 8
.A 3
where q (1))) E(n')c 1.
Proof. Denote oi = (n(n"), = 9-1(1') = E(7'), then 41 + g'e, denote B = bullz
A + cB/2. We have by proof of Lemma 26 that q²_ + < 1. We claim the following holds:
q 1
(26a)
{ < - (1-4)<,
(26b)
23

---

Under review as a conference paper at ICLR 2022
Check inequality (26a):
1 + f'e <1
1
+ K [22| can'n 1/2 1/27 <
n
= 1/ P. K1 1b < can' VnT
C47/ V < q/ | K 12 <2 caai V
TT < K 12
| K 11
vur < O1)
n/ < xptur+trvnn
which are true by assumption.
Check inequality (26b):
(1- 933
Scv/n 1/2 ( of + eB/2) S (1 n n-1 -1- K 1 Dent (nullbulll * exp(11) loge 108 + cB/2) S //
n
-VTr S p))
With (26) we can prove the lemma by mathematical induction. Suppose BE-1 S EB and Ak-1 S AR, < B, then check
B& S 5' Aa-1 + dL,B
< c0
(26h) S eB
and
4 S q A + E'Bu-1
S o Ax-1 + ECB
< (o' + f'e) max (s
$ { 9Ax-1 A > 8
q8 < A < 8
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 defined in Lemma 26 and 27. Assume nt < poly(e). then there exists k = O(oo 1 and k2 such that
Ell Kbb
(1 2e) <
< 71
E bky
[|]
where YI, is the largest eigenvalue of K.
Proof. In Lemma 26 let 9 33, then for h Olog 1) we have BE, 5 EBg. For the 2nd stage, by Lemma 27 we can early stop at ly such that Ar, 2 30 and Abtt1 < Bb. We then have
B&g cBo S CA
24

---

Under review as a conference paper at ICLR 2022
Then check
E1| K KK 112
E bk 1|
E IKP bx
+ |KP, bkg 2
f P_1
b
K P b
E / KVKKsbb bkc
12
P K K 2 bbal
E bb 1|e
V K 1.bbal
/ P-1 K1 112 P1 K
6ka
bkz
K P Pibkall 1|
P K 112 P1 K 2
bkg 12
E 1 ll2
(177(18 2
E E Pibr,
- 2222 + (n 2)r
Pibg 12 + E1 P- 11bb
22(11 + (CT) + (n 2)T)/nT)
8o
2v 17 - -gg221 + (n 2)T) nn72
v 2((11 + VTT)(c + (n- ()T)//
$ 900
(1)
2 (n n1 c3(2\1 + (n- 2)r) nT) - - 22(21 + (es)) + (n- -22))
(1 - c) - nc (By no < poly(c))
=M 2E)
And the upper bound in the theorem is by definition of 71-
F DIRECTIONAL BIAS OF GD WITH MODERATE OR SMALL STEP SIZE
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 GTG r diag(T)... ... To); G (g1........ gn.
where the eigenvectors gi 's are orthogonal. The GD update as
7 K(Ka y) a++1 = Q
n
Denote w, : GT (ar â),, we can rewrite GD update in wt:
W++1 w. " r =
1 2 r2)
n
n
We recap Theorem to make reading casier as follows: Theorem 29 (Direction bias of GD). Assume oig is away from 0, An + 2nt < An-1, GD with step size;
n
< (A1 + nT)²
For small 0, take l Ollog !), have
[K(as - 2)l12
i' <
< VI+eT
| -all2
25

---

Under review as a conference paper at ICLR 2022
Proof. For i ,,..., n, we have
Wh (1 m / v0 (8)
(3)
1////n. Denote qi = -1-17/// n,, then 0 91 S ... 9n < since
n
(13)
11
n2
0<n< <
<
(11 TT) 2
71
7
Since An +nT < An-1- nt, we have In < nn by lemma 20, it follows that 9n 9u-1. Denote q 1/91/ < 1, then
i=1 (wkk (2)
(w (m))
1-1 1 92th (w)
(8) )2
(n) y²
9% (wD
22 24 (w)) (2)
i=1
2 (wo
(m) y
2k Dí 5-11 (wi (2)
(wb (1))
72 e(mp (1)
log
Let 2h <
k >
7f Σ ((m)
Olog t), we have
79 Σズ-1 (w)
log 9
Σ (w 12
2he
I
(wk 1)
71
Thus
| 1K(as - -0
0% 2
|1 112
Σm (w0 (1) p29
Dm=1 (w)
(w)) (1))))2 1272
Di=1 (w/ )2
(w (2) )2
Σ Fizl (a0b) (1))
im
Σ (w)
(1)
)22
$ 1m
71
Σ (w) (1)
S im
+ 11
7
in
= 2 +
711
thus
K(a: - -x)l2
S (1++
| - 6 12
The lower bound of the theorem holds by definition of 7n-
G EFFECT OF DIRECTIONAL BIAS
In this section, we provide the proof for theorems in Section 4.2. There are two theorems there, so split this section into two subsections. Subsection G.1 proves Theorem 9, for a general problem setting of squared error minimization, 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.
26

---

Under review as a conference paper at ICLR 2022
G.1
PROOF OF THEOREM 9
Denote w w"" rewrite the objective function as
min ||
s.t. ||Av
Denote the eigen decomposition of A A QIQ" where Q [q.,..., vnl. QQ" QQ" =
and I = Pol), 2 2 Pn 2 0. Then
||A = Σ p: v)²
So
|| 2 S p1
= = pillol12
The equality is achieved when v is in the direction of qı and P = ||A"A||, || then the theorem holds.
Take L(w) =
G.2 PROOF OF THROREM 11
Calculate A Denote f â K"K(.,X) + f, then have for a f E H.s f a (²((,,),, let
= a. then
|1 - -11
[|,"x(.,XX) + fll
=1|b² K(, (x)x) + +15
-2( K(, XI,
where we can check
(b" K(, fI (.(( f" a."(,XX))n
Σ (, (ii), 8(x - (K(: (;)));;). à ())))
E belff à K( (By reproducing property)
be(yn vil
And we further calculate that
n
| K(,, x)1
b. xx), Σ b, K b,
(kb (,, 2;:,, K ((,xx)))
i=
Σ
b,by (b;, 2.) kb Kb
1==1
That is,
Lp(f) = b"t Kb 11111
and
inf LD(f) 11.11124 SEH,
27

---

Under review as a conference paper at ICLR 2022
It follows that
A()) = LD(f)
inf LD(f) = b" Kb SEH,
Kb
We claim that
A
mi K =
6a kb
|Kb]2 = 2na/m 71
where the equality is obtained when b is in the direction of the largest eigenvector of K. To this, we check | & 71 6 Kb. Recall the eigendecomposition of K GT' where G
g1...... [n] has orthogonal columns and I' = diag(nn.1. ................................ 7n). Then
|bb = Σ 1/ (g,
and
bo Kb = Σ
76 7g
t=1
So we have
|Kb S 71 Σ (99T -
Kb Kb
This finishes our claim on A
SGD output: By Theorem 5, the SGD output has
2e)m
E[ bballa) S El]] 2
Thus
E ( E
mg bSGDja
S F
gf T SGD 2BSDD)2)111 22)1/2)
< 12
VTT Kb ||2/ 26)ml
= /naa//////// 2c)
(2 2e
< (1 (2)
last inequality by let e < 1/4.
GD output: By Theorem 7, the GD output has
Kb K
< (1 + +2h
bGD
28

---

Under review as a conference paper at ICLR 2022
Thus
n
A(JOD) = Σ
7/ 1g b baD)2
b
2 In
2 ml|KKGD
12/1(1 c'
= 2na/((1 + +mm
71 4
(I+ cn
n1 (1 E))
mn
MA.
where M by taking e' <1 7n/71-
H EXPERIMENTS
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
FashionMNIST, including the data description, network structure, and algorithm details, also there are more experiment results in Subsection H.2 that not listed in Section 4 due to page limit.
H.1 SIMULATION
This subsection is corresponding to Figure 1.
Data Generation. The training data simulated as follows: Set n 10, 100, simulate Xaxp where elements of X are i.i.d. N NO, 1); denote ith row of X as æ;, normalize æ; such that it has squared l2 norm in [.49, 1}; set yi = Ei=1 sin(2i.)) + c where G s.i.d. .01...).. The testing data simulated in exactly the same way, except that we only simulate
testing data.
Kernel Function. We set the kernel function to be the polynomial kernel
K (x1, 222 = ((11,02) +01)²
SGD and GD implementation. Both SGD and GD run for small and moderate step sizes. The moderate step size scheme for SGD is: 7) .1 for the first 50 steps, and 7/2 .01 for the next 1000 steps; for GD is: 71 = .5 for the first 50 steps, and 7/2 = .05 for the next 1000 steps. The small step size scheme for SGD is 1 0.01 for 1050 steps; for GD is n 0.05 for 1050 steps. Note that the step size for SGD is fraction of that for GD, this matches our Theorem and 7 that the step size of GD is of magnitude n1/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 [o, 1].
Network structure. we use 6-layer ResNet-like (He et al., 2016) Neural Network, and the struc- ture is follows
Input + x 7 Conv = BatchNorm = ReLU = 3 x MaxPool
ResBlock1 = ResBlock2 Global AvePool = FC output
29

---

Under review as a conference paper at ICLR 2022
The Residual Blocks Figure 7.6.3 in Zhang et al. (2021) (without 1 x 1 convolution). Note that each residual block contains two 3 x convolutional layers, thus total number of layers as stated.
Algorithm. We minimize the Cross Entropy Loss objective L(w) Ei= 4(w), where ((w) is the loss function at ith sample. One step SGD is follows:
# ut 1)t
(l((w)
VEI
where / a randomly sampled subset of {l....,,) (uniform random sample without replacement)) We choose the batch size [ to be 25.
One step GD is as follows:
w w. 1/e VT.(w)
Both SGD and GD are run using two settings of step sizes V)- The moderate step size setting is as follows:
0.2, { = 1,.... 5000
// = 0.02, [ = 5001, 20000
And the small step size setting has 17: 0.02, = 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 Quo- tient(RRQ), which normalizes the Rayleigh Quotient by the maximum eigenvalue of the Hessian as follows
V [V
V
VL(w) LV
RRQ(w)
V2L(w)ll
where Lwwr is the loss function the whole training 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 rum: 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.
Experiment
#1
#2
#3
#4
#5
#6
#7
#8
#9
#10
SGD moderate LR
83,69
82.95
82.37
82.05
83.4
83,16
83.72
83.29
83.28
83.23
GD + moderate LR
80.93
80.79
80.79
81.80
81.68
81.12
82.43
81.63
80.94
81.54
SGD + small LR
82.00
81.72
81.34
81.92
82.63
82.67
82.99
82.22
80.78
82,10
GD small LR
78.88
78.71
78.49
79.3
80.45
79.78
80.15
79.66
79.54
79.68
Experiment
#11
#12
#13
#14
#15
#16
#17
#18
#19
#20
SGD moderate
83.12
82.92
83.58
83.47
82.35
83.57
83.59
82.43
84.21
83.
GD + moderate LR
82.41
81.56
81.42
80.86
81.23
81.25
81.82
80.42
81.80
82.12
SGD + small LR
82.62
80.66
82.01
81.01
81.32
81.66
82.12
80.78
82.28
82.48
GD + small
80.08
78.29
79.93
79.36
78.9
79.69
80.2
79.62
79.98
79.69
Table 1: Test Accuracy
We also use one-side Wilcoxon signed-rank test 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.
Null Hypothesis on Test Accuracy
p-value
SGD moderate LR < GD moderate LR
9.54 x 10
SGD + moderate I.R < SGD + small L.R
9.54 x 10-7
SGD + moderate LR GD + small LR
9.54 10-r
Table 2: Wilcoxon signed-rank test result
30

---

Under review as a conference paper at ICLR 2022
85.0
85.0
82.5
82.3
80.0
80.0
Test accuracy
77.5
77.5
75.0
75.0
SGD, size 0.001 (76.9)
sire 0.001 (77.13)
SGD, size 0.005 (80.93)
sire 0.005 (79.91)
72.5
72.5
SGD, step size 0.01 (81.81)
size 0.01 (79.98)
SGD, step size 0.02 (81.76)
size 0.02 (79.98)
70.0
SGD, step size 0.1 (82. 69)
70.0
GD, stop size 0.1 (80.96)
SGD, step size 0.2 (83.41)
GD, step size 0.2 (81.45)
67.5
SGD, step size 0.5 (82.82)
67.5
GD, step size 0.5 (81.65)
SGD, slep size 1.0 (02.50)
GD, slep size 1.0 (81.2)
65.0
5000
10000
15000
20000
65.0
5000
10000 iterations
15000
20000
itcrations
Figure 3: Use more step sizes in SGD/GD. The test accuracy is evaluated once every 500 iterations, and inside the bracket the average of the last 5 test accuracy values.
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 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.
31


Reviews:
[{"review_id": "oXR3aqAGj59", "reviewer": "Reviewer_EcVL", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Pros:\n+ The paper is very well written and easy to follow. Related works are well discussed.\n+ Prior work only shows the directional bias of SGD for linear regression. It is good to learn that the directional bias of SGD also works for kernel regression.\n\n# Cons:\n- Most of the proof techniques are from (Wu et al. 2021). Given prior results for linear regression, an extension to kernel regression seems a bit incremental to justify a conference paper. ", "summary_of_the_paper": "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. ", "summary_of_the_review": "I cannot recommend an acceptance to this paper as most of the results are more or less incremental given prior work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "cdyRq_wHFAc", "reviewer": "Reviewer_RGP1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is interesting and deals with a very important issue: generalization in simple problems, and the effects of training with SGD compared to GD. Focusing on simple tasks is very powerful and definitely we need more insights in this direction. However, I think the paper has a few drawbacks and deserves a few months of more work. Here are some concerns/questions for the authors. I will read the review, discuss with the authors and potentially upgrade my score.\n\n1) The main concern I have in the link to generalization and the link to properties in the *training* landscape. Theorem 8 is trivial and is well known, however the link to generalization definitely does not follow: A is the training matrix, and GD converges exactly to w^* – the problem is that the w^* in test loss is different! In general, even though i might be missing something here, I invite the authors to tone the claim down: \"explaining generalization\" is the the holy grail of ML, such cold claims are somewhat unacceptable in published research.\n\n2) Theorem 4 and 6 are nice and novel, however how do they compare? I have read Remark 7 but I do not feel like this is good enough: for SGD you use 2 different stepsizes and you also have a particular choice dependent on the C_i constants. My question is simple: lets take eta = 0.01 for both GD and SGD, fixed during learning. does the remark still hold? why? Please, show this experimentally (yes you can, and its a different setting compared to figure 1)!\n\n3) Going exactly to experiments: why is there no experiment on generalization for kernel regression? your paper is about that! I would be surprised if you find that SGD generalizes better than GD in a fair setting (i.e. you tune the methods, and you use the same tricks for both). \n\n4) Second experimental concern: why in your FMNIST experiment you do not select the same stepsizes ranges for GD and SGD? You do not show GD performance with the \"moderate stepsize\" you have in SGD\n\n5) Suggestions/ typos\n- explain better directional bias in the intro\n- typo in sentence \"we prove that a two-stage SGD has b_t converges in the direction of the largest eigenvector of K\"\n- again typo  \"that GD hasbt converges\" before thm 6 \n", "summary_of_the_paper": "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.", "summary_of_the_review": "The topic of the paper is very nice, but I have some concerns and hope to have a nice conversation with the authors!\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VPETcuXesHH", "reviewer": "Reviewer_aXTx", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nBasically, this paper is well organized and the results are clearly presented. However, my major concern is regarding the novelty of this paper, given the closely related prior work [Wu et al., 2021].\n\n\n**1.** It seems that given Assumption 1 and Proposition 14, the model is pretty similar to the linear setting considered in  [Wu et al., 2021], while the only difference is to replace the Gram matrix in  [Wu et al., 2021] with kernel matrix. \n\n**2.** It is true that the SGD algorithm considered in this paper is different from the epoch-wise SGD in [Wu et al., 2021], but it seems that the proof technique will not be that different as claimed by the authors. One difference I can see is that when using SGD in steps, one can focus on the expected components of the iterates along different directions, while for SGD in epochs, one can directly calculate the components rather than taking expectations. The authors may need to clearly clarify the difference in the Introduction.\n\n**3.** Can you provide some intuition regarding the case when the gram matrix is not diagonal dominant? Does the result still hold or can the proof technique still work?\n\n**4.** Experiments in figure 2 are basically the same as those in [Wu et al., 2021], could you clarify some differences between them? Otherwise, these experiments may not be necessary since they do not provide any new message.\n\n**5.** Regarding Assumption 1, it would be better to provide some example kernel functions and data models right after this assumption rather than deferring them to Appendix. \n\n==========================\n\nThanks for your response. I suggest you revise your paper accordingly at least to highlight the difference and novelty compared to [Wu et al., 2021] .  Besides, it could be better if you can consider more challenging settings (e.g., the gram matrix is not that diagonal dominant), which could be closer to the practical cases.", "summary_of_the_paper": "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. ", "summary_of_the_review": "Given my concern about the novelty and contribution of this paper, I do not recommend acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is an interesting paper, aiming to separate the generalization properties of SGD and GD.  Unfortunately, the reviewers had many significant concerns, primarily on the topic of the relationship to prior work by Wu et al. (which has a similar setting and similar proof techniques), but also regarding presentation and interpretation of results in general.  As such, I recommend the authors continue with this line of valuable work, aiming in particular to further separate it from existing results.
Decision: Reject