💻 computer science

Metric Differential Privacy at the User-Level Via the Earth Mover's Distance

Cet article initie l'étude de la confidentialité différentielle métrique au niveau de l'utilisateur en utilisant la distance de l'Earth Mover, proposant de nouveaux mécanismes pour les requêtes linéaires et par article, une réduction du cadre non borné vers le cadre borné, et démontrant une utilité améliorée par rapport à la DP standard au niveau de l'utilisateur.

Auteurs originaux : Jacob Imola, Amrita Roy Chowdhury, Kamalika Chaudhuri

Publié 2026-07-07

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jacob Imola, Amrita Roy Chowdhury, Kamalika Chaudhuri

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayiez de protéger les données privées des gens, comme leurs localisations quotidiennes ou leurs messages textuels. Pendant des années, l'étalon-or de la confidentialité a été la Confidentialité Différentielle (Differential Privacy - DP). Pensez à la DP standard comme une couverture de sécurité « taille unique ». Elle traite chaque changement dans un ensemble de données comme étant également dangereux.

Si un utilisateur change sa position de « Maison » à « Travail », la DP standard ajoute une énorme quantité de « bruit » (confusion aléatoire) aux données pour masquer l'information. Mais elle fait exactement la même chose si un utilisateur change sa position de « Maison » à « La maison du voisin d'à côté ». En réalité, le premier changement est important, mais le second est minime. La DP standard ne fait pas la distinction entre les deux, donc elle ajoute souvent trop de bruit, ce qui rend les données moins utiles pour l'analyse.

Ce document présente une approche plus intelligente et plus flexible appelée Confidentialité Différentielle Métrique (Metric DP), spécifiquement adaptée aux données de type « User-Level » (où une seule personne contribue à de nombreux points de données, comme un mois de signaux GPS).

Voici la décomposition de leur nouvelle idée, la Distance de l'Earth Mover (dEM), et son fonctionnement, en utilisant des analogies simples.

L'idée centrale : L'analogie du « déplacement de terre »

Les auteurs utilisent un concept appelé Distance de l'Earth Mover (dEM). Imaginez que vos données sont un tas de terre étalé sur un champ.

La DP standard demande : « Avez-vous déplacé de la terre ? » Si oui, elle panique et ajoute un bruit maximal.
La dEM-DP demande : « Quelle quantité de terre avez-vous déplacée, et à quelle distance l'avez-vous déplacée ? »

Si vous déplacez un minuscule grain de terre d'un pouce, c'est un petit changement. Si vous déplacez un camion entier de terre à travers le champ, c'est un changement énorme. La dEM mesure le coût du déplacement de la terre.

Petit coût = Moins sensible. Le système de confidentialité ajoute moins de bruit.
Grand coût = Plus sensible. Le système de confidentialité ajoute plus de bruit.

Cela permet au système d'être « à grain fin ». Il protège férocement les grands secrets, mais laisse passer les petits détails inoffensifs, ce qui rend les données finales beaucoup plus utiles.

Les trois principales contributions

Le document présente trois outils techniques principaux pour faire fonctionner cela :

1. De nouvelles façons de répondre aux questions (Mécanismes)

Les auteurs ont conçu deux nouvelles méthodes pour répondre aux questions sur les données tout en conservant cette confidentialité de « déplacement de terre ».

Requêtes Linéaires (La question de la « moyenne ») : Imaginez demander : « Quelle est la distance moyenne à laquelle les gens vivent d'un parc spécifique ? » Les auteurs ont créé une façon de répondre à cela qui comprend si la réponse change légèrement (un petit mouvement de terre) ou radicalement (un grand mouvement). Ils ont prouvé que si la question elle-même est « lisse » (ne saute pas de manière sauvage), ils peuvent ajouter beaucoup moins de bruit que les méthodes standards.
Requêtes par élément (La question de la « liste ») : Imaginez publier une liste de tous les mots utilisés par les gens, mais de manière brouillée. Les méthodes standards traiteraient chaque changement de mot comme un risque massif. Les auteurs ont utilisé une astuce ingénieuse appelée « Mélange » (Shuffling).
- Analogie : Imaginez que 100 personnes écrivent chacune une note secrète. Si vous les remettez à un collecteur dans l'ordre, le collecteur sait qui a écrit quoi. Mais si vous jetez toutes les notes dans un mélangeur, que vous les mélangez et que vous donnez le tas, le collecteur voit la collection de notes mais ne peut pas dire quelle note provient de quelle personne.
- Les auteurs ont prouvé que ce « mélange » rend la garantie de confidentialité beaucoup plus forte qu'on ne le pensait auparavant, permettant ainsi moins de bruit et une meilleure qualité de données.

2. Gérer les données « désordonnées » (La Réduction)

Dans le monde réel, les gens ne contribuent pas toujours la même quantité de données. Une personne peut avoir 100 points de localisation ; une autre peut en avoir 10. Les méthodes standards luttent contre ce désordre « non borné ».

La solution : Les auteurs ont créé un traducteur « boîte noire ». Imaginez que vous avez une machine qui ne fonctionne que si tout le monde apporte exactement 10 articles. Les auteurs ont construit un pré-processeur qui prend les 100 articles d'une personne et les réduit aléatoirement à 10, ou prend les 5 articles d'une personne et les augmente jusqu'à 10.
La magie : Ils ont prouvé que ce processus d'échantillonnage ne déforme pas trop la distance de « déplacement de terre ». Cela signifie que vous pouvez utiliser leurs outils simples (conçus pour des groupes de taille égale) sur des données réelles et désordonnées sans briser les règles de confidentialité.

3. Prouver que c'est meilleur (Le gain d'utilité)

Enfin, ils ont analysé les chiffres pour montrer que leur nouvelle méthode fonctionne réellement mieux que l'ancienne méthode « taille unique ».

Le résultat : Pour certains types de questions (comme trouver des moyennes ou compter la fréquence d'apparition de mots), leur méthode produit des données avec moins d'erreur.
Pourquoi ? Parce que la DP standard, ayant peur de tout changement, ajoute tellement de bruit que la réponse devient floue. La dEM-DP réalise que certains changements sont triviaux, elle ajoute donc moins de bruit, gardant la réponse nette et utile.

Exemples concrets du document

Les auteurs utilisent trois scénarios pour expliquer pourquoi cela importe :

Données de localisation :
- Scénario : Un utilisateur passe de « Maison » à « Travail » (un grand changement) vs « Maison » à « La maison d'à côté » (un changement minuscule).
- DP standard : Traite les deux comme étant également dangereux. Ajoute un énorme bruit.
- dEM-DP : Réalise que le mouvement « à côté » est un risque faible. Ajoute un bruit minuscule. Les données restent assez précises pour voir les schémas généraux de trafic sans révéler exactement qui est où.
Données textuelles :
- Scénario : Un utilisateur change sa conversation de « Mathématiques » à « Musique Classique » (un énorme changement sémantique) vs « Algèbre » à « Trigonométrie » (un changement minuscule).
- dEM-DP : Comprend qu'« Algèbre à Trigonométrie » est un petit changement de sens. Il protège l'utilisateur de manière moins agressive, préservant la nuance de la conversation pour l'analyse.
Graphes sociaux (Amis) :
- Scénario : Un utilisateur ajoute un nouvel ami ou change complètement son groupe d'amis.
- dEM-DP : Reconnaît que changer un ami est un petit « mouvement de terre ». Cela permet au système de diffuser des données sur la structure du réseau sans brouiller toute l'image.

L'essentiel

Ce document soutient que nous n'avons pas besoin de traiter chaque changement de données comme une menace nucléaire. En mesurant combien et jusqu'où les données changent (en utilisant la Distance de l'Earth Mover), nous pouvons créer des systèmes de confidentialité qui sont :

Plus intelligents : Ils comprennent la différence entre un grand secret et un petit détail.
Plus utiles : Ils ajoutent moins de « bruit », donc les données sont plus précises.
Plus flexibles : Ils fonctionnent même lorsque les gens contribuent des quantités de données différentes.

C'est comme passer d'un système de sécurité qui verrouille la porte dès qu'une feuille de vent la frappe, à un système qui ne verrouille la porte que lorsqu'un cambrioleur tente de grimper. La maison reste sûre, mais vous n'avez pas à subir le bruit constant du vent.

Résumé Technique : Confidentialité Différentielle Métrique au Niveau de l'Utilisateur via la Distance de l'Earth Mover (dEM)

Énoncé du Problème

La Confidentialité Différentielle (DP - Differential Privacy) est devenue le standard pour l'analyse de données, offrant traditionnellement des garanties de confidentialité uniformes où chaque paire de jeux de données d'entrée est traitée comme étant également sensible. Cependant, dans de nombreuses applications pratiques, les données présentent une hétérogénéité ; par exemple, révéler la ville exacte de résidence d'un utilisateur est plus sensible que de révéler son pays. La Confidentialité Différentielle Métrique (Metric DP) remédie à cela en dégradant la garantie de confidentialité de manière linéaire avec la distance entre les paires d'entrées, permettant une meilleure utilité lorsque les entrées sont similaires.

Alors que les travaux antérieurs sur la Metric DP se sont concentrés sur le cadre de l'item-level (où chaque utilisateur contribue avec un seul élément de donnée), les scénarios du monde réel impliquent souvent des contributions de type user-level (utilisateur), où un seul utilisateur fournit une collection d'éléments (par exemple, un historique de localisations ou un ensemble de mots). Les cadres existants de la DP au niveau de l'utilisateur reposent sur la DP standard, traitant tous les changements apportés à l'ensemble des données d'un utilisateur comme étant également sensibles, indépendamment de la magnitude ou de la nature du changement. Ce papier initie l'étude de la Metric DP au niveau de l'utilisateur, en utilisant spécifiquement la Distance de l'Earth Mover (dEM) comme métrique sous-jacente. L'objectif est de définir une notion de confidentialité où la sensibilité de la contribution d'un utilisateur dépend à la fois de la fraction de données modifiées et de la distance de ces changements, capturant une sémantique de confidentialité plus nuancée que la DP standard au niveau de l'utilisateur.

Méthodologie

1. Définition de la dEM-DP

Les auteurs définissent la dEM-DP en mesurant la distance entre deux jeux de données d'utilisateurs $K$ et $K'$ en utilisant la Distance de l'Earth Mover (également connue sous le nom de distance 1-Wasserstein).

Métrique : $d_{EM}(\tilde{K}, \tilde{K}')$ représente le coût minimum de transport de la distribution de probabilité du jeu de données $K$ vers $K'$ , où le coût est la quantité de données déplacées multipliée par la distance $d_X$ entre les éléments.
Garantie de Confidentialité : Un mécanisme $M$ satisfait la $(\alpha, \delta)$ -bounded dEM-DP si pour tout couple de jeux de données $K, K'$ de même taille :
$\Pr[M(K) \in O] \le e^{\alpha \cdot d_{EM}(\tilde{K}, \tilde{K}')} \Pr[M(K') \in O] + \delta$
Ici, le paramètre de confidentialité varie avec la distance. Si $d_{EM}$ est faible (jeux de données similaires), la garantie de confidentialité est plus forte ( $\epsilon$ effectif plus bas) par rapport à la DP standard, qui appliquerait un $\epsilon$ uniforme.

2. Conception de Mécanismes

Le papier propose deux nouveaux mécanismes pour la publication de requêtes sous dEM-DP, tant dans le Modèle Local (les utilisateurs privatisent leurs données avant l'envoi) que dans le Modèle Central (un agrégateur de confiance détient les données).

A. Requêtes Linéaires (PrivEMDLinear)

Pour les requêtes linéaires de la forme $F\tilde{K}$ , les auteurs analysent la sensibilité sous dEM.

Analyse de Sensibilité : Contrairement à la DP standard qui nécessite que la fonction de requête soit bornée, l'analyse dEM-DP exige que la fonction $f$ (représentant la requête) soit Lipschitzienne continue.
Résultat : Les auteurs prouvent que la sensibilité d'une requête linéaire sous dEM est bornée supérieurement par la constante de Lipschitz de la fonction de requête. Cela permet l'ajout d'un bruit calibré (par exemple, en utilisant le mécanisme K-norm ou le mécanisme Gaussien) qui est proportionnel à la constante de Lipschitz plutôt qu'à une borne globale pessimiste, améliorant ainsi l'utilité.

B. Requêtes par Éléments Non Ordonnés (PrivEMDItemWise)

Pour la publication d'un ensemble de sorties bruitées pour chaque élément d'un jeu de données d'utilisateur (par exemple, un histogramme), le mécanisme applique un mécanisme de base de Metric DP au niveau de l'élément $A$ à chaque élément, puis mélange (shuffle) les résultats.

Amplification de la Confidentialité par Mélange : Les auteurs généralisent le résultat de "l'amplification de la confidentialité par mélange" au cadre de la Metric DP. Puisque la sortie est une liste non ordonnée, un adversaire ne peut pas lier des sorties spécifiques à des indices d'entrée spécifiques.
Nouveauté Technique : Ils prouvent que le mélange de $m$ éléments réduit le coût de confidentialité de $O(m\alpha)$ (via la composition) à $O(\alpha\sqrt{m})$ . Ce résultat est dérivé en analysant le couplage entre les vecteurs d'entrée et en exploitant les propriétés du modèle de mélange.

3. Extension aux Données Non Bornées

Les jeux de données du monde réel ont souvent des tailles variables par utilisateur (cadre non borné), ce qui complique l'analyse dEM car la taille du jeu de données devient elle-même une préoccupation de confidentialité.

Réduction : Les auteurs proposent une réduction boîte noire de la dEM-DP non bornée vers la dEM-DP bornée.
Mécanisme : Ils utilisent l'échantillonnage avec remplacement pour projeter n'importe quel jeu de données d'utilisateur sur une taille fixe $s$ . Ils prouument que cette projection est "lisse", signifiant que la distance dEM entre les jeux de données projetés est proche de la distance dEM entre les jeux de données originaux (à un petit facteur additif près).
dEM-DP Discrète : Pour gérer l'erreur additive provenant de l'échantillonnage, ils introduisent une définition "discrète" de la dEM-DP où les changements avec une distance $\le r$ sont protégés uniformément. Ils démontrent que pour des tailles d'échantillon suffisamment grandes, la dEM-DP non bornée peut être réduite à la dEM-DP bornée avec une perte négligeable de sémantique de confidentialité.

Principales Contributions

Définition de la Metric DP au niveau de l'utilisateur : Le papier établit une définition formelle de la Metric DP au niveau de l'utilisateur en utilisant la Distance de l'Earth Mover, capturant à la fois les aspects spatiaux et de magnitude des changements de données.
Nouveaux Mécanismes :
- PrivEMDLinear : Un mécanisme pour les requêtes linéaires qui exploite la continuité de Lipschitz pour borner la sensibilité, offrant une meilleure utilité que la DP standard au niveau de l'utilisateur pour des types de requêtes spécifiques.
- PrivEMDItemWise : Un mécanisme général pour les requêtes par éléments qui utilise le mélange. Les auteurs fournissent une analyse d'amplification de la confidentialité généralisée montrant une amélioration en $\sqrt{m}$ par rapport aux bornes de composition standard.
Réduction pour le cas Non Borné : Une technique de réduction boîte noire qui convertit les mécanismes dEM-DP bornés en mécanismes non bornés via l'échantillonnage, permettant l'application de ces mécanismes à des jeux de données avec des tailles de contribution d'utilisateur variables.
Améliorations de l'Utilité : L'analyse théorique démontre que les mécanismes dEM-DP peuvent atteindre une utilité strictement meilleure (erreur plus faible) que les bases de la DP au niveau de l'utilisateur pour :
- Requêtes d'Embedding Linéaire : Dans les modèles central et local, particulièrement lorsque le paramètre de confidentialité $\alpha$ peut être supérieur à l' $\epsilon$ standard pour des entrées dissemblables.
- Estimation de Fréquence : Dans le modèle local, l'erreur est améliorée lorsque la taille du domaine et les paramètres de confidentialité satisfont certaines conditions, en tirant parti du fait que seuls les éléments "proches" (au sein de clusters) nécessitent une forte confidentialité.

Résultats et Signification

Le papier affirme que la dEM-DP offre une définition de la confidentialité plus fine qui s'aligne mieux avec les sémantiques de confidentialité du monde réel.

Sémantique de Confidentialité : Dans la DP standard, changer les données d'un utilisateur pour un mois entier est traité avec la même sensibilité que de changer une seule journée. Dans la dEM-DP, le changement d'une seule journée est considéré comme moins sensible (plus petite $d_{EM}$ ), permettant moins de bruit et une utilité plus élevée, tandis que le changement de longue durée reçoit une garantie plus forte.
Gains d'Utilité : Les bornes théoriques montrent que les mécanismes dEM-DP peuvent surpasser les bases de la DP au niveau de l'utilisateur pour les requêtes d'embedding linéaire et l'estimation de fréquence. Par exemple, pour l'estimation de fréquence, la dépendance de l'erreur vis-à-vis de la taille du domaine $k$ et du paramètre de confidentialité est améliorée sous dEM-DP lorsque les données présentent une structure (par exemple, des métriques regroupées).
Généralisabilité : La réduction aux cadres bornés et l'analyse de mélange générale suggèrent que ces techniques peuvent être appliquées largement à divers espaces métriques et types de requêtes au-delà des exemples spécifiques (localisation, texte, graphes) fournis.

Les auteurs positionnent ce travail comme le premier à proposer une définition générale de la Metric DP au niveau de l'utilisateur via la dEM, dépassant les applications textuelles spécifiques pour un cadre applicable à des espaces métriques généraux. Ils soulignent que bien que la dEM-DP soit une relaxation de la DP standard, elle offre un compromis plus pratique pour les applications où la similitude des données est corrélée à la sensibilité.