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.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
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 a
term 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.
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
= 1
as 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 1
instead 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.
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.
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, 10
iterations) 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 10
and
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 10
iterations with batch size 1 when varying either
, 1
or 1
through a range of 13 values uniformly spaced in log-scale between 10
and 1. When varying
, we take
= 0 and
= 1
10
. When varying
, we take
= 10
and
= 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 10
iterations with
= 10
, then 10
iterations 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 10
and 10
with 9 values, for 1
the range is from 10
to 0.3 with 9 values, and for 1
, from 10
to 10
with 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.
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.
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
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.1 Setup and notations
We recall the dynamic system introduced in Section 2.3. In the rest of this section, we take an iteration , and when needed,
] refers to a specific coordinate. Given
our starting point,
= 0,
For Adam, the step size is given by
For Adagrad (potentially extended with heavy-ball momentum), we have = 1 and
Notice we include the factor 1 in the step size rather than in (A.1), as this allows for a more elegant proof. The original Adam algorithm included compensation factors for both
and
(Kingma & Ba, 2015) to correct the initial scale of m and v which are initialized at 0. Adam would be exactly recovered by replacing (A.2) with
However, the denominator 1 potentially makes (
non monotonic, which complicates the proof. Thus, we instead replace the denominator by its limit value for
. This has little practical impact as (i) early iterates are noisy because v is averaged over a small number of gradients, so making smaller step can be more stable, (ii) for
= 0.9 (Kingma & Ba, 2015), (A.2) differs from (A.4) only for the first 50 iterations.
Throughout the proof we note ] the conditional expectation with respect to
. In particular,
is deterministic knowing
. We introduce
For any with k < n, we define ˜
by
i.e. the contribution from the k last gradients are replaced by their expected value for know values of . For k = 1, we recover the same definition as in (18).
A.2 Results
For any total number of iterations , we define
a random index with value in
, verifying
If = 0, this is equivalent to sampling
uniformly in
. If
0, the last few
iterations are sampled rarely, and all iterations older than a few times that number are sampled almost uniformly. We bound the expected squared norm of the total gradient at iteration
, which is standard for non convex stochastic optimization (Ghadimi & Lan, 2013).
Note that like in previous works, the bound worsen as increases, with a dependency of the form O((1
). This is a significant improvement over the existing bound for Adagrad with heavy-ball momentum, which scales as (1
(Zou et al., 2019b), or the best known bound for Adam which scales as (1
(Zou et al., 2019a).
Technical lemmas to prove the following theorems are introduced in Section A.5, while the proof of Theorems 3 and 4 are provided in Section A.6.
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
A.3 Analysis of the results with momentum
First notice that taking 0 in Theorems 3 and 4, we almost recover the same result as stated in 2 and 1, only losing on the term 4
which becomes 12
.
Simplified expressions with momentum Assuming and
, which is verified for typical values of
and
(Kingma & Ba, 2015), it is possible to simplify the bound for Adam (13) as
Optimal finite horizon Adam is still Adagrad We can perform the same finite horizon analysis as in Section 4.3. If we take and
= 1
, then (A.9) simplifies to
The term (1 in the denominator in (A.9) is indeed compensated by the
in the numerator and we again recover the proper ln(
convergence rate, which matches (A.10) up to a +1 term next to the log.
A.4 Overview of the proof, contributions and limitations
There is a number of steps to the proof. First we derive a Lemma similar in spirit to the descent Lemma 5.1. There are two differences: first, when computing the dot product between the current expected gradient and each past gradient contained in the momentum, we have to re-center the expected gradient to its values in the past, using the smoothness assumption. Besides, we now have to decorrelate more terms between the numerator and denominator, as the numerator contains not only the latest gradient but a decaying sum of the past ones. We similarly extend Lemma 5.2 to support momentum specific terms. The rest of the proof follows mostly as in Section 5, except with a few more manipulation to regroup the gradient terms coming from different iterations.
Compared with previous work (Zou et al., 2019b;a), the re-centering of past gradients in (A.14) is a key aspect to improve the dependency in , with a small price to pay using the smoothness of F which is compensated by the introduction of extra
in (A.1). Then, a tight handling of the different summations as well as the the introduction of a non uniform sampling of the iterates (A.8), which naturally arises when grouping the different terms in (A.49), allow to obtain the overall improved dependency in O((1
).
The same technique can be applied to SGD, the proof becoming simpler as there is no correlation between the step size and the gradient estimate, see Section B. If you want to better understand the handling of momentum without the added complexity of adaptive methods, we recommend starting with this proof.
A limitation of the proof technique is that we do not show that heavy-ball momentum can lead to a variance reduction of the update. Either more powerful probabilistic results, or extra regularity assumptions could allow to further improve our worst case bounds of the variance of the update, which in turn might lead to a bound with an improvement when using heavy-ball momentum.
A.5 Technical lemmas
We first need an updated version of 5.1 that includes momentum.
Lemma A.1 (Adaptive update with momentum approximately follows a descent direction). Given , the iterates defined by the system (A.1) for (
that is non-decreasing, and under the conditions (6),
(7), and (8), as well as 0 1, we have for all iterations
,
Proof. We use multiple times (22) in this proof, which we repeat here for convenience,
Let us take an iteration for the duration of the proof. We have
Let us now take an index 0 1. We show that the contribution of past gradients
and
due to the heavy-ball momentum can be controlled thanks to the decay term
. Let us first have a look at B. Using (A.13) with
we have
Notice first that for any dimension ), so that
Besides, using the L-smoothness of F given by (8), we have
using Jensen inequality and the fact that is non-decreasing. Injecting (A.16) and (A.17) into (A.15), we obtain
Now going back to the A term in (A.14), we will study the main term of the summation, i.e. for ] and
Notice that we could almost apply Lemma 5.1 to it, except that we have in the denominator instead of
. Thus we will need to extend the proof to decorrelate more terms. We will further drop indices in the rest of the proof, noting
, ˜v = ˜
and
. Finally, let us note
In particular we have ˜. With our new notations, we can rewrite (A.19) as
We first focus on C:
due to the fact that +
+ ˜
max(
+ ˜v) and
.
Applying (A.13) to with
we obtain
Given that + ˜
and taking the conditional expectation, we can simplify as
Now turning to , we use (A.13) with
we obtain
Given that , and
= 1, we obtain after taking the conditional expectation,
Notice that in A.23, we possibly divide by zero. It suffice to notice that if = 0 then
= 0 a.s. so that
= 0 and (A.24) is still verified. Summing (A.22) and (A.24), we get
Given that + ˜v by definition of ˜v, and that using (7),
+ 1R, we have
, reintroducing the indices we had dropped
Taking the complete expectation and using that by definition ) we get
Injecting (A.27) into (A.21) gives us
Injecting (A.28) and (A.18) into (A.14) finishes the proof.
Similarly, we will need an updated version of 5.2.
Lemma A.2 (sum of ratios of the square of a decayed sum and a decayed sum of square). We assume we have 0 1 and 0
, and a sequence of real numbers (
. We define
=
and
=
. Then we have
Proof. Now let us take , we have using Jensen inequality
so that
Given that for ], we have by definition
), we get
Thus, when summing over all ], we get
Applying Lemma 5.2, we obtain (A.29).
We also need two technical lemmas on the sum of series. Lemma A.3 (sum of a geometric term times a square root). Given 0 < a < 1 and , we have,
where we used the classical integral of the standard Gaussian density function.
Let us now introduce :
then we have
where we used (A.33). Given thatln(
we obtain (A.32).
Lemma A.4 (sum of a geometric term times roughly a power 3/2). Given 0 < a < 1 and , we have,
Proof. Let us introduce :
then we have
A.6 Proof of Adam and Adagrad with momentum
Common part of the proof Let us a take an iteration . Using the smoothness of F defined in (8), we have
Taking the full expectation and using Lemma A.1,
Notice that because of the bound on the norm of the stochastic gradients at the iterates (7), we have for any
, and any coordinate
],
+ ˜
. Introducing Ω
,
we have
Now summing over all iterations ] for
, and using that for both Adam (A.2) and Adagrad (A.3),
is non-decreasing, as well the fact that F is bounded below by
from (6), we get
First looking at B, we have using Lemma A.2,
Then looking at C and introducing the change of index ,
using Lemma A.4. Finally, using Lemma A.2, we get
Finally, introducing the same change of index for D, we get
using Lemma A.3. Finally, using Lemma 5.2 or equivalently Lemma A.2 with = 0, we get
This is as far as we can get without having to use the specific form of given by either (A.2) for Adam or (A.3) for Adagrad. We will now split the proof for either algorithm.
Adam For Adam, using (A.2), we have = (1
. Thus, we can simplify the A term from (A.37), also using the usual change of index
, to get
If we now introduce as in (A.8), we can first notice that
we then have
Further notice that for any coordinate ], we have
, besides
, so that putting
together (A.37), (A.46), (A.38), (A.40) and (A.42) we get
with
This conclude the proof of theorem 4.
Adagrad For Adagrad, we have = (1
= 1 and Ω
so that,
Reusing (A.44) and (A.45) from the Adam proof, and introducing as in (9), we immediately have
Further notice that for any coordinate ], we have
, besides
= (1
, so that putting together (A.37), (A.50), (A.38), (A.40) and (A.42) with
= 1, we get
with
This conclude the proof of theorem 3.
A.7 Proof variant using Hölder inequality
Following (Ward et al., 2019; Zou et al., 2019b), it is possible to get rid of the almost sure bound on the gradient given by (7), and replace it with a bound in expectation, i.e.
Note that we now need an bound in order to properly apply the Hölder inequality hereafter:
We do not provide the full proof for the result, but point the reader to the few places where we have used (7). We first use it in Lemma A.1. We inject R into (A.15), which we can just replace with ˜R. Then we use (7) to bound r and derive (A.26). Remember that r is defined in (A.20), and is actually a weighted sum of the squared gradients in expectation. Thus, a bound in expectation is acceptable, and Lemma A.1 is valid replacing the assumption (7) with (A.53).
Looking at the actual proof, we use (6) in a single place: just after (A.35), in order to derive an upper bound for the denominator in the following term:
which gives us
Thus we can recover almost exactly (A.36) except we have to replace all terms of the form with
. The rest of the proof follows as before, with all the dependencies in
remaining the same.
We extend the existing proof of convergence for SGD in the non convex setting to use heavy-ball momentum (Ghadimi & Lan, 2013). Compared with previous work on momentum for non convex SGD byYang et al. (2016), we improve the dependency in from O((1
) to O((1
). A recent work by Liu et al. (2020) achieve a similar dependency of
)), with weaker assumptions (without the bounded gradients assumptions).
B.1 Assumptions
We reuse the notations from Section 2.1. Note however that we use here different assumptions than in Section 2.3. We first assume F is bounded below by , that is,
We then assume that the stochastic gradients have bounded variance, and that the gradients of F are uniformly bounded, i.e. there exist R and so that
B.2 Result
Let us take a step size 0 and a heavy-ball parameter 1
0. Given
, taking
= 0, we define for any iteration
the iterates of SGD with momentum as,
Note that in (B.4), the scale of the typical size of will increases with
. For any total number of iterations
, we define
a random index with value in
, verifying
Theorem B.1 (Convergence of SGD with momemtum). Given the assumptions from Section B.1, given as defined in (B.5) for a total number of iterations
,
0, 1
0, and (
given by (B.4),
with ˜.
B.3 Analysis
We can first simplify (B.6), if we assume , which is always the case for practical values of N and
, so that ˜
, and,
It is possible to achieve a rate of convergence of the form ), by taking for any C > 0,
which gives us
In comparison, Theorem 3 by Yang et al. (2016) would give us, assuming now that = (1
) min
We observe an overall dependency in of the form O((1
) for Theorem 3 by Yang et al. (2016) , which we improve to O((1
) with our proof.
Liu et al. (2020) achieves a similar dependency in (1 ) as here, but with weaker assumptions. Indeed, in their Theorem 1, their result contains a term in
) with
(1
for some problem dependent constant M that does not depend on
.
Notice that as the typical size of the update will increase with
, by a factor 1
), it is convenient to scale down
by the same factor, as we did with (B.8) (without loss of generality, as C can take any value). Taking
of this form has the advantage of keeping the first term on the right hand side in (B.6) independent of
, allowing us to focus only on the second term.
B.4 Proof
For all , we note
) and
] is the conditional expectation with respect to
. In particular,
and
are deterministic knowing
.
Lemma B.1 (Bound on ). Given
0, 1
0, and (
) and (
) defined as by B.4, under the assumptions from Section B.1, we have for all
,
Proof. Let us take an iteration ,
Lemma B.2 (sum of a geometric term times index). Given 0 < a < 1, and
with
,
Finally, taking i = 0 and gives us the upper bound.
Lemma B.3 (Descent lemma). Given 0, 1
0, and (
) and (
) defined as by B.4, under the assumptions from Section B.1, we have for all
,
Proof. For simplicity, we note ) the expected gradient and
) the stochastisc gradient at iteration n.
This last step is the main difference with previous proofs with momentum (Yang et al., 2016): we replace the current gradient with an old gradient in order to obtain extra terms of the form . The price to pay is the second term on the right hand side but we will see that it is still beneficial to perform this step. Notice that as F is L-smooth so that we have, for all
using Jensen inequality. We apply
with and
= 1
to the second term in (B.14), and use (B.15) to get
Taking the full expectation we have
Now let us take , first notice that
Furthermore, we have +
from (B.2), while
using (B.11) from Lemma B.1. Injecting those three results in (B.17), we have
Now, using (B.12) from Lemma B.2, we obtain
which concludes the proof.
Proof of Theorem B.1
Proof. Let us take a specific iteration . Using the smoothness of F given by (B.3), we have,
Taking the expectation, and using Lemma B.3 and Lemma B.1, we get
rearranging, and summing over , we get
Let us focus on the A term on the left-hand side first. Introducing the change of index , we get
We recognize the unnormalized probability given by the random iterate as defined by (B.5). The normalization constant is
which we can inject into (B.24) to obtain
Injecting (B.25) into (B.23), and using the fact that F is bounded below by (B.1), we have
which concludes the proof of Theorem B.1.