summaries: 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).   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). 
abstractText: O( √ 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.
authors.name: Guanghui Wang
authors.name: Shiyin Lu
authors.name: Quan Cheng
authors.name: Wei-Wei Tu
authors.name: Lijun Zhang
references.authors: Parnia Bahar Tamer Alkhouli Jan-Thorsten Peter Christopher Jan-Steffen Brix Hermann Ney
references.title: Empirical investigation of optimization algorithms in neural machine translation
references.venue: The Prague Bulletin of Mathematical Linguistics,
references.authors: Amitabh Basu Soham De Anirbit Mukherjee Enayat Ullah
references.title: Convergence guarantees for rmsprop and adam in non-convex optimization and their comparison to nesterov acceleration on autoencoders
references.venue: arXiv preprint arXiv:1807.06766,
references.authors: Sebastian Bock Josef Goppold Martin Wei
references.title: An improvement of the convergence proof of the adam-optimizer
references.venue: arXiv preprint arXiv:1804.10587,
references.authors: Xiangyi Chen Sijia Liu Ruoyu Sun Mingyi Hong
references.title: On the convergence of a class of adam-type algorithms for non-convex optimization
references.venue: In Proceedings of the 7th International Conference on Learning Representations,
references.authors: Zaiyi Chen Yi Xu Enhong Chen Tianbao Yang
references.title: Sadagrad: Strongly adaptive stochastic gradient methods
references.venue: In Proceedings of 35th International Conference on Machine Learning,
references.authors: Michael Denkowski Graham Neubig
references.title: Stronger baselines for trustable results in neural machine translation
references.venue: In Proceedings of the 1st Workshop on Neural Machine Translation,
references.authors: Timothy Dozat
references.title: Incorporating nesterov momentum into adam
references.venue: In Proceedings of 4th International Conference on Learning Representations, Workshop Track,
references.authors: John Duchi Elad Hazan Yoram Singer
references.title: Adaptive subgradient methods for online learning and stochastic optimization
references.venue: Journal of Machine Learning Research,
references.authors: Karol Gregor Ivo Danihelka Alex Graves Danilo Jimenez Rezende Daan Wierstra
references.title: Draw: a recurrent neural network for image generation
references.venue: In Proceedings of the 32nd International Conference on Machine Learning,
references.authors: Elad Hazan Satyen Kale
references.title: Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization
references.venue: Journal of Machine Learning Research,
references.authors: Elad Hazan Amit Agarwal Satyen Kale
references.title: Logarithmic regret algorithms for online convex optimization
references.venue: Machine Learning,
references.authors: Kaiming He Xiangyu Zhang Shaoqing Ren Jian Sun
references.title: Deep residual learning for image recognition
references.venue: In Proceedings of the 29th IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Sham M Kakade Ambuj Tewari
references.title: On the generalization ability of online strongly convex programming algorithms
references.venue: In Advances in Neural Information Processing Systems
references.authors: Diederik P Kingma Jimmy Ba
references.title: Adam: A method for stochastic optimization
references.venue: In Proceedings of 3rd International Conference on Learning Representations,
references.authors: Ryan Kiros Yukun Zhu Ruslan R Salakhutdinov Richard Zemel Raquel Urtasun Antonio Torralba Sanja Fidler
references.title: Skip-thought vectors
references.venue: In Advances in Neural Information Processing Systems
references.authors: Alex Krizhevsky
references.title: Learning multiple layers of features from tiny images
references.venue: Technical report, Citeseer,
references.authors: Yann LeCun
references.title: The mnist database of handwritten digits. http://yann
references.venue: lecun. com/exdb/mnist/,
references.authors: H Brendan McMahan Matthew Streeter
references.title: Adaptive bound optimization for online convex optimization
references.venue: In Proceedings of the 23rd Annual Conference on Learning Theory, pp
references.authors: Mahesh Chandra Mukkamala Matthias Hein
references.title: Variants of rmsprop and adagrad with logarithmic regret bounds
references.venue: In Proceedings of the 33rd International Conference on Machine Learning,
references.authors: Sashank J Reddi Satyen Kale Sanjiv Kumar
references.title: On the convergence of adam and beyond
references.venue: In Proceedings of 6th International Conference on Learning Representations,
references.authors: Noam Shazeer Mitchell Stern
references.title: Adafactor: Adaptive learning rates with sublinear memory cost
references.venue: In Proceedings of the 35th International Conference on Machine Learning,
references.authors: Tijmen Tieleman Geoffrey Hinton
references.title: Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine
references.authors: Phuong Thi Tran
references.title: On the convergence proof of amsgrad and a new version
references.venue: IEEE Access,
references.authors: Kelvin Xu Jimmy Ba Ryan Kiros Kyunghyun Cho Aaron Courville Ruslan Salakhudinov Rich Zemel Yoshua Bengio
references.title: Show, attend and tell: Neural image caption generation with visual attention
references.venue: In Proceedings of 32nd International Conference on Machine Learning,
references.authors: Matthew D Zeiler
references.title: Adadelta: an adaptive learning rate method
references.venue: arXiv preprint arXiv:1212.5701,
references.authors: Jiawei Zhang Limeng Cui Fisher B
references.title: Gouza. Gadam: Genetic-evolutionary adam for deep neural network optimization
references.venue: arXiv preprint arXiv:1805.07500,
references.authors: Martin Zinkevich
references.title: Online convex programming and generalized infinitesimal gradient ascent
references.venue: In Proceedings of the 20th International Conference on Machine Learning,
references.title: α/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 A ∈ Rd×d be a positive definite matrix and D ⊆ R
references.authors: AMSgrad Reddi
references.title: 2018) provide the following regret bound
references.venue: Reddi et al
references.authors: Recently Tran
references.title: 2019) point out a mistake in the proof of Theorem 7. Specifically, in Reddi et al. (2018), the following inequality is utilized
references.venue: (Proof of Lemma
references.authors: Tran
references.title: 2019), the letter requirement can be violated in some counterexamples. Note that similar problems exist in many recent proposed Adam variants
references.venue: To address this issue, Tran et al
sections.text: 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 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.
sections.heading: 1 INTRODUCTION
sections.text: Online Convex Optimization (OCO) is a well-established learning framework which has both theoretical and practical appeals (Shalev-Shwartz et al., 2012). It is performed in a sequence of consecutive rounds: In each round t, firstly a learner chooses a decision xt from a convex set D ⊆ Rd, at the same time, an adversary reveals a loss function ft(·) : D 7→ R, and consequently the learner suffers a loss ft(xt). The goal is to 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):
  R(T ) := T∑ t=1 ft(xt)−min x∈D T∑ t=1 ft(x).
  The most classic algorithm for OCO is Online Gradient Descent (OGD) (Zinkevich, 2003), which attains an O( √ T ) regret. OGD iteratively performs descent step towards gradient direction with a predetermined step size, which is oblivious to the characteristics of the data being observed. As a result, its regret bound is data-independent, 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 & Ba, 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., 2015; Gregor et al., 2015; Kiros et al., 2015; Denkowski & Neubig, 2017; Bahar 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( √ T ) in the worst case and become tighter when gradients are sparse 1.
  ∗Lijun Zhang is the corresponding author. 1We note that, as very recently pointed out by Tran et al. (2019), there still exists a minor theoretical flaw in the analysis of Reddi et al. (2018), and such issue in fact appears in many of recent variants of AMSgrad/AdamNC. In this paper, we provide a simple way to fix this problem. The details can be found in Appendix G.
  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 as well as other regularized learning problems, and it is wellknown that the vanilla OGD with an appropriately chosen step size enjoys a much better O(log T ) regret bound for strongly convex functions (Hazan et al., 2007). In this paper, we 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 data-dependent 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 a 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 an 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, we 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 `2-norm and ‖ · ‖∞ the infinite norm. For a positive definite matrix H ∈ Rd×d, the weighted `2-norm is defined by ‖x‖2H = x>Hx. The H-weighted projection ΠHD (x) of x onto D is defined by ΠHD (x) = arg miny∈D ‖y− x‖2H . We use gt to denote the gradient of ft(·) at xt. For vector sequence {vt}Tt=1, we denote the i-th element of vt by vt,i. For diagonal matrix sequence {Mt}Tt=1, we use mt,i to denote the i-th element in the diagonal of Mt. We use g1:t,i = [g1,i, · · · , gt,i] to denote the vector obtained by concatenating the i-th element of the gradient sequence {gt}Tt=1.
sections.heading: 2 RELATED WORK
sections.text: In this section, we briefly review related work in online convex and strongly convex optimization.
  In the literature, most studies are devoted to 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 O(1/ √ t) (referred to as convex OGD) achieves a data-independent O(d √ T ) regret (Zinkevich, 2003), where d is the dimension. To conduct more informative updates, Duchi et al. (2011) introduce Adagrad algorithm, which adjusts the step size of OGD in a perdimension basis according to the geometry of the past gradients. In particular, the diagonal version of the algorithm updates decisions as
  xt+1 = xt − α√ t Vt −1/2gt (1)
  where α > 0 is a constant factor, Vt is a d× d diagonal matrix, and ∀i ∈ [d], vt,i = ( ∑t j=1 g 2 j,i)/t is the arithmetic average of the square of the i-th elements of the past gradients. Intuitively, while the step size of Adagrad, i.e., (α/ √ t)V −1/2 t , decreases generally on the order of O(1/ √ t) as that in convex OGD, the additional matrix V −1/2t will automatically increase step sizes for sparse dimensions in order to seize the infrequent yet valuable information therein. For convex functions, Adagrad enjoys an O( ∑d i=1 ‖g1:T,i‖) regret, which is O(d √ T ) in the worst case and becomes tighter when gradients are sparse.
  Although Adagrad works well in sparse cases, its performance has been found to 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.e.,
  Vt = βVt−1 + (1− β)diag(gtg>t )
  where β ∈ [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
  essentially limited to recent few gradients. Since the invention of RMSprop, many EMA variants of Adagrad have been developed (Zeiler, 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̂t = β1ĝt−1 + (1− β1)gt (2) Vt = β2Vt−1 + (1− β2)diag(gtg>t ) (3) xt+1 = xt − α√ t Vt −1/2ĝt (4)
  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̂t = max { V̂t−1, Vt } xt+1 = xt −
  α√ t V̂ −1/2 t ĝt
  where an additional element-wise maximization procedure is employed before the update of xt to ensure a stable step size. The other is AdamNC, where the framework of Adam remains unchanged, yet a time-variant β2 (i.e., β2t) is adopted to keep the step size under control. Theoretically, the two algorithms achieve data-dependentO( √ T ∑d i=1 vT,i+ ∑d i=1 ‖g1:T,i‖ log T ) andO( √ T ∑d i=1 vT,i+∑d
  i=1 ‖g1:T,i‖) regrets respectively. In the worst case, they suffer O(d √ T log T ) and O(d √ T )
  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 O(d √ T ) 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 dataindependent O(d log T ) regret (Hazan et al., 2007). Inspired by this, Mukkamala & Hein (2017) modify the update rule of Adagrad in (1) as follows
  xt+1 = xt − α t Vt −1gt
  so that the step size decays approximately on the order of O(1/t), which is similar to that in strongly convex OGD. The new algorithm, named SC-Adagrad, is proved to enjoy a data-dependent regret bound of O( ∑d i=1 log(‖g1:T,i‖2)), which is O(d log T ) in the worst case. They further extend this 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 in 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 et al., 2018; Shazeer & Stern, 2018). However, to our knowledge, none of these algorithms are particularly designed for strongly convex functions, nor enjoy a logarithmic regret bound.
sections.heading: 3 SADAM
sections.text: In this section, we first describe the proposed algorithm, then state its theoretical guarantees, and finally compare it with the SC-RMSprop algorithm.
sections.heading: 3.1 THE ALGORITHM
sections.text: Before proceeding to our algorithm, following previous studies, we introduce some standard definitions (Boyd & Vandenberghe, 2004) and assumptions (Reddi et al., 2018). Definition 1. A function f(·) : D 7→ R is λ-strongly convex if ∀x1, x2 ∈ D,
  f(x1) ≥ f(x2) +∇f(x2)>(x1 − x2) + λ
  2 ‖x1 − x2‖2. (5)
  Algorithm 1 SAdam
  1: Input: {β1t}Tt=1, {β2t}Tt=1, δ 2: Initialize: ĝ0 = 0, V̂0 = 0d×d, x1 = 0. 3: for t = 1, . . . , T do 4: gt = ∇ft(xt) 5: ĝt = β1tĝt−1 + (1− β1t)gt 6: Vt = β2tVt−1 + (1− β2t)diag(gtg>t ) 7: V̂t = Vt + δ t Id
  8: xt+1 = ΠV̂tD ( xt − αt V̂ −1 t ĝt ) 9: end for
  Assumption 1. The infinite norm of the gradients of all loss functions are bounded by G∞, i.e., their exists a constant G∞ > 0 such that maxx∈D ‖∇ft(x)‖∞ ≤ G∞ holds for all t ∈ [T ]. Assumption 2. The decision set D is bounded. Specifically, their exists a constant D∞ > 0 such that maxx1,x2∈D ‖x1 − x2‖∞ ≤ D∞.
  We are now ready to present our algorithm, which follows the general framework of Adam and is summarized in Algorithm 1. In each round t, we firstly observe the gradient at xt (Step 4), then compute the first-order momentum ĝt (Step 5). Here β1t a time-variant hyperparameter. Next, we calculate the second-order momentum Vt by EMA of the square of past gradients (Step 6). This procedure is controlled by β2t, whose value will be discussed later. After that, we add a vanishing factor δt to the diagonal of Vt and get V̂t (Step 7), which is a standard technique for avoiding too large steps caused by small gradients in the beginning iterations. Finally, we update the decision by ĝt and V̂t, 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 xt in Step 8, and the other is the configuration of β2t in Step 6. Intuitively, both modifications stem from strongly convex OGD, and jointly result in a faster decaying yet under controlled step size which helps utilize the strong convexity while preserving the practical benefits of Adam. Specifically, in the first modification, we remove the square root operation in (4) of Adam, and update xt at Step 8 as follows
  xt+1 = xt − α
  t V̂ −1t ĝt. (6)
  In this way, the step size used to update the i-th element of xt is αt v̂ −1 t,i , which decays in general on the order of O(1/t), and can still be automatically tuned in a per-feature basis via the EMA of the historical gradients.
  The second modification is made to β2t, which determines the value of Vt and thus also controls the decaying rate of the step size. To help understand the motivation behind our algorithm, we first revisit Adam, where β2t 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 β2t should satisfy the following two conditions: Condition 1. ∀t ∈ [T ] and i ∈ [d],
  √ tv
  1/2 t,i α − √ t− 1v1/2t−1,i α ≥ 0.
  Condition 2. For some ζ > 0 and ∀t ∈ [T ], i ∈ [d],√√√√t t∑ j=1 Πt−jk=1β2(t−k+1)(1− β2j)g2j,i ≥ 1 ζ √√√√ t∑ j=1 g2j,i.
  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 α√
  t , where
  α > 0 is a constant factor), in which √ t
  α − √ t− 1 α ≥ 0,∀t ∈ [T ]
  is a key condition used in the analysis. We first modify Condition 1 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 αt with α ≥ 1 λ for λ-strongly convex functions. Under this configuration, we have
  t α − t− 1 α ≤ λ,∀t ∈ [T ]. (7)
  Motivated by this, we propose the following condition for our SAdam, which is an analog to (7).
  Condition 3. Their exists a constant C > 0 such that for any α ≥ Cλ , we have ∀t ∈ [T ] and i ∈ [d],
  tvt,i α − (t− 1)vt−1,i α ≤ λ(1− β1). (8)
  Note that the extra (1 − β1) 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/ √ t in Adam, we modify Condition 2 accordingly as follows:
  Condition 4. For some ζ > 0, ∀t ∈ [T ] and i ∈ [d],
  t t∑ j=1 t−j∏ k=1 β2(t−k+1)(1− β2j)g2j,i ≥ 1 ζ t∑ j=1 g2j,i. (9)
sections.heading: 3.2 THEORETICAL GUARANTEES
sections.text: In the following, we give a general regret bound when the two conditions are satisfied.
  Theorem 1. Suppose Assumptions 1 and 2 hold, and all loss functions f1(·), . . . , fT (·) are λstrongly convex. Let δ > 0, β1t = β1νt−1, where β1 ∈ [0, 1), ν ∈ [0, 1), and {β2t}Tt=1 ∈ [0, 1]T be a parameter sequence such that Conditions 3 and 4 are satisfied. Let α ≥ Cλ . The regret of SAdam satisfies
  R(T ) ≤ dD 2 ∞δ
  2α(1− β1) +
  dβ1D 2 ∞(G 2 ∞ + δ)
  2α(1− β1)(ν − 1)2 +
  αζ (1− β1)3 d∑ i=1 log  1 ζδ T∑ j=1 g2j,i + 1  . (10) Remark 1. The above theorem implies that our algorithm enjoys an O( ∑d i=1 log(‖g1:T,i‖2)) regret bound, which is O(d log T ) in the worst case, and automatically becomes tighter whenever the gradients are small or sparse such that ‖g1:T,i‖2 G2∞T for some i ∈ [d]. The superiority of data-dependent bounds have been witnessed by a long list of literature, such as Duchi et al. (2011); Mukkamala & Hein (2017); Reddi et al. (2018). In the following, we give some concrete examples:
  • Consider a one-dimensional sparse setting where non-zero gradient appears with probability c/T and c > 1 is a constant. Then E [ log (∑T
  t=1 g 2 t,1
  )] = O(log(c)), which is a constant
  factor.
  • Consider a high-dimensional sparse setting where in each dimension of gradient non-zero element appears with probability p = T (m−d)/d with m ∈ [1, d) being a constant. Then, E [∑d i=1 log (∑T j=1 g 2 j,i )] = O(m log T ), which is much tighter than O(d log T ).
  Remark 2. In practice, first-order momentum is a 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 to rigorously analyse the influence of the first-order momentum parameter β1 as it affects all the gradients appearing in the last term of the regret of Theorem 1. 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 a similar structure as our regret bound with respect to β1.
  Next, we provide an instantiation of {β2t}Tt=1 such that Conditions 3 and 4 hold, and derive the following Corollary. Corollary 2. Suppose Assumptions 1 and 2 hold, and all loss functions f1(·), . . . , fT (·) are λstrongly convex. Let δ > 0, β1t = β1νt−1 where ν, β1 ∈ [0, 1), and 1 − 1t ≤ β2t ≤ 1 − γ t , where γ ∈ (0, 1]. Then we have: 1. For any α ≥ (2−γ)G 2 ∞
  λ(1−β1) , ∀t ∈ [T ] and i ∈ [d],
  tvt,i α − (t− 1)vt−1,i α ≤ λ(1− β1).
  2. For all t ∈ [T ] and j ∈ [d],
  t t∑ j=1 t−j∏ k=1 β2(t−k+1)(1− β2j)g2j,i ≥ γ t∑ j=1 g2j,i.
  Moreover, let α ≥ (2−γ)G 2 ∞
  λ(1−β1) , and the regret of SAdam satisfies:
  R(T ) ≤ dD 2 ∞δ
  2α(1− β1) +
  dβ1D 2 ∞(G 2 ∞ + δ)
  2α(1− β1)(ν − 1)2 +
  α γ(1− β1)3 d∑ i=1 log γ δ T∑ j=1 g2j,i + 1  . Furthermore, as a special case, by setting β1t = 0 and 1 − 1t ≤ β2t ≤ 1 − γ t , our algorithm reduces to SC-RMSprop (Mukkamala & Hein, 2017), which is a variant of RMSprop for strongly convex functions. Although 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:
  R(T ) ≤δdD 2 ∞
  2α +
  α
  2γ d∑ i=1 log ( TvT,i δ + 1 ) + α γ d∑ i=1 (1− γ)(1 + log T ) infj∈[1,T ] jvj,i + δ . (11)
  Focusing on the denominator of the last term in (11), we have
  inf j∈[1,T ]
  jvj,i + δ ≤ 1v1,i + δ ≤ G∞ + δ
  thus α
  γ d∑ i=1 (1− γ)(1 + log T ) infj∈[1,T ] jvj,i + δ ≥ dα γ (1− γ)(log T + 1) G∞ + δ
  which implies that their regret bound is of order O(d log T ), and thus data-independent. In contrast, based on Corollary 2, we present a new regret bound for SC-RMSprop in the following, which is O( ∑d i=1 log(‖g1:T,i‖2)), and thus data-dependent.
  Corollary 3. Suppose Assumptions 1 and 2 hold, and all loss functions f1(·), . . . , fT (·) are λstrongly convex. Let δ > 0, β1t = 0, and 1− 1t ≤ β2t ≤ 1− γ t , where γ ∈ (0, 1]. Let α ≥ (2−γ)G2∞ λ . Then SAdam reduces to SC-RMSprop, and its regret satisfies
  R(T ) ≤dD 2 ∞δ 2α + α γ d∑ i=1 log γ δ T∑ j=1 g2j,i + 1  . (12) Finally, we note that Mukkamala & Hein (2017) also consider a more general version of SC-RMSprop which uses a time-variant non-increasing δ for each dimension i. In Appendix D we introduce the δ-variant technique to our SAdam, and provide the corresponding theoretical guarantee.
sections.heading: 4 EXPERIMENTS
sections.text: In this section, we present empirical results on optimizing strongly convex functions and training deep networks. More results can be found Appendix.
  Algorithms. In both experiments, we compare the following algorithms:
  • SC-Adagrad (Mukkamala & Hein, 2017), with step size αt = α/t. • SC-RMSprop (Mukkamala & Hein, 2017), with step size αt = α/t and βt = 1− 0.9t . • Adam (Kingma & Ba, 2015) and AMSgrad (Reddi et al., 2018), both with β1 = 0.9, β2 = 0.999, αt = α/ √ t for convex problems and time-invariant αt = α for non-convex
  problems. • AdamNC (Reddi et al., 2018), with β1 = 0.9, β2t = 1− 1/t, and αt = α/ √ t for convex
  problems and a time-invariant αt = α for non-convex problems. • Online Gradient Descent (OGD), with step size αt = α/t for strongly convex problems and
  a time-invariant αt = α for non-convex problems. • Our proposed SAdam, with β1 = 0.9, β2t = 1− 0.9t .
  For Adam, AdamNC and AMSgrad, we choose δ = 10−8 according to the recommendations in their papers. For SC-Adagrad and SC-RMSprop, following Mukkamala & Hein (2017), we choose a time-variant δt,i = ξ2e−ξ1tvt,i for each dimension i, with ξ1 = 0.1, ξ2 = 1 for convex problems and ξ1 = 0.1, ξ2 = 0.1 for non-convex problems. For our 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 a rather large δ = 10−2 to avoid this problem. To conduct a fair comparison, for each algorithm, we choose α from the set {0.1, 0.01, 0.001, 0.0001} and report the best results. Datasets. In both experiments, we examine the performances of the aforementioned algorithms on three widely used datasets: MNIST (60000 training samples, 10000 test samples), CIFAR10 (50000 training samples, 10000 test samples), and CIFAR100 (50000 training samples, 10000 test samples). We refer to LeCun (1998) and Krizhevsky (2009) for more details of the three datasets.
sections.heading: 4.1 OPTIMIZING STRONGLY CONVEX FUNCTIONS
sections.text: In the first experiment, we consider the problem of mini-batch `2-regularized softmax regression, which belongs to the online strongly convex optimization framework. Let K be the number of classes and m be the batch size. In each round t, firstly a mini-batch of training samples {(xm, ym)}mi=1 arrives, where yi ∈ [K],∀i ∈ [m]. Then, the algorithm predicts parameter vectors {wi, bi}Ki=1, and suffers a loss which takes the following form:
  J(w, b) =− 1 m m∑ i=1 log
  ( ew > yi
  xi+byi∑K j=1 e w>j xi+bj
  ) + λ1
  K∑ k=1 ‖wk‖2 + λ2 K∑ k=1 b2k.
  The value of λ1 and λ2 are set to be 10−2 for all experiments. The regret (in log scale) v.s. dataset proportion is shown in Fig. 1. It can be seen that our SAdam outperforms other methods across all the considered datasets. Besides, we observe that data-dependent strongly convex methods such as SC-Adagrad, 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.
sections.heading: 4.2 TRAINING DEEP NETWORKS
sections.text: Following Mukkamala & Hein (2017), we also conduct experiments on a 4-layer CNN, which consists of two convolutional layers (each with 32 filters of size 3 × 3), one max-pooling layer (with a 2 × 2 window and 0.25 dropout), and one fully connected layer (with 128 hidden units and 0.5 dropout). We employ ReLU 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. 2, 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.
sections.heading: 5 CONCLUSION AND FUTURE WORK
sections.text: 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 a data-dependent O(d log T ) regret bound for strongly convex functions, which means that it converges much faster than Adam, AdamNC, and AMSgrad in such cases, and can enjoy a huge gain in the face of sparse gradients. In addition, we also provide the first data-dependent logarithmic regret bound for SCRMSprop. 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 O(d log T ) regret for online strongly convex optimization, it can be easily translated into a data-dependent O(d log T/T ) convergence rate for stochastic strongly convex optimization (SSCO) by using the online-to-batch conversion (Kakade & Tewari, 2009). However, this rate is not optimal for SSCO, and it is sill an open problem how to achieve a datadependent O(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 a future work.
sections.heading: 6 ACKNOWLEDGEMENT
sections.text: This work was partially supported by NSFC (61976112), NSFC-NRF Joint Research Project (61861146001), and the Collaborative Innovation Center of Novel Software Technology and Industrialization.
sections.heading: A PROOF OF THEOREM 1
sections.text: From Definition 1, we can upper bound regret as
  R(T ) = T∑ t=1 ft(xt)− T∑ t=1 ft(x∗) (5) ≤ T∑ t=1 g>t (xt − x∗)− λ 2 ‖xt − x∗‖2 (13)
  where x∗ := minx∈D ∑T t=1 ft(x) is the best decision in hindsight. On the other hand, by the update rule of xt+1 in Algorithm 1, we have
  ‖xt+1 − x∗‖2V̂t = ∥∥∥ΠV̂tD (xt − αtV̂ −1t ĝt)− x∗∥∥∥2
  V̂t
  ≤‖xt − αtV̂ −1t ĝt − x∗‖2V̂t =− 2αtĝ>t (xt − x∗) + ‖xt − x∗‖2V̂t + α 2 t ||ĝt||2V̂ −1t
  =− 2αt ( β1tĝt−1 + (1− β1t)gt )> (xt − x∗)
  + ‖xt − x∗‖2V̂t + α 2 t ||ĝt||2V̂ −1t
  (14)
  where αt := α/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 A ∈ Rd×d be a positive definite matrix and D ⊆ Rd be a convex set. Then we have, ∀x, y ∈ Rd,
  ‖ΠAD(x)−ΠAD(y)‖A ≤ ‖x− y‖A. (15)
  Rearranging (14), we have
  g>t (xt − x∗) ≤ ‖xt − x∗‖2V̂t − ‖xt+1 − x∗‖ 2 V̂t
  2αt(1− β1t) + β1t 1− β1t ĝ>t−1(x∗ − xt)
  + αt
  2(1− β1t) ‖ĝt‖2V̂ −1t
  ≤ ‖xt − x∗‖2V̂t − ‖xt+1 − x∗‖ 2 V̂t
  2αt(1− β1t) + β1t 1− β1t ĝ>t−1(x∗ − xt)
  + αt
  2(1− β1) ‖ĝt‖2V̂ −1t
  (16)
  where the last inequality is due to β1t ≤ β1. We proceed to bound the second term of the inequality above. When t ≥ 2, by Young’s inequality and the definition of β1t, we get
  β1t 1− β1t ĝ>t−1(x∗ − xt) ≤ αt−1β1t 2(1− β1t) ‖ĝt−1‖2V̂ −1t−1 + β1t 2αt−1(1− β1t) ‖xt − x∗‖2V̂t−1
  ≤ αt−1 2(1− β1) ‖ĝt−1‖2V̂ −1t−1 + β1t 2αt−1(1− β1t) ‖xt − x∗‖2V̂t−1 .
  (17)
  When t = 1, this term becomes 0 since ĝ0 = 0 in Algorithm 1. Plugging (16) and (17) into (13), we get the following inequality, of which we divide the righthand side into three parts and upper bound each of them one by one. R(T )≤ T∑ t=1 ( ‖xt − x∗‖2V̂t − ‖xt+1 − x∗‖ 2 V̂t 2αt(1− β1t) − λ 2 ‖xt − x∗‖2 ) ︸ ︷︷ ︸
  P1
  + 1
  2(1− β1) T∑ t=2 αt−1‖ĝt−1‖2V̂ −1t−1 + ∑T t=1 αt‖ĝt‖2V̂ −1t 2(1− β1)︸ ︷︷ ︸
  P2
  + T∑ t=2 β1t 2αt−1(1− β1t)
  ‖xt − x∗‖2V̂t−1︸ ︷︷ ︸ P3 .
  To bound P1, we have
  P1 = ‖x1 − x∗‖2V̂1 2α1(1− β1) − ‖xT+1 − x∗‖2VT 2αT (1− β1T )︸ ︷︷ ︸
  ≤0
  − T∑ t=1 ( λ 2 ‖xt − x∗‖2 )
  + T∑ t=2 ( ‖xt − x∗‖2V̂t 2αt(1− β1t) − ‖xt − x∗‖2V̂t−1 2αt−1(1− β1(t−1)) )
  ≤ ‖x1 − x∗‖2V̂1 2α1(1− β1) − T∑ t=1 ( λ 2 ‖xt − x∗‖2 ) + T∑ t=2
  1
  1− β1t
  ( ‖xt − x∗‖2V̂t
  2αt − ‖xt − x∗‖2V̂t−1 2αt−1
  )
  = T∑ t=2
  1 2α(1− β1t) ( t‖xt − x∗‖2V̂t − (t− 1)‖xt − x∗‖ 2 V̂t−1 − λα(1− β1t)‖xt − x∗‖2 ) + ( ‖x1 − x∗‖2V̂1 2α1(1− β1) − λ 2 ‖x1 − x∗‖2
  ) (18)
  where the inequality is derived from β1(t−1) ≥ β1t. For the first term in the last equality of (18), we have
  t‖xt − x∗‖2V̂t − (t− 1)‖xt − x∗‖ 2 V̂t−1 − λα(1− β1t)‖xt − x∗‖2
  = d∑ i=1 (xt,i − x∗,i)2(tv̂t,i − (t− 1)v̂t−1,i − λα(1− β1t))
  = d∑ i=1 (xt,i − x∗,i)2(tvt,i − (t− 1)vt−1,i − λα(1− β1t))
  (8) ≤ d∑ i=1 (xt,i − x∗,i)2(αλ(1− β1)− λα(1− β1t)) ≤ 0
  (19)
  where the second equality is because v̂t,i = vt,i + δt , and the second inequality is due to 1− β1 ≤ 1− β1t. For the second term of (18), we have(
  ‖x1 − x∗‖2V̂1 2α1(1− β1) − λ 2 ‖x1 − x∗‖2
  ) =
  d∑ i=1 (x1,i − x∗,i)2 ( v̂1,i − λα(1− β1) 2α(1− β1) )
  = d∑ i=1 (x1,i − x∗,i)2 ( v1,i − λα(1− β1) + δ 2α(1− β1) )
  ≤ d∑ i=1 (x1,i − x∗,i)2 (
  δ
  2α(1− β1) ) ≤ dD 2 ∞δ
  2α(1− β1)
  (20)
  where first inequality is due to Condition 3, and the second inequality follows from Assumption 2. Combining (18), (19) and (20), we get
  P1 ≤ dD2∞δ
  2α(1− β1) . (21)
  To bound P2, we introduce the following lemma. Lemma 2. The following inequality holds
  T∑ t=1 αt‖ĝt‖2V̂ −1t ≤ αζ (1− β1)2 d∑ i=1 log  1 ζδ T∑ j=1 g2j,i + 1  . (22)
  By Lemma 2, we have
  P2 = 1
  2(1− β1) T∑ t=2 αt−1‖ĝt−1‖2V̂ −1t−1 + ∑T t=1 αt‖ĝt‖2V̂ −1t 2(1− β1)
  ≤ 1 (1− β1) T∑ t=1 αt‖ĝt‖2V̂ −1t
  (22) ≤ αζ (1− β1)3 d∑ i=1 log  1 ζδ T∑ j=1 g2j,i + 1  . (23)
  Finally, we turn to upper bound P3:
  P3 = T∑ t=2 β1t 2αt−1(1− β1t) ‖xt − x∗‖2V̂t−1
  = d∑ i=1 T∑ t=2 β1t 2α(1− β1t) (xt,i − x∗,i)2(t− 1)v̂t−1,i
  ≤D 2 ∞(G 2 ∞ + δ)
  2α
  d∑ i=1 T∑ t=1 β1t 1− β1t t
  ≤β1D 2 ∞(G 2 ∞ + δ)
  2α
  d∑ i=1 T∑ t=1 νt−1 1− β1 t
  = β1D
  2 ∞(G 2 ∞ + δ)
  2α(1− β1) d∑ i=1 T−1∑ t=0
  νt(t+ 1)︸ ︷︷ ︸ P ′3 .
  To further bound P ′3, following Bock et al. (2019), we have
  P ′3 = T−1∑ t=0 νtt+ νt
  =
  ( (T − 1)νT+1 − TνT + ν
  (ν − 1)2 +
  1− νT
  1− ν ) =
  1− T (νT − νT+1)− νT (1− ν)2
  ≤ 1 (1− ν)2
  (24)
  where the inequality follows from νT ≥ νT+1. Thus,
  P3 ≤ dβ1D
  2 ∞(G 2 ∞ + δ)
  2α(1− β1)(ν − 1)2 . (25)
  We complete the proof by combining (21), (23) and (25).
sections.heading: B PROOF OF COROLLARY 2
sections.text: For the first condition, we have
  tvt,i − (t− 1)vt−1,i =tβ2tvt−1,i + t(1− β2t)g2t,i − (t− 1)vt−1,i ≤t (
  1− γ t
  ) vt−1,i + t 1
  t g2t,i − (t− 1)vt−1,i
  ≤(t− γ − (t− 1))vt−1,i +G2∞ ≤(2− γ)G2∞
  (26)
  where the first inequality is derived from the definition of β2t, the second and the third inequalities are due to Assumption 1. Based on (26), for any α ≥ (2−γ)G 2 ∞
  λ(1−β1) , we have tvt,i α − (t−1)vt−1,i α ≤ λ(1− β1)
  holds for all t ∈ [T ] and i ∈ [d]. For the second condition, we have
  t t∑ j=1 t−j∏ k=1 β2(t−k+1) (1− β2j) g2j,i ≥t t∑ j=1 t−j∏ k=1 ( 1− 1 t− k + 1 ) γ j g2j,i
  =t t∑ j=1 t−j∏ k=1 t− k t− k + 1 γ j g2j,i
  =t t∑ j=1 j t γ j g2j,i
  =γ t∑ j=1 g2j,i
  (27)
  where the inequality follows from βt ≥ 1− 1t and 1− βt ≥ γ t .
sections.heading: C PROOF OF LEMMA 2
sections.text: We begin with the following lemma that is central to our analysis.
  Lemma 3. For all i ∈ [d] and t ∈ [T ], we have
  T∑ j=1 g2j,i∑j k=1 g 2 k,i + ζδ ≤ log
  (∑T j=1 g 2 j,i
  ζδ + 1
  ) . (28)
  Proof. For any a ≥ b > 0, the inequality 1 + x ≤ ex implies that
  1 a (a− b) ≤ log a b . (29)
  Let m0 = ζδ, and mj = ∑j k=1 g 2 k,i + ζδ > 0. By (29), we have
  g2j,i∑j k=1 g 2 k,i + ζδ = mj −mj−1 mj ≤ log mj mj−1 .
  Summing over 1 to T , we have
  T∑ j=1 g2j,i∑j k=1 g 2 k,i + ζδ ≤ log mt m0 = log
  (∑T j=1 g 2 j,i
  ζδ + 1
  ) .
  Now we turn to the proof of Lemma 2. First, expending the last term in the summation by the update rule of Algorithm 1, we get
  αT ‖ĝT ‖2V̂ −1T = αT d∑ i=1 ĝ2T,i vT,i + δ T = α d∑ i=1
  (∑T j=1(1− β1j) ∏T−j k=1 β1(T−k+1)gj,i )2 T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δ . (30)
  The above equality can be further bounded as
  αT ‖ĝT ‖2V̂ −1T ≤α d∑ i=1
  (∑T j=1 ∏T−j k=1 β1(T−k+1)gj,i )2 T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δ
  ≤α d∑ i=1
  (∑T j=1 ∏T−j k=1 β1(T−k+1) )(∑T j=1 ∏T−j k=1 β1(T−k+1)g 2 j,i ) T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δ
  ≤α d∑ i=1
  (∑T j=1 β T−j 1 )(∑T j=1 ∏T−j k=1 β1(T−k+1)g 2 j,i ) T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δ
  ≤ α (1− β1) d∑ i=1
  ∑T j=1 β T−j 1 g 2 j,i
  T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δ
  (9) ≤ αζ
  (1− β1) d∑ i=1
  ∑T j=1 β T−j 1 g
  2 j,i∑T
  j=1 g 2 j,i + ζδ
  ≤ αζ (1− β1) d∑ i=1 T∑ j=1 βT−j1 g2j,i∑j k=1 g 2 k,i + ζδ
  (31)
  where the first inequality is due to 1− β1j ≤ 1, the second inequality follows from Cauchy-Schwarz inequality, the third inequality is due to β1t ≤ β1. Let rj = g2j,i/( ∑j k=1 g 2 k,i + ζδ). Using similar arguments for all time steps and summing over 1 to T , we have T∑ t=1 αt‖ĝt‖2V̂ −1t ≤ αζ (1− β1) d∑ i=1 T∑ t=1 t∑ j=1 βt−j1 rj
  = αζ
  (1− β1) d∑ i=1 T∑ j=1 T−j∑ l=0 βl1rj
  = αζ
  (1− β1) d∑ i=1 T∑ j=1
  ∑T−j l=0 β l 1g
  2 j,i∑j
  k=1 g 2 k,i + ζδ
  ≤ αζ (1− β1)2 d∑ i=1 T∑ j=1 g2j,i∑j k=1 g 2 k,i + ζδ
  (28) ≤ αζ (1− β1)2 d∑ i=1 log
  (∑T j=1 g 2 j,i
  ζδ + 1
  ) .
  (32)
sections.heading: D SADAM WITH A DECAYING REGULARIZATION FACTOR
sections.text: Algorithm 2 SAdam with time-variant δt (SAdamD)
  1: Input: {β1t}Tt=1, {β2t}Tt=1, {δt}Tt=1 2: Initialize: ĝ0 = 0, V̂0 = 0d×d, x1 = 0. 3: for t = 1, . . . , T do 4: gt = ∇ft(xt) 5: ĝt = β1tĝt−1 + (1− β1t)gt 6: Vt = β2tVt−1 + (1− β2t)diag(gtg>t ) 7: V̂t = Vt + diag ( δt t
  ) 8: xt+1 = ΠV̂tD ( xt − αt V̂ −1 t ĝt
  ) 9: end for
  In this section, we establish a generalized version of SAdam, which employs a time-variant regularization factor δt,i for each dimension i, instead of a fixed one for all i ∈ [d] and t ∈ [T ] as in the original SAdam. The algorithm is referred to as SAdamD and summarized in Algorithm 2. It can be seen that
  our SAdamD reduces to SC-RMSprop with time-variant δt when β1t = 0 and 1− 1t ≤ β2t ≤ 1− γ t . For SAdamD, we prove the following theoretical guarantee:
  Theorem 4. Suppose Assumptions 1 and 2 hold, and all loss functions f1(·), . . . , fT (·) are λ-strongly convex. Let {δt,i}Tt=1 ∈ (0, 1]T be a non-increasing sequence for all i ∈ [d], β1t = β1νt−1 where β1 ∈ [0, 1), ν ∈ [0, 1), and {β2t}Tt=1 ∈ [0, 1]T be a parameter sequence such that Conditions 3 and 4 are satisfied. Let α ≥ Cλ . The regret of SAdamD satisfies
  R(T ) ≤ D2∞
  ∑d i=1 δ1,i
  2α(1− β1) +
  αζ (1− β1)3 d∑ i=1 log  1 ζδT,i T∑ j=1 g2j,i + 1 + β1D2∞ ( dG2∞ + ∑d i=1 δ1,i ) 2α(1− β1)(ν − 1)2 .
  (33)
  By setting β1t = 0 and 1 − 1t ≤ β2t ≤ 1 − γ t , we can derive the following regret bound for SC-RMSprop:
  Corollary 5. Suppose Assumptions 1 and 2 hold, and all loss functions f1(·), . . . , fT (·) are λstrongly convex. Let {δt,i}Tt=1 ∈ (0, 1]T be a non-increasing sequence for all i ∈ [d], and 1− 1t ≤ β2t ≤ 1− γt , where γ ∈ (0, 1]. Let α ≥ (2−γ)G2∞ λ . Then SAdamD reduces to SC-RMSprop, and the regret satisfies
  R(T ) ≤ D2∞
  ∑d i=1 δ1,i
  2α + α γ d∑ i=1 log  γ δT,i T∑ j=1 g2j,i + 1  . (34) Finally, we provide an instantiation of δt and derive the following Corollary.
  Corollary 6. Suppose Assumptions 1 and 2 hold, and all loss functions f1(·), . . . , fT (·) are λstrongly convex. Let δt,i = ξ21+ξ1 ∑t j=1 g 2 j,i
  , where ξ2 ∈ (0, 1] and ξ1 ≥ 0 are hypeparameters. Then we have δt,i ∈ (0, 1] and is non-increasing ∀i ∈ [d], t ∈ [T ]. Let 1 − 1t ≤ β2t ≤ 1 − γ t , where γ ∈ (0, 1], and α ≥ (2−γ)G 2 ∞
  λ . Then SAdamD reduces to SC-RMSprop, and the regret satisfies
  R(T ) ≤dD 2 ∞ξ2 2α + α γ d∑ i=1 log γ T∑ j=1 g2j,i + ξ2 + α γ d∑ i=1 log ξ1 ξ2 T∑ j=1 g2j,i + 1 ξ2  . (35)
sections.heading: E PROOF OF THEOREM 4
sections.text: By similar arguments as in the proof of Theorem 1, we can upper bound regret as R(T )≤ T∑ t=1 ( ‖xt − x∗‖2V̂t − ‖xt+1 − x∗‖ 2 V̂t 2αt(1− β1t) − λ 2 ‖xt − x∗‖2 ) ︸ ︷︷ ︸
  P1
  + 1
  2(1− β1) T∑ t=2 αt−1‖ĝt−1‖2V̂ −1t−1 + ∑T t=1 αt‖ĝt‖2V̂ −1t 2(1− β1)︸ ︷︷ ︸
  P2
  + T∑ t=2 β1t 2αt−1(1− β1t)
  ‖xt − x∗‖2V̂t−1︸ ︷︷ ︸ P3 .
  To bound P1, based on (18), we have
  P1 ≤ T∑ t=2
  1 2α(1− β1t) ( t‖xt − x∗‖2V̂t − (t− 1)‖xt − x∗‖ 2 V̂t−1 − λα(1− β1t)‖xt − x∗‖2 ) + ( ‖x1 − x∗‖2V̂1 2α1(1− β1) − λ 2 ‖x1 − x∗‖2 ) . (36)
  For the first term in (36), we have
  t‖xt − x∗‖2V̂t − (t− 1)‖xt − x∗‖ 2 V̂t−1 − λα(1− β1t)‖xt − x∗‖2
  = d∑ i=1 (xt,i − x∗,i)2(tv̂t,i − (t− 1)v̂t−1,i − λα(1− β1t))
  = d∑ i=1 (xt,i − x∗,i)2(tvt,i − (t− 1)vt−1,i − λα(1− β1t) + δt,i − δt−1,i)
  ≤ d∑ i=1 (xt,i − x∗,i)2(λα(1− β1)− λα(1− β1t)︸ ︷︷ ︸ ≤0 + δt,i − δt−1,i︸ ︷︷ ︸ ≤0 )
  ≤0
  (37)
  For the second term of (36), we have
  ( ‖x1 − x∗‖2V̂1 2α1(1− β1) − λ 2 ‖x1 − x∗‖2 ) = d∑ i=1 (x1,i − x∗,i)2 ( v̂1,i − λα(1− β1) 2α(1− β1) )
  = d∑ i=1 (x1,i − x∗,i)2 ( v1,i − λα(1− β1) + δ1,i 2α(1− β1) )
  ≤ D2∞
  ∑d i=1 δ1,i
  2α(1− β1)
  (38)
  where the inequality follows from Condition 3. Combining (36), (37) and (38), we have
  P1 ≤ D2∞
  ∑d i=1 δ1,i
  2α(1− β1) . (39)
  To bound P2, we first introduce the following lemma.
  Lemma 4. The following inequality holds
  T∑ t=1 αt‖ĝt‖2V̂ −1t ≤ αζ (1− β1)2 d∑ i=1 log  1 ζδT,i T∑ j=1 g2j,i + 1  . (40)
  The proof of Lemma 4 can be found in Appendix F. Based on Lemma 4, we have
  P2 = 1
  2(1− β1) T∑ t=2 αt−1‖ĝt−1‖2V̂ −1t−1 + ∑T t=1 αt‖ĝt‖2V̂ −1t 2(1− β1)
  ≤ 1 (1− β1) T∑ t=1 αt‖ĝt‖2V̂ −1t
  (40) ≤ αζ (1− β1)3 d∑ i=1 log  1 ζδT,i T∑ j=1 g2j,i + 1  . (41)
  Finally, we turn to upper bound P3:
  P3 ≤ d∑ i=1 T∑ t=1 β1t 2α(1− β1t) (xt,i − x∗,i)2tv̂t,i
  ≤ D 2 ∞
  2α d∑ i=1 T∑ t=1 β1t 1− β1t t(G2∞ + δ1,i)
  ≤ β1D 2 ∞
  2α d∑ i=1 T∑ t=1 νt−1 1− β1 t(G2∞ + δ1,i)
  = β1D
  2 ∞
  2α d∑ i=1 (G2∞ + δ1,i) 1− β1 T−1∑ t=0 νt(t+ 1)
  (24) ≤ β1D 2 ∞
  2α d∑ i=1 (G2∞ + δ1,i) (1− β1)(ν − 1)2
  = β1D
  2 ∞(dG 2 ∞ + ∑d i=1 δ1,i)
  2α(1− β1)(ν − 1)2 .
  (42)
  We finish the proof by combining (39), (41) and (42).
sections.heading: F PROOF OF LEMMA 4
sections.text: Expending the last term in the summation by using the update rule of Algorithm 2, we have
  αT ‖ĝT ‖2V̂ −1T =αT d∑ i=1
  ĝ2T,i
  vT,i + δT,i T
  = α d∑ i=1
  (∑T j=1(1− β1j) ∏T−j k=1 β1(T−k+1)gj,i )2 T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δT,i . (43)
  The above equality can be further bounded as
  αT ‖ĝT ‖2V̂ −1T ≤α d∑ i=1
  (∑T j=1 ∏T−j k=1 β1(T−k+1) )(∑T j=1 ∏T−j k=1 β1(T−k+1)g 2 j,i ) T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δT,i
  ≤α d∑ i=1
  (∑T j=1 β T−j 1 )(∑T j=1 ∏T−j k=1 β1(T−k+1)g 2 j,i ) T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δT,i
  ≤ α (1− β1) d∑ i=1
  ∑T j=1 β T−j 1 g 2 j,i
  T ∑T j=1(1− β2j)Π T−j k=1 β2(T−k+1)g 2 j,i + δT,i
  (9) ≤ αζ
  (1− β1) d∑ i=1
  ∑T j=1 β T−j 1 g
  2 j,i∑T
  j=1 g 2 j,i + ζδT,i
  ≤ αζ (1− β1) d∑ i=1 T∑ j=1 βT−j1 g2j,i∑j k=1 g 2 k,i + ζδT,i .
  (44)
  The first inequality follows from Cauchy-Schwarz inequality and 1 − β1t ≤ 1, and the second inequality is due to β1t ≤ β1. Let rj =
  g2j,i∑j k=1 g 2 k,i+ζδT,i . By using similar arguments as in (32), we
  have
  T∑ t=1 αt‖ĝt‖2V̂ −1t ≤ αζ (1− β1) d∑ i=1 T∑ t=1 t∑ j=1 βT−j1 g2j,i∑j k=1 g 2 k,i + ζδt,i
  ≤ αζ (1− β1) d∑ i=1 T∑ t=1 t∑ j=1 βT−j1 g2j,i∑j k=1 g 2 k,i + ζδT,i
  = αζ
  (1− β1) d∑ i=1 T∑ t=1 t∑ j=1 rj
  ≤ αζ (1− β1) d∑ i=1 T∑ j=1
  ∑T−j l=0 β l 1g
  2 j,i∑j
  k=1 g 2 k,i + ζδT,i
  ≤ αζ (1− β1)2 d∑ i=1 T∑ j=1 g2j,i∑j k=1 g 2 k,i + ζδT,i
  (28) ≤ αζ (1− β1)2 d∑ i=1 log  1 ζδT,i T∑ j=1 g2j,i + 1  .
  (45)
sections.heading: G ON THE CONVERGENCE OF AMSGRAD
sections.text: 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 to fix this problem.
  The AMSgrad algorithm developed in Reddi et al. (2018) is summarized in Algorithm 3.
  Algorithm 3 AMSgrad
  1: Input: {β1t}Tt=1, β2 2: Initialize: ĝ0 = 0, V̂0 = 0d×d, x1 = 0. 3: for t = 1, . . . , T do 4: gt = ∇ft(xt) 5: ĝt = β1tĝt−1 + (1− β1t)gt 6: Vt = β2Vt−1 + (1− β2)diag(gtg>t ) 7: V̂t = max{Vt, V̂t−1}
  8: xt+1 = Π √ V̂t
  D ( xt − αtV̂ −1/2t ĝt ) , where αt = α√t
  9: end for
  For AMSgrad, Reddi et al. (2018) provide the following regret bound.
  Theorem 7 (Theorem 4 in Reddi et al. (2018), problematic). Suppose Assumptions 1 and 2 hold, and all loss functions f1(·), . . . , fT (·) are convex. Let δ > 0, β1 > 0, β1t ≤ β1, and γ = β1√β2 ≤ 1. The regret of AMSgrad satisfies
  R(T ) ≤ D 2 ∞ √ T
  α(1− β1) d∑ i=1 v̂ 1/2 T,i + D2∞ 2(1− β1) T∑ t=1 d∑ i=1 β1tv̂ 1/2 t,i αt + α √ 1 + log T
  (1− β1)2(1− γ) √ (1− β2) d∑ i=1 ‖g1:T,i‖.
  (46)
  Recently, Tran et al. (2019) point out a 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∑ t=1 [ 1 2αt(1− β1t) [ ‖V̂ 1/4t (xt − x∗)‖2 − ‖V̂ 1/4 t (xt+1 − x∗)‖2 ] +
  β1t 2αt(1− β1t)
  ‖V̂ 1/4t (xt − x∗)‖2 ] + α √ 1 + log T
  (1− β1)2(1− γ) √ (1− β2) d∑ i=1 ‖g1:T,i‖
  ≤ 1 2α1(1− β1) ‖V̂ 1/4t (x1 − x∗)‖2 + 1 2(1− β1) T∑ t=2
  [ ‖V̂ 1/4t (xt − x∗)‖2
  αt − ‖V̂ 1/4t−1 (xt − x∗)‖2 αt−1
  ]
  + T∑ t=1 [ β1t 2αt(1− β1) ‖V̂ 1/4t (xt − x∗)‖2 ] +
  α √ 1 + log T
  (1− β1)2(1− γ)( √ 1− β2) d∑ i=1 ‖g1:T,i‖
  (47)
  which, however, may not hold. To see this, we note that essentially (47) uses
  T∑ t=1
  1
  2αt(1− β1t)
  [ ‖V̂ 1/4t (xt − x∗)‖2 − ‖V̂ 1/4 t (xt+1 − x∗)‖2 ] ≤ 1
  (1− β1) T∑ t=1 1 2αt [ ‖V̂ 1/4t (xt − x∗)‖2 − ‖V̂ 1/4 t (xt+1 − x∗)‖2 ] (48)
  which holds only if β1t ≤ β1 and ‖V̂ 1/4t (xt − x∗)‖2 − ‖V̂ 1/4 t (xt+1 − x∗)‖2 is non-negative. However, as empirically shown by Tran et al. (2019), the letter requirement can be violated in 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 √ T ) data-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 a new theoretical analysis and an O(d √ T ) data-independent regret bound.
  In this paper, we find out that the above problem can be solved by simply configuring β1t of AMSgrad in a non-increasing manner, i.e., ∀t ≥ 2, β1t ≤ β1(t−1). Specifically, when β1t is non-increasing, we can rewrite (47) as
  T∑ t=1 [ 1 2αt(1− β1t) [ ‖V̂ 1/4t (xt − x∗)‖2 − ‖V̂ 1/4 t (xt+1 − x∗)‖2 ] +
  β1t 2αt(1− β1t)
  ‖V̂ 1/4t (xt − x∗)‖2 ] + α √ 1 + log T
  (1− β1)2(1− γ) √ (1− β2) T∑ i=1 ‖g1:T,i‖
  ≤ 1 2α1(1− β1) ‖V̂ 1/41 (x1 − x∗)‖2 + 1 2 T∑ t=2
  [ ‖V̂ 1/4t (xt − x∗)‖2
  αt(1− β1t) − ‖V̂ 1/4t−1 (xt − x∗)‖2 αt−1(1− β1(t−1))
  ]
  + T∑ t=1 [ β1t 2αt(1− β1) ‖V̂ 1/4t (xt − x∗)‖2 ] +
  α √ 1 + log T
  (1− β1)2(1− γ)( √ 1− β2) d∑ i=1 ‖g1:T,i‖
  ≤ 1 2α1(1− β1) ‖V̂ 1/41 (x1 − x∗)‖2 + 1 2 T∑ t=2
  [ ‖V̂ 1/4t (xt − x∗)‖2
  αt(1− β1t) − ‖V̂ 1/4t−1 (xt − x∗)‖2 αt−1(1− β1t)
  ]
  + T∑ t=1 [ β1t 2αt(1− β1) ‖V̂ 1/4t (xt − x∗)‖2 ] +
  α √ 1 + log T
  (1− β1)2(1− γ)( √ 1− β2) d∑ i=1 ‖g1:T,i‖
  ≤ 1 2α1(1− β1) ‖V̂ 1/41 (x1 − x∗)‖2 + 1 2(1− β1) T∑ t=2
  [ ‖V̂ 1/4t (xt − x∗)‖2
  αt − ‖V̂ 1/4t−1 (xt − x∗)‖2 αt−1
  ]
  + T∑ t=1 [ β1t 2αt(1− β1) ‖V̂ 1/4t (xt − x∗)‖2 ] +
  α √ 1 + log T
  (1− β1)2(1− γ)( √ 1− β2) d∑ i=1 ‖g1:T,i‖
  where the second inequality is derived from β1t ≤ β1(t−1), and the last inequality is due to the fact that β1t ≤ β1 and [ ‖V̂ 1/4t (xt−x∗)‖ 2 αt − ‖V̂ 1/4 t−1 (xt−x∗)‖ 2 αt−1 ] is non-negative. In this way, the proof of
  AMSgrad can proceed, and the algorithm structure as well as the conclusion in Theorem 7 remain unchanged.
  To summarize, we restate Theorem 7 as follows. Theorem 8 (Fixed theoretical guarantee of AMSgrad). Suppose Assumptions 1 and 2 hold, and all loss functions f1(·), . . . , fT (·) are convex. Let δ > 0, β1 > 0, β1t ≤ β1(t−1) where t ≥ 2, β11 = β1, and γ = β1√
  β2 ≤ 1. The regret of AMSgrad satisfies
  R(T ) ≤ D 2 ∞ √ T
  α(1− β1) d∑ i=1 v̂ 1/2 T,i + D2∞ 2(1− β1) T∑ t=1 d∑ i=1 β1tv̂ 1/2 t,i αt + α √ 1 + log T
  (1− β1)2(1− γ) √ (1− β2) d∑ i=1 ‖g1:T,i‖.
  (49)
sections.heading: H EXPERIMENTS ON RESNET18
sections.text: In this section, we conduct the image classification task on CIFAR10 dataset using ResNet18 (He et al., 2016). The parameter configuration of algorithms is the same as that in Section 4. We repeat each experiment 10 times and take their average. The training loss v.s. epoch is shown in Fig. 4a, and the testing accuracy v.s. epoch is shown in Fig. 4b. As can be seen, our proposed SAdam outperforms other algorithms.
title: STRONGLY CONVEX FUNCTIONS