Résumé technique : Sur la malédiction de la dimensionnalité dans l'estimation de la covariance creuse et l'ACP privées

Énoncé du problème

Cet article étudie l'estimation de la covariance et l'analyse en composantes principales (ACP) en haute dimension avec confidentialité différentielle (DP) dans des régimes où la dimension ambiante $d$ est comparable ou nettement supérieure à la taille de l'échantillon $n$. Dans ces contextes, les estimateurs classiques (par exemple, les matrices de covariance empiriques) sont prouvés comme étant inconsistants sans hypothèses structurelles. Les auteurs se concentrent sur deux problèmes canoniques sous la condition de $k$-raies-colonnes creuses ($k$-RCS) :

1. Estimation de la covariance creuse (Problème 1) : Récupérer une matrice de covariance $\Sigma$ possédant $k$ lignes et colonnes creuses dans la norme opérateur.
2. ACP creuse (Problème 2) : Récupérer le premier vecteur propre $v_1$ de $\Sigma$.

La motivation centrale est de résoudre une divergence dans la littérature : alors que l'estimation creuse non privée ne nécessite que $\text{poly}(k, \log d)$ échantillons, les meilleurs résultats connus en DP (par exemple, [WX21]) sous des hypothèses naturelles d'invariance d'échelle nécessitent $\Omega(d)$ échantillons. L'article demande si cette « malédiction de la dimensionnalité » est inhérente à la DP ou si elle peut être atténuée par des hypothèses structurelles supplémentaires.

Méthodologie et modèles

Les auteurs analysent ces problèmes sous deux modèles statistiques principaux :

• Modèle 1 (Covariance $k$-creuse) : La matrice de covariance $\Sigma$ est $k$-RCS, mais le premier vecteur propre $v_1$ n'est pas supposé être creux.
• Modèle 2 (ACP $k$-creuse) : Un renforcement du Modèle 1 où le premier vecteur propre $v_1$ est également $k$-creux.

L'étude distingue la DP pure ($\delta=0$) de la DP approximative ($\delta > 0$).

Techniques de borne supérieure

• Estimation de la covariance creuse : Les auteurs proposent un algorithme de seuillage (Algorithme 1). Il consiste à tronquer les entrées de données pour contrôler la sensibilité, calculer la covariance empirique, puis effectuer une sélection privée des $k$ meilleures entrées pour chaque ligne en utilisant le mécanisme de Laplace. L'algorithme repose sur la composition avancée pour gérer le coût de confidentialité de la sélection de $k$ entrées à travers $d$ lignes.
• ACP creuse (Modèle 2) : Pour atteindre une complexité d'échantillonnage indépendante de la dimension, les auteurs utilisent la primitive FriendlyCore (de [TCK+22]). Cela permet la construction d'une moyenne pondérée de covariances par lots qui possède une sensibilité bornée dans la norme $\ell_{\infty,\infty}$, indépendante de $d$. Cette estimation stable est ensuite perturbée par un bruit gaussien. Crucialement, l'algorithme exploite la parcimonie de $v_1$ (Modèle 2) pour estimer le support du vecteur propre via une étape d'estimation de support privée, évitant ainsi de devoir scanner l'ensemble des $d$ dimensions.

Techniques de borne inférieure

• Empreintes digitales (Fingerprinting) et constructions graphiques : Pour l'estimation de la covariance creuse, les auteurs adaptent les techniques d'empreinte digitale (de [Nar24]) en utilisant une construction basée sur la distribution de Wishart inverse et des projections de graphes. Ils instancient un modèle de remplacement bayésien pour dériver des bornes inférieures.
• Arguments de compactage (Packing Arguments) : Pour l'ACP creuse sous DP pure, les auteurs construisent une famille de matrices de covariance $k$-RCS avec des vecteurs propres principaux denses en utilisant des graphes expanseurs bipartites et des codes de Gilbert-Varshamov. Cela crée un ensemble de compactage de taille $\exp(\Omega(d))$, prouvant que distinguer entre ces distributions nécessite $\Omega(d)$ échantillons.
• Lemme d'Assouad : Pour la borne inférieure de l'ACP sous DP approximative, ils emploient une variante de la méthode d'Assouad privée, construisant une famille de distributions basées sur des pics de bordure (edge-spikes) dans un graphe pour démontrer que même avec la DP approximative, la complexité d'échantillonnage dépendante de la dimension persiste pour certaines distributions « pointues » (spiky).

Résultats clés

1. Estimation de la covariance creuse privée (Problème 1)

• Borne supérieure : L'article établit une complexité d'échantillonnage de $\tilde{O}(k^2 + \sqrt{d} \cdot k^{1.5})$ sous DP approximative. Le facteur $\sqrt{d}$ provient de la nécessité de sélectionner privement les $k$ meilleures entrées pour chacune des $d$ lignes.
• Borne inférieure : Une borne inférieure correspondante de $\tilde{\Omega}(k^2 + \sqrt{d} \cdot k)$ est prouvée.
• Implication : La dépendance en $\sqrt{d}$ est serrée. Même avec la DP approximative, il existe un écart exponentiel entre les complexités d'échantillonnage privées et non privées lorsque $k = \text{polylog}(d)$.

2. ACP creuse privée (Problème 2)

• Sous le Modèle 2 (Vecteur propre creux) : Les auteurs montrent que si le premier vecteur propre est également $k$-creux, une complexité d'échantillonnage de $\text{poly}(k, \log d)$ est réalisable sous DP approximative (Théorème 3). Cela contourne la malédiction de la dimensionnalité.
• Sous le Modèle 1 (Vecteur propre général) :
  • DP pure : Une borne inférieure de $\Omega(d/\epsilon)$ est prouvée (Théorème 4). Cela démontre que sans l'hypothèse de parcimonie sur $v_1$, la DP pure nécessite un nombre linéaire d'échantillons en $d$.
  • DP approximative : Une borne inférieure de $\Omega(d/\epsilon)$ est également établie pour une famille spécifique de distributions $k$-RCS « pointues » (Théorème 5).
• Implication : L'article démontre une séparation où la parcimonie du vecteur propre est une hypothèse structurelle critique qui permet une ACP creuse efficace. Sans elle, le problème souffre d'une malédiction de la dimensionnalité.

3. ACP standard (Non-creuse)

• Les auteurs fournissent une borne inférieure plus forte pour l'ACP DP standard (non creuse) sous DP approximative, montrant que $\Omega(d)$ échantillons sont nécessaires pour une plage de paramètres plus large que ce qui était connu auparavant (Théorème 6). Cela améliore les limites antérieures qui étaient restreintes à de très petits $\delta$ (par exemple, $\delta = \exp(-\Omega(d))$).

Signification et affirmations

L'article affirme fournir la première démonstration d'une séparation exponentielle entre les complexités d'échantillonnage privées et non privées pour des tâches d'estimation creuse naturelles en haute dimension. Spécifiquement :

• Il identifie que la malédiction de la dimensionnalité dans l'estimation de la covariance creuse privée est inhérente sous les paramétrages naturels, avec une dépendance serrée en $\sqrt{d}$.
• Il clarifie que la malédiction de la dimensionnalité dans l'ACP creuse privée n'est pas inhérente si le vecteur propre est creux (Modèle 2), mais l'est si le vecteur propre est dense (Modèle 1).
• Les résultats soulignent que les hypothèses de modélisation (spécifiquement la parcimonie du vecteur propre) peuvent déplacer de manière prouvable le paysage de la complexité d'échantillonnage pour les problèmes de DP.
• L'article laisse comme problème ouvert l'existence d'une borne supérieure $\text{poly}(k, \log d)$ pour le Problème 2 sous le Modèle 1 avec la DP approximative, notant que leur borne inférieure actuelle pour la DP approximative repose sur un paramétrage « pointu » spécifique qui diffère de leurs réglages de borne supérieure.

Le travail contribue par un ensemble flexible de techniques (empreinte digitale, compactage basé sur les graphes et algorithmes basés sur la stabilité) qui produisent des bornes quasi-correspondantes, expliquant précisément quand les procédures de parcimonie-sensibles sont nécessaires et quand elles sont suffisantes.