META-STORM: Generalized Fully-Adaptive Variance Reduced SGD for Unbounded Functions
Authors: Zijian Liu
Ta Duy Nguyen
Thien Hang Nguyen
Alina Ene
Huy Nguyen
Venue: Submitted to ICLR 2023 (2023)
Keywords: Nonconvex Optimization
Stochastic Optimization
Adaptive Algorithms
Variance Reduction

Abstract: We study the application of variance reduction (VR) techniques to general non-convex stochastic optimization problems. In this setting, the recent work STORM (Cutkosky & Orabona, 2019) overcomes the drawback of having to compute gradients of “mega-batches” that earlier VR methods rely on. There, STORM utilizes recursive momentum to achieve the VR effect and is then later made fully adaptive in STORM+ (Levy et al., 2021), where full-adaptivity removes the requirement for obtaining certain problem-specific parameters such as the smoothness of the objective and bounds on the variance and norm of the stochastic gradients in order to set the step size. However, STORM+ crucially relies on the assumption that the function values are bounded, excluding a large class of useful functions. In this work, we propose META-STORM, a generalized framework of STORM+ that removes this bounded function values assumption while still attaining the optimal convergence rate for non-convex optimization. META-STORM not only maintains full-adaptivity, removing the need to obtain problem specific parameters, but also improves the convergence rate’s dependency on the problem parameters. Furthermore, META-STORM can utilize a large range of parameter settings that subsumes previous methods allowing for more flexibility in a wider range of settings. Finally, we demonstrate the effectiveness of META-STORM through experiments across common deep learning tasks. Our algorithm improves upon the previous work STORM+ and is competitive with widely used algorithms after the addition of per-coordinate update and exponential moving average heuristics.

Under review as a conference paper at ICLR 2023
META-STORM: GENERALIZED FULLY-ADAPTIVE
VARIANCE REDUCED SGD FOR UNBOUNDED FUNC- TIONS
Anonymous authors Paper under double-blind review
ABSTRACT
We study the application of variance reduction (VR) techniques to general non- convex stochastic optimization problems. In this setting, the recent work STORM (Cutkosky Orabona 2019) overcomes the drawback of having to compute gra- dients of 'mega-batchess that earlier VR methods rely on. There, STORM utilizes recursive momentum to achieve the VR effect and then later made fully adaptive in STORM+ (Levy al. (02T), where full-adaptivity removes the requirement for obtaining certain problem-specife parameters such as the smoothness of the ob- jective and bounds on the variance and norm of the stochastic gradients in order to set the step size. However, STORM+ crucially relies on the assumption that the function values are bounded, excluding large class of useful functions. In this work, we propose moves this bounded function values assumption while still attaining the optimal convergence rate for non-convex optimization. META-STORM not only main- tains full-adaptivity, removing the need obtain problem specific parameters, but also improves the convergence rate's s dependency on the problem parameters. Fur- thermore, METAA-TTRR. can utilize large range parameter settings that sub- sumes previous methods allowing for more flexibility in wider range of settings. Finally, we demonstrate the effectiveness of across common deep learning tasks. Our algorithm improves upon the previous work STORM+ and competitive with widely used algorithms after the addition of per-coordinate update and exponential moving average heuristics.
a generalized framework of STORM+ that re-
through experiments
INTRODUCTION
In this paper, we consider the stochastic optimization problem in the form
min F(x) = Eg-D (x, FER
(1)
where F; R2 R. is possibly non-convex. We assume only access to a first-order stochastic oracle via sample functions f(x E), where comes from a distribution D representing the randomness in the sampling process. Optimization problems of this form ubiquitous in machine learning and deep learning. Empirical risk minimization (ERM) is one instance, where F(z) is the loss function that can be evaluated by sample minibatch represented by
An important advance in solving Problem is the recent development of variance reduction (VR) techniques that improve the convergence rate to critical points of vanilla SGD from O(1/T1/4) to O1133//33 (Fang al. 2018 Li et al. 2021 for the class of mean-squared smooth functions (Arjevani et al. (2019). In contrast to earlier VR algorithms which often require the computation of the gradients over large batches, recent methods such as (Cutkosky & Orabonal (2019); Levy et al. 2021): Huang et al. (2021) avoid this drawback by using weighted average of past gradients, often known as momentum. When the weights are selected appropriately, momentum reduces the error in the gradient estimates which improves the convergence rate.
A different line of work on adaptive methods (Duchi et al. 2011 Kingma & Ba 2014). some of which incorporate momentum techniques, have shown tremendous success in practice. These adap-

---

Under review as a conference paper at ICLR 2023
Table 1: Comparison of the convergence rate after T iterations under constant success probability. The as- sumptions and definitions of the parameters referenced can be found in Section 1.2 used all algorithms, thus we leave them out from the table.
Assumptions 1 and 2 are
Methods
Adaptive?
Convergence rate
Assumptions
g1/3 0 2124, 1/2 1/ +
STORM Cutkosky &
x
T1/2
11/3
3', 4
== ==0(((F(r))- - =}))
Orabona 2019
Super-ADAM Huang et al. 2021
0 ((n2/2+ +ologg)
(7tV Tt13)
X
K (= F)))
3
Does not adapt to
0 (7ilz Ni
mggl18)
71/2 + 9//3
STORM+ (Levy 2021
3',4 6
al.
K1 = 0 (30/4 + 30 + +30/22 + B018))
R2 0 (3312 + -B3//)
o (m1 22 log (1+ + o²²r) TpIp + 01/3
META-STORM-SG. (Ours])
T173
3.4
K1 (P(x)) - F¹ + 0² + 82 + 1iz log K22
22 = O((1 + (3) 0 + + R2 ko (1 ooT)) ri/ + o1/3
META-STORM, p (Ours)
11/3
3,5
N1 = 0 - F 6o + 0² ط3 K2 k2)
N2 = 0(1++0))))
tive methods remove the burden of obtaining certain problem-specific parameters, such smooth- ness, in order to set the right step size to guarantee convergence. STORM+ (Levy et al. (02T is the first algorithm to bridge the gap between fully-adaptive algorithms and VR methods, achieving the variance-reduced convergence rate of O(1 (1//T1/3) while not requiring knowledge of any problem- specific parameter. This is also the first work to demonstrate the interplay between adaptive momen- tum and step sizes to adapt to the problem's 's structure, while still achieving the VR rate. However, STORM+ relies on a strong assumption that the function values are bounded, which generally does not hold in practice. Moreover, the convergence rate of STORM+ has high polynomial dependencies on the problem parameters, compared to what can be achieved by appropriately configuring the step sizes and momentum parameters given knowledge of the problem parameters (see Section 3.1.
and META-STORM, two flexible algorithmic frameworks that attain the optimal variance-reduced convergence rate for general non- convex objectives. Both of them generalize STORM+ by allowing wider range of parameter selec- tion and removing the restrictive bounded function value assumption while maintaining its desirable fully-adaptive property eliminating the need to obtain any groblem-specing parameter. These have been enabled via our novel analysis framework that also establishes a convergence rate with much better dependency on the problem parameters. We present a comparison of META-STORM and its sibling META-STORM-SG against recent VR methods in Table [ the appendix, we pro- pose another algorithm, META-STORM-NE with even less restrictive assumptions; however, with a tradeoff of losing the adaptivity to the variance parameter.
Our contributions: In this work, we propose
We complement theoretical results with experiments across three common tasks: image classi- fication, masked language modeling, and sentiment analysis. Our algorithms improve upon the pre- vious work, STORM+. Furthermore, the addition of heuristics such as exponential moving average and por-coordi updates improves our algorithms' generalization performance. These versions of algorithms are shown to be competitive with widely used algorithms such as Adam and Adam W.
2

---

Under review as a conference paper at ICLR 2023
1.1 RELATED WORK
Variance reduction methods for stochastic non-convex optimization: Variance reduction is in-
troduced for non-convex optimization SylAllee-ZZee Bhulnn-Zhu& & Hazan (2016); Reddi et al. (2016) in the con- text of finite sum optimization, achieving faster convergence over the full gradient descent method.
These methods are first improved by Lei et al. (2017) and later by [Fang et al. (2018) [i et al. (202T) both of which achieve an ((1/T1/3) convergence rate, matching the lower bounds in Arjevani al. (019). However, these earlier methods periodically need to compute the full gradient (in the finite- sum case) or a giant batch at a check point, which can be quite costly. Shortly after, [Cukkosky & Orabona (2019) and Tran- Dinh et al. (2019) introduce a different approach that utilizes stochastic gradients from previous time steps instead of computing the full gradient at a checkpoints. These methods are framed as momentum-based methods as they are similar to using a weighted average of the gradient estimates to achieve the variance reduction. Recently, SUPER-ADAS
(Huang et al.) 2021) integrates STORM in larger framework of adaptive algorithms, but loses adaptivity to the variance parameter a. At the same time, STORM+ (Levy et al. 2021 proposes a fully adaptive version of STORM, which our work builds upon.
Adaptive methods for stochastic non-convex optimization: Classical methods, like SGD (Ghadimi & Lan 2013), typically require the knowledge of problem parameters, such as the smooth- ness and the variance of the stochastic gradients, to set the step sizes. In contrast, adaptive methods (Duchi al.) 2011] Tieleman et al., 2012 Kingma & Baj 2014) forgo this requirement: their step sizes only rely on the stochastic gradients obtained by the algorithms. Although these adaptive methods are originally designed for convex optimization, they enjoy great successes and popular- ity in highly non-convex practical applications such as training deep neural networks, often making them the method of choice in practice. As a result, theoretical understanding of adaptive methods for non-convex problems has received significant attention in recent years. The works by Ward et al.) (2019); Kavis et al. (202T) propose convergence analysis of AdaGrad under various assumptions. Among VR methods, STORM+ is the only fully adaptive algorithm that does not require knowledge of any problem parameter. Our work builds on and generalizes STORM+, removing the bounded function value assumption while obtaining much better dependencies on the problem parameters.
1.2 PROBLEM DEFINITION AND ASSUMPTIONS
We study stochastic non-convex optimization problems for which the objective function F: Rd R that has form F(z)= == EE-D [xx {)] and f(,g) is a sampling function depending on a ran- dom variable & drawn from a distribution D. We will omit the writing of 'D in Eg-D (x, {)] for simplicity in the remaining paper. ||
represents || lla for brevity, [T] is defined as {1, 2, ... .T.
The analysis of our algorithms relies on the following assumptions 1-5:
1. Lower bounded function value: Fx := ::inn inf F(x)= > -0.
2. Unbiased estimator with bounded variance: We assume to have access to (x, satisfying
Eg [Vf(x; {)] v (zx)), E& [I]] [=))]] < O² for some 2 0.
3. Averaged f-smoothness: E&g [I[] (f( B² u1 y ER
4. Bounded stochastic gradients: [V < G, Vr E Rd (upport(D) for some G 2 0.
5. Bounded stochastic gradient differences: [v))) vf(xg')) I 20, Vr R support(D) (D) for some δ 2 O.
Assumptions 1, 2 and 3 are standard in the VR setting (Arjevani et al. 2019). Assumption 5 is weaker than the assumptions made in the prior works based on the STORM framework (Cutkosky & Orabona 2019 Levy et al. (02T). These works assume that the stochastic gradients are bounded, i... Assumption 4. We note that assumption 4 implies that assumption 5 holds by replacing ă by G. thus we only have to consider ā = O To better understand assumption 5, we fix & e support(D) and consider another g¹ DD, then due to the convexity of || (1,,\/V/(xx())VFF V/r)) = [V]((, - Eg [V V[(z || < Ber [[[V ((. E V gY'l] < 27. This means assumption 5 implies stronger version of assumption 2. For this reason, we can consider a = O(
This bound holds when ²² and T large enough.
3

---

Under review as a conference paper at ICLR 2023
Algorithm 1 META-STORM-SC
Algorithm 2 META-STORM
Input: Initial point 21 E R
Input: Initial point 21 E F
Parameters: do, bo, 7.P E 1 2b 2g =1 Sample E ~ D, d1 -V (Z1
Parameters: do, bo, p/P E 3 2
_ 2
Sample E ~ D. Vf) =1
for ( = 11=1... 1, ' do:
for f = 1,... 7 do:
a++1 = 1 + Ei=1 [
b. = (8))
Σ ||d:|l2)//
og
I++1 = It b.
" de
by = (bg + Σ ||d:12)0/aa/
Sample E1+1 ~ D
Fe+1 = It- di
a++1 1 + Ei=
[V((a)))) v ((
Sample f6-1 ~ D
o V d+1 = ( + a++1((de
d++1 = V (( + a++1)(de
(((r)((+11)
(x+1)
end for
end for
Output Tout Ie. where & Uniform ((7).
Output Tont = Jy where t Uniform ([T).
Additional assumptions made in the prior works (Cutkosky & Orabona 2019 Huang et al. (021) include the following:
Levy et al. 2021
3'. Almost surely 8-smooth: [V {) - Vf(y, E)Il S - ull, Vx, E , & support(D).
6. Bounded function values: There exists B 2 0 such that
- B for all x. y R.
We remark that 3' is strictly stronger than 3 and it is NOT a standard assumption in Arjevani et al. (211)). Moreover, assumption 6, which plays critical role the analysis of Levy al. (2021). is relatively strong and cannot be always satisfied in non-convex optimization. Our work removes these two restrictive assumptions and also improves the dependency on the problem parameters.
OUR ALGORTHTM
In this section, we introduce two main algorithms, META-STORM-SC and META-STORM, shown in Algorithm Tand Algorithm 2 respectively. Our algorithms follow the generic framework of momentum- based variance-reduced SGD put forward by STORM (Cutkosky & Orabona 2019).
The STORM template incorporates momentum and variance reduction as follows:
de = ae (t) + (1 (1- az) d + (1 - at) (V {t) - ()(=;11)
(2)
momentum
variance redluctio
R+41 = D4
de b
(3)
The first variant, META-STORM-SG, similar prior works, uses the gradient norms when setting a, and similarly, requires the strong assumption on the boundedness of the stochastic gradients. The major difference lies in the structure of the momentum parameters and the step sizes and their relationship, which is further developed in the second algorithm META-STORM so that assumption 4 can be relaxed to assumption 5. We now highlight our key algorithmic contributions and how they depart from prior works.
first point of departure our use of stochastic gradient differences when setting the momen- tum parameter a, in META-STORM: prior works set based on the stochastic gradients, while META-STORM sets at based on the difference of two gradient estimators taken at two different time step & and & at the same point Tz-1- The gradient difference can be viewed as a proxy for the variance o², which allows us to require the mild assumption in the analysis. With this choice, our algorithm obtains the best dependency the coefficient a++1 in the update for d now depends on & and addressing this correlation requires more careful analysis. The second point of departure is the setting of the step sizes b, and their relationship to the momentum parameters in both META-STORM-SC and META-STORN
the problem parameters. On the other hand,
We propose general update rule b, (b)/r + Σi= | /af that allows for broad range of choices for p and that subsume prior works. In practice, different problem domains may ben- efit from different choices of p and g. Our framework allows to capture prior works such as
4

---

Under review as a conference paper at ICLR 2023
the STORM+ update b, = -Ei= ||d:|2/a,+] (1////+4)/// 1// using different but related choice of momen- tum parameters and a simpler update that uses only the current momentum value a, instead of all the previous momentum values d++1 with i I t. We further motivate and provide intuition for We note that our algorithm uses only the stochastic gradient information received, and it does not require any knowledge of the problem parameters.
our algorithmic choices in Section 3
We provide an overview and intuition for our algorithm in Section 3 and give the complete anal- ysis in the appendix. Our analysis departs significantly from prior works such as STORM+, and allows us to forgo the bounded function value assumption and improve the convergence rate's de- pendency on the problem parameters. It remains an interesting open question determine the best convergence rate that can be achieved when the function values are bounded.
We can further alleviate assumption 5). provided in Section H in the appendix. To the best of our knowledge, META-STORM-NA is the only adaptive algorithm that enjoys the convergence rate (11/71/3) under only the weakest assumptions 1-3. It also allows wide range of choices for E (0, 2 However, the tradeoff is that the algorithm does not adapt to the variance parameter a. For the detailed analysis, we refer readers to Section H
another new algorithm, META-STORMA- (Algorithm
Finally, we show the convergence rate obtained by Algorithms [ad in the following theorems. The convergence rates for general are given in the appendix.
Theorem 2.1. Under the assumptions 1-4 in Section 1.2 with the choice = 2 and setting dg =
bo --= to simplify the final bound, META-STORM SG ensures that
E V F 11 -0 Wi1 (0²T) < W1]
02/9
(W2 W3 log (1 (1+
T1/3
71/3 T2/9
where W1 = OFF(m() F C + (1) log (3 (3+ 3)3)). W₂ 2/3
04/3 G4/3 + (1+ (2/3) log"
(5 20
3)) and W ((1 (743))8211))
We note that when o2 and T is large enough, the effect of W1 can be eliminated. Combining Theorem and Markov's inequality, we immediately have the following corollary.
Corollary 2.2. Under the same setting in Theorem 2.1 additionally we assume o² > 0 and T is large enough, then for any 0 < 5 < 1, with probability
IV || S 50( Ki + K2 log (1 + TT))
01/3)
T1/2 + T1/3)
83/2
where K1 = (F((x)) - Fm + 02 + 62 + K2 log and K2 = O(11 + (2)
Theorem 2.3. Under the assumptions 1-3 and 5 in Section 1.2 with the choice and setting
40 bo = 17 = to simplify the final bound, META-STORM ensures that
0217
E IVF (Iout) [$] = (2 (1 (1+o2T))
T3/T
T2/7
where Qı -F())))F=)))) 6/7
677 + (00) 6/7 12/7 18/7 /7 + +(1+ (1+318/7 30/7 log 6/T log (8 + G*1))
and Q2 = (110(((11 11877) (11/7) g0/T).
Combining Theorem 2.3 and Markov's inequality, also have the following corollary.
Corollary 2.4. Under the same setting in Theorem 2.3 then, for any 0 < 8 < 1, with probability
1-8
F || 0 16 + K2 log (1 OT)
71/2 + o 01/3)
87/6
T1/33
where K1 = O((((z)) - F" + Go + + K2 log k2) and K2 = (1+ ((1
We emphasize that the aim of our analysis is provide convergence in expectation with constant probability. In particular, we state Corollaries 2.2 and 2.4 only to give a more intuitive way to see the dependency on the problem parameters. To boost the success probability and achieve log & dependency on the probability margin, a common approach is to perform log independent repetitions of the algorithms.
5

---

Under review as a conference paper at ICLR 2023
We briefly discuss the difference between the convergence rate of the two algorithms. We note that these two rates cannot be compared directly since assumption 4 is stronger than assumption 5. Additionally, as pointed out in Section 1.2. we have ã = o(õ) and thus the term O in Corollary 2.4 is O(G)), whereas Corollary 2.2 has O(C²) term. To give an intuition why an extra higher order term W1 appears in Theorem 2.1 when a = compared with Theorem 2.3 we note that when O, de in both algorithms degenerates to (2+,). However, the coefficient dz-1 becomes 1 in META-STORN but does not in META-STTORM-S.. This discrepancy leads to by being larger in META-STORM- than in META-STORM, and moreover the META-STORM by becomes exactly the same as the stepsize used in AdaGrad. Due to the larger b, when a = O, it is reasonable to expect slower convergence rate for METTA-SOOR--SG. The appearance of the term Wi reflects that.
OVERVIEW OF MAIN IDEAS AND ANALYSIS
In this section, we an overview of our novel analysis framework. We first give a basic von-adaptive algorithm and its analysis motivate the algorithmic choices made by our adaptive algorithms. We then discuss how to turn the con-adaptive algorithm into an adaptive one. Section Djnn the appendix gives a proof sketch for Theorem 2.3 for the special case p = y that illustrates the main ideas used in the analyses of all of our algorithms. We give the complete analyses in the appendix.
3.1 NON-ADAPTIVE ALGORITHM
As a warm-up towards our fully adaptive algorithms and their analysis, we start with a basic non- adaptive algorithm and analysis that will guide our algorithmic choices and provide intuition for our analysis. The algorithm instantiates the STORM template using fixed choices as = and b = outline an analysis for the algorithm and for the momentum and step size. In the following.
derive appropriate choices for the values a and b.
Algorithm: As noted above, the algorithm performs the following updates:
Tt+1 = Zt b de;
de-1 = (f(++111++)) + (1 a)(4; Vf (++1)).
To make it simpler, we assume d1 = Fx1)). Alternatively, one can use a standard mini-bated
setting set d, D V Vf(r; E with proper m leading to small variance in previous
non-adaptive analysis (Fang et al. 2018
Zhou et al. 2018 Tran-Dinh et al. 2019).
Key idea: We start by introducing some convenient notation. Let de V FF(4 ((:)) be the stochastic error (in particular, é 0) and
H = Σ IVF(()))
D. =
||
E,
First, to bound EE []] ( where Tour is an iterate chosen uniformly at random, it suffices to up- per bound E [. Then, can translate this term convergence guarantee for E. [ (Fow)) I[]- An important intuition from STORM/STORM is the incorporation of VR in (2). leading to a de-
crease over time of the error term et. Thus, we can view d, as a proxy for V FI(e). It is then natural to decompose Hr in terms of Dy and ET. By the definition of ér, we can write H7 < 2Dr +ET. Therefore, to upper bound [[ it suffices to upper bound E[[ry.] and EE [E J. which will be the essential steps in the analysis framework. A key insight is that E D and E Ey] can be upper bounded terms of each other, as we now show.
Bounding Dy: Starting from the function value analysis, using smoothness, the update rule rz+1 Ft de. the definition of & = d, F((.). and
we obtain
3
F( - F(x.) < (VF F++1 22) +
|
xell2 (VF())),
d.)
||de|]
II
26
-
1 |dl, 1|
1 (c,, de) +
8
|del
-5
1
|dell
+
1
|
2
/
||eel
2
26
26
262
Suppose that we choose b so that b > 233, which ensures that 25
8
4b By rearranging the previous
1
inequality, summing up over all iterations, and taking expectation, we obtain
E Dr] 4bR (F()) F(TT+1)) 2E [r] < 4b (F(m1)
F²) + 2F ET].
(4)

---

Under review as a conference paper at ICLR 2023
Bounding Ey: By the standard calculation for the stochastic error e, used in STORM, have
+ 2(1 a) 282
E [||-=1l s (1
[|c
b2 E || I1] + 2a²
Summing up over all iterations, rearranging. and using that a E [0, 1] and O. obtain
E E 1- (1 a)² (2(1 a)² 82 E 22² By combining inequalities and obtain
2
E
D 200²T. (5)
ab
4
E D
4b (F(1)) F*)
E
[Dr] ] + 4a0 2a;
ab?
83 (F(x)) F*) ab
43
F.
[ET]
+ 200 200
ab
Ideal non-adaptive choices for a, Here, we set a and b to optimize the overall bound, and obtain choices that depend the problem parameters. In the next section, build upon these choices to obtain adaptive algorithms that use only the stochastic gradient information received by the algorithm.
We observe that 6 and (7 bound E[Dr] and [E(Er] in terms of themselves, and the coefficient on Suppose that set that this coefficient is 1 ie., we set 8.92
the right-hand side is ab2
4.9
82
so that 4,3
(note that this requires setting b 2 2v23, that 1). By plugging this choice
ab
into and we obtain
Drl,E(Er S FF POPT
b²
The best choice for b is the one that balances the two terms above: = 0 also need b 2 ((3),, set to the of the two. Hence, obtain
1/3
Since we
F(a1)-Fr
(+ ( 0
θ 12
(8)
2/3 (02T)2(3)
b = (B+ (F()) 1/3):
(9)
E CDD] E
Hr] ((8(F(()) - (8(F(z1) -F 2/3 (0)2)) 113)
F²))2/3
(10)
3.2 ADAPTIVE ALGORITHM
In this section, we build on the non-adaptive algorithm and its analysis from the previous section. We first motivate the algorithmic choices made by our algorithm via a thought experiment where pretend that Hr. Dr. Ey are deterministic quantities.
Towards adaptive algorithms: To develop an adaptive algorithm, we would like pick a, b without an explicit dependence on the problem parameters by using quantities that the algorithm can track. We break this down by first considering choices that do not depend on B, but on a, and then removing the dependency quantities. A natural choice for a that mirrors the non-adaptive choice ( is = (1 + ooT" 2/3 Since we are pretending that Dr deterministic quantity, we can set by inspecting (5)
As thought experiment, let us pretend that Hr. Dr, Er are deterministic
3
232 ab
ET
DT 2200"T
=D. we set b = D1/22/22//// //4/4, we ensure that Dy cancels and we obtain desired upper bound on ET.
More precisely, by plugging in (1+ T2T) and 1/2 // into 5), obtain
1/22DT Dr + 2T s 00 (1 2T) 1/3 + +1+00 + T2T) 1/3)
232
Ex
7

---

Under review as a conference paper at ICLR 2023
We now consider two cases for Dr- If Dr < 163 TT the above inequality together with Hr I 2Dr + 2Er imply that Hr I ((1 + + 037)1/3). Otherwise, we have Dr 2 16 + 0TT)// and thus ab² 2 16 Plugging into 66.. we obtain
Dr O(VD Dr (1+ 1/6 (F(z1) - F(x))) + +11+ (1+
which solves D, I O((1 (FT)) F*))). We again bound Hr using Hy 1 2Dr + 2E,. In both cases, we have the bound
Hy 50((
(F( =イ)²) (
We now turn to removing the dependency on o'T in a. The algorithm can also track Hy == T
E [ Et) (rx f++1) which can be viewed as proxy for p²T. Replacing r& by this proxy and making a and be time dependent give the update rules employed by our algorithm in the special case 2. Our update rule for general p follows from similar thought experiment.
Using a similar approach as the non-adaptive analysis, we can turn the above argument into a rigorous analysis. In the appendix, we give the complete analysis as well proof sketch in Section D that gives an overview of our main analysis techniques.
Analysis:
EXPERIMENTS
We examine the empirical performance of our methods against the previous work STORM+ (Levy al. ) and popular algorithms (Adam, AdamW, AdaGrad, and SGD) on three tasks: (1) Image
classification with the CIFARIO 10 dataset (Krizhevsky et al.) 2009) using ResNet18 (Ren et al. 2016)
models; (2) Masked language modeling
the BERT pretraining loss (Devlin et al. 2018) with
the IMDB dataset (Maas et al.] (011) using distill- -ERT models (Sanh et al., 2019 D. where we employ the standard cross entropy loss for MLM fine tuning (with whole word masking and fixed test masks) with maximum length 128; and (3) Sentiment analysis with the SST2 dataset (Socher cet al. 2013) via finetuning BERT models (Devlin et 2018). We use the standard train/validation split and run all algorithms for 4 epochs.
We use the default implementation of AdaGrad, Adam, AdamW, and SGD from Pytorch. For STORM+, we follow the authors' original implementation! We give the complete implementation details and tables of hyperparameters for all algorithms Section of the Appendix.
Heuristics. For our algorithms and STORM+, we further examine whether heuristics like exponen- tial moving average (EMA) of the gradient sums (or often called online moment estimation) and per-coordinate update would be beneficial. The versions with heuristics is denoted (H) in the results below. This discussed in full details Section Section[B.I.]] of the Appendix.
Results. We perform our experiments on the standard train/test splits of each dataset. We tune for the best learning rate across fixed grid for all algorithms and perform each run times. For readability, we omit error bars in the plot. Full plots with error bars and tabular results with standard deviation as well as further discussions are presented in Scction B.2 of the Appendix
1. CIFARIO (Figure[) Overall, META-STORM-SC achieves the lowest training loss with META- STORM and STORM+ coming in close. META-STORM with heuristics attains the best test accu- racy, with Adam coming in close.
2. IMDB (Figure
[). Adam W attains the best training loss. However, META-STORM with heuris- ties achieve the best test loss (with AdamW W coming in close). algorithms outperform STORM in both minimizing training loss and test loss.
and the heuristic
3. SST2 (Figure 3. META-STORM with heuristics attain the best training loss and accuracy, above Adam and Adam W. also achieves the best validation accuracy out of all the algorithms. Furthermore, non-heuristic META-STORM and META-STORM.S. outperform STORM+. We
Link to the code of STORM+; https:/ / / thub. com/ LONS- RPP sttor//tttm/ppp// code 'The reader should keep in mind that crraacce-reduee algorithms like -TOTRM require twice the amount of gradient queries, so the improvement in performance that algorithms exhibit does not come without cost. Additional plots and further discussions are available in Section B
8

---

Under review as a conference paper at ICLR 2023
remark that STORM+ appears to be rather unstable for this task as of the random do not converge to good stationary points.
Accurry
2.04
META-STORMA SG (MI
METAISTORE STOM (M]
META-S META-STORM-C
META-STORM
2.90
STOROS+
STORM
METASTORM 5C (K)
8.16
META-STORM
SCD
2.06
META STORM
STORM
5.00
STORM-
STORM
1.82
SCD
100
40
100
Eaoch
Epoch
Figure 1: Training loss and test accuracy on CIFARIO. (H) denotes the addition of heuristics.
Trote
ORO
METIA STORM STORN
255
META-STDEM
META-STORM
STORMS- (N)
STORM-
230
8
5.00
Adagod
Adaged
Adore
SGD
1.90
Adantty
1:56
Figure 2: Training loss and test loss on IMDB. (H) denotes the addition of heuristics.
Truis Lut
Vall Acconecy
0.30
META STORM SG. (1)
META-STORM (H)
META-STORM
STRA-STORM
STORM-
STORM-
META STORM
META-STORM (HI
0.20
SED
Adagrad
2.00
STORM
METASTORM-5C
META-TORM
3:84
5.30
5.00
SCD
Adart))
1/5
2/
3.2
400
Eacch
Epoch
Figure 3: Training loss and validation accuracy on SST2. (H) denotes the addition of heuristics.
CONCLUSION
In this paper, we propose META-STORM-SG and META-STORM, two fully-adaptive momentum- based variance-reduced SGD frameworks that generalize upon STORM+ and remove STORM+'s restrictive bounded function values assumption. META-STORM and its sibling META-STORM-SC attain the optimal convergence rate with better dependency on the problem parameters than previous methods and allow for wider range of configurations. Experiments demonstrate our algorithms' effectiveness across common deep learning tasks against the previous work STORM+, and when heuristics are further added, achieve competitive performance against ofate-of-the-ee algorithms.

---

Under review as a conference paper at ICLR 2023
Reproducibility Statement. We include the full proofs of all theorems in the Appendix. For experiments, full implementation details including hyperparameter selection and algorithm devel- opment are included in Section B of the Appendix. We also make our source code available.
REFERENCES
Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In International conference on machine learning, pp. 699-707. PMLR, 2016.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv: vrrXiv/991..00 1912.02365, 2019.
Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex sgd.
Advances in neural information processing systems, 32, 2019.
Jacob Devlin, Ming- Ming-Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint
2018.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex op- timization via stochastic path integrated differential estimator. arXiv preprint arXiv:1807.016% 2018.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal on Optimization, 23(4):2341-266 2013.
methoss
Feihu Huang, Junyi Li, and Heng Huang. Super-adam: Faster and universal framework of adaptive gradients. arXiv preprint arXiv:2 106.08208, 2021.
Ali Kavis, Kfir Yehuda Levy, and Volkan Cevher. High probability bounds for a class noncon- vex algorithms with adagrad stepsize. In International Conference on Learning Representations, 2021.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.69888 6980, 2014.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite-sum optimization via scsg methods. Advances in Neural Information Processing Systems, 30, 2017.
Kfir Levy, Ali Kavis, and Volkan Cevher. Storm+: Fully adaptive sgd with recursive momentum for nonconvex optimization. Advances in Neural Information Processing Systems, 34, 2021.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. Page: A simple and optimal prob- abilistic gradient estimator for nonconvex optimization. International Conference on Machine Learning, pp. 6286-6295, PMLR, 2021.
Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 142-150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics. URL http:
// //www. www.ww.ww............ owg. http://aahhooooooloollll
Sashank Reddi, Ahmed Hefny,, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International conference on machine learning. pp. 314 323. PMLR, 2016.
Shaoqing Ren, Jian Sun, K He, and X Zhang. Deep residual learning for image recognition. In CVPR, volume 2, pp. 4, 2016.
10

---

Under review as a conference paper at ICLR 2023
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint arXiv:1910.01108, 2019.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng, a sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pp. 1631-1642 Seattle, Washington, USA, October 2013. Association for Computa- tional Linguistics. URL https: / https///c/aaaaaooooooo/////11111
and Christopher Potts. Recursive deep models for semantic compositionality
Tijmen Tieleman, Geoffrey Hinton, et al. Lecture 6.5-rmsprop: Divide the gradient by running average its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
Quoc Tran-Dinh, Nhan H Pham, Dzung T Phan, and Lam M Nguyen. Hybrid stochastic gradi- ent descent algorithms for stochastic nonconvex optimization. arXiv preprint 1rXiv:1905.05920 2019.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. In International Conference on Machine Learning, pp. 6677-6686. PMLR, 2019.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization, Advances in Neural Information Processing Systems, 31, 2018.

---

Under review as a conference paper at ICLR 2023
A
APPENDIX OUTLINE
The appendix is organized as follows.
Section B presents the full implementation details for our algorithms and hyperparameters used. This section also includes additional ablation studies and experiments.
Section introduces the notations used in the analysis of our algorithms.
Section CaciionDDrreee presents the proof sketch of Theorem 2.3
Section establishes some basic results that are used our full analysis.
Section
F
gives the analysis of META-STORM for general p.
Section gives the analysis of META-STORM-SG for general p.
Section Introduces META-STORM-NA and gives the analysis for general p.
Section I gives several basic inequalities that are used in our analysis.
B EXPERIMENTAL DETAILS AND ADDITIONAL EXPERIMENTS
In this section, we present the complete implementation details along with the full experimental setup. All of experiments were conducted on NVIDIA RTX3090.
B. IMPLEMENTATION DETAILS AND HYPERPARAMETER TUNING
In this section, we present the full implementation details of the heuristics version, parameter selec- tion, and hyperparameter tuning for all 3 datasets.
B.1.1 HEURISTICS VERSIONS OF META-STORM, AND META-STORM-SC
Algorithm 3 Heuristic update of META-STORM and META-STORM-SG.
G, aG. 4 ( ()(z, (())) 1 (z),
for META-STORM (H)
for META-STORM-SG (H)
a++1 (1+ Gr/ag) -2/3
Dt = aD,-1 + (1 - a)
1/1 + Dt) ///
for META-STORM (H)
b. =
1/1 + D.)
/a
for META-STORM-SG (H)
! de
Zt+1 = It
by
d+1 V v((141,(441) + (1-441)(d: ((())
12

---

Under review as a conference paper at ICLR 2023
Algorithm 4 Heuristic update of STORM+
G. = -G: +
(t)
d++1 = (1 (L+///o0)
di
D; aDi-1 + a)
a++1
b. = (bo + Di) -1/3
2++ = bt di
d+1 ((41) (1 a411((4 Vf((x,
For our algorithms, we employ the common heuristic of using an exponential moving average (EMA) scheme in the momentum and the step size. We also perform a per-coordinate update instead of simply using the norm. With this, our update rules for 2++1 I₁ nd,/b, becomes coordinate- wise division with the update rules in Algorithm
3 where all the operations between vectors here are coordinate-wise multiplication, exponentiation, and division. our experiments, we set 0.99, do L, bo 10 as selected by the criterion detailed next. Similarly, also examine the same heuristics on STORM+ via an analogous implementation in Algorithm
B.1.2 ALGORITHM DEVELOPMENT AND DEFAULT PARAMETERS SELECTION
We develop our algorithm on MNIST and tune for p, do, and by. For dg, we tune on MNIST across range of values from 1 to 10 and found that larger values of an are helpful. For bo, we simply need a small number for numerical stability so we pick 10-8 For the heuristic versions of our algorithms, ag = gives the best results. This might be due to the effects of per-coordinate operations removing the need scale down the aundient-accumulater step-size.
Effects of varying p. In Figures 4 and we show the training loss and test accuracy of different values of p of algorithms on MNIST (with ag 10a and by 10-8). For each configuration, we tune the base learning rate across { (10-3, 10 1.-3.10 100-2.00 10-111,, 10} The results suggest that the lower values of tend to perform better. While = 1/3 has comparable performance to the lowest setting of p, this choice is somewhat analogous to STORM+. Hence, we select the lowest possible value p for our algorithms in the subsequent experiments (with p = 0.20 for META-STORM and 0.25 for META-STORM-SSG)
0.40
1.20
9/20
0.50
1/3
Tran
0.20
0.15
9/20
1/5
0.35
0
10
20
50
10
20
30
40
50
Epoch
Epoch
Figure 4: Training loss and test accuracy for META-STORM on MNIST for different p. values A For the heuristics versions of our afgorithins, we perform the same experiments and show the results in Figures and Since p 0.50 attains the lowest training loss for both heuristics versions of our algorithms, we select such value for all our experiments.
Default parameters.
13

---

Under review as a conference paper at ICLR 2023
Trin oo
Text Areuraty
0.35
1/2
2/5
1/4
0.88
0.25
Tran
0.20
0.97
1/2
0.86
2/5
0.10
0.96
10
Figure 5: Training loss and test accuracy for META-STORM-SG on MNIST for different values.
Train Loss
Text Aucuraty
0.55
1/2
9/20
2/5
0:30
1/5
Accurscie
Trin
0.20
0.37
1/2
0/20
0.96
2/5
0.10
0.90
10
20
D0
10
20
50
Coech
Opoch
Figure 6: Training loss and test accuracy for META-STORM (H) on MNIST for different values.
Table 2: Default parameters for META-STORM algorithms and STORM+. The version with heuris- ties is denoted with an additional (H).
Algorithm
p
Ap
bp
META-STORM
0.20
0g =10
1// -10
META-STORM-SG
0.25
ag =10
b =10
META-STORM (H)
0.50
o3 =1
b =100 8
META-STORM SG (H)
0.50
of =1
///0 =10
STORM+
N/A
0g
# of parameters
bo
STORM+ (H)
N/A
1
by 10
The discussion above leads to the choice of ao = 10 and by 10-8 by default for our algorithms with p = 0.20 for META-STORM and = 0.25 for META-STORM-SS on the benchmarks present in this section. For the heuristic versions of META-STORM. 10 for our algorithm with heuristics. This version with heuristics is further denoted (H) in our results below. For STORM+, of parameters of the model (which is roughly 10 for ResNet18 for example) and by = 1. For other baseline algorithms,
p 0.50, ag 1, and by
the original authors' implementation of setting ag to the number
use the default parameters from Pytorch implementation.
Hyperparameter tuning. For all algorithms, we tune only the learning rate while using the default values for the other parameters for all algorithms.
14

---

Under review as a conference paper at ICLR 2023
Trin lo
Text Areuraty
0.35
1/2
2/5
1/4
Acaracies
0.88
0.25
Tran
0.20
0.87
1/2
0.86
2/5
0.10
0.96
10
Figure 7: Training loss and test accuracy for META-STORM-SG (H) MNIST for different p values.
For learning rate tuning, we perform grid search across values {10-5, 10-4, 10-3 10 10-2,10-1,1
for CIFAR10 and IMDB and across values {10-5, 55 2 (due to 2 10-5 being the default learning rate for Adam on SST2 and also more practical due to SST2 being a smaller dataset). For Adam on IMDB, the learning rate in our grid search is not small enough to converge, requiring additional tuning for decreasing training loss.
10-5, 10-4, 10-3, ,,00,,
10100.111 for SST2 10
Table includes the selected learning rate we used for each algorithm across the datasets. After obtaining the best learning rate, we additionally run each algorithm across 5 different seeds to obtain error bars.
Table 3: Table of Hyperparameters.
Algorithm
CIFAR1O
IMDB
SST2
META-STORN
10-2
10-2
META-STORM-SC
10-1
10
META-STORM (H)
10 10-3
10-4
2 10-5
META-STORM (H)
10
10
2- 10
STORM+
10-2
10-2
STORM+ (H)
10 2
10-3
10 10-4
Adam
10
10-6
10
A
N/A
10
10
Adagrad
10-3
10-3
10
SGD
10 10-3
10-2
10-3
10
B.2 FULL RESULTS FOR EXPERIMENTS IN SECTION AND ADDITIONAL EXPERIMENTS
this section, we show complete plots and tabular results along with more detailed discussions for our experiments. The reader should note that STORM-based methods require twice the amount of oracle access over the baselines. The plots show average across seeds along with min/max bars. The tables show the average across 5 seeds across range of selected epochs and standard deviation is included at the last epoch. In the plots and tables below: (H) denotes the version of the algorithm with the heuristics (EMA and per-coordinate update) employed.
B.2.1 CIFARIO: O: RESULTS AND DISCUSSIONS
Figure shows all plots of the main experiments in Section 4 in Figure
15

---

Under review as a conference paper at ICLR 2023
Tran
Low
0.5
0.89
KE STORM (H)
META STORMASC (H]
KETASSOOMA (4)
PIE SEETA-TTRMA (M)
KE TAATSTORISS
0.73
MIE TA STOTHAGG
ME TA-STORM
MIE STORM
STORM (4)
STORM-- (4)
30
STOREE
STORM-
Lo0
Adan
Adamn
Aitgooa
Tooch
Accurzzy
0.53
0.03
3.95
2.69
NETA-STORM-S
0.11
META-STORE STTRA-TORAAS
NETA STORM
0.1
MFTA STORM
NETA STORM
MFTA STORM
IETA STORM
081
META STORM
STORM-
STORM- (11)
STO
0.3
STORM-
Adart
83
Adaged
078
Adugred
SAD
SGD
0.7
20
100
0
20
110
Esock
Excch
Figure 8: Losses and accuracies CIFARIO.
Tables. Tables and 5 show the training loss and accuracy for CIFARIO. Tables and 7 show the test loss and accuracy for CIFAR10.
Table 4: CIFARI0 average training loss across 5 seeds for selected epochs. Lowest loss bolded per selected epoch.
Algorithm
10
20
40
60
70
80
90
100
MS-SG (H)
1.611
0.328
0.154
0.052
0.029
0.023
0.018
0.015
0.01440.004
MS (H)
1,618
0.329
0.153
0.051
0.028
0.023
0.018
0.016
0.014=t0.003
MS-SG
1.899
0.421
0.194
0.053
0.023
0.016
0.014
0.008
MS
1,941
0.441
0.204
0.056
0.023
0.017
0,013
0.010
0.009110001
STORM+ (H)
1.727
0.358
0.167
0.089
0.053
0.037
0.027
0.022
0.018+0.006
STORM+
1.604
0.349
0.177
0.059
0.026
0.019
0.017
0.011
0.009+0.002
Adam
1.452
0.327
0.153
0.052
0.030
0.024
0.021
0.019
0.016=20003
Adagrad
1.359
0.456
0.305
0.164
0.096
0.076
0.059
0.048
0.040=0.002
SGD
1.561
0.441
0.253
0.097
0.044
0.031
0.024
0.019
0.01440.001
16

---

Under review as a conference paper at ICLR 2023
Table 5: CIFARIO average training accuracy across seeds for selected epochs. Highest accuracy is bolded per selected epoch.
Algorithm
10
20
40
60
70
80
90
100
MS-SG (H)
0.405
0.886
0.946
0.982
0.990
0.992
0.994
0.995
0.995=0.000
MS (H)
0.403
0.886
0.946
0.982
0.990
0.992
0.994
0.995
0.995=0.000
MS-
0.317
0.854
0.932
0.981
0.992
0.995
0.995
0.996
0.997=0.001
MS
0,306
0.846
0.928
0,980
0.992
0.994
0.996
0.997
0.997=0.000
STORM+ (II)
0.365
0.876
0.941
0.968
0.981
0.987
0.990
0.992
0.994
STORM+
0.413
0.879
0.938
0.979
0.991
0.993
0.994
0.996
0.997-0.00
Adam
0.468
0.887
0.946
0.982
0.989
0.992
0.993
0.994
0.995=0.000
Adagrad
0.504
0.840
0.894
0.945
0.969
0.976
0,983
0.986
0.988-0.001
SGD
0,423
0.847
0.912
0.966
0.985
0.989
0.992
0.994
0.995=0.000
Table 6: CIFARIO average test loss across 5 seeds for selected epochs. Lowest loss bolded per selected epoch.
Algorithm
10
20
40
60
70
80
90
100
MS-SG (H)
1.272
0.405
0.343
0.386
0.423
0.423
0.456
0.487
0.481 +0.039
(H)
1.250
0.390
0.337
0.390
0.431
0.441
0.444
0.446
0.460++00021
MS-SG
1,553
0.472
0.373
0.437
0.473
0.484
0.501
0.498
0.522:10.034
MS
1,577
0.498
0,379
0.425
0.463
0.490
0.488
0,496
0.506=000016
STORM+ (H)
1.429
0.417
0.342
0.346
0.400
0.405
0.433
0.455
0.451
STORM+
1.321
0.457
0,355
0.385
0.404
0.423
0.443
0.457
0.400
Adam
1.222
0.412
0.335
0.384
0.401
0.432
0.434
0.441
0..022
Adagrad
1.104
0.541
0,468
0.447
0,468
0,476
0.488
0.499
0.502+00.01
SGD
1.315
0.525
0.446
0.425
0.450
0.447
0.471
0.460
0.487+0.011
Table 7:
CIFARIO average test accuracy across 5 seeds for selected epochs. Highest accuracy is bolded per selected epoch.
Algorithm
10
20
40
60
70
80
90
100
MS-SG (II)
0.539
0.867
0.901
0.916
0.923
0.922
0.924
0.924
0.922-000005
MS (H)
0.546
0.871
0.901
0.914
0.918
0.922
0.924
0.925
0.927=0.001
MS-SG
0.427
0.843
0.886
0.902
0.909
0.914
0.913
0.914
0.915=0.004
MS
0.418
0.834
0.883
0.902
0.910
0.913
0.915
0.917
0.918=0.004
STORM+ (H)
0.482
0.861
0.898
0.909
0.911
0.920
0.919
0.919
0.921=0.002
STORM+
0.529
0.852
0.892
0.911
0.918
0.920
0,921
0.922
0.003
Adam
0.574
0.866
0.902
0.913
0.921
0.920
0.923
0.923
0.925
Adagrad
0.601
0,816
0.845
0.862
0.866
0.869
0.868
0.870
0,872=0.003
SGD
0.522
0.825
0.860
0.888
0.897
0.904
0.905
0.909
0.907=0.003
Discussion. META-STORMA achieves the lowest training loss and best training accuracy (with META-STORM and STORM+ coming in close). META-STORM-SG maintains the best training loss and accuracy for longest before the final epoch. For test loss and test accuracy, META-STORM (H) attains the best test accuracy (with Adam coming in close) while Adam attains the best test and META-STORM, achieve low training loss, their generalization
loss. While META-STORM- performance seems worse than their heuristic counterparts.
17

---

Under review as a conference paper at ICLR 2023
To further study this generalization gap among different algorithms, Table shows the generaliza- tion gap of different algorithms. METAA-TORMM, with heuristics and Adam achieve the smallest gap among all the algorithms. For algorithms, the version with heuristics exhibit a smaller gener- alization gap than the version without the heuristics while STORM+ lies between. Interestingly, Adagrad and SGD exhibit larger generalization gaps.
Table 8: CIFAR10 accuracy generalization gap (train acc test acc) of the last epoch's accuracy.
Algorithm
MS-SG/(H)
MS/(H)
STORM+(HH)
Adam
Adagrad
SGD
Test acc 91.7%
91.8%
92.3% 1%
92.5%
87.2%
90.7%
Train acc 99.8%/99.5%
99.7%/99.55% 5%%
99.7%/99.44 44%
99.5%
98.9%
99.6%
Gen gap 8.1%/733%
7.9%/6.8% %
7.4%/773%
7.0%
11.7%
8.9%
B.2.2
IMDB: RESULTS AND DISCUSSIONS
Figure from Section 4 shows the train and test loss of the algorithms used. We include Figure here that includes the error bars across random seeds.
Tables.
Tables
9 and 10 show the train and test loss for our experiments.
Table IMDB average training loss across seeds for selected epochs. Lowest loss for each epoch is bolded below.
Algorithm
2
4
5
6
7
9
10
MS-SG (H)
0.481
0.450
0.435
0.424
0.415
0.407
0.400
0.394
0.389
0.384=+0.011
MS (II)
0.482
0.450
0.435
0.424
0.415
0.407
0,400
0.393
0.389
0.3841100000
MS-SG
0.947
0.483
0.467
0.462
0.458
0.455
0.453
0.452
0.451
0.45011.000
MS
0,503
0.486
0.481
0.478
0.477
0.475
0.474
0.473
0.473
0.472+0.011
STORM+ (H)
0.474
0.447
0.434
0.425
0.418
0.411
0.406
0.401
0.397
0.394++0.010
STORM+
0.495
0.476
0.471
0.466
0,464
0.461
0,460
0.459
0.458
0,458
Adam
0.602
0.514
0.515
0.525
0.536
0.548
0.559
0.568
0.575
0.577#0.013
Adagrad
0.509
0.451
0.441
0.435
0,431
0.428
0,426
0.424
0.424
0,422+0.009
SGD
0.491
0.463
0,450
0.441
0.434
0.428
0.423
0.419
0.415
0.412-000010
AdamW
0.485
0.453
0.435
0.421
0.410
0.399
0.389
0.381
0.374
0.368
1.00
0.93
NETA-STORRS-G
META-STOMM-3C (H)
STORM
STORM (8)
META STORM
033
9.
(4)
0.33
9770
0.43
8.50
0.43
6.4
0.35
10
Tpoch
Epoch
Figure 9: Training loss and test loss on IMDB. (H) denotes the addition of heuristics.
18

---

Under review as a conference paper at ICLR 2023
Tran
9.80
0.89
META STORM (H)
META STORAATRAAASS S6 (9)
0.22
KETASTORMA (4)
META-STORM (1]
KE PETASTORMSSG
META- METASTORRISG
ME TA-STORM
META- TORM
STORM- (4)
STORM e1)
STORBE
STORIM-
Adam
Adke
0.43
SGD
0.22
0:30
Tran
Accurnyy
8.00
META STORM- (II)
META SISSSTORMMRO SG
8.00
META
METASTOOM
METASTORMISC
NFFTA STORM
LITA STORM
0.70
STORM-
2.33
STORM4
STORdt
STORM
0.44
Adar
3.60
Adugrad
SGD
0.0
SGD
Acaele
0.50
1.0
1.6
20
2.5 Epoch
30
30
4.3
1.2
1.5
2M
2.3 Esock
3.5
4.0
Figure 10: Losses and accuracies SST2.
Table 10: IMDB test loss.
Lowest loss for each epoch is bolded below.
Algorithm
MS-SG (H)
0.446
0.433
0.427
0.420
0.416
0.411
0.406
0.403
0.400
0.397110.010
MS (H)
0.446
0.433
0.427
0.420
0.416
0.411
0.406
0.403
0.400
0.397=100010
MS-SG
0.470
0.451
0.447
0.442
0.439
0.438
0.436
0.435
0.435
0.433+400012
MS
0.469
0.462
0.461
0.458
0.457
0.456
0.454
0.454
0.454
0.453100.010
STORM+ (HI)
0.441
0.429
0.423
0.417
0,413
0.409
0.405
0.403
0.401
0.3901100010
STORM+
0.462
0.453
0.450
0.445
0.446
0.442
0.442
0.440
0.441
0.440++0.012
Adam
0.498
0.490
0.498
0.507
0.519
0.530
0.538
0.545
0.550
0.550++0.013
Adagrad
0.444
0.432
0.428
0.423
0.421
0.419
0.417
0.417
0.417
0.416+000110
SGD
0.455
0.440
0.434
0.427
0,424
0.419
0,416
0.413
0.411
0,409
AdamW
0.455
0.441
0.433
0.425
0.420
0.414
0.409
0.405
0.401
0.398+0.000
Discussion. Here, AdamW achieves the best training loss with the heuristic algorithms coming in close. For the test loss, these algorithms also have similar performances. All META-STORM algorithms (with and without heuristics) perform better than STORM+ in minimizing training loss. For test loss, META-STORM-ST Both the heuristic versions of performs better than STORM+ but META-STORM does not. and
outperform STORM+. We see that STORM+ with heurstics performs similarly to META-STORM with heuristies.
B.2.3 SST2: FULL RESULTS AND DISCUSSIONS
Figure T0 shows all 4 plots of the main experiments for SST2.
19

---

Under review as a conference paper at ICLR 2023
Tables.
Tables 11 and 12 present the training loss and accuracy for the experiments for SST2.
Tables
13 and
show the validation loss and accuracy for the experiments for SST2.
Table 11: SST2 training loss. Lowest loss for each epoch is bolded below.
Algorithm
2
3
4
META-STORM-SG (H)
0.200
0.098
0.057
0.032=00.005
METTA-STORM (H)
0.200
0.098
0.056
0.032-10.005
HETA-STORM-SS
0.258
0.188
0.165
0.154=0.008
META-STORM
0.251
0.173
0.146
0.132-+0.008
STORM+ (H)
0.532
0.112
0.073
0.057=000006
STORM+
0.357
0.255
0.218
0.195
Adam
0.216
0.111
0.071
0.048=0.006
Adagrad
0.227
0.158
0.141
0.134=0.006
SGD
0.257
0.144
0.099
0.070
Adam W
0.211
0.110
0.071
0.048
Table 12: SST2 training accuracy. Highest accuracy for each epoch is bolded below.
Algorithm
META-STORE SG (H)
0.923
0.966
0.980
0.988=0.002
METT--SORRM (H)
0.923
0.966
0.980
0.988=0.003
RETA-STORM- SG
0.893
0.927
0.937
0.941=0.003
META-STORM
0.896
0.933
0.945
0.95110.002
STORM+ (II)
0.733
0,946
0.957
0.96311.001
STORM+
0.817
0.868
0.883
0.891
Adam
0.914
0.961
0.975
0.983
Adagrad
0,910
0.940
0.947
0.951
SGD
0.893
0.947
0.965
0.976=0.002
Adam W
0.917
0.961
0.975
0.983
Table 13: SST2 validation loss.
Lowest loss for each epoch is bolded below.
Algorithm
2
3
4
META-STORM-S STORM-SG (H)
0.205
0.226
0.261
0.302=0.012
META-STORM (H)
0.199
0.218
0.260
0.297=0.010
META-STORM-SG
0.238
0.238
0.242
0.245=0.000
META-STORM
0.233
0.238
0.247
0.251
STORM+ (H)
0.216
0.224
0.255
0.203
STORM+
0.308
0,326
0.327
0.350
Adam
0.222
0.236
0.242
0.269=0.007
Adagrad
0.223
0.234
0.243
0.244=0.003
SGD
0.230
0.228
0.238
0.268
Adam
0.220
0.234
0.243
00009
20

---

Under review as a conference paper at ICLR 2023
Table 14: SST2 validation accuracy. Highest accuracy for each epoch is bolded below.
Algorithm
4
HETA-STORM-SER (H)
0.924
0.929
0.933
0.934-00.004
META-STORM (H)
0.926
0.927
0.929
0.936+0.002
META-STORM-SG
0.910
0.912
0.915
0.915
SEETA-STOMM
0.913
0.916
0.916
0.917=0.005
STORM+ (H)
0.920
0.923
0.925
0.925=0.003
STORM+
0.838
0.841
0.841
0.843
Adam
0.921
0,925
0.926
0.92611.004
Adagrad
0.912
0.915
0.915
0.916=0.002
SGD
0.915
0,924
0.925
0.925+00003
AdamW
0,921
0.925
0.926
0.926=0.0004
Discussions. Similarly to CIFARIO, we examine the generalization gap of different algorithms in Table 15] Here, we see that MS-SG attains the lowest generalization gap between training accuracy and test accuracy while Adam suffers from the largest generalization gap among the algorithms compared in our experiments.
Table 15: SST2 accuracy generalization gap (train acc - test acc) of the last epoch's 's accuracy.
Algorithm
MS-SG/HH
MS/(H)
(TORM+/(H)
Adam
Adagrad
SGD
Train acc.
94.1%/98.8%
95.1%
89.1%/96.39%
98.3%
95.1%
97.6%
Val acc.
91.5%
91.7%
84.3%
92.6%
91.6%
92.5%
Gen. gap 2.6%/5.2%
3.4%/5.2%
4.8%/3.8%
5.7%
3.5%
5.1%
C ASSUMPTIONS AND NOTATIONS
C.1 ASSUMPTIONS
We recall the assumptions in Section 1.2
we rely on:
1. Lower bounded function value: F == inf F(x) -0.
Unbiased estimator with bounded variance: We assume to have access to (f(x, satisfying
Eg [Vf {)) VF(z), Eg [l]Vf(z.) [= < o² for some 2
Averaged 3-smoothness: Eg [I]V/(x, V 0] s 3²12 ul Vx,y Rdd.
4. Bounded stochastic gradients: [>,( < G, Vu E Rd, E support(D) for some Ô 2 0.
Bounded stochastic gradient differences: (.. vs(x,()) S 26, Vo Rd,
support(D) for some ā 2 0.
We remind the reader that O and & O(θ).
C.2 NOTATIONS
In the analysis below, we employ the following notations
Buax = max {8,1};
D, =
Σ |ddl|
2 Er,- =
Σ
ains ||
im1
21

---

Under review as a conference paper at ICLR 2023
H. Σ [F(a))] H. = Σ [ H.
v ( Ei) (as,,,
We will also write E, E, algebra generated by the first t samples. Besides, define 0 = 1. In Section | we will list and prove all inequalities used in the subsequent proofs.
Ei ||:l1 -
We denote F, a (5 S < t) as the sigma
D PROOF SKETCH FOR THEOREM 2.3
In this section, to give an overview of the proof techniques, we present the proof sketch for Theorem 2.3 for the special case p 3. For simplicity, we assume > to simplify the notation. The analysis of the fully adaptive algorithms follows similar approach to the non-adaptive analysis will translate to given Section 3 As before, towards our final goal of bounding (z F Hy and upper bound it via Dr and ET.
Bounding Ey: As existing VR algorithms, we need calculate how the stochastic error G changes with each iteration. By standard calculation, we obtain
le+1ll + + Z 1|2 20 |I f( VF()))) M4+1 a a+11/ee/12 & ||
(11)
where
Ze+1 Vf(2111 Vf( VF(*++)) + VF(x;;;
M4+1 2(1 art1) (et, 2(1 4441)0441 (f( E(t1) - VF(*+11))
We note that, in META-STORM, dx+1 E Fr+ which implies B[M++1 Fi] o 0. This extra term Mi-1 makes our analysis more challenging compared with previous works. Now, we highlight some challenges and point out how to solve them:
CHALLENGE 1. How to obtain a term as close to Ey as possible with a proper upper bound? In the L.H.S. of (11), we can see extra coefficient a++1 1 appear in front of ||e: 12 straightforward option is to divide both sides by 0,41 then sum up to get Er. However, if we do so, the following problem arises. Let focus on the term [ 11 //u41 The averaged 8-smoothness assumption gives
||d.l1 b²
E Z4+1
Fi
However, we cannot apply this result to Z 12/ar+1 since a++1 E Fi+1 as noted above. If we temporarily think 4,+1 < ca, for some constant e (we can expect this because the change from as to 0++1 is not too large due to the bounded differences assumption), will get E(a, Z
Fil < E Eca, ( Z 1 || Fi] < 2 82 ||de|| then we obtain |||| 1-
If we plug in the update rule of b, (b) Dr) 1/2 1/2/a// 1/4
aed;
Fi] S 5 1/2 dd,12 D It can be shown that Σ
dd
can
be upper bounded by log Dr but now we still have the extra a, -1/2 coefficent. To remove it, bg
1/2 reasonable to divide both sides of 11 by a,+1 rather than 0:+1.
CHALLENGE 2.
How to get rid of the term involving Mc+1? As discussed in Challenge 1, 1/2 want to divide both sides by a.+1- Now focus the term a. M++1- Again, due to a++1 Fe+1. Fe+1,Eaa,117 Me41 Fi] * 0. An important observation here is that, if we replace a++1 by a, Me+1, we will have martingale difference sequence. Formally, we define
N41 = 2(1 )²)² (c,, Z+t1) + 2(1 at)a, (f( - VF(x+11)).
Then B[N+1 Fil and Ela, 1/2 No41 Fi] are both 0. This observation tells us that, in 1/2 M4+1), it suffices to bound EE a,41 1122 at 1/2 Ne+1). order to bound E D az41
Using the SchwartSchwartz. inequality, show that the term Σ a,41
1/2 -1/2 M 0;;
-1/2 No41
22

---

Under review as a conference paper at ICLR 2023
be bounded by terms related Et= (4++1 1/2 or "e 3/2 IIV ( VF(I++1)112 We then bound these latter terms in turn, and elim-
4141 11 ||? and
E di
inate the term involving M++1-
After overcoming the two challenges above, can finally show the following incquality, where K1, K2, K4 are constants that depend only on a, ã, 3, do, bo 77 and are independent of
E
1/2 a T+ ET]
[/T, I Ki K3E log (1+ Hr K2 [oo (1 + Dr/ba)] (12)
Bounding Dy: By following the standard non-adaptive analysis via smoothness, obtain
2²3 3 |deel
F(x++1) Fxx)) (VF())), de) by
(13)
26
Here we proceed similarly to the non-adaptive analysis from Section 3.1 but start to diverge
from the analysis approach used in STORM+, The STORM+ analysis proceeds by splitting
-(VF(x)) de) = -IIVF(z;)II (VF((z), < - + /||//12 multiplying both
sides of (13) with by/1, //. and summing up over all iterations. This gives the following upper bound on Hy:
T
T 2 (F - F(x++1)) b.
T
T
Idell
H Σ (F(E.) < Σ
Σ
|lee|1 + n13
Σ
by
1=1
1=1
This analysis requires F(x) to be bounded so that the sum Σ (F(x)) - F(x++)) can tele- scope. To remove this assumption, we go back to (13) split - -(VF(xx), de) = -Idd (c,, de), and upper bound the inner product via the Cauchy- Schwhr-Schwartz inequality and the inequality ab S z + 27 - which holds for any 7 > 0:
Aa bt 2r/3
n13
(ee, d+) < |eel|]|dd11 S
||e||
+
2Aa
1/2 be
where > O is a constant (setting À based on yields the best dependence on θ). We note that this choice will need bound E 1/2 (1) and 1/2 turns out be the smallest choice of which makes E
have a constant order. The intuition for setting y = >a by is that this coefficient ensures constant split if a; and b, correspond to the non-adaptive choices derived in Section 3.1 which were set so that a /2b = θ (3). We obtain
1d
2 (F(21) - F +
T
113
de
2
E
mB
bc
E
Era/2 (xx)
b
1/2
m1B
a
(14)
The term (+) can be bounded using standard techniques used in the analyses of adaptive algorithms. The term (*+) has already been bounded in the previous analysis. Now we only need to simplify the term on the L.H.S. to Dr. But due to the randomness of b, this is not achievable. However,
the same as for the first inequality in (2), we can bridge this gap by aiming for a slightly weaker
inequality that bounds D instead of Dr. More precisely, we connect the left-hand side of 14 to 1//22 as follows:
|d b
62
T
1/4 ||de
1|
2 bo
+
2
1/4 aT
D
1/2 bp-
(15)
bo
1/2
18 +
Σi=
||d:
By plugging in bound:
15 into
14p and setting À appropriately, we can finally obtain the following upper
Ks + Kg 1 H
1/3
E
D
1/2
< K3 KgTE
log (1 HT/aa)] + K,E log
by
(16)
23

---

Under review as a conference paper at ICLR 2023
where Ks, K6; K7, Kg, Ky depend only 3, 3, du, bu. 17 and are independent of T.
Combining the bounds: The final part of the analysis is to combine (22 and I6 In contrast
to the simpler non non-adaptive analysis, these inequalities bound 1/2 Er and ar+ Dr /2 instead of Dr and ET. order to obtain an upper bound on Hr via the inequality Hy S 2DT + 2ET, we need to connect d1+1 Er and 1/4 ar+1 D 1/2 and Dy and Er. The bounded variance assumption on the stochastic gradients gives us a bound on E[ = E[1 + H//aa) = O(1 + o²T) (note that this - is the smallest c to make sure we can upper bound E[a;+ 1)). Combining this result and Holder's inequality gives us the bound
1/4
E
D
3/7
TT
1/4
1/2
B1/7
#r+1
- 3/2
E
E
3/7
3/7
aT+
1/2
ET
E+/7
aT+I
3/8
S 1337
aT+1 ET
1/2
1/7
-3/2 [T+I
where 3/7 is chosen ensure that we finally can the bound BlaT+1
3/2
Thus obtain
upper bound on E F Finally, applying the concavity of x/7 to E H gives Theorem 2.3
3/7
E BASIC ANALYSIS
As discussed in Section aim to use Ey and Dr to bound Hy. Here, apply this framework to give some basic results which will be used frequently for the full analysis of every algorithm. We first state the following decomposition in analysis framework. The reason that we can not always bound Hy directly because of the randomness of a and b, in our algorithms.
ÿ S 1 here is
Lemma E.1. Given P S 1, we have
E
h
2 max
EP
E
[D+]
S max {
E
E
D
Proof. By the definition of Hr, Er and Dr. have Hr S
2E 2Dr.
Hence
(a)
H S (2ET +
2D
2
D
H
S 2
E
E
+
E
P
< 20+1 max
E
E
E
4 max
E
EP
E
D
where (a) and (b) are both by due to p S 1.
E. VARIANCE REDUCTION ANALYSIS FOR Ey
The same as in all existing momentum- bomentum-based VR methods, we need to analyze how the error term ér changes in the algorithm. Based our notations, we give the following standard lemmas. Lemma E.2. Vt > 1, we have
a111leel|2 S ||rl12 - 11 1/ 2
[ V + M
where
Z(4 = Vf( Vf(x - - V
Me+1 = 2(1 at+1) (et, Z++1) + 2(1 at (e-1)a41 (et, (1 VF((e)))
Proof. Starting from the definition of 4-11, we have
||e++]| 2 | (F(
24

---

Under review as a conference paper at ICLR 2023
( + (1 (1 ( -VF(
II(1 de+1 ee + 21+1) + (V VF
(1 a(+1) 2 "|ee|l"
+ [1(1 ac+ 2 up+ (V -FF())))) Mc-1
(0)
S (1 (1-a++1) 1|{ 1² 1
+ 2(1 att1) )² 12 112 1 - VF( M4+1
(
< (1 de+1 ||Ee|1
+ 2 Z 1|2 2a (1 VF( M
where (a) is by (x + y)² < 2x + 23/ (b) is by E a+41 S 1. Adding ac+ ac+1|leell - ||er+1 1 to both sides, get the desired result.
Lemma E.3. Vt 2 I, we have
|d.112
| Fel I n1
E
by
Proof. From the definition of Ze+1, have
E [[] 1 Fi]
E [[V [(1+1, Ett) V - -
IVE
[V ((+1)
18 |1 xel1
(c)
3
| 1|
where (a) is by E [[|X - E
[X]
S [[[]]]]] (b) is by the averaged A-smooth assumption, (c)
by the fact T141 - Ht
2 b
2d.
E.2 ON THE WAY TO BOUND Dr
We choose to bound the terms Dr instead of starting from Hy as done AdaGradNorn or STORM+. The latter also requires the bounded function value assumption in the analysis.
Lemma E.4. For any of META-STORMA META-STORM or META-STORM-NA, we have, for any X
E
D
1-p
<
bg
1-1
+ (F( - F*)
T
+ M1max
|
XE ET,1/2]
E
bt
+
1/2
b2
M7
a++1A
Proof. Using smoothness, the update rule 2++1 = by we obtain
" de and the definition of de VF(a)))
F(1441) F + (VF(It), xc+1 -x,) + 2| xell
=F(x) (VF())) de)
1128
by + Idel12
2b²
n||d, mlee, de) 112
= F((x)
||d+||
b,
26²
First we use Cauchy-Schwarz to separate the stochastic gradient and the stochastic error terms
7/|d/11
Aenlle
7/ d
172
F(x(1)) S F(xx)
2b. +
+
11
be
2A,b,
26
25

---

Under review as a conference paper at ICLR 2023
Taking
Xa 1/2
Aa b
17 mmmax
for some À > 0. We have
n||d,11
17
Amm1eaa12
I F((x)) F( +
+
1
l1del1
2b.
2b}
2x,b:
26,
2b.
17/3
11² Bmmax
Aa 1/2
||eel1
=F(x)) F(
1|dell
20g
20
1/2
26,
2.maxx
1//3
11² 3max
nb
1|del12
=((x)) F(+++)++ +
+
20++1
1/2 1
2
69
2,3maxx
1 Piax
Bumax 20,+1 x
T/
||d.]1
2olfilleal1
< F(1)) F(1++1++ +
2
by
2.mmxxx
||dell
2 (F(11) - F*) +
T
11/maxx
||de||?
AE
[Er,1/2]
S n7
1maax
+
by
+
be
a++1 A
1/2
by
m
The final step is to relate the I.H.S. to Dr. Recall for META-STORM-SG and META-STORM-NA, we have
be (b
Hence
T
|d
T
0 ||de
T
a ||de]
2
by
11/
||d 1
(b
1/P
+ >i ||d:|13)
1=1
[=1
iml
1=1
6/
at+
(b
+
||d:|13) 1111)))ppp_p1 - a+++1
(bb
1/p + Σt= 11d
(6b
a
(60
1/p
|dd112)1-p 6//0-
41 D
D
1/p-1
The same result holds for META-STORM by similar proof. By using this bound, the proof is finished.
To finish section, prove technical result, Lemma E.5 which will be very useful in the proof of every algorithm. The motivation to prove it is because we want to bound the term inside the expectation part in Lemma
E.4
Lemma E.5. Given A, B Z O. We have
for META-STORM-SC and META-STORM-N.
||
(A B)
1/2 A + ar+1
B bo
A+
bt
log
1/2
b2
1
1=1
a++1
for META-STORM
T
Idel2
(A + B)
A + aT41
1/2 B
Σ
A +
by
log
1/2
1
bo
a₁
26

---

Under review as a conference paper at ICLR 2023
Proof. In META-STORM-SG and META-STORM-NA we have
by = (80 1/ +
|dd11))P/a
1=1
where p+ 2q = 1. Define the set
B
S LE [T]
by S A
1/2
0r-1
and let max S. We know
B
| 2
B
||del?
A +
bi
A+ 1/2
bi
1/2
by
ar+1
1ES
0,41
1/
2//06//9
Σ EES
A +
bt
a;
1/2
Ui
0++1
1//1 1/11P
A + 1/2
B
b
ax+1
g/p
bi
a,+1
1/1 1/p
Σ
4+41
1/2
+ B
1/2bb)
ap+1
2 3-1 bb
-2b
63/1P
LES
where (a) is by 0z 2 a++1- Note that
(oL A B- - o.fib1)
1,41
b
2 (6)
In
(A+ B 0:41b:)
0,+1
2-
1 2 -2
16
(A+ B 1/2
1 -2 bg
a+t1
1-2
(A+ + - d1
1/2
bz
(A+
-1
1
1
4-2
-
P
p
P
(A +
B)
1
where (b) holds by a+11 I 1, (c) is due to is by applying Lemma [88]
2--P
1-2p
1 by p + 24 = 1 and (d)
2p
22
Thus we know
T
A
B
bt
del 2
<
p
(A+ B)
6
6
12
p
6. 1/P
EES
(e)
(A + B)
log
1 1-p
b-1
EES
(A + B) --11
log
1 1-P P
b
(A + B) 1-11
b2
log bo
1- p
(
(A B)
1-1
1/2 A + aT++
B
log
1 p
bo
where (e) is by taking x = (be/b, 1/2 in 1 1 < log (f) is because b, is increasing. The reason
(g) is true is that by S A A -1/2 < A + + 0T B where the first inequality is due to E S and the second one holds by that a,
1/2
112 is increasing. Now we finish the proof for HETA-STORM-SG and META-STOOM--A. The proof for META-STORM is essentially the same hence omitted here. [T
27

---

Under review as a conference paper at ICLR 2023
F ANALYSIS OF META-STORM FOR GENERAL p
In this section, we give a general analysis for our Algorithm META-STORM. We will see that p special corner case. First recall the choices of 0₂ and b;
a++1 = (1+)
Vf 5.)
Vf(a,, (ab)))221/0/02233
b. = (bg
|| 12/p/////
where p, q satisfy + 2q 1,p E
ag 0 and bo > 0 are absolute constants. Naturally,
we have 01 = 1. We will finally prove the following theorem.
Theorem F.1. Under the assumptions 1-3 and 5, by defining g 3(1-)) 4-p
E 1/ V7 -2]. 2].
we have
E
H
2K:
K4
2-
+
22 K4
+
(2Ka) 1
(1+
(1
20 a6
$
p * 1 2
<4
1
(2K] + 2 +K2 + 3)
log 1 +1+
2022
+
2kg F
log
4Kg bp
(1
2022
+ +b
%
Ky 3
20 + K log
Kg + Kg
T
20
+ 4 Ko+ + Ki +
log
1
+
a
bo
0
where K, E [9] are some constants only depending on og, bo, 7) o1 0,
p.p.q.
F(x1)
F To
simplify our final bound, we only indicate the dependency on B and F(x1) F*
E H = =
F=) (((((())-)
3 log 3 + 8 logi #
(1+ (1 (1 (1)))
Remark F.2. For all E [9), the constant K; will be defined in the proof that follows.
By using the concavity of x², we state the following convergence theorem without proof.
Theorem F.3. Under the assumptions 1-3 and by defining p = 3(1-p) 4-p
E 13 V7 2). we have
E VF (zown))
= ((((())))
Fo) 3 1 3 3 log 1 1 (1+ (
1
28/3
T
Here, we give more explicit convergence dependency for p p= used in Theorem 2.3
Theorem F.4. Under the assumptions 1-3 and 5, when P = 2' by setting X min 11 (ao/0)T/3 (which is used in Kşto Ko) we get the best dependency on ō. For simplicity, under the setting ag bo =n= = we have
E [[IFF |5/7 -o - l0g
6/7 (1+ (1+0'T))
1
T2/7 O2I7)
T3/7
where Qi 0 ((((x)) p/)0/7 + 12/7 + (6o) 6/7 + (1 30/7 1o/Tlog 8/7 (3 18+0 +5 and Q2 = 0 ((1 + 11877) g6/T).
To start with, we first state the following useful bound for az: Lemma F.5. Vo E (0, 3/2] and Vt 2 1, there is
20
aj
40
<
1
+
of
2
0++1
28

---

Under review as a conference paper at ICLR 2023
Especially, taking (1/2,1,3/2). we have
1/2
g2/3
ag
1/2.
S
01
0++1
dg
2/3
42/3
dt
1
ati
a(+1
at
3/2
40
3/2
<
1
04+1
Proof. Note that
20/3
a
1
V &t)
V Vf 1111)11
di
a141
ai
3/2
48
1
(x(e,, Ee+1)11 111
at
3/2
20/3
ag
4
2a/3
472
20/3
3/2 az
S1+
02
aj
where the last inequality is because 20/3 < 1.
Lemma F.5 allows us to obtain some other properties of dz.
Lemma F6. For t 2 1
((1 - a241)² 2²
42/3g4/3
ac+1
ag
4/3
((1 - a0+1 (1+1) - (1 a1)a2) 2
4//3/4/3
a++1
4g
Proof. Let 0c+1 I, ar = y and note that x S y S 1. For the first inequality,
((1 0t-1)² (1 - ax) ))²
(1 x²² - (1 - y)²
0+++1
(y x x2 x 8)
< 1
-1)22 - y)
42/3///3 4/3
02 x (2 a.)
(Lemma F5
2/3
00
4 42/3///3
4/3
a
For the second inequality, we have
((1 ac+1)a+41 - (1 )²)
((1 x).
(1 -)y)²
(y xx)2 2)
04+1
(y
x)
11
-1)
42/334/3
2/3
04
(Lemma F.5
0g
42/3/A/3
4/3
04.
0
29

---

Under review as a conference paper at ICLR 2023
F.1
ANALYSIS OF Ey
Following a similar approach, we first define random time r satisfying
T max ([T) Ot 2 K-13
where
K-1 min (1, (64(14))))
One thing need to emphasize here is that, in current choice, dt Fi, which implies { =1 t = =r=t- --=--l = {ar-1 2 K-1,a, az < K-1j E Ft. This means T + 1 is stopping time instead of itself. We now prove useful proposition for
Lemma F.7. We have
a++1 kn, Vt S T, 01+1 - a 2/ +
where
Ko = [=KK/// + 4 /ag) -
3/2
2/3 (max { 11, 17287722///// /ai] + 452 (ag///))2//
Proof. First, by the definition of r, we know a, 2 K- 2 Kt T. r. For time t, we have
77+1 04 3/2 /VV
-3/2
( / 4
01+11 - (a- 452 /2/) = (K_ 3/2 + 46 ///)
=Ko
which implies 0 2 Ko.
For the second proposition, let h(y) = 12/3, h' (122)(1) - 822
Due to the concavity of h, we know h(y)) 11(22) S
2(y:
-82) Now we have
301
a at (a, 3/2 [V - V ff (++1)1
(a.
2/23///3
1/2 (f( - E(+))l
8a, 1/202 2
20
3ag
3a
9
where the last step is by 0i I a,+1 < K- (1440T)
F.1.1 BOUND ON E 2, FOR l [4
Unlike STORM+ in which they bound E [Er], we choose to bound E 3///222 We first prove the following bound on E [2233/222
Lemma F88 For any E [] 2). we have
4 111
20 + 16 1
654/3
(3a + 552)
624/3
172
3/3
473
||d 1|
E 2r,3/2-21] <
E
K-26-/2 1/2
K- 11/21
by
Proof.
We start from Lemma H.2
a141/eee|2 < ||= ||+++|| 2 +
V 1
VF( Me+1
Summing up from and taking expectations on both sides, will have
E E
<
||el ||e+t]| + 22 + &( VF( M
<0² + E
Σ 2 Zz+ 2 + +07 VV
|/ - VF( M
30

---

Under review as a conference paper at ICLR 2023
T
< +
E
21 2 + (V (F( + Σ Mc+1 Σ 1=1
(17)
First we bound IE Ei=1 Met1l. From the definition of M4+1, we have
[M++1] = 2 a1+1) (ec, Z + 2(1 a(+1)a+4(ee, (f(1 (F(*++1))
Now for 2 1, we define
N1+1 = 2( (ec, Ze+1} + 2(1 - ar)a (I( VF VF(x++1) E Fit
with N1 0. key observation that
E
Σ No-1
O.
This is because N₁ Ei= N, martingale and is bounded stopping time. Then by optional sampling theorem, we have
E
N411
E
N₂
E [[ 0.
By subtracting E
DE= t= M411 by DIE==1 Net1l. we obtain
E
M+1
E
2 ((1 (1-04+1) ax+1)2 - aaa))) (ee, Ze+i)
+ 2 ((1 ax++ ) -(1 at )cx) (Ez, V[(22+1,5441) VP(x41))] (18)
Using Mtuchy-Schwarc inequality for each term, we have
2 ((1 a++1)² - (1 - -aa))) (ee, Zz+1}
<2 (1- a+11² - (1 (1) ||c /11 Zt+1||
4 ((1 - at+1) )2 (1 - 2²)
at+1 ||c|||2
|Z1+111
at+1
2 ((1 (e+1)0++1 - (1 - -a)aa) fee, V[(eet1, - V V((+++1)
<2 <1 0441) - (1 a ar)a [[
FF(
| + 4(11 - 00-1)a411 - (1 - a: ) )2
d++1
[V - VF(2++1)
4
G++1
Plugging the above bounds into 18
we obtain
E
Me+1
((1 -
0c+1) 2- 2²)
<
0++1
||ee|12 +
4|1 Zt+1 11
2
ac+1
(8)
((1 Oe+1 ae+1)a444 )a11
a,))
4
V (((4114444)))) - (
(19)
ac+1
(64)
Plugging the bounds for (i) and (ii) from Lemma F.6
into 19
the following bound on
1 M comes up
E
M
31

---

Under review as a conference paper at ICLR 2023
45/3
45/3/4/3
SR
0++1
||el|12
1 +
oj
(
V (cc+1))1
2
4/3
1/3
a0
d
12G4/3
1274/3
<B
E
12++1
2
ai -
4/3
4/3
au
dg
Then from
17
we have
1254/3
[
S
o²
+E
Dr,1
E
2
1|
2
4/3
1=1
ao
1274/3
+ E
20
02
V (1 - V (
4/3
40
which will give us
674/3
T
E E,.1l S 20
+4
1+
E
Σ
1
2
a0
(188)
6/4/3
+ E
4
0
+
ai
(e (F(441))1
(20)
4/3
d
(fv)
For term (Hi)), Lemma E.3
tells us
||d.]1
Z1+111 |F
Sn
(21)
62
For term (iv), we know
604/3
E [(vv]]
E
a1+1
+
4/3
di
|
1|2
an
664/3
Σ
4
a1+1
+
4/3
a
E - B/
ag
654/3
E
4
a1+1
+
1/3
d
| (((4111444)) - Vf
(22)
Qn
Note that
4/3
= 1+ 1-1
at
Ví(,,))) Vs (x)
then we have
T
654/3
G +
1/3 a
| [ - &42))1
Og
(114 - /
=4
4/3
1 Σ 1=1 | / {1) V (
211
2//4/3 2/3 dg
4/3
1 - V/ )1? (PP/aa)
32

---

Under review as a conference paper at ICLR 2023
8
20G2
<4ag
+
+ +243 2/3
+
a
aj
04/3
=16
(3ah
+ 20
+ 96
(3ag + 50²)
1/3
0g
6g4/3
<16
1+
(3ag + 50")
(23)
4/3
d
where, for the first inequality, we use Lemma 1.4 and Lemma we obtain
1.5 Plugging
21
and
23
into
20
E [r,1 S 20 + 16 (1
671/3
654/3
1
11
(3aî - 502) +
1
ny
B
4/3
4/3
b
Note that by Lemma F.7 we have for S T,0++1 2 Ko- By using this property and noticing 28- 1/2 2 we can obtain
Ku
28 1/2
7.3/2-22
K2t- 1/2
a 1++1
3/2-26
||e
S
Σ
alell
1=1
6G4/3
654/3
|del
220² + 16
1+
(3ag + 502) + 4
1+
11
3
4/3 ag
4/3
62
ag
which will give the desired bound immediately.
F.1.2 BOUND ON E Er FOR l E [1 21
With the previous result on E EE,,3/222 we can bound E [E7,1-20]- Lemma E9, For any
[1. 1). we have
1-1
E
Hr /a
{>
E [ET,1-2d & K2(1) + (2)
E
log (1 - HT Hr/aa8)))))
8 {=
(1 + 282)
32 |cd
+ E
(a(
f
a
where
7232 02 +8
674/3 d
(3a + 562)
24 (1 (2) 8)62 02
Ki({) =3 3 0² +
+
(2
ag K
2f 1/2
((1421 0
(+)
K2(1)= = 3(1+ 3(1+20 J00
P(4--11
{= 1
14462
4/3
3 (1 + 262)
1462
Ka( = 2f2
1
+
K0
dg
4/3
g2
Proof. We use a similar strategy as in the previous proof in which we bound E [E,,3/2-2]] 21]. Starting from Lemma E.2
2 | |k4+1ll + 2
2a (1
VF( Me+1-
33

---

Under review as a conference paper at ICLR 2023
Dividing both sides by a get
taking the expectations on both sides and summing up from to T to
Ex
|
||
E ET.1-24
2F
2f a1+1
a++1
t=1
2
M++1
+
|Z 1| + I ( VF
2t
2r
a++1
a++1
_
+ E
Σ
a++1
22
a ||
2
M
Z1+1
2a 2f
(f((et), - VF(*4)))
(24)
22
22
1+1
4++
As before, we bound
E
Mc+1 0++1
first. From the definition of M411, we have
M4+1
2((
ac+1)² a.
E
= E
(EE, Z(+1) + 2(1 a1+1)a (e,, (f(2411,441) FF
2F
similar key observation that, if we replace a++1 by ar we can find
2(1
a,)²
(Et, Zz+1) + 2(1 - at)a -2 (et, (f(e V O.
o7
By subtracting E
Mo+1 a2+1
by O, we know
M++1
(1 a(41)²
(1 (1-a)²) (et, Zet1)
E
E
2
ai
+2 ((1 az (ai1)a) ar+1
(1-aa)af 20) (ee, ([((e++, VF(+++))) (25)
Using Cauchy-Schwarz for each term
(1
01+1)2
(1-a:)
(er, Zz+1)
a-
D++1) )
(1 a2)
||ee|l|
a++1
21
at
(1-a,1)²
)
[1,11
-2
0,
26) ||ee|12
a2l
a²t
1
28
28
a1+1
2 a
1-28
(1 0:)a 20) (EL, (f(c++1 E(+1
<2 (1 a1+1 )
1-26
at)at ||ca
Vf E++1)
V (x
((1 ax+ Ja
1-28 28
at)at 2202
< (0,221 aa 21) lez 1|2 +
-( -
V
a,41 a,
Plugging these two bounds into (25 we obtain
(1-0++112
(1 (1-a,)2) 2
E
M
< IF.
(a
ar
20 ||ea|1]] +
a
a:""
|| 2
28
28
22
a1+1
a,+1
a
(i)
((1 a++1)
1-26 1-26 a(+1
(1- ar )ak
1-28
+ E
V
f( VF(x++1)11
a 0,41
21
a, 26
(65)
(26)
34

---

Under review as a conference paper at ICLR 2023
To bound (i) and (ti), let af41 I, af y and note that 0 S for (i)
1. By Lemma 1.6
have
(1-ae+1)²
(1 (1-a,)2 )2)
(1 1/e/2
1/93 2
07
x² y
at+1 at
y²
x²
1
(27)
f²1²
fatt1
For (tt), by Lemma L.7
((1 ((1 11--(+1)0 1-28 (1 oe Ja 2202
((1
x
110
1/--2
(1
y
11
12-2) x²y²
11² x2
a++1 a,
12/t-2
2-28
0g
(28)
82
(2
Plugging 27 and 28 into
26 will have
M
S
2 (a
a 20) 1|cell
a
28
a²-2 (V( VF(
1
F2
Now combining this with
24 we obtain
T
T 282
E E
20] 50²
+E
28
[|eel? +
1+1
le (
(16)
(10)
2-2F
+
2a
(V(012, - FF(
(29)
f2
For (iii), we split the sum according to then use Lemma F.7 and Lemma
F.5
T
T
Σ (a 21 a. ||e,12 Σ
3 (a - ar 202 ||eal1 2 +
Σ
3 (a a-2%) ||
1=1
1=
Note that 3/2-22 - 28 E
[ 1], we have
28 0,+1 a,
3/2
1
3/2-2 at
0,+1
3/2-28
a141
-3/2
-3/2) -/22)
a,
a,+1
3/2-28
a.+1
a
2
a
3/2-20 28
(Lemma
a
and we can use Lemma F.7 bound for 2 r +1
1
0
a,
28 1-26
a S (a,t)
1-2f
a, a
a++1
af
a141
1-28
a1+1
35

---

Under review as a conference paper at ICLR 2023
Thus
T
3 (att1
0f 20
||ee11
1
12 4441
3/2
1/ +
Σ
T
2
ar+1
40
(=++1
T
127
3/2 3/2-21
11,11111/2 +
Σ
2
1-2f
||ll
0
114
3
r+1
1=1
1=1
127²
- -
2
//,3/222 2f
%
For (tv), note that
1 26
1 + 2F
2
E
|
E
Batt1
e
1111
22
+ 26 g
47
1c++1 1 11? a?
E
1+
at
(Lemmal F.5
4
1 + 26 e
1G2
[[]
Z 112 a?
Fel
E
1+
28
dg
1 + 26 E
462
4
| 112
1
di
28
2)2
32
where the last step is by Lemma
E.3
Hence we obtain
T 1+
282
T
26
47
1f
|d 112
E
Σ
Z
1|
S
E
1+
at
n² 32
Catt1
of
a 22
1=1
For (v), by the same argument when bounding
22
we know
2-26
E [[()] < E
Σ
+
20
2-28
(I &
l2
Now we use Lemma
I.2 and Lemma
I.3
get
2-28
20
2-
[[ &
f2
a
T
Vf Sffoean
1
[(x; 1/ 4(1-0)/3
1 Σ[=1 | V 41) V
11=1
+ 20
11 (1+ VVf(,, 41) 1 4(1 41/3
24G
12
+ 2a x
2
2
111
(1 + 26 dg
3
H Hr/aa
e+ 1
+
it-1
log
1 1 H Hr/wū)
l 1= 1/
4-11
24 (1 + ++2) 02
(1 + 262) ag
3
H /a3
t+
12
log
[1 H7 ai
1 t=1
36

---

Under review as a conference paper at ICLR 2023
Plugging the bounds (dit), (iv) and (v) into (29
get
E [ S o² o² 24 (1
(?)
0²
1252
+
E
E,
3//22222 28
+
Br.
1
d
3
26
462
||de| 12
E
1+
28
2 1
g2
8
of
1=1
11
(1 + 2(
d
E
HT/
3
e e
4F-
8
I
log
+1 HT/aa)
8=
which gives us
24 (1 + () 4) 7²
3672
E Er. 28 S3
02+
+
E
[,,,3/2-21]
a
T
(1 + 20)
4
$
|1de
1
up 32
L
2
at b2
M-1
(1 + 26)) aB
E
H Hr/
e e 3
46
E
log
1 +
Hr /
8 8=
Now we plug in the bound on E, 1/2 in Lemma F.8 get the final result
E Er.1-2
720²
02 +8
1 6/4/3 ag
(3aā + 502)
24 (1 + 82)
g2
33
0²
f2
ag
Ko
28 1/2
Ki(9)
11
H /08
(+
+ K2(
E log
(1 + H+
l
14472
66
3 (1 + 28
(40² 0g
$
3 (1 + 202)
n? B2 1
+ E
1
28
+
K2d
1/2
4/3
8
a? D3
ag
Ks(()
where
9(1+2e2) jag
1+
K2(E)=
(48- 1)
3
3112202) 0a
f= 1
4
F.1.3
BOUND ON E ET11/1
The following bound on E [/2, will be useful when bound Dy- Corollary F.10. We have
1|d 112
E ET.1/2] < (((14))) log (1+ H HT +E Σ
Ka(1/4)a,"
54
12
1/2
Proof. Take é in Lemma F9
37

---

Under review as a conference paper at ICLR 2023
F.1.4 BOUND ON E
@T++1 Er
20
With the previous result on E 1ET,1-20 we can bound E
24 Er @T+1
immediately,
Lemma E11. Given p + 2q = 1.p E
3-y7 2
we have
Ki + K2B
(Hr/aš]
KKB D
9 >
20 E @T+1 ET 5
Ki + K2l
log (LaHt/a))
K2lE [og
1 +
Dz bg
g
where
K1 = (i(4)
K₂ = K2(9)
Ka(g)= + 3(1+29") 4²
14-1
q>
1
K1
Kz(g) + 3(2+20") d²
122
q= 1
4
Proof. When > i + < 21 by Lemma
R9 taking 8 = q, we know
3 3 + 2222)
122 |1de
1r S (i) + K2
Hr//ab)
+
E
Kz(g)a +
3 (1+2222) Kg(g) +
de 11
<g)(g) + K2(g)
(ar/af)
+E
Σ
17a 32
q²
200
1-11
3 3(1 + 29")
|d 11
= Kg( + K2(D)
/ar/aa)
+
Kz(g)= +
17232B
q2
2002
(4) K2(4) K2(1)B
(Hrr/ab)
19-1
+ -Kalo))
+
3 3 + 20²)
1 Σ (b)/P
||de|12
q²
2F
Σ lld:112)
(b)
3 (1+ + 20²)
D 1-p2p
< (i(1) + K2(g)E
(HT/aa)
Kg(g)
11² 3
d²
1 2p
3 3(1 + 21²)) Kg(9)
3 82
kg(g) K2(g)B
(Hr/
+
E
D 1- 2p
dp
4g
where (a) is by
2p
+ 1=
[|d])12)
2p
2.0 63 a
2q
1/2
+
Σ
|d 1
1=1
(b) is by Lemma L. (c) is by 1- - 2p 4q 1.
When q = 1. by a similar argument, we have
E ETT11-2y S (g(g) + K2(g)L log (1 + (rrrraa)))
+ Kalg) - (1 + 2q²)
Dr
)
1 log 1
q²
bg
38

---

Under review as a conference paper at ICLR 2023
Now can define
Kz(9) 3(1+20") d²
n²
q> 4
4q
K4 =
Kz(g) + 3(2420")
1223²
q=
The final step is by noticing for 2g = > 0,
T
T
E
0++1
||el| 2
ar+1
1-24
|
= aT+1
1-20
Er
F.2 ANALYSIS OF Dr
We will prove the following bound
Lemma F.12. Given p + 24
1.p
3-v7 1]
we have
:2
ag Hr aj
Ks Kg
(1+ HT/
E
S K5 K&E
log
K-E
log
b0
where
1-1
+ -- (F(1)) F*) + (K1(1/4
2
K6 = 2K2(1/4)
Ks = bg
17
mumax
m.max
K, (Kg + Kg)) -
202/3
Kg = + AK3(1/4)) ( Kg =
+
+ 54A
mmaax.
1-p
0
2/3
x
A can be any number.
Proof. We start from Lemma
E.4
2
0
D
< bg
+
(F(21) - =F"
7
T
11.maxx 1/2
||dell 62
XE ET.1/2]
+
E
mimax +
by
a
8)maxx
where À > is used reduce the order of ā in the final bound. In the proof of the general case, we don't choose À explicitly anymore. Plugging in the bound on EE' [Er,1/2] in Corollary F.10 we have
E
a7
D+"
XKG(1/4)
XK2(1/4)
E log A 2 +
H
<bi
(F(x1)-F7
3maaxx +
1Bmax
a
m7aax 1/2 a
(L(L/4)
54 B2
|| 12 1i
+
Bmaax
br
Bmaa
1/2 31.aax 0₂
a HT
<Ks + KGLE
log
2
a4
1/2
3)
|| 1|2
+ E
11 + XKa(1/K)))
Bmax +
+ 54A
bt
1/2
1/2
02
Aat+1
a
a + H
<Ks + KolE
log
2
39

---

Under review as a conference paper at ICLR 2023
252/3
7mma
||del1 ||
+ E
(1 (1+AK3 (K3(1/4)) mmax
+
541
(30)
///3
1/2
on
a
(4)
where, in the last step, we use Lemma
F.5 Next, we apply Lemma E.5
(i) to get
1 AKa(1/) + +
2/2/3 A
54A
77,3axx
(i) =
1-p
(1+ (kx(K/1))) Smaa + (
252/3
+ 542
n3max (1+ H, /a8) 1/3
x log
bu
1/3
K8 + Kg (1+ Hrr/aaa
= K log
by
By plugging the above bound into
(30
get the desired result.
F.3
COMBINE THE BOUNDS AND THE FINAL PROOF
From Lemma
F.11
we have
Hr/ag 14
Ki + K2E
+ K4B
D 1-122p
7>
E
O E
Ki + K2F
log ( H-HHr/aj
+ K2TE
log
(1 + D/ ]
9=
From Lemma 1.12
we have
1/3
0g + Hr
Ks + Ko
(1 Hr a
E
ar+1
D
K3 + KgB
log
+ KyE
log
a
by
Now let
3(1 p)
3
p 4 p
E
V7 2
7
Apply Lemma E.I
we can obtain
H
< 4 max
E
ET
E
D
(31)
Now we can give the final proof of Theorem
Proof. First, have
E
H
E
Vf(x,
2
Var [V Ei) 20²T,
where the second equation is by the independency of & and & Now we consider following two
cases:
Case 1: E
D
E
E
In this case, we will finally prove
2K R4
1-
2Kg
+ (2Ka) $
(1+
2
q
E
E
x
$ (1
(2K1
2 (K₂ + Ks) log
2021 (1+
+
2K 1
log
4Ka
20
b
2p
0g
66
a
40

---

Under review as a conference paper at ICLR 2023
Note that by Holder inequality
E
aT+1
E7
x ar-1
(112
11 2012
EP
@T+1
ET
E1-9
a++1
EP
(T
24
ET
E1-8
(1 + HT/ (g)
211-2
311- #1
(a)
BB
"T+1
1- 20
ET
E1-#
(1 + H / /
3(1 p7
2pF
EP
GT+1
2
E7
E 2up
+ Hr/ [b)
where (a) is by 1 24 = p. (b) is due to
2pp
2p(1-p) 2p+1
< 1.
First, if q # 2. we have
29-1
E
aT+1 ET
S K1 + KyE
(Hr/ab)
+ K₁E
D DI-221 2p
(c)
$ K1 + K₂B 22
H / 2
+ K4E 1-20
D
(4)
Ki + K₂ (20 (20²T/az
1-
K4E 1-22
E
where (c) is by
29-1 1-22
< 1 and p > 3 = 1 - 2p S
3(1-p) t-p
= D. (d) is by E [ s
TT and E
D
< E
E
Then we know
E
E T
S 1
ar+1 24
ET
E
1 + HT//a/
K1 + K₂ (/²))aa)
1-20
3
+ K2E 1-2p
E7
(1+ 21)2)) 2n5
If K,E 1-
D
< K1
K2 (20 (2²2T/a))
1 2g 3
we know
1-30
Ki
K₂
2T
+
K4
K4
0g
2
1 2p
K1
K2
1202T
+E
+
K4
K4
2K
T-sp
2K2
20
+
K4
K4
aj
1 32 If K
E
> K1
K₂
T2o2T/a²)
1-2p
then we know
TT
E
(2K4) 2
2p 2p
E
1
a
E
D
& < (2Kg)
(1+
2T
ab
Combining two results, we know when y +
1
E
PP
<
2K
T-
+
2K2
T-2p
220TT"
+ (2K,)
+/ (1+
20
T
K₁
K₂
aj
og
41

---

Under review as a conference paper at ICLR 2023
2K K
2-
2K2
1-
(1+
TT
(2K1)
$
K4
d
Following similar approach, we can prove for q 1 theree is
20 4
K4
E
E
20
E
E
Ki + K2 log
1+
+
log
1
1
Now we use Lemma 1.9 get
20
2K4
4K4
(
2
20
E E
2K1 2K2 log
1
+
log
1
+ 1/0
dg
2
p
dp
K1
T0
2K
4K4
20 T
2K1
K2 + +2
log
1
+
log
1+
+ 00
3
2
p
2
ag
Finally, we have
2K1 Ks
T
+ (2tee
+ (2Kg) )
(1+ 2
$
9 9#
E E
(2Kis 2 (K2 + Ke) log (
2027 og
+
2K4 8
log
1Kg b
(1
20
Case 2: E
D 2 E
E
In this case, we will finally prove
+
E D
<
K5 +
KB
K7
log
1
20
+ K7 log
Ks + Ko
1
20
3
bo
og
Note that by Holder inequality
ju
E
D
E
aT++
D
X aT+1
< E T-P
(T+1 D
E T-p
aT++
Iー
254 311-p-7
-
@T+1 D!-"
E T-P
(1 H1+Ha/
Eip
aT
D 1-p
E3
1+ Hr//a]
where the last step is by
25g
(1-p)3 3(1-p p1-p-pP) D)
1. We know
3(1-p-))
1/3
a + Hr ao
Ks + Kg
(1+Hr/ Hr
E 1 DJ. < Ks + K&l.
log
+ KyE
log
bo
(1+ (1+t//af) 1/37
(c) K5 + Kg log
ag + E
H
Ks KyTE
K7 log
bo
a +
E
H
Ks + Kg
(1 ++ E. H /aß)
1/3
Kg + Kg log
+ K₂ log
ag
bp
42

---

Under review as a conference paper at ICLR 2023
og + 2022
Ks + Kg (1 + 20 //)) 1/3
Ks + K9 log
+ K3 log
ai
bu
where (e) is by the concavity of log function, (f) holds due to [X1/3] S B1/3 [X] for X 2 0, (g)
is by
HT
s Tr
Then we have
E
D 0
< IE
a7+1 D. n
E 1 1+ Hr/
a + TT
Ks + Kg (1 + 20²T)/B)
1/3
--p
20 T
K5 - Kglog
+ Kr log
1
+
aj
bo
ao
2
K7 3
20²T
Kg + Kg
1-p
(
T
$ K3 +
K6 +
log
1+
+ K7 log
11
aj
bo
a
Finally, combining Case 1 and Case 2 and using
(31
we get the desired result and finish the proof
E
H
4 max
{
EE
E
E
D
2K1 K₁
+
+ (2Kz) 1 (1
20 g
1
<4
2K1 + (K2 +
K1)
log ( +
20
+
2kg D
log
1Kg by
$
1
+1 20"T
+ 6,9
q
Kr
20
Kg + Kg
1-
20
+ 4 K3 + Ko +
log
1+
+ K log
1
3
dg
2
b0
a
G ANALYSIS OF META-STORM-SG FOR GENERAL p
In this section, we give a general analysis for our Algorithm
Readers will see
p = 2 is a very special corner case. First we recall the choices of o and by:
a++1 (1
V (1)l 2/3
b. /b//
d ///
where p,4 q satisfy + 2q = 1, E 1 > 0 and by > 0 are absolute constants. Naturally, we have a1 1. We will finally prove the following theorem.
Theorem G.1. Under the assumptions 1-4, by defining p 2(1-)) E [3 2), we have
E
H
<4Ca1
(2o2T)²
8 S
+ 4C1ol 4Coo
(20 s 4C10]
- 2
T
(2Cz) op (1 2(2
2C
C/5
+
2C Cs
+
P p 114
+4
(202T)
))²
1 + ()
Ci +
Co
+
C
p
log
1 +
miu /0t /2,
ag
p
2/3
2T) 1/3
"p
+
207 + 20
+4
C4 + (3Cg + Cb) log
+ Co log
2/3
bp
43

---

Under review as a conference paper at ICLR 2023
2 (2) P. x +
1/3
where Ci E [10] are some constants only depending do, bo, ao G. p. F(11) Fr, To simplify our final bound, we only indicate the dependency on B and F(x1) F* when a + 0 and T is big enough to eliminate Cg and C10
H2 =0 (((F(z))- + P log T-p 3 B log T- (1 (1+ +1+)))) (1+
F=
Remark G.2. For i [10), the constant C₁ will be defined in the proof that follows.
Again, by the concavity of xP, we have the following convergence theorem, of which the proof is omitted.
Theorem G.3. Under the assumptions 1-4 by defining ş = 20-p) E [3 $ when # 0 and T is big enough, we have
22/3
logi E [VF( =0 (((()))))F))) F*) B log v B + B log f (1 +++2T))
log
TB
T25/3
Here, we give more explicit convergence dependency for used in Theorem 2.1
Theorem G.4. Under the assumptions 1-4, when p 1. by setting À min {1, /)/ (which is used in C2 to Os and C10) we get the best dependency on G. For simplicity, under the setting ag bo n L, we have
W
(o2T) 1/3 < W1]
(
22/9 T1/3
E VF (Foo)))) 11203] =0
(W2 + W3 Wogg (1+ ((T))
T1/3
T2/9
0 (F(m)) - F + ② 8 (1 62 log (8+
where
W1
W2
0 (F(x1) - F+/2/3 + 0413 G (1 /2 log 2/3 (++088) and W3
0 (1 011 32/3)33133
To start with, we first state the following useful bound for dz:
Lemma G.5. Vt 2 there is
3/2 a,
3/2 < (G/ao)2
a++1
Proof.
33/2 0,+1
3/2
(,,, (²/a0)²
G.1 ANALYSIS OF Ey
Following a similar approach, define random time satisfying
max ([7) 2 Co)
where
Co = min (an
Note that {T 1-=10 1) = {a+ 2 Co, a+1 < Co} E Fr, this means 7 is stopping time. We now prove
useful proposition of
Lemma G.6. Vt 2 + 1, we have
0.41 a, <2/3.
-1
44

---

Under review as a conference paper at ICLR 2023
Proof. Let h(y) y²/3. 2(mn v2) Now we have
Due to the concavity, we know h(11) h(y2) - (1(22((11 322
392
dx41
(a:
3/2
+
(x.,
(ai 3/2/2/33
20,
1/2 V f E.]1
2a,
2
S
30 2
3a
2
3
where the last step is by a S a,+1 < Co < (ap/ (
G.1.1 BOUND ON E 2 FOR E [:: 2
Similar to the analysis of META-STORM, we choose to bound [Er,3/2-2 20]. following bound on [/r3/2-2x]:
We first prove the
Lemma G.7. For any l [ 2). have
0² - 24a +
+G
| 1|
E 2,,3/22-2
<
E
2/2-1/2
222-1/2 0
Di
Proof. We start from Lemma E.2
0411/e//' 2| s |leell 2 ||++1|| 2 2| Z 1|
+ 20 |/ (1(++ E(+1) VF(x++)) M
Summing up from T 1 and taking the expectations on both sides, we obtain
E E 1.1
E
| |6++|| 221
+ 2a
Vf(42 ((1)4)),6)))VV((((4))))))))) Met1
r-1
= E
|le - |||,|| 11 Σ 2/ 11+
+ + V (11411 VF Me11
T
2/ 12+1 < E |1 1 - ||,, + Σ
1=1
+ 20
E4+)
F 12(+1111
Σ
Me+1
1=1
T
+ E [E,-1.1 + ||= 0²² + E
2| 21+11111 Σ t=1
+ 20 [5(2 - (F(++1)) +
Σ
Met1
1
Because Co 5 1, ar41 5 28 1122211222221 0 and 3/2 - 26 2 0. so we have
2/2 222-1/2,32222 3/2-2t < 1. a,+1
Besides, for ST 1, by the definition of T, we have Co S 0141; then we know
C22 01+1
3/2-2t
2/-1/2 3/2-2 2f
<
a,41
01+1-
45

---

Under review as a conference paper at ICLR 2023
These two results give
c 22
22,3/222
CØ 222
Σ
a++1
3/2-2F
||ea|1"
Σ
ae+ ||x.1l2 + ||,,|1²
t=1
-,1 1|c/11
which implies
T
E
Co
1/2
3/,3/2-08 22
S 0²²² + E
Σ 2 1
+ 2/ (( - ( Σ M++1
LetM; Ei= M2 F, with M1 For S t, we know E [M,[F,]] 0, hence M₁ is
martingale. Note that is a bounded stopping time, hence by optional sampling theorem
M++1 = E [M,]] =0 O.
Now we have
Co
E,,32222 28
S 0² + E
2 2 20 (V - VF( Σ
1=1
By Lemma E.3
E [1 |1 S 172 32 |d
by
Besides, under our current choice, a++1 E Ft.
E
Vf
E+11)
E
Using these two bounds, we have
T
|del
Co 2f 1/-1/22, E, 1/3/2-20 28
S 5 +
2n
32
20
bi
T
|del
(Ie+1, 1)1=
0² + E
2n²² 32
+
+2a0a
x
b2
(1+ Σ ||V (2)2/aa))))))
1=1
||
40" + 2n 3 < 0² 24a
by
where the last inequality holds by Lemma 1.4 bound immediately
Dividing both sides by O2 28-11/2 we get the desired
24a
-
2n 82
||
E E/3/2-22
<
+
E
2
1/2
28
1/2
b2
46

---

Under review as a conference paper at ICLR 2023
G.1.2 BOUND ON E Er,1-2 FOR & E [á1
With the previous result on E [Br.3/2-2o] we can bound E [T,1
Lemma G.8. For any 8 [ 2) have
16-1
E
Ar/ab
3
{> 3
E 1 S Ci(e) + C2(1)
E
log
HT HT/
f= 1
G
||del1
+ E
00
2t-1/2 1/2
4t41
28
+1
61/2
att b
where
G
0² + 24m + 162
Ci(e) 3 0² 6 +
21 1/2
18a4
8>
C2(() =
1-1
6ag
Proof. Starting from Lemma E.2 as well
0e41//ee|12 < || | 112 + 2||
V (F(++1)) + M
Dividing both sides by aff. and taking expectations, we have
||e]|
||e.-1|12
2 a1t1
1-22 TE
|
+
12+11
att1
ait1
M+11
2a
2a2-2f
V (1441,
V
(
F
(32)
2t
Note that under current choice, ac+1 Fr, hence we have
M441
[M
[F]
E
= 0;
a++
|| 1241
1
EE
|1|Ze+11 ||5
||
E
E
< E
1/ 32
2f
2f
a by
[11 (
2-26
V F ))
E
[22-2<1
V
1
F (x (1 [[]]]]
[
((+)))+++++1))))
(++1)
where the second bound holds by Lemma
E.3
Plugging these three bounds into
32 we know
||
|| 2
a++1 l ||
-2n2
+ +a
a?
4+
28
1
24 6
Now sum up from to get
|
|[441112
||bp12
<B
+ 2n
+
2a
27
a++
2f
a++1
a b
T
r
|2
T
<0² + E
Σ
0,41
0,
20 ||ee|12
+2
2t a++1
bi
20
2-21
(18)
(33)
47

---

Under review as a conference paper at ICLR 2023
For (i), we split the time by
(utt ai 2 |leal1
Σ
26
20)
||x.11 + Σ
(a al 2)20) ||er|1
01+1 - a1
t=T+1
T
(+1
3/2
a1
3/2
att1
3/2-24 2f
||r||
+ Σ
(aitz a) 1|
1=++
3/2-2
||:112
Σ
2
1-26
Ee
a++1
3
(=T+1
T
1+1
3/2-2f
+
Σ
3
2
1+1
1-28
t=1
1//3/222
1T.1-20
where the second inequality is by Lemma G.5 and Lemma G.6 Next, for (ii), we use Lemma 1.2 to get
20
2F
&+1))
1=1
T
-20
2
4(1 4(1-1)/3
t=1
V (2,, 6/133/a3)
3G2
Σim (V
1-4(1-9/3
1)13 <1
520 x
+
|-11-1773
dg
log 1 +
E
|V [()
4(1 4/1-0/3-1
ab
16-1
Ga
Hr/ag)
{> 1
=66² +
3
2a log
1 + HT/aj)
l {=
Plugging these two bounds into
(33 we have
T
||de|] ||
E EEr;1-2d S 02 6G
E
E
3/2
21 + -
Er.1-2
2n2 32
a
3
a++1 bi?
46-1
6a
Hr/
e> 1
48
2a log
1 + Hr/aa)
{= 1
Thus
1-1
36
18a4 E at-1
(Hr/ [g
l>
E [[T,1-22] <3 (0² +60²)
+
+
bags Tog
1 + Hy /03 ]
l {=
de 2
+ Gn B
Plugging the bound on E
E 5/2322 - 22 in Lemma G.7
we finally get
111
2 [02 + 24 4
E Hr /bb
8>1 1
ET,1- 1-2 3
o² + 6 +
+Cz(e)
cf 1/2
11/2
E log (1 + H /
t=
(1)
48

---

Under review as a conference paper at ICLR 2023
T
G
|d,
+
E
00
2121
1+1
28
+
6of² B2
a++1 by
22
where
180g
>>> 1
C2(1) =
It-
6ag
l
G.1.3
BOUND ON E 1T/1/2]
The following bound on [Er112] will be useful when we bound Dr-
Corollary G.9. We have
E E
S (1/44)
log
( Hr
T
6172 1| 112
1/2
E
+1
1/2 az+1 03
tm/
Proof. Take i in Lemma G.8
G.1.4 BOUND ON E
aT+1 ET
1- 24
ET
Lemma G.10. Given p + 2q
1,p
[] 1] we have
(ir/aā) "
Ci + C2lE
+ CalE D2-22
<> 1
24 E T+
ET x
C1 + C2lE
log (1+ (I+HT/ajs HT
]
+ CzE log
[ 1
Dr
q q= 7
where
G = Ci(q)
C2 C2(9)
G2
6n
2 1/2
+
4--T
9
C3
G2
1) 2g
ag
Proof. When p # + q > 1. by Lemma G.8
taking
q. we know
G
|| 12
[TT,I-22 ((((g)) (Arr/at)
+
24
1/2
a
2g
+1
6rj² 32
24 ax
dd
< +C(O)))
(Arr/ab)
+
+
6n
03
1/2
a by
24
19-1
C1(2) + C2(2)
(ar/aa)
G2
T
|d 1|
+1
6n x E
Σ
di CP 1/2
2/p +
E ||d.112)
(
4111
G2
D 1-22p"
+ (
(Ar/ab]
+
+
63
T
02
2
1/2
1 2p
49

---

Under review as a conference paper at ICLR 2023
G
2 3²
Ci(1) C2(1)
(Hr (Hr/ab)
+
+ 1
D
2p
af
a 1/2
4q
where (a) is by
0g
1/p
Σ [[d;|(2)
2p
2
28
a++1 by = 1
2q
/p
+
Σ
I|de 11?
)
24 a++1
(b) is by Lemma L1 (c) is by
2p 4q
1.
When
1 +
1 4. by a similar argument, we have
Dr
)
E 21 s (1) C2(4) log (1+ Hr H+-Hr/aB))
+1
61723²R
log
1+
aj
bg
Now we can define
6n
00 2n 1/2
172
+1 1
2q-1
>
= C3
1)
2z
9 ==
The final step is by noticing for - 29
T
27,1-21 =
Σ
1-20
||ee||
2
#T+1
2-
||ee|| = 4771 ET.
1=1
1=1
G.2 ANALYSIS OF Dr
We will prove the following bound Lemma G.11. Given p + 2q L.p
1,2 })
we have
(1+ Hy (1+ Ho 1/37
a + aj
C + Cs
E
a D 1-
< C4 + C3E
log
+ C&B
log
bn
where
1
2
(F(x1) F*) + XC1 (1/4)
XC2 (1/4)
C4 = bg
+
C.
7
11.maxx
C. (C, + Ca) +1
mmaa: Cs = (1) + 62
1
m)max
1-p
A > 0 can be any number.
Proof. The same as before, we start from Lemma E.4
1-1 2 (F(x))-F"))r 2 at D D < by
3maax a
||d 1
AE Er.1/2]
mmmax
be
02
mmmax
where X 0 is used to reduce the order of G in the final bound. In the proof of the general case. don't choose À explicitly anymore. Plugging in the bound EE [E2,1/2] in Corollary G.9 know
+ (F(x1)- - FF) + AC1(1/4
+ (124)
ag
+ H
E
a
D
log of
Bmnax
Bmmax
+
(1+
6202 ag
mumax + (1 61
17aax axt1
be
||d, 1|2
b2
50

---

Under review as a conference paper at ICLR 2023
d
Hr
C4 + C3E
log
6AG ag
(1 + 61
1
||cel 1
mmax
be
(34)
1/2
by
a1+1
Applying Lemma E.5 (i), we get
((1
6AG² 4B
+ 2 + 62
m/maax -1
(1) <
1 1-P -
1 + 6A 2g
m/max + ( + 62) 3/3axx 11+Ar/o8 1/3
x log
bo
C7 Os (1+ Hr/aa]
1/3
Co log
bo
By using this bound to
34 the proof is completed.
G.3
COMBINE THE BOUNDS AND THE FINAL PROOF.
From Lemma G.10
we have
C C2E (Ar/a8))
Czll D DI-22 2p
<> !
E
@T ET
1- 2g
4
Ci C2R
log (1 (T/H//a))
C3E log
1 Dr }
q 1
From Lemma G.11
we have
(1+ Hr 1/3
ag HH
+ Cs
Hy
E
D 1-p
$ C
log
+ C&E
log
T
aj
bn
Now let
2(1 p)
1 1
1
3
3
Apply Lemma 1
we have
+
max
E
D
max
E
E D
(35)
Now we can give the final proof of Theorem G.I Proof. First, we have
T
E
E
VV
[V
T
2/ 21 VF(a)) 9
<
E
1=1
T
E
2Hr +2 _
V f (,) -V(()))))VV((()
1=1
51

---

Under review as a conference paper at ICLR 2023
T
2 H +
2
(2 &1)
VF(ED)1 -VF(E)))
i=1
T
E H.
+ E
2
[V - VF(a))1?
T
S E HH
+ E$
2 Σ
V (i(;,, (
1=1
S E
H
+ (20 2))
S 2 max
E [D9]]
_I' [ + (20
E E E D 0 } + (20²T)²
8
< 4
(36)
Now we consider following two cases:
Case 1: E
E
> E
[ In this case, we will finally prove
(
(()))
2C1
20
1-20
+ (2
(1+ 2(20e7)))
C5
+Coll (202T)) 8 S $AC0
9#1
E
(20RT)²
1 2(202T)
C1 +
C2 +
C3 p
log
1 min (000 /2,10
o
+C,1 (202T)²
S 4Cg)
9 9=
where Cg is constant. Note that by Holder inequality
E
E
GT+1
2
E
ar-1
(1-2))7
-ft -11-2018
S
RR
4T+1
1-20
ET
E1-P
(r++1 7
EP
@T+1
ET
E1-8
(1 + Hr/aa)
201-2910
3(1-P)
B
@T+1
1-
ET
B1-P
(1 + Hy / /
3(1-1)
2pp
(6)
10a
aT+1 24
ET
(1 + H7 / [
<
@T+1
ET
E
1+
Hr a 1
where (a) is by 1 2q = p. (b) is due to
2p
2p 1+2p
< 1.
3(1-p)
First, if q f 1. we have
10-11
E
24 ET
$ c + C9E
(Ar/ab)
+ +CGE [ 1-ppp 2p
(0)
C1 + C2E 1-20
30
(Hrr/aa)
+ +CBE
D
1-30
(
2 G + C2
4E
E
+ (202T) 8
1-22 + CC F
B
2p
ao
where (c) is by
1q 1q
2p
<
2-2p 3
= p and p 2 + 1
2p <
2-2p = p.. (d) is by 3
36 and
3
E
<
IE
Then we know
E
S
E
@T+1
24
E
E 2p
1 + (a) 07
52

---

Under review as a conference paper at ICLR 2023
1
4E
EP
+ (202))²
s
C
+ C2
+
C3
E
2
00
4E
E
+ (T)
X
1+
d
4E
E
$ 22
we will get
F
2 T2
(1
(20
E E
C1 C2
C3
1-3e
Biy.
1
2
40
4g
1-2e
2(220T))
If Cg
E
S Ci + C2
we have
C1
C2
2 (2021)
E
+
C3
C
28
1-2p
E
E
Ci
C2
( (200T $
35
+
C3
C3
0g
20
1-22
200
I-20
2
(2022T)
<
+
C3
C3
28
1-2p
(2(272T)
If CgE 32
Ci + C2
we have
1
(1
2 (202T)
$
38
E
(2C
ES
1
28
40
E, 211-12
2 (2021T)
(2Cg)² B1-2p
1+
20
do
2 (202T)) 0
E
S (2C²)
1 1+
28
Combining two cases, we know under 4E
D
< 22
20
1-28
$
202
1-2p
2 2202TT)
1
(1+
2 (7)
E
+ (2Ca) oF
[+
C
C3
0g
28
a
25
<
2C
22C
+ (2CC)) $
(
|+
2 (2021)) 1
C3
C3
a0
29
Now 4
E
> (20
then we have
1-2p
8E
E T
SE
E
E
E <
C1 + C2
+
1-2p CGE
1
+
28
0g
a
53

---

Under review as a conference paper at ICLR 2023
1-2p
3
SE
E/T]
( 1
8E
E
cP + Cτ
C3E 2p
B
(37)
20
du
We claim there a constant Cy such that E
I
Cg because the highest order of E
E
is only
1 - 2p
+
2p
3
=
11
4p 3
< 1. Here we give the order of Cg directly without proof
C = o 00 +
Ci
I
32
C3
+
2
2
C
+
TF
5
0g
Hence, when q # 1. we finally have
1
2C C3
((22)
2C2
- +
(2Ca) $
(1+
2 (2027)
P
+Co1 (2027) s 4Cb)
+
C33
Following a similar approach, we can prove for q 4 ththeee is
C2
C3
(202T)² 9
2 (2)2T)
$1
E
E
S
C1
+
log
1+ min a /2, 40
1+
Cg.
p
p
28
where
Cg
0
0
(C/22
(ch²² + +2//2)
log 1/2
log
C2 + Cs
+ ap
26
+ dg
36
28
ag b
Finally, we have
(20)
+ + (2Cz) #
2(202r)))
20, C
1
+Ca1
S 4Cg (202T))
E E
C +
(
C2 + -
log
1+
(202T)
1 2(2027))3
min
00 /2,46
+C+1
(202T)
S 40g
9 g=
Case 2:
E
< E
[ In this case, we will finally prove
2/3
+ (202T) 1/3
1=p
E D <
C4 + (3Cs + Cc) log
+ Co log
2C, + 2Cs
2/3
b0
1/3
2 T)
x 1
+ Cio.
28
where C1o is constant. Note that by Holder inequality
E
D
p T
= E
CT
1-p
X
aT+1
I-P
E 1 1-p
<
E
p-p
a7++1 T
ar+1
D シー r
E 1
(1+ Ar/aa]
का 311-p-p5
77+1
54

---

Under review as a conference paper at ICLR 2023
(e)
E (1+ Hr ag) 19
D 1-p
aT+1
< E 1-p
77+1 D -
E$
1+ (
T
where (c) is by
2q
1-p
1. We know
3(1-P-8)
31-P-1)
E 47 D 1-p
C (08(11111//10 HT/ab) 1/3
00 + H
<C + C&E
log
C
log
d
bn
1/3 30
C7 C Cs (1 (1+ 11+Ar/on Ar/aa)
Cs E
40 +
2
Hr
Co E
C +
log
log
p
dj
3p
b0
(2C7) 38 (20%) 30
1+ (ir//at) 8
S
Cs
28 0
H
Co
S C4 +
log
E
log
dg
28
3p
(
C3
0
28
E
H
Co
(2C+) + (2C%) 38 1 +
E
H
28
S 4 +
log
log
p
00
37
690
(6)
Cs
0
28
4E
D
(202T)
S 44 +
log
p
40
28
(2C7) 3D + (2C%)
35
1+
4F
D (202m))
C.
+
log
37
where (f) is by (x + y)"h S x" + yd (x + y) < (2x)
(2 for 0 S x, y.
0 S
p S 1,9 2 0, (g)
holds by the concavity of log function, (h) is due to (6 and E
E
< E
D Then we know
E
D 5
<
D
E
1
H
27
+ 4E
D
+ (202T)²
Cs
Ci+ +
log
p
dg
(2C7) + (2Cs)*
38
1
4tH
DD (2027))))
T-p
C6 log
+
3p
33
1/3
4E
D
+ (2021)
x 1+
26
4E
D
< (2 &
we will get
1
Cs log
4g
25
+ 2T)
Co
(207) + (20
36
1
a
E
<
C1 +
log
p
0
28
35
3
55

---

Under review as a conference paper at ICLR 2023
(2 $
1/3
x
+
d0
-
C5
C6
28
+ 2 (2
Co
(2C7) (2Cx)
Ca
log
log
p
3p
0
28
3p
by
(
2 (20
(T)
1/3
1 +
90
2/3
+ (202
1/3
207 + 2C's
1-
C4 (30s + C6) log
+ Co log
2/3
bp
0
(
2 (2 $
1/3
If 4E
D
2 (2 p,
we have
8E[D
C3
00
28
8E
D
Cs
(2C7)
(2Cg) 355
1
28
D
S
C +
log
log
p
40
2p
3p
bg
33
1/3
SE
D
x
1 1
(38)
25
dg
which implies there constant Cio such that E directly without proof
[ Cio. Here we give the order of Cío
Cio
0
25 n dg + C4 Co log
C7 C (Cs Co) log
Cs + Co
3p
do
Combining these two results, we know
2/3 + 2 (202T) 1/3
E D s
C4 + (3Cs + G6) log
d
+ Co log
207 20s
2/3
bo
d0
1/3
2 (2
+ Ciol (202T)² s $4C10]
x 1+
a
Finally, combining Case and Case 2 and using 35 proof
we get the desired result and the finish the
E
H
E [
<4 max
<4C,1
T2
< 4Co
+ 4010 (200T)* s 4C10]
2C
+
+
( (2g)
-
(2C3) #
(1+ 2(20*T)s
Cs
+4
$ min " /2,4//22 ))
22
2(202T)
C +
log
1+
56

---

Under review as a conference paper at ICLR 2023
-2
C4 + (30g Co) log % + (22(20²T) 1/3
207 + 2Cs
+4
log
b0
1+ 2 (2
p)
1/3
x
2t
d
H ALGORITHM META-STORM-VA AND ITS ANALYSIS FOR GENERAL p
To highlight the differences with META-STORM-SG and META-STORM, we set only based on the time round t, not using the stochastic gradients. This is the reason that the convergence of this algorithm does not depend on bounded stochastic gradients or bounded stochastic gradients differences assumptions. Moreover, the requirement of p (0, is also more relaxed compared with our previous algorithms.
Algorithm META-STORM-NA is shown in Algorithm
Algorithm 5 META-STORM.NT
Input: Initial point E Rd
Parameters: (g V 3 do. (0, 10.2.Pt. .p 2q
2
Sample & ~ D, d1 = (((11()))
for f 1, do:
a++1 = (1 + t/ag)) -
h. = //2// + -/= 13)0/01+1
It+1 = It b, de
Sample {,-
d++1 = (1(41) + 1441 -ale))ddV((eeeeee ((11s(141))
end for
Output Tout xt where t ~ Uniform ([71).
Now we give the main convergence result, Theorem H.T of META-STORM-NA. As we discussed
before, can achieve the rate ((1/T9) under the weakest assumptions 1-3, however, with losing the adaptivity to the variance parameter tradeoff.
Theorem H.1. Under the assumptions 1-3, by defining p = 1 - 1-pe [ 1), we have (omitting the dependency on v); ag and bo)
H
((F(z)) F 3 log (5T) 0² log T 2 T3)
By combining the above theorem with the concavity of r², we give the following convergence guarantee omitting the proof:
Theorem H.2. There is
+B3 F((x)) [((x)) -F F + 3 log (ST) + log T + o2
E VV |1 =0
T
Note that 25 2 1, hence the criterion, E [[//F(r)))] used Theorem H.2 is strictly stronger than E [| F [I) In the following sections, will give proof of Theorem H.l
H.1 BOUND ON E Er1/2
Lemma H.3. Given + 2q 1, I.p. (0, }],, we have
0² (1+ 20 log (1 + T/al)) + 32E
ΣT
ll? 4
E ET.1/2] s
1 2/(3a
57

---

Under review as a conference paper at ICLR 2023
Proof. We start from Lemma E.2
Gr+1 deel||e/|| < ||e.|12 ||c+ 2|| Ze+1 +
2 VF( + Mc+1-
Dividing both sides by a141 summing up from to T and taking the expectations on both sides, obtain
1/2
ET,1/2]
T
||e/|1
|14t1 12 +P 2/1 1// 1
20
(I( S(+1) (F(+++1) M411
<I
1/2
t=1
at+1
2
<
(0 - a, a.4
|24+1] 1|
1/2
at-1
M
+ 20 (f( V (((++1))1
1/2
at+1
Because 4441is not random, we know
2
2n/ S2 ||de11
E
12-3
< E
a++1% by
a++1
E 20141 &e+1) - VF((++1)] 1
< 20 20
3/2
Mr+1 E
O,
01+1
where the first inequality is by Lemma know
E.3 Besides, by the concavity of 2/3 and au >
V
3 we
a,+1 a. -1 (1 +1/g)) 2/3 - (1 (1- /aa)
2
2
S
<1
3a (1 + (t 1) / 1/3
3a
Then we have
2
T
2 1|del2
E Er1 S 00² +E
E
ET.1/2
+
+ 20 0²
300
01-1
1=1
0²
(1++2
3/2
+ 2r2 32E
Σn=
1
>1=1
1=1
at+1
1==1
= E ET.1/2 s
1- 2-2/(3ag)
Note that
T
Σ
3/2
Σ
1
S a log (1 + TTao))
0
1 + 1/0
So we know
2² (1+ + 2 log (1 + T/a + 3 B
lide 1|? Et
1/2,7
E [T.1/2] <
1 1 2/(3aH)
H.2 BOUND ON E Er]
Lemma H.4. Given p + 2q L, p (0, f], we have
6af0² 2 (1+ T/q 1/3 (
32
2 ( 2n
p*1
E E < 1- 2/(3g))
2p
1 --2/(3a))
E log
1 +
Dr
)
p p=
58

---

Under review as a conference paper at ICLR 2023
Proof. We start from Lemma E.2
a+42lleell & ||,.ll2 |<++l + 2 + ( (F + Mc+1-
Dividing both sides by a++1, summing up from to T and taking the expectations on both sides, obtain
E
E
|ee|1
|1211
1 2|| Z2+
112
20 (( VF(x++1) M
<E
ar+1
1=1
T
(ait) - -a |leel? + 2
<o² 2 + E
Ze+1ll 1|
ax+1
22/(3gg)
M++1
+ 2a 1 (f(Ic+1, VF(#++1)1
d++1
2
2
_0²² 2 + +E
ET +
11+111
300
2
ax+1
M
+ 2a (f(14)1,6++1 - V V
F(+++1)11 +
ax+1
Because 4141i8 not random, we know
2
2nn 3 | 11
E
/ze+1 1|
E
ac+ 1b
a+++
E (2oeeill
V
(x(+++1) ) []
20
M
E
0,
a++1
where the first inequality is by Lemma
E.3
Then we know
T
2n
( 12
E ET < <
+
ET
+
+ 201+102
300
act1b?
t=1
0² [1+ 21+2 1=1 ac+1
+ 277² 32
Σ7 t=1
11
E ET]
2/ (3ag)
Note that there is
T
|
||d/|
(a)
||del1
1
07
0,+1
1-2q
(00
1/p
+ Dr)
2p
1=1
ax+1
(b// + Di)
2p
11d,12
< (1+T//)))
60
1/p
+ +D,)
2p
D--22
(6)
p 2
2n S (1 T/33)
1 1-2p
log 1
D bg
p=
where (a) is by 1 - 2q p. (b) is by Lemma
I.1
Besides
Σ a++1
1
S 33 (1 (1+ 1/3
3a 33, (1+ (1+TT/all T/
1/3
2.
1=1 (1 + 2/2 2/3
So we know
62 2 (1 11+17 T T/a3) 1/3
(1/3(11
3r
2 D 1 2p
p
E Er]
<
2p
1 - 2/(30g)
1 2/(3ng)
E log 1
Dr bg
p=
59

---

Under review as a conference paper at ICLR 2023
H.3 BOUND ON E D "
Lemma H.5. Given + 2q
1. (0, ž},, we have
p E D T
$ (1 + T/ag) 1
hg
1-
+ (F(21) -P*) o2 2a log (1+T//) T/a3))
2
373axxx (1 122((33g)
"
(1 + T/ab)
--
1
9ag 2 3ng
(1 + T T/ag) 1/3
m/max
4 41/
log
1-
300
bu
Proof. The same before, start from Lemma E.4
E D 1-
TT
+
(F(x))
PT)
11.max Bmmax +
||del
AE
E
ac+1 A
1/2
li2
Now simply take A and use Lemma H.3 get
σ² (1 2a log (1 T/ab))
E
a
1-p p
$ bb
+ (F(x1) - F²) +
mmaax (1 - 2/ (3a5))
9a
||de12
m.max be
(39)
1/2 (3a 2) a
(4)
Applying Lemma E.5 to (i), we get
3a 3a5
2 41)xmaxx
1
9a
3a 2 (1 + T/a3) 1/3
1)3ax
(1)
log
1 1-p
Note that af41
a ar
(1+77 T/aa)
is deterministic, by multiplying both sides of (39) by
(1 + T/a3)
get the desired result.
H.4 COMBINE THE BOUNDS AND THE FINAL PROOF.
From Lemma we have
oajo² 2 (1+T/ag)
1/3
(1+T/)))
E(D
P# 7
E Er]]
1-2p
1 2/(3gg)
1- --2/(3gg)
E log
1
Dy b6
}
p
From Lemma H.5 we have
E
D (1+T/ag)
2
69
+
2 (F(x1) F*) +
0² (1 2ag log (1 + T/a3))
m)max (1 2/(2))an))
+ T/aØ)
330
$ 1
1
9ag -2 1+
3a - (1 T/ 1/3
B)
4n7 A
log
1-
30
bu
Now let
[1
1
p= p
E
Apply Lemma E.I
we know
H
< 4 max
E
E
E
D
(40)
Now can give the final proof of Theorem
H.1
60

---

Under review as a conference paper at ICLR 2023
Proof. Now we consider following two cases:
Case 1: p # 1.2 Note that by Holder inequality
E
= E.0 [Er]
E
D 2p
< E 22
D
So we know
Gaßo² 2 (1+ a//3)/
1/3
(1+ _
E E
+
(1 (132)(3 - -2p) E [D. -
1 122(3ag))
6ago² (1 + T T//
1/3
+ { 3
1
E 20 [
1 2/ (3a
(1 (1-2/(3))) - 2p))
Now if E
ET
E
D
we know
Gajo²
(1+T/a8)) 1/3
21/2 + +T/3))
$
E
E
E
1-2n
1 1-2g(
(1 (1- 2/ (3a 2p)
oago² 2 (1 + T/a))
1/3
(1+T0))))) 3
B
B1-2p
D
1 2/(
(1 (1-22((ag)) 2p)
20 (1+ 3 (1-2((30))1122p)
6ago" (14T/05)
Then if
E. E1-2p EPP
we know
1-2/(30))
1/3 $
6ago² 2 (1 + T//a))
2 2a 2/(3g))
E
E
2
(1+
1- (3a
If
(1 4 (1-2((3a)))1 (1-pp) 2p)
E 11-2p ES
>
6aje0² (1+T/a3) 1/3
we know
2n1² 37 (1 - TT/a)) 20
E
< 2
E1-2p 2p
E
(1 2/ 2/(30)) - 2p)
2
E
D
(1 (1+T/ab) T/
2/ (3(ag)) 22p)
Hence under E
E
> E
we get
)9)
2 2 82
+ (11
1- 2/(303) (1-1)(800))
2 6aβo²
(1 + a/
2/(3ga))((1 2p)
Then by using 40
we know
E H
[ }
<4 max
E
E
T
<4 (1 + T/a)))
2 32
+(1 1- 2/ 23(3)
2 6aβ0
$
(1 2p)
61

---

Under review as a conference paper at ICLR 2023
1-1
2
(1 log (1+ (T/a)))
2a
+b6
+ (F(x)) - P*) +
7)
mmaa (1 2/(3))))
#1
3ug 441:maxxx
(
9o 2 (1 T/ T/a 1/3 3a -
m/max
3a0
-
log
1-p p
bp
=0 ((((a))
( Fr + B log (3T) + o² 2 + o28) 78) )
Case 2: p= 1.2 By similar proof, we still have
E H so ((F())) F* + B log (GT) + o² log T + o28) I
log
1 BASIC INEQUALITIES
In this section, we prove some technical lemmas used in our proof. Lemma 1.1. For > 0, G21 2 0, E (0, we have
E C
p 1
(co +
c:)
log
1+ Dims
p= 1
Proof. We first prove the case p + 1. From Lemma 3 in Levy et al. (202I) for b, > 0, bi2 2 0. p E (0, 1), we have
T
1-p
Σ
b
bj
b,)
p
Now we define
To min {t [T] : a > 0}.
By the definition of To. we know for any
<
k To L. 0. Then we have
To-1
C
C
C
(CD + Σ c.
(Co + 2i=1 ())
(co
+ Σ
Di=I
To-1
es
El=r, c)
(Co + Σiz G)P
G))
t=To
i
1-p p
1-p
1
Ci
C
p
1
T=
For p = 1, we know
Σ
T
4
T
Co -
1-1
4
Co
Ei=10
00 + Σ1
1= C
[=1
T
00 + Σ1
To C
log
6u + Σ1= Cj
1=1
Σ 6
= log
1+
Co
where the inequality holds by 1 1 < log
2
62

---

Under review as a conference paper at ICLR 2023
Lemma 1.2. For co > 0, G221 E (0, p E (0, 1]. we have
C+1
3
p
I
T Ei=a) Gi
1-p
p#1
1
+
(co + Σ c)p
C
log
1 1+
p=1
Proof. Define
i Σ
To min
< 1 E [T),
q c22c
then we know
C++
C++1
c
(Co +
Σi= G)
(Co +
1== G) 10
2
To 1
T-1
C+11
C++1
(co
E G)P
(co + -i=1 cs + Ei=To+1 c:)
To
t=To
1--1
C++1
a++
2
(cu + Ei=1++1 G)
t=
3c
a+1
(cu + Ei=To+1 G)P
1-P
-i=To+1 C3)
T
p p*1 1
+ 2 To 11
log
p=1
1-p
3c
Ei=1 Ci
2*1
1
E 4
log
1
1+
p p=1
where (a) is by Lemma 1.1
Lemma L.3. For co
>
0, G21 (0,c). p E (0, 13, we have
1-p
T
c+1
6c
1-p
Σ 9
p#1
+
(co +
Σ G)P
6
log
1+
-i 4
p=1
[=1
Proof. Define
1-1
To min
1E [T]
Σ
4 2 c
f=1
Then we know
T
To 1
T
C41
C+11
C+1
(co
1= G)P
(co
Σ E c)
1=T (co + Σ To 1
Ei=1 4 + Ei=1, c)P
1=1
To
Ct-1
C++1
(co + c +
Li=to c.)0
1-1
[=T
3c
T
G+1
(co + Σ To
G)P
1
Σ To=To (3
1-p
2* 1
6c
I-p
> 7
log
1
To
p p=1
63

---

Under review as a conference paper at ICLR 2023
6c
+
1-p
Lim1
T
Ci
1-p
p#
log
1
2i=1
p=1
80
where (a) is by Lemma
1.2
Lemma I.4. (Lemma 6 in Levy et al. (202l)) for C:21 E (0, c. we have
T
Σ
4
12 2c.
(1+ 4/1/3
Lemma 1.5. For 6221 E c0, we have, we have
C+1
5c.
Σ 2/4/3
Proof. Define
1-1
To min
EE [T]
C
2 c
i=
Then we know
T
To-1
T
C++1
C++1
C++1
Σ 1= 4//43
(1 i=1 4/4/3
(1 i= 4/443
t=1
1=
To 1
T
4-1
<
C++1 +
(1
Σi i=l
Q + 1
4/443
t=l
1=2
<3c+
4-1
(1 c Ei 4//43
1-1
t=To
< 3e Σ
C++1
(1 + Σ 4/3
t=
122+5c 5c,
where the last inequality is by Lemma I.4
Lemma 1.6. Given 0 S x S y S 1, E < 1. we have
(1- (1-z"/1 1//2 (1 - /832
y² x2
x2
y²
Proof. Note that
[1/2 (1 -1-20 2/2222
(1 y 11/2222 2
1
1/8
y
1/8
(-
I/E
1 y
1/8
2
x2
y²
x
x
2
11/l
1 y2/l
2
<
+
x
y
5.
now let h(x) = 1-
we can find l1((x) = (1-0)a214+4
11
< 0. Hence
2x
1 - 1/8
1 -
1/
h(z) h(y)) 2 0.
x
y
Besides, let g(x) = h(xx)
we can find that
(1
(1 12//
g(xx)= =
2 0.
lx?
64

---

Under review as a conference paper at ICLR 2023
This means
1 h(())= + Ey
1
h(x)
= g(x)) g(y) = 0,
Ex
which implies
1
5 h(x)) - Mwy) - fx Eyj
Thus finally have
(1 r 11/532
(1 - y 1012
1
1
(h(x)) - h(1)))
x22
y2
1/
2
tx
Ey
(y²
x2
1x
8²
Lemma 1.7. Given 0 < 1. E 1.2 we have
x²
(1 - (1= (1 1 "y /t-2)
2/1
Cx2
Proof. If é 1 2' then we know
(11 x //11///12-1111111111111111111111 -01- 1/-22)
(v? 2²²² S (v² =²) x² $ (v² x2)
xz²² 1p
2² - x² y g/104
y
If * 2. let M(x) denote x//))x//111 then we know (xxx) 31/e-32(C-1))"
By
Taylor's expansion, there exists I S y. such that
h(x) h(y) = h²(=) y)
1/1-332 1) - 28 +
8 (xr y).
This will give
( (1-x"'))a (1-1))1000 (10""))) = (1(()) h(y))2
(2 - 21/ f
+ 1)2
2/1-6 x
x (y x)
f2
2/1--
(1²-2²)
122
22 x²
211-
Lemma L8. Given m, n 2 0, For 0 S x S m. we have
n+1
(m x)x== <
m
n1
12 +
65

---

Under review as a conference paper at ICLR 2023
Proof. Note that
log ((m x))x") )- = loo (m - 2) + n log x = log (m - x) + n log Σ
n nlg
(a)
m
S
(n + 1) log
x n2
+ n log
n + 1
n2 +
n+1
(n + 1) log
n nllgg log
n
72 +
n+
where (a) is by the concavity of log function. Then we know (m x) x" -
n²
n+1
Lemma 199. Given A,A, 0,C
0, D, 0,0 S a S 1,if we have
(1+²)) " D,
X 1+ Blog
then there is Especially, when D 2 I, we know
C 1/u "
4uBD
X <
2A + 2B log
D.
4uBD
" +oV))
X <
2A + 2B log
C +
D.
Proof. Let = (X/D) then we know
DY
Y $ A+ Blog
1+
C
DY
1/u
=A+uBloy
1
C
(0)
2D
1/u
S + BBl
21/" +
y
C
D
1/u
A + uB uBlog 24/u BBloo
1+
r)
1
(2)
1/uy
1/u
A+ + B Bogg 2 + uB log
+ uB log
2uB
2uB
D
1/u
A+ B log 2+ (C/D)
I/u
Y
D log 2uB + B Blog
+
+
uB
2
2
C
Y
4uBD
(C/D)
< + A+ B log
2
C
where (a) is by (a + y)² < (2x)² (2 for x, 2 0. 2 (b) is by log S x
S x. Then
we know
4uBD
C
1/u
Y < 2A 2B log
+
C
1
1/u "
4uBD
C
+ X
2A 2B 2B
+
D.
D
66


Reviews:
[{"review_id": "nVzE_DBiib", "reviewer": "Reviewer_XfXs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a variance reduction method based on the STORM algorithm. Not like STORM, their algorithm does not require access to specific problem parameters such as the Lipschitz constant and the gradient bound. They prove that this algorithm will converge at the rate of $O(T^{-1/3})$ under slightly weaker assumptions than STORM.", "summary_of_the_review": "The paper proposes a fully adaptive optimization method based on STORM and proves its convergence under mild assumptions. ", "strength_and_weaknesses": "Strength:\n- Based on STORM’s framework, the paper designs an algorithm that does not require the knowledge of the Lipschitz constant or the variance bound constant, which is practical.\n- The algorithm converges under the same iteration complexity of $O(T^{-1/3})$ as the pioneering work STORM+ without the assumption that the function value is bounded. Their assumption is also slightly weaker than that of the original STORM.\n- The algorithms seem to have more stable convergence behavior than Adam and STORM+, and the heuristic version has a competitive convergence speed compared with Adam.\n\nWeakness:\n- The choice of parameter $p$ seems to have a large effect on the algorithm’s convergence.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "mfH_ryGGFXm", "reviewer": "Reviewer_HMzj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a few improved variants of STORM+ that generalizes to a broader class of functions with weaker assumptions and better theoretical guarantees. STORM+ is a VR algorithm for non-convex stochastic optimization problems. However, prior methods suffer from assumption like boundedness of function value and the theoretical convergence depends on such parameters. In this work, the authors propose an adaptive framework for STORM+ that removes this dependence and relaxes a few other assumptions. They also corroborated their new algorithms with empirical experiments.", "summary_of_the_review": "I think the paper is studying an interesting problem and has some nice idea in it. I think both the theory and experiment part could be improved more to make the contributions and supporting arguments clearer. Due to these reasons I gave my recommendation of the paper as below but am open to changing once my concerns are properly addressed.", "strength_and_weaknesses": "The paper is well-motivated and structured in a way to help authors understand the technical contributions in proving the results. I think the writing and exposition may be improved from the following few aspects, and would be happy to re-evaluate the paper once these are addressed properly:\n\n1) I think the technical section 3.1 and 3.2 could be written slightly more clearly to highlight which parts of the analysis are inherited from prior work, and which are new contributions. The current way written without reading the previous papers it is not immediate to me which part helps remove the additional / stronger assumptions in prior work. Also is there any difference in the adaptivity design part compared with prior work?\n\n2) The final complexity result stated in theorems doesn't agree on units (i.e. see definition of kappa, Q_1 in the paper etc.). When scaling the function by an additional factor L, the convergence result doesn't seem scale-invariant, which is a bit counter-intuitive to me. Would there be a proper analysis that could make this scale-invariant?\n\n3) The final high-probability bounds it may be helpful to directly state it using log(1/delta), and save the reasoning in the proof sketch. This makes the results more citable for future work.\n\n4) In the experiments, the figure could be improved a little bit to make each line of comparison look clearer (i.e. the color of STORM+ and another META-STORM-SG(H) looks quite confusing). Also, some parts of the comparison doesn't feel very fair since you are comparing META-STORM with heuristic to STORM+ without. It may be beneficial to use same heuristic on both methods and then compare.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XSR8iF6kgA0", "reviewer": "Reviewer_KkGZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the variance reduction technique for nonconvex optimization, along the research line of STORM and STORM+. The proposed META-STORM extends STORM+ by relaxing the assumption of bounded function value STORM+ while achieving the optimal convergence rate.", "summary_of_the_review": "This paper extends STORM+ by relaxing the assumption of bounded function value STORM+ while achieving the optimal convergence rate. The improvement is somewhat novel, but not very interesting.  ", "strength_and_weaknesses": "Strengths:\n\n1: This paper is somewhat novel.\n\n2: The theoretical analysis is technically sound.\n\n3: This paper is well-written and easy to follow. \n\n\nWeaknesses:\n\n1: The proposed META-STORM introduces an additional learning rate that needs to be tuned. (Note STORM and STORM+ do not require this additional hyperparameter.) Thus, META-STORM is not a fully adaptive algorithm. The authors need to explain this.\n\n2: How will relaxing the assumption of bounded function value STORM+ affect the optimization process in practice? Can the authors provide some examples with unbound function values that STORM+ would fail? Or this assumption is only required for the analysis of STORM+? The authors may need to provide more explanations here. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "9WNA6LWclqp", "reviewer": "Reviewer_caqd", "summary": "", "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": "", "summary_of_the_paper": "This paper studies variance reduced methods for nonconvex optimization. In particular, variants of STORM are proposed to remove the unreasonable assumptions in STORM+. Numerical results are then presented to demonstrate the proposed algorithms.", "summary_of_the_review": "This works falls more into theoretical part. And it indeed removes unreasonable assumptions in previous works. The numerical results do not fully support the theoretical findings due to the suboptimal implementation and benchmarks. ", "strength_and_weaknesses": "**Strength:** \nOverall, the strength of this work lies in its theoretical part. What interests me the most is the theoretical frame work of updating $a_t$ in META-STORM. This novel design helps to remove unnecessary assumptions in previous works. \n\n**Weakness:**\n\nThe numerical experiments are relatively weak compared to its theoretical part. \n\n- (W1) Numerical experiments on Cifar10 is not optimal, for example I assume that there is no learning rate decay by examining the loss curve of SGD. And the final test accuracy seems not matching the best that one can achieve (93 to 94%).\n\n- (W2) The paper is somehow contradicted: it motivates fully adaptively to parameters when choosing learning rates, yet has to tune through grid search for best numerical performance in numerical tests.  \n\n- (W3) It is not clear what are the specific heuristics used for in META-STORM (H). Moreover, can the authors explain the reasons for coordinate-wise learning rate in META-STORM(H)? It looks to me that the b_t update is a normalized adaptive learning rate, which is a simplified version of coordinate-wise learning rate. It is hence less intuitive for me to make adaptivity adaptive.\n\n- (W4) How does an epoch counts in the experiments? Since the proposed algorithms compute two gradients while SGD and Adam only needs one.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject