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 \cite{rahmani2025fundamental} 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 \cite{braverman2016communication} showed that sparsity does \emph{not} reduce communication cost for mean estimation, we prove that sparsity \emph{does} help for cross-covariance estimation in the vertical split. Specifically, for sufficiently large $d_1{d}_2\mathrm{/}{s}^{\mathrm{\prime }}$ and $0<\epsilon <{\sigma }^2\sqrt{s^{\mathrm{\prime }}}\mathrm{/}32$, any scheme achieving expected Frobenius distortion at most $\epsilon$ must satisfy $B_k=\mathrm{\Omega }({\sigma }^4{d}_k{s}^{\mathrm{\prime }}\log (d_1{d}_2\mathrm{/}{s}^{\mathrm{\prime }})\mathrm{/}{\epsilon }^2)$ and $m=\mathrm{\Omega }({\sigma }^4{s}^{\mathrm{\prime }}\log (d_1{d}_2\mathrm{/}{s}^{\mathrm{\prime }})\mathrm{/}{\epsilon }^2)$ for cross-covariance estimation, where $s^{\mathrm{\prime }}=s\wedge d_{\min }$. For the $1$-sparse case, our achievable scheme reduces the $d_1{d}_2$ factor in the dense communication rate to $\log (d_1{d}_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 \cite{rahmani2025fundamental}. We show that the communication lower bound is tight up to polylogarithmic factors under the conditions of Remark~\ref{rem:achievmatch}, using an achievable scheme based on covering-net quantization and entry-wise hard thresholding.