Optimal partition selection with Rényi differential privacy

Dit artikel presenteert een optimale algoritme voor partitie-selectie onder Rényi-differentiële privacy dat uitbreidt op eerdere werken door meerdere partities per gebruiker te ondersteunen, en toont aan dat het vrijgeven van frequenties een inherente kostenpost met zich meebrengt ten opzichte van mechanismen die alleen partities vrijgeven.

De kern

Stel je voor dat je een grote, geheime vergaderzaal hebt vol met mensen. Iedereen heeft een lijstje met onderwerpen waar ze over willen praten (bijvoorbeeld: "pizza", "katten", "ruimtereizen"). Je wilt een samenvatting maken van de populairste onderwerpen, maar je mag de identiteit van de individuele sprekers niet onthullen. Dit is het probleem van partitie-selectie in de wereld van privacy.

Deze paper, geschreven door onderzoekers van Google, lost een heel lastig raadsel op: Hoe kies je de populairste onderwerpen, zodat je zo veel mogelijk waardevolle informatie vrijgeeft, maar niemand kan achterhalen wie wat heeft gezegd?

Hier is de uitleg, vertaald naar alledaagse taal met een paar creatieve vergelijkingen.

1. Het Probleem: De "Stille" Vergaderzaal

Stel je voor dat je een spelletje doet waarbij je de top 10 onderwerpen moet kiezen. Maar er is een strenge regel: als iemand anders naar je lijstje kijkt, mag hij of zij niet kunnen zien of jij specifiek "pizza" hebt genoemd.

In het verleden gebruikten onderzoekers een simpele truc: ze telden hoeveel keer een woord werd genoemd en voegden daar wat "ruis" (statistisch lawaai) aan toe, alsof je een beetje wazig door een raam kijkt. Als het getal na het lawaai nog steeds hoog genoeg was, werd het woord op de lijst gezet.

• Het probleem: Deze oude methode (zoals de "Gaussian-mechanisme" of "Laplace-mechanisme") was niet optimaal. Het was alsof je een deur openhield, maar er bleef een kier open staan waar te veel privacy door lekte, of je liet juist te veel waardevolle informatie achterwege.

2. De Oplossing: De "Slimme" Deurwachter (SNAPS)

De auteurs van dit paper hebben een nieuwe, slimmere deurwachter bedacht, genaamd SNAPS (Smooth Norm-Aware Partition Selection).

De Analogie van de Deurwachter:
Stel je voor dat je een deurwachter hebt die beslist wie er binnen mag.

• De oude methode: De deurwachter gooide een dobbelsteen. Als je 5 keer "pizza" zei, gooide hij een dobbelsteen. Als hij een 6 gooide, ging de deur open. Dit was willekeurig en niet erg efficiënt.
• De nieuwe methode (SNAPS): Deze deurwachter is een wiskundig genie. Hij kijkt niet alleen naar het aantal keer dat je "pizza" zei, maar berekent precies hoe "veilig" het is om de deur te openen, gebaseerd op een nieuwe, strengere privacy-regel (Rényi-differentiële privacy).

Waarom is dit beter?
De nieuwe methode gebruikt een soort "slimme ruis". In plaats van willekeurig lawaai toe te voegen, past de deurwachter de ruis precies aan op de situatie.

• Voorbeeld: Als je 100 keer "pizza" zegt, is het heel veilig om de deur open te doen. De oude methode deed dit misschien ook, maar met een onnodig groot risico. De nieuwe methode doet het met een perfect risico, waardoor je meer populaire woorden op je lijstje kunt zetten zonder de privacy te schenden.

3. Het Grote Geheim: De "Prijs" van het Tellen

Een van de meest fascinerende ontdekkingen in dit paper is een soort "verborgen kostenpost".

Stel je voor dat je niet alleen wilt weten welke woorden populair zijn (bijv. "pizza"), maar ook precies hoe vaak ze zijn gezegd (bijv. "100 keer").

• De ontdekking: Als je de deurwachter dwingt om ook het exacte aantal (de frequentie) te onthullen, moet je een hogere prijs betalen in de vorm van meer ruis. Het is alsof je de deurwachter vraagt om niet alleen de deur open te doen, maar ook om te tellen hoeveel mensen er precies binnenlopen. Dat kost meer energie (privacy-budget).
• De les: Als je alleen de lijst met populaire woorden wilt (en niet het exacte aantal), is de oude methode (die ook het aantal probeert te onthullen) eigenlijk te dom. Je kunt beter een methode kiezen die alleen de deur open doet. Dat levert je veel meer waardevolle informatie op voor dezelfde prijs.

4. De Test: Het Winnen van de "Populaire Woorden"-Wedstrijd

De auteurs hebben hun nieuwe deurwachter (SNAPS) getest in de echte wereld. Ze hebben hem ingezet in bestaande systemen die worden gebruikt voor grote datasets (zoals Reddit-berichten, Twitter-tweets en Amazon-reviews).

Het resultaat:
Het was alsof je in een race een oude, zware fiets vervangt door een strakke racefiets.

• In alle tests bleek dat hun nieuwe methode 10% tot 20% meer populaire onderwerpen kon vrijgeven dan de oude methoden, terwijl de privacy precies even goed bleef.
• Het werkt zowel als je alles in één keer doet (parallel) als stap voor stap (sequentieel).

Samenvatting in één zin

De auteurs hebben een nieuwe, slimmere manier bedacht om populaire onderwerpen te kiezen in een privé-omgeving; ze laten zien dat je veel meer waardevolle informatie kunt vrijgeven als je stopt met proberen het exacte aantal te tellen en in plaats daarvan een slimme, niet-willekeurige "deurwachter" gebruikt die precies weet hoe hij de privacy-regels moet toepassen.

Kortom: Ze hebben de sleutel gevonden om de deur van de waarheid een stukje wijd open te zetten, zonder dat de dieven (privacy-bots) erdoorheen kunnen gluren.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Optimal partition selection with Rényi differential privacy" van Harrison en Manurangsi, in het Nederlands.

Probleemstelling

Het paper adresseert het partitie-selectieprobleem in de context van differentieel privacy (DP). Dit probleem treedt vaak op bij privé data-analyse, bijvoorbeeld bij het bepalen van de output-partities (sleutels) in een GROUP BY-query of bij het vrijgeven van datasets met hoge dimensionaliteit (zoals URL's of strings).

• De uitdaging: Elke gebruiker bezit een set partities (mogelijk uit een onbegrensde ruimte). Het doel is om de maximale set van partities vrij te geven die in de dataset voorkomen, terwijl strikte privacybeperkingen worden nageleefd.
• Beperking: De mechanismen mogen geen "false positives" introduceren; ze mogen alleen een subset van de werkelijke partities vrijgeven.
• Context: Eerdere werken (zoals [DVGM21]) hebben een optimale oplossing gevonden voor $(\varepsilon, \delta)$-DP wanneer elke gebruiker slechts één partitie bijdraagt. Echter, in scenario's waar gebruikers meerdere partities kunnen bijdragen, of waar composities van mechanismen plaatsvinden, zijn bestaande methoden (zoals het toevoegen van Laplace- of Gaussisch ruis) niet optimaal.

Methodologie

De auteurs gebruiken Rényi Differentieel Privacy (RDP) en de variant $\delta$-benaderde RDP als privacy-maatstaf. RDP biedt strakkere compositieseigenschappen dan standaard DP, wat essentieel is voor complexe queries.

De kern van de methodologie bestaat uit drie onderdelen:

1. Optimalisatie voor één partitie per gebruiker:

   • De auteurs generaliseren het optimale algoritme van [DVGM21] naar de $\delta$-benaderde $(\alpha, \varepsilon)$-RDP setting.
   • Ze definiëren een optimaal partitie-selectie primitief $\pi^*(n)$, waarbij $n$ de telling van een partitie is. Dit primitief bepaalt de release-kans voor een partitie.
   • Het algoritme berekent $\pi^*(n)$ iteratief door de maximale waarde $p$ te vinden zodat de Rényi-divergentie tussen de Bernoulli-verdelingen $Ber(p)$ en $Ber(\pi^*(n-1))$ binnen de privacygrenzen blijft.
   • Ze bewijzen dat dit mechanisme optimaal is voor het geval $\Delta_1 = 1$ (elke gebruiker draagt maximaal één partitie bij).

2. Gewogen Partitie Selectie (SNAPS Mechanisme):

   • Voor het geval dat gebruikers meerdere partities bijdragen of gewogen vectoren hebben (bijv. $L_2$-norm begrensd), bestaat er geen enkel "optimaal" mechanisme in de strikte zin.
   • De auteurs introduceren SNAPS (Smooth Norm-Aware Partition Selection). Dit is een gewogen primitief dat privacyverlies "glad" maakt afhankelijk van het gewicht dat een gebruiker bijdraagt.
   • SNAPS kan worden gebruikt als een "drop-in" vervanging voor het Gaussische mechanisme in bestaande adaptieve algoritmen (zoals PolicyGaussian en MAD2R), zonder dat de ruisvector zelf hoeft te worden vrijgegeven.

3. Additieve Ruis vs. Niet-Additieve Mechanismen:

   • De auteurs onderzoeken het fundamentele verschil tussen mechanismen die additieve ruis toevoegen (en vervolgens drempelen) en de optimale niet-additieve mechanismen.
   • Additieve mechanismen hebben het voordeel dat ze zowel de partitie als de (ruisbezoedelde) telling kunnen vrijgeven.
   • De auteurs formuleren een convex optimalisatieprobleem om het beste additieve ruismechanisme te vinden voor een gegeven utility. Ze tonen aan dat er een numerieke scheiding bestaat in privacy tussen additieve en niet-additieve mechanismen.

Belangrijkste Bijdragen

1. Optimaal Algoritme voor RDP:

   • Een nieuw algoritme dat de optimale partitie-selectie biedt onder $\delta$-benaderde $(\alpha, \varepsilon)$-RDP voor gebruikers die één partitie bijdragen. Dit herwint het resultaat van [DVGM21] als $\alpha \to \infty$, maar biedt betere utility voor eindige $\alpha$ door strakkere composities.
   • Een bewijs dat er geen optimaal mechanisme bestaat wanneer gebruikers meerdere partities bijdragen ($\Delta_1 \neq 1$).

2. Het SNAPS Mechanisme:

   • Een nieuw, praktisch mechanisme voor gewogen partitie-selectie dat werkt met $L_r$-norm grenzen.
   • SNAPS kan direct worden ingepluggen in state-of-the-art adaptieve algoritmen (MAD2R en PolicyGaussian) om de prestaties te verbeteren, vooral wanneer de exacte frequentie van de partities niet nodig is.

3. De "Kosten" van het Vrijgeven van Tellingen:

   • De auteurs tonen aan dat er een inherente privacy-kost is aan het vrijgeven van de frequentie (telling) van een partitie via additieve ruis.
   • Als de telling niet nodig is, zijn additieve ruismechanismen (zoals Laplace of Gaussisch) sub-optimaal vergeleken met de door hen ontwikkelde niet-additieve mechanismen.

Resultaten

• Experimentele Validatie:

  • De auteurs hebben SNAPS geïntegreerd in twee bestaande algoritmen: MAD2R en PolicyGaussian.
  • Tests zijn uitgevoerd op diverse datasets (Reddit, Wiki, Twitter, Finance, Amazon, IMDb).
  • Resultaat: Het gebruik van SNAPS leidt tot een 10-20% verbetering in de grootte van de vrijgegeven output (utility) vergeleken met de originele algoritmen die het Gaussische mechanisme gebruikten, onder dezelfde privacybudgetten ($\varepsilon=1, \delta=10^{-5}$).

• Theoretische Scheiding:

  • Numerieke experimenten tonen een duidelijke scheiding in privacy-garanties tussen de optimale niet-additieve mechanismen ($\pi^*$) en de beste mogelijke additieve ruismechanismen.
  • Terwijl additieve mechanismen in de limiet $\alpha \to \infty$ (strikte DP) bijna optimaal zijn (zoals getoond in [DVGM21]), is er in het regime van eindige $\alpha$ (RDP) een significant verlies in utility als men zich beperkt tot additieve ruis.

Significantie

Dit paper is significant voor de gemeenschap van differentieel privacy om de volgende redenen:

1. Verbeterde Utility: Het biedt een praktische manier om de utility van partitie-selectie aanzienlijk te verhogen door over te stappen van standaard additieve ruis (Gaussisch/Laplace) naar geoptimaliseerde niet-additieve mechanismen, vooral in compositiescenario's.
2. Fundamenteel Inzicht: Het onthult een fundamentele trade-off: het vrijgeven van de telling van een partitie (via additieve ruis) kost meer privacy dan alleen het vrijgeven van de partitie zelf. Dit helpt beleidsmakers en ontwikkelaars om betere keuzes te maken: als de telling niet nodig is, moet men niet vasthouden aan additieve mechanismen.
3. Toepasbaarheid: De SNAPS-methode is direct toepasbaar in bestaande systemen (zoals privé SQL-query engines) als vervanging voor de Gaussische mechanismen, wat leidt tot direct betere resultaten zonder de privacy-begroting te verhogen.
4. RDP als Standaard: Het paper onderstreept het belang van het gebruik van Rényi DP voor composities, aangezien dit leidt tot strakkere grenzen en betere prestaties dan traditionele $(\varepsilon, \delta)$-DP benaderingen in complexe workflows.

Kortom, het paper levert zowel theoretische optimaliteit als praktische algoritmen die de staat van de kunst voor privé partitie-selectie aanzienlijk verbeteren.