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

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.