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 established nearly tight bounds for dense (unstructured) cross-covariance matrices, we investigate whether imposing elementwise s-sparsity on the cross-covariance C 21 can reduce the required communication and sample complexity. In contrast to the horizontal-split setting, where showed that sparsity does not reduce communication cost for mean estimation, we prove that sparsity does help for cross-covariance estimation in the vertical split. Specifically, for sufficiently large d 1d 2/s' and 0< epsilon<σ 2 sqrt s' /32, any scheme achieving expected Frobenius distortion at most epsilon must satisfy B k = Ω(σ 4 d k, s' (d 1 d 2/s')/epsilon 2) and m = Ω(σ 4, s' (d 1 d 2/s')/epsilon 2) for cross-covariance estimation, where s' = s d. For the 1-sparse case, our achievable scheme reduces the d 1d 2 factor in the dense communication rate to (d 1d 2), 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. We show that the communication lower bound is tight up to polylogarithmic factors under the conditions of Remark, using an achievable scheme based on covering-net quantization and entry-wise hard thresholding.