Résumé technique : Apprentissage modal non paramétrique différentiellement privé avec applications à la régression et au partitionnement

Énoncé du problème

L'estimation des modes de densité — les maximisateurs locaux d'une fonction de densité de probabilité — est un problème fondamental en statistique, offrant des résumés localisés et interprétables de distributions complexes et multimodales. Contrairement aux résumés globaux (ex. : moyenne ou médiane), les modes révèlent des sous-populations hétérogènes et sont critiques dans des applications allant du partitionnement (clustering) et de la classification à la vision par ordinateur et à la régression non paramétrique. Cependant, la récupération des modes est intrinsèquement non régulière ; de petites perturbations de la densité peuvent créer ou détruire des points critiques, rendant l'estimation sensible à la lissité locale, à la courbure et à la séparation.

Bien qu'il existe des recherches significatives sur les méthodes différentiellement privées (DP) pour les moyennes, la régression et le partitionnement, l'estimation privée des modes reste largement inexplorée. Les approches existantes, telles que la méthode basée sur les plus proches voisins de Pacchiano et al. (2021), sont limitées aux contextes à mode unique ou manquent de garanties d'optimalité dépendantes de la lissité. Cet article traite du défi de la récupération de multiples modes de densité à partir de données sensibles tout en fournissant des garanties rigoureuses de confidentialité $(\varepsilon, \delta)$-différentielle.

Méthodologie : DP-GRAMS

Les auteurs proposent DP-GRAMS (Differentially Private GRadient Ascent for Mode Seeking), un algorithme à plusieurs étapes qui adapte la procédure classique de mean-shift à un contexte différentiellement privé. La méthode exploite l'équivalence entre le mean shift et l'ascension de gradient sur le log-densité (fonction de score).

1. Estimation de score stabilisée

Pour garantir la confidentialité, l'algorithme ne travaille pas directement sur le gradient du log-densité brut $\nabla \log \hat{p}(x)$, qui peut être très sensible aux observations extrêmes. Au lieu de cela, il emploie un estimateur de score stabilisé :
$$\hat{s}_{A, p_{floor}}(x) = \frac{\text{clip}_A(\nabla \hat{p}(x))}{\max\{\hat{p}(x), p_{floor}\}}$$
où $\hat{p}(x)$ est un estimateur de densité par noyau (KDE). Le numérateur est tronqué (clipped) à un niveau $A$ pour limiter la sensibilité, et le dénominateur est plafonné à une valeur minimale $p_{floor}$ pour éviter la division par des valeurs proches de zéro.

2. Pipeline à trois étapes

L'algorithme procède en trois phases distinctes :

• Initialisation Privée Sensible à la Densité (DAP - Density-Aware Private) :
  Trouver des modes nécessite une bonne initialisation. Les auteurs introduisent un schéma DAP qui échantillonne des points initiaux à partir d'une grille publique. Il utilise le mécanisme exponentiel avec une fonction d'utilité basée sur la masse empirique locale (approximant la densité locale). Crucialement, il emploie une règle de suppression locale : après la sélection d'une ancre, tous les points de la grille situés dans un rayon $\rho_{init}$ sont retirés de l'ensemble des candidats. Cela garantit une couverture diversifiée des régions de haute densité (bassins modaux) sans sélectionner de manière répétée le même voisinage, atteignant une couverture à haute probabilité de tous les vrais modes avec $k \asymp M \log n$ tirages.

• Ascension de Gradient Bruitée Corrélée :
  À partir de chaque initialisation, l'algorithme effectue une ascension de gradient stochastique sur l'estimateur de score stabilisé. Pour satisfaire la confidentialité :

  • Troncation du Gradient (Gradient Clipping) : Les contributions du score sont tronquées.
  • Bruit Correlé : Puisque de multiples trajectoires partent de points différents mais peuvent converger vers le même mode, l'ajout de bruit indépendant à chaque trajectoire engendrerait un coût de confidentialité prohibitif. Au lieu de cela, DP-GRAMS ajoute un bruit gaussien corrélé à chaque itération. La structure de corrélation est induite par un noyau exponentiel basé sur la proximité spatiale des itérés actuels. Cela permet la libération conjointe de multiples trajectoires sous un seul budget de confidentialité.

• Fusion (Merging) :
  L'étape finale fusionne les candidats modes proches produits par les trajectoires d'ascension. Si le nombre de modes est inconnu, une fusion basée sur un rayon est utilisée ; si le nombre est connu, le partitionnement agrégatif par liaison de Ward (Ward-linkage) est appliqué. Cette étape de post-traitement est déterministe et ne consomme pas de budget de confidentialité supplémentaire.

3. Extensions

Le cadre est étendu à deux tâches en aval :

• DP-PMS : Une méthode de régression modale privée qui se met à jour dans la direction de la réponse pour estimer les modes conditionnels.
• DP-GRAMS-C : Un pipeline de partitionnement qui libère des centres modaux privés et assigne les points de données de manière déterministe.

Contributions Théoriques

L'article établit des garanties statistiques et de confidentialité rigoureuses sous l'hypothologie que la densité réelle appartient localement à une classe de Hölder avec un paramètre de lissage $\beta > 2$.

Garanties de Confidentialité

Le pipeline complet de DP-GRAMS satisfait la confidentialité $(\varepsilon, \delta)$-différentielle. Le budget de confidentialité est réparti entre l'initialisation ($\varepsilon_{init}$) et les étapes d'ascension ($\varepsilon_{modes}$). L'utilisation du mécanisme exponentiel pour l'initialisation et du mécanisme gaussien corrélé pour l'ascension garantit que le coût de confidentialité évolue efficacement avec le nombre de modes et les itérations.

Taux d'Erreur et Optimalité

Les auteurs dérivent des bornes supérieures sur l'erreur quadratique moyenne (MSE) des modes estimés. Le taux d'erreur prend la forme :
$$O\left( \left(\frac{\log n}{n}\right)^{\frac{2(\beta-1)}{d+2\beta}} \right) + O\left( \left(\frac{\text{polylog}(n, \delta)}{n^2 \varepsilon^2}\right)^{\frac{\beta-1}{d+\beta}} \right)$$

• Le premier terme représente l'erreur statistique non privée, correspondant aux taux minimax connus pour l'estimation de mode (ex. : Tsybakov, 1990).
• Le second terme capture la dégradation due aux contraintes de confidentialité.

De plus, l'article dérive des bornes inférieures minimax pour l'estimation de mode privée, montrant que les estimateurs proposés sont presque optimaux au sens minimax, à des facteurs logarithmiques près dans la MSE. C'est un résultat significatif, car il démontre que le coût de la confidentialité ne modifie pas fondamentalement la dépendance du taux de convergence vis-à-vis de la taille de l'échantillon $n$ et de la dimension $d$, à condition que la densité soit suffisamment lisse.

Résultats Expérimentaux

Des expériences approfondies sur des données synthétiques et réelles valident les conclusions théoriques :

• Données Synthétiques : Sur des mélanges gausiens bivariés et des mélanges $t$ à queues lourdes, DP-GRAMS parvient à récupérer plusieurs modes. Les courbes de compromis confidentialité-utilité montrent que la méthode est compétitive avec le mean shift non privé, particulièrement à mesure que la taille de l'échantillon $n$ et le budget de confidentialité $\varepsilon$ augmentent.
• Régression Modale : Sur des données de mélange sinusoïdales et à constantes par morceaux, la régression modale privée (DP-PMS) suit avec succès des structures conditionnelles multimodales que les méthodes basées sur la moyenne (comme LOWESS) ne parviennent pas à capturer.
• Partitionnement (Clustering) : Sur les jeux de données MNIST et Cancer RNA-Seq, DP-GRAMS-C démontre des performances supérieures en indice de Rand ajusté (ARI) et en information mutuelle normalisée (NMI) par rapport au $k$-moyennes privé (DP-$k$-Means), particulièrement pour des budgets de confidentialité modérés. La méthode préserve efficacement la géométrie des clusters dans les espaces réduits de haute dimension.

Signification et Revendications

L'article affirme fournir le premier cadre complet pour l'estimation de mode non paramétrique différentiellement privée qui :

1. Gère les multiples modes : Contra à les travaux antérieurs focalisés sur les modes uniques ou les approches de plus proches voisins, cette méthode est conçue pour récupérer un ensemble de modes séparés.
2. Atteint une quasi-optimalité : En utilisant des noyaux d'ordre supérieur et en exploitant la lissité ($\beta > 2$), la méthode atteint des taux d'erreur presque optimaux au sens minimax, dépassant les limites des estimateurs de plus proches voisins qui ne peuvent exploiter la lissité d'ordre supérieur.
3. Mécanismes de Confidentialité Pratiques : L'introduction de l'initialisation DAP et des mécanismes de bruit corrélé offre une solution pratique à la tension entre le besoin d'une distribution granulaire des données (pour trouver les modes) et l'exigence de protéger les données individuelles.
4. Utilité en Aval : Le cadre s'étend naturellement à la régression modale et au partitionnement, fournissant une approche unifiée pour les tâches non paramétriques sous contraintes de confidentialité.

Les auteurs concluent que bien que le problème de l'estimation de mode privée soit difficile en raison de la nature non régulière des points critiques, l'algorithme DP-GRAMS proposé offre une solution statistiquement saine et pratiquement implémentable avec des compromis confidentialité-utilité favorables.