RMSprop converges with proper hyper-parameter
Authors: Naichen Shi
Dawei Li
Mingyi Hong
Ruoyu Sun
Venue: ICLR 2021 Spotlight (2021)
Keywords: RMSprop
convergence
hyperparameter

Abstract: Despite the existence of divergence examples, RMSprop remains 
one of the most popular algorithms in machine learning. Towards closing the gap between theory and practice, we prove that RMSprop converges with proper choice of hyper-parameters under certain conditions. More specifically, we prove that when the hyper-parameter $\beta_2$ is close enough to $1$, RMSprop and its random shuffling version converge to a bounded region in general, and to critical points in the interpolation regime. It is worth mentioning that our results do not depend on  ``bounded gradient"  assumption, which is often the key assumption utilized by existing theoretical work for Adam-type adaptive gradient method. Removing this assumption allows us to establish a phase transition from divergence to non-divergence for RMSprop. 

Finally, based on our theory, we conjecture that in practice there is a critical threshold $\sf{\beta_2^*}$, such that RMSprop generates reasonably good results only if $1>\beta_2\ge \sf{\beta_2^*}$. We provide empirical evidence for such a phase transition in our numerical experiments.

Published as a conference paper at ICLR 2021
RMSPROP CONVERGES PARAMETER
WITH PROPER
HYPER-
Naichen ;hi; Dawei Lij Mingyi Hong; Ruoyu Sun
ABSTRACT
Despite the existence of divergence examples, RMSprop remains one of the most popular algorithms in machine learning. Towards closing the gap between theory and practice, we prove that RMSprop converges with proper choice of hyper- parameters under certain conditions. More specifically, we prove that when the hyper-parameter 33 is close enough 1, R.MSprop and its random shuffling version converge to bounded region in general, and to critical points in the interpolation regime. It is worth mentioning that results do not depend on "bounded gradient" assumption, which is often the key assumption utilized by existing theoretical work for Adam-type adaptive gradient method. Removing this assumption allows us establish a phase transition from divergence to non-divergence for RMSprop.
Finally, based on our theory, we conjecture that in practice there is a critical threshold 152 such that RMSprop generates reasonably good results only if 32 2 88. We provide empirical evidence for such phase transition in our numerical experiments.
INTRODUCTION
RMSprop TTellmman & Hinton 2012) remains one of the most popular algorithms for machine learning applications. As a non momentum version of more general algorithm Adam, RMSprop's good empirical performance has been well acknow
by practitioners in generative adversarial
networks (GANs) (Seward et al., 2018; YazIeı et al. 2019; Karnewar Wang 2020 Jolicoeur Martineau 2019), reinforcement learning (Mnih et al. 2016), etc. In spite of its prevalence, however, Reddi et al. a (2018) discovered that RMSprop (as well as the more general version Adam) can diverge even for simple convex functions. To fix the algorithm, the authors Reddi et al. (2018) proposed new variant called AMSGrad, which is guaranteed to converge under certain conditions.
Since then, it has been active area of research to design provably convergent variants of RMSprop. These variants include AdaFom (Chen et al. 2019), Adabound (Luo et al., 2019). Nostalgic Adam (Huang al. 2019). Yogi (Zaheer al. 2018)), and many more. Despite the variants, the vanilla RM- Sprop indeed works well in practice, and after proper hyper-parameter tuning, the non-convergence issue has nor been commonly observed. Why there a large gap between theory and practice? Is this because the real-world problems are likely to be "nice", or is it because the theoretical analysis of RMSprop does not match how is used in practice?
With the above questions in mind, we revisited the exumler- of Reddi et al. (2018) and found an interesting phenomenon. One counter-example of Reddi et al. (2018) is the following:
Cz, for t mod C = otherwise
ft(x))
(1)
where x E 1-1, They proved the divergence under the condition B2 & min ( where 82 is the second order momentum coefficient in Algorithm (the algorithm is presented later). For instance, when C' = 10, then the algorithm diverges if B2 < 0.3. Reddi et al. (2018) mentioned
DC
'IOE, University Michigan, naichens @ umich.edu. Part of the work was done when Naichen Shi was working with Prof. Ruoyu Sun as an intern.
IISE University of Mllinoi Urbana- Chaana-haampiig.....
illinoisddd
TCE, University of Minnesota - Twin Cities, mhong @ umn.edu.
5 University of Illinois Urbana-Champan ruoyus @ @illinoislidddu Corresponding author: Ruoyu Sun.

---

Published as a conference paper at ICLR 2021
2-5 B2)
3.5
1og:o
Figure 1: Phase diagram of the outcome of RMSprop on the counter example (1. Different marks represent different outcome: label data point convergence if the distance between and - smaller than 0.01 on average after 750000 iterations example, but for each counter example in which Adam diverges, there exists larger 32 that can make Adam converge. We fix 81 = 0. Step size is set as T)t
as divergence otherwise. each choice of 92, there exists counter
that "this explains why large 82 is advisable while using Adam algorithm", but they did not analyze whether large B2 leads to convergence in their example. We ran simulation for problem (I) with different 32 and found there is always a threshold of 83 above which RMSprop converges, see Figure I For instance, when C' = 10, the transition point of B2 is roughly 0.955: the algorithm converges 32 > 0.956 but diverges 32 < 0.955. In general. there is a curve of phase transition from divergence to convergence, and such curve slopes upward, which means the transition point is closer to if C' becomes larger. Based on this observation, we make the following conjecture:
Conjecture: RMSprop converges if 32 large enough.
Before further discussion, introduce the following assumption. Assumption 1.1. f(x) Eÿ= f2(), and
VS S DI DV (x) Do-
We divide optimization problems into 2 classes: realizable problems where Do 0 and
non-realizable problems where Do > O. When Do = 0, the assumption (I.I) becomes (+) < D1 [=) which is called "strong growth condition" (SGC) Vaswani ). It requires the norm of the stochastic gradient to proportional to the batch gradient norm. When fx))l
for all j. For linear regres- sion problems, SGC holds the linear model can fit all data. More specifically, for the problem minx ||x|| ー (a
0. under SGC have V (z)]l
x) where A is an by matrix and a² is the j-th row vector of A, SGC holds with D1 < Amax (ΣnL. a.a. a,aa)) /Amin (AT A) (Raj & Bach, 2020). SGC can be viewed as simple condition that models overparameterized neural networks capable of interpolating all data points (Vaswani et al. 2211)). Therefore, in this work we use the terminology "realizable problems" to refer to the problems that satisfy SGC.
1.1 MAIN CONTRIBUTIONS
In an attempt to resolve the conjecture, we delve into RMSprop's convergence issues and obtain a series of theoretical and empirical results. Our contributions summarized below:
2

---

Published as a conference paper at ICLR 2021
We find that RMSprop's convergence is contingent the choice of 82. For general optimization problems, there are two types of hyper-parametens parameters such as step size in GD, and universal constants such momentum coefficient in heavy ball method] Our result reveals that 32 is closer to the first type.
pebblemddepedent hyper-
We prove that RMSprop converges stationary point for realizable problems (interpolation regime), and to some bounded region for non-realizable problems. Combining with the divergence example of RMSprop, this indicates the existence of phase transition from divergence to convergence dependent on $2- Note that when we say "convergence", in weak sense means the sequence converges to a bounded region for non-realizable case; and in a strong sense it means the sequence converges to stationary points for realizable case.
To our best knowledge, we the first to prove the convergence of RMSprop and some of Adam without any form of assumption about the boundedness of the gradient norm. This is important for showing the transition: with added assumptions on bounded gradients, the gradients cannot diverge, while the counter-exampel shows that the gradient can.
2 PRELIMINARIES
We consider a finite-sum problem:
n-1 min f(x) = fz(() aER
(3)
j=0
In neural network training. fj usually represents the loss contributed by the j-th sample batch. We present randomly shuffled Adam in Algorithm RMSProp is the special case of Adam with 31 0. In this work, we mainly focus on RMSprop: nevertheless, we will present a result for a special case of Adam with small 31.
Algorithm Randomly Shuffled Adam
Initialize m1.-1 for l = + 0o do
1 T-8
V (zoo and 11.- T-33 max, (Vf)(())())) o (z)())))
Sample {Tk.0, Th.1, ... -h,n-1) } as random permutation of 1,, .. ,, 1}
for i 0 +
do
m = 31m2,i-1 + (1 31) V
Uk = 32 1 + (1 B2) V FT. V
Fk,i-1 = Ikii Ve m4,
Mhen
end for
Break if certain stopping criterion is satisfied.
TA+1.0 Tk,a Uk+1,-1 U 1,, M m
end for return x
In Algorithm [ x denotes the optimization variable, m denotes the first order momentum and denotes the second order momentum. Specifically, we denote Zk,i, my,s, Uk,i E Rd as the value of v at the k-th outer loop and i-th inner loop, respectively. We denote Vf, as the gradient of fj and let be the component-wise multiplication. The division of two vectors is component wise as well. Moreover, we denote Y/: the step-size and B1, B2 as the hyper-parameters in the algorithm. When n = 1, we obtain full batch Adam.
We replaced the bias correction step in (Kingma & Ba 2015) with special initialization on m1,-1 and 11,-1. This initialization can also correct the bias, but has cleaner results. Since the effect of initialization RMSprop with zero initialization or our initialization will have the same asymptotic behavior. We put results for the original version of RMSprop in the appendix.
bias correction becomes more and more negligible the training progresses,
'Rigorousyy speaking, for the best convergence rate, the momentum coefficient should also be problem- dependent; but just for achieving convergence, it problem independent.
3

---

Published as a conference paper at ICLR 2021
As for hyper- parameearameeers, we choose 7 vt and fix Bg to be a constant that is independent of the iteration count. We allow e to be an arbitrary non-negative constant; in particular, our result holds even for c = O. The constant is added in practice for numerical stability, and is typically chosen to be 10-6 or even 10-$, It is much smaller than Uki (which is roughly the size of gradient norm).
2.1 RELATED WORK
As discussed earlier, one line of research focuses on variants of RMSprop and Adam that can be proved to converge. These works usually modify the update rule of vt. For instance, AMSGrad (Reddi et al. 2018), AdaFom (Chen et al. 2019) explicitly make non-decreasing. Nostalgic Adam (Huang et al. 2019) and the algorithms analyzed in Zou et al. (2019) and [Chen et al. (2019) use iterationdeeeedentt 32 (and/or 31.) to let 2 weigh more on past gradients. Some works add new modifications into RMSprop and Adam; for instance, Zhou et al. (2019) mitigate the bias in update direction by using different estimate of Uz. Dozat (016) combine Adam with Nesterov momentum, and Liu et al. (020a) employ a warm-up technique.
Besides modifying the algorithm, a few attempts have been made to address the non-convereence issues of the original versions, but they often rely on extra assumptions. A number of works (Zaheer et al. 2018 De al. 2019 Défossez al. 2020) prove the convergence of Adam under these additional assumptions. One representative work along this line, Défossez et al. (2020), establishes a clean convergence result and also provides some insights on the momentum mechanisms by improving the dependence of the iteration complexity on 1 - 31. However, these works assume to be relatively large compared to / /Uk,i. The issue is that such choice essentially transforms RMSprop back to SGD since the effective step size is primarily controlled by c, in lieu of Vuk, This is in contrary to the spirit of RMSprop. which is to use adaptive step size to accelerate convergence, A few other works do not need the assumption of e, but they have other assumptions. [De et al. (2018) analyze deterministic and stochastic RMSprop, but they utilize a rather unrealistic assumption that the sign of sign( V (z)) for all p. 9. Chen et al. (2019) describe a few quantities based on the iterates, and prove that if they grow in certain speed as the iterates go, the algorithm converges. The drawback is that the condition cannot be checked a priori. Besides the assumptions mentioned above, all the aforementioned works require the gradient to be bounded.
all noisy gradients are the same, i.c., sign( fff())
In general, removing boundedness assumptions (of any kind, including bounded gradient, bounded iterates, etc.) is not necessarily easy. Thus, such results are appreciated even for basic SGD. For instance, Bertsekas & T'itsiklis (2000) presents a nice discussion of various results on inexact GI) without involving conventional bounded assumptions, and claims douuddd--assuppiinn of the main contributions of their work. Very recently, we notice another work (Liu et al.] 2020b) which removes the bounded gradient assumption for SGDM (SGD with momentum) and obtains satisfactory rates. Nevertheless, we are not aware of an existing result on RMSprop that does not require bounded gradient assumption. We will explain later why removing this bounded gradient assumption is particularly important for our paper.
one
THE raison é'être FOR B₂
Figure [ clearly demonstrates the important role of 33 in the convergence of RMSprop. Specifically, sufficrently large 3g critical for RMSprop's convergence. Indeed, some recent works (Reddi et al. 2018 Zhou et al. 2019) have also made similar arguments, but they focus on understanding one part of the phenomenon, that is, small 32 leads to divergence. Our goal in this work is to complete the other part of the story by showing that, sufficiently large B2 guarantees convergence. The formal result will be provided in Sec.
To understand the function of B2, we first discuss why RMSprop diverges. It is known that the stochastic noise due to mini-batch will distort the gradient direction, leading to possible divergence, but in standard SGD, the distortion in multiple iterations is eliminated since the stochastic gradient is an unbiased estimate of the gradient. For RMSprop, at a given iteration the scaling constant 1/ l/vē in the update direction may cause larger gradient distortion than the standard SGD. The distortion can be so significant that the average updating direction falls outside the dual cone of the true gradient. To illustrate this consider the extreme case that B2 and 0 (i.e., signSGD) and the special
4

---

Published as a conference paper at ICLR 2021
example (T). When applying signSGD to solve in each epoch which consists of C' iterations, one iteration will move left followed by C - iterations that move x right. Since all step sizes are the same in epoch, the accumulated effect of one epoch makes move in the ascending direction, instead of the descending direction.
Then why does large B2 help? Intuitively, large B2 can control the distortion update directions. In the extreme case that B2 = 1 and c = O, RMSprop reduces to SGD where the distortion of multiple iterations can be mitigated, leading to convergence. We suspect that 32 does not need be exactly and large 32 is enough to control the distortion. Our experiment in Figure confirms that, at least for the counter-example of Reddi al. (2018), there an interval [3 [c. such that RMSprop converges.
What was initially not clear is whether the counter-example of Reddi et al. (2018) very special case or the convergence of large-3z-RMSpro holds for all problems. We found the real situation is somewhat more tricky. For non-realizable problems, we discovered an example for which RMSprop cannot converge to the minimum for wide range of (3 < 1, but unlike the small-32-case the iterates converge to small ball around the minimum. This motivates us to distinguish three convergent- situations: divergence, convergence to a small region, convergence to critical points. What we can prove for the general problem is (see Theorem 4.3p: for small 32. R.Sprrp can diverge; for large B2, RMSprop must converge small region whose size depends on $2.
Then why do we observe the convergence to a single point in the experiment for ! We suspect this is because the problem (I) is realizable, and conjecture that the property of "convergence to critical points" holds for all realizable problems. We indeed prove this conjecture (see Corollary 4.1): large-32 Sege-33-RMMprop converges critical points if the problem satisfies SGC.
We summarize our findings about the convergence properties of RMSprrp in Table
Setting non-realizable realizable
32 close to I
Bg close to diverge
converge to small region (Thm. converge to critical points (Coro.
diverge
Table 1:
Outcome of shuffled RMSprop under different hyperparameter settings. On unconstrained problems, the gradient norm can decrease to zero after infinite iterations, we classify the result as "convergence to critical points", ; If the gradient norm keeps increasing to infinity during training, we classify the result as "divergence". We classify result "converge small region" if the gradient falls below certain level but not close
Note that our results do not conflict with Theorem 3 in Reddi et al. (018)) which claims that "for any constant B1 and 32 there exists a divergent example" since here we choose 33 to problem- dependent, just like one chooses step size < 2/T, for GD where I, is problem dependent parameter. Another remark is that though 32 could be close to I, RMSprop still retains the ability to adapt v to gradient square norm long B2 1, because and the impact of previous signals decays exponentially. is the adaptive ability that distinguishes R.Spprpp from SGD. Proving the theoretical advantage of R.SSprpp over SGD (i.e., choosing B2 < 1 better than 32 = 1) is a very intriguing question; in general, the theoretical advantage of adaptive gradient methods (including R.Mpprop and AdaGrad) over SGD is long standing question. in this work, we focus on the fundamental problem of convergence, instead of the more challenging question of justifying the advantage of RMSprop.
gradient signals
added for each iteration
CONVERGENCE RESULTS
In this section, present the formal theoretical results. We start from the results of full batch RMSprop/Adam, and then present the results for the stochastic versions. Note that random shuffling not a key factor, and the proof works for other settings.
5

---

Published as a conference paper at ICLR 2021
4.1 FULL-BATCH VERSION
We first consider the full-batch version of RMSprop. The following theorem shows that if we use all samples evaluate the gradient, RMSProp with diminishing stepsize converges critical points regardless of the choice of 32. Here we consider one popular step size schedule that 1/2
m1
V
Theorem 4.1. (convergence of full-batch RMSprop) For problem (3) with
assume that is gradient Lipschitz continuous with constant L and lower bounded by f Then, for full-batch
RMSprop (Alg. I with $1 = 0, = 0) with diminishing step size T) vE
"t and any B2 E (0, 1), we
have:
log VT
min SE(LTT)
|V 00
where T 0 is the total iteration number.
De et al. (2119) also proves the convergence of full batch RMSprop. but they require the gradient norm to be upper bounded; in contrast, we do not need this assumption, and only require lower-boundedness and L-smoothness of f-
Our result suggests that the convergence property of batch- Mutch-pMSSrrpp. is similar to signSGD, an algorithm that only uses the sign of gradient calculate its descent direction (Bernstein et al. 2018): in the full-batch setting, signSGD (which can be called sign GD) has also been proved to converge without bounded gradient assumption.
Below, we also derive an analogous result for full-batch Adam with only one additional constraint 31 < V B2 < which is often satisfied in practice:
Theorem 4.2. (convergence of full-batch Adam) For optimization problem (3) with assume that f is gradient Lipschitz continuous with constant L. and lower bounded by f Then, for full- Adam with diminishing step size Tp. /t
and any 31 < V < 1, we have:
log T VT
min EL
V 5o
4.2 STOCHASTIC VERSIONS
As mentioned earlier, simulation shows that RMSprop may not converge critical points for non-realizable problems (an example is provided in the appendix). Nevertheless, we can still show randomly shuffled large-82-RMSSpon converges to bounded region:
Theorem 4.3. (large-3 32 RMSprop converge to a region) For problem assume f is bounded by f and all f, is L-Lipschitz continuous. Furthermore, assume holds, and B2 satisfies
Ta (B2)
A V
10dn B
dnD1
(1- 32)
11)
V2 1
(4)
13
2/2
Then, for randomly shuffled RMSprop with 1).
I1, Vt"
have
min min Suell IIVS V (E(1.T]
Did Do
so
log
VT
+ (Qaav Do VT24.
Here Q3,3 is a 32-dependent constant that goes to zero in the limit as B2 +
Remark 1. This result and the result in Reddi et al. 2018) together distinguish
and small-33--RM. RMMMoopp the former converges to a bounded region, while the latter can diverge. Note that there is gap between the lower bound of 33 and the upper bound of Bg in the counter-exampi examee. We do not try to provide tight bounds on the threshold 82 as our main goal is to show a qualitative difference between large-33-RMSSp and small-3,-RMa mnall-3--RMiSprop.
Remark 2:
Condition 4 in Theorem 4.3 implies that 8g S O (n'n 3.5) In the appendix introduce three problem-dependent parameters A1 [1, Vn), P2 E [0, n), and As [1,yn] in equations 115

---

Published as a conference paper at ICLR 2021
to 1 1 ( (nP1P2Ps)). For the worst case, the bound is O (n-3.9,, just like condition 4 Theorem 4.3 3 In actual training process, Pl, P2. and P3 may not reach their upper bounds, thus the threshold of 522 can be lower in practice (see Appendix A.5 for some empirical estimate of p; s). The dependence on the number of batches n suggests that as n increases, the required nyper-parameter 32 should be larger. This is understandable since more minibatches means larger noise in the stochastic gradient, and thus larger B2 is required. There is gap between our theoretical bound of 32 and the empirical transition point, and it is an interesting future question to close this gap.
and (16), and improve the sufficient condition 4
We point out three possible algorithm behaviors: divergence to infinity (or divergence for short), convergence
Remark 3.
bounded region (or non-divergence for short) and convergence critical points. We distinguish the three cases, making it easier to explain the qualitative difference of small-32 and large-$2 regime. For non-realizable cases, the phase transition from divergence to non-divergence. Therefore, it is important to discard the bounded-gradient assumption: this assumption eliminates the possibility of divergence of gradients a priori. To be clear, there are actually two sub-cases of non non-divergence: iterates can stay in a bounded but huge region (bad case), or iterates stay in bounded region dependent on some parameters (good case). Indeed, the "convergence" of constant-stepsize SGD is in the sense of "converging to region with size proportional to the noise variance".. Our result of "converging to bounded region" is also meaningful as the size of the region goes to zero the noise variance goes to 0 or Do goes to 0 (realizable case).
Note that "divergence" can be also interpreted as "not converging to critical points" which is the notion used in Reddi et al. (2018), instead of "diverging to infinity"". We use the latter concept of "diverging to infinity" for the term "divergence", because "not converging to critical points" can small region around critical points (like monstnt--stessize SGD). In the example of Reddi et al. (218), a constrained problem is considered (bound constraint [-1,1]), thus divergence infinity cannot happen. We add an example where the iterates and the gradients can diverge to infinity for small B3; see Appendix A.2.
include the good case of converging
As corollary of Theorem 4.3 if the optimization problem satisfies SGC (i.e. Do = -)), RMSprrp converges to critical points.
Corollary 4.1. Suppose the assumptions of Theorem 4.3 holds. Further, assume holds with Do = 0, ie., Ej [V (x)] < D1 / (z)1l2 for all x. we have:
log
|V so 8E(1.7)
min
vT24 4.
With the above corollary, the numerical result in Figure [ should not be surprising: problem ! satisfies the strong growth condition, and thus there is always range of B3 inside which RMSprop converges. We just need to tune 32 larger.
We can prove similar convergence results for Adam with small 31 and large 32.
Theorem 4.4. For optimization problem 3 assume that f is lower-bounded by f and f, is
gradient Lipschitz continuous with constant for all j. Furthermore, assume that f, satisfies (2) for all x. Then, for randomly shuffled Adam with diminishing step size ipe Vi and Br, B2 satisfying
T1 (81.32) + T2 (82) < 1- V we have minee(1, f S O
log T
VT 2 T2 is defined in and Ti
+0 (Qa.sDDo
/T
4, where Q3.5 is a constant that approuches the limit Ti + T2 > defined as Ti (31,
dn D 83
+ +1)
Remark: This result shows that controlling 32 and B1 together can ensure convergence of Adam. We conjecture that the same convergence can be proved for a large range of 31, but we are not able to prove that for now (which is why we focus on RMSprop in this work) and leave it to future work.
EXPERIMENTS
We conduct experiments of image classification and GAN MNIST and CIFAR-10 to support our theoretical findings. The details of GAN experiments are in the appendix, and this section we focus on image classification results.
7

---

Published as a conference paper at ICLR 2021
075
12:0.90
12:0.6
030
025
600
025
0
-1 00
Figure Trajectories of RMSprop with large small 82 the loss surface. Two trajectories start from the same initialization and trained on the same dataset MNIST, but have very different behavior. We calculate hyper-plane spanned by the starting point of two trajectories and their respective ending points, and then project two trajectories onto this plane. The large- 82 -b-trajectory converges to minima, while the small- falll-22-aa d2-trajectory diverges. The difference between these two trajectories suggests phase transition for 82 in (0.8, 0.99).
We visualize the optimization trajectory when training on MNIST for small 3g 0.8 and large 82 0.99 in Figure We observe different behaviors: while the trajectory of f3 0.8 moves away from the bottom of the basin, for larger B2 the trajectory stays in the level set and has decreasing loss values.
In the CIFAR experiments, we use ResNet-18. We choose 3n = 0.8, 0.9, 0.95, 0.99 respectively. With different batch sizes 8, 16, 32, run each algorithm for 100 epochs without explicit regularization. Table 2 shows two phenomena: first, for fixed batch size, there is transition point of B2 above which the accuracy suddenly jumps; second, the transition point is closer to the batch size decreases. More specifically, for batch size 8, the transition point lies in (0.95, 0.99]: the average training accuracy is 44.53% for 82 = 0.95, but jumps 99.74% for for f3 0.99. For batch size 16, the transition point lies in (0.9, 0.95]: the average training accuracy is 67. .777%% for B3 0.9, but jumps to 96.38% for 82 = 0.95. For batch size 16, the transition point lies [0.8, 0.9]. As batch size increases from 8 to 16 and then 32, then transition point decreases from 0.99 to 0.95 and then to 0.9.
These two phenomena are consistent with our theory. The first phenomenon can be explained by Theorem 4.3 and Corollary 4.1 which state that for large enough 8g. R.MSprop converges. The second phenomenon can be explained by Theorem 4.3 as well: as explained in Remark the required 83 decreases as the number of mini-hatches decreases, i.e., the batch size increases.
Table 2:
Performance of Adam with different 82 with ResNet-18 CIFAR-IO (100 epochs)
batch size
measure
3y=0.8
8y=0.9
32=0.95
82=0.99
SGD
train acc.
10.00110.00
10.00+1.000
44.53+32.09
99.74:10.06
100.0011..00
test acc.
10.00:10.00
10.00=0.00
42.02:129559
70.2340.26
70.37+0.44
16
train acc.
28.70-132.39
67.274
96.3811.35
99.7510.05
99.9810.02
acc.
27.64:1:0.55
62.7117.71
70.1110.90
70.4310.15
69.4510.38
32
train acc.
66.9333.07
96.72.11.6
99.1710.42
99.80
81.50
test acc. 63.99:42.13
70.05+11.40
71.92+0.50
71.34
68.92+1.12
Next, we demonstrate that the convergence speed of SGD is much slower than Adam under the same experiment setting as T We compare the average training and test accuracy at the 10-th epoch. As Table 3 shows, the accuracy of Adam is much higher than SGD at the 10-th epoch.
All codes generating experimental results are available on the Github repository https: /tt::/ggttti github com/sounde http://oonnnsnnteeessssiiiiieiee wtwresti
8

---

Published as a conference paper at ICLR 2021
Table 3:
Training and test accuracy the 10-th epoch
batch size
measure
32=0.99
SGD
train acc.
95.41=10.1
05.8911.25
test
70.02:#0.17
62.62=11.26
32
train acc.
97.92.10.23
57.8710.70
test acc.
70.44:0.19
56.18=0.86
CONCLUSION
In this work, we study the convergence behavior of RMSprop by taking a closer look at the hyper- parameters. Specifically, for realizable problems, provide a data-dependent threshold of 8 above which we prove the convergence of randomly shuffled RMSprop and small 83 Adam without bounded gradient assumption. We also show that R.Mpprop converge into bounded region under non-rcalizable settings. These findings reveal that there is critical threshold of 32 regarding the convergence behavior of RMSprop, and the phase transition supported by the numerical experiments. Our results provide basic guidelines for tuning hyper-parament parameters in practice.
7 ACKNOWLEDGEMENT
M. Hong is supported by NSF grant CMMI-1727757. Ruichen Li from Peking University helped check some proof of Theorem 4.3 We thank all anonymous reviewers for their feedback. We also want to thank Eduard Gorbunov and Juntang Zhuang for pointing out some mistakes on openreview in the earlier versions.
REFERENCES
Jeremy Bernstein, Yu-Xisi Xiang Wang, Kamyar Azizzadenesheli, and Anima Anandkumar. SIGNSGD: Compressed optimisation for non convex problems. Arxiv:1802.04434 2018.
Dimitri Bertsekas and John Tsitsiklis. Gradient convergence in gradient methods with errors. SIAM Journal on Optimization, 10(3):627-622, 2000.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. for non-convex optimization. International Conference on Learning Representations, 2019.
On the convergence a class of Adam-type algorithms
Soham Anirbit Mukherjee, and Enayat Ullah. Convergence guarantees for RMSProp and Adam non-
convex optimization and an empirical comparison to Nesterov acceleration. A807v 2018.
Soham De, Anirbit Mukherjee, and Enayat Ullah. Understanding RMSprop and Adam: Thcoretical and empirical
studies. Arxiv: 180,06676,, 2019.
Timothy Dozat. Incorporating Nesterov momentum into Adam. International Conference Learning Repre- sentations, 2016.
Alexandre Défossez, Léon Bottou, Francis Bach, and Nicolas Usunier. On the convergence of Adam and Adagrad. CoRR, abs/2003.00335, 2020. URLptttps//arxxv.oogg/
/200222203..mm 02395
Haiwen Huang, Chang Wang, and Bin Dong. Nostalgic Adam: Weighting more of the past gradicnts when designing the adaptive learning rate. IJCAI, 2019.
Alexia Oolicour-Maartnenn tional Conference Learning Representations, 2019.
The relativistic discriminator: key element missing from standard GAN, Interna-
Animesh Karnewar and Oliver Wang. MSG-GAN: Multi-Scale gradients for generative adversarial networks. CVPR, 2020.
Diederik P. Kingma and Jimmy Lei Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. In Internationnl Conference on Learning Representations, 2020a. URL URI.tttps::.... //tppps::///ppeieeeeeeee revi ww..et..eeeeeeeeeee www.nee/forrmmmt.akkraaaaaa

---

Published as a conference paper at ICLR 2021
Yanli Liu,, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. Neural Information Processing Systems, 2020b.
Liangchen Luo. Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. International Conference on Learning Representations, 2019.
Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy P. Lillicrap. Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods deep reinforcement learning. International Conference on Machine Learning. 2016.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks, International Conference on Learning Representations, 2016.
Anant Raj and Francis Bach. Explicit regularization stochastic gradient methods through duality. Arxiv, 2020.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. International Conference on Learning Representations, 2018.
Calvin Seward. Thomas Unterthiner, Urs Bergmann, Nikolay Jetchev, and Sepp Hochreiter. First order generative adversarial networks. In Proceedings of the 35th International Conference on Machine Learning, Proceedings of Machine Learning Research, pp. 4567-4576. PMLR, 10-15 Jul 2018. URL WuRLatttp://prceedingg
/v//s///v///// m1 press/ v80 Ba..
Tieleman and G. Hinton. RMSProp: Divide the gradient by running average its recent magnitude. Coursera, 2012.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of SGD for over-parameterized models (and an accelerated perceptron). Neural Information Processing Systems, 2019.
Yasin YazIcı, Chuan-Sheng Foo, Stefan Winkler, Kim-Hui Yap. Georgios Piliouras, and Vijay Chandrasekhar. The unusual effectiveness of averaging in GAN training. International Conference Learning Representa- tions, 2019.
Manzil Zaheer, Sashank J.Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. Neural Information Processing Systems, 2018
Zhiming Zhou, Qingru Zhang, Guansong Lu, Hongwei Wang, Weinan Zhang, and Yong Yu. Adashift: decorrela- tion and convergence of adaptive learning methods. International Conference Learning Representations, 2019.
Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. sufficient condition for convergences of Adam and RMSProp. CVPR, 2019.
10


Reviews:
[{"review_id": "hkya5mHmDvE", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe paper studies one of the most popular algorithms in machine learning: RMSprop. More specifically, it investigates the relation between the hyper-parameters and the convergence of the algorithm. By proving the convergence without using \"bounded gradient\" assumption, the authors establish a phase transition from divergence to non-divergence for RMSProp.\n\nPros:\n\n1. The paper concerns one of the most important algorithms in machine learning. In my opinion, the problem is practical and of interest in machine learning community.\n\n2. The results of the paper provide explicit conditions for the hyper-parameters of RMSprop/Adam that ensure the convergence of the algorithms. These results provide basic guidelines for tuning hyper-parameters of the algorithms in practice.\n\nCons:\n\nApart from the strong points, I still have some concerns about the clarity of the paper. I hope the authors can address my concerns to improve the quality of the paper.\n\n1. The parameter $\\beta_2$ is the most important subject of the paper. Until algorithm 1, the paper discusses $\\beta_2$ without defining it clearly. It would be more clear if $\\beta_2$ is mentioned from the beginning of the paper that it comes form algorithm 1.\n\n2. The authors divide the problems into 2 sub-classes to investigate: realizable and non-realizable, which are not clearly defined. It would be better if the authors can define these 2 sub-classes more formally.\n\n3. The experiments supporting the theoretical results are comprehensible. However, I would suggest the authors provide a figure with x-axis to be epochs and y-axis to be accuracy so that the readers can have better idea upon how SGD and RMSProp behave during training.", "extra_scores": {}, "extra_text": {}}, {"review_id": "dpuRDjWPy3D", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper starts off from the recent realization that there exists divergent examples for any set of hyperparameters for algorithms in the Adam family, such as RMSProp. It sets out to study the effect of the beta2 parameter on convergence for a fixed specific problem. The analysis shows that there exists a beta2 < 1 that leads to convergence for realizable problems, and to convergence to a bounded region of interest for non-realizable problems, without requiring a bounded-gradient assumption. Experiments confirm this new theory.\n\nOverall, the paper is well-written, clear and easy to read. One of its strongest points is how well the analysis and the relevance of the results is motived. For instance, the importance of removing the assumption on the bounds on the gradient because it effectively removes one of the convergence/divergence regimes is well executed.\nThere is also significant efforts on providing clear simplified examples from rather complex theorems, which is very appreciated (e.g. Corollary 4.1).\nFurther, there is a real effort to contrast the results with the previous work, and to explain how it complements them, resolving clearly what initially appears as direct contradictions.\n\nThe results are relevant, both from the point of view of the theory, where it adds to a body of work explaining how and why the Adam family of algorithm performs well on modern machine learning taskloads, and from the point of view of the practitioner, outlining what hyperparameter tuning is necessary to achieve convergence. They are also original, in the sense that they provide novel insights, while removing problematic assumptions that permeate most of the related work.\n\nA couple of things could be improved:\n- as pointed out in the paper, if beta2 = 1, the algorithm degenerates to SGD. While there is a remark explaining why as long as beta2 < 1 the two algorithms differ, it would be informative to compare the convergence regimes with high beta2 to SGD directly, to validate that there exists a set of hyperparameters that not only provide convergence, but improved convergence properties compared to SGD (otherwise the results are a lot less relevant), as well as give an order of magnitude of what value is typically necessary for beta2.\n- condition (4) in theorem 4.3 is quite difficult to apprehend, with a slightly worrying beta2^n term. More exegesis would be beneficial for reader comprehension.\n\nOverall, this is a nice, well-written and relevant paper that clears the bar for publication in its current version.", "extra_scores": {}, "extra_text": {}}, {"review_id": "cjfcGuf98pp", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 work revisits a famous counterexample on the convergence of Adam (originally presented in Reddi 2018). The authors show that, if the EMA parameter beta2 in RMSprop and Adam is chosen high enough, then both methods converge to a bounded region in the stochastic setting. In addition, the authors provide some results for the full-batch case. Crucially, and differently from many other papers on the topic, the gradients are not assumed to be bounded and the beta2 hyperparameter is not chosen to increase to 1.\n\nThe paper is well written and the logic of it is convincing. I like the introduction and Figure 1 (this nicely illustrates the relevance of this paper). It is also very well organized. Unfortunately, I did not have the time I wish I had to dig into the proofs (just had a quick check), but the methodology of the authors and the results are convincing.\n\nThis is overall a very nice paper, with clean and easy to read results, that clarifies an important point: it is misleading to claim that “Adam does not converge” (which was pointed out in Reddi 2018 to introduce AMSgrad). I have heard this (wrong) claim many times in the optimization community – hence I think this paper deserves attention (therefore my clear accept). This work truly does merge the gap between theory and practice in non-convex stochastic optimization.\n\nJust a few suggestions: I think the authors should cite and discuss the results in Defossez et al. 2019 (On the convergence of Adam and Adagrad). Also, I think Figure 1 deserves better quality. It's done in matlab so in the xlabel command you can put 'interpreter','latex' and 'fontsize',20. Finally, I spotted 1 typo: in Remark2 “cases of non-divergence cases”.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows convergence results for RMSprop in certain regimes. The reviews are uniformly positive about this paper and I recommend acceptance.
Decision: Accept (Spotlight)