On the Marginal Regret Bound Minimization of Adaptive Methods
Authors: Wenjie Li
Guang Cheng
Venue:  (2021)
Keywords: Optimization Algorithm
Adaptive algorithms
Online Learning
Regret Minimization

Abstract: Numerous adaptive algorithms such as AMSGrad and Radam have been proposed and applied to deep learning recently. However, these modifications do not improve the convergence rate of adaptive algorithms and whether a better algorithm exists still remains an open question. In this work, we propose a new motivation for designing the proximal function of adaptive algorithms, named as marginal regret bound minimization. Based on such an idea, we propose a new class of adaptive algorithms that not only achieves marginal optimality but can also potentially converge much faster than any existing adaptive algorithms in the long term. We show the superiority of the new class of adaptive algorithms both theoretically and empirically using experiments in deep learning. 

Under review as a conference paper at ICLR 2021
ON THE MARGINAL REGRET BOUND MINIMIZATION OF ADAPTIVE METHODS
Anonymous authors Paper under double-blind review
ABSTRACT
Numerous adaptive algorithms such as AMSGrad and Radam have been proposed and applied to deep learning recently. However, these modifications do not improve the convergence rate of adaptive algorithms and whether better algorithm exists still remains an open question. In this work, we propose a new motivation for designing the proximal function of adaptive algorithms, named as marginal regret bound minimization. Based on such an idea, we propose a new class of adaptive algorithms that not only achieves marginal optimality, but can also potentially converge much faster than any existing adaptive algorithms in the long term. We show the superiority of the new class of adaptive algorithms both theoretically and empirically using experiments in deep learning.
INTRODUCTION
Accelerating the convergence speed of optimization algorithms is one main concern of the machine learning community. After stochastic gradient descent (SGD) was introduced, quite a few variants of SGD have become popular, such as momentum (Polyak) 1964) and AdaGrad (Duchi et al., 2011) Instead of directly moving parameters in the negative direction of the gradient, AdaGrad proposed to scale the gradient by matrix, which was the matrix in the proximal function of the composite mirror descent rule (Duchi et al.) 20IT). The diagonal version of AdaGrad designed this matrix be the square root of the global average of the squared gradients. Duchi et al. 12011) proved that this algorithm could be faster than SGD when the gradients were sparse.
However, AdaGrad's performance is known to deteriorate when the gradients are dense, especially in high dimensional problems such as deep learning (Reddi et al. 2018). tackle this issue, many new algorithms were proposed to boost the performances of AdaGrad. Most of these algorithms focused on changing the design of the matrix in the proximal function. For example, RMSProp (Ticleman & Hinton 2012) and Adam (Kingma & Ba 2015) changed the global average design in AdaGrad to the exponential moving average. However, Reddi et al. (2018) proved that such a modification had convergence issues in the presence of high frequency noises and added max operation to the matrix of Adam, leading to the AMSGrad algorithm. Other modifications, such as Padam (Chen) & Gu 2018), AdaShift (Zhou al. 2019), NosAdam (Huang al., (019)) and Radam (Liu et al. 2019), were based on various designs of this matrix as well. However, all aforementioned works did not improve the convergence rate of AdaGrad and simply supported their designs using experiments and synthetic examples. A theoretical foundation for the design of this matrix that improves the convergence and guides future adaptive algorithms very much needed.
In this work, we bring new insights to the design of the matrix in the proximal function. In particular, our major contributions in this paper are listed as follows
We propose a new motivation for designing the proximal function in adaptive algorithms. Specifically, we have found a marginally optimal design, which is the best matrix each time step through minimizing the marginal increment of the regret bound.
Based our proposal of marginal regret bound minimization, we create new class of adaptive algorithms, named as AMX. We prove theoretically that AMX can converge with a regret bound of size Ō ((F), where 7 is smaller than T. Such a regret bound is potentially much smaller than those of common adaptive algorithms and make AMX converge

---

Under review as a conference paper at ICLR 2021
much faster than any existing adaptive algorithms, depending In the worst case, show is at least as fast as AMSGrad and AdaGrad under the same assumptions
We evaluate AMX's empirical performance on different tasks deep learning. All experi- ments show our algorithm can converge fast and achieve good testing performances.
2 BACKGROUND
Notation: We denote the set of all positive definite matrices in ddd by S For any two vectors a, E Rd, we use vā for element-wise square root, a² for element-wise square, |a] for element-wise absolute value, a/b for element wise division, and max(a, b) for element-wise maximum between and b. We also frequently use the notation 91:T, 92, ... 9T, i.c. the vector of all the i-th elements of vectors 91
-r. For a vector a, we use diag(a) to represent the diagonal matrix whose diagonal entries are a. For two functions ((),, g(),, f(() o(g(()) means [(t)/9() - 0 as t goes to infinity. We use (-) to omit logarithm terms in big-O notations. We say space X' has bounded diameter Do if x =o S Dao Va, y E X.
Online Learning Framework. We choose the online learning framework to analyze all the algo- rithms this paper. In this framework, an algorithm picks a new 2; E X according to its update rule at each iteration I, where X C Rd is the set of feasible values of 2t. The composite loss function ft + & is then revealed, where & is the regularization function that controls the complexity of x and fi can be considered the instantancous loss at t. In the convex setting, fo and e are both convex functions, The regularized regret function is defined with respect to an optimal predictor xx as
R(T) 21(00 f((x') + o(xx) "(x").
Our goal is to find algorithms that ensures a sub-linear regret, i.e. R(T) = (T),, which means that the average regret converges to zero. For example, online gradient descent is proved to have regret of OVVdT) (Zinkevich, 2003). where d is the dimension size of X. Note that stochastic optimization and online learning are basically interchangeable to online algorithms and their stochastic counterparts using the same names. For example, we will use stochastic gradient descent (SGD) to represent online gradient descent as it is more well-known.
et al. (004). Therefore, we will refer
Composite Mirror Descent Setup. In this paper, we will revisit the general composite mirror descent method (Duchi et al. 2010b) used in the creation of the first adaptive algorithm, AdaGrad, to bring new insights into adaptive methods. Such general framework is preferred because it covers a wide range of algorithms, including both SGD and all the adaptive methods, and thus simplifies the discussions. The composite mirror descent rule at the time step /. + is to solve for
It+1 = argmin xe (ar(gt, z) + (zo(z) + B (z, x1)].
where is the gradient, o (z) is the regularization function in the dual space, and a is the step size. Also, the is a strongly convex and differentiable function, named as the proximal function and B (z. 2x) is the Bregman divergence associated with d/ defined as
Bv, (z. v) = (z) (v)
The general update rule ① mostly determined by the function vit. We first observe that it becomes the projected SGD algorithm when 1i (x) = x" x and 6(x) = O.
Te+1 argmin far (t), || r. 12 Tx (tg)))
(SGD)
where xx) argmin yx || vll2 is the projection operation that ensures the updated parameter is in the original space. On the other hand, adaptive algorithms choose different proximal functions (x((x) (z, H,x), where H, can be any full or diagonal symmetric positive definite matrix.
r 1
(ge x) + a,d(x) (x- Iz, H,(x xx))),
(Adaptive)
Another popular representation of adaptive algorithms is the generalized projection rule Æx+1 H (Ir on H where x (2) argmingex 1// 1)2,, which is used in lot of
2

---

Under review as a conference paper at ICLR 2021
recent literature such as Reddi et al. (0188); Huang et al. (2019). We show that these two rules are actually equivalent when ((z) = in the Appendix A. so that the regret bounds found in different representations can be generalized. A few recent works have shown that adaptive algorithms work well with special designs of the step sizes og (Choi et al. 2019, Vaswani et al. 2020). In this work, we choose the more standard a = a/ vt as is used in most analysis. Also, we restrain our discussions to diagonal matrix proximal functions in the main text, i.e. H, = diag (he), h Rd. Discussions on extending our results to full matrix proximal functions are provided in Appendix
Different Designs of the Proximal Function. Recently, researchers have proposed numerous designs of H, diag(h,) such as AdaGrra (Duchi et al. 2011). Adam (Kingma & Ba 2015). AMSGrad (Reddi et al. 2018) and NosAdam (Huang et al., 2019). to name few. It's impossible to go over all the proposed designs in this section so we choose the two most famous designs to review. The first adaptive algorithm, AdaGrad, used the square root of the average of past gradient squares as the diagonal h1 of the matrix in the proximal function (Duchi et al. 2011 i.c.
R 1//2
Ei g
h4 = (
(AdaGrad)
Normally, a small constant is added to li at each iteration. Some recent work have shown that tuning this constant can benefit the performance of adaptive algorithms (Zaheer et al. 2018 Savarese (ct al. 2019). However, in this work, we assume it is small and fixed for simplicity, as it is originally designed to compute the pseudo-inverse,
equivalently, avoid division by zero in the generalized projected descent. Kingma & Ba (2015) proposed Adam to replace the simple average by exponential moving average in AdaGrad, but Reddi et al. (2018) showed that there was mistake in Adam's convergence analysis, which lead to divergence of Adam even in simple convex problems. They therefore proposed the following simple modification of Adam ensure its convergence.
Ei (1 B2)33 9
h1- = max,
1/23
(AMSGrad)
t
where 32 E (0, 1) is constant. We propose the following theorem that generalizes the regret bounds for most of the designs of the diagonal matrix proximal function.
Theorem 2.1 Let the sequence {x.} be defined by the update rule ① and for any x", denote D2 = || x² 2111.0. When (h((x) (x. H(x), where Hr = diag(hi, (bt,1, he,2, ... hr,d), assume
without loss of generality that @(x1) = 0, Ho = O. if (he,s/a)) 2 (h1-1,./au then
1 Di
angi.
R(T)
+
04-1
2hg
The proof is relegated to Appendix A.3 The above regret bound is suitable for any designs of h, that satisfy the constraint condition (he, 2 (he-1.s/o--1). Such a condition is crucial because if it is unsatisfied. the regret R(T') might diverge. In fact, the divergence of Adam in simple convex problems results from not satisfying this constraint, which is proved by Reddi et al. (2018). With
or = a.vl in Theorem 2.1 most of recent adaptive algorithms have regret bound of the following
form (Duchi al. 2011 Reddi et al. 2018: Huang et al. 2019
Luo al. 2019
d
B(T) S C Σ hTs + f(1)
1Ig.T + C2
where C1, C2 are constants and f(T) ol (T)). These algorithms are supposed to converge faster than SGD when the gradients are sparse or small, i.e. when Ei= hr.; < Vd and Σi= [1g12 < VdT. However, all existing regret bounds are still O(VT), which makes it hard to compare different proximal functions. Whether the best proximal function exists and whether the O(vT) regret bound can be further improved still remain open questions.
'The regret bound of AdaGrad given in the original paper was O(Ilgur,ella)) because Duchi et al. (201 used constant learning rate ou = a and hence h, = Σi= g.. When changed into the same setting where oe az VF, be becomes E:_ of /t and the regret also has the form of 3 shown Reddi et al. 2018
3

---

Under review as a conference paper at ICLR 2021
3 THE MOTIVATION-MARGINA REGRET BOUND MINIMIZATION
In this section, we introduce the motivation behind our new class of algorithms. Although we find difficult to determine the optimal proximal function globally, we show that it is possible find the best proximal function at each iteration through marginal regret bound minimization. Denote R(T) to be the regret upper bound (the right hand side inequality (2) in Theorem 2.11 we define the marginal regret bound increment A (T) as follows.
At time step T,
A AR(T) = R(T) R(T 1) 1) Σ NTT
hT 1.
argr.
D
oT-1
2hr
As shown in the definition, (R(T) will be the increment in the regret bound R(T) after hr is determined. An important observation here is that hr-1 is given constant T, A (T))) is only function of br. Therefore, the best design of by we can find at this moment is the one that minimizes A (T) and satisfy the constraint in Theorem 2.1 Consider the minimization problem
hrr
hr-11 2 0,
mink. Af(T), s.t.
(4)
OT
OT-1
We propose the following proposition that solves the problem above
Proposition 3.1 With at = st, the minimum of problem is obtained at {
T T
2
h4 max
12
I9r
(5)
2TD7
To see this, set the function L with the Lagrangian multiplier as follows
Σ hrg
hr-1.
argi.
hr
hr-1 11)
L(h,
D
OT
0T-1
2hr,, OT
CT-
Take partial derivatives with respect to each lT, we can see that D7.00 = ( + p..
By the complementary slackness conditions, either 0 or hr, = (arr / /h When
N4 = 0, lur;; (a /e
and the constraint condition lT,;; 2 (OT forr/ar /or MTT needs
to be satisfied. Hence, by setting or = a/ /T, we can get the solution in 5
Solution 5 is the best diagonal matrix proximal function in terms of regret bound increment at time T. Therefore, if we replace T by in the subscripts, we can obtain a greedy choice of the proximal function he that minimizes the marginal regret bound increment each time step. Intuitively, the
reason this solution achieves the minimum is that it balances the two terms of A R(T.. On each dimension (i), it makes the first term of A AR(T zero when the derivative small
2 i.e. when
don't 't need to have a even larger fTT to slow down. When the derivative is too large, fir,, adapts to
the size of the derivative so that the second term of AR(T) is constrained.
However, similar to the other greedy algorithms, solution 5 only suboptimal minimizes the regret bound marginally instead of globally. Moreover, the parameter Dr, is often unknown during the optimization process because x" is usually unknown. Therefore, stronger theoretical motivation is needed to trust that solution or similar algorithms can be useful and beneficial.
4 A NEW CLASS OF ADAPTIVE ALGORITHMS AMX
Now, motivated by the greedy choice of he in section 3 we focus on a more general design of the diagonal matrix in the proximal functions that has the following form and show why such greedy designs can be beneficial in the long term. Consider
h max { -
(AMX)
Because (hx,a/ot) (hr-1.//u-s) O when he, (0t/or-1)ht-1,
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1 AMX Algorithm (Diagonal, Composite Mirror Descent Form)
1: Input: F, 0; a/vl,
2: Initialize hg 0, Hn - 0
3: for /= to T do
4: 9t = f(()
5: h = max(
- 1 +e
6: 21+1 argmin (ge, a(d(z) + (x- 24, diag(h:) rz))
7: end for
where ot is arbitary function of t, for example solution (5) or as simple as c 1. The correspond- ing new class of adaptive algorithms is given in Algorithm which we name as AMX. Note that the diagonal proximal function performs all operations coordinate-wist wisely, therefore we start our analysis from one dimension (z). Denote (i)-th dimension component of the regret bound as
he-1á ) Di,
(T)
(6)
04-1
2h4
For a sequence of gradients 91.92. gr, denote the time steps when h4 celgr,il as (8) Tm. Note that 7j " may be different across different dimensions, so the analysis apply to each dimension independently. These are the time steps when the gradient term celsal dominates h on the (i)-th dimension and h4 = c, when f y Vj = =, m,, Since he,
Ti 12
(i)
is equal to / 1 h between Tj " which is exactly the same as in section the increment in the first term of the right hand side of (6) is always O. Therefore, we have the following proposition
Proposition 4.1 For any E (T) j+t). the regret bound increment on the (i)-th dimension is
aggi
( RD (T,0)
2h,
The above proposition indicates that the regret increments between the T (1)ss 's are only related to the second term (T). Note that the first term (T) is major reason why the regret bound is O(VT) because there is 1/ar term in the summation. Therefore, such designs of h4 try to constrain the regret increments between 7, (()'ss and hence can potentially make the regret bound small.
More importantly, Proposition 4.1 is true for the time steps between the last ((()) and + 1. Denote Doo to be the bounded diameter of the parameter space X' because the regret bound increment is
only related to the second term after the last Tim the bound in equation (6
(8)
becomes
(T) S
T
11-1.
D
+
aigi
D2
Tim
Iecal
az
ar-1
2
Tan
2
1=1
1=1
Since R(T) = Σd
R()( so the total regret upper bound across all the dimensions is
d
D2
T a
R(T) <
19r.l
(8)
2v7c.
The first of the right hand side can be considered better than the O(vT) regret bound of SGD or common adaptive algorithms when some or all of the Tim; are much smaller than T and hyp's are bounded. Therefore if we can ensure the second term also increases much slower than O(VT), which is decided by the design of c, then the AMX class of algorithms is potentially much faster than SGD and the other adaptive algorithms. Note that need h, be bounded in the above arguments, therefore e, can be at most constant. Fortunately, one simple yet very effective design that we have found is c 1. We formalize the above statements in the following theorem.
5

---

Under review as a conference paper at ICLR 2021
Theorem 4.1 Let {xe} and {he} be the sequences obtained from Algorithm 1 a4 = aa/attte (Ti) Let {Tms Ji=1 Ji= be the largest time steps t on each dimension when he, = at at Assume that F has
bounded diameter 1
y11 I Dx Vx,y y E F. Then we have the following bound on the regret.
D2
T (6)
R(T)
log Tmn l1g (8)
.1l2
log(
1
2
Tins
An important remark here is that using a different constant = c in Theorem 4.1 is equivalent to tuning the step size by 1/c, as it magnifies all [9t at the same time in the algorithm. Using decaying C can further improve the first term in Theorem 4.1 but it also enlarges the second and the third term so the regret may not be O( D()T) anymore. We will focus Ct to prove AMX can potentially converge faster in the rest of this paper, but a detailed discussion about the possible choices of e for future designs of the AMX algorithm is provided in Appendix A.. which proves that e cannot be O(1/VE) if we do not impose any further assumptions.
Now, since most of the bound in Theorem 4.1 depends on the time steps {Tmi 1d instead of T (only log term), the specific AMX algorithm can be potentially much faster than common adaptive algorithms. To further make our argument clearer, we propose the following corollary.
Corollary 4.1 Let T max; (aax,(Tih) {TiM)) } in Theorem 4.1 under the same assumptions as AdaGrad and AMSGrad, Algorithm converges with regret bound
T )
(imax(VT.Vis log
(10)
The corollary indicates that the regret bound is approximately of size Ö(VF) if we omit the log aware, this is the first algorithm that generates regret bound that is not
terms. As far asymptotically O(VT), so AMX can be potentially much faster than any existing algorithms. The time step can be understood as "the time when the gradients start to converge" and whether it makes the convergence faster depends on the distribution of the gradients. For example, if T = vT, the regret bound only of size OTT//1 log T). We emphasize that a small T is not an assumption on the gradient distribution, but rather a condition that once satisfied, the regret bound will only increase logarithmically and hence the algorithm converges very fast. Moreover, the regret bounds of the other adaptive algorithms go to (VVT) even under such conditions, because their regret bound increments not minimized. We use rather simple example to illustrate why AMX has this unique advantage.
Example. Suppose that the domain is a hyper-cube X' = [| I 1}. then Doo = 2. Assume that each dimension, the gradient decreases 19c,al (1/vř)lg1.n (1. and 191.; < 1, Vi. Note that this is one example where adaptive algorithms should work well since [|gı,,ill2 < !9.. (1 + log T) < VT. A very important property for AMX in this case is that is the first time step, its regret bound only increases logarithmically. However, the regret bounds of the other algorithms still goes to O(VT). We plot the regret bounds of AMX, AMSGrad and AdaGrad in Figure 4, Note that the regret bound of AMX increases much slower than AdaGrad and AMSGrad, hence it is much faster than these algorithms in this example. One may argue that the example is extreme since - = rarely happens in real situations. However, the regret in this example can be understood as the regret increment after in real training processes, i.e. before т, AMX is only asymptotically as fast as the other adaptive algorithms, but after since the regret increment of AMX is very small, it converges very fast. More details of this example can be found in Appendix D.I
AVX Acctival Avoors
24
13:0
530
3030
1203
Figure 1: The regret bounds of AMX, AdaGrad, AMSGrad in the example.
Besides, since the term V log /T) in Corollary 4.1 is at most ( the AMX algorithm is at least as fast as AdaGrad and AMSGrad under the same assumptions. We propose the following theorem that corresponds to the general results in section to prove our claim:
TTiis claim can be easily proved by taking derivative of and finding the maximum of VFlog(T/T)

---

Under review as a conference paper at ICLR 2021
Theorem 4.2 Let {xi} and {he} be the sequences obtained from Algorithm ! Assume that F has bounded diameter | yllso I Dxx Vx, y E F. Then we have the following bound on the regret.
a4 aa =
R(T)
D2 VT
hT + a 2 V 1 + log T
111.
(11)
The above bound can be considered as being better than the regret of SGD, i.e., O(vdT), when Ei= /T, < Vd and Σi= |g::T, < VdT (Duchi et al. 2011). Therefore, AMX can be at least much faster than SGD when the gradients are sparse small, and can be potentially even faster. To keep up with the current popular adaptive algorithms such as Adam, we also provide the detailed implementation of adding first order momentum into AMX and include some discussions on its convergence properties in Appendix [ Similar to Algorithm [I] the AMX with momentum algorithm has regret bound that (mostly) depends on instead of T and hence enjoys the acceleration.
EXPERIMENTS
In this section, we evaluate the effectiveness of the specific AMX algorithm proposed in Section (i.e. = 1) on different deep learning tasks. We relegate more details of parameter tuning and step size decay strategies to Appendix D.2 Moreover, an empirical analysis for different designs of fcr 1?- that show different {ce ) generate different performances is provided in Appendix D.6
METTI
Manw
AMSS ad
AUSCred
SGOM
900V
1987 W881 N0W 4099 J008 SA8
28.0 7000 190h K00 300
27
100
202
100
(a) CIFAR-10 Training (bc.(b) CIFAR-10 10 Testing Acc(c) CIFAR- Training Acc(d) CIFAR- 100 Testing Acc.
Figure 2: Training and Testing Top-1 accuracy on CIFAR-10 and CIFAR-100.
Table 1: Testing Top-1 accuracy the CIFAR-10. CIFAR- 100 datasets and testing IoU on the VOC2012
Table 2: Validation perplexity on the charac- Penn Tree Bank (PTB) dataset and BLEU score on the IWSLT' 14 DE-EN dataset. The results were averaged over three independent muss. Our results were shown in hold.
Segmentation dataset. The results were averaged over 5 independent runs. Our results were shown in bold.
OPTIMIZER
CIFAR-10
CIFAR- 100
VOC2012
SGDM
92.40 + 0.06
77.80 + 0.08
76.10 + 0.09
OPTIMIZER
CHAR-PTB
IWSLT' 14
ADAGRAD
85,60 : 0.14
72.84 0.06
71.28 + 0.18
ADAGRAD
2.63 + 0.04
25.56 : 0.05
ADAM
91.85= 0.03
0.011:005
$3.32#0.211
ADAM
2.48 - 0.08
28,01 + 0.07
AMSGRAD
9..97
75.75 + 0.04
73.66
2.13
AMSGRAD
2.46 1 0.05
28.15 0.06
AMX
92.42 0.08
77.65 0.10
76.04+ 0.16
AMX
2.32 - 0.04
28.29 0.03
We compared our AMX algorithm with SGD with momentum (SGDM), Adam, AdaGrad and AMSGrad on different tasks in deep learning- The hyper-parameters in AMX were set to be c in this subsection. For the language modeling and the neural machine translation tasks, because SGDM typically performs much worse than adaptive algorithms, we did not include it in the comparisons. Following Loshchilov & Hutter 2019). we used decoupled weight decay in all the algorithms.
Image Classification. We first conducted some experiments where 7 possibly very large and AMX was only as fast as the other adaptive algorithmss, but still achieved better testing performances. The image classification task was performed on the CIFAR (Krizhevsky et al. 2009) datasets. We used the publicly available code by Li al. (2020) and De Vries & Taylor (2017) 7) to train ResNet-20 and 18 (He al. 2016 on CIFAR- 10 and CIFAR-100 respectively using batch size of 128.

---

Under review as a conference paper at ICLR 2021
We summarized the performances of different algorithms in Figure started slightly slowly, but it quickly caught up with the other adaptive algorithms and converged much faster than SGDM. This was possibly because the time when gradients start converge (the in section 4 was large in image classification tasks, and AMX could only converge asymptotically as fast as the other adaptive algorithms, corresponding Theorem 4.1 However, its final testing performance was as good as SGDM, so it converged both fast and well at the same time. The other adaptive algorithms such as Adam and AMSGrad had faster training performances in the beginning. but they ended up with much worse final accuracy than SGDM and AMX.
2 and Table As observed, AMX
Image Segmentation. Next, more experiments proved our claim that AMX could be potentially much faster and generate even better testing performances. For the segmentation task, we used the publicly released implementation of the Deeplab model (Chen et al.] 2016) by Kazuto (2016) and evaluated the performances of different algorithms on the PASCAL VOC2012 Segmentation dataset (Everingham et al. 2014). We used a small batch size of 4 and polynomially decaying step size in 20k iterations. The trained models were evaluated at the 5k, 10k, 15k and 20k iterations and we used mean Intersection over Union (loU) as the evaluation metric. The results were provided in Figure ((a) 3(b) and Table I As shown in the figures and the table, AMX not only the fastest adaptive algorithm but also achieved the best IoU score, which was comparable to that of SGDM. The other algorithms were not able perform similarly.
Adamii
Adumii
Atumni
AMSGrad
AMEGGed
AUSG ad AMX
AMSG ad AMCX
0.14
SG:M4
300g
1208
LOW
2006
1906 18030 118 1480 19000 1ES 2833
100
3013
300
4%
300
1000 2003 2000 1E0 SEB GRR 1000
(a) VOC Training Loss Curve (b) VOC Testing IoU
(c) PTB Test Perplexity (d) IWSLT Test Perplexity
Figure 3: (a), (b). Training Loss and Testing loU curves on the VOC2012 Segmentation dataset. (c). Validation perplexity curve on the Penn Tree Bank (PTB) dataset. (d). Validation Perplexity curve the IWSLT' 14 DE-EN machine translation dataset.
Language Modeling. We trained lhree-layer LSTMs (Hochreiter & Schmidhuber 1997) the
character level Penn Tree Bank (PTB) dataset. The general setup in Merity et al. (2017 7) was adopted in our experiments. Specifically, we trained the model for 500 epochs with batch size 128. The validation perplexity curve and the final validation perplexity were shown in Figure 3(c) and Table 2 It can be observed that AMX was the fastest algorithm and achieved the lowest perplexity among all the adaptive algorithms, which proved our claim that AMX was potentially much faster.
Neural Machine Translation. We utilized the publicly released code by peyin 2018) and trained the basic attentional neural machine tramslation models (Luong et al. 2015) on the IWSLT' 14 DE-EN (Ranzato et al.) 2013) dataset. We used 64 as the batch size and decreased the step size by every iterations. The validation perplexity curve and the final BLEU score were reported in Figure 3(d) and Table 2
AMX not only had much smoother validation perplexity curve, but also achieved the best BLEU score among all the adaptive algorithms,, showing that AMX was indeed a better choice.
6 CONCLUSION
In this paper, we propose our design of the best proximal functions at each time step based on marginal regret bound mininization. We then show that more general class of adaptive algorithms can not only achieve marginal optimality in some sense, but also converge much faster than any existing adaptive algorithms, depending on the distribution of the gradients. We evaluate one particular case of our new class of algorithms on different tasks in deep learning and show its effectiveness. This work provides a new framework for adaptive algorithms and can hopefully prevent the random searching process for better designs of the proximal function. Future researchers can concentrate on finding better choices of the sequence {c to find better algorithms.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, USA, 2004. ISBN 0521833787.
Nicolò Cesa-Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. IEEE Transacitons on Information Theory. 2004.
Jinghui Chen and Quanquan Gu. Closing the generalization gap of adaptive gradient methods in training deep neural networks. arXiv preprint arXiv:1806.0677 06763, 2018.
Liang-Chin Chen, George Papandreou, Iasonas Kokkinos, Kevin Murphy, and Alan L. Yuille. Deeplab: Semantic image segmentation with deep convolutional nets, atrous convolution, and fully connected crfs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40:834-848, 2016.
Dami Choi, Christopher J. Shallue, Zachary Nado, Jachoon Lee, Chris J. Maddison, and George E. Dahl. On empirical comparisons of optimizers for deep learning, 2019.
Terrance DeVries and Graham W. Taylor. Improved regularization of convolutional neural networks with cutout, 2017.
John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Ambuj Tewari. Composite objective mirror descent. In Proceedings of the Twenty Third Annual Conference on Computational Learning Theory, 2010b.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research (JMLR), pp. 12:2121-2159, 2011.
Mark Everingham, S. M. Ali Eslami, Luc Van Gool, Christopher K. I. Williams, John Winn, and Andrew Zisserman. The pascal visual object classes challenge: retrospective. International Journal of Computer Vision(IJCV). 2014.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, pp. 9(3):1735-1780, 1997.
Haiwen Huang, Chang Wang, and Bin Dong. Nostalgic adam: Weighting more of the past gradients when designing the adaptive learning rate. arXiv preprint arXiv: 1805.07557, 2019.
Kazuto1011. Deeplab with pytorch.
https:///gttubb.cmm//kuuttt//
deeplab -asbbrchttrc 2016.
Diederik P Kingma and Jimmy Lei Ba. Adam: A method for stochastic optimization. Proceedings of the 3rd International Conference on Learning Representations (ICLR), 2015.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced research). 2009.
Wenjie Li, Zhaoyang Zhang, Xinjiang Wang, and Ping Luo. Adax: Adaptive gradient descent with exponential long term memory. arXiv preprint arXiv:2004.097440 2020.
Tsung- Yi Lin, Michael Maire, Serge Belongie, Lubomir Bourdev, Ross Girshick, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick. Microsoft COCO: common objects in context. CoRR, abs/ 4t5./4005.033 02.. 2014.
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. arXiv preprint arXiv:1908.03266 032655, 2019.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. Proceedings of 7th International Conference Learning Representations (ICI.), 2019.

---

Under review as a conference paper at ICLR 2021
Liangchen Luo. Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. Proceedings of 7th International Conference on Learning Representations. 2019.
Minh-Thang Luong, Hieu Pham, and Christopher D. Manning. Effective approaches attention- based neural machine translation, 2015.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing Istm language models. arXiv preprint (00iv0/700.02/888 2017.
peyin. Basic pytorch implementation attentional neural machine translation. /attpa://iithu
com./pcyin/pytorrchhcc sasrrrchhhhiiiie www.aasiiiie... _as_s__aaaii________ 2018.
Boris Polyak. Some methods of speeding up the convergence of iteration methods. USSR Compula- tional Mathematics and Mathematical Physics, pp. 4(5):1-17, 1964.
Marc' Aurelio Ranzato, Sumit Chopra, Michael Auli, and Wojeiech Zaremba. Sequence level training with recurrent neural networks, 2015.
Sashank Reddi, Stayen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. Proceedings of the 6th International Conference Learning Representations (ICLR), 2018.
Pedro Savarese, David McAllester, Sudarshan Babu, and Michael Maire. Domain-independent dominance of adaptive methods, 2019.
Tijmen Tieleman and Geoffrey Hinton. Rmsprop:
Divide the gradient by a running average of its recent magnitude. COURSERA: Neural networks for machine learning, pp. 4(2):26-31, 2012.
Sharan Vaswani, Frederik Kunstner, Issam Laradji, Si Yi Meng, Mark Schmidt, and Simon Lacoste- Julien. Adaptive gradient methods converge faster with parameterizatiion (and you can do line-search), 2020.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. Advances Neural Information Processing Systems 31, 2018.
Zhiming Zhou, Qingru Zhang, Guansong Lu, Hongwei Wang, Weinan Zhang, and Yong Yu. Adashift: Decorrelation and convergence of adaptive learning rate methods. Proceedings of 7th International Conference on Learning Representations (ICLR), 2019.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent, Inter- national Conference Machine Learning (ICML), 2003.
10

---

Under review as a conference paper at ICLR 2021
A PROOFS OF RESULTS IN THE MAIN TEXT
In this appendix, we provide proofs of all the results and theorems in the main text, except for Theorem 4.2, which is proved in section Cas as it is the same 31 = 0 in the momentum design. An important remark here is that adding e to h2 does not affect the proof here because when h4, is placed on the denominator, 1/hr, 1/(/, e). When he is placed the numerator, we generally use br. instead of giving it specific form. Also, we set e to be very small in real experiments (Ie-8).
Further Notations. Except for the notations mentioned in the main text, the following notations needed for this appendix. Given a norm || ||. its dual norm is defined to be l| s { (z, v/
For example, the dual norm of the Mahalanobis norm || I| = v(, A-), A 0 is the Mahalabonis
norm || ||A-1. A function f is said to be 1-strongly convex with respect to the norm || || if
f(v) 2 f(x) + (Vf(z), x) + z11kz vll
A.1 EQUIVALENCE BETWEEN COMPOSITE MIRROR DESCENT AND GENERALIZED PROJECTED ALGORITHMS
Begining with the generalized projected adaptive algorithm, we can find that
T++1 / (z+ 04 Hr 9t) == argmin || (xt a4 H,, 9:) 1
= argmin Dex | (a (z, H, 9x))]1²
argmin || / xx.) + or H, 1/2 gt. 1|
(12)
argmin
x - xι) + (x 2t. Hi (z - z1))}
argmin (2ar (9t, (x It, H1 rz))}}
Given (x)) (x, Hev), it can be shown directly (also in A.3) that Ba, (Ir, xz) (x-Ir, Hx(x-x)))
Therefore comparing equation 12 with equation T we know that they are equivalent when the regularization term ((x) = 0, except that we need to double the step sizes
A.2 PROOF OF LEMMA A.
Lemma A.1 Let {x,} be a sequence of outputs from the update rule (1) and assume that (Ve) are strongly convex functions with respect to the norm norm. Also without loss of generality let B
-1 Let || ll be the corresponding dual
(x", (x" = 0. Then for any x², we have
T
T
B (xt,2.)
B (x" .1)
+ at (((())))
f((x)) - fo(x") + 6(x+) - 60x²))
Or.
0t-1
2
(13)
Proof.
Since r++1 satisfies equation 1 for all E X and d' (x(11) E 06(21+1).
(x- Iz+1, 0tgi + o, (2++1) Voh( - Vvi(zr)) 20
(14)
Also since fi's is are convex functions, know that f((x) 2 f((z)) (f)) xx) and likewise for ((x(+1). We therefore have the following
arlf((zs) - f((x*))
= =
le+1 -
+o (1) xx) a (n I(+1)
(15)
-x-- - I1t1, V - (z) - ((f (x(11)))))
+ +(x" - r1t1, Voh V + (z z(+1)
(xx I1+1. Vvl(.,)) Voh
an ar
tx+1)
where the first inequality is due to the convexity of o, and ft. The second incquality is due to the positiveness in equation 14] Since by definition
11

---

Under review as a conference paper at ICLR 2021
Be (x", ,D)) = v1(x')) - v)(()) - (Vii( - xz)
Byg (x", (I++1) (1(x") (1(0+11)))))))))1))))))))))))))) (V14( 31+1)
(16)
Be, (Fe+1, = (1(()+1) - (2(())) - (V 2141 - xz)
Therefore
ar(f((a)) - f((x'))) + ai(((1(+1) - o(x'))
s By, x1)) By (x",2++) Bi (1t+1, R2) + ae(S((()); s1+1)
s By (2" ,2)) Bw (1" (1411) (1141, 22) + | 112. ot
1
( (17)
2
of [
s Byg (x" ,21) B (x", T441)
where the second inequality is due to the Fenchel's inequality on the conjugate functions 5 1 and ell - The last inequality is due to the strong convexity of B (:. Therefore the lemma can be proved by dividing or on both sides and take the summation.
A.3 PROOF OF THEOREM 2.1
Proof. When (x) (xr, H,æ),, the dual norm || lll; is the Mahalanobis norm || Ilm."
(2, v) -e((x) - (2( (Vvi(y) x y) (xx H(x) - (yy, H.y) - H(H,y, - 8) ((x v), He( yy)
(18)
Therefore by Lemma A.1
Σ f(())) - f((=') + ((xx)
66x*)
T Be, (x*1
Bug (a*,
+ at =² (1))
<
||
1/2 (xt =2²)12
11 1/2 (#++1 - =11
at -
04
a4
H
/2 (x1
x²) x²2
H 1/ (xt (
x= x²11
|1 (xt - x²11
Σ
(1((())))
a
at
ar-1
2
t=2
h1s
(I1,1 - xz722 +
h4,
1
(x1, x;t)2
Σ
0t
aq
04-1
1=2
he,i
11111
(
T
d
ai
at ((,
Otg
0t-1
2
2h,
1=1
he.
h1-1,
T
arfi (xe)²
D2
Oks
at-1
2h
1=1
t=1
(19)
where the second inequality is by re-arranging the sum and deleting the last negative term.
12

---

Under review as a conference paper at ICLR 2021
A.4 PROOF OF THEOREM 4.1
Proof. Based on Theorem and Proposition 4.1 take he to be the design in Algorithm | with
[2] Ct = Then after the final Tim, (which means the last gradient that "large") for each dimension i, the first term doesn't I increase and the second term can be bounded as follows.
T
1,11 1,1
d
agg
R(T)
D
04-1 1 Ct
1,00
2hg
d
h_
T
d
Time
Do
at
Mt,i
(8)
00
2
1=1
t=
i=1
Time
(6)
d
9t,i
++]
Σ
d
T
0x
9t,i
(8)
2
2
t=1 1=1
1=1
t=rm,
+1
TTRL
(8)
d
d
T
a
Tm
(
D
9
2
2
t
1
t=1 i=1
i=
t=rm
(1)
+1
(1)
Tim
(8)
(E)
d
d
T
D
+
gh.s
+
Tim
(0)
log
2
2
[= 1 i=
Y=1
T
D
a
Tim
(4) THN
a
+ log Tim
(+)
l12
+
Tin
(8)
9
Ting
(4)
log(
Tm,
T
(
(20)
where the first inequality is by Theorem 2.1 and the second one is by Proposition 4.1 The third inequality by the fact that 19r.:l S
10)
m0 . for all t 2 Tim
(8)
+ 1. The fourth
inequality is by Σ T 10
Stmminn +1 1/t I1=
(9) 1/1 log(
The last inequality is by the fact that
7ing
d
Qt
Jt,i
<
9
,1l2,
2
==1
1=1
(21)
a
+
log Tim 111 .12
(1)
2
where the first inequality is by the Schhaz- Inequality.
A.5 DISCUSSIONS ABOUT THE POSSIBLE DESIGNS OF Ct
We first show our claim that given design of c.. scaling it by constant is the same scaling the step size a, by 1/a. Note that the maximum operation can be commuted with constant scaling, therefore by unrolling the maximum operation
13

---

Under review as a conference paper at ICLR 2021
h4 max
h 1, aceleel
max
h celgal
t
1
2
max
1 max
2 a00-110--1111 19c--11
celoul
(22)
1-1
a max
h 2,
c-
19- 11
t
V
max
1=0
Therefore we know that it is equivalent to scaling a, by 1/a since it magnifies all a G. at the same time. Now given the discussions in section we know that can be at most constant, which is because it is strictly 12(1), then the regret is strictly 22 ((VT)). Now we can possibly use a decaying Cr. However, if cz is too small, then the regret may also be strictly S2( ((VT) because the second term in Theorem 2.1 can be very large. We show that & Q(1/vl) by giving a counter example of the sequence of gr such that the regret becomes very large. Suppose 19ol (1/t)²/a|gn) [g]), [g
0, Vi, a 1/Vi, then since the size of the gradients keep decreasing, hence
h4 max
ca-5199-)
1=0
1-1
i j
max
V
gc-ssl
vt
(23)
1=0
max (1gt-
1
9
Vi
The specific distribution of gradients meets the requirement for adaptive algorithms to work well because 11 = Iø Σx VŁ = O(T1/4) Now, despite the first term in the regret bound in Theorem becomes constant, the second term becomes very large because
T
14,5
h1-15
T
d
aggi,
R(T)=
<
D&
+
Ogg
a1-1
1,00
2hg
1=1
1=1
1=1
d
agi,
D2
(24)
a1
2/
t=1 i=1
hi
T
algi,l
D2
+
O
2/t
Now notice that
14

---

Under review as a conference paper at ICLR 2021
VT 2VV--1
(25)
Therefore the regret upper bound there is already O O(VT). Changing the gradients be further larger, for example, Ige| = (1/1)1/8| 91). will still satisfy the |19:7: < VT condition, but also make the regret bound even larger (0(T)/4)). Therefore using C = O(1/Vt) is unacceptable in terms of the of course change the initial time step, the argument still holds if the first few o s are not smaller than ((1/V() in order. Next, we show the regret bound is indeed achievable by the regret. We propose the following theorem:
regret bound. Note that
Theorem A.1 If ot = O(IVVE) in Algorithm ] then there exists an online convex optimization problem where 11122 & VT and AMX has a regret of size ((VT)
Proof. We recall the terms in the proof of Lemma A.l
a<(f((z)) - f((x')) an(((1411) -
- x(x'))
(4) x²) {f((f((t),
a (0) re+1 -
-x") x²)
(26)
= af 2441 x²) ) a 1 (Ie Je+1 x²) + a. (f(f(())), 2 x(+1)
If we set (0x) = O in the above inequality and let fx(x) ge be linear loss function, then the first inequality becomes an equality. Moreover, it's possible to make the term at (x)) J++1 -xx) > for all f, as long
change the loss function to be positive when Iz+1 x and negative when It-1 < x,, then we know the regret
R(T) Σ
Σ (1(2)), - x²) x²)+ + (f((zz), 2141)
2 Σ (f,())), - x(+1)
(27)
Wtt: 2 H. gi)
aggi
2/4,i
Notice what we have claimed before Theorem A.1 are all about this term being larger than O O(VT). therefore we prove our claim.
B FULL MATRIX PROXIMAL FUNCTION
When He is not a diagonal matrix but full matrix, we can similarly prove a general regret bound for any matrix in Theorem B.1 below.
Theorem B.1 Let the sequence {at} be defined by the update rule 4 and for any x", denote D222 = I|+e - x= 11.. When (1)(x)) = (x, Hyx), where H, E St is a general matrix, assume without
loss of generality that ((x1) = 0, Ho 0, if ir( He 2 ir( H.-1
a. then
T
T
R(T) < Σ
D2 1r
|r(
He He-l
+ Σ
ar
gt
H.
(28)
at-1
2
t=1
t=l
15

---

Under review as a conference paper at ICLR 2021
Proof. When He is full matrix, similar to Theorem
2.1
get the regret bound
(x"
B (x" xz)
R(T) S
(gt, H
(29)
ag
at11
Let Amax (M) denote the largest eigenvalue of matrix M, then
B (x))
B (x",
He
H, 10-1)(0000 -x=)
(x" It.
a
ar-1
a
ax-1
(30)
Ht
He-l) S 1100 Iz 12
He He-1
< ||00 - It A22x
0t-1
04-1
Hence we prove the regret bound shown in Theorem B.1 minimization problem in this case corresponding to Theorem B.1 and the constraint is
Moreover, the marginal regret bound
He O4
H1-1)- + at (r(HH, 9(9)), s. > 0, tr(
H
H
min tr
tr(
(31)
04-1
2
az
where Dr.2 ||,
x" I|2. Now, we propose a proposition that shows the optimal full matrix solution is the one that reaches the infimum of the problem.
Proposition B.1 The following matrix
tr( 1-1 H.
ar
H max
1
T 1/2
(Full)
(32)
of (r([ (r(( 2D) Hu9 1/2))
2D2
and its Pooore-Penrose pseudoinverse H;; gives an infimum to the problem
31 iee.
Dj Diptr( Hi + tH( 9:9 inf H.>0,an "e 12 at 2
Diztn ) +
at tn(
tr(
9.96
He-1 ac-]
at 2
(33)
Proof. Now similarly, we can first construct the Lagrangian for the marginal regret bound minimiza- tion problem. Let 0 Z 0 denote Lagrangian parameter for the trace constraint, and Z ż 0 for the positive definiteness constraint. Then the Lagrangian problem is
He +
at 1H, 9.9)t) Our(( He H (r(H 2
L(H,,0,2) -
(34)
04-1
Take derivative with respect He we can get
D a1 H g:gi H1 01 =
(35)
0t
where / is the identity matrix. an invertible H, can be found, then the generalized complementarity condition (Boyd & Vandenberghe 2004) implies that Z = 0 and either 0 = 0 or tr( mi
= tr H4
If 0 = 0
H, ( o3 2D "191) 1/2 and tr(
Hi
tr( H
(36)
at
a4-1
However, this is not an acceptable solution since is not invertible.
If 0 of O, note that we need 0 to be real, hence there is no solution because grg. has rank at most 1, and even if 0 = / or, there does not exist a matrix that makes the term H, 9:9h H, zero
Instead, propose the following matrix reaches the infimum of problem 31
16

---

Under review as a conference paper at ICLR 2021
tr( 1- H ir((2ng )
H1-1)
( at
H max
1
2002 a )
(37)
It can be understood as special maximum operation that makes sure
tr(H;)= = max unly t Ht-1), at tr((g:g)) )122)
v2D
Now, a very important remark here is that the solution is not invertible, because 9.gr has rank at most. Therefore, the equation above is not acceptable direct solution to problem (31). However, setting H, to be as in the above equation gives solution to the infimum problem in Proposition B.1 Let 9:96 be diagonally decomposed by
Q
Q²
of 9r
Σ 9i,
(38)
and define the matrices (8) that can be written as,
tr( L- Hz-1)
aiee
Vo 0
(6) max
Q
Q",
(39)
V + nd
V2De
0
51
Therefore we know that limg-s0 He(0) = H2 and that
Dr, at.
Ho(d),
+ at (6)
9:9?
2
tr( Vt-1
Vo
arlVu +
V2Dr2(VE +nd)
Vo
of
Hi-1),
+ min
Ir(Q
Q²))
22,
2tr( - H1-1)
2
0
max tr( Vt- H
Vv
(Vu + nd) /vou
22D22(V no)
+ min
2D1,
1-ع H+-1) 2tr(
2
(40)
Hence
lim Dip
Hi(0)
+
a ai (6) '(9g""
8-4
ai
2
=D max tr(
H Hr-1); 1);
V
+ +mn
a+
V2Di,((V)
/2Dr,2
2tlv L-1 H
Hi
-D 0tt
tr
Hi gish T
(41)
2
vt
V--I
D2 2r,2
H.-1)
1- H is larger if
if
2tr(
1 H
V2Dr220
if
04 V2D,2
ur((9,97)) larger
17

---

Under review as a conference paper at ICLR 2021
Now, let g(0) = Hnf (L,H,, 0, Z())) be the dual of problem 31 where when Dig > 0 we define the matrices (0) and (0, 6) as
(
0
Dia
H,(0,8)=
at
Ve
0
Q",
(42)
8)1
22 -
0 57
Then from the derivative with respect to Hr, we know that
D
8)1
at (,(0,6) 919; H,(0,8)-1 Z(0) =0
(43)
a2 2
Therefore 60, achieves the minimum in the dual, moreover
g(0) 1r. H)(0,0)
at 9 9 0tr((
H2(0,6)
H1-1 tr(H,,0,,0Z(00)
) +
04
2
04
04-1
(Vū + 6n)
V 20 2o(DD? - -0a))
(Vo + +n)
-tr( H(-11
(n - 1)8(D} - -0cr))
=Di,2
0(
22 -80r)
2
/2(2,, - -Bor)
a1-1
/2 - -Aa.)
2v (Di,2 - tor)
(n (n-1)6, Di,2 - ta,
= =DD - -0) (Vo+ + 88)
H1-1
Otrl
V2(Di22 Octe)
2
04-1
v22
(44)
Notice that take 0 = 0, lims g(0) = V2Dr, 2. V., and take to be
aclv no)
D20 Oc.)
(45)
tr( or 11
then
((0) Di
1 Hz-1)
+
a25
04-1
2tr( / / H,-1)
(46)
Note that they are equal the cases respectively, therefore the duality gap in this problem is zero and H2 is indeed the infimum solution.
Similarly. He always better than any other full matrix proximal function at in terms of regret. unified algorithm is provided in Algorithm 2, where the max" operation is a special operation that shows how the diagonal AMX algorithm is similar to the full matrix one, in the sense that it tries to find the maximum trace between the two matrices, i.e.
tr(H)) max tr(
Hz-1), (((
C DISCUSSIONS ON AMX ALGORITHM WITH MOMENTUM
We provide the detailed implementation of the diagonal AMX algorithm with momentum and decoupled weight decay here. The momentum term is implemented in line 5 in Algorithm B where and {3 called the momentum parameters. This implementation exactly the same as the implementation modern adaptive algorithms such as Kingma & Ba (2015); Reddi al. (2018): Huang et al. (019) and Li all 2020)
my -1-
18

---

Under review as a conference paper at ICLR 2021
Algorithm 2 AMX Algorithm (Composite Mirror Descent Form)
1: Input: E F, {ax 1
2: Initialize hgg 0, Ho
3: for wrtt = to T do
4: 9: fx,,
5: if H, is diagonal matrix then
6:
h. max( / (-1 1 (1/9))
7:
H₂ diag (1)) te
8:
else
H, max" (v (v H4- (cagngt 2122) +
9:
10: end if
11: 21+11 argmin (gc, + a(o(z) + (x - Tz, H.( - 2z))}
12: end for
Algorithm 3 AMX Algorithm with Momentum (Diagonal)
1: Input: x F, ([a))))_1 (51 17 = 1,c le 8, 5e -2
2: Initialize mo hi
3: for to do
4: 9: f((ee)
5: m, = 8imm-1 + (1 - B11]gt
6: h V maxx 1 1i cth +
7:
H₂ = (ha,, h4.2.
.. ......,h h(.d)
8: Ft+11 H H. (It a.m4 /2e \oraf))
9: end for
The following theorem provides regret bound for algorithm 3 shows its convergence.
Theorem C.1 Let {rr} and { be the sequences obtained from Algorithm 3 at = atvi.a 1,81, B1. I Br for all [T]. Assume that F has bounded diameter || - y1lo S DoO, Vx, y F and [V(((x)) < Goo for all [T] and x E F. Then for generated using Algorithm 3 we have the following bound on the regret.
D2
D2
T
Biche
av1 + log
R(T)= <
+
llg.tlll (47)
20 B1)
2(1
31
Oe
(1 31)3
Corollary C.1 follows immediately from the above theorem.
Corollary C.1 Setting 31 11 in Theorem C.1
then we have
D2 /T R(T) < 20(1 - 81)
D2.G
aVI+ log
hr, + 2(1 - (11 X²)
Σ 1lgh (1 31)3
(48)
Similarly, the bound above can be considered as better than the regret of SGD when Dd= hT, < Vd and |g..r VdT Duchi al. 2011). which is the
the claims make in Theorem 4.2 Another important observation is that Theorem 4.1 also holds here with similar arguments (because the first term almost the same as the first without momentum, the second term is a constant, and the third term is almost the same as well. We provide a similar theorem here.
Theorem C.2 Let (1e) and (he) be the sequences obtained from Algorithm 3 a, = 1, 1 = B1e -1x-1, for all E [T). Assume that F has bounded diameter || ylloc S Dx.. Vz, y and [=)] < G.e. for all E [T] and x E F. Let (i) Fiz1 be the largest time steps each dimension when his (g..s Then for at generated using Algorithm we have the
a vl/Vl.
19

---

Under review as a conference paper at ICLR 2021
following bound on the regret.
Do
Do Goc
d
R(T)= S 20x11=
B1)
60 Ting
Tm,
+ 2(1 Bi)(1 X2)
(1 B1
)
Σ
1 + log Tim mm 0 12: 1la
i=1
1=1
+ (1 31)3
Ti,
(i)
log(
T
(
0g co)
Tm,
(49)
The above regret bound can be considered as significantly better than O(VT) because it mostly depends on the time steps Tm, instead of the number of time steps T. Given distribution of gradients, is possible that Ti. 's are much smaller than T, and hence the regret is much smaller than common adaptive optimizers. The regret at most O(VT), which is the same as AdaGrad and AMSGrad.
(8)
We also conducted experiments to examine the effect of momentum on the convergence and per- formance of our algorithm on CIFAR-10. shown figure 4 the choice of 31 did not affect the convergence rate or the performance of AMX too much.
AMX, 8, 0.9
90
95
AMX, 8, 0.5
85
Train Top-1 Accuracy
AMX, 8, =0
Top-1 Tes- Accuracy
80
75-
85
70-
80
Test
65
60.
AMX, 8, =0.9
AMX, 8, =0.5
55
AMX, 8j =0
70
10000
20000 30000 40000 50000
60000
50
10000 20000 30000 40000
50000
60000
Iterations
Iterations
(a) Training Top-1 Accuracy
(b) Testing Top-1 Accuracy
Figure 4: Training and testing Top-1 accuracy curve on CIFAR-10 with different momentum parame-
ters 31
C.I PROOF OF REGRET BOUND OF AMX WITH MOMENTUM
C. PROOF OF THEOREM 4.2 AND THEOREM C.I
(001). we provide the proof of regret bound in Theorem 4.2 and Theorem C.1 Note that Algorithm ii special case of algorithm Therefore we only need
Proof. Following the proof by Reddi
to prove Theorem and Theorem (.2 can be directly inferred by taking B,, and change by
2. By the definition of the projection operation IT.H, we know that
r+t1 II (a, 04 H, mm) argmin 1/ (a ( mm))ll
(50)
Using Lemma in Reddi et al. 2018 with direct substitution of 21 (#+ - -O,H, m,) Q H. and = x² for xt E F. the following inequality holds:
(u1 uz) 2 |H. (xe41 - =² < |77 (xr O, T.HHHmm. x² x²)l1
-|HH!// (I: x² =² + af H. 1/2 m2
1/2m//2m 20, , (Ir xx")
= -| x² x²')'' I1 + o H 1/2 1/2mm/ m1 231 + +11 Brdge, (x1 - -x")) (51)
20

---

Under review as a conference paper at ICLR 2021
where the first equality is due to II F Ji,, (x*) xx. Rearrange the last inequality, obtain
(1 - (g. (I) - x²)) -
1
|| |
(2) (
x²) x²)ll |1 (x141 - x²)]²] + at Bi (m
2 H 1/2 mill
20x
- (st-x"))
|| 1/ (xts -xx)) x12) || (0141 - x -0)))²+++
at
H 1/2 m 11?
20x
2
B1 | 1/2 m 1|2
B1t
|| 1/2
-x)="")
(
20x
(52)
The second inequality is from applying the Cauchy-Schward and Young's inequality. By the convexity of fo and Lemma C.1 and Lemma C.2 we have
T
Σ f((x))) - fe(x") S
Srs (xt x²))
t=1
T
1
|1
1/2 (xt = (It+1
(1141 -
-2')
11, 1/2
mel?
20r(1 81c)
2(1 B1t))
1=1
+
11,, 1=-112 11+
31
11, 1/2 (IIe x²)11
2(1
B1x)
20r, Bit)
D
hT,
T
811
11,
1/2
(xx,(xxx
x²)11
avl + log T
1g..2
20T -B1) i=1
20v
[1 B1)
(1 31)3 1=1
t=1
Dx2
1
0 1 log T
hT,
Sic(Er,1 x/) +
1
20T - -11)
20x (1 - B1)
(1 31)3
Doc2
D2
T
Birher
av avI log T
d
$ 2aT (1 - -B1)
Σ
hT +
1g1.1,
2(1 (1)
ag
(1 - 31
i=1
t=1 i=1
D2
T
Biches
avI + log T
20T -1)
2(1
B1)
Oe
(1 31
i=1
t=
1=1
(53)
To obtain the regret bound in 4.2 above bound, and the regret bound follows
take 31 0 and
a/2 by equivalence in A.1 in the
D2
VT
R1 <
hrs + 2 + log T Σ |11.
(54)
C.1.2 AUXILLARY LEMMAS
Lemma C.1 For the parameter settings and conditions assumed in Theorem C.1
we have
B
H,, 1/2 mel2 5 av log T
Σ
(55)
2( 3ie)
31
where C is a constant.
Proof: We first analyze with the following process directly from the update rules, note that
mT.
Σ
B1y
(((T-
1=1
(56)
h7 = max(
h 1,5 gt.))
T
21

---

Under review as a conference paper at ICLR 2021
T
H
1/2 mmpl 1|
04/| H 1/2 m//21 + oT
M .i hT
i=1
d
j== (1 31) [T= 1 - 1)955)
Σ
1/2mm/11 m2Il² +a
1/2
Tmaxx
T-1 12 1,8 1 ,7,))
T
d
1== 11= 8I(T b+t1) ( Ez1(1 (1 (1, -1(T-
H
1/2
mml? +a
1, 97 Tmax ( 1
i=1
d
j-ر Sf (2
T
T
34 97.1)
Hi
1/2 "mll" +a +
j-
Tmax T 119 1, PT
1=1
d
2j=1 8---330 S935
anll H 1/2 1111mmml mm + (1 - 31)
Tmaxx 2 - 1, of
d
T
Bf
-3
93,
H 1/2 m/2me112 +
a
(1-B1 31)
j=1
T
T
oullH, 1/2 m+11 +
(1 31)
vs
(57)
where the first inequality is from the Cauchy-Schward incquality. The second inequality is due to the fact that 31x S B1, vI. The third inequality follows from ΣØ= 8f S 1/((1 -31) and that
1 315 S 1. The fourth one comes from the fact that hī 2 " +-1 1,. and that h2, 2 L... Therefore
d
3 19
Σ ag ||l H 1/2
94
a
<
31)
Vj
(1 B1)
vi
1=1
1=1
i=
j=1
i=1 (=1
j=1
d
T
d
T
a
9t.i
a
Mt.l
[1
31)
(1 (1- 11-1))
Vl
(58)
i=1
[=1
j=t
1=1 [=1
< d
a
1gnerall2
T
a/l + log T
Σ
11
(1 31
t
(1 - 31
The second equality is from rearranging the order of summation. The third inequality comes from the fact that -T. < 1/(1 -11). The second last inequality is due to the Sauchy-Schwerr inequality.
Lemma C.2 For the parameter settings and conditions assumed in Theorem C.1
we have
T
D² 20r
H 1/ (x+ - x²)1²- -") (5++1 - 22
-x*)11]]
<
hrs
(59)
i=1
22

---

Under review as a conference paper at ICLR 2021
Proof:
By the definition of L2 norm, since
had ai
Ar-1d 0-11
by the conditions in the problem (4)
T
|1
1/2 (2x
(1++1 - =²] | x²)l1
T
|H, (xr x11
11 1-1
1/2
x²) x²11
x2"112+ | |H|/ 11112 (21
ac-1
2=
hed (#t,i -x,)²
h 11-1.1 1.6 (x1,5 - 22)2
11,((1,5 xx/² +
(60)
a1 i=1
ar
a1-1
i=
he.s h1-1,
Σ
11,((11,5
+
(Fe x²?²
a1
at
a--1
D2
-
hT,
2αT
where the first inequality is deleting the last negative term in the summation. The last inequality is from the telescopic summation and the bounded diameter that || x"I Doo
D EXPERIMENT DETAILS AND MORE EXPERIMENTS
For all the algorithms, we used the default momentum hyper-parameters. that is 7 = 0.9 for SGDM, (0.9, 0.999) for Adam and AMSGrad, and (31,c) (0.9, 1) for AMX in algorithm 3 The small number e is set to be le-8 to avoid division by zero.
D.1 SYNTHETIC EXAMPLE
For the synthetic example in section we used 19t.s| 1 19.,l. Vi, and 191.al = 0.01 across all the dimensions. The dimension size set be d = 3, and the step sizes are set to = 0.5, o; = a/vi for all the algorithms. The design of step sizes is much larger than what usually use in real applications, because it makes the increment in the regret bound AMX much more visible. The increment in the first term of AMX is already zero, and the increment in the second term is very small. we use smaller step size a,, we can barely see any increment in the regret bound of AMX in the figures. The syper-parameter of AMSGrad is set to be 32 0.999.
D.2 IMAGE CLASSIFICATION
For CIFAR-10 and CIFAR-100, the 32 32 images zero-padded the edges with 4 pixels on each margin and randomly cropped and horizontally flipped to generate the input. The input images also normalized using the dataset mean and standard deviation. For the step sizes CIFAR-10. we searched over {1c-4, 5e-4, 1e-3, 2e-3, 3e-3, 5e-3, le-2, 2c-2} for all the udaptive methods and found that 5e-3 works the best for AMX. The best step sizes for AdaGrad, Adam, AMSGrad were le-2, 1e-3, 1e-3 respectively. For SGDM, the best step size was lc-1. We also grid-searched the weight decay on 11 5e-2, le-2, 5e-3, 1e-3, 5e-4, le-4). On CIFAR-10. le-1 weight decay worked the best for Adam and AMSGrad and 5e-2 worked the best for AMX. 5e-4 worked the best for AdaGrad and SGD. On CIFAR- 100, all adaptive algotithms worked the best when the weight decay was le-1, but SGD still needed the 5e-4 weight decay. The increments in the first term and the second term of the regret bounds are plotted in Figure ((a) and (bb) On CIFAR-10, 100 the step sizes different algorithms were decreased by factor of 0.1 at the the 100th and 150th epoch. On CIFAR- 100, the step sizes were decreased by a factor of 0.2 at the 60th, 100th, and 160th epoch.
D.3 IMAGE SECMENTATION
The Deeplab-ASPI model implemented by Kazutol011 (2016) was used in this task. We followed their settings and reported the mean loU values averaged over three independent runs. The model
23

---

Under review as a conference paper at ICLR 2021
1.8
0.5
AMX
AMX
AdaGrad
AdaGrad
1.4
AMSGrad
0.4
AMSGrad
1.2
Regret
100
Regret
0.2
0.6
0.4
0.1
0.0
0.0
2000
4000
6000
8000
1000C
2000
4000
5000
8000
10000
Iterations
Iterations
(a) The First Term of the Regret Bound
(b) The Second Term of the Regret Bound
Figure 5: The first and the second term of the regret bound in equation (2) with the diameter Dr,oc replaced by Doo = 2. As can be observed, the first term of AMX stops increasing after т, which is the first time step. The other algorithms do not have such nice property. Therefore, even if the second term of AMX is slightly larger than the second term AdaGrad, the overall regret of AMX is much smaller. That means AMX converge much faster than AdaGrad and AMSGrad in the example.
was pretrained on the MS-COCO dataset (Lin et al. 2014). We did not use the CRF post-processing technique. We tried the initial step sizes [5e-3, Ie-3, 5e-4, Ic-4, 5e-5, 3e-5, le-5, 5e-6) } for all the optimizers and we found that le-6 worked the best for Adam and AMSGrad. 5e-5 was the best for AMX and le-3 was the best for SGD, Similar the experiments on CIFAR-IO, 0.1 weight decay was applied to Adam and AMSGrad. 5e-2 weight decay was applied to AMX and 5e-4 weight decay was applied SGDM.
D.4 LANGUAGE MODELING
We trained three layer LSTMs using the instructions provided by Kazuto (0016). Specifically, the LSTMs consisted of 200 embedding size and 1 hidden units. For the dropout probabilities and the batch size, we followed the default values. A 1.2c-6 weight decay was applied to all the algorithms and we tuned over {lc-4, 5c-4, le-3, 2e-3, 3e-3, 4e-3, 5c-3, le-2, 5e-2] for the initial step sizes. We found that the algorithms were not very sensitive to the initial step sizes, and we reported the results of 2e-3 for Adam and A.MSGrad, 3e-3 for AMX, and le-2 for AdaGrad, which were the best results among all the possible step sizes. We decayed the step size by factor of 0. at the 300th and 400th epochs.
D.5 NEURAL MACHINE TRANSLATION
We used the basic implementation of the attentional neural machine translation model by pyccin (2018) and followed their settings. The hidden size of the LSTM was 256 and the embedding size was 256 Label smoothing was set be 0. and the drop out probability was 0.2. We tuned over (5e-2, le-2 5e-3, 1e-3, 5e-4, le-4) step sizes for all the adaptive optimizers and found that similar to CIFAR-10 10, le-3 worked the best for Adam and AMSGrad and 5c-3, 1e-2 were the best step sizes for AMX and AdaGrad respectively. We averaged the BLEU scores on the IWSLT' 14 German to English dataset (Ranatoo et al. 2015) over three independent runs and reported them in table 2
D.6 EMPIRICAL STUDY OF THE
The hyper-parameter & plays an important role in our class of AMX algorithms. We conducted an empirical study on some of the designs of e and compared the performance of the corresponding algorithms. We compared the designs c = 0.5. 0.1, 1/v7, 1/t on CIFAR-10 10 and reported their top-1 accuracy in Figure 0 and Table All the algorithms were trained using the same settings as Appendix D.2 with the same initial step size 5e-4. As observed, changing the constant e; to 0.1 and
24

---

Under review as a conference paper at ICLR 2021
0.5 did not affect the convergence speed or the final accuracy too much, which meant the performance was not sensitive to the value of q.. However, 4 11/v and e =1/l resulted in slower convergence and worse performance, meaning that these designs were not preferred. These observations also correspond to our claims in section A.55 i.c. despite that these designs make the first term in Theorem 2.1 even smaller, they also make the second term much larger so that the algorithm becomes slower.
103
Table 3: Testing Top-1 Accu- racy CIFAR-10 with differ- ent designs of C₃. The results were averaged over 3 indepen- dent runs.
ARXX
Trur (ccunoc)
ANX m1101
60
AROX
APXX -IVE
AMX o -1
The The
02
AMX 0.5
25
AMX -1
11
Ct
ACC.
o
-1/
79
C =
92.42 + 0.06
170
10010
23850
1000 10010
53000 M003
10320
20320
33000
10002
00302
Ct 0.5
92.35 + 0.08
Ct 0.1
92.46 + 0.05
(a) Training Top-1 Accuracy
(b) Testing Top-1 Accuracy
C 1/vl
92.15 + 0.06
C 1/1
91.73 + 0.13
Figure 6: Training and testing Top-1 accuracy curve on CIFAR-10 with
different designs of et.
25


Reviews:
[{"review_id": "repzzpz3Voo", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a new motivation for designing the proximal function of adaptive algorithms. This leads to a new class of adaptive algorithms that achieves marginal optimality and converges faster than existing algorithms in the long term. The claims are substantiated empirically for a wide variety of deep learning tasks as well as empirically. I have no complaints about the comprehensive empirical evaluations and the quality of the theoretical results (if correct). I did not have time to go through all the proofs in the supplementary materials.\n\nI find that the intuition and motivation for the proposed class of methods is generally clear. It seems, however, that this method (as described in Section 3) is a bit ad hoc as the authors are trying to examine a *one-step increment* of the regret. Given from what we know of momentum methods in which the exploitation of longer-term memory may be beneficial, perhaps the authors can comment on whether looking at longer step windows of the regret would be beneficial. \n\nFurthermore, the reviewer is wondering whether there's any benefit to going beyond the use of the *diagonal* proximal function. Would a non-diagonal and more dense proximal term be beneficial?\n\nCorollary 4.1 seems overly conservative because the authors use \\tau, the max of the \\tau_{m_i}'s to control the overall regret bound. Also, it would be good to avoid the use of the O notation here to show the dependence of the regret (or at least discuss it) on the other parameters of the problem (e.g., the diameter of the problem). ", "extra_scores": {}, "extra_text": {}}, {"review_id": "asZrvZcFVNS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new class of adaptive algorithms inspired by finding an optimal proximal function of adaptive algorithms. They provide a theoretical analysis of the new method showing that it would potentially improve the regret bound of current algorithms. Finally, the proposed method is empirically matched with or superior to other popular algorithms on different tasks. \n\nOverall, the method is novel and backed up by some empirical results. However, I have the following concerns mainly on the theories. \n\n- The theories require a bounded domain, yet it is not justified. \n- \"*The AMX algorithm is at least as fast as AdaGrad and AMSGrad under the same assumptions*\": The regret of AdaGrad is ($\\frac{D^2}{\\alpha} + \\alpha)\\sum_{i=1}^d ||g_{1:T,i}||$ under the same setting. While for AMX, the construction of h_t potentially decreases the first term in the regret but also brings an extra log factor to the second term.  In fact,  the second term in Theorem 4.1 is ~$\\sum_{i=1}^d(\\sqrt{1+\\log\\tau}||g_{1:\\tau,i}||)$.  Overall, since that there is no clue how large $\\tau$ is, the regret of AMX may be worse than $\\sum_{i=1}^d||g_{1:T,i}||$ when $\\tau$ is close to $T$. Indeed,  the bound in Theorem 4.2 is worse than AdaGrad by a log term. \n- \"*We emphasize that a small $\\tau$ is not an assumption on the gradient distribution, but rather a condition that on satisfied.*\": There is no citation for this statement nor evidence showing that it is actually happening in the real training process. There is only a specific example to show $\\tau$ can be 1, but I'm still not convinced.  Small $\\tau$ is the key point to show the potential superiority, it would be better to illustrate how $\\tau$ behaves in real training.    \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "PS_WIgIX68e", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n \nThe paper provides a new family of adaptive optimization algorithms by designing the proximal function of the adaptive algorithms to minimize marginal regret bound. The paper shows that the regret bound is better than existing algorithms in a sense. The paper also presents simulation study on a variety of domains that compare the proposed algorithms with other commonly used algorithms.\n\n\n##########################################################################\n\nReasons for score: \n \nOverall, I vote for rejecting. I appreciate the clear explanation of the motivation behind considering marginal regret bound. However, I have a few concerns outlined in the section below.\n\n##########################################################################\n\nPros: \n \n1. The paper is easy to follow. The idea of minimizing marginal regret bound is novel and interesting.\n \n2. The paper provides rigorous theoretical proofs for many claims, but also generalizes in a clever way (AMX generalizes Equation 5) to potentially enhance performance.\n \n3. Th paper provides experiments on a variety of tasks in different domains including computer vision and language. The results are very encouraging, as the proposed method is shown to converge either faster or better in most cases compared to other commonly used adaptive algorithms. The paper explains in details how the experiments are done, including relevant parameters and training procedure.\n\n\n##########################################################################\n\nCons: \n\n1. The paper shows better bound by introducing a quantity $\\tau$ which denotes the largest time steps something happens, and then Corollary 4.1 shows regret bound is roughly $\\sqrt{\\tau}$. Since $\\tau$ is at most T, the paper claims that the bound is better than bounds for other adaptive algorithms, which is simply $\\sqrt{T}$. However, I am not convinced that this can only be done for AMX, but not for other adaptive algorithms like Adam or AMSGrad. In other words, what is preventing us from defining $\\tau$ in a similar or different way, and then show a bound in terms of $\\tau$ for Adam or AMSGrad?\n\n2. The main theoretical insights is that AMX can converge faster than other adaptive algorithms. However, in many experiments AMX did not converge faster than Adam or AMSGrad (e.g. Figure 2). Instead, we often see that the test performance of AMX is better than other adaptive algorithms, i.e., AMX converges to a solution that generalizes better. In this sense, there is a misalignment between theory and practice.\n\n3. The baseline adaptive algorithms (SGDM, AdaGrad, AMSGrad, Adam) are all very commonly used but proposed at least two years ago. It would be better if the paper can show comparison with some more recently proposed adaptive algorithms, like Radam or AdaBound.", "extra_scores": {}, "extra_text": {}}, {"review_id": "PDJC_M4XN9R", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a variant of AdaGrad which optimizes greedily the increase of the regret per trial. More precisely, it optimizes diagonal matrices which adaptively determines the regularizer of the composite mirror descent updates. The experimental results shows that the convergence speed is comparable to other state-of-the-arts, but often it achieves better test performances. \n\nThe proposed update makes sense and seems natural. However, the modification seems a bit incremental. The authors pointed out the proposed algorithm achieves potentially better regret bound than typical \\sqrt{T} and this is the first algorithm to do so. I am afraid that that is not correct. In the online convex optimization literature, there are bunch of researches on learning on \"easy data\", which aims to obtain better worst case regret bounds by taking advantage of “easyness” in the data. In fact, there are many papers on that topic (see, e.g., NIPS workshop on Learning faster from easy data II in 2015 and following work). \n\nIt is not clear to me why the proposed method achieves better test performances in the experiments. The authors should try to explain why. A reasonable explanation might increase the technical contribution.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "2NnuTgG-LSv", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThis paper introduces a new online convex optimization algorithm that operates in via the reduction to online linear optimization in which the regret is bounded by $\\sum_{t=1}^T \\langle g_t, x_t - u\\rangle$ where $g_t$ is the gradient of the t^th loss at $x_t$. The algorithm is based on online mirror descent with non-decreasing quadratic regularizers $x^\\top H_t x$, using the update $x_{t+1} = argmin_x \\langle g_t, x \\rangle + (x-x_t)^\\top H_t(x-x_t)$ (or, equivalently using the terminology in the paper, $argmin \\langle g_t, x_t\\rangle /\\sqrt(t) + (x-x_t)^\\top H_t(x-x_t)$ where we replace $H_t$ by $H_t/\\sqrt{t}$. The analysis is restricted to diagonal $H_t$, for which we can break the regret into a sum of $d$ 1-dimensional problems, so it suffices to do the analysis in the scalar case. The idea is to break out the standard analysis of mirror descent regret as the sum over all t of $D^2(H_t - H_{t-1}) + g_t^2 H_t^{-1}$, where $D$ is the $\\ell_\\infty$ diameter of the domain, and then choose $H_t$ to minimize each of these terms greedily subject to the non-decreasing condition. A regret bound is provided for this algorithm that achieves worst-case $\\sqrt{T}$ regret, but in cases in which the gradients are small, the regret is much better. By employing this strategy on a per-coordinate basis one can obtain an adagrad-esque regret bound.\n\nAs far as I can tell, the algorithm is equivalent to the update:\n$$\nx_{t+1} = argmin_x \\langle g_t, x\\rangle + (x-x_t)^2 max_{t’ \\le t} \\sqrt{t’}|g_t’|\n$$\nWhere I remove the composite term and consider 1-d problems for simplicity.\n\nThe analysis seems correct here, and the idea is a good approach. However, I am a bit concerned about the quality of the theoretical results obtained. In particular, it is extremely unclear to me that the main regret bound in Theorem 4.1 actually offers any advantage whatsoever over AdaGrad. In the paragraphs following the result, the authors offer the example in which $g_t = O(1/\\sqrt{t})$. The authors then observe that in this setting, AdaGrad will obtain $O(\\sqrt{\\log(T)})$ regret. They then also note that Theorem 4.1 obtains regret $\\ll \\sqrt{T}$. This is true, but my reading of theorem 4.1 is that it will have $O(\\log(T))$ regret, which is *worse* than AdaGrad by a $\\sqrt{\\log(T)}$ factor.\nI am not sure what is happening in Figure 1- my understanding is that this is plotting the analytical regret bound which seems actually smaller for AdaGrad using the provided example. I suspect the learning rates for adagrad are not tuned properly, but perhaps I am missing something.\n\nI have been unable to conceive of any sequence of gradients in which theorem 4.1 actually outperforms AdaGrad, and it is very easy to find sequences in which it does much worse (e.g. simply reverse the sequence of gradients in the provided example). It is, however, plausible to me that in reasonable settings in which the gradients decrease over time one might expect the bound to be within a constant (or maybe a log factor) of AdaGrad’s bound.\n\nLooking at the analysis, I suspect that this is a fundamental issue with the approach of bounding bregman divergences based on the diameter of the domain. Once we commit to this, it is clear that the final regret bound must be at least on the order of $D^2H_T$ by telescoping sum, since $H_T$ is increasing. Further, the $\\sum_t g_t^2H_t^{-1}$ term can be lower-bounded by $\\sum g_t^2 H_T^{-1}$. Clearly, the minimizing value for $H_T$ here is then $D\\sqrt{\\sum g_t^2}$ to yield a bound of O(D \\sqrt{\\sum_t g_t^2}), which is exactly what AdaGrad does.\n\nI am willing to believe that the analysis can be improved here, but I am pretty sure that one cannot due so by bounding the Bregman divergences with the diameter. This leads to a pleasant telescoping sum, but I think AdaGrad may already optimize that style of analysis.\n\nAs for the empirical results, these seem a bit more promising so perhaps there is some improved analysis that could be made. There could be a few clarifications here though: is the value for $\\alpha_t$ set to $\\alpha/\\sqrt{t}$ in these experiments, or is it tuned via some other schedule? In analysis of Adam and AMSGrad, the authors typically use the $\\alpha/\\sqrt{t}$ approach, but in practice I think this is not usually employed. If $\\alpha_t$ is set via some other schedule, and momentum is used as well, then it becomes unclear if the $\\alpha$ tuning and the momentum is not what is providing the gain over AdaGrad rather than other differences.\n\nI am less expert in evaluating the significance of the final numbers in the empirical study. They do seem relevant, but frankly I feel that the theoretical discussion is currently dragging the paper down quite a bit.\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a new online convex optimization algorithm that uses per-coordinate learning rates. The learning rates are changed over time using information coming from the gradients. A regret upper bound is proved and the algorithm is empirically validated on deep learning experiments.

While the analysis is in principle correct, it does not seem to provide any advantage over the guarantees of similar algorithm, for example the mirror descent version AdaGrad with diagonal matrices. Also, despite the intuition of the authors, the reviewers have found that the approach used in the analsysis is fundamentally bounded to give a worse guarantee than AdaGrad. Overall, the theoretical contribution appears to be not sufficient.

On the empirical side, the experiments failed to convince the majority of the reviewers that the algorithm has a significative gain over similar algorithms.

More generally, this paper suffers from the same problem of many other similar papers: There is a complete disconnect from the theory proven under restrictive assumptions (convexity, bounded domains, no stochasticity) and the experiments (non-convex functions, no projection on bounded domain, stochastic setting). Unfortunately, the deep learning literature is full of such papers, but the community should strive to do better and substantially raise the quality of field. In this view, I strongly suggest to the authors to try to improve the theoretical contribution, for example, trying to prove a convergence guarantee of the gradients to 0, rather than focusing on regret upper bounds. Such analysis would also suggest better ways to design new optimization algorithms better suited to non-convex problems.
Decision: Reject