Stable and Budget-Feasible Coalition Formation for Clustered Federated Learning: A Hedonic Potential-Game Approach

Résumé Technique : Formation de Coalitions Stable et Budgétairement Faisable pour l'Apprentissage Fédéré Groupé

Énoncé du Problème
Les systèmes d'apprentissage fédéré (FL) souffrent souvent d'hétérogénéité statistique, où une « grande coalition » unique de tous les participants produit des modèles sous-optimaux. Bien que l'apprentissage fédéré groupé (clustered FL) traite l'aspect statistique en regroupant des participants compatibles, le côté économique reste sous-exploré. Plus précisément, il manque des cadres qui garantissent simultanément :

1. La Stabilité : Les participants n'ont aucun intérêt à quitter unilatéralement leur coalition assignée pour une autre (stabilité de Nash) ou à être rejetés par une coalition de destination (stabilité individuelle).
2. La Faisabilité Budgétaire : L'entité coordinatrice peut financer les transferts nécessaires pour compenser les participants sans encourir de déficit.
3. L'Efficacité : La partition résultante approxime l'optimum du bien-être social global.

Les approches existantes traitent souvent la stabilité et les contraintes budgétaires séparément ou supposent la superadditivité du surplus, ce qui n'est pas le cas dans les contextes de FL non convexes et hétérogènes.

Méthodologie
Le papier modélise le problème comme un jeu de formation de coalitions hédoniques avec surplus transférable.

• Modèle de Système : Les participants $N$ sont partitionnés en coalitions. Chaque coalition $S$ entraîne un modèle spécifique à la coalition $\theta_S$ en utilisant des objectifs locaux pondérés. Le modèle gère les échecs de communication (mises à jour perdues) via une règle d'agrégation sécurisée qui laisse le modèle inchangé si aucune mise à jour n'arrive.
• Modèle Économique :
  • Surplus : Le surplus transférable total $W(S)$ est défini comme le bénéfice d'apprentissage attendu $B(S)$ moins les coûts du coordinateur $C_0(S)$ et les coûts des participants $d_i(S)$.
  • Transferts : Un coordinateur paie des transferts $t_i(S)$ aux participants. L'utilité du participant est $U_i(S) = t_i(S) - d_i(S)$.
  • Faisabilité Budgétaire : Une règle d'allocation est faiblement faisable sur le plan budgétaire si le coordinateur conserve un surplus non négatif ($R_0(S) \ge 0$) dans chaque coalition formée.
• Préférences Hédoniques : Les préférences sont induites par une règle d'allocation convertissant le surplus en utilités. Le papier se concentre sur les allocations de surplus par paires symétriques, où l'utilité d'un participant dans une coalition est la somme des valeurs par paires $v_{ij}$ avec tous les autres membres $j \in S$.
• Analyse de la Théorie des Jeux :
  • Les auteurs prouvent que les allocations par paires symétriques induisent un jeu de potentiel exact. La fonction de potentiel est la somme des valeurs par paires au sein des coalitions.
  • Cette structure garantit l'existence d'une partition stable de Nash et assure que toute séquence de mouvements de meilleure réponse stricte se termine en un nombre fini d'étapes.
  • La Stabilité Individuelle (où les membres de la destination doivent consentir à un entrant) est également analysée, montrant que si les valeurs par paires sont non négatives, la stabilité de Nash implique la stabilité individuelle.
• Bien-être et Efficacité :
  • Le bien-être social est décomposé en utilité des participants (liée à la fonction de potentiel) et en surplus conservé par le coordinateur.
  • Le papier établit que l'équilibre budgétaire exact (zéro surplus conservé) produit une partition stable de Nash optimale pour le bien-être uniquement si le surplus est exactement représentable par paires.
  • Sans représentabilité exacte, la perte de bien-être peut être illimitée sous la seule condition de faisabilité budgétaire. Cependant, si le surplus conservé est borné par rapport à l'optimum, une garantie d'efficacité multiplicative (Prix de la Stabilité) est dérivée.
  • La maximisation du potentiel global est montrée comme étant équivalente au clustering de corrélation à accord maximal pondéré. Le papier propose un pipeline : approximer le clustering, puis appliquer la stabilisation par meilleure réponse stricte pour atteindre une partition stable tout en préservant les garanties d'approximation.
• Vérification : Le papier fournit une vérification par oracle en temps polynomial pour la faisabilité budgétaire lorsque la fonction de surplus conservé est sous-modulaire.

Contributions Clés

1. Modélisation : Introduit un modèle de FL spécifique à la coalition qui gère les tours de communication infructueux sans agrégation indéfinie et ne suppose pas la superadditivité.
2. Séparation Économique : Sépare explicitement les bénéfices d'apprentissage, les coûts, les transferts et le surplus conservé par le coordinateur, en dérivant les conditions de faisabilité budgétaire et de rationalité individuelle.
3. Garanties de Stabilité : Prouve que les allocations par paires symétriques créent un jeu de potentiel exact, garantissant l'existence de partitions stables de Nash et individuellement stables avec une convergence finie.
4. Bornes d'Efficacité : Caractérise la relation entre le surplus conservé par le coordinateur et l'efficacité du bien-être. Il prouve que l'équilibre exact produit une stabilité optimale uniquement sur une classe spécifique de surplus, tandis qu'un surplus relatif borné fournit une borne d'efficacité multiplicative serrée.
5. Complexité Computationnelle : Lie la maximisation du potentiel global au clustering de corrélation (NP-difficile) et dérive des garanties de bien-être de bout en bout pour les pipelines d'approximation-plus-stabilisation.
6. Vérification : Montre que d'innombrables contraintes budgétaires peuvent être vérifiées en un temps d'oracle polynomial si le surplus conservé est sous-modulaire.
7. Validation Empirique : Réalise une étude préenregistrée sur CIFAR-10 avec $n=4$ participants.

Résultats Expérimentaux
L'étude évalue le mécanisme sur cinq graines de données CIFAR-10 avec des distributions hétérogènes :

• Optimalité du Bien-être : Dans un étalonnage « bénin », le mécanisme décentralisé a atteint l'optimum du bien-être de la table estimée certifiée pour les cinq graines. Le Prix de la Stabilité empirique était exactement 1.
• Stabilité vs Baselines : En revanche, une base de référence de « partage de surplus égal » a échoué à produire un résultat stable de Nash sur trois des cinq graines (l'ensemble stable de Nash était vide, et la dynamique cyclait).
• Convergence : Le processus de meilleure réponse décentralisé a convergé rapidement (moyenne de 1,53 mouvements) à partir de diverses initialisations.
• Sensibilité : Dans un étalonnage « mince » (sensible aux coûts), les coûts de stabilité ont augmenté (Prix de la Stabilité jusqu'à 1,29), et la partition optimale est devenue sensible aux erreurs d'estimation, soulignant le compromis entre la rigueur budgétaire et la stabilité.
• Estimation : Les estimateurs de gain de validation par paire (PVG) ont fourni des signes de paires nettement plus fiables que l'alignement de gradient, qui était sujet aux faux positifs.

Signification et Revendications
Le papier affirme qu'il connecte la valeur d'apprentissage, les transferts monétaires, la stabilité et l'efficacité économique sans confondre l'équilibre local, l'optimalité globale et la tractabilité computationnelle.

• Théorique : Il corrige les limites des travaux préliminaires en interprétant correctement l'équilibre de Nash comme un optimum de potentiel local et en ne supposant pas la superadditivité. Il établit que la stabilité et l'efficacité sont des concepts distincts liés par le surplus conservé par le coordinateur.
• Pratique : Le mécanisme proposé offre une manière prouvablement stable et budgétairement faisable d'organiser les participants hétérogènes au FL. Les résultats empiriques démontrent que si des règles simples de division du surplus peuvent échouer à stabiliser, l'approche de potentiel par paires proposée garantit la convergence vers un état stable qui peut coïncider avec l'optimum du bien-être.
• Limites : Les auteurs notent que le modèle actuel suppose que le coordinateur connaît ou estime les coûts et les bénéfices (allocation incitative plutôt que conception de mécanisme de vérité). La validation empirique est limitée à $n=4$ participants pour permettre l'énumération exacte et la certification, et les résultats sont spécifiques aux tables de valeurs estimées de l'expérience.

Le travail conclut que bien que l'équilibre budgétaire exact ne garantisse pas l'optimalité du bien-être en général, le cadre proposé offre une base théorique robuste et un mécanisme pratique pour la formation de coalitions stable et budgétairement faisable dans l'apprentissage fédéré groupé.