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 O ~ ( T − 1 / 2 )
rate of convergence, whereas AdaGrad-truncation attains ( 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 = ∑ 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 O ( m 5 / 2 n d 2 ϵ − 2 ) ~
”. A similar statement exists in Corollary 2. Could you please explain what “nearly” means in this context?
• In Lemma 8 in the supplements, a a T and b b 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 a a T or b b 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 a a 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 ∇ 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:
I am not convinced about the importance of consistency ratio and that it is a verifiable condition.
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.
(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.
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.
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.
• 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.