Research map / Optimization / Nonconvex and smooth optimization

Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimization

NeurIPS 2026 · Optimization › Nonconvex and smooth optimization · approach: Coordinate and Adam convergence analysis

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that gradient orthogonalization (Muon) is a non-Euclidean trust-region method with spectral norm, derives a stochastic non-Euclidean trust-region method with momentum (plus weight decay and extrapolation variants) recovering Muon, normalized SGD and signSGD, and proves convergence rates for non-convex, star-convex and second-order smooth settings.

Problem

Muon and gradient orthogonalization work empirically well for training deep networks, but lack theoretical understanding and convergence guarantees; the difference from Orthogonal-SGDM is also unexplained.

Approach

Reinterprets gradient orthogonalization exactly as a first-order trust-region method whose trust region is a spectral-norm ball, then builds a stochastic non-Euclidean trust-region method with momentum (and variants with weight decay and extrapolation) that covers Muon, normalized SGD and signSGD, with new complexity bounds for arbitrary norms and regularizers.

Key results

• Stochastic non-Euclidean trust-region method with momentum achieves 1/eps^4 complexity for non-convex functions, giving the first convergence result for Muon.
• With weight decay under star-convexity, complexity improves to 1/eps^3, versus 1/eps^3.5 previously known for normalized SGD/signSGD with second-order smoothness.
• Adding extrapolation under second-order smoothness yields 1/eps^3.5 complexity for non-convex functions.

Surprising findings

• Gradient orthogonalization is equivalent to a trust-region step, not plain gradient descent in the spectral norm as previously claimed; the earlier interpretation has an extra nuclear-norm factor.

Limitations

• Purely theoretical; no experiments are reported in the provided text.
• Star-convex and non-convex results rely on assumptions (star-convexity, bounded domain of regularizer) that may not hold in practice.
• Whether extrapolation improves Muon's convergence remains open.

Experimental setup

Metrics: expected stationarity measure functional suboptimality iteration complexity

Baselines: Muon Orthogonal-SGDM normalized SGD with momentum signSGD with momentum

Builds on: Muon normalized SGD with momentum signSGD with momentum Orthogonal-SGDM

Closest papers by meaning

• Trust Region Methods for Nonconvex Stochastic Optimization beyond Lipschitz Smoothness (AAAI 2024 · similarity 0.87)
• On orthogonality and learning recurrent networks with long term dependencies (ICML 2017 · similarity 0.86)
• How to Make the Gradients Small Privately: Improved Rates for Differentially Private Non-Convex Optimization (ICML 2024 · similarity 0.84)
• SUMO: Subspace-Aware Moment-Orthogonalization for Accelerating Memory-Efficient LLM Training (NeurIPS 2025 · similarity 0.84)
• Stacey: Promoting Stochastic Steepest Descent via Accelerated $\ell_p$-Smooth Nonconvex Optimization (ICML 2025 · similarity 0.83)
• Generalized Gradient Norm Clipping & Non-Euclidean $(L_0,L_1)$-Smoothness (NeurIPS 2025 · similarity 0.83)