- 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 -uniformly convex one. This makes the analysis cover and Schatten- geometries for .
For smooth convex objectives with a gradient-variation noise assumption, they prove an accelerated rate . They also give Hölder-smooth extensions. With mini-batches and -moment noise they derive oracle complexities and a batch rule for the non-accelerated method. At this recovers .
They then assume the problem is smooth in the -geometry and compare upper bounds across p. Their conclusion is that a smaller can be better when the oracle budget exceeds the dimension . 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 to is also proposed. There are no experiments.
Critical strengths
- 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- 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.
- 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
-
The regime-dependent conclusions seem stronger than the evidence supports. The guarantees comparison is based on the worst case relationships and , treating them as if they were equalities. Footnote 2 defines the -geometry as "natural" when is smallest at . In that case with . The finite- bound then beats the bound once , so the crossover lies anywhere between and . The paper’s is the worst-case endpoint. The claim that smaller wins for is the better-founded direction, since the finite- guarantee is smaller even in the worst case. It is still a comparison of guarantees, not of performance. The claim that is preferred for needs the worst case to be attained, and no lower bound shows this. If is close to 1, smaller wins at every . 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.
-
Contribution (ii) presents , increasing with , as the batch rule. That is the non-accelerated rule. Under the accelerated parameterization (Table 4) the exponent decreases with . For 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 , 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
-
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.
-
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?
-
Can the authors provide intuition for why the optimal batch size increases with in the non-accelerated regime but decreases with under the accelerated parameterization?
-
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?
-
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
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 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 , and the intermediate , 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 prescription: (our ), and (our with )
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 (), weight decay (parameterized by when ) and the use of different geometries (), all in a way where their impact can be understood theoretically."
Can the authors provide intuition for why the optimal batch size increases with in the non-accelerated regime but decreases with under the accelerated parameterization?
Under a fixed budget , a larger batch size leaves fewer iterations. The stochastic term, , penalizes iterations more for larger , so without acceleration, where the deterministic term is the same for all , larger prefers a larger batch size. With acceleration, on the other hand, the deterministic term decays faster for smaller , so smaller 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 -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 cancels exactly against the negative smoothness term, since both have the same exponent. For the regret term has exponent , so one has to carefully trade off the two terms. This is what leaves us with the 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, grows linearly in relative to , as in the worst case . 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 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 would become suboptimal.
Thank you for the detailed rebuttal and the substantial revision. These changes address my main concerns, and I raise my score.
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 n iterations with a fixed batch size B, which makes the regimes much easier to interpret (Table 2):
A phase diagram (Figure 2) shows these regions over B and n/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, L2R22 and L∞R∞2 can be computed exactly, and we confirm that L2R22/(L∞R∞2) grows linearly in d, matching the worst case L2R22≤dL∞R∞2 up to a constant. So the problem has ∞-norm geometry, with the largest possible separation. We compare SODA with p=2 and p=∞ (Muon), with step sizes tuned per oracle budget, in three settings:
So even when both the geometry (L∞R∞2<L2R22) and the noise structure (rank-one noise, so that σ1,2/σ2=1) favor a Schatten-∞ based optimizer such as Muon, there is a regime, n≳d, in which p=2 attains a smaller loss.
(Davis and Drusvyatskiy 2025) "When do spectral gradient updates help in deep learning?"
We now show that this worst case is attained in a concrete example:
The new experiments on this model confirm that the resulting predictions hold for a concrete example and that the transition from p=∞ to p=2 dominating occurs where Table 2 predicts.
All discussion in the main text is now based on the accelerated rate. Even though p=2 allows a larger critical batch size than p→∞, we can still (perhaps counterintuitively) conclude that a large batch size favors p→∞. This is because, while the critical batch size of p=2 is larger, p=2 already attains its optimal rate at a smaller batch size. In contrast, p→∞ benefits from a larger batch size, because batching shrinks its stochastic term until the comparison is decided by the deterministic term, where p→∞ is favored for n≲d.