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

Résumé Technique : Bornes de l'information théorique pour l'estimation de la covariance parcimonieuse dans le modèle distribué à division verticale

Formulation du problème
Cet article étudie l'erreur d'estimation minimax pour l'estimation de la matrice de covariance distribuée (DCME) dans le cadre de la division verticale (division par caractéristiques). Dans ce modèle, $K=2$ agents observent le même ensemble de $m$ échantillons indépendants et identiquement distribués (i.i.d.) provenant d'une distribution sous-gaussienne, mais chaque agent n'observe que des sous-ensembles disjoints des coordonnées. Plus précisément, l'Agent 1 observe les $d_1$ premières coordonnées et l'Agent 2 observe les $d_2$ coordonnées restantes.

La cible d'estimation principale est la matrice de co-variance croisée $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}$. Les blocs diagonaux ($C_{11}$ et $C_{22}$) peuvent être estimés localement sans communication ; ainsi, le coût de communication est dicté par la nécessité d'estimer $C_{21}$. Les agents compressent leurs données locales en budgets de bits limités $B_1$ et $B_2$ et les transmettent à un serveur central.

L'article se concentre sur le scénario où la matrice de co-variance croisée $C_{21}$ est $s$-parcimonieuse, c'est-à-dire qu'elle contient au plus $s$ entrées non nulles. La question centrale est de savoir si cette parcimonie structurelle peut réduire le budget de communication et la complexité d'échantillonnage requis par rapport au cas dense (non structuré), contrastant avec le cadre de division horizontale où la parcimonie n'a pas été montrée comme réduisant les coûts de communication pour l'estimation de la moyenne.

Méthodologie
Les auteurs emploient un cadre d'information théorique pour établir des bornes inférieures et construire un schéma réalisable correspondant.

1. Bornes inférieures (Converse) :

   • Méthode de Fano avec aléatoire auxiliaire : La preuve utilise une version moyennée de l'inégalité de Fano. Une famille d'hypothèses est construite où les matrices de co-variance croisée sont perturbées par des matrices de permutations partielles signées.
   • Empilement parcimonieux (Sparse Packing) : Une contribution combinatoire clé est la construction d'un ensemble d'empilement pour les matrices de permutations partielles signées $s'$-parcimonieuses (où $s' = s \wedge d_{\min}$). Les auteurs prouvent l'existence d'un grand ensemble de telles matrices qui sont mutuellement séparées selon la distance de Hamming, adaptant l'argument probabiliste de Raskutti et al. [2011] à la contrainte de permutation partielle.
   • Inégalité de traitement de données forte conditionnelle (C-SDPI) : Pour gérer la corrélation entre les données des agents (puisqu'ils observent les mêmes échantillons sous-jacents), l'article s'appuie sur le cadre C-SDPI introduit par Rahmani et al. [2025]. Cette inégalité quantifie la contraction d'information à travers un canal dépendant de l'état, où l'état est la co-variance croisée inconnue. Les auteurs montrent qu'en moyennant sur les motifs de support aléatoires (via la variable auxiliaire $W$), un calcul traitable de le coefficient C-SDPI est possible.
   • Séparation d'hypothèses : La séparation entre les hypothèses est mesurée par la norme de Frobenius, liée à la distance de Hamming des matrices creuses sous-jacentes via une isométrie.

2. Réalisabilité (Direct) :

   • Conception du protocole : Les auteurs proposent un protocole distribué combinant la quantification par réseau de couverture (pour les parties denses des données) avec un seuillage dur par entrée (pour exploiter la parcimonie).
   • Étapes : Les agents estiment localement les auto-covariances et les quantifient. Pour la co-variance croisée, les agents sous-échantillonnent et quantifient leurs vecteurs de données à l'aide de réseaux de couverture. Le serveur central reconstruit la co-variance empirique et applique un seuillage dur aux entrées, fixant les petites valeurs à zéro.
   • Analyse : L'analyse de l'erreur décompose la distorsion en bruit de quantification et bruit statistique. Crucialement, les auteurs utilisent des inégalités de concentration pour les produits sous-exponentiels (provenant des termes de co-variance croisée) pour borner l'erreur statistique, ce qui n'est pas requis dans le cas dense.

Contributions clés et résultats

• La parcimonie réduit la communication dans la division verticale : L'article prouve que, contrairement au cadre de division horizontale pour l'estimation de la moyenne, la parcimonie réduit effectivement le coût de communication pour l'estimation de la co-variance croisée dans la division verticale.
• Bornes inférieures minimax :
  • Pour l'estimation de la co-variance croisée $s$-parcimonieuse sous la norme de Frobenius, le budget de communication par agent $B_k$ doit suivre l'échelle :
    $$B_k = \Omega\left( \frac{\sigma^4 d_k s' \log(d_1 d_2 / s')}{\varepsilon^2} \right)$$
  • La complexité d'échantillonnage $m$ doit suivre l'échelle :
    $$m = \Omega\left( \frac{\sigma^4 s' \log(d_1 d_2 / s')}{\varepsilon^2} \right)$$
  • Ici, $s' = s \wedge d_{\min}$. Dans le cas 1-parcimonieux ($s=1$), cela produit une amélioration exponentielle de la dépendance à la dimension, réduisant le facteur de $d_1 d_2$ (taux dense) à $\log(d_1 d_2)$.
• Réalisabilité correspondante : Le protocole proposé atteint les bornes inférieures dérivées à des facteurs polylogarithmiques près, confirmant la précision des bornes.
• Lemme combinatoire : L'article établit un nouveau résultat d'empilement pour les matrices de permutations partielles signées $s'$-parcimonieuses, montrant l'existence d'un ensemble de taille approximativement $( (2d_1 d_2)^{3/4} / (4s'^2) )^{s'}$ avec une distance de Hamming mutuelle supérieure à $s'/2$.

Signification et affirmations
L'article affirme résoudre une question ouverte laissée par Rahmani et al. [2025] concernant l'impact de la parcimonie dans le modèle de division verticale. Les auteurs démontrent que la raison structurelle de l'amélioration est que le cadre de division verticale manque d'un mécanisme pour gonfler la borne de communication au-delà de ce que dicte le nombre de packing. En restreignant l'espace des hypothèses aux matrices $s'$-parcimonieuses, le nombre de packing (et donc l'information requise pour distinguer les hypothèses) passe de $\log |V| \sim d_1 d_2$ à $\log |V| \sim s' \log(d_1 d_2 / s')$.

Ce résultat est significatif pour les systèmes distribués où les dépendances entre agents sont intrinsèquement parcimonieuses, comme dans les études multi-omiques (corrélant différents ensembles de caractéristiques biologiques) ou la finance (reliant l'historique des transactions aux dossiers de crédit). L'article note que tandis que le cas dense nécessite une communication linéaire dans le produit de la dimension ambiante, le cas parcimonieux permet une communication dont l'échelle est liée à la dimension intrinsèque $s'$, offrant des gains d'efficacité substantiels.

Les auteurs restent modestes concernant les problèmes ouverts, notant spécifiquement que leur schéma réalisable nécessite la connaissance préalable du niveau de parcimonie $s$ pour calibrer le seuil. Savoir si un protocole peut atteindre les mêmes taux sans connaître $s$ demeure une question ouverte. De même, l'extension de ces résultats à d'autres hypothèses structurelles (par exemple, faible rang, bandes ou parcimonie de groupe) est identifiée comme une direction pour les travaux futurs.