Par Gautam Kamath
À mesure que les statistiques et l'apprentissage machine s'appliquent à des contextes de plus en plus variés, nous devons adapter nos méthodes pour relever des défis divers. Certains d'entre eux, comme la collecte de données provenant de sources non fiables ou l'interprétation d'informations personnelles sensibles, étaient inimaginables lors de la conception initiale de nos outils statistiques.
Plus précisément, on a besoin de méthodes statistiques qui satisfont aux critères suivants :
- Robustesse : même si les données s'écartent légèrement de nos hypothèses (par exemple, en raison d'une contamination, d'une mauvaise spécification du modèle ou de l'influence d'une partie malveillante), la méthode devrait tout de même produire une solution raisonnable.
- Confidentialité : la méthode ne doit pas produire une solution qui divulgue trop d'informations sur les points de données individuels avec lesquels elle a été fournie.
Sans précautions particulières, la plupart de nos techniques conventionnelles échouent à atteindre ces deux objectifs. Cela reste vrai même pour l'estimation de la moyenne, la plus élémentaire des tâches statistiques. En me concentrant sur ce problème, j'aborderai quelques développements récents en matière de robustesse et de confidentialité, en soulignant les liens conceptuels et techniques surprenants qui les unissent.
Estimation robuste à faible coût de calcul
Le problème fondamental est d'une simplicité trompeuse : étant donné un ensemble de données à d dimensions issu d'une distribution de probabilité, fournir une estimation de la moyenne. Une hypothèse technique minimale est que la variance de la distribution soit bornée dans toutes les directions.
Ce problème est relativement simple à résoudre : il suffit de calculer la moyenne empirique de l'ensemble de données. Avec un nombre linéaire d'échantillons (une taille d'ensemble de données proportionnelle à d), on obtient une estimation précise de la moyenne.
Des problèmes surviennent lorsque l'estimateur doit être robuste. Dans ce contexte, nous supposerons qu'une petite quantité (par exemple, 1 % de la taille de l'ensemble de données) de données choisies de manière adverse peut être ajoutée à l'ensemble de données (ce qu'on appelle parfois le modèle de contamination de Huber en statistique). Néanmoins, l'objectif est d'obtenir une bonne estimation de la moyenne, la précision ne se dégradant que proportionnellement à la quantité de données contaminées.
Il est facile de constater que ce cadre robuste peut poser problème aux estimateurs naïfs, même avec une seule donnée erronée dans une dimension (indice : que devient la moyenne empirique lorsqu’on ajoute une donnée très éloignée de la moyenne ?). Heureusement, dans le cadre unidimensionnel, nous avons des statistiques alternatives robustes, comme la médiane.
Malheureusement, la situation se corse en grande dimension. L'approche naturelle consiste à généraliser la médiane à ces contextes. Une généralisation possible est la médiane de Tukey, qui cherche à 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 possible, sauf qu'elle est NP-difficile à calculer. Autrement dit, son calcul serait prohibitif, même en 10 dimensions. Une autre généralisation courante est la médiane géométrique, qui correspond au point minimisant 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 se heurte à un autre problème : la précision se dégrade rapidement avec l'augmentation de la dimensionnalité. Cette dichotomie s'applique à toutes les méthodes précédentes d'estimation robuste de la moyenne en grande dimension : soit l'estimateur n'est pas efficace en termes de calcul, soit la garantie d'erreur diminue avec l'augmentation de la dimension.
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 proposé le premier estimateur robuste de la moyenne qui, simultanément, a) est efficace à calculer et b) offre une garantie d'erreur indépendante de la dimension, résolvant ainsi un problème ouvert de longue date dans ce domaine. L'algorithme calcule un « centre spectral » de l'ensemble de données : à partir d'informations spectrales, il identifie les directions présentant une variance supérieure à la valeur attendue, puis, après projection sur ces directions, il élimine les points aberrants.
Ces travaux ont suscité un vif intérêt pour les statistiques robustes, efficaces en termes de calcul et de grande dimension. À titre d'exemple notable, dans un article paru en 2020 dans les Annals of Statistics , Samuel B. Hopkins introduit le concept de « centre combinatoire ». Ses travaux abordent le problème de l'estimation efficace de la moyenne avec des taux sous-gaussiens sous un angle similaire, démontrant ainsi la large applicabilité de ces idées algorithmiques. Mais le lien le plus intéressant reste à venir.
Confidentialité et connexions robustes
Il a été démontré à maintes reprises que, sans précautions particulières, les statistiques sont susceptibles de divulguer des informations sur des données individuelles. Cela peut être problématique si ces données concernent des informations sensibles sur des personnes.
Pour remédier à ces problèmes, Cynthia Dwork, Frank McSherry, Kobbi Nissim et Adam Smith ont introduit la définition différentielle de confidentialité (PD) en 2006. En résumé, un algorithme est dit PD si la distribution de ses sorties est insensible à l'ajout ou à la suppression de n'importe quelle donnée d'entrée. Concrètement, cela signifie qu'il est impossible de tirer des conclusions significatives sur les données d'entrée individuelles à partir de la sortie d'un algorithme PD.
Intuitivement, ça semble relever de la robustesse. En effet, pour garantir à la fois 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, des formalisations pleinement satisfaisantes de cette relation demeurent difficiles à établir.
Comment estimer de manière confidentielle la moyenne d'une distribution multivariée ? Dans un article présenté à COLT 2020 avec Vikrant Singhal et Jonathan Ullman, nous proposons un estimateur basé sur l'ajout d'un bruit gaussien à la moyenne empirique. Cet algorithme simple, consistant uniquement en l'ajout de bruit, est clairement efficace en termes de calcul. De plus, il atteint l'erreur optimale. Attention : il n'atteint qu'une forme assouplie de confidentialité différentielle, appelée confidentialité différentielle (ε,δ) ou confidentialité différentielle approximative . Une variante de cet algorithme ajoute un bruit de Laplace : cet estimateur est également efficace en termes de calcul et atteint la notion la plus forte de confidentialité différentielle (confidentialité différentielle pure ou (ε,0)). Cependant, la garantie d'erreur est affaiblie par un facteur dépendant de la dimension. Un autre algorithme présenté dans notre article est basé sur le mécanisme exponentiel : au lieu d'ajouter du bruit, cet algorithme introduit la confidentialité en échantillonnant aléatoirement une solution à partir d'une distribution judicieusement choisie. Il offre une forte confidentialité différentielle et des garanties d'erreur optimales, mais l'étape d'échantillonnage le rend inefficace en termes de calcul.
En résumé, nous avons des algorithmes qui satisfont à deux des propriétés suivantes :
- DP fort
- Erreur optimale
- efficacité du calcul
Existe-t-il un estimateur qui permet d'atteindre ces trois objectifs simultanément ?
Dans le cadre d'un travail conjoint avec Hopkins et Mahbod Majid (MMath '23, Université de Waterloo) présenté à STOC 2022, nous avons répondu par l'affirmative à cette question en concevant un tel algorithme. Nous avons proposé une variante de l'estimateur mentionné précédemment, basée sur le mécanisme exponentiel. Afin de surmonter les difficultés de calcul liées à la procédure d'échantillonnage, nous utilisons des algorithmes d'échantillonnage log-concave efficaces. Mais surtout, notre algorithme repose sur l'algorithme du centre combinatoire de Hopkins : celui-là même qui permet d'obtenir des taux sous-gaussiens et qui s'avère également efficace dans des contextes robustes. Cela révèle un lien technique et algorithmique inattendu entre robustesse, taux sous-gaussiens et confidentialité.
Peut-on aller plus loin ? Existe-t-il des liens plus généraux entre la robustesse et la confidentialité ? Dans un article présenté à STOC 2023 avec Hopkins, Majid et Shyam Narayanan (et simultanément par Hilal Asi, Ullman et Lydia Zakynthinou dans un travail indépendant présenté à ICML 2023), nous démontrons que c’est le cas : la robustesse implique la confidentialité. Plus précisément, nous proposons une transformation boîte noire qui utilise un estimateur robuste pour construire un estimateur privé. Dans bien des cas, l'optimalité de l'estimateur robuste implique l'optimalité de l'estimateur privé. Ce lien révèle des liens conceptuels forts entre robustesse et confidentialité. Certaines réciproques partielles sont connues (dans un article 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 apporter de réponse définitive à cette question.
Globalement, ces résultats permettent de mieux comprendre comment concevoir des procédures statistiques en tenant compte de critères importants tels que la robustesse et la confidentialité. Peut-être étonnamment, les concepts techniques nécessaires dans les deux cas sont assez similaires. Cela suggère des liens plus profonds entre ces deux domaines, ce qui pourrait s'avérer précieux dans le développement d'algorithmes mieux adaptés aux nombreux défis du monde réel.
