Byzantine-Robust and Differentially Private Federated Optimization under Weaker Assumptions

1. Problématique

L'apprentissage fédéré (Federated Learning - FL) permet à des clients hétérogènes d'entraîner un modèle commun sans partager leurs données brutes. Cependant, ce paradigme fait face à deux défis majeurs qui menacent sa fiabilité et sa confidentialité :

• Vulnérabilité aux attaques Byzantines : Des clients malveillants peuvent envoyer des mises à jour de modèles arbitraires pour saboter l'entraînement (ex: attaques par manipulation de gradients).
• Fuites de confidentialité : Les gradients et les paramètres du modèle peuvent révéler des informations sensibles sur les données d'entraînement (attaques par inférence de membre, inversion de gradients).

La Privacité Différentielle (DP) est la méthode standard pour protéger les données, mais elle nécessite l'ajout de bruit, ce qui peut dégrader la convergence. De plus, combiner la robustesse aux attaques byzantines et la DP dans un même cadre est complexe car les deux objectifs entrent souvent en conflit (le bruit de la DP peut masquer les attaques byzantines, et les mécanismes de robustesse peuvent amplifier le bruit).

Limites des travaux existants : La plupart des algorithmes actuels qui tentent de résoudre ces deux problèmes simultanément reposent sur des hypothèses théoriques irréalistes, telles que :

• Des gradients bornés (hypothèse souvent fausse, même pour des fonctions quadratiques simples).
• L'accès à un jeu de données auxiliaire côté serveur.
• Des règles d'agrégation spécifiques ou restrictives.
• Des analyses basées uniquement sur l'espérance (in-expectation) plutôt que sur des garanties à haute probabilité.

2. Méthodologie : Byz-Clip21-SGD2M

Les auteurs proposent un nouvel algorithme nommé Byz-Clip21-SGD2M. Il s'agit d'une méthode d'optimisation stochastique qui intègre de manière synergique plusieurs mécanismes pour gérer le bruit de la DP et les attaques byzantines tout en relaxant les hypothèses théoriques.

Les composants clés de l'algorithme sont :

• Double Momentum (Double Momentum) :
  • Un tampon de momentum côté client ($v_i$) pour lisser le bruit des mini-batches locaux.
  • Un tampon de momentum côté serveur ($m_i$) pour contrer l'accumulation du bruit de la DP dans les mises à jour agrégées.
• Mécanisme de Clipping (Troncature) :
  • Les mises à jour sont tronquées (clipping) selon une norme seuil $\tau$ avant d'ajouter le bruit de la DP. Cela garantit une sensibilité bornée, condition nécessaire pour la garantie de privacité différentielle locale.
  • Le clipping agit également comme un compresseur contractif, aidant à contrôler la dérive des clients.
• Rétroaction d'Erreur (Error Feedback - EF) :
  • Inspiré de EF21, un mécanisme de rétroaction est utilisé côté client pour compenser le biais introduit par le clipping et l'hétérogénéité des données, permettant la convergence même sans hypothèse de gradients bornés.
• Agrégation Robuste :
  • Le serveur utilise une règle d'agrégation robuste (satisfaisant la définition de [Allouah et al., 2023a], comme la médiane coordonnée ou la médiane géométrique) pour filtrer les mises à jour malveillantes des clients byzantins.

Hypothèses de travail :
Contrairement aux travaux précédents, la convergence est prouvée sous des hypothèses standards et plus faibles :

• Fonctions $L$-lisses (L-smoothness).
• Bruit de gradient sous-gaussien ($\sigma$-sub-Gaussian).
• Hétérogénéité bornée uniquement à l'initialisation (ou sous une forme généralisée), et non uniformément sur tout l'espace.

3. Contributions Clés

1. Nouvel Algorithme : Introduction de Byz-Clip21-SGD2M, qui combine agrégation robuste, double momentum et clipping soigneusement conçu.
2. Analyse de Convergence à Haute Probabilité : Les auteurs fournissent une preuve de convergence avec une probabilité élevée ($1-\alpha$) sous les hypothèses standards mentionnées ci-dessus. Cela élimine le besoin d'hypothèses de gradients bornés, ce qui est une avancée majeure par rapport à la littérature précédente.
3. Garanties de Performance :
   • En l'absence d'adversaires, l'algorithme récupère les taux de convergence de l'état de l'art (SOTA).
   • En présence d'adversaires byzantins et de bruit DP, les bornes d'utilité sont améliorées et montrent que l'impact de la DP et des attaques byzantines se multiplie (effet combiné), mais reste contrôlé.
4. Validation Empirique : Des expériences sur des modèles CNN et MLP entraînés sur le dataset MNIST démontrent la supériorité de la méthode par rapport aux baselines (Safe-DSHB, Byz-Clip-SGD) dans divers scénarios d'attaques (IPM, Label Flipping) et de budgets de confidentialité.

4. Résultats Théoriques et Expérimentaux

Résultats Théoriques :

• Le taux de convergence pour la norme du gradient moyen est de l'ordre de $\tilde{O}\left(\frac{1}{\sqrt{GT}} + \frac{\sqrt{d}}{\sqrt{G}\epsilon} + \sqrt{\delta_{byz}}\right)$ (sous certaines conditions), où $d$ est la dimension, $G$ le nombre de clients honnêtes, $\epsilon$ le budget de confidentialité, et $\delta_{byz}$ la fraction d'attaquants.
• La dépendance logarithmique par rapport à la probabilité d'échec $\alpha$ est conforme aux analyses à haute probabilité standards.
• L'analyse couvre le cas où les tampons de momentum sont corrélés, contrairement à certains travaux précédents qui supposaient des tampons i.i.d. (indépendants et identiquement distribués), une hypothèse souvent irréaliste.

Résultats Expérimentaux :

• Scénarios : Entraînement sur MNIST avec des attaques byzantines (IPM et Label Flipping) et différents budgets de confidentialité ($\epsilon \in \{3, 8, 13, 18, 23\}$).
• Performance : Byz-Clip21-SGD2M atteint une précision de test supérieure ou égale aux méthodes de référence (Safe-DSHB, Byz-Clip-SGD) dans la plupart des configurations.
• Robustesse : La méthode maintient une bonne performance même avec un nombre élevé de clients byzantins (jusqu'à 26% des clients dans certains tests) et des budgets de confidentialité stricts.
• Extension (Amplification par sous-échantillonnage) : Une variante (Byz-Clip21-SGD2M+) utilisant le sous-échantillonnage pour amplifier la DP a également été testée, montrant des résultats compétitifs, bien que l'analyse théorique complète pour cette variante soit reportée à un travail futur.

5. Signification et Impact

Cet article est significatif pour plusieurs raisons :

• Relaxation des hypothèses : Il démontre qu'il est possible d'obtenir des garanties de convergence solides pour l'apprentissage fédéré privé et robuste sans supposer que les gradients sont bornés, une hypothèse qui limitait considérablement l'applicabilité des méthodes précédentes.
• Cadre Unifié : Il fournit une fondation théorique unifiée pour traiter simultanément la confidentialité (DP) et la sécurité (Byzantine), deux exigences critiques pour les systèmes d'IA modernes conformes aux réglementations comme le RGPD et l'AI Act de l'UE.
• Praticabilité : L'algorithme proposé est conçu pour être efficace en pratique, utilisant des mécanismes éprouvés (momentum, clipping, rétroaction d'erreur) dans une architecture distribuée réaliste.

En conclusion, Byz-Clip21-SGD2M représente une avancée majeure vers des systèmes d'apprentissage fédéré véritablement fiables, capables de résister aux attaques malveillantes tout en garantissant la vie privée des utilisateurs, le tout sous des hypothèses mathématiques réalistes.