Adaptive Data Admission and Retention for Streaming Federated Learning

Sintesi Tecnica: Ammissione e Ritenzione Adattiva dei Dati per il Federated Learning in Streaming

Definizione del Problema
Questo articolo affronta la sfida del Federated Learning (FL) in Streaming in ambienti in cui i dispositivi client hanno una memoria limitata e i dati di addestramento arrivano sequenzialmente con costi di campionamento variabili nel tempo. A differenza delle configurazioni FL tradizionali con dataset offline fissi, il FL in streaming comporta un flusso continuo di nuovi campioni che comportano costi di acquisizione, annotazione o trasmissione. I client non possono memorizzare tutti i dati storici indefinitamente. Di conseguenza, il sistema si trova di fronte a un compromesso fondamentale: ammettere nuovi campioni migliora la diversità dei dati e la generalizzazione, ma comporta costi immediati, mentre ritenere e riutilizzare i campioni storici riduce i costi ma rischia il "disequilibrio di riutilizzo" (eccessiva dipendenza da dati obsoleti) e il sovraccarico di memoria.

Il problema centrale è formulato come un compito di ottimizzazione stocastica vincolata. L'obiettivo è minimizzare l'eccesso cumulativo di rischio di popolazione (la differenza tra il rischio del modello appreso e l'ottimo rischio di popolazione) soggetto a due vincoli a lungo termine:

1. Budget del costo di campionamento: Il costo medio di ammissione dei campioni non deve superare un limite prestabilito.
2. Vincolo di occupazione del buffer: Il numero medio di campioni memorizzati in ogni buffer locale del client non deve superare la sua capacità di memoria.

Fondamentalmente, il framework scinde il controllo: un Server dei Parametri (PS) centrale decide le quantità di ammissione (quanti nuovi campioni accettare), mentre i singoli client gestiscono indipendentemente i propri buffer locali (quali campioni scartare) sulla base di informazioni locali, senza che il PS acceda ai dati grezzi.

Metodologia
Gli autori propongono un framework unificato che comprende un limite teorico di apprendimento e una politica di controllo online.

1. Derivazione del Limite dell'Errore di Apprendimento:
   Il documento deriva prima un limite esplicito sull'eccesso cumulativo di rischio di popolazione. Questo limite caratterizza esplicitamente tre fattori critici:

   • Dimensione istantanea del campione di addestramento ($n(t)$): Il numero di campioni attualmente nel buffer utilizzati per l'addestramento.
   • Crescita dei campioni distinti ($N(t)$): Il numero cumulativo di campioni unici osservati.
   • Disequilibrio di riutilizzo: La perdita di diversità statistica causata da un riutilizzo non uniforme dei campioni memorizzati.
     Per catturare questo aspetto, gli autori introducono una metrica di dimensione effettiva del campione, $\tilde{N}_{eff}(t) = N(t) \cdot \tilde{V}(t)$, dove $\tilde{V}(t)$ è un fattore che misura l'uniformità del riutilizzo dei campioni. Il limite mostra che le prestazioni di apprendimento degradano se il riutilizzo dei campioni è altamente disomogeneo.

2. Politica Active-Constraint Drift-Plus-Penalty (ACDPP):
   Per ottimizzare il sistema online, gli autori sviluppano la politica ACDPP, che combina:

   • Ritenzione lato Client a $K$-Step: Una regola strutturata secondo cui ogni campione ammesso viene mantenuto per esattamente $K$ round prima di essere scartato. Questa regola deterministica semplifica il pattern di riutilizzo, permettendo alla dimensione effettiva del campione $\tilde{V}(t)$ di essere espressa in forma chiusa.
   • Ammissione Online lato Server: Un algoritmo Drift-Plus-Penalty (DPP) modificato. Il server mantiene una coda virtuale di debito dei costi per tracciare le violazioni del costo di campionamento. Esso minimizza un'espressione "drift-plus-penalty" dove il termine di penalità è un surrogato del limite dell'errore di apprendimento derivato in precedenza.
   • Vincoli Rettangolari Variabili nel Tempo: Un'aggiunta innovativa allo standard framework DPP. La regione di ammissione ammissibile è vincolata all'interno di un intervallo variabile nel tempo $[\Lambda_{min}(t), \Lambda_{max}(t)]$ che si restringe gradualmente verso un punto operativo target $\bar{\Lambda}$ con il passare del tempo. Questo design bilancia la flessibilità iniziale (per adattarsi a costi variabili) con la stabilità tardiva (per minimizzare i termini $1/n(t)$ nel limite dell'errore).

Contributi Chiave

• Caratterizzazione Teorica: Il documento stabilisce un limite dell'errore di apprendimento per il FL in streaming basato sulla memoria che collega esplicitamente le prestazioni alla dimensione del campione istantanea, al conteggio dei campioni distinti e al disequilibrio di riutilizzo tramite una rappresentazione della dimensione effettiva del campione.
• Design dell'Algoritmo: La proposta della politica ACDPP, che integra una regola di ritenzione lato client a $K$-step con una regola di ammissione online lato server caratterizzata da vincoli rettangolari variabili nel tempo.
• Garanzie di Prestazione: Gli autori dimostrano che la proposta politica raggiunge:
  • Regret Sublineare: L'eccesso cumulivo di rischio cresce in modo sublineare rispetto a un benchmark oracle privo di costi (che ha memoria illimitata e costo di campionamento nullo).
  • Violazione del Costo Sublineare: La violazione cumuliva del budget del costo di campionamento cresce in modo sublineare.
  • Violazione del Buffer Limitata: Attraverso la selezione offline dell'orizzonte di ritenzione $K$, si dimostra che la violazione cumuliva dell'occupazione del buffer è uniformemente limitata ($O(1)$).
• Framework di Confronto: L'analisi utilizza una catena di confronto multi-step che collega la politica ACDPP a una politica ausiliaria di ammissione costante e, infine, all'oracle privo di costi, fornendo espliciti limiti di regret.

Risultati Sperimentali
La politica è stata valutata su tre dataset di classificazione di immagini: MNIST, CIFAR-10 e ImageNette, sia con partizioni di dati non-i.i.d. che i.i.d.

• Prestazioni: ACDPP ha superato costantemente i baseline, inclusa una politica ibrida (che mescola campioni freschi e obsoleti) e una politica di ammissione costante. Su CIFAR-10 (non-i.i.d.), ACDPP ha migliorato l'accuratezza del test di 26,7 punti percentuali rispetto al baseline ibrido e di 3,5 punti rispetto al baseline di ammissione costante.
• Velocità di Convergenza: ACDPP è convergente significativamente più velocemente, raggiungendo le accuratezze target circa 2,2x - 2,6x più velocemente dei baseline su vari dataset.
• Soddisfazione dei Vincoli: Gli esperimenti hanno confermato che la politica mantiene l'occupazione del buffer entro i limiti prescritti e stabilizza la coda del debito dei costi, validando le garanzie teoriche.

Significatività e Rivendicazioni
L'articolo sostiene di colmare una lacuna nella letteratura esistente fornendo un framework centrato sull'apprendimento che ottimizza congiuntamente l'ammissione e la gestione della memoria sotto costi dinamici, piuttosto che concentrarsi esclusivamente sulle risorse di sistema (comunicazione/computazione) o sulla selezione statica dei campioni.

• Va oltre i metodi di selezione basati sul "punteggio" (che assumono che i campioni con gradiente elevato siano preziosi) minimizzando direttamente l'eccesso cumulivo di rischio di popolazione con garanzie di regret teoriche.
• Affronta la sfida specifica dei dati in streaming dove il learner deve decidere quanti campioni ammettere e per quanto tempo ritenerli, un problema non pienamente affrontato dai lavori precedenti focalizzati sulle risorse o sulla selezione.
• Gli autori sottolineano che il loro approccio fornisce esplicite garanzie di regret sublineare e gestisce gli effetti accoppiati di ammissione e ritenzione dei campioni, offrendo una soluzione fondata per l'addestramento di modelli su larga scala e rispettosi della privacy in sistemi edge con flussi di dati in evoluzione.