Résumé technique : Le prix de la confidentialité de l'apprentissage des risques de queue

1. Énoncé du problème

L'article aborde la question fondamentale de l'impact de la confidentialité différentielle (DP) sur l'apprentissage de la Valeur à Risque Conditionnelle (CVaR), un fonctionnel standard de risque de queue utilisé pour optimiser les performances sur des sous-populations rares ou à pertes élevées.

Dans la minimisation empirique du risque (ERM) standard, l'objectif est la perte moyenne. En revanche, la CVaR se concentre sur la fraction $\tau$ la plus défavorable de la distribution des pertes (où $\tau \in (0, 1]$ est la masse de queue). Le défi central identifié est que les échantillons déterminant l'objectif de la CVaR sont précisément les échantillons de la « queue » à perte élevée. Dans de nombreuses applications, ceux-ci correspondent à des cas rares, atypiques ou minoritaires. Par conséquent, les exigences de robustesse (se concentrer sur la queue) et de confidentialité (protéger les enregistrements individuels) entrent en collision sur les mêmes observations.

L'article vise à caractériser le risque excédentaire minimax de la CVaR sous confidentialité différentielle. Plus précisément, il se demande : quel est le taux de convergence optimal pour l'apprentissage privé de la CVaR, et comment le paramètre de confidentialité $\epsilon$ interagit-il avec la masse de queue $\tau$ et la taille de l'échantillon $n$ ?

2. Méthodologie et cadre

Les auteurs emploient une combinaison d'analyse de sensibilité, de constructions de bornes inférieures minimax et de réductions modulaires pour relier l'apprentissage de la CVaR à la théorie établie de l'optimisation convexe stochastique privée (SCO).

2.1 Analyse de sensibilité

L'analyse commence par établir la sensibilité exacte d'un enregistrement de l'objectif empirique de la CVaR.

• Pour des pertes bornées $\ell \in [0, B]$, la modification d'un seul enregistrement dans l'ensemble de données modifie la CVaR empirique minimisée d'au plus $B \min\{1, 1/(n\tau)\}$.
• Crucialement, la sensibilité évolue avec $1/(n\tau)$ plutôt qu'avec $1/n$. Cela s'explique par le fait que l'objectif empirique de la CVaR moyenne effectivement uniquement sur les $n\tau$ enregistrements de queue informatifs, attribuant à chacun un poids de $1/(n\tau)$.
• Ce calcul de sensibilité dicte l'échelle de bruit requise pour la confidentialité différentielle, suggérant que la « taille d'échantillon effective » pour la confidentialité n'est pas $n$, mais $n\tau$.

2.2 Décomposition du risque

L'article propose une décomposition du risque excédentaire de CVaR privé en deux composantes distinctes :

1. Erreur statistique ordinaire de risque de queue : L'erreur inhérente à l'estimation du risque de queue à partir de $n$ échantillons, qui évolue avec la taille d'échantillon effective $n\tau$.
2. Prix de la confidentialité : L'erreur supplémentaire introduite par la confidentialité différentielle, qui évolue avec la taille d'échantillon de queue privée effective $\epsilon n\tau$.

2.3 Réductions modulaires

Pour l'apprentissage lipschitzien convexe, les auteurs utilisent une approche modulaire :

• Bornes supérieures : Ils réduisent le problème de la CVaR privée à un problème standard de SCO privé via l'objectif soulevé de Rockafellar-Uryasev. Cela transforme la minimisation de la CVaR en une optimisation convexe sur un espace de paramètres soulevé $(w, \eta)$.
• Bornes inférieures : Ils utilisent un théorème de transfert d'échantillons de queue. Ce théorème intègre un problème SCO privé ordinaire avec $m$ échantillons dans un problème de CVaR avec $n$ échantillons, où $m \approx n\tau$. Cela démontre que tout résultat de difficulté pour le SCO privé sur $m$ échantillons se traduit immédiatement par un résultat de difficulté pour la CVaR privée sur $n$ échantillons avec $n\tau$ enregistrements informatifs.

3. Contributions et résultats clés

3.1 Estimation scalaire

Pour le problème de l'estimation privée de la CVaR d'une variable aléatoire scalaire $Z \in [0, B]$, l'article établit un taux minimax complet sous DP pure (et DP approchée pour un petit $\delta$) :
$$\Theta\left( B \min\left\{ 1, \frac{1}{\sqrt{n\tau}} + \frac{1}{\epsilon n\tau} \right\} \right)$$

• Le terme $1/\sqrt{n\tau}$ représente l'erreur statistique.
• Le terme $1/(\epsilon n\tau)$ représente le prix de la confidentialité.
• Signification : Ce résultat prouve que la pénalité de confidentialité évolue avec $1/(\epsilon n\tau)$, et non avec $1/(\epsilon n)$. La borne inférieure tient même lorsque le seuil VaR est connu, isolant la difficulté dans l'estimation privée de la moyenne de la queue.

3.2 Apprentissage de classes finies

Pour une classe d'hypothèses finie de taille $M$, le taux minimax complet est :
$$\Theta\left( B \min\left\{ 1, \sqrt{\frac{\log(2M)}{n\tau}} + \frac{\log(2M)}{\epsilon n\tau} \right\} \right)$$

• Le terme statistique ordinaire évolue avec $\sqrt{\log M / (n\tau)}$.
• Le terme de confidentialité évolue avec $\log M / (\epsilon n\tau)$.
• Cela confirme que la taille d'échantillon effective pour les termes statistiques et de confidentialité est régie par la masse de queue $\tau$.

3.3 Apprentissage lipschitzien convexe

Pour des pertes convexes lipschitziennes sur un ensemble euclidien de diamètre $D$ avec une constante de Lipschitz $G$ :

• Borne supérieure : En utilisant la formulation convexe soulevée et les algorithmes standards de SCO privé, le terme privé évolue comme :
  $$\tilde{O}\left( \frac{(GD + B)\sqrt{d}}{\epsilon n\tau} \right)$$
  (où $\tilde{O}$ cache des facteurs polylogarithmiques).
• Borne inférieure : Via le théorème de transfert d'échantillons de queue, l'article prouve une borne inférieure correspondante (à des facteurs logarithmiques près) :
  $$\tilde{\Omega}\left( \min\{B, GD\} \min\left\{ 1, \frac{1}{\sqrt{n\tau}} + \frac{\sqrt{d}}{\epsilon n\tau} \right\} \right)$$
• Transition de phase : L'apprentissage privé non trivial des risques de queue n'est possible que si la taille d'échantillon de queue privée effective domine la complexité du modèle : $\epsilon n\tau \gg \sqrt{d}$.

3.4 Extension de la sensibilité

L'article étend l'analyse de sensibilité aux risques cohérents à enveloppe bornée généraux. Pour un risque cohérent avec une enveloppe de densité duale bornée par $\kappa$, la sensibilité d'un enregistrement est $B \min\{1, \kappa/n\}$. Pour la CVaR, $\kappa = 1/\tau$. Les auteurs soutiennent que bien que les taux minimax soient prouvés spécifiquement pour la CVaR, le mécanisme de sensibilité suggère une structure de prix de confidentialité similaire pour d'autres risques cohérents à enveloppes bornées.

4. Signification et affirmations

L'article prétend identifier la frontière confidentialité-risque de queue et résoudre les taux minimax pour l'apprentissage privé de la CVaR. Ses contributions principales sont :

1. Identification de la taille d'échantillon effective : Le travail démontre que dans l'apprentissage des risques de queue, la taille d'échantillon pertinente pour l'estimation statistique et la protection de la confidentialité est $n\tau$, et non $n$. Le prix de la confidentialité est inversement proportionnel au nombre d'enregistrements de queue informatifs.
2. Complétude de la décomposition : Pour les cas scalaire et de classes finies, l'article fournit une décomposition « fermée » de l'erreur en un terme statistique et un terme de confidentialité, montrant que le prix de la confidentialité est intrinsèque et inévitable.
3. Modularité : Les résultats séparent la géométrie spécifique de la CVaR (le facteur $1/\tau$) de la géométrie générale de l'optimisation convexe privée. Cela permet d'appliquer directement les résultats existants du SCO privé à la CVaR avec un simple redimensionnement de la taille de l'échantillon.
4. Distinction par rapport à l'estimation des quantiles : L'article clarifie que l'apprentissage privé de la CVaR est distinct de l'estimation privée des quantiles. Même si le seuil VaR est connu, la difficulté d'estimer la moyenne de la queue de manière privée persiste, entraînée par la sensibilité des enregistrements de queue.

Les auteurs concluent que le facteur d'inverse de la masse de queue $1/\tau$ est le prix de confidentialité intrinsèque de l'apprentissage des risques de queue. Les résultats montrent que la protection d'événements rares à fort impact (la queue) sous confidentialité différentielle entraîne un coût qui évolue linéairement avec la rareté de ces événements ($1/\tau$), modifiant fondamentalement les exigences de complexité d'échantillonnage par rapport à l'apprentissage des risques moyens.