Technische Samenvatting: Steekproefvrije Privacy-Accounting voor Matrixmechanismen onder Random Allocation

Probleemstelling

Het artikel behandelt de uitdaging om strakke, deterministische privacygaranties te berekenen voor differentieel private modeltraining die gebruikmaakt van matrixfactorisatiemechanismen in combinatie met random allocation (ook bekend als het "balls-in-bins"-schema of het schema voor gebalanceerde iteratiesteekproeven).

Hoewel privacyversterking door steekproeven een standaardtechniek is om ruis te verminderen in Differentieel Private Stochastische Gradientafstijging (DP-SGD), wordt het "balls-in-bins"-schema bij schaalbare training verkiest boven Poisson-steekproeven vanwege de rekenkundige efficiëntie en de uniforme data-dekking. Echter, wanneer dit wordt gecombineerd met matrixfactorisatie (wat gecorreleerde ruis introduceert over iteraties heen om de bruikbaarheid te verbeteren), ondervinden bestaande methoden voor privacy-accounting aanzienlijke beperkingen:

1. Afhankelijkheid van Monte Carlo: Nieuwere benaderingen (bijv. Choquette-Choo et al., 2025) vertrouwen op Monte Carlo-steekproeven om versterkingsparameters te schatten. Deze aanpak is rekenkundig duur, vooral in regimes met hoge privacy waar het vereiste aantal steekproeven omgekeerd evenredig is met $\delta$ (bijv. blijkt dat het aantonen van $(\epsilon, 10^{-8})$-DP $10^5$ keer duurder is dan $(\epsilon, 10^{-3})$-DP).
2. Probabilistische Garanties: Deze op steekproeven gebaseerde methoden leveren vaak garanties die slechts met hoge waarschijnlijkheid gelden, of vereisen dat het mechanisme gebruikmaakt van willekeurige abstentie, in plaats van deterministische $(\epsilon, \delta)$-DP-grenzen te bieden.
3. Rekenkundige Onoplosbaarheid: De verdeling van privacyverlies voor matrixmechanismen onder random allocation omvat hoogdimensionale mengsels, waardoor een exacte evaluatie van de hockey-stick-divergentie zonder steekproeven onoplosbaar is.

Methodologie

De auteurs stellen twee verschillende, steekproefvrije accountingprocedures voor die deterministische grenzen expliciet berekenen, gebruikmakend van de structuur van het random allocation-schema en de correlaties die door matrixfactorisatie worden geïntroduceerd.

1. Rényi-divergentie-accountant (Dynamisch Programmeren)

Deze methode berekent een bovengrens voor de Rényi-divergentie, die vervolgens wordt omgezet naar $(\epsilon, \delta)$-DP met behulp van standaard conversiestellingen.

• Kerninzicht: De verdeling van privacyverlies voor de "verwijder"-richting (waarbij een datapunt uit de dataset wordt verwijderd) kan worden uitgedrukt als een som over een Gram-matrix $G$ die is afgeleid van de strategiematrix $C$.
• Complexiteitsreductie: Voor algemene matrices is het bewezen dat het berekenen van deze som #P-compleet is. Echter, voor gestructureerde matrices (bijv. bandmatrices waarbij de strategiematrix $C$ een bandbreedte $p$ heeft), erft de Gram-matrix $G$ een cyclisch gebandeerde structuur.
• Algoritme: De auteurs formuleren een dynamisch programmerings-benadering om de som exact te berekenen voor $p$-bandmatrices.
  • Complexiteit: De runtime wordt gereduceerd van exponentieel $O(2^\alpha)$ (in de orde $\alpha$) naar polynoom $O(b p \alpha^{2p})$, waarbij $b$ het aantal batches per epoch is.
  • Truncatie: Voor matrices die niet strikt gebandeerd zijn maar snel afnemende elementen hebben (bijv. gebandeerde inverse matrices), truncateert de methode de Gram-matrix en voegt een berekenbare additieve correctieterm toe om te waarborgen dat de grens geldig blijft.
• Add-richting: Een aparte, strakke analytische bovengrens wordt afgeleid voor de "add"-richting met behulp van de ongelijkheid van het rekenkundig en meetkundig gemiddelde (AM-GM).

2. Conditionele Compositie-accountant

Deze methode adresseert het regime met "kleine $\epsilon$" (hoge privacy) waar Rényi-conversieformules los kunnen zijn. Het overwint de onderlinge afhankelijkheid van stappen veroorzaakt door ruiscorrelatie en vaste participatieaantallen.

• Concept: In plaats van onafhankelijke stappen aan te nemen, maakt de methode gebruik van conditionele compositie. Het identificeert "goede" uitkomsten waarbij de conditionele verdelingen van het mechanisme bij stap $n$ worden gedomineerd door een paar vaste, factoriserende verdelingen $(P^{(n)}, Q^{(n)})$.
• Slechte Gebeurtenissen: De methode houdt rekening met "slechte" uitkomsten (waar dominantie faalt) door hun waarschijnlijkheid $\delta_E$ te begrenzen. Het totale privacyverlies is de composities van de onafhankelijke stappen plus $\delta_E$.
• Dominantiecriterium: De auteurs leiden een criterium af op basis van reverse hazard-functies van Gaussian-mengselgewichten. Zij tonen aan dat als de posterior reverse hazard-functie puntsgewijs kleiner is dan de reverse hazard van een doelverdeling, dominantie geldt.
• Staartgrenzen: Om de parameters van de dominerende verdelingen te bepalen, leiden de auteurs analytische staartgrenzen af voor het privacyverlies van ternaire Gaussian-mengsels. Zij maken gebruik van een variational family van verdelingen om deze grenzen te verstrakken, en optimaliseren over temperatuurparameters om de standaardafwijking van de staartgrens te minimaliseren.
• Efficiëntie: Hoewel de initiële evaluatie $O(N^2 b^2)$ is, kunnen subsequentie evaluaties voor verschillende ruismultipliers $\sigma$ worden geamortiseerd naar $O(N b^2)$, wat het efficiënt maakt voor mechanismecalibratie.

Belangrijkste Bijdragen

1. Deterministische Accounting: Het artikel introduceert de eerste steekproefvrije methoden om deterministische $(\epsilon, \delta)$-DP-garanties te berekenen voor matrixmechanismen onder random allocation, waardoor de behoefte aan Monte Carlo-schatting wordt geëlimineerd.
2. Verbeterde Complexiteit voor DP-SGD: Voor het speciale geval van ongecorreleerde ruis (standaard DP-SGD) verbetert de voorgestelde Rényi-accountant de rekenkundige complexiteit van exacte accounting onder random allocation van exponentieel $O(2^\alpha)$ naar polynoom $O(b \alpha^2)$, wat aanzienlijk beter presteert dan eerdere exacte methoden.
3. Generalisatie naar Gecorreleerde Ruis: Het kader breidt zich uit tot willekeurige gebandeerde en niet-gebandeerde matrixmechanismen (inclusief Banded Square Root, Banded Inverse en Buffered Linear Toeplitz), en behandelt de complexe inter-stapcorrelaties die inherent zijn aan deze mechanismen.
4. Dual-regime Strakheid: De combinatie van de Rényi-accountant (sterk in het laag-privacy/grote-$\epsilon$-regime) en de conditionele compositie-accountant (strakker in het hoog-privacy/kleine-$\epsilon$-regime) biedt een uitgebreide accountingoplossing.

Resultaten

De auteurs evalueren hun methoden tegen de state-of-the-art Monte Carlo-accountant over verschillende matrixmechanismen (DP-SGD, BSR, BISR, BandMF, BandInvMF, BLT) en instellingen (single en multi-epoch).

• Nauwkeurigheid: In het laag-privacy-regime ($\epsilon \ge 2$) komt de Rényi-accountant nauw overeen met de Monte Carlo-referentie. In het hoog-privacy-regime ($\epsilon \le 1$) levert de conditionele compositie-accountant strakkere grenzen op, wat toelaat om kleinere gekalibreerde ruismultipliers $\sigma$ te gebruiken in vergelijking met Monte Carlo-schattingen.
• Robuustheid: De prestaties houden stand over verschillende bandbreedten ($p$) en aantallen batches ($b$).
• Bruikbaarheid: Experimenten op CIFAR-10 tonen aan dat de ruismultipliers die zijn afgeleid uit deze steekproefvrije garanties de bruikbaarheidsvoordelen van het gebruik van gecorreleerde ruis boven ongecorreleerde ruis behouden.
• Runtime: De methoden overwinnen de $O(\delta^{-1})$-afhankelijkheid van Monte Carlo-steekproeven. Hoewel de conditionele compositie-accountant hogere initiële kosten heeft voor grote $N$, zijn de geamortiseerde kosten voor calibratie aanzienlijk lager dan bij Monte Carlo voor strikte privacybudgetten.

Betekenis en Claims

Het artikel claimt de eerste steekproefvrije privacy-accounting te bieden voor mechanismen met gecorreleerde gradiënten en participaties. De betekenis hiervan ligt in:

• Het mogelijk maken van Deterministische Garanties: Het verwijdert de afhankelijkheid van probabilistische grenzen of willekeurige abstentie, wat vaak onpraktisch of theoretisch zwakker is voor productiesystemen.
• Schaalbaarheid: Door de complexiteit van exacte Rényi-accounting voor random allocation te reduceren van exponentieel naar polynoom, maakt het nauwkeurige privacy-accounting haalbaar voor schaalbare trainingruns waarbij Monte Carlo-steekproeven rekenkundig prohibitief zouden zijn.
• Praktische Calibratie: Het vermogen om efficiënt strakke grenzen te berekenen over een breed scala aan $\epsilon$ en $\delta$ faciliteert een betere calibratie van ruismultipliers, wat direct de afweging tussen bruikbaarheid en privacy in differentieel private deep learning verbetert.

De auteurs erkennen beperkingen, en merken op dat de complexiteit van de Rényi-accountant exponentieel blijft in de bandbreedte $p$ (hoewel polynoom in $\alpha$), en dat de conditionele compositiemethode vertrouwen op een grove partitie van uitkomsten die pessimistisch kan zijn. Zij suggereren dat toekomstig werk fijnmazigere partities en efficiëntere variational inference kan verkennen om grenzen verder te verstrakken.