Direction Matters: On the Implicit Bias of Stochastic Gradient Descent with Moderate Learning Rate
Authors: Jingfeng Wu
Difan Zou
Vladimir Braverman
Quanquan Gu
Venue: ICLR 2021 Poster (2021)
Keywords: SGD
regularization
implicit bias

Abstract: Understanding the algorithmic bias of stochastic gradient descent (SGD) is one of the key challenges in modern machine learning and deep learning theory. Most of the existing works, however, focus on very small or even infinitesimal learning rate regime, and fail to cover practical scenarios where the learning rate is moderate and annealing. In this paper, we make an initial attempt to characterize the particular regularization effect of SGD in the moderate learning rate regime by studying its behavior for optimizing an overparameterized linear regression problem. In this case, SGD and GD are known to converge to the unique minimum-norm solution; however, with the moderate and annealing learning rate, we show that they exhibit different directional bias: SGD converges along the large eigenvalue directions of the data matrix, while GD goes after the small eigenvalue directions. Furthermore, we show that such directional bias does matter when early stopping is adopted, where the SGD output is nearly optimal but the GD output is suboptimal. Finally, our theory explains several folk arts in practice used for SGD hyperparameter tuning, such as (1) linearly scaling the initial learning rate with batch size; and (2) overrunning SGD with high learning rate even when the loss stops decreasing.

Published as a conference paper at ICLR 2021
DIRECTION MATTERS: ON THE IMPLICIT BIAS OF STOCHASTIC GRADIENT DESCENT WITH MODERATE LEARNING RATE
Jingfeng Wu
Difan Zou
Computer Science Department Johns Hopkins University Baltimore, MD 21218, USA juujfe jhu. edu
Computer Science Department University Californi, Los Angeles Los Angeles, CA 90095, USA knowzou vela a. edu
Vladimir Braverman
Quanquan Gu
Computer Science Department Johns Hopkins University Baltimore, MD 21218, USA vovaâcs, juu.edh
Computer Science Department University of California, Los Angeles Los Angeles, CA 90095, USA gggucss w.w..cllce... edu
ABSTRACT
Understanding the algorithmic bias of stochastic gradient descent (SGD) is one of the key challenges in modern machine learning and deep learning theory. Most of the existing works, however, focus on very small or even infinitesimal learning rate regime, and fail to cover practical scenarios where the learning rate is moderate and annealing. this paper, we make an initial attempt characterize the partic- ular regularization effect of SGD in the moderate learning rate regime by studying its behavior for optimizing an overparameterized linear regression problem. this case, SGD and GD are known to converge to the unique minimum-norm so- lution; however, with the moderate and annealing learning rate, we show that they exhibit different directional bias: SGD converges along the large eigenvalue di- rections of the data matrix, while GD goes after the small eigenvalue directions. Furthermore, show that such directional bias does matter when early stopping is adopted. where the SGD output is nearly optimal but the GD output is sub- optimal. Finally, our theory explains several folk arts in practice used for SGD hyperparameter tuning, such as (1) linearly scaling the initial learning rate with batch size; and (2) overrunning SGD with high learning rate even when the loss stops decreasing.
INTRODUCTION
Stochastic gradient descent (SGD) and its variants play key role in training deep learning models. From the optimization perspective, SGD is favorable in many aspects, e.g., scalability for large-scale models (He al., 2016), parallelizability with big training data (Goyal et al., 2017), and rich theory for its convergence (Ghadimi & Lan, 2013; Gower et al., 2019). From the learning perspective, more surprisingly, overparameterized deep nets trained by SGD usually generalize well, even in the absence of explicit regularizers (Zhang et al., 2016; Keskar et al., 2016). This suggests that SGD favors certain "good" solutions among the numerous global optima of the overparameterized model. Such phenomenon is attributed the implicit bias of SGD. It remains one of the key theoretical challenges to characterize the algorithmic bias of SGD, especially with moderate and annealing learning rate typically used in practice (He et al., 2016; Keskar al., 2016).
In the small learning rate regime, the regularization effect of SGD is relatively well understood, thanks to the recent advances the implicit bias of gradient descent (GD) (Gunasekar et al.. 2017; 201 Sa;b; Soudry et al., 2018; Ma et al., 2018; Li et al., 2018; Ji & Telgarsky, 2019b;a; Ji et al., 2020; Nacson et al., 2019a; Ali al., 2019; Arora al., 2019; Moroshko et al., 2020; Chizat &

---

Published as a conference paper at ICLR 2021
GD SGD
SGD
1000
5A-
0.4
-12
-02
-1A
-0.4
3.6
(a) Small learning regime
(b) Moderate learning rate regime
and We (0.6, 0.6). (a): Small learning rate regime. The small learning rate is 0.1/k. In this regime SGD and GD behave similarly and they both converge along e2. (b): Moderate learning rate regime. The initial moderate learning rate is 1/ 1.1/x and the decayed learning rate is ry' 0.1/k. In this regime GD converges along e but SGD converges along e1, the larger eigenvalue dircction of the data matrix. Please refer to Section 3 for further discussions.
Figure 1: Illustration for the 2-D example studied Section 3. Here
Bach, 2020). According to classical stochastic approximation theory (Kushner & Yin, 2003), with a sufficiently small learning rate, the randomness in SGD is negligible (which scales with learning rate), and as a consequence SGD will behave highly similar to its deterministic counterpart, i.e., GD. Based on this fact, the regularization effect of SGD with small learning rate can be understood through that of GD. Take linear models for example, GD has been shown to be biased towards max- margin/minimumm-nn norm solutions depending the problem setups (Soudry et al., 2018; Gunasekar et al., 20;8a; Ali et al., 2019); correspondingly, follow-ups show that SGD with small learning rate has the same bias (up certain small uncertainty governed by the learning rate) (Nacson et al., 2019;; Gunasekar et al., 2018a1 8a; Ali et al., 2020). The analogy between SGD and GD in the small learning rate regime is also demonstrated in Figures ((a) and 3.
However, the regularization theory for SGD with small learning rate cannot explain the benefits of SGD in the moderate learning rate regime, where the initial learning rate is moderate and followed by annealing (Li et al., 2019; Nakkiran, 2020; Leclere & Madry, 2020; Jastrzebski et al., 2019). In particular, empirical studies show that, in the moderate learning rate regime, (small batch) SGD generalizes much better than GD/large batch SGD (Keskar et al., 2016; Jastrzębski et al., 2017; Zhu et al., 2019; Wu al., 2020) (see Figure 3). This observation implies that, instead of imitating the bias of GD as in the small learning rate regime, SGD in the moderate learning rate regime admits superior bias than GD - it requires a dedicated characterization for the implicit regularization effect of SGD with moderate learning rate.
In this paper, we reveal a particular regularization effect of SGD with moderate learning rate that in- volves convergence direction. In specific, we consider overparameterized linear regression model learned by SGD/GD. In this setting, SGD and GD are known to converge to the unique minimum- norm solution (Zhang al., 2016; Gunasekar al., 2018 8a) (see also Section 2.1). However, with moderate and annealing learning rate, we show that SGD and GD favor different convergence direc- tions: SGD converges along the large eigenvalue directions of the data matrix; in contrast, GD goes after the small eigenvalue directions. The phenomenon is illustrated in Figure 1(b). To sum up, we make the following contributions in this work:
1. For an overparameterized linear regression model, we show that SGD with moderate learning rate converges along the large eigenvalue directions of the data matrix, while GD goes after the small eigenvalue directions. To our knowledge, this result initiates the regularization theory for SGD in the moderate learning rate regime, and complements existing results for the small learning rate.
2. Furthermore, we show the particular directional bias of SGD with moderate learning rate benefits generalization when early stopping is used. This is because converging along the large eigenvalue directions (SGD) leads to nearly optimal solutions, while converging along the small eigenvalue directions (GD) can only give suboptimal solutions.
3. Finally, our results explain several folk arts for tuning SGD hyperparameters. such as (1) linearly scaling the initial learning rate with batch size (Goyal et al., 2017); and (2) overrunning SGD with high learning rate even when the loss stops decreasing (He al., 2016).
2

---

Published as a conference paper at ICLR 2021
2 PRELIMINARY
Let (x, v) E Rd x R be a pair of d-dimensional feature vector and 1-dimensional label. We consider linear regression problem with square loss defined {x;, y; w) (w To x y) where R is the model parameter. Let D be the population distribution over (z,, y). then the test loss is LD (w) := E(z.g)<D [e(1, y; w)] Let S { yi J== be training set data points drawn i.idd. from the population distribution D. Then the training/empirical loss is defined as the average of the individual loss over all training data points,
Ls(w)= = 1 - k(w), where ((w)) == E(1,1, W1, (w To I2
yi)²
We use {nk} to denote a learning rate scheme (LR). Then gradient descent (GD) iteratively performs the following update:
Wk+1 = WR T Ls(ww)= = W 2TT
n Zz (I; wkk - -y)).
(GD)
Next we introduce mini-batch stochastic gradient descent (SGD). Let b be the batch size. For sim- plicity suppose mb for integer m (number of mini-batches). Then at each epoch, SGD first randomly partitions the training set into m disjoint mini-batcher with size b. and then sequentially performs m updates using the stochastic gradients calculated over the mini-batches. Specif- ically, at the k-th epoch, let the mini-batch index sets be B . where [B]] = 6 and
U B3 .1, ..), then SGD takes updates follows
The b
(((w)s) wkj
21T Σ x. Wks -K---) j 1......, m. (SGD)
Wkii+ wkj""
iEB
We also write Wk+11 wk.++1 and Wkk Wk,1 1 to be consistent with notations in (GD).
2.1 THE MINIMUM NORM BIAS
Before presenting our results on the directional bias, let us first recap the well-known minimum- norm bias for SGD/GD optimizing linear regression problem (Zhang et al., 2016; Gunasekar et al., 2018a; Belkin et al., 2019; Bartlett et al., 2020). We rewrite the training loss as Ls(w) 1 | w 1| where X = (ZI,..., In) E Rdxn and Y = (Vi,..., BR) E R". Then its global minima are given by W. == {w E Rd Pw W., == X(XXX)-IY) where P is the projection operator onto the data manifold, i.e., the column space of X. We focus on overparame- terized cases where W, contains multiple elements.
Notice that every gradient (w)) = 2z, _ w o--wy y:) is spanned in the data manifold, thus (GD) and (SGD) can never move along the direction that is orthogonal to the data manifold. In other words, (GD) and (SGD) implicitly admit the following hypothesis class:
Hs = [w E Rd PIw w = powo),
where Wy is the initialization and P1 = I - P is the projection operator onto the orthogonal complement to the column space of X.
Putting things together, for any global optimum W, (hence Pw W.), we have
|| - woolloll woll 21 ||Pw Pwoll ||P w P1 wn 112 = llw. Pwol 112 |P P woll
where the right hand side minimized when Piw = P1 wo. i.e., w E H.s thus w is the solution found by SGD/GD in the non-degenerated cases (when the learning rate set properly so that the algorithms can find a global optimum). In sum, SGD/GD is biased to find the global optimum that closest to the initialization, which is referred as the "minimum-ne norm" bias literature since the initialization is usually set to be zero.
In this paper we focus on SGD without replacement, nonetheless our results and techniques are ready to he extended to SGD with replacement well.
3

---

Published as a conference paper at ICLR 2021
3 WARMING UP: A 2- 2-DIMENSIONAL CASE STUDY
In this section we conduct a 2-dimensional case study to motivate our understanding on the direc- tional bias of SGD the moderate learning rate regime. Let us consider a training set consisting of two orthogonal points, S = {I1, 0), (22, V/2 0)} where
21 = VR- 6 = (Vi, O)T, 12 02 = (0, 1)T K K> 2.
Clearly w. 0 is the unique minimum of Ls(w). (w). The Hessian of the empirical loss is V2 Ls(w)= d1a: + 222r22 diag (k, 1), which has two eigenvalues: the smaller one is contributed by data F2. and the larger one x contributed by data J Hence L.(w)) k-smooth. Similarly the Hessian of the individual losses are V & (w) 2
diag (2x, 0) and V (2(w) 2rgzd diag (0, 2). Thus ( is 2-smooth, but é (w), the individual loss for data æ is only 2x-smooth, which is more ill-conditioned compared to Ls(w) and (2(w).
Next we consider moderate initial learning rate 1f E ( ) According to convex optimization theory (Boyd et al., 2004), gradient step with such learning rate is convergent for Ls(w) and (w)), but oscillating for & (w)) In other words, (GD) convergent; and (SGD) is convergent along direc- tion T2 (or e2), but oscillating along direction T1 (or e1). We also see this by analytically solving (GD) and (SGD) for this example:
wd (11 (1-1k)* nK)*
(11-211)) 2m1c)*
(1 1 1))* Wo,
agd
(1- 21) wo.
(2)
where |1 - sp/c| <
(1-1)) 7/ < and |1 2nyl < 1 < |1 2/pa|-
[1
By Eq. (2), with moderate learning rate GD is convergent for both directions ei and e2. Moreover, GD fits e1 faster since the contraction parameter is smaller, i.c., |1 - mx] < [1 7| < 1. Thus observing the entire optimization path, GD approaches the minimum w, = 0 along eg. which corresponds to the smaller eigenvalue direction of V Ls(w). This is verified by the blue dots in Figure ((b). We note this directional bias for GD also holds in the small learning rate regime, as shown in Figure 1(a).
As for SGD in the initial phase where the learning rate is moderate, Eq. (2) shows it converges along 62 but oscillates along é1 since | 2ny < < 2/pks In other words, SGD cannot fit ei before the learning rate decays; however when this happens, 62 is already well fitted. Overall, SGD fits e2 first then fits e1, i.c., SGD converges to the minimum w. 0 along e1. which corresponds to the larger cigenvalue direction of V Ls().. This is verified by the red dots in Figure 1(b). We note this particular directional bias for SGD is dedicated the moderate learning rate regime; in the small learning rate regime, as discussed before, SGD behaves similar to GD thus goes after the smaller eigenvalue direction, which is illustrated in Figure 1(a).
The above idea can be carried over to more general cases: the training loss usually has relatively smooth curvature because of the empirical averaging; yet some individual losses can possess bad smoothness condition, corresponding to the data points that contribute to the large eigenvalues of the Hessian/data matrix. Then with a moderate learning rate, while GD is convergent, SGD is convergent for the smooth individual losses but oscillating for the ill-conditioned individual losses. Thus SGD can only fit the latter losses after the learning rate anneals. Therefore, in the moderate learning rate regime, SGD tends to converge along the large eigenvalue directions while GD tends to go after the small eigenvalue directions. We will rigorously justify the above intuitions in the following section.
MAIN RESULTS
In this section we present our main theoretical results. The proofs are deferred to Appendix B.
We specify the population distribution of (x, y) E Rd x R. in the following manner. (1) We consider the feature vector as x = Ç. where Ç and E are two independent random variables that represent the magnitude and angle of respectively. That is, Ç E R is bounded in (0, 1). and & E IRd obeys sphere uniform distribution, (4(5a=1) (2) We consider a realizable setting where the label is given by y w._ xr i.e., there exists true parameter w. E Rd that generates the label from the feature
4

---

Published as a conference paper at ICLR 2021
vector'. Then the test loss is Lo(w) ((zg)) [(w w.)] xx (w (w-w))] = w. w.112 where μ F /d. For i.i.d. generated training set 8 (10, V1) i== the training loss and the individual losses are
Ls(w) = 1 w - w.) XX - ww), (ww) = (w - w.) xæ (w -ww-w,) i= , where = (#1,..., In). We denote by P the projection operator onto the column space of X (the data manifold). For E [n]. we denote A; == ||0: S E (0,1]. Without loss of generality, assume {Ae) are sorted in descending order, i.e., X 2 d2 2 An. With the these preparations, we are ready state our main theorems.
4.1 THE DIRECTIONAL BIAS OF SGD
We first present Theorems I and 2 that characterize the different directional biases of SGD and GD in the moderate learning rate regime.
Theorem 1 (The directional bias of SGD with moderate LR, informal). Suppose d 2 poly (n) De-
note n/Vd (which is small). Then with high probability it holds that X1 A2 + + (v) An-12
An + (v), An > 9 (v). Suppose the initialization is set such that x, (wi - w-) # 0 for every
i [n] Consider (SGD) with the following moderate learning rate scheme
17 E ( ) 1/ (0, 28r)
k = .1; = ki + +1....,.2
m
then for e such that poly (c) > v, there exist 1n = (log _ + ki2) and h2 > 0 such that with high probability the output of SGD w == Wk, satisfies
(1-c) (P(wakd - w.)) XXX P P(waRd - w.) S 71
||P (waed - -w.)l2
where 71 is the largest eigenvalue of the data matrix XXT.
Theorem 2 (The directional bias of GD with moderate or small LR, informal), Under the same conditions as Theorem 1, consider (GD) with the following moderate or small learning rate scheme
T7e E (D. 2A1 (
n2
k ==
(5)
then for any > O, if h22 > O (log 2), then with high probability the output of GD wad Wkk satisfies
Iin S (P(wed w.)) XXT. P (wsd - w.) {11+ 7n.
(6)
IP (WRdd w. M|
where Ynu is the smallest eigenvalue of the data matrix X restricted in the column space of X. Remark 1. As the Rayleigh quotient (4) (resp. (6) converges to its maximun (resp. minimum), the vector gets closer to the eigenvector of the largest (resp. smallest) eigenvalue (Trefethen & Bau III, 1997). Thus Theorem I and 2 suggest that, when projected onto the data manifold, SGD and GD converge to the optimum along the largest and smallest eigenvalue direction respectively. Here we are only interested in the projection onto the data manifold, since SGD/GD cannot move along the direction that is orthogonal to the data manifold as discussed in Section 2.1.
Remark 2. In Theorem we use the gap between Xj and X2 to show a learning rate scheme such that SGD converges along the largest eigenvalue direction. This can be extended by considering the gap between Dr and A and the learning rate scheme defined similarly, then SGD converges along the subspace spanned by the eigenvectors of the top r eigenvalues. Similar extension applies to Theorem 2 as well.
"This is for the conciseness of presentation. Our results can be easily generalized to linear regression with well-specified noise. i.e.. noise that is independent of the feature vector.
"For two sequences (#,, 2 0) and {yn 2 0}: In = O (yv) if there exist constants > and N such that θ (y.) ) if x,, O (yn)) and ye O (#.). ). H. = o (sw) if for every >> 0 there exists positive constant N (e) > 0 such that
2., < Cy,, for every n 2 N;
Cy.. for every 2 N()::
poly (y.) if there
exists large absolute constant D > 0 such that v. = O (v!)).
"This holds with prohability if un is initialized randomly and follows, e.g., Gaussian distribution.
5

---

Published as a conference paper at ICLR 2021
We legitimately assume b < n/2 - (v)) since it is not very meaningful to discuss SGD that uses more than (roughly) half of the training set as a mini-batch. Then the learning rate schedule in (3) intersects with that in (5), i.e., (5) covers both moderate and small learning rate schemes. Their intersection determines a moderate learning rate scheme, where SGD converges along the large eigenvalue directions while GD goes after the small eigenvalue directions. This justifies the regularization effect of SGD with moderate learning rate.
Remark 3.
Remark 4. Technically, in Theorem one can set n to include GD as a special case, so that GD also follows the large eigenvalue directions. However, the initial learning rate in (3) needs to be at R 2 n. ignoring the small order term, which is way too large to be even numerically stable in least X1
practical big data cireumstances. This observation also directly supported by Theorem 2, where (5) specifies the runge of leurning rate such that GD converges along small eigenvalue directions. Note the upper bound in (5) linearly scales with n, and is large enough to include all learning rate that can be adopted in practice. Thus one cannol have a legitimate learning rate for GD to converge along the large eigenvalue directions as SGD does with moderate learning rate.
Note GD with small learning rate also converges along the small eigenvalue directions, since (5) covers the small learning rate scheme. In complement, the following Theorem shows that in the small learning rate regime, SGD is imitating GD and converges along the small eigenvalue directions as well. Theorems 1, 2 and 3 together show that, converging along the large eigenvalue directions is a distinct regularization effect that is unique to SGD with moderate learning rate.
Theorem 3 (The directional bias of SGD with small LR, informal). Theorem 2 applies to (SGD) with the following small learning rate scheme
Tie T== 1/ E (0. 2Λ1 +0 == 1._,...,kk
Experiment Figure 2 shows two experiments for verifying Theorems 1, 2 and 3. The details of the experimental setup are deferred to Appendix D. In Figure 2(a), we run SGD and GD in both moderate and small learning rate regimes, and directly compare their Rayleigh quotients as defined in (4) and (6). We can see that the Rayleigh quotient reaches its maximum for SGD with moderate learning rate, and reaches its minimum for both GD and SGD with small learning rate, which ver- ifies Theorems 1, 2 and In Figure 2(b), we run the algorithms to optimize a neural network on a subset of the FashionMNIST dataset. Since the neural network is non-convex and have multiple local minima, we compare the relative Rayleigh quotients, i.e., the Rayleigh quotients of the conver- gence directions divided by the maximum absolute eigenvalue of the Hessian (see Appendix D.3). Figure 2(b) shows that SGID with moderate learning rate converges along relatively large eigenvalue directions while GD/SGD with small learning rate converges along relatively small eigenvalue di- rections. This distinguishes the directional bias of SGD and GD in the moderate learning rate regime and provides evidence from neural network training to support our theory.
4.2 EFFECTS OF THE DIRECTIONAL BLAS
Next we justify the benefit of the particular directional bias of SGD with moderate learning rate.
Recall the hypothesis class Hs (Eq. (1)) for SGD and GD. Then for an algorithm output whl, have the following generalization error decomposition (Shalev-Shwart & Ben-David, 2014),
(w inf LD(w)= (l( - inf Lo(w')+ + inf w E'
Lo(w") inf L (w).
w
E'E
A(uels), estimation emorr
approximation error
The approximate error is an intrinsic error determined by the hypothesis class, and not improvable unless enlarging the hypothesis class. In contrast, the estimation error A(w"ls) is determined by the algorithm as well as its hyperparameters. Thus, in the following theorem, we use the estimation error to compare the generalization performance of the SGD and GD outputs in different learning rate regimes.
Theorem 4 (Effects of the directional bias, informal). Let W. := {w E Hs Ls(w) = =a be an a-level set of the training loss Ls(w). Let A: = inf wew. A(w) be the minimum estimation error within the a-level set W.. Under the same conditions as Theorems 1- and assuming that b < n/2 O (V), then the following holds with high probability:
6

---

Published as a conference paper at ICLR 2021
Relative Rayleigh quotient
0.0025
1.0
SGD, small LR
Rayleigh quotient
0.9
0.0020
GD, small LR
0.8
SGD, small
SGD, moderate LR
0.0015
GD, moderate LR
0.7
GD, small LR
0.6
SGD, moderate LR
0.0010
0.5
GD, moderate LR
0.4
0.0005
0.3
Yo
0.0000
2000
4000 # Iteration
6000
8000
10000
0
2000
4000
6000
8000 10000
# Iteration
(a) Linear regression on synthetic data
(b) Neural network on a subset of FashionMNIST
Figure 2: Comparison of the (relative) Rayleigh quotients. (a): A linear regression example. We randomly draw 100 samples from a 10, 000-dimensional space described in Section 4, where C <~ [40.55 1]). The small learning rate scheme is specified by (1/' k2) = (0.2, 10*), and the moderate learning rate scheme is specified by (1, v', kı, k2) = (1.05, 0.1, x 10", 3 x 10*). Numerical results show the Rayleigh quotient converges to its maximum for SGD with moderate learning rate, and converges to its minimum for GD and SGD with small learning rate, which verifies Theorems 1, and 3. (b): A neural network example. The plots averaged over 10 runs. We randomly draw 000 samples from MaSh the training set. The model is a 5-layer convolutional neural network. The small learning rate scheme is specified by (1/ k2) = (10-3 10"). and the moderate learning rate scheme is specified by (n, k1) = (10 2 10 2.5 x 10', 10*). Since neural network is non-convex, we compare the relative Rayleigh quotient of the concerned algorithms. i.e. the Rayleigh quotient of the convergence directions divided by the maximum absolute eigenvalue of the Hessian (see Appendix D.3).
The output of (SGD) with moderate LR (3) in Theorem I satisfies A(wak) < (1 + +)) Da where a is the training loss of w and is a small constant;
The outpul of (GD) with moderate or small LR (5) in Theorem 2 satisfies A > M A
()1 where a is the training loss of w and M = (1 (1-t) "/2/ 'nn is a constant larger than 1 + e;
The output of (SGD) with small LR (7) in Theorem 3 satisfies (wFrd) > M A., where is the training loss of wddd and M = (1 71/7n is a constant larger than 1 1+ c.
Theorem 4 suggests that: (1) in the moderate learning rate regime, there separation between the test error of SGD and that of GD. In detail, early stopped SGD finds nearly optimal solution thanks to its particular directional bias. In contrast, early stopped GD can only find suboptimal one; and (2) in the small learning rate regime, however, SGD no longer admits the dedicated directional bias for moderate learning rate. Instead it behaves similarly as GD, and hence outputs suboptimal solutions when early stopping is adopted.
Remark 5. In practice it is usually intractable and unnecessary to achieve the exact global minima of the training loss; instead we often early stop the algorithm once obtaining a small enough training loss. i.e. reaching an cellevel set. In this spirit, Theorem 4 compares the generalization ability of SGD with moderate learning rate vs. GD/SGD with small learning rate within a level set.
also obtained by Nakkiran (2020) for different purpose. In specific, Nakkiran (2020) show the separation between the test error of GD with "large" and annealing learning rate, and test error of GD with small learning rate. However, the "large" learning rate for GD in their analysis is linear in the training sample size and is not practical as we have discussed in Remark 4. In contrast, we show that under the practically used moderate learning rate, there is separation between the generalization abilities of SGD and GD. To our knowledge, our work gives the first theoretical justification of the phenomenon that SGD outperforms GD when the learning rate moderate.
Remark 6. We note the second conclusion in Theorem
Experiment Figure 3 shows the generalization performance of a neural network trained by SGD and GD in both moderate and small learning rate regimes. The setup details are included in Ap- pendix D. We can observe that (1) SGD with moderate learning rate generalizes the best, and (2) GD and SGD with small learning rate perform similarly, but both are worse than SGD with moderate learning rate. The empirical results suggest SGD with moderate learning has certain benign regular- ization effect. This is explained by the distinct directional bias for SGD with moderate learning rate shown in previous theorems.
7

---

Published as a conference paper at ICLR 2021
5 RELATED WORK
In this section, we review related works and discuss their similarities and differences to our work.
The implicit bias of GD The implicit bias of GD has been extensively studied in recent years. We summa- rize several representative results as follows. For homo- geneous model with exponentially-tun verges along the max-margin direction (Gunasekar et al.,
80
Test accuracy
loss, GD con-
70-
SGD, small
GD, small LR (81.61 = 0.29)
2017: 201 Sa;b; Soudry et al., 2018; 8 Ma et al., 2018; Ji
SGD, moderate LR (82.47 0.57)
& Telgarsky, 2019a; Ji et al., 2020; Nacson et al., 2019a). For least square problem and its variants, GD is biased to- wards minimum-norm solution (Gunasekar al., 201 Sa; Ali et al., 2019; Suggala et al., 2018). Note that this is also the foundation for the learning theory in the interpo- lation regime such as double descent (Belkin et al., 2019) and benign overfitting (Bartlett et al., 2020). For matrix factorization and linear network, Gunasekar et al. (2017); Li et al. (2018) show the GD solution minimizes nuclear norm in special cases; more generally, Arora et al. (2019); & Telgarsky (2019b) show GD balances/aligns layers; Moroshko et al. (2020) suggest the GD bias relies on ini- tialization scale and training accuracy. For infinite-width network, Chizat & Bach (2020) show GD finds max- margin classifier in a functional space. The regularization theory for GD is fruitful; While some of them can be applied to SGD with small learning rate have discussed (Nacson et al., 2019b; Gunasekar et al., 201 8a; Ali et al., 2020), none of them can be carried over to SGD in the moderate learning rate regime. As far as we know, our paper the first to study the regularization effect of SGD with moderate learning rate.
CD, moderate LR (81.46 1.10)
60
2000
4000 6000
8000
10000
# Iterationn
The test accuracy of neural network on a subset FuShionMNIST. The plots are averaged over 10 runs. The exper- imental setting is identical to that in Figure 2(b). The plots show that SGD with moder- ate learning rate achieves the highest test ac- curacy, and GD and SGD with small learn- ing rate perform similarly, but are worse than the former.
Figure 3:
The stability of SGD Stability is another approach to justify the generalization ability of SGD, where stable algorithm is guaranteed to have small generalization error (Bousquet & Elisseeff, 2002). Along this line, several works show that SGD is stable under certain assumptions and there- fore generalizes well (Hardt et al., 2016; Kuzborskij & Lampert, 2018; Charles & Papailiopoulos, 2018; Bassily et al., 2020). More interestingly, Charles & Papailiopoulos (2018) show a simple example where SGD is stable but GD is not, which partly explains the empirically superior perfor- mance of SGD. We also aim to justify the benefits of SGD, but take a different approach from the algorithmic regularization.
The escaping behavior of SGD A popular theory (Jastrzębski et al., 2017; Zhu et al., 2019; Sim- sekli al., 2019) attributes the regularization effect of SGD its behavior of escaping from sharp minima. These works are built upon the continuous approximation of SGD via stochastic differential equations (Li et al., 2017: Hu al., 2017; Xu et al., 2018; Simsekli al., 2019). However requires a small learning rate for the approximation to hold. In contrast, our main interest is in the moderate learning rate regime. Another related work in this line is (Wu al., 2018), where they study the dynamical stability of minima and how SGD chooses them, but they do not show a directional bias introduced in our work.
Non-small learning rate The regularization effect of non-small learning rate has received increas- ing attentions recently. Theoretically, Li ei al. (2019); HaoChen et al. (2020) study the generalization of certain stochastic dynamics equipped with annealing learning rate scheme. However, their results cannot cover vanilla SGD. Lewkowycz et al. (2020) study the role of initial large learning rate for feinity-widthh network. Our work is motivated by Nakkiran (2020), which shows that a large initial learning rate helps GD generalize. This result can be recovered from our theorems; more impor- tantly, we characterize the directional bias of SGD. Empirically, Jastrzebski et al. (2019); Leclere & Madry (2020) investigate the impact of two-phase learning rate for training with SGD, but they do not provide any theoretical analysis.
8

---

Published as a conference paper at ICLR 2021
6 DISCUSSIONS
Linear scaling rule Linearly enlarging the initial learning rate according batch size, or the linear sealing rule (Goyal et al., 2017), is an important folk art for paralleling SGD with large batch size while maintaining a good generalization performance. Interestingly, the linear scaling rule arises naturally from Theorem 1, where LR (3) suggests the initial learning rate yf to scale linearly with batch size b to guarantee the desired directional bias. Our theory thus partly explains the mechanism of the linear scaling rule.
Overrunning SGD with high learning rate Besides the moderate initial learning rate, another key ingredient in Theorem is sufficiently large k1, i.e., SGD needs to run with moderate learning rate for sufficiently long time (to fit small eigenvalue directions). This requirement coincidentally agrees with the folk art to overrun SGD with high learning rate. For example, see Figure 4 in (He et al., 2016); from the ~ x 10 to the ~ 3 10 iteration, even the training error seems to make no progress, practitioners let SGD with relatively high learning rate for nearly 10 iterates. Our theory sheds light on understanding the hidden benefits in this "overrunning" phase: indeed the loss not decreasing since SGD with high learning rate cannot fit the large eigenvalue directions, but on the other hand the overrunning lets SGD fit the small eigenvalue directions better, which in the end leads to the directional bias that SGD converges along the large eigenvalue directions according to Theorem 1. Thus overrunning SGD with high learning rate is helpful.
Key technical challenges With non-small learning rate, analyzing SGD is usually hard since mea- sure concentration turns vacuous and as result one cannot relate the SGD iterates to that of GD. Alternatively, we control the SGD iterates epoch by epoch, then bound their composition to charac- terize the long run behavior of SGD. However, controlling the epoch-wise update of SGD is highly non-trivial, since in different epochs the sequence of stochastic gradient steps varies, and they do not commute due to the issue of matrix multiplication. To overcome this difficulty, we adopt techniques from matrix perturbation theory (Horn & Johnson, 2012) 2) and conduct an analysis in the overparam- eterized regime. We believe these techniques are of independent interest.
CONCLUSION AND FUTURE WORK
We characterize a distinct directional regularization effect of SGD with moderate learning rate, where SGD converges along the large eigenvalue directions of the data matrix. In contrast, neither GD nor SGD with small learning rate can achieve this effect. Moreover, we show this directional bias benefits generalization when early stopping is adopted. Finally, our theory explains several folk arts used in practice for SGD hyperparameter tuning.
As an initial attempt, our results are limited to overparameterized linear models, and we ignore other factors that may contribute to the good generalization of SGD for training neural networks, e.g., network structures and explicit regularization. left as future work to extend our results to nonlinear/noncoovvex models (with explicit regularization).
ACKNOWLEDGEMENT
We would like thank the anonymous reviewers for their helpful comments. QG is partially sup- ported by the National Science Foundation CAREER Award 1906169, IIS-200898 and Salesforce Deep Learning Research Award. DZ is supported by the Bloomberg Data Science Ph.D. Fellow- ship. VB is supported in part by NSF CAREER grant 1652257, ONR Award N00014-18-1-2230 and the Lifelong Learning Machines program from DARPA/MTO.C JW is supported by ONR Award N00014- 1-188---22 -234. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
REFERENCES
Alnur Ali, J Zico Kolter, and Ryan Tibshirani. A continuous-tima view of early stopping for least squares regression. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1370-1378, 2019.

---

Published as a conference paper at ICLR 2021
Alnur Ali, Edgar Dobriban, and Ryan J Tibshirani. The implicit regularization of stochastic gradient flow for least squares. arXiv preprint arXiv:2003.07802, 2020.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix
factorization. In Advances in Neural Information Processing Systems, pp. 7413-7424, 2019.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Acudemy of Sciences, 2020.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. arXiv preprint vrXiv:2006.06914 2020.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. arXiv preprint arXiv:1903.0755 2019.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499-526, 2002.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni- versity press, 2004.
Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International Conference Machine Learning, pp. 745-754. PMLR, 2018.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. arXiv preprint arXiv:2002.04458 2020.
Saced Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal on Optimization, 23(4):2341 2013.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. arXiv preprint 1901.0900009900 2019.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, An- drew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint arXiv:1706.02677 2017.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pp. 6151-6153 2017.
Suriya Gunasckar, Jason Lec, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In ICML, 2018a.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent linear convolutional networks. In Advances in Neural Information Processing Systems, pp. 9461-9471, 2018b.
Jeff 7. HaoChen, Colin Wei, Jason D Lee, and Tengyu Ma. Shape matters: Understanding the implicit bias of the noise covariance. arXiv preprint arXi::2006.08680 2020.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1234, 2016.
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, pp. 770-778, 2016.
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
Wenqing Hu, Chris Junchi Li, Lei Li, and Jian-Gur Liu. On the diffusion approximation of noncon- vex stochastic gradient descent. arXiv preprint arXiv: 07562, 2017.
10

---

Published as a conference paper at ICLR 2021
Stanistaw Jastrzębski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima in sgd. arXiv preprint arXiv:1711.04623, 2017.
Stanislaw Jastrzebski, Maciej Szymezak, Stanislav Fort, Devansh Arpit, Jacek Tabor, Kyunghyun Cho, and Krzysztof Geras. The break-even point on optimization trajectories of deep neural networks. In International Conference on Learning Representations, 2019.
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference on Learning Theory, pp. 1792,1798, 2019a.
Ziwei Ji and Matus Jan Telgarsky. Gradient descent aligns the layers of deep linear networks. In 7th International Conference on Learning Representations, ICLR 2019, 2019b.
Ziwei Ji, Miroslav Dudík, Robert E Schapire, and Matus Telgarsky. Gradient descent follows the regularization path for general losses. In Conference Learning Theory, pp. 2109-2136, 2020.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On surge-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv: 1609:.6000.0000 1609004866 2016.
Harold Kushner and G George Yin. Stochastie approximation and recursive algorithms and appli- cations, volume 35. Springer Science & Business Media, 2003.
Ilja Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 2815-2824, PMLR, 2018.
Guillaume Leclerc and Aleksander Madry. The two regimes of deep network training. arXiv preprint arXiv:2002. 10376, 2020.
Aitor Lewkowycz, Yasaman Bahri, Ethan Dyer, Jascha Dock-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint arXiv:2003.022 02218, 2020.
Qianxiao Li, Cheng Tai, et al. Stochastic modified equations and adaptive stochastic gradient algo- rithms. In Proceedings of the 34th International Conference on Machine Learning-Volle Volume 70, pp. 2101-2110. JMLR. org, 2017.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in wer-parameterizze matrix sensing and neural networks with quadratic activations. In Conference On Learning The- ory, pp. 2-47. PMLR, 2018
Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. In Advances in Neural Information Processing Systems, pp. 1674-11685, 2019.
Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex sta- tistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In International Conference on Machine Learning, pp. 3345-33555 2018.
Edward Moroshko, Suriya Gunasekar, Blake Woodworth, Jason D Lee, Nathan Srebro, and Daniel Soudry. Implicit bias in deep linear classification: Initialization scale vs training accuracy. arXiv preprint ar arXiv:2007.067 2020.
Mor Shpigel Nacson, Jason Lee, Suriya Gunasekar, Pedro Henrique Pamplona Savarese, Nathan Srebro, and Daniel Soudry. Convergence of gradient descent on separable data. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1420-3428. PMLR, 2019a.
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with fixed learning rate. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 3051-3059. PMLR, 2019b.
Preetum Nakkiran. Learning rate annealing can provably help generalization, even for convex prob- lems. arXiv preprint arXiv:2005.07366 2020.

---

Published as a conference paper at ICLR 2021
Shai Shalev-Shwarlz and Shai Ben-David. Understanding machine learning: From theory algo- rithms. Cambridge university press, 2014.
Umut Simsekli, Mert Gürbüzbalaban, Thanh Huy Nguyen, Gael Richard, and Levent Sagun. On the heavy-tailed theory of stochastic gradient descent for deep neural networks. arXiv preprint arXiv:1912.000/8, 2019.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19 (1):2822-2878, 28788, 2018.
Arun Suggala, Adarsh Prasad, and Pradeep K Ravikumar. Connecting optimization and regulariza- tion paths. Advances in Neural Information Processing Systems, pp. 10608-10614 2018.
Lloyd N Trefethen and David Bau III. Numerical linear algebra, volume 50. Siam, 1997.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint 1eXiv:1011.3000 2010.
Jingfeng Wu, Wenqing Hu, Haoyi Xiong, Jun Huan, Vladimir Braverman, and Zhanxing Zhu. On the noisy gradient descent that generalizes sgd. The 37th International Conference Machine Learning. 2020.
Lei Wu, Chao Ma, and E Weinan. How sgd selects the global minima in over-parameterized learning: A dynamical stability perspective. In Advances Neural Information Processing Systems, pp. 8279-8288, 2018.
Pan Xu, Jinghui Chen, Difan Zou, and Quanquan Gu. Global convergence of langevin dynamics based algorithms for nonconvex optimization. In Advances in Neural Information Processing Systems, pp. 3122-3133, 2018
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint 1.1 2016.
Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise in stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects. The 36th International Conference on Machine Learning, 2019.
12

---

Published as a conference paper at ICLR 2021
A PRELIMINARIES
A. ADDITIONAL NOTATIONS
We adopt the notations and settings in main text. In addition we make the following notations.
For vector E R denote its direction as ī == T For simplicity assume the training data
( In are linear independent. For training data zi, i E [r]], we denote A; ||>i||2 then by construction we have A (0, 1]. Without loss generality let A 2 2 An. We define
X (fI Fa) Rdxn
X-1 = T3, I3, E Rdx(n-1),
Then based the above definitions, define the following two projection operators
P= X(X x)-xx"
P-
Clearly for any E Rd, Pu projects onto subspace span (..,..., 3, while P1 projects v onto the orthogonal complement of span (II,...,InI Furthermore we introduce two more projection operators
P-1 = X (X P P1 -
For any Rd, P-10 projects onto subspace span { ,. while Pie projects into the orthogonal complement span { hn) with respect to span f En). ) In the following, we often write the column space of P. which refers to {Pv: o E R }. similarly for P-1. Pi and P1 as well. Clearly the column space of is also span (.1...., xn } the column space of P-1 also the data manifold span f.z...., .n We highlight that the total space R" can be decomposed as the direct sum the column space of P-1, P1 and Pl, i.e., P-1 + P + PI. By definition, it is easy to verify that
PIX =0, 0, PX = X. P.X (P10 0, (,
P- =
Then we define the following matrices which will be repeatedly used in the subsequent proof.
H =
H-1 == (P-X))(-1X)
H1 = (PXX)
H. (P. (P=z)) + (P
Based on the above definitions, is easy to show that
H (PiX + P P-1X)
(P_1X)(P_1X) + (PXX)((X)) ( (P-1X)(PXX) = - H
A.2 LEMMAS
We present the following theorems and lemmas as preparation for our analysis.
Theorem (Gershgorin circle theorem, restated for symmetric matrix), Let A E Rixn be symmet- ric matrix. Let Asj be the entry in the i-th row and the j-th column. Let
RA(A) = Σ Aigl i 1,...
13

---

Published as a conference paper at ICLR 2021
Consider n. Gershgorin discs
Dx(A) := E 2 A&l S (A())) i= i......,
The eigenvalues of are in the union of Gershgorin discs
G(A) = D((A).
==1
Furthermore, if the union of of the n discs that comprise G(A) forms a set G& that is disjoint from the remaining - k discs, then (+(A) contains exactly & eigenvalues of A. counted according to their algebraic multiplicities.
Proof. See, e.g., Horn & Johnson (2012), Chap 6.1, Theorem 6.1.1.
Theorem (Hoffman- Wielandt theorem, restated for symmetric matrix). Let A, E E R be sym- metric. Let λ1, ................................ An be the eigenvalues of A, arranged in decreasing order. Let Ai...., dn be the eigenvalues of A + E. arranged in decreasing order. Then
Σ - 1o12 < 1
Proof. See, e.g., Horn & Johnson (2012), Chapter 6.3, Theorem 6.3.5 and Corollary 6.3.8. Lemma 1. Let 4log(2n²/ /0) for some å E (0, 1). Then with probability least ō, we have
(a R,)1 < LL: δ
i
Proof. See Section C.I.
By Lemma 1 assume d 2 poly (n) such that nı is sufficiently small depends requirements.
The following two lemmas characterize the projected components each training data onto the column space of Pt, P-1, and PI.
Lemma 2. For æy * 21, we have
P-14, = Ty:
Play = 0;
Piæ, = O.
Proof. These by the construction of the projection operators.
Lemma 3. Assume Vou < 1/4. With probability at least 1 5, we have
0 PP118 $ 2/nu;
vI - 2 < Pi 112 < 1
P 0.
Proof. See Section C.2.
The following four lemmas characterize the spectrum the matrices H, H-1, H1 and He. Lemma 4. Let ....., nnn be the non-zero eigenvalues of H == X in decreasing order. then
An n S ......, Yo. S A + nt.
Furthermore, if there exist D and Ar+1 such that Xp > A + 2ni, then
An 7etl.-.. In S Art1 n X 71.... 2r S A1 n.
14

---

Published as a conference paper at ICLR 2021
Proof. See Section C.3.
Lemma 5. Assume An 2 3n.. Consider the symmetric matrix H-1 := P-IX((_IX)* R
O is an eigenvalue of H-1 with algebraic multiplicity being + 1, and its corresponding eigenspace is the column space of Pi + PI.
Restricted in the column space of P-1, the eigenvalues of H-1 belong
(An nu, d2 ni).
Proof. See Section C.4.
Lemma 6. Consider matrix H1 PiX(PIX)T E Rdxd, We have Hi has only one non-zero eigenvalue, which belongs to
D1 (1 (n-4n)², A1]-
Moreover, the corresponding eigenspace the column space of Pt, which 1-dim.
Proof. Clearly H1 is rank-1 since the column space of P1 is 1-dim. Thus it has only one non-zero eigenvalue, which given by
(r(Hi)
Σ 1
(Ai (1 11-4m²²) A1}, PP 12 1
where the last equality follows from Lemma
Lemma 7, Consider matrix H == (P-12)) + (P(m))()111)) E Rdxd
|ell2 - 2\ 1-118:11 S 4ymi.
Proof.
- 2\ PPP-1 S 4 Hell2 S 22111=1011122 ||
where the last equality follows from Lemma 3 and \ < 1.
B MISSING PROOFS FOR THE THEOREMS IN MAIN TEXT
B. THE DIRECTIONAL BIAS OF SGD WITH MODERATE LEARNING RATE
Reloading notations Let == [B),...
B be randomly chosen uniform m m-partition of [n]]
where n mb. Then the SGD iterates at the k-th epoch can be formulated as:
277c Σ
Faaz (wk. w.), 1...,,,, m.,
Wkit1 = Wkj
where we assume that the learning rate is fixed within each epoch. Note here x is independently and randomly chosen at each epoch. For simplicity we often ignore the epoch-indicator k. and write the uniform partition
[Bi.... .B,...,,.......... It is clear from context that is random over epochs. Bm
For a mini-batch By E म, we denote (BB)) = EieB, I.K."
Considering translating the variable by
w W.s
then we can reformulate the SGD update rule as
2nk H(,))
-1 b
27Tk H(BB)) ūk.t j= 1,..., m.
Ukit11 = -Ukj
(8)
15

---

M, = Mm x Mm-1 X ... x Mj. Published as a conference paper at ICLR 2021
Let
21t
M == I
II j=1 b
H(B,)
21 H(mm)
(1-
2nk HBBm-1) ... (I 2nk H(B.))
Here the matrix production over a sequence of matrices (M; E Rdxd] و |== is defined from the left to right with descending index.
II ==1
Let Uk++1 = 0k.m+1 and dy = UR.1- Then we can further reformulate Eq. (8) and obtain the epoch- wise update of SGD
Uk+1 -1-
2T/ H(mm))
2T H H(Bm-i)) (1 (1- 2T H(Bi) U/ -, (9)
In light of the notion of v, the following lemma restates the related notations of loss functions, hypothesis class, level set, and estimation error defined in Section and 4.
Lemma 8 (Reloading SGD notations). Regarding repramaterization the following related notations:
W., reload
Empirical loss and population loss are
Hi(Pio) + - 1P-11) (-1((1u)) (Po)) Hc(Po), Ls(v) = ((Po))T
LD(D) p 111112.
The hypothesis class is
Hs = {v Rd: PLu = P1vo].
The a-level set is u E Hs. the estimation error is
v= {uE Hs Ls(t) a).
A(u) = 1 | Pelp
Moreover,
unc
A. = inf A(v)
VEV
Proof.
See Section C.5.
Based on the above definitions, the following lemma characterizes the one-step update of SGD. Lemma 9 (One step SGD update). Consider the j-th SGD update at the k-th epoch as given by Eq. (8). Set the learning rate be constant n during that epoch. Then for .....,. m we have
(P
29 (H (" P.
I _T
(B
(P
Pi Uk.
P_IUk.3
Uk.
Moreover, i & Bj, i.e., I1 is not used in the j-the step, then
Piukst1 ( = (
Piuk.s (Pi
20
Proof. See Section C.6.
16

---

Published as a conference paper at ICLR 2021
Eq. (9) indicates the key analyze the convergence of tk+1 is characterize the spectrum of the matrix Mn. In particular the following lemma bounds the spectrum of M, when projected onto the column space of P-
Lemma 10. Suppose 3rd < An- Suppose < 1) < X Let π == , Bm3 be uniform m partition of index set [n], where n = mb. Consider the following d x matrix
21 1
M-1 II
P-H((B))))
E Raxd
==1
Then for the spectrum of .M __ we have:
1 is an eigenvalue of eigenspace is the column spuce of Pi + P1.
with multiplicity being d n + 1; moreover, the corresponding
Restricted in the column space of P-1, the eigenvalues of M M_,M-1 are upper bounded by
(a-1(1))² < 1, where
9-1(1) max {11
2n (A2 ni)
3nzp
21 (An ne) +
3repp
+
1
<
b
b
Proof. See Section C.7.
Consider the projections of up onto the column space of P-1 and P1. For simplicity let
A = PP1eekl2. B₁ = 1P1elll
The following lemma controls the update of A& and Bi.
Lemma 11 (Update rules for A and B&). Suppose 3ru An. Suppose O 3 Consider the k-th epoch of SGD iterates given by Eq. (9), Set the learning rate in this epoch to be constant fj. Denote
{(n)
21
n (n)
|1
(-1 == max
11-2
27
(A2 + nw)
3rmp
2n (An
nc)
3rm
1.
h
b
Then we have the following:
Aut1 S g-1 As + E(1) Bi.
BB41 S (n) BB - E(n) Ak-
BB41 (n)) By E(n) Ag-
Proof. See Section C.8.
Note we can rephrase the update rules for As and B& as
Ak+1
1--100 ( E(r)
E(n)
Ax
B
<
(1(1))
Bx
where "<" means "entry-wisely smaller than".
The following two lemmas characterize the long run behaviors of Ay, and Bg with different learning rate.
17

---

Published as a conference paper at ICLR 2021
Lemma 12 (The long run behavior of SGD with moderate LR). Suppose 3nt < Xn and X2 + Ant λ1- Suppose vo is far away from O. Consider the first 1 epochs of SGD iterates given by Eq. (9).
Set the learning rate during this stage to be constant, Le., Ul for k k1. Suppose
A T/ < <
X + 3nu
Then for 0 < c < 1 and 0 < 3 < 8 < Bo satisfying v S poly (cß), there exists h 2
O (log 1 such that cB
Ap Se. B.
1 By, $ |Poolle PI + 3 poly
For all 0, I,..,, k1, Ba Bo.
Proof. See Section C.9.
(The long run behavior of SGD with small LR). Suppose 3nt < Ans and X2 + < d1. Suppose vo is far away from O. Consider another h2 - k1 epochs of SGD iterates given by Eq. (9). Set the learning rate to be constant during the updates, i.e., an = r/ for
Lemma 13
kz Suppose
0 << T/ < 2
Consider the and given in Lemma 12. Then for k 2 ki, we have
A& S c.
B₁ < pq. Bk-1,
Bk-1 B,
where q E (0,1) is constant.
BB
Bk-1 < B.
Proof. See Section C.10.
Theorem 5 (Theorem 1, formal version). Suppose 3nd < An and x2 + 4nu < A1, Suppose is away from O. Consider the SGD iterates given by Eq. (9) with the following moderate learning rate scheme
17 A1-3/nc Xatsne) k L....,ki: Ki5 k = ki + I,...,k h2g.
1/ (0, 2x1)
Then for 0 < E < such that vnu S poly (E), there exist kn > O (log {)
and k2 such that
U/ Huke 2.
c1- <
Puka 12
Proof. We choose kn and l2 as Lemma 12 and Lemma 13 with 3 set as a small constant, then we guaranteed have
A < e 1..35.
S
Bkg
from where we have
P Uky
l1
B2
K2
1
2
2
Peka
2
A2, B2
1+
18

---

Published as a conference paper at ICLR 2021
Then have
Huk
(Pruks) (
(P-10ks) 1
+ (Puks) T HH PUKp) || Puka l1
Pekk
||Pukal12
1|
|| Uk2
2 A1 (1 -
+ 0 4/m
|| 112
2 A1 - 4n(²) (1 <²) - 44
2 (71 - (1 (1 - 4nd ) (1 - - 4/Tu
(since 7 S A1 + no by Lemma 4)
71 (1 4nc²) - - -m((1 4n=²) - -e AVTu
2 71 (1 0.5c) - 0.5mm (since Vnl S poly (c))
71 (1 c).
Theorem (Theorem 4 first part, formal version). Suppose 3nd < An and X2 + Ana < A1 Suppose vo is away from Consider the SGD iterates given by Eq. (9) with the following moderate learning rate schedule
E
A1-3/nc' Au+3ni
k = 1,...,ki kig
U
b r/'
0, 2
h = k1 + 1,..., k2
Then for < <<< satisfying vni I poly (c), there exist ky and 1 such that SGD outputs an e-optimal solution.
Proof. We set
3
(10)
na
80
>
B
(11)
and apply Lemma 12 to choose b such that
n
P-110k
12
S Bc
(12)
m
na
Piu Bu
0A < k ky
(13)
Pn
Thus for all 0 < k < kn
Ls(eR)= (Por) TXX (Pvx)
> 2n |Puxl2
(In is the smallest eigenvalue of X.X in the column space of P)
Y' |
a. (by Eq. (13))
which implies SGD cannot reach the a-level set during the iteration of first stage, i.e., SGD does not terminate in this stage.
We thus consider the second stage. From Lemma know || ll will keep decreasing before being smaller than 8, and P_]vull2 stays small during this period, i.e., SGD fits Piv while in the same time does not mess up P_ v.. Mathematically speaking, there exists hi and a such that
VICE
A |P- |P-11k, c 8
m
Ls(Vk,) a.
19

---

Published as a conference paper at ICLR 2021
which implies SGD terminates at the ky-th epoch. Then by Lemmas 3 and 8, we have nox (L))(
(PIVK)) ) H1(PiUss)) + (P-10k,) H2(P-1Uw)) + (Pukg) (
2 PI [kgn) T H1 (11kk))) PP1-11
2 (A1 n1) 4nt² (Ak + BBxr))
2 (7 3nd)
4ni² Absz
which yields
4m14 AR
(1 2) na
B S
33n Then we can bound the estimation error as
7/1
A μ P 12
1al B/ A
< 1 2)
uma
+ 2. pma
71
71
pna
< (1 + c)
71
= (1 + E) A.:
where we use the fact that A, pmaam1 from Lemma 8. Hence SGD is c-near optimal.
B.2 THE DIRECTIONAL BIAS OF GD WITH MODERATE OR SMALL LEARNING RATE
Reloading notations Denote the eigenvalue decomposition of XX"
XX = GTGT, : diag (?..... .,....)). 0), G = (91..... In....,gd) where G Raxd is orthonormal, and M...., Yn given by Lemma 4. Clearly, span (g1.....9h. ] = span ( In Let
G₁1 = (g)) G1 = (Inth....,9h 9a),
then
P P= G Pi = G. GI.
Recall the GD iterates at the k-th epoch:
21k xXT (wk w.). Wk+1 wy
n
Considering translating then rotating the variable as,
G (w -ww),
then we can reformulate the GD iterates as
2TTE l'ue
(1- 21TH r
u 1 Uk
uk.
(14)
n
We present the following lemma to reload the related notations regarding the parameterization u G (w W.).
Lemma 14 (Reloading GD notations). Regarding reparametrizationn u G (w - Wa), we can
reload the following related notations:
Empirical loss and population loss are
7i (u(i) 2
Ls(u)=
Σ
Lp(u)= = 1 11111/
7
1=1
20

---

Published as a conference paper at ICLR 2021
The hypothesis class is
Hss = R : = =bo for n 1, ...
The a-level set is For E H.s, the estimation error is
== fue Hy Ls(u) = aa.
u((t) ((()))
(
Moreover,
A, pma
71
Proof. See Section C.11.
The following lemma sovles GD iterates in Eq. (14). Lemma 15. Fort t = 0, O,
II
21
40
(8)
isism;
(2)
n+lsisd d.
Proof. This by directly solving Eq. (14) where I' is diagonal.
Theorem 7 (Theorem 2, formal version). Suppose An 2nd < An-1. Suppose uo is away from 0. Consider the GD iterates given by Eq. (14) with learning rate scheme
Qk E (0,
n
2 + 2ni
Then for e (0,1), if 2 O (log 2) then we have
Ug Twk
Y/ 5
S (1++))-
Tn.
Σ Σ u
(1)
Proof. For 1,...,n,, denote (:(n) =
2%,
17, where 17 E (0, 221+2mc
n Then we have
(n) < since
n <
2(A1 + nd)
2
2m
where the second inequality follows from Yι Tu by Lemma 4. Furthermore, since X, + < An-1 Tu. Lemma gives us
0 <090 7n ... sm <1,
(15)
which implies
(n(1)) a- (n-1(11) (11) 2 2 41 (n) > 0.
(16)
Moreover,
-n qn-1(1)
1 2% 2
f(n)
n
On (1)
increasing, let q max, am
f(), then g by assumption the learning rate.
From Lemma 15 have
k
0g
= II
(i()))
(4) i= I....,
(17)
0=
21

---

Published as a conference paper at ICLR 2021
By the assumption that
2/ 1(u
(2
log
1
71 Di=
0 !
k
(18)
2
logg 9
we have
Uk
(1)
R- 1
(1)
/2
(2)2
uuk"
1=0 (:( 2 (up )2
= 1++
(by Eq. (17))
(== On (m) )2. (uo
[m] )2
1=1
(4)
2
40
(i())
11+
(u)
(u)))2
In (T )2
E
40
(1)
2
1 (m))²
< 11+
(by Eq. (16))
(uo
In (1)²)
(=
(1)
40
< +
q
2k
(n))2
(ug
7n
< 1+
E,
(by Eq. (18))
71
which further yields
(uk
(n)
)
1
In E.
1 2
2
(19)
E
U
(1)
2
+
In 71
By the above incqualities we have
u T Tu
11
(0)
2
(1)
2 %
1
f=1
i=
U
(1)) )2
(uk
(uz
2 "nn +
(1)
2
7/8
>m 1
uk
iml
k
(uk
S Yn +
(by Eq. (15))
1=1
-==1
uk
(1))²2
(uk
=In +
1
111
Σ i=
S Y' + In e 711
(by Eq. (19))
71
Yn (1 + c).
Finally we note that 14 Fug
In since Yn. is the smallest in {7
Theorem 8 (Theorem- 4 second part, formal version). Suppose An + 2nu < An-1- Suppose up is away O. Consider the GD iterates given by Eq. (14) with learning rate scheme
7) E 0, 2X + 2n
n
22

---

Published as a conference paper at ICLR 2021
Then for (0,1), if 2 O (log :) 11 (1 6) is constant. then GD outpus M --suboptimal solution, where M
On
Proof. Consider an a-level set where
Ls(u)) T'g.
(20)
From Lemma 15 know (s( is monotonic decreasing thus GD cannot terminate before the k-epoch, i.e. the output of GD is uk.
Thus
Σ
(i)
(u)
i=
Uk
71
(by Lemma 14)
A.
na
Σ UR
(0)
2
(by Eq. (20))
u Timk
2 71 (1 c)yn
(by Theorem 7)
2 71 (1 -1-6 c)
M,
where we have M > 1 by letting < 1 In
B.3 THE DIRECTIONAL. BIAS OF SGD WITH SMALL LEARNING RATE
We analyze SGD with small learning rate by repeating the arguments in previous two sections.
Let us denote X-n (I1, 22, ....... ... ; 1n) and
P_n X
X== (X X XT
P-=P-P P
That is, P-n is the projection onto the column space of X-n and Pn is the projection onto the orthogonal complement of the column space of X-n with respect to the column space of X.
Let us reload
= H=n = (P=x)))
Hn = (PxX))
H. = (P-nzn) ( +
Then
H1 = H. + Hn + He.
Following a routine check we can reload the following lemmas.
Lemma 16 (Variant of Lemma 10). Suppose 3nd <. An Suppose 0 < 1 < 3,43mi Let Let ==
(Bi,...,B., Bm... be uniform m partition of index [n)), where mb. Consider the following d x d matrix
M_n = II
I 2n P H(B))) E Rdxd
j=1
Then for the spectrum of M. M_M_p we have:
1 is an eigenvalue of M_M with multiplicity being n + 1; moreover, the corresponding eigenspace is the column space of P, P1.
23

---

Published as a conference paper at ICLR 2021
Restricted in the column space of P-n, the eigenvalues of M (g-n(1))² 1, where
M-n M upper bounded by
(-n(1) max {1--2
2n (A1 + ne)
3nm
2n (An-1 ni) +
3reee
1.
b
Proof.
This is by a routine check the proof Lemma 10.
Consider the projections of 2h onto the column space of P-n and Pn. For simplicity we reload the following notations
Aş == 11-n00ll2 BB = P
The following lemma controls the update of A and Bi-
Lemma (Variant of Lemma 11). Suppose 3ru An. Suppose O 1j < X. Consider the k-th epoch of SGD iterate given by Eq. (9). Set the learning rate this epoch be constant fj. Denote
4
{(n)
2m
On (1)
|| |
2n
3rmp
1 27
3rm
q-n(1)) = max
(A1 + +no)
+
(An-1 ne)
<1.
b
b
Then have the following:
Aut1 S g-n(1)) Aş E(n) Bg.
BBt1 S (n)) Bg + E(n) Ag.
BB41 (n())) Bg E(i) Av-
Proof. This is by a routine check the proof Lemma 11.
Lemma 18 (Variant Lemma 13). Suppose 3nd < An and An + Anu < An-1- Consider the SGD iterates given by Eq. (9) with the following small learning rate scheme
= n/ E (0. 2 2nd
k = 1, I,..., 12-
Then for 0 < <e< satisfying Vnu S poly (c), k2 2 0 (logg :)
then
Akz. < 6. Buy
24

---

Published as a conference paper at ICLR 2021
Proof. From the assumption we have r/
b
and n/ 2x thus
t())
4v/
Vnu
:: ::=E(m/ E(1') = b
27'
On = (r)) =
P
b
= 1 21/ An
|| 11
b
2An (1 4n
< 1
1//
(since || 2 - 4n by reloading Lemma 3
b
< 1
+ 3nn'
21/
3rn'
Q-n q-n (1')
max
(A1 + +ne)
(A ne)
b
21/
3rm'l
21'
3nn/ /. (n
max 1
b (>1 + ne)
1
ne)
b
b
= 1 21/
-ne) + 3rn't
b (An-1 - me)
b
= 1 2(An-1 - -nz) 3nl
1/' E (0,1).
Moreover, by the gap assumption An 4nu < An-1 we have
2(A mi) 3nd 2An(1 4nx?)
4n - q-n 2 1/
b
21/ (An-1 --n-3ne) -3nc)
0.
Therefore 0 < <-n-n < 9n < 1. Thus we can set & 4n/ b
to be small such that
q-n
0 < ====
<
(21)
E Au/ Bu
Moreover, since /ni S poly (e) and
4n' Tmu
we have
5
(1 (1-
(22)
On E
Ao/Bo
Now recursively show
Au Bx
Aa. Bo
Clearly it holds for ls 0. Suppose As
A2.
consider
B. Bo
Ar41 in the following Best
Ax+1
I-n
Aş + Bx
(by Lemma 17)
B
On B& 5 An
As +
9-n Bx
Gn E Bz
As
As +
q Br
(by inductive assumption)
In
{ Ao/
Bo
9-n
A
E
On
E
Ao/
Bo
B
E Ao/ Bo
A
(1
q)
(by Eq. (21) and (22))
Bb
2
An
(1
q)c
Bu
2
Ao
<
Bo
25

---

Published as a conference paper at ICLR 2021
where in the last inequality we assume
2
Ao.
Bo
Moreover, from the above we have
Ak+1 Bx+1
(1 - c)
59
By:
which implies
Aks
Ao + 1 -
(1 9
S 1/
Bka
Bg
2
$ + C,
2
2
where we set kn 2 O (log 2
Next we prove the directional bias of SGD with small learning rate.
Theorem (Theorem 3, formal version). Suppose 3n < >n and An + 4n < An-1- Suppose vo away from O. Consider the SGD iterates given by Eq. (9) with the following small learning rate scheme
Th = E (0.
)
k = I,....ki..
2 2nl
Then for 0 <E 1 satisfying T S poly (e), kf 2 O (log 2 then
1/ H Huke
In 5
S (1 + E)
Pukk 1
Proof. First by Lemma 18 we have
B
62 21 2 1
(23)
A2 + B
A
+1
Big
Next by H Hn + H-n Ho we obtain
0/2 Huk,
(Pr T Hn (n.uk))))
(P-nuhz) ) T 11 (I_((Pnnke)
(PUt.) Ho(Puk)))
|P 12
PUkk 12
|Pnkk
||P_n
112
< An
(A1 + nn).
+ 44/m
by reloading Lemma 5, 6, 7
| 11
Pu
12
AZ
< An + (A1 + ni)
+ 4V
A + 137
S In
n + (A1 + nc)) 2² + 4//n
by reloading Lemma and Eq. (23)
I In in- e.
since Vne S poly (c)
"h Hong |
Finally, we note
2 Nn since "n is the smallest eigenvalue of / restricted in the column
space of P.
Theorem 10 (Theorem third part, formal version). Suppose 3ru < An and An + 4ne < An-1- Suppose is away from 0. Consider the SGD iterates given by Eq. (9) with the following small learning rate scheme
Th =nn (0. b
k 1. I...,,k.. K2
2 2n
Then for 0 E 1 such that Vnc S poly (c), if k2 2 O (log !) then SGD outputs an M- suboptimal solution where M 21 (1 t) > is constant.
Ta
26

---

Published as a conference paper at ICLR 2021
Proof. From Eq. (9) and r// of MM is smaller than 1, thus Ug indeed converges 0.
2 we know that restricted in the column space of P, the eigenvalues
Consider an a-level set where
1 2/ Huke
LS(())
(24)
Then
A(u)
P
711
(by Lemma 8)
A
T&CK
Prk l1
71 2k Huk
(by Eq. (24))
2 71 (1 + +)
(by Theorem 9)
2 21 (1 -e)
M,
where we have M > by letting
In. "1"
C PROOF OF AUXILIARY LEMMAS IN SECTIONS A AND B
C.I PROOF OF LEMMA
Proof of Lemma 1. Note that T; follows uniform distribution on the sphere Sd-1, Therefore, let be random variable following distribution x distribution and define 2, T, have 2 follows standard normal distribution in the d-dimensional space. Then it suffices to prove that for all i j.
(2,,
First we will bound the inner product (zs, 2z). Note that we have each entry in 2; is 1-subgaussian, it can be direcly deduced that
2
(k)
2
(Z 23)
2
is d-subbexponential, where 2, (k) denotes the k-th of the vector 2;. Then if follows that
(12z 23)1 t) s 2exp
(-d)
d
Next we will lower bound ||2/|22. Note that
| - d= Σ (b) ((:10))- -1)
k=1
Since o! 1-subgaussian, we have ||=;|| 2| - is d-subexpoential, then
IP (1I=1122 - al 21) S 2exp
Finally, applying the union bound for all possible i, E [n]], we have with probability at least 1 - 6, the following holds for all * j.
2n
(<1,, S V d log
8
2n²
|| 2 d V d dlog
8
Assume 4log(2n2/5) we have ||=,||² 2 d/2. Then it follows that
12,, 2yح2
2n
(Z,, =
|| |=
2
d
log
6
=: t.
This completes the proof.
27

---

Published as a conference paper at ICLR 2021
C.2 PROOF OF LEMMA 3
Proof of Lemma 3. Similar to the proof of Lemma 1, we consider translating ,1,..., .n to
21:...;5 2n by introducing xå random variables. Let Z-1 (22,.... 2n) R (n-1), in which
each entry is i..d. generated from Gaussian distribution (0, 1). Then we have
P-131 X-1(X_,X-1)
Z- (-_, - _
Then conditioned on ž1, we have each entry in __,ãz i..d. follows (0, 1). Then it is clear that ||__, l12 follows from - distribution, implying that with probability at least 8', we have
a & (n - 1) + v(n log(2/8").
Then by Corollary 5.35 in Vershynin (2010), we know that with probability at least that
holds
Vd Vn / 1lgg0()/))) S min (Z-1) S max (Z-1) S Vd vn 1++ 22 log(2/""). Therefore, assume v(n 1)+ + 2 S vd/8, we have with probability at least 8'
||2-(2_,2=)+11 vd + / + log (2/8")
(Vd vn- 221-22log 22g0
1
1 4 (1maT
n n-
/ 22lg((2/8)
Vd
Combining with the upper bound of || that [-_ 7- - 1|2 ||
||
T
2l,, set 8' = 8/2, we have with probability at least -
(1m 1n-1
log (4/8)
n d
v nn 1) d
log 4/0)
+
d
(1 + 4/T)) Vni,
where the last inequality follows from the definition of t. Then assume /nc S 1/4, we are able to
completes the proof of the first argument. Note that 1 + P|- 11 | 11 1, we have
1-122l122 = V 1 1
v1 V1- 4n 2 4n
This completes the proof of the second argument. The third argument holds trivially by the con- struction of P1.
C.3 PROOF LEMMA
Proof of Lemma 4. Clearly X Rdxd is of rank and symmetric, thus X has real, non- zero (potentially repeated) cigenvalues, denoted as 7..... Yn in non-decreasing order. Moreover, 7i..... Yn are also cigenvalues of X X E Ruxn thus it is sufficient to locate the eigenvalues of X X, where [XTX). = x. xz-
We first calculate the diagonal entry
(x x) (x
=x] x; X,
Then we bound the off diagonal entries. For j $ i,
(X X)1; x xj / Mad (-1,)),
where we use 0 < Ais..., An < 1. Thus we have
Ra(X T X) = Σ (x
(xTx) < sm, i= 1=
Finally conclusions hold by applying Gershgorin circle theorem.
28

---

Published as a conference paper at ICLR 2021
C.4 PROOF OF LEMMA 5
Proof of Lemma 5. The first conclusion is clear since by construction, we have P-IP, = P-1P1 0.
Note that H_1 is a rank n symmetric matrix. Let r2..... be the n non-zero eigenvalues of H-1. Clearly, ...... Tn with 71 0 give the spectrum of
H- P Rax*
We then bound T2,.... .
Tn by analyzing 1-
From Lemma we have PP ll2 S 2/. From Lemma we have
P-I (1-1 12 P-10n) (P- (P-1 I2.,,,
Then calculate the diagonal entries:
P-1111 1 112 A1 4n & 4ni?; i= 1;
H
| = Ais
i i 1.
Then we bound the off diagonal entries. jet * Then at least one of them is not 1. Without loss of generality let i # 1, which yields = P-123 by Lemma (2). Thus (x,, P1zy) = (P-1 Pıa,) = Thus we have
H (H-1),} = =P--134) P-133
x. P-100
= x. 22 I; PIz3
2
Vady 7z) E (-1,)).
Thus we have
(xHH)))=
Σ j
H 1)
$ nı, i= 1=
Finally, we set 4nu + 2nu An. so that the first Geoshgorin disc does not intersect with the others, then Gershgorin circle theorem gives our second conclusion.
C.5 PROOF OF LEMMA 8
Proof of Lemma 8, For the empirical loss, is clear that
[v( 1 (w -w.) XXT (w w.) T 1
1
= Hv
H((ut)
H T (Pu) + - (Pv) H
H_ (
1 (Pv) H.
n
n
n
(Pi)) H. (Piu) + - (P-10) H H- - (Pv) H.(P)),
n
where we use Lemma 4, Lemma 5, and Lemma 6. For the population loss
Lo(u)= 4 -|w w.1l2 1|112
For the hypothesis class Hs {w Rd PLw = P1 wo) applying w. and Wh W. to.
we obtain
H.s {u E Rd Piv P vo).
For the a-level set, note the optimal training loss is 1.3 infrets Ts((v) 0.
29

---

Published as a conference paper at ICLR 2021
As for the estimation error, note that infueMs (D( = P vo 11112 1| Poolll thus for e E Hs, we have
(v)) LD(3) inf v'EV
= = μ 1I μ Pull
Finally, consider E V, i.e., na = XXT u, thus
A. inf A(v) ΦEV
inf na=v XXTx
1 ||
ana
71
where " is the largest eigenvalue of the matrix XXT and the inferior is attended by setting parallel to the first eigenvector of X
C.6 PROOF OF LEMMA 9
Proof of Lemma 9, From Eq. (8) have
Uk.j. j == 1....., m. UkJ+1 = [ (T-
2n HBB)
(25)
Recall the following property of projection operators:
= P1P, P-1P-
0 0= P-P-1 = P-1P.
Moreover since x.! PLu O, we have
H(B))PLV=
Σ
x3 PLU= =
sEB,
Applying P1 to Eq. (25) we have
2n
Pickjjt1 = P1
I
H(BB))
Uk.j
b
211 ((;))
Pi
1
(Piuk.j + P--1kk. + Pi Piuks))
2m ((;)))
20 H(B,)) P-10k.j
P1
I
Piuk.j +
(1-
b
2n P (B.)BB))p))
2n
Pi ((BB))p1))) P-IVEE--
b
Similarly applying P- to Eq. (25) we have
21
PiiEa++1= = P-1
H(;))
Uk.j
b
211
P-1
H(B,)
(PIMR. + P-11kk. + PLUK.)
b
2m H(;))
(1-2 2n H(B:)) P-IUKS
P
1
Pivn.j + P-1
b
2m
(1-2 P-H P P-1
21
P_ H1
.PUKk +
To sum up we have
PiuKat1 (P
27 (H
$
Piuk.s
-1 (B, T- -. (P_1"R.)
Notice that if 1 & By. i.e. œ1 is not used in the j-th step, then we claim
Pi (B; H(;;) 0,
30

---

Published as a conference paper at ICLR 2021
since (B,,) =ieB, z is composed by the data belonging to the column space of P-1. There- fore 1 & B, we have
Piukit1 3 P-IUR-t1)
(aan)))(() -(6 1 2 P (P
Piuk.
C.7 PROOF OF LEMMA 10
Proof of Lemma 10. Clearly for each component in the production, the column space Pi + P1. which is (n d + ---diennsinnal, belongs to its eigenspace of eigenvalue 1, which yields the first claim.
In the following, we restrict ourselves in the column space of P-1- Let us expand M-1:
m
20
M_1
II [I
P-1H(BB)PP-)
j=1
P-1) ... (1- 2 20 P-1 HB (08m)-)))
(I
P- P-1H(BB)PP-i
b
2m m
1
P. P- (_HH(B))PP
b
H-1
2n
2
Σ
P- P= .....
ISijjSn
We first analyze matrix H-1. Since HB,)) Eies, Ta and क { Bm is partition for index set [n]], we have
12
H-1
P P-ll (B,)
j=1
Y
P_
F.S T P-1
j=1
KEB
P-1
I
P-1
P_, XP
which is exactly the matrix we studied in Lemma 5, and from where we have H_1 has eigenvalue zero (with multiplicity being - 1) in the column space P1 PL, and restricted in the column space of P-1, the eigenvalues of H_1 belong to (An - nı,, X2 + nt).
Then we analyze matrix C.
P- P_1H(())
P-1 Σ
P-1 Σ T
NEB,
J'EB,
Σ Σ
(P-12
P_ P.yy)
(26)
PEB; JEB
Remember that B, 0 B, @ for i # j. thus Ze # z. for 1' e B, and j' Bj. Then from Lemma
we have,
P P
(0,, Vivay ' L.
31

---

Published as a conference paper at ICLR 2021
Inserting this into Eq. (26) we obtain
|P_,
b² max $ b3...
We can bound the Frobenius norm of the higher degree terms in matrix C' in similar manner; in sum for the Frobenius norm of C, we have
||
S
2m b
m 8
(2m1)²
8)
Σ (2m1)* )
n2
1 2mmz
==0
= (1 + 2mp2)
2mrz
m² ve.
< 1 + m 2m +
(2m1)² - -1 2m7 (for 2np < 2m
2
where for the second to the last inequality we notice that for f(t) (1 + t)m and E [0, d.l we have ft( m(m- (1) < mmm- 1)(1 + 2m ) S m(m-1) Ve, which implies (t)
is (m² Ve)=soootthh for E [0, 2m moreover, by the assumption that 3n < An and r7 X 43mi
we can indeed verify that
2bc
2bb
1
2np < An + 3ne
(27)
6ne
2m
Now rephrase
217
H. + (1- 21 H +0) H11+
MI,M-1-
21 H-1 + +CT (1
21 H-11 + 1
21 H-1 C'+CC. b
(28)
b
Restricting ourselves in the column space of P-1, the cigenvalues of H-1 belong to (An nu, A2 + ni), thus the eigenvalues of (I- 2n H-1) are upper bounded by
-ne) ne) )
2n max (1 -
27 (An (1-
<1,
(29)
where the last inequality is guaranteed by our assumptions on 17 and v. For simplicity we defer the verification to the end of the proof.
Consider the following eigen decomposition I- 2nH U diag (p pn 11-1.1 1)UT. where μ1, ,I...., Mn-1 E (-1,1) by Eq. (29). Then we have
[|( -H--1) ||diag (MI, .. Mn 1)U TCclle
< <|UTCU|| = ||C||
Therefore we can bound the Frobenius norm of by
|| s [I(T
||C|]
< 2 |||[ < 8m²31²²² 16m
9m2 ?,?
(30)
32

---

Published as a conference paper at ICLR 2021
where the last inequality follows from 2nj. S 1/(2m) proved in Eq. (27).
Finally, applying Hoffman- Wielandt theorem with Eq. (28), (29) and (30), we conclude that, re-
stricted in the column space of P-1, the eigenvalues of __,MM
upper bounded by
{
{
21 b
2
(1 (1
21 (An nu)
max
(A2 ml)
9m?2n2??
9mm212??
2n (A2 + ni)
2 + +33mL)
(1
2n (An na) +3mmg
2)
S max
|
= (q))
(31)
At this point we left to verify Eq. (29) and
9-1 = max {1=
21
3rzp
21 (An - ne)
3rmp
b (12 + -m)
+ b
- b
+
1.
(32)
b
Clearly it suffices to verify Eq. (32).
21
3rmm 1 +
(A2 + +me)
b
3nd
2(12 + ni)
1) < 1 3nz
b 1) 1<1
7)
2dz-ne > 0
2 +5a 11 < 2
1> 0
2d2 N1 > 0
1 22
3ru < An
(since A 2 An)
0 < 17
Similarly, we verify that
27 (>n nt) + 3rm
1
b
3nz
2(2m n2)
3nt 1
1 < 1
11 1
b
2A, 5me
n > 0
21 t 17 <
>>> 0
2 5m
17 X, +0.5m
3nn < An
0 17
b A0t
(since X2 2 An)
These complete our proof.
C.8 PROOF OF LEMMA 11
Proof of Lemma 1I. Note that during one epoch of SGD updates, Fi is used for only once. Without loss of generality, assume SGD uses 21 at the 1-th step, i.e., E B, and 1 & B, for j * I. Recursively
33

---

Published as a conference paper at ICLR 2021
applying Lemma 9, we have
Pi Piok,m+1 P- P-10k,m+1/
(
0
I j= (I- 20 P- ((B))))) x
(B)()))))))
21 PiHHBB))P_
20 (B)H((B))) T-
P(BB
2
(0 (I - - x
0
P-1
Let Uk+1 Ukm++1, 0% = 1k,1 and
27 P-1 PB
Mi== I
211 P- (B,
My1 ==
II
b
j=1+1
1-1
24 P_ P-1 (B,))
M< = II
j=1
2n
M-1 == M Mar
II j=1
P-1H(BB)PPr
P-
b
then we have
PIuk+1 P-1Uk+1
11
2 P1 ((B))
( Maa)
PIUR P-10h
0
M
2y
P_ H(B))
MI
b
I 21 P, (B))
P(B Mei)
Pius P-11k/
(33)
-Mst (
(-)
M-1
In the following we bound the norm of each entries in the above coefficient matrix.
According to Lemma 5, we have the cigenvalues of P_) upper bounded by A2 + Thus the assumption 7) Ag yields
21 (B)
1
b
2
which further yields
||Mil12 S 1. |Maill S1 1.
(34)
On the other hand notice that Pıx; 0 for i + 1, thus
P1 = P1 Σ
naa P-1 Pio P-1.
iEB.
P- P_HH(B,)PP P- Σ
r,g T P = p-101 Pı,
FEB.
which yield
max (11_H(()))=-1b,,1P12-))-
< |P121l2 |P-111112 S 2/Tu,
(35)
where the last inequality is from Lemma 3 and \₁ = ||~1|| 21? < 1. Eq. (34) and (35) imply
max {1("00 2m P.H((B))).)) Mei Me0e)) M2i (?) P- H(B))) 11}
<
=: E(n) (36)
b
Next, by P!x; = 0 for # 1 we have
P.H(B.)P = Σ x, Pi
P (P111)
34

---

Published as a conference paper at ICLR 2021
from where know || is the only non-zero eigenvalue of the rank-1 matrix P1 (.) and
the corresponding eigenspace is the column space of Pt. Therefore 27 11 l is an eigenvalue of the matrix
2n Pi (Bi) Pt, and the corresponding eigenspace the column space of P1, which
5
implies
|| (1- 2n P1H(BB))P) Piuk
(1
27 b ||
=
Piue
2
2n
||
|
b
9 (1))
(37)
Finally, according to Lemma 10, we have, restricted in the column space of P-1, the right eigenval- of M-1 is upper bounded by (1-1(1))² which implies
|MM-P-auulle S g-1(n)) 11P-111112-
(38)
Note we have g-1(1)- < 1 by Lemma 10.
Combining Eq. (33) with Eq. (36), (37), (38), and letting B₃ | As 1PP-I obtain
Bk+1 $ (1))) B + E(n) Ak
B&+1 2 (1) BB - {(n) A
A S 9-11 (n) E(n) BB.
C.9 PROOF OF LEMMA 12
Proof of Lemma 12. Let
$ = ===((1) E(r) An
2nd11
41 = (7)
(39)
b
4-1 4-1:= (11 max {11
1
2n
(A2 + ne)
+
3nm
1
21
(An - ne)
3rm
b
b
b
b
Then for 0 < k < k1, Lemma 11 gives
B qi BB-1 - EAA-1,
(40)
As B₁
<
9-1
{ Ak-1
(41)
n
Bk-1
where "S" means "entry-wisely smaller than".
Let p-1:P1 Pi determine the eigen decomposition of the coefficient matrix, i.e.,
q $) 5)
) /cos 0
sin 0
(p-1
0)
cos 0
- -sin 0
sin
cos 0
sin
cos
(42)
35

---

Published as a conference paper at ICLR 2021
Then Eq. (41) and Eq. (42) yield
Ak Bb
9-1 {
s) &
AD
-
Bo
cos
sin
cos
sin 0 cos 0
(Ao)
sin 0 cos 0
pt
sin 0
Bo
ph + (p)
p sin? 0
(pf
-pt cos sin
Ao
(pf - p cos sin 0
pf (pf
p-1n sin? 0
BB
Ag ph_ + (pt p²_
(Ao sin Bo cos 0) sin
Bu p + (p)
p=11)
(Ap cos 0 Bu sin 0) sin
Ag p=1 + pf -p-1
A + B sin 0
Bo p3 + of p=1
Ag + B sin 0
Ag p + p p² |PPoll22 sin 0
(43)
Bn 1 +
|Puoll2 sin
We claim the following inequalities hold by our assumptions:
0 0<p-1 < < S 11 +
(44a)
b Pup l2 S 2
8 8,
(44b)
p |Puoll2 sin S E
(44c)
2
ç Ao BB0 < (q: - 1)30-
(44d)
The verification of Eq. (44) left later. In the following we prove the conclusions using Eq. (44).
We first bound As, using Eq. (43) and Eq. (44):
As S Ao p²1
p p01 1|P sin
< Proll2
-
+ p²
P
sin
< 3 + 3 2
= = 3,
which justifies the first conclusion. In addition obtain uniform upper bound for Ag for k == 0, 1,.,,..., kj:
As < Ao p=1 lat - |Pooll2 sin 0
< Ao + p |Pooll2 sin 0
< Ao + B.
(45)
Next we bound Bb, using Eq. (43) and Eq. (44):
Bk, S Bo pt + p p
| ll sin 0
< PPoll2 ki P1
PPooll2 sin 0
PPoll2
ki 3,
2
which justifies the second conclusion.
We proceed to derive the uniform lower bound for Bg for is = 0, 0,1....,ky We do by induction.
For 0, by assumption have Bn Bn Suppose BB-1 2 9o, then by Eq. (40), (44) and (45)
36

---

Published as a conference paper at ICLR 2021
have
B& 2 91 BB-1 - AA-1
2 Q1 : 90 - 6 (Ao + E
2
Ao + 6
91 90 8
2 80)
9n.
which justifies the third conclusion.
Verification of Eq. (44)
From Eq. (42) and Gershgorin circle theorem have
Q1 5 S P1
S q1 + E,
(46)
q-1 E S p-
S q-1 + g.
Moreover, reformatting Eq. (42) as
$
cos 0
sin 0 cos
(PoT
n)
cos 0
- sin 0 sin 0 cos
E 91
=
sin
P-1 cos? 0 + P1 sin" 0
(p1 p-1) ) cos 0 sin 0
(pi p-1) cos sin 0
sin 2 0 + cos? 0
P-1 + (p1 p-1) sin? 0
(pl p-1) cos 0 sin 0 (p) p-1) sin 0/
(p) p-1) cos sin
then have
(pi P-1) cos 0 sin
tan 20.
(47)
21 9-1
(pi - p-1) 2 sin 0) 2
For Eq. (44a), using Eq. (46) it suffices to show
0 < Q1
(48a)
9-1 + { < 1,
(48b)
< Q1 E.
(48c)
Notice the definitions 91, q-1 and & are given in Eq. (39). Firstly, Eq. (48c) holds trivially when V 4/3. Secondly, for Eq. (48b), noticing that { show
Anymm
< yas b
when n 2 16, it suffices to
b
2n (A2 + ma) + 4nmy. b
2n (An ni)
4nm. ) <1
max
b
ing 5
1 < 1
2(2
17 < 1
Ant
b
inc b
< 1
2(2,
<
ing
b
2A 2A2-2nd 2nd 8
n > 0
24 24266m 6me b 2A 6m
n <2
> 0
24 2nd
2
>
A > 0
An 3nd 0
11 A Amt
< X.
3nd < Am
0 < 7) < A3
37

---

Published as a conference paper at ICLR 2021
which are given in assumptions. Thirdly, for Eq. (48c) it suffices show
2
/n
||
11
- 1-
>
1
b
b
2 (1
4mi² 2)
4 Avnl nM
11
1J 2
(by Lemma 3)
b
b
>
(1 4mi
2//l
b
77 \ 3/mz'
(since no < 1)
which are given in assumptions.
For Eq. (44b), suffices to show set
log |Prolla O log 1
0.5ef
h1 = +
log p-1
cB
given in assumptions. For Eq. (44c), using Eq. (44b) it suffices to show
p-1
P-1
0.5c,
Tog
sin <
P
2oll22
P1
P1
locior +-))
4-1 - E
0.5eB
lokly-1 27
sin
<
ạ1 +
9-1 -
(1ppool
(
0.5cB
1-
Jog(er 1:6) logce 1-
E 0.9 (91 9-1)
(by Eq. (47))
Φ +
||uull2
+ nu & poly (e.).
(by Eq. (39))
For Eq. (44c), it suffices to show
$ S (9) 1).0
Ao + 0.5e30
Viu < 0 (1).
(by Eq. (39))
C.10 PROOF OF LEMMA 13
Proof of Lemma 13. Let
:':)((n') 4nf /nu
di (n(n)) 11- 2n'X, A1
1P
(49)
b
d-1 = q-1(1') max {1
1
2n' (1e ne)
3nn'e
2n'
(An
na)
3ro7
b
Then for Kj < k < h2g Lemma 11 gives us
Ax Bx
Ak-1 BR-1
(50)
where "<" means "entry-wisely smaller than". Denote
B = |Puoll2 p + 2/2 B = poly
é
1
(51)
cB
38

---

Published as a conference paper at ICLR 2021
We claim the following inequalities hold by our assumptions:
0 0 1 < 9/1 < 1,
(52a)
566_9-1 -1 1/
(52b)
5' B (1 (1-
(52c)
The verification of Eq. (52) is left later. In the following we prove the main conclusions in the lemma using Eq. (52). We proceed by induction. Clearly the conclusions are true for kj. Suppose for kj,..., k 1, the conclusions are also true. Then the induction assumptions give us
AR-1 c. c. 3,
(53)
B&- S B,, $ B,
(54)
where the last inequality is due to B 2 B₁, 2 90 > B. Then by Eq. (50) we have
B& 1 q/ Bx + 5' Ak-1
1 9/ B + 5' e. B
(by Eq. (53))
s // B (q'-1 91) 8
(by Eq. (52b))
9''1- BR-1, B&-1 > 3,
(by Eq. (52a))
33
B S 3.
Also by Eq. (50) have
Av s d-11 Ak-1 + BB
BB
S 4 - B + S.B B
(by Eq. (53) and (54))
$ sdn B + (1-1'1) .....cp. C.B (by Eq. (52c))
c.
Verification of Eq. (52) d-1 < 1 is already justified by the choice of learning rate r/ Xu+3ne (e.g., see Lemma 10), thus for Eq. (52a), suffices to show
Notice the definitions of 41, d'1 and g' are given in Eq. (39). Recall
0 An
2ny b (An ne) 3nn't
|| 11 <1
21 >
(by Lemma 3)
2A1 - -4nu?) > 2(2n - nn)) + 3nd
n// < 2
A > An + 2nl
which are given in assumptions.
For Eq. (52b), it suffices to show
s's (9 -1)
c
Vnu s
E
which is implied by n S poly (eß). For Eq. (52c), it suffices show
E' < B (1 8 8
Vnc S poly (E
(by Eq. (51)
We complete our proof.
39

---

Published as a conference paper at ICLR 2021
C.11 PROOF OF LEMMA 14
Proof of Lemma 14. For the empirical loss,
1 u G Xx Ls(u) 1 (w w.) XX (w w.)
Gu u
1 1 Tu
Σ
(2())
n
im
For the population loss.
ID(U)= = po ||00 w. w.11 1 || 2 la |1u1
For the hypothesis class Hs {w E Rd wiw Pi wo); Note Pi G diag (0, 0.1,...;1)
Apply w W. = Gu and notice we - wr = Gun. then we obtain
Hs = {u Rº P.Gu = P1P.... Guo}
(5) = {u E R² u Un
for i n + 1, I.....d..
For the level set, only need to note that L = infuEMs Hs Ls(u) 0. As for the estimation error, we note that
d Σ
(1))
inf well
LD(U)
"1
i=++1
thus for u E U, we have
A(u) L(u)
inf L(u') 14 11|uul22
P Σ
(ub)
(u6")
w'ell
i=n+1
(i)))
Σ
(u())
(1)
1
+ F
1
110
ビ==-
1=
1 )
Now consider u E U, i.e. 1 Ei= 7i (u(t)) a, then
/ (u()) 2 una
n
A, inf (uu) wELl
inf
=a= 74 (((1)))2
71
where the inferior attended when, e.g., (1)
+
nn 71
and (2) _...= (1) 0.
D DETAILS OF THE EXPERIMENTS
In this section, we describe the details for our experiments.
D. 2-D EXAMPLE
This part corresponds to Section 3 and Figure I. The training data points
T1 (VK, T, x2 = (0, T)T, k 4 and the corresponding individual losses are
(w) w. In w, (2(w) w x2az w.
Then the training loss is
I.(ww) 0.5(6((w) f2(w))
40

---

Published as a conference paper at ICLR 2021
We initialize the algorithms from wy (0.6, 0.6) Two kinds of learning rate regime are consid- ered. In the small learning rate regime, the learning rate is
N] 0.1/K, k L...... 800.
In the moderate learning rate regime, the learning rate is
1.1/K, h 10;;
The 0.1/K, k: 101, 800.
For SGD, the mini-batch size is 1.
D.2 LINEAR REGRESSION ON SYNTHETIC DATA
This part corresponds to Section 4 and Figure 2(a).
The model an overparameterized linear model, with d = 10 and n = 100. The true parameter w, is randomly drawn from d-dimensional Gaussian distribution, A/(0, 0.1 Iaxa).
We then randomly draw n 100 samples from the d-dimensional space as described in Section 4, where ( ~ (((0.5, 1]).
We initialize the algorithms from zero. We consider two kinds of learning rate regimes. The small learning rate scheme is specified by
7 0.2,
k 1,1, 10a
The moderate learning rate scheme is specified by
1.05,
k = 1 1....,2
2 10
T 0.1,
k +
2 10 3 103
For SGD, the mini-batch size is 1.
D.3 NEURAL NETWORK ON A SUBSET OF FASHIONMNIST
This part corresponds to Figure 2(b) and Figure 3.
Model We
LeNet-alike convolutional network:
input = conv1 = ReLU > max_pool + conv2 = ReLU =
max_pool fel ReLU fe2 ReLU linear output.
The first convolutional layer uses 5 x 5 kernels with 10 channels and no padding and the second convolutional layer 5 x 5 kernels with 16 channels and padding. The number of hidden units between the two fully connected layers are 60.
Dataset
https : ht//ggttuu com/ a
We randomly choose 2, 000 original test data as our training set, and use the 60, 000 original training data as our test set. Thus we have 2, 000 training data and 60, 000 data. We scale the image data to [0, 1].
Algorithms We randomly initialize the algorithms from a Gaussian distribution with zero mean and standard deviation 0.02. We consider two kinds of learning rate regimes. The small learning rate scheme specified by
T 10
1, 1......0000 10
The moderate learning rate scheme is specified by
10-2 k = 1....,,,235 2.5 x 103;
7/ = 10 = + x 103...., 10
For SGD, the mini-batch size is 25. For both GD and SGD, the weight decay parameter is set as 0.002.
41

---

Published as a conference paper at ICLR 2021
85
80
Test Accuracy
Test Accuracy
GD, LR=0. 001 (82.22)
SGD, LR=0.001 (81.85)
75
75
GD; LR=0.01 (82.61)
SGD, LR-0.01 (83.37)
70
GD; LR=0.02 (82.45)
70
LR-0.02 (82.76)
GD, LR=0. 04 (81.63)
SGD, LR=0.04 (80.76)
65
GD, LR=0.08 (78.85)
65
SGD, LR-0.08 (10.00)
GD, 1R=0.16 (10.00)
SGD, LR-0.16 (10.00)
60
60
0
2000
4000 6000
8000
10000
2000
4000 6000
8000
10000
# Iteration
# Iteration
(a) GD with increasing LRs
(b) SGD with increasing LRs
Figure 4: Test accuracy vs. number of iteration for algorithms with increasing learning rates. The model is a 5 5-layer convolutional neural network, and the dataset is a subset of FashionMNIST dataset. Details are described in Appendix D.3.
Table 1: Test accuracy (%) of GD/SGD in different LR on neural network example
Experiment
#1
#2
#3
#4
#5
#6
#7
#8
#9
10
SGD
81.57
81.85
81.71
81.74
82.29
81.38
82.10
82.05
81.95
81.77
small LR
GD
81.45
81.25
82.22
81.73
81.89
81.32
81.71
81.75
81.43
81.35
small LR
SGD
82.32
83.37
81.40
82.30
82.58
82.61
81.68
83.24
82.53
82.65
moderate LR GD
81.54
82.62
78.39
81.81
81.86
80.91
81.84
82.15
81.65
81.83
moderate LR
Relative Rayleigh quotient We discuss the relative Rayleigh quotients calculated in Figure 2(b). Unlike the linear regression model where the Hessian is a constant, for neural networks the loss function is non-convex. In other words, not only there are multiple local minima, but also the Hessian varies at different points. Therefore, a direct comparison in terms of the Rayleigh quotients for the iterates of different algorithms makes little sense. Instead, we consider the relative Rayleigh quotient, i.e., the Rayleigh quotient normalized by the maximum absolute eigenvalue of the Hessian that point. Mathematically, the relative Rayleigh quotient is defined
V[(w) RRQ(w) = M
V2L(w)-
VL(w) [V
[VL((w)l:
where (L(w)/ (Vtte>///VL//)l))/ is the convergence direction of gradient methods, and || ((w))()))))))) (w)ll ||2 is the operator norm of the Hessian, i.e., its maximum absolute eigenvalue. Note that it is computationally hard in practice project parameter onto the data manifold, thus we use the vanilla convergence direction instead of the projected one in the above definition of the relative Rayleigh quotient. Since our goal compare the relative Rayleigh quotient between different algorithms, this simplification would not affect our conclusions. We obtain the maximum absolute eigenvalue of the Hessian by running power method for 5 iterates.
Additional experiments: GD and SGD with increasing learning rates We conduct numerical experiments of training neural networks on subset of FashionMNIST dataset for SGD and GD with different learning rates 17 E {0.001, 0.01, 0.02, 0.04, 0.08, 0.16). The test accuracy results are displayed in Figure 4.
Several conclusions can be drawn from the plots. (1) For learning rate over 77 0.08, SGD cannot converge (thus only gives about 10% test accuracy). SGD generalizes best with a moderate learning rate 17 = 0.01. (2) GD fails to converge when r7 0.16. Also. as the learning rate increases, the test accuracy of GD first increases then decreases; but even at its peak (n = 0.01), GD performs worse than SGD with moderate learning rate.
42

---

Published as a conference paper at ICLR 2021
We also conduct statistical test to show SGD with moderate learn- ing rate is significantly better than the other baselines. Recall that the experiments are repeated for 10 runs, at each run, first fix random seed, then run the four algorithms (GD/SGD with small/moderate learning rate) under the same seed. In Table 1, we report the complete results from the 10 runs. By running paired t-test the 5% significance level, find that SGD with moder- ate learning rate is significantly better than GD with moderate learning rate (p-value = 0.0043). Similarly, SGD with moderate learning rate is significantly better than SGD with small learn- ing rate (p-value = 0.012), and is also significantly better than GD with small learning rate (p-value 0.0095).
Paired t-test for Figure 3
43


Reviews:
[{"review_id": "lNa0aMCzlv2", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nIn this paper, an implicit bias of SGD and GD in terms of the direction of convergence points is studied. This study shows that, in a setting of linear regression, SGD and GD converge to different directions, which are determined by the largest/smallest eigenvectors of a data matrix when the learning rate is moderately large. Experiments using synthetic data and Fashion MNIST support the theoretical results.\n\n\nDetailed comments:\nFirst of all, I don't have much experience in the analysis of SGD/GD and my assessment for technical points may miss some important points. \n\nOverall, the paper is well written. The motivation and problem setting are clearly written. Related work is sufficiently introduced. \n\nThe main theoretical results (Theorems 1, 2, 4) are interesting. As far as I know, there's no study to reveal the implicit bias in terms of direction. However, I have several concerns.\n\n1. In the data generation process, the noiseless output y = <w*, x> is assumed. However, the output often contains observations noise such as an additive Gaussian model as y = <w*, x> + $\\xi$ where $\\xi$ is small Gaussian noise. Would it be possible to show similar results in the noisy case?\n\n2. More importantly, the benefit of the directional bias is not clear. Theorem 4 shows SGD achieves $\\epsilon$-optimal solution and GD achieves $M$-suboptimal solution. However, we cannot conclude that SGD solution is better than GD solution because the generalization performance depends on the unknown constants $\\epsilon$ and $M$. So, GD may win in some cases but SGD may win in other cases, but it seems there is no way to know in what conditions $\\epsilon$ and $M$ satisfy some specific values so that SGD beats GD. Would it be possible to clarify the conditions?", "extra_scores": {}, "extra_text": {}}, {"review_id": "jgw_IKjC_sR", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes the differences in the convergence of SGD and GD when using \"small\" and \"moderate\" learning rates to shed light on why SGD with \"moderate\" and annealing learning rates perform well in practice. Focusing on an overparametrized linear regression problem, the paper claims that SGD with a \"moderate\" learning converges differently (along the large eigenvalue directions) compared to SGD/GD with a \"small\" learning rate (along the small eigenvalue directions).  They further show analytically for this problem that there exists a learning rate schedule (with moderate learning rates) such that SGD will perform + generalize well, while there exist small learning rate schedules such that GD will perform + generalize poorly.  \n\nThis paper is clearly written and presents a clear illustration of their hypothesis for why SGD with a moderate learning rate performs well in practice through Figure 1 and a simple linear regression example in section 3. The paper focuses most of its analysis on a toy example problem (overparametrized linear regression) and the empirical experiments do not clearly support the paper's claims.\n \nThis paper should be rejected as is. Although the motivating example and illustrations are interesting, the analysis for the overparameterized linear regression problem is too specific to clearly claim that this \"directional bias\" is why SGD with moderate learning rates is successful. \n\nI have two main concerns: (1) in the special case of overparametrized linear regression, Theorem 2 only shows that GD with small learning rates converge along the smallest eigenvalue direction. It does not preclude GD from having the same behavior as SGD for larger learning rates. I also do not agree with remark 4.\n(2) it's not clear how or why the results for overparameterized linear regression would extend to generic NN losses. The example experiments (Fig 2) need more detail to be clear and are not sufficient to support the hypothesis in the paper.  \n\nQuestions:\nIn section 3, doesn't Eq (3) show that GD will behave identically to SGD if the learning rate is doubled? What is considered a \"moderate\" learning rate for GD + SGD does not need to be identical, right? \n\nFor the overparametrized regression, why do we not include some form of regularization on the weights (as would commonly be done in practice)? Does this affect the results?\n\nWhat is the minibatch size for SGD in the experiments? How are the results (in Figure 2a + 2b) sensitive to random initialization?  \n\nMinor comment: Page 6: the definition of level set probably needs a $\\leq$ sign.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "TzXjjeh1meN", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In the paper the authors analyzed the convergence dynamics toward a minimum of gradient descent (GD) and stochastic gradient descent (SGD). The algorithms are considered to start in the basin of attraction of a minimum, and using discrete steps they approach the bottom. The main result of the paper concerns the fact that, with moderate learning rate, SGD approaches the minimum along the steepest direction, contrary to GD.\nThe authors conclude that the implicit bias of SGD does not appear in small learning rate formulation, but it becomes manifest when a moderate learning rate is considered.\n\n* It seems from the analysis that SGD differs from GD because its learning rate is modified by the batch size and therefor it uses an \"effective learning rate\". The question is : what would happen if GD is taken with a learning rate that matches the effective learning rate of SGD? This situation is very similar to the one observed in [Nakkiran (2020)] (and also close to [Lewkowycz et al. (2020)]), where they consider GD and draw similar conclusions. \n\n* Another questions is whether it is really necessary to have discrete steps to have a difference between GD and SGD in the continuous formulations. In the introduction the authors make a comparison between the implicit biases in the literature for GD and SGD claiming that they are the same because of the small learning rate. However this is not clear to me, could the authors cite papers where this is explicitly shown? \nIn particular there is a literature on the effect of SGD in the continuous formulation [e.g Jastrzebski et al. 2018 (arXiv:1711.04623); Zhu et al. 2019 (ICML2019); Xie et al. 2020 (arXiv:2002.03495)] using stochastic differential equations it was possible to show that SGD has an implicit temperature that adapts to the geometry of the landscape favoring, in particular, flatter solutions. In few words, do we need to rely on the discrete formulation to understand the advantages of SGD?\n\n* The result by [Nakkiran (2020)] seems to heavily rely on having a data distribution that is highly homogeneous to observe the difference between the training and the generalization loss. Do we have evidence that this is relevant for practical situations?\nI would happy have more numerical experiments as the one in Fig.2 . In particular showing the effect of increasing the learning rate in GD (and SGD) from the current \"small\" value to a value large enough so that it does not converge anymore. Both in the synthetic and real dataset.\n\nThe questions above block me from giving a higher rating, but I will be happy to increase the rate given satisfactory answers.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work compares and contrasts the learning rate dynamics of GD and SGD and shows that under practical learning rate settings, SGD is biased to approach the minimum along the direction of steepest descent, leading to better performance. Reviewers agree that the theoretical results are significant. The authors satisfactorily responded to reviewers’ questions and improved the paper’s clarity during the discussion phase.
Decision: Accept (Poster)