Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: *Summary:
This 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.

*Significance: 
The authors have missed a very important aspect of stochastic optimization.
In stochastic optimization the right way to measure progress is to present the error versus the number of stochastic gradient computations.
The authors present the error as a function of the number of epochs, where in each epoch we go over the whole dataset.

Moreover, the suggested method does not have any benefit over full GD.
Basically, when m=1, the method in the paper is equivalent to GD and obtains the same optimal 
$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).


*Summary of review:
The suggested method  does not show any benefit over full GD, so I don't see what is the contribution here.

review_title: No benefit over full GD

final_score: rating: 7: Good paper, accept
review_content: 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.

Overall I liked this work, the result seems interesting, and potentially will inspire future work.

I 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. 
This 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/).

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

However, 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?

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

review_title: nice results, could do with more discussion of the assumptions.

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.  
However, 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. 

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

In terms of technical details, the reviewer would like to raise the following questions?
1) What should be the nature of Assumption A.3.? 
2) How should it relate to existing assumptions, e.g., strong convexity-type or bounded variance condition? 
3) Is there any example that is independent of algorithms such that this assumption can be twisted to satisfy? 
4) 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?
5) Can the stepsize in Theorems  2 and 3 be independent of $f^*$? 
6) Can one choose constant stepsize $\eta_t = \eta/T$ so that the $\log(T)$ term in the convergence rate disappear?

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

In addition, the paper still contains so many typos as well as some inconsistent English expressions. Here are some of them: bouned, 
intuitions, we refer scalars that does not depend on t to constants, ormance, seems off, etc.



review_title: Adaptive Gradient Methods Can Be Provably Faster than SGD with Random Shuffling

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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.



Summary:

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

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

•	Specifically, 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.

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

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



Strengths:

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

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

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

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



Weaknesses:

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

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

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

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

•	Numerically, 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. 

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



Additional Comments:

•	I 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?

•	Second 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?

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

•	In 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? 

•	In 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?

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

•	In 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?



Score:

I 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:

1.	I am not convinced about the importance of consistency ratio and that it is a verifiable condition.

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

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



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

======================================= Post-Discussions ======================================= 

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

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

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

review_title: Reviewer #3

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