Leveraging Spatial and Temporal Correlations in Sparsified Mean Estimation
This addresses communication bottlenecks in federated learning by exploiting data correlations, though it is incremental as it builds on existing sparsification techniques.
The paper tackles the problem of estimating the mean of distributed vectors with high communication costs by leveraging spatial and temporal correlations in the data, modifying the server's decoding method to reduce error. Experiments show it outperforms more complex sparsification methods in tasks like PCA, K-Means, and Logistic Regression.
We study the problem of estimating at a central server the mean of a set of vectors distributed across several nodes (one vector per node). When the vectors are high-dimensional, the communication cost of sending entire vectors may be prohibitive, and it may be imperative for them to use sparsification techniques. While most existing work on sparsified mean estimation is agnostic to the characteristics of the data vectors, in many practical applications such as federated learning, there may be spatial correlations (similarities in the vectors sent by different nodes) or temporal correlations (similarities in the data sent by a single node over different iterations of the algorithm) in the data vectors. We leverage these correlations by simply modifying the decoding method used by the server to estimate the mean. We provide an analysis of the resulting estimation error as well as experiments for PCA, K-Means and Logistic Regression, which show that our estimators consistently outperform more sophisticated and expensive sparsification methods.