Distributed Mean Estimation with Limited Communication

By Ananda Theertha Suresh, Felix X. Yu, Sanjiv Kumar, H. Brendan McMahan. 2016

400 citations recorded by the source corpus.

Motivated by the need for distributed learning and optimization algorithms with low communication cost, we study communication efficient algorithms for distributed mean estimation. Unlike previous works, we make no probabilistic assumptions on the data. We first show that for d dimensional data with n clients, a naive stochastic rounding approach yields a mean squared error (MSE) of Θ (d/n) and uses a constant number of bits per dimension per client. We then extend this naive algorithm in two ways: we show that applying a structured random rotation before quantization reduces the error to O((log d)/n) and a better coding strategy further reduces the error to O(1/n). We also show that the latter coding strategy is optimal up to a constant in the minimax sense i.e., it achieves the best MSE for a given communication cost. We finally demonstrate the practicality of our algorithms by applying them to distributed Lloyd's algorithm for k-means and power iteration for PCA.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

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

In Statistics and Probability

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, methodology): “For gradient compression, some existing works [376] are developed in the minimax sense to characterize the worst case scenario.”
The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation (2021, methodology): “The next step performs a unitary rotation/reflection operation x′′ i = HdDξx ′ i (Suresh et al., 2017).”
Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs (2020, methodology): “Distributed mean estimation and its use in training learning models has been studied extensively in the literature (see [SYKM17, AGL + 17, GKMM19, MT20] and references therein).”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, background): “Moreover, summation is perhaps the most primitive functionality in database systems in general, and in private implementations in particular (see, e.g., (Kotsogiannis et al., 2019; Wilson et al., 2019; Suresh et al., 2017)).”
Secure Federated Submodel Learning (2019, background): “γ-level quantization [29], which maps each parameter into {0, 1, .”
SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, background): “That includes the design of more eﬃcient communication strategies (Konečn`y et al., 2016b,a; Suresh et al., 2017; Stich et al., 2018; Karimireddy et al., 2019; Basu et al., 2019), the study of lower bounds for parallel stochastic optimization with a dependency graph (Woodworth et al., 2018b),…”
GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, background): “…bandwidth/power usage per channel use, decreasing communication payload sizes is one popular solution, which is enabled by gradient quantization (Suresh et al., 2017), model parameter quantization (Zhu et al., 2016; Sriranga et al., 2019), and model output exchange for large-sized models via…”
Qsparse-Local-SGD: Distributed SGD With Quantization, Sparsification, and Local Computations (2019, methodology): “Theoretically justified gradient compression using unbiased stochastic quantizers has been proposed and analyzed in [6], [8], [13], [15].”
Natural Compression for Distributed Deep Learning (2019, background): “Another possibility is to apply randomized sparsification masks to the gradients [45, 28, 4, 44], or to rely on coordinate/block descent updates-rules, which are sparse by design [37, 11, 32].”
DoubleSqueeze: Parallel Stochastic Gradient Descent with Double-Pass Error-Compensated Compression (2019, background): “inimum. The convergence rate guarantee of 1Bit-SGD is studied recently in Bernstein et al. (2018a,b). Some specic methods for implementing the compression for distributed systems is also studied. In Suresh et al. (2017), authors proposed some communication ecient strategies distributed mean estimati”
Agnostic Federated Learning (2019, background): “…efﬁcient communication strategies (Koneˇcn`y, McMahan, Yu, Richt´arik, Suresh, and Bacon, 2016b; Koneˇcn`y, McMahan, Ramage, and Richt´arik, 2016a; Suresh, Yu, Kumar, and McMahan, 2017), devising efﬁcient distributed optimization methods beneﬁting from differential privacy guarantees (Agarwal,…”
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, methodology): “We first propose a direct application of quantization [33] and Binomial mechanism and characterize its privacy/error guarantees along with its communication costs.”
Byzantine Stochastic Gradient Descent (2018, background): “There is an extremely rich literature studying the scalability and communication requirements of distributed SGD, e.g. [1, 9, 23, 24, 31, 32, 35, 40], in settings where all the workers are correct.”
D2: Decentralized Training over Decentralized Data (2018, methodology): “Decentralized algorithms Centralized algorithms requires a central server to communicate with all other workers [Suresh et al., 2017].”
Randomized Distributed Mean Estimation: Accuracy vs. Communication (2016, methodology): “Note that this bound improves upon the performance of the method of [10] in two aspects.”