Organizations: State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing, China · School of Artificial Intelligence, Nanjing University, Nanjing, China · Department of Computer Science, City University of Hong Kong, Hong Kong, China
Agnostic federated learning (AFL) seeks a model that performs reliably across m heterogeneous workers, but communication remains a bottleneck. We improve communication efficiency by reducing the number of synchronization rounds via faster convergence and the communication cost per round via compression. We first propose AFL-BR, which updates the dual weights over workers using online mirror ascent with KL divergence and blockwise restarts. It achieves an O((logm)1/4T−1/8) stationarity rate after T update rounds, reducing the m-dependence of the synchronization rounds required for convergence from polynomial to logarithmic order. Building on AFL-BR, we develop AFL-Com by applying bidirectional compression with error feedback (EF). Instead of compressing local gradients, workers apply EF to their dual-weighted gradients, enabling direct control of the aggregated compression error under time-varying weights. We then establish an O((δ−1+(logm)1/4)T−1/8) stationarity rate for AFL-Com under general δ-approximate compressors and improve the δ-dependence from δ−1 to δ−1/2 for additive-and-idempotent compressors with shared randomness (SR). With suitable compression levels, AFL-Com retains the same convergence rate as AFL-BR at a lower per-round communication cost, yielding reductions in total communication complexity by factors of (logm)1/4 with Top-k and (logm)1/2 with Rand-k and SR. Experiments validate the improved synchronization and communication efficiency of our methods.
Figures & tables
Algorithm
Technique
Synchronization rounds for ε -stationarity
Communication cost per round
Communication complexity
SGDA ⋆
–
O(m7/2ε−8)
O(dm)
O(dm9/2ε−8)
DRFA ♣
Local updates
O(ε−12+m2ε−8)
O(dm)
O(dmε−12+dm3ε−8)
Fully synchronized
O(m2ε−8)
O(dm)
O(dm3ε−8)
AFL-BR (Algorithm 1 )
–
O((logm)2ε−8)
O(dm)
O(dm(logm)2ε−8)
AFL-Com (Algorithm 2 )
Compression (Top- k ) §
O((logm)2ε−8)
O(dm(logm)−1/4)
O(dm(logm)7/4ε−8)
Compression (Rand- k with SR) ∗
O((logm)2ε−8)
O(dm(logm)−1/2)
O(dm(logm)3/2ε−8)
Table 1: Comparison of nonconvex AFL methods using Top- k and Rand- k as examples. d is the model dimension and m the number of workers. Definitions of compressors are provided in Appendix B.1 . ⋆,♣ Hidden m -dependence is made explicit; see Appendices C.1 and C.2 . \lx@sectionsign Set k=Θ(d(logm)−1/4) in Theorem 2 . ∗ Set k=Θ(d(logm)−1/2) with SR in Theorem 3 . Parfenov et al. (2026) is omitted since it relies on a Minty-inspired condition with a different criterion.
Figure 1: Synchronization rounds versus m on FEMNIST.
Figure 2: Worst-worker test accuracy. The top and bottom rows correspond to Fashion-MNIST and CIFAR-10, respectively. From left to right, the columns report performance against update rounds, synchronization rounds, and cumulative communication cost.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 3: Maximum worker test loss. The top and bottom rows correspond to Fashion-MNIST and CIFAR-10, respectively. From left to right, the columns report performance against update rounds, synchronization rounds, and cumulative communication cost.
Federated Learning (FL) enables collaborative model training across distributed clients without sharing raw data, thereby preserving privacy. However, FL often suffers from significant communication and computational overhead, limiting its scalability and sustainability. In this work, we introduce a Full Compression Pipeline (FCP) for FL in communication-constrained environments. FCP integrates three complementary deep compression techniques (pruning, quantization, and Huffman encoding) into a unified end-to-end framework. By compressing local models and communication payloads, FCP substantially reduces transmission costs and resource consumption while maintaining competitive accuracy. To quantify its impact, we develop an evaluation framework that captures both communication and computation overheads as a unified model cost, allowing a holistic assessment of efficiency trade-offs. The pipeline is evaluated in an independent and identically distributed (IID) and non-IID data setting. In one representative scenario, training a ResNet-12 model on the CIFAR-10 dataset with ten clients and a 2 Mbps bandwidth, the FCP achieves more than 11× reduction in model size, with only a 2% drop in accuracy compared to the uncompressed baseline. This results in an FL training that is more than 60% faster.
Elouan Colybes, Shirin Salehi, Anke Schmeink
Chair of Information Theory and Data Analytics (INDA), RWTH Aachen University, Aachen, Germany
Recent developments have shown that Muon-type optimizers based on linear minimization oracles (LMOs) over non-Euclidean norm balls have the potential to get superior practical performance than Adam-type methods in the training of large language models. Since large-scale neural networks are trained across massive machines, communication cost becomes the bottleneck. To address this bottleneck, we investigate Gluon, which is an extension of Muon under the more general layer-wise (L0,L1)-smooth setting, with both unbiased and contraction compressors. In order to reduce the compression error, we employ the variance reduced technique in SARAH in our compressed methods. The convergence rates and improved communication cost are achieved under certain conditions. As a byproduct, a new variance reduced algorithm with faster convergence rate than Gluon is obtained. We also incorporate momentum variance reduction (MVR) to these compressed algorithms and comparable communication cost is derived under weaker conditions when Li1=0. Finally, several numerical experiments are conducted to verify the superior performance of our compressed algorithms in terms of communication cost.
Xun Qian, Alexander Gaponov, Grigory Malinovsky +1
Center of Excellence for Generative AI, King Abdullah University of Science and Technology, Thuwal, Saudi Arabia.
Asynchronous decentralized federated learning (ADFL) eliminates central coordination and global synchronization, making it attractive for large-scale and heterogeneous systems. However, frequent peer-to-peer communication, asynchronous updates on directed topologies, and non-IID data jointly lead to excessive communication overhead, biased aggregation and severe model drift. We propose PushCen-ADFL, a communication-efficient ADFL framework that enables stable training under asymmetric communication and delayed client participation. PushCen-ADFL couples communication, aggregation, and local stabilization in a shared centroid representation space, forming a closed loop between compression and optimization. Clients exchange centroid-form messages, apply average-preserving push-sum mixing to correct aggregation bias, and use a lightweight centroid regularization anchored in the same centroid space to mitigate drift under heterogeneity and staleness. A bounded, sender-deduplicated buffer further improves robustness under irregular asynchronous arrivals. Experiments on vision datasets demonstrate that PushCen-ADFL improves accuracy under data heterogeneity by up to 6% while reducing per-push communication cost by more than 80%, achieving a favorable accuracy-communication trade-off.
Jiahui Bai, Hai Dong, A. K. Qin
School of Computer Technologies, RMIT University Melbourne, VIC, Australia · School of Science, Computing and Engineering Technologies, Swinburne University of Technology Hawthorn, VIC, Australia