Better Privacy Guarantees for Larger Groups

Technisches Resümee: Bessere Privatsphäre-Garantien für größere Gruppen

Problemstellung
Dieses Paper adressiert ein von Pujol und Desfontaines [2023] aufgeworfenes offenes Problem bezüglich des Designs privater Histogramme für feste, disjunkte Gruppen. Standardmäßige Mechanismen der differenziellen Privatsphäre (Differential Privacy) fügen typischerweise ein Rauschen mit fester Größenordnung zu jedem Zähler hinzu, was eine einheitliche absolute Privatsphäre bietet, aber im Vergleich zu kleinen Gruppen zu deutlich geringeren relativen Fehlern bei großen Gruppen führt. Die Kernfrage lautet, ob man diesen Überschuss an Genauigkeit anders „ausgeben“ kann: indem man den Fehler einer Gruppe proportional zu ihrem Zähler ($x_i$) skalieren lässt, um stärkere Privatsphäre-Garantien (ein kleineres Privatsphäre-Budget) für Mitglieder größerer Gruppen zu gewährleisten.

Das Paper untersucht dies unter dem Add-or-Remove-One-Adjazenzmodell (Hinzufügen oder Entfernen eines Elements). Das Ziel ist es, einen Mechanismus zu finden, bei dem das Privatsphäre-Budget $v(n)$ nur vom Gruppenanteil $n$ abhängt, nicht-inkrementell ist und eine gruppenweise count-abhängige zero-concentrated differential privacy (zCDP) erfüllt. Dies erfordert die Begrenzung der Rényi-Divergenz in beide Richtungen für jede Ordnung $\alpha > 1$ zwischen benachbarten Datensätzen.

Eine kritische technische Hürde ist die Randbedingung bei Null. Die ursprüngliche Formulierung erforderte, dass der erwartete absolute Fehler strikt kleiner als $r x_i$ ist. Bei $x_i = 0$ impliziert dies $E|\hat{x}_i| < 0$, was unmöglich ist. Selbst die Lockerung der Ungleichung auf $\leq$ unter Beibehaltung einer endlichen zwei-seitigen Rényi-Divergenz über die $0 \leftrightarrow 1$ Kante führt zu einem Widerspruch (was die Ausgabe bei Zähler 1 deterministisch erzwingt und somit die Fehlerschranke verletzt).

Methodik und reparierte Formulierung
Um das Problem an der Randbedingung zu lösen, schlagen die Autoren eine „reparierte“ Nutzenanforderung vor:
$$E|\hat{x}_i - x_i| < r \max\{x_i, 1\}$$
Dies bewahrt das relative Fehlertarget für alle positiven Zähler, führt jedoch eine feste absolute Toleranz bei Null ein, was das Problem machbar macht.

Das Paper verwendet zwei primäre methodische Ansätze:

1. Machbarkeit (Obere Schranke): Die Autoren spezialisieren ein bestehendes „Shifted-Transformation“-Framework (Finley et al. [2026]). Sie transformieren den Zählraum mittels eines Logarithmus mit einem Shift $c$ (d. h. $\log(x_i + c)$), fügen Gauß-Rauschen mit fester Varianz hinzu und wenden vor der Exponentiation und dem Clipping einen deterministischen Drift an.

   • Kernelement: Im Gegensatz zu Standard-Log-Normal-Mechanismen, die einen Drift von $-\sigma^2/2$ verwenden, um Mittelwert-Unverzerrtheit zu gewährleisten, verwendet dieser Mechanismus einen Drift von $-\sigma^2$. Dieser spezifische Drift wurde gewählt, um den erwarteten absoluten multiplikativen Fehler zu minimieren, was mit der Nutzenmetrik des Papers übereinstimmt.
   • Privatsphäre-Mechanismus: Durch die Arbeit im Log-Raum mit gleicher Varianz stellt der Mechanismus sicher, dass die Rényi-Divergenz zwischen benachbarten Zählern für alle Ordnungen $\alpha$ endlich ist, wodurch die „Tail-Obstruction“ vermieden wird, bei der ungleiche Varianzen eine unendliche Divergenz in eine Richtung verursachen würden.

2. Unmöglichkeit (Untere Schranke): Die Autoren beweisen, dass kein Mechanismus, der die reparierte Nutzenanforderung und die count-abhängigen zCDP-Anforderungen erfüllt, eine Abfallrate des Privatsphäre-Budgets schneller als die Invers-Quadrat-Rate des Zählers erreichen kann.

   • Zwei-Zähler-Argument: Ein Test zwischen zwei spezifischen Zählern etabliert den $n^{-2}$-Exponenten.
   • Viele-Zähler-Argument: Durch die Verwendung einer „Hidden Offset“-Zufallsvariable und informationstheoretischer Argumente (in Bezug auf den erwarteten absoluten Fehler und die Mutual Information) leiten die Autoren eine engere untere Schranke für den führenden Koeffizienten des Privatsphäre-Budgets ab.

Schlüsselergebnisse

• Optimaler asymptotischer Rate: Für jedes feste $0 < r < 1$ sinkt das optimale Privatsphäre-Budget $v(n)$ als $\Theta_r(n^{-2})$.

  • Obere Schranke: Der Shifted-Log-Gaussian-Mechanismus erreicht $v(n) = O_r(n^{-2})$. Speziell gilt für $n \to \infty$: $v(n) \approx \frac{1}{2\sigma^2 n^2}$.
  • Untere Schranke: Jeder Mechanismus, der die Anforderungen erfüllt, muss $\liminf_{n \to \infty} n^2 v(n) \geq \frac{(1-r)^6}{128r^2(1+r)^2}$ erfüllen. Dies bestätigt, dass die Invers-Quadrat-Rate intrinsisch ist und kein Artefakt der Konstruktion.

• Führende Koeffizienten: Das Paper verengt die Lücke zwischen der besten möglichen oberen und unteren Schranke für den führenden Koeffizienten $C^*$ im Grenzfall kleiner $r$ und großer $n$:
  $$\frac{\pi}{4e^2} \leq C^* \leq \frac{1}{\pi}$$
  Das Verhältnis zwischen diesen Schranken liegt bei etwa 2,995, was zeigt, dass die Schranken innerhalb eines Faktors von drei liegen.

• Versagen der Ungleich-Varianz-Gauß-Verteilung: Das Paper zeigt, dass ein naiver Mechanismus, der $N(n, r^2 n^2)$ (Gauß-Rauschen mit einer Varianz proportional zum Quadrat des Zählers) freigibt, die zCDP-Definition verletzt. Er weist zwar die korrekte Fehlerskala auf, aber die ungleichen Varianzen zwischen benachbarten Zählern führen dazu, dass die Rényi-Divergenz in eine Richtung für ausreichend hohe Ordnungen $\alpha$ unendlich wird, was die „All-Orders“-Anforderung verletzt.

• Trivialer Fall: Bei $r=1$ erfüllt eine datenunabhängige Freigabe (z. B. immer den Wert $0,5$ ausgeben) das reparierte Kriterium mit einem Privatsphäre-Verlust von Null ($v \equiv 0$).

Bedeutung und Ansprüche
Das Paper beansprucht, den ersten mechanismusunabhängigen Beweis geliefert zu haben, dass die Invers-Quadrat-Rate für diese spezifische Formulierung der gruppenweisen Privatsphäre optimal ist.

• Machbarkeit: Es etabliert, dass die „reparierte“ Formulierung lösbar ist, und liefert einen konkreten, komponierbaren Mechanismus (Shifted-Log-Gaussian), der die optimale Rate erreicht.
• Optimalität: Es beweist, dass kein Mechanismus, unabhängig von Komplexität oder Korrelationsstruktur, eine schnellere Abfallrate als $n^{-2}$ erreichen kann.
• Präzision: Durch die Verwendung von Many-Count-Information-Argumenten verengt das Paper die Schranken für den führenden Koeffizienten im Vergleich zu vorherigen Zwei-Zähler-Analysen signifikant und reduziert die Unsicherheit auf einen Faktor von weniger als drei.

Die Autoren stellen explizit fest, dass die Bestimmung des exakten Wertes des optimalen Koeffizienten $C^*$ eine offene Frage bleibt. Sie merken zudem an, dass ihre Ergebnisse für feste, disjote Gruppen gelten; überlappende oder datenabhängige Gruppen würden eine separate Sensitivitätsanalyse erfordern. Der Mechanismus ist verzerrt (aufgrund des $-\sigma^2$ Drifts), ist aber spezifisch darauf kalibriert, den erwarteten absoluten Fehler zu minimenieren, nicht um unverzerrt zu sein.