Timezone: »

 
Poster
EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimization
Laurent Condat · Kai Yi · Peter Richtarik

Tue Nov 29 02:00 PM -- 04:00 PM (PST) @ Hall J #622
in Poster Session 2 »

In distributed or federated optimization and learning, communication between the different computing units is often the bottleneck and gradient compression is widely used to reduce the number of bits sent within each communication round of iterative methods. There are two classes of compression operators and separate algorithms making use of them. In the case of unbiased random compressors with bounded variance (e.g., rand-k), the DIANA algorithm of Mishchenko et al. (2019), which implements a variance reduction technique for handling the variance introduced by compression, is the current state of the art. In the case of biased and contractive compressors (e.g., top-k), the EF21 algorithm of Richtárik et al. (2021), which instead implements an error-feedback mechanism, is the current state of the art. These two classes of compression schemes and algorithms are distinct, with different analyses and proof techniques. In this paper, we unify them into a single framework and propose a new algorithm, recovering DIANA and EF21 as particular cases. Our general approach works with a new, larger class of compressors, which has two parameters, the bias and the variance, and includes unbiased and biased compressors as particular cases. This allows us to inherit the best of the two worlds: like EF21 and unlike DIANA, biased compressors, like top-k, whose good performance in practice is recognized, can be used. And like DIANA and unlike EF21, independent randomness at the compressors allows to mitigate the effects of compression, with the convergence rate improving when the number of parallel workers is large. This is the first time that an algorithm with all these features is proposed. We prove its linear convergence under certain conditions. Our approach takes a step towards better understanding of two so-far distinct worlds of communication-efficient distributed learning.

Keywords: federated learning · Distributed Optimization · compression · variance reduction · Communication · randomized algorithm · error feedback
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Laurent Condat (KAUST)
Kai Yi (KAUST)

I’m a PhD student under the supervision of Prof. Peter Richtárik. Before that, I received my Master from KAUST in Dec. 2021 and B.Eng with honor from Xi’an Jiaotong University in June 2019. I’ve interned at Tencent AI Lab, CMU Xulab, NUS CVML Group, and SenseTime.

Peter Richtarik (KAUST)

More from the Same Authors