Randomized Distributed Mean Estimation: Accuracy vs. Communication

By Jakub Konecný, Peter Richtárik. 2016

110 citations recorded by the source corpus.

We consider the problem of estimating the arithmetic average of a finite collection of real vectors stored in a distributed fashion across several compute nodes subject to a communication budget constraint. Our analysis does not rely on any statistical assumptions about the source of the vectors. This problem arises as a subproblem in many applications, including reduce-all operations within algorithms for distributed and federated optimization and learning. We propose a flexible family of randomized algorithms exploring the trade-off between expected communication cost and estimation error. Our family contains the full-communication and zero-error method on one extreme, and an epsilon-bit communication and O(1/(epsilon n)) error method on the opposite extreme. In the special case where we communicate, in expectation, a single bit per coordinate of each vector, we improve upon existing results by obtaining O(r/n) error, where r is the number of bits used to represent a floating point value.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistics and Probability, ML Systems & Hardware

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 Theory and Mathematics

In Statistics and Probability

In ML Systems & Hardware

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “Much of the existing literature applies to the objective (a) [245, 376, 244, 20, 204].”
Distributed Fixed Point Methods with Compressed Iterates (2019, methodology): “To overcome this issue, standard techniques proceed by compressing the communicated messages, typically gradients or stochastic gradients [1,5,28,46].”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, background): “Much sparser vectors can be obtained by random sparsiﬁcation techniques that randomly mask the input vectors and only preserve a constant number of coordinates (Wangni et al., 2018; Konecny & Richt´arik, 2018; Stich et al., 2018).”
Expanding the Reach of Federated Learning by Reducing Client Resource Requirements (2018, background): “This is due to the fact that the Hadamard transform, in expectation, spreads a vector’s information more evenly across its components [Suresh et al., 2017, Koneˇcný and Richtárik, 2016].”
cpSGD: Communication-efficient and differentially-private distributed SGD (2018, background): “, see [21] and in particular [5] showed that stochastic quantization and Elias coding [15] can be used to obtain communication-optimal SGD for convex functions.”
Communication Compression for Decentralized Training (2018, background): “, 2017, Konečnỳ and Richtárik, 2016]. Other compression methods can be found in Kashyap et al. [2007], Lavaei and Murray [2012], Nedic et al. [2009]. 3 Preliminary: decentralized parallel stochastic gradient descent (D-PSGD)”
Gradient Sparsification for Communication-Efficient Distributed Optimization (2017, background): “In addition, a similar objective was also formulated in [17] for studying the mean estimation problem on distributed data, with a statistical guarantee under skewness, comparably, we studied a more generalized problem, with a specific algorithm proposed to actually determine the sparsification proba”
ATOMO: Communication-efficient Learning via Atomic Sparsification (2018, methodology): “An equivalent form of this problem was presented in [29] (Section 6.”
Stochastic Distributed Learning with Gradient Quantization and Variance Reduction (2019, background): “Much sparser vectors can be obtained by random sparsification techniques that randomly mask the input vectors and only preserve a constant number of coordinates (Suresh et al., 2017; Konečný & Richtárik, 2016; Wangni et al., 2018; Stich et al., 2018).”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “Xiv preprint 1610.02527 (2016). [83] [88] Chapter 7: Jakub Konecny and Peter Richtarik: \Randomized Distributed Mean Estimation: Accuracy vs Communication." arXiv preprint 1611.07555 (2016). [86] Section 7.8: Jakub Konecny, Brendan McMahan, Felix Yu, Peter Richtarik, Ananda Theertha Suresh and ”
Distributed learning with compressed gradient differences (2019, background): “Other works with SGD update structure include (Konečný and Richtárik, 2016; Bernstein et al., 2018; Khirirat et al., 2018).”
Federated Learning With Quantized Global Model Updates (2020, background): “Several studies address this issue by considering communications with rate limitations, and propose different compression and quantization techniques [2–9], as well as performing local updates to reduce the frequency of communications from the devices to the PS [10, 11].”
A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent (2019, background): “, 2017), sparsification (Konečný and Richtárik, 2018; Alistarh et al., 2018; Wangni et al., 2018) and dithering (Alistarh et al.”
Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor (2020, unknown): “To explore savings in communication, various (mostly randomized) compression operators have been proposed and analyzed such as random sparsiﬁcation (Koneˇcn´y & Richt´arik, 2018; Wangni et al., 2018), top-k sparsiﬁcation (Alistarh et al., 2018), standard random dithering (Goodall, 1951; Roberts,…”
Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization (2020, methodology): “…], f i is L i -smooth and convex, and we denote The innovation introduced in [11] is the following unifying assumption on the stochastic gradients g k used in (2) which allows to simultaneously analyze classical SGD, variance reduced methods, quantized stochastic gradient methods, and some…”