CS Paper Radar

Federated Compositional Muon Optimizer for Matrix-Wise Models

Wang Yan, Feihu Huang

cs.LG math.OC ·submitted 2026-08-13 01:46 UTC · v2
theory

Abstract

Muon, a more recently developed optimizer, is useful for matrix-wise models in AI areas. Although many works have studied Muon and its variants, these methods are still not particularly well-suited for hierarchical structured problems. To fill this gap, we propose an effective federated compositional Muon (FedCoMuon) optimizer to solve distributed matrix-wise compositional optimization problems. Specifically, our FedCoMuon optimizer builds on compositional gradient tracking and orthogonalized momentum. Moreover, we propose a variance reduced variant of FedCoMuon (FedCoMuon-VR) based on a momentum-based variance reduced technique. In theory, we analyze the convergence properties of our algorithms under the non-i.i.d. and non-convex settings. In particular, we prove that our FedCoMuon-VR obtains a lower sample complexity of $O(ε^{-3})$ for finding an $ε$-stationary solution than the existing FedMuon algorithms. Extensive numerical experiments on robust federated learning and task-distributed risk-sensitive meta learning show that our proposed methods are competitive with existing compositional baselines and achieve the best reported accuracy in several settings.

Comment
45 pages

Closest papers

Nearest neighbours by meaning across the whole index.

DisMUSE: An Efficient Distributed Singular-Spectrum-Based Optimization Approach with Theoretical Convergence Guarantee

cs.LG math.OC ·2026-11-06 ·Zhen Qin, Zhiyao Zhang, Yingbin Liang, Jia Liu
similarity 0.69
Abstract

In recent years, singular-spectrum-based optimizers have attracted increasing attention due to their ability to preserve the matrix structure of neural network gradients, thereby enabling geometry-aware optimization. However, most singular-spectrum-based (SSB) approaches remain centralized, limiting their use in distributed learning infrastructures that exploit massive parallelism. Distributed SSB optimization is still at an early stage, with open questions about convergence guarantees and communication efficiency. To fill this gap, we propose the Distributed Momentum-based Spectral Estimator (DisMUSE), an efficient distributed SSB optimization framework for both data-center and federated settings. Using Muon-style exact orthogonalized momentum as the spectral update, DisMUSE integrates a recursive variance-reduced momentum estimator and achieves an $O((KT)^{-1/3})$ convergence rate, where $K$ and $T$ denote the number of nodes and local iterations per node, respectively. This rate matches the best-known rates for variance-reduced nonconvex distributed optimization. Building on this variance-reduced framework, we study two extensions. First, our DisMUSE method with finite Newton-Schulz (NS) iterations preserves the same convergence order under a uniform normalized support-spectrum condition, up to a multiplicative factor. Second, we develop a communication-efficient variant based on low-rank (LR) momentum transmission and quantify the error it introduces to the stationarity bound, characterizing the trade-off between accuracy and communication cost.

0.16

A Momentum-Based Variance-Reduced Algorithm for Federated Multiobjective Optimization

cs.LG math.OC ·2026-08-24 ·Yong Zhao, Chunlin You, Minh N. Dao, Zai-Yun Peng
similarity 0.67
Abstract

Federated learning has traditionally been formulated as a single-objective optimization problem, primarily focused on maximizing model utility. In real-world applications, however, machine learning models often need to optimize multiple and potentially conflicting objectives simultaneously. This motivates federated multiobjective optimization (FMOO), which provides a natural framework for jointly handling multiple task-specific objectives in federated learning. In this paper, we propose a momentum-based variance-reduced algorithm for federated multiobjective optimization. The method incorporates a momentum-driven gradient estimator into the local updates to reduce the variance of stochastic updates, leading to an improved convergence rate. We establish theoretical guarantees showing that the expected Pareto stationarity measure of a randomly selected output iterate decays at a rate of $\mathcal{O}(T^{-2/3})$, improving upon the $\mathcal{O}(T^{-1/2})$ rates established for existing methods such as FSMGDA and FedCMOO. Numerical experiments on federated multiobjective optimization benchmarks demonstrate the effectiveness and competitive performance of the proposed algorithm.

0.19

High-Probability Convergence of SGD via Batched Updates

cs.LG math.OCeess.SY ·2026-09-11 ·Feng Zhu, Robert W. Heath, Aritra Mitra
published similarity 0.66
Abstract · To appear at the 65th IEEE Conference on Decision and Control

Stochastic gradient descent (SGD) is the primary workhorse for large-scale optimization. While the average behavior of its iterates, typically characterized by mean-squared error bounds, is well-understood, obtaining high-probability guarantees for the last iterate remains challenging. Prior approaches to this problem have either imposed restrictive assumptions (such as bounded domains or gradients) or relied on complex proofs involving auxiliary sequences. In this work, we propose Batched SGD, a simple variant that partitions online samples into epochs and performs a single update per epoch using a refined, low-variance gradient estimate. Our main contribution demonstrates that this batching mechanism enables a surprisingly simple high-probability analysis that avoids both restrictive assumptions and auxiliary sequences. Under standard smoothness and norm-sub-Gaussian noise assumptions, we establish near-optimal rates for both strongly convex and non-convex objectives. Furthermore, we show that our batching idea extends naturally to federated learning (FL). We provide the first high-probability guarantees for FL, achieving logarithmic communication complexity, linear speedup in the number of agents, and resilience to data heterogeneity.

0.31

Byzantine-Robust Muon: Resilient Momentum Orthogonalization for Distributed Learning

cs.LG ·2026-11-09 ·Grigory Malinovsky, Yury Demidovich, Peter Richtárik
similarity 0.66
Abstract · 51 pages

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.

0.16

FedSubMuon: Communication-Efficient Federated LLM Fine-Tuning via Structured Subspace Muon

cs.LG cs.AI ·2026-09-05 ·Shaolong Chen, Youming Tao, Shuzhen Chen, Falko Dressler, Qingqing Ye +1 more
top venue similarity 0.64
Abstract · 15 pages, 4 figures, 2 algorithms

Federated fine-tuning adapts large language models (LLMs) to decentralized client data, but its scalability in cross-device training is often limited by the high communication cost. Muon is an optimizer that improves optimization performance by orthogonalizing momentum for matrix-valued parameters. Existing federated Muon methods demonstrate the benefit of matrix-aware optimization in federated learning, but still require transmitting full layer-size updates and optimizer state. A natural way to reduce communication is to directly apply Muon to LoRA factors, but this changes the optimized object and weakens Muon's matrix-aware update geometry. We propose FedSubMuon, a communication-efficient federated Muon fine-tuning method that optimizes compact coefficient matrices within shared structured subspaces. This design keeps Muon on a single matrix-valued trainable object, while reducing the client upload to compact coefficient matrices. We further introduce FedSubMuon-GT, an accuracy-oriented extension that uses projected gradients to adapt tracked subspace bases toward task-relevant gradient directions. Experiments on instruction tuning and mathematical reasoning show that FedSubMuon-GT achieves the best overall accuracy on four of five dataset-model pairs, while FedSubMuon performs best under all matched communication budgets. On Dolly-15K, the closest communication baseline requires 5.5 times and 1.4 times more total communication on Llama-1B and Qwen-4B, respectively.

0.66

Distributed Zeroth-Order Composite Finite-Sum Optimization via Incremental Variance Reduction

eess.SY math.OC ·2026-10-30 ·Silan Zhang, Yujie Tang
similarity 0.63
Abstract

We study decentralized composite finite-sum optimization over a fixed connected undirected network, where agents access local component functions through function evaluations and share a possibly nonsmooth convex regularizer. In this setting, standard two-point gradient estimators can retain nonvanishing variance at a solution, complicating their integration with gradient tracking. We propose Distributed Zeroth-Order Incremental Variance Reduction (Distributed ZIVR), which combines incrementally updated component-gradient estimates with a proximal gradient-tracking scheme. The method admits an implementation using a constant number of function evaluations per agent at every iteration, without intermittent full-component or full-coordinate refreshes. For convex smooth component functions and strongly convex local averages, we establish linear convergence up to a controllable finite-difference error. With the finite-difference radius chosen for the target accuracy, Chebyshev-accelerated mixing yields a per-agent oracle complexity of $\widetilde{O}(d(m+κ)\log(1/ε))$ for expected squared solution error $ε$, where $d$ is the dimension, $m$ is the number of components per agent, and $κ$ is the condition number. This matches the centralized ZIVR oracle bound, while the communication bound has only an inverse square-root dependence on the network spectral gap. Experiments on logistic and robust regression demonstrate rapid reduction of solution and consensus errors.

0.13

NBCLT: Parameter-Agnostic Norm-Ball Clipped Local Training

cs.LG ·2026-10-13 ·Linxuan Pan, Shucheng Yang, Junchi Yang
similarity 0.63
Abstract

Distributed learning with multiple local steps reduces communication but aggravates drift, and its practical performance often depends on carefully tuned hyperparameters under heterogeneous data and communication constraints. At the same time, recent Muon-type optimizers suggest that constraining updates within suitable norm balls provides a simple way to encode geometric priors into optimization. In this work, we propose NBCLT (Norm-Ball Clipped Local Training), a unified local-training framework for both federated learning (FL) and decentralized learning (DL). NBCLT combines a predict-and-correct local update rule with Euclidean projections onto flexible norm balls, thereby performing norm-ball clipping under flexible update geometries while retaining a simple implementation. In FL, its problem-parameter-free regime achieves $\mathcal{O}(ε^{-2})$ communication complexity and $\mathcal{O}(ε^{-4})$ total stochastic-gradient complexity without assuming bounded heterogeneity, when the per-round local-computation budget is scaled appropriately with the horizon. In DL, NBCLT is compatible with both static and time-varying mixing and preserves these accuracy exponents under the analogous computation scaling, up to fixed network constants and an additive initialization cost.

0.20

Optimizing Large Language Models with Chained LMOs

cs.LG cs.AI ·2026-10-07 ·Sungyoon Kim, Kaan Ozkara, Youngsuk Park
similarity 0.63
Abstract

Muon has motivated a growing family of optimizers that compose multiple matrix normalizations, but these methods remain fragmented and lack a unified perspective. We introduce chained linear minimization oracles (chained LMOs), which cast these methods as compositions of LMOs. Despite their empirical success, many chains fall outside the standard LMO framework and can diverge on smooth convex objectives. To explain why composition can nevertheless help, we turn to linear associative memory and show that chaining can improve over Muon under anisotropic embeddings. Empirically, we propose TensorChain, a novel optimizer within the framework that stacks compatible weight matrices across different layers and normalizes the 3d tensor across its axes. In Qwen3 0.6B and 1.7B pretraining, TensorChain outperforms all chained baselines in average token efficiency, with average token savings of 9.6% over Muon at matched validation loss.

0.19