Introduction
Adaptive methods such as Adam ([37 ] ) and AdamW ([50 ] ) remain the default choice for training large models ([2 , 46 ] ). A prominent recent alternative is Muon ([32 ] ), which applies an approximate orthogonalization to the momentum of matrix-valued parameters. Muon has attracted considerable attention due to its strong empirical performance, efficient GPU implementation, and reduced optimizer-state memory; its scalability has been demonstrated by training the Moonlight 16B Mixture-of-Experts model on 5.7 trillion tokens ([47 ] ). Its update can be interpreted through stochastic spectral descent ([14 , 41 ] ) and, more generally, as a step along a linear minimization oracle (LMO) over a norm ball ([30 , 66 ] ). The LMO view gives a unified treatment of non-Euclidean methods with momentum, recovering normalized SGD ([43 , 16 ] ), SignSGD and Signum ([10 , 75 ] ), Scion ([66 ] ), and Muon as special cases.
In this work, we study whether, and how, the advantages of momentum orthogonalization carry over to differential privacy (DP). We consider the standard central, example-level setting of DP-SGD ((Abadi et al., 2016): each per-example gradient is clipped to norm c c c , Gaussian noise is added to the average, and the result is passed to the optimizer; the momentum and LMO steps are post-processing and do not affect privacy [21 ] . The optimization problem, however, becomes substantially more delicate. Active clipping introduces a state-dependent bias, privacy noise is injected at every step, momentum aggregates gradients along a changing trajectory, and the noisy momentum is then passed through a nonlinear map. Existing analyses of private nonconvex optimization typically sidestep active clipping: the sharpest rates assume Lipschitz losses, that is, uniformly bounded per-example gradients, so that clipping at a threshold above the bound is inactive [8 , 79 , 83 , 7 , 52 ] , and analyses of private distributed methods make similar assumptions (Appendix § 13 ). Generic analyses of biased stochastic gradients [4 , 20 ] measure the full additive bias and do not exploit the structure of the update.
Key observation: for an LMO, clipping is (almost) a rescaling. Let μ ( g ) : = E [ clip c ( g + ξ ) ] \mu(g) := \mathbb{E}[\operatorname{clip}_{c}(g + \xi)] μ ( g ) := E [ clip c ( g + ξ )] be the expected clipped gradient, where g g g is the true gradient and ξ \xi ξ is zero-mean sampling noise with variance σ 2 \sigma^2 σ 2 . We show (Lemma 1) that
μ ( g ) = λ ( g ) g + r ( g ) , λ ( g ) ≍ c max { c , ∥ g ∥ 2 } , ∥ r ( g ) ∥ 2 ≲ λ ( g ) min { σ , σ 2 c } . (1) \begin{aligned}
\mu(g) &= \lambda(g)g + r(g), \qquad\lambda(g) \asymp\frac{c}{\max\{c,\lVert g\rVert_2\}},\\
\lVert r(g)\rVert_2 &\lesssim\lambda(g)\min\left\{\sigma,\frac{\sigma^2}{c}\right\}. \tag*{(1)}
\end{aligned} μ ( g ) ∥ r ( g ) ∥ 2 = λ ( g ) g + r ( g ) , λ ( g ) ≍ max { c , ∥ g ∥ 2 } c , ≲ λ ( g ) min { σ , c σ 2 } . (1)
The leading effect of clipping is thus a positive rescaling of the true gradient, and an LMO is blind to it: LMO ( λ g ) = LMO ( g ) \operatorname{LMO}(\lambda g) = \operatorname{LMO}(g) LMO ( λ g ) = LMO ( g ) for every λ > 0 \lambda> 0 λ > 0 . Only the residual r ( g ) r(g) r ( g ) , which changes the direction , enters the optimization error. This lets us analyze momentum-LMO methods under active clipping assuming only bounded centered variance , without bounded gradients and without a clipping threshold that grows with the horizon.
Contributions. Our answer to the question in the title has a theoretical and an empirical part.
Convergence of private momentum-LMO methods. For smooth nonconvex objectives in any finite-dimensional norm (covering Muon, Scion, sign descent, and normalized SGD), we prove a high-probability bound that separates optimization error, momentum tracking, sampling noise, privacy noise, and a clipping floor ρ 1 min { σ , σ 2 / c } \rho_1\min\{\sigma,\sigma^2/c\} ρ 1 min { σ , σ 2 / c } (Theorem 1). The floor is the dual-norm version of the tight Euclidean floor of clipped SGD [38 ] and vanishes as σ → 0 \sigma\to0 σ → 0 ; passing through the LMO thus costs at most the norm-conversion constant ρ 1 \rho_1 ρ 1 relative to clipped SGD, and the guarantee does not show that it improves on it. At a fixed noise scale, the bound gives the rate O ~ ( K − 1 / 4 ) \widetilde{O}(K^{-1/4}) O ( K − 1/4 ) , where O ~ \widetilde{O} O hides factors logarithmic in K K K and in the failure probability; and with noise calibrated to an ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) budget it gives the familiar O ( ( c E ∥ Z ∥ ∗ log ( 1 / δ ) / ( n ε ) ) 1 / 2 ) O((c\mathbb{E}\lVert Z\rVert_*\sqrt{\log(1/\delta)}/(n\varepsilon))^{1/2}) O (( c E ∥ Z ∥ ∗ log ( 1/ δ ) / ( n ε ) ) 1/2 ) dependence (Corollary 1, Appendix § 10 .§ 2 ).
What changes under DP. On CNN and a 30M-parameter GPT model, we sweep the batch size, learning rate, and momentum for DP-SGD, DP-Adam, and DP-Muon (and Scion). Under DP, the optimal batch size grows by one to two orders of magnitude and the ranking of optimizers depends on the batch size , unlike in non-private training, where Muon is best at every batch size. On CIFAR-10, DP-Muon attains the lowest mean test loss at all but one batch size, with the gaps within one standard deviation at intermediate batch sizes; on language modeling, DP-Muon is best at small batch sizes, DP-Adam near the optimal batch size, and Scion at large batch sizes (§ 4 ).
Concurrent work. Two concurrent and independent works also study private Muon2 . Kim and Fan (2026) analyze a Muon variant with finite-step Newton–Schulz (NS) orthogonalization and propose a bias-
Algorithm 1 DP-Muon (private momentum-LMO)
Require: stepsize γ \gamma γ , momentum α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , clipping threshold c c c , noise scale σ D P \sigma_{\mathrm{DP}} σ DP , batch size B B B , iterations K K K
m 0 ← 0 m_0 \gets0 m 0 ← 0
for k = 0 , … , K − 1 k = 0,\ldots,K-1 k = 0 , … , K − 1 do
Sample S k ⊆ [ n ] S_k \subseteq[n] S k ⊆ [ n ] , ∣ S k ∣ = B |S_k| = B ∣ S k ∣ = B , uniformly at random
g ^ k ← 1 B ∑ i ∈ S k clip c ( ∇ f i ( x k ) ) + z k , z k ∼ N ( 0 , c 2 σ D P 2 I ) \hat{g}_k \gets\frac{1}{B}\sum_{i\in S_k}\operatorname{clip}_c(\nabla f_i(x_k)) + z_k,\ z_k \sim\mathcal{N}(0,c^2\sigma_{\mathrm{DP}}^2 I) g ^ k ← B 1 ∑ i ∈ S k clip c ( ∇ f i ( x k )) + z k , z k ∼ N ( 0 , c 2 σ DP 2 I )
m k + 1 ← ( 1 − α ) m k + α g ^ k m_{k+1} \gets(1-\alpha)m_k + \alpha\hat{g}_k m k + 1 ← ( 1 − α ) m k + α g ^ k
x k + 1 ← x k + γ LMO ( m k + 1 ) x_{k+1} \gets x_k + \gamma\,\operatorname{LMO}(m_{k+1}) x k + 1 ← x k + γ LMO ( m k + 1 )
end for
corrected DP-MuonBC; their vanishing-rate corollaries assume moment bounds on the raw (uncentered) per-example gradients and let the clipping threshold grow with the horizon, while their general bound contains a clipping term that persists even without sampling noise. Shanmugam et al. [70 ] study when orthogonalization recovers useful singular directions of privatized gradients through a Wedin-type signal-to-noise argument and report large gains of DP-Muon over DP-SGD in vision at large batch sizes. Our analysis is complementary: it covers general LMO geometries, requires only centered variance, and isolates the part of the clipping bias that an LMO actually sees; a detailed comparison is given in § 3.3 and Appendix § 12 .
Setup and Algorithm
We consider min x ∈ X f ( x ) : = 1 n ∑ i = 1 n f i ( x ) \min_{x\in\mathcal{X}} f(x) := \frac{1}{n}\sum_{i=1}^{n} f_i(x) min x ∈ X f ( x ) := n 1 ∑ i = 1 n f i ( x ) over a finite-dimensional normed space ( X , ∥ ⋅ ∥ ) (\mathcal{X}, \|\cdot\|) ( X , ∥ ⋅ ∥ ) with dual norm ∥ v ∥ ⋆ : = sup ∥ d ∥ ≤ 1 ⟨ v , d ⟩ \|v\|_\star:= \sup_{\|d\|\leq1}\langle v,d\rangle ∥ v ∥ ⋆ := sup ∥ d ∥ ≤ 1 ⟨ v , d ⟩ . For the unit ball C = { v : ∥ v ∥ ≤ 1 } C = \{v : \|v\| \leq1\} C = { v : ∥ v ∥ ≤ 1 } , the linear minimization oracle is LMO ( g ) ∈ arg min v ∈ C ⟨ g , v ⟩ \operatorname{LMO}(g) \in\arg\min_{v\in C}\langle g,v\rangle LMO ( g ) ∈ arg min v ∈ C ⟨ g , v ⟩ , so that ⟨ g , LMO ( g ) ⟩ = − ∥ g ∥ ⋆ \langle g,\operatorname{LMO}(g)\rangle= -\|g\|_\star ⟨ g , LMO ( g )⟩ = − ∥ g ∥ ⋆ and LMO ( λ g ) = LMO ( g ) \operatorname{LMO}(\lambda g) = \operatorname{LMO}(g) LMO ( λ g ) = LMO ( g ) for λ > 0 \lambda> 0 λ > 0 . The spectral norm on a weight matrix gives Muon, LMO ( G ) = − U V ⊤ \operatorname{LMO}(G) = -UV^\top LMO ( G ) = − U V ⊤ for G = U Σ V ⊤ G = U\Sigma V^\top G = U Σ V ⊤ ; the ℓ ∞ \ell_\infty ℓ ∞ norm gives sign descent; the ℓ 2 \ell_2 ℓ 2 norm gives normalized gradient descent; and layer-wise combinations give Scion (Pethick et al. [66 ] ) (see Table 2 in the appendix). Since X \mathcal{X} X is finite-dimensional, there are constants ρ 1 , ρ 2 \rho_1,\rho_2 ρ 1 , ρ 2 with ∥ v ∥ ⋆ ≤ ρ 1 ∥ v ∥ 2 \|v\|_\star\leq\rho_1\|v\|_2 ∥ v ∥ ⋆ ≤ ρ 1 ∥ v ∥ 2 and ∥ v ∥ 2 ≤ ρ 2 ∥ v ∥ ⋆ \|v\|_2 \leq\rho_2\|v\|_\star ∥ v ∥ 2 ≤ ρ 2 ∥ v ∥ ⋆ ; for the spectral norm on an m × n ′ m \times n' m × n ′ matrix, ∥ ⋅ ∥ ⋆ \|\cdot\|_\star ∥ ⋅ ∥ ⋆ is the nuclear norm, ρ 1 = min { m , n ′ } \rho_1 = \sqrt{\min\{m,n'\}} ρ 1 = min { m , n ′ } , and ρ 2 = 1 \rho_2 = 1 ρ 2 = 1 . Clipping is Euclidean, clip c ( v ) : = v min { 1 , c / ∥ v ∥ 2 } \operatorname{clip}_c(v) := v\min\{1,c/\|v\|_2\} clip c ( v ) := v min { 1 , c /∥ v ∥ 2 } , as in DP-SGD.
Table 2. Common LMO geometries on R d \mathbb{R}^d R d (or on R m × n ′ \mathbb{R}^{m\times n'} R m × n ′ for the spectral norm).
DP-Muon (Algorithm 1) privatizes the mini-batch gradient exactly as DP-SGD does; only the optimizer step differs. In practice, Muon is applied with a few Newton–Schulz iterations in place of the exact polar factor; our analysis assumes an exact LMO.
A randomized algorithm M \mathcal{M} M is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -differentially private if P ( M ( D ) ∈ S ) ≤ e ε P ( M ( D ′ ) ∈ S ) + δ \mathbb{P}(\mathcal{M}(\mathcal{D}) \in S) \leq e^\varepsilon\mathbb{P}(\mathcal{M}(\mathcal{D}') \in S) + \delta P ( M ( D ) ∈ S ) ≤ e ε P ( M ( D ′ ) ∈ S ) + δ for all measurable S S S and all adjacent datasets D , D ′ \mathcal{D},\mathcal{D}' D , D ′ (Dwork et al. [21 ] ). We use add/remove adjacency (one example added or removed) for Poisson subsampling, as in Abadi et al. [1 ] , and replace-one adjacency for fixed-size sampling without replacement (Wang et al. [85 ] ); an ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP guarantee under add/remove adjacency implies ( 2 ε , ( 1 + e ε ) δ ) (2\varepsilon,(1+e^\varepsilon)\delta) ( 2 ε , ( 1 + e ε ) δ ) -DP under replace-one adjacency, but not conversely.
Proposition 1 (Privacy). Let x 0 x_0 x 0 , K K K , B B B , c c c , σ D P \sigma_{\mathrm{DP}} σ DP , α \alpha α , and γ \gamma γ be fixed independently of the data (and, under replace-one adjacency, n n n be public), and let the output be the whole trajectory x 0 , … , x K x_0,\ldots,x_K x 0 , … , x K , so that any function of it, such as the tail average or a uniformly sampled iterate, inherits the guarantee. The privacy of Algorithm 1 is that of DP-SGD with the same sampling, clipping, and noise: the momentum and LMO steps only post-process the privatized gradients g ^ 0 , … , g ^ K − 1 \hat{g}_0,\ldots,\hat{g}_{K-1} g ^ 0 , … , g ^ K − 1 . In particular, with q = B / n q = B/n q = B / n , there are constants c 1 , c 2 > 0 c_1,c_2 > 0 c 1 , c 2 > 0 such that Algorithm 1, with fixed-size sampling without replacement, is ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) -DP under replace-one adjacency for any ε < c 1 q 2 K \varepsilon< c_1q^2K ε < c 1 q 2 K if
σ D P ≥ c 2 K log ( 1 / δ ) n ε . (2) \sigma_{\mathrm{DP}} \geq\frac{c_2\sqrt{K\log(1/\delta)}}{n\varepsilon}. \tag*{(2)} σ DP ≥ n ε c 2 K log ( 1/ δ ) . (2)
*If the fixed-size sampling is replaced by Poisson subsampling at rate q q q (normalized by the expected batch size B B B ), a calibration of the same form, with different constants, holds under add/remove adjacency (Abadi et al., 2016, Theorem 1).
Proof sketch. The first claim is the post-processing property of differential privacy [21 ] , applied with adaptive composition over the K K K releases g ^ k \hat{g}_k g ^ k . For fixed-size sampling, replacing one example changes the clipped sum ∑ i ∈ S k clip c ( ∇ f i ( x k ) ) \sum_{i\in S_k}\operatorname{clip}_c(\nabla f_i(x_k)) ∑ i ∈ S k clip c ( ∇ f i ( x k )) by at most 2 c 2c 2 c in ℓ 2 \ell_2 ℓ 2 , so each release is a Gaussian mechanism with noise multiplier σ m u l t = B σ D P \sigma_{\mathrm{mult}} = B\sigma_{\mathrm{DP}} σ mult = B σ DP relative to sensitivity c c c . For the subsampled Gaussian mechanism, Wang et al. [85 ] and the discussion after it) give the Rényi-DP bound ϵ ′ ( a ) = O ( q 2 a / σ m u l t 2 ) \epsilon'(a) = O(q^2a/\sigma_{\mathrm{mult}}^2) ϵ ′ ( a ) = O ( q 2 a / σ mult 2 ) at small orders a a a and large σ m u l t \sigma_{\mathrm{mult}} σ mult ; the replace-one sensitivity 2 c 2c 2 c only changes the constant. Composing over K K K steps and converting to ( ϵ , δ ) (\epsilon,\delta) ( ϵ , δ ) with an order a ≍ log ( 1 / δ ) / ϵ a \asymp\log(1/\delta)/\epsilon a ≍ log ( 1/ δ ) / ϵ , exactly as in the proof of Abadi et al. [1 ] , gives (2) ; the requirement that this order lies in the range where the bound holds is what imposes ϵ < c 1 q 2 K \epsilon< c_1q^2K ϵ < c 1 q 2 K .
Note that, for a fixed number of steps K K K , the noise scale on the averaged gradient, c σ D P c\sigma_{\mathrm{DP}} c σ DP , does not depend on B B B ; at a fixed budget of epochs, K ∝ 1 / B K \propto1/B K ∝ 1/ B and the noise on the average decreases with B B B only through the smaller number of steps (Appendix § 11 .§ 1 quantifies this with the accountant actually used in the experiments).
Assumption 1. f f f is bounded below by f ⋆ f^\star f ⋆ , and ∇ f \nabla f ∇ f is L L L -Lipschitz: ∥ ∇ f ( x ) − ∇ f ( y ) ∥ ⋆ ≤ L ∥ x − y ∥ \lVert\nabla f(x)-\nabla f(y)\rVert_\star\le L\lVert x-y\rVert ∥ ∇ f ( x ) − ∇ f ( y ) ∥ ⋆ ≤ L ∥ x − y ∥ for all x , y x,y x , y .
Assumption 2. For all x x x , 1 n ∑ i = 1 n ∥ ∇ f i ( x ) − ∇ f ( x ) ∥ 2 2 ≤ σ 2 \frac{1}{n}\sum_{i=1}^{n}\lVert\nabla f_i(x)-\nabla f(x)\rVert_2^2 \le\sigma^2 n 1 ∑ i = 1 n ∥ ∇ f i ( x ) − ∇ f ( x ) ∥ 2 2 ≤ σ 2 .
Assumption 2 bounds only the centered spread of per-example gradients; in particular, the gradients themselves may be arbitrarily large, so clipping can be active throughout training.
Theory: How Muon Handles Clipping
Clipping is a rescaling up to a small residual
For a fixed point x x x , write g = ∇ f ( x ) g=\nabla f(x) g = ∇ f ( x ) and ξ i = ∇ f i ( x ) − g \xi_i=\nabla f_i(x)-g ξ i = ∇ f i ( x ) − g , so that μ ( g ) = 1 n ∑ i clip c ( g + ξ i ) \mu(g)=\frac{1}{n}\sum_i\operatorname{clip}_c(g+\xi_i) μ ( g ) = n 1 ∑ i clip c ( g + ξ i ) is the expected clipped mini-batch gradient, and let a c ( g ) : = c / max { c , ∥ g ∥ 2 } a_c(g):=c/\max\{c,\lVert g\rVert_2\} a c ( g ) := c / max { c , ∥ g ∥ 2 } denote the factor by which g g g itself would be clipped.
Lemma 1 (Positive-ray decomposition). Under Assumption 2, for every g g g there is λ ( g ) ∈ [ 1 4 a c ( g ) , 2 a c ( g ) ] \lambda(g)\in[\frac{1}{4}a_c(g),2a_c(g)] λ ( g ) ∈ [ 4 1 a c ( g ) , 2 a c ( g )] such that
∥ μ ( g ) − λ ( g ) g ∥ 2 ≤ 16 λ ( g ) min { σ , σ 2 c } , \lVert\mu(g)-\lambda(g)g\rVert_2 \le16\lambda(g)\min\left\{\sigma,\frac{\sigma^2}{c}\right\}, ∥ μ ( g ) − λ ( g ) g ∥ 2 ≤ 16 λ ( g ) min { σ , c σ 2 } , and
1 n ∑ i ∥ clip c ( g + ξ i ) − μ ( g ) ∥ 2 2 ≤ 320 λ ( g ) 2 σ 2 . \frac{1}{n}\sum_i\left\lVert\operatorname{clip}_c(g+\xi_i)-\mu(g)\right\rVert_2^2 \le320\lambda(g)^2\sigma^2. n 1 i ∑ ∥ clip c ( g + ξ i ) − μ ( g ) ∥ 2 2 ≤ 320 λ ( g ) 2 σ 2 .
The scale λ ( g ) \lambda(g) λ ( g ) is comparable to the clipping factor of the true gradient , so the residual is small relative to the shrunken signal λ ( g ) g \lambda(g)g λ ( g ) g : the clipped mean points in the right direction up to an angle controlled by min { σ , σ 2 / c } / ∥ g ∥ 2 \min\{\sigma,\sigma^2/c\}/\lVert g\rVert_2 min { σ , σ 2 / c } / ∥ g ∥ 2 . When c ≥ σ c\ge\sigma c ≥ σ and ∥ g ∥ 2 ≥ 4 σ 2 / c \lVert g\rVert_2\ge4\sigma^2/c ∥ g ∥ 2 ≥ 4 σ 2 / c , the proof takes λ ( g ) = ⟨ μ ( g ) , g ⟩ / ∥ g ∥ 2 2 \lambda(g)=\langle\mu(g),g\rangle/\lVert g\rVert_2^2 λ ( g ) = ⟨ μ ( g ) , g ⟩ / ∥ g ∥ 2 2 , so the residual is the component orthogonal to g g g of E [ a c ( g + ξ ) ξ ] = E [ ( a c ( g + ξ ) − a c ( g ) ) ξ ] \mathbb{E}[a_c(g+\xi)\xi]=\mathbb{E}[(a_c(g+\xi)-a_c(g))\xi] E [ a c ( g + ξ ) ξ ] = E [( a c ( g + ξ ) − a c ( g )) ξ ] , which is second order in ξ \xi ξ by the two-point estimate ∣ a c ( y ) − a c ( g ) ∣ ≤ a c ( g ) ∥ y − g ∥ 2 / c |a_c(y)-a_c(g)|\le a_c(g)\lVert y-g\rVert_2/c ∣ a c ( y ) − a c ( g ) ∣ ≤ a c ( g ) ∥ y − g ∥ 2 / c . When c ≥ σ c\ge\sigma c ≥ σ and ∥ g ∥ 2 < 4 σ 2 / c \lVert g\rVert_2<4\sigma^2/c ∥ g ∥ 2 < 4 σ 2 / c , it takes λ ( g ) = a c ( g ) \lambda(g)=a_c(g) λ ( g ) = a c ( g ) , and the residual contains in addition the longitudinal term ( E a c ( g + ξ ) − a c ( g ) ) g (\mathbb{E}\,a_c(g+\xi)-a_c(g))g ( E a c ( g + ξ ) − a c ( g )) g , which the same estimate bounds by 4 a c ( g ) σ 2 / c 4a_c(g)\sigma^2/c 4 a c ( g ) σ 2 / c because g g g is small. When c < σ c<\sigma c < σ and ∥ g ∥ 2 ≫ σ \lVert g\rVert_2\gg\sigma ∥ g ∥ 2 ≫ σ , most per-example gradients are clipped onto a cone around g g g . Both cases use only the centered variance (proofs in Appendix § 9 .§ 2 ). Koloskova et al. [38 ] bound the additive deviation ∥ μ ( g ) − clip c ( g ) ∥ 2 \lVert\mu(g)-\operatorname{clip}_c(g)\rVert_2 ∥ μ ( g ) − clip c ( g ) ∥ 2 from the same ray, since clip c ( g ) = a c ( g ) g \operatorname{clip}_c(g)=a_c(g)g clip c ( g ) = a c ( g ) g ; the new element here is that the deviation is bounded relative to λ ( g ) \lambda(g) λ ( g ) , uniformly in ∥ g ∥ 2 \lVert g\rVert_2 ∥ g ∥ 2 , which is exactly what a scale-invariant update needs. Relatedly, Xiao et al. [86 ] identify the sampling noise of the gradients being clipped as a key source of the bias of clipped and normalized DP-SGD.
The second ingredient translates a small projective error into a descent direction.
Lemma 2 (Projective LMO bound). For all m , g ∈ X ⋆ m,g \in\mathcal{X}^{\star} m , g ∈ X ⋆ and d ∈ LMO ( m ) d \in\operatorname{LMO}(m) d ∈ LMO ( m ) ,
⟨ g , d ⟩ ≤ − ∥ g ∥ ⋆ + 2 R ( m , g ) , \langle g,d\rangle\le-\lVert g\rVert_{\star}+2\mathcal{R}(m,g), ⟨ g , d ⟩ ≤ − ∥ g ∥ ⋆ + 2 R ( m , g ) , where R ( m , g ) : = inf λ > 0 ∥ m − λ g ∥ ⋆ / λ \mathcal{R}(m,g):=\inf_{\lambda>0}\lVert m-\lambda g\rVert_{\star}/\lambda R ( m , g ) := inf λ > 0 ∥ m − λ g ∥ ⋆ / λ .
This is the normalized-step inequality of Cutkosky and Mehta [16 ] (see also Pethick et al., [66 ] ) applied to m / λ m/\lambda m / λ , using LMO ( m ) = LMO ( m / λ ) \operatorname{LMO}(m)=\operatorname{LMO}(m/\lambda) LMO ( m ) = LMO ( m / λ ) and optimizing over λ \lambda λ . Unlike the additive bias ∥ m − g ∥ ⋆ \lVert m-g\rVert_{\star} ∥ m − g ∥ ⋆ , R ( m , g ) \mathcal{R}(m,g) R ( m , g ) vanishes whenever m m m is any positive multiple of g g g .
Convergence of DP-Muon
Let k b : = ⌈ log 2 / α ⌉ k_{\mathrm{b}}:=\lceil\log2/\alpha\rceil k b := ⌈ log 2/ α ⌉ , T : = K − k b T:=K-k_{\mathrm{b}} T := K − k b , Φ 0 : = f ( x 0 ) − f ⋆ \Phi_{0}:=f(x_{0})-f^{\star} Φ 0 := f ( x 0 ) − f ⋆ , Φ ˉ : = ( Φ 0 + k b γ L / 2 ) 2 \bar{\Phi}:=(\sqrt{\Phi_{0}}+k_{\mathrm{b}}\gamma\sqrt{L/2})^{2} Φ ˉ := ( Φ 0 + k b γ L /2 ) 2 , σ ~ : = ρ 1 σ \tilde{\sigma}:=\rho_{1}\sigma σ ~ := ρ 1 σ , b ~ c : = ρ 1 min { σ , σ 2 / c } \tilde{b}_{c}:=\rho_{1}\min\{\sigma,\sigma^{2}/c\} b ~ c := ρ 1 min { σ , σ 2 / c } , and, for η ∈ ( 0 , 1 ) \eta\in(0,1) η ∈ ( 0 , 1 ) and Z ∼ N ( 0 , I ) Z\sim\mathcal{N}(0,I) Z ∼ N ( 0 , I ) ,
ν D P ( η ) : = c σ D P 3 α ( E ∥ Z ∥ ⋆ + ρ 1 2 log ( T / η ) ) . \nu_{\mathrm{DP}}(\eta):=c\sigma_{\mathrm{DP}}\sqrt{3\alpha}\left(\mathbb{E}\lVert Z\rVert_{\star}+\rho_{1}\sqrt{2\log(T/\eta)}\right). ν DP ( η ) := c σ DP 3 α ( E ∥ Z ∥ ⋆ + ρ 1 2 log ( T / η ) ) .
the high-probability size of the momentum-filtered privacy noise.
Theorem 1. Let Assumptions 1–2 hold, T > 0 T>0 T > 0 , and
ρ 2 L γ c ≤ α 4 , 10 ρ 2 ν D P ( η ) c ≤ 1 2 . (3) \frac{\rho_{2}L\gamma}{c}\le\frac{\alpha}{4},\qquad\frac{10\rho_{2}\nu_{\mathrm{DP}}(\eta)}{c}\le\frac{1}{2}. \tag*{(3)} c ρ 2 L γ ≤ 4 α , c 10 ρ 2 ν DP ( η ) ≤ 2 1 . (3) Then, with probability at least 1 − η 1-\eta 1 − η over the privacy noise, the iterates of Algorithm 1 satisfy
1 T ∑ k = k b K − 1 E S ∥ ∇ f ( x k ) ∥ ⋆ ≤ 2 Φ ˉ γ T + 45 L γ α + 64 b ~ c + C σ ~ B ( α + 1 α T ) + 20 ν D P ( η ) , \frac{1}{T}\sum_{k=k_{\mathrm{b}}}^{K-1}\mathbb{E}_{S}\lVert\nabla f(x_{k})\rVert_{\star}
\le\frac{2\bar{\Phi}}{\gamma T}+\frac{45L\gamma}{\alpha}+64\tilde{b}_{c}
+\frac{C\tilde{\sigma}}{\sqrt{B}}\left(\sqrt{\alpha}+\frac{1}{\alpha T}\right)+20\nu_{\mathrm{DP}}(\eta), T 1 k = k b ∑ K − 1 E S ∥ ∇ f ( x k ) ∥ ⋆ ≤ γ T 2 Φ ˉ + α 45 L γ + 64 b ~ c + B C σ ~ ( α + α T 1 ) + 20 ν DP ( η ) , where E S \mathbb{E}_{S} E S is the expectation over mini-batch sampling given the privacy noise and C C C is a universal constant.
The first condition in (3) ties the stepsize to the clipping threshold and the momentum: the iterates must move slowly enough that the clipping scales λ ( ∇ f ( x k ) ) \lambda(\nabla f(x_{k})) λ ( ∇ f ( x k )) seen by the momentum buffer change by at most a constant factor over its effective window 1 / α 1/\alpha 1/ α . The second requires the filtered privacy noise to be smaller than the clipping radius, which is the norm of the clipped signal when gradients are large. Because the noise is controlled through its worst-case dual norm E ∥ Z ∥ ⋆ \mathbb{E}\lVert Z\rVert_{\star} E ∥ Z ∥ ⋆ , this condition is restrictive: in the experiments of § 4 , even in the optimistic ℓ 2 \ell_{2} ℓ 2 specialization it holds, together with the run-in requirement T > 0 T>0 T > 0 , only for CIFAR-10 at the largest batch size with momentum 0.99, for no language-modeling configuration, and not at the observed optima; in the spectral geometry of DP-Muon, where H 2 / d H^{2}/d H 2 / d grows with the matrix rank, it holds for none of our configurations (Appendix § 11 .§ 2 gives the numbers).
Corollary 1. For fixed c c c and σ D P \sigma_{\mathrm{DP}} σ DP , the choice α = Θ ( 1 / K log K ) \alpha=\Theta(1/\sqrt{K}\log K) α = Θ ( 1/ K log K ) and γ = Θ ( K − 3 / 4 ( log K ) − 1 / 4 ) \gamma=\Theta(K^{-3/4}(\log K)^{-1/4}) γ = Θ ( K − 3/4 ( log K ) − 1/4 ) satisfies (3) for K K K large enough (of order ρ 2 4 σ D P 4 H 4 \rho_{2}^{4}\sigma_{\mathrm{DP}}^{4}H^{4} ρ 2 4 σ DP 4 H 4 up to logarithms, Appendix § 10 .§ 1 ) and gives
1 T ∑ k = k b K − 1 E S ∥ ∇ f ( x k ) ∥ ⋆ = O ( ( log K ) 1 / 4 K 1 / 4 ) + O ( b ~ c ) . \frac{1}{T}\sum_{k=k_{\mathrm{b}}}^{K-1}\mathbb{E}_{S}\lVert\nabla f(x_{k})\rVert_{\star}
=\mathcal{O}\left(\frac{(\log K)^{1/4}}{K^{1/4}}\right)+\mathcal{O}(\tilde{b}_{c}). T 1 k = k b ∑ K − 1 E S ∥ ∇ f ( x k ) ∥ ⋆ = O ( K 1/4 ( log K ) 1/4 ) + O ( b ~ c ) .
With σ D P \sigma_{\mathrm{DP}} σ DP calibrated by (2) to a fixed ( ϵ , δ ) (\epsilon,\delta) ( ϵ , δ ) budget for the fixed-size sampling of Algorithm 1, a suitable choice of K , α , γ K,\alpha,\gamma K , α , γ gives instead
O ( ( L Φ 0 ) 1 / 4 ( c H log ( 1 / δ ) n ϵ ) 1 / 2 ) + O ( b ~ c ) , \mathcal{O}\left((L\Phi_{0})^{1/4}\left(\frac{cH\sqrt{\log(1/\delta)}}{n\epsilon}\right)^{1/2}\right)+\mathcal{O}(\tilde{b}_{c}), O ( L Φ 0 ) 1/4 ( n ϵ cH log ( 1/ δ ) ) 1/2 + O ( b ~ c ) ,
with H = E ∥ Z ∥ ⋆ + ρ 1 2 log ( K / η ) H=\mathbb{E}\lVert Z\rVert_{\star}+\rho_{1}\sqrt{2\log(K/\eta)} H = E ∥ Z ∥ ⋆ + ρ 1 2 log ( K / η ) , whenever n ϵ n\epsilon n ϵ is large enough; in particular, it suffices that n ϵ ≳ H log ( 1 / δ ) max { ρ 2 2 L Φ 0 / c , c / L Φ 0 } n\epsilon\gtrsim H\sqrt{\log(1/\delta)}\max\{\rho_{2}^{2}\sqrt{L\Phi_{0}}/c,c/\sqrt{L\Phi_{0}}\} n ϵ ≳ H log ( 1/ δ ) max { ρ 2 2 L Φ 0 / c , c / L Φ 0 } up to lower-order terms (Appendix § 10 .§ 2 ).
The fixed-noise rate matches the K − 1 / 4 K^{-1/4} K − 1/4 rate of normalized SGD with momentum [16 ] and of clipped SGD [38 ] (the first-moment counterpart of the K − 1 / 2 K^{-1/2} K − 1/2 squared-norm rate: a squared-norm rate implies ours by Jensen’s inequality, not conversely), which is optimal under bounded variance [6 ] , up to the ( log K ) 1 / 4 (\log K)^{1/4} ( log K ) 1/4 factor from the high-probability bound over the privacy noise. For the ℓ 2 \ell_2 ℓ 2 geometry, H ≈ d H \approx\sqrt{d} H ≈ d and the calibrated bound is the usual nonconvex DP-SGD dependence ( d log ( 1 / δ ) ) 1 / 4 / n ε (d\log(1/\delta))^{1/4}/\sqrt{n\varepsilon} ( d log ( 1/ δ ) ) 1/4 / n ε . The privacy term of the bound is below the initial gradient bound 2 L Φ 0 \sqrt{2L\Phi_0} 2 L Φ 0 when n ε ≳ c H log ( 1 / δ ) / L Φ 0 n\varepsilon\gtrsim cH\sqrt{\log(1/\delta)}/\sqrt{L\Phi_0} n ε ≳ cH log ( 1/ δ ) / L Φ 0 , but the whole bound is nontrivial only if, in addition, the clipping floor b ~ c \tilde b_c b ~ c , which does not depend on n ε n\varepsilon n ε , is small compared with L Φ 0 \sqrt{L\Phi_0} L Φ 0 . The condition on n ε n\varepsilon n ε in Corollary 1 is stronger than this threshold by the factor ρ 2 2 L Φ 0 / c 2 \rho_2^2L\Phi_0/c^2 ρ 2 2 L Φ 0 / c 2 whenever c ≲ L Φ 0 c \lesssim\sqrt{L\Phi_0} c ≲ L Φ 0 , that is, the requirement on n ε n\varepsilon n ε grows with the ratio of the gradient scale to the clipping threshold, which is the price of not assuming bounded gradients (Appendix § 10 .§ 2 ). For the spectral geometry, E ∥ Z ∥ ⋆ \mathbb{E}\|Z\|_\star E ∥ Z ∥ ⋆ is the nuclear norm of a Gaussian matrix, of order min { m , n ′ } max { m , n ′ } \min\{m,n'\}\sqrt{\max\{m,n'\}} min { m , n ′ } max { m , n ′ } (Table 2 ), and the bound controls the nuclear norm of the gradient. Translated to Frobenius stationarity, the ratio of the leading privacy terms of the spectral and Euclidean bounds is ( L o p / L F ) 1 / 4 r 1 / 4 / s 0 (L_{\mathrm{op}}/L_F)^{1/4}r^{1/4}/s_0 ( L op / L F ) 1/4 r 1/4 / s 0 , where r = min { m , n ′ } r=\min\{m,n'\} r = min { m , n ′ } , L o p L_{\mathrm{op}} L op and L F L_F L F are the smoothness constants of Assumption 1 in the two geometries, and s 0 ∈ [ 1 , r ] s_0\in[1,\sqrt{r}] s 0 ∈ [ 1 , r ] is such that ∥ ∇ f ∥ n u c ≥ s 0 ∥ ∇ f ∥ F \|\nabla f\|_{\mathrm{nuc}}\ge s_0\|\nabla f\|_F ∥∇ f ∥ nuc ≥ s 0 ∥∇ f ∥ F along the trajectory. For gradients with a flat spectrum (s 0 = r s_0=\sqrt{r} s 0 = r ) and comparable smoothness constants this is a gain of r − 1 / 4 r^{-1/4} r − 1/4 , for rank-one gradients a loss of r 1 / 4 r^{1/4} r 1/4 , and the gain disappears when L o p / L F L_{\mathrm{op}}/L_F L op / L F grows like r r r , as it does for f = 1 2 ∥ X ∥ F 2 f=\frac{1}{2}\|X\|_F^2 f = 2 1 ∥ X ∥ F 2 ; the advantage of the spectral geometry therefore rests on L o p ≪ r L F L_{\mathrm{op}}\ll rL_F L op ≪ r L F , which is the premise of Muon itself. This compares only the leading privacy terms: after the same conversion, the clipping floor b ~ c = ρ 1 min { σ , σ 2 / c } \tilde b_c=\rho_1\min\{\sigma,\sigma^2/c\} b ~ c = ρ 1 min { σ , σ 2 / c } , with ρ 1 = r \rho_1=\sqrt{r} ρ 1 = r in the spectral geometry, is r / s 0 \sqrt{r}/s_0 r / s 0 times its Euclidean counterpart, so the two floors coincide for flat spectra and the spectral one is larger by r \sqrt{r} r for rank-one gradients. The worst-case dual-norm treatment of the noise is the price of the generality in the norm.
Proof sketch. The LMO is invariant to the bias-correction factor of the momentum, so we work with m ˉ k = ∑ t ≤ k w k , t g ^ t \bar m_k=\sum_{t\le k}w_{k,t}\hat g_t m ˉ k = ∑ t ≤ k w k , t g ^ t , ∑ t w k , t = 1 \sum_t w_{k,t}=1 ∑ t w k , t = 1 . By Lemma 1, m ˉ k = A k ∇ f ( x k ) + D k + ∑ t w k , t r t + N k + P k \bar m_k=A_k\nabla f(x_k)+D_k+\sum_t w_{k,t}r_t+N_k+P_k m ˉ k = A k ∇ f ( x k ) + D k + ∑ t w k , t r t + N k + P k with A k = ∑ t w k , t λ t A_k=\sum_t w_{k,t}\lambda_t A k = ∑ t w k , t λ t , a drift term D k D_k D k , sampling noise N k N_k N k , and privacy noise P k P_k P k . Lemma 2 with λ = A k \lambda=A_k λ = A k reduces the descent step to bounding each term divided by A k A_k A k . The residuals contribute 16 b ~ c 16\tilde b_c 16 b ~ c . The first condition in (3) keeps A k A_k A k within a constant factor of a c ( ∇ f ( x k ) ) a_c(\nabla f(x_k)) a c ( ∇ f ( x k )) , which controls the drift (≲ L γ / α \lesssim L\gamma/\alpha ≲ L γ / α ) and, with the variance bound of Lemma 1, the sampling noise. Gaussian concentration bounds ∥ P k ∥ ⋆ ≤ ν D P ( η ) \|P_k\|_\star\le\nu_{\mathrm{DP}}(\eta) ∥ P k ∥ ⋆ ≤ ν DP ( η ) for all k k k , and dividing by A k A_k A k produces the ∥ ∇ f ( x k ) ∥ ⋆ \|\nabla f(x_k)\|_\star ∥∇ f ( x k ) ∥ ⋆ -proportional term absorbed by the second condition. Full proofs are in Appendix § 9 .
Comparison with existing guarantees
Table 1 compares guarantees for mechanisms that clip individual examples before aggregation, as DP-SGD and Algorithm 1 do. Two points deserve emphasis. First, our clipping floor ρ 1 min { σ , σ 2 / c } \rho_1\min\{\sigma,\sigma^2/c\} ρ 1 min { σ , σ 2 / c } is the dual-norm version of the floor of [38 ] , which is tight for clipped Gaussian noise; passing through a non-Euclidean LMO thus costs only the norm-conversion constant ρ 1 \rho_1 ρ 1 . Second, the floor depends only on the centered variance and vanishes as σ → 0 \sigma\to0 σ → 0 , even when ∥ ∇ f ∥ 2 ≫ c \|\nabla f\|_2\gg c ∥∇ f ∥ 2 ≫ c . In contrast, the general bound of Kim and Fan (2026) contains a clipping term of the form E [ ( ∥ ∇ f i ∥ − c ) + ] \mathbb{E}[(\|\nabla f_i\|-c)_+] E [( ∥∇ f i ∥ − c ) + ] , which persists for deterministic gradients larger than $c, and their vanishing-rate corollaries require moment bounds on raw gradients, which by 1 n ∑ i ∥ ∇ f i ∥ 2 2 = ∥ ∇ f ∥ 2 2 + 1 n ∑ i ∥ ∇ f i − ∇ f ∥ 2 2 \frac{1}{n}\sum_i\|\nabla f_i\|_2^2=\|\nabla f\|_2^2+\frac{1}{n}\sum_i\|\nabla f_i-\nabla f\|_2^2 n 1 ∑ i ∥∇ f i ∥ 2 2 = ∥∇ f ∥ 2 2 + n 1 ∑ i ∥∇ f i − ∇ f ∥ 2 2 also bound the mean gradient, together with a threshold growing with K K K . Outside privacy, Cutkosky and Mehta [17 ] analyze the same clip–momentum–normalize pipeline in general norms under heavy-tailed noise, with an additive clipping bias controlled by a threshold that grows with the horizon. Rates are stated under different conventions (fixed noise versus calibrated noise, average versus minimum, norm versus squared norm), which we align in Appendix § 12 .
Table 1. Optimization guarantees for per-example clipping. “Fixed”: the rate in K K K holds at a constant noise scale, so the privacy budget grows with K K K ; “calibrated”: noise calibrated to a fixed ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) is substituted into the bound. Constants and logarithms are suppressed unless shown. Theorem numbers, exact assumptions, and conventions are listed in Appendix E.
Experiments
Setup. We compare DP-SGD, DP-Adam, and DP-Muon (along with DP-Scion for language modeling) against their non-private counterparts on CIFAR-10 image classification [42 ] and on language modeling using a 30M-parameter NanoGPT model. To approximate the orthogonalization update, we utilize the Newton–Schulz method Jordan et al. [32 ] with 5 iterations. DP training uses Opacus (Yousefpour et al. [88 ] ) with Poisson subsampling (our analysis uses fixed-size batches), clipping threshold c = 1 c = 1 c = 1 following De et al. [19 ] , ε = 8 \varepsilon= 8 ε = 8 , and δ = 1 / ( 2 n ) \delta= 1/(2n) δ = 1/ ( 2 n ) . For each optimizer and batch size B B B we grid-search the learning rate and the momentum 1 − α 1-\alpha 1 − α , with zero weight decay; grids are listed in Appendix § 14 . To make models compatible with per-example clipping, BatchNorm layers are replaced by GroupNorm and biases are disabled in all linear layers. We report the best value over the grid for each B B B . The CIFAR-10 curves average three seeds; all language-modeling results and all heatmaps are single runs. For DP-SGD on CIFAR-10 (B ≥ 256 B \ge256 B ≥ 256 ) and for Scion at B = 16,384 B = 16{,}384 B = 16 , 384 , the best learning rate lies at the upper end of the grid (Appendix § 14 ), so these baselines may be slightly under-tuned. Note that the hyperparameter search itself is not included in the privacy accounting, as is common in the DP literature (Papernot and Steinke [62 ] ). Note that we utilize standard momentum for SGD and Muon optimizers (equivalent to nesterov=False in PyTorch).
Image classification. We train the CIFAR Airbench architecture (Jordan (2024), 2M parameters). Without privacy (Figure 1 , left), Muon attains the lowest test loss at every batch size, with its minimum (below 1.05) at B = 256 B = 256 B = 256 , whereas Adam and SGD are best at B ≤ 128 B \le128 B ≤ 128 . With privacy (right), the picture changes in two ways. First, all optimizers prefer batches that are one to two orders of magnitude larger, with minima at B = 5000 B = 5000 B = 5000 –10000, in line with prior observations for DP-SGD ([19 , 69 ] ). Second, the gaps between optimizers largely disappear: for 128 ≤ B ≤ 1024 128 \le B \le1024 128 ≤ B ≤ 1024 the three curves overlap within one standard deviation. DP-Muon attains the lowest test loss at every batch size except B = 10000 B = 10000 B = 10000 , where DP-SGD is marginally better, but the differences exceed one standard deviation only at the extremes B = 64 B = 64 B = 64 and B = 25000 B = 25000 B = 25000 , where DP-Muon degrades the least. Across privacy levels at B = 1024 B = 1024 B = 1024 (Appendix § 14 .§ 2 ), DP-Muon is on par with or slightly better than DP-SGD and DP-Adam for ε ∈ { 1 , 5 , 8 } \varepsilon\in\{1,5,8\} ε ∈ { 1 , 5 , 8 } , with the largest margin over DP-Adam at ε = 1 \varepsilon= 1 ε = 1 ; at ε = 3 \varepsilon= 3 ε = 3 the three methods are within noise.
Figure 1. Best test loss as a function of batch size for SGD, Adam, and Muon. All plotted values represent the optimal configuration found across the learning rate and momentum grid search. (Left ) Standard non-private training. (Right ) Differentially private (DP) training for 80 epochs. We perform three independent runs to compute the reported deviation intervals.
Language modeling. The model consists of 6 layers, 6 attention heads, an embedding dimension of 384, and a vocabulary of 50,304 tokens. It is trained on sequences of length 1,024 for 600 million tokens from the 10-billion-token subset of FineWeb (Penedo et al. [65 ] , equating to roughly 20 tokens per parameter.
The training set is a fixed random subset of n ≈ 5.86 ⋅ 10 5 n \approx5.86 \cdot10^{5} n ≈ 5.86 ⋅ 1 0 5 sequences from this pool, processed for one epoch with Poisson sampling rate q = B / n q = B/n q = B / n and δ = 1 / ( 2 n ) \delta= 1/(2n) δ = 1/ ( 2 n ) ; this translates to approximately 18,300 steps for a batch size of B = 32 B = 32 B = 32 , down to 36 steps for a maximum batch size of B = 16,384 B = 16{,}384 B = 16 , 384 . We define a single sequence of 1,024 tokens as the privacy unit, so a document that spans several sequences is not protected as a whole.
In the non-private baseline, the performance ranking (Muon < Adam < SGD) holds across all batch sizes, and Muon’s advantage grows with B B B (achieving a final loss of 4.10 versus 4.82 for Adam at B = 1024 B = 1024 B = 1024 ). Under differential privacy (right), the optimal batch size shifts from 32–64 up to 1024–4096, and the optimizer ranking becomes dependent on B B B . DP-Muon has the lowest loss for B ≤ 256 B \le256 B ≤ 256 , by at most 0.09 nats in single runs; DP-Adam is optimal for $512 \le B \le 2048$ and attains the lowest overall loss (6.33 at B = 1024 B = 1024 B = 1024 , versus 6.51 for DP-Muon at $B = 2048); and DP-Scion, which utilizes sign updates for the embedding and output layers, performs best for B ≥ 4096 B \ge4096 B ≥ 4096 and exhibits the least degradation at very large batch sizes. At their respective optimal batch sizes, the four optimizers are within 0.25 nats of each other, compared to a gap of 0.9 nats between Muon and SGD without privacy.
What changes under privacy. We highlight three findings. (i) Batch size is the dominant hyperparameter on both tasks: at a fixed budget of epochs or tokens, the optimal batch size grows by a factor of 15–300, and the ranking of optimizers depends on it, so conclusions drawn at a single batch size, or transferred from non-private training, can be misleading. In both tasks the root-mean-square size of the privacy noise exceeds the root-mean-square bound c / B c/\sqrt{B} c / B on the sampling noise of clipped gradients by one to two orders of magnitude at every batch size and decays with B B B faster than B − 1 / 2 B^{-1/2} B − 1/2 , and the observed optima lie where its norm becomes comparable to the clipping radius (Figure 3 , Appendix § 11 .§ 1 ). There, the noise-to-signal ratio is about 4–27 times larger than the admissibility condition of Theorem 1 allows for 1 − α = 0.9 1-\alpha= 0.9 1 − α = 0.9 , so the theorem does not cover these configurations and does not explain the location of the optima (Appendix § 11 .§ 2 ). The dependence of the ranking on the batch size is consistent with reports of large gains for private Muon at large batches in vision ((Shanmagum et al., 2026)). (ii) The learning rate of DP-Muon grows with the batch size: for language modeling, from 0.05 at B ≤ 512 B \le512 B ≤ 512 to 0.2 at B ≥ 8192 B \ge8192 B ≥ 8192 , whereas the optimal learning rate of DP-Adam stays within [ 10 − 3 , 3 ⋅ 10 − 3 ] [10^{-3}, 3 \cdot10^{-3}] [ 1 0 − 3 , 3 ⋅ 1 0 − 3 ] , and without privacy, the optimal learning rate of every method on language modeling is the same at all batch sizes (Appendix § 14 .§ 3 ). (iii) DP-Muon is insensitive to the momentum: for DP language modeling, at the optimal learning rate, its loss varies by about 0.1 nats or less over momentum values 1 − α ∈ [ 0.8 , 0.95 ] 1 - \alpha\in[0.8, 0.95] 1 − α ∈ [ 0.8 , 0.95 ] at every batch size, so the selected momentum appears erratic across batch sizes (Appendix § 14 .§ 3 ). This is compatible with Theorem 1, in which a longer momentum window 1 / α 1/\alpha 1/ α reduces the filtered sampling and privacy noise (∝ α \propto\sqrt{\alpha} ∝ α ) but increases the tracking error (∝ L γ / α \propto L\gamma/\alpha ∝ L γ / α ).
Figure 3. Left: norm of the privacy noise added to the averaged gradient relative to the clipping radius, for the two experimental settings; shaded regions mark the observed DP-optimal batch sizes. Right: decay exponent of the privacy noise in the batch size; sampling noise has exponent 1/2.
Related Work
LMO-based methods. Beyond Scion and the trust-region analyses of [40 ] (); Kovalev and Borodich 2025), LMO-based methods include the layer-wise Gluon ([68 ] ), and the effect of replacing the polar factor by a few Newton–Schulz steps is analyzed by [73 ] and Kim and Oh (2026). None of these works consider per-example clipping or privacy noise; distributed and compressed variants are discussed in Appendix § 13 .
Clipping in private optimization. Analyses of per-example clipping are compared in § 3.3 . A complementary line replaces clipping by per-sample normalization, which removes the threshold ([13 , 87 ] ); we instead keep the standard clipping of DP-SGD and normalize only the aggregated momentum through the LMO. Nonlinear post-processing of privatized gradients creates its own bias, which can be corrected for Adam ([76 ] ) and for Newton–Schulz (Kim and Fan, 2026).
Training dynamics and hyperparameters under privacy. Large batches are crucial for accurate private training ([19 ] ); Sander et al. [69 ] show that the performance of DP-SGD is governed mainly by the total amount of injected noise, which allows hyperparameters to be tuned at small batch sizes, Panda et al. [61 ] propose a linear scaling rule to transfer hyperparameters across privacy budgets, McKenna et al. [54 ] derive scaling laws for private language models, and Papernot and Steinke [62 ] account for the privacy cost of tuning. Under privacy, the noise dominates Adam’s second-moment estimate, so that DP-Adam behaves like DP-SGD unless corrected ([76 ] ), and Monzio Compagnoni et al. [57 ] compare DP-SignSGD with DP-SGD through stochastic differential equations. For non-private LMO methods, Shulgin et al. [74 ] derive hyperparameter scaling laws by minimizing convergence bounds of the same form as Theorem 1.
Conclusion and Limitations
Muon is compatible with differential privacy because, for a scale-invariant update, the leading effect of per-example clipping is a harmless rescaling; the remaining directional bias is controlled by the centered variance alone, which yields convergence guarantees for private momentum-LMO methods in any norm whose clipping floor matches that of clipped SGD up to the norm-conversion constant ρ 1 \rho_1 ρ 1 . Empirically, privacy makes the batch size the dominant hyperparameter and reorders optimizers, so DP-Muon is most beneficial in some batch-size regimes rather than uniformly. Our analysis has limitations: it assumes an exact LMO rather than a few Newton–Schulz steps and fixed-size batches, whereas our experiments use Poisson subsampling; it treats the Gaussian noise through worst-case dual-norm bounds, which leads to the admissibility condition in (3) and excludes the hyperparameter regime of our experiments (entirely in the spectral geometry of DP-Muon, and except for CIFAR-10 at the largest batch size in the ℓ 2 \ell_2 ℓ 2 specialization); and its fixed-threshold bound retains a clipping floor. Our language-modeling experiments are small-scale pretraining from scratch; private fine-tuning of pretrained models [44 ] (Kim and Fan 2026) is a natural next step.
Acknowledgements
The research reported in this publication was supported by funding from King Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme, ii) CRG Grant ORFSCRG12-2024-6460, and iii) Center of Excellence for Generative AI, under award number 5940.
Prerequisites
Throughout the appendix, Assumptions 1 and 2 from § 2 hold.
Definition 2 (Dual norm). Let ( X , ∥ ⋅ ∥ ) (\mathcal{X}, \lVert\cdot\rVert) ( X , ∥ ⋅ ∥) be a finite-dimensional normed vector space with dual space X ∗ \mathcal{X}^{\ast} X ∗ . The dual norm is
∥ v ∥ ∗ : = sup ∥ d ∥ ≤ 1 ⟨ v , d ⟩ , v ∈ X ∗ . \lVert v \rVert_{\ast} := \sup_{\lVert d \rVert\le1} \langle v,d\rangle,\quad v \in\mathcal{X}^{\ast}. ∥ v ∥ ∗ := ∥ d ∥ ≤ 1 sup ⟨ v , d ⟩ , v ∈ X ∗ .
Definition 3 (Linear minimization oracle (LMO)). For C = { x ∈ X : ∥ x ∥ ≤ 1 } C = \{x \in\mathcal{X} : \lVert x\rVert\le1\} C = { x ∈ X : ∥ x ∥ ≤ 1 } , LMO ( v ) : = arg min d ∈ C ⟨ v , d ⟩ \operatorname{LMO}(v) := \operatorname*{arg\,min}_{d \in C} \langle v,d\rangle LMO ( v ) := arg min d ∈ C ⟨ v , d ⟩ for v ∈ X ⋆ v \in\mathcal{X}^{\star} v ∈ X ⋆ ; when the minimizer is not unique, any minimizer may be used.
Corollary 2. For any d ∈ LMO ( v ) d \in\operatorname{LMO}(v) d ∈ LMO ( v ) , Definitions 2 and 3 give ⟨ v , d ⟩ = − ∥ v ∥ ⋆ \langle v,d\rangle= -\lVert v\rVert_{\star} ⟨ v , d ⟩ = − ∥ v ∥ ⋆ ; moreover, LMO ( λ v ) = LMO ( v ) \operatorname{LMO}(\lambda v) = \operatorname{LMO}(v) LMO ( λ v ) = LMO ( v ) for every λ > 0 \lambda> 0 λ > 0 .
Definition 4 (Norm-equivalence constants). Since X \mathcal{X} X is finite-dimensional, there exist ρ 1 , ρ 2 > 0 \rho_1,\rho_2 > 0 ρ 1 , ρ 2 > 0 such that
∥ v ∥ ⋆ ≤ ρ 1 ∥ v ∥ 2 , ∥ v ∥ 2 ≤ ρ 2 ∥ v ∥ ⋆ ∀ v ∈ X ⋆ . (4) \lVert v\rVert_{\star} \le\rho_1 \lVert v\rVert_2,\qquad\lVert v\rVert_2 \le\rho_2 \lVert v\rVert_{\star}\qquad\forall v \in\mathcal{X}^{\star}. \tag*{(4)} ∥ v ∥ ⋆ ≤ ρ 1 ∥ v ∥ 2 , ∥ v ∥ 2 ≤ ρ 2 ∥ v ∥ ⋆ ∀ v ∈ X ⋆ . (4)
Table 2 lists the LMO, the constants ρ 1 , ρ 2 \rho_1,\rho_2 ρ 1 , ρ 2 , and the order of E ∥ Z ∥ ⋆ \mathbb{E}\lVert Z\rVert_{\star} E ∥ Z ∥ ⋆ for Z ∼ N ( 0 , I ) Z \sim\mathcal{N}(0,I) Z ∼ N ( 0 , I ) (which enters the privacy-noise term) for common geometries.
By Assumption 1, for all x , y ∈ X x,y \in\mathcal{X} x , y ∈ X ,
f ( y ) ≤ f ( x ) + ⟨ ∇ f ( x ) , y − x ⟩ + L 2 ∥ y − x ∥ 2 . (5) f(y) \le f(x) + \langle\nabla f(x),y-x\rangle+ \frac{L}{2}\lVert y-x\rVert^2. \tag*{(5)} f ( y ) ≤ f ( x ) + ⟨ ∇ f ( x ) , y − x ⟩ + 2 L ∥ y − x ∥ 2 . (5)
Corollary 3. For every x x x , write ∇ f i ( x ) = ∇ f ( x ) + ξ i \nabla f_i(x)=\nabla f(x)+\xi_i ∇ f i ( x ) = ∇ f ( x ) + ξ i with i ∼ Unif [ n ] i\sim\operatorname{Unif}[n] i ∼ Unif [ n ] . By Assumption 2,
E i [ ξ i ] = 1 n ∑ i = 1 n ξ i = 0 , E i [ ∥ ξ i ∥ 2 2 ] = 1 n ∑ i = 1 n ∥ ξ i ∥ 2 2 ≤ σ 2 . \mathbb{E}_i[\xi_i]=\frac{1}{n}\sum_{i=1}^{n}\xi_i=0,\qquad\mathbb{E}_i[\lVert\xi_i\rVert_2^2]=\frac{1}{n}\sum_{i=1}^{n}\lVert\xi_i\rVert_2^2\le\sigma^2. E i [ ξ i ] = n 1 i = 1 ∑ n ξ i = 0 , E i [∥ ξ i ∥ 2 2 ] = n 1 i = 1 ∑ n ∥ ξ i ∥ 2 2 ≤ σ 2 .
Define the clipping factor
a c ( v ) : = c max { c , ∥ v ∥ 2 } , so that clip c ( v ) = a c ( v ) v . a_c(v):=\frac{c}{\max\{c,\lVert v\rVert_2\}},
\qquad\text{so that}\qquad\operatorname{clip}_c(v)=a_c(v)\,v. a c ( v ) := max { c , ∥ v ∥ 2 } c , so that clip c ( v ) = a c ( v ) v .
Corollary 4. Since v ↦ max { c , ∥ v ∥ 2 } v\mapsto\max\{c,\lVert v\rVert_2\} v ↦ max { c , ∥ v ∥ 2 } is 1 1 1 -Lipschitz ,
∣ a c ( y ) − a c ( x ) ∣ ≤ a c ( y ) a c ( x ) c ∥ y − x ∥ 2 . (6) |a_c(y)-a_c(x)|\le\frac{a_c(y)a_c(x)}{c}\lVert y-x\rVert_2. \tag*{(6)} ∣ a c ( y ) − a c ( x ) ∣ ≤ c a c ( y ) a c ( x ) ∥ y − x ∥ 2 . (6)
DP-Muon convergence
Notation
Let:
f ( x ) : = 1 n ∑ i = 1 n f i ( x ) , n = ∣ D ∣ . f(x):=\frac{1}{n}\sum_{i=1}^{n}f_i(x),\qquad n=|\mathcal{D}|. f ( x ) := n 1 i = 1 ∑ n f i ( x ) , n = ∣ D ∣.
At iteration k k k , independently of previous sampling and Gaussian noise, draw
S k ∼ Unif { S ⊆ [ n ] : ∣ S ∣ = B } . S_k\sim\operatorname{Unif}\{S\subseteq[n]:|S|=B\}. S k ∼ Unif { S ⊆ [ n ] : ∣ S ∣ = B } .
And compute private averaged gradient
g ^ k = 1 B ∑ i ∈ S k clip c ( ∇ f i ( x k ) ) + z k . \hat{g}_k = \frac{1}{B}\sum_{i\in S_k}\operatorname{clip}_c(\nabla f_i(x_k)) + z_k. g ^ k = B 1 i ∈ S k ∑ clip c ( ∇ f i ( x k )) + z k .
We define the clipped mini-batch average:
g ˉ k = 1 B ∑ i ∈ S k clip c ( ∇ f i ( x k ) ) . \bar{g}_k = \frac{1}{B}\sum_{i\in S_k}\operatorname{clip}_c(\nabla f_i(x_k)). g ˉ k = B 1 i ∈ S k ∑ clip c ( ∇ f i ( x k )) .
In the subsequent lemmas, we will use a simplified notation. Assuming a deterministic vector g g g and a stochastic noise vector ξ i \xi_i ξ i satisfying Corollary 3, we write:
μ ( g ) : = 1 n ∑ i = 1 n clip c ( g + ξ i ) . \mu(g) := \frac{1}{n}\sum_{i=1}^{n}\operatorname{clip}_c(g+\xi_i). μ ( g ) := n 1 i = 1 ∑ n clip c ( g + ξ i ) .
We inject Gaussian privacy noise:
z k ∼ N ( 0 , c 2 σ D P 2 I ) , E [ z k ] = 0 , E ∥ z k ∥ 2 2 : = d c 2 σ D P 2 . z_k \sim\mathcal{N}(0,c^2\sigma_{\mathrm{DP}}^2 I), \qquad\mathbb{E}[z_k]=0, \qquad\mathbb{E}\lVert z_k\rVert_2^2 := dc^2\sigma_{\mathrm{DP}}^2. z k ∼ N ( 0 , c 2 σ DP 2 I ) , E [ z k ] = 0 , E ∥ z k ∥ 2 2 := d c 2 σ DP 2 .
From the algorithm definition, the overall oracle is:
g ^ k : = g ˉ k + z k . (7) \hat{g}_k := \bar{g}_k + z_k. \tag*{(7)} g ^ k := g ˉ k + z k . (7)
For notational convenience, define
σ ~ : = ρ 1 σ , b ~ c : = ρ 1 min { σ , σ 2 c } . (8) \tilde{\sigma} := \rho_1\sigma,\qquad\tilde{b}_c := \rho_1\min\left\{\sigma,\frac{\sigma^2}{c}\right\}. \tag*{(8)} σ ~ := ρ 1 σ , b ~ c := ρ 1 min { σ , c σ 2 } . (8)
Define the pre-batch filtration representing the complete history of the algorithm prior to drawing the batch S t S_t S t and privacy noise z t z_t z t (x t x_t x t is determined):
F t : = σ ( x 0 , { S s , z s } s = 0 t − 1 ) . (9) \mathcal{F}_t := \sigma\left(x_0,\{S_s,z_s\}_{s=0}^{t-1}\right). \tag*{(9)} F t := σ ( x 0 , { S s , z s } s = 0 t − 1 ) . (9)
Useful lemmas
Lemma 1 in the main text combines Lemmas 4 and 5 below, and Lemma 2 is Lemma 3 .
Throughout this subsection ξ \xi ξ denotes ξ i \xi_i ξ i with i ∼ Unif [ n ] i\sim\operatorname{Unif}[n] i ∼ Unif [ n ] , and E , P \mathbb{E},\mathbb{P} E , P are with respect to i i i ; by Corollary 3, E ξ = 0 \mathbb{E}\xi=0 E ξ = 0 and E ∥ ξ ∥ 2 ≤ σ 2 \mathbb{E}\lVert\xi\rVert^2\leq\sigma^2 E ∥ ξ ∥ 2 ≤ σ 2 .
For m , g ∈ X ⋆ m,g\in\mathcal{X}^\star m , g ∈ X ⋆ , define the error
R ( m , g ) : = inf λ > 0 ∥ m − λ g ∥ ⋆ λ . (10) \mathcal{R}(m,g):=\inf_{\lambda>0}\frac{\lVert m-\lambda g\rVert_\star}{\lambda}. \tag*{(10)} R ( m , g ) := λ > 0 inf λ ∥ m − λ g ∥ ⋆ . (10)
Lemma 3 (Inner Product Bound). Let d ∈ LMO ( m ) d\in\operatorname{LMO}(m) d ∈ LMO ( m ) . Then
⟨ g , d ⟩ ≤ − ∥ g ∥ ⋆ + 2 R ( m , g ) . (11) \langle g,d\rangle\leq-\lVert g\rVert_\star+2\mathcal{R}(m,g). \tag*{(11)} ⟨ g , d ⟩ ≤ − ∥ g ∥ ⋆ + 2 R ( m , g ) . (11)
Proof. Fix any λ > 0 \lambda>0 λ > 0 . By Corollary 2,
λ ⟨ g , d ⟩ = ⟨ m , d ⟩ − ⟨ m − λ g , d ⟩ ≤ − ∥ m ∥ ⋆ + ∥ m − λ g ∥ ⋆ ≤ − λ ∥ g ∥ ⋆ + 2 ∥ m − λ g ∥ ⋆ . \begin{aligned}
\lambda\langle g,d\rangle&= \langle m,d\rangle-\langle m-\lambda g,d\rangle\\
&\leq-\lVert m\rVert_\star+\lVert m-\lambda g\rVert_\star\\
&\leq-\lambda\lVert g\rVert_\star+2\lVert m-\lambda g\rVert_\star.
\end{aligned} λ ⟨ g , d ⟩ = ⟨ m , d ⟩ − ⟨ m − λ g , d ⟩ ≤ − ∥ m ∥ ⋆ + ∥ m − λ g ∥ ⋆ ≤ − λ ∥ g ∥ ⋆ + 2 ∥ m − λ g ∥ ⋆ .
Divide by λ \lambda λ and take the infimum over λ > 0 \lambda>0 λ > 0 . □ \square □
Lemma 4 (Clipping Bias Smooth Bound). For every g g g , there exists a scalar λ ( g ) > 0 \lambda(g) > 0 λ ( g ) > 0 such that
1 4 a c ( g ) ≤ λ ( g ) ≤ 2 a c ( g ) , (12) \frac{1}{4}a_c(g) \le\lambda(g) \le2a_c(g), \tag*{(12)} 4 1 a c ( g ) ≤ λ ( g ) ≤ 2 a c ( g ) , (12) and
∥ μ ( g ) − λ ( g ) g ∥ 2 ≤ 16 λ ( g ) min { σ , σ 2 c } . \lVert\mu(g) - \lambda(g)g \rVert_2 \le16\lambda(g) \min\left\{\sigma,\frac{\sigma^2}{c}\right\}. ∥ μ ( g ) − λ ( g ) g ∥ 2 ≤ 16 λ ( g ) min { σ , c σ 2 } . Consequently,
∥ μ ( g ) − λ ( g ) g ∥ ⋆ ≤ 16 λ ( g ) b ~ c . \lVert\mu(g) - \lambda(g)g \rVert_{\star} \le16\lambda(g)\widetilde{b}_c. ∥ μ ( g ) − λ ( g ) g ∥ ⋆ ≤ 16 λ ( g ) b c . Proof. Case 1: c ≥ σ c \ge\sigma c ≥ σ . Since
max { c , ∥ g + ξ ∥ 2 } ≤ max { c , ∥ g ∥ 2 } + ∥ ξ ∥ 2 , \max\{c,\lVert g+\xi\rVert_2\} \le\max\{c,\lVert g\rVert_2\}+\lVert\xi\rVert_2, max { c , ∥ g + ξ ∥ 2 } ≤ max { c , ∥ g ∥ 2 } + ∥ ξ ∥ 2 , we have
a c ( g + ξ ) = c max { c , ∥ g + ξ ∥ 2 } ≥ c max { c , ∥ g ∥ 2 } + ∥ ξ ∥ 2 = a c ( g ) 1 + a c ( g ) ∥ ξ ∥ 2 / c . a_c(g+\xi)=\frac{c}{\max\{c,\lVert g+\xi\rVert_2\}}\ge\frac{c}{\max\{c,\lVert g\rVert_2\}+\lVert\xi\rVert_2}=\frac{a_c(g)}{1+a_c(g)\lVert\xi\rVert_2/c}. a c ( g + ξ ) = max { c , ∥ g + ξ ∥ 2 } c ≥ max { c , ∥ g ∥ 2 } + ∥ ξ ∥ 2 c = 1 + a c ( g ) ∥ ξ ∥ 2 / c a c ( g ) . The map t ↦ ( 1 + t ) − 1 t\mapsto(1+t)^{-1} t ↦ ( 1 + t ) − 1 is convex on [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) , hence by Jensen’s inequality:
E [ a c ( g + ξ ) ] ≥ a c ( g ) 1 + a c ( g ) E ∥ ξ ∥ 2 / c ≥ a c ( g ) 2 , \mathbb{E}[a_c(g+\xi)]\ge\frac{a_c(g)}{1+a_c(g)\mathbb{E}\lVert\xi\rVert_2/c}\ge\frac{a_c(g)}{2}, E [ a c ( g + ξ )] ≥ 1 + a c ( g ) E ∥ ξ ∥ 2 / c a c ( g ) ≥ 2 a c ( g ) , where we used E ∥ ξ ∥ 2 ≤ σ ≤ c \mathbb{E}\lVert\xi\rVert_2\le\sigma\le c E ∥ ξ ∥ 2 ≤ σ ≤ c .
Using E [ ξ ] = 0 \mathbb{E}[\xi]=0 E [ ξ ] = 0 and (6) :
∥ E [ a c ( g + ξ ) ξ ] ∥ 2 = ∥ E [ ( a c ( g + ξ ) − a c ( g ) ) ξ ] ∥ 2 ≤ a c ( g ) c E [ a c ( g + ξ ) ∥ ξ ∥ 2 ] ≤ a c ( g ) σ 2 c . (13) \lVert\mathbb{E}[a_c(g+\xi)\xi]\rVert_2=\lVert\mathbb{E}[(a_c(g+\xi)-a_c(g))\xi]\rVert_2\le\frac{a_c(g)}{c}\mathbb{E}[a_c(g+\xi)\lVert\xi\rVert_2]\le a_c(g)\frac{\sigma^2}{c}. \tag*{(13)} ∥ E [ a c ( g + ξ ) ξ ] ∥ 2 = ∥ E [( a c ( g + ξ ) − a c ( g )) ξ ] ∥ 2 ≤ c a c ( g ) E [ a c ( g + ξ ) ∥ ξ ∥ 2 ] ≤ a c ( g ) c σ 2 . (13) Suppose first that
∥ g ∥ 2 ≥ 4 σ 2 c . \lVert g\rVert_2\ge\frac{4\sigma^2}{c}. ∥ g ∥ 2 ≥ c 4 σ 2 . Define
λ ( g ) : = ⟨ μ ( g ) , g / ∥ g ∥ 2 ⟩ ∥ g ∥ 2 = ⟨ μ ( g ) , g ⟩ ∥ g ∥ 2 2 . \lambda(g):=\frac{\langle\mu(g),g/\lVert g\rVert_2\rangle}{\lVert g\rVert_2}=\frac{\langle\mu(g),g\rangle}{\lVert g\rVert_2^2}. λ ( g ) := ∥ g ∥ 2 ⟨ μ ( g ) , g / ∥ g ∥ 2 ⟩ = ∥ g ∥ 2 2 ⟨ μ ( g ) , g ⟩ . Since
μ ( g ) = E [ a c ( g + ξ ) ( g + ξ ) ] = E [ a c ( g + ξ ) ] g + E [ a c ( g + ξ ) ξ ] , \mu(g)=\mathbb{E}\left[a_c(g+\xi)(g+\xi)\right]=\mathbb{E}[a_c(g+\xi)]g+\mathbb{E}[a_c(g+\xi)\xi], μ ( g ) = E [ a c ( g + ξ ) ( g + ξ ) ] = E [ a c ( g + ξ )] g + E [ a c ( g + ξ ) ξ ] , previously proven bound E [ a c ( g + ξ ) ] ≥ a c ( g ) 2 \mathbb{E}[a_c(g+\xi)]\ge\frac{a_c(g)}{2} E [ a c ( g + ξ )] ≥ 2 a c ( g ) , ∥ E [ a c ( g + ξ ) ξ ] ∥ 2 ≤ a c ( g ) σ 2 c \lVert\mathbb{E}[a_c(g+\xi)\xi]\rVert_2\le a_c(g)\frac{\sigma^2}{c} ∥ E [ a c ( g + ξ ) ξ ] ∥ 2 ≤ a c ( g ) c σ 2 and Cauchy–Schwarz imply:
λ ( g ) = E [ a c ( g + ξ ) ] + ⟨ E [ a c ( g + ξ ) ξ ] , g ⟩ ∥ g ∥ 2 2 ≥ a c ( g ) 2 − ∥ E [ a c ( g + ξ ) ξ ] ∥ 2 ∥ g ∥ 2 ∥ g ∥ 2 2 ≥ a c ( g ) 2 − a c ( g ) σ 2 c ∥ g ∥ 2 ≥ a c ( g ) 4 . \lambda(g)=\mathbb{E}[a_c(g+\xi)]+\frac{\langle\mathbb{E}[a_c(g+\xi)\xi],g\rangle}{\lVert g\rVert_2^2}\ge\frac{a_c(g)}{2}-\frac{\lVert\mathbb{E}[a_c(g+\xi)\xi]\rVert_2\lVert g\rVert_2}{\lVert g\rVert_2^2}\ge\frac{a_c(g)}{2}-\frac{a_c(g)\sigma^2}{c\lVert g\rVert_2}\ge\frac{a_c(g)}{4}. λ ( g ) = E [ a c ( g + ξ )] + ∥ g ∥ 2 2 ⟨ E [ a c ( g + ξ ) ξ ] , g ⟩ ≥ 2 a c ( g ) − ∥ g ∥ 2 2 ∥ E [ a c ( g + ξ ) ξ ] ∥ 2 ∥ g ∥ 2 ≥ 2 a c ( g ) − c ∥ g ∥ 2 a c ( g ) σ 2 ≥ 4 a c ( g ) . If ∥ g ∥ 2 ≥ c \lVert g\rVert_2\ge c ∥ g ∥ 2 ≥ c , then ∥ μ ( g ) ∥ 2 ≤ c = a c ( g ) ∥ g ∥ 2 \lVert\mu(g)\rVert_2\le c=a_c(g)\lVert g\rVert_2 ∥ μ ( g ) ∥ 2 ≤ c = a c ( g ) ∥ g ∥ 2 , so λ ( g ) ≤ ∥ μ ( g ) ∥ 2 ∥ g ∥ 2 ≤ c ∥ g ∥ 2 = a c ( g ) \lambda(g)\le\frac{\lVert\mu(g)\rVert_2}{\lVert g\rVert_2}\le\frac{c}{\lVert g\rVert_2}=a_c(g) λ ( g ) ≤ ∥ g ∥ 2 ∥ μ ( g ) ∥ 2 ≤ ∥ g ∥ 2 c = a c ( g ) . If ∥ g ∥ 2 < c \lVert g\rVert_2<c ∥ g ∥ 2 < c , then a c ( g ) = 1 a_c(g)=1 a c ( g ) = 1 and:
λ ( g ) = E [ a c ( g + ξ ) ] + ⟨ E [ a c ( g + ξ ) ξ ] , g ⟩ ∥ g ∥ 2 2 ≤ 1 + σ 2 c ∥ g ∥ 2 ≤ 5 4 = 5 4 a c ( g ) . \lambda(g)=\mathbb{E}[a_c(g+\xi)]+\frac{\langle\mathbb{E}[a_c(g+\xi)\xi],g\rangle}{\lVert g\rVert_2^2}\le1+\frac{\sigma^2}{c\lVert g\rVert_2}\le\frac{5}{4}=\frac{5}{4}a_c(g). λ ( g ) = E [ a c ( g + ξ )] + ∥ g ∥ 2 2 ⟨ E [ a c ( g + ξ ) ξ ] , g ⟩ ≤ 1 + c ∥ g ∥ 2 σ 2 ≤ 4 5 = 4 5 a c ( g ) . Thus (12) holds. By the definition of λ ( g ) \lambda(g) λ ( g ) , the residual is orthogonal to g g g . Combining with (13) we have:
∥ μ ( g ) − λ ( g ) g ∥ 2 ≤ ∥ E [ a c ( g + ξ ) ξ ] ∥ 2 ≤ a c ( g ) σ 2 c ≤ 4 λ ( g ) σ 2 c . \lVert\mu(g)-\lambda(g)g\rVert_2\le\lVert\mathbb{E}[a_c(g+\xi)\xi]\rVert_2\le a_c(g)\frac{\sigma^2}{c}\le4\lambda(g)\frac{\sigma^2}{c}. ∥ μ ( g ) − λ ( g ) g ∥ 2 ≤ ∥ E [ a c ( g + ξ ) ξ ] ∥ 2 ≤ a c ( g ) c σ 2 ≤ 4 λ ( g ) c σ 2 .
Now suppose that
∥ g ∥ 2 < 4 σ 2 c . \lVert g\rVert_2 < \frac{4\sigma^2}{c}. ∥ g ∥ 2 < c 4 σ 2 .
and choose λ ( g ) : = a c ( g ) \lambda(g) := a_c(g) λ ( g ) := a c ( g ) . Then
μ ( g ) − a c ( g ) g = ( E [ a c ( g + ξ ) ] − a c ( g ) ) g + E [ a c ( g + ξ ) ξ ] . \mu(g) - a_c(g)g = \left(\mathbb{E}[a_c(g+\xi)] - a_c(g)\right)g + \mathbb{E}[a_c(g+\xi)\xi]. μ ( g ) − a c ( g ) g = ( E [ a c ( g + ξ )] − a c ( g ) ) g + E [ a c ( g + ξ ) ξ ] .
The second term is bounded by a c ( g ) σ 2 / c a_c(g)\sigma^2/c a c ( g ) σ 2 / c . For the first term using (6) ,
∥ g ∥ 2 E ∣ a c ( g + ξ ) − a c ( g ) ∣ ≤ a c ( g ) ∥ g ∥ 2 c E [ a c ( g + ξ ) ∥ ξ ∥ 2 ] ≤ a c ( g ) ∥ g ∥ 2 σ c ≤ 4 a c ( g ) σ 2 c , \lVert g\rVert_2\mathbb{E}|a_c(g+\xi)-a_c(g)| \le\frac{a_c(g)\lVert g\rVert_2}{c}\mathbb{E}[a_c(g+\xi)\lVert\xi\rVert_2] \le a_c(g)\frac{\lVert g\rVert_2\sigma}{c} \le4a_c(g)\frac{\sigma^2}{c}, ∥ g ∥ 2 E ∣ a c ( g + ξ ) − a c ( g ) ∣ ≤ c a c ( g ) ∥ g ∥ 2 E [ a c ( g + ξ ) ∥ ξ ∥ 2 ] ≤ a c ( g ) c ∥ g ∥ 2 σ ≤ 4 a c ( g ) c σ 2 ,
where the last step uses both ∥ g ∥ 2 < 4 σ 2 / c \lVert g\rVert_2 < 4\sigma^2/c ∥ g ∥ 2 < 4 σ 2 / c and σ / c ≤ 1 \sigma/c \le1 σ / c ≤ 1 . Hence
∥ μ ( g ) − a c ( g ) g ∥ 2 ≤ 5 a c ( g ) σ 2 c . \lVert\mu(g)-a_c(g)g\rVert_2 \le5a_c(g)\frac{\sigma^2}{c}. ∥ μ ( g ) − a c ( g ) g ∥ 2 ≤ 5 a c ( g ) c σ 2 .
Case 2: c < σ c < \sigma c < σ . If ∥ g ∥ 2 < 8 σ \lVert g\rVert_2 < 8\sigma ∥ g ∥ 2 < 8 σ , choose λ ( g ) : = a c ( g ) \lambda(g) := a_c(g) λ ( g ) := a c ( g ) . Since
∥ μ ( g ) ∥ 2 ≤ c , ∥ a c ( g ) g ∥ 2 ≤ c , \lVert\mu(g)\rVert_2 \le c,\qquad\lVert a_c(g)g\rVert_2 \le c, ∥ μ ( g ) ∥ 2 ≤ c , ∥ a c ( g ) g ∥ 2 ≤ c ,
we obtain
∥ μ ( g ) − a c ( g ) g ∥ 2 ≤ 2 c . \lVert\mu(g)-a_c(g)g\rVert_2 \le2c. ∥ μ ( g ) − a c ( g ) g ∥ 2 ≤ 2 c .
If ∥ g ∥ 2 ≤ c \lVert g\rVert_2 \le c ∥ g ∥ 2 ≤ c , then a c ( g ) = 1 a_c(g)=1 a c ( g ) = 1 and 2 c ≤ 2 σ 2c\le2\sigma 2 c ≤ 2 σ . If ∥ g ∥ 2 > c \lVert g\rVert_2 > c ∥ g ∥ 2 > c , then a c ( g ) = c / ∥ g ∥ 2 a_c(g)=c/\lVert g\rVert_2 a c ( g ) = c / ∥ g ∥ 2 and ∥ g ∥ 2 < 8 σ \lVert g\rVert_2 < 8\sigma ∥ g ∥ 2 < 8 σ , which gives
2 c ≤ 16 a c ( g ) σ . 2c \le16a_c(g)\sigma. 2 c ≤ 16 a c ( g ) σ .
It remains to consider ∥ g ∥ 2 ≥ 8 σ \lVert g\rVert_2 \ge8\sigma ∥ g ∥ 2 ≥ 8 σ . Define the good event
G : = { ∥ ξ ∥ 2 ≤ ∥ g ∥ 2 / 2 } . \mathcal{G} := \{\lVert\xi\rVert_2 \le\lVert g\rVert_2/2\}. G := {∥ ξ ∥ 2 ≤ ∥ g ∥ 2 /2 } .
By Markov’s inequality,
q : = P ( G c ) ≤ 4 σ 2 ∥ g ∥ 2 2 ≤ 1 16 . q := \mathbb{P}(\mathcal{G}^{c}) \le\frac{4\sigma^2}{\lVert g\rVert_2^2} \le\frac{1}{16}. q := P ( G c ) ≤ ∥ g ∥ 2 2 4 σ 2 ≤ 16 1 .
On G \mathcal{G} G , we have ∥ g + ξ ∥ 2 ∈ [ ∥ g ∥ 2 / 2 , 3 ∥ g ∥ 2 / 2 ] \lVert g+\xi\rVert_2 \in[\lVert g\rVert_2/2,3\lVert g\rVert_2/2] ∥ g + ξ ∥ 2 ∈ [∥ g ∥ 2 /2 , 3 ∥ g ∥ 2 /2 ] and ∥ g ∥ 2 / 2 > c \lVert g\rVert_2/2 > c ∥ g ∥ 2 /2 > c . Therefore,
⟨ g ∥ g ∥ 2 , clip c ( g + ξ ) ⟩ = c ∥ g ∥ 2 + ⟨ g / ∥ g ∥ 2 , ξ ⟩ ∥ g + ξ ∥ 2 ≥ c 3 . \left\langle\frac{g}{\lVert g\rVert_2},\operatorname{clip}_c(g+\xi)\right\rangle
= c\frac{\lVert g\rVert_2+\langle g/\lVert g\rVert_2,\xi\rangle}{\lVert g+\xi\rVert_2}
\ge\frac{c}{3}. ⟨ ∥ g ∥ 2 g , clip c ( g + ξ ) ⟩ = c ∥ g + ξ ∥ 2 ∥ g ∥ 2 + ⟨ g / ∥ g ∥ 2 , ξ ⟩ ≥ 3 c .
On G c \mathcal{G}^{c} G c , the same inner product is at least − c -c − c . Consequently,
⟨ μ ( g ) , g ∥ g ∥ 2 ⟩ ≥ c 3 ( 1 − q ) − c q = c 3 ( 1 − 4 q ) ≥ c 4 . \left\langle\mu(g),\frac{g}{\lVert g\rVert_2}\right\rangle
\ge\frac{c}{3}(1-q)-cq
= \frac{c}{3}(1-4q)
\ge\frac{c}{4}. ⟨ μ ( g ) , ∥ g ∥ 2 g ⟩ ≥ 3 c ( 1 − q ) − c q = 3 c ( 1 − 4 q ) ≥ 4 c .
Set
λ ( g ) : = 1 ∥ g ∥ 2 ⟨ μ ( g ) , g ∥ g ∥ 2 ⟩ . \lambda(g) := \frac{1}{\lVert g\rVert_2}\left\langle\mu(g),\frac{g}{\lVert g\rVert_2}\right\rangle. λ ( g ) := ∥ g ∥ 2 1 ⟨ μ ( g ) , ∥ g ∥ 2 g ⟩ .
Then
a c ( g ) 4 ≤ λ ( g ) ≤ a c ( g ) . \frac{a_c(g)}{4} \le\lambda(g) \le a_c(g). 4 a c ( g ) ≤ λ ( g ) ≤ a c ( g ) .
Let P g ⊥ P_{g^\perp} P g ⊥ be the Euclidean projection onto the orthogonal complement of g g g . On G \mathcal{G} G ,
∥ P g ⊥ clip c ( g + ξ ) ∥ 2 ≤ 2 c ∥ g ∥ 2 ∥ ξ ∥ 2 . \left\lVert P_{g^\perp}\operatorname{clip}_c(g+\xi)\right\rVert_2 \le\frac{2c}{\lVert g\rVert_2}\lVert\xi\rVert_2. P g ⊥ clip c ( g + ξ ) 2 ≤ ∥ g ∥ 2 2 c ∥ ξ ∥ 2 .
whereas on G c \mathcal{G}^{c} G c it is at most c c c . Hence
∥ P g ⊥ μ ( g ) ∥ 2 ≤ 2 c σ ∥ g ∥ 2 + c q ≤ 5 c σ 2 ∥ g ∥ 2 = 5 2 a c ( g ) σ ≤ 10 λ ( g ) σ . \begin{aligned}
\lVert P_{g^{\perp}}\mu(g)\rVert_{2} \leq\frac{2c\sigma}{\lVert g\rVert_{2}}+c q \\
&\leq\frac{5c\sigma}{2\lVert g\rVert_{2}}=\frac{5}{2}a_{c}(g)\sigma\leq10\lambda(g)\sigma.
\end{aligned} ∥ P g ⊥ μ ( g ) ∥ 2 ≤ ∥ g ∥ 2 2 c σ + c q ≤ 2 ∥ g ∥ 2 5 c σ = 2 5 a c ( g ) σ ≤ 10 λ ( g ) σ .
By construction, μ ( g ) − λ ( g ) g = P g ⊥ μ ( g ) \mu(g)-\lambda(g)g=P_{g^{\perp}}\mu(g) μ ( g ) − λ ( g ) g = P g ⊥ μ ( g ) .
Case g = 0 g=0 g = 0 . Choose λ ( 0 ) : = 1 \lambda(0):=1 λ ( 0 ) := 1 . If c < σ c<\sigma c < σ , then
∥ μ ( 0 ) ∥ 2 ≤ E [ min { ∥ ξ ∥ 2 , c } ] ≤ c < σ . \lVert\mu(0)\rVert_{2}\leq\mathbb{E}[\min\{\lVert\xi\rVert_{2},c\}]\leq c<\sigma. ∥ μ ( 0 ) ∥ 2 ≤ E [ min {∥ ξ ∥ 2 , c }] ≤ c < σ .
If c ≥ σ c\geq\sigma c ≥ σ , then
μ ( 0 ) = E [ clip c ( ξ ) − ξ ] , \mu(0)=\mathbb{E}[\operatorname{clip}_{c}(\xi)-\xi], μ ( 0 ) = E [ clip c ( ξ ) − ξ ] ,
and
∥ μ ( 0 ) ∥ 2 ≤ E [ ∥ ξ ∥ 2 1 { ∥ ξ ∥ 2 > c } ] ≤ E ∥ ξ ∥ 2 2 c ≤ σ 2 c . \lVert\mu(0)\rVert_{2}\leq\mathbb{E}[\lVert\xi\rVert_{2}\mathbf{1}\{\lVert\xi\rVert_{2}>c\}]\leq\frac{\mathbb{E}\lVert\xi\rVert_{2}^{2}}{c}\leq\frac{\sigma^{2}}{c}. ∥ μ ( 0 ) ∥ 2 ≤ E [∥ ξ ∥ 2 1 {∥ ξ ∥ 2 > c }] ≤ c E ∥ ξ ∥ 2 2 ≤ c σ 2 .
This completes the proof.
Lemma 5 (Clipping Variance). With the notation of Lemma 4 ,
E ∥ clip c ( g + ξ ) − μ ( g ) ∥ 2 2 ≤ 20 a c ( g ) 2 σ 2 ≤ 320 λ ( g ) 2 σ 2 . (14) \mathbb{E}\lVert\operatorname{clip}_{c}(g+\xi)-\mu(g)\rVert_{2}^{2}\leq20a_{c}(g)^{2}\sigma^{2}\leq320\lambda(g)^{2}\sigma^{2}. \tag*{(14)} E ∥ clip c ( g + ξ ) − μ ( g ) ∥ 2 2 ≤ 20 a c ( g ) 2 σ 2 ≤ 320 λ ( g ) 2 σ 2 . (14) Proof. Because the mean minimizes the mean-square error:
E ∥ clip c ( g + ξ ) − μ ( g ) ∥ 2 2 ≤ E ∥ clip c ( g + ξ ) − clip c ( g ) ∥ 2 2 . \mathbb{E}\lVert\operatorname{clip}_{c}(g+\xi)-\mu(g)\rVert_{2}^{2}\leq\mathbb{E}\lVert\operatorname{clip}_{c}(g+\xi)-\operatorname{clip}_{c}(g)\rVert_{2}^{2}. E ∥ clip c ( g + ξ ) − μ ( g ) ∥ 2 2 ≤ E ∥ clip c ( g + ξ ) − clip c ( g ) ∥ 2 2 . If ∥ g ∥ 2 ≤ 2 c \lVert g\rVert_{2}\leq2c ∥ g ∥ 2 ≤ 2 c , the clipping scalar satisfies a c ( g ) ≥ 1 / 2 a_{c}(g)\geq1/2 a c ( g ) ≥ 1/2 . Because Euclidean projection onto the radius-c c c ball is non-expansive,
E ∥ clip c ( g + ξ ) − clip c ( g ) ∥ 2 2 ≤ E ∥ ξ ∥ 2 2 ≤ σ 2 ≤ 4 a c ( g ) 2 σ 2 . \mathbb{E}\lVert\operatorname{clip}_{c}(g+\xi)-\operatorname{clip}_{c}(g)\rVert_{2}^{2}\leq\mathbb{E}\lVert\xi\rVert_{2}^{2}\leq\sigma^{2}\leq4a_{c}(g)^{2}\sigma^{2}. E ∥ clip c ( g + ξ ) − clip c ( g ) ∥ 2 2 ≤ E ∥ ξ ∥ 2 2 ≤ σ 2 ≤ 4 a c ( g ) 2 σ 2 . Now suppose ∥ g ∥ 2 > 2 c \lVert g\rVert_{2}>2c ∥ g ∥ 2 > 2 c . Define the event where the noise is bounded relative to the gradient:
G : = { ∥ ξ ∥ 2 ≤ ∥ g ∥ 2 / 2 } . \mathcal{G}:=\{\lVert\xi\rVert_{2}\leq\lVert g\rVert_{2}/2\}. G := {∥ ξ ∥ 2 ≤ ∥ g ∥ 2 /2 } . By the reverse triangle inequality and the definition of G \mathcal{G} G (∥ ξ ∥ 2 ≤ ∥ g ∥ 2 / 2 \lVert\xi\rVert_{2}\leq\lVert g\rVert_{2}/2 ∥ ξ ∥ 2 ≤ ∥ g ∥ 2 /2 ), any vector v v v on the line segment connecting g g g and g + ξ g+\xi g + ξ has a length of at least:
∥ v ∥ 2 ≥ ∥ g ∥ 2 − ∥ ξ ∥ 2 ≥ ∥ g ∥ 2 2 > c . \lVert v\rVert_{2}\geq\lVert g\rVert_{2}-\lVert\xi\rVert_{2}\geq\frac{\lVert g\rVert_{2}}{2}>c. ∥ v ∥ 2 ≥ ∥ g ∥ 2 − ∥ ξ ∥ 2 ≥ 2 ∥ g ∥ 2 > c . Thus, the entire segment remains strictly outside the clipping ball.
Outside the ball, the clipping operator is the radial projection clip ( v ) = c v / ∥ v ∥ 2 \operatorname{clip}(v)=cv/\lVert v\rVert_{2} clip ( v ) = c v / ∥ v ∥ 2 . Its Jacobian matrix is:
J clip ( v ) = c ∥ v ∥ 2 ( I − v v T ∥ v ∥ 2 2 ) . J_{\operatorname{clip}}(v)=\frac{c}{\lVert v\rVert_{2}}\left(I-\frac{vv^{\mathsf{T}}}{\lVert v\rVert_{2}^{2}}\right). J clip ( v ) = ∥ v ∥ 2 c ( I − ∥ v ∥ 2 2 v v T ) . The term ( I − v v T / ∥ v ∥ 2 2 ) (I-vv^{\mathsf{T}}/\lVert v\rVert_{2}^{2}) ( I − v v T / ∥ v ∥ 2 2 ) is an orthogonal projection matrix onto the subspace perpendicular to v v v . Because orthogonal projections have a spectral norm of exactly 1 1 1 , the operator norm of the Jacobian is strictly determined by the scalar prefix:
∥ J clip ( v ) ∥ 2 = c ∥ v ∥ 2 ⋅ 1 ≤ c ∥ g ∥ 2 / 2 = 2 c ∥ g ∥ 2 = 2 a c ( g ) . \lVert J_{\operatorname{clip}}(v)\rVert_{2}=\frac{c}{\lVert v\rVert_{2}}\cdot1\leq\frac{c}{\lVert g\rVert_{2}/2}=\frac{2c}{\lVert g\rVert_{2}}=2a_{c}(g). ∥ J clip ( v ) ∥ 2 = ∥ v ∥ 2 c ⋅ 1 ≤ ∥ g ∥ 2 /2 c = ∥ g ∥ 2 2 c = 2 a c ( g ) .
Finally, by the local Lipschitz property of the clipping operator, we bound the distance between the outputs using the maximum operator norm along the line segment connecting the inputs:
∥ clip c ( g + ξ ) − clip c ( g ) ∥ 2 ≤ ( max v ∥ J clip ( v ) ∥ 2 ) ∥ ( g + ξ ) − g ∥ 2 ≤ 2 a c ( g ) ∥ ξ ∥ 2 . \left\|\operatorname{clip}_c(g+\xi)-\operatorname{clip}_c(g)\right\|_2 \le\left(\max_v \left\|J_{\operatorname{clip}}(v)\right\|_2\right)\left\|(g+\xi)-g\right\|_2 \le2a_c(g)\|\xi\|_2. ∥ clip c ( g + ξ ) − clip c ( g ) ∥ 2 ≤ ( v max ∥ J clip ( v ) ∥ 2 ) ∥ ( g + ξ ) − g ∥ 2 ≤ 2 a c ( g ) ∥ ξ ∥ 2 .
On the complement event G c G^c G c , the distance is bounded by the ball’s diameter, 2 c = 2 a c ( g ) ∥ g ∥ 2 2c=2a_c(g)\|g\|_2 2 c = 2 a c ( g ) ∥ g ∥ 2 . Applying Markov’s inequality to ∥ ξ ∥ 2 2 \|\xi\|_2^2 ∥ ξ ∥ 2 2 yields:
P ( G c ) = P ( ∥ ξ ∥ 2 2 > ∥ g ∥ 2 2 4 ) ≤ 4 σ 2 ∥ g ∥ 2 2 . \mathbb{P}(G^c)=\mathbb{P}\left(\|\xi\|_2^2>\frac{\|g\|_2^2}{4}\right)\le\frac{4\sigma^2}{\|g\|_2^2}. P ( G c ) = P ( ∥ ξ ∥ 2 2 > 4 ∥ g ∥ 2 2 ) ≤ ∥ g ∥ 2 2 4 σ 2 .
Summing over both events gives:
E ∥ clip c ( g + ξ ) − clip c ( g ) ∥ 2 2 ≤ E [ ( 2 a c ( g ) ∥ ξ ∥ 2 ) 2 ] + ( 2 a c ( g ) ∥ g ∥ 2 ) 2 P ( G c ) ≤ 4 a c ( g ) 2 σ 2 + 4 a c ( g ) 2 ∥ g ∥ 2 2 ( 4 σ 2 ∥ g ∥ 2 2 ) = 20 a c ( g ) 2 σ 2 . \begin{aligned}
\mathbb{E}\left\|\operatorname{clip}_c(g+\xi)-\operatorname{clip}_c(g)\right\|_2^2
&\le\mathbb{E}\left[(2a_c(g)\|\xi\|_2)^2\right]+(2a_c(g)\|g\|_2)^2\mathbb{P}(G^c)\\
&\le4a_c(g)^2\sigma^2+4a_c(g)^2\|g\|_2^2\left(\frac{4\sigma^2}{\|g\|_2^2}\right)\\
&=20a_c(g)^2\sigma^2.
\end{aligned} E ∥ clip c ( g + ξ ) − clip c ( g ) ∥ 2 2 ≤ E [ ( 2 a c ( g ) ∥ ξ ∥ 2 ) 2 ] + ( 2 a c ( g ) ∥ g ∥ 2 ) 2 P ( G c ) ≤ 4 a c ( g ) 2 σ 2 + 4 a c ( g ) 2 ∥ g ∥ 2 2 ( ∥ g ∥ 2 2 4 σ 2 ) = 20 a c ( g ) 2 σ 2 .
Finally, substituting the lower bound from (12) implies a c ( g ) 2 ≤ 16 λ ( g ) 2 a_c(g)^2\le16\lambda(g)^2 a c ( g ) 2 ≤ 16 λ ( g ) 2 , concluding the proof. □
Bias-corrected momentum and an exact master theorem
Define
m ‾ k : = m k + 1 1 − ( 1 − α ) k + 1 = ∑ t = 0 k w k , t g ^ t , w k , t : = α ( 1 − α ) k − t 1 − ( 1 − α ) k + 1 . \overline{m}_k:=\frac{m_{k+1}}{1-(1-\alpha)^{k+1}}=\sum_{t=0}^{k}w_{k,t}\widehat{g}_t,\qquad w_{k,t}:=\frac{\alpha(1-\alpha)^{k-t}}{1-(1-\alpha)^{k+1}}. m k := 1 − ( 1 − α ) k + 1 m k + 1 = t = 0 ∑ k w k , t g t , w k , t := 1 − ( 1 − α ) k + 1 α ( 1 − α ) k − t .
Note that,
LMO ( m k + 1 ) = LMO ( m ‾ k ) , ∑ t = 0 k w k , t = 1. \operatorname{LMO}(m_{k+1})=\operatorname{LMO}(\overline{m}_k),\qquad\sum_{t=0}^{k}w_{k,t}=1. LMO ( m k + 1 ) = LMO ( m k ) , t = 0 ∑ k w k , t = 1.
Denote
g k : = ∇ f ( x k ) , d k : = LMO ( m k + 1 ) . g_k:=\nabla f(x_k),\qquad d_k:=\operatorname{LMO}(m_{k+1}). g k := ∇ f ( x k ) , d k := LMO ( m k + 1 ) .
For every t t t , define
μ t : = μ ( g t ) = 1 n ∑ i = 1 n clip c ( ∇ f i ( x t ) ) . \mu_t:=\mu(g_t)=\frac{1}{n}\sum_{i=1}^{n}\operatorname{clip}_c\left(\nabla f_i(x_t)\right). μ t := μ ( g t ) = n 1 i = 1 ∑ n clip c ( ∇ f i ( x t ) ) .
According to the Lemma 4 , we choose 2 a c ( g t ) ≥ λ t ≥ 1 4 a c ( g t ) > 0 2a_c(g_t)\ge\lambda_t\ge\frac{1}{4}a_c(g_t)>0 2 a c ( g t ) ≥ λ t ≥ 4 1 a c ( g t ) > 0 and r t r_t r t such that
μ t = λ t ∇ f ( x t ) + r t , ∥ r t ∥ ⋆ ≤ 16 λ t b ~ c . (15) \mu_t=\lambda_t\nabla f(x_t)+r_t,\qquad\|r_t\|_{\star}\le16\lambda_t\widetilde b_c. \tag*{(15)} μ t = λ t ∇ f ( x t ) + r t , ∥ r t ∥ ⋆ ≤ 16 λ t b c . (15)
Define the scalar ray average
A k : = ∑ t = 0 k w k , t λ t > 0. A_k:=\sum_{t=0}^{k}w_{k,t}\lambda_t>0. A k := t = 0 ∑ k w k , t λ t > 0.
Define the centered mini-batch fluctuation
ε t : = 1 B ∑ i ∈ S t clip c ( ∇ f i ( x t ) ) − μ t . (16) \varepsilon_t:=\frac{1}{B}\sum_{i\in S_t}\operatorname{clip}_c\left(\nabla f_i(x_t)\right)-\mu_t. \tag*{(16)} ε t := B 1 i ∈ S t ∑ clip c ( ∇ f i ( x t ) ) − μ t . (16)
Because x t x_t x t , λ t \lambda_t λ t , and A t − 1 A_{t-1} A t − 1 are determined by F t \mathcal{F}_t F t , they are F t \mathcal{F}_t F t -measurable. Now we can derive the expectation and variance of ε t \varepsilon_t ε t (a direct consequence of (14) and sampling without replacement):
E [ ε t ∣ F t ] = 0 , E [ ∥ ε t ∥ 2 2 ∣ F t ] ≤ 320 λ t 2 σ 2 n − B B ( n − 1 ) ≤ 320 λ t 2 σ 2 B . (17) \mathbb{E}[\varepsilon_t \mid\mathcal{F}_t] = 0,\qquad
\mathbb{E}[\|\varepsilon_t\|_2^2 \mid\mathcal{F}_t] \le320\lambda_t^2\sigma^2\frac{n-B}{B(n-1)} \le\frac{320\lambda_t^2\sigma^2}{B}. \tag*{(17)} E [ ε t ∣ F t ] = 0 , E [ ∥ ε t ∥ 2 2 ∣ F t ] ≤ 320 λ t 2 σ 2 B ( n − 1 ) n − B ≤ B 320 λ t 2 σ 2 . (17)
Define the tracking terms
D k : = ∑ t = 0 k w k , t λ t ( g t − g k ) D_k := \sum_{t=0}^{k} w_{k,t}\lambda_t(g_t-g_k) D k := t = 0 ∑ k w k , t λ t ( g t − g k )
N k : = ∑ t = 0 k w k , t ε t N_k := \sum_{t=0}^{k} w_{k,t}\varepsilon_t N k := t = 0 ∑ k w k , t ε t
P k : = ∑ t = 0 k w k , t z t P_k := \sum_{t=0}^{k} w_{k,t}z_t P k := t = 0 ∑ k w k , t z t
Theorem 5 (Exact projective convergence reduction). Under Assumptions 1–2, the iterates of Algorithm 1 satisfy, for every γ > 0 \gamma> 0 γ > 0 , α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , and K ≥ 1 K \ge1 K ≥ 1 ,
1 K ∑ k = 0 K − 1 E ∥ g k ∥ ⋆ ≤ Φ 0 K γ + L γ 2 + 32 b ~ c + 2 K ∑ k = 0 K − 1 E [ ∥ D k ∥ ⋆ A k + ∥ N k ∥ ⋆ A k + ∥ P k ∥ ⋆ A k ] , (18) \frac{1}{K}\sum_{k=0}^{K-1}\mathbb{E}\|g_k\|_{\star}
\le\frac{\Phi_0}{K\gamma}+\frac{L\gamma}{2}+32\widetilde b_c+\frac{2}{K}\sum_{k=0}^{K-1}\mathbb{E}\left[\frac{\|D_k\|_{\star}}{A_k}+\frac{\|N_k\|_{\star}}{A_k}+\frac{\|P_k\|_{\star}}{A_k}\right], \tag*{(18)} K 1 k = 0 ∑ K − 1 E ∥ g k ∥ ⋆ ≤ K γ Φ 0 + 2 L γ + 32 b c + K 2 k = 0 ∑ K − 1 E [ A k ∥ D k ∥ ⋆ + A k ∥ N k ∥ ⋆ + A k ∥ P k ∥ ⋆ ] , (18) where Φ 0 : = f ( x 0 ) − f ⋆ \Phi_0 := f(x_0)-f^\star Φ 0 := f ( x 0 ) − f ⋆ .
Proof. By the L L L -smoothness of f f f and the constraint ∥ d k ∥ ≤ 1 \|d_k\| \le1 ∥ d k ∥ ≤ 1 , the single-step descent inequality is:
f ( x k + 1 ) ≤ f ( x k ) + γ ⟨ g k , d k ⟩ + L γ 2 2 . f(x_{k+1}) \le f(x_k) + \gamma\langle g_k,d_k\rangle+ \frac{L\gamma^2}{2}. f ( x k + 1 ) ≤ f ( x k ) + γ ⟨ g k , d k ⟩ + 2 L γ 2 .
The update direction is generated by the scale-invariant LMO, meaning LMO ( m k + 1 ) = LMO ( m ‾ k ) \operatorname{LMO}(m_{k+1})=\operatorname{LMO}(\overline m_k) LMO ( m k + 1 ) = LMO ( m k ) . Applying the projective LMO property (Lemma 3 ) to this direction yields:
⟨ g k , d k ⟩ ≤ − ∥ g k ∥ ⋆ + 2 R ( m ‾ k , g k ) . \langle g_k,d_k\rangle\le-\|g_k\|_{\star}+2\mathcal{R}(\overline m_k,g_k). ⟨ g k , d k ⟩ ≤ − ∥ g k ∥ ⋆ + 2 R ( m k , g k ) .
To bound this projective error, we expand the bias-corrected momentum. Using (15) and (16) , we decompose it as:
m ‾ k = ∑ t = 0 k w k , t ( g ‾ t + z t ) = ∑ t = 0 k w k , t ( λ t g t + r t + ε t + z t ) = ∑ t = 0 k w k , t λ t ( g t − g k ) + A k g k \begin{aligned}
\overline m_k=\sum_{t=0}^{k}w_{k,t}(\overline g_t+z_t) \\
&=\sum_{t=0}^{k}w_{k,t}\left(\lambda_t g_t+r_t+\varepsilon_t+z_t\right) \\
&=\sum_{t=0}^{k}w_{k,t}\lambda_t(g_t-g_k)+A_k g_k
\end{aligned} m k = t = 0 ∑ k w k , t ( g t + z t ) = t = 0 ∑ k w k , t ( λ t g t + r t + ε t + z t ) = t = 0 ∑ k w k , t λ t ( g t − g k ) + A k g k
+ ∑ t = 0 k w k , t r t + ∑ t = 0 k w k , t ε t + ∑ t = 0 k w k , t z t . \quad+\sum_{t=0}^{k}w_{k,t}r_t+\sum_{t=0}^{k}w_{k,t}\varepsilon_t+\sum_{t=0}^{k}w_{k,t}z_t. + t = 0 ∑ k w k , t r t + t = 0 ∑ k w k , t ε t + t = 0 ∑ k w k , t z t .
The clipping-ray residual satisfies
∥ ∑ t = 0 k w k , t r t ∥ ⋆ A k ≤ 16 b ~ c . \frac{\left\lVert\sum_{t=0}^{k} w_{k,t}r_t \right\rVert_\star}{A_k} \leq16\tilde{b}_c. A k ∑ t = 0 k w k , t r t ⋆ ≤ 16 b ~ c .
By taking the specific scaling factor λ = A k \lambda= A_k λ = A k in (10) , we can bound the projective error by the sum of these normalized component norms:
R ( m ‾ k , g k ) ≤ 16 b ~ c + ∥ D k ∥ ⋆ A k + ∥ N k ∥ ⋆ A k + ∥ P k ∥ ⋆ A k . \mathcal{R}(\overline{m}_k,g_k) \leq16\tilde{b}_c+\frac{\lVert D_k\rVert_\star}{A_k}+\frac{\lVert N_k\rVert_\star}{A_k}+\frac{\lVert P_k\rVert_\star}{A_k}. R ( m k , g k ) ≤ 16 b ~ c + A k ∥ D k ∥ ⋆ + A k ∥ N k ∥ ⋆ + A k ∥ P k ∥ ⋆ .
Substituting this back into the LMO bound gives:
E ⟨ g k , d k ⟩ ≤ − E ∥ g k ∥ ⋆ + 32 b ~ c + 2 E [ ∥ D k ∥ ⋆ A k + ∥ N k ∥ ⋆ A k + ∥ P k ∥ ⋆ A k ] . \mathbb{E}\langle g_k,d_k\rangle\leq-\mathbb{E}\lVert g_k\rVert_\star+32\tilde{b}_c+2\mathbb{E}\left[\frac{\lVert D_k\rVert_\star}{A_k}+\frac{\lVert N_k\rVert_\star}{A_k}+\frac{\lVert P_k\rVert_\star}{A_k}\right]. E ⟨ g k , d k ⟩ ≤ − E ∥ g k ∥ ⋆ + 32 b ~ c + 2 E [ A k ∥ D k ∥ ⋆ + A k ∥ N k ∥ ⋆ + A k ∥ P k ∥ ⋆ ] .
Plugging this inner product bound into the initial smoothness inequality yields:
f ( x k + 1 ) ≤ f ( x k ) − γ ∥ g k ∥ ⋆ + γ ( 32 b ~ c + 2 [ ∥ D k ∥ ⋆ A k + ∥ N k ∥ ⋆ A k + ∥ P k ∥ ⋆ A k ] ) + L γ 2 2 . f(x_{k+1}) \leq f(x_k)-\gamma\lVert g_k\rVert_\star+\gamma\left(32\tilde{b}_c+2\left[\frac{\lVert D_k\rVert_\star}{A_k}+\frac{\lVert N_k\rVert_\star}{A_k}+\frac{\lVert P_k\rVert_\star}{A_k}\right]\right)+\frac{L\gamma^2}{2}. f ( x k + 1 ) ≤ f ( x k ) − γ ∥ g k ∥ ⋆ + γ ( 32 b ~ c + 2 [ A k ∥ D k ∥ ⋆ + A k ∥ N k ∥ ⋆ + A k ∥ P k ∥ ⋆ ] ) + 2 L γ 2 .
Rearranging to isolate γ ∥ g k ∥ ⋆ \gamma\lVert g_k\rVert_\star γ ∥ g k ∥ ⋆ , summing from k = 0 k=0 k = 0 to K − 1 K-1 K − 1 , taking expectations, using the global lower bound f ( x K ) ≥ f ⋆ f(x_K)\geq f^\star f ( x K ) ≥ f ⋆ , and dividing the entire inequality by K γ K\gamma K γ proves (18) .
A closed-form specialization
This subsection gives one sufficient condition under which the exact tracking terms in Theorem 5 have the familiar momentum-LMO scaling. This condition is sufficient, not claimed to be necessary. Define:
a k : = min { 1 , c ∥ g k ∥ 2 } . a_k := \min\left\{1,\frac{c}{\lVert g_k\rVert_2}\right\}. a k := min { 1 , ∥ g k ∥ 2 c } .
Lemma 6 (A k A_k A k Bound). Suppose
ρ 2 L γ c ≤ α 4 . (19) \frac{\rho_2L\gamma}{c}\leq\frac{\alpha}{4}. \tag*{(19)} c ρ 2 L γ ≤ 4 α . (19) Then, for all k k k ,
a k 5 ≤ A k ≤ 8 a k 3 , 3 32 ≤ λ k A k ≤ 10. (20) \frac{a_k}{5}\leq A_k\leq\frac{8a_k}{3},\qquad\frac{3}{32}\leq\frac{\lambda_k}{A_k}\leq10. \tag*{(20)} 5 a k ≤ A k ≤ 3 8 a k , 32 3 ≤ A k λ k ≤ 10. (20)
Proof. Since ∥ d k ∥ ≤ 1 \lVert d_k\rVert\leq1 ∥ d k ∥ ≤ 1 ,
∥ g k − g k − 1 ∥ 2 ≤ ρ 2 ∥ g k − g k − 1 ∥ ⋆ ≤ ρ 2 L γ ∥ d k − 1 ∥ ≤ ρ 2 L γ . \lVert g_k-g_{k-1}\rVert_2\leq\rho_2\lVert g_k-g_{k-1}\rVert_\star\leq\rho_2L\gamma\lVert d_{k-1}\rVert\leq\rho_2L\gamma. ∥ g k − g k − 1 ∥ 2 ≤ ρ 2 ∥ g k − g k − 1 ∥ ⋆ ≤ ρ 2 L γ ∥ d k − 1 ∥ ≤ ρ 2 L γ .
By the reverse triangle inequality, setting h : = ρ 2 L γ / c h:=\rho_2L\gamma/c h := ρ 2 L γ / c implies
∥ g k ∥ 2 − ∥ g k − 1 ∥ 2 ≤ c h and ∥ g k − 1 ∥ 2 − ∥ g k ∥ 2 ≤ c h . \lVert g_k\rVert_2-\lVert g_{k-1}\rVert_2\leq ch\quad\text{and}\quad\lVert g_{k-1}\rVert_2-\lVert g_k\rVert_2\leq ch. ∥ g k ∥ 2 − ∥ g k − 1 ∥ 2 ≤ c h and ∥ g k − 1 ∥ 2 − ∥ g k ∥ 2 ≤ c h .
Because c h ≥ 0 ch\geq0 c h ≥ 0 , we can bound the maximum functions as follows:
max { c , ∥ g k ∥ 2 } ≤ max { c , ∥ g k − 1 ∥ 2 + c h } ≤ max { c , ∥ g k − 1 ∥ 2 } + c h , \max\{c,\lVert g_k\rVert_2\}\leq\max\{c,\lVert g_{k-1}\rVert_2+ch\}\leq\max\{c,\lVert g_{k-1}\rVert_2\}+ch, max { c , ∥ g k ∥ 2 } ≤ max { c , ∥ g k − 1 ∥ 2 + c h } ≤ max { c , ∥ g k − 1 ∥ 2 } + c h ,
max { c , ∥ g k − 1 ∥ 2 } ≤ max { c , ∥ g k ∥ 2 + c h } ≤ max { c , ∥ g k ∥ 2 } + c h . \max\{c,\lVert g_{k-1}\rVert_2\}\leq\max\{c,\lVert g_k\rVert_2+ch\}\leq\max\{c,\lVert g_k\rVert_2\}+ch. max { c , ∥ g k − 1 ∥ 2 } ≤ max { c , ∥ g k ∥ 2 + c h } ≤ max { c , ∥ g k ∥ 2 } + c h .
Since the scaling factor is defined as
a k = c max { c , ∥ g k ∥ 2 } , a_k=\frac{c}{\max\{c,\lVert g_k\rVert_2\}}, a k = max { c , ∥ g k ∥ 2 } c ,
we can expand the ratio a k / a k − 1 a_k/a_{k-1} a k / a k − 1 and apply the upper bound derived above:
a k a k − 1 = max { c , ∥ g k − 1 ∥ 2 } max { c , ∥ g k ∥ 2 } ≤ max { c , ∥ g k ∥ 2 } + c h max { c , ∥ g k ∥ 2 } = 1 + c h max { c , ∥ g k ∥ 2 } . \frac{a_k}{a_{k-1}} = \frac{\max\{c,\lVert g_{k-1}\rVert_2\}}{\max\{c,\lVert g_k\rVert_2\}} \le\frac{\max\{c,\lVert g_k\rVert_2\}+ch}{\max\{c,\lVert g_k\rVert_2\}} = 1+\frac{ch}{\max\{c,\lVert g_k\rVert_2\}}. a k − 1 a k = max { c , ∥ g k ∥ 2 } max { c , ∥ g k − 1 ∥ 2 } ≤ max { c , ∥ g k ∥ 2 } max { c , ∥ g k ∥ 2 } + c h = 1 + max { c , ∥ g k ∥ 2 } c h .
Because the denominator max { c , ∥ g k ∥ 2 } \max\{c,\lVert g_k\rVert_2\} max { c , ∥ g k ∥ 2 } is strictly bounded below by c c c , the fraction is at most c h / c = h ch/c=h c h / c = h . Thus,
a k a k − 1 ≤ 1 + h . \frac{a_k}{a_{k-1}} \le1+h. a k − 1 a k ≤ 1 + h .
By exact symmetry, applying the bound for max { c , ∥ g k ∥ 2 } \max\{c,\lVert g_k\rVert_2\} max { c , ∥ g k ∥ 2 } to the inverse ratio yields:
a k − 1 a k = max { c , ∥ g k ∥ 2 } max { c , ∥ g k − 1 ∥ 2 } ≤ max { c , ∥ g k − 1 ∥ 2 } + c h max { c , ∥ g k − 1 ∥ 2 } ≤ 1 + h . \frac{a_{k-1}}{a_k} = \frac{\max\{c,\lVert g_k\rVert_2\}}{\max\{c,\lVert g_{k-1}\rVert_2\}} \le\frac{\max\{c,\lVert g_{k-1}\rVert_2\}+ch}{\max\{c,\lVert g_{k-1}\rVert_2\}} \le1+h. a k a k − 1 = max { c , ∥ g k − 1 ∥ 2 } max { c , ∥ g k ∥ 2 } ≤ max { c , ∥ g k − 1 ∥ 2 } max { c , ∥ g k − 1 ∥ 2 } + c h ≤ 1 + h .
Inverting this result provides the lower bound, giving us the final two-sided inequality:
1 1 + h ≤ a k a k − 1 ≤ 1 + h . \frac{1}{1+h} \le\frac{a_k}{a_{k-1}} \le1+h. 1 + h 1 ≤ a k − 1 a k ≤ 1 + h .
Hence, for 0 ≤ t ≤ k 0\le t\le k 0 ≤ t ≤ k ,
a k ( 1 + h ) k − t ≤ a t ≤ a k ( 1 + h ) k − t . \frac{a_k}{(1+h)^{k-t}} \le a_t \le a_k(1+h)^{k-t}. ( 1 + h ) k − t a k ≤ a t ≤ a k ( 1 + h ) k − t .
Using λ t ∈ [ a t / 4 , 2 a t ] \lambda_t\in[a_t/4,2a_t] λ t ∈ [ a t /4 , 2 a t ] (Lemma 4 ), and the recursive bound a t ≤ a k ( 1 + h ) k − t a_t\le a_k(1+h)^{k-t} a t ≤ a k ( 1 + h ) k − t , we can rewrite the moving average by re-indexing the sum with j = k − t j=k-t j = k − t :
A k = ∑ t = 0 k ( 1 − α ) k − t λ t ∑ t = 0 k ( 1 − α ) k − t ≤ ∑ t = 0 k ( 1 − α ) k − t 2 a k ( 1 + h ) k − t ∑ t = 0 k ( 1 − α ) k − t = 2 a k ∑ j = 0 k [ ( 1 − α ) ( 1 + h ) ] j ∑ j = 0 k ( 1 − α ) j . A_k=\frac{\sum_{t=0}^{k}(1-\alpha)^{k-t}\lambda_t}{\sum_{t=0}^{k}(1-\alpha)^{k-t}}
\le\frac{\sum_{t=0}^{k}(1-\alpha)^{k-t}2a_k(1+h)^{k-t}}{\sum_{t=0}^{k}(1-\alpha)^{k-t}}
=2a_k\frac{\sum_{j=0}^{k}[(1-\alpha)(1+h)]^j}{\sum_{j=0}^{k}(1-\alpha)^j}. A k = ∑ t = 0 k ( 1 − α ) k − t ∑ t = 0 k ( 1 − α ) k − t λ t ≤ ∑ t = 0 k ( 1 − α ) k − t ∑ t = 0 k ( 1 − α ) k − t 2 a k ( 1 + h ) k − t = 2 a k ∑ j = 0 k ( 1 − α ) j ∑ j = 0 k [( 1 − α ) ( 1 + h ) ] j .
To bound this ratio of finite geometric series, we compare it to the ratio of their infinite series limits. For positive x , y ∈ ( 0 , 1 ) x,y\in(0,1) x , y ∈ ( 0 , 1 ) , such that x > y x>y x > y , the relationship ( ∑ j = 0 k x j ) / ( ∑ j = 0 k y j ) ≤ ( 1 − y ) / ( 1 − x ) (\sum_{j=0}^{k}x^j)/(\sum_{j=0}^{k}y^j)\le(1-y)/(1-x) ( ∑ j = 0 k x j ) / ( ∑ j = 0 k y j ) ≤ ( 1 − y ) / ( 1 − x ) holds. Applying this with y = 1 − α y=1-\alpha y = 1 − α and x = ( 1 − α ) ( 1 + h ) x=(1-\alpha)(1+h) x = ( 1 − α ) ( 1 + h ) yields:
∑ j = 0 k [ ( 1 − α ) ( 1 + h ) ] j ∑ j = 0 k ( 1 − α ) j ≤ 1 − ( 1 − α ) 1 − ( 1 − α ) ( 1 + h ) = α α − h + α h . \frac{\sum_{j=0}^{k}[(1-\alpha)(1+h)]^j}{\sum_{j=0}^{k}(1-\alpha)^j}
\le\frac{1-(1-\alpha)}{1-(1-\alpha)(1+h)}
=\frac{\alpha}{\alpha-h+\alpha h}. ∑ j = 0 k ( 1 − α ) j ∑ j = 0 k [( 1 − α ) ( 1 + h ) ] j ≤ 1 − ( 1 − α ) ( 1 + h ) 1 − ( 1 − α ) = α − h + α h α .
Because h ≤ α / 4 h\le\alpha/4 h ≤ α /4 (as we assumed in the lemma statement) and α < 1 \alpha<1 α < 1 , we can find the maximum of this fraction by minimizing its denominator:
α − h ( 1 − α ) ≥ α − α 4 ( 1 − α ) = 3 α 4 + α 2 4 ≥ 3 α 4 . \alpha-h(1-\alpha)\ge\alpha-\frac{\alpha}{4}(1-\alpha)=\frac{3\alpha}{4}+\frac{\alpha^2}{4}\ge\frac{3\alpha}{4}. α − h ( 1 − α ) ≥ α − 4 α ( 1 − α ) = 4 3 α + 4 α 2 ≥ 4 3 α .
Substituting this minimum back into the fraction gives the final upper bound:
α α − h + α h ≤ α 3 α / 4 = 4 3 . \frac{\alpha}{\alpha-h+\alpha h}\le\frac{\alpha}{3\alpha/4}=\frac{4}{3}. α − h + α h α ≤ 3 α /4 α = 3 4 .
Similarly, we establish the lower bound using λ t ≥ a t / 4 \lambda_t\ge a_t/4 λ t ≥ a t /4 and the inverse recursive bound a t ≥ a k ( 1 + h ) − ( k − t ) a_t\ge a_k(1+h)^{-(k-t)} a t ≥ a k ( 1 + h ) − ( k − t ) :
A k ≥ a k 4 ∑ j = 0 k [ ( 1 − α ) / ( 1 + h ) ] j ∑ j = 0 k ( 1 − α ) j . A_k\ge\frac{a_k}{4}\frac{\sum_{j=0}^{k}[(1-\alpha)/(1+h)]^j}{\sum_{j=0}^{k}(1-\alpha)^j}. A k ≥ 4 a k ∑ j = 0 k ( 1 − α ) j ∑ j = 0 k [( 1 − α ) / ( 1 + h ) ] j .
Here, the numerator’s geometric base z = ( 1 − α ) / ( 1 + h ) z=(1-\alpha)/(1+h) z = ( 1 − α ) / ( 1 + h ) is strictly less than the denominator’s base y = 1 − α y=1-\alpha y = 1 − α . Consequently, the finite series ratio is bounded below by its infinite counterpart ( 1 − y ) / ( 1 − z ) (1-y)/(1-z) ( 1 − y ) / ( 1 − z ) :
∑ j = 0 k [ ( 1 − α ) / ( 1 + h ) ] j ∑ j = 0 k ( 1 − α ) j ≥ 1 − ( 1 − α ) 1 − 1 − α 1 + h = α ( 1 + h ) α + h . \frac{\sum_{j=0}^{k}[(1-\alpha)/(1+h)]^j}{\sum_{j=0}^{k}(1-\alpha)^j}
\ge\frac{1-(1-\alpha)}{1-\frac{1-\alpha}{1+h}}
=\frac{\alpha(1+h)}{\alpha+h}. ∑ j = 0 k ( 1 − α ) j ∑ j = 0 k [( 1 − α ) / ( 1 + h ) ] j ≥ 1 − 1 + h 1 − α 1 − ( 1 − α ) = α + h α ( 1 + h ) .
Consider the function ϕ ( h ) = α ( 1 + h ) α + h \phi(h) = \frac{\alpha(1+h)}{\alpha+h} ϕ ( h ) = α + h α ( 1 + h ) on the interval [ 0 , α / 4 ] [0,\alpha/4] [ 0 , α /4 ] . Its derivative with respect to h h h is strictly negative, meaning the function is monotonically decreasing and must attain its absolute minimum at the upper boundary h = α / 4 h = \alpha/4 h = α /4 . Thus:
α ( 1 + h ) α + h ≥ α ( 1 + α / 4 ) α + α / 4 = 4 + α 5 ≥ 4 5 . \frac{\alpha(1+h)}{\alpha+h} \ge\frac{\alpha(1+\alpha/4)}{\alpha+\alpha/4} = \frac{4+\alpha}{5} \ge\frac{4}{5}. α + h α ( 1 + h ) ≥ α + α /4 α ( 1 + α /4 ) = 5 4 + α ≥ 5 4 .
Plugging this scalar back into our initial expression yields:
A k ≥ a k 4 ( 4 5 ) = a k 5 . A_k \ge\frac{a_k}{4}\left(\frac{4}{5}\right) = \frac{a_k}{5}. A k ≥ 4 a k ( 5 4 ) = 5 a k .
Combining these bounds with λ k ∈ [ a k / 4 , 2 a k ] \lambda_k \in[a_k/4, 2a_k] λ k ∈ [ a k /4 , 2 a k ] (Lemma 4 ) proves (20) .
Drift and sampling-noise bounds
Recall that
w k , t : = α ( 1 − α ) k − t 1 − ( 1 − α ) k + 1 . w_{k,t} := \frac{\alpha(1-\alpha)^{k-t}}{1-(1-\alpha)^{k+1}}. w k , t := 1 − ( 1 − α ) k + 1 α ( 1 − α ) k − t .
We define
β k : = α 1 − ( 1 − α ) k + 1 = w k , k . (21) \beta_k := \frac{\alpha}{1-(1-\alpha)^{k+1}} = w_{k,k}. \tag*{(21)} β k := 1 − ( 1 − α ) k + 1 α = w k , k . (21)
Consequently, the weights satisfy the recursion:
w k , t = ( β t ∏ i = t + 1 k − 1 ( 1 − β i ) ) ( 1 − β k ) = w k − 1 , t ( 1 − β k ) . (22) w_{k,t} = \left(\beta_t \prod_{i=t+1}^{k-1}(1-\beta_i)\right)(1-\beta_k) = w_{k-1,t}(1-\beta_k). \tag*{(22)} w k , t = ( β t i = t + 1 ∏ k − 1 ( 1 − β i ) ) ( 1 − β k ) = w k − 1 , t ( 1 − β k ) . (22)
Then
m ‾ 0 = g ^ 0 , m ‾ k = m k + 1 1 − ( 1 − α ) k + 1 = ( 1 − β k ) m ‾ k − 1 + β k g ^ k . \overline{m}_0 = \widehat{g}_0,\qquad\overline{m}_k = \frac{m_{k+1}}{1-(1-\alpha)^{k+1}} = (1-\beta_k)\overline{m}_{k-1}+\beta_k\widehat{g}_k. m 0 = g 0 , m k = 1 − ( 1 − α ) k + 1 m k + 1 = ( 1 − β k ) m k − 1 + β k g k .
Moreover, β k ≥ α \beta_k \ge\alpha β k ≥ α , and after the run-in iterations
k b : = ⌈ log 2 α ⌉ , (23) k_b := \left\lceil\frac{\log2}{\alpha}\right\rceil, \tag*{(23)} k b := ⌈ α log 2 ⌉ , (23)
we have β k ≤ 2 α \beta_k \le2\alpha β k ≤ 2 α .
Let
N k : = ∑ t = 0 k w k , t ε t , P k : = ∑ t = 0 k w k , t z t , N_k := \sum_{t=0}^{k} w_{k,t}\varepsilon_t,\qquad P_k := \sum_{t=0}^{k} w_{k,t}z_t, N k := t = 0 ∑ k w k , t ε t , P k := t = 0 ∑ k w k , t z t ,
and
D k : = ∑ t = 0 k w k , t λ t ( g t − g k ) . D_k := \sum_{t=0}^{k} w_{k,t}\lambda_t(g_t-g_k). D k := t = 0 ∑ k w k , t λ t ( g t − g k ) .
Lemma 7 (Useful Recursions).
A k = ( 1 − β k ) A k − 1 + β k λ k , A_k = (1-\beta_k)A_{k-1}+\beta_k\lambda_k, A k = ( 1 − β k ) A k − 1 + β k λ k , D k = ( 1 − β k ) D k − 1 + ( 1 − β k ) A k − 1 ( g k − 1 − g k ) , D_k = (1-\beta_k)D_{k-1}+(1-\beta_k)A_{k-1}(g_{k-1}-g_k), D k = ( 1 − β k ) D k − 1 + ( 1 − β k ) A k − 1 ( g k − 1 − g k ) , N k = ( 1 − β k ) N k − 1 + β k ε k . N_k = (1-\beta_k)N_{k-1}+\beta_k\varepsilon_k. N k = ( 1 − β k ) N k − 1 + β k ε k .
Proof. From (21) and (22) :
A k = ∑ t = 0 k w k , t λ t = ∑ t = 0 k − 1 w k , t λ t + w k , k λ k = ∑ t = 0 k − 1 ( 1 − β k ) w k − 1 , t λ t + β k λ k = ( 1 − β k ) ( ∑ t = 0 k − 1 w k − 1 , t λ t ) + β k λ k = ( 1 − β k ) A k − 1 + β k λ k , \begin{aligned}
A_k &= \sum_{t=0}^{k} w_{k,t}\lambda_t = \sum_{t=0}^{k-1} w_{k,t}\lambda_t + w_{k,k}\lambda_k = \sum_{t=0}^{k-1}(1-\beta_k)w_{k-1,t}\lambda_t + \beta_k\lambda_k \\
&= (1-\beta_k)\left(\sum_{t=0}^{k-1}w_{k-1,t}\lambda_t\right)+\beta_k\lambda_k=(1-\beta_k)A_{k-1}+\beta_k\lambda_k,
\end{aligned} A k = t = 0 ∑ k w k , t λ t = t = 0 ∑ k − 1 w k , t λ t + w k , k λ k = t = 0 ∑ k − 1 ( 1 − β k ) w k − 1 , t λ t + β k λ k = ( 1 − β k ) ( t = 0 ∑ k − 1 w k − 1 , t λ t ) + β k λ k = ( 1 − β k ) A k − 1 + β k λ k ,
D k = ∑ t = 0 k w k , t λ t ( g t − g k ) = ∑ t = 0 k − 1 w k , t λ t ( g t − g k ) = ( 1 − β k ) ∑ t = 0 k − 1 w k − 1 , t λ t ( g t − g k − 1 + g k − 1 − g k ) = ( 1 − β k ) ∑ t = 0 k − 1 w k − 1 , t λ t ( g t − g k − 1 ) + ( 1 − β k ) ( ∑ t = 0 k − 1 w k − 1 , t λ t ) ( g k − 1 − g k ) = ( 1 − β k ) D k − 1 + ( 1 − β k ) A k − 1 ( g k − 1 − g k ) , \begin{aligned}
D_k &= \sum_{t=0}^{k}w_{k,t}\lambda_t(g_t-g_k)=\sum_{t=0}^{k-1}w_{k,t}\lambda_t(g_t-g_k) \\
&= (1-\beta_k)\sum_{t=0}^{k-1}w_{k-1,t}\lambda_t(g_t-g_{k-1}+g_{k-1}-g_k) \\
&= (1-\beta_k)\sum_{t=0}^{k-1}w_{k-1,t}\lambda_t(g_t-g_{k-1})+(1-\beta_k)\left(\sum_{t=0}^{k-1}w_{k-1,t}\lambda_t\right)(g_{k-1}-g_k) \\
&= (1-\beta_k)D_{k-1}+(1-\beta_k)A_{k-1}(g_{k-1}-g_k),
\end{aligned} D k = t = 0 ∑ k w k , t λ t ( g t − g k ) = t = 0 ∑ k − 1 w k , t λ t ( g t − g k ) = ( 1 − β k ) t = 0 ∑ k − 1 w k − 1 , t λ t ( g t − g k − 1 + g k − 1 − g k ) = ( 1 − β k ) t = 0 ∑ k − 1 w k − 1 , t λ t ( g t − g k − 1 ) + ( 1 − β k ) ( t = 0 ∑ k − 1 w k − 1 , t λ t ) ( g k − 1 − g k ) = ( 1 − β k ) D k − 1 + ( 1 − β k ) A k − 1 ( g k − 1 − g k ) ,
N k = ∑ t = 0 k w k , t ε t = ∑ t = 0 k − 1 w k , t ε t + w k , k ε k = ∑ t = 0 k − 1 ( 1 − β k ) w k − 1 , t ε t + β k ε k = ( 1 − β k ) N k − 1 + β k ε k . N_k=\sum_{t=0}^{k}w_{k,t}\varepsilon_t=\sum_{t=0}^{k-1}w_{k,t}\varepsilon_t+w_{k,k}\varepsilon_k=\sum_{t=0}^{k-1}(1-\beta_k)w_{k-1,t}\varepsilon_t+\beta_k\varepsilon_k=(1-\beta_k)N_{k-1}+\beta_k\varepsilon_k. N k = t = 0 ∑ k w k , t ε t = t = 0 ∑ k − 1 w k , t ε t + w k , k ε k = t = 0 ∑ k − 1 ( 1 − β k ) w k − 1 , t ε t + β k ε k = ( 1 − β k ) N k − 1 + β k ε k .
Lemma 8 (Drift and sampling-noise bounds). Under (19) , there exists a universal constant C s t o c h > 0 C_{\mathrm{stoch}}>0 C stoch > 0 such that
∥ D k ∥ ⋆ A k ≤ 32 L γ 3 α , (24) \frac{\lVert D_k\rVert_\star}{A_k}\leq\frac{32L\gamma}{3\alpha}, \tag*{(24)} A k ∥ D k ∥ ⋆ ≤ 3 α 32 L γ , (24) and, for T : = K − k b > 0 T:=K-k_b>0 T := K − k b > 0 ,
1 T ∑ k = k b K − 1 E [ ∥ N k ∥ ⋆ A k ] ≤ C s t o c h σ ~ B ( α + 1 α T ) . (25) \frac{1}{T}\sum_{k=k_b}^{K-1}\mathbb{E}\left[\frac{\lVert N_k\rVert_\star}{A_k}\right]\leq C_{\mathrm{stoch}}\frac{\widetilde{\sigma}}{\sqrt{B}}\left(\sqrt{\alpha}+\frac{1}{\alpha T}\right). \tag*{(25)} T 1 k = k b ∑ K − 1 E [ A k ∥ N k ∥ ⋆ ] ≤ C stoch B σ ( α + α T 1 ) . (25)
Proof. Consider the recursions of Lemma 7:
D k = ( 1 − β k ) D k − 1 + ( 1 − β k ) A k − 1 ( g k − 1 − g k ) . D_k=(1-\beta_k)D_{k-1}+(1-\beta_k)A_{k-1}(g_{k-1}-g_k). D k = ( 1 − β k ) D k − 1 + ( 1 − β k ) A k − 1 ( g k − 1 − g k ) .
A k = ( 1 − β k ) A k − 1 + β k λ k . A_k=(1-\beta_k)A_{k-1}+\beta_k\lambda_k. A k = ( 1 − β k ) A k − 1 + β k λ k .
Now we can define:
q k : = ( 1 − β k ) A k − 1 A k = 1 − β k λ k A k . q_k:=\frac{(1-\beta_k)A_{k-1}}{A_k}=1-\beta_k\frac{\lambda_k}{A_k}. q k := A k ( 1 − β k ) A k − 1 = 1 − β k A k λ k .
By (20) and burn in (β k ≥ α \beta_k\geq\alpha β k ≥ α ),
0 ≤ q k ≤ 1 − 3 α 32 = : q ‾ . 0\leq q_k\leq1-\frac{3\alpha}{32}=: \overline{q}. 0 ≤ q k ≤ 1 − 32 3 α =: q .
Therefore,
∥ D k ∥ ⋆ A k = ∥ ( 1 − β k ) D k − 1 + ( 1 − β k ) A k − 1 ( g k − 1 − g k ) ∥ ⋆ A k ≤ q k ∥ D k − 1 ∥ ⋆ A k − 1 + q k ∥ g k − 1 − g k ∥ ⋆ ≤ q ˉ ∥ D k − 1 ∥ ⋆ A k − 1 + q ˉ L γ ≤ ∑ i = 1 k q ˉ i L γ + q ˉ k ∥ D 0 ∥ ⋆ A 0 ≤ L γ 1 1 − q ˉ + q ˉ k ∥ D 0 ∥ ⋆ A 0 . \begin{aligned}
\frac{\lVert D_k\rVert_\star}{A_k}
&= \frac{\lVert(1-\beta_k)D_{k-1}+(1-\beta_k)A_{k-1}(g_{k-1}-g_k)\rVert_\star}{A_k}\\
&\le q_k\frac{\lVert D_{k-1}\rVert_\star}{A_{k-1}}+q_k\lVert g_{k-1}-g_k\rVert_\star\\
&\le\bar q\frac{\lVert D_{k-1}\rVert_\star}{A_{k-1}}+\bar q L\gamma\\
&\le\sum_{i=1}^{k}\bar q^iL\gamma+\bar q^k\frac{\lVert D_0\rVert_\star}{A_0}\\
&\le L\gamma\frac{1}{1-\bar q}+\bar q^k\frac{\lVert D_0\rVert_\star}{A_0}.
\end{aligned} A k ∥ D k ∥ ⋆ = A k ∥( 1 − β k ) D k − 1 + ( 1 − β k ) A k − 1 ( g k − 1 − g k ) ∥ ⋆ ≤ q k A k − 1 ∥ D k − 1 ∥ ⋆ + q k ∥ g k − 1 − g k ∥ ⋆ ≤ q ˉ A k − 1 ∥ D k − 1 ∥ ⋆ + q ˉ L γ ≤ i = 1 ∑ k q ˉ i L γ + q ˉ k A 0 ∥ D 0 ∥ ⋆ ≤ L γ 1 − q ˉ 1 + q ˉ k A 0 ∥ D 0 ∥ ⋆ .
Since D 0 = 0 D_0=0 D 0 = 0 , summing the geometric series proves (24) .
For the sampling noise, Lemma 7 gives
N k A k = ( 1 − β k ) N k − 1 + β k ε k A k = ( 1 − β k ) A k − 1 A k N k − 1 A k − 1 + β k A k ε k = q k N k − 1 A k − 1 + β k A k ε k . \frac{N_k}{A_k}=\frac{(1-\beta_k)N_{k-1}+\beta_k\varepsilon_k}{A_k}=\frac{(1-\beta_k)A_{k-1}}{A_k}\frac{N_{k-1}}{A_{k-1}}+\frac{\beta_k}{A_k}\varepsilon_k=q_k\frac{N_{k-1}}{A_{k-1}}+\frac{\beta_k}{A_k}\varepsilon_k. A k N k = A k ( 1 − β k ) N k − 1 + β k ε k = A k ( 1 − β k ) A k − 1 A k − 1 N k − 1 + A k β k ε k = q k A k − 1 N k − 1 + A k β k ε k .
Next, we expand the squared L 2 L_2 L 2 norm of this expression:
∥ N k ∥ 2 2 A k 2 = ∥ q k N k − 1 A k − 1 + β k A k ε k ∥ 2 2 = q k 2 ∥ N k − 1 ∥ 2 2 A k − 1 2 + β k 2 A k 2 ∥ ε k ∥ 2 2 + 2 q k β k A k ⟨ N k − 1 A k − 1 , ε k ⟩ . \frac{\lVert N_k\rVert_2^2}{A_k^2}=\left\lVert q_k\frac{N_{k-1}}{A_{k-1}}+\frac{\beta_k}{A_k}\varepsilon_k\right\rVert_2^2=q_k^2\frac{\lVert N_{k-1}\rVert_2^2}{A_{k-1}^2}+\frac{\beta_k^2}{A_k^2}\lVert\varepsilon_k\rVert_2^2+2q_k\frac{\beta_k}{A_k}\left\langle\frac{N_{k-1}}{A_{k-1}},\varepsilon_k\right\rangle. A k 2 ∥ N k ∥ 2 2 = q k A k − 1 N k − 1 + A k β k ε k 2 2 = q k 2 A k − 1 2 ∥ N k − 1 ∥ 2 2 + A k 2 β k 2 ∥ ε k ∥ 2 2 + 2 q k A k β k ⟨ A k − 1 N k − 1 , ε k ⟩ .
We now take the conditional expectation:
E [ ⟨ N k − 1 A k − 1 , ε k ⟩ ∣ F k ] = ⟨ N k − 1 A k − 1 , E [ ε k ∣ F k ] ⟩ = 0. \mathbb{E}\left[\left.\left\langle\frac{N_{k-1}}{A_{k-1}},\varepsilon_k\right\rangle\right|\mathcal{F}_k\right]=\left\langle\frac{N_{k-1}}{A_{k-1}},\mathbb{E}[\varepsilon_k\mid\mathcal{F}_k]\right\rangle=0. E [ ⟨ A k − 1 N k − 1 , ε k ⟩ F k ] = ⟨ A k − 1 N k − 1 , E [ ε k ∣ F k ] ⟩ = 0.
This factorization is valid because the past accumulated noise N k − 1 N_{k-1} N k − 1 and the denominator A k − 1 A_{k-1} A k − 1 are F k \mathcal{F}_k F k -measurable.
Hence using E [ ∥ ε k ∥ 2 2 ∣ F k ] ≤ 320 λ k 2 σ 2 B \mathbb{E}[\lVert\varepsilon_k\rVert_2^2\mid\mathcal{F}_k]\le\frac{320\lambda_k^2\sigma^2}{B} E [∥ ε k ∥ 2 2 ∣ F k ] ≤ B 320 λ k 2 σ 2 (17) and λ k / A k ≤ 10 \lambda_k/A_k\le10 λ k / A k ≤ 10 (20) :
E [ ∥ N k ∥ 2 2 A k 2 ∣ F k ] ≤ q k 2 ∥ N k − 1 ∥ 2 2 A k − 1 2 + β k 2 A k 2 320 λ k 2 σ 2 B ≤ q k 2 ∥ N k − 1 ∥ 2 2 A k − 1 2 + 32000 β k 2 σ 2 B . \mathbb{E}\left[\left.\frac{\lVert N_k\rVert_2^2}{A_k^2}\right|\mathcal{F}_k\right]\le q_k^2\frac{\lVert N_{k-1}\rVert_2^2}{A_{k-1}^2}+\frac{\beta_k^2}{A_k^2}\frac{320\lambda_k^2\sigma^2}{B}\le q_k^2\frac{\lVert N_{k-1}\rVert_2^2}{A_{k-1}^2}+32000\beta_k^2\frac{\sigma^2}{B}. E [ A k 2 ∥ N k ∥ 2 2 F k ] ≤ q k 2 A k − 1 2 ∥ N k − 1 ∥ 2 2 + A k 2 β k 2 B 320 λ k 2 σ 2 ≤ q k 2 A k − 1 2 ∥ N k − 1 ∥ 2 2 + 32000 β k 2 B σ 2 .
Now using (20) and q k ∈ [ 0 , 1 ] q_k\in[0,1] q k ∈ [ 0 , 1 ] ,
q k 2 ≤ q k = 1 − β k λ k A k ≤ 1 − 3 β k 32 , q_k^2\le q_k=1-\beta_k\frac{\lambda_k}{A_k}\le1-\frac{3\beta_k}{32}, q k 2 ≤ q k = 1 − β k A k λ k ≤ 1 − 32 3 β k ,
which is a deterministic bound. Let X k : = E [ ∥ N k ∥ 2 2 / A k 2 ] X_k:=\mathbb{E}[\lVert N_k\rVert_2^2/A_k^2] X k := E [∥ N k ∥ 2 2 / A k 2 ] , where the expectation is over the mini-batch sampling (conditionally on the Gaussian noise sequence, which is independent of the batches; the argument is identical for the total expectation). Taking expectations of the previous conditional inequality gives
X k ≤ ( 1 − 3 β k 32 ) X k − 1 + 32000 β k 2 σ 2 B , X 0 = E ∥ ε 0 ∥ 2 2 λ 0 2 ≤ 320 σ 2 B . X_k\le\left(1-\frac{3\beta_k}{32}\right)X_{k-1}+32000\beta_k^2\frac{\sigma^2}{B},\qquad X_0=\mathbb{E}\frac{\lVert\varepsilon_0\rVert_2^2}{\lambda_0^2}\le\frac{320\sigma^2}{B}. X k ≤ ( 1 − 32 3 β k ) X k − 1 + 32000 β k 2 B σ 2 , X 0 = E λ 0 2 ∥ ε 0 ∥ 2 2 ≤ B 320 σ 2 .
Since β k ≤ 1 \beta_k\le1 β k ≤ 1 , induction yields the uniform bound X k ≤ C 0 σ 2 / B X_k\le C_0\sigma^2/B X k ≤ C 0 σ 2 / B with C 0 : = 32000 ⋅ 32 3 C_0:=32000\cdot\frac{32}{3} C 0 := 32000 ⋅ 3 32 . After the run-in, α ≤ β k ≤ 2 α \alpha\le\beta_k\le2\alpha α ≤ β k ≤ 2 α , so unrolling from k b k_b k b gives
X k ≤ C 0 ( 1 − 3 α 32 ) k − k b σ 2 B + C 1 α σ 2 B , C 1 : = 4 ⋅ 32000 ⋅ 32 3 , k ≥ k b . X_k\le C_0\left(1-\frac{3\alpha}{32}\right)^{k-k_b}\frac{\sigma^2}{B}+C_1\alpha\frac{\sigma^2}{B},\qquad C_1:=4\cdot32000\cdot\frac{32}{3},\qquad k\ge k_b. X k ≤ C 0 ( 1 − 32 3 α ) k − k b B σ 2 + C 1 α B σ 2 , C 1 := 4 ⋅ 32000 ⋅ 3 32 , k ≥ k b .
By Jensen’s inequality, ∥ v ∥ ⋆ ≤ ρ 1 ∥ v ∥ 2 \lVert v\rVert_{\star} \le\rho_{1}\lVert v\rVert_{2} ∥ v ∥ ⋆ ≤ ρ 1 ∥ v ∥ 2 , and x + y ≤ x + y \sqrt{x+y} \le\sqrt{x}+\sqrt{y} x + y ≤ x + y ,
E [ ∥ N k ∥ ⋆ A k ] ≤ ρ 1 σ B ( C 0 ( 1 − 3 α 32 ) k − k b 2 + C 1 α ) \mathbb{E}\left[\frac{\lVert N_k\rVert_{\star}}{A_k}\right] \le\frac{\rho_1\sigma}{\sqrt{B}}\left(\sqrt{C_0}\left(1-\frac{3\alpha}{32}\right)^{\frac{k-k_b}{2}}+\sqrt{C_1\sqrt{\alpha}}\right) E [ A k ∥ N k ∥ ⋆ ] ≤ B ρ 1 σ C 0 ( 1 − 32 3 α ) 2 k − k b + C 1 α
Summing over k = k b , … , K − 1 k=k_b,\ldots,K-1 k = k b , … , K − 1 and using ∑ j ≥ 0 r j / 2 = 1 1 − r ≤ 2 1 − r = 64 3 α \sum_{j\ge0}r^{j/2}=\frac{1}{1-\sqrt{r}}\le\frac{2}{1-r}=\frac{64}{3\alpha} ∑ j ≥ 0 r j /2 = 1 − r 1 ≤ 1 − r 2 = 3 α 64 for r = 1 − 3 α 32 r=1-\frac{3\alpha}{32} r = 1 − 32 3 α gives
1 T ∑ k = k b K − 1 E [ ∥ N k ∥ ⋆ A k ] ≤ C s t o c h ρ 1 σ B ( α + 1 α T ) \frac{1}{T}\sum_{k=k_b}^{K-1}\mathbb{E}\left[\frac{\lVert N_k\rVert_{\star}}{A_k}\right]\le C_{\mathrm{stoch}}\frac{\rho_1\sigma}{\sqrt{B}}\left(\sqrt{\alpha}+\frac{1}{\alpha T}\right) T 1 k = k b ∑ K − 1 E [ A k ∥ N k ∥ ⋆ ] ≤ C stoch B ρ 1 σ ( α + α T 1 )
for a universal C s t o c h C_{\mathrm{stoch}} C stoch . This is (25) .
Privacy-noise bound
Let Z ∼ N ( 0 , I ) Z\sim\mathcal{N}(0,I) Z ∼ N ( 0 , I ) . The map z ↦ ∥ z ∥ ⋆ z\mapsto\lVert z\rVert_{\star} z ↦ ∥ z ∥ ⋆ is ρ 1 \rho_1 ρ 1 -Lipschitz with respect to ∥ ⋅ ∥ 2 \lVert\cdot\rVert_2 ∥ ⋅ ∥ 2 . The Gaussian component of the bias-corrected momentum is P k = ∑ t = 0 k w k , t z t P_k=\sum_{t=0}^{k}w_{k,t}z_t P k = ∑ t = 0 k w k , t z t . Because it is a linear combination of independent Gaussian vectors, P k P_k P k is Gaussian with covariance Cov ( P k ) = c 2 σ D P 2 ( ∑ t = 0 k w k , t 2 ) I \operatorname{Cov}(P_k)=c^2\sigma_{\mathrm{DP}}^2\left(\sum_{t=0}^{k}w_{k,t}^2\right)I Cov ( P k ) = c 2 σ DP 2 ( ∑ t = 0 k w k , t 2 ) I .
To evaluate this variance multiplier, we explicitly sum the squares of the normalized exponential moving average weights w k , t = α ( 1 − α ) k − t 1 − ( 1 − α ) k + 1 w_{k,t}=\frac{\alpha(1-\alpha)^{k-t}}{1-(1-\alpha)^{k+1}} w k , t = 1 − ( 1 − α ) k + 1 α ( 1 − α ) k − t :
∑ t = 0 k w k , t 2 = α 2 ( 1 − ( 1 − α ) k + 1 ) 2 ∑ t = 0 k ( 1 − α ) 2 ( k − t ) = α 2 ( 1 − ( 1 − α ) k + 1 ) 2 1 − ( 1 − α ) 2 ( k + 1 ) 1 − ( 1 − α ) 2 = α 2 ( 1 − ( 1 − α ) k + 1 ) 2 ( 1 − ( 1 − α ) k + 1 ) ( 1 + ( 1 − α ) k + 1 ) α ( 2 − α ) = α 2 − α 1 + ( 1 − α ) k + 1 1 − ( 1 − α ) k + 1 . \begin{aligned}
\sum_{t=0}^{k}w_{k,t}^2=\frac{\alpha^2}{\left(1-(1-\alpha)^{k+1}\right)^2}\sum_{t=0}^{k}(1-\alpha)^{2(k-t)} \\
&=\frac{\alpha^2}{\left(1-(1-\alpha)^{k+1}\right)^2}\frac{1-(1-\alpha)^{2(k+1)}}{1-(1-\alpha)^2} \\
&=\frac{\alpha^2}{\left(1-(1-\alpha)^{k+1}\right)^2}\frac{\left(1-(1-\alpha)^{k+1}\right)\left(1+(1-\alpha)^{k+1}\right)}{\alpha(2-\alpha)} \\
&=\frac{\alpha}{2-\alpha}\frac{1+(1-\alpha)^{k+1}}{1-(1-\alpha)^{k+1}}.
\end{aligned} t = 0 ∑ k w k , t 2 = ( 1 − ( 1 − α ) k + 1 ) 2 α 2 t = 0 ∑ k ( 1 − α ) 2 ( k − t ) = ( 1 − ( 1 − α ) k + 1 ) 2 α 2 1 − ( 1 − α ) 2 1 − ( 1 − α ) 2 ( k + 1 ) = ( 1 − ( 1 − α ) k + 1 ) 2 α 2 α ( 2 − α ) ( 1 − ( 1 − α ) k + 1 ) ( 1 + ( 1 − α ) k + 1 ) = 2 − α α 1 − ( 1 − α ) k + 1 1 + ( 1 − α ) k + 1 .
For k ≥ k b = ⌈ log 2 α ⌉ k\ge k_b=\left\lceil\frac{\log2}{\alpha}\right\rceil k ≥ k b = ⌈ α l o g 2 ⌉ , we have ( 1 − α ) k + 1 ≤ 1 2 (1-\alpha)^{k+1}\le\frac{1}{2} ( 1 − α ) k + 1 ≤ 2 1 , so the right-hand side is at most 3 α 3\alpha 3 α . Therefore P k = d s k Z P_k\mathrel{\overset{d}{=}}s_kZ P k = d s k Z with Z ∼ N ( 0 , I ) Z\sim\mathcal{N}(0,I) Z ∼ N ( 0 , I ) and s k ≤ 3 α c σ D P s_k\le\sqrt{3\alpha}\,c\sigma_{\mathrm{DP}} s k ≤ 3 α c σ DP , and ∥ P k ∥ ⋆ \lVert P_k\rVert_{\star} ∥ P k ∥ ⋆ is stochastically dominated by 3 α c σ D P ∥ Z ∥ ⋆ \sqrt{3\alpha}\,c\sigma_{\mathrm{DP}}\lVert Z\rVert_{\star} 3 α c σ DP ∥ Z ∥ ⋆ .
To bound the dual norm of this noise, we apply the Tsirelson-Ibragimov-Sudakov concentration inequality. For the standard Gaussian vector Z Z Z and the ρ 1 \rho_1 ρ 1 -Lipschitz mapping z ↦ ∥ z ∥ ⋆ z\mapsto\lVert z\rVert_{\star} z ↦ ∥ z ∥ ⋆ , the one-sided tail bound is:
P ( ∥ Z ∥ ⋆ − E ∥ Z ∥ ⋆ ≥ t ) ≤ exp ( − t 2 2 ρ 1 2 ) . \mathbb{P}\left(\lVert Z\rVert_{\star}-\mathbb{E}\lVert Z\rVert_{\star}\ge t\right)\le\exp\left(-\frac{t^2}{2\rho_1^2}\right). P ( ∥ Z ∥ ⋆ − E ∥ Z ∥ ⋆ ≥ t ) ≤ exp ( − 2 ρ 1 2 t 2 ) .
To guarantee a global failure probability of at most η ∈ ( 0 , 1 ) \eta\in(0,1) η ∈ ( 0 , 1 ) across the T T T tail iterations, we allocate a failure budget of η / T \eta/T η / T to each step. Setting the right-hand side to η / T \eta/T η / T yields the deviation threshold t = ρ 1 2 log ( T / η ) t=\rho_1\sqrt{2\log(T/\eta)} t = ρ 1 2 log ( T / η ) . Scaling the expectation and the deviation threshold by the standard-deviation bound 3 α c σ D P \sqrt{3\alpha}\,c\sigma_{\mathrm{DP}} 3 α c σ DP yields the momentum-filtered DP-noise scale:
H T , η : = E ∥ Z ∥ ⋆ + ρ 1 2 log ( T η ) , Z ∼ N ( 0 , I ) , H_{T,\eta}:=\mathbb{E}\lVert Z\rVert_{\star}+\rho_1\sqrt{2\log\left(\frac{T}{\eta}\right)},\qquad Z\sim\mathcal{N}(0,I), H T , η := E ∥ Z ∥ ⋆ + ρ 1 2 log ( η T ) , Z ∼ N ( 0 , I ) ,
ν D P ( η ) : = c σ D P 3 α H T , η (26) \nu_{\mathrm{DP}}(\eta):=c\sigma_{\mathrm{DP}}\sqrt{3\alpha}\,H_{T,\eta} \tag*{(26)} ν DP ( η ) := c σ DP 3 α H T , η (26)
This ensures that for any single step k k k , P ( ∥ P k ∥ ⋆ ≥ ν D P ( η ) ) ≤ η T \mathbb{P}(\lVert P_k\rVert_{\star} \ge\nu_{\mathrm{DP}}(\eta)) \le\frac{\eta}{T} P (∥ P k ∥ ⋆ ≥ ν DP ( η )) ≤ T η . Applying a union bound over the T T T tail iterations guarantees that with probability at least 1 − η 1-\eta 1 − η over the Gaussian vectors { z k } \{z_k\} { z k } , the concentration holds:
∥ P k ∥ ⋆ ≤ ν D P ( η ) ∀ k ∈ { k b , … , K − 1 } . (27) \lVert P_k\rVert_{\star} \le\nu_{\mathrm{DP}}(\eta) \qquad\forall k \in\{k_b,\ldots,K-1\}. \tag*{(27)} ∥ P k ∥ ⋆ ≤ ν DP ( η ) ∀ k ∈ { k b , … , K − 1 } . (27)
Under (20) , the smoothed normalization factor is bounded as A k ≥ α k 5 A_k \ge\frac{\alpha_k}{5} A k ≥ 5 α k , which implies 1 A k ≤ 5 max { 1 , ∥ g k ∥ 2 c } \frac{1}{A_k} \le5\max\left\{1,\frac{\lVert g_k\rVert_2}{c}\right\} A k 1 ≤ 5 max { 1 , c ∥ g k ∥ 2 } . Consequently, on the event (27) , using the algebraic inequality max { 1 , x } ≤ 1 + x \max\{1,x\}\le1+x max { 1 , x } ≤ 1 + x and the norm equivalence ∥ g k ∥ 2 ≤ ρ 2 ∥ g k ∥ ⋆ \lVert g_k\rVert_2\le\rho_2\lVert g_k\rVert_{\star} ∥ g k ∥ 2 ≤ ρ 2 ∥ g k ∥ ⋆ , we can bound:
P k = ∥ P k ∥ ⋆ A k ≤ 5 ν D P ( η ) max { 1 , ∥ g k ∥ 2 c } ≤ 5 ν D P ( η ) ( 1 + ∥ g k ∥ 2 c ) ≤ 5 ν D P ( η ) + 5 ρ 2 ν D P ( η ) c ∥ g k ∥ ⋆ . (28) \begin{aligned}
P_k &= \frac{\lVert P_k\rVert_{\star}}{A_k} \le5\nu_{\mathrm{DP}}(\eta)\max\left\{1,\frac{\lVert g_k\rVert_2}{c}\right\}\\
&\le5\nu_{\mathrm{DP}}(\eta)\left(1+\frac{\lVert g_k\rVert_2}{c}\right)\\
&\le5\nu_{\mathrm{DP}}(\eta)+5\rho_2\frac{\nu_{\mathrm{DP}}(\eta)}{c}\lVert g_k\rVert_{\star}. \tag*{(28)}
\end{aligned} P k = A k ∥ P k ∥ ⋆ ≤ 5 ν DP ( η ) max { 1 , c ∥ g k ∥ 2 } ≤ 5 ν DP ( η ) ( 1 + c ∥ g k ∥ 2 ) ≤ 5 ν DP ( η ) + 5 ρ 2 c ν DP ( η ) ∥ g k ∥ ⋆ . (28)
The first k b k_b k b iterations can be controlled deterministically. For every lower-bounded L L L -smooth function,
∥ ∇ f ( x ) ∥ ⋆ 2 ≤ 2 L ( f ( x ) − f ⋆ ) . \lVert\nabla f(x)\rVert_{\star}^{2}\le2L(f(x)-f^{\star}). ∥ ∇ f ( x ) ∥ ⋆ 2 ≤ 2 L ( f ( x ) − f ⋆ ) .
Since every update has norm at most γ \gamma γ ,
f ( x k + 1 ) − f ⋆ ≤ ( f ( x k ) − f ⋆ + γ L / 2 ) 2 . f(x_{k+1})-f^{\star}\le\left(\sqrt{f(x_k)-f^{\star}}+\gamma\sqrt{L/2}\right)^2. f ( x k + 1 ) − f ⋆ ≤ ( f ( x k ) − f ⋆ + γ L /2 ) 2 .
Therefore,
f ( x k b ) − f ⋆ ≤ Φ ‾ : = ( Φ ‾ 0 + k b γ L / 2 ) 2 . (29) f(x_{k_b})-f^{\star}\le\overline{\Phi}:=\left(\sqrt{\overline{\Phi}_0+k_b\gamma\sqrt{L/2}}\right)^2. \tag*{(29)} f ( x k b ) − f ⋆ ≤ Φ := ( Φ 0 + k b γ L /2 ) 2 . (29)
Theorem 6. (Closed-form convergence of DP-Muon). Assume Assumptions 1–2 and the sufficient ray-scale condition (19) . Let k b k_b k b be defined by (23) , and let T : = K − k b > 0 T:=K-k_b>0 T := K − k b > 0 . Then, with probability at least 1 − η 1-\eta 1 − η over the Gaussian privacy noise,
( 1 − 10 ρ 2 ν D P ( η ) c ) 1 T ∑ k = k b K − 1 E S ∥ g k ∥ ⋆ ≤ Φ ‾ γ T + L γ 2 + 64 L γ 3 α + 32 b ~ c + C s t o c h σ ~ B ( α + 1 α T ) + 10 ν D P ( η ) . (30) \left(1-10\rho_2\frac{\nu_{\mathrm{DP}}(\eta)}{c}\right)\frac{1}{T}\sum_{k=k_b}^{K-1}\mathbb{E}_{S}\lVert g_k\rVert_{\star}
\le\frac{\overline{\Phi}}{\gamma T}+\frac{L\gamma}{2}+\frac{64L\gamma}{3\alpha}+32\widetilde{b}_c+C_{\mathrm{stoch}}\frac{\widetilde{\sigma}}{\sqrt{B}}\left(\sqrt{\alpha}+\frac{1}{\alpha T}\right)+10\nu_{\mathrm{DP}}(\eta). \tag*{(30)} ( 1 − 10 ρ 2 c ν DP ( η ) ) T 1 k = k b ∑ K − 1 E S ∥ g k ∥ ⋆ ≤ γ T Φ + 2 L γ + 3 α 64 L γ + 32 b c + C stoch B σ ( α + α T 1 ) + 10 ν DP ( η ) . (30) Here E S \mathbb{E}_{S} E S denotes expectation over stochastic-gradient sampling conditional on the Gaussian-noise realization.
Proof. Apply Theorem 5 to the tail k = k b , … , K − 1 k=k_b,\ldots,K-1 k = k b , … , K − 1 , replacing the initial function gap by (29) . Use Lemma 8 for D k D_k D k and N k N_k N k . On the Gaussian event (27) , use (28) . The projective LMO lemma contributes a factor 2 in front of each tracking term, which yields the coefficient 10 ρ 2 ν D P ( η ) / c 10\rho_2\nu_{\mathrm{DP}}(\eta)/c 10 ρ 2 ν DP ( η ) / c on the left and the additive 10 ν D P ( η ) 10\nu_{\mathrm{DP}}(\eta) 10 ν DP ( η ) on the right. Summing the smoothness inequality and dividing by γ T \gamma T γ T proves (30) .
Corollary 5 (Clean high-probability form). If, in addition,
10 ρ 2 ν D P ( η ) c ≤ 1 2 . 10\rho_{2}\frac{\nu_{\mathrm{DP}}(\eta)}{c}\le\frac{1}{2}. 10 ρ 2 c ν DP ( η ) ≤ 2 1 .
then
1 T ∑ k = k b K − 1 E S ∥ g k ∥ ⋆ = O ( Φ ‾ γ T + L γ α + b ~ c + σ ~ B ( α + 1 α T ) + c σ D P α H T , η ) . \frac{1}{T}\sum_{k=k_b}^{K-1}\mathbb{E}_{S}\|g_k\|_{\star}
=O\left(\frac{\overline{\Phi}}{\gamma T}+\frac{L\gamma}{\alpha}+\widetilde{b}_c+\frac{\widetilde{\sigma}}{\sqrt{B}}\left(\sqrt{\alpha}+\frac{1}{\alpha T}\right)+c\sigma_{\mathrm{DP}}\sqrt{\alpha}H_{T,\eta}\right). T 1 k = k b ∑ K − 1 E S ∥ g k ∥ ⋆ = O ( γ T Φ + α L γ + b c + B σ ( α + α T 1 ) + c σ DP α H T , η ) .
Theorem 1 in the main text is Corollary 5 with explicit constants: under 10 ρ 2 ν D P ( η ) / c ≤ 1 / 2 10\rho_{2}\nu_{\mathrm{DP}}(\eta)/c\le1/2 10 ρ 2 ν DP ( η ) / c ≤ 1/2 , the left-hand side of (30) is at least half the average, and L γ + 128 L γ 3 α ≤ 45 L γ α L\gamma+\frac{128L\gamma}{3\alpha}\le\frac{45L\gamma}{\alpha} L γ + 3 α 128 L γ ≤ α 45 L γ for α ≤ 1 \alpha\le1 α ≤ 1 .
Rates
Throughout this section, H T , η = E ∥ Z ∥ ⋆ + ρ 1 2 log ( T / η ) H_{T,\eta}=\mathbb{E}\|Z\|_{\star}+\rho_{1}\sqrt{2\log(T/\eta)} H T , η = E ∥ Z ∥ ⋆ + ρ 1 2 log ( T / η ) , so that ν D P ( η ) = 3 α c σ D P H T , η \nu_{\mathrm{DP}}(\eta)=\sqrt{3\alpha}\,c\sigma_{\mathrm{DP}}H_{T,\eta} ν DP ( η ) = 3 α c σ DP H T , η , and the two conditions of Theorem 1 read
(stability) γ ≤ c α 4 ρ 2 L , (admissibility) α ≤ 1 1200 ρ 2 2 σ D P 2 H T , η 2 . (31) \begin{aligned}
\text{(stability)}\quad&\gamma\le\frac{c\alpha}{4\rho_{2}L}, \qquad
\text{(admissibility)}\quad\alpha\le\frac{1}{1200\rho_{2}^{2}\sigma_{\mathrm{DP}}^{2}H_{T,\eta}^{2}}. \tag*{(31)}
\end{aligned} (stability) γ ≤ 4 ρ 2 L c α , (admissibility) α ≤ 1200 ρ 2 2 σ DP 2 H T , η 2 1 . (31)
In addition, T = K − k b > 0 T=K-k_b>0 T = K − k b > 0 requires α = Ω ( 1 / K ) \alpha=\Omega(1/K) α = Ω ( 1/ K ) .
Fixed noise scale
Fix c = Θ ( 1 ) c=\Theta(1) c = Θ ( 1 ) and σ D P = Θ ( 1 ) \sigma_{\mathrm{DP}}=\Theta(1) σ DP = Θ ( 1 ) , independent of K K K ; then b ~ c = Θ ( 1 ) \widetilde{b}_c=\Theta(1) b c = Θ ( 1 ) is a constant floor. Balancing Φ ‾ / ( γ T ) \overline{\Phi}/(\gamma T) Φ / ( γ T ) against L γ / α L\gamma/\alpha L γ / α gives γ ⋆ = Φ ‾ α / ( L T ) \gamma_{\star}=\sqrt{\overline{\Phi}\alpha/(LT)} γ ⋆ = Φ α / ( L T ) , and with T ≥ K / 2 T\ge K/2 T ≥ K /2 the bound of Theorem 1 becomes
1 T ∑ k = k b K − 1 E S ∥ ∇ f ( x k ) ∥ ⋆ = O ( L Φ ‾ K α + b ~ c + ( σ ~ B + c σ D P H T , η ) α + σ ~ B α K ) . (32) \frac{1}{T}\sum_{k=k_b}^{K-1}\mathbb{E}_{S}\|\nabla f(x_k)\|_{\star}
=O\left(\sqrt{\frac{L\overline{\Phi}}{K\alpha}}+\widetilde{b}_c+\left(\frac{\widetilde{\sigma}}{\sqrt{B}}+c\sigma_{\mathrm{DP}}H_{T,\eta}\right)\sqrt{\alpha}+\frac{\widetilde{\sigma}}{\sqrt{B\alpha K}}\right). \tag*{(32)} T 1 k = k b ∑ K − 1 E S ∥∇ f ( x k ) ∥ ⋆ = O K α L Φ + b c + ( B σ + c σ DP H T , η ) α + B α K σ . (32)
Since H T , η = Θ ( log K ) H_{T,\eta}=\Theta(\sqrt{\log K}) H T , η = Θ ( log K ) for fixed dimension and η \eta η , balancing 1 / K α 1/\sqrt{K\alpha} 1/ K α against α log K \sqrt{\alpha\log K} α log K gives
α ⋆ = Θ ( 1 K log K ) , γ ⋆ = Θ ( 1 K 3 / 4 ( log K ) 1 / 4 ) , \alpha_{\star}=\Theta\left(\frac{1}{\sqrt{K}\log K}\right),\qquad
\gamma_{\star}=\Theta\left(\frac{1}{K^{3/4}(\log K)^{1/4}}\right), α ⋆ = Θ ( K log K 1 ) , γ ⋆ = Θ ( K 3/4 ( log K ) 1/4 1 ) ,
and the last term in (32) is then of lower order. These choices are admissible for K K K large enough: α ⋆ ≫ 1 / K \alpha_{\star}\gg1/K α ⋆ ≫ 1/ K ; γ ⋆ / α ⋆ = Θ ( K − 1 / 4 ( log K ) 1 / 4 ) → 0 \gamma_{\star}/\alpha_{\star}=\Theta(K^{-1/4}(\log K)^{1/4})\to0 γ ⋆ / α ⋆ = Θ ( K − 1/4 ( log K ) 1/4 ) → 0 , so the stability condition holds; and α ⋆ H T , η 2 = Θ ( log K / K ) → 0 \alpha_{\star}H_{T,\eta}^{2}=\Theta(\sqrt{\log K/K})\to0 α ⋆ H T , η 2 = Θ ( log K / K ) → 0 , so the admissibility condition holds. Explicitly, admissibility requires K log K ≳ ρ 2 2 σ D P 2 H T , η 2 \sqrt{K}\log K\gtrsim\rho_{2}^{2}\sigma_{\mathrm{DP}}^{2}H_{T,\eta}^{2} K log K ≳ ρ 2 2 σ DP 2 H T , η 2 , that is, K ≳ ρ 2 4 σ D P 4 H T , η 4 K\gtrsim\rho_{2}^{4}\sigma_{\mathrm{DP}}^{4}H_{T,\eta}^{4} K ≳ ρ 2 4 σ DP 4 H T , η 4 up to logarithms, which is of order d D P 4 d_{\mathrm{DP}}^{4} d DP 4 for the ℓ 2 \ell_{2} ℓ 2 geometry and min { m , n ′ } 4 max { m , n ′ } 2 σ D P 4 \min\{m,n'\}^{4}\max\{m,n'\}^{2}\sigma_{\mathrm{DP}}^{4} min { m , n ′ } 4 max { m , n ′ } 2 σ DP 4 for the spectral geometry; the rate below describes the regime beyond this horizon. Moreover, k b γ ⋆ ≲ γ ⋆ / α ⋆ → 0 k_b\gamma_{\star}\lesssim\gamma_{\star}/\alpha_{\star}\to0 k b γ ⋆ ≲ γ ⋆ / α ⋆ → 0 , so Φ ‾ → Φ ‾ 0 \overline{\Phi}\to\overline{\Phi}_{0} Φ → Φ 0 and treating Φ ‾ \overline{\Phi} Φ as a constant is self-consistent. Substituting α ⋆ \alpha_{\star} α ⋆ into (32) gives the first part of Corollary 1:
1 T ∑ k = k b K − 1 E S ∥ ∇ f ( x k ) ∥ ⋆ = O ( ( log K ) 1 / 4 K 1 / 4 ) + O ( b ~ c ) . \frac{1}{T}\sum_{k=k_b}^{K-1}\mathbb{E}_{S}\|\nabla f(x_k)\|_{\star}
=O\left(\frac{(\log K)^{1/4}}{K^{1/4}}\right)+O(\widetilde{b}_c). T 1 k = k b ∑ K − 1 E S ∥∇ f ( x k ) ∥ ⋆ = O ( K 1/4 ( log K ) 1/4 ) + O ( b c ) .
Noise calibrated to a fixed privacy budget
We now fix ( ϵ , δ ) (\epsilon,\delta) ( ϵ , δ ) and set σ D P = c 2 K log ( 1 / δ ) / ( n ϵ ) \sigma_{\mathrm{DP}}=c_{2}\sqrt{K\log(1/\delta)}/(n\epsilon) σ DP = c 2 K log ( 1/ δ ) / ( n ϵ ) with the constants of the fixed-size calibration (2) , so that Algorithm 1 is ( ϵ , δ ) (\epsilon,\delta) ( ϵ , δ ) -DP whenever ϵ < c 1 q 2 K \epsilon<c_{1}q^{2K} ϵ < c 1 q 2 K (Proposition 1) and the noise scale grows with K K K . Write ℓ δ : = log ( 1 / δ ) \ell_{\delta}:=\log(1/\delta) ℓ δ := log ( 1/ δ ) and
D : = c c 2 ℓ δ H n ϵ , H : = E ∥ Z ∥ ⋆ + ρ 1 2 log ( K / η ) ≥ H T , η . D:=\frac{cc_{2}\sqrt{\ell_{\delta}}H}{n\epsilon},\qquad
H:=\mathbb{E}\|Z\|_{\star}+\rho_{1}\sqrt{2\log(K/\eta)}\ge H_{T,\eta}. D := n ϵ c c 2 ℓ δ H , H := E ∥ Z ∥ ⋆ + ρ 1 2 log ( K / η ) ≥ H T , η .
so that ν D P ( η ) ≤ 3 D α K \nu_{\mathrm{DP}}(\eta) \le\sqrt{3}D\sqrt{\alpha K} ν DP ( η ) ≤ 3 D α K . The key observation is that, with calibrated noise, the privacy term depends on α \alpha α and K K K only through the effective horizon s : = α K s := \alpha K s := α K .
Corollary 6 (Calibrated rate). Let Φ 0 = f ( x 0 ) − f ⋆ > 0 \Phi_0 = f(x_0) - f^\star> 0 Φ 0 = f ( x 0 ) − f ⋆ > 0 , let K K K be an integer, choose s ⋆ : = L Φ 0 / D s_\star:= \sqrt{L\Phi_0}/D s ⋆ := L Φ 0 / D , α = s ⋆ / K \alpha= s_\star/K α = s ⋆ / K , and γ = Φ 0 α / ( L K ) \gamma= \sqrt{\Phi_0}\alpha/(LK) γ = Φ 0 α / ( L K ) , and suppose that
D ≤ min { c 2 1200 ρ 2 2 L Φ 0 , L Φ 0 4 } (33) D \le\min\left\{\frac{c^2}{1200\rho_2^2\sqrt{L\Phi_0}},\frac{\sqrt{L\Phi_0}}{4}\right\} \tag*{(33)} D ≤ min { 1200 ρ 2 2 L Φ 0 c 2 , 4 L Φ 0 } (33) and K ≥ max { 2 s ⋆ , s ⋆ σ ~ 2 / ( B L Φ 0 D ) } K \ge\max\{2s_\star, s_\star\widetilde{\sigma}^2/(B\sqrt{L\Phi_0}D)\} K ≥ max { 2 s ⋆ , s ⋆ σ 2 / ( B L Φ 0 D )} , where D D D and s ⋆ s_\star s ⋆ depend on K K K through H H H . Then, with probability at least 1 − η 1-\eta 1 − η over the privacy noise,
1 T ∑ k = k b K − 1 E S ∥ ∇ f ( x k ) ∥ ⋆ ≲ ( L Φ 0 ) 1 / 4 D + σ ~ D B L Φ 0 + b ~ c , \frac{1}{T}\sum_{k=k_b}^{K-1}\mathbb{E}_{S}\|\nabla f(x_k)\|_\star\lesssim(L\Phi_0)^{1/4}\sqrt{D}+\frac{\widetilde{\sigma}D}{\sqrt{B L\Phi_0}}+\widetilde{b}_c, T 1 k = k b ∑ K − 1 E S ∥∇ f ( x k ) ∥ ⋆ ≲ ( L Φ 0 ) 1/4 D + B L Φ 0 σ D + b c , where ≲ \lesssim ≲ hides a universal constant. In particular, the bound is O ( ( L Φ 0 ) 1 / 4 c H ℓ δ / ( n ε ) ) + O ( b ~ c ) O((L\Phi_0)^{1/4}\sqrt{cH\sqrt{\ell_\delta}/(n\varepsilon)})+O(\widetilde{b}_c) O (( L Φ 0 ) 1/4 cH ℓ δ / ( n ε ) ) + O ( b c ) , since the middle term is of order 1 / ( n ε ) 1/(n\varepsilon) 1/ ( n ε ) .
Proof. Condition (33) gives D ≤ L Φ 0 / 4 D \le\sqrt{L\Phi_0}/4 D ≤ L Φ 0 /4 , that is, s ⋆ ≥ 4 s_\star\ge4 s ⋆ ≥ 4 .
Run-in and initial gap. Since α = s ⋆ / K ≤ 1 / 2 \alpha= s_\star/K \le1/2 α = s ⋆ / K ≤ 1/2 , we have k b ≤ log 2 / α + 1 ≤ 2 / α = 2 K / s ⋆ ≤ K / 2 k_b \le\log2/\alpha+ 1 \le2/\alpha= 2K/s_\star\le K/2 k b ≤ log 2/ α + 1 ≤ 2/ α = 2 K / s ⋆ ≤ K /2 , so T ≥ K / 2 T \ge K/2 T ≥ K /2 . Moreover, k b γ L / 2 ≤ 2 Φ 0 α / ( L K ) L / 2 = 2 Φ 0 / s ⋆ ≤ Φ 0 k_b\gamma\sqrt{L}/2 \le2\sqrt{\Phi_0\alpha/(LK)}\sqrt{L}/2 = \sqrt{2\Phi_0/s_\star} \le\sqrt{\Phi_0} k b γ L /2 ≤ 2 Φ 0 α / ( L K ) L /2 = 2 Φ 0 / s ⋆ ≤ Φ 0 , so Φ ‾ ≤ 4 Φ 0 \overline{\Phi} \le4\Phi_0 Φ ≤ 4 Φ 0 .
Stability. ρ 2 2 L γ / c ≤ α / 4 \rho_2^2L\gamma/c \le\alpha/4 ρ 2 2 L γ / c ≤ α /4 is equivalent to α K ≥ 4 ρ 2 L Φ 0 / c \sqrt{\alpha K} \ge4\rho_2\sqrt{L\Phi_0}/c α K ≥ 4 ρ 2 L Φ 0 / c , that is, s ⋆ ≥ 16 ρ 2 2 L Φ 0 / c 2 s_\star\ge16\rho_2^2L\Phi_0/c^2 s ⋆ ≥ 16 ρ 2 2 L Φ 0 / c 2 , which is equivalent to D ≤ c 2 / ( 16 ρ 2 2 L Φ 0 ) D \le c^2/(16\rho_2^2\sqrt{L\Phi_0}) D ≤ c 2 / ( 16 ρ 2 2 L Φ 0 ) and is implied by (33).
Admissibility. 10 ρ 2 ν D P ( η ) / c ≤ 10 3 ρ 2 D s ⋆ / c ≤ 1 / 2 10\rho_2\nu_{\mathrm{DP}}(\eta)/c \le10\sqrt{3}\rho_2D\sqrt{s_\star}/c \le1/2 10 ρ 2 ν DP ( η ) / c ≤ 10 3 ρ 2 D s ⋆ / c ≤ 1/2 is equivalent to s ⋆ ≤ c 2 / ( 1200 ρ 2 2 D 2 ) s_\star\le c^2/(1200\rho_2^2D^2) s ⋆ ≤ c 2 / ( 1200 ρ 2 2 D 2 ) , which is equivalent to D ≤ c 2 / ( 1200 ρ 2 2 L Φ 0 ) D \le c^2/(1200\rho_2^2\sqrt{L\Phi_0}) D ≤ c 2 / ( 1200 ρ 2 2 L Φ 0 ) , as assumed.
Bound. Theorem 1 applies. With Φ ‾ ≤ 4 Φ 0 \overline{\Phi} \le4\Phi_0 Φ ≤ 4 Φ 0 and T ≥ K / 2 T \ge K/2 T ≥ K /2 ,
2 Φ ‾ γ T + 45 L γ α ≤ 16 Φ 0 γ K + 45 L γ α = ( 16 + 45 ) L Φ 0 α K = 61 ( L Φ 0 ) 1 / 4 D , \frac{2\overline{\Phi}}{\gamma T}+\frac{45L\gamma}{\alpha}\le\frac{16\Phi_0}{\gamma K}+\frac{45L\gamma}{\alpha}=(16+45)\sqrt{\frac{L\Phi_0}{\alpha K}}=61(L\Phi_0)^{1/4}\sqrt{D}, γ T 2 Φ + α 45 L γ ≤ γ K 16 Φ 0 + α 45 L γ = ( 16 + 45 ) α K L Φ 0 = 61 ( L Φ 0 ) 1/4 D ,
20 ν D P ( η ) ≤ 20 3 D s ⋆ = 20 3 ( L Φ 0 ) 1 / 4 D , 20\nu_{\mathrm{DP}}(\eta)\le20\sqrt{3}D\sqrt{s_\star}=20\sqrt{3}(L\Phi_0)^{1/4}\sqrt{D}, 20 ν DP ( η ) ≤ 20 3 D s ⋆ = 20 3 ( L Φ 0 ) 1/4 D ,
C σ ~ B ( α + 1 α T ) ≤ C σ ~ B s ⋆ K + 2 C σ ~ B s ⋆ ≤ C ( L Φ 0 ) 1 / 4 D + 2 C σ ~ D B L Φ 0 , C\frac{\widetilde{\sigma}}{\sqrt{B}}\left(\sqrt{\alpha}+\frac{1}{\alpha T}\right)\le C\frac{\widetilde{\sigma}}{\sqrt{B}}\sqrt{\frac{s_\star}{K}}+\frac{2C\widetilde{\sigma}}{\sqrt{B}s_\star}\le C(L\Phi_0)^{1/4}\sqrt{D}+\frac{2C\widetilde{\sigma}D}{B\sqrt{L\Phi_0}}, C B σ ( α + α T 1 ) ≤ C B σ K s ⋆ + B s ⋆ 2 C σ ≤ C ( L Φ 0 ) 1/4 D + B L Φ 0 2 C σ D ,
where the last step uses K ≥ s ⋆ σ ~ 2 / ( B L Φ 0 D ) K \ge s_\star\widetilde{\sigma}^2/(B\sqrt{L\Phi_0}D) K ≥ s ⋆ σ 2 / ( B L Φ 0 D ) for the first term and s ⋆ = L Φ 0 / D s_\star= \sqrt{L\Phi_0}/D s ⋆ = L Φ 0 / D for the second. Adding 64 b ~ c 64\widetilde{b}_c 64 b c completes the proof. □ \square □
Discussion. For the ℓ 2 \ell_2 ℓ 2 geometry, E ∥ Z ∥ 2 ≤ d \mathbb{E}\|Z\|_2 \le\sqrt{d} E ∥ Z ∥ 2 ≤ d and ρ 1 = ρ 2 = 1 \rho_1=\rho_2=1 ρ 1 = ρ 2 = 1 , so the bound reads
O ( ( L Φ 0 ) 1 / 4 ( c 2 d log ( 1 / δ ) ) 1 / 4 ( n ε ) − 1 / 2 ) + O ( b ~ c ) O\left((L\Phi_0)^{1/4}(c^2d\log(1/\delta))^{1/4}(n\varepsilon)^{-1/2}\right)+O(\widetilde{b}_c) O ( ( L Φ 0 ) 1/4 ( c 2 d log ( 1/ δ ) ) 1/4 ( n ε ) − 1/2 ) + O ( b c )
up to logarithmic factors in K / η K/\eta K / η , which matches the ( d / ( n ε ) ) 1 / 2 (\sqrt{d}/(n\varepsilon))^{1/2} ( d / ( n ε ) ) 1/2 dependence of private normalized and clipped SGD [87 ] . Condition (33) requires n ε ≳ H log ( 1 / δ ) max { ρ 2 2 L Φ 0 / c , c / L Φ 0 } n\varepsilon\gtrsim H\sqrt{\log(1/\delta)}\max\{\rho_2^2\sqrt{L\Phi_0}/c,c/\sqrt{L\Phi_0}\} n ε ≳ H log ( 1/ δ ) max { ρ 2 2 L Φ 0 / c , c / L Φ 0 } (with the constant 1200 in the first term). The privacy contribution to the bound is below the initial gradient bound 2 L Φ 0 \sqrt{2L\Phi_0} 2 L Φ 0 as soon as n ε ≳ c H log ( 1 / δ ) / L Φ 0 n\varepsilon\gtrsim cH\sqrt{\log(1/\delta)}/\sqrt{L\Phi_0} n ε ≳ cH log ( 1/ δ ) / L Φ 0 (the clipping floor b ~ c \widetilde{b}_c b c does not depend on n ε n\varepsilon n ε ); for c ≲ L Φ 0 c \lesssim\sqrt{L\Phi_0} c ≲ L Φ 0 and the ℓ 2 \ell_2 ℓ 2 geometry both requirements reduce to n ε ≳ d log ( 1 / δ ) n\varepsilon\gtrsim d\log(1/\delta) n ε ≳ d log ( 1/ δ ) , but for c ≪ L Φ 0 c \ll\sqrt{L\Phi_0} c ≪ L Φ 0 , that is, under strongly active clipping, the admissibility requirement is stronger by the factor ρ 2 2 L Φ 0 / c 2 \rho_2^2L\Phi_0/c^2 ρ 2 2 L Φ 0 / c 2 . In the experiments of § 4 , even with L Φ 0 / c = 1 \sqrt{L\Phi_0}/c=1 L Φ 0 / c = 1 and H ≈ d H\approx\sqrt{d} H ≈ d , the first term requires n ε ≳ 6 ⋅ 10 6 n\varepsilon\gtrsim6\cdot10^6 n ε ≳ 6 ⋅ 1 0 6 on CIFAR-10 against the actual n ε = 4 ⋅ 10 5 n\varepsilon=4\cdot10^5 n ε = 4 ⋅ 1 0 5 . Because H H H , and hence D D D , grow with log ( K / η ) \log(K/\eta) log ( K / η ) (so that $s_\star=\sqrt{L\Phi_0}/D shrinks), condition (33) bounds the horizon K K K from above at fixed ( n , ε , δ ) (n,\varepsilon,\delta) ( n , ε , δ ) : the admissible horizons are the integers K K K satisfying the two lower bounds of the corollary, condition (33) , and the accountant condition ε < c 1 q 2 K \varepsilon< c_1 q^{2}K ε < c 1 q 2 K of Proposition 1. Since the dependence on K K K is logarithmic, this range is very large whenever (33) holds with room, but it is not unrestricted. Faster rates for private nonconvex optimization under Lipschitz losses use variance reduction or tree aggregation [79 , 7 , 52 ] ; obtaining them for momentum-LMO methods under active clipping is left for future work.
Privacy Noise and Batch Size in the Experiments
Throughout this appendix the privacy unit is one example (CIFAR-10) or one 1,024-token sequence (language modeling). CIFAR-10 experiments use n = 50 k n = 50\mathrm{k} n = 50 k , 80 epochs, and d ≈ 2 M d \approx2\mathrm{M} d ≈ 2 M . Language-modeling experiments use n ≈ 5.86 ⋅ 10 5 n \approx5.86 \cdot10^{5} n ≈ 5.86 ⋅ 1 0 5 sequences (a 600M-token budget, one epoch) and d ≈ 30 M d \approx30\mathrm{M} d ≈ 30 M . This appendix quantifies the privacy noise in our experiments (Section D.1), checks the conditions of Theorem 1 against the tuned configurations (Section D.2), and reports the spread between optimizers (Section D.3).
The privacy noise as a function of the batch size
With Poisson sampling at rate q = B / n q = B/n q = B / n , E E E epochs, and hence K = E n / B K = En/B K = E n / B steps, the noise multiplier σ m u l t ( B ) \sigma_{\mathrm{mult}}(B) σ mult ( B ) needed for a target ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) is determined by the accountant, and the noise added to the averaged gradient is z k ∼ N ( 0 , c 2 σ D P 2 I ) z_k \sim\mathcal{N}(0,c^2\sigma_{\mathrm{DP}}^2 I) z k ∼ N ( 0 , c 2 σ DP 2 I ) with σ D P = σ m u l t / B \sigma_{\mathrm{DP}} = \sigma_{\mathrm{mult}}/B σ DP = σ mult / B . We computed σ m u l t ( B ) \sigma_{\mathrm{mult}}(B) σ mult ( B ) with the Rényi-DP accountant of the Poisson-subsampled Gaussian mechanism [85 ] (the default fractional and integer orders of Opacus and its conversion to ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) ) for ε = 8 \varepsilon= 8 ε = 8 and δ = 1 / ( 2 n ) \delta= 1/(2n) δ = 1/ ( 2 n ) . Two regimes are relevant:
Large-multiplier regime (σ m u l t ≳ 1 \sigma_{\mathrm{mult}} \gtrsim1 σ mult ≳ 1 , many epochs): the accountant gives σ m u l t ≈ c 2 q K log ( 1 / δ ) / ε ∝ B \sigma_{\mathrm{mult}} \approx c_2 q \sqrt{K\log(1/\delta)}/\varepsilon\propto\sqrt{B} σ mult ≈ c 2 q K log ( 1/ δ ) / ε ∝ B , so the noise on the average decays as B − 1 / 2 B^{-1/2} B − 1/2 , like sampling noise.
Small-multiplier regime (σ m u l t ≲ 1 \sigma_{\mathrm{mult}} \lesssim1 σ mult ≲ 1 , few epochs): σ m u l t \sigma_{\mathrm{mult}} σ mult varies slowly with B B B , so the noise on the average decays almost as B − 1 B^{-1} B − 1 .
Table 3 and Figure 3 report the results. Three facts stand out. First, the root-mean-square norm of the privacy noise, c σ m u l t d / B c\sigma_{\mathrm{mult}}\sqrt{d}/B c σ mult d / B , exceeds the root-mean-square bound c / B c/\sqrt{B} c / B on the sampling error of the clipped mini-batch average by a factor of 37–103 on image classification and 26–192 on language modeling. Because every clipped gradient has norm at most c c c , this bound holds both for fixed-size sampling, where E ∥ g ˉ k − μ k ∥ 2 2 = n − B B ( n − 1 ) 1 n ∑ i ∥ clip c ( ∇ f i ( x k ) ) − μ k ∥ 2 2 ≤ c 2 / B , \mathbb{E}\lVert\bar{g}_k-\mu_k\rVert_2^2 = \frac{n-B}{B(n-1)}\frac{1}{n}\sum_i\lVert\operatorname{clip}_c(\nabla f_i(x_k))-\mu_k\rVert_2^2 \le c^2/B, E ∥ g ˉ k − μ k ∥ 2 2 = B ( n − 1 ) n − B n 1 ∑ i ∥ clip c ( ∇ f i ( x k )) − μ k ∥ 2 2 ≤ c 2 / B , and for Poisson sampling normalized by the expected batch size, where the mean-square error equals 1 − q B 1 n ∑ i ∥ clip c ( ∇ f i ( x k ) ) ∥ 2 2 ≤ c 2 / B \frac{1-q}{B}\frac{1}{n}\sum_i\lVert\operatorname{clip}_c(\nabla f_i(x_k))\rVert_2^2 \le c^2/B B 1 − q n 1 ∑ i ∥ clip c ( ∇ f i ( x k )) ∥ 2 2 ≤ c 2 / B . It bounds the mean-square error, not each realization: with n = 4 n=4 n = 4 , B = 2 B=2 B = 2 , and clipped scalar gradients ( c , c , − c , − c ) (c,c,-c,-c) ( c , c , − c , − c ) , the sample of the two positive gradients has probability 1 / 6 1/6 1/6 and error c > c / 2 c > c/\sqrt{2} c > c / 2 . In root-mean-square terms the gradient noise is therefore set mainly by the privacy parameter rather than by the data. This compares the noises themselves; it does not show that the sampling term of Theorem 1, which is expressed through the centered variance σ \sigma σ of the unclipped gradients, is negligible, since σ \sigma σ is not measured in our experiments. Second, the decay exponent q e f f : = − d log ( σ m u l t / B ) / d log B q_{\mathrm{eff}} := -\mathrm{d}\log(\sigma_{\mathrm{mult}}/B)/\mathrm{d}\log B q eff := − d log ( σ mult / B ) / d log B lies strictly between 1 / 2 1/2 1/2 and 1 1 1 : from 0.87 to 0.53 on image classification and from 0.95 to 0.88 on language modeling. Third, the observed optimal batch sizes lie where the norm of the privacy noise, ∥ z k ∥ 2 ≈ c σ m u l t d / B \lVert z_k\rVert_2 \approx c\sigma_{\mathrm{mult}}\sqrt{d}/B ∥ z k ∥ 2 ≈ c σ mult d / B , is comparable to the clipping radius c c c , which upper-bounds the norm of the expected clipped gradient μ k \mu_k μ k : the ratio is 0.4–0.6 on CIFAR-10 and 0.7–2.4 on language modeling at the optima.
Table 3. Noise multiplier for ( ε , δ ) = ( 8 , 1 / ( 2 n ) ) (\varepsilon, \delta) = (8, 1/(2n)) ( ε , δ ) = ( 8 , 1/ ( 2 n )) from the Rényi-DP accountant, ratio of the privacy-noise norm to the clipping radius (NSR = σ m u l t d / B = \sigma_{\mathrm{mult}}\sqrt{d}/B = σ mult d / B ), and ratio of the root-mean-square norm of the privacy noise to the root-mean-square bound c / B c/\sqrt{B} c / B on the sampling error of clipped gradients (DP/samp. = σ m u l t d / B = \sigma_{\mathrm{mult}}\sqrt{d/B} = σ mult d / B ). Since c / B c/\sqrt{B} c / B is an upper bound, this ratio is a lower bound on the ratio of root-mean-square noise levels; it does not bound individual realizations. Bold: observed DP-optimal batch sizes (Figure 1 and Figure 2 ). The row B = 2500 B = 2500 B = 2500 for CIFAR-10 is included for the accountant only; it is not part of the DP grid of Appendix § 14 .§ 1 .
Figure 2. Language modeling (30M GPT): best loss versus batch size at the best learning rate and momentum for each batch size. Left: non-private. Right: DP (ε = 8 \varepsilon= 8 ε = 8 ), including Scion. Note the different batch-size and loss ranges.
Applicability of Theorem 1 in the experiments
With σ D P = σ m u l t / B \sigma_{\mathrm{DP}} = \sigma_{\mathrm{mult}}/B σ DP = σ mult / B , the noise condition in (3) reads
B ≥ 20 3 ρ 2 α H σ m u l t ( B ) , (34) B \ge20\sqrt{3}\rho_2\sqrt{\alpha}H\sigma_{\mathrm{mult}}(B), \tag*{(34)} B ≥ 20 3 ρ 2 α H σ mult ( B ) , (34)
with H = E ∥ Z ∥ ⋆ + ρ 1 2 log ( T / η ) H = \mathbb{E}\lVert Z\rVert_{\star} + \rho_1\sqrt{2\log(T/\eta)} H = E ∥ Z ∥ ⋆ + ρ 1 2 log ( T / η ) ; it is a lower bound on the batch size. For the ℓ 2 \ell_2 ℓ 2 geometry (H ≈ d H \approx\sqrt{d} H ≈ d , ρ 2 = 1 \rho_2 = 1 ρ 2 = 1 ) it is equivalent to NSR = σ m u l t d / B ≤ 1 / ( 20 3 α ) = \sigma_{\mathrm{mult}}\sqrt{d}/B \le1/(20\sqrt{3}\sqrt{\alpha}) = σ mult d / B ≤ 1/ ( 20 3 α ) , that is, NSR ≤ 0.13 \le0.13 ≤ 0.13 , 0.09 0.09 0.09 , and 0.065 0.065 0.065 for α = 0.05 \alpha= 0.05 α = 0.05 , 0.1 0.1 0.1 , and 0.2 0.2 0.2 . The observed optima sit at NSR ≈ 0.4 \approx0.4 ≈ 0.4 –2.4 2.4 2.4 (Table 3 ), about 4 4 4 –27 27 27 times above this threshold for α = 0.1 \alpha= 0.1 α = 0.1 ; this is an observation about the experiments, not a consequence of the theorem. Read as a constraint on the momentum, the condition α ≤ 1 / ( 1200 ρ 2 2 σ D P 2 H 2 ) \alpha\le1/(1200\rho_2^2\sigma_{\mathrm{DP}}^2H^2) α ≤ 1/ ( 1200 ρ 2 2 σ DP 2 H 2 ) requires 1 − α ≥ 0.997 1-\alpha\ge0.997 1 − α ≥ 0.997 at the CIFAR-10 optimum B = 5000 B = 5000 B = 5000 and 1 − α ≥ 0.9996 1-\alpha\ge0.9996 1 − α ≥ 0.9996 at B = 1024 B = 1024 B = 1024 , and for language modeling at B ∈ { 1024 , 2048 } B \in\{1024, 2048\} B ∈ { 1024 , 2048 } a momentum window 1 / α 1/\alpha 1/ α of 2 ⋅ 10 3 2\cdot10^3 2 ⋅ 1 0 3 –7 ⋅ 10 3 7\cdot10^3 7 ⋅ 1 0 3 steps, longer than the horizon K K K . Within our grids it holds only at the largest batch sizes with 1 − α = 0.99 1-\alpha= 0.99 1 − α = 0.99 . Theorem 1 also requires the run-in T = K − ⌈ log 2 / α ⌉ > 0 T = K-\lceil\log2/\alpha\rceil> 0 T = K − ⌈ log 2/ α ⌉ > 0 , which for 1 − α = 0.99 1-\alpha= 0.99 1 − α = 0.99 means K > 70 K > 70 K > 70 : this holds for CIFAR-10 at B = 25000 B = 25000 B = 25000 (K = 160 K = 160 K = 160 ) but not for language modeling at B = 16384 B = 16384 B = 16384 (K = 36 K = 36 K = 36 ). For the spectral geometry, H 2 ≍ min { m , n ′ } 2 max { m , n ′ } H^2 \asymp\min\{m,n'\}^2\max\{m,n'\} H 2 ≍ min { m , n ′ } 2 max { m , n ′ } exceeds d = m n ′ d = mn' d = m n ′ by the factor min { m , n ′ } \min\{m,n'\} min { m , n ′ } , so the condition is more restrictive still: E ∥ Z ∥ n u c / m n ′ > 2.5 \mathbb{E}\lVert Z\rVert_{\mathrm{nuc}}/\sqrt{mn'} > 2.5 E ∥ Z ∥ nuc / m n ′ > 2.5 for every matrix with min { m , n ′ } ≥ 10 \min\{m,n'\} \ge10 min { m , n ′ } ≥ 10 , which covers the weight matrices of our networks, whereas the ℓ 2 \ell_2 ℓ 2 condition holds at CIFAR-10, B = 25000 B = 25000 B = 25000 , 1 − α = 0.99 1-\alpha= 0.99 1 − α = 0.99 only with a margin of about 1.25, so no configuration satisfies the spectral condition. Within our grids, Theorem 1 therefore covers, in the ℓ 2 \ell_2 ℓ 2 specialization, only CIFAR-10 at B = 25000 B = 25000 B = 25000 with 1 − α = 0.99 1-\alpha= 0.99 1 − α = 0.99 , and none of the configurations at the observed optima.
Spread between optimizers
The following observations are read from the annotated heatmaps. At the same batch size, and hence the same number of steps, privacy reduces the differences between optimizers on language modeling (Table 4 ): the spread of the best losses across SGD, Adam, and Muon drops from 1.69 to 0.09 nats at B = 128 B = 128 B = 128 and from 2.84 to 0.22 nats at B = 1024 B = 1024 B = 1024 . Under privacy the spread grows with the batch size, from 0.08–0.09 nats for B ≤ 256 B \le256 B ≤ 256 (NSR ≈ 9 \approx9 ≈ 9 ) to 0.89 nats at B = 16384 B = 16384 B = 16384 (NSR = 0.2 = 0.2 = 0.2 ), and to 1.23 nats when Scion is included. At the smallest batch sizes the models also learn little (losses of 6.7–6.9 nats). On CIFAR-10 the spread grows from at most 1.5 accuracy points for B ≤ 512 B \le512 B ≤ 512 to 7.6 points at B = 25000 B = 25000 B = 25000 (NSR = 0.23 = 0.23 = 0.23 ); note that Figure 4 –Figure 5 report accuracy, whereas § 4 reports loss.
Table 4. Best loss per optimizer and batch size for language modeling (from the heatmaps; lower is better) and spread across optimizers. Non-private runs use B ≤ 1024 B \le1024 B ≤ 1024 ; Scion was run only with privacy and is excluded from the spread for comparability.
Figure 4. CNN, non-private: peak test accuracy for each batch size and learning rate (top) or momentum (bottom ).
Figure 5. CNN, DP (ε = 8 \varepsilon= 8 ε = 8 ): peak test accuracy for each batch size and learning rate (top ) or momentum (bottom ).
Detailed Comparison with Existing Guarantees
Per-example versus aggregate clipping. We compare only with analyses of mechanisms that clip individual examples before aggregation, as in (35) ,
g ^ k = 1 B ∑ i ∈ S k clip c ( ∇ f i ( x k ) ) + z k . (35) \hat{g}_k = \frac{1}{B} \sum_{i \in S_k} \operatorname{clip}_c(\nabla f_i(x_k)) + z_k. \tag*{(35)} g ^ k = B 1 i ∈ S k ∑ clip c ( ∇ f i ( x k )) + z k . (35)
Clipping a single vector only rescales it, clip c ( g ) = a c ( g ) g \operatorname{clip}_c(g) = a_c(g)g clip c ( g ) = a c ( g ) g with a c ( g ) > 0 a_c(g) > 0 a c ( g ) > 0 , so a scale-invariant LMO is unaffected by clipping an exact gradient, a batch average, or a client update. In contrast, the average in (35) need not even be positively correlated with the unclipped mean: with c = 1 c = 1 c = 1 and per-example gradients ( 4 , − 1 , − 1 ) (4, -1, -1) ( 4 , − 1 , − 1 ) in one dimension, the unclipped mean is 2 / 3 2/3 2/3 while the clipped mean is − 1 / 3 -1/3 − 1/3 , and a larger batch does not help because all examples are already used. The two mechanisms also differ in privacy calibration: under add/remove adjacency (the Poisson case of Proposition 1), the sum of individually clipped gradients has ℓ 2 \ell_2 ℓ 2 -sensitivity c c c , whereas clipping an aggregate of unbounded gradients only gives sensitivity 2 c 2c 2 c for the aggregate.
Aligning conventions. Three conventions differ across the literature. First, the stationarity measure: a bound O ( K − 1 / 2 ) + N O(K^{-1/2}) + \mathcal{N} O ( K − 1/2 ) + N on an averaged squared norm gives, by Jensen’s inequality, O ( K − 1 / 4 ) + O ( N ) O(K^{-1/4}) + O(\sqrt{\mathcal{N}}) O ( K − 1/4 ) + O ( N ) on the norm, and best-iterate, averaged, and expected-minimum statements are ordered as E min k ∥ g k ∥ ≤ min k E ∥ g k ∥ ≤ 1 K ∑ k E ∥ g k ∥ \mathbb{E}\min_k \|g_k\| \le\min_k \mathbb{E}\|g_k\| \le\frac{1}{K}\sum_k \mathbb{E}\|g_k\| E min k ∥ g k ∥ ≤ min k E ∥ g k ∥ ≤ K 1 ∑ k E ∥ g k ∥ . Second, the noise convention: writing s s s for the per-coordinate standard deviation of the noise after averaging, our z k ∼ N ( 0 , c 2 σ D P 2 I ) z_k \sim\mathcal{N}(0,c^2\sigma_{\mathrm{DP}}^2 I) z k ∼ N ( 0 , c 2 σ DP 2 I ) has s = c σ D P s=c\sigma_{\mathrm{DP}} s = c σ DP , a noise multiplier σ m u l t \sigma_{\mathrm{mult}} σ mult on the sum gives s = c σ m u l t / B s=c\sigma_{\mathrm{mult}}/B s = c σ mult / B , and Koloskova et al. [38 ] use s = σ D P / d s=\sigma_{\mathrm{DP}}/\sqrt{d} s = σ DP / d without the factor c c c . Third, whether a rate in K K K holds at a fixed noise scale , so that the total privacy budget grows with K K K , or after the noise has been calibrated to a fixed ( ε , δ ) (\varepsilon,\delta) ( ε , δ ) ; a calibrated bound typically does not vanish with K K K . Theorem 1 and Appendix § 10 .§ 1 are fixed-noise statements, and Corollary 6 is the calibrated one.
Centered variance versus raw moments. For every x x x ,
1 n ∑ i = 1 n ∥ ∇ f i ( x ) ∥ 2 2 = ∥ ∇ f ( x ) ∥ 2 2 + 1 n ∑ i = 1 n ∥ ∇ f i ( x ) − ∇ f ( x ) ∥ 2 2 . (36) \frac{1}{n}\sum_{i=1}^{n}\|\nabla f_i(x)\|_2^2 = \|\nabla f(x)\|_2^2 + \frac{1}{n}\sum_{i=1}^{n}\|\nabla f_i(x)-\nabla f(x)\|_2^2. \tag*{(36)} n 1 i = 1 ∑ n ∥∇ f i ( x ) ∥ 2 2 = ∥∇ f ( x ) ∥ 2 2 + n 1 i = 1 ∑ n ∥∇ f i ( x ) − ∇ f ( x ) ∥ 2 2 . (36)
Hence a bound on the raw second moment of per-example gradients along the trajectory also bounds the mean gradient, and a light-tail condition such as 1 n ∑ i exp ( ∥ ∇ f i ( x ) ∥ 2 2 / G 0 2 ) ≤ e \frac{1}{n}\sum_i \exp(\|\nabla f_i(x)\|_2^2/G_0^2) \le e n 1 ∑ i exp ( ∥∇ f i ( x ) ∥ 2 2 / G 0 2 ) ≤ e implies it by Jensen’s inequality. Assumption 2 bounds only the centered term on the right, and Lemma 1 uses nothing else.
Notes on Table 1 .
Koloskova et al. [38 ] : Appendix C.4 (the main-text theorem is stated for the minimum over iterates); the DP extension uses ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) -smoothness with a trajectory-dependent constant, and we compare the case L 1 = 0 L_1=0 L 1 = 0 . Their lower bounds show that the floor min { σ , σ 2 / c } \min\{\sigma,\sigma^2/c\} min { σ , σ 2 / c } cannot be improved for clipped SGD under bounded variance.
Yang et al. [87 ] : Theorem 3.4 (fixed) and Corollary 3.5 (calibrated), under ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) -smoothness and ∥ ∇ f i − ∇ f ∥ ≤ τ 0 + τ 1 ∥ ∇ f ∥ \|\nabla f_i-\nabla f\|\le\tau_0+\tau_1\|\nabla f\| ∥∇ f i − ∇ f ∥ ≤ τ 0 + τ 1 ∥∇ f ∥ almost surely with c > 2 τ 0 / ( 1 − τ 1 ) c>2\tau_0/(1-\tau_1) c > 2 τ 0 / ( 1 − τ 1 ) ; the bound is on E min k ∥ ∇ f ( x k ) ∥ \mathbb{E}\min_k\|\nabla f(x_k)\| E min k ∥∇ f ( x k ) ∥ .
Chen et al. [15 ] : Theorem 5. The per-example noise is arbitrary; the bound is stated for a weighted clipped stationarity measure plus a Wasserstein distance between the noise distribution and a symmetric reference, which vanishes for symmetric noise.
Shulgin and Richtárik [72 ] : Theorem 2, with 1 < q ≤ 2 1<q\le2 1 < q ≤ 2 and an exact norm-quantile oracle.
Vatan Khah et al. [82 ] : Theorem 4.4 and Corollary 4.5 of arXiv v2 (fixed noise) and their Appendix H (calibrated via advanced composition, without subsampling), with 1 < p ≤ 2 1<p\le2 1 < p ≤ 2 , B = 1 B=1 B = 1 , and local smoothness; the bound holds with high probability and carries log ( K / η ) \log(K/\eta) log ( K / η ) factors.
Kim and Fan (2026) (v2): Theorem 4.3 contains a clipping residual of order E ( ∥ ∇ f i ∥ − c ) + \mathbb{E}(\|\nabla f_i\|-c)_+ E ( ∥∇ f i ∥ − c ) + . Corollary F.2 assumes an exponential moment of per-example gradient norms and uses c K ∝ log K c_K\propto\sqrt{\log K} c K ∝ log K , giving K − 1 / 4 log K K^{-1/4}\sqrt{\log K} K − 1/4 log K ; Corollary F.3 assumes a raw second moment and uses c K ∝ K 1 / 6 c_K\propto K^{1/6} c K ∝ K 1/6 , giving K − 1 / 6 K^{-1/6} K − 1/6 . Both are in expectation, for the sum of blockwise nuclear norms of matrix parameters, with a fixed noise multiplier , so that the noise standard deviation grows with c K c_K c K . The vanishing rates require the number of Newton–Schulz steps to grow logarithmically with the horizon.
This work: Theorem 1, Corollaries 1 and 6; exact LMO, the conditions (3) , high probability over the privacy noise and expectation over sampling.
Discussion. Among guarantees for per-example clipping, ours is, to our knowledge, the only one for momentum-LMO dynamics in a general norm that requires only a centered variance bound. Its fixed-noise rate matches the O ( K − 1 / 4 ) \mathcal{O}(K^{-1/4}) O ( K − 1/4 ) rate of clipped SGD on the average gradient norm (Koloskova et al., [38 ] ), which is optimal under bounded variance even without clipping (Arjevani et al., [6 ] ), up to the ( log K ) 1 / 4 (\log K)^{1/4} ( log K ) 1/4 factor from our high-probability treatment of the privacy noise. Compared with Kim and Fan (2026), the main differences are as follows. (i) Our clipping floor ρ 1 min { σ , σ 2 / c } \rho_1\min\{\sigma,\sigma^2/c\} ρ 1 min { σ , σ 2 / c } vanishes as the sampling noise vanishes, even when ∥ ∇ f ∥ 2 ≫ c \|\nabla f\|_2\gg c ∥∇ f ∥ 2 ≫ c , because the deterministic part of the clipping bias is a rescaling that the LMO ignores; their residual E [ ( ∥ ∇ f i ∥ − c ) + ] \mathbb{E}[(\lVert\nabla f_i\rVert-c)_+] E [(∥ ∇ f i ∥ − c ) + ] does not vanish in this case. (ii) We need no moment bounds on the raw gradients, which by (36) would also bound the mean gradient, and no clipping threshold growing with K K K . (iii) Our bound holds for any norm and with high probability over the privacy noise. On the other hand, their vanishing rates have no floor (at the price of a growing threshold), and they analyze finite-step Newton–Schulz and a bias-corrected variant, whereas we assume an exact LMO; their rates and ours are therefore not directly comparable. Shanmugam et al. [70 ] give a Wedin-type condition under which orthogonalization recovers the leading singular directions of a privatized gradient and document the resulting phase transition empirically; their results concern spectral recovery at a single step rather than convergence of the algorithm.
Extended Related Work
Muon and LMO-based optimization. Muon applies an approximate polar-factor transformation to a momentum matrix and can be interpreted as stochastic spectral descent [14 , 41 ] ; practical implementations use a few Newton–Schulz iterations [9 , 73 ] , whose effect on convergence is analyzed by Kim and Oh (2026). The LMO formulation of Pethick et al. [66 ] places Muon within a broader class of norm-constrained non-Euclidean methods that includes normalized, sign-based, and coordinate-type updates, extended layer-wise by Gluon [68 ] ; trust-region analyses [40 ] (Kovalev and Borodich 2025) study the interplay between momentum and noise. For normalized SGD, Cutkosky and Mehta [16 ] established the K − 1 / 4 K^{-1/4} K − 1/4 rate with momentum, and Cutkosky and Mehta [17 ] combined clipping, momentum, and normalization in general normed spaces under heavy-tailed noise, with an additive clipping bias controlled by a growing threshold. Practical and distributed variants include BP-Muon and Drop-Muon [34 , 27 ] and the distributed or compressed methods Dion, MuLoCo, EF21-Muon, and Compressed Gluon [3 , 77 , 26 , 67 ] .
Clipping, normalization, and private optimization. Clipping and normalization are used to stabilize training [63 , 56 , 12 , 11 ] and to limit the influence of unreliable updates in robust distributed optimization [33 , 53 , 29 ] . In differential privacy, clipping bounds the sensitivity of each example [1 ] , also in federated settings [23 , 55 , 80 ] , and makes the gradient estimator biased whenever it is active [15 , 38 ] . Per-sample normalization [13 , 87 ] removes the dependence on the threshold, and Tang et al. [76 ] show that the nonlinear post-processing of noisy gradients by Adam introduces a bias that can be corrected, the analogue of DP-MuonBC (Kim and Fan, 2026). Monzio Compagnoni et al. [57 ] compare DP-SignSGD, the ℓ ∞ \ell_\infty ℓ ∞ instance of an LMO method, with DP-SGD through stochastic differential equations and find that adaptive methods are preferable at high privacy. Many convergence analyses of private methods simplify clipping through bounded gradients [91 , 45 , 92 , 83 , 51 , 58 , 84 ] , bounded noise or heterogeneity [48 , 60 ] , or inactive clipping [60 , 90 ] ; Das et al. [18 ] study normalized client updates for convex federated objectives. Outside privacy, clipping is analyzed for nonsmooth or fast-growing convex functions [71 , 22 , 5 ] , under generalized smoothness [89 , 25 , 81 , 49 , 28 , 78 ] , and under heavy-tailed noise [24 , 59 ] . For private nonconvex optimization with Lipschitz losses, faster rates are obtained with variance reduction or tree aggregation [79 , 7 , 52 ] , and private Frank–Wolfe-type methods in ℓ p \ell_p ℓ p geometries are studied by Bassily et al. [8 ] .
Additional Experimental Details
Our implementation uses PyTorch (Paszke et al., [64 ] ) and Opacus (Yousefpour et al., [88 ] ), builds on the code of Jordan (2024) for CIFAR-10, and all models are trained on 4 NVIDIA A100-PCIE-40GB GPU. CIFAR-10 is distributed by its authors for research use; FineWeb is released under the ODC-By 1.0 license; the CIFAR Airbench, and NanoGPT code are MIT-licensed. In all heatmaps, each cell shows the best value over the remaining hyperparameter; the red box marks the best configuration overall and black boxes mark the best value along each column. Due to computational constraints across the extensive hyperparameter sweeps, each cell in the heatmaps represents a single training run. For CIFAR-10, the line plots in Figure 1 , Figure 6 report the mean and standard deviation across three independent runs.
Figure 6. CNN, B = 1024 B = 1024 B = 1024 : peak test accuracy and best test loss versus the privacy budget ε \varepsilon ε , with hyperparameters tuned at ε = 8 \varepsilon= 8 ε = 8 . Shaded regions show the standard deviation over three runs.
CIFAR-10
Non-private. We evaluate learning rates γ ∈ { 10 − 4 , 10 − 3 , 10 − 2 , 10 − 1 , 1 } \gamma\in\{10^{-4}, 10^{-3}, 10^{-2}, 10^{-1}, 1\} γ ∈ { 1 0 − 4 , 1 0 − 3 , 1 0 − 2 , 1 0 − 1 , 1 } , momentum values 1 − α ∈ { 0 , 0.6 , 0.8 , 0.9 , 0.95 , 0.99 } 1-\alpha\in\{0, 0.6, 0.8, 0.9, 0.95, 0.99\} 1 − α ∈ { 0 , 0.6 , 0.8 , 0.9 , 0.95 , 0.99 } , and batch sizes B ∈ { 32 , 64 , 128 , 256 , 512 , 1024 , 2500 } B \in\{32, 64, 128, 256, 512, 1024, 2500\} B ∈ { 32 , 64 , 128 , 256 , 512 , 1024 , 2500 } . Figure 4 shows that Muon is robust to the learning rate (accuracy within about one point for γ ∈ { 10 − 2 , 10 − 1 , 1 } \gamma\in\{10^{-2}, 10^{-1}, 1\} γ ∈ { 1 0 − 2 , 1 0 − 1 , 1 } at most batch sizes), whereas Adam and SGD are more sensitive to it. For SGD, the best learning rate lies at the upper end of the grid (γ = 1 \gamma= 1 γ = 1 ) for most batch sizes.
Private. We evaluate learning rates γ ∈ { 10 − 3 , 10 − 2 , 10 − 1 , 1 , 10 } \gamma\in\{10^{-3}, 10^{-2}, 10^{-1}, 1, 10\} γ ∈ { 1 0 − 3 , 1 0 − 2 , 1 0 − 1 , 1 , 10 } , momentum values 1 − α ∈ { 0 , 0.6 , 0.8 , 0.9 , 0.95 , 0.99 } 1-\alpha\in\{0, 0.6, 0.8, 0.9, 0.95, 0.99\} 1 − α ∈ { 0 , 0.6 , 0.8 , 0.9 , 0.95 , 0.99 } , and batch sizes B ∈ { 64 , 128 , 256 , 512 , 1024 , 5000 , 10000 , 25000 } B \in\{64, 128, 256, 512, 1024, 5000, 10000, 25000\} B ∈ { 64 , 128 , 256 , 512 , 1024 , 5000 , 10000 , 25000 } . Figure 5 shows that DP-Muon remains comparatively robust to the learning rate, although the window of good learning rates is narrower than without privacy, and that DP-Adam has the same optimal learning rate (10 − 2 10^{-2} 1 0 − 2 ) at every batch size. For DP-SGD, the best learning rate lies at the upper end of the grid (γ = 10 \gamma= 10 γ = 10 ) for B ≥ 256 B \ge256 B ≥ 256 .
Privacy-budget ablation
We vary the privacy budget ε ∈ { 1 , 3 , 5 , 8 } \varepsilon\in\{1, 3, 5, 8\} ε ∈ { 1 , 3 , 5 , 8 } at batch size B = 1024 B = 1024 B = 1024 . For each method, we select the best configuration at ε = 8 \varepsilon= 8 ε = 8 and reuse it for all other values of ε \varepsilon ε . As shown in Figure 6 , all methods perform similarly. DP-Muon is on par with or slightly better than the baselines for ε ∈ { 1 , 5 , 8 } \varepsilon\in\{1, 5, 8\} ε ∈ { 1 , 5 , 8 } , with larger variance at ε = 3 \varepsilon= 3 ε = 3 , and DP-Adam is the least accurate at ε = 1 \varepsilon= 1 ε = 1 and ε = 8 \varepsilon= 8 ε = 8 .
Language modeling
Non-private. We evaluate momentum values 1 − α ∈ { 0.8 , 0.9 , 0.95 , 0.99 } 1 - \alpha\in\{0.8, 0.9, 0.95, 0.99\} 1 − α ∈ { 0.8 , 0.9 , 0.95 , 0.99 } , batch sizes B ∈ { 32 , 64 , 128 , 256 , 512 , 1024 } B \in\{32, 64, 128, 256, 512, 1024\} B ∈ { 32 , 64 , 128 , 256 , 512 , 1024 } , and the optimizer-specific learning-rate grids shown in Figure 7 : { 10 − 3 , 5 ⋅ 10 − 3 , 10 − 2 , 5 ⋅ 10 − 2 , 10 − 1 } \{10^{-3}, 5 \cdot10^{-3}, 10^{-2}, 5 \cdot10^{-2}, 10^{-1}\} { 1 0 − 3 , 5 ⋅ 1 0 − 3 , 1 0 − 2 , 5 ⋅ 1 0 − 2 , 1 0 − 1 } for SGD and Muon, and { 5 ⋅ 10 − 4 , 10 − 3 , 5 ⋅ 10 − 3 , 10 − 2 , 5 ⋅ 10 − 2 } \{5 \cdot10^{-4}, 10^{-3}, 5 \cdot10^{-3}, 10^{-2}, 5 \cdot10^{-2}\} { 5 ⋅ 1 0 − 4 , 1 0 − 3 , 5 ⋅ 1 0 − 3 , 1 0 − 2 , 5 ⋅ 1 0 − 2 } for Adam. For every optimizer, the optimal learning rate is the same at all batch sizes (0.05 for SGD, 10 − 3 10^{-3} 1 0 − 3 for Adam, and 0.1 for Muon, at the upper end of its grid), and Muon achieves the lowest loss at every batch size, with a gap to Adam that grows with B B B .
Figure 7. GPT (30M), non-private: best loss for each batch size and learning rate (top ) or momentum (bottom ).
Private. We evaluate momentum values 1 − α ∈ { 0.8 , 0.9 , 0.95 , 0.99 } 1 - \alpha\in\{0.8, 0.9, 0.95, 0.99\} 1 − α ∈ { 0.8 , 0.9 , 0.95 , 0.99 } , batch sizes B ∈ { 128 , 256 , 512 , 1024 , 2048 , 4096 , 8192 , 16384 } B \in\{128, 256, 512, 1024, 2048, 4096, 8192, 16384\} B ∈ { 128 , 256 , 512 , 1024 , 2048 , 4096 , 8192 , 16384 } , and the learning rates { 10 − 3 , 5 ⋅ 10 − 3 , 10 − 2 , 5 ⋅ 10 − 2 , 10 − 1 , 0.5 , 1 } \{10^{-3}, 5 \cdot10^{-3}, 10^{-2}, 5 \cdot10^{-2}, 10^{-1}, 0.5, 1\} { 1 0 − 3 , 5 ⋅ 1 0 − 3 , 1 0 − 2 , 5 ⋅ 1 0 − 2 , 1 0 − 1 , 0.5 , 1 } for SGD, { 5 ⋅ 10 − 4 , 10 − 3 , 3 ⋅ 10 − 3 , 5 ⋅ 10 − 3 , 10 − 2 , 5 ⋅ 10 − 2 } \{5 \cdot10^{-4}, 10^{-3}, 3 \cdot10^{-3}, 5 \cdot10^{-3}, 10^{-2}, 5 \cdot10^{-2}\} { 5 ⋅ 1 0 − 4 , 1 0 − 3 , 3 ⋅ 1 0 − 3 , 5 ⋅ 1 0 − 3 , 1 0 − 2 , 5 ⋅ 1 0 − 2 } for Adam, { 5 ⋅ 10 − 3 , 10 − 2 , 5 ⋅ 10 − 2 , 0.1 , 0.2 , 0.5 } \{5 \cdot10^{-3}, 10^{-2}, 5 \cdot10^{-2}, 0.1, 0.2, 0.5\} { 5 ⋅ 1 0 − 3 , 1 0 − 2 , 5 ⋅ 1 0 − 2 , 0.1 , 0.2 , 0.5 } for Muon, and { 10 − 2 , 5 ⋅ 10 − 2 , 0.1 , 0.2 , 0.5 , 1 } \{10^{-2}, 5 \cdot10^{-2}, 0.1, 0.2, 0.5, 1\} { 1 0 − 2 , 5 ⋅ 1 0 − 2 , 0.1 , 0.2 , 0.5 , 1 } for Scion, obtained by refining a common initial grid around each optimizer’s best configurations. Scion applies Newton–Schulz orthogonalization to all hidden layers and sign updates to the embedding and output layers. Figure 8 –Figure 10 show the following. (i) The optimal learning rate of DP-Muon increases with the batch size (0.05 for B ≤ 512 B \le512 B ≤ 512 , 0.1 for 1024 ≤ B ≤ 4096 1024 \le B \le4096 1024 ≤ B ≤ 4096 , 0.2 for B ≥ 8192 B \ge8192 B ≥ 8192 ), while that of DP-Adam stays in [ 10 − 3 , 3 ⋅ 10 − 3 ] [10^{-3}, 3 \cdot10^{-3}] [ 1 0 − 3 , 3 ⋅ 1 0 − 3 ] . (ii) At its optimal learning rate, the loss of DP-Muon varies by about 0.1 nats or less over 1 − α ∈ { 0.8 , 0.9 , 0.95 } 1 - \alpha\in\{0.8, 0.9, 0.95\} 1 − α ∈ { 0.8 , 0.9 , 0.95 } at every batch size, and 1 − α = 0.99 1 - \alpha= 0.99 1 − α = 0.99 is worse at small batch sizes; the selected momentum therefore changes from one batch size to the next without a clear trend. (iii) For DP-SGD, the loss depends strongly on the momentum at a given learning rate, reflecting the coupling between the two through the effective step size. (iv) For Scion at B = 16384 B = 16384 B = 16384 , the best learning rate is the largest one in the grid.
Figure 8. GPT (30M), DP (ε = 8 \varepsilon= 8 ε = 8 ): best loss for each batch size and learning rate (top ) or momentum (bottom ).
Figure 10. GPT (30M), DP (ε = 8 \varepsilon= 8 ε = 8 ): best loss for every learning rate (columns) and momentum (rows), for B ∈ { 2048 , 4096 , 8192 , 16384 } B \in\{2048, 4096, 8192, 16384\} B ∈ { 2048 , 4096 , 8192 , 16384 } . “Gluon Scale 1” denotes the Scion variant used in Figure 2 .
Figure 9. GPT (30M), DP (ε = 8 \varepsilon= 8 ε = 8 ): best loss for every learning rate (columns) and momentum (rows), for B ∈ { 128 , 256 , 512 , 1024 } B \in\{128,256,512,1024\} B ∈ { 128 , 256 , 512 , 1024 } . “Gluon Scale 1” denotes the Scion variant used in Figure 2 .