Fairness-Aware Federated Learning with Trajectory Shapley Value

Riepilogo Tecnico: Apprendimento Federato Consapevole dell'Equità con il Valore di Shapley della Traiettoria

Enunciato del Problema
L'Apprendimento Federato (FL) consente l'addestramento collaborativo di modelli su client distribuiti senza condividere dati grezzi, affrontando vincoli di privacy e comunicazione in domini quali le energie rinnovabili, la sanità e i sistemi autonomi. Tuttavia, gli schemi di aggregazione convenzionali, in particolare la Media Federata (FedAvg), si basano su pesi fissi (tipicamente uniformi o proporzionali alla dimensione del dataset). Questi pesi statici non tengono conto delle contribuzioni variabili nel tempo dei client, dell'eterogeneità dei dati e della partecipazione parziale. Di conseguenza, il modello globale può soffrire di bias, instabilità e vulnerabilità verso client di bassa qualità o malevoli (bizantini) che esercitano un'influenza sproporzionata.

I metodi esistenti per la valutazione dei client utilizzano spesso il Valore di Shapley (SV) dalla teoria dei giochi cooperativi per assegnare punteggi equi basati sulle contribuzioni marginali. Tuttavia, il calcolo esatto del SV è intrattabile per reti di grandi dimensioni. Le approssimazioni come il campionamento Monte Carlo possono sottostimare i client che si uniscono in ritardo o partecipano raramente, mentre i metodi basati sul gradiente (ad esempio, il Valore di Shapley del Gradiente Coseno) possono sovrastimare gli aggiornamenti di grande magnitudine e mancare di informazioni basate sulla validazione. Vi è la necessità di una metrica di contribuzione che sia temporalmente coerente, robusta al comportamento avversario e capace di valutare i client in base alla loro influenza sulla traiettoria di ottimizzazione piuttosto che solo sulla riduzione statica della perdita.

Metodologia: Valore di Shapley della Traiettoria (TSV) e FedTSV
Gli autori propongono il Valore di Shapley della Traiettoria (TSV), una nuova metrica di contribuzione, e FedTSV, un algoritmo di aggregazione adattivo.

1. Valore di Shapley della Traiettoria (TSV):

   • Concetto: Invece di concentrarsi esclusivamente sulla riduzione statica della perdita, il TSV valuta quanto l'aggiornamento della coalizione di un client sia allineato con la traiettoria di ottimizzazione del modello globale.
   • Aggiornamento di Riferimento: Ad ogni round di comunicazione $t$, il server calcola un aggiornamento di riferimento ($\Delta^t_{val}$) eseguendo $K$ passi di Discesa del Gradiente Stocastico (SGD) su dati di validazione tenuti da parte, partendo dal modello globale corrente $\theta_t$.
   • Funzione di Utilità: Per qualsiasi coalizione $S$ di client partecipanti, il server calcola il loro aggiornamento medio ($\Delta^t_S$). Viene definita un'utilità per-round limitata $v_t(S)$ basata sulla distanza tra l'aggiornamento della coalizione e il riferimento di validazione:
     $$v_t(S) = \left( 1 + \frac{\text{Dist}(\Delta^t_S, \Delta^t_{val})^2}{\sigma_t} \right)^{-1}$$
     dove $\text{Dist}$ è una metrica (ad esempio, euclidea) e $\sigma_t$ è un fattore di normalizzazione per garantire la stabilità vicino ai punti stazionari.
   • Punteggio: L'utilità $v_t(S)$ aumenta man mano che l'aggiornamento della coalizione si avvicina geometricamente alla direzione di discesa della validazione. Il Valore di Shapley viene stimato per round utilizzando il campionamento Monte Carlo su questa utilità limitata e accumulato nel tempo per formare un punteggio cumulativo di contribuzione.

2. Algoritmo FedTSV:

   • Ponderazione Adattiva: I valori di Shapley cumulativi vengono convertiti in pesi di aggregazione non negativi e dipendenti dal tempo ($\alpha^t_i$).
   • Meccanismo: I client con contribuzioni cumulative positive ricevono pesi più elevati, mentre quelli con contribuzioni negative (che indicano comportamenti malevoli o un allineamento costantemente scarso) vengono troncati a zero.
   • Robustezza: Questo meccanismo permette al server di rispondere dinamicamente in tempo reale a partecipazioni eterogenee e avversarie, riducendo il peso dei client malevoli senza richiedere conoscenze preliminari sul loro stato.
   • Complessità: Il metodo richiede solo un passaggio di addestramento per client per round più un passaggio di validazione lato server, mantenendo la fattibilità computazionale.

Contributi Chiave
Il documento delinea tre contributi principali:

1. Metrica TSV: Introduzione di una nuova metrica di contribuzione che valuta i client attraverso la loro influenza sulla traiettoria di ottimizzazione, offrendo un'alternativa temporalmente coerente ai metodi convenzionali basati sul SV.
2. Algoritmo FedTSV: Sviluppo di un algoritmo di ponderazione adattiva che sfrutta il TSV per regolare dinamicamente i pesi di aggregazione, migliorando equità e robustezza in ambienti eterogenei e avversari.
3. Validazione Empirica: Dimostrazione dell'efficacia di FedTSV su benchmark di classificazione di immagini (MNIST e CIFAR-10) e vari scenari FL, evidenziando i suoi vantaggi per l'apprendimento distribuito che preserva la privacy.

Risultati Sperimentali
Gli autori hanno valutato FedTSV rispetto a baseline tra cui FedAvg, Valore di Shapley del Gradiente Coseno (CGSV) e metodi Leave-One-Out (LOO) sui dataset MNIST e CIFAR-10 con 100 client (70 IID, 10 non-IID, 20 malevoli).

• Convergenza e Accuratezza: FedTSV ha accelerato costantemente la convergenza e raggiunto una maggiore accuratezza globale rispetto alle baseline. Su CIFAR-10, FedAvg si è saturato a livelli di accuratezza inferiori (~0,65), mentre FedTSV ha mantenuto prestazioni stabili e superiori.
• Robustezza: FedTSV ha dimostrato una maggiore stabilità contro la corruzione delle etichette e l'eterogeneità statistica. Le fluttuazioni delle prestazioni di FedTSV sono state significativamente inferiori rispetto ad altri metodi, in particolare sul più complesso scenario CIFAR-10.
• Valutazione della Contribuzione: La visualizzazione dei pesi dei client ha mostrato che FedTSV ha separato efficacemente i tipi di client: i client malevoli hanno ricevuto punteggi bassi, i client benigni IID si sono concentrati nella regione positiva e i client benigni non-IID si sono collocati in mezzo. Al contrario, FedAvg ha assegnato pesi uniformi, mentre CGSV e LOO hanno mostrato distribuzioni disperse o pesi gonfiati per i client avversari.

Significato e Affermazioni
Il documento afferma che FedTSV fornisce una base principiale per l'ottimizzazione federata consapevole dell'equità. Integrando l'analisi degli aggiornamenti basata sulla traiettoria con i principi del valore di Shapley, il metodo offre un meccanismo sia efficiente che robusto. Gli autori affermano che FedTSV migliora la robustezza in presenza di client eterogenei e avversari, preservando al contempo l'efficienza computazionale.

Il documento mantiene un tono modesto riguardo alle garanzie teoriche, notando che le solite dimostrazioni di convergenza per FedAvg non si applicano direttamente all'obiettivo variabile nel tempo di FedTSV, e che un'analisi rigorosa della convergenza è lasciata a lavori futuri. Le direzioni di ricerca future identificate includono l'indagine delle fondamenta teoriche di FedTSV da un punto di vista della teoria dei giochi, focalizzandosi specificamente sulla compatibilità degli incentivi e sull'equità nell'apprendimento collaborativo a lungo termine.