On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
Authors: Dongruo Zhou
Jinghui Chen
Yuan Cao
Ziyan Yang
Quanquan Gu
Venue: Accepted by TMLR ()

Abstract: Adaptive gradient methods are workhorses in deep learning. However, the convergence guarantees of adaptive gradient methods for nonconvex optimization have not been thoroughly studied. In this paper, we provide a fine-grained convergence analysis for a general class of adaptive gradient methods including AMSGrad, RMSProp and AdaGrad. For smooth nonconvex functions, we prove that adaptive gradient methods in expectation converge to a first-order stationary point. Our convergence rate is better than existing results for adaptive gradient methods in terms of dimension. In addition, we also prove high probability bounds on the convergence rates of AMSGrad, RMSProp as well as AdaGrad, which have not been established before. Our analyses shed light on better understanding the mechanism behind adaptive gradient methods in optimizing nonconvex objectives.

Published in Transactions on Machine Learning Research (02/2024)
On the Convergence of Adaptive Gradient Methods for Nonconvex Optimization
Dongruo Zhou" Indiana University
dz13@iu. edu
Jinghui Chen' The Pennsyluania State Universiby
jzc591 edu
Yuan Cao* The University of Hong Kong
yuancaoGhhu.Mk
Ziyan Yang
zy47@rice. edu
Rice University
Quanquan Gu
gguBcs. ucla edu
University of California, Los Angeles
Reviewed on OpenReview: https: // opwnrevvee..........ommom net/ forum? id= Gh0cmbb a3c
Abstract
Adaptive gradient mothods are workhorses deep learning. However, the convergence guar- antees of adaptive gradient methods for nonconvex optimization have not been thoroughly studied. In this paper, provide fine-grained convergence analysis for general class of adaptive gradient methods including AMSGrad, RMSProp and AdaGrad. For smooth nonconvex functions, we prove that adaptive gradient methods in expectation converge to first-order stationary point. Our convergence rate better than existing results for adaptive gradient methods in terms dimension. In addition, we also prove high probability bounds on the convergence rates of AMSGrad, RMSProp as well as AdaGrad, which have been established before. Our analyses shed light on better understanding the mechanism behind adaptive gradient methods in optimizing nonconvex objectives.
1 Introduction
Stochastic gradient descent (SGD) (Robbins & Monro 1951 and its variants have been widely used training deep neural networks. Among those variants, adaptive gradient methods (AdaGrad) (Duchi et. al., 2011 McMahan & Streeter 2010), which scale each coordinate of the gradient by function of past gradients, can achieve better performance than vanilla SGD in practice when the gradients are sparse. An intuitive explanation for the success of AdaGrad is that it automatically adjusts the learning rate for each feature based on the partial gradient, which accelerates the convergence. However, AdaGrad was later found to demonstrate degraded performance especially cases where the loss function is nonconvex or the gradient is dense, due to rapid decay learning rate. This problem is especially exacerbated in deep learning due the huge number of optimization variables. To overcome this issue, RMSProp (Tieleman & Hinton 2012) proposed to exponential moving average rather than the arithmetic average to scale the gradient, which mitigates the rapid decay of the learning rate. Kingin & Ba 2014] proposed an adaptive momentum estimation method (Adam), which incorporates the idea of momentum (Polyak 1964 Sutskever
et al. 2013) into RMSProp. Other related algorithms include AdaDelta ZZiler 2012) and Nadam (Dzzat 2016), which combine the idea of the exponential moving average of the historical gradients, Polyak's heavy
"Equal Contribution

---

Published in Transactions on Machine Learning Research (02/2024)
Recently, by revisiting the original convergence analysis of Adam, Reddi et al. (2018) found that for some handerafted simple convex optimization problem, Adam does not even converge to the global minimizer. In order to address this convergence issue of Adam, Reddi et al. (2018) proposed a new variant of the Adam algorithm named AMSGrad, which has guaranteed convergence in the convex setting. The update rule of AMSGrad is as follows::
ball Polyak 1964) and Nesterov's accelerated gradient descent
Nesterov 2013
X++1 =
m
v== max (a-x(V.-1.V))
(1.1)
VV te
where a₁ > O is the step size, 6 is a small number to ensure numerical stability, x, E IR is the iterate in the t-th iteration, and m,, V. E Rd are the exponential moving averages of the gradient and the squared gradient at the 1-th iteration respectively:
m. = -1m + (1 (1--11) 81)g. -2 + +111++111100 (1-32)g;
(1.2)
Here 31, E [0, 1] are algorithm hyperparameters, and gr is the stochastic gradient at x
Despite the successes of adaptive gradient methods for training deep neural networks, the convergence guarantees for these algorithms are mostly restricted to online convex optimization (Duchi et al.) 2011:
Kingma & Ba 2014 Reddi et al. 2018). Therefore, there is huge gap between existing online convex optimization guarantees for adaptive gradient methods and the empirical successes of adaptive gradient methods in nonconvex optimization. In order to bridge this gap, there are a few recent attempts to prove the nonconvex optimization guarantecs for adaptive gradient methods. More specifically, [asu et al. (2018) proved the convergence rate RMSProp and Adam when using deterministic gradient rather than stochastic gradient. Li Orabonal (2018) proved the convergence rate of AdaGrad, assuming the gradient is L--iischitz
continuous. Ward et al. (2018) proved the convergence rate of AdaGrad-Norma where the moving average of the norms of the gradient vectors is used to adjust the gradient vector in both deterministic and stochastic settings for smooth nonconvex functions. Nevertheless, the convergence guarantees in Basu et al. (2018) Ward et al. (2018) are still limited to simplified algorithms. Another attempt to obtain the convergence rate under stochastic setting is prompted recently by Zou & Shen (2018), in which they only focus on the condition when the momentum vanishes. Chen et al. (2018a) studies the convergence properties of adaptive gradient methods in the nonconvex sotting, however, dimension d. Défossez et al. 2020)) proves the convergence of Adam and Adagrad in nonconvex smooth optimization under the assumption of almost sure uniform bound on the L norm of the gradients. In this paper, we provide fine-grained convergence analysis of the adaptive gradient methods. In particular, we analyze several representative adaptive gradient methods, i.c., AMSGrad (Reddi et al. 2018 which fixed the non-convergence issue in Adam and the RMSProp (fixed version via (Reddi el al. 2018 ) and prove its convergence rate for smooth nonconvex objective functions in the stochastic optimization setting, Morcover, existing thcoretical guarantees for adaptive gradicnt methods are mostly bounds in expectation over the randomness of stochastic gradients, and are therefore only on-average convergence guarantees. In practice, however, the optimization algorithm is usually only run once, and therefore the performance cannot be guaranteed by the in-expectation bounds. To deal with this problem, we also provide high probability convergence rates for AMSGrad and RMSProp, which can characterize the performance of the algorithms on a single run.
convergence rate has quadratic dependency on the problem
1.1 Our Contributions
The main contributions of our work are as follows:
With slight abuse of notation, here we denote by vv: the clement-wisc square root of the vector ve, mi/ the element- wise division between mi and /vt, and 1 v.) the element-wise maximum between Vt-1 and v.. We denote by &? the wlement-wise square the vector gt.
2

---

Published in Transactions on Machine Learning Research (02/2024)
We prove that the convergence rate of AMSGrad to stationary point for stochastic nonconvex optimization is
o
d/
7)
(1.3)
73/1-0/2
when 1g1. S T. Here g1:T, = 92,i.-. 9r, with {gt) being the stochastic gradi-
ents satisfying | I ae. and $ E [0, 1/2] is a parameter that characterizes the growth rate of the cumulative stochastic gradient g1:7,
Our result implies that the worst case (i.e., 1/2) convergence rate for AMSGrad is
d d (v
which has a better dependence on the dimension d and T than the convergence rate proved in Chen et al. [2018a), i.e.
O log T + dd
VT
We also establish high probability bounds for adaptive gradient methods. To the best of our knowl- edge, it is the first high probability convergence guarantees for AMSGrad and RMSProp for non- convex stochastic optimization.
Notations: scalars are denoted by lower case letters, vectors by lower case bold face letters, and matrices by upper case bold face letters. For a vector x = [a,]] E Rd, we denote the lp norm (p 2 1) x by 1/p the lo norm of by ||x||>> max For a sequence of vectors {g:);- we denote by Ijs the i-th element in gj. We also denote gi.e, = [g .t, With slightly abuse of notation, for any two vectors a and b, we denote a² as the element wise square, a" as the element wise power operation, a/b as the element-we
||x||p
division and max(a, b) as the element-wise maximum. For a matrix A = [A E Rdxd, we define || 11.1 = Enj= Asy and ||A|] 00000 = max AAgl- Given two sequences {an} and {bn), we write O₂ = O(b,,) ) if there exists a constant 0 < C < too such that an S Cb.. We use notation ((-) to hide logarithmic factors.
2 Related Work
Here review other related work that is not covered before.
Adaptive gradient methods: Mukkamala & Hein (2017) proposed SC-Adagrad and SC-RMSprop, which derives logarithmic regret bounds for strongly convex functions. Chen et al. (2018b) proposed SADAGRAD
for solving stochastic strongly convex optimization and more generally stochastic convex optimization that satisfics the second order growth condition. Zaheer et al. (2018) studied the effect of adaptive denominator constant and minibatch size in the convergence of adaptive gradient methods. Zou el. al. (2019) presented an easy-to-check sufficient condition guarantee the convergences of Adam and AMSGrad in the non-
convex stochastic sctting. Chen al. (2020) proposed partially adaptive gradient method and proved its convergence in nonconvex setlings. Alacaoglu el al. (2020) proposed a new framework to derive data-
dependent regret bounds with a constant momentum parameter in various settings.
Nonconvex Stochastic Optimization: Ghadimi & Lan 2013 proposed a randomized stochastic gradient
(RSG) method, and proved its O(I/VT) convergence rate to a stationary point. Ghadimi & Lan (2016) proposed an randomized stochastic accelerated gradient (RSAG) method, which achieves O(1/T + o² P/TT) convergence rate, where o² is an upper bound on the variance of the stochastic gradient. Motivated by
3To be precise, T4 Orabona 2020 studies delayed AdaGrad algorithm with momentum.
3

---

Published in Transactions on Machine Learning Research (02/2024)
Table 1: Comparison of convergence rate of AMSGrad and AdaGrad in terms of the convergence types and assumptions by different works in the nonconvex smooth setting. Here T denotes the total number of iterations and d is the dimension.
Conv. Rate
Conv. Type
Assumptions
AMSGrad
Chen et al. (2018a)
O
log T+
in-expectation
smoothness, bounded gradient
VT
Alacaoglu al. (2020)
log T vT
in-expectation
smoothness, bounded gradient
Ours (worst case, i.e., 8 8= 1/2)
0
d +
d P
in-expectation
smoothness, bounded gradient
Ours (worst case, i.c., s = 1/2)
+
high probability
smoothness, bounded gradient, fx(, Gaussian vector
Vf(x) a sub-
AdaGrad
Défossez et al. (2020)
in-expectation
smoothness, bounded gradient
T
vT
Li & Orabona 3
0
high probability
smoothness,
[V)((x,)
v fx)]ll is sub- Gaussia
Ours (worst case, i.c., s = 1/2)
0
V
+ T
in-expectation
smoothness, bounded gradient
Ours (worst case, i.e., 1/2)
V 4 44)
high probability
smoothness, bounded gradient, fx(,
Vʃ(x) sub-
Gaussian vector
the success of stochastic momentum methods in deep learning (Sutskever et al, 2013 Yang et al. (2016) provided a unified convergence analysis for both stochastic heavy-ball method and the stochastic variant of Nesterov's 's accelerated gradient meth and proved O(1/VT) convergence rate to a stat stationary point for smooth nonconvex functions, Reddi et al. (2016); Allen- Zhu & Hazan 2016)) proposed variants of stochastic
variance-reducee gradient (SVRG) method (Johnson & Zhang 2013) that provably faster than gradient descent in the nonconvex finite-sum setting. Lei et al. (2017) proposed stochastically controlled stochas- tie gradient (SCSG), which further improves convergence rate of SVRG for finite-sum smooth nonconvex optinization. Recently, Zhou et al. (2018) proposed new algorithm called stochastic nested variance- reduced gradient (SNVRG), which achieves strictly better gradient complexity than both SVRG and SCSG for finite-sum and stochastic smooth nonconvex optimization.
There are only a few works on the high probability convergence results. Kakade & Tewari (2009) proved high probability bounds for the PEGASOS algorithun via Freeman's inequality. Harvey al. (2019a b) proved convergence bounds for non-smooth, strongly convex case via generalized Freeman's 's incquality. Jainn et al. (2019) makes the last itcrate of SGD information theorctically optimal by providing a high probability bound. Li & Orabonal 2020) presented high probability analysis for Delayed AdaGrad algorithm with momentum in the smooth nonconvex setting.
High Probability Bounds:
For the case of comparison, we summarize the convergence rates of adaptive gradient mothods derived in different works in Table [ along with the convergence types and corresponding assumptions.
3 Algorithms
We mainly consider the following three algorithms: AMSGrad (Reddi al.) 2018), a corrected version of RMSProp (Tileman & Hinton 2012 Reddi al.] 2018 and AdaGrad (Duchi et al. 2011).
4

---

Published in Transactions on Machine Learning Research (02/2024)
Algorithm AMSGrad (Reddi et al. 2018
Require: Initial point X1, step size {ar (o adaptive gradient parameters 31, 32, I: <- 0, Vo <- 0, Vo < 0
2: for = 1 to 1' do
3: g: = (x,,,
4: m, = 6 + (1 31)
Vt = 82V1-1 (1 g2
V. max (V-- V1)
7: X++1 = ar V, 1/2
mr with V, = diag( +e)
8: end for
Ensure: Choose Xout from {x.). 2 < with probability at-1/ Σ Os.
The AMSGrad algorithm is originally proposed by Reddi et al. (0018) to fix the non-convergence issue in the original Adam optimizer {Kingma & Ba 2014). Specifically, in Algorithm | the effective learning rate of AMSGrad is ag V. 1/2 where V, = (V.), while in original Adam, the effective learning rate is a V, where V. (v.) This choice of effective learning rate guarantees that it is non-increasing and thus fix the possible convergence issue. In Algorithm [ present variant of RMSProp (Tieleman & Hinton 2012 (adding the max step according to Reddi et al. (018)) where the effective learning rate is also set as 04 1/2
Algorithm 2 R.SPrrp (Tieleman & Hinton 2012) (modified according to Reddi et al. (2018)
Require: Initial point X1, step size (ox:)== adaptive gradient parameters 3,e.
1: Vo +- 0, Vo <-
2: for = 1 to T' do
3: g: Ex(
V. fi:-1 + 31-3 g)g?
V. max mV.xVVi-1, V.)
6: X++1 = at V. 1/2
ge with V, diag(V, +
7: end for
Ensure: Choose Xout from {x,}, 2 < ( < with probability a/-1/ El= Og..
Algorithm 3 AdaGrad (Duchi et al. 2011
Require: Initial point X1, step size (o.) adaplive gradient parameter e.
1: Vo+ +0
2: for = 1 to T do
g: (x(( Et)
V. 7 gi
5: Xe+1 = Xt. a4 1/2
ge with V, = diag(V, +)
6: end for
Ensurc: Choose Xout from {x,], 2 < < with probability at-1/ ΣT-1 0s.
In Algorithm 3 we further present the AdaGrad algorithm (Duchi al. 2011). 1), which adopts the summation
of past stochastic gradient squares instead of the running average compute the effective learning rate.
4 Convergence Results in Expectation
In this section, we present main results the convergence of AMSGrad, RMSProp and AdaGrad. We study the following stochastic nonconvex optimization problem
min f(x) = [x)] XERd
5

---

Published in Transactions on Machine Learning Research (02/2024)
where & is random variable satisfying certain distribution, f(x; {) R R is L-smooth nonconvex function. Tn the stochastic setting, one cannot directly access the full gradient of f(x). Instead, one can only get unbiased estimators of the gradient of f(x), which is ()( This setting has been studied in
Ghadimi & Lan 2013 2016
Assumption 4.1 (Bounded Gradient) f(x) - (x;( has Go -bounded slochaslic gradient. That is, for any &, we assume that || (x: <c Goo.
Tt is worth mentioning that Assumption 4.1 is slightly weaker than the b--boundenness assumption [Vx(x s G2 used in Reddi et al. (2016 Chen et al. (018a)) Since fx: I [VV S v [x: <o,, the fz-boundedness assumption implies Assumption 4.1 with Gx G2. Meanwhile, G.
will be tighter than G2 by factor of vd when each coordinate of V v almost equals to each other.
Assumption 4.2 (L-smooth) f(x) = (x;{) is L-smooth: for any x,y E TRdd we have
[(() - fly) (Vf(y), v) 5 x- -
L
Assumption 4.2 is standard assumption in the analysis of gradient-based algorithms. It is equivalent to the L-gradient Lipschitz condition, which is often written |V((() ffy))ll S L||x yyl2- We are now ready to present our main result.
Theorem 4.3 (AMSGrad) Suppose 31 < 3/ a4 = and ||gıT, Go for == 1, ..... T,O S
1/2. Then under Assumptions 4.1 and 4.2 the iterates xt of AMSGrad satisfy that
Mi
M2d
aM3d
(4.1)
Ta
T1/2-8"
where {Mi}i= are defined as follows:
202 (Goo + 1112
M1 = 2(Gx + VO)
M2 =
+ 2G +Vo)
1- B1
2LG (Go0 vc)
2,37
M3 = 2//2 -
1 1 - 31
2/2 (2)(113))2/43
122
and A = [(x1) infx f(x).
Note that in Theorem 4.3 we have condition that |ggIT < 7.. Here characterizes the growth rate of g1:7,,, i..,, the cumulative stochastic gradient (Liu et al. 2019). In the worse case where the stochastic gradients are not sparse, we have = 1/2, while in practice when the stochastic gradients are sparse, we have & < 1/2.
Remark 4.4 If choose 0 -1 then 4.1
implies that AMSGrad achieves
d//2
T//4- x/2
T
convergence rate. In the worst case when s = 1/2, this result matches the convergence rate of noncoreer SGD Ghadimi Lan 2016). For the dimension dependence, is nol direclly comparable since they made a different stochastic noise assumption (they assumed the stochastic gradient is a-sub w.r.t. the lo norm of the gradient). By directly translating their assumption to ours (to replace with VdG we can obtoin /d/T dominant term in their convergence result, which matches convergence rate. Note that Chen et al. 2018a)) also provided a similar bound for AMSGrad that
1
-0(108
=0 log T + d2
E [[]((
T
VT
6

---

Published in Transactions on Machine Learning Research (02/2024)
It can be seen that the dependence of in their bound is quadratic, which is worse than the linear dependence suggested by 4..1p. A recent. work (Défossez et al., 2020) discussed the convergence issue of Adam by showing that the bound consists of a constant term and does not converye to zero. In comparison, our result for AMSGrad does not have such a constant term and converges to zero in a rate O(d //////////-//3)) This suggests that the converyence issue of Adamm is indeed fixed in AMSGmd.
Corollary 4.5 (A variant of RMSPropp Under the same conditions of Theorem 4.3 if as a and |g & T for t T,0 S 1/2, then the iterates Xt of RMSProp sotisfy that
1
Σ
T
B[IVf(x011]
M1
M2d
aMyd
Ta
T
T1/2-8²
where (M)).- defined as follows:
(G Vc)
M1 2G + Vo)a, M2 2G (G + 1/24 2G (Gx + Vo), M3
11/2 -8)1/2
and - /(xi) - inf f(x).
Corollary 4.6 (AdaGrad) Under the same condilions of Theorem 4.3 if ag = a and ||gIT, S G
,T, 2.00$ L...
1/2, then the the iterates Xx of AdaGrad satisfy that
T
M
M2d
aM3d
Σ
[((Vf(x))1
+
+
T
Ta
T
T1/2-8²
where {M:) defined as follows:
Mi >( + VO)A, M₂ 20 (G 1012 3Go((os Vo), M3 6l. voje
and = f(x)) infx fl (xx).
Corollaries 4.5 and 1.6 imply that RMSProp and AdaGrad achieve the same rate of convergence AMSGrad. In worst case where 1/2, both algorithms achieve O d/T d/T) convergence rate, which matches the convergences rate of nonconvex SGD given by Ghadimi & Lan 20166
Remark 4.7 Défosses et al. 2020 gave bound O(a 112-1/1-111-1 + aa)dT-11/2) for AdaGrad, which gives the following rate
VT
VT
when a = 1. Our result gives a faster rate in terms of the dependency in dimension d.
5 Convergence Results with High Probability
In the previous section, we provide convergence results the three adaptive gradient methods in expectation. These bounds can only guarantee the average performance of a large number of trials of the algorithm, but cannot rule out extremely bad solutions. What's more, for practical applications such as training deep neural networks, we often perform single run of the algorithm since the training time be fairly large. Hence, it is helpful to get high probability bounds which guarantee the performance of the algorithın on single run. To overcome this limitation, in this section, we further establish high probability bounds on the convergence rate for AMSGrad, RMSProp and AdaGrad. We make the following additional assumption.
Assumption 5.1 The stochastic gradients are sub- Gaussian random vectors Jin et al. 2019
[e|exp((v, (x(x v)(x))) < exp([lv|220//)
for all d and all x.

---

Published in Transactions on Machine Learning Research (02/2024)
Assumption 5.1 is commonly considered when studying high probability bounds Li & Orabona, 2020 It
is weaker than Assumption B2 in Li & Orabona [2020]: for the case when {x) Vx(x) is standard Gaussian vector, o² defined in Li & Orabona (2020) is of order O(d), while o² O in our definition.
Theorem 5.2 (AMSGrad) Suppose B1 < 8242, O4 S 2 and
gitT,ll2 & Go for i
I,.... T,0 < S 1/2. Then for any 5 > O, under Assumptions 4.1
4.2
and
5.1 with probability at least
8, the iterates x, of AMSGrad satisfy that
T
M1
M2d
aMad
Σ t=2
(5.1)
Ta
T
71/2-8²
where (M:) are defined as follows:
Mi = 4(G + vE)A + C" + log(2/)),
M2 4G2 + vC)c-112
+ (G + Ve).
1- B1
4LG (Goo + (E)
(1+ 2,9
M3 c1/2(1 f2) - -B1/322
1 1-
and = f(xi) -inf f(x).
Remark 5.3 Simillur to the discussion in Remark 4.4 can choose @(d1/2T1//40//2) -1 to achieve an O(d"/2/T3/4--0 d/T) convergence rate.
We also have the following corollaries providing the high probability bounds for RMSProp and AdaGrad.
Corollary 5.4 (A variant of RMSProp) Under the same conditions of Theorem 5.2 if = a S o 2022 and ||ghT,ll2 S T for == 1,..., T,O S 8 S 1/2, then for any 0, with probability least - 6, the iterates X2 of RMSProf satisfy that
Mi
M2d
aMad T1/2-5²
(5.2)
T-1 t=
Ta
T
where (M)) defined as follows:
M1 4(G + VOA C" + v log(2/8),
M2 4G2 + Vi)c 1/2 +4G
M3 4LGoo (Goo + Vt)
e1/ - /)
and - f(x)) infx f(x).
Corollary 5.5 (AdaGrad) Under the same conditions of Theorem 5.2 if a 50 and llgiT S Go for t= 1...., T,0 s s 1/2, then for any 0, with probability at least 1 - 6, the iterates of AdaGrad satisfy
T
Mi Ta
M2d
aM3d 71/2-8
(5.3)
T
t=
where { are defined as follows:
Mi (Goo + ve)(4A + C' Colog(2/6))
M2 (G + v 4Goo),
4Lo + Ve)
M3 e1/2
and A f(x)) infx f(x).
8

---

Published in Transactions on Machine Learning Research (02/2024)
6 Proof Sketch of the Main Results
In this section, we provide proof sketch of Theorem 4.3 and Theorem 5.2 and the complete proofs as well as proofs for other corollaries and technical lemmas can be found in the supplemental materials. Compared with the analysis of standard stochastic gradient descent, the main difficulty of analyzing the convergence rate of adaptive gradient methods caused by the stochastic momentum m, and adaptive stochastic gradient
v. 1/2 V-1/2 gr. To address this challenge, following Yang et. al. 2016), we define an auxiliary sequence 2,: let
Xo = X1, and for each t 2 1,
B1 1 81
B1 31
24 = X
+
(x+
x,-1)
1 31 x
Xt-1-
(6.1)
The following lemmn shows that Ze+1 Ze can be represented by m,, gr and V.1/2 This indicates that by considering the sequence {zr}: it is possible to analyze algorithms which include stochastic momentum, such as AMSGrad.
Lemma 6.1 Let ze be defined in
6. Then for t 2 2, we have the following expression for Zt+1 Zt.
B1
- (a, V, (2) -1 (xt-1 - x,) - -a, V. g1.
2t+1
Zt
1 31
We can also represent 2++1
2z as the following:
31
V-1/2
ar 1/2
m -0, -O,V 1/22 gr.
2+41 24
(4-
31
For =1, 1, we have Z2 2 01 V
1/2
g1.
With Lemma 6.1 we have the following two lemmas giving upper bounds for ||z+1 zell2 and l V/(xx)ll2, which useful for the proof of the main theorem.
Lemma 6.2 Let ze be defined in 6.1 For 2 we have
z
Zell2 S | V 1/2 g: 2 1 31
31
|x-- x2
Lemma 6.3 Let ze be defined in 6.1 For 2 2, we have
[[z) - vf(x))ll2 - L (1 (1 ) -|xx - x1-1
B1)
We also need the following lemma to bound [V](()) Veloo and |mollooo Basically, it shows that these quantities can be bounded by Goe.
Lemma 6.4 Let Ve and m, be as defined in Algorithmm Goo, l| S G2 and || Goo.
Then under Assumplion 4.1 we have [x))) S
Lastly, we need the following lemma that provides upper bounds on IIV- specifically, it shows that we can bound | 1/2
1/2 my llz and V
1/2 gg l2.2..
More
f--//2mila mill2 and |V gillz with Σ |gg.r,ll.- The bound of
||V. 1/2 mill is essential for to obtain tighter dependency in terms of d.
Lemma 6.5 Let B1, B2 be the weight parameters, Qit, = 1....,T be the step sizes in Algorithm denote 7 = 31/3/ ///222 Suppose that a4 a and 7 S 1, then under Assumplion 4.1 we have the following two results:
We
71/2 - - 1/2 mlll 2e1/2 1/2 7) s=1 a
2
Σ
1grr.ll22
9

---

Published in Transactions on Machine Learning Research (02/2024)
and
a 2e2/2(1 1/)1/2(1 7) i=1
1/2 8:
1=1
With all lemmas provided above, now we are ready to provide the proof of Theorem 4.3
Proof [Proof Sketch of Theorem 4.3 Since f is L-smooth, have:
f(z(+1) & f(z)) + f((z)) (Ze+1 zr) + L |z zel12
L
=f(zz) + Vx(x)) (Z++1 z,) + (Vf(z)) vf(xx)) (Z++1 21)
21+1
2:l12.
(6.2)
1.
In the following, we bound I, 12 and I3 separately. Bounding term I We can prove that when / = 1,
vx(x)) (z2 - 21) = -V((x) an V. gi.
(6.3)
For / 1 2, by Lemma 6.1 can prove the following result:
V fx() [zt+1 2,) S 11 B1 Poo
ff(x)) aa-1111 Vo-1V,1' V gr.
(6.4)
Bounding term I;: For 2 1, by Lemma 6.1 and Lemma 6.2 we can prove that
(Vf(z.) - vf(xx)) (Ze41 - 2,) 2.) S a
a. 1/2
8il12
2L
31
) ||x, x.-1
(6.5)
1- B1
Bounding term I3: For 2 by Lemma 6.1 have
L
B1 )²
2:12 < L a, V,
1/2
gel12
2L
1- B1 ||x x2133
(6.6)
2
Now we get back to
6.2
1, We provide upper bounds of 6.2 for = and t > separately. For t = 6.6 into 6.. laking expectation and rearranging terms, we have
substituting 6.3
6.5
and
E[f(z2) f(z) & Ga + 27. 1/
1/2 gi
(6.7)
For / 122 2, substituting 6.4
6.5 and 6.6 into 6.2
laking expectation and rearranging terms, have
E (((et)) +
Go Goollor l,, 1/2
E ((2x) +
G2
04 1
V
B1
31
< E - a
f(xx
+ -1 + 20 V. 1/2
gel1
4L
B1
) 11oe- V/ m m- 11]
(6.8)
1 - 31
where the inequality holds due to the fact ff(x,)
1V=1/v((x,)) > (Gor + (V) by Lemma 6.4 Rearranging it, we have
We now telescope 6.8 for i to T, and add it with 6.7
(Goc + V
Σ
E (x:))
O
<
A
20
0.1 1/2d
+ day Go
+ 2T.
E ar V
1/2
8:112
g:
+4T
31
Σ
T
E
0r
1-1
1/2
m:
[|2]
1 81
1 B1
t=1
(6.9)
10

---

Published in Transactions on Machine Learning Research (02/2024)
By using Lemma 6.5 we can further bound Σi= Bllar V. 1/2 Be and Σ Eller V. 1/2 mm 1 in
6.9 with
Ea a12, which turns out to be
2 2/0 G GGo + v()c-1/20 1/2d 11 - 2(G + +V)++ T
1
+ dG vQ)
B (xout)
Ta
1-
x + Lo
E
Σ (Buzzlll))
(1+2 -0-2(1111))
))) 1-31/ 31
31 11
(6.10)
1/22 7) 32)1/2
Finally, rearranging 6.10 and adopting the theorem condition that llg.T,ll22 S Tx, we obtain
Mj Ta
+ M2d + aM3d
E [
71/2-0'
where {M) are defined in Theorem 4.3 This completes the proof.
Remark 6.6 We highlight here why we can achieve lighter dimension dependency (d/vT U.S. vd/vT) compared with Défossez et al. (2020). Both our analysis and the one in Défossez et al. (2020) required to upper bound the gradient norm V (x(u)) 11 by the stochastic gradients gr and momentum m. (see our (69) and (A.19) in Défossez et al. (2020). However, Défossez et al. (2020) bounded m, and g: separately as suggested by (A.20) in Défossez et al. (2020), and they obtained better bound for my, which depends on a² and worse bound for ge, which has an a" dependency. Thus, the final bound in their result suffers from an a²d + = Odd) dependency (see the second and third term in (A.54) in Défossez el al. (2020). To compare with, we bound both my and gr. by Ei=1 |guT, uniformly by using Lemma 6.5 which makes our final bound only has an a' dependency (see the third term in (6.10)). Therefore, by optimizing a, our final bound only depends on vd rather than d.
We then show the proof sketch for high probability result, i.e, Theorem
4.3
Proof [Proof Sketch of Theorem 5.2 Following the same procedure as in the proof for Theorem 4.3 until
6.6 For t = 1, substituting
6.3
6.5 and 6.6 into 6..2. rearranging terms, we have
f (z2)
f())) S do G. 2L||a V 1/2 gi 12
(6.11)
For t 2 2, substituting
6.4
6.5
and 6.6 into 6.2 rearranging terins, we have
1/2
G2 04-1 l1.11
f(2(41) +
1.1
f(z)) +
B1
1- 31
(
B1 )²
< - T 0411 1-1 g: + 2L V 1/2
1/2
gi
1|2 + +4L
m
(6.12)
1 B1
We now telescope 6.12 for = to T and add it with 6.11
Rearranging it, we have
a V/(x)
V
1-1
< +
G ajt a1t 1122d
+ don + 2L
Σ oo V.
T
1/2
g:
1
+ 4L
B1
2 T
ao
V
1/2
m; ||-
(6.13)
1- 31
1
B1
1/2 Now consider the filtration F, = off...... Et). Since x; and v-1 only depend on E f..... . f by Assump tion 5.1 and martingale concentration argument, we obtain
Σ
a ()(x) V Σ Va(V 1/
5
a V (x:) log(2/6))
(6.14)
11

---

Published in Transactions on Machine Learning Research (02/2024)
By using Lemma
6.5 and substituting 6.14 into 6.13 we have
T
Σ 04 [)(x)
V /
Go a2a11111 0,- 11/2d
T
L
d
A
+ +dan - 02
Σ
Σ 1
1 -
21/2(1 - Bz) 1/22122111 7)
1=2
==1
B1 (1 C'log(2/8) + (1
/TT B1)
Σ 1g.
1- cl/2 32) //(112(1111 7)
Moreover, by Lemma 6.4 we have (xxx) 1 V((x) 2 (Goo ve) and therefore by
choosing a₁ aso c/2 and rearranging terms, we have
T
+ + vo.
4G 4G2 + /0c--1/2
1/2
T + 4G (G + V2) d T
d
A
T
Ta
1- 31
4(Gxx + Vc)La
d
C' + vc) log(2/22/))
Σ
ggrr,ll2 +
e1/2(1 - B2) 1/2 7)T
Ta
7m1
1- (1-1))
81 ) 8(Gx + vE) - 31)
1/2 - 32)212211 - 7)71/2 ()////1 Σ 1g1.
(6.15)
where O' is an absolute constant. Finally, rearranging 6.15 and adopting the condition ||guT,lle S To gives T
Mi
M2d aMad
fxx))
+
Ta
T
T1/2-s²
2=2
where {M are defined in Theorem 5.2 This completes the proof.
7 Conclusion
In this paper, provided a fine-grained analysis of general class of adaptive gradient methods, and proved their convergence rates for smooth nonconvex optimization. Our results provide faster convergence rates of AMSGrad and the corrected version of RMSProp as well as AdaGrad for smooth nonconvex optimization compared with previous works. In addition, we also prove high probability bounds on the convergence rates of AMSGrad and RMSProp as well as AdaGrad, which have not been established before.
Acknowledgments
We thank Yiqi Tang for his valuable discussions and preparation of this work. We thank the anonymous reviewers for their helpful comments. This research was sponsored in part by the National Science Foundation CAREER. Award IIS-1906169, BIGDATA IIS- 1855099 and IIS-2008981. We also thank AWS for providing cloud computing credits associated with the NSF BIGDATA award. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.
References
Ahmet Alacaoglu, Yura Malitsky, Panayotis Mertikopoulos, and Volkan Cevher. new regret analysis for adam-type algorithms. In International Conference Machine Learning, pp. 222-210. PMLR, 2020.
12

---

Published in Transactions on Machine Learning Research (02/2024)
Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In International Conference on Machine Learning, pp. 199-707, 2016.
Amitabh Basu, Soham De, Anirbit Mukherjee, and Enayal Ullah. Convergence guarantees for rmsprop and adam in non-convex optimization and their comparison to nesterov acceleration on autoencoders. arXiv preprint arXiv:1807.06760 2018.
Jinghui Chen, Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. Closing the generaliza- tion gap of adaptive gradient methods in training deep neural networks. In International Joinl Conferences on Artificial Intelligence, 2020.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong, On the convergence of a class of adam-type algorithms for nonconvex optimization. arXiv preprint Xiv: Xrivv1880..0241, 2018a.
Zaiyi Chen, Yi Xu, Enhong Chen, and Tianbao Yang. Sadagrad: Strongly adaptive stochastic gradient methods. In International Conference on Machine Learning, pp. 913-921, 2018b.
Alexandre Défossez, Léon Bottou, Francis Bach, and Nicolas Usunier. On the convergence of adam and adagrad. arXiv preprint arXiv:2003. 02395, 2020.
Timothy Dozal. Incorporating nesterov momentum into adam. 2016.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 22(Jul): 2159,, 2011.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341 2368, 2013.
Saced Ghadimi and Guanghui Lan. Accelerated gradient methods for nonconvex nonlinear and stochastic programming, Mathematical Programming, 156(1-2):59 99, 2016.
Nicholas JA Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analysos for non-smooth stochastic gradient descent. In Conference on Learning Theory, pp. 1579 1613. PMLR, 2019a.
Nicholas JA Harvey, Christopher Liaw, and Sikander Randhawa. Simple and optimal high-probability bounds for strongly-convex stochastic gradient descent. arXiv preprint Xrx: Kit:1909 1909. 00843, 2019b.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. Tn ECCV, pp. 630 645. Springer, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 988):1735-1788) 1997.
Prateck Jain, Dheeraj Nagaraj, and Pranecth Netrapalli. Making the last iterate of sgd information theo- retically optimal. orXiv preprint arXiv: 194444444,,,4, 2019.
Chi Jin, Pranceth Netrapalli, Rong Ge, Sham M Kakade, and Michael Jordan. A short note on concentration inequalities for random vectors with subgaussian norm. arXie preprint 1xx::1902.0377 2019.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Aduances in neural information processing systems, pp. 315-323, 2013.
Sham M Kakade and Ambuj Tewari. On the generalization ability of online strongly convex programming algorithms. In Advances in Neural Information Processing Systems, pp. 801 808, 2009.
Diederik P Kingma and Jimmy Ba. arXivo1412, 6980, 2014.
Adam: A method for stochastic optimization. arXiv preprint
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite-sum optimization via sesg methods. In Advances in Neural Information Processing Systems, pp. 2345 2355, 2017.
13

---

Published in Transactions on Machine Learning Research (02/2024)
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. arXiv preprint. ar arxi::805..00 14, 2018.
Xiaoyu Li and Francesco Orabona. A high probability analysis of adaptive sgd with momentum. arXiv preprint or Xiv:2000 14294, 2020.
Mingrui Liu, Youssef Mroueh, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, and Tianbao Yang. To- wards better understanding of adaptive gradient algorithms in generative adversarial nets, arXie preprint arXiv:1912. 11940, 2019.
Mitchell P Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. Building a large annotated corpus of english: The penn treebank. Computational linguistics, 19(2): -330, 1993.
H. Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. arXiv preprint Xiv: Ff:::000 400, 2010.
Mahesh Chandra Mukkamala and Matthias Hein. Variants of rmsprop and adagrad with logarithmic regret bounds. In ICML, 2017.
Yurii Nesterov. Introductory leclures on conver oplimizalion: basic course, volume 87. Springer Science Business Media, 2013.
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5):1 17, 1964.
Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. pp. 314-323, 2016.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Slatistics, 22(3):400-44) -00440007777 1951.
Σla Sutskever, James Martens, George Dahl, and Geoffrey Hinton. momentum in deep learning. In International conference on machine learning, pp. 1139-1144 2013.
On the importance of initialization and
T. Tieleman and G. Hinton. Lecture 6.5 RmmsProp: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 2012.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex land- scapes, from any initialization. arXiv preprint arXiv: 1806.880..00 01811, 2018.
Tianbao Yang, Qihang Lin, and Zhe Li. Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization. arXiv preprint arXiv:1604.03257 2016.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In Advances in neural information processing systems, pp. 9793-9803, 2018.
Matthew Zeiler. Adadelta: an adaptive learning rate method. arXie preprint arXiv:1212.5701, 2012.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for wononnvexx arXiv preprint arXim:1006 07811, 2018.
Fangyu Zou and Li Shen. On the convergence of adagrad with momentum for training deep neural networks. arXiv preprint XrXix:1808.0 03408, 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 IEFE/CVP Conference on Computer Vision and Pattern Recognition, pp. 11127 11135, 2019.
14

---

Published in Transactions on Machine Learning Research (02/2024)
Appendix
A Proof of the Main Theory
Here we provide the detailed proof of the main theorem.
A.1 Proof of Theorem 4.3
Let Xy X1. To prove Theorem 4.3 wC need the following lemmas:
Lemma A.1 (Restatement of Lemma 6.4 Let V. and m. be as defined in Algorithm Assumplion 4.1 we have [x]] S G Villo I G and ||mell>o S G
Then under
Lemma A.2 (Generalized version of Lemma 6.5 Let 31, 32, 31, 3/g be the weight parameters such that
m, - (1 8 gt
V, B2V + (1- 13))
04g 1 = , be the slep sizes. We denole 31/32/2 Suppose that 0z and S 1, then under Assumption 4.1 we have the following two results:
az 8
d
Σ a
V
V
1/2 m
S
ggr
2/2 (1) 7) i=1
and
T a
T1/2a? 221 1/)112211 7)
V 1/2
8011
lgg.,
1=1
Note that Lemma A.2 is general and applicable various algorithms. Specifically, set 3 31 and 88/ 82. we recover the case in Algorithm | Further B1 0 recover the case in Algorithm Set Bi 31
and 32 1, 8// 0 recover the case in Algorithm 3
To deal with stochastic momentun m. and stochastic weight 1-1/2 an auxiliary sequence z, as follows: let X = x1, and for cach 2
following Yang et al. 20116 we define
B1
B1
2: Xx + 1- Bi
(x: xx-1)
31 X1
Xt-1-
(A.1)
1
31
Lemma A.3 shows that Z+41 2₁ can be represented in two different ways.
Lemma A.3 (Restatement of Lemma 6.1 Let 2t be defined in
A.1
For 1 2 2, we have
21+1 2, 1- 31
81
(as Vo
1/2) ( V, 11
(x xi) -a, V. 1/2 g:.
(A.2)
and
2,+1 2,
31
(a, 1-112
1-1 - a, 1/2
m. m -a, -. 1/2 gr.
(A.3)
1-
B
For 1 = 1, we have
22 Z = -0 V 1/2 g1.
(A.4)
By Lemma A.3. we connect Z1+1 Z, with X1+1 xx, and a, v. 1/2 ge. The following two lemmas give bounds
14+1 2 2 and [2.) (x(x))l2, which play important roles in proof.
15

---

Published in Transactions on Machine Learning Research (02/2024)
Lemma A.4 (Restatement of Lemma 6.2
Let Ze be defined in
A.1
For t 2 2, have
81
Z1+1 2e|12 laV, 1/2
gt l1 +
x Nx 12-
1 B1
Lemma A.5 (Restatement of Lemma 6.3
Let ze be defined in
A.1
For t 22 2, we have
[V] vx((x)]l2 ( T-3
B1 ) -|xx, x1-1l12. (1-11,))
We present the following lemma which upper bounds the difference f(ze+1) - f(z)).
Lemma A.6 For 1, we have
f(z2) f(z)) S da, Gx + +2l/|a V. 1/2 gi
For 2 2, we have
f(z++1)+ + 2 V- 1211111 [((z))
62 V.-12 11
1- 31
1 81
< -xV((x)) a/-1 - V gz + 2L
a0 Vi
1/2
8:
11
+ 4L
31
||x: - x1
1x,-xx-118
1- 31
Now we are ready to prove Theorem 4.3
Proof Proof of Theorem 4.3
By Lemma A.6 for 1, we have
B[f(z2) f(z1)] s EldaiGo +2 / 1/2
gı 1/
(A.5)
For 2 2, we have
G2 O+ 1-11211
G2 |4 V-112 1/2
E
f((
f(z)) +
1.1
1-31
1 81
< E
([(x)) 0 V-1/2 + +2Ll
1/2 1-12 gr112 + +4L
311
||xe - x1
(1- B1
vf(x)) a4 - / 21 ag
V. 1/2
gr gr
+ 4L
1- 31 )
31
2
||| V 1/2 m,
2
E
-
- - +
21
04
V.
1/2
g: 2 4L
1 (1 B1
3
V.
m
(A.6)
16

---

Published in Transactions on Machine Learning Research (02/2024)
where the equality holds because Eig:] (x(), conditioned (x(x)) and V.1/2 the second inequality holds because of Lemma A.1
Telescoping [A66) for t to T and adding with B 1.
have
T
(Go + ve)
Σ a V
1=2
G
01 V 1/2
1.1 + da - (H(TTH)) +
1211a7771/111
$ E f(z1) +
1- 31
1- 31
T
$1
2 T
+ 2L Σ
B
1/2 at V.
80112 + 4L
Σ
A1-1 V -1/2
1-
31
1=1
1=2
E
A +
Go a1
a1c
1/22 1/2d
dag Go0
+
Σ
T
E
04
Ve 1/2
8112
31
1=1
T
4L
81
E
aas V
V
1/2m.11
(A.7)
1
B1
1=1
By Lemma A.2
we have
T1/ -1-11 (1)
E
1/2
m
(A.8)
2/2 (12
where 7 = =/1/8//2 We also have
T
T1/2a?
Σ
af
IV
1/2
<
E
Σ (BITT
(A.9)
2/2
B2)
t=1
Substituting A.8 and
A.9
into
A.7
and rearranging A..7 we have
B|| [X 112
1
E
(xx))1
aa
2 a1-1 2
(G + V
c 1/2d
<
+ da Goo
Σ at-1
1- 31
GGx + +V]
T1/2
1/2 -7) E
B Birrllla
Et-, 01-1
2e112
GT + Vt)
13
T1/2 - -B1)
d
+
E
I Σ1=001-1 01-1
(1-B)
2/2 (/2 (1)
1=1
2
G2 (Goc + -0)c-1/2d 1/2d
< 2(G v()A+
+
.GGoolGo + vc)
Ta
T
1- B1
2(G + Lo
(1+2 31)
1- 31 (13) ))
+ (12 - (1) -
(A.10)
1/2 (1-32)1111
where the second inequality holds because a₁ a. Rearranging A.10 and note that in the theorem condition we have |ggir,:ll2 Go,T", we obtain
Mr To
M2d +
aMdd 72/2-5'
E [
where (M,)_ are defined in Theorem 4.3 This completes the proof.
17

---

Published in Transactions on Machine Learning Research (02/2024)
A.2 Proof of Corollary 4.5
Proof [Proof of Corollary 4.5
Following the proof for Theorem 4.3 setting $1 = = 0 and 33 = -
in Lemma A.2
we get the conclusion.
A.3 Proof of Corollary 4.6
Proof Proof of Corollary 4.6 Following the proof for Theorem 4.3 sctting 31 31 = =0, ;2 = and 8 =0
in Lemma we get the conclusion.
A.4 Proof of Theorem 5.2
Proof Proof of Thcorem 5.2
By Lemma A.6 for 1 1, we have
f(z2) - f(21)= & do + +2lllarV V/
1/2
gi
(A.11)
For 2 2, we have
G aa V 11,1
Coollar-1 V.-1211 -11111111
(((x)
1.1
[(2++1) +
1- $1
1 31
< -x)((x)) a4-1 1o-1V,11 1/122
Bt + 2L
az V. 1/2
gt
12
+ 4L
B1
2
||x: - x2-1
1 11- B1
-x(((x)) a11 V 1/2
V-12
g: + +2 V 1/2
g:
2
+ 4L
1 31
B1
|1a:-1V;711 V. 1112
(A.12)
Telescoping A.12 for t to T and adding A.11
have
G2
01 V 1/2
I1111
-((eem))
G 1ay 1/2
Σ 04 Vx(x)) V B: S s(2)) +
+ dan Gr
1 1 B1
1- B1
+ 2L
Σ
T
| V.
1/2
1 4h
31
Σ | V- m; 11
1- B1
1=1
1=2
G3e 1/2d
A
dan Go + 2L.
Σ
| V. 1/2
g
1-
81
2
+ 4T.
0r V --1/2 1
(A.13)
1- 1-131
By Lemma A.2
we have
T 121 -31)
Σ
of
1/2 m,
m
1g.
(A.14)
2/1 322 -7) i=1
[=1
where 7 = //////22 We also have
T
T1/2
V
1/2
<
Σ
1g
(A.15)
2/ (1
1/2 -7) 111
18

---

Published in Transactions on Machine Learning Research (02/2024)
Moreover, consider the filtration J, (Ei....., Since x and V only depend on fi,...,Et-11 For any T, > 0, by Assumption 5.1 with -4-0 1-1 ( we have
Ef exp [Aat-1Vf(x) t-1 (gr vf(x)))] Fe-1) s 2IV
Denote = [
1/2 V 1-1 [g vx(x))). Then we have
P(Zz 2 - = PlexppAZZ) 2 exp(Ar)|Ft-i)
EB[ (eepp(-Ar (Z1) 2 1H15-1]
S exp(-Ar) -A))
exp(- exp(p 0z - "
exp(<>r
With exactly the same proof, we also have
Piz S exp(-Ar "
Combining above two inequalities, we have
P( 2 7|F=-1) S 2exp(-Xrrr 2t
Choosing A = [o2a V (-1 V 1 T,, finally obtain
P(IZ 2 F(F=1) S 2 -expxxxprrr 2exp(-72/2oo))
(A.16)
for all > 0, where 0; = ==aaa-llV l fxx 2. The tail bound (A.16) enables the application of Lemma 6 in Jin ct al. 2019). which gives that with probability at least 1 - 5,
T Σ Z
of + Clog(2/c), S
Σ t=
1=2
where an absolute constant. Plugging in the definitions of Ze and os we obtain
vf(xi) g:
a v-(x) V (((xi)
(x.) Cloo((20))
t=2
T
S E
a
V
+Cloo(22))))
(A.17)
1=2
where the second inequality is by the fact that the diagonal entries V are all loewr bounded by e. Substituting A.14h,
A.15)
and A.17 into
A.13)
we have
G2 G2 a1 1/2d
1/
O4 Vf(x,)
V. < A+
+ dog + 2/2 - 1/2
Σ 1g..,all2
3
31
2LT
31)
d
+
1gg.2,112
1 - 31
2//2 (111-8))1/1 1/2 7) 1=1
+ - 02
0 [xx;) +Clog(2/5..
2
t=2
19

---

Published in Transactions on Machine Learning Research (02/2024)
Moreover, by Lemma A.1
have Vx(x))
VV. 2 (Gro (xx and therefore by
choosing at and rearranging terms, have
T
(Gro + vo)
a(1 -
2=2
Go aE
1/2d a/22d
1/2
<
A
+ doG + 21/2 32) 1/221 7)
Σ |ggTT
B1
B1
2LT 22 31)
Σ
gu. C (2o0(2/))).
1- B1
21/2 - 1 1/2 - 7)
Therefore when <. 26/2, we have
(x:)12
T 1=2
OGG + V
4G (oo 12/2-1/2
d
4Go + vo) d
Ta
A
1 1-3 B1
T +
T
x0G + Le
Σ ||ght,
e1/2(1 - (2) 1/2(1 7/T11/
:=1
+ (1-1
81 8GGx + 11
31)
C' + vc) log(2/6)
ggr.
81 1/2 - (12 -1-11-17700 77)
Ta
where O' is an absolute constant.
Now by the theorem condition |gg S To we have
Mi
M2d
aM3d
V
To
T 71/2-8²
where (M,)a are defined in Theorem
5.2
This completes the proof.
A.5 Proof of Corollary 5.4
Proof [Proo of Corollary 5.4 Following the proof for Theorem 5.2 setting 18/ = - = 0 and 33 = 32 =
in Lemma we get the conclusion.
A.6 Proof of Corollary 5.4
Proof [Proof of Corollary 5.4 Following the proof for Theorem 5.2 setting B =/=00 -1 = =0, 82 = and 3 0
in Lemna A.2 we get the conclusion.
20

---

Published in Transactions on Machine Learning Research (02/2024)
B Proof of Technical Lemmas
B.1 Proof of Lemma A.1
Proof [Proof of Lemma A.1 Since f has G stochastic gradient, for any x and &, [Vx S Thus, we have
Goo.
|Vx = | V (xx s (xxlV Go
Next we bound
me We have | - Go.. Suppose that meelo I Goo, then for m411, we have
mm+11lx0 = ||3| m + - 1--))g--1lle
S $1 || m 20 + (1 l1)llo
< Gox (1 31
Goo.
Thus, for any 1 we have | S Go Finally bound lool First have l|volloo 1/ooloo G2 Suppose that l/ I 6% and ||Vello I G2 Note that have
|/2111/ 1182v, + (1 (1- 11-)2))++1 1
s B2llvee lloo + (1 82) 82)
S G2 + +1 - -32)
+11-13
G2
and by definition, we have 1/1llo maxll/frlooc /141ll100 S G% Thus, for any 2 0, we have
loo I G2
B.2 Proof of Lemma A.2
Proof Recall that or Majs St,j denote the j-th coordinate of v,, m, and gr. We have
m
1/2
V
1/2
11
+
1=1
t
1/2
m
< 0
1/2
20
1/2
1/221/2
01
2
d
Mi
2/1
1/2
i=1
d
(1
92,)²
a?
(B.1)
2/2
(E
1=1
where the first. inequality holds since a ++b > 2/ab and the second inequality holds because o., Ut.s. Next have
(1 99,,)2
af (1)2
d
84 19)
1/2
j=1 (1- (1-8))85-00))
2e1 2/21/2
Σ jml $5 02,))'²
i=1
0f (1 - -1)
Σ j=1 8 'g
(B.2)
2/ 1/2
ot-j 1/22
i=1
j=
95,5)
21

---

Published in Transactions on Machine Learning Research (02/2024)
where the first inequality holds due to Cauchy inequality, and the last incquality holds because Σj= S (1 B1)-1. Note that
Σ g3.a 2 (E 9 )/,
8 1g ?
Σ
(32 gg )
i= j=1
1 gا
(B.3)
where the equality holds due to the definition of y. Substituting
B.2 and
B33 into
B.1
we have
a² 81)
V
1/2 mel1 S 2/1/2 1/2
1g
(B.4)
1=1 1=1
Telescoping B.4 1 to T, we have
a1 81)
V 1/2 mx13
Igpal
1/) 2e1/2(1
1=1 i= j=1
af - 31
d T
95,3
2/1 B2)2/22
1=1 j=1
[=)
a3 B1)
T
19
(B.5)
2/2
13)2/2
7)
1=1 1=1
Finally, have
T
1/2
Σ
93
T1/
/2
gi. 1l22
(B.6)
1=
where the inequality holds due Hölder's inequality. Substituting B.6 into B.5
we have
of V m S /1 B1)
d
Σ
ll...
-
Specifically, taking 31 = 0, we have m. = gr, then
T
T1/2
Σ
V 1/2 1 S
2/1 1/2112211 7)
B.3 Proof of Lemma A.3
Proof By definition, we have
31
Z1+1 = Xx+1 +
(x++1 - Xx)
1- B1
B1
X(+1
Xt.
11 31
1
B1
22

---

Published in Transactions on Machine Learning Research (02/2024)
Then we have
31
2++1 - 2t
1- 3]
(x(+1 - xx)
-- B]
(xt xx-1)
1
V. //)))
1/2
31
0r-1 V
1/2
31
1 31
(-1
m--1-
The equities above are based on definition. Then we have
-04
V.Vi
1/2
81 V-1/2
24+1 2,
11m-11+ (1- (1)
+
04-1
m
1 31
1 11
B1
(ac-1
Vo-iVi11- V-1/2 - a4 V.
m - V 1/2 1/2
1- B1
B1
at-1 V/112 [ (ar V 1/3 (ac-1 V V -1
0t 1/1/2 1/2
m
gr
Bi
B1 [ - (a. V (a-1 -1 (x|-1 - -x,) - -a, V, 1/2
1- 31
The equalities above follow by combining the like terms.
B.4 Proof of Lemma A.4
Proof By Lemma A.3 we have
|zc+1 2r|12-
B1
(ar V. 1/2 v/ (ac-1 ( V-113--
(x1-1- xx) a V. V-1/2 g:
1 31
2
<
81
I- (ore (ax
1/3 1/ (0z- 11113-1 10,00
-|x--1 - xx|12 + || V, 1/2
g l1
1- 31
where the inequality holds because the term 31/(1 31) is positive, and triangle inequality. Considering
that Vi 1/2 1o 1/2 when p >>> O, have I (ar V 1/2 (ar V-1/2--1 S 1. With that fact,
20,00
the term above can be bound as:
211 -2//2 5 Va 1/2
+ - B1
31
Xx--1 - Xx X:12-
This completes the proof.
B.5 Proof of Lemma A.5
Proof For term | (z:)) V (xx) we have:
[V/(2,) - (xx))l2 L||z, xxl12 s L 1 B1
B1
(xt
(1(111))
B1 -1)
1||xx-xxxx x1-1
where the last inequality holds because the term B1/(1 33)) positive.
23

---

Published in Transactions on Machine Learning Research (02/2024)
B.6 Proof of Lemma A.6
Proof Since is I-smooth, we have:
f(zL+1) - f(z)) + ff(zz) (Z++1 -ze) + L
2 1t+1 zell2
L
= f(() + fx(x)) (Rt+1 2+)+ + (Z)) vf(x))) (2141 21) +
|z zell
(B.7)
12
13
In the following, we bound I1 I2 and I3 separately. Bounding term Ji: When 1 = 1, we have
vf(x)) (z2 z1) -Vf(x)) Ta V, V.1/2.1 g1.
(B.8)
For t 1.2 2, we have
v)((x) (2e+1 (2(+1 - 21)
=V((x,)
B1
(a--1 1-112 a, 1/2 1/2
m - 1/2 g
1- 31
81
vx(xx) (at-1 1/2
ar - 1/2
1/2
m Vf((x)) T as V. gt.
(B.9)
1-3 31
where the first equality holds due to B.9 we have
A.3 in Lemma
A.3. For vf(x,) (a - V, 1/2 m,-1 in
((xx))(((-1))) V-12 V.V, 1/2 m < /V |a-- -a, V. 1/2
m
< 5 |
11 V- 1/2
(B.10)
The first inequality holds because for positive diagonal matrix A, have x Ay S |x| ||A||1.1 |yyl
1/2 2 0. Next we bound - [xx,) The second inequality holds due to a: V-1/2 2 ar V. have
T ar v. 1/2
g:. We
0 -VS(()) 0n V. -V/((x) 01 V-1/2 g g: - vs(x)) (as V.12 - 1 )g.
I -V((xx)) a -112 g: |V/((x))ll> || V. 1-12 0:-1 --12
1/2
1/2 1.1
||g: ooo
1/2 < (x)())) a (-1 g: + 2% (1|0- V V 11, ||a V 1/2
(B.11)
The first incquality holds because for positive diagonal matrix A, have x Ay < |x||
|||
|11.1
|
The second inequality holds due to a. V-1/2 2 ar V. 1/2 2 0. Substituting we have
B.10 and B.1
into
B.9
Vf(x)) (2141 2.) S -Vx(xx) 0n - 1/2
g: 1- B1
0% |00- V. | v. 11
(B.12)
Bounding term 1p: For 2 1, we have
(Vf(z)) vx(x)) T (2e+1- 22) < [\(zz)) vs(x:)]1
1|zz-111 22212
(1an V.
1////////
1/2
8r112
31
||x -xill)
31
-[|xx x
1 Bi
1
- B
1-
B1
a
V-1/2 1/2
8il12
||x; - x,-1112 +
- B1
Br
2
||x x,- 12
B1
L V.
T.
1/2
g:
1/ + 2T
1|x, x
(B.13)
(1-
24

---

Published in Transactions on Machine Learning Research (02/2024)
where the second inequality holds because of Lemma A.3 and Lemma Young's inequality.
A.4
the last inequality holds due to
Bounding term 13: For 2 1, we have
L
zel2
L ||
V,
ge
B1
|x Xell2 1
2
1 91
<4llav
1,1/2
81
11 +2
31
)
{2
||x|- - x112.
(B.14)
1- B1
The first inequality is obtained by introducing Lemmaa A.3
For 1, substituting B.8 have
B.13
and B.14 into B.7
taking expectation and rearranging terms, we
B1 ) ||x| -xu
f(22) f(z1) -V((x)) a1 V, 1/2
g1 +
a1 V 1/2
g1
4L
1 31
= =Vvf(x)) V 1/2
gi + +
a1 V, 1/2
g1
< d + 22||a 01 1-1/2 B1
(B.15)
where the last inequality holds because
-V((())
1/2 gi s d. VV(() 11
1/2
gi lol S dG
For 2 2, substituting B.12. have
B.13
laking expectation and rearranging terms, we and B.14 into
B.7
G2 l
V
1/2
C2
0 0
1-112
[(2+11) +
1.1
((z,)
1.1
$1
1 11
aL-1 (-1
1/2
+
2L
V.
gi
11 4L
31
||x: - x1-1
1x,-xx-111
1-
which ends our proof.
B.7 Experimental Verification of the Growth Rate Condition
In order to show that the growth rate condition of the cumulative stochastic gradient indoed holds, we have conducted experiments to estimate the growth rate parameter for ResNet-18 (He al. 2016) model and 3-layer LSTM model (Hochreiter & Schmidhuber 1997) respectively. For simplicity, we assume G 1 and estimate the growth rate by calculating the logarithm of the cumulative gradient norm log ||gır, and calculate log al As can be seen from Table 2 of adaptive gradient methods (AdaGrad, RMSProp and AMSGrad) is smaller than that of SGDM for training 3-layer LSTM model on the Penn TreeBank (Marcus et al. 1993) dataset. All of them are actually far below the theoretical limit 1/2 in this real experiment.
method
training loss
test perplexity
SGDM
0.136
4.01
65.11
AdaGrad
0.089
3.92
64.90
RMSProp 0.085
3.84
63.77
AMSGrad
0.086
3.85
63.97
Table Empirical growth rate parameter of 3-layer LSTM model on Penn TreeBank dataset.
25


Reviews:
[{"review_id": "tNjlUEyR7f", "reviewer": "Reviewer_Zzdv", "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:\nThe paper tackles a significant problem for the deep learning community.\nThe paper does a great job of introducing and explaining all the algorithms and the differences between each other.\nIn addition, the paper proposes a clear overview of the previous results.\n\nWeaknesses:\nI am not a leading expert in this area so I do not know how the paper is up to date with the recent literature on adaptive algorithms, this is my only \"concern\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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 authors provide convergence rates for three popular stochastic adaptive algorithms used in deep learning: AMSGrad, RMSProp, and AdaGrad.\nConvergence rates are proved in expectation and with high probability for smooth non-convex functions under bounded stochastic gradients and sufficient control of the cumulative stochastic gradients assumptions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "None", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "h0aeONXent", "reviewer": "Reviewer_6XWB", "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:\n1. Clear improvements upon existing work.\n2. A unified treatment of different adaptive gradient methods.\n\nWeaknesses:\n1. One of the main advantages of adaptive gradient methods is avoiding the expensive hyperparameter tuning to optimize accuracy as a function of the stepsize. However, all results in this paper still contain hyperparameters (most crucially, $\\alpha$), which needs to be set in a fairly nontrivial way to obtain the claimed rates.\n2. While reading the manuscript, I missed a more high-level explanation of how these improvements were obtained. Namely, what major insights were obtained in this work that allowed the authors to get the improved dimension dependence. \n3. Despite the paper providing a unifying framework for adaptive gradient methods, there is some amount of repetition in the arguments (see, e.g. the proofs of Thm 4.3 and Thm. 5.2). Ideally, these similar analyses could have been unified in a streamlined fashion.\n4. Various typos and unclear notation make reading more difficult than it should be.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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 submission provides convergence rate analyses for adaptive gradient methods in nonconvex smooth stochastic optimization; more precisely, rates for the expected squared norm of the gradient for an iterate chosen at random. Both the assumptions and the rates are favorable, compared to existing works. Moreover, the work includes guarantees both in-expectation and with high-probability.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I consider the following comments as essential in order to accept this submission. \n\nMajor comments: \n\n1. Most discussions about the role of gradient sparsity ended up not making an impact on the results of the paper, e.g. in the form of a precise rate of convergence. I understand these discussions have already appeared in the seminal works on adaptive gradient methods, but I was left with the impression that these discussions were somewhat incomplete.\n2. In all algorithms, it is not specified the range of the offset parameter $\\epsilon$. Just looking at any of the upper bounds, it seems to always be beneficial to take $\\epsilon\\to\\infty$ (or sufficiently large, to make the terms where $\\epsilon^{-1/2}$ appears negligible. This seems intuitively wrong. More precisely, my questions are: Does $\\epsilon$ have any hard constraints (other than nonnegativity)? If not, Why not making $\\epsilon\\to \\infty$? \nA slightly related question is the fact that some adaptive gradient methods need some offset parameter (see e.g., Figure 1 in the original adagrad paper https://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf, or Section 3.5 in McMahan's survey https://www.jmlr.org/papers/volume18/14-428/14-428.pdf). Is the offset parameter in the studied results strictly necessary?\n\nMinor comments:\n\n1. Remark 4.4. I couldn't find anywhere in Ghadimi-Lan 2016 an upper bound matching (or resembling) the one in the manuscript. So the claim of \"matching the rates of nonconvex SGD\" seems unjustified. In the same remark, the rate is wrong: it should be $O(d^{1/2}/T^{3/4-s/2})$.\n2. Notational inconsistency. The initial optimality gap is denoted as $\\Delta$, but in all proofs the notation $\\Delta f$ is used. \n3. Equation (6.8) In the expression $(G_{\\infty}^{2p})^{-1}$, where does $p$ come from?\n4. Middle of page 20. There is a jump of line in the middle of the equation $\\mathbb{P}[\\exp(\\lambda Z_t)\\geq \\exp(\\lambda \\tau)|{\\cal F}_{t-1}]$.\n5. Middle of page 24. $m_t(\\alpha_{t-1}\\hat V_{t-1}^{-1/2})$ is not possible as a matrix-vector product. Please switch the two terms. This error is present in multiple equations, so a more thorough revision within the proofs is needed.\n6. Page 24 (and elsewhere). What is $\\|\\cdot\\|_{\\infty,\\infty}$ and $\\|\\cdot\\|_{1,1}$?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "g7mbmRyinb", "reviewer": "Reviewer_gkXY", "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": "The strengths of this work are as follows:\n\n\n1. The paper proposes a rigorous convergence analysis of adaptive gradient methods, including AMSGrad, RMSProp, and AdaGrad, supported by relevant evidence.\n\n2. The paper establishes that for smooth nonconvex functions the analyzed adaptive gradient methods achieve better convergence rates in terms of dimension when compared to the existing results for adaptive gradient methods. \n\n3. By proving high probability bounds on the convergence rates, in addition to bounds in expectation, the work introduces novel and previously unestablished bounds.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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 presents significant contributions in nonconvex optimization, providing a detailed convergence analysis for a broad class of adaptive gradient methods, including AMSGrad, RMSProp, and AdaGrad. The authors propose new convergence guarantees both in expectation and high probability, which outperform the existing ones for adaptive gradient methods in terms of dimension. Indeed, Table 1 on page 3 clearly shows that the new convergence rates have a better dependence on the dimension $d$ and $T$ than the existing rates. It is also worth to note that the high probability bounds on the convergence rates established in this article are novel in nonconvex optimization and hold significant value, particularly when characterizing the performance of algorithms in a single run.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "There are some minor aspects which can be changed (they are not critical to securing recommendation for acceptance):\n\n\n1. The reference to footnote number 3 in Table 1 in the text should be checked to ensure it is properly linked and functioning.\n\n2. The missing dot at the end of the penultimate sentence on page 14 can be added to maintain proper punctuation.\n\n3. In section B.6, additional details about estimating the growth rate parameter $s$ could be included to provide a more comprehensive explanation of the estimation process.", "broader_impact_concerns": "There are no concerns on the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Deep learning optimizers are the cornerstone of practical ML, and hence new works in this area should be of interest to many.
Decision: Accept (poster)