SGDEM: stochastic gradient descent with energy and momentum
Authors: Hailiang Liu
Xuping Tian
Venue: ICLR 2022 Submitted (2022)
Keywords: stochastic optimization
energy stability
momentum

Abstract: In this paper, we propose SGDEM, Stochastic Gradient Descent with Energy and Momentum to solve a large class of general nonconvex stochastic optimization problems, based on the AEGD method that originated in the work [AEGD: Adaptive Gradient Descent with Energy. arXiv: 2010.05109]. SGDEM incorporates both energy and momentum at the same time so as to inherit their dual advantages. We show that SGDEM features an unconditional energy stability property, and derive energy-dependent convergence rates in the general nonconvex stochastic setting, as well as a regret bound in the online convex setting. A lower threshold for the energy variable is also provided. Our experimental results show that SGDEM converges faster than AEGD and generalizes better or at least as well as SGDM in training some deep neural networks.

Under review as a conference paper at ICLR 2022
SGEM: STOCHASTIC GRADIENT WITH ENERGY AND MOMENTUM
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we propose SGEM, Stochastic Gradient with Energy and Momen- tum to solve a large class of general non-convex stochastic optimization problems, based on the AEGD method that originated in the work [AEGD: Adaptive Gradi- ent Descent with Energy- arXiv: 2010.05109] SGEM incorporates both energy and momentum at the same time so as to inherit their dual advantages. We show that SGEM features unconditional energy stability property, and derive energy- dependent convergence rates in the general nonconvex stochastic setting, as well regret bound in the online convex setting. A lower threshold for the energy variable is also provided. Our experimental results show that SGEM converges faster than AEGD and generalizes better or least as well as SGDM training some deep neural networks.
INTRODUCTION
In this paper, propose SGEM: Stochastic Gradient with Energy and Momentum to solve the following general non-convex stochastic optimization problem
min f(0) :- Eg (0: BERd
(1)
where Eg[-] denotes the expectation with respect to the random variable &. We assume that f is differentiable and bounded from below, i... f inf f(0) > -c for some e > 0.
Problem (T) arises in many statistical learning and deep learning models (LeCun al. 2015 Good- fellow et al. 2016 Bottou et al. 2018). For such large scale problems. it would be too expensive to compute the full gradient f(0). One approach to handle this difficulty is to use an unbiased esti- mator of V f0). Denote the stochastic gradient at the t-th iteration as gr. the iteration of Stochastic Gradient Descent (SGD) (Robbins & Monro [95I) can described as:
0,+1 = 0₂ ne9t,
where 7/2 is called the learning rate. Its convergence is known to be ensured if 7/ meets the sufficient condition:
Σ Me 00,
00.
However, vanilla SGD suffers from slow convergence due to the variance of the stochastic gradient, which one of the major bottlenecks for practical use of SGD (Bottou 2012 Shapiro Wardi 1996). Its performance is also sensitive to the learning rate, which is tricky to tune via (2) Dif- ferent techniques have been introduced to improve the convergence and robustness of SGD, such as variance reduction (Defazio et al.) 2014 Lei et al. 2017 Johnson & Zhang 2013 Osher et al.) 2019) momentum acceleration (Allen-Zhu 2018 Sutskever et al. [013)). and adaptive learning rate (Duchi al. 2011 Tieleman & Hinton 2012 Kingma& & Ba 2017). Among these, momentum and adaptive learning rate techniques are most economic since they require slightly more computation in each iteration. However, training with adaptive algorithms such as Adam or its variants typically generalizes worse than SGD with momentum (SGDM), even when the training performance is better
Wilson al. (2018).
The most popular momentum technique, Heavy Ball (HB)
(Po
1964 has been extensively
studied for stochastic optimization problems (Liu et al. 2020b Jin et al.
2018 Qian 1999., SGDM,

---

Under review as a conference paper at ICLR 2022
also called SHB, as a combination of SGD and momentum takes the following form
m = 1m4-1 + gt, 0.+1 = 0₂ m),
where mo and μ E (0, is the momentum factor. This helps reduce the variance in stochastic
gradients thus speeds up the convergence, and has been found to be successful in practice (Sutskever al. 2013).
AEGD originated in the work Liu & Tian (2020) is gradient-based optimization algorithm that adjusts the learning rate by transtormed gradient and an energy variable r. The method includes two ingredients: the base update rule:
rt
0.+1 = 02 + 21/ T++1 1 2
(3)
and the stochastic evaluation of the transformed gradient as
9t
Ut 2 (VT(OEE)) +
(4)
AEGD is unconditionally energy stable with guaranteed convergence in energy regardless of the size of the base learning rate > 0 and how o is evaluated. This explains why the method can have a rapid initial training process well good generalization performance (Liu & Tian 2020).
In this paper, we attempt to incorporate both energy and momentum at the same time so as to inherit their dual advantages. We do so by keeping the base AEGD update rule (3). but taking
0/ 2(1 31
m
my = 3m,-1 + 3)g,, B E ().
(5)
E() f(Or(((
+c'
We call this novel method SGEM. An immediate advantage is that with such i2 one can significantly reduce the oscillations observed in the AEGD stochastic cases. Regarding the theoretical results, in this work we develop convergence theory for SGEM, in both stochastic nonconvex setting and online convex setting. While Liu & Tian 2020). convergence analysis is provided mainly in deterministic setting, and the result in the stochastic setting is only upper bound the norm of the stochastic transformed gradient e rather than on f()).
We highlight the main contributions of our work as follows:
We propose novel and simple gradient- caudient-bbsedd method SGEM which integrates both energy and momentum. The only hyperparameter requires tuning the base learning rate.
We show the unconditional energy stability of SGEM, and provide energy deregdee vergence rates in the general stochastic nonconvex setting, and a regret bound for the online convex framework. We also obtain lower threshold for the energy variable. Our assump- tions are natural and mild.
We empirically validate the good performance of SGEM on several deep learning bench- marks. Our results show that
-The base learning rate requires little tuning on complex deep learning tasks. Overall, SGEM is able to achieve both fast convergence and good generalization per- formance. Specifically, SGEM converges faster than AEGD and generalizes better or at least well SGDM.
Related works. The essential idea behind AEGD is the so called Invariant Energy Quadratiza- (IEQ) strategy, originally introduced for developing linear and unconditionally energy stable schemes for gradient flows in the form of partial differential equations (Yang) 2016 Zhao et al.) 2017]. As for gradient-base methods, there has appeared numerous works on the analysis con- vergence rates. In online convex setting, regret bound for SGD is derived in Zinkevich (2003): ; the classical convergence results of SGD in stochastic nonconvex setting can be found in Bottou et al. (0018); For SGDM, refer the readers to Yu et al. (2019); Yan et al.] (2018); Liu et al. (202bb) for convergence rates on smooth nonconvex objectives. For adaptive gradient methods, most con- vergence analysis are restricted to online convex setting (Duchi et al. [201 Reddi et al. 2018 Luo ctt al. 2019). while recent attempts, such as Chen et al. (2019); Zou et al. (2019), 1,, have been made to analyze the convergence in stochastic nonconvex setting.
2

---

Under review as a conference paper at ICLR 2022
This paper is organized follows. We first review AEGD in Section 2 then introduce the proposed algorithm in Section 3 Theoretical analysis including unconditional energy stability, convergence rates in both stochastic nonconvex setting and online convex setting presented in Section In
Section 5
we report some experimental results on deep learning tasks.
Notation For vector 0 E IR", denote dt, the i-th element of 0 at the t-th iteration. For vector norm, we use ||. to denote la norm and use || so to denote (s norm. We also use [m]] to represent the list (I,..,, m for any positive integer m..
REVIEW OF AEGD
Recall that for the objective function assume that f is differentiable and bounded from below, i.e., f(0) > -c for some c > 0. The key idea of AEGD introduced in Liu & Tian (2020) is the use of auxiliary energy variable such that
ff(0) 2rv, e = V VV/((e) +
(6)
where taking Vf(0) + e initially, will be updated together with 0, and is dubbed as the transformed gradient. The gradient flow 0 - {(()) is then replaced by
0 2rc, v v.v.
A simple implicit-explicit discretization gives the following AEGD update rule:
v((..)
0 2Vf(0.) +
(7a)
0,+1 0: 12
(7b)
T++1 = (fe+1 0z)
(7c)
This yields decoupled update for Tz+1 = rre((1 + 2n|v=l²), which serves to adapt the learn-
ing rate, For large-scale problems, stochastic sampling approach preferred. Let [00;; &.) be stochastic estimator of the function value [(0;) at the (-th iteration, be stochastic estimator of the gradient f(.)) then the stochastic version of AEGD is still but with 2 replaced by
gt.
It 2VT(00 +c
Usually, Ie should be required to satisfy E[g.] an element-wi wise version of AEGD for stochastic training reads as
(0.) and [[ bounded. Correspondingly,
0t,2 2 (((()))) +
i (m),
(8a)
Tt.s
T4411 1 2mp
Ti,
(1( +
(8b)
0411,i 02.: 2,
(8c)
The element-wise AEGD allows for different effective learning rates for different coordinates, which has been empirically verified be more effective than the global AEGD (7). For further details, we refer to Liu & Tian (2020). We will focus only on the element-wise version of SGEM in what
follows.
THE PROPOSED ALGORITHM
In this section, we present novel algorithm to improve AEGD with added momentum in the fol- lowing manner:
m, = -mm-1 + - (1-8)g,,
mo = 0,
(9a)
m4
01
(9b)
2(1 - ((1-8')(/(0:45
3

---

Under review as a conference paper at ICLR 2022
where 3 (0, 1) controls the weight for gradient at each step. With defined, the update rule for r and 0 are kept the same as given in (8,, c). The relation between the energy and the momentum in the algorithm is realized through relating m, (as approximation to f) to ee (as approximation of VF V 2//ra): where U2 is used to update the energy r++1- In machine
learning tasks, f as loss function is often in the form of f(0) 1 Σ i=1 1.(0), where 15 measuring the distance between the model output and target label at the i-th data point, is typically bounded from below, that is, (0) -c, Vi [m]] for some >> 0. Hence in (9b) can be easily chosen in advance so that f(0Ø; Ee) as a random sample from {1,( } is bounded below by -c for all t [T]. We summarize this in Algorithm ( (called SGEM, for short).
A key feature of SGEM is that it incorporates momentum into AEGD without changing the overall structure of the AEGD algorithm (the update of and 0 remain the same) so that it is shown (in Section to still enjoy the unconditional energy stability property as AEGD does. In addition, by using m, instead of ft. the variance be largely reduced. In fact, proved in [iu al. (20206), under the assumption EE, lll9. [(+))]] = og < 00, My, which can be expressed as a linear combination of the gradients all previous steps,
m, (1 -
(10)
/=1
enjoys a reduced "variance" the sense that
Be
me (1
Σ g 3
S B) 3
Algorithm 1 SGEM. Good default setting for parameters are -- 0.2, 0.9
Require: the base learning 7f; constant such that (() + for all [T]:
momentum factor 3 E (0, 1).
Require: Initialization: 01; me 0: (((01:))++1
for 1 to T do
2: Compute gradient: 9t. V (0);
3: m. = 3m,-1 + (1 - 3)g, (momentum update)
4: Ut m4/ (2 8*) (ft;;
(transformed momentum)
5: Tr+1 (1 27yu @ vz) (energy update)
6: O.t11 = 02 - -2 O v, (state update)
7: end for
8:
return Or
Remark 3.1. (i) In Algorithm we use y to denote element-wise product, s/y denote
element-wise division of two vectors I, y E IR".
(ii) It is clear that m. defined (10) is not convex combination of gi. this is why there is a factor 1- in (o)); such treatment is dubbed as bias correction in Kingma & Ba (2017) for Adam.
(iii) most machine learning problems, we have f(0) Z 0, for which good default value for in
Algorithm is
4 THEORETICAL RESULTS
In this section, we present our theoretical results, including the unconditional energy stability of SGEM, the convergence of SGEM for the general stochastie nonconvex optimization, a lower bound for energy and a regret bound in the online convex setting.
4.1 UNCONDITIONAL ENERGY STABILITY
Theorem 4.1. (Unconditional energy stability) SGEM Algorithm is unconditionally energy siuble in the sense that for any step size 7) >> 0,
Ely E[r2,)] B(( r2, EE((Ott.. 0c.))) E [n],
(11)
4

---

Under review as a conference paper at ICLR 2022
that is E/ri,)] is strictly decreasing and convergent with E[r - Elri] as - oc, and also
lim E[(0++1,5 - - 0, 1000
0c,)) ( + c)2 e [n].
(12)
Remark 4.1. (i) The unconditional energy stability only depends @ c), irrespective of the choice for Vt. This property essentially means that the energy variable Tt, which serves to approxi- mate / f(0,) c G, is strictly decreasing for any 1) > O.
(ūi) 12) indicates that the sequence |10++1 -z]l converges to zero at rate of at least 1/Vl. We note that this does not guarantee the convergence of {0,} unless additional information on the geometry
of f is available.
Proof. From 88, c) we have
(0+11 0,,,) 4n7 1, (By
(2 1,) r++1,) (By
n((r,, (..) (nr. 1))
This upon taking expectation ensures the asserted properties. Such proof with use of the special form of it, the same as that for AEGD (see (seeLiu Tian (2020)..
4.2 CONVERGENCE ANALYSIS
Below, state the necessary assumptions that commonly used for analyzing the convergence of a stochastic algorithm for nonconvex problems, and notations that will be used in our analysis.
Assumption 4.1. I. (Smoothness) The objective function
4 is L-smooth: for any x, y E R".
f(v) < V()))
+ -
2. (Independent samples) The random samples {Er) are independent.
3. (Unbiasedness) The estimator the gradient and function value unbiased:
[gc] = ((,),, (e, f(O:).
Denoting the variance of the stochastic gradient and function value by og and oy, respectively: - (0.)) = o 1x, f(0.) of.
We have the following results.
Theorem 4.2. Let {0,} the solution sequence generated by Algorithm 7 with fixed > 0. Under Assumption ann and assume that the stochastic gradient and function value are bounded such that lgolloc I Go and < a E f(0(; + c B, then 0g S Goo and for all T 2 1.
T min PT, Σ [V
C1 C1+ C2n fon++ C3a
<
nT
where Ci, C2 Cg are constants depending on B, TJ L, Goo, B, n and f(0)) +
Remark 4.2. (i) Numerically we observe that for reasonable choice of n, Vt, decays much slower than 1/ Vt (See Fig thus the convergence result Theorem 4.2 is meaningful. The question of how depends on T theoretically interesting but subtle to characterize. Nevertheless, in The- orem 4.3 below, we identify a sufficient condition for ensuring a lower threshold for E(rTa}, from which we see that in the absence of noise, i.e 0g = O, min; r > 0 can be ensured, then the rate of O(1/T) is recovered Theorem 4.2
(ii) The assumption that the magnitude of the stochastic gradient is bounded is standard in non- convex stochastic analysis (Bttou et al. 2018). As for the upper bound on the stochastic func- tion value, we recall the introduced update rule in SGEM (9p.)): bound Vo. don't 't need an upper bound on f; while such upper bound is technically needed to bound m since
m, = 2(1 3B)T cot.
5

---

Under review as a conference paper at ICLR 2022
10
ctfar10 ResNet34
DenseNet121
cifar100 1D-roo--VGG1
ResNet34
eitar100 on DenseNet121
(1/2)
10
Epoch
Figure min; Tr, of SGEM with default base learning rate 0.2 training DL tasks.
We only present a sketch of proofs for Theorem 4.2 and 4.3 here using notation F; (f(0;:)) +c n/ and viewing r++1 as a n x diagonal matrix that is made up of rtt1.,, ".,, I. Detailed proofs, including two crucial lemmas and the full proof for Theorem 4.4 are deferred to the appendix.
Proof. Using the L-smoothness of f, we have
f(0++1) - f(0,) < v f(0.) (00+)) 02) + 2 1 - 0el12
(13)
The first term on the RHS is carefully regrouped as
B B
3 ff()))
T 1--17 + f(,)) (M--1T mer+11 1)tt
vf()))
Taking a conditional expectation on the first term gives
8 V.(..)
3 2
vS(0)) 2 (1 - 3) VB
min rr VS(0))1
We manage to bound the other two terms in terms of Σ Σ 14 and EL E 7e+1,m, Their bounds are presented in Lemma A.2 The asserted bound then fol- lows by further summation in with telescope cancellation for f(0.+1) f(0)) and bounding the last term
(13 using [12
4.3 LOWER BOUND FOR THE ENERGY
First note that the I-smoothness of f(0) implies the T---mmoohhness of F(0) = /f(0) with with
G2
LF = 2F(0*)
LL+
2F²
(14)
This will be used in the following result and its proof.
Theorem 4.3 (Lower bound of rT). Under the same assumptions as in Theorem 4.2 we have
BirTE max(F((*) nDi -022 D3, 0}.
(15)
where a = max(o,, max (Go, B) with Lf given in [4] and
D L
VBnF((t))
D2
(1 3)
G2
D3 + F(01) mil
-
2
4a
Moreover, in the absence of noise, we have
min PT. > minr; > if nD + 2D2 F(O0).
(16)

---

Under review as a conference paper at ICLR 2022
Remark 4.3. (i) T6 is only sufficient condition, not used guide for choosing 1/. We observe from our experimental results that the upper bound for to guarantee the positiveness of r can be much larger (See Figure
(ū) In Theorem 4.3] we measure how far r" can deviate from F()") in the worst situation. Under the stochastic nonconvex setting, n1 is the error brought by the step size 1, 3D2 due to the use of momentum, and a D3 is responsible for the existence of noise.
(iii) In the case of no momentum and no noise, we have
F(0*)
minrr, minr; if 7
D1
This caplures the result for the deterministic AEGD obtained in Liu & Tian 2020
Proof. Using the smssoothhnsss of F(0), we have
LF
F(0++1) (FF.) S VF(O.) (0.41 0,) 10 0cll?
(17)
in which the key term (F(0,)T(0+++) - 02) can be decomposed into three terms:
(V.(
9t ) ((++1 0c), 2F.
2F, 1 1- ( 3 02),
3-3) (0.+1 0t),
The first two terms bounded by using the bounded variance assumption and 12 respectively. We convert the last term, using (recall
T1+1 - Tty vr, - Or,i),
into expressions in terms of r141, Te,s which upon summation bounded by rr. The last term in (17) is bounded again by using (12).
4.4 REGRET BOUND FOR ONLINE CONVEX OPTIMIZATION
Our algorithm also applicable the online optimization that deals with the optimization problems having no or incomplete knowledge of the future (online). In the framework proposed in Zinkevich 2003), at each step I, the goal is to predict the parameter 0, F, where F 1 is feasible set, and evaluate it on previously unknown loss function fz. The nature of the sequence is unknown in advance, the SGEM algorithm needs be modified. This can be done by replacing f(0,, & by fe(O,) and taking (0,) in defined in (9). i.e.,
my 8m4-1 + (1 ((.).
(18a)
m2
=
(18b)
2(1 - 39) (.) +c
This algorithm also unconditional energy stable as pointed out in Remark 4.1 For convergence, we evaluate our algorithm using the regret, that is the sum of all the previous difference between the online prediction (O:) and the best fixed point parameter fr(0*) from a feasible set F::
T R(T) Σ (1.(0)) - f((0))),
where 6* = argmingeF Σt= f(( For convex objectives we have the following regret bound.
Theorem 4.4. Let {0,} be the solution sequence generated by SGEM with fixed n > 0. Assume that [| vlloc I Doc for all x. E F, < a I fa(O.) + S B, and 9r E F for all e [T]. When F and f. are convex, SGEM achieves the following bound on the regret, for all T 2 1,
1/2
R(T) S CT/T/n
Σ
(19)
TT3
where C. is constant depending on B, B, Doo and (1()))
7

---

Under review as a conference paper at ICLR 2022
Remark 4.4. (i) TTT > O. then R(T) is of order O(VT)) which is known the best possible bound for online convex optimization (Hazan 2019 Section 3.2). Our experimental results show that for in reasonable range, TT decays much slower than 1/vT T (See Figure 1 for which the convergence holds true in the sense that
R(T) T
lim
-.
(ii) The bound on Og typically enforced by projection onto F (Zinkevich 2003), with which the regret bound ( can still be proven since projection is contraction operator (azan 2019 Chap- ter 3). As for the upper bound on the function value, just like we remarked for Theorem technically needed to bound me.
5 NUMERICAL EXPERIMENTS
In this section, we compare the performance of the proposed method with several other methods, in- cluding AEGD, SGDM, AdaBelief (Zhuang al.) 2020), AdaBound (Luo et al. 2019), RAdam (Liu al., 2020a),, Yogi (Zaheer al. 2018), and Adam (Kingma & Ba 2017). when applied to train- ing deep neural networks. We consider three convolutional neural network (CNN) architectures:
VGG-16 (Simonyan & Zisserman 2013), ResNet-34 (He et al. (0166) DenseNet- 121 (Huang al.,
2017) on the CIFAR-10 and CIFAR- 100 datasets (Krizhevsky & Hinton, 2009); we also conduct
experiments on the ImageNet dataset (Russakovsky al.) 2015) with the ResNet-18 architecture (He et al. 2016).
For experiments CIFAR-10 and CIFAR-100, we employ the fixed budget of 200 epochs and reduce the learning rates by 10 after 150 epochs. The weight decay and minibatch size are set as 5 x 10-4 and 128 respectively. For the ImageNet tasks, we run 90 epochs and use similar learning rate decaying strategy at the 30th and 60th epoch. The weight decay and minibatch size are set as 1 x 10-4 and 256 respectively.
In each task, we only tune the base learning rate and report the one that achieves the best final generalization performance for each method:
SGEM: For CIFAR10 & 100 tasks, we use the default parameter 7) = 0.2; for the ImageNet task, the learning rate is set 17 0.3.
SGDM, AEGD: We search learning rate among (0.05, 0.1,
AdaBelief, AdaBound, Yogi, RAdam, Adam: We search learning rate among {0.0005, 0.001, 0.013, other hyperparameters such as B1, B2, are set as the default val- ues in their literature.
From the experimental results of CIFARIO & 100, we see that in all tasks, SGEM and AEGD achieve higher test accuracy than the other methods while the oscillation AEGD test accuracy is significantly reduced by SGEM expected. We also observe that the differences between these methods are more obvious experiments on CIFAR-100.
For the ImageNet task, since all previous experiments show that SGDM gives the highest test accu- racy, we focus on the comparison between SGDM and SGEM, and only run Adam as a represen- tative of other adaptive methods. The results are presented in Figure It can be seen that SGEM still shows fast convergence and is able to achieve comparable test accuracy as SGDM in the end of training. Here the highest test accuracy achieved by SGDM and SGEM are 69.89 and 69.92. respectively.
6 CONCLUSION
In this paper, we propose SGEM, which integrates AEGD with momentum. We show that SGEM still enjoys the unconditional energy stability property as AEGD, while the use of momentum helps to reduce the variance of the stochastic gradient significantly, as verified in our experiments. We
Code available at htwp://////oooooo........ooeeeea
8

---

Under review as a conference paper at ICLR 2022
96
96
SODEM
SCDEN
SCDEN
SCOOM
ADGI
94
SCOOM
AECO
AdhBellee
AdaBelef
TOo: 200//// 75
Allabound
Adaibunnd
92
AdsBound
Ithlem
BAdam
Adwm
Adam
86
88
95
04
85
05
50
100
150
200
150
200
200
Spoch
Spoch
Epech
(a) VGG-16 CIFAR-10
(b) ResNet-34 34 on CIFAR-10
(c) DenseNet- 121 on CIFAR-10 10
SCOEM
SCGEM
90
AEGI
AEGD
70-
SKLOM
SLE3M
66
66
AdaRelle
1:St ALOUDCY
70
AdaBelef
AdsBound
RAidom
Togi
TGS
Adamm
150
(d) VGG-16 CIFAR- 100
(e) 34 CIFAR-100
(1) DenseNet-121 CIFAR-
100
Figure 2: Test accuracy for VGG-16, ResNet-34 and DenseNet-122 on CIFAR-10/100
SCDEM SCOM
Toining Loss
T:st Acc.recreyy
SGDEM
SCDM
Idem
1.0
20
Epach
Epach
Figure 3: Training loss and test accuracy for ResNet-18 18 on ImageNet
also provide convergence analysis both online convex setting and the general stochastic noncon- vex setting. Since convergence results depend on the energy variable, lower bound the energy is also presented. Finally, we empirically show that SGEM converges faster than AEGD and generalizes better least well SGDM several deep learning benchmarks.
Based on our observations in this paper, we list some problems for future work. First, we believe there is threshold for 17", such that rr either tends positive number decays slower than 1/VT if 17 17" A further theoretical investigation this issue is desirable. Second, since r, is strictly decreasing, there is a room to limit r for controlling its decay whenever necessary. A proper energy limiter should be obtained.
REFERENCES
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18(221):1-51, 2018. URL http: http:t::///....o////a/pp///////
718/16-410.htm.
Leon Bottou. Stochastic Gradient Descent Tricks, volume 7700 of Lecture Notes in Com- puler Science (LNCS). Springer, neural networks, tricks of the trade, reloaded edition, Jan-

---

Under review as a conference paper at ICLR 2022
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Rev. 60(2):23-311, 2018.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of class of Adam-type algorithms for non-convex optimization. In International Conference on Learning Representa- tions, 2019.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA:
fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural In- formation Processing Systems, volume 27, 2014. URL URL/ttts///proceedinn neurips. 4d
httpppper/2214//le//eeeeeee Tebebee 3a41 4d44ddd9ffe
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121-2159, 2011.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. http:
//ww.deeplearn.npooo. org
Elad Hazan. Introduction online convex optimization. arXiv, abs/1909.05207, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp- 770-778, 2016.
doi: N0.119//VPRR.206.990
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2261-2269, 2017. doi: 10. 10.10//.2P222217.2244.
Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. Proceedings of the 31st Conference On Learning Theory, volume 75, pp. 1042-1085, 2018
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predic- tive variance reduction. In Advances in Neural Information Processing Systems, vol- ume 26, 2013. URL https: httpss////oocceeigg..eeeeeee ac1 (edd209cccceeeiie wew2252988cbbbbee
http:///ss..oppppr///1////////// pdd
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv, abs/1412.6980, 2017.
Alex Krizhevsky and Geoffrey Hinton, Learning multiple layers of features from tiny images. Uni- versity of Toronto, 2009.
Yann LeCun, Y. Bengio, and Geoffrey Hinton. Deep learning. Nature, 521:436-44, 05 2015. doi: 10. 10.1038/nature1455 15339.
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite-sum optimiza- tion via SCSG methods. In Advances in Neural Information Processing Systems, vol- ume 30, 2017. URL
.ddf
Hailiang Liu and Xuping Tian. AEGD: Adaptive gradient decent with energy. abs/2010.05109, 2020.
arXiv,
Liyua Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Ji- awei Han. On the variance of the adaptive learning rate and beyond. In International Confer- ence on Learning Representations, 2020a. URL htt.:tttt/ppprreeeeeeee wwwpeeiwwwwwweeeeeeeeeee meet/forum?ic. Ekgz2aEKDx
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. In NeurlPS, 2020b.
10

---

Under review as a conference paper at ICLR 2022
Liangchen Luo, Yuanhao Xiong, and Yan Liu. Adaptive gradient methods with dynamic bound of learning rate. In International Conference on Learning Representations, 2019.
Stanley Osher, Bao Wang, Penghang Yin, Xiyang Luo, Farzin Barekat, Minh Pham, and Alex Lin. 2019.
Laplacian smoothing gradient descent. arXiv,
B. T. Polyak. Some methods of speeding up the convergence of iterative methods. 2 Vyčisl. Mat i Mat. Fiz., 4:791-803, 1964. ISSN 0044-4669.
Ning Qian. On the momentum term gradient descent learning algorithms. Neural Net- works, 12(1):145-151 1999. ISSN 0893-6080. doi: https//col.ong/00.00000599999399
001 URL htt.s://www..ccceeeeeeeeeeee.ees
8089 80893608098001100
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In International Conference on Learning Representations, 2018.
Herbert Robbins and Sutton Monro. A stochastic approximation method. Ann. Math. Statistics, 22:400 1951. ISSN 0003-4851. doi: 10.1214//om///177725556 URL htttpstts://do..
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 15(3):211-252, 2015. doi: 10.1007/s1 12.-0077/11263---1--0886663
A. Shapiro and Y. Wardi Convergence analysis of gradient descent stochastic algorithms. Optim. Theory Appl., 91(2):439-544 1996. ISSN 0022-3239, doi: 10.1007/BF021190044 URL https:
ord/1..0rg.o..oo. 1007 021100004
90104
K. Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recog- nition. arXiv, 0bs//1409.1555 2015.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initial- ization and momentum in deep learning. In Proceedings of the 30th International Conference on Machine Learning, volume 28, pp. 1139-1147 1147, 2013.
Tijmen Tieleman and Geoffrey Hinton. RMSprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
Ashia C. Wilson, Rebecca Roelofs, Mitchell Stern, Nathan Srebro, and Benjamin Recht, The marginal value of adaptive gradient methods in machine learning, arXiv, abs/1705.08292.1 2018.
Yan Yan, Tianbao Yang, Zhe Li, Qihang Lin, and Yi Yang. A unified analysis of stochastic mo- mentum methods for deep learning. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 2955-29611 2018.
Xiaofeng Yang. Linear, first and recond-order unconditionally energy stable numerical schemes for the phase field model of homopolymer blends. Journal of Computational Physics, 327:294-316, 2016.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient mo- mentum sgd for distributed non-convex optimization. ICML, 2019.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In S. Bengio, Н. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: httt:::://ppocceediinee nwwrips....... ee/ 21C
Jia Zhao, Qi Wang, and Xiaofeng Yang. Numerical approximations for phase field dendritic crystal growth model based on the invariant energy quadratization approach. International Journal for Numerical Methods in Engineering, 110:279-300, 2017.

---

Under review as a conference paper at ICLR 2022
Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar C Tatikonda, Nicha Dvornek, Xenophon Papademetris, and James Duncan. Adabelief optimizer: Adapting stepsizes by the belief in observed gradients. In Advances in Neural Information Processing Systems, volume 33, pp. 18895, 2020. URL httpp:: hptp:see///oocciiiiippcc ngs nwwrips. httppsscccpppp////22..//// 2T1e//d2444455877522200 14
44
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICMI,, pp. 928 928-935, 2003.
Fangyu Zou, Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. sufficient condition for con- vergences of adam and rmsprop. 2019 IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), pp. 11119-11127 2019.
12

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A. PROOF OF THEOREM
For the proofs of Theorem 4.2 and Theorem 4.3 we introduce notation
== v f)) cc.
(20)
The initial data for ry is taken as V1,1 F1. We also denote the update rule presented in Algorithm
as
8,+1 = 0₂ 21,
(21)
where T2+1 is viewed as a n x n diagonal matrix that is made up of [M++1,,..., F1-1, r141m) Lemma A.1. Under the assumptions in Theorem 4.2 we have for all t [T].
(i) f/) 3 Go.
(ii) (P)))) = (0.) - s(0,) t
(ii)) [[FF] $ F(O.). In particular, E/ri,d = E[A] S F(0:) for all E [n].
(iv) of = Blll: - V f(0))11 S G and of (0);(( f(0)) s B².
(v) ((IF((.) F:1] S T.
(vi) EII VP.0.)
St 2F.
17
G² 3a
oj 2a
Proof. (i) By assumption || S Go we have
[V)) = ||E|g]]ll> S [Bllgellool S Goe.
(ii) This follows from the unbiased sampling of f(0,) = Eq, (f):::
(iii) By Jensen's inequality, we have
B.A. S E| = /F(00)2 F(O.).
(iv) By assumptions l1 0 I Go and f(1:: + B, we have
o3 Ellge v (0.)] Elllo (V)) & Gs. of f()ri))) f(0,) (II (010::))1111110 11f(0))) S?. (v) By the assumption
< <as S &0) + c F72 we have
[((t) f((:: Ex)
Elf((e) f(0: 1
((.,))) F.ll < E
2 o1.
F(O,) F.
2/a
(vi) By the definition of F(0), we have
9t 1 [VF()))
f(())) 9t
2F.
2F(0.) 2F,
V (O.) F(O.))
VS(0)) 9t
F(O.)
F.
(f( - F(8.))
2
Vf(Oe)
9t
2
+
2
F(B.)FF
F.
G2
1
pr. F(O.)12
+
V ((()))
9t.
112
2a
2a
13

---

Under review as a conference paper at ICLR 2022
where both the gradient bound and the assumption that 0 < a S f(f(: + F? are essentially used. Take an expectation to get
9t
189
G 2a
BlIE, - F(00)
1 Blll)((0)) - 9.
2F,
2a
Similar to the proof for (iv), we have
EI - F(O.))
of.
4a
This together with the variance assumption for gives
G
9t
1
2 +
2F:
8
2a g"
Lemma A.2. For any T 2 we have
(i)
E
El Us ret14) S
nF(1.) 27
(ii) E
T - m P
E
Et my resmm)] < 20.F(0.)
9
(iii)
EE
En |1++111l133
(01)
(iv)
E
Ei= 9h re+19t
8BnF(01) (1-3)-m
(v)
E
Σ ||e+1
(B.F 11-3pn
Proof. From Algorithm [line 5, we have
Fef -
T++1 2
Taking summation over / from to T gives
T Fi.s 1u-1T+11 2n
1
11 2n
1=1
From which we get
T Σ
T
nFi
o 12+1
Te <
2n
Taking expectation and using (iii) in Lemma A.I gives (i).
Recall that m, = 2(1 Piee, and F. S VB, we further get
2BnF 17
Σ m r441, 4B
Σ 1=1
o
r141
Using T141, S Vi and mo,i 0, we also have
Σ
Te m
(22)
1=1==1
Connecting the above two inequalities and taking expectation gives (ii).
Using TEt1a S T1,i, the above inequality further implies
T
T S
| 1|
141,
1=1
t=1
1=1 1=1
p < 2BnFf/n /
14

---

Under review as a conference paper at ICLR 2022
Taking expectation and using (ii) in Lemma A.1 gives (iii).
By my = 3m4-1 + (1- 11--1% B)9 we have
T Σ t=1
a T
a
3
D1 r++1 =
Tt+1,
1-
3
mzs
1 B
m
i=1
T
2,32
T
$ (1- 3)²
To+1. +
T0+1,
(1
3)
i= 1=1
2(1 + (
8BnFi
Σ
m, r1+1m $
(1 3)2
(1
3)
1=1
Here the third inequality is by (a + b)2 2n 2b3:
22
and 0 B < are used in the fourth
inequality. Taking expectation and using (iii) in Lemma A.1
gives (iv).
Similar as the derivation for (ii), have
T
8BnF7
|re+10el1
r.
2
(1 3)
Taking expectation and using (ii) in Lemma
gives (v).
We now ready prove Theorem 4.2 The upper bound on og is given by (iv) in Lemma A.I
Since f is L-smooth, we have
L ~ 10 0el1
f(0++1) S f(0,) + f(0.) (0++1 -0:) +
(((.))((00+1
(23)
2
n/ Denoting f) = n/ Pr, the second term in the RHS of (23 can be expressed as
v.(())) (0t+1 - 02)
= v f(0)) 112)
((() T m (since m, 2(1 - )
3
=
1
g
v.,) T 107++11mmm.. + - -))get
(24)
3
8
V f(.))
1/7++19
v.((e)) Thre+1m--1
3
1- 3
3
1 3
V f(t))
1h-1 +
V.((.)) (M--1T 1f(0))((n-112
mote+1)g
3
gr
((.))
10
3
We further bound the second term and third term in the RHS of 224.. respectively. For the second term, we note that 1-8 1- < 1 and
f(t) (M)-1 (7t-1ri--eere 1)
fV, (T) -
1 r+41)9 + (e.) (7:-1-mh)ras re411
IV)(),) (r.
- + (n--1 11)9, r.t1
(n-11 (V)(((()))))))) 9t) T
< [V//(0)))>>>>>>||]> r 11.11111llelle + 1n-11 T/e ret1
+ + - - retige
$ ( ( + (2m/ Va)g, rst19t
(25)
15

---

Under review as a conference paper at ICLR 2022
The third inequality holds because for positive diagonal matrix A, xT Ay || ||A||a.Illy/llo where ||A||1.1 = E; Osi- The last inequality follows from the result 1241, I Te,s for E [n], the assumption |/ S Go Fe 2 Va, and (i) in Lemma A.1
For the third term in the RHS of 24p. we note that
B
Bn
V f(,))
70 S
V vf((.) n0---m--l
3
(1-B)vr B)
in which
V f((,)) r141m4-1 ((44))1
19 -- (Vf((t)) 91) r+41m=11
- 2 12+ + - + (VV 9t) T 1141m1
(26)
where the last inequality is because for positive diagonal matrix A, xT Ay S 2o TA Ax Substituting (25) and (26) into (24). we get
22" Ay.
1 B 0.) S
T (1rxll1, (144)l11))
((0))
Vf(()) 7T-1Fe9t +
gr
2n
3n
+
9: r++19 + 2(1 3)va
m 1
(27)
Va
2(1 3)v0
2n
Bn
(ft) 91) T(419) + (1- B)
(V)())) - gt) r141m-11-
With 27 we take conditional expectation
23
with respect to (0) and rearrange
1 - 3
3
Vi(O.) The 17: I7. V.((.))
Ea
(
3
B
7/2 (11r.l1,1 11re41l1..)
B&
f(0.) - -(0++1)
Va
2m +
3n
Bn
oe r(+19 2(1- B) m -
(28)
Va
2(1 (1-8))a
2n (VS((.) 3 T14199
Bn
L (Vf(0.) 9t) r141m-11+++
2 11 - 00l1
(1 -1- Ba
where the assumption [9]] = ff(:)) is used in the first equality. Since Ei...., & are independent random variables, we set E Eç, Eg Bgr and take a summation on 28 over from to T get
T
1
3 g vf(i)) (1.r)
E
1=1
G2 E Va
E
((O)) s(er+1)]
+
|1ril1.11 |1t+1l111
2n
Bn
B1
Va
2(1 13)
E
Σ
91 re41hh
2(1 (011-)v[l Va
E
Σ m ram--1
(29)
2n
Σ (V (VI().)) - 9t) Trennge
+
Va
Bn
T
+
(V - 9t) re+1m.-1l
+
E
1 - 0=11?
10:11
(1 -1--90 7
16

---

Under review as a conference paper at ICLR 2022
Below bound each term in 29 separately. By the Seuchy-Schwarz inequality, get
T
E
(V.))) ge) r141m4-1
VS(()) de gellremm--ll
1/2 [.((0)) -ullt)
1/27
Σ 1m+11m-111
1/2
1/2
E
f(()) sall?
E
1r++1m-1l1
11?
S 12BTT/mF((L)))
(30)
where Lemma A. (ii) and the bounded variance assumption were used. We replace m in by and use Lemma A. (v) to get
(30
(VS(())) - (T)TTeee Tretggll
T
V f((t)) sell?) salle)
1/2
T
))
1/2
E
|re1gel
2 2Bn F
(31)
3
By 12 the last term in 29 is bounded above by
Tam Fa (01).
E
0
0.112
<
(32)
2
Substituting Lemma A.
(i) (iii), 32
30
into
29
to get
T
$ (f(0)) - fz) + DG Va
(00) 1/- 1/- v....)
nF(O,)
fr
[=1
8
8BnF(A1)
3BnF(01)
(33)
+
Va + 2(1 2(1-3)Va
(1 - -)² + (1- - Va
(4 + 3) 3))22BB1 ((O))VnTT, + Lim p² (01).
(1 Va
2
Note that the left hand side is bounded from below by
(1 3) E
min FT3
IV [V
B
where we used
1-
2
and n 2 n VB. Thus we have
C1 + Can + Csa, VnT
E
min PT5
7
17

---

Under review as a conference paper at ICLR 2022
where
C (f(0)) - 1NBB
1-3
GB 20 F(01)
(2 2
3
8B3/2
C2
+
(1 B)
Va
2(1 3-Va
(1 3)
(B3/2F((1))
VBLm
F²((1))
(1 V)3
2(1 - 3)2
(4+ B)
C3 = 11-8/a F(01).
A.2 PROOF OF THEOREM 4.3
First note that by (iv) in Lemma A. max {a o1) S max maxx(Goo B). Recall that F(0) = ((0) + c, then for any I, E {0r]rmo we have
Vf(x) VS(w)
VF VF(v)I
2F(x) 2F(y)
1 (F))) F(() ([(6)-V((0)
2
F(z)F(y)
Fly)
Go Fly) F(x)]+ + 2F(0*) [Vf(x) - ([())))(()))))) 2(F(0+))
-
One may check that
GM
IF(y) - F(x)) S 2F(0r) ||x - vll-
These together with the T-smoothness of f lead to
[|VF(z) VF(()) Lxl(æ yll.
where
G LF 2 +c ( 2(f(0))
This confirms the s--smoots of F, which yields
LF 11 0,11
- < (F((0) (((+) - 01) +
2
1 3r
(VF((..)
Jt
T(00+) 02) + gt
vz)
T (0c+1 0z)
2F
2F:
1 1- B
1 3r
I
3 vz) (0e41 - 0t) +
10 0cl12.
Summation of the above over / from 1 to T and taken with the expectation gives
4
-F(())))F((1)) <
-
Σ S.
(34)
i=l
18

---

Under review as a conference paper at ICLR 2022
where
T
3
S
E
B 1 (0.+1 - 0c)
1 1 Bt
S E
1 1- 3 ve) (0c+1 0()
2F
S3
(F)()))
9t
TT (0c+1 01)
2F:
LF 110+11 - 0,112
S
Below we bound S1, S2, S3, S₁ separately. To bound S1, we first note that
T1411 - = -21 =
= ve,e(0e+1,5 0.)
from which we get
T
S = E
T (0++1 -01)
3
1 8r
E
(r1+1,1 - tee)
E
T441, Tt,
(Since r4t1, S rt.))
E B[r4+1,1 - -nE
For S2, have
9t
1 -
gr
(01001 - 0.)
S2 E
2F:
1-3
n
T
B
E
Mh 1,i)
(2
2F,
B
Bm
T
<
(1 B)
11
m
1,
t=1
Bn
IE
T141 7
1/2
ΣΣ
r4 2z
1/27
B)
1=1
t=1
BV BVFF((O1)
(1 -8
where the fourth inequality is by the Cauchy-Schware inequality, the last inequality is by Lemma (ii).
A.T
19

---

Under review as a conference paper at ICLR 2022
For S3, by the Sauchy-Schwarze inequality, have
S3 = E
VF(0))
T - -bs)
2F:
10
9t [F((0))
|1100+1 0c)l
2F,
1/2
1/27
9t VF((0)
)12)
|10++1 - -
2F
1/2
T
1/2
VF((0))
91 ||(
E
1
0e11
2F
G2
1
< (m0
0g
8n3
2a
where the last inequality is by (vi) in Lemma A. and
112
Theorem 4.1
For S4, also by
12 in Theorem
we have
LF
T
LFMFF((0))
S4
E
10++1 - 0.112
2
2
With the above bounds on S1, S2, S3, St.
34
can be rearranged
F(0") By BvBnF(O)) - F(01)V V
G
1
L
o
+
3)-
4a
2
B[rr+1.1] - nE[Fi] + F(O1)
min E + (n - 1)E(fil) (nn - 1)B[A]+ + (F(0,)
E(Fil)
< min E E 1. B(IF(0)) Fil]
I min B 2/a" of
where (iii) in Lemma A.I was used. Hence,
min Err,l 2 max(F((0)) - n/D1 -
where a max max(aa,,0 ) and
D LpnF2(01)
D2 = (BnF(O1)
2
(1- 1-3)aa
G2
D3 2
+ F(01) +(00))mm
4a
A.3 PROOF OF THEOREM 4.4
Using the same argument as for (iv) in Lemma A.2
we have
T
8Bn (11)) +
T 1. <
(1 (1-391 18)n
20

---

Under review as a conference paper at ICLR 2022
With this estimate and the convexity of ft. the regret can be bounded by
R(T)
Σ [1(0.) 12(0))
S
Dt T (0. 0*)
"
T
10 0.1
Vt-1,,
i=1
1/2
1/2
10, - 0712
Σ
Σ
Te+1,
1/2
2D 22 1- B (0))) /nT/nn
TT+1.
where the fourth inequality is by the Cauchy-Schward inequality, and the assumption ||x- - y11x S Doo for all x. y E F is used in the last inequality.
21


Reviews:
[{"review_id": "c67hXXL-HdS", "reviewer": "Reviewer_TrUv", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The strengths are:\n- The authors propose a new algorithm based on the idea of 'energy' variable from the work  [AEGD: Adaptive Gradient Descent with Energy]. \n- They prove the unconditional energy stability property for SGDEM that is similar to AEGD and does not depend on the transformed momentum term $v_t$. They provide some convergence bounds for SGDEM for general stochastic nonconvex setting, and a regret bound for the online convex framework. \n- Numerical results are shown for their method and other state-of-the-art methods for training neural networks on ImageNet and CIFAR dataset. \n\nThe weaknesses are:\n- Firstly, the theoretical results use a lot of assumptions. Assumption 4.1 involved both the first and zero-th oracles, while Theorem 4.2 still needs that the gradient and function value are bounded. (Why assuming bounded variance while the gradients are bounded?). Similarly, Theorem 4.3 assumes that all iterates and the function value are bounded. The bounded function value is a strong assumption because it assumes that the algorithm can not go to some bad points with large output. We also need that $a$ is strictly larger than 0.\n- Secondly, the convergence of this method depends heavily on the lower bound of $r_{T,i}$. We know that the expectation of this sequence is strictly decreasing, and this term always appears at the denominator of the bound. Hence if this term goes to 0, the results are not informative. The authors can not prove a lower bound for $r_{T,i}$ (away from 0) even in Theorem 4.3, since the right-hand side of equation (15) can be 0 especially when $F(\\theta^*) -\\beta D_2 < 0$, no matter how they choose the learning rate. In addition, we can not choose an arbitrarily small learning rate to satisfy a positive lower bound, because it may harm the result of Theorem 4.2.\n- Finally, the experiment of SGDEM does not show encouraging performance (over existing methods) for CIFAR datasets. \n\nOther comments: \n- The name SGDEM appeared in another work (https://arxiv.org/pdf/2102.13653v1.pdf) which was published in February 2021. If this work was published later than that time period, I strongly suggest that the authors change the abbreviated name of your method to avoid confusion, and to distinguish the two methods. \n- In Algorithm 1, it is not quite reasonable to state a requirement in the beginning that the (stochastic) function value of the algorithm at $t$ is larger than minus $c$, for all iteration $t$. Since this is a hyper-parameter, it must be chosen in advance to satisfy that $-c$ is a lower bound of every possible input. Note that this hyper parameter $c$ also depends on the stochastic function value, not only $f$", "summary_of_the_paper": "In this paper, the authors propose a new algorithm called Stochastic Gradient Descent with Energy and Momentum (SGDEM) for non-convex stochastic optimization problems. The idea of 'energy' variable is from the work  [AEGD: Adaptive Gradient Descent with Energy]. The authors prove some similar property for SGDEM (unconditional energy stability) that does not depend on the transformed momentum term $v_t$. They prove some convergence bounds for SGDEM for general stochastic nonconvex setting, and a regret bound for the\nonline convex framework. In addition, they provide numerical results for their method in comparison with others for training neural networks. ", "summary_of_the_review": "To summarize, the authors proposed a momentum method based on AEGD using gradient and function value information. However, the theoretical and experimental results are not convincing enough. Hence I will encourage the authors to improve this paper and resubmit to another venue. \n\n---\nI thank the authors for your responses and the improvement of your \bmanuscript. After the discussion period, I decided to keep my initial suggestion.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JGRYBjyllv6", "reviewer": "Reviewer_e7GR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- Convergence analysis for SGDEM are shown for both nonconvex and convex settings. I have checked the proofs and find no problem but there is a chance I miss something.\n- Numerical experiments on different deep learning models on two CIFAR datasets illustate the advantage of SGDEM over other baselines.\n\nWeaknesses:\n- There is not much novelty in algorithm design as the idea of using momentum is quite common.\n- For nonconvex analysis, the assumption that the gradient and function value are bounded above is quite strong to me. It limits the applicability of the proposed method.\n- For convex analysis, the assumption that the domain is bounded and bounded function value are also strong.\n- Numerical experiments only consider deep learning examples which are nonconvex objectives. I wonder how SGDEM performs in objectives other than neural network. Adding examples including convex objectives is also recommended.", "summary_of_the_paper": "The paper  extends the adaptive gradient descent with energy method by incorporating momentum to obtain a new variant called stochastic gradient descent with energy and momentum (SGDEM). Convergence analysis is provided for nonconvex and convex expectation problems. Numerical experiments demonstrate the effectiveness of SGDEM over AEGD and other baselines.", "summary_of_the_review": "The paper contains substantial novelty in providing convergence analysis for SGDEM. However, the theoretical results rely on additional assumptions which are rather strong including bounded gradient, bounded function value (and bounded domain for convex setting) apart from standard assumptions. Numerical experiments only consider deep learning examples which is not extensive enough to illustrate the practical performance of SGDEM.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "I1GshhchCd8", "reviewer": "Reviewer_64qc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main result of the paper is combining the two existing algorithms: AEGM and momentum method. However, due to the momentum update of the gradient estimator, the analysis is different from the existing analysis of the AEGM and is more complex to some degree.  However, there are some issues w.r.t. the current analysis, for which the reviewer has no idea how one can fix that. \n\nThe experiments of the paper have shown some performance improvements.\n\nOverall, the reviewer thinks this work is marginally below the acceptance level. ", "summary_of_the_paper": "In this paper, the authors propose an algorithm called SGDEM, which is a combination of the AEGD method and the momentum method. For the proposed method, the authors have shown a convergence to the stationary point for the nonconvex case and a regret bound for the online convex case. Numerical experiments are done for several neural network training problems. \n\n", "summary_of_the_review": "The main issue:\n\nIn Theorem 4.2, the reviewer finds the LHS of the bound is deterministic (after taking expectation), while the RHS is stochastic due to the presence of $\\min_i r_{T,i}$, which is confusing to the reviewer. \n\nThis seems to be the following mistake in the analysis. In the first equation under Eq. (33), the authors seems to argue that \n$$E\\Big[ \\min_i r_{T,i}\\cdot \\sum_{t=0}^{T-1}||\\nabla f(\\theta_t)||^2 \\Big] \\geq \\min_i r_{T,i}\\cdot E\\Big[ \\sum_{t=0}^{T-1}||\\nabla f(\\theta_t)||^2 \\Big].$$\nHowever, this is not right in general since $\\min_i r_{T,i}$ is a random variable and is dependent on $E\\Big[\\sum_{t=0}^{T-1}||\\nabla f(\\theta_t)||^2 \\Big]$. It is also not possible to write $E\\Big[ \\min_i r_{T,i}\\cdot \\sum_{t=0}^{T-1}||\\nabla f(\\theta_t)||^2 \\Big] \\geq E\\Big[\\min_i r_{T,i}\\Big]\\cdot E\\Big[ \\sum_{t=0}^{T-1}||\\nabla f(\\theta_t)||^2 \\Big].$ \n\nThe reviewer does not have any idea to fix this issue. And it should be formally pointed out by the authors. In the worst case, the authors should at least formally make the following assumption, and point out that this assumption is UNCHECKABLE. \n\nAssumption: there exists a constant W>0 s.t. $\\min_i r_{T,i}\\geq W$ for any $T$ and any iteration sequence generated by the algorithm.\n\n\n\n\n\n\n\nMinor issues:\n\n1. The authors use both $f(\\theta;\\xi)$ and $f(\\theta,\\xi)$ in this paper, please unify the notation. \n\n2. On page 2, related works, the \"differentialequations\" should be \"differential equations\".\n\n3. In the first equation under (13), a coefficient of $\\frac{1}{1-\\beta^t}$ is missing. \n\n4. In the second equation under (13), the \"$\\leq$\" should be \"$\\geq$\" and \"\\sqrt{a}\" should be \"$\\sqrt{B}$\".\n\n5. Throughout the paper, the authors use the notation of $w^Tuv$. The authors should formally write $w^T(u\\odot v)$, in order to distinguish from the common understanding $(w^Tu)\\cdot v$. \n\n\n--------------------------------------------------------------------------------------------------------\nAfter revision, the author clear the mistake mentioned above. I have changed the score from 5 to 6,\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "-WPfJXYNNDc", "reviewer": "Reviewer_Su6j", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1: This paper proposes an improved variant of AEGD by incorporating the energy and momentum at the same time.\n\n2: Rigorous theoretical analysis is provided to verify the effectiveness of the proposed algorithm.\n\n3: This paper is well-organized and easy to read. The background knowledge is presented well and the related papers are cited. The readers can easily understand the paper. \n\nWeaknesses:\n\n1: The contribution of SGDEM over AEGD is limited. Although theoretical analysis is provided to verify the effectiveness of the proposed algorithm, the advantages of SGDEM over the AEGD are unclear.  As an improved version of AEGD, I believe detailed comparisons of theoretical results between these two methods are required.\n\n2:  The motivation to incorporate the momentum mechanism is straightforward since the momentum is widely used for optimization methods such as the popular SGD with momentum. However, the relation between the energy and the momentum is unclear. If it is just a combination of the known energy method in AEGD and the momentum method in SGD with momentum, the idea is not well-motivated.   \n\n3: The experimental results are weak. For most of the experiments, the proposed method performs worse than baseline AEGD even with the existence of oscillation. \n\n4: The experiments are only conducted for vision tasks while NLP is a very important application in deep learning. The optimization method should also be essentially tested for NLP tasks.", "summary_of_the_paper": "This paper studies stochastic gradient descent methods for general non-convex stochastic optimization problems. The proposed method SGDEM is an improved version of AEGD by incorporating both energy and momentum at the same time, which can achieve unconditional energy stability property. The authors provide an energy-dependent convergence rate for the non-convex stochastic setting and a regret bund in the online setting. ", "summary_of_the_review": "I have checked the response. I still think the idea is not novel enough and the experimental results are weak. Therefore, I would like to keep my score.  ", "strength_and_weaknesses": "", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers have the following concerns:
1. The theoretical results for the proposed method are weak. Theorem 4.2 cannot be considered as a convergence result, because the bound depends on some random variables $r_{T,i}$. The reviewers agree that a proper analysis would require some knowledge on the lower bound of these variables. Although there is some empirical explanation for this, the lower bounded assumption of  $r_{T,i}$ is not theoretically justified. The authors acknowledge that this is the main challenge for the present algorithm. In addition, the analysis requires bounded gradient and bounded function value, which is also strong for nonconvex settings. 
2. The empirical performance is not strong. In most experiments, the proposed method is not better than the baseline AEGD. The novelty and contribution of SGEM over AEGD is quite limited, since the idea of adding momentum is not new. 

The suggestions to improve this paper are as follows
1. Since the lower bounded assumption on $r_{T,i}$ is not standard and hard to verify, the authors might consider analyzing a theoretical guarantee for it. On the other hand, they could verify more experiments with various data sets to have some sense whether this assumption may be true or not. Next, please try to relax the strong assumptions as discussed. 
2. It is better if the authors can show the performance of SGEM for convex settings, and for other deep learning tasks (e.g. NLP) as suggested by the reviewers.

The authors should consider to improve the paper based on the reviewers' comments and suggestions and resubmit this paper in the future venues.
Decision: Reject