Information-Theoretic Bounds for Sparse Covariance Estimation in the Vertical-Split Distributed Model
Abstract
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 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<ε<σ2√(s')/32, any scheme achieving expected Frobenius distortion at most ε must satisfy Bk = Ω(σ4 dk s' log(d1 d2/s')/ε2) and m = Ω(σ4 s' log(d1 d2/s')/ε2) for cross-covariance estimation, where s' = s ∧ 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 \cite{rahmani2025fundamental}. 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.
Related
- Measuring Learned Equivariance: An Information Theoretic Approach
- A Sample-Based Approach for Hierarchical Information-Theoretic Compression of Probabilistic Occupancy Grids
- Conditional Fisher-Information Central Limit Theorems under Log-Concavity with Information-Theoretic Consequences
- Robust Covariance Estimation for Entry-wise Contaminated and Partially Observed Data via Expectation Maximization Algorithm
- Online Covariance Estimation for Averaged Stochastic Gradient Descent on Riemannian Manifolds
BibTeX
@misc{tan2026informationtheoretic,
title = {{Information-Theoretic Bounds for Sparse Covariance Estimation in the Vertical-Split Distributed Model}},
author = {Jing Yee Tan and Guangyue Han},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.07124},
eprint = {2606.07124},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.07124},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Information-Theoretic Bounds for Sparse Covariance Estimation in the Vertical-Split Distributed Model
AU - Jing Yee Tan
AU - Guangyue Han
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2606.07124
UR - https://arxiv.org/abs/2606.07124
AB - 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. 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 d_1d_2/s' and 0<ε<σ^2√(s')/32, any scheme achieving expected Frobenius distortion at most ε must satisfy B_k = Ω(σ^4 d_k s' log(d_1 d_2/s')/ε^2) and m = Ω(σ^4 s' log(d_1 d_2/s')/ε^2) for cross-covariance estimation, where s' = s ∧ d_min. For the $1$-sparse case, our achievable scheme reduces the d_1d_2 factor in the dense communication rate to log(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 \cite{rahmani2025fundamental}. 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.
ER -