🤖 machine learning

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

Dit artikel presenteert de eerste convergente differentieel private ondergrens voor zeroth-order optimalisatie door een hybride ruismechanisme en een nieuwe koppelingsanalyse in te voeren die de beperkingen van standaard verschoven divergentieramenwerken, veroorzaakt door anisotrope updates, overwint.

Oorspronkelijke auteurs: Eli Chien, Wei-Ning Chen, Pan Li

Gepubliceerd 2026-05-04

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Eli Chien, Wei-Ning Chen, Pan Li

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Geheel: Het Spoor Verbergen terwijl je een Reuzenpuzzel Oplost

Stel je voor dat je een enorme, complexe puzzel hebt (een enorm AI-model) die je moet oplossen. Je wilt deze oplossen met een specifieke methode genaamd Zeroth-Order Optimization (Optimalisatie van de nulde orde).

Het Probleem:
Normaal gesproken kijk je, om een puzzel op te lossen, naar de stukjes en zoek je uit welke kant je ze precies moet duwen (gradiënten). Maar bij "Zeroth-Order" mag je niet direct naar de stukjes kijken. In plaats daarvan moet je een zet raden, kijken hoe het plaatje eruitziet, een andere zet raden, kijken hoe dat eruitziet, en vervolgens die gissingen middelen om de beste richting te bepalen. Het is alsof je probeert de uitgang van een donker doolhof te vinden door tegen muren te lopen en op echo's te luisteren, in plaats van de kaart te zien.

De Privacy-uitdaging:
Je wilt deze puzzel oplossen met data van veel mensen, maar je moet hun privacy beschermen (Differentiële Privacy). Om dit te doen, voeg je meestal "ruis" (statische interferentie) toe aan je gissingen, zodat niemand kan zien of de data van een specifieke persoon is gebruikt.

De Oude Manier (De "Compositie"-valstrik):
Vroeger behandelden methoden elke enkele stap in het puzzeloplossingsproces als een apart evenement. Ze dachten: "Als ik ruis toevoeg aan stap 1, stap 2, stap 3... en zo verder, loopt de totale privacykost op als een rekening." Als je 1.000 stappen zet, wordt de privacykost enorm, en moet je uiteindelijk stoppen omdat je je volledige privacybudget hebt "besteed". Het is alsof je tol betaalt voor elke enkele mijl die je rijdt; uiteindelijk kun je de reis niet meer betalen.

De Doorbraak van het Artikel:
Dit artikel zegt: "Even wachten! We hoeven geen tol te betalen voor elke enkele stap als we de tussenliggende stappen verborgen houden."

Ze introduceren een concept genaamd Privacy Amplification by Iteration (PABI) (Privacyversterking door iteratie). Denk hier zo aan:

De Oude Manier: Je vertelt iedereen elke 10 voet waar je bent. Ze kunnen je exacte pad traceren.
De Nieuwe Manier: Je vertelt iedereen alleen waar je begon en waar je eindigde. Je houdt het pad ertussen geheim. Omdat het pad verborgen is, doet de "ruis" die je aan het begin toevoegde eigenlijk een veel betere job om je identiteit te beschermen tegen het moment dat je het einde bereikt. De privacykost stopt met groeien en stabiliseert zich eigenlijk.

De Specifieke Hindernissen die ze Overwonnen

De auteurs stonden voor twee hoofdproblemen toen ze probeerden dit "verborgen pad"-idee toe te passen op Zeroth-Order-methoden:

1. Het "Anisotrope" Ruisprobleem (De Eénrichtingsstatische Interferentie)
In standaard methoden voeg je ruis toe in alle richtingen (zoals statische interferentie op een tv-scherm overal). Bij Zeroth-Order voeg je ruis alleen toe langs de specifieke richting die je hebt geraden (zoals statische interferentie op slechts één lijn).

Het Probleem: De wiskundige hulpmiddelen die worden gebruikt om privacy te bewijzen voor "alle-richtingen"-ruis, werken niet voor "één-richtings"-ruis. Het is alsof je probeert een vierkante pen in een rond gat te steken. De standaardwiskunde zegt: "Dit werkt niet omdat de ruis niet uniform is."

2. De "Lipschitz"-barrière (De Glijdende Helling)
Om privacy te bewijzen, moeten wiskundigen meestal bewijzen dat het systeem "stabiel" is—wat betekent dat een kleine verandering in de invoer leidt tot een kleine, voorspelbare verandering in de uitvoer.

Het Probleem: Bij Zeroth-Order is het systeem, omdat de richtingen willekeurig zijn, niet perfect stabiel de hele tijd. Het is alleen stabiel meestal. De oude wiskundige hulpmiddelen vereisen dat het altijd stabiel is, dus faalden ze.

De Oplossing: Een Hybride Motor en een "Spook"-proces

De auteurs bouwden een nieuwe motor om deze problemen op te lossen:

1. Het Hybride Ruismechanisme
In plaats van te kiezen tussen "ruis overal" of "ruis in één richting", creëerden ze een mix.

Ze voegen ruis toe langs de specifieke richting die ze raden (om het puzzeloplossen efficiënt te houden).
Ze voegen ook een klein beetje ruis toe in alle andere richtingen (net genoeg om aan de wiskundige eisen te voldoen).
Het Resultaat: Dit geeft hen het beste van twee werelden: goede prestaties bij het oplossen van de puzzel en een wiskundige structuur die privacybewijzen toelaat.

2. Het "Spook"-proces (De Koppeltruc)
Omdat ze de oude wiskundige hulpmiddelen niet konden gebruiken, bedachten ze een nieuwe truc.

Stel je twee mensen voor, Alice en Bob, die proberen de puzzel op te lossen met iets verschillende data.
De auteurs creëerden een "Spook"-versie van het proces die precies in het midden van Alice en Bob zit.
Ze bewezen dat Alice en het Spook heel dicht bij elkaar liggen, en Bob en het Spook ook heel dicht bij elkaar liggen.
Door dit "Spook" als brug te gebruiken, konden ze bewijzen dat Alice en Bob ook dicht genoeg bij elkaar liggen om als privé te worden beschouwd, zelfs zonder de oude wiskundige hulpmiddelen.

De Verrassende Ontdekking: Meer Richtingen = Betere Privacy

Een van de coolste bevindingen in het artikel gaat over $K$ , het aantal richtingen dat je tegelijkertijd raadt.

Oud Geloof: Het gebruik van meer richtingen ( $K > 1$ ) maakt het makkelijker om de puzzel op te lossen (betere bruikbaarheid), maar kost meer privacy.
Nieuwe Bevinding: Onder deze nieuwe "verborgen pad"-analyse, verbetert het gebruik van meer richtingen eigenlijk de privacy terwijl de kwaliteit van het puzzeloplossen hoog blijft.
De Analogie: Stel je voor dat je probeert een naald in een hooiberg te vinden. Als je alleen naar één plek kijkt, heb je veel "dekking" (ruis) nodig om te verbergen wat je doet. Als je naar 10 plekken tegelijk kijkt, verspreidt de "dekking" zich effectiever, waardoor het voor een waarnemer moeilijker wordt om uit te zoeken naar welke specifieke plek je keek.

Samenvatting van wat ze Beweren

Ze hebben het eerste wiskundige bewijs gecreëerd dat Zeroth-Order-optimalisatie een convergente privacykost kan hebben. Dit betekent dat de privacykost stopt met groeien na een bepaald aantal stappen, in plaats van voor altijd te groeien.
Ze hebben bewezen dat door de tussenliggende stappen van de optimalisatie te verbergen, je veel sterkere privacygaranties krijgt dan eerder mogelijk werd geacht.
Ze hebben aangetoond dat het gebruik van meerdere willekeurige richtingen tegelijkertijd (orthonormale richtingen) niet alleen goed is voor snelheid, maar eigenlijk een geheime wapen is voor privacy.
Ze hebben een nieuw "Hybride Ruis"-recept geleverd dat dit mogelijk maakt.

Wat ze NIET Beweren:

Ze beweren niet dat dit direct werkt voor elk type AI-model of dataset; hun wiskunde is gebaseerd op specifieke aannames (zoals dat de verliesfunctie "glad" en "convex" is).
Ze beweren niet dat dit alle privacyproblemen in AI oplost, alleen dat het een betere theoretische grens biedt voor dit specifieke type optimalisatiemethode.
Ze leveren nog geen kant-en-klare softwaretool voor het publiek; dit is een theoretisch raamwerk dat de weg effent voor toekomstige tools.

1. Probleemstelling

Het artikel behandelt de uitdaging om grote schaalmodellen (bijv. LLM's) te trainen onder Differentiële Privacy (DP)-beperkingen, terwijl er strikte geheugenbeperkingen worden gehanteerd.

Context: Standaard DP-methoden van de eerste orde (zoals DP-SGD) vereisen het opslaan van per-staal gradients tijdens backpropagatie, wat leidt tot een enorme geheugenoverhead die slecht schaalt met de modelgrootte.
Oplossingstrend: Zeroth-order optimalisatie (ZO)-methodes zijn naar voren gekomen als een geheugenefficiënt alternatief, omdat ze alleen forward passes (verliesevaluaties) vereisen en geen expliciete gradients berekenen.
Het Gat: Hoewel bestaande ZO-methoden (zoals DPZero) empirisch goed werken, berust hun theoretische privacyanalyse op standaard compositiestellingen. Dit resulteert in privacykosten die lineair groeien met het aantal trainingsstappen ( $T$ ), wat een afweging tussen bruikbaarheid en privacy forceert.
De Kernuitdaging: Het uitbreiden van Privacy Amplification by Iteration (PABI) — een techniek die convergente (constante) privacygrenzen oplevert voor methoden van de eerste orde — naar methoden van de zeroth-orde.
- Waarom het moeilijk is: PABI van de eerste orde vertrouwt op het toevoegen van isotroop (richtingsonafhankelijk) Gaussisch ruis aan gradients, wat het gebruik van "shifted Rényi divergence"-lemma's mogelijk maakt. In tegenstelling hieraan voegen efficiënte ZO-methoden anisotrope (richtingsafhankelijke) scalaire ruis toe langs willekeurige update-richtingen. Deze anisotropie breekt de globale Lipschitz-eigenschap die vereist is door standaard shifted-divergence-frameworks, waardoor bestaande PABI-tools niet toepasbaar zijn.

2. Methodologie

De auteurs stellen een nieuw kader voor dat een Hybride Ruismechanisme en een Koppelingsanalyse combineert om de beperkingen van standaardanalyse te omzeilen.

A. Hybride Ruismechanisme (Noisy-ZOGD)

In plaats van puur directionele ruis (efficiënt maar moeilijk te analyseren) of puur isotrope ruis (makkelijk te analyseren maar nut-verspillend) te kiezen, stellen de auteurs een geünificeerde updateregel voor:
$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 updates: Gebruikt $K$ willekeurige richtingen per stap om de variantie van de gradientenschatting te verminderen.
Hybride Ruis:
1. Directionele Ruis ( $G^{(1)}$ ): Scalaire Gaussische ruis toegevoegd langs de update-richtingen $u_{t,k}$ . Dit behoudt het nut door ruis te concentreren waar gevoeligheid bestaat.
2. Isotrope Ruis ( $G^{(2)}$ ): Kleine isotrope Gaussische ruis toegevoegd over alle dimensies. Dit is cruciaal voor de theoretische analyse om de "shift" in het koppelingsproces te behandelen.
Orthonormale Richtingen: De update-richtingen $\{u_{t,k}\}$ worden gesampled als een orthonormale set uit de Stiefel-mannigfaltigheid (in plaats van i.i.d. willekeurige vectoren), wat de privacygrenzen aanscherpt.

B. Nieuwe Koppelingsanalyse (Omzeilen van Shifted Divergence)

Het standaard PABI-bewijs vertrouwt op het lemma voor Shifted Rényi Divergence, dat een globale Lipschitz-voorwaarde vereist. Aangezien de ZO-updatekaart niet globaal Lipschitz is (alleen puntsgewijs Lipschitz met hoge waarschijnlijkheid), construeren de auteurs een gekoppeld hulpproces $\tilde{W}_t$ :

Constructie: Zij definiëren een hulptrajectorie $\tilde{W}_t$ die "in het midden" zit van twee aangrenzende trainingsprocessen ( $W_t$ op dataset $D$ en $W'_t$ op dataset $D'$ ).
Decompositie: De privacyanalyse wordt opgesplitst in twee delen:
- Total Variation (TV) Grens: Meet de waarschijnlijkheid dat de koppeling faalt (d.w.z. dat $W_t$ en $\tilde{W}_t$ divergeren). Dit wordt begrensd met behulp van de puntsgewijze Lipschitz-eigenschap van de ZO-update (die geldt met hoge waarschijnlijkheid).
- Rényi Divergentie Grens: Meet de divergentie tussen het hulpproces $\tilde{W}_t$ en het aangrenzende proces $W'_t$ . Omdat $\tilde{W}_t$ is geconstrueerd om uit te lijnen met de ruistructuur, kan dit deel worden geanalyseerd met standaard shifted Gaussische mechanismen.
Resultaat: Deze aanpak omzeilt de noodzaak van een globale Lipschitz-constante, waardoor een convergente privacygrens mogelijk is, zelfs met anisotrope ruis.

3. Belangrijkste Bijdragen

Eerste Convergente PABI voor Zeroth-Order: Het artikel levert het eerste theoretische bewijs dat zeroth-order optimalisatie met verborgen staten een convergente privacygrens bereikt (privacykosten verzadigen na een vast aantal stappen) in plaats van lineair te groeien met $T$ .
Hybride Ruismechanisme: Introduceert een schema voor ruisinjectie dat het nut balanceert (via directionele ruis) en analytische hanteerbaarheid (via een kleine isotrope component).
Rol van Update-dimensie ( $K$ ):
- Toont aan dat onder analyse met verborgen staten, het verhogen van het aantal update-richtingen $K$ de privacyverlies vermindert (in tegenstelling tot standaard compositieanalyse waarbij $K$ de kosten verhoogt).
- Demonstreert dat het gebruik van orthonormale update-richtingen de privacygrenzen aanzienlijk verbetert in vergelijking met i.i.d. willekeurige richtingen.
Nieuwe KoppelingsTechniek: Ontwikkelt een specifieke constructie van een hulpproces die de globale Lipschitz-barrière omzeilt, een techniek die potentieel toepasbaar is op andere niet-gladde of niet-Lipschitz optimalisatiesettingen.

4. Belangrijkste Resultaten

Privacygrens: Voor gladde, sterk convexe verliezen voldoet het voorgestelde Noisy-ZOGD-algoritme aan $(\epsilon, \delta)$ $(ϵ, δ)$ -DP met:
$\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)$
- De grens verzadigt bij $T \approx \frac{R n \sqrt{d}}{K \Delta}$ , wat betekent dat verdere iteraties de privacykosten niet verhogen.
- De grens is omgekeerd evenredig met $K$ , wat aantoont dat het gebruik van meer richtingen de privacy verbetert.
Vergelijking:
- vs. Standaard Compositie: Standaard analyse levert $\epsilon \propto \sqrt{T}$ op, wat onbeperkt groeit. De voorgestelde methode convergeert.
- vs. Output Perturbatie: Hoewel output perturbatie (alleen aan het einde ruis toevoegen) onafhankelijk is van $T$ , is deze over het algemeen zwakker voor praktische $T$ . De voorgestelde methode biedt een strakkere grens voor intermediaire $T$ .
Nuttigheid: Het hybride ruismechanisme behoudt dezelfde nutsgaranties als puur directionele ruis (DPZero), omdat de totale ruisvariantie behouden blijft.

5. Betekenis

Schaalbaarheid: Dit werk maakt de theoretische rechtvaardiging mogelijk van het trainen van massale modellen (miljarden parameters) met DP en beperkt geheugen, een kritieke bottleneck in huidige LLM-finetuning.
Algoritmisch Ontwerp: Het weerlegt het geloof dat het gebruik van meerdere zeroth-order richtingen ( $K > 1$ ) puur een afweging van nut is. Het artikel bewijst dat het ook een privacyvoordeel is, wat het gebruik van hogere dimensionale updates in DP-ZO-algoritmen aanmoedigt.
Theoretische Vooruitgang: Door het "anisotrope ruis"-probleem in PABI op te lossen, overbrugt het artikel een significant gat tussen privacytheorie van de eerste en zeroth-orde, en biedt het een nieuwe toolkit (koppeling met hulpprocessen) voor het analyseren van complexe, niet-Lipschitz optimalisatiedynamica onder privacybeperkingen.
Praktische Impact: Biedt concrete richtlijnen voor practitioners: gebruik orthonormale richtingen, stem de hybride ruisparameter $\beta_t$ af, en maak gebruik van een grotere $K$ om betere privacy-nut-afwegingen te bereiken zonder geheugenkosten te verhogen.