📊 statistics

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

This paper establishes that, unlike in horizontal-split mean estimation, imposing elementwise sparsity on the cross-covariance matrix in a vertical-split distributed setting significantly reduces both communication and sample complexity, with the authors providing tight minimax lower bounds and a matching achievable scheme based on covering-net quantization and hard thresholding.

Original authors: Jing Yee Tan, Guangyue Han

Published 2026-06-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jing Yee Tan, Guangyue Han

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a giant jigsaw puzzle, but the pieces are split between two friends, Alice and Bob, who are in different rooms. They can't see each other's pieces, and they can only send a very limited number of text messages to a central "Puzzle Master" to help them figure out the final picture.

This paper is about how much information Alice and Bob need to send to solve the puzzle, specifically when the puzzle has a special secret: most of the connections between their pieces are actually empty.

The Setup: The "Vertical" Split

In many data problems, we usually split data by rows (giving Alice half the people and Bob the other half). This paper looks at a different setup called the "Vertical Split."

The Scenario: Imagine a hospital where one doctor records a patient's genetic data (Alice) and another records their clinical symptoms (Bob). They have the same patients, but they see different features of those patients.
The Goal: They want to find the Cross-Covariance. In plain English, they want to know: "Which specific genes are actually linked to which specific symptoms?"
The Constraint: They can only send a tiny number of bits (text messages) to the server. They need to compress their massive data files into these tiny messages.

The Old Problem: The "Dense" Puzzle

Previously, researchers (Rahmani et al., 2025) figured out that if every gene could potentially link to every symptom (a "dense" puzzle), Alice and Bob had to send a huge amount of information. The cost of communication grew directly with the total number of possible gene-symptom pairs ( $d_1 \times d_2$ ).

Think of it like this: If you have 1,000 genes and 1,000 symptoms, there are 1 million possible connections. In the old "dense" model, you had to describe the status of all 1 million connections, even if 999,999 of them were just noise.

The New Discovery: Sparsity is a Superpower

The authors of this paper asked a simple question: "What if most of those connections are actually zero?"

In reality, a specific gene usually only affects a few specific symptoms. The "Cross-Covariance" matrix is sparse—it's mostly zeros, with only a few important numbers ( $s$ ) scattered around.

The Big Surprise:
In other types of data problems (like estimating an average), knowing the data is sparse didn't help reduce the communication cost. But in this specific "Vertical Split" scenario, sparsity is a game-changer.

The Result: If the number of real connections is small (sparse), Alice and Bob don't need to send messages about the 1 million empty spots. They only need to send messages about the few important spots.
The Analogy:
- Dense (Old Way): You have to send a map of the entire ocean, marking every single drop of water, even though you only care about the few islands.
- Sparse (New Way): You realize 99% of the ocean is empty. You only send a map of the islands. The amount of data you send drops from "the size of the ocean" to "the size of the islands."

How They Proved It

The authors used a clever mathematical trick to prove this.

The Lower Bound (The "Impossible" Limit): They created a scenario where they tried to trick the system. They asked, "What is the absolute minimum amount of data Alice and Bob must send to be sure they get the right answer?" They proved that if the connections are sparse, the minimum data required drops dramatically. It goes from scaling with the total size ( $d_1 d_2$ ) to scaling with the number of real connections ( $s$ ) times a small log factor.
- Metaphor: They proved that you can't cheat the system; you simply cannot solve the puzzle with fewer messages than this new, lower limit.
The Achievable Scheme (The "How-To"): They also built a protocol (a set of rules) that actually works.
- Step 1: They use a "Covering Net" to compress the data (like taking a high-res photo and shrinking it to a thumbnail).
- Step 2: They use "Hard Thresholding." This is like a filter. When the server receives the data, it looks at every connection. If the connection looks too weak (like background noise), it sets it to zero. If it's strong, it keeps it.
- The Result: This method achieves the theoretical minimum they proved earlier. It confirms that the "sparse" savings are real and achievable.

Why This Matters (According to the Paper)

The paper highlights that this is different from other distributed problems. Usually, sparsity helps you get a better statistical answer (you need fewer samples), but it doesn't help you save on communication.

Here, sparsity helps both. Because the agents (Alice and Bob) are looking at the same underlying samples (the same patients) but different features, the correlation structure allows them to exploit the "empty space" in the data to drastically cut down the number of bits they need to send.

In a nutshell:
If you are trying to find the links between two sets of data (like genes and symptoms) and you know that most links don't exist, you can communicate much more efficiently than if you assumed every possible link might exist. This paper proves exactly how much you can save and how to do it.

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

Problem Formulation
This paper investigates the minimax estimation error for distributed covariance matrix estimation (DCME) in the vertical-split (feature-split) setting. In this model, $K=2$ agents observe the same set of $m$ independent and identically distributed (i.i.d.) samples from a $d$ -dimensional sub-Gaussian distribution, but each agent observes only a disjoint subset of the coordinates. Specifically, Agent 1 observes the first $d_1$ coordinates and Agent 2 observes the remaining $d_2$ coordinates.

The primary estimation target is the cross-covariance matrix $C_{21} = \mathbb{E}[(X_2 - \mathbb{E}X_2)(X_1 - \mathbb{E}X_1)^\top] \in \mathbb{R}^{d_2 \times d_1}$ . The diagonal blocks ( $C_{11}$ and $C_{22}$ ) can be estimated locally without communication; thus, the communication cost is driven by the need to estimate $C_{21}$ . The agents compress their local data into limited bit budgets $B_1$ and $B_2$ and transmit them to a central server.

The paper focuses on the scenario where the cross-covariance matrix $C_{21}$ is $s$ -sparse, meaning it contains at most $s$ non-zero entries. The central question is whether this structural sparsity can reduce the required communication budget and sample complexity compared to the dense (unstructured) case, contrasting this with the horizontal-split setting where sparsity was previously shown not to reduce communication costs for mean estimation.

Methodology
The authors employ an information-theoretic framework to establish lower bounds and construct a matching achievable scheme.

Lower Bounds (Converse):
- Fano's Method with Auxiliary Randomness: The proof utilizes an averaged version of Fano's inequality. A hypothesis family is constructed where the cross-covariance matrices are perturbed by signed partial permutation matrices.
- Sparse Packing: A key combinatorial contribution is the construction of a packing set for $s'$ -sparse signed partial permutation matrices (where $s' = s \wedge d_{\min}$ ). The authors prove the existence of a large set of such matrices that are pairwise separated in Hamming distance, adapting the probabilistic argument of Raskutti et al. [2011] to the partial permutation constraint.
- Conditional Strong Data Processing Inequality (C-SDPI): To handle the correlation between agents' data (since they observe the same underlying samples), the paper relies on the C-SDPI framework introduced by Rahmani et al. [2025]. This inequality quantifies information contraction through a state-dependent channel, where the state is the unknown cross-covariance. The authors show that averaging over the random support patterns (via the auxiliary variable $W$ ) allows for a tractable computation of the C-SDPI coefficient.
- Hypothesis Separation: The separation between hypotheses is measured in the Frobenius norm, linked to the Hamming distance of the underlying sparse matrices via an isometry.
Achievability (Direct):
- Protocol Design: The authors propose a distributed protocol combining covering-net quantization (for the dense parts of the data) with entry-wise hard thresholding (to exploit sparsity).
- Steps: Agents locally estimate self-covariances and quantize them. For the cross-covariance, agents subsample and quantize their data vectors using covering nets. The central server reconstructs the empirical cross-covariance and applies a hard threshold to entries, setting small values to zero.
- Analysis: The error analysis decomposes the distortion into quantization noise and statistical noise. Crucially, the authors utilize concentration inequalities for sub-exponential products (arising from the cross-covariance terms) to bound the statistical error, which is not required in the dense case.

Key Contributions and Results

Sparsity Reduces Communication in Vertical Split: The paper proves that, unlike in the horizontal-split setting for mean estimation, sparsity does reduce the communication cost for cross-covariance estimation in the vertical split.
Minimax Lower Bounds:
- For $s$ -sparse cross-covariance estimation under the Frobenius norm, the communication budget per agent $B_k$ must scale as:
  $B_k = \Omega\left( \frac{\sigma^4 d_k s' \log(d_1 d_2 / s')}{\varepsilon^2} \right)$
- The sample complexity $m$ must scale as:
  $m = \Omega\left( \frac{\sigma^4 s' \log(d_1 d_2 / s')}{\varepsilon^2} \right)$
- Here, $s' = s \wedge d_{\min}$ . In the 1-sparse case ( $s=1$ ), this yields an exponential improvement in dimension dependence, reducing the factor from $d_1 d_2$ (dense rate) to $\log(d_1 d_2)$ .
Matching Achievability: The proposed protocol achieves the derived lower bounds up to polylogarithmic factors, confirming the tightness of the bounds.
Combinatorial Lemma: The paper establishes a new packing result for $s'$ -sparse signed partial permutation matrices, showing the existence of a set of size roughly $( (2d_1 d_2)^{3/4} / (4s'^2) )^{s'}$ with pairwise Hamming distance greater than $s'/2$ .

Significance and Claims
The paper claims to resolve an open question left by Rahmani et al. [2025] regarding the impact of sparsity in the vertical-split model. The authors demonstrate that the structural reason for the improvement is that the vertical-split framework lacks a mechanism to inflate the communication bound beyond what the packing number dictates. By restricting the hypothesis space to $s'$ -sparse matrices, the packing number (and thus the required information to distinguish hypotheses) reduces from $\log |V| \sim d_1 d_2$ to $\log |V| \sim s' \log(d_1 d_2 / s')$ .

This result is significant for distributed systems where cross-agent dependencies are inherently sparse, such as in multi-omics studies (correlating different biological feature sets) or finance (linking transaction histories with credit records). The paper notes that while the dense case requires communication linear in the ambient dimension product, the sparse case allows for communication scaling with the intrinsic dimension $s'$ , offering substantial efficiency gains.

The authors remain modest regarding open problems, specifically noting that their achievable scheme requires prior knowledge of the sparsity level $s$ to calibrate the threshold. Whether a protocol can achieve the same rates without knowing $s$ remains an open question. Similarly, the extension of these results to other structural assumptions (e.g., low-rank, banded, or group sparsity) is identified as a direction for future work.