🤖 machine learning

Efficient Public Verification of Private ML via Regularization

Dieses Papier stellt einen neuartigen differenziell privaten stochastischen konvexen Optimierungsalgorithmus vor, der nahezu optimale Privacy-Utility-Trade-offs erreicht und gleichzeitig eine öffentliche Verifizierung seiner Privatsphäre-Garantien ermöglicht, wobei die dafür anfallenden Rechenkosten signifikant niedriger sind als das Training des Modells.

Ursprüngliche Autoren: Zoë Ruha Bell, Anvith Thudi, Olive Franzese-McLaughlin, Nicolas Papernot, Shafi Goldwasser

Veröffentlicht 2026-07-01

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Zoë Ruha Bell, Anvith Thudi, Olive Franzese-McLaughlin, Nicolas Papernot, Shafi Goldwasser

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 sind Teil einer Gemeinschaft, die ihre persönlichen Daten (wie Fotos oder Krankenakten) bündelt, um ein intelligentes Computerprogramm zu trainieren. Sie möchten helfen, haben aber schreckliche Angst, dass das fertige Programm versehentlich Ihre Geheimnisse preisgeben könnte. Um dies zu verhindern, versprechen die Leute, die das Programm entwickeln, einen speziellen „Privatsphäre-Schild“ namens Differential Privacy einzusetzen.

Es gibt jedoch ein großes Problem: Woher wissen Sie als ganz normaler Mensch, dass sie den Schild tatsächlich verwendet haben?

Das Problem: Die „Black Box“-Falle

Derzeit müssen Sie, wenn Sie prüfen wollen, ob das Programm sicher ist, wie ein Detektiv vorgehen. Sie bitten die Entwickler, das Programm mit verschiedenen Daten laufen zu lassen und zu sehen, was dabei herauskommt. Das Paper argumentiert, dass dies so ist, als würde man versuchen, eine Nadel im Heuhaufen zu finden, indem man nur nach dem Heu sucht.

Die Autoren beweisen, dass ein unehrlicher Entwickler Sie leicht austricksen könnte. Er könnte eine „geheime Hintertür“ in das Programm einbauen. Diese Hintertür ist wie eine versteckte Falltür, die sich nur öffnet, wenn man einen geheimen Code (eine digitale Signatur) kennt.

Für Sie (die Öffentlichkeit): Sieht das Programm vollkommen sicher und privat aus.
Für den Entwickler (oder dessen Freunde): Können sie den geheimen Code verwenden, um die Falltür zu öffnen und alle Daten zu stehlen.

Da diese Hintertür hinter komplexer Mathematik verborgen ist, können Sie sie nicht einfach durch das Betrachten des Endprodukts entdecken. Sie benötigen einen besseren Weg, um den Prozess zu verifizieren.

Die Lösung: Das „Quittungs“-System

Die Autoren haben eine neue Art entwickelt, diese Programme zu trainieren, die mit einem öffentlich verifizierbaren Beleg einhergeht. Anstatt den Entwickler nur zu vertrauen, erstellen sie einen schrittweisen Beweis, den jeder überprüfen kann, der aber die privaten Daten nicht preisgibt.

Denken Sie an das Backen eines Kuches in einer verschlossenen Küche:

Der alte Weg: Sie vertrauen dem Bäcker, weil er sagt: „Ich habe mich an das Rezept gehalten.“ Sie haben keine Möglichkeit zu prüfen, ohne ihn stundenlang beim Kochen zu beobachten.
Der neue Weg: Der Bäcker folgt einem spezifischen Rezept, das er dazu verpflichtet, eine Spur von „Krümeln“ (mathematische Beweise) zu hinterlassen, während er arbeitet.
- Er beweist, dass er die Zutaten korrekt gehackt hat.
- Er beweist, dass er die richtige Menge an „Rauschen“ (eine spezielle Zutat, die die Daten verschleiert, um Einzelpersonen zu verbergen) hinzugefügt hat.
- Entscheidend: Sie können diese Krümel viel schneller überprüfen, als es gedauert hat, den Kuchen zu backen.

Wie es funktioniert (Der „Regularisierungs“-Trick)

Das Geheimrezept ist etwas, das man Regularisierung nennt.

Stellen Sie sich vor, Sie versuchen, den tiefsten Punkt in einem nebligen Tal zu finden (das beste Modell).
Normalerweise würden Sie einen langen, gewundenen Pfad nehmen und jeden einzelnen Schritt überprüfen.
Die Methode der Autoren fügt einen „magnetischen Leitfaden“ (Regularisierung) hinzu, der Sie zur Mitte zieht. Dies macht den Pfad glatter und vorhersehbarer.
Da der Pfad so vorhersehbar ist, müssen Sie nicht jeden einzelnen Schritt des Entwicklers überprüfen. Sie müssen nur einige wichtige „Checkpoints“ (Gradienten) prüfen und verifizieren, dass das „Rauschen“ korrekt hinzugefügt wurde.

Das Ergebnis: Schneller prüfen als Backen

Das Paper zeigt, dass mit dieser neuen Methode:

Das Training (das Backen): Eine gewisse Zeit in Anspruch nimmt.
Die Verifizierung (das Prüfen des Belegs): Signifikant weniger Zeit benötigt als das Training.

In ihren Tests haben sie dies an einem Standarddatensatz (MNIST, was wie ein kleines Fotoalbum handgeschriebener Zahlen ist) ausprobiert.

Alte Methode: Es dauerte etwa 100 Stunden, um die Privatsphäre zu verifizieren.
Neue Methode: Es dauerte nur etwa 3 Stunden.

Sie fanden heraus, dass der zeitaufwendigste Teil die Überprüfung der „Schritte“ (Gradienten) war, aber selbst dann mussten sie weit weniger Schritte überprüfen als zuvor. Die Zeit, die für die Kommunikation zwischen dem Prüfer und dem Entwickler aufgewendet wurde, war fast null.

Was das für Sie bedeutet

Dieses Paper behauptet nicht, dass wir nun jedes KI-Modell (wie die komplexen Modelle, die Poesie schreiben oder Autos fahren) verifizieren können. Es konzentriert sich speziell auf eine Art von mathematischem Problem, das Konvexe Optimierung genannt wird (was so etwas wie das Finden des besten geraden Pfades ist).

Es beweist jedoch einen entscheidenden Punkt: Es ist möglich, ein System zu bauen, in dem der Beweis der Privatsphäre günstiger und schneller zu prüfen ist als das Training selbst. Dies verhindert, dass unehrliche Entwickler ihre Privatsphäre-Schilde vortäuschen, und gibt der Öffentlichkeit einen echten, effizienten Weg, um zu sagen: „Ja, ich vertraue diesem Modell.“

Kurz gesagt: Sie haben einen Weg gefunden, den „Privatsphäre-Beleg“ so leicht lesbar zu machen, dass Sie verifizieren können, dass der Bäcker nicht Ihre Kekse gestohlen hat, ohne ihn die ganze Zeit beim Backen des Kuchens beobachten zu müssen.

Technisches Resümee: Effiziente öffentliche Verifizierung von privatem ML durch Regularisierung

Problemstellung

Differential Privacy (DP) ist der Standardrahmen zum Schutz sensibler Informationen in Trainingsdatensätzen für maschinelles Lernen und garantiert, dass Nutzer des Modells keine Rückschlüsse auf spezifische Datenpunkte ziehen können. Es besteht jedoch eine kritische Lücke: Datenanbieter und die Öffentlichkeit mangelt es an effizienten Methoden, um zu verifizieren, dass ein veröffentlichtes Modell tatsächlich unter DP-Garantien trainiert wurde.

Aktuelle Verifizierungsmethoden stehen vor zwei primären Einschränkungen:

Black-Box-Auditing: Ansätze, die einen Modelltrainer mit unterschiedlichen Datensätzen abfragen, sind statistisch unzureichend. Das Paper zeigt, dass unter der Annahme digitaler Signaturen ein böswilliger Trainer eine „rechentechnisch nicht detektierbare“ Backdoor implementieren kann. Diese Backdoor bleibt während Standard-Audits latent, ermöglicht es dem Trainer jedoch, den Datensatz an spezifische Entitäten zu leaken, was den Algorithmus trotz bestandener Black-Box-Prüfung nicht-privat macht.
Interaktive Verifizierungskosten: Bestehende interaktive Beweise für DP (z. B. die Verifizierung von DP-SGD) erfordern, dass der Verifizierer nahezu alle Trainingsschritte nachrechnet. Beispielsweise erforderte die Verifizierung von DP auf dem MNIST-Datensatz bisher etwa 100 Stunden Rechenzeit, was mit den Trainingskosten skaliert. Dies macht die öffentliche Verifizierung für große Datensätze unpraktikabel.

Das Paper adressiert die Herausforderung, einen DP-Algorithmus zu entwerfen, bei dem die Verifizierungskosten strikt niedriger als die Trainingskosten sind, speziell für stochastische konvexe Optimierung (DP-SCO).

Methodik

1. Theoretische Grundlage: Undetektierbare Backdoors

Die Autoren formalisieren zunächst die Unzulänglichkeit des Black-Box-Auditing. Sie konstruieren einen backdoored Trainingsalgorithmus $T'$ , der für jeden polynomzeitlichen Auditor rechentechnisch ununterscheidbar von einem legitimen DP-Algorithmus $T$ ist.

Mechanismus: Der Algorithmus bettet einen Schritt zur Verifizierung digitaler Signaturen in die Trainingsdaten ein. Wenn ein spezifischer Input eine gültige Signatur enthält (die nur der böswillige Trainer besitzt), gibt der Algorithmus den Rohdatensatz anstelle des Modells aus.
Implikation: Dies beweist, dass ohne interaktive Protokolle kein öffentlicher Auditor die Privatsphäre eines Modells garantieren kann, was einen Wechsel zur interaktiven Zertifizierung erforderlich macht.

2. Kernalgorithmus: Modifizierter Phased ERM

Um eine effiziente Verifizierung zu erreichen, schlagen die Autoren eine Modifikation des Phased Empirical Risk Minimization (ERM) Algorithmus (Feldman et al., 2020) vor.

Standard Phased ERM: Löst eine Serie von regularisierten Zielfunktionen auf disjunkten Teilmengen der Daten, wobei die Stärke der Regularisierung über die Phasen hinweg zunimmt. Es stützt sich auf die parallele Komposition von Privacy-Budgets, um enge Garantien zu erreichen. Die Verifizierung der parallelen Komposition ist jedoch aufwendig, da der Verifizierer bestätigen muss, dass jede Phase eine spezifische, disjunkte Teilmenge der Daten verwendet hat.
Die Modifikation: Die Autoren ändern die Abbruchkriterien für die approximierten Minimierer in jeder Phase.
- Anstatt zu fordern, dass der Excess Loss klein ist, fordern sie, dass die Gradientennorm klein ist ( $\|\nabla F_i(\tilde{w}_i)\|_2 \leq \frac{2}{n_i} L$ ).
- Sie passen das Privacy-Budget $\delta$ für jede Phase auf $\delta / \lceil \log_2(n) \rceil$ an.
Resultierender Vorteil: Diese Modifikation ermöglicht es dem Algorithmus, nahezu optimale Privacy-Utility-Trade-offs unter Verwendung der standardmäßigen sequentiellen Komposition statt der parallelen Komposition zu erzielen. Die standardmäßige Komposition ist wesentlich einfacher zu verifizieren, da sie nicht die Disjunktheit der Datens subsets beweisen muss, sondern nur, dass das Rauschen korrekt hinzugefügt wurde und die Gradientennormen erfüllt sind.

3. Verifizierungsprotokoll

Das vorgeschlagene Protokoll (Algorithmus 2) beinhaltet einen interaktiven Beweis zwischen einem Prover (Trainer) und einem Verifier (Öffentlichkeit):

Commitment: Der Prover committet auf den Datensatz und die Modellgewichte in jeder Phase.
Gradientenverifizierung: Unter Verwendung von Zero-Knowledge-Beweisen (ZKP) prüft der Verifizierer, ob die Gradientennorm des approximierten Minimierers unter dem erforderlichen Schwellenwert liegt.
Rauschverifizierung: Der Verifizierer prüft, ob Gaußsches Rauschen zu den Gewichten unter Verwendung eines diskreten Gaußschen Commitment-Schemas hinzugefügt wurde.
Komplexität: Die Verifizierung erfordert die Prüfung von $n$ Gradienten (wobei $n$ die Datensatzgröße ist) und $d \cdot \lceil \log_2(n) \rceil$ Gaußschen Zufallsvariablen-Commitments (wobei $d$ die Dimension ist).

4. Erweiterung auf Machine Unlearning

Die Autoren erweitern diese Techniken auf Approximate Machine Unlearning für stark konvexe Verluste. Durch die Nutzung der Stabilität stark konvexer Funktionen zeigen sie, dass Unlearning durch die Prüfung von Gradienten auf dem Retain-Datensatz ( $D'$ ) statt auf dem vollen Datensatz zertifiziert werden kann, was nur $|D'|$ Gradientenprüfungen und $d$ Rausch-Commitments erfordert.

Kernergebnisse

Theoretische Garantien

Privacy-Utility-Trade-off: Der modifizierte Algorithmus erreicht einen Excess Population Risk von $\tilde{O}(L D (\frac{1}{\sqrt{n}} + \frac{\sqrt{d \ln(1/\delta)}}{\epsilon n}))$ , was nahezu optimal ist (entspricht bekannten unteren Schranken bis auf $\log \log(n)$ Faktoren).
Effizienz der Verifizierung: Die Zertifizierung erfordert die Verifizierung von nur $n$ $n$ Gradienten und $d \cdot \lceil \log(n) \rceil$ $d \cdot ⌈ lo g (n)⌉$ Gaußschen Zufallsvariablen.
- Im Vergleich zu den schnellsten bekannten Trainingsalgorithmen für DP-SCO, die $\tilde{\Omega}(\min(n^{1.5}, n^2/\sqrt{d}))$ Gradienten erfordern, ist die Verifizierungskosten deutlich niedriger (mindestens eine $O(\sqrt{n})$ Verbesserung in nicht-glatten Settings).
- In glatten Settings bietet die Reduktion der Gaußschen Zufallsvariablen-Checks (von $\Omega(dn)$ auf $d \log n$ ) einen erheblichen Laufzeitvorteil.

Empirische Evaluierung

Die Autoren implementierten das Protokoll mit dem EMP-Toolkit für binäre logistische Regression auf dem MNIST-Datensatz ( $n=60.000, d=784$ ).

Laufzeitvergleich:
- Bisheriger Ansatz (DP-SGD Verifizierung): ~100 Stunden.
- Vorgeschlagener Ansatz: ~3 Stunden auf einer Laptop-CPU.
Bottleneck-Analyse:
- Gradientenverifizierung: Dominiert die Laufzeit. Die Anzahl der zu verifizierenden Gradienten wurde im Vergleich zu vorherigen Methoden um mehr als das Vierfache reduziert.
- Rauschverifizierung: Die Zeit zur Verifizierung von Gaußschen Zufallsvariablen sank drastisch (vom dominierenden Kostenfaktor zu einem vernachlässigbaren Teil, der weniger Zeit als eine einzige Gradientenverifizierung beansprucht).
- Kommunikation: Der Netzwerk-Overhead (LAN/WAN) war im Vergleich zur Berechnung unbedeutend.
- Training: Die Trainingszeit war vernachlässigbar (Sekunden), da sie im Gegensatz zum Verifizierungsprozess keine homomorphe Verschlüsselung erfordert.

Bedeutung und Behauptungen

Das Paper behauptet, den ersten bekannten DP-SCO Algorithmus zu präsentieren, dessen DP-Verifizierung besser als die Trainingskosten skaliert.

Paradigmenwechsel: Es bewegt das Feld von „Black-Box-Auditing“ (das gegen rechentechnisch begrenzte Adversaries nachweislich unzureichend ist) hin zu „effizienter öffentlicher Verifizierung“ via interaktiver Beweise.
Praktikabilität: Durch die Reduzierung der Verifizierungszeit von ~100 Stunden auf ~3 Stunden auf Standardhardware für MNIST-Skala-Daten argumentiert das Paper, dass die öffentliche Zertifizierung von privatem ML praktikabel wird.
Limitierungen: Die Autoren merken bescheiden an, dass der aktuelle Ansatz auf konvexe Settings beschränkt ist und nicht direkt auf tiefe neuronale Netze anwendbar ist (obwohl er auf das Fine-Tuning der letzten Schicht anwendbar sein könnte). Sie räumen zudem ein, dass für sehr große Datensätze die lineare Skalierung mit $n$ dennoch unpraktisch sein kann und zukünftige Arbeit nötig ist, um stochastische Gradienten effizienter zu handhaben (z. B. via Randomized Smoothing).

Zusammenfassend lässt sich sagen, dass das Paper etabliert, dass durch die Nutzung von Regularisierung zur Stabilisierung der Optimierung und die Modifikation der Verifizierungskriterien (Fokus auf Gradientennormen statt Excess Loss) DP-Algorithmen konstruiert werden können, die sowohl hinsichtlich des Nutzens nahezu optimal als auch effizient für die Öffentlichkeit verifizierbar sind.