Résumé Technique : HeteRo-Select

Énoncé du Problème

Les systèmes d'Apprentissage Fédéré (FL) allouent traditionnellement la compression de gradient en fonction de la vitesse de liaison (bande passante) et des capacités des dispositifs. Bien que cette approche soit efficace lorsque la bande passante est corrélée à l'informativité des données, cette hypothèse échoue dans des conditions de données non-IID (non-indépendantes et identiquement distribuées). Dans les réseaux de bordure (edge networks) réels, les clients possédant des données locales fortement sous-représentées (haute informativité statistique) opèrent souvent sur des connexions à faible bande passante. Un allocateur piloté par la capacité (comme l'état de l'art FedCG) attribue par inadvertance la compression la plus agressive à ces clients critiques, écartant ainsi des coordonnées de gradient statistiquement importantes et introduisant une perte d'information structurelle. Ce décalage entre les contraintes du système et l'utilité statistique dégrade la convergence et l'efficacité.

Méthodologie : HeteRo-Select

Le papier propose HeteRo-Select, un cadre qui remplace la bande passante comme principal moteur de la compression par un score d'informativité par client ($S_k$). La bande passante n'est conservée que comme un plafond strict pour éviter la latence des clients traînards (stragglers). Le cadre unifie trois décisions de communication en un score normalisé unique :

1. Score d'Informativité Composé ($S_k$) :
   Le score est une somme pondérée de quatre composantes, normalisées par min-max sur $[0, 1]$ :

   • Informativité de la Perte ($V'_k$) : Perte locale normalisée, servant de proxy pour la distance par rapport à la convergence.
   • Diversité de Direction du Gradient ($D_k$) : Mesure la différence angulaire entre le gradient récent d'un client et la moyenne mobile du serveur. Cela agit comme un proxy respectueux de la vie privée pour les distributions de données sous-représentées.
   • Équité ($F'_k$) : Une pénalité additive pour les clients sur-sélectionnés et un bonus pour les clients sous-sélectionnés afin d'éviter la famine (starvation).
   • Obsolescence ($St'_k$) : Un bonus logarithmique pour les clients non sélectionnés récemment, garantissant des probabilités de sélection strictement positives et empêchant le système de s'effondrer sur un sous-ensemble étroit.

2. Mécanisme de Décision Unifié :

   • Sélection de Client : Les probabilités sont dérivées via un softmax tempéré de $S_k$.
   • Ratio de Compression ($\theta_k$) : Le ratio de compression par client est alloué proportionnellement à $S_k$ au sein d'un budget global suivant un calendrier cosinus, plafonné par la limite de bande passante du client ($\theta_k \leq \theta^{cap}_k$).
   • Poids d'Agrégation : Le serveur agrège les mises à jour en utilisant des poids proportionnels à $S_k$ avant d'appliquer le momentum.

3. Feedback d'Erreur Adaptatif et Sparsification :

   • Feedback d'Erreur : Le taux de décroissance du tampon $\beta(t)$ est lié au budget de compression global. Lorsque la compression est lourde (faible $\theta_t$), les résidus sont préservés plus longtemps pour éviter l'effondrement du tampon.
   • Sparsification Pondérée par la Courbure : Alors que la plupart des couches utilisent une sélection top-k basée sur la magnitude standard, un petit ensemble de couches (échantillonnées via une règle de Markov) utilise un critère pondéré par la courbure ($v^2_{k,i} / |H_{ii}|$). Cela réduit le poids des coordonnées dans les régions de haute courbure où de petits gradients sont hautement influents, calculé via une estimation diagonale de Hutchinson par client.

4. Entraînement Local :
   Les clients exécutent FedProx avec un taux d'apprentissage (learning rate) à décroissance globale. Le papier note explicitement que l'échelle du taux d'apprentissage local par le score d'informativité dégrade les performances (provoquant un dépassement/overshoot), confirmant que le signal du score est plus efficace au niveau de la couche de communication qu'au niveau de l'optimiseur local.

Principales Contributions

1. Cadre Unifié : Un score normalisé unique pilote la sélection des clients, le ratio de compression et le poids d'agrégation, déplaçant le signal d'optimisation de la capacité du système vers l'informativité statistique.
2. Mécanismes Adaptatifs : Introduction d'un calendrier de feedback d'erreur lié au budget de compression et d'une stratégie d'échantillonnage de couche de Markov pour la sparsification pondérée par la courbure.
3. Garanties Théoriques :
   • Preuve que l'échantillonnage proportionnel au score réduit l'hétérogénéité effective du sous-ensemble sélectionné ($E[B^2_{sel}] \leq B^2$).
   • Preuve que la compression proportionnelle au score atteint une erreur top-k agrégée plus faible qu'une allocation uniforme sous un budget de trafic fixe.
4. Validation Empirique : Démonstration de l'efficacité de la méthode à travers diverses tailles de modèles et niveaux d'hétérogénéité des données sans réajustement des hyperparamètres.

Résultats Expérimentaux

Évalué sous un protocole correspondant à la ligne de base FedCG (100 clients, 10 sélectionnés par tour, 100 tours) :

• CIFAR-10 (AlexNet) : HeteRo-Select atteint une accélération de 1,78× et une réduction de 18,2 % du trafic pour atteindre la précision cible de 70 % par rapport à FedCG.
• Généralisation Cross-Scale : La même configuration (sans réajustement) atteint avec succès les précisions cibles sur :
  • MNIST (Régression Logistique, 7,8k paramètres).
  • CIFAR-10 (AlexNet, 2,78M paramètres).
  • TinyImageNet (ResNet-18, 11,27M paramètres).
  • Note : La cible CIFAR-100 n'a pas été atteinte en 100 tours en raison d'une hétérogénéité extrême, bien que l'efficacité à des niveaux de précision inférieurs soit restée supérieure.
• Test de Stress (Anti-Corrélation) : Lorsque la bande passante et l'informativité ont été délibérément inversées (clients informatifs sur des liens lents), HeteRo-Select a tout de même atteint la précision cible avec moins de trafic cumulé que la version à bande passante normale. Le système a converti les déficits de bande passante en délais de temps plutôt qu'en pertes de précision grâce au tampon d'erreur adaptatif.
• Études d'Ablation :
  • Le retrait de la composante de diversité ($D_k$) a causé un écart significatif entre le pic et la précision finale (1,2 pts), confirmant son rôle dans la prévention de la dérive en fin de cycle.
  • Les taux d'apprentissage locaux adaptatifs au score ont dégradé les performances ; un calendrier de décroissance globale a été jugé optimal.
  • Une régularisation proximale forte ($\mu=0,1$) était nécessaire pour réaliser les gains de réduction de variance.

Signification et Revendications

Le papier affirme que HeteRo-Select traite un décalage structurel fondamental dans les systèmes FL actuels : la tendance à compresser le plus lourdement les gradients les plus informatifs en raison des contraintes de bande passante. En découplant la décision de ce qui doit être compressé de la capacité à transmettre, le fait d'utiliser la bande passante uniquement comme un plafond, la méthode garantit que l'utilité statistique pilote l'allocation des ressources.

Les auteurs positionnent HeteRo-Select comme une extension de la philosophie d'optimisation conjointe vue dans FedCG, mais avec un signal d'optimisation déplacé. Le travail démontre qu'en traitant l'informativité comme le moteur principal, le système peut maintenir des taux de convergence élevés et une robustesse, même lorsque les capacités du système et les distributions de données sont anti-corrélées. Le papier reste modeste quant à ses limites, admettant qu'une hétérogénéité extrême (ex: CIFAR-100 avec 40 classes manquantes) peut dépasser la capacité d'un budget de rounds fixes, et que la sonde de courbure de Hutchinson ajoute un léger surcoût de calcul qui ne compense pas toujours son coût en gain de précision à des échelles de modèles plus petites.