Sintesi Tecnica: HeteRo-Select

Definizione del Problema

I sistemi di Federated Learning (FL) allocano tradizionalmente la compressione dei gradienti in base alla velocità del link (larghezza di banda) e alle capacità del dispositivo. Sebbene efficace quando la larghezza di banda è correlata all'informatività dei dati, questa ipotesi fallisce in condizioni di dati non-IID (non indipendenti e identicamente distribuiti). Nelle reti edge del mondo reale, i client con dati locali altamente sottorappresentati (alta informatività statistica) operano spesso su connessioni a bassa larghezza di banda. Un allocatore guidato dalle capacità (come lo stato dell'arte FedCG) assegna involontariamente la compressione più aggressiva a questi client critici, scartando coordinate di gradiente statisticamente importanti e introducendo una perdita di informazione strutturale. Questo disallineamento tra vincoli di sistema e utilità statistica degrada la convergenza e l'efficienza.

Metodologia: HeteRo-Select

Il paper propone HeteRo-Select, un framework che sostituisce la larghezza di banda come driver primario della compressione con un punteggio di informatività per client ($S_k$). La larghezza di banda viene mantenuta solo come un tetto massimo per evitare la latenza degli stragglers. Il framework unifica tre decisioni di comunicazione in un unico punteggio normalizzato:

1. Punteggio di Informatività Composta ($S_k$):
   Il punteggio è una somma pesata di quattro componenti, normalizzate min-max nell'intervallo $[0, 1]$:

   • Informatività della Perdita ($V'_k$): Perdita locale normalizzata, che funge da proxy della distanza dalla convergenza.
   • Diversità della Direzione del Gradiente ($D_k$): Misura la differenza angolare tra il gradiente recente di un client e la media mobile del server. Funge da proxy a prova di privacy per le distribuzioni di dati sottorappresentate.
   • Equità ($F'_k$): Una penalità additiva per i client sovraselezionati e un bonus per quelli sottoselezionati per prevenire l'esclusione (starvation).
   • Obsolescenza/Staleness ($St'_k$): Un bonus logaritmico per i client non selezionati di recente, garantendo probabilità di selezione strettamente positive e impedendo al sistema di collassare in un sottoinsieme ristretto.

2. Meccanismo Decisionale Unificato:

   • Selezione del Client: Le probabilità sono derivate tramite una softmax con scalatura di temperatura di $S_k$.
   • Rapporto di Compressione ($\theta_k$): Il rapporto di compressione per client è allocato proporzionalmente a $S_k$ all'interno di un budget con programmazione a coseno globale, limitato dal limite di larghezza di banda del client ($\theta_k \leq \theta^{cap}_k$).
   • Peso di Aggregazione: Il server aggrega gli aggiornamenti utilizzando pesi proporzionali a $S_k$ prima di applicare il momentum.

3. Feedback dell'Errore Adattivo e Sparsificazione:

   • Feedback dell'Errore: Il tasso di decadimento del buffer $\beta(t)$ è legato al budget globale di compressione. Quando la compressione è intensa (basso $\theta_t$), i residui sono preservati più a lungo per prevenire il collasso del buffer.
   • Sparsificazione Pesata sulla Curvatura: Mentre la maggior parte dei layer utilizza la selezione standard basata sulla magnitudo (top-k), un piccolo set di layer (campionati tramite una regola di Markov) utilizza un criterio pesato sulla curvatura ($v^2_{k,i} / |H_{ii}|$). Questo declassa le coordinate in regioni ad alta curvatura dove piccoli gradienti sono altamente influenti, calcolate tramite una singola stima diagonale di Hutchinson per client.

4. Training Locale:
   I client eseguono FedProx con un tasso di apprendimento (learning rate) globalmente decrescente. Il paper nota esplicitamente che scalare il learning rate locale in base al punteggio di informatività degrada le prestazioni (causando overshoot), confermando che il segnale del punteggio è più efficace allo strato di comunicazione, non all'ottimizzatore locale.

Contributi Chiave

1. Framework Unificato: Un unico punteggio normalizzato guida la selezione dei client, il rapporto di compressione e il peso di aggregazione, spostando il segnale di ottimizzazione dalle capacità di sistema all'informatività statistica.
2. Meccanismi Adattivi: Introduzione di uno schema di feedback dell'errore legato al budget di compressione e di una strategia di campionamento dei layer di Markov per la sparsificazione pesata sulla curvatura.
3. Garanzie Teoriche:
   • Dimostrazione che il campionamento proporzionale al punteggio riduce l'eterogeneità effettiva del sottoinsieme selezionato ($E[B^2_{sel}] \leq B^2$).
   • Dimostrazione che la compressione proporzionale al punteggio ottiene un errore top-k aggregato inferiore rispetto all'allocazione uniforme sotto un budget di traffico fisso.
4. Validazione Empirica: Dimostrazione dell'efficacia del metodo attraverso diverse dimensioni di modello e livelli di eterogeneità dei dati senza necessità di ricalibrazione degli iperparametri.

Risultati Sperimentali

Valutato sotto un protocollo che corrisponde al baseline FedCG (100 client, 10 selezionati per round, 100 round):

• CIFAR-10 (AlexNet): HeteRo-Select ottiene un accelerazione di 1.78× e una riduzione del traffico del 18,2% per raggiungere l'accuratezza target del 70% rispetto a FedCG.
• Generalizzazione Cross-Scale: La stessa configurazione (senza ricalibrazione) raggiunge con successo le accuratezze target su:
  • MNIST (Logistic Regression, 7.8k parametri).
  • CIFAR-10 (AlexNet, 2.78M parametri).
  • TinyImageNet (ResNet-18, 11.27M parametri).
  • Nota: L'obiettivo CIFAR-100 non è stato raggiunto entro 100 round a causa dell'estrema eterogeneità, sebbene l'efficienza ai livelli di accuratezza inferiori sia rimasta superiore.
• Test di Stress (Anti-Correlazione): Quando larghezza di banda e informatività sono state deliberatamente invertite (client informativi su link lenti), HeteRo-Select ha comunque raggiunto l'accuratezza target con meno traffico cumulativo rispetto alla corsa a larghezza di banda normale. Il sistema ha convertito i deficit di larghezza di banda in ritardi temporali piuttosto che in perdite di accuratezza tramite il buffer di errore adattivo.
• Studi di Ablazione:
  • Rimuovendo la componente di diversità ($D_k$), si è verificato un gap significativo tra il picco e l'accuratezza finale (1.2 punti), confermando il suo ruolo nel prevenire il drift negli ultimi round.
  • I learning rate locali adattivi al punteggio hanno degradato le prestazioni; un programma di decadimento globale è risultato ottimale.
  • È stata richiesta una forte regolarizzazione prossimale ($\mu=0.1$) per realizzare i guadagni nella riduzione della varianza.

Significato e Rivendicazioni

Il paper sostiene che HeteRo-Select affronti un disallineamento strutturale fondamentale negli attuali sistemi FL: la tendenza a comprimere i gradienti più informativi proprio con la massima intensità a causa dei vincoli di larghezza di banda. Decoupling (disaccoppiando) la decisione di cosa comprimere dalla capacità di trasmetterlo (usando la larghezza di banda solo come un limite superiore), il metodo assicura che l'utilità statistica guidi l'allocazione delle risorse.

Gli autori posizionano HeteRo-Select come un'estensione della filosofia di ottimizzazione congiunta vista in FedCG, ma con un segnale di ottimizzazione spostato. Il lavoro dimostra che trattare l'informatività come il driver primario permette al sistema di mantenere alti tassi di convergenza e robustezza anche quando le capacità di sistema e le distribuzioni dei dati sono anti-correlate. Il paper rimane modesto riguardo ai propri limiti, ammettendo che l'eterogeneità estrema (ad esempio CIFAR-100 con 40 classi mancanti) può superare la capacità di un budget di round fissi, e che la sonda di curvatura di Hutchinson aggiunge un minore overhead computazionale che non sempre recupera il proprio costo in termini di guadagni di accuratezza su scale di modelli più piccole.