# Information-Theoretic Bounds for Sparse Covariance Estimation in the Vertical-Split Distributed Model

arXiv: https://arxiv.org/abs/2606.07124 · HTML: https://mlsanity.com/paper/2606.07124/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 33 references that are in the map.
- First posted on arXiv 5 Jun 2026.

## Builds on (most cited first, 13 of 13)

- [Distributed Mean Estimation with Limited Communication](https://mlsanity.com/paper/1611.00429/) (2016)
- [Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality](https://mlsanity.com/paper/1506.07216/) (2015)
- [Geometric Lower Bounds for Distributed Parameter Estimation under Communication Constraints](https://mlsanity.com/paper/1802.08417/) (2018)
- [Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction](https://mlsanity.com/paper/1812.11476/) (2018)
- [On Communication Cost of Distributed Statistical Estimation and Dimensionality](https://mlsanity.com/paper/1405.1665/) (2014)
- [Inference under Information Constraints II: Communication Constraints and Shared Randomness](https://mlsanity.com/paper/1905.08302/) (2019)
- [Unified lower bounds for interactive high-dimensional estimation under information constraints](https://mlsanity.com/paper/2010.06562/) (2020)
- [Distributed Gaussian Mean Estimation under Communication Constraints: Optimal Rates and Communication-Efficient Algorithms](https://mlsanity.com/paper/2001.08877/) (2020)
- [Improved Distributed Principal Component Analysis](https://mlsanity.com/paper/1408.5823/) (2014)
- [The Minimax Learning Rates of Normal and Ising Undirected Graphical Models](https://mlsanity.com/paper/1806.06887/) (2018)
- [Principal Component Analysis and Higher Correlations for Distributed Data](https://mlsanity.com/paper/1304.3162/) (2013)
- [Distributed Estimation of Gaussian Correlations](https://mlsanity.com/paper/1805.12472/) (2018)
- [Estimation of large block structured covariance matrices: Application to "multi-omic" approaches to study seed quality](https://mlsanity.com/paper/1806.10093/) (2018)

## Abstract (arXiv)

We study the minimax estimation error for distributed covariance matrix estimation in the vertical-split (feature-split) setting, where two agents each observe different coordinates of~m i.i.d. sub-Gaussian samples and communicate a limited number of bits to a central server. While citerahmani2025fundamental established nearly tight bounds for dense (unstructured) cross-covariance matrices, we investigate whether imposing elementwise s-sparsity on the cross-covariance C21 can reduce the required communication and sample complexity. We show that sparsity can reduce the communication required for cross-covariance estimation in the vertical split at a fixed target distortion. Specifically, for sufficiently large d1d2/s' and 0<varepsilon<σ2√s'/32, any scheme achieving expected Frobenius distortion at most varepsilon must satisfy Bk = Omega(σ4 dk, s' log(d1 d2/s')/varepsilon2) and m = Omega(σ4, s' log(d1 d2/s')/varepsilon2) for cross-covariance estimation, where s' = s wedge dmin. For the 1-sparse case, our achievable scheme reduces the d1d2 factor in the dense communication rate to log(d1d2), up to polylogarithmic factors, for the cross-covariance communication component in the matching regime. Our lower bounds are established via Fano's method with an explicit sparse packing using a Varshamov--Gilbert-type argument for signed partial permutation matrices combined with the Conditional Strong Data Processing Inequality of citerahmani2025fundamental. We show that the communication lower bound is tight up to polylogarithmic factors under the conditions of Remark 4.9, using an achievable scheme based on covering-net quantization and entry-wise hard thresholding.