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

Sintesi Tecnica: Formazione di Coalizioni Stabili e a Budget Fattibile per il Clustered Federated Learning

Definizione del Problema
I sistemi di apprendimento federato (Federated Learning, FL) soffrono spesso di eterogeneità statistica, in cui una singola "grande coalizione" di tutti i partecipanti produce modelli subottimali. Sebbene il clustered FL affronti l'aspetto statistico raggruppando partecipanti compatibili, l'aspetto economico rimane inesplorato. Nello specifico, manca un framework che garantisca simultaneamente:

1. Stabilità: I partecipanti non abbiano incentivi ad abbandonare unilateralmente la coalizione assegnata per un'altra (stabilità di Nash) o a essere rifiutati da una coalizione di destinazione (stabilità individuale).
2. Fattibilità del Budget: L'entità coordinatrice possa finanziare i trasferimenti necessari per compensare i partecipanti senza incorrere in un deficit.
3. Efficienza: La partizione stabile risultante approssimi l'ottimo del benessere sociale globale.

Gli approcci esistenti trattano spesso la stabilità e i vincoli di budget separatamente o assumono la superadditività del surplus, il che non avviene nei contesti di FL eterogenei e non convessi.

Metodologia
Il documento modella il problema come un gioco edonico di formazione delle coalizioni con surplus trasferibile.

• Modello di Sistema: I partecipanti $N$ sono partizionati in coalizioni. Ogni coalizione $S$ addestra un modello specifico per la coalizione $\theta_S$ utilizzando obiettivi locali pesati. Il modello gestisce i fallimenti della comunicazione (aggiornamenti persi) tramite una regola di aggregazione sicura che lascia invariato il modello se non arrivano aggiornamenti.
• Modello Economico:
  • Surplus: Il totale del surplus trasferibile $W(S)$ è definito come il beneficio di apprendimento atteso $B(S)$ meno i costi del coordinatore $C_0(S)$ e i costi dei partecipanti $d_i(S)$.
  • Trasferimenti: Un coordinatore paga i trasferimenti $t_i(S)$ ai partecipanti. L'utilità del partecipante è $U_i(S) = t_i(S) - d_i(S)$.
  • Fattibilità del Budget: Una regola di allocazione è debolmente fattibile per il budget se il coordinatore trattiene un surplus non negativo ($R_0(S) \ge 0$) in ogni coalizione formata.
• Preferenze Edoniche: Le preferenze sono indotte da una regola di allocazione che converte il surplus in utilità. Il documento si concentra sulle allocazioni di surplus pairwise simmetriche, dove l'utilità di un partecipante in una coalizione è la somma dei valori a coppie $v_{ij}$ con tutti gli altri membri $j \in S$.
• Analisi Teoria dei Giochi:
  • Gli autori dimostrano che le allocazioni pairwise simmetriche inducono un gioco di potenziale esatto. La funzione di potenziale è la somma dei valori a coppie all'interno delle coalizioni.
  • Questa struttura garantisce l'esistenza di una partizione di stabilità di Nash e assicura che qualsiasi sequenza di mosse di risposta migliore (better-response) stretta termini in passi finiti.
  • Anche la Stabilità Individuale (dove i membri di destinazione devono acconsentire a un entrante) è analizzata, mostrando che se i valori a coppia sono non negativi, la stabilità di Nash implica la stabilità individuale.
• Benessere ed Efficienza:
  • Il benessere sociale è scomposto in utilità dei partecipanti (collegata alla funzione di potenziale) e scarto trattenuto dal coordinatore.
  • Il documento stabilisce che il bilancio esatto del budget (zero scarto trattenuto) produce una partizione di stabilità di Nash ottimale in termini di benessere solo se il surplus è esattamente rappresentabile a coppie.
  • Senza esatta rappresentabilità, la perdita di benessere può essere illimitata sotto la sola fattibilità del budget. Tuttavia, se lo scarto trattenuto è limitato rispetto all'ottimo, viene derivata una garanzia di efficienza moltiplicativa (Prezzo della Stabilità).
  • La massimizzazione del potenziale globale è mostrata essere equivalente al clustering di correlazione a massimo accordo pesato. Il documento propone una pipeline: approssimare il clustering, quindi applicare la stabilizzazione tramite risposta migliore stretta per raggiungere una partizione stabile preservando le garanzie di approssimazione.
• Verifica: Il documento fornisce una verifica tramite oracolo in tempo polinomiale per la fattibilità del budget quando la funzione dello scarto trattenuto è submodulare.

Contributi Chiave

1. Modellazione: Introduce un modello di FL specifico per coalizione che gestisce i round di comunicazione non riusciti senza aggregazioni indefinite e non assume la superadditività.
2. Separazione Economica: Separa esplicitamente i benefici di apprendimento, i costi, i trasferimenti e il surplus trattenuto dal coordinatore, derivando le condizioni per la fattibilità del budget e la razionalità individuale.
3. Garanzie di Stabilità: Dimostra che le allocazioni pairwise simmetriche creano un gioco di potenziale esatto, garantendo l'esistenza di partizioni di stabilità di Nash e di stabilità individuale con convergenza finita.
4. Limiti di Efficienza: Caratterizza la relazione tra lo scarto trattenuto dal coordinatore e l'efficienza del benessere. Dimostra che il bilancio esatto produce l'ottimalità della stabilità solo su una specifica classe di surplus, mentre uno scarto relativo limitato fornisce un limite di efficienza moltiplicativa stretto.
5. Complessità Computazionale: Collega la massimizzazione del potenziale globale al clustering di correlazione (NP-difficile) e deriva garanzie di benessere end-to-end per le pipeline di approssimazione-più-stabilizzazione.
6. Verifica: Mostra che un numero esponenziale di vincoli di budget può essere verificato in tempo polinomiale tramite oracolo se lo scarto trattenuto è submodulare.
7. Validazione Empirica: Conduce uno studio preregistrato su CIFAR-10 con $n=4$ partecipanti.

Risultati Sperimentali
Lo studio valuta il meccanismo su cinque seed di dati CIFAR-10 con distribuzioni eterogenee:

• Ottimalità del Benessere: In una calibrazione "benigna", il meccanismo decentralizzato ha raggiunto l'ottimo del benessere stimato in tabella certificata per tutti e cinque i seed. Il Prezzo della Stabilità empirico era esattamente 1.
• Stabilità vs. Baseline: Al contrario, una baseline di "condivisione del surplus uguale" non è riuscita a produrre un esito di stabilità di Nash in tre dei cinque seed (l'insieme di stabilità di Nash era vuoto e la dinamica ciclava).
• Convergenza: Il processo di risposta migliore decentralizzato è convergente rapidamente (media di 1,53 mosse) da varie inizializzazioni.
• Sensibilità: In una calibrazione "snella" (sensibile ai costi), i costi di stabilità sono aumentati (Prezzo della Stabilità fino a 1,29) e la partizione ottimale è diventata sensibile agli errori di stima, evidenziando il compromesso tra la compattezza del budget e la stabilità.
• Stima: Gli stimatori del guadagno di validazione a coppie (PVG) hanno fornito segni di coppia significativamente più affidabili rispetto all'allineamento dei gradienti, che era incline a falsi positivi.

Significato e Rivendicazioni
Il documento sostiene di collegare il valore dell'apprendimento, i trasferimenti monetari, la stabilità e l'efficienza economica senza confondere l'equilibrio locale, l'ottimalità globale e la trattabilità computazionale.

• Teorico: Corregge le limitazioni del lavoro preliminare interpretando correttamente l'equilibrio di Nash come un ottimo locale del potenziale e non assumendo la superadditività. Stabilisce che stabilità ed efficienza sono concetti distinti legati allo scarto trattenuto dal coordinatore.
• Pratico: Il meccanismo proposto offre un modo provabilmente stabile e fattibile per il budget per organizzare partecipanti di FL eterogenei. I risultati empirici dimostrano che, mentre le semplici regole di divisione del surplus possono fallire nel stabilizzare, l'approccio del potenziale pairwise proposto garantisce la convergenza verso uno stato stabile che può coincidere con l'ottimo del benessere.
• Limitazioni: Gli autori osservano che l'attuale modello assume che il coordinatore conosca o stimi i costi e i benefici (allocazione di incentivi piuttosto che design di meccanismi veritieri). La validazione empirica è limitata a $n=4$ partecipanti per consentire l'enumerazione esatta e la certificazione, e i risultati sono specifici per le tabelle di valore stimate dell'esperimento.

Il lavoro conclude che, sebbene il bilancio esatto del budget non garantisca l'ottimalità del benessere in generale, il framework proposto fornisce una solida base teorica e un meccanismo pratico per la formazione di coalizioni stabili e a budget fattibile nel Clustered Federated Learning.