Adaptive Gradient Methods Converge Faster with Over-Parameterization (and you can do a line-search)
Authors: Sharan Vaswani
Issam H. Laradji
Frederik Kunstner
Si Yi Meng
Mark Schmidt
Simon Lacoste-Julien
Venue:  (2021)
Keywords: Adaptive gradient methods
Over-parameterization
Stochastic line-search
Momentum

Abstract: Adaptive gradient methods are typically used for training over-parameterized models capable of exactly fitting the data; we thus study their convergence in this interpolation setting. Under an interpolation assumption, we prove that AMSGrad with a constant step-size and momentum can converge to the minimizer at the faster $O(1/T)$ rate for smooth, convex functions. Furthermore, in this setting, we show that AdaGrad can achieve an $O(1)$ regret in the online convex optimization framework. When interpolation is only approximately satisfied, we show that constant step-size AMSGrad converges to a neighbourhood of the solution. On the other hand, we prove that AdaGrad is robust to the violation of interpolation and converges to the minimizer at the optimal rate. However, we demonstrate that even for simple, convex problems satisfying interpolation, the empirical performance of these methods heavily depends on the step-size and requires tuning. We alleviate this problem by using stochastic line-search (SLS) and Polyak's step-sizes (SPS) to help these methods adapt to the function's local smoothness. By using these techniques, we prove that AdaGrad and AMSGrad do not require knowledge of problem-dependent constants and retain the convergence guarantees of their constant step-size counterparts. Experimentally, we show that these techniques help improve the convergence and generalization performance across tasks, from binary classification with kernel mappings to classification with deep neural networks.

Under review as a conference paper at ICLR 2021
ADAPTIVE GRADIENT METHODS CONVERGE FASTER WITH AVER-PARAMETERIIZAION (AND YOU CAN DO A LINE-SEARCH)
Anonymous authors Paper under double-blind review
ABSTRACT
Adaptive gradient methods are typically used for training wver-parameteizee models capable of exactly fitting the data; we thus study their convergence in this interpolation setting. Under an interpolation assumption, with a constant step-size and momentum can converge to the minimizer at the faster O(I/T) rate for smooth, convex functions. Furthermore, in this setting, we show that AdaGrad can achieve an O(1) regret in the online convex optimization framework. When interpolation only approximately satisfied, we show that constant siep-size AMSGrad converges to neighbourhood of the solution. On the other hand, we prove that AdaGrad is robust to the violation of interpolation and converges to the minimizer at the optimal rate. However, we demonstrate that even for simple, convex problems satisfying interpolation, the empirical performance of these methods heavily depends on the step-size and requires tuning. We alleviate this problem by using stochastic line-search (SLS) and Polyak's 's step-sizes (SPS) help these methods adapt the function's 's local smoothness. By using these techniques, we prove that AdaGrad and AMSGrad do not require knowledge of problem-dependent constants and retain the convergence guarantees of their constant step-size counterparts. Experimentally, we show that these techniques help improve the convergence and generalization performance across tasks, from binary classification with kernel mappings to classification with deep neural networks.
prove that AMSGrad
INTRODUCTION
Adaptive gradient methods such as AdaGrad (Duchi et al., 2011), RMSProp (Tieleman & Hinton, 2012), AdaDelta (Zeiler, 2012), Adam (Kingma & Ba, 2015), and AMSGrad (Reddi et al., 2018) are popular optimizers for training deep neural networks (Goodfellow et al., 2016). These methods scale well and exhibit good performance across problems, making them the default choice for many machine learning applications. Theoretically, these methods are usually studied in the non-smooth, online convex optimization setting (Duchi et al., 2011; Reddi et al., 2018) with recent extensions to the strongly-convex (Mukkamala & Hein, 2017; Wang et al., 2020; Xie al., 2020) and non-convex settings (Li & Orabona, 2019; Ward et al., 2019; Zhou et al., 2018; Chen et al., 2019; Wu et al., 2019; Défossez et al., 2020; Staib et al., 2019). An online- reduction gives guarantees similar to stochastic gradient descent (SGD) in the offline setting (Cesa-Bianch) et al., 2004; Hazan & Kale, 2014; Levy et al., 2018).
However, there are several discrepancies between the theory and application of these methods. Although the theory advocates for using decreasing step-sizes for Adam, AMSGrad and its vari- ants (Kingma& & Ba. 2015; Reddi et al., 2018), constant step-size is typically used in practice (Paszke et al., 2019). Similarly, the standard analysis of these methods assumes a decreasing momentum parameter, however, the momentum is fixed in practice. On the other hand, AdaGrad (Duchi et al., 10 has been shown to be "universal" as it attains the best known convergence rates both the stochastic smooth and non-smooth settings (Levy et al., 2018), but its empirical performance is rather disappointing when training deep models (Kingma & Ba, 2015). Improving the empirical performance was indeed the main motivation behind Adam and other methods (Tieleman & Hinton, 2012: Zeiler, 2012) that followed AdaGrad. Although these methods have better empirical performance, they are not guaranteed converge to the solution with constant step-size and momentum parameter.

---

Under review as a conference paper at ICLR 2021
Another inconsistency is that although the standard theoretical results are for non- non-smooth functions, these methods are also extensively used in the easier, smooth setting. More importantly, adaptive gra- dient methods are generally used to train highly expressive, large wver-parameterized models (Zhang et al., 2017; Liang & Rakhlin, 2018) capable of interpolating the data. However, the standard theoreti- cal analyses do not take advantage of these additional properties. On the other hand, a line of recent work (Schmidt& & Le Roux. 3013; Jain et al., 2018: Ma et al., 2018; Liu & Belkin, 2020; Cevher & Vü, 2019; Vaswani et al., 2019a;b; Wu et al., 2019; Loizou et al., 2020) focuses on the convergence of SGD in this interpolation setting. In the standard finite-sum case, interpolation implies that all the functions in the sum are minimized at the same solution. Under this additional assumption, these works show SGD with a constant step-size converges to the minimizer at a faster rate for both convex and non-convex smooth functions.
In this work, we aim to resolve some of the discrepancies in the theory and practice of adaptive gradient methods. To theoretically analyze these methods, we consider simplistic setting smooth, convex functions under interpolation. Using the intuition gained from theory, we propose better techniques to adaptively set the step-size for these methods, dramatically improving their empirical performance when training over wer-parameterize models.
1.1 BACKGROUND AND CONTRIBUTIONS
Constant step-size. We focus on the theoretical convergence of two adaptive gradient methods: AdaGrad and AMSGrad. For smooth, convex functions, Levy et al. (2018) prove that AdaGrad with a constant step-size adapts to the smoothness and gradient noise, resulting in an O(1/r 4/VT) convergence rate, where T is the number of iterations and Ç² is a global bound on the variance in the stochastic gradients. This convergence rate matches that of SGD under the same setting (Moulines & Bach, 20.1). In Section 3, we show that constant step-size AdaGrad also adapts to interpolation and prove an 0(/r + %/VT) rate, where a is the extent to which interpolation is violated. In the over- wver-paametterzeed setting, o² can be much smaller than ç² (Zhang & Zhou, 2019), implying a faster convergence. When interpolation is exactly satisfied, x² O, we obtain an O(/r)) rate, while ç² can still be large. In the online convex optimization framework, for smooth functions, we show that the regret of AdaGrad improves from O(VT) to O(1) when interpolation is satisfied and retains its OlvT ((VT)-reege -regret guarantee in the general setting (Appendix C.2). Assuming its corresponding preconditioner remains bounded, we show that AMSGrad with a constant step-size and constant momentum parameter also converges at the rate O(Yr)) under interpolation (Section 4). However, unlike AdaGrad, it requires specific step-sizes that depend on the problem's 's smoothness. More generally, constant step-size AMSGrad converges to neighbourhood of the solution, attaining an Ol/r d²) rate, which matches the rate of constant step-size SGD in the same setting (Schmidt Le Roux, 2013; Vaswani et al., 201 9a). When training wer-parameterized models, this result provides some justification for the faster (O(F/) vs. O(//T)) convergence of the AMSGrad variant typically used in practice.
Adaptive step-size. Although AdaGrad converges at the same asymptotic rate for any step-size (up to constants), it unclear how to choose this step-size without manually trying different values. Similarly, AMSGrad is sensitive to the step-size, converging only for a specific range in both theory and practice. In Section 5, experimentally show that even for simple, convex problems, the step-size has big impact on the empirical performance of AdaGrad and AMSGrad. To overcome this limitation, we use recent methods (Vaswani al., 2019a; Loizou et al., 2020) that automatically set the step-size for SGD. These works use stochastic variants of the classical Armijo line-search (Armijo, 1966) or the Polyak step-size (Polyak, 1963) in the interpolation setting. We combine these techniques with adaptive gradient methods and show that a variant of stochastic line-search (SLS) enables AdaGrad to adapt to the smoothness of the underlying function, resulting in faster empirical convergence, while retaining its favourable convergence properties (Section 3). Similarly, AMSGrad with variants of SL.S and SPS can match the convergence rate of its constant step-size counterpart, but without knowledge of the underlying smoothness properties (Section 4).
Experimental results. Finally, in Section 5, we benchmark our results against SGD variants with SLS (Vaswani et al., 2019b), SPS (Loizou et al., 2020), tuned Adam and its recently proposed variants (Luo et al., 2019; Liu et al., 2020). We demonstrate that the proposed techniques for setting the step-size improve the empirical performance of adaptive gradient methods. These improvements are consistent across tasks, ranging from binary classification with a kernel mapping to multi-class classification using standard deep neural network architectures.
2

---

Under review as a conference paper at ICLR 2021
2 PROBLEM SETUP
We consider the unconstrained minimization of an objective f I + R with a finite-sum structure, fw)) Σi= f1 In supervised learning, represents the number of training examples, and fi is the loss function on training example i. Although we focus on the finite-sum setting, our results can be easily generalized the online optimization setting. The objective of our analysis is to better understand the effect of the step-size and line-searches when interpolation is (almost) satisfied. This is complicated by the fact that adaptive methods are still poorly understood; state-of-the-ar analyses do not show an improvement over gradient descent in the worst-case. To focus on the effect of step-sizes, we make the simplifying assumptions described in this section.
We assume f and each fi are differentiable, convex, and lower-bounded by f and f respectively. Furthermore, we assume that each function f. in the finite-sum sum smosth,, implying that f is L -smothh, where Liax = max; L, We also make the standard assumption that the iterates remain bounded ball of radius around a global minimizer, ||wss - w"1 S D for all wr (Ahn et al., 2020). We remark that the bounded iterates assumption simplifies the analysis but is not essential, and similar to Reddi et al. (2018); Duchi et al. (2011); Levy et al. (2018), our theoretical results can be extended to include projection step. We include the formal definitions of these properties (Nemirovski et al., 2009) in Appendix A.
The interpolation assumption means that the gradient of each fi in the finite-sum converges to zero at an optimum. If the overall objective f is minimized at w", Vf(w")= = O. then for all f; we have fi(w") 0. The interpolation condition can be exactly satisfied for many over-parameterizee machine learning models such as non-parametric kernel regression without regularization (Belkin al., 2019; Liang & Rakhlin, 2018) and weertparameterized deep neural networks (Zhang al., 2017). We measure the extent to which interpolation is violated by the disagreement between the minimum overall function value f and the minimum value of each individual functions ft. = - f;'] E [0, oo) (Loizou et al., 2020). The minimizer of f need not be unique for o² to be uniquely defined, as it only depends on the minimum function values. Interpolation is said to be exactly satisfied if o² = 0, and we also study the setting when o² > 0.
For preconditioner matrix Ag and a constant momentum parameter B E [0, 1). the update for a generic adaptive gradient method at iteration & can be expressed as:
Wk++1 Wk T/k A mm :
my -:m=-mm + (1 3) (wx)
Here, Vi (wx) is the stochastic gradient of a randomly chosen function fú,- and T7 the step-size. Adaptive gradient methods typically differ in how their preconditioners are constructed and whether or not they include the momentum term Bm4-1 (see Table for a list of common methods). Both
Table 1: Adaptive preconditioners (analyzed methods are bolded), with Go = and 31, B2 E [0, 1). practice, a small c/ is added to ensure A& > 0. *: We use the PyTorch implementation in experiments which includes bias correction.
Optimizer
G
(V. = (ix.
A
B
AdaGrad
Gk-1 + diag V. )
G²/a
RMSProp
B2Gx-1 + (1 32) diag( Vz Vz
//2
0
Adam
(32GR-1 (1- (1-13) (32) diag V, V, ())()((1 85)
G max ( A
_1
AMSGrad
(32Gx-1 (1- 32) diag V. V. ()/(())(1111))))))))))) B5)
G2/23
B1
RMSProp and Adam maintain an exponential moving average of past stochastic gradients. but as Reddi et al. (2018) pointed out, unlike AdaGrad, the corresponding preconditioners do not guarantee that A4+1 > A and the resulting per-dimension step-sizes do not go to zero. This can lead to large fluctuations in the effective step-size and prevent these methods from converging. To mitigate this problem, they proposed AMSGrad, which ensures A 2 Aş and the convergence of iterates. Consequently, theoretical results focus AdaGrad, AMSGrad and other adaptive gradient methods that ensure this monotonicity. However, we also considered RMSProp and Adam in our experimental evaluation.
Although our theory holds for both the full matrix and diagonal variants (where A, is a diagonal matrix) of these methods, we use only the latter in experiments for scalability. The diagonal variants
3

---

Under review as a conference paper at ICLR 2021
perform per-dimension scaling of the gradient and avoid computing the full matrix inverse, their per-iteration cost is the same as SGD, although with an additional ((d) memory. For AMSGrad, we assume that the corresponding preconditioners bounded in an interval [Amin [max] This is a common assumption made in the analysis adaptive methods. Moreover, for diagonal preconditioners, such boundedness property is easy verify, and it is also inexpensive to maintain the desired range by projection. Our main theoretical results for AdaGrad (Section 3) and AMSGrad (Section are summarized in Table 2.
well-behaved in the sense that their cigenvalues
Table 2: Results for smooth, convex functions.
Adapts
Method
Step-size
to smoothness
Rafe
Reference
AdaGrad
Constant
x
0 + %VT)
Theorem
Conservative Lipschitz LS
/
0 + %/V))
Theorem
AMSGrad
Constant
x
0(1/T + +
Theorem 3
AMSGrad w/o momentum
Armijo SLS
/
0 + +
Theorem 4
AMSGrad
Conservative Armijo SPS
0(//++07
Theorem
ADAGRAD
For smooth, convex objectives, Levy al. (2018) showed that AdaGrad converges at rate + ((VT)) where Ç² = sup, E. (ww) of the stochastic gradients. In the over ever-parameterized setting, we show that AdaGrad achieves the O(/r) rate when interpolation is exactly satisfied and a slower convergence to the solution if interpolation is violated.' The proofs for this section are in Appendix C.
is a uniform bound on the variance
Theorem (Constant step-size AdaGrad), Assuming (i) convexity and (ii) Umax--Smothin fa. and (iii) bounded iterates, AdaGrad with a constant step-size v and uniform averaging such that WT E Wk, converges at a rate
each
B[f(ØT) -
Q T
Var VT
where a
1 1/D² + 2n) dLmax.
2
When interpolation is exactly satisfied, a similar proof technique can be used show that AdaGrad incurs only O(1) regret in the online convex optimization setting (Theorem 6 in Appendix C.2). The above theorem shows that AdaGrad is robust to the violation of interpolation and converges to the minimizer at the desired rate for any reasonable step-size. Although this is favourable property, the best constant step-size depends on the problem, and as we demonstrate experimentally in Section 5, the performance of AdaGrad depends correctly tuning this step-size.
To overcome this limitation, we use a conservative Lipschitz line-search that sets the step-size on the fly, improving the empirical performance of AdaGrad while retaining its favourable convergence guarantees. At each iteration, this line-search selects a step-size 7) that satisfies the property
fiz (wk The V fie (wx)) < fi, (wx) c V fr (ww)ll and 17p S 77k-1-
(2)
The resulting step-size is then used in the standard AdaGrad update in Eq. (1). To find an acceptable step, our results use a backtracking line-search, described in Appendix F. For simplicity, the theoretical results assume access to the largest step-size that satisfies the above condition. 2 Here, is a hyper- parameter determined theoretically and typically set to 1/2 in our experiments. The "conservative" part of the line-search is the non- non-increasing constraint the step-sizes, which is essential for convergence to the minimizer when interpolation is violated. We refer to it as the Lipschitz line- search as is only used to estimate the local Lipschitz constant. Unlike the classical Armijo line-search for
similar result also appears the course notes (Orabona, 2019).
The difference between the exact and backtracking line-search is minimal, and the bounds only changed by constant depending the backtracking parameter.
4

---

Under review as a conference paper at ICLR 2021
preconditioned gradient descent, the line-search in Eq. (2) is in the gradient direction, even though the update is in the preconditioned direction. The resulting step-size found is guaranteed to be the range [2(1 [2(1-c)/Lmar M)= I (Vaswani al., 2019b) and allows us prove the following theorem.
Theorem 2. Under the same assumptions as Theorem 1, AdaGrad with a conservative Lipschitz line-search with 1/2, a step-size upper bound Tluax and uniform averaging converges at a rate
E[((iT) -
a T
Var
where a
1 [ max 2
2 Imax ddmax-
VT
?/max
Intuitively, the Lipschitz line-search enables AdaGrad to take larger steps at iterates where the underlying function is smoother. It retains the favourable convergence guarantees of constant step- size AdaGrad, while improving its empirical performance (Section 5). Moreover, if interpolation is exactly satisfied, we can obtain an ((/T)) convergence without the conservative constraint f/ S 7/k-1 on the step-sizes (Appendix C.3).
AMSGRAD AND NON-DECREASING PRECONDITIONERS
In this section, consider AMSGrad and, more generally, methods with non-decreasing precon- ditioners satisfying A ž AŞ-1- As our focus is on the behavior of the algorithm with respect to the overall step-size, we make the simplifying assumption that the effect of the preconditioning is bounded, meaning that the eigenvalues of A& lie in the [Amin: 4max] range. This is a common assumption made in the analyses of adaptive methods (Reddi al., 2018; Alacaoglu et al., 2020) that prove worst-case convergence rates matching those of SGD. For our theoretical results, we consider the variant of AMSGrad without bias correction, as its effect is minimal after the first few iterations. The proofs for this section are in Appendix D and Appendix E.
The original analysis of AMSGrad (Reddi et al., 2018) uses a decreasing step-size and a decreasing momentum parameter. It shows an ((1//)) convergence for AMSGrad in both the smooth and non-smooth convex settings. Recently, Alacaoglu et al. (2020) showed that this analysis is loose and that AMSGrad does not require decreasing momentum parameter obtain the ((/VT) rate. However, in practice, AMSGrad is typically used with both a constant step-size and momentum parameter. Next, present the convergence result for this commonly-use variant of AMSGrad.
Theorem 3. Under the same assumptions as Theorem 1, and assuming (iv) non-decreasing precon- ditioners (v) bounded eigenvalues in the [amin: amass] interval, where Omass/ 0mas//mmin amins AMSGrad with 1-8 auin and uniform averaging converges at a rate,
[0, 1), constant step-size 1j I+3 2Lomax
1+ 1+3 3/² 1
2 2 2
Bif(Er) - f4
+
T
When 0, we obtain a (1//)) convergence the minimizer. However, when interpolation is only approximately satisfied, we obtain convergence to neighbourhood with its size depending on o². We observe that the noise o² is not amplified because of the non-decreasing momentum (or step-size). A similar distinction between the convergence of constant step-size Adam (or AMSGrad) vs. AdaGrad has also been recently discussed the non-convex setting (Défossez et al., 2020). Unfortunately. the final bound is minimized by setting 31 = 0 and our theoretical analysis does not show an advantage of using momentum. Note that this is a common drawback the analyses of heavy-ball momentum for non-quadratic functions in both the stochastic and deterministic settings (Ghadimi et al., 2015; Reddi et al., 2018; Alacaoglu et al., 2020; Sebbouh et al., 2020).
Since AMSGrad is typically used for optimizing paramtttmeee models, the violation o² is small, even when interpolation is not exactly satisfied. Another reason that constant step-size AMSGrad is practically useful is because of the of large batch-sizes that result in smaller effective neighbourhood. To get some intuition about the effect of batch-size, note that if we use a batch-size of b, the resulting neighbourhood depends of = EB =b [fs (w²) fa (=:g) where wi is the minimizer of batch B of training examples. By convexity, of < [E]] | x V V (ww" (w"))]] If we assume that the distance I!w* x is bounded, of x V fa Since the examples in each batch are sampled with replacement, using the bounds in (Lohr, 2009), of x b [V showing that the effective neighbourhood shrinks the batch-size becomes larger, becoming zero for
nb
5

---

Under review as a conference paper at ICLR 2021
the full-batch variant. With over- paramtttreeiiiiionnn and large batch-sizes, the effective neighbourhood is small enough for machine learning tasks that do not require exact convergence to the solution.
The constant step-size required for the above result depends on Lmax. which is typically unknown. Furthermore, using a global bound on Lmax usually results in slower convergence since the local Lipschitz constant vary considerably during the optimization. To overcome these issues, use stochastic variant of the Armijo line-search. Unlike the Lipschitz line-search whose sole purpose is estimate the Lipschitz constant, the Armijo line-search selects a suitable step-size in the precon- ditioned gradient direction, and as we show in Section 5, it results in better empirical performance. Similar to the constant step-size, when interpolation is violated, we only obtain convergence to a neighbourhood of the solution. The stochastic Armijo line-search returns the largest step-size 17 satisfying the following conditions at iteration k;
fig (wr- A ' fic (wx)) S (ww) c |I f.g (ww))la?" and T)s S 1/max-
(3)
The step-size is artificially upper- bounded by 7/max (typically chosen to be large value). The line- search guarantees descent on the current function fi, and that 7h lies in the [2ami (1-c)/ Lumax 7max range. In the next theorem, we first consider the variant of AMSGrad without momentum (3 0) and show that using the Armijo line-search retains the (1/TT) convergence rate without the need to know the Lipschitz constant.
Theorem 4. Under the same assumptions as Theorem 1, AMSGrad with zero momentun, Armijo line-search with e = 3/4, a step-size upper bound Tmmax and uniform averaging converges at a rate,
3DDd amax
1
2
B[ - 5
max
2T
1mmax
Qmin
Comparing this rate with that of using constant step-size (Theorem 3), we observe that the Armijo line-search results in a worse constant in the convergence rate and a larger neighbourhood. These dependencies can be improved by considering a conservative version of the Armijo line-search. However, we experimentally show that the proposed line-search drastically improves the empirical performance of AMSGrad. We show that a similar bound also holds for AdaGrad (sce Theorem 7 in Appendix C). AdaGrad with an Armijo line-search converges to a neighbourhood in the absence of interpolation (unlike the results in 3). Moreover, the above bound depends on Amin which can be Oc) in the worst-case, resulting in unsatisfactory worst-case rate of O(/<r) even in the interpolation setting. However, like AMSGrad, AdaGrad with Armijo line-search has excellent empirical performance, implying the need for different theoretical assumption in the future.
Before considering techniques to set the step-size for AMSGrad including momentum, we present the details of the stochastic Polyak step-size (SPS) Loizou et al. (2020); Berrada et al. (2019) and Armijo SPS, our modification to the adaptive setting. These variants set the step-size as:
Armijo SPS: 1/s min { Si, (WK) Sīx c fll (ww))lA
Sc, (wx) Ji cl Vf (wx))l /mmax
SPS: Tm min
7/max
Here, fi, is the minimum value for the function fi. The advantage of SPS over a line-search is that it does not require potentially expensive backtracking procedure to set the step-size. Moreover, it can be shown that this step-size is always larger than the one returned by line-search, which can lead to faster convergence. However, SPS requires knowledge of f for each function in the finite-sum. This value is difficult to obtain for general functions but is readily available in the interpolation setting for many machine learning applications. Common loss functions are lower-bounded by zero, and the interpolation setting ensures that these lower-bounds are tight. Consequently, using SPS with f; = has been shown to yield good performance for pre-paaramteriieed problems (Loizou et al., 2020; Berrada et al., 2019). In Appendix D. we show that the Armijo line-search used for the previous results can be replaced by Armijo SPS and result in similar convergence rates.
For AMSGrad with momentum, we propose to use a conservative variant of Armijo SPS that sets "mma = - at iteration k ensuring that 7) S 71-1. This is because using potentially increasing step-size sequence along with momentum can make the optimization unstable and result in divergence. Using this step-size, we prove the following result.
Theorem 5. Under the same assumptions of Theorem 1 and assuming (iv) non non- decreasin precon- ditioners (v) bounded eigenvalues in the (Omin Omaxx] interval with f min AMSGrad with
6

---

Under review as a conference paper at ICLR 2021
3 [0. 1), conservative Armijo SPS with 1+8/1-3 and uniform averaging converges rate,
Bif(ūr) 5 - 1 3- 2T max
dr
T + +o²
1 3
The above result exactly matches the convergence rate in Theorem but does not require knowledge of the smoothness constant to set the step-size. Moreover, the conservative step-size enables convergence without requiring an artificial upper-bound Mhna as in Theorem 8. We note that a similar convergence rate can be obtained when using a conservative variant of Armijo SLS ( (Appendix E.2), although our theoretical techniques only allow for a restricted range of f3.
When A₂ = la. the AMSGrad update is equivalent to the update for SGD with heavy-ball momen- tum (Sebbouh et al., 2020). By setting A = La in the above result, we recover an O(1/T + o²) rate for SGD (using SPS to set the step-size) with heavy-ball momentum. In the smooth, convex setting, our rate matches that of (Sebbouh et al., 2020); however, unlike their result, we do not require knowledge of the Lipschitz constant. This result also provides theoretical justification for the heuristic used for incorporating heavy-ball momentum for SLS in (Vaswani et al., 2019b).
For general preconditioner, the AMSGrad update in Eq. (1) is not equivalent to heavy-ball mo- mentum. With a constant momentum parameter y E [0, 1), the general heavy-ball update (Loizou & Richtárik, 2017) is given as 1 Wig Or A, VV Vi, (wx) +- (WTR wx-1) 11) (refer Appendix E. for a relation between the two updates). Unlike this update, AMSGrad also preconditions the momen- tum direction (wyy w If we consider the merommmmentum variant of adaptive gradient methods as preconditioned gradient descent, the above update is a more natural way to incorporate momentum. We explore this alternate method and prove the same O + o²) convergence rate for constant step-size, conservative Armijo SPS and Armijo SLS techniques in Appendix E.3. In the next section, we use the above techniques for training large weer-parameterized deep networks.
EXPERIMENTAL EVALUATION
Margin5.0 m.
Margie
Murgen 03
Margini6.05
Adaped
18
15
30
100
1.50
200
53
100
250
200
50
100
150
200
100
250
200
(a) AdaGrad
(b) AMSGrad
Figure 1: Synthetic experiments showing the impact of step-size on the performance of AdaGrad, AMSGrad with varying step-sizes, including the default in PyTorch, and the SLS variants.
Synthetic experiment: We first present an experiment to show that AdaGrad and AMSGrad with constant step-size are not robust even for simple, convex problems. We use their Py PyTorch implementations (Paszke et al., 2019) on a binary classification task with logistic regression. Following the protocol of Meng et al. (2020), we generate linearly-separabl dataset with n = 10y examples (ensuring interpolation is satisficd) and d = 20 features with varying margins. For AdaGrad and AMSGrad with a batch-size of 100, show the training loss for a grid of step-sizes in the [10 10-3) range and also plot their default (in PyTorch) variants. For AdaGrad, we compare against the proposed Lipschitz line-search and Armijo SLS variants. As is suggested by the theory, for each of these variants, we set the value of c = 1/2. For AMSGrad, we compare against the variant employing the Armijo SLS with c= 1/2. and use the default (in PyTorch) momentum parameter of 9 = 0.9. In Fig. we observe a large variance across step-sizes and poor performance of the default step-size. The best performing variant of AdaGrad/AMSGrad has a step-size of order 102, The line-search variants have good performance across margins, often better than the best-performing constant step-size.
TThis corresponds to the largest allowable step-size in Theorem 4 without momentum. Unfortunately, the values of suggested by the analysis incorporating momentum Theorem 5 are conservative.
7

---

Under review as a conference paper at ICLR 2021
CIFARIO ResNet34
CIFARLO0 00 DenseNet121
CIFAR100 ResNet33
Tiny ImageNett ResNet18
10'
10"
Than tax (og)
20-1
10
10-1
10-1
20-2
10-4
10-4
10
10-3
10
10-3
10-4
10-3
0
50
100
150
200
50
100
150
200
30
100
150
200
30
1000
130
200
Epoch
Epoch
Epoch
Epoch
CIFARIO ResNet34
CIFARI00 DenseNet121
CIFARI00 ResNet34
Tiny ImageNet- ResNet16
0.76
0.94
0.74
0.39
Valdaton 300/3ey
0.92
0.72
0.72
0.37
0.90
0.70
0.70
0.68
0.68
0.58
0.35
0.66
0.66
0.86
100
50
Spech
Epoch
Epoch
-+- Amsgrad SLS
+ Amograd
SLS 1
- Adabound
Radam
Adam
SLS
Adagrad
SLS
Figure 2: Comparing optimizers for multi-class classification with deep networks. Training loss (top) and validation accuracy (bottom) for CIFAR-IO, CIFAR-100 and Tiny ImageNet.
Real experiments: Following the protocol in (Luo et al., 2019; Vaswani et al., 2019b; Loizou et al., 2020), we consider training standard neural network architectures for multi-class classification on CIFAR-10, CIFAR-100 and variants of the ImageNet datasets. For each of these experiments, we use batch-size of 128 and compare against Adam with the best constant step-size found by grid-search. We also include recent improved variants of Adam; RAdam (Liu et al., 2020) and AdaBound (Luo al., 2019). To see the effect of preconditioning, we compare against SGD with SLS (Vaswani et al., 2019a) and SPS (Loizou et al., 2020). We find that SGD with SLS is more stable and has consistently better test performance than SPS, and hence we only show results for SLS. We also compared against tuned constant step-size SGD and similar to (Vaswani et al., 2019a), we observe that it is consistently outperformed by SGD with SL...
For the proposed methods, we consider the combinations with theoretical guarantees in the convex setting, specifically AdaGrad and AMSGrad with the Armijo SLS. For AdaGrad, we only show Armijo SLS since it consistently outperforms the Lipschitz line-search. For all variants with Armijo SLS, we use = 0.5 for all convex experiments (suggested by Theorem 4 and Vaswani et al. (2019a)). Since we do not have theoretical analysis for non-convex problems, we follow the protocol in Vaswani et al. (2019a) and set c = 0.1 for all the non-convex experiments. Throughout, we set 0.9 for AMSGrad. We also compare to the AMSGrad variant with heavy-ball (HB) momentum (with 7 0.25 found by grid-search). We refer to Appendix F for a detailed discussion about the practical considerations and pseudocodes for the SLS/SPS variants.
We show a subset of results for CIFAR-10, CIFAR-100 and Tiny ImageNet and defer the rest to Appendix G. From Fig. AdaGrad and AMSGrad with Armijo SLS have consistently the best performance, while SGD with (ii) the AdaGrad and AMSGrad variants not only converge faster than Adam and Radam but also with considerably better test performance. AdaBound has comparable convergence in terms of training loss, but does not generalize as well. (iii) AMSGrad momentum is consistently better than the heavy-ball (HB) variant. Moreover, we observed that HB momentum was quite sensitive to the setting of 7, whereas AMSGrad is robust to 3. In Appendix G, we include ablation results for AMSGrad with Armijo SLS but without momentum, and conclude that momentum does indeed improve the performance. In Appendix G, we plot the wall-clock time for the SLS variants and verify that the performance gains justify the increase in wall-clock time per epoch. In the appendix, we show the variation of ttep-size across epochs, observing a warm-up up phase where the step-size increases followed by a constant decreasing step-size (Goyal et al., 2017).
make the following observations, (i) in terms of generalization,
SLS is often competitive.
8

---

Under review as a conference paper at ICLR 2021
In Appendix G, also consider binary classification with RBF kernels for datasets from LIB- SVM (Chang & Lin, 2011) and study the effect of over-varamette peeepaarmettrizzttonn for deep matrix factoriza- tion (Rolinek & Martius, 2018; Vaswani al., 2019b). We show that the same trends hold across different datasets, deep models, deep matrix factorization, and binary classification using kernels.
Our results indicate that simply setting the correct step-size on the fly can lead substantial empirical gains, often more than those obtained by designing a different preconditioner. Furthermore, we see that with appropriate step-size adaptation, adaptive gradient methods can generalize better than SGD. By disentangling the effect of the step-size from the preconditioner, our results show that AdaGrad has good empirical performance, contradicting common knowledge. Moreover, our techniques are orthogonal to designing better preconditioners and can be used with other adaptive gradient or even second-order methods.
DISCUSSION
When training wer-parameterized models in the interpolation setting, we showed that for smooth, convex functions, constant step-size variants of both AdaGrad and AMSGrad are guaranteed to converge to the minimizer at ((1/T) rates. We proposed to use stochastic line-search techniques to help these methods adapt to the function's 's local smoothness, alleviating the need tune their step-size and resulting in consistent empirical improvements across tasks. Although adaptive gradient methods outperform SGD practice, their convergence rates are worse than constant step-size SGD and we hope to address this discrepancy in the future.
REFERENCES
Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. Sgd with shuffling: optimal rates without component convexity and large epoch requirements. Advances in Neural Information Processing Systems, 33, 2020.
Ahmet Alacaoglu, Yura Malitsky, Panayotis Mertikopoulos, and Volkan Cevher. new regret analysis for adam-type algorithms. arXiv preprint wxXi:20003.0972,,2000
Larry Armijo. Minimization of functions having lipschitz continuous first partial derivatives. Pacific Journal of mathematics, 16(1):1-3, 1966.
Mikhail Belkin, Alexander Rakhlin, and Alexandre B. Tsybakov. Does data interpolation contradict statistical optimality? In The 22nd International Conference Artificial Intelligence and Statistics, AISTATS, 2019.
Leonard Berrada, Andrew Zisserman, and M. Pawan Kumar. Training neural networks for and by interpolation. arXiv preprint: (atpiit:::990..00 /906.05661, 2019.
Nicolò Besa-Bianchh, Alex Conconi, and Claudio Gentile. On the generalization ability of on- on-line learning algorithms. IEEE Transactions Information Theory, 2009):2050- 2004.
Volkan Cevher and Bang Công Vü. On the linear convergence of the stochastic gradient method with constant step-size. Optimization Letters, 1775)1117-11187, 2019.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3):1227, 2011. Software available at http::/www. csie. ntu. ftclu.twwwjjiiie hillin/iisssm.....
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong, On the convergence of a class of Adam- type algorithms for non-convex optimization. In 7th International Conference on Learning Representations, ICLR, 2019.
Alexandre Défossez, Léon Bottou, Francis Bach, and Nicolas Usunier. On the convergence of Adam and AdaGrad. arXiv preprint:2003.02239 2020.
John C. Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. The Journal of Machine Learning Research, 12:2121-2159, 2011.

---

Under review as a conference paper at ICLR 2021
Euhanna Ghadimi, Hamid Reza Feyzmahdavian, and Mikael Johansson. Global convergence of the heavy-ball method for convex optimization. In 2015 European control conference (ECC), pp. 310-315 IEEE, 2015.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. Adaptive computation and machine learning. MIT press, 2016. URL http:
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: training imagenet hour. arXiv preprint: 1706.02677, 2017.
Elad Hazan. Introduction to online convex optimization. Foundations and Trends Optimization, (3-4):157-325, 2016.
Elad Hazan and Satyen Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-conver optimization. The Journal of Machine Learning Research, 15(1): 2489-2512, 2014.
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, and Aaron Sidford. Accelerating stochastic gradient descent for least squares regression. Conference On Learning Theory, COLT, 2018.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, ICLR, 2015.
Kfir Y. Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and accelera- tion. In Advances Neural Information Processing Systems, NeurIPS, 2018.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS, 2019.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression generalize. arXiv preprint: I 1808.00000 003877 2018.
Chaoyue Liu and Mikhail Belkin. Accelerating SGD with momentum for wver-parameterized learning. In 8th International Conference on Learning Representations, ICLR, 2020.
Liyuan Liu, Haoming Jiang, Pengeheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. In 8th International Conference on Learning Representations, ICLR, 2020.
Sharon L Lohr. Sampling: design and analysis. Nelson Education, 2009.
Nicolas Loizou and Peter Richtárik. Linearly convergent stochastic heavy ball method for minimizing generalization error. arXiv preprint: 2017.
Nicolas Loizou, Sharan Vaswani, Issam Laradji, and Simon Lacoste-Julien. Stochastic Polyak step-size for SGD: An adaptive learning rate for fast convergence. arXiv preprint:2002.10542 2020.
Ilya Loshchilov and Frank Hutter. SGDR: stochastic gradient descent with warm restarts. In
5th International Conference on Learning Representations, ICLR. OpenReview.net, 2017. URL https: apwnreview.eeeeeeooe/eee/ net forum? wieeeiiiessssseeeeeeee
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. In 7th International Conference Learning Representations, ICLR, 2019.
Siyuan Ma, Racf Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effec- tiveness of SGD in modern paramerraetri learning. In Proceedings of the 35th International Conference Machine Learning, /CML,, 2018.
Si Yi Meng, Sharan Vaswani, Issam Laradji, Mark Schmidt, and Simon Lacoste-Julien. Fast and furi- ous convergence: Stochastic second order methods under interpolation. In The 23nd International Conference Artificial Intelligence and Statisties, AISTATS, 2020.
10

---

Under review as a conference paper at ICLR 2021
Eric Moulines and Francis R. Bach. Non- Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Advances in Neural Information Processing Systems, NeurIPS, 2011.
Mahesh Chandra Mukkamala and Matthias Hein. Variants of RMSProp and AdaGrad with logarithmic regret bounds. In Proceedings of the 34th International Conference Machine Learning, ICML, 2017.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):5574 1609, 2009.
Francesco Orabona. A modern introduction to online learning, arXiv preprint arXiv: 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, NeurlPS, 2019.
Boris T. Polyak. Gradient methods for minimizing functionals. Zhurnal Vychislitel noi Matematiki i Matematicheskot Fiziki, 3(4):643-653, 1963.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In 6th International Conference on Learning Representations, ICLR, 2018.
Michal Rolinek and Georg Martius. L4: practical loss-based stepsize adaptation for deep learning. In Advances in Neural Information Processing Systems, NeurlPS, 2018.
Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under strong growth condition. arXiv 130. 2013.
Othmane Sebbouh, Robert M Gower, and Aaron Defazio. On the convergence of the stochastic heavy ball method. arXiv preprint arXiv:2006.077 078667, 2020.
Matthew Staib, Sashank J. Reddi, Satyen Kale, Sanjiv Kumar, and Suvrit Sra. Escaping saddle points with adaptive gradient methods. In Proceedings of the 36th International Conference on Machine Learning, ICML, 2019.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-RMSProp: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 2012.
Sharan Vaswani, Francis Bach, and Mark Schmidt. parameterized models and an accelerated perceptron. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS, 2019a.
Fast and faster convergence of SGD for over-
Sharan Vaswani, Aaron Mishkin, Issam Laradji. Mark Schmidt, Gauthier Gidel, and Simon Lacoste- Julien. Painless stochastic gradient: Interpolation. line-search, and convergence rates. In Advances in Neural Information Processing Systems, NeurIPS, 2019b.
Guanghui Wang, Shiyin Lu, Quan Cheng, Weiwei Tu, and Lijun Zhang. SAdam: A variant of Adam for strongly convex functions. In 8th International Conference on Learning Representations, ICLR, 2020.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. AdaGrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization. In Proceedings of the 36th International Conference on Machine Learning, ICML, 2019.
Xiaoxia Wu, Simon S. Du, and Rachel Ward. Global convergence of adaptive gradient methods for an over-parameterizee neural network. arXiv preprint: /902.07 2019.
Yuege Xie, Xiaoxia Wu, and Rachel Ward. Linear convergence of adaptive stochastic gradient descent. In Silvia Chiappa and Roberto Calandra (eds.). The 23rd International Conference Artificial Intelligence and Statistics, AISTATS, volume 108 of Proceedings of Machine Learning Research, pp. 1475-1485. PMLR, 2020.
11

---

Under review as a conference paper at ICLR 2021
Matthew D. Zeiler. ADADELTA: adaptive learning rate method. arXiv preprint:1212.57011 2012.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations, ICLR, 2017.
Lijun Zhang and Zhi-Hua Zhou. Stochastic approximation of smooth and strongly convex functions: Beyond the O(1/T) convergence rate. In Conference on Learning Theory, COLT, 2019.
Dongruo Zhou, Yigi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv 1reprinn:18888.55777,, 2018.
12

---

Under review as a conference paper at ICLR 2021
Supplementary material
ORGANIZATION OF THE APPENDIX
Setup and assumptions
B Line-search and Polyak step-sizes
C Proofs for AdaGrad
Step-size
Rate
Reference
Constant
O(/T+ + + 01/r+ ///T+//// %/VT) ((/rr)
Theorem Theorem 2 Theorem
Conservative Lipschitz LS
Non-conservative LS (with interpolation)
D Proofs for AMSGrad and non-decreasing preconditioners without momentum
Constant
( + +
Theorem 8 Theorem
Armijo LS
AMSGrad with momentum
Constant
0(1/4 + 02) 01/r 02)
Theorem 3
Conservative Armijo LS
Theorem 10
Conservative Armijo SPS
01/T+002)
Theorem
Proofs for AMSGrad with heavy ball momentum
Constant
0(1r +
Theorem 11
Conservative Armijo LS
01/T+
Theorem 13
Conservative Armijo SPS
(1/r+022)
Theorem
Experimental details
G Additional experimental results
13

---

Under review as a conference paper at ICLR 2021
Table 3: Summary of notation
Concept
Symbol
Concept
Symbol
Iteration counter, maximum Iterates, minimum
k, T Wky w Tl f(w), f f(
General preconditioner
Ak
Preconditioner bounds
Omins 4max]
Step-size
Maximum smoothness
L Lmax
Function value, minimum
Dimensionality
d
Stoch. function value, minimum
Diameter bound
D
Variance
O² [iifi(w") -f7l
A SETUP AND ASSUMPTIONS
We restate the main notation in Table 3. We restate the main assumptions required for our theoretical results
We assume objective f Rd R has finite-sum structure,
f(w) = 1 Σ f((w,,
(4)
and analyze the following update, with in selected uniformly at random,
wk++1 = wi 77 A2 mg my = fm--1 (1 - -V (wx)
(Update rule)
where 7hs is either pre-specified constant selected on the fly. We consider AdaGrad and AMSGrad and use the fact that the preconditioners are non-decreasing i.e. A& > Ag-1- For AdaGrad, 3 0. For AMSGrad, further assume that the preconditioners remain bounded with eigenvalues in the range [amin: (max).
amin I < A 3 O.nax.
(Bounded preconditioner)
For all algorithms, we assume that the iterates do not diverge and remain ball of radius D. as is standard in the literature on online learning (Duchi et al., 2011; Levy et al., 2018) and adaptive gradient methods (Reddi al., 2018),
| w S D.
(Bounded iterates)
Our main assumptions that each individual function f. is convex, differentiable, has finite minimum fü, and is -mooth, meaning that for all and w,
f((v) 2 f(() (Vf((w), v).
(Individual Convexity)
fi()) f((w)) (V)((w), w) + Lj 2 1|u-ar wwll
(Individual Smoothness)
which also implies that f is convex and smooth, where Liaax is the maximum smoothness constant of the individual functions. A consequence of smoothness is the following bound on the norm of the gradient stochastic gradients.
[+ S (f -f)
To characterize interpolation, we define the expected difference between the minimum of f. f(w"). and the minimum of the individual functions fú"
= Elf((w") fi1l
(Noise)
When interpolation is exactly satisfied, every data point can exactly, such that fj = and f(=*) = 0, we have 2² = 0.
14

---

Under review as a conference paper at ICLR 2021
B LINE-SEARCH AND POLYAK STEP-SIZES
We now give the main guarantees the step-sizes returned by the line-search. In practice, use backtracking line-search to find a step-size that satisfies the constraints, described in Algorithm (Appendix F). For simplicity of presentation, here assume the line-search returns the largest step-size that satisfies the constraints.
When interpolation is not exactly satisfied, the procedures need to be equipped with additional safety mechanism; either by capping the maximum step-size by some 7max or by ensuring non- increasing step-sizes, 77 S 7/k-1. In this case, 7max ensures that bad iteration of the line-search procedure does not result in divergence. When interpolation is satisfied, those conditions can be dropped (e.g., setting 7max - (0) and the rate does not depend on Muaax. The line-searches depend on parameter с E (0, 1) that controls how much decrease is necessary to accept step (larger means more decrease is demanded).
Assuming the Lipschitz and Armijo line-searches select the largest 1) such that
- ( S f((w) en [t))]
7 S 7max,
(Lipschitz line-search)
fi(w- - (V(--)) f((w) en (V)(( the following lemma holds.
1 S Tmax
(Armijo line-search)
Lemma (Line-scarch). If fi is L--sohhth, the Lipschitz and Armijo lines-searches ensure
n| [i < 1 (fi(w)) - -)), and
2 (1 -c)
min
7/max:
S 1j S 7/max:
Isj
1 [V S c (fi(w)) fi). and min
2 Amiu (A) (1 -
Mmaxx
S mmax
L;
We do not include the backtracking line-search parameters in the analysis for simplicity, as the same bounds hold, up to some constant. With a backtracking line-search, we start with large enough candidate step-size and multiply it by some constant y < 1 until the Lipschitz or Armijo linc-search condition satisfied. If 1/ was a proposal step-size that did not satisfy the constraint, but rn/ does, the maximum step-size 77 that satisfies the constraint must be in the range yn S 1 < n/.
Proof of Lemma 1. Recall that if fa is smosthhth, then for an arbitrary direction d,
f(w - d) S fi(w)= - (V.((w), d) + L [d]la
2
For the Lipschitz lene-search, = f(w)). The smoothness and the line-search condition are then
Smoothness:
f((w - f(())) - f.(w) < ( - n) [V
Line-scarch:
f(w (f fi(w) < cc [
As illustrated in Fig. 3. the line-search condition looser than smoothness if
f((w)
Smoothness: f(w)) (447² [()]|
(4n)² [V S -on V f
Line search: f(w)) - f(w))
The inequality is satisfied for any n E [a, bj. where b are values of y that satisfy the equa- tion with equality, 0, = 2(1 2(1-e)/L, L), and the line-search condition holds for 2(1 2(1-0)/L.
===
Figure 3: Sketch of the line-search incqualities.
2(1 2l.-c)/L.. If the step-size is capped at Tmax we have 17 2 min(fmax: 2(1-c)/L.}, and the proof for the Lipschitz line- tine-search is complete. The proof for the Armijo line-search is identical except for the smoothness property, which is modified
As the line-search selects the largest feasible step-size, 17 2
15

---

Under review as a conference paper at ICLR 2021
to use the |I norm for the direction d d= n/ "V.
+ L, 2²"
fi(w nA ----l/(((ii - (
IAA fi(w)]1
Li
f((w) - 1 +
2dmin
-1) 22 (A) 12 --)) 3) |VSi(w)]lA-.
I
= +((w)+
where the second inequality comes from || Amintay [V
Similarly, the stochastic Polyak step-sizes (SPS) for Sa at are defined as
fi(w) ft c c (w))
minn f((w) fr (V))
SPS:
min
Tmax y. Armijo SPS:
Mmax
where the parameter e > 0 controls the scaling of the step (larger e means smaller steps).
Lemma (SPS guarantees). If J is Ly-smooth, SPS and Armijo SPS ensure that
SPS:
[/V s ([(((w)= - -1), min Mmaxx Zehs
S 11 S Vmmax
Armijo SPS:
[[ ((f(w)- ff), min Tmax
Amin(A) 201.
< S 1/max
Proof of Lemma 2. The first guarantee follows directly from the definition of the step-size. For SPS,
fe(w) -t Tmuax [VV
/|V[[())| min
c (l
min
fi(w:)
Mmax [V[(())]]
(1(w)) fi).
c
The same inequalities hold for Armijo SPS with [ To lower- bound the step-size, we use the L,-smoothness of fú, which implies f((w) f 2 21, (w)]2 For SPS,
1-1-
f((w) - 21, [V]](
clVVf(u)]l'
c 2CL,
For Armijo SPS, we additionally use [ S Xmii (aj
|f((w)]?
fe(w) - ff
( 21.
Amiu (A)
Xxman (4) [[((w)]1
2cL;
16

---

Under review as a conference paper at ICLR 2021
C PROOFS FOR ADAGRAD
We now move to the proof of the convergence of AdaGrad in the smooth setting with a constant step-size (Theorem 1) and the conservative Lipschitz line-search (Theorem 2). We first give a rate for an arbitrary step-size тh in the range [Tmin 7mmax] and derive the rates of Theorems and 2 by specializing the range constant step-size or line-search.
Proposition (AdaGrad with non-inereasing step-sizes). Assuming (i) convexity and (ūi Imaxx" smoothness of each fú, and (iii) bounded iterates, AdaGrad with non-increasing (mk TBs-1). 1), bounded step-sizes (1K E Thmin Tmaxs), and uniform averaging WT = + Wks converges at a rate
Vag VT
(D2
1
D2
[[f(wr)
-
where
+ 2Muax d.
2
17min
We first use the above result to prove Theorems and 2. The proof of Theorem immediate by plugging Tmii M/aa in Proposition 1. We recall its statement;
Theorem 1 (Constant step-size AdaGrad). Assuming (i) convexity and (ii) Lmax" smoothness of each fú, and (iii) bounded iterates, AdaGrad with constant step-size and uniform averaging such that WT = Ei= Wkk converges at a rate
a Vag T VT
1 1
2
B[f(Ør) -
+
where a
2 + 21 dLmax-
For Theorem 2, we use the properties of the conservative Lipschitz line-search. We recall its statement;
Theorem 2. Under the same assumptions as Theorem AdaGrad with conservative Lipschitz line-search with e = 1/2, a step-size upper bound mmax and uniform averaging converges rate
a [[f(wT) - f
vao T VT
(DD max 2
1
where =
Lixxx
+
2 1mmx
dLmax.
Tmmax
Proof Theorem 2. Using Lemma there is step-size ті that satisfies the Lipschitz line-search with 2 (l-cc)/Luax Setting c 1/2 and using a maximum step-size Tmaxx we have
1 max
min
Mmax
7max
Lmax
Linax
7min
7/mxx
Before going into the proof of Proposition 1, we recall some standard lemmas from the adaptive gradient literature (Theorem 7 & Lemma 10 in (Duchi et al., 2011), Lemma 5.15 & 5.16 in (Hazan, 2016)), and useful quadratic inequality (Levy et al., 2018, Part Theorem 4.2)). We include proofs in Appendix C.1 for completeness.
Lemma 3. the preconditioners are non-decreasing (A Ak-1), the step-sizes are non- increasing (m) S M7-1),, 1), and the iterates stay within a ball of radius D of the minima,
Et ||
u0 112 Th d.
D2 Tr(A)..
Ao
o6-1
1/2 Lemma 4. For AdaGrad, A = Et_ (wk, (wx (wx)) (wx))
and satisfies,
Σ V (wx) (wx)1 2Tr(Arr)
Tr(Ar) V V. (2xx
17

---

Under review as a conference paper at ICLR 2021
Lemma 5. If I a(x + for and 2
1 Vaz + 4ab + a) S sa+ Vab. 1/4 2
We now prove Proposition
Proof of Proposition I. We first give overview of the main steps. Using the definition of the update rule, along with Lemmas 3 and 4, we will show that
E (V, (WR), wa - --)== <
D
+ 21maxx
Tr(AT).
(5)
M/nin
Using the definition of Ar, individual smoothness and convexity, we then show that for constant a,
E B[f(we) - f4) s a Fi, - fix (w²) + To²)
(6)
Using the quadratic inequality (Lemmaa 5), averaging and using Jensen's 's inequality finishes the proof. To derive Eq. (5), we start with the Update rule, measuring distances to w" in the I|-IlA, norm,
||wx+1 - w" Il = I|w - wt 11 27k (V fue (w*), wis - w²) + गे V.. (w (l
Dividing by Tık reorganizing the equation and summing across iterations yields
2
V fi (wx); wk w²)
w²1
T Si (wx) (wx))
Ae
Av-1
T
T
wwo w" 11
Ak-1 m6-1
+
7max
V (wx))
We use the Lemmas 3, 4 to bound the RHS by the trace of the last preconditioner,
D
Tr(AT) + 2mmax Tr(AT):
(Lemmas and 4)
D2
+ 2m
Tr(Ar).
(T7 2 Memin)
7min
To derive Eq. (6), we bound the trace of Ar using Lemma 4 and Individual Smoothness,
Tr(AT) S vdl Et
V (ux))l?
(Lemma 4, Trace bound)
I /2dLmax Eks fae (wx) fii.
(Individual Smoothness)
S 22Lmmxx Elen fie (wk) (w=) + fee fie(w*) - fiz
(tx
Combining the above inequalities with di, = Six (w*) ffi and = = ( + 21 v 2d
Manio
E Si, (wK), un - w²) S av Ei (wkk) ((w) + dia-
Using Individual Convexity and taking expectations,
Σ B[f(ww) f aB
El (ww) - fix (w*) + 88z
s <aye
En fi. (wx) Sig (w*) din
(Jensen's 's inequality)
Letting 0² : -E(lo,] = Eslf((w*) - fr] and taking the square on both sides yields
2
Σ Bls(wx) -
< a²
E
fúx (wx) fie (wm) + To²
18

---

Under review as a conference paper at ICLR 2021
The quadratic bound (Lemma 5) x² a(x () implies x S a + vaB, with
T Σ Blf(wu)) fl,
1
1
D2
2mmxx
ddmaxi
B ==
2
Mmmin
gives the first bound below. Averaging wT + Ek wk and using Jensen's inequality give the result;
T
Blf(wx) f* < a v
Eff(ūr)
a 5
Vao VT
T
19

---

Under review as a conference paper at ICLR 2021
C.I PROOFS OF ADAPTIVE GRADIENT LEMMAS
For completeness, we give proofs for the lemmas used in the previous section. We restate them here;
Lemma 3. If the preconditioners are non-decreasing (As ł AR-1). the step-sizes are non-increasing (Th S 11)-1), and the iterates stay within ball of radius D of the minima,
Ek
1aa w 11? A n6-1 7T
D Tr(Ar).
Proof of Lemmma 3. Under the assumptions that A& is non-decreasing and The is non-increasing,
1. Ak At-1 2 O, so we can use the Bounded iterates assumption to bound
Σ
1i
w01 A2
Av-1
Ek
Amax
(An me
Ak-1
96-1
llwek
w01
Amax
(Az 1
mk-1
We then upper-bound Amax by the trace and use the linearity of the trace to telescope the sum,
- Ei=
Au
As 1
= D2 Ek= Tr
As
Tr
Ae 7
96-1
= D2 (rr
Ar
- Tr
Aa
I D2 1 Tr(At)
Lemma 4. For AdaGrad, A₁ = E V.s. (wk) (wx) T
1/2 and satisfies,
Σ (V (Tr(Ar). Tr(At) S V IV (wx))l
Proof of Lemma 4. For ease of notation, let V. = (i,(())) By induction, starting with 7- 1,
(wr)( VTA V, Tr(VT AT 'v) = Tr Tr(AT' (Cyelic property of trace) (A1 = (
Tr(AT 4 = I))
Suppose that it holds for 7 1, V V بي S 2Tr(Ar-1). We will show that it also holds for T. Using the definition of the preconditioner and the cyclic property of the trace,
Σ V (wk) (wx) 112 s + I|
(Induction hypothesis)
2Tr (TT((A) - V+ + (r(AA
(AdaGrad update)
We then use the fact that for any X 2 Y z 0. we have (Duchi et al., 2011, Lemma 8)
2Tr (x
v) (X-))
Tr
- 2Tr 2Tr (x**).
As
= =
ł 0, we can use the above inequality and the induction holds for T.
For the trace bound, recall that Ar G/ where GT E Via (wrk J (wx)T. We use Jensen's inequality,
Tr(Ar) T TT((c/3
E (Ay(Gr) d 1 E VA)(or) < <d
= VdVTTr(T))
To finish the proof, we use the definition of GT and the linearity of the trace to get
/ V.V.
TrV.V.) = V I..l
20

---

Under review as a conference paper at ICLR 2021
Lemma 5. 1f - sa(r b) for a 2 0 and b 2 0.
1 x 2 Va 4ab + a) sa Vab.
Proof of Lemma 5. The starting point the quadratic inequality x² az ab < 0. Letting T1 S 72 be the roots of the quadratic, the inequality holds if x E [2], The upper bound is then given by using Va + b S vu + vb
v + 4ab
a a va
44ab
a + Vab.
r2
C.2 REGRET BOUND FOR ADAGRAD UNDER INTERPOLATION
In the online convex optimization framework, consider sequence of functions, f&l chosen potentially adversarially by the environment. The aim of the learner to output series of strategies wklk wylk- before seeing the function fs. After choosing Wk, the learner suffers the loss fu(w)) and observes the corresponding gradient vector V. (wx). They suffer an instantaneous regret rk fa( fie (w) compared fixed strategy w. The aim bound the cumulative regret.
T R(T) -iv(wu)) - fua
where w* arg min El= (ww is the best strategy if we had access to the entire sequence of functions in hindsight. Assuming the functions are convex but non-smooth, AdaGrad obtains an OLL/VT) regret bound (Duchi al., 2011). For online convex optimization, the interpolation assumption implies that the learner model is powerful enough to fit the entire sequence of functions. For large over-pat wer-parameterized models like neural networks, where the number of parameters is the order of millions, this is reasonable assumption for large T.
We first recall the update of AdaGrad, at iteration k the learner decides to play the strategy wk- suffers loss f&x (wx) and uses the gradient feedback f((()))) update their strategy
Wk+1 = A fa (wa), where A Σ
Now we show that for smooth, convex functions under interpolation assumption, AdaGrad with constant step-size can result in constant regret.
Theorem 6. For sequence of -mooth, convex functions fK. assuming the iterates remain bounded s.t. for all k; I|w w"1 I D, AdaGrad with a constant step-size n achieves the following regret bound,
1 Dot (2=_+ +2 2m 2 1)
R(T) <
dlmma + V
D= + 2n dlmaxo02 VT
where o² is an upper-bound on fi(ww)) st.
Observe that o² the degree which interpolation violated, and if o² + 0, R(T) O (T) matching the regret of (Duchi et al., 2011). However, when interpolation is exactly satisfied, o² = 0. and R(T) (1).
Proof of Theorem 6. The proof follows that of Proposition which is inspired from (Levy al., 2018). For convenience, we repeat the basic steps. Measuring distances to w in the ||-I|A, norm,
[w w² w'll2, ||ww -= 2 ws w²) n? | ( 12,,
21

---

Under review as a conference paper at ICLR 2021
Dividing by 21z, reorganizing the equation and summing across iterations yields
Σ (ilk(u)) wi w²) 1u w
1011 17( -/11)
"
Σ
(VfA(())))
2
By convexity of fk. (Vfx(wx), wk w²) (w() -f((w"). Using the definition of regret,
T
T
R(T)
-
1o0
w01
" VVaa(a))l
2
k=1
We use the Lemmas 3, 4 to bound the RHS by the trace of the last preconditioner,
D2
R(T) <
2n +" Tr(Ar).
We now bound the trace of Ar using Lemma 4 and Individual Smoothness,
Tr(Ar) s vd
f. (ww))).
(Lemma 4, Trace bound)
2d max E Sk(WE) - 5
(Individual Smoothness)
S /2dTmmxx
Σx= Su(Wk) Su(w") fa(w") Sk.
(+ff((")))
S 22
R(T) + +o2T.
(Since Sa(w=' f S 5²0
Plugging this back into the regret bound,
D
R(T) S + /2dLmaxly R(T) o
211
Squaring both sides and denoting a = =(Dr + V2dLmax.
[R(T)] S (R(T(()) (()((()) + o²T'.
Using the quadratic bound (Lemma 5) x² < a(x + 3) implics x S VaB, with
1 / !つ인 1 + 2n dLmax:
T R(T),
B TT,
2
yields the bound,
R(T) Va3
1
D2
+ 2n 2
D2 + 2n dL dLmax + 1/2
11
2
17
22

---

Under review as a conference paper at ICLR 2021
C.3 WITH INTERPOLATION, WITHOUT CONSERVATIVE LINE SEARCHES
In this section, we show that the conservative constraint 7/++1 S T is not necessary if interpolation satisfied. We give the proof for the Armijo line-search, that has better empirical performance, but a worse theoretical dependence on the problem's constants. For the theorem below, 4min is lower-bounded by in practice, A similar proof also works for the Lipschitz line-search.
Theorem 7 (AdaGrad with Armijo line-search under interpolation). Under the same assumptions of Proposition 1, but without non increasire step-sizes, if interpolation satisfied, AdaGrad with the Armijo line-search and uniform averaging converges at the rate,
(D² + 21 ddmmax
Linax
})²
Elf(wr) 5
max
2T
T/max
amin
where amin ming {Amin (Aa)).
Proof of Theorem 7. Following the proof of Proposition 1,
M&VVi (wk), wi w²) Io w" 11.. - || w + n IIV.s (wx))l
On the left-hand side, we use individual convexity and interpolation, which implies fie (w*) =
min fég (w) and bound n)s by Mmnin giving
The ( Jú (wx), wk w²) mk (Jiv (wx) Jú, (w*)) 2 Mmmin (Ji, (Wrk) Sia (w")).
20
On the right-hand side, we can apply the AdaGrad lemmas (Lemma 4)
T
Σ 1o0k w² w" - -1 - w0 wll... + #maxx V (wx)))
(r(r) 21/maxx Tr(Ar),
(By Lemmas 3 and 4)
<( DD2 + 2m vay Ex- | (ww)ll
(By the trace bound of Lemma 4)
<D2 + 2mxx) v /2d V Ek= Six (wx) - Júg (w*))
(By Individual Smoothness and interpolation)
Defining
DD2 + mxxx) 22d..max and combining the previous inequalities yields
21pmit
T Σ (fu - fix (w S av avVV Σ for - fiee (w*).
k=1
Taking expectations and applying Jensen's 's inequality yields
El f(w") av E (lf(w)) f(ww)].
Squaring both sides, dividing by Σi=1 ((s(w)) - f(w"), followed by dividing by T and applying Jensen's 's inequality,
à² DD2 + 2 'dTmax
Bff(ūr) - f f(")(()))))))))
T
2 T
Using the Armijo line-search guarantee (Lemma 1) with 1/2 and maximum step-size Tmax
again Tmmax: Lmax
Mmin min
where amin ming Amin (Ak)). giving the rate
Bif(ūT) - f(w")[ 2 + 2 )²
ddLmax
Lmax amin
)) 2
max
2T
TJmax
23

---

Under review as a conference paper at ICLR 2021
D PROOFS FOR AMSGRAD AND NON-DECREASING PRECONDITIONERS WITHOUT MOMENTUM
We now give the proofs for AMSGrad and general bounded, non-decreasing preconditioners in the smooth setting, using constant step-size (Theorem 8) and the Armijo line-search (Theorem 4). in Appendix C, we prove general proposition and specialize it for each of the theorems;
In addition to assumptions of Theorem I, assume that (iv) the preconditioners are non-decreasing and have (v) bounded eigenvalues in the [Aming Omax] range. If the step-sizes constrained to lie in the range [7min Tmax] and satisfy
Proposition 2.
Th V fix (wx) ) S M (fre (wx) )
fid, for some M < 2,
(7)
using uniform averaging wT = Ei=r Wk leads to the rate
Da
(
2 Mmax
1 1000
[(((")) --) s (2 Mmmin
M Mmin
Theorem 8. Under the assumptions of Theorem I and assuming (iv) non-decreasing precondition- ers (v) bounded eigenvalues in the [Auiin Omaxx interval, AMSGrad with no momentum, constant amin and uniform averaging converges at a rate,
step-size 17
2Lemxx
2D dmax Lmmax
B[((ūT) 5
+ 0².
amin T
Proof of Theorem 8. Using Bounded preconditioner and Individual Smoothness, we have that
VV, (wx))l 2L
[i 5
(Jin (wx) fia)-
amin
Omnn
A constant step-size Tmax 17min
satisfies the step-size assumption (Eq. 7) with M 1 and
2Lmax
1 1 do
2 Tmax
-1)0²
1 22 D2 de D' + o²
T (2 M) M)/mnn
M
Mmnin
-T
Gmin
We restate Theorem 4;
Theorem 4. Under the same assumptions as Theorem 1, AMSGrad with zero momentum, Armijo line-search with c 3/4, step-size upper bound Tmmax and uniform averaging converges at a rate,
B[((TT) 3Ddd amax + 33mmaxx2
2
max
2T
V/max
Omin
Proof of Theorem 4. For the Armijo line-search, Lemma I guarantees that
1 7 f. (ww)) S (Ji, (wrk) - }7 and min 7/max:
2mii (Aa) (1 (1-c)
S 1) S 7max
c
Linax
ammin Selecting 3/4 gives M 4/3 and Mmin min Mmaxx 2Lmaxx { 50
D2 damax
2 Mmax
-))2
1
T (2 M Mmmn
M Mmin
1 Dadamaxx
2
Mmax
1 1000
T (2 Main
2
4/3 Mhuin
1 3DD da
31Jmax
1102
T 21min
Mmni
3 da
2
1
2Lmax
max
30mmax max
2T
Tmmax
amin
Thnax
amin
24

---

Under review as a conference paper at ICLR 2021
Theorem 9. Under the assumptions Thherrmm I and assuming (iv) non-decreasing precondition- ers (v) bounded eigenvalues in the [amins amax] interval, AMSGrad with no momentum, Armijo SPS with = 8/2 and uniform averaging converges at rate,
3D'd dmax
3Lmax
Blf(wT) - 5
3m
max
2T
7max
20min
Proof Theorem 5. For Armijo SPS, Lemma guarantees that TTk V (w)) 1 (fi. (w*) fi.): and
min
7max 2c Lmax
amin
S S 7mmax
Selecting 3/1 gives M 4/s and Mnin min
Maxxx TTeaax j. ,,50
20min
D2 da
2 Mmax
-1 1 )0²
T (2 M Mmnnn
M Mmni
1 da
2
Mmax
1100
T (2 4/3)Tmii
2 1/3 1/min
1 3d
31maxx
-
-1)0²
-
T 21mmin
Thnin
d0
L
1
3
$ 2T
max
3maax max
7max
2amia
Thaax
20min
Before diving into the proof of Proposition 2, we prove the following lemma to handle terms of the form (Se (wx) - fsa (w )). If 7hs depends on the function sampled at the current iteration, Siz as in the case of line-search, bounds ny (fe (wk) fia (w )) in terms the range [Mmin 7max];
cannot take expectations the terms not independent. Lemma
Lemma 6. IF0 S Mmin S S Tmax and the minimum value of ft is fú, then n(s(ww) fs(w)) 2 Mmin (J(()) - s((w")) - (Nmax - Mmmn (Iiin) - f()-
Proof of Lemma 6. By adding and subtracting ft the minimum value of fú, we get non-negative and non-positive term multiplied by 1). We can use the bounds 1j 2 Tmin and r) S Vmmax separately;
n[Ji(w)- Ji(w")] n/ f(((w))= S
fi(w"))
50
2 Mhii (w) fil + Mmax f((w")].
Adding and subtracting MminJe(w" finishes the proof,
M/iin [f((w) fe(w") + fi(w") f7] + Mmax [f fz(w")),
7mmi mf (f() - fe(w")] + (Amax Mmnin [ff - f((w")].
Proof of Proposition 2. We start with the Update rule, measuring distances to w" in the II-II norm,
| w" 11 ||w w" 113,. 2mp fi (wk), wy -w") ni f (ww))2 To bound the RHS, we use the assumption on the step-sizes (Eq. (7)) and Individual Convexity,
(8)
2m ( fi, (wK), uk -")
) +
vi V (wx))1 )1
S -2m (V ft. (wx). wx ) + Mm (fi, (wx) - fi),
(Step-size assumption, Eq. (7))
--21TA lfe. (w*) f(z(w")
Mm. (Wk) - fid,
(Individual Convexity)
s -22m If (wx) (w=" )] + Mm.(fil (wk) - fir(w" fic(w") -fi).
(+ (w*))
s -- (fm fv. (www)) + Manax fay (w") fii)-
(m% S maax)
25

---

Under review as a conference paper at ICLR 2021
Plugging the inequality back into Eq. (8) and reorganizing the terms yields
2 (wk) - fiz (w)") - (1u0x w" 11. ||ax+11 w0 i1ae)
MMmax (w)) - fin
Using Lemma 6, we have that
(2 (1 fex (w*) (2 M Mynnn (Sic (wk) Siz (w²))
- (2 M) MM - (Jin (w0) (1nn si...
Using this inequality in Eq. (9), we have that
(2 MM Mmii (fia (wx) fir (ww)w)
(Mmax Mmin (Fis (w=) fia) wm w" w²1 ||wx+1 w" (lAa.) + MMmax (Fe (w²) sia);
Moving the terms depending on fig (w*) fiv to the RHS.
(2 MMmi (fea (wx) fiz (w=)) S ||wx wz w01 11 w=1l (laa))
+ (27max (2 M MM)ml (fre (2)) fie).
Taking expectations and summing across iterations yields
(2 - M Munin
Elfs (wx) - (ww
Σ [w w² w²l -1|ux+1- w (1A
+(2mmax (2 M Mmmm)moo''
Using Lemma 3 to telescope the distances and using the Bounded preconditioner,
Iue w01 10 -|Iuk+1 10
D2 Tr(AT) D) d dmaax Wk w0l - A
which guarantees that
2 MM Munn [[f(wk) f(w")] SD2 damax + (27maxx
M Muni To?
Dividing by 7(2 M) Timi and using Jensen's 's inequality finishes the proof, giving the rate for the averaged iterate,
B(((Tr) f(w=)( 1 D de
2 Mmax
1100 0o
1
(2 M) Munn
M Mhiin
26

---

Under review as a conference paper at ICLR 2021
E AMSGRAD WITH MOMENTUM
We first show the relation between the AMSGrad momentum and heavy ball momentum and then present the proofs with AMSGrad momentum E.2 and heavy ball momentum in E.3,
E.I RELATION BETWEEN THE AMSGRAD UPDATE AND PRECONDITIONED SGD WITH HEAVY-BALL MOMENTUM
Recall that the AMSGrad update is given as:
Wk+1= Wk Tis A mm : m. 3mm--1 + +1 V (wk)
Simplifying,
Wk++1 = A (3mmmm + (1- 3iV
#k++1 wk 7) (3) A Vi (wk) 7uB A m
From the update iteration k 1,
We Wk-1 a] 1 A 12-11
m A. (Wk- wk-1)
-
From the above relations.
Wk++1 Wk Th (1 - 3) A. f.. (wx) + A A (wk, Wk-1)
T7--1
which is of the same form as
Wk+1 w/: 7Jk A 7w1 wk-1),
the update with heavy ball momentum. The two updates equivalent up constants except for the key difference that for AMSGrad, the momentum vector (wy. Wk-1) is further preconditioned by Ar Ap-1-
27

---

Under review as a conference paper at ICLR 2021
E.2 PROOFS FOR AMSGRAD WITH MOMENTUM
We now give the proofs for AMSGrad having the update.
Wh+1 W/: A.
mi mm
m& 3mm-- 81 fix (wx)
We analyze it in the smooth setting using a constant step-size (Theorem 3), conservative Armijo SPS (Theorem 5) and conservative Armijo SLS (Theorem 10). As before, we abstract the common elements to general proposition and specialize it for each of the theorems.
Proposition 3. In addition to assumptions of Theorem 1, assume that (iv) the preconditioners non-decreasing and have (v) bounded eigenvalues in the [amin @max] range. If the step-sizes are lower-bounded and non-increasing, Muin S
Tiss 7] and satisfy
1-8
f (ww))la S M(fi(wu) fii,, for some M < <2-
(10)
1 1
using uniform averaging WT Ek= Wk leads to the rate
Bif(or) fr - $ 2 1+ ( M)
-1
D Mo² Mmin
1 1-3"M
We first show how the convergence rate of each step-size method can be derived from Proposition 3.
Theorem 3. Under the same assumptions as Theorem 1, and assuming (iv) non- decreasing preconditioners (v) bounded eigenvalues the [Omin amax] interval, where amin and uniform
= amax/omin, AMSGrad with [0, 1), constant step-size I+. 2hmax
averaging converges at a rate,
Bif(ūr) - f*] 1 1 2T 2T Dd
t
T
Proof of Theorem 3. Using Bounded preconditioner and Individual Smoothness, we have that
2Lmax
f (ww) S |V (wx))2 <
(fa (wk) fiJ).
Qmin
amin
Using a constant step-size = 1-8 Omin
satisfies the requirement of Proposition (Eq. (10)) with constant = 1-8 The convergence then,
1+8 2bmax
1+ 3
1+
D2 da
Blf(wT) - f(=')) []
2
M
Mo2
1- 3
1 1-
Mmnn T
1
D2
I-
T
1 1+7
3
i+9 2Lemas
+ 3
2T 2Tanase D2d
+
3
T
with = 4mmax/ Amin-
28

---

Under review as a conference paper at ICLR 2021
Theorem Under the same assumptions of Theorem and assuning (iv) non- decreasing preconditioners (v) bounded eigenvalues in the [amin Qmax interval with fmax/aamn AMSGrad with 3 E [0, 1), conservative Armijo SPS with 1+ and uniform averaging converges al rate,
1+ L Dd
B)f(eT) - fd] -
to2.
3
T
Proof of Theorem 5. For Armijo SPS, Lemma guarantees that
Th V Sú (wx) ) 2 S 1 (J (wx) Ji,):
Gmin
and
2c Tmax
Setting
1-3 ensures that M 1/c satisfies the requirement of Proposition and Miin 1-8 aain. Plugging in these values into Proposition 3 completes the proof.
1+9 2hmox.
Theorem 10. Under the assumptions of Theorem and assuming (iv) non-decreusing precon- ditioners (v) bounded eigenvalues in the (amin; (maxx] interval, AMSGrad with momentum with parameter B E [0, 1/), conservative Armijo SLS with 2 1+8 and uniform averaging converges
3 1-B
at a rate,
1+ 3 Lmax Dd
[[ [ s
53
T
Proof of Theorem 10. For Armijo SLS, Lemma guarantees that
1 (Ji, (wx) -(t):
2(1 - amin
Vi, (wx))l S
and
1jk-
Temax
The line-search parameter c is restricted to [0. 1] and relates to the the requirement parameter M of Proposition (Bq. (10)) through M = 1/c. The combined requirements on M are then that 1 < M < 2 1-8
T+ which only feasible B }. To leave room to satisfy the constraints, let B < $
Setting M 1
satisfies the constraints and requirement for Proposition and
1
1+ 1-9
D2 -Ma2 Mmiin T
([f(wT) f(w")]
2
M
1-3 3
1+
3
Liax
Dd
3 31
2
1- B
2
2(1 c) Omin
T
21
1 1 3
Txnax D2dds
+ 8
Timax D&
30 =
+ 302
1- 3 (1
c)
T
1 1- -53
T
where the last step substituted 1/(1-c).
21 B
3(1 (8
2(1 (1+
11 5/
1-c=1-
31 8
3(1
3 1 3
Before diving into the proof of Proposition we prove the following lemma.
Lemma 7. For any set of vectors a, b, c, d, if + c, then,
|aa d| |6 dl ||a b11 + 2(c, d)
29

---

Under review as a conference paper at ICLR 2021
Proof.
||a d = |b+
c +b++
d| ||b - ddl + 2/c, b d) + +||l|
Since c = a - b,
1b --I + 2(a b, 1 d) ||a b11
= |b 1--d] dll + 2(a b, - a d) + ||a - bl|
|6 1-d] dll + 2(a 6,6 a) + 2(a b, d) + aa b12
|b dl 2 lla b12 2(a a d) ||a bll
= 6b dl2 2 - ||a b1| 2(c, a d)
We now to the proof of the main proposition. Our proof follows the structure of Reddi et al. (2018); Alacaoglu et al. (2020).
Proof of Proposition 3. To reduce clutter, let Ps Ag/mk- Using the update, we have the expansion
Wh+1 -=" = =(wx Ph 1=1m)) w²:
= =(wx - (1 - Px Vin (wk) - 3-Pp"ma-1) - w,
Measuring distances in the p.-ormm such that || (2,, Paat),
|10411 w=ll 11 = l|w - w w01 2(1 - B) (we - w", V (wx))) 23 (wy w" m + ||m 11
We separate the distance to w from the momentum in the second inner product using the update and Lemma 7 with P (wk w") 0, d P... (wx-1 w²).
- 22(m Wkk w²) = -2 (P -ukk - -wk, wh w²):
= |lux wi-1ll Px + || w u111 - || w" w011?
|| 1| p-- + ||10 w
"0(1p=-_ plp || w01|?__
< |
11 || + 1|1 w² I| - || - w 1|?--17
where the last inequality uses the fact that ти S 7 and A₁ Az-1 which implies Ps. > P Pa-..
and |mlk w01
10' 1| I || ww w w' Plugging this inequality and grouping terms yields
2(1 - B) (wi - w", ([ S [Iwee w: 112 - -1|w4+1 w w1'1 [1?m.]
+ B |lwwx - w011/2 -1lwa-1 w0 [1PA_.]
+ [BB 1mmx-112 + lImallbe..]
By convexity, the inner product on the left-hand- is bounded by (wx w", fa, (wx)) 2 Jig (wx) - fig (w*). The first two lines the right- aigt-hand-side will telescope we sum iterations, so we only need to treat the norms of the momentum terms. We introduce a free parameter 8 > 0. that is only used for the analysis, and expand
3 ||m--111 + [|m=lpp.- 3 1mm-1PP + (8) 1mm - ||mm IP.
To bound || P, expand it by its update and use Young's inequality to get
|| 12p-- [|,m=-1 (1 BIV (ww)l
< (1 + e) 1m--1 (1 + 1/) (32 IV, (wx))
30

---

Under review as a conference paper at ICLR 2021
where O is also free parameter, introduced to control the tradeoff of the bound. Plugging this bound in the momentum terms, we get
B [m 11 pp + lmmellpp S
|| 11 + (1 + () + 6).3² || 11l - 6 || |
+ + 1/)+ 6) 3) fi (wx))l?,
As p-1 3 P.1. we have that || 11 plp 5 | | which implies
$ (B + (1 + () + 8)189) || 11 PEl - 8 8'1mellie
(1 1/- + 6) 3)² V fie (wx))l (ww))
To get a telescoping sum, we set å to be equal to B + (1 + e) + 5),8?, which is satisfied if (-(1+)) and is satisfied if 3 < 1/vIte. We now plug back the inequality
= (1+c))32
1 lip |mmall So 10|lma-lll
|| ||mallp..1
+ (1 + 1/-)(1 + 5)(1 - B32 VV (wxk) (w
in the previous expression to get
2(1 B) (fi (Wx) fi. (w))) S | w0 - -luuk11 w0
+ B |lukk w0'l/" - |||uk w (ppp_
+ | [1 - || 1I2.--1
+ (1 + 1/c)(1 + 5) 3)² Si. (wk) (
All terms now telescope, except the gradient norm which bound using the step size assumption,
(i 1/s | (ux+) S ([ - sit);
M (Ji, (wx) fi,("") + M(i, (w") si.).
This gives the expression a (wx) - fir (w")) S 1w0g - w² w²1 - -|1uk+1 1wk+1-10 - w0 Px.
+ B |11b - -w"ll?a - -1lWa-1 w" PP-1
+ 8 [|mm-1 11 -1|m= Pp
+ (1 + 11+ -1 (f fi),
with a = 2(1 - (2) 3y Summing all iterations, the individual terms are bounded by the Bounded iterates and Lemma 3;
D2
ww w/ w01l²2 | w= w0'
< D2Tr(PPT)
Tr(AT)
Mmii
$ 3 D2
1luk w. "011 1106-1-00 11
$ B Uur -w =1
Tr(Ar)
Mmin
T
8
|| || P-1, -I|mall p-
< 6 6/
0.
1=1
Using the boundedness the preconditioners gives Tr(Ar) & domax and the total bound
T
(1 + 3)D damax
T
(Si. (wx) si,("))))
+ (1 + 1/) + 6) 3) M > (Js, (w²) -f.).
Muiin
1=1
1=1
31

---

Under review as a conference paper at ICLR 2021
Taking expectations,
(1 3 (1++ 6)(1 8) Mo
E[f(wx) f(w")] v
Muii
It remains expand and simplify the constants, We had defined
B + (1 + c) 6
2(1 -) 8) (1 + 1/) + () 3) 0, and
0,
(1
where < > is free parameter. This puts the requirement on f that B bounds, we set 3 1/(1 c), 1/3 1, which gives the substitutions
<1///+c To simplify the
1 1
8
1+ 8 1 1
1 1+6=
8 5=
1-3 3
1-
B
1- 8
Plugging those into the rate gives
(1+ 31+ 3)
-
+ +1+
Mhii
while plugging them into a gives
a = 2(1 B] - 1/)(1 + 6) - 3)
= (1 - 3) 1 M which is positive if M < 2 22-12-1
1 1- B
1 B
Dividing by aT, using Jensen's inequality and averaging finishes the proof, with the rate
Σ [lf(wx) - f(w")] s 1- 3
1 +
(
2
1+3 -1
D2 + Mo²
1 1 3
Mmmn T
32

---

Under review as a conference paper at ICLR 2021
E.3 PROOFS FOR AMSGRAD WITH HEAVY BALL MOMENTUM
We now give the proof's for AMSGrad with heavy ball momentum with the update.
Wk+11 = wik A V fig (wx) + + (wy -w
We analyze it in the smooth setting using a constant step-size (Theorem 11), conservative Armijo SPS (Theorem 12) and conservative Armijo SL. (Theorem 13). As before, we abstract the common clements to general proposition and specialize it for each of the theorems.
Proposition 4. In addition to assumptions of Theorem I, assume that (iv) the preconditioners are non-decreasing and have (v) bounded eigenvalues in the [Amin amaxx range. the step-sizes are lower-bounded and non-increasiing, 1/min S 1/k S Ti and satisfy
Tke f (wx M S (M((((w)) fil, for some M <2 2%
(11)
AMSGrad with heavy ball momentum with parameter < 1 and uniform averaging ur Ei=n Wy leads the rate
1 T
2(1 + DD2 amaxd
+ +2]lf(wo)- [(""" + Mo²
B[f(wT) - f 2- 27 2- M
7mmin
We first show how the convergence rate of each step-size method can be derived from Proposition 4.
Theorem 11. Under the assumptions of Theorem I and assuming (iv) non non-decreasing precondi- tioners (v) bounded eigenvalues in the [Omins amax range, AMSGrad with heavy ball momentum with parameter 7 E [0, 1), constant step-size 20min (1-2) and uniform averaging converges at a rate
SLmax
37 [[S(wT) - |+ T 2 (1 7)2 Tnmax Dand + (1 71-
1 1/9 1+ 7+
(1-
(f(ro) - ([((uuo)-ffa [(ww)) + 20
Proof of Theorem 11. Using Bounded preconditioner and Individual Smoothness, we have that
V fúg (w)) I1 S /i (wx)ll < 2Lmax (fi (wx) fiJ)
amin
amin
A constant step-size 17 = 20mm (1 (1-7)/3Lma means the requirement for Proposition 4 is satisfied with
M (1 7). Plugging (2 27 M) 3 - 7) Proposition 4 finishes the proof.
Theorem 12. Under the assumptions of Theorem 1 and assuming (iv) non-decreasing precondi-
tioners (v) bounded eigenvalues the [Amins Gmax interval, AMSGrad with heavy ball momentum with parameter 7 E [0, 1), conservative Armijo SPS with 3/4(1-7) and uniform averaging converges at a rate,
9 1 72 (L T 7)2 Lmaa kd +
3y (1 71-7) ([(() - [[w[)) + 202
Proof of Theorem 12. For Armijo SPS, Lemma 2 guarantees that and
T) f (w))1 S 1 (f,, (wk) -fū);
amin S 7Jp-
2c L
Selecting e = 3/4(1-2) gives M = 1/3(1 -7) < 7)) and the requirement of Proposition 4 are T/nin and M are the same
satisfied. The minimum step-size is then Tuiin 2e 3T.max as in the constant step-size case (Theorem 11) and the same rate applies.
20min (1-7)
Theorem 13. Under the assumptions of Theorem I and assuming (iv) non-decreasing precondi- tioners (v) bounded eigenvalues in the [amins amax] interval, AMSGrad with heavy ball momentum with parameter 7 E [0, 1/4), conservative Armijo SLS with 3/4(1-7) and uniform averaging
33

---

Under review as a conference paper at ICLR 2021
converges at rate,
1 1 72 Bif(@r) 1- 1 T 6 47 Liaa D' 37 (1 (1- ( f((w0)] + 20².
(0]
Proof of Theorem 13. Selecting 3/4(1->) is feasible if < 1/4 as < The Armijo SLS (Lemma 1) then guarantees that
Th V.. (mw)) S - (fr, (wk) fi.),
2(1 c) amin
and
S 1).
Linax
which satisfies the requirements of Proposition 4 with M = [1 7). Plugging M in the rate yields
(6 1 72 Blf(wT) - f[(w"]] T
1
Ddumaxe
37 (1->) [f(wo) - f((w))) 20
Mmin
With c
3/4 T-g; Muin 2 2(1-c)amin
2amin 1-48 I.max
Plugging into the above bound yields
T.max
4(1
1 1+
3y _y (1 (1-7)1((00) (/(w)))) - f(w")] 20
[[S(wT) - f(w)(()))))))))) s
6
Lmax D²
4y
We now move to the proof the main proposition. Our proof follows the structure of Ghadimi et al. (2015); Sebbouh et al. (2020).
Proof of Proposition 4. Recall the update for AMSGrad with heavy-ball momentum,
wk+11 Wk T)k A Si, (wx) + 7(wk wk-1)--
(12)
The proof idea is to analyze the distance from w" to Wy and a momentum term,
|| = w + my - w= 11
where my = 1 22x Wk-1),
(13)
by considering the momentum update (Eqq. 12) as a preconditioned step on the joint iterates (wx + mm))
The Wk+1 + m&+1 = Wi + my 1 A V fú, (wk).
(14)
Let us verify Eq. (14). First, expressing Wh+1 + mg+1 as weighted difference of wx+1 and Wi.
Wk+1 + m&+1 = Wh+1 + 1,, - wx) - Wk41 I-y Wk.
Expanding Wh41 in terms of the update rule then gives
I- (wi - A (wk) + 7(wx - wk wk- I- Wk:
(wk Tkk V
fic (wx) -1)
Wk - wk-
n 1-
A V.s (wx).
which can then be re-written as wy + m. 1- A follows similar steps as the analysis without momentum. Using Eq. (14), we have the recurrence
V f. (Wx). The analysis of the method then
fig (wk) w" 2
| l2 = ||wx-1 + m++1 w 112 = wk + m.
m I-
A
(15)
= 111 2TTK
(wx), we + my w*) +
I fi, (w (w
(1
To bound the inner anorrpp we use Individual Convexity to relate it to the optimality gap.
(V Sig. (wx), wk m4 w²) (Vii (wk), wi w²) + 7 1-7 (V V/i (wkk,, wa wk-1);
> fig (ww) fix (ww + 1- [f,, (wn) fic (wk-1))1
7
[fi, (wx) Sr. (w))
1 1- [f.,
1~1 (wk-1) - Sig (w)))
7
34

---

Under review as a conference paper at ICLR 2021
To bound the gradient norm, the step-size assumption that
Te Six (wx) )ll S Mi (wn) - fiJl = Jin (ww) - Sin (w=)] + M Miii((') -fill
For simplicity of notation, let define the shortcuts he(w)) feg (w) Jú, (w"),
= fin("("") Shae
Plugging those two inequalities in the recursion of Eq. (15) gives
| I ||0x112a
(1 7)2 (2 M))a((w)) + (1 7) he (wkk)) + (1 7)2 ok-
T/
21tk7
MaR
We now divide by nu/(1-7)2 and reorganize the inequality
(1 (1-3)² (IóRIlãA ||0ut + Mo
(2 ())(((w)))) 27/4(
(wk-1) S
Tlk
Taking the average over all iterations, the inequality yields
T
(1 (1->)² (110811a. -100-1113e) Mo
Σ (2 ()s) 2 (wx- S
T
T]
To bound the right-hand side, under the assumption that the iterates are bounded by ||20g - w0 S D. we use Young's inequality to get a bound on 1|x=
| = | + m. ==11
-11- (wi
1 (w:e - =00 - -1- 1- (Wk-1 - w=*) |
2
2(1 + 72) D2 3
|l0ck w=11 112 + 72 ||wke- w0 112)
7)3
21-
Given the upper bound | 11212222 A, reorganization of the sum lets apply Lemma 3 to get
Σ 1 (1ów112.. - -188+11 112. = Σx= ||6R|
2
-/ km |
122
Ax -
Ax
Σx
|18x
2-
||8ull 2
Ax
1 Ax
74-1
$ Σ ==
||8
2
AA
Ak
Σド=
||
Ak-1
||0 11
Ao
w/
No
Σ ||6
l|
20 aaaaadd
A
Ak-1
7/
76
where the last step uses the convention Ao = 0 and Lemma 3 on òn instead of wv w" Plugging this inequality in, we get the simpler bound on the right-hand-side
Σ 2 (w)) 27 < 2(1 + amaxd
T
+ Mo
T
T'mmn
1=1
Now that the step-size is bounded deterministically, we can take the expectation on both sides to get
Σ (2 M)h(wx) 2Yh(wx-1) < 2(1 + +22) Mo²
T
Thmin
where hww)= = fww f and 0² = E. [ft,, (w*) [- To simplify the left-hand-side, we change the weights on the optimality gaps to get a telescoping sum,
Σin M)h((u) 27h(wx-11 = E2 27 - -M)((ux) + 2yh(ww) 27h(wx-1).
(2 2 27 M) LT h(ww))
+ 22(h((T)) h(wa)),
(2 2 M) EE M(wk)
-2hh(wo).
35

---

Under review as a conference paper at ICLR 2021
The last inequality uses h(wr) 2 0. Moving the initial optimality gap to the Light-hand-sid,, get
1 12 112-27- 27 2 M) h(w))
2(1
D2
amaxd 27t((wo) Mo?
$ T
7min
Assuming 2 2-2 M and dividing, we get
112(1 72) + 27h((oo)) Mo²2
T
Σ h h(wk)
S 2 2 2n M
Mmmin
Using Jensen's 's inequality and averaging the iterates finishes the proof.
36

---

Under review as a conference paper at ICLR 2021
F EXPERIMENTAL DETAILS
Our proposed adaptive gradient methods with SLS and SPS step-sizes presented in Algorithms and 3. We now make a few additional remarks on the practical use of these methods.
Algorithm Adaptive methods with SLS(S, precond, 8, conservati ive, mode, wop Tmaaxs
(0, 1), < 1)
1: for = O...., T do
2:
in <- sample mini-batch of size b
3:
Aş - precond(k)
Form the preconditioner.
4:
if' modd Lipschitz then
5:
Pk - V fi. (w))
6:
else mode Armi jo then
7: Pk + A V f., (w%)
8: end
9: if conservat ive then
k 0) then
11:
7 f 7max
12:
else
13:
7 77k-1
14:
end
else
16:
1Jk: -- 7mmax
end
18:
while fuc - 7h6 Pho) > frz (wk) TTK (V (wk), Pk) do
b> Line-search loop
17K t7TT
20: end while
me + 1.mm-11 + (1 BBV (wk)
Wk+1 Wx Th -
23:
end for
24: return WT
Algorithm reset(y), 7maxx k, n, 7, opt)
1: if h 0 then
2: return Tmax
3: else if opt= 0 then
4: 1) 6- 7)
5:
else if opt= then
6: <- 7/ b/n
7: else if opt: then
8:
< 7mnx
9: end if'
10: return
As suggested by Vaswani et al. (2019b), the standard backtracking search can sometimes result in step-sizes that are too small while taking bigger steps can yield faster convergence. To this end, we adopted their strategies to reset the initial step-size at every iteration (Algorithm 2). In particular, using reset option corresponds to starting every backtracking line search from the step-size used in the previous iteration. Since the backtracking never increases the step-size, this option enables the "conservative step-size" constraint for the Lipschitz line-search to be automatically satisfied. For the Armijo line-search, use the heuristic from Vaswani al. (2019b) corresponding to reset option 1. This option begins every backtracking with slightly larger (by factor of >//". 7 throughout our experiments) step-size compared to the step-size at the previous iteration, and works well consistently across experiments. Although we do not have theoretical guarantees for Armijo
37

---

Under review as a conference paper at ICLR 2021
SLS with general preconditioners such Adam, experimental results indicate that this is in fact a promising combination that also performs well in practice.
Algorithm Adaptive methods with SPS(/, [ precond, i.conservative, mode, Wp.
mmax
1: for = ...... T do
2:
4 sample mini-batch of size b
3: As + precond(k)
Form the preconditioner
4:
mode Li Lipschitz then
5:
Pk 4- VS. (w))
6:
else mode Armi jo then
7: Pk + A V fig (wk)
8:
end
9: if conservat i ve then
10: ifk 0 then
11:
f)B 7/max
12:
else
13:
7 9
14:
end
15:
else
16:
I]B f- 7max
end if
TK + min { f.g ((.))-fi))
18:
c(V pw)) 7B
my 8m + (1 V (wk)
Wk+1 wk A -
21: end for
return WT
On the other hand, rather than being too conservative, the step-sizes produced by SPS between successive iterations can vary wildly such that convergence becomes unstable. Loizou et al. (2020) suggested to use a smoothing procedure that limits the growth of the SPS from the previous iteration to the current. We use this strategy in our experiments with 7 = 2"/" and show that both SPS and Armijo SPS work well. For the convex experiments, for both SLS and SPS,
0.5 as is suggested by the theory. For the non-convex experiments, we observe that all values c E [0.1, 0.5] result in reasonably good performance, but use the values suggested in Vaswani et al. (2019b); Loizou et al. (2020), i.c. = 0.1 for all adaptive methods using SLS and = 0.2 for methods using SPS.
38

---

Under review as a conference paper at ICLR 2021
G ADDITIONAL EXPERIMENTAL RESULTS
In this section, we present additional experimental results showing the effect of the step-size for adaptive gradient methods using synthetic dataset (Fig. 4). We show the wall-clock times for the optimization methods (Fig. 5). We show the variation in the step-size for the SLS methods when training deep networks for both the CIFAR in Fig. and ImageNet (Fig. 7) datasets. We evaluate these methods on easy non-convex objectives classification on MNIST (Fig. 8) and deep matrix factorization (Fig. 10). We use deep matrix factorization to examine the effect of over-parameteriizatonn on the performance of the optimization methods and check the methods performance when minimizing convex objectives associated with binary classification using RBF kernels in Fig. 9. Finally in Fig. 11, quantify the gains of incorporating momentum in AMSGrad by comparing against the performance AMSGrad without momentum.
Morgin:o.01
M.rgin:0.05
Margin:0.1
Margin
10a
107
Then (og)
2.0
10
10-1
10-1-
10
10-2
19
10
10-1
100
50
100
150
200
Epacc
Spoch
Spach
Epach
Adag
Detault Adagrad
Acugeaz Losch
Adugrad
(a) AdaGrad
Margin:0.00
Margin:0 0.05
Margin0011
Margin:0.5
10
1.0
107
10
109
10-4
10
Trann
10-1
10
10-4
10
10
100 #poch
150
200
50
100 Fporn
150
200
50
100
150
200
100
150
250
1pacn
Fpncch
(b) AMSGrad
Figure 4: Effect step-size on the performance of adaptive gradient methods for binary classification on linearly separable synthetic dataset with different margins. We observe that the large variance for the adaptive gradient methods, and the variants with SLS have consistently good performance across margins and optimizers.
39

---

Under review as a conference paper at ICLR 2021
CIAR10
ResNet34
113.397
Amsgrad
Average traiiigg timalpen
100
91,609
Amsgrad SLS HB
Adagrad SL5
Adabound
80
77.038
75.312
77,012
62.962
63.203
Adam
60-
S1S
20
a
OFAR100 DenseNet121
Avsrage training tmelogod
Amssgred 318
Adagrad SLS
200
203.612
221.197
Adabound
Adam
150
SLS
98.330
87.487
108.076
Methoos
CIAR100 ResNet34
Rverage traniing timeeepph
Amsgred
Adagrad SLS
80
75:188
Adabound
60
SLS
31.368
26.686
20
Methoos
(c)
Tiny ImageNet
175
Amsgrad + 515
Amsgrad S15
150
125
126.805
115:225
Radam
Adam
1.00
82.629
Adagrad
75
Aveage
50
25
Methoos
Figure 5: Runtime (in seconds/epoch) for optimization methods for multi-class classification using the deep network models in Fig. 2. Although the runtime/epoch larger for the SLS/SPS variants, they require fewer epochs to reach the maximum test accuracy (Figure 2). This justifies the moderate increase in wall-clock time.
40

---

Under review as a conference paper at ICLR 2021
CIFARIO N44
CIFAR10-ResNet34
GFFAR10-RcENe333
100
100
(log)
Stop $28 (log)
10-
Validation V
10-4
10:10
10:14
50
Epoch
Epoch
Adagrad
Adabound
Radam
Adam
SLS
Amsgred
Amsgrad
(a) CIFAR-10 ResNet
CIFARIO-
CIFARIO NeDDesseNel211
10a
Tra loss (10g)
Stop size (log]
20
Valdaaion
--
0.00
10-9
10
16-12
50
1.00 Epoch
150
200
50
100 Epach
150
200
50
100 Epoch
150
200
Adagrad
SLS
Amsgrad
Amsgrrd
CIFAR-10 DenseNet
0.76
10a
0.74
Train 00t (kg)
Stop size (og)
30-1
20-4
10-4
10:2
50
1:00
150
200
50
1000
350
200
50
100 Epoch
150
200
Epoch
Epoch
Adagrad
SLS
Amsgrad +
Amsgrad
(c) CIFAR-100 ResNet
CIFARIDO DenseNet121
CIFRR1OD De
CIFAR100 CIFAR100 NenseNet121
0.76
10a
0.74
300
Train Ioss 00g1
St0p size (log)
20-1
0.72
20
10
20
10-4
10
10"*
50
100
150
200
100
150
200
50
100
150
200
Epoch
Epach
Epoch
Adagrad
SUS
Adabound
Ro dam
Adam
SLS
Amsgrad + 5L5
Amsgrad SL5 HB
(d) CIFAR- 100 DenseNet
Figure 6: Comparing optimization methods image classification tasks using ResNet and DenseNet models on the CIFAR- 10/10//100 100 datasets. For the SLS/SPS variants, refer to the experimental details in Appendix For Adam, we did a grid-search and use the best step-size. We use the default prrerrparameters for the other baselines. We observe the consistently good performance of AdaGrad and AMSGrad with Armijo SLS. We also show the variation in the step-size and observe a cyclic pattern (Loshchilov & Hutter, 2017) an initial warmup in the learning rate followed by decrease or saturation to a small step-size (Goyal et al., 2017).
41

---

Under review as a conference paper at ICLR 2021
Imagewoof-ResNeil
Imagewoof-ResNelll
Rnngewoof-RReNNil3
10"
100
0.675
10
"o.450
(lgg
30
10
10-2
0.575
0.400
10-4
10
0.550
10
0.525
10-4
0.500
Adlebound
Radam
Adam
Amsggrad SLS
Adagrad SLS
Arsigrad SLS
(a) Imagewoof
Imagenetbe
0.84
Imagenette
Imagenette
0.83
M
0.81
Step (te
1.0-
0.80
10-4
momtrr
0.78
10.4
10"
0.76
20
60
80
100
20
40
80
100
20
40
80
100
Epoch
Epoch
Epoch
Amagradi
Adagrad
Amsgrad
(b) ImageNette
Tiny Imag eNet. ResNet18
Tiny ImageNet ResNet18
Tiny Ima geNet ResNet18
0.40
107
Train loss Ibgi
10-1
0.38
St5 sibe (10g)
30-
0.36
10-5
0.34
50
1.00
125
150
175
200
50
1.00
150
2000
50
100
150
200
Epoch
Ep
Epoch
Adabound
Radam
-
Adam
5LS
Amagrad SLS
Adagrad 515
Amsgrad SL5 HB
(c) Tiny Imagenet
Figure 7: Comparing optimization methods on image classification tasks using variants of ImageNet. We use the same settings the CIFAR datasets and observe that AdaGrad and AMSGrad with Armijo SLS is consistently better.
MNIST
MNIST
MNIST
10a
10F
Validation sccurac)
10-1
Itain loss (log)
10
0.982
10
10-2
10-3
10
Stop
10
0.978
10-4
0.976
Epoch
Epoch
Adabound
Adagrad
Amagrad Amsgred
Figure 8: Comparing optimization methods on MNIST.
42

---

Under review as a conference paper at ICLR 2021
mushrooms
10-4
Train Trainloss (log)
10
10"
10-3
10-2
10
Eppcc
Adagrad
Amsgrad
Amagrad
Figure Comparison of optimization methods on convex objectives: binary classification on LIBSVM datasets using RBF kernel mappings. The kernel bandwidths chosen by cross- cross-validation following the protocol in (Vaswani et al., 2019b). All line-search methods use c = 1/2 and the procedure described in Appendix F. The other methods convergence of the SLS variants and the poor performance of the baselines.
their default parameters. We observe the superior
True model
Rank
Rank
Rank
10-4
6.301
Train loss (lg)
10
10-1
10-7
10
20-10
10
10-1
10-33
10-2
50
Adabound
Adagrad
Amssgrad
Figure 10: Comparison of optimization methods for deep matrix factorization. Methods use the same sarrmmprrretter settings as above and we examine the effects of over prrrraatttttiiiooooonn on the problem: minw,, ,w, Ex,,)(o.)) W,W Az| (Vaswani et al., 2019b; Rolinck Martius, 2018). choose 1006 with condition number x(A) = 10 and control the over-parameterization via the rank & (equal to 1,4, 10) of W1 * and W2 E R10x We also compare against the true model. In each case, we use a fixed dataset of 1000 samples. We observe that as the over- parameterization increases, the performance of all methods improves, with the methods equipped with SLS performing the best.
43

---

Under review as a conference paper at ICLR 2021
CIFARIO ResNet34
DenseNet121
CIFAR100 ResNet34
Tiny ImageNet ResNet18
207
10a
109
20"
Train loss 0ogi
10
10
10-1
20-4
10
10-4
10
10:3
1000
150
200
200
2.00
150
Epoch
Epoch
Epoch
Epoch
CIFAR10
ResNeI34
CFAR100
CIFAR100 ResNel34
Image ResNet18
Vallidatinn acouracy
0.92
0.37
0.90
0.68
0.68
0.35
0.66
0.66
100
150
200
50
100
150
200
50
100
150
200
50
200
150
200
Epech
Epoch
Spoch
Epoch
Adagrad
Amegrad
Amagrad
Adagrad
Figure 11: Ablation study comparing variants of the basic optimizers for multi-class classification with deep networks. Training loss (top) and validation accuracy (bottom) for CIFAR- 10, CIFAR- 100 and Tiny ImageNet. We consider the AdaGrad with AMSGrad-lin like momentum and do find improvements in performance. We also benchmark the performance of AMSGrad without momentum, and observe that incorporating AMSGrad momentum does improve the performance, whereas heavy- ball momentum has a minor, sometimes detrimental effect. We use SLS and Adam benchmarks to study the effects of incorporating preconditioning vs step-size adaptation.
44


Reviews:
[{"review_id": "ka-KZZOhvcq", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes adaptive algorithms such as adagrad and AMSGrad in a finite-sum optimization problem. The proofs appear to treat this setting through online convex optimization and online-to-batch conversion. It is shown that both AdaGrad and AMSGrad improve when the individual losses are all minimized at the same point. Further, line search techniques are analyzed in conjunction with these algorithms, and empirical results show that in practice the line searches speed up convergence.\n\nI do not think Theorem 1 is particularly novel. I am not sure of an original reference (it may be a kind of folklore), but see for example https://parameterfree.com/2019/09/20/adaptive-algorithms-l-bounds-and-adagrad/ theorem 7, from which it is trivial to deduce Theorem 1 by observing that WLOG we may assume f_i^*=0 for all i since subtracting the minimum value does not change the gradients.\n\nFor Theorem 2, I may be missing something. This value of alpha seems *strictly worse* than what we would get in Theorem 1 by just setting eta=eta_max. So what is the line search buying us? Is it just for empirical performance with no theoretical benefit yet? It is not obviously presented this way, so if so I think some remarks to this effect are in order.\n\nThe assumption on bounded eigenvalues for the results on AMSGrad seems a little troublesome to me: I am worried that all of the adaptive nature of the preconditioner is irrelevant and these assumptions are doing all the heavy-lifting. Indeed, if we set \\beta=0, then with learning rate \\eta = a_min/L and sgd update w_{t+1} = w_t - eta * V^(-1) g_t for *any* V in [a_min, a_max], then I suspect that standard analysis of gradient descent using learning rates at most 1/L will yield fairly similar results to Theorem 3. I would be happy to hear otherwise, though!\n\nMy overall feeling is that there is a missing piece here in the theory to show that the line search is useful. I am not confident that the other results are significant on their own. \n\nAs for the empirical results, these seem like reasonable gains over Adam. I would have preferred to see more standard deep learning benchmarks on non-image tasks as well,, but I am not an expert here and so would defer to other opinions.\n\n\nNits:\nI am not sure that the assumption that the iterates are bounded is well justified here. I do believe it has been assumed in some past literature, but this does not make it actually true. It is certainly *not* standard in the literature on online learning. The two references (Duchi et al 2011 and Levy et al 2018) cited as evidence here do not actually assume this. Instead, they use projections to *ensure* that the iterates are bounded without assumptions.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "bawcqX8l03", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies adaptive gradient methods under the over-parametrized settings, where the authors study the converge in the interpolation setting. In this setting, the optimal objective is 0. The authors show that the convergence rate is O(1/T). In addition, when the interpolation is approximately satisfied, the authors show the convergence to a neighborhood of the solution. The authors also provide theoretical justifications for popular line search methods.\n\nOverall, I find the paper easy to read. However, I do have a few questions that would like to see the authors' answers:\n\n1. The authors implicitly assume that the optimal solution is unique.  However, this is not the case in many over-parametrized models. For example, consider the case for logistic regression where the two classes are perfectly separable. The minimizer is not well defined, but there have been extensive work on this topic. Can the authors' analysis adapt to such situations? \n\n2. Taking the logistic regression as an example again, the \"minimizer\" is not within a bounded region. Can the authors' analysis been adopted to analyze such case?\n\n3. The result are all in the form of expectation. Can the authors bound the L2-norm?\n\n4. I think it would be informative to add the result when the loss is strongly convex, where we can have the bound for the solutions.", "extra_scores": {}, "extra_text": {}}, {"review_id": "UIi7TeuUY6T", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "##########################################################################\n\n\nSummary:\n\nThis paper studies the convergence of adaptive gradient methods under an interpolation assumption, showing for example these methods can converge at an O(1/t), instead of O(1/\\sqrt{t}) rate when perfect interpolation is satisfied. Convergence behaviors with line search and Polyak step sizes are also analyzed. \n\n\n##########################################################################\n\n\nReasons for score: \n \n\nThis paper provides good insights regarding how an interpolation assumption may help accelerate adaptive gradient methods. I do not feel the technical results very solid, as some difficult-to-check properties are just put as assumptions (see cons). \n\n\n##########################################################################Pros: \n \n\nPros: \n\n1. The results provides insights regarding why adaptive gradient methods may converge faster when the interpolation assumption is satisfied.  \n\n2. Line search and Polyak step size methods help address the need of problem and algorithm parameters in standard theories. Moreover, there are few papers discussing line search and Polyak step size methods in the finite-sum setup.  \n\n3. The Polyak step size is well-motivated in the interpolation setting. \n \n\n##########################################################################\n\nCons: \n\n1. The abstract claims that “AdaGrad can achieve an O(1) regret in the online convex optimization framework.” I do not see this result in the main text.\n\n2. The paper reads waiving regarding difficult-to-check assumptions. In particular, this paper assumes the sequence of iterates is bounded in a set of radius D and the eigenvalue of the preconditioning matrices are bounded. The main argument supporting these assumptions are simply they are “common” in existing literature. I feel the technical challenges in the analyses are alleviated a lot because of these “common” assumptions.   Notice that without the conditions, the convergence guarantees may not be meaningful because the D parameter in all theorems and a_{min} and a_{max} in Theorem 3 and Theorem 4 can scale with the iteration counter.  \n\n3. The proposed line search methods seem to be computationally very expensive. The proposed line search methods require computing the largest step size satisfying the desired inequality, instead of the *largest among a sequence of exponentially decaying step sizes* as in standard Armijo line search methods. Is it possible to analyze the performance of latter—more computationally favorable—scheme? \n\n4. It is claimed that the step size chosen by the proposed conservative Lipschitz line search method is bounded in [2 (1 - c) / L_{max}, \\eta_{k - 1}]. Can it happen that \\eta_{k - 1} \\leq 2 (1 - c) / L_{max}? If yes, then is the step size selection rule well-defined? There is also a similar claim for the stochastic Armijo line search method.  \n\n5. I don’t get the sentence that “a similar distinction between the convergence of constant step-size Adam (or AMSGrad) vs. AdaGrad has also been recently discussed in the non-convex setting (Défossez et al., 2020)” in Section 4. What is the distinction?  \n\n6. Minor comment: \n    1. Typo in the first paragraph: online batch reduction -> online-to-batch reduction\n    2. m_1 is not specified in (1). \n    3. The abbreviation SPS is not defined when it appears for the first time in the main text.  \n\n##########################################################################\n\nAfter reading author rebuttal: \n\nI think the value of this work is to demonstrate the possible benefits of an interpolation assumption. Hence, though there are some theoretical issue and theory-practice gap, I keep the original score. \n\n- I do not feel it very reasonable to emphasize the regret result in the abstract and then put the corresponding section in the appendix. It is more reasonable to move Appendix C.2 to the main text though I guess it would be difficult in practice. \n\n- I understand adding a projection step typically does not change the proof much. However, this is not the setup analyzed in this paper. I feel the associated newly-added clarification in Section 2 reads somewhat waiving. I suggest the authors add some clarifications in the revision similar to the following in the rebuttal. \n\n\"Without an explicit projection step, we believe it is possible to adopt the recent SGD analysis \"On the almost sure convergence of stochastic gradient descent in non-convex problems, NeurIPS, 2020.\" to prove that the iterates do remain bounded with high-probability. We leave this for future work.\"\n\n- The other clarifications are OK to me. \n\n- I suggest the authors add some clarification regarding 4 in the main text. \n \n\n#########################################################################", "extra_scores": {}, "extra_text": {}}, {"review_id": "5Xns0rKrA8h", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper revisited two important stochastic algorithms, AdaGrad and AMSGrad. It reanalyzes these two algorithms under interpolation setup and shows how the results get improved under this particular case.\n***\nStrength: interpolation setup is reasonable in over-parametrized regime. This paper establishes a thorough analysis on AdaGrad and AMSGrad under the interpolation setup. Further, it incorporates the stochastic line search technique and stochastic Polyak stepsize technique with AMSGrad to make the stepsize selection adaptive. The improvement results and the dependence on the extent of interpolation violation seem interesting.\n***\nConcerns: why do the authors not consider the unconservative stochastic line search and Polyak for AdaGrad. Also, I'm wondering what's the technical challenges to reestablish these results. Is that simply combining the classical analysis with the previous work (Vaswani et al. 2019 Painless stochastic gradient: Interpolation, line-search, and convergence rates). The stepsize lies in a bounded interval lower bounded away from zero, so that the randomness of stepsize is well controlled. \n***\nFor future improvement, I think authors should emphasize the difficulty of the analysis more clear. Based on my reading, authors list comprehensive results while how significance of these results is less discussed. It would be good to provide a general proof framework to make \"how interpolation helps on a sharper analysis\" more clear.\n\n   \n***\nDuring rebuttal:\nThe authors should highlight some technical difficulties in the paper. In principle, stochastic line search under overparameterized regime does not make things harder because the stepsize is lower bounded. The difficulty of stochastic stepsize is to control the product of stepsize and gradient, while under this regime the product is separable. It seems the analysis of momentum plus this observation is enough for the analysis. It would be useful to provide some insights and challenges of the analysis.\n\n  ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear authors,

the paper contains many interesting and novel ideas. Indeed, tuning step-size is very time and energy-consuming, and deriving and analyzing new adaptive algorithms has not only theoretical benefits but, more importantly, is a key when training more complicated ML models.

The paper contains many weaknesses as noted by reviewers. I know that you have addressed many of them one of the reviewers is still concerned about the other issues involving Theorem 1 and the assumption of the bounded preconditioner.
He thinks the preconditioner bound is troublesome. In the overparameterized regime, he would expect the gradients to become near zero as the algorithm converges, which would actually cause the preconditioner to NOT be bounded below. It seems that the analysis might actually improve if the authors abandoned AMSGrad/Adam and instead just considered SGD for which the preconditioner assumption is not an assumption but just a property of the algorithm.





Thank you  
Decision: Reject