Correlation Aware Sparsified Mean Estimation Using Random Projection

We study the problem of communication-efficient distributed vector mean estimation, which is a commonly used subroutine in distributed optimization and Federated Learning (FL). Rand- k sparsification is a commonly used technique to reduce communication cost, where each client sends k d of its coordinates to the server. However, Rand- k is agnostic to any correlations, that might exist between clients in practical scenarios. The recently proposed Rand- k -Spatial estimator leverages the cross-client correlation information at the server to improve Rand- k's performance. Yet, the performance of Rand- k -Spatial is suboptimal, and improving mean estimation is key to a faster convergence in distributed optimization. We propose the Rand-Proj-Spatial estimator with a more flexible encoding-decoding procedure, which generalizes the encoding of Rand- k by projecting the client vectors to a random k -dimensional subspace.