Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressor

DOI10.1093/IMAIAI/IAAB006zbMATH Open1494.94003arXiv2002.08958OpenAlexW3154043723MaRDI QIDQ5095263FDOQ5095263

Authors: Mher Safaryan, Egor Shulgin, Peter Richtárik 

Publication date: 5 August 2022

Published in: Information and Inference: A Journal of the IMA (Search for Journal in Brave)

Abstract: 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 {em uncertainty principle} for randomized compression operators, thus quantifying this limitation mathematically, and {em 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 {em Kashin compression (KC)}. In contrast to all previously proposed compression mechanisms, KC enjoys a {em 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.

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

Recommendations

• Stochastic distributed learning with gradient quantization and double-variance reduction
• scientific article; zbMATH DE number 6866309
• Deterministic compression with uncertain priors
• Communication lower bounds for statistical estimation problems via a distributed data processing inequality
• Deterministic compression with uncertain priors

zbMATH Keywords

uncertainty principlecompressiondimension-free boundsKashin's representation

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Communication theory (94A05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cited In (2)

• Deterministic compression with uncertain priors
• Stochastic distributed learning with gradient quantization and double-variance reduction

This page was built for publication: Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressor

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