Adaptive Gradient Methods Can Be Provably Faster than SGD with Random Shuffling
Authors: Xunpeng Huang
Vicky Jiaqi Zhang
Hao Zhou
Lei Li
Venue:  (2021)

Abstract: Adaptive gradient methods have been shown to outperform SGD in many tasks of training neural networks. However, the acceleration effect is yet to be explained in the non-convex setting since the best convergence rate of adaptive gradient methods is worse than that of SGD in literature. In this paper, we prove that adaptive gradient methods exhibit an $\small\tilde{O}(T^{-1/2})$-convergence rate for finding first-order stationary points under the strong growth condition, which improves previous best convergence results of adaptive gradient methods and random shuffling SGD by factors of $\small O(T^{-1/4})$ and $\small O(T^{-1/6})$, respectively. In particular, we study two variants of AdaGrad with random shuffling for finite sum minimization. Our analysis suggests that the combination of random shuffling and adaptive learning rates gives rise to better convergence.

Under review as a conference paper at ICLR 2021
ADAPTIVE GRADIENT METHODS CAN BE PROVABLY FASTER THAN SGD WITH RANDOM SHUFFLING
Anonymous authors Paper under double-blind review
ABSTRACT
Adaptive gradient methods have been shown to outperform SGD in many tasks training neural networks. However, the acceleration effect is yet to be explained in the non-convex setting since the best convergence rate adaptive gradient methods is worse than that of SGD in literature. In this paper, prove that adaptive gradient methods exhibit order stationary points under the strong growth condition, which improves previous best convergence results of adaptive gradient methods and random shuffling SGD by factors of O(4-1/4) and D(T)1/6)) respectively. In particular, variants of AdaGrad with random shuffling for finite sum minimization. Our analysis suggests that the combination of random shuffling and adaptive learning rates gives rise to better convergence.
rate for finding first-
study two
INTRODUCTION
We consider the finite sum minimization problem in stochastic optimization:
min #ER
f(x) = n f((x),
where f the objective function and its component functions fi : Rd + are smooth and possibly non-convex. This formulation has been used extensively in training neural networks today, Stochastic gradient descend (SGD) and its variants have shown to be quite effective for solving this problem, whereas recent works demonstrate another prominent line of gradient-basee algorithms by
introducing adaptive step sizes to automatically adjust the learning rate (Duchi et al. 201 Tieleman
& Hinton 2012
Kingma & Ba 2014).
Despite the superior performance of adaptive gradient methods in many tasks (Devlin et al. 2019 Vaswani et al. 2017). their theoretical convergence remains the same
worse for non-convex objectives, compared to SGD. In general non-convex settings, it is often impractical to discuss optimal solutions. Therefore, the attention of analysis turns stationary points instead. Many works have
been proposed to study first-order (Chen et al. 2019 Zhou et al. 2018 Zaheer et al. 2018 Ward al. 2018 Zhou al., 2018) and second-order (Allen Zhu 2018 Staib et al.) 2019) stationary points. Table summarized some previous best-known results for finding first-order stationary points.
One might notice that the best dependence on the total iteration number of adaptive gradient methods matches that of vanilla SGD. In addition, with the introduction of incremental sampling techniques, an even better convergence SGD can be obtained (Haochen Sra 2019 Nguyen et al. 2020).
This gap between theory and practice of adaptive gradient methods has been an open problem that we aim to solve in this paper. Motivated by the analysis of sampling techniques, rigorously prove that adaptive gradient methods exhibit a faster non-asymptotic convergence rate that matches the best result on SGD. In particular, make the following contributions:
Our main contribution (Theorem 32 is to prove that two variants of AdaGrad can find (TT-1/2) -aap///i-ppooxiaateee first-order stationary points under the strong growth condition assumption (Schmidt Roux 2013). This improves previous best convergence results of adaptive gradient methods and shuffling SGD by factors of O(T-1/1) and O

---

Under review as a conference paper at ICLR 2021
Table I: Convergence rate comparisons for the non-convex optimization problem. First two categories, "SGD' and Adaptive Gradient Methods' are based on the expectation minimization problem, whereas the last category is based on the finile sum minimization problem.
Algorithm
Assumptions (L-smooth+)
T
SGD
vanilla SGD
a² hounded gradient variance
((T-1/))
Constant step-size size SGD
(
strong growth condition
Vaswani 2019
AMSGrad, AdaFom
bounded gradients
0 (
Adaptive Gradient Methods
Chen et al
2019
initial gradient lower bound
AMSGGadd Padam
bounded gradients
0 (T-1//))
Zhou et al.
2018
gradient sparsity
RMSProp. Yogi
bounded gradients
0 O +111/00)) +o)
7aheer et al
2018
o² bounded gradient variance
AdaGrad-No NORMM
bounded gradients
((-11/4)
(Ward et al.
2018
a² hounded gradient variance
GGT
o² bounded gradient variance
(T--1/4)
(Agarwal et al.
2019
Shuffing
Nguuyen et al. 2020
Random Shuftlngg SGD
bounded gradients
Ô n (55.1113)
Ours
bounded gradients
Ô ( TT1//)
strong growth condition
T denotes the number of iterations; n is the number of samples in the finite sum minimization problem.
respectively. As a result, this bridges the gap between analysis and practice of adaptive gradient methods by proving that adaptive gradient methods can be faster than SGD with random shuffling in theory.
We study the strong growth condition under which our convergence rate is derived. This condition has been previous used study SGD in the expectation minimization setting (Schmidt & Roux 2013 Vaswani et al. 2019). We prove that this condition is satisfied by general types of models under some additional assumptions.
We conduct preliminary experiments to demonstrate the combined acceleration effect of random shuffling and adaptive learning rates.
Our analysis points out two key components that lead to better convergence results of adaptive gradient methods: the epoch-wiss wise analysis of random shuffling can incorporate the benefit of full gradients; the adaptive learning rates along with the strong growth condition provide better improvement of objective value in consecutive epochs.
Expectation Minimization The comparison in Table D shows the convergence rates in the non-convex setting with respect to first-order stationary points. The results the first two categories apply the general expectation minimization problem with f(x) = E=f(xx . z). Whereas the convergences for expectation minimization naturally transform to finite sum minimization, the statements remain asymptotic, meaning E//V (a))] O(T)), where the expectation is taken to compensate the stochastic gradients. Many efforts have been made to reduce variance finite sum minimization (Johnson Zhang. 2013 Reddi et al. 2016,) Haochen & Sra 2019). In particular, non-asymptotic results can be gained using random shufiling, under which the dependency on sample size n seems to be unavoidable (Haochen Sral 2019).
Finite Sum Mininization
2 PRELIMINARIES
A typical setting of machine learning using gradient methods is the finite sum minimization in equation (T). In this problem, the number of samples n is usually very large, rendering the evaluation of full gradients expensive. Therefore, mini-batch gradient is introduced to approximate the full
2

---

Under review as a conference paper at ICLR 2021
gradient. Mini-batch gradient descent is often carried out in epochs, where each epoch includes several iterations of parameter updates. This epoch-wise implementation can easily incorporate shufiling techniques, which have proven to be effective for SGD both in theory and practice.
We aim to analyze the convergence rate of adaptive gradient methods under this framework, where the objective be non-convex. Throughout this paper, we restrict the discussions of convergence to achieving c-approximate first-order stationary point defined as æ satisfying f()]l S c. We leave for future work analysis related to saddle points and second-order stationary points. We want to show that adaptive gradient methods can find x such that [+](] (T22) in T epochs.
x² denotes the matrix we' T and || is the lz-norm of vector w: diag V), [VI,, Amin (V) and Amax (V) are the diagonal matrix, the spectral norm, the largest and smallest non-zero eigen- values of the matirx V, respectively. For alphabets with subscripts, Vay denotes the collection of (U, Ui+1,..., .... } and v. denotes the entire set of u.; similar notations are used for alphabets with double subscripts. Let [n] = {1, (1,...:11 n.), O(),, Ó(-) be the standard asymptotic notations. Denote e; as the unit vector with its i-th component being 1 and e the all-one vector whose dimension depend on the context. As a clarification, we use T to denote the number of epochs (instead of the number of iterations in Table starting from this section.
Notations.
AdaGrad-type methods. As opposed to SGD, adaptive gradient methods assign a coordinate-wise adaptive learning rate to the stochastic gradient. We formulate the generic AdaGrad-type optimizers. including their full and diagonal versions, as follows. At the i-th iteration of epoch t, the parameter is updated by:
F1,++1
Dt.i Tte V 1/2
9t.ir
(full version)
F1,441 Ct,i midia 1/2 gr,
(diagonal version)
where it.; is the mini-batch gradient of the objective at Tt the matrix Vi, contains second-momen calculated using all the past stochastic gradients and γ is the step size of epoch t. The initial parameter of epoch + 1 is taken to be the parameter updated by epoch L, i.e. 3141,1 = Fr,m+ I where we have m iterations in each epoch. The full version is impractical for high-dimensional æ. Thus the diagonal version is often preferred in literature. As an example, the recond-momed matrix in AdaGrad taken to be V (Ei=) 2 + Ej= gt,/ SGD can also be written into this general form where we set Vt, to the identity matrix.
Sampling Strategy. Random shuffling, also known as sampling without replacement, an often- used technique to accelerate the convergence of SGD. The idea is to sample a random permutation of function indices [n] for each epoch and slide through this permutation to get the mini-batch gradients for the iterations in this epoch. Some implementations shuffle the set [ri] uniformly independently for each epoch while others shuffle the set once during initialization and use the same permutation for all epochs. Generally speaking, suppose we have permutation
(aI...., ..., σx) On) at epoch t, we define the set By, = {az : - 1) m <j S im where m is the number of iterations in one epoch. Then the mini-batch gradient is taken to be It.i m/n EjeB.. (
This sampling method of mini-batches benefits the theoretical analysis of SGD by providing bounded error between the full gradient and the aggregation of mini-batch gradients in one epoch (Haochen & Sra. 2019; Nguyen et al. 2020). A naive observation that backups this point can be made = Zt.m, since L BB,, = [n]. we would have En 9t. = Vf( Then
by assuming 2t,1
full gradient can be used to obtain convergence better than plain SGD.
Random shuffling for AdaGrad. Unlike SGD, in adaptive methods, is hard to approximate the full gradient with the aggregation of mini-batch gradient updates in one epoch due to the presence of the second moments. As we will show experiments, the simple shuffling variant that only changes the sampling method of mini batches in AdaGrad does not lead to better convergence. The major difficulty hampering the analysis of this variant is that the second-momed matrix uses all the gradient information in history without distinguishment. Thus to be able to leverage the benefit of the full gradient, we propose to study a slight modification of AdaGrad. Formally, we shuffle the set [n]] once at initialization and obtain the mini-batch gradients in random shuffling manner. We update the
3

---

Under review as a conference paper at ICLR 2021
parameters by the same rules of AdaGrad-type -type methods described above where the second-moment matrix is taken to be:
Vn,1
9
15
+
AAdaGrad-window
j=++1
j=1
The difference between HhaGrad-window and AdaGrad is that the former only use the latest m mini-batch gradients instead of an epoch-wise average of the mini-batch gradients in history. The step size is 7/ = n/ / where 7) a constant for both methods. The updates of AdaGrad-window is also very similar to the GGT method (Agarwal et al. 2019) without momentum. However, GGT uses the full matrix inversion, where our analysis applies to both full and diagonal versions.
3 MAIN RESULTS
We will show that Adndrad-window has the convergence rate of O(T-1/2) for non-convex problems under some mild assumptions. This significant improvement compared with previous best convergence results of adaptive gradient methods and random shuffling SGD, which are of order O(T-1/4) and ((T-1/3) respectively. The key towards our convergence rate improvement is two- fold: the epoch-wise analysis of random shuffling enables us to leverage the benefit of full gradients; the adaptive learning rates and the strong growth condition endow a better improvement of objective value in consecutive epochs.
In order to achieve this better convergence, we first state the assumptions and important concepts used in the proof. Apart from the general assumptions [A1] and uSe] in previous analysis (Fang et al.
2018 Zaheer al. 2018 Ward et al. 2018), we pose another assumption described below in
A3 to characterize the consistency between individual gradients and the full gradient.
Assumptions.
We assume the following for AdaGrad-window:
(A1) The objective function is lower bounded and component-wise T-smooth, i.e. 7f" E IR s.t. f(x) 2 f -c, Va and fz()) fi L || yll Vx, y, i.
(A2) The mini-batch gradients in the algorithm are uniformly upper bounded, i.e. 3G E R s.t. ||,,و|| S G, Vt.
(A3) The objective function satisfies the strong growth condition with constant r², i.e. Va, "t [=)] S 2 [[))))) (
The strong growth condition assumption is essentially enforcing the norms of individual gradients to be at the same scale as the norm of the full gradient. This condition was originally used to derive faster convergence for SGD in the context of convex finite sum minimization (Schmidt & Roux 2013). It was further explored to analyze SGD-type methods after showing its closed relationship with interpolation (Ma previous analysis, we will give more in in-tepth discussion for this assumption in section
2018, Vaswani et al. 2019; Gower et al., 2019). Built upon these
Under these assumptions. the following theorems show our convergence result for the full and diagonal versions of AdaGrad-window
-544 denote Theorem (The convergence rate of full AdaGrad-windowy For any T > 4, set m 5/4 Ci m//4/11// 8 x2 (f( l G) /v2 and C2 3/4 /11/3///11888--//// constants independent T.
as
T. We have:
[V < { (C1 + +C1+
min SSTT
(2)
VT
Theorem (The convergence rate of diagonal AdaGrad 7 m 5/4 denote C₁ m²/4 8 (f(#1,1)- - + GVd) 1/2 and C² =
For any T > 4, set
5m 5/4 /1133+8.2220 V2 as constants independent of We have:
1 (C + C.TT)
min SSKT
< VT
(3)
4

---

Under review as a conference paper at ICLR 2021
The interpretation of these two theorems is that able find an approximate first-order stationary point such that f = 1/3) within T epochs using both versions. We notice that the convergence rate AdaGrad-windee
matches that of GD when m = 1, which denotes that results relatively tight with respect T. The complete proof is included in the appendix. We will give the intuition and key lemmas explaining how to utilize random shuffling and second moments obtain these results in the next section.
In addition, we also prove for another variant of AdaGrad, namely, AdaGrad-truncation with second- moment matrix defined as Vi,; second-moment matrix is very similar to the norm version of AdaGrad (Ward et al. 2018) whereas we use the aggregation of mini-batch gradients in the previous epoch as the coefficient. AdaGrad- truncation is beneficial since the formulation leads fast and simple implementation without needing to discuss the full and diagonal versions. Due to the space limitation, we list the result below and defer the discussions to the appendix.
I and Vt. m| 1 1| when > 1 This
Theorem (The convergence rate of AdaGrad-truncation)) For any T > 4, set 7 /3/ (10m /f(E fo + G2)/vL+ +2, 2, denote C' 80m(Lr+ 2) f( f G2 as constants independent of T. We have:
C VT
min SSKT
(4)
OVERVIEW OF ANALYSIS
The goal of this section give the key intuition for proving Theorem I and Theorem In the following, we use the full version as an example where similar results can be obtained for the diagonal version by adding a dependency on dimension d. Proof details of both versions are included in the appendix. The key towards proving Theorem[is to establish the following lemma.
Lemma 1. For any > 1, in the full version of AdaGrad-windae denole Ci 11/11/3 8 8. 02 = 5n mn/22 + mn as constants independent of 1. We have ei- ther:
1
1
e [(([(()))) S f(x11) - f(xr + C2:
(5)
Vi Vi (nmL). In addition, there is always 0 - f( f(x +
or [((x)))))) S
1
The deduction of convergence rate is straightforward based on this lemma. Either there [V S (/mL../2// /T for some T/2 S T, leading directly to Theorem or we can sum up equation (5) for T/2 < t < T: the coefficients are approximately vT on the left and T the right thus leading to Theorem [ Therefore, lemma instead. Under the L-smooth assumption, we have the standard descent result for one epoch ff(x; (x,,1 x1,++1) S f(x111 fx(,m+1) + L/2 || æ 2| (we refer the proof of to (Nesterov 2018)). Rewrite the equation by replacing Ft,++1 Ft,1 on the left with the
turn the proof of this
HlaGrad-windol updates:
L
Vf (2) V 1/2 Σ grd) <f(w),)) f(x + =| 21,11l2
V
m
m
+ " Vt
vf(x(1))
V 1/2
Σ
gt.i
V
1/2
gt.i
S2
The idea behind this decomposition is to split out the term SI that behaves similarly to the full gradient and control the remaining terms. Similar to other analysis of adaptive methods, the term |x I on the right can be upper bound by a constant times 1/t (we refer sealars that do not depend on t constants). This can be done by simply plugging in the update rules, the details of which are showed in the appendix. Next, we show how to bound term SI and S2 in order to prove Lemma
5

---

Under review as a conference paper at ICLR 2021
4.1 LOWER BOUND OF S1
To obtain the lower bound of S1. we need two steps. The first step stems from the idea in random shuffling SGD (Haochen & Sra 2019), which is to bound the difference between the full gradient and the aggregation of mini-batch gradients. Formally, we have the following lemma.
Lemma 2. For any >> 0, the full version of AdaGrad wwndrow denote constant C3 = we have:
[VI(211)) - m Σ gt. Σ V C3.
(6)
Building on top of this lemma, term S1 can be written into a constant combination of 1/ and EE gt.s) V.. 112 (Σih It.s). which leads our second step. In the second step, we utilize the strong growth assumption to obtain lower bound formulated as below.
Lemma 3. For any > 0, the full version of MakaGrad-windond we have either:
2 ge.i) V 1,
Zg. V11/3+8.0 gr.ll
(7)
or [V S V (nmL). In addition, there always nt gr.))
1/2 (2 It,s) 2
This lemma shows that (E 9r.a) constant. Therefore,
It.s) can be lower bound by > It.ill times
1,
able to derive constant combination of Σ D= gt.il and 1/vi f the
lower bound for $1, which is desired for Lemma
We emphasize that the essential element of the convergence rate improvement lies in Lemma For SGD, the matrix V.m is the identity matrix leading to a lower bound of >>' It.ill instead of E St.sll- This lower order leads to a greater decrease objective value between consecutive epochs as shown in Lemma The reason that we are able to lower the order on ||> It,a is due to the presence of the second moments canceling out the order.
4.2 UPPER BOUND OF S2
To obtain the upper bound of $2, we can write V E It.i into E 1/2
gt.;- Therefore, only need to take care of the second-monen matrices Vi, and V,,. As a matter of fact, we have the following lemma.
Lemma For any
and S i S m, in the full version of AdaGrad denote 6m i 1)(m L)L/T + 4n(mm i)(m + i 1)L/ as constants independent of we
have:
V
1/2 v.l2
1 Vt C4.
(8)
Based on this lemma, we can obtain an upper bound of $2 using the result below.
Lemma 5. For any > 1, in the full version of AdaGrad-windon denote Cs 5xpm5/2 n mpm pm?1. constants independent of t, have:
(x
m V 1.
V
g
Vi
C5.
With this upper bound derived, we are able to prove Lemma towards the convergence result in the Theorem
U| which is the key intermediate result
COMPLEXITY ANALYSIS
Based on Theorem and discuss the computational complexity for two versions of AdaGrad- window. We compare the total complexity between AdaGrad-wint window and random shuffling SGD to demonstrate that this adaptive gradient method can be faster than SGD after finite epochs in theory.

---

Under review as a conference paper at ICLR 2021
Corollary 1 (The computational complexity of full-version AdaGrad-windowe Let { lT=1 be the sequence generated by GaaGrad-window For given tolerance e, to guarantee that the total number of epochs is nearly (ignoring logarithm) O(mb/2 E-2) Therefore, the total number of gradient evaluations is nearly (ignoring logarithm) O
ming f
Compared with the full version, their diagonal version is more practical in modern neural network training. Fortunately, a similar result can be derived for the diagonal version.
Corollary (The computational complexity diagonal-version AdaGrad-window). Let { be the sequence generated by AdaGrad-windon min SAST [f(x,,))) I 6, the total number of epochs is nearly (ignoring logarithm) 1/ Ommi22d E 2). Therefore, the total number of gradient evaluations is nearly (ignoring logarithm) O (m 2nds
For given tolerance to guarantee
For achieving the e-approximate first-order stationary point, the total number of gradient evaluation required by random shuffling SGD is Onde 3) (Haochen & Sra 2019; Nguyen et al. 2020 In a rough comparison, AdnGrad-window has advantages over random shuffling SGD when R O(m (mm). Therefore, in theory, AdaGrad one epoch m is small. Recent works in deep neural net training You et al. 2017 2020 have shown that large batch scenarios, adaptive methods tend to converge faster in training. Since m is the number of iterations in epoch, meaning that small m gives a large batch size, our theory supports these previous findings. However, it seems that choosing m = 1, which amounts to full gradient calculation every step, attains the fastest result theoretically. We point out here that our bound on the m might not be strict and encourage future work to improve upon that in order to get sense of how choose mini-batch sizes practice.
is more efficient when the number of iterations in
THE STRONG GROWTH CONDITION ASSUMPTION
This section aims to provide answers regarding the strong growth condition assumption (A3) In particular, when is this assumption satisfied? Can it be used improve the convergence rate of other methods? As answers to the first question, we first summarize previous results based on its closed relation with interpolation and the weak growth condition (Vaswani al. 2019), then we extend to show that two general types of objective functions satisfy the strong growth condition in some cases. We discuss the convergence rate of other gradient- maddentt-based methods under the strong growth condition for the second question.
6.1 FUNCTIONS SATISFYING THE STRONG GROWTH CONDITION ASSUMPTION
The strong growth condition in (A3) requires [() O for all the individual functions at local stationary point æ with f U. In the sense of fitting model to data, where each fa represents a data point, this translates æ. the parameter, interpolating all the data points. The interpolation property has been utilize to study the convergence and mini-batch size of SGD for convex loss functions (a et al. 2018). Formally, function f is said to satisfy the interpolation property, if for any x::
Vs(x) 0 = Vf(()) = 0, Vi.
(10)
This property has been observed to hold for expressive models such as over- wer-parameterized neural networks (Zhang et al. 2017)
Another concept closely related to the strong growth condition is the weak growth condition. Defined by Vaswani al. 2019)) function is said to satisfy the weak growth condition with constant p, if for any t::
v n Σ
[Vf((z)) 2pL[f(x) f(x")).
(11)
where L is the smoothness constant and x" is a minima of f. assuming existence. The weak growth condition is relaxed version of the strong growth condition in that the latter implies the former. Vaswani et al. (2019) also showed that functions satisfying both the weak growth condition and Polyak-LLojasiewiez (PL.) inequality (Polyak 1963) must satisfy the strong growth condition.

---

Under review as a conference paper at ICLR 2021
Furthermore, they proved that convex functions with interpolation property must satisfy the weak growth condition. The following diagram summarized the above results.
interpolation
weak growth condition inequality
strong growth condition
Figure 1: Previous results on the strong growth condition
Since the PL inequality holds for strongly convex functions, strongly convex functions with interpola- tion property must satisfy the strong growth condition. Results (Milne 2019) demonstrate that the quadratic loss function with 12-penalty for a feed-forward neural network with ReLU activation piecewise strongly convex, with domains of convexity determined by the network architecture, penalty factor, and data. Based on this fact, may have the following lemma for the strong growth condition.
Let f((x)) be the lz-penalized quadratic loss function at data point (a;, 0i) for feed- forward neural network with ReLU activation and scalar outputs, i.e.
Lemma 6.
f:(x) = La (a; + 111=1??
where x is the parameter of the neural network and is the penalty factor. Define nonempty open set containing 0 to be:
A
== | H-1 |
222 + 1)c
where H. is the number of hidden layers and c 2 ||a:Il, Vi. If Ss has a uniform minimizer x² for i 1,,,.. n and is L-smooth with constant L, then almost all points in U satisfy the strong growth condition with constant 2L
X i.e. EU' c U such that UN has no inner point and:
R
2L X IV)(E))?
E
Therefore, for feed-forward neural networks with ReLU activation, e.g. VGG networks (Simonyan & Zisserman 2015), are able to show that the strong growth condition holds for in the neighborhood of if there exists a uniform minimizer for all f.. As a result, we might have the strong growth condition for all æτ,i generated by the algorithm if the initialization and step sizes appropriately chosen.
For linear models, are able derive much stronger results such that the strong growth condition holds for all æ without any constraint on the global minimizer. In particular, Vaswani et al. (211)) showed that the squared-hinge loss, for linearly separable data with margin and finite support c, satisfies the strong growth condition with constant S We extend this result to cross-entropy loss and obtain the same result.
Lemma 7. For linear separable data with margin t and finite support of size c, the cross-entropy loss satisfies the strong growth condition with constant 7z.
6.2 CONVERGENCE RATE UNDER THE STRONG GROWTH CONDITION ASSUMPTION
Under the strong growth condition assumption, previous results have shown that SGD can achieve better convergence rate in many settings. In the context of expectation minimization and global optimality. SGD has linear convergence for strongly convex problems and sublinear O con- vergence for convex problems (Schmidt & Roux 2013). For non-convex problems, Vaswani et al. (2019) proved that constant step-size SGD can obtain first-order stationary points in an rate asymptotically, However, to the best of our knowledge, non-asymptotic results under the strong growth condition have yet to be explored. Our main theorem shows that adaptive gradient methods achieve non-asymptotic convergence rate of -1/2)
8

---

Under review as a conference paper at ICLR 2021
7 EXPERIMENTS
To investigate the effect of adaptive step size and random shuffling, we compare the empirical performances of four different methods on MNIST and CIFAR-I0 show the acceleration effect. We include SGD and AdaGrad to confirm the existing phenomenon that adaptive step size accelerates the convergence of training. We also show results the modified counterparts, SGD-shuffle and AdaGrad-window to demonstrate the additional benefits of shuffling in training. Both adaptive methods are taken to be the more practical diagonal version.
For our first experiment, compare the results of four methods for logistic regression MNIST. To further examine the performance on non-convex problems, we train ResNet- 18 (He et al. 2015) for the classification problem on CIFAR-10. 10. To back up our theoretical results in the last section where the convergence on the minimum of gradients across epochs established, we report the best train loss and best test accuracy up-to-current-epoch in figure 2 We can see that adaptive methods perform better than SGD methods at the end in both training and testing. For the first few epochs of ResNet-18 18 training, we argue that the comparison seems contrary the theory because of the constant effect in the convergence rate where this effect dies out when the epoch number increases. We can also see that SGDD-suffll and AdaGrad-windone exhibit better convergence than their counterparts in training. The details for the experiments are in the appendix.
SGG
Bort Tort Accurnty
SGB
Best Test Accurtty
SGD-shuffle
Best Train Loss
5CB-shultl Adagrad
0.30
-
Adograd-siideee winddww
Allagrad
SCD
12
SCD
Bist
SED shuffie
560 shuffle
0.2
90
Adugridd
20
Adlgrod
Adagras
Adkgruddeendow
30
20
10
20
30
20
40
60
60
60
Epochs
Epachw
Spochs
Epochs
Figure 2: Left: best train loss and test accuracy up-to-current-epoch of logistic regression on MNIST. Right: best train loss and test accuracy up-to-current-epocch of ResNet-18 on CIFAR-10.
CONCLUSION
In this paper, we provide a novel analysis to demonstrate that adaptive gradient methods can be faster than SGD after finite epochs in non-convex and random shuffling settings. We prove that AdaGrad-windn and AdaGrad-trunced
obtain convergence rate of 1/2) for first-order stationary points, a significant improvement compared with existing works. One key element the strong growth condition, which is common in peramtteeettr models. We also investigate the computational complexity and show that our theory supports recent findings on training with large batch sizes. We believe that this paper is good start that could lead analysis and practice in more general settings.
REFERENCES
Naman Agarwal, Brian Bullins, Xinyi Chen, Elad Hazan, Karan Singh, Cyril Zhang, and Yi Zhang. Efficient full-matrix adaptive regularization. In International Conference on Machine Learning. pp. 110, 2019.
Zeyuan Allen-Zhu. Natasha 2: Faster non-convex optimization than sgd. In Advances in neural information processing systems, pp. 2675-2686, 2018.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. In International Conference on Learning Representations, 2019.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume I (Long and Short Papers), pp. 4171-4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.

---

Under review as a conference paper at ICLR 2021
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(Ju):2121-2159, 2011.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex opti-
mization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, pp. 689-699, 2018.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtarik. Sgd: General analysis and improved rates, 2019.
Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM review, 53(2): 217-288, 2011.
Jeff Haochen and Suvrit Sra. Random shuffling beats SGD after finite epochs. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), International Conference on Machine Learning, volume 97, pp. 2624-2633 Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, 2015.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 26, pp. 315-323. Curran As- sociates, Inc., 2013. URL
www.:iiiinnnnnnnnnnn..e.. nwwrips cc pawp:/aapprreeeee httppppppp////////// aalaa000ecceaaL022223eeeeeeeeee2
pdf
Tosio Kato. Perturbation theory for linear operators; 2nd ed. Grundlehren der mathernatscchen Wissenschaften A Series of Comprehensive Studies in Mathematics. Springer, Berlin, 1976. URL
https: cds cern http:e/cccceeeerr///111111
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1412. 6980, 2014.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of SGD in modern over-parametrized learning. volume 80 of Proceedings of Machine Learning Research, pp. 3325-3334, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http:ttt:///:ceeeee
mlr press/v80 1a/800/aal / Ba. html
Tristan Milne. Piecewise strong convexity of neural networks, 2019.
Yurii Nesterov. Lectures on Convex Optimization. Springer Publishing Company, Incorporated, 2nd edition, 2018. ISBN 3319915770.
Lam M Nguyen, Quoc Tran-Dinh Dzung T Phan, Phuong Ha Nguyen, and Marten van Dijk. A unified convergence analysis for shuffling-type gradient methods. arXiv preprint arXiv:2002.08244. 2020.
B. Polyak. Gradient methods for the minimisation of functionals. Ussr Computational Mathematics and Mathematical Physics, 3:864-878. 1788 1963.
Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization, 2016.
Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition, 2013.
Bernhard A. Schmitt. Perturbation bounds for matrix square roots and pythagorean sums. Linear
Algebra and its Applications,, 174:215 227, 1992. ISSN 0024-3795. doi: http://doiicomm org/
URL http:/ http://wwwwineeerreettttt.eeeeee rect www.:/eeettttteeeeeeeeeeeeeeeeee com/ com/science/
Bxticlee/p1/0002455533333
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition, 20155
10

---

Under review as a conference paper at ICLR 2021
Matthew Staib, Sashank Reddi, Satyen Kale, Sanjiv Kumar, and Suvrit Sra. Escaping saddle points with adaptive gradient methods. arXiv preprint arXiv:1901.09199, 2019.
T. Tieleman and G. Hinton. Lecture 6.5-RmsProp: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 2012.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need, 2017.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and an accelerated perceptron, 2019.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization. arXiv preprini arXiv:1806.0188 I, 2018.
Yang You, Igor Gitman, and Boris Ginsburg. Large batch training of convolutional networks, 2017.
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. In International Conference on Learning Representations. 2020. URL http://ppppte.eeee//o/e/ee/o//ep net wtw.://rrrnnnnnanneeeee
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In Advances in neural information processing systems, pp. 9793-9803,
2018.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization, 2017.
Dongruo Zhou, Yigi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint 1808001800..67,, 2018.


Reviews:
[{"review_id": "pPiF0DLYxmX", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper develops new stepsize rules for Adagrad with shuffling to improve the convergence rate from $O(1/T^{1/3})$ in the previous works to $\\tilde{O}(1/T^{1/2})$, which is significantly better than existing AdaGrad variants.  \nHowever, after reading up to the analysis as well as the assumptions stated in the paper, it appears that Assumption 3 seems to be artificially enforced to achieve such a fast rate. Unfortunately, the authors do not provide examples or mathematical justification to show why this assumption is reasonable. This assumption is not algorithmic independent, it depends on the sequences generated by the algorithm. Although the authors conduct some experiments to show that this assumption holds in practice, but such an example remains nonconstructive and may hold by accident. \n\nThough the proof technique seems to be new, it heavily relies on Assumption 3 to transform the squared-norm of the gradient as usually used in gradient-based methods for nonconvex problems to the norm of the gradient, making the convergence rate to be faster than known results as can be seen in the key recursive inequality (5) of Lemma 1. \n\nIn terms of technical details, the reviewer would like to raise the following questions?\n1) What should be the nature of Assumption A.3.? \n2) How should it relate to existing assumptions, e.g., strong convexity-type or bounded variance condition? \n3) Is there any example that is independent of algorithms such that this assumption can be twisted to satisfy? \n4) This rate seems to match the rate of SGD in the strongly convex case? Is there any relation between Assumption A3. and the strong convexity? If so, what is the meaning of the constant r?\n5) Can the stepsize in Theorems  2 and 3 be independent of $f^*$? \n6) Can one choose constant stepsize $\\eta_t = \\eta/T$ so that the $\\log(T)$ term in the convergence rate disappear?\n\nSince the main contribution is on the new choice of step-size/learning rate, it is very hard to assess the work from a practical point of view if one just simply tunes the learning rate in standard Adagrad to compete with the new algorithm. So, I do not see the experiment reflects much the efficiency of the new algorithm if the test is only done with NN training. Therefore, additional examples could be added to illustrate the benefit of the new variant.\n\nIn addition, the paper still contains so many typos as well as some inconsistent English expressions. Here are some of them: bouned, \nintuitions, we refer scalars that does not depend on t to constants, ormance, seems off, etc.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "UmTpW-gc7Md", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper shows that adaptive learning rates are beneficial for finding critical points of finite-sum optimization problems. In particular, with appropriate learning rates, a variant of adagrad can find a epsilon critical point in \\tilde O(1/epsilon^2) iterations. This improves upon previous results of either O(1/\\epsilon^3) or O(1/\\epsion^4) in various situations. The key new assumption is a “consistency condition” that bounds how big individual example gradients can be when the overall gradient is small.\n\nOverall I liked this work, the result seems interesting, and potentially will inspire future work.\n\nI liked the consistency condition here, but I think the paper would be very much served by a more in-depth discussion of what this condition is saying. My own intuition here is that, roughly speaking, the standard deviation of the gradients is at most r sqrt(m) larger than the true average gradient for some constant r. \nThis seems like some kind of analog of the “L*” bounds in convex stochastic optimization, for which it is known that when the gradients have variance at the optimum (which also implies small loss values at the optimum in the convex case), then asymptotically faster convergence is possible. Moreover, in this case it is also known that adaptive methods like adagrad are able to achieve these rates easily. See, e.g. (https://parameterfree.com/2019/09/20/adaptive-algorithms-l-bounds-and-adagrad/).\n\nMy main qualm with the paper is that the modified algorithms appear to require O(m) memory in order to implement the windowed adagrad. This seems a bit excessive, but seems a good direction for future work. For example, it is possible that some kind of EMA would be able to remove this issue.\n\nHowever, related to this issue, it seems that the overall computational complexity of the algorithm is actually *worse* than just plain full-batch gradient descent, which would not require any memory overhead and takes O(n/epsilon^2) gradient evaluations to reach an epsilon critical point, rather than O(m^(5/2)n/epsilon^2) so it is unclear that this analysis really explains any success over full-batch gradient descent. Is it possible that the m factor is very loose in this analysis, or do I miss something here?\n\nFor Lemma 6 something seems a little off in proving the last statement. I believe the result is correct, but something is perhaps missing in the second equality, or at the very least could do with more explanation. For example, if d=1, m=2, \\delta=0 and g_1 =1 and g_2=-1, then the relevant value is zero, but the second equality would say it is sqrt(2).\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "AWrt-8TCi1I", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*Summary:\nThis paper investigates stochastic methods for finding an approximate stationary point for a non-convex function that can be written as a finite sum. The authors consider the combination of adaptive (Adagrad style) methods in conjunction with a random shuffling.\n\n*Significance: \nThe authors have missed a very important aspect of stochastic optimization.\nIn stochastic optimization the right way to measure progress is to present the error versus the number of stochastic gradient computations.\nThe authors present the error as a function of the number of epochs, where in each epoch we go over the whole dataset.\n\nMoreover, the suggested method does not have any benefit over full GD.\nBasically, when m=1, the method in the paper is equivalent to GD and obtains the same optimal \n$O(1/\\sqrt{T})$ rate. When $m>1$ the authors prove a rate which is worse by a factor of $O(m^{5/4})$ compared to GD. Therefore, they actually show that GD (m=1) is optimal for their algorithm and that there is no benefit to stochasticity (m > 1).\n\n\n*Summary of review:\nThe suggested method  does not show any benefit over full GD, so I don't see what is the contribution here.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "95XxJ08yglD", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "I will initially provide a summary of the paper and list overall strengths and weakness of the paper. Then, I present my additional comments which are related to specific expressions in the main text, proof steps in the appendix etc. I would appreciate it very much if authors could address my questions/concerns under “Additional Comments” as well, since they affect my assessment and understanding of the paper; consequently my score for the paper.\n\n\n\nSummary:\n\n•\tThe paper focuses on convergence of two newly-proposed versions of AdaGrad, namely AdaGrad-window and AdaGrad-truncation, for finite sum setting where each component is smooth and possibly nonconvex. \n\n•\tThe authors prove convergence rate with respect to number of epochs T, where in each epoch one full pass over the data is performed with respect to well-known “random shuffling” sampling strategy. \n\n•\tSpecifically, AdaGrad-window is shown to achieve $\\tilde{ \\mathcal O } (T^{-1/2})$ rate of convergence, whereas AdaGrad-truncation attains $\\mathcal( T^{-1/2} )$ convergence, under component-wise smoothness and bounded gradients assumptions. Additionally, authors introduce a new condition/assumption called consistency ratio which is an essential element of their analysis.\n\n•\tThe paper explains the proposed modification to AdaGrad and provide their intuition for such adjustments. Then, the main results are presented followed by a proof sketch, which demonstrates the main steps of the theoretical approach.\n\n•\tIn order to evaluate the practical performance of the modified adaptive methods in a comparative fashion, two set of experiments were provided: training logistic regression model on MNIST dataset and Resnet-18 model on CIFAR-10 dataset. In these experiments; SGD, SGD with random shuffling, AdaGrad and AdaGrad-window were compared. Additionally, authors plot the behavior of their proposed condition “consistency ratio” over epochs.\n\n\n\nStrengths:\n\n•\tI think epoch-wise analysis, especially for finite sum settings, could help provide insights into behaviors of optimization algorithms. For instance, it may enable to further investigate effect of batch size or different sampling strategies with respect to progress of the algorithms after every full pass of data. This may also help with comparative analysis of deterministic and stochastic methods.\n\n•\tI have checked the proof of Theorem 1 in details and had a less detailed look at Theorems 2 and 3. I appreciate some of the technically rigorous sections of the analysis as the authors bring together analytical tools from different resources and re-prove certain results with respect to their adjustments.\n\n•\tPerformance comparison in the paper is rather simple but the authors try to provide a perspective of their consistency condition through numerical evidence. It gives some rough idea about how to interpret this condition.\n\n•\tMain text is written in a clear; authors highlight their modification to AdaGrad and also highlight what their new “consistency condition” is. Proposed contributions of the paper are stated clearly although I do not totally agree with certain claims. One of the main theorems has a proof sketch which gives an overall idea about authors’ approach to proving the results. \n\n\n\nWeaknesses:\n\n•\tAlthough numerically the paper provides an insight into the consistency condition, it is not verifiable ahead of time. One needs to run a simulation to get some idea about this condition, although it still wouldn’t verify the correctness. Since authors did not provide any theoretical motivation for their condition, I am not fully convinced out this assumption. For instance, authors could argue about a specific problem setting in which this condition holds.\n\n•\tTheorem 3 (Adagrad-truncation) sets the stepsize depends on knowledge of $r$. I couldn’t figure out how it is possible to compute the value $r$ ahead of time. Therefore, I do not think this selection is practically applicable. Although I appreciate the theoretical rigor that goes into proving Theorem 3, I believe the concerns about computing $r$ weakens the importance of this result. If I am missing out some important point, I would like to kindly ask the authors to clarify it for me.\n\n•\tThe related work which is listed in Table 1, within the group “Adaptive Gradient Methods” prove \\emph{iteration-wise} convergence rates for variants of Adam and AdaGrad, which I would call the usual practice. This paper argues about \\emph{epoch-wise} convergence. The authors claim improvement over those prior papers although the convergence rate quantifications are not based on the same grounds. All of those methods consider the more general expectation minimization setting. I would suggest the authors to make this distinction clear and highlight iteration complexities of such methods while comparing previous results with theirs. In my opinion, total complexity comparison is more important that rate comparison for the setting that this paper considers.\n\n•\tAs a follow up to the previous comment, the related work could have highlighted related results in finite sum setting. Total complexity comparisons with respect to finite sum setting is also important. There exists results for finite-sum nonconvex optimization with variance reduction, e.g., Stochastic Variance Reduction for Nonconvex Optimization, 2016, Reddi et. al. I believe it is important to comparatively evaluate the results of this paper with that of such prior work.\n\n•\tNumerically, authors only compare against AdaGrad and SGD. I would say this paper is a rather theory paper, but it claims rate improvements, for which I previously stated my doubts. Therefore, I would expect comparisons against other methods as well, which is of interest to ICLR community in my opinion. \n\n•\tThis is a minor comment that should be easy to address. For ICLR, supplementary material is not mandatory to check, however, this is a rather theoretical paper and the correctness/clarity of proofs is important. I would say authors could have explained some of the steps of their proof in a more open way. There are some crucial expressions which were obtained without enough explanations. Please refer to my additional comments in the following part.\n\n\n\nAdditional Comments:\n\n•\tI haven’t seen the definition that $x_{t, m+1} = x_{t+1, 1}$ in the main text. It appears in the supplements. Could you please highlight this in the main text as it is important for indexing in the analysis?\n\n•\tSecond bullet point of your contributions claim that “[consistency] condition is easy to verify”. I do not agree with this as I cannot see how someone could guarantee/compute the value $r$ ahead of time or even after observing any sequence of gradients. Could you please clearly define what verification means in this context?\n\n•\tIn Assumption A3, I understand that $G_t e_i = g_{t,i}$ and $G_t e = \\sum_{i=1}^{m} g_{t,i}$. I believe the existing notation makes it complicated for the reader to understand the implications of this condition.\n\n•\tIn the paragraph right above Section 4.2, authors state that presence of second moments, $V_{t,i}$ enables adaptive methods to have improved rates of SGD through Lemma 3. Could the authors please explain this in details? \n\n•\tIn Corollary 1, authors state that “the computational complexity is nearly $\\tilde{ \\mathcal O (m^{5/2}nd^2\\epsilon^{-2}) }$”. A similar statement exists in Corollary 2. Could you please explain what “nearly” means in this context?\n\n•\tIn Lemma 8 in the supplements, $aa^T$ and $bb^T$ in the main expression of the lemma are rank-1 matrices. This lemma has been used in the proof of Lemma 4. As far as I understood, Lemma 8 is used in such a way that $aa^T$ or $bb^T$ correspond to something like $g_{t,j}^2 – g_{t-1, j}^2$. I am not sure if this construction fits into Lemma 8 because, for instance, the expression $g_{t,j}^2 – g_{t-1, j}^2$ is difference of two rank-1 matrices, which could have rank \\leq 2. Hence, there may not exist some vector $a$ such that $aa^T = g_{t,j}^2 – g_{t-1, j}^2$, hence Lemma 8 may not be applied. If I am mistaken in my judgment I am 100% open for a discussion with the authors. \n\n•\tIn the supplements, in section “A.1.7 PROOF OF MAIN THEOREM 1”, in the expression following the first line, I didn’t understand how you obtained the last upper bound to $\\| \\nabla f(x_{t,i}) \\|$. Could you please explain how this is obtained?\n\n\n\nScore:\n\nI would like to vote for rejecting the paper. I praise the analytically rigorous proofs for the main theorems and the use of a range of tools for proving the key lemmas. Epoch-wise analysis for stochastic methods could provide insight into behavior of algorithms, especially with respect to real-life experimental setting. However, I have some concerns:\n\n1.\tI am not convinced about the importance of consistency ratio and that it is a verifiable condition.\n\n2.\tRelated work in Table 1 has iteration-wise convergence in the general expectation-minimization setting whereas this paper considers finite sum structure with epoch-wise convergence rates. The comparison with related work is not sufficient/convincing in this perspective.\n\n3.\t(Minor) I would suggest the authors to have a more comprehensive experimental study with comparisons against multiple adaptive/stochastic optimizers. More experimental insight might be better for demonstrating consistency ratio.\n\n\n\nOverall, due to the reasons and concerns stated in my review, I vote for rejecting this paper. I am open for further discussions with the authors regarding my comments and their future clarifications.\n\n======================================= Post-Discussions ======================================= \n\nI would like to thank the authors for their clarifications. After exchanging several responses with the authors and regarding other reviews, I decide to keep my score. \n\n1. Although the authors come up with a more meaningful assumption, i.e., SGC, compared to their initial condition, I am not fully convinced about the contributions with respect to prior work: SGC assumption is a major factor in the improved rates and it is a very restrictive assumption to make in practice. \n\n2. Although this paper proposes theoretical contributions regarding adaptive gradient methods, the experiments could have been a bit more detailed. I am not sure whether the experimental setup fully displays improvements of the proposed variants of AdaGrad.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear authors,

Improving the theoretical understanding of powerful algorithms is an important contribution to our field. Nevertheless, most of the reviewers are inclined to reject the paper. I somehow have to agree with them as e.g., adding more restrictive assumptions can allow deriving better bounds, but the question then is how useful this result will be to the ICLR community. I would encourage you to chose maybe another venue.

Thanks
Decision: Reject