Year: 2018

Abstract:
RMSProp and ADAM continue to be extremely popular algorithms for training neural nets but their theoretical convergence properties have remained unclear. Further, recent work has seemed to suggest that these algorithms have worse generalization properties when compared to carefully tuned stochastic gradient descent or its momentum variants. In this work, we make progress towards a deeper understanding of ADAM and RMSProp in two ways. First, we provide proofs that these adaptive gradient algorithms are guaranteed to reach criticality for smooth non-convex objectives, and we give bounds on the running time. Next we design experiments to empirically study the convergence and generalization properties of RMSProp and ADAM against Nesterov’s Accelerated Gradient method on a variety of common autoencoder setups and on VGG-9 with CIFAR-10. Through these experiments we demonstrate the interesting sensitivity that ADAM has to its momentum parameter β1. We show that at very high values of the momentum parameter (β1 = 0.99) ADAM outperforms a carefully tuned NAG on most of our experiments, in terms of getting lower training and test losses. On the other hand, NAG can sometimes do better when ADAM’s β1 is set to the most commonly used value: β1 = 0.9, indicating the importance of tuning the hyperparameters of ADAM to get better generalization performance. We also report experiments on different autoencoders to demonstrate that NAG has better abilities in terms of reducing the gradient norms, and it also produces iterates which exhibit an increasing trend for the minimum eigenvalue of the Hessian of the loss function at the iterates.

text: Next we design experiments to empirically study the convergence and generalization properties of RMSProp and ADAM against Nesterov’s Accelerated Gradient method on a variety of common autoencoder setups and on VGG-9 with CIFAR-10. Through these experiments we demonstrate the interesting sensitivity that ADAM has to its momentum parameter β1. We show that at very high values of the momentum parameter (β1 = 0.99) ADAM outperforms a carefully tuned NAG on most of our experiments, in terms of getting lower training and test losses. On the other hand, NAG can sometimes do better when ADAM’s β1 is set to the most commonly used value: β1 = 0.9, indicating the importance of tuning the hyperparameters of ADAM to get better generalization performance.
We also report experiments on different autoencoders to demonstrate that NAG has better abilities in terms of reducing the gradient norms, and it also produces iterates which exhibit an increasing trend for the minimum eigenvalue of the Hessian of the loss function at the iterates.

heading: 1 INTRODUCTION
text: Many optimization questions arising in machine learning can be cast as a finite sum optimization problem of the form: minx f(x) where f(x) = 1k ∑k i=1 fi(x). Most neural network problems also fall under a similar structure where each function fi is typically non-convex. A well-studied algorithm to solve such problems is Stochastic Gradient Descent (SGD), which uses updates of the form: xt+1 := xt − α∇f̃it(xt), where α is a step size, and f̃it is a function chosen randomly from {f1, f2, . . . , fk} at time t. Often in neural networks, “momentum” is added to the SGD update to yield a two-step update process given as: vt+1 = µvt−α∇f̃it(xt) followed by xt+1 = xt+vt+1. This algorithm is typically called the Heavy-Ball (HB) method (or sometimes classical momentum), with µ > 0 called the momentum parameter (Polyak, 1987). In the context of neural nets, another variant of SGD that is popular is Nesterov’s Accelerated Gradient (NAG), which can also be thought of as a momentum method (Sutskever et al., 2013), and has updates of the form vt+1 = µvt − α∇f̃it(xt + µvt) followed by xt+1 = xt + vt+1 (see Algorithm 1 for more details). Momentum methods like HB and NAG have been shown to have superior convergence properties compared to gradient descent in the deterministic setting both for convex and non-convex functions (Nesterov, 1983; Polyak, 1987; Zavriev & Kostyuk, 1993; Ochs, 2016; O’Neill & Wright, 2017; Jin et al., 2017). While (to the best of our knowledge) there is no clear theoretical justification in
the stochastic case of the benefits of NAG and HB over regular SGD in general (Yuan et al., 2016; Kidambi et al., 2018; Wiegerinck et al., 1994; Orr & Leen, 1994; Yang et al., 2016; Gadat et al., 2018), unless considering specialized function classes (Loizou & Richtárik, 2017); in practice, these momentum methods, and in particular NAG, have been repeatedly shown to have good convergence and generalization on a range of neural net problems (Sutskever et al., 2013; Lucas et al., 2018; Kidambi et al., 2018).
The performance of NAG (as well as HB and SGD), however, are typically quite sensitive to the selection of its hyper-parameters: step size, momentum and batch size (Sutskever et al., 2013). Thus, “adaptive gradient” algorithms such as RMSProp (Algorithm 2) (Tieleman & Hinton, 2012) and ADAM (Algorithm 3) (Kingma & Ba, 2014) have become very popular for optimizing deep neural networks (Melis et al., 2017; Xu et al., 2015; Denkowski & Neubig, 2017; Gregor et al., 2015; Radford et al., 2015; Bahar et al., 2017; Kiros et al., 2015). The reason for their widespread popularity seems to be the fact that they are believed to be easier to tune than SGD, NAG or HB. Adaptive gradient methods use as their update direction a vector which is the image under a linear transformation (often called the “diagonal pre-conditioner”) constructed out of the history of the gradients, of a linear combination of all the gradients seen till now. It is generally believed that this “pre-conditioning” makes these algorithms much less sensitive to the selection of its hyperparameters. A precursor to these RMSProp and ADAM was outlined in Duchi et al. (2011).
Despite their widespread use in neural net problems, adaptive gradients methods like RMSProp and ADAM lack theoretical justifications in the non-convex setting - even with exact/deterministic gradients (Bernstein et al., 2018). Further, there are also important motivations to study the behavior of these algorithms in the deterministic setting because of usecases where the amount of noise is controlled during optimization, either by using larger batches (Martens & Grosse, 2015; De et al., 2017; Babanezhad et al., 2015) or by employing variance-reducing techniques (Johnson & Zhang, 2013; Defazio et al., 2014).
Further, works like Wilson et al. (2017) and Keskar & Socher (2017) have shown cases where SGD (no momentum) and HB (classical momentum) generalize much better than RMSProp and ADAM with stochastic gradients. Wilson et al. (2017) also show that ADAM generalizes poorly for large enough nets and that RMSProp generalizes better than ADAM on a couple of neural network tasks (most notably in the character-level language modeling task). But in general it’s not clear and no heuristics are known to the best of our knowledge to decide whether these insights about relative performances (generalization or training) between algorithms hold for other models or carry over to the full-batch setting.
A summary of our contributions In this work we try to shed some light on the above described open questions about adaptive gradient methods in the following two ways.
• To the best of our knowledge, this work gives the first convergence guarantees for adaptive gradient based standard neural-net training heuristics. Specifically we show run-time bounds for deterministic RMSProp and ADAM to reach approximate criticality on smooth non-convex functions, as well as for stochastic RMSProp under an additional assumption. Recently, Reddi et al. (2018) have shown in the setting of online convex optimization that there are certain sequences of convex functions where ADAM and RMSprop fail to converge to asymptotically zero average regret. We contrast our findings with Theorem 3 in Reddi et al. (2018). Their counterexample for ADAM is constructed in the stochastic optimization framework and is incomparable to our result about deterministic ADAM. Our proof of convergence to approximate critical points establishes a key conceptual point that for adaptive gradient algorithms one cannot transfer intuitions about convergence from online setups to their more common use case in offline setups.
• Our second contribution is empirical investigation into adaptive gradient methods, where our goals are different from what our theoretical results are probing. We test the convergence and generalization properties of RMSProp and ADAM and we compare their performance against NAG on a variety of autoencoder experiments on MNIST data, in both full and mini-batch settings. In the full-batch setting, we demonstrate that ADAM with very high values of the momentum parameter (β1 = 0.99) matches or outperforms carefully tuned NAG and RMSProp, in terms of getting lower training and test losses. We show that as the autoencoder size keeps increasing, RMSProp fails to generalize pretty soon. In
the mini-batch experiments we see exactly the same behaviour for large enough nets. We further validate this behavior on an image classification task on CIFAR-10 using a VGG-9 convolutional neural network, the results to which we present in the Appendix E. We note that recently it has been shown by Lucas et al. (2018), that there are problems where NAG generalizes better than ADAM even after tuning β1. In contrast our experiments reveal controlled setups where tuning ADAM’s β1 closer to 1 than usual practice helps close the generalization gap with NAG and HB which exists at standard values of β1.
Remark. Much after this work was completed we came to know of a related paper (Li & Orabona, 2018) which analyzes convergence rates of a modification of AdaGrad (not RMSPRop or ADAM). After the initial version of our work was made public, a few other analysis of adaptive gradient methods have also appeared like Chen et al. (2018), Zhou et al. (2018) and Zaheer et al. (2018).

heading: 2 NOTATIONS AND PSEUDOCODES
text: Firstly we define the smoothness property that we assume in our proofs for all our non-convex objectives. This is a standard assumption used in the optimization literature. Definition 1. L−smoothness If f : Rd → R is at least once differentiable then we call it L−smooth for some L > 0 if for all x,y ∈ Rd the following inequality holds,
f(y) ≤ f(x) + 〈∇f(x),y − x〉+ L2 ‖y − x‖ 2 .
We need one more definition that of square-root of diagonal matrices, Definition 2. Square root of the Penrose inverse If v ∈ Rd and V = diag(v) then we define, V − 1 2 := ∑ i∈Support(v) 1√ vi eie T i , where {ei}{i=1,...,d} is the standard basis of Rd
Now we list out the pseudocodes used for NAG, RMSProp and ADAM in theory and experiments,

heading: Nesterov’s Accelerated Gradient (NAG) Algorithm
text: Algorithm 1 NAG 1: Input : A step size α, momentum µ ∈ [0, 1), and an initial starting
point x1 ∈ Rd, and we are given query access to a (possibly noisy) oracle for gradients of f : Rd → R.
2: function NAG(x1, α, µ) 3: Initialize : v1 = 0 4: for t = 1, 2, . . . do 5: vt+1 = µvt +∇f(xt) 6: xt+1 = xt − α(∇f(xt) + µvt+1) 7: end for 8: end function

heading: RMSProp Algorithm
text: Algorithm 2 RMSProp
1: Input : A constant vector Rd 3 ξ1d ≥ 0, parameter β2 ∈ [0, 1), step size α, initial starting point x1 ∈ Rd, and we are given query access to a (possibly noisy) oracle for gradients of f : Rd → R.
2: function RMSPROP(x1, β2, α, ξ) 3: Initialize : v0 = 0 4: for t = 1, 2, . . . do 5: gt = ∇f(xt) 6: vt = β2vt−1 + (1− β2)(g2t + ξ1d) 7: Vt = diag(vt) 8: xt+1 = xt − αV − 12 t gt 9: end for 10: end function

heading: ADAM Algorithm
text: Algorithm 3 ADAM
1: Input : A constant vector Rd 3 ξ1d > 0, parameters β1, β2 ∈ [0, 1), a sequence of step sizes {αt}t=1,2.., initial starting point x1 ∈ Rd, and we are given oracle access to the gradients of f : Rd → R.
2: function ADAM(x1, β1, β2, α, ξ) 3: Initialize : m0 = 0, v0 = 0 4: for t = 1, 2, . . . do 5: gt = ∇f(xt) 6: mt = β1mt−1 + (1− β1)gt 7: vt = β2vt−1 + (1− β2)g2t 8: Vt = diag(vt)
9: xt+1 = xt − αt ( V 1 2 t + diag(ξ1d) )−1 mt
10: end for 11: end function

heading: 3 CONVERGENCE GUARANTEES FOR ADAM AND RMSPROP
text: Previously it has been shown in Rangamani et al. (2017) that mini-batch RMSProp can off-the-shelf do autoencoding on depth 2 autoencoders trained on MNIST data while similar results using nonadaptive gradient descent methods requires much tuning of the step-size schedule. Here we give the first result about convergence to criticality for stochastic RMSProp albeit under a certain technical assumption about the training set (and hence on the first order oracle). Towards that we need the following definition,
Definition 3. The sign function We define the function sign : Rd → {−1, 1}d s.t it maps v 7→ (1 if vi ≥ 0 else − 1)i=1,...,d.
Theorem 3.1. Stochastic RMSProp converges to criticality (Proof in subsection A.1) Let f : Rd → R be L−smooth and be of the form f = 1k ∑k i=1 fi s.t. (a) each fi is at least once differentiable, (b) the gradients are s.t ∀x ∈ Rd,∀p, q ∈ {1, . . . , k}, sign(∇fp(x)) = sign(∇fq(x)) , (c) σf < ∞ is an upperbound on the norm of the gradients of fi and (d) f has a minimizer, i.e., there exists x∗ such that f(x∗) = minx∈Rd f(x). Let the gradient oracle be s.t when invoked at some xt ∈ Rd it uniformly at random picks it ∼ {1, 2, .., k} and returns, ∇fit(xt) = gt. Then corresponding to any , ξ > 0 and a starting point x1 for Algorithm 2, we can define,
T ≤ 1 4 ( 2Lσ2f (σ 2 f+ξ)(f(x1)−f(x∗))
(1−β2)ξ
) s.t. we are guaranteed that the iterates of Algorithm 2 using
a constant step-length of, α = 1√ T
√ 2ξ(1−β2)(f(x1)−f(x∗))
σ2fL will find an −critical point in at most T
steps in the sense that, mint=1,2...,T E[‖∇f(xt)‖2] ≤ 2.
Remark. We note that the theorem above continues to hold even if the constraint (b) that we have about the signs of the gradients of the {fi}i=1,...,k only holds on the points in Rd that the stochastic RMSProp visits and its not necessary for the constraint to be true everywhere in the domain. Further we can say in otherwords that this constraint ensures all the options for the gradient that this stochastic oracle has at any point, to lie in the same orthant of Rd though this orthant itself can change from one iterate of the next. A related result was concurrently shown by Zaheer et al. (2018).
Next we see that such sign conditions are not necessary to guarantee convergence of the deterministic RMSProp which corresponds to the full-batch RMSProp experiments in Section 5.3.
Theorem 3.2. Convergence of deterministic RMSProp - the version with standard speeds (Proof in subsection A.2) Let f : Rd → R be L−smooth and let σ < ∞ be an upperbound on the norm of the gradient of f . Assume also that f has a minimizer, i.e., there exists x∗ such that f(x∗) = minx∈Rd f(x). Then the following holds for Algorithm 2 with a deterministic gradient oracle:
For any , ξ > 0, using a constant step length of αt = α = (1−β2)ξ L √ σ2+ξ for t = 1, 2, ..., guarantees that ‖∇f(xt)‖ ≤ for some t ≤ 1 2 × 2L(σ2+ξ)(f(x1)−f(x∗))
(1−β2)ξ , where x1 is the first iterate of the algorithm.
One might wonder if the ξ parameter introduced in the algorithms above is necessary to get convergence guarantees for RMSProp. Towards that in the following theorem we show convergence of another variant of deterministic RMSProp which does not use the ξ parameter and instead uses other assumptions on the objective function and step size modulation. But these tweaks to eliminate the need of ξ come at the cost of the convergence rates getting weaker. Theorem 3.3. Convergence of deterministic RMSProp - the version with no ξ shift (Proof in subsection A.3) Let f : Rd → R be L−smooth and let σ < ∞ be an upperbound on the norm of the gradient of f . Assume also that f has a minimizer, i.e., there exists x∗ such that f(x∗) = minx∈Rd f(x), and the function f be bounded from above and below by constants B` and Bu as Bl ≤ f(x) ≤ Bu for all x ∈ Rd. Then for any > 0, ∃T = O( 1 4 ) s.t. the Algorithm 2 with a deterministic gradient oracle and ξ = 0 is guaranteed to reach a t-th iterate s.t. 1 ≤ t ≤ T and ‖∇f(xt)‖ ≤ .
In Section 5.3 we show results of our experiments with full-batch ADAM. Towards that, we analyze deterministic ADAM albeit in the small β1 regime. We note that a small β1 does not cut-off contributions to the update direction from gradients in the arbitrarily far past (which are typically significantly large), and neither does it affect the non-triviality of the pre-conditioner which does not depend on β1 at all. Theorem 3.4. Deterministic ADAM converges to criticality (Proof in subsection A.4) Let f : Rd → R be L−smooth and let σ < ∞ be an upperbound on the norm of the gradient of f . Assume also that f has a minimizer, i.e., there exists x∗ such that f(x∗) = minx∈Rd f(x). Then the following holds for Algorithm 3:
For any > 0, β1 < +σ and ξ > σ2β1
−β1σ+ (1−β1) , there exist step sizes αt > 0, t = 1, 2, . . . and a natural number T (depending on β1, ξ) such that ‖∇f(xt)‖ ≤ for some t ≤ T .
In particular if one sets β1 = +2σ , ξ = 2σ, and αt = ‖gt‖
2
L(1−βt1)2 4 3( +2σ)2 where gt is the gradient
of the objective at the tth iterate, then T can be taken to be 9Lσ 2
6 [f(x2) − f(x∗)], where x2 is the second iterate of the algorithm.
Our motivations towards the above theorem were primarily rooted in trying to understand the situations where ADAM can converge at all (given the negative results about ADAM as in Reddi et al. (2018)). But we point out that it remains open to tighten the analysis of deterministic ADAM and obtain faster rates than what we have shown in the theorem above. Remark. It is sometimes believed that ADAM gains over RMSProp because of its “bias correction term” which refers to the step length of ADAM having an iteration dependence of the following form, √ 1− βt2/(1 − βt1). In the above theorem, we note that the 1/(1 − βt1) term of this “bias correction term” naturally comes out from theory!

heading: 4 EXPERIMENTAL SETUP
text: For testing the empirical performance of ADAM and RMSProp, we perform experiments on fully connected autoencoders using ReLU activations and shared weights and on CIFAR-10 using VGG9, a convolutional neural network. Let z ∈ Rd be the input vector to the autoencoder, {Wi}i=1,..,` denote the weight matrices of the net and {bi}i=1,..,2` be the bias vectors. Then the output ẑ ∈ Rd of the autoencoder is defined as ẑ =W>1 σ(. . . σ(W > `−1σ(W > ` a+b`+1) +b`+2) . . . ) +b2` where a = σ(W`σ(. . . σ(W2σ(W1z + b1) + b2) . . . ) + b`). This defines an autoencoder with 2` − 1 hidden layers using ` weight matrices and 2` bias vectors. Thus, the parameters of this model are given by x = [vec(W1)> ... vec(W`)> b>1 ...b > 2`] > (where we imagine all vectors to be column vectors by default). The loss function, for an input z is then given by: f(z;x) = ‖z− ẑ‖2. Such autoencoders are a fairly standard setup that have been used in previous work (Arpit et al., 2015; Baldi, 2012; Kuchaiev & Ginsburg, 2017; Vincent et al., 2010). There have been relatively
fewer comparisons of ADAM and RMSProp with other methods on a regression setting. We were motivated by Rangamani et al. (2017) who had undertaken a theoretical analysis of autoencoders and in their experiments had found RMSProp to have good reconstruction error for MNIST when used on even just 2 layer ReLU autoencoders.
To keep our experiments as controlled as possible, we make all layers in a network have the same width (which we denote as h). Thus, given a size d for the input image, the weight matrices (as defined above) are given by: W1 ∈ Rh×d, Wi ∈ Rh×h, i = 2, . . . , `. This allowed us to study the effect of increasing depth ` or width h without having to deal with added confounding factors. For all experiments, we use the standard “Glorot initialization” for the weights (Glorot & Bengio, 2010), where each element in the weight matrix is initialized by sampling from a uniform distribution with [−limit, limit], limit = √ 6/(fanin + fanout), where fanin denotes the number of input units in the weight matrix, and fanout denotes the number of output units in the weight matrix. All bias vectors were initialized to zero. No regularization was used.
We performed autoencoder experiments on the MNIST dataset for various network sizes (i.e., different values of ` and h). We implemented all experiments using TensorFlow (Abadi et al., 2016) using an NVIDIA GeForce GTX 1080 Ti graphics card. We compared the performance of ADAM and RMSProp with Nesterov’s Accelerated Gradient (NAG). All experiments were run for 105 iterations. We tune over the hyper-parameters for each optimization algorithm using a grid search as described in the Appendix (Section B). To pick the best set of hyper-parameters, we choose the ones corresponding to the lowest loss on the training set at the end of 105 iterations. Further, to cut down on the computation time so that we can test a number of different neural net architectures, we crop the MNIST image from 28× 28 down to a 22× 22 image by removing 3 pixels from each side (almost all of which is whitespace).
Full-batch experiments We are interested in first comparing these algorithms in the full-batch setting. To do this in a computationally feasible way, we consider a subset of the MNIST dataset (we call this: mini-MNIST), which we build by extracting the first 5500 images in the training set and first 1000 images in the test set in MNIST. Thus, the training and testing datasets in miniMNIST is 10% of the size of the MNIST dataset. Thus the training set in mini-MNIST contains 5500 images, while the test set contains 1000 images. This subset of the dataset is a fairly reasonable approximation of the full MNIST dataset (i.e., contains roughly the same distribution of labels as in the full MNIST dataset), and thus a legitimate dataset to optimize on.
Mini-batch experiments To test if our conclusions on the full-batch case extend to the mini-batch case, we then perform the same experiments in a mini-batch setup where we fix the mini-batch size at 100. For the mini-batch experiment, we consider the full training set of MNIST, instead of the mini-MNIST dataset considered for the full-batch experiments and we also test on CIFAR-10 using VGG-9, a convolutional neural network.

heading: 5 EXPERIMENTAL RESULTS
text: 5.1 RMSPROP AND ADAM ARE SENSITIVE TO CHOICE OF ξ
The ξ parameter is a feature of the default implementations of RMSProp and ADAM such as in TensorFlow. Most interestingly this strictly positive parameter is crucial for our proofs. In this section we present experimental evidence that attempts to clarify that this isn’t merely a theoretical artefact but its value indeed has visible effect on the behaviours of these algorithms. We see in Figure 1 that on increasing the value of this fixed shift parameter ξ, ADAM in particular, is strongly helped towards getting lower gradient norms and lower test losses though it can hurt its ability to get lower training losses. The plots are shown for optimally tuned values for the other hyper-parameters.
5.2 TRACKING λmin(HESSIAN) OF THE LOSS FUNCTION
To check whether NAG, ADAM or RMSProp is capable of consistently moving from a “bad” saddle point to a “good” saddle point region, we track the most negative eigenvalue of the Hessian λmin(Hessian). Even for a very small neural network with around 105 parameters, it is still intractable to store the full Hessian matrix in memory to compute the eigenvalues. Instead, we use the
Scipy library function scipy.sparse.linalg.eigsh that can use a function that computes the matrix-vector products to compute the eigenvalues of the matrix (Lehoucq et al., 1998). Thus, for finding the eigenvalues of the Hessian, it is sufficient to be able to do Hessian-vector products. This can be done exactly in a fairly efficient way (Townsend, 2008).
We display a representative plot in Figure 2 which shows that NAG in particular has a distinct ability to gradually, but consistently, keep increasing the minimum eigenvalue of the Hessian while continuing to decrease the gradient norm. However unlike as in deeper autoencoders in this case the gradient norms are consistently bigger for NAG, compared to RMSProp and ADAM. In contrast, RSMProp and ADAM quickly get to a high value of the minimum eigenvalue and a small gradient norm, but somewhat stagnate there. In short, the trend looks better for NAG, but in actual numbers RMSProp and ADAM do better.

heading: 5.3 COMPARING PERFORMANCE IN THE FULL-BATCH SETTING
text: In Figure 3, we show how the training loss, test loss and gradient norms vary through the iterations for RMSProp, ADAM (at β1 = 0.9 and 0.99) and NAG (at µ = 0.9 and 0.99) on a 3 hidden layer autoencoder with 1000 nodes in each hidden layer trained on mini-MNIST. Appendix D.1 and D.2 have more such comparisons for various neural net architectures with varying depth and width and input image sizes, where the following qualitative results also extend.
Conclusions from the full-batch experiments of training autoencoders on mini-MNIST:
• Pushing β1 closer to 1 significantly helps ADAM in getting lower training and test losses and at these values of β1, it has better performance on these metrics than all the other algorithms. One sees cases like the one displayed in Figure 3 where ADAM at β1 = 0.9 was getting comparable or slightly worse test and training errors than NAG. But once β1 gets closer to 1, ADAM’s performance sharply improves and gets better than other algorithms.
• Increasing momentum helps NAG get lower gradient norms though on larger nets it might hurt its training or test performance. NAG does seem to get the lowest gradient norms compared to the other algorithms, except for single hidden layer networks like in Figure 2.

heading: 5.4 CORROBORATING THE FULL-BATCH BEHAVIORS IN THE MINI-BATCH SETTING
text: In Figure 4, we show how training loss, test loss and gradient norms vary when using mini-batches of size 100, on a 5 hidden layer autoencoder with 1000 nodes in each hidden layer trained on the full MNIST dataset. The same phenomenon as here has been demonstrated in more such mini-batch comparisons on autoencoder architectures with varying depths and widths in Appendix D.3 and on VGG-9 with CIFAR-10 in Appendix E.
Conclusions from the mini-batch experiments of training autoencoders on full MNIST dataset:
• Mini-batching does seem to help NAG do better than ADAM on small nets. However, for larger nets, the full-batch behavior continues, i.e., when ADAM’s momentum parameter β1 is pushed closer to 1, it gets better generalization (significantly lower test losses) than NAG at any momentum tested.
• In general, for all metrics (test loss, training loss and gradient norm reduction) both ADAM as well as NAG seem to improve in performance when their momentum parameter (µ for NAG and β1 for ADAM) is pushed closer to 1. This effect, which was present in the full-batch setting, seems to get more pronounced here.
• As in the full-batch experiments, NAG continues to have the best ability to reduce gradient norms while for larger enough nets, ADAM at large momentum continues to have the best training error.

heading: 6 CONCLUSION
text: To the best of our knowledge, we present the first theoretical guarantees of convergence to criticality for the immensely popular algorithms RMSProp and ADAM in their most commonly used setting of optimizing a non-convex objective.
By our experiments, we have sought to shed light on the important topic of the interplay between adaptivity and momentum in training nets. By choosing to study textbook autoencoder architectures
where various parameters of the net can be changed controllably we highlight the following two aspects that (a) the value of the gradient shifting hyperparameter ξ has a significant influence on the performance of ADAM and RMSProp and (b) ADAM seems to perform particularly well (often supersedes Nesterov accelerated gradient method) when its momentum parameter β1 is very close to 1. On VGG-9 with CIFAR-10 and for the task of training autoencoders on MNIST we have verified these conclusions across different widths and depths of nets as well as in the full-batch and the mini-batch setting (with large nets) and under compression of the input/out image size. Curiously enough, this regime of β1 being close to 1 is currently not within the reach of our proof techniques of showing convergence for ADAM. Our experiments give strong reasons to try to advance theory in this direction in future work.

heading: A PROOFS OF CONVERGENCE OF (STOCHASTIC) RMSPROP AND ADAM

heading: A.1 PROVING STOCHASTIC RMSPROP (PROOF OF THEOREM 3.1)
text: Now we give the proof of Theorem 3.1.
Proof. We define σt := maxk=1,..,t ‖∇fik(xk)‖ and we solve the recursion for vt as, vt = (1 − β2) ∑t k=1 β t−k 2 (g 2 k + ξ). This lets us write the following bounds,
λmin(V − 12 t ) ≥ 1√ maxi=1,..,d(vt)i ≥ 1√ maxi=1,..,d((1− β2) ∑t k=1 β t−k 2 (g 2 k + ξ1d)i)
≥ 1√ 1− βt2 √ σ2t + ξ
Now we define, t := mink=1,..,t,i=1,..,d(∇fik(xk))2i and this lets us get the following bounds,
λmax(V − 12 t ) ≤
1 mini=1,..,d( √ (vt)i) ≤ 1√ (1− βt2) √ (ξ + t)
Now we invoke the bounded gradient assumption about the fi functions and replace in the above equation the eigenvalue bounds of the pre-conditioner by worst-case estimates µmax and µmin defined as,
λmin(V − 12 t ) ≥ 1√ σ2f + ξ := µmin
λmax(V − 12 t ) ≤ 1√ (1− β2) √ ξ := µmax
Using the L-smoothness of f between consecutive iterates xt and xt+1 we have,
f(xt+1) ≤ f(xt) + 〈∇f(xt),xt+1 − xt〉+ L
2 ‖xt+1 − xt‖2
We note that the update step of stochastic RMSProp is xt+1 = xt − α(Vt)− 1 2 gt where gt is the stochastic gradient at iterate xt. Let Ht = {x1,x2, ..,xt} be the set of random variables corresponding to the first t iterates. The assumptions we have about the stochastic oracle give us the following relations, E[gt] = ∇f(xt) and E[‖gt‖2] ≤ σ2f . Now we can invoke these stochastic oracle’s properties and take a conditional (onHt) expectation over gt of the L−smoothness in equation to get,
E[f(xt+1) | Ht] ≤ f(xt)− αE [ 〈∇f(xt), (Vt)− 1 2gt〉 | Ht ] + α2L 2 E [ ‖(Vt)− 1 2gt‖2 | Ht ] ≤ f(xt)− αE [ 〈∇f(xt), (Vt)− 1 2gt〉 | Ht ] + µ2max α2L 2 E [ ‖gt‖2 | Ht
] ≤ f(xt)− αE [ 〈∇f(xt), (Vt)− 1 2gt〉 | Ht ] + µ2max α2σ2fL
2 (1)
We now separately analyze the middle term in the RHS above in Lemma A.1 below and we get,
E[〈∇f(xt), (Vt)− 1 2gt〉 | Ht] ≥ µmin‖∇f(xt)‖2
We substitute the above into equation 1 and take expectations over Ht to get,
E[f(xt+1)− f(xt)] ≤ −αµmin‖∇f(xt)‖2 + µ2max α2σ2fL
2
=⇒ E[‖∇f(xt)‖2] ≤ 1
αµmin E[f(xt)− f(xt+1)] +
ασ2fL
2 µ2max µmin
(2)
Doing the above replacements to upperbound the RHS of equation 2 and summing the inequation over t = 1 to t = T and taking the average and replacing the LHS by a lowerbound of it, we get,
min t=1...T
E[‖∇f(xt)‖2] ≤ 1
αTµmin E[f(x1)− f(xT+1)] +
ασ2fL
2 µ2max µmin
≤ 1 αTµmin
(f(x1)− f(x∗)) + ασ2fL
2 µ2max µmin
Replacing into the RHS above the optimal choice of,
α = 1√ T
√ 2 (f(x1)− f(x∗))
σ2fLµ 2 max
= 1√ T
√ 2ξ(1− β2) (f(x1)− f(x∗))
σ2fL
we get,
min t=1...T
E[‖∇f(xt)‖2] ≤ 2
√ 1
Tµmin (f(x1)− f(x∗))× Lσ2f 2 µ2max µmin = 1√ T
√ 2Lσ2f (σ 2 f + ξ) (f(x1)− f(x∗))
(1− β2)ξ
Thus stochastic RMSProp with the above step-length is guaranteed is reach −criticality in number of iterations given by, T ≤ 1 4
( 2Lσ2f (σ 2 f+ξ)(f(x1)−f(x∗))
(1−β2)ξ ) Lemma A.1. At any time t, the following holds,
E[〈∇f(xt), V −1/2t gt〉 | Ht] ≥ µmin ‖∇f(xt)‖ 2

heading: Proof.
text: E [ 〈∇f(xt), V −1/2t gt〉 | Ht ] = E [ d∑ i=1 ∇if(xt)(V −1/2t )ii(gt)i | Ht ]
= d∑ i=1 ∇if(xt)E [ (V −1/2 t )ii(gt)i | Ht ] (3)
Now we introduce some new variables to make the analysis easier to present. Let api := [∇fp(xt)]i where p indexes the training data set, p ∈ {1, . . . , k}. (conditioned on Ht, apis are constants) This implies, ∇if(xt) = 1k ∑k p=1 api We recall that E [(gt)i] = ∇if(xt) where the expectation is taken over the oracle call at the tth update step. Further our instantiation of the oracle is equivalent to doing the uniformly at random sampling, (gt)i ∼ {api}p=1,...,k.
Given that we have, Vt = diag(vt) with vt = (1 − β2) ∑t k=1 β t−k 2 (g 2 k + ξ1d) this implies, (V −1/2t )ii = 1√
(1−β2)(gt)2i+di where we have defined di := (1 − β2)ξ + (1 − β2) ∑t−1 k=1 β t−k 2 ((gk) 2 i + ξ). (conditioned on Ht, di is a constant) This leads to an explicit form of the needed expectation over the tth−oracle call as,
E [ (V −1/2 t )ii(gt)i | Ht ] = E [ (V −1/2 t )ii(gt)i | Ht ] = E(gt)i∼{api}p=1,...,k [ (gt)i√
(1− β2)(gt)2i + di | Ht
]
= 1
k k∑ p=1 api√ (1− β2)a2pi + di
Substituting the above (and the definition of the constants api) back into equation 3 we have,
E [ 〈∇f(xt), V −1/2t gt〉 | Ht ] = d∑ i=1
( 1
k k∑ p=1 api )1 k k∑ p=1 api√ (1− β2)a2pi + di 
We define two vectors ai,hi ∈ Rk s.t (ai)p = api and (hi)p = 1√ (1−β2)a2pi+di
Substituting this, the above expression can be written as,
E [ 〈∇f(xt), V −1/2t gt〉 | Ht ] = 1
k2 d∑ i=1 ( a>i 1k ) ( h>i ai ) = 1 k2 d∑ i=1 a>i ( 1kh > i ) ai (4)
Note that with this substitution, the RHS of the claimed lemma becomes,
µmin ‖∇f(xt)‖2 = µmin d∑ i=1
( 1
k k∑ p=1 ∇pf(xt)
)2
= µmin k2 d∑ i=1 (a>i 1k) 2
= µmin k2 d∑ i=1 a>i 1k1 > k ai
Therefore our claim is proved if we show that for all i, 1k2 a > i ( 1kh > i ) ai− µmink2 a > i 1k1 > k ai ≥ 0. This can be simplified as,
1 k2 a>i ( 1kh > i ) ai − µmin 1 k2 a>i 1k1 > k ai = 1 k2 a>i ( 1k (hi − µmin1k)> ) ai
To further simplify, we define qi ∈ Rk, (qi)p = (hi)p−µmin = 1√ (1−β2)a2pi+di −µmin. We therefore need to show,
1 k2 a>i ( 1kq > i ) ai ≥ 0
We first bound di by recalling the definition of σf (from which it follows that a2pi ≤ σ2f ),
di ≤ (1− β2) [ ξ +
t−1∑ k=1 βt−k2 (σ 2 f + ξ)
] = (1− β2) [ ξ +
β2 − βt−12 1− β2 (σ2f + ξ) ] ≤ (1− β2)ξ + (β2 − βt−12 )ξ + (β2 − β t−1 2 )σ 2 f = (1− βt−12 )ξ + (β2 − β t−1 2 )σ 2 f
=⇒ √ (1− β2)a2pi + di ≤ √ (1− β2)σ2f + (1− β t−1 2 )ξ + (β2 − β t−1 2 )σ 2 f = √ (1− βt−12 )(σ2f + ξ) =⇒ −µmin + 1√
(1− β2)a2pi + di ≥ −µmin + 1√ (1− βt−12 )(σ2f + ξ) = − 1√ σ2f + ξ + 1√ (1− βt−12 )(σ2f + ξ)
=⇒ −µmin + 1√
(1− β2)a2pi + di ≥ 0 (5)
The inequality follows since β2 ∈ (0, 1] Putting this all together, we get,
(a>i 1k)(q > i ai)
= ( k∑ p=1 api ) k∑ p=1 −µminapi + api√ (1− β2)a2pi + di  =
k∑ p,q=1 −µminapiaqi + apiaqi√ (1− β2)a2pi + di  =
k∑ p,q=1 apiaqi −µmin + 1√ (1− β2)a2pi + di  Now our assumption that for all x, sign(∇fp(x)) = sign(∇fq(x)) for all p, q ∈ {1, . . . , k} leads to the conclusion that the term apiaqi ≥ 0. And we had already shown in equation 5 that[ −µmin + 1√
(1−β2)a2pi+di
] ≥ 0. Thus we have shown that (a>i 1k)(q>i ai) ≥ 0 and this finishes the
proof.

heading: A.2 PROVING DETERMINISTIC RMSPROP - THE VERSION WITH STANDARD SPEED (PROOF
text: OF THEOREM 3.2)
Proof. By the L−smoothness condition and the update rule in Algorithm 2 we have,
f(xt+1) ≤ f(xt)− αt〈∇f(xt), V − 12 t ∇f(xt)〉+ α2t L 2 ‖V − 1 2 t ∇f(xt)‖2
=⇒ f(xt+1)− f(xt) ≤ αt ( Lαt 2 ‖V − 1 2 t ∇f(xt)‖2 − 〈∇f(xt), V − 12 t ∇f(xt)〉 ) (6)
For 0 < δ2t < 1√ 1−βt2 √ σ2t+ξ we now show a strictly positive lowerbound on the following function,
2
L
( 〈∇f(xt), V − 12 t ∇f(xt)〉 − δ2t ‖∇f(xt)‖ 2
‖V − 1 2
t ∇f(xt)‖2
) (7)
We define σt := maxi=1,..,t ‖∇f(xi)‖ and we solve the recursion for vt as, vt = (1 − β2) ∑t k=1 β t−k 2 (g 2 k + ξ). This lets us write the following bounds,
〈∇f(xt), V − 12 t ∇f(xt)〉 ≥ λmin(V − 12 t )‖∇f(xt)‖2 ≥ ‖∇f(xt)‖2√ maxi=1,..,d(vt)i
≥ ‖∇f(xt)‖ 2√
maxi=1,..,d((1− β2) ∑t k=1 β t−k 2 (g 2 k + ξ1d)i)
≥ ‖∇f(xt)‖ 2√ 1− βt2 √ σ2t + ξ
(8)
Now we define, t := mink=1,..,t,i=1,..,d(∇f(xk))2i and this lets us get the following sequence of inequalities,
‖V − 1 2 t ∇f(xt)‖2 ≤ λ2max(V − 12 t )‖∇f(xt)‖2 ≤
‖∇f(xt)‖2 (mini=1,..,d( √ (vt)i))2 ≤ ‖∇f(xt)‖ 2 (1− βt2)(ξ + t) (9)
So combining equations 9 and 8 into equation 7 and from the exit line in the loop we are assured that ‖∇f(xt)‖2 6= 0 and combining these we have,
2
L
( −δ2t ‖∇f(xt)‖ 2 + 〈∇f(xt), V − 12 t ∇f(xt)〉
‖V − 1 2
t ∇f(xt)‖2
) ≥ 2 L −δ2t + 1√1−βt2√σ2t+ξ 1
(1−βt2)(ξ+ t)  ≥ 2(1− β t 2)(ξ + t)
L
( −δ2t +
1√ 1− βt2 √ σ2t + ξ
)
Now our definition of δ2t allows us to define a parameter 0 < βt := 1√ 1−βt2 √ σ2t+ξ − δ2t and rewrite the above equation as,
2
L
( −δ2t ‖∇f(xt)‖ 2 + 〈∇f(xt), V − 12 t ∇f(xt)〉
‖V − 1 2
t ∇f(xt)‖2
) ≥ 2(1− β
t 2)(ξ + t)βt L
(10)
We can as well satisfy the conditions needed on the variables, βt and δt by choosing,
δ2t = 1
2 min t=1,... 1√ 1− βt2 √ σ2t + ξ = 1 2 1√ σ2 + ξ =: δ2
and
βt = min t=1,.. 1√ 1− βt2 √ σ2t + ξ − δ2 = 1 2 1√ σ2 + ξ
Then the worst-case lowerbound in equation 10 becomes,
2
L
( −δ2t ‖∇f(xt)‖ 2 + 〈∇f(xt), V − 12 t ∇f(xt)〉
‖V − 1 2
t ∇f(xt)‖2
) ≥ 2(1− β2)ξ
L × 1 2 1√ σ2 + ξ
This now allows us to see that a constant step length αt = α > 0 can be defined as, α = (1−β2)ξ
L √ σ2+ξ and this is such that the above equation can be written as, Lα2 ‖V − 12 t ∇f(xt)‖2 −
〈∇f(xt), V − 12 t ∇f(xt)〉 ≤ −δ2 ‖∇f(xt)‖ 2 . This when substituted back into equation 6 we have,
f(xt+1)− f(xt) ≤ −δ2α ‖∇f(xt)‖2 = −δ2α ‖∇f(xt)‖2
This gives us,
‖∇f(xt)‖2 ≤ 1
δ2α [f(xt)− f(xt+1)]
=⇒ T∑ t=1 ‖∇f(xt)‖2 ≤ 1 δ2α [f(x1)− f(x∗)] (11)
=⇒ min t=1,,.T
‖∇f(xt)‖2 ≤ 1
Tδ2α [f(x1)− f(x∗)] (12)
Thus for any given > 0, T satisfying, 1Tδ2α [f(x1)−f(x∗)] ≤ 2 is a sufficient condition to ensure that the algorithm finds a point xresult := argmint=1,,.T ‖∇f(xt)‖ 2 with ‖∇f(xresult)‖2 ≤ 2.
Thus we have shown that using a constant step length of α = (1−β2)ξ L √ σ2+ξ deterministic RMSProp can find an −critical point in T = 1 2 × f(x1)−f(x∗) δ2α = 1 2 × 2L(σ2+ξ)(f(x1)−f(x∗)) (1−β2)ξ steps.

heading: A.3 PROVING DETERMINISTIC RMSPROP - THE VERSION WITH NO ADDED SHIFT (PROOF
text: OF THEOREM 3.3)
Proof. From the L−smoothness condition on f we have between consecutive iterates of the above algorithm,
f(xt+1) ≤ f(xt)− αt〈∇f(xt), V − 12 t ∇f(xt)〉+ L
2 α2t ‖V
− 12 t ∇f(xt)‖2
=⇒ 〈∇f(xt), V − 12 t ∇f(xt)〉 ≤ 1
αt (f(xt)− f(xt+1)) + Lαt 2 ‖V − 1 2 t ∇f(xt)‖2 (13)
(14)
Now the recursion for vt can be solved to get, vt = (1 − β2) ∑t k=1 β t−k 2 g 2 k.
Then ∥∥∥V 12t ∥∥∥ ≥ 1maxi∈Support(vt)√(vt)i = 1maxi∈Support(vt)√(1−β2)∑tk=1 βt−k2 (g2k)i =
1 maxi∈Support(vt) σ √ (1−β2) ∑t k=1 β t−k 2 = 1 σ √ (1−βt2) . Substituting this in a lowerbound on the LHS of equation 13 we get,
1 σ √ (1− βt2) ‖∇f(xt)‖2 ≤ 〈∇f(xt), V − 12 t ∇f(xt)〉 ≤ 1 αt (f(xt)− f(xt+1))+ Lαt 2 ‖V − 1 2 t ∇f(xt)‖2
Summing the above we get, T∑ t=1 1 σ √ (1− βt2) ‖∇f(xt)‖2 ≤ T∑ t=1 1 αt (f(xt)− f(xt+1)) + T∑ t=1 Lαt 2 ‖V − 1 2 t ∇f(xt)‖2 (15)
Now we substitute αt = α√t and invoke the definition of B` and Bu to write the first term on the RHS of equation 15 as,
T∑ t=1 1 αt [f(xt)− f(xt+1)] = f(x1) α + T∑ t=1 ( f(xt+1) αt+1 − f(xt+1) αt ) − f(xT+1) αT+1
= f(x1) α − f(xT+1) αT+1 + 1 α T∑ t=1 f(xt+1)( √ t+ 1− √ t)
≤ Bu α − B`
√ T + 1
α + Bu α
( √ T + 1− 1)
Now we bound the second term in the RHS of equation 15 as follows. Lets first define a function P (T ) as follows, P (T ) = ∑T t=1 αt‖V − 12 t ∇f(xt)‖2 and that gives us,
P (T )− P (T − 1) = αT d∑ i=1 g2T,i vT,i = αT d∑ i=1
g2T,i (1− β2) ∑T k=1 β T−k 2 g 2 k,i
= αT
(1− β2) d∑ i=1 g2T,i∑T k=1 β T−k 2 g 2 k,i ≤ dα (1− β2) √ T
=⇒ T∑ t=2 [P (t)− P (t− 1)] = P (T )− P (1) ≤ dα (1− β2) T∑ t=2 1√ t ≤ dα 2(1− β2) ( √ T − 2)
=⇒ P (T ) ≤ P (1) + dα 2(1− β2)
( √ T − 2)
So substituting the above two bounds back into the RHS of the above inequality 15and removing the factor of √ 1− βT2 < 1 from the numerator, we can define a point xresult as follows,
‖∇f(xresult)‖2 := argmin t=1,..,T
‖∇f(xt)‖2 ≤ 1
T T∑ t=1 ‖∇f(xt)‖2
≤ σ T ( Bu α − Bl √ T + 1 α + Bu α ( √ T + 1− 1)
+ L
2
[ P (1) +
dα 2(1− β2) ( √ T − 2)
])
Thus it follows that for T = O( 1 4 ) the algorithm 2 is guaranteed to have found at least one point xresult such that, ‖∇f(xresult)‖2 ≤ 2

heading: A.4 PROVING ADAM (PROOF OF THEOREM 3.4)

heading: Proof.
text: Let us assume to the contrary that ‖gt‖ > for all t = 1, 2, 3. . . .. We will show that this assumption will lead to a contradiction. By L−smoothness of the objective we have the following relationship between the values at consecutive updates,
f(xt+1) ≤ f(xt) + 〈∇f(xt),xt+1 − xt〉+ L
2 ‖xt+1 − xt‖2
Substituting the update rule using a dummy step length ηt > 0 we have,
f(xt+1) ≤ f(xt)− ηt〈∇f(xt), ( V 1 2 t + diag(ξ1d) )−1 mt〉+
Lη2t 2 ∥∥∥∥(V 12t + diag(ξ1d))−1mt∥∥∥∥2 =⇒ f(xt+1)− f(xt) ≤ ηt ( −〈gt, ( V 1 2 t + diag(ξ1d) )−1 mt〉+
Lηt 2 ∥∥∥∥(V 12t + diag(ξ1d))−1mt∥∥∥∥2 )
(16)
The RHS in equation 16 above is a quadratic in ηt with two roots: 0 and 〈gt, ( V 1 2 t +diag(ξ1d) )−1 mt〉
L 2 ∥∥∥∥∥ ( V 1 2 t +diag(ξ1d) )−1 mt ∥∥∥∥∥ 2 .
So the quadratic’s minimum value is at the midpoint of this interval, which gives us a candidate tth−step length i.e α∗t := 12 · 〈gt, ( V 1 2 t +diag(ξ1d) )−1 mt〉
L 2 ∥∥∥∥∥ ( V 1 2 t +diag(ξ1d) )−1 mt ∥∥∥∥∥ 2 and the value of the quadratic at this point
is − 14 · (〈gt,
( V 1 2 t +diag(ξ1d) )−1 mt〉)2
L 2 ∥∥∥∥∥ ( V 1 2 t +diag(ξ1d) )−1 mt ∥∥∥∥∥ 2 . That is with step lengths being this α∗t we have the following
guarantee of decrease of function value between consecutive steps,
f(xt+1)− f(xt) ≤ − 1 2L · (〈gt,
( V 1 2 t + diag(ξ1d) )−1 mt〉)2∥∥∥∥(V 12t + diag(ξ1d))−1mt∥∥∥∥2
(17)
Now we separately lower bound the numerator and upper bound the denominator of the RHS above.

heading: Upperbound on
text: ∥∥∥∥(V 12t + diag(ξ1d))−1mt∥∥∥∥
We have, λmax (( V 1 2 t + diag(ξ1d) )−1) ≤ 1
ξ+mini=1..d √ (vt)i Further we note that the recursion of vt can be solved as, vt = (1 − β2) ∑t k=1 β t−k 2 g 2 k. Now we define, t := mink=1,..,t,i=1,..,d(g 2 k)i and this gives us,
λmax
(( V 1 2 t + diag(ξ1d) )−1) ≤ 1 ξ + √ (1− βt2) t
(18)
We solve the recursion for mt to get, mt = (1−β1) ∑t k=1 β t−k 1 gk. Then by triangle inequality and defining σt := maxi=1,..,t ‖∇f(xi)‖ we have, ‖mt‖ ≤ (1 − βt1)σt. Thus combining this estimate of ‖mt‖ with equation 18 we have,
∥∥∥∥(V 12t + diag(ξ1d))−1mt∥∥∥∥ ≤ (1− βt1)σtξ +√ t(1− βt2) ≤ (1− β t 1)σt ξ (19)
Lowerbound on 〈gt, ( V 1 2 t + diag(ξ1d) )−1 mt〉
To analyze this we define the following sequence of functions for each i = 0, 1, 2.., t
Qi = 〈gt, ( V 1 2 t + diag(ξ1d) )−1 mi〉
This gives us the following on substituting the update rule for mt,
Qi − β1Qi−1 = 〈gt, ( V 1 2 t + diag(ξ1d) )−1 (mi − β1mi−1)〉
= (1− β1)〈gt, ( V 1 2 t + diag(ξ1d) )−1 gi〉
At i = t we have,
Qt − β1Qt−1 ≥ (1− β1) ‖gt‖ 2 λmin
(( V 1 2 t + diag(ξ1d) )−1) Lets define, σt−1 := maxi=1,..,t−1 ‖∇f(xi)‖ and this gives us for i ∈ {1, .., t− 1},
Qi − β1Qi−1 ≥ −(1− β1) ‖gt‖σt−1λmax (( V 1 2 t + diag(ξ1d) )−1) We note the following identity,
Qt−βt1Q0 = (Qt−β1Qt−1)+β1(Qt−1−β1Qt−2)+β21(Qt−2−β1Qt−3)+ ..+βt−11 (Q1−β1Q0)
Now we use the lowerbounds proven on Qi − β1Qi−1 for i ∈ {1, .., t − 1} and Qt − β1Qt−1 to lowerbound the above sum as,
Qt − βt1Q0 ≥ (1− β1) ‖gt‖ 2 λmin
(( V 1 2 t + diag(ξ1d) )−1) − (1− β1) ‖gt‖σt−1λmax (( V 1 2 t + diag(ξ1d)
)−1) t−1∑ j=1 βj1
≥ (1− β1) ‖gt‖ 2 λmin
(( V 1 2 t + diag(ξ1d) )−1) − (β1 − βt1) ‖gt‖σt−1λmax (( V 1 2 t + diag(ξ1d) )−1) (20)
We can evaluate the following lowerbound, λmin (( V 1 2 t + diag(ξ1d) )−1) ≥ 1
ξ+ √ maxi=1,..,d(vt)i . Next we remember that the recursion of vt can be solved as, vt = (1 − β2) ∑t k=1 β t−k 2 g 2 k and we define, σt := maxi=1,..,t ‖∇f(xi)‖ to get,
λmin
(( V 1 2 t + diag(ξ1d) )−1) ≥ 1 ξ + √ (1− βt2)σ2t
(21)
Now we combine the above and equation 18 and the known value of Q0 = 0 (from definition and initial conditions) to get from the equation 20,
Qt ≥ −(β1 − βt1) ‖gt‖σt−1 1 ξ + √ (1− βt2) t
+ (1− β1) ‖gt‖ 2 1 ξ + √ (1− βt2)σ2t
≥ ‖gt‖ 2
( (1− β1)
ξ + σ √ (1− βt2) − (β1 − β t 1)σ ξ ‖gt‖
) (22)
In the above inequalities we have set t = 0 and we have set, σt = σt−1 = σ. Now we examine the following part of the lowerbound proven above,
(1− β1) ξ + √ (1− βt2)σ2 − (β1 − β t 1)σ ξ ‖gt‖ = ξ ‖gt‖ (1− β1)− σ(β1 − βt1)(ξ + σ
√ (1− βt2))
ξ ‖gt‖ (ξ + σ √ (1− βt2))
= σ(β1 − βt1) ξ ( ‖gt‖(1−β1) σ(β1−βt1) − 1 ) − σ √ (1− βt2)
ξ ‖gt‖ (ξ + σ √ (1− βt2))
= σ(β1 − βt1) ( ‖gt‖ (1− β1) σ(β1 − βt1) − 1 ) ξ −
( σ √
(1−βt2) −1+ (1−β1)‖gt‖
(β1−βt1)σ ) ξ ‖gt‖ (ξ + σ √ (1− βt2))
Now we remember the assumption that we are working under i.e ‖gt‖ > . Also by definition 0 < β1 < 1 and hence we have 0 < β1 − βt1 < β1. This implies,
(1−β1)‖gt‖ (β1−βt1)σ > (1−β1) β1σ > 1 where the last inequality follows because of our choice of as stated in the theorem statement. This allows us to define a constant, (1−β1)β1σ − 1 := θ1 > 0 s.t (1−β1)‖gt‖ (β1−βt1)σ − 1 > θ1
Similarly our definition of ξ allows us to define a constant θ2 > 0 to get, σ√(1− βt2) −1 + (1−β1)‖gt‖
(β1−βt1)σ
 < σ θ1 = ξ − θ2
Putting the above back into the lowerbound for Qt in equation 22 we have,
Qt ≥ ‖gt‖ 2 ( σ(β1 − β21)θ1θ2 ξσ(ξ + σ) ) (23)
Now we substitute the above and equation 19 into equation 17 to get,
f(xt+1)− f(xt) ≤ − 1 2L · (〈gt,
( V 1 2 t + diag(ξ1d) )−1 mt〉)2∥∥∥∥(V 12t + diag(ξ1d))−1mt∥∥∥∥2
≤ − 1 2L Q2t∥∥∥∥(V 12t + diag(ξ1d))−1mt∥∥∥∥2
≤ − 1 2L
‖gt‖ 4 ( (β1−β21)θ1θ2 ξ(ξ+σ) )2 (
(1−βt1)σ ξ )2 ≤ −‖gt‖ 4
2L
( (β1 − β21)2θ21θ22
(ξ + σ)2(1− βt1)2σ2
) (24)
=⇒ (
(β1 − β21)2θ21θ22 2L(ξ + σ)2(1− βt1)2σ2
) ‖∇f(xt)‖4 ≤ [f(xt)− f(xt+1)]
=⇒ T∑ t=2 ( (β1 − β21)2θ21θ22 2L(ξ + σ)2σ2 ) ‖∇f(xt)‖4 ≤ [f(x2)− f(xT+1)]
=⇒ min t=2,..,T
‖∇f(xt)‖4 ≤ 2L(ξ + σ)2σ2
T (β1 − β21)2θ21θ22 [f(x2)− f(x∗)]
Observe that if,
T ≥ 2Lσ 2(ξ + σ)2
2 4(β1 − β21)2θ21θ22 [f(x2)− f(x∗)]
then the RHS of the inequality above is less than or equal to 4 and this would contradict the assumption that ‖∇f(xt)‖ > for all t = 1, 2, . . .. As a consequence we have proven the first part of the theorem which guarantees the existence of positive step lengths, αt s.t ADAM finds an approximately critical point in finite time.
Now choose θ1 = 1 i.e 2 = β1σ 1−β1 i.e β1 = +2σ =⇒ β1(1− β1) = +2σ (1− +2σ ) = 2σ ( +2σ)2 . This also gives a easier-to-read condition on ξ in terms of these parameters i.e ξ > σ. Now choose ξ = 2σ i.e θ2 = σ and making these substitutions gives us,
T ≥ 18Lσ 4 2 4 (
2σ ( +2σ)
)2 σ2 [f(x2)− f(x∗)] ≥ 18L 8 6 (
1 +2σ )2 [f(x2)− f(x∗)] ≥ 9Lσ2 6 [f(x2)− f(x∗)] We substitute these choices in the step length found earlier to get,
α∗t = 1 L · 〈gt,
( V 1 2 t + diag(ξ1d) )−1 mt〉∥∥∥∥(V 12t + diag(ξ1d))−1mt∥∥∥∥2 = 1 L · Qt∥∥∥∥(V 12t + diag(ξ1d))−1mt∥∥∥∥2
≥ 1 L
‖gt‖ 2 ( σ2(β1−β21) ξσ(ξ+σ) ) (
(1−βt1)σ ξ )2 = ‖gt‖2L(1− βt1)2 4 3( + 2σ)2 := αt In the theorem statement we choose to call as the final αt the lowerbound proven above. We check below that this smaller value of αt still guarantees a decrease in the function value that is sufficient for the statement of the theorem to hold.
A consistency check! Let us substitute the above final value of the step length αt =
1 L
‖gt‖ 2
( σ2(β1−β 2 1)
ξσ(ξ+σ) ) (
(1−βt1)σ ξ
)2 = ξL(1−βt1)2 ‖gt‖2 ( (β1−β21) σ(ξ+σ) ) , the bound in equation 19 (with σt replaced by
σ), and the bound in equation 23 (at the chosen values of θ1 = 1 and θ2 = σ) in the original equation 17 to measure the decrease in the function value between consecutive steps,
f(xt+1)− f(xt) ≤ αt ( −〈gt, ( V 1 2 t + diag(ξ1d) )−1 mt〉+
Lαt 2 ∥∥∥∥(V 12t + diag(ξ1d))−1mt∥∥∥∥2 )
≤ αt ( −Qt +
Lαt 2 ∥∥∥∥(V 12t + diag(ξ1d))−1mt∥∥∥∥2 )
≤ ξ L(1− βt1)2 ‖gt‖ 2 ( (β1 − β21) σ(ξ + σ) )( −‖gt‖ 2 ( σ(β1 − β21)θ1θ2 ξσ(ξ + σ) )) + L
2
( ξ
L(1− βt1)2 ‖gt‖
2 ( (β1 − β21) σ(ξ + σ) ) (1− βt1)σ ξ )2 The RHS above can be simplified to be shown to be equal to the RHS in equation 24 at the same values of θ1 and θ2 as used above. And we remember that the bound on the running time was derived from this equation 24.

heading: B HYPERPARAMETER TUNING
text: Here we describe how we tune the hyper-parameters of each optimization algorithm. NAG has two hyper-parameters, the step size α and the momentum µ. The main hyper-parameters for RMSProp are the step size α, the decay parameter β2 and the perturbation ξ. ADAM, in addition to the ones in RMSProp, also has a momentum parameter β1. We vary the step-sizes of ADAM in the conventional way of αt = α √ 1− βt2/(1− βt1).
For tuning the step size, we follow the same method used in Wilson et al. (2017). We start out with a logarithmically-spaced grid of five step sizes. If the best performing parameter was at one of the extremes of the grid, we tried new grid points so that the best performing parameters were at one of the middle points in the grid. While it is computationally infeasible even with substantial resources to follow a similarly rigorous tuning process for all other hyper-parameters, we do tune over them somewhat as described below.
NAG The initial set of step sizes used for NAG were: {3e−3, 1e−3, 3e−4, 1e−4, 3e−5}. We tune the momentum parameter over values µ ∈ {0.9, 0.99}.
RMSProp The initial set of step sizes used were: {3e−4, 1e−4, 3e−5, 1e−5, 3e−6}. We tune over β2 ∈ {0.9, 0.99}. We set the perturbation value ξ = 10−10, following the default values in TensorFlow, except for the experiments in Section 5.1. In Section 5.1, we show the effect on convergence and generalization properties of ADAM and RMSProp when changing this parameter ξ.
Note that ADAM and RMSProp uses an accumulator for keeping track of decayed squared gradient vt. For ADAM this is recommended to be initialized at v0 = 0. However, we found in the TensorFlow implementation of RMSProp that it sets v0 = 1d. Instead of using this version of the algorithm, we used a modified version where we set v0 = 0. We typically found setting v0 = 0 to lead to faster convergence in our experiments.
ADAM The initial set of step sizes used were: {3e−4, 1e−4, 3e−5, 1e−5, 3e−6}. For ADAM, we tune over β1 values of {0.9, 0.99}. For ADAM, We set β2 = 0.999 for all our experiments as is set as the default in TensorFlow. Unless otherwise specified we use for the perturbation value ξ = 10−8 for ADAM, following the default values in TensorFlow.
Contrary to what is the often used values of β1 for ADAM (usually set to 0.9), we found that we often got better results on the autoencoder problem when setting β1 = 0.99.
C EFFECT OF THE ξ PARAMETER ON ADAPTIVE GRADIENT ALGORITHMS
In Figure 5, we show the same effect of changing ξ as in Section 5.1 on a 1 hidden layer network of 1000 nodes, while keeping all other hyper-parameters fixed (such as learning rate, β1, β2). These other hyper-parameter values were fixed at the best values of these parameters for the default values of ξ, i.e., ξ = 10−10 for RMSProp and ξ = 10−8 for ADAM.

heading: D ADDITIONAL EXPERIMENTS

heading: D.1 ADDITIONAL FULL-BATCH EXPERIMENTS ON 22× 22 SIZED IMAGES
text: In Figures 6, 7 and 8, we show training loss, test loss and gradient norm results for a variety of additional network architectures. Across almost all network architectures, our main results remain consistent. ADAM with β1 = 0.99 consistently reaches lower training loss values as well as better generalization than NAG.

heading: D.2 ARE THE FULL-BATCH RESULTS CONSISTENT ACROSS DIFFERENT INPUT DIMENSIONS?
text: To test whether our conclusions are consistent across different input dimensions, we do two experiments where we resize the 22× 22 MNIST image to 17× 17 and to 12× 12. Resizing is done using TensorFlow’s tf.image.resize images method, which uses bilinear interpolation.
D.2.1 INPUT IMAGES OF SIZE 17× 17
Figure 9 shows results on input images of size 17× 17 on a 3 layer network with 1000 hidden nodes in each layer. Our main results extend to this input dimension, where we see ADAM with β1 = 0.99 both converging the fastest as well as generalizing the best, while NAG does better than ADAM with β1 = 0.9.
D.2.2 INPUT IMAGES OF SIZE 12× 12
Figure 10 shows results on input images of size 12 × 12 on a 3 layer network with 1000 hidden nodes in each layer. Our main results extend to this input dimension as well. ADAM with β1 = 0.99 converges the fastest as well as generalizes the best, while NAG does better than ADAM with β1 = 0.9.

heading: D.3 ADDITIONAL MINI-BATCH EXPERIMENTS ON 22× 22 SIZED IMAGES
text: In Figure 11, we present results on additional neural net architectures on mini-batches of size 100 with an input dimension of 22 × 22. We see that most of our full-batch results extend to the minibatch case.
E IMAGE CLASSIFICATION ON CONVOLUTIONAL NEURAL NETS
To test whether these results might qualitatively hold for other datasets and models, we train an image classifier on CIFAR-10 (containing 10 classes) using VGG-like convolutional neural networks (Simonyan & Zisserman, 2014). In particular, we train VGG-9 on CIFAR-10, which contains 7 convolutional layers and 2 fully connected layers, a total of 9 layers. The convolutional layers contain 64, 64, 128, 128, 256, 256, 256 filters each of size 3 × 3, respectively. We use batch normalization (Ioffe & Szegedy, 2015) and ReLU activations after each convolutional layer, and the first fully connected layer. Table 1 contains more details of the VGG-9 architecture. We use minibatches of size 100, and weight decay of 10−5. We use fixed step sizes, and all hyperparameters were tuned as indicated in Section B.
We present results in Figure 12. As before, we see that this task is another example where tuning the momentum parameter (β1) of ADAM helps. While attaining approximately the same loss value, ADAM with β1 = 0.99 generalizes as good as NAG and better than when β1 = 0.9. Thus tuning β1 of ADAM helped in closing the generalization gap with NAG.

Review summaries:
This paper present a convergence analysis of the popular methods RMSProp and ADAM in the case of smooth non-convex functions. In particular it was shown that the above adaptive gradient algorithms are guaranteed to reach critical points for smooth non-convex objectives and bounds on the running time are provided. An empirical investigation is also presented with main focus on the comparison of the adaptive gradient methods and the Nesterov accelerated gradient algorithm (NAG).