🤖 machine learning

Privacy Amplification in Differentially Private Zeroth-Order Optimization with Hidden States

Dieser Beitrag stellt die erste konvergente, differentialprivat geschützte Schranke für die Nullter-Ordnung-Optimierung vor, indem er einen hybriden Rauschmechanismus und eine neuartige Kopplungsanalyse einführt, die die durch anisotrope Updates bedingten Einschränkungen standardmäßiger verschobener Divergenzrahmenwerke überwindet.

Ursprüngliche Autoren: Eli Chien, Wei-Ning Chen, Pan Li

Veröffentlicht 2026-05-04

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Eli Chien, Wei-Ning Chen, Pan Li

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: Die Spur verbergen, während man ein riesiges Puzzle löst

Stellen Sie sich vor, Sie haben ein massives, komplexes Puzzle (ein riesiges KI-Modell), das Sie lösen müssen. Sie möchten es mit einer bestimmten Methode lösen, die Zeroth-Order-Optimierung genannt wird.

Das Problem:
Normalerweise schauen Sie, um ein Puzzle zu lösen, auf die Teile und herausfinden, in welche Richtung Sie sie genau bewegen müssen (Gradienten). Aber bei „Zeroth-Order" dürfen Sie die Teile nicht direkt betrachten. Stattdessen müssen Sie einen Zug erraten, sehen, wie das Bild aussieht, einen anderen Zug erraten, sehen, wie dieser aussieht, und dann diese Vermutungen mitteln, um die beste Richtung zu ermitteln. Es ist wie der Versuch, den Ausgang eines dunklen Labyrinths zu finden, indem man gegen Wände stößt und auf Echos lauscht, anstatt die Karte zu sehen.

Die Privatsphären-Herausforderung:
Sie möchten dieses Puzzle mit Daten vieler Menschen lösen, müssen aber deren Privatsphäre schützen (Differential Privacy). Um dies zu tun, fügen Sie normalerweise „Rauschen" (Störgeräusche) zu Ihren Vermutungen hinzu, damit niemand erkennen kann, ob die Daten einer bestimmten Person verwendet wurden.

Der alte Weg (Die „Komposition"-Falle):
Frühere Methoden behandelten jeden einzelnen Schritt des Puzzle-Löseprozesses als separates Ereignis. Sie dachten: „Wenn ich Rauschen zu Schritt 1, Schritt 2, Schritt 3 ... und so weiter hinzufüge, addieren sich die gesamten Privatsphärenkosten wie eine Rechnung." Wenn Sie 1.000 Schritte unternehmen, werden die Privatsphärenkosten enorm, und Sie müssen schließlich aufhören, weil Sie Ihr gesamtes Privatsphärenbudget „ausgegeben" haben. Es ist wie das Bezahlen einer Maut für jede einzelne Meile, die Sie fahren; schließlich können Sie sich die Reise nicht mehr leisten.

Der Durchbruch des Papers:
Dieses Paper sagt: „Moment mal! Wir müssen nicht für jeden einzelnen Schritt eine Maut bezahlen, wenn wir die Zwischenschritte verborgen halten."

Sie führen ein Konzept ein, das Privatsphären-Verstärkung durch Iteration (PABI) genannt wird. Stellen Sie es sich so vor:

Der alte Weg: Sie teilen allen alle 10 Fuß Ihren Standort mit. Sie können Ihren genauen Weg nachverfolgen.
Der neue Weg: Sie teilen allen nur mit, wo Sie gestartet sind und wo Sie enden. Sie halten den Weg dazwischen geheim. Da der Weg verborgen ist, erfüllt das „Rauschen", das Sie am Anfang hinzugefügt haben, tatsächlich eine viel bessere Arbeit beim Schutz Ihrer Identität, bis Sie am Ende ankommen. Die Privatsphärenkosten hören auf zu wachsen und gleichen sich tatsächlich aus.

Die spezifischen Hürden, die sie überwunden haben

Die Autoren stießen auf zwei Hauptprobleme, als sie versuchten, diese Idee des „verborgenen Pfads" auf Zeroth-Order-Methoden anzuwenden:

1. Das „anisotrope" Rausch-Problem (Das einseitige Störgeräusch)
Bei Standardmethoden fügen Sie Rauschen in alle Richtungen hinzu (wie Störgeräusche auf einem Fernsehbildschirm überall). Bei Zeroth-Order fügen Sie Rauschen nur entlang der spezifischen Richtung hinzu, die Sie erraten haben (wie Störgeräusche nur auf einer Linie).

Das Problem: Die mathematischen Werkzeuge, die verwendet werden, um die Privatsphäre für das „Rauschen in alle Richtungen" zu beweisen, funktionieren nicht für „Rauschen in eine Richtung". Es ist wie der Versuch, einen quadratischen Pflock in ein rundes Loch zu stecken. Die Standardmathematik sagt: „Das funktioniert nicht, weil das Rauschen nicht einheitlich ist."

2. Die „Lipschitz"-Barriere (Der rutschige Abhang)
Um die Privatsphäre zu beweisen, müssen Mathematiker normalerweise beweisen, dass das System „stabil" ist – was bedeutet, dass eine kleine Änderung der Eingabe zu einer kleinen, vorhersehbaren Änderung der Ausgabe führt.

Das Problem: Bei Zeroth-Order ist das System, da die Richtungen zufällig sind, nicht immer perfekt stabil. Es ist nur meistens stabil. Die alten mathematischen Werkzeuge verlangen, dass es immer stabil ist, daher versagten sie.

Die Lösung: Ein Hybridmotor und ein „Geist"-Prozess

Die Autoren bauten einen neuen Motor, um diese Probleme zu lösen:

1. Der Hybrid-Rausch-Mechanismus
Anstatt zwischen „Rauschen überall" oder „Rauschen in eine Richtung" zu wählen, schufen sie eine Mischung.

Sie fügen Rauschen entlang der spezifischen Richtung hinzu, die sie erraten (um die Puzzle-Lösung effizient zu halten).
Sie fügen auch ein winziges bisschen Rauschen in alle anderen Richtungen hinzu (nur genug, um die mathematischen Anforderungen zu erfüllen).
Das Ergebnis: Dies bietet ihnen das Beste aus beiden Welten: gute Puzzle-Lösungsleistung und eine mathematische Struktur, die Privatsphärenbeweise ermöglicht.

2. Der „Geist"-Prozess (Der Kopplungs-Trick)
Da sie die alten mathematischen Werkzeuge nicht verwenden konnten, erfanden sie einen neuen Trick.

Stellen Sie sich zwei Personen vor, Alice und Bob, die versuchen, das Puzzle mit leicht unterschiedlichen Daten zu lösen.
Die Autoren schufen eine „Geist"-Version des Prozesses, die genau in der Mitte zwischen Alice und Bob sitzt.
Sie bewiesen, dass Alice und der Geist sehr nah beieinander sind und Bob und der Geist sehr nah beieinander sind.
Indem sie diesen „Geist" als Brücke verwendeten, konnten sie beweisen, dass Alice und Bob auch nah genug beieinander sind, um als privat zu gelten, selbst ohne die alten mathematischen Werkzeuge.

Die überraschende Entdeckung: Mehr Richtungen = bessere Privatsphäre

Eine der coolsten Entdeckungen im Paper betrifft $K$ , die Anzahl der Richtungen, die Sie gleichzeitig erraten.

Alte Überzeugung: Die Verwendung mehrerer Richtungen ( $K > 1$ ) macht das Puzzle einfacher zu lösen (bessere Nutzbarkeit), kostet aber mehr Privatsphäre.
Neue Entdeckung: Unter dieser neuen Analyse des „verborgenen Pfads" verbessert die Verwendung von mehr Richtungen tatsächlich die Privatsphäre, während die Puzzle-Lösungsqualität hoch bleibt.
Die Analogie: Stellen Sie sich vor, Sie versuchen, eine Nadel im Heuhaufen zu finden. Wenn Sie nur einen Ort ansehen, benötigen Sie viel „Tarnung" (Rauschen), um zu verbergen, was Sie tun. Wenn Sie gleichzeitig 10 Orte ansehen, verteilt sich die „Tarnung" effektiver, was es einem Beobachter erschwert, herauszufinden, welchen spezifischen Ort Sie betrachtet haben.

Zusammenfassung ihrer Behauptungen

Sie schufen den ersten mathematischen Beweis, dass Zeroth-Order-Optimierung eine konvergente Privatsphärenkosten haben kann. Das bedeutet, dass die Privatsphärenkosten nach einer bestimmten Anzahl von Schritten aufhören zu wachsen, anstatt für immer zu wachsen.
Sie bewiesen, dass durch das Verbergen der Zwischenschritte der Optimierung viel stärkere Privatsphäre-Garantien erhalten werden, als bisher für möglich gehalten wurden.
Sie zeigten, dass die gleichzeitige Verwendung mehrerer zufälliger Richtungen (orthonormale Richtungen) nicht nur gut für die Geschwindigkeit ist, sondern tatsächlich eine geheime Waffe für die Privatsphäre darstellt.
Sie lieferten ein neues „Hybrid-Rauschen"-Rezept, das dies ermöglicht.

Was sie NICHT behaupten:

Sie behaupten nicht, dass dies sofort für jeden KI-Modelltyp oder Datensatz funktioniert; ihre Mathematik beruht auf spezifischen Annahmen (wie dass die Verlustfunktion „glatt" und „konvex" ist).
Sie behaupten nicht, dass dies alle Privatsphärenprobleme in der KI löst, sondern nur, dass es eine bessere theoretische Obergrenze für diese spezifische Art von Optimierungsmethode bietet.
Sie stellen noch kein fertiges Software-Tool für die Öffentlichkeit bereit; dies ist ein theoretischer Rahmen, der den Weg für zukünftige Tools ebnet.

1. Problemstellung

Das Papier adressiert die Herausforderung, großskalige Modelle (z. B. LLMs) unter Differential Privacy (DP)-Randbedingungen zu trainieren und gleichzeitig strenge Speicherbeschränkungen zu bewältigen.

Kontext: Standard-First-Order-DP-Methoden (wie DP-SGD) erfordern das Speichern von pro-Sample-Gradienten während der Backpropagation, was zu einem massiven Speicher-Overhead führt, der sich mit der Modellgröße schlecht skaliert.
Lösungstrend: Zeroth-Order-Optimierung (ZO)-Methoden haben sich als speichereffiziente Alternative etabliert, da sie nur Vorwärtsdurchläufe (Verlustbewertungen) benötigen und keine expliziten Gradienten berechnen.
Die Lücke: Während bestehende ZO-Methoden (z. B. DPZero) empirisch gut funktionieren, stützt sich ihre theoretische Privatsphärenanalyse auf standardmäßige Zusammensetzungs-Theoreme. Dies führt zu Privatsphärenkosten, die linear mit der Anzahl der Trainingsschritte ( $T$ ) wachsen und einen Trade-off zwischen Nutzen und Privatsphäre erzwingen.
Die Kernherausforderung: Die Erweiterung von Privacy Amplification by Iteration (PABI) – einer Technik, die für First-Order-Methoden konvergente (konstante) Privatsphärenschranken liefert – auf Zeroth-Order-Methoden.
- Warum es schwierig ist: First-Order-PABI beruht auf dem Hinzufügen von isotropem (richtungsunabhängigem) Gaußschen Rauschen zu Gradienten, was die Verwendung von „verschobenen Rényi-Divergenz"-Lemmata ermöglicht. Im Gegensatz dazu fügen effiziente ZO-Methoden anisotropes (richtungsabhängiges) skalares Rauschen entlang zufälliger Aktualisierungsrichtungen hinzu. Diese Anisotropie bricht die globale Lipschitz-Eigenschaft, die für standardmäßige verschobene-Divergenz-Rahmenwerke erforderlich ist, und macht bestehende PABI-Werkzeuge unanwendbar.

2. Methodik

Die Autoren schlagen ein neuartiges Framework vor, das einen Hybriden Rauschmechanismus und eine Kopplungsanalyse kombiniert, um die Grenzen der Standardanalyse zu umgehen.

A. Hybrider Rauschmechanismus (Noisy-ZOGD)

Anstatt rein richtungsabhängiges Rauschen (effizient, aber schwer zu analysieren) oder rein isotropes Rauschen (leicht zu analysieren, aber nutzwertverschwendend) zu wählen, schlagen die Autoren eine vereinheitlichte Aktualisierungsregel vor:
$w_{t+1} = \Pi_{\mathcal{B}_R} \left[ w_t - \frac{\eta}{K} \sum_{k=1}^K \hat{g}_t(w_t; u_{t,k}) + \frac{\eta}{\sqrt{K}} \sum_{k=1}^K G^{(1)}_{t,k} u_{t,k} + \eta \sqrt{d} G^{(2)}_t \right]$

$K$ -dimensionale Aktualisierungen: Verwendet $K$ zufällige Richtungen pro Schritt, um die Varianz der Gradientenschätzung zu reduzieren.
Hybrides Rauschen:
1. Richtungsabhängiges Rauschen ( $G^{(1)}$ ): Skalares Gaußsches Rauschen, das entlang der Aktualisierungsrichtungen $u_{t,k}$ hinzugefügt wird. Dies erhält den Nutzen, indem das Rauschen dort konzentriert wird, wo die Sensitivität besteht.
2. Isotropes Rauschen ( $G^{(2)}$ ): Kleines isotropes Gaußsches Rauschen, das über alle Dimensionen hinzugefügt wird. Dies ist entscheidend für die theoretische Analyse, um die „Verschiebung" im Kopplungsprozess zu handhaben.
Orthonormale Richtungen: Die Aktualisierungsrichtungen $\{u_{t,k}\}$ werden als orthonormale Menge von der Stiefel-Mannigfaltigkeit abgetastet (anstatt als i.i.d. Zufallsvektoren), was die Privatsphärenschranken strafft.

B. Neuartige Kopplungsanalyse (Umgehung der verschobenen Divergenz)

Der Standard-PABI-Beweis stützt sich auf das Lemma der Verschobenen Rényi-Divergenz, das eine globale Lipschitz-Bedingung erfordert. Da die ZO-Aktualisierungsmapping nicht global Lipschitz ist (nur punktweise Lipschitz mit hoher Wahrscheinlichkeit), konstruieren die Autoren einen gekoppelten Hilfsprozess $\tilde{W}_t$ :

Konstruktion: Sie definieren eine Hilfsbahn $\tilde{W}_t$ , die „in der Mitte" zweier benachbarter Trainingsprozesse liegt ( $W_t$ auf Datensatz $D$ und $W'_t$ auf Datensatz $D'$ ).
Zerlegung: Die Privatsphärenanalyse wird in zwei Teile aufgeteilt:
- Gesamtvariations-(TV-)Schranke: Misst die Wahrscheinlichkeit, dass die Kopplung versagt (d. h. $W_t$ und $\tilde{W}_t$ divergieren). Dies wird unter Verwendung der punktweisen Lipschitz-Eigenschaft der ZO-Aktualisierung begrenzt (die mit hoher Wahrscheinlichkeit gilt).
- Rényi-Divergenz-Schranke: Misst die Divergenz zwischen dem Hilfsprozess $\tilde{W}_t$ und dem benachbarten Prozess $W'_t$ . Da $\tilde{W}_t$ so konstruiert ist, dass er mit der Rauschstruktur übereinstimmt, kann dieser Teil mit standardmäßigen verschobenen Gaußschen Mechanismen analysiert werden.
Ergebnis: Dieser Ansatz vermeidet die Notwendigkeit einer globalen Lipschitz-Konstante und ermöglicht eine konvergente Privatsphärenschranke, selbst bei anisotropem Rauschen.

3. Hauptbeiträge

Erste konvergente PABI für Zeroth-Order: Das Papier liefert den ersten theoretischen Beweis, dass Zeroth-Order-Optimierung mit versteckten Zuständen eine konvergente Privatsphärenschranke erreicht (die Privatsphärenkosten sättigen sich nach einer festen Anzahl von Schritten), anstatt linear mit $T$ zu wachsen.
Hybrider Rauschmechanismus: Einführung eines Rauscheinjektionsschemas, das Nutzen (durch richtungsabhängiges Rauschen) und analytische Handhabbarkeit (durch eine kleine isotrope Komponente) ausbalanciert.
Rolle der Aktualisierungsdimension ( $K$ ):
- Zeigt auf, dass unter der Analyse mit versteckten Zuständen eine Erhöhung der Anzahl der Aktualisierungsrichtungen $K$ den Privatsphärenverlust reduziert (im Gegensatz zur standardmäßigen Zusammensetzungsanalyse, bei der $K$ die Kosten erhöht).
- Demonstriert, dass die Verwendung orthonormaler Aktualisierungsrichtungen die Privatsphärenschranken im Vergleich zu i.i.d. zufälligen Richtungen erheblich verbessert.
Neuartige Kopplungstechnik: Entwicklung einer spezifischen Hilfsprozess-Konstruktion, die die globale Lipschitz-Barriere umgeht, eine Technik, die potenziell auf andere nicht-glätte oder nicht-Lipschitz-Optimierungsszenarien anwendbar ist.

4. Hauptergebnisse

Privatsphärenschranke: Für glatte, stark konvexe Verlustfunktionen erfüllt der vorgeschlagene Noisy-ZOGD-Algorithmus $(\epsilon, \delta)$ $(ϵ, δ)$ -DP mit:
$\epsilon = O\left( \sqrt{\frac{\Delta^2 \log(1/\delta)}{n^2 \sigma^2} \min\left(T, \frac{R n \sqrt{d}}{K \Delta}\right)} \right)$
- Die Schranke sättigt bei $T \approx \frac{R n \sqrt{d}}{K \Delta}$ , was bedeutet, dass weitere Iterationen die Privatsphärenkosten nicht erhöhen.
- Die Schranke ist umgekehrt proportional zu $K$ , was zeigt, dass die Verwendung mehrerer Richtungen die Privatsphäre verbessert.
Vergleich:
- vs. Standard-Zusammensetzung: Die Standardanalyse ergibt $\epsilon \propto \sqrt{T}$ , was unbegrenzt wächst. Die vorgeschlagene Methode konvergiert.
- vs. Output-Perturbation: Während Output-Perturbation (Hinzufügen von Rauschen nur am Ende) unabhängig von $T$ ist, ist sie für praktisches $T$ im Allgemeinen schwächer. Die vorgeschlagene Methode bietet eine engere Schranke für mittleres $T$ .
Nutzen: Der hybride Rauschmechanismus behält dieselben Nutzenzusicherungen wie rein richtungsabhängiges Rauschen (DPZero) bei, da die gesamte Rauschvarianz erhalten bleibt.

5. Bedeutung

Skalierbarkeit: Diese Arbeit ermöglicht die theoretische Rechtfertigung des Trainings massiver Modelle (Milliarden von Parametern) mit DP und begrenztem Speicher, einem kritischen Engpass beim aktuellen Fine-Tuning von LLMs.
Algorithmisches Design: Sie widerlegt die Annahme, dass die Verwendung mehrerer Zeroth-Order-Richtungen ( $K > 1$ ) rein ein Nutzen-Trade-off ist. Das Papier beweist, dass dies auch ein Privatsphärenvorteil ist, und ermutigt zur Verwendung höherdimensionaler Aktualisierungen in DP-ZO-Algorithmen.
Theoretischer Fortschritt: Durch die Lösung des „anisotropes Rauschen"-Problems in PABI schließt das Papier eine signifikante Lücke zwischen der First-Order- und der Zeroth-Order-Privatsphärentheorie und bietet ein neues Werkzeugset (Kopplung mit Hilfsprozessen) zur Analyse komplexer, nicht-Lipschitz-Optimierungsdynamiken unter Privatsphärenbedingungen.
Praktische Auswirkungen: Liefert konkrete Richtlinien für Praktiker: Verwenden Sie orthonormale Richtungen, stimmen Sie den hybriden Rauschparameter $\beta_t$ ab und nutzen Sie ein größeres $K$ , um bessere Privatsphären-Nutzen-Trade-offs zu erzielen, ohne die Speicherkosten zu erhöhen.