On Communication Cost of Distributed Statistical Estimation and Dimensionality
This work addresses communication efficiency in distributed statistical estimation, which is crucial for large-scale machine learning systems, though it is incremental as it builds on prior lower bounds and extends to structured parameters.
The paper tackles the problem of estimating the mean of a Gaussian distribution in a distributed setting, showing that communication cost scales linearly with dimensions and proving lower bounds of Ω(md/log(m)) and Ω(md) bits for interactive and simultaneous settings, respectively, while also proposing a protocol that achieves minimax loss with O(md) bits and saving a d/s factor for sparse parameters.
We explore the connection between dimensionality and communication cost in distributed learning problems. Specifically we study the problem of estimating the mean $\vecθ$ of an unknown $d$ dimensional gaussian distribution in the distributed setting. In this problem, the samples from the unknown distribution are distributed among $m$ different machines. The goal is to estimate the mean $\vecθ$ at the optimal minimax rate while communicating as few bits as possible. We show that in this setting, the communication cost scales linearly in the number of dimensions i.e. one needs to deal with different dimensions individually. Applying this result to previous lower bounds for one dimension in the interactive setting \cite{ZDJW13} and to our improved bounds for the simultaneous setting, we prove new lower bounds of $Ω(md/\log(m))$ and $Ω(md)$ for the bits of communication needed to achieve the minimax squared loss, in the interactive and simultaneous settings respectively. To complement, we also demonstrate an interactive protocol achieving the minimax squared loss with $O(md)$ bits of communication, which improves upon the simple simultaneous protocol by a logarithmic factor. Given the strong lower bounds in the general setting, we initiate the study of the distributed parameter estimation problems with structured parameters. Specifically, when the parameter is promised to be $s$-sparse, we show a simple thresholding based protocol that achieves the same squared loss while saving a $d/s$ factor of communication. We conjecture that the tradeoff between communication and squared loss demonstrated by this protocol is essentially optimal up to logarithmic factor.