Communication-Efficient Agnostic Federated Learning via Faster Convergence and Compression

arXiv:2609.36610v1 Announce Type: new Abstract: 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((log m)^{1/4}T^{-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((elta^{-1}+(log m)^{1/4})T^{-1/8}) stationarity rate for AFL-Com under general elta-approximate compressors and improve the elta-dependence from elta^{-1} to elta^{-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 (log m)^{1/4} with Top-k and (log m)^{1/2} with Rand-k and SR. Experiments validate the improved synchronization and communication efficiency of our methods.

Related

• Subspace Optimization for Efficient Federated Learning under Heterogeneous Data
• MUC-FL: Block-Wise Marginal Utility Contribution for Communication-Efficient Federated Learning
• Convergence Analysis of Sequential Federated Learning on Heterogeneous Data
• Leveraging Kernel Symmetry for Joint Compression and Error Mitigation in Edge Model Transfer
• Theoretical Foundations of Communication-Efficient, Robust, and Practical Distributed and Federated Optimization

Source: arXiv cs.LG | 2026-09-30