📊 statistics

Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation

Dieser Beitrag stellt ein stichprobenfreies Rahmenwerk zur Privatsphärenberechnung vor, das auf der Rényi-Divergenz und der bedingten Komposition basiert, um effiziente, deterministische und engere Privatsphärengarantien für differentielle private Matrixmechanismen unter zufälliger Zuweisung zu bieten und damit die Einschränkungen bestehender stichprobenbasierter Ansätze zu adressieren.

Ursprüngliche Autoren: Jan Schuchardt, Nikita Kalinin

Veröffentlicht 2026-05-18

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Jan Schuchardt, Nikita Kalinin

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Sich in einer Menge zu verstecken

Stellen Sie sich vor, Sie versuchen, einen intelligenten Computer (ein maschinelles Lernmodell) darauf zu trainieren, Katzen auf Fotos zu erkennen. Sie haben ein riesiges Fotoalbum, und Sie möchten, dass der Computer lernt, ohne dass jemand herausfinden kann, ob ein bestimmtes Foto einer Person in diesem Album enthalten war. Dies ist das Ziel von Differential Privacy (DP).

Um dies zu erreichen, lernt der Computer in kleinen Gruppen (Batches). Um den Datenschutz zu gewährleisten, fügt es dem Lernprozess ein wenig „Rauschen" oder „Störgeräusch" hinzu, ähnlich wie man die Lautstärke eines Radios erhöht, um ein Flüstern zu übertönen. Je mehr Rauschen Sie hinzufügen, desto sicherer ist der Datenschutz, aber der Computer wird „dümmer", da das Signal begraben wird.

Die Herausforderung, die dieses Paper löst, lautet: Wie können wir die geringstmögliche Menge an Rauschen hinzufügen und dabei trotzdem das Datenschutzversprechen einhalten?

Das Problem: Die „Zufalls-Lotterie" versus die „Zugewiesenen Sitzplätze"

In der Vergangenheit versuchten Forscher, den Datenschutz zu schützen, indem sie zufällig auswählten, welche Fotos in jedem Schritt betrachtet werden (wie eine Lotterie).

Das Lotterie-Problem: Manchmal wird ein Foto 10 Mal hintereinander ausgewählt; zu anderen Zeiten wird es überhaupt nicht ausgewählt. Dies führt zu einer „ungleichen Abdeckung" und macht die Mathematik zur Berechnung des Datenschutzes sehr unübersichtlich und langsam.
Die neue Methode (Bälle in Behälter): Eine neuere Methode, die als „Zufällige Zuweisung" (oder Bälle in Behälter) bezeichnet wird, ist so, als würde man jedem Foto eine spezifische Sitzplatznummer zuweisen. Wenn Sie 100 Sitzplätze und 10 Runden haben, darf jedes Foto in jeder Runde genau einmal auf einem Sitzplatz Platz nehmen. Es ist fair, vorhersehbar und effizient.

Die alte Lösung: Das „Raten-Spiel"

Bei der Verwendung dieser „Zugewiesenen Sitzplätze"-Methode mit fortschrittlichen Rauschtechniken (die als Matrix-Mechanismen bezeichnet werden und eine raffinierte Art darstellen, das Rauschen so zu korrelieren, dass es sich besser selbst auslöscht), mussten Forscher zuvor eine Methode namens Monte-Carlo-Sampling verwenden.

Die Analogie: Stellen Sie sich vor, Sie möchten die genaue Durchschnittsgröße aller Menschen in einem Stadion herausfinden. Die alte Methode sagte: „Lassen Sie uns einfach raten! Wir wählen 1 Million zufällige Personen aus, messen sie und hoffen, dass unser Durchschnitt nahe genug liegt."

Der Fehler: Dies ist langsam. Wenn Sie extrem sicher sein wollen (hoher Datenschutz), müssen Sie Millionen Male raten. Es ist wie der Versuch, eine Nadel im Heuhaufen zu finden, indem man jeweils nur ein Sandkorn betrachtet. Außerdem ist die erhaltene Antwort nur „wahrscheinlich" richtig, nicht zu 100 % garantiert.

Die neue Lösung: Der „Rechner"

Dieses Paper stellt eine neue Art vor, den Datenschutz zu berechnen, die nicht auf Raten basiert. Stattdessen verwendet es zwei neue „Buchhalter" (mathematische Werkzeuge), die die genauen Datenschutzkosten direkt berechnen.

1. Der „Rényi-Buchhalter" (Die dynamische Karte)

Stellen Sie sich das Rauschen im System als ein komplexes Labyrinth vor. Der alte Weg versuchte, das Labyrinth zufällig zu durchlaufen, um zu sehen, wie lange es dauert.

Die Innovation: Die Autoren erstellten eine dynamische Karte (Dynamische Programmierung). Anstatt das Labyrinth zu durchlaufen, berechnen sie den kürzesten Weg sofort, indem sie das Labyrinth in kleine, handhabbare Abschnitte zerlegen.
Das Ergebnis: Sie können nun die Datenschutzkosten für einfache Fälle (DP-SGD) viel schneller berechnen als zuvor – sie verwandeln eine Aufgabe, die exponentielle Zeit benötigte (wie $2^{100}$ ), in etwas Polynomiales (wie $100^2$ ). Es ist wie der Wechsel vom Durchlaufen jedes Pfades in einem Wald zum Einsatz einer Drohne, die in Sekunden darüber fliegt und ihn kartiert.

2. Der „Bedingte Kompositions-Buchhalter" (Das Sicherheitsnetz)

Manchmal ist die „dynamische Karte" für sehr strenge Datenschutzregeln zu grob (wenn Sie super sicher sein müssen).

Die Innovation: Diese Methode zerlegt den Trainingsprozess in einzelne Schritte. Sie fragt: „Wenn wir in einer ‚guten' Situation sind, ist der Datenschutz sicher? Wenn wir in einer ‚schlechten' Situation sind (was sehr selten ist), wie schlimm ist es dann?"
Das Ergebnis: Es ermöglicht dem System zu sagen: „Wir sind zu 99,999 % sicher, dass wir sicher sind, und für diese winzige 0,001 % Chance, unsicher zu sein, ist genau so viel zusätzliches Rauschen erforderlich." Dies bietet eine deterministische Garantie (100 %ige Sicherheit) anstelle eines „hochwahrscheinlichen" Rates.

Warum dies wichtig ist

Das Paper vergleicht seine neuen „Rechner"-Methoden mit dem alten „Raten-Spiel" (Monte Carlo).

Geschwindigkeit: Die neuen Methoden sind enorm schneller, insbesondere wenn Sie einen sehr hohen Datenschutz benötigen (niedriges $\delta$ ). Die alte Methode wird mit zunehmender Strenge immer langsamer; die neue Methode bleibt schnell.
Genauigkeit: Die neuen Methoden bieten eine harte, mathematische Garantie. Sie müssen nicht hoffen, dass Ihre zufälligen Raten richtig waren.
Flexibilität: Sie funktionieren mit allen Arten von „Matrix-Mechanismen" (verschiedene Arten, Rauschen hinzuzufügen), nicht nur mit den einfachen.

Zusammenfassung

Die Autoren haben einen schnellen, deterministischen Rechner für den Datenschutz entwickelt.

Früher: Man musste eine langsame, teure Simulation durchführen (Millionen Male raten), um eine „wahrscheinlich sichere" Antwort zu erhalten.
Jetzt: Man kann einen intelligenten Algorithmus verwenden, um fast sofort eine „zu 100 % garantiert sichere" Antwort zu erhalten.

Dies ermöglicht es Entwicklern, intelligentere, datenschutzfreundlichere KI-Modelle zu trainieren, ohne sich stundenlang in Berechnungen zu verstricken, nur um zu prüfen, ob ihre Datenschutzeinstellungen korrekt sind.

Technische Zusammenfassung: Stichprobenfreie Privatsphärenberechnung für Matrixmechanismen unter zufälliger Zuweisung

Problemstellung

Die Arbeit adressiert die Herausforderung, enge, deterministische Privatsphärengarantien für differenziell privates Modelltraining zu berechnen, das Matrixfaktorisierungsmechanismen in Kombination mit zufälliger Zuweisung (auch bekannt als „Bälle-in-Behälter"-Schema oder Schema für balancierte Iterationsstichprobenziehung) verwendet.

Während Privatsphärenverstärkung durch Stichprobenziehung ein Standardverfahren zur Rauschreduktion beim Differenziell Privaten Stochastischen Gradientenabstieg (DP-SGD) ist, wird das „Bälle-in-Behälter"-Schema gegenüber der Poisson-Stichprobenziehung für das Training in großem Maßstab aufgrund seiner Recheneffizienz und gleichmäßigen Datenabdeckung bevorzugt. Wenn es jedoch mit Matrixfaktorisierung kombiniert wird (die korreliertes Rauschen über Iterationen hinweg einführt, um die Nutzbarkeit zu verbessern), stoßen bestehende Methoden zur Privatsphärenberechnung auf erhebliche Einschränkungen:

Abhängigkeit von Monte-Carlo-Simulationen: Neuere Ansätze (z. B. Choquette-Choo et al., 2025) verlassen sich auf Monte-Carlo-Sampling, um Verstärkungsparameter zu schätzen. Dieser Ansatz ist rechenintensiv, insbesondere in Regimen mit hoher Privatsphäre, wo die erforderliche Anzahl an Stichproben umgekehrt proportional zu $\delta$ skaliert (z. B. zeigt sich, dass der Nachweis von $(\epsilon, 10^{-8})$ -DP $10^5$ -mal teurer ist als $(\epsilon, 10^{-3})$ -DP).
Probabilistische Garantien: Diese auf Sampling basierenden Methoden liefern oft Garantien, die nur mit hoher Wahrscheinlichkeit gelten, oder erfordern, dass der Mechanismus zufällige Enthaltung einsetzt, anstatt deterministische $(\epsilon, \delta)$ -DP-Schranken zu bieten.
Rechnerische Unlösbarkeit: Die Verteilung des Privatsphärenverlusts für Matrixmechanismen unter zufälliger Zuweisung beinhaltet hochdimensionale Mischungen, was eine exakte Bewertung der Hockey-Stick-Divergenz ohne Sampling unmöglich macht.

Methodik

Die Autoren schlagen zwei verschiedene, stichprobenfreie Berechnungsverfahren vor, die deterministische Schranken explizit berechnen, indem sie die Struktur des Schemas der zufälligen Zuweisung und die durch Matrixfaktorisierung eingeführten Korrelationen nutzen.

1. Rényi-Divergenz-Rechner (Dynamische Programmierung)

Diese Methode berechnet eine obere Schranke für die Rényi-Divergenz, die anschließend unter Verwendung standardisierter Umrechnungstheoreme in $(\epsilon, \delta)$ -DP umgewandelt wird.

Kernidee: Die Verteilung des Privatsphärenverlusts für die Richtung „Entfernen" (wobei ein Datenpunkt aus dem Datensatz entfernt wird) kann als Summe über eine Gram-Matrix $G$ ausgedrückt werden, die aus der Strategiematrix $C$ abgeleitet ist.
Komplexitätsreduktion: Für allgemeine Matrizen wurde bewiesen, dass die Berechnung dieser Summe #P-vollständig ist. Für strukturierte Matrizen (z. B. bandförmige Matrizen, bei denen die Strategiematrix $C$ eine Bandbreite $p$ aufweist) erbt die Gram-Matrix $G$ jedoch eine zyklisch bandförmige Struktur.
Algorithmus: Die Autoren formulieren einen Ansatz der dynamischen Programmierung, um die Summe für $p$ $p$ -bandförmige Matrizen exakt zu berechnen.
- Komplexität: Die Laufzeit wird von exponentiell $O(2^\alpha)$ (in der Ordnung $\alpha$ ) auf polynomiell $O(b p \alpha^{2p})$ reduziert, wobei $b$ die Anzahl der Batches pro Epoche ist.
- Trunkierung: Für Matrizen, die nicht strikt bandförmig sind, aber schnell abklingende Einträge aufweisen (z. B. bandförmige Inversenmatrizen), wird die Gram-Matrix getrunken und ein berechenbarer additiver Korrekturterm hinzugefügt, um die Gültigkeit der Schranke sicherzustellen.
Richtung „Hinzufügen": Eine separate, enge analytische obere Schranke wird für die Richtung „Hinzufügen" unter Verwendung der Ungleichung zwischen arithmetischem und geometrischem Mittel (AM-GM) hergeleitet.

2. Bedingter Zusammensetzungs-Rechner

Diese Methode adressiert das Regime mit „kleinem $\epsilon$ " (hohe Privatsphäre), in dem Rényi-Umrechnungsformeln ungenau sein können. Sie überwindet die durch Rauschkorrelation und feste Teilnahmezahlen verursachte Abhängigkeit der Schritte.

Konzept: Anstatt unabhängige Schritte anzunehmen, verwendet die Methode bedingte Zusammensetzung. Sie identifiziert „gute" Ergebnisse, bei denen die bedingten Verteilungen des Mechanismus im Schritt $n$ durch ein Paar fester, faktorisierender Verteilungen $(P^{(n)}, Q^{(n)})$ dominiert werden.
Schlechte Ereignisse: Die Methode berücksichtigt „schlechte" Ergebnisse (bei denen die Dominanz versagt), indem sie deren Wahrscheinlichkeit $\delta_E$ schätzt. Der gesamte Privatsphärenverlust ist die Zusammensetzung der unabhängigen Schritte plus $\delta_E$ .
Dominanzkriterium: Die Autoren leiten ein Kriterium basierend auf umgekehrten Hazard-Funktionen von Gaußschen Mischgewichten her. Sie zeigen, dass die Dominanz gilt, wenn die posteriori umgekehrte Hazard-Funktion punktweise kleiner ist als die umgekehrte Hazard-Funktion einer Zielverteilung.
Tail-Schranken: Um die Parameter der dominierenden Verteilungen zu bestimmen, leiten die Autoren analytische Tail-Schranken für den Privatsphärenverlust ternärer Gaußscher Mischungen her. Sie nutzen eine variationsfamilie von Verteilungen, um diese Schranken zu straffen, indem sie über Temperaturparameter optimieren, um die Standardabweichung der Tail-Schranke zu minimieren.
Effizienz: Während die initiale Auswertung $O(N^2 b^2)$ beträgt, können nachfolgende Auswertungen für verschiedene Rauschmultiplikatoren $\sigma$ auf $O(N b^2)$ amortisiert werden, was sie für die Mechanismus-Kalibrierung effizient macht.

Hauptbeiträge

Deterministische Berechnung: Die Arbeit stellt die ersten stichprobenfreien Methoden vor, um deterministische $(\epsilon, \delta)$ -DP-Garantien für Matrixmechanismen unter zufälliger Zuweisung zu berechnen und eliminiert damit die Notwendigkeit von Monte-Carlo-Schätzungen.
Verbesserte Komplexität für DP-SGD: Für den Spezialfall von unkorreliertem Rauschen (Standard-DP-SGD) verbessert der vorgeschlagene Rényi-Rechner die rechnerische Komplexität der exakten Berechnung unter zufälliger Zuweisung von exponentiell $O(2^\alpha)$ auf polynomiell $O(b \alpha^2)$ und übertrifft damit frühere exakte Methoden erheblich.
Verallgemeinerung auf korreliertes Rauschen: Das Framework erstreckt sich auf beliebige bandförmige und nicht-bandförmige Matrixmechanismen (einschließlich Banded Square Root, Banded Inverse und Buffered Linear Toeplitz) und behandelt die komplexen inter-schrittweisen Korrelationen, die diesen Mechanismen inhärent sind.
Zwei-Regime-Strikte: Die Kombination des Rényi-Rechners (stark im Regime niedriger Privatsphäre/großes $\epsilon$ ) und des bedingten Zusammensetzungs-Rechners (straffer im Regime hoher Privatsphäre/kleines $\epsilon$ ) bietet eine umfassende Berechnungslösung.

Ergebnisse

Die Autoren bewerten ihre Methoden gegenüber dem state-of-the-art Monte-Carlo-Rechner über verschiedene Matrixmechanismen (DP-SGD, BSR, BISR, BandMF, BandInvMF, BLT) und Einstellungen (einzelne und mehrere Epochen).

Genauigkeit: Im Regime niedriger Privatsphäre ( $\epsilon \ge 2$ ) stimmt der Rényi-Rechner eng mit dem Monte-Carlo-Referenzwert überein. Im Regime hoher Privatsphäre ( $\epsilon \le 1$ ) liefert der bedingte Zusammensetzungs-Rechner straffere Schranken, was im Vergleich zu Monte-Carlo-Schätzungen kleinere kalibrierte Rauschmultiplikatoren $\sigma$ ermöglicht.
Robustheit: Die Leistung bleibt über verschiedene Bandbreiten ( $p$ ) und Batch-Anzahlen ( $b$ ) hinweg konstant.
Nutzbarkeit: Experimente auf CIFAR-10 zeigen, dass die aus diesen stichprobenfreien Garantien abgeleiteten Rauschmultiplikatoren die Nutzbarkeitsvorteile der Verwendung von korreliertem Rauschen gegenüber unkorreliertem Rauschen bewahren.
Laufzeit: Die Methoden überwinden die $O(\delta^{-1})$ -Abhängigkeit des Monte-Carlo-Samplings. Obwohl der bedingte Zusammensetzungs-Rechner für große $N$ höhere initiale Kosten hat, sind seine amortisierten Kosten für die Kalibrierung bei strengen Privatsphäre-Budgets signifikant niedriger als bei Monte-Carlo.

Bedeutung und Behauptungen

Die Arbeit behauptet, die erste stichprobenfreie Privatsphärenberechnung für Mechanismen mit korrelierten Gradienten und Teilnahmen zu liefern. Ihre Bedeutung liegt in:

Ermöglichung deterministischer Garantien: Sie beseitigt die Abhängigkeit von probabilistischen Schranken oder zufälliger Enthaltung, die für Produktionssysteme oft unpraktisch oder theoretisch schwächer sind.
Skalierbarkeit: Durch die Reduzierung der Komplexität der exakten Rényi-Berechnung für zufällige Zuweisung von exponentiell auf polynomiell macht sie eine präzise Privatsphärenberechnung für Trainingsläufe in großem Maßstab möglich, bei denen Monte-Carlo-Sampling rechnerisch prohibitiv wäre.
Praktische Kalibrierung: Die Fähigkeit, effizient enge Schranken über einen weiten Bereich von $\epsilon$ und $\delta$ zu berechnen, erleichtert eine bessere Kalibrierung von Rauschmultiplikatoren und verbessert direkt den Trade-off zwischen Nutzbarkeit und Privatsphäre beim differenziell privaten Deep Learning.

Die Autoren räumen Einschränkungen ein und stellen fest, dass die Komplexität des Rényi-Rechners weiterhin exponentiell in der Bandbreite $p$ ist (obwohl polynomiell in $\alpha$ ), und dass die Methode der bedingten Zusammensetzung auf einer groben Partitionierung von Ergebnissen beruht, die möglicherweise pessimistisch ist. Sie schlagen vor, dass zukünftige Arbeiten feinere Partitionen und effizientere variationsinferenz untersuchen könnten, um die Schranken weiter zu straffen.