FedSEA: Achieving Benefit of Parallelization in Federated Online Learning

1. Problema e Contesto

Il lavoro affronta le limitazioni attuali dell'Apprendimento Federato Online (OFL - Online Federated Learning). Mentre l'apprendimento federato (FL) risolve problemi di privacy e comunicazione distribuendo l'addestramento su dispositivi edge, l'OFL si occupa di scenari in cui i dati arrivano come flussi continui e le distribuzioni sottostanti cambiano nel tempo.

Le sfide principali identificate dagli autori sono:

• Modello Avversario Pessimistico: Gli approcci OFL standard assumono un avversario che seleziona funzioni di perdita arbitrarie e peggiori casi (worst-case) per ogni client. Questo modello preclude di fatto qualsiasi beneficio derivante dalla parallelizzazione (l'idea che più client lavorino insieme riducano l'errore).
• Mancanza di Distinzione tra Eterogeneità: Le attuali analisi non distinguono chiaramente tra due fonti di variazione statistica:
  • Eterogeneità Spaziale: Differenze nelle distribuzioni di dati tra i diversi client.
  • Eterogeneità Temporale: Cambiamenti nella distribuzione dei dati per lo stesso client nel tempo.
• Inefficienza Computazionale: Molti lavori esistenti richiedono gradienti veri (full gradient), il che è impraticabile per flussi di dati massivi in tempo reale. L'uso di gradienti stocastici è più efficiente, ma la sua integrazione in OFL con garanzie teoriche solide è una sfida aperta.

2. Metodologia Proposta: FedSEA

Gli autori propongono un nuovo quadro teorico e un algoritmo chiamato FedSEA (Federated Stochastically Extended Adversary).

Il Framework SEA (Stochastically Extended Adversary)

Invece di un avversario che sceglie funzioni di perdita deterministiche e peggiori, nel framework SEA:

• L'avversario seleziona dinamicamente e indipendentemente una distribuzione di dati $D_{t,m}$ per ogni client $m$ a ogni passo temporale $t$.
• Il client osserva un campione casuale $\xi_{t,m} \sim D_{t,m}$ e subisce una perdita basata su questo campione.
• La forma funzionale della perdita $f$ rimane fissa, ma la distribuzione dei dati evolve. Questo modello colma il divario tra l'ottimizzazione stocastica (distribuzione fissa) e l'ottimizzazione avversaria (distribuzione delta di Dirac), permettendo di catturare sia la varianza stocastica intrinseca che gli shift temporali.

L'Algoritmo FedSEA

L'algoritmo combina la discesa del gradiente stocastico online (SGD) sui client con un'aggregazione periodica sul server:

1. Aggiornamento Locale: Ogni client $m$ aggiorna il proprio modello locale $x_{t,m}$ utilizzando il gradiente stocastico calcolato sul campione osservato.
2. Sincronizzazione Periodica: Ogni $\tau$ passi temporali, i client inviano i loro modelli al server.
3. Aggregazione Globale: Il server calcola la media dei modelli locali e la trasmette a tutti i client, che aggiornano i propri modelli locali con la media globale.

3. Contributi Chiave

1. Integrazione SEA in OFL: Formalizzazione di un nuovo framework distribuito che modella separatamente l'eterogeneità spaziale (tra client) e temporale (nel tempo).
2. Analisi Fine-Grained dell'Eterogeneità: Quantificazione dell'impatto individuale di $\zeta^2$ (eterogeneità spaziale, deviazione dei gradienti locali dalla media globale) e $K^2$ (eterogeneità temporale, gap tra la perdita ottima istantanea e quella globale ottima).
3. Dimostrazione del Beneficio della Parallelizzazione: Identificazione di un regime specifico (variazione temporale "mite") in cui l'errore di regret migliora all'aumentare del numero di client ($M$), superando i risultati pessimistici della letteratura precedente.

4. Risultati Teorici

Gli autori stabiliscono limiti superiori (bound) sul regret globale atteso $E[R_T]$ su un orizzonte temporale $T$ per due classi di funzioni di perdita:

A. Funzioni Lisce e Convesse

• Bound: $O(\sqrt{T})$.
• Analisi del Regret: Il bound è composto da termini che dipendono dalla varianza del gradiente stocastico ($\sigma^2$), dall'eterogeneità spaziale ($\zeta^2$) e da quella temporale ($K^2$).
• Vantaggio della Parallelizzazione: Se la variazione temporale media $\bar{K}^2$ è sufficientemente piccola rispetto alla varianza stocastica ($\bar{\sigma}^2/M \ge L\bar{K}^2$), il termine dominante del regret diventa $O(\sqrt{T/M})$. Questo dimostra che la parallelizzazione riduce effettivamente l'errore, a differenza dei risultati worst-case precedenti che non mostravano tale beneficio.

B. Funzioni Lisce e Fortemente Convesse

• Bound: $O(\log T)$.
• Analisi: Utilizzando step-size decrescenti, si ottiene un regret logaritmico.
• Vantaggio della Parallelizzazione: Analogamente al caso convesso, se l'eterogeneità temporale massima $K^2_{max}$ è "mite" rispetto alla varianza ($\sigma^2_{max}/M \ge L K^2_{max}$), il regret migliora a $O(\log(T/M))$.

Osservazioni Critiche sui Risultati:

• L'eterogeneità temporale è il fattore dominante che influenza i limiti del regret.
• L'eterogeneità spaziale influisce principalmente sui termini di ordine superiore o sulle costanti additive (drift), ma non degrada la velocità di convergenza fondamentale se la sincronizzazione ($\tau$) è gestita correttamente.
• Il costo di comunicazione può essere ridotto: è possibile sincronizzare solo $O((MT)^{3/4})$ volte su $T$ iterazioni totali mantenendo il bound ottimale.

5. Significato e Impatto

Questo lavoro è significativo perché:

• Ridefinisce i limiti dell'OFL: Sposta l'attenzione da modelli avversari puramente deterministici e pessimistici a modelli più realistici (SEA) che incorporano la natura stocastica dei dati reali.
• Giustifica l'uso della Parallelizzazione: Fornisce le prime garanzie teoriche che dimostrano come l'aggiunta di più client in un contesto OFL possa effettivamente accelerare l'apprendimento e ridurre il regret, a condizione che le distribuzioni temporali non cambino troppo rapidamente.
• Applicabilità Pratica: Il framework è ideale per scenari reali come le previsioni di carico nelle smart grid o i sistemi di raccomandazione, dove i dati sono distribuiti geograficamente (eterogeneità spaziale) e cambiano dinamicamente nel tempo (eterogeneità temporale).

In sintesi, FedSEA dimostra che, in presenza di un avversario "più debole" (stocastico) ma realistico, l'apprendimento federato online può beneficiare della parallelizzazione, offrendo limiti di regret migliori rispetto ai risultati worst-case esistenti.