Fundamental Limits of Distributed Covariance Matrix Estimation Under Communication Constraints
Mohammad Reza Rahmani, Mohammad Hossein Yassaee, Mohammad Ali Maddah-Ali, Mohammad Reza Aref
Abstract
Estimating high-dimensional covariance matrices is crucial in various domains. This work considers a scenario where two collaborating agents access disjoint dimensions of $m$ samples from a high--dimensional random vector, and they can only communicate a limited number of bits to a central server, which wants to accurately approximate the covariance matrix. We analyze the fundamental trade--off between communication cost, number of samples, and estimation accuracy. We prove a lower bound on the error achievable by any estimator, highlighting the impact of dimensions, number of samples, and communication budget. Furthermore, we present an algorithm that achieves this lower bound up to a logarithmic factor, demonstrating its near-optimality in practical settings.
BibTeX
@inproceedings{
rahmani2024fundamental,
title={Fundamental Limits of Distributed Covariance Matrix Estimation Under Communication Constraints},
author={Mohammad Reza Rahmani and Mohammad Hossein Yassaee and Mohammad Ali Maddah-Ali and Mohammad Reza Aref},
booktitle={Forty-first International Conference on Machine Learning},
year={2024},
url={https://openreview.net/forum?id=biE1uHyG0l}
}