Title: CONVERGENCE GUARANTEES FOR RMSPROP AND ADAM IN NON-CONVEX OPTIMIZATION AND AN EM-PIRICAL COMPARISON TO NESTEROV ACCELERATION

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.
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 (

1. INTRODUCTION:

Many optimization questions arising in machine learning can be cast as a finite sum optimization problem of the form: min x f (x) where f (x) = 1 k k i=1 f i (x). Most neural network problems also fall under a similar structure where each function f i is typically non-convex. A well-studied algorithm to solve such problems is Stochastic Gradient Descent (SGD), which uses updates of the form: x t+1 := x t -α∇ fit (x t ), where α is a step size, and fit is a function chosen randomly from {f 1 , f 2 , . . . , f k } at time t. Often in neural networks, "momentum" is added to the SGD update to yield a two-step update process given as: v t+1 = µv t -α∇ fit (x t ) followed by x t+1 = x t + v t+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 v t+1 = µv t -α∇ fit (x t + µv t ) followed by x t+1 = x t + v t+1 (see Algorithm 1 for more details).

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 & Richtá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) .

2. NOTATIONS AND PSEUDOCODES:

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 : R d → R is at least once differentiable then we call it L-smooth for some L > 0 if for all x, y ∈ R d the following inequality holds,

f (y) ≤ f (x) + ∇f (x), y -x + L 2 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 ∈ R d and V = diag(v) then we define, V -1 2 := i∈Support(v) 1 √ vi e i e T i ,

Initialize : v 1 = 0 4: for t = 1, 2, . . . do 5: v t+1 = µv t + ∇f (x t ) 6: x t+1 = x t -α(∇f (x t ) + µv t+1 ) 7: end for 8: end function RMSProp Algorithm Algorithm 2 RMSProp 1: Input : A constant vector R d ξ1 d ≥ 0, parameter β 2 ∈ [0, 1), step size α, initial starting point x 1 ∈ R d ,

Initialize : v 0 = 0 4: for t = 1, 2, . . . do 5: g t = ∇f (x t ) 6: v t = β 2 v t-1 + (1 -β 2 )(g 2 t + ξ1 d ) 7: V t = diag(v t ) 8: x t+1 = x t -αV -1 2 t g t 9:

end for 10: end function ) , a sequence of step sizes {α t } t=1,2.. , initial starting point x 1 ∈ R d , and we are given oracle access to the gradients of f : R d → R. 2: function ADAM(x 1 , β 1 , β 2 , α, ξ)

ADAM Algorithm Algorithm 3 ADAM 1: Input : A constant vector R d ξ1 d > 0, parameters β 1 , β 2 ∈ [0, 1

3::

Initialize : m 0 = 0, v 0 = 0 4: for t = 1, 2, . . . do 5:

g t = ∇f (x t ) 6: m t = β 1 m t-1 + (1 -β 1 )g t 7: v t = β 2 v t-1 + (1 -β 2 )g 2 t 8: V t = diag(v t ) 9: x t+1 = x t -α t V 1 2 t + diag(ξ1 d ) -1 m t 10:

end for 11: end function

3. CONVERGENCE GUARANTEES FOR ADAM AND RMSPROP:

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 :

R d → {-1, 1} d s.t it maps v → (1 if v i ≥ 0 else -1) i=1,...,d .

Theorem 3.1. Stochastic RMSProp converges to criticality (Proof in subsection A.1) Let f : R d → R be L-smooth and be of the form f = 1 k k i=1 f i s.t. (a) each f i is at least once differentiable, (b) the gradients are s.t ∀x ∈ R d , ∀p, q ∈ {1, . . . , k}, sign(∇f p (x)) = sign(∇f q (x)) , (c) σ f < ∞ is an upperbound on the norm of the gradients of f i and (d) f has a minimizer, i.e., there exists x * such that f (x * ) = min x∈R d f (x). Let the gradient oracle be s.t when invoked at some x t ∈ R d it uniformly at random picks i t ∼ {1, 2, .., k} and returns, ∇f it (x t ) = g t . Then corresponding to any , ξ > 0 and a starting point x 1 for Algorithm 2, we can define,

T ≤ 1 4 2Lσ 2 f (σ 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 * )) σ 2 f L

will find an -critical point in at most T steps in the sense that, min t=1,2...,T E[ ∇f

(x t ) 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 {f i } i=1,...,k only holds on the points in R d 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 R d 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 : R d → 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 * ) = min x∈R d 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 (x t ) ≤ for some t ≤ 1 2 × 2L(σ 2 +ξ)(f (x1)-f (x * )) (1-β2)ξ

, where x 1 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 : R d → 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 * ) = min x∈R d f (x), and the function f be bounded from above and below by constants B and B u as B l ≤ f (x) ≤ B u for all x ∈ R d . 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 (x t ) ≤ .

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 : R d → 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 * ) = min x∈R d 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 (x t ) ≤ for some t ≤ T .

In particular if one sets β 1 = +2σ , ξ = 2σ, and α t =

EQUATION

3( +2σ) 2 where g t is the gradient of the objective at the t th iterate, then T can be taken to be

9Lσ 2 6 [f (x 2 ) -f (x * )]

, where x 2 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 -β t 2 /(1 -β t 1 ). In the above theorem, we note that the 1/(1 -β t 1 ) term of this "bias correction term" naturally comes out from theory! 4 EXPERIMENTAL SETUP 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 VGG-9, a convolutional neural network. Let z ∈ R d be the input vector to the autoencoder, {W i } i=1,.., denote the weight matrices of the net and {b i } i=1,..,2 be the bias vectors. Then the output ẑ ∈ R d of the autoencoder is defined as

ẑ = W 1 σ(. . . σ(W -1 σ(W a + b +1 ) + b +2 ) . . . ) + b 2 where a = σ(W σ(. . . σ(W 2 σ(W 1 z + b 1 ) + b 2 ) . . . ) + 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(W 1 ) ... 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 -ẑ 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: W 1 ∈ R h×d , W i ∈ R h×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/(fan in + fan out ), where fan in denotes the number of input units in the weight matrix, and fan out 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 10 5 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 10 5 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 mini-MNIST 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.

5. EXPERIMENTAL RESULTS:



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 10 5 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. 

5.3. COMPARING PERFORMANCE IN THE FULL-BATCH SETTING:

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 . 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.

6. CONCLUSION:

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.

(g 2 k + ξ). This lets us write the following bounds,

λ min (V -1 2 t ) ≥ 1 max i=1,..,d (v t ) i ≥ 1 max i=1,..,d ((1 -β 2 ) t k=1 β t-k 2 (g 2 k + ξ1 d ) i ) ≥ 1 1 -β t 2 σ 2 t + ξ

Now we define, t := min k=1,..,t,i=1,..,d (∇f i k (x k )) 2 i and this lets us get the following bounds,

λ max (V -1 2 t ) ≤ 1 min i=1,..,d ( (v t ) i ) ≤ 1 (1 -β t 2 ) (ξ + t )

Now we invoke the bounded gradient assumption about the f i 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 -1 2 t ) ≥ 1 σ 2 f + ξ := µ min λ max (V -1 2 t ) ≤ 1 (1 -β 2 ) √ ξ := µ max

Using the L-smoothness of f between consecutive iterates x t and x t+1 we have,

f (x t+1 ) ≤ f (x t ) + ∇f (x t ), x t+1 -x t + L 2 x t+1 -x t 2

We note that the update step of stochastic RMSProp is x t+1 = x t -α(V t ) -1 2 g t where g t is the stochastic gradient at iterate x t . Let H t = {x 1 , x 2 , .., x t } 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[g t ] = ∇f (x t ) and E[ g t 2 ] ≤ σ 2 f . Now we can invoke these stochastic oracle's properties and take a conditional (on H t ) expectation over g t of the L-smoothness in equation to get,

E[f (x t+1 ) | H t ] ≤ f (x t ) -αE ∇f (x t ), (V t ) -1 2 g t | H t + α 2 L 2 E (V t ) -1 2 g t 2 | H t ≤ f (x t ) -αE ∇f (x t ), (V t ) -1 2 g t | H t + µ 2 max α 2 L 2 E g t 2 | H t ≤ f (x t ) -αE ∇f (x t ), (V t ) -1 2 g t | H t + µ 2 max α 2 σ 2 f L 2 (1)

We now separately analyze the middle term in the RHS above in Lemma A.1 below and we get,

E[ ∇f (x t ), (V t ) -1 2 g t | H t ] ≥ µ min ∇f (x t ) 2

We substitute the above into equation 1 and take expectations over H t to get,

E[f (x t+1 ) -f (x t )] ≤ -αµ min ∇f (x t ) 2 + µ 2 max α 2 σ 2 f L 2 =⇒ E[ ∇f (x t ) 2 ] ≤ 1 αµ min E[f (x t ) -f (x t+1 )] + ασ 2 f L 2 µ 2 max µ 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 (x t ) 2 ] ≤ 1 αT µ min E[f (x 1 ) -f (x T +1 )] + ασ 2 f L 2 µ 2 max µ min ≤ 1 αT µ min (f (x 1 ) -f (x * )) + ασ 2 f L 2 µ 2 max µ min

Replacing into the RHS above the optimal choice of,

α = 1 √ T 2 (f (x 1 ) -f (x * )) σ 2 f Lµ 2 max = 1 √ T 2ξ(1 -β 2 ) (f (x 1 ) -f (x * )) σ 2 f L we get, min t=1...T E[ ∇f (x t ) 2 ] ≤ 2 1 T µ min (f (x 1 ) -f (x * )) × Lσ 2 f 2 µ 2 max µ min = 1 √ T 2Lσ 2 f (σ 2 f + ξ) (f (x 1 ) -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σ 2 f (σ 2 f +ξ)(f (x1)-f (x * )) (1-β2)ξ

Lemma A.1. At any time t, the following holds,

EQUATION

Now we introduce some new variables to make the analysis easier to present. Let a pi := [∇f p (x t )] i where p indexes the training data set, p ∈ {1, . . . , k}. (conditioned on H t , a pi s are constants) This implies,

∇ i f (x t ) = 1 k k p=1 a pi We recall that E [(g t ) i ] = ∇ i f (x t )

where the expectation is taken over the oracle call at the t th update step. Further our instantiation of the oracle is equivalent to doing the uniformly at random sampling, (g t ) i ∼ {a pi } p=1,...,k .

Given that we have,

V t = diag(v t ) with v t = (1 -β 2 ) t k=1 β t-k 2 (g 2 k + ξ1 d ) this im- plies, (V -1/2 t ) ii = 1 √ (1-β2)(g t ) 2 i +di

where we have defined

d i := (1 -β 2 )ξ + (1 - β 2 ) t-1 k=1 β t-k 2 ((g k ) 2 i + ξ).

(conditioned on H t , d i is a constant) This leads to an explicit form of the needed expectation over the t th -oracle call as,

E (V -1/2 t ) ii (g t ) i | H t = E (V -1/2 t ) ii (g t ) i | H t = E (g t )i∼{api} p=1,...,k (g t ) i (1 -β 2 )(g t ) 2 i + d i | H t = 1 k k p=1 a pi (1 -β 2 )a 2 pi + d i

Substituting the above (and the definition of the constants a pi ) back into equation 3 we have,

E ∇f (x t ), V -1/2 t g t | H t = d i=1 1 k k p=1 a pi   1 k k p=1 a pi (1 -β 2 )a 2 pi + d i   We define two vectors a i , h i ∈ R k s.t (a i ) p = a pi and (h i ) p = 1 √ (1-β2)a 2 pi +di

Substituting this, the above expression can be written as,

EQUATION

Note that with this substitution, the RHS of the claimed lemma becomes,

µ min ∇f (x t ) 2 = µ min d i=1 1 k k p=1 ∇ p f (x t ) 2 = µ min k 2 d i=1 (a i 1 k ) 2 = µ min k 2 d i=1 a i 1 k 1 k a i Therefore our claim is proved if we show that for all i, 1 k 2 a i 1 k h i a i -µmin k 2 a i 1 k 1 k a i ≥ 0.

This can be simplified as,

1 k 2 a i 1 k h i a i -µ min 1 k 2 a i 1 k 1 k a i = 1 k 2 a i 1 k (h i -µ min 1 k ) a i

To further simplify, we define

q i ∈ R k , (q i ) p = (h i ) p -µ min = 1 √ (1-β2)a 2 pi +di

-µ min . We therefore need to show,

1 k 2 a i 1 k q i a i ≥ 0

We first bound d i by recalling the definition of σ f (from which it follows that a 2 pi ≤ σ 2 f ),

d i ≤ (1 -β 2 ) ξ + t-1 k=1 β t-k 2 (σ 2 f + ξ) = (1 -β 2 ) ξ + β 2 -β t-1 2 1 -β 2 (σ 2 f + ξ) ≤ (1 -β 2 )ξ + (β 2 -β t-1 2 )ξ + (β 2 -β t-1 2 )σ 2 f = (1 -β t-1 2 )ξ + (β 2 -β t-1 2 )σ 2 f =⇒ (1 -β 2 )a 2 pi + d i ≤ (1 -β 2 )σ 2 f + (1 -β t-1 2 )ξ + (β 2 -β t-1 2 )σ 2 f = (1 -β t-1 2 )(σ 2 f + ξ) =⇒ -µ min + 1 (1 -β 2 )a 2 pi + d i ≥ -µ min + 1 (1 -β t-1 2 )(σ 2 f + ξ) = - 1 σ 2 f + ξ + 1 (1 -β t-1 2 )(σ 2 f + ξ) =⇒ -µ min + 1 (1 -β 2 )a 2 pi + d i ≥ 0 (5)

The inequality follows since

β 2 ∈ (0, 1]

Putting this all together, we get,

(a i 1 k )(q i a i ) = k p=1 a pi   k p=1   -µ min a pi + a pi (1 -β 2 )a 2 pi + d i     = k p,q=1   -µ min a pi a qi + a pi a qi (1 -β 2 )a 2 pi + d i   = k p,q=1 a pi a qi   -µ min + 1 (1 -β 2 )a 2 pi + d i  

Now our assumption that for all x, sign(∇f p (x)) = sign(∇f q (x)) for all p, q ∈ {1, . . . , k} leads to the conclusion that the term a pi a qi ≥ 0. And we had already shown in equation 5 that

-µ min + 1 √ (1-β2)a 2 pi +di

≥ 0. Thus we have shown that (a i 1 k )(q i a i ) ≥ 0 and this finishes the proof.

A.2 PROVING DETERMINISTIC RMSPROP -THE VERSION WITH STANDARD SPEED (PROOF OF THEOREM 3.2)

Proof. By the L-smoothness condition and the update rule in Algorithm 2 we have,

f (x t+1 ) ≤ f (x t ) -α t ∇f (x t ), V -1 2 t ∇f (x t ) + α 2 t L 2 V -1 2 t ∇f (x t ) 2 =⇒ f (x t+1 ) -f (x t ) ≤ α t Lα t 2 V -1 2 t ∇f (x t ) 2 -∇f (x t ), V -1 2 t ∇f (x t ) (6) For 0 < δ 2 t < 1 √ 1-β t 2 √ σ 2 t +ξ

we now show a strictly positive lowerbound on the following function,

2 L ∇f (x t ), V -1 2 t ∇f (x t ) -δ 2 t ∇f (x t ) 2 V -1 2 t ∇f (x t ) 2 (7)

We define σ t := max i=1,..,t ∇f (x i ) and we solve the recursion for v t as,

v t = (1 - β 2 ) t k=1 β t-k 2 (g 2 k + ξ)

. This lets us write the following bounds,

EQUATION

Now we define, t := min k=1,..,t,i=1,..,d (∇f (x k )) 2 i and this lets us get the following sequence of inequalities,

EQUATION

So combining equations 9 and 8 into equation 7 and from the exit line in the loop we are assured that ∇f (x t ) 2 = 0 and combining these we have,

2 L -δ 2 t ∇f (x t ) 2 + ∇f (x t ), V -1 2 t ∇f (x t ) V -1 2 t ∇f (x t ) 2 ≥ 2 L   -δ 2 t + 1 √ 1-β t 2 √ σ 2 t +ξ 1 (1-β t 2 )(ξ+ t)   ≥ 2(1 -β t 2 )(ξ + t ) L -δ 2 t + 1 1 -β t 2 σ 2 t + ξ

Now our definition of δ 2 t allows us to define a parameter 0 < β t :=

1 √ 1-β t 2 √ σ 2 t +ξ

-δ 2 t and rewrite the above equation as,

2 L -δ 2 t ∇f (x t ) 2 + ∇f (x t ), V -1 2 t ∇f (x t ) V -1 2 t ∇f (x t ) 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,

δ 2 t = 1 2 min t=1,... 1 1 -β t 2 σ 2 t + ξ = 1 2 1 σ 2 + ξ =: δ 2 and β t = min t=1,.. 1 1 -β t 2 σ 2 t + ξ -δ 2 = 1 2 1 σ 2 + ξ

Then the worst-case lowerbound in equation 10 becomes,

2 L -δ 2 t ∇f (x t ) 2 + ∇f (x t ), V -1 2 t ∇f (x t ) V -1 2 t ∇f (x t ) 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 -1 2 t ∇f (x t ) 2 - ∇f (x t ), V -1 2 t ∇f (x t ) ≤ -δ 2 ∇f (x t )

2 . This when substituted back into equation 6 we have,

EQUATION

EQUATION

Thus for any given > 0, T satisfying, 1 T δ 2 α [f (x 1 ) -f (x * )] ≤ 2 is a sufficient condition to ensure that the algorithm finds a point x result := arg min t=1,,.T ∇f (x t )

2 with ∇f (x result ) 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.

A.3 PROVING DETERMINISTIC RMSPROP -THE VERSION WITH NO ADDED SHIFT (PROOF OF THEOREM 3.3)

Proof. From the L-smoothness condition on f we have between consecutive iterates of the above algorithm,

EQUATION

Now the recursion for v t can be solved to get,

v t = (1 -β 2 ) t k=1 β t-k 2 g 2 k . Then V 1 2 t ≥ 1 max i∈Support(v t ) √ (vt)i = 1 max i∈Support(v t ) √ (1-β2) t k=1 β t-k 2 (g 2 k )i = 1 max i∈Support(v t ) σ √ (1-β2) t k=1 β t-k 2 = 1 σ √ (1-β t 2 )

. Substituting this in a lowerbound on the LHS of equation 13 we get,

1 σ (1 -β t 2 ) ∇f (x t ) 2 ≤ ∇f (x t ), V -1 2 t ∇f (x t ) ≤ 1 α t (f (x t ) -f (x t+1 ))+ Lα t 2 V -1 2 t ∇f (x t ) 2

Summing the above we get,

EQUATION

Now we substitute α t = α √ t and invoke the definition of B and B u to write the first term on the RHS of equation 15 as,

T t=1 1 α t [f (x t ) -f (x t+1 )] = f (x 1 ) α + T t=1 f (x t+1 ) α t+1 - f (x t+1 ) α t - f (x T +1 ) α T +1 = f (x 1 ) α - f (x T +1 ) α T +1 + 1 α T t=1 f (x t+1 )( √ t + 1 - √ t) ≤ B u α - B √ T + 1 α + B u α ( √ 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 -1 2 t

∇f (x t ) 2 and that gives us,

P (T ) -P (T -1) = α T d i=1 g 2 T,i v T,i = α T d i=1 g 2 T,i (1 -β 2 ) T k=1 β T -k 2 g 2 k,i = α T (1 -β 2 ) d i=1 g 2 T,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 -β T 2 < 1 from the numerator, we can define a point x result as follows,

∇f (x result ) 2 := arg min t=1,..,T ∇f (x t ) 2 ≤ 1 T T t=1 ∇f (x t ) 2 ≤ σ T B u α - B l √ T + 1 α + B u α ( √ 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

x result such that, ∇f (x result ) 2 ≤ 2

A.4 PROVING ADAM (PROOF OF THEOREM 3.4)

Proof.

Let us assume to the contrary that g t > 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 (x t+1 ) ≤ f (x t ) + ∇f (x t ), x t+1 -x t + L 2 x t+1 -x t 2

Substituting the update rule using a dummy step length η t > 0 we have,

EQUATION

The RHS in equation 16 above is a quadratic in η t with two roots: 0 and

g t , V 1 2 t +diag(ξ1 d ) -1 mt L 2 V 1 2 t +diag(ξ1 d ) -1 mt 2 .

So the quadratic's minimum value is at the midpoint of this interval, which gives us a candidate

t th -step length i.e α * t := 1 2 • g t , V 1 2 t +diag(ξ1 d ) -1 mt L 2 V 1 2 t +diag(ξ1 d ) -1

mt 2 and the value of the quadratic at this point

is -1 4 • ( g t , V 1 2 t +diag(ξ1 d ) -1 mt ) 2 L 2 V 1 2 t +diag(ξ1 d ) -1 mt 2 .

That is with step lengths being this α * t we have the following guarantee of decrease of function value between consecutive steps,

EQUATION

Now we separately lower bound the numerator and upper bound the denominator of the RHS above.

Upperbound on V 1 2 t + diag(ξ1 d ) -1 m t We have, λ max V 1 2 t + diag(ξ1 d ) -1 ≤ 1 ξ+min i=1..d √ (vt)i

Further we note that the recursion of v t can be solved as,

v t = (1 -β 2 ) t k=1 β t-k 2 g 2

k . Now we define, t := min k=1,..,t,i=1,..,d (g 2 k ) i and this gives us,

EQUATION

We solve the recursion for m t to get,

m t = (1 -β 1 ) t k=1 β t-k 1 g k .

Then by triangle inequality and defining σ t := max i=1,..,t ∇f (x i ) we have, m t ≤ (1 -β t 1 )σ t . Thus combining this estimate of m t with equation 18 we have,

V 1 2 t + diag(ξ1 d ) -1 m t ≤ (1 -β t 1 )σ t ξ + t (1 -β t 2 ) ≤ (1 -β t 1 )σ t ξ (19) Lowerbound on g t , V 1 2 t + diag(ξ1 d )

-1 m t To analyze this we define the following sequence of functions for each i = 0, 1, 2.., t

Q i = g t , V 1 2 t + diag(ξ1 d ) -1 m i

This gives us the following on substituting the update rule for m t ,

Q i -β 1 Q i-1 = g t , V 1 2 t + diag(ξ1 d ) -1 (m i -β 1 m i-1 ) = (1 -β 1 ) g t , V 1 2 t + diag(ξ1 d ) -1 g i At i = t we have, Q t -β 1 Q t-1 ≥ (1 -β 1 ) g t 2 λ min V 1 2 t + diag(ξ1 d ) -1

Lets define, σ t-1 := max i=1,..,t-1 ∇f (x i ) and this gives us for i ∈ {1, .., t -1},

Q i -β 1 Q i-1 ≥ -(1 -β 1 ) g t σ t-1 λ max V 1 2 t + diag(ξ1 d ) -1

We note the following identity,

Q t -β t 1 Q 0 = (Q t -β 1 Q t-1 )+β 1 (Q t-1 -β 1 Q t-2 )+β 2 1 (Q t-2 -β 1 Q t-3 )+..+β t-1 1 (Q 1 -β 1 Q 0 )

Now we use the lowerbounds proven on Q i -β 1 Q i-1 for i ∈ {1, .., t -1} and Q t -β 1 Q t-1 to lowerbound the above sum as,

EQUATION

We can evaluate the following lowerbound,

λ min V 1 2 t + diag(ξ1 d ) -1 ≥ 1 ξ+ √ max i=1,..,d (vt)i .

Next we remember that the recursion of v t can be solved as,

v t = (1 -β 2 ) t k=1 β t-k 2 g 2

k and we define, σ t := max i=1,..,t ∇f (x i ) to get,

EQUATION

)

Now we combine the above and equation 18 and the known value of Q 0 = 0 (from definition and initial conditions) to get from the equation 20,

EQUATION

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 -β t 2 )σ 2 - (β 1 -β t 1 )σ ξ g t = ξ g t (1 -β 1 ) -σ(β 1 -β t 1 )(ξ + σ (1 -β t 2 )) ξ g t (ξ + σ (1 -β t 2 )) = σ(β 1 -β t 1 ) ξ g t (1-β1) σ(β1-β t 1 ) -1 -σ (1 -β t 2 ) ξ g t (ξ + σ (1 -β t 2 )) = σ(β 1 -β t 1 ) g t (1 -β 1 ) σ(β 1 -β t 1 ) -1 ξ - σ √ (1-β t 2 ) -1+ (1-β 1 ) g t (β 1 -β t 1 )σ ξ g t (ξ + σ (1 -β t 2 ))

Now we remember the assumption that we are working under i.e g t > . Also by definition 0 < β 1 < 1 and hence we have

0 < β 1 -β t 1 < β 1 . This implies, (1-β1) g t (β1-β t 1 )σ > (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) g t (β1-β t 1 )σ -1 > θ 1

Similarly our definition of ξ allows us to define a constant θ 2 > 0 to get,

  σ (1 -β t 2 ) -1 + (1-β1) g t (β1-β t 1 )σ   < σ θ 1 = ξ -θ 2

Putting the above back into the lowerbound for Q t in equation 22 we have,

EQUATION

Now we substitute the above and equation 19 into equation 17 to get,

f (x t+1 ) -f (x t ) ≤ - 1 2L • ( g t , V 1 2 t + diag(ξ1 d ) -1 m t ) 2 V 1 2 t + diag(ξ1 d ) -1 m t 2 ≤ - 1 2L Q 2 t V 1 2 t + diag(ξ1 d ) -1 m t 2 ≤ - 1 2L g t 4 (β1-β 2 1 )θ1θ2 ξ(ξ+σ) 2 (1-β t 1 )σ ξ 2 ≤ - g t 4 2L (β 1 -β 2 1 ) 2 θ 2 1 θ 2 2 (ξ + σ) 2 (1 -β t 1 ) 2 σ 2 (24) =⇒ (β 1 -β 2 1 ) 2 θ 2 1 θ 2 2 2L(ξ + σ) 2 (1 -β t 1 ) 2 σ 2 ∇f (x t ) 4 ≤ [f (x t ) -f (x t+1 )] =⇒ T t=2 (β 1 -β 2 1 ) 2 θ 2 1 θ 2 2 2L(ξ + σ) 2 σ 2 ∇f (x t ) 4 ≤ [f (x 2 ) -f (x T +1 )] =⇒ min t=2,..,T ∇f (x t ) 4 ≤ 2L(ξ + σ) 2 σ 2 T (β 1 -β 2 1 ) 2 θ 2 1 θ 2 2 [f (x 2 ) -f (x * )] Observe that if, T ≥ 2Lσ 2 (ξ + σ) 2 2 4 (β 1 -β 2 1 ) 2 θ 2 1 θ 2 2 [f (x 2 ) -f (x * )]

then the RHS of the inequality above is less than or equal to 4 and this would contradict the assumption that ∇f (x t ) > 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 θ:

EQUATION

+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 (x 2 ) -f (x * )] ≥ 18L 8 6 1 +2σ 2 [f (x 2 ) -f (x * )] ≥ 9Lσ 2 6 [f (x 2 ) -f (x * )]

We substitute these choices in the step length found earlier to get,

α * t = 1 L • g t , V 1 2 t + diag(ξ1 d ) -1 m t V 1 2 t + diag(ξ1 d ) -1 m t 2 = 1 L • Q t V 1 2 t + diag(ξ1 d ) -1 m t 2 ≥ 1 L g t 2 σ 2 (β1-β 2 1 ) ξσ(ξ+σ) (1-β t 1 )σ ξ 2 = g t 2 L(1 -β t 1 ) 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 g t 2 σ 2 (β 1 -β 2 1 ) ξσ(ξ+σ) (1-β t 1 )σ ξ 2 = ξ L(1-β t 1 ) 2 g t 2 (β1-β 2 1 )

σ(ξ+σ) , 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 (x t+1 ) -f (x t ) ≤ α t -g t , V 1 2 t + diag(ξ1 d ) -1 m t + Lα t 2 V 1 2 t + diag(ξ1 d ) -1 m t 2 ≤ α t -Q t + Lα t 2 V 1 2 t + diag(ξ1 d ) -1 m t 2 ≤ ξ L(1 -β t 1 ) 2 g t 2 (β 1 -β 2 1 ) σ(ξ + σ) -g t 2 σ(β 1 -β 2 1 )θ 1 θ 2 ξσ(ξ + σ) + L 2 ξ L(1 -β t 1 ) 2 g t 2 (β 1 -β 2 1 ) σ(ξ + σ) (1 -β t 1 )σ ξ 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.

B HYPERPARAMETER TUNING:

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 -β t 2 /(1 -β t 1 ). 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 v t . For ADAM this is recommended to be initialized at v 0 = 0. However, we found in the TensorFlow implementation of RMSProp that it sets v 0 = 1 d . Instead of using this version of the algorithm, we used a modified version where we set v 0 = 0. We typically found setting v 0 = 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. 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. 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. 

:



Figures and Tables:

where {e i } {i=1,...,d} is the standard basis of R d Now we list out the pseudocodes used for NAG, RMSProp and ADAM in theory and experiments, Nesterov's Accelerated Gradient (NAG) Algorithm Algorithm 1 NAG 1: Input : A step size α, momentum µ ∈ [0, 1), and an initial starting point x 1 ∈ R d , and we are given query access to a (possibly noisy) oracle for gradients of f : R d → R. 2: function NAG(x 1 , α, µ) 3:

Figure 1: Optimally tuned parameters for different ξ values. 1 hidden layer network of 1000 nodes; Left: Loss on training set; Middle: Loss on test set; Right: Gradient norm on training set

Figure 2: Tracking the smallest eigenvalue of the Hessian on a 1 hidden layer network of size 300. Left: Minimum Hessian eigenvalue. Right: Gradient norm on training set.

Figure 3: Full-batch experiments on a 3 hidden layer network with 1000 nodes in each layer; Left: Loss on training set; Middle: Loss on test set; Right: Gradient norm on training set

Figure 5: Fixed parameters with changing ξ values. 1 hidden layer network of 1000 nodes

Figure 6: Loss on training set; Input image size 22 × 22

Figure 7: Loss on test set; Input image size 22 × 22

Figure 9: Full-batch experiments with input image size 17 × 17

Figure 10: Full-batch experiments with input image size 12 × 12

and we are given query access to a (possibly noisy) oracle for gradients of f : R d → R. 2: function RMSPR O P(x 1 , β 2 , α, ξ)

Table content: <table><tr><td>3:</td></tr></table>

Peer review (iclr2019):
 There may exist an error on the proof of Theorem 3.1 in appendix. For the first equation in page 13, the authors want to estimate lower-bound of the term . The second inequality may be wrong. Please check it carefully. (Hints: both the index sets { i | .nabla{f}(xt))_{i}*gt_{i} <0 } and { i | .nabla{f}(xt))_{i}*gt_{i} >0 } depend on the random variable . Hence, the expectation and summation cannot be exchanged in the second inequality.)