Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers SGD with momentum (and classical SGD if momentum coefficient is equal to zero) and provides last-iterate convergence rates for such an algorithm with (i) allowing for the bigger stepsizes, and (ii) by relaxing the PL-condition. 

strengths_and_weaknesses: 1. Overall, understanding the theoretical convergence of SGD and momentum SGD is an important problem in machine learning. I think it is an interesting and solid result that both SGD and momentum SGD allow for the larger learning rates (even without improving the convergence rate). 

2. The paper misses the discussion on the tightness of the obtained result: is the obtained convergence rate tighter than existing ones (also the ones that use PL-condition or strong-convexity)? Also, does it recover known convergence rates of momentum SGD for the average iterates? Are obtained results recover best-known last iterate convergence rates of SGD when momentum is set to zero? 

3. I found Theorem 3.1 to be confusing. I quickly checked the proof and it seems that you basically show there that ||\nabla g(theta_n) || -> 0 as n -> \infty. I think it would be less confusing to state the theorem in terms of the norm of the gradient. I also did not find that you prove that \theta_n stays bounded, thus it can happen that ||\theta_n|| -> \infty, e.g. if the function behaves similarly to e^{-theta} for \theta -> + \infty. Thus the algorithm might not converge to any connected component of stationary points. 

4. Regarding presentation, assumptions 3.1, 2) and 3.3. are not common in the literature. It would be useful for the reader to spend more time to explain the connections to the common assumptions in the literature: e.g. for assumption 3.3. explaining how does delta_0 relates to the strong convexity parameter, or \mu in PL condition (I think delta_0 <= \mu). It would be also helpful to provide a table with existing last-iterate convergence results under 

5. Overall the proofs are hard to read. 

6. Less important, I found the notation in the paper to be confusing, usually the stochastic noise is denoted as \sigma, and lipschitz smoothness as L. 

questions: 7. What would be the optimal stepsize to give the fastest convergence? 

8. Can you show some advantages in the theory of using momentum ? 

9. how “a” is defined in theorem 3.2. Should it be a’ ? if not, what is the dependance on a’ in the convergence rate ? 

limitations: -
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper establishes the convergence result of the last iterate of momentum algorithms. In contrast to the existing results that require the step size to be squared summable, this paper allows a larger spectrum of step size rules and even constant step size. The proof technique is different from the standard martingale-based argument.
strengths_and_weaknesses: Strength:

1. The presentation is clear, and the authors make efforts to explain the meaning and use of each assumption, condition in their results, and compare their results to relevant literature.

2. From the practical point of view, it establishes provable convergence for larger step sizes, so the results look nice to me, although I am not an expert in this field. 

3. The additional numerical results certify the theoretical analysis.

Weakness:

1. I am not sure how strong Assumption 3.3 is, even though it is weaker than the P-L condition. The paper illustrates that this assumption holds for a two layer ReLU network, but I doubt it works for more layers.

2. Some illustration of the proof seems important. See my questions below.
questions: 1. I didn't check all proofs, but I think it would be helpful to sketch the proof of Theorem 3.1, in addition to mentioning the main challenges. In particular, how does the proof technique differ from those in [7]?

2.  I am wondering if the rate of $2+\eta_0$, $\eta\in[0,1/2)$, is the best achievable in the setting of Section 3.1. This can be answered either theoretically, or numerically.

3. For Proposition 3.1, the result improves the previous one [22] that imposes strong convexity. But is there any substantial difference in terms of the proof compared with [22]?

4. Minor: I cannot find the definition of $\alpha^{(n)}$ in line 121.
limitations: This is a theoretical work so I think there's not much potential negative societal impact. The authors do not discuss much about the limitations of their results.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proves last-iterate convergence for SGD with and without momentum for larger step sizes and weaker assumptions. In particular, the paper provides asymptotic convergence rates for mSGD when the learning rate decay is slower than what was needed by previous works, hence showing theoretically why mSGD can work with larger learning rates than shown by previous theory. The paper also provides non-asymptotic rates under a more general assumption than strong convexity. The paper has theorems 3.3 and 3.2 which show that even though larger step size may lead to one iterate being very close to a stationary point, the expected error at a fixed iteration number might not necessarily get smaller with larger step size.
strengths_and_weaknesses: Strengths:
1. The paper proves asymptotic convergence for mSGD for learning rates that decay slower than what was proved by previous theory.
2. The paper proves non-asymptotic convergence rates for mSGD in a milder condition than strong convexity.
3. The paper proves that for larger step sizes, indeed convergence is faster in the sense that there will be one iterate that is closer to the optimizer (Theorem 3.3)



Weaknesses:
1. Most of the results in the paper are asymptotic in nature and only prove convergence in the limit (that is, they do not have asymptotic convergence rates). Hence they do not provide much information about the actual rates of convergence. 


Suggestions:
1. The paper should include proof sketches or ideas for the main theorems in the main paper. Since the part where Assumption 3.3 is demonstrated for shallow neural networks is not rigorous, maybe that can be moved to the appendix to make space for proof sketches.


NOTE: I have not verified the proofs in the appendix.


questions: 1. Although Theorem 3.2 hints that larger step sizes might not necessarily lead to faster convergence, to actually prove that it is indeed the case, a lower bound needs to be shown. Is there any lower bound existing in literature that matches or closely follows your upper bound from Theorem 3.2? If not, then a discussion should be added in the paper about this.

2. It will be nice to have some experiments that show that large step sizes that satisfy assumption 3.2 can still be slower for convergence than smaller step sizes, to support the discussion for Theorem 3.2 (lines 190-192).
limitations: Most of the results in the paper are asymptotic in nature and only prove convergence in the limit (that is, they do not have asymptotic convergence rates). Hence they do not provide much information about the actual rates of convergence.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors improve the step size requirement for mSGD and prove the convergence result. Specifically, they have extra assumption condition 2 in Assumption 3.1 then they allow the step size to decay more slowly. Additionally, they prove the subsequence convergence with constant step size. They implement the experiments to verify their theoretical results. 
strengths_and_weaknesses: Strengths:

The problem studied in the paper is very interesting and important for the community. The authors improve the results which are verified by the experiments. The neural network example to support Assumption 3.3 is nice.

Weaknesses:

I don't see any major weakness. Maybe the authors can point out the intuition of the extra assumption (Condition 2 in Assumption 3.1) and how to use it to prove the results. 

questions: 1) I am not totally sure if Condition 2 in Assumption 3.1is a reasonable one. Is the set of stationary points bounded? For overparameterized models, I believe it's not. Is it critical in the proof? Can you clarify it a bit more?

2) The equation in Assumption 3.3 is very close to PL condition. In my understanding, you want the loss to decrease exponentially out of this set? I suggest the authors have more discussion about the relation to PL condition.

3) Can you clarify why we care about the convergence result for subsequence i.e., Theorem 3.4? 

limitations: yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This work considers mSGD and SGD under more weaker conditions on the step size as considered before. This can be important since in practice, picking a large step size initially is shown to improve convergence. Therefore, a theory of convergence with large step sizes can be useful. It is standard to consider step sizes such that $\sum_t \epsilon_t = \infty$ and $\sum_t \epsilon_t^2 < \infty$ whereas this work improves this to $\sum_t \epsilon_t^{2+\eta_0} < \infty$. Under these conditions, along with standard assumptions like smoothness, asymptotic convergence to a stationary point is established (Theorem 3.1).

Under additional growth assumptions of the function, the Theorem 3.2 establishes rates of convergence as a function of the step size sequence, which shows the dependence of the momentum parameter alpha. However, since this does not establish how picking larger step sizes can be effective, the authors show Theorem 3.3 where the upper bounds are such that picking a larger step size can help the algorithm reach a point better than the initial point more reliably. 

The proof techniques and assumptions mostly seem to be modifications of [7]. 

[7] R. Jin, Y. Xing, and X. He, “On the convergence of mSGD and AdaGrad for stochastic optimization,” in
312 International Conference on Learning Representations, 2022
strengths_and_weaknesses: *Strengths*:
The work establishes convergence for widely used stochastic gradient methods in regimes which have not been considered in the literature but nevertheless seem very important. 

*Weaknesses*:
The work does not justify why picking larger step sizes is useful. Theorem 3.2, like the authors discuss, does not show that picking a step size sequence such that $\sum_t \epsilon_t^2 = \infty$ is helpful in terms of convergence rates.

Theorem 3.3, on the other hand, considers a non-standard stopping time $\tau^{(a)}$. This seems to be quite a weak metric to compare algorithms since this is the first time when the algorithm's output is better than the initial point. Also, arguing about how certain step sizes are better based on upper bounds is fallacious since we do not know if the upper bounds are sharp. 


questions: 1. Given the observations above, how do we justify using larger step sizes based on the theoretical results provided?

2. The authors should to carefully compare the techniques used in [7] to the current work since a lot of the main techniques and assumptions seem very similar. They currently mainly compare the results obtained in [7]. 

3. Below Theorem 3.2, the authors discuss that [7] uses the condition $\mathbb{E}\|\nabla g(\theta,\zeta)\|^2 \leq M \|\nabla g(\theta)\|^2$. However, when I checked the ICLR 2022 paper, this work did not contain this assumption in Theorem 2 (See (4) in Assumption 2). However, I do agree Theorem 2 in [7] cannot be established without such an assumption and the original work [7] could have a typo. The authors should elaborate more on this. 
limitations: The authors have been forthright about several of the weaknesses in the analysis in their discussions (as pointed above), however several of the limitations need to be discussed more as pointed out in the rest of the review.
review_title: null

Meta-review: metareview: The paper studies mSGD and SGD methods and provide convergence under weaker requirement on stepsizes. 
The reviewers in general agree that the result is novel, has interesting techniques, and is above bar for Neurips publication. 
However, the paper should tone down it's claim about advantage of large step size as it is mostly based on comparing upper bounds. 
confidence: Certain
Decision: Accept