Computationally tractable robust differentially private mean estimation

Résumé Technique : Estimation de la Moyenne Robuste et Différentiellement Privée de Complexité Calculatoire Traitable

Énoncé du Problème
L'article traite du défi consistant à estimer la moyenne d'une distribution de grande dimension sous deux contraintes simultanées : la confidentialité différentielle (DP) et la robustesse aux valeurs aberrantes. Le cadre implique un échantillon de $n$ vecteurs dans $\mathbb{R}^d$ tirés d'une distribution elliptique inconnue $\nu = EC(\mu, \Sigma, F)$, qui est sujette à une contamination $\eta$. Dans ce modèle, un adversaire remplace jusqu'à $\lfloor \eta n \rfloor$ observations par des valeurs arbitraires pouvant dépendre de l'échantillon original. L'objectif est d'estimer la moyenne de la population $\mu$ tout en satisfaisant la confidentialité différentielle à concentration nulle (zCDP) et en maintenant une précision statistique malgré des distributions à queues lourdes et une contamination adversaire.

Les méthodes existantes dans ce domaine font face à des compromis importants. De nombreux estimateurs privés robustes reposent sur des techniques calculatoirement intensives telles que les méthodes de Monte Carlo par chaînes de Markov (MCMC), les relaxations de sommes de carrés ou l'optimisation par gradient, ce qui les rend peu pratiques pour les données de grande dimension. D'autres, bien qu'efficaces, reposent souvent sur une confidentialité différentielle approximative ou manquent de garanties de robustesse sous des notions de confidentialité fortes comme la DP pure ou à concentration nulle. De plus, de nombreuses approches existantes nécessitent le réglage de paramètres difficiles à interpréter ou dont la mise à l'échelle se fait mal avec la dimension.

Méthodologie : La Moyenne Ballon (Balloon Mean)
Les auteurs proposent un nouvel estimateur, la moyenne ballon, qui évite les sous-programmes d'optimisation complexes au profit de simples opérations d'algèbre linéaire. L'algorithme opère de manière itérative, alternant entre deux étapes :

1. Mise à jour de la moyenne (Projection et Moyennage Bruité) : Étant donné une estimation actuelle du centre $\tilde{\mu}_{m-1}$ et un rayon $\tilde{R}_{m-1}$, l'algorithme projette tous les points de données sur le ballon de Mahalanobis $B_{\tilde{R}_{m-1}, \Sigma}(\tilde{\mu}_{m-1})$. Il calcule ensuite la moyenne de l'échantillon de ces projections et ajoute un bruit gaussien calibré à la sensibilité de la projection (qui dépend du rayon). Cela produit une nouvelle estimation privée de la moyenne $\tilde{\mu}_m$.
2. Mise à jour du Ballon (Expansion Privée du Rayon) : L'algorithme « gonfle » le ballon centré sur la nouvelle estimation $\tilde{\mu}_m$ jusqu'à ce qu'il contienne une fraction cible $\tau_m$ des données. Ceci est réalisé à l'aide d'une version privée de l'algorithme AboveThreshold. L'algorithme interroge une séquence de rayons définis par une grille géométrique ($R_{min} + \beta^i - 1$) et compte de manière privée combien de points tombent à l'intérieur de chaque rayon. Il s'arrête au premier rayon où le compte bruité dépasse un seuil bruité correspondant à la fraction cible $\tau_m$.

Le processus se répète pour $M$ itérations. L'estimation finale est la moyenne des projections sur le ballon final. La méthode repose sur quelques paramètres de réglage interprétables : le rayon initial, le facteur d'expansion de la grille $\beta$, le nombre d'itérations $M$, et la fraction cible $\tau$.

Contributions Clés

1. Innovation Algorithmique : L'introduction de la moyenne ballon, un estimateur calculatoirement efficace qui localise itérativement la moyenne en identifiant de manière privée des ballons de Mahalanobis contenant le gros des données. Elle évite le MCMC, les sommes de carrés et la descente de gradient.
2. Garanties Théoriques : L'article fournit des bornes d'erreur en échantplon fini pour la moyenne ballon sous des modèles à queues lourdes (où seul le second moment existe) et des modèles elliptiques contaminés de manière adversaire. L'analyse suppose une matrice de covariance $\Sigma$ connue (bien que les auteurs notent qu'une estimation privée robuste de $\Sigma$ puisse être substituée).
3. Confidentialité et Complexité : L'estimateur satisfait la confidentialité différentielle à concentration nulle $\rho$-zCDP avec une extension naturelle vers la DP pure. La complexité calculatoire est de $O(d^3 + nd^2 + Mnd + Mn \log n)$, ce qui se réduit à $O(nd^2)$ sous des hypothèses standards ($n > d$ et $M < \log n$).

Résultats Théoriques
Le principal résultat théorique (Théorème 4.4) établit une borne supérieure sur l'erreur de Mahalanobis $|\tilde{\mu}_M - \mu|_\Sigma$. Avec une probabilité élevée, l'erreur suit l'échelle :
$$\sqrt{\frac{d}{n(\rho_- \wedge 1)}} + \sqrt{d\eta} + \sqrt{\frac{\log(\dots)}{n}}$$
où $\rho_-$ est le budget de confidentialité alloué par itération.

• Cadre à Queues Lourdes ($\eta=0$) : L'estimateur atteint le taux de convergence optimal au sens de la minimaxité, à des facteurs logarithmiques près.
• Contamination Adversaire ($\eta > 0$) : L'erreur inclut un terme évoluant en $\sqrt{d\eta}$. Les auteurs notent que bien que les bornes inférieures existantes suggèrent qu'une dépendance en $\sqrt{\eta}$ (indépendante de $d$) pourrait être atteignable, la dépendance actuelle en $\sqrt{d}$ est probablement structurelle en raison de l'incapacité de l'algorithme à traiter explicitement les contaminants placés le long d'une direction unique dans des coques de grande dimension. Ils reconnaissent cette lacune mais soulignent qu'aucun algorithme existant ne parvient simultanément à une dépendance optimale de la contamination, une confidentialité forte et une efficacité calculatoire.

Évaluation Empirique
Des simulations approfondies à travers différentes dimensions ($d \in \{2, \dots, 128\}$), tailles d'échantillons et budgets de confidentialité ($\rho \in \{0.01, 1\}$) démontrent les performances de la méthode :

• Robustesse : La moyenne ballon surpasse significativement les autres estimateurs privés calculatoirement tractables (tels que COINPRESS, les estimateurs M de Huber privés et les moyennes optimales par instance) dans les contextes contaminés et à queues lourdes.
• Sensibilité aux Paramètres : La méthode présente une faible sensibilité à l'estimation initiale de la moyenne, au rayon initial et à la taille de la grille $\beta$. Le paramètre $\tau$ agit comme un contrôle de robustesse ; des valeurs plus petites de $\tau$ (excluant moins de données) améliorent les performances dans les contextes contaminés mais peuvent légèrement augmenter l'erreur dans les contextes sains.
• Nombre d'Itérations : L'erreur se stabilise après 3 à 4 itérations, suggérant que $M=4$ est suffisant pour la plupart des applications pratiques.

Signification et Revendications
L'article positionne la moyenne ballon comme une solution pratique au « trilemme » de la robustesse, de la confidentialité et de la tractabilité calculatoire. Les auteurs affirment que, bien que la méthode puisse ne pas atteindre la dépendance théoriquement optimale de la contamination pour les contextes adversaires (en raison de limitations structurelles), elle offre une combinaison unique de :

1. Simplicité Calculatoire : Elle est implémentable en haute dimension sans optimisation complexe.
2. Confidentialité Forte : Elle satisfait la zCDP, une notion de confidentialité plus forte que la DP approximative souvent utilisée dans les contextes robustes.
3. Optimalité Statistique : Elle atteint les taux minimax dans le cadre à queues lourdes et fournit des performances robustes dans les contextes contaminés là où d'autres méthodes efficaces échouent.

Les auteurs concluent que la moyenne ballon est un outil viable pour l'estimation de la moyenne privée dans des scénarios réels impliquant des données de grande dimension, potentiellement à queues lourdes et contaminées, offrant un équilibre entre garanties théoriques et faisabilité pratique.