Training By Vanilla SGD with Larger Learning Rates
Authors: Yueyao Yu
Jie Wang
Wenye Li
Yin Zhang
Venue:  (2021)

Abstract: The stochastic gradient descent (SGD) method, first proposed in 1950's, has been the foundation for deep-neural-network (DNN) training with numerous enhancements including adding a momentum or adaptively selecting learning rates, or using both strategies and more.  A common view for SGD is that the learning rate should be eventually made small in order to reach sufficiently good approximate solutions.  Another widely held view is that the vanilla SGD is out of fashion in comparison to many of its modern variations.  In this work, we provide a contrarian claim that, when training over-parameterized DNNs, the vanilla SGD can still compete well with, and oftentimes outperform, its more recent variations by simply using learning rates significantly larger than commonly used values.  We establish theoretical results to explain this local convergence behavior of SGD on nonconvex functions, and also present computational evidence, across multiple tasks including image classification, speech recognition and natural language processing, to support the practice of using larger learning rates.


Under review as a conference paper at ICLR 2021
TRAINING BY VANILLA SGD WITH LARGER LEARNING RATES
Anonymous authors Paper under double-blind review
ABSTRACT
The stochastic gradient descent (SGD) method, first proposed in 1950's, has been the foundation for deep-neural-nntworkk (DNN) training with numerous enhance- ments including adding a momentum or adaptively selecting learning rates, or using both strategies and more. common view for SGD is that the learning rate should be eventually made small in order to reach sufficiently good approximate solutions. Another widely held view is that the vanilla SGD is out of fashion comparison many of its modern variations. In this work, provide con- trarian claim that, when training over over-paramenn peer-parametriiee DNNs, the vanilla SGD can still compete well with, and oftentimes outperform, its more recent variations by simply using learning rates significantly larger than commonly used values. We establish theoretical results to explain this local convergence behavior of SGD on nonconvex functions, and also present computational evidence, across multi- ple tasks including image classification, speech recognition and natural language processing, to support the practice of using larger learning rates.
INTRODUCTION
We are interested in minimizing a function f R -> R with an expectation form:
fzx = Eg (z, E),. zERd
min
(la)
where the subscript indicates expectation is computed on the random variable &. Specially, if the & probability distribution is clear and random variable & is uniformly distributed on N terms, the objective function can be expressed into finite-sum form:
min #EBd
f(x)
1 N
Σ M(x),
(Ib)
where J((x) : Rd + IR is the i-th component function. The optimization of Eqs.(1a) and (1b) is widely encountered in machine learning tasks (Goodfellow al., 2016; Simonyan & Zisserman, 2014).
To solve this problem given in Eqb(Ib), we can com- pute the gradient of objective function directly with a classic GD (Gradient Descent) algorithm. However, this method suffers from expensive gradient computation for extremely large N, and hence people apply stochastic gradient descent method (SGM) to address this issue. In- cremental gradient descent (IGD) primary version of SGM, where its calculation of gradient proceeds on single component f. at each iteration, instead the whole.
Barsion
As special case of IGD, SGD (Robbins & Monro, 1951), a fundamental method to train neural networks, always updates parameters by the gradient computed on mini- batch. There exists an intuitive view that SGD with constant step size (SGD-CS) potentially leads faster
Figure The step size vs. iteration for nonconvex functions: in neighbor- hood of the solution, the learning rate can be constant value below thresh- old.

---

Under review as a conference paper at ICLR 2021
convergence rate. Some studies (Solodov, 1998; Tseng, 1998) show that, under a so-called strong growth condition (SGC), SGD-CS converges to an opti- mal point faster than SGD with diminishing step size.
In this work, we study the local convergence (or last-iterate convergence as is called in Jain et al. (2019)) of SGD-CS on nonconvex functions. Note that SGD-CS does not provide guarantee of converge when starting from any initialization point. Therefore, a useful strategy is to use SGD with a decreasing step size at the beginning, and then switch SGD-CS in neighborhood of minimizer. Fig.1 illustrates the range of the step size of SGD versus the number of iterations.
Our main theoretical and experimental contributions are as follows.
We establish local (or last-iterate) convergence of SGD with a constant step size (SGD- CS) nonconvex functions under the interpolation condition. We note that previous re- sults are mostly for strongly convex functions under strong (or weak) growth condition. Our result is much closer common situations in practice.
We discover that on linear regression problems with l, regularization, the size of conver- gent learning rates can be quite large for incremental gradient descent (IGD). Our numeri- cal results show that, within a fairly large range, the larger step size is, the smaller spectral radius is, and the faster the convergence rate is.
Based on the above observations, we further propose a strategy called SGDL that uses the SGD with a large initial learning rate (more than 10 times larger than the learning rate in SGD with momentum), while still being a vanilla SGD. We conduct extensive experiments various popular deep-learning tasks and models in computer vision, audio recognition and natural language processing. Our results show that the method converges successfully and has strong generalization performance, and sometimes outperforms its advanced vari- ant (SGDM) and other several popular adaptive methods (e.g., Adam, AdaDelta, etc).
2 RELATED WORK
There are many papers on stochastic optimization and we summarize typical ones which are most relevant with our work. The convergence of SGD for over-parameterized models is analyzed in (Vaswani et al., 2018; Mai & Johansson, 2020; Allen-Zhu et al., 2019; Li & Liang, 2018). The power of interpolation is studied in (Ma et al., 2018; Vaswani et al., 2019). The work (Jastrzębski et al., 2017) investigates large ratio of learning rate to batch size often leads to a wide endpoint. The work (Smith & Topin, 2019) shows phenomenon called super-convergence which is in contrast to the results in (Bottou et al., 2018). More recently, several new learning rate schedules have proposed for SGD (Loshchilov & Hutter, 2016; Smith, 2017: Agarwal al., 2017: Carmon al., 2018).
Adaptive gradient methods are widely in deep learning application. Popular solutions include AdaDelta (Zeiler, 2012), RMSProp(Hinton
al., 2012), Adam(Kingma & Ba, 2014) and so on. Unfortunately, it is believed that the adaptive methods may have a poor empirically performance. For example, Wilson al. (2017) have observed that Adam hurts generalization performance in comparison to SGD with or without momentum.
The work (Schmidt & Roux, 2013) introduces SGD-CS that attains linear convergence rate for strongly convex functions under the strong growth condition (SGC), and sublinear convergence rate for convex functions under the SGC. The work (Cevher & Vu, 2018) investigates the weak growth condition (WGC), the necessary condition for linear convergence of SGD-CS. For general con- vex function, the work (Ma et al., 2018) shows that SGD-CS attains linear convergence rate under the interpolation property. For finite sum f. the interpolation property means ff(")) 0 for i 1..... N. which is held apparently in over- pweepparaeteriized DNN. However, the theoretical analysis of SGD-CS for nonconvex functions less mature in the convex case.
2

---

Under review as a conference paper at ICLR 2021
3 PRELIMINARIES
3.1 NOTATIONS
We denote the minimizer of object function f as x² and use usual partial ordering for symmetric matrices: A = B means A B is positive semidefinite; similar for the relations ,, The norm || either denotes the Euclidean norm for vectors or Frobenius norm for matrices. The Hessian matrix of each component function fi(x) is denoted (z). With slight abuse of notation, the Hessian matrix H, at x is denoted as H We also denote the mean and variance of {H{,.. H
as H' = Ei Hi and E = x E (Hz)² - (H*) and define a = min(a, b). X & Y
means random variable X converges to random variable Y in probability, while X _. Y means X converges to random variable Y in L norm.
3.2 ASSUMPTIONS
Our results are under the following mild assumptions:
(A.1) The objective function f has the same structure given in Eq.(1b).
(A.2) Each component function fi in (q. is twice continously differentiable, with the corre- sponding Hessian matrix H2 being Lipschitz continuous for constant L, at the minimizer x². Without loss of generality, we suppose that
[1+((x) H:(x" Il < L||x 2"I|,
for = I, where L = max Li-
(=1....N
(A.3) As in (Zhang et al., 2000, Remark 5.2), we assume the point of interest x² strong minimizer (i.e. H(x") > 0).
Assumption (A.3) restricts that the objective function is essentially strongly convex sufficiently small neighhorhood of a minimizer. The work (Liu et al., 2020) investigates that the loss function is typically nonconvex in any neighborhood a minimizer. However, this assumption is not restrictive in the regularization setting.
study the & regularized problem instead, and then the Hessian matrix becomes positive definite. This phenomenon is also validated in numerical experiment in Section and we add &g regularizer in DNNs in Section 6.
Remark 1. Even if the Hessian matrix of the point of interest x² has zero eigenvalues,
Based on the above technical assumptions, we focus on the convergence analysis of SGD-CS by discussing the convergence behavior precisely:
1
m
Tk+1
Tb a
e (Ix).
m
Next, we introduce the notion of point attraction to help us understand the convergence behavior to (2).
Definition 1. We say xt is point of attraction to (2) if there is an open ball N(a", ,e) of x", such that.or any 2 E NN, , { generated by (2) all lie in N and converges to x² the norm.
The Ostrowski Theorem says sufficient condition for x² to be a point of attraction of the deter- ministic iteration Øx+1 T(xx) is that the spectral radius of T'(z) is strictly less than one, which further implies the condition that there exists an open ball A such that once the initial xn N, the iterates (Ix. will converge to x" with linear rate. We define the strong minimizer x² point of strong attraction following the similar manner.
Definition 2.
We say x² a point of strong attraction to Eq. if there exists neighborhood N of x², such that for any x. E N, the sequence {Ik} generated by Eq. all lie in N and satisfy
E El ==112 p² || xx 1=1 for some p [0, 1).
3

---

Under review as a conference paper at ICLR 2021
The following discussion studies necessary and sufficient conditions for the minimizer x" being point of attraction of SGD with the constant step size a. However, starting from any initialization point, SGD-CS cannot be guaranteed to find such local neighborhood around z², except in some special cases including the loss function studied Section 5 and Appendix A.2. Therefore, a prac- tical strategy is 2018), and as long as the iteration points belong to neighborhood of a point of attraction, one can use constant step size.
diminishing step size when starting from random initial point (Allen-Zhu,
4 RESULTS FOR NONCONVEX FUNCTIONS
In this section, we rigorously show the necessary condition for the minimizer x" being a point of attraction, and Theorem provides sufficient condition for the strong minimizer x be a point of strong attraction with high probability. The detailed proofs are in Appendix.A.I.
4.1 NRCESSARY CONDITION
Lemma 1. Suppose that the assumptions (A.1) and (A.2) hold, then
[VS((=)] < Le + |Hzlle for = 1, I,
provided that (N(x",,))
Theorem 1. Suppose that the assumptions (A.1) and (A.2) hold. If the minimizer xf is point of attraction of (2)( then the interpolation property satisfied, i.e.
Vfi()") =0 for = 1 1,..., N.
4.2
SUFFICIENT CONDITION
4.2. 1
SUFFICIENT CONDITION FOR POINTS OF STRONG ATTRACTION
Define the error function (I)
cxx)) HH (x-x") [v)()> fi(
(3)
This error function quantifies the residual for the first-order Taylor expansion for Vf((x) around the point x" since
ff(()) Vf((=*) + H3 x²) + cx)))
By substituting (I( into Eq.(2), we have
1
1k+1 xx= = =x
>
H ( (Ix - xxx) + (e()((x)]] - x
j=1
(4)
[T -
(I-aHl aH' all (ux x²) -re - (2x)
addition, our proof for sufficient condition indicates a bound on the error function. Lemma 2. Suppose that the assumptions (A. 1) and (A.2) hold, and x" is local minimizer of J. If the interpolation property is satisfied, then the error function defined in Eq.(3) is bounded by:
[e,(x)) < - 12
(5)
Under the assumption that {ox} stay in the local neighborhood, we can show that interpolation property is sufficient condition for x being point of strong attraction of Eq,()), provided that the step-size o is sufficiently small.
Theorem 2. Suppose that the assumptions (A.1)-(A.3) hold, then {zx generated from (q. all lie in the neighborhood ( and [B[ x+1 pi k- x" [1] [2] if the radius p and the step
4

---

Under review as a conference paper at ICLR 2021
size satisfy the following conditions:
= Amax
T 2aH + a² (H 2 + 22 +aIee) <1,
(6a)
Xmaxx ( 2Xmax I [mmin(H+))
0 <<a
min im
(6b)
0 a < 2Amin ([(1))) + E" + 12 - Le))((H)) + -1211111))
(6c)
If f((x)) = for i ,,...,,, N, then the minimizer x² is a point of strong attraction of the iteration (2).
4.2.2 STAYING IN THE LOCAL NEIGHBORHOOD
Now we show that {æ generated from Eq.(2) all stay in the local neighborhood with high prob- ability. The proof follows the idea (Tan & Vershynin, 2019). the remaining of this section, we abuse the notation slightly and denote X as random vector in the k-th iteration of SGD-CS scheme, and zy as the realization of Xx. Considering the setup of Theorem without assuming that } always lies in the neighborhood N(*", ,e), we have the following technical results.
Lemma 3. Let To E Naxx, c) such that ||ag - x= I VBe for some ô E [o, 1). Define the stopping time r = minfk: f X2 & Nx"" ,)), then P(T 00 1-
Remark 2. With the setup stated Lemma 3, the sequence {or} stay in the local neighborhood N(x c) with probability least 1 5.
Indeed, we can show the result in Theorem 2 by relaxing the assumption into that the sequence generated by (2) stays in the local neighborhood within infinite iterates. Under the setup stated in the Lemma 3, we build the sufficient condition for points of strong attraction with the probabilistic guarantee.
Theorem 3. There exists event E which holds with probability at least P(E) 2 1 5 and the sequence {0x} generated by Eq (2) satisfies
E|l - x 11 p
x²1
(7)
It's clear that x" point of attraction if it is point of strong attraction. Therefore, once the event that the iterates generated from SGD-CS stay in the local neighborhood happens, the interpolation property becomes necessary and sufficient condition for the strong minimizer xt to be a point of attraction to (2).
Remark 3.
5 CASE STUDIES ON LARGE LEARNING RATES
This section shows Incremental Gradient Descent (IGD) with a constant step size actually converges into the global optimum point for some special problems, and then some numerical experiments presented to illustrate this point. We present the results through an example as follows, with more examples appeared in Appendix.A.2.
(wx = - 11 - b112 P 11
Under some mild assumptions (c.f Example in Appendix.A.2), the IGD with constant step size converges when
2N LE (0, p(DD + p( ATA)
where p the spectral radius.
The problem in (8) can be extended into general nonlinear least squares:
N Σ (((2) - R(x)" ((x).
f(x)
1=1
5

---

Under review as a conference paper at ICLR 2021
Corduve 1et
Compute
Left: the range of spectral radius where IGD converges, it can be seen there are wide range / for convergence. Middle: the Log error || 2112. The error line in blue grows slowly after an initial rapid rise. This implies that in the presence of noise, large t-values can still calculate x close x². Right: calculated solution of a large radius (3.0),the computed values of a(t) do not significantly deviate from the noisy data & within the large t-value.
Figure 2:
A sufficient condition for the convergence of IGD is
Xmax t E (0. 7 (I(HI;
where (xH, N Hx(t), and H:(-) denotes the Hessian matrix for the i-th component function (-).)
We conduct a numerical simulation for the regularized least squares problem in (8. Let training data be generated via x I=cz + NO, o²) where is uniformly sampled from (0, 10). The min- imizer x² does not necessarily represent the best solution available due to noise, so all approximate solutions within the same noise level should equally good fact.
The experimental results demonstrate that with large step sizes, IGD still converge and have decent performance, which meets our expectations. After the first sharp rise, the step size can be updated insensitive the error. In our next section, we will implement vanilla SGD with large initial learning rate and use this optimizer for large scale problems.
EXPERIMENTS
We show the empirical results of different models to compare our SGDL with other popular opti- mization methods, including SGD, SGDM, Adam, and AdaDelta. We focus the CIFAR10 and CIFAR 100 image classification task (Krizhevsky et al., 2009), with the downsampled variant of Im- ageNet named ImageNet32 (Chrabaszez et al., 2017), the Speech Commands Dataset for audio CroggitiionWardeee 2018), 8), and the language modeling task on Penn Treebank(MMrrcu et al., 1993).
6.1 CIFAR1O AND CIFAR
DerDein B
Cpcch
Cooth
Eoot
(a) Train eiror on CI- (b) Test error on CI- (c) Train error on CI- (d) Test error on FARI0.
FARIO.
FAR100.
FAR100.
Figure 3: Different learning rate for the vanilla SGD in the ResNet56 model on CIFAR10 and CIFARI00. Models are trained with learning rate from 0.2 to
The first experiment is carried out on the CIFARIO and CIFAR100 datasets, which are standard im- age collection with 10 and 100 classes respectively. After the preprocessing in Appendix A.3.1, we train VGG (Simonyan Zisserman, 2014), ResNet (He et al., 2016) and DenseNet(Huang al., 2017) for up to 150 epochs and minibatch size to 256. Additional, for all optimizers without

---

Under review as a conference paper at ICLR 2021
AdaDelta, use annealing strategy that the learning rate is lowered by 10 times epoch 50 and 100. For ResNet experiments, we select a ResNet network with 56 layers and 120 layers respec- tively. For VGG, rate k = 12. We first run a ResNet56 model on CIFARIO and CIFAR100 with different learning rates. From the results show in Fig.3 poor performance on the test set.
VGG16. For DenseNet,
DenseNet with 100 layers and growth
small learning rate like 0.2, 0.4 has relatively
(a) Test Error CIFARIO.
Ao Aw
Paoc
(h) Test Error CIFARIO0.
Figure 4:
The performance of several popular models CIFARIO and CIFARI00. Figures from left to right are for ResNet56, ResNetl 10, VGG16 and DenseNet, respectively.
We compare different optimization method including performance in Fig.4. We can see that our method still works fairly well and has the same or even better performance in comparison to SGDM and other optimizers.
and shows the
6.2 IMAGENET32
The second experiment is carried out on ImageNet32 dataset (Deng et al., 2009) with more than a million images in 1000 classes, out of which 50000 images are used testing set. Each image has 32 x 32 pixels. The objective is to train an image classifter. We apply similar train strategy as on the CIFAR10 and CIFAR 100 datasets in Section 6.1, except that the epoch budget is down to 120 and the learning rate is shrunk to one-tenth of its current value every 30 epochs.
Tran Emor
M
8
Top-1
20
43
80
100
120
83
100
120
22
20
100
120
Firnch
(a) Train Error.
(b) Top-1 Error.
(c) Top-5 Error.
Figure 5: Left: Train error for ResNet56 on ImageNet32; Middle: Top-1 1 eπror; Right: Top-5 error.
Our experiments is only focus on ResNet56 due to computational resource limitation. To adjust the difficulty on this dataset, we increase the model capacity for the previously used model by quadrupling the number of channels on each convolution layer. From the results Fig.5, find our method outperforms SGDM slightly about 0.5% for the best accuracy. More interestingly, SGD also has good performance, while two adaptive methods both work just passably.

---

Under review as a conference paper at ICLR 2021
6.3 AUDIO RECOGNITION
The third experiment is carried out the Speech Commands Dataset, which consists of recordings from thousands different people uncontrolled recording conditions. Each sample is represented as 16000-dimension vector. Each recording is one second in length. We divide the data into training set and a testing set.
With the dataset, train 2-layered neural net with 20 channels, 2D dropout layer and full-connection layers with 1,000 hidden nodes. More specific hpyerparameter settings is in Ap- pendix.A.33 3.2. A.3.2. From the results in Fig.6, we can see that SGDL has quite competitive effect and outperforms vanilla SGD exceedingly.
6.4 LSTM LANGUAGE MODEL
(a) Train Error.
(b) Test Error.
The fourth experiment carried out on the standard language modeling task Penn Tree- bank (PTB) dataset. The learning rate is se- lected and optimized for several years and the current state-of-the-art results supported our perspective about large learning rate (Merity al., 2017a). We focus compare the effect of SGDL, SGDM and other optimizers on top of a state-of-the-art {2, 32 LSTM training recipe with some training tricks (Merity al., 2017b;a; Inan al., 2016; Gal & Ghahramani, 2016). The details on LSTMs are in A.3.ndix.A.333.
Figure LeNet5 on Speech Commands Dataset.
125
Tran
Spach
Epech
Epoch
(a) Perplexity in 2-layer LSTM.
(b) Perplexity in 3-layer LSTM.
Figure 7: LSTM on Penn Treebank Dataset. For Fig. (a) and Fig. (b), the left shows Train Perplexity and the right shows Test Perplexity.
From the result in Fig.7, we evaluate the performance by perplexity metric. We find that Adam the fastest on the initial progress, but its final performance is worse than our SGDL. We also investigate AdaDelta has terrible performance, while SGDM has almost same curves with ADAM.
6.5 DISCUSSION
In Sections 6.1.,,4, we have observed that if vanilla SGD has the same learning rate as SGDM, tends to a poor generalization performance some tasks and this one of the reasons why SGD is usually shelved for training models nowadays. Our experiments show that larger initial learning rate increases the test accuracy on Fig.3. Further more, can be seen that SGDL has an admirable performance in our experiments and outperforms SGDM in some tasks. For various deep neural networks such as Densseet, VGG, our SGDL works well, which is not affected by abundance layers or the existence of the residual mechanism. The experimental results have provided evidence that SGD with large learning rate is a good alternative to SGD with momentum in some practical tasks.
8

---

Under review as a conference paper at ICLR 2021
7 CONCLUSION
We provide a rigorous proof on the local convergence behavior of SGD-CS on smooth and noncon- vex functions. Motivated by numerical experiments IGD, recommend vanilla SGD with large learning rate (SGDL) for training neural networks. Extensive evaluations have been carried out in deep learning tasks (CV.Speech,NLP) with popular neural network architectures. The results have demonstrated the smooth convergence and effective generalization performance of SGDL. For our future work, we will analyze the effect from more training strategies such batch normalization about convergence. We will also analyze the pros and cons in SGD and its variants (SGDM) in our further work.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approxi- mate local minima faster than gradient descent. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1195-1199, 2017.
Zeyuan Allen-Zhu How to make the gradients small stochastically: Even faster convex and non- convex sgd. In Advances in Neural Information Processing Systems. pp. 1157-1167, 2018.
Zeyuan Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference Machine Leurning, pp. 242-252. PMLR, 2019.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311, 2018.
Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal Optimization, 280))1751-1772,, 2018.
Volkan Cevher and Bang Cong Vu. On the linear convergence of the stochastic gradient method with constant step-size, 2018.
Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. A downsampled variant of imagenet as an alternative to the cifar datasets. arXiv preprint arXiv:1707.088/1 2017.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pp. 248-255, Icee, 2009.
Rick Durrett. Probability: theory and examples, volume 49. Cambridge university press, 2019.
Yarin Gal and Zoubin Ghahramani. theoretically grounded application of dropout in recurrent neural networks. In Advances in neural information processing systems, pp. 1019-1027, 2016.
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning lecture 6a overview of mini-batch gradient descent. Cited on, 14(8), 2012.
Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700 4700, 2017.
Hakan Inan, Khashayar Khosravi, and Richard Socher. Tying word vectors and word classifiers: A loss framework for language modeling. arXiv preprint 161 2016.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint 1.Xiv:1502.03: 2015.
Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. Making the last iterate of sgd information theoretically optimal. volume 99 of Proceedings of Machine Learning Research, pp. 1752-1755, Phoenix, USA, 25-28 Jun 2019. PMLR. URL http: http:::/ppoceeednnge.. www.pp..e...ee.mmm. /v99/ Jain19a.his html.
Stanislaw Jastrzębski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima in sgd. arXiv preprint arXiv: 2017.
10

---

Under review as a conference paper at ICLR 2021
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems, pp. 8157- 8166, 2018.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Toward parameterized systems of non-linear equations: the lessons of deep learning. arXiv preprint arXiv:2003.00307, 2020.
theory of optimization for over-
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv: /30800383,, 2016.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effec- tiveness of sgd in modern over-parametrized learning. In International Conference on Machine Learning, pp. 3325-3300 3334,, 2018.
Vien V Mai and Mikael Johansson.
Convergence of stochastic gradient method with momentum for nonsmooth nonconvex optimization. arXiv preprint arXiv:2002.05466 2020.
Mitchell Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. Building large annotated corpus english: The penn treebank. 1993.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing Istm lan- guage models. arXiv preprint 1708.02200.,18. 2017a.
Stephen Merity, Bryan McCann, and Richard Socher. Revisiting activation regularization for lan- guage rnns. arXiv preprint arXiv: 700,00009, 2017b.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400-407, 1951.
Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint arXiv: 3008. 6370, 2013.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.
Leslie N Smith. Cyclical learning rates for training neural networks. In 2017 IEEE Winter Confer- ence on Applications of Computer Vision (WACV), pp. 464-472. IEEE, 2017.
Leslie N Smith and Nicholay Topin. Super-convergence: Very fast training of neural networks using large learning rates. In Artificial Intelligence and Machine Learning for Dolti-DDmain Operations Applications, volume 11006, pp. 1100612. International Society for Optics and Photonics, 2019.
Mikhail V Solodov. Incremental gradient algorithms with stepsizes bounded away from zero. Com- putational Optimization and Applications, 11():223-35 1998.
Yan Shuo Tan and Roman Vershynin. Phase retrieval via randomized kaczmarz: Theoretical guar- antees. Information and Inference: Journal of the IMA, 8(1):97-123, 2019.
Paul Tseng. An incremental gradient (-projection) method with momentum term and adaptive step- size rule. SIAM Journal on Optimization, 8(2):506-531, 1998.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and an accelerated perceptron. arXiv preprint arXiv: 1810.07288, 2018.
Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste- Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. In Ad- vances in Neural Information Processing Systems, pp. 3732-3745, 2019.

---

Under review as a conference paper at ICLR 2021
Pete Warden. Speech commands: A dataset for limite--vocabulary speech recognition. arXiv preprint orXiv:180..032000 2018.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal
value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, pp. 4148-4158, 2017.
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv:1212.5701, 2012.
Yin Zhang, Richard Tapia, and Leticia Velazquez. On convergence of minimization methods: attrac- tion, repulsion, and selection. Journal of Optimization Theory and Applications, 107(3):529-546. 2000.
A APPENDIX
A.1 PROOFS FOR SECTION 4
Proof of Lemma 1. For I,..., N, by Lipschitz continuity of H; at x", for any y N(x"" e),
(1) H s Llyy
==|| Lc.
and therefore Hy( < Hy H + +| Le | For fixed x E NNxx c). define (1( Va(x l(x xx )), and therefore g((() (x =x)'"H((>'* 1(x x² )). By the
fundamental theorem of calculus.
[x)x)) Vf((=*)] = 119:(1) 9:(0)ll = L (t dt
(g)(())) dt 1// 11x x²) Helx" + - x"))ll
<
||+ - x= "111||1i( + 1(x x x²))
||x [|r->"11(A4 2"'l(Le + HH dt
< Lea + ||A
Proof of Theorem I. Being a point of attraction, the sequence {Ix} satisfies the Cauchy criteria: x.Ill 0.
lim N
sup m,n2N
Then 100 E| - xxll = Substituting 06+1 with the iteration (2),
lim Ea k0000
m
m
a lim
E
V
5s (xk)
k000
m
j=1
m
a lim
Σ
Ve, (Fx)
10000
Nm
m
fimm El N)m
Since |1 -m
m Σm
See (#x)
2 O for fi. {1...., N and all iterates hr
1
lim E
V fe, (2+)
= 0, for any fim E [1,...,N.9.
100
1=1
12

---

Under review as a conference paper at ICLR 2021
In partieular, when & fm for fixed i .N,
lim E [x =
k-000
For fixed = 1,..., N, the hyphothesis of the bounded convergence theorem (Durrett, 2019, Theo- rem 1.5.3) is satisfied:
VV S LE + |1 for any E Wix e), following the result in Lemma (1).
[ + [Vff(=*)] 24 E x' implies (zxo)l E [V)((=)]] By compari- son theorem for convergence, || [zx))l & [V((')]
Applying the bounded convergence theorem on (9) over the region N( c) gives
E lim [[x)( = E| f. ||| [V =0, for I,...,N,
which implies the desired result.
Proof of Lemma 2. By the interpolation property and definition of ex(x) for = 1, I....,N,
c(x)) H (x (x)=") + Vf(())
=-Hī H (x x*)= Vfi(=" + (x xx))
HH (x" [Vii(=)) + H1(x" + +1 - (()=-x)])-- (x- 220-x" x²)] for some E [0.
(10a)
[H,(x" + + H (a xx)),
(10b)
where (10a) is by the Taylor expansion on fz()), and (10b) is because Vf((x*) = 0. By Cauchy- schwarz inequality,
[(](())] s |H 1(x x²)) H3 I|| x²1l
< L [((x x") | x"1l
(10c)
L 1 x² 2²1
where (10c) is by Lipschitz continuity of H, at st"
Proof of Theorem 2. Since the step size
(1.....) Amax {H)) the term
0 H = I, for I....,N.
Substituting (4) into the term || - x 21 gives
| - x=12= =
all c/ (Ix - xx") -ae (x5))(x)))
(IR x²)=(I all al! (m) ( xx")
max
je (1 mI....m
+ + (Ita) )1 20( x² 2²²T(T aH' (e)) (11a)
cl
< max je (I....mm))
(xx- - (1 aH! 5/
( - x²)
+ + (xx))|² + 2a fal x'Illl I aH c ( (xxi)l (11b)
(IR xz) TT)T(T a (1 )( - x²)
max
(l......
+ I 1ark - 1111² + 2TL aH - 1²13
(11c)
(It (xx-20 x²)
max je(I....m)
all
(111)))) 22+ 22 1122|/11 x111 2 2aL 12x x= "1|l affiolll
(ax xx))
x²)
(Ix xz)J (T (T- (6))
) oT.2 2ale (ox-xx) x*) (11d)
max jE(L..m)
13

---

Under review as a conference paper at ICLR 2021
where (11a) follows from the inequality | Σ a:ll < mI la (11b) follows from
the Cauchy-Schwarz inequality on the last term; (11c) follows from Lemma (2); (11d) is because that the sequence { E [2",,, e). and that | qu S 1.
Therefore, taking conditional expectation both sides given vy. implies
B B|| - x=1 xn]
(Ix =²)²
max je( m
B BRD [(1 aHf + L22 +2Le)
(12)
(ox x*)
The expectation term Egg {(I aH {(N)) ((n)) ) can be simplified as follows:
%
E Beol [TT aH' =²
I - 2aH (H (
)
(6))
44
I 2all" a (1)
N
1
= 1 2aH" ta (11))
(13)
N 1=1
I 2aH' + (1-) + a²
(H - -()))-(1)))))
1
N
- 2aH + aa a ,
Combining (12) and (13) gives an upper bound on E[]|+ - x x112 xx]:
B[||0441- - x=1 œu] < (Ix (x=- (
(mx-x")
Since and are sufficiently small such that
p Amaax (1 [-22HH' (HH)) + + 2 -2lell <1,
the conditional expectation is further upper bounded by
E [| x. æ S p| 2²1
Therefore,
B||| x=||= [|2] = E [ - 2²1 m S pBll|z x² 11.
(14)
Furtheremore,
B||l2* x=11²1 < pBilla - x 1=1 111 ... p² 1001 x='1-
By (6b),
1' > Lel,
(15)
2aH > 0.
(16)
Since H Lel > 0 and by (6c),
a((1)) + ) al 2H -Lell
(17)
Combining (16) and (17) gives
0 = I - 2 (HH) +22121 2aLel I
14

---

Under review as a conference paper at ICLR 2021
Proof of Lemma 3. Let F& denote the o-algebra generated by the first & SGD-CS random vectors
c(lmm) Sk
c(1mm) Construct Z₁= = 11 prnk
11² Firstly we show that Z is a supermatingale:
1=
F
x2
B|Z
Fil
=E
Fx
IF
7 Fk
p=((k+2)
pra(kt1)
[Xrak 1011?
[x++I
x=11
E
175h FR
+
1 Fl
prnk
phtt
@
Z +
patt /
1
B [||X*+1 x² 1r>k Fiol
(1)
S Zkl + pett [11x - x 1"1111>a||Ta
ZglTsk + Zklr>k Zk: [x 11
where (i) is because that in Theorem (2). As result,
1k is measurable with respect to Fki (ii) is by applying (14)
||x 11 Fo E
||,,
x 112
Zo 2 B & Fol
E
PTAR
N2T
12T
Fo
By definition of the stopping time, ||X,- x²12 1| 2 e: and the term Zo ||:00
x011 S 8c2 since
|100
x=1 Voc. Substituting these two relations into the inequality above gives
de E
1AZ Fo = 62
Fo 2 EL,2 Pfk 2 T}. Ak.
Or after a rearrangement, 2 P(r o0). which implies P(r = 00) 2 1-88. 8.
Furthermore,
B| x= 22 EIIIX x c0 00) 2 (1- O| -x 111 oo).
(18)
Apply Theorem (2) bound B|| X x=1 21
Bll|X x= 1|2 [ S p² 11:0 - x x²1
(19)
We now estimate [ xx 1| r = oo] by utilizing (18) and (19):
/
1100 x²1 [|| Xx - 111 = x0) S 11
Proof of Theorem 3. Define the event E = (r )0). It suffices to show the relation (7). By direct calculation,
E[| X x² 1111, X₂ = 2x] S E X - x= 0=1121 X₂ = Øx.
[ -x" -2"1121>>k
X₁ = kk, Fil
R[[|X =x'12 Xx = Ik, Fx
p|| x 1
where the last inequality follows from (14). As result,
[|| X x 1121
= E { [E[] Xx+1 x=1121 1121 Xxl}
- [| X x:" 11
Inductively, E[[|X2 - x² 112 S |01 - xx 1|2. Therefore.
E|||X, x= || = El| Xx,
x² 1 1 s Ei|lX, x= 1| S pp1100 ==1
which completes the proof.
Proof of Remark 2. Conditioned on the event (T = oo). we have
P(IIXx - x" 2|2 > 2 T = =oo) =0
It follows that
P(] x011 < <e P([ x 2²1 < 2 T -0)
15

---

Under review as a conference paper at ICLR 2021
A.2 EXAMPLES
Example 1. (Quadratic Functions) Consider minimizing for the objective function f(x) Ei= oi x, where -RNx x1, and ft =xī,i [N.. Then the gradient of each compo- nent Is is given by
()(x)= = I,
where E; E N is a all-zero matrix except E = 1. Then the end-to-end N runs of IGD update with step size L can be expressed matrix compact form:
new
-K((tx='
where
N Kx(t) = II ==1
( (1- 21E, = diag(1 - 2t, - 2t, ,,, 10,1--200 2t).
(20)
Applying the basic knowledge in linear algegra, (tK)(tt) -1- 2t/. As long as E (0, 1), the IGD will converge from any initial point.
Example 2. (Standard Least Squares Problem) Consider the standard un-determined least squares problem
f(x) 1 114 bll AERmXN N <n Similarly, the end-to-end N runs of IGD update with step size t.forms the linear system
new (t) + tc(t),
with
Ko(()= I,, K₃()) 11 (I (I- 1=
and c(t) = Ein (1)jy,(t)ag. The sufficient condition for convergence is Amax (K N (t)) and Amaax(Ky NK (t)) < In this situation, we can assert that Amaxe X (Kx(t)) 2 1: we can pick E RR" \ {0) that Azo O, which implies (K x())))o
the necessary condition is Xmax
This means that
an eigenvalue of (x(1), Le., Amax (Kx (1)) 2 This example also suggests that regularization helps with the convergence in optimization.
Example 3. (Regularized Least Squares Problem) Consider the regularized least squares objective function
1 1 6112 1
f(x) can be shown that the end-to-end N iteration of IGD with step size can be expressed as a compact matrix form:
new = (NN(()) + te((),
(21a)
Ko(t)= = Ky(t) II 1 ta m
D) j= ;=,,..,,N
(21b)
c(t) = Σ by
(21c)
The necessary and sufficient conditions for the convergence of IGD suffice to characterize the con- dition p(t) p(Kx(t)) < 1. We need make of the famous conjecture about matrix AM-GM inequality:
For any positive semi-definite matrix PI, .a...., Pa E R
1 1 A
Σ
Po Pap ... Pa., 3
16

---

Under review as a conference paper at ICLR 2021
We make reasonable assumption that the products within K (t) commutativve, then applying this conjecture gives
ta,at -1 E1
- = =[1- E - A
L
(t(()=
3
N
Hence, a sufficient condition for the convergence would be:
(1'-
<1
Or equivalently, need to pick t such that, for any eigenvalue À of the matrix JDD + AT A, we have
(1- tA
(1-x) N
<I
2N
P(nD + AT
Example 4. (General Nonlinear Least Squares Problem) Consider the general nonlinear least squares problem:
N
1 -(=))= R(x)). Σ t=1
f(x)
2
By assuming that rx(x) are twice continuously differentiable for all [N), the end-to-end N iteration of IGD with step size I can be safely approximated as
new (x(t)x= + +te(t) + 0(1120 =11))²)
(22a)
Ko(t)= 11 K₃(1) II (I- j= --
(22b)
i=1
d() = Σ K k)-1(1)H((')rr
(22c)
is reasonable assume that Hx(x") ) is full rank for all since adding small regularization terms can resolve the rank deficiency issue. Applying the conjecture again, we imply that
N
t (t()) x 1 NI--- _u(()"))
Therefore, sufficient condition for the convergence of IGD would be
EE 0, Xmnax (E (x(H,(x+))))
where E(H,(x')) = N Σ Hx(x').
A.3 SUPPLEMENT TO EXEPERIEMENTS
A.3.1 IMAGE CLASSIFICATION
We normalize data and then augment them by horizontal flips and random crops from the image padded by pixels, filling missing pixels with reflections of the original image. We adopt Kaiming initializationHHe et al., 2015), BN (Ioffe & Szegedy, 2015) but without dropout. The models are trained for up to 150 epochs and minibatch size to 256. We select the best learning rate from Table. in Appendix.A.3.1 1.3.1 for SGD(M), and for SGDL, the learning rate is more than 10 times larger than the best SGDM Ir, in our paper, we select it from {1.0, 1.1, 1.2, 1.3), more specific parameter settings are as follows. Additional, for all optimizers without AdaDelta, we use annealing strategy to divide learning rate by 10 on 50 and 100 epochs.
The figures show results for ResNetl 10, VGG.DenseNet figure, the specific learning rate is given for SGDL. On CIFARIO, SGDL learning rate 1.0 for ResNet 56, 1.1 for DenseNet and 1.2 for 1e and VGG16, while CIFARI00, learning rate is 1.0 for VGG16 and 1.3 for ResNet 56, ResNetl 10 and DenseNet on SGDL. For SGDM, the learning rate is 0.1 for most experiments, while it is 0.05 for VGG16 on CIFAR10. 10. Finally, 0.001 is the most suitable learning rate for ADAM. On ImageNet, we use 1.1, 0.1, 0.001 as learning rate for SGDL,, SGDM, and ADAM.
CIFAR1O and CIFAR100. For each
17

---

Under review as a conference paper at ICLR 2021
Popular optimizers in the paper CIFARIO, CIFARIO0, ImageNer32 and Speech Com- mands Dataset. 7 denotes momentum, is the weight decay coefficient, is from Kingma & Ba (2014) and is from Zeiler (2012).
Table 1:
Optimizer
Learning rate
Other Parameter Tuning
Adam
{0.0001, 0.001, 0.01) 1.0 (0.001, 0.01, 0.05, 0.1}
8 (0.9, 0.999)
AdaDelta
= 0.9
SGD
? 0.005
SGDM
(0.001, 0.01, 0.05, 0.1}
1) = 0.9, 7 = 0.005
SGDL
2 10 + 1r(SGDM)
7 0.005
A.3.2 SPEECH COMMANDS DATASET
On Speech Commands Dataset, Similarly, the learning rate is 0.001 for Adam and 1.0 for AdaDelta as above. We choose 0.01 from {0.001, 0.01, 0.05, 0.1} as the best for SGDM and 0.15 for SGDL 15 times larger than SGDM.
A.3.3 DETAILS ON LSTM
For LSTMs, there are 1150 units in the hidden layer, an embedding of 400 and batch size of 20. We select the best learning rate 1 from {0.001, 0.01, 0.1, for SGD(M) and the learning rate is same above sections for Adam and Adadelta. For SGDI, we use 30 as an initial learning rate from the author's advise(Merity al., 2017a) on (2.3)-Layer LSTM for 150 epochs with the same annealing mechanism similarly above. To train all models, carry gradient clipping with maximum norm 0.25. More specifically, for those dropout values, we use (0.4, 0.3, 0.4, 0.1, 0.5) word vector, output between LSTM layers, output of final LSTM layer, embedded dropout and DropConnect respectively.
20
Acbem
14
1m
Autern DetaDeta
AdoDetta
16
SODL
Train Emerr
12
Test %
8
50
100
150
50
100
150
Epoch
Epoch
(a) Train Error for Resnet56.
(b) Test Error for Resnet56.
Figure 8: Resnet56 on CIFAR-10.
18

---

Under review as a conference paper at ICLR 2021
Adamm SGD SGDM 3GDL
16
SOD SGDM
Train Error %
SODL
12
Test Enor
10
50
100
150
50
100
150
Epoch
Epoch
(a) Train Error for Resnet 10.
(b) Test Error for Resnet 10.
Figure 9: Resnetl 10 on CIFAR-IO.
Aclam SGDM SGDL
Ackamn SOD SGDM SODL
16
Train Ertor %
12
Enor
10
6
50
100
150
50
100
150
Epoch
Epoch
(a) Train Error for VGGI6.
(b) Test Error for VGG16.
Figure 10: VGG16 on CIFAR-10.
Adam SGD
AcdeDelis
SGD SODM SSODL
SODM
Train Eroor %
SGDL
12
Enror
10
0-
8
6
50
100
150
50
100
150
Epoch
Epoch
(a) Train Error for DenseNet.
(b) Test Error for DenseNet.
Figure 11: DenseNet on CIFARIO.
Adam SGD
DedeDells SGD SCDM SGDL
16
38
SODM
Train Erer %
SGDL
36
12
34
4M (unlttrool
6
32
30
50
100
150
50
100
150
Epoch
Epach
(a) Train Error for Resnet56.
(b) Test Error for Resnet56.
Figure 12:
Resnet56 on CIFAR
19

---

Under review as a conference paper at ICLR 2021
AdaDetta
SQD
38
www
SGD
AdaDett
SGDM
SGDM
Train Enter %
BODL
36
BODL
12
34
6
32
28
26
50
100
150
50
100
150
Epoch
Epoch
(a) Train Error for Resnet1 10.
(b) Test Error for Resnet
Figure 13: Resnetl 10 on CIFAR100.
20
36
VWV
Adlmm AdaDetta S3D SGGM
Ackem
DdtDDtta SGD SGDM
Train Eror %
8ODL
%
26
100
Epoch
Epoch
(a) Train Error for VGGI6.
(b) Test Error for VGG16.
Figure 14: VGG16 on CIFAR
Adam SGDM
Acam SODM SCIEE
16
32
Train Enerr %
SGDL
12
Error
30
28
50
100
150
50
100
150
Epoch
Epoch
(a) Train Error for DenseNet.
(b) Test Error for DenseNet.
Figure 15:
DenseNet on CIFAR 100.
20


Reviews:
[{"review_id": "rgjVGmZ8jX", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Main idea: As a classical and effective optimizer, vanilla SGD can always compete with or even outperform its momentum or adaptive variations when training over-parameterized DNNs. The paper aims to theoretically justify this claim and empirically compare the performance across multiple tasks.\n\n1.\tWhat is exactly the overall advantage or difference between the SGDL and the vanilla SGD? Particularly, in how to choose the stepsize alpha?\n2.\tThere is no theoretical comparisons between SGD and its momentum and adaptive variations. Because the paper claims to theoretically justify the claim that “SGD is better”, can authors point out how they justify it theoretically?\n3.\tRemark 1 that follows theorem 2 gives particular conditions to make Eq.(7) hold. Can authors explain more on how to derive these 3 conditions 8(a)-(8(c)?  Does the proof assume that the initial point is close enough to the optimal solution? How can SGDL globally converge (converge from any starting point)?  \n4.\tIn experiments, what is SGDM? \n5.\tIn experiments, the paper uses decaying learning rate, so a large initial stepsize can quickly decay into a small number, so how does this become an advantage?  SGD has better generalization which has been observed in many prior works.\n6.\tThe paper has some typos, and the meaning of some sentences is puzzling.  For instance, (1) there are multiple uses of N in definition 2; (2) the index used in the paper is not consistent, i=1:N and i=1,…,N are both used in the manuscript and other format has been used in the proofs; (3) Eq.8(b) and the condition of theorem 2 are not consistent.\n\n#####################\nupdate:  I have read authors' response to my comments and also read other reviewers' comments and discussions.  The main concern of my comments is still not clear. I will keep my rating unchanged. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "eB6a-dDVRhy", "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": "This paper presents a theoretical analysis of SGD with constant step size (SGD-CS) and presents conditions under which SGD-CS leads to parameter updates that converge to a local minima, including parameters of non-convex functions.  The authors then show, in context of some special functions, that the step size can be fairly large yet convergence is achieved.  This is followed by a number of empirical studies of SGD with large (but annealed) step-size (SGDL) on a variety of tasks.\n\nI find the connection of SGD-CS with SGDL tenuous, and it is not clear that the theoretical analysis helps in selecting largest possible step size.  However, I do find the following contributions of the paper valuable:\na) Analysis of SGD-CS sheds lights on conditions under which the minimizers (local) of objective functions act as attractor (or strong attractor) of SGD updates.  This is worth sharing.\nb) The empirical results with SGDL show a very consistent pattern of SGDL outperforming other optimization approaches (including ADAM, SGD with momentum, etc.).  While this is not really SGD-CS, I find the consistent behavior of SGDL worth noting and sharing.\n\nSome clarifications and minor typographical errors:\n* SGC in last sentence of Section 3.1 is not defined.\n* Section 3.2 assumptions A.1 and A.2 should refer to Eq. (1b) and not (1a) I think\n* In Figure 2 which optimization approach is used to derive the curves?\n* In Fig. 6, the two curves in (a) and two in (b) … are they train and test perplexity results?\n* Last sentence of conclusions is unclear, please restate.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "FJhwVdZHFb", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper investigates the SGD with constant step size (SGD-CS) on non-conex optimization problems. Theoretically, the paper shows the conditions under which a minimizer $x^*$ is a point of attraction in a local neighborhood under the algorithm SGD-CS with sufficiently small step-size. Furthermore, the paper experimentally shows that vanilla SGD-CS with relatively large step-size performs well, or even outperforms its momentum and/or adaptive counterparts, on several popular deep learning tasks.\n\n[Comments]:\n\n1: Claim and analysis are not consistent. The authors claim in the introduction that convergence of SGD-CS on non-convex functions is shown. However, the analysis only focuses on points of attraction and the stay within a local neighborhood. I would like to point out that the latter concepts are not equivalent to convergence. To show convergence of an algorithm, the missing piece of the paper is that, starting from the initialization point, the algorithm can be guaranteed to find such a local neighborhood around the point of attraction. Without this guarantee, the analysis of points of attraction is meaningless in the sense of algorithm convergence. Hence, I disagree that convergence of SGD-CS is theoretically shown in the paper.\n\n2: Considering the necessary condition for points of attraction, Theorem 1, the assumption A.3 barely holds true in practical cases. As stated in Theorem 1, $x^*$ being a point of attraction implies interpolation property. For most real world tasks, interpolation can be only achieved when the model is over-parameterized, i.e., number of parameters is greater than the number of data samples. (For example, consider solving a system of linear equations). As pointed out by the work [Liu et al. 2020], most of the minimizers are not isolated, instead they form a low-dimensional manifold. In this case, none of the minimizers satisfies Assumption A.3, because the Hessian matrice H at the minimizers always have zero-eigenvalues (flat directions).\n\n3: The main theoretical result, Theorem 2, relies on the fact that step-size is sufficiently small. However, one of the main claims of the paper is the convergence under large step size, as discussed in Section 5 and experimented in Section 6. I don’t see the connection between the small step-size theoretical result and the large step-size experiments. The theory seems not to explain the experiments.\n\n4: The paper frequently talks about large learning rates. However, it is not clear to me what is the criteria to be large or small. Especially, in section 5, the paper provides a certain range of step size values (e.g., step size $t \\in (0, 1/\\lambda_{max}(H))$, within which the SGD-CS converges on a few simple examples. What are the reasons to claim these step-sizes are large?\n\n[About clarity]:\n\n1: It should be reader friendly to enlarge some of the figures.\n\n2: Providing an intuition of the error function, defined in Eq.(4), should be helpful.\n\n3: Notations can be improved.\n\n[References]:\n\n[Liu et al. 2020] Liu, Zhu, and Belkin. Toward a theory of optimization for over-parameterized systems of non-linear equations: the lessons of deep learning. arXiv:2003.00307.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "5z01jhbUF-L", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the smooth finite-sum problem under suitable conditions in the non-convex case. They show the necessary condition for the minimizer $x^*$ being a point of attraction, and Theorem 1 provides a sufficient condition for the strong minimizer $x^*$ to be a point of strong attraction with high probability. Based on the results, they introduce a modified SGD algorithm with a large initial learning rate (SGDL), and provide extensive experiments on various popular tasks and models in computer vision, audio recognition and natural language processing. \npros: 1, They give a sufficient condition for the strong minimizer $x^*$ to be a point of strong attraction with high probability. \n2, Extensive experiments are presented to show the effectiveness of SGDL. \n\ncons: 1, In Theorem 2, it is better to show how to choose the $\\epsilon$ explicitly and what linear convergence rate can be achieved, i.e., how small the parameter $\\rho$ can be. \n2, Even though this paper considers the non-convex case, the assumptions seems very restrictive. Assumption A.3 means that in a neighborhood of $x^*$, the objective function is essentially strongly convex. Furthermore, all $\\nabla f_i(x^*)$ need to be zero. \n\nminor comment: In the first inequality of the proof of Remark 2, why the bound is not zero? Since under the condition $\\tau=\\infty$, $||X_k-x^*||$ should be no larger than $\\epsilon$. \n\n---------------------After the rebuttal------\nThe authors partially addressed my concerns. I remain the current score.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper primary theoretical contribution claim is to establish the constant size SGD converges linear to the optimal solution in non-convex settings. This is shown in the interpolation regime for over-parametrized situations when starting from points nearby to the optimum. The paper's empirical claim is to use relatively larger learning rates for SGD in common deep learning settings and claim that they can do well. 

My recommendation is based on the overall low scores provided by the reviewers - which did not change post rebuttal. The concerns raised by the reviewers amounting to my decision recommendation is summarized below - 

Overall the reviewers found the connection between the theoretical results and the overall claims of the paper unconnected. The reviewers found the theoretical contribution of the local convergence weak - particularly in the context of an analysis of constant learning rates and taking into account existing work on the convex case for such results. Furthermore, the experimental contribution of the paper is incremental as the proposed algorithm is standard with just a larger than typical initial learning rates. This factor is usually searched over during Hyper Parameter sweeps in all the large scale learning setups. In this context, SGDL performing favorably, is an interesting observation but not enough of a contribution. Further the reviewers objected to the fact that SGDL does not connect with the theory presented as SGDL in experiments still uses learning rate schedules.


Decision: Reject