A Simple Convergence Proof of Adam and Adagrad

2020·Arxiv

Abstract

Abstract

We provide a simple proof of convergence covering both the Adam and Adagrad adaptive optimization algorithms when applied to smooth (possibly non-convex) objective functions with bounded gradients. We show that in expectation, the squared norm of the objective gradient averaged over the trajectory has an upper-bound which is explicit in the constants of the problem, parameters of the optimizer, the dimension d, and the total number of iterations N. This bound can be made arbitrarily small, and with the right hyper-parameters, Adam can be shown to converge with the same rate of convergence O(d ln(). When used with the default parameters, Adam doesn’t converge, however, and just like constant step-size SGD, it moves away from the initialization point faster than Adagrad, which might explain its practical success. Finally, we obtain the tightest dependency on the heavy ball momentum decay rate among all previous convergence bounds for non-convex Adam and Adagrad, improving from O((1 ) to O((1 ).

1 Introduction

First-order methods with adaptive step sizes have proved useful in many fields of machine learning, be it for sparse optimization (Duchi et al., 2013), tensor factorization (Lacroix et al., 2018) or deep learning (Goodfel- low et al., 2016). Duchi et al. (2011) introduced Adagrad, which rescales each coordinate by a sum of squared past gradient values. While Adagrad proved effective for sparse optimization (Duchi et al., 2013), experiments showed that it under-performed when applied to deep learning (Wilson et al., 2017). RMSProp (Tieleman & Hinton, 2012) proposed an exponential moving average instead of a cumulative sum to solve this. Kingma & Ba (2015) developed Adam, one of the most popular adaptive methods in deep learning, built upon RMSProp and added corrective terms at the beginning of training, together with heavy-ball style momentum.

In the online convex optimization setting, Duchi et al. (2011) showed that Adagrad achieves optimal regret for online convex optimization. Kingma & Ba (2015) provided a similar proof for Adam when using a decreasing overall step size, although this proof was later shown to be incorrect by Reddi et al. (2018), who introduced AMSGrad as a convergent alternative. Ward et al. (2019) proved that Adagrad also converges to a critical point for non convex objectives with a rate O(ln() when using a scalar adaptive step-size, instead of diagonal. Zou et al. (2019b) extended this proof to the vector case, while Zou et al. (2019a) displayed a bound for Adam, showing convergence when the decay of the exponential moving average scales as 1 and the learning rate as 1.

In this paper, we present a simplified and unified proof of convergence to a critical point for Adagrad and Adam for stochastic non-convex smooth optimization. We assume that the objective function is lower bounded, smooth and the stochastic gradients are almost surely bounded. We recover the standard O(ln() convergence rate for Adagrad for all step sizes, and the same rate with Adam with an appropriate choice of the step sizes and decay parameters, in particular, Adam can converge without using the AMSGrad variant. Compared to previous work, our bound significantly improves the dependency on the momentum parameter . The best known bounds for Adagrad and Adam are respectively in O((1 ) and O((1) (see Section 3), while our result is in O((1) for both algorithms. This improvement is a step toward understanding the practical efficiency of heavy-ball momentum.

Outline. The precise setting and assumptions are stated in the next section, and previous work is then described in Section 3. The main theorems are presented in Section 4, followed by a full proof for the case without momentum in Section 5. The proof of the convergence with momentum is deferred to the supplementary material, Section A. Finally we compare our bounds with experimental results, both on toy and real life problems in Section 6.

2 Setup

2.1 Notation

Let be the dimension of the problem (i.e. the number of parameters of the function to optimize) and take [d] = {1, 2, . . . , d}. Given a function , we denote by its gradient and the i-th component of the gradient. We use a small constant , e.g. 10, for numerical stability. Given a sequence (with , we denote for and ] the i-th component of the n-th element of the sequence.

We want to optimize a function . We assume there exists a random function such that )] = ) for all , and that we have access to an oracle providing i.i.d. samples (. We note ] the conditional expectation knowing . In machine learning, x typically represents the weights of a linear or deep model, f represents the loss from individual training examples or minibatches, and F is the full training objective function. The goal is to find a critical point of F.

2.2 Adaptive methods

We study both Adagrad (Duchi et al., 2011) and Adam (Kingma & Ba, 2015) using a unified formulation. We assume we have 0 1, 0 , and a non negative sequence (. We define three vectors iteratively. Given our starting point, = 0, and = 0, we define for all iterations ,

The parameter is a heavy-ball style momentum parameter (Polyak, 1964), while controls the decay rate of the per-coordinate exponential moving average of the squared gradients. Taking = 0, = 1 and gives Adagrad. While the original Adagrad algorithm did not include a heavy-ball-like momentum, our analysis also applies to the case 0.

Adam and its corrective terms The original Adam algorithm (Kingma & Ba, 2015) uses a weighed average, rather than a weighted sum for (1) and (2), i.e. it uses

We can achieve the same definition by taking . The original Adam algorithm further includes two corrective terms to account for the fact that and are biased towards 0 for the first few iterations. Those corrective terms are equivalent to taking a step-size of the form

Those corrective terms can be seen as the normalization factors for the weighted sum given by (1) and (2) Note that each term goes to its limit value within a few times 1) updates (with ). which explains the (1 ) term in (4). In the present work, we propose to drop the corrective term for , and to keep only the one for , thus using the alternative step size

This simplification motivated by several observations:

• By dropping either corrective terms, becomes monotonic, which simplifies the proof.

• For typical values of and (e.g. 0.9 and 0.999), the corrective term for converges to its limit value much faster than the one for .

• Removing the corrective term for is equivalent to a learning-rate warmup, which is popular in deep learning, while removing the one for would lead to an increased step size during early training. For values of close to 1, this can lead to divergence in practice.

We experimentally verify in Section 6.3 that dropping the corrective term for has no observable effect on the training process, while dropping the corrective term for leads to observable perturbations. In the following, we thus consider the variation of Adam obtained by taking provided by (5).

2.3 Assumptions

We make three assumptions. We first assume F is bounded below by , that is,

We then assume the norm of the stochastic gradients is uniformly almost surely bounded, i.e. there is is used here to simplify the final bounds) so that

3 Related work

Early work on adaptive methods (McMahan & Streeter, 2010; Duchi et al., 2011) showed that Adagrad achieves an optimal rate of convergence of ) for convex optimization (Agarwal et al., 2009). Later, RMSProp (Tieleman & Hinton, 2012) and Adam (Kingma & Ba, 2015) were developed for training deep neural networks, using an exponential moving average of the past squared gradients.

Kingma & Ba (2015) offered a proof that Adam with a decreasing step size converges for convex objectives. However, the proof contained a mistake spotted by Reddi et al. (2018), who also gave examples of convex problems where Adam does not converge to an optimal solution. They proposed AMSGrad as a convergent variant, which consisted in retaining the maximum value of the exponential moving average. When goes to zero, AMSGrad is shown to converge in the convex and non-convex setting (Fang & Klabjan, 2019; Zhou et al., 2018). Despite this apparent flaw in the Adam algorithm, it remains a widely popular optimizer, raising the question as to whether it converges. When goes to 1 and to 0, our results and previous work (Zou et al., 2019a) show that Adam does converge with the same rate as Adagrad. This is coherent with the counter examples of Reddi et al. (2018), because they uses a small exponential decay parameter 5.

The convergence of Adagrad for non-convex objectives was first tackled by Li & Orabona (2019), who proved its convergence, but under restrictive conditions (e.g., ). The proof technique was improved by Ward et al. (2019), who showed the convergence of “scalar” Adagrad, i.e., with a single learning rate, for any value of with a rate of O(ln(). Our approach builds on this work but we extend it to both Adagrad and Adam, in their coordinate-wise version, as used in practice, while also supporting heavy-ball momentum.

The coordinate-wise version of Adagrad was also tackled by Zou et al. (2019b), offering a convergence result for Adagrad with either heavy-ball or Nesterov style momentum. We obtain the same rate for heavy-ball momentum with respect to N (i.e., O(ln()), but we improve the dependence on the momentum parameter from O((1 ) to O((1 ). Chen et al. (2019) also provided a bound for Adagrad and Adam, but without convergence guarantees for Adam for any hyper-parameter choice, and with a worse dependency on . Zhou et al. (2018) also cover Adagrad in the stochastic setting, however their proof technique leads to aterm in their bound, typically with =10. Finally, a convergence bound for Adam was introduced by Zou et al. (2019a). We recover the same scaling of the bound with respect to and . However their bound has a dependency of O((1 ) with respect to , while we get O((1 ), a significant improvement. Shi et al. (2020) obtain similar convergence results for RMSProp and Adam when considering the random shuffling setup. They use an affine growth condition (i.e. norm of the stochastic gradient is bounded by an affine function of the norm of the deterministic gradient) instead of the boundness of the gradient, but their bound decays with the number of total epochs, not stochastic updates leading to an overall extra term with s the size of the dataset. Finally, Faw et al. (2022) use the same affine growth assumption to derive high probability bounds for scalar Adagrad.

Non adaptive methods like SGD are also well studied in the non convex setting (Ghadimi & Lan, 2013), with a convergence rate of ) for a smooth objective with bounded variance of the gradients. Unlike adaptive methods, SGD requires knowing the smoothness constant. When adding heavy-ball momentum, Yang et al. (2016) showed that the convergence bound degrades as O((1), assuming that the gradients are bounded. We apply our proof technique for momentum to SGD in the Appendix, Section B and improve this dependency to O((1 ). Recent work by Liu et al. (2020) achieves the same dependency with weaker assumptions. Defazio (2020) provided an in-depth analysis of SGD-M with a tight Liapunov analysis.

4 Main results

For a number of iterations , we note a random index with value in , so that

If = 0, this is equivalent to sampling uniformly in . If 0, the last few iterations are sampled rarely, and iterations older than a few times that number are sampled almost uniformly. Our results bound the expected squared norm of the gradient at iteration , which is standard for non convex stochastic optimization (Ghadimi & Lan, 2013).

4.1 Convergence bounds

For simplicity, we first give convergence results for = 0, along with a complete proof in Section 5. We then provide the results with momentum, with their proofs in the Appendix, Section A.6. We also provide a bound on the convergence of SGD with a ) dependency in the Appendix, Section B.2, along with its proof in Section B.4.

No heavy-ball momentum

Theorem 1 (Convergence of Adagrad without momentum). Given the assumptions from Section 2.3, the iterates defined in Section 2.2 with hyper-parameters verifying = 1, with 0 and = 0, and defined by (9), we have for any ,

Theorem 2 (Convergence of Adam without momentum). Given the assumptions from Section 2.3, the iterates defined in Section 2.2 with hyper-parameters verifying 0 1,

and = 0, and defined by (9), we have for any ,

with

With heavy-ball momentum

Theorem 3 (Convergence of Adagrad with momentum). Given the assumptions from Section 2.3, the iterates defined in Section 2.2 with hyper-parameters verifying = 1, with 0 and 0 1, and defined by (9), we have for any such that ,

with ˜, and,

Theorem 4 (Convergence of Adam with momentum). Given the assumptions from Section 2.3, the iterates defined in Section 2.2 with hyper-parameters verifying 0 1, 0 , and,

with ˜, and

4.2 Analysis of the bounds

Dependency on d. The dependency in d is present in previous works on coordinate wise adaptive methods (Zou et al., 2019a;b). Note however that R is defined as the bound on the on the stochastic gradient, so that in the case where the gradient has a similar scale along all dimensions, would be a reasonable bound for . However, if many dimensions contribute little to the norm of the gradient, this would still lead to a worse dependency in d that e.g. scalar Adagrad Ward et al. (2019) or SGD.

Diving into the technicalities of the proof to come, we will see in Section 5 that we apply Lemma 5.2 once per dimension. The contribution from each coordinate is mostly independent of the actual scale of its gradients (as it only appears in the log), so that the right hand side of the convergence bound will grow as d. In contrast, the scalar version of Adagrad (Ward et al., 2019) has a single learning rate, so that Lemma 5.2 is only applied once, removing the dependency on d. However, this variant is rarely used in practice.

Almost sure bound on the gradient. We chose to assume the existence of an almost sure uniform -bound on the gradients given by (7). This is a strong assumption, although it is weaker than the one used by Duchi et al. (2011) for Adagrad in the convex case, where the iterates were assumed to be almost surely bounded. There exist a few real life problems that verifies this assumption, for instance logistic regression without weight penalty, and with bounded inputs. It is possible instead to assume only a uniform bound on the expected gradient ), as done by Ward et al. (2019) and Zou et al. (2019b). This however lead to a bound on instead of a bound on , all the other terms staying the same. We provide the sketch of the proof using Hölder inequality in the Appendix, Section A.7.

It is also possible to replace the bound on the gradient with an affine growth condition, i.e. the norm of the stochastic gradient is bounded by an affine function of the norm of the expected gradient. A proof for scalar Adagrad is provided by Faw et al. (2022). Shi et al. (2020) do the same for RMSProp, however their convergence bound is decays as O(log() with T the number of epoch, not the number of updates, leading to a significantly less tight bound for large datasets.

Impact of heavy-ball momentum. Looking at Theorems 3 and 4, we see that increasing always deteriorates the bounds. Taking = 0 in those theorems gives us almost exactly the bound without heavy-ball momentum from Theorems 1 and 2, up to a factor 3 in the terms of the form .

As discussed in Section 3, previous bounds for Adagrad in the non-convex setting deteriorates as O((1) (Zou et al., 2019b), while bounds for Adam deteriorates as O((1 ) (Zou et al., 2019a). Our unified proof for Adam and Adagrad achieves a dependency of O((1 ), a significant improvement. We refer the reader to the Appendix, Section A.3, for a detailed analysis. While our dependency still contradicts the benefits of using momentum observed in practice, see Section 6, our tighter analysis is a step in the right direction.

On sampling of Note that in (9), we sample with a lower probability the latest iterations. This can be explained by the fact that the proof technique for stochastic optimization in the non-convex case is based on the idea that for every iteration n, either ) is small, or ) will decrease by some amount. However, when introducing momentum, and especially when taking the limit 1, the latest gradient ) has almost no influence over , as the momentum term updates slowly. Momentum spreads the influence of the gradients over time, and thus, it will take a few updates for a gradient to have fully influenced the iterate and thus the value of the function ). From a formal point of view, the sampling weights given by (9) naturally appear as part of the proof which is presented in Section A.6.

4.3 Optimal finite horizon Adam is Adagrad

Let us take a closer look at the result from Theorem 2. It could seem like some quantities can explode but actually not for any reasonable values of and N. Let us try to find the best possible rate of convergence for Adam for a finite horizon N, i.e. such that (ln() for some choice

of the hyper-parameters ) and ). Given that the upper bound in (11) is a sum of non-negative terms, we need each term to be of the order of ln(or negligible. Let us assume that this rate is achieved for ) and ). The bound tells us that convergence can only be achieved if lim ) = 0 and lim ) = 1, with the limits taken for . This motivates us to assume that there exists an asymptotic development of + ), and of 1 + ) for a and b positive. Thus, let us consider only the leading term in those developments, ignoring the leading constant (which is assumed to be non-zero). Let us further assume that , we have

with E = 4+ . Let us ignore the log terms for now, and use for , to get

Adding back the logarithmic term, the best rate we can obtain is O(ln(), and it is only achieved for a = 1/2 and b = 1, i.e., and = 1 . We can see the resemblance between Adagrad on one side and Adam with a finite horizon and such parameters on the other. Indeed, an exponential moving average with a parameter = 1as a typical averaging window length of size N, while Adagrad would be an exact average of the past N terms. In particular, the bound for Adam now becomes

which differ from (10) only by a +1) next to the log term.

Adam and Adagrad are twins. Our analysis highlights an important fact: Adam is to Adagrad like constant step size SGD is to decaying step size SGD. While Adagrad is asymptotically optimal, it also leads to a slower decrease of the term proportional to , as 1instead of 1/N for Adam. During the initial phase of training, it is likely that this term dominates the loss, which could explain the popularity of Adam for training deep neural networks rather than Adagrad. With its default parameters, Adam will not converge. It is however possible to choose and to achieve an critical point for arbitrarily small and, for a known time horizon, they can be chosen to obtain the exact same bound as Adagrad.

5 Proofs for β1 = 0 (no momentum)

We assume here for simplicity that = 0, i.e., there is no heavy-ball style momentum. Taking , the

recursions introduced in Section 2.2 can be simplified into

Remember that we recover Adagrad when for 0 and = 1, while Adam can be obtained taking 0 1, 0,

Throughout the proof we denote by ] the conditional expectation with respect to . In particular, and are deterministic knowing . For all , we also define ˜so that for all ],

i.e., we replace the last gradient contribution by its expected value conditioned on .

5.1 Technical lemmas

A problem posed by the update (16) is the correlation between the numerator and denominator. This prevents us from easily computing the conditional expectation and as noted by Reddi et al. (2018), the expected direction of update can have a positive dot product with the objective gradient. It is however possible to control the deviation from the descent direction, following Ward et al. (2019) with this first lemma.

Lemma 5.1 (adaptive update approximately follow a descent direction). For all and ], we have:

Proof. We take ] and note and ˜v = ˜.

Given that g and ˜v are independent knowing , we immediately have

Now we need to control the size of the second term A,

The last inequality comes from the fact that + ˜max(+ ˜v) and. Following Ward et al. (2019), we can use the following inequality to bound and ,

First applying (22) to with

we obtain

Given that + ˜and taking the conditional expectation, we can simplify as

Given that+ ˜v and, we can simplify (23) as

Now turning to , we use (22) with

we obtain

Given that and taking the conditional expectation we obtain

which we simplify using the same argument as for (24) into

Notice that in (25), we possibly divide by zero. It suffice to notice that if = 0 then = 0 a.s. so that = 0 and (27) is still verified. Summing (24) and (27) we can bound

Injecting (28) and (21) into (20) finishes the proof.

Anticipating on Section 5.2, the previous Lemma gives us a bound on the deviation from a descent direction. While for a specific iteration, this deviation can take us away from a descent direction, the next lemma tells us that the sum of those deviations cannot grow larger than a logarithmic term. This key insight introduced in Ward et al. (2019) is what makes the proof work.

Lemma 5.2 (sum of ratios with the denominator being the sum of past numerators). We assume we have 0 1 and a non-negative sequence (. We define for all = . We have

Proof. Given that ln is increasing, and the fact that 0, we have for all ,

The first term forms a telescoping series, while the second one is bounded by ln(). Summing over all ] gives the desired result.

5.2 Proof of Adam and Adagrad without momentum

Let us take an iteration , we define the update :

Adagrad. As explained in Section 2.2, we have for 0. Using the smoothness of F (8), we have

Taking the conditional expectation with respect to we can apply the descent Lemma 5.1. Notice that due to the a.s. bound on the gradients (7), we have for any ], + ˜, so that,

This gives us

Summing the previous inequality for all ], taking the complete expectation, and using that gives us,

From there, we can bound the last sum on the right hand side using Lemma 5.2 once for each dimension. Rearranging the terms, we obtain the result of Theorem 1.

Adam. As given by (5) in Section 2.2, we have

defined in (8), we have

We have for any ], + ˜=

(7), so that,

Taking the conditional expectation with respect to we can apply the descent Lemma 5.1 and use (34) to obtain from (33),

complete expectation yields

Applying Lemma 5.2 for each dimension and rearranging the terms finishes the proof of Theorem 2.

6 Experiments

On Figure 1, we compare the effective dependency of the average squared norm of the gradient in the parameters and for Adam, when used on a toy task and CIFAR-10.

6.1 Setup

Toy problem. In order to support the bounds presented in Section 4, in particular the dependency in , we test Adam on a specifically crafted toy problem. We take and define for all [6], = 10. We take (, Bernoulli variables with = 1] = . We then define f for all as

with for all ,

Figure 1: Observed average squared norm of the objective gradients after a fixed number of iterations when varying a single parameter out of , 1 and 1 , on a toy task (left, 10iterations) and on CIFAR-10 (right, 600 epochs with a batch size 128). All curves are averaged over 3 runs, error bars are negligible except for small values of on CIFAR-10. See Section 6 for details.

Figure 2: Training trajectories for varying values of 10and 999, 0.9999}. The top row (resp. bottom) gives the training loss (resp. squared norm of the expected gradient). The left column uses all corrective terms in the original Adam algorithm, the middle column drops the corrective term on (equivalent to our proof setup), and the right column drops the corrective term on . We notice a limited impact when dropping the corrective term on , but dropping the corrective term on has a much stronger impact.

Intuitively, each coordinate is pointing most of the time towards 1, but exceptionally towards -1 with a weight of 1. Those rare events happens less and less often as i increase, but with an increasing weight. Those weights are chosen so that all the coordinates of the gradient have the same variance. It is necessary to take different probabilities for each coordinate. If we use the same p for all, we observe a phase transition when 1 , but not the continuous improvement we obtain on Figure 1a.

We plot the variation of after 10iterations with batch size 1 when varying either , 1 or 1 through a range of 13 values uniformly spaced in log-scale between 10and 1. When varying , we take = 0 and = 1 10. When varying , we take = 10and = 1 10(i.e. is so that we are in the Adagrad-like regime). Finally, when varying , we take = 0 and = 10. We start from close to the optimum by running first 10iterations with = 10, then 10iterations with = 10, always with = 1 10. This allows to have 0 in (11) and (13) and focus on the second part of both bounds. All curves are averaged over three runs. Error bars are plotted but not visible in log-log scale.

CIFAR-10. We train a simple convolutional network (Gitman & Ginsburg, 2017) on the CIFAR-10image classification dataset. Starting from a random initialization, we train the model on a single V100 for 600 epochs with a batch size of 128, evaluating the full training gradient after each epoch. This is a proxy for , which would be to costly to evaluate exactly. All runs use the default config = 10, = 0.999 and = 0.9, and we then change one of the parameter.

We take from a uniform range in log-space between 10and 10with 9 values, for 1 the range is from 10to 0.3 with 9 values, and for 1, from 10to 10with 11 values. Unlike for the toy problem, we do not initialize close to the optimum, as even after 600 epochs, the norm of the gradients indicates that we are not at a critical point. All curves are averaged over three runs. Error bars are plotted but not visible in log-log scale, except for large values of .

6.2 Analysis

Toy problem. Looking at Figure 1a, we observe a continual improvement as increases. Fitting a linear regression in log-log scale of ] with respect to 1 gives a slope of 0.56 which is compatible with our bound (11), in particular the dependency in ). As we initialize close to the optimum, a small step size yields as expected the best performance. Doing the same regression in log-log scale, we find a slope of 0.87, which is again compatible with the ) dependency of the second term in (11). Finally, we observe a limited impact of , except when 1 is small. The regression in log-log scale gives a slope of -0.16, while our bound predicts a slope of -1.

CIFAR 10. Let us now turn to Figure 1b. As we start from random weights for this problem, we observe that a large step size gives the best performance, although we observe a high variance for the largest . This indicates that training becomes unstable for large , which is not predicted by the theory. This is likely a consequence of the bounded gradient assumption (7) not being verified for deep neural networks. We observe a small improvement as 1 decreases, although nowhere near what we observed on our toy problem. Finally, we observe a sweet spot for the momentum , not predicted by our theory. We conjecture that this is due to the variance reduction effect of momentum (averaging of the gradients over multiple mini-batches, while the weights have not moved so much as to invalidate past information).

6.3 Impact of the Adam corrective terms

Using the same experimental setup on CIFAR-10, we compare the impact of removing either of the corrective term of the original Adam algorithm (Kingma & Ba, 2015), as discussed in Section 2.2. We ran a cartesian product of training for 100 epochs, with 999, 0.9999}, and 10. We report both the training loss and norm of the expected gradient on Figure 2. We notice a limited difference when dropping the corrective term on , but dropping the term has an important impact on the training trajectories. This confirm our motivation for simplifying the proof by removing the corrective term on the momentum.

7 Conclusion

We provide a simple proof on the convergence of Adam and Adagrad without heavy-ball style momentum. Our analysis highlights a link between the two algorithms: with right the hyper-parameters, Adam converges like Adagrad. The extension to heavy-ball momentum is more complex, but we significantly improve the dependence on the momentum parameter for Adam, Adagrad, as well as SGD. We exhibit a toy problem where the dependency on and experimentally matches our prediction. However, we do not predict the practical interest of momentum, so that improvements to the proof are needed for future work.

Broader Impact Statement

The present theoretical results on the optimization of non convex losses in a stochastic settings impact our understanding of the training of deep neural network. It might allow a deeper understanding of neural network training dynamics and thus reinforce any existing deep learning applications. There would be however no direct possible negative impact to society.

References

Alekh Agarwal, Martin J Wainwright, Peter L Bartlett, and Pradeep K Ravikumar. Information-theoretic lower bounds on the oracle complexity of convex optimization. In Advances in Neural Information Processing Systems, 2009.

Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of Adam-type algorithms for non-convex optimization. In International Conference on Learning Representations, 2019.

Aaron Defazio. Momentum via primal averaging: Theoretical insights and learning rate schedules for non- convex optimization. arXiv preprint arXiv:2010.00406, 2020.

John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(Jul), 2011.

John Duchi, Michael I Jordan, and Brendan McMahan. Estimation, optimization, and parallelism when data is sparse. In Advances in Neural Information Processing Systems 26, 2013.

Biyi Fang and Diego Klabjan. Convergence analyses of online adam algorithm in convex setting and two-layer relu neural network. arXiv preprint arXiv:1905.09356, 2019.

Matthew Faw, Isidoros Tziotis, Constantine Caramanis, Aryan Mokhtari, Sanjay Shakkottai, and Rachel Ward. The power of adaptivity in sgd: Self-tuning step sizes with unbounded gradients and affine variance. In Po-Ling Loh and Maxim Raginsky (eds.), Proceedings of Thirty Fifth Conference on Learning Theory, Proceedings of Machine Learning Research. PMLR, 2022.

Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4), 2013.

Igor Gitman and Boris Ginsburg. Comparison of batch normalization and weight normalization algorithms for the large-scale image classification. arXiv preprint arXiv:1709.08145, 2017.

Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.

Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proc. of the International Conference on Learning Representations (ICLR), 2015.

Timothée Lacroix, Nicolas Usunier, and Guillaume Obozinski. Canonical tensor decomposition for knowledge base completion. arXiv preprint arXiv:1806.07297, 2018.

Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In AI Stats, 2019.

Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momen- tum. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 18261–18271. Curran Associates, Inc., 2020. URL https: //proceedings.neurips.cc/paper/2020/file/d3f5d4de09ea19461dab00590df91e4f-Paper.pdf.

H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. In COLT, 2010.

Boris T Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics, 4(5), 1964.

Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In Proc. of the International Conference on Learning Representations (ICLR), 2018.

Naichen Shi, Dawei Li, Mingyi Hong, and Ruoyu Sun. Rmsprop converges with proper hyper-parameter. In International Conference on Learning Representations, 2020.

T. Tieleman and G. Hinton. Lecture 6.5 — rmsprop. COURSERA: Neural Networks for Machine Learning, 2012.

Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex land- scapes. In International Conference on Machine Learning, 2019.

Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, 2017.

Tianbao Yang, Qihang Lin, and Zhe Li. Unified convergence analysis of stochastic momentum methods for convex and non-convex optimization. arXiv preprint arXiv:1604.03257, 2016.

Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXiv:1808.05671, 2018.

Fangyu Zou, Li Shen, Zequn Jie, Weizhong Zhang, and Wei Liu. A sufficient condition for convergences of Adam and RMSprop. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019a.

Fengyu Zou, Li Shen, Zenqun Jie, Ju Sun, and Wei Liu. Weighted Adagrad with unified momentum. arXiv preprint arXiv:1808.03408, 2019b.

Supplementary material for A Simple Convergence Proof of Adam and Adagrad

Overview

In Section A, we detail the results for the convergence of Adam and Adagrad with heavy-ball momentum. For an overview of the contributions of our proof technique, see Section A.4.

Then in Section B, we show how our technique also applies to SGD and improves its dependency in compared with previous work by Yang et al. (2016), from O((1) to . The proof is simpler than for Adam/Adagrad, and show the generality of our technique.

A Convergence of adaptive methods with heavy-ball momentum