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

Sintesi Tecnica: Limiti Informazione-Teoretici per la Stima della Covarianza Sparsa nel Modello Distribuito a Divisione Verticale

Formulazione del Problema
Questo articolo investiga l'errore di stima minimax per la stima della matrice di covarianza distribuita (DCME) nel contesto della divisione verticale (feature-split). In questo modello, $K=2$ agenti osservano lo stesso insieme di $m$ campioni indipendenti e identicamente distribuiti (i.i.d.) da una distribuzione sub-gaussiana, ma ogni agente osserva solo un sottoinsieme disgiunto delle coordinate. Nello specifico, l'Agente 1 osserva le prime $d_1$ coordinate e l'Agente 2 osserva le restanti $d_2$ coordinate.

L'obiettivo primario di stima è la matrice di covarianza incrociata $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}$. I blocchi diagonali ($C_{11}$ e $C_{22}$) possono essere stimati localmente senza comunicazione; pertanto, il costo di comunicazione è dettato dalla necessità di stimare $C_{21}$. Gli agenti comprimono i propri dati locali in budget di bit limitati $B_1$ e $B_2$ e li trasmettono a un server centrale.

L'articolo si concentra sullo scenario in cui la matrice di covarianza incrociata $C_{21}$ è $s$-sparsa, ovvero contiene al massimo $s$ elementi non nulli. La questione fondamentale è se questa scarsità strutturale possa ridurre il budget di comunicazione richiesto e la complessità campionaria rispetto al caso denso (non strutturato), ponendosi in contrasto con il setting a divisione orizzontale dove è stato precedentemente dimostrato che la scarsità non riduce i costi di comunicazione per la stima della media.

Metodologia
Gli autori utilizzano un framework informazione-teoretico per stabilire i limiti inferiori (lower bounds) e costruire uno schema realizzabile corrispondente.

1. Limiti Inferiori (Converse):

   • Metodo di Fano con Randomicità Ausiliaria: La dimostrazione utilizza una versione mediata della disuguaglianza di Fano. Viene costruita una famiglia di ipotesi in cui le matrici di covarianza incrociata sono perturbate da matrici di permutazione parziale con segno.
   • Packing Sparso: Un contributo combinatorio chiave è la costruzione di un insieme di packing per matrici di permutazione parziale con segno $s'$-sparse (dove $s' = s \wedge d_{\min}$). Gli autori dimostrano l'esistenza di un grande insieme di tali matrici che sono pairwise separate in distanza di Hamming, adattando l'argomento probabilistico di Raskutti et al. [2011] al vincolo di permutazione parziale.
   • Conditional Strong Data Processing Inequality (C-SDPI): Per gestire la correlazione tra i dati degli agenti (poiché osservano gli stessi campioni sottostanti), l'articolo si affida al framework C-SDPI introdotto da Rahmani et al. [2025]. Questa disuguaglianza quantifica la contrazione dell'informazione attraverso un canale dipendente dallo stato, dove lo stato è la covarianza incrociata incognita. Gli autori mostrano che la mediazione sui pattern di supporto casuali (tramite la variabile ausiliaria $W$) permette un computo trattabile del coefficiente C-SDPI.
   • Separazione delle Ipotesi: La separazione tra le ipotesi è misurata nella norma di Frobenius, collegata alla distanza di Hamming delle matrici sparse sottostanti tramite un'isometria.

2. Realizzabilità (Direct):

   • Design del Protocollo: Gli autori propongono un protocollo distribuito che combina la quantizzazione tramite covering-net (per le parti dense dei dati) con la soglia dura elemento per elemento (per sfruttare la scarsità).
   • Fasi: Gli agenti stimano localmente le auto-covarianze e le quantizzano. Per la covarianza incrociata, gli agenti sottocampionano e quantizzano i loro vettori di dati utilizzando le covering nets. Il server centrale ricostruisce la covarianza incrociata empirica e applica una soglia dura agli elementi, impostando a zero i valori piccoli.
   • Analisi: L'analisi dell'errore decompone la distorsione in rumore di quantizzazione e rumore statistico. Fondamentalmente, gli autori utilizzano disuguaglianze di concentrazione per prodotti sub-esponenziali (derivanti dai termini di covarianza incrociata) per limitare l'errore statistico, operazione che non è richiesta nel caso denso.

Contributi Chiave e Risultati

• La Scarsità Riduce la Comunicazione nella Divisione Verticale: L'articolo dimostra che, diversamente dal caso a divisione orizzontale per la stima della media, la scarsità riduce effettivamente il costo di comunicazione per la stima della covarianza incrociata nella divisione verticale.
• Limiti Minimax (Minimax Lower Bounds):
  • Per la stima della covarianza incrociata $s$-sparsa sotto la norma di Frobenius, il budget di comunicazione per agente $B_k$ deve scalare come:
    $$B_k = \Omega\left( \frac{\sigma^4 d_k s' \log(d_1 d_2 / s')}{\varepsilon^2} \right)$$
  • La complessità campionaria $m$ deve scalare come:
    $$m = \Omega\left( \frac{\sigma^4 s' \log(d_1 d_2 / s')}{\varepsilon^2} \right)$$
  • Qui, $s' = s \wedge d_{\min}$. Nel caso 1-sparse ($s=1$), ciò produce un miglioramento esponenziale nella dipendenza dalla dimensione, riducendo il fattore da $d_1 d_2$ (tasso denso) a $\log(d_1 d_2)$.
• Realizzabilità Coerente (Matching Achievability): Il protocollo proposto raggiunge i limiti derivati fino a fattori polilogaritmici, confermando la compattezza (tightness) dei limiti.
• Lemma Combinatorio: L'articolo stabilisce un nuovo risultato di packing per matrici di permutazione parziale con segno $s'$-sparse, mostrando l'esistenza di un insieme di dimensione circa $( (2d_1 d_2)^{3/4} / (4s'^2) )^{s'}$ con distanza di Hamming pairwise superiore a $s'/2$.

Significatività e Rivendicazioni

L'articolo sostiene di aver risolto una questione aperta lasciata da Rahmani et al. [2025] riguardante l'impatto della scarsità nel modello a divisione verticale. Gli autori dimostrano che la ragione strutturale del miglioramento è che il framework a divisione verticale manca di un meccanismo per gonfiare il limite di comunicazione oltre quanto determinato dal numero di packing. Limitando lo spazio delle ipotesi alle matrici $s'$-sparse, il numero di packing (e quindi l'informazione necessaria per distinguere le ipotesi) si riduce da $\log |V| \sim d_1 d_2$ a $\log |V| \sim s' \log(d_1 d_2 / s')$.

Questo risultato è significativo per i sistemi distribuiti in cui le dipendenze tra agenti sono intrinsecamente sparse, come negli studi multi-omici (correlazione di diversi set di caratteristiche biologiche) o nella finanza (collegamento tra cronologie di transazioni e record di credito). L'articolo nota che mentre il caso denso richiede una comunicazione lineare nel prodotto della dimensione ambiente, il caso sparso permette una comunicazione che scala con la dimensione intrinseca $s'$, offrendo guadagni di efficienza sostanziali.

Gli autori rimangono modesti riguardo ai problemi aperti, notando specificamente che il loro schema realizzabile richiede la conoscenza pregressa del livello di scarsità $s$ per calibrare la soglia. Se un protocollo possa raggiungere gli stessi tassi senza conoscere $s$ rimane una questione aperta. Allo stesso modo, l'estensione di questi risultati ad altre assunzioni strutturali (ad esempio, low-rank, banded o group sparsity) è identificata come una direzione per lavori futuri.