Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributions

Titel: Reveal-or-Obscure: Een Differentieel Privacy Algoritme voor Steekproeven uit Discrete Verdelingen

Auteurs: Naima Tasnim, Atefeh Gilani, Lalitha Sankar en Oliver Kosut (Arizona State University)

---

1. Probleemstelling

De groeiende beschikbaarheid van gevoelige data in sectoren zoals gezondheidszorg, financiën en rechtshandhaving vereist methoden voor privacybehoudende data-analyse. Een veelbelovende aanpak is het genereren van synthetische data die de statistische eigenschappen van de originele data nabootsen.

Het specifieke probleem dat in dit artikel wordt aangepakt, is differentieel privacy (DP) steekproeftrekking (DP sampling). In plaats van een volledige verdeling te leren of een hele dataset te publiceren, is het doel om één representatief steekproefelement te genereren uit een dataset van $n$ observaties, getrokken uit een onbekende discrete verdeling $P$ over een alfabet van grootte $k$.

De uitdaging ligt in het vinden van een balans tussen:

• Privacy: Het garanderen van $\epsilon$-differentieel privacy, zodat de output niet significant verschilt als één individuele datapunt in de invoer wordt veranderd of verwijderd.
• Nuttigheid (Utility): Het minimaliseren van de afstand tussen de verdeling van de gegenereerde steekproef en de ware onderliggende verdeling $P$.

Bestaande methoden (zoals die van Raskhodnikova et al. [5]) voegen expliciet ruis (bijv. Laplace-ruis) toe aan de geschatte empirische verdeling. Dit leidt vaak tot een hoge steekproefcomplexiteit (het aantal benodigde data-punten $n$) om een bepaalde nauwkeurigheid te bereiken, vooral bij strenge privacy-eisen.

2. Methodologie

De auteurs introduceren twee algoritmen: ROO (Reveal-or-Obscure) en DS-ROO (Data-Specific ROO).

A. Reveal-or-Obscure (ROO)

ROO is een conceptueel eenvoudig maar effectief algoritme dat geen expliciete ruis toevoegt aan de verdeling. In plaats daarvan maakt het een probabilistische keuze tussen twee acties:

1. Obscure (Verduisteren): Met een vaste kans $q$ wordt een steekproef getrokken uit een uniforme verdeling over het alfabet $[k]$. Dit "verbergt" de feitelijke data.
2. Reveal (Openbaren): Met kans $1-q$ wordt een steekproef willekeurig gekozen uit de oorspronkelijke dataset $X^n$. Dit "onthult" de empirische verdeling.

De parameter $q$ wordt zo gekozen dat aan de $\epsilon$-DP-eis wordt voldaan. De auteurs bewijzen dat deze structuur, hoewel identiek aan een eerder voorgesteld algoritme (Cheu en Nayak [1]), leidt tot een strikt betere analyse van de steekproefcomplexiteit.

B. Data-Specific ROO (DS-ROO)

Het standaard ROO-algoritme gebruikt een vaste $q$ die is ontworpen voor het ergste geval (waarbij één alfabet-element volledig ontbreekt in de dataset). Dit is echter inefficiënt voor datasets waar alle elementen redelijk vaak voorkomen.

DS-ROO generaliseert ROO door $q$ te maken tot een functie van de dataset zelf:

• Het algoritme berekent $m$, het minimaal aantal keren dat een element van het alfabet voorkomt in de dataset.
• De kans op verduisteren, $q_m$, wordt adaptief bepaald op basis van $m$.
• Logica: Als $m$ groot is (de verdeling is uniformer en er is minder kans dat het verwijderen van één punt de verdeling drastisch verandert), wordt $q_m$ kleiner. Dit betekent dat er minder vaak "verduisterd" wordt, wat de nuttigheid (nauwkeurigheid) verbetert zonder de privacy te schaden.
• In het ergste geval ($m=0$) degradeert DS-ROO tot het standaard ROO-algoritme.

3. Belangrijkste Bijdragen

1. Nieuw Algoritme (ROO): Een DP-steekproefalgoritme dat privacy bereikt door probabilistisch te kiezen tussen het openbaren van de empirische verdeling of het verduisteren ervan via een uniforme verdeling, zonder expliciete ruis toe te voegen aan de tellingen.
2. Verbeterde Complexiteitsgrens: De auteurs bewijzen dat ROO een strikt betere bovengrens voor de steekproefcomplexiteit biedt dan de state-of-the-art methoden [5] en [1]. Voor hogere waarden van $\epsilon$ (lagere privacy) wordt een exponentiële reductie in het benodigde aantal steekproeven $n$ bereikt.
3. Adaptieve Generalisatie (DS-ROO): Een techniek om $q$ dynamisch aan te passen op basis van de dataset-structuur (specifiek de minimale frequentie $m$). Dit zorgt voor een betere privacy-utility trade-off.
4. Empirisch Bewijs: Demonstratie dat DS-ROO bij dezelfde privacy-begroting ($\epsilon$) aanzienlijk betere nauwkeurigheid (kleinere totale variatieafstand) bereikt dan zowel het standaard ROO als de bestaande methoden.

4. Resultaten en Analyse

• Privacy: Zowel ROO als DS-ROO voldoen strikt aan de definitie van $\epsilon$-differentieel privacy. De bewijzen (in de appendix) tonen aan dat de verhouding tussen de waarschijnlijkheid van output op twee naburige datasets (die slechts één element verschillen) begrensd is door $e^\epsilon$.
• Steekproefcomplexiteit:
  • Voor ROO wordt de benodigde steekproefgrootte $n$ afgeleid als:
    $$n = \frac{k(1-\alpha) - 1}{\alpha(e^\epsilon - 1)}$$
    Waarbij $\alpha$ de nauwkeurigheid is (totale variatieafstand).
  • Deze formule toont aan dat $n$ exponentieel daalt naarmate $\epsilon$ toeneemt, wat een significant voordeel is ten opzichte van lineaire of slechtere schalingen in eerdere werken.
• Nuttigheid (Utility):
  • De totale variatieafstand ($d_{TV}$) voor ROO wordt begrensd door $\alpha = q(1 - 1/k)$.
  • Empirische experimenten (met $k=9, n=1000$) tonen aan dat DS-ROO de uitgangsverdeling veel nauwkeuriger benadert dan ROO en de methode van Raskhodnikova et al.
  • Figuur 3 in het artikel illustreert dat voor een gegeven $\epsilon$, de fout ($\alpha$) van DS-ROO aanzienlijk lager is.
  • De verbetering is het grootst bij verdelingen die niet extreem scheef zijn. Bij extreme scheefheid (waarbij een element kans 0 heeft) convergeert DS-ROO naar ROO.

5. Betekenis en Conclusie

Dit werk biedt een fundamentele doorbraak in het domein van differentieel privacy voor discrete verdelingen. De kerninzicht is dat privacy niet noodzakelijkerwijs vereist dat men ruis toevoegt aan de data; het kan ook worden bereikt door de strategie van steekproeftrekking te randomiseren.

• Efficiëntie: De methode reduceert de kosten (in termen van benodigde data) voor het genereren van privacy-bevattende synthetische data aanzienlijk.
• Adaptiviteit: DS-ROO introduceert een nieuwe richting in DP-algoritmen: het aanpassen van de privacy-mechanisme-parameters op basis van de waargenomen data-structuur (zolang dit binnen de privacy-garanties valt), wat leidt tot superieure prestaties in praktische scenario's.
• Toekomstperspectief: Hoewel het huidige werk zich richt op discrete verdelingen op een eindig alfabet, vormen deze resultaten een belangrijke stap naar het genereren van grotere synthetische datasets en het toepassen van vergelijkbare principes op complexere verdelingsklassen.

Kortom, de auteurs hebben aangetoond dat door slimme probabilistische keuzes ("Reveal-or-Obscure") en adaptieve strategieën, de traditionele afweging tussen privacy en nuttigheid in DP-steekproeven aanzienlijk kan worden verbeterd.