Résumé technique : Une approximation privée de la matrice du second moment de tout intrant subsamplable

Énoncé du problème

L'article traite du problème de l'estimation de la matrice du second moment (équivalente à la matrice de covariance) d'un ensemble de données dans un espace de haute dimension ($\mathbb{R}^d$) de manière différentiellement privée (DP). Bien que l'estimation de cette matrice soit fondamentale en apprentissage automatique et en statistiques, les approches de DP existantes reposent souvent sur des hypothèses restrictives, telles que le fait que les données d'entrée soient tirées d'une distribution gaussienne ou possèdent des valeurs propres bien conditionnées.

Les auteurs se concentrent sur un cadre plus général où les données d'entrée peuvent présenter des différences de variance significatives entre les axes (grands nombres de conditionnement) et peuvent contenir des valeurs aberrantes (outliers). Dans de tels scénarios, les bornes de concentration standard peuvent échouer et les algorithmes de DP traditionnels (par exemple, ceux reposant sur des scores de levier par point bornés) peuvent entraîner une complexité d'échantillonnage prohibitive ou échouer totalement si les valeurs aberrantes possèdent un levier élevé. Le défi central est de parvenir à des compromis utilité-vie privée forts pour les entrées les plus défavorables satisfaisant une propriété structurelle spécifique, sans supposer que la distribution sous-jacente est gaussienne.

Méthodologie

L'hypothèse de subsamplabilité

La contribution théorique centrale est la formalisation de la subsamplabilité $(m, \alpha, \beta)$. Un ensemble de données $X$ est défini comme $(m, \alpha, \beta)$-subsamplable si un sous-échantillonnage aléatoire de taille $m$ (ou plus) préserve la structure spectrale de la matrice du second moment $\Sigma$ originale jusqu'à un facteur multiplicatif de $(1 \pm \alpha)$ avec une probabilité d'au moins $1 - \beta$.

• Cette hypothèse est plus faible que les bornes de concentration matricielle standard, qui exigent une telle préservation pour tout $\alpha, \beta$ avec un $m$ suffisamment grand. Ici, les auteurs exigent seulement l'existence de certains $\alpha, \beta$ et d'un $m$ correspondant.
• Cette propriété permet à l'algorithme de gérer des distributions avec des valeurs aberrantes, à condition que ces dernières ne dominent pas la structure spectrale globale des sous-échantillons aléatoires.

Cadre algorithmique

Les auteurs proposent un cadre algorithmique récursif, s'appuyant sur l'approche de Kamath et al. (2019) mais l'adaptant au contexte de la subsamplabilité plutôt qu'au contexte gaussien. L'algorithme opère sous le cadre de la zCDP (zero-Concentrated Differential Privacy).

1. Initialisation : L'algorithme suppose que l'intrant est borné en norme $L_2$ par $R$ et que la matrice du second moment $\Sigma$ satisfait $I \preceq \Sigma \preceq R^2 I$. Cela est réalisé en estimant la plage $R$ et la valeur propre minimale $\lambda_{\min}$ à l'aide d'outils de DP existants.
2. Préconditionnement récursif :
   • Dans chaque itération, du bruit est ajouté à la matrice empirique du second moment pour garantir la confidentialité.
   • L'algorithme identifie le sous-espace $V$ correspondant aux grandes valeurs propres (celles $\ge \psi \kappa$, où $\kappa$ est la borne supérieure actuelle des valeurs propres).
   • Une transformation linéaire $\Pi$ est appliquée pour réduire la projection des points de données sur $V$ par un facteur $\eta$ (spécifiquement $\eta = 1/2$).
   • Crucialement, contrairement au cas gaussien où tous les points rétrécissent uniformément, les auteurs doivent gérer les points dont les normes dépassent la nouvelle borne après transformation. Ils définissent un « ensemble de queue » $P_{tail}$ contenant les points qui violent les bornes de subsamplabilité.
   • L'algorithme applique une fonction de rétrécissement $S$ aux points de $P_{tail}$ pour les forcer dans la nouvelle borne de rayon ($\sqrt{3/7}R$).
3. Analyse de la queue : L'analyse prouve que les points nécessitant un rétrécissement appartiennent à $P_{tail}$, lequel ne constitue qu'une petite fraction ($\approx \beta/m$) de l'ensemble de données. De plus, la suppression ou le rétrécissement de ces points ne dégrade pas de manière significative la borne inférieure de la matrice du second moment des données « bonnes » restantes.
4. Terminaison : La récursion continue jusqu'à ce que le nombre de condition $\kappa$ soit réduit à une constante ($O(m)$). À ce stade, l'ajout de bruit simple suffit pour obtenir une approximation $(1 \pm \gamma)$.

Comparaison avec les références

L'article établit une référence utilisant le cadre Subsample-and-Aggregate (Nissim et al., 2007) combiné aux techniques d'espace métrique semi-convexe d'Ashtiani & Liaw (2022). Cette référence fournit une approximation $(1 \pm 2\alpha)$ mais nécessite une complexité d'échantillonnage nettement plus élevée, particulièrement en présence de valeurs aberrantes.

Contributions clés et résultats

1. Algorithme récursif pour les intrants subsamplables : Les auteurs présentent un algorithme récursif qui parvient à une $(1 \pm \gamma)$-approximation de la matrice du second moment pour tout intrant $(m, \alpha, \beta)$-subsamplable. L'algorithme satisfait $\rho$-zCDP.
2. Gestion des valeurs aberrantes : La méthode est montrée comme étant robuste à une fraction notable de valeurs aberrantes. Plus précisément, pour un mélange d'une distribution bien comportée $D$ et d'une fraction $\eta$ de valeurs aberrantes, l'algorithme réussit à condition que la matrice du second moment des valeurs aberrantes $\Sigma_{out}$ satisfasse $\Sigma_{out} \preceq O(1/\eta)\Sigma_D$.
3. Complexité d'échantillonnage améliorée :
   • Pour les distributions générales (y compris celles à queue lourde), l'algorithme proposé atteint une complexité d'échantillonnage d'environ $\tilde{O}\left(\frac{d}{\gamma^2} + \frac{d^{3/2}}{\gamma\sqrt{\rho}}\right)$.
   • En revanche, la référence Subsample-and-Aggregate nécessite $\tilde{O}\left(\frac{d^2}{\epsilon \gamma^3}\right)$, ce qui est nettement plus élevé, surtout en présence de valeurs aberrantes où l'exigence de la référence sur la fraction de valeurs aberrantes $\eta$ est beaucoup plus stricte ($\eta = O(1/m)$ contre la tolérance de la méthode proposée).
4. Formalisation de la subsamplabilité : L'article fournit une définition rigoureuse de la subsamplabilité et démontre comment elle sert de proxy traçable pour contrôler le comportement de la queue sans nécessendre de strictes hypothèses gaussiennes.

Signification et affirmations

Les auteurs affirment que leur travail comble le fossé entre l'estimation privée pour les entrées bien comportées (gaussiennes) et la réalité plus complexe des distributions générales, potentiellement à queue lourde, avec des valeurs aberrantes.

• Robustesse : L'algorithme est conçu pour l'estimation du second moment dans des régimes avec de grands nombres de condition, là où les méthodes précédentes (telles que Brown et al., 2023) peuvent subir des erreurs significatives si les valeurs aberrantes sont corrélées avec les directions des petites valeurs propres.
• Hypothèses plus faibles : En s'appuyant sur la subsamplabilité plutôt que sur des bornes de score de levier uniformes, la méthode tolère la présence de multiples valeurs aberrantes, à condition qu'elles ne dominent pas le spectre global des sous-échantillons aléatoires.
• Utilité : L'article démontre que des garanties d'utilité fortes (approximation $(1 \pm \gamma)$ arbitraire) sont réalisables même lorsque la plage d'entrée est nettement supérieure à la valeur propre minimale, un scénario où les techniques de DP standard peinent souvent.

Les auteurs notent explicitement que si leur analyse nécessite une borne sur le paramètre $\beta$ (liée à la probabilité d'échec du sous-échantillonnage) dépendant de la plage $R$, il s'agit d'un compromis permettant de gérer des distributions bien comportées avec des valeurs aberrantes. Ils identifient le remplacement de cette dépendance par une borne $O(1)$ comme un problème ouvert intéressant. Le travail ne propose pas de validation expérimentale sur des jeux de données réels, mais fournit des garanties théoriques et des bornes de complexité d'échantillonnage pour des modèles de distribution spécifiques, incluant les distributions de Pareto tronquées et les distributions uniformes sur des ellipsoïdes convexes.