Faster Rates for Compressed Federated Learning with Client-Variance Reduction

DOI10.1137/23M1553820arXiv2112.13097MaRDI QIDQ6202285FDOQ6202285

Haoyu Zhao, Author name not available (Why is that?), Zhize Li, Peter Richtárik

Publication date: 26 March 2024

Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Abstract: Due to the communication bottleneck in distributed and federated learning applications, algorithms using communication compression have attracted significant attention and are widely used in practice. Moreover, the huge number, high heterogeneity and limited availability of clients result in high client-variance. This paper addresses these two issues together by proposing compressed and client-variance reduced methods COFIG and FRECON. We prove an $O(frac(1+omega{)}^{3/2}sqrtNSepsilo{n}^2+frac(1+omega)N^{2/3}Sepsilo{n}^2)$ bound on the number of communication rounds of COFIG in the nonconvex setting, where $N$ is the total number of clients, $S$ is the number of clients participating in each round, $epsilon$ is the convergence error, and $omega$ is the variance parameter associated with the compression operator. In case of FRECON, we prove an $O(frac(1+omega)sqrtNSepsilo{n}^2)$ bound on the number of communication rounds. In the convex setting, COFIG converges within $O(frac(1+omega)sqrtNSepsilon)$ communication rounds, which is also the first convergence result for compression schemes that do not communicate with all the clients in each round. We stress that neither COFIG nor FRECON needs to communicate with all the clients, and they enjoy the first or faster convergence results for convex and nonconvex federated learning in the regimes considered. Experimental results point to an empirical superiority of COFIG and FRECON over existing baselines.

Full work available at URL: https://arxiv.org/abs/2112.13097

zbMATH Keywords

variance reductiondistributed optimizationfederated learningcommunication compression

Mathematics Subject Classification ID

Computational aspects of data analysis and big data (68T09) Analysis of algorithms and problem complexity (68Q25) Communication complexity, information complexity (68Q11)

Cites Work

• Advances and Open Problems in Federated Learning
• Title not available (Why is that?)

This page was built for publication: Faster Rates for Compressed Federated Learning with Client-Variance Reduction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202285)