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

Resumo Técnico: Limites de Informação-Teórica para Estimativa de Covariância Esparsa no Modelo de Divisão Vertical

Formulação do Problema
Este artigo investiga o erro de estimativa minimax para a estimativa de matriz de covariância distribuída (DCME) no cenário de divisão vertical (divisão de características). Neste modelo, $K=2$ agentes observam o mesmo conjunto de $m$ amostras independentes e identicamente distribuídas (i.i.d.) de uma distribuição sub-gaussiana, mas cada agente observa apenas um subconjunto disjunto das coordenadas. Especificamente, o Agente 1 observa as primeiras $d_1$ coordenadas e o Agente 2 observa as $d_2$ coordenadas restantes.

O alvo principal de estimativa é a matriz de covariância cruzada $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}$. Os blocos diagonais ($C_{11}$ e $C_{22}$) podem ser estimados localmente sem comunicação; portanto, o custo de comunicação é impulsionado pela necessidade de estimar $C_{21}$. Os agentes comprimem seus dados locais em orçamentos de bits limitados $B_1$ e $B_2$ e os transmitem para um servidor central.

O artigo foca no cenário em que a matriz de covariância cruzada $C_{21}$ é $s$-esparsa, ou seja, contém no máximo $s$ entradas não nulas. A questão central é se essa esparsidade estrutural pode reduzir o orçamento de comunicação e a complexidade de amostragem em comparação com o caso denso (não estruturado), contrastando com o cenário de divisão horizontal, onde se demonstrou anteriormente que a esparsidade não reduz os custos de comunicação para a estimativa da média.

Metodologia
Os autores empregam um arcabouço de informação-teórica para estabelecer limites inferiores e construir um esquema alcançável correspondente.

1. Limites Inferiores (Converso):

   • Método de Fano com Aleatoriedade Auxiliar: A prova utiliza uma versão média da desigualdade de Fano. Uma família de hipóteses é construída onde as matrizes de covariância cruzada são perturbadas por matrizes de permutação parcial com sinais.
   • Empacotamento Esparso: Uma contribuição combinatória fundamental é a construção de um conjunto de empacotamento para matrizes de permutação parcial com sinais $s'$-esparsas (onde $s' = s \wedge d_{\min}$). Os autores provam a existência de um grande conjunto de tais matrizes que são pairwise separadas em distância de Hamming, adaptando o argumento probabilístico de Raskutti et al. [2011] à restrição de permutação parcial.
   • Desigualdade de Processamento de Dados Forte Condicional (C-SDPI): Para lidar com a correlação entre os dados dos agentes (visto que eles observam as mesmas amostras subjacentes), o artigo baseia-se no arcabouço C-SDPI introduzido por Rahmani et al. [2025]. Esta desigualdade quantifica a contração de informação através de um canal dependente de estado, onde o estado é a covariância cruzada desconhecida. Os autores mostram que a média sobre os padrões de suporte aleatórios (via a variável auxiliar $W$) permite um cálculo tratável do coeficiente C-SDPI.
   • Separação de Hipóteses: A separação entre hipóteses é medida na norma de Frobenius, vinculada à distância de Hamming das matrizes esparsas subjacentes via uma isometria.

2. Alcançabilidade (Direto):

   • Design de Protocolo: Os autores propõem um protocolo distribuído combinando quantização por rede de cobertura (para as partes densas dos dados) com limiarização rígida elemento a elemento (para explorar a esparsidade).
   • Etapas: Os agentes estimam localmente as autocovariâncias e as quantizam. Para a covariância cruzada, os agentes realizam subamostragem e quantizam seus vetores de dados usando redes de cobertura. O servidor central reconstrói a covariância cruzada empírica e aplica um limiar rígido às entradas, definindo valores pequenos como zero.
   • Análise: A análise de erro decompõe a distorção em ruído de quantização e ruído estatístico. Crucialmente, os autores utilizam desigualdades de concentração para produtos sub-exponenciais (derivados dos termos de covariância cruzada) para limitar o erro estatístico, o que não é necessário no caso denso.

Principais Contribções e Resultados

• A Esparsidade Reduz a Comunicação na Divisão Vertical: O artigo prova que, ao contrário do cenário de divisão horizontal para estimativa de média, a esparsidade reduz o custo de comunicação para a estimativa de covariância cruzada na divisão vertical.
• Limites Inferiores Minimax:
  • Para a estimativa de covariância cruzada $s$-esparsa sob a norma de Frobenius, o orçamento de comunicação por agente $B_k$ deve escalar como:
    $$B_k = \Omega\left( \frac{\sigma^4 d_k s' \log(d_1 d_2 / s')}{\varepsilon^2} \right)$$
  • A complexidade de amostragem $m$ deve escalar como:
    $$m = \Omega\left( \frac{\sigma^4 s' \log(d_1 d_2 / s')}{\varepsilon^2} \right)$$
  • Aqui, $s' = s \wedge d_{\min}$. No caso 1-esparso ($s=1$), isso resulta em uma melhoria exponencial na dependência da dimensão, reduzindo o fator de $d_1 d_2$ (taxa densa) para $\log(d_1 d_2)$.
• Alcançabilidade Correspondente: O protocolo proposto atinge os limites derivados até fatores polilogarítmicos, confirmando a precisão dos limites.
• Lema Combinatório: O artigo estabelece um novo resultado de empacotamento para matrizes de permutação parcial com sinais $s'$-esparsas, mostrando a existência de um conjunto de tamanho aproximadamente $( (2d_1 d_2)^{3/4} / (4s'^2) )^{s'}$ com distância de Hamming pairwise superior a $s'/2$.

Significância e Alegações
O artigo afirma resolver uma questão aberta deixada por Rahmani et al. [2025] sobre o impacto da esparsidade no modelo de divisão vertical. Os autores demonstram que a razão estrutural para a melhoria é que o arcabouço de divisão vertical carece de um mecanismo para inflar o limite de comunicação além do que o número de empacotamento dita. Ao restringir o espaço de hipóteses para matrizes $s'$-esparsas, o número de empacotamento (e, portanto, a informação necessária para distinguir hipóteses) reduz de $\log |V| \sim d_1 d_2$ para $\log |V| \sim s' \log(d_1 d_2 / s')$.

Este resultado é significativo para sistemas distribuídos onde as dependências entre agentes são inerentemente esparsas, como em estudos de multi-ômica (correlacionando diferentes conjuntos de características biológicas) ou finanças (vinculando históricos de transações com registros de crédito). O artigo observa que, enquanto o caso denso requer comunicação linear no produto da dimensão ambiente, o caso esparso permite que a comunicação escale com a dimensão intrínseca $s'$, oferecendo ganhos substanciais de eficiência.

Os autores mantêm a modéstia em relação a problemas abertos, notando especificamente que seu esquema alcançável requer conhecimento prévio do nível de esparsidade $s$ para calibrar o limiar. Se um protocolo pode atingir as mesmas taxas sem conhecer $s$ permanece uma questão aberta. Da mesma forma, a extensão destes resultados para outras suposições estruturais (por exemplo, baixo rank, banded ou esparsidade de grupo) é identificada como uma direção para trabalhos futuros.