🤖 machine learning

Federated and differentially private estimation of KL divergence

Questo articolo introduce FedPriKL, un nuovo metodo di privacy differenziale per stimare la divergenza KL in contesti federati che raggiunge un'accuratezza non viesata e a bassa varianza con sensibilità limitata, minimizzando al contempo l'overhead di comunicazione rispetto ai baseline esistenti.

Autori originali: Sayan Biswas, Graham Cormode, Carsten Maple, Mary Scott

Pubblicato 2026-08-24

📖 4 min di lettura☕ Lettura da pausa caffè

CC BY 4.0

Autori originali: Sayan Biswas, Graham Cormode, Carsten Maple, Mary Scott

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Nel mondo moderno dei dati, le informazioni sono spesso sparse tra milioni di dispositivi individuali, dagli smartphone ai tracker sanitari indossabili. Questa natura frammentata crea un modo potente per apprendere il mondo senza mai raccogliere i dati di tutti in un unico archivio centrale. Questo approccio, noto come apprendimento federato (federated learning), consente a un sistema centrale di costruire modelli chiedendo ai dispositivi di eseguire calcoli sui propri dati locali e poi condividendo solo i risultati. Tuttavia, una sfida critica rimane: come facciamo a sapere se i dati utilizzati stanno cambiando nel tempo? Se il comportamento delle persone che utilizzano un'app cambia, i modelli costruiti su dati vecchi possono diventare inaccurati o irrilevanti. Per risolvere questo problema, gli analisti devono misurare la differenza tra i dati attuali e uno standard noto, un compito che solitamente richiede di vedere i dati grezzi. Ma in un mondo in cui la privacy è fondamentale, rivelare i dati grezzi è spesso impossibile. La soluzione richiede un modo per misurare questa differenza matematicamente senza mai esporre i dettagli individuali che compongono i dati.

Ricercatori dell'EPFL, dell'Università di Oxford, dell'Università di Warwick e dell'Infectious Diseases Data Observatory hanno sviluppato un nuovo metodo chiamato FedPriKL per risolvere esattamente questo problema. Il loro lavoro si concentra su una specifica misura matematica utilizzata per confrontare due set di dati, uno strumento che indica quanto un gruppo di informazioni si sia allontanato da un punto di riferimento. In questo scenario, il punto di riferimento è uno standard pubblico su cui tutti concordano, mentre l'altro gruppo è il dato privato e sensibile detenuto dagli utenti sui propri dispositivi. L'obiettivo è calcolare la distanza tra questi due gruppi senza che il server centrale veda mai i singoli record. I ricercatori hanno creato un protocollo che consente a un coordinatore centrale di chiedere a una piccola selezione casuale di dispositivi di controllare quanto spesso determinati elementi compaiano nei loro dati locali. Questi dispositivi inviano poi indietro solo i conteggi per quegli specifici elementi, che vengono combinati in modo sicuro. Per garantire che nemmeno questi conteggi possano essere rintracciati fino a una singola persona, il sistema aggiunge una quantità calcolata con cura di rumore matematico al risultato finale.

Il team ha scoperto che il loro metodo funziona con un alto grado di precisione mantenendo al contempo rigorose garanzie di privacy. Hanno dimostrato matematicamente che il loro approccio produce una stima non influenzata (unbiased), il che significa che il risultato è corretto in media, e che la quantità di rumore necessaria per proteggere la privacy è sufficientemente piccola da non compromettere l'utilità dei dati. Nei loro esperimenti, hanno testato il sistema utilizzando un grande dataset di cifre scritte a mano, simulando uno scenario del mondo reale in cui migliaia di utenti contribuiscono con i dati. Hanno scoperto che, scegliendo attentamente quanti dispositivi interrogare e quanto rumore aggiungere, il sistema può produrre risultati quasi altrettanto accurati come se non fosse stata utilizzata alcuna protezione della privacy. Questo rappresenta un miglioramento significativo rispetto ai metodi precedenti in cui i dispositivi cercavano di nascondere i propri dati aggiungendo rumore prima dell'invio, una tecnica che spesso portava a risultati imprecisi. Il nuovo metodo mantiene l'aggiunta del rumore alla fine del processo, dopo che i dati sono stati combinati in modo sicuro, preservando così l'integrità della misurazione.

I ricercatori hanno anche esplorato come diverse impostazioni influenzino il risultato. Hanno scoperto che il sistema funziona bene anche quando viene chiesto solo a una piccola frazione del totale degli utenti di partecipare in ogni dato round, e che la quantità di dati che ogni utente deve inviare è molto piccola, spesso meno di un kilobyte. Ciò rende il sistema pratico per dispositivi con batteria e memoria limitate. Lo studio ha dimostrato che il metodo può distinguere accuratamente tra piccoli cambiamenti e grandi cambiamenti nei dati, il che è essenziale per decidere quando un modello informatico deve essere aggiornato. Sebbene l'attuale versione del sistema si basi su un passaggio intermedio fidato per combinare i dati in modo sicuro, i ricercatori hanno dimostrato che questo passaggio può essere eseguito utilizzando l'hardware sicuro esistente o tecniche crittografiche avanzate, garantendo che nessuna entità veda mai i dati grezzi. Il lavoro fornisce una strada concreta per monitorare le tendenze dei dati in un modo che rispetti la privacy dell'utente, permettendo alle organizzazioni di mantenere accurati i propri modelli senza compromettere la riservatezza degli individui che generano i dati.

Sintesi Tecnica: FedPriKL – Stima della Divergenza KL Federata e Differenzialmente Privata

Definizione del Problema

Nel moderno apprendimento federato e nell'analisi dei dati, un compito critico è il monitoraggio del drift (deriva) della distribuzione per determinare quando i modelli richiedono un riaddestramento o un fine-tuning. Ciò richiede il confronto tra la distribuzione empirica dei dati detenuti dai client distribuiti ( $P$ ) e una distribuzione di riferimento pubblica fissa ( $\Pi$ ). Tuttavia, la condivisione diretta dei dati dei client o degli istogrammi completi è spesso impraticabile a causa degli elevati costi di comunicazione e dei vincoli di privacy.

Gli approcci esistenti affrontano ostacoli significativi:

Privacy: La raccolta centralizzata di campioni viola la privacy dell'utente.
Risultati di Impossibilità: Il Teorema dell'Invarianza di Shift [9] implica che stimare la divergenza KL tra due distribuzioni sconosciute in uno spazio più piccolo della dimensione del dominio è impossibile.
Comunicazione: Trasmettere istogrammi completi dai client al server è proibitivo in termini di larghezza di banda per domini di grandi dimensioni.
Bias nella Perturbazione Locale: Gli approcci standard di privacy differenziale locale (LDP), in cui i client aggiungono rumore prima dell'aggregazione, introducono un bias significativo quando si stimano funzioni non lineari come la divergenza KL, specialmente quando si gestiscono piccole masse di probabilità.

Il documento affronta il problema della stima di $D_{KL}(\Pi \parallel P)$ in un contesto di apprendimento federato orizzontale dove $P$ è definita dall'aggregato dei dati di $n$ client, e $\Pi$ è un benchmark pubblico noto. L'obiettivo è ottenere una formalità di privacy differenziale (DP) a livello di esempio, minimizzando l'overhead di comunicazione e mantenendo l'accuratezza dello stimatore.

Metodologia: FedPriKL

Gli autori propongono FedPriKL, un protocollo basato sul campionamento che sfrutta un modello di "aggregatore fidato" per ottenere una stima non viesata sotto DP. L'innovazione tecnica centrale è uno stimatore Monte Carlo non viesato basato sui rapporti di verosimiglianza, combinato con l'aggregazione sicura e l'iniezione di rumore calibrato.

Componenti Chiave:

Stimatore Monte Carlo Non Viesato:
Invece di calcolare l'intera divergenza, il metodo campiona $m$ punti $x_i$ dalla distribuzione di riferimento $\Pi$ . Per ogni campione, il protocollo stima il rapporto di verosimiglianza $r(x) = P(x)/\Pi(x)$ .
Utilizzando l'identità derivata dal Fatto IV.2, la divergenza KL è stimata tramite la funzione:
$\Phi(r(x), \lambda) = \lambda(r(x) - 1) - \ln(r(x))$
L'aspettativa di questa funzione sui campioni da $\Pi$ è uguale a $D_{KL}(\Pi \parallel P)$ . Il parametro $\lambda$ controlla la varianza dello stimatore.
Workflow del Protocollo (Algoritmo 2):
- Campionamento: Il server seleziona batch disgiunti di client ( $C_t$ ) e campiona punti $x_{i,t}$ da $\Pi$ .
- Aggregazione Sicura (SecAgg): I client calcolano la frequenza dei punti campionati nei loro dataset locali. Queste frequenze vengono aggregate utilizzando un protocollo di aggregazione sicura (ad esempio, lo sharing di segreti di Shamir) per calcolare la massa di probabilità empirica globale $P(x)$ senza rivelare i dati individuali dei client.
- Elaborazione dell'Aggregatore Fidato: Le probabilità aggregate vengono inviate a un aggregatore fidato. L'aggregatore calcola i rapporti di verosimiglianza $r(x)$ , applica la trasformazione non lineare $\Phi$ e aggiunge rumore Gaussiano calibrato ( $\eta_{\epsilon, \delta}$ ) al risultato.
- Stima Finale: I valori trasformati rumorosi vengono mediati per produrre la stima DP finale.
Meccanismo di Privacy:
A differenza degli approcci baseline dove i client aggiungono rumore localmente (pre-aggregazione), FedPriKL aggiunge rumore dopo l'aggregazione sicura ma prima che la trasformazione non lineare sia finalizzata. Ciò evita il bias introdotto dal clipping dei valori negativi nel rumore locale (un problema comune nella LDP). La sensibilità dello stimatore è limitata (Teorema IV.4 e IV.5), consentendo una precisa calibrazione del rumore per soddisfare la $(\epsilon, \delta)$ -DP.
Modello di Fiducia:
Il protocollo assume un aggregatore fidato (o una realizzazione TEE/SMC) che vede solo le statistiche aggregate in modo sicuro dei punti campionati, non i dati grezzi dei client. Il server è "onesto-ma-curioso" e riceve solo la stima rumorosa finale.

Contributi Chiave

Formalizzazione del Problema: Il documento formalizza il problema del calcolo della divergenza KL in un contesto federato con garanzie formali di privacy differenziale, affrontando specificamente il caso di un riferimento pubblico rispetto a una popolazione privata.
2.za Algoritmo FedPriKL: Gli autori presentano il primo stimatore federato basato sul campionamento e efficiente in termini di comunicazione per $D_{KL}(\Pi \parallel P)$ che offre la privacy differenziale a livello di esempio.
Analisi Teorica:
- Non Viesatezza: È stato dimostrato che lo stimatore è non viesato (Teorema IV.7).
- Limiti di Sensibilità: Sono stati stabiliti limiti di sensibilità per lo stimatore, consentendo la derivazione di scale di rumore ottimali (Teoremi IV.4, IV.5).
- Caratterizzazione della Varianza: È stata fornita una caratterizzazione teorica della varianza dello stimatore in funzione di $\lambda$ , $\epsilon$ e della dimensione del campione, e derivato il $\lambda$ ottimale per minimizzare la varianza (Teoremi V.1, V.3).
Efficienza di Comunicazione: Il payload per client è indipendente dalla dimensione del dominio. Per un dominio di $2^{16}$ elementi, il payload rimane inferiore a 1 KB.

Risultati Sperimentali

Gli autori hanno valutato FedPriKL sul dataset FEMNIST (cifre scritte a mano partizionate per autore), confrontandolo con uno stimatore non privato e un approccio baseline LDP (Algoritmo 1).

Accuratezza vs. Privacy: FedPriKL raggiunge un'accuratezza comparabile allo stimatore non privato quando il budget di privacy $\epsilon$ è moderato ( $0.5 \le \epsilon \le 1.0$ ).
Superiorità rispetto alla Baseline: FedPriKL supera significativamente la baseline (perturbazione locale) in termini di accuratezza e stabilità. La baseline soffre di bias dovuto al necessario clipping delle stime di probabilità negative.
Sensibilità ai Parametri:
- $\lambda$ : Il parametro di varianza ottimale $\lambda$ è stato trovato empiricamente vicino a 0.
- Dimensione del Campione ( $m$ ): Un numero ridotto di campioni ( $m=10$ ) è sufficiente per raggiungere un'accuratezza quasi ottimale, mantenendo leggera la comunicazione del client.
- Dimensione del Batch: Variare il numero di client partecipanti influisce sul tasso di convergenza ma non altera fondamentalmente l'ottimale $\lambda$ .
Robustezza: Il metodo mantiene un basso errore assoluto attraverso diverse magnitudo di divergenza (da piccole a grandi divergenze KL).

Significato e Rivendicazioni

Il documento afferma che FedPriKL è il primo stimatore federato efficiente in termini di comunicazione per la divergenza KL tra un riferimento pubblico e una popolazione privata che offre una formalità di privacy differenziale a livello di esempio.

La significatività risiede nella sua capacità di:

Abilitare il Rilevamento del Drift: Fornire un meccanismo di preservazione della privacy affinché le piattaforme possano rilevare spostamenti di distribuzione e attivare il riaddestramento del modello senza esporre dati sensibili degli utenti.
Superare l'Impossibilità: Limitando il problema a un riferimento pubblico noto, esso elude i risultati di impossibilità riguardanti lo sketching di distribuzioni sconosciute.
Bilanciare Utilità e Privacy: Dimostra che un'alta utilità può essere mantenuta sotto rigorosi vincoli di privacy spostando la fase di iniezione del rumore in una fase post-aggregazione tramite una componente fidata, evitando così il bias inerente ai metodi di perturbazione locale.

Gli autori notano che la dipendenza da un aggregatore fidato (o TEE/SMC) è un compromesso pratico che può essere risolto tramite hardware sicuro o calcolo multipartito, e identificano la rimozione di tale assunzione di fiducia come una direzione per il lavoro futuro.