28 mai 2024
Par Gautam Kamath
Les statistiques et l'apprentissage automatique étant appliqués dans des contextes de plus en plus vastes, nous devons préparer nos méthodes à faire face à des défis de grande ampleur. Certains d'entre eux, comme la collecte de données à partir de sources non fiables ou la déduction d'informations sensibles et personnelles, n'avaient pas été imaginés lors de la création de notre boîte à outils statistiques.
Plus précisément, nous avons besoin de méthodes statistiques qui répondent aux critères suivants :
Sans une attention particulière, la plupart de nos techniques conventionnelles ne parviennent pas à atteindre ces deux objectifs. Cela vaut même pour l'estimation de la moyenne, la plus élémentaire des tâches statistiques. En me concentrant sur ce problème, je discuterai de certains développements récents en matière de robustesse et de confidentialité, en soulignant les liens conceptuels et techniques surprenants entre les deux.
Le problème de base est d'une simplicité déconcertante : étant donné un ensemble de données à d dimensions tirées d'une certaine distribution de probabilités, il faut produire une estimation de la moyenne. Comme hypothèse technique minimale, nous avons besoin que la variance de la distribution soit limitée dans toutes les directions.
Ce problème est assez facile à résoudre : il suffit de prendre la moyenne empirique de l'ensemble des données. Avec un nombre linéaire d'échantillons (une taille d'ensemble de données proportionnelle à d), nous obtenons une estimation précise de la moyenne.
Des problèmes se posent lorsque l'estimateur doit être robuste. Dans ce contexte, nous supposerons qu'une petite quantité (disons 1 % de la taille de l'ensemble de données) de données choisies de manière contradictoire peut être ajoutée à l'ensemble de données (parfois connu sous le nom de 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 cadre robuste peut poser des problèmes aux estimateurs naïfs, même avec un seul point de données corrompu dans une dimension (indice : qu'arrive-t-il à la moyenne empirique lorsque nous ajoutons un point très éloigné ?) Heureusement, pour le cadre unidimensionnel, nous disposons d'autres statistiques robustes, telles que la médiane.
Malheureusement, le tableau est plus sombre dans les contextes de dimension supérieure. L'approche naturelle consiste à essayer de généraliser la médiane dans ces contextes. L'une de ces généralisations est la médiane de Tukey, qui tente de trouver le "point le plus profond dans l'espace" par rapport à l'ensemble de données. Il s'avère qu'elle offre la meilleure garantie de précision que l'on puisse espérer, à ceci près qu'elle est NP-difficile à calculer. En d'autres termes, son calcul prendrait un temps prohibitif, même dans un cadre à 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. Si la médiane géométrique peut être calculée efficacement, elle se heurte à un autre problème : à 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 d'estimation robuste de la moyenne en haute dimension : soit l'estimateur n'est pas efficace en termes de calcul, soit la garantie d'erreur se dégrade au fur et à mesure que la dimension augmente.
Nous avons résolu cette tension dans un travail conjoint avec Ilias Diakonikolas, Daniel Kane, Jerry Li, Ankur Moitra, et Alistair Stewart publié à FOCS 2016. Nous avons donné le premier estimateur robuste pour la moyenne qui simultanément a) est efficace à calculer et b) a une garantie d'erreur indépendante de la dimension, réglant un problème ouvert depuis des décennies dans le domaine. L'algorithme calcule un "centre spectral" de l'ensemble de données : en utilisant des informations spectrales sur l'ensemble de données, il trouve des directions avec une variance plus élevée que prévu, et après avoir projeté sur ces directions, il élimine les points qui ressortent comme des valeurs aberrantes.
Ces travaux ont suscité une vague d'intérêt pour les statistiques en haute dimension, robustes et efficaces sur le plan informatique. Un exemple notable est celui de Samuel B. Hopkins qui, dans un article paru en 2020 dans les Annals of Statistics, introduit le "centre combinatoire". Son travail aborde de la même manière le problème de l'estimation efficace de la moyenne avec des taux sub-gaussiens, montrant ainsi la large applicabilité de ces idées algorithmiques. Mais le lien le plus intéressant reste à venir.
Il a été démontré à maintes reprises que, sans précaution particulière, les statistiques sont susceptibles de laisser filtrer des détails sur des points de données individuels. Cela peut être problématique si les données correspondent à des informations sensibles sur des personnes.
Pour pallier ces problèmes, Cynthia Dwork, Frank McSherry, Kobbi Nissim et Adam Smith ont introduit la définition de la confidentialité différentielle (DP) en 2006. En gros, un algorithme est DP si sa distribution sur les résultats est insensible à l'ajout ou à la suppression de tout point de données de son entrée. D'un point de vue opérationnel, cela signifie que l'on ne peut pas déduire grand-chose sur les points de données d'entrée individuels en examinant la sortie d'un algorithme DP.
Intuitivement, cela ressemble à un type de robustesse. Après tout, tant pour la robustesse que pour la confidentialité, un estimateur ne doit pas être trop sensible à un petit nombre de points dans l'ensemble de données. Cependant, les formalisations pleinement satisfaisantes de ce lien ont été difficiles à trouver.
Comment estimer en privé la moyenne d'une distribution multivariée ? Dans un article de COLT 2020 avec Vikrant Singhal et Jonathan Ullman, nous donnons un estimateur basé sur l'ajout d'un bruit gaussien à la moyenne empirique. Comme cet algorithme simple consiste simplement à ajouter du bruit, il est clairement efficace d'un point de vue informatique. Et il permet d'obtenir l'erreur optimale que l'on peut espérer. Le problème est qu'il ne permet d'obtenir qu'une variante détendue de la confidentialité différentielle, connue sous le nom de confidentialité différentielle (ε,δ) ou de confidentialité approximative. Une variante de cet algorithme ajoute à la place un bruit de Laplace : cet estimateur est à nouveau efficace sur le plan du calcul et permet d'obtenir 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 est basé 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. Cet algorithme offre de fortes garanties de DP et d'erreur optimale, mais l'étape d'échantillonnage le rend inefficace à calculer.
En résumé, nous disposons d'algorithmes qui satisfont à deux des critères suivants :
Existe-t-il un estimateur qui permette de réaliser ces trois objectifs en même temps ?
Dans un travail conjoint avec Hopkins et Mahbod Majid (University of Waterloo MMath '23) à 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 obstacles de calcul associés à 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 combinatoire central de Hopkins : le même que celui utilisé pour obtenir des taux sub-gaussiens, qui est également efficace dans des contextes robustes. Cela montre un lien algorithmique technique inattendu entre la robustesse, les taux sous-gaussiens et la protection de la vie privée.
Peut-on aller plus loin ? Existe-t-il des liens plus généraux entre la robustesse et la protection de la vie privée ? 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 à ICML 2023), nous montrons que c'est le cas : la robustesse implique la confidentialité. En particulier, nous donnons une transformation de 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 des liens conceptuels forts entre la robustesse et la protection de la vie privée. Certaines conversions partielles sont connues (dans un travail classique de STOC 2009 par Dwork et Jing Lei, ainsi que dans un article plus récent de NeurIPS 2022 par Kristian Georgiev et Hopkins), mais aucune ne semble être le mot de la fin sur cette question.
Dans l'ensemble, ces résultats donnent un aperçu de la manière de concevoir des procédures statistiques en tenant compte de considérations importantes telles que la robustesse et la confidentialité. Il est peut-être surprenant de constater que les idées techniques nécessaires dans les deux cas sont assez similaires. Cela laisse entrevoir des liens plus profonds entre les deux domaines, ce qui pourrait nous être utile lorsque nous travaillons à l'élaboration d'algorithmes mieux adaptés aux nombreux défis du monde réel.
