Year: 2020

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.

heading: 1 INTRODUCTION
text: 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 et 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; Défossez et al., 2020; Staib et al., 2019). An online–batch reduction gives guarantees similar to stochastic gradient descent (SGD) in the offline setting (Cesa-Bianchi 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 variants (Kingma & Ba, 2015; Reddi et al., 2018), a 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., 2011) has been shown to be “universal” as it attains the best known convergence rates in 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 to converge to the solution with a constant step-size and momentum parameter.
Another inconsistency is that although the standard theoretical results are for non-smooth functions, these methods are also extensively used in the easier, smooth setting. More importantly, adaptive gradient methods are generally used to train highly expressive, large over-parameterized models (Zhang et al., 2017; Liang & Rakhlin, 2018) capable of interpolating the data. However, the standard theoretical analyses do not take advantage of these additional properties. On the other hand, a line of recent work (Schmidt & Le Roux, 2013; Jain et al., 2018; Ma et al., 2018; Liu & Belkin, 2020; Cevher & Vũ, 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 a 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-parameterized models.

heading: 1.1 BACKGROUND AND CONTRIBUTIONS
text: 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/T + ζ/ √ T) convergence rate, where T is the number of iterations and ζ2 is a global bound on the variance in the stochastic gradients. This convergence rate matches that of SGD under the same setting (Moulines & Bach, 2011). In Section 3, we show that constant step-size AdaGrad also adapts to interpolation and prove an O(1/T + σ/ √ T) rate, where σ is the extent to which interpolation is violated. In the over-parameterized setting, σ2 can be much smaller than ζ2 (Zhang & Zhou, 2019), implying a faster convergence. When interpolation is exactly satisfied, σ2 = 0, we obtain an O(1/T) rate, while ζ2 can still be large. In the online convex optimization framework, for smooth functions, we show that the regret of AdaGrad improves from O( √ T ) to O(1) when interpolation is satisfied and retains its O( √ T )-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(1/T) under interpolation (Section 4). However, unlike AdaGrad, it requires specific step-sizes that depend on the problem’s smoothness. More generally, constant step-size AMSGrad converges to a neighbourhood of the solution, attaining an O(1/T + σ2) rate, which matches the rate of constant step-size SGD in the same setting (Schmidt & Le Roux, 2013; Vaswani et al., 2019a). When training over-parameterized models, this result provides some justification for the faster (O(1/T) vs. O(1/ √ 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 is 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, we experimentally show that even for simple, convex problems, the step-size has a big impact on the empirical performance of AdaGrad and AMSGrad. To overcome this limitation, we use recent methods (Vaswani et 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 SLS 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.

heading: 2 PROBLEM SETUP
text: We consider the unconstrained minimization of an objective f : Rd → R with a finite-sum structure, f(w) = 1n ∑n i=1 fi(w). In supervised learning, n 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 to 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-art 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∗i , respectively. Furthermore, we assume that each function fi in the finite-sum is Li-smooth, implying that f is Lmax-smooth, where Lmax = maxi Li. We also make the standard assumption that the iterates remain bounded in a ball of radius D around a global minimizer, ‖wk − w∗‖ ≤ D for all wk (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 a 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∗, ∇f(w∗) = 0, then for all fi we have ∇fi(w∗) = 0. The interpolation condition can be exactly satisfied for many over-parameterized machine learning models such as non-parametric kernel regression without regularization (Belkin et al., 2019; Liang & Rakhlin, 2018) and over-parameterized deep neural networks (Zhang et 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 f∗i , σ2 := Ei[f∗ − f∗i ] ∈ [0,∞) (Loizou et al., 2020). The minimizer of f need not be unique for σ2 to be uniquely defined, as it only depends on the minimum function values. Interpolation is said to be exactly satisfied if σ2 = 0, and we also study the setting when σ2 > 0.
For a preconditioner matrix Ak and a constant momentum parameter β ∈ [0, 1), the update for a generic adaptive gradient method at iteration k can be expressed as:
wk+1 = wk − ηk A−1k mk ; mk = βmk−1 + (1− β)∇fik(wk) (1) Here, ∇fik(wk) is the stochastic gradient of a randomly chosen function fik , and ηk is the step-size. Adaptive gradient methods typically differ in how their preconditioners are constructed and whether or not they include the momentum term βmk−1 (see Table 1 for a list of common methods). Both
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 Ak+1 Ak 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 Ak+1 Ak and the convergence of iterates. Consequently, our theoretical results focus on 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 Ak is a diagonal matrix) of these methods, we use only the latter in experiments for scalability. The diagonal variants
perform a per-dimension scaling of the gradient and avoid computing the full matrix inverse, so their per-iteration cost is the same as SGD, although with an additional O(d) memory. For AMSGrad, we assume that the corresponding preconditioners are well-behaved in the sense that their eigenvalues are bounded in an interval [amin, amax]. This is a common assumption made in the analysis of adaptive methods. Moreover, for diagonal preconditioners, such a boundedness property is easy to verify, and it is also inexpensive to maintain the desired range by projection. Our main theoretical results for AdaGrad (Section 3) and AMSGrad (Section 4) are summarized in Table 2.

heading: 3 ADAGRAD
text: For smooth, convex objectives, Levy et al. (2018) showed that AdaGrad converges at a rate O(1/T + ζ/ √ T), where ζ2 = supw Ei[‖∇f(w)−∇fi(w)‖2] is a uniform bound on the variance of the stochastic gradients. In the over-parameterized setting, we show that AdaGrad achieves the O(1/T) rate when interpolation is exactly satisfied and a slower convergence to the solution if interpolation is violated.1 The proofs for this section are in Appendix C.
Theorem 1 (Constant step-size AdaGrad). Assuming (i) convexity and (ii) Lmax-smoothness of each fi, and (iii) bounded iterates, AdaGrad with a constant step-size η and uniform averaging such that w̄T = 1 T ∑T k=1 wk, converges at a rate
E[f(w̄T )− f∗] ≤ α
T + √ ασ√ T , where α = 1 2
( D2
η + 2η
)2 dLmax.
When interpolation is exactly satisfied, a similar proof technique can be used to 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 a favourable property, the best constant step-size depends on the problem, and as we demonstrate experimentally in Section 5, the performance of AdaGrad depends on 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 ηk that satisfies the property
fik(wk − ηk∇fik(wk)) ≤ fik(wk)− c ηk ‖∇fik(wk)‖ 2 , and ηk ≤ ηk−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, c is a hyperparameter determined theoretically and typically set to 1/2 in our experiments. The “conservative” part of the line-search is the non-increasing constraint on 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 it is only used to estimate the local Lipschitz constant. Unlike the classical Armijo line-search for
1A similar result also appears in the course notes (Orabona, 2019). 2The difference between the exact and backtracking line-search is minimal, and the bounds are only changed
by a constant depending on the backtracking parameter.
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 in the range [2(1−c)/Lmax, ηk−1] (Vaswani et al., 2019b) and allows us to prove the following theorem. Theorem 2. Under the same assumptions as Theorem 1, AdaGrad with a conservative Lipschitz line-search with c = 1/2, a step-size upper bound ηmax and uniform averaging converges at a rate
E[f(w̄T )− f∗] ≤ α
T + √ ασ√ T , where α = 1 2
( D2 max { 1
ηmax , Lmax
} + 2 ηmax )2 dLmax.
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 stepsize AdaGrad, while improving its empirical performance (Section 5). Moreover, if interpolation is exactly satisfied, we can obtain anO(1/T) convergence without the conservative constraint ηk ≤ ηk−1 on the step-sizes (Appendix C.3).

heading: 4 AMSGRAD AND NON-DECREASING PRECONDITIONERS
text: In this section, we consider AMSGrad and, more generally, methods with non-decreasing preconditioners satisfying Ak Ak−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 Ak lie in the [amin, amax] range. This is a common assumption made in the analyses of adaptive methods (Reddi et 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 O(1/ √ T) 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 a decreasing momentum parameter to obtain the O(1/ √ T) rate. However, in practice, AMSGrad is typically used with both a constant step-size and momentum parameter. Next, we present the convergence result for this commonly-used variant of AMSGrad. Theorem 3. Under the same assumptions as Theorem 1, and assuming (iv) non-decreasing preconditioners (v) bounded eigenvalues in the [amin, amax] interval, where κ = amax/amin, AMSGrad with β ∈ [0, 1), constant step-size η = 1−β1+β amin 2Lmax and uniform averaging converges at a rate,
E[f(w̄T )− f∗] ≤ ( 1 + β
1− β
)2 2LmaxD 2dκ
T + σ2.
When σ = 0, we obtain a O(1/T) convergence to the minimizer. However, when interpolation is only approximately satisfied, we obtain convergence to a neighbourhood with its size depending on σ2. We observe that the noise σ2 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 in the non-convex setting (Défossez et al., 2020). Unfortunately, the final bound is minimized by setting β1 = 0 and our theoretical analysis does not show an advantage of using momentum. Note that this is a common drawback in 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 over-parameterized models, the violation σ2 is small, even when interpolation is not exactly satisfied. Another reason that constant step-size AMSGrad is practically useful is because of the use of large batch-sizes that result in a 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 on σ2b := EB;|B|=b [fB(w∗)− fB(x∗B)] where w∗B is the minimizer of a batch B of training examples. By convexity, σ2b ≤ E[‖w∗ − x∗B‖ ‖∇fB(w∗)‖]. If we assume that the distance ‖w∗ − x∗B‖ is bounded, σ2b ∝ E‖∇fB(w∗)‖. Since the examples in each batch are sampled with replacement, using the bounds in (Lohr, 2009), σ2b ∝ n−bnb ‖∇fi(w
∗)‖, showing that the effective neighbourhood shrinks as the batch-size becomes larger, becoming zero for
the full-batch variant. With over-parameterization 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 can vary considerably during the optimization. To overcome these issues, we use a stochastic variant of the Armijo line-search. Unlike the Lipschitz line-search whose sole purpose is to estimate the Lipschitz constant, the Armijo line-search selects a suitable step-size in the preconditioned 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 ηk satisfying the following conditions at iteration k,
fik(wk − ηkA −1 k ∇fik(wk)) ≤ fik(wk)− c ηk ‖∇fik(wk)‖ 2 A−1k , and ηk ≤ ηmax. (3)
The step-size is artificially upper-bounded by ηmax (typically chosen to be a large value). The linesearch guarantees descent on the current function fik and that ηk lies in the [2amin (1−c)/Lmax, ηmax] range. In the next theorem, we first consider the variant of AMSGrad without momentum (β = 0) and show that using the Armijo line-search retains the O(1/T ) convergence rate without the need to know the Lipschitz constant. Theorem 4. Under the same assumptions as Theorem 1, AMSGrad with zero momentum, Armijo line-search with c = 3/4, a step-size upper bound ηmax and uniform averaging converges at a rate,
E[f(w̄T )− f∗] ≤ (
3D2d · amax 2T + 3ηmaxσ 2
) max { 1
ηmax , 2Lmax amin
} .
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 (see 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 O( ) in the worst-case, resulting in an unsatisfactory worst-case rate of O(1/ T) even in the interpolation setting. However, like AMSGrad, AdaGrad with Armijo line-search has excellent empirical performance, implying the need for a 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:
SPS: ηk = min
{ fik(wk)− fik ∗
c ‖∇fik(wk)‖ 2 , ηmax
} , Armijo SPS: ηk = min { fik(wk)− fik ∗
c ‖∇fik(wk)‖ 2 A−1k
, ηmax
} .
Here, fik ∗ is the minimum value for the function fik .The advantage of SPS over a line-search is that it does not require a 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∗i 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∗i = 0 has been shown to yield good performance for over-parameterized 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 ηmax = ηk−1 at iteration k ensuring that ηk ≤ ηk−1. This is because using a 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-decreasing preconditioners (v) bounded eigenvalues in the [amin, amax] interval with κ = amax/amin, AMSGrad with
β ∈ [0, 1), conservative Armijo SPS with c = 1+β/1−β and uniform averaging converges at a rate,
E[f(w̄T )− f∗] ≤ ( 1 + β
1− β
)2 2LmaxD 2dκ
T + σ2.
The above result exactly matches the convergence rate in Theorem 3 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 ηmax 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 β.
When Ak = Id, the AMSGrad update is equivalent to the update for SGD with heavy-ball momentum (Sebbouh et al., 2020). By setting Ak = Id in the above result, we recover an O(1/T + σ2) 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 a general preconditioner, the AMSGrad update in Eq. (1) is not equivalent to heavy-ball momentum. With a constant momentum parameter γ ∈ [0, 1), the general heavy-ball update (Loizou & Richtárik, 2017) is given as wk+1 = wk−αk A−1k ∇fik(wk)+γ (wk − wk−1) (refer to Appendix E.1 for a relation between the two updates). Unlike this update, AMSGrad also preconditions the momentum direction (wk − wk−1). If we consider the zero-momentum 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(1/T + σ2) 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 over-parameterized deep networks.

heading: 5 EXPERIMENTAL EVALUATION
text: 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 PyTorch implementations (Paszke et al., 2019) on a binary classification task with logistic regression. Following the protocol of Meng et al. (2020), we generate a linearly-separable dataset with n= 103 examples (ensuring interpolation is satisfied) and d = 20 features with varying margins. For AdaGrad and AMSGrad with a batch-size of 100, we show the training loss for a grid of step-sizes in the [103, 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.3 and use the default (in PyTorch) momentum parameter of β = 0.9. In Fig. 1, 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.
3This corresponds to the largest allowable step-size in Theorem 4 without momentum. Unfortunately, the values of c suggested by the analysis incorporating momentum Theorem 5 are too conservative.
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 a 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 et 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 SLS.
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 c = 0.5 for all convex experiments (suggested by Theorem 4 and Vaswani et al. (2019a)). Since we do not have a 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 γ = 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. 2 we make the following observations, (i) in terms of generalization, AdaGrad and AMSGrad with Armijo SLS have consistently the best performance, while SGD with SLS is often competitive. (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 γ, whereas AMSGrad is robust to β. 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 step-size across epochs, observing a warm-up phase where the step-size increases followed by a constant or decreasing step-size (Goyal et al., 2017).
In Appendix G, we also consider binary classification with RBF kernels for datasets from LIBSVM (Chang & Lin, 2011) and study the effect of over-parameterization for deep matrix factorization (Rolinek & Martius, 2018; Vaswani et 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 to substantial empirical gains, often more than those obtained by designing a different preconditioner. Furthermore, we see that with an 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.

heading: 6 DISCUSSION
text: When training over-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 O(1/T ) rates. We proposed to use stochastic line-search techniques to help these methods adapt to the function’s local smoothness, alleviating the need to tune their step-size and resulting in consistent empirical improvements across tasks. Although adaptive gradient methods outperform SGD in practice, their convergence rates are worse than constant step-size SGD and we hope to address this discrepancy in the future.

heading: Supplementary material

heading: ORGANIZATION OF THE APPENDIX
text: A Setup and assumptions B Line-search and Polyak step-sizes C Proofs for AdaGrad
Step-size Rate Reference Constant O(1/T + σ/ √ T) Theorem 1 Conservative Lipschitz LS O(1/T + σ/ √ T) Theorem 2 Non-conservative LS (with interpolation) O(1/T) Theorem 7
D Proofs for AMSGrad and non-decreasing preconditioners without momentum
Constant O(1/T + σ2) Theorem 8 Armijo LS O(1/T + σ2) Theorem 4
E AMSGrad with momentum
Constant O(1/T + σ2) Theorem 3 Conservative Armijo LS O(1/T + σ2) Theorem 10 Conservative Armijo SPS O(1/T + σ2) Theorem 5
Proofs for AMSGrad with heavy ball momentum
Constant O(1/T + σ2) Theorem 11 Conservative Armijo LS O(1/T + σ2) Theorem 13 Conservative Armijo SPS O(1/T + σ2) Theorem 12
F Experimental details G Additional experimental results

heading: A SETUP AND ASSUMPTIONS
text: We restate the main notation in Table 3. We now restate the main assumptions required for our theoretical results
We assume our objective f : Rd → R has a finite-sum structure,
f(w) = 1
n n∑ i=1 fi(w), (4)
and analyze the following update, with ik selected uniformly at random,
wk+1 = wk − ηk A−1k mk ; mk = βmk−1 + (1− β)∇fik(wk) (Update rule)
where ηk is either a pre-specified constant or selected on the fly. We consider AdaGrad and AMSGrad and use the fact that the preconditioners are non-decreasing i.e. Ak Ak−1. For AdaGrad, β = 0. For AMSGrad, we further assume that the preconditioners remain bounded with eigenvalues in the range [amin, amax],
aminI Ak amaxI. (Bounded preconditioner)
For all algorithms, we assume that the iterates do not diverge and remain in a 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 et al., 2018),
‖wk − w∗‖ ≤ D. (Bounded iterates)
Our main assumptions are that each individual function fi is convex, differentiable, has a finite minimum f∗i , and is Li-smooth, meaning that for all v and w,
fi(v) ≥ fi(w)− 〈∇fi(w), w − v〉, (Individual Convexity)
fi(v) ≤ fi(w) + 〈∇fi(w), v − w〉+ Li 2 ‖v − w‖2 , (Individual Smoothness)
which also implies that f is convex and Lmax-smooth, where Lmax 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,
‖∇fi(w)‖2 ≤ 2Lmax(fi(w)− f∗i ).
To characterize interpolation, we define the expected difference between the minimum of f , f(w∗), and the minimum of the individual functions f∗i ,
σ2 = E i [fi(w ∗)− f∗i ] <∞. (Noise)
When interpolation is exactly satisfied, every data point can be fit exactly, such that f∗i = 0 and f(w∗) = 0, we have σ2 = 0.

heading: B LINE-SEARCH AND POLYAK STEP-SIZES
text: We now give the main guarantees on the step-sizes returned by the line-search. In practice, we use a backtracking line-search to find a step-size that satisfies the constraints, described in Algorithm 1 (Appendix F). For simplicity of presentation, here we 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 an additional safety mechanism; either by capping the maximum step-size by some ηmax or by ensuring nonincreasing step-sizes, ηk ≤ ηk−1. In this case, ηmax ensures that a bad iteration of the line-search procedure does not result in divergence. When interpolation is satisfied, those conditions can be dropped (e.g., setting ηmax →∞) and the rate does not depend on ηmax. The line-searches depend on a parameter c ∈ (0, 1) that controls how much decrease is necessary to accept a step (larger c means more decrease is demanded).
Assuming the Lipschitz and Armijo line-searches select the largest η such that
fi(w − η∇fi(w)) ≤ fi(w)− cη ‖∇fi(w)‖2 , η ≤ ηmax, (Lipschitz line-search) fi(w − ηA−1∇fi(w)) ≤ fi(w)− cη ‖∇fi(w)‖2A−1 , η ≤ ηmax, (Armijo line-search)
the following lemma holds.
Lemma 1 (Line-search). If fi is Li-smooth, the Lipschitz and Armijo lines-searches ensure
η ‖∇fi(w)‖2 ≤ 1
c (fi(w)− f∗i ), and min
{ ηmax,
2 (1− c) Li
} ≤ η ≤ ηmax,
η ‖∇fi(w)‖2A−1 ≤ 1 c (fi(w)− f∗i ), and min
{ ηmax,
2λmin(A) (1− c) Li
} ≤ η ≤ ηmax.
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 a large enough candidate step-size and multiply it by some constant γ < 1 until the Lipschitz or Armijo line-search condition is satisfied. If η′ was a proposal step-size that did not satisfy the constraint, but γη′ does, the maximum step-size η that satisfies the constraint must be in the range γη′ ≤ η < η′.
Proof of Lemma 1. Recall that if fi is Li-smooth, then for an arbitrary direction d,
fi(w − d) ≤ fi(w)− 〈∇fi(w), d〉+ Li 2 ‖d‖2 .
For the Lipschitz line-search, d = η∇fi(w). The smoothness and the line-search condition are then
Smoothness: fi(w − η∇fi(w))− fi(w) ≤ ( Li 2 η 2 − η ) ‖∇fi(w)‖2 , Line-search: fi(w − η∇fi(w))− fi(w) ≤ −cη ‖∇fi(w)‖2 .
As illustrated in Fig. 3, the line-search condition is looser than smoothness if(
Li 2 η 2 − η ) ‖∇fi(w)‖2 ≤ −cη ‖∇fi(w)‖2 .
The inequality is satisfied for any η ∈ [a, b], where a, b are values of η that satisfy the equation with equality, a = 0, b = 2(1−c)/Li, and the line-search condition holds for η ≤ 2(1−c)/Li.
Smoothness: fi(w) + ( Li 2 η 2 − η)‖∇fi(w)‖2
Line search: fi(w)− cη‖∇fi(w)‖2
η = 0 η = 2(1−c)Li
fi(w)•
Figure 3: Sketch of the line-search inequalities.
As the line-search selects the largest feasible step-size, η ≥ 2(1−c)/Li. If the step-size is capped at ηmax, we have η ≥ min{ηmax, 2(1−c)/Li}, and the proof for the Lipschitz line-search is complete. The proof for the Armijo line-search is identical except for the smoothness property, which is modified
to use the ‖·‖A-norm for the direction d = ηA−1∇fi(w);
fi(w − ηA−1∇fi(w)) ≤ fi(w)− η〈∇fi(w), A−1∇fi(w)〉+ Li 2 η2 ∥∥A−1∇fi(w)∥∥2 ,
≤ fi(w)− η ‖∇fi(w)‖2A−1 + Li
2λmin(A) η2 ‖∇fi(w)‖2A−1 ,
= fi(w)+
( Li
2λmin(A) η2 − η
) ‖∇fi(w)‖2A−1 ,
where the second inequality comes from ‖A−1∇fi(w)‖2 ≤ 1λmin(A) ‖∇fi(w)‖ 2 A−1 .
Similarly, the stochastic Polyak step-sizes (SPS) for fi at w are defined as
SPS: η = min { fi(w)− f∗i c ‖∇fi(w)‖2 , ηmax } , Armijo SPS: η = min { fi(w)− f∗i c ‖∇fi(w)‖2A−1 , ηmax } ,
where the parameter c > 0 controls the scaling of the step (larger c means smaller steps).
Lemma 2 (SPS guarantees). If fi is Li-smooth, SPS and Armijo SPS ensure that
SPS: η ‖∇fi(w)‖2 ≤ 1c (fi(w)− f ∗ i ), min { ηmax, 1 2cLi } ≤ η ≤ ηmax,
Armijo SPS: η ‖∇fi(w)‖2A−1 ≤ 1 c (fi(w)− f ∗ i ), min { ηmax, λmin(A) 2cLi } ≤ η ≤ ηmax
Proof of Lemma 2. The first guarantee follows directly from the definition of the step-size. For SPS,
η ‖∇fi(w)‖2 = min { fi(w)− f∗i c ‖∇fi(w)‖2 , ηmax } ‖∇fi(w)‖2 ,
= min
{ fi(w)− f∗i
c , ηmax ‖∇fi(w)‖2 } ≤ 1 c (fi(w)− f?i ).
The same inequalities hold for Armijo SPS with ‖∇fi(w)‖2A−1 . To lower-bound the step-size, we use the Li-smoothness of fi, which implies fi(w)− f∗i ≥ 12Li ‖∇fi(w)‖ 2. For SPS,
fi(w)− f∗i c ‖∇fi(w)‖2 ≥ 1 2Li ‖∇fi(w)‖2 c ‖∇fi(w)‖2 = 1 2cLi .
For Armijo SPS, we additionally use ‖∇fi(w)‖2A−1 ≤ 1 λmin(A) ‖∇fi(w)‖2,
fi(w)− f∗i c ‖∇fi(w)‖2A−1 ≥ 1 2Li ‖∇fi(w)‖2 c 1λmin(A) ‖∇fi(w)‖ 2 = λmin(A) 2cLi .

heading: C PROOFS FOR ADAGRAD
text: 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 ηk in the range [ηmin, ηmax], and derive the rates of Theorems 1 and 2 by specializing the range to a constant step-size or line-search.
Proposition 1 (AdaGrad with non-increasing step-sizes). Assuming (i) convexity and (ii) Lmaxsmoothness of each fi, and (iii) bounded iterates, AdaGrad with non-increasing (ηk ≤ ηk−1), bounded step-sizes (ηk ∈ [ηmin, ηmax]), and uniform averaging w̄T = 1T ∑T k=1wk, converges at a rate
E[f(w̄T )− f∗] ≤ α
T + √ ασ√ T , where α = 1 2
( D2
ηmin + 2ηmax
)2 dLmax.
We first use the above result to prove Theorems 1 and 2. The proof of Theorem 1 is immediate by plugging η = ηmin = ηmax in Proposition 1. We recall its statement;
Theorem 1 (Constant step-size AdaGrad). Assuming (i) convexity and (ii) Lmaxsmoothness of each fi, and (iii) bounded iterates, AdaGrad with a constant step-size η and uniform averaging such that w̄T = 1T ∑T k=1 wk, converges at a rate
E[f(w̄T )− f∗] ≤ α
T + √ ασ√ T , where α = 1 2
( D2
η + 2η
)2 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 1, AdaGrad with a conservative Lipschitz line-search with c = 1/2, a step-size upper bound ηmax and uniform averaging converges at a rate
E[f(w̄T )− f∗] ≤ α
T + √ ασ√ T , where α = 1 2
( D2 max { 1
ηmax , Lmax
} + 2 ηmax )2 dLmax.
Proof of Theorem 2. Using Lemma 1, there is a step-size ηk that satisfies the Lipschitz line-search with ηk ≥ 2 (1−c)/Lmax. Setting c = 1/2 and using a maximum step-size ηmax, we have
min { ηmax, 1
Lmax
} ≤ ηk ≤ ηmax, =⇒
1
ηmin = max
{ 1
ηmax , Lmax
} .
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 a useful quadratic inequality (Levy et al., 2018, Part of Theorem 4.2)). We include proofs in Appendix C.1 for completeness.
Lemma 3. If the preconditioners are non-decreasing (Ak Ak−1), the step-sizes are nonincreasing (ηk ≤ ηk−1), and the iterates stay within a ball of radius D of the minima,∑T
k=1 ‖wk − w∗‖ 2 1 ηk Ak− 1ηk−1Ak−1 ≤ D 2 ηT Tr(AT ).
Lemma 4. For AdaGrad, Ak = [∑k i=1∇fik(wk)∇fik(wk)> ]1/2 and satisfies,
∑T k=1 ‖∇fik(wk)‖ 2 A−1k ≤ 2Tr(AT ), Tr(AT ) ≤ √ d ∑T k=1 ‖∇fik(wk)‖ 2 .
Lemma 5. If x2 ≤ a(x+ b) for a ≥ 0 and b ≥ 0,
x ≤ 1 2
(√ a2 + 4ab+ a ) ≤ a+ √ ab.
We now prove Proposition 1.
Proof of Proposition 1. We first give an overview of the main steps. Using the definition of the update rule, along with Lemmas 3 and 4, we will show that
2 ∑T k=1〈∇fik(wk), wk − w∗〉 ≤ ( D2 ηmin + 2ηmax ) Tr(AT ). (5)
Using the definition of AT , individual smoothness and convexity, we then show that for a constant a,∑T k=1 E[f(wk)− f∗] ≤ a ( E [√∑T k=1 fik(wk)− fik(w∗) ] + Tσ2 ) , (6)
Using the quadratic inequality (Lemma 5), averaging and using Jensen’s inequality finishes the proof.
To derive Eq. (5), we start with the Update rule, measuring distances to w∗ in the ‖·‖Ak norm,
‖wk+1 − w∗‖2Ak = ‖wk − w ∗‖2Ak − 2ηk〈∇fik(wk), wk − w ∗〉+ η2k ‖∇fik(wk)‖ 2 A−1k .
Dividing by ηk, reorganizing the equation and summing across iterations yields
2 T∑ k=1 〈∇fik(wk), wk − w∗〉 ≤ T∑ k=1 ‖wk − w∗‖2(Ak ηk − Ak−1 ηk−1 ) + T∑ k=1 ηk ‖∇fik(wk)‖ 2 A−1k ,
≤ T∑ k=1 ‖wk − w∗‖2(Ak ηk − Ak−1 ηk−1 ) + ηmax T∑ k=1 ‖∇fik(wk)‖ 2 A−1k .
We use the Lemmas 3, 4 to bound the RHS by the trace of the last preconditioner,
≤ D 2
ηT Tr(AT ) + 2ηmaxTr(AT ), (Lemmas 3 and 4) ≤ ( D2
ηmin + 2ηmax
) Tr(AT ). (ηk ≥ ηmin)
To derive Eq. (6), we bound the trace of AT using Lemma 4 and Individual Smoothness, Tr(AT ) ≤ √ d √∑T k=1 ‖∇fik(wk)‖ 2 , (Lemma 4, Trace bound)
≤ √
2dLmax √∑T k=1 fik(wk)− f∗ik . (Individual Smoothness)
≤ √
2dLmax √∑T k=1 fik(wk)− fik(w∗) + fik(w∗)− f∗ik (±fik(w ∗))
Combining the above inequalities with δik = fik(w ∗)− f∗ik and a = 1 2 ( D2 ηmin + 2ηmax) √ 2dLmax,∑T
k=1〈∇fik(wk), wk − w∗〉 ≤ a √∑T k=1 fik(wk)− fik(w∗) + δik .
Using Individual Convexity and taking expectations,∑T k=1 E[f(wk)− f∗] ≤ aE [√∑T k=1 fik(wk)− fik(w∗) + δik ] ,
≤ a √ E [∑T k=1 fik(wk)− fik(w∗) + δik ] . (Jensen’s inequality)
Letting σ2 := Ei[δi] = Ei[fi(w∗)− f∗i ] and taking the square on both sides yields( T∑ k=1 E[f(wk)− f∗] )2 ≤ a2 ( E [ T∑ k=1 fik(wk)− fik(w∗) ] + Tσ2 ) .
The quadratic bound (Lemma 5) x2 ≤ α(x+ β) implies x ≤ α+ √ αβ, with
x = T∑ k=1 E[f(wk)− f∗], α = 1 2 ( D2 1 ηmin + 2ηmax )2 dLmax, β = Tσ 2,
gives the first bound below. Averaging w̄T = 1T ∑T k=1wk and using Jensen’s inequality give the result;
T∑ k=1 E[f(wk)− f∗] ≤ α+ √ αβ =⇒ E[f(w̄T )− f∗] ≤ α T + √ ασ√ T .

heading: C.1 PROOFS OF ADAPTIVE GRADIENT LEMMAS
text: 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 (Ak Ak−1), the step-sizes are non-increasing (ηk ≤ ηk−1), and the iterates stay within a ball of radiusD of the minima,∑T
k=1 ‖wk − w∗‖ 2 1 ηk Ak− 1ηk−1Ak−1 ≤ D 2 ηT Tr(AT ).
Proof of Lemma 3. Under the assumptions that Ak is non-decreasing and ηk is non-increasing, 1 ηk Ak − 1ηk−1Ak−1 0, so we can use the Bounded iterates assumption to bound∑T k=1 ‖wk − w∗‖
2 Ak ηk − Ak−1 ηk−1
≤ ∑T k=1 λmax ( Ak ηk − Ak−1ηk−1 ) ‖wk − w∗‖2
≤ D2 ∑T k=1 λmax ( Ak ηk − Ak−1ηk−1 ) .
We then upper-bound λmax by the trace and use the linearity of the trace to telescope the sum, ≤ D2 ∑T k=1 Tr ( Ak ηk − Ak−1ηk−1 ) = D2 ∑T k=1 Tr ( Ak ηk ) − Tr ( Ak−1 ηk−1 ) ,
= D2 ( Tr ( AT ηT ) − Tr ( A0 η0 )) ≤ D2 1ηT Tr(AT ).
Lemma 4. For AdaGrad, Ak = [∑k i=1∇fik(wk)∇fik(wk)> ]1/2 and satisfies,
∑T k=1 ‖∇fik(wk)‖ 2 A−1k ≤ 2Tr(AT ), Tr(AT ) ≤ √ d ∑T k=1 ‖∇fik(wk)‖ 2 .
Proof of Lemma 4. For ease of notation, let ∇k :=∇fik(wk). By induction, starting with T = 1,
‖∇fi1(w1)‖ 2 A−11 = ∇>1 A−11 ∇1 = Tr ( ∇>1 A−11 ∇1 ) = Tr ( A−11 ∇1∇>1 ) , (Cyclic property of trace)
= Tr ( A−11 A 2 1 ) = Tr(A1). (A1 = (∇1∇>1 ) 1/2)
Suppose that it holds for T −1, ∑T−1 k=1 ‖∇k‖ 2 A−1k ≤ 2Tr(AT−1). We will show that it also holds for T . Using the definition of the preconditioner and the cyclic property of the trace,∑T k=1 ‖∇fik(wk)‖ 2 A−1k ≤ 2Tr(AT−1) + ‖∇T ‖2A−1T (Induction hypothesis)
= 2Tr ( (A2T −∇T∇>T ) 1/2 ) + Tr ( A−1T ∇T∇ > T ) (AdaGrad update)
We then use the fact that for any X Y 0, we have (Duchi et al., 2011, Lemma 8) 2Tr ( (X − Y )1/2 ) + Tr ( X− 1/2Y ) ≤ 2Tr ( X 1/2 ) .
As X = A2T Y = ∇T∇>T 0, we can use the above inequality and the induction holds for T .
For the trace bound, recall that AT = G 1/2 T where GT = ∑T i=1∇fik(wk)∇fik(wk)>. We use Jensen’s inequality,
Tr(AT ) = Tr ( G 1/2 T ) = ∑d j=1 √ λj(GT ) = d ( 1 d ∑d j=1 √ λj(GT ) ) ,
≤ d √
1 d ∑d j=1 λj(GT ) = √ d √ Tr(GT ).
To finish the proof, we use the definition of GT and the linearity of the trace to get√ Tr(GT ) = √ Tr (∑T k=1∇k∇k> ) = √∑T k=1 Tr(∇k∇k>) = √∑T k=1 ‖∇k‖ 2 .
Lemma 5. If x2 ≤ a(x+ b) for a ≥ 0 and b ≥ 0,
x ≤ 1 2
(√ a2 + 4ab+ a ) ≤ a+ √ ab.
Proof of Lemma 5. The starting point is the quadratic inequality x2 − ax− ab ≤ 0. Letting r1 ≤ r2 be the roots of the quadratic, the inequality holds if x ∈ [r1, r2]. The upper bound is then given by using √ a+ b ≤ √ a+ √ b
r2 = a+ √ a2 + 4ab
2 ≤ a+
√ a2 + √ 4ab
2 = a+
√ ab.

heading: C.2 REGRET BOUND FOR ADAGRAD UNDER INTERPOLATION
text: In the online convex optimization framework, we consider a sequence of functions fk|Tk=1, chosen potentially adversarially by the environment. The aim of the learner is to output a series of strategies wk|Tk=1 before seeing the function fk. After choosing wk, the learner suffers the loss fk(wk) and observes the corresponding gradient vector ∇fk(wk). They suffer an instantaneous regret rk = fk(wk)− fk(w) compared to a fixed strategy w. The aim is to bound the cumulative regret,
R(T ) = T∑ k=1 [fk(wk)− fk(w∗)]
where w∗ = arg min ∑T k=1 fk(w) 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 O(1/ √ T ) regret bound (Duchi et 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-parameterized models like neural networks, where the number of parameters is of the order of millions, this is a 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 fk(wk) and uses the gradient feedback∇fk(wk) to update their strategy as
wk+1 = wk − ηA−1k ∇fk(wk), where Ak = [∑k i=1∇fk(wk)∇fk(wk)> ]1/2 .
Now we show that for smooth, convex functions under the interpolation assumption, AdaGrad with a constant step-size can result in constant regret.
Theorem 6. For a sequence of Lmax-smooth, convex functions fk, assuming the iterates remain bounded s.t. for all k, ‖wk − w∗‖ ≤ D, AdaGrad with a constant step-size η achieves the following regret bound,
R(T ) ≤ 1 2
( D2 1
η + 2η
)2 dLmax + √ 1
2
( D2 1
η + 2η
)2 dLmaxσ2 √ T
where σ2 is an upper-bound on fk(w∗)− f∗k .
Observe that σ2 is the degree to which interpolation is violated, and if σ2 6= 0, R(T ) = O( √ T ) matching the regret of (Duchi et al., 2011). However, when interpolation is exactly satisfied, σ2 = 0, and R(T ) = O(1).
Proof of Theorem 6. The proof follows that of Proposition 1 which is inspired from (Levy et al., 2018). For convenience, we repeat the basic steps. Measuring distances to w∗ in the ‖·‖Ak norm,
‖wk+1 − w∗‖2Ak = ‖wk − w ∗‖2Ak − 2η〈∇fk(wk), wk − w ∗〉+ η2 ‖∇fk(wk)‖2A−1k .
Dividing by 2η, reorganizing the equation and summing across iterations yields
T∑ k=1 〈∇fk(wk), wk − w∗〉 ≤ T∑ k=1 ‖wk − w∗‖2(Ak 2η − Ak−1 2η ) + η 2 T∑ k=1 ‖∇fk(wk)‖2A−1k .
By convexity of fk, 〈∇fk(wk), wk − w∗〉 ≥ fk(wk)− fk(w∗). Using the definition of regret,
R(T ) ≤ T∑ k=1 ‖wk − w∗‖2(Ak 2η − Ak−1 2η ) + η 2 T∑ k=1 ‖∇fk(wk)‖2A−1k .
We use the Lemmas 3, 4 to bound the RHS by the trace of the last preconditioner, R(T ) ≤ ( D2
2η + η
) Tr(AT ).
We now bound the trace of AT using Lemma 4 and Individual Smoothness, Tr(AT ) ≤ √ d √∑T k=1 ‖∇fk(wk)‖ 2 , (Lemma 4, Trace bound)
≤ √
2dLmax √∑T k=1 fk(wk)− f∗k , (Individual Smoothness)
≤ √
2dLmax √∑T k=1 fk(wk)− fk(w∗) + fk(w∗)− f∗k , (±fk(w∗))
≤ √ 2dLmax √ R(T ) + σ2T . (Since fk(w∗)− f∗k ≤ σ2)
Plugging this back into the regret bound, R(T ) ≤ ( D2
2η + η
)√ 2dLmax[ √ R(T ) + σ2T ].
Squaring both sides and denoting a = ( D2 2η + η )√ 2dLmax,
[R(T )]2 ≤ a2[R(T ) + σ2T ].
Using the quadratic bound (Lemma 5) x2 ≤ α(x+ β) implies x ≤ α+ √ αβ, with
x = R(T ), α = 1
2
( D2 1
η + 2η
)2 dLmax, β = σ 2T,
yields the bound,
R(T ) ≤ α+ √ αβ = 1
2
( D2 1
η + 2η
)2 dLmax + √ 1
2
( D2 1
η + 2η
)2 dLmaxσ2T .

heading: C.3 WITH INTERPOLATION, WITHOUT CONSERVATIVE LINE-SEARCHES
text: In this section, we show that the conservative constraint ηk+1 ≤ ηk is not necessary if interpolation is 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, amin 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-increasing step-sizes, if interpolation is satisfied, AdaGrad with the Armijo line-search and uniform averaging converges at the rate,
E[f(w̄T )− f∗] ≤ ( D2 + 2η2max )2 dLmax
2T
( max { 1
ηmax , Lmax amin
})2 .
where amin = mink{λmin(Ak)}.
Proof of Theorem 7. Following the proof of Proposition 1,
2 T∑ k=1 ηk〈∇fik(wk), wk − w∗〉 = T∑ k=1 ‖wk − w∗‖2Ak − ‖wk+1 − w ∗‖2Ak + η 2 k ‖∇fik(wk)‖ 2 A−1k .
On the left-hand side, we use individual convexity and interpolation, which implies fik(w ∗) = minw fik(w) and we can bound ηk by ηmin, giving ηk〈∇fik(wk), wk − w∗〉 ≥ ηk (fik(wk)− fik(w∗))︸ ︷︷ ︸
≥0
≥ ηmin(fik(wk)− fik(w∗)).
On the right-hand side, we can apply the AdaGrad lemmas (Lemma 4) T∑ k=1 ‖wk − w∗‖2Ak − ‖wk+1 − w ∗‖2Ak + η 2 max ‖∇fik(wk)‖ 2 A−1k ,
≤ D2Tr(AT ) + 2η2maxTr(AT ), (By Lemmas 3 and 4) ≤ ( D2 + 2η2max )√ d √∑T k=1 ‖∇fik(wk)‖ 2 , (By the trace bound of Lemma 4)
≤ ( D2 + 2η2max )√ 2dLmax √∑T k=1 fik(wk)− fik(w∗).
(By Individual Smoothness and interpolation)
Defining a = 12ηmin ( D2 + 2η2max )√ 2dLmax and combining the previous inequalities yields
T∑ k=1 (fik(wk)− fik(w∗)) ≤ a √∑T k=1 fik(wk)− fik(w∗).
Taking expectations and applying Jensen’s inequality yields∑T k=1 E[f(wk)− f(w∗)] ≤ a √∑T k=1 E[f(wk)− f(w∗)].
Squaring both sides, dividing by ∑T k=1 E[f(wk)− f(w∗)], followed by dividing by T and applying Jensen’s inequality,
E[f(w̄T )− f(w∗)] ≤ a2
T =
( D2 + 2η2max )2 dLmax
2η2minT .
Using the Armijo line-search guarantee (Lemma 1) with c = 1/2 and a maximum step-size ηmax,
ηmin = min { ηmax,
amin Lmax
} ,
where amin = mink{λmin(Ak)}, giving the rate E[f(w̄T )− f(w∗)] ≤ ( D2 + 2η2max )2 dLmax
2T
( max { 1
ηmax , Lmax amin
})2 .

heading: D PROOFS FOR AMSGRAD AND NON-DECREASING PRECONDITIONERS WITHOUT MOMENTUM
text: We now give the proofs for AMSGrad and general bounded, non-decreasing preconditioners in the smooth setting, using a constant step-size (Theorem 8) and the Armijo line-search (Theorem 4). As in Appendix C, we prove a general proposition and specialize it for each of the theorems;
Proposition 2. In addition to assumptions of Theorem 1, assume that (iv) the preconditioners are non-decreasing and have (v) bounded eigenvalues in the [amin, amax] range. If the step-sizes are constrained to lie in the range [ηmin, ηmax] and satisfy
ηk ‖∇fik(wk)‖ 2 A−1k ≤M(fik(wk)− fik ∗ ), for some M < 2, (7)
using uniform averaging w̄T = 1T ∑T k=1 wk leads to the rate
E[f(w̄T )− f∗] ≤ 1
T D2damax (2−M)ηmin +
( 2
2−M ηmax ηmin
− 1 ) σ2.
Theorem 8. Under the assumptions of Theorem 1 and assuming (iv) non-decreasing preconditioners (v) bounded eigenvalues in the [amin, amax] interval, AMSGrad with no momentum, constant step-size η = amin2Lmax and uniform averaging converges at a rate,
E[f(w̄T )− f∗] ≤ 2D2d amax Lmax
amin T + σ2.
Proof of Theorem 8. Using Bounded preconditioner and Individual Smoothness, we have that
‖∇fik(wk)‖ 2 A−1k ≤ 1 amin ‖∇fik(wk)‖ 2 ≤ 2Lmax amin (fik(wk)− fik ∗ ).
A constant step-size ηmax = ηmin = amin2Lmax satisfies the step-size assumption (Eq. 7) with M = 1 and
1
T D2damax (2−M)ηmin +
( 2
2−M ηmax ηmin
− 1 ) σ2 = 1
T
2LmaxD 2damax
amin + σ2.
We restate Theorem 4;
Theorem 4. Under the same assumptions as Theorem 1, AMSGrad with zero momentum, Armijo line-search with c = 3/4, a step-size upper bound ηmax and uniform averaging converges at a rate,
E[f(w̄T )− f∗] ≤ (
3D2d · amax 2T + 3ηmaxσ 2
) max { 1
ηmax , 2Lmax amin
} .
Proof of Theorem 4. For the Armijo line-search, Lemma 1 guarantees that
η ‖∇fik(wk)‖ 2 A−1k ≤ 1 c (fik(wk)− f∗ik), and min { ηmax, 2λmin(Ak) (1− c) Lmax } ≤ η ≤ ηmax.
Selecting c = 3/4 gives M = 4/3 and ηmin = min { ηmax,
amin 2Lmax
} , so
1
T D2damax (2−M)ηmin +
( 2
2−M ηmax ηmin
− 1 ) σ2
= 1
T D2damax (2− 4/3)ηmin +
( 2
2− 4/3 ηmax ηmin
− 1 ) σ2,
= 1
T 3D2damax 2ηmin + ( 3ηmax ηmin − 1 ) σ2,
≤ 3D 2damax 2T max
{ 1
ηmax , 2Lmax amin
} + 3ηmaxσ 2 max { 1
ηmax , 2Lmax amin
} .
Theorem 9. Under the assumptions of Theorem 1 and assuming (iv) non-decreasing preconditioners (v) bounded eigenvalues in the [amin, amax] interval, AMSGrad with no momentum, Armijo SPS with c = 3/4 and uniform averaging converges at a rate,
E[f(w̄T )− f∗] ≤ (
3D2d · amax 2T + 3ηmaxσ 2
) max { 1
ηmax , 3Lmax 2amin
} .
Proof of Theorem 5. For Armijo SPS, Lemma 2 guarantees that
ηk ‖∇fik(wk)‖ 2 A−1k ≤ 1 c (fik(wk)− f∗ik), and min { ηmax, amin 2cLmax } ≤ η ≤ ηmax.
Selecting c = 3/4 gives M = 4/3 and ηmin = min { ηmax,
2amin 3Lmax
} , so
1
T D2damax (2−M)ηmin +
( 2
2−M ηmax ηmin
− 1 ) σ2
= 1
T D2damax (2− 4/3)ηmin +
( 2
2− 4/3 ηmax ηmin
− 1 ) σ2,
= 1
T 3D2damax 2ηmin + ( 3ηmax ηmin − 1 ) σ2,
≤ 3D 2damax 2T max
{ 1
ηmax , 3Lmax 2amin
} + 3ηmaxσ 2 max { 1
ηmax , 3Lmax 2amin
} .
Before diving into the proof of Proposition 2, we prove the following lemma to handle terms of the form ηk(fik(wk)− fik(w∗)). If ηk depends on the function sampled at the current iteration, fik , as in the case of line-search, we cannot take expectations as the terms are not independent. Lemma 6 bounds ηk(fik(wk)− fik(w∗)) in terms of the range [ηmin, ηmax];
Lemma 6. If 0 ≤ ηmin ≤ η ≤ ηmax and the minimum value of fi is f∗i , then
η(fi(w)− fi(w∗)) ≥ ηmin(fi(w)− fi(w∗))− (ηmax − ηmin)(fi(w∗)− f∗i ).
Proof of Lemma 6. By adding and subtracting f∗i , the minimum value of fi, we get a non-negative and a non-positive term multiplied by η. We can use the bounds η ≥ ηmin and η ≤ ηmax separately;
η[fi(w)− fi(w∗)] = η[fi(w)− f∗i︸ ︷︷ ︸ ≥0 + f∗i − fi(w∗)︸ ︷︷ ︸ ≤0 ],
≥ ηmin[fi(w)− f∗i ] + ηmax[f∗i − fi(w∗)]. Adding and subtracting ηminfi(w∗) finishes the proof,
= ηmin[fi(w)− fi(w∗) + fi(w∗)− f∗i ] + ηmax[f∗i − fi(w∗)], = ηmin[fi(w)− fi(w∗)] + (ηmax − ηmin)[f∗i − fi(w∗)].
Proof of Proposition 2. We start with the Update rule, measuring distances to w∗ in the ‖·‖Ak norm,
‖wk+1 − w∗‖2Ak = ‖wk − w ∗‖2Ak − 2ηk〈∇fik(wk), wk − w ∗〉+ η2k ‖∇fik(wk)‖ 2 A−1k
(8)
To bound the RHS, we use the assumption on the step-sizes (Eq. (7)) and Individual Convexity,
− 2ηk〈∇fik(wk), wk − w∗〉+ η2k ‖∇fik(wk)‖ 2 A−1k , ≤ −2ηk〈∇fik(wk), wk − w∗〉+Mηk(fik(wk)− fik ∗ ), (Step-size assumption, Eq. (7)) ≤ −2ηk[fik(wk)− fik(w∗)] +Mηk(fik(wk)− fik ∗ ), (Individual Convexity) ≤ −2ηk[fik(wk)− fik(w∗)] +Mηk(fik(wk)− fik(w∗) + fik(w∗)− fik ∗ ), (±fik(w∗)) ≤ −(2−M)ηk[fik(wk)− fik(w∗)] +Mηmax(fik(w∗)− fik ∗ ). (ηk ≤ ηmax)
Plugging the inequality back into Eq. (8) and reorganizing the terms yields (2−M)ηk[fik(wk)− fik(w∗)] ≤ ( ‖wk − w∗‖2Ak − ‖wk+1 − w ∗‖2Ak )
+Mηmax(fik(w ∗)− fik ∗ )
(9)
Using Lemma 6, we have that
(2−M)ηk[fik(wk)− fik(w∗)] ≥ (2−M)ηmin(fik(wk)− fik(w∗)) − (2−M)(ηmax − ηmin)(fik(w∗)− fik ∗ ).
Using this inequality in Eq. (9), we have that
(2−M)ηmin(fik(wk)− fik(w∗))− (2−M)(ηmax − ηmin)(fik(w∗)− fik ∗ ) ≤ ( ‖wk − w∗‖2Ak − ‖wk+1 − w ∗‖2Ak ) +Mηmax(fik(w ∗)− fik ∗ ),
Moving the terms depending on fik(w ∗)− fik ∗ to the RHS, (2−M)ηmin(fik(wk)− fik(w∗)) ≤ ( ‖wk − w∗‖2Ak − ‖wk+1 − w ∗‖2Ak )
+ (2ηmax − (2−M)ηmin)(fik(w∗)− fik ∗ ).
Taking expectations and summing across iterations yields
(2−M)ηmin T∑ k=1 E[fik(wk)− fik(w∗)] ≤E [ T∑ k=1 ( ‖wk − w∗‖2Ak − ‖wk+1 − w ∗‖2Ak )]
+(2ηmax − (2−M)ηmin)Tσ2.
Using Lemma 3 to telescope the distances and using the Bounded preconditioner,
T∑ k=1 ‖wk − w∗‖2Ak − ‖wk+1 − w ∗‖2Ak ≤ T∑ k=1 ‖wk − w∗‖2Ak−Ak−1 ≤ D 2 Tr(AT ) ≤ D2 d amax,
which guarantees that
(2−M)ηmin T∑ k=1 E[f(wk)− f(w∗)] ≤D2damax + (2ηmax − (2−M)ηmin)Tσ2.
Dividing by T (2−M)ηmin and using Jensen’s inequality finishes the proof, giving the rate for the averaged iterate,
E[f(w̄T )− f(w∗)] ≤ 1
T D2damax (2−M)ηmin +
( 2
2−M ηmax ηmin
− 1 ) σ2.

heading: E AMSGRAD WITH MOMENTUM
text: We first show the relation between the AMSGrad momentum and heavy ball momentum and then present the proofs with AMSGrad momentum in E.2 and heavy ball momentum in E.3.

heading: E.1 RELATION BETWEEN THE AMSGRAD UPDATE AND PRECONDITIONED SGD WITH HEAVY-BALL MOMENTUM
text: Recall that the AMSGrad update is given as:
wk+1 = wk − ηk A−1k mk ; mk = βmk−1 + (1− β)∇fik(wk)
Simplifying,
wk+1 = wk − ηk A−1k (βmk−1 + (1− β)∇fik(wk)) wk+1 = wk − ηk(1− β)A−1k ∇fik(wk)− ηkβ A−1k mk−1
From the update at iteration k − 1,
wk = wk−1 − ηk−1A−1k−1mk−1
=⇒ −mk−1 = 1
ηk−1 Ak−1 (wk − wk−1)
From the above relations,
wk+1 = wk − ηk(1− β)A−1k ∇fik(wk) + β ηk ηk−1 A−1k Ak−1 (wk − wk−1)
which is of the same form as
wk+1 = wk − ηk A−1k + γ(wk − wk−1),
the update with heavy ball momentum. The two updates are equivalent up to constants except for the key difference that for AMSGrad, the momentum vector (wk − wk−1) is further preconditioned by A−1k Ak−1.

heading: E.2 PROOFS FOR AMSGRAD WITH MOMENTUM
text: We now give the proofs for AMSGrad having the update.
wk+1 = wk − ηk A−1k mk ; mk = βmk−1 + (1− β)∇fik(wk)
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 a general proposition and specialize it for each of the theorems.
Proposition 3. In addition to assumptions of Theorem 1, assume that (iv) the preconditioners are non-decreasing and have (v) bounded eigenvalues in the [amin, amax] range. If the step-sizes are lower-bounded and non-increasing, ηmin ≤ ηk ≤ ηk−1 and satisfy
ηk ‖∇fik(wk)‖ 2 A−1k ≤M(fik(wk)− fik ∗ ), for some M < 2 1− β 1 + β , (10)
using uniform averaging w̄T = 1T ∑T k=1 wk leads to the rate
E[f(w̄T )− f∗] ≤ 1 + β
1− β
( 2− 1 + β
1− β M )−1[ D2damax ηminT +Mσ2 ] .
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) nondecreasing preconditioners (v) bounded eigenvalues in the [amin, amax] interval, where κ = amax/amin, AMSGrad with β ∈ [0, 1), constant step-size η = 1−β1+β amin 2Lmax
and uniform averaging converges at a rate,
E[f(w̄T )− f∗] ≤ ( 1 + β
1− β
)2 2LmaxD 2dκ
T + σ2.
Proof of Theorem 3. Using Bounded preconditioner and Individual Smoothness, we have that
η ‖∇fik(wk)‖ 2 A−1k ≤ η 1 amin ‖∇fik(wk)‖ 2 ≤ η 2Lmax amin (fik(wk)− fik ∗ ).
Using a constant step-size η = 1−β1+β amin 2Lmax satisfies the requirement of Proposition 3 (Eq. (10)) with constant M = 1−β1+β . The convergence is then,
E[f(w̄T )− f(w∗)] ≤ 1 + β
1− β
( 2− 1 + β
1− β M )−1[ D2damax ηminT +Mσ2, ] = 1 + β
1− β
[ D2damax
1−β 1+β amin 2Lmax
T + 1− β 1 + β σ2,
]
=
( 1 + β
1− β
)2 2LmaxD 2dκ
T + σ2,
with κ = amax/amin.
Theorem 5. Under the same assumptions of Theorem 1 and assuming (iv) nondecreasing preconditioners (v) bounded eigenvalues in the [amin, amax] interval with κ = amax/amin, AMSGrad with β ∈ [0, 1), conservative Armijo SPS with c = 1+β/1−β and uniform averaging converges at a rate,
E[f(w̄T )− f∗] ≤ ( 1 + β
1− β
)2 2LmaxD 2dκ
T + σ2.
Proof of Theorem 5. For Armijo SPS, Lemma 2 guarantees that
ηk ‖∇fik(wk)‖ 2 A−1k ≤ 1 c (fik(wk)− f∗ik), and amin 2cLmax ≤ ηk.
Setting c = 1+β1−β ensures that M = 1/c satisfies the requirement of Proposition 3 and ηmin ≥ 1−β 1+β amin 2Lmax . Plugging in these values into Proposition 3 completes the proof.
Theorem 10. Under the assumptions of Theorem 1 and assuming (iv) non-decreasing preconditioners (v) bounded eigenvalues in the [amin, amax] interval, AMSGrad with momentum with parameter β ∈ [0, 1/5), conservative Armijo SLS with c = 23 1+β 1−β and uniform averaging converges at a rate,
E[f(w̄T )− f∗] ≤ 3 1 + β 1− 5β LmaxD
2dκ
T + 3σ2
Proof of Theorem 10. For Armijo SLS, Lemma 1 guarantees that
ηk ‖∇fik(wk)‖ 2 A−1k ≤ 1 c (fik(wk)− f∗ik), and 2(1− c) amin Lmax ≤ ηk.
The line-search parameter c is restricted to [0, 1] and relates to the the requirement parameter M of Proposition 3 (Eq. (10)) through M = 1/c. The combined requirements on M are then that 1 < M < 2 1−β1+β , which is only feasible if β < 1 3 . To leave room to satisfy the constraints, let β < 1 5 .
Setting 1c = M = 3 2 1−β 1+β satisfies the constraints and requirement for Proposition 3, and
E[f(w̄T )− f(w∗)] ≤ 1 + β
1− β
( 2− 1 + β
1− β M )−1[ D2damax ηminT +Mσ2 ] ,
= 1 + β
1− β
( 2− 3
2
)−1[ Lmax
2(1− c) amin D2damax T + 3 2 1− β 1 + β
σ2 ] ,
= 1 + β 1− β Lmax (1− c) D2dκ T + 3σ2 = 3 1 + β 1− 5β LmaxD 2dκ T + 3σ2.
where the last step substituted 1/(1− c),
1− c = 1− 2 3 1 + β 1− β = 3(1− β)− 2(1 + β) 3(1− β) = 1 3 1− 5β 1− β .
Before diving into the proof of Proposition 3, we prove the following lemma,
Lemma 7. For any set of vectors a, b, c, d, if a = b+ c, then,
‖a− d‖2 = ‖b− d‖2 − ‖a− b‖2 + 2〈c, a− d〉

heading: Proof.
text: ‖a− d‖2 = ‖b+ c− d‖2 = ‖b− d‖2 + 2〈c, b− d〉+ ‖c‖2
Since c = a− b,
= ‖b− d‖2 + 2〈a− b, b− d〉+ ‖a− b‖2
= ‖b− d‖2 + 2〈a− b, b− a+ a− d〉+ ‖a− b‖2
= ‖b− d‖2 + 2〈a− b, b− a〉+ 2〈a− b, a− d〉+ ‖a− b‖2
= ‖b− d‖2 − 2 ‖a− b‖2 + 2〈a− b, a− d〉+ ‖a− b‖2
= ‖b− d‖2 − ‖a− b‖2 + 2〈c, a− d〉
We now move 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 Pk = Ak/ηk. Using the update, we have the expansion wk+1 − w∗ = ( wk − P−1k mk ) − w∗,
= ( wk − (1− β)P−1k ∇fik(wk)− βP −1 k mk−1 ) − w∗,
Measuring distances in the ‖·‖Pk-norm, such that ‖x‖ 2 Pk = 〈x, Pkx〉,
‖wk+1 − w∗‖2Pk = ‖wk − w ∗‖2Pk − 2(1− β) 〈wk − w ∗,∇fik(wk)〉,
− 2β 〈wk − w∗,mk−1〉+ ‖mk‖2P−1k .
We separate the distance to w∗ from the momentum in the second inner product using the update and Lemma 7 with a = c = P 1/2k−1(wk − w∗), b = 0, d = P 1/2k−1(wk−1 − w∗).
−2〈mk−1, wk − w∗〉 = −2 〈Pk−1(wk−1 − wk), wk − w∗〉, = [ ‖wk − wk−1‖2Pk−1 + ‖wk − w ∗‖2Pk−1 − ‖wk−1 − w ∗‖2Pk−1 ] ,
= ‖mk−1‖2P−1k−1 + ‖wk − w ∗‖2Pk−1 − ‖wk−1 − w ∗‖2Pk−1 , ≤ ‖mk−1‖2P−1k−1 + ‖wk − w ∗‖2Pk − ‖wk−1 − w ∗‖2Pk−1 ,
where the last inequality uses the fact that ηk ≤ ηk−1 and Ak Ak−1, which implies Pk Pk−1, and ‖wk − w∗‖2Pk−1 ≤ ‖wk − w ∗‖2Pk . Plugging this inequality in and grouping terms yields
2(1− β) 〈wk − w∗,∇fik(wk)〉 ≤ [ ‖wk − w∗‖2Pk − ‖wk+1 − w ∗‖2Pk ]
+ β [ ‖wk − w∗‖2Pk − ‖wk−1 − w ∗‖2Pk−1 ]
+ [ β ‖mk−1‖2P−1k−1 + ‖mk‖ 2 P−1k ] By convexity, the inner product on the left-hand-side is bounded by 〈wk − w∗,∇fik(wk)〉 ≥ fik(wk)− fik(w∗). The first two lines of the right-hand-side will telescope if we sum all iterations, so we only need to treat the norms of the momentum terms. We introduce a free parameter δ ≥ 0, that is only used for the analysis, and expand
β ‖mk−1‖2P−1k−1 + ‖mk‖ 2 P−1k = β ‖mk−1‖2P−1k−1 + (1 + δ) ‖mk‖ 2 P−1k − δ ‖mk‖2P−1k .
To bound ‖mk‖2P−1k , we expand it by its update and use Young’s inequality to get
‖mk‖2P−1k = ‖βmk−1 + (1− β)∇fik(wk)‖ 2 P−1k
≤ (1 + )β2 ‖mk−1‖2P−1k + (1 + 1/ )(1− β)2 ‖∇fik(wk)‖ 2 P−1k ,
where > 0 is also a free parameter, introduced to control the tradeoff of the bound. Plugging this bound in the momentum terms, we get
β ‖mk−1‖2P−1k−1 + ‖mk‖ 2 P−1k ≤β ‖mk−1‖2P−1k−1 + (1 + )(1 + δ)β 2 ‖mk−1‖2P−1k − δ ‖mk‖ 2 P−1k ,
+ (1 + 1/ )(1 + δ)(1− β)2 ‖∇fik(wk)‖ 2 P−1k .
As P−1k P−1k−1, we have that ‖mk−1‖ 2 P−1k ≤ ‖mk−1‖2P−1k−1 which implies
≤ ( β + (1 + )(1 + δ)β2 ) ‖mk−1‖2P−1k−1 − δ ‖mk‖ 2 P−1k
+ (1 + 1/ )(1 + δ)(1− β)2 ‖∇fik(wk)‖ 2 P−1k .
To get a telescoping sum, we set δ to be equal to β + (1 + )(1 + δ)β2, which is satisfied if δ = β+(1+ )β 2
1−(1+ )β2 , and δ > 0 is satisfied if β < 1/ √ 1+ . We now plug back the inequality
β ‖mk−1‖2P−1k−1 + ‖mk‖ 2 P−1k ≤ δ [ ‖mk−1‖2P−1k−1 − ‖mk‖ 2 P−1k ] + (1 + 1/ )(1 + δ)(1− β)2 ‖∇fik(wk)‖
2 P−1k ,
in the previous expression to get
2(1− β) (fik(wk)− fik(w∗)) ≤ ‖wk − w∗‖ 2 Pk − ‖wk+1 − w∗‖2Pk + β [ ‖wk − w∗‖2Pk − ‖wk−1 − w ∗‖2Pk−1 ]
+ δ [ ‖mk−1‖2P−1k−1 − ‖mk‖ 2 P−1k ] + (1 + 1/ )(1 + δ)(1− β)2 ‖∇fik(wk)‖
2 P−1k .
All terms now telescope, except the gradient norm which we bound using the step size assumption,
‖∇fik(wk)‖ 2 P−1k = ηk ‖∇fik(wk)‖ 2 A−1k ≤M(fik(wk)− fik ∗ ),
= M(fik(wk)− fik(w∗)) +M(fik(w∗)− fik ∗ ).
This gives the expression
α (fik(wk)− fik(w∗)) ≤ ‖wk − w∗‖ 2 Pk − ‖wk+1 − w∗‖2Pk + β [ ‖wk − w∗‖2Pk − ‖wk−1 − w ∗‖2Pk−1 ]
+ δ [ ‖mk−1‖2P−1k−1 − ‖mk‖ 2 P−1k ] + (1 + 1/ )(1 + δ)(1− β)2M(fik(w∗)− fik ∗ ),
with α = 2(1− β)− (1 + 1/ )(1 + δ)(1− β)2M . Summing all iterations, the individual terms are bounded by the Bounded iterates and Lemma 3;
T∑ k=1 ‖wk − w∗‖2Pk − ‖wk+1 − w ∗‖2Pk ≤ D 2Tr(PT ) ≤ D2 ηmin Tr(AT )
β T∑ k=1 ‖wk − w∗‖2Pk − ‖wk−1 − w ∗‖2Pk−1 ≤ β ‖wT − w ∗‖2PT ≤ β D2 ηmin Tr(AT )
δ T∑ k=1 ‖mk−1‖2P−1k−1 − ‖mk‖ 2 P−1k
≤ δ ‖m0‖2P0 = 0.
Using the boundedness of the preconditioners gives Tr(AT ) ≤ damax and the total bound
α T∑ k=1 (fik(wk)− fik(w∗)) ≤ (1 + β)D2damax ηmin + (1 + 1/ )(1 + δ)(1− β)2M T∑ k=1 (fik(w ∗)− fik ∗ ).
Taking expectations,
α T∑ k=1 E[f(wk)− f(w∗)] ≤ (1 + β)D2damax ηmin + (1 + 1/ )(1 + δ)(1− β)2Mσ2T.
It remains to expand α and simplify the constants. We had defined
α = 2(1− β)− (1 + 1/ )(1 + δ)(1− β)2M > 0, and δ = β + (1 + )β 2
1− (1 + )β2 > 0,
where > 0 is a free parameter. This puts the requirement on β that β < 1/ √
1 + . To simplify the bounds, we set β = 1/(1 + ), = 1/β − 1, which gives the substitutions
1 + = 1
β 1 +
1
=
1
1− β δ = 2
β
1− β 1 + δ =
1 + β 1− β .
Plugging those into the rate gives
α T∑ k=1 E[f(wk)− f(w∗)] ≤ (1 + β)D2damax ηmin + (1 + β)Mσ2T,
while plugging them into α gives
α = 2(1− β)− (1 + 1/ )(1 + δ)(1− β)2M, = (1− β) [ 2− 1 + β
1− β M
] , which is positive if M < 2
1− β 1 + β .
Dividing by αT , using Jensen’s inequality and averaging finishes the proof, with the rate
T∑ k=1 E[f(wk)− f(w∗)] ≤ 1 + β 1− β ( 2− 1 + β 1− β M )−1[ D2damax ηminT +Mσ2 ] .

heading: E.3 PROOFS FOR AMSGRAD WITH HEAVY BALL MOMENTUM
text: We now give the proofs for AMSGrad with heavy ball momentum with the update.
wk+1 = wk − ηk A−1k ∇fik(wk) + γ (wk − wk−1) We analyze it in the smooth setting using a constant step-size (Theorem 11), a conservative Armijo SPS (Theorem 12) and conservative Armijo SLS (Theorem 13). As before, we abstract the common elements to a general proposition and specialize it for each of the theorems.
Proposition 4. In addition to assumptions of Theorem 1, assume that (iv) the preconditioners are non-decreasing and have (v) bounded eigenvalues in the [amin, amax] range. If the step-sizes are lower-bounded and non-increasing, ηmin ≤ ηk ≤ ηk−1 and satisfy
ηk ‖∇fik(wk)‖ 2 A−1k ≤M(fik(wk)− fik ∗ ), for some M < 2− 2γ, (11)
AMSGrad with heavy ball momentum with parameter γ < 1 and uniform averaging w̄T = 1 T ∑T k=1 wk leads to the rate
E[f(w̄T )− f∗] ≤ 1
2− 2γ −M
[ 1
T
( 2(1 + γ2)D2amaxd
ηmin + 2γ[f(w0)− f(w∗)]
) +Mσ2 ] .
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 1 and assuming (iv) non-decreasing preconditioners (v) bounded eigenvalues in the [amin, amax] range, AMSGrad with heavy ball momentum with parameter γ ∈ [0, 1), constant step-size η = 2amin (1−γ)3Lmax and uniform averaging converges at a rate
E[f(w̄T )− f∗] ≤ 1
T
( 9
2
1 + γ2
(1− γ)2 LmaxD
2κd+ 3γ
(1− γ) [f(w0)− f(w∗)]
) + 2σ2.
Proof of Theorem 11. Using Bounded preconditioner and Individual Smoothness, we have that
η ‖∇fik(wk)‖ 2 A−1k ≤ η 1 amin ‖∇fik(wk)‖ 2 ≤ η 2Lmax amin (fik(wk)− fik ∗ ).
A constant step-size η = 2amin (1−γ)/3Lmax means the requirement for Proposition 4 is satisfied with M = 43 (1− γ). Plugging (2− 2γ −M) = 2 3 (1− γ) in Proposition 4 finishes the proof.
Theorem 12. Under the assumptions of Theorem 1 and assuming (iv) non-decreasing preconditioners (v) bounded eigenvalues in the [amin, amax] interval, AMSGrad with heavy ball momentum with parameter γ ∈ [0, 1), conservative Armijo SPS with c = 3/4(1−γ) and uniform averaging converges at a rate,
E[f(w̄T )− f∗] ≤ 1
T
( 9
2
1 + γ2
(1− γ)2 LmaxD
2κd+ 3γ
(1− γ) [f(w0)− f(w∗)]
) + 2σ2.
Proof of Theorem 12. For Armijo SPS, Lemma 2 guarantees that
ηk ‖∇fik(wk)‖ 2 A−1k ≤ 1 c (fik(wk)− f∗ik), and amin 2cLmax ≤ ηk.
Selecting c = 3/4(1−γ) gives M = 4/3(1− γ) ≤ 2(1− γ) and the requirement of Proposition 4 are satisfied. The minimum step-size is then ηmin = amin2cLmax = 2amin (1−γ) 3Lmax
, so ηmin and M are the same as in the constant step-size case (Theorem 11) and the same rate applies.
Theorem 13. Under the assumptions of Theorem 1 and assuming (iv) non-decreasing preconditioners (v) bounded eigenvalues in the [amin, amax] interval, AMSGrad with heavy ball momentum with parameter γ ∈ [0, 1/4), conservative Armijo SLS with c = 3/4(1−γ) and uniform averaging
converges at a rate,
E[f(w̄T )− f∗] ≤ 1
T
( 6 1 + γ2
1− 4γ LmaxD
2κd+ 3γ
(1− γ) [f(w0)− f(w∗)]
) + 2σ2.
Proof of Theorem 13. Selecting c = 3/4(1−γ) is feasible if γ < 1/4 as c < 1. The Armijo SLS (Lemma 1) then guarantees that
ηk ‖∇fik(wk)‖ 2 A−1k ≤ 1 c (fik(wk)− f∗ik), and 2(1− c) amin Lmax ≤ η,
which satisfies the requirements of Proposition 4 with M = 43 (1− γ). Plugging M in the rate yields
E[f(w̄T )− f(w∗)] ≤ 1
T
( 6 1 + γ2
1− γ D2amaxd ηmin + 3γ (1− γ) [f(w0)− f(w∗)]
) + 2σ2,
With c = 3/4 1−γ , ηmin ≥ 2(1−c)amin Lmax = 2aminLmax 1−4γ 4(1−γ) . Plugging it into the above bound yields
E[f(w̄T )− f(w∗)] ≤ 1
T
( 6 1 + γ2
1− 4γ LmaxD
2κd+ 3γ
(1− γ) [f(w0)− f(w∗)]
) + 2σ2.
We now move to the proof of 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+1 = wk − ηkA−1k ∇fik(wk) + γ(wk − wk−1). (12) The proof idea is to analyze the distance from w∗ to wk and a momentum term,
‖δk‖2 = ‖wk +mk − w∗‖2Ak , where mk = γ 1−γ (wk − wk−1), (13)
by considering the momentum update (Eq. 12) as a preconditioned step on the joint iterates (wk+mk),
wk+1 +mk+1 = wk +mk − ηk1−γA −1 k ∇fik(wk). (14)
Let us verify Eq. (14). First, expressing wk+1 +mk+1 as a weighted difference of wk+1 and wk,
wk+1 +mk+1 = wk+1 + γ 1−γ (wk+1 − wk) = 1 1−γwk+1 − γ 1−γwk.
Expanding wk+1 in terms of the update rule then gives
= 11−γ (wk − ηkA −1 k ∇fik(wk) + γ(wk − wk−1))− γ 1−γwk, = 11−γ (wk − ηkA −1 k ∇fik(wk)− γwk−1),
= 11−γwk − γ 1−γwk−1 − ηk 1−γA −1 k ∇fik(wk),
which can then be re-written as wk + mk − ηk1−γA −1 k ∇fik(wk). The analysis of the method then follows similar steps as the analysis without momentum. Using Eq. (14), we have the recurrence
‖δk+1‖2Ak = ‖wk+1 +mk+1 − w ∗‖2Ak = ∥∥∥wk +mk − ηk1−γA−1k ∇fik(wk)− w∗∥∥∥2 Ak ,
= ‖δk‖2Ak − 2ηk 1− γ 〈∇fik(wk), wk +mk − w∗〉+ η2k (1− γ)2 ‖∇fik(wk)‖ 2 A−1k .
(15)
To bound the inner-product, we use Individual Convexity to relate it to the optimality gap,
〈∇fik(wk), wk +mk − w∗〉 = 〈∇fik(wk), wk − w∗〉+ γ
1− γ 〈∇fik(wk), wk − wk−1〉,
≥ fik(wk)− fik(w∗) + γ
1− γ [fik(wk)− fik(wk−1)],
= 1
1− γ [fik(wk)− fik(w∗)]−
γ
1− γ [fik(wk−1)− fik(w∗)].
To bound the gradient norm, we use the step-size assumption that
ηk ‖∇fik(wk)‖ 2 A−1k ≤M [fik(wk)− f∗ik ] = M [fik(wk)− fik(w ∗)] +M [fik(w ∗)− f∗ik ].
For simplicity of notation, let us define the shortcuts
hk(w) = fik(w)− fik(w∗), σ2k = fik(w∗)− f∗ik .
Plugging those two inequalities in the recursion of Eq. (15) gives
‖δk+1‖2Ak ≤ ‖δk‖ 2 Ak − ηk
(1− γ)2 (2−M)hk(wk) +
2ηkγ
(1− γ)2 hk(wk−1) + Mηk (1− γ)2 σ2k.
We can now divide by ηk/(1−γ)2 and reorganize the inequality as
(2−M)hk(wk)− 2γhk(wk−1) ≤ (1− γ)2
ηk
( ‖δk‖2Ak − ‖δk+1‖ 2 Ak ) +Mσ2k.
Taking the average over all iterations, the inequality yields
1
T T∑ k=1 (2−M)hk(wk)− 2γhk(wk−1) ≤ 1 T T∑ k=1 (1− γ)2 ηk ( ‖δk‖2Ak − ‖δk+1‖ 2 Ak ) +Mσ2k.
To bound the right-hand side, under the assumption that the iterates are bounded by ‖wk − w∗‖ ≤ D, we use Young’s inequality to get a bound on ‖δk‖2;
‖δk‖22 = ‖wk +mk − w ∗‖22 = ∥∥∥ 11−γ (wk − w∗)− γ1−γ (wk−1 − w∗)∥∥∥2 2
≤ 2 (1− γ)2
( ‖wk − w∗‖22 + γ 2 ‖wk−1 − w∗‖22 ) ≤ 2(1 + γ 2)
(1− γ)2 D2 = ∆2.
Given the upper bound ‖δk‖2 ≤ ∆, a reorganization of the sum lets us apply Lemma 3 to get∑T k=1 1 ηk ( ‖δk‖2Ak − ‖δk+1‖ 2 Ak ) = ∑T k=1 ‖δk‖ 2 1 ηk Ak − ∑T k=1 ‖δk+1‖ 2 1 ηk Ak
= ∑T k=1 ‖δk‖ 2 1 ηk Ak − ∑T+1 k=2 ‖δk‖ 2 1 ηk−1 Ak−1
≤ ∑T k=1 ‖δk‖ 2 1 ηk Ak − ∑T k=1 ‖δk‖ 2 1 ηk−1 Ak−1 + ‖δ1‖21 η0 A0
= ∑T k=1 ‖δk‖
2 1 ηk Ak− 1ηk−1Ak−1 ≤ ∆ 2amaxd ηmin ,
where the last step uses the convention A0 = 0 and Lemma 3 on δk instead of wk − w∗. Plugging this inequality in, we get the simpler bound on the right-hand-side
1
T T∑ k=1 (2−M)hk(wk)− 2γhk(wk−1) ≤ 2(1 + γ2)D2amaxd Tηmin +Mσ2k.
Now that the step-size is bounded deterministically, we can take the expectation on both sides to get
1 T E [ T∑ k=1 (2−M)h(wk)− 2γh(wk−1) ] ≤ 2(1 + γ 2)D2amaxd Tηmin +Mσ2,
where h(w) = f(w)− f∗ and σ2 = E [ fik(w ∗)− f∗ik ] . To simplify the left-hand-side, we change the weights on the optimality gaps to get a telescoping sum,∑T k=1(2−M)h(wk)− 2γh(wk−1) = ∑T k=1(2− 2γ −M)h(wk) + 2γh(wk)− 2γh(wk−1),
= (2− 2γ −M) [∑T k=1 h(wk) ] + 2γ(h(wT )− h(w0)),
≥(2− 2γ −M) [∑T k=1 h(wk) ] − 2γh(w0).
The last inequality uses h(wT ) ≥ 0. Moving the initial optimality gap to the right-hand-side, we get
1 T (2− 2γ −M)E [ T∑ k=1 h(wk) ] ≤ 1 T ( 2(1 + γ2)D2amaxd ηmin + 2γh(w0) ) +Mσ2.
Assuming 2− 2γ −M > 0 and dividing, we get
1 T E [ T∑ k=1 h(wk) ] ≤ 1 2− 2γ −M [ 1 T ( 2(1 + γ2)D2amaxd ηmin + 2γh(w0) ) +Mσ2 ] .
Using Jensen’s inequality and averaging the iterates finishes the proof.

heading: F EXPERIMENTAL DETAILS
text: Our proposed adaptive gradient methods with SLS and SPS step-sizes are presented in Algorithms 1 and 3. We now make a few additional remarks on the practical use of these methods.
Algorithm 1 Adaptive methods with SLS(f , precond, β, conservative, mode, w0, ηmax, b, c ∈ (0, 1), γ < 1)
1: for k = 0, . . . , T − 1 do 2: ik ← sample mini-batch of size b 3: Ak ← precond(k) . Form the preconditioner. 4: if mode == Lipschitz then 5: pk ← ∇fik(wk) 6: else if mode == Armijo then 7: pk ← A−1k ∇fik(wk) 8: end if 9: if conservative then 10: if k == 0 then 11: ηk ← ηmax 12: else 13: ηk ← ηk−1 14: end if 15: else 16: ηk ← ηmax 17: end if 18: while fik(wk − ηk · pk) > fik(wk)− c ηk 〈∇fik(wk), pk〉 do . Line-search loop 19: ηk ← γ ηk 20: end while 21: mk ← βmk−1 + (1− β)∇fik(wk) 22: wk+1 ← wk − ηkA−1k mk 23: end for 24: return wT
Algorithm 2 reset(η, ηmax, k, b, n, γ,opt) 1: if k = 0 then 2: return ηmax 3: else if opt= 0 then 4: η ← η 5: else if opt= 1 then 6: η ← η · γb/n 7: else if opt= 2 then 8: η ← ηmax 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 0 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, we use the heuristic from Vaswani et al. (2019b) corresponding to reset option 1. This option begins every backtracking with a slightly larger (by a factor of γb/n, γ = 2 throughout our experiments) step-size compared to the step-size at the previous iteration, and works well consistently across our experiments. Although we do not have theoretical guarantees for Armijo
SLS with general preconditioners such as Adam, our experimental results indicate that this is in fact a promising combination that also performs well in practice.
Algorithm 3 Adaptive methods with SPS(f , [f∗i ]ni=1, precond, β,conservative, mode, w0, ηmax, b, c)
1: for k = 0, . . . , T − 1 do 2: ik ← sample mini-batch of size b 3: Ak ← precond(k) . Form the preconditioner 4: if mode == Lipschitz then 5: pk ← ∇fik(wk) 6: else if mode == Armijo then 7: pk ← A−1k ∇fik(wk) 8: end if 9: if conservative then
10: if k == 0 then 11: ηB ← ηmax 12: else 13: ηB ← ηk−1 14: end if 15: else 16: ηB ← ηmax 17: end if 18: ηk ← min { fik (wk)−f ∗ ik )
c 〈∇fik (wk), pk〉 , ηB }

heading: 19: mk ← βmk−1 + (1− β)∇fik(wk)
text: 20: wk+1 ← wk − ηkA−1k mk 21: end for 22: 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 τ = 2b/n and show that both SPS and Armijo SPS work well. For the convex experiments, for both SLS and SPS, we set c = 0.5 as is suggested by the theory. For the non-convex experiments, we observe that all values of c ∈ [0.1, 0.5] result in reasonably good performance, but use the values suggested in Vaswani et al. (2019b); Loizou et al. (2020), i.e. c = 0.1 for all adaptive methods using SLS and c = 0.2 for methods using SPS.

heading: G ADDITIONAL EXPERIMENTAL RESULTS
text: In this section, we present additional experimental results showing the effect of the step-size for adaptive gradient methods using a 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. 6 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-parameterization 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, we quantify the gains of incorporating momentum in AMSGrad by comparing against the performance AMSGrad without momentum.

Review summaries:
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.

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.