- 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
-
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.
-
The worst-case lower bound construction for SHB in Theorem 4.1 relies on a discrete Rademacher noise distribution (). 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.
-
The restrictions on the momentum parameter need more explanation (such as in Theorem 4.4 and in Theorem 5.1). The authors should clarify why these restrictions are needed.
-
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
-
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?
-
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
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 -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 -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.
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.
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 L-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 L-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 L-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, only requires that the additive noise variables are independent across iterations, have zero mean, and have variance σ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.
Our construction can also be realized as a finite-sum minimization problem: x0=L2Δ,f(x)=n1∑i=1nfi(x),fi(x)=2Lx2+aix, where n1∑i=1nai=0 and n1∑i=1nai2=σ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 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 β, 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 η, increases with β across the range β∈0.01,0.02,…,0.99, for each T∈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 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 β approaches 1.
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 achieves lower final training loss than β=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 under this metric, despite the lower loss achieved with β=0.9. These additions and the refined discussion are included in Section 7.1 and Appendix G of the revised manuscript.