How Does Muon Work in Private Deep Learning? Scalable Differentially Private Training via Orthogonalization

Alexander Gaponov, Grigory Malinovsky, Egor Shulgin, Peter Richtarik

Oct 17, 2026arXiv:2610.24736v1

cs.LG

Scorecard· 16/16

5.5/10 impact

Elegant rescaling insight and honest, thorough study, but theory does not cover practical regimes, empirical gains are marginal, and concurrent works overlap.

Abstract

Training deep neural networks requires optimizers that balance computational efficiency with formal data privacy. While orthogonalized update rules, such as the recently introduced Muon optimizer, have shown strong empirical performance and scalability, their behavior under Differential Privacy (DP) is not yet understood. In this paper, we propose DP-Muon, a differentially private variant of the Muon optimizer. By analyzing Muon's orthogonalized updates through the lens of a Linear Minimization Oracle (LMO), we show that the leading effect of per-example clipping is a positive rescaling of the gradient, to which the LMO is blind, so that only a small directional residual controlled by the centered gradient variance enters the optimization error. This yields an $\mathcal O(K^{-1/4})$ convergence rate, up to logarithmic factors, to a clipping-dependent neighborhood at a fixed noise scale and, with noise calibrated to a fixed $(\varepsilon,δ)$ budget, the standard $(\sqrt d/(n\varepsilon))^{1/2}$ privacy--utility bound of DP-SGD, without assuming bounded gradients. Furthermore, we investigate the hyperparameter landscape of DP-Muon and document how the optimal learning rate, momentum, and batch size change under privacy. Empirically, on image classification DP-Muon matches or improves on DP-SGD and DP-Adam, whereas on language modeling the best optimizer depends on the batch size, with DP-Muon best at small batches and DP-Adam best near the privacy-optimal batch size.

AI Impact Assessments

(1 model)

Core Contribution

The paper studies Muon-style orthogonalized updates under differential privacy, where the optimizer is applied to per-example-clipped, Gaussian-noised gradients. Its key observation is that a linear minimization oracle (LMO) is scale-invariant. In expectation, per-example clipping acts mostly as a positive rescaling of the true gradient, λ(g)g, plus a residual that is controlled by the centered variance (Lemma 1). The LMO is blind to the rescaling, so only the small directional residual enters the error.

Combined with a projective LMO inequality (Lemma 2), this gives a convergence analysis for private momentum-LMO methods in any finite-dimensional norm, covering Muon, Scion, signSGD and normalized SGD. The analysis needs only a bounded centered variance, not bounded gradients and not a clipping threshold that grows with the horizon.

Rates: O(K^{-1/4}) to a clipping floor ρ₁·min{σ, σ²/c} at fixed noise. With noise calibrated to an (ε,δ) budget, it recovers the standard (√d/(nε))^{1/2} DP-SGD-type bound.

Empirical contribution: a large hyperparameter study (learning rate, momentum, batch size) on CIFAR-10 and a 30M-parameter GPT.

Findings: under DP the optimal batch size grows by 15–300×, and the optimizer ranking becomes batch-size dependent. DP-Muon is best at small batches, DP-Adam near the privacy-optimal batch, and Scion at very large batches.

Methodological Rigor

The theory is clean and carefully stated, with detailed appendix proofs. The case analysis in Lemma 1 and the Gaussian concentration argument look sound. The authors are unusually candid about the gaps.

Admissibility condition: Theorem 1 requires the filtered privacy noise to be smaller than the clipping radius. The authors show this fails for essentially all experimental configurations at the observed optima, by 4–27× in the ℓ₂ specialization and entirely in the spectral geometry. The theory therefore does not explain the empirical optima.

Other theory gaps: it assumes an exact LMO (experiments use 5 Newton–Schulz steps), fixed-size batches (experiments use Poisson sampling), and a clipping floor that persists.

Dimension dependence: worst-case dual-norm noise handling means the spectral geometry shows no demonstrated advantage. The paper itself says the advantage depends on L_op ≪ rL_F.

Experiments: CIFAR-10 uses three seeds. All language-modeling results and all heatmaps are single runs. Differences between optimizers (up to 0.09 nats at small batches) are within plausible noise. Some baselines sit at the grid edge (DP-SGD, Scion at the largest batch), so tuning may be incomplete. The scale is small (2M-parameter CNN, 30M GPT). BatchNorm is replaced and biases removed.

Positive: hyperparameters are tuned per optimizer and batch size, the privacy accounting is documented, and Appendix D quantifies the noise regime honestly.

Potential Impact

The rescaling-blindness insight is elegant and likely reusable. It explains why scale-invariant updates are natural partners for clipping, and it extends to normalized and sign methods. It may influence follow-up analyses of private non-Euclidean optimizers.

Practical impact is more modest. The empirical benefit of DP-Muon is marginal on vision and regime-dependent on language modeling, where DP-Adam wins at the privacy-optimal batch. The finding that batch size dominates, and that conclusions do not transfer from non-private training, is useful guidance but largely consistent with De et al. and Sander et al.

The area is crowded. Two concurrent works (Kim & Fan 2026; Shanmugam et al. 2026) study the same algorithm under the same name. The novelty is therefore a competitive, partly overlapping advance, with the claim being a tighter, more general analysis under weaker assumptions rather than a first-of-its-kind result.

Timeliness & Relevance

Muon is a hot optimizer, and private training of LLMs is a growing need. Asking whether Muon's gains survive DP is a natural and timely question. The honest answer here is "only partly," which is informative but less exciting than a clear win. Private fine-tuning, where DP is most deployed, is not studied.

Strengths

A crisp conceptual lemma (clipping ≈ rescaling) tailored to scale-invariant updates.

Assumptions weaker than competing analyses: centered variance only, with a floor that vanishes as σ→0.

A general-norm result with a careful comparison table and reconciliation of conventions.

Very transparent about the limits of the theory and the experiments.

A thorough hyperparameter landscape with full heatmaps.

Limitations

The theory does not cover the practical regime, so there is a disconnect between theory and experiments.

The rate matches clipped SGD and shows no advantage from the LMO, so the paper does not explain why Muon helps under DP.

Empirical gains are small and often within noise, with single-run language-modeling results.

Experiments are small-scale, with no fine-tuning or large-model evidence.

Concurrent overlapping work reduces distinctiveness.

Overall

This is a solid, honest theory-plus-empirics paper. It offers a neat technical insight and a useful empirical map. It is unlikely to be field-changing, because the guarantees are vacuous in practical regimes and the empirical advantage is modest and mixed.

Rating:5.5/ 10

Significance 5Rigor 6.5Novelty 6Clarity 7

Generated Oct 20, 2026

Comparison History (0)

No comparisons yet.

Scorecard· 16/16

5.5/10 impact

Elegant rescaling insight and honest, thorough study, but theory does not cover practical regimes, empirical gains are marginal, and concurrent works overlap.