Randomized Distributed Mean Estimation: Accuracy vs. Communication

Frontiers in Applied Mathematics and Statistics

, Jakub¹  Konečný¹ 

[1] School of Mathematics, The University of Edinburgh, Edinburgh, United Kingdom

关键词: Communication efficiency;    Distributed mean estimation;    Accuracy-communication tradeoff;    Gradient compression;    quantization;   

DOI  :  10.3389/fams.2018.00062

学科分类：数学（综合）

来源: Frontiers

【 摘 要 】

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.

【 授权许可】

CC BY