acceptodds
Under review as a conference paper at ICLR 2027

Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates

Abstract

Recently, several instances of non-Euclidean SGD, including SignSGD, Lion, and Muon, have attracted significant interest from the optimization community due to their practical success in training deep neural networks. Consequently, a number of works have attempted to explain this success by developing theoretical convergence analyses. Unfortunately, these results cannot properly justify the superior performance of these methods, as they could not beat the convergence rate of vanilla Euclidean SGD. We resolve this important open problem by developing a new unified convergence analysis under the structured smoothness and gradient noise assumption. In particular, our results indicate that non-Euclidean SGD (i) can exploit the sparsity or low-rank structure of the upper bounds on the Hessian and gradient noise, (ii) can provably benefit from popular algorithmic tools such as extrapolation or momentum variance reduction, and (iii) can match the state-of-the-art convergence rates of adaptive and more complex optimization algorithms such as AdaGrad and Shampoo.

Primary area:
optimization
Keywords:
optimization theory, convex optimization, stochastic optimization

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_PgwMOpenReview ↗
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
  1. 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.
  2. The proposed non-Euclidean analytic framework (discussions around Assumption 5) seems new.
  3. The topic of this paper is timely and should be welcome within the optimization community.
Critical weaknesses
  1. 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 ϵ−4\epsilon^{-4} 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.
  2. I am particularly confused by the comparison with Euclidean SGD. In the convex case, Theorem 1 gives an O~(ϵ−3)\widetilde O(\epsilon^{-3}) bound for normalized SGD, which is not vanilla SGD. A similar ϵ−3\epsilon^{-3} 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 O(ϵ−2)O(\epsilon^{-2}) 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.
  3. 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 ρ\rho in Eq. (1) is identical to that in [4]. For the main examples, this machinery ultimately recovers the familiar ℓ∞/ℓ1\ell_\infty/\ell_1 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.
  4. The discussion of (L0,L1)(L_0,L_1)-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
  1. 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?
  2. Why does normalized SGD have O~(ϵ−3)\widetilde O(\epsilon^{-3}) complexity in the convex case? Eqs. (24)-(25) appear to choose α=Θ(ϵ2)\alpha=\Theta(\epsilon^2) and β=Θ(ϵ3)\beta=\Theta(\epsilon^3) 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 O(ϵ−2)O(\epsilon^{-2}) projected SGD baseline?
  3. 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?
  4. 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.
Reviewer_7YJxOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies Non-Euclidean SGD methods under one unified analysis. Depending on the choice of parameters in the framework (norm, space of operators H\mathcal{H}, etc.), the framework covers many existing algorithms, such as Normalized SGD, SignSGD, Muon, and others. The paper focuses on the constrained optimization problem and uses a Frank-Wolfe-like gap as a convergence criterion, which can also be converted to the function gap if the objective is convex. The paper provides sufficient conditions for convergence of the algorithm for three types of momentum construction (12a)-(12c) and weight decay. Depending on the choice of the momentum, the convergence is accelerated. Finally, the paper compares several special cases to demonstrate when one or another instance of the algorithm is faster.

Critical strengths
  • The paper provides a unified convergence analysis that includes many variants of existing algorithms. Importantly, the convergence analysis is treated in a unified manner: only the choice of momentum estimator implies some changes. This paper provides a very technical treatment of the algorithms but uses the same theoretical framework for all of them.

  • The convergence analysis is well written. All steps are explained with sufficient detail.

Critical weaknesses
  • The claims made in the paper are not entirely novel. Earlier works like [Carlson et al., 2015] and [1] already focused on the difference in the choice of the norm in the convergence analysis. This paper goes in a similar direction, but covers more algorithms. However, the style of the argument remains the same. The authors are encouraged to give credit to prior work and highlight main differences.

  • Due to the high technicality of this work, the text is very overloaded. I understand that to cover many algorithms under one umbrella, such generality is necessary, but it makes the understanding less clear. I encourage the authors to include some illustrative figures or descriptions of special cases to connect the notation to specific properties of the analysis. For example, it is not clear why

    • It is unclear why Assumption 5 is needed. It would be good to cover some special cases to provide an understanding of the restrictiveness of such an assumption.
    • It is unclear why we need to define the norm in such a complicated form given in (1). Again, giving some examples would make it clearer.
    • Comparison on page 9 msotly focuses on matrices M,L,Σ\mathbf{M}, \mathbf{L}, \mathbf{\Sigma}. It does not discuss how matrix T\mathbf{T} differentiates the algorithms. This questions whether such generality is actually needed to make the statements.
  • It is important to connect the conditions under which one or another algorithm is faster to practice. For example, when describing the conditions for when SignSGD is faster than Normalized SGD, it would be beneficial to provide examples when they are (not) satisfied, to give some guidance for practitioners on optimizer choice. Without such guidance, it is completely unclear whether they can be satisfied in practice, and if they are satisfied, whether the performance of the algorithms can be explained by the current analysis. Otherwise, claims like "explain the superior practical performance" are not justified.

  • Though the analysis is very general, the main steps in the analysis mirror those used in [Kovalev, 2025b]. The authors are encouraged to provide

  • It would also be beneficial to add supporting experiments to provide additional evidence for the comparison on page 9. The comparison is based on the worst asymptotic terms in the rate. However, whether those terms are dominant in practice remains undiscussed. Giving empirical results to support such a comparison would make the comparison more justified. I understand that the main contribution of this work is a unified theoretical analysis of existing algorithms, but adding some experiments would show that the analysis is predictive and indeed explains some practical observations. Without such empirical results, claims like "explain the superior practical performance", again, are not justified.

  • The comparison of algorithms is based on upper bounds. It is not clear whether such upper bounds are tight. The authors are encouraged to discuss the tightness of the analysis for the validity of the comparison. If the bounds are loose, such a comparison is limited.

[1] Balles, Lukas, Fabian Pedregosa, and Nicolas Le Roux. "The geometry of sign gradient descent." arXiv preprint arXiv:2002.08056 (2020).

Questions for authors
  • I believe there are missing bold symbols in equations (36)-(37).

  • Can the authors discuss the tightness of the analysis? Can it be improved?

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

The paper provides a unified analysis of non-euclidean SGD optimizers. The authors consider 33 broad optimization schemes derived from an abstract linear minimization oracle in Algorithm 1. The 33 broad schemes apply momentum, momentum + extrapolation and momentum +variance reduction to the output of this linear minimization oracle, which takes as input a noisy gradient.

The goal is to minimize min⁡x∈Qf(x)\min_{x\in Q} f(x), where QQ can be a constrained or unconstrained set of ρ(x)≤R,∀x∈Q\rho(x) \leq \mathcal{R}, \forall x\in Q. Based on this norm function ρ\rho, the authors can define a dual norm, ρ⋆\rho^\star, appropriate smoothness (A1) and noise variance assumptions (A2). For momentum + extrapolation they need second-order smoothness (A3) and for momentum + VR, they need noisy gradients to be Lipschitz (A4). All these assumptions are norms in terms of linear operators L,Σ,T,ML, \Sigma, T, M. Assumption A5 on these operators ensure that (A1) - (A4) in the non-euclidean setting resemble the corresponding assumptions in euclidean settings, with the norms replaced by ρ\rho, and those of the operators L,Σ,T,ML, \Sigma, T, M.

In Table 1, the authors show that specific instantiations of these norms and operators can recover NormalizedSGD, SignSGD and Muon within the same framework. Further, as their framework builds on top of the unified analysis of adaptive algorithms in (Kovalev et al 2025a), this shows adaptive counter-parts for these 33 algorithms.

For non-convex and convex objectives, the authors provide convergence rate for these 33 broad optimization schemes in Theorems 1, 2 and 3, and summarized in Table 2. Further, in Table 3 and Section 3.3, they compare momentum + VR of their setup to the adaptive meta-algorithm rates of (Kovalev et al 2025a), and find conditions under which these are comparable. Additionally, in Section 3.3, they compare Muon and SignSGD to Normalized SGD and establish conditions under which these non-euclidean methods outperform Normalized SGD.

Critical strengths
  • Unified Analysis: Their unified analysis has 3 main components-- i) generic LMO oracle, ii) non-euclidean norm operator, iii) defining smoothness and noise variances in terms of this norm. This analysis allows them to handle non-euclidean optimizers. Further, their algorithm provides 33 broad options -- momentum, momentum +extrapolation and momentum + VR, which allows them to handle a much larger class of optimizers.

  • Straightforward Analysis: Once the setup of this unified analysis and requisite norms is developed, the subsequent analysis is pretty straightforward and easy to understand. First, they use an equivalent of standard smoothness to bound gradient norms (in their case, the Frank-Wolfe Gap) in terms of function suboptimality and deviation of momentum from the true gradient (Lemma 7). Then, they recursively bound the deviation of momentum and true gradient (Lemma 8,9,10), unroll it (Corollaries 1,2,3) and then plug in the criteria for non-convex and convex case.

  • Benefits of Non-Euclidean over Euclidean methods and equivalence to adaptive methods: The authors provide exact conditions under which their non-euclidean methods outperform the euclidean method Normalized SGD, while existing works could not show this improvement. They also provide some explanation of how existing works fail in Appendix A. Further, with the equivalence between their framework and (Kovalev 2025a), they show that their methods perform similar to adaptive methods.

Critical weaknesses
  • **Are existing explanations of Non-Euclidean methods really insufficient?**In the abstract, main contributions, and Appendix A, the authors state that no existing analysis of non-euclidean methods can beat vanilla SGD. However, when the authors themselves compare their results for non-euclidean methods to Normalized SGD in Section 3.3, they can show an improvement under conditions on the noise variance, and smoothness. They say that this "aligns and complements the existing theory" in (Liu et al 2024b, Jiang et al 2024a, An et al 2025). Note that the difference between these methods is due to the different norms of smoothness and noise in the convergence rates, not the ϵ\epsilon-dependence. Further, these existing papers that the authors cite actually show similar conditions under which these non-euclidean methods perform better. Either the authors should not make this claim that no existing work has shown this, or they should precisely state how existing works show improvement and how their analysis is more precise. Further, the analysis in Appendix A never mentions (Liu et al 2024b, Jiang et al 2024a) and (An et al 2025b). I think using "extra dimension factors" as the reason to dismiss (Jiang et al 2024b) does not make sense if the main improvement that the authors show is also due to more accurate dimension factors. A much more reasonable way to present these results would be in a Table, comparing the precise convergence rates from all these papers and the authors analysis for Muon, SignSGD and Normalized SGD.

  • Presentation needs to be improved: Section 3.3 which seems like one of the most important parts of the paper is moved to the end, while intermediate results like Corollaries 1-3, which can be easily inferred from their corresponding Lemmas are kept in the main paper. Further, I think Appendix A contains important comparisons which form the main message of the paper so it would be better to keep them in the main draft. Additionally, the convergence analysis for each of Eq (12a-c) does not need to be presented individually. I think presenting the full analysis for one of these cases, and stating the final results for the remaining cases in the main paper might be a better approach. Right now, Lemmas 6,7 and 9,10 don't add much to the understanding of the full method.

  • Case of R→∞\mathcal{R}\to \infty for convex case and ∣∣x⋆∣∣|| x^\star || in Section 3.3: In Theorems 1,2,3, it seems like for convex objectives, you need finite R\mathcal{R}, other wise the step size goes to 00 and number of iterations blows to ∞\infty. If you analyze standard SGD on convex functions, you only need to bound initial iterate sub-optimality rho(x0−x∗)rho(x_0-x*), not all iterates. Then, in Section 3.3, when comparing SignSGD, Muon and NormalizedSGD, you actually use the result of initial iterate suboptimality, which you have not proved, and plug in x0=0x_0 =0. I think you should make this distinction clear and only use what you have proved.

  • Comparison to (Pethick et al 2025): The general framework of these two papers match, both of them use an LMO, an arbitrary norm for progress and smoothness. I think the authors should clarify the main differences to this framework. To me, it looks like using the arbitrary norm for noise covariance, extrapolation and VR seem to be the main extensions over this paper.

Overall, I'm positive about this paper, as long as the 1st,3rd and 4th weaknesses are addressed.

Questions for authors
  • Why doesn't the framework include vanilla SGD, not Normalized SGD? Could the authors clarify on common cases which are not covered by this framework and why?
  • In Appendix A, the authors provide reasons for why existing analyses are not tight? Could the authors explain how their framework makes this tight?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.