Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy

Technische Samenvatting: Dobrushin-coëfficiënten van private mechanismen voorbij Local Differential Privacy

Probleemstelling
Het artikel behandelt de beperkingen van het gebruik van Local Differential Privacy (LDP) als de enige metriek voor het kwantificeren van privacy in discrete Markov-kernels (privacy-mechanismen). Hoewel LDP breed wordt toegepast, merken de auteurs twee primaire problemen op:

1. Overmatige restrictiviteit: In statistische toepassingen zoals parameterschatting kan het bereiken van strikte LDP-garanties (kleine $\epsilon$) leiden tot een extreme degradatie van de schattingsprestaties (hoge minimax-risico's).
2. Contraintuïtief gedrag bij nul-waarschijnlijkheden: De standaard LDP-definitie levert een oneindige privacykosten op als een mechanisme een nul-waarschijnlijkheid toekent aan een output voor een gegeven input ($K_{Y|X=x}(y) = 0$). Dit behandelt mechanismen met aanzienlijke randomisatie (bijv. $K_1$ in het voorbeeld in het artikel) identiek aan identiteitsafbeeldingen of triviale mechanismen (bijv. $K_2$) als ze beide nul-entries bevatten, waardoor het onmogelijk wordt om "ruisende" en "deterministische" gedragingen te onderscheiden in termen van privacy-lekken.

Om deze problemen aan te pakken, onderzoeken de auteurs Dobrushin-coëfficiënten (contractiecoëfficiënten van de Total Variation-afstand) voor mechanismen die voldoen aan Pointwise Maximal Leakage (PML) in plaats van strikte LDP. PML is een pointwise adaptatie van maximal leakage die afhankelijk is van de datadistributie $P_X$. De auteurs analyseren specif specifiek mechanismen waarbij de inputdistributie $P_X$ een minimale waarschijnlijkheidsmassa heeft die begrensd is door een constante $c > 0$ (dat wil zeggen, $\min_x P_X(x) \geq c$). Dit framework staat de analyse toe van mechanismen met nul-waarschijnlijkheidstoewijzingen die onder LDP als "oneindig privaat" (of oneindig lekken) zouden worden beschouwd.

Methodologie
Het artikel maakt gebruik van informatie-theoretische instrumenten om grenzen af te leiden voor de contractie van $f$-divergenties door privacy-mechanismen.

• Definities: De auteurs definiëren $(\epsilon, c)$-PML als een beperking waarbij de PML begrensd wordt door $\epsilon$ voor alle inputdistributies in de verzameling $Q_X(c) = \{P_X : \min_x P_X(x) \geq c\}$. Dit generaliseert LDP, aangezien LDP overeenkomt met de limiet $c \to 0$.
• Contractiecoëfficiënten: Het centrale object van studie is de Dobrushin-coëfficiënt $\eta_{TV}(\epsilon, c)$, gedefinieerd als het supremum van de contractie van de Total Variation (TV)-afstand over alle kernels die voldoen aan $(\epsilon, c)$-PML.
• Reductie naar binaire outputs: De auteurs bewijzen dat om de maximale Dobrushin-coëfficiënt te vinden, het voldoende is om mechanismen met binaire outputruimtes ($|Y|=2$) te overwegen. Dit vereenvoudigt het optimalisatieprobleem aanzienlijk.
• Ongelijkheden: De afleiding maakt gebruik van Binette's ongelijkheid (een generalisatie van de reverse Pinsker-ongelijkheid) om de TV-grenzen uit te breiden naar algemene $f$-divergenties (zoals Relatieve Entropie en Hellinger-divergentie).

Belangrijkste Bijdragen en Resultaten

1. Bereikbare grenzen op Dobrushin-coëfficiënten:
   Het artikel leidt een strakke bovengrens af voor de Dobrushin-coëfficiënt $\eta_{TV}(\epsilon, c)$ voor elke kernel die voldoet aan $(\epsilon, c)$-PML. De grens wordt gegeven door:
   $$\eta_{TV}(\epsilon, c) \leq \min\left( \frac{e^\epsilon - 1}{e^\epsilon(1 - Nc) + 1}, 1 \right)$$
   waarbij $N$ de grootte van het input-alfabet is.

   • Regime-analyse: De auteurs tonen aan dat als $\epsilon \geq \log(2/Nc)$, de contractiecoëfficiënt 1 is (geen contractie treedt op). Als $\epsilon < \log(2/Nc)$, is de coëfficiënt strikt kleiner dan 1, wat duidt op privacy-geïnduceerde contractie.
   • Herstel van LDP: Naarmate $c \to 0$, herstelt de grens het bekende resultaat voor $\epsilon$-LDP: $\eta_{TV} \leq \frac{e^\epsilon - 1}{e^\epsilon + 1}$.
   • Mechanisme-constructie: Het artikel biedt expliciete constructies van mechanismen (specifiek binaire-output mechanismen) die deze grenzen bereiken, waarmee wordt aangetoond dat de grenzen bereikbaar zijn.

2. Extensie naar algemene $f$-divergenties:
   Met behulp van Binette's ongelijkheid breiden de auteurs de TV-grenzen uit naar algemene $f$-divergenties. Ze leiden sterke dataverwerkingsongelijkheden (SDPI's) af voor Relatieve Entropie en Hellinger-divergentie onder $(\epsilon, c)$-PML-beperkingen. Deze grenzen zijn afhankelijk van de TV-contractiefactor en de extremale ratio's van de outputdistributies.

3. Toepassing op Minimax-risico:
   De afgeleide grenzen worden toegepast op privaat minimax-schattingsrisico. Met behulp van Le Cam's twee-puntsmethode en de tensorisatie-eigenschap van $f$-divergenties, tonen de auteurs aan dat de steekproefcomplexiteit die nodig is om een bepaald risiconiveau te bereiken, toeneemt met een factor proportioneel aan de inverse van de private Dobrushin-coëfficiënt. Specifiek: als de coëfficiënt 1 is, komt de steekproefcomplexiteit overeen met de niet-private setting; als deze minder dan 1 is, wordt de effectieve steekproefomvang verminderd.

Betekenis en Claims
Het artikel claimt een genuanceerder framework te bieden voor het analyseren van privacy-mechanismen dan LDP alleen. Door de parameter $c$ te introduceren, kunnen de auteurs de privacy-lekken kwantificeren voor mechanismen die nul-waarschijnlijkheid-entries bevatten, die uitgesloten of problematisch worden behandeld onder standaard LDP.

• Strakkere grenzen: Voor mechanismen die voldoen aan LDP, zijn de voorgestelde grenzen strakker of aanpasbaarder dan eerdere resultaten wanneer de inputdistributie een bekende minimale massa $c$ heeft.
• Voorbij LDP: Het framework breidt de analyse van contractiecoëfficiënten uit naar de gehele klasse van discrete kernels, inclusief die welke geen eindige LDP-garantie voldoen.
• Operationele Interpretatie: De resultaten koppelen de theoretische contractiecoëfficiënten direct aan de degradatie van statistische schattingsprestaties, waardoor een instrument wordt geboden om de "kosten" van privacy te kwantificeren in termen van verhoogd risico of steekproefomvang.

De auteurs benadrukken dat hun werk bestaande LDP-resultaten herstelt als een speciaal geval, terwijl het een continue interpolatie biedt tussen uniforme distributiebeperkingen en het volledige LDP-regime, waarmee het "overmatige restrictiviteit" van LDP in specifieke statistische contexten aanpakt.