Muon with Finite Newton-Schulz: The Smoothing Benefit in Nonsmooth Nonconvex Optimization

# The Smoothing Benefit in Nonsmooth Nonconvex Optimization
Source: [https://arxiv.org/html/2608.26288](https://arxiv.org/html/2608.26288)
## Muon with Finite Newton–Schulz: The Smoothing Benefit in Nonsmooth Nonconvex OptimizationThanks:Authors are listed in alphabetical order\.

Taira TsuchiyaNote:The University of Tokyo and RIKEN;tsuchiya@mist\.i\.u\-tokyo\.ac\.jp\.

August 26, 2026

###### Abstract

Muon has emerged as a strong optimizer for the matrix\-valued parameters in large language model pretraining, approximately orthogonalizing its momentum with a few Newton–Schulz iterations\. Existing theory either replaces this iteration with the exact polar factor it approximates, or treats its finite depth as an approximation error, and thus the iteration Muon actually runs can only hurt the guarantees\. We show that finite Newton–Schulz can instead be beneficial for nonsmooth nonconvex optimization\. To this end, we analyze Muon through the online\-to\-nonconvex conversion, which views the update rule as an online learner and converts its regret bound into a stationarity guarantee\. The finite Newton–Schulz iteration smooths the discontinuous polar map into a Lipschitz map of the singular values, and Muon with finite Newton–Schulz can be regarded as an online learner with a smoothed spectral potential\. This smoothing is exactly what the conversion needs: we prove that a Newton–Schulz depth growing only logarithmically in the target accuracy suffices for convergence to stationary points in nonsmooth nonconvex optimization, whereas Muon with the exact\-polar update may fail to converge\. The resulting sample complexity bounds match the best\-known guarantees for nonsmooth nonconvex optimization and are optimal for smooth nonconvex optimization up to problem\-dependent factors\. The argument extends beyond Newton–Schulz to general spectral maps with the same smoothing property\.

## 1Introduction

In large language model \(LLM\) pretraining, where most trainable parameters are matrices, Muon\([Jordan et al\., 2024](https://arxiv.org/html/2608.26288#bib.bib28)\)has emerged as a strong alternative to the de facto standard AdamW\([Loshchilov and Hutter, 2019](https://arxiv.org/html/2608.26288#bib.bib40)\)\. Scaling studies report substantial efficiency gains\([Liu et al\., 2025](https://arxiv.org/html/2608.26288#bib.bib37)\), Muon\-based optimizers have been used to train frontier models such as Kimi K2 and GLM\-4\.5\([Kimi Team, 2025](https://arxiv.org/html/2608.26288#bib.bib30);[GLM\-4\.5 Team, 2025](https://arxiv.org/html/2608.26288#bib.bib22)\), and a systematic benchmark places Muon among the strongest pretraining optimizers\([Wen et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib55)\)\. This success depends on an efficient implementation of the operation at the core of Muon, the orthogonalization of the update direction\.

At each round, Muon maintains an exponential moving averageMMof the stochastic gradients and steps along an orthogonalization ofMM: for a singular value decompositionM=U​Σ​V⊤M=U\\Sigma V^\{\\top\}, the ideal direction is the polar factorU​V⊤UV^\{\\top\}, which keeps the singular subspaces ofMMand maps every positive singular value to one\([Jordan et al\., 2024](https://arxiv.org/html/2608.26288#bib.bib28);[Bernstein and Newhouse, 2024](https://arxiv.org/html/2608.26288#bib.bib9)\)\. Instead of computingU​V⊤UV^\{\\top\}through a singular value decomposition, Muon approximates it with a few iterations of Newton–Schulz, a classical scheme built from a fixed odd matrix polynomial that requires only matrix–matrix multiplications\([Kovarik, 1970](https://arxiv.org/html/2608.26288#bib.bib33);[Björck and Bowie, 1971](https://arxiv.org/html/2608.26288#bib.bib11)\)\. We refer to the iteration truncated at a finite depth as finite Newton–Schulz\. This inexpensive orthogonalization is a key reason why Muon is practical at the scale of LLM pretraining\.

Muon’s empirical success has prompted a rapidly growing convergence theory, so far mostly for smooth objectives\. Most of it, however, replaces the Newton–Schulz loop with the exact polar factor, or, more generally, with an exact linear minimization oracle over a norm ball\([Li and Hong, 2025](https://arxiv.org/html/2608.26288#bib.bib35);[Kovalev, 2025](https://arxiv.org/html/2608.26288#bib.bib32);[Pethick et al\., 2025](https://arxiv.org/html/2608.26288#bib.bib46);[Shen et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib51);[Chen et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib15);[Riabinin et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib48);[Sfyraki and Wang, 2026](https://arxiv.org/html/2608.26288#bib.bib49),e\.g\.,\), so the finite Newton–Schulz iteration never enters the analysis\. More recent analyses account for the finite Newton–Schulz iteration, but treat its finite\-depth effect as an approximation error relative to the exact\-polar update\([Kim and Oh, 2026](https://arxiv.org/html/2608.26288#bib.bib29);[Shulgin et al\., 2026a](https://arxiv.org/html/2608.26288#bib.bib52);[Choudhury et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib16)\)\. In these analyses, finite Newton–Schulz can only hurt because the guarantees improve when the iteration more closely approximates the exact polar factor\.

A separate line of theoretical work removes the smoothness assumption on the objective and instead builds on online learning\. The online\-to\-nonconvex conversion \(O2NC\) of[Cutkosky et al\. \(2023\)](https://arxiv.org/html/2608.26288#bib.bib17)lets an online learner choose the update increments of an optimizer\. The learner’s regret then translates into a bound on a relaxed, Goldstein\-type stationarity measure\([Goldstein, 1977](https://arxiv.org/html/2608.26288#bib.bib23)\), the standard target in nonsmooth nonconvex optimization\. Applying this framework to matrix optimizers,[Jiang et al\. \(2026a\)](https://arxiv.org/html/2608.26288#bib.bib26)observe that Muon with the exact\-polar update coincides with follow\-the\-leader over the operator\-norm ball, an online algorithm that can suffer linear regret and thus cannot guarantee convergence to stationary points\. They therefore replace the online learner, injecting stochastic perturbations or augmenting the momentum matrix, and derive the Pion and Leon algorithms, which come with stationarity guarantees for nonsmooth objectives\. These methods, however, depart from Muon as implemented: they add ingredients that Muon does not use, and the finite Newton–Schulz iteration that Muon does use never enters their analyses\.

Thus one line of work admits finite Newton–Schulz only as an error to be controlled and requires smoothness, while the other handles nonsmooth objectives but replaces the update that Muon actually performs\. This leaves the basic question open:

*Can the finite Newton–Schulz iteration be a benefit rather than an error, enabling Muon with momentum to find stationary points of nonsmooth objectives?*

### 1\.1Contributions of this paper

We answer this question affirmatively\. With momentum and finite Newton–Schulz, Muon finds stationary points of nonsmooth objectives, whereas with the exact\-polar update it may fail to converge\([Parshakova et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib44)\)\. The reason is that the finite iteration replaces the discontinuous polar map with a Lipschitz map of the singular values, and this smoothing enables the online\-to\-nonconvex conversion to provide a stationarity guarantee\.

The following informal statement summarizes the resulting guarantee\.

###### Theorem 1\.1\(Informal version of[Theorem5\.3](https://arxiv.org/html/2608.26288#S5.Thmtheorem3)\)\.

Consider a Lipschitz objective that may be neither smooth nor convex, accessed through an unbiased stochastic gradient oracle with bounded noise\. Then, for any radiusρ\>0\\rho\>0and accuracyε\>0\\varepsilon\>0, Muon with momentum andq=O⁡\(log⁡\(1/ε\)\)q=O\(\\log\(1/\\varepsilon\)\)Newton–Schulz steps per round finds a\(ρ,ε\)\(\\rho,\\varepsilon\)\-stationary point in expectation withinO⁡\(ρ−1​ε−3\+ε−2\)O\(\\rho^\{\-1\}\\varepsilon^\{\-3\}\+\\varepsilon^\{\-2\}\)stochastic gradient evaluations\.

The stationarity criterion is the\(ρ,ε\)\(\\rho,\\varepsilon\)\-stationarity of[Jiang et al\. \(2026a\)](https://arxiv.org/html/2608.26288#bib.bib26), stated as[Definition2\.2](https://arxiv.org/html/2608.26288#S2.Thmtheorem2), and the leadingρ−1​ε−3\\rho^\{\-1\}\\varepsilon^\{\-3\}dependence matches the guarantees established for Pion and Leon under the same criterion \(see[AppendixA](https://arxiv.org/html/2608.26288#A1)\)\. To our knowledge, this is the first stationarity guarantee for nonsmooth nonconvex objectives in which finite Newton–Schulz acts as the smoothing mechanism that enables convergence rather than as an approximation error to be controlled\. The required depth grows only logarithmically in the target accuracy, which is consistent with the empirical observation that a few Newton–Schulz iterations suffice in practice\([Jordan et al\., 2024](https://arxiv.org/html/2608.26288#bib.bib28)\)\. The precise variant we analyze and its remaining differences from deployed Muon are specified in[Section2](https://arxiv.org/html/2608.26288#S2)and discussed in[Section6](https://arxiv.org/html/2608.26288#S6)\.

##### Technical contributions\.

By the online\-to\-nonconvex conversion, it suffices to bound the discounted regret that Muon’s update rule incurs as an online learner over the operator\-norm ball\([Cutkosky et al\., 2023](https://arxiv.org/html/2608.26288#bib.bib17);[Jiang et al\., 2026a](https://arxiv.org/html/2608.26288#bib.bib26)\)\. We show that this update is the gradient of a smoothed spectral potential evaluated at the momentum, so the learner is a gradient\-based prediction algorithm\([Abernethy et al\., 2014](https://arxiv.org/html/2608.26288#bib.bib1);[Abernethy et al\., 2016](https://arxiv.org/html/2608.26288#bib.bib2)\)\. The discounted regret of such an algorithm decomposes into a penalty term, which shrinks as the potential approaches the nuclear norm, and a stability term, which grows with the Lipschitz constant of the induced spectral map\. Unlike the standard decomposition in terms of the cumulative gradients\([Jiang et al\., 2026a](https://arxiv.org/html/2608.26288#bib.bib26)\), ours is carried out in terms of the momentum, which yields the optimalO⁡\(1/ε2\)O\(1/\\varepsilon^\{2\}\)dependence for deterministic smooth objectives \([Section5\.3](https://arxiv.org/html/2608.26288#S5.SS3)\)\. Our key lemma \([Lemma5\.2](https://arxiv.org/html/2608.26288#S5.Thmtheorem2)\) quantifies both terms for finite Newton–Schulz: the penalty decays and the stability grows, both geometrically inqq\. The depth therefore governs a penalty–stability tradeoff, and balancing the two terms yields sublinear discounted regret atq=O⁡\(log⁡\(1/ε\)\)q=O\(\\log\(1/\\varepsilon\)\)and, through the conversion, the guarantee above \([Section5](https://arxiv.org/html/2608.26288#S5)\)\. Asq→∞q\\to\\infty, the update approaches the exact polar factor, and the stability term grows without bound, reflecting the linear regret that follow\-the\-leader can suffer\.

The Muon learner is also follow\-the\-regularized\-leader \(FTRL\) on the discounted linear losses, with a spectral regularizer given by the Fenchel conjugate of the smoothed potential \([Theorem5\.7](https://arxiv.org/html/2608.26288#S5.Thmtheorem7)\)\. The depth controls the amount of regularization: atq=0q=0the regularizer becomes the squared Frobenius regularizer restricted to the operator\-norm ball, and asq→∞q\\to\\inftyit decays to zero on the ball and the update approaches follow\-the\-leader\.

The analysis is not specific to the Newton–Schulz polynomial\. The regret bound holds for more general spectral maps of the singular values \([Theorem4\.2](https://arxiv.org/html/2608.26288#S4.Thmtheorem2)\), which is useful to identify sufficient conditions for such maps to yield stationarity guarantees on nonsmooth objectives\. In particular, recent work designs a smooth relaxation of the polar transformation and derives its associated convex regularizer\([Mustafi et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib43);[Feoktistov et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib21)\), and our general analysis covers such relaxations \([AppendixF](https://arxiv.org/html/2608.26288#A6)\)\. In contrast to these studies, we show that the finite Newton–Schulz iteration itself smooths the polar transformation and induces an FTRL regularizer, without introducing a separate relaxation\.

### 1\.2Related work

##### Muon optimizer\.

Muon was proposed by[Jordan et al\. \(2024\)](https://arxiv.org/html/2608.26288#bib.bib28)as an optimizer for the matrix\-shaped hidden layers of neural networks\. Spectral update directions were used earlier in preconditioned spectral descent\([Carlson et al\., 2015](https://arxiv.org/html/2608.26288#bib.bib13)\), and the steepest\-descent and duality interpretations of Muon are developed by[Bernstein and Newhouse \(2024\)](https://arxiv.org/html/2608.26288#bib.bib9);[Bernstein and Newhouse \(2025\)](https://arxiv.org/html/2608.26288#bib.bib10)\. Convergence guarantees for Muon with the exact\-polar update or an exact linear minimization oracle have been established under smoothness and generalized smoothness\([Li and Hong, 2025](https://arxiv.org/html/2608.26288#bib.bib35);[Kovalev, 2025](https://arxiv.org/html/2608.26288#bib.bib32);[Pethick et al\., 2025](https://arxiv.org/html/2608.26288#bib.bib46);[Shen et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib51);[Chen et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib15);[Riabinin et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib48);[Sfyraki and Wang, 2026](https://arxiv.org/html/2608.26288#bib.bib49)\)\. Its implicit bias, the denoising role of momentum, and the regimes in which spectral updates outperform Euclidean ones have also been studied\([Fan et al\., 2025](https://arxiv.org/html/2608.26288#bib.bib20);[Li et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib36);[Davis and Drusvyatskiy, 2025](https://arxiv.org/html/2608.26288#bib.bib18);[Braun et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib12)\)\. For Muon with the exact\-polar update,[Parshakova et al\. \(2026\)](https://arxiv.org/html/2608.26288#bib.bib44)construct convex Lipschitz objectives on which the iterates fail to converge, which sharpens the question of what changes under finite Newton–Schulz on nonsmooth problems\. Our work takes up this question, analyzing the update that retains both momentum and finite Newton–Schulz on nonsmooth nonconvex objectives\.

##### Newton–Schulz and general spectral maps\.

Iterative orthogonalization by matrix polynomials goes back to[Kovarik \(1970\)](https://arxiv.org/html/2608.26288#bib.bib33)and[Björck and Bowie \(1971\)](https://arxiv.org/html/2608.26288#bib.bib11), and the iterations used in Muon range from empirically tuned polynomials\([Jordan et al\., 2024](https://arxiv.org/html/2608.26288#bib.bib28)\)to optimal polynomial schemes designed for this purpose\([Amsel et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib6)\)\. Analyses of Muon that include the finite iteration treat the effect of the finite iteration as an error: for smooth nonconvex objectives\([Kim and Oh, 2026](https://arxiv.org/html/2608.26288#bib.bib29)\), through inexact linear minimization oracles\([Shulgin et al\., 2026a](https://arxiv.org/html/2608.26288#bib.bib52)\), and for Nesterov momentum under heavy\-tailed noise\([Choudhury et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib16)\)\. A few recent works identify benefits of orthogonalization and of its finite approximations in structured settings: on matrix quadratics, finite Newton–Schulz damps directions associated with small singular values near rank deficiency\([Shulgin et al\., 2026b](https://arxiv.org/html/2608.26288#bib.bib53)\), inexact polar updates can improve reachability on simple strongly convex quadratics\([Gonon et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib24)\), and spectral orthogonalization acts as a preconditioner in matrix factorization and in\-context learning models\([Ma et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib41)\)\. These benefits are confined to quadratic or otherwise structured objectives\. In contrast, we show that finite Newton–Schulz enables stationarity guarantees for general nonsmooth nonconvex objectives and characterize how the depth trades off polar approximation against the stability of the online updates\. Beyond the exact polar factor, recent work has considered more general spectral maps\([Qi et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib47);[Dong and Sawin, 2026](https://arxiv.org/html/2608.26288#bib.bib19);[Jiang et al\., 2026b](https://arxiv.org/html/2608.26288#bib.bib27);[Wu et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib56)\), including smooth relaxations of spectral normalization and orthogonalization\([Feoktistov et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib21);[Mustafi et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib43)\)\. Our theory in[Section4](https://arxiv.org/html/2608.26288#S4)gives sufficient conditions under which such maps enjoy stationarity guarantees for nonsmooth nonconvex objectives\.

##### Online\-to\-nonconvex conversion\.

The online\-to\-nonconvex conversion \(O2NC\) framework was introduced by[Cutkosky et al\. \(2023\)](https://arxiv.org/html/2608.26288#bib.bib17), who convert online regret guarantees into optimal stationarity guarantees for stochastic nonsmooth nonconvex optimization\. The framework can also exploit additional properties of an objective: it attains the optimal first\-order complexity for deterministic smooth objectives\([Cutkosky et al\., 2023](https://arxiv.org/html/2608.26288#bib.bib17)\), and the best\-known complexity when both the gradient and Hessian are Lipschitz\([Patitucci et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib45)\)\. The discounted O2NC framework, which is central to our analysis of Muon’s momentum, grew out of O2NC variants based on random scaling and model exponential moving averages\([Zhang and Cutkosky, 2024](https://arxiv.org/html/2608.26288#bib.bib58);[Ahn and Cutkosky, 2024](https://arxiv.org/html/2608.26288#bib.bib3)\)\. The broader online\-learning perspective has also been used to understand practical optimizers such as Adam\([Ahn et al\., 2024](https://arxiv.org/html/2608.26288#bib.bib4)\)and schedule\-free SGD\([Ahn et al\., 2025](https://arxiv.org/html/2608.26288#bib.bib5)\), and to handle heavy\-tailed gradient noise\([Liu et al\., 2024](https://arxiv.org/html/2608.26288#bib.bib38);[Liu, 2026](https://arxiv.org/html/2608.26288#bib.bib39)\)and weakly convex optimization\([Ji and Yuan, 2026](https://arxiv.org/html/2608.26288#bib.bib25)\)\. Most closely related to our matrix setting,[Jiang et al\. \(2026a\)](https://arxiv.org/html/2608.26288#bib.bib26)construct a family of smoothed potentials for the nuclear norm and use the resulting adaptive matrix online learners to derive Pion and Leon, which have a convergence guarantee in nonsmooth optimization\. In contrast, we analyze the finite Newton–Schulz transformation underlying Muon and show that finite depth smooths the exact\-polar update by quantifying how the depth trades off polar approximation against the stability of successive updates from the online\-to\-nonconvex conversion perspective\. A detailed comparison with the closest smooth and nonsmooth guarantees is provided in[AppendixA](https://arxiv.org/html/2608.26288#A1)\.

## 2Optimization setting and the Muon update

This section formalizes the optimization problem, the stationarity criterion, and the Muon update that we analyze\.

##### Notation\.

We work with matrices inℝm×n\\mathbb\{R\}^\{m\\times n\}with1≤m≤n1\\leq m\\leq nand setr≔min⁡\{m,n\}=mr\\coloneqq\\min\\\{m,n\\\}=m\. The casem\>nm\>nis reduced to this one by transposing every matrix\. We writeσ1​\(X\)≥⋯≥σr​\(X\)≥0\\sigma\_\{1\}\(X\)\\geq\\cdots\\geq\\sigma\_\{r\}\(X\)\\geq 0for the singular values ofX∈ℝm×nX\\in\\mathbb\{R\}^\{m\\times n\}and setσ⁡\(X\)≔\(σ1​\(X\),…,σr​\(X\)\)\\sigma\(X\)\\coloneqq\(\\sigma\_\{1\}\(X\),\\ldots,\\sigma\_\{r\}\(X\)\)\. We writediag\(x1,…,xr\)∈ℝr×r\\diag\(x\_\{1\},\\ldots,x\_\{r\}\)\\in\\mathbb\{R\}^\{r\\times r\}for the diagonal matrix with diagonal entriesx1,…,xrx\_\{1\},\\ldots,x\_\{r\}\. We write⟨X,Y⟩≔tr\(X⊤​Y\)\\langle X,Y\\rangle\\coloneqq\\tr\(X^\{\\top\}Y\)for the Frobenius inner product and define the operator, Frobenius, and nuclear norms by∥X∥op≔σ1​\(X\)\\lVert X\\rVert\_\{\\mathrm\{op\}\}\\coloneqq\\sigma\_\{1\}\(X\),∥X∥F≔∑i=1rσi​\(X\)2\\lVert X\\rVert\_\{\\mathrm\{F\}\}\\coloneqq\\sqrt\{\\sum\_\{i=1\}^\{r\}\\sigma\_\{i\}\(X\)^\{2\}\}, and∥X∥∗≔∑i=1rσi​\(X\)\\lVert X\\rVert\_\{\*\}\\coloneqq\\sum\_\{i=1\}^\{r\}\\sigma\_\{i\}\(X\)\. These norms satisfy∥X∥op≤∥X∥F≤r​∥X∥op\\lVert X\\rVert\_\{\\mathrm\{op\}\}\\leq\\lVert X\\rVert\_\{\\mathrm\{F\}\}\\leq\\sqrt\{r\}\\,\\lVert X\\rVert\_\{\\mathrm\{op\}\}and∥X∥F≤∥X∥∗≤r​∥X∥F\\lVert X\\rVert\_\{\\mathrm\{F\}\}\\leq\\lVert X\\rVert\_\{\*\}\\leq\\sqrt\{r\}\\,\\lVert X\\rVert\_\{\\mathrm\{F\}\}\. For a positive integerkk, let\[k\]≔\{1,…,k\}\[k\]\\coloneqq\\\{1,\\ldots,k\\\}\. For a scalar functionhh, we useLip⁡\(h\)\\Lip\(h\)to denote its Lipschitz constant\. For a differentiable functionΦ\\Phi, we useBΦ\(M′∥M\)≔Φ\(M′\)−Φ\(M\)−⟨∇Φ\(M\),M′−M⟩B\_\{\\Phi\}\(M^\{\\prime\}\\\|M\)\\coloneqq\\Phi\(M^\{\\prime\}\)\-\\Phi\(M\)\-\\langle\\nabla\\Phi\(M\),M^\{\\prime\}\-M\\rangleto denote the Bregman divergence fromMMtoM′M^\{\\prime\}induced byΦ\\Phi\.

##### Polar factor and singular\-value maps\.

LetS=Udiag\(σ1\(S\),…,σr\(S\)\)V⊤S=U\\diag\(\\sigma\_\{1\}\(S\),\\ldots,\\sigma\_\{r\}\(S\)\)V^\{\\top\}be a thin singular value decomposition\. Define its polar factor bypolar\(S\)≔Udiag\(𝟏\{σi\(S\)\>0\}\)V⊤\\polar\(S\)\\coloneqq U\\diag\(\\mathbf\{1\}\\\{\\sigma\_\{i\}\(S\)\>0\\\}\)V^\{\\top\}, where𝟏​\{⋅\}\\mathbf\{1\}\\\{\\cdot\\\}denotes the indicator function\. The value ofpolar⁡\(S\)\\polar\(S\)is independent of the chosen thin singular value decomposition\. The operator and nuclear norms are dual, so for everyS∈ℝm×nS\\in\\mathbb\{R\}^\{m\\times n\}and radiusD\>0D\>0,

sup∥X∥op≤D⟨S,X⟩=D​∥S∥∗,\\sup\_\{\\lVert X\\rVert\_\{\\mathrm\{op\}\}\\leq D\}\\langle S,X\\rangle=D\\lVert S\\rVert\_\{\*\},\(1\)where the supremum is attained by the matrixD​polar⁡\(S\)D\\polar\(S\)\. For a scalar functionh:\[0,∞\)→ℝh\\colon\[0,\\infty\)\\to\\mathbb\{R\}withh⁡\(0\)=0h\(0\)=0, define the singular\-value map

ℋh\(S\)≔Udiag\(h\(σ1\(S\)\),…,h\(σr\(S\)\)\)V⊤\\mathcal\{H\}\_\{h\}\(S\)\\coloneqq U\\diag\\left\(h\(\\sigma\_\{1\}\(S\)\),\\ldots,h\(\\sigma\_\{r\}\(S\)\)\\right\)V^\{\\top\}\(2\)forS=Udiag\(σ1\(S\),…,σr\(S\)\)V⊤S=U\\diag\(\\sigma\_\{1\}\(S\),\\ldots,\\sigma\_\{r\}\(S\)\)V^\{\\top\}\. The value ofℋh​\(S\)\\mathcal\{H\}\_\{h\}\(S\)is independent of the chosen thin singular value decomposition\. Indeed, a thin singular value decomposition is unique up to a simultaneous orthogonal change of basis inUUandVVwithin each group of repeated positive singular values, and this change cancels in[2](https://arxiv.org/html/2608.26288#S2.E2)\. The singular vectors associated with zero singular values can be chosen independently inUUandVV, but the corresponding terms vanish sinceh⁡\(0\)=0h\(0\)=0\.

### 2\.1Objective and stationarity

Let𝒟\\mathcal\{D\}be a probability distribution on a sample space𝒵\\mathcal\{Z\}, and letℓ:ℝm×n×𝒵→ℝ\\ell\\colon\\mathbb\{R\}^\{m\\times n\}\\times\\mathcal\{Z\}\\to\\mathbb\{R\}be a loss function\. We consider the nonconvex matrix optimization problem

minW∈ℝm×n⁡ℒ⁡\(W\)≔𝔼ζ∼𝒟​\[ℓ⁡\(W,ζ\)\]\.\\min\_\{W\\in\\mathbb\{R\}^\{m\\times n\}\}\\mathcal\{L\}\(W\)\\coloneqq\\mathbb\{E\}\_\{\\zeta\\sim\\mathcal\{D\}\}\[\\ell\(W;\\zeta\)\]\.We impose the following conditions on the objectiveℒ\\mathcal\{L\}and the stochastic gradient oracle\.

###### Assumption 2\.1\.

The functionℒ\\mathcal\{L\}is differentiable111As discussed in[Cutkosky et al\. \(2023, Proposition 2 and Corollary 6\)](https://arxiv.org/html/2608.26288#bib.bib17), for a locally Lipschitz objective that is not differentiable everywhere, we can construct a differentiable surrogate objectiveℒ^δ​\(W\)≔𝔼U​\[ℒ⁡\(W\+δ​U\)\]\\widehat\{\\mathcal\{L\}\}\_\{\\delta\}\(W\)\\coloneqq\\mathbb\{E\}\_\{U\}\[\\mathcal\{L\}\(W\+\\delta U\)\], whereδ\>0\\delta\>0andUUis uniform on the Frobenius unit ball, and this does not worsen the resulting stationarity guarantees\.and bounded below\. There are constantsΓ\>0\\Gamma\>0andσ≥0\\sigma\\geq 0such that, at every query pointW∈ℝm×nW\\in\\mathbb\{R\}^\{m\\times n\}, the oracle uses a random seed independent of the preceding history and returns a stochastic gradientGGsatisfying

𝔼⁡\[G∣W\]=∇ℒ​\(W\),𝔼⁡\[∥G∥F2∣W\]≤Γ2,𝔼⁡\[∥G−∇ℒ​\(W\)∥F2∣W\]≤σ2\.\\mathbb\{E\}\[G\\mid W\]=\\nabla\\mathcal\{L\}\(W\),\\qquad\\mathbb\{E\}\[\\lVert G\\rVert\_\{\\mathrm\{F\}\}^\{2\}\\mid W\]\\leq\\Gamma^\{2\},\\qquad\\mathbb\{E\}\[\\lVert G\-\\nabla\\mathcal\{L\}\(W\)\\rVert\_\{\\mathrm\{F\}\}^\{2\}\\mid W\]\\leq\\sigma^\{2\}\.\(3\)

For the initial pointW0∈ℝm×nW\_\{0\}\\in\\mathbb\{R\}^\{m\\times n\}, letΔℒ≔ℒ⁡\(W0\)−infW∈ℝm×nℒ⁡\(W\)<∞\\Delta\_\{\\mathcal\{L\}\}\\coloneqq\\mathcal\{L\}\(W\_\{0\}\)\-\\inf\_\{W\\in\\mathbb\{R\}^\{m\\times n\}\}\\mathcal\{L\}\(W\)<\\infty\. Note that we have∥∇ℒ​\(W\)∥F≤Γ\\lVert\\nabla\\mathcal\{L\}\(W\)\\rVert\_\{\\mathrm\{F\}\}\\leq\\Gammafor everyWWby Jensen’s inequality and[Assumption2\.1](https://arxiv.org/html/2608.26288#S2.Thmtheorem1), and thusℒ\\mathcal\{L\}isΓ\\Gamma\-Lipschitz with respect to the Frobenius norm\. We do not assume smoothness ofℒ\\mathcal\{L\}\. Without loss of generality, we assumeΓ≤r​Gop\\Gamma\\leq\\sqrt\{r\}\\,G\_\{\\mathrm\{op\}\}when∥Gt∥op≤Gop\\lVert G\_\{t\}\\rVert\_\{\\mathrm\{op\}\}\\leq G\_\{\\mathrm\{op\}\}, since this implies𝔼⁡\[∥G∥F2∣W\]≤r​Gop2\\mathbb\{E\}\[\\lVert G\\rVert\_\{\\mathrm\{F\}\}^\{2\}\\mid W\]\\leq rG\_\{\\mathrm\{op\}\}^\{2\}\.

To cover objectives without smoothness, we measure progress by the following notion of\(ρ,ε\)\(\\rho,\\varepsilon\)\-stationarity\.

###### Definition 2\.2\([Jiang et al\., 2026a](https://arxiv.org/html/2608.26288#bib.bib26), Definition 9\)\.

ForW∈ℝm×nW\\in\\mathbb\{R\}^\{m\\times n\}andρ\>0\\rho\>0, let𝒫⁡\(W,ρ\)\\mathcal\{P\}\(W;\\rho\)be the set of finitely supported probability distributionspponℝm×n\\mathbb\{R\}^\{m\\times n\}such that𝔼Y∼p​\[Y\]=W\\mathbb\{E\}\_\{Y\\sim p\}\[Y\]=Wand𝔼Y∼p​∥Y−W∥op≤ρ\\mathbb\{E\}\_\{Y\\sim p\}\\lVert Y\-W\\rVert\_\{\\mathrm\{op\}\}\\leq\\rho\. Forε≥0\\varepsilon\\geq 0, a pointWWis said to be a*\(ρ,ε\)\(\\rho,\\varepsilon\)\-stationary point*if∥∇ℒ\(W\)∥∗\[ρ\]≔infp∈𝒫⁡\(W,ρ\)∥𝔼Y∼p∇ℒ\(Y\)∥∗≤ε\\lVert\\nabla\\mathcal\{L\}\(W\)\\rVert\_\{\*\}^\{\[\\rho\]\}\\coloneqq\\inf\_\{p\\in\\mathcal\{P\}\(W;\\rho\)\}\\lVert\\mathbb\{E\}\_\{Y\\sim p\}\\nabla\\mathcal\{L\}\(Y\)\\rVert\_\{\*\}\\leq\\varepsilon\.

The point mass atWWbelongs to𝒫⁡\(W,ρ\)\\mathcal\{P\}\(W;\\rho\), so∥∇ℒ​\(W\)∥∗\[ρ\]≤∥∇ℒ​\(W\)∥∗\\lVert\\nabla\\mathcal\{L\}\(W\)\\rVert\_\{\*\}^\{\[\\rho\]\}\\leq\\lVert\\nabla\\mathcal\{L\}\(W\)\\rVert\_\{\*\}\. Other distributions in𝒫⁡\(W,ρ\)\\mathcal\{P\}\(W;\\rho\)allow gradients at different points to cancel on average\. For general Lipschitz nonsmooth objectives, such relaxations are unavoidable\([Zhang et al\., 2020](https://arxiv.org/html/2608.26288#bib.bib57);[Kornowski and Shamir, 2022](https://arxiv.org/html/2608.26288#bib.bib31)\)\.

### 2\.2Muon with momentum and finite Newton–Schulz

For matrix parameters, Muon maintains gradient momentum and approximately orthogonalizes it with a few Newton–Schulz iterations\. The specific Muon update investigated in this paper is given in[Algorithm1](https://arxiv.org/html/2608.26288#algorithm1)\.

Algorithm 1Muon online learner with momentum and finite Newton–SchulzRequire :momentum

β∈\(0,1\)\\beta\\in\(0,1\), radius

D\>0D\>0, operator\-norm bound

Gop\>0G\_\{\\mathrm\{op\}\}\>0, depth

q∈\{0,1,…\}q\\in\\\{0,1,\\ldots\\\}
1Set

M0←0M\_\{0\}\\leftarrow 0and

X1←0X\_\{1\}\\leftarrow 0;

2for

t=1,2,…t=1,2,\\ldotsdo

3Receive gradient feedback

GtG\_\{t\}after playing

XtX\_\{t\};

4Update momentum

Mt←β​Mt−1\+\(1−β\)​GtM\_\{t\}\\leftarrow\\beta M\_\{t\-1\}\+\(1\-\\beta\)G\_\{t\};

5Normalize momentum by

Y←Mt/GopY\\leftarrow M\_\{t\}/G\_\{\\mathrm\{op\}\};

6for

j=1,…,qj=1,\\ldots,qdo

7

B←Y​Y⊤B\\leftarrow YY^\{\\top\},

P←B​YP\\leftarrow BY,

Q←B​PQ\\leftarrow BP;

8

Y←158​Y−54​P\+38​QY\\leftarrow\\frac\{15\}\{8\}Y\-\\frac\{5\}\{4\}P\+\\frac\{3\}\{8\}Q;

9Set

Xt\+1←−D​YX\_\{t\+1\}\\leftarrow\-DY;

The learner in[Algorithm1](https://arxiv.org/html/2608.26288#algorithm1)maintains the momentum sequence

M0≔0,Mt≔β​Mt−1\+\(1−β\)​Gt,M\_\{0\}\\coloneqq 0,\\qquad M\_\{t\}\\coloneqq\\beta M\_\{t\-1\}\+\(1\-\\beta\)G\_\{t\},\(4\)whereβ∈\(0,1\)\\beta\\in\(0,1\)is the momentum parameter, as in Line[1](https://arxiv.org/html/2608.26288#algorithm1)\. For the Muon learner, we assume that the stochastic gradients returned by the oracle are bounded in operator norm by the inputGop\>0G\_\{\\mathrm\{op\}\}\>0, that is,∥Gs∥op≤Gop\\lVert G\_\{s\}\\rVert\_\{\\mathrm\{op\}\}\\leq G\_\{\\mathrm\{op\}\}for everyss\. The normalization in Line[1](https://arxiv.org/html/2608.26288#algorithm1)then satisfies∥Mt/Gop∥op≤1\\lVert M\_\{t\}/G\_\{\\mathrm\{op\}\}\\rVert\_\{\\mathrm\{op\}\}\\leq 1\. Then the learner appliesqqNewton–Schulz steps in Line[1](https://arxiv.org/html/2608.26288#algorithm1)\([Kovarik, 1970](https://arxiv.org/html/2608.26288#bib.bib33);[Björck and Bowie, 1971](https://arxiv.org/html/2608.26288#bib.bib11)\)\. Finally, the learner sets the next action toXt\+1=−D​YX\_\{t\+1\}=\-DYin Line[1](https://arxiv.org/html/2608.26288#algorithm1)\.

In general, truncating the Taylor expansion ofλ−1/2\\lambda^\{\-1/2\}aroundλ=1\\lambda=1at orderκ≥1\\kappa\\geq 1gives

pκ​\(λ\)≔∑s=0κcs​\(1−λ\)s,cs≔\(2​s\)\!4s​\(s\!\)2\.p\_\{\\kappa\}\(\\lambda\)\\coloneqq\\sum\_\{s=0\}^\{\\kappa\}c\_\{s\}\(1\-\\lambda\)^\{s\},\\qquad c\_\{s\}\\coloneqq\\frac\{\(2s\)\!\}\{4^\{s\}\(s\!\)^\{2\}\}\.\(5\)Throughout this paper, we focus on the caseκ=2\\kappa=2as computed in Line[1](https://arxiv.org/html/2608.26288#algorithm1), which is the degree\-five Newton–Schulz transformation commonly used in Muon\. On the singular values, one step of Line[1](https://arxiv.org/html/2608.26288#algorithm1)then acts as

f⁡\(x\)≔x​p2​\(x2\)=158​x−54​x3\+38​x5,A≔f′​\(0\)=158\.f\(x\)\\coloneqq x\\,p\_\{2\}\(x^\{2\}\)=\\frac\{15\}\{8\}x\-\\frac\{5\}\{4\}x^\{3\}\+\\frac\{3\}\{8\}x^\{5\},\\qquad A\\coloneqq f^\{\\prime\}\(0\)=\\frac\{15\}\{8\}\.Forq∈\{0,1,2,…\}q\\in\\\{0,1,2,\\ldots\\\}, letf∘qf^\{\\circ q\}denote theqq\-fold composition offf, withf∘0f^\{\\circ 0\}the identity, and define

hq≔f∘qon​\[0,1\],hq​\(x\)≔1for​x≥1\.h\_\{q\}\\coloneqq f^\{\\circ q\}\\quad\\text\{on \}\[0,1\],\\qquad h\_\{q\}\(x\)\\coloneqq 1\\quad\\text\{for \}x\\geq 1\.\(6\)Under the operator\-norm bound above, the procedure in Lines[1](https://arxiv.org/html/2608.26288#algorithm1)–[1](https://arxiv.org/html/2608.26288#algorithm1)can be written as

Xt\+1=−D​ℋhq​\(Mt/Gop\)\.X\_\{t\+1\}=\-D\\mathcal\{H\}\_\{h\_\{q\}\}\(M\_\{t\}/G\_\{\\mathrm\{op\}\}\)\.\(7\)In the discounted online\-to\-nonconvex conversion framework introduced in[Section3](https://arxiv.org/html/2608.26288#S3), we use the learner in[Algorithm1](https://arxiv.org/html/2608.26288#algorithm1)as the online learner𝒜\\mathcal\{A\}to determine the update direction in the optimizer\.

Note that the learner in[Algorithm1](https://arxiv.org/html/2608.26288#algorithm1)differs from practical Muon implementations in several respects, including the fixed normalization discussed in[Section6](https://arxiv.org/html/2608.26288#S6)\. Nevertheless, it retains momentum and uses finitely many Newton–Schulz steps, as practical Muon does\.

## 3Discounted online\-to\-nonconvex conversion

Online\-to\-nonconvex conversion \(O2NC\) uses an online learner to select update directions and converts a bound on regret into a stationarity guarantee\([Cutkosky et al\., 2023](https://arxiv.org/html/2608.26288#bib.bib17)\)\. In particular, we use the discounted O2NC framework of[Jiang et al\. \(2026a\)](https://arxiv.org/html/2608.26288#bib.bib26), since it uses the same discount factorβ\\betaas the momentum update in[Algorithm1](https://arxiv.org/html/2608.26288#algorithm1)\.

##### Conversion mechanism\.

At each roundtt, the online learner chooses an incrementXtX\_\{t\}from the preceding gradient feedback, and the conversion setsWt=Wt−1\+XtW\_\{t\}=W\_\{t\-1\}\+X\_\{t\}\. To relate the online loss toℒ⁡\(Wt\)−ℒ⁡\(Wt−1\)\\mathcal\{L\}\(W\_\{t\}\)\-\\mathcal\{L\}\(W\_\{t\-1\}\), it queries the oracle at a random point on the segment between these endpoints\.[Algorithm2](https://arxiv.org/html/2608.26288#algorithm2)formalizes the overview in Section 5\.1 of[Jiang et al\. \(2026a\)](https://arxiv.org/html/2608.26288#bib.bib26), using the protocol in their Appendix G and the output rule in their Proposition 25\.

Algorithm 2Discounted O2NC with a generic online learnerRequire :horizon

TT, initial point

W0W\_\{0\}, discount

β∈\(0,1\)\\beta\\in\(0,1\), radius

D\>0D\>0, online learner

𝒜\\mathcal\{A\}
1Initialize

𝒜\\mathcal\{A\};

2for

t=1,2,…​Tt=1,2,\\dots Tdo

3Receive

XtX\_\{t\}satisfying

∥Xt∥op≤D\\lVert X\_\{t\}\\rVert\_\{\\mathrm\{op\}\}\\leq Dfrom the online learner

𝒜\\mathcal\{A\};

4Set

Wt←Wt−1\+XtW\_\{t\}\\leftarrow W\_\{t\-1\}\+X\_\{t\};

5Set

W~t←Wt−1\+ut​Xt\\widetilde\{W\}\_\{t\}\\leftarrow W\_\{t\-1\}\+u\_\{t\}X\_\{t\}for

ut∼Unif⁡\(\[0,1\]\)u\_\{t\}\\sim\\operatorname\{Unif\}\(\[0,1\]\);

6Query the stochastic gradient oracle at

W~t\\widetilde\{W\}\_\{t\}to obtain

GtG\_\{t\}satisfying[3](https://arxiv.org/html/2608.26288#S2.E3)with

W=W~tW=\\widetilde\{W\}\_\{t\};

7Construct and feed the linear loss

ℓt\[β\]​\(X\)≔β−t​⟨Gt,X⟩\\ell\_\{t\}^\{\[\\beta\]\}\(X\)\\coloneqq\\beta^\{\-t\}\\langle G\_\{t\},X\\rangleto

𝒜\\mathcal\{A\};

8Form

W¯t\\bar\{W\}\_\{t\}as in[8](https://arxiv.org/html/2608.26288#S3.E8), sample

τ\\taufrom[9](https://arxiv.org/html/2608.26288#S3.E9), and return

W¯τ\\bar\{W\}\_\{\\tau\};

The key observation for O2NC is that we can estimate the function changeℒ⁡\(Wt\)−ℒ⁡\(Wt−1\)\\mathcal\{L\}\(W\_\{t\}\)\-\\mathcal\{L\}\(W\_\{t\-1\}\)by choosing the query point appropriately, even without smoothness ofℒ\\mathcal\{L\}\. As in Line[2](https://arxiv.org/html/2608.26288#algorithm2), the conversion chooses the query pointW~t=Wt−1\+ut​Xt\\widetilde\{W\}\_\{t\}=W\_\{t\-1\}\+u\_\{t\}X\_\{t\}forut∼Unif⁡\(\[0,1\]\)u\_\{t\}\\sim\\operatorname\{Unif\}\(\[0,1\]\)and observes a conditionally unbiased gradientGtG\_\{t\}satisfying[Assumption2\.1](https://arxiv.org/html/2608.26288#S2.Thmtheorem1), as in Line[2](https://arxiv.org/html/2608.26288#algorithm2)\. With this choice of query point, under[Assumption2\.1](https://arxiv.org/html/2608.26288#S2.Thmtheorem1)the fundamental theorem of calculus along the segment fromWt−1W\_\{t\-1\}toWtW\_\{t\}gives

ℒ⁡\(Wt\)−ℒ⁡\(Wt−1\)=∫01⟨∇ℒ​\(Wt−1\+u​Xt\),Xt⟩​𝑑u=𝔼ut​\[⟨∇ℒ​\(W~t\),Xt⟩\]\.\\mathcal\{L\}\(W\_\{t\}\)\-\\mathcal\{L\}\(W\_\{t\-1\}\)=\\int\_\{0\}^\{1\}\\langle\\nabla\\mathcal\{L\}\(W\_\{t\-1\}\+uX\_\{t\}\),X\_\{t\}\\rangle\\,\\mathrm\{d\}u=\\mathbb\{E\}\_\{u\_\{t\}\}\\left\[\\langle\\nabla\\mathcal\{L\}\(\\widetilde\{W\}\_\{t\}\),X\_\{t\}\\rangle\\right\]\.This implies thatℒ\(Wt\)−ℒ\(Wt−1\)=𝔼\[⟨Gt,Xt⟩∣Wt−1,Xt\]\\mathcal\{L\}\(W\_\{t\}\)\-\\mathcal\{L\}\(W\_\{t\-1\}\)=\\mathbb\{E\}\[\\langle G\_\{t\},X\_\{t\}\\rangle\\mid W\_\{t\-1\},X\_\{t\}\]\. By this identity, controlling the decrease of the objective reduces to online linear optimization with gradient feedbackGtG\_\{t\}, without any smoothness ofℒ\\mathcal\{L\}\. The conversion then constructs the loss functionℓt\[β\]\\ell\_\{t\}^\{\[\\beta\]\}and feeds it to the online learner, as in Line[2](https://arxiv.org/html/2608.26288#algorithm2)\.

AfterTTrounds, as in Line[2](https://arxiv.org/html/2608.26288#algorithm2), the conversion computes the exponentially weighted average \(EWA\) iterates

W¯t≔1−β1−βt∑s=1tβt−sW~s,t=1,…,T,\\bar\{W\}\_\{t\}\\coloneqq\\frac\{1\-\\beta\}\{1\-\\beta^\{t\}\}\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\\widetilde\{W\}\_\{s\},\\qquad t=1,\\ldots,T,\(8\)and then chooses the randomized outputW¯τ\\bar\{W\}\_\{\\tau\}, where the output timeτ∈\[T\]\\tau\\in\[T\]is drawn independently according to the distribution given by

ℙ⁡\(τ=t\)≔\{1−βtT,1≤t<T,1−βT\(1−β\)​T,t=T\.\\mathbb\{P\}\(\\tau=t\)\\coloneqq\\begin\{cases\}\\dfrac\{1\-\\beta^\{t\}\}\{T\},&1\\leq t<T,\\\\ \\dfrac\{1\-\\beta^\{T\}\}\{\(1\-\\beta\)T\},&t=T\.\\end\{cases\}\(9\)

##### Conversion guarantee\.

The discounted O2NC framework transforms a discounted\-regret bound of an online learner into a guarantee for\(ρ,ε\)\(\\rho,\\varepsilon\)\-stationarity in[Definition2\.2](https://arxiv.org/html/2608.26288#S2.Thmtheorem2)\. For a fixed terminal timett, define the discounted regret of an online learner run over the feasible set\{X∈ℝm×n:∥X∥op≤D\}\\\{X\\in\\mathbb\{R\}^\{m\\times n\}\\colon\\lVert X\\rVert\_\{\\mathrm\{op\}\}\\leq D\\\}by

Regt\[β\]⁡\(D\)≔max⁡∑s=1t∥X∥op≤D⁡βt−s​⟨Gs,Xs−X⟩\.\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(D\)\\coloneqq\\max\_\{\\lVert X\\rVert\_\{\\mathrm\{op\}\}\\leq D\}\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\\langle G\_\{s\},X\_\{s\}\-X\\rangle\.\(10\)
The following lemma is a corollary of[Jiang et al\. \(2026a, Proposition 25\)](https://arxiv.org/html/2608.26288#bib.bib26), and the proof is given in[AppendixC](https://arxiv.org/html/2608.26288#A3)\.

###### Lemma 3\.1\(Corollary of[Jiang et al\., 2026a](https://arxiv.org/html/2608.26288#bib.bib26), Proposition 25\)\.

Under[Assumption2\.1](https://arxiv.org/html/2608.26288#S2.Thmtheorem1), fixρ\>0\\rho\>0and run[Algorithm2](https://arxiv.org/html/2608.26288#algorithm2)withD=\(1−β\)​ρ/\(4​β\)D=\(1\-\\beta\)\\rho/\(4\\beta\)\. Then

𝔼⁡\[∥∇ℒ​\(W¯τ\)∥∗\[ρ\]\]\\displaystyle\\mathbb\{E\}\\left\[\\lVert\\nabla\\mathcal\{L\}\(\\bar\{W\}\_\{\\tau\}\)\\rVert\_\{\*\}^\{\[\\rho\]\}\\right\]≤4​Δℒ\(1−β\)​ρ​T\+1T​𝔼​\[RegT\[β\]⁡\(1\)\+\(1−β\)​∑t=1T−1Regt\[β\]⁡\(1\)\]\\displaystyle\\leq\\frac\{4\\Delta\_\{\\mathcal\{L\}\}\}\{\(1\-\\beta\)\\rho T\}\+\\frac\{1\}\{T\}\\mathbb\{E\}\\left\[\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{T\}\(1\)\+\(1\-\\beta\)\\sum\_\{t=1\}^\{T\-1\}\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(1\)\\right\]\+\(1−β\+βT\)​r​σ1−β2,\\displaystyle\\qquad\+\\left\(1\-\\beta\+\\frac\{\\beta\}\{T\}\\right\)\\frac\{\\sqrt\{r\}\\,\\sigma\}\{\\sqrt\{1\-\\beta^\{2\}\}\},whereRegt\[β\]⁡\(1\)≔max⁡∑s=1t∥U∥op≤1⁡βt−s​⟨Gs,Xs/D−U⟩\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(1\)\\coloneqq\\max\_\{\\lVert U\\rVert\_\{\\mathrm\{op\}\}\\leq 1\}\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\\langle G\_\{s\},X\_\{s\}/D\-U\\rangleso thatRegt\[β\]⁡\(D\)=D​Regt\[β\]⁡\(1\)\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(D\)=D\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(1\)\.

The only quantities in the bound of[Lemma3\.1](https://arxiv.org/html/2608.26288#S3.Thmtheorem1)that depend on the online learner are the expected discounted regrets𝔼⁡\[Regt\[β\]⁡\(1\)\]\\mathbb\{E\}\[\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(1\)\], which we bound in the subsequent sections\.

##### Exact\-polar Muon as follow\-the\-leader\.

For the gradients\(Gs\)s=1t\(G\_\{s\}\)\_\{s=1\}^\{t\}returned at the O2NC query points, we haveMt=\(1−β\)​βt​∑s=1tβ−s​GsM\_\{t\}=\(1\-\\beta\)\\beta^\{t\}\\sum\_\{s=1\}^\{t\}\\beta^\{\-s\}G\_\{s\}\. Hence, Muon with the exact\-polar computation, in which the Newton–Schulz iteration is replaced by the exact polar factor, can be written as

Xt\+1=−Dpolar\(Mt\)=−Dpolar\(∑s=1tβ−sGs\)∈arg​min∥X∥op≤D∑s=1t⟨β−sGs,X⟩,X\_\{t\+1\}=\-D\\polar\(M\_\{t\}\)=\-D\\polar\\left\(\\sum\_\{s=1\}^\{t\}\\beta^\{\-s\}G\_\{s\}\\right\)\\in\\argmin\_\{\\lVert X\\rVert\_\{\\mathrm\{op\}\}\\leq D\}\\,\\sum\_\{s=1\}^\{t\}\\left\\langle\\beta^\{\-s\}G\_\{s\},X\\right\\rangle,\(11\)where we usedpolar⁡\(c​S\)=polar⁡\(S\)\\polar\(cS\)=\\polar\(S\)forc\>0c\>0, and the inclusion follows by applying[1](https://arxiv.org/html/2608.26288#S2.E1)to−∑s=1tβ−sGs\-\\sum\_\{s=1\}^\{t\}\\beta^\{\-s\}G\_\{s\}\. This implies that the Muon update with the exact\-polar computation is equivalent to the follow\-the\-leader \(FTL\) algorithm over the operator\-norm ball for the loss sequence\(ℓs\[β\]\)s=1t\(\\ell\_\{s\}^\{\[\\beta\]\}\)\_\{s=1\}^\{t\}, as noted by[Jiang et al\. \(2026a, Section 5\.2\)](https://arxiv.org/html/2608.26288#bib.bib26)\.

Since FTL need not achieve sublinear regret, the discounted O2NC framework alone does not provide a general stationarity guarantee for Muon with the exact\-polar update on nonsmooth nonconvex objectives\. This is consistent with the counterexamples of[Parshakova et al\. \(2026\)](https://arxiv.org/html/2608.26288#bib.bib44), who construct nonsmooth convex Lipschitz objectives on which Muon with the exact\-polar update and subgradients evaluated at the current iterate fails to converge\. To obtain convergence guarantees for nonsmooth nonconvex optimization,[Jiang et al\. \(2026a\)](https://arxiv.org/html/2608.26288#bib.bib26)instead replace FTL with online algorithms that enforce stability explicitly\. In contrast,[Section5](https://arxiv.org/html/2608.26288#S5)shows that the finite Newton–Schulz iteration in[Algorithm1](https://arxiv.org/html/2608.26288#algorithm1), though introduced only to approximate the polar factor numerically, achieves sublinear discounted regret with an appropriate normalization and depth\.

## 4Discounted regret for a matrix online learner with a general spectral map

Figure 1:Finite Newton–Schulz smooths the exact polar map\. For a normalized singular valuex∈\[0,1\]x\\in\[0,1\], increasingqqdecreases the gapΔ⁡\(hq\)\\Delta\(h\_\{q\}\)between the Newton–Schulz map and the exact polar map but increases the Lipschitz constantLip⁡\(hq\)=Aq\\Lip\(h\_\{q\}\)=A^\{q\}of the map\. The shaded region isΔ⁡\(h3\)=∫01\(1−h3​\(x\)\)​𝑑x\\Delta\(h\_\{3\}\)=\\int\_\{0\}^\{1\}\(1\-h\_\{3\}\(x\)\)\\,\\mathrm\{d\}x\.The conversion of[Section3](https://arxiv.org/html/2608.26288#S3)reduces nonconvex stationarity to bounding the discounted regret of the online learner over the operator\-norm ball\. This section provides that bound for the learner that maintains momentum and applies a general spectral map to it\. The analysis is based on the gradient\-based prediction algorithm \(GBPA\) framework\([Abernethy et al\., 2014](https://arxiv.org/html/2608.26288#bib.bib1);[Abernethy et al\., 2016](https://arxiv.org/html/2608.26288#bib.bib2)\), in which the learner plays the gradient of a differentiable potential function of the aggregated gradient feedback\. In our setting with the loss functionℓt\[β\]\\ell\_\{t\}^\{\[\\beta\]\}, this aggregate corresponds to the momentumMt−1M\_\{t\-1\}, so the learner playsXt=−D∇Φ~t\(Mt−1\)X\_\{t\}=\-D\\nabla\\widetilde\{\\Phi\}\_\{t\}\(M\_\{t\-1\}\)for some potential functionΦ~t\\widetilde\{\\Phi\}\_\{t\}, and we consider the regret decomposition in terms of the momentum sequence\.[Section5](https://arxiv.org/html/2608.26288#S5)specializes the result to Muon with finite Newton–Schulz in[Algorithm1](https://arxiv.org/html/2608.26288#algorithm1)\.

We consider a spectral maph:\[0,∞\)→\[0,1\]h\\colon\[0,\\infty\)\\to\[0,1\]satisfying the following conditions\.

###### Assumption 4\.1\.

The functionh:\[0,∞\)→\[0,1\]h\\colon\[0,\\infty\)\\to\[0,1\]is continuous, nondecreasing, and satisfies

h⁡\(0\)=0,Lip⁡\(h\)<∞,Δ⁡\(h\)≔∫0∞\(1−h⁡\(u\)\)​𝑑u<∞\.h\(0\)=0,\\qquad\\Lip\(h\)<\\infty,\\qquad\\Delta\(h\)\\coloneqq\\int\_\{0\}^\{\\infty\}\(1\-h\(u\)\)\\,\\mathrm\{d\}u<\\infty\.

Here the approximation errorΔ⁡\(h\)\\Delta\(h\)measures the gap betweenhhand the exact polar map, which sends every positive singular value to one, and a smallerΔ⁡\(h\)\\Delta\(h\)forces a largerLip⁡\(h\)\\Lip\(h\)\. The functionhqh\_\{q\}in[6](https://arxiv.org/html/2608.26288#S2.E6)satisfies[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1), as verified in[Section5\.1](https://arxiv.org/html/2608.26288#S5.SS1), and[Figure1](https://arxiv.org/html/2608.26288#S4.F1)illustrates this tradeoff forh=hqh=h\_\{q\}\.

### 4\.1Online learner and discounted\-regret bound

Using the momentum[4](https://arxiv.org/html/2608.26288#S2.E4)and a normalization scaleCt\>0C\_\{t\}\>0, we consider the online learner that takes the action

Xth≔−D​ℋh​\(Mt−1Ct\),X\_\{t\}^\{h\}\\coloneqq\-D\\mathcal\{H\}\_\{h\}\\left\(\\frac\{M\_\{t\-1\}\}\{C\_\{t\}\}\\right\),\(12\)which satisfies∥Xth∥op≤D\\lVert X\_\{t\}^\{h\}\\rVert\_\{\\mathrm\{op\}\}\\leq Dbecauseh⁡\(⋅\)∈\[0,1\]h\(\\cdot\)\\in\[0,1\]\. Forh=hqh=h\_\{q\}andCt=GopC\_\{t\}=G\_\{\\mathrm\{op\}\}, the action[12](https://arxiv.org/html/2608.26288#S4.E12)is the finite Newton–Schulz update in[7](https://arxiv.org/html/2608.26288#S2.E7)provided that∥Mt∥op≤Gop\\lVert M\_\{t\}\\rVert\_\{\\mathrm\{op\}\}\\leq G\_\{\\mathrm\{op\}\}for alltt\. Replacingℋh​\(⋅\)\\mathcal\{H\}\_\{h\}\(\\cdot\)withpolar⁡\(⋅\)\\polar\(\\cdot\)recovers Muon with the exact\-polar computation, which corresponds to the update[11](https://arxiv.org/html/2608.26288#S3.E11)\. The potential corresponding to exact\-polar Muon is the base potentialΦ⁡\(M\)≔∥M∥∗\\Phi\(M\)\\coloneqq\\lVert M\\rVert\_\{\*\}, one of whose subgradients is the exact polar factor\. The update[12](https://arxiv.org/html/2608.26288#S4.E12)replaces this base potentialΦ\\Phiby the smoothed potential given by

Φ~h,C​\(M\)≔C​∑i=1rϕh​\(σi​\(M\)C\)forϕh​\(x\)≔∫0xh⁡\(u\)​𝑑u\.\\widetilde\{\\Phi\}\_\{h,C\}\(M\)\\coloneqq C\\sum\_\{i=1\}^\{r\}\\phi\_\{h\}\\left\(\\frac\{\\sigma\_\{i\}\(M\)\}\{C\}\\right\)\\qquad\\text\{for\}\\quad\\phi\_\{h\}\(x\)\\coloneqq\\int\_\{0\}^\{x\}h\(u\)\\,\\mathrm\{d\}u\.\(13\)
The regret bound under the update[12](https://arxiv.org/html/2608.26288#S4.E12)depends onhhthrough two scalar quantities: the Lipschitz constantLip⁡\(h\)\\Lip\(h\)and the approximation errorΔ⁡\(h\)\\Delta\(h\)\.

###### Theorem 4\.2\.

Suppose[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1)holds\. For anyt≥1t\\geq 1, let\(Cs\)s=1t\(C\_\{s\}\)\_\{s=1\}^\{t\}be positive reals satisfyingCs\+1≥β​CsC\_\{s\+1\}\\geq\\beta C\_\{s\}fors∈\[t−1\]s\\in\[t\-1\]\. Then the online learner[12](https://arxiv.org/html/2608.26288#S4.E12)achieves

Regt\[β\]\(D\)≤D\(r​Ct​Δ​\(h\)1−β\+11−β∑s=1tβt−sBΦ~h,Cs\(Ms∥Ms−1\)\)\.\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(D\)\\leq D\\left\(\\frac\{rC\_\{t\}\\Delta\(h\)\}\{1\-\\beta\}\+\\frac\{1\}\{1\-\\beta\}\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}B\_\{\\widetilde\{\\Phi\}\_\{h,C\_\{s\}\}\}\(M\_\{s\}\\\|M\_\{s\-1\}\)\\right\)\.\(14\)If, in addition,[Assumption2\.1](https://arxiv.org/html/2608.26288#S2.Thmtheorem1)holds andCs=CC\_\{s\}=Cfor alls∈\[t\]s\\in\[t\], then

𝔼⁡\[Regt\[β\]⁡\(D\)\]≤D⁡\(r​C​Δ​\(h\)1−β\+2​Γ2​Lip⁡\(h\)C\)\.\\mathbb\{E\}\[\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(D\)\]\\leq D\\left\(\\frac\{rC\\Delta\(h\)\}\{1\-\\beta\}\+\\frac\{2\\Gamma^\{2\}\\Lip\(h\)\}\{C\}\\right\)\.\(15\)

The coarser bound[15](https://arxiv.org/html/2608.26288#S4.E15)is sufficient for the guarantee for nonsmooth nonconvex objectives in[Theorem5\.3](https://arxiv.org/html/2608.26288#S5.Thmtheorem3), while the guarantee for smooth objectives in[Theorem5\.6](https://arxiv.org/html/2608.26288#S5.Thmtheorem6)relies on the bound depending on the Bregman divergence[14](https://arxiv.org/html/2608.26288#S4.E14)to obtain its optimalO⁡\(1/ε2\)O\(1/\\varepsilon^\{2\}\)dependence in the deterministic case\. Notably, the bound[15](https://arxiv.org/html/2608.26288#S4.E15)has the same structure as the well\-known penalty–stability tradeoff in the analysis of FTRL and online mirror descent\([Shalev\-Shwartz, 2012](https://arxiv.org/html/2608.26288#bib.bib50);[McMahan, 2017](https://arxiv.org/html/2608.26288#bib.bib42);[Zimmert and Seldin, 2021](https://arxiv.org/html/2608.26288#bib.bib59);[Tsuchiya et al\., 2023](https://arxiv.org/html/2608.26288#bib.bib54),e\.g\.,\), with a penalty term proportional toΔ⁡\(h\)\\Delta\(h\)and a stability term proportional toLip⁡\(h\)\\Lip\(h\)\.

### 4\.2Proof of[Theorem4\.2](https://arxiv.org/html/2608.26288#S4.Thmtheorem2)

Here we provide the proof of[Theorem4\.2](https://arxiv.org/html/2608.26288#S4.Thmtheorem2)\.

#### 4\.2\.1The representation as a gradient\-based prediction algorithm \(GBPA\)

The action[12](https://arxiv.org/html/2608.26288#S4.E12)normalizes the momentumMt−1M\_\{t\-1\}by the scaleCtC\_\{t\}\. We first show that it is a GBPA updateXt=−D∇Φ~t\(Mt−1\)X\_\{t\}=\-D\\nabla\\widetilde\{\\Phi\}\_\{t\}\(M\_\{t\-1\}\)for the smoothed potentialΦ~t=Φ~h,Ct\\widetilde\{\\Phi\}\_\{t\}=\\widetilde\{\\Phi\}\_\{h,C\_\{t\}\}of[13](https://arxiv.org/html/2608.26288#S4.E13)\. The following lemma gives its gradient\.

###### Lemma 4\.3\.

Under[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1), for everyC\>0C\>0the functionΦ~h,C\\widetilde\{\\Phi\}\_\{h,C\}is convex and continuously differentiable on all ofℝm×n\\mathbb\{R\}^\{m\\times n\}, and its gradient is

∇Φ~h,C​\(M\)=ℋh​\(M/C\)\.\\nabla\\widetilde\{\\Phi\}\_\{h,C\}\(M\)=\\mathcal\{H\}\_\{h\}\(M/C\)\.\(16\)

###### Proof\.

WriteΦ~h,C​\(M\)=∑i=1rϕ⁡\(σi​\(M\)\)\\widetilde\{\\Phi\}\_\{h,C\}\(M\)=\\sum\_\{i=1\}^\{r\}\\phi\(\\sigma\_\{i\}\(M\)\)withϕ⁡\(x\)≔C​ϕh​\(x/C\)\\phi\(x\)\\coloneqq C\\phi\_\{h\}\(x/C\)\. Sincehhis continuous, nonnegative, and nondecreasing withh⁡\(0\)=0h\(0\)=0, the functionϕ\\phiis convex, nondecreasing, and differentiable, and its derivative satisfiesϕ′​\(x\)=h⁡\(x/C\)\\phi^\{\\prime\}\(x\)=h\(x/C\)andϕ′​\(0\)=0\\phi^\{\\prime\}\(0\)=0\. Hence, by the convexity of separable singular\-value functions \([LemmaB\.1](https://arxiv.org/html/2608.26288#A2.Thmtheorem1)\), the functionΦ~h,C\\widetilde\{\\Phi\}\_\{h,C\}is convex onℝm×n\\mathbb\{R\}^\{m\\times n\}, and by the standard singular\-value gradient formula \([LemmaB\.2](https://arxiv.org/html/2608.26288#A2.Thmtheorem2)\), its gradient is∇Φ~h,C\(M\)=Udiag\(h\(σi\(M\)/C\)\)V⊤=ℋh\(M/C\)\\nabla\\widetilde\{\\Phi\}\_\{h,C\}\(M\)=U\\diag\\left\(h\(\\sigma\_\{i\}\(M\)/C\)\\right\)V^\{\\top\}=\\mathcal\{H\}\_\{h\}\(M/C\), which completes the proof\. ∎

By[16](https://arxiv.org/html/2608.26288#S4.E16), the action[12](https://arxiv.org/html/2608.26288#S4.E12)can be written as

Xth=−Dℋh\(Mt−1Ct\)=−D∇Φ~h,Ct\(Mt−1\),X\_\{t\}^\{h\}=\-D\\mathcal\{H\}\_\{h\}\\left\(\\frac\{M\_\{t\-1\}\}\{C\_\{t\}\}\\right\)=\-D\\nabla\\widetilde\{\\Phi\}\_\{h,C\_\{t\}\}\(M\_\{t\-1\}\),\(17\)which is the GBPA update with the time\-varying potentialΦ~t=Φ~h,Ct\\widetilde\{\\Phi\}\_\{t\}=\\widetilde\{\\Phi\}\_\{h,C\_\{t\}\}evaluated at the momentumMt−1M\_\{t\-1\}\. A GBPA also has a dual description: with a convex potential, it is follow\-the\-regularized\-leader \(FTRL\) with the regularizer given by the Fenchel conjugate of the potential\([Abernethy et al\., 2014](https://arxiv.org/html/2608.26288#bib.bib1)\), and[Section5\.4](https://arxiv.org/html/2608.26288#S5.SS4)develops this correspondence for the spectral potentialsΦ~h,C\\widetilde\{\\Phi\}\_\{h,C\}\.

#### 4\.2\.2Regret decomposition based on momentum for GBPA

We now derive the discounted\-regret bound of the GBPA update[17](https://arxiv.org/html/2608.26288#S4.E17)\. Unlike the standard GBPA decomposition in terms of the cumulative gradients\([Abernethy et al\., 2014](https://arxiv.org/html/2608.26288#bib.bib1);[Abernethy et al\., 2016](https://arxiv.org/html/2608.26288#bib.bib2)\), employed by[Jiang et al\. \(2026a\)](https://arxiv.org/html/2608.26288#bib.bib26), the following lemma decomposes the discounted regret directly in terms of the momentum sequence\.

###### Lemma 4\.4\.

Under[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1), the discounted regret for the online learner[17](https://arxiv.org/html/2608.26288#S4.E17)is decomposed as

Regt\[β\]⁡\(D\)=\\displaystyle\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(D\)=D1−β\(Φ\(Mt\)−Φ~h,Ct\(Mt\)\+∑s=1tβt−sBΦ~h,Cs\(Ms∥Ms−1\)\+∑s=1t−1βt−s−1Vs\),\\displaystyle\\frac\{D\}\{1\-\\beta\}\\biggl\(\\Phi\(M\_\{t\}\)\-\\widetilde\{\\Phi\}\_\{h,C\_\{t\}\}\(M\_\{t\}\)\+\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}B\_\{\\widetilde\{\\Phi\}\_\{h,C\_\{s\}\}\}\(M\_\{s\}\\\|M\_\{s\-1\}\)\+\\sum\_\{s=1\}^\{t\-1\}\\beta^\{t\-s\-1\}V\_\{s\}\\biggr\),\(18\)whereVs≔Φ~h,Cs\+1​\(Ms\)−β​Φ~h,Cs​\(Ms\)−\(1−β\)​⟨Ms,ℋh​\(Ms/Cs\+1\)⟩V\_\{s\}\\coloneqq\\widetilde\{\\Phi\}\_\{h,C\_\{s\+1\}\}\(M\_\{s\}\)\-\\beta\\widetilde\{\\Phi\}\_\{h,C\_\{s\}\}\(M\_\{s\}\)\-\(1\-\\beta\)\\langle M\_\{s\},\\mathcal\{H\}\_\{h\}\(M\_\{s\}/C\_\{s\+1\}\)\\rangle\.

On the right\-hand side of[18](https://arxiv.org/html/2608.26288#S4.E18), the first term is a penalty term, the gap between the base potentialΦ\\Phiand the smoothed potentialΦ~h,Ct\\widetilde\{\\Phi\}\_\{h,C\_\{t\}\}, the second term is a stability term, the accumulated Bregman divergences along the momentum trajectory, and the last term is the variation of the potentials across rounds\. We show that the penalty term is controlled by the approximation errorΔ⁡\(h\)\\Delta\(h\), the stability term by the Lipschitz constantLip⁡\(h\)\\Lip\(h\), and the third term is nonpositive under the scale conditionCs\+1≥β​CsC\_\{s\+1\}\\geq\\beta C\_\{s\}\.

###### Proof\.

By the definition of the discounted regret in[10](https://arxiv.org/html/2608.26288#S3.E10)andMt=\(1−β\)​∑s=1tβt−s​GsM\_\{t\}=\(1\-\\beta\)\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}G\_\{s\}, we have

Regt\[β\]⁡\(D\)\\displaystyle\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(D\)=∑s=1tβt−s​⟨Gs,Xs⟩\+max∥X∥op≤D⁡⟨−Mt1−β,X⟩=∑s=1tβt−s​⟨Gs,Xs⟩\+D1−β​∥Mt∥∗,\\displaystyle=\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\\langle G\_\{s\},X\_\{s\}\\rangle\+\\max\_\{\\lVert X\\rVert\_\{\\mathrm\{op\}\}\\leq D\}\\left\\langle\-\\frac\{M\_\{t\}\}\{1\-\\beta\},X\\right\\rangle=\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\\langle G\_\{s\},X\_\{s\}\\rangle\+\\frac\{D\}\{1\-\\beta\}\\lVert M\_\{t\}\\rVert\_\{\*\},where we used the fact that the maximum in the operator–nuclear duality[1](https://arxiv.org/html/2608.26288#S2.E1)is attained atX=−D​polar⁡\(Mt\)X=\-D\\polar\(M\_\{t\}\)\. Substituting the actions[17](https://arxiv.org/html/2608.26288#S4.E17)into the last equality and multiplying by1−β1\-\\betagives

\(1−β\)Regt\[β\]\(D\)=−D∑s=1t\(1−β\)βt−s⟨Gs,∇Φ~h,Cs\(Ms−1\)⟩\+D∥Mt∥∗\.\(1\-\\beta\)\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(D\)=\-D\\sum\_\{s=1\}^\{t\}\(1\-\\beta\)\\beta^\{t\-s\}\\langle G\_\{s\},\\nabla\\widetilde\{\\Phi\}\_\{h,C\_\{s\}\}\(M\_\{s\-1\}\)\\rangle\+D\\lVert M\_\{t\}\\rVert\_\{\*\}\.\(19\)
We evaluate the first term in[19](https://arxiv.org/html/2608.26288#S4.E19)\. By using\(1−β\)​Gs=Ms−Ms−1\+\(1−β\)​Ms−1\(1\-\\beta\)G\_\{s\}=M\_\{s\}\-M\_\{s\-1\}\+\(1\-\\beta\)M\_\{s\-1\}and the definition of the Bregman divergence, we have

\(1−β\)​⟨Gs,∇Φ~h,Cs​\(Ms−1\)⟩\\displaystyle\(1\-\\beta\)\\langle G\_\{s\},\\nabla\\widetilde\{\\Phi\}\_\{h,C\_\{s\}\}\(M\_\{s\-1\}\)\\rangle=⟨Ms−Ms−1,∇Φ~h,Cs​\(Ms−1\)⟩\+\(1−β\)​⟨Ms−1,∇Φ~h,Cs​\(Ms−1\)⟩\\displaystyle=\\langle M\_\{s\}\-M\_\{s\-1\},\\nabla\\widetilde\{\\Phi\}\_\{h,C\_\{s\}\}\(M\_\{s\-1\}\)\\rangle\+\(1\-\\beta\)\\langle M\_\{s\-1\},\\nabla\\widetilde\{\\Phi\}\_\{h,C\_\{s\}\}\(M\_\{s\-1\}\)\\rangle=Φ~h,Cs\(Ms\)−Φ~h,Cs\(Ms−1\)−BΦ~h,Cs\(Ms∥Ms−1\)\+\(1−β\)⟨Ms−1,∇Φ~h,Cs\(Ms−1\)⟩\.\\displaystyle=\\widetilde\{\\Phi\}\_\{h,C\_\{s\}\}\(M\_\{s\}\)\-\\widetilde\{\\Phi\}\_\{h,C\_\{s\}\}\(M\_\{s\-1\}\)\-B\_\{\\widetilde\{\\Phi\}\_\{h,C\_\{s\}\}\}\(M\_\{s\}\\\|M\_\{s\-1\}\)\+\(1\-\\beta\)\\langle M\_\{s\-1\},\\nabla\\widetilde\{\\Phi\}\_\{h,C\_\{s\}\}\(M\_\{s\-1\}\)\\rangle\.\(20\)Now, byM0=0M\_\{0\}=0andΦ~h,C1​\(0\)=0\\widetilde\{\\Phi\}\_\{h,C\_\{1\}\}\(0\)=0, we have

∑s=1tβt−s​\(Φ~h,Cs​\(Ms\)−Φ~h,Cs​\(Ms−1\)\)=Φ~h,Ct​\(Mt\)\+∑s=1t−1βt−s−1​\(β​Φ~h,Cs​\(Ms\)−Φ~h,Cs\+1​\(Ms\)\)\.\\\!\\\!\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\\left\(\\widetilde\{\\Phi\}\_\{h,C\_\{s\}\}\(M\_\{s\}\)\-\\widetilde\{\\Phi\}\_\{h,C\_\{s\}\}\(M\_\{s\-1\}\)\\right\)=\\widetilde\{\\Phi\}\_\{h,C\_\{t\}\}\(M\_\{t\}\)\+\\sum\_\{s=1\}^\{t\-1\}\\beta^\{t\-s\-1\}\\left\(\\beta\\widetilde\{\\Phi\}\_\{h,C\_\{s\}\}\(M\_\{s\}\)\-\\widetilde\{\\Phi\}\_\{h,C\_\{s\+1\}\}\(M\_\{s\}\)\\right\)\.\(21\)We also have

∑s=1tβt−s​⟨Ms−1,∇Φ~h,Cs​\(Ms−1\)⟩=∑s=1t−1βt−s−1​⟨Ms,∇Φ~h,Cs\+1​\(Ms\)⟩,\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\\langle M\_\{s\-1\},\\nabla\\widetilde\{\\Phi\}\_\{h,C\_\{s\}\}\(M\_\{s\-1\}\)\\rangle=\\sum\_\{s=1\}^\{t\-1\}\\beta^\{t\-s\-1\}\\langle M\_\{s\},\\nabla\\widetilde\{\\Phi\}\_\{h,C\_\{s\+1\}\}\(M\_\{s\}\)\\rangle,\(22\)where we usedM0=0M\_\{0\}=0\. Substituting[20](https://arxiv.org/html/2608.26288#S4.E20),[21](https://arxiv.org/html/2608.26288#S4.E21)and[22](https://arxiv.org/html/2608.26288#S4.E22)into the right\-hand side of[19](https://arxiv.org/html/2608.26288#S4.E19)and dividing by1−β1\-\\betacompletes the proof\. ∎

#### 4\.2\.3Bounding the three terms

The following lemma bounds the penalty term\.

###### Lemma 4\.5\.

Under[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1), for everyM∈ℝm×nM\\in\\mathbb\{R\}^\{m\\times n\}andC\>0C\>0,

0≤Φ⁡\(M\)−Φ~h,C​\(M\)≤r​C​Δ​\(h\)\.0\\leq\\Phi\(M\)\-\\widetilde\{\\Phi\}\_\{h,C\}\(M\)\\leq rC\\Delta\(h\)\.

###### Proof\.

By[13](https://arxiv.org/html/2608.26288#S4.E13)and the definition ofΔ⁡\(h\)\\Delta\(h\)in[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1),

Φ⁡\(M\)−Φ~h,C​\(M\)=C​∑i=1r\(σi​\(M\)C−ϕh​\(σi​\(M\)C\)\)=C​∑i=1r∫0σi​\(M\)/C\(1−h⁡\(u\)\)​𝑑u≤r​C​Δ​\(h\)\.\\Phi\(M\)\-\\widetilde\{\\Phi\}\_\{h,C\}\(M\)=C\\sum\_\{i=1\}^\{r\}\\left\(\\frac\{\\sigma\_\{i\}\(M\)\}\{C\}\-\\phi\_\{h\}\\left\(\\frac\{\\sigma\_\{i\}\(M\)\}\{C\}\\right\)\\right\)=C\\sum\_\{i=1\}^\{r\}\\int\_\{0\}^\{\\sigma\_\{i\}\(M\)/C\}\(1\-h\(u\)\)\\,\\mathrm\{d\}u\\leq rC\\Delta\(h\)\.This completes the proof\. ∎

The stability term is controlled by the following smoothness estimate for the potential\.

###### Lemma 4\.6\.

Under[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1), for everyC\>0C\>0the gradient ofΦ~h,C\\widetilde\{\\Phi\}\_\{h,C\}is\(Lip⁡\(h\)/C\)\(\\Lip\(h\)/C\)\-Lipschitz in the Frobenius norm\. Consequently,

BΦ~h,C\(M′∥M\)≤Lip⁡\(h\)2​C∥M′−M∥F2\.B\_\{\\widetilde\{\\Phi\}\_\{h,C\}\}\(M^\{\\prime\}\\\|M\)\\leq\\frac\{\\Lip\(h\)\}\{2C\}\\lVert M^\{\\prime\}\-M\\rVert\_\{\\mathrm\{F\}\}^\{2\}\.

###### Proof\.

By the Lipschitzness of singular\-value maps \([LemmaB\.4](https://arxiv.org/html/2608.26288#A2.Thmtheorem4)\) applied tohhsatisfying[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1), for anyM,M′∈ℝm×nM,M^\{\\prime\}\\in\\mathbb\{R\}^\{m\\times n\},

∥ℋh​\(M/C\)−ℋh​\(M′/C\)∥F≤Lip⁡\(h\)C​∥M−M′∥F,\\lVert\\mathcal\{H\}\_\{h\}\(M/C\)\-\\mathcal\{H\}\_\{h\}\(M^\{\\prime\}/C\)\\rVert\_\{\\mathrm\{F\}\}\\leq\\frac\{\\Lip\(h\)\}\{C\}\\lVert M\-M^\{\\prime\}\\rVert\_\{\\mathrm\{F\}\},\(23\)and thus∇Φ~h,C=ℋh\(⋅/C\)\\nabla\\widetilde\{\\Phi\}\_\{h,C\}=\\mathcal\{H\}\_\{h\}\(\\cdot/C\)is\(Lip⁡\(h\)/C\)\(\\Lip\(h\)/C\)\-Lipschitz\. By applying the fundamental theorem of calculus tou↦Φ~h,C​\(M\+u⁡\(M′−M\)\)u\\mapsto\\widetilde\{\\Phi\}\_\{h,C\}\(M\+u\(M^\{\\prime\}\-M\)\)on\[0,1\]\[0,1\]and then using the Cauchy–Schwarz inequality and[Equation23](https://arxiv.org/html/2608.26288#S4.E23), for anyM,M′∈ℝm×nM,M^\{\\prime\}\\in\\mathbb\{R\}^\{m\\times n\}we have

BΦ~h,C\(M′∥M\)\\displaystyle B\_\{\\widetilde\{\\Phi\}\_\{h,C\}\}\(M^\{\\prime\}\\\|M\)=∫01⟨∇Φ~h,C​\(M\+u⁡\(M′−M\)\)−∇Φ~h,C​\(M\),M′−M⟩​𝑑u\\displaystyle=\\int\_\{0\}^\{1\}\\left\\langle\\nabla\\widetilde\{\\Phi\}\_\{h,C\}\(M\+u\(M^\{\\prime\}\-M\)\)\-\\nabla\\widetilde\{\\Phi\}\_\{h,C\}\(M\),\\,M^\{\\prime\}\-M\\right\\rangle\\,\\mathrm\{d\}u≤∫01‖∇Φ~h,C​\(M\+u⁡\(M′−M\)\)−∇Φ~h,C​\(M\)‖F​‖M′−M‖F​𝑑u≤Lip⁡\(h\)2​C​‖M′−M‖F2,\\displaystyle\\leq\\int\_\{0\}^\{1\}\\\|\\nabla\\widetilde\{\\Phi\}\_\{h,C\}\(M\+u\(M^\{\\prime\}\-M\)\)\-\\nabla\\widetilde\{\\Phi\}\_\{h,C\}\(M\)\\\|\_\{\\mathrm\{F\}\}\\\|M^\{\\prime\}\-M\\\|\_\{\\mathrm\{F\}\}\\,\\mathrm\{d\}u\\leq\\frac\{\\Lip\(h\)\}\{2C\}\\\|M^\{\\prime\}\-M\\\|\_\{\\mathrm\{F\}\}^\{2\},which completes the proof\. ∎

Finally, the last term in[18](https://arxiv.org/html/2608.26288#S4.E18)is nonpositive under the scale condition due to the convexity ofϕh\\phi\_\{h\}andϕh​\(0\)=0\\phi\_\{h\}\(0\)=0\.

###### Lemma 4\.7\.

Let0<β<10<\\beta<1andC,C′\>0C,C^\{\\prime\}\>0withC′≥β​CC^\{\\prime\}\\geq\\beta C\. Under[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1), for everyM∈ℝm×nM\\in\\mathbb\{R\}^\{m\\times n\},

Φ~h,C′​\(M\)−β​Φ~h,C​\(M\)−\(1−β\)​⟨M,∇Φ~h,C′​\(M\)⟩≤0\.\\widetilde\{\\Phi\}\_\{h,C^\{\\prime\}\}\(M\)\-\\beta\\widetilde\{\\Phi\}\_\{h,C\}\(M\)\-\(1\-\\beta\)\\langle M,\\nabla\\widetilde\{\\Phi\}\_\{h,C^\{\\prime\}\}\(M\)\\rangle\\leq 0\.Consequently,Vs≤0V\_\{s\}\\leq 0wheneverCs\+1≥β​CsC\_\{s\+1\}\\geq\\beta C\_\{s\}\.

###### Proof\.

The left\-hand side of the desired inequality decomposes over the singular values ofMM, so it suffices to show, for each singular valueλ\\lambdaofMM, that

C′​ϕh​\(λ/C′\)−β​C​ϕh​\(λ/C\)−\(1−β\)​λ​h​\(λ/C′\)≤0\.C^\{\\prime\}\\phi\_\{h\}\(\\lambda/C^\{\\prime\}\)\-\\beta C\\phi\_\{h\}\(\\lambda/C\)\-\(1\-\\beta\)\\lambda\\,h\(\\lambda/C^\{\\prime\}\)\\leq 0\.Writex≔λ/C′x\\coloneqq\\lambda/C^\{\\prime\}andθ≔β​C/C′∈\(0,1\]\\theta\\coloneqq\\beta C/C^\{\\prime\}\\in\(0,1\], so thatλ/C=β​x/θ\\lambda/C=\\beta x/\\theta\. Then, dividing the above inequality byC′C^\{\\prime\}, we can see that it suffices to show that

F⁡\(θ\)≔ϕh​\(x\)−θ​ϕh​\(β​x/θ\)−\(1−β\)​x​h​\(x\)≤0\.F\(\\theta\)\\coloneqq\\phi\_\{h\}\(x\)\-\\theta\\phi\_\{h\}\(\\beta x/\\theta\)\-\(1\-\\beta\)xh\(x\)\\leq 0\.This directly follows from the convexity ofϕh\\phi\_\{h\}andϕh​\(0\)=0\\phi\_\{h\}\(0\)=0\. Indeed, these two properties implyϕh​\(β​x\)=ϕh​\(θ⋅\(β​x/θ\)\+\(1−θ\)​0\)≤θ​ϕh​\(β​x/θ\)\\phi\_\{h\}\(\\beta x\)=\\phi\_\{h\}\(\\theta\\cdot\(\\beta x/\\theta\)\+\(1\-\\theta\)0\)\\leq\\theta\\phi\_\{h\}\(\\beta x/\\theta\)\. Again by the convexity ofϕh\\phi\_\{h\}andϕh′=h\\phi\_\{h\}^\{\\prime\}=h, we haveϕh​\(β​x\)≥ϕh​\(x\)\+\(β​x−x\)​ϕh′​\(x\)=ϕh​\(x\)\+\(β​x−x\)​h​\(x\)\\phi\_\{h\}\(\\beta x\)\\geq\\phi\_\{h\}\(x\)\+\(\\beta x\-x\)\\phi\_\{h\}^\{\\prime\}\(x\)=\\phi\_\{h\}\(x\)\+\(\\beta x\-x\)h\(x\)\. Combining these two inequalities, we obtain

F⁡\(θ\)=ϕh​\(x\)−θ​ϕh​\(β​x/θ\)−\(1−β\)​x​h​\(x\)≤ϕh​\(x\)−ϕh​\(β​x\)−\(1−β\)​x​h​\(x\)≤0,F\(\\theta\)=\\phi\_\{h\}\(x\)\-\\theta\\phi\_\{h\}\(\\beta x/\\theta\)\-\(1\-\\beta\)xh\(x\)\\leq\\phi\_\{h\}\(x\)\-\\phi\_\{h\}\(\\beta x\)\-\(1\-\\beta\)xh\(x\)\\leq 0,which completes the proof\. ∎

We are now ready to prove[Theorem4\.2](https://arxiv.org/html/2608.26288#S4.Thmtheorem2)\.

###### Proof of[Theorem4\.2](https://arxiv.org/html/2608.26288#S4.Thmtheorem2)\.

We upper bound the right\-hand side of[18](https://arxiv.org/html/2608.26288#S4.E18)in[Lemma4\.4](https://arxiv.org/html/2608.26288#S4.Thmtheorem4)\. Since the first term of[18](https://arxiv.org/html/2608.26288#S4.E18)is at mostD​r​Ct​Δ​\(h\)/\(1−β\)DrC\_\{t\}\\Delta\(h\)/\(1\-\\beta\)by[Lemma4\.5](https://arxiv.org/html/2608.26288#S4.Thmtheorem5)andVs≤0V\_\{s\}\\leq 0by[Lemma4\.7](https://arxiv.org/html/2608.26288#S4.Thmtheorem7), we obtain[14](https://arxiv.org/html/2608.26288#S4.E14)\. For the second claim, letCs=CC\_\{s\}=Cfor alls∈\[t\]s\\in\[t\]and take expectations under[Assumption2\.1](https://arxiv.org/html/2608.26288#S2.Thmtheorem1)\. Bounding each Bregman divergence in[14](https://arxiv.org/html/2608.26288#S4.E14)by[Lemma4\.6](https://arxiv.org/html/2608.26288#S4.Thmtheorem6), we have

𝔼\[∑s=1tβt−sBΦ~h,Cs\(Ms∥Ms−1\)\]≤Lip⁡\(h\)2​C𝔼\[∑s=1tβt−s∥Ms−Ms−1∥F2\]≤2​\(1−β\)​Γ2​Lip⁡\(h\)C\.\\mathbb\{E\}\\left\[\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}B\_\{\\widetilde\{\\Phi\}\_\{h,C\_\{s\}\}\}\(M\_\{s\}\\\|M\_\{s\-1\}\)\\right\]\\leq\\frac\{\\Lip\(h\)\}\{2C\}\\,\\mathbb\{E\}\\left\[\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\\lVert M\_\{s\}\-M\_\{s\-1\}\\rVert\_\{\\mathrm\{F\}\}^\{2\}\\right\]\\leq\\frac\{2\(1\-\\beta\)\\Gamma^\{2\}\\Lip\(h\)\}\{C\}\.Here, the last inequality follows fromMs−Ms−1=\(1−β\)​\(Gs−Ms−1\)M\_\{s\}\-M\_\{s\-1\}=\(1\-\\beta\)\(G\_\{s\}\-M\_\{s\-1\}\), the bound𝔼⁡\[∥Gs−Ms−1∥F2\]≤4​Γ2\\mathbb\{E\}\[\\lVert G\_\{s\}\-M\_\{s\-1\}\\rVert\_\{\\mathrm\{F\}\}^\{2\}\]\\leq 4\\Gamma^\{2\}, which follows from[Assumption2\.1](https://arxiv.org/html/2608.26288#S2.Thmtheorem1)and Jensen’s inequality, and\(1−β\)​∑s=1tβt−s≤1\(1\-\\beta\)\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\\leq 1\. Substituting this bound into[14](https://arxiv.org/html/2608.26288#S4.E14)gives[15](https://arxiv.org/html/2608.26288#S4.E15), which completes the proof\. ∎

## 5Regret and stationarity guarantees for Muon with finite Newton–Schulz

This section specializes the general theory of[Section4](https://arxiv.org/html/2608.26288#S4)to the finite Newton–Schulz map and to[Algorithm1](https://arxiv.org/html/2608.26288#algorithm1)\. The proofs of this section are deferred to[AppendicesD](https://arxiv.org/html/2608.26288#A4)and[E](https://arxiv.org/html/2608.26288#A5)\.

### 5\.1Discounted regret for Muon with finite Newton–Schulz

Recall the functionhqh\_\{q\}from[6](https://arxiv.org/html/2608.26288#S2.E6)and the constantA=15/8A=15/8\. Throughout this section, we use the constant normalizationCt=GopC\_\{t\}=G\_\{\\mathrm\{op\}\}and assume the operator\-norm bound∥Gs∥op≤Gop\\lVert G\_\{s\}\\rVert\_\{\\mathrm\{op\}\}\\leq G\_\{\\mathrm\{op\}\}of[Section2\.2](https://arxiv.org/html/2608.26288#S2.SS2)\. First, we verify thathqh\_\{q\}satisfies[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1)\. By[6](https://arxiv.org/html/2608.26288#S2.E6),hqh\_\{q\}is theqq\-fold composition offfon\[0,1\]\[0,1\], extended by the constant11on\[1,∞\)\[1,\\infty\)\. Sinceffis a polynomial that is nondecreasing on\[0,1\]\[0,1\]withf⁡\(0\)=0f\(0\)=0andf⁡\(1\)=1f\(1\)=1,hq:\[0,∞\)→\[0,1\]h\_\{q\}\\colon\[0,\\infty\)\\to\[0,1\]is continuous and nondecreasing, satisfieshq​\(0\)=0h\_\{q\}\(0\)=0andhq​\(x\)=1h\_\{q\}\(x\)=1forx≥1x\\geq 1, and has a finite Lipschitz constant\.

Since the momentum update[4](https://arxiv.org/html/2608.26288#S2.E4)and the operator\-norm bound∥Gs∥op≤Gop\\lVert G\_\{s\}\\rVert\_\{\\mathrm\{op\}\}\\leq G\_\{\\mathrm\{op\}\}give∥Mt∥op≤\(1−βt\)​Gop≤Gop\\lVert M\_\{t\}\\rVert\_\{\\mathrm\{op\}\}\\leq\(1\-\\beta^\{t\}\)G\_\{\\mathrm\{op\}\}\\leq G\_\{\\mathrm\{op\}\}for everytt, all singular values ofMt/GopM\_\{t\}/G\_\{\\mathrm\{op\}\}lie in\[0,1\]\[0,1\], and the finite Newton–Schulz iteration coincides with the singular\-value mapℋhq​\(Mt/Gop\)\\mathcal\{H\}\_\{h\_\{q\}\}\(M\_\{t\}/G\_\{\\mathrm\{op\}\}\)\. Thus[Algorithm1](https://arxiv.org/html/2608.26288#algorithm1)is exactly the online learner of[12](https://arxiv.org/html/2608.26288#S4.E12)with normalizationCt=GopC\_\{t\}=G\_\{\\mathrm\{op\}\}, which satisfies the scale conditionCt\+1=Gop≥β​CtC\_\{t\+1\}=G\_\{\\mathrm\{op\}\}\\geq\\beta C\_\{t\}and keeps the action feasible,∥Xt\+1∥op≤D\\lVert X\_\{t\+1\}\\rVert\_\{\\mathrm\{op\}\}\\leq D\. Specializing[Theorem4\.2](https://arxiv.org/html/2608.26288#S4.Thmtheorem2)toh=hqh=h\_\{q\}and choosing the depthqqvia our key lemma \([Lemma5\.2](https://arxiv.org/html/2608.26288#S5.Thmtheorem2)below\), we obtain the following discounted\-regret bound\.

###### Theorem 5\.1\.

Suppose[Assumption2\.1](https://arxiv.org/html/2608.26288#S2.Thmtheorem1)holds,Γ\>0\\Gamma\>0, and∥Gs∥op≤Gop\\lVert G\_\{s\}\\rVert\_\{\\mathrm\{op\}\}\\leq G\_\{\\mathrm\{op\}\}almost surely for everyss\. IfGop​r/\(Γ​1−β\)≥1G\_\{\\mathrm\{op\}\}\\sqrt\{r\}/\(\\Gamma\\sqrt\{1\-\\beta\}\)\\geq 1, then for everyt≥1t\\geq 1, the learner of[Algorithm1](https://arxiv.org/html/2608.26288#algorithm1)achieves

𝔼⁡\[Regt\[β\]⁡\(D\)\]≤\(1\+2​A\)​D​Γ​r1−βwith depthq=⌈logA⁡Gop​rΓ​1−β⌉\.\\mathbb\{E\}\[\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(D\)\]\\leq\(1\+2A\)D\\Gamma\\sqrt\{\\frac\{r\}\{1\-\\beta\}\}\\quad\\text\{with depth\}\\quad q=\\left\\lceil\\log\_\{A\}\\frac\{G\_\{\\mathrm\{op\}\}\\sqrt\{r\}\}\{\\Gamma\\sqrt\{1\-\\beta\}\}\\right\\rceil\.\(24\)

The bound of[Theorem5\.1](https://arxiv.org/html/2608.26288#S5.Thmtheorem1)is obtained from[15](https://arxiv.org/html/2608.26288#S4.E15)in[Theorem4\.2](https://arxiv.org/html/2608.26288#S4.Thmtheorem2)withh=hqh=h\_\{q\}, by balancing a penalty term controlled by the approximation errorΔ⁡\(hq\)\\Delta\(h\_\{q\}\)against a stability term controlled by the Lipschitz constantLip⁡\(hq\)\\Lip\(h\_\{q\}\)\. The following lemma shows thatLip⁡\(hq\)\\Lip\(h\_\{q\}\)grows exactly asAqA^\{q\}, whileΔ⁡\(hq\)\\Delta\(h\_\{q\}\)remains within constant factors ofA−qA^\{\-q\}\.

###### Lemma 5\.2\.

For every integerq≥0q\\geq 0, the functionhqh\_\{q\}in[6](https://arxiv.org/html/2608.26288#S2.E6)satisfies

Lip⁡\(hq\)=Aq,12​Aq≤Δ⁡\(hq\)≤1Aq\+1≤1Aq,A=158\.\\Lip\(h\_\{q\}\)=A^\{q\},\\qquad\\frac\{1\}\{2A^\{q\}\}\\leq\\Delta\(h\_\{q\}\)\\leq\\frac\{1\}\{A^\{q\}\+1\}\\leq\\frac\{1\}\{A^\{q\}\},\\qquad A=\\frac\{15\}\{8\}\.\(25\)

###### Proof sketch of[Theorem5\.1](https://arxiv.org/html/2608.26288#S5.Thmtheorem1)\.

SubstitutingLip⁡\(hq\)=Aq\\Lip\(h\_\{q\}\)=A^\{q\}andΔ⁡\(hq\)≤A−q\\Delta\(h\_\{q\}\)\\leq A^\{\-q\}from[Lemma5\.2](https://arxiv.org/html/2608.26288#S5.Thmtheorem2)into[15](https://arxiv.org/html/2608.26288#S4.E15)in[Theorem4\.2](https://arxiv.org/html/2608.26288#S4.Thmtheorem2)withC=GopC=G\_\{\\mathrm\{op\}\}gives

𝔼⁡\[Regt\[β\]⁡\(D\)\]≤D⁡\(r​Gop\(1−β\)​Aq\+2​Aq​Γ2Gop\)\.\\mathbb\{E\}\[\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(D\)\]\\leq D\\left\(\\frac\{rG\_\{\\mathrm\{op\}\}\}\{\(1\-\\beta\)A^\{q\}\}\+\\frac\{2A^\{q\}\\Gamma^\{2\}\}\{G\_\{\\mathrm\{op\}\}\}\\right\)\.Balancing the two terms over the integer depthqqgives[24](https://arxiv.org/html/2608.26288#S5.E24)\. ∎

This tradeoff explains the benefit of a finite Newton–Schulz iteration over exact orthogonalization\. Asq→∞q\\to\\infty,hqh\_\{q\}approaches the exact polar map, and the update approaches the exact polar factor, the ideal Muon update\. In this limit,Δ⁡\(hq\)→0\\Delta\(h\_\{q\}\)\\to 0, butLip⁡\(hq\)→∞\\Lip\(h\_\{q\}\)\\to\\infty, which reflects the discontinuity of the polar map, and the stability term is no longer controlled\.[LemmaD\.1](https://arxiv.org/html/2608.26288#A4.Thmtheorem1)shows that the same tradeoff holds at any finite Taylor order and that our analysis therefore extends beyond the degree\-five Newton–Schulz polynomial investigated here\. Moreover, the same penalty–stability tradeoff is unavoidable for general spectral maps, as everyhhsatisfying[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1)obeysΔ⁡\(h\)≥1/\(2​Lip⁡\(h\)\)\\Delta\(h\)\\geq 1/\\left\(2\\Lip\(h\)\\right\)\. By[Lemma5\.2](https://arxiv.org/html/2608.26288#S5.Thmtheorem2), the finite Newton–Schulz map satisfiesΔ⁡\(hq\)≤1/Lip⁡\(hq\)\\Delta\(h\_\{q\}\)\\leq 1/\\Lip\(h\_\{q\}\)and hence attains this lower bound up to a factor of two\.[AppendixF](https://arxiv.org/html/2608.26288#A6)proves this lower bound and instantiates our guarantees for a recently proposed smooth relaxation of the polar map\([Mustafi et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib43);[Feoktistov et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib21)\)\.[AppendixG](https://arxiv.org/html/2608.26288#A7)illustrates this depth tradeoff numerically on a synthetic nonsmooth objective\.

### 5\.2Sample complexity in nonsmooth nonconvex optimization

Substituting the discounted\-regret bound in[Theorem5\.1](https://arxiv.org/html/2608.26288#S5.Thmtheorem1)into the online\-to\-nonconvex conversion framework of[Lemma3\.1](https://arxiv.org/html/2608.26288#S3.Thmtheorem1), we can obtain the following stationarity guarantee for nonsmooth nonconvex optimization\.

###### Theorem 5\.3\.

Suppose[Assumption2\.1](https://arxiv.org/html/2608.26288#S2.Thmtheorem1)holds,Γ\>0\\Gamma\>0, and∥Gs∥op≤Gop\\lVert G\_\{s\}\\rVert\_\{\\mathrm\{op\}\}\\leq G\_\{\\mathrm\{op\}\}almost surely for everyss, fixρ\>0\\rho\>0andε\>0\\varepsilon\>0, and letBNS≔r​\(\(1\+2​A\)​Γ\+σ\)B\_\{\\mathrm\{NS\}\}\\coloneqq\\sqrt\{r\}\(\(1\+2A\)\\Gamma\+\\sigma\)\. Running[Algorithm2](https://arxiv.org/html/2608.26288#algorithm2)using[Algorithm1](https://arxiv.org/html/2608.26288#algorithm1)as its online learner𝒜\\mathcal\{A\}with1−β=min⁡\{1/9,\(ε/3​BNS\)2\}1\-\\beta=\\min\\\{1/9,\(\\varepsilon/3B\_\{\\mathrm\{NS\}\}\)^\{2\}\\\},D=\(1−β\)​ρ/\(4​β\)D=\(1\-\\beta\)\\rho/\(4\\beta\), and depthq=⌈logA⁡max⁡\{1,3​BNS​Gop​r/\(Γ​ε\)\}⌉q=\\left\\lceil\\log\_\{A\}\\max\\left\\\{1,\\ 3B\_\{\\mathrm\{NS\}\}G\_\{\\mathrm\{op\}\}\\sqrt\{r\}/\(\\Gamma\\varepsilon\)\\right\\\}\\right\\rceilgives

𝔼⁡\[∥∇ℒ​\(W¯τ\)∥∗\[ρ\]\]≤ε3\+O⁡\(Δℒ​r​\(Γ\+σ\)2ρ​ε2​T\+r​\(Γ\+σ\)2ε​T\),\\mathbb\{E\}\\left\[\\lVert\\nabla\\mathcal\{L\}\(\\bar\{W\}\_\{\\tau\}\)\\rVert\_\{\*\}^\{\[\\rho\]\}\\right\]\\leq\\frac\{\\varepsilon\}\{3\}\+O\\left\(\\frac\{\\Delta\_\{\\mathcal\{L\}\}\\,r\(\\Gamma\+\\sigma\)^\{2\}\}\{\\rho\\varepsilon^\{2\}T\}\+\\frac\{r\(\\Gamma\+\\sigma\)^\{2\}\}\{\\varepsilon T\}\\right\),\(26\)soW¯τ\\bar\{W\}\_\{\\tau\}is a\(ρ,ε\)\(\\rho,\\varepsilon\)\-stationary point in expectation with gradient\-oracle complexity

T=O⁡\(max⁡\{Δℒ​r​\(Γ\+σ\)2ρ​ε3,r​\(Γ\+σ\)2ε2\}\)\.T=O\\left\(\\max\\left\\\{\\frac\{\\Delta\_\{\\mathcal\{L\}\}\\,r\(\\Gamma\+\\sigma\)^\{2\}\}\{\\rho\\varepsilon^\{3\}\},\\ \\frac\{r\(\\Gamma\+\\sigma\)^\{2\}\}\{\\varepsilon^\{2\}\}\\right\\\}\\right\)\.\(27\)

The leadingρ−1​ε−3\\rho^\{\-1\}\\varepsilon^\{\-3\}term matches the bounds for Pion and Leon\([Jiang et al\., 2026a](https://arxiv.org/html/2608.26288#bib.bib26)\), and[AppendixA](https://arxiv.org/html/2608.26288#A1)gives a detailed comparison\.

### 5\.3Sample complexity in smooth nonconvex optimization

Using the same discounted O2NC reduction, we also obtain a guarantee for smooth objectives\. In addition to[Assumption2\.1](https://arxiv.org/html/2608.26288#S2.Thmtheorem1)and the operator\-norm bound∥Gs∥op≤Gop\\lVert G\_\{s\}\\rVert\_\{\\mathrm\{op\}\}\\leq G\_\{\\mathrm\{op\}\}of[Section2\.2](https://arxiv.org/html/2608.26288#S2.SS2), throughout this subsection we assume the following smoothness ofℒ\\mathcal\{L\}with respect to the operator norm\.

###### Assumption 5\.4\.

There is a constantLop\>0L\_\{\\mathrm\{op\}\}\>0such that

∥∇ℒ​\(W\)−∇ℒ​\(W′\)∥∗≤Lop​∥W−W′∥opfor all​W,W′∈ℝm×n\.\\lVert\\nabla\\mathcal\{L\}\(W\)\-\\nabla\\mathcal\{L\}\(W^\{\\prime\}\)\\rVert\_\{\*\}\\leq L\_\{\\mathrm\{op\}\}\\lVert W\-W^\{\\prime\}\\rVert\_\{\\mathrm\{op\}\}\\qquad\\text\{for all \}W,W^\{\\prime\}\\in\\mathbb\{R\}^\{m\\times n\}\.\(28\)

For smooth objectives we use the bound[14](https://arxiv.org/html/2608.26288#S4.E14)of[Theorem4\.2](https://arxiv.org/html/2608.26288#S4.Thmtheorem2), stated in terms of the Bregman divergences\. Under[Assumption5\.4](https://arxiv.org/html/2608.26288#S5.Thmtheorem4), and forh=hqh=h\_\{q\}andCs≡GopC\_\{s\}\\equiv G\_\{\\mathrm\{op\}\}, each Bregman divergenceBΦ~hq,Gop\(Ms∥Ms−1\)B\_\{\\widetilde\{\\Phi\}\_\{h\_\{q\},G\_\{\\mathrm\{op\}\}\}\}\(M\_\{s\}\\\|M\_\{s\-1\}\)is bounded more sharply, as shown in[SectionD\.4](https://arxiv.org/html/2608.26288#A4.SS4)\. The resulting bound on∥∇ℒ​\(W\)∥∗\[ρ\]\\lVert\\nabla\\mathcal\{L\}\(W\)\\rVert\_\{\*\}^\{\[\\rho\]\}is converted to a bound on∥∇ℒ​\(W\)∥∗\\lVert\\nabla\\mathcal\{L\}\(W\)\\rVert\_\{\*\}by the following lemma, whose proof is given in[SectionD\.4](https://arxiv.org/html/2608.26288#A4.SS4)\.

###### Lemma 5\.5\.

Under[Assumption5\.4](https://arxiv.org/html/2608.26288#S5.Thmtheorem4), for everyW∈ℝm×nW\\in\\mathbb\{R\}^\{m\\times n\},∥∇ℒ​\(W\)∥∗≤∥∇ℒ​\(W\)∥∗\[ρ\]\+Lop​ρ\\lVert\\nabla\\mathcal\{L\}\(W\)\\rVert\_\{\*\}\\leq\\lVert\\nabla\\mathcal\{L\}\(W\)\\rVert\_\{\*\}^\{\[\\rho\]\}\+L\_\{\\mathrm\{op\}\}\\rho\.

Thus, the discounted O2NC conversion of[Lemma3\.1](https://arxiv.org/html/2608.26288#S3.Thmtheorem1)gives the following sample complexity guarantee\.

###### Theorem 5\.6\.

Suppose[Assumption2\.1](https://arxiv.org/html/2608.26288#S2.Thmtheorem1)and[Assumption5\.4](https://arxiv.org/html/2608.26288#S5.Thmtheorem4)hold,∥Gs∥op≤Gop\\lVert G\_\{s\}\\rVert\_\{\\mathrm\{op\}\}\\leq G\_\{\\mathrm\{op\}\}almost surely for everyss, and fixε\>0\\varepsilon\>0\. Running[Algorithm2](https://arxiv.org/html/2608.26288#algorithm2)using[Algorithm1](https://arxiv.org/html/2608.26288#algorithm1)as its online learner𝒜\\mathcal\{A\}with1−β=min⁡\{1/2,ε2/\(144​r​σ2\)\}1\-\\beta=\\min\\\{1/2,\\varepsilon^\{2\}/\(144r\\sigma^\{2\}\)\\\},D=\(1−β\)​ε/\(48​β​Lop\)D=\(1\-\\beta\)\\varepsilon/\(48\\beta L\_\{\\mathrm\{op\}\}\), and depthq=⌈logA⁡max⁡\{1,12​r​Gop/ε\}⌉q=\\left\\lceil\\log\_\{A\}\\max\\left\\\{1,12rG\_\{\\mathrm\{op\}\}/\\varepsilon\\right\\\}\\right\\rceilgives

𝔼⁡\[∥∇ℒ​\(W¯τ\)∥∗\]≤23​ε\+O⁡\(εT\+Lop​Δℒε​T\+r​σ2ε​T\+r​σ2​Lop​Δℒε3​T\),\\mathbb\{E\}\\left\[\\lVert\\nabla\\mathcal\{L\}\(\\bar\{W\}\_\{\\tau\}\)\\rVert\_\{\*\}\\right\]\\leq\\frac\{2\}\{3\}\\varepsilon\+O\\left\(\\frac\{\\varepsilon\}\{T\}\+\\frac\{L\_\{\\mathrm\{op\}\}\\Delta\_\{\\mathcal\{L\}\}\}\{\\varepsilon T\}\+\\frac\{r\\sigma^\{2\}\}\{\\varepsilon T\}\+\\frac\{r\\sigma^\{2\}L\_\{\\mathrm\{op\}\}\\Delta\_\{\\mathcal\{L\}\}\}\{\\varepsilon^\{3\}T\}\\right\),\(29\)soW¯τ\\bar\{W\}\_\{\\tau\}satisfies𝔼⁡\[∥∇ℒ​\(W¯τ\)∥∗\]≤ε\\mathbb\{E\}\\left\[\\lVert\\nabla\\mathcal\{L\}\(\\bar\{W\}\_\{\\tau\}\)\\rVert\_\{\*\}\\right\]\\leq\\varepsilonwith gradient\-oracle complexity

T=O⁡\(max⁡\{Lop​Δℒε2,r​σ2ε2,r​σ2​Lop​Δℒε4\}\)\.T=O\\left\(\\max\\left\\\{\\frac\{L\_\{\\mathrm\{op\}\}\\Delta\_\{\\mathcal\{L\}\}\}\{\\varepsilon^\{2\}\},\\ \\frac\{r\\sigma^\{2\}\}\{\\varepsilon^\{2\}\},\\ \\frac\{r\\sigma^\{2\}L\_\{\\mathrm\{op\}\}\\Delta\_\{\\mathcal\{L\}\}\}\{\\varepsilon^\{4\}\}\\right\\\}\\right\)\.\(30\)

Theε−2\\varepsilon^\{\-2\}dependence in the deterministic case matches the classical lower bound for smooth nonconvex optimization\([Carmon et al\., 2020](https://arxiv.org/html/2608.26288#bib.bib14)\)\. Under the standard unbiased bounded\-variance stochastic first\-order oracle, theε−4\\varepsilon^\{\-4\}dependence matches the lower bound of[Arjevani et al\. \(2023\)](https://arxiv.org/html/2608.26288#bib.bib8)\. The leading terms coincide with those established for exact\-polar Muon\([Kovalev, 2025](https://arxiv.org/html/2608.26288#bib.bib32);[Shen et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib51)\), as summarized in[AppendixA](https://arxiv.org/html/2608.26288#A1)\. The resulting complexity has the same dependence as that of[Kim and Oh \(2026\)](https://arxiv.org/html/2608.26288#bib.bib29), except that the middle term improves fromr2​σ2/ε2r^\{2\}\\sigma^\{2\}/\\varepsilon^\{2\}tor​σ2/ε2r\\sigma^\{2\}/\\varepsilon^\{2\}, though the algorithms under analysis are slightly different\. As in the analysis for nonsmooth objectives, the proof in[SectionD\.4](https://arxiv.org/html/2608.26288#A4.SS4)choosesqqby balancing theqq\-dependent terms in the regret bound, rather than by bounding the finite\-step approximation error relative to the exact\-polar update\.

### 5\.4Interpretation of Muon with finite Newton–Schulz as FTRL

By Fenchel duality, the online learner[12](https://arxiv.org/html/2608.26288#S4.E12)is follow\-the\-regularized\-leader \(FTRL\) on the discounted linear losses, with a spectral regularizer given by the Fenchel conjugate of the smoothed potential\. Define the Fenchel conjugatesϕh∗​\(a\)≔supx≥0\{a​x−ϕh​\(x\)\}\\phi\_\{h\}^\{\*\}\(a\)\\coloneqq\\sup\_\{x\\geq 0\}\\\{ax\-\\phi\_\{h\}\(x\)\\\}andΦ~h,C∗​\(W\)≔supM∈ℝm×n\{⟨W,M⟩−Φ~h,C​\(M\)\}\\widetilde\{\\Phi\}\_\{h,C\}^\{\*\}\(W\)\\coloneqq\\sup\_\{M\\in\\mathbb\{R\}^\{m\\times n\}\}\\\{\\langle W,M\\rangle\-\\widetilde\{\\Phi\}\_\{h,C\}\(M\)\\\}\.

###### Theorem 5\.7\.

Suppose[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1)holds and let\(Ct\)t≥1\(C\_\{t\}\)\_\{t\\geq 1\}be a positive sequence\. For anyt≥1t\\geq 1, the action[12](https://arxiv.org/html/2608.26288#S4.E12)is the FTRL update

Xth=−D∇Φ~h,Ct\(Mt−1\)∈arg​min∥X∥op≤D\{⟨∑s=1t−1β−sGs,X⟩\+Rh,Ct​\(X\)\(1−β\)​βt−1\},X\_\{t\}^\{h\}=\-D\\nabla\\widetilde\{\\Phi\}\_\{h,C\_\{t\}\}\(M\_\{t\-1\}\)\\in\\argmin\_\{\\lVert X\\rVert\_\{\\mathrm\{op\}\}\\leq D\}\\left\\\{\\left\\langle\\sum\_\{s=1\}^\{t\-1\}\\beta^\{\-s\}G\_\{s\},X\\right\\rangle\+\\frac\{R\_\{h,C\_\{t\}\}\(X\)\}\{\(1\-\\beta\)\\beta^\{t\-1\}\}\\right\\\},\(31\)where the regularizerRh,CR\_\{h,C\}is given by

Rh,C​\(X\)≔D​Φ~h,C∗​\(X/D\)=D​C​∑i=1rϕh∗​\(σi​\(X\)D\)\.R\_\{h,C\}\(X\)\\coloneqq D\\widetilde\{\\Phi\}\_\{h,C\}^\{\*\}\(X/D\)=DC\\sum\_\{i=1\}^\{r\}\\phi\_\{h\}^\{\*\}\\left\(\\frac\{\\sigma\_\{i\}\(X\)\}\{D\}\\right\)\.\(32\)

By[Theorem5\.7](https://arxiv.org/html/2608.26288#S5.Thmtheorem7)withh=hqh=h\_\{q\}, the finite Newton–Schulz update of[Algorithm1](https://arxiv.org/html/2608.26288#algorithm1)corresponds to FTRL with the regularizerRhq,Ct​\(X\)R\_\{h\_\{q\},C\_\{t\}\}\(X\)controlled by the depthqq\. Atq=0q=0, the regularizer is the Euclidean quadratic\(Ct/2​D\)​∥X∥F2\(C\_\{t\}/2D\)\\lVert X\\rVert\_\{\\mathrm\{F\}\}^\{2\}on the ball, and asq→∞q\\to\\inftyit decays to zero on the ball, and the update approaches the follow\-the\-leader action−D​polar⁡\(Mt−1\)\-D\\polar\(M\_\{t\-1\}\)in[11](https://arxiv.org/html/2608.26288#S3.E11)\. We discuss this in more detail in[AppendixE](https://arxiv.org/html/2608.26288#A5)\.

## 6Conclusion and future work

This paper analyzed Muon with momentum and finite Newton–Schulz through the discounted online\-to\-nonconvex conversion, viewing it as an online learner with a smoothed spectral potential\. In this view, the finite Newton–Schulz iteration is a smoothing mechanism rather than an approximation error, and the depth of the Newton–Schulz iteration governs a penalty–stability tradeoff between the polar\-approximation error and the Lipschitz constant of the update\. Balancing the two terms at a depth that grows only logarithmically in the target accuracy yields sublinear discounted regret, and hence convergence to stationary points of nonsmooth nonconvex objectives, whereas Muon with the exact\-polar update may fail to converge\. For smooth objectives, the same reduction yields rates whose leading terms coincide with those established for exact\-polar Muon, and the regret bound extends to general spectral maps\.

The analysis leaves a gap to deployed Muon\. It fixes the normalization to a constant known before the run, whereas practical Muon normalizes by a data\-dependent quantity such as the current Frobenius norm of the momentum, which can violate the scale condition of[Theorem4\.2](https://arxiv.org/html/2608.26288#S4.Thmtheorem2)\. Our guarantees also assume the classical coefficients obtained from the truncation of the Taylor expansion, rather than the empirically tuned quintic used in the original Muon implementation of[Jordan et al\. \(2024\)](https://arxiv.org/html/2608.26288#bib.bib28)\. Moreover, the conversion queries the gradient at random points between consecutive iterates, whereas practical Muon evaluates it at the current iterate\. Extending the analysis to these practical variants is left for future work\.

## References

- Abernethy et al\. \(2014\)Jacob Abernethy, Chansoo Lee, Abhinav Sinha, and Ambuj Tewari\.Online linear optimization via smoothing\.In*Proceedings of the 27th Conference on Learning Theory*, volume 35, pages 807–823, 2014\.
- Abernethy et al\. \(2016\)Jacob Abernethy, Chansoo Lee, and Ambuj Tewari\.Perturbation techniques in online learning and optimization\.In*Perturbations, Optimization, and Statistics*, chapter 8, pages 233–264\. MIT Press, 2016\.
- Ahn and Cutkosky \(2024\)Kwangjun Ahn and Ashok Cutkosky\.Adam with model exponential moving average is effective for nonconvex optimization\.In*Advances in Neural Information Processing Systems*, volume 37, pages 94909–94933, 2024\.
- Ahn et al\. \(2024\)Kwangjun Ahn, Zhiyu Zhang, Yunbum Kook, and Yan Dai\.Understanding Adam optimizer via online learning of updates: Adam is FTRL in disguise\.In*Proceedings of the 41st International Conference on Machine Learning*, volume 235, pages 619–640, 2024\.
- Ahn et al\. \(2025\)Kwangjun Ahn, Gagik Magakyan, and Ashok Cutkosky\.General framework for online\-to\-nonconvex conversion: Schedule\-free SGD is also effective for nonconvex optimization\.In*Proceedings of the 42nd International Conference on Machine Learning*, volume 267, pages 772–795, 2025\.
- Amsel et al\. \(2026\)Noah Amsel, David Persson, Christopher Musco, and Robert M\. Gower\.The Polar Express: Optimal matrix sign methods and their application to the Muon algorithm\.In*International Conference on Learning Representations*, 2026\.
- Andersson et al\. \(2016\)Fredrik Andersson, Marcus Carlsson, and Karl\-Mikael Perfekt\.Operator\-Lipschitz estimates for the singular value functional calculus\.*Proceedings of the American Mathematical Society*, 144\(5\):1867–1875, 2016\.
- Arjevani et al\. \(2023\)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–2\):165–214, 2023\.
- Bernstein and Newhouse \(2024\)Jeremy Bernstein and Laker Newhouse\.Old optimizer, new norm: An anthology\.In*OPT 2024: 16th Annual Workshop on Optimization for Machine Learning*, 2024\.
- Bernstein and Newhouse \(2025\)Jeremy Bernstein and Laker Newhouse\.Modular duality in deep learning\.In*Proceedings of the 42nd International Conference on Machine Learning*, volume 267, pages 3920–3930, 2025\.
- Björck and Bowie \(1971\)Åke Björck and C\. Bowie\.An iterative algorithm for computing the best estimate of an orthogonal matrix\.*SIAM Journal on Numerical Analysis*, 8\(2\):358–364, 1971\.
- Braun et al\. \(2026\)Guillaume Braun, Han Bao, Wei Huang, and Masaaki Imaizumi\.Spectral gradient descent mitigates anisotropy\-driven misalignment: A case study in phase retrieval\.In*International Conference on Machine Learning*, 2026\.
- Carlson et al\. \(2015\)David E\. Carlson, Edo Collins, Ya\-Ping Hsieh, Lawrence Carin, and Volkan Cevher\.Preconditioned spectral descent for deep learning\.In*Advances in Neural Information Processing Systems*, volume 28, pages 2971–2979, 2015\.
- Carmon et al\. \(2020\)Yair Carmon, John C\. Duchi, Oliver Hinder, and Aaron Sidford\.Lower bounds for finding stationary points I\.*Mathematical Programming*, 184:71–120, 2020\.
- Chen et al\. \(2026\)Lizhang Chen, Jonathan Li, and Qiang Liu\.Muon optimizes under spectral norm constraints\.*Transactions on Machine Learning Research*, 2026\.
- Choudhury et al\. \(2026\)Sayantan Choudhury, Xiaoran Cheng, Martin Takáč, Sen Na, and Mladen Kolar\.Muon with Nesterov momentum: Heavy\-tailed noise and \(randomized\) inexact polar decomposition\.*arXiv preprint arXiv:2605\.06884*, 2026\.
- Cutkosky et al\. \(2023\)Ashok Cutkosky, Harsh Mehta, and Francesco Orabona\.Optimal stochastic non\-smooth non\-convex optimization through online\-to\-non\-convex conversion\.In*Proceedings of the 40th International Conference on Machine Learning*, volume 202, pages 6643–6670, 2023\.
- Davis and Drusvyatskiy \(2025\)Damek Davis and Dmitriy Drusvyatskiy\.When do spectral gradient updates help in deep learning?*arXiv preprint arXiv:2512\.04299*, 2025\.
- Dong and Sawin \(2026\)Yihe Dong and Will Sawin\.Muonp: Muon with fractional spectral powers\.*arXiv preprint arXiv:2606\.13867*, 2026\.
- Fan et al\. \(2025\)Chen Fan, Mark Schmidt, and Christos Thrampoulidis\.Implicit bias of spectral descent and Muon on multiclass separable data\.In*Advances in Neural Information Processing Systems*, volume 38, 2025\.
- Feoktistov et al\. \(2026\)Dmitrii Feoktistov, Timofey Belinsky, Andrey Veprikov, Amir Zainullin, and Aleksandr Beznosikov\.Softsign: Smooth sign in your optimizer for better parameter heterogeneity handling\.In*International Conference on Machine Learning*, 2026\.
- GLM\-4\.5 Team \(2025\)GLM\-4\.5 Team\.GLM\-4\.5: Agentic, reasoning, and coding \(ARC\) foundation models\.*arXiv preprint arXiv:2508\.06471*, 2025\.
- Goldstein \(1977\)A\. A\. Goldstein\.Optimization of Lipschitz continuous functions\.*Mathematical Programming*, 13\(1\):14–22, 1977\.
- Gonon et al\. \(2026\)Antoine Gonon, Andreea\-Alexandra Muşat, and Nicolas Boumal\.Insights on Muon from simple quadratics\.*arXiv preprint arXiv:2602\.11948*, 2026\.
- Ji and Yuan \(2026\)Fanfan Ji and Xiaotong Yuan\.Derandomized online\-to\-non\-convex conversion for stochastic weakly convex optimization\.In*International Conference on Learning Representations*, 2026\.
- Jiang et al\. \(2026a\)Ruichen Jiang, Zakaria Mhammedi, Mehryar Mohri, and Aryan Mokhtari\.Adaptive matrix online learning through smoothing with guarantees for nonsmooth nonconvex optimization\.In*Proceedings of Thirty Ninth Conference on Learning Theory*, volume 336, pages 3782–3824, 2026a\.
- Jiang et al\. \(2026b\)Xiaowen Jiang, Andrei Semenov, and Sebastian U\. Stich\.Enhancing LLM training via spectral clipping\.In*International Conference on Machine Learning*, 2026b\.
- Jordan et al\. \(2024\)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/](https://kellerjordan.github.io/posts/muon/)\.
- Kim and Oh \(2026\)Gyu Yeol Kim and Min\-hwan Oh\.Convergence of Muon with Newton–Schulz\.In*International Conference on Learning Representations*, 2026\.
- Kimi Team \(2025\)Kimi Team\.Kimi K2: Open agentic intelligence\.*arXiv preprint arXiv:2507\.20534*, 2025\.
- Kornowski and Shamir \(2022\)Guy Kornowski and Ohad Shamir\.Oracle complexity in nonsmooth nonconvex optimization\.*Journal of Machine Learning Research*, 23\(314\):1–44, 2022\.
- Kovalev \(2025\)Dmitry Kovalev\.Understanding gradient orthogonalization for deep learning via non\-Euclidean trust\-region optimization\.*arXiv preprint arXiv:2503\.12645*, 2025\.
- Kovarik \(1970\)Zdislav Kovarik\.Some iterative methods for improving orthonormality\.*SIAM Journal on Numerical Analysis*, 7\(3\):386–389, 1970\.
- Lewis \(1995\)Adrian S\. Lewis\.The convex analysis of unitarily invariant matrix functions\.*Journal of Convex Analysis*, 2\(1–2\):173–183, 1995\.
- Li and Hong \(2025\)Jiaxiang Li and Mingyi Hong\.A note on the convergence of Muon\.*arXiv preprint arXiv:2502\.02900*, 2025\.
- Li et al\. \(2026\)Xianliang Li, Zihan Zhang, Weiyang Liu, and Han Bao\.Denoise first, orthogonalize later: Understanding momentum in Muon via spectral filtering\.*arXiv preprint arXiv:2606\.03899*, 2026\.
- Liu et al\. \(2025\)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\.
- Liu et al\. \(2024\)Langqi Liu, Yibo Wang, and Lijun Zhang\.High\-probability bound for non\-smooth non\-convex stochastic optimization with heavy tails\.In*Proceedings of the 41st International Conference on Machine Learning*, volume 235, pages 32122–32138, 2024\.
- Liu \(2026\)Zijian Liu\.Online convex optimization with heavy tails: Old algorithms, new regrets, and applications\.In*Proceedings of The 37th International Conference on Algorithmic Learning Theory*, volume 313, pages 1–47, 2026\.
- Loshchilov and Hutter \(2019\)Ilya Loshchilov and Frank Hutter\.Decoupled weight decay regularization\.In*International Conference on Learning Representations*, 2019\.
- Ma et al\. \(2026\)Jianhao Ma, Yu Huang, Yuejie Chi, and Yuxin Chen\.Preconditioning benefits of spectral orthogonalization in Muon\.*arXiv preprint arXiv:2601\.13474*, 2026\.
- McMahan \(2017\)H\. Brendan McMahan\.A survey of algorithms and analysis for adaptive online learning\.*Journal of Machine Learning Research*, 18\(90\):1–50, 2017\.
- Mustafi et al\. \(2026\)Aratrika Mustafi, Soumya Mukherjee, and Bharath K\. Sriperumbudur\.Move on Muon: A Hamiltonian probability gradient flow perspective of Muon optimizer\.*arXiv preprint arXiv:2605\.23871*, 2026\.
- Parshakova et al\. \(2026\)Tetiana Parshakova, Ahmed Khaled, Michael Crawshaw, Guillaume Garrigos, and Robert M\. Gower\.Muon does not converge on convex Lipschitz functions\.*arXiv preprint arXiv:2605\.08980*, 2026\.
- Patitucci et al\. \(2026\)Francisco Patitucci, Ruichen Jiang, and Aryan Mokhtari\.Improving online\-to\-nonconvex conversion for smooth optimization via double optimism\.In*International Conference on Learning Representations*, 2026\.
- Pethick et al\. \(2025\)Thomas Pethick, Wanyun Xie, Kimon Antonakopoulos, Zhenyu Zhu, Antonio Silveti\-Falls, and Volkan Cevher\.Training deep learning models with norm\-constrained LMOs\.In*Proceedings of the 42nd International Conference on Machine Learning*, volume 267, pages 49069–49104, 2025\.
- Qi et al\. \(2026\)Xianbiao Qi, Marco Chen, Jiaquan Ye, Yelin He, and Rong Xiao\.Delving into Muon and beyond: Deep analysis and extensions\.In*International Conference on Machine Learning*, 2026\.
- Riabinin et al\. \(2026\)Artem Riabinin, Egor Shulgin, Kaja Gruntkowska, and Peter Richtárik\.From Muon to Gluon: Bridging theory and practice of LMO\-based optimizers for LLMs\.In*International Conference on Machine Learning*, 2026\.
- Sfyraki and Wang \(2026\)Maria\-Eleni Sfyraki and Jun\-Kun Wang\.Lions and Muons: Optimization via stochastic Frank–Wolfe under heavy\-tailed noise\.In*International Conference on Machine Learning*, 2026\.
- Shalev\-Shwartz \(2012\)Shai Shalev\-Shwartz\.Online learning and online convex optimization\.*Foundations and Trends in Machine Learning*, 4\(2\):107–194, 2012\.
- Shen et al\. \(2026\)Wei Shen, Ruichuan Huang, Minhui Huang, Cong Shen, and Jiawei Zhang\.On the convergence analysis of Muon\.*Transactions on Machine Learning Research*, 2026\.
- Shulgin et al\. \(2026a\)Egor Shulgin, Sultan Alrashed, Francesco Orabona, and Peter Richtárik\.Beyond the ideal: Analyzing the inexact Muon update\.In*International Conference on Artificial Intelligence and Statistics*, volume 300, 2026a\.
- Shulgin et al\. \(2026b\)Egor Shulgin, Sam Laing, Antonio Orvieto, and Peter Richtárik\.A quadratic lens on Muon: Orthogonalization, invariance, and implicit preconditioning\.In*HiLD 2026: 4th Workshop on High\-dimensional Learning Dynamics*, 2026b\.
- Tsuchiya et al\. \(2023\)Taira Tsuchiya, Shinji Ito, and Junya Honda\.Stability\-penalty\-adaptive follow\-the\-regularized\-leader: Sparsity, game\-dependency, and best\-of\-both\-worlds\.In*Advances in Neural Information Processing Systems*, volume 36, pages 47406–47437, 2023\.
- Wen et al\. \(2026\)Kaiyue Wen, David Hall, Tengyu Ma, and Percy Liang\.Fantastic pretraining optimizers and where to find them\.In*International Conference on Learning Representations*, 2026\.
- Wu et al\. \(2026\)Fangzhou Wu, Rikhav Shah, Sandeep Silwal, and Qiuyi Zhang\.DynMuon: A dynamic spectral shaping view of Muon\.In*HiLD 2026: 4th Workshop on High\-dimensional Learning Dynamics*, 2026\.
- Zhang et al\. \(2020\)Jingzhao Zhang, Hongzhou Lin, Stefanie Jegelka, Suvrit Sra, and Ali Jadbabaie\.Complexity of finding stationary points of nonconvex nonsmooth functions\.In*Proceedings of the 37th International Conference on Machine Learning*, volume 119, pages 11173–11182, 2020\.
- Zhang and Cutkosky \(2024\)Qinzi Zhang and Ashok Cutkosky\.Random scaling and momentum for non\-smooth non\-convex optimization\.In*Proceedings of the 41st International Conference on Machine Learning*, volume 235, pages 58780–58799, 2024\.
- Zimmert and Seldin \(2021\)Julian Zimmert and Yevgeny Seldin\.Tsallis\-INF: An optimal algorithm for stochastic and adversarial bandits\.*Journal of Machine Learning Research*, 22\(28\):1–49, 2021\.

## Appendix AComparison with prior convergence guarantees

This appendix compares the guarantees of this work with those of prior work on Muon and related methods\.

Table 1:Gradient\-oracle complexity for nonsmooth nonconvex objectives under the\(ρ,ε\)\(\\rho,\\varepsilon\)\-stationarity criterion of[Definition2\.2](https://arxiv.org/html/2608.26288#S2.Thmtheorem2)\. Herer=mr=m,ν=\(n/\(n−r−1\)\)1/4\\nu=\(n/\(n\-r\-1\)\)^\{1/4\}, and NS abbreviates Newton–Schulz\. The bounds for Pion and Leon are stated for sufficiently smallε\\varepsilon\.Table 2:Gradient\-oracle complexity for findingε\\varepsilon\-stationary points of smooth nonconvex objectives\. The results are specialized to smoothness in the operator norm and stationarity in the nuclear norm\. The “Deterministic” and “Stochastic” columns give the complexity with exact gradients and with unbiased stochastic gradients of variance at mostσ2\\sigma^\{2\}, respectively, and the bounds for the stochastic setting assume one sample per oracle query\. For[Shulgin et al\. \(2026a\)](https://arxiv.org/html/2608.26288#bib.bib52),δ<1\\delta<1is a uniform additive error of the inexact linear minimization oracle\. For[Kim and Oh \(2026\)](https://arxiv.org/html/2608.26288#bib.bib29),χq=\(1−εq\)−1\\chi\_\{q\}=\(1\-\\varepsilon\_\{q\}\)^\{\-1\}, whereεq\\varepsilon\_\{q\}is the uniform operator\-norm error of theqq\-step Newton–Schulz output relative to the polar factor, and under their uniform condition on the initial residual,χq\\chi\_\{q\}converges to one doubly exponentially inqq\. NS abbreviates Newton–Schulz\.In[Table1](https://arxiv.org/html/2608.26288#A1.T1), we summarize the gradient\-oracle complexity and the treatment of the polar computation for nonsmooth nonconvex objectives\. The leadingρ−1​ε−3\\rho^\{\-1\}\\varepsilon^\{\-3\}term in the bound of this work matches the bounds for Pion and Leon\. The bound for Pion assumes an exact expectation of polar factors, and the Monte Carlo implementation of Pion usesk=Tk=Tsamples per round to preserve this bound\. For exact\-polar Muon, the discounted O2NC framework alone does not provide a general stationarity guarantee for nonsmooth objectives, as discussed in[Section3](https://arxiv.org/html/2608.26288#S3)\. For Pion and Leon, the matrixQ⪰0Q\\succeq 0and the constantG\>0G\>0satisfy𝔼⁡\[Gt​Gt⊤\]⪯Q2\\mathbb\{E\}\[G\_\{t\}G\_\{t\}^\{\\top\}\]\\preceq Q^\{2\}and∥Gt∥op≤G\\lVert G\_\{t\}\\rVert\_\{\\mathrm\{op\}\}\\leq Galmost surely\. The quantities∥Q∥∗2\\lVert Q\\rVert\_\{\*\}^\{2\}andr​\(Γ\+σ\)2r\(\\Gamma\+\\sigma\)^\{2\}reflect different oracle assumptions and are not directly comparable\.

In[Table2](https://arxiv.org/html/2608.26288#A1.T2), we summarize the gradient\-oracle complexity and the treatment of the polar computation for smooth nonconvex objectives\. The leading terms of this work coincide with those established for exact\-polar Muon\([Kovalev, 2025](https://arxiv.org/html/2608.26288#bib.bib32);[Shen et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib51)\)\. Compared with[Kim and Oh \(2026\)](https://arxiv.org/html/2608.26288#bib.bib29), the bounds of this work involve no factorχq\\chi\_\{q\}, and the middle term improves fromr2​σ2/ε2r^\{2\}\\sigma^\{2\}/\\varepsilon^\{2\}tor​σ2/ε2r\\sigma^\{2\}/\\varepsilon^\{2\}, though the algorithms under analysis are slightly different\. The output criteria follow the respective references: an expected minimum for[Kovalev \(2025\)](https://arxiv.org/html/2608.26288#bib.bib32), an average expected gradient norm for the other prior works, and the randomized output in[Theorem5\.6](https://arxiv.org/html/2608.26288#S5.Thmtheorem6)for this work\. The bound for[Shulgin et al\. \(2026a\)](https://arxiv.org/html/2608.26288#bib.bib52)in the stochastic setting specializes their norm\-compatibility factor to the nuclear norm, whose square isrr\. Their guarantee for the inexact LMO requires a uniform errorδ<1\\delta<1, which is not automatically available for a fixed\-depth polar approximation near rank deficiency\. This work additionally assumes an almost\-sure operator\-norm bound and a Frobenius second\-moment bound for the stochastic gradients\.

## Appendix BAuxiliary lemmas on singular\-value functions

For ease of reference, this appendix collects the standard singular\-value lemmas used in this paper\. Some of them are stated in the special forms in which we use them\.

The following three lemmas specialize results of[Lewis \(1995\)](https://arxiv.org/html/2608.26288#bib.bib34)to separable functions of the singular values\.

###### Lemma B\.1\(Convexity of separable singular\-value functions\)\.

Letϕ:\[0,∞\)→ℝ\\phi\\colon\[0,\\infty\)\\to\\mathbb\{R\}be convex and nondecreasing\. ThenS↦∑i=1rϕ⁡\(σi​\(S\)\)S\\mapsto\\sum\_\{i=1\}^\{r\}\\phi\(\\sigma\_\{i\}\(S\)\)is convex onℝm×n\\mathbb\{R\}^\{m\\times n\}\.

###### Proof\.

Definef:ℝr→ℝf\\colon\\mathbb\{R\}^\{r\}\\to\\mathbb\{R\}byf⁡\(γ\)≔∑i=1rϕ⁡\(\|γi\|\)f\(\\gamma\)\\coloneqq\\sum\_\{i=1\}^\{r\}\\phi\(\|\\gamma\_\{i\}\|\)\. Sinceϕ\\phiis convex and nondecreasing, the mapt↦ϕ⁡\(\|t\|\)t\\mapsto\\phi\(\|t\|\)is convex\. Thus,ffis convex, lower semicontinuous, and absolutely symmetric\. Applying[Lewis \(1995, Corollary 2\.6\)](https://arxiv.org/html/2608.26288#bib.bib34)toffshows that the functionS↦\(f∘σ\)​\(S\)=∑i=1rϕ⁡\(σi​\(S\)\)S\\mapsto\(f\\circ\\sigma\)\(S\)=\\sum\_\{i=1\}^\{r\}\\phi\(\\sigma\_\{i\}\(S\)\)is convex, which completes the proof\. ∎

The next lemma gives the corresponding gradient formula\.

###### Lemma B\.2\(Singular\-value gradient formula\)\.

Letϕ:\[0,∞\)→ℝ\\phi\\colon\[0,\\infty\)\\to\\mathbb\{R\}be convex and differentiable withϕ′​\(0\)=0\\phi^\{\\prime\}\(0\)=0, and defineF⁡\(S\)≔∑i=1rϕ⁡\(σi​\(S\)\)F\(S\)\\coloneqq\\sum\_\{i=1\}^\{r\}\\phi\(\\sigma\_\{i\}\(S\)\)\. ThenFFis differentiable on all ofℝm×n\\mathbb\{R\}^\{m\\times n\}, and for any thin singular value decompositionS=Udiag\(σ1\(S\),…,σr\(S\)\)V⊤S=U\\diag\(\\sigma\_\{1\}\(S\),\\ldots,\\sigma\_\{r\}\(S\)\)V^\{\\top\},

∇F\(S\)=Udiag\(ϕ′\(σ1\(S\)\),…,ϕ′\(σr\(S\)\)\)V⊤\.\\nabla F\(S\)=U\\diag\\left\(\\phi^\{\\prime\}\(\\sigma\_\{1\}\(S\)\),\\ldots,\\phi^\{\\prime\}\(\\sigma\_\{r\}\(S\)\)\\right\)V^\{\\top\}\.

###### Proof\.

Definef:ℝr→ℝf\\colon\\mathbb\{R\}^\{r\}\\to\\mathbb\{R\}byf⁡\(γ\)≔∑i=1rϕ⁡\(\|γi\|\)f\(\\gamma\)\\coloneqq\\sum\_\{i=1\}^\{r\}\\phi\(\|\\gamma\_\{i\}\|\)\. Sinceϕ\\phiis convex andϕ′​\(0\)=0\\phi^\{\\prime\}\(0\)=0, it is nondecreasing, and henceffis convex and absolutely symmetric\. The conditionϕ′​\(0\)=0\\phi^\{\\prime\}\(0\)=0also makest↦ϕ⁡\(\|t\|\)t\\mapsto\\phi\(\|t\|\)differentiable at00, soffis differentiable onℝr\\mathbb\{R\}^\{r\}and∇f​\(σ⁡\(S\)\)=\(ϕ′​\(σ1​\(S\)\),…,ϕ′​\(σr​\(S\)\)\)\\nabla f\(\\sigma\(S\)\)=\(\\phi^\{\\prime\}\(\\sigma\_\{1\}\(S\)\),\\ldots,\\phi^\{\\prime\}\(\\sigma\_\{r\}\(S\)\)\)\. Applying[Lewis \(1995, Theorem 3\.1\)](https://arxiv.org/html/2608.26288#bib.bib34)toffshows thatF=f∘σF=f\\circ\\sigmais differentiable and has the above gradient, which completes the proof\. ∎

The following lemma gives the Fenchel conjugate used in the FTRL interpretation\.

###### Lemma B\.3\(Fenchel conjugate formula for singular\-value functions\)\.

Letϕ:\[0,∞\)→\(−∞,\+∞\]\\phi\\colon\[0,\\infty\)\\to\(\-\\infty,\+\\infty\]be proper and convex, and writeϕ∗​\(a\)≔supx≥0\{a​x−ϕ⁡\(x\)\}\\phi^\{\*\}\(a\)\\coloneqq\\sup\_\{x\\geq 0\}\\\{ax\-\\phi\(x\)\\\}\. Then the Fenchel conjugate ofS↦∑i=1rϕ⁡\(σi​\(S\)\)S\\mapsto\\sum\_\{i=1\}^\{r\}\\phi\(\\sigma\_\{i\}\(S\)\)isW↦∑i=1rϕ∗​\(σi​\(W\)\)W\\mapsto\\sum\_\{i=1\}^\{r\}\\phi^\{\*\}\(\\sigma\_\{i\}\(W\)\)\.

###### Proof\.

Definef:ℝr→\(−∞,\+∞\]f\\colon\\mathbb\{R\}^\{r\}\\to\(\-\\infty,\+\\infty\]andF:ℝm×n→\(−∞,\+∞\]F\\colon\\mathbb\{R\}^\{m\\times n\}\\to\(\-\\infty,\+\\infty\]byf⁡\(γ\)≔∑i=1rϕ⁡\(\|γi\|\)f\(\\gamma\)\\coloneqq\\sum\_\{i=1\}^\{r\}\\phi\(\|\\gamma\_\{i\}\|\)andF⁡\(S\)≔∑i=1rϕ⁡\(σi​\(S\)\)F\(S\)\\coloneqq\\sum\_\{i=1\}^\{r\}\\phi\(\\sigma\_\{i\}\(S\)\)\. The functionffis invariant under sign changes and coordinate permutations, andF=f∘σF=f\\circ\\sigma\. Hence,[Lewis \(1995, Theorem 2\.4\)](https://arxiv.org/html/2608.26288#bib.bib34)givesF∗=f∗∘σF^\{\*\}=f^\{\*\}\\circ\\sigma\. For everyμ∈ℝr\\mu\\in\\mathbb\{R\}^\{r\},

f∗​\(μ\)\\displaystyle f^\{\*\}\(\\mu\)=supγ∈ℝr∑i=1r\{μi​γi−ϕ⁡\(\|γi\|\)\}=∑i=1rsupt∈ℝ\{μi​t−ϕ⁡\(\|t\|\)\}\\displaystyle=\\sup\_\{\\gamma\\in\\mathbb\{R\}^\{r\}\}\\sum\_\{i=1\}^\{r\}\\\{\\mu\_\{i\}\\gamma\_\{i\}\-\\phi\(\|\\gamma\_\{i\}\|\)\\\}=\\sum\_\{i=1\}^\{r\}\\sup\_\{t\\in\\mathbb\{R\}\}\\\{\\mu\_\{i\}t\-\\phi\(\|t\|\)\\\}=∑i=1rsupx≥0\{\|μi\|​x−ϕ⁡\(x\)\}=∑i=1rϕ∗​\(\|μi\|\)\.\\displaystyle=\\sum\_\{i=1\}^\{r\}\\sup\_\{x\\geq 0\}\\\{\|\\mu\_\{i\}\|x\-\\phi\(x\)\\\}=\\sum\_\{i=1\}^\{r\}\\phi^\{\*\}\(\|\\mu\_\{i\}\|\)\.Sinceσi​\(W\)≥0\\sigma\_\{i\}\(W\)\\geq 0, we obtainF∗​\(W\)=f∗​\(σ⁡\(W\)\)=∑i=1rϕ∗​\(σi​\(W\)\)F^\{\*\}\(W\)=f^\{\*\}\(\\sigma\(W\)\)=\\sum\_\{i=1\}^\{r\}\\phi^\{\*\}\(\\sigma\_\{i\}\(W\)\), which completes the proof\. ∎

The following lemma for singular\-value maps is used to control the Lipschitz constant of the gradient of the spectral potential\.

###### Lemma B\.4\(Lipschitz bound for singular\-value maps,[Andersson et al\., 2016](https://arxiv.org/html/2608.26288#bib.bib7), Proposition 4\.1 and Theorem 4\.2\)\.

Leth:\[0,∞\)→ℝh\\colon\[0,\\infty\)\\to\\mathbb\{R\}satisfyh⁡\(0\)=0h\(0\)=0and beLip⁡\(h\)\\Lip\(h\)\-Lipschitz\. Then the singular\-value mapℋh\\mathcal\{H\}\_\{h\}of[2](https://arxiv.org/html/2608.26288#S2.E2)is well defined and, for allX,Y∈ℝm×nX,Y\\in\\mathbb\{R\}^\{m\\times n\},

∥ℋh​\(X\)−ℋh​\(Y\)∥F≤Lip⁡\(h\)​∥X−Y∥F\.\\lVert\\mathcal\{H\}\_\{h\}\(X\)\-\\mathcal\{H\}\_\{h\}\(Y\)\\rVert\_\{\\mathrm\{F\}\}\\leq\\Lip\(h\)\\lVert X\-Y\\rVert\_\{\\mathrm\{F\}\}\.

## Appendix CProof of[Lemma3\.1](https://arxiv.org/html/2608.26288#S3.Thmtheorem1)

This appendix provides the proof of[Lemma3\.1](https://arxiv.org/html/2608.26288#S3.Thmtheorem1)\.

###### Proof\.

Letℱ0\\mathcal\{F\}\_\{0\}be theσ\\sigma\-algebra generated by the learner’s initialization and its internal randomness, and, fort≥1t\\geq 1, letℱt\\mathcal\{F\}\_\{t\}be theσ\\sigma\-algebra generated byℱ0\\mathcal\{F\}\_\{0\}and all randomness through roundtt\. By construction,WtW\_\{t\}andXtX\_\{t\}areℱt−1\\mathcal\{F\}\_\{t\-1\}\-measurable\. LetEt≔Gt−∇ℒ​\(W~t\)E\_\{t\}\\coloneqq G\_\{t\}\-\\nabla\\mathcal\{L\}\(\\widetilde\{W\}\_\{t\}\)denote the oracle noise\. Specializing the proof of Proposition 25 of[Jiang et al\. \(2026a\)](https://arxiv.org/html/2608.26288#bib.bib26)to the operator and nuclear norms and usingℒ⁡\(WT\)≥infWℒ⁡\(W\)\\mathcal\{L\}\(W\_\{T\}\)\\geq\\inf\_\{W\}\\mathcal\{L\}\(W\)gives

𝔼⁡\[∥∇ℒ​\(W¯τ\)∥∗\[ρ\]\]\\displaystyle\\mathbb\{E\}\\left\[\\lVert\\nabla\\mathcal\{L\}\(\\bar\{W\}\_\{\\tau\}\)\\rVert\_\{\*\}^\{\[\\rho\]\}\\right\]≤4​Δℒ\(1−β\)​ρ​T\+1T​𝔼​\[RegT\[β\]⁡\(1\)\+\(1−β\)​∑t=1T−1Regt\[β\]⁡\(1\)\]\\displaystyle\\leq\\frac\{4\\Delta\_\{\\mathcal\{L\}\}\}\{\(1\-\\beta\)\\rho T\}\+\\frac\{1\}\{T\}\\mathbb\{E\}\\left\[\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{T\}\(1\)\+\(1\-\\beta\)\\sum\_\{t=1\}^\{T\-1\}\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(1\)\\right\]\+1T​𝔼​\[‖∑t=1TβT−t​Et‖∗\]\+1−βT​∑t=1T−1𝔼⁡\[‖∑s=1tβt−s​Es‖∗\]\.\\displaystyle\\qquad\+\\frac\{1\}\{T\}\\mathbb\{E\}\\left\[\\left\\lVert\\sum\_\{t=1\}^\{T\}\\beta^\{T\-t\}E\_\{t\}\\right\\rVert\_\{\*\}\\right\]\+\\frac\{1\-\\beta\}\{T\}\\sum\_\{t=1\}^\{T\-1\}\\mathbb\{E\}\\left\[\\left\\lVert\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}E\_\{s\}\\right\\rVert\_\{\*\}\\right\]\.EachEtE\_\{t\}isℱt\\mathcal\{F\}\_\{t\}\-measurable\. Conditional onℱt−1\\mathcal\{F\}\_\{t\-1\}andutu\_\{t\},[3](https://arxiv.org/html/2608.26288#S2.E3)of[Assumption2\.1](https://arxiv.org/html/2608.26288#S2.Thmtheorem1)gives𝔼\[Et∣ℱt−1,ut\]=0\\mathbb\{E\}\[E\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\},u\_\{t\}\]=0and𝔼\[∥Et∥F2∣ℱt−1,ut\]≤σ2\\mathbb\{E\}\[\\lVert E\_\{t\}\\rVert\_\{\\mathrm\{F\}\}^\{2\}\\mid\\mathcal\{F\}\_\{t\-1\},u\_\{t\}\]\\leq\\sigma^\{2\}\. The tower property therefore gives𝔼⁡\[Et∣ℱt−1\]=0\\mathbb\{E\}\[E\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\]=0and𝔼⁡\[∥Et∥F2\]≤σ2\\mathbb\{E\}\[\\lVert E\_\{t\}\\rVert\_\{\\mathrm\{F\}\}^\{2\}\]\\leq\\sigma^\{2\}, so\(Et\)t≥1\(E\_\{t\}\)\_\{t\\geq 1\}is a matrix\-valued martingale difference sequence\. Consequently, the conditional orthogonality of the martingale differences gives, for everyt≥1t\\geq 1,

𝔼⁡\[‖∑s=1tβt−s​Es‖F2\]=∑s=1tβ2​\(t−s\)​𝔼​\[∥Es∥F2\]≤σ2​1−β2​t1−β2≤σ21−β2\.\\mathbb\{E\}\\left\[\\left\\lVert\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}E\_\{s\}\\right\\rVert\_\{\\mathrm\{F\}\}^\{2\}\\right\]=\\sum\_\{s=1\}^\{t\}\\beta^\{2\(t\-s\)\}\\mathbb\{E\}\\left\[\\lVert E\_\{s\}\\rVert\_\{\\mathrm\{F\}\}^\{2\}\\right\]\\leq\\sigma^\{2\}\\frac\{1\-\\beta^\{2t\}\}\{1\-\\beta^\{2\}\}\\leq\\frac\{\\sigma^\{2\}\}\{1\-\\beta^\{2\}\}\.The inequality∥⋅∥∗≤r​∥⋅∥F\\lVert\\cdot\\rVert\_\{\*\}\\leq\\sqrt\{r\}\\,\\lVert\\cdot\\rVert\_\{\\mathrm\{F\}\}and Jensen’s inequality give, for everyt≥1t\\geq 1,

𝔼⁡\[‖∑s=1tβt−s​Es‖∗\]≤r​\(𝔼⁡\[‖∑s=1tβt−s​Es‖F2\]\)1/2≤r​σ1−β2\.\\mathbb\{E\}\\left\[\\left\\lVert\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}E\_\{s\}\\right\\rVert\_\{\*\}\\right\]\\leq\\sqrt\{r\}\\left\(\\mathbb\{E\}\\left\[\\left\\lVert\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}E\_\{s\}\\right\\rVert\_\{\\mathrm\{F\}\}^\{2\}\\right\]\\right\)^\{1/2\}\\leq\\frac\{\\sqrt\{r\}\\,\\sigma\}\{\\sqrt\{1\-\\beta^\{2\}\}\}\.Therefore,

1T​𝔼​\[‖∑t=1TβT−t​Et‖∗\]\+1−βT​∑t=1T−1𝔼⁡\[‖∑s=1tβt−s​Es‖∗\]\\displaystyle\\frac\{1\}\{T\}\\mathbb\{E\}\\left\[\\left\\lVert\\sum\_\{t=1\}^\{T\}\\beta^\{T\-t\}E\_\{t\}\\right\\rVert\_\{\*\}\\right\]\+\\frac\{1\-\\beta\}\{T\}\\sum\_\{t=1\}^\{T\-1\}\\mathbb\{E\}\\left\[\\left\\lVert\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}E\_\{s\}\\right\\rVert\_\{\*\}\\right\]≤\(1T\+\(1−β\)​\(T−1\)T\)​r​σ1−β2=\(1−β\+βT\)​r​σ1−β2\.\\displaystyle\\leq\\left\(\\frac\{1\}\{T\}\+\\frac\{\(1\-\\beta\)\(T\-1\)\}\{T\}\\right\)\\frac\{\\sqrt\{r\}\\,\\sigma\}\{\\sqrt\{1\-\\beta^\{2\}\}\}=\\left\(1\-\\beta\+\\frac\{\\beta\}\{T\}\\right\)\\frac\{\\sqrt\{r\}\\,\\sigma\}\{\\sqrt\{1\-\\beta^\{2\}\}\}\.Combining the preceding bounds completes the proof\. ∎

## Appendix DDeferred proofs from[Section5](https://arxiv.org/html/2608.26288#S5)

This appendix provides the proofs deferred from[Section5](https://arxiv.org/html/2608.26288#S5)\.

### D\.1Newton–Schulz iterations at a general Taylor order

The analysis in[Section5](https://arxiv.org/html/2608.26288#S5)specializes to the degree\-five Newton–Schulz polynomial used in[Algorithm1](https://arxiv.org/html/2608.26288#algorithm1)\. We begin by defining the Newton–Schulz iteration obtained by truncating the Taylor expansion at an arbitrary orderκ≥1\\kappa\\geq 1and then show that the same penalty–stability tradeoff holds for every such order\. For an integerκ≥1\\kappa\\geq 1, recall from[5](https://arxiv.org/html/2608.26288#S2.E5)in[Section2](https://arxiv.org/html/2608.26288#S2)the polynomialpκp\_\{\\kappa\}and coefficientscsc\_\{s\}, and define

fκ​\(x\)≔x​pκ​\(x2\)=x​∑s=0κcs​\(1−x2\)s,x∈\[0,1\]\.f\_\{\\kappa\}\(x\)\\coloneqq xp\_\{\\kappa\}\(x^\{2\}\)=x\\sum\_\{s=0\}^\{\\kappa\}c\_\{s\}\(1\-x^\{2\}\)^\{s\},\\qquad x\\in\[0,1\]\.The corresponding Newton–Schulz iteration isxj\+1=fκ​\(xj\)x\_\{j\+1\}=f\_\{\\kappa\}\(x\_\{j\}\), wherefκf\_\{\\kappa\}has degree2​κ\+12\\kappa\+1\. The slope offκf\_\{\\kappa\}at the origin is

Aκ≔fκ′​\(0\)=\(2​κ\+1\)​cκ=\(2​κ\+1\)​\(2​κ\)\!4κ​\(κ\!\)2\.A\_\{\\kappa\}\\coloneqq f\_\{\\kappa\}^\{\\prime\}\(0\)=\(2\\kappa\+1\)c\_\{\\kappa\}=\\frac\{\(2\\kappa\+1\)\(2\\kappa\)\!\}\{4^\{\\kappa\}\(\\kappa\!\)^\{2\}\}\.For an integerq≥0q\\geq 0, define

hκ,q≔fκ∘qon​\[0,1\],hκ,q​\(x\)≔1for​x≥1\.h\_\{\\kappa,q\}\\coloneqq f\_\{\\kappa\}^\{\\circ q\}\\quad\\text\{on \}\[0,1\],\\qquad h\_\{\\kappa,q\}\(x\)\\coloneqq 1\\quad\\text\{for \}x\\geq 1\.The map considered in[Section5](https://arxiv.org/html/2608.26288#S5)is recovered by settingκ=2\\kappa=2, in which case

f2​\(x\)=158​x−54​x3\+38​x5,A2=158,h2,q=hq\.f\_\{2\}\(x\)=\\frac\{15\}\{8\}x\-\\frac\{5\}\{4\}x^\{3\}\+\\frac\{3\}\{8\}x^\{5\},\\qquad A\_\{2\}=\\frac\{15\}\{8\},\\qquad h\_\{2,q\}=h\_\{q\}\.The following lemma generalizes[Lemma5\.2](https://arxiv.org/html/2608.26288#S5.Thmtheorem2)to everyκ≥1\\kappa\\geq 1\. Thus, for every Taylor orderκ\\kappa, the penalty term in[15](https://arxiv.org/html/2608.26288#S4.E15)decreases at rateAκ−qA\_\{\\kappa\}^\{\-q\}, while the stability term grows at rateAκqA\_\{\\kappa\}^\{q\}\. Consequently, the argument in[Section5](https://arxiv.org/html/2608.26288#S5)applies withAκA\_\{\\kappa\}in place ofAA, and our analysis extends to the Newton–Schulz polynomials obtained by truncating the Taylor expansion at any finite order\.

The following lemma establishes the bounds for everyκ≥1\\kappa\\geq 1and yields[Lemma5\.2](https://arxiv.org/html/2608.26288#S5.Thmtheorem2)whenκ=2\\kappa=2\.

###### Lemma D\.1\(Extension of[Lemma5\.2](https://arxiv.org/html/2608.26288#S5.Thmtheorem2)\)\.

For every integerκ≥1\\kappa\\geq 1andq≥0q\\geq 0,

Lip⁡\(hκ,q\)=Aκq,12​Aκq≤Δ⁡\(hκ,q\)≤1Aκq\+1≤1Aκq\.\\Lip\(h\_\{\\kappa,q\}\)=A\_\{\\kappa\}^\{q\},\\qquad\\frac\{1\}\{2A\_\{\\kappa\}^\{q\}\}\\leq\\Delta\(h\_\{\\kappa,q\}\)\\leq\\frac\{1\}\{A\_\{\\kappa\}^\{q\}\+1\}\\leq\\frac\{1\}\{A\_\{\\kappa\}^\{q\}\}\.

###### Proof\.

Fix an integerκ≥1\\kappa\\geq 1and writePκ​\(u\)≔∑s=0κcs​usP\_\{\\kappa\}\(u\)\\coloneqq\\sum\_\{s=0\}^\{\\kappa\}c\_\{s\}u^\{s\}\. Thenfκ​\(x\)=x​Pκ​\(1−x2\)f\_\{\\kappa\}\(x\)=xP\_\{\\kappa\}\(1\-x^\{2\}\)\. Withu≔1−x2u\\coloneqq 1\-x^\{2\}, differentiation and the identity2​\(s\+1\)​cs\+1=\(2​s\+1\)​cs2\(s\+1\)c\_\{s\+1\}=\(2s\+1\)c\_\{s\}give

fκ′​\(x\)\\displaystyle f\_\{\\kappa\}^\{\\prime\}\(x\)=Pκ​\(u\)−2​\(1−u\)​Pκ′​\(u\)\\displaystyle=P\_\{\\kappa\}\(u\)\-2\(1\-u\)P\_\{\\kappa\}^\{\\prime\}\(u\)=∑s=0κcs​us−2​\(1−u\)​∑s=1κs​cs​us−1\\displaystyle=\\sum\_\{s=0\}^\{\\kappa\}c\_\{s\}u^\{s\}\-2\(1\-u\)\\sum\_\{s=1\}^\{\\kappa\}sc\_\{s\}u^\{s\-1\}=\(2​κ\+1\)​cκ​uκ\+∑s=0κ−1\(\(2​s\+1\)​cs−2​\(s\+1\)​cs\+1\)​us\\displaystyle=\(2\\kappa\+1\)c\_\{\\kappa\}u^\{\\kappa\}\+\\sum\_\{s=0\}^\{\\kappa\-1\}\\bigl\(\(2s\+1\)c\_\{s\}\-2\(s\+1\)c\_\{s\+1\}\\bigr\)u^\{s\}=\(2​κ\+1\)​cκ​uκ=Aκ​\(1−x2\)κ\.\\displaystyle=\(2\\kappa\+1\)c\_\{\\kappa\}u^\{\\kappa\}=A\_\{\\kappa\}\(1\-x^\{2\}\)^\{\\kappa\}\.Therefore0≤fκ′​\(x\)≤Aκ0\\leq f\_\{\\kappa\}^\{\\prime\}\(x\)\\leq A\_\{\\kappa\}on\[0,1\]\[0,1\], with maximumAκA\_\{\\kappa\}atx=0x=0\. Sincefκ′≥0f\_\{\\kappa\}^\{\\prime\}\\geq 0,fκ​\(0\)=0f\_\{\\kappa\}\(0\)=0, andfκ​\(1\)=1f\_\{\\kappa\}\(1\)=1, the mapfκf\_\{\\kappa\}sends\[0,1\]\[0,1\]into itself, and hence so does everyhκ,qh\_\{\\kappa,q\}\. The caseq=0q=0is immediate, and forq≥1q\\geq 1the chain rulehκ,q′​\(x\)=∏j=0q−1fκ′​\(hκ,j​\(x\)\)h\_\{\\kappa,q\}^\{\\prime\}\(x\)=\\prod\_\{j=0\}^\{q\-1\}f\_\{\\kappa\}^\{\\prime\}\(h\_\{\\kappa,j\}\(x\)\)gives0≤hκ,q′​\(x\)≤Aκq0\\leq h\_\{\\kappa,q\}^\{\\prime\}\(x\)\\leq A\_\{\\kappa\}^\{q\}on\[0,1\]\[0,1\]\. Atx=0x=0every factor equalsfκ′​\(0\)=Aκf\_\{\\kappa\}^\{\\prime\}\(0\)=A\_\{\\kappa\}becausehκ,j​\(0\)=0h\_\{\\kappa,j\}\(0\)=0, and hencehκ,q′​\(0\)=Aκqh\_\{\\kappa,q\}^\{\\prime\}\(0\)=A\_\{\\kappa\}^\{q\}\. Extendinghκ,qh\_\{\\kappa,q\}by the constant11on\[1,∞\)\[1,\\infty\)leaves this bound unchanged, soLip⁡\(hκ,q\)=Aκq\\Lip\(h\_\{\\kappa,q\}\)=A\_\{\\kappa\}^\{q\}\.

For the lower bound onΔ⁡\(hκ,q\)\\Delta\(h\_\{\\kappa,q\}\), the propertieshκ,q​\(0\)=0h\_\{\\kappa,q\}\(0\)=0,Lip⁡\(hκ,q\)=Aκq\\Lip\(h\_\{\\kappa,q\}\)=A\_\{\\kappa\}^\{q\}, andhκ,q≤1h\_\{\\kappa,q\}\\leq 1givehκ,q​\(x\)≤min⁡\{Aκq​x,1\}h\_\{\\kappa,q\}\(x\)\\leq\\min\\\{A\_\{\\kappa\}^\{q\}x,1\\\}\. Therefore

Δ⁡\(hκ,q\)=∫0∞\(1−hκ,q​\(x\)\)​𝑑x≥∫0Aκ−q\(1−Aκq​x\)​𝑑x=1Aκq−12​Aκq=12​Aκq\.\\Delta\(h\_\{\\kappa,q\}\)=\\int\_\{0\}^\{\\infty\}\(1\-h\_\{\\kappa,q\}\(x\)\)\\,\\mathrm\{d\}x\\geq\\int\_\{0\}^\{A\_\{\\kappa\}^\{\-q\}\}\(1\-A\_\{\\kappa\}^\{q\}x\)\\,\\mathrm\{d\}x=\\frac\{1\}\{A\_\{\\kappa\}^\{q\}\}\-\\frac\{1\}\{2A\_\{\\kappa\}^\{q\}\}=\\frac\{1\}\{2A\_\{\\kappa\}^\{q\}\}\.
For the upper bound onΔ⁡\(hκ,q\)\\Delta\(h\_\{\\kappa,q\}\), define forL≥1L\\geq 1andx∈\[0,1\]x\\in\[0,1\]

gL​\(x\)≔1−\(1−x\)L\.g\_\{L\}\(x\)\\coloneqq 1\-\(1\-x\)^\{L\}\.This family maps\[0,1\]\[0,1\]into itself and satisfies the composition identitygL∘gM=gL​Mg\_\{L\}\\circ g\_\{M\}=g\_\{LM\}forL,M≥1L,M\\geq 1\. We first show thatfκ​\(x\)≥gAκ​\(x\)f\_\{\\kappa\}\(x\)\\geq g\_\{A\_\{\\kappa\}\}\(x\)on\[0,1\]\[0,1\]\. Bothfκ′​\(x\)=Aκ​\(1−x2\)κf\_\{\\kappa\}^\{\\prime\}\(x\)=A\_\{\\kappa\}\(1\-x^\{2\}\)^\{\\kappa\}andgAκ′​\(x\)=Aκ​\(1−x\)Aκ−1g\_\{A\_\{\\kappa\}\}^\{\\prime\}\(x\)=A\_\{\\kappa\}\(1\-x\)^\{A\_\{\\kappa\}\-1\}are positive forx∈\[0,1\)x\\in\[0,1\), so\(fκ−gAκ\)′​\(x\)\(f\_\{\\kappa\}\-g\_\{A\_\{\\kappa\}\}\)^\{\\prime\}\(x\)has the same sign as

ψκ​\(x\)≔log⁡fκ′​\(x\)gAκ′​\(x\)=κ​log⁡\(1\+x\)\+\(κ\+1−Aκ\)​log⁡\(1−x\),\\psi\_\{\\kappa\}\(x\)\\coloneqq\\log\\frac\{f\_\{\\kappa\}^\{\\prime\}\(x\)\}\{g\_\{A\_\{\\kappa\}\}^\{\\prime\}\(x\)\}=\\kappa\\log\(1\+x\)\+\(\\kappa\+1\-A\_\{\\kappa\}\)\\log\(1\-x\),whose derivative is

ψκ′​\(x\)=Aκ−1−\(2​κ\+1−Aκ\)​x1−x2\.\\psi\_\{\\kappa\}^\{\\prime\}\(x\)=\\frac\{A\_\{\\kappa\}\-1\-\(2\\kappa\+1\-A\_\{\\kappa\}\)x\}\{1\-x^\{2\}\}\.To determine the sign of the numerator, we boundAκA\_\{\\kappa\}\. Sincefκ​\(1\)−fκ​\(0\)=1f\_\{\\kappa\}\(1\)\-f\_\{\\kappa\}\(0\)=1, integratingfκ′​\(x\)=Aκ​\(1−x2\)κf\_\{\\kappa\}^\{\\prime\}\(x\)=A\_\{\\kappa\}\(1\-x^\{2\}\)^\{\\kappa\}over\[0,1\]\[0,1\]givesAκ−1=∫01\(1−x2\)κ​𝑑xA\_\{\\kappa\}^\{\-1\}=\\int\_\{0\}^\{1\}\(1\-x^\{2\}\)^\{\\kappa\}\\,\\mathrm\{d\}x\. Combining this with\(1−x\)κ<\(1−x2\)κ<1\(1\-x\)^\{\\kappa\}<\(1\-x^\{2\}\)^\{\\kappa\}<1on\(0,1\)\(0,1\)gives

1κ\+1=∫01\(1−x\)κ​𝑑x<∫01\(1−x2\)κ​𝑑x=1Aκ<1,\\frac\{1\}\{\\kappa\+1\}=\\int\_\{0\}^\{1\}\(1\-x\)^\{\\kappa\}\\,\\mathrm\{d\}x<\\int\_\{0\}^\{1\}\(1\-x^\{2\}\)^\{\\kappa\}\\,\\mathrm\{d\}x=\\frac\{1\}\{A\_\{\\kappa\}\}<1,so1<Aκ<κ\+11<A\_\{\\kappa\}<\\kappa\+1\. Hence the numerator is positive atx=0x=0and negative atx=1x=1, and it has a unique zero in\(0,1\)\(0,1\)\. The denominator is positive on\[0,1\)\[0,1\), soψκ\\psi\_\{\\kappa\}first increases and then decreases\. Sinceψκ​\(0\)=0\\psi\_\{\\kappa\}\(0\)=0andψκ​\(x\)→−∞\\psi\_\{\\kappa\}\(x\)\\to\-\\inftyasx→1x\\to 1, there is a uniquex¯∈\(0,1\)\\bar\{x\}\\in\(0,1\)such that

ψκ​\(x\)≥0for​x∈\[0,x¯\],ψκ​\(x\)≤0for​x∈\[x¯,1\)\.\\psi\_\{\\kappa\}\(x\)\\geq 0\\quad\\text\{for \}x\\in\[0,\\bar\{x\}\],\\qquad\\psi\_\{\\kappa\}\(x\)\\leq 0\\quad\\text\{for \}x\\in\[\\bar\{x\},1\)\.Hencefκ−gAκf\_\{\\kappa\}\-g\_\{A\_\{\\kappa\}\}is nondecreasing on\[0,x¯\]\[0,\\bar\{x\}\]and nonincreasing on\[x¯,1\]\[\\bar\{x\},1\], and sincefκ​\(0\)−gAκ​\(0\)=fκ​\(1\)−gAκ​\(1\)=0f\_\{\\kappa\}\(0\)\-g\_\{A\_\{\\kappa\}\}\(0\)=f\_\{\\kappa\}\(1\)\-g\_\{A\_\{\\kappa\}\}\(1\)=0, we concludefκ​\(x\)≥gAκ​\(x\)f\_\{\\kappa\}\(x\)\\geq g\_\{A\_\{\\kappa\}\}\(x\)on\[0,1\]\[0,1\]\.

We next provehκ,q≥gAκqh\_\{\\kappa,q\}\\geq g\_\{A\_\{\\kappa\}^\{q\}\}for everyq≥0q\\geq 0by induction onqq\. The base casehκ,0=g1h\_\{\\kappa,0\}=g\_\{1\}is immediate\. Assuminghκ,q≥gAκqh\_\{\\kappa,q\}\\geq g\_\{A\_\{\\kappa\}^\{q\}\}, the monotonicity offκf\_\{\\kappa\}, the boundfκ≥gAκf\_\{\\kappa\}\\geq g\_\{A\_\{\\kappa\}\}, and the composition identity give

hκ,q\+1=fκ∘hκ,q≥fκ∘gAκq≥gAκ∘gAκq=gAκq\+1,h\_\{\\kappa,q\+1\}=f\_\{\\kappa\}\\circ h\_\{\\kappa,q\}\\geq f\_\{\\kappa\}\\circ g\_\{A\_\{\\kappa\}^\{q\}\}\\geq g\_\{A\_\{\\kappa\}\}\\circ g\_\{A\_\{\\kappa\}^\{q\}\}=g\_\{A\_\{\\kappa\}^\{q\+1\}\},which completes the induction\. Finally,hκ,q≥gAκqh\_\{\\kappa,q\}\\geq g\_\{A\_\{\\kappa\}^\{q\}\}andhκ,q​\(x\)=1h\_\{\\kappa,q\}\(x\)=1forx≥1x\\geq 1give

Δ⁡\(hκ,q\)=∫01\(1−hκ,q​\(x\)\)​𝑑x≤∫01\(1−x\)Aκq​𝑑x=1Aκq\+1≤1Aκq,\\Delta\(h\_\{\\kappa,q\}\)=\\int\_\{0\}^\{1\}\(1\-h\_\{\\kappa,q\}\(x\)\)\\,\\mathrm\{d\}x\\leq\\int\_\{0\}^\{1\}\(1\-x\)^\{A\_\{\\kappa\}^\{q\}\}\\,\\mathrm\{d\}x=\\frac\{1\}\{A\_\{\\kappa\}^\{q\}\+1\}\\leq\\frac\{1\}\{A\_\{\\kappa\}^\{q\}\},which completes the proof\. ∎

### D\.2Proof of[Theorem5\.1](https://arxiv.org/html/2608.26288#S5.Thmtheorem1)

###### Proof of[Theorem5\.1](https://arxiv.org/html/2608.26288#S5.Thmtheorem1)\.

By the definition of the depth in[Theorem5\.1](https://arxiv.org/html/2608.26288#S5.Thmtheorem1),

Gop​rΓ​1−β≤Aq<A​Gop​rΓ​1−β\.\\frac\{G\_\{\\mathrm\{op\}\}\\sqrt\{r\}\}\{\\Gamma\\sqrt\{1\-\\beta\}\}\\leq A^\{q\}<\\frac\{AG\_\{\\mathrm\{op\}\}\\sqrt\{r\}\}\{\\Gamma\\sqrt\{1\-\\beta\}\}\.Then, byC=GopC=G\_\{\\mathrm\{op\}\}together withΔ⁡\(hq\)≤A−q\\Delta\(h\_\{q\}\)\\leq A^\{\-q\}andLip⁡\(hq\)=Aq\\Lip\(h\_\{q\}\)=A^\{q\}from[Lemma5\.2](https://arxiv.org/html/2608.26288#S5.Thmtheorem2), the first term in[15](https://arxiv.org/html/2608.26288#S4.E15)of[Theorem4\.2](https://arxiv.org/html/2608.26288#S4.Thmtheorem2)is bounded by

r​Gop\(1−β\)​Aq≤r​Gop\(1−β\)​\(Gop​r/\(Γ​1−β\)\)=Γ​r1−β\.\\frac\{rG\_\{\\mathrm\{op\}\}\}\{\(1\-\\beta\)A^\{q\}\}\\leq\\frac\{rG\_\{\\mathrm\{op\}\}\}\{\(1\-\\beta\)\\left\(G\_\{\\mathrm\{op\}\}\\sqrt\{r\}/\(\\Gamma\\sqrt\{1\-\\beta\}\)\\right\)\}=\\Gamma\\sqrt\{\\frac\{r\}\{1\-\\beta\}\}\.The second term satisfies

2​Aq​Γ2Gop<2​A​\(Gop​r/\(Γ​1−β\)\)​Γ2Gop=2​A​Γ​r1−β\.\\frac\{2A^\{q\}\\Gamma^\{2\}\}\{G\_\{\\mathrm\{op\}\}\}<\\frac\{2A\\left\(G\_\{\\mathrm\{op\}\}\\sqrt\{r\}/\(\\Gamma\\sqrt\{1\-\\beta\}\)\\right\)\\Gamma^\{2\}\}\{G\_\{\\mathrm\{op\}\}\}=2A\\Gamma\\sqrt\{\\frac\{r\}\{1\-\\beta\}\}\.Adding these two bounds yields[24](https://arxiv.org/html/2608.26288#S5.E24), which completes the proof\. ∎

### D\.3Proof of[Theorem5\.3](https://arxiv.org/html/2608.26288#S5.Thmtheorem3)

###### Proof of[Theorem5\.3](https://arxiv.org/html/2608.26288#S5.Thmtheorem3)\.

Ifε\>BNS\\varepsilon\>B\_\{\\mathrm\{NS\}\}, the definition ofBNSB\_\{\\mathrm\{NS\}\}andA=15/8A=15/8giveBNS≥\(1\+2​A\)​r​Γ\>3​r​Γ\.B\_\{\\mathrm\{NS\}\}\\geq\(1\+2A\)\\sqrt\{r\}\\,\\Gamma\>3\\sqrt\{r\}\\,\\Gamma\.Hence, every pointWWsatisfies

∥∇ℒ​\(W\)∥∗\[ρ\]≤∥∇ℒ​\(W\)∥∗≤r​∥∇ℒ​\(W\)∥F≤r​Γ<ε3\.\\lVert\\nabla\\mathcal\{L\}\(W\)\\rVert\_\{\*\}^\{\[\\rho\]\}\\leq\\lVert\\nabla\\mathcal\{L\}\(W\)\\rVert\_\{\*\}\\leq\\sqrt\{r\}\\,\\lVert\\nabla\\mathcal\{L\}\(W\)\\rVert\_\{\\mathrm\{F\}\}\\leq\\sqrt\{r\}\\,\\Gamma<\\frac\{\\varepsilon\}\{3\}\.Consequently,𝔼⁡\[∥∇ℒ​\(W¯τ\)∥∗\[ρ\]\]<ε/3\\mathbb\{E\}\[\\lVert\\nabla\\mathcal\{L\}\(\\bar\{W\}\_\{\\tau\}\)\\rVert\_\{\*\}^\{\[\\rho\]\}\]<\\varepsilon/3, so[26](https://arxiv.org/html/2608.26288#S5.E26)holds in this case\.

It remains to considerε≤BNS\\varepsilon\\leq B\_\{\\mathrm\{NS\}\}\. Then1−β=\(ε/3​BNS\)2≤1/91\-\\beta=\(\\varepsilon/3B\_\{\\mathrm\{NS\}\}\)^\{2\}\\leq 1/9\. We first verify the condition of[Theorem5\.1](https://arxiv.org/html/2608.26288#S5.Thmtheorem1)\.Γ≤r​Gop\\Gamma\\leq\\sqrt\{r\}G\_\{\\mathrm\{op\}\}\(from∥Gs∥F≤r​∥Gs∥op≤r​Gop\\lVert G\_\{s\}\\rVert\_\{\\mathrm\{F\}\}\\leq\\sqrt\{r\}\\lVert G\_\{s\}\\rVert\_\{\\mathrm\{op\}\}\\leq\\sqrt\{r\}G\_\{\\mathrm\{op\}\}\) givesGop​r/\(Γ​1−β\)≥1/1−β\>1G\_\{\\mathrm\{op\}\}\\sqrt\{r\}/\(\\Gamma\\sqrt\{1\-\\beta\}\)\\geq 1/\\sqrt\{1\-\\beta\}\>1, so, using1−β=ε/\(3​BNS\)\\sqrt\{1\-\\beta\}=\\varepsilon/\(3B\_\{\\mathrm\{NS\}\}\), the depth specified in[Theorem5\.3](https://arxiv.org/html/2608.26288#S5.Thmtheorem3)equals the depth required in[Theorem5\.1](https://arxiv.org/html/2608.26288#S5.Thmtheorem1)\. Hence,Regt\[β\]⁡\(D\)=D​Regt\[β\]⁡\(1\)\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(D\)=D\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(1\)gives

𝔼⁡\[Regt\[β\]⁡\(1\)\]≤\(1\+2​A\)​Γ​r1−β\.\\mathbb\{E\}\[\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(1\)\]\\leq\(1\+2A\)\\Gamma\\sqrt\{\\frac\{r\}\{1\-\\beta\}\}\.Substituting this into the regret term of[Lemma3\.1](https://arxiv.org/html/2608.26288#S3.Thmtheorem1)and using\(1\+\(1−β\)​\(T−1\)\)/T=1−β\+β/T\\left\(1\+\(1\-\\beta\)\(T\-1\)\\right\)/T=1\-\\beta\+\\beta/Tgives

1T​𝔼​\[RegT\[β\]⁡\(1\)\+\(1−β\)​∑t=1T−1Regt\[β\]⁡\(1\)\]≤\(1−β\+βT\)​\(1\+2​A\)​Γ​r1−β\.\\frac\{1\}\{T\}\\mathbb\{E\}\\left\[\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{T\}\(1\)\+\(1\-\\beta\)\\sum\_\{t=1\}^\{T\-1\}\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(1\)\\right\]\\leq\\left\(1\-\\beta\+\\frac\{\\beta\}\{T\}\\right\)\(1\+2A\)\\Gamma\\sqrt\{\\frac\{r\}\{1\-\\beta\}\}\.Since1−β2≥1−β\\sqrt\{1\-\\beta^\{2\}\}\\geq\\sqrt\{1\-\\beta\}, it holds that

1−β\+β/T1−β2≤1−β\+β/T1−β=1−β\+βT​1−β,\\frac\{1\-\\beta\+\\beta/T\}\{\\sqrt\{1\-\\beta^\{2\}\}\}\\leq\\frac\{1\-\\beta\+\\beta/T\}\{\\sqrt\{1\-\\beta\}\}=\\sqrt\{1\-\\beta\}\+\\frac\{\\beta\}\{T\\sqrt\{1\-\\beta\}\},andBNS=r​\(\(1\+2​A\)​Γ\+σ\)B\_\{\\mathrm\{NS\}\}=\\sqrt\{r\}\\left\(\(1\+2A\)\\Gamma\+\\sigma\\right\)gives

1T​𝔼​\[RegT\[β\]⁡\(1\)\+\(1−β\)​∑t=1T−1Regt\[β\]⁡\(1\)\]\+\(1−β\+βT\)​r​σ1−β2≤BNS​\(1−β\+βT​1−β\)\.\\frac\{1\}\{T\}\\mathbb\{E\}\\left\[\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{T\}\(1\)\+\(1\-\\beta\)\\sum\_\{t=1\}^\{T\-1\}\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(1\)\\right\]\+\\left\(1\-\\beta\+\\frac\{\\beta\}\{T\}\\right\)\\frac\{\\sqrt\{r\}\\,\\sigma\}\{\\sqrt\{1\-\\beta^\{2\}\}\}\\leq B\_\{\\mathrm\{NS\}\}\\left\(\\sqrt\{1\-\\beta\}\+\\frac\{\\beta\}\{T\\sqrt\{1\-\\beta\}\}\\right\)\.Thus[Lemma3\.1](https://arxiv.org/html/2608.26288#S3.Thmtheorem1)gives

𝔼⁡\[∥∇ℒ​\(W¯τ\)∥∗\[ρ\]\]≤4​Δℒ\(1−β\)​ρ​T\+BNS​\(1−β\+βT​1−β\)\.\\mathbb\{E\}\\left\[\\lVert\\nabla\\mathcal\{L\}\(\\bar\{W\}\_\{\\tau\}\)\\rVert\_\{\*\}^\{\[\\rho\]\}\\right\]\\leq\\frac\{4\\Delta\_\{\\mathcal\{L\}\}\}\{\(1\-\\beta\)\\rho T\}\+B\_\{\\mathrm\{NS\}\}\\left\(\\sqrt\{1\-\\beta\}\+\\frac\{\\beta\}\{T\\sqrt\{1\-\\beta\}\}\\right\)\.HereBNS​1−β=ε/3B\_\{\\mathrm\{NS\}\}\\sqrt\{1\-\\beta\}=\\varepsilon/3, the first term is36​Δℒ​BNS2/\(ρ​ε2​T\)36\\Delta\_\{\\mathcal\{L\}\}B\_\{\\mathrm\{NS\}\}^\{2\}/\(\\rho\\varepsilon^\{2\}T\), and the third term is3​β​BNS2/\(ε​T\)3\\beta B\_\{\\mathrm\{NS\}\}^\{2\}/\(\\varepsilon T\)\. SinceBNS2=O⁡\(r​\(Γ\+σ\)2\)B\_\{\\mathrm\{NS\}\}^\{2\}=O\(r\(\\Gamma\+\\sigma\)^\{2\}\), this proves[26](https://arxiv.org/html/2608.26288#S5.E26), and requiring each of the twoTT\-dependent terms to be at mostε/3\\varepsilon/3gives[27](https://arxiv.org/html/2608.26288#S5.E27), which completes the proof\. ∎

### D\.4Deferred proofs from[Section5\.3](https://arxiv.org/html/2608.26288#S5.SS3)

Here, we prove the results of[Section5\.3](https://arxiv.org/html/2608.26288#S5.SS3)under[Assumptions2\.1](https://arxiv.org/html/2608.26288#S2.Thmtheorem1)and[5\.4](https://arxiv.org/html/2608.26288#S5.Thmtheorem4)\. Writegs≔∇ℒ​\(W~s\)g\_\{s\}\\coloneqq\\nabla\\mathcal\{L\}\(\\widetilde\{W\}\_\{s\}\)for the gradient at the query point of roundss, and let𝒬s\\mathcal\{Q\}\_\{s\}be theσ\\sigma\-algebra of the history up to and including the choice ofW~s\\widetilde\{W\}\_\{s\}, so thatgsg\_\{s\}andMs−1M\_\{s\-1\}are𝒬s\\mathcal\{Q\}\_\{s\}\-measurable\. Thus,[Assumption2\.1](https://arxiv.org/html/2608.26288#S2.Thmtheorem1)withW=W~sW=\\widetilde\{W\}\_\{s\}gives𝔼⁡\[Gs∣𝒬s\]=gs\\mathbb\{E\}\[G\_\{s\}\\mid\\mathcal\{Q\}\_\{s\}\]=g\_\{s\}and𝔼⁡\[∥Gs−gs∥F2∣𝒬s\]≤σ2\\mathbb\{E\}\[\\lVert G\_\{s\}\-g\_\{s\}\\rVert\_\{\\mathrm\{F\}\}^\{2\}\\mid\\mathcal\{Q\}\_\{s\}\]\\leq\\sigma^\{2\}\.

###### Proof of[Lemma5\.5](https://arxiv.org/html/2608.26288#S5.Thmtheorem5)\.

For anyp∈𝒫⁡\(W,ρ\)p\\in\\mathcal\{P\}\(W;\\rho\), the triangle inequality and[28](https://arxiv.org/html/2608.26288#S5.E28)give

∥∇ℒ​\(W\)∥∗≤∥𝔼Y∼p​\[∇ℒ​\(Y\)\]∥∗\+𝔼Y∼p​\[∥∇ℒ​\(W\)−∇ℒ​\(Y\)∥∗\]≤∥𝔼Y∼p​\[∇ℒ​\(Y\)\]∥∗\+Lop​ρ,\\lVert\\nabla\\mathcal\{L\}\(W\)\\rVert\_\{\*\}\\leq\\lVert\\mathbb\{E\}\_\{Y\\sim p\}\\left\[\\nabla\\mathcal\{L\}\(Y\)\\right\]\\rVert\_\{\*\}\+\\mathbb\{E\}\_\{Y\\sim p\}\\left\[\\lVert\\nabla\\mathcal\{L\}\(W\)\-\\nabla\\mathcal\{L\}\(Y\)\\rVert\_\{\*\}\\right\]\\leq\\lVert\\mathbb\{E\}\_\{Y\\sim p\}\\left\[\\nabla\\mathcal\{L\}\(Y\)\\right\]\\rVert\_\{\*\}\+L\_\{\\mathrm\{op\}\}\\rho,using𝔼Y∼p​\[∥Y−W∥op\]≤ρ\\mathbb\{E\}\_\{Y\\sim p\}\\left\[\\lVert Y\-W\\rVert\_\{\\mathrm\{op\}\}\\right\]\\leq\\rho\. Taking the infimum overppcompletes the proof\. ∎

###### Lemma D\.2\.

Under[Assumption2\.1](https://arxiv.org/html/2608.26288#S2.Thmtheorem1), for everys≥1s\\geq 1,

𝔼\[BΦ~hq,Gop\(Ms∥Ms−1\)\|𝒬s\]≤2\(1−β\)∥gs−Ms−1∥∗\+Aq​\(1−β\)22​Gopσ2\.\\mathbb\{E\}\\left\[B\_\{\\widetilde\{\\Phi\}\_\{h\_\{q\},G\_\{\\mathrm\{op\}\}\}\}\(M\_\{s\}\\\|M\_\{s\-1\}\)\\,\\middle\|\\,\\mathcal\{Q\}\_\{s\}\\right\]\\leq 2\(1\-\\beta\)\\lVert g\_\{s\}\-M\_\{s\-1\}\\rVert\_\{\*\}\+\\frac\{A^\{q\}\(1\-\\beta\)^\{2\}\}\{2G\_\{\\mathrm\{op\}\}\}\\sigma^\{2\}\.\(33\)

###### Proof\.

LetΨ≔Φ~hq,Gop\\Psi\\coloneqq\\widetilde\{\\Phi\}\_\{h\_\{q\},G\_\{\\mathrm\{op\}\}\}andM^s≔β​Ms−1\+\(1−β\)​gs\\widehat\{M\}\_\{s\}\\coloneqq\\beta M\_\{s\-1\}\+\(1\-\\beta\)g\_\{s\}for simplicity\. First, the updateMsM\_\{s\}is related toM^s\\widehat\{M\}\_\{s\}by

Ms=M^s\+\(1−β\)​\(Gs−gs\),M^s=β​Ms−1\+\(1−β\)​gs\.M\_\{s\}=\\widehat\{M\}\_\{s\}\+\(1\-\\beta\)\(G\_\{s\}\-g\_\{s\}\),\\qquad\\widehat\{M\}\_\{s\}=\\beta M\_\{s\-1\}\+\(1\-\\beta\)g\_\{s\}\.By the definition of the Bregman divergence, the pointsMs−1,M^s,MsM\_\{s\-1\},\\widehat\{M\}\_\{s\},M\_\{s\}satisfy

BΨ\(Ms∥Ms−1\)=\\displaystyle B\_\{\\Psi\}\(M\_\{s\}\\\|M\_\{s\-1\}\)=BΨ\(M^s∥Ms−1\)\+BΨ\(Ms∥M^s\)\+⟨∇Ψ\(M^s\)−∇Ψ\(Ms−1\),Ms−M^s⟩\.\\displaystyle B\_\{\\Psi\}\(\\widehat\{M\}\_\{s\}\\\|M\_\{s\-1\}\)\+B\_\{\\Psi\}\(M\_\{s\}\\\|\\widehat\{M\}\_\{s\}\)\+\\langle\\nabla\\Psi\(\\widehat\{M\}\_\{s\}\)\-\\nabla\\Psi\(M\_\{s\-1\}\),M\_\{s\}\-\\widehat\{M\}\_\{s\}\\rangle\.\(34\)The last inner product has zero conditional expectation, since𝔼⁡\[Ms−M^s∣𝒬s\]=\(1−β\)​𝔼​\[Gs−gs∣𝒬s\]=0\\mathbb\{E\}\[M\_\{s\}\-\\widehat\{M\}\_\{s\}\\mid\\mathcal\{Q\}\_\{s\}\]=\(1\-\\beta\)\\mathbb\{E\}\[G\_\{s\}\-g\_\{s\}\\mid\\mathcal\{Q\}\_\{s\}\]=0\.

ForBΨ\(M^s∥Ms−1\)B\_\{\\Psi\}\(\\widehat\{M\}\_\{s\}\\\|M\_\{s\-1\}\), usingM^s−Ms−1=\(1−β\)​\(gs−Ms−1\)\\widehat\{M\}\_\{s\}\-M\_\{s\-1\}=\(1\-\\beta\)\(g\_\{s\}\-M\_\{s\-1\}\), we have

BΨ\(M^s∥Ms−1\)\\displaystyle B\_\{\\Psi\}\(\\widehat\{M\}\_\{s\}\\\|M\_\{s\-1\}\)=Ψ⁡\(M^s\)−Ψ⁡\(Ms−1\)−⟨∇Ψ​\(Ms−1\),M^s−Ms−1⟩\\displaystyle=\\Psi\(\\widehat\{M\}\_\{s\}\)\-\\Psi\(M\_\{s\-1\}\)\-\\langle\\nabla\\Psi\(M\_\{s\-1\}\),\\widehat\{M\}\_\{s\}\-M\_\{s\-1\}\\rangle≤\|Ψ⁡\(M^s\)−Ψ⁡\(Ms−1\)\|\+\|⟨∇Ψ​\(Ms−1\),M^s−Ms−1⟩\|\\displaystyle\\leq\\left\|\\Psi\(\\widehat\{M\}\_\{s\}\)\-\\Psi\(M\_\{s\-1\}\)\\right\|\+\\left\|\\langle\\nabla\\Psi\(M\_\{s\-1\}\),\\widehat\{M\}\_\{s\}\-M\_\{s\-1\}\\rangle\\right\|≤2​∥M^s−Ms−1∥∗=2​\(1−β\)​∥gs−Ms−1∥∗,\\displaystyle\\leq 2\\lVert\\widehat\{M\}\_\{s\}\-M\_\{s\-1\}\\rVert\_\{\*\}=2\(1\-\\beta\)\\lVert g\_\{s\}\-M\_\{s\-1\}\\rVert\_\{\*\},where the last inequality follows from operator–nuclear duality and∥∇Ψ​\(M\)∥op=∥ℋhq​\(M/Gop\)∥op≤1\\lVert\\nabla\\Psi\(M\)\\rVert\_\{\\mathrm\{op\}\}=\\lVert\\mathcal\{H\}\_\{h\_\{q\}\}\(M/G\_\{\\mathrm\{op\}\}\)\\rVert\_\{\\mathrm\{op\}\}\\leq 1, which holds sincehq∈\[0,1\]h\_\{q\}\\in\[0,1\]\.

ForBΨ\(Ms∥M^s\)B\_\{\\Psi\}\(M\_\{s\}\\\|\\widehat\{M\}\_\{s\}\),[Lemma4\.6](https://arxiv.org/html/2608.26288#S4.Thmtheorem6)withLip⁡\(hq\)=Aq\\Lip\(h\_\{q\}\)=A^\{q\}gives

BΨ\(Ms∥M^s\)≤Aq2​Gop∥Ms−M^s∥F2=Aq​\(1−β\)22​Gop∥Gs−gs∥F2\.B\_\{\\Psi\}\(M\_\{s\}\\\|\\widehat\{M\}\_\{s\}\)\\leq\\frac\{A^\{q\}\}\{2G\_\{\\mathrm\{op\}\}\}\\lVert M\_\{s\}\-\\widehat\{M\}\_\{s\}\\rVert\_\{\\mathrm\{F\}\}^\{2\}=\\frac\{A^\{q\}\(1\-\\beta\)^\{2\}\}\{2G\_\{\\mathrm\{op\}\}\}\\lVert G\_\{s\}\-g\_\{s\}\\rVert\_\{\\mathrm\{F\}\}^\{2\}\.Taking the conditional expectation of[34](https://arxiv.org/html/2608.26288#A4.E34)and using𝔼⁡\[∥Gs−gs∥F2∣𝒬s\]≤σ2\\mathbb\{E\}\[\\lVert G\_\{s\}\-g\_\{s\}\\rVert\_\{\\mathrm\{F\}\}^\{2\}\\mid\\mathcal\{Q\}\_\{s\}\]\\leq\\sigma^\{2\}gives[33](https://arxiv.org/html/2608.26288#A4.E33), which completes the proof\. ∎

###### Lemma D\.3\.

Under[Assumptions2\.1](https://arxiv.org/html/2608.26288#S2.Thmtheorem1)and[5\.4](https://arxiv.org/html/2608.26288#S5.Thmtheorem4), for everys≥1s\\geq 1,

𝔼⁡\[∥gs−Ms−1∥∗\]≤βs−1​∥∇ℒ​\(W0\)∥∗\+2​Lop​D1−β\+σ​r⁡\(1−β\)1\+β\.\\mathbb\{E\}\\left\[\\lVert g\_\{s\}\-M\_\{s\-1\}\\rVert\_\{\*\}\\right\]\\leq\\beta^\{s\-1\}\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}\+\\frac\{2L\_\{\\mathrm\{op\}\}D\}\{1\-\\beta\}\+\\sigma\\sqrt\{\\frac\{r\(1\-\\beta\)\}\{1\+\\beta\}\}\.

###### Proof\.

Fors≥2s\\geq 2, sinceW~s=Ws−1\+us​Xs\\widetilde\{W\}\_\{s\}=W\_\{s\-1\}\+u\_\{s\}X\_\{s\},W~s−1=Ws−2\+us−1​Xs−1\\widetilde\{W\}\_\{s\-1\}=W\_\{s\-2\}\+u\_\{s\-1\}X\_\{s\-1\}, andWs−1=Ws−2\+Xs−1W\_\{s\-1\}=W\_\{s\-2\}\+X\_\{s\-1\}withus∈\[0,1\]u\_\{s\}\\in\[0,1\]in[Algorithm2](https://arxiv.org/html/2608.26288#algorithm2),W~s−W~s−1=\(1−us−1\)​Xs−1\+us​Xs\\widetilde\{W\}\_\{s\}\-\\widetilde\{W\}\_\{s\-1\}=\(1\-u\_\{s\-1\}\)X\_\{s\-1\}\+u\_\{s\}X\_\{s\}\. Since∥Xt∥op≤D\\lVert X\_\{t\}\\rVert\_\{\\mathrm\{op\}\}\\leq D, this and[Assumption5\.4](https://arxiv.org/html/2608.26288#S5.Thmtheorem4)give

∥W~s−W~s−1∥op≤2​D,∥gs−gs−1∥∗≤2​Lop​D\.\\lVert\\widetilde\{W\}\_\{s\}\-\\widetilde\{W\}\_\{s\-1\}\\rVert\_\{\\mathrm\{op\}\}\\leq 2D,\\qquad\\lVert g\_\{s\}\-g\_\{s\-1\}\\rVert\_\{\*\}\\leq 2L\_\{\\mathrm\{op\}\}D\.\(35\)The definition ofMs−1M\_\{s\-1\}andGj=gj\+\(Gj−gj\)G\_\{j\}=g\_\{j\}\+\(G\_\{j\}\-g\_\{j\}\)give

gs−Ms−1=\(gs−\(1−β\)​∑j=1s−1βs−1−j​gj\)−\(1−β\)​∑j=1s−1βs−1−j​\(Gj−gj\)\.g\_\{s\}\-M\_\{s\-1\}=\\left\(g\_\{s\}\-\(1\-\\beta\)\\sum\_\{j=1\}^\{s\-1\}\\beta^\{s\-1\-j\}g\_\{j\}\\right\)\-\(1\-\\beta\)\\sum\_\{j=1\}^\{s\-1\}\\beta^\{s\-1\-j\}\(G\_\{j\}\-g\_\{j\}\)\.\(36\)The first term of[36](https://arxiv.org/html/2608.26288#A4.E36)can be rewritten as

gs−\(1−β\)​∑j=1s−1βs−1−j​gj=βs−1​g1\+∑j=2sβs−j​\(gj−gj−1\)\.g\_\{s\}\-\(1\-\\beta\)\\sum\_\{j=1\}^\{s\-1\}\\beta^\{s\-1\-j\}g\_\{j\}=\\beta^\{s\-1\}g\_\{1\}\+\\sum\_\{j=2\}^\{s\}\\beta^\{s\-j\}\(g\_\{j\}\-g\_\{j\-1\}\)\.SinceX1=0X\_\{1\}=0we haveW~1=W0\\widetilde\{W\}\_\{1\}=W\_\{0\}andg1=∇ℒ​\(W0\)g\_\{1\}=\\nabla\\mathcal\{L\}\(W\_\{0\}\), so[35](https://arxiv.org/html/2608.26288#A4.E35)yields

‖gs−\(1−β\)​∑j=1s−1βs−1−j​gj‖∗\\displaystyle\\left\\lVert g\_\{s\}\-\(1\-\\beta\)\\sum\_\{j=1\}^\{s\-1\}\\beta^\{s\-1\-j\}g\_\{j\}\\right\\rVert\_\{\*\}≤βs−1​∥∇ℒ​\(W0\)∥∗\+2​Lop​D​∑j=2sβs−j\\displaystyle\\leq\\beta^\{s\-1\}\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}\+2L\_\{\\mathrm\{op\}\}D\\sum\_\{j=2\}^\{s\}\\beta^\{s\-j\}≤βs−1​∥∇ℒ​\(W0\)∥∗\+2​Lop​D1−β\.\\displaystyle\\leq\\beta^\{s\-1\}\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}\+\\frac\{2L\_\{\\mathrm\{op\}\}D\}\{1\-\\beta\}\.\(37\)For the second term of[36](https://arxiv.org/html/2608.26288#A4.E36),𝔼⁡\[∥Gs−gs∥F2∣𝒬s\]≤σ2\\mathbb\{E\}\[\\lVert G\_\{s\}\-g\_\{s\}\\rVert\_\{\\mathrm\{F\}\}^\{2\}\\mid\\mathcal\{Q\}\_\{s\}\]\\leq\\sigma^\{2\}and𝔼⁡\[Gs−gs∣𝒬s\]=0\\mathbb\{E\}\[G\_\{s\}\-g\_\{s\}\\mid\\mathcal\{Q\}\_\{s\}\]=0give

𝔼⁡\[‖\(1−β\)​∑j=1s−1βs−1−j​\(Gj−gj\)‖F2\]\\displaystyle\\mathbb\{E\}\\left\[\\left\\lVert\(1\-\\beta\)\\sum\_\{j=1\}^\{s\-1\}\\beta^\{s\-1\-j\}\(G\_\{j\}\-g\_\{j\}\)\\right\\rVert\_\{\\mathrm\{F\}\}^\{2\}\\right\]=\(1−β\)2​∑j=1s−1β2​\(s−1−j\)​𝔼​\[∥Gj−gj∥F2\]\\displaystyle=\(1\-\\beta\)^\{2\}\\sum\_\{j=1\}^\{s\-1\}\\beta^\{2\(s\-1\-j\)\}\\mathbb\{E\}\\left\[\\lVert G\_\{j\}\-g\_\{j\}\\rVert\_\{\\mathrm\{F\}\}^\{2\}\\right\]≤1−β1\+β​σ2\.\\displaystyle\\leq\\frac\{1\-\\beta\}\{1\+\\beta\}\\sigma^\{2\}\.Thus, Jensen’s inequality and∥Z∥∗≤r​∥Z∥F\\lVert Z\\rVert\_\{\*\}\\leq\\sqrt\{r\}\\lVert Z\\rVert\_\{\\mathrm\{F\}\}give

𝔼⁡\[‖\(1−β\)​∑j=1s−1βs−1−j​\(Gj−gj\)‖∗\]≤σ​r⁡\(1−β\)1\+β\.\\mathbb\{E\}\\left\[\\left\\lVert\(1\-\\beta\)\\sum\_\{j=1\}^\{s\-1\}\\beta^\{s\-1\-j\}\(G\_\{j\}\-g\_\{j\}\)\\right\\rVert\_\{\*\}\\right\]\\leq\\sigma\\sqrt\{\\frac\{r\(1\-\\beta\)\}\{1\+\\beta\}\}\.\(38\)Combining[36](https://arxiv.org/html/2608.26288#A4.E36),[37](https://arxiv.org/html/2608.26288#A4.E37), and[38](https://arxiv.org/html/2608.26288#A4.E38)completes the proof\. ∎

###### Proof of[Theorem5\.6](https://arxiv.org/html/2608.26288#S5.Thmtheorem6)\.

Ifε\>32​r​Γ\\varepsilon\>\\frac\{3\}\{2\}\\sqrt\{r\}\\,\\Gamma, then Jensen’s inequality and[3](https://arxiv.org/html/2608.26288#S2.E3)of[Assumption2\.1](https://arxiv.org/html/2608.26288#S2.Thmtheorem1)imply that every pointWWsatisfies

∥∇ℒ​\(W\)∥∗≤r​∥∇ℒ​\(W\)∥F≤r​Γ<23​ε\.\\lVert\\nabla\\mathcal\{L\}\(W\)\\rVert\_\{\*\}\\leq\\sqrt\{r\}\\,\\lVert\\nabla\\mathcal\{L\}\(W\)\\rVert\_\{\\mathrm\{F\}\}\\leq\\sqrt\{r\}\\,\\Gamma<\\frac\{2\}\{3\}\\varepsilon\.Consequently,[29](https://arxiv.org/html/2608.26288#S5.E29)holds in this case\.

It remains to considerε≤32​r​Γ\\varepsilon\\leq\\frac\{3\}\{2\}\\sqrt\{r\}\\,\\Gamma\. LetΨ≔Φ~hq,Gop\\Psi\\coloneqq\\widetilde\{\\Phi\}\_\{h\_\{q\},G\_\{\\mathrm\{op\}\}\}for simplicity\. The choiceCs=GopC\_\{s\}=G\_\{\\mathrm\{op\}\}satisfiesCs\+1≥β​CsC\_\{s\+1\}\\geq\\beta C\_\{s\}, so[14](https://arxiv.org/html/2608.26288#S4.E14)of[Theorem4\.2](https://arxiv.org/html/2608.26288#S4.Thmtheorem2)applies withh=hqh=h\_\{q\}\. UsingΔ⁡\(hq\)≤A−q\\Delta\(h\_\{q\}\)\\leq A^\{\-q\}from[Lemma5\.2](https://arxiv.org/html/2608.26288#S5.Thmtheorem2)andRegt\[β\]⁡\(D\)=D​Regt\[β\]⁡\(1\)\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(D\)=D\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(1\), dividing byDDand taking expectations gives

𝔼⁡\[Regt\[β\]⁡\(1\)\]\\displaystyle\\mathbb\{E\}\[\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(1\)\]≤r​Gop\(1−β\)​Aq\+11−β∑s=1tβt−s𝔼\[BΨ\(Ms∥Ms−1\)\]\\displaystyle\\leq\\frac\{rG\_\{\\mathrm\{op\}\}\}\{\(1\-\\beta\)A^\{q\}\}\+\\frac\{1\}\{1\-\\beta\}\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\\mathbb\{E\}\\left\[B\_\{\\Psi\}\(M\_\{s\}\\\|M\_\{s\-1\}\)\\right\]≤r​Gop\(1−β\)​Aq\+Aq​\(1−β\)​σ22​Gop​∑s=1tβt−s\+2​∑s=1tβt−s​𝔼​\[∥gs−Ms−1∥∗\]\\displaystyle\\leq\\frac\{rG\_\{\\mathrm\{op\}\}\}\{\(1\-\\beta\)A^\{q\}\}\+\\frac\{A^\{q\}\(1\-\\beta\)\\sigma^\{2\}\}\{2G\_\{\\mathrm\{op\}\}\}\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\+2\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\\mathbb\{E\}\\left\[\\lVert g\_\{s\}\-M\_\{s\-1\}\\rVert\_\{\*\}\\right\]≤r​Gop\(1−β\)​Aq\+Aq​\(1−β\)​σ22​Gop​∑s=1tβt−s\\displaystyle\\leq\\frac\{rG\_\{\\mathrm\{op\}\}\}\{\(1\-\\beta\)A^\{q\}\}\+\\frac\{A^\{q\}\(1\-\\beta\)\\sigma^\{2\}\}\{2G\_\{\\mathrm\{op\}\}\}\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\+2∑s=1tβt−s\(βs−1∥∇ℒ\(W0\)∥∗\+2​Lop​D1−β\+σr⁡\(1−β\)1\+β\),\\displaystyle\\qquad\+2\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\\left\(\\beta^\{s\-1\}\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}\+\\frac\{2L\_\{\\mathrm\{op\}\}D\}\{1\-\\beta\}\+\\sigma\\sqrt\{\\frac\{r\(1\-\\beta\)\}\{1\+\\beta\}\}\\right\),where in the second inequality we used[LemmaD\.2](https://arxiv.org/html/2608.26288#A4.Thmtheorem2)and the tower property, and in the last inequality we used[LemmaD\.3](https://arxiv.org/html/2608.26288#A4.Thmtheorem3)\. Using∑s=1tβt−s≤1/\(1−β\)\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\\leq 1/\(1\-\\beta\)and∑s=1tβt−s​βs−1=t​βt−1\\sum\_\{s=1\}^\{t\}\\beta^\{t\-s\}\\beta^\{s\-1\}=t\\beta^\{t\-1\}, we further bound this as

𝔼⁡\[Regt\[β\]⁡\(1\)\]\\displaystyle\\mathbb\{E\}\[\\operatorname\{Reg\}^\{\[\\beta\]\}\_\{t\}\(1\)\]≤r​Gop\(1−β\)​Aq\+Aq​σ22​Gop\+2​t​βt−1​∥∇ℒ​\(W0\)∥∗\+4​Lop​D\(1−β\)2\+2​r​σ1−β2\.\\displaystyle\\leq\\frac\{rG\_\{\\mathrm\{op\}\}\}\{\(1\-\\beta\)A^\{q\}\}\+\\frac\{A^\{q\}\\sigma^\{2\}\}\{2G\_\{\\mathrm\{op\}\}\}\+2t\\beta^\{t\-1\}\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}\+\\frac\{4L\_\{\\mathrm\{op\}\}D\}\{\(1\-\\beta\)^\{2\}\}\+\\frac\{2\\sqrt\{r\}\\,\\sigma\}\{\\sqrt\{1\-\\beta^\{2\}\}\}\.\(39\)
The term2​t​βt−1​∥∇ℒ​\(W0\)∥∗2t\\beta^\{t\-1\}\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}contributes to the bound of[Lemma3\.1](https://arxiv.org/html/2608.26288#S3.Thmtheorem1)as

1T​\(2​T​βT−1\+2​\(1−β\)​∑t=1T−1t​βt−1\)​∥∇ℒ​\(W0\)∥∗\\displaystyle\\frac\{1\}\{T\}\\left\(2T\\beta^\{T\-1\}\+2\(1\-\\beta\)\\sum\_\{t=1\}^\{T\-1\}t\\beta^\{t\-1\}\\right\)\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}≤1T​\(21−β\+21−β\)​∥∇ℒ​\(W0\)∥∗=4​∥∇ℒ​\(W0\)∥∗T⁡\(1−β\),\\displaystyle\\leq\\frac\{1\}\{T\}\\left\(\\frac\{2\}\{1\-\\beta\}\+\\frac\{2\}\{1\-\\beta\}\\right\)\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}=\\frac\{4\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}\}\{T\(1\-\\beta\)\},where the inequality usesT⁡\(1−β\)​βT−1≤\(1−β\)​∑t=1Tβt−1=1−βT≤1T\(1\-\\beta\)\\beta^\{T\-1\}\\leq\(1\-\\beta\)\\sum\_\{t=1\}^\{T\}\\beta^\{t\-1\}=1\-\\beta^\{T\}\\leq 1and∑t≥1t​βt−1≤\(1−β\)−2\\sum\_\{t\\geq 1\}t\\beta^\{t\-1\}\\leq\(1\-\\beta\)^\{\-2\}\.

Setρ≔ε/\(12​Lop\)\\rho\\coloneqq\\varepsilon/\(12L\_\{\\mathrm\{op\}\}\), so thatD=\(1−β\)​ρ/\(4​β\)D=\(1\-\\beta\)\\rho/\(4\\beta\)\. Substituting[39](https://arxiv.org/html/2608.26288#A4.E39)into[Lemma3\.1](https://arxiv.org/html/2608.26288#S3.Thmtheorem1)and using\(1\+\(1−β\)​\(T−1\)\)/T=1−β\+β/T\(1\+\(1\-\\beta\)\(T\-1\)\)/T=1\-\\beta\+\\beta/Tgives

𝔼⁡\[∥∇ℒ​\(W¯τ\)∥∗\[ρ\]\]\\displaystyle\\mathbb\{E\}\\left\[\\lVert\\nabla\\mathcal\{L\}\(\\bar\{W\}\_\{\\tau\}\)\\rVert\_\{\*\}^\{\[\\rho\]\}\\right\]≤4​Δℒ\(1−β\)​ρ​T\+4​∥∇ℒ​\(W0\)∥∗T⁡\(1−β\)\\displaystyle\\leq\\frac\{4\\Delta\_\{\\mathcal\{L\}\}\}\{\(1\-\\beta\)\\rho T\}\+\\frac\{4\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}\}\{T\(1\-\\beta\)\}\+\(1−β\+βT\)​\(r​Gop\(1−β\)​Aq\+4​Lop​D\(1−β\)2\+3​r​σ1−β2\+Aq​σ22​Gop\)\.\\displaystyle\\qquad\+\\left\(1\-\\beta\+\\frac\{\\beta\}\{T\}\\right\)\\left\(\\frac\{rG\_\{\\mathrm\{op\}\}\}\{\(1\-\\beta\)A^\{q\}\}\+\\frac\{4L\_\{\\mathrm\{op\}\}D\}\{\(1\-\\beta\)^\{2\}\}\+\\frac\{3\\sqrt\{r\}\\,\\sigma\}\{\\sqrt\{1\-\\beta^\{2\}\}\}\+\\frac\{A^\{q\}\\sigma^\{2\}\}\{2G\_\{\\mathrm\{op\}\}\}\\right\)\.Then, using[Lemma5\.5](https://arxiv.org/html/2608.26288#S5.Thmtheorem5)and substitutingD=\(1−β\)​ρ/\(4​β\)D=\(1\-\\beta\)\\rho/\(4\\beta\)gives

𝔼⁡\[∥∇ℒ​\(W¯τ\)∥∗\]\\displaystyle\\mathbb\{E\}\\left\[\\lVert\\nabla\\mathcal\{L\}\(\\bar\{W\}\_\{\\tau\}\)\\rVert\_\{\*\}\\right\]≤4​Δℒ\(1−β\)​ρ​T\+4​∥∇ℒ​\(W0\)∥∗T⁡\(1−β\)\+\(1\+βT⁡\(1−β\)\)​r​GopAq\\displaystyle\\leq\\frac\{4\\Delta\_\{\\mathcal\{L\}\}\}\{\(1\-\\beta\)\\rho T\}\+\\frac\{4\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}\}\{T\(1\-\\beta\)\}\+\\left\(1\+\\frac\{\\beta\}\{T\(1\-\\beta\)\}\\right\)\\frac\{rG\_\{\\mathrm\{op\}\}\}\{A^\{q\}\}\+Lop​ρ​\(1\+1β\+1T⁡\(1−β\)\)\+3​r​σ​1−β\+β/T1−β2\+\(1−β\+βT\)​Aq​σ22​Gop\.\\displaystyle\\qquad\+L\_\{\\mathrm\{op\}\}\\rho\\left\(1\+\\frac\{1\}\{\\beta\}\+\\frac\{1\}\{T\(1\-\\beta\)\}\\right\)\+3\\sqrt\{r\}\\sigma\\frac\{1\-\\beta\+\\beta/T\}\{\\sqrt\{1\-\\beta^\{2\}\}\}\+\\left\(1\-\\beta\+\\frac\{\\beta\}\{T\}\\right\)\\frac\{A^\{q\}\\sigma^\{2\}\}\{2G\_\{\\mathrm\{op\}\}\}\.We next bound the six terms one by one\. The choices ofρ\\rhoandβ\\betagiveLop​ρ=ε/12L\_\{\\mathrm\{op\}\}\\rho=\\varepsilon/12and1/\(1−β\)=max⁡\{2,144​r​σ2/ε2\}≤2\+144​r​σ2/ε21/\(1\-\\beta\)=\\max\\\{2,144r\\sigma^\{2\}/\\varepsilon^\{2\}\\\}\\leq 2\+144r\\sigma^\{2\}/\\varepsilon^\{2\}\. Thus, the first term satisfies

4​Δℒ\(1−β\)​ρ​T\\displaystyle\\frac\{4\\Delta\_\{\\mathcal\{L\}\}\}\{\(1\-\\beta\)\\rho T\}=O⁡\(Lop​Δℒε​T\+r​σ2​Lop​Δℒε3​T\)\.\\displaystyle=O\\left\(\\frac\{L\_\{\\mathrm\{op\}\}\\Delta\_\{\\mathcal\{L\}\}\}\{\\varepsilon T\}\+\\frac\{r\\sigma^\{2\}L\_\{\\mathrm\{op\}\}\\Delta\_\{\\mathcal\{L\}\}\}\{\\varepsilon^\{3\}T\}\\right\)\.
For the second term, we first bound∥∇ℒ​\(W0\)∥∗\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}\. Applying the fundamental theorem of calculus along the segment fromWWtoW′W^\{\\prime\}, followed by operator–nuclear duality and[Assumption5\.4](https://arxiv.org/html/2608.26288#S5.Thmtheorem4), gives

ℒ⁡\(W′\)≤ℒ⁡\(W\)\+⟨∇ℒ​\(W\),W′−W⟩\+Lop2​∥W′−W∥op2\.\\mathcal\{L\}\(W^\{\\prime\}\)\\leq\\mathcal\{L\}\(W\)\+\\langle\\nabla\\mathcal\{L\}\(W\),W^\{\\prime\}\-W\\rangle\+\\frac\{L\_\{\\mathrm\{op\}\}\}\{2\}\\lVert W^\{\\prime\}\-W\\rVert\_\{\\mathrm\{op\}\}^\{2\}\.\(40\)TakeW=W0W=W\_\{0\}andW′=W0−∥∇ℒ​\(W0\)∥∗​polar⁡\(∇ℒ​\(W0\)\)/LopW^\{\\prime\}=W\_\{0\}\-\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}\\polar\(\\nabla\\mathcal\{L\}\(W\_\{0\}\)\)/L\_\{\\mathrm\{op\}\}\. Then⟨∇ℒ\(W0\),W′−W0⟩=−∥∇ℒ\(W0\)∥∗2/Lop\\langle\\nabla\\mathcal\{L\}\(W\_\{0\}\),W^\{\\prime\}\-W\_\{0\}\\rangle=\-\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}^\{2\}/L\_\{\\mathrm\{op\}\}and∥W′−W0∥op=∥∇ℒ​\(W0\)∥∗/Lop\\lVert W^\{\\prime\}\-W\_\{0\}\\rVert\_\{\\mathrm\{op\}\}=\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}/L\_\{\\mathrm\{op\}\}, so[40](https://arxiv.org/html/2608.26288#A4.E40)givesℒ⁡\(W′\)≤ℒ⁡\(W0\)−∥∇ℒ​\(W0\)∥∗2/\(2​Lop\)\\mathcal\{L\}\(W^\{\\prime\}\)\\leq\\mathcal\{L\}\(W\_\{0\}\)\-\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}^\{2\}/\(2L\_\{\\mathrm\{op\}\}\)\. Combining this withℒ⁡\(W′\)≥ℒ⁡\(W0\)−Δℒ\\mathcal\{L\}\(W^\{\\prime\}\)\\geq\\mathcal\{L\}\(W\_\{0\}\)\-\\Delta\_\{\\mathcal\{L\}\}yields∥∇ℒ​\(W0\)∥∗≤2​Lop​Δℒ≤ε\+Lop​Δℒ/ε\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}\\leq\\sqrt\{2L\_\{\\mathrm\{op\}\}\\Delta\_\{\\mathcal\{L\}\}\}\\leq\\varepsilon\+L\_\{\\mathrm\{op\}\}\\Delta\_\{\\mathcal\{L\}\}/\\varepsilonand then

4​∥∇ℒ​\(W0\)∥∗\(1−β\)​T\\displaystyle\\frac\{4\\lVert\\nabla\\mathcal\{L\}\(W\_\{0\}\)\\rVert\_\{\*\}\}\{\(1\-\\beta\)T\}≤4​2​Lop​ΔℒT​\(2\+144​r​σ2ε2\)=O⁡\(εT\+Lop​Δℒε​T\+r​σ2ε​T\+r​σ2​Lop​Δℒε3​T\)\.\\displaystyle\\leq\\frac\{4\\sqrt\{2L\_\{\\mathrm\{op\}\}\\Delta\_\{\\mathcal\{L\}\}\}\}\{T\}\\Big\(2\+\\frac\{144r\\sigma^\{2\}\}\{\\varepsilon^\{2\}\}\\Big\)=O\\left\(\\frac\{\\varepsilon\}\{T\}\+\\frac\{L\_\{\\mathrm\{op\}\}\\Delta\_\{\\mathcal\{L\}\}\}\{\\varepsilon T\}\+\\frac\{r\\sigma^\{2\}\}\{\\varepsilon T\}\+\\frac\{r\\sigma^\{2\}L\_\{\\mathrm\{op\}\}\\Delta\_\{\\mathcal\{L\}\}\}\{\\varepsilon^\{3\}T\}\\right\)\.
For the third term,Γ≤r​Gop\\Gamma\\leq\\sqrt\{r\}\\,G\_\{\\mathrm\{op\}\}andε≤32​r​Γ\\varepsilon\\leq\\frac\{3\}\{2\}\\sqrt\{r\}\\,\\Gammaimply12​r​Gop/ε≥8\>112rG\_\{\\mathrm\{op\}\}/\\varepsilon\\geq 8\>1\. Thus,q=⌈logA⁡\(12​r​Gop/ε\)⌉q=\\lceil\\log\_\{A\}\(12rG\_\{\\mathrm\{op\}\}/\\varepsilon\)\\rceiland12​r​Gop/ε≤Aq<12​A​r​Gop/ε12rG\_\{\\mathrm\{op\}\}/\\varepsilon\\leq A^\{q\}<12ArG\_\{\\mathrm\{op\}\}/\\varepsilon\. It follows that

\(1\+βT⁡\(1−β\)\)​r​GopAq\\displaystyle\\Big\(1\+\\frac\{\\beta\}\{T\(1\-\\beta\)\}\\Big\)\\frac\{rG\_\{\\mathrm\{op\}\}\}\{A^\{q\}\}≤ε12\+ε12​T​\(2\+144​r​σ2ε2\)=ε12\+O⁡\(εT\+r​σ2ε​T\)\.\\displaystyle\\leq\\frac\{\\varepsilon\}\{12\}\+\\frac\{\\varepsilon\}\{12T\}\\Big\(2\+\\frac\{144r\\sigma^\{2\}\}\{\\varepsilon^\{2\}\}\\Big\)=\\frac\{\\varepsilon\}\{12\}\+O\\left\(\\frac\{\\varepsilon\}\{T\}\+\\frac\{r\\sigma^\{2\}\}\{\\varepsilon T\}\\right\)\.
For the fourth term,1−β≤1/21\-\\beta\\leq 1/2implies1/β≤21/\\beta\\leq 2\. Together withLop​ρ=ε/12L\_\{\\mathrm\{op\}\}\\rho=\\varepsilon/12, this gives

Lop​ρ​\(1\+1β\+1T⁡\(1−β\)\)\\displaystyle L\_\{\\mathrm\{op\}\}\\rho\\Big\(1\+\\frac\{1\}\{\\beta\}\+\\frac\{1\}\{T\(1\-\\beta\)\}\\Big\)≤ε4\+ε12​T​\(2\+144​r​σ2ε2\)≤ε4\+O⁡\(εT\+r​σ2ε​T\)\.\\displaystyle\\leq\\frac\{\\varepsilon\}\{4\}\+\\frac\{\\varepsilon\}\{12T\}\\Big\(2\+\\frac\{144r\\sigma^\{2\}\}\{\\varepsilon^\{2\}\}\\Big\)\\leq\\frac\{\\varepsilon\}\{4\}\+O\\left\(\\frac\{\\varepsilon\}\{T\}\+\\frac\{r\\sigma^\{2\}\}\{\\varepsilon T\}\\right\)\.
For the fifth term, the definition ofβ\\betaensures3​r​σ​1−β≤ε/43\\sqrt\{r\}\\sigma\\sqrt\{1\-\\beta\}\\leq\\varepsilon/4\. Moreover,1−β2≥1−β\\sqrt\{1\-\\beta^\{2\}\}\\geq\\sqrt\{1\-\\beta\},1/1−β≤2\+12​r​σ/ε1/\\sqrt\{1\-\\beta\}\\leq\\sqrt\{2\}\+12\\sqrt\{r\}\\sigma/\\varepsilon, andr​σ2≤\(ε\+r​σ2/ε\)/2\\sqrt\{r\\sigma^\{2\}\}\\leq\(\\varepsilon\+r\\sigma^\{2\}/\\varepsilon\)/2give

3​r​σ​1−β\+β/T1−β2\\displaystyle 3\\sqrt\{r\}\\sigma\\frac\{1\-\\beta\+\\beta/T\}\{\\sqrt\{1\-\\beta^\{2\}\}\}≤3​r​σ​1−β\+3​r​σT​1−β≤ε4\+O⁡\(εT\+r​σ2ε​T\)\.\\displaystyle\\leq 3\\sqrt\{r\}\\sigma\\sqrt\{1\-\\beta\}\+\\frac\{3\\sqrt\{r\}\\sigma\}\{T\\sqrt\{1\-\\beta\}\}\\leq\\frac\{\\varepsilon\}\{4\}\+O\\left\(\\frac\{\\varepsilon\}\{T\}\+\\frac\{r\\sigma^\{2\}\}\{\\varepsilon T\}\\right\)\.
For the sixth term,\(1−β\)​σ2≤ε2/\(144​r\)\(1\-\\beta\)\\sigma^\{2\}\\leq\\varepsilon^\{2\}/\(144r\)and the upper bound onAqA^\{q\}above give

\(1−β\+βT\)​Aq​σ22​Gop\\displaystyle\\Big\(1\-\\beta\+\\frac\{\\beta\}\{T\}\\Big\)\\frac\{A^\{q\}\\sigma^\{2\}\}\{2G\_\{\\mathrm\{op\}\}\}≤ε12\+O⁡\(r​σ2ε​T\)\.\\displaystyle\\leq\\frac\{\\varepsilon\}\{12\}\+O\\left\(\\frac\{r\\sigma^\{2\}\}\{\\varepsilon T\}\\right\)\.Therefore,

𝔼⁡\[∥∇ℒ​\(W¯τ\)∥∗\]\\displaystyle\\mathbb\{E\}\\left\[\\lVert\\nabla\\mathcal\{L\}\(\\bar\{W\}\_\{\\tau\}\)\\rVert\_\{\*\}\\right\]≤23​ε\+O⁡\(εT\+Lop​Δℒε​T\+r​σ2ε​T\+r​σ2​Lop​Δℒε3​T\)\.\\displaystyle\\leq\\frac\{2\}\{3\}\\varepsilon\+O\\left\(\\frac\{\\varepsilon\}\{T\}\+\\frac\{L\_\{\\mathrm\{op\}\}\\Delta\_\{\\mathcal\{L\}\}\}\{\\varepsilon T\}\+\\frac\{r\\sigma^\{2\}\}\{\\varepsilon T\}\+\\frac\{r\\sigma^\{2\}L\_\{\\mathrm\{op\}\}\\Delta\_\{\\mathcal\{L\}\}\}\{\\varepsilon^\{3\}T\}\\right\)\.This gives[29](https://arxiv.org/html/2608.26288#S5.E29), and requiring the1/T1/Tterms to be at mostε/3\\varepsilon/3gives[30](https://arxiv.org/html/2608.26288#S5.E30), which completes the proof\. ∎

## Appendix EDeferred details on the FTRL interpretation \([Section5\.4](https://arxiv.org/html/2608.26288#S5.SS4)\)

For the FTRL interpretation, we compute the Fenchel conjugate of the smoothed potentialΦ~h,C\\widetilde\{\\Phi\}\_\{h,C\}and the regularizer it induces, and then specialize the results to the Newton–Schulz maphqh\_\{q\}\. The regularizer is a sum of the scalar conjugate over the singular values\.

### E\.1General spectral maphh\(proof of[Theorem5\.7](https://arxiv.org/html/2608.26288#S5.Thmtheorem7)\)

###### Lemma E\.1\.

Extendϕh\\phi\_\{h\}to a proper convex function onℝ\\mathbb\{R\}by settingϕh​\(x\)=\+∞\\phi\_\{h\}\(x\)=\+\\inftyforx<0x<0, and letϕh∗​\(a\)≔supx≥0\{a​x−ϕh​\(x\)\}\\phi\_\{h\}^\{\*\}\(a\)\\coloneqq\\sup\_\{x\\geq 0\}\\\{ax\-\\phi\_\{h\}\(x\)\\\}be its Fenchel conjugate\. Under[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1),ϕh∗​\(a\)<∞\\phi\_\{h\}^\{\*\}\(a\)<\\inftyif and only ifa≤1a\\leq 1\.

###### Proof\.

Fora≤1a\\leq 1andx≥0x\\geq 0,

a​x−ϕh​\(x\)≤x−ϕh​\(x\)=∫0x\(1−h⁡\(u\)\)​𝑑u≤∫0∞\(1−h⁡\(u\)\)​𝑑u=Δ⁡\(h\),ax\-\\phi\_\{h\}\(x\)\\leq x\-\\phi\_\{h\}\(x\)=\\int\_\{0\}^\{x\}\(1\-h\(u\)\)\\,\\mathrm\{d\}u\\leq\\int\_\{0\}^\{\\infty\}\(1\-h\(u\)\)\\,\\mathrm\{d\}u=\\Delta\(h\),soϕh∗​\(a\)≤Δ⁡\(h\)<∞\\phi\_\{h\}^\{\*\}\(a\)\\leq\\Delta\(h\)<\\infty\. Fora\>1a\>1, the boundϕh​\(x\)≤x\\phi\_\{h\}\(x\)\\leq xgivesa​x−ϕh​\(x\)≥\(a−1\)​x→∞ax\-\\phi\_\{h\}\(x\)\\geq\(a\-1\)x\\to\\inftyasx→∞x\\to\\infty, soϕh∗​\(a\)=\+∞\\phi\_\{h\}^\{\*\}\(a\)=\+\\infty, which completes the proof\. ∎

Lifting the scalar conjugate to matrices via[LemmaB\.3](https://arxiv.org/html/2608.26288#A2.Thmtheorem3)gives the Fenchel conjugate of the smoothed potential\.

###### Lemma E\.2\.

Under[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1), for everyC\>0C\>0, the Fenchel conjugate ofΦ~h,C\\widetilde\{\\Phi\}\_\{h,C\}is

Φ~h,C∗​\(W\)=C​∑i=1rϕh∗​\(σi​\(W\)\)\.\\widetilde\{\\Phi\}\_\{h,C\}^\{\*\}\(W\)=C\\sum\_\{i=1\}^\{r\}\\phi\_\{h\}^\{\*\}\(\\sigma\_\{i\}\(W\)\)\.

###### Proof\.

Apply the Fenchel conjugate formula for singular\-value functions \([LemmaB\.3](https://arxiv.org/html/2608.26288#A2.Thmtheorem3)\) toϕ⁡\(x\)≔C​ϕh​\(x/C\)\\phi\(x\)\\coloneqq C\\phi\_\{h\}\(x/C\)\. This expresses the Fenchel conjugate ofΦ~h,C\\widetilde\{\\Phi\}\_\{h,C\}asW↦∑i=1rϕ∗​\(σi​\(W\)\)W\\mapsto\\sum\_\{i=1\}^\{r\}\\phi^\{\*\}\(\\sigma\_\{i\}\(W\)\)\. The change of variablesx=C​ux=Cugivesϕ∗​\(a\)=supx≥0\{a​x−C​ϕh​\(x/C\)\}=C​ϕh∗​\(a\)\\phi^\{\*\}\(a\)=\\sup\_\{x\\geq 0\}\\\{ax\-C\\phi\_\{h\}\(x/C\)\\\}=C\\phi\_\{h\}^\{\*\}\(a\), which completes the proof\. ∎

We are now ready to prove[Theorem5\.7](https://arxiv.org/html/2608.26288#S5.Thmtheorem7)\.

###### Proof of[Theorem5\.7](https://arxiv.org/html/2608.26288#S5.Thmtheorem7)\.

By[17](https://arxiv.org/html/2608.26288#S4.E17), it holds that

Xth=−Dℋh\(Mt−1Ct\)=−D∇Φ~h,Ct\(Mt−1\)\.X\_\{t\}^\{h\}=\-D\\mathcal\{H\}\_\{h\}\\left\(\\frac\{M\_\{t\-1\}\}\{C\_\{t\}\}\\right\)=\-D\\nabla\\widetilde\{\\Phi\}\_\{h,C\_\{t\}\}\(M\_\{t\-1\}\)\.It remains to show thatXthX\_\{t\}^\{h\}minimizes the FTRL objective\. The definition ofMt−1M\_\{t\-1\}givesMt−1=\(1−β\)​βt−1​∑s=1t−1β−s​GsM\_\{t\-1\}=\(1\-\\beta\)\\beta^\{t\-1\}\\sum\_\{s=1\}^\{t\-1\}\\beta^\{\-s\}G\_\{s\}\. Hence the objective in[31](https://arxiv.org/html/2608.26288#S5.E31)is\(⟨Mt−1,X⟩\+Rh,Ct​\(X\)\)/\(\(1−β\)​βt−1\)\\big\(\\langle M\_\{t\-1\},X\\rangle\+R\_\{h,C\_\{t\}\}\(X\)\\big\)/\\big\(\(1\-\\beta\)\\beta^\{t\-1\}\\big\)\. SubstitutingX=−D​WX=\-DWand usingRh,Ct​\(X\)=D​Φ~h,Ct∗​\(X/D\)R\_\{h,C\_\{t\}\}\(X\)=D\\widetilde\{\\Phi\}\_\{h,C\_\{t\}\}^\{\*\}\(X/D\)together with the evenness ofΦ~h,Ct∗\\widetilde\{\\Phi\}\_\{h,C\_\{t\}\}^\{\*\}\(which holds sinceσi​\(−W\)=σi​\(W\)\\sigma\_\{i\}\(\-W\)=\\sigma\_\{i\}\(W\)\) gives

⟨Mt−1,X⟩\+Rh,Ct​\(X\)=−D⁡\(⟨Mt−1,W⟩−Φ~h,Ct∗​\(W\)\)\.\\langle M\_\{t\-1\},X\\rangle\+R\_\{h,C\_\{t\}\}\(X\)=\-D\\left\(\\langle M\_\{t\-1\},W\\rangle\-\\widetilde\{\\Phi\}\_\{h,C\_\{t\}\}^\{\*\}\(W\)\\right\)\.Thus minimizing the left\-hand side over∥X∥op≤D\\lVert X\\rVert\_\{\\mathrm\{op\}\}\\leq Dis the same as maximizing⟨Mt−1,W⟩−Φ~h,Ct∗​\(W\)\\langle M\_\{t\-1\},W\\rangle\-\\widetilde\{\\Phi\}\_\{h,C\_\{t\}\}^\{\*\}\(W\)over∥W∥op≤1\\lVert W\\rVert\_\{\\mathrm\{op\}\}\\leq 1\. By the Fenchel–Young inequality,

⟨Mt−1,W⟩−Φ~h,Ct∗​\(W\)≤Φ~h,Ct​\(Mt−1\),\\langle M\_\{t\-1\},W\\rangle\-\\widetilde\{\\Phi\}\_\{h,C\_\{t\}\}^\{\*\}\(W\)\\leq\\widetilde\{\\Phi\}\_\{h,C\_\{t\}\}\(M\_\{t\-1\}\),with equality if and only ifW=∇Φ~h,Ct​\(Mt−1\)W=\\nabla\\widetilde\{\\Phi\}\_\{h,C\_\{t\}\}\(M\_\{t\-1\}\)\. The minimizer is thereforeX=−D∇Φ~h,Ct\(Mt−1\)=XthX=\-D\\nabla\\widetilde\{\\Phi\}\_\{h,C\_\{t\}\}\(M\_\{t\-1\}\)=X\_\{t\}^\{h\}, which completes the proof\. ∎

##### Closed form of the regularizer\.

The regularizer[32](https://arxiv.org/html/2608.26288#S5.E32)is a sum of the scalar conjugateϕh∗\\phi\_\{h\}^\{\*\}over the singular values\. In terms of the generalized inverseh−1​\(v\)≔inf\{x≥0:h⁡\(x\)≥v\}h^\{\-1\}\(v\)\\coloneqq\\inf\\\{x\\geq 0:h\(x\)\\geq v\\\}withinf∅≔\+∞\\inf\\emptyset\\coloneqq\+\\infty, the scalar conjugate is

ϕh∗​\(a\)=\{0,a≤0,∫0ah−1​\(v\)​dv,0≤a≤1,\+∞,a\>1\.\\phi\_\{h\}^\{\*\}\(a\)=\\begin\{cases\}0,&a\\leq 0,\\\\\[2\.84526pt\] \\displaystyle\\int\_\{0\}^\{a\}h^\{\-1\}\(v\)\\,\\mathrm\{d\}v,&0\\leq a\\leq 1,\\\\\[8\.53581pt\] \+\\infty,&a\>1\.\\end\{cases\}\(41\)Indeed, fora≤0a\\leq 0the mapx↦a​x−ϕh​\(x\)x\\mapsto ax\-\\phi\_\{h\}\(x\)is nonincreasing, soϕh∗​\(a\)=0\\phi\_\{h\}^\{\*\}\(a\)=0, and[LemmaE\.1](https://arxiv.org/html/2608.26288#A5.Thmtheorem1)givesϕh∗​\(a\)=\+∞\\phi\_\{h\}^\{\*\}\(a\)=\+\\inftyfora\>1a\>1\. Fora∈\[0,1\]a\\in\[0,1\], the integrand ofa​x−ϕh​\(x\)=∫0x\(a−h⁡\(u\)\)​𝑑uax\-\\phi\_\{h\}\(x\)=\\int\_\{0\}^\{x\}\(a\-h\(u\)\)\\,\\mathrm\{d\}uis positive exactly whenu<h−1​\(a\)u<h^\{\-1\}\(a\), so

ϕh∗​\(a\)=∫0h−1​\(a\)\(a−h⁡\(u\)\)​𝑑u=∫0ah−1​\(v\)​𝑑v,\\phi\_\{h\}^\{\*\}\(a\)=\\int\_\{0\}^\{h^\{\-1\}\(a\)\}\(a\-h\(u\)\)\\,\\mathrm\{d\}u=\\int\_\{0\}^\{a\}h^\{\-1\}\(v\)\\,\\mathrm\{d\}v,where the second equality exchanges the order of integration over\{\(u,v\):h⁡\(u\)<v≤a\}\\\{\(u,v\):h\(u\)<v\\leq a\\\}\. Takinga=1a=1gives

ϕh∗​\(1\)=∫0h−1​\(1\)\(1−h⁡\(u\)\)​𝑑u=∫0∞\(1−h⁡\(u\)\)​𝑑u=Δ⁡\(h\),\\phi\_\{h\}^\{\*\}\(1\)=\\int\_\{0\}^\{h^\{\-1\}\(1\)\}\(1\-h\(u\)\)\\,\\mathrm\{d\}u=\\int\_\{0\}^\{\\infty\}\(1\-h\(u\)\)\\,\\mathrm\{d\}u=\\Delta\(h\),where the second equality uses1−h⁡\(u\)=01\-h\(u\)=0foru\>h−1​\(1\)u\>h^\{\-1\}\(1\)\. Thus, sinceϕh∗\\phi\_\{h\}^\{\*\}is nondecreasing,0≤ϕh∗​\(a\)≤Δ⁡\(h\)0\\leq\\phi\_\{h\}^\{\*\}\(a\)\\leq\\Delta\(h\)for everya∈\[0,1\]a\\in\[0,1\]\.

Figure 2:The scalar contributionϕhq∗​\(a\)\\phi\_\{h\_\{q\}\}^\{\*\}\(a\)to the FTRL regularizer for depthsq=0,…,3q=0,\\ldots,3, wherea=σi​\(X\)/D∈\[0,1\]a=\\sigma\_\{i\}\(X\)/D\\in\[0,1\]\. At depth zero,ϕh0∗​\(a\)=a2/2\\phi\_\{h\_\{0\}\}^\{\*\}\(a\)=a^\{2\}/2\. The curves are pointwise nonincreasing inqq, each marked endpoint equalsϕhq∗​\(1\)=Δ⁡\(hq\)\\phi\_\{h\_\{q\}\}^\{\*\}\(1\)=\\Delta\(h\_\{q\}\), and these endpoint values converge to zero asq→∞q\\to\\infty\.

### E\.2Specialization to Newton–Schulzhqh\_\{q\}

WriteY=Mt/Gop=Udiag\(xi\)V⊤Y=M\_\{t\}/G\_\{\\mathrm\{op\}\}=U\\diag\(x\_\{i\}\)V^\{\\top\}for a thin singular value decomposition, withxi∈\[0,1\]x\_\{i\}\\in\[0,1\]because∥Y∥op≤1\\lVert Y\\rVert\_\{\\mathrm\{op\}\}\\leq 1\. Then\(YY⊤\)kY=Udiag\(xi2​k\+1\)V⊤\(YY^\{\\top\}\)^\{k\}Y=U\\diag\(x\_\{i\}^\{2k\+1\}\)V^\{\\top\}\. Using this fork=0,1,2k=0,1,2, we see that the Newton–Schulz step of Line[1](https://arxiv.org/html/2608.26288#algorithm1)acts as

158Y−54\(YY⊤\)Y\+38\(YY⊤\)2Y=Udiag\(f\(xi\)\)V⊤\.\\frac\{15\}\{8\}Y\-\\frac\{5\}\{4\}\(YY^\{\\top\}\)Y\+\\frac\{3\}\{8\}\(YY^\{\\top\}\)^\{2\}Y=U\\diag\\left\(f\(x\_\{i\}\)\\right\)V^\{\\top\}\.Sinceffmaps\[0,1\]\[0,1\]into itself, the singular values stay in\[0,1\]\[0,1\], soqqsteps replace eachxix\_\{i\}byf∘q​\(xi\)=hq​\(xi\)f^\{\\circ q\}\(x\_\{i\}\)=h\_\{q\}\(x\_\{i\}\)from[6](https://arxiv.org/html/2608.26288#S2.E6), and therefore theqq\-step iteration equals the singular\-value mapℋhq​\(Y\)\\mathcal\{H\}\_\{h\_\{q\}\}\(Y\)of[7](https://arxiv.org/html/2608.26288#S2.E7), as stated in[Section2\.2](https://arxiv.org/html/2608.26288#S2.SS2)\.

For the constant normalizationCt=GopC\_\{t\}=G\_\{\\mathrm\{op\}\},[Theorem5\.7](https://arxiv.org/html/2608.26288#S5.Thmtheorem7)gives

Xt=−D∇Φ~hq,Gop\(Mt−1\)∈arg​min∥X∥op≤D\{⟨∑s=1t−1β−sGs,X⟩\+Rhq,Gop​\(X\)\(1−β\)​βt−1\}\.X\_\{t\}=\-D\\nabla\\widetilde\{\\Phi\}\_\{h\_\{q\},G\_\{\\mathrm\{op\}\}\}\(M\_\{t\-1\}\)\\in\\argmin\_\{\\lVert X\\rVert\_\{\\mathrm\{op\}\}\\leq D\}\\left\\\{\\left\\langle\\sum\_\{s=1\}^\{t\-1\}\\beta^\{\-s\}G\_\{s\},X\\right\\rangle\+\\frac\{R\_\{h\_\{q\},G\_\{\\mathrm\{op\}\}\}\(X\)\}\{\(1\-\\beta\)\\beta^\{t\-1\}\}\\right\\\}\.Thus the update that appliesqqNewton–Schulz steps to the momentum is the FTRL update for the discounted linear losses\.

##### Vanishing regularizer asq→∞q\\to\\infty\.

By the closed form[41](https://arxiv.org/html/2608.26288#A5.E41),ϕhq∗\\phi\_\{h\_\{q\}\}^\{\*\}is nondecreasing with0≤ϕhq∗​\(a\)≤ϕhq∗​\(1\)=Δ⁡\(hq\)0\\leq\\phi\_\{h\_\{q\}\}^\{\*\}\(a\)\\leq\\phi\_\{h\_\{q\}\}^\{\*\}\(1\)=\\Delta\(h\_\{q\}\)on\[0,1\]\[0,1\]\. SinceΔ⁡\(hq\)→0\\Delta\(h\_\{q\}\)\\to 0asq→∞q\\to\\inftyby[25](https://arxiv.org/html/2608.26288#S5.E25)of[Lemma5\.2](https://arxiv.org/html/2608.26288#S5.Thmtheorem2), the FTRL update approaches the follow\-the\-leader action−D​polar⁡\(Mt−1\)\-D\\polar\(M\_\{t\-1\}\)of exact\-polar Muon\.[Figure2](https://arxiv.org/html/2608.26288#A5.F2)showsϕhq∗\\phi\_\{h\_\{q\}\}^\{\*\}for depthsq=0,…,3q=0,\\ldots,3\.

## Appendix FGuarantees for other spectral maps

[Section5](https://arxiv.org/html/2608.26288#S5)focuses on the finite Newton–Schulz map, while the analysis of[Section4](https://arxiv.org/html/2608.26288#S4)applies to any spectral map satisfying[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1)\. We illustrate this generality using a recently proposed smooth relaxation of the polar map\([Mustafi et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib43);[Feoktistov et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib21)\)as an example\. The relaxation inherits the stationarity guarantees for nonsmooth nonconvex objectives from[Sections3](https://arxiv.org/html/2608.26288#S3)and[4](https://arxiv.org/html/2608.26288#S4), where the bound balances the approximation errorΔ⁡\(h\)\\Delta\(h\)against the Lipschitz constantLip⁡\(h\)\\Lip\(h\)as for finite Newton–Schulz\. A smallerΔ⁡\(h\)\\Delta\(h\)forces a largerLip⁡\(h\)\\Lip\(h\), and we show that this tradeoff is unavoidable for every map satisfying[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1)\.

### F\.1A smooth relaxation of the polar map

For a smoothing parametera\>0a\>0, define

h~a​\(x\)≔a​x1\+a2​x2,x∈\[0,∞\)\.\\widetilde\{h\}\_\{a\}\(x\)\\coloneqq\\frac\{ax\}\{\\sqrt\{1\+a^\{2\}x^\{2\}\}\},\\qquad x\\in\[0,\\infty\)\.This smooth approximation of the polar map is used in recent work\([Feoktistov et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib21);[Mustafi et al\., 2026](https://arxiv.org/html/2608.26288#bib.bib43)\)\. We first check thath~a\\widetilde\{h\}\_\{a\}satisfies[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1)\. It is continuous withh~a​\(0\)=0\\widetilde\{h\}\_\{a\}\(0\)=0, and its derivative

h~a′​\(x\)=a\(1\+a2​x2\)3/2\\widetilde\{h\}\_\{a\}^\{\\prime\}\(x\)=\\frac\{a\}\{\\left\(1\+a^\{2\}x^\{2\}\\right\)^\{3/2\}\}is positive, soh~a\\widetilde\{h\}\_\{a\}is strictly increasing, with0≤h~a​\(x\)<10\\leq\\widetilde\{h\}\_\{a\}\(x\)<1on\[0,∞\)\[0,\\infty\)\. Sinceh~a′\\widetilde\{h\}\_\{a\}^\{\\prime\}is decreasing on\[0,∞\)\[0,\\infty\), the Lipschitz constant is

Lip⁡\(h~a\)=h~a′​\(0\)=a\.\\Lip\(\\widetilde\{h\}\_\{a\}\)=\\widetilde\{h\}\_\{a\}^\{\\prime\}\(0\)=a\.
The approximation error is

Δ⁡\(h~a\)=∫0∞\(1−a​x1\+a2​x2\)​𝑑x=limz→∞\[x−1a​1\+a2​x2\]0z=1a,\\Delta\(\\widetilde\{h\}\_\{a\}\)=\\int\_\{0\}^\{\\infty\}\\left\(1\-\\frac\{ax\}\{\\sqrt\{1\+a^\{2\}x^\{2\}\}\}\\right\)\\mathrm\{d\}x=\\lim\_\{z\\to\\infty\}\\left\[\\,x\-\\frac\{1\}\{a\}\\sqrt\{1\+a^\{2\}x^\{2\}\}\\,\\right\]\_\{0\}^\{z\}=\\frac\{1\}\{a\},where we usedx−1a​1\+a2​x2=−1a2​x\+a​1\+a2​x2→0x\-\\tfrac\{1\}\{a\}\\sqrt\{1\+a^\{2\}x^\{2\}\}=\-\\tfrac\{1\}\{a^\{2\}x\+a\\sqrt\{1\+a^\{2\}x^\{2\}\}\}\\to 0asx→∞x\\to\\infty\. Combining these gives

Lip⁡\(h~a\)=a,Δ⁡\(h~a\)=1a=1Lip⁡\(h~a\),\\Lip\(\\widetilde\{h\}\_\{a\}\)=a,\\qquad\\Delta\(\\widetilde\{h\}\_\{a\}\)=\\frac\{1\}\{a\}=\\frac\{1\}\{\\Lip\(\\widetilde\{h\}\_\{a\}\)\},which is the analogue of[Lemma5\.2](https://arxiv.org/html/2608.26288#S5.Thmtheorem2)forh~a\\widetilde\{h\}\_\{a\}\. Balancing the approximation error against the Lipschitz constant as in[Section5](https://arxiv.org/html/2608.26288#S5)then yields guarantees such as[Theorems5\.1](https://arxiv.org/html/2608.26288#S5.Thmtheorem1)and[5\.3](https://arxiv.org/html/2608.26288#S5.Thmtheorem3)forh~a\\widetilde\{h\}\_\{a\}, now controlled by the smoothing parameteraarather than the iteration depthqq\.

### F\.2The tradeoff is intrinsic to general spectral maps

This inverse relationship betweenΔ⁡\(h\)\\Delta\(h\)andLip⁡\(h\)\\Lip\(h\)is not special to the two maps above\. For anyhhsatisfying[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1), the propertiesh⁡\(0\)=0h\(0\)=0,h≤1h\\leq 1, andLip⁡\(h\)\\Lip\(h\)\-Lipschitz continuity giveh⁡\(x\)≤min⁡\{Lip⁡\(h\)​x,1\}h\(x\)\\leq\\min\\\{\\Lip\(h\)\\,x,\\,1\\\}, and therefore

Δ⁡\(h\)=∫0∞\(1−h⁡\(x\)\)​𝑑x≥∫01/Lip⁡\(h\)\(1−Lip⁡\(h\)​x\)​𝑑x=12​Lip⁡\(h\)\.\\Delta\(h\)=\\int\_\{0\}^\{\\infty\}\\left\(1\-h\(x\)\\right\)\\mathrm\{d\}x\\geq\\int\_\{0\}^\{1/\\Lip\(h\)\}\\left\(1\-\\Lip\(h\)\\,x\\right\)\\mathrm\{d\}x=\\frac\{1\}\{2\\,\\Lip\(h\)\}\.The approximation error therefore cannot fall below1/\(2​Lip⁡\(h\)\)1/\(2\\Lip\(h\)\), soΔ⁡\(h\)\\Delta\(h\)andLip⁡\(h\)\\Lip\(h\)cannot both be made small\. The tradeoff between approximation and stability exploited by finite Newton–Schulz is thus intrinsic to every map satisfying[Assumption4\.1](https://arxiv.org/html/2608.26288#S4.Thmtheorem1), not an artifact of the Newton–Schulz iteration\.

## Appendix GNumerical experiments

We test the finite Newton–Schulz update analyzed in[Section5](https://arxiv.org/html/2608.26288#S5)on a synthetic nonsmooth nonconvex objective\. By[Lemma5\.2](https://arxiv.org/html/2608.26288#S5.Thmtheorem2), increasing the Newton–Schulz depthqqreduces the approximation errorΔ⁡\(hq\)\\Delta\(h\_\{q\}\)relative to the exact polar map but increases the Lipschitz constantLip⁡\(hq\)\\Lip\(h\_\{q\}\), and the regret bound of[Theorem5\.1](https://arxiv.org/html/2608.26288#S5.Thmtheorem1)balances these two effects\. The purpose of the experiment is not to benchmark the optimization performance of the individual methods, but to examine qualitatively whether this depth\-dependent penalty–stability tradeoff appears in the optimization behavior\. For this purpose, all methods evaluate the gradient at the current iterate rather than at the randomized query points of the O2NC conversion \([Section3](https://arxiv.org/html/2608.26288#S3)\)\.

Fork=1,…,Nk=1,\\ldots,N, letZk∈ℝd×dZ\_\{k\}\\in\\mathbb\{R\}^\{d\\times d\}be a standard Gaussian random matrix and setJk=S​Zk​SJ\_\{k\}=SZ\_\{k\}SwithS=diag\(s1,…,sd\)S=\\diag\(s\_\{1\},\\ldots,s\_\{d\}\)andsi=10−\(i−1\)/\(d−1\)s\_\{i\}=10^\{\-\(i\-1\)/\(d\-1\)\}\. ForW∈ℝd×dW\\in\\mathbb\{R\}^\{d\\times d\}, we minimize an anisotropic variant of the objective employed in[Jiang et al\. \(2026a\)](https://arxiv.org/html/2608.26288#bib.bib26),

ℒ⁡\(W\)=1N​∑k=1Nψ⁡\(⟨Jk,W⟩\),ψ⁡\(z\)=\|z\|​\(1−a​cos⁡\(ω​z\)\),\\mathcal\{L\}\(W\)=\\frac\{1\}\{N\}\\sum\_\{k=1\}^\{N\}\\psi\(\\langle J\_\{k\},W\\rangle\),\\qquad\\psi\(z\)=\|z\|\\bigl\(1\-a\\cos\(\\omega z\)\\bigr\),withd=20d=20,N=100N=100,a=0\.9a=0\.9, andω=3\\omega=3, and we select the subgradient00atz=0z=0\.

All methods run on the same problem instance with learning rates0\.010\.01and0\.050\.05and momentum parameterβ=0\.9\\beta=0\.9\. We compare the following methods:

- •Muon \(SVD\): the exact polar factor of the momentum matrix, computed by a singular value decomposition\.
- •Muon \(NS\): the updateℋhq​\(Mt/Gop\)\\mathcal\{H\}\_\{h\_\{q\}\}\(M\_\{t\}/G\_\{\\mathrm\{op\}\}\)with depthq∈\{0,2,5,10\}q\\in\\\{0,2,5,10\\\}, where the learning rate plays the role of the radiusDDin[Section5](https://arxiv.org/html/2608.26288#S5), andq=0q=0uses the normalized momentum itself\. We fixGop=3\.2G\_\{\\mathrm\{op\}\}=3\.2, which exceeds every gradient operator norm observed in the runs\.
- •Pion and Leon: Algorithms 2 and 3 of[Jiang et al\. \(2026a\)](https://arxiv.org/html/2608.26288#bib.bib26)with step sizeη=1\\eta=1in their notation, second\-moment parameter0\.90\.9, and a numerical regularization of10−810^\{\-8\}in the preconditioner\. Pion averages1010perturbation samples per step\.

Figure 3:Loss versus gradient evaluations \(top\) and wall\-clock time \(bottom\) with learning rates0\.010\.01\(left\) and0\.050\.05\(right\)\.[Figure3](https://arxiv.org/html/2608.26288#A7.F3)shows how the loss evolves for each depthqqand learning rate\. At the larger learning rate, the exact\-polar update continues to fluctuate around a high loss value, and the largest depthq=10q=10also exhibits this instability\. On the other hand, the shallowest depthq=0q=0is stable but slow, needing many more gradient evaluations to make comparable progress\. The intermediate depthsq=2q=2andq=5q=5avoid both of these failures: they descend quickly and remain stable\. This matches qualitatively the penalty–stability tradeoff discussed in[Section5](https://arxiv.org/html/2608.26288#S5), where increasing the depth gives a better approximation to the polar map but increases the Lipschitz constant that governs the stability of the update\. In this sense, the experiment demonstrates a benefit of the finite Newton–Schulz iteration beyond approximating the exact polar map\. Pion and Leon are also stable, and Pion is slower in wall\-clock time since each of its steps computes several perturbed polar factors\.