Better Privacy Guarantees for Larger Groups

Technische Samenvatting: Betere privacygaranties voor grotere groepen

Probleemstelling
Dit artikel behandelt een openstaand probleem geponeerd door Pujol en Desfontaines [2023] met betrekking tot het ontwerp van private histogrammen voor vaste, disjuncte groepen. Standaard differential privacy-mechanismen voegen doorgaans ruis toe met een vaste grootte aan elke telling, wat resulteert in een uniforme absolute privacy maar ook in aanzienlijk kleinere relatieve fouten voor grote groepen vergeleken met kleine groepen. De kernvraag is of men deze overschot aan nauwkeurigheid anders kan "verkwisten": door de fout in een groep proportioneel te laten schalen met de telling ($x_i$) om sterkere privacygaranties te bieden (een kleiner privacybudget) voor leden van grotere groepen.

Het onderzoek vindt plaats onder het add-or-remove-one (optellen of aftrekken van één) adjacency-model. Het doel is om een mechanisme te vinden waarbij het privacybudget $v(n)$ alleen afhankelijk is van de groepsgrootte $n$, niet-toenemend is en voldoet aan count-dependent group-wise zero-concentrated differential privacy (zCDP). Dit vereist het begrenzen van de Rényi-divergentie in beide richtingen voor elke orde $\alpha > 1$ tussen naburige datasets.

Een kritische technische hindernis die wordt geïdentificeerd, is de randvoorwaarde bij nul. De oorspronkelijke formulering vereiste dat de verwachte absolute fout strikt minder dan $r x_i$ was. Bij $x_i = 0$ impliceert dit $E|\hat{x}_i| < 0$, wat onmogelijk is. Bovendien leidt het versoepelen van de ongelijkheid naar $\leq$, terwijl een eindige tweezijdige Rényi-divergentie over de $0 \leftrightarrow 1$ rand behouden blijft, tot een contradictie (wat de output bij telling 1 deterministisch zou maken, waarmee de foutgrens wordt geschonden).

Methodologie en Gerepareerde Formulering
Om het randprobleem op te lossen, stellen de auteurs een "gerepareerde" nutseis voor:
$$E|\hat{x}_i - x_i| < r \max\{x_i, 1\}$$
Dit behoudt de relatieve foutdoelstelling voor alle positieve tellingen, terwijl het een vaste absolute tolerantie bij nul introduceert, wat het probleem uitvoerbaar maakt.

Het artikel gebruikt twee primaire methodologische benaderingen:

1. Haalbaarheid (Bovengrens): De auteurs specialiseren een bestaand "shifted-transformation" raamwerk (Finley et al. [2026]). Ze transformeren de tellingruimte via een logaritme met een verschuiving $c$ (d.w.z. $\log(x_i + c)$), voegen Gaussian ruis met een vaste variantie toe, en passen een deterministische drift toe voordat ze exponentiëren en afkappen (clipping).

   • Belangrijke Innovatie: In tegenstelling tot standaard log-normale mechanismen die een drift van $-\sigma^2/2$ gebruiken om gemiddeld onbevooroordeeldheid te garanderen, gebruikt dit mechanisme een drift van $-\sigma^2$. Deze specifieke drift is gekozen om de verwachte absolute multiplicatieve fout te minimaliseren, wat aansluit bij de nutmetriek van het artikel.
   • Privacy-mechanisme: Door in de log-ruimte te werken met gelijke variantie, zorgt het mechanisme ervoor dat de Rényi-divergentie tussen aangrenzende tellingen eindig is voor alle orden $\alpha$, waardoor de "tail obstruction" wordt vermeden waarbij ongelijke varianties een oneindige divergentie in één richting veroorzaken.

2. Onmogelijkheid (Ondergrens): De auteurs bewijzen dat geen enkel mechanisme dat voldoet aan de gerepareerde nutseis en de count-dependent zCDP-vereisten, een privacybudget-degradatiesnelheid kan bereiken die sneller is dan de inverse-kwadraat van de telling.

   • Two-Count Argument: Een test tussen twee specifieke tellingen vestigt de $n^{-2}$ exponent.
   • Many-Count Argument: Door gebruik te maken van een "hidden offset" willekeurige variabele en informatie-theoretische argumenten (gerelateerd aan de verwachte absolute fout versus wederzijdse informatie), leiden de auteurs een strakkere ondergrens af voor de leidende coëfficiënt van het privacybudget.

Kernresultaten

• Optimale Asymptotische Snelheid: Voor elke vaste $0 < r < 1$ vervalt het optimale privacybudget $v(n)$ als $\Theta_r(n^{-2})$.

  • Bovengrens: Het shifted-log Gaussian mechanisme bereikt $v(n) = O_r(n^{-2})$. Specifiek, wanneer $n \to \infty$, geldt $v(n) \approx \frac{1}{2\sigma^2 n^2}$.
  • Ondergrens: Elk mechanisme dat aan de vereisten voldoet, moet hebben $\liminf_{n \to \infty} n^2 v(n) \geq \frac{(1-r)^6}{128r^2(1+r)^2}$. Dit bevestigt dat de inverse-kwadraat snelheid inherent is en niet een artefact is van de constructie.

• Leidende Coëfficiënten: Het artikel verkleint de kloof tussen de beste mogelijke boven- en ondergrenzen voor de leidende coëfficiënt $C^*$ in de limiet van kleine $r$ en grote $n$:
  $$\frac{\pi}{4e^2} \leq C^* \leq \frac{1}{\pi}$$
  De ratio tussen deze grenzen is ongeveer 2,995, wat aangeeft dat de grenzen binnen een factor drie liggen.

• Falen van Ongelijke-Variantie Gaussian: Het artikel demonstreert dat een naïef mechanisme dat $N(n, r^2 n^2)$ vrijgeeft (Gaussian ruis met een variantie proportioneel aan het kwadraat van de telling) faalt aan de zCDP-definitie. Hoewel het de juiste foutschaal heeft, veroorzaken de ongelijke varianties tussen aangrenzende tellingen dat de Rényi-divergentie in één richting oneindig wordt voor voldoende hoge orden $\alpha$, wat de "alle-orden" vereiste schendt.

• Triviaal Geval: Bij $r=1$ voldoet een data-onafhankelijke release (bijv. altijd 0,5 outputen) aan de gerepareerde criteria met nul privacyverlies ($v \equiv 0$).

Betekenis en Claims
Het artikel claimt het eerste mechanisme-onafhankelijke bewijs te leveren dat de inverse-kwadraat snelheid optimaal is voor deze specifieke formulering van groep-gewijze privacy.

• Haalbaarheid: Het stelt vast dat de "gerepareerde" formulering oplosbaar is en biedt een concreet, composabel mechanisme (shifted-log Gaussian) dat de optimale snelheid bereikt.
• Optimaliteit: Het bewijst dat geen enkel mechanisme, ongeacht complexiteit of correlatiestructuur, de $n^{-2}$ degradatiesnelheid kan verbeteren.
• Precisie: Door gebruik te maken van many-count informatie-argumenten, verfijnt het artikel de grenzen op de leidende constante aanzienlijk vergeleken met eerdere two-count analyses, waardoor de onzekerheid wordt teruggebracht tot een factor minder dan drie.

De auteurs stellen expliciet dat het bepalen van de exacte waarde van de optimale coëfficiënt $C^*$ een open vraag blijft. Ze merken ook op dat hun resultaten van toepassing zijn op vaste, disjuncte groepen; overlappende of data-afhankelijke groepen zouden een aparte sensitiviteitsanalyse vereisen. Het mechanisme is vertekend (door de $-\sigma^2$ drift) maar is specifiek gekalibreerd om de verwachte absolute fout te minimaliseren, niet om onbevooroordeeld te zijn.