A Hierarchical Sampling Framework for bounding the Generalization Error of Federated Learning

Riepilogo Tecnico: Un Framework di Campionamento Gerarchico per Limitare l'Errore di Generalizzazione nell'Apprendimento Federato

Enunciato del Problema
L'Apprendimento Federato (FL) consente a più client di addestrare collaborativamente un modello globale mantenendo i dati localizzati. Sebbene esistano limiti di generalizzazione per l'apprendimento supervisionato centralizzato, la loro applicazione diretta al FL spesso non riesce a sfruttare la struttura specifica dell'impostazione FL, in particolare la natura non i.i.d. dei dati derivante da strategie di campionamento gerarchico. La letteratura esistente manca di un framework unificato che comprenda varie strategie di campionamento gerarchico e strutture di comunicazione, basandosi spesso su assunzioni in conflitto con la natura distribuita del FL o non riuscendo a tenere conto delle dipendenze indotte da fonti di dati gerarchiche.

Metodologia
Gli autori propongono un framework generalizzato per l'Apprendimento Federato Gerarchico (HFL) modellato come una struttura ad albero multistrato. In questa impostazione:

• Campionamento Gerarchico: Il dataset è indicizzato da un albero con una topologia fissa. La radice rappresenta una meta-distribuzione $D$. I nodi a livelli intermedi rappresentano client o cluster (distribuzioni sui nodi inferiori), e i nodi foglia rappresentano i punti dati effettivi. Il campionamento procede ricorsivamente dalla radice alle foglie, inducendo dipendenze tra i dataset dei client.
• Costruzione del Supercampione: Per analizzare la generalizzazione, gli autori adattano la tecnica del "supercampione" (originariamente di Steinke et al., 2020). Costruiscono un dataset "fantasma" $\bar{\mu}$ con proprietà statistiche identiche al dataset originale $\mu$. Per ogni nodo nell'albero, una variabile binaria $U$ seleziona tra il nodo originale e la sua copia fantasma. Ciò permette di misurare la sensibilità dell'algoritmo alla modifica di un singolo nodo nell'albero di campionamento.
• Distanza di Wasserstein: L'errore di generalizzazione è limitato utilizzando la distanza di Wasserstein-1 ($W$) tra la distribuzione dell'ipotesi di output condizionata a una specifica selezione di nodo e la distribuzione incondizionata. Questo approccio si basa sull'assunzione che la funzione di perdita $\ell(w, z)$ sia $L$-Lipschitziana rispetto all'ipotesi $w$.

Contributi Chiave

1. Framework HFL Generalizzato: Il documento introduce un framework che comprende varie strategie di campionamento gerarchico e precedenti framework FL come casi speciali, modellando esplicitamente le dipendenze indotte dalla struttura ad albero.
2. Limite di Generalizzazione di Wasserstein: Gli autori derivano un nuovo limite di generalizzazione in termini di distanza di Wasserstein. Questo limite vale per un'ampia gamma di funzioni di perdita (sotto l'assunzione di Lipschitz) e si dimostra essere strettamente più stretto dei limiti esistenti basati sull'Informazione Mutua Condizionata (CMI) all'avanguardia per perdite limitate.
3. Limiti Consapevoli della Privacy: Il framework è esteso per incorporare assunzioni di Privacy Differenziale (DP). Imponendo vincoli di privacy locale sui passaggi di aggregazione all'interno dell'albero, gli autori derivano limiti di generalizzazione basati sulla privacy algoritmica.
4. Caso di Studio: Modello di Posizione Gaussiana (GLM): La strettezza dei limiti derivati è valutata utilizzando un Modello di Posizione Gaussiana. Gli autori dimostrano che il loro limite recupera il corretto tasso asintotico dell'errore di generalizzazione rispetto al numero di punti dati, sebbene mostri una discrepanza di scala riguardo alla profondità dell'albero di campionamento rispetto all'errore reale.

Risultati

• Teorema Principale (Teorema 5): Sotto l'assunzione di Lipschitz, l'errore di generalizzazione atteso è limitato da una somma sui livelli dell'albero della distanza di Wasserstein attesa tra la distribuzione dell'ipotesi condizionata a un nodo selezionato e la distribuzione incondizionata dell'ipotesi.
• Relazione con CMI (Corollario 6 e 9): Per perdite limitate, il limite di Wasserstein implica i limiti CMI esistenti. Gli autori mostrano che la loro derivazione evita la lassità introdotta dalle catene di disuguaglianze (come la disuguaglianza di Pinsker applicata più volte) presenti nei precedenti proof basati su CMI, risultando in un limite strettamente più stretto.
• Implicazioni per la Privacy (Teorema 13): Sotto assunzioni di privacy differenziale $\epsilon$ per l'aggregazione locale, l'errore di generalizzazione è limitato da una funzione dei parametri di privacy $\epsilon_l$ attraverso i livelli, specificamente coinvolgendo $\sqrt{\min(\epsilon_l, \epsilon_l(e^{\epsilon_l}-1))}$.
• Analisi GLM: Nel Modello di Posizione Gaussiana, il vero errore di generalizzazione scala come $\sqrt{\frac{\sum \sigma_l^2/N_l}{\sum \sigma_l^2}}$. Il limite di Wasserstein derivato scala come $\sum \frac{\sigma_l}{N_l}$. Sebbene il limite catturi la scala con il numero di punti dati ($N_l$), gli autori notano che non coglie la specifica scala con la profondità dell'albero ($L$) osservata nel vero errore, in particolare quando le varianze sono omogenee attraverso i livelli.

Significato e Affermazioni
Il documento afferma di fornire una base teorica più generale e più stretta per comprendere la generalizzazione nell'Apprendimento Federato tenendo conto esplicitamente delle dipendenze gerarchiche dei dati. Utilizzando la distanza di Wasserstein, il framework cattura la geometria delle distribuzioni e la sensibilità dell'algoritmo di apprendimento alla struttura di campionamento in modo più efficace rispetto ai precedenti approcci basati sulla teoria dell'informazione. Gli autori affermano che il loro limite implica strettamente i limiti CMI esistenti per perdite limitate, offrendo un affinamento piuttosto che semplicemente un'alternativa. Inoltre, la capacità del framework di integrarsi senza soluzione di continuità con le assunzioni di Privacy Differenziale ne dimostra l'utilità nell'analisi di sistemi FL che preservano la privacy. Gli autori riconoscono le limitazioni, notando che il limite attuale non tiene conto esplicitamente dei vincoli di comunicazione o delle limitazioni computazionali dei singoli nodi, sebbene suggeriscano che questi possano essere incorporati tramite condizioni di indipendenza come mostrato nella loro derivazione del Corollario 10. Si suggerisce un lavoro futuro per estendere il framework a strutture ad albero generali (non fisse).