acceptodds
Under review as a conference paper at ICLR 2027

Provably Finding Low Neural Loss via Spectral-GD

Abstract

Optimizers of the Muon family are rapidly becoming a competitive alternative to the standard adaptive methods for training LLMs. Such optimizers update the training parameters exploiting the intrinsically rich geometry of the space of the architectural weight matrices. In this work we do a first-of-its-kind analysis of Spectral-GD - the full-batch, momentum-free core of Muon - to show that it can provably train a shallow ReLU net in the large width regime. In terms of any set accuracy target and failure probability over random initialization, we give explicit estimates for the required width, step-length and number of iterations to reach the accuracy target. Our work rigorously establishes the surprise that gradient direction information, in the matrix sense, can be enough to train wide nets.

Primary area:
optimization
Keywords:
Spectral GD, Matrix Optimizers, Neural Net, Gradient Descent, Optimization Theory

Reviews

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

Spectral-GD replaces a weight-matrix gradient with its polar factor and can be viewed as a full-batch, momentum-free simplification of Muon. The paper analyzes Spectral-GD under the empirical squared loss of a two-layer ReLU network with randomly initialized and fixed second-layer weights, in the neural tangent kernel (NTK) regime. The paper derives a non-asymptotic training guarantee for Spectral-GD to achieve a prescribed training-loss accuracy, with explicit bounds on the required network width, step size, and number of iterations. Experiments on synthetic networks and language models provide additional empirical evidence.

Critical strengths
  1. Timely and relevant theoretical problem. The paper addresses an important question motivated by the growing use of Muon-family optimizers in LLM training: whether the polar-factor gradient update can provably reduce neural-network training loss despite discarding singular-value magnitude information.
  2. Careful treatment of ReLU activation changes. The analysis explicitly handles activation-boundary cases and controls the linearization error caused by changing ReLU gates, rather than assuming that the activation patterns remain fixed throughout training. This strengthens the technical treatment of the non-smooth network.
Critical weaknesses
  1. Gap between the theorem statement and its proof. Theorem 3.1 (Eq. 9) claims that the empirical loss remains below the target threshold for all t≥Tt \geq T. However, Step 3 of the proof only establishes that the iterates remain within the neighborhood B\mathcal B for 0≤t≤T0\leq t\leq T, and the descent argument is only applied within this finite horizon. Step 5 therefore appears to establish the guarantee at iteration TT, rather than for all subsequent iterations. Could the authors clarify how the required neighborhood and kernel conditions are maintained beyond TT, or otherwise weaken the theorem statement to match the proved result?
  2. Extremely conservative width requirement. Although the paper improves the sufficient width scaling from n6n^6 to n5n^5 relative to the cited GD analysis, the explicit constant in Appendix D.2 (Eq. 45) appears to make the guarantee quantitatively vacuous. Substituting the parameters reported for the synthetic experiment (n=20n=20, B≈1.68B\approx1.68, α=1\alpha=1, δ=0.05\delta=0.05, and λ0≈0.32\lambda_0\approx0.32) yields a sufficient width of approximately 9.4×10239.4\times10^{23}, whereas the experiment uses m=1000m=1000. The authors should discuss this enormous gap and clarify the practical interpretation of the theoretical width improvement.
Questions for authors
  1. Unclear role of the spectral transformation. The theoretical analysis establishes that Spectral-GD can achieve low training loss under the stated assumptions. However, it remains unclear which parts of the guarantee specifically depend on the polar-factor transformation, as opposed to more general normalized-gradient updates.
2 comments

We thank the reviewer for their detailed feedback. We present the following responses to the key issues raised. All revisions made in response to the reviewers’ comments are highlighted in blue in the updated manuscript.

W1. ...weaken the theorem statement to match the proved result

Response. Thanks for the spotting the typo in the theorem statement; and it is corrected in the updated uploaded file. Theorem 3.1 now states L(WT)≤εL(\mathbf{W}_T)\le\varepsilon (Eq. 9), as does Section 1. The iterates stay in B\mathcal B for t≤Tt\le T (Eqs. 26--27), and Step 5 runs over t⋆≤t<Tt^\star\le t<T, where both endpoints lie in B\mathcal B, so Lemma 4.3 gives L(Wt)≤εL(\mathbf{W}_t)\le\varepsilon on [t⋆,T][t^\star,T]. Also a general version of the Theorem 3.13.1 has been given in Appendix A as Theorem A.3

W2. .....The authors should discuss this enormous gap

Response. The width in (7) is a worst-case sufficient condition. The first NTK bounds for GD had similar character (n6/(λ04δ3)n^6/(\lambda_0^4\delta^3) in Du et al.), and were later reduced to scale as n4n^4 by Song & Yang (2019) --- which is the same scaling with nn as encompassed by our general Theorem A.3 that applies to a class of algorithms.

This philosophy of neural net theory can be traced back to the work since Neal (1996) who had argued qualitatively about large width limits being analytically trainable. Our work can be seen as the latest embodiment of that philosophy in the context of the most modern optimizers.

The width sweep (new Figure 3, m∈{500,…,8000}m\in\{500,\dots,8000\}) evidences the mechanism of the proof, shrinking gate changes and unit movement, already at mm in the hundreds.

Q1. Unclear role of the spectral transformation.

Response. New Theorem A.3 (Appendix A) gives a generalization of the claimed main theorem 3.1 which is specific to spectral-GD. The general theorem clarifies that three properties of the direction matrix Dt{\bf D}_t are important, (1) ⟨Gt,Dt⟩≥∥Gt∥F\langle {\bf G}_t,{\bf D}_t\rangle\ge\|{\bf G}_t\|_F , (2) ∥Dt∥2≤1\|{\bf D}_t\|_2\le1, and (3) ∥Dt∥F≤ρ\|\mathbf{D}_t\|_F\le\rho. Theorem A.3 shows that every update rule with these properties gets L(WT)≤εL(\mathbf{W}_T)\le\varepsilon with the same η\eta and TT as for Spectral-GD and the second term of the width bound (Eq. 46) ∝ρ2n4\propto\rho^2n^4; Spectral-GD corresponds to ρ=n\rho=\sqrt n.

Thank you for the detailed response and for tightening the paper’s claims. The revisions make the paper more rigorous and complete, even though they narrow the scope of the theoretical guarantees.

I am keeping my rating at 2, and I lean toward rejection. But since my work focuses primarily on the practical use and stability of optimizers, and my confidence rating of 2 reflects my limited expertise in the theoretical analysis at issue here, I would not argue against it If the AC recommends acceptance.

This year’s four-point scale is too coarse to convey that distinction. Given that I have heard that roughly two-thirds of submissions received a rating of 2, I wanted to state my position explicitly in writing. I would appreciate it if the AC considered this clarification carefully when weighing my review.

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

The paper analyzes Spectral-GD, the full-batch, momentum-free version of Muon with update W←W−ηPolar(∇L(W))W \leftarrow W - \eta \text{Polar}(\nabla L(W)), on a two-layer ReLU network with fixed random second layer and a trained first layer. In the NTK setting of Du et al. (2018b), it proves that for width m=Ω(n5/(λ04δ3))m = \Omega(n^5/(\lambda_0^4 \delta^3)), step size η=Θ(λ0ε/n)\eta = \Theta(\sqrt{\lambda_0 \varepsilon}/n) and T=O(n3/2/(λ0εδ))T = O(n^{3/2}/(\lambda_0 \sqrt{\varepsilon \delta})) iterations, the training loss is at most ε\varepsilon with probability 1−δ1-\delta over initialization. The proof follows the NTK template. Initialization events control the kernel and the number of near-boundary neurons. A uniform kernel and remainder bound holds on a Frobenius ball around W0W_0. The residual then shrinks by a fixed amount per step until it reaches the target level and stays there. The paper notes that its width requirement is lower than the n6n^6 of Du et al. but the rate is O(1/ε)O(1/\sqrt{\varepsilon}) instead of geometric. Validation consists of a synthetic experiment (n=20, d=100, m=1000), and LLM experiments comparing Spectral-GD with AdamW (fine-tuning Qwen models) and with Muon (pretraining Pythia-70M and modded-nanogpt).

Critical strengths

The proofs of the lemmas are, as far as I could verify, arithmetically correct, but as stated, the proof of the main result is incomplete, because it does not seem to cover t>Tt > T.

Critical weaknesses
  1. The result does not say anything specific about Spectral-GD or Muon, and the claims are framed as if it did. It is also compared against old baselines.

    • The descent step uses only ⟨G,Polar(G)⟩=∣G∣∗≥∣G∣F\langle G, Polar(G)\rangle = \\|G\\|_* \geq \\|G\\|_F and the step bounds ∣ΔW∣2≤η\\|\Delta W\\|_2 \leq \eta, ∣ΔW∣F≤nη\\|\Delta W\\|_F \leq \sqrt{n} \eta. With the normalized gradient G/∣G∣FG/ \\|G\\|_F, the same argument seems to go through, with Frobenius step η\eta, and gives width n4n^4. So the spectral structure appears to only cost a factor n\sqrt{n}.
    • The n5n^5 versus n6n^6 comparison says little. It is against a 2018 baseline, and nothing ties the gain to the update rule. I believe later analyses (for example Song & Yang 2019 "Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound", arXiv:1906.03593) report lower widths, and the authors should compare with them. The explanation that the slower rate comes from discarding the gradient's magnitude also has no support.
    • Because this is the NTK regime, any descent direction with enough alignment trains the net, so the conclusion that "the surprise that gradient direction information, in the matrix sense, can be enough to train wide nets" is not really a surprise. The statement "first guarantee for Spectral-GD in any non-convex setting" are not supported. The last also conflicts with the paper’s own citation of Chen et al. and with standard steepest-descent results. The main message of the abstract does not follow from the theorem.
    • The "counterpoint to Shumaylov et al." framing does not seem to be fully correct. Their claim is that exact spectral geometry does not explain Muon's performance. A convergence proof that works for any normalized direction is compatible with that claim and even supports it.
  2. The theorem is stated more strongly than it is proven, and the novelty claim is false.

    • Eq. (9) claims L(Wt)≤εL(W_t) \leq \varepsilon for all t≥Tt \geq T, but in the proof, the iterates are only controlled up to T. Each step can move Frobenius distance nη\sqrt{n} \eta, so the displacement bound grows linearly in t and leaves the ball B\mathcal{B} eventually. Nothing controls WtW_t for t>Tt > T. The experiment shows the loss staying below ε\varepsilon up to T, but the theorem as written is not proven.
    • The novelty claim is false. The introduction says “For Spectral-GD itself, no non-asymptotic convergence guarantee has been established in any non-convex setting prior to this work”. However, this is not true, and there do exist numerous prior works with the corresponding proofs. As Theorem A.1 shows Spectral-GD is a spectral-norm LMO step. Rates for LMO and Muon-type methods on smooth non-convex objectives already exist. Also, standard steepest-descent analysis gives such a rate directly. Only the narrower claim (a global training-loss guarantee in the NTK regime) is defensible. Prior LMO analyses are not discussed in the literature review.

I also have major concerns about the experiments. More on this in the section below.

Questions for authors
  1. The experiments claim to use full gradients for training LLMs. However, literally using full-batch gradients seems infeasible for the FineWeb pretraining runs involving 15T tokens. The experiments presumably use minibatches, in which case the description of the method as full-batch is inaccurate. This would mean that the experiments evaluate a stochastic, momentum-free polar update, which is not covered by the theorem. If so, the close alignment between Muon and momentum-free Muon in Figure 1 is rather suspicious. Could the authors explain the experimental setup?
  2. There are several other aspects of the experimental results that need clarification. In Figures 1(c) and 1(d), why is the initial loss approximately 4.25 for both models? Why is the training loss in Figure 1(d) substantially lower than the validation loss? Which parameters are updated by Spectral-GD? Why is Muon trajectory in Figure 1(d) truncated at 1000 steps?
  3. Eq. (9) says L(Wt)≤εL(W_t) \leq \varepsilon for all t≥Tt \geq T. Where is it shown that iterates stay in B\mathcal{B} beyond T?
  4. What is the explicit constant in the width requirement (7)? Can the theorem be stated without Ω\Omega inside a max?
  5. The synthetic run uses m=1000m=1000, while the theorem requires m of order 102410^{2^4} for these parameters. Can you show how behavior changes with mm?
  6. How were the hyperparameters tuned?

Overall, I have serious concerns about the reliability and reproducibility of the experimental results, and I do not find the current presentation sufficient to resolve them. The paper also contains numerous presentation and citation issues. For example, "Polar Express (?)" - unresolved reference, Du et al. (2018b) and Du et al. (2018c) refer to the same arXiv paper (1810.02054), yet Appendix E attributes different content to the them, Qwen-1.5 is cited using the Qwen3 report, some sentences have no terminating periods, section references are incorrect, and the Muon trajectory in Figure 1(d) is truncated. Taken together, these issues undermine my confidence in the paper's claims and suggest that it is far from being ready for publication.

4 comments

We thank the reviewer for their detailed feedback. We present the following responses to the key issues raised. Note: All revisions made in response to the reviewers’ comments are highlighted in blue in the updated manuscript.

W1. The theorem is stated more strongly than it is proven.

Response. Thanks for the spotting the typo in the theorem statement; and it is corrected in the updated uploaded file. Theorem 3.1 now states L(WT)≤εL(\mathbf{W}_T)\le\varepsilon (Eq. 9), as does Section 1. The iterates stay in B\mathcal B for t≤Tt\le T (Eqs. 26--27), and Step 5 runs over t⋆≤t<Tt^\star\le t<T, where both endpoints lie in B\mathcal B, so Lemma 4.3 gives L(Wt)≤εL(\mathbf{W}_t)\le\varepsilon on [t⋆,T][t^\star,T]. Also a general version of the Theorem 3.13.1 has been given in Appendix A as Theorem A.3.

W2. ...anything specific about Spectral-GD or Muon

Response. New Theorem A.3 (Appendix A) gives this general theorem that the reviewer has guessed correctly. The proof uses the direction Dt{\bf D}_t only through three properties, (1) ⟨Gt,Dt⟩≥∥Gt∥F\langle {\bf G}_t,{\bf D}_t\rangle\ge\|{\bf G}_t\|_F, (2) ∥Dt∥2≤1\|{\bf D}_t\|_2\le1, (3) ∥Dt∥F≤ρ\|{\bf D}_t\|_F\le\rho, and any such update reaches L(WT)≤εL({\bf W}_T)\le\varepsilon with the same η\eta and TT as Theorem 3.1, provided the width satisfies a ρ\rho dependent condition (Eq. 46).

Please refer to Table 22 on page 77 which gives the mapping which reduces the general theorem(A.1) to the theorem 3.13.1 of the main paper.

W3. The n5n^5 versus n6n^6 comparison says little

Response. The review in our Section 1 now cites the mentioned Song & Yang (2019) result. Widths from different proofs are sufficient conditions and are presented as such. On the rate: in our bound T∝1/εT\propto1/\sqrt\varepsilon because each step lowers the residual by a fixed amount αηλ0/4\alpha\eta\sqrt{\lambda_0}/4 (Eq. 29) rather than a fixed fraction, and the term nα2η2n\alpha^2\eta^2 in Eq. 28 does not shrink with the residual, which forces η∝ε\eta\propto\sqrt\varepsilon. Both are consequences of the step having fixed length, independent of the gradient's magnitude - which is the hallmark of these modern neural optimizers which we are explaining.

W4. The novelty claim is false.

Response. Our claim concerns reaching a prescribed training loss of a neural network, which none of the following former results give :

Li & Hong (2025) (Thms. 2.1, 3.1), Pethick et al. (2025) (Thms. 5.4--5.7), Kovalev (2025) (Thms. 1, 2, 5) and Chen et al. (2025) (Thms. 3--6).

These results bound a gradient norm, a Frank--Wolfe gap or a KKT residual of an LL-smooth objective.

The only results on the objective value are, Shen et al. (2025) (Thms. 4.5, 4.6, 4.9, 4.10, 4.16) and Kovalev (2025) (Thms. 3, 4, 6--8), and these assume star-convexity.

The squared loss of a ReLU network is neither smooth nor star-convex, and its stationary points need not have low loss. We have stated the claim in these terms and cite these works in Section 1 to establish that this work is the first provable neural training by spectral methods.

W5. The main message of the abstract does not follow

Response. The surprise is not about the alignment but the absence of magnitude information. The update sets every singular value of the gradient to one, so the step does not shrink as the loss falls. For GD the NTK argument is self-correcting, because the step vanishes with the residual; for Spectral-GD it is not, and the iterates must be controlled over a fixed budget paid for in width. That such a step still reaches any prescribed loss, with explicit width, step size and number of steps, is the content of the abstract's sentence.

W6. The “counterpoint to Shumaylov et al.” framing

Response. Shumaylov et al. (2026) do not question that Muon trains; Muon is their baseline. They show empirically that its exact spectrum is not what explains its performance: random (Kaon) or quasi-norm (Freon) singular values with Muon's singular vectors match Muon on GPT-2 124M. Their theory (Thms. 2.3, 2.5) gives convergence to a stationary point of a smooth objective, for the update X−α⟨G,D⟩DX-\alpha\langle G,D\rangle D, whose step keeps the size of the gradient. It therefore covers neither Spectral-GD, whose step has fixed length, nor the loss of a ReLU network and neither do they establish training.

Our result answers this different/harder question of loss minimization on a non-convex non-smooth landscape, and Theorem A.3, which does not single out the polar factor, is consistent with their finding. We will phrase the sentence as complementary to their work.

(Continued in the next comment)

W7. reliability and reproducibility of the experimental results

Response. We address each of these points below: the full-batch setup and the dataset in Q1; the initial loss, the training/validation gap, the updated parameters and the truncated Muon curve (now complete in the revised Figure 1(d)) in Q2; the dependence on the width in Q5; and the hyperparameters in Q6. The code is in the footnote on page 4.

W8. Presentation and citation issues:

Response. Thanks for pointing these out. All of these are fixed in the updated uploaded draft.

Q1. Can the authors explain the experimental setup?

Response. We thank the reviewer for raising this concern. Our Pythia-160M and modded-nanogpt pretraining experiments use a fixed subset of the nampdn-ai/mini-fineweb dataset on Hugging Face, not the complete FineWeb corpus. We split it 70/30: 70% is used for training and the remaining 30% only for validation. Both models are trained with full-batch gradients over this fixed training partition. At each iteration we accumulate gradients across microbatches, without updating the parameters, until the entire training partition has been processed, and then apply a single optimizer update with the accumulated full gradient. This is repeated for 5,000 iterations. Muon is run on the same full-batch gradients; it differs from Spectral-GD in its Nesterov momentum (0.950.95) and in computing the polar factor approximately, by Newton--Schulz iteration, instead of by an exact SVD. Thus full-batch refers to the gradient over the entire fixed training partition; gradient accumulation makes this memory-efficient while preserving the full-batch update. The link to our anonymized code is now given in the footnote on page 4.

Q2. Why is the Muon trajectory in Figure 1(d) truncated

Response. Initial loss. Both models are trained on the same character-level vocabulary of V=65V=65 symbols, and both are initialized from the same distribution: every weight matrix is drawn i.i.d. from N(0,0.022)\mathcal N(0,0.02^2), and the output layer is preceded by a normalization layer. With high probability over this random draw, every output logit is therefore close to zero, with standard deviation about 0.02768≈0.550.02\sqrt{768}\approx0.55, so the predicted next-character distribution is nearly uniform over the VV symbols, whatever the particular draw. The initial cross-entropy then concentrates at about ln⁡V+0.552/2=ln⁡65+0.15≈4.3\ln V+0.55^2/2=\ln65+0.15\approx4.3, which is the starting value of both curves. It depends only on the vocabulary and the initialization scale, which the two models share, and not on their depth or width (Pythia: 12 layers, width 768; modded-nanogpt: 11 layers, width 768). Training vs. validation. The fixed training subset is used at every step, so after 50005000 full passes the model fits it more closely than held-out text. Parameters. Spectral-GD updates all parameters except the biases, which are trained with AdamW. Truncated Muon. Thank you for catching this plotting error. All three Muon seeds in Figure 1(d) were trained and evaluated for the full 50005000 iterations, as the training-loss panel shows; because of an error when we generated the figure, only the first part of Muon's validation curve, up to k=1000k=1000, was plotted. Over the full run, Muon's validation loss stays within one standard deviation of Spectral-GD's (mean ±\pm std over 3 seeds, Muon vs. Spectral-GD):

kk1000100020002000300030004000400050005000
Muon3.081±0.0203.081\pm0.0203.058±0.0163.058\pm0.0163.030±0.0293.030\pm0.0293.009±0.0373.009\pm0.0372.983±0.0382.983\pm0.038
Spectral-GD3.103±0.0313.103\pm0.0313.073±0.0153.073\pm0.0153.032±0.0083.032\pm0.0082.995±0.0142.995\pm0.0142.979±0.0252.979\pm0.025

The revised Figure 1(d) in the manuscript now shows the complete validation curves for both optimizers.

Q3. Where is it shown that the iterates stay in BB beyond TT?

Response. Thanks for the spotting the typo in the theorem statement; and it is corrected in the updated uploaded file. Theorem 3.1 now states L(WT)≤εL(\mathbf{W}_T)\le\varepsilon (Eq. 9), as does Section 1. The iterates stay in B\mathcal B for t≤Tt\le T (Eqs. 26--27), and Step 5 runs over t⋆≤t<Tt^\star\le t<T, where both endpoints lie in B\mathcal B, so Lemma 4.3 gives L(Wt)≤εL(\mathbf{W}_t)\le\varepsilon on [t⋆,T][t^\star,T]. Also a general version of the theorem 3.13.1 has been given in Appendix A as Theorem A.3.

Q4. Can the theorem be stated without Ω\Omega inside a max?

Response. Yes. Eq. 7 now gives the explicit constants. The generalized version in Theorem A.3 also reports the exact constants.

(Continued in the next comment)

Thank you for the detailed rebuttal and the revisions. The corrections address several of my concerns, but two main issues remain.

First, Theorem A.3 shows that the analysis is not specific to the polar factor. The proof uses only that the step is aligned with the gradient and has bounded norm. The normalized gradient also satisfies this, and the analysis gives it a smaller width requirement. The extra alignment of the polar factor is not used, as the conclusion acknowledges. The result therefore shows that normalized steps train wide networks in the NTK regime, but nothing in it distinguishes Spectral-GD from normalized GD.

Second, the experiments do not support the claims made from them. The pretraining runs make 5000 full-batch passes over the same fixed data, with heavy overfitting in Figure 1(d), so they do not show that Spectral-GD is a good model of Muon in pretraining. They also do not include normalized GD, so they cannot show that the polar factor itself matters.

Overall, these issues keep me from recommending acceptance.

AuthorsOpenReview ↗

Clarifications.

Thanks for replies and may we present the following 2 arguments.

  • Kindly note that Theorem A.3 gives different answers/different width requirements for Spectral-GD and normalized-GD. This is explicitly said in the lines below the statement of Theorem A.3, near the top of page 7 : that the parameter ρ\rho in there evaluates to n\sqrt{n} for spectral-GD and 11 for normalized GD.

    Hence as far as Theorem A.3 goes it distinguishes between spectral-GD and normalized-GD.

  • May we emphasize the purpose of the experiments shown in Figures 1 (a), (b), (c) and (d) : there are merely illustrative experiments meant to show that under certain identical conditions Spectral-GD and Muon behave similarly -- which is clearly visible in these 4 plots by the nearly overlapping nature of the lines for Muon and Spectral-GD. This is not to claim that in all conditions both algorithms would always match or even to replicate the conditions of the theory : it just shows that there exists conditions when these two methods can nearly coincide.

    Ever since the first NTK proofs around 2018, it is well known that NTK styled theory works in parameter regimes not usually used, and that many ordinary experimental setups often replicate behaviour in the NTK regime.

    May we emphasize that this is a pure theory/maths paper and the theory stands on its own independent of the experiments.

The crux of this research is to establish proof techniques to understand algorithms like Spectral-GD which do not converge but which nonetheless can find nets of arbitrarily low loss.

To the best of our knowledge, prior to our proof there has been no other theoretical argument to establish spectral-GD finding low loss neural nets.

This is the first-of-its-kind proof of training by such algorithms in the non-smooth non-convex regime.

We strongly emphasize that this is quite subtle to establish - as can be understood by reading the proof - it requires many subtle changes to the NTK proof pipeline. We request that our work be judged as work of pure theory/maths where the contribution is to establish a novel extension of the NTK proof technique towards helping understand the new spectral optimizers being used in modern deep-learning.

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

This paper analyzes Spectral-GD, the full-batch, momentum-free core of Muon, for training a wide two-layer ReLU network. Under Gaussian initialization, fixed random output weights, and a positive-definite infinite-width kernel, it gives width, step-size, and iteration conditions for reaching a prescribed training loss with high probability. The proof combines NTK stability with spectral–nuclear norm duality. A synthetic regression experiment illustrates the training dynamics, while language-model experiments compare Spectral-GD with AdamW and Muon.

Critical strengths

The paper analyzes the polar update directly, which is relevant to understanding Muon. Its focus on reaching a target training loss is more informative than a stationary-point guarantee.

The setup specifies the ReLU derivative at activation boundaries and the compact polar factor for rank-deficient gradients. These conventions make the treatment of nonsmoothness and zero singular values precise.

Critical weaknesses

1.Theorem 3.1 claims the loss bound for “all t ≥T” , but the proof establishes neighborhood containment only up to TT . Lemma 4.3 requires both update endpoints to remain in that neighborhood. Step 5 does not establish this condition after TT.

2.The width comparison needs qualification. The “n5 in place of n6” claim compares sufficient bounds from different analyses and does not isolate an advantage of the update rule.

Questions for authors

1.What ensures that the weights remain in the required neighborhood after TT? Should the theorem instead be restricted to the loss at TT?

2.Can you compare with Frobenius-normalized GD under the same assumptions to clarify which improvement comes from the polar update?

3 comments

We thank the reviewer for their detailed feedback. We present the following responses to the key issues raised. Note: All revisions made in response to the reviewers’ comments are highlighted in blue in the updated manuscript.

W1. Theorem 3.1 claims the loss bound for “all t≥Tt \geq T”

Response. Thanks for the spotting the typo in the theorem statement; and it is corrected in the updated uploaded file. Theorem 3.1 now states L(WT)≤εL(\mathbf{W}_T)\le\varepsilon (Eq. 9), as does Section 1. The iterates stay in B\mathcal B for t≤Tt\le T (Eqs. 26--27), and Step 5 runs over t⋆≤t<Tt^\star\le t<T, where both endpoints lie in B\mathcal B, so Lemma 4.3 gives L(Wt)≤εL(\mathbf{W}_t)\le\varepsilon on [t⋆,T][t^\star,T]. Also a general version of the Theorem 3.13.1 has been given in Appendix A as Theorem A.3

W2. The width comparison needs qualification.

Response. The paragraph on page 4, line number between 179-192 has been edited to give a more detailed comparison with previous NTK literatures for similar shallow nets.

Q1. Should the theorem instead be restricted to the loss at TT?

Response. We believe the mis-interpretation above arose because of the typo in our earlier draft which has been now fixed. Theorem 3.1 now states L(WT)≤εL(\mathbf{W}_T)\le\varepsilon (Eq. 9), as does Section 1. The iterates stay in B\mathcal B for t≤Tt\le T (Eqs. 26--27), and Step 5 runs over t⋆≤t<Tt^\star\le t<T, where both endpoints lie in B\mathcal B, so Lemma 4.3 gives L(Wt)≤εL(\mathbf{W}_t)\le\varepsilon on [t⋆,T][t^\star,T].

Q2. Can you compare with Frobenius-normalized GD

Response. New Theorem A.3 (Appendix A) gives this general theorem that the reviewer has guessed correctly. The proof uses the direction Dt{\bf D}_t only through three properties, (1) ⟨Gt,Dt⟩≥∥Gt∥F\langle {\bf G}_t,{\bf D}_t\rangle\ge\|{\bf G}_t\|_F, (2) ∥Dt∥2≤1\|{\bf D}_t\|_2\le1, (3) ∥Dt∥F≤ρ\|{\bf D}_t\|_F\le\rho, and any such update reaches L(WT)≤εL({\bf W}_T)\le\varepsilon with the same η\eta and TT as Theorem 3.1, provided the width satisfies a ρ\rho dependent condition (Eq. 46).

Please refer to Table 22 on page 77 which gives the mapping which reduces the general theorem(A.1) to the theorem 3.13.1 of the main paper.

Thanks for following up. The stated correction appears to address the proof's time-range issue, but I'm still unsure whether the improved width bound reflects an advantage over Frobenius-normalized GD. I'll keep my original rating for now.

AuthorsOpenReview ↗

Clarification.

May we emphasize that there is no claim in the paper about Spectral-GD being better than Frobenius-normalized GD. Establishing such a comparison is not the topic of the paper. The objective of the paper is to establish that algorithms as considered in Theorem A.3 (and the special case Theorem 3.1) - which are momentum-free Muon generalized - can find arbitrarily low loss nets and remain confined among those states for a parametric amount of time.

We strongly emphasize that this is quite subtle to establish - as can be understood by reading the proof - it requires many subtle changes to the NTK proof pipeline. We request that our work be judged as work of pure theory/maths where the contribution is to establish a novel extension of the NTK proof technique towards helping understand the new spectral optimizers being used in modern deep-learning.

Comments on the paper

2 comments

Q5. Can the authors show how the behavior changes with mm?

Response. New Figure 3 sweeps m∈{500,1000,2000,4000,8000}m\in\{500,1000,2000,4000,8000\} at ε=0.2\varepsilon=0.2, η=0.00918\eta=0.00918, n=20n=20, d=100d=100, five initializations per width, and plots the loss, the fraction of (input, unit) pairs whose ReLU gate differs from initialization, and max⁡r∥wr(t)−wr(0)∥2\max_r\|\mathbf{w}_r(t)-\mathbf{w}_r(0)\|_2. At every width the loss falls below ε\varepsilon and stays there. From m=500m=500 to 80008000 the gate-change fraction drops from about 0.0150.015 to 0.00340.0034, and the largest unit movement from about 0.350.35 to 0.080.08. These are the quantities the proof controls (Lemma 4.2), so its mechanism is already visible at mm in the hundreds.

Q6. How were the hyperparameters tuned?

Response. There was no tuning for the synthetic experiment: η\eta and TT are computed from (8) before training (Section 1, Table 1). We did not tune the hyperparameters of the LLM experiments either; we took them from standard references. For pretraining, Muon's momentum (0.950.95, Nesterov) and its five Newton--Schulz steps are the defaults of modded-nanogpt (Jordan, 2024), and the learning-rate schedule follows nanoGPT (Karpathy, 2022): after a linear warmup (250250 steps), cosine decay over the 50005000 iterations to one tenth of the peak learning rate. Spectral-GD and Muon use the same peak learning rate (0.0050.005) and the same schedule, so neither optimizer is tuned in its favour; the biases are trained with AdamW at learning rate 3⋅10−43\cdot10^{-4}. For fine-tuning, the learning rate is 2⋅10−52\cdot10^{-5} with weight decay 0.010.01, and on kto-mix-14k Spectral-GD uses this learning rate divided by 5. A table in the new experimental appendix will list all settings.

AuthorsOpenReview ↗

A Clarifying Summary

Since the seminal thesis of Radford Neal (1995) - https://glizen.com/radfordneal/ftp/thesis.pdf, it has often been explored to quantify how neural net training by first-order algorithms become analytically tractable in the large width regime. This has led to two famous mathematical paradigms : the mean-field approach that uses infinite width and the Neural Tangent Kernel (NTK) approach to proofs which needs width scaling polynomially in the number of training data.

Our contribution is to be seen as a novel extension of the NTK framework : to explain modern matrix optimizers of the Muon-type. 

To the best of our knowledge, prior to our proof there has been no other theoretical argument to establish spectral-GD finding low loss neural nets.

This is the first-of-its-kind proof of training by such algorithms in the non-smooth non-convex regime.

Unlike in the NTK framework, convergence in the usual sense cannot happen for such methods given the gradient information is not fully available to Muon-type optimizers. In this first-of-its-kind work, we rigorously prove that despite this lack of information, such optimizers can be tuned to progress such that they find arbitrarily low loss nets - and remain confined there upto times determined by the width. The parameter kk in the general Theorem A.3 quadratically increases the width requirement  and linearly elongates the time the optimizer state remains confined to ϵ−\epsilon- loss weights, for any ϵ>0\epsilon >0.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.