Technische Zusammenfassung: Das Spektrum der Unterscheidbarkeit normaler Verteilungen und seine Anwendung auf datenschutzfreundliches maschinelles Lernen

1. Problemstellung

Differential Privacy (DP) ist die Standarddefinition zum Schutz sensibler Daten und verlangt, dass die Ausgabe eines randomisierten Algorithmus ununterscheidbar bleibt, wenn ein einzelner Datensatz zur Eingabedatenbank hinzugefügt oder daraus entfernt wird. Während der „Gaußsche Mechanismus" (Hinzufügen von Gaußschem Rauschen zu einer deterministischen Abfrage) ein grundlegendes DP-Werkzeug ist, produzieren viele moderne Algorithmen des maschinellen Lernens und statistische Verfahren natürlicherweise multivariate Gaußsche Ausgaben, bei denen sowohl der Mittelwert als auch die Kovarianzmatrix von der Eingabedatenbank abhängen.

Bestehende Privatsphärenanalysen für solche Algorithmen stützen sich häufig auf lose obere Schranken, indirekte Divergenzen oder Worst-Sensitivitätsargumente. Diese Ansätze erfassen den genauen Privatsphärenverlust nicht, wenn benachbarte Datensätze Gaußsche Ausgaben mit unterschiedlichen Kovarianzmatrizen hervorrufen. Diese Lücke führt zu zwei Kernforschungsfragen:

1. Gibt es eine allgemeine, exakte Methode, um die Unterscheidbarkeit (IS) zwischen zwei beliebigen multivariaten Gaußschen Verteilungen zu beschreiben?
2. Kann eine enge Charakterisierung dieser IS genutzt werden, um neue, effizientere DP-Mechanismen für Algorithmen mit Gaußschen Ausgaben zu entwerfen?

2. Methodik: Das NDIS-Lemma und das Werkzeugkasten

Die Autoren führen das Spektrum der Unterscheidbarkeit normaler Verteilungen (NDIS) ein, ein analytisches Lemma in geschlossener Form, das die Hockey-Stick-Divergenz $\delta_{X,Y}(\epsilon)$ zwischen zwei beliebigen multivariaten Gaußschen Verteilungen $X \sim \mathcal{N}(\mu_1, \Sigma_1)$ und $Y \sim \mathcal{N}(\mu_2, \Sigma_2)$ exakt charakterisiert.

Das NDIS-Lemma

Das Lemma drückt die Unterscheidbarkeit als Erwartungswert einer Hinge-Funktion aus, die auf ein quadratisches Polynom einer standardnormalverteilten Zufallsvariablen $Z \sim \mathcal{N}(0, I_d)$ angewendet wird:
$$\delta_{X,Y}(\epsilon) = \mathbb{E}\left[ \left( 1 - \exp(g_\epsilon(Z)) \right)_+ \right]$$
wobei $g_\epsilon(Z)$ eine quadratische Form ist, die durch die Mittelwerte und Kovarianzen von $X$ und $Y$ bestimmt wird. Konkret beinhaltet $g_\epsilon(Z)$ die Eigenwerte der Matrix $M = \Sigma_1^{1/2}\Sigma_2^{-1}\Sigma_1^{1/2}$ sowie einen linearen Term, der aus der Mittelwertdifferenz abgeleitet ist.

Der NDIS-Werkzeugkasten

Um das NDIS-Lemma praktisch nutzbar zu machen, entwickeln die Autoren einen „Werkzeugkasten" von Ergebnissen:

1. Verbindung zu verallgemeinerten $\chi^2$-Verteilungen: Die Autoren beweisen, dass die Berechnung von $\delta_{X,Y}(\epsilon)$ auf die Auswertung der Verteilungsfunktionen (CDFs) zweier verallgemeinerter $\chi^2$-Zufallsvariablen reduziert werden kann. Dies ermöglicht eine effiziente numerische Berechnung unter Verwendung etablierter Algorithmen (z. B. Imhof-ähnliche oder Davies-ähnliche Methoden).
2. Analytische Vereinfachungen:
   • Mittelwertverschiebung (gleiche Kovarianz): Stellt das bekannte geschlossene Profil der Privatsphäre des Standard-Gaußschen Mechanismus wieder her.
   • Kovarianzverschiebung (gleicher Mittelwert): Liefert analytische obere Schranken für Fälle, in denen sich die Kovarianzen unterscheiden, aber in der Loewner-Ordnung vergleichbar sind (z. B. $\Sigma_2 \succeq \Sigma_1$). Dies umfasst einen „Null-Leckage"-Schwellenwert, bei dem reine $\epsilon$-DP erreicht wird.
   • Allgemeiner Fall: Für beliebige Mittelwert- und Kovarianzverschiebungen zerlegen die Autoren das Problem in einen Mittelwertverschiebungsschritt und einen Kovarianzverschiebungsschritt und kombinieren ihre Schranken über die Dreiecksungleichung für die DP-Divergenz.
3. Asymmetrie-Eigenschaft: Die Autoren zeigen, dass wenn $\Sigma_1 \succeq \Sigma_2$, dann $\delta_{X,Y}(\epsilon) \geq \delta_{Y,X}(\epsilon)$ gilt. Dies identifiziert eine „harte" Richtung für den Privatsphärenverlust und vereinfacht die Worst-Szenario-Analyse.

3. Hauptbeiträge und Ergebnisse

A. Enge Charakterisierung der Zufälligen Projektion (RP)

Die Autoren wenden den NDIS-Werkzeugkasten auf die Gaußsche Zufällige Projektion an, eine Technik zur Dimensionsreduktion (z. B. in PCA und SVMs).

• Problem: Bisherige Analysen von DP-RP beruhten auf der Abschätzung des kleinsten Singulärwerts (LSV) der Eingabematrix, was ein konservativer Proxy für die Privatsphäre ist.
• Ergebnis: Unter Verwendung von NDIS leiten die Autoren eine exakte Privatsphärencharakterisierung basierend auf dem Hebelwert ($p(i)$) des entfernten Datensatzes ab. Sie beweisen, dass der Privatsphärenverlust eine monoton steigende Funktion des Hebelwerts ist.
• Mechanismus ($M_{RP}$): Sie schlagen einen Mechanismus vor, der die Eingabedatenbank regularisiert (via Ridge-Regularisierung), um sicherzustellen, dass der maximale Hebelwert unter einem Schwellenwert $p^*$ bleibt, der aus dem Ziel $(\epsilon, \delta)$ abgeleitet ist.
• Verbesserung: Experimente zeigen, dass eine hebelwertbasierte Kalibrierung im Vergleich zu LSV-basierten Methoden deutlich größere zulässige Hebelwerte (und somit weniger Regularisierung/Rauschen) erlaubt und einen strikt besseren Trade-off zwischen Privatsphäre und Nutzen bietet.

B. Heben allgemeiner Algorithmen mit Gaußschen Ausgaben

Die Autoren schlagen ein allgemeines Framework vor, um jeden Algorithmus mit Gaußschen Ausgaben in einen DP-Mechanismus zu „heben".

• Sensitivitätsdefinition: Sie definieren ein Loewner-vergleichbares NDIS-Sensitivitätsmodell, das die Verschiebung des Mittelwerts und die relative Änderung der Kovarianz (über Eigenwerte) zwischen benachbarten Datensätzen begrenzt.
• Kalibrierung: Gegeben diese Sensitivitätsschranken berechnet das Framework automatisch das minimale isotrope Gaußsche Rauschen ($\sigma I$), das erforderlich ist, um $(\epsilon, \delta)$-DP zu erfüllen.
• Anwendungen: Dieses Framework wird an Bayesscher Logistischer Regression und Gaußscher Prozessregression demonstriert und liefert die ersten engen DP-Garantien für diese spezifischen Verfahren mit Gaußschen Ausgaben.

C. White-Box-Audit-Tool

Die Arbeit stellt ein Tool für das White-Box-Auditing von Mechanismen mit Gaußschen Ausgaben vor.

• Methode: Durch Nutzung der Verbindung zwischen NDIS und den CDFs verallgemeinerter $\chi^2$-Verteilungen kann ein Auditor den genauen $\delta$-Wert für ein bestimmtes Paar benachbarter Eingaben berechnen (oder eng abschätzen), wobei nur der Mittelwert und die Kovarianz der Ausgaben bekannt sein müssen.
• Bedeutung: Im Gegensatz zu Black-Box-Auditoren, die probabilistische Schätzungen liefern, bietet dieses Tool (unter der Annahme eines CDF-Orakels) eine deterministische untere Schranke für den tatsächlichen Privatsphärenverlust und ermöglicht so die Erkennung von Privatsphärenverletzungen mit hoher Sicherheit.

4. Bedeutung und Behauptungen

Die Arbeit behauptet, dass NDIS ein einheitliches und exaktes Framework für die Analyse der Privatsphäre von Algorithmen mit Gaußschen Ausgaben bietet und über die Einschränkungen des Standard-Gaußschen Mechanismus hinausgeht.

• Theoretische Auswirkung: Es löst das offene Problem der Charakterisierung der optimalen $(\epsilon, \delta)$-Parameter für beliebige Paare von Gaußschen Verteilungen, insbesondere solche mit unterschiedlichen Kovarianzen.
• Praktische Auswirkung:
  • Es ermöglicht rauschsparende Mechanismen (z. B. bei der Zufälligen Projektion), indem konservative Worst-Szenario-Schranken durch exakte hebelwertbasierte Kalibrierungen ersetzt werden.
  • Es bietet ein allgemeines Rezept zur Privatisierung komplexer statistischer Algorithmen (wie der Bayesschen Inferenz), ohne für jeden neuen Algorithmus die Privatsphärenbeweise von Grund auf neu herleiten zu müssen.
  • Es stellt ein rigoroses Audit-Tool zur Verifizierung der Privatsphärenbehauptungen von Algorithmen mit Gaußschen Ausgaben bereit.

Die Autoren betonen, dass ihr Ansatz nicht auf asymptotischen Näherungen oder spezifischen algorithmischen Strukturen beruht, sondern auf der fundamentalen Geometrie von Gaußschen Verteilungen, was ihn auf eine breite Klasse von datenschutzfreundlichen Aufgaben des maschinellen Lernens anwendbar macht.