Résumé technique : Analyse en composantes principales robuste et différentiellement privée

Énoncé du problème

L'analyse en composantes principales (PCA) est un outil fondamental pour la réduction de la dimensionnalité, pourtant son application à des données sensibles nécessite des garanties de confidentialité rigoureuses, généralement fournies par la confidentialité différentielle (DP). Cependant, les méthodes existantes de DP-PCA font face à des limitations significatives :

1. Hypothèses distributionnelles : De nombreuses méthodes reposent sur des hypothèses restrictives, telles que des données sous-gaussiennes, ce qui échoue lorsque les données sont à queues lourdes (par exemple, les distributions de Cauchy ou les distributions $t$ multivariées).
2. Manque de robustesse : Les mécanismes de DP standards dépendent souvent de statistiques comme la moyenne échantillonnale ou la covariance, qui sont très sensibles aux valeurs aberrantes et à la contamination des données. La contamination peut gonfler la sensibilité du mécanisme, nécessitant un bruit excessif qui dégrade l'utilité statistique.
3. Barrières computationnelles et pratiques : Certaines approches de PCA privée robustes sont coûteuses en termes de calcul, reposent sur des paramètres de modèle inconnus qui doivent être estimés (introduisant ainsi un bruit supplémentaire), ou sont difficiles à étendre au-delà de la première composante principale.

Le papier traite le besoin d'une méthode de PCA qui soit simultanément différentiellement privée, robuste aux distributions à queues lourdes et à la contamination des données, et efficace sur le plan computationnel pour l'extraction de plusieurs composantes principales.

Méthodologie

Les auteurs proposent une méthode appelée $g$-DPPCA (Generalized Differentially Private PCA), qui exploite les propriétés des distributions elliptiques et des signes spatiaux généralisés.

1. Fondement théorique : Tau de Kendall multivarié généralisé

Le cœur de la méthode est la Matrice de Tau de Kendall multivarié généralisée ($K_{g\xi}$).

• Signe spatial généralisé : La méthode utilise une transformation $g_\xi(t) = \xi(\|t\|_2) \cdot \frac{t}{\|t\|_2}$, où $\xi$ est une fonction d'échelle positive. Cela préserve la direction d'un vecteur tout en rescalant sa magnitude.
• Préservation des vecteurs propres : Sous l'hypothèse que les données suivent une distribution elliptique (ce qui inclut les distributions gaussiennes et à queues lourdes), les vecteurs propres de la matrice de Tau de Kendall généralisée $K_{g\xi}$ coïncident avec ceux de la matrice de dispersion de la population $\Sigma$. Cela permet d'effectuer la PCA sur $K_{g\xi}$ plutôt que sur la matrice de covariance standard.
• Bornage : Pour assurer la robustesse et une sensibilité finie pour la DP, la fonction $g$ est restreinte à être bornée (c'est-à-dire $\|g\|_\infty < \infty$). Deux transformations spécifiques sont analysées :
  • Transformation sphérique ($g_{sph}$) : Projette les vecteurs sur la sphère unité ($\xi(s)=1$).
  • Winsorisation ($g^{(r)}_{wins}$) : Tronque les vecteurs dépassant un rayon $r$ à la frontière de la boule ($\xi(s) = \min(r, s)$).

2. Estimation et mécanisme de confidentialité

• Estimateur : La matrice de population $K_{g\xi}$ est estimée à l'aide d'une U-statistique de second ordre, $\hat{K}_g$, basée sur les différences par paires des données :
  $$\hat{K}_g(S) = \frac{2}{n(n-1)} \sum_{i<j} g\left(\frac{X_j - X_i}{\sqrt{2}}\right) g\left(\frac{X_j - X_i}{\sqrt{2}}\right)^\top$$
  Cette formulation évite d'estimer le paramètre de localisation $\mu$ (moyenne), qui est une source d'inefficacité et de bruit dans d'autres méthodes robustes privées.
• Confidentialité différentielle : Puisque $g$ est bornée, la sensibilité de $\hat{K}_g$ est bornée. Les auteurs ajoutent un bruit gaussien à l'estimateur vectorisé $\hat{K}_g$ pour satisfaire la $(\epsilon, \delta)$-DP.
• Post-traitement : Les composantes principales privées sont obtenues en extrayant les vecteurs propres de la matrice perturbée $\tilde{K}_g$. Par la propriété de post-traitement de la DP, les vecteurs propres résultants restent différentiellement privés.

Contributions clés

1. Cadre unifié pour la robustesse et la confidentialité : Le papier introduit une méthode qui atteint à la fois la confidentialité différentielle et la robustesse contre les données à queues lourdes et la contamination arbitraire des données sans nécessiter d'hypothèses sous-gaussiennes.
2. Garanties théoriques :
   • Récupération de sous-espace : Les auteurs dérivent des bornes d'erreur pour la récupération du sous-espace propre de la population sous le modèle de distribution elliptique. Les bornes dépendent de l'écart propre (eigen-gap) et des paramètres de confidentialité.
   • Point de rupture (Breakdown Point) : La méthode montre d'avoir un point de rupture non nul (borné en dessous par une constante positive lorsque $n \to \infty$), contrairement aux estimateurs standards basés sur la covariance échantillonnale qui ont un point de rupture de $1/n$.
   • Robustesse à la contamination : L'analyse théorique démontre que la méthode reste robuste même lorsqu'une fraction des données est arbitrairement corrompue, à condition que le taux de corruption ne soit pas trop élevé.
3. Efficacité computationnelle : Contrairement à certaines méthodes existantes de PCA privée robuste qui reposent sur une optimisation complexe (par exemple, la descente de gradient géodésique sur la variété de Stiefel), $g$-DPPCA est simple à calculer, impliquant uniquement des différences par paires et une décomposition en valeurs propres.
4. Mise en œuvre pratique : Le papier fournit des directives spécifiques pour choisir le rayon de winsorisation $r$ (par exemple, proportionnel à $\sqrt{d}$ ou via l'estimation privée des quantiles) et compare les variantes sphériques et winsorisées.

Résultats empiriques

Les auteurs ont mené des expériences numériques approfondies comparant $g$-DPPCA (utilisant à la fois les transformations sphériques et winsorisées) à trois méthodes concurrentes :

• Analyze Gauss (AG) : PCA-DP standard sur la matrice de covariance échantillonnale.
• SGPCA : PCA privée supposant une covariance à pics (spiked covariance) et une sous-gaussianité.
• NSGGD : Descente de gradient géodésique stochastique bruyante (une méthode robuste mais intensément coûteuse en calcul).

Résultats :

• Données à queues lourdes : Dans les simulations avec des distributions $t$ multivariées (à queues lourdes), $g$-DPPCA a systématiquement surpassé tous les concurrents. SGPCA et AG ont échoué à récupérer le sous-espace avec précision, tandis que NSGGD a montré une certaine robustesse mais une efficacité moindre que $g$-DPPCA.
• Contamination des données : Sous une contamination de 5 % des données, $g$-DPPCA a maintenu une erreur faible à mesure que la taille de l'échantillon augmentait. En revanche, les erreurs d'AG et de SGPCA n'ont pas diminué, et bien que NSGGD soit robuste, $g$-DPPCA a obtenu une précision supérieure.
• Données gaussiennes : Sous des hypothèses gaussiennes, $g$-DPPCA est performante de manière comparable à SGPCA (qui est théoriquement optimale pour ce cadre) et meilleure qu'AG et NSGGD.
• Données réelles : Une visualisation des données génétiques européennes projetées sur les deux premières composantes principales privées a montré que $g$-DPPCA capture efficacement la structure géographique, produisant des résultats similaires à la PCA non privée, alors que NSGGD produit des projections moins informatives.

Signification et affirmations

Le papier affirme fournir la première méthode de PCA différentiellement privée qui offre des garanties de récupération de sous-espace prouvables sous des distributions elliptiques (incluant les cas à queues lourdes) tout en maintenant la robustesse contre la contamination arbitraire des données.

Les auteurs soulignent que leur approche évite les inefficacités computationnelles et les problèmes d'estimation de paramètres des méthodes robustes privées précédentes. En utilisant le Tau de Kendall généralisé et des signes spatiaux bornés, la méthode atteint un équilibre où :

• Elle ne nécessite pas l'hypothèse restrictive de sous-gaussianité couramment utilisée dans les bornes de DP-PCA optimales.
• Elle ne souffre pas de l'« inflation de bruit » causée par les valeurs aberrantes dans les calculs de sensibilité.
• Elle est facilement implémentable et scalable pour l'extraction de plusieurs composantes principales.

Ce travail suggère que pour l'analyse de données modernes impliquant des ensembles de données potentiellement lourds, sensibles ou contaminés, $g$-DPPCA offre une alternative statistiquement supérieure et pratiquement viable aux techniques existantes de réduction de dimensionnalité préservant la confidentialité.