Faster Rates for Compressed Federated Learning with Client-Variance Reduction
Haoyu Zhao, Konstantin Burlachenko, Zhize Li, Peter Richtárik · SIAM Journal on Mathematics of Data Science · 2024
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 [Formula: see text] bound on the number of communication rounds of COFIG in the nonconvex setting, where [Formula: see text] is the total number of clients, [Formula: see text] is the number of clients participating in each round, [Formula: see text] is the convergence error, and [Formula: see text] is the variance parameter associated with the compression operator. In case of FRECON, we prove an [Formula: see text] bound on the number of communication rounds. In the convex setting, COFIG converges within [Formula: see text] communication rounds, which, to the best of our knowledge, 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.