FedAVG: Algoritmo di Media Ponderata Federata

L'algoritmo FedAVG rappresenta uno degli approcci basilari e più utilizzati nell'apprendimento federato. La sua semplicità ed efficienza lo hanno reso il punto di partenza per molte varianti più avanzate.

Formula Principale

L'aggiornamento globale dei pesi avviene attraverso la media ponderata degli aggiornamenti locali dei client:

dove:

• w^{t+1}: pesi globali aggiornati al tempo t+1
• K: numero totale di client partecipanti
• n_k: numero di campioni di dati posseduti dal client k
• n = \sum n_k: totale dei campioni sui client coinvolti
• w_k^t: pesi locali del client k dopo l'aggiornamento locale al tempo t

Caratteristiche Salienti

• Efficienza: semplice e veloce da implementare.
• Adatto a setting con dati distribuiti in modo uniforme.
• Meno efficace in contesti con forte eterogeneità dei dati tra i client.

Nota Comparativa

A differenza di FedProx, FedAVG non include alcun termine di regolarizzazione per gestire l'eterogeneità dei dati. Questo può portare a una convergenza più veloce in ambienti omogenei, ma potenzialmente instabile quando i dataset dei client differiscono significativamente.

Dataset Consigliati e Sconsigliati

Adatto per:

• ✅ Dataset con distribuzione dei dati simile tra i client.
• ✅ Problemi di classificazione di immagini generiche (ad esempio MNIST, CIFAR-10) quando ogni client ha dati simili.
• ✅ Ambienti in cui la variabilità tra i client è ridotta.

Sconsigliato per:

• ❌ Dataset altamente eterogenei, con classi squilibrate tra i client (ad esempio dati medici provenienti da ospedali con pazienti diversi).
• ❌ Situazioni in cui i client hanno quantità di dati molto diverse o caratteristiche statistiche divergenti.

L'assenza di un termine di regolarizzazione rende FedAVG meno robusto nei contesti in cui i dati tra i client sono troppo diversi. In tali casi, algoritmi come FedProx risultano più efficaci.

Riferimenti

K. McMahan, E. Moore, D. Ramage, S. Hampson, B. A. Arcas.
"Communication-Efficient Learning of Deep Networks from Decentralized Data", 2017.

FedProx: Algoritmo con Regolarizzazione per l'Eterogeneità dei Dati

L'algoritmo FedProx è stato progettato per affrontare le difficoltà causate dall'eterogeneità dei dati tra i client nell'apprendimento federato. Introduce un termine di regolarizzazione per stabilizzare il processo di aggiornamento dei pesi globali.

Formula Principale

La funzione obiettivo in FedProx aggiunge un termine di regolarizzazione:

dove:

• w: pesi globali da ottimizzare
• K: numero totale di client partecipanti
• n_k: numero di campioni di dati posseduti dal client k
• n = \sum n_k: totale dei campioni sui client coinvolti
• w^k: pesi locali del client k dopo l'addestramento locale
• \mu: parametro di regolarizzazione per controllare la vicinanza tra i pesi locali e globali

Caratteristiche Salienti

• Più robusto rispetto a FedAVG in presenza di dati eterogenei.
• Migliora la stabilità della convergenza.
• Possibile rallentamento nella velocità di convergenza rispetto a FedAVG.

Nota Comparativa

A differenza di FedAVG, FedProx introduce un termine di penalità che limita l'eccessivo allontanamento dei pesi locali rispetto ai pesi globali. Questo consente un migliore adattamento a scenari con dati non IID (Indipendenti e Identicamente Distribuiti).

Dataset Consigliati e Sconsigliati

Adatto per:

• ✅ Dataset eterogenei con differenze significative tra i client.
• ✅ Applicazioni mediche, dove i dati dei pazienti variano notevolmente da un centro ospedaliero all'altro.
• ✅ Dati raccolti da dispositivi diversi con caratteristiche tecniche differenti.

Sconsigliato per:

• ❌ Dataset omogenei e bilanciati tra i client.
• ❌ Scenari in cui è essenziale una convergenza molto rapida e stabile.

L'uso di FedProx in ambienti omogenei potrebbe introdurre un'inefficienza inutile, data la presenza del termine di regolarizzazione.

Riferimenti

T. Li, A. K. Sahu, A. Talwalkar, V. Smith.
"Federated Learning: Challenges, Methods, and Future Directions", 2020.

FedNova: Normalized Averaging per la Riduzione del Bias

L'algoritmo FedNova è stato sviluppato per affrontare il problema del bias introdotto dall'esecuzione di un numero diverso di aggiornamenti locali tra i client. Introduce una media normalizzata degli aggiornamenti, riducendo il bias di aggiornamento e migliorando la stabilità della convergenza.

Formula Principale

FedNova utilizza una media normalizzata degli aggiornamenti locali:

dove:

• w^{t+1}: pesi globali aggiornati al tempo t+1
• w^t: pesi globali al tempo t
• g_k: gradiente normalizzato del client k (corretto per il numero di step locali)
• K: numero totale di client partecipanti
• n_k: numero di campioni del client k
• n = \sum n_k: totale dei campioni sui client coinvolti
• \eta: tasso di apprendimento

Caratteristiche Salienti

• Corregge il bias causato da diverse quantità di aggiornamenti locali.
• Migliora la stabilità e l'equità della convergenza.
• Richiede calcoli aggiuntivi per la normalizzazione dei gradienti.

Nota Comparativa

Rispetto a FedAVG e FedProx, FedNova è particolarmente utile quando i client hanno capacità computazionali diverse e completano un diverso numero di epoche locali.

Dataset Consigliati e Sconsigliati

Adatto per:

• ✅ Scenari con client eterogenei in termini di potenza computazionale.
• ✅ Situazioni in cui i client eseguono numeri variabili di aggiornamenti locali.

Sconsigliato per:

• ❌ Dati perfettamente bilanciati e omogenei tra i client.
• ❌ Situazioni dove la semplicità e velocità di convergenza sono prioritari.

Riferimenti

T. Wang, T. Tuor, S. Salonidis, K. K. Leung, C. Makaya, T. He, and K. Chan.
"Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization", 2020.

SCAFFOLD: Algoritmo di Correzione della Deriva per l'Eterogeneità

L'algoritmo SCAFFOLD è stato sviluppato per mitigare il problema della deriva del client (client drift), che si verifica frequentemente in ambienti con dati eterogenei. SCAFFOLD introduce delle variabili di controllo per correggere la differenza tra gli aggiornamenti locali e il gradiente globale atteso.

Formula Principale

SCAFFOLD utilizza variabili di controllo sia a livello globale che locale per stabilizzare gli aggiornamenti:

dove:

• w^{t+1}: pesi globali aggiornati al tempo t+1
• w^t: pesi globali al tempo t
• g_k: gradiente calcolato dal client k
• K: numero totale di client partecipanti
• c: variabile di controllo globale
• c_k: variabile di controllo del client k
• \eta: tasso di apprendimento

Caratteristiche Salienti

• Mitiga il problema della deriva dei client in presenza di dati eterogenei.
• Migliora la stabilità e la velocità di convergenza rispetto a FedAVG in ambienti non IID.
• Richiede il mantenimento e lo scambio di variabili di controllo aggiuntive tra server e client.

Nota Comparativa

Rispetto a FedAVG e FedProx, SCAFFOLD compensa direttamente la deriva introdotta dagli aggiornamenti locali nei client con dati non IID, risultando spesso più efficiente in questi contesti.

Dataset Consigliati e Sconsigliati

Adatto per:

• ✅ Scenari con dati fortemente eterogenei tra i client.
• ✅ Applicazioni distribuite in cui la deriva dei client rappresenta un problema significativo.

Sconsigliato per:

• ❌ Dati perfettamente IID e bilanciati tra i client.
• ❌ Ambienti dove la semplicità di implementazione è essenziale e il costo di mantenere variabili di controllo è proibitivo.

Riferimenti

S. Karimireddy, S. Kale, M. Mohri, S. Reddi, and A. Suresh.
"SCAFFOLD: Stochastic Controlled Averaging for Federated Learning", 2020.