🤖 machine learning

Trade-off Functions for DP-SGD with Subsampling based on Random Shuffling: Tight Upper and Lower Bounds

Dieser Artikel leitet enge, transparente geschlossene obere und untere Schranken für die Trade-off-Funktion von Differenziell Privatem Stochastischem Gradientenabstieg (DP-SGD) mit zufälliger Mischungs-Subsampling her und zeigt, dass diese Methode im Vergleich zu Poisson-Subsampling eine überlegene Interpretierbarkeit und günstige Privacy-Utility-Trade-offs bietet, insbesondere in Regimen, in denen der Noise-Multiplikator hinreichend groß ist.

Ursprüngliche Autoren: Marten van Dijk, Murat Bilgehan Ertan

Veröffentlicht 2026-05-08

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Marten van Dijk, Murat Bilgehan Ertan

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

Stellen Sie sich vor, Sie versuchen einem Computer beizubringen, Katzen auf Fotos zu erkennen, ohne dem Computer jemals das Foto einer bestimmten Person „zeigen" zu dürfen. Dies ist das Ziel von Differenzialer Privatsphäre (DP). Um dies zu erreichen, lernt der Computer aus kleinen Gruppen von Fotos (sogenannten „Mini-Batches") und fügt dem Lernprozess ein wenig „Statik" oder „Rauschen" hinzu, ähnlich wie man die Lautstärke eines Radios erhöht, um ein Flüstern zu übertönen.

Die große Frage, die diese Arbeit beantwortet, lautet: Wie viel Rauschen müssen wir hinzufügen, um Privatsphäre zu garantieren, wenn wir die Fotos zufällig mischen?

Das Problem: Das „Mischen" versus der „Münzwurf"

In der realen Welt nehmen wir beim Trainieren von KI-Modellen normalerweise eine riesige Liste von Daten, mischen sie zufällig (wie ein Kartenspiel) und schneiden sie dann in gleich große Stücke, um das Modell zu unterrichten. Dies nennt man Zufälliges Mischen.

Mathematiker, die Privatsphäre analysieren, haben jedoch jahrelang hauptsächlich eine andere Methode untersucht, die Poisson-Subsampling genannt wird. Stellen Sie sich vor, Sie würfen für jedes einzelne Foto eine Münze: „Kopf, nimm es auf; Zahl, überspringe es." Dies ist mathematisch einfacher zu berechnen, entspricht aber nicht dem, wie die meisten realen Systeme tatsächlich funktionieren.

Da die Mathematik zur Analyse der „Münzwurf"-Methode nicht perfekt zur „Misch"-Methode passt, hatten wir keine klare, präzise Anleitung dafür, wie privat die „Misch"-Methode tatsächlich war. Wir haben geraten.

Die Lösung: Ein neues, klares Regelwerk

Die Autoren dieser Arbeit haben eine enge, geschlossene Formel (eine klare, exakte Gleichung) hergeleitet, um die Privatsphäre der „Misch"-Methode zu messen. Sie haben nicht nur geraten; sie haben fortgeschrittene statistische Werkzeuge verwendet (wie den Berry-Esseen-Satz, der wie ein superpräzises Lineal funktioniert, um zu messen, wie nah ein unordentlicher Datenhaufen einer perfekten Glockenkurve ist), um eine strenge obere und untere Schranke für die Privatsphäre zu erstellen.

Stellen Sie es sich so vor:

Alter Weg: „Wenn Sie die Karten mischen, sind Sie wahrscheinlich sicher, aber wir können Ihnen nicht genau sagen, wie sicher, ohne eine Million Simulationen durchzuführen."
Neuer Weg: „Wenn Sie die Karten mischen und diese spezifische Menge an Rauschen hinzufügen, ist dies die exakte mathematische Garantie, dass niemand das System betrügen kann."

Wichtige Erkenntnisse in einfacher Sprache

1. Der „Sweet Spot" für Rauschen
Die Arbeit zeigt, dass es einen bestimmten Bereich von Rauschen gibt, in dem die Mathematik hervorragend funktioniert.

Zu wenig Rauschen: Wenn das Rauschen zu gering ist, ist das System wie ein Flüstern in einem ruhigen Raum; ein Angreifer kann das Geheimnis leicht hören. Die Arbeit bestätigt, dass unterhalb eines bestimmten Schwellenwerts Privatsphäre nicht garantiert werden kann.
Genau richtig: Wenn das Rauschen über einem bestimmten Niveau liegt (speziell, wenn der Rauschmultiplikator $\sigma$ ungefähr größer als $\sqrt{3/\ln M}$ ist), liefern die Autoren eine klare Formel, die zeigt, dass das System extrem privat ist.
Das Ergebnis: Für eine einzelne Trainingsrunde (ein „Epoch") erhalten Sie bei etwa 11,4 Millionen Datenpunkten, die in 1,14 Millionen kleine Gruppen aufgeteilt sind, durch Hinzufügen einer Standardmenge an Rauschen ( $\sigma=1$ ) eine sehr starke Privatsphäre-Garantie. Sie ist so stark, dass ein Angreifer im Wesentlichen nur rät, ähnlich wie beim Münzwurf, um zu entscheiden, ob die Daten einer bestimmten Person verwendet wurden.

2. Die „Mehr-Runden"-Falle
Was passiert, wenn Sie das Modell über viele Runden (Epochen) hinweg trainieren?

Die lineare Gefahr: Wenn Sie einfach den Privatsphäre-Verlust jeder Runde addieren, wird die Privatsphäre-Garantie sehr schnell schlechter. Es ist wie das Gehen durch ein Minenfeld; wenn Sie 100 Schritte machen, sind Sie 100 Mal wahrscheinlicher, auf eine Mine zu treten. Die Arbeit zeigt, dass mit ihrer aktuellen Formel die Privatsphäre-Garantie zusammenbricht, wenn Sie zu viele Runden trainieren, es sei denn, Sie verfügen über einen unmöglich riesigen Datensatz.
Die asymptotische Hoffnung: Die Autoren untersuchten auch, was im „langen Lauf" passiert (wenn der Datensatz unendlich groß wird). Sie stellten fest, dass der Privatsphäre-Verlust viel langsamer wächst als angenommen – wie die Quadratwurzel der Anzahl der Runden, nicht wie die Anzahl der Runden selbst. Dies ist eine enorme Verbesserung und legt nahe, dass Sie im Grenzfall mehr Runden trainieren können, ohne Ihre gesamte Privatsphäre zu verlieren. Allerdings geben sie zu, dass sie noch keine einfache Formel haben, um dies für reale, endliche Datensätze zu berechnen.

3. Warum dies wichtig ist
Diese Arbeit überbrückt die Lücke zwischen Theorie und Praxis.

Federated Learning: Dies ist entscheidend für Technologien wie Federated Learning, bei denen Ihr Telefon ein Modell auf Ihren Daten trainiert, ohne die Daten an einen zentralen Server zu senden. In diesen Szenarien werden Daten häufig gemischt und in Batches verarbeitet.
Kein Raten mehr: Vorher mussten Ingenieure konservative Schätzungen verwenden (unter Annahme des Worst-Case-Szenarios) oder sich auf komplexe Computersimulationen verlassen, die schwer zu interpretieren waren. Jetzt haben sie eine klare, transparente Formel, um ihre Parameter festzulegen.

Das Fazit

Die Autoren haben einen präzisen „Privatsphäre-Rechner" für die häufigste Methode entwickelt, mit der wir KI-Modelle tatsächlich trainieren (zufälliges Mischen). Sie bewiesen, dass wir mit der richtigen Menge an Rauschen und einem ausreichend großen Datensatz sehr starke Privatsphäre-Garantien in einem einzigen Trainingsdurchlauf erreichen können. Obwohl das Training über viele Runden hinweg eine Herausforderung bleibt, bietet diese Arbeit die erste klare, mathematische Landkarte für die Navigation durch Privatsphäre in der realen Welt und bewegt uns weg von vagen Schätzungen hin zu exakten, vertrauenswürdigen Zahlen.

Technische Zusammenfassung: Trade-off-Funktionen für DP-SGD mit Subsampling basierend auf zufälliger Durchmischung

Problemstellung

Differenziell privater stochastischer Gradientenabstieg (DP-SGD) ist der Standardmechanismus zum Training von Deep-Learning-Modellen unter Datenschutzbedingungen. Während das $f$ -Differential-Privacy-( $f$ -DP $)$ -Rahmenwerk die engstmögliche Charakterisierung von Datenschutzgarantien durch Trade-off-Funktionen zwischen falsch-positiven und falsch-negativen Raten liefert, haben sich bestehende Analysen vorwiegend auf Poisson-Subsampling konzentriert (bei dem Datenpunkte unabhängig mit fester Wahrscheinlichkeit in Minibatches einbezogen werden).

In der Praxis verwenden Implementierungen von DP-SGD und stochastischer Optimierung jedoch typischerweise zufällige Durchmischung, bei der der Datensatz pro Epoche einmal permutiert und in Minibatches fester Größe partitioniert wird. Diese Diskrepanz zwischen dem analysierten Algorithmus (Poisson) und dem eingesetzten Algorithmus (Durchmischung) hat dazu geführt, dass die Datenschutzgarantien realer Systeme nur ungenau charakterisiert sind. Frühere Arbeiten zu durchmischtem DP-SGD lieferten lediglich obere Schranken für die Trade-off-Funktion (untere Schranken für den Datenschutzverlust) durch explizite adversarische Ereignisse oder numerische Auswertungen, ohne geschlossene, transparente Ausdrücke zu bieten. Darüber hinaus deuten jüngste Unmöglichkeitsresultate darauf hin, dass für kleine Rauschmultiplikatoren ( $\sigma \le 1/\sqrt{2 \ln M}$ ) die Trade-off-Funktion nachweislich von der idealen Diagonalen des zufälligen Rätens ( $1-a$ ) getrennt ist, während das Verhalten im Bereich hohen Rauschens eine offene Frage blieb, die eine enge, geschlossene Analyse erfordert.

Methodik

Die Autoren leiten eine enge, geschlossene Analyse der Trade-off-Funktion für DP-SGD mit zufälliger Durchmischung im Rahmen von $f$ -DP ab. Die Methodik durchläuft folgende Stufen:

Reduktion auf einen Angreifer: Das Problem wird auf ein skalares Hypothesentestproblem reduziert. Unter dem Worst-Case-Angreifermodell (das den Beitrag eines einzelnen abweichenden Datensatzes isolieren kann) beobachtet der Angreifer $M$ Runden. Unter der Nullhypothese ( $H_0$ ) sind alle Beobachtungen reines Rauschen $N(0, 1)$ . Unter der Alternativhypothese ( $H_1$ ) enthält genau eine Runde (zufällig gleichverteilt durch die Permutation der Durchmischung ausgewählt) eine verschobene Beobachtung $N(1/\sigma, 1)$ , während die übrigen Rauschen bleiben.
Likelihood-Ratio-Test: Nach dem Neyman-Pearson-Lemma thresholdiert der optimale Test das Likelihood-Verhältnis, was sich auf das Thresholding des Stichprobenmittels von lognormalverteilten Variablen $Y_j = \exp(X_j/\sigma - 1/(2\sigma^2))$ reduziert, wobei $X_j \sim N(0, 1)$ .
Nicht-asymptotische Analyse (Berry-Esseen): Für eine einzelne Epoche wenden die Autoren den Berry-Esseen-Satz an, um die Konvergenzrate des Stichprobenmittels dieser lognormalverteilten Variablen gegen eine Normalverteilung abzuschätzen. Dies liefert eine konkrete, nicht-asymptotische untere Schranke für die Trade-off-Funktion $f(a)$ im Regime $\sigma \ge \sqrt{3/\ln M}$ . Die Schranke wird ausgedrückt als $f(a) \ge 1 - a - \delta$ , wobei $\delta$ eine explizite Funktion des Rauschmultiplikators $\sigma$ und der Anzahl der Runden $M$ ist.
Asymptotische Analyse (Edgeworth-Entwicklung): Um die Berry-Esseen-Schranken zu verbessern, die durch einen Fehlerterm der Ordnung $O(1/\sqrt{M})$ begrenzt sind, führen die Autoren eine Beweistechnik ein, die auf einer zweigliedrigen Edgeworth-Entwicklung basiert. Diese Verallgemeinerung des zentralen Grenzwertsatzes ermöglicht eine feinere asymptotische Abschätzung der Verteilung der Summe lognormalverteilter Variablen. Dieser Ansatz etabliert das asymptotische Verhalten der Trade-off-Funktion für $M \to \infty$ , wobei die Anzahl der Epochen $E$ als $E = c_M^2 M$ skaliert, mit $c_M \to 0$ .

Hauptbeiträge

Geschlossene untere Schranke für eine einzelne Epoche: Die Arbeit liefert die erste enge, geschlossene untere Schranke für die Trade-off-Funktion von durchmischtem DP-SGD im Regime hohen Rauschens ( $\sigma \ge \sqrt{3/\ln M}$ ). Die Schranke lautet:
$f(a) \ge 1 - a - \delta$
wobei $\delta$ explizit in Abhängigkeit von $\sigma$ und $M$ definiert ist (Satz 4.1). Dieses Ergebnis ist innerhalb des Beweisrahmens von Berry-Esseen bis auf konstante Faktoren scharf.
Konkrete Parameterempfehlungen: Die Autoren leiten spezifische Parametereinstellungen für sinnvollen Datenschutz ab. Für eine einzelne Epoche ( $E=1$ ) mit $\sigma=1$ und $\delta=10^{-2}$ zeigen sie, dass eine Datensatzgröße von $N \approx 1.14 \times 10^7$ , partitioniert in $M \approx 1.14 \times 10^6$ Runden, ausreicht. Dies belegt, dass sinnvoller Datenschutz in Szenarien des Federated Learning mit großen Datensätzen und einer einzelnen Epoche erreichbar ist.
Asymptotische Charakterisierung als Gaußsche Differentialprivacy: Mithilfe von Edgeworth-Entwicklungen stellt die Arbeit fest, dass für festes $\sigma$ bei $M \to \infty$ und $E = c_M^2 M$ mit $c_M \to 0$ die $E$ -fach zusammengesetzte Trade-off-Funktion gleichmäßig gegen die Diagonale des zufälligen Rätens ( $1-a$ ) konvergiert. Dies verbessert die Abhängigkeit von der Anzahl der Epochen von der linearen $O(E)$ -Strafe, die durch naive Komposition nahegelegt wird, zu einer asymptotischen $O(\sqrt{E})$ -Trennung (Korollar 5.3).
Vergleich mit Poisson-Subsampling: Die Autoren vergleichen ihre asymptotischen Ergebnisse mit der entsprechenden asymptotischen Analyse für Poisson-Subsampling. Sie stellen fest, dass im Grenzwert geringen Rauschens ( $\sigma \to 0$ ) die zufällige Durchmischung asymptotisch um den Faktor $\sqrt{2}$ näher an der idealen Diagonalen des zufälligen Rätens liegt als Poisson-Subsampling, während sich die beiden Regime im Grenzwert hohen Rauschens ( $\sigma \to \infty$ ) als äquivalent erweisen.

Ergebnisse

Gültigkeitsbereich des Regimes: Die Analyse gilt für $\sigma \ge \sqrt{3/\ln M}$ . Dieses Regime ergänzt das Unmöglichkeitsresultat von Ertan und van Dijk [12], das zeigt, dass für $\sigma < 1/\sqrt{2 \ln M}$ die Trade-off-Funktion von $1-a$ getrennt ist. Zusammen bilden diese Ergebnisse die Datenschutzlandschaft von durchmischtem DP-SGD ab.
Kompositionsschranken:
- Nicht-asymptotisch: Die Iteration der Einzel-Epoche-Schranke ergibt $f^{\otimes E}(a) \ge (1-\delta)^E - a$ , was eine lineare Abhängigkeit von $E$ für den Datenschutzverlust impliziert.
- Asymptotisch: Die auf Edgeworth-Entwicklungen basierende Analyse deutet auf eine engere Abhängigkeit hin, bei der die Trennung von der Diagonalen als $O(\mu \sqrt{E})$ skaliert und nicht als $O(\mu E)$ , vorausgesetzt $E$ skaliert sublinear mit $M$ .
Praktische Implikationen: Die Arbeit identifiziert das Regime der einzelnen Epoche als den „praktischen Sweet Spot" für durchmischtes DP-SGD. In Szenarien des Federated Learning, in denen Clients an wenigen Epochen teilnehmen, sind sinnvolle Datenschutzgarantien ( $\delta \approx 0.01$ ) mit realistischen Datensatzgrößen erreichbar. Umgekehrt hebt die Arbeit eine „Multi-Epoche-Explosion" hervor, bei der eine Erhöhung von $E$ unter der linearen Kompositionsschranke die erforderliche Datensatzgröße $N$ schnell unpraktisch macht (z. B. erfordert $E=100$ eine Größe von $N \sim 10^{11}$ ).

Bedeutung und Behauptungen

Die Arbeit behauptet, eine enge, geschlossene Analyse zu liefern, die die Diskrepanz zwischen den in der Literatur analysierten Algorithmen (Poisson) und den in der Praxis eingesetzten Algorithmen (zufällige Durchmischung) auflöst. Durch die Herleitung transparenter, interpretierbarer Schranken ermöglichen die Autoren Praktikern, Parameteranforderungen direkt abzulesen, ohne sich auf undurchsichtige numerische Werkzeuge zu verlassen.

Die Bedeutung der Arbeit liegt in:

Überbrückung von Theorie und Praxis: Die Validierung, dass zufällige Durchmischung, der Standard in Machine-Learning-Frameworks, eine rigorose Datenschutzanalyse zulässt, die in Regimen geringen Rauschens oft günstiger ist als Poisson-Subsampling.
Definition der Datenschutzlandschaft: Die Ergänzung bestehender Unmöglichkeitsresultate zur Definition der präzisen Rauschschwellenwerte, die für sinnvollen Datenschutz in durchmischtem DP-SGD erforderlich sind.
Leitung der Parametersauswahl: Die Bereitstellung konkreter Formeln zur Auswahl von $M$ , $N$ und $\sigma$ , um spezifische Datenschutzbudgets zu erreichen, was insbesondere für Anwendungen im Federated Learning relevant ist.

Die Autoren bleiben hinsichtlich zukünftiger Arbeiten bescheiden und weisen darauf hin, dass, obwohl die asymptotischen Ergebnisse eine verbesserte $\sqrt{E}$ -Abhängigkeit für mehrere Epochen nahelegen, der Beweis einer konkreten, geschlossenen Form dieser Abhängigkeit (im Gegensatz zum asymptotischen Grenzwert) ein offenes Problem bleibt. Zudem wird die explizite Darstellung der Folgen $\delta_M$ und $\gamma_M$ in der Edgeworth-Entwicklung, um eine konkrete Mehr-Epoche-Schranke zu erhalten, als Richtung für zukünftige Forschung identifiziert.