acceptodds
Under review as a conference paper at ICLR 2027

Last-Iterate Convergence Rate of Normalized Gradient Descent under Hölder Smoothness

Abstract

Normalized gradient descent is a widely studied adaptive optimization method. Most existing analyses focus on the best iterate or a weighted average of the iterates, whereas practical implementations typically return the last iterate. In this paper, we study the last-iterate convergence of normalized gradient descent for convex, -Holder-smooth objectives. For a constant stepsize, we establish an upper bound of , which contains a logarithmic overhead relative to the known guarantees for the best and weighted-average iterates. For , this overhead is known to be unavoidable. We complement this analysis with numerical results based on the performance estimation problem (PEP), investigating the finite-horizon worst-case behavior in the smooth setting and whether the logarithmic overhead reflects an intrinsic limitation of constant-step normalized gradient descent. We then show that a linearly decreasing stepsize yields a last-iterate guarantee of , matching the order of the best-iterate/weighted-average guarantees without requiring knowledge of and .

Primary area:
optimization
Keywords:
last-iterate convergence rate, normalized gradient descent, holder smoothness

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_LD7COpenReview ↗
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 ν\nu in a certain sense.

3 comments

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.

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.

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

The analysis in Section 5 does remove the logarithmic overhead, but it remains unclear whether the obtained rate is optimal for general ν\nu in a certain sense.

Thank you for the comment. Our primary goal is to establish a last-iterate convergence rate matching the well-known O(T−(1+ν)/2)O(T^{-(1+\nu)/2}) rate for the best and weighted-average iterates of normalized gradient descent. Theorem 2 achieves this rate for all ν∈[0,1]\nu\in[0,1] without any logarithmic overhead.

Moreover, for ν=0\nu=0, our O(1/T)O(1/\sqrt{T}) rate is optimal as Theorem 3.2.1 in [1] established a matching Ω(1/T)\Omega(1/\sqrt{T}) lower bound for first-order methods. For general ν>0\nu>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

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

O(Mν(∥x1−x⋆∥2T)1+ν2(1+log⁡T)1−ν2).O \left( M_\nu( \frac{\|x_1-x^\star\|^2}{T})^{\frac{1+\nu}{2}}(1+\log T)^{\frac{1-\nu}{2}} \right).

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 ν\nu 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.

Reviewer_FEeAOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

Summary

This paper establishes the last-iterate convergence of normalize gradient descent (NGD) on Hölder smooth convex objects. The result interpolates the existing convergence rates of NGD in nonsmooth and smoothing settings upto log factors. The authors justify the log factor dependence through the PEP framework and further remove the dependence with a linearly decaying stepsize.

Critical strengths

Strength

The paper is well-written and the results are neat. It addresses an existing gap in the literature.

Critical weaknesses

Weaknesses

I feel the contributions of the paper incremental despite the neat theoretical results. The related theoretical components already appeared in the literature [1, 2]. Besides, I feel some of the results can be further improved. For example

  1. The order of log factor dependence seems suboptimal even in the PEP experiments. I also find it not sufficiently explained why it's OK to fix {gt}\{g_t\} in the PEP formulation.
  2. From a convergence rate perspective, both convergence rates in the main results are not anytime due to dependence on TT. Stepsizes like O(1/t)O(1/\sqrt{t}) would be more desirable from a practical perspective.

Overall I think the contributions are fine and give borderline rej. I'll raise to borderline acc if my questions are sufficiently addressed/discussed.

Questions for authors

Questions

  1. The analysis now originates from the nonsmooth case, and the potential function is distance to optimality. But here you are essentially doing smooth optimization, and the function satisfies descent lemma f(x)≤f(y)+⟨∇f(y),x−y⟩+Lνν+1∣x−y∣2f(x) \leq f(y) + \langle \nabla f(y), x - y \rangle + \frac{L_\nu}{\nu + 1} \\|x - y\\|^2. Why not establish last-iterate convergence using descent property? I believe at least when ν=1\nu = 1 you can do the analysis easily.
  2. Could you extend the analysis to anytime stepsize that does not depend on TT?

Minor issues

  1. On page 3, I believe it's better to mention you are dealing with convex problems at the very beginning.

References

[1] Zamani, M., & Glineur, F. (2025). Exact convergence rate of the last iterate in subgradient methods. SIAM Journal on Optimization, 35(3), 2182-2201.

[2] Orabona, F. (2023). Normalized gradients for all. arXiv preprint arXiv:2308.05621.

5 comments

We thank the reviewer for the constructive feedback. We believe that we have fully addressed all of the reviewer's concerns in our responses below. In particular, our new lower-bound result, Theorem 3, significantly strengthens the paper by showing that the logarithmic overhead is unavoidable without prior knowledge of TT. We therefore kindly ask the reviewer to reconsider their assessment and, if possible, reconsider the score.

If the reviewer still has concerns, we would appreciate being informed. We will be happy to resolve them.

The order of log factor dependence seems suboptimal even in the PEP experiments. I also find it not sufficiently explained why it's OK to fix gtg_t in the PEP formulation.

Thank you for the comment. Ideally, we would solve the PEP without fixing the gradient norms to obtain the exact worst-case performance. However, this problem is computationally intractable with standard SDP techniques due to the nonlinear normalization.

To address this difficulty, we fix the gradient norms, which makes the PEP tractable. Although this restriction may yield a weaker lower bound, the current result is sufficient to show that the last-iterate convergence rate is slower than O(1T)O(\frac{1}{T}). This is because the worst-case performance of the original PEP can only be worse than that of the restricted PEP. We agree with the reviewer that establishing the tightness of the logarithmic factor is important, but we leave it for future work. We have clarified these points in Section 4.2.

From a convergence rate perspective, both convergence rates in the main results are not anytime due to dependence on T. Stepsizes like O(1/t)O(1 / \sqrt{t}) would be more desirable from a practical perspective.

Thank you for the comment. In Theorem 3, we provide an additional lower-bound result, demonstrating that any stepsize that does not rely on prior knowledge of TT must incur a logarithmic overhead. Therefore, the dependence on TT is not merely an artifact of our analysis, but reflects a fundamental limitation of any anytime stepsize scheme, and the suggested stepsize O(1/t)O(1/\sqrt{t}) cannot omit the logarithmic overhead.

The analysis now originates from the nonsmooth case, and the potential function is distance to optimality. But here you are essentially doing smooth optimization, and the function satisfies descent lemma f(x)≤f(y)+⟨∇f(y),x−y⟩+Lν1+ν∥x−y∥2f (x) \leq f (y) + \langle \nabla f (y), x - y \rangle + \frac{L_\nu}{1 + \nu} \| x - y \|^2. Why not establish last-iterate convergence using descent property? I believe at least when ν=1\nu=1 you can do the analysis easily.

Thank you for your comment. Indeed, as you point out, the last-iterate convergence rate of gradient descent can be derived using the descent lemma [1]. However, the same argument does not apply directly to normalized gradient descent. The key difference is that standard gradient descent guarantees that f(xt+1)≤f(xt)f(x_{t+1}) \leq f(x_t), whereas this monotonicity is not guaranteed for normalized gradient descent (See Section E). This lack of monotonicity makes the last-iterate analysis of normalized gradient descent substantially more challenging, as the standard descent-based arguments are no longer directly applicable. To the best of our knowledge, our work provides the first theoretical analysis of the last-iterate convergence of normalized gradient descent, addressing an important gap in the theoretical understanding of this widely studied optimization method.

Could you extend the analysis to anytime stepsize that does not depend on TT ?

See the above reply.

On page 3, I believe it's better to mention you are dealing with convex problems at the very beginning.

Thank you for your comments. We have revised our manuscript so that we mention that we consider the convex problem at the beginning of Section 3.

Reference

[1] Nesterov. Lectures on convex optimization. In Springer, 2018.

Thanks for the response. However, I'm not convinced that the descent lemma cannot help improve the rate. Here I give a concrete example for ν=1\nu = 1 where the log⁡T\log T dependence can be improved. According to generative AI tools, this analysis extends to ν∈(0,1]\nu \in (0, 1].

Given the update

\qquad k=1,\ldots,K-1,$$ we have, for any $u$, that $$\\|x^{k+1}-u\\|^2 \leq \\|x^k-u\\|^2 -2\eta\frac{f(x^k)-f(u)}{\\|\nabla f(x^k)\\|} +\eta^2.$$ Taking $u=x^{\star}$ and telescoping, we get $$\sum_{k=s}^{K-1} \frac{f(x^k)-f(x^{\star})}{\\|\nabla f(x^k)\\|} \leq \frac{\\|x^s-x^{\star}\\|^2}{2\eta} +\frac{\eta}{2}(K-s).$$ By the descent lemma, we have $$f(x^{k+1})\leq f(x^k)-\eta\\|\nabla f(x^k)\\| +\frac{L\eta^2}{2}.$$ Telescoping again gives $$\sum_{k=s}^{K-1}\\|\nabla f(x^k)\\| \leq \frac{f(x^s)-f(x^{\star})}{\eta} +\frac{L\eta}{2}(K-s).$$ By Cauchy–Schwarz, $$\begin{align} \textstyle (K-1)^2\left[\min_{1\leq k\leq K-1}f(x^k)-f(x^{\star})\right] \leq \left(\sum_{k=1}^{K-1}\sqrt{f(x^k)-f(x^{\star})}\right)^2 \leq \left(\sum_{k=1}^{K-1}\\|\nabla f(x^k)\\|\right) \left(\sum_{k=1}^{K-1} \frac{f(x^k)-f(x^{\star})}{\\|\nabla f(x^k)\\|}\right) \leq \left(\frac{f(x^1)-f(x^{\star})}{\eta} +\frac{L\eta}{2}(K-1)\right) \left(\frac{\\|x^1-x^{\star}\\|^2}{2\eta} +\frac{\eta}{2}(K-1)\right) =\mathcal{O}\left( \left(\frac{1}{\eta}+\eta(K-1)\right)^2\right). \end{align}$$ Consequently, $$\min_{1\leq k\leq K-1}f(x^k)-f(x^{\star}) =\mathcal{O}\left( \frac{1}{\eta^2(K-1)^2}+\eta^2\right).$$ Now let $i^{\star}[s]$ denote the smallest index attaining the minimum over $s,\ldots,K$. We have $$\begin{align} \textstyle \sum_{k=i^{\star}[s]}^{K-1}\\|\nabla f(x^k)\\|\leq \frac{f(x^{i^{\star}[s]})-f(x^K)}{\eta} +\frac{L\eta}{2}\bigl(K-i^{\star}[s]\bigr) \leq \frac{L\eta}{2}\bigl(K-i^{\star}[s]\bigr). \end{align}$$ Taking $u=x^{i^{\star}[s]}$ in the distance inequality and telescoping from $i^{\star}[s]$ also gives $$\sum_{k=i^{\star}[s]}^{K-1} \frac{f(x^k)-f(x^{i^{\star}[s]})}{\\|\nabla f(x^k)\\|} \leq \frac{\eta}{2}\bigl(K-i^{\star}[s]\bigr).$$ Again, by Cauchy–Schwarz, for any $1\leq s\leq K$, $$\begin{align} \textstyle \sum_{k=i^{\star}[s]}^{K-1} \sqrt{f(x^k)-f(x^{i^{\star}[s]})} \leq \sqrt{\frac{\eta}{2}\bigl(K-i^{\star}[s]\bigr) \cdot\frac{L\eta}{2}\bigl(K-i^{\star}[s]\bigr)} =\frac{\eta\sqrt{L}}{2}\bigl(K-i^{\star}[s]\bigr). \end{align}$$ Take $s^1$ so that $$s^1\in\arg\min_{1\leq k\leq\lfloor K/2\rfloor}f(x^k).$$ Then $$\sum_{k=i^{\star}[s^1]}^{K-1} \sqrt{f(x^k)-f(x^{i^{\star}[s^1]})} \leq\frac{\eta\sqrt{L}}{2}\bigl(K-i^{\star}[s^1]\bigr).$$ Set $$s^2=s^1+\left\lfloor\frac{K-s^1}{2}\right\rfloor.$$ Then $i^{\star}[s^2]\geq i^{\star}[s^1]$ and $$f(x^{i^{\star}[s^2]})-f(x^{i^{\star}[s^1]})\geq0.$$ If $i^{\star}[s^1]\geq s^2$, then $f(x^{i^{\star}[s^2]}) = f(x^{i^{\star}[s^1]})$. Otherwise, $i^{\star}[s^1]<s^2$, and $$\begin{align} \textstyle \frac{K-s^1}{2} \sqrt{f(x^{i^{\star}[s^2]})-f(x^{i^{\star}[s^1]})} \leq \sum_{k=s^2}^{K-1} \sqrt{f(x^{i^{\star}[s^2]})-f(x^{i^{\star}[s^1]})} \leq \sum_{k=i^{\star}[s^1]}^{K-1} \sqrt{f(x^k)-f(x^{i^{\star}[s^1]})} \leq\frac{\eta\sqrt{L}}{2}\bigl(K-i^{\star}[s^1]\bigr) \leq\frac{\eta\sqrt{L}}{2}(K-s^1), \end{align}$$ where the first inequality uses $K-s^2\geq(K-s^1)/2$. Dividing both sides by $K - s^1$ and taking square on both sides, we get $$f(x^{i^{\star}[s^2]})-f(x^{i^{\star}[s^1]})\leq L\eta^2.$$ Repeat the argument with $$s^{t+1}=s^t+\left\lfloor\frac{K-s^t}{2}\right\rfloor$$ until $s^T=K-1$. The number of remaining updates is halved, up to rounding, at each step, so $T=\mathcal{O}(\log K)$. Therefore, $$\begin{align} \textstyle f(x^K)-f(x^{s^1}) \leq f(x^K)-f(x^{i^{\star}[s^1]}) =f(x^K)-f(x^{i^{\star}[s^T]}) \quad+\sum_{t=1}^{T-1} \left[f(x^{i^{\star}[s^{t+1}]})-f(x^{i^{\star}[s^t]})\right] \leq\frac{L\eta^2}{2}+L\eta^2(T-1) =\mathcal{O}(L\eta^2\log K). \end{align}$$ Finally, applying the best-iterate bound to the first $\lfloor K/2\rfloor$ iterates gives $$\begin{align} \textstyle f(x^{s^1})-f(x^{\star}) =\min_{1\leq k\leq\lfloor K/2\rfloor}f(x^k)-f(x^{\star}) =\mathcal{O}\left(\frac{1}{\eta^2K^2}+\eta^2\right). \end{align}$$ Therefore, $$\begin{align} \textstyle f(x^K)-f(x^{\star}) =\mathcal{O}\left( L\eta^2\log K+\frac{1}{\eta^2K^2}+\eta^2\right) =\mathcal{O}\left( \eta^2\log K+\frac{1}{\eta^2K^2}+\eta^2\right). \end{align}$$ Taking $\eta^2=1/(K\sqrt{\log K})$ gives the last-iterate rate $$f(x^K)-f(x^{\star}) =\mathcal{O}\left(\frac{\sqrt{\log K}}{K}\right).$$

We sincerely thank the reviewer for the insightful follow-up comment and for sharing your argument. Building on your idea, we further revisited our analysis and found that Theorem 1 can be improved to the following bound, as stated in Proposition 3 of the revised manuscript:

\le \mathcal{O} \left( M_\nu \left( \frac{\|x_1-x^\star\|^2}{T} \right)^{\frac{1+\nu}{2}} (1 + \log T)^{\frac{1 - \nu}{2}} \right).$$ We will replace Theorem 1 with this sharper result in the camera-ready version and acknowledge your valuable contribution in the Acknowledgments. **We would also like to emphasize that our main contributions remain significant.** Our improved analysis establishes an $\mathcal{O}(1/T)$ last-iterate convergence rate for $\nu=1$ with a suitably tuned constant stepsize. These results generalize the last-iterate analysis of Zamani & Glineur (2025) from bounded-subgradient objectives to convex Hölder-smooth functions, including smooth functions with unbounded gradients. Note that our PEP experiments remain valid. They use the original stepsize $|x_1-x^\star|/\sqrt{T}$, rather than the improved stepsize $|x_1-x^\star|/\sqrt{T(1+\log T)}$ in Proposition 3. We will also update the experiments and their discussion in the camera-ready version. Furthermore, Theorem 2 remains unchanged: a linearly decreasing stepsize eliminates the logarithmic overhead for all $\nu\in[0,1]$, achieving the last-iterate convergence rate $\mathcal{O}(T^{-(1+\nu)/2})$. We believe these results make a meaningful contribution to understanding the last-iterate convergence of normalized gradient descent under Hölder smoothness.
Reviewer_F56cOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This work analyses normalized gradient descent, which is gradient descent but instead of the raw gradient the normalized one is used in computing the update. In particular, this work considers the behavior of normalized gradient descent on convex Hölder-smooth functions, and establish the convergence rate of the last iterate. Both constant stepsize and linearly decaying stepsize rules are considered, with constant stepsize rule matching the known rates for best iterates up to a logarithmic factor and the linearly decaying stepsize rule matching it tightly.

Critical strengths

Last iterate guarantees are meaningful results, as in a majority of practical cases the last iterate is used as the final result. Hölder-smoothness is also a meaningful topic, as the classical smoothness assumption is repeatedly reported to be too strong to hold in machine learning applications. The convergence results are, to the best of my knowledge, novel, and also quite surprising in the sense that the last iterate can match the rate of convergence of the best iterate, exactly even up to logarithmic factors.

Critical weaknesses

The analyses are limited to convex problems. The authors provide justifications of the convexity assumption, and while I do agree that the study under the convex setting has its own merits, the practical machine learning tasks being nonconvex is not an alterable fact, and thus is nonetheless a weakness. Maybe near convergence the local loss landscape could be (nearly) convex, but that does not necessarily explain how the results in the convex setting can be used to enhance our understanding of the behavior of the method in practical machine learning scenarios.

Also, the proposed stepsize requires knowledge of both the training horizon TT and the distance to the optimal point ∥∥x1−x∗∥∥\|\|x_1 - x^*\|\|. The dependence on TT is a rather mild limitation and more of a matter of taste, but the dependence on the distance is a more critical weakness, as unless there is some additional information on the global landscape of the function it is impossible to know that a priori.

Questions for authors
  1. Can the authors provide some additional defense of the convexity assumption? I am unfortunately not yet sufficiently convinced that the analysis in this work is providing useful insight beyond the convex regime, contrary to what is stated in Appendix A. Is there additional prior work showing convex optimization theory matching the behavior of neural network training other than in scheduling learning rates? And can the authors clarify which specific insights from their analysis they expect to carry over to neural network training?

  2. As mentioned in the second critical weakness above, choosing the stepsize seems to require unrealistic prior knowledge; can you elaborate on this point a bit further?

  3. Linearly decaying stepsizes are indeed often used in practice, but the decay can also be applied only to the final portion of training rather than from the beginning. What would the convergence rate be if we used constant-then-linear-decay stepsize scheduling? In particular, would the logarithmic overhead still be removed, and how would the guarantee depend on the fraction of training devoted to decay?

4 comments

We thank the reviewer for the constructive comments. We have addressed the concerns regarding the convexity assumption and the dependence of the stepsize on TT and ∥x0−x⋆∥\|x_0-x^\star\| in our rebuttal below. In particular, the newly added Theorem 3 substantially strengthens our contribution by establishing a lower bound for the prior knowledge of TT. We kindly ask the reviewer to reconsider their assessment and, if possible, adjust the score to reflect these results.

If the reviewer still has concerns, we would appreciate being informed. We will be happy to resolve them.

Can the authors provide some additional defense of the convexity assumption? [...]

Thank you for the comment. First, we argue that the standard non-convex framework can be overly pessimistic. As discussed in Appendix A, for smooth non-convex objectives, gradient descent already achieves the optimal convergence rate among first-order methods. Consequently, this non-convex setting leaves little room to explain why more sophisticated methods, such as Adam, often perform better than gradient descent in practice.

Second, convex optimization theory has traditionally served as the starting point for understanding optimization algorithms. For example, AdaGrad and Adam were initially analyzed within the convex optimization framework [1,3]. More recently, analysis under convex assumptions has also explained the benefits of practical techniques such as learning-rate scheduling (as discussed in Appendix A) and Local SGD [2]. However, despite their widespread use in practice, the theoretical benefits of these techniques in non-convex settings remain insufficiently understood. These examples demonstrate that convex analysis can provide useful insights into the behavior of optimization algorithms used in practice.

Therefore, we believe that rigorously analyzing the convergence behavior of normalized gradient descent is an important step toward understanding its properties and practical performance, including in non-convex settings. We have added this discussion to Appendix A in the revised manuscript.

Also, the proposed stepsize requires knowledge of both the training horizon TT and the distance to the optimal point ∥x0−x⋆∥\| x_0 - x^\star\|. [...]

Dependence on TT

In Theorem 3, we provide an additional lower-bound result showing that any stepsize that does not rely on prior knowledge of TT must incur logarithmic overhead.

Furthermore, we would like to clarify that assuming prior knowledge of TT is common in practical neural network training. In particular, cosine decay and linear decay are among the most widely used learning rate schedules, and both require TT. As the reviewer also acknowledges in the following comment, linearly decaying step sizes are often used in practice. Therefore, we believe that assuming prior knowledge of TT is a reasonable and practically relevant setting.

Dependence on ∥x0−x⋆∥\| x_0 - x^\star\|

We note that choosing stepsize based on ∥x0−x⋆∥\| x_0 - x^\star\| is common in the convergence analysis of optimization algorithms. Moreover, even if the stepsize is not allowed to depend on$| x_0 - x^\star|$, we can still achieve a convergence rate of O(T−1+ν2)O(T^{- \frac{1 + \nu}{2}}), albeit with a worse dependence on the initial distance (See Corollary 1). Importantly, this does not affect our main finding that normalized gradient descent with a constant stepsize incurs a logarithmic overhead, whereas a linearly decaying stepsize eliminates it.

What would the convergence rate be if we used constant-then-linear-decay stepsize scheduling? In particular, would the logarithmic overhead still be removed, and how would the guarantee depend on the fraction of training devoted to decay?

Thank you for this question. We have added Corollary 2, which analyzes a stepsize schedule that is initially constant and then decreases linearly toward the end of training. Corollary 2 shows that even when linear decay is applied only during the final portion of training, the same log-free convergence rate of O(T−1+ν2)O(T^{-\frac{1+\nu}{2}}) as full linear decay can be achieved. Thus, linear decay need not be applied throughout the entire training process to eliminate the logarithmic overhead.

Reference

[1] Kingma et. al., Adam: A Method for Stochastic Optimization, ICLR 2015

[2] Woodworth et. al., Is Local SGD Better than Minibatch SGD?, ICML 2020

[3] Duchi et. al., Adaptive subgradient methods for online learning and stochastic optimization, JMLR, 2011.

Dear Reviewer,

Thank you again for your time and effort in reviewing our paper. We believe that our rebuttal has addressed your concerns. As the discussion deadline is approaching, we would like to kindly follow up and would appreciate your feedback. If you have any remaining concerns, we would be very happy to address them.

Best regards,
The Authors

Thank you for the comments.

The new results, on the stepsizes that do not require knowledge of x⋆x^\star and the constant-then-linear-decay stepsizes, are interesting, assuming in good faith that the newly added material written by the authors is correct. There do exist convergence analyses of certain algorithms that rely on information about x⋆x^\star, but I respectfully disagree with the assertion that they are common, and I believe that those analyses are in some sense incomplete (considering that the reason we design optimization algorithms is that we don't know x⋆x^\star a priori). Hence, in the next version of the paper (which would be the camera ready version if this paper gets accepted), I suggest presenting the new version (Corollary 1) as the main result, and optionally including the current main result (which uses stepsizes depending on ∥x0−x⋆∥\|x_0 - x^\star\|) as its immediate corollary.

Yet, regarding the additional explanation on the convexity assumption and its implications, I am not sure if I am satisfied with what the authors have provided in the rebuttal. Indeed, the currently widely used set of assumptions in the study of nonconvex optimization tends to be pessimistic. However, that does not automatically validate the convexity assumption, as the loss landscape is obviously nonconvex. I agree that convex optimization provides a starting point for understanding optimization algorithms, so the claim would have been more convincing if it had been shown more clearly how these results serve as a starting point for a better understanding. What did we come to understand better? Also, as the authors mentioned optimization algorithms that are used in practice, how would understanding normalized GD help us better understand practical optimization algorithms (given that its connection to Adam or Muon requires substantial simplifications and the current study only covers deterministic algorithms)?

We thank the reviewer for the comments. We hope the following replies have addressed the reviewer's concerns and will be reflected in their final assessment. If you have any remaining concerns, we are very glad to address them.

Dependence on ∥x1−x⋆∥\| x_1 - x^\star \|

We will revise the camera-ready version of the manuscript to include Corollary 1 and the corresponding convergence rate derived from Proposition 3 in the main paper.

For a constant stepsize, the proof of Proposition 3 directly yields the convergence rate when the stepsize is AT(1+log⁡(T))\frac{A}{\sqrt{T (1 + \log (T))}}, where AA is an arbitrary positive scalar. Specifically, we obtain

\begin{align} f(x_T)-f(x^\star) \leq O\left( M_\nu A^{1+\nu} \left( 1+\frac{|x_1-x^\star|^2}{A^2} \right)^{2+\nu} \frac{(1+\log T)^{\frac{1-\nu}{2}}} {T^{\frac{1+\nu}{2}}} \right). \end{align}

For linear decaying stepsize, we have shown the convergence rate when the stepsize is (1−tT+1)AT(1 - \frac{t}{T+1}) \frac{A}{\sqrt{T}} in Corollary 1, which recovers Theorem 2 when we set A=∥x1−x⋆∥A = \| x_1 - x^\star\|.

We promise to present both in the main text in the camera-ready version.

Practical Implications of Our Analysis

Roughly speaking, our analysis suggests using a linear decay scheduler for normalized gradient descent. This demonstrates a concrete benefit of stepsize scheduling, particularly from the perspective of last-iterate convergence. Of course, our analysis does not directly cover nonconvex settings or Adam and Muon. Nevertheless, given the connections between normalized gradient descent and Adam/Muon, our analysis suggests that stepsize schedulers may also be worth using with these practical optimizers. Furthermore, our results suggest that stepsize scheduling may also be beneficial in nonconvex settings, as we show that it can improve the convergence rate over constant stepsizes even in the special case of convex optimization.

In particular, analyzing the last-iterate convergence rates of Adam and Muon, and investigating whether a linear decay scheduler is sufficient or whether more sophisticated scheduling strategies are needed, would be a very interesting and practically important research direction. Our analysis of normalized gradient descent can provide a useful starting point for exploring this direction.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.