Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: New convergence results for momentum-SGD and AdaGrad
main_review: PAPER SUMMARY: This paper presents new proofs to the convergence of momentum-SGD and AdaGrad. The new theoretical results show they both converge (in the sense of the estimate sequence). Also, the momentum-SGD converges at a faster rate than SGD (with additional assumption on the properties of the loss function used).

NOVELTY & SIGNIFICANCE: momentum-SGD and AdaGrad are extensively used algorithms in practice. Providing further understanding of their properties is always a good direction to go. This paper proves that under some mild assumptions, momentum-SGD can converges faster than SGD (with additional assumption on the properties of the loss function used). This seems to be a new result for nonconvex objectives (for convex/strongly convex ones we already have similar results). For AdaGrad, the paper proves that the estimate sequence itself is convergent, but not convergence rate is provided. Such result for AdaGrad seems a bit weak. In the theoretical aspect, this paper paves new ways to prove the convergence for such algorithms.

TECHNICAL SOUNDNESS: The theoretical results and assumptions seem legitimate and reasonable. But I have not checked the proof details.

summary_of_the_review: The paper provies new convergence results for momentum-SGD and AdaGrad, showing that momentum-SGD converges faster than SGD and AdaGrad's estimate sequence converges. The momentum-SGD proof is beneficial for understanding why momentum works in nonconvex objectives, which is still a not well understood topic.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper focuses on developing asymptotic convergence of mSGD and Adagrad, which is stronger than the existing results on subsequence convergence and iterate average convergence. The assumptions are similar or weaker than previous works. 
main_review: I read some parts of the proof carefully, and it seems that there are some mistakes that should be resolved. I also have several suggestions for the presentation of the paper.

Regarding the presentation: (* are the major concerns)

1. In the optimization literature, the term "estimate sequence" refers to a sequence of auxiliary functions, which were first used in the analysis of Nesterov's accelerated gradient descent. See Definition 2.2.2 of the following textbook.

Nesterov, Yurii. Introductory lectures on convex optimization: A basic course. Vol. 87. Springer Science & Business Media, 2003.

Please consider just using "iterates" to refer to the \theta_n in the paper.

2*. The updating rules of mSGD and SHB in equations 3 and 4 are actually equivalent. This should be mentioned in the paper, and it is inappropriate to say that "the results in Liu et al (2020) do not apply to mSGD." 

For example, to get equ 4 from 3, we have

$v_n = \alpha v_{n-1} + \varepsilon \nabla_n,  \theta_{n+1} = \theta_n - v_n$

$\frac{1}{\alpha + \varepsilon} v_n = \frac{\alpha}{\alpha + \varepsilon} v_{n-1} + \frac{\varepsilon}{\alpha + \varepsilon} \nabla_n, \theta_{n+1} = \theta_n - (\alpha+ \varepsilon) * \frac{1}{\alpha + \varepsilon} v_n$ 

To get equ 4, we just need to set $\frac{1}{\alpha + \varepsilon} v_n$ as $v_n$ and $\beta$ as $\frac{\alpha}{\alpha + \varepsilon}$. All the parameters can also depend on $n$. 

3*. It would be much better if simple proof sketches of theorems 1, 2, and 3 can be added. For example, how is the milder assumption in Assumption 2 4) handled in the analysis? How is the difficulty mentioned in equ (11) handled? Otherwise, readers have to dive into the details of proof to figure them out.

4. In Assumption 4 1), $\varepsilon_1$ has already been used as stepsizes. 

5. Assumption 4 2) is very similar to the Polyak-Lojasiewicz condition, this should be mentioned.

6*. It is inappropriate to say that "We can observe that the convergence rate of mSGD is quicker than that of SGD in this sense." In equation (78), It is unclear why the bound $O((\frac{1}{2-\alpha})^n)$ is relaxed to the bound presented in Theorem 1. Looking at $O((\frac{1}{2-\alpha})^n)$, a larger momentum $\alpha \rightarrow 1^-$ actually gives a worse bound.

7. Under Assumption 5, why is "condition 1)" is relatively weak?

Regarding the proof:

I haven't checked all the proof in detail, here are some problems that need to be clarified:

1. Lemma 3 is a standard result, see Lemma 1.2.3 of the textbook mentioned above.

2. In Lemma 4, it seems that the S_i needs to be bounded, as used in the proof.

3. In Lemma 4, $\varepsilon_0$ is actually defined in the proof, this should be clarified.

4. In the second last equation on page 14, the last term should be integrated to t', not x.

5* The last equation on page 14 is incorrect, how is x_2 canceled? It seems that t'' > 0 is needed, why is this true?

6* In equ 17, why is $|g'(t')| = ||\nabla f(x_0)||$? Specifically, we have $g'(t') = \frac{x_0 - x_2}{\|x_0 - x_2\|}\cdot \nabla f(x_0)$. Therefore, $|g'(t')| = ||\nabla f(x_0)||$ if and only if $x_0- x_2$ is parallel to $\nabla f(x_0)$, why is this the case?

7* In the second last equality of the proof of lemma 4, how is the term $g'(t'')$ handled? The equality holds if and only if $g'(t'') = g'(t')$, why is this true?

summary_of_the_review: In summary, the issues mentioned above must be resolved. In my opinion, there are obvious mistakes in the proof.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper analyzes the convergence of momentum-based SGD (mSGD) and AdaGrad in the sense of asymptotic convergence rather than time average or subsequence convergence in existing results. The analysis shows that mSGD is better than SGD in terms of expectation of squared gradient norms on last iterate.
main_review: The paper appears to use a different template other than ICLR's. I encourage the authors to double check this. The current template makes the paper harder to read at least for me.

Strengths:
- Theorem 1 presents asymptotic convergence which complements existing results in the literature. Convergence in theorem 2 is for metric depending on last iterate which is stronger compared to time-averaged metric.
- The convergence on expectation of squared norm gradient on last iterate shows that mSGD is better than SGD.

Weaknesses:
- The clarity of the paper is not good, the proofs in the appendix are highly technical and hard to follow. I would recommend to have an outline to better understand how each lemma play a role in the main convergence analysis. I have gone through the proofs and find no problem but there is a chance I miss something.

Comments:
- What is the motivation of using assumption 4 or 5 rather than assuming convexity. As these assumptions are not standard, it is better to include examples of classes of function that satisfy these assumptions.
summary_of_the_review: The paper contains solid contribution in terms of theoretical analysis, especially for mSGD. The convergence results are on last iterate different from existing results. However, given the currents state of the submission, the clarity of the paper needs to be significantly improved. Adding proof outline and providing more explanations for key steps definitely helps to improve the quality of the paper.
review_title: null

Meta-review: The paper presents an asymptotic analysis of the convergence of the last iterate of mSGD and Adagrad. This result extends previous work providing stronger results under weaker assumptions. Even if these topics received less attention from the community, they are key problems in stochastic optimization.

The reviewers and I had several doubts about the proofs and relation with previous work. However, the rebuttal phase essential acted as a minor revision process. In fact, the authors fixed all the issues, convincing the reviewers (and me) that the results are novel, correct, and interesting.

For the above reasons, I recommend the acceptance of this paper.
Decision: Accept (Poster)