Résumé technique : Estimation adaptative privée de la covariance via des modèles graphiques gaussiens (PACE-GGM)

Énoncé du problème

L'estimation de la covariance est une tâche fondamentale en statistiques et en apprentissage automatique, sous-tendant la régression, l'analyse en composantes principales et la modélisation multivariée. Dans des contextes impliquant des données sensibles, la confidentialité différentielle (DP) est requise pour publier des estimations tout en protégeant les enregistrements individuels. L'approche canonique, connue sous le nom de mécanisme gaussien (ou perturbation des statistiques suffisantes, SSP), ajoute du bruit à toutes les $d(d+1)/2$ entrées de la matrice de covariance empirique. Cette méthode repose sur une borne globale de la norme $\ell_2$ pour les enregistrements de données, résultant en une sensibilité de $\sqrt{2}C^2/n$ pour la matrice complète.

Cependant, dans de nombreuses applications pratiques (par exemple, des données tabulaires avec des attributs tronqués ou normalisés), il est plus naturel de supposer des bornes coordonnées ($|x_j| \le B$) plutôt qu'une borne globale $\ell_2$ serrée. Sous une borne $\ell_\infty$, la sensibilité d'une entrée unique est de $2B^2/n$, tandis que la sensibilité de la matrice complète est de $\sqrt{2}dB^2/n$. Cela crée une disparité significative : une entrée unique peut être mesurée avec un écart-type de bruit un facteur $d/\sqrt{2}$ plus petit que celui de la matrice complète pour le même budget de confidentialité. Le problème central abordé est de savoir si un algorithme peut être conçu pour mesurer sélectivement un sous-ensemble des entrées les plus informatives de la matrice de covariance empirique et reconstruire la matrice complète, concentrant ainsi le budget de confidentialité plus efficacement qu'une perturbation uniforme.

Méthodologie : PACE-GGM

Les auteurs proposent PACE-GGM (Estimation Adaptative Privée de la Covariance via des Modèles Graphiques Gaussiens), un algorithme itératif basé sur un paradigme « sélection-mesure-reconstruction ». La méthode opère sous une confidentialité différentielle concentrée à zéro (zCDP).

1. Initialisation

L'algorithme commence par allouer une fraction du budget de confidentialité ($\rho_{diag}$) pour mesurer toutes les entrées diagonales de la matrice de covariance en utilisant le mécanisme gaussien. Cela forme une estimation initiale $\hat{\Sigma}^{(0)}$.

2. Boucle itérative Sélection-Mesure-Reconstruction

L'algorithme procède par rounds, maintenant un ensemble de mesures bruitées $\{y_{jk}\}$ et leurs précisions associées $\{\lambda_{jk}\}$. À chaque tour :

• Sélection : Une entrée $(j, k)$ mal approximée par l'estimation courante est sélectionnée en utilisant le mécanisme exponentiel. Le score de qualité est l'erreur d'approximation $|\Sigma_{jk}(X) - \hat{\Sigma}^{(t-1)}_{jk}|$. Cette étape identifie de manière adaptative quelles entrées fournissent le plus grand gain d'information.
• Mesure : L'entrée sélectionnée est mesurée en utilisant le mécanisme gaussien avec une partie du budget restant. La nouvelle mesure est combinée avec les mesures précédentes de la même entrée en utilisant un pondération par l'inverse de la variance pour mettre à jour la moyenne pondérée par la précision $y_{jk}$ et la précision $\lambda_{jk}$.
• Reconstruction : Une nouvelle matrice de covariance complète $\hat{\Sigma}^{(t)}$ est reconstruite en résolvant un problème d'optimisation de Maximum d'Entropie. L'objectif est de trouver la matrice semi-définie positive (PSD) qui minimise l'erreur de reconstruction (négatif de la vraisemblance des mesures observées) tout en maximisant le log-déterminant (entropie).
  • Mathématiquement, cela résout :
    $$\max_{\Sigma} \log |\Sigma| \quad \text{sous contrainte} \quad \Sigma \in \arg\min_{W \succeq 0} \sum_{(j,k) \in S} \lambda_{jk} (W_{jk} - y_{jk})^2$$
  • Cela se connecte au problème classique de Sélection de Covariance (Dempster, 1972) et aux Modèles Graphiques Gaussiens (GGM). La solution correspond à un GGM où la matrice de précision $K = \Sigma^{-1}$ possède des zéros pour les entrées non observées (indépendance conditionnelle).
  • Les auteurs proposent une Méthode de Point Intérieur (IPM-CHOLESKY) paramétrant $\Sigma$ via son facteur de Cholesky ($L$) pour résoudre cela efficacement, gérant les cas où le problème pourrait être mal posé en raison du bruit.

3. Recuit du Budget

Pour gérer le compromis entre mesure et reconstruction, l'algorithme emploie une stratégie de recuit de budget (inspirée de AIM). Si le changement d'une estimation après mesure est faible par rapport au niveau de bruit, le budget par tour est augmenté pour permettre des mesures futures plus informatives.

4. Garantie de Confidentialité

L'algorithme satisfait le $\rho$-zCDP. La preuve repose sur les propriétés de composition du zCDP :

• L'étape d'initialisation satisfait le $\rho_{diag}$-zCDP.
• Chaque tour implique une composition adaptative du mécanisme exponentiel et du mécanisme gaussien.
• L'étape de reconstruction est une opération de post-traitement et n'engendre aucun coût de confidentialité supplémentaire.

Contributions Clés

1. Sélection Adaptative d'Entrées : PACE-GGM est la première méthode à sélectionner de manière privée et adaptative quelles entrées de covariance mesurer en fonction des données, plutôt que de privatiser la matrice complète ou de sélectionner en fonction d'une hypothèse structurelle fixe (comme la parcimonie).
2. Reconstruction par Maximum d'Entropie : L'article introduit une méthode de reconstruction fondée sur des principes qui récupère la matrice de covariance complète à partir d'observations partielles et bruitées en trouvant le complétion PSD à entropie maximale. Cela connecte la mesure adaptative à la théorie des Modèles Graphiques Gaussiens.
3. Analyse de Sensibilité : Les auteurs démontrent rigoureusement que sous des bornes coordonnées ($\ell_\infty$), mesurer des entrées individuelles est significativement plus efficace (d'un facteur $d/\sqrt{2}$) que de mesurer la matrice complète, justifiant ainsi l'approche sélective.
4. Innovation du Solveur : Le développement d'un solveur IPM-CHOLESKY qui gère efficacement la non-convexité de la paramétrisation de Cholesky et exploite les composantes connexes dans le graphe de mesure pour réduire la complexité computationnelle.

Résultats Expérimentaux

La méthode a été évaluée sur 14 ensembles de données réels avec des dimensions allant de $d=6$ à $d=260$ à travers divers budgets de confidentialité ($\rho \in \{10^{-4}, \dots, 10\}$).

• Performance : PACE-GGM surpasse constamment le mécanisme gaussien standard (SSP) et d'autres bases de référence comme AdaptiveCov et un estimateur uniquement diagonal.
• Régime d'Amélioration : Les gains sont les plus prononcés dans des contextes de haute dimension et des régimes de budget de confidentialité faible à modéré. Dans ces scénarios, la capacité à concentrer le budget sur des entrées informatives produit des erreurs de Mahalanobis et de Frobenius significativement plus faibles.
• Parcimonie : L'algorithme concentre naturellement les mesures sur les entrées où la covariance sous-jacente est dense. Pour des ensembles de données de haute dimension (par exemple, $d=260$), il mesure une très petite fraction d'entrées hors diagonale (par exemple, 0,1 % pour l'ensemble de données madeline) tout en atteignant une précision supérieure par rapport aux méthodes qui perturbent toutes les entrées.
• Robustesse du Solveur : Les expériences ont montré que la formulation par Maximum d'Entropie via IPM est plus robuste et stable que la Descente de Gradient Projetée (PGD), qui était sensible à l'initialisation.

Importance et Revendications

L'article revendique que PACE-GGM comble un vide dans la synthèse et l'estimation de données à confidentialité différentielle. Alors que les méthodes basées sur les marginales ciblent des variables discrètes ou discrétisées, PACE-GGM fournit un bloc de construction pour la génération de données synthétiques continues en estimant avec précision la structure de covariance des variables continues.

Les auteurs soulignent que la méthode est particulièrement efficace lorsque le modélisateur dispose de bornes coordonnées (un contexte naturel pour les données tabulaires) mais manque d'une borne globale $\ell_2$ serrée. En évitant la distribution uniforme de bruit du SSP, PACE-GGM atteint des performances de l'état de l'art dans des régimes où les budgets de confidentialité sont contraints et les dimensions sont élevées. La méthode est présentée comme une routine pratique et adaptative aux données qui améliore l'erreur d'estimation sans nécessiter un réglage complexe des hyperparamètres, car elle est robuste aux choix spécifiques des fractions d'allocation de budget ($\alpha$ et $\beta$).