Robustness to Unbounded Smoothness of Generalized SignSGD
Authors: Michael Crawshaw
Mingrui Liu
Francesco Orabona
Wei Zhang
Zhenxun Zhuang
Venue: NeurIPS 2022 Accept (2022)
Keywords: stochastic
optimization
noncovex
adam
transformer
clipping
signsgd
momentum
unbounded smoothness

Abstract: Traditional analyses in non-convex optimization typically rely on the smoothness assumption, namely requiring the gradients to be Lipschitz. However, recent evidence shows that this smoothness condition does not capture the properties of some deep learning objective functions, including the ones involving Recurrent Neural Networks and LSTMs. Instead, they satisfy a much more relaxed condition, with potentially unbounded smoothness. Under this relaxed assumption, it has been theoretically and empirically shown that the gradient-clipped SGD has an advantage over the vanilla one. In this paper, we show that clipping is not indispensable for Adam-type algorithms in tackling such scenarios: we theoretically prove that a generalized SignSGD algorithm can obtain similar convergence rates as SGD with clipping but does not need explicit clipping at all. This family of algorithms on one end recovers SignSGD and on the other end closely resembles the popular Adam algorithm. Our analysis underlines the critical role that momentum plays in analyzing SignSGD-type and Adam-type algorithms: it not only reduces the effects of noise, thus removing the need for large mini-batch in previous analyses of SignSGD-type algorithms, but it also substantially reduces the effects of unbounded smoothness and gradient norms. To the best of our knowledge, this work is the first one showing the benefit of Adam-type algorithms compared with non-adaptive gradient algorithms such as gradient descent in the unbounded smoothness setting. We also compare these algorithms with popular optimizers on a set of deep learning tasks, observing that we can match the performance of Adam while beating others.

Robustness to Unbounded Smoothness of Generalized SignSGD
Michael Crawshaw"
Mingrui Liu"
Francesco Orabona" Boston University
George Mason University mcrawsha@gmu edu
George Mason University
mingrui gmu.. edu
francesco@orabonte com Zhenxun Zhuang" Meta Platforms, Inc. 1 dbboymms@gmmmi......m..m com
Wei Zhang"
IBM T. J. Watson Research Center weizêus ibm. com
Abstract
Traditional analyses in non-convex optimization typically rely on the smoothness assumption, namely requiring the gradients to be Lipschitz. However, recent evidence shows that this smoothness condition does not capture the properties of some deep learning objective functions, including the ones involving Recurrent Neural Networks and LSTMs. Instead, they satisfy a much more relaxed condition, with potentially unbounded smoothness. Under this relaxed assumption, it has been theoretically and empirically shown that the gradient-clipedd SGD has an advantage over the vanilla one. In this paper, we show that clipping is not indispensable for Adam-type algorithms in tackling such scenarios: we theoretically prove that a generalized SignSGD algorithm can obtain similar convergence rates as SGD with clipping but does not need explicit clipping at all. This family of algorithms on end recovers SignSGD and the other end closely resembles the popular Adam algorithm. Our analysis underlines the critical role that momentum plays in analyzing SignSGD-type and Adam-type algorithms: it not only reduces the effects of noise, thus removing the need for large mini-batch in previous analyses SignSGD-type algorithms, but it also substantially reduces the effects of unbounded smoothness and gradient norms. To the best of our knowledge, this work is the first one showing the benefit of Adam-type algorithms compared with non-adaptive gradient algorithms such as gradient descent in the unbounded smoothness setting. We also compare these algorithms with popular optimizers on a set of deep learning tasks, observing that we can match the performance of Adam while beating others.
Introduction
Recent years have witnessed a surge in non-convex machine learning models, with a focus on deep neural networks [27]. DNNs have achieved tremendous progress in a variety of tasks, including computer vision [26, 18, 23], natural language processing [11, [0], and lot more. Despite their huge empirical success, the theoretical analyses non-convex optimization [21] prove be fundamentally more challenging than the established convex optimization theory [4]. Among the numerous literature, many of them assume smoothness of the objective function, namely requiring the gradients to be Lipschitz. Under this scenario, past works have succeeded in proving the convergence rates for number of algorithms, e.g., Stochastic Gradient Descent [14], AdaGrad [52, 30], and STORM [9, 7].
Nevertheless, it was recently observed that the smoothness assumption does not capture the training of LSTMS [20]: the Hessian can grow with the size of the gradients [56]. Inspired by this, Zhang
Authors in alphabetical order.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Serador
4.0
Adam Clpppng
12500
32000
10200
0.0
103 Spacc
130
125
200
2520
7500
undertnor
Val No seraeeettt
Adam No Clippng Adam Closmn
(a) Wikitext-2
(b) WMT 16 de-en
Figure 1: Local gradient Lipschitz constant vs. Gradient norm on training (a) 2-layer Trans- former Encoder on Wikitext-2 (b) 6-layer Transformer on WMT' 16 Multimodal Machine Translation de-en dataset. The colorbar indicates #lterations in training. Details in Section 5.2.
25
Epoch
Figure 2: Training GPT-2 on Wikitext- 103 using Adam with without gradient clipping.
2.5 led
Perstoon
Berstoon
Ted
Iteraion
2,5
1.0
2.0
10000
50000
10000
30000
amcolmpee
20020
20200
0.6
20000
20000
3.4
0.5
10000
0.5
10000
500 Abroiute gracierz
10
20
105
500
1000
4000 gradentt Valle
Abrov Life gradiect Wiice
#boolute gradler
(a) Encoder First Layer
(b) Encoder Last Layer
(c) Decoder Second Layer
(d) Decoder Last Layer
Figure 3: Local gradient Lipschitz constant vs. absolute gradient value on training a Transformer on
WMT 16 Multimodal Translation de-en dataset. Each figure represents randomly picked coordinate in corresponding layers. The colorbar indicates #Iterations during training. Details in Section 5.2.
al. [56] proposed a relaxed smoothness assumption, named (Lo, L,) smoothness:
[V=(())) S Lo + L, [VF()]]
They also showed that the well-known gradient clipping technique ensure Stochastic Gradient Descent's (SGD) convergence in such scenarios. Later, their results were improved to show that SGD with clipping can be made unaffected by the I, in (1) and is able to recover the optimal convergence rate of SGD under the original smoothness setting [55, 22].
Nevertheless, the (Lo. L1) condition has not yet been empirically verified beyond LSTMs. Therefore, our first contribution lies in studying the applicability and generalization of the (Lo, L1) condition. In particular, we have empirically verified that the popular Transformer [50] model also seems to satisfy this assumption, see Figure 1. Yet, we noticed that different coordinates, especially when they are in different layers of the model, exhibit very distinct Lo and L1 values as shown in Figure 3. Hence, we propose to refine the (Lo, L1) assumption in (I) to a coordinate-wise version (Assumption 2) and consider this to better capture the loss surface when training deep neural networks like Transformers.
Given that assume (a generalization) of the (Lo, L1) assumption. it would be natural clipping procedure. However, we found out that the use of clipping on Adam [25), while carried out in common practice (e.g., 53), has effect on the training and testing performance on optimizing a large transformer model as shown in Figure 2. In retrospect, this might not be surprising: is known that Adam has implicit clipping behavior due to the normalization by the estimated second moment of the gradients. Indeed, Adam can be interpreted as a variant of SignSGD [2].
some
Inspired by this, our second contribution is to propose and analyze a generalized SignSGD algorithm under the relaxed smoothness assumption. It is parameterized in such a way that on one end recovers SignSGD while on the other end closely resembles Adam. Apart from the convergence rates, we also located the critical role the momentum plays analyzing Adam-type algorithms: not only reduces the effects of noise but also gives an exponential decaying effect on the unbounded gradient norms and smoothness. This can partly explain the phenomenon that clipping does not help Adam. Moreover, show gap between the upper bound of SignSGD and the lower bound of SGD

---

in the relaxed smoothness setting. This can be considered first step in explaining the superior performance of Adam in practical deep learning problems.
The structure of this paper is as follows. Section 2 discusses related works and how our paper builds upon and distinguishes from them. The settings and assumptions are carried out in Section We will introduce formally the generalized SignSGD algorithm and its analysis in Section 4, with a detailed discussion on the bounds and the role of momentum. The experimental results are shown in Section 5, comparing our algorithm with some popular competitors in deep learning tasks. Finally, we draw some conclusions and discuss the limitations of our work in Section 6.
Notations We will use [d] to denote the sequence [1,2,..... d] and use bold letters to represent vectors, e.g., u E TRd. The j-th coordinate of a vector u is uj. Throughout this paper, we study the Euclidean space IRd with the inner product ))- Bfu] means the expectation with respect to the underlying probability distribution of a random variable u, and E,, [u] is the conditional expectation of u conditioned on the past of time L. The gradient of F at æ is denoted by VF(x). We use I[.) to
denote the indicator function, p to denote the p-norm: ||0/|pp == (2) 1j=1 luylP) and |/o]oo the
maximum norm: ||// == max[[ull, (lull....,,
We also denote by Ek=, Ik = 0 when i > j.
2 Related Works
Adaptive Gradient Methods Adaptive gradient methods [34, 12, 25, 19, 44] are popular optimizers
for training deep neural networks. The traditional analysis of adaptive gradient methods is providing regret bounds under the online convex optimization framework [12, 25, 44]. Recently, there are some analysis of adaptive gradient methods for nonconvex smooth functions [6. 5, 54, 10, 61]. Zou et al. [60] introduces an intriguing connection between Adam [25] and SignGD [3] when training a two-layer neural network in the deterministic setting, where SignGD is an algorithm following the negative gradient sign direction to perform the update. However, these works cannot be directly extended to nonconvex functions with unbounded smoothness in the stochastic setting. To the best of our knowledge, this work is the first one establishing guarantees for coordinate- wise type optimizers like generalized SignSGD as well as Adam-type updates under a relaxed smoothness condition.
Gradient Clipping The algorithm and analysis of gradient clipping can be traced back to [1, 48, 13] under the assumption that the function is convex and rapidly growing. Hazan et al. [17] considered gradient clipping in quasi-convex optimization. Mai and Johansson [32] showed the stability and convergence of stochastic gradient clipping algorithms for convex problems without the smoothness condition. Gradient clipping
standard technique in training deep neural networks [39, 40] such as RNNs and LSTMs. The theoretical analysis of gradient clipping for nonconvex models is pioneered by [56]. in which the authors analyzed the convergence of gradient clipping under the relaxed smoothness assumption rather than the standard smoothness assumption. Zhang et al. [55] further improved the convergence rate bound under the same assumption as in [56). Gradient clipping is also used when there is heavy tail noise in the stochastic gradient to establish high probability convergence rates [8, 15, 57J. Cutkosky and Mehta [7] proved that normalized momentum improves normalized SGD under second-order smoothness condition. A close algorithm is the one in [22] which employs gradient normalization, momentum, and no gradient clipping to tackle the (Lo, Li) condition (1) and control noise. Yet, their algorithm normalizes each coordinate with the same scale unlike popular optimizers such as Adam [25]. Moreover, we observe empirically that normalized SGD with momentum performs worse than Adam. Motivated by this, we propose coordinate- wise optimization algorithm which requires new analysis tools compared with [22].
Employ m to compute v; in Adam Designed to combine the advantages of Adagrad [12] and RMSProp [49], the update of Adam [25] employs the ratio between the exponential moving average of the stochastic gradient (m); and the exponential moving average of the squared stochastic gradient (v,). Many variants of Adam have been proposed ever since. Among them, one idea is to use m to compute instead of 9.. The intuition is that m, represents better update direction than 9: and can thus better capture the the convergence of Adam in federated learning setting; yet, they only consider the smooth setting and require large e to obtain convergence in contrast to the original Adam. Later, Wang et al. [51] explored this idea in more detail, but their analyses are still restricted to the smooth setting. There also exist other variants of the Adam update that attempt to obtain a more stable update changing the order of the normalization and momentum operations [sce, c.g., 59].
-oment information. Reddi et al. [43] adopted this change to prove
3

---

3 Settings and Preliminaries
In this paper, we foeus on the following stochastic optimization problem:
min F F()) == [f {)],
#ER
where is random variable representing a randomly selected data sample or random noise following an unknown distribution D. We will use the following assumptions.
Assumption 1. F : IR + R is differentiable and bounded from below with infinum F* Assumption say that differentiable function F(x) (Lo, --mooothh coordinate-wisel if for any 2, y E Rdd for which ||
yll2
S
we have for any j E [d] that
||Z1||
OF 0r.
OF
Loj
OF 0x. (a:)
y
(x)
+ Li
11 2012
(2)
Jzj
vd
We will denote Lo = Lo, Lo, Lo,al' and L1 == [L1,1 I1.,..... It,d]"
The original (Lo. L1) smoothness assumption (1) in [56] was proposed as generalization of the more common smoothness assumption, which says that the gradient should be Lipschitz. Indeed, when Iı.j are zero, we recover the smoothness assumption. In contrast, when Lı.j are non-zero, the smoothness of the function is potentially unbounded. Yet, [56] works with norms and applies to the global scale, while ours is more fine-graines and applies to each coordinate separately. One motivation for this assumption comes from |Remark 2.3, 55] where they noted that (1) can be relaxed to an assumption gradient differences: there exists Ko, Ki > 0 such that
VFF()) V (f))ll & (Ko + [= y122. Vx, y E Rd
y112 S 1/K1 (3) ||00
Indeed, our Assumption implies (3) when To.; Lo and Iı = L, for all [d]. up to constants
(See Lemma 3 in the Appendix). Note that the va factor in ours is exactly for easy comparison with (3). The reason we turn to the current coordinate-wise version is that we observed a vast variance across different layers in training Transformer models: (1) is still true globally (Figure 1), but each layer or even each coordinate satisfies has very different (Lo, L1) pair (Figure 3). The smoothness assumption has been generalized in orthogonal directions in other work [45, 3, 24].
One merit of Assumption 2 that it gives the following descent lemma. Lemma 1. Let F be (Lo, L1)-smooth coordinate-wisely. Then, for any x, y E R& for which Lills we have
||0 2l12 -
Looi + Lng
0F (a:) (a)) b1y x 0112|15 xzyl
F(y) S F(x) (VF()),y x))
Σ j=1
0x,
Our last assumption is common in the literature studying the (Lo, L1) smooth condition [56, 55]. Assumption 3. For each j E [d]. there exists oj > O such that for all x E IRd and ~ D, the noise aF (x)) S o with probability 1. We will denote or = [01, 02, o2,....0all TalT. satisfies [Vf(x, ax;
4 A Generalized SignSGD Algorithm
Algorithm 1 Generalized SignSGD (All operations vectors element-wise.)
1: Inputs: 31, B1, 82, 17
2: my = 0, Un =
3: for p=rt=1, 1,.....
do
4: Compute an unbiased estimate ff( FF(,;) denoted as g,
5: m: - (1 B1)g,
6: V: = 320,~1 + +1 32 m²
7:
F1+1 82 1) /0:
8: end for

---

In this section, we present in Algorithm generalized SignSGD algorithm. This algorithm encompasses a variety of optimization algorithms.
At first sight, it seems very similar to Adam. Indeed, if we employ g in computing v, instead of m then it exactly Adam, except for the bias correction terms. We would like to clarify that the idea of this change has been explored before, as detailed in Section 2. In this paper, the motivation for adopting this idea comes from the known effect of momentum on reducing the influence of noises [7]. Indeed, in our analysis the difference between and V (F:;)) is much more controllable than between 9t and (xr)) Thus, we consider employing m, in computing v, better choice.
On the other end, the careful reader might observe that Algorithm 1 recovers the SignSGD with Momentum algorithm, also called SIGNUM in [3]. when setting 32 O. Sign-bases algorithms are naturally suited to distributed learning [29] and the idea dated back to at least RPROP [46]. The convergence stationary point (with & norm) under coordinate-wiss smoothness condition has been established for SignSGD with/without the momentum in [3] though they necessitate large mini-batches to control the variance the noise. Yet, we are more interested in their property of the update size being bounded without the need for explicit clipping.
Note that both SignSGD and Adam are good candidates for optimization algorithms whose update must be bounded on functions that satisfy the (Lo, L1) condition. Indeed, SignSGD can be seen as an extreme form of gradient clipping. On the other hand, said in the introduction, Adam does not seem to require gradient clipping at when used to train the large Transformer model in Figure
Hence, we expect our algorithm, a generalization of SignSGD and a close resemblance to Adam, can enjoy the merits of both and be robust to the unbounded smoothness in the (Lo, L1) scenario. In the next section, we will formalize this claim by presenting the theoretical analysis of Algorithm 1.
4.1 Theoretical Convergence Analysis
Theorem 1. Under Assumptions 1, 2, and assume M, := sup {
OF 0u,
(x)
F(x) S F(x1)) is
finite for each j E [d]. let A be any upper bound on F(x1)) -F,, a min
Volliv
||
a-a, J < 1, = 1- diz B.
V Loll VT for 2 max
voa
100dA 1
10000d A 1 L
[1 82)p" Loll
(1 Ppp Loll
Algorithm/ 1 guarantees, Muarattnngaaraatessss with probability at least 1 8. that
Vlogld//b) Loll 1/4 11/1||111
log (1T IA
min (E[T]
[V =0
PVI -211/1
PVT
+0 ||M
|||||
vI
3z
3/1 Lo
IVF
T
exp
1/2
T
Furthermore, for the case when 32 = 0, we have the following refined guarantee:
[VF((,;)) =0 v /og(dTT)) (o/ Lo Illl 1/4
///4||0]] log(dT/8)
Lo A
min tE(T]
T2/4
VT
IVF(xi)l VT
|o Lo
||0|| T
VT
Here, M, denotes the maximum absolute value of the partial derivative of F' for coordinate j among the sub-level set of F(æ1). namely any point æ with F(x) <. F(x1). In other words, we assume of F(x1); yet, we do not make any restriction on gradients
gradients to be bounded in the sub-level outside of this set. We believe this is not strong assumption, for example, when the sub-level set of F Fxx1) is bounded, then by the assumed continuity of gradients it trivially holds. Also, we just require an upper bound and it can even be exponentially large as we have an exponentially decaying coefficient to counteract it: notice how the term
M is multiplied by a term that decays exponentially with T. Better still, when 32 0, we no longer even need this assumption and the algorithm entirely free of the influence of |M To see why this is good, we show refined lower bound of Gradient Descent under the relaxed smoothness scenario below which is originally in [56].
5

---

La max e), and zo E R. Pick any constant learning rate 1i for GD. with the knowledge of the above constants. Then, there exists a I-d (Lo, L smooth function, bounded from below by f (finite), and such that sup(lf : f f(z) S f(za) S M on which the number of iterations T of GD with learning rate 1, to guarantee (f'(() c at least
Theorem 2. Fix eix 0,
00, 1,
M ff 16L0
15e"
2c
In
ML1 Lg
+ 1)
Theorem 2 shows that in the relaxed smoothness setting, GD with any constant step size will suffer from linear term depending on M, On a side note, it is fixed version of the lower bound in [56]: we provide in Appendix an explanation of errors in their lower bound and our corrected proof.
Compared with GD, algorithm only has exponentially decaying dependence L1 We consider this to be substantial merit of our algorithm. Furthermore, when 82 = in which case we recover the SignSGD with Momentum algorithm, we can even show that it completely removes the effects of the unbounded gradient norms. Also notice that in such case we actually no longer need the assumption of My := sup {
(x)
F(z) S F(x1) being finite for each j [d] anymore, and
the || L1 Il term does not appear in the final bound anymore.
We also would like to point out that this bound closely resembles the one achieved by SGD with gradient clipping algorithm [55] except that we consider the coordinate- -wise setting: take the setting
of B2 = for example, we need at most O A max | Lolla
d |'
L
d
L2 11 })
Lolli
||
to get
point x with |VF(())) S e with high probability.
Remark The almost surely bounded assumption 3 can be relaxed to sub-gat sub-gaussian noise, using standard extensions of Freedman inequality [e.g., 16].
Remark 2 When 32 O. can prove average-iterate complexity bound (see Proof of Theorem 1 for 3/2 = 0 in Appendix A.3); yet, we use the min form for consistency between the two cases.
Remark 3 Our bound is incomparable with the one in [55. Theorem 3.2]. Yet, as we said, if (3). In this case, assuming the noise vector and the gradient vector to be dense to be able to compare the l f1-nrrm and the noomm, we recover the same bound of [55, Theorem 3.2] in terms of dependencies on L1, Lg, and T. Instead, in the more general case when Lo.; and Lı, are not uniform vectors, our bound allows finer control of the unbounded smoothness.
To.j Tig and T.1.j I, for all j E [d]. then the function satisfies
Remark Careful readers might be concerned on the relations between a, 31, 82, p. and T when a # 1. We would like to note that, when 32 is fixed, a is inversely proportional to VT. In turn, the definition of p means that as 7 grows, P grows and approaches for 7 decreases when T grows. This means that there must exists a threshold of T above which the two conditions T always hold. In summary, Theorem I conveys the same message as [55] that as long as the expected e is sufficiently small, the complexity no longer has a dependency on L1.
vB2.. Thus, the
conditions
The proof of the theorem is highly technical and it uses recent advancements in the analysis of momentum methods [7], key techniques to deal with the L1) assumption [55], as well as a novel and essential inductive argument to control the norm of past gradients. We want to stress that the difficulty mainly comes from analyzing Adam-type updates when 82 > O, while for the other case of
f2 = 0 the proof is significantly simpler. The full proof is in the Appendix, but here we present proof sketch that underlines the main steps. First, we list some key lemmas we used but move their proof's to the appendix due to space constraints.
Lemma 5.
With notations Algorithm f. TS== q L. || we have ||x,-, 2zll2 S [| low
-I-3
Lemma limits our focus to the most recent F steps on which Assumption and Lemma can apply. Lemma 7. Assume Assumption 3. With the notation of Algorithm 1, let [d] and 31 < 1. Then, with probability at least 38, for any to E [t), we have
to
8 8:- |T. dx, (az))
0F
3
< 3a, max(1, log +
o0 max logx(1) E,. VI - -1377

---

Lemma 7 is the major tool use handle the noise we incur during drawing stochastic gradients. It is derived based on Lemma 12 in [8].
Lemma 10. With the notation of Algorithm 1 and under the assumptions of Theorem 1, if af (x+ S Sw; M2 holds for all T S t and j E [d], and > O, then, with probability at least 1 3tp we have that,
OF
< 5Bj mmal 2 pD
either
(Ix)
or
Øxz
D
Mlg 5v 122
where Bj A nho (I-BA(1-B3) + 88 + 0j) + + B3) and D 2 1 (1--)((--.)
Lemma 10 is similar to Lemma A.2 in [60] which considered the deterministic and smooth setting; in contrast, our proof is much more challenging in that we need to tackle both the noise and the unbounded smoothness. With this lemma, we know that either the true gradient is small that the update of our Algorithm can be lower bounded.
Lemma 12. Under Assumptions 1, 2, and 3, using the lyperparameters in Theorem denoting =11-1 1-118 31 and E = m. F (2t), for all t and j E [d] we have, with probability at least 33,
|e+t1a S (1-a)' ao, + (1 aa)
aF dz;
(m1)
nLos +o (1))))
[-1
OF
( (x:-
doy
TE0
Lemma 12 shows how the use of momentum can help control the noise by choosing 81 wisely. is adapted from the proof of Theorem 2 in [8] but with the added difficulty of unbounded smoothness.
Proof sketch of Theorem I. Observing the formula of setting 8L, we see that when ||o||1 I
/ 31 0. As B2 < B1, Algorithm reduces to SignSGD. In this case, the key
aF (x:) can be controlled as C₁ Et aF (zx) + C2. The summation of true gradients over time can then be Jay
component is Lemma 12 using which we are able to show that Σ ma.j az,
offsetted by choosing y and 31 wisely when we invoke the descent lemma 1. The rest is standard.
Now for the other case in which ||a|| VI we take a different route.
First, notice that Assumption and the Descent Lemma I only hold when two points are not too far away. Thus, we need restrict our attention to the recent updates (Lemma 5), beyond which we would have no control. This means we want the influence of those updates too long ago to not have big effect the current one. To make this happen, one natural idea is to a bounded gradient assumption, then with the use of exponential averaging, their effect would be quickly reduced. Yet, assuming directly that all gradients are bounded would trivialize the (Lo, L1) assumption. Thus,
(x) F(x)= s F( being finite for each j E [d]. Then, we prove that M, will provide upper bound to all the true gradients the algorithm see. We prove it using induction, analyzing separately the case that either the true gradient is already very small and we have reached the proximity of stationary point, the objective function is monotonically non-increasing and the gradient remains bounded.
pose much weaker condition. assuming that Mj =su { OF B2,
Having controlled the past gradients, we prove in Lemma 10 that the update of Algorithm is either very small that can pass having constant lower bound that we can use in the Descent Lemma 1.
Also, considering that this the stochastic setting, noise typically slows down convergence or can even cause the algorithm to diverge if the hyperparameters are not chosen wisely. To handle this, we invoke Freedman's inequality to show that the addition of adjacent stochastic noise almost cancels out each other and the absolute value of the sum remains controlled (Lemma 7).
Yet, we still need another block to handle the difference between the true gradient and the momentum as we are updating in the direction of the momentum instead of the true gradient. Turns our that we
can prove that sign(m.,s) sign
aF Bi.
(#r))
when
dzy (ax) is not small. As before, in the case
aF
ar (#:) is small, we have converged on that coordinate. Combining all these blocks together, we Duy
are able to arrive at the final results.
7

---

0.8
0.90
Our Generalized SignSGD
Adam
0.6
Momentum
0.85
Training Loss
Momentum Normalized SGDClipGrad
Test Accuracy
SCDClipMomentum
0.4
0.80
Our Generalized SignSGO
Adam
SGD Momentum
0.2
0.75
Momentum Normalized
SGDCIipGrad
SCDCliaMomentum
0.70
25
50
75
100
125
150
25
50
75
100
125
150
Epoch
Epoch
Figure 4: Training 20-layer Resnet on CIFARIO. The shading of each curve represents the 95% confidence interval computed across 5 independent runs from different random seeds.
6.5
Our Generalized SIgnSGD
Our Generalized SignSGD
Adam
Adam
Momentum
Momentum
Training Loss
Momentum Normalized
Test Perplexity
SGD Momentum Normalized
SGDCIipGrad
SGDCIipprad
5.0
SGDClipMementumm
80
SGDClipMomentum
4.5
70
4.0
3.5
60
3.0
0
200
400
600
0
200
400
600
Epoch
Epoch
Figure 5: Training an AWD-LSTM to do language modeling (word level) on Penn Treebank. The shading each curve represents the 95% confidence interval over independent runs.
Experiments
We conducted our experiments using PyTorch [41] on Nvidia V100 GPUs. Codes can be found at com/ haateeexxunnzhhanngGGgnnne zed- Si gnSGD.
5.1 Comparison with Other Optimizers
To validate the efficacy of our Algorithm 1, we compare with Adam [25], SGD [47], SGD Momen- tum Normalized [22], SGDClipGrad, and SGDCLlipMmmentu.. The latter two are from Algorithm
1 [55] where SGDClipGrad corresponds to the case when v = and SGDClipMomentum corresponds to when == 1.
grid-search to fine-tune the initial learning rate for all optimizers, as well as the clipping threshold for SGDClipGrad and SGDClipMomentum. and 33 for Adam and our algorithm, to select the giving the best validation performance validation set. We then employ the best performing hyperparameters to train the model over all training data and report the testing performance. The testing is repeated with random seeds 5 times to climinate the influence of stochasticity. For more details, please refer to Section A.4.
Training Unless otherwise specified,
separated
Resnet for Image Classification on CIFAR-10 We employ the 20-layer Residual Network model [18] do image classification on the CIFAR-10 dataset. Images are normalized per channel using the means and standard deviations computed from all training images. We adopt the data augmentation technique following [28] (for training only): pixels are padded on each side of an image and 32 crop is randomly sampled from the padded image its horizontal flip. The mini-batch size is 128 and we train all algorithms for 164 epochs. We do not employ any learning rate decay schedule in order to focus the comparison of the optimizers themselves. We fixed the weight decay value to be

---

Table 1: Average final training loss and test accuracy achieved by each method when optimizing respective models on each dataset. The + shows 95% confidence intervals of the mean loss/accura- cy/perplexity value over 5 runs starting from different random seeds.
CIFARIO
Penn Treebank
Methods
Training loss
Test accuracy
Training
Test perplexity
SGD Momentum
0.2226 + 0.0169
0.8674 = 0.0048
3.8587
0.00558
66.4622 4 0. 3842
SGD Momentum Normalized
0.1262 1. 0.0170
0,8795
0.0086
3.8487
0.0073
61.0558 1. 0.3224
SGDClipGrad
0.1258 + 0,0403
0.8677
0,0106
3,5774
O. 0.0081
60.1601 4 0,2797
SGDC ipMomeeium
0.1220 1: 0.0162
0,8809 = 0.0022
3,6038
0.0102
59.3052 1: 0,2798
Adam
0.1161 + 0.0111
0.8823 = 0.0011
3.7692
U. 0.602
58 10.9005 = O. 0.3058
Our Algorithm
0.1086 +: 0.0129
0.8835
0.0032
3.7028 0.0425
58.9661 +: 1.5218
0.0001 and the momentum parameter (31) to be 0.9. Figure 4 and Table 1 report the training and testing performance for each algorithm, showing that ours is among the best.
LSTM for Language Modeling on Penn Treebank We adopt 3-layer AWD-LSTM [35] to do language modeling on the Penn Treebank (PTB) dataset [33] level). The mini-batch size is 40 and we trained each algorithm for 750 epochs. Apart from the hyperparameters we stated above, we further fine-tuned the weight decay value for all algorithms noticing its significant influence on the performance. We choose the set of hyperparameters that give the smallest final validation perplexity. We report the results in Figure 5 and Table 1. It can be seen that we can match the performance of Adam while beating the others.
5.2 Transformers Observe (Lu, smmoohhhsssssss
For Figure which verifies the original form (1) of the (Lo, L1) condition using the norm, we followed the method in Section H.3 of [56]. Specifically, given 2; and I++1, denote d == I++1 Zt- We estimate the smoothness at B2 by
VV + +dd - VF(2:))l2
L,
max (E(6,.6.....5)
l/d/22
where {81, 62,,82,... .2,...,,8, 8N} denotes the sample locations and we use 1 6 6. g)
For Figure 3 verifying the coordinate wise version (2) of the (Lo. L1) condition. note that the equation symmetric that if we just swap æ and y it shall still holds. Thus, during plotting, we oF compare 6zy (m++1)- oF 6x, (m=) 11 - - vs. min aF (mx) 0zz
of day (.)
Figure I(a) on training a 2-layer Transformer Encoder do language modeling on the Wikitext-2 dataset. The implementation, settings, and parameter choices follow this.' We only plot the first 5 training epochs. Figure 1(b) and are on training 6-layer Transformer [50] to do machine translation on the WMT' 16 Multimodal Machine Translation Task Berman-Engligg dataset. The implementation of the transformer is forked from here" and we also follow their default settings. The mini-bate size is 256 and we trained for 400 epochs using Adam and report the whole training trajectory.
5.3 Clipping does not Affect Adam's Performance
We compare clipping and non-clipping for Adam optimizer on the Wikitext- 103 (103 million tokens, 180MB) [36] language modeling task, with 16-layer GPT-2 transformer model [42]. This GPT-2 model has an input length of 256 tokens, 410 410-dimension word embedding, 16 Attention layers with 10 Attention heads and 2100 hidden dimensions. Model size is 201.58 MB. The vocabulary size is 28996. We use the hyper- hyper-paramen parameter settings prescribed in [53]: batch size 256, warm up learning rate from to 2.5 x 10-4 in the first 64000 samples (i.e., 250 iterations) and then cosine-anneal learning rate to zero, on top of Adam optimizer. It takes about 40 hours to train 200 epochs on 8 V100 GPUs. We use clipping threshold max_ _oorrmmommm 0.25 for the entire model as prescribed in the literature [53]. We also count that with this clipping scheme, clipping occurs in every single batch. As can see from Figure 2, neither training loss (2.79 vs 2.76) nor perplexity score (27.92 vs 27.97) differs much in the clipping and non-clipping case, which is consistent with our theory that Adam naturally achieves gradients clipping effect.

---

6 Conclusion and Limitations
Smoothness has been widely adopted condition for proving convergence rates of algorithms in the non-convex optimization scenario. Yet, it has been found that this assumption does not capture losses when employing some deep learning models including RNNs and LSTMs. In light of this, relaxed smoothness assumption was proposed that aligns well with the practice. We observed that the loss surface of training using Transformers also exhibits this relaxed smoothness. Under this assumption, SGD with clipped gradient has been proven to work well. However, we found that clipping is not necessary for achieving convergence in such a setting. Indeed, we showed that a generalized SignSGD algorithm does not require explicit clipping but can almost guarantee the same bound as SGD with clipping. In the analyses, we identified the key effect of using momentum in analyzing Adam-type algorithms, that it reduces both the noise and the unbounded gradient norms. Finally, we conducted a variety of deep learning tasks showing that our algorithm can match Adam's performance while exceeding others.
Limitations The current work in no way perfect one and there are many directions worth exploring beyond it. First of all, though our algorithm could be seen as a close resemblance to the original Adam algorithm, they are still not equal. Considering the huge popularity of Adam and its established effectivity in practice, it is worth studying whether Adam in its original form can converge in the relaxed smooth setting, Second, while our Theorem 1 are upper bounds and cannot be directly compared between the two cases of 82, it does suggests that 82 = O minimizes the worst-case convergence rate. However, it still does not fully explain the phenomenon that choice of B3 close to 1 yields better performance in using our Algorithm I as well as Adam in practice. Third, despite there are lower bounds showing that, for example, GD with a constant step size can be arbitrarily worse than GD with clipping, it would be more meaningful to study whether the relaxed smooth condition is inherently more difficult, possibly by establishing a lower bound for all first-order optimization algorithms. Fourth, did show that Transformers observe the relaxed smoothness condition, but consider it more beneficial to research in-depth what properties or structures make a model satisfy such conditions. Finally, when conducting our experiments, we observed that the weight decay value plays a prominent role in each optimizer's 's performance, and that the best weight decay value varies for different optimizers. Thus, one potential direction would be explore different ways of incorporating the regularization in a way to preserve the scale-freeness [37, 38) of Algorithm 1, just as AdamW [31] does [58].
Acknowledgements
Michael Crawshaw supported by the Institute for Digital Innovation fellowship from George Mason University. Michael Crawshaw and Mingrui Liu are both supported by a grant from George Mason University. Francesco Orabona is supported by the National Science Foundation under the grants no. 1908111 "AF: Small: Collaborative Research: New Representations for Learning Algorithms and Secure Computation", no. 2022446 "Foundations of Data Science Institute", and no. 2046096 "CAREER: Parameter- free Optimization Algorithms for Machine Learning". The majority of work of Zhenxum Zhuang was done when he was a Ph.D. student at Boston University.
References
[1] I. Alber, Alfredo N. lusem, and Mikhail V. Solodov. On the projected subgradient method for nonsmooth convex optimization in Hilbert space. Mathematical Programming. (1()):23-35, 1998.
[2] Lukas Balles and Philipp Hennig. Dissecting Adam: The sign, magnitude and variance of stochastic gradients. In International Conference on Machine Learning, pages 403- PMLR, 2018.
[3] Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD: Compressed optimisation for non-convex problems. In International Conference on Machine Learning, pages 560-569. PMLR, 2018.
[4] Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press,
2004.
10

---

[5] Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of class of Adam-type algorithms for non-convex optimization. In International Conference on Learning Representations, 2019.
[6] Zaiyi Chen, Zhuoning Yuan, Jinfeng Yi, Bowen Zhou, Enhong Chen, and Tianbao Yang. Universal stagewise learning for non-convex problems with convergence on averaged solutions. In International Conference on Learning Representations, 2019.
[7] Ashok Cutkosky and Harsh Mchta. Momentum improves normalized SGD, In International Conference on Machine Learning, pages 2260-2268. PMLR, 2020.
[8] Ashok Cutkosky and Harsh Mchta. High-probability bounds for non-convex stochastic opti- mization with heavy tails. Advances in Neural Information Processing Systems, 34, 2021.
[9] Ashok Cutkosky and Francesco Orabona. Momentum-basee -basd variance reduction non-convex SGD. In Advances in Neural Information Processing Systems, pages 15236-15245, 2019.
[10] Alexandre Défossez, Léon Bottou, Francis Bach, and Nicolas Usunier. A simple convergence proof of Adam and Adagrad. arXiv preprint arXiv:2003.02399 2020.
[11] Jacob Devlin, Ming-Wo Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 180000000 2018.
[12] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(111:2121-2159, 201
[13] Yuri Ermoliev. Stochastic quasigradient methods. In Numerical techniques for stochastic optimization, number 10 in Springer Series in Computational Mathematics, pages 141-185. Springer, 1988.
[14] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-25 2013.
[15] Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping. arXiv preprint ar arXiv:2005.10785, 2020.
[16] Nicholas JA Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Conference Learning Theory, pages 1579-1613. PMLR, 2019.
[17] Elad Hazan, Kfir Y Levy, and Shai Shalev-Shwartz. Beyond convexity: Stochastic quasi-convex optimization. In Advances in Neural Information Processing Systems, 2015.
[18] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778. 2016.
[19] Geoffrey Hinton, Li Deng, Dong Yu, George Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, and Brian Kingsbury. Deep neural networks for acoustic modeling in speech recognition. IEEE Signal processing magazine, 29, 2012.
[20] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 1835 1997.
[21] Prateek Jain and Purushottam Kar. Non-convex optimization for machine learning. Found. Trends Mach. Learn., 10:142-336, 2017.
[22] Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: asy-asympt analysis. In Advances in Neural Information Processing Systems, volume 34, pages 2771 2771-2782. Curran Associates, Inc., 2021.
11

---

[23] Michael Kamp, Linara Adilova, Joachim Sicking, Fabian Hüger, Peter Schlicht, Tim Wirtz, and Stefan Wrobel. Efficient decentralized deep learning by dynamic model averaging. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 393-409. Springer, 2018.
[24] Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. arXiv preprint (tti::2000003322)) 2020.
[25] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Interna- tional Conference on Learning Representations, 2015.
[26] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pages 1097-1105, 2012.
[27] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436-444, 2015.
[28] Chen-Yu Lee, Saining Xie, Patrick Gallagher, Zhengyou Zhang, and Zhuowen Tu. Deeply- supervised nets. Artificial intelligence and statistics, pages 562-570. PMLR, 2015.
[29] Mu Li, David G Andersen, Jun Woo Park, Alexander Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene J Shekita, and Bor- YoinG Su. Scaling distributed machine learning with the parameter server. In OSDI, volume 14, pages 583-598, 2014.
[30] Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 983-992. PMLR, 2019.
[31] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference Learning Representations, 2019.
[32] Vien V Mai and Mikael Johansson. Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness. In International Conference on Machine Learning, pages 7325-7335 PMLR, 2021.
[33] Mitchell P. Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. Building a large annotated corpus English: The Penn Treebank. Comput. Linguist.. 19(2):31-333, June 1993.
[34] H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. arXiv preprint arXiv:1002.ee 4908, 2010.
[35] Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing LSTM language models. International Conference on Learning Representations, 2018.
[36] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. ICLR, 2017.
[37] Francesco Orabona and Dávid Pál. Scale-free algorithms for online linear optimization. In International Conference on Algorithmic Learning Theory, pages 287-301. Springer, 2015.
[38] Francesco Orabona and Dávid Pál. Scale-free online learning. Theoretical Computer Science 7 716:50-69, 2018. Special Issue ALT 2015.
[39] Razvan Pascamu, Tomas Mikolov, and Yoshua Bengio. Understanding the exploding gradient problem. corr abs/121 111/1211155663 (2012). arXiv preprint arXiv: 2012.
[40] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. International conference on machine learning, pages 1310-1318. PMLR, 2013.
12

---

[41] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, pages 8024-8035, 2019.
[42] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and llya Sutskever. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
[43] Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference on Learning Representations, 2021.
[44] Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In International Conference on Learning Representations, 2018.
[45] Peter Richtárik and Martin Takác. Iteration complexity of randomized blord-coee descent methods for minimizing a composite function. Mathematical Programming. 144:1-38, 2014.
[46] Martin Riedmiller and Heinrich Braun. A direct adaptive method for faster backpropagation learning: The RPROP algorithm. In IEEE international conference on neural networks, pages 586-591. IEEE, 1993.
[47] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
[48] Naum Zuselevich Shor. Minimization methods for non-differentiable functions, volume 3. Springer Science & Business Media, 2012.
[49] Tijmen Tieleman, Geoffrey Hinton, et al. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
[50] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances neural information processing systems, 30, 2017.
[51] Yizhou Wang, Yue Kang, Can Qin, Huan Wang, Yilun Xu, Yulun Zhang, and Yun Raymond Fu. Rethinking Adam: A twofold exponential moving average approach. arXiv preprins arXiv:2/06.11514 2021.
[52] Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. In International Conference on Machine Learning, pages 6677-6686. PMLR, 2019.
[53] Thomas Wolf. Transfer Learning in Natural Language Processing, 2019. Available at https: / //github. com/ wtt.:ccm//////aee htt.//gggggnnceeee///// httpa//nnannaaaaaaaaneeeeeeeeeee
[54] Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. Advances in neural information processing systems, 31, 2018.
[55] Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. In H. Larochelle. M. Ranzato, Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1551 155511. Curran Associates, Inc., 2020.
[56] Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference Learning Representations, 2020.
[57] Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 13:15333-55393, 2020.
13

---

[58] Zhenxun Zhuang, Mingrui Liu, Ashok Cutkosky, and Francesco Orabona. Understanding AdamW through proximal methods and scale-freeness. Transactions on Machine Learning Research, 2022.
[59] Liu Ziyin, Zhikang T Wang. and Masahito Ueda. LaProp: Separating momentum and adaptivity in Adam. arXiv preprint Stdiv:2002.0488333 2020.
[60] Difan Zou, Yuan Cao, Yuanzhi Li, and Quanquan Gu. Understanding the generalization of Adam in learning neural networks with proper regularization. arXiv preprint arXiv:2108.1137/ 2021.
[61] Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. A sufficient condition for convergences of Adam and RMSProp. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11127-11135, 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This paper is mainly theoretical one analyzing machine learning algorithms, we do not forsee any potential negative societal impacts of our work.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 3.
(b) Did you include complete proofs of all theoretical results? [Yes] See the Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as URL)? [Yes] In supplemental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 5. and A.4.
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 5
4. If you using existing assets (e.g., code, data, models) or curating/releusing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] Included the code folder of the supplemental materials.
(c) Did you include any new assets either in the supplemental material
URL? [No] (d) Did you discuss whether and how consent obtained from people whose data you'ne using/curating? [No] Data use follows the permission of corresponding licenses.
(e) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [No]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "q-PyBCWQa5V", "reviewer": "Reviewer_AWaX", "summary": "This paper tackles the problem of optimizing non-convex stochastic functions with relaxed smoothness assumptions, e.g. the $(L_0,L_1)$-smoothness, where the smoothness parameter (i.e. upper bound on the second-order derivative) can be unbounded and locally proportional to the gradient magnitude. Building on prior works [1,2], this paper studies a more fine-grained smoothness, namely the coordinate-wise $(L_0,L_1)$-smoothness. Under this assumption, the authors propose an algorithm based on normalized gradient with momentum and analyze its convergence guarantee. The resulting complexity bound has a similar form to [2], showing that the efficacy of the algorithm does not depend on $L_1$ or the gradient upper bound when $\\epsilon$ is small enough. The authors also give experiments to show that coordinate-wise $(L_0,L_1)$-smoothness is reasonable and the proposed algorithm is practically efficient.\n\n[1] Why gradient clipping accelerates training: A theoretical justification for adaptivity. ICLR 2020.\n\n[2] Improved Analysis of Clipping Algorithms for Non-convex Optimization. NeurIPS 2020.", "questions": "See the above section.", "limitations": "No negative societal impact", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n1. (**Relevance and significance**) Non-convex optimization plays a central role in modern deep learning. Traditionally, the analysis of non-convex optimization algorithms relies heavily on the smoothness of objective functions, in which case vanilla SGD is provably optimal. However, such an assumption is quite unrealistic in practice, especially in training deep neural networks such as LSTMs, for which SGD is much worse than adaptive gradient methods empirically (e.g., Adam). Recently, such an inconsistency between theory and practice has been partially addressed by introducing a relaxed smoothness assumption [1,2]. However, their assumption is still not satisfactory, as the linear dependency between smoothness and gradient norm is very coarse and quite artificial. Investigating better smoothness conditions that align well with practice is clearly of significant value. This paper takes a step towards such a research problem, which in my opinion is important and relevant to the optimization community.\n\n2. (**Writing**). This paper is well-written, clear, and easy to read. The related work section is comprehensive, despite there is an important work missing (see the Weakness part). The comparison between this paper and prior works is well-explained. \n\n3. (**Technical novelty**). I believe studying coordinate-wise smoothness is novel and the proposed algorithm is clean. The similarity of the proposed algorithm with Adam is quite interesting.\n\n**Weaknesses**:\n\nHowever, I have to say currently this paper have several major weaknesses. I hope they can be addressed before acceptance.\n\n1. (**Missing related work**). A recent work [3] tackled almost the same problem with a similar algorithm as proposed in this paper, and thus should be discussed in detail. In particular, the work of [3] studied the algorithm called normalized SGD with momentum under the $(L_0,L_1)$-smoothness assumption (Algorithm 1 and Theorem 3.5 in their paper). They already pointed out how gradient normalization and momentum can be combined together when dealing with $(L_0,L_1)$-smooth functions with noisy gradients, and how a carefully chosen momentum factor reduces the noise and the required mini-batch size. They also pointed out the relationship with Adam. The only difference is that this paper studies coordinate-wise smoothness and thus uses coordinate-wise gradient normalization. Therefore, I suggest the authors to revise some statements in this paper to avoid overclaim, for example, the abstract/conclusion sections, as well as the following lines:\n- Line 74-76: \"To the best of our knowledge, this work is the first one establishing guarantees for generalized SignSGD as well as Adam-type updates under a relaxed smoothness condition.\"\n- Line 8: \"we show that clipping is not indispensable in tackling such scenarios...... Our analysis underlines the critical role that momentum plays: ...... but it also substantially reduces the effects of unbounded smoothness and gradient norms.\"\n\n  Moreover, [3] also relaxed the bounded noise assumption to a much weaker assumption, which is better than this paper. They also found a concrete problem called the distributionally robust optimization, which is provably $(L_0,L_1)$-smooth. On the other hand, compared with [3], the strength of this paper lies in the coordinate-wise smoothness / coordinate-wise normalization which are different and novel. \n\n2. (**Regarding the Assumption**) The proposed smoothness assumption seems unreasonable if I understand correctly. For example, consider the quadratic function $F(x)=\\frac 1 2 (x_1+x_2)^2$. It does not satisfy the inequality:\n\\begin{equation}\n\\left|\\frac{\\partial F}{\\partial x_{j}}(\\boldsymbol{y})-\\frac{\\partial F}{\\partial x_{j}}(\\boldsymbol{x})\\right| \\leq\\left(L_{0, j}+L_{1, j}\\left|\\frac{\\partial F}{\\partial x_{j}}(\\boldsymbol{x})\\right|\\right)\\left|y_{j}-x_{j}\\right|\n\\end{equation}\nbecause $\\left|\\frac{\\partial F}{\\partial x_{j}}(\\boldsymbol{y})-\\frac{\\partial F}{\\partial x_{j}}(\\boldsymbol{x})\\right|$ can be arbitrarily large as $y_i,i\\neq j$ can be chosen arbitrarily which however does not change the right hand side. This seems problematic as even the simple quadratic functions (which are smooth and convex) do not satisfy the condition. The authors should illustrate what functions satisfy this assumption and why it is acceptable.\n\n3. (**Regarding the main results**)\n- The main result only provides a complexity upper bound in terms of $\\min_t ||\\nabla F(x_t)||_1$. This seems a bit weak since $\\min_t ||\\nabla F(x_t)||_1\\le \\epsilon$ does not even indicate convergence of the algorithm. It is likely that the gradients near the end of training (say, the last $0.1T$ iterations) are all large. Can you use better metrics to derive the complexity bounds, such as $\\frac 1 T \\sum_t ||\\nabla F(x_t)||_1$ as in [2], or other better forms?\n- It seems that $\\beta_2=0$ gives the best bound: $\\rho$ reaches the maximal value and the algorithm does not require the extra assumption of the gradient upper bound $M_j$. So what is the advantages of increasing $\\beta_2$? Why do the authors consider the general case when $\\beta_2>0$?\n- This paper makes the assumption that the gradient noise is bounded, which is somewhat restrictive (while it is indeed used in prior works [1,2] for analyzing gradient clipping). However, since [3] successfully derived complexity guarantees of the normalized SGD+momentum algorithm under the weaker and more common noise assumption, I think it is likely that this paper can follow the same techniques to relax the noise assumption. Actually, after coarsely reading the proof I found that part of the analysis (e.g., Lemma 11) is similar to the noise reduction analysis in [3]. This weakness is not a major one, but it would be nice to address it.\n\nNevertheless, I appreciate the motivation of this paper. The current rating is *not final* and I am willing to increase the score if the major concerns (including concerns 1, 2, and the first of 3) are addressed after the author response.\n\n**Miscellaneous minor issues**: In line 194, it should be $\\beta_1<1$.\n\n[3] Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis. NeurIPS 2021.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ju_MYvdCtYj", "reviewer": "Reviewer_JfA2", "summary": "This work extends adaptive (L0, L1)-smooth [1] from gradient clip that clips large gradients to signSGD that shrinks the learning rate when the gradient norm is large. The author proves the convergence and shows the experiments.\n\nThe core idea is that the gradient smoothness is small (it changes quickly) when the gradient norm is large. Both gradient clip and signSGD reduces the learning rate when the curvature changes too fast. \n\n[1] Zhang, Jingzhao, Tianxing He, Suvrit Sra, and Ali Jadbabaie. \"Why gradient clipping accelerates training: A theoretical justification for adaptivity.\" arXiv preprint arXiv:1905.11881 (2019).", "questions": "no", "limitations": "see strengths and weaknesses. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1） Based on the (L0, L1)-smooth observation, the extension from gradient clip to signSGD follows the intuition. \n2） both theoretical proofs and experimental results are shown. \n\n\nWeaknesses:\n1) The (L0, L1)-smooth observation is well demonstrated by [1]. \n2) [1] already prove the fast convergence rate of normalized gradient methods with the (L0, L2)-smooth. \nThe signSGD is close related to the normalized gradient method. (comparing equation (6) in [1] with algorithm 1 line 5-7). \nIt reduces the novelty is this work. \n\n[1] Zhang, Jingzhao, Tianxing He, Suvrit Sra, and Ali Jadbabaie. \"Why gradient clipping accelerates training: A theoretical justification for adaptivity.\" arXiv preprint arXiv:1905.11881 (2019).", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PVjQIGfMSca", "reviewer": "Reviewer_3xib", "summary": "In this paper, the authors firstly studied the applicability and generalization of the relaxed smoothness assumption. Empirically, the authors showed that Transformer, one of the most widely used practical models, also satisfied the relaxed smoothness assumption for some $L_0, L_1$, which showed the assumption is meaningful and not too strong.  Secondly, given the relaxed smoothness assumption, the authors proposed and analyzed a generalized SignSGD algorithm. From theoretical perspective, the authors not only proved the convergence rates, but also located the critical role of the momentum players: it reduces the noise effect and gives an exponential decaying effect on the unbounded gradient norms and smoothness. ", "questions": "Is it possible to propose a last-iterate norm upper bound or average-iterate norm upper bound? \nBy the way, the numbering of the lemmas is quite strange. Lemma 11 is in front of Lemma 9. Could you explain that?", "limitations": "I don't think this paper has any potential negative societal impact since it is completely a theory-based work. All the experiments are used to verify their theory and compare with other optimizers. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper has high writing quality, complete literature review. The topic is OK in terms of originality and significance. However, according to the authors' experimental results, the generalized SignSGD seems to be a little worse than the best existing algorithm, which may make it difficult to be widely used in practice. On the other hand, in the main theorem, the left hand side is the minimum of norm over T, which I feel quite strange, since the most metric I saw is the last-iterate norm and the average norm. It would be better if the authors can make a clear explanation on this. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept