acceptodds
Under review as a conference paper at ICLR 2027

When to use what Schatten- norm in deep learning?

Abstract

Schatten- based optimizers such as Muon have shown promising empirical performance, but there remains seemingly conflicting observations regarding whether they are beneficial. We resolve this conflict by showing that the conclusion is regime dependent. Even when the natural problem geometry is the Schatten- norm, smaller Schatten- geometries can be optimal, specifically in the low-dimensional regime, which we show includes Chinchilla scaling. This conclusion follows from a new noise-robust acceleration result for the SODA framework for . The same analysis explains why Muon-like methods do not require warmup, why they naturally favor large batches, and yields a batch size scaling rule for arbitrary .

Primary area:
optimization
Keywords:
Deep learning, geometry, optimization, dual averaging

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_pbnNOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

The paper builds on the SODA framework of Pethick et al. (2026). SODA combines optimistic dual averaging with schedule-free averaging, and with a hard spectral-norm constraint it recovers Muon. The authors replace the strongly convex reference function analysis by a pp-uniformly convex one. This makes the analysis cover ℓp\ell_p and Schatten-pp geometries for p>2p > 2.

For smooth convex objectives with a gradient-variation noise assumption, they prove an accelerated rate O(LpRp2/n+σqRp/n1/p)O(L_pR_p^2/n + \sigma_qR_p/n^{1/p}). They also give Hölder-smooth extensions. With mini-batches and rr-moment noise they derive oracle complexities and a batch rule Bp∼N2(p−1)/(3p−2)B_p \sim N^{2(p-1)/(3p-2)} for the non-accelerated method. At p=∞p = \infty this recovers B∼N2/3B \sim N^{2/3}.

They then assume the problem is smooth in the ∞\infty-geometry and compare upper bounds across p. Their conclusion is that a smaller pp can be better when the oracle budget NN exceeds the dimension dd. They argue that this regime contains Chinchilla scaling, explains why Muon does not need warmup, and explains why it favors large batches. A geometry restart scheme from p≈log⁡dp \approx \log d to p=prp = p_r is also proposed. There are no experiments.

Critical strengths
  1. A clean, unified, and rigorous analysis within the SODA framework of Pethick et al. (2026), covering accelerated and non-accelerated methods, heavy-tailed noise, and mini-batching. The resulting rates recover known results and give potential explanations for the practical performance of Muon and related algorithms. For example, the theory shows that the benefits of Muon depend on the regime, even when the natural problem geometry is the Schatten-∞\infty norm. It also explains why Muon-like methods do not require warmup, why they may benefit from large batches, and how to derive a batch-size scaling rules.
  2. The paper is honest about its limitations, noting that the norm conversions it relies on are worst-case bounds and that sharper, problem-dependent relations may lead to different conclusions.
Critical weaknesses
  1. The regime-dependent conclusions seem stronger than the evidence supports. The guarantees comparison is based on the worst case relationships Lp≤L∞L_p \leq L_\infty and Rp≤d1/pR∞R_p \leq d^{1/p}R_\infty, treating them as if they were equalities. Footnote 2 defines the ∞\infty-geometry as "natural" when LpRp2L_pR_p^2 is smallest at p=∞p = \infty. In that case LpRp2=cL∞R∞2L_pR_p^2 = c L_\infty R_\infty^2 with c∈[1,d2/p]c \in [1, d^{2/p}]. The finite-pp bound then beats the ∞\infty bound once N>cp/2N > c^{p/2}, so the crossover lies anywhere between N≈1N \approx 1 and N≈dN \approx d. The paper’s N≈dN \approx d is the worst-case endpoint. The claim that smaller pp wins for N≥dN \geq d is the better-founded direction, since the finite-pp guarantee is smaller even in the worst case. It is still a comparison of guarantees, not of performance. The claim that p=∞p = \infty is preferred for N≤dN \leq d needs the worst case to be attained, and no lower bound shows this. If cc is close to 1, smaller pp wins at every NN. The noise conversion has the same issue. The Limitations paragraph says sharper relations could move the boundary, but it seems that they could also remove one side of it.

  2. Contribution (ii) presents Bp∼N2(p−1)/(3p−2)B_p \sim N^{2(p-1)/(3p-2)}, increasing with pp, as the batch rule. That is the non-accelerated rule. Under the accelerated parameterization (Table 4) the exponent 2(p+1)/(3p+2)2(p+1)/(3p+2) decreases with pp. For p=2p = 2 the table entry is the largest batch that keeps the optimal rate. So the ordering of the optimal batch size depends on the parameterization, and the main part of the paper states only one. The paper presents acceleration as a benefit of smaller pp, so it should say which rule it recommends. Appendix D.2 says acceleration allows taking larger batch sizes without noting the reversal.

Questions for authors
  1. The model is convex, and the paper does not discuss which conclusions might extend to the nonconvex setting. Could the authors include the motivation for studying the convex case in the paper? Citing work showing that insights from convex optimization can transfer to deep learning practice could strengthen the motivation for studying this framework in the first place.

  2. The motivation for the SODA framework may be difficult to follow for readers unfamiliar with the original work of Pethick et al. (2026). Could the authors elaborate on the main design principles behind SODA, why it is a meaningful framework to study, and the origins of all of its algorithmic components, beyond describing it as an extension of ODA?

  3. Can the authors provide intuition for why the optimal batch size increases with pp in the non-accelerated regime but decreases with pp under the accelerated parameterization?

  4. The analytical tools appear quite standard (ODA with a uniformly convex regularizer, the online-to-batch argument of Defazio et al., mirror descent under heavy-tailed noise). The main contribution seems to lie in combining these tools and interpreting the resulting rates across different regimes, but this aspect is currently the least well-supported. Could the authors clarify what they consider the main novel contributions?

  5. Is the worst-case norm conversion tight for any class of problems? Which regimes do the authors expect to be most relevant in practice?

Overall, I still think it is a good paper and would be happy to reconsider my score if the authors address the weaknesses and questions raised above.

3 comments

We thank the reviewer for the critical comments, which helped us substantially improve both the results and the presentation.

The regime discussion is now stated after nn iterations with a fixed batch size BB, which makes the regimes much easier to interpret (Table 2):

  • low-dimensional (n≳dn\gtrsim d): p=prp=p_r is preferred
  • high-dimensional, low-rank noise: p→∞p\to\infty is preferred
  • high-dimensional, deterministic-dominated (e.g., a large batch size): p→∞p\to\infty is preferred
  • high-dimensional, noise-dominated: p=prp=p_r is preferred

A phase diagram (Figure 2) shows these regions over BB and n/dn/d.

New experiments (Section 5). To show that the regimes are informative, we use the random-feature model of (Davis and Drusvyatskiy 2025). For this model, L2R22L_2R_2^2 and L∞R∞2L_\infty R_\infty^2 can be computed exactly, and we confirm that L2R22/(L∞R∞2)L_2R_2^2/(L_\infty R_\infty^2) grows linearly in dd, matching the worst case L2R22≤d L∞R∞2L_2R_2^2\le d\,L_\infty R_\infty^2 up to a constant. So the problem has ∞\infty-norm geometry, with the largest possible separation. We compare SODA with p=2p=2 and p=∞p=\infty (Muon), with step sizes tuned per oracle budget, in three settings:

  • exact gradients: the transition from p=∞p=\infty to p=2p=2 occurs at n≈dn\approx d, as predicted (first row of Table 2);
  • rank-one noise (the setting most favorable to Schatten-∞\infty): the transition occurs at N≈dN\approx d, as predicted (second row of Table 2);
  • single-sample minibatch gradients at a fixed BB: the window in which p=∞p=\infty is preferred grows with BB, and Table 2 predicts where it ends (third row of Table 2).

So even when both the geometry (L∞R∞2<L2R22L_\infty R_\infty^2<L_2R_2^2) and the noise structure (rank-one noise, so that σ1,2/σ2=1\sigma_{1,2}/\sigma_2=1) favor a Schatten-∞\infty based optimizer such as Muon, there is a regime, n≳dn\gtrsim d, in which p=2p=2 attains a smaller loss.

(Davis and Drusvyatskiy 2025) "When do spectral gradient updates help in deep learning?"

  1. The claim that p=∞p = \infty is preferred for N≤dN \leq d needs the worst case to be attained

We now show that this worst case is attained in a concrete example:

  • Problem constants. In the random-feature model, L2R22/(L∞R∞2)L_2R_2^2/(L_\infty R_\infty^2) grows linearly in dd, from 22 at d=16d=16 to 1111 at d=128d=128 (roughly 0.09d0.09d). This is the same scaling as the worst case L2R22≤d L∞R∞2L_2R_2^2\le d\,L_\infty R_\infty^2, up to a constant.
  • Noise. The conversion is attained with equality for low-rank noise, and the dimension factor is attained for isotropic noise. The effect on the regimes is shown in the phase diagram (Figure 2).

The new experiments on this model confirm that the resulting predictions hold for a concrete example and that the transition from p=∞p=\infty to p=2p=2 dominating occurs where Table 2 predicts.

accelerated batch size rule vs non-accelerated

All discussion in the main text is now based on the accelerated rate. Even though p=2p=2 allows a larger critical batch size than p→∞p\to\infty, we can still (perhaps counterintuitively) conclude that a large batch size favors p→∞p\to\infty. This is because, while the critical batch size of p=2p=2 is larger, p=2p=2 already attains its optimal rate at a smaller batch size. In contrast, p→∞p\to\infty benefits from a larger batch size, because batching shrinks its stochastic term until the comparison is decided by the deterministic term, where p→∞p\to\infty is favored for n≲dn\lesssim d.

Questions for authors

Could the authors include the motivation for studying the convex case in the paper?

Strictly speaking, our analysis does not need convexity everywhere, only star-convexity and Hölder co-coercivity along the trajectory. We work in this setting for two reasons:

  • It lets us bound the loss gap f(xn)−f⋆f(x^n)-f^\star itself, which is what we ultimately care about.
  • Since the loss gap is the same in every geometry, it gives a geometry-free criterion for comparing p=2p=2, p→∞p\to\infty and the intermediate pp, which is the central question of the paper.

There is growing evidence that insights from this setting transfer to deep learning practice:

  • Meterez et al. (2026) show that a quadratic model predicts the training dynamics of up to 10% of training
  • Convex theory closely predicts learning-rate schedules for large models (Schaipp et al., 2025)
  • The hyperparameters of MAI (Microsoft AI, 2026) match our p=2p=2 prescription: LR×WD∝1/steps\mathrm{LR}\times\mathrm{WD}\propto 1/\text{steps} (our λk≍1/k\lambda_k\asymp 1/k), and LR∝B steps−0.57\mathrm{LR}\propto\sqrt B\,\text{steps}^{-0.57} (our R2/(σ2k1/2)R_2/(\sigma_2 k^{1/2}) with σ2∝B−1/2\sigma_2\propto B^{-1/2})

Could the authors elaborate on the main design principles behind SODA, why it is a meaningful framework to study, and the origins of all of its algorithmic components, beyond describing it as an extension of ODA?

We tried to capture this with the following passage: "What is particularly attractive about this algorithmic template in the context of deep learning is that it allows us to capture commonly used techniques such as Nesterov momentum (mˉk+1\bar m^{k+1}), weight decay (parameterized by λk\lambda_k when λˉk=0\bar\lambda_k=0) and the use of different geometries (∂h∗\partial h^*), all in a way where their impact can be understood theoretically."

Can the authors provide intuition for why the optimal batch size increases with pp in the non-accelerated regime but decreases with pp under the accelerated parameterization?

Under a fixed budget N=nBN=nB, a larger batch size leaves fewer iterations. The stochastic term, S2,pNn1/2−1/p\tfrac{S_{2,p}}{\sqrt N}n^{1/2-1/p}, penalizes iterations more for larger pp, so without acceleration, where the deterministic term Apn\tfrac{A_p}{n} is the same for all pp, larger pp prefers a larger batch size. With acceleration, on the other hand, the deterministic term Apn1+2/p\tfrac{A_p}{n^{1+2/p}} decays faster for smaller pp, so smaller pp needs fewer iterations and can afford a larger batch size.

Could the authors clarify what they consider the main novel contributions?

We agree that the individual building blocks are known, and we do not claim novelty for them, but we would not consider combining them trivial.

To our knowledge, this is the first accelerated rate for pp-norm geometries that is robust to heavy-tailed noise. Prior accelerated results are deterministic (d'Aspremont et al., 2018), and heavy-tailed mirror descent is non-accelerated (Vural et al., 2022) and combining them is not a mechanical procedure. In the Euclidean analysis, the regret term ∥gk−gk−1∥∗2\Vert g^k-g^{k-1}\Vert_*^2 cancels exactly against the negative smoothness term, since both have the same exponent. For p>2p>2 the regret term has exponent q<2q<2, so one has to carefully trade off the two terms. This is what leaves us with the 1/n1+2/p1/n^{1+2/p} which matches the lower bound of Guzmán and Nemirovski (2015).

The second major contribution is indeed then to use this result to extract precise statements about which optimizer choice is favorable in which regime. Regarding support for the interpretation: We now also have experimental support for the interpretation with the new Section 5, which tests the regimes on the random-feature model of Davis and Drusvyatskiy and confirms our regime predictions.

Is the worst-case norm conversion tight for any class of problems?

Yes. In the random-feature model, L2R22L_2R_2^2 grows linearly in dd relative to L∞R∞2L_\infty R_\infty^2, as in the worst case L2R22≲d L∞R∞2L_2R_2^2\lesssim d\,L_\infty R_\infty^2. The noise conversion is attained for both low-rank noise (equality) and isotropic noise (the full dimension factor).

Which regimes do the authors expect to be most relevant in practice?

We do not think there is a universal statement here. The main point of the paper is to make people aware that they are implicitly placing themselves in a particular regime (see the new phase diagram, Figure 2). Two cases illustrates this:

  • if one is doing pre-training with a fixed horizon then the batch size should scale sufficiently fast across the scaling ladder in order to keep p=∞p=\infty optimal (section 4).
  • if one is doing continuous training where the horizon is not known in advance and the batch size is fixed, then training will eventually hit the low dimensional regime in which case p=∞p=\infty would become suboptimal.

Thank you for the detailed rebuttal and the substantial revision. These changes address my main concerns, and I raise my score.

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

This paper shows that when constructing a SODA- or Muon-like optimizer, the choice of Schatten-p norm to build it with should best depend on how heavy-tailed the gradient noise distribution is, rather than what the problem's smoothness geometry is like. Using a few basic assumptions about the optimization problem, the authors find a certain kind of bound on SODA's convergence rate, wherein the best choice of p is tied to the heavy-tailedness of the noise. This in turn acts as an explanation for why Schatten-p norm based optimizers with differing values of p have become dominant for different problems. Various parameters in the bound additionally offer explanations for the success of certain empricial best-practices, such as learning rate warmup, and staying under a critical batch size that shifts with the training compute budget.

Critical strengths
  • The assumptions required to obtain the result are fairly standard and/or reasonable, while the resulting bound(s), when optimized, dictate fairly reasonable kinds of techniques to be used for training, such as learning rate warmup followed by decay, and staying under the critical batch size.
  • The bounds also dictate that the best choice of p to use in a SODA or Muon-like optimizer is tied to the tail behavior of the gradient noise in the problem, offering to explain why SGD (p=2p=2) is used in some cases, Soft-Muon (2<p<∞2<p<\infty) in others, and Muon (p=∞p=\infty) in yet others.
  • The bounds offer to explain what happens when pp mis-attributes the heavy-tailedness of the gradient noise.
  • In Section 4.1.1, the theory makes a specific a priori prediction that switching the optimizer at a particular point in time should improve optimization. Since this strategy is as-of-yet mostly untested, it's empirical validation would serve as very strong evidence for the validity of this theory. This is in contrast to many other theories, which mostly produce a posteriori predictions and do not offer as easy a way to validate them.
Critical weaknesses
  • While the theory dictates what pp to use for different problems, it would be nice to see some choices of pp that have become standardized in various empirical settings (modded-nanogpt, CIFAR10 speedrun, and other examples mentioned in the paper) to compare against the best values of pp that the theory would predict in those settings. While this may require some experiments to measure the gradient distributions during training, seeing the predictions match up with standard practices would ground these results.
  • A horizon-free modification to the settings must be constructed in order to extract the result that learning rate warmup followed by decay is best. It is unclear how reasonable this modification is, as the theory says nothing about the modified version and how it may break the bounds derived. Therefore, it is not entirely clear whether the theory actually serves good insight into the reasons that learning rate warmup and decay are useful.
  • The both parameterizations require that the learning rate γk\gamma_k increases over the whole time, whereas the final learning rate value decreases with the step count to compensate. This is not well supported in practice, so it is strange that the theory requires this learning rate schedule to get the best bound. It is not clear whether a horizon-free modification to the accelerated parameterization will recover a more reasonable strategy either.
Questions for authors
  • Is there any way to estimate NswN_{sw} in one or more practical settings to see if an empirically tuned switch point matches what your theory predicts will be the best?
  • Why is dd linked to the rank dimension rather than the parameter count in a neural network?
  • On my last listed weakness point: Is there any version or modification of the theory or assumptions from which we can derive a more realistic learning rate schedule as the optimal schedule, or are we stuck with this strangely increasing schedule?
3 comments

We thank the reviewer for the constructive comments, which helped us improve the results.

New experiments (Section 5). We have added new experiments to illustrate that the derived regimes can be observed in practice. We use the random-feature model of (Davis and Drusvyatskiy 2025). For this model, L2R22L_2R_2^2 and L∞R∞2L_\infty R_\infty^2 can be computed exactly, and we confirm that L2R22/(L∞R∞2)L_2R_2^2/(L_\infty R_\infty^2) grows linearly in dd, matching the worst case L2R22≤d L∞R∞2L_2R_2^2\le d\,L_\infty R_\infty^2 up to a constant. So the problem has ∞\infty-norm geometry, with the largest possible separation. We compare SODA with p=2p=2 and p=∞p=\infty (Muon), with step sizes tuned per oracle budget, in three settings:

  • exact gradients: the transition from p=∞p=\infty to p=2p=2 occurs at n≈dn\approx d, as predicted (first row of Table 2)
  • rank-one noise (the setting most favorable to Schatten-∞\infty): the transition occurs at N≈dN\approx d, as predicted (second row of Table 2)
  • single-sample minibatch gradients at a fixed BB: the window in which p=∞p=\infty is preferred grows with BB, and Table 2 predicts where it ends (third row of Table 2)

So even when both the geometry (L∞R∞2<L2R22L_\infty R_\infty^2<L_2R_2^2) and the noise structure (rank-one noise, so that σ1,2/σ2=1\sigma_{1,2}/\sigma_2=1) favor a Schatten-∞\infty based optimizer such as Muon, there is a regime, n≳dn\gtrsim d, in which p=2p=2 attains a smaller loss.

(Davis and Drusvyatskiy 2025) "When do spectral gradient updates help in deep learning?"

"Since this strategy is as-of-yet mostly untested, it's empirical validation would serve as very strong evidence for the validity of this theory"

We have now tested the switching strategy which leads to better performance especially in the later lower dimensional phase (Appendix F.3). This improvement is achieved with a single run, in contrast with the baselines that are tuned for each horizon. The primary downside is that the algorithm needs to estimate problem constants such as noise, smoothness and distance to solution in order to set both the stepsize schedule and the switching point. It would be interesting for future work to remove these dependencies.

"choices of pp that have become standardized in various empirical settings"

Interestingly, HTMuon (Pang et al., 2026) uses p=9p=9 for models of width d=512d=512 to 20482048 (their exponent 0.125=q−10.125=q-1). This closely matches our choice pd=max⁡3,⌈log⁡(ed)⌉∈8,9p_d=\max\\{3,\lceil\log(\mathrm{e}d)\rceil\\}\in\\{8,9\\}. We have added experiments in appendix F.2 on the random feature model showing that pdp_d matches or improves on p=∞p=\infty across the regimes.

learning rate warmup and decay not covered by theory

The warmup observation is covered by our theory for the fixed-horizon parameterization. There η\eta is constant in kk, and the effective stepsize is λkγkq−1≍ηq−1k(3−p)/(p−1)\lambda_k\gamma_k^{q-1}\asymp\eta^{q-1}k^{(3-p)/(p-1)}. It increases with kk for p<3p<3 (linearly for p=2p=2) and decreases for p>3p>3 (as k−1k^{-1} for p→∞p\to\infty). So the presence of warmup for small pp, and its absence for p→∞p\to\infty, is a property of the guaranteed method. The horizon-free version is only used to translate the nn-dependence of η\eta (a smaller η\eta for longer horizons) into a decay within a single run. We agree that this part is not covered by our guarantees, which is what the footnote in the "Effective stepsize" addresses.

strangely increasing [learning rate] schedule

We believe there is a misunderstanding due to naming. What people typically refer to as the learning rate is what in our notation appears as λkγkq−1\lambda_k \gamma_k^{q-1} (please see the paragraph called "Effective stepsize"). This quantity is not increasing throughout the entire run.

Questions For Authors

Is there any way to estimate NswN_{sw}?

For the random feature model that we test on it is indeed possible to estimate the switching time since we can compute the problem constants, but it is interesting future work to avoid needing to know these quantities in advance.

Why is dd linked to the rank dimension rather than the parameter count in a neural network?

The dimension factors in our results come from conversions between Schatten norms, ∥X∥p≤rank⁡(X)1/p∥X∥∞\Vert X\Vert_p\le\operatorname{rank}(X)^{1/p}\Vert X\Vert_\infty. Since Schatten norms depend only on the singular values, of which there are at most min⁡(m,n)\min(m,n), these factors depend on the rank and not on the number of entries mnmn. The random-feature model in our new experiments shows that the rank factor is indeed attained in the sense that L2R22/(L∞R∞2)L_2R_2^2/(L_\infty R_\infty^2) grows linearly in dd (Appendix F.1).

Thank you for your answering my questions and for the extra experimental results.

On the switching strategy results: they look great, indeed the switching helps with learning as predicted by the theory. I do not find any issue with needing to estimate the switching point, since practically speaking, this is a single hyperparameter and so can easily be tuned via hyperparameter sweep, which is much less effort than estimating the necessary quantities.

On standard choices of pp for various empirical settings, I am still not convinced. I was aiming more to get a sense of how the theory transfers to any realistic problem settings where Schatten-pp-norm optimizers are commonly used, perhaps by figuring out what the theory predicts is a good pp for those settings, and comparing to the (effective) pp that the research field for that setting has conventionally determined is the best in that setting. (You can effectively read the pp value used in those settings by looking at the field's usual choice of optimizer and hyperparameters.) The HTMuon paper is a good example that shows one type of problem (LLM pretraining), but the random feature model is not a real problem that a practitioner will ever encounter and tune a pp parameter for. I was wondering more about consistency of good pp estimation across diverse problem settings more akin to things like language pretraining, vision pretraining, flow matching and diffusion models, LoRA finetuning, CNNs, reinforcement learning, etc, where it is well known that different optimizers (which probably correspond to different pp parameters) are better for different problems. As the discussion period comes to a close, I am mainly describing this as advice/suggestions for any future revisions of the paper you might make, rather than for this submission cycle.

On your response to "learning rate warmup and decay not covered by theory", I believe I originally misunderstood how you have derived the warmup-decay curve. You are not fundamentally getting it from the horizon-free modification, but rather from pp affecting whether the stepsize increases or decreases with time, if I have understood your response correctly. But in order to get a warmup-decay curve from that, you require that early on in training we have p<3p<3 and later on we have p>3p>3. I am quite unsure that this condition on the variation of pp during training is a well-founded assumption. So for that, I am still not convinced, but I feel it is likely because I was not able to understand how you obtained the warmup-decay curve.

On "strangely increasing [learning rate] schedule", indeed I had a misunderstanding due to naming, thank you for clarifying.

Also, thank you for answering my three listed questions. I believe I also had a misunderstanding due to naming dd as "dimension" when it has always referred to rank.

Scores this year are from 1 to 4. If I had an option, I would increase my score by 0.5 and decrease my confidence by 0.5, but that is not an option, so I will just maintain both.

Thanks for the positive response to our rebuttal and for engaging in such a detailed manner.

I was wondering more about consistency of good pp estimation across diverse problem settings more akin to things like language pretraining, vision pretraining, flow matching and diffusion models, LoRA finetuning, CNNs, reinforcement learning

We agree that this is a very promising direction and the hope is indeed to develop problem dependent guidance. Now that we have clear dependencies on the geometry and noise structure one can ask, e.g., what the noise structure is in RL or what the geometry is in finetuning.

But in order to get a warmup-decay curve from that, you require that early on in training we have p<3p<3 and later on we have p>3p>3.

This is indeed the point. Empirically, warmup is not necessary for Muon, which is consistent with the fact that large pp effectively removes the warmup in our theory. We hope this clarifies it.

Reviewer_g8jpOpenReview ↗
Rating
2
Confidence
4(+1)
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The authors discuss Schatten style optimizers, and seek to close a theory-empirical gap to further interpretability. The conclusion is that this is regime dependent. The results discuss new noise-robust acceleration result for the SODA framework, and aims to explain why Muon-like methods do not need warmup and favor large batches. The main convergence result is the central piece of this work, however some statements overclaim the consequences.

Critical strengths
  • The extension from strongly convex to p-uniformly convex reference functions yields a robust accelerated guarantee for both vector and Schatten norms in Corollary 3.2. The paper's strongest technical contribution is then retaining an accelerated deterministic term while accounting for heavy-tailed stochastic noise. This targets a limitation in previous and existing SODA analysis.

  • Section 4 makes the tradeoff distinction between the dim penalty through choosing a smaller p and the stronger acceleration available in that geometry. This is a nice theoretical reason why matching the optimizer's norm to the objective's smoothness norm might not yield the best convergence guarantee.

  • The separation of the oracle's noise moment ( r) versus the algorithm's conjugate gradient exponent ( q) then deriving the tradeoffs of batch size, iteration count, total oracle budget is well planned and informative. Section 3.1's treatment of noise assumption and mini-batching is more informative than a general qualitative argument that spectral methods prefer large batches.

Critical weaknesses
  • Some conclusions overstate. The geometry selection conclusions are stronger than the upper-bound comparisons. A small upper bound does not establish better algorithm performance on the same problem class. THe cited lower bound of Guzman and Nemirovski applies when the iteration budget does not exceed dimension, and therefore does not establish optimality in N>d regimes. This distinction between minimizing the derived guarantee and establishing an optimal algorithm is critical to the paper's claims.

  • Section 4.2 argues regarding training regimes which favor smaller p. However given Table 3's stochastic condition, the conclusion also depends on noise, smoothness, and distance to the optimum scale with model size. These dependencies are unclear. Using a single matrix's rank as the effective dimension of the full training problem need further justification as well.

  • The statement that larger p favor larger batch sizes needs qualification, since acceleration is the main new contribution. Table 2 states the non-accelerated exponent which increases with p, but appendix D and Table 4 give the accelerated exponent which decreases with p. The balancing rule also states the largest batch size retaining the rate rather than a unique optimum. These distinctions are crucial to the paper.

  • The conclusions also overstate the impact of deep learning behavior. Guarantees assume convexity and specific parameters in SODA, this does not carry over to prove optimization or training experiments testing its predicted geometry crossover / switching strategy.

Questions for authors
  • Does optimal geometry here mean the geometry minimizing the particular SODA upper bounds derived here, or an ordering of achievable errors on a common problem class?

  • How should the increasing batch exponent in Table 2 be reconciled with the decreasing accelerated exponent in Table 3? Is parametrization intended to explain practical Muon training? Is the recommendation about a necessary batch size a bound-minimizing batch size, or the largest batch preserving oracle complexity?

  • Can the authors give a practical experiment supporting the predicted change in preferred geometry as N/d varies under a common oracle budget? Is the warmup behaviour in Fig 1 covered by a convergence guarantee for the plotted anytime schedule?

3 comments

We thank the reviewer for the critical comments, which helped us substantially improve both the results and the presentation.

The regime discussion is now stated after nn iterations with a fixed batch size BB. This makes the regimes much easier to interpret (Table 2):

  • low-dimensional (n≳dn\gtrsim d): p=prp=p_r is preferred
  • high-dimensional, low-rank noise: p→∞p\to\infty is preferred
  • high-dimensional, deterministic-dominated (e.g., a large batch size): p→∞p\to\infty is preferred
  • high-dimensional, noise-dominated: p=prp=p_r is preferred

A phase diagram (Figure 2) shows these regions over BB and n/dn/d.

New experiments (Section 5). To show that the regimes are informative, we use the random-feature model of (Davis and Drusvyatskiy 2025). For this model, L2R22L_2R_2^2 and L∞R∞2L_\infty R_\infty^2 can be computed exactly, and we confirm that L2R22/(L∞R∞2)L_2R_2^2/(L_\infty R_\infty^2) grows linearly in dd, matching the worst case L2R22≤d L∞R∞2L_2R_2^2\le d\,L_\infty R_\infty^2 up to a constant. So the problem has ∞\infty-norm geometry, with the largest possible separation. We compare SODA with p=2p=2 and p=∞p=\infty (Muon), with step sizes tuned per oracle budget across three settings:

  • exact gradients: the transition from p=∞p=\infty to p=2p=2 occurs at n≈dn\approx d as predicted (first row of Table 2).
  • rank-one noise (the setting most favorable to Schatten-∞\infty): the transition occurs at N≈dN\approx d as predicted (second row of Table 2).
  • single-sample minibatch gradients at fixed BB: the window where p=∞p=\infty is preferred grows with BB, as predicted, and Table 2 predicts where it ends (the third row of Table 2).

So even when both the geometry (L∞R∞2<L2R22L_\infty R_\infty^2<L_2R_2^2) and the noise structure (rank-one noise, so that σ1,2σ2=1\frac{\sigma_{1,2}}{\sigma_2}=1) favor a Schatten-∞\infty based optimizer such as Muon, there is a regime, N≳dN\gtrsim d, in which p=2p=2 attains a smaller loss.

Further changes.

  • Tighter noise bound for p→∞p\to\infty. The noise assumption now lets us measure the noise in any Schatten-ss norm with s∈[1,r]s\in[1,r] (e.g., the nuclear norm under bounded variance). This removes the dimension factor for low-rank noise. But even in that case, the low-dimensional regime still favors p=2p=2, which is what the middle panel of Figure 3 experimentally confirms.
  • Large batch size: The large batch size benefit for p→∞p\to\infty is now much more apparent and it persists even under the accelerated rates (in fact all results in the main text are now based on the accelerated rates). This might seem at odds with the batch size rule showing that p=2p=2 admits a larger batch size than p→∞p\to\infty. However, the rule gives the largest batch size optimizing the complexity, while a much smaller batch size is already optimal for p=2p=2, so only p→∞p\to\infty benefits from the large batch.
  • Scaling laws. We propagate the updated regime discussion to the Chinchilla scaling section, which adds an additional qualifier, namely that the low dimensional regime is entered if the batch size is not grown fast enough (specifically slower than N2/3N^{2/3}).

(Davis and Drusvyatskiy 2025) "When do spectral gradient updates help in deep learning?"

The geometry selection conclusions are stronger than the upper-bound comparisons

We agree that the geometry selection compares upper bounds. However, we believe the comparison is tight, since the worst case is attained. We now show this explicitly on the random-feature model. There, L2R22L_2R_2^2 exceeds L∞R∞2L_\infty R_\infty^2 by a factor that grows linearly in dd, which is the largest possible separation. The transition between geometries also occurs where the theory predicts (Section 5).

the conclusion also depends on noise, smoothness, and distance to the optimum scale with model size.

The conclusion now rests on a sufficient condition that does not depend on these quantities. Specifically, the low-dimensional regime n≳dn\gtrsim d, in which p=prp=p_r is preferred is independent of the noise level, smoothness or distance to the optimum.

Using a single matrix's rank as the effective dimension of the full training problem need further justification as well.

The Chinchilla scaling now reaches the low-dimensional regime provided the batch size is small enough (B≲N2/3B\lesssim N^{2/3}). Even if depth was accounted for in the rank through rank⁡(diag(W1,…,WD))\operatorname{rank}(\mathrm{diag}(W_1,\dots,W_D)), it would only change the batch size requirement (to B≲N1/3B\lesssim N^{1/3} specifically).

The statement that larger p favor larger batch sizes needs qualification since acceleration is the main new contribution

All results in the main text are now based on the accelerated result. As explained above, even though p=2p=2 can enjoy a larger critical batch size we still conclude (maybe counterintuitively) that p=∞p=\infty becomes favorable in the large batch size setting.

The conclusions also overstate the impact of deep learning behavior. Guarantees assume convexity

We agree that our assumptions only provide a model for what is happening in practice and we have toned down the conclusion to only state that the analysis provides a possible explanation for the empirical observations.

Strictly speaking, our analysis only requires star-convexity and Hölder co-coercivity along the trajectory. We work in this setting because it lets us bound the loss gap f(xn)−f⋆f(x^n)-f^\star itself, which is what we ultimately care about in practice. Since the loss gap is the same in every geometry, it also gives us a geometry-free criterion for comparing p=2p=2, p→∞p\to\infty and the intermediate pp.

Questions

"optimal geometry"

We are indeed comparing upper bounds on the loss f(x)−f⋆f(x)-f^\star (this geometry-free comparison is made possible by star-convexity). The comparison is now illustrated on a concrete problem instance, the random-feature model. It attains the worst-case separation L∞R∞2≍L2R22/dL_\infty R_\infty^2\asymp L_2R_2^2/d and has σ1,2=σ2\sigma_{1,2}=\sigma_2, both of which are the best case for Schatten-∞\infty. Even so, p=2p=2 is preferred once N≳dN\gtrsim d, as the bounds predict.

How should the increasing batch exponent in Table 2 be reconciled with the decreasing accelerated exponent in Table 3?

The main text is now based entirely on the accelerated result. The batch size rule is the largest batch size that preserves the oracle complexity. Although this critical batch size is larger for p=2p=2, at a fixed large batch size p=∞p=\infty is still favored, as explained above.

Can the authors give a practical experiment supporting the predicted change in preferred geometry as N/d varies under a common oracle budget?

Yes, see the new Section 5. Under a common oracle budget with per-budget tuning, p=∞p=\infty is preferred for N≲dN\lesssim d and p=2p=2 for N≳dN\gtrsim d, for all d∈{16,32,64,128}d\in\{16,32,64,128\}, both with exact gradients and with rank-one noise.

Is the warmup behaviour in Fig 1 covered by a convergence guarantee for the plotted anytime schedule?

The plotted anytime schedule itself is not covered (see the footnote in Section 3), but the warmup observation is covered by our theory for the fixed-horizon parameterization (Corollary 3.1). There η\eta is constant in kk, and the effective stepsize is λkγkq−1≍ηq−1k(3−p)/(p−1)\lambda_k\gamma_k^{q-1}\asymp\eta^{q-1}k^{(3-p)/(p-1)}. It increases with kk for p<3p<3 (linearly for p=2p=2) and decreases for p>3p>3 (as k−1k^{-1} for p→∞p\to\infty). So the presence of warmup for small pp, and its absence for p→∞p\to\infty, is a property of the guaranteed method.

I apologize to the authors for my late response, and this has been taken into consideration. I have also reviewed the revision in detail.

I appreciate the added crossover experiments, I especially appreciate the effort in the rebuttal. But the rebuttal has not established that the geometry comparison is tight. The experiment shows a large separation and an empirical crossover, but this does not establish that the algorithm errors attain the upper bounds being compared. Especially in a paper like this when the theoretical analysis needs to be clear, solid, without over-claiming, this is a difficult gap for me.

The cited Guzmán–Nemirovski lower bound is also restricted to iteration counts no greater than the relevant dimension, so it does not establish tightness in the n>dn>d setting. In this paper's particular direction, I am unfortunately speaking from a perspective of experience.

If I could, I would set my confidence level to 3.5, since I view 4 as being the global authority on the topic (which I am not). Yet I do have direct experience on this topic. I will maintain my score since I have deep concerns on the presentation of the theoretical analysis. I encourage the authors to take time in revising this work with care, and thank you for the rebuttal.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.