Who Trains Matters: Federated Learning under Enrollment and Participation Selection Biases

1. Enunciato del Problema

L'Apprendimento Federato (FL) mira ad addestrare un modello globale su una popolazione target di client distribuiti senza centralizzare i dati grezzi. Gli algoritmi standard (ad es. FedAvg) assumono implicitamente che i client che partecipano a ogni round di comunicazione siano un campione rappresentativo della popolazione target. Tuttavia, nella pratica, questa assunzione fallisce spesso a causa del bias di selezione, che il documento identifica come verificantesi in due fasi distinte:

1. Bias di Iscrizione (Enrollment Bias): Determinato da regole di ammissibilità (vincoli del dispositivo, requisiti software, consenso dell'utente) che stabiliscono quali client sono mai raggiungibili per l'addestramento. Ciò crea una discrepanza tra il pool iscritto e la popolazione target.
2. Bias di Partecipazione: Determinato da fattori dinamici (batteria, rete, ora locale) che stabiliscono quali client iscritti partecipano effettivamente a un round di comunicazione specifico.

Il Problema Centrale: La letteratura esistente affronta principalmente il bias di partecipazione a livello di round. Tuttavia, il documento sostiene che anche se il bias di partecipazione fosse corretto perfettamente, il bias di iscrizione induce una discrepanza persistente tra l'obiettivo di addestramento (ottimizzazione per il sottoinsieme iscritto) e l'obiettivo della popolazione target. Se il pool iscritto non è rappresentativo, il modello converge a una soluzione subottimale per la popolazione prevista.

2. Metodologia

Il documento formalizza l'FL sotto un modello di selezione a due stadi e propone un framework di debiasing basato sul Ponderamento Inverso della Probabilità (IPW).

A. Framework di Selezione a Due Stadi

Gli autori modellano l'inclusione dei client come un processo causale:

• Stadio 1 (Iscrizione): Un client $i$ è iscritto ($E_i=1$) con probabilità $\pi^{enroll}_i = P(E_i=1 | Z_i)$, dove $Z_i$ sono le covariate pre-iscrizione (ad es. tipo di dispositivo, regione).
• Stadio 2 (Partecipazione): Condizionatamente all'iscrizione, il client $i$ partecipa al round $r$ ($A_{i,r}=1$) con probabilità $\pi^{part}_{i,r} = P(A_{i,r}=1 | E_i=1, Z_i, X_{i,r})$, dove $X_{i,r}$ sono le covariate pre-round (ad es. batteria, rete).

La probabilità complessiva di inclusione si fattorizza come:
$$p_{i,r} = \pi^{enroll}_i \times \pi^{part}_{i,r}$$

B. L'Algoritmo Proposto: FedIPW

Per recuperare l'aggiornamento medio della popolazione target, gli autori propongono FedIPW (Federated Inverse Probability Weighting).

• Meccanismo: Invece di mediare gli aggiornamenti in modo uniforme, il server pondera l'aggiornamento $\Delta_{i,r}$ di ciascun client per l'inverso della sua probabilità di inclusione:
  $$\hat{\bar{\Delta}}_r = \frac{1}{N} \sum_{i: A_{i,r}=1} \frac{\Delta_{i,r}}{\hat{p}_{i,r}}$$
• Stima: Poiché le probabilità vere sono sconosciute, FedIPW stima i due componenti separatamente:
  1. $\hat{\pi}^{enroll}_i$ è stimato utilizzando covariate pre-iscrizione e indicatori di iscrizione (richiedendo dati a livello di popolazione).
  2. $\hat{\pi}^{part}_{i,r}$ è stimato tra i client iscritti utilizzando covariate a livello di round.
• Garanzia Teorica: Sotto le assunzioni di ignorabilità e positività, FedIPW fornisce uno stimatore non distorto dell'aggiornamento medio della popolazione target.

C. Estensione a Informazioni Limitate: Calibrazione Aggregata

In molti scenari reali, le covariate a livello individuale per i client non iscritti non sono disponibili, rendendo impossibile l'IPW completo di iscrizione.

• Soluzione: Gli autori introducono un'estensione di Calibrazione Aggregata.
• Metodo: Ripesa il campione iscritto in modo che la distribuzione ponderata delle covariate pre-iscrizione (ad es. regione, versione del sistema operativo) corrisponda a sintesi aggregate note della popolazione target (ad es. dati censuari).
• Ruolo: Questo agisce come una correzione parziale del bias di iscrizione quando mancano dati individuali completi.

3. Contributi Chiave

1. Formalizzazione della Selezione a Due Stadi: Il documento distingue il bias di iscrizione dal bias di partecipazione, formalizzandoli come un processo causale sequenziale. Dimostra che ignorare il bias di iscrizione porta a una discrepanza strutturale che le correzioni basate solo sulla partecipazione non possono risolvere.
2. Algoritmo FedIPW: Derivazione di uno schema di aggregazione ponderato per probabilità inversa che recupera l'obiettivo della popolazione target sotto assunzioni standard.
3. Analisi di Ottimizzazione con Soglia di Bias: Gli autori forniscono un'analisi agnostica rispetto all'algoritmo che mostra come gli errori di ponderazione residui (dovuti a errori di stima o a specificazione strutturale errata, come l'omissione dello stadio di iscrizione) inducano una soglia di bias non vanificante.
   • Il limite di errore si decompone in un termine transitorio, un termine di varianza e una soglia di bias proporzionale a $\epsilon_w^2 G^2 / \mu$, dove $\epsilon_w$ è l'errore di ponderazione e $G$ è l'eterogeneità del gradiente.
   • Ciò dimostra che una correzione della selezione incompleta (ad es. correggere solo la partecipazione) comporta una subottimalità persistente.
4. Calibrazione Aggregata: Un metodo pratico per regimi a informazioni limitate che utilizza sintesi della popolazione per mitigare parzialmente il bias di iscrizione.

4. Risultati Sperimentali

Gli autori validano la loro teoria utilizzando regressione logistica federata sintetica, dove l'ottimo vero della popolazione target può essere calcolato con precisione.

• Disallineamento dell'Obiettivo: FedAvg ingenuo converge a una "soluzione del client selezionato" con una perdita sulla popolazione target significativamente più alta rispetto all'ottimo vero.
• Prestazioni di FedIPW: FedIPW recupera con successo l'obiettivo della popolazione target, tracciando da vicino le prestazioni "Oracle" (ideali) anche all'aumentare del bias di iscrizione.
• Fallimento della Correzione Solo Partecipazione: I metodi che correggono solo la partecipazione a livello di round migliorano rispetto a FedAvg ma non raggiungono l'ottimo all'aumentare del bias di iscrizione, confermando l'esistenza della soglia di bias.
• Calibrazione Aggregata: In contesti in cui mancano i dati individuali dei non iscritti, la calibrazione aggregata riduce significativamente l'errore residuo lasciato dai metodi basati solo sulla partecipazione, sebbene sia sensibile al rumore nelle sintesi della popolazione.

5. Significato e Implicazioni

• Cambiamento di Paradigma: Il documento sostiene che "chi può addestrare affatto" (iscrizione) è critico quanto "chi partecipa a un round" (partecipazione). Gli attuali sforzi di debiasing nell'FL focalizzati esclusivamente sulla selezione a livello di round sono insufficienti se il pool iscritto non è rappresentativo.
• Errore Strutturale vs. Statistico: L'analisi distingue tra errori di stima statistica (che possono essere ridotti con modelli migliori) e specificazione strutturale errata (ad es. omissione dello stadio di iscrizione), che crea una soglia di bias irriducibile.
• Guida Pratica: Il lavoro fornisce una roadmap per i professionisti:
  1. Se sono disponibili dati individuali per gli utenti non iscritti, utilizzare FedIPW con ponderazione a due stadi.
  2. Se sono disponibili solo dati aggregati sulla popolazione, utilizzare la Calibrazione Aggregata per correggere parzialmente il bias di iscrizione.
  3. Affidarsi esclusivamente alla correzione della partecipazione è teoricamente insufficiente per raggiungere obiettivi allineati alla popolazione in ambienti eterogenei.

In sintesi, questo documento stabilisce che ottenere un modello rappresentativo della popolazione target nell'FL richiede la correzione del bias di selezione in entrambe le fasi di iscrizione e partecipazione, offrendo un rigoroso framework matematico e algoritmi pratici per raggiungere tale obiettivo.