Technische Samenvatting: Grenzen van het Personaliseren van Differential Privacy-budgetten

Probleemstelling

Bij Differential Privacy (DP) vormt het selecteren van een geschikt privacy-budget ($\epsilon$) een fundamentele uitdaging: een kleiner $\epsilon$ garandeert sterkere privacy, maar verslechtert de bruikbaarheid (nauwkeurigheid) van de berekening. Waar klassieke DP een uniform budget oplegt aan alle deelnemers, is een natuurlijke uitbreiding gepersonaliseerde (of heterogene) DP, waarbij elke agent $i$ een specifiek privacyvereiste $\epsilon_i$ heeft. Deze aanpak wordt gemotiveerd door het feit dat agenten uiteenlopende privacyhoudingen hebben en dat personalisatie theoretisch de ruimte van haalbare algoritmen uitbreidt, wat potentieel de afweging tussen privacy en nauwkeurigheid kan verbeteren.

Echter, volledig gepersonaliseerde mechanismen (bijvoorbeeld affiene schatters die datapunten herbekijken op basis van individuele $\epsilon_i$) zijn complex om te auditeren, te communiceren en aan te passen. Een eenvoudiger alternatief is een drempel-schatting (thresholding estimator), die datapunten met te strenge privacyvereisten verwijdert en een enkel, zorgvuldig gekozen privacy-budget toepast op de overige data.

De centrale vraag die in dit artikel wordt behandeld is: Levert de complexiteit van volledige personalisatie aanzienlijke winst op in bruikbaarheid (specifiek voor schatting van het gemiddelde) in vergelijking met de eenvoudigere drempel-baseline? De auteurs onderzoeken of de "marginale waarde" van volledige personalisatie substantieel is of dat de winsten in de meeste praktische regimes bescheiden zijn.

Methodologie en Model

De auteurs focussen op het probleem van schatting van het gemiddelde voor een verdeling $P$ met begrenste steun $[-1/2, 1/2]$, gegeven $n$ i.i.d. datapunten waarbij elk punt $x_i$ een specifiek privacy-budget $\epsilon_i$ heeft.

Vergelijkde Schatters

1. Optimale Affiene Schatter (Volledig Gepersonaliseerd):

   • Dit is de best bekende schatter voor heterogene DP. Deze maakt gebruik van een gewogen gemiddelde van de datapunten: $\hat{\mu} = \sum w_i x_i + Z$, waarbij $Z$ Laplace-ruis is.
   • De gewichten $w_i$ worden geoptimaliseerd om de Gemiddelde Kwikwafel (MSE) te minimaliseren.
   • De optimale strategie omvat het "clipsen" van privacy-niveaus: er wordt een drempel $\tau$ geselecteerd en de effectieve privacy-niveaus worden ingesteld op $\bar{\epsilon}_i = \min(\epsilon_i, \tau)$. De gewichten zijn evenredig met deze geknipte niveaus ($w_i \propto \bar{\epsilon}_i$), en de ruisschaal wordt bepaald door de maximale gevoeligheid ten opzichte van de geknipte budgetten.
   • De MSE wordt gekarakteriseerd als:
     $$\text{MSE}_{\text{aff}}(\epsilon) = \inf_{\tau>0} \left( \frac{q_\tau}{4s_\tau^2} + \frac{2}{s_\tau^2} \right)$$
     waarbij $s_\tau = \sum \min(\epsilon_i, \tau)$ en $q_\tau = \sum \min(\epsilon_i, \tau)^2$.

2. Unieke-Drempel $\epsilon$-Schatter (Vereenvoudigde Baseline):

   • Deze schatter selecteert één enkel globaal drempel $\epsilon$.
   • Het verwijdert alle datapunten waarbij de individuele vereiste $\epsilon_i < \epsilon$.
   • Het past een uniform privacy-budget $\epsilon$ toe op de overige $n_\epsilon$ datapunten.
   • De MSE wordt geminimaliseerd over de keuze van $\epsilon$:
     $$\text{MSE}_{\text{thr}}(\epsilon) = \inf_{\epsilon>0} \left( \frac{1}{4n_\epsilon} + \frac{2}{\epsilon^2 n_\epsilon^2} \right)$$

Metriek

De prestaties worden gemeten aan de hand van de Verdelings-robuste Gemiddelde Kwikwafel (worst-case MSE over verdelingen met begrenste steun). De auteurs analyseren de benaderingsratio $\frac{\text{MSE}_{\text{thr}}}{\text{MSE}_{\text{aff}}}$ om het verlies in bruikbaarheid te kwantificeren wanneer de eenvoudige drempelaanpak wordt gebruikt in plaats van het optimale affiene mechanisme.

Belangrijkste Bijdragen en Resultaten

Het artikel biedt nauwkeurige grenzen voor de prestatiekloof tussen de drempel-schatting en de optimale affiene schatter over drie distincte regimes:

1. Combinatie van Publieke en Private Data

• Situatie: Een mengsel van $n_1$ private datapunten (budget $\epsilon_1$) en $n_2$ publieke datapunten (effectief $\epsilon_2 = \infty$).
• Resultaat: De drempel-schatting bereikt een 2-benadering van de optimale affiene schatter.
• Inzicht: De kloof is strak en nadert 2 slechts in een smal gebied waar de bijdragen aan de variantie van de private en publieke delen in evenwicht zijn. In de meeste andere configuraties ligt de ratio dicht bij 1, wat wijst op een verwaarloosbare winst door personalisatie.

2. Twee Eindige Privacy-niveaus

• Situatie: Datapunten hebben één van twee eindige privacy-budgetten, $\epsilon_1 < \epsilon_2$.
• Resultaat: De benaderingsratio verslechtert van 2 naar 4.
• Inzicht: De auteurs leveren een tegenvoorbeeld dat de ratio groter dan 2 kan zijn. Echter, zij bewijzen dat de ratio begrensd is door 4, ongeacht de specifieke waarden van $\epsilon_1, \epsilon_2$ of de aantallen data. Dit impliceert dat zelfs in deze iets complexere situatie de drempelaanpak het overgrote deel van de bruikbaarheid vastlegt.

3. Willekeurig Aantal Privacy-niveaus ($m$ niveaus)

• Situatie: Datapunten hebben $m$ distincte privacy-niveaus ($0 < \epsilon_1 < \dots < \epsilon_m$).
• Resultaat: Er is in het algemeen geen constante-factor benadering mogelijk.
  • Ondergrens: De auteurs construeren een specifiek geval waarbij de ratio kwadratisch groeit met het aantal niveaus: $\Omega(m^2)$. Specifiek, als $m \approx \log_2 n$, is de ratio $\Omega((\log_2 n)^2)$.
  • Bovengrens: Zij bewijzen dat voor elk geval de ratio begrensd is door $\min((1 + \log_2 n)^2, m^2)$.
• Inzicht: Hoewel de kloof theoretisch kan groeien met het aantal privacy-niveaus, is de groei beperkt (kwadratisch in $m$ of logaritmisch in $n$). De "worst-case" scenario's vereisen specifieke, enigszins kunstmatige verdelingen van privacy-niveaus en data-aantallen.

Betekenis en Claims

Het artikel betoogt dat de dominante factor in het bereiken van hoge bruikbaarheid in heterogene DP het kiezen van het juiste effectieve privacy-budget is, in plaats van volledige personalisatie te implementeren.

• Bescheiden Winsten: In de meest voorkomende en praktische scenario's (combinatie van publieke/private data of omgaan met twee niveaus van privacy) zijn de winsten van volledig gepersonaliseerde affiene schatters beperkt tot constante factoren (maximaal 4x).
• Praktijktoepasbaarheid van Drempels: De drempel-schatting biedt aanzienlijke praktische voordelen: het is eenvoudiger te auditeren, staat toe privacy-garanties duidelijker te communiceren, en past zich eenvoudiger aan aan veranderingen in de gebruikersbasis. Het biedt ook "gratis" privacy aan agenten die genereuzer zijn met hun data.
• Theoretische Grenzen: Hoewel het artikel vaststelt dat de kloof kan groeien met het aantal privacy-niveaus ($m$), merken de auteurs op dat optimale gepersonaliseerde schatters zelfs niet bekend zijn voor $m > 2$ in het algemene geval. Derhalve blijft de drempelaanpak een robuuste, bijna-optimale heuristiek voor schatting van het gemiddelde.

De auteurs concluderen dat voor schatting van het gemiddelde de complexiteit van volledige personalisatie vaak niet gerechtvaardigd is door de marginale winsten in bruikbaarheid, wat suggereert dat eenvoudigere drempelstrategieën voldoende zijn voor de meeste regimes van belang. Zij veronderstellen dat vergelijkbare bevindingen kunnen gelden voor bredere leertaken, hoewel dit een open gebied blijft voor toekomstig onderzoek.