acceptodds
Under review as a conference paper at ICLR 2027

Beyond Rate Optimality: How Polyak’s Momentum Shapes Non-Convex Optimization

Abstract

Polyak's heavy-ball momentum is widely used in deep learning, where it often accelerates training, yet its advantage is not consistently reflected in standard smooth non-convex optimization theory. Since GD and SGD already attain optimal worst-case rates, any benefit of momentum within this framework must appear at a finer level. We therefore compare worst-case bounds beyond their asymptotic order, focusing on their dependence on the momentum parameter. Many existing convergence guarantees remain unfavorable to momentum, raising the question of whether this reflects loose analyses or genuine worst-case behavior. For SGD with heavy-ball momentum (SHB), SignGD with momentum (Signum), and deterministic Muon, we show that lower bounds on the respective averaged gradient norms can exceed the upper bounds for their non-momentum counterparts over commonly used ranges of , even when each method uses its optimal constant step size. The gaps widen as increases and diverge in deterministic settings as . For GD with heavy-ball momentum (HB), we further show that the same separation persists under the best-iterate squared gradient norm. These results show that the unfavorable momentum dependence in existing guarantees cannot in general be attributed solely to loose upper bounds, suggesting that the standard framework may miss key ingredients behind momentum's practical benefits, such as alternative convergence measures, structural assumptions, or a more refined treatment of stochasticity.

Primary area:
optimization
Keywords:
Polyak's Momentum, Heavy-Ball Momentum, Non-Convex Optimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_iVKoOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies whether the unfavorable momentum dependence in standard smooth non-convex upper bounds is merely an artifact of analysis. It derives worst-case lower bounds for Stochastic Heavyball, deterministic Signum, and an exact-SVD version of Muon, and compares them with upper bounds for the corresponding non-momentum methods.

Critical strengths

The paper asks a clear and interesting question that goes beyond asymptotic rate optimality and focuses on the momentum dependence hidden in constants. The lower-bound constructions are technically substantial and cover several optimizer families rather than a single special case. The discussion is unusually careful about the gap between worst-case smooth non-convex theory and the empirical success of momentum in deep learning.

Critical weaknesses
  1. In Section 6 and Proposition 6.1, the lower bound analysis for the matrix optimizer Muon restricts weight matrices strictly to diagonal matrices. Under this assumption, Muon’s Newton-Schulz orthogonalization dynamics degenerate directly into vector-level Signum operations. Because Muon’s primary practical mechanism lies in singular value equalization and off-diagonal rotational interactions across matrix dimensions, establishing a lower bound solely on a degenerate diagonal subspace significantly weakens the representative strength of the theoretical claim regarding real-world, full-matrix Muon optimization.

  2. The worst-case lower bound construction for SHB in Theorem 4.1 relies on a discrete Rademacher noise distribution (±σ\pm \sigma). However, in practice, Rademacher noise is rarely used directly in deep learning. While the construction is mathematically valid under worst-case analysis, this specific discrete noise creates extreme, adversarial trajectory oscillations. It is unclear whether the proven lower bound scaling still holds under continuous noise distributions (e.g., isotropic Gaussian noise) or more realistic mini-batch gradient-dependent noise encountered in deep learning training.

  3. The restrictions on the momentum parameter need more explanation (such as β∈[5/6,1)\beta \in [5/6, 1) in Theorem 4.4 and β>0.863\beta > 0.863 in Theorem 5.1). The authors should clarify why these restrictions are needed.

  4. The experimental comparisons could be strengthened. It would be helpful to include comparisons with Lion and Sophia to demonstrate the effectiveness of the proposed method.

Questions for authors
  1. Theorem 4.1 considers the averaged squared gradient norm in stochastic optimization, while Theorem 4.4 establishes a best-iterate lower bound only in the deterministic setting. Can a comparable lower-bound separation be established for stochastic heavy-ball momentum under the best-iterate criterion? What are the main theoretical obstacles?

  2. The theoretical analysis assumes a constant step size and a fixed momentum coefficient within each run. Do the unfavorable worst-case comparisons persist under diminishing step sizes or time-varying momentum schedules?

3 comments

We thank the reviewer for their assessment and valuable feedback. For an overview of our main contributions and the revisions made in response to the reviews, please see our general comment.

Weaknesses

W1

We would like to clarify that restricting our lower-bound construction to diagonal matrices does not restrict the validity of the worst-case lower bound over the full matrix function class. Specifically, the quadratic objective in Proposition 6.1 is defined over the full matrix space, is LL-smooth with respect to the Frobenius norm, and satisfies the initial function-value gap condition. Under diagonal initialization, the Muon iterates remain diagonal. Therefore, Corollary 6.2 establishes a worst-case lower bound over the full class of LL-smooth matrix functions.

We agree that our construction does not capture the off-diagonal interactions of Muon. However, any upper bound over the full class of LL-smooth matrix functions must also hold for our diagonal hard instance. Therefore, obtaining a stronger worst-case guarantee by exploiting matrix structure would require additional assumptions that exclude such instances.

W2

As the reviewer acknowledges, our construction with Rademacher noise is mathematically valid under worst-case analysis. As discussed in our response to W1, a worst-case lower bound only requires an instance satisfying the stated assumptions. Furthermore, the proof of Theorem 4.1 does not depend on the specific distribution of Rademacher noise.

Specifically, in Appendix A.2, Lemma A.1 (Equation (6)) expresses each SHB iterate as a deterministic HB iterate plus a linear combination of past noise variables. The identity following Lemma A.1, E[xk2]=yk2+η2σ2∑i=0k−1dk−i2,\mathbb{E}[x_k^2]=y_k^2+\eta^2\sigma^2\sum_{i=0}^{k-1}d_{k-i}^2, only requires that the additive noise variables are independent across iterations, have zero mean, and have variance σ2\sigma^2. The subsequent analysis is based on only this equation. Therefore, the same proof and lower bound apply to independent Gaussian noise with the same variance. We have revised Section 4.1 and Appendix A accordingly, stating the noise assumption as independent, zero-mean additive noise with variance σ2\sigma^2.

Our construction can also be realized as a finite-sum minimization problem: x0=2ΔL,f(x)=1n∑i=1nfi(x),fi(x)=L2x2+aix,x_0=\sqrt{\frac{2\Delta}{L}},\quad f(x)=\frac{1}{n}\sum_{i=1}^n f_i(x),\quad f_i(x)=\frac{L}{2}x^2+a_i x, where 1n∑i=1nai=0\frac{1}{n}\sum_{i=1}^n a_i=0 and 1n∑i=1nai2=σ2\frac{1}{n}\sum_{i=1}^n a_i^2=\sigma^2. Sampling a component uniformly and independently at each iteration yields the same equation and hence the same lower bound.

W3

The numerical thresholds in our results are sufficient conditions, and we do not claim that they represent phase transitions in the optimization dynamics.

For Theorem 4.4, the condition β≥5/6\beta\ge 5/6 comes from our proof (Appendix C.6), and we do not claim that this condition is necessary for the unfavorable worst-case comparison. To further examine the effect of β\beta, we use the Performance Estimation Problem (PEP) framework, which allows us to numerically evaluate the worst-case performance of optimization algorithms over a given function class. Although these numerical results do not constitute a formal proof, Figure 4 in Appendix F shows that the worst-case best-iterate squared gradient norm of HB, minimized over the step size η\eta, increases with β\beta across the range β∈0.01,0.02,…,0.99\beta\in\\{0.01,0.02,\ldots,0.99\\}, for each T∈5,10,15,20,25,30T\in\\{5,10,15,20,25,30\\}. These numerical results show no indication of a phase transition in this range.

Similarly, for Signum, the sufficient condition β>0.863\beta>0.863 comes from comparing our lower bound with the SignGD upper bound, and we do not claim that this threshold is necessary for the unfavorable worst-case comparison or that it represents a phase transition in the optimization dynamics.

Our main result is that the worst-case lower bound for a momentum method can exceed the upper bound for its non-momentum counterpart, even after optimizing the step size separately for each method, and that this gap grows as β\beta approaches 11.

W4

We have added experiments with Lion and Sophia-G on Tiny Shakespeare (Appendix G, Figures 9, 11, and 13), covering minibatch sizes 128 and 256 and a full-batch setting. For both optimizers, β=0.9\beta=0.9 achieves lower final training loss than β=0\beta=0 in all three settings. The gradient-norm results, however, depend more on the optimizer and batch setting. For example, full-batch Lion favors β=0\beta=0 under this metric, despite the lower loss achieved with β=0.9\beta=0.9. These additions and the refined discussion are included in Section 7.1 and Appendix G of the revised manuscript.

Questions

Question 1

Our stochastic lower bound in Theorem 4.1 concerns the averaged squared gradient norm and does not imply a lower bound under the best-iterate criterion. Establishing a lower bound under the best-iterate criterion is more challenging because a single iterate with a small expected squared gradient norm can make the minimum small, even if the expected squared gradient norms at all other iterations are large. Thus, a lower bound under this criterion requires controlling the gradient norm at every iterate.

This is also why the construction in Theorem 4.4 does not directly extend to the stochastic setting. Our proof first constructs a deterministic HB trajectory and then uses interpolation conditions for LL-smooth functions to construct an objective that realizes this trajectory. With stochastic gradients, however, the iterates need not follow the prescribed trajectory. Consequently, the same interpolation construction does not guarantee that the expected squared gradient norm remains large at every iterate. A stochastic extension would therefore require a different construction that establishes such a lower bound for stochastic iterates.

Question 2

Our current results do not establish whether the unfavorable worst-case comparisons persist under diminishing step sizes or time-varying momentum schedules.

Diminishing step sizes. The proof of Theorem 4.1 relies on a linear recurrence with constant coefficients to derive a lower bound that holds uniformly over constant step sizes. With iteration-dependent step sizes, the recurrence coefficients vary over time, so the same analysis no longer applies.
For Theorem 4.4, we construct an HB trajectory for each fixed step size and verify that it satisfies the interpolation conditions for LL-smooth functions. Extending this argument to diminishing step sizes would require a new construction satisfying these conditions.
For Theorem 5.1, our proof constructs a quadratic instance where Signum follows a periodic trajectory around the minimizer. This construction relies on a constant step size, and the same periodic trajectory is not guaranteed under diminishing step sizes.

Time-varying momentum. Our proofs also rely on a constant momentum parameter. In particular, the recurrence in Theorem 4.1 and the trajectories constructed in Theorems 4.4 and 5.1 depend on this assumption. Therefore, we cannot conclude from our current results whether the unfavorable comparisons persist under general time-varying momentum schedules.

Reviewer_iVKoOpenReview ↗

I will keep the positive score

I have read all the reviews and rebuttals. Authors have addressed and clarified my concerns, and provided additional experiments supporting the results empirically. I will keep my already positive score.

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

This paper studies Polyak momentum in LL-smooth optimization, added to SGD, Signed gradient and Muon. It provides lower bound on the convergence of the algorithms, in term of gradient norm. The lower bound highlights that in some regime, momentum can yield a lower bound strictly above the upper bound of the version without momentum. Also, these lower bounds can be arbitrarily large as the momentum parameter β\beta is close to 11.

Critical strengths

To me the main strength of this paper is to quantify through lower bounds the effect of a high momentum parameter, specifically that high momentum is harmful (through the worst case paradigm). The construction in Theorem 4.4 is specifically interesting, and leads to a "best iterate"-result.

Critical weaknesses

My main concern about this work is the scope and significance. This work draws implications from its lower bound results, specifically about the fact that "standard framework may miss key ingredients behind momentum’s practical benefits". However:

  • This paper seems to somewhat reduce our current established knowledge of non-convex optimization to LL-smoothness. Other frameworks exists, for instance when assuming both gradient and Hessian are Lipschitz [1,2], and in such setting we can get improved complexity with a Heavy Ball algorithm [3,4]. So, I believe these new lower bounds in the LL-smooth regime are more technical, rather than an insight for "non-convex optimization" in general.
  • While this work discusses the stochastic aspect, most of the results holds in the deterministic setting. Yet, it is known that momentum provides a variance reduction mechanism, which is likely an important aspect of its performance. I believe this also diminishes the scope of the result.

[1] How to Escape Saddle Points Efficiently, Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, Michael I. Jordan

[2] Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent, Chi Jin, Praneeth Netrapalli, Michael I. Jordan

[3] Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε^{-7/4}) Complexity, Huan Li, Zhouchen Lin, 2022

[4] Kansei Ushiyama and Shun Sato. A restart-free accelerated algorithm for non-convex minimization: Continuous and discrete analysis

Questions for authors

Please see my remarks in the Weaknesses section.

4 comments

We appreciate the reviewer's comments and helpful suggestions. For an overview of our main contributions and the revisions made in response to the reviews, please see our general comment.

W1

We agree that the standard LL-smooth framework does not capture all non-convex optimization settings, and that stronger assumptions can lead to improved convergence guarantees. Nevertheless, the standard LL-smooth framework has been widely used in the convergence analysis of momentum methods, where unfavorable dependence on the momentum parameter has repeatedly appeared. As reviewed in Section 3, this behavior is reflected in existing upper-bound comparisons for SHB [7], Signum [8], and Muon [9], as well as in convergence bounds for Adam and AdaGrad [10]. This motivates our investigation of whether the unfavorable momentum dependence in standard LL-smooth upper bounds is merely an artifact of the analyses or reflects an intrinsic worst-case limitation.

The works cited by the reviewer provide important positive results under stronger smoothness assumptions. However, they consider algorithms that differ from the standard Polyak heavy-ball method studied in our work. Specifically, [1] studies perturbed gradient descent, [2] analyzes a variant of Nesterov's accelerated gradient method, [3] considers restarted accelerated methods, and [4] develops a restart-free method based on velocity control. Thus, these results do not directly address the unmodified Polyak heavy-ball method with a fixed momentum parameter considered here. We have added a discussion of restarted HB [3] and restart-free HB-type methods [4] to Section 1.2.

Additionally, we remark that the instances used in Theorems 4.1 and 5.1 are quadratic objectives with constant Hessians. Therefore, both lower bounds remain valid when Hessian-Lipschitzness is additionally assumed, since these instances satisfy this condition with zero Hessian-Lipschitz constant.

W2

We acknowledge that momentum can be beneficial in stochastic optimization. Indeed, prior work has shown that Signum can converge in stochastic settings where SignSGD fails to converge ([8, 11]), as we already discuss in Sections 1.2, 3.2, 5, and 7.2.

However, these stochastic benefits do not settle the question of whether momentum can exhibit unfavorable worst-case behavior in the deterministic setting. Indeed, Polyak's original heavy-ball method was shown to accelerate optimization on deterministic ill-conditioned quadratics [6], illustrating that momentum can be beneficial even without gradient noise. More importantly, even if momentum can cause slowdown on certain problems, this does not establish a quantitative worst-case separation between algorithms with and without momentum, especially when the step size is optimized separately for each method. Our results establish precisely such a separation. In the deterministic case of Theorem 4.1, the ratio of the SHB lower bound to the SGD upper bound is (1−12T)11−β2\left(1-\frac{1}{2T}\right)\frac{1}{1-\beta^2}. Furthermore, Theorem 4.4 establishes a best-iterate lower bound whose leading 1/T1/T coefficient is at least 133(1−β)\frac{1}{3\sqrt{3}(1-\beta)} times that of the GD upper bound.

More broadly, our goal is not to claim that momentum is always detrimental, but to highlight the limitations of the standard smooth non-convex worst-case framework in explaining its practical benefits. In particular, our full-batch experiments in Appendix G show that momentum variants achieve lower training loss than their non-momentum counterparts across several optimizers, even without minibatch gradient noise. We also observe improvements in gradient-norm metrics with momentum in several settings, although the results are more dependent on the optimizer and metric. Similar benefits in full-batch settings have also been observed in [5, Figure 5], comparing GD with and without momentum. These observations suggest that factors beyond noise reduction may also contribute to the practical benefits of momentum. Understanding these benefits may require additional structural assumptions or different analysis frameworks, as discussed in Section 7.

References

[1] How to Escape Saddle Points Efficiently, Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, Michael I. Jordan
[2] Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent, Chi Jin, Praneeth Netrapalli, Michael I. Jordan
[3] Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε−7/4)O(\varepsilon^{-7/4}) Complexity, Huan Li, Zhouchen Lin, 2022
[4] Kansei Ushiyama and Shun Sato. A restart-free accelerated algorithm for non-convex minimization: Continuous and discrete analysis
[5] Fu, Jingwen, et al. "When and why momentum accelerates sgd: An empirical study." arXiv preprint arXiv:2306.09000 (2023).
[6] B.T. Polyak, Some methods of speeding up the convergence of iteration methods, USSR Computational Mathematics and Mathematical Physics, 1964.
[7] Liu, Yanli, Yuan Gao, and Wotao Yin. "An improved analysis of stochastic gradient descent with momentum." Advances in neural information processing systems 33 (2020): 18261-18271.
[8] Sun, Tao, et al. "Momentum ensures convergence of signsgd under weaker assumptions." International Conference on Machine Learning. PMLR, 2023.
[9] Shen, Wei, et al. "On the convergence analysis of muon." TMLR, 2026.
[10] Défossez, Alexandre, et al. "A simple convergence proof of adam and adagrad." TMLR, 2022.
[11] Yang, Junchi, et al. "Two sides of one coin: the limits of untuned SGD and the power of adaptive methods." NeurIPS 2023.

I would like to thank the authors for their answer. I still have concerns about the general scope and significance of this paper, and I continue to believe that it may draw overly broad conclusions about nonconvex optimization based on its results. Nevertheless, I find the precise characterizations of the lower bound regarding the choice of momentum to be interesting, as a specific lower bound study of heavy ball-type methods. I am willing to raise my score to 3.

Thank you for reconsidering your assessment. In the next revision, we will clarify our contributions and their scope while avoiding overstatement.

Reviewer_fDLsOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates whether Polyak's heavy-ball momentum can improve worst-case optimization performance beyond the asymptotic convergence rates of standard gradient-based methods. The authors established lower bounds for methods including SHB, SIGNUM, and MUON. The main discovery is that the lower bounds associates with 1−β1-\beta and approaches ∞\infty when β→1\beta\to 1. Furthermore, a constant β\beta for SIGNUM and MUON establishes higher lower bounds than the upper bounds to their no-momentum counterparts.

Critical strengths

The paper address an important and interesting theoretical question. The paper is well-written and easy-to-follow. It encompasses prevalent optimization algorithms in a full, rigorously set up environment, and establish new lower bound results.

Critical weaknesses

The paper has limited contribution over known results: the result that lower bound with momentum is higher than the upper bound without momentum for GD, is not unknown and not surprising given that the trajectory is analytically solvable on quadratic losses. The gradient noises added in the paper do not fundamentally complicate the question and change the conclusion: actually for the theoretical result for SGD vs SHB, the leading terms (SGD upper bound vs. SHB lower bound) of rate O(1/T)O(1/\sqrt{T}), introduced by gradient noise, presented in the paper, actually matches, and the true worse part is a second term of rate O(1/T)O(1/T), which appears similarly in the convergence rate analysis without gradient noises.

In the new domain of Signum and MUON, the paper fail to discuss SignSGD vs Signum in a stochastic setting (and including specgd vs muon): the paper only deals with a zero gradient noise case, without further discussion over

a. does Signum converge in the lower bound case proposed in the paper?

b. what happens in the setting where SignSGD diverges while Signum converges? (in a stochastic case)

My understanding is that momentum plays two roles in the Signum with gradient noise: heavier momentum reduces gradient bias by noise (helping optimization) while slowing down optimization with sign of expected (in the worst case), so the total contribution should be a trade-off of both effects. A pure general worst-case is not very surprising given that the limit β→1\beta\to 1 incurs bad limiting dynamics, especially happening under zero gradient noise where the above benefit of momentum is ignored.

Therefore, removing gradient noise fail to answer the most important and interesting question in the topic: what is the role of momentum in practices with MUON, what is its interplay with gradient noises, and how should we pick hyperparameters. The topic is also complicated as only under careful hyperparameterizations Signum and SignSGD both can converge to establish a comparison. A worst-case conclusion is not practically helpful.

Questions for authors

Regarding a. and b. in the above weaknesses.

2 comments

We thank the reviewer for their reading and constructive feedback. For an overview of our main contributions and the revisions made in response to the reviews, please see our general comment.

Weaknesses

Comparison with Prior Results

Regarding the novelty concern, we compare our result with several related works. [5, Proposition 3] shows that there exist linear regression problems for which the performance of HB is no better than that of SGD. [6, Theorem 2.5] establishes a sample-complexity lower bound for SHB under persistent noise. [7, Theorem 2] shows that SHB can be slower than SGD when the momentum parameter approaches one jointly with the step size.

Our results differ from these existing works in the following ways:

  1. We establish a strict worst-case separation between SHB and SGD under the standard smooth non-convex assumptions, even after optimizing the constant step size separately for each method. Specifically, Theorem 4.1 establishes a lower bound for SHB under the averaged squared gradient norm, which we compare against the corresponding SGD upper bound. Corollary 4.2 identifies conditions on the noise level and fixed momentum parameter under which the SHB lower bound strictly exceeds the SGD upper bound for sufficiently large TT.
  2. We further quantify how this worst-case separation depends on the momentum parameter β\beta and show that it persists under the best-iterate criterion in the deterministic setting. In the deterministic case of Theorem 4.1, the ratio of the SHB lower bound to the SGD upper bound is (1−12T)11−β2\left(1-\frac{1}{2T}\right)\frac{1}{1-\beta^2}. Theorem 4.4 further establishes a best-iterate lower bound using a non-quadratic smooth interpolation construction. Together with Proposition 4.3, this shows that the ratio of the leading 1/T1/T coefficients of the HB lower bound and the GD upper bound is at least 133(1−β)\frac{1}{3\sqrt{3}(1-\beta)} for β∈[5/6,1)\beta\in[5/6,1). We have expanded Section 1.2 of the revised manuscript to discuss these works and clarify how our results differ from them.

Leading-Term Comparison for SHB and SGD

We agree that, for fixed β<1\beta<1 and positive noise variance, the SGD upper bound and our SHB lower bound have the same leading T−1/2T^{-1/2} coefficient, and their difference appears at order T−1T^{-1}. However, our goal is precisely to compare worst-case guarantees beyond their leading-order convergence rates. In particular, Corollary 4.2 establishes that the difference in the T−1T^{-1} terms leads to a strict separation, where the SHB lower bound exceeds the SGD upper bound, under an explicit condition on the noise level and momentum parameter. This distinction is now stated in the revised manuscript (Section 4.1).

Stochastic Sign-Based Methods

We agree with the reviewer's intuition that momentum can play two competing roles in stochastic sign-based optimization: averaging noisy gradients can help optimization, while accumulated past gradients can slow down optimization in certain cases. Indeed, prior work has shown that Signum can converge in stochastic settings where SignSGD fails to converge ([3, 4]), as we already discuss in Sections 1.2, 3.2, 5, and 7.2. Our deterministic lower bound complements these positive results.

However, this intuition does not immediately imply that momentum must slow down optimization in the deterministic setting. For example, Polyak's original heavy-ball method was shown to accelerate optimization on deterministic ill-conditioned quadratics [8], illustrating that momentum can be beneficial even without gradient noise. More importantly, even if momentum can cause slowdown on certain problems, this does not establish a quantitative worst-case separation between algorithms with and without momentum, especially when the step size is optimized separately for each method. Our Theorem 5.1 proves that the worst-case lower bound for Signum exceeds the upper bound for SignGD when β>0.863\beta > 0.863, even after optimizing the constant step size separately for each method. Moreover, the separation grows as Ω((1−β)−1/4)\Omega((1-\beta)^{-1/4}) as β→1\beta \to 1. Establishing such a lower bound is highly nontrivial, particularly because Signum is sensitive to the choice of step size.

More broadly, our goal is not to claim that momentum is always detrimental, but to highlight the limitations of the standard smooth non-convex worst-case framework in explaining its practical benefits. In particular, our full-batch Tiny Shakespeare experiments (Appendix G) show that momentum improves training loss across several optimizers, even without stochastic gradient noise. Similar benefits in full-batch settings have also been observed in [1, 2]. These observations suggest that factors beyond noise reduction may also contribute to the practical benefits of momentum. Understanding these benefits may require additional structural assumptions or different analysis frameworks, as discussed in Section 7.

We agree that understanding the interplay between momentum and stochastic noise, as well as its implications for practical hyperparameter choices, is an important direction. However, our contribution here is to establish a quantitative worst-case limitation of momentum under the standard framework, rather than to fully characterize this interplay.

Questions

Question a

Our lower-bound instance satisfies the assumptions of [3], including smoothness and bounded variance. Therefore, their Theorem 1 guarantees convergence of Signum on our instance with the parameter choices η=1/(LT3/4)\eta=1/(LT^{3/4}) and β=1−1/T\beta=1-1/\sqrt{T}.

Question b

As discussed above under Stochastic Sign-Based Methods, in such stochastic settings, momentum can indeed enable convergence when SignSGD fails to converge. Specifically, [4] provides a one-dimensional non-convergence example for SignSGD, while [3] establishes convergence guarantees for Signum under smoothness and bounded variance assumptions. In fact, we already discuss these results in Sections 1.2, 3.2, 5, and 7.2. Our deterministic lower bound in Theorem 5.1 does not contradict these stochastic results, as it concerns a different setting.

References

[1] Kunstner, Frederik, et al. "Noise is not the main factor behind the gap between sgd and adam on transformers, but sign descent might be." ICLR 2023.
[2] Song, Minhak, Kwangjun Ahn, and Chulhee Yun. "Does SGD really happen in tiny subspaces?" ICLR 2025.
[3] Sun, Tao, et al. "Momentum ensures convergence of signsgd under weaker assumptions." ICML 2023.
[4] Yang, Junchi, et al. "Two sides of one coin: the limits of untuned SGD and the power of adaptive methods." NeurIPS 2023.
[5] Kidambi, Rahul, et al. "On the insufficiency of existing momentum schemes for stochastic optimization." 2018 Information Theory and Applications Workshop (ITA). IEEE, 2018.
[6] Ganesh, Swetha, et al. "Does Momentum Help in Stochastic Optimization? A Sample Complexity Analysis." Uncertainty in Artificial Intelligence. PMLR, 2023.
[7] Deng, Xiaoge, et al. "Exploring the Inefficiency of Heavy Ball as Momentum Parameter Approaches 1." IJCAI. 2024.
[8] B.T. Polyak, Some methods of speeding up the convergence of iteration methods, USSR Computational Mathematics and Mathematical Physics, 1964.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Comment

We thank all reviewers for their time and detailed feedback. Below, we summarize the main contributions of our work and the key revisions made in response to the reviews.

Key Contributions

Our work examines whether the unfavorable momentum dependence in standard smooth non-convex worst-case guarantees is merely an artifact of existing upper-bound analyses or can arise in worst-case performance. We establish lower bounds for SHB, Signum, and the exact-SVD version of Muon, and compare them with upper bounds for their non-momentum counterparts after optimizing the constant step size separately for each method. For deterministic HB, we additionally establish a best-iterate lower bound. These results go beyond asymptotic rates by showing that, under the stated assumptions and convergence criteria, momentum can yield worse worst-case guarantees over specific parameter regimes, with an explicit dependence on the momentum parameter.

These are worst-case results within the function classes, algorithms, and convergence criteria studied in our work. They do not imply that momentum is generally harmful or that our lower-bound instances represent typical training dynamics. At the same time, momentum also has established benefits in other settings, including Polyak's classical acceleration result for ill-conditioned quadratic objectives and stochastic convergence guarantees for sign-based methods. Our full-batch experiments further demonstrate benefits of momentum across several optimizer-metric combinations. The broader message is that standard smooth non-convex worst-case analysis may not capture all the factors underlying these practical benefits. As discussed in Section 7, this motivates exploring alternative convergence criteria, additional structural assumptions, and more refined treatments of stochasticity.

Summary of Revision

  • Clarified the SHB lower-bound construction and its comparison with SGD (Section 4.1 and Appendix A). We removed the unnecessary Rademacher noise restriction, specifying independent additive noise with zero mean and variance σ2\sigma^2. We also explicitly state that, for fixed β<1\beta<1 and positive noise variance, the SGD upper bound and our SHB lower bound share the same leading T−1/2T^{-1/2} term, with their asymptotic separation determined by the T−1T^{-1} terms.
  • Expanded the related work section (Section 1.2). We added results on restarted HB and restart-free HB-type methods under Lipschitz gradient and Hessian assumptions. We also clarified that our results establish regimes where lower bounds for momentum methods exceed upper bounds for their non-momentum counterparts with optimally tuned constant step sizes, and quantify the dependence of this separation on the momentum parameter.
  • Expanded experiments and refined their discussion (Section 7.1 and Appendix G). We added Lion and Sophia-G experiments on Tiny Shakespeare in both minibatch and full-batch settings. We also clarified that momentum generally improves training loss and often improves averaged gradient norms, while the latter comparison varies across optimizers and batch sizes.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.