Non-Convex Over-the-Air Heterogeneous Federated Learning: A Bias-Variance Trade-off

1. Il Problema

Il paper affronta le sfide del Federated Learning (FL) in ambienti wireless eterogenei, utilizzando la tecnica di calcolo Over-the-Air (OTA).

• Contesto: Nell'FL standard, i dispositivi inviano gradienti a un server centrale per aggregarli. Nell'approccio OTA, i dispositivi trasmettono simultaneamente sfruttando la sovrapposizione delle onde radio (canale di accesso multiplo), permettendo un'aggregazione "istantanea" e scalabile.
• Limitazioni degli approcci esistenti:
  • La maggior parte dei disegni OTA-FL attuali impone aggiornamenti a bias zero (non distorti). Questo richiede che i dispositivi con canali peggiori (basso guadagno) limitino la loro potenza di trasmissione per non saturare il ricevitore, o che si assumano condizioni wireless omogenee.
  • In scenari eterogenei (dispositivi con diverse condizioni di canale su larga scala), forzare il bias zero porta a una varianza estremamente alta negli aggiornamenti del modello, rallentando la convergenza.
  • Le analisi teoriche precedenti si concentrano su obiettivi convessi, mentre i moderni modelli di Machine Learning (es. Deep Neural Networks) sono non convessi.
• Obiettivo: Sviluppare un framework OTA-FL per obiettivi lisci non convessi in presenza di eterogeneità wireless, gestendo il compromesso tra bias e varianza.

2. Metodologia

Gli autori propongono un approccio che abbandona la rigidità del "bias zero" a favore di un bias strutturato e tempo-invariante, ottimizzato per ridurre la varianza complessiva.

• Modello di Sistema:

  • $N$ dispositivi inviano gradienti locali a una Base Station (BS) tramite un canale di fading Rayleigh.
  • Viene utilizzata una strategia di controllo della potenza basata sull'inversione del canale troncata (truncated channel inversion). I dispositivi con canali troppo deboli non trasmettono in quel round.
  • Il ricevitore applica un fattore di post-scaling ($\alpha$) per stimare il gradiente globale.

• Analisi di Convergenza (Teorema 1):

  • Viene derivato un limite di convergenza a tempo finito per la norma quadrata media del gradiente (misura di stazionarietà).
  • Il limite rivela esplicitamente un compromesso Bias-Varianza:
    1. Termine di Bias: Deriva dalla partecipazione non uniforme dei dispositivi (pesi $p_m$ diversi da $1/N$). Minimizzare questo termine richiederebbe un bias zero.
    2. Termine di Varianza: Include la varianza di trasmissione (dovuta all'inversione troncata), la varianza dei mini-batch e il rumore del ricevitore.
  • La scelta dei pre-scaler ($\gamma_m$) influenza entrambi i termini: un $\gamma_m$ più basso riduce la varianza di trasmissione e il bias, ma amplifica il rumore del ricevitore; un $\gamma_m$ più alto riduce il rumore ma aumenta il bias strutturato.

• Algoritmo di Ottimizzazione (SCA):

  • Il problema di ottimizzazione congiunta dei parametri di potenza (pre-scaler) per minimizzare il limite di convergenza è non convesso.
  • Gli autori sviluppano un algoritmo efficiente basato sull'Approssimazione Convessa Successiva (SCA).
  • Vantaggio chiave: L'algoritmo richiede solo l'CSI statistico (condizioni di canale su larga scala, $\Lambda_m$) alla Base Station, evitando l'overhead pesante dell'acquisizione di CSI istantaneo globale ad ogni round. I dispositivi utilizzano il CSI istantaneo locale per decidere se trasmettere.

3. Contributi Chiave

1. Analisi Non Convessa: Estensione della teoria OTA-FL a obiettivi non convessi (tipici delle DNN), fornendo limiti di convergenza rigorosi che includono esplicitamente il termine di bias.
2. Design a Bias Strutturato: Proposta di un nuovo schema OTA-FL che accetta un bias controllato e tempo-invariante per mitigare l'alta varianza causata dall'eterogeneità dei canali, superando i limiti dei disegni a bias zero.
3. Algoritmo SCA Efficiente: Sviluppo di un algoritmo di ottimizzazione che risolve il problema di controllo della potenza non convesso utilizzando solo informazioni statistiche al server, rendendo il sistema pratico per reti reali.
4. Trade-off Esplicito: Dimostrazione teorica e pratica che ottimizzare il compromesso bias-varianza porta a una convergenza più rapida rispetto agli approcci tradizionali.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su un compito di classificazione di immagini (MNIST) con una rete neurale fully-connected non convessa, simulando un ambiente wireless eterogeneo.

• Confronto: Il metodo proposto (SCA) è stato confrontato con:
  • Ideal FedAvg: Aggregazione senza rumore (limite superiore teorico).
  • Vanilla OTA-FL: Impone bias zero (richiede CSI istantaneo globale).
  • OPC OTA-Comp: Ottimizza il MSE con CSI istantaneo globale (costoso).
  • Altri schemi: LCPC, BB-FL (scheduler basati su eterogeneità).
• Performance:
  • Il design basato su SCA raggiunge una convergenza più rapida e una migliore accuratezza finale rispetto a Vanilla OTA-FL e agli scheduler esistenti.
  • Le prestazioni sono molto vicine a quelle dell'OPC OTA-Comp (che usa CSI istantaneo globale), ma senza il costo di overhead di comunicazione per l'acquisizione del CSI globale.
  • L'approccio dimostra che accettare un piccolo bias controllato riduce significativamente la varianza, accelerando l'apprendimento in scenari eterogenei.

5. Significato e Impatto

Questo lavoro è significativo perché:

• Ridefinisce il paradigma OTA-FL: Sposta il focus dalla ricerca ossessiva di aggiornamenti "non distorti" (bias zero) all'ottimizzazione sistematica del compromesso bias-varianza, che è più adatto alle reti wireless reali e non omogenee.
• Praticità: L'uso esclusivo di CSI statistico al server rende la soluzione scalabile e applicabile a grandi reti di dispositivi IoT, dove l'acquisizione di CSI istantaneo globale è proibitiva.
• Rilevanza per il Deep Learning: Fornisce le basi teoriche necessarie per applicare l'OTA-FL ai moderni modelli non convessi, colmando un divario tra teoria dell'ottimizzazione wireless e pratica del Machine Learning.

In sintesi, il paper dimostra che in un ambiente wireless eterogeneo, un approccio "imperfetto" ma ottimizzato (bias strutturato) è superiore a un approccio "perfetto" ma ad alta varianza (bias zero), portando a un apprendimento federato più robusto ed efficiente.