Detecting Correlations with Little Memory and Communication
This work addresses information-constrained learning for practical estimation problems, offering foundational insights with broad implications for machine learning and distributed systems.
The paper tackles the problem of detecting correlations in multivariate data under memory or communication constraints, proving a tight trade-off between these constraints and sample complexity, with results showing that optimal sample complexity requires at least quadratic memory/communication bits in dimension.
We study the problem of identifying correlations in multivariate data, under information constraints: Either on the amount of memory that can be used by the algorithm, or the amount of communication when the data is distributed across several machines. We prove a tight trade-off between the memory/communication complexity and the sample complexity, implying (for example) that to detect pairwise correlations with optimal sample complexity, the number of required memory/communication bits is at least quadratic in the dimension. Our results substantially improve those of Shamir [2014], which studied a similar question in a much more restricted setting. To the best of our knowledge, these are the first provable sample/memory/communication trade-offs for a practical estimation problem, using standard distributions, and in the natural regime where the memory/communication budget is larger than the size of a single data point. To derive our theorems, we prove a new information-theoretic result, which may be relevant for studying other information-constrained learning problems.