Stochastic Normalized Gradient Descent with Momentum for Large Batch Training
Authors: Shen-Yi Zhao
Yin-Peng Xie
Wu-Jun Li
Venue:  (2021)
Keywords: normalized gradient
large batch training size

Abstract: Stochastic gradient descent (SGD) and its variants have been the dominating optimization methods in machine learning. Compared with small batch training, SGD with large batch training can better utilize the computational power of current multi-core systems like GPUs and can reduce the number of communication rounds in distributed training. Hence, SGD with large batch training has attracted more and more attention. However, existing empirical results show that large batch training typically  leads to a drop of generalization accuracy. As a result, large batch training has also become a challenging topic. In this paper, we propose a novel method, called stochastic normalized gradient descent with momentum (SNGM), for large batch training. We theoretically prove that compared to momentum SGD (MSGD) which is one of the most widely used variants of SGD, SNGM can adopt a larger batch size to converge to the $\epsilon$-stationary point with the same computation complexity (total number of gradient computation). Empirical results on deep learning also show that SNGM can achieve the state-of-the-art accuracy with a large batch size.

Under review as a conference paper at ICLR 2021
STOCHASTIC NORMALIZED GRADIENT DESCENT WITH MOMENTUM FOR LARGE BATCH TRAINING
Anonymous authors Paper under double-blind review
ABSTRACT
Stochastic gradient descent (SGD) and its variants have been the dominating op- timization methods in machine learning. Compared with small batch training, SGD with large batch training can better utilize the computational power cur- rent multi-core systems like GPUs and can reduce the number of communication rounds in distributed training. Hence, SGD with large batch training has attracted and more attention. However, existing empirical results show that large batch training typically leads to a drop of generalization accuracy. As a result, large batch training has also become challenging topic. In this paper, we pro- pose novel method, called stochastic normalized gradient descent with momen- tum (SNGM), for large batch training. We theoretically prove that compared momentum SGD (MSGD) which is one of the most widely used variants of SGD, SNGM can adopt a larger batch size to converge to the e-stationary point with the same computation complexity (total number of gradient computation). Empiri- cal results on deep learning also show that SNGM can achieve the state-of-the-art accuracy with large batch size.
INTRODUCTION
In machine learning, we often need to solve the following empirical risk minimization problem:
1 T1 f((w).
min F(w)
(1)
WERE
where w E Rdd denotes the model parameter, denotes the number of training samples, fi() denotes the loss on the ith training sample. The problem in (1) can be used to formulate broad family of machine learning models, such as logistic regression and deep learning models.
Stochastic gradient descent (SGD) Robbins & Monro (1951) and its variants have been the domi- nating optimization methods for solving (1). SGD and its variants are iterative methods. the ith iteration, these methods randomly choose a subset (also called mini-batch) I, C (1,2,..., n) and compute the stochastic mini-batch gradient 1/B EiET, (w,) for updating the model parameter, where = II the batch size. Existing works Li et al. (2014b); Yu et al. (2019a) have proved that with the batch size of B, SGD and its momentum variant, called momentum SGD (MSGD), achieve (1IvVTB) convergence rate for smooth non-convex problems, where T is total number of model parameter updates.
With the population of multi-core systems and the easy implementation for data parallelism, many distributed variants of SGD have been proposed, including parallel SGD et al. (2014a), decentral- ized Lin et al. (2017), local SGD Yu et al. (2019b); Lin et al. 2020), local momentum SGD Yu et al. 2019a) and so on. Theoretical results show that all these methods can achieve
convergence rate for smooth non-convex problems. Here, is the batch size on each worker and K the number of workers. By setting Kb B, distributed methods is consistent with that sequential methods. In distributed settings, small number of model parameter updates T' implies small synchronize cost and communication cost. Hence, a small T can further speed up the training process. Based on the ((1/VTK)) convergence rate, we can find that if we adopt a larger 6, the will be smaller. Hence, large batch training can reduce the number of communication rounds in distributed training. Another benefit of adopting
observe that the convergence rate of these

---

Under review as a conference paper at ICLR 2021
CNN, CIFRA10
CNN, CIFRA10
2.5
80
B 128
B 4096
training loss
2
test accuracy
1.5
40
20
128
4096
0.5
100
150
50
100
150
#grad/n
#grad/n
Figure 1: The training loss and test accuracy for training a non-convex model (a network with two convolutional layers) on CIFARIO. The optimization method is MSGD with the poly power learning rate strategy.
large batch training is to better utilize the computational power of current multi-core systems like GPUs| et al. (2017). Hence, large batch training has recently attracted more and more attention in machine learning.
Unfortunately, empirical results LeCun al. (2012); Keskar al. (2017) show that existing SGD methods with a large batch size will lead to a drop of generalization accuracy on deep learning models. Figure [ shows the comparison of training loss and test accuracy between MSGD with a small batch size and MSGD with large batch size. We can find that large batch training does degrade both training loss and test accuracy. Many works try to explain this phenomenon Keskar et al. (2017); Hoffer et al. (2017). They observe that SGD with small batch size typically makes the model parameter converge makes the model parameter fall into the region of sharp minimum. And usually, flatten minimum can achieve better generalization ability than a sharp minimum. Hence, large batch training has also become a challenging topic.
flatten minimum while SGD with large batch size typically
Recently, many methods have been proposed for improving the performance of SGD with a large batch size. The work in Goyal et al. (2017); You et al. (2020) proposes many tricks like warm- up, momentum correction and linearly scaling the learning rate, for large batch training. The work in You et al. (2017) observes that the norms of gradient different layers of deep neural networks are widely different and the authors propose the layer-wise adaptive rate scaling method (LARS). The work in Ginsburg al. (2019) also proposes similar method that updates the model parameter in layer-wise way. Most of these methods lack theoretical evidence to explain why they can adopt large batch size. Although the work in You et al. (2020) proposes some theoretical explanations for LARS, the implementation is still not consistent with its theorems in which both of the momentum coefficient and weight decay are set zeros.
In this paper, we propose novel method, called stochastic normalized gradient descent with mo- mentum (SNGM), for large batch training. SNGM combines normalized gradient Nesterov (2004); Hazan et al.) (2015); Wilson et al.) al.) (2019) and Polyak's momentum technique Polyak 1964) together. The main contributions this paper are outlined as follows:
We theoretically prove that compared to MSGD which is one of the most widely used variants of SGD, SNGM can adopt larger batch size to converge to the e-stationary point with the same computation complexity (total number of gradient computation). That is to say, SNGM needs smaller number of parameter update, and hence has faster training speed than MSGD.
For relaxed smooth objective function (see Definition 2). we theoretically show that SNGM can achieve an c-stationary point with computation complexity of (11/²). To the best of our knowledge, this is the first work that analyzes the computation complexity stochastic optimization methods for a relaxed smooth objective function.
Empirical results on deep learning also show that SNGM can achieve the state-of-tt satte-of-the-nn the-art accuracy with large batch size.
2

---

Under review as a conference paper at ICLR 2021
2 PRELIMINARIES
In this paper, we use |I-I] to denote the Euclidean norm, use w to denote one of the optimal solutions of (1), i.e., w' E arg minw F(w). We call c-stationary point of F(w) if [VF())] <c. The computation complexity of an algorithm is the total number of its gradient computation. We also give the following assumption and definitions:
Assumption (a-bounded variance) For any V VF(w) S (o 0).
Definition 1 (Smoothness) A function ((.) is L-smooth (L 0) if for any u,
L
(u) S ((w))( + Vo(w)
w) | w|?. (u (u
L is called smoothness constant in this paper.
Definition (Relaxed smoothness Zhang et al. (2020)) A function Φ(-) is (L, smooooh (L 2 0, 0) if o() is twice differentiable for any
( S L + Vow)ll
where V (2w(w) denotes the Hessian matrix of ((w).
From the above definition, we can observe that if function d(w) is (I., 0)-smoohh, then it is
classical L-smooth function Nesterov (2004). For a (L, A--smooth function, we have the following property Zhang et al. (2020):
Lemma of) is (I, X)-smooth, then for any u, w, a such that I|u - w|l & a, we have
[Vo(u)] S (La [VV(()]))
All the proofs of lemmas and corollaries of this paper are put in the supplementary.
3 RELATIONSHIP BETWEEN SMOOTHNESS CONSTANT AND BATCH SIZE
In this section, we deeply analyze the convergence property of MSGD to find the relationship be- tween smoothness constant and batch size, which provides insightful hint for designing our new method SNGM.
MSGD can be written as follows:
V&+1 = [v. + g:>
W
7/V++1
(3)
ZiEZ, Vf((w) is a stochastic mini-batch gradient with batch size of B, and Vi+1 is the Polyak's 's momentum Polyak (1964).
where gi 1/BE iEZ,
We aim find how large the batch size can be without loss of performance. The convergence rate of MSGD with the batch size B for L-smooth functions can be derived from the work in Yu et al. 2019a). That is to say, when 7 S (1 ()2/((1 + L), we obtain
2(1 (Wo)) F(ww)]
Lnoz
4L211002
T/
(1 (1- B)B
(1- 3)2
-0
+ n/c
B
,
0
7 B
+ O(²),
(4)
where C = TB denotes the computation complexity (total number of gradient computation). Ac- cording Corollary in Yu et al. 2019a). set 77 vB/v B/VC and obtain that
1 VC
B2 c
E VV(((())))))
< v
0
+ 0
(5)
3

---

the t-th iteration, SNGM runs the Under review as a conference paper at ICLR 2021
Algorithm SNGM
Initialization: 7) > 0, B (0,1), 0, Up 0, Wo: for ,,,, do
Randomly choose function indices, denoted as Izi Compute mini-batch gradient g: B ΣiEI, Ww((w:);
U++1 -u, + 8i
Wc+1 W. 7/1
end for
Since 7 S (1-+))((1++))) necessary for 4. firstly obtain that B O(VC/L). Further-
more, according the right term of ()) we have B such that /2/C / 1/vC. ie.. B C1/4 for (11/<²) computation complexity guarantee. Hence in MSGD, we have to set the batch size satisfying
vc V.
B S Omiin T, T.CAAA).
(6)
We can observe that larger I. leads smaller batch size in MSGD. If B does not satisfy (6) MSGD will get higher computation complexity.
In fact, to the best of our knowledge, among all the existing convergence analysis of SGD and its variants on both convex and non-convex problems, we can observe three necessary conditions for the O11/e²) computation complexity guarantee Li et al. (2014b Lian al. 2207 x Yu et al. 2019b a (a) the objective function is T-smooth; (b) the learning rate y/ is less than (17L); (c) the batch size
proportional the learning rate 7). One direct corollary is that the batch size is limited by the smooth constant L, i.e., B < (1)L)) Hence, we can not increase the batch size casually in these SGD based methods. Otherwise, it may slow down the convergence rate and we need to compute more gradients, which is consistent with the observations in Hoffer et al. (2017).
STOCHASTIC NORMALIZED GRADIENT DESCENT WITH MOMENTUM
In this section, propose novel methods, called stochastic normalized gradient descent with momentum (SNGM), which is presented in Algorithm T following update:
g
U = fu; +
[g:
W++1 W. 1/1++,
where = =1/B (f((w)) is stochastic mini-bated gradient with batch size of B. When SNGM will degenerate stochastic normalized gradient descent (SNGD) Hazan et al. (2015). The u, is variant of Polyak's momentum. But different from Polyak's 's MSGD which adopts g: directly for updating u,+1, SNGM adopts the normalized gradient g:/ G for updating u,+1- In MSGD, we can observe that if g: is large, then u, may be large as well and this may lead to bad model parameter. Hence, we have to control the learning rate in MSGD, iec, 7) S (1/L), for a L-smooth objective function. The following lemma shows that ||l| in SNGM can be well controlled whatever gı large or small.
Lemma 2 Let (1t) be the sequence produced by 7 then have Vt 2 0.
1
|ull S
1-B"
4.1 SMOOTH OBJECTIVE FUNCTION
For smooth objective function, we have the following convergence result of SNGM:
4

---

Under review as a conference paper at ICLR 2021
Table 1: Comparison between MSGD and SNGM for T-smooth objective function. C denotes the computation complexity (total number of gradient computation).
B wwill
learning rate
batch size
MSGD
+
min S,Y,C,C C2/44
V2
SNGM
((tiaa)
VB
VC
VC
Theorem Let F(w) be L-smooth function (L 0). The sequence {w,] is produced by Algo-
rithm 7 Then for any yj >> 0, B > O, we huve
1
2(1 - (B)))))(wo) F(w")]
2x
E
VF(w:))
LuN
(9)
T
nT
/B B
1=
where K.
1+9 (1-3)2.
Proof See the supplementary.
We can observe that different from (4 which needs 17 S O(1/L), ( is true for any positive learning
rate. According to Theorem L we obtain the following computation complexity of SNGM:
Corollary Let F(w) be a s-sohoth function (L > 0). The sequence {w;) produced by Algo- rithm !
Given any total number of gradient computation C > O, let T = [C/B].
C(1 C(1-8)0 3)0²
21(1 + (F)((o))) - F(w"))
and
2(1 (F F(w))) (1+ B)LC
Then we have
8L(1 ()) F(w*) )002
4 VI())) s 2
0 C1/4
(1 (1- B)C
Hence, the computation complexity for achieving an e-stationary point is O(1/e2).
is easy to verify that the and B in Corollary make the right term of (9) minimal. However, the 7 and B rely the L and F(w F(w*) which are usually unknown in practice. The following corollary shows the computation complexity of SNGM with simple settings about learning rate and batch size.
Corollary Let F(w) be a T-smooth function (I. > 0). The sequence {we) produced by Algo- rithm! Given any total number of gradient computation C > 0, let T [C/B], VC and
/ B/C. Then we have
1
T-1 Σ
BIIV < 2(1 F)(F(w)) F(w")]
L(1 +
20 1
(1 (1- 1)2 C1/4 (1/4))
0
C1/4
Hence, the computation complexity for achieving an c-stationary point is (11(c))
According Corollary 2 the batch size of SNGM can be set as O(VC), which does not rely the smooth constant L, and the (1/=²) computation complexity is still guaranteed (see Table Hence, SNGM adopt larger batch size than MSGD, especially when I. is large.
5

---

Under review as a conference paper at ICLR 2021
4.2 RELAXED SMOOTH OBJECTIVE FUNCTION
Recently, the authors in Zhang et al. 2020) observe the relaxed smooth property in deep neural networks. According Definition 2 the relaxed smooth property is more general than L-smooth property. For a relaxed smooth objective function, we have the following convergence result of SNGM:
Theorem Let F(w) be a ALmotth function (L 2 0, 0). The sequence {we} produced by Algorithm ! with the learning rate lt and batch size B. Then we have
BIVF((W.)l S 2 ((1-9)(4 3) F(w))
4
8LAM +
(10)
1/
VB
where K.
1+8 [1 (1-8y7
and 1 S 1/(8x)).
Proof 2 The proof is similar that of Thhorem 7
See the supplementary.
According to Theorem we obtain the computation complexity SNGM:
Corollary Let F(w) be a (L, A) A)-smooth function (L 2 0, 2 0). The sequence {we} is produced by Algorithm 1 Given any total number of gradient computation 0, let = [C/B], B), B VC and 1j = I/C & 1/(8nA). Then we have
BlW)( < 2(1 - (F)((wo)) F(w")]
8L(1 + B) (1- 3yCC/ + 4o
C1/4 = 0
C1/4
C1/4
Hence, the computation complexity for achieving an e-stationary point is O(1/ct).
According to Corollary SNGM with batch size of B = VC can still guarantee a ((1/e*)
computation complexity a relaxed smooth objective function.
EXPERIMENTS
All experiments are conducted with the platform of PyTorch, on a server with eight NVIDIA Tesla V100 (32G) GPU cards. The datasets for evaluation include CIFAR 10 and ImageNet.
5.1 ON CIFARIO
First, we evaluate SNGM by training ResNet20 and ResNet56 on CIFARIO. CIFARIO contains 50k training samples and 10k test samples. We compare SNGM with MSGD and existing large batch training method LARS You et al.
2017 We implement LARS by using the open source
2016 for training the two models CIFARIO is using code [ The standard strategy He et al. MSGD with a weight decay of 0.0001, a batch size of 128, an initial learning rate of 0.1, and dividing the learning rate the 80th and 120th epochs. We also adopt this strategy for MSGD in this experiment. For SNGM and LARS, we set a large batch size of 4096 and also a weight decay of 0.0001. Following You et al. (0117). we adopt the poly power learning rate strategy and adopt the gradient accumulation Out et al. (018)) with a batch size of 128 for the two large batch training methods. The momentum coefficient is 0.9 for all methods. Different from existing heuristic methods for large batch training, we do not adopt the warm-up strategy for SNGM.
The results are presented in Figure [ As can be seen, SNGM achieves better convergence rate on training loss than LARS. The detailed information about the final convergence results is presented in Table We can observe that MSGD with a batch size of 4096 leads to a significant drop of test accuracy. SNGM with batch size of 4096 achieves almost the same test accuracy as MSGD with a batch size of 128. But the other large batch training method LARS achieves worse test accuracy than MSGD with a batch size of 128. These results successfully verify the effectiveness of SNGM.

---

Under review as a conference paper at ICLR 2021
3
MSGD, B=128
MSGD, B=128
LARS, B400
LARS, B B409
training loss
SNGM, B-4096
training loss
SNGM, B 4-09
2
50
100
150
50
100
150
#grad/n
#grad/n
(a) ResNet20
(b) ResNe156
100
100
80
test test accuracy
test accuracy
60
60
40
40
MSGD, B=128 LARS, B=4096
MSGD, B=128
20
LARS, B-4096
SNGM, B --009
SNGM, B 4409
20
0
50
100
150
50
100
150
#grad/n
#grad/n
(c) ResNet20
(d) ResNet56
Figure 2: Learning curves on 10.
Table 2: Experimental results CIFARIO. In LARS with warm-up, we adopt the gradual warm-up
strategy and a power of 2, which is the same setting as that in You et al. (2017). In the warm- up stage (5 epochs), the learning rate increases from 0.1 to the target (2.4 in ResNet20 and 2.8 in ResNet56) gradually.
warm-up
initial learning rate
power
batch size
test accuracy
MSGD
0.1
128
91.63%
MSGD
4096
89.25%
LARS
No
0.8
1.1
4096
90.66% %
ResNet20
LARS
Yes
2.4
4096
90.80%
SNGM
No
1.6
1.1
4096
91.42%
MSGD
0.1
128
93.11% %
MSGD
0.3
4096
88.55%
LARS
No
0.64
1.1
4096
92.46%
ResNet56
LARS
Yes
2.8
4096
92.98%
SNGM
No
1.3
1.1
4096
93.12%
5.2
ON IMAGENET
We also compare SNGM with MSGD by training ResNet18 and ResNer50 on ImageNet. The stan- dard strategy He et al. (016) for training the two models on ImageNet is using MSGD with a weight decay of 0.0001, batch size of 256, an initial learning rate of 0. and dividing the learning rate at the 30th and 60th epochs. We also adopt this strategy for MSGD in this experiment. For SNGM, we set larger batch size of 8192 and weight decay of 0.0001. We still adopt the poly power learning rate and the gradient accumulation with a batch size of 128 for SNGM. We do not adopt the warm- up strategy for SNGM either. The momentum coefficient is 0.9 in the methods. The results

---

Under review as a conference paper at ICLR 2021
presented in Figure and Table 3
As be seen, SNGM with larger batch size achieves almost the same test accuracy as MSGD with a small batch size.
80
80
accuracy
60
test accuracy
60
40
40
20
20
MSGD, B
MSGD, B=256
SNGM, B-1992
SNGM, B=8192
0
20
40
60
80
100
0
20
40
60
80
100
#grad/n
#grad/n
(a) ResNet18
(b) ResNe150
Figure 3: Learning curves on ImageNet.
Table Experimental results on ImageNet.
initial learning rate
power
batch size
test accuracy
MSGD
0.1
256
69.71%
ResNet18
SNGM
0.8
2
8192
69.65%
MSGD
0.1
256
75.70%
ResNet50
SNGM
0.8
2
8192
75.42%
CONCLUSION
In this paper, we propose novel method called stochastic normalized gradient descent with mo- mentum (SNGM), for large batch training. We theoretically prove that compared to MSGD which one of the most widely used variants of SGD, SNGM can adopt larger batch size converge to the e-stationary point with the same computation complexity. Empirical results on deep learning also show that SNGM can achieve the state-of-the- accuracy with large batch size.
REFERENCES
Boris Ginsburg, Patrice Castonguay, Oleksii Hrinchuk, Oleksii Kuchaiev, Vitaly Lavrukhin, Ryan Leary, Jason Li, Huyen Nguyen, and Jonathan M. Cohen. Stochastic gradient methods with layer- wise adaptive moments for training of deep networks. CoRR, abs/1905.1 1286, 2019.
Priya Goyal, Piotr Dollár, Ross B. Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: training ima- genet in hour. CoRR, abs/ 00111706666777 2017.
Elad Hazan, Kfrr Y. Levy, and Shai Shalev-Shwartz. Beyond convexity: Stochastic quasi-convex optimization. In Advances in Neural Information Processing Systems, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. Proceedings of Conference on Computer Vision and Pattern Recognition, 2016.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generaliza- tion gap in large batch training of neural networks. In Advances in Neural Information Processing Systems, 2017.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large- batch training for deep learning: Generalization gap and sharp minima. In Proceedings of the International Conference Learning Representations, 2017.
8

---

Under review as a conference paper at ICLR 2021
Yann A. LeCun, Léon Bottou, Genevieve B. Orr, and Klaus-Robert Müller. Efficient BackProp, pP- 48. Springer, 2012.
Mu Li, David G. Andersen, Alexander J. Smola, and Kai Yu. Communication efficient distributed machine learning with the parameter server. 2014a.
Mu Li, Tong Zhang, Yuqiang Chen, and Alexander J. Smola. Efficient mini-batch training for stochastic optimization. In Proceedings of the ACM Conference on Knowledge Discovery and Data Mining. 2014b.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent. In Advances Neural Information Processing Systems, 2017.
Tao Lin, Sebastian U. Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini bini-batches, use local SGD. In Proceedings of the International Conference on Learning Representations, 2020.
Yurii E. Nesterov. Introductory Lectures on Convex Optimization A Basic Course, volume 87 of Applied Optimization. Springer, 2004.
Myle Ott, Sergey Edunov, David Grangier, and Michael Auli. Scaling neural machine translation. In Proceedings of the Conference on Machine Translation, 2018.
Boris Polyak. Some methods of speeding up the convergence of iteration methods. Ussr Computa- tional Mathematics and Mathematical Physics, 4:1-17, 12 1964.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathemat- ical Statistics, 2203):400-47,, 1951.
Ashia C. Wilson, Lester Mackey, and Andre Wibisono. Accelerating rescaled gradient descent: Fast optimization of smooth functions. In Advances in Neural Information Processing Systems, 2019.
Yang You, Igor Gitman, and Boris Ginsburg. Scaling SGD batch size 32k for imagenet training.
CoRR, abs/1708.03000 708.03888, 2017
Yang You, Jing Li, Sashank J. Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training BERT in 76 minutes. In Proceedings of the International Conference Learning Representations, 2020.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis communication efficient mo- mentum SGD for distributed non-convex optimization. In Proceedings of the 36th International Conference on Machine Learning, 2019a
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019b.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In Proceedings of the International Conference Learning Representations, 2020.

---

Under review as a conference paper at ICLR 2021
A
APPENDIX
A.1 PROOF OF LEMMA 1
The proof follows Zhang et al. (2020). We put it here for completeness. For any u, w, let r(z)
(u w) + w, P 2 = Vo(r x]]] x E [0, 1]. Then we have
p(x) - (x) = S. Ha(r(w))r + Vor())))
-1 l Ho(r(v)) - -
< u u|u-wl/ If [1066
wll
sa (L (L+
=La + [Vo(w)] + Aa J. ply)dy.
According to Gronwall's Inequality, obtain
p(a)= S (La + Vdl( (l))e
A.2 PROOF OF LEMMA 2
According to (7). we have
|uta || <3|[u.]]
<38
| || + B
<
|ool + f8 + gt-1 +... + 1
1
- 1- 3
A.3 PROOF OF THEOREM 1
Let 2, W. + I-3 (w: - w,-1), then we have We+1 = We - 1)
Er
+ +.3w,,
w.-1) and
[:ll
B
Z
W W++1
W
1 3
1
1
g:
=2t
1 B
gg
Using the smooth property, we obtain
F(Z++1) SF(z;)
1- 3 (Z(z))
7
T
g:
Lnj
Ig
2(1 13)2
=F(ze)
17
|ggll +
Ln²
1- 3
2(1 8y2
17
((v))))) - VF (F(w)))²
T g:
+ (VF(w:) )z))² T gr
1- B
|g:|]
lg
<F(()) - |B:ll +
17
Ln
+
1- [L|2z well + /F(w))) -g (11)
2(1 3)2
Since W Wt = =B(w: wi-1) - -/g/// /l we obtain
|| well s B wi-1ll
+ n
S 1 1-3 3
71
10

---

Under review as a conference paper at ICLR 2021
Hence, |/we- Wi-1ll 7 B) and 1 well
B4
1-3 W
w _ (1 - -)2
(12)
Combining the above equations, obtain (1 - (z,) - F(z(+1)]
Ln
LBn
+
(1 B)3 + |VP((.:) -gell-
"
2(1
3)
Since [VF(w;)] [V:(w; Bell + -lgglll. we obtain
[VF(w))] (1 (1- ())F(z)) (1=))) F(z(+1))
Ln
+ LBn
(1 - 3)² 2/[V/((w,) - -gell-
"
2(1 3)
Using the fact that E VF(w:) - gell s 2o/BB and summing up the above inequality from to T 1, we obtain
2(1 - VF(w))l
(BFF)) - F(w")]
20
Lin +
T
r/[
VB
A.4 PROOF OF THEOREM 2
Let 2, = W. + 1-8 (W:- W Wi-1), then we have W4+1 = W. -1 8r
+ B(w,
w.-1) and
1
8
Z1+1
W1+1
Wt
3
g
B
W/
1
+
(w:
w
W
8
gg
1 B
17
g1
W1
W
3
3
lgr
1)
gr
3
|grl
Using the Taylor theorem, there exists & such that
F(z++1) {F(2.)
"7
VF(2:)
g:
1- B
Ig: |l
2(1 -3)
(E) 2(1
=F(z,)
lleell +
18)2
[V.)) VF(w,))
gr
+ (VF(w,, - -g.) gt
(13)
Iglll
Let vi(w) = (VF(w)- - VF((w)))
[ Using the Taylor theorem, there exists Ce such that
(2.)) -11 Ve) w:)l= = [V+(G)(+ -w:)l
H well.
(14)
Combining 13) and 14), we obtain
(1 (1- ()] F(2e+1) [Hr(E))]
|g: ||
"
2(1 3)
+ ([) - w.ll +VF( g: ()..
(15)
Since W W: = 3(w; - w;-1) - ng: /|gr|/. we obtain
|| will S B wi-ll + n S 1 1 3
"
11

---

Under review as a conference paper at ICLR 2021
Hence, ||we- Wi-1ll m B) and
13 1 llw -w- 5 (1 - -)2
12 - well
(16)
Combining 115 and 16).
we obtain
1 -3)(F(())) F((e+1))
+ ||Hr(E))l
2(1 - 8) + ||
||g ||
(1 - B)2
+ (VF((w)) 8:1l-
Since [VV - [V::)) gell + ||g:ll. we obtain
VVF(w))] < (L)))) F(2+1))
17 H (
(1 - 1-)33 p()
.nn
" Fl Ball.
2(1 B)
Next, we bound the two Hessian matrices. For convenience, we denote 1+88 (1-8)7
Since ||z:
wall S Bn/(1 3)2 and
||211 - well S 11
zell + 1ize - w.ll
1
3
5:1(
+ (1 3)2
3
SKT)
1
$ X
we obtain
|+)(()) < L + (L + + V
[ |I
L (L+ 1 wl)).
Then we obtain
[VF((;))] s
(1 -1--300 (3) F(Z(+1]
11
+ (1 832
3n
g II+ (L+ (ww)())
17
2(1 - 3)
+ (2(,))((..) - 8ell
(1 (2)))()) F(Zeti)
+ +4Kanj T. + F/IVF(w::II)
+ 2 VF(w.) - grll.
Since 4Akm S 1/2, we obtain
[VF((::)] - 2(1 (zz) - F(Z++1) 8Lai + +4|[F/(WWW)) grll-
1) Summing up the above inequality from t = to T 1, we obtain
2(1 ()(F(wo) F(w*)] } Σ Bl/VF(W))l <
4g
+ 8LAn +
n/T
/B
where 1) S SAx and we use the fact that VF((,, gell S <OVBB.
A.5 PROOF OF COROLLARY
Let x 2(1 3)([(w))) F(w*)],
"] y
Ln. 20. Then have
xB + yn
IyyB
ryB = 2v2
ryz?
2
22 C VB 2/2
Cy
VB
C
C
The equal sign works if and only if /Br/Cy, B /C22/ (C22/((xyy. Then we obtain
8L(1+ + F) - F(w )|o2 (1-B)C
Bl|VF(w))l < 2/2
12

---

Under review as a conference paper at ICLR 2021
A.6 PROOF OF COROLLARY 2
By plugging T = [C. B = v2 and v) v1/C into 9 we obtain the result.
A.7 PROOF OF COROLLARY
By plugging T [C/ B VC and r) = v//CC into 10 we obtain the result.
13


Reviews:
[{"review_id": "w6gZIi_lV8", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "###################################################################\n\nSummary:\n\nThis paper proposes a new stochastic normalized gradient descent method with momentum (SNGM) for large batch training. They prove that unlike mometum SGD (MSGD), SNGM can adopt larger batch size to converge to the epsilon-stationary point with the same computation complexity (total number of gradient computation). The paper shows that SNGM with large batches is comparable to MSGD with small batches for training ResNet on CIFAR10 and ImageNet. The paper also shows that SNGM outperforms LARS on CIFAR10.\n\n###################################################################\n\nReason for the Score:\n\nOverall, I vote for rejecting. I have two main major concerns. First, the theoretical contributions of the paper are only small extensions from existing works and not significant. Second, very limited number of experiments are performed in the paper. The authors also do not compare the proposed method with popular works in large batch training that yield better results than those reported in the paper.\n\n###################################################################\n\nStrong points:\n\n1. Analyzing the relationship between smoothness constant and batch size can potentially help provide a better understanding of large batch training algorithms.\n\n2. The paper is well-written.\n\n###################################################################\n\nWeak points:\n\n1. The analysis of the relationship between smoothness constant and batch size is a trivial extension from the results in Theorem 1 and Corollary 1 of Yu et al. (2019a).\n\n2. The authors claim that existing works such as LARS lack theoretical evidence to explain why they can adopt a large batch size. However, theoretical explanations for normalized SGD with momentum like LARS are provided in Cutkosky et al. (2020).\n\n3. The paper does not compare the proposed SNGM method with popular works in large batch training. In particular, in ImageNet experiments, the authors only compare the SNGM method with the baseline MSGD trained with small batches. In fact, when training ResNet50 on ImageNet with the batch size of 8192, LAMB proposed by You et al. (2020) reported the test accuracy of 76.66%, which is much better than the reported test accuracy of 75.42% attained by SNGM. Another existing work that reported a better result on the same task is Smith et al. (2018).\n\n4. The main claim of the paper is that SNGM can adopt large batch size. However, only experiments with a batch size of 4096 on CIFAR and a batch size of  8192 on ImageNet are provided. More experiments with different batch sizes, especially larger ones, are needed.  \n\n###################################################################\n\nAdditional Concerns and Questions for the Authors:\n\n1. LARS and LAMB also normalize the update in SGD. After reading the paper, I do not see the clear theoretical and practical advantages of SNGM over these methods.\n\n2. The paper only provides experiments with ResNets and image datasets. Additional experiments on different models and tasks, such as training BERT for language modeling, are needed to validate the advantage of SNGM. \t\n\n###################################################################\n\nMinor Comments that did not Impact the Score:\n\n1. It would be good if the authors can compare the runtime of SNGM with other methods.\n\n2. If possible, error bars should be provided for the experimental results.\n\t\t\t\n3. Related works should be discussed more.\t\t\t\n\t\t\t\n###################################################################\n\nReferences:\n\nHao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization. In Proceedings of the 36th International Conference on Machine Learning, 2019a. \n\nAshok Cutkosky and Harsh Mehta. Momentum improves normalized SGD. International Conference on Machine Learning, 2020.\t\t\n\nYang You, Jing Li, Sashank J. Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training BERT in 76 minutes. In Proceedings of the International Conference on Learning Representations, 2020. \n\t\t\t\t\nSmith, S., jan Kindermans, P., Ying, C., and Le, Q. V. Don’t decay the learning rate, increase the batch size. In International Conference on Learning Representations (ICLR), 2018.\t\n\n###################################################################\n\nPost Discussion Score:\n\nThe authors did not submit their rebuttal. After reading the comments from other reviewers, I decided to keep my original score for this paper.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ja7avO-MVbx", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "In this paper, the authors proposed an optimizer by the name of SNGM (stochastic normalized gradient descent with momentum). We can get the main idea by just reading its name. The authors claimed the main contributions are on the theoretical side. Overall, I think this paper is neat and clear. The figures and tables are easy to read and understand. The main idea is also highlighted in a proper way. I like the style of this paper.\n\nHere are some of my concerns:\n\nIn terms of algorithm design, the idea of this paper is pretty simple: Momentum SGD plus normalized gradients. Similar ideas have been tried in many previous papers (e.g. [1]).\n\nThe authors claimed two theoretical contributions: \n\n(1) SNGM is able to adopt a larger batch size to converge to the epsilon-stationary point with the same number of floating-point operations as SGD. \n\n(2) They can prove that SNGM converges to an epsilon-stationary point with a computation complexity of O(1/epsilon^4).\n\nI quickly went over the proof and did not find obvious flaws. However, because SNGM has a relatively simple algorithm structure, the theoretical study of this paper seems to be not a lot of hardcore work. The theoretical contribution is above the average but not very impressive.\n\nThe experimental results are not strong enough to convince potential users.\n\nThe authors used [3] as the LARS implementation. Please see also [4] to make sure the implementation is correct. The researchers in [4] [5] [6] reported a much higher accuracy than this paper by LARS optimizer in ImageNet/ResNet-50 training. If the authors can confirm the implementation is correct, then they need to make sure the hyper-parameters of all optimizers are properly tuned. Only in this way, we can have a fair comparison.\n\nThe authors used a batch size of 8192 in ImageNet training experiments.\nAccording to previous papers like [2] [4] [5] [6], a batch size of 8192 is probably too small to be considered as a “large batch size”. It can be easier to evaluate the contribution of this paper if the authors can report the results using a batch size over 32K.\nIf the authors have out-of-memory issues with limited hardware resources, please check [7].\n\nIt will be better if the authors can provide a copy of the implementation with detailed hyper-parameters.\n\n[1] https://arxiv.org/pdf/1707.04822v1.pdf\n\n[2] https://openreview.net/pdf?id=Syx4wnEtvH\n\n[3] https://github.com/noahgolmant/pytorch-lars \n\n[4] https://arxiv.org/pdf/1909.09756.pdf\n\n[5] https://arxiv.org/pdf/1807.11205.pdf\n\n[6] https://arxiv.org/pdf/1811.06992.pdf\n\n[7] https://discuss.pytorch.org/t/how-to-implement-accumulated-gradient/3822", "extra_scores": {}, "extra_text": {}}, {"review_id": "9HsLbWGDpwN", "reviewer": "AnonReviewer4", "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": "Summary:\nLarge batch training has been observed to not only significantly improve the training speed but also lead to a worse generalization performance. This paper considers how to improve the performance of MSGD in large batch training. They propose the so called normalized MSGD where instead of the gradient, the algorithm uses the normalized gradient to update the momentum. They also provide theoretical justification of this change by considering smooth and relaxed smooth function. O(1/\\epsilon^4)  convergence rate is established.\n#######################\nPros:\n\n1. Though the idea of using normalized gradient to improve the algorithm’s  performance is not novel, there still lacks theoretical analysis. The paper successfully fills this gap.\n\n2. The paper overall is well written and well structured. The authors give a clear path from the background to algorithm and then convergence analysis. I have no difficult in reading and understanding all the results.\n\n#######################\n\nMajor Comments:\n\n1. The algorithm considered in this paper is a simple combination of MSGD and gradient normalization. As such, none of the components are new. The theoretical results are not very surprising, and the techniques used are not new. I checked the proof, the only difference compared with MSGD’s proof is to bound the difference between gradient and normalized gradient which is not difficult given the smoothness condition (at least in my opinion). I may miss something and if I can be convinced on the difficulty of the analysis, I would like to raise the score.\n\n2. The theoretical result only considers converging to a first order stationary point. However, in nonconvex setting, that is far away from claiming the algorithm can have better performance. I  understand the difficulty to prove second-order convergence, but at least some discussion should be added.\n\n3. I suggest the authors to add more intuitive explanation to why this normalized MSGD works. \n\n4. Numerically, the paper only compared with LARS which is a 2017 algorithm. I strongly suggest to add more experiments and compare SNGD with more benchmarks.\n\n\nOverall, I vote for reject since I don’t find enough novel results here. I am willing to raise my score if the authors can convince me their contribution", "extra_scores": {}, "extra_text": {}}, {"review_id": "0pHl9kr9TI", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 proposed a simple stochastic normalized gradient methods with momentum (SNGM) for non-convex optimization, the authors argued the main advantage of the method is it allows large-batch training. Theoretical convergence guarantees and  empirical results for neural network training are provided.\n\nMy main concerns are in the theoretical results: in the paper the authors argues the following: standard MSGD has convergence of O(/1/sqrt(C) + B^2/C), while SNGM, with B=sqrt(C), has convergence rate of O(1/C^(1/4)).  It seems to me it is unfair comparison as one has O(1/C^(1/2)) rate and the other has O(1/C^(1/4)) rate.\n\nIf we choose B=C^(1/4) in MSGD, then MSGD has convergence rate of O(1/C^(1/2)), which is much faster than the SNGM rate of O(1/C^(1/4)) ? Only if we fix the overall rate of O(1/C^(1/4)), then for MSGD the largest mini-batch size is B=C^(3/8), which is smaller than the SNGM minibatch size. Can SNGM obtain O(1/C^(1/2)) rate ? What is is mini--batch size limit under the fast O(1/C^(1/2)) rate ?\n\nPlease correct me if I am wrong.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agree that the contributions of this paper are not significant, and the paper does not compare well with many of the existing works. Authors did not respond.
Decision: Reject