STORM+: Fully Adaptive SGD with Recursive Momentum for Nonconvex Optimization
Authors: Kfir Yehuda Levy
Ali Kavis
Volkan Cevher
Venue: NeurIPS 2021 Poster (2021)
Keywords: adaptive methods
recursive momentum
nonconvex optimization
stochastic optimization

Abstract: In this work we investigate stochastic non-convex optimization problems where the objective is an expectation over smooth loss functions, and the goal is to find an approximate stationary point. The most popular approach to handling such problems is variance reduction techniques, which are also known to obtain tight convergence rates, matching the lower bounds in this case. Nevertheless, these techniques require a careful maintenance of anchor points in conjunction with appropriately selected ``mega-batchsizes". This leads to a challenging hyperparameter tuning problem, that weakens their practicality. Recently, [Cutkosky and Orabona, 2019] have shown that one can employ recursive momentum in order to avoid the use of anchor points and large batchsizes, and still obtain the optimal rate for this setting. Yet, their method called $\rm{STORM}$ crucially relies on the knowledge of the smoothness, as well a bound on the gradient norms. In this work we propose $\rm{STORM}^{+}$, a new method that is completely parameter-free, does not require large batch-sizes, and obtains the optimal $O(1/T^{1/3})$ rate for finding an approximate stationary point. Our work builds on the $\rm{STORM}$ algorithm, in conjunction with a novel approach to adaptively set the learning rate and momentum parameters.

STORM*: Fully Adaptive SGD with Momentum for
Nonconvex Optimization
Kfir Y. Levy
Ali Kavis EPFL ali. kavissieeepfl.co ch
Volkan Cevher EPFL
Technion kfiryleery@technionac...
volkan.ccvhergepfl.. ch
Abstract
In this work we investigate stochastic non-convex optimization problems where the objective is an expectation over smooth loss functions, and the goal is to find an approximate stationary point. The most popular approach to handling such problems is variance reduction techniques, which are also known to obtain tight convergence rates, matching the lower bounds this case. Nevertheless, these techniques require careful maintenance of anchor points in conjunction with ap- propriately selected tuning problem, that weakens their practicality. Recently, [Cutkosky and Orabona, 2019] have shown that one can employ recursive momentum in order to avoid the use of anchor points and large batchsizes, and still obtain the optimal rate for this setting. Yet, their method called STORM crucially relies on the knowledge the smoothness, well bound the gradient norms. In this work propose STORM*, a new method that is completely parameter-free, does not require large batch-sizes, and obtains the optimal (1/T1//5 rate for finding an approximate stationary point. Our work builds the STORM algorithm, in conjunction with novel approach to adaptively set the learning rate and momentum parameters.
This leads to a challenging hyperparameter
1 Introduction
Over the past decade non-convex models have become principal tools in ML (Machine Learning), and in data-science. This predominantly includes deep models, as well as Phase Retrieval [Candes et al., 2015], non-negative matrix factorization [Hoyer, 2004], and matrix completion problems [Ge et al., 2016] among others.
The main workhorse for training ML models is SGD (stochastic gradient descent) and its numerous variants. One parameter that significantly affects the SGD performance the learning rate, which often requires a careful and costly hyper-paramett tuning. Adaptive approaches to setting the learning rate like AdaGrad [Duchi et al., 2] and Adam [Kingma and Ba, 2014] as well as non-adaptive heuristics [Loshchilov and Hutter, 2017, He et al., 2019] are very popular in modern MI. applications, yet these methods also require some tuning of hyper-paramette like momentum and the scale the learning rate schedule.
popular SGD heuristic that has proven be crucial in many applications is the use of momentum, ie., the use of weighted average of past gradients instead of the current gradient [Sutskever et al., 2013, Kingma and Ba, 2014]. Although adaptive approaches to setting the momentum have been investigated in the past [Srinivasan et al., 2018, Hameed et al., 2016], principled and theoretically- grounded approaches to doing so are less investigated. Another aspect that has not been extensively studied, which we take into account in this work, is the interplay between learning rate and momentum.
A Viterbi fellow. Corresponding author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In this work we explore momentum-basee adaptive and parameter- free methods for stochastic non-convex optimization problems. Concretely, we focus on the setting where the objective is an expectation over smooth losses (see Eq. (4)), and the goal is to find an approximate stationary point.
In the general case of smooth non-convex objectives it is known that one can approach stationary point rate of O(1/T!/4), where T is the total number of samples [Ghadimi and Lan, 2013]. While this rate is optimal in the general case, it is known that one can obtain an improved rate of O(1/T4/3) if the objective is an expectation over smooth losses [Fang et al., 2018, Zhou et al., 2018, Cutkosky and Orabona, 2019, Tran-Dinhi et al., 2019]. Besides, this rate was recently shown to be tight [Arjevani et al., 2019].
Nevertheless, most of the methods developed for this setting rely on variance reduction techniques [Johnson and Zhang, 2013, Zhang et al., 2013, Mahdavi al., 2013, Wang et al., 2013], which require careful maintenance of anchor points in conjunction with appropriately selected large batchsizes. This leads to a challenging typer-paramett tuning problem, weakening their practicality. One exception is the recent STORM algorithm of Cutkosky and Orabona [2019].
STORM does not require large batches nor anchor points; instead, it uses a corrected momentum based gradient update that leads to implicit variance reduction, which in turn facilitates fast conver- gence. Unfortunately, none of the aforementioned methods (including STORM ) is parameter- Indeed, the knowledge of smoothness parameter together with either the noise variance or a bound on the norm of the gradients are crucial to establish their guarantees.
In this work, we essentially develop a parameter- free variant of STORM algorithm. We summarize contributions follows,
We present STORM+ a parameter-free momentum based method that ensures the optimal O(1/T1/3) rate for the expectation over smooth losses setting. Similarly to STORM, our method does not require large- hinge-batches nor anchor points.
STORM+ implicitly adapts to the variance of the gradients. Concretely, it obtains con- vergence rate of O(1/vT + 1/3 /T113), which recovers the optimal O(1/VT) rate in the noiseless case. We also improve over STORM by shaving off a (log Ty3/4 factor from the 1/VT term.
In STORM* we demonstrate novel way to set the learning rate by introducing an adaptive interplay between learning rate and momentum parameters.
Related Work
In the context of stochastic non-convex optimization with general smooth losses, it was shown in Ghadimi and Lan [2013] that SGD with an appropriately selected learning rate can obtain rate of O(1TT//4) for finding approximate stationary point, which is known to match the respective lower bound [Arjevani et al., 2019]. While the method of Ghadimi and Lan [2013] requires knowledge of the smoothness and variance parameters, recent works have shown that adaptive methods like AdaGrad are able to obtain this bound in a parameter free manner, as well as to adapt to the variance of the problem [Li and Orabona, 2019, Ward et al., 2019, Reddi al., 2018]. These results, in sense, explain the success of adaptive methods like AdaGrad [Duchi et al., 2011], Adam [Kingma and Ba, 2014], and RMSProp [Tieleman and Hinton, 2012] in handling non-convex problems.
The idea of using variance reduction techniques for non-convex problems was first suggested in the context of finite sum problems by Allen-Zhu and Hazan [2016], Reddi al. [2016], showing a rate of ((1/T1/4) This was later improved by Lei et al. [2017] to a rate of ((1/T8/30) The first works that have obtained the optimal 1/33 for this setting were Fang al. [2018], Zhou et al. [2018]. Additionally, Fang et al. [2018] shows that the same convergence behavior applics to the more general expectation over smooth losses setting (see Eq. (4)) setting that captures finite-sum problems as private case.
2 An adaptive method is method that updates its learning rate according to the (noisy) gradient feedback that it receives throughout the training process.
2

---

The STORM algorithm suggested in Cutkosky and Orabona [2019] is the first algorithm to obtain the optimal ((1/T=/3) for this setting without the need to maintain anchor points or large batches. Instead, it relies on clever correction of the momentum by making only one extra call the oracle, which leads to an implicit variance reduction effect. Moreover, STORM adapts to the variance of the problem by obtaining a rate of ( TV + o /T/// without any prior knowledge of variance. However, needs know the smoothness parameter and a bound on the gradient norms to set the step size and momentum parameters, Simultaneously to the work of Cutkosky and Orabona [2019], another paper [Tran-Dinh et al.. 2019] have obtained the same optimal bound by proposing similar update rule. Note that Tran-Dine et al. [2019] does calculate single anchor point, and it still requires the knowledge of the smoothness and variance parameters.
Setting and Preliminaries
We discuss stochastic non-convex optimization problems where the objective f IRd + IR is of the following form,
f(x) := [f
and is an unknown distribution from which we may draw i.d. samples. Our goal is to find an approximate stationary point of f, i.. after T draws from D we should output a point 7 E IRd such that f S Po)y(1/T))
We focus on first order methods, i.e., methods that may access the gradients of f(, and make the following assumptions regarding the noisy gradients and function values.
Bounded values: There exists B > 0 such that,
max [f(x) f(y)l s B.
2,EER
Bounded gradients:
There exists G > 0 such that,
[v; e) < G² Vo TR. E E support(D).
(2)
Bounded variance: There exists > such that,
(=; {) ff(2)) S o²; Var ER.
(3)
Expectation over smooth losses: There exists L >> 0 such that,
[v E) v fy:: Elll - L|| yll Vz,y E I support(D).
(4)
The last assumption also implies that the expected loss f(-) is L smooth. A property of smooth functions that we will exploit throughout the paper is the following.
f() S f(x) + (v( ( - + (T/2)lly xll; Vz, Rd
(5)
In the rest this manuscript, f { relates to gradients with respect to x, i.e., V := V.. We use || to denote the Euclidean norm, and x² denotes global minima of f()), i.e.e,, x" min f(x).
4 Method
In this section we present STORM* (STochastic Recursive Momentum +): a parameter-free stochastic optimization method that finds approximate stationary points optimal rate. We describe our method in Alg. and Eq. (8), and state its guarantees in Theorem 1.
The original STORM algorithm: The original STORM template of Cutkosky and Orabona [2019) relies on an SGD-style update with a corrected momentum. Concretely, the idea is to maintain gradient estimate d, which is corrected weighted average of past stochastic gradients, and then update the iterates similarly to SGD,
F141 Z, md. Standard momentum is a weighted average of past gradients,
(6)
a. v + (1 ar)d-11 where a [0, 1].
3

---

Under this construction, d, is generally a biased estimate of fZz)) In STORM it is suggested to add a correction term .1 a,) (V. Vf(z1-11 E.)), which leads to the following update rule (again, 0z E 1))
d, far, (.) (1 a,)(d, -
(Corrected Momentum)
The correction term plays erucial role here: it exploits the smoothness of f(. () in a way that leads to a variance reduction effect. To see this effect one can inspect the error of the momentum de compared to the exact gradient at Zt,
:= - -=da-V((a)
The STORM update rule induces the following error dynamics,
et (1 an)er- (V(V V((())) + (1 az)
where Z, (Vi( {t) -V((11)))-(((()) -) Due to the smoothness of Intuitively, as we approach
the objective we have /Z,ll S O(1 xz- O
stationary point (and use a small enough learning rate) then 7/- 1 decreases which in turn reduces the magnitude of Ze's. Moreover, the second term in the above dynamics, az (V ( Ex)
ff(x))) )) can be controlled by choosing a small enough momentum dr- Thus, carefully controlling the learning rate and momentum parameters leads to variance reduction effect which facilitates fast convergence.
The original STORM paper [Cutkosky and Orabona, 2019] makes the following choices,
1/3
T) 0/
w +
||:11
& de --= cL 1
where we denote 9: == V f(re, Ee). The above choice of learning rate is inspired by AdaGrad Duchi al. [2011], which also sets the learning rate inversely proportional the cumulative square norms of past gradients. Note that 0 and w are constants that depend on the smoothness of the objective L, as well as on the bound on the gradients G, and is an absolute constant independent of the problem's characteristics. These choices of the constants and especially the choice of ag x L'm is crucial for the analysis of the original STORM. In fact, the convergence proof for STORM breaks down unless we encode this prior knowledge into T and az Next, we describe our parameter-free version.
Our STORM* algorithm: STORM* relies on the original STORM template described in Equa- tions (6) and (Corrected Momentum), with the following parameter-fre choices of learning rate and momentum parameter,
1/3
2/3
1) = 1/
Σ
| /ait1
& at 4=1/ 1+
|
(8)
where again we denote St V VI &t). Note that in contrast to the original STORM our adaptive learning rate builds on history of estimates (di,...,dd, de) as well as on the momentum parameters {a1...., (.+1) ). Our momentum term is similar to the adaptive choice of STORM, yet it does not require a bound on the gradients nor on the smoothness parameter, which was crucial for the original analysis. Finally, note that the above choice ensures de E [0.
For completeness we present our method in Alg. 1, where it can be seen that STORM+ is a combi- nation of the original STORM template (Equations (6) and (Corrected Momentum)) together with the specific choices of nt and a, appearing in Eq. (8). Note that the solution that STORM* outputs point chosen uniformly at random among all iterates, which is quite standard in (stochastic) non-convex optimization.
Notation: In Alg. and throughout the rest of the paper we will employ the following notation,
gt
g. == Vf(zn ge == fxz)
Now, we position to present main theorem regarding STORM (Alg. 1):

---

Algorithm STORM
Input: #iterations T', I1 E R²
I: Sample & and set dj = 91 Vf((1.
2: for -,....? T do
a--1 t 1/ 1+ 2/3
& n + 1/ (Ei=) |d,12/0z+1 1/3
4: T++1 s- It nch
5: Sample 51+1 and set 9++1 == ((41)) and Jt == Vf(zzi d++1 t 91+1 (1 ac+1)(de 91)
6:
7: end for
8: Choose är uniformly at random from ( 2T)
9:
return Ër
Theorem 1.
Under the assumption in Eq. (1), (2), (3) and (4) in Section 3, STORM* ensures,
.
1/3
[ SO
VT
T1/3
where = O(B3/4 13 M = 0 L + 8
G (LG4)3/2), and the expectation is with respect to the randomization of the samples as well as the algorithm's ss.
Theorem demonstrates that the stochastic case STORM* achieves the optimal 0(1/T1/3) rate for our setting. Moreover, can be seen that STORM implicitly adapts to the variance the noise: in the noiseless case where a 0, STORM* recovers optimal O (1/TT)) rate. We note that scaling the learning rate by some (absolute) constant factor may enable us to obtain better dependence on and B.
Analysis
In this section we provide the convergence analysis of the STORM+ algorithm. We begin with the analysis in the offline case where a = O, and establish convergence rate of O(1vVT) in Section 5.1 for completeness. In Section 5.2, we introduce simplified version of STORM with a non- adaptive momentum parameter the form G++1 == 1/t2/3, Due to simplicity and space limitations, is inconvenient to share the full proof of STORM* and this simplified version enables us to illustrate the main steps of the original proof. We show that this version achieves convergence rate of (3)) in the stochastic case (though it does not adapt the variance). Finally, in Section 5.1 we provide proof sketch for STORM in Alg. that establishes the result in Theorem 1.
5.1 Offline Case
Here we analyze STORM+ + in the case where a = 0, and demonstrate a rate of O(1/VT) for finding an approximate stationary point.
Theorem 2. Let f satisfy Eg. (1), (4) and Fr be generated after running Alg. I for T iterations under deterministic oracle. Then holds that,
( O(VI+ 1 /VT).
where we take expectation due to randomness governing the generation of IT (see line 8 in Alg. 1).
Proof. In the case where o = one can directly show by induction that de = g: = Vf())) So the update rule becomes I++1 = It 7/7t. Now, using the smoothness of the objective implies,
A A, f(x,1) f(xx) < 17.1" Lnj 1
5

---

here we denoted A : f(z1)= f(x"), where x² E arg min f(z). Dividing by nis re-arranging and summing gives,
A
A++1
D
+
T)t 11ge 11?
1/1
111'
11t
1/1-1
B
T
T
1 l1
B
+
t=2
1h
7h-1
2
E :=
1
1/3
2/3
T
1/3
T
2/3
B
L
11:.1
S
B
Σ
1
11?
//a+1
+
L
Σ
11?
1/
i=1
t=1
2/9
1/3
2/3
$ B
1 Σ
|
Σ
11
112
+
Σ
where the second inequality uses TJ Ei |0:11 1apP/as1)
-1/3
(Ein l13:11
-1/3
which
holds since de = Dt and a, S We also use that A. E [0, B] together with Vi n--1 2
The third inequality uses Lemma 3 below; and the last inequality uses 1/ac+1 S (1/0T+1)
[++EE1 Ib 1²) 2/3
which holds since a, is monotonically non-increasing.
By treating the inequality in Eq. (9) as a polynomial Σi= 19:1| 1| one can derive the following bound, Σt= 12. < O(1 + L + B²/4). Using the definition of Fy well as Jensen's 's inequality implies,
E| V = E|g((r)) S Elg
Σ 1T.13/T O B /VT).
which establishes the bound. In the proof we have used the technical lemma below,
Lemma 3. Let by O, b2 ...y bn 0 be sequence real numbers, p (0,1) 1) be real number.
1-p
bi
1 S 1 1-
2
bi
Σ== bz)
li=l
5.2 Stochastic Case Analysis of Simplified STORM*
Here analyze simplified version of STORM* in the stochatic setting. While this version does not adapt to the noise variance, it exhibits the optimal rate of 11//T/33 in the stochastic case, and its analysis illustrates some of the main ideas that we employ in the proof of the fully adaptive STORM* (which is more involved).
The version that analyze here differs from STORM* in the choice of the momentum parameters. Here we choose a 1 and a,+1 1/12/3 1L 2 1, in contrast to the adaptive choice that we make 1/3
in Alg. 1. Note that we keep the same expression for the step size, = =1/ (Σ ||d,11 ||d,13/a/41)
Theorem 4, Under Assumptions in Eq. (1), (2), (3) and (4), simplified STORM* ensures,
E = 0 O0V L3 B3/2
Proof. The proof is composed of two parts. In the first we bound the cumulative expectation of errors F. D |e?, where é, is the difference between the corrected momentum d, and the exact gradient Ht, I.c. de zr. Thus, in the first part relate the above sum to the sum of exact

---

gradients E E 10.12 Then, in the second part we divide into two sub-cases the first where E E ||, 12 < (1/2) 1 and its complement. In one of these sub-cases we also use the smoothness of the objective together with the update rule, similarly to what we do in Eq. (9).
First Part: Bounding E
E l|cel1.. The update rule for de induces the following error dynamics,
E (1 - (1-a))er- dx)Et-1 1 + ag 9t) + (1 az) Zt
(10)
where Z, == (g. 91-1) - (ā. - 91-1). Letting Mr be the history to time t. ie., H4 := {r1 &2. E3 ..,E:) {r} } and recalling that both a and 2; depend on history up to t 1, i... H4-1, immediately implics that Ela - g:) H = E((1 - a, Z. = 0. as well as
B[(1 a)4-1 [H,-]] (1 11)
Thus, taking the square of the above equation and then taking the expectation gives,
E 1 $ (1 ax) ' E| 12 + [I(1 a,) + (g - 31)l
1 (1 - ) (|--1 | 2 a,)² | 2 + P - 1el
$ (1 ) || 1| + 8T. ||d,-1| 2aç0²
(11)
where the second line uses ||6 + c|| < 2 2||e|12, and the last line uses E gell² < 0² and
(1 - a.) E [0, 1]. as well as the smoothness assumption that implies / S 9tt 9t-1 || + l
R-11l S 21 x1-lll = 2[m/-lldd
Dividing Eq. (11) by at and re-arranging implies.
1 E EI S at
E | 1|
E |lcce + ST. 1|d /ail 20
Summing the above, and using co == gives.
E
||er
T-1
E 1=1
c--1 11? s
E |all +8L E
- 1|
/aol +20
a2
OT
Q-1
at
[=1
(A)
(B)
(C)
(D)
(12)
Next we bound all the term on the RHS of the above equation:
Bounding (A): Since or S we can bound -E -|||e/|| /or S =Ellerl?
Bounding (B): Note that G(z) = 22/3 a concave function in RR. Thus applying the gradient
inequality implies that V21, 22 2 0 we have (21 + 2// - 2//3
2 -13 22. Hence, for all t 2 2,
-
1/ae+1 1/a, /2/3 (t - 1)2/3 2 1/3 < 2/3
1/3
Moreover, 1/az - 1/a1 0. These imply that (B) < (2/3) T 11=
Bounding (C): By definition of ne we have,
||d__|1? /at
1/3
T
1/3
(C) E
2/3 S 3E
Σ |adell /app////11///
S 2/72/9
E
||de|1
E
[|d] (id/1///+))) aa+1))
where the first inequality uses Lemma 3, and the second inequality uses 1/0,- S 1/ar+1 S 2233 as well as Jensen's 's inequality with respect to the concave function U22) = 1// defined over R4.
Bounding (D): Lemma 3 immediately implies that (D) = 1+ ΣT= 1/t2/3 < 1 3T 13 < 1/3
Plugging these bounds into Eq. (12) and re-arranging yields.
1/3
T
T
leal 2 <
22/2
E
1de11
+ 24o 1/13
(13)
1=1
7

---

Second Part: Bounding E Ei=1 l Here we use the bound of Eq. (13) in order to bound the sum of square gradients. Let divide into two sub-cases.
Case 1 Assume that E. EΣ | ||d/ll < 21l + 2||e 12 (due to d, Plugging this inside Eq. (13) yields,
E 16 Combining the condition of Case 1 with
9t + Et), implies that E E |deel2 < 6E Σ |||]|
T
E Σ |ell S 72127//9
6E
Σ l
+ 2402
t=1
The above immediately implies that E EΣi 1 ||a/|1 2 O(LL+ /33) and due the condition
of Case we therefore have, E ビ |0: S ( + 0²)T1/3). This concludes the first case.
Case 2 Assume that E E | - 1 Σ 11 Combining the condition of Case 2 with ||de]| 2 1 + 2||ez||² (due to d, = St + ct), implies that E - ||de - 3E Σ ll l|
Now using the update rule z++1 Z₁ mi together with smoothness of f(-), one can show in similar manner to our derivation of Eq. (9) the following bound (we defer this the appendix).
T
T
1/3
T
2/3
3
| 2BT
Σ
11
+
|ddl
(14)
2
t=1
[=
Taking the expectation of the above equation and plugging in E well as E
ET
||de
1|
3E Et=1
|g:11
as
>
||eall
E
-t l gives,
T E
T
1/3
T
2/3
E
| 2BT
3E
|ell
L
3E
11
(15)
Am
where we also used Jensen's inequality with respect to he concave functions 1/1 1/3 and 2//3 defined over i The above immediately implies, E second case.
E || 11 < O(L3 /3/2222/3). This concludes the
Summary.
We have shown that E E the definition of Fr and using Jensen's 's inequality similarly to what we did in the offline analysis provides,
| < O(LL3 + o² /3/ combining this with
/3/2/T1/3)
which concludes the proof.
5.3 Stochastic Case Analysis of STORM
Finally, we provide sketch of the proof for the STORM* algorithm appearing in Alg. 1. In high level, the analysis follows similar lines to that of of simplified STORM" 's appearing in Section 5.2.
There two extra challenges compared the analysis of simplified STORM*
Now a, is random variable that depends on the noisy samples.
2. The differences 1/at+1 1/a, not necessarily smaller than
Recall that in the analysis appearing in Section 5.2 we used 1/a:+1 - 1/a; S 2/3, which was crucial to bounding term (B).
Among the tools that we use to address the first challenge version of Young's inequality, that we mention in the appendix. To cope with the second challenge, when we bound the expectation of
D |ez 1| it is split into two.
Neell
Σ
1

---

appearing in where r* is time-step after which we can ensure that 1/at+1 1/a: S 2/3. Next we proceed with the proof sketch.
Proof Sketch of Theorem 1. The proof is composed of three parts: (a) In the first part bound the cumulative expectation of errors Ei= || where 6 = de 9t. and r* is a stopping time after which we can ensure that 1/ax41 - ar S 2/3. (b) In the second part we use our bound on E || in order to bound the total sum of square errors, E EE ||ee|l (c) Then, in the last part we divide into two sub-cases the first where E Ei=1 ||& - (1/2)E Il Il and its complement. In one of these sub-cases we also use the smoothness of the objective together with the update rule, similarly to what we do in Eq. (9).
First Part: Bounding E E lIeell?. Recall the error dynamics of STORM* Eq. (10). Taking the square and summing up to some T" E [T] enables to bound,
Σ 1=1
|eall S Σ 10---1l---11 +2
12
2
of 11 dell + M
where M, 2((1 a1) ar (g: 3t) 3.) (1-a))
2z) is martingale difference sequence such that E[M, H,-1] = O. where H, is the history to time t, i.e. He == (z), E1, ......... &. Also, recall that Z, = (g: 11 (9: 91-1).
Now let us define 3 == min 1/ and T' = maxft E [T] : o 2 $}. Recalling that 4++1 is measurable with respect to HA implies that 7" [T] is a stopping time.
Re-arranging the above and using the definition of 7" implies,
T
|eal| S || 11
act aet1 elel 2
Zz
2
a
Del1
+
M
(iI)
(ii)
where we used 7* T, as well as B < Next we bound the expected value of the above terms.
Bounding (i). As in the previous section, the smoothness property implies that | s 1 Using the expression for 7h-1 together with Lemma 3 enables to show,
d I 12T du 12)2/3
(1) < 4
|| 12)2/3
t=1
Bounding (ii). One can directly show that Eja the expression for a,, is possible to show that,
3. - E 11
Using this together with
1
Eii
E
Σ 12//333/33 Sa.
where C1 a constant, and the second inequality is due to a lemma that we describe in the appendix.
Bounding (iii). Since -" E []] is a bounded stopping time, and M, is a martingale differ- ence sequence, then Doob's optional stopping theorem Levin and Peres [2017] implies E(ii)) E E Mr 0.
Conclusion. The above together with Jensen's 's inequality for U(2) 1/3 defined over R4, yields,
||eall < 2C1/B+ 24 2 (E
|d.l|
(16)

---

Second Part:
Li=1 ||al1.. Recall the error dynamics of STORM appearing in Eq. (10). Dividing by Va,, taking the square and summing up some T enables to bound.
Bounding E E
1 <
1 + 2arllg: - gell Ye
- c 12
-
1)1 1/ +2
a1
at
where Y = 2( 1-
ya, 9--1, Va - 3:) + 1- Ze) is martingale difference sequence such va,
E|Y,/He-11 = 0. Re-arranging the above and summing one can show,
T
1 lelll +2
2 2
T
T
1-11 1
+2
ax 1lg
Dell
+
Y1
G++1
t=1
(B)
(C)
(D)
(B)
Now, due the martingale property E(E) O. Next, we focus on bounding term (B).
Bounding (B). Using the definition of one can show that 1/a--1 S 1/3 ; vt S T where 1/3 = (1/38/2 + G2)2/3, Moreover, we can show,
1/ar+1 1/a, S 2/3; 2
This enables to decompose and bound (B) according to to,
1 ||cell1
1
Meall
+ Σ
E(
1
||ee||
Or+1
a₁
O++1
ar
Gr+1 at
1=
2
2
$
| 21
Σ
|lell1
|el|
(17)
t=
This enables to use Eq. (16) to bound the expected value of term (B).
From here the analysis of the other terms and bounding E | done similarly to our analysis of simplified STORM*
1=1 | 2 In this part we divide into two sub-cases depending whether l or not. And continue similarly our analysis of simplified STORM* The rest of the details appear in the appendix.
Third Part: Bounding E E
E ||ea| > (1/2)E
Conclusion
We have presented novel parameter-free and adaptive algorithm for non-convex optimization that obtains the optimal rate in the setting expectation over smooth losses while adapting to variance in gradient estimates. Our approach suggests new way to set the learning rate and momentum jointly and adaptively throughout the learning process, which might open up new avenues to both practical and thcoretical developments in this direction.
Acknowledgments
This work has received funding from the European Research Council (ERC) under the European Union's is Horizon 2020 research and innovation programme (grant agreement 725594- time-data); Hasler Foundation Program: Cyber Human Systems (project number 16066); the Department of the Navy, Office of Naval Research (ONR) under grant number N62909-17-1-2111 the Swiss National Science Foundation (SNSF) under grant number 207821_178865 / I; and the Army Research Office under Grant Number W91 W91INF-19 1-0444. K. Y. Levy acknowledges support from the Israel Science Foundation (grant No. 447/20).
10

---

References
Z. Allen-Zhu and E. Hazan. Variance reduction for faster non-convex optimization. In International conference on machine learning, pages 699-707. PMLR, 2016.
Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv: 19/2.02365, 2019.
E. J. Candes, X. Li, and M. Soltanolkotabi. Phase retrieval via wirtinger flow: Theory and algorithms. IEEE Transactions Information Theory, 61(4):1985-2000 2015.
A. Cutkosky and F. Orabona. Momentum-base based variance reduction non-convex sgd. Advances in neural information processing systems, 32, 2019.
Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 120ul):2121-2159 2011.
C. Fang, C. Li, 7. Lin, and Zhang. Near-optimal non-convex optimization via stochastic path integrated differential estimator. Advances in Neural Information Processing Systems, 31:689, 2018.
R. Ge, J. D. Lee, and T. Ma. Matrix completion has spurious local minimum. Advances in Neural Information Processing Systems, pages 2981-2989, 2016.
S. Ghadimi and G. Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic program- ming. SIAM Journal on Optimization, 23(4):2341-236 2013.
A. A. Hameed, B. Karlik, and M. S. Salman. Back propagatonnt algorithm with variable adaptive momentum. Knowledge-
Systems, 114:79-87, 2016.
T. He, Z. Zhang, H. Zhang, Z. Zhang, J. Xie, and M. Li. Bag of tricks for image classification with convolutional neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 558-567, 2019.
O. Hoyer. Non-negative matrix factorization with sparseness constraints. Journal of machine learning research, 5(9), 2004.
R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26:315-323, 2013.
D. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6900, 2014.
L. Lei, C. Ju, J. Chen, and M. I. Jordan. Non-convex finite-sum optimization via sesg methods. In Proceedings of the 3 1st International Conference on Neural Information Processing Systems, pages 2345-2355, 2017.
D. A. Levin and Y. Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
X. Li and Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd International Conference Artificial Intelligence and Statistics, pages 983-992. PMLR. 2019.
I. Loshchilov and F. Hutter. Sgdr: Stochastic gradient descent with warm restarts. In International Conference on Learning Representations, 2017. URL ryQu7f-RZ. RZ.
M. Mahdavi, Zhang, and R. Jin. Mixed optimization for smooth functions. Advances in neural information processing systems, 16:674-682. 2013.
Reddi, A. Hefny, S. Sra, Poczos, and Smola. Stochastic variance reduction for nonconvex optimization. In International conference machine learning, pages 314-323. PMLR, 2016.

---

S. J. Reddi, S. Kale, and S. Kumar. On the convergence of adam and beyond. In International Conference on Learning Representations, 2018. URL httll//////peeeeeeeew.eeee wwtp://wewe/eotommooeeee ryQu7f-RZ. RZ.
V. Srinivasan, A. R. Sankar, and V. N. Balasubramanian. Adine: An adaptive momentum method for stochastic gradient descent. In Proceedings of the ACM india joint international conference on data science and management of data, pages 249-256, 2018.
I. Sutskever, J. Martens, G. Dahl, and G. Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning, pages 1139-1147. PMLR, 2013.
Tieleman and G. Hinton. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
Q. Tran-Dinh, N. H. Pham, D. T. Phan, and L. M. Nguyen. Hybrid stochastic gradient descent algorithms for stochastic nonconvex optimization. arXiv preprint arXiv: 190:::90500000 1905.0592, 2019.
C. Wang, X. Chen, A. Smola, and P. Xing. Variance reduction for stochastic gradient optimization. In Proceedings the 26th International Conference on Neural Information Processing Systems- Volume 1, pages 181-189, 2013.
R. Ward, x. Wu, and L. Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes.
In International Conference on Machine Learning, pages 6677-6686. PMLR, 2019.
Zhang, M. Mahdavi, and Jin. Linear convergence with condition number independent access of full gradients. Advances in Neural Information Processing Systems, 26:980-9883 2013.
D. Zhou, P. Xu, and Q Gu. Stochastic nested variance reduction for nonconvex optimization. Advances in Neural Information Processing Systems, 31:3921-3932, 2018.
12


Reviews:
[{"review_id": "xHL59eY9HeX", "reviewer": "Reviewer_Ft5i", "summary": "The paper proposes STORM+, which adopts the STORM method with a new way to set the learning rate (parameter free momentum based). The method also obtains the state-of-the-art convergence result for finding an approximate stationary point. ", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Comments: \n\n1) The idea of applying the adaptive learning rate to the existing method is not new. This could be considered as a marginal work. However, I appreciate the convergence analysis of the paper. \n\n2) Numerical experiments (in the supplementary document) do not show any advantages of STORM+ over STORM. It is true that STORM+ does not require to tune the parameters because of the parameter-free choices of parameters, but from the experiments, it is not clear whether STORM uses the best tuning parameters. \n\n3) Comparing to other methods, STORM+ also does not show the benefits. This would raise a question why people have to consider this method but not using Adam. I would suggest the authors provide more experiments to verify the effectiveness of the proposed method. \n\n4) Since the paper focuses on the practical side of STORM, it would be nice to bring the numerical experimental part into main content. \n\n5) Hybrid-SGD in [Tran-Dinh et al, 2019] does not require “bounded values” and “bounded gradients” assumptions. Could you please have some discussion of why the proposed method has more advantage than Hybrid-SGD? I do not see much comparisons with this method. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "_I6oehvFhkg", "reviewer": "Reviewer_ZL4A", "summary": "This paper proposes an adaptive variant of the recently proposed STORM algorithm for minimizing expectations of smooth, nonconvex losses. By doing so, it removes the hyperparameters necessary for running STORM.\nIt offers an analysis of the method and rates of convergence, but no empirical validation of the method.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main argument for this method is practical : STORM requires parameters that are hard to access, namely the common lipschitz constant of the functions appearing in the expectation. It seems to me that it is therefore crucial to show experiments validating the proposed adaptive method. Additionally, it would be beneficial to compare the adaptive variant to the sublinear momentum variant on typical problems.\nThis explains my rating. I will be glad to modify it given empirical evidence of the proposed algorithm's performance. I would recommend a minima reproducing the experiments from the initial STORM paper, adding the STORM+ variants considered in this paper.\n\nThe worst case bound adapts to the magnitude of noise: is this the case in practice on toy experiments? It would be nice to check whether this is an artifact of the proof/worst case, or if this is also true in practice. Such experiments would help me modify my rating.\n\nWhat is the point of section 5.2 ? I would argue to move this to appendix, saying that a version of the algorithm w/ sublinear momentum parameter also achieves the same aymptotic convergence rate, although the non-asymptotic rate does not adapt to the variance of the stochastic gradient estimator.\nRather than provide the analysis for the case sigma=0 and the case w/ sublinear momentum parameter, I would also rather see an extended sketch of the analysis of STORM+ in the main paper. It would also be helpful for the reader to re-state things when they are needed. \n\nThe paper is not very well written, with quite a few typos. I would recommend working on the flow of the paper and its presentation : re-stating asumptions/lemma results when needed, relying less on bullet-point style presentation (cf line 182 - 206).\n\nComments on form:\nTypo line 30: hanging sentence\nLine 82: forgot the bar on x\nIt should be “Such that” instead of “such” in all the conditions (bounded values etc)\nLine 84: why is x* a global minima, rather than a stationary point?\nLine 92: notation consistency: maybe use greek letters for scalars? (a_t -> rho_t or beta_t to be consistent with the literature?)\n\nLemma 2: why is it written that p must be rational? This isn’t used in the proof in the appendix.\nProof of lemma 2 : the induction hypothesis must hold for n-1 >= 1, not > 1. It also needs to be said somewhere that b1 cannot be 0.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "PHm3y1nzJBm", "reviewer": "Reviewer_CNhs", "summary": "In this paper, the authors provide a parameter-free version named STORM+ of the STORM algorithm. STORM+ uses the same single-loop recursive momentum (which leads to implicit variance reduction effects) and constant batchsizes as in STORM, but features a parameter-free design by constructing the learning rate \\eta_t and momentum coefficient a_t using past parameters and momentums (as a comparison, STORM needs to tune these two factors manually). Theoretically, the authors show that STORM+ achieves the same near-optimal complexity as STORM but without needing to tune the parameters to ensure this guarantee.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "After response:\n\nThanks a lot for your response. I appreciate the novel analysis in this paper to handle the hyperparameters' adaptivity in the original STORM method, and after my second reading, I feel that I am too picky at the assumptions and experiments in this paper. Therefore, I increase my score to 6.\n....................................................................................................................................................................................\n\nIn this paper, the authors provide a parameter-free version named STORM+ of the STORM algorithm. STORM+ uses the same single-loop recursive momentum (which leads to implicit variance reduction effects) and constant batchsizes as in STORM, but features a parameter-free design by constructing the learning rate \\eta_t and momentum coefficient a_t using past parameters and momentums (as a comparison, STORM needs to tune these two factors manually). Theoretically, the authors show that STORM+ achieves the same near-optimal complexity as STORM but without needing to tune the parameters to ensure this guarantee. My detailed comments are given as follows. \n\nPros: \n1.\tThis paper is easy to following and overall well-written. The motivation is very clear, i.e., replacing the manually tuned learning rate and the momentum coefficients in STORM with adaptive ones based on past iterate information. The proof idea is easy to get based on the sketch in Section 5. Basically, it seems to me that the authors try to add d_i into \\eta_t and a_t so that the resulting convergence results also contain a summation of d_i, and such a summation can be well handled after do the telescoping for the final convergence analysis. Overall, the idea is reasonable to me.\n\n2.\tIt is good to show that the resulting scheme can achieve the same optimal complexity as STORM. Parameter-free optimization and variance reduction are both of great interest to the community, and of course parameter-free algorithm with near-optimal performance guarantee should be of interest. \n\nCons:\n1.\tHowever, I have several concerns on the assumptions and the empirical justification. First, I note that compared to the analysis for STORM, this paper seems to additionally assume that the function value of f is bounded, i.e., max_{x,y\\in R^d} |f(x)-f(y)|<\\infty. As a result, the comparison to STORM in this paper here is not that fair. In addition, this is a very strong assumption as x is allowed to be any vector in R^d, which can be violated, e.g., for simple linear function f(x)=wx. I am wondering whether such value boundedness is necessary for the adaptivity proof. In STORM paper, they assume the gradient is bounded (as also made in this paper) because they can use this assumption to remove the variance factor \\sigma in the learning rate. I am thinking whether this bounded value assumption is further used  to remove other manually tuned parameters? I hope the authors can explain a little bit. \n\n2.\tNo experiments are provided in this paper. Parameter-free optimization is interesting because it will help to eliminate the expensive hyperparameter selection process while achieving the same promising performance. STORM not only achieves the optimal complexity, but also has good practical performance (comparable to Adam). I strongly encourage the authors can test the performance of STORM+ and figure out whether it is comparable to (even better if it can outperform) STORM with the best hyperparameter tuning. I wish to see such a comparison in the authors’ response.\n\nOverall, I feel this paper contains some interesting designs and analysis, but given my concerns in the assumption and the lacking experiments, I cannot accept it currently. However, I am open to increase my score based on other reviewers’ comments and the authors’ response.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Br9hL1Y3cSE", "reviewer": "Reviewer_m4aE", "summary": "This paper is interesting and technically sound. It devises a thoroughly parameter-free algorithm named STORM+, on the basis of STORM. STORM+ obtains the optimal theoretical results and achieves comparable performance with respect to other adaptive methods. The merit of this paper is that it does not require the knowledge of any problem parameters and only initial step-size tuning suffices. ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Perhaps several important findings/conclusions can be better presented in the form of theorems or lemmas, e.g., contents in Line 141-142 and Line 156-159.\n\n2. The meaning of several sentences is not clear (e.g., in Line 209). Careful proofreading is recommended.\n\n3. STORM+ and its simplified ones achieve the optimal rate $\\frac{1}{\\epsilon^3}$. What are the main differences between them? More discussion is needed to make this paper more solid.\n\n4. Detailed derivations of $M_t$ in Line 413 are preferable, as well as $Y_t$ in Line436.\n\n5. All mathematical symbols or operators used in the text are required to be defined.\n\n6. More discussion and comparison between STORM+ and the existing nonconvex stochastic optimization methods are recommended.\n\n7. The reviewer believes that the main conclusions of the article are solid. However, the current version is not suitable for publication and the reviewer would like to suggest the authors to make serious revision to the article in terms of logic, presentation and organization.\n\nTypos: \n\nLine 146: $...\\leq -\\frac{1}{\\eta_T}\\Delta_{t+1} + …$ $\\rightarrow$ $...\\leq -\\frac{1}{\\eta_T}\\Delta_{T+1}+ …$\n\nLine 204: he$\\rightarrow$the\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "More experiments should be conducted to demonstrate the effectiveness of the proposed method.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10h"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper generated a lot of discussion among reviewers. Overall it seems that the contribution is novel and provides an interesting new learning rate schedule meriting acceptance. However, the claims of optimality in the rates are not well-supported. The extra assumption that the objective is bounde above and below may invalidate current lower bounds. 

Decision: Accept (Poster)