- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies the normalized gradient descent (NGD) for convex Holder-smooth functions and establishes the last-iterate convergence rate under two choices of stepsizes.
Critical strengths
The analysis is clean and the ideas are well described.
Critical weaknesses
The proof framework and techniques are largely inherited from the prior work (particularly Zamani & Glineur (2025)). While extending those to Holder functions seems to need a few more arguments, the overall approach and conclusions are very close to the existing ones. Overall, the novelty and contributions here appear to be incremental.
Questions for authors
The analysis in Section 5 does remove the logarithmic overhead, but it remains unclear whether the obtained rate is optimal for general in a certain sense.
3 comments
Thank you for reply. I'll maintain my score.
We thank the reviewer again for your feedback.
Following our discussion with Reviewer FEeA, we have further improved our convergence analysis. In particular, Proposition 3 establishes an improved last-iterate convergence rate of
Regarding the reviewer's concern about the novelty of our proof techniques, we would like to emphasize that Proposition 3 further addresses this concern, as its proof goes beyond the Lemma 1-based analysis adapted from Zamani & Glineur (2025) by leveraging the descent lemma. We will replace Theorem 1 with Proposition 3 in the camera-ready version.
Note that the main contribution of our paper remains unchanged: we characterize the logarithmic overhead in the constant-stepsize convergence bound for general and show that it can be removed by a linearly decaying stepsize.
We believe this additional theoretical guarantee further strengthens the contribution of our paper and helps address the reviewer's concerns. We understand the reviewer's earlier decision to maintain the score. However, we would be grateful if the reviewer could also take these improvements into account when reconsidering their evaluation.
We thank the reviewer for your feedback. The reviewer raised two concerns, particularly regarding the novelty of our analysis and the optimality of the linear decay scheduler. We believe that our responses below adequately address both concerns. We hope that our clarifications and additional results will encourage the reviewer to reconsider their score.
If the reviewer still has concerns, we would appreciate being informed. We will be happy to resolve them.
We respectfully disagree that our results are merely incremental.
Significance of the result: First, it is surprising that the last-iterate convergence bound for normalized gradient descent retains a logarithmic overhead even for smooth objectives. To put this result into perspective, gradient descent achieves an O(1/T) last-iterate convergence rate for smooth objectives [1], whereas a logarithmic overhead typically arises in the non-smooth setting [2]. Thus, our result reveals a notable contrast between the known last-iterate convergence guarantees for gradient descent and normalized gradient descent, which is not an immediate consequence of existing results.
Nontriviality of the proof: Second, our proof is not simply a direct extension of the analysis in Zamani and Glineur (2025). While Lemma 1 builds upon their result, the subsequent analysis requires a substantially more involved mathematical induction argument to establish our convergence guarantee. Thus, the proof goes beyond applying the existing framework to the Hölder setting. We added a more detailed explanation in Section E.
Thank you for the comment. Our primary goal is to establish a last-iterate convergence rate matching the well-known O(T−(1+ν)/2) rate for the best and weighted-average iterates of normalized gradient descent. Theorem 2 achieves this rate for all ν∈[0,1] without any logarithmic overhead.
Moreover, for ν=0, our O(1/T) rate is optimal as Theorem 3.2.1 in [1] established a matching Ω(1/T) lower bound for first-order methods. For general ν>0, we do not claim optimality among all first-order methods; establishing tighter rates for normalized gradient descent is beyond the scope of this work.
Reference
[1] Yurii Nesterov. Lectures on convex optimization. In Springer, 2018.
[2] Zamani et. al., Exact convergence rate of the last iterate in subgradient methods. SIAM Journal on Optimization, 2025