🤖 machine learning

Federated and differentially private estimation of KL divergence

Dieses Paper stellt FedPriKL vor, eine neuartige differenziell private Methode zur Schätzung der KL-Divergenz in föderierten Umgebungen, die eine unverzerrte Genauigkeit mit geringer Varianz bei beschränkter Sensitivität erreicht und gleichzeitig den Kommunikationsaufwand im Vergleich zu bestehenden Baselines minimiert.

Ursprüngliche Autoren: Sayan Biswas, Graham Cormode, Carsten Maple, Mary Scott

Veröffentlicht 2026-08-24

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Sayan Biswas, Graham Cormode, Carsten Maple, Mary Scott

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

In der modernen Welt der Daten sind Informationen oft über Millionen einzelner Geräte verstreut, von Smartphones bis hin zu Wearables für die Gesundheitsverfolgung. Diese verstreute Natur schafft eine leistungsstarke Möglichkeit, die Welt zu lernen, ohne jemals alle Daten in einem zentralen Tresor sammeln zu müssen. Dieser Ansatz, bekannt als Federated Learning, ermöglicht es einem zentralen System, Modelle zu erstellen, indem es Geräte bittet, Berechnungen auf ihren eigenen lokalen Daten durchzuführen und anschließend nur die Ergebnisse zu teilen. Es bleibt jedoch eine kritische Herausforderung bestehen: Woher wissen wir, ob sich die verwendeten Daten im Laufe der Zeit verändern? Wenn sich das Verhalten der Menschen, die eine App nutzen, verschiebt, können die auf alten Daten aufgebauten Modelle ungenau oder irrelevant werden. Um dies zu beheben, müssen Analysten den Unterschied zwischen den aktuellen Daten und einem bekannten Standard messen – eine Aufgabe, die normalerweise voraussetzt, dass man die Rohdaten sieht. Doch in einer Welt, in der Privatsphäre oberstes Gebot ist, ist die Offenlegung der Rohdaten oft unmöglich. Die Lösung erfordert einen Weg, diesen Unterschied mathematisch zu messen, ohne jemals die individuellen Details preiszugeben, die die Daten ausmachen.

Forscher der EPFL, der Universität Oxford, der Universität Warwick und des Infectious Diseases Data Observatory haben eine neue Methode namens FedPriKL entwickelt, um genau dieses Problem zu lösen. Ihre Arbeit konzentriert sich auf ein spezifisches mathematisches Maß, das zur Vergleichung zweier Datensätze verwendet wird – ein Werkzeug, das uns sagt, wie stark eine Informationsgruppe von einem Referenzpunkt abgewichen ist. In diesem Szenario ist der Referenzpunkt ein öffentlicher Standard, auf den sich alle geeinigt haben, während die andere Gruppe die privaten, sensiblen Daten sind, die Nutzer auf ihren Geräten halten. Das Ziel besteht darin, den Abstand zwischen diesen beiden Gruppen zu berechnen, ohne dass der zentrale Server jemals die einzelnen Datensätze sieht. Die Forscher entwickelten ein Protokoll, das es einem zentralen Koordinator ermöglicht, eine kleine, zufällige Auswahl an Geräten zu bitten, zu prüfen, wie häufig bestimmte Elemente in ihren lokalen Daten vorkommen. Diese Geräte senden dann nur die Zählungen für diese spezifischen Elemente zurück, welche anschließend sicher kombiniert werden. Um sicherzustellen, dass selbst diese Zählungen nicht auf eine einzelne Person zurückgeführt werden können, fügt das System am Ende des Ergebnisses eine sorgfältig berechnete Menge an mathematischem Rauschen hinzu.

Das Team stellte fest, dass ihre Methode mit einem hohen Grad an Genauigkeit arbeitet und gleichzeitig strenge Datenschutzgarantien aufrechterhält. Sie haben mathematisch bewiesen, dass ihr Ansatz eine unverzerrte Schätzung liefert, was bedeutet, dass das Ergebnis im Durchschnitt korrekt ist, und dass die Menge an Rauschen, die zum Schutz der Privatsphäre erforderlich ist, klein genug ist, um die Nützlichkeit der Daten nicht zu beeinträchtigen. In ihren Experimenten testeten sie das System unter Verwendung eines großen Datensatzes handgeschriebener Ziffern, um ein reales Szenario zu simulieren, in dem Tausende von Nutzern Daten beisteuern. Sie entdeckten, dass das System durch eine sorgfältige Wahl der Anzahl der angefragten Geräte und der Menge des hinzugefügten Rauschens Ergebnisse liefern konnte, die fast so genau waren, als wäre gar kein Datenschutz verwendet worden. Dies ist eine signifikante Verbesserung gegenüber bisherigen Methoden, bei denen Geräte versuchten, ihre Daten zu verbergen, indem sie Rauschen vor dem Senden hinzufügten – eine Technik, die oft zu ungenauen Ergebnissen führte. Die neue Methode hält die Hinzufügung des Rauschens an das sehr Ende des Prozesses, nachdem die Daten sicher kombiniert wurden, was die Integrität der Messung bewahrt.

Die Forscher untersuchten auch, wie verschiedene Einstellungen das Ergebnis beeinflussen. Sie fanden heraus, dass das System gut funktioniert, selbst wenn nur ein kleiner Bruchteil der Gesamtnutzer gebeten wird, an einem gegebenen Durchgang teilzunehmen, und dass die Menge der Daten, die jeder Nutzer senden muss, sehr gering ist, oft weniger als ein Kilobyte. Dies macht das System praktikabel für Geräte mit begrenzter Akkulaufzeit und Speicherplatz. Die Studie zeigte, dass die Methode in der Lage ist, zwischen kleinen und großen Änderungen der Daten genau zu unterscheiden, was entscheidend ist, um zu entscheiden, wann ein Computermodell aktualisiert werden muss. Während die aktuelle Version des Systems auf einen vertrauenswürdigen Zwischenschritt angewiesen ist, um die Daten sicher zu kombinieren, zeigten die Forscher, dass dieser Schritt mithilfe bestehender sicherer Hardware oder fortschrittlicher kryptografischer Techniken durchgeführt werden kann, wodurch sichergestellt wird, dass keine einzelne Instanz die Rohdaten sieht. Die Arbeit bietet einen konkreten Weg nach vorn, um Datentrends auf eine Weise zu überwachen, die die Privatsphäre respektiert, und ermöglicht es Organisationen, ihre Modelle präzise zu halten, ohne die Vertraulichkeit der Individuen zu gefährden, die die Daten generieren.

Technische Zusammenfassung: FedPriKL – Föderierte und differenziell private Schätzung der KL-Divergenz

Problemstellung

In modernem föderiertem Lernen und Analytik ist die Überwachung von Verteilungsdrifts eine kritische Aufgabe, um zu bestimmen, wann Modelle ein Retraining oder Fine-Tuning benötigen. Dies erfordert den Vergleich der empirischen Verteilung der bei verteilten Clients gehaltenen Daten ( $P$ ) mit einer festen öffentlichen Referenzverteilung ( $\Pi$ ). Das direkte Teilen von Client-Daten oder vollständigen Histogrammen ist jedoch aufgrund hoher Kommunikationskosten und Datenschutzbeschränkungen oft nicht realisierbar.

Bestehende Ansätze stehen vor erheblichen Hürden:

Privatsphäre: Die zentrale Sammlung von Stichproben verletzt die Privatsphäre der Nutzer.
Unmöglichkeitsresultate: Das Shift-Invariance-Theorem [9] impliziert, dass die Schätzung der KL-Divergenz zwischen zwei unbekannten Verteilungen in einem Raum, der kleiner als die Domänengröße ist, unmöglich ist.
Kommunikation: Die Übertragung vollständiger Histogramme von Clients zum Server ist für große Domänen bandbreitenprohibitiv.
Bias durch lokale Perturbation: Standardansätze der lokalen differenziellen Privatsphäre (LDP), bei denen Clients Rauschen vor der Aggregation hinzufügen, führen zu einem signifikanten Bias bei der Schätzung nichtlinearer Funktionen wie der KL-Divergenz, insbesondere beim Umgang mit kleinen Wahrscheinlichkeitsmassen.

Das Paper adressiert das Problem der Schätzung von $D_{KL}(\Pi \parallel P)$ in einem horizontalen föderierten Setting, in dem $P$ durch die aggregierten Daten von $n$ Clients definiert ist und $\Pi$ eine bekannte öffentliche Benchmark darstellt. Das Ziel ist es, eine formale beispielbezogene (example-level) differenzielle Privatsphäre (DP) zu erreichen und gleichzeitig den Kommunikationsaufwand zu minimieren sowie die Genauigkeit des Schätzers zu maximieren.

Methodik: FedPriKL

Die Autoren schlagen FedPriKL vor, ein sampling-basiertes Protokoll, das ein Modell eines „vertrauenswürdigen Aggregators“ nutzt, um eine erwartungstreue (unbiased) Schätzung unter DP zu erreichen. Die zentrale technische Innovation ist ein erwartungstreuer Monte-Carlo-Schätzer basierend auf Likelihood-Verhältnissen, kombiniert mit sicherer Aggregation und kalibrierter Rauschinjektion.

Kernkomponenten:

Erwartungstreuer Monte-Carlo-Schätzer:
Anstatt die vollständige Divergenz zu berechnen, sampelt die Methode $m$ Punkte $x_i$ aus der Referenzverteilung $\Pi$ . Für jede Stichprobe schätzt das Protokoll das Likelihood-Verhältnis $r(x) = P(x)/\Pi(x)$ .
Unter Verwendung der in Fakt IV.2 abgeleiteten Identität wird die KL-Divergenz über die Funktion geschätzt:
$\Phi(r(x), \lambda) = \lambda(r(x) - 1) - \ln(r(x))$
Der Erwartungswert dieser Funktion über die Stichproben aus $\Pi$ entspricht $D_{KL}(\Pi \parallel P)$ . Der Parameter $\lambda$ steuert die Varianz des Schätzers.
Protokoll-Ablauf (Algorithmus 2):

Sampling: Der Server wählt disjunkte Batches von Clients ( $C_t$ ) aus und zieht Stichproben von Punkten $x_{i,t}$ aus $\Pi$ .
Sichere Aggregation (SecAgg): Clients berechnen die Häufigkeit der gesampelten Punkte in ihren lokalen Datensätzen. Diese Häufigkeiten werden über ein Protokoll zur sicheren Aggregation (z. B. Shamirs Secret Sharing) aggregiert, um die globale empirische Wahrscheinlichkeitsmasse $P(x)$ zu berechnen, ohne individuelle Client-Daten offenzulegen.
Verarbeitung durch den vertrauenswürdigen Aggregator: Die aggregierten Wahrscheinlichkeiten werden an einen vertrauenswürdigen Aggregator gesendet. Dieser berechnet die Likelihood-Verhältnisse $r(x)$ , wendet die nichtlineare Transformation $\Phi$ an und fügt kalibriertes Gaußsches Rauschen ( $\eta_{\epsilon, \delta}$ ) hinzu.
Finale Schätzung: Die verrauschten transformierten Werte werden gemittelt, um die finale DP-Schätzung zu erzeugen.

Privatsphäre-Mechanismus:
Im Gegensatz zu Baseline-Ansätzen, bei denen Clients das Rauschen lokal (vor der Aggregation) hinzufügen, fügt FedPriKL das Rauschen nach der sicheren Aggregation, aber vor der Finalisierung der nichtlinearen Transformation hinzu. Dies vermeidet den Bias, der durch das Clipping negativer Werte bei lokaler Perturbation entsteht. Die Sensitivität des Schätzers ist begrenzt (Theorem IV.4 und IV.5), was eine präzise Rauschkalibrierung ermöglicht, um $(\epsilon, \delta)$ -DP zu erfüllen.
Vertrauensmodell:
Das Protokoll setzt einen vertrauenswürdigen Aggregator voraus (oder eine TEE/SMC-Realisierung), der nur die sicher aggregierten Statistiken der gesampelten Punkte sieht, aber nicht die Rohdaten der Clients. Der Server ist „honest-but-curious“ und erhält lediglich die finale verrauschte Schätzung.

Zentrale Beiträge

Problemformalisierung: Das Paper formalisiert das Problem der Berechnung der KL-Divergenz in einem föderierten Setting mit formalen Garantien für differenzielle Privatsphäre, insbesondere für den Fall einer öffentlichen Referenz gegenüber einer privaten empirischen Verteilung.
FedPriKL-Algorithmus: Die Autoren präsentieren den ersten kommunikationseffizienten, sampling-basierten föderierten Schätzer für $D_{KL}(\Pi \parallel P)$ , der formale beispielbezogene DP bietet.
Theoretische Analyse:
- Erwartungstreue (Unbiasedness): Es wird bewiesen, dass der Schätzer erwartungstreu ist (Theorem IV.7).
- Sensitivitätsgrenzen: Es wurden begrenzte Sensitivitäten für den Schätzer etabliert, was die Ableitung optimaler Rauschskalen ermöglicht (Theorem IV.4, IV.5).
- Varianzcharakterisierung: Es wurde eine theoretische Charakterisierung der Varianz des Schätzers als Funktion von $\lambda$ , $\epsilon$ und der Stichprobengröße bereitgestellt und das optimale $\lambda$ zur Minimierung der Varianz abgeleitet (Theorem V.1, V.3).
Kommunikationseffizienz: Die Payload pro Client ist unabhängig von der Domänengröße. Für eine Domäne mit $2^{16}$ Elementen bleibt die Payload unter 1 KB.

Experimentelle Ergebnisse

Die Autoren evaluierten FedPriKL auf dem FEMNIST-Datensatz (handschriftliche Ziffern, partitioniert nach Autoren) und verglichen es mit einem nicht-privaten Schätzer und einem Baseline-LDP-Ansatz (Algorithmus 1).

Genauigkeit vs. Privatsphäre: FedPriKL erreicht eine Genauigkeit, die mit dem nicht-privaten Schätzer vergleichbar ist, wenn das Privacy-Budget $\epsilon$ moderat ist ( $0,5 \le \epsilon \le 1,0$ ).
Überlegenheit gegenüber der Baseline: FedPriKL ist in Bezug auf Genauigkeit und Stabilität dem Baseline-Ansatz (lokale Perturbation) deutlich überlegen. Die Baseline leidet unter einem Bias aufgrund des notwendigen Clippings negativer Wahrscheinlichkeitsschätzungen.
Parametersensitivität:
- $\lambda$ : Das optimale Varianzparameter $\lambda$ liegt empirisch nahe bei 0.
- Stichprobengröße ( $m$ ): Eine geringe Anzahl von Stichproben ( $m=10$ ) reicht aus, um eine nahezu optimale Genauigkeit zu erreichen, wodurch die Kommunikation der Clients leichtgewichtig bleibt.
- Batch-Größe: Die Variation der Anzahl der teilnehmenden Clients beeinflusst die Konvergenzrate, verändert aber nicht grundlegend das optimale $\lambda$ .
Robustheit: Die Methode hält einen niedrigen absoluten Fehler über verschiedene Divergenz-Magnituden hinweg auf (von kleinen bis großen KL-Werten).

Bedeutung und Ansprüche

Das Paper behauptet, dass FedPriKL der erste kommunikationseffiziente föderierte Schätzer für die KL-Divergenz zwischen einer öffentlichen Referenz und einer privaten Population ist, der formale beispielbezogene differenzielle Privatsphäre bietet.

Die Bedeutung liegt in der Fähigkeit:

Drift-Erkennung zu ermöglichen: Bereitstellung eines privatsphäre-wahrenden Mechanismus für Plattformen, um Verteilungsverschiebungen zu erkennen und das Retraining von Modellen auszulösen, ohne sensible Nutzerdaten preiszugeben.
Unmöglichkeitsresultate zu umgehen: Durch die Beschränkung des Problems auf eine bekannte öffentliche Referenz umgeht das Verfahren die Unmöglichkeitsresultate bezüglich des Sketching unbekannter Verteilungen.
Nutzen und Privatsphäre auszubalancieren: Es zeigt, dass ein hoher Nutzen unter strengen Privatsphäre-Beschränkungen beibehalten werden kann, indem der Schritt der Rauschinjektion über eine vertrauenswürdige Komponente in die Post-Aggregation-Phase verschoben wird, wodurch der bei lokalen Perturbationsmethoden inhärente Bias vermieden wird.

Die Autoren merken an, dass die Abhängigkeit von einem vertrauenswürdigen Aggregator (oder TEE/SMC) ein praktischer Trade-off ist, der durch sichere Hardware oder Mehrparteienberechnung gelöst werden kann, und identifizieren die Aufhebung dieser Vertrauensannahme als Richtung für zukünftige Arbeiten.