A Simple Convergence Proof of Adam and Adagrad
Authors: Alexandre Défossez
Leon Bottou
Francis Bach
Nicolas Usunier
Venue: Accepted by TMLR ()

Abstract: We provide a simple proof of convergence covering both the Adam and Adagrad adaptive optimization algorithms when applied to smooth (possibly non-convex) objective functions with bounded gradients. We show that in expectation, the squared norm of the objective gradient averaged over the trajectory has an upper-bound which is explicit in the constants of the problem, parameters of the optimizer, the dimension $d$, and the total number of iterations $N$. 
This bound can be made arbitrarily small, and with the right hyper-parameters, Adam can be shown to converge with the same rate of convergence $O(d\ln(N)/\sqrt{N})$. When used with the default parameters, Adam doesn't converge, however, and just like constant step-size SGD, it moves away from the initialization point faster than
Adagrad, which might explain its practical success.
Finally, we obtain the tightest dependency on the heavy ball momentum decay rate $\beta_1$ among all previous convergence bounds for non-convex Adam and Adagrad,
improving from $O((1-\beta_1)^{-3})$ to $O((1-\beta_1)^{-1})$. 

Published in Transactions on Machine Learning Research (10/2022)
A Simple Convergence Proof of Adam and Adagrad
Alexandre Défosscz
defossez@mela. com
Meta AI
Léon Bottou
Meta Al
Francis Bach
INRIA PSL
Nicolas Usunier
Meta Al
Reviewed on OpenReview: https: openreview. net/ forum? id= 2P222STT7
Abstract
We provide simple proof of convergence covering both the Adam and Adagrad adaptive optimization algorithms when applied smooth (possibly non-convex) objective functions with bounded gradients. We show that in expectation, the squared norm of the objective gradient averaged over the trajectory has an upper-bound which is explicit in the constants of the problem, parameters of the optimizer, the dimension d, and the total number of iterations N. This bound can be made arbitrarily small, and with the right hyper- ppper-parameters, Adam can be shown to converge with the same rate of convergence with the default parameters, Adam doesn't converge, however, and just like constant step- size SGD, it moves away from the initialization point faster than Adagrad, which might explain its practical success. Finally, we obtain the tightest dependency the heavy ball momentum decay rate 31 among all previous convergence bounds for non-convex Adam and Adagrad, improving from O((1 - -B1) -3) to O((1 -1)
(Nd)(NN)/NN))) When used
1 Introduction
First-order methods with adaptive step sizes have proved useful in many fields of machine learning, be it for sparse optimization (Duchi al.) 2013), tensor factorization (Lacroix et al., 2018) or deep lcarning (Goodfel-
low et al. 2016). Duchi al. [2011) introduced Adagrad, which rescales each coordinate by sum of squared past gradient values. While Adagrad proved effective for sparse optimization (Duchi et al. (013). experiments
showed that it under-performed when applied to deep learning (Wilson et al. 2017]. RMSProp Tieleman & Hinton 2012) proposed an exponential moving average instead of a cumulative sum to solve this. Kingma & Ba 2015 developed Adam, one of the most. popular adaptive methods deep learning, built upon RMSProp
and added corrective terms the beginning of training, together with heavy-ball style momentum.
In the online convex optimization setting, Duchi al. 2011 showed that Adagrad achieves optimal regret for online convex optimization. Kingma & Ba (2015) provided similar proof for Adam when using decrcasing overall step size, although this proof was later shown to be incorrect by Reddi et al. (2018). who introduced AMSGrad as a convergent alternative. Ward el al. (2019) proved that Adagrad also converges lo a critical point for non convex objectives with a rate O(I(NN) //vN) when using a scalar adaptive step-size, instead of diagonal. Zoo al. (2019b) extended this proof to the vector case, while Zou et al. (2019a) displayed a bound for Adam, showing convergence when the decay of the exponential moving average scales 1/N and the learning rate 1/VN.

---

Published in Transactions on Machine Learning Research (10/2022)
In this paper, present simplified and unified proof of convergence to critical point for Adagrad and Adam for stochastic non-convex smooth optimization. We assume that the objective function is lower bounded, smooth and the stochastic gradients are almost surely bounded. We recover the stan- dard O(I((N)/VN) convergence rate for Adagrad for all step sizes, and the same rate with Adam with an appropriate choice of the step sizes and decay parameters, particular, Adam can converge without using the AMSGrad variant. Compared to previous work, our bound significantly improves the dependency on the momentum parameter 31. The best known bounds for Adagrad and Adam are respectively in (((1-3)) and ((11-3)) =)) (see Section 3), while our result is in O((1 =1)=²) for both algorithms. This improvement is a step toward understanding the practical efficiency of heavy-ball momentum.
Outline. The precise setting and assumptions are stated in the next section, and previous work is then described in Section X The main theorems are presented in Section E followed by a full proof for the
case without momentum in Section 5 The proof of the convergence with momentun is deferred to the supplementary material, Section
A Finally we compare our bounds with experimental results, both on toy
and real life problems in Section
2 Setup
2.1
Notation
Let d E N be the dimension of the problem (i.e. the number of parameters of the function to optimize) and take [d] (1,2.....d) Given function h Rd - R, we denote by Vh its gradient and V.h the i-th component of the gradient. We use small constant 6, e.g. 10-8, for numerical stability. Given sequence (un)nEN with Vn E N, Un E Rd, we denote Ung for E N and i E [d] the i-th component of the n-th element of the sequence.
We want to optimize a function F: Rd R. We assume there exists a random function f Rd R such that E [V]( VF(x) for all Rd, and that we have access an oracle providing i.id. samples (fr)eE We note E,,1 [+] the conditional expectation knowing fi...., fn-1- In machine learning, typically represents the weights of linear deep model, represents the loss from individual training examples or minibatches, and F is the full training objective function. The goal is to find critical point of F.
2.2 Adaptive methods
We study both Adagrad Duchi et al. 2011 and Adam (Kingına & Ba 2015) using unified formulation. We assume we have 0 < 32 < 1, vectors May Un In E Rd iteratively. Given xo E Rd our starting point, mo O, and vo = O, we define for all iterations n E N
B1 < 82, and non negalive sequence (un)neN= We define three
Ma, = 3mm, 1, + (ifa(En-1)
(1)
Un 82Un-111 V (Vifa(zn-))
(2)
Mn.i
Fnii In-1, On Ve Un,i
The parameter 31 is heavy-ball style momentum parameter (Polyak 1964). while B2 controls the decay rate of the per-coordinate exponential moving average of the squared gradients. Taking $1 0, B2 = 1 and = a gives Adagrad. While the original Adagrad algorithm did not include a heavy-ball-like momentum, our analysis also applies to the case 31 > 0.
Adam and its corrective terms The original Adam algorithm Kingma & Ba 2015 average, rather than a weighted sum for and i.e. uses
uses a weighed
mn, (1- 31) Σ 3 V. V. (2x-1) -1 -Bi)m...
k=
2

---

Published in Transactions on Machine Learning Research (10/2022)
We can achieve the same definition by taking Gadam includes two corrective terms account for the fact that mn and Un are biased towards 0 for the first few iterations. Those corrective terms equivalent to taking step-size on of the form
VI-3, The original Adam algorithm further
1-
1 31 On,adam = a.
(4)
VI - 32
ST
corrective torm for Vhy
corrective term for my
Those corrective terms can be seen as the normalization factors for the weighted sum given by (1 and (2)
Note that each term goes to its limit value within few times 1/(1 - B) updates (with B E (31, 92 1). which explains the (1 - ) term in 44. In the present work, we propose to drop the corrective term for may and
to keep only the one for Una thus using the alternative step size
On = a(1 a(1 B1)1 1 - B2
(5)
This simplification motivated by several observations:
By dropping either corrective terms, On becomes monotonic, which simplifies the proof.
For typical values of $1 and $2 (c.g. 0.9 and 0.999), the corrective term for m. converges to its limit value much faster than the one for Uz-
Removing the corrective term for m, is equivalent. to learning-rate warmup, which is popular in deep learning, while removing the one for un would lead to increased step size during early training. For values of B2 close to 1, this can lead to divergence in practice.
We experimentally verify in Section 6.3 that dropping the corrective term for ma has no observable effect the training process, while dropping the corrective term for U, leads to observable perturbations. In the following, we thus consider the variation of Adam obtained by taking on provided by (
2.3 Assumptions
We make three assumptions. We first assume F is bounded below by F., that is,
Va E R2d, F(x) 2 Fe.
(6)
We then assume the lo norm of the stochastic gradients is uniformly almost surely bounded, i.c. there is R 2 ve (Ve is used here to simplify the final bounds) so that
[V R Ve a.s., Va E RR,
(7)
and finally, the smoothness of the objective function, e.g., its gradient is L L-Liptchitz- with respect to the fo-nrm::
Va,y EdR,
-VF())-VF(WI) L L| vll2.
(8)
We discuss the use of assumption 7 in Section 4.2
3 Related work
Early work on adaptive methods (McMahan & Streeter 2010 Duchi et al. 2011 showed that Adagrad achieves an optimal rate of convergence of O(1/VN) for convex optimization AAgarall et al., 2009). Later, RMSProp (Tieleman & Hinton 2012) and Adam (Kingma & Ba 2015) were developed for training deep neural networks, using an exponential moving average of the past squared gradients.
Kingma & Ba (2015) offered a proof that Adam with a decreasing step size converges for convex objectives. However, the proof contained mistake spotted by Reddi al. (2018), who also gave examples of convex
3

---

Published in Transactions on Machine Learning Research (10/2022)
problems where Adam does not converge to an optimal solution. They proposed AMSGrad as convergent variant, which consisted in retaining the maximum value of the exponential moving average. When a goes to zero, AMSGrad is shown to converge in the convex and non-convex setting (Fang & Klabjan 2019 Zhou ct al.) 2018). Despite this apparent flaw in the Adam algorithm, it remains a widely popular optimizer, raising the question as to whether it converges. When 32 goes to and a to O, our results and previous work (Zou et al., 2019a) show that Adam does converge with the same rate as Adagrad. This is coherent with the counter examples of Reddi et al. (2018), because they uses a small exponential decay parameter B2 < 1/5.
The convergence of Adagrad for non-convex objectives was first tackled by Li & Orabona 2019) who proved its convergence, but under restrictive conditions (e.g., a S Lt/ The proof technique was improved by Ward et al. (2019), who showed the convergence of "scalar" Adagrad, ie., with a single learning rate, for any value of a with a rate of O(In(N//VN), Our approach builds on this work but we extend it to both Adagrad and Adam, in their coordinate-wer wise version, as used practice, while also supporting heavy-ball momentum.
The coordinale-wise version of Adagrad was also lackled by Zou et al. (2019b), offering a convergence result for Adagrad with either heavy-ball or Nesterov style momentum. We obtain the same rate for heavy-ball momentum with respect to N (i.e., O(InNN///N) parameter 31 from O((1 - 31) to (((1-3))-) Chen et al. (2019) also provided a bound for Adagrad and Adam, but without convergence guarantees for Adam for any hyper-parameter choice, and with a worse dependency on 31. Zhou et al. (2018) also cover Adagrad in the stochastic setting, however their proof technique leads to a VI/E term in their bound, typically with e=10- Finally, a convergence bound for Adam was introduced by Zou et al. (2019a). We recover the same scaling of the bound with respect a and 82. However their bound has dependency of ((( 9)) with respect to 81, while we get O(11 ((11-8)-1 significant improvement. [Shi et al. (2020) obtain similar convergence results for RMSProp and Adam when considering the random shuffling setup. They use an affine growth condition (i.e. norm of the stochastic gradient is bounded by an affine function of the norm of the deterministic gradient) instead of the boundness of the gradient, but their bound decays with the number of total epochs, not stochastic updates leading to an overall V extra term with 8 the size of the dataset. Finally, Faw el al. (2022) use the same affine growth assumption to derive high probability bounds for scalar Adagrad.
but we improve the dependence on the momentum
Non adaptive methods like SGD are also well studied in the non convex setting (Ghadimi & Lan 2013 with a convergence rate of O(1/VN) for smooth objective with bounded variance of the gradients. Unlike adaptive methods, SGD requires knowing the smoothness constant. When adding heavy-ball momentum, Yang et al. (2016) showed that the convergence bound degrades as 0((1-3)) assuming that the gradients are bounded. We apply our proof technique for momentum to SGD in the Appendix, Section B and improve this dependency (((1 - -1) Recent work by Liu al. (2020) achieves the same dependency with
weaker assumptions. Defazio 2020 provided an in-depth analysis of SGD-M with a tight Liapunov analysis.
4 Main results
For number of iterations N E No, we note TN a random index with value in NO...., N - 1}, so that
Vj EJENJ <, =] x 1 NN-1.
(9)
If 91 0, this is equivalent to sampling 7 uniformly in (O...., (0....,N-1), Tf 31 > 0, the last few 1- iterations are sampled rarely, and iterations older than few times that number are sampled almost uniformly. Our results bound the expected squared norm of the gradient at iteration T, which is standard for non convex stochastic optimization (Ghadimi & Lan 2013).
4.1 Convergence bounds
For simplicity, we first give convergence results for 3 = 0, along with a complete proof in Section 5 then provide the results with momentum, with their proofs in the Appendix, Section A.6 We also provide bound on the convergence of SGD with 0(1/(1 - 31) dependency in the Appendix, Section B.2
We
along
with its proof in Section B.4
4

---

Published in Transactions on Machine Learning Research (10/2022)
No heavy-ball momentum
Theorem 1 (Convergence of Adagrad without momentum). Given the assumptions from Section 2.3 the iterates In defined in Section 2.2 with hoperr-parameters verifying B2 = 1, = a with > 0 and B1 = 0, and r defined by ( we have for any N N
2R F( F. B |VF
VN (4dR² + adRL) In 1 NR
(10)
avN
Theorem 2 (Convergence of Adam without momentum). Given the assumptions from Section 2.3 the 8 with a > 0
iterates Vn defined in Section 2.2 with parameers verifying 0 < B2 < 1, an = =ay /a 1-07
-
T-ma
and 31 0, and defined by we have for any N N'
S 2R F(oo) F.
R²
E
N In
1+
Lm((32)
(11)
aN
(1 - B2)E
with
4dR²
adRL
E V1
B2
1 $2
With heavy-ball momentum
Theorem 3 (Convergence of Adagrad with momentum). Given the assumptions from Section 2.3 the
ilerales In defined in Section 2.2 with papper-pssumeeer verifying B2 1, On = with or >> O and 0 S 3 <
and F defined by 9 we have for any N E N such that N
P T-
[ 2RVN F(FO) F.
VN
NR
Eln 11
(12)
aN
N
E
with Ñ N
B 1-3, and,
12dR 202 1 31
E = adRL +
+
1- -1
Theorem 4 (Convergence of Adam with momentum). Given the assumptions from Section
2.3 the it-
erates Fn defined in Section 2.2 with hyper-parameters verifying 0 < B2 < 1, 0
S
B1
B2, and,
= a B1)
BT with and v defined by
9 we have for any N E N such that N >
1-81
s 22 F(xo) F. aN + E
R
N
E |F(++)1
In
1+
In(32)
(13)
N
(1
32
N
0 with Ñ - N
I-3, and
adRL(1-
12dR2 11-1//11.. 31
202dL233
(1 - B1/32)(1 (2) +
(1 3//3
B2 (1- B1/B2) -82)3/2'
4.2 Analysis of the bounds
Dependency on d. The dependency d present in previous works on coordinate wise adaptive meth- ods (Zou et al., 2019a b). Note however that R defined as the fx bound on the on the stochastic gradient, that in the case where the gradient has similar scale along all dimensions, dR would be reasonable bound for ||V fz))(? However, if many dimensions contribute little to the norm of the gradient, this would still lead to worse dependency in d that e.g. scalar Adagrad Ward et al. 2009 or SGD.
Diving into the technicalities of the proof to come, we will see in Section 5 that we apply Lemma 5.2 once per dimension. The contribution from each coordinate is mostly independent of the actual scale its gradients (as only appears in the log), so that the right hand side of the convergence bound will grow as d. In contrast, the scalar version of Adagrad (aard et al. 2019) has a single learning rate, so that Lemma 5.2 is only applied once, removing the dependency on d. However, this variant is rarely used in practice.
5

---

Published in Transactions on Machine Learning Research (10/2022)
Almost sure bound on the gradient. We chose to assume the existence of an almost sure uniform Exc bound on the gradients given by 77). This is a strong assumption, although it is weaker than the one used by Duchi et al. (2011) h for Adagrad in the convex case, where the iterates were assumned to be almost surely bounded. There exist a few real life problems that verifies this assumption, for instance logistic regression without weight penally, and with bounded inputs. It is possible instead to assurne only a uniform bound on the expected gradient Far)), as done by Ward et al. (2019) and Zou et al. (2019b). This however lead to a 4/3 2/3
bound on E [|>F(=>))l
instead of bound on E [[VF(=))) all the other terms staying the same. We provide the sketch of the proof using Hölder inequality in the Appendix, Section A.7
It is also possible to replace the bound on the gradient. with an affine growth condition, i.e. the norm of the stochastic gradient is bounded by an affine function of the norm of the expected gradient. A proof for scalar Adagrad is provided by Faw et al. (2022). Shi et al. (2020) do the same for RMSProp, however their convergence bound is decays (llog (T)/ //VT) with T the number of epoch, not the number of updates, leading to significantly less tight bound for large datasets.
Impact of heavy-ball momentum. Looking at Theorems 3 and we see that increasing B1 always deteriorates the bounds. Taking B1 0 in those theorems gives us almost exactly the bound without heavy-ball momentum from Theorems 1 and up to factor in the terms of the form dR3.
As discussed in Section 3 previous bounds for Adagrad in the non-convex setting deteriorates as (((1-3)) (Zou et al. 2019b). while bounds for Adamn deteriorates as O((1 - -2) (Zou et al. 2019a). Our unified proof for Adam and Adagrad achieves a dependency of O((1 - -B1) a significant improvement. We refer the reader to the Appendix, Section A.3 for a detailed analysis. While our dependency still contradicts the benefits of using momentum observed in practice, see Section our tighter analysis a step in the right direction.
On sampling of T Note that in 9 we sample with a lower probability the latest iterations. This can be explained by the fact that the proof technique for stochastic optimization in the non-convex case is based on the idea that for every iteration n, either V=(,,) small, or F(zn+1) will decrease by some amount. However, when introducing momentum, and espocially when taking the limit 31 + 1, the latest gradient VF(x,, has almost. no influence over Tn+1; as the momentum term updates slowly. Momentum spreads the influence of the gradients over time, and thus, it will take few updates for a gradient to have fully influenced the iterate I, and thus the value of the function F(z,). From formal point of view, the sampling weights given by 99 naturally appear as part of the proof which is presented in Section A.6
4.3 Optimal finite horizon Adam is Adagrad
Let us take closer look at the result from Theorem 2 It could seem like some quantities can explode but actually not for any reasonable values of a, B2 and N. Let us try to find the best possible rate of convergence for Adam for a finite horizon N, i.e. g E R2 such that [IVF(;,))? )[]] O(n(NNNN9) for some choice a(N) and (2().. Given that the upper bound in 411 is a sum of non-negative terms, we need each term to be of the order of In or negligible. Let us assume that this rate is achieved for a(N) and (2V).. The bound tells us that convergence can only be achieved if lim ((N) = 0 and lim (NN 1, with the limits taken for N + This molivates us to assume that there exists an asymptotic development of a(N) & N
of the syper-paramette
+ +NN-)) and of 1 1-2 (2) x N- + o(N-b) for and b positive. Thus, let us consider only the leading term in those developments, ignoring the leading constant (which is assumed to be non-zero). Let us further assume that e < R2,, we have
2R F(xo) F. Nl-a
No
--
E [VF(++)]]]
+ In
(14)
c
1- N-
6

---

Published in Transactions on Machine Learning Research (10/2022)
N-b with E AdR2Nb/2 dRLNN- Let ignore the log terms for now, and use I-N-8 N-b b for N
to get
2 2R F(xo)- F. N1-a 4 4dR dRLN dRLN
E IVF((() )1
Adding back the logarithmic term, the best rate we can obtain is O(n(NN//V)) and it is only achieved for a = 1/2 and b = 1, i.e., a = a. /vN and 32 = 1-NN.. We can see the resemblance between Adagrad on one side and Adam with a finite horizon and such parameters on the other. Indeed, an exponential moving average with parameter 32 1- - 1/N
typical averaging window length of size N, while Adagrad would be an exact average of the past N terms. In particular, the bound for Adam now becomes
E
[[F(++)]]]
S F(xo) Fr + VN (AdR² + taidRL) (In (1 (m((1
RN
+ N N-1
(15)
aIVN
which differ from 100 only by +N/(N - 1) next to the log term.
Adam and Adagrad are twins. Our analysis highlights an important fact: Adam is to Adagrad like constant step size SGD to decaying step size SGD. While Adagrad is asymptotically optimal, also leads slower decrease of the term proportional to F(x))= F., as 1/vN instead of 1/N for Adam. During the initial phase of training, it is likely that this term dominates the loss, which could explain the popularity of Adam for training deep neural networks rather than Adagrad. With its default parameters, Adam will not converge. It is however possible to choose and B2 to achieve critical point for arbitrarily small and, for known time horizon, they can be chosen to obtain the exact same bound as Adagrad.
5 Proofs for B = (no momentum)
We assume here for simplicity that 31 = 0, i..,, there no heavy-ball style momentum. Taking n E N", the recursions roduced in Section 2.2 can be simplified into
Co.i B2un 1,i + (Vifn (xn-1))²
F
(16)
In,s
= Fn-1,i - On Vetun.
Remember that recover Adagrad when on for and B2 1, while Adam be obtained taking 0 << 82 <,,00,000
1 - fz
On 01 1 A32
(17)
Throughout the proof we denote by En-1 [+] the conditional expectation with respect to fi...., fn- In particular, Øn-1 and Un-1 are deterministic knowing fi...., For all n E N', we also define in E Rd so that for all i [d].
Un, 32 En-1 (Vifh(en-1))
(18)
i.c. we replace the last gradient contribution by its expocted value conditioned on fi...., fn-1-
5.1 Technical lemmas
A problem posed by the update [6] is the correlation between the numerator and denominator. This prevents from easily computing the conditional expectation and as noted by Reddi et. al. (2018), the expected direction of update have positive dot product with the objective gradient. It is however possible to control the deviation from the descent direction, following Ward et al. (2019) with this first lemma.
Lemma 5.1 (adaptive update approximately follow a descent direction). For all n E N" and E [d], we have:
(ifa(xn-))
(V,F(In-1)) 2RE,-1
(iifa(In-1)
En-1
v,F(In-1)
> 2 Un.i
(19)
Ve Unas
+ Un.i

---

Published in Transactions on Machine Learning Research (10/2022)
Proof. We take i [d] and note G V,F(En-1): 9 Vefu(en-1), Unss and é Un,5.
Gg
Gg
Gg (veto
E
VE+
=
Rn
Vecto 1
+ Bn-1
Ve+u vc+ū
(20)
Given that I and e are independent knowing :.....:n-11. we immedialely have
Gg VE+ū
G²
En-1
(21)
VE+u
Now we need to control the size of the second term A,
= Gg
VE + UVE + 0 VE + + VE+
E, En | g²
Gg Nctove DlVC+U+ VC+
En [g
g²
A < GGgl
+GG
ve+
(e+o)VE+$
The last inequality comes from the fact that Ve + e ve+ max Vc u, Ve 8j and | [g²]
-² S
g21
En- [ g². Following Ward et al. (019)), we use the following incquality to bound x. and p.
X 20
y² 2X
AA 2, R, zy -
+
(22)
First applying
22 to with
Ve+ō
G
[ Ve + o.
E
I
Ve
obtain
G
E g 2 (E (e+ +0)
4/C+0
Given that c 2 En-1 [g2] and taking the conditional expectation, we can simplify as
G2
En-1 [ E,
En [k] v
(23)
4Ve+
ve+a 1
Given that En-11 | S Ve+ 8 and / Bn-1
[
S R, we can simplify
23
as
G
9²
E [m]
+ RE
(24)
4
c c+0
Now turning to p, use 22 with
VE +
1Ggl
g²
X
2E _E,-1
[02]
Ve+8 3
y
+ 0
we obtain
2
En [ g²
p 5
(25)
4/e + 0 E
Ve+ō + ()+
8

---

Published in Transactions on Machine Learning Research (10/2022)
Given that c+ 2 g² and taking the conditional expectation we obtain
G²
En-1
g2
E S
E
(26)
4VE+0
Ve+
0
+
which we simplify using the same argument as for 24 into
g
En-1 |p) S AVE+U
RE
(27)
[+
Notice that in 25 possibly divide by zero. It suffice to notice that if En-1 [0
0 then g² = 0 a.s.
that and 27 is still verified. Summing [2 and 27
we can bound
G²
g
En [|A|]] S
2RE
(28)
2
V
6 6
Injecting
28 and 21 into 20 finishes the proof.
Anticipating on Section 5.2 the previous Lemma gives bound on the deviation from descent direction. While for specific iteration, this deviation can take us away from descent direction, the next lemma tells us that the sum of those deviations cannot grow larger than a logarithmic term. This key insight introduced in Ward et al. 2019 is what makes the proof work.
Lemma 5.2 (sum of ratios with the denominator being the sum of past numerators). We assume we have << B2 S 1 and a nen-negative sequence (an)neN-. We define for all n N", b, = Σÿ=1 3
aj. We have
S in (+ bN (x)) 30N-Ninn6 Nn(2)).
Σ j=1 c+
(29)
Proof- Given that In is increasing, and the fact that bj > ag 0, we have for all N
a
s Inne+ by) - In(e + bi - -aj)
+ bj
= =Inee bU) - Im(e + (2bb-1)
E c bb + In
E + b c B2bj-1
In
c b
The first term forms a telescoping scries, while the sccond one bounded by - In(3)). Summing over all E [N] gives the desired result.
5.2 Proof of Adam and Adagrad without momentum
Let us take an iteration n E No, we define the update un E Rd::
Vi E [d], Un.s = Vi (In
(30)
Ve+ Ung
Adagrad. As explained in Section 2.2 we have an = a for a > 0. Using the smoothness F
S we have
a²L 2
F(x.11) S F(x.) oVF(I,)) un +
|
(31)
Taking the conditional expectation with respect to fo,-.., .n- we can apply the descent Lemma 5.1 that due to the a.s. lx bound on the gradients 77), we have for any E [d], V En, S R so that,
Notice
(V. (V.F(xn-1))
(V,F(xn-1)) 1))
(32)
2/e2 + Enat
2R
9

---

Published in Transactions on Machine Learning Research (10/2022)
This gives
a²I.)
E En [F(xn)) I F(n-11)
IVF En
(xn-1)
[2aR
En-1
[| 12]
2Ryn
Summing the previous inequality for all E [N], laking the complete expectation, and using that v gives us,
VN
N-1 Σ
+ a² L
N-1
E [[ S F(zo) 2R
(x.))
2a
Un 2
2
From there, we can bound the last sum on the right hand side using Lemma 5.2 once for each dimension. Rearranging the terms, we obtain the result of Theorem
Adam. As given by in Section 2.2 we have On av T-32
1- 8T for a
Using the smoothness of F
defined in we have
2
F(xn) S F(In-1) - On (F )"u,
U 12-
(33)
We have for any i E [d], V Uni S BV/e Ex=0 82 RV 80 that,
1-91
thanks to the a.s. loo bound on the gradients
I-3,
(1)((=)1)) a (V, (T,F(=nn)))
On 2 2/ c Un,i
(34)
2R
Taking the conditional expectation with respect to fI...., fn-1 we can apply the descent Lemma 5. and
use 34) to obtain from 33
a [V Ra
E, [F(xn)) & F(En-1)-
En-1 |lum 12
2R
Given that 32 < 1, we have an S complete expectation yields
Summing the previous inequality for all n E [N] and taking the
V1-
E [[
a
Σ
(IVF( + (v==R
E
2aR
a²L
N
E
2R
2(1
32)
n=0
Applying Lemma
5.2 for each dimension and rearranging the terms finishes the proof of Theorem 2
6
Experiments
On Figure I compare the effective dependency of the average squared norm of the gradient in the parameters a, 31 and Bn for Adam, when used on toy task and CIFAR-10.
6.1 Setup
Toy problem. In order to support the bounds presented in Section 4 in particular the dependency in B2, we test Adam on specifically crafted toy problem. We take E IR and define for all i E [6], P: 10m We take (Qi)ke0)) Bernoulli variables with PP (Q; = = Pt- We then define f for all x E Rdd as
Q
f(z)
Σ (1 Q.) Huber(x; 1) Huber( + 1), (E(6]
(35)
p
with for all y E R,
Huber(y) = =
v² 2
when |g| 1
[gl otherwise.
10

---

Published in Transactions on Machine Learning Research (10/2022)
109
10-1
P [ FV+()))
10a
10-2
10-3
10
81
10a
82
10-5
10-5
10-1 10-3 10
10 100
10-0 5
10
10-3
10-2 2 10-1
100
Parameter
Parameter
(a) Average squared norm of the gradient on loy task, see Section G for more details. For the a and B2 curves, we initialize close to the optimum to make the Fo F. term negligible.
(b) Average squared norm of the gradient of small convolutional model Gitman Ginsburg (2017) trained on CIFAR-10, with random mitialization. The full gradient is evaluated every epoch.
Figure 1: Observed average squared norm of the objective gradients after fixed number of iterations when varying a single parameter out of a, 1- 31 and 1 32, on a toy task (left, 10t iterations) and on CIFAR-10 (right, 600 epochs with batch size 128). All curves averaged over runs, error bars negligible except for small values of CIFAR-10. See Section 0 for details.
All corrections
Dropping correction for ma
Dropping correction for ea
100
100
Cross. Entropy
10
10-1
10
50
100
50
100
50
100
Epoch
Epoch
Epoch
12 (xxn)) P
10
10
10a
400600
300 AOWANN
100
10"
X00BXXXX
500000 WWW
10-1
10-1
10-1
* 400
100
100
100
Epoch
Epoch
Epoch
Figure Training trajectories for varying values of a (10-4,10-3), 81 E {0., 0,,,0,5,88888 0.8.0,0,8 and 32 {0.9, 0.99. 0.999, 0.9999}. The top row (resp. bottom) gives the training loss (resp. squared norm of the expected gradient). The left column column drops the corrective term my (equivalent to proof setup), and the right column drops the corrective term on e.- We notice a limited impact when dropping the corrective term on m,, but dropping the corrective term on has a much stronger impact.
all corrective terms in the original Adam algorithm, the middle
Intuitively, each coordinate pointing most of the time towards but exceptionally towards -1 with a weight of 1/ /Pi. Those rare events happens less and less often increase, but with increasing weight.
11

---

Published in Transactions on Machine Learning Research (10/2022)
Those weights are chosen that all the coordinates of the gradient have the same variance It is necessary to take different probabilities for each coordinate. If we use the same p for all, we observe phase transition when 1 1 B2 R but not the continuous improvement we obtain on Figure Ia
We plot the variation of E [1+()=)] after 10 iterations with batch size when varying either a, 1 Pr or -- through range of 13 values uniformly spaced in log-scale between 10-6 and 1. When varying a, we take 31 0 and 82- - 1 10-6, When varying B1, we take a = 10 and B2 - 10-6 (i.e. 82 is that we are in the Adagrad-Iig like regime). Finally, when varying 32, we take 81 0 and
10 We start from To close to the optimum by running first 10 iterations with = 10-1, then 10s iterations with
a == 10- always with B2 = 1 - 10-6. This allows to have F(zo) - F_ ~ 0 in [11 and (3) and focus on the second part of both bounds. All curves are averaged over three runs. Error bars are plotted but not visible in log-log scale.
CIFAR-10. We train a simple convolutional network Giitman & Ginsburg 2017 on the CIEAR-10 image classification dataset. Starting from a random initialization, we train the model on a single V100 for 600 epochs with a batch size of 128, evaluating the full training gradient after each epoch. This a proxy for E [[(=)))))) which would be to costly to evaluate exactly. All runs use the default config = 10-3, 82 = 0.999 and 31 0.9, and we then change one of the parameter.
We take a from a uniform range in log-space between 10-6 and 10-2 with 9 values, for 1- 31 the range is from 10- to 0.3 with values, and for 1- 32, from 10 to 10-1 with 11 values. Unlike for the toy problem, we do not initialize close to the optimum, we are not at a critical point. All curves are averaged over three runs. Error bars are plotted but not visible in log-log scale, except for large values of a.
even after 600 epochs, the norm of the gradients indicates that
6.2 Analysis
Toy problem. Looking at Figure La we observe a continual improvement as 32 increases. Fitting a linear regression in log-log scale of V >B with respect to - 33 gives slope of 0.56 which compatible with our bound [11, in particular the dependency in O(1/VI- B2). As we initialize close to the optimum, small step size a yields as expected the best performance. Doing the same regression in log-log scale, we find a slope of 0.87, which is again compatible with the O(a) dependency of the second term in (II). Finally, we observe a limited impact of $1, except when 1 - 31 is small. The regression in log-log scale gives a slope of -0.16, while our bound predicts a slope of -1.
CIFAR 10. Let us now turn to Figure lb As we start from random weights for this problem, we observe that a large step size gives the best performance, although we observe a high variance for the largest a. This indicates that training bocomes unstable for large a, which is not predicted by the theory. This is likely a consequence of the bounded gradient assumption (7) not being verified for deep neural networks. We observe a small improvement as 1- .2 decreases, although nowhere near what we observed on our toy problem. Finally, we observe sweet spot for the momentum B1, not predicted by our theory. We conjecture that this is due to the variance reduction effect of momentum (averaging of the gradients over multiple mini-batches, while the weights have not moved so much as to invalidate past information).
6.3 Impact of the Adam corrective terms
Using the same experimental sctup on CIFAR-10, we compare the impact of removing either of the corrective
term of the original Adam algorithm [Kingma & Ba 2015), as discussed in Section 2.2 We ran a cartesian
product of training for 100 epochs, with 81 E (0, 0.5, 0.8, 0.9, 0.99), B2 E {0.9, 0.99, 0.999, 0.9999), and E {10-4,10 10-33. We report both the training loss and norm of the expected gradient on Figure 2 We notice limited difference when dropping the corrective term on ma, but dropping the term 2n has an
We deviate from the a.s. bounded gradient assumption for this experiment, see Scction 4.2 for a discussion on a.s. bound v8 bound in expectation. httpss//www.. cs. toronto. cetesseeeddurrrrreee wtti///fazz//a..aaet html
12

---

Published in Transactions on Machine Learning Research (10/2022)
important impact on the training trajectories. This confirm motivation for simplifying the proof by removing the corrective term on the momentum.
7
Conclusion
We provide simple proof on the convergence of Adam and Adagrad without heavy-ball style momentum. Our analysis highlights link between the two algorithms: with right the syper-paramcters, Adam converges like Adagrad. The exlension to heavy-ball unmentun is more complex, but we significantly improve the dependence on the momentum parameter for Adam, Adagrad, as well as SGD. We exhibit a toy problem where the dependency on and 32 experimentally matches our prediction. However, we do not predict the practical interest of momentum, so that improvements to the proof are needed for future work.
Broader Impact Statement
The present theoretical results on the optimization of non convex losses a stochastic scttings impact our understanding of the training of deep neural network. It might allow a deeper understanding of neural network training dynamics and thus reinforce any existing deep learning applications. There would be however no direct possible negative impact to society.
References
Alckh Agarwal, Martin Wainwright, Peter Bartlett, and Pradeep Ravikumar. Information-thcorete lower bounds on the oracle complexity of convex optimization. In Advances in Neurol Information Pro- cessing Systems, 2009.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class Adam-type algorithms for non-convex optimization. In International Conference on Learning Representations, 2019.
Aaron Defazio. Momentum via primal averaging: Theoretical insights and learning rate schedules for non- convex optimization. arXiv preprint arXim:2010.00400 2020.
John Duchi, Flad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(Jul), 2011.
John Duchi, Michael Jordan, and Brendan McMahan. Estimation, optimization, and parallelism when data sparse. In Advances in Neural Information Processing Systems 26, 2013.
Biyi Fang and Diego Klabjan. Convergence analyses of online adam algorithm in convex setting and two-layer relu neural network. arXiv preprint arxiv:1905. 09356, 2019.
Matthew Faw, Isidoros Tziotis, Constantine Caramanis, Aryan Mokhtari, Sanjay Shakkottai, and Rachel Ward. The power of adaptivity in sgd: Self-tuning step sizes with unbounded gradients and affine variance. Po-Ling Loh and Maxim Raginsky (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, Proccodings of Machine Learning Research. PMLR, 2022.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4), 2013.
Igor Gitman and Boris Ginsburg. Comparison of batch normalization and weight normalization algorithms for the large-scale image classification. arXio preprint NKi::10090081.. 2017.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proc. of the Interna- tional Conference on Learning Representations (ICLR), 2015.
Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. Xiv preprint Now:1806.07297, 2018.
13

---

Published in Transactions on Machine Learning Research (10/2022)
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In AT Stats, 2019.
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momen- tum. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Newral Information Processing Systems, volume 33, pp. 18261-18271. Curran Associates, Inc., 2020. URL https: pdf
//proceedings.neus httppppccii.sa..r.ppppppppaaapap
H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. In COLT, 2010.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. USSR Compulational Mathematics and Mathematical Physics, 4(5), 1964.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In Proc. of the International Conference on Learning Representations (ICLR), 2018.
Naichen Shi, Dawei Li, Mingyi Hong, and Ruoyu Sun. Rmsprop converges with proper eyper-parameter International Conference Learning Representations, 2020.
T. Tieleman and G. Hinton. Lecture 6.5 rmsprop. COURSERA: Neural Networks for Machine Learning, 2012.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex land- scapes. In International Conference on Machine Learning, 2019.
Ashia C Wilson, Rebecca Roclofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Newral Information Processing Systems, 2017.
Tianbao Yang, Qihang Lin, and Zhe Li. Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization. arXiv preprint (XXi::664.00220 2016.
Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXie:1808. 1808.06110 2018.
Fangyu Zou, Li Shen, Zequn Jic, Weizhong Zhang, and Wei Liu. A sufficient condition for convergences of Adam and RMSprop. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019a.
Fengyu Zou, Li Shen, Zenqun Jie, Ju Sun, and Wei Liu, Weighted Adagrad with unified momentum. arXiv preprint ar arXiv: 1 1888 09408, 2019b.
14

---

Published in Transactions on Machine Learning Research (10/2022)
Supplementary material for A Simple Convergence Proof of Adam and Adagrad
Overview
In Section we detail the results for the convergence of Adam and Adagrad with heavy-ball momentum. For overview of the contributions of our proof technique, Section A.4
Then in Section we show how our technique also applies to SGD and improves its dependency in $1 compared with previous work by Yang et al. (2016), from - to O(1 - --) The proof is simpler than for Adam/ Adagrad, and show the generality of our technique.
A Convergence of adaptive methods with heavy-ball momentum
A.1 Setup and notations
We recall the dynamic system introduced in Section 2.3 In the rest of this section, we take an iteration n E N and when needed, e [d] refers to a specific coordinate. Given 20 E Rd our starting point, me = 0, and Up 0, we define
Mn.i 81mn-11 + V (in
Un.i 12 + (I
(A.1)
mm.1 = =1n-1ii Vetua..
En.i
For Adam, the step size given by
On = a0 51)1 {
(A.2)
1 - 32
For Adagrad (potentially extended with heavy-ball momentum); have B2 and
On a
(A.3)
Notice include the factor 1 - 81 in the step size rather than in A.1 this allows for clegant proof. The original Adam algorithm included compensation factors for both 81 and B2 (Kingma & Ba 2015) to correct the initial scale of m and which are initialized at O. Adam would be exactly recovered by replacing A.2) with
1 1
3
1 -
33
On 1 37
(A.4)
1 32
However, the denominator 1 1- potentially makes (ax)nEN~ non monotonic, which complicates the proof. Thus, we instead replace the denominator by its limit value for -0000. This has little practical impact (i) early iterates are noisy because is averaged over small number of gradients, making smaller step can be more stable, (ii) for 31 = 0.9 (Kingma & Ba 2015) iterations.
A.2 differs from [A.4] only for the first 50
Throughout the proof we note En- [|] the conditional expectation with respect to fi....,f In particular, In-1, Un-1 deterministic knowing f fn-1. We introduce
G, VF(2n-1) and I. (fn(
(A.5)
Like in Section 5.2 we introduce the update un E Rdd as well as the update without heavy-ball momentum
Un Rd:
Un.
Mn. and Uns VE Un.
go.i
(A.6)
VE Unii
15

---

Published in Transactions on Machine Learning Research (10/2022)
For any & N with & < n, we define Eng Rd by
Bn.k, = un + Bn-k-1
Σ
32
9j
(A.7)
j=n-k+1
T.e. the contribution from the k last gradients are replaced by their expected value for know values of fn...,fn-k-1 For h = 1, we recover the same definition as in 18
A.2 Results
For any total number of iterations N N", we define TN random index with value in fo, , N 1), verifying
Vj EN (.AJ<N,P((T=-
8
(A.8)
If 31 0, this is equivalent to sampling t uniformly in fo...., N 1}. If 31 > O, the last few I- iterations are sampled rarely, and all iterations older than a few times that number are sampled almost uniformly. We bound the expected squared norm of the total gradient at iteration т, which is standard for non convex stochastic optimization (Ghadimi & Lan 2013).
Note that like in previous works, the bound worsen as 31 increases, with dependency of the form O((1 (1)-1). This is significant improvement over the existing bound for Adagrad with heavy-ball momentum, which scales as (1 (1-33)) 3:)-3 [Zou et al. 2019b), or the best known bound for Adam which scales as (1 - 31)-
Zou et al. 2019a
Technical lemmas to prove the following theorems are introduced in Section A.5 while the proof of Theorems and are provided in Section A.6
Theorem 3 (Convergence of Adagrad with momentum). Given the assumptions from Section 2.3 the
iterates In defined in Section 2.2 with
verifying 32 1, an a with a > 0 and 0 B
1,
and F defined by 9 we have for any N E N" such that N
8g I-3,
& 2RVN F(Zo) F. VN aÑ
NR
[IFF(E))1
E'n In 1+
(12)
N
with Ñ N I-3,
B
and,
E = adRL 12dR 1- 31
2a 2d2dL2 31
+
31
Theorem 4 (Convergence of Adam with momentum). Given the assumptions from Section erales In defined Section 2. with Haper-parametery verifying 0 < B2 < 1, O S
2.3 the it-
B
B2 and,
O₂ a0 - B1lv 1-
1 with a 0, and v defined by (9) we have for any N E N" such that N >
I I-
E [IVF(E))))]
s 2R aÑ + E
F(xo) F. In 1+
R²
In(82)
(13)
(1 - 82)
N
with N =
1-31 and
81
adRL(1 31)
12dR2 11- 31
20²dL233
+
(1 - B1/32)(1 :2)
(1 - 31/32 1 B2 (1- (1) - 3/2
A.3 Analysis of the results with momentum
First notice that taking 31 + in Theorems and we almost recover the same result as stated in and
only losing the term Rd which becomes 1
16

---

Published in Transactions on Machine Learning Research (10/2022)
Simplified expressions with momentum Assuming N typical values of B1 and B2 KKnggma & Ba 2015), it is possible to simplify the bound for Adam 13 as
1-8 and 31/32 B1, which is verified for
A
2 2R F(oo)
Fx
E [+F
aN
1- ( +
[dRRL
12dR
20
(~ In 1+
(1+
R²
)
In((2))
(A.9)
(1 31)vi - 32
(1) B2)
e(1 B2)
Similarly, if we assume N
91
simplify the bound for Adagrad (??)
I-31
F(oo) F. avN
12dR
2a 2d²
NR
[FF(,)) 2 2R
adRL + 1- 31
1
(A.10)
VN
B1
Optimal finite horizon Adam is still Adagrad We can perform the same finite horizon analysis as in Section 4.3 we take = VN and $2 = 1/N, then A.9 simplifies to
E [VF(x+))
& 2R
F(oo) F.
1 VN
12dR 20 (adRL= +
+1). (A.11) In 1 N +
NR²
avN
3 1 31
The term 12- in the denominator in (A.9) is indeed compensated by the a² in the numerator and we again recover the proper In(N)//N convergence rate, which matches (A.10) up a +1 term next to the log.
A.4 Overview of the proof, contributions and limitations
There is a number of steps to the proof. First we derive a Lemma similar in spirit to the descent Lemma 5.1 There are two differences: first, when computing the dot product between the current expected gradient and each past gradient contained in the momentum, we have to re-center the expected gradient to its values the past, using the smoothness assumption. Besides, we now have decorrelate more terms between the numerator and denominator, as the numerator contains not only the latest gradient but decaying sum of the past ones. We similarly extend Lemma. 5.2 support momentum specific terms. The rest of the proof follows mostly in Section 5 except with few more manipulation to regroup the gradient terms coming from different iterations.
Compared with previous work (Zou et al. 2019b a), the re-centering of past gradients in A.14 is a key aspect to improve the dependency in B1, with a small price to pay using the smoothness of which is compensated by the introduction of extra GR,,,, in (A.I). Then, a tight handling of the different sunmations as well the the introduction of a non uniform sampling of the iterates (A.8), which naturally arises when grouping the different terms in A..49). allow to obtain the overall improved dependency in O - D(11-11)11 B1)=1).
The same technique can be applied to SGD, the proof becoming simpler as there is no correlation bet the step size and the gradient estimate, see Section B If you want to better understand the handling of momentum without the added complexity adaptive mothods, we recommend starting with this proof.
A limitation of the proof technique that we do not show that heavy-ball momentum can lead a variance reduction of the update. Either more powerful probabilistic results, or extra regularity assumptions could allow to further improve worst case bounds of the variance of the update, which in turn might lead to bound with improvement when using heavy-ball momentum.
A.5 Technical lemmas
We first need an updated version of 5.1 that includes momentum.
Lemma A.1 (Adaptive update with momentum approximately follows a descent direction). Given xo Rdd the ilerates defined by the system A.1 for (ay)jers that is non-decreasing, and under the conditions
17

---

Published in Transactions on Machine Learning Research (10/2022)
and
8
well as S 31 < B2 1,
have for all iterations No,
G -.
E
G n
Mm,
2
B
Ri
V
Unai
<VE
Bn,k+1,
[d] k=0
2 L
V1 -
B1
Un Σ Bivk
3R
vk
+
Un
(A.12)
4R
VI-
31
k=
Proof.
We use multiple times
22 in this proof, which repeat here for convenience,
A x
y²
YA 0, R. zy
(A.13)
2X
Let us take an iteration n E No for the duration of the proof. We have
Σ
Gnd
Mn.i
B Gn,
In-k.i
V
Uni
Ve+ + Un
sE|d]
iE|d] k=0
B Gn-
In-k,s
sf (Gn,s - Gn-kad In-k,i
(A.14)
V Uni
vc + Ungd
EE|
k=0
(E(d]
B
Let us now take an index 0 S k < n - 1. We show that the contribution of past gradients Gn-k and 9n-k due to the heavy-ball momentum can be controlled thanks to the decay term Bf. Let us first have a look at B. Using A.13 with
3 2R / +1 I = 1Gn Gn-kill 1
9nn-kil
Ve + Unn
we have
31
RVk + -2-k.s
BB|
<
8k
(Gn,i- - Gn-k,i) +
(A.15)
4Rvk+1
v1 - B1 + Uni
*E|d]
K=
Notice first that for any dimension e [d], c Un, 2 e 3 Un- 2 3 (E + Un-k,)), so that
Pn
<
U2
U2
(A.16)
c + Ct
B
Besides, using the L-smoothness of F given by ( we have
||,, - Gn
I L
||
|
In
k
k
= 2
an
Un
1=1
k
< 0 T,2k
Unn |nn 11
(A.17)
using Jensen inequality and the fact that an is non-decreasing, Injecting A.16 and A.17 into obtain
A. 1.15)
we
カ-1
2
k
B k
B
<
VI
313
Un
12
+
Vk
+
4R
B1
B2
k=0
L2
R
3
1
81
B/VK
+
Vk
+++1
1nn
(A.18)
4R
11
32
k=1
k=0
18

---

Published in Transactions on Machine Learning Research (10/2022)
Now going back to the A term in A.14). we will study the main term of the summation, i.c. for i E [d] and k < n
V Vifn-a ((n--(((nx-1)) vc + Un
E
k.-k. Gn- k,d
E VC + Un
V.F(5n-
(A.19)
Notice that could almost apply Lemma 5.1 it, except that we have Unii in the denominator instead of Un-k,i- Thus we will need to extend the proof to decorrelate more terms. We will further drop indices in the rest of the proof, noting G = Gn-k,i, = In-k.i i kn, and == Un Finally, let us note
8²
Σ
22 2 9z
and y2 En -- [89)
(A.20)
j=n
In particular have 8 p2
82. With notations, we rewrite (A.19)
E
G
g
E
G
GGg
VE+U Ve+o)
1
1
Ve
t
VC + 0
-2-
G 9
E k-1
+Gg Vctove+ u(VC+ VC++)
Vc+ūj
G2
p2 2-6 8²
+ E
Gg
(A.21)
Ve + 0
1c+ove - ilv++U U + vc 0
We first focus on C::
22 Vc + vie 8)
8
|C| $ |Ggl
+ +Gg
(e+ v)
due to the fact that Ve+ ( V u and |r2 - 821 2 Applying
A.13) to K with
I 3 B +
G
1g| 12 VE+iVe+o
A
y
VE+U
wC obtain
G
1
g2r4
K S
VI- (c+ ()
Given that 6 2 and taking the conditional expectation, we can simplify as
g²
E, En [ 4VE+U
(A.22)
VI- 3i Ve +
c c+e
v
Now turning to p, we use A.13 with
VI -
BIVE
|G8
[g
2r
Vc +
c+
we obtain
C 82
1
2
'28²
P
(A.23)
1
VI 31 v 2)
19

---

Published in Transactions on Machine Learning Research (10/2022)
Given that e c+ v 2 8², and kn
82 = 1, we obtain after taking the conditional expectation,
p
G
g²
E. En-k-1 [p]s 4 V1 31 vc E
(A.24)
+
Notice that in A.2) A.23
we possibly divide by zero. It suffice to notice that if p² 0 then 8² = - a.s. s0 that
and A.24 is still verified. Summing A.22 and A 24),
we gel.
G2
2
2
g2
En & 2V++U
En
(A.25)
VI- 31 VEE
c+
Given that & Ve+ 0 by definition of 8, and that using 7 indices we had dropped
r S vk IR, we have reintroducing the 3
B k-1 1 [||]] S 2 Unk+1.
Ga
2R
Vk + kBm
kn
(A.26)
VT
11
+ Un.
Taking the complete expectation and using that by definition e + Un + B in k, 2 (e + Un un-k,)) we gel
E
[[[]]
S
1 E
Ga-ki
+
2R
Vk
1E
nn- k
(A.27)
2
VVE++
Un.k+i.
v1
313
ak
E Un-kii
Injecting A.27
into A.21
gives
A
E
E
Gh-
bi
1 E
Gz-
2R
Vk 1E
-n-
1)
VE + Un,
VVE+ Un,ker
VT 3135
c + Un-
k=0
1
B
G G
2R
31
Vk: + 1E
[
(A.28)
2
VC Bn,k+1,
VI
8g
iE(d]
k=
iEld
R=
Injecting A.28 and A.18
into
A.14 finishes the proof.
Similarly, we will need an updated version of 5.2
Lemma A.2 (sum ratios of the square of a decayed sum and a decayed sum of square). We assume we have 0 < 82 I and 0 < 31 < B2, and a sequence of real numbers (an)neN.. We define by, Σラ= 1n-100 0g and On ΣØ= 88 3 az.
aj. Then we have
Σ
1
In 1+ bn bm
In 1n(22)
(A.29)
bj (1 31)(1 31/32)
Proof.
Now let us take j E No j S n, we have using Jensen inequality
G3
3
aj
31
that
3
b
B
e+
6
1=1
Note that we do need the almost sure bound the gradient, and a bound R. [[T would be sufficient..
20

---

Published in Transactions on Machine Learning Research (10/2022)
Given that for 1 E [5], we have by definition e by 2 c
32-1b1
bi
(e+
bi), get
B1
j-l
dj
(A.30)
E bj
1-
31
82
E
1=1
Thus, when summing over all j E [n], we get
Σ 1=1
B1
3
6 bi
j=1
1=1
1
2
j-1
1 B1
32
1
n
d
(A.31)
(1 - B1)(1- - 331/32)
6 E bj
Applying Lemma 5.2 we obtain (A.29)
We also need two technical lemmas on the sum of series. Lemma A.3 (sum of geometric term times a square root). Given 0 < a < 1 and E N, we have,
Q-1
Σ
a' Va
1
1+
5 (1 - a)3/2
(A.32)
2/ (n)a)
Proof. We first need to study the following integral:
|
eln(a)r
dr
2/ dr then introducing y Vz.
2
J
In(a)y? dy
then introducing u /n2
2/2 du
a
VT
dr
(A.33)
2/x
3V-n((a)
where we used the classical integral of the standard Gaussian density function. Let us now introduce Aq:
Q-1
Aq
Σ
ad
V9
4=
then we have
Q-1
Q
AQ Aq-aAq
Σ
V 9 + 1
Σ
/q
then using the concavity of V
9=0
m=1
Q-1 Σ
$1 Ω Q
2
S1+
dx
2
V
(1 51 +
2 2 In
21

---

Published in Transactions on Machine Learning Research (10/2022)
where we used (A.33). Given that V- In(a)
vI-a obtain A.32]
Lemma A.4 (sum of geometric term times roughly power 3/2). Given 0 <a < 1 and Q N, we have,
Q-1
4a
a
V + +1) 5 (1 a1-o)
(A.34)
-=0
Proof. Let us introduce Ag:
Q-1
Aq Σ
a V + 1),
-=
then we have
Q-1
Q
AQ aAo
Σ
a 19 +1) Σ
a V 1q
4=0
9=1
Q-1
a / (4 + 1) -
a V (19 + 1) -1)
Q-1
2
Σ
a V4
Q-2
2a
a"
[V+++ +1
then using Lemma A.3
9=0
4a
(1 (1- a1-a)AQ= 5
(1 [1-)33/2
A.6 Proof of Adam and Adagrad with momentum
Common part of the proof Let us a take an itcration n E N Using the smoothnoss of F defined
we have
a 2
F(x,) S F(In-1) an Ghu un +
|ua 1
Taking the full expectation and using Lemma A.1
E [F(a)) s E
(x
(In-
an 2
Ga
+
a L
E
en
2 + Bnndiiidd
(E(d) k=0
T3 2
vi 31
n-1
12
n-1
3 V
3a,
n-1
V || -
(A.35)
4R
--- Bi
Br
Notice that because of the bound on the lo norm of the stochastic gradients at the iterates 7 we have for
any &e E N, l < and any coordinate i E [d], V SnL+II & RR Eグ=0 83 Introducing Ω,
Σド= 3/.
22

---

Published in Transactions on Machine Learning Research (10/2022)
we have
[F((n))] S &B[F [F(
On
B [|
+ anL E
|
2
a V1 - B1 4R
30, R
12-1 1
B1 k
2
Σ k=1
8ivk
+
vk+
1
11
(A.36)
v1 B1
B2
k=0
Now summing over all iterations E [N] for N E N", and using that for both Adam A.2 and Adagrad an is non-decreasing, as well the fact that F is bounded below by F. from we get
A.3
az I F. +
|IG
S F(xo)
E
|
2
2R
n=1
k==
3 L
V
31
N
E
1un- 112
B Vi +
30 n R
N
B k
Vk
+
1E
[ 11]]
(A.37)
4R
B2
k=l
k=U
First looking at B, we have using Lemma A.2
B
of L 2(1- 31) - 31
Σ In (1+
uN:t)
N log(32))
(A.38)
c
iE|d
Then looking at C and introducing the change of index j -
L2
C
VI
Σ
ViV
4R
a 2
V1
31
E
|1us| 12
Σ
3/Vk
4R
1=1
kmn
L2y
V1 31 Σ
E
Σ
3/ Σ1
4R
3 L22
V1 - 31
Σ
E
[115)12
3\VK(++1)
4R
a 1 N
B1 (1 82)
|| 11
(A.39)
R
using Lemma Finally, using Lemma
A.2
we get
L2
C
Σ In (1
N Nlog(32))
(A.40)
R(1
(1)
811B2)
vE[d]
23

---

Published in Transactions on Machine Learning Research (10/2022)
Finally, introducing the same change of index j
k for D, we get
31 ==
30N R
N
B1
n-j
Vl+n-jE
jB
|111122
B2
n=
30 R
N
N
81 n-j
E
|1
Σ
VI+n-1 j
V1 B1
$2
/=1
n=)
N
60 R
E2
|105112
(A.41)
v1 $1
(1 31/B2)3/21
/=1
using Lemma
A.3
Finally, using Lemma 5.2
or equivalently Lemma A.2
with B1 = 0, we get
D V1 - 311 (1-
6
Σ iE(d
In (1+ ONs N NIn(33))
(A.42)
3/2
This is as far as we can get without having to use the specific form of ow given by either A.2 for Adam or A.3 for Adagrad. We will now split the proof for either algorithm.
Adam For Adam, using A.2 we have an = (1 - 31) Thus, we can simplify the A term from AA.37
also using the usual change of index j = k, get
N
A
1
On
E
||
2R
a(1
31)
N
N
E
G
Σ 8
2R
N
||G;16]]
2R
N
N-j+1
E
VF
( 1)13
2R
j=1
N-1
Σ
(1
(A.43)
2R
1=0
If we now introduce 7 as in A.8
we can first notice that
1- 3
B
Σ (1
- = N
3
2
N
(A.44)
1- 31
1 - 31
3=0
Introducing
B
Ñ N 1- 31
(A.45)
we then have
N
A 2
VF (1F((t))13 112
(A.46)
2R
Further notice that for any coordinate i E [d], we have UN S together
R² I-m
besides aN S a 1-8
so that putting
V1-32
A.37
A.46),
A.38
A.40
and A.42
we get
Fo
F_
E
R²
E
S 2R
In
1
-Nlog(B2)
(A.47)
aN
N
c(1 (2)
24

---

Published in Transactions on Machine Learning Research (10/2022)
with
adRL(1 - B1)
+ 2L.
12dR² vI -1
E =
+
(A.48)
B1/B2)(1 (011-11) -2) (1 (1 B2)3/2 (1 (1- 31/32)312 -1-
This conclude the proof of theorem
Adagrad For Adagrad, we have an (1 11)a,, B2
and Sn I VN so that,
N
A
Qg
31
E
||
2R
A=1
j=1
a(1 31)
N
N
E
GG
Σ
3
2R N
j=1
R=
8
8N-1t1
E
|G
2RVN N
j=l
Σ
(1-
N E
|VF
2R
N-1
a
Σ
(1
N
1) (VF(<))1
(A.49)
2R
j=0
Reusing A. A.44)
and A5.45)
from the Adam proof, and introducing t as in
we immediately have
(A.50)
2R N
Further notice that for any coordinate E [d]
we have S N R2, besides aN (1 -i)a, so that putting
together [A.37].
A.50
A.38
A.40
and A.42 with B2 = 1, we get
Fo F.
VN N
NR
E
VF
< 2RRV aN
E In 1+
(A.51)
with
2o2dL23
12dR
E = adRL +
(A.52)
1 B1
1 1- B1
This conclude the proof of thcorem
A.7 Proof variant using Hölder inequality
Following Ward et al. 2019 Zou al., 2019b). is possible to get rid of the almost sure bound on the gradient given by and replace with a bound in expectation, i.e.
Vx E Rd [[] < R Vc.
(A.53)
Note that we now need an & bound in order to properly apply the Hölder inequality hercafter:
We do not provide the full proof for the result, but point the reader to the few places where we have used
We first use it in Lemma A.1 We inject R into (A.15), which we can just replace with R. Then we use
bound and derive (.26)). Remember that defined in (A.20), and is actually a weighted sum of
the squared gradients in expectation. Thus, a bound in expectation is acceptable, and Lemma A.I is valid replacing the assumption with (A.5)..
25

---

Published in Transactions on Machine Learning Research (10/2022)
Looking at the actual proof, use ( in single place: just after AA.35 for the denominator in the following term:
in order to derive upper bound
Gh-ki k.s
On M
3
(A.54)
2
2 E +
Un,k+
[E|d] k=
Let us introduce Vo,++1 = Eie(d Un. We immediately have that
G
an
M 2
(A.55)
2
k=0
2 E +
Vnne+1
3
Taking X = |1nn=
Y= (Ve+ Ve+Vontt)
we can apply Hölder inquality as
Ve-Vnn
2 B I|
x
22
2
(A.56)
E2
which gives
E
E G x
(A.57)
Ve+ Vn,k+1
E [e+ + Vnn++1]
Ωr R
EE= 32 and using the fact that E |e EiEty Br,841. S R
with Pn
Thus we can recover almost exactly A.36 except we have to replace all terms of the form E [|IG ( =1]]]] with
The rest of the proof follows as before, with all the dependencies in a, B1, B2 remaining the E |IG..
samee
B
Non convex SGD with heavy-ball momentum
We extend the existing proof of convergence for SGD in the non convex setting to use heavy-ball momen-
tum
Ghadimi & Lan 2013). Compared with previous work on momentum for non convex SGD by Yang
et al.
2016), we improve the dependency in B1 from O((1 ((11-))) to O(11- 0(11-3)-1)). A recent work by Liu
et al.
2020) achieve similar dependency of ((1((1 -8)),, with weaker assumptions (without the bounded
gradients assumptions).
B.1
Assumptions
We reuse the notations from Scction 2.1
Note however that we use here different assumptions than We first assume F' bounded below by F., that is,
Section 2.3
Va E Rdd F(x) F.. F..
(B.1)
We then assume that the stochastic gradients have bounded variance, and that the gradients of F are uniformly bounded, i.e. there exist. R and so that
Vr TR. |VF()) R² and IE [V]())
[VF()) < <
(B.2)
and finally, the smoothness of the objective function, e.g., gradient I-Liptchitz-comtimnous with respect the norm:
Va,y Rd. VV(())
-FF())-F(()1) - [ v1l2-
(B.3)
26

---

Published in Transactions on Machine Learning Research (10/2022)
B.2 Result
Let us take a step size > 0 and heavy-ball parameter > Bi 2 0. Given Rd,, taking mo 0, we define for any iteration n E No the iterates of SGD with momentum
Mm = = V
(B.4)
Iin -nn-1 0m
Note that in B.4). the scale of the typical size of ma will increases with 81. For any total number of iterations E N" we define IN a random index with value in {o,...,N= N-..,N-11 1}, verifying
Vj JJN NT = il x 1- B
(B.5)
Theorem B.1 (Convergence of SGD with momentum). Given the assumplions from Section B.1 given T as defined B55 for a total number of iterations N 1 1-8 2o Rd a > 0, 1 > $1 2 0, and (Ta knn
given by B.
1-3 (F(zo) F.)+ s
N a + R + o
[VF
(B.6)
aN
N
- 31)
with N
A
1-31
B.3 Analysis
We can first simplify B.6.. we assume N B1, that N ze N, and,
which always the case for practical values of N and
1-3
1- 31 < a.
ab(1 + (1)( + + (F(wn) F.) 2(1 - 31)2
E IVF
(B.7)
It is possible to achieve rate of convergence of the form OLL/VN), by taking for any C > 0,
C
a a= (1 (1-31)
(B.8)
VN
which gives us
L(1 + BR)( + o²
[VF(<>))1 I
CVN CCN (F(zo) F.)+
(B.9)
VN
2(1
In comparison, Theorem 3 by Yang al. (2016) would give us, assuming now that (1- Bi) min { + JN
c
VN
min NE
E [IVF(<>>1]]
& N (F(xo) F.) max 21,
-1}
C
C L
VN (1-1-8 B1)² (3 +o? + (1-31)203)
(B.10)
We observe an overall dependency in Bn of the form 0(11 -2) for Theorem by Yang et al. (2016) which we improve O(11 (((1-1,)-)) -1)-1) with our proof.
Liu et al. 22020) achieves similar dependency in (1-11 here, but with weaker assumptions. Indeed, in their Theorem 1, their result contains term in O(1/a.) with a < (1 M for some problem dependent constant M that does not depend on 31.
Notice that as the typical size of the update m, will increase with 31, by a factor 1/(1- -1), it is convenient scale down a by the same factor, as we did with (B.8) (without loss of generality, as C' can take any value). Taking a of this form has the advantage of keeping the first term on the right hand side in (B.6) independent of B1, allowing us to focus only the second term.
27

---

Published in Transactions on Machine Learning Research (10/2022)
B.4 Proof
For all E N", note Gn = (f(xn-1) and In = (f(an-1) En-1 [1] is the conditional expectation with respect to fn-1. In particular, In-1 and Mn-1 are deterministic knowing :.....:fn-1.
Lemma B.1 (Bound on ma). Given a > 0, > 31 2 0, and (Ix) and (ma) defined as by B. under the assumptions from Section B.1 we have for all n E N
R² + 0²
E
mm
2
(B.11)
(1 31)²
Proof. Let us take an iteration n E N
E
mm
12
=
01 In
using Jensen we get,
k=D
8
B 119m~
0=
n-1
(R² + +
31
R2 + 02
(1 - B1)
Lemma B.2 (sum of geometric term times index). Given 0 <a <1 i N and Q EEN N with Q 2 i
Σ a 1 (i-ad-itiQ2 a Q-1-1
a'
a
<
(B.12)
1
(1 (1-a)²
Proof. Let A, Eq adg, we have
A; - aA; aa + Σ a (1+111)
g=it1
a)A; a'i a a
9+1
Finally, taking i = 0 and Q + gives us the upper bound. Lemma B.3 (Descent lemma). Given > 0, 1 81 2 0, and (xn) and (mn) defined as by B.4 under the assumptions from Section B.1 we have for all n E N
n
LL3 +
EF VF(In=1) mn]
Σ f [F(
(B.13)
(1- -1-31)3
Proof. For simplicity, we note Gn VF(xn-1) the expected gradient and In ff the stochastisc gradient at iteration n.
Gh mn
G fn-k
+
Σ
(Gn
Gn- 9" gn
(B.14)
0=0
1=1
28

---

Published in Transactions on Machine Learning Research (10/2022)
This last step is the main difference with previous proofs with momentum (Yang et al. 2016 the current gradient with an old gradient in order obtain extra terms of the form |G The price pay is the sccond term the right hand side but will see that it is still beneficial to perform this step. Notice that as F. is I-smooth so that we have, for all & E N"
replace
Gr, Gn- I
Σ am
1=1
S L2k
mp mp-11p 1
(B.15)
using Jensen inequality. We apply
1lv12
2
AA x.y E R. |rall2
- 2
| |12112 +
(B.16)
2A
11
with x Gn Gn-ki y = In-* and
the second lerm in B.14 and use (B115 get
kaT.
n-1
n-1
3 (1-
aLk
mm mn 2
Σ
G n
81-
1 +
m
1lan-
2
1 31
k=
Taking the full expectation we have
m.) mn)
Σ
n-1
B [G (nn=-n=a) - al
8k
((-
Bi)
Σ
m 12
I1 x 112]
Bg
k=
k=1
(B.17)
Now let take & {0, (O....,P n - 13, first notice that
E GTT k = E E, - V
F V
E VF (nn-k-1)
VF
E
G
- l
Furthermore, have E [19n~ < R x² from B.2
while E [|
<
R02 8.1
using
B.11
from
Lemma B.1 Injecting those three results in B.17 we have
n-
3k
G mm
B ||nn-
- aL + +020
(B.18)
2
3
1 - B1
A=
aL
n-1
B
||G
(R² +
Σ
stk.
(B.19)
1 B
km
Now, using B.12 from Lemma R.2 we obtain
T mn] E
Σ 3 [1Gm-
aL3I(R2 +
(B.20)
(1-B1)² B1)3
k=
which concludes the proof.
29

---

Published in Transactions on Machine Learning Research (10/2022)
Proof of Theorem B.1
Proof. Let us take specific iteration E N", Using the smoothness of F given by B.3 we have,
LLL
F(xn)= S F(In-1) a mn +
mm
(B.21)
2
Taking the expectation, and using Lemma B.3 and Lemma B.1
we get
T (R² + 0²)
aZI(R + o²)
[[F(xn) S E (F -
E n
(1-31)
2(1 2(1-31)
LL + +Bi) +
S [B(
B ||Gn~<112]
(B.22)
- 31)3
rearranging, and summing over n {l..... N), we get
ΣΣ E [IG || F B[F((NN)] +N a²L(1 (R) + +
(B.23)
2(1 B1)3
Let us focus on the term on the left-hand side first. Introducing the change of index = n k, we get
n
=
B
E
N
N
G
Σ 83
a
i=1
n=1
N
a
E
V
F (x==
(1 -N-+
1
8
E
[VF
2 (1- BN.
(B.24)
3
We recognize the unnormalized probability given by the random iterate as defined by ization constant is
B.5 The normal-
N
1- 1-3N
3N
B1 N.
Σ
1- 11--N-i-
31
2 N
1
1
81
1=0
which we can inject into B.24 to obtain
aN A
E VVF
(B.25)
31
Injecting B.25
into
B.23 and using the fact. that is bounded below by F. B.
we have
E
VF (1, |1
< - 31 (F(xo) F.) + aÑ
N NaL(1 + ( + +
(B.26)
N
2(1 - 31)
(B.27)
which concludes the proof of Thcorem
B.1
30


Reviews:
[{"review_id": "orWzm8wK4Y", "reviewer": "Reviewer_8u7Z", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n+ Recovering previous results such as convergence rate for Adam is good\n+ Common notation is useful for the community to take forward \n+ Improving tightness around $\\beta_1$ is a much needed improvement over older proofs\n+ In general proofs are well written\n\n\n\n## Weaknesses\n- The deviation from the original Adam, and simplified proofs depends on simplification of the algorithm itself.\n- Some assumptions are strong, and need to be justified in the text / as part of the proof", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a \"simple\" proof for Adam and Adagrad for smooth objective functions with bounded gradients. The link between Adam and Adagrad is shown via this proof, along with experimental results with a toy problem and CIFAR10 dataset. The paper has the potential to be impactful for researchers who are interested in proofs that are applicable to other related algorithms as well", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "-  [Minor] Without much context, factors in the abstract such as $\\beta_1$ does not make sense for most readers (have to scroll down to sec. 2.2); Better to keep the details in the main text and make the abstract lighter, or introduce in abstract for completeness as decay rates for moment estimates. \n- [Minor] hyphenate non-convex throughout (also non-adaptive)\n- [Minor] Please explain this further or repeat part of (Yang et al., 2016) here - \"improves the dependency on $1 − \\beta_1$ from $a −2$ to $a −1$\"\n- [Minor] \"rate at which the scale of past gradients is forgotten\" can be rephrased. Same comment on \"it has a slower forgetting of..\" on page 6\n- \"leads to an algorithm close to Adam\" - this is important to note, and \"for a typical $\\beta_1$ of 0.9 ... 50 iterations\", seems like a justification to simplify the proof. This is no longer Adam, but perhaps the paper can be scoped down to a proof for Adagrad. Alternatively, provide the more complicated proof for full Adam as supplementary material.\n- [Minor] References for \"Image generation, music synthesis and Language modeling\" seem like fillers. Can you simplify this paragraph? Remove unnecessary references and rephrase sentences like \"does Adam really not converge?\"\n- Would be better to show general proof, and then apply $\\beta_1 = 0$; this is just a suggestion, feel free to explain why this ordering is better for you. In fact, are theorem 3 and 4 sufficient? -- this is important to discuss on this topic - \"Taking $\\beta_1 = 0 $ in those theorems gives us **almost exactly** the bound without heavy-ball momentum from Theorems 1 and 2\"\n- recheck Lemma 5.1 for correctness\n- [Minor] \"weights are chosen so that the variances of all the coordinates of the gradient are equals1\" -- \"equal\"? fullstop?\n- Bounded gradient assumption needs more discussion. This is a very strong assumption and may not apply to most cases. In fact, this may be where your CIFAR 10 experiment varies from theory. Also, the toy problem does not add much value, can you consider another experiment? \n \n\n\n\n- ", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nuGfky98mJ", "reviewer": "Reviewer_BBkw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I think this is a strong submission which is well suited to the TMLR format.\nThe authors provide new technical results on Adam and Adagrad which will be of use to other researchers in optimization.\nI recommend that the submission be accepted.\n\n### Correctness\n\nI checked the proofs and the submission is theoretically sound as far as I am able to determine.\nAll theorems are supported by rigorous proofs which, aside from one minor issue (see specific comments below), appear to be correct.\nThe experiments are well-executed and sufficient details are provided for replication. \n\n#### Detailed Comments\n\n**Equation 13**: I don't see how obtain the last $N^{-b}$ term in this equation. \n    Substituting in the value for $\\beta_2$ gives $-\\log(1 - N^{-b})$, which, using bounds on the logarithm,\n    satisfies\n    $$N^{-b} \\leq -\\log(1 - N^{-b}) \\leq \\frac{N^{-b}}{1 - N^{-b}},$$\n    which gives the slightly worse bound of $1/(N^b - 1)$.\n    Can the authors clarify this please?\n\n**Bounds for Convex Functions**: One of the interesting aspects of these results is that they do not require a bounded diameter assumption. \n    The standard analysis for Adagrad assumes $\\sup_{x \\in \\mathcal{X}} \\|x - x^*\\|_2 \\leq D$ and then rescales the step-size by $D$ to guarantee convergence.\n    Do you think the approach here could be utilized to avoid such an assumption in a convergence proof for convex $f$? \n\n\n**Equations 4**: This choice of step-size is equivalent to choosing $m_{n} = (1 - \\beta_1) \\beta_1 m_{n-1} + (1 - \\beta_1) \\nabla_{i} f(x_n - 1)$, which is not the exponential moving average used in Adam. \n    You would need to scale as $\\beta_1 / (1 - \\beta_1)$ in Equation 1 to obtain Adam by the rescaling in Equation 4.\n    This different is most pronounced for $\\beta_1 \\approx 1$, for which scaling of $m_{n-1}$ is approximately zero in the update compared to Adam, which would use $\\beta_1$. \n    The effect is least noticeable for $\\beta_1 \\approx 1/2$, for which it is merely divided by two.\n    I think that (1) this should be clarified in the text, which currently states \"our algorithm differs from Adam only for the first 50 iterations\" and (2) can the authors please clarify the impact of this difference on the algorithm/analysis?\n\n**Effect of Bias Correction**: Again with respect to the statement \"our algorithm differs from Adam only for the first 50 iterations.\", I would like to note that this may change the entire optimization path. \n    So, it is somewhat misleading to remark on the similarity to Adam after initial iterations are complete.\n\n**Equation 8**: Can the authors remark on as to why the sampling distribution for iterates should so heavily discount the most recent iterations? \n    This is quite unintuitive to me.\n\n**Section 4.3**: In what sense is the word 'Optimal' being used here? \n    It's not clear from the discussion that the choices of $\\alpha = N^{-a}$ and $\\beta_2 = 1 - N^{-b}$ minimize the upper bound from Equation 10.\n    The choices for $a,b$ may be optimal given the form of $\\alpha$ and $\\beta_2$, but this does not imply optimality of the overall choice.\n    \n### Interest\n\nThe convergence of Adam is a topic of enduring interest to the optimization for machine learning community.\nAlthough the convergence theorems in this work are not highly novel, the short and elegant proofs for the momentum-free case are a strong contribution and I am confident this submission will be of interest to many researchers.\n\n### Strengths and Weaknesses:\n\n**Strengths**:\n- The proofs for Adam and Adagrad without momentum are simple, short, and insightful. I was interested to see that the key element is controlling the deviation from a descent direction.\n- The momentum bounds recover the bounds without momentum up to a constant factor when $\\beta_1 \\rightarrow 0$. \n- The text is generally well written with comprehensive related work.\n\n**Weaknesses**:\n- It's not clear that the version of Adam analyzed directly recovers the original formulation given by Kingma and Ba. \n- The organization of the paper sometimes uses forward references to technical lemmas/equations. \n\n\n### Minor Comments:\n\n- Page 1: \"The best know bounds for Adagrad\" --  typo.\n- Eq 6: Missing a comma here. A 'quad' between the quantification and the expression would make the expression clearly as well.\n- Section 4.2: It is awkward to discuss Lemma 5.2 before the result is introduced in the text. Such forward references should always be avoided if possible. \n- Equation 19: Missing a '+' between the two expectations.\n- A.1: Using $G_n = \\nabla F(x_{n-1})$ and $g_n = \\nabla f_n(x_{n-1})$ goes against standard notation in probability, where capital letters denote random variables and lower-case letters denote deterministic quantities.\n- Theorem A.1 and A.2: The 'thmtools' package provides a 'restatable' environment which can be used to avoid creating new theorem statements. \n- Theorem A.1 The constant was denoted $C$ in the main paper, but here it has changed to $E$.\n- A.4: Again, the forward reference to Eq. A.19 should be avoided if possible.\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission provides a new convergence analysis for the Adagrad and Adam algorithms.\nFor Adagrad and Adam without momentum, the proof is simple---less than two pages in length--and intuitive.\nThe main challenge is to control the amount any step can vary from a descent direction, which the authors do by building on theoretical tools in the literature.\nA more complex and lengthy analysis is provided for Adagrad and Adam with momentum;\nthe resulting convergence rates improve the dependence on the momentum term compared to existing results, but the rate is still slower with momentum than without. \nThe submission concludes with experiments comparing the predicted dependencies of the convergence rate on step-size and momentum parameters to empirical effects.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I think the following changes would be appropriate:\n\n1. Please clarify the connection between the variant of Adam analyzed and the original method proposed by Kingma and Ba.\n2. Try to resolve the forward references in Sections 4.2 and A.3.\n3. Clarify the use of 'optimal' in Section 4.3.", "broader_impact_concerns": "This is a theoretical paper with no specific ethical implications. The Adam and Adagrad algorithms are already widely used, so studying their convergence does not present any issues.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BMTU0xQZ4t", "reviewer": "Reviewer_yRem", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\nThe proofs are not too complicated, and streamline previous analyses to achieve the better $1-\\beta_1$ bounds. The proofs seem correct and well presented. The improved dependencies are not so surprising given the similar results in convex settings, or even with slightly different algorithms in the non-convex setting (e.g.  https://arxiv.org/pdf/2007.14294.pdf), but I think the authors are correct in noting that such dependencies have not appeared previously for these specific algorithms, which may be of interest.\n\nWeaknesses:\nThese weaknesses are more along the lines of things where the paper seems to fall short of its potential:\n\nThe Adam algorithm analyzed is not actually Adam as it removes some of the “bias correction” terms. Now, the authors state (and I intuitively agree) that these bias correction terms likely are irrelevant because they decay exponentially fast. However, since they do decay so fast, I feel that there is something missing to make the story complete: if we believe that the provided updates are nearly the same as the original updates, can we just bound the difference in these updates to obtain a bound for the original updates? If not, then perhaps it is a bit premature to claim that the bias correction does not do anything.\n\nI think a truly unified analysis would smoothly interpolate between Adagrad and Adam. As currently written, it seems there is no such smooth interpolation because a constant $\\alpha$ is forced at every round. If one instead allowed for $\\alpha = 1/\\sqrt(n)$, for example, then with $\\beta_2=1$, $\\beta_1=0$, the “Adam” algorithm would become AdaGrad (because $\\lim_{x\\to 1} \\sqrt{(1-x^n)/(1-x)} = \\sqrt{n}$, so $\\alpha_n=1$). \nHowever, even with a constant $\\alpha$, it seems like the analysis is a bit loose on this edge case: for $\\alpha = 1/\\sqrt{N}$, $\\beta_2=1$, $\\beta_1=0$, we obtain $\\alpha_n = \\sqrt{n}/\\sqrt{N}$. Now, intuitively we should expect $v_n = \\Theta(n)$ so that the algorithm is SGD with an effective learning rate set to the standard value of $O(1/\\sqrt{N})$. Thus, we should expect convergence at the optimal rates. However, the current bound appears to blow up. The remarks at the beginning of section 4.3 seem to try to address this by setting $\\beta_2=1-1/N$ and showing that this is an acceptable value. However, I find this to be actually just emphasizing the weirdness of the result: a difference of only $O(1/N)$ in $\\beta_2$ actually causes an enormous difference in the bound!\n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides analysis of a family of first-order optimization algorithms. The family is parametrized by $\\beta_1$ and $\\beta_2$, the two exponentially-weighted moving average parameters in Adam, and so includes both Adam and AdaGrad. I believe it also includes RMSProp. Theorems are provided for smooth stochastic losses that bound the sum of gradient magnitude squared in expectation. By appropriate settings of the parameters, it is possible to achieve the optimal $O(1/T^{1/4})$ convergence rate for gradient norm. Some experiments are provided to verify that the gradient indeed becomes small on certain problems.\n\nThe results tighten some dependencies on $1-\\beta_1$ from previous works, and appear to be a bit shorter and general.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "A discussion (or even better, a resolution) of the above issues would help readers see the nuances in the bounds presented in this paper.\n\nOn page 6 equation 19, I believe you mean to add rather than multiply the expectations.\n", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "leNRFEBCLt", "reviewer": "Reviewer_Z1mR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n1. **Improvements in the dependence on $\\beta_1$.** Compared to the previously best-known rates for Adagrad (Zou et al., 2019b) and Adam (Zou et al., 2019a), the rates from this paper have better dependence on momentum parameter $\\beta_1$. That is, the derived upper bounds are proportional to $O((1 - \\beta_1)^{-1})$, while the previously best-known rates have $O((1-\\beta_1)^{-3})$ (Adagrad) and $O((1-\\beta_1)^{-5})$ dependence on $\\beta_1$. Since $\\beta_1$ is typically very small in practice, the improvement is noticeable.\n\n2. **Simple proofs.** I have checked all proofs: they are correct and quite easy to understand. Each step of the proof is clearly explained and motivation why is it needed is also evident. The proofs consist of 3 stages: derivation of the lower bound for the inner product between the direction used by a method and the gradient direction (needed after application of smoothness in the proof), estimation of the sums appeared in the first lemma, and application of smoothness.\n\n3. **Observation \"Optimal finite horizon Adam is Adagrad\"**. The observation provided in Section 4.3 is very insightful. First, one can easily notice that if $\\beta_2$ is independent of $N$, then Theorem 2 and 4 establish the convergence of Adam only to some neighborhood of the solution, *which cannot be reduced via stepsize*. This fact is expected since Adam is known to be non-convergent in general, so, it is good that this phenomenon is reflected in the analysis. However, if $\\beta_2$ goes to $1$ when $N$ increases, then the issue vanishes. We know that $\\beta_2 = 1$ corresponds to Adagrad, so it is natural to expect that the bound for Adam would transform in the bound of Adagrad in this case once $\\beta_2$ is close enough to $1$. And this is true for the derived bounds: bound for Adam (almost) coincides with the bound for Adagrad when $\\beta_2 = 1 - 1/N$, where $N$ is the number of iterations. I think this is a very good property of the proposed analysis, since it reflects some basic intuition about the relation between Adagrad and Adam.\n\n4. **Clarity and structure.** The paper has a good structure and is realtively clean: I haven't found many typos or mistakes in English. This fact make the paper easily-readable.\n\n### Weaknesses \n\n1. **Bounded stochastic gradients.** The assumption from (6), i.e., uniformly bounded stochastic gradients, is quite strong, especially when the optimization problem is unconstrained. \n\n2. **Some related works are not discussed.** In particular, Defazio (2020) and Liu et al. (2020) also derive O((1-\\beta_1)^{-1}) dependence on $\\beta_1$ for momentum SGD, but they did it without assuming that $\\|F(x)\\| \\leq R$, i.e., without the bounded gradients assumption. I think, it is important to add the comparison with these works. It also would be great to discuss the differences between the analysis techniques.\n\n---\n\nReferences:\n\nDefazio, A. (2020). Momentum via primal averaging: Theoretical insights and learning rate schedules for non-convex optimization. arXiv preprint arXiv:2010.00406.\n\nLiu, Y., Gao, Y., & Yin, W. (2020). An improved analysis of stochastic gradient descent with momentum. Advances in Neural Information Processing Systems, 33, 18261-18271.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The work focuses on non-convex smooth stochastic minimization problem with bounded stochastic gradients (almost surely). In this setup, the authors propose new convergence analysis of Adagrad (with/without momentum) and Adam and derived new convergence rates $O(d\\ln(N) / \\sqrt{N})$ for both methods. Moreover, the derived rates have better dependence on the heavy-ball momentum parameter $\\beta_1$ than the previous best-known rates. As a separate contribution of this work one can emphasize the simplicity fo the proposed proofs.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "### Requests (I think, this changes are necessary)\n\n1. The discussion about the necessity of bounded stochastic gradients assumption is needed. In particular, it will be interesting to see what part of the proof significantly relies on this assumption. Maybe, some simple motivating examples (either theoretical or empricial) could illustrate this phenomenon better. Next, Zou et al. (2019a,b) use bounded second moment assumption in their results. However, they obtain a bound on $\\mathbb{E}[\\|\\nabla F(x_\\tau)\\|^{4/3}]^{2/3}$, which is weaker than the bound on $\\mathbb{E}[\\|\\nabla F(x_\\tau)\\|^{2}]$ derive in this work. The authors also point out that it is possible to derive similar results under bounded second moment assumption. Could the authors add the proof for at least one **momentum** method under this assumption? In particular, it would be interesting to confirm whether the dependence on $\\beta_1$ will remain the same or it will become as in [Zou et al., 2019a,b].\n\n2. As I mentioned in the weaknesses section, the comparison of rates for momentum SGD with the rates from [Defazio, 2020] and [Liu et al., 2020] is missing. I believe this should be added. It would be great to add the discussion of the differences between the analyses. [Next part is not a strict request, but rather a recommendation] In particular, I am curious: is it possible to modify the analysis of Momentum SGD to get rid of the bounded gradient assumption?\n\n3. In the numerical experiments, I did not get why the method does not converge for $\\beta_1 \\neq 0$ in Figure 1a: the norm of the gradient is always large. In figure 1b, it seems that the method did not reach good squared norm of the gradient.\n\n### Suggestions (I think, this suggestions may help to strengthen the paper)\n\n1. **On $O(\\cdot)$ notation.** Although the authors explicitly mention and discuss the dependence on $d$ (dimension of the problem) in the derived bounds, they do not show this dependence in the rates written using $O(\\cdot)$-notation. I think, it is worth to explicitly show this dependence in such cases. Moreover, I think that the authors could also add that $R$ is an upper bound for $\\ell_\\infty$-norm. When gradients are dense and many components are of the same size, $\\ell_\\infty$-norm is $\\sqrt{d}$-times smaller than $\\ell_2$-norm, which is typically used in the estimates. In this case, the rates are proportional to $\\sqrt{d}$, in some sense.\n\n2. As I mentioned before, assumption (6) is quite strong especially when the optimization problem is unconstrained. Therefore, the natural question arises: are the proofs generalizable to the constrained case (when one can project to the set where the problem is defined)? If yes, it would be great to generalize them. If no, it would be great to discuss this limitation and point out what part of the proof is unclear ofr the possible generalization.\n\n3. I am also curious whether it is possible to remove the logarithmic factors from the convergence guarantees for Adagrad and Adam without spoiling the rate. Could the authors add the discussion in this?\n\n4. Could the authors test Adam with the parameters used in theory vs Adam with practical default parameters recommended by Kingma & Ba (2015)? It is interesting to see, how Adam performs in practice with this parameters.\n\n5. Is it possible to extend the analysis to cover scalar version of Adagrad and Adam?\n\n### Minor comments\n\n1. If I am not mistaken, in inequality (13), the last term should be multiplied by some numerical constant (e.g., 10 is enough), since $- \\ln(1-N^{-b}) \\geq N^{-b}$.\n\n2. In inequality (14), one should have $dR^2$ instead of $dR$, right?\n\n3. In inequality (19), there should be a plus sign after the first expectation in the RHS.\n\n4. In the proof of Lemma 5.2, monotonicity of logarithm is used, not concavity, if I understand correctly.\n\n5. In inequality (30), there is extra dot after $u_n$ in the second term in RHS.\n\n6. Figure 1: how do the authors evaluate the expectation $\\mathbb{E}[\\|F(x_\\tau)\\|^2]$? Or is it the squared norm for the last iterate?\n\n7. In inequality (A.11), constant $E$ is introduced, which is already defined as $C$ in the main part of the paper.\n\n8. Typos in Appendix A.4: in the last sentence of the first paragraph: \"int (A.54)\" $\\to$ \"in (A.54)\". In the second paragraph: \"we recommand\" $\\to$ \"we recommend\"\n\n9. In the line above (A.35), one should have $b_l$ instead of $b_j$ in the end of the derivation.\n\n10. There is an extra space before the line after (B.4).\n\n11. There is an unnecessary repetition of the text after (B.5). This was explained previously in the paper.\n\n12. Theorem B.1: \"Assuming the assumptions\" -- this phrase does not sound natural.\n\n13. In the line above (B.18), the bound for the second moment of momentum should contain $\\beta_1$ instead of $\\beta_2$.", "broader_impact_concerns": "I do not have any broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper as the reviewers note provides a simple and intuitive proof for the convergence of Adam and Adagrad. As the reviewers the analysis will be useful to the community and streamlines previously existing analyses and improves the dependence on 1-beta. The reviewers raised some points and they were answered and appropriate edits were made by the authors. I recommend acceptance. 
Decision: Accept (poster)