- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies non-Euclidean SGD with momentum and weight decay under structured smoothness and noise assumptions. The framework encompasses various non-Euclidean optimizers including normalized SGD, SignSGD, and Muon. The authors analyze a general algorithmic frameworking that contains ordinary momentum, momentum with extrapolation, and variance reduction. The main takeaway is that these methods can exploit structure in the smoothness and noise operators, yielding better convergence guarantees than their Euclidean counterparts. No experiments are provided.
Critical strengths
- The paper brings several non-Euclidean optimizers into one framework, with results for both convex and non-convex problems. The inclusions of momentum and variance reduction under both convexity and non-convexity are concrete contributions.
- The proposed non-Euclidean analytic framework (discussions around Assumption 5) seems new.
- The topic of this paper is timely and should be welcome within the optimization community.
Critical weaknesses
- I find the distinction from prior work insufficiently clear. The matrix smoothness and noise conditions in Eq. (36), and the low-rank smoothness/noise versus high-rank solution argument following Eq. (37), substantially overlap with ASGO [1]. For the vector case, the finite variance special cases of [2] also cover the coordinate-wise and matrix assumptions used in the discussion and already give the same leading non-convex dependence for SignSGD and Muon (with closely related structural factors). Although the convex bounds in Eqs. (35) and (37) were not proved in [1] or [2], but the paper should explain much more precisely which conclusions and proof steps are new, rather than presenting the structural advantage itself as a new explanation.
- I am particularly confused by the comparison with Euclidean SGD. In the convex case, Theorem 1 gives an bound for normalized SGD, which is not vanilla SGD. A similar bound was already established for non-Euclidean trust region SGD with momentum under star convexity in [3]. More importantly, this is not the optimal complexity of the underlying smooth convex stochastic optimization problem: standard projected SGD (with averaging) achieves stochastic oracle complexity under the usual bounded-variance assumptions. Even last-iterate stochastic gradient methods can achieve this dependence under suitable step-size schedules [5]. Thus, improving the constants over normalized SGD in Eqs. (35) and (37) does not by itself establish an advantage over vanilla SGD. The paper's claims about outperforming Euclidean SGD need a more careful, like-for-like comparison.
- I am not convinced that the operator space formulation in Section 2.2 adds enough to justify its complexity. As the authors acknowledge in Section 2.2, Assumption 5 is similar to the structural assumption in [4], and the definition of in Eq. (1) is identical to that in [4]. For the main examples, this machinery ultimately recovers the familiar and spectral/nuclear norm pairs. Putting these cases under one notation is useful, but a unified presentation is not automatically a new technical contribution. I would like to understand which part of the analysis genuinely requires this operator-space viewpoint, rather than following from existing non-Euclidean arguments combined with known structured smoothness and noise bounds. At present, the additional value of the abstraction is not made clear.
- The discussion of -smoothness and affine variance is also unconvincing. The authors acknowledge that these assumptions may be more realistic, but then state that "applying the techniques from our paper to generalized variants of Assumptions 1 and 2 should be straightforward" without any supporting argument. I would not take such an extension for granted because they would change the descent and momentum error estimates used throughout the proofs. If the extension really is straightforward, a short derivation or even one representative result in the appendix would be helpful. Otherwise, it would be better to leave it as an open direction rather than dismiss the technical details in passing.
References
[1] ASGO: Adaptive Structured Gradient Optimization. NeurIPS, 2025.
[2] Sign-Based Optimizers Are Effective Under Heavy-Tailed Noise. arXiv:2602.07425, 2026.
[3] Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimization. arXiv:2503.12645, 2025.
[4] SGD with Adaptive Preconditioning: Unified Analysis and Momentum Acceleration. arXiv:2506.23803, 2025.
[5] Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods. ICLR, 2024.
Questions for authors
- Could the authors provide a theorem-level comparison with [1-4], especially for Eqs. (34)-(37) and Theorems 1-3? Which specific parts of the analysis cannot be recovered from the existing structural bounds and non-Euclidean momentum arguments?
- Why does normalized SGD have complexity in the convex case? Eqs. (24)-(25) appear to choose and in the noise dominated regime. Is the resulting rate known to be unavoidable for this particular algorithm, or could it reflect looseness in the analysis? How do the claimed advantages compare with the standard projected SGD baseline?
- Theorem 3 uses Assumption 4 (mean-square Lipschitz stochastic gradients), whereas the adaptive method comparison in Table 3 relies on different assumptions. How much of the reported improvement survives when the assumptions and gradient evaluation costs are matched?
- Could the authors define the projection in Assumption 5 precisely and show at least one worked extension to generalized smoothness or affine variance? If these extensions require additional conditions, that would also be worth clarifying.