SAdam: A Variant of Adam for Strongly Convex Functions
Authors: Guanghui Wang
Shiyin Lu
Quan Cheng
Wei-wei Tu
Lijun Zhang
Venue:  (2020)
Keywords: Online convex optimization
Adaptive online learning
Adam

Abstract: The Adam algorithm has become extremely popular for large-scale machine learning. Under convexity condition, it has been proved to enjoy a data-dependent $O(\sqrt{T})$ regret bound where $T$ is the time horizon. However, whether strong convexity can be utilized to further improve the performance remains an open problem. In this paper, we give an affirmative answer by developing a variant of Adam (referred to as SAdam) which achieves a data-dependent $O(\log T)$ regret bound for strongly convex functions. The essential idea is to maintain a faster decaying yet under controlled step size for exploiting strong convexity. In addition, under a special configuration of hyperparameters, our SAdam reduces to SC-RMSprop, a recently proposed variant of RMSprop for strongly convex functions, for which we provide the first data-dependent logarithmic regret bound. Empirical results on optimizing strongly convex functions and training deep networks demonstrate the effectiveness of our method.

Published as a conference paper at ICLR 2020
SADAM: A VARIANT OF ADAM FOR STRONGLY CONVEX FUNCTIONS
Guanghui 5hin'n Lu', Quan Cheng', Wei- Wei Tu and Lijun Zhang! National Key Laboratory for Novel Software Technology, Nanjing University, China
24Paradigm Inc., Beijing, China
{wanggh, lusy, chengq, zhangl j] Lamda. n ju. edu. en, Ewwwcn@gmail...mm com
ABSTRACT
The Adam algorithm has become extremely popular for large-scale machine learn- ing. Under convexity condition, it has been proved to enjoy a data-dependent O(VT) regret bound where T' is the time horizon. However, whether strong con- vexity can be utilized to further improve the performance remains an open problem. In this paper, we give an affirmative answer by developing a variant of Adam (referred to as SAdam) which achieves data-dependent (log' regret bound for strongly convex functions. The essential idea is maintain faster decaying yet under controlled step size for exploiting strong convexity. In addition, under a special configuration of hyperparameters, recently proposed variant of R.Spprop for strongly convex functions, for which we provide the first data-dependent logarithmic regret bound. Empirical results on optimizing strongly convex functions and training deep networks demonstrate the effectiveness of our method.
SAdam reduces to SC- RCSpopp a
INTRODUCTION
Online Convex Optimization (OCO) is well-established learning framework which has both theoret- ical and practical appeals Shalev-Shwartz Shwartz et al.) 2012). It is performed in a sequence of consecutive rounds: In each round firstly learner chooses decision x; from convex set 'D C Rd the same time, an adversary reveals a loss function fe(-): : + IR, and consequently the learner suffers a loss (X:). The goal is minimize regret, defined as the difference between the cumulative loss of the learner and that of the best decision in hindsight (Hazan et al. 2016):
T
R(T) = Σ f(()))
min X
fx().
1=1
The most classic algorithm for OCO is Online Gradient Descent (OGD) Zinkevich 2003). which attains an O(v ((vT) regret. OGD iteratively performs descent step towards gradient direction with predetermined step size, which is oblivious the characteristics of the data being observed. result, its regret bound is data-independeni and can not benefit from the structure of data. To address this limitation, various of adaptive gradient methods, such as Adagrad (Duchi et al. 2011), RMSprop (Tieleman & Hinton 2012) and Adadelta (Zeiler) 2012) have been proposed to exploit the geometry of historical data. Among them, Adam (Kingma & Baj 2015), which dynamically adjusts the step size and the update direction by exponential average of the past gradients. has been extensively popular and successfully applied to many applications (Xu et al.] 2013 Greeor et al.] 2015 Kiros et al. 2015; Denkowski & Neubig 2017 7 Baharr et al. 2017). Despite the outstanding performance, Reddi et al. 2018) pointed out that Adam suffers the non-convergence issue, and developed two modified versions, namely AMSgrad and AdamNC. These variants are equipped with data-dependent regret bounds, which are O(VT) in the worst case and become tighter when gradients are sparse
"ijunn Zhang is the corresponding author.
Wee note that, as very recently pointed out by Tran et al. (211)) there still exists minor theoretical flaw in the analysis of Reddi et al. (2018), and such issue in fact appears many of recent variants of MSSggra/AAdamNeC In this paper, we provide simple way to fix this problem. The details found in Appendix G

---

Published as a conference paper at ICLR 2020
While the theoretical behavior of Adam in convex cases becomes clear, it remains an open problem whether strong convexity can be exploited to achieve better performance. Such property arises, for instance, in support vector machines well other regularized learning problems, and it is well- known that the vanilla OGD with an appropriately chosen step size enjoys a much better Ollog T) regret bound for strongly convex functions (Hazan et al. 2007). In this paper, propose a variant of Adam adapted to strongly convex functions, referred to as SAdam. Our algorithm follows the general framework of Adam, yet keeping a faster decaying step size controlled by time-variant heperparameters to exploit strong convexity. Theoretical analysis demonstrates that SAdam achieves a detendeennddtt O (log T' regret bound for strongly convex functions, which means that it converges faster than AMSgrad and AdamNC in such cases, and also enjoys huge gain in the face of sparse gradients.
Furthermore, under a special configuration of heperparameters, the proposed algorithm reduces to the SC-RMSprop (Mukkamala Hein 2017). which is a variant of RMSprop algorithm for strongly convex functions. We provide alternative proof for SC-RMSprop, and establish the first data-dependent logarithmic regret bound. Finally, we evaluate the proposed algorithm on strongly convex problems as well as deep networks, and the empirical results demonstrate the effectiveness of our method.
Notation. Throughout the paper, use lower case bold face letters to denote vectors, lower case letters to denote scalars, and upper case letters to denote matrices. We use || to denote the 22-norm and || || the infinite norm. For a positive definite matrix H Rdxd the weighted f2-norm is defined by ||x|] = x Hx.. The /l H--wiighted projection 11 (x) of x onto D is defined by [ = arg min by x1|2.- We use g. to denote the gradient of f.) at X₁. For vector sequence [v.]T=i: we denote the i-th element of by Ut,i- For diagonal matrix sequence {Mr) we use me,i to denote the i-th element in the diagonal of M₁. We use E = [gi.s.".., ,t,,] to denote the vector obtained by concatenating the i-th element of the gradient sequence (g:)
2 RELATED WORK
In this section, we briefly review related work in online convex and strongly convex optimization.
In the literature, most studies are devoted the minimization of regret for convex functions. Under the assumptions that the infinite norm of gradients and the diameter of the decision set are bounded, OGD with step size on the order of (1/vi) (referred to as convex OGD) achieves a data-inneeennent (dvTT) regret ZZinkevich 2003), where d is the dimension. To conduct more informative updates, Duchi et (201T) introduce Adagrad algorithm, which adjusts the step size of OGD in per- dimension basis according to the geometry of the past gradients, In particular, the diagonal version of the algorithm updates decisions as
X X2
Vi V
g.
where a > is a constant factor, V3 is a x d diagonal matrix, and Vi E [d] Dr,; = (Ej= 3.t// is the arithmetic average of the square of the i-th elements of the past gradicnts. Intuitively, while the step size of Adagrad, i.e., (a/ (a/vi)),, decreases generally on the order of O(1 ((1/V)) as that in convex OGD, the additional matrix V,-1/2 will automatically increase step sizes for sparse dimensions in order to seize the infrequent yet valuable information therein. For convex functions, Adagrad enjoys O [I. regret, which is O(dVT) in the worst case and becomes tighter when gradients are sparse.
Although Adagrad works well in sparse cases, its performance has been found deteriorate when gradients are dense due to the rapid decay of the step size since it uses all the past gradients in the update (Zeiler) 2012). To tackle this issue, Tieleman & Hinton (2012) propose RMSprop, which alters the arithmetic average procedure with Exponential Moving Average (EMA). i.c.,
V VV + (1 3)diag(g.g)
where 3 E [0, 1] is a hyperparameter, and diag(-) denotes extracting the diagonal matrix. In this way, the weights assigned to past gradients decay exponentially so that the reliance of the update is
2

---

Published as a conference paper at ICLR 2020
essentially limited to recent few gradients. Since the invention of RMSprop, many EMA variants of
Adagrad have been developed (Zeieer 2012 Kingma & Ba 2015 Dozat 2016). One of the most popular algorithms is Adam (Kingma & Ba 2015). where the first-order momentum acceleration,
shown in (2) is incorporated into RMSprop to boost the performance:
g. - + (1 -1-18 -1)g.
V, 32 1 + (1 (1-32) diaig
(3)
V, 1/21/
Xt+1 X2
V
While it has been successfully applied to various practical applications, a recent study by Reddi et al. (2018) shows that Adam could fail to converge to the optimal decision even in some simple one-dimensional convex scenarios due to the potential rapid fluctuation of the step size. To resolve this issue, they design two modified versions of Adam. The first one is AMSgrad,
V/ = max V2-1, Vi}
X++1 = X a
V g:
where an additional element-wise maximization procedure is employed before the update of x; to ensure stable step size. The other is AdamNC, where the framework Adam remains unchanged, yet time-variant 32 (i.e., 32t) is adopted to keep the step size under control. Theoretically, the two algorithms achieve deta-dependent D(VTE' UT >i= IITT, log T) and O(VTT V
Zi=1 V
E (lI,,lll regrets respectively. In the worst case, they suffer O and O(dVT) regrets respectively, and enjoy a huge gain when data is sparse.
Note that the aforementioned algorithms are mainly analysed in general convex settings and suffer at least (TV regret in the worst case. For online strongly convex optimization, the classical OGD with step size proportional to O(1/t) (referred to as strongly convex OGD) achieves a data- independent O(d log 7') regret (Hazan et al. 2007). Inspired by this, Mukkamala & Hein (0017)
modify the update rule of Adagrad in 1 as follows
X
V
so that the step size decays approximately on the order of O(1/t), which similar to that in strongly convex OGD. The new algorithm, named SC-Adagrad, proved enjoy data-dependent regret which is (d T) the worst case. They further extend this
bound of O Iog(Il[i:::II1)) idea to RMSprop, and propose an algorithm named SC-RMSprop. However, as pointed out in Section 3 their regret bound for SC-RMSprop is in fact data-independent, and this paper we provide the first data-dependent regret bound for this algorithm.
Very recently, several modifications of Adam adapted to non-convex settings have been developed (Chen et al.) 2019 Basu et al.) 2018 Zhang al. 2018| Shazeer & Stem 2018). However, to our knowledge, none of these algorithms are particularly designed for strongly convex functions, nor enjoy logarithmic regret bound.
3 SADAM
In this section, we first describe the proposed algorithm, then state its theoretical guarantees, and finally compare it with the SC-RMSprop algorithm.
3.1 THE ALGORITHM
Before proceeding to algorithm, following previous studies, introduce some standard defini- tions (Boyd & Vandenberghe| 2004) and assumptions (Reddi et al. 2018).
Definition 1. A function f(-) D + R is X-strongly convex Vx1 X2 D,
> 11 xx x2 12
f(x) 2 f(x2) Vf(x2) T (x,
xx) 2
(5)
3

---

Published as a conference paper at ICLR 2020
Algorithm 1 SAdam
Input: {51))-1, (52r 17
2: Initialize: &o- 0, Vo = Odxd; X1
3: for t =l..... 1...., T do
4: g. Vf((Xi)
5: g. BirBi-1 1 (1 (1r)g
6: V. 82oVi-1 111 (1 Bee ddag (gege
7:
V. V I
8:
x = Há's
X1 - 2 Vi g:
9: end for
Assumption 1. The infinite norm of the gradients of all loss functions are bounded by Goo. i.e., their exists a constant Go >> 0 such that maXxED V (x S oo holds for all t E [T]. Assumption 2. The decision set DD bounded. Specifically, their exists a constant Doo > such that maxx, NeD || X2|loo
D
We are now ready to present our algorithm, which follows the general framework of Adam and is summarized in Algorithm | In each round t, we firstly observe the gradient at x, (Step 4), then compute the first-order momentum & (Step 5). Here 31g a variantriant hyperparameter. Next, we calculate the second-order momentum Vi by EMA of the square of past gradients (Step 6). This procedure controlled by 32.. whose value will be discussed later. After that, we add a vanishing factor to the diagonal of V and get V/2 (Step 7), which is a standard technique for avoiding too large steps caused by small gradients in the beginning iterations. Finally, update the decision by &, and Vr, which is then projected onto the decision set (Step 8).
While SAdam is inspired by Adam, there exist two key differences: One is the update rule of x, in Step 8, and the other is the configuration of 32 in Step 6. Intuitively, both modifications stem from strongly convex OGD, and jointly result in faster decaying yet under controlled step size which helps utilize the strong convexity while preserving the practical benefits of Adam. Specifically, the first modification, we remove the square root operation in (4) of Adam, and update x₁ at Step 8 as follows
X Xx
In this way, the step size used to update the i-th element of is 4 which decays in general on the order of (L/tt), and can still be automatically tuned in a per-feature basis via the EMA of the historical gradients.
The second modification is made to 82,, which determines the value of V2 and thus also controls the decaying rate of the step size. To help understand the motivation behind our algorithm, we first revisit Adam, where 3z is simply set to be constant, which, however, could cause rapid fluctuation of the step size, and further leads to the non-convergence issue. To ensure convergence, Reddi et al. (2018) propose that 32r should satisfy the following two conditions:
Condition 1. Vt E [T] and i E [d],
Vio
1/2
V Tu 2 0.
a
a
Condition 2. For some and vt (T), i (d.
1 B2i)
The first condition implies that the difference between the inverses of step sizes in two consecutive rounds is positive. It is inherently motivated by convex OGD (i.e., OGD with step size z. where a a constant factor), in which
V
2 0, Vt E T
4

---

Published as a conference paper at ICLR 2020
is key condition used in the analysis. We first modify Condition by mimicking the behavior of strongly convex OGD as we are devoted to minimizing regret for strongly convex functions. In strongly convex OGD (Hazan et al., 2007). the step size at each round t is set as with a 2 & for X-strongly convex functions. Under this configuration, we have
t
- X, v
a
Motivated by this, we propose the following condition for our SAdam, which is an analog to 77) Condition 3. Their exists constant C 0 such that for any G. we have VI [T' and [d].
tug
(t 1) A(1 - 31).
α
Note that the extra (1 - B1) in the righthand side of (8) is necessary because SAdam involves the first-order momentum in its update.
Finally, since the step size of SAdam scales with 1/t rather than 1/v in Adam, modify Condition
2 accordingly as follows:
Condition 4. For some
O, E E [T]
and i [d].
j-j
ΣΣ II
820-2+1 - -1-5))19)9-.. 2 Σ g3
(9)
k=1
3.2 THEORETICAL GUARANTEES
In the following, we give a general regret bound when the two conditions are satisfied.
Theorem 1. Suppose Assumptions 7 and 2 hold, and all loss functions f1(:)...,, fr(.) X- strongly convex. Let > O, 81 = 31 where 3 E =0, 1), E [0, 1), and {82 E 10, be a parameter sequence such that Conditions 4 are satisfied. Let a 2 C. The regret of SAdam satisfies
X.
d3, (G2 + R(T) < 22(1 B1) 2a(1 (1) 1)2 (1 B1)3
+
+ ac
log
1
Σ
Ij.s
+ +1/
(10)
Ç8
The above theorem implies that our algorithm enjoys an O bound, which is Oo 7) in the worst case, and automatically becomes tighter whenever the gradients are small or sparse such that | < G2 for some i E [d]. The superiority of data-dependent bounds have been witnessed by long list of literature, such as Duchi et al. (201T); Mukkamala & Hein 2017); Reddi et al. (20T8). the following, we give some concrete examples:
Remark 1.
regret
Consider a one-dimensional sparse setting where non-zero gradient appears with probability c/T and e 1 is constant. Then E log [ET s )] Ollo(()), which is a constant factor.
Consider a high-dimensional sparse setting where in each dimension of gradient non-zero element appears with probability p = (mm-d)/d with m E [1,d) d) being a constant. Then, d log ( = (m i log T), which much tighter than Old T).
E
Remark In practice, first-order momentum is powerful technique that can significantly boost the performance (Reddi et al., 2018), and our paper is the first to show that algorithms equipped with such technique can achieve logarithmic regret bound for strongly convex functions. However, since the regret bound of SAdam is data-dependent, it is difficult rigorously analyse the influence of the first-order momentum parameter 31 as it affects all the gradients appearing in the last term of the regret of Theorem I We will further investigate this in the feature work. We note that the regret bounds of adaptive algorithms with first-order momentum (e.g., Reddi et al. 2018 Chen et al. 2019) all share similar structure regret bound with respect /1.
5

---

Published as a conference paper at ICLR 2020
Next, provide an instantiation of {B211==1 such that Conditions and hold, and derive the following Corollary.
Corollary 2. Suppose Assumptions 7 and 2 hold, and all loss functions fı(-),.... fr(()) X-
strongly convex. Let 8 > 0, 312 = B,1" where v, B1 E [0, 1), and
S 82. S T where
Y E (0, Then we have:
(2-7)0% 1. For any 2 XI-B) V1 E [7] and E [d].
Wig (t - 1) < X(1 -B)).
For all t E [T] and j E [d].
[-j
Σ
II
2 Σ
gz.
5= km1
==1
(2-7) Moreover, let a 2 A(1-8:)
and the regret of SAdam satisfies:
dD R(T)= 20(11 - B1) 20x11 (1) - 1)2 7(1 313
d3 D2, (G2 + 6)
a
log
2 + Σ j=1
Furthermore, special case, by setting 81 0 and 1
821 S 7. algorithm
reduces to SC-RMSprop (Mukkamala & Hein 2017). which is a variant of RMSprop for strongly convex functions. Although (ukhouua Mukkamala & Hein (2017) have provided theoretical guarantees for this algorithm, we note that their regret bound is in fact data-independent. Specifically, the regret bound provided by Mukkamala & Hein (2017) takes the following form:
SdD2 R(T) S
TUT,
(1 7) + log T) inf JE JUyz +
log
(1I)
2a
2
1=1
Focusing on the denominator of the last term in (1). we have
inf juy, 5 10i, d Go +
SE(1.T]
thus
(1+ da (1 (l0g T 1) inf infse(L.]jjvj. +
Go +
which implies that their regret bound is of order Odd T)). and thus data-independent. In contrast, based on Corollary 2 we present new regret bound for SC-RMSprop in the following, which is
O 1= log(le (o[[)lg..... l)). and thus data-dependent.
Corollary 3. Suppose Assumptions 7 and 2 hold, and all loss functions fi(-)....,
are A
S fz 11- where E (0, 1). Let a 2 (2-7)02 Then SAdam reduces SC-RMSprop, and its regret satisfies
strongly convex. Let > 0, 81c = O, and
dD2
R(T)
log
Eo +1
(12)
2a
Finally, we note that Mukkamala Hein (017)) also consider more general version of SC-RMSprop which uses time-varian non-increasing 8 for each dimension i. In Appendix D we introduce the 8-variant technique to our SAdam, and provide the corresponding theoretical guarantee.
EXPERIMENTS
In this section, present empirical results optimizing strongly convex functions and training deep networks. More results can be found Appendix.
Algorithms. In both experiments, compare the following algorithms:

---

Published as a conference paper at ICLR 2020
10a
A.lagaddd M.R.prpppppppp
RMipprep
ANSprop
Regret
Regret
AdamNC
Regret
10a
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
Dataset proportion
Dataset proportion
Dataset proportion
(a) MNIST
(b) CIFARIO
(c) CIFAR100
Fig. 1: Regret v.s. data proportion for ég-regularized softmax regression
SC-Adagrad MMkkaamala & Hein 2017) with step size = =a/t.
SC-RMSprop (Mukkamala & Hein 2017 with step size a, a/t and 3 0.9
Adam (Kingma & Ba 2015) and AMSgrad (Reddi et al. 2018), both with 8 = 0.9,
32 = 0.999, 0₁ a/v for convex problems and time-invariant de for non-convex problems.
1/4, and az a/ / for convex problems and a tume-invarian O2 a for non-convex problems.
AdamNC (Reddi al. 2018), with B1 0.9. f2.
Online Gradient Descent (OGD), with step size a = a/t for strongly convex problems and for non-convex problems.
time-invariant
Our proposed SAdam, with 31 0.9, 32,
For Adam, AdamNC and AMSgrad, we choose = 10 according to the recommendations in their papers. For SC-Adagrad and SC-RMSprop, following Mukkamala & Hein (2017), choose time-variant ó,,5 = _ Exxtr, for each dimension i, with & 0.1, E2 = for convex problems and & 0.1, Σ 0.1 for non-convex problems. For SAdam, since the removing of the square root procedure and very small gradients may cause too large step sizes in the beginning iterations, we use rather large 8 10-2 2 avoid this problem. To conduct fair comparison, for each algorithm, choose a from the set {0.1, 0.01, 0.001, 0.0001} } and report the best results.
Datasets. In both experiments, examine the performances of the aforementioned algorithms three widely used datasets: MNIST (60000 training samples, 10000 test samples), CIFARIO (50000 training samples. 10000 test samples), and CIFAR 100 (50000 training samples, 10000 test samples). We refer to LeCun (1998) and Krizhevsky (2099) for more details of the three datasets.
4.1 OPTIMIZING STRONGLY CONVEX FUNCTIONS
In the first experiment, we consider the problem of mini-batch éz-regularized softmax regression, which belongs to the online strongly convex optimization framework. Let K be the number of classes and be the batch size. each round i, firstly mini-batch of training samples {(Xm> Fm ) m arrives, where y/1 E [K]. Vi [m]. Then, the algorithm predicts parameter vectors {wa, bi Jij and suffers a loss which takes the following form:
e J. +b
K
J(w, b)
log
+ A
Wx
X2
12
Ej=1 e. Netbb
i=1
k=1
1=1
The value ê₁ and A2 are set to 10-2 for experiments. The regret (in log scale) v.s. dataset proportion is shown in Fig. It can be seen that our SAdam outperforms other methods across all the considered datasets. Besides, we observe that data data-dependent strongly convex methods such as SC-Adagrad, SC-RMSS SC-RMSprop and SAdam preform better than algorithms for general convex functions such as Adam, AMSgrad and AdamNC. Finally, OGD has the overall highest regret on all three datasets.
7

---

Published as a conference paper at ICLR 2020
0.20
2.0
0.15
SCMMppp
0G0
1.5
SC. RN5prp
OCD
SC M.sprp
Adam
Adan
3.5
Adamn
AdamiIC Amaggadd
Lozs
AdumNIC
Adumiic
0.10
Amegrad
3.0
Amegrad
1.0
0.05
1.5
0.00
10
20
30
40
50
20
40
60
80
100
20
40
60
80
100
Epoch
Epoch
Epoch
(a) MNIST
(b) CIFARIO
(c) CIFAR 100
Fig. 2: Training loss v.s. number of epochs for 4-layer CNN
0.40
Accuracy
0.99
Test Accuracy
0.70
Accuracy
00.35
SAdam
SAdam Adspprad
0.30
SAdom Adagrad
joMbpropp
Adagrad
0.65
MMliprap
stoppppp
0.25
AdamNc
Adamiic
AdamNc
Amagraa
Amagred
Amagrad
0.98
0.60
80
0.20
Epoch
Epoch
Epoch
(a) MNIST
(b) CIFAR1O
(c) CIFARI00
Fig. 3: Testing accuracy v.s. number epochs for 4-layer CNN
4.2 TRAINING DEEP NETWORKS
Following Mukkamala & Hein (017)). we also conduct experiments on a 4-yayer CNN, which consists of two convolutional layers (each with 32 filters of size 3), one max-poot max-pooling layer (with 2 window and 0.25 dropout), and one fully connected layer (with 128 hidden units and 0.5 dropout). We employ ReL.U function as the activation function for convolutional layers and softmax function as the activation function for the fully connected layer. The loss function is the cross-entropy. The training loss v.s. epoch is shown in Fig. _ and the testing accuracy v.s. epoch is presented in Fig. 4 As can be seen, our SAdam achieves the lowest training loss on the three data sets. Moreover, this performance gain also translates into good performance on testing accuracy. The experimental results show that although our proposed SAdam is designed for strongly convex functions. it could lead to superior practical performance even in some highly non-convex cases such as deep learning tasks.
5 CONCLUSION AND FUTURE WORK
In this paper, we provide a variant of Adam adapted to strongly convex functions. The proposed algorithm, namely SAdam, follows the general framework of Adam, while keeping a step size decaying in general on the order of O(1(t) and controlled by data-dependent heperparameters to exploit strong convexity. Theoretical analysis shows that SAdam achieves data-dependent Od 2") regret bound for strongly convex functions, which means that it converges much faster than Adam, AdamNC, and AMSgrad in such cases, and can enjoy huge gain in the face of sparse gradients. In addition, we also provide the first data- dependent logarithmic regret bound for SC- RMSprop. Finally, we test the proposed algorithm on optimizing strongly convex functions as well as training deep networks, and the empirical results demonstrate the effectiveness of our method.
Since SAdam enjoys a data-dependent Odd T) regret for online strongly convex optimization, can be easily translated into data-dependent Odd T/T) convergence rate for stochastic strongly convex optimization (SSCO) by using the auline-to-batee conversion (Kakade & Tewari 2009). However, this rate is not optimal for SSCO, and it is sill open problem how to achieve data- dependent (d/T) convergence rate for SSCO. Recent development on adaptive gradient method (Chen et al., 2018) has proved that Adagrad combined with the multi-stage scheme (Hazan & Kale 2014) can achieve this rate, but it is highly non-trivial to extend this technique to SAdam, and we leave it as future work.
8

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGEMENT
This work was partially supported by NSFC (61976112), NSFC-NRF Joint Research Project (61861 146001), and the Collaborative Innovation Center of Novel Software Technology and In- dustrialization.
REFERENCES
Parnia Bahar, Tamer Alkhouli, Jan- Thorsten Peter, Christopher Jan-Steffen Brix, and Hermann Ney. Empirical investigation of optimization algorithms in neural machine translation. The Prague Bulletin of Mathematical Linguistics, 108(1):13-25, 2017.
Amitabh Basu, Soham De, Anirbit Mukherjee, and Enayat Ullah. Convergence guarantees for rmsprop and adam in non-convex optimization and their comparison to nesterov acceleration on autoencoders. arXiv preprint
2018.
Sebastian Bock, Josef Goppold, and Martin Wei. An improvement of the convergence proof of the optimizp arXiv preprint arXiv:1804. 10587, 2019.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. In Proceedings of the 7th International Conference on Learning Representations, 2019.
Zaiyi Chen, Xu, Enhong Chen, and Tianbao Yang. Sadagrad: Strongly adaptive stochastic gradient methods, In Proceedings of 35th International Conference on Machine Learning, pp. 912-920, 2018.
Michael Denkowski and Graham Neubig. Stronger baselines for trustable results in neural machine translation. Proceedings of the 1st Workshop on Neural Machine Translation, pp. 18 28, 2017.
Timothy Dozat. Incorporating nesterov momentum into adam. In Proceedings of 4th International Conference Learning Representations, Workshop Track, 2016.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal Machine Learning Research, 12:2121-2155 2011.
Karol Gregor, Ivo Danihelka, Alex Graves, Danilo Jimenez Rezende, and Daan Wierstra. Draw: recurrent neural network for image generation. In Proceedings of the 32nd International Conference on Machine Learning, pp. 1462-1471, 2015.
Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-conved optimization. Journal of Machine Learning Research, 15:2489-2512. 2014.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 69:169-192, 2007.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends in Opti- mization, 2(3-4)::57-322 2016.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proceedings of the 29th IEFE Conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Sham M Kakade and Ambuj Tewari. On the generalization ability of online strongly convex programming algorithms. In Advances in Neural Information Processing Systems 21, pp. 801-808, 2009.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of 3rd International Conference Learning Representations, 2015.

---

Published as a conference paper at ICLR 2020
Ryan Kiros, Yukun Zhu, Ruslan R Salakhutdinov, Richard Zemel, Raquel Urtasun, Antonio Torralba, and Samja Fidler. Skip-thought vectors. In Advances in Neural Information Processing Systems 27, pp. 3294-3302 2015.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmistt/ 1998.
H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex op- timization. In Proceedings of the 23rd Annual Conference on Learning Theory, pp. 224-256, 2010.
Mahesh Chandra Mukkamala and Matthias Hein. Variants of rmsprop and adagrad with logarithmic regret bounds. In Proceedings of the 33rd International Conference on Machine Learning, pp. 2017.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. the convergence adam and beyond. In Proceedings of 6th International Conference Learning Reprexentations, 2018.
Shai Shalev-Shwartz al. Online learning and online convex optimization. Foundations and R in Machine Learning, 4(2):107-194, 2012.
Noam Shazeer and Mitchell Stern. Adafactor: Adaptive learning rates with sublinear memory cost. In Proceedings of the 35th International Conference on Machine Learning, pp. 4596-4604, 2018.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, pp. 26-31, 2012.
Phuong Thi Tran et al. On the convergence proof of amsgrad and a new version. IEEE Access, 11706-61716, 2019.
Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio. Show, attend and tell: Neural image caption generation with visual attention. In Proceedings of 32nd International Conference Machine Learning, pp. 2048-2057. 2015.
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv: 1212.5701 2012.
Jiawei Zhang, Limeng Cui, and Fisher B Gouza. Gadam: Genetic-evolutionaay adam for deep neural network optimization. arXiv preprint arXiv:180..07500 2018.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning, pp. 2003.
10

---

Published as a conference paper at ICLR 2020
A
PROOF OF THEOREM
From Definition
!
we can upper bound regret as
T
T
T
A
R(T)
Σ
fx))
Σ
f(
g
[x
x.)
2 x x. 1
(13)
t=1
1=1
t=1
where x, == m Σ
(x) is the best decision in hindsight. On the other hand, by the update we have
rule of 1 in Algorithm
1
|x++1 - x. x.11i; [ (x. ooVi Bc) x, x/12
S Xx ar Vi= -x.1l,
2a1 (x: - x.) + 1|x: - xx11
+ ai 18
(14)
2a, (3118:-1 + (1 B1()ge) T (xx - x.)
+ ||x: -
x. -
+ agl l leall
where := a/t, and the inequality is due to the following lemma, which implies that the weighted projection procedure is non-expansive.
Lemma 1. (McMahan & Streeter, 2010 Let Rddd be a positive definite matrix and D C Rd be a convex set. Then we have, Vx.y
R"
[TT((x) (y) S xx - -yla--
(15)
Rearranging 14
we have
Xx X. 11
||x x. x.113
B1t T
(x:
x.)
gi-1 (x. xi)
20y(1
B1e)
31
+
18e113
18
2(1
11o)
(16)
x.
12
||x X. 11.1.
B1t T
B (x. x,) B1.
20y
B1n)
0t
|| 1
2(1
B1)
where the last inequality is due to 31c S 31. We proceed to bound the second term of the inequality above. When & 2, by Young's 's inequality and the definition of BIG, get
B1 1 B10 1x. x1) < 1
81
1g.
112
+
|xx - x. x.1
2(1 B1e)
2a,-1 Bie)
(17)
$ Q4-1
l8:-1
311
||x: - x, 11 Vii
2(1 B1)
20 (1
3ie)
When = 1, this term becomes since E. in Algorithm I Plugging 16 and 17 into 13 we get the following inequality, of which divide the righthand side into three parts and upper bound each them one by one.
T
x. 13, - ||x++1 - x,
R(T)s
|x1
x.112
20x+(1 Bix)
2
P
+
1
Σ
T
04
+
D 0it [iell
+
T
B1
1x1
x.
1,
2(1 - 31)
2(1 -B1)
20 1
B1e)
1=2
1=2
11

---

Published as a conference paper at ICLR 2020
To bound P1, we have
[x] x. |1
||T++1 x,11is
T
Pi 201 32)
X - x.11?)
2ar (1r)
2
1=1
x.
112
Vi
||x: x-l1 1-1
20x(11 - 81c)
201-1 (1 - -1((-11))
[X]
x,
113
T
2
||x,- - X. x.11?
||x, x=11 11
Σ
|xx - x.11²) + +-
201 (1 (1)
2
1 - Bie
201e
20xe11
t=2
T
(f/|x: x.11i. - -+-x)) -x-1 x2122_1 - -Aa(1 - -B1e)l(x1 - -x-113)
1))|x
20x(1 - -11))
1=2
||21 - x.
X |x1 - x.133
+
2a1(1 - B1) 2
(18)
where the inequality is derived from B1(t-1) 2 Bic. For the first term in the last equality of [88 we
have
t f|xx x111. - (t --]][|x: x. x112, sa(1 310)] x.
d
(ot, 2x,1) x) )
(t 1)00-14 - dal1 B21))
(19)
(xr, - x.,1) (turr, - (t (64-1)om 1))1 - Aa(1 - 31x))
-3) - Aa(11 1 BI.)) 00 (Ii, 2..)) (a>(1 31)
where the second equality is because 0z, = 04,5 :. and the second inequality is due to 1 31 s
1 Bic.
For the second term of (8), we have
||x] x,
2 1/
01,5 Aa(1- -1)
|x] x, 113
Σ (11,1 xn,
20 (1 - {1)
20x11 - (11)
U1,5 - da - 31) +
(x1,1 - In,,)²
20 - B1)
1=1
(20)
(#1,6 x2,1)
2a(1 31)
1=1
dD2 8
2a - -1)
where first inequality is due to Condition Combining (18). 19) and (20), we get
and the second inequality follows from Assumption
2
dD2 8 P S 20(1 81)
(21)
To bound Ps. we introduce the following lemma. Lemma 2. The following inequality holds
1
1
log
Σ
R3
+1
(22)
(1 31
C6
j=1
12

---

Published as a conference paper at ICLR 2020
By Lemma we have
T
E ar pel18all
1
P2
a1-1
gt
+
2(1
B1)
2(1 31)
1=2
T
1
04
|
(23)
(1 31)
1 T
9j. +1 +1
aç
log
Σ
31)3
1=1
Finally, we turn to upper bound P3:
T
B1
P3
|x: - xx.1?
1x.1111?
204
(1
- B11)
t=2
d
T
B10
(It, (tt 1 1.5
2a 311)
1=1 t=2
D2
GG
+
31
20
B1
i=1
D2 (G2 +
T v²1
20
B1
i=1
31 D& (G2
+0)
T
00
(t
+++1
20(1 B1)
rg
To further bound Pj, following Bock et al. 2019
we have
P== T-1
v' + v'
TT 1) - TVT +v 1-
+ 1- v/
(v - 112
(24)
T(vT -vT+1)= - -VT
(1-v)²
1
$ (1 (1-v)) v)2
where the inequality follows from nT 2 T+ Thus,
d3, D2 &c (G2 + 8)
P3 S 2a(1 31)(v= 1)2"
(25)
We complete the proof by combining 21
23 and
25
B PROOF OF 2
For the first condition, we have
tü,, - (t 1)U -1,2201-1111 + t(1 (2o)gi, - (t- 1)11-14
st 1 ?) U/-1, + t { 9 (t 1)1
(26)
S(t-7 - - (t - 1))0,-1, + G2
<(2-7)
13

---

Published as a conference paper at ICLR 2020
where the first inequality is derived from the definition of B2c, the second and the third inequalities due to Assumption 1 Based on (26). for any 2 12-2)0% x(1-3,) we have fer. (t-1)mt-11 S A(1 31)
holds for all E [7] and i [d]. For the second condition, we have
[-j
82( k+ (1-
03.3
2t
1 -- k + t-
j=1 k=1
t-k 7 03.
k +
(27)
11
15 93
Σ o3.2
j=1
where the inequality follows from 3 2 1 - and 3, 7 7.
C PROOF OF LEMMA 2
We begin with the following lemma that is central our analysis.
Lemma 3. For all i E [d] and t E [T], we have
T
Ei oi
+1)
S log
(28)
k= L.. + 58
co
Proof. For any 2 b the inequality 1 + S et implies that
(a b) S log b
(29)
Let mg = =ō, and mj = Σ/_ Rh. + ç6 > 0. By
we have
93.4
mÿ M3-1
my
< log
Σ 1= Z. + Ç8
m
m1-1
Summing over 1 to T, we have
T Σ
-3.4
Ei= Çō +1
m log
< log
1= 22. + +58
mg
j=1
Now we turn to the proof of Lemma rule of Algorithm D
2
First, expending the last term in the summation by the update
we get
(1 31) (1-
- - 11 (,0
or 1111611 = or
5 a
(30)
UT
T
i=1
14

---

Published as a conference paper at ICLR 2020
The above equality can be further bounded
Eラ= I BIeT- (+T)2+1))95
arlk
aT
V,,
5a
j=11(1 (1 B25) III / - +
==1
Ilk f1(r-k+1) - l1k- 1 311r
T TEi=1 (1 - (Bas) ) k= -
+ +
Eイ=1 8T [E/=1 II I -
d
(31)
a
T TE (1 -12)) -2(T-
Σ/= 38 gf.
a
(1 B1)
Σド= j= (1 - B25) 11 $2 (-T-+11)0.. -2(( 2 + 5
-3 "T S ac
α
j=1
(1 31)
j=11 83.i + {
B1) j=1
Σ F Ç6
where the first inequality is due 1 Bıy $ 1. the second inequality follows from Cauchy-Schward g., + {6). Using similar
inequality, the third inequality is due to Bi, S 31. Let = arguments for all time steps and summing over to T, we have
d T
Σ cell 12
ac
8 3
1
11
31)
(1 oc
T
Birr
31)
ac
d T
ET 31g3,
(32)
(1 31
k= L +
1=1
oc
T
Gj..
(1 }1) 2
k= L + C8
i=1 1=1
28
af
2 B.
log
1
31) 2
D SADAM WITH A DECAYING REGULARIZATION FACTOR
Algorithm 2 SAdam with vime-variant o, (SAdamD)
1: Input: (3u)T-1, 1T 16
2: Initialize: & 0, Vo Oaxds X1 O.
3: for t I,...,T T do
4: g. = Vx((x))
5: g. Bicke-1 + (1 B1dgg
6: V. 32eVe-1 + (1 - Bze )digg
7: V. V, + diag (2:)
8: X n1 x1 4
V g:
9: end for
In this section, establish generalized version of SAdam, which employs vame-variant regulariza- tion factor d,, for each dimension i, instead of a fixed one for all E [d] and t E [T' as in the original SAdam. The algorithm is referred SAdamD and summarized in Algorithm 2 It can be seen that
15

---

Published as a conference paper at ICLR 2020
SAdamD reduces to SC-RMSprop with time-variant 6, when S1 and - / B2r S For SAdamD, we prove the following theoretical guarantee:
7-
Theorem 4. Suppose Assumptions Caniipptiisaanaaa hhodd and all loss functions fi f(()...... f.(........................))... are A-strongly
convex. Let {==, [0, be non-increasing sequence for all E [dl, Bic = Bir--1 where 31 E 10, 10,1), and (,2z) [0, 1)SH be parameter sequence such that Conditions 3 and
4 are satisfied. Let 2 X. The regret of SAdamD satisfies
C.
B1 B1D (dG2 + +E 81,5
R(T) - 20r(1 - 31) (1
D Σ ii=l 81,1
aç
log Σ i=1
Σ 93s +1
3133
Ç
20(1 B1)(U - 1)2
(33)
By setting 31 = 0 and - S 82c S 1 - 7. we can derive the following regret bound for SC-RMSprop:
hold, and all loss functions fi(:) ((())...,fr)) are X- strongly convex. Let {5e,i E (0, I be non non-increasing sequence for all i [d], and -
Corollary 5. Suppose Assumptions 7 and 2
$2: 11 7, where y E (0, 1}. Let a (2-
Then SAdamD reduces to SC-RMSprop, and the
regret satisfies
R(T) < 2a
D2 >d
δ1,4
a
log
T Σ 23
+1
(34)
j=1
Finally, we provide an instantiation of 8 and derive the following Corollary.
Corollary 6. Suppose Assumptions 7 and hold, and all loss functions .T).......(() are X- strongly convex. Let δi,i 1+t,
8z "3. where &2 (0, and &1 are hypeparameters. Then
we have de E (0, 1] and is non-increasing Vi E [d], [T]. Let 1 - S B2c 1 where y E (0, 1}, and a 62-7)62, Then SAdamD reduces to SC-RMSprop, and the regret satisfies
dD3 E2
1
R(T)
log 7 Σ
T3 + E2
log
Σ 9
+
(35)
2a
E2
E2
i=1
j=1
E PROOF OF THEOREM 4
By similar arguments as the proof of Theorem
we can upper bound regret as
T
Xx
13
|
R(T)s
2 |x.
x.11?
20
B1x)
Pi
ΣT
04
|
p-11
T
B1t
+
Xx
x.
2(1
B1)
2(1 -B1)
20
(1
Bie)
2
2=
Pb
To bound Pt, based on 18 have
T
1
P
(4|[x, x. 113 - (1 1)](x, - x.133 - -Aa(1 - Bie))(xx 8, - -x.13)
2a(1
B10)
(36)
||x|
-x.1
xx x.112)
+
201(1
-Bi)
2
16

---

Published as a conference paper at ICLR 2020
For the first term in (3), we have
111)]/x--xx,, -x.1 t x x, x.1 - (t (t-1) -
-Aa(1 - - -B10) |x - x.12
d
(1t,) - ),,,)((02,, (1- 11)-)11-11 - Aa(11 - B1r))
(11,e )x,1)((102, (1- (0-1)01-1,- da(1 - BIe) + 81,5 61-1,1)
(37)
(ft, Jz, )=,,)((an)) ()a(1 B1) Aa Bie) + وي, 6ي-1,8)
50
<0
For the second term of (36). we have
|x] x,112;
(1,1 Aa((1 -B1)
|xx x.
Σ 111 zx,i)
201 -81)
2a(1 - 32)
U1,4 da - (31) + 81,
Σ [1, - xz,i)²
(38)
2a(1 - -1)
1=1
D2 Σ Dim1 81.5
2n - (1)
where the inequality follows from Condition
Combining
36
37 and 38
we have
D Σ 1== ò1,1
Pi S 20 81)
(39)
To bound Pz. we first introduce the following lemma. Lemma 4. The following inequality holds
T
T
au g 12,
S (1 B1)
ac
log
1
Σ
og +1
(40)
j=1
The proof of Lemma can be found in Appendix F
Based Lemma 4 have
T
Σ Et=1 Or 11 V--
1
P2 = 2(1 - B1)
a1
g
2 V-1
2(1 -11)
1=2
T
1
< (1 31)
(41)
t=1
d
T Σ
ac
1
log
23
+1
B1
3
{dT,
1=1
1=1
17

---

Published as a conference paper at ICLR 2020
Finally, we turn to upper bound P3:
B1
Ps <
(2
xx,,) tt0,s
2a(1 B1))
D
d
T
t(G² +
2a
-
B1
1=1
D 00
V 1-1
ΣΣ
t(G + t..))
20
B1
1=
(42)
31
(G2 + 61,))
T-1
Σ (t++)
20
1- B1
D1 d
(G2 + 01,))
201
(1 - (1) - 1)2
31 D2 (dG2
Σ ii=1 51,;)
2a(1 - 31) - 1)²
We finish the proof by combining 39
41 and 42
F PROOF OF LEMMA 4
Expending the last term in the summation by using the update rule of Algorithm we have
d
(I -1,) IT BI x+11913
or 1 2 = ar
97,
(43)
a
TI B1 - + +8T,
VT
The above equality can be further bounded as
1= IHE B B1(T-k+1)
== IT's Bier Puer-k+1)03.
or11r1
<a
TE (1 Bz5 k= B2(T k+ 1193, + 8r.
1=1
T Σ
8 ( T 1 B1(T-
5
(2,) 1= 32 ++1) -
ST
1=1
Σ 8T 95.5
(44)
31)
j=1 (1 - B2) 11 1 1 + 8T
ビj=1 34 - 999
9
ac
11
31)
j=1 23. +ōŌT,
T
ac
d
T
07.4
B1)
Emm + ÇōT.
=
The first inequality follows from Cauchy-Schware inequality and 1 Br. S 1, and the second 93
inequality is due to BI. Br. Let
Eim of, *8,, By using similar arguments as in 32).
18

---

Published as a conference paper at ICLR 2020
have
oç
93.5
at Bt v,
(1 - 31)
Σ k==11 g + Cde,
o
3
(1 31)
Σ Rk.i + CŌr;
T ΣΣΣ
(1 11)
= t= j=1
(45)
ac
d T
0= 8ig93
(1 - 31)
Rhs + Cdr,
1=1 j=1
aç
(1 31)²
Σ
g + CŌr
i=1 j=1
d
T
aC
log
Fj.t +
)1
ÇōT,
i=1
j=1
G ON THE CONVERGENCE OF AMSGRAD
In this section, we firstly provide the AMSgrad algorithm and its theoretical guarantees (Reddi et al.) 2018), then state a theoretical flaw in their analysis revealed by Tran et al. 2019), and finally propose a simple solution fix this problem.
The AMSgrad algorithm developed in Reddi et al. (2018) is summarized in Algorithm
Algorithm 3 AMSgrad
1: Input: (81))=1,3
2: Initialize:
0, Vo = -Oaxd,X; X1 0.
3: for 1...., T do
4: g. V[((x.))
5: g. B1r81-1 + (1 - 31e)g.
6: Vi 32V-11 + (2)diag(g..)
7: VA max Vi, V/-13
8: N m Vi
X₁ ar V. 1/2
where at VT
9: end for
For AMSgrad, Reddi et al. (2018) provide the following regret bound.
Theorem 7 (Thcorem 4 in Reddi et al. (0018), problematic). Suppose Assumptions 7 and 2 hold, and
all loss functions fi().... fr(.) are convex. Ler 8 > 0, B1 > 0, Bi S B1, and 7 < 1. The regret of AMSgrad satisfies
D2 VT
d
D2
T
1/2
R(T) <
1/2 U
a
31)
2(1 B1)
i=1
tm t=1
(46)
av 1 + log T
+
1191:1;11-
(1 (1- 7) /(1 B2)
19

---

Published as a conference paper at ICLR 2020
Recently, Tran et al. 2019) point out mistake in the proof of Theorem 7 Specifically, in Reddi et al. (2018). the following inequality is utilized (Proof of Lemma 2, Page 18):
T
1111/((x (xx)))1
(X++1 - (xee/
xx,)11
20.(1 -11))
1=1
B1c
11/1/4(xx (x5e -x.11p] + - 31) 7) V (1 - 32)
αv + log T
+ 2ar (1 -B1r)
1
|12/1/1(x (x1 -x.)112 +
1V, (x1 x.)
11 1-1 (x+ x.)
2a (1 - 31)
2(1 - -3))
a1
ac-1
T
B1c 11////1(xx - xx)1 + (1- (1)
av log'
d
+
1191:11ll
2ar(1 - 31)
(v (2)
1=1
(47)
which, however, may not hold. To see this, we note that essentially 447 uses
T
Σ
| (x+
-x)]2 11Ve (x++1 - xx)]1²]
20
-
31e)
[=1
(48)
T
1
|12 x.)11 11V: (x++1 - -x.)13]
5 31)
20
1=1
which holds only if 31 S 31 and | | (x, - 12 (x+1 -x)]l is non-negative. However, as empirically shown by Tran et al. (2019), the letter requirement can be violated some counterexamples. Note that similar problems exist in many recent proposed Adam variants. To address this issue, Tran et al. 2019) establish a new convergence proof of AMSGrad, which indicates an O(d data- uata-independent regret bound. Moreover, as an alternative, they also propose a variant of AMSgrad, called AdamX, which alters the stricture of AMSgrad to force the inequality been satisfied. For AdamX, they also give new theoretical analysis and Odd/T) data iuta-inndepndent regret bound.
In this paper, find out that the above problem can be solved by simply configuring B1v of AMSgrad in a non-increasing manner, i.e., Vt. 2 2, Bi & (1(e-1)- Specifically, when BI is non-increasing, we can rewrite (47) as
Σ
1 20 B1o)
|11.1/1(x, (x, -x,1= x111
(x1+1 -11111 (IV21/((x411 -
x3)1
31c
av a/I+1o log T
T |1ghT,ll
11,21/4xx (x: - -x.)11
+
+
200, (1 - 311)
(1 (1- 3:) - 7) v(1 (2) 1=1
T
|1V11/40 (x; - x.)
|| (x, x. )12
11x1/4(x1 - -xx)11++
Σ
201 (1 B1)
2 t=2
as B1x)
0/ 0/-1 (1 B1(1-1))
d
+
B1c
|1,.1/4 (xx -xx)11
Rv 1 + T
Σ
11
2ar -B1)
(1- (1- (V[ (22 1=1
1=1
T
||0:1/1 (xx - x1)11
11 (x: x.) x.)
112/1/4(x
(x1 xx,)12++ +
Σ
2a
81)
2
a1 - B1x)
at a- 11 Bic)
+
Σ
T
31t
|1V:1/((xe - -x.)
a 1
Σ llo.r
d
2ay(1
- (11)
(1 - 311 (1- (v)(-))(v---) B2)
t=1
20

---

Published as a conference paper at ICLR 2020
1/144 (xt x.)1
I1 (xt x.)]?
2//4 (x1 - -x.)1l
201 (1 31)
2(1 - 31)
0t-1
1=
B1t
av + log T
+
|IV:/'4xx (x:
-x:- xx,11
+ (1 81) (v[ 52)
11g.T.lll
21 31)
==1
where the second incquality is derived from Bic S (i(--1). and the last inequality is due to the fact | (x:-x.]1
non-negative. In this way, the proof of ( x1)""
that B1 I 31 and
0--1 AMSgrad can proceed, and the algorithm structure as well as the conclusion in Theorem remain unchanged.
D2
To summarize, we restate Theorem 7 as follows.
Theorem (Fixed theoretical guarantee AMSgrad). Suppose Assumptions) 7 and 2 hold, and all loss functions fi(-)...., f-) are convex. Let á > 0. $1 0, B1 Bi(t-1) where t 2. B11 B1. and 7
81 < 1. The regret of AMSgrad satisfies
v02
V&
D&
VT
D2
T
BieU 1/2
R(T) -
1/2 T
+
00
a(1 31) i=1
2(1 31)
01
t=1
i=1
(49)
av + log T
1191:1
(1 - 31-
7) /(1 (2)
H EXPERIMENTS ON RESNET18
2.0
SAdam
0.8
SC Adagrad
1.5
RMSprppppppppp
Test Accuracy
OGD
0.6
Adam
Loss
AdamNC
1.0
Amsgrad
0.4
SAdam
SC Adagrad
SC, RM.prMprrppp
0.5
0.2
Adam
AdamNC
Amsgrad
0.0
0.0
20
40
60
80
100
20
40
60
80
100
Epoch
Epoch
(a) Training Loss v.s. number of epochs
(b) Testing accuracy v.s. number of epochs
Fig. 4: experimental results of ResNet18 CIFAR10 dataset
In this section, we conduct the image classification task on CIFAR10 dataset using ResNet18 (He) al.) 2016). The parameter configuration of algorithms is the same that in Section We repeat each experiment 10 times and take their average. The training loss v.s. epoch is shown in Fig. 44a and the testing accuracy v.s. epoch shown in Fig. 4b As can be seen, proposed SAdam outperforms other algorithms.
21


Reviews:
[{"review_id": "Syg4z4lAFr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies Adam and proves that under strong convexity assumption, it obtains the improved regret bound $O(log(T))$. The regret bound is data-dependent, thus as a side-effect it also improves previous known result for strongly convex RMSProp (SC-RMSProp).\n\nThe paper is clear and well-written and I also think that theoretical results are correct and new. However, I have some concerns on the possible impacts of the results especially in the context of ICLR:\n\n- First of all, the assumption to show improved regret is strong convexity of all functions $f_t$. However, this is very restrictive and much stronger than the assumption that the sum of functions is strongly convex. In addition, from what I see, in the proof of Theorem 1, the authors use strong convexity with the $x^\\star$, so they can maybe replace global strong convexity to strong convexity restricted to the path towards the solution. A reference where these restricted strong convexity type assumptions are studied:\n\nNecoara, Nesterov, Glineur, “Linear convergence of first order methods for non-strongly convex optimization”, Math. Prog. 2019.\n\n- To show improved regret, consistent with previous work SC-Adagrad and SC-RMSProp, the authors modify the algorithm to use $V_t^{-1}$ in page 3 in the step size, instead of $V_t^{-1/2}$ of regular Adam. It is easy to see that this is to make sure step size has a faster decrease, which is needed also to show standard SGD gets $1/k$ rate for strongly convex problems. However, given that one might not now if the problem has strong convexity (there might exist cases where this property only exists locally), it is not clear if one should apply Adam or SAdam. \n\n- Another remark related to the previous one is the following. Standard SGD uses step size $\\alpha_0/\\sqrt{k}$ for convex optimization without strong convexity and $\\alpha_0/k$ for strongly convex optimization. If one uses $alpha_0/k $for convex optimization without strong convexity, one gets a very bad rate $1/log(k)$ and very bad practical performance. So, given SAdam gives step sizes suited for strongly convex optimization (similar to SGD for strongly convex optimization), I would expect SAdam's step sizes to be not very suitable when there is no strong convexity.\n\n- An additional point is that the step size of SAdam depends on the global strong convexity parameter $\\lambda$ which further restricts the applicability of the method. For the theoretical results to hold, the step size should be set according to $\\lambda$, and when the step size is not selected that way, one loses the fast convergence rate.\n\n- In the experiments, the authors show the performance of SAdam for neural network training and related to my previous remarks, I have the following concerns. First of all, how do the authors pick step sizes now since it depends on strong convexity constant as in eq. (7). In addition, given that neural networks are certainly non-strongly convex, I would expect that the fast decreasing step size caused by using $V_t^{-1}$ might also hurt the performance considerably, which happens as I discussed above even for convex but non-strongly convex losses. I would suspect that much worse effects can be seen for non-convex optimization. Of course, the authors can argue that if the loss landscape of neural network has some local strong convexity parameters, SAdam would adapt and get faster convergence. But unfortunately, I would not agree with such a statement, because the analysis is not made to adapt to local strong convexity and a dependence to strong convexity constant is present due to eq. (7), so if one does not know the constant, the theoretical guarantees would not apply. In addition, the provided experiments for neural network training is not extensive enough to convince practitioners to use SAdam instead of Adam which has been used for years.\n\nOverall, I think that it is interesting to see that a variant of Adam can be shown to obtain improved regret under strong convexity, I find the assumptions strong and the impact for neural network training, therefore for ICLR, quite questionable.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJxbm19sKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In the setting of online convex optimization, this paper investigates the question of whether adaptive gradient methods can achieve “data dependent” logarithmic regret bounds when the class of loss functions is strongly convex. To this end, the authors propose a variant of Adam - called SAdam - which indeed satisfies such a desired bound. Importantly, SAdam is an extension of SC-RMSprop (a variant of RMSprop) for which a “data independent” logarithmic bound was found. Experiments on optimizing strongly convex functions and training deep networks show that SAdam outperforms other adaptive gradient methods (and SGD).  \n\nThe paper is very well-written, well-motivated and well-positioned with respect to related work. The regret analysis of SAdam is conceptually simple and elegant. The experimental protocol is well-detailed, and the results look promising. In a nutshell, this is an excellent piece of work.\n\nI have just a minor comment. In the experiments, SAdam was tested using $\\beta_1 = 0.9$ and $\\beta_{2t} = 1 - \\frac{0.9}{t}$. Since Corollary 2 covers a wide range of admissible values for these parameters, it would be interesting to report (for example in Appendix) a sensitivity analysis of SAdam, using different choices of $\\beta_1$ and $\\beta_{2t}$. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HJgSWr8htH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose a variant of Adam, named as SAdam, and establish a data-dependent O(log T) regret bound. The key idea is using a faster decaying yet under controlled step size to exploit strong convexity. Some experiments are carried out to demonstrate the effectiveness of the proposed algorithm. The idea seems interesting, the writing is well-written, and the analysis seems correct (I did not fully check all steps, but the key steps seems ok to me). \n\nProbs:\n1. The proposed SAdam is an effective variant of Adam designed for strongly convex functions. The algorithm is a natural extension of Adam, and SC-RMSprop could be regarded as a special case.\n2. The authors establish a data-dependent O(log T) regret bound for SAdam, and as a byproduct, they present the first data-dependent logarithmic regret for SC-RMSprop. The authors also fix a small bug in the analysis of AMSgrad. The theoretical result is the key technical contribution of this paper.\n3. The experimental results shows that Aadam can be used to minimize strongly convex functions, as well as neural networks, which is believed to be non-convex.\n\nCons:\n1. As the authors mentioned in Remark 2, the main limitation of their analysis is that the role of the first-order momentum is unclear. Although the first-order momentum can accelerate the convergence in practice, proving this in theory remains an open problem. Is there some contribution on this aspect? \n\n2. The 4-layer CNN in Section 4.2 is a bit small. It would be better if the authors test their algorithm on larger and more popular neural networks.\n\nIn summary, this paper contributes the theoretical studies of ADAM-type algorithm, although the algorithm is somehow incremental. To me, a bit surprising result is that the step size originally designed for strongly convex functions also works well for training CNN.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers all appreciated the results. They expressed doubts regarding the discrepancy between the assumptions made and the reality of the loss of deep networks.

I share these concerns with the reviewers but also believe that, due to the popularity of Adam, a careful analysis of a variant is worthy of publication.
Decision: Accept (Poster)