cs.LGNov 9, 2026

Byzantine-Robust Muon: Resilient Momentum Orthogonalization for Distributed Learning

Authors: Grigory Malinovsky, Yury Demidovich, Peter Richtárik

Organizations: King Abdullah University of Science and Technology (KAUST), Saudi Arabia

Abstract

Optimization methods, including the Muon optimizer based on the Linear Minimization Oracle (LMO) and momentum orthogonalization, have shown strong empirical performance in large-scale and distributed learning, yet their robustness to adversarial behavior and data heterogeneity is not well understood. We study these methods within a unified first-order trust-region framework and analyze Muon-based updates with robust aggregation for Byzantine-robust distributed and federated learning. Our analysis does not rely on the i.i.d. assumption and introduces a non-Euclidean notion of heterogeneity consistent with the trust-region geometry. Under this framework, we establish convergence guarantees for both general non-convex and star-convex objectives. Our results provide a theoretical characterization of Byzantine-robust Muon-based optimization, with an additive heterogeneity error floor consistent with known impossibility results, under explicit aggregation assumptions. Under an explicit additive oracle-error condition, the guarantees also cover inexact orthogonalization, with the non-convex Byzantine terms in the bound's numerator unchanged but a smaller progress denominator. In simulated federated training with ResNet-18 and ViT-Tiny on CIFAR-10, additional image benchmarks, and a 38M-parameter byte-level language model on TinyStories, the tested Muon configuration attains higher attacked accuracy (lower perplexity) than the tested SGD and normalized-SGD configurations, and than sign updates on CIFAR-10. Fixed-honest controls further show a substantial RFA advantage over averaging under a bounded RFA-query attack, higher attacked accuracy for Muon-NS than tensorwise Euclidean normalization from shared checkpoints, and lower held-out TinyStories perplexity than a tuned AdamW baseline.

Figures & tables

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Byzantine-Robust Optimization under (L0,L1)(L_0, L_1)-Smoothness

    Mar 12, 2026Arman Bolatov, Samuel Horváth, Martin Takáč +1Distributed OptimizationByzantine-Robust Federated Learning

  2. Byzantine-Robust Distributed SGD: A Unified Analysis and Tight Error Bounds

    Apr 11, 2026Boyuan Ruan, Xiaoyu Wang, Ya-Feng LiuDistributed OptimizationFault-Tolerant Distributed Training

  3. Byzantine-Robust and Differentially Private Federated Optimization under Weaker Assumptions

    Mar 24, 2026Rustem Islamov, Grigory Malinovsky, Alexander Gaponov +3Byzantine-Robust Federated LearningDifferentially Private Federated Learning