🤖 machine learning

Federated and differentially private estimation of KL divergence

Dit artikel introduceert FedPriKL, een nieuwe differentieel private methode voor het schatten van de KL-divergentie in federatieve omgevingen die onbevooroordeelde nauwkeurigheid met een lage variantie bereikt met een begrensde sensitiviteit, terwijl de communicatie-overhead wordt geminimaliseerd in vergelijking met bestaande baselines.

Oorspronkelijke auteurs: Sayan Biswas, Graham Cormode, Carsten Maple, Mary Scott

Gepubliceerd 2026-08-24

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Sayan Biswas, Graham Cormode, Carsten Maple, Mary Scott

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

In de moderne wereld van data is informatie vaak verspreid over miljoenen individuele apparaten, van smartphones tot draagbare gezondheidstrackers. Deze verspreide aard creëert een krachtige manier om over de wereld te leren zonder ieders data in één centrale kluis te hoeven verzamelen. Deze aanpak, bekend als federated learning, stelt een centraal systeem in staat om modellen te bouwen door apparaten te vragen berekeningen uit te voeren op hun eigen lokale data en vervolgens alleen de resultaten te delen. Echter, een kritieke uitdaging blijft: hoe weten we of de gebruikte data in de loop van de tijd verandert? Als het gedrag van de mensen die een app gebruiken verschuift, kunnen de modellen die op oude data zijn gebouwd, inaccuraat of irrelevant worden. Om dit op te lossen, moeten analisten het verschil meten tussen de huidige data en een bekende standaard, een taak die normaal gesproken vereist dat men de ruwe data inziet. Maar in een wereld waar privacy van cruciaal belang is, is het onthullen van de ruwe data vaak onmogelijk. De oplossing vereist een manier om dit verschil wiskundig te meten zonder ooit de individuele details te onthullen die de data vormen.

Onderzoekers van EPFL, de Universiteit van Oxford, de Universiteit van Warwick en de Infectious Diseases Data Observatory hebben een nieuwe methode ontwikkeld genaamd FedPriKL om exact dit probleem op te lossen. Hun werk richt zich op een specifieke wiskundige maatstaf die wordt gebruikt om twee sets data te vergelijken, een instrument dat ons vertelt hoeveel één groep informatie is afgedwaald van een referentiepunt. In dit scenario is het referentiepunt een publieke standaard waar iedereen het over eens is, terwijl de andere groep de private, gevoelige data is die gebruikers op hun apparaten bewaren. Het doel is om de afstand tussen deze twee groepen te berekenen zonder dat de centrale server de individuele records ziet. De onderzoekers hebben een protocol ontwikkeld waarmee een centrale coördinator een kleine, willekeurige selectie van apparaten kan vragen om te controleren hoe vaak bepaalde items voorkomen in hun lokale data. Deze apparaten sturen vervolgens alleen de tellingen voor die specifieke items terug, die vervolgens veilig worden gecombineerd. Om te garanderen dat zelfs deze tellingen niet naar een enkel persoon herleid kunnen worden, voegt het systeem een zorgvuldig berekende hoeveelheid wiskundige ruis toe aan het uiteindelijke resultaat.

Het team kwam tot de conclusie dat hun methode werkt met een hoge mate van nauwkeurigheid, terwijl strikte privacygaranties worden gehandhaafd. Ze hebben wiskundig bewezen dat hun aanpak een onbevooroordeelde schatting oplevert, wat betekent dat het resultaat gemiddeld correct is, en dat de hoeveelheid ruis die nodig is om de privacy te beschermen klein genoeg is om het nut van de data niet te ruïneren. In hun experimenten testten ze het systeem met behulp van een grote dataset van handgeschreven cijfers, wat een realistische scenario simuleert waarbij duizenden gebruikers data bijdragen. Ze ontdekten dat door zorgvuldig te kiezen hoeveel apparaten worden gevraagd en hoeveel ruis er wordt toegevoegd, het systeem resultaten kan produceren die bijna net zo nauwkeurig zijn als wanneer er geen privacybescherming zou worden gebruikt. Dit is een significante verbetering ten opzichte van eerdere methoden waarbij apparaten probeerden hun data te verbergen door ruis toe te voegen voordat ze deze verzonden, een techniek die vaak leidde tot inaccurate resultaten. De nieuwe methode houdt de toevoeging van ruis aan het einde van het proces, nadat de data veilig is gecombineerd, wat de integriteit van de meting bewaart.

De onderzoekers verkenden ook hoe verschillende instellingen de uitkomst beïnvloeden. Ze ontdekten dat het systeem goed werkt, zelfs wanneer slechts een klein deel van de totale gebruikers wordt gevraagd om deel te nemen in een gegeven ronde, en dat de hoeveelheid data die elke gebruiker moet verzenden zeer klein is, vaak minder dan één kilobyte. Dit maakt het systeem praktisch voor apparaten met een beperkte batterijduur en geheugen. De studie toonde aan dat de methode accuraat onderscheid kan maken tussen kleine veranderingen in data en grote veranderingen, wat essentieel is voor het beslissen wanneer een computermodel moet worden bijgewerkt. Hoewel de huidige versie van het systeem vertrouwt op een vertrouwde tussenstap om de data veilig te combineren, hebben de onderzoekers aangetoond dat deze stap kan worden uitgevoerd met bestaande beveiligde hardware of geavanceerde cryptografische technieken, waardoor geen enkele entiteit ooit de ruwe data ziet. Het werk biedt een concreet pad vooruit om datatrends te monitoren op een manier die de privacy van de gebruiker respecteert, waardoor organisaties hun modellen accuraat kunnen houden zonder de vertrouwelijkheid van de individuen die de data genereren in gevaar te brengen.

Technische Samenvatting: FedPriKL – Federate en Differentieel Privé Estimatie van de KL-divergentie

Probleemstelling

In moderne federated learning en analytics is het monitoren van distributieverschuivingen (distribution drift) een cruciale taak om te bepalen wanneer modellen hertraind of gefinetuned moeten worden. Dit vereist het vergelijken van de empirische distributie van de data die door gedistribueerde clients wordt vastgehouden ( $P$ ) met een vaste publieke referentiedistributie ( $\Pi$ ). Het direct delen van clientdata of volledige histogrammen is echter vaak onhaalbaar vanwege hoge communicatiekosten en privacybeperkingen.

Bestaande benaderingen kampen met aanzienlijke hindernissen:

Privacy: Centrale verzameling van samples schendt de privacy van gebruikers.
Onmogelijkheidsresultaten: De Shift Invariance Theorem [9] impliceert dat het schatten van de KL-divergentie tussen twee onbekende distributies in een ruimte die kleiner is dan de domeingrootte, onmogelijk is.
Communicatie: Het verzenden van volledige histogrammen van clients naar een server is voor grote domeinen qua bandbreedte onhaalbaar.
Bias in Lokale Perturbatie: Standaard Local Differential Privacy (LDP) benaderingen, waarbij clients ruis toevoegen vóór aggregatie, introduceren aanzienlijke bias bij het schatten van niet-lineaire functies zoals de KL-divergentie, met name bij het afhandelen van kleine waarschijnlijkheidsmassa's.

Het artikel adresseert het probleem van het schatten van $D_{KL}(\Pi \parallel P)$ in een horizontale federated setting waar $P$ wordt gedefinieerd door de geaggregeerde data van $n$ clients, en $\Pi$ een bekende publieke benchmark is. Het doel is om formele example-level differential privacy (DP) te bereiken terwijl de communicatieoverhead wordt geminimaliseerd en de nauwkeurigheid van de estimator wordt behouden.

Methodologie: FedPriKL

De auteurs stellen FedPriKL voor, een sampling-gebaseerd protocol dat gebruikmaakt van een "trusted aggregator"-model om een unbiased estimatie onder DP te bereiken. De kern van de technische innovatie is een unbiased Monte Carlo-estimator gebaseerd op likelihood ratios, gecombineerd met veilige aggregatie en gekalibreerde ruisinjectie.

Kerncomponenten:

Unbiased Monte Carlo Estimator:
In plaats van de volledige divergentie te berekenen, gebruikt de methode $m$ punten $x_i$ gesampled uit de referentiedistributie $\Pi$ . Voor elk sample schat het protocol de likelihood ratio $r(x) = P(x)/\Pi(x)$ .
Gebruikmakend van de identiteit afgeleid in Fact IV.2, wordt de KL-divergentie geschat via de functie:
$\Phi(r(x), \lambda) = \lambda(r(x) - 1) - \ln(r(x))$
De verwachtingswaarde van deze functie over samples van $\Pi$ is gelijk aan $D_{KL}(\Pi \parallel P)$ . De parameter $\lambda$ controleert de variantie van de estimator.
Protocol Workflow (Algoritme 2):
- Sampling: De server selecteert disjuncte batches van clients ( $C_t$ ) en samplet punten $x_{i,t}$ uit $\Pi$ .
- Secure Aggregation (SecAgg): Clients berekenen de frequentie van gesamplede punten in hun lokale datasets. Deze frequenties worden geaggregeerd met behulp van een secure aggregation protocol (bijv. Shamir's secret sharing) om de globale empirische waarschijnlijkheidsmassa $P(x)$ te berekenen zonder individuele clientdata te onthullen.
- Trusted Aggregator Processing: De geaggregeerde waarschijnlijkheden worden naar een vertrouwde aggregator gestuurd. De aggregator berekent de likelihood ratios $r(x)$ , past de niet-lineaire transformatie $\Phi$ toe, en voegt gekalibreerde Gaussische ruis ( $\eta_{\epsilon, \delta}$ ) toe aan het resultaat.
- Final Estimation: De genoiseerde getransformeerde waarden worden gemiddeld om de uiteindelijke DP-schatting te produceren.
Privacy Mechanisme:
In tegen tegenover baseline benaderingen waar clients ruis lokaal toevoegen (pre-aggregatie), voegt FedPriKL ruis toe na de secure aggregatie maar vóór de niet-lineaire transformatie definitief wordt afgerond. Dit voorkomt de bias die wordt geïntroduceerd door het afknippen (clipping) van negatieve waarden in lokale ruis (een veelvoorkomend probleem in LDP). De sensitiviteit van de estimator is begrensd (Theorem IV.4 en IV.5), wat nauwkeurige ruis-kalibratie mogelijk maakt om $(\epsilon, \delta)$ -DP te voldoen.
Trust Model:
Het protocol gaat uit van een vertrouwde aggregator (of een TEE/SMC realisatie) die alleen de beveiligd geaggregeerde statistieken van de gesamplede punten ziet, en niet de ruwe clientdata. De server is "honest-but-curious" en ontvangt alleen de uiteindelijke genoiseerde schatting.

Belangrijkste Bijdragen

Probleemformalisering: Het artikel formaliseert het probleem van het berekenen van de KL-divergentie in een federated setting met formele differential privacy garanties, specifiek gericht op het geval van een publieke referentie versus een private empirische distributie.
FedPriKL Algoritme: De auteurs presenteren de eerste communicatie-efficiënte, sampling-gebaseerde federated estimator voor $D_{KL}(\Pi \parallel P)$ die formele example-level DP biedt.
Theoretische Analyse:
- Unbiasedness: Bewijs dat de estimator unbiased is (Theorem IV.7).
- Sensitivity Bounds: Vastgestelde begrensde sensitiviteit voor de estimator, wat de afleiding van optimale ruisschalen mogelijk maakt (Theorems IV.4, IV.5).
- Variantie Karakterisering: Bood een theoretische karakterisering van de variantie van de estimator als functie van $\lambda$ , $\epsilon$ , en de samplegrootte, en leidde de optimale $\lambda$ af om de variantie te minimaliseren (Theorem V.1, V.3).
Communicatie Efficiëntie: De per-client payload is onafhankelijk van de domeingrootte. Voor een domein van $2^{16}$ elementen blijft de payload onder de 1 KB.

Experimentele Resultaten

De auteurs evalueerden FedPriKL op de FEMNIST dataset (handgeschreven cijfers gepartitioneerd per schrijver), waarbij ze het vergeleken met een niet-private estimator en een baseline LDP benadering (Algoritme 1).

Accuracy vs. Privacy: FedPriKL bereikt een nauwkeurigheid die vergelijkbaar is met de niet-private estimator wanneer het privacybudget $\epsilon$ gematigd is ( $0.5 \le \epsilon \le 1.0$ ).
Superioriteit over Baseline: FedPriKL presteert aanzienlijk beter dan de baseline (lokale perturbatie) in termen van nauwkeurigheid en stabiliteit. De baseline lijdt onder bias door de noodzakelijke clipping van negatieve waarschijnlijkheidsschattingen.
Parameter Sensitiviteit:
- $\lambda$ : De optimale variantieparameter $\lambda$ wordt empirisch gevonden dicht bij 0.
- Sample Grootte ( $m$ ): Een klein aantal samples ( $m=10$ ) is voldoende om een bijna optimale nauwkeurigheid te bereiken, waardoor de clientcommunicatie lichtgewicht blijft.
- Batch Grootte: Het variëren van het aantal participerende clients beïnvloedt de convergentiesnelheid, maar verandert de optimale $\lambda$ niet fundamenteel.
Robuustheid: De methode behoudt een lage absolute fout over verschillende divergentie-magnitudes (van kleine tot grote KL-waarden).

Betekenis en Claims

Het artikel claimt dat FedPriKL de eerste communicatie-efficiënte federated estimator voor de KL-divergentie tussen een publieke referentie en een private populatie is die formele example-level differential privacy biedt.

De betekenis ligt in het vermogen om:

Drift Detectie Mogelijk te Maken: Een privacy-bewarend mechanisme bieden voor platforms om distributieverschuivingen te detecteren en modelhertraining te triggeren zonder gevoelige gebruikersdata bloot te leggen.
Onmogelijkheid te Omzeilen: Door het probleem te beperken tot een bekende publieke referentie, omzeilt het de onmogelijkheidsresultaten met betrekking tot het sketchen van onbekende distributies.
Utility en Privacy te Balanceren: Het demonstreert dat een hoge utility behouden kan blijven onder strikte privacybeperkingen door de ruisinjectiestap naar een post-aggregatie fase te verplaatsen via een vertrouwde component, waardoor de bias inherent aan lokale perturbatiemethoden wordt vermeden.

De auteurs merken op dat de afhankelijkheid van een vertrouwde aggregator (of TEE/SMC) een praktische afweging is die kan worden opgelost via beveiligde hardware of multi-party computation, en zij identificeren het wegnemen van deze vertrouwen-aanname als een richting voor toekomstig werk.