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

arXiv: https://arxiv.org/abs/2511.11466 · HTML: https://mlsanity.com/paper/2511.11466/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 63 references that are in the map.
- First posted on arXiv 14 Nov 2025.

## Builds on (most cited first, 30 of 46)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Kimi K2: Open Agentic Intelligence](https://mlsanity.com/paper/2507.20534/) (2025)
- [GLM-4.5: Agentic, Reasoning, and Coding (ARC) Foundation Models](https://mlsanity.com/paper/2508.06471/) (2025)
- [Symbolic Discovery of Optimization Algorithms](https://mlsanity.com/paper/2302.06675/) (2023)
- [Muon is Scalable for LLM Training](https://mlsanity.com/paper/2502.16982/) (2025)
- [Shampoo: Preconditioned Stochastic Tensor Optimization](https://mlsanity.com/paper/1802.09568/) (2018)
- [Why gradient clipping accelerates training: A theoretical justification for adaptivity](https://mlsanity.com/paper/1905.11881/) (2019)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [Training Deep Learning Models with Norm-Constrained LMOs](https://mlsanity.com/paper/2502.07529/) (2025)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Momentum Improves Normalized SGD](https://mlsanity.com/paper/2002.03305/) (2020)
- [Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimization](https://mlsanity.com/paper/2503.12645/) (2025)
- [Muon Optimizes Under Spectral Norm Constraints](https://mlsanity.com/paper/2506.15054/) (2025)
- [Gluon: Making Muon & Scion Great Again! (Bridging Theory and Practice of LMO-based Optimizers for LLMs)](https://mlsanity.com/paper/2505.13416/) (2025)
- [The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2202.05791/) (2022)
- [ASGO: Adaptive Structured Gradient Optimization](https://mlsanity.com/paper/2503.20762/) (2025)
- [PolarGrad: A Class of Matrix-Gradient Optimizers from a Unifying Preconditioning Perspective](https://mlsanity.com/paper/2505.21799/) (2025)
- [Lion Secretly Solves Constrained Optimization: As Lyapunov Predicts](https://mlsanity.com/paper/2310.05898/) (2023)
- [Muon Outperforms Adam in Tail-End Associative Memory Learning](https://mlsanity.com/paper/2509.26030/) (2025)
- [Generalized-Smooth Nonconvex Optimization is As Efficient As Smooth Nonconvex Optimization](https://mlsanity.com/paper/2303.02854/) (2023)
- [MuonBP: Faster Muon via Block-Periodic Orthogonalization](https://mlsanity.com/paper/2510.16981/) (2025)
- [Structured Preconditioners in Adaptive Optimization: A Unified Analysis](https://mlsanity.com/paper/2503.10537/) (2025)
- [SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance](https://mlsanity.com/paper/2302.08783/) (2023)
- [An Exploration of Non-Euclidean Gradient Descent: Muon and its Many Variants](https://mlsanity.com/paper/2510.09827/) (2025)
- [Beyond the Ideal: Analyzing the Inexact Muon Update](https://mlsanity.com/paper/2510.19933/) (2025)

## Built on by (most cited first, 8 of 8)

- [Symmetry-Compatible Principle for Optimizer Design: Embeddings, LM Heads, SwiGLU MLPs, and MoE Routers](https://mlsanity.com/paper/2605.18106/) (2026)
- [A Tale of Two Geometries: Adaptive Optimizers and Non-Euclidean Descent](https://mlsanity.com/paper/2511.20584/) (2025)
- [Ky Fan Norms and Beyond: Dual Norms and Combinations for Matrix Optimization](https://mlsanity.com/paper/2512.09678/) (2025)
- [Communication-Efficient Gluon in Federated Learning](https://mlsanity.com/paper/2604.10689/) (2026)
- [Free Heavy-Tailed Lunch for Muon: A Theoretical Justification of Empirical Success](https://mlsanity.com/paper/2606.14560/) (2026)
- [Optimal Projection-Free Adaptive SGD for Matrix Optimization](https://mlsanity.com/paper/2604.02505/) (2026)
- [Distance-Aware Muon: Adaptive Step Scaling for Normalized Optimization](https://mlsanity.com/paper/2605.18999/) (2026)
- [Stochastic Non-Smooth Convex Optimization with Unbounded Gradients](https://mlsanity.com/paper/2605.15522/) (2026)

## Abstract (arXiv)

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.