Preserving Target Distributions With Differentially Private Count Mechanisms

1. Probleemstelling

In veel data-analyse-scenario's (bijv. volkstellingen, gezondheidsdata) worden gegevens gepresenteerd als een tabel met aantallen (counts), waarbij elke rij het aantal individuen in een specifieke categorie weergeeft. Om privacy te waarborgen, worden deze tabellen vaak gepubliceerd met toegevoegde ruis (differentially private mechanisms).

Er bestaat echter een fundamenteel spanningsveld tussen twee soorten vragen die onderzoekers willen beantwoorden:

1. Categorie-gebaseerde vragen: "Hoeveel gevallen zijn er in Colorado?" (vereist nauwkeurigheid per individuele rij).
2. Verdelingsvragen (Distribution questions): "Welk percentage van de vluchten heeft geen luchtmarshals?" of "Wat is de verdeling van het aantal leerlingen per school?" (vereist de juiste vorm van de verdeling van de aantallen, onafhankelijk van de specifieke categorie).

Standaard differentieel-private mechanismen (zoals Laplace of Geometrisch) zijn ontworpen om de fout per individuele telling te minimaliseren. Dit leidt echter tot statistische bias in de verdeling. Bijvoorbeeld, mechanismen die niet-negatieve uitkomsten garanderen, hebben de neiging om het aantal nullen in de verdeling kunstmatig op te blazen.

Het huidige dilemma is dat organisaties vaak twee aparte producten moeten maken: een geprijsde tabel met aantallen en een aparte geprijsde verdeling. Dit breekt de consistentie tussen de data, wat essentieel is voor betrouwbare statistische analyse. De auteurs stellen de vraag: Hoe kunnen we een geprijsde tabel van aantallen genereren die zowel nauwkeurig is voor individuele tellingen als de onderliggende verdeling van de aantallen behoudt?

2. Methodologie: Een Twee-Staps Kader

De auteurs introduceren een nieuw raamwerk dat bestaat uit twee fasen om dit probleem op te lossen:

Fase 1: Distributie-privatisering (Distribution Privatizer)

Omdat de ware verdeling ($\zeta$) van de data geheim moet blijven, wordt deze eerst geprijsd om een doelverdeling ($z$) te genereren.

• Nieuwe Mechanisme: De auteurs introduceren de Cyclische Laplace-mechanisme (Cyclic Laplace). In tegenstelling tot de standaard Laplace-mechanisme die onafhankelijke ruis toevoegt aan elke bin, voegt dit mechanisme ruis toe die tussen aangrenzende bins in de verdeling wordt "uitgewisseld".
• Werkingsprincipe: Het mechanisme berekent de verdeling $\zeta$, sample onafhankelijke Laplace-variabelen $L_i$, en geeft als output $V_i = \zeta_i + L_i - L_{i+1}$. Dit zorgt ervoor dat de cumulatieve som van de verdeling minder varieert dan bij standaard methoden, wat de nauwkeurigheid van de verdelingsvorm verbetert.

Fase 2: Constructie van het Tellingmechanisme (Constructor Algorithm)

Gegeven de doelverdeling $z$, moet een overgangsmatrix $T$ worden geconstrueerd die als vast punt (fixed point) $z$ heeft (d.w.z. als de invoer uit verdeling $z$ komt, is de verwachte uitvoer ook $z$).

• Wiskundige Theorie ($\epsilon$-scales): De auteurs ontwikkelen een algebraïsche theorie waarbij differentieel-private overgangsmatrices worden beschreven als conische combinaties van basis-elementen die ze $\epsilon$-scales noemen. Een $\epsilon$-scale is een kansverdeling waarbij de differentieel-private beperking voor elke paar aangrenzende posities "bindt" (d.w.z. de verhouding is exact $e^\epsilon$ of $e^{-\epsilon}$).
• Polytope Representatie: Ze definiëren een convex polytope $F$ (voor mechanismen met vast punt) en een representatiepolytope $R_F$. Ze bewijzen dat elke hoekpunt (extreme point) van $F$ kan worden gegenereerd door een relatief klein aantal $\epsilon$-scales.
• Algoritmen:
  • Exacte Oplossing: Voor kleine $n$ kan een lineaire programmering (LP) worden gebruikt om het mechanisme met de laagste telling-fout te vinden binnen $F$.
  • Heuristische Oplossing (Algorithm 1): Voor grote $n$ is LP te traag. De auteurs ontwikkelen een heuristisch algoritme dat kolommen van de matrix $T$ sequentieel vult met "single-peaked" $\epsilon$-scales. Dit algoritme heeft een looptijd van $O(n^2)$ en garandeert dat het resultaat een hoekpunt van het polytope is.

3. Belangrijkste Bijdragen

1. Het Concept van "Accuracy of Distribution": De paper formaliseert de nauwkeurigheid van de verdeling als een primaire prestatie-indicator, los van de nauwkeurigheid van individuele tellingen.
2. Cyclische Laplace-mechanisme: Een nieuw mechanisme voor het privatiseren van verdelingen dat superieur presteert aan bestaande histogram-mechanismen (zoals wavelet-transformaties of hiërarchische methoden) in termen van verdelingsfout.
3. Wiskundige Theorie van Vaste Punten: Een diepgaande analyse van de structuur van differentieel-private overgangsmatrices met een vast punt, gebruikmakend van $\epsilon$-scales en convex polytopes. Dit biedt een fundamenteel inzicht in de ruimte van mogelijke mechanismen.
4. Efficiënte Constructie-algoritmen: De ontwikkeling van een heuristisch algoritme (Algorithm 1) dat in $O(n^2)$ tijd een geldig mechanisme genereert, wat veel sneller is dan bestaande LP-oplossers voor grote datasets.
5. Empirische Validatie: Uitgebreide experimenten die de praktische haalbaarheid en de trade-offs aantonen.

4. Resultaten en Experimenten

De auteurs hebben hun methode getest op drie datasets: synthetische binomiale data, moordcijfers per county (sterk rechtsscheef) en schooldata (licht rechtsscheef). Ze vergeleken hun vaste-punt methoden met vier "unfixed" baselines (geen vast punt, zoals Truncated Geometric, Staircase, Discrete Gaussian).

• Nauwkeurigheid van de Verdeling: Het toevoegen van een vast-punt-beperking leidt tot een drastische verbetering in de nauwkeurigheid van de verdeling. Bijvoorbeeld, bij een privacy-budget ($\epsilon$) van 0.48 daalde de Wasserstein-afstand (fout in verdeling) met 94% ten opzichte van de beste baseline. Zelfs bij zeer lage budgets ($\epsilon=0.1$) presteerde de vaste-punt methode veel beter.
• Nauwkeurigheid van Tellingen: Er is een prijs te betalen: de nauwkeurigheid van individuele tellingen neemt licht af (meestal enkele procenten) omdat het mechanisme beperkt wordt tot het polytope $F$ (een strikt deel van de ruimte $U$). Echter, deze daling wordt door de auteurs als acceptabel beschouwd gezien de winst in verdelingsnauwkeurigheid.
• Looptijd: Standaard LP-oplossers (Simplex, Interior Point) zijn onpraktisch voor grote $n$. Het voorgestelde heuristische algoritme is echter zeer efficiënt ($O(n^2)$) en kan zelfs op een laptop een dataset met $n=2000$ in minder dan 10 seconden verwerken, wat vergelijkbaar is met de snelste unfixed baselines.
• Budgetverdeling: De auteurs stellen een "vuistregel" voor om het totale privacy-budget ($\epsilon_t$) te verdelen tussen de distributie-privatisering ($\epsilon_1$) en het tellingmechanisme ($\epsilon_2$), afhankelijk van de grootte van het budget.

5. Betekenis en Conclusie

Deze studie is significant omdat het een oplossing biedt voor het "consistentie-probleem" in differentieel privacy. Organisaties kunnen nu één enkel geprijsd data-product publiceren dat zowel robuust is voor individuele queries als voor verdelingsanalyses, zonder dat ze twee inconsistente datasets hoeven te genereren.

De kernboodschap is dat het opofferen van een klein deel van de nauwkeurigheid van individuele tellingen (vaak minder dan 5-10%) een enorme winst oplevert in de kwaliteit van de verdelingsdata. Dit maakt de methode zeer aantrekkelijk voor beleidsmakers en onderzoekers die geïnteresseerd zijn in trends, verdelingen en populatiestructuren, zoals bij volkstellingen of epidemiologische studies. De combinatie van een nieuwe wiskundige theorie en een praktisch, snel algoritme maakt dit een belangrijke stap voorwaarts in de toepassing van differentieel privacy op real-world data.