Publication Type
Conference Proceeding Article
Version
publishedVersion
Publication Date
12-2025
Abstract
Due to the communication bottleneck in distributed and decentralized federated learning applications, algorithms using compressed communication have attracted significant attention. The Error Feedback (EF) is a widely-studied compression framework for convergence with biased compressors such as top-k sparsification. Although various improvements have been obtained in recent years, the theoretical guarantee for EF-type framework is still limited. Previous works either 1) rely on strong assumptions such as bounded gradient/dissimilarity assumptions, thus can not deal with arbitrary data heterogeneity and also slow the convergence speed, or 2) can not enjoy linear speedup in the number of clients. In this work, we propose a new EFSkip framework which removes the strong assumptions to allow arbitrary data heterogeneity and enjoys linear speedup for significantly improving upon previous results. In particular, EFSkip achieves a substantially lower computational complexity compared to the previous EF21, i.e., EFSkip enjoys the linear speedup in the number of clients (reducing the result linearly using more clients). We also show that EFSkip enjoys linear speedup and achieves faster convergence for nonconvex problems satisfying Polyak-Lojasiewicz (PL) condition. We believe that the new EFSkip framework will have a large impact on the communication- and computation-efficient distributed and decentralized federated learning.
Discipline
Artificial Intelligence and Robotics
Research Areas
Data Science and Engineering; Intelligent Systems and Optimization
Areas of Excellence
Digital transformation
Publication
Proceedings of the 39th Conference on Neural Information Processing Systems (NeurIPS 2025), San Diego, CA, December 2-7
First Page
15489
Last Page
15497
Identifier
10.1609/aaai.v39i15.33700
Publisher
AAAI
City or Country
Philadelphia, Pennsylvania, USA
Citation
BAO, Hongyan; CHEN, Pengwen; SUN, Ying; and LI, Zhize.
EFSkip: A new error feedback with linear speedup for compressed federated learning with arbitrary data heterogeneity. (2025). Proceedings of the 39th Conference on Neural Information Processing Systems (NeurIPS 2025), San Diego, CA, December 2-7. 15489-15497.
Available at: https://ink.library.smu.edu.sg/sis_research/10843
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1609/aaai.v39i15.33700