DP-MacAdam: Differentially Private Mechanism with Adaptive Clipping and Adaptive Momentum

Technische Samenvatting: DP-MacAdam

Probleemstelling
Differentially Private Stochastic Gradient Descent (DP-SGD) is het standaardkader voor privacy-beschermend machine learning, maar het lijdt onder een aanzienlijke praktische beperking: de afhankelijkheid van een vaste gradiënt-clippingdrempel ($C$). In de praktijk is het selecteren van $C$ moeilijk; een waarde die te klein is, verwerpt signalen door excessieve clipping, terwijl een waarde die te groot is, de sensitiviteit verhoogt, wat grotere ruis-toevoeging vereist om aan het privacybudget te voldoven.

Bestaande benaderingen proberen dit op twee verschillende, complementaire manieren aan te pakken, maar geen van beide benut de beschikbare statistieken volledig:

1. Adaptive Clipping (bijv. AdaClip): Gebruikt empirische schattingen van het gradiëntgemiddelde en de variantie om gradiënten dynamisch te verschuiven en te schalen voordat ze worden geclipped. Dit vermindert de verwachte ruis per iteratie, maar verwerpt deze statistieken na de voorbewerking, waardoor het terugkeert naar een standaard SGD-update die de adaptieve informatie negeert.
2. Adaptive Momentum (bijv. DP-Adam): Maakt gebruik van exponentiële voortschrijdende gemiddelden (EMA) van gradiëntmomenten om coördinaat-gewijze adaptieve leersnelheden te berekenen (vergelijkbaar met Adam). Het vertrouwt echter op vaste isotrope clipping, waardoor de voordelen van ruisreductie door adaptieve clipping worden nagelaten.

Het kernprobleem dat wordt aangepakt, is het gebrek aan een algoritme dat tegelijkertijd dezelfde gradiëntstatistieken kan exploiteren voor zowel adaptieve clipping als adaptieve momentum-updates onder differential privacy-garanties, zonder extra privacykosten te veroorzaken.

Methodologie: DP-MacAdam
De auteurs stellen DP-MacAdam (Differentially Private Mechanism with Adaptive Clipping and Adaptive Momentum) voor, een algoritme dat de coördinaat-gewijze adaptieve clipping van AdaClip verenigt met de adaptieve momentum-updates van Adam.

• Verenigde Statistieken: Het algoritme houdt voortschrijdende schattingen bij van het gradiëntgemiddelde ($m_t$) en de variantie ($s_t$), die volledig zijn afgeleid van geprivatiseerde gradiënten. Door de post-processing eigenschap van DP voldoen deze schattingen aan $(\epsilon, \delta)$-DP zonder extra kosten.
• Adaptive Clipping & Momentum:
  • Gradiënten worden gecentreerd en geschaald met behulp van de huidige schattingen van het gemiddelde ($\hat{m}_{t-1}$) en een schalingsvector ($b_{t-1}$) voordat ze worden geclipped.
  • De geprivatiseerde, getransformeerde gradiënten worden vervolgens gebruikt om zowel de momentumtermen (eerste en tweede momenten) voor de parameter-update als de variantieschatting voor de volgende iteratie te updaten.
• Bias-Corrected Variance Estimation: Een cruciaal technisch bijdrage is de afleiding van een nieuwe bias-correctiefactor, $\kappa_t = 2(\beta_1 - \beta_1^t)/(1 + \beta_1)$.
  • Standaard EMA introduceert initialisatiebias.
  • In de DP-setting wordt de variantieschatting verder vertekend door de inflatie van de ruis die wordt toegevoegd tijdens het clippingproces.
  • De auteurs leiden $\kappa_t$ af om een onbevooroordeelde schatting te verkrijgen van de ware gradiëntvariantie uit de EMA van ruis-gecorrigeerde instantane variantieschattingen, waarbij rekening wordt gehouden met zowel de EMA-initialisatie als de correlatiestructuur die door gewogen middeling wordt geïntroduceerd.
• Ruis-schaling: Het algoritme clipped de getransformeerde gradiënten naar een eenheids-$\ell_2$-norm. Ruis wordt toegevoegd aan het gemiddelde van de batch geclippede gradiënten in plaats van aan individuele gradiënten, waarbij de ruisvariantie wordt geschaald met $1/B^2$. Het algoritme trekt de bekende ruisvariantieterm af van de variantieschatting om de variantie van de niet-verruiste gradiënt te herstellen.

Belangrijkste Bijdragen

1. Algoritmeontwerp: DP-MacAdam is het eerste algoritme dat AdaClip-stijl coördinaat-gewijze adaptieve clipping combineert met Adam-stijl adaptieve momentum onder DP-garanties.
2. Theoretische Afleiding: De auteurs leiden een specifieke bias-correctiefactor ($\kappa_t$) af die een onbevooroordeelde schatting van de gradiëntvariantie mogelijk maakt vanuit de EMA van ruis-gecorrigeerde schattingen, waarbij zowel de DP-ruisinflatie als de EMA-initialisatiebias worden geadresseerd.
3. Empirische Prestaties: Het algoritme bereikt een verbeterde modelutiliteit vergeleken met state-of-the-art baselines (DP-SGD, AdaClip, DP-Adam en DP-AdamBC) over diverse privacybudgetten op MNIST en CIFAR-10. Cruciaal is dat het dit bereikt zonder handmatige afstemming van de clippingdrempel of dimensionaliteitsreductie als voorbewerking te vereisen.

Experimentele Resultaten
De auteurs evalueerden DP-MacAdam op MNIST (fully connected netwerk) en CIFAR-10 (5-laagse CNN) tegenover DP-SGD, AdaClip, DP-Adam en DP-AdamBC.

• MNIST: DP-MacAdam presteerde consistent beter dan alle baselines over ruismultipliers ($\sigma$) van 0,5 tot 1,0, waarbij een nauwkeurigheid van maximaal 93,2% werd bereikt (tegenover 92,8% voor DP-Adam en 90,0% voor DP-SGD bij $\sigma=0,5$).
• CIFAR-10: DP-MacAdam behaalde de hoogste nauwkeurigheid over de meeste privacybudgetten, met een resultaat van 59,96% bij $\sigma=0,5$ (tegenover 58,90% voor DP-Adam).
• Observaties: De auteurs merken op dat hoewel DP-MacAdam-BC (een variant die tweede-moment bias-correctie incorporeert voor Adam) winst liet zien op MNIST, het onderpresteerde op CIFAR-10. Ze hypothetiseren dat de tweede-moment bias-correctie grotere winst oplevert in taken waar Adam de SGD in de niet-private setting verslaat.
• Efficiëntie: In tegen tegenstelling tot AdaClip werkt DP-MacAdam direct op de ruwe inputs zonder het privacybudget te besteden aan dimensionaliteitsreductie (bijv. PCA).

Betekenis en Claims
De auteurs claimen dat DP-MacAdam een belangrijke stap voorwaarts vertegenwoordigt door aan te tonen dat de statistieken die gebruikt worden voor adaptieve clipping effectief kunnen worden hergebruikt om adaptieve momentum-updates aan te drijven, waardoor de modelutiliteit wordt verbeterd zonder de privacy in gevaar te brengen. De auteurs benadrukken dat hun aanpak de noodzaak wegneemt voor handmatige afstemming van de clippingdrempel, een grote praktische hindernis bij het implementeren van DP-SGD.

De auteurs blijven bescheiden over de reikwijdte van hun werk en merken op dat:

• De optimale keuze voor de schalingsvector $b_t$ onder hun EMA-gebaseerde variantieschatting openstaat voor toekomstig onderzoek.
• Een formele convergentieanalyse van DP-MacAdam niet in dit werk wordt geleverd.
• De empirische evaluatie momenteel beperkt is tot beeldclassificatietaken (MNIST, CIFAR-10), waarbij toekomstig werk wordt gesuggereerd voor complexere taken zoals NLP en grotere datasets.