Résumé technique : Échantillonnage adaptatif et écrêtage pour l'optimisation privée du pire cas par groupe

Énoncé du problème

L'article aborde le défi consistant à entraîner des modèles d'apprentissage automatique satisfaisant simultanément deux exigences critiques : l'équité et la vie privée. Plus précisément, les auteurs se concentrent sur l'optimisation du pire cas par groupe (WGO), qui vise à maximiser la précision du groupe démographique le moins performant (critère max-min de Rawls), tout en respectant la confidentialité différentielle (DP) pour protéger les données des utilisateurs.

La littérature existante indique un conflit fondamental entre ces objectifs. La descente de gradient stochastique standard à confidentialité différentielle (DP-SGD) exacerbe souvent les problèmes d'équité, entraînant une précision nettement inférieure pour les groupes minoritaires par rapport à la SGD standard. Bien que des travaux antérieurs aient tenté de atténuer l'injustice induite par la DP ou proposé des algorithmes privés WGO (par exemple, Zhou et Bassily [2024]), ces approches souffrent de limitations pratiques :

1. Atténuation de l'injustice : Les méthodes qui ajustent uniquement les mécanismes internes de la DP-SGD échouent à traiter les scénarios où la SGD standard elle-même est injuste.
2. WGO privé antérieur : Les algorithmes WGO privés existants reposent souvent sur des hypothèses (par exemple, des tailles de groupes équilibrées) qui ne tiennent pas dans les jeux de données réels, ou ils présentent de mauvaises performances expérimentales en raison d'une variance élevée et de stratégies d'échantillonnage inefficaces.

Méthodologie

Les auteurs proposent ASC (Optimisation du groupe au pire cas échantillonnée et écrêtée de manière adaptative), un algorithme pratique conçu pour optimiser la précision du groupe au pire cas sous des contraintes de confidentialité différentielle. L'innovation centrale réside dans le dépassement du simple rééquilibrage des pertes pour modifier fondamentalement les mécanismes d'échantillonnage et d'écrêtage de la DP-SGD.

1. L'algorithme ASC

ASC fonctionne en contrôlant de manière adaptative deux paramètres pour chaque groupe $g$ à chaque étape d'entraînement :

• Échantillonnage adaptatif : Au lieu d'échantillonner un lot uniforme à partir de l'ensemble du jeu de données et de rééquilibrer les gradients (ce qui introduit une variance élevée pour les groupes minoritaires), ASC échantillonne un nombre spécifique de points $m_g$ à partir de chaque groupe $g$ au sein d'un seul lot. La taille du lot pour chaque groupe est proportionnelle au poids actuel du groupe $\lambda_g$ (c'est-à-dire $m_g \approx \lambda_g M$). Cela garantit que la mise à jour attendue correspond directement à l'objectif WGO.
• Écrêtage équilibré : Pour maintenir une garantie de confidentialité cohérente malgré des taux d'échantillonnage variables ($m_g/n_g$), ASC définit de manière adaptative le seuil d'écrêtage des gradients $\xi_g$ pour chaque groupe. Le seuil est calculé de telle sorte que la garantie de confidentialité différentielle de Rényi (RDP) pour l'étape reste fixe à un budget prédéfini $(\alpha, \epsilon_s)$, indépendamment de la taille du groupe ou du taux d'échantillonnage. Cela permet à l'algorithme d'ajouter du bruit à la somme des mises à jour de groupe plutôt qu'aux mises à jour individuelles, réduisant ainsi le bruit total.

2. Lignes de base et comparaisons

L'article évalue ASC par rapport à plusieurs lignes de base :

• DP-SGD : Entraînement privé standard.
• Rééquilibrage de perte DP (DP-LRW) : Une nouvelle ligne de base qui applique la DP-SGD standard mais réévalue les gradients en fonction de l'importance du groupe. Les auteurs notent que cela introduit une variance significative en raison du redimensionnement des gradients.
• aZB (Zhou et Bassily [2024]) : Une méthode WGO privée antérieure qui échantillonne des lots à partir de groupes basés sur des probabilités catégorielles. Les auteurs identifient que cette méthode souffre d'une variance élevée et de garanties de confidentialité médiocres lorsque les tailles de groupes sont déséquilibrées, car le coût de confidentialité est dicté par le plus petit groupe.
• aZB-prop : Une variante de aZB utilisant un échantillonnage proportionnel pour égaliser les garanties de confidentialité, bien qu'elle souffre toujours d'une variance d'échantillonnage élevée.

3. Analyse théorique

Les auteurs fournissent une analyse de convergence pour les algorithmes WGO bruyants, décomposant l'erreur en termes liés au paysage d'optimisation et à la variance d'échantillonnage.

• Le Théorème 3 démontre que ASC présente une variance d'échantillonnage significativement plus faible que aZB et aZB-prop.
• Contrairement à aZB, qui inclut un terme pour la divergence inter-groupe qui ne diminue pas avec la taille du lot, la variance de ASC est uniquement une combinaison pondérée des variances intra-groupe car il échantillonne tous les groupes à chaque étape.
• L'article prouve que ASC satisfait la $(\alpha, \epsilon)$-RDP en composant les garanties des étapes de mise à jour du modèle adaptatif et des étapes périodiques de rééquilibrage des groupes.

Contributions clés

1. Une nouvelle ligne de base : Introduction de DP-LRW, une ligne de base simple et facile à implémenter qui privatise le rééquilibrage des pertes, montrant des améliorations par rapport à la DP-SGD standard mais soulignant les problèmes de variance.
2. L'algorithme ASC : Un algorithme pratique pour le WGO privé qui utilise un échantillonnage stratifié adaptatif et des seuils d'écrêtage adaptatifs. Cette conception permet au modèle de prioriser les groupes plus difficiles à apprendre sans compromettre les garanties de confidentialité ou l'utilité du modèle.
3. Analyse de convergence : Une étude théorique établissant que la variance d'échantillonnage est un différenciateur principal entre les algorithmes WGO, prouvant la stabilité supérieure d'ASC par rapport aux méthodes antérieures.
4. Validation expérimentale : La première comparaison expérimentale complète des algorithmes WGO privés, démontrant que ASC atteint une précision de groupe au pire cas de l'état de l'art sans sacrifier la précision moyenne globale.

Résultats expérimentaux

Les auteurs ont évalué ASC sur trois jeux de données : MNIST déséquilibré (classification de chiffres avec des classes sous-échantillonnées), CelebA (attributs faciaux avec des déséquilibres démographiques) et Fraude de compte bancaire (données tabulaires avec des groupes de fraude/âge).

• Performance : ASC a constamment surpassé toutes les lignes de base. Sur le jeu de données CelebA, ASC a atteint une précision de groupe au pire cas (WGA) 30 % supérieure à la meilleure méthode suivante. Sur MNIST déséquilibré, ASC a atteint 75,2 % de WGA contre 20,4 % pour la DP-SGD standard.
• Variance : Les mesures empiriques ont confirmé l'analyse théorique, montrant qu'ASC présente une réduction d'environ 100 fois de la variance d'échantillonnage par rapport à aZB et aZB-prop.
• Budgets de confidentialité : ASC a maintenu des performances robustes sur une gamme de budgets de confidentialité ($\epsilon \in [0.1, 5]$), tandis que d'autres méthodes (comme DP-SGD-F) n'ont montré d'améliorations significatives qu'à des valeurs $\epsilon$ plus élevées et moins privées.

Signification et affirmations

L'article prétend fournir la première méthode pratique pour imposer simultanément l'équité du groupe au pire cas et la confidentialité différentielle. Les auteurs soutiennent que les approches précédentes étaient soit théoriquement solides mais pratiquement inadaptées (par exemple, échouant sur des données déséquilibrées), soit n'ont pas réussi à traiter les causes profondes de l'injustice dans l'apprentissage privé.

En découplant la stratégie d'échantillonnage du mécanisme de confidentialité par l'écrêtage adaptatif, ASC résout la tension entre la nécessité de surpondérer les groupes minoritaires (pour l'équité) et la nécessité de borner la sensibilité (pour la confidentialité). Les auteurs concluent que leur travail offre un impact sociétal positif en permettant l'entraînement de modèles d'apprentissage automatique équitables et privés, une condition préalable à une IA digne de confiance dans les applications centrées sur l'humain. Ils reconnaissent les limitations fondamentales de la confidentialité concernant les groupes extrêmement petits, mais notent que leur méthode améliore considérablement les lignes de base existantes, même dans ces contextes difficiles.