Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor

By Mher Safaryan, Egor Shulgin, Peter Richtárik. 2020

71 citations recorded by the source corpus.

In order to mitigate the high communication cost in distributed and federated learning, various vector compression schemes, such as quantization, sparsification and dithering, have become very popular. In designing a compression method, one aims to communicate as few bits as possible, which minimizes the cost per communication round, while at the same time attempting to impart as little distortion (variance) to the communicated messages as possible, which minimizes the adverse effect of the compression on the overall number of communication rounds. However, intuitively, these two goals are fundamentally in conflict: the more compression we allow, the more distorted the messages become. We formalize this intuition and prove an uncertainty principle for randomized compression operators, thus quantifying this limitation mathematically, and effectively providing asymptotically tight lower bounds on what might be achievable with communication compression. Motivated by these developments, we call for the search for the optimal compression operator. In an attempt to take a first step in this direction, we consider an unbiased compression method inspired by the Kashin representation of vectors, which we call Kashin compression (KC). In contrast to all previously proposed compression mechanisms, KC enjoys a dimension independent variance bound for which we derive an explicit formula even in the regime when only a few bits need to be communicate per each vector entry.

Subfields: Artificial Intelligence, Computational Mechanics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

Citations in the corpus

Breaking the Communication-Privacy-Accuracy Trilemma (2020, background): “While various compression schemes, based on quantization, sparsification, and dithering have been proposed in the recent literature and Kashin’s representation for communication efficiency [27], [28], [29], [30] or for LDP [31] has also been explored in a few works, it is particularly powerful in th”
Stochastic Controlled Averaging for Federated Learning with Communication Compression (2023, methodology): “…practice, we can simply set Furthermore, it is known that one can convert any ω -unbiased compressor C i into a q 2 -contractive compressors with q 2 = ω 1+ ω through scaling 1 1+ ω C i : x (cid:55)→ 1 1+ ω C i ( x ) (see, e.g. , (Safaryan et al., 2022, Lemma 1) and (Huang et al., 2022, Lemma 1)).”