When and Why SignSGD Outperforms SGD: A Theoretical Study Based on ℓ1-norm Lower Bounds
arXiv:2605.06615v1 [cs.LG] 7 May 2026
1
Hongyi Tao1,* Dingzhi Yu1,2,* Lijun Zhang1,2 State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210023, China 2 School of Artificial Intelligence, Nanjing University, Nanjing 210023, China [email protected],{yudz,zhanglj}@lamda.nju.edu.cn * Equal Contribution
Abstract Sign-based optimization algorithms, such as SignSGD and Muon, have garnered significant attention for their remarkable performance in training large foundation models. Despite this empirical success, we still lack a theoretical understanding of when and why these sign-based methods outperform vanilla SGD. The core obstacle is that under standard smoothness and finite variance conditions, SGD is known to be minimax optimal for finding stationary points measured by ℓ2 -norms, thereby fundamentally precluding any complexity gains for sign-based methods in standard settings. To overcome this barrier, we analyze sign-based optimizers leveraging ℓ1 -norm stationarity, ℓ∞ -smoothness, and a separable noise model, which can better capture the coordinate-wise nature of signed updates. Under this distinct problem geometry, we derive matched upper and lower bounds for SignSGD and explicitly characterize the problem class in which SignSGD provably dominates SGD. Specifically, we compare the upper bound of SignSGD with the lower bound of SGD, illustrating that SignSGD effectively reduces the complexity by a factor of d under sparse noise, where d is the problem dimension. Furthermore, we elevate this framework to the matrix domain, providing an equivalent optimal lower bound for the Muon optimizer, proving that extending the sign operator to matrices preserves this optimal scaling with dimensionality. Finally, we bridge our theoretical bounds to practice, demonstrating that the theoretical superiority of SignSGD accurately predicts its faster convergence during the pretraining of a 124M parameter GPT-2 model. Code is available at https://github.com/ Dingzhen230/SignSGD_Outperforms_SGD.
1
Introduction
Efficient and scalable stochastic optimization algorithms play an indispensable role in the huge success of large foundation models [Devlin et al., 2019, Brown et al., 2020, Achiam et al., 2023, Touvron et al., 2023, Team et al., 2023]. Among these, sign-based optimization algorithms, such as SignSGD [Bernstein et al., 2018] and Muon [Jordan et al., 2024], have attracted increasing focus due to substantial empirical edges over stochastic gradient descent (SGD) [Robbins and Monro, 1951]. SignSGD leverages 1-bit signed gradient to update the model, which naturally enjoys many favorable empirical properties in distributed environments [Bernstein et al., 2019] and low-precision training regimes [Yu et al., 2026a]. Muon optimizes using the matrix sign operator, implemented via Newton–Schulz iterations [Kovarik, 1970, Björck and Bowie, 1971]. Numerous empirical studies [Liu et al., 2025, Shah et al., 2025, Wen et al., 2025, Semenov et al., 2025] have shown its consistent speedup over AdamW [Loshchilov and Hutter, 2019], and it has become a new industrial paradigm for pretraining massive-scale large language models (LLMs) [Team et al., 2025, 2026, Zeng et al., 2025, 2026, Cheng et al., 2026, DeepSeek-AI, 2026]. Preprint.
The empirical success of sign-based optimizers has motivated a fruitful line of work that attempts to justify their advantages theoretically. From an optimization theory perspective, the convergence of sign-based methods under various assumptions has been extensively studied [Bernstein et al., 2018, 2019, Safaryan and Richtárik, 2021, Sun et al., 2023, Jiang et al., 2025b, Yu et al., 2026b]. However, a complete theoretical understanding of why sign-based optimizers outperform SGD remains elusive. The biggest obstacle preventing any theoretical advances is that SGD is already worst-case optimal when the objective function is smooth and stochastic gradients are unbiased with bounded variance [Arjevani et al., 2023]. Under these standard assumptions, any first-order algorithm requires at least Ω(ϵ−4 ) queries to find an ϵ-stationary point measured by the ℓ2 -norm, a complexity tightly matched by SGD [Ghadimi and Lan, 2013]. Consequently, evaluating the performance of sign-based methods under the aforementioned problem class and ℓ2 -stationary measure inherently fails to deliver any provable gains we desire. In this paper, we systematically investigate when and why sign-based methods can outperform SGD by delving into a new problem class and performance measure that depart from the canonical setting in Arjevani et al. [2023]. Specifically, instead of the traditional ℓ2 -geometry based on ℓ2 smoothness, finite variance, and ℓ2 -stationarity, we consider an ℓ∞ -geometry with ℓ∞ -smoothness, coordinate-wise finite variance, and ℓ1 -stationarity. This geometry shift is motivated by the insight that sign-based updates are intrinsically aligned with ℓ∞ -geometry [Balles et al., 2020, Bernstein and Newhouse, 2024, Xie et al., 2025a,b]. Under this alternative geometry, we provide the first rigorous characterization of a problem class in which SignSGD provably outperforms SGD. To clarify this geometric shift, it is essential to highlight the distinction between these conditions. Standard ℓ2 -smoothness assumes the loss landscape curves uniformly across all directions, while ℓ∞ smoothness bounds the gradient change based on the maximum coordinate-wise distance, providing a hypercube-based geometric assumption that aligns with coordinate-wise, scaled updates of sign-based methods. Define Df (x, y) := f (y) − (f (x) + ⟨∇f (x), y − x⟩) as Bregman Divergence of f , the above two smooth model can be expressed as |Df (x, y)| ≤
L2 ∥y − x∥22 , 2
ℓ2 -smoothness;
|Df (x, y)| ≤
L∞ ∥y − x∥2∞ , 2
ℓ∞ -smoothness.
Furthermore, we adopt a separable noise model where variance is tracked independently for each coordinate via a vector σ = [σ1 , σ2 , . . . , σd ]. This fine-grained characterization is more suitable for analyzing the highly imbalanced noise prevalent in modern deep learning [Sagun et al., 2017, Zhu et al., 2019, Zhang et al., 2020, Pan et al., 2022, Wu et al., 2022, Pan et al., 2024]: E ∥gtb − ∇f (xt )∥22 Ft−1 ≤ σ 2 , Standard noise model; h i 2 b ∀i ∈ [d], E gt,i − ∇i f (xt ) Ft−1 ≤ σi2 , Separable noise model. Under this refined geometry, we develop a clean, self-contained lower bound analysis for SignSGD. We prove an ℓ1 -norm lower bound that matches its upper bound, thereby giving a tight characterization of its convergence rate. We further derive an ℓ1 -norm lower bound for SGD under the same setting. Comparing the upper bound of SignSGD with the lower bound of SGD reveals a strict separation: when the coordinate-wise noise is sparse or highly heterogeneous, SignSGD achieves a better dimension dependence. Finally, we extend this framework to matrix optimization and establish the first lower bound for Muon measured by the nuclear norm with matching upper bounds. The main contributions of this paper are summarized as follows. • Tight Bounds for SignSGD: Let L∞ and σ denote the ℓ∞ -smooth Lipschitz constant and the noise variance vector, respectively. We establish that pthe convergence rate of SignSGD 1 L∞ ∆/N + ∥σ∥21 L∞ ∆/N 4 . with a constant step size is: E [mint ∥∇f (xt )∥1 ] = Θ • Provable Dimensional Gains of SignSGD over SGD: By comparing SignSGD’s upper bound with SGD’s lower bound, we prove that SignSGD achieves a strictly superior dimension dependence. We show that when the noise σ is sparse, SignSGD’s complexity can be d times better than that of SGD. We validate these theoretical findings by demonstrating accelerated convergence during the pretraining of a 124M-parameter GPT-2 model. • Unified Extension to Matrix Optimizers: We elevate our theoretical framework into the matrix domain, mapping separable operations to orthogonalized matrix steps. By applying 2
spectral norm smoothness and matrix variance, we provide equivalent upper and lower bounds for the recently proposed Muon optimizer [Jordan et al., 2024], proving for the first time that Muon handles large-scale matrix parameters just as effectively as SignSGD handles flat vectors.
2
Related Work
Sign-based methods: vector optimizers The idea of using only gradient signs dates back at least to RProp [Riedmiller and Braun, 1993], while the modern stochastic formulation was introduced by Bernstein et al. [2018], who studied SignSGD and its momentum variant Signum for smooth non-convex optimization. Since SignSGD replaces the stochastic gradient by its coordinate-wise sign, its natural stationarity measure is ℓ1 -norm rather than the usual ℓ2 -norm. This geometry is also closely tied to communication efficiency, as one-bit sign updates and majority vote make SignSGD attractive in distributed learning environments [Bernstein et al., 2019, Jin et al., 2020, Safaryan and Richtárik, 2021]. A fundamental limitation of vanilla sign updates appears in non-smooth optimization. Even for simple convex non-smooth objectives, SignSGD can fail to converge because the discontinuity of the sign map may repeatedly select an unfavorable subgradient direction [Karimireddy et al., 2019, Xiao et al., 2023]. Error feedback repairs this issue by accumulating and correcting compression errors [Karimireddy et al., 2019]. More recently, StoSignSGD [Yu et al., 2026a] takes a different route by injecting unbiased structural stochasticity directly into the sign conversion. Its coordinate-wise max-buffer controls the stochastic sign scale, and its noise level is coupled with the gradient signal. This design preserves the numerical simplicity of sign updates while resolving the non-smooth non-convergence pathology of deterministic SignSGD. In smooth stochastic optimization, a separate line of work sharpens the convergence theory of signbased methods through momentum-based analyses [Sun et al., 2023, Jiang et al., 2025b], stochastic sign mechanisms [Jin et al., 2020, Safaryan and Richtárik, 2021], variance reduction [Chzhen and Schechtman, 2023, Jiang et al., 2024], and heavy-tailed noise analyses [Kornilov et al., 2025, Yu et al., 2026b]. Sign-based vector optimizers are also closely related to adaptive methods. Several works interpret the optimization dynamics of Adam [Kingma and Ba, 2015] through signed or normalized update directions [Balles and Hennig, 2018, Crawshaw et al., 2022, Kunstner et al., 2023, Peng et al., 2025], while Lion [Chen et al., 2023] has emerged as a representative momentum-based sign optimizer with strong empirical performance and growing theoretical support [Chen et al., 2024, Dong et al., 2024, Jiang and Zhang, 2025, Sfyraki and Wang, 2025, Yu et al., 2026b]. Most relevant to our motivation, Yu et al. [2026b] demonstrate that SignSGD- and Lion-type methods can provably outperform AdamW, especially in LLM training regimes where the noise is heavy-tailed [Zhang et al., 2020]. Sign-based methods: matrix optimizers Matrix sign optimizers extend the sign-based philosophy from coordinate-wise vector updates to structured matrix updates. The representative example is Muon [Jordan et al., 2024], which applies an orthogonalized matrix sign direction: for a matrix gradient G = U ΣV ⊤ , the update direction is msign (G) = U V ⊤ . In practice, this matrix sign operation is efficiently approximated by Newton–Schulz iterations [Kovarik, 1970, Björck and Bowie, 1971]. Subsequent variants, such as MuonLight, incorporate Nesterov momentum, learning-rate alignment, and implementation refinements, and have been used or benchmarked in massive-scale language model training [Liu et al., 2025, Zeng et al., 2025, Team et al., 2025, Wen et al., 2025, Semenov et al., 2025, DeepSeek-AI, 2026]. These works suggest that matrix-level normalization can provide optimization benefits beyond coordinate-wise sign updates. Theoretical understanding of Muon and related matrix optimizers is still developing. Existing studies analyze Muon from several complementary perspectives, including spectral and nuclear-norm geometry, normalized matrix descent, preconditioning, connections to Adam-type methods, and empirical justifications for its superiority [Li and Hong, 2025, Shen et al., 2025, Chang et al., 2025, Si et al., 2025, Sfyraki and Wang, 2025, Chen et al., 2025, Huang et al., 2025, Li et al., 2025b, Qian et al., 2025, Tveit et al., 2025, Page et al., 2025, Mehta et al., 2025, Vasudeva et al., 2025a,b, Frans et al., 2025, Pan et al., 2025, Wang et al., 2025, Zhang and Gao, 2025, Zhang et al., 2025, Su, 2025, Crawshaw et al., 2025, Ma et al., 2026, Du and Su, 2026]. Lower complexity bounds Complexity lower bounds are the standard tool for determining whether an apparent algorithmic improvement is genuine or merely an artifact of analysis. The oracle3
complexity viewpoint goes back to the classical framework of Nemirovski and Yudin [1983], and was later developed extensively for stochastic convex optimization [Agarwal et al., 2012]. These results identify how noise, dimension, and geometry constrain the best possible rates in stochastic first-order optimization. For smooth non-convex optimization, the classical target is an ϵ-stationary point measured by ∥∇f (x)∥2 . In the deterministic setting, Carmon et al. [2020, 2021] established sharp lower bounds for finding stationary points of smooth high-dimensional functions, while Chewi et al. [2023] showed that even in one dimension the query complexity depends delicately on whether the algorithm is deterministic or randomized and whether it can access first-order or zeroth-plus-first-order information. In the stochastic setting, Ghadimi and Lan [2013] gave the standard O(ϵ−4 ) upper bound for SGD under unbiased bounded-variance gradients, and subsequent lower-bound work showed that this rate is essentially unavoidable. In particular, Drori and Shamir [2020] studied worst-case lower bounds for SGD itself, and Arjevani et al. [2023] proved that any stochastic first-order method requires Ω(ϵ−4 ) stochastic-gradient queries under the standard bounded-variance model, with a corresponding Ω(ϵ−3 ) lower bound under mean-squared smoothness. Thus, in the usual ℓ2 -geometry, SGD is minimax optimal, and one should not expect a worst-case improvement without changing the geometry, the oracle model, or the stationarity criterion. A more recent line of work asks whether adaptive or sign-based methods can provably improve over SGD once the problem structure is refined. Jiang et al. [2025a] show that this is possible for AdaGrad under coordinate-wise smoothness and coordinate-wise noise assumptions: by adopting an ℓ1 -stationarity measure, they prove both an AdaGrad upper bound and an SGD lower bound, yielding regimes where AdaGrad improves over SGD by a factor of the dimension. Complementarily, Crawshaw and Liu [2025] study lower bounds for adaptive gradient algorithms under (L0 , L1 )-smoothness, showing that several AdaGrad variants necessarily incur higher-order dependence on the relaxedsmoothness parameters.
3
SignSGD: Upper Bound and Lower Bound
In this section, we give the first tight characterization of the convergence of SignSGD. 3.1
Notations and Assumptions
We write [T ] for {1, 2, . . . , T }, |x| for element-wise absolute value of x ∈ Rd . The L-weighted vector norm for L ∈ Rd+ is defined as ∥x∥2L := x⊤ diag(L)x. For vector descent methods, we study the optimization problem minx∈Rd f (x), where f : Rd → R is differentiable. Given a point x ∈ Rd , we can only access the gradient ∇f (x) = [∇1 f (x), · · · , ∇d f (x)] ∈ Rd in a noisy manner which we will later define in Assumption 2a. We use sign (·) to denote the sign operator, and WLOG, use the convention sign (0) = 0, which our lower bound analysis may encounter. Below, we list some necessary assumptions. Assumption 1a (Lower bounded objective). The function f is bounded from below. There exists f ∗ > −∞ such that f (x) ≥ f ∗ , for all x ∈ Rd . We further denote ∆ = f (x0 ) − inf x∈Rd f (x). Assumption 2a (Separable noise model). At step t we observe a mini-batch of mutually independent gradients gt = {gt1 , · · · , gtB } satisfying E gtb |Ft−1 = ∇f (xt ), ∀b ∈ [B] where Ft = σ(g1 , . . . , gt ) denotes the natural filtration. Moreover, the coordinate-wise conditional variance is bounded separably: there exist non-negative constants σ = [σ1 , σ2 , · · · , σd ] such that h i 2 b E gt,i − ∇i f (xt ) Ft−1 ≤ σi2 , ∀i ∈ [d], ∀b ∈ [B]. Assumption 1a is standard and necessary for stochastic non-convex optimization [Arjevani et al., 2023]. Assumption 2a is widely used in analysis of adaptive methods like AdaGrad [Duchi et al., 2011], and sign-based methods like SignSGD [Bernstein et al., 2018, Li et al., 2025a, Jiang et al., 2025a, Yu et al., 2026b]. Assumption 3a (ℓ∞ -smoothness). The objective function f is ℓ∞ -smooth if there exists non-negative constant L∞ such that for all x, y ∈ Rd , we have |f (y) − (f (x) + ⟨∇f (x), y − x⟩)| ≤
4
L∞ ∥y − x∥2∞ . 2
Algorithm 1 SignSGD [Bernstein et al., 2018]
Algorithm 2 Muon [Jordan et al., 2024] 1: Require iteration number T , initial point
1: Require iteration number T , initial point x0 ,
batch size B, learning rate η 2: for step t = 0 to T − 1 do 3: Compute stochastic gradient: PB b 1/B b=1 gt 4: xt+1 = xt − η sign (gt ) 5: end for
W0 , batch size B, learning rate η. gt
2: for step t = 0 to T − 1 do 3: Compute stochastic gradient:
=
Gt
=
PB
b b=1 Gt 4: Wt+1 = Wt − η msign (Gt ) 5: end for 1/B
Assumption 4a (Separable smoothness). The objective function f is L-separable smooth if there exists a non-negative vector L = [L1 , L2 , . . . , Ld ] such that for all x, y ∈ Rd , we have |f (y) − (f (x) + ⟨∇f (x), y − x⟩)| ≤
1 ∥y − x∥2L . 2
Separable smoothness (Assumption 4a) is widely used in analyses of SignSGD methods [Bernstein et al., 2018, 2019, Safaryan and Richtárik, 2021, Yu et al., 2026b], which naturally aligns with sign descent methods due to their separable nature. Balles et al. [2020] further discussed the relationship between Assumptions 3a and 4a, pointing out that the latter is a more generalized assumption. We present the following lemma to formalize this claim, whose proof can be found in Appendix A. Lemma 1. If f is L-separable smooth, then it is also ℓ∞ -smooth with L∞ = ∥L∥1 . 3.2 Upper Bound Theory of SignSGD For completeness, the whole algorithmic procedure of SignSGD is listed in Algorithm 1. Though the upper bounds of SignSGD and its variants under various settings have been widely studied [Bernstein et al., 2018, Karimireddy et al., 2019, Sun et al., 2023, Jiang et al., 2024, 2025b, Jiang and Zhang, 2025, Yu et al., 2026b], we present the upper bound analysis here for consistency of the paper. Theorem 1. Run Algorithm 1 for T iterations under Assumptions 1a to 3a, by setting the hyperparameters as: r 2∆ ∥σ∥21 η= , B = max 1, T . (1) L∞ T ∆L∞ Denote N = BT as the total complexity, Algorithm 1 guarantees: # " r 1 ! T L∞ ∆ ∥σ∥21 L∞ ∆ 4 1X ∥∇f (xt )∥1 = O + . E T t=1 N N
(2)
3.3 Lower Bound Theory of SignSGD After establishing an upper bound for Algorithm 1, we present a corresponding lower bound under the same conditions, which immediately verifies the sharpness of the upper bound in Theorem 1. Theorem 2. Fix T ≥ 1 and a scaling parameter η > 0, and consider running Algorithm 1 for T iterations with batch size B. For any given parameters L∞ , σ, and ∆, there exists a function f : Rd → R and a stochastic gradient oracle such that: 1. f satisfies Assumptions 1a and 3a; 2. the stochastic gradients gt satisfy Assumption 2a; 3. denote N = BT , the iterates generated by Algorithm 1 satisfy r 1 ! L∞ ∆ ∥σ∥21 L∞ ∆ 4 E min ∥∇f (xt )∥1 = Ω + . 0≤t<T N N
(3)
To the best of our knowledge, Theorem 2 is the first known tight lower bound for the SignSGD algorithm that does not depend on the dimension d explicitly. We briefly illustrate our proof techniques below, with the full analysis postponed to Appendix B.2. 5
Proof Sketch. To analyze the complexity of SignSGD, we divide the proof into five main steps. Step 1: Dimensional Decomposition. We first reduce the d-dimensional optimization into d parallel Pd one-dimensional problems by constructing a separable objective function f (x) = i=1 pi (xi ), where xi denotes the i-th coordinate. Utilizing Lemma 1, we can safely distribute the global ℓ∞ smoothness constant L∞ and the suboptimality ∆ across coordinates such that ∥L∥1 = L∞ and Pd i=1 ∆i = ∆. Step 2: Constructing a 1D Resisting Oracle. We establish the worst-case lower bound for a single coordinate by constructing a “resisting oracle” [Nesterov et al., 2018]. Specifically, in the deterministic setting, we design a hard 1D function pi that maintains a constant slope p′i (x) = −ϵ across a sequence of N query points. Consequently, any algorithm that fails to escape this predefined region is strictly prevented from finding an ϵ-stationary point, as the gradient magnitude is uniformly bounded away from zero. Step 3: Inducing Stall via Adversarial Bimodal Noise. To extend the 1D construction to the stochastic setting, we introduce an adversarial noise distribution. We define a specialized gradient oracle σ 2 + ϵ2 ϵ2 σ2 . (4) P gtb = 0 | xt = 2 i 2 , P gtb = i 2 p′i (xt ) | xt = 2 σi + ϵ ϵ σi + ϵ2 This oracle is unbiased and has an exact variance of σi2 . Crucially, this specific noise structure is designed to force the optimizer to stall, so that more total steps are needed to escape from previously defined “resisting oracle” when the variance σi2 is large. We yield a rigorous 1D complexity lower bound under stochastic setting as: (r 1 ) h i L∆ L∆σ 2 4 ′ E min |p (xt )| ≥ C max , . t N N Step 4: Dimensional Lifting and Adversarial Tuning. Finally, we aggregate the 1D lower bounds across all d dimensions. By adversarially tuning the coordinate-wise smoothness (Li ∝ σi ) and the suboptimality (∆i ) subject to their global constraints, we maximize the aggregated lower bound. This step successfully lifts the 1D result to the d-dimensional setting and recovers the exact dependency on ∥σ∥1 as stated in the theorem.
4
Why Sign Operator Works: Comparison Between SignSGD and SGD
In this section, we compare SignSGD with SGD from both theoretical and empirical perspectives. This comparison highlights the role of sign descent beyond its classical interpretation as a gradientcompression mechanism [Bernstein et al., 2018]: under Assumption 3a, the sign operator can also lead to provably improved complexity bounds. 4.1 Theoretical Study: SignSGD Converges Provably Faster than SGD We introduce the following ℓ1 -norm lower bound for SGD, whose proof can be found in Appendix C. This result characterizes the intrinsic hardness faced by SGD under our ℓ∞ -smooth geometry, and therefore serves as the key benchmark for comparing against the upper bound of SignSGD. Theorem 3 (SGD lower bound). Fix T ≥ 1 and a scaling parameter η > 0, and consider running vanilla SGD for T iterations with batch size B = 1. For any given parameters L∞ , σ, and ∆, there exists a function f : Rd → R and a stochastic gradient oracle such that: 1. f satisfies Assumptions 1a and 3a; 2. the stochastic gradients gt satisfy Assumption 2a; 3. the iterates generated by vanilla SGD satisfy r 1 ! dL∞ ∆ d∥σ∥22 L∞ ∆ 4 + . E min ∥∇f (xt )∥1 = Ω T T t∈[T ]
(5)
Proof Sketch. We reduce the claim to the coordinate-wise lower bound of Jiang et al. [2025a]. Under Assumption 4a with smoothness vector L = (L1 , . . . , Ld ) and separable variance vector σ = (σ1 , . . . , σd ), their result gives a hard instance for vanilla SGD as (24). 6
The key observation is that Lemma 1 converts any L-separable smooth function into an ℓ∞ -smooth function with constant ∥L∥1 . Therefore, under the constraint ∥L∥1 = L∞ , the adversary is free to allocate the curvature across coordinates. Optimizing this allocation yields the desired lower bound under Assumption 3a. For the deterministic term in (24), we choose a highly imbalanced smoothness vector, for example L1 ≥ ∥L∥1/2 and ∥L∥1 = L∞ . Then ∥L∥∞ = Ω(L∞ ), and the coordinate-wise lower bound gives ! r dL∞ ∆ . (6) E min ∥∇f (xt )∥1 = Ω T t∈[T ] This shows that, in the worst case, SGD suffers an additional factor d even in the noiseless part of the complexity. For the stochastic allocate the curvature according to the noise profile by setting term in (24), we P 2 d Li = σi /∥σ∥22 L∞ , i ∈ [d] so that i=1 Li = L∞ and it yields that 1/4 ! d∥σ∥22 L∞ ∆ E min ∥∇f (xt )∥1 = Ω . (7) T t∈[T ] The two constructions above give two valid ℓ∞ -smooth hard instances satisfying the same global parameters L∞ , σ, ∆. Taking the worse of them, and using max{a, b} = Ω(a + b) for non-negative quantities a, b, we obtain the result in Theorem 3. Comparison based on density function ϕ(σ). We proceed to compare the rate obtained in Theorem 1, which is the upper bound for SignSGD, and Theorem 3, which is the lower bound for SGD. We define the density function ϕ : Rd → R for noise σ as follows: ∥σ∥21 1 ϕ(σ) = ,1 . (8) ∈ d∥σ∥22 d The above function ϕ is a measure of how “dense” a vector is. ϕ(σ) ≈ 1/d corresponds to highly skewed noise acting on only a few coordinates, whereas ϕ(σ) = 1 represents perfectly uniform noise across all parameters. Now, we are able to compare SignSGD with SGD: to find an ϵ-stationary point in terms of the ℓ1 -norm, the required complexity is L∞ ∆ ∥σ∥21 L∞ ∆ Θ + for SignSGD, (9) ϵ2 ϵ4 dL∞ ∆ ∥σ∥21 L∞ ∆ and Ω + for SGD. (10) ϵ2 ϕ(σ)ϵ4 In view of the above two complexity bounds, we make the following observations. 1. Deterministic term. For the first noiseless term, SignSGD reduces the complexity of SGD by a factor of d, revealing its superior dependence on the dimensional factors. 2. Stochastic term. Since 1/d ≤ ϕ(σ) ≤ 1, we underline that the second noise-dependent term of SignSGD is still strictly better than SGD. Moreover, when the distribution of the noise σ is sparse, SignSGD further reduces the required iteration count of SGD by a factor of d. As shown above, our results provide the first problem setting in which SignSGD achieves a provably better complexity bound (in terms of the dimensional dependence) than SGD. 4.2
Empirical Study
In previous sections, we have discussed how SignSGD can potentially outperform SGD, especially under the ℓ∞ -smooth and sparse noise settings. To verify the theoretical results, we conduct a comprehensive empirical study for SignSGD and SGD under a variety of regimes. Our code is available at https://github.com/Dingzhen230/SignSGD_Outperforms_SGD. 7
11
SGD SignSGD
10
SGD SignSGD
10
Validation Loss
Train Loss
9 8 7 6
9 8 7 6
5
5 0
2000
4000
Iteration
6000
8000
10000
0
2000
4000
Iteration
6000
8000
10000
Figure 1: The training and validation loss for nanoGPT trained on C4. 4.2.1 Experiments on Numerical Examples To amplify the difference between the two optimizers, we manually crafted two numerical example functions that fit into the extreme cases stated in Section 4.1. Due to limited space, the experimental results of these numerical examples are shown in Figure 3. Our findings are summarized as follows. 1. Deterministic example. SignSGD outperforms SGD when facing a ℓ∞ -geometry target and a sufficiently large d. Therefore, we set our target function as an imbalanced quadratic Pd objective f (x) = 1/2 i=1 Li x2i for x ∈ Rd . To better demonstrate the difference, we set d = 5000 and L1 = 1000, Li = 1, i ≥ 2. From Figure 3a we can observe that SGD performs worse than SignSGD because it is heavily penalized for the 1st coordinate where L1 dominates L∞ . 2. Stochastic example. SignSGD outperforms SGD when facing sparse noise structure. We switch to a simple quadratic objective function f (x) = ∥x∥22 /2 for x ∈ R100 . Then we add Gaussian noise N (0, 1002 ) to only the first component of the gradient, which further results in maximizing the sparsity of σ as ϕ(σ) = 1/d under such a setting. Results in Figure 3b align with our findings, as SignSGD consistently outperforms SGD facing sparse noise. 4.2.2 Experiments on nanoGPT Pretraining Following the setup detailed in Appendix E, we train the nanoGPT model [Karpathy, 2022] on the C4 dataset [Raffel et al., 2020] using SGD and SignSGD [Bernstein et al., 2018]. The training and validation learning curves are shown in Figure 1. We observe a substantial performance gap between the two optimizers: while SGD achieves a rapid decrease in loss during the very early stages of training, its progress drastically slows down and plateaus shortly after. In contrast, SignSGD maintains a consistent and significantly faster convergence rate throughout the entire pretraining process. To understand the fundamental cause of this severe performance degradation in SGD, and to verify whether it stems from the highly sparse noise distribution identified in our theory, we leverage the empirical framework in Bernstein et al. [2018] to investigate the noise distributions in practice. Specifically, we track the dynamic evolution of the gradient noise density function (ϕ(σ)) during training and compare the optimization trajectory of our LLM against a standard CNN baseline (ResNet-20 [He et al., 2016] on CIFAR-10 [Krizhevsky et al., 2009]). The comparative results are presented in Figure 2. As illustrated in Figure 2, the noise distribution trends between CNN and LLM training exhibit a striking discrepancy. In the CNN training, the gradient noise starts relatively sparse but rapidly homogenizes during the early epochs, eventually stabilizing into a highly dense state (ϕ ≈ 0.7). This aligns perfectly with classical assumptions where noise become more Gaussian-like over time, as the expected density ϕ for an isotropic Gaussian distribution analytically converges to 2/π ≈ 0.637. Conversely, the LLM starts with a distribution with ϕ ≈ 0.3 and becomes increasingly sparse as training progresses, plunging to extreme levels of ϕ → 0.03 before the middle of training procedure. These empirical findings perfectly corroborate our theoretical insights by providing a unified explanation for the contrasting optimization dynamics observed across different modalities. In CNNs, where the gradient noise rapidly homogenizes into a dense state as visualized in Figure 2b, our theory correctly predicts that SignSGD and SGD should perform comparably, as seen in Bernstein et al. [2018]. Conversely, in LLM pretraining, Figure 2a shows that the noise distribution becomes 8
1.000
NanoGPT Standard Gaussian Convergence Limit
0.800
Variance Density ( )
Variance Density ( )
1.000
0.637 0.600 0.400 0.200
0.029 0.000
0
2000
4000
Step
6000
8000
0.800
0.700
0.637 0.600 0.400 0.200 0.000
10000
(a) Noise density on nanoGPT.
ResNet Standard Gaussian Convergence Limit
0
20
40
60
80
Epoch
100
120
140
160
(b) Noise density on ResNet-20.
Figure 2: Evolution of gradient noise sparsity density ϕ(σ) along the training trajectory of SGD. Figure 2a shows noise density of LLM(nanoGPT-124m) tracked continuously across 10000 iterations. Figure 2b shows noise density of CNN (ResNet-20) tracked continuously across 160 epochs. increasingly sparse and heavily skewed. Standard SGD, whose updates are proportional to gradient magnitudes, is paralyzed by this extreme variance heterogeneity. Sign-based optimizers, however, safely navigate this extreme sparsity by utilizing coordinate-wise updates that are invariant to gradient magnitudes (yielding the decisive performance advantage seen in Figure 1). Our theoretical framework successfully reconciles both the performance parity in CNNs and the significant superiority of SignSGD in LLMs, confirming that sign-based methods are intrinsically more suited for LLMs as established in Section 4.1.
5
Matrix Optimizers
While vector-based sign methods effectively handle separable scaling, modern LLM architectures rely heavily on matrix multiplications. This motivates extending our framework to the matrix domain. The Muon algorithm is introduced by Jordan et al. [2024], and there lies essential similarity between SignSGD and Muon: Bernstein and Newhouse [2024] pointed out that SignSGD can be regarded as steepest descent under infinity norm, while Muon can be regarded as steepest descent under spectral norm. Now that we have already illustrated the edge of SignSGD in Section 4, we will show in the sequel that it’s natural to extend our previous framework from vectors to the matrix domain. 5.1 Notations and Assumptions We denote the set of m × m positive semi-definite (PSD) matrices by Sm . For any X ∈ Rm×n . The matrix sign operator is defined as msign (X) := UV⊤ , where X = UΣV⊤ is the (compact) singular value decomposition (SVD) of X ∈ Rm×n . Following common practice [Li and Hong, 2025, Shen et al., 2025, Sato et al., 2025, Chang et al., 2025, Pan et al., 2025], we assume zero numerical error in Newton–Schulz algorithm. The inner product between matrices X, Y ∈ Rm×n is denoted by ⟨Y, X⟩ := Tr Y⊤ X . We let ∥·∥op , ∥·∥∗ , and ∥·∥F denote the matrix operator norm, nuclear norm, and Frobenius norm, respectively. For a vector v ∈ Rm , diag(v) ∈ Rm×m denotes the rectangular diagonal matrix whose elements are given by (diag(v))ij = vi if i = j and 0 otherwise. Throughout this section, we consider the matrix optimization problem minRm×n F (W) under the following assumptions. Assumption 1b (Lower bounded objective). The function F ∈ Rm×n → R is bounded from below. There exists F ∗ > −∞ such that F (W) ≥ F ∗ holds for all W ∈ Rm×n . We further denote ∆ = F (W0 ) − inf W∈Rm×n F (W). Assumption 2b (Extension of Assumption 2a in matrix form). At step a mini-batch bt we observe of mutually independent gradients Gt = {G1t , · · · , GB t } satisfying E Gt |Ft−1 = ∇f (Wt ), ∀b ∈ [B] where Ft = σ(G1 , . . . , Gt ) denotes the natural filtration. Denote by Nbt = Gbt − ∇f (Wt ), there exists Σ ∈ Sm such that E (Nbt )(Nbt )⊤ |Ft−1 ⪯ Σ2 , ∀b ∈ [B]. Assumption 3b (Spectral norm smoothness). We say F : Rm×n → R is L∗ -spectral norm smooth if for any W, W′ ∈ Rm×n , it holds that |F (W′ ) − (F (W) + ⟨∇F (W), W′ − W⟩)| ≤ 9
L∗ ∥W′ − W∥2op . 2
Assumption 2b can be viewed as an extension of Assumption 2a into matrix space, and has been widely used for analyzing Muon and other matrix Optimizers (An et al. [2025, Assumption 3], Pan et al. [2025, Assumption 3]). Assumption 3b accounts for the distinct structure of matrix parameters, which can be viewed as an extension of Assumption 3a into matrix space. 5.2 Upper bound Theory of Muon The Muon algorithm is presented in Algorithm 2. We state its upper bound below, with the proof deferred to Appendix D.1. Theorem 4 (Muon upper bound). Run Algorithm 2 for T iterations under Assumptions 1b to 3b, by setting the hyperparameters as: r 2∆ ∥Σ∥2∗ , B = max 1, T . (11) η= L∗ T ∆L∗ Denote N = BT as the total complexity, Algorithm 2 guarantees: " # r 1/4 ! T L∗ ∆ 1X ∥Σ∥2∗ L∗ ∆ E ∥∇F (Wt )∥∗ = O + . T t=1 N N
(12)
A key feature of Theorem 4 is that the bound does not depend explicitly on the matrix dimension min{m, n}, in sharp contrast to existing analyses of Muon that incur such dimension dependence [Li and Hong, 2025, Shen et al., 2025, Chang et al., 2025, Huang et al., 2025]. 5.3 Lower bound Theory of Muon After establishing the upper bound for Algorithm 2, we present a corresponding lower bound under the same conditions, which verifies the sharpness of Theorem 4. The proof is deferred to Appendix D.2. Theorem 5 (Muon lower bound). Fix T ≥ 1 and a scaling parameter η > 0, and consider running Algorithm 2 for T iterations with batch size B. For any given parameters L∞ , σ, and ∆, there exists a function f : Rm×n → R and a stochastic gradient oracle such that: 1. f satisfies Assumptions 1b and 3b; 2. the stochastic gradients Gt satisfy Assumption 2b; 3. denote N = BT , the iterates generated by Algorithm 2 satisfy r 1/4 ! h i ∥Σ∥2∗ L∗ ∆ L∗ ∆ + . E min∥∇F (Wt )∥∗ = O t N N
(13)
To our best knowledge, Theorem 5 is the first lower complexity bound for Muon. Existing stochastic lower bounds, such as Arjevani et al. [2023], are formulated for vector-valued methods under Euclidean geometry, and thus do not directly apply to spectral-norm smoothness and nuclear-norm stationarity. Our theorem fills this gap and shows that the dimension-free upper bound in Theorem 4 is unimprovable in our matrix geometry. We outline the proof below. Proof Sketch. Our proof establishes a strict geometric and dynamic equivalence, mathematically reducing the Muon optimization in the matrix domain to the SignSGD optimization in the vector domain. We outline the proof in the following five steps. Step 1: Constructing the Matrix Objective with OrthogonalPAlignments. We lift the hard vector m instance f (x) into the matrix domain by defining F (W) = i=1 fi (QWP⊤ )ii . The reasons why we addtionally introduce two orthogonal matrices Q and P here are: • Q is explicitly used to align the separable vector noise with the target matrix covariance Σ; • P is used as the projection matrix, projecting the m × n matrix into an m × m subspace. Step 2: Designing the Structured Matrix Oracle. To mirror the stochasticity, we construct a structured stochastic matrix gradient Gt = Q⊤ diag(gt )P. Driven by the alignment in Step 1, this specific design perfectly satisfies the required matrix noise covariance Σ = Q⊤ diag(σ)Q, while safely isolating the worst-case vector noise gt strictly within the projected subspace. 10
Step 3: Establishing Trajectory Equivalence via SVD. Since Q⊤ and P are naturally orthogonal matrices, they seamlessly form the left and right singular vectors of Gt without altering the SVD transformation. Consequently, the SVD orthogonalization bypasses them and explicitly acts as a scalar sign (·) operator on the inner diagonal entries. Muon’s matrix update Wt+1 = Wt − η msign (Gt ) mathematically collapses into the exact SignSGD vector update: xt+1 = xt − η sign (gt ). Step 4: Aligning Geometric Constraints. We establish a rigorous one-to-one mapping between the governing metrics of both domains. We prove that the vector ℓ∞ -smoothness flawlessly translates to the matrix spectral norm smoothness (L∗ = L∞ ), and the trace norm of the matrix noise covariance matches the ℓ1 -norm of the vector noise (∥Σ∥∗ = ∥σ∥1 ). Step 5: Transferring the Complexity Bound. Finally, because orthogonal transformations preserve singular values, we show that the trace norm (nuclear norm) of the matrix gradient ∥∇F (Wt )∥∗ is precisely equivalent to the ℓ1 -norm of the vector gradient ∥∇f (xt )∥1 , enabling us to directly invoke the vector bounds from Theorem 2 to establish the exact Ω(·) lower bound for Muon.
6
Conclusion
In this work, we bridge the longstanding gap between the empirical superiority of sign-based optimizers and their theoretical guarantees in non-convex stochastic optimization. By moving from the standard ℓ2 framework to an ℓ∞ -smooth, coordinate-wise noise setting with ℓ1 -stationarity, we give an optimal complexity-theoretic characterization of SignSGD and identify a problem geometry in which it provably outperforms SGD. Specifically, we prove matching upper and lower bounds for SignSGD, establish a strictly worse lower bound for SGD, and show that the resulting separation becomes most pronounced under sparse or highly heterogeneous noise. We further extend this framework to matrix optimization and obtain matching bounds for Muon under spectral norm smoothness and nuclear norm stationarity. Our empirical results corroborate these theoretical findings. Both controlled sparse noise toy problems and GPT-2 pretraining exhibit the skewed gradient noise structure leveraged by our theory, supporting the viewpoint that sign-based methods enjoy a genuine geometric advantage in real-world high-dimensional problems, such as LLM pretraining.
References Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. GPT-4 technical report. arXiv preprint arXiv:2303.08774, 2023. Alekh Agarwal, Peter L Bartlett, Pradeep Ravikumar, and Martin J Wainwright. Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Transactions on Information Theory, 58(5):3235–3249, 2012. Kang An, Yuxing Liu, Rui Pan, Yi Ren, Shiqian Ma, Donald Goldfarb, and Tong Zhang. ASGO: Adaptive structured gradient optimization. In Advances in Neural Information Processing Systems 38 (NeurIPS), pages 126775–126814, 2025. Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, 199(1): 165–214, 2023. Lukas Balles and Philipp Hennig. Dissecting Adam: The sign, magnitude and variance of stochastic gradients. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 404–413, 2018. Lukas Balles, Fabian Pedregosa, and Nicolas Le Roux. The geometry of sign gradient descent. arXiv preprint arXiv:2002.08056, 2020. Jeremy Bernstein and Laker Newhouse. Old optimizer, new norm: An anthology. In OPT 2024: Optimization for Machine Learning, 2024. URL https://openreview.net/forum?id= ux18f5nOpD. Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. SignSGD: Compressed optimisation for non-convex problems. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 560–569, 2018. 11
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. SignSGD with majority vote is communication efficient and fault tolerant. In International Conference on Learning Representations (ICLR), 2019. Åke Björck and Clazett Bowie. An iterative algorithm for computing the best estimate of an orthogonal matrix. SIAM Journal on Numerical Analysis, 8(2):358–364, 1971. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 1877–1901, 2020. Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71–120, 2020. Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points II: First-order methods. Mathematical Programming, 185(1):315–355, 2021. Da Chang, Yongxiang Liu, and Ganzhao Yuan. On the convergence of Muon and beyond. arXiv preprint arXiv:2509.15816, 2025. Lizhang Chen, Bo Liu, Kaizhao Liang, and Qiang Liu. Lion secretly solves a constrained optimization: As lyapunov predicts. In International Conference on Learning Representations (ICLR), pages 35404–35439, 2024. Lizhang Chen, Jonathan Li, and Qiang Liu. Muon optimizes under spectral norm constraints. arXiv preprint arXiv:2506.15054, 2025. Xiangning Chen, Chen Liang, Da Huang, Esteban Real, Kaiyuan Wang, Hieu Pham, Xuanyi Dong, Thang Luong, Cho-Jui Hsieh, Yifeng Lu, et al. Symbolic discovery of optimization algorithms. In Advances in Neural Information Processing Systems 36 (NeurIPS), pages 49205–49233, 2023. Xin Cheng, Wangding Zeng, Damai Dai, Qinyu Chen, Bingxuan Wang, Zhenda Xie, Kezhao Huang, Xingkai Yu, Zhewen Hao, Yukun Li, et al. Conditional memory via scalable lookup: A new axis of sparsity for large language models. arXiv preprint arXiv:2601.07372, 2026. Sinho Chewi, Sébastien Bubeck, and Adil Salim. On the complexity of finding stationary points of smooth functions in one dimension. In Proceedings of The 34th International Conference on Algorithmic Learning Theory (ALT), pages 358–374, 2023. Evgenii Chzhen and Sholom Schechtman. SignSVRG: fixing SignSGD via variance reduction. arXiv preprint arXiv:2305.13187, 2023. Michael Crawshaw and Mingrui Liu. Complexity lower bounds of adaptive gradient algorithms for non-convex stochastic optimization under relaxed smoothness. In International Conference on Learning Representations (ICLR), 2025. Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Robustness to unbounded smoothness of generalized SignSGD. In Advances in Neural Information Processing Systems 35 (NeurIPS), pages 9955–9968, 2022. Michael Crawshaw, Chirag Modi, Mingrui Liu, and Robert M Gower. An exploration of nonEuclidean gradient descent: Muon and its many variants. arXiv preprint arXiv:2510.09827, 2025. DeepSeek-AI. DeepSeek-V4: Towards Highly Efficient Million-Token Context Intelligence, 2026. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 4171–4186, 2019. 12
Yiming Dong, Huan Li, and Zhouchen Lin. Convergence rate analysis of LION. arXiv preprint arXiv:2411.07724, 2024. Yoel Drori and Ohad Shamir. The complexity of finding stationary points with stochastic gradient descent. In Proceedings of the 37th International Conference on Machine Learning (ICML), pages 2658–2667, 2020. Zhehang Du and Weijie Su. The newton-muon optimizer. arXiv preprint arXiv:2604.01472, 2026. John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research (JMLR), 12(7), 2011. Kevin Frans, Pieter Abbeel, and Sergey Levine. What really matters in matrix-whitening optimizers? arXiv preprint arXiv:2510.25000, 2025. Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341–2368, 2013. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 770–778, 2016. Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Jack W. Rae, Oriol Vinyals, and Laurent Sifre. Training compute-optimal large language models. In Advances in Neural Information Processing Systems 35 (NeurIPS), pages 30016–30030, 2022. Feihu Huang, Yuning Luo, and Songcan Chen. LiMuon: Light and fast Muon optimizer for large models. arXiv preprint arXiv:2509.14562, 2025. Ruichen Jiang, Devyani Maladkar, and Aryan Mokhtari. Provable complexity improvement of AdaGrad over SGD: Upper and lower bounds in stochastic non-convex optimization. In Proceedings of the 38th Conference on Learning Theory (COLT), pages 3124–3158, 2025a. Wei Jiang and Lijun Zhang. Convergence analysis of the Lion optimizer in centralized and distributed settings. arXiv preprint arXiv:2508.12327, 2025. Wei Jiang, Sifan Yang, Wenhao Yang, and Lijun Zhang. Efficient sign-based optimization: Accelerating convergence via variance reduction. In Advances in Neural Information Processing Systems 37 (NeurIPS), pages 33891–33932, 2024. Wei Jiang, Dingzhi Yu, Sifan Yang, Wenhao Yang, and Lijun Zhang. Improved analysis for sign-based methods with momentum updates. arXiv preprint arXiv:2507.12091, 2025b. Richeng Jin, Yufan Huang, Xiaofan He, Huaiyu Dai, and Tianfu Wu. Stochastic-Sign SGD for federated learning with theoretical guarantees. arXiv preprint arXiv:2002.10940, 2020. Keller Jordan, Yuchen Jin, Vlado Boza, Jiacheng You, Franz Cesista, Laker Newhouse, and Jeremy Bernstein. Muon: An optimizer for hidden layers in neural networks, 2024. URL https: //kellerjordan.github.io/posts/muon/. Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 3252–3261, 2019. Andrej Karpathy. NanoGPT, 2022. URL https://github.com/karpathy/nanoGPT. Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015. 13
Nikita Kornilov, Philip Zmushko, Andrei Semenov, Mark Ikonnikov, Alexander Gasnikov, and Alexander Beznosikov. Sign operator for coping with heavy-tailed noise in non-convex optimization: High probability bounds under (L0 , L1 )-smoothness. arXiv preprint arXiv:2502.07923, 2025. Zdislav Kovarik. Some iterative methods for improving orthonormality. SIAM Journal on Numerical Analysis, 7(3):386–389, 1970. Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images.(2009), 2009. Frederik Kunstner, Jacques Chen, Jonathan Wilder Lavington, and Mark Schmidt. Noise is not the main factor behind the gap between SGD and Adam on transformers, but sign descent might be. In International Conference on Learning Representations (ICLR), 2023. √ Huan Li, Yiming Dong, and Zhouchen Lin. On the O( d/T 1/4 ) convergence rate of rmsprop and its momentum extension measured by ℓ1 norm. Journal of Machine Learning Research (JMLR), 26(131):1–25, 2025a. Jiaxiang Li and Mingyi Hong. A note on the convergence of Muon and further. arXiv preprint arXiv:2502.02900, 2025. Zichong Li, Liming Liu, Chen Liang, Weizhu Chen, and Tuo Zhao. NorMuon: Making Muon more efficient and scalable. arXiv preprint arXiv:2510.05491, 2025b. Jingyuan Liu, Jianlin Su, Xingcheng Yao, Zhejun Jiang, Guokun Lai, Yulun Du, Yidao Qin, Weixin Xu, Enzhe Lu, Junjie Yan, et al. Muon is scalable for LLM training. arXiv preprint arXiv:2502.16982, 2025. Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations (ICLR), 2019. Jianhao Ma, Yu Huang, Yuejie Chi, and Yuxin Chen. Preconditioning benefits of spectral orthogonalization in Muon. arXiv preprint arXiv:2601.13474, 2026. Sushant Mehta, Raj Dandekar, Rajat Dandekar, and Sreedath Panat. Muon: Training and trade-offs with latent attention and moe. arXiv preprint arXiv:2509.24406, 2025. Arkadi Semen Nemirovski and David Berkovich Yudin. Problem complexity and method efficiency in optimization. Wiley-Interscience, 1983. Yurii Nesterov et al. Lectures on convex optimization, volume 137. Springer, 2018. Saurabh Page, Advait Joshi, and SS Sonawane. Muonall: Muon variant for efficient finetuning of large language models. arXiv preprint arXiv:2511.06086, 2025. Rui Pan, Haishan Ye, and Tong Zhang. Eigencurve: Optimal learning rate schedule for SGD on quadratic objectives with skewed Hessian spectrums. In International Conference on Learning Representations (ICLR), 2022. Rui Pan, Yuxing Liu, Xiaoyu Wang, and Tong Zhang. Accelerated convergence of stochastic heavy ball method under anisotropic gradient noise. In International Conference on Learning Representations (ICLR), pages 55989–56028, 2024. Rui Pan, Yang Luo, Yuxing Liu, Yang You, and Tong Zhang. Unbiased gradient low-rank projection. arXiv preprint arXiv:2510.17802, 2025. Hanyang Peng, Shuang Qin, Yue Yu, Fangqing Jiang, Hui Wang, and Zhouchen Lin. Simple convergence proof of Adam from a sign-like descent perspective. arXiv preprint arXiv:2507.05966, 2025. Xun Qian, Hussein Rammal, Dmitry Kovalev, and Peter Richtarik. Muon is provably faster with momentum variance reduction. arXiv preprint arXiv:2512.16598, 2025. 14
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research (JMLR), 21(140):1–67, 2020. Martin Riedmiller and Heinrich Braun. A direct adaptive method for faster backpropagation learning: The RPROP algorithm. In IEEE International Conference on Neural Networks, pages 586–591. IEEE, 1993. Herbert Robbins and Sutton Monro. A stochastic approximation method. The Annals of Mathematical Statistics, pages 400–407, 1951. Mher Safaryan and Peter Richtárik. Stochastic sign descent methods: New algorithms and better theory. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 9224–9234, 2021. Levent Sagun, Utku Evci, V Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the Hessian of over-parametrized neural networks. arXiv preprint arXiv:1706.04454, 2017. Naoki Sato, Hiroki Naganuma, and Hideaki Iiduka. Convergence bound and critical batch size of Muon optimizer. arXiv preprint arXiv:2507.01598, 2025. Andrei Semenov, Matteo Pagliardini, and Martin Jaggi. Benchmarking optimizers for large language model pretraining. arXiv preprint arXiv:2509.01440, 2025. Maria-Eleni Sfyraki and Jun-Kun Wang. Lions and Muons: Optimization via stochastic frank-wolfe. arXiv preprint arXiv:2506.04192, 2025. Ishaan Shah, Anthony M Polloreno, Karl Stratos, Philip Monk, Adarsh Chaluvaraju, Andrew Hojel, Andrew Ma, Anil Thomas, Ashish Tanwer, Darsh J Shah, et al. Practical efficiency of Muon for pretraining. arXiv preprint arXiv:2505.02222, 2025. Wei Shen, Ruichuan Huang, Minhui Huang, Cong Shen, and Jiawei Zhang. On the convergence analysis of Muon. arXiv preprint arXiv:2505.23737, 2025. Chongjie Si, Debing Zhang, and Wei Shen. Adamuon: Adaptive Muon optimizer. arXiv preprint arXiv:2507.11005, 2025. Weijie Su. Isotropic curvature model for understanding deep learning optimization: Is gradient orthogonalization optimal? arXiv preprint arXiv:2511.00674, 2025. Tao Sun, Qingsong Wang, Dongsheng Li, and Bao Wang. Momentum ensures convergence of SIGNSGD under weaker assumptions. In Proceedings of the 40th International Conference on Machine Learning (ICML), pages 33077–33099, 2023. Gemini Team, Rohan Anil, Sebastian Borgeaud, Jean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, Katie Millican, et al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11805, 2023. Kimi Team, Yifan Bai, Yiping Bao, Guanduo Chen, Jiahao Chen, Ningxin Chen, Ruijue Chen, Yanru Chen, Yuankun Chen, Yutian Chen, et al. Kimi K2: Open agentic intelligence. arXiv preprint arXiv:2507.20534, 2025. Kimi Team, Tongtong Bai, Yifan Bai, Yiping Bao, SH Cai, Yuan Cao, Y Charles, HS Che, Cheng Chen, Guanduo Chen, et al. Kimi K2.5: Visual Agentic Intelligence. arXiv preprint arXiv:2602.02276, 2026. Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971, 2023. Amund Tveit, Bjørn Remseth, and Arve Skogvold. Muon optimizer accelerates grokking. arXiv preprint arXiv:2504.16041, 2025. 15
Bhavya Vasudeva, Puneesh Deora, Yize Zhao, Vatsal Sharan, and Christos Thrampoulidis. How Muon’s spectral design benefits generalization: A study on imbalanced data. arXiv preprint arXiv:2510.22980, 2025a. Bhavya Vasudeva, Jung Whan Lee, Vatsal Sharan, and Mahdi Soltanolkotabi. The rich and the simple: On the implicit bias of Adam and SGD. In Advances in Neural Information Processing Systems 38 (NeurIPS), page to appear, 2025b. Shuche Wang, Fengzhuo Zhang, Jiaxiang Li, Cunxiao Du, Chao Du, Tianyu Pang, Zhuoran Yang, Mingyi Hong, and Vincent YF Tan. Muon outperforms Adam in tail-end associative memory learning. arXiv preprint arXiv:2509.26030, 2025. Kaiyue Wen, David Hall, Tengyu Ma, and Percy Liang. Fantastic pretraining optimizers and where to find them. arXiv preprint arXiv:2509.02046, 2025. Lei Wu, Mingze Wang, and Weijie Su. The alignment property of sgd noise and how it helps select flat minima: A stability analysis. In Advances in Neural Information Processing Systems 35 (NeurIPS), pages 4680–4693, 2022. Nachuan Xiao, Xiaoyin Hu, and Kim-Chuan Toh. Stochastic subgradient methods with guaranteed global stability in nonsmooth nonconvex optimization. arXiv preprint arXiv:2307.10053, 2023. Shuo Xie, Mohamad Amin Mohamadi, and Zhiyuan Li. Adam exploits ℓ∞ -geometry of loss landscape via coordinate-wise adaptivity. In International Conference on Learning Representations (ICLR), pages 7937–7965, 2025a. Shuo Xie, Tianhao Wang, Beining Wu, and Zhiyuan Li. A tale of two geometries: Adaptive optimizers and non-Euclidean descent. arXiv preprint arXiv:2511.20584, 2025b. Dingzhi Yu, Rui Pan, Yuxing Liu, and Tong Zhang. StoSignSGD: Unbiased Structural Stochasticity Fixes SignSGD for Training Large Language Models. arXiv preprint arXiv:2604.15416, 2026a. Dingzhi Yu, Hongyi Tao, Yuanyu Wan, Luo Luo, and Lijun Zhang. Sign-based optimizers are effective under heavy-tailed noise. arXiv preprint arXiv:2602.07425, 2026b. Aohan Zeng, Xin Lv, Qinkai Zheng, Zhenyu Hou, Bin Chen, Chengxing Xie, Cunxiang Wang, Da Yin, Hao Zeng, Jiajie Zhang, et al. GLM-4.5: Agentic, reasoning, and coding (arc) foundation models. arXiv preprint arXiv:2508.06471, 2025. Aohan Zeng, Xin Lv, Zhenyu Hou, Zhengxiao Du, Qinkai Zheng, Bin Chen, Da Yin, Chendi Ge, Chengxing Xie, Cunxiang Wang, et al. GLM-5: from vibe coding to agentic engineering. arXiv preprint arXiv:2602.15763, 2026. Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? In Advances in Neural Information Processing Systems 33 (NeurIPS), pages 15383–15393, 2020. Minxin Zhang, Yuxuan Liu, and Hayden Schaeffer. Adagrad meets Muon: Adaptive stepsizes for orthogonal updates. arXiv preprint arXiv:2509.02981, 2025. Xinwen Zhang and Hongchang Gao. On provable benefits of Muon in federated learning. arXiv preprint arXiv:2510.03866, 2025. Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise in stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 7654–7663, 2019. 16
A
Proof of Lemma 1
Suppose f is L-separable smooth, we have |f (y) − (f (x) + ⟨∇f (x), y − x⟩)| ≤
d 1 1X ∥y − x∥2L = Li (yi − xi )2 2 2 i=1 d
≤
1X ∥L∥1 Li ∥y − x∥2∞ = ∥y − x∥2∞ . 2 i=1 2
Therefore f also satisfies Assumption 3a with L∞ = ∥L∥1 .
B
Analysis for SignSGD
B.1
Upper Bound for SignSGD
Proof of Theorem 1. Under Assumption 3a, we have: f (xt+1 ) ≤ = =
L∞ ∥xt+1 − xt ∥2∞ 2 η 2 L∞ f (xt ) − ⟨∇f (xt ), η sign (gt )⟩ + 2 f (xt ) + ⟨∇f (xt ), η(sign (∇f (xt )) − sign (gt ))⟩ f (xt ) + ⟨∇f (xt ), xt+1 − xt ⟩ +
− ⟨∇f (xt ), η sign (∇f (xt ))⟩ +
η 2 L∞ 2
=
f (xt ) + ⟨∇f (xt ), η(sign (∇f (xt )) − sign (gt ))⟩ − η∥∇f (xt )∥1 +
≤
f (xt ) + 2η∥∇f (xt ) − gt ∥1 − η∥∇f (xt )∥1 +
η 2 L∞ 2
η 2 L∞ , 2
where the last inequality is due to ⟨∇f (xt ), η(sign (∇f (xt )) − sign (gt ))⟩ =
d X
∇i f (xt ) ∗ η(sign (∇i f (xt )) − sign (gt,i ))
i=1
≤
d X
2η |∇i f (xt )| ∗ I(sign (∇i f (xt )) ̸= sign (gt,i ))
i=1
≤ 2η
d X
|∇i f (xt ) − gt,i | ∗ I(sign (∇i f (xt )) ̸= sign (gt,i ))
i=1
≤ 2η
d X
|∇i f (xt ) − gt,i | = 2η∥∇f (xt ) − gt ∥1 .
i=1
Rearranging the obtained relation and summing up yields " # " # T T ∆ 1X ηL∞ 1X ∥∇f (xt )∥1 ≤ + 2E ∥∇f (xt ) − gt ∥1 + . E T t=1 ηT T t=1 2
(14)
we denote ξt = ∇f (xt ) − gt as the noise of gradient in iteration t. Due to i.i.d characteristic of ξt , we have: " # " # T T T 1X 1X 1X E ∥∇f (xt ) − gt ∥1 = E ∥ξt ∥1 = E [∥ξt ∥1 ] T t=1 T t=1 T t=1 (15) T d 1 XX ∥σ∥1 = E[|ξt,i |] ≤ √ , T t=1 i=1 B 17
where the inequality follows from Jensen’s p inequality for the variance of the mini-batch mean. Putting (15) back to (14), and setting η = 2∆/L∞ T , We get: " # r T 1X 2∆L∞ ∥σ∥1 E ∥∇f (xt )∥1 ≤ +2 √ . (16) T t=1 T B If the first term dominates, which means r 2∆L∞ ∥σ∥1 ≥ 2∥σ∥1 ≥ 2 √ , T B
(17)
by setting B = 1, we have " # r r T √ 1X 2∆L∞ ∆L∞ ∥σ∥1 E ∥∇f (xt )∥1 ≤ + 2 √ ≤ (2 + 2) . T t=1 T N B 2
Otherwise, we set B = ∥σ∥1/∆L∞ T , which implies r 1 2∆L∞ 4∥σ∥21 ∆L∞ 4 = . T N
(18)
Plugging (18) into (16), we get # " 1 1 T 4∥σ∥21 ∆L∞ 4 ∥σ∥21 ∆L∞ 4 1X ∥∇f (xt )∥1 ≤ E +2 . T t=1 N N
(19)
Combining the above two cases together, we have # " ! r 1 1 T (∥σ∥1 ) 2 (∆L∞ ) 4 1X ∆L∞ ∥∇f (xt )∥1 = O + E . 1 T t=1 N (N ) 4 This completes the proof. B.2 Lower Bound for SignSGD To exploit the separable nature of SignSGD before generalizing to d dimensions, we start by bounding the complexity of Algorithm 1 in finding stationary points in one dimension: Lemma 2. For any positive integer n, suppose that ϵ satisfies 1 ϵ≤ √ 2 n
(20)
Let x1 ∈ R and xt = x1 + (t − 1)η for any 2 ≤ t ≤ n + 1. Then there exists a function p : R → R such that: (i) p has a 1-Lipschitz gradient; (ii) p(x1 ) − inf p ≤ 1 (iii) p′ (xt ) = −ϵ for any t ∈ [1, n]. Proof. We construct the function p as: −ϵ(x − x1 ) p(x) = ϕt,ϵ (x) + ct 1 (x − x )2 − ϵ(x − x ) + c t+1 t+1 N +1 2
x ∈ (−∞, x1 ]; x ∈ (xt , xt+1 ]; x ∈ (xn+1 , ∞),
where the values {ct }nt=1 are chosen to ensure that the function p is continuous. The function ϕt,ϵ (x) is defined as below: 1 xt + xt+1 2 (x − xt ) − ϵ(x − xt ) x ∈ xt , ; 2 2 ϕt,ϵ (x) = − 1 (x − x )2 − ϵ(x − x ) t+1 t+1 xt + xt+1 2 x∈ , xt+1 . 2 2 + (xt+1 − xt ) − (x t+1 − xt )ϵ 4 18
Without loss of generality we can assume x1 = η, otherwise we just need to perform a translation to our function p. Plugging in xt = tη, we have: 1 xt + xt+1 2 x ∈ xt , ; (x − tη) − ϵ(x − tη) 2 2 ϕt,ϵ (x) = 2 1 η xt + xt+1 2 − ηϵ x ∈ , xt+1 . − (x − (t + 1)η) − ϵ(x − (t + 1)η) + 2 4 2 Further, we can give the value ct as follows: c1 = 0,
ct+1 = t
1 2 η − ηϵ . 4
(21)
From the definition of p, we have 0, x ∈ (−∞, x1 ]; 1 2 p(x) ≥ min ct − 2 ϵ , ct+1 , x ∈ (xt , xt+1 ]; 1 2 c x ∈ (xn+1 , +∞), n+1 − ϵ , 2 which can be written as 1 inf p ≥ min ct − ϵ2 t 2 1 2 1 = min 0, n η − ηϵ − ϵ2 . 4 2 This implies that
1 2 1 2 1 2 p(x1 ) − inf p ≤ max ϵ , n ηϵ − η + ϵ 2 4 2 1 1 2 ≤ max ϵ , nϵ2 + ϵ2 2 2 1 2 2 = nϵ + ϵ . 2 With (20), we have 1 1 1 nϵ2 + ϵ2 ≤ + < 1. 2 4 8n This completes the proof. Lemma 3. Consider running SignSGD on a one-dimensional smooth function p with the scaling parameter η and batch size B. For any L > 0 and ∆ > 0 , there exists a function p : R → R and a corresponding stochastic gradient oracle gt such that: (i) p has L-Lipschitz gradients and p(x1 ) − inf p ≤ ∆ (ii) √ the stochastic gradient gtb is unbiased and has a bounded variance of σ 2 (iii) 2 2 Given ϵ such that ϵ ≤ L∆, if N = BT ≤ L∆(4ϵ +σ )/128ϵ4 , then we have E[min |p′ (xi )|] ≥ ϵ. Which further implies that: ) ( 1 r h i L∆σ 2 4 L∆ ′ E min |p (xt )| ≥ C max , . t N N Proof of Lemma 3. We set x1 = η. Without loss of generality, we can assume that L = 1 and ∆ = 1. Now we define N := 1/16ϵ2 , which surely satisfies the requirement in (20) with 2ϵ. According to Lemma 2, there exists a function p : R → R such that (i) its gradient is 1-Lipschitz; (ii) p(x1 ) − inf p ≤ 1; (iii) p′ (xt ) = −2ϵ for any 1 ≤ t ≤ N + 1. Consider running SignSGD on function p with the stochastic gradient oracle gtb given as below: σ2 σ 2 + 4ϵ2 ′ 4ϵ2 b P gtb = 0 | xt = 2 , P g = p (x ) | x = 2 . b ∈ [B] t t t 2 2 σ + 4ϵ 4ϵ σ + 4ϵ2 19
It is straightforward to verify that gtb satisfies the requirement. Now we denote mt as the number of steps that gt is non-zero during the first t steps with m0 = 0, which means that for mt steps the xt goes forward by η and t − mt steps the algorithm does nothing to xt since gt = 0, sign (gt ) = 0. We denote M = mT . By definition, we have B ! 4Bϵ2 4ϵ2 4ϵ2 ≤ T × 1 − 1 + = BT. E(M ) = T × 1 − 1 − 2 σ + 4ϵ2 σ 2 + 4ϵ2 σ 2 + 4ϵ2 According to Markov’s inequality we have 1 , 2
P(M ≥ 2E[M ]) ≤
1 , we have M ≤ 2E[M ] ≤ n. Moreover, we can use 2 induction to prove that xt = η + ηMt−1 , which means that p′ (xt ) = −2ϵ. Finally, we can bound h i 1 h i E min |p′ (xt )| ≥ E min |p′ (xt )| | M ≤ n = ϵ. t t 2 p 2 2 Since the equation above holds for any N = T B ≤ L∆(4ϵ +σ )/128ϵ4 , by setting ϵ = L∆/32N , we get L∆ 4ϵ2 + σ 2 N= ≤ L∆ . (22) 2 32ϵ 128ϵ4 1/4 2 Similarly we can set ϵ = L∆σ /128N to satisfy the condition. Therefore for some constant C, we have ) ( 1 r h i L∆ L∆σ 2 4 ′ , E min |p (xt )| ≥ C max . (23) t N N
which means that with probability at least
This completes the proof. Lemma 3 states the complexity lower bound for Algorithm 1 for a one-dimensional function. Now we can extend to a dimension d result, which will yield the bound in Theorem 2. Proof of Theorem 2. First by applying Lemma 3 to each coordinate, we have ( ) 1 r d h i X Li ∆i σi2 4 Li ∆i E min∥∇f (xt )∥1 ≥ max , . t N N i=1 By choosing ∆i = Li ∆/∥L∥1 , we have: s r d r d h i X X Li ∆i ∆ ∥L∥1 ∆ E min∥∇f (xt )∥1 ≥ = Li = . t N ∥L∥1 N N i=1 i=1 2
Then, by choosing ∆i = P
1
σi3 Li3
∆, we get
2
1
i
d X Li ∆i σ 2 4
d 3 3 j=1 σj Lj
1
h
E min∥∇f (xt )∥1 ≥ t
i
N
i=1
Pd
=
=
d X
i=1 2 3
3 1
i=1 σi Li
N
3
8
Pd
This completes the proof. 20
2
1
3 3 j=1 σj Lj N
14
∆ .
σi L∞ , we get ∥σ∥1 h i ∥σ∥2 L∆ 41 1 E min∥∇f (xt )∥1 ≥ . t N
Further, by setting Li = (σi/∥σ∥1 ) ∥L∥1 =
14
4
σi3 Li3 ∆
C
Proof of Theorem 3
Proof. In Jiang et al. [2025a], the lower bound of SGD is established as follows. Lemma 4. (Jiang et al. [2025a, Theorem 4.1]) Run vanilla SGD for T iterations with a batch size B, there exists a function which satisfies Assumption 1a with f (x1 ) − inf f ≤ ∆, Assumption 4a with L = [L1 , L2 , . . . , Ld ], and Assumption 2a with σ = [σ1 , σ2 , . . . , σd ], and we have: r √ 2 ! 14 Pd h i L ) d∆( σ d∥L∥ ∆ i ∞ i=1 i . E min∥∇f (xt )∥1 = Ω (24) + t T T Now with Lemma 1, we know that any L separable smooth function f is also ℓ∞ -smooth with L∞ = ∥L∥1 . So we can properly set Li to maximize (24) to get the lower bound of SGD under Assumption 3a. For the first term, let’s consider a case where L∞ = ∥L∥1 is imbalanced and dominated by a certain coordinate, for example, we have 1 1 1 L1 > ∥L∥1 , ∥L∥∞ = L1 ≥ ∥L∥1 = L∞ . 2 2 2 So under this case, ! ! r r h i d∥L∥∞ ∆ dL∞ ∆ =Ω . (25) E min∥∇f (xt )∥1 = Ω t T T 2 Then, for the second term, by setting Li = σi /∥σ∥22 L∞ , we get 1 ! h i dL∞ ∆∥σ∥22 4 . (26) E min∥∇f (xt )∥1 = Ω t T Putting the two cases in (25) and (26) together and we can obtain (5). This completes the proof.
D
Analysis for Muon
D.1
Upper Bound for Muon
Proof of Theorem 4. Under Assumption 3b, we have: L∗ ∥Wt+1 − Wt ∥2op 2 L∗ = F (Wt ) − ⟨∇F (Wt ), η msign (Gt )⟩ + ∥η msign (Gt )∥2op 2
F (Wt+1 ) ≤ F (Wt ) + ⟨∇F (Wt ), Wt+1 − Wt ⟩ +
= F (Wt ) − η ⟨Gt , msign (Gt )⟩ − η ⟨∇F (Wt ) − Gt , msign (Gt )⟩ + ≤ F (Wt ) − η∥Gt ∥∗ + η∥∇F (Wt ) − Gt ∥∗ ∥msign (Gt )∥op +
L∗ η 2 2
L∗ η 2 2
L∗ η 2 , 2 where the second inequality is due to |⟨A, B⟩| ≤ ∥A∥∗ ∥B∥op . Summing over t = 0, . . . , T − 1, we get ≤ F (Wt ) − η∥∇F (Wt )∥∗ + 2η∥∇F (Wt ) − Gt ∥∗ +
F (WT ) − F (W1 ) ≤ −η
T −1 X
T −1 X
t=0
t=0
∥∇F (Wt )∥∗ + 2η
∥∇F (Wt ) − Gt ∥∗ +
L∗ η 2 T . 2
(27)
Under Assumption 1b, F (W1 ) − F (WT ) ≤ F (W1 ) − inf F ≤ ∆, take expectation on both sides, and we get T −1 T −1 1 X 2 X ∆ L∗ η E [∥∇F (Wt )∥∗ ] ≤ + E [∥∇F (Wt ) − Gt ∥∗ ] + . T t=0 ηT T t=0 2
(28)
Define Nt = ∇F (Wt ) − Gt . Consider Batch size B, we denote the gradient on each sample is Gbt , 1 ≤ b ≤ B, and the noise on each sample as Nbt = ∇F (Wt ) − Gbt . We have the following lemma: 21
Lemma 5. (An et al. [2025, Lemma 9]) Under Assumption 2b, with batch size B, we have Σ2 E Nt N⊤ ⪯ . (29) t B 1 Under the fact that the map X 7→ Tr X 2 is concave on the positive semi-definite cone, we can apply Jensen’s inequality to get q q ∥Σ∥∗ ⊤ E [∥Nt ∥∗ ] = E Tr (30) Nt N⊤ ≤ Tr E N N ≤ √ . t t t B p Plugging (30) back to (28) and set η = 2∆/L∗ T , we get r T −1 2∆L∗ 1 X ∥Σ∥∗ E [∥∇F (Wt )∥∗ ] ≤ +2 √ . (31) T t=0 T B If T ≤ ∆L∗/∥Σ∥2∗ , By setting B = 1, we have " # r r T √ 2∆L∗ ∆L∗ 1X + 2∥Σ∥∗ ≤ (2 + 2) E ∥∇F (Wt )∥∗ ≤ T t=1 T N 2
Otherwise, we set B = ∥Σ∥∗/∆L∗ T , which implies r 1 2∆L∗ 4∥Σ∥2∗ ∆L∗ 4 . = T BT
(32)
Bringing (32) back to (31) " # 1 1 T 1X 4∥Σ∥2∗ ∆L∗ 4 ∥Σ∥2∗ ∆L∗ 4 E + ∥∇F (Wt )∥∗ ≤ 2 T t=1 BT BT ! 1 ∥Σ∥2∗ ∆L∗ 4 =O . BT Putting the above two cases together, we have " # r 1 ! T ∥Σ∥2∗ ∆L∗ 4 1X ∆L∗ E ∥∇F (Wt )∥∗ = O + . T t=1 N N
D.2 Lower Bound for Muon Assume the target weight matrix is W ∈ Rm×n . Without loss of generality, we assume m ≤ n. We introduce a projection matrix P = [Im , 0m×(n−m) ] ∈ Rm×n which pads an m × m matrix with zeros to match the m × n dimension. Let Σ ∈ Rm×m be the target matrix noise covariance, which can be diagonalized via an orthogonal matrix Q ∈ Rm×m as Σ = Q⊤ diag(σ)Q. We construct our worst-case matrix objective function by extracting the diagonal elements of the transformed matrix QWP⊤ ∈ Rm×m : F (W) =
m X
fi (QWP⊤ )ii ,
(33)
i=1
where f (x) =
Pm
i=1 fi (xi ) is the hard 1D vector instance constructed in Theorem 2.
First, we provide two lemmas to establish the strict geometric equivalence between the vector domain and the matrix domain. Lemma 6. Assume that the separable vector function f (x) : Rm → R satisfies Assumption 2a with bounded variance σ 2 . Then the constructed matrix function F (W) : Rm×n → R satisfies Assumption 2b with matrix noise covariance Σ2 = Q⊤ diag(σ 2 )Q. 22
Proof. By the chain rule, the exact gradient of F (W) is given by: ∇F (W) = Q⊤ diag ∇f (x) P, ⊤
m
(34)
m
where x ∈ R with xi = (QWP )ii . Let g ∈ R be the stochastic gradient oracle for f (x). We construct the corresponding stochastic matrix gradient G for F (W) as: G = Q⊤ diag(g)P.
(35)
⊤
The estimation error matrix is G − ∇F (W) = Q diag(g − ∇f (x))P. Computing the uncentered covariance, we have: E (G − ∇F (W))(G − ∇F (W))⊤ = E Q⊤ diag(g − ∇f (x))PP⊤ diag(g − ∇f (x))Q = Q⊤ E diag (gi − ∇fi (xi ))2 Q. Here we used the property that PP⊤ = Im . Under Assumption 2a, we have E (gi − ∇fi (xi ))2 ≤ σi2 , which implies: E (G − ∇F (W))(G − ∇F (W))⊤ ⪯ Q⊤ diag(σ 2 )Q = Σ2 . This completes the proof. Lemma 7. Assume that f (x) : Rm → R satisfies Assumption 3a with L∞ -smoothness parameter L. Then the constructed matrix function F (W) : Rm×n → R satisfies Assumption 3b with spectral norm smoothness L∗ = L. Proof. Let X, Y ∈ Rm×n be two arbitrary matrices, and define ∆ = Y − X. We map these matrices to vectors x, y ∈ Rm by defining xi = (QXP⊤ )ii and yi = (QYP⊤ )ii . Let their difference be δ = y − x, where δi = (Q∆P⊤ )ii . By definition, F (X) = f (x) and F (Y) = f (y). First, we bridge the Frobenius inner product of the matrices with the Euclidean inner product of the vectors. Let S = diag(∇f (x)). Using (34) and the cyclic property of the trace operator, we have: ⟨∇F (X), ∆⟩F = tr (Q⊤ SP)⊤ ∆ = tr P⊤ S⊤ Q∆ = tr S⊤ (Q∆P⊤ ) . Let M = Q∆P⊤ ∈ Rm×m . Since S is diagonal, the trace tr(S⊤ M) perfectly reduces to the element-wise sum of their main diagonals: m m X X tr S⊤ M = Sii Mii = ∇fi (xi )δi = ⟨∇f (x), y − x⟩ . i=1
i=1
Therefore, the Taylor expansion residuals in both domains are strictly identical: F (Y) − (F (X) + ⟨∇F (X), Y − X⟩F ) = f (y) − (f (x) + ⟨∇f (x), y − x⟩) .
(36)
Taking the absolute value and applying the L∞ -smoothness of f (x), we obtain: L ∥y − x∥2∞ . (37) 2 To bound the vector ℓ∞ -norm using the matrix spectral norm, we examine the maximum component of δ. For any i ∈ {1, . . . , m}: |F (Y) − F (X) − ⟨∇F (X), Y − X⟩F | ≤
⊤ ⊤ |yi − xi | = (Q∆P⊤ )ii = e⊤ i Q∆P ei = qi ∆ẽi ,
where ei ∈ Rm is the standard basis vector, qi = Q⊤ ei ∈ Rm , and ẽi = P⊤ ei ∈ Rn . Since Q is orthogonal and P is a standard projection, both vectors preserve their unit Euclidean lengths: ∥qi ∥2 = 1 and ∥ẽi ∥2 = 1. By the definition of the induced matrix 2-norm (spectral norm), we have: q⊤ i ∆ẽi ≤ ∥qi ∥2 ∥∆∥op ∥ẽi ∥2 = ∥Y − X∥op . Taking the maximum over all i yields ∥y − x∥∞ ≤ ∥Y − X∥op . Substituting this into (37) establishes that F (W) is L∗ -spectral norm smooth with L∗ = L. 23
Proof of Theorem 5. We now demonstrate that under this construction, the optimization trajectory of Muon in the matrix space exactly replicates that of SignSGD in the vector space. Recall the constructed stochastic matrix gradient is Gt = Q⊤ diag(gt )P. The Muon optimizer updates the weight matrix W by moving in the direction of the orthogonalized gradient, computed via the thin SVD: Gt = UΛV⊤ , where the update direction is msign (Gt ) = UV⊤ . We can explicitly write the SVD of our constructed Gt . Let S = diag(sign (gt )) and Λ = diag(|gt |). We have: Gt = Q⊤ SΛP = Q⊤ diag(sign (gt )) diag(|gt |)P. Notice that Q⊤ diag(sign (gt )) is an m × m matrix with orthonormal columns (since both Q⊤ and diag(±1) are orthogonal), diag(|gt |) is an m × m non-negative diagonal matrix, and P is an m × n matrix with orthonormal rows. This strictly matches the definition of the thin SVD. Thus, the orthogonal factor is uniquely identified as: msign (Gt ) = UV⊤ = Q⊤ diag(sign (gt ))P. The Muon update rule Wt+1 = Wt − η msign (Gt ) then translates to: Wt+1 = Wt − ηQ⊤ diag(sign (gt ))P. Left-multiplying by Q and right-multiplying by P⊤ , we obtain: QWt+1 P⊤ = QWt P⊤ − η diag(sign (gt )). By isolating the diagonal entries xt,i = (QWt P⊤ )ii , we recover the exact SignSGD coordinate-wise update: xt+1 = xt − η sign (gt ) . This establishes a strict dynamic isomorphism: the sequence of the extracted diagonal entries perfectly replicates the trajectory of SignSGD running on the vector function f (x). By Lemma 6 and Lemma 7, F (W) satisfies Assumption 2b with noise covariance Σ = Q⊤ diag(σ)Q and Assumption 3b with L∗ = L∞ . Furthermore, the trace norm (nuclear norm) of the noise covariance matrix strictly aligns: ∥Σ∥∗ = tr(Σ) = ∥σ∥1 . Finally, observe the true gradient ∇F (Wt ) = Q⊤ diag(∇f (xt ))P. Because orthogonal transformations preserve singular values, the singular values of ∇F (Wt ) are exactly the absolute values of the components of ∇f (xt ). Thus, the nuclear norm of the matrix gradient equals the ℓ1 -norm of the vector gradient: ∥∇F (Wt )∥∗ = ∥∇f (xt )∥1 . Because the optimization trajectories are identical and all bounding metrics perfectly correspond, we can directly invoke the vector lower bound from Theorem 2 to establish the matrix lower bound for Muon: r 1 ! h i L∗ ∆ ∥Σ∥2∗ L∗ ∆ 4 E min∥∇F (Wt )∥∗ = Ω + . t N N This completes the proof.
E
Experimental Details
In this section, we will present the omitted details for experiments. E.1 Experimental Details for LLMs Here, we present the omitted details for the experiments in Section 4.2.2 and Figure 2a. We conduct all experiments using PyTorch and Distributed Data Parallel (DDP) across four NVIDIA Pro 6000 GPUs (96GB VRAM each). Our results are based on the codebase provided by Semenov et al. [2025], which can be found at https://github.com/epfml/llm-optimizer-benchmark/tree/ main/scripts. The GPT2-small model is trained for 10k steps with a global batch size of 512 sequences, and we use a standard sequence length of 512, thus totaling approximately 1× the Chinchilla-optimal token count as suggested by Hoffmann et al. [2022]. The best learning rates of SignSGD and SGD are found via grid search in {1e − 2, 1e − 3, 1e − 4}. We employ a linear warm-up period of 10% total iterations at the start of pretraining. 24
60
SGD signSGD
2500
SGD signSGD
50
2000
40
Loss
Loss
1500 1000
30 20
500
10
0
0 0
500
1000
1500
Iteration
2000
2500
0
3000
(a) Deterministic case with anisotropic curvature.
500
1000
1500
Iteration
2000
2500
3000
(b) Stochastic example with sparse noise.
Figure 3: Empirical toy problems demonstrating settings where SignSGD converges provably faster than SGD. Figure 3a illustrates the deterministic convergence on an imbalanced quadratic objective Pd 2 5000 f (x) = , where the curvature is dominated by a single dimension i=1 Li xi /2 for x ∈ R (L1 = 1000, Li>1 = 1). This highly skewed ℓ∞ -smooth geometry severely bottlenecks the learning rate of SGD, whereas SignSGD maintains steady convergence. Figure 3b demonstrates the training loss curve on a simple isotropic quadratic objective f (x) = ∥x∥2 /2 for x ∈ R100 , where we inject Gaussian noise N (0, 1002 ) exclusively into the first gradient component to simulate extreme noise sparsity. E.2 Experimental Details for CNNs Here, we present the omitted details for the experiments on Figure 2b. We followed the codebase in Bernstein et al. [2018], which can be found at https://github.com/jxbz/signSGD. To ensure a fully standard and exact mathematical comparison with our LLM framework, we ported their precise architectural definitions to modern PyTorch and implemented a fully distributed variancetracking system using PyTorch’s Distributed Data Parallel (DDP). Then, we conduct all experiments across four NVIDIA Pro 6000 GPUs (96GB VRAM each).
25