28 mai 2024
Par Gautam Kamath
À mesure que les statistiques et l’apprentissage automatique sont appliqués dans des contextes de plus en plus vastes, nous devons préparer nos méthodes pour faire face à des défis de plus grande envergure. Certaines — comme recueillir des données à partir de sources non fiables ou tirer des inférences à partir d’informations sensibles et personnelles — n’étaient pas imaginées lorsque notre boîte à outils statistiques a été créée à l’origine.
Plus précisément, nous avons besoin de méthodes statistiques qui répondent aux critères suivants :
Sans un soin particulier, la plupart de nos techniques conventionnelles échouent à ces deux objectifs. Cela est vrai même pour l’estimation moyenne, la tâche statistique la plus basique. En me concentrant sur ce problème, je vais discuter de quelques développements récents en matière de robustesse et de confidentialité, en mettant en lumière les liens conceptuels et techniques surprenants entre les deux.
Le problème central est trompeusement simple : étant donné un ensemble de données de dimension d tiré d’une distribution de probabilité, on obtient une estimation de la moyenne. Comme hypothèse technique minimale, il faut que la variance de la distribution soit bornée dans toutes les directions.
Ce problème est assez facile à résoudre : il suffit de prendre la moyenne empirique de l’ensemble de données. Avec seulement un nombre linéaire d’échantillons (une taille de jeu de données proportionnelle à d), on obtient une estimation précise de la moyenne.
Les problèmes surviennent lorsque l’estimateur doit être robuste. Dans ce contexte, nous supposerons qu’une petite quantité (disons 1% de la taille du jeu de données) de données choisies par l’adversaire peut être ajoutée à l’ensemble de données (parfois appelé modèle de contamination de Huber en statistique). Néanmoins, l’objectif est d’obtenir une bonne estimation de la moyenne, où la précision ne se dégrade que proportionnellement à la quantité de données contaminées.
Il n’est pas difficile de voir que ce réglage robuste peut poser problème aux estimateurs naïfs, même avec un seul point de données corrompu dans une dimension (indice : que se passe-t-il avec la moyenne empirique quand on ajoute un point très loin?). Heureusement, pour le contexte unidimensionnel, nous disposons de statistiques alternatives robustes, comme la médiane.
Malheureusement, l’image est plus floue dans les décors de haute dimension. L’approche naturelle consiste à tenter de généraliser la médiane pour ces contextes. Une généralisation est la médiane de Tukey, qui tente de trouver le « point le plus profond dans l’espace » par rapport au jeu de données. Il s’avère qu’il offre la meilleure garantie de précision qu’on puisse espérer — avec la réserve qu’il est NP-difficile à calculer. En d’autres termes, il faudrait un temps prohibitif à calculer, même dans un contexte à 10 dimensions. Une autre généralisation populaire est la médiane géométrique, qui est le point dans l’espace qui minimise la somme des distances L2 aux points de l’ensemble de données. Bien que la médiane géométrique puisse être calculée efficacement, elle rencontre un problème différent : à mesure que la dimensionnalité du problème augmente, la précision se dégrade rapidement. Cette dichotomie s’applique à toutes les méthodes précédentes pour l’estimation robuste de la moyenne en haute dimension : soit l’estimateur n’est pas efficace sur le plan informatique, soit la garantie d’erreur se dégrade à mesure que la dimension augmente.
Nous avons résolu cette tension lors d’un travail conjoint avec Ilias Diakonikolas, Daniel Kane, Jerry Li, Ankur Moitra et Alistair Stewart, publié à la FOCS 2016. Nous avons donné le premier estimateur robuste pour la moyenne qui simultanément a) est efficace à calculer et b) bénéficie d’une garantie d’erreur indépendante de la dimension, réglant ainsi un problème ouvert vieux de plusieurs décennies dans le domaine. L’algorithme calcule un « centre spectral » de l’ensemble de données : en utilisant l’information spectrale sur le jeu de données, il trouve des directions avec une variance supérieure à ce qu’on attendait, et après avoir projeté sur ces directions, il écarte les points qui ressortent comme des valeurs aberrantes.
Ce travail a suscité un vif d’intérêt pour les statistiques robustes, efficaces en calcul et à haute dimension. À titre d’exemple notable, dans un article des Annals of Statistics de 2020, Samuel B. Hopkins introduit le « centre combinatoire ». Son travail adopte une perspective similaire au problème de l’estimation moyenne efficace avec des taux sub-gaussiens, montrant la large applicabilité de ces idées algorithmiques. Mais la connexion la plus intéressante reste à venir.
Il a été démontré à plusieurs reprises que, sans une attention particulière, les statistiques ont tendance à divulguer des détails sur des points de données individuels. Cela peut poser problème si les données correspondent à des informations sensibles sur des personnes.
Pour atténuer ces problèmes, Cynthia Dwork, Frank McSherry, Kobbi Nissim et Adam Smith ont introduit la définition de la vie privée différentielle (DP) en 2006. En gros, un algorithme est DP si sa distribution sur les sorties est insensible à l’ajout ou à la suppression de tout point de données de son entrée. Opérationnellement, cela implique qu’on ne peut pas déduire grand-chose sur les points de données d’entrée individuels en regardant la sortie d’un algorithme DP.
Intuitivement, cela ressemble à une forme de robustesse. Après tout, pour la robustesse et la confidentialité, un estimateur ne devrait pas être trop sensible à un petit nombre de points dans l’ensemble de données. Cependant, les formalisations pleinement satisfaisantes de cette connexion ont été insaisissables.
Comment estimez-vous en privé la moyenne d’une distribution multivariée? Dans un article COLT 2020 avec Vikrant Singhal et Jonathan Ullman, nous donnons un estimateur basé sur l’ajout du bruit gaussien à la moyenne empirique. Puisque cet algorithme simple n’est qu’une addition de bruit, il est clairement efficace sur le plan informatique. Et elle atteint l’erreur optimale qu’on peut espérer. La mise en garde : il n’atteint qu’une saveur détendue de DP, connue sous le nom de confidentialité différentielle (ε,δ), ou DP approximatif . Une variante de cet algorithme ajoute plutôt le bruit de Laplace : cet estimateur est à nouveau efficace en calcul et atteint la notion la plus forte de DP (confidentialité pure, ou (ε,0)-différentielle). Cependant, la garantie d’erreur est affaiblie par un facteur dépendant de la dimension. Un autre algorithme de notre article repose sur le mécanisme exponentiel : plutôt que d’ajouter du bruit, cet algorithme introduit la confidentialité en échantillonnant aléatoirement une solution à partir d’une distribution judicieusement choisie. Cela offre de fortes garanties de DP et d’erreur optimale — mais l’étape d’échantillonnage rend le calcul inefficace.
Pour résumer, nous avons des algorithmes qui bénéficient de deux des éléments suivants :
Existe-t-il un estimateur qui réalise les trois en même temps?
Dans un travail conjoint avec Hopkins et Mahbod Majid MMath '23 de l’Université de Waterloo lors du STOC 2022, nous avons répondu à cette question par l’affirmative, en concevant un tel algorithme. Nous avons donné une variante de l’estimateur mentionné précédemment basée sur le mécanisme exponentiel. Pour surmonter les barrières computationnelles antérieures associées à la procédure d’échantillonnage, nous utilisons des algorithmes pour un échantillonnage log-concave efficace. Mais surtout, au cœur de notre algorithme, nous employons l’algorithme du centre combinatoire de Hopkins : le même que celui utilisé pour obtenir des taux sub-gaussiens, qui est aussi efficace dans des contextes robustes. Cela montre un lien algorithmique technique inattendu entre la robustesse, les taux sub-gaussiens et la confidentialité.
Peut-on aller plus loin? Existe-t-il des liens plus généraux entre robustesse et intimité? Dans un article STOC 2023 avec Hopkins, Majid et Shyam Narayanan (et, simultanément, par Hilal Asi, Ullman et Lydia Zakynthinou dans un travail indépendant à l’ICML 2023), nous montrons que c’est le cas : la robustesse implique la vie privée. En particulier, nous donnons une transformation boîte noire qui utilise un estimateur robuste pour construire un estimateur privé. Dans de nombreux cas, l’optimalité de l’estimateur robuste implique l’optimalité de l’estimateur privé. Cette connexion montre de forts liens conceptuels entre robustesse et vie privée. Quelques converses partielles sont connues (dans un travail classique du STOC 2009 de Dwork et Jing Lei, ainsi qu’un article plus récent de NeurIPS 2022 par Kristian Georgiev et Hopkins), mais aucun ne semble être le dernier mot sur ce sujet.
Dans l’ensemble, ces résultats offrent un aperçu de la façon de concevoir des procédures statistiques sous des considérations importantes comme la robustesse et la confidentialité. Peut-être de façon surprenante, les idées techniques nécessaires dans les deux cas sont assez similaires. Cela suggère des liens plus profonds entre les deux domaines, ce qui pourrait nous être utile alors que nous travaillons vers des algorithmes mieux adaptés aux nombreux défis du monde réel.
