- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies the preconditioning effect of exact-polar Muon in symmetric matrix factorization and an infinite-prompt Gaussian softmax-attention model. It establishes logarithmic iteration complexity, independent of the condition number, for each fixed momentum parameter. The paper proves lower bounds for a coordinatewise gradient-history class that includes full-batch Adam, along with a matched local separation between Muon and stabilized Adam. Synthetic experiments support the theoretical claims.
Critical strengths
- The paper delivers a theoretical characterization of spectral orthogonalization and undercomplete matrix factorization. The analysis shows that normalizing spectral updates can eliminate dependence on the condition number, clarifying the mechanism in Muon’s preconditioning.
Critical weaknesses
-
The guarantee on the general matrix factorization is limited. Table 1 suppresses , which the sufficient positive-momentum conditions (in Appendix B.3) force to be extremely large as gets closer to 1; the value is lower bounded by . These restrictions limit what the logarithmic iteration bound explains about training with practical schedules.
-
The comparison with Adam remains restricted. Though the paper provides a matched comparison in a particular regime (Table 1), the main lower bounds use different initializations from the Muon upper bounds.
Questions for authors
-
Could Table 1 explicitly include the dependence on and its admissible range depending on ?
-
Equation 31 gives an initialization scale for the undercomplete guarantee, which depends on the accuracy level . How much of this dependence is necessary for the dynamics? Could the authors either explain this sensitivity or provide experimental results?
-
How robust are the Adam lower bounds to small perturbations in the initializations? Do these lower bounds hold with non-negligible probability under a random initialization scheme? Can a comparable bound be derived under the initializations assumed in the Muon upper bounds?
2 comments
Thank you for your clarification. The authors' response addressed my questions, hence I raise my score to 3 (weak accept).
Response to Reviewer oQLB
Thank you for these questions. We have made the schedule dependence explicit, examined initialization sensitivity, and clarified what the Adam lower bounds establish.
1. Dependence on ρ and μ. We agree that hiding 1/(1−ρ) obscured an important limitation. Table 1 now reports (1+log(1/ε))/(1−ρ) and the admissible decay ranges. For example, at μ=0.9 the general matrix-factorization proof requires 1/(1−ρμ)≃3.42×109, while the experiments use ρ=0.98 (giving 50). Thus the general theorem does not explain that practical schedule. The ICL theorem and the matched local comparison admit faster decay; we distinguish these results in the Discussion.
2. Accuracy-dependent initialization in undercomplete factorization. The requirement that the starting scale shrink with ε is sufficient, not known to be necessary. Our proof controls the accumulated alignment error until the decaying steps become smaller than the desired tolerance; finer accuracy requires a longer tracking horizon and hence a smaller certified initial scale (Appendix B.1). We cannot yet prove convergence to arbitrary accuracy from one fixed undercomplete start. However, in 160 sensitivity runs using a common schedule across four starting scales, two widths, and two condition numbers, every run reached and sustained 10−7 error within 2,000 updates (Appendix L.3). This suggests the sufficient condition may be conservative.
3. Are the Adam lower bounds caused by poor initialization? No: the constructions deliberately start near a true solution. With unrestricted initialization, an algorithm might stall at a saddle point or in an invariant low-dimensional subspace; that would say little about its local convergence rate. Our lower bounds avoid this issue:
We agree that these broader lower bounds use different starts and error criteria from the Muon upper bounds; they are not direct matched comparisons. That is why we also added Proposition 6: for any prescribed neighborhood of an optimum, it constructs a common factorization instance and initialization on which Muon needs Oμ(logκ+log(1/ε)) iterations but stabilized Adam requires Ω(κlog(1/ε)). The Adam result assumes a positive stabilizer and bounded scalar rates, which we state explicitly.
Robustness to perturbations. Theorem 2 uses exact zero-gradient histories, so its support-based proof does not extend directly to dense perturbations or isotropic random starts. For the matched Adam result, Appendix J.4 shows that the finite-horizon lower bound persists in some Frobenius ball around the constructed initialization, uniformly over bounded scalar-rate schedules. We do not quantify that ball's probability under standard random initialization or claim a matched Muon guarantee throughout it.