Technische Samenvatting: Trade-off Functies voor DP-SGD met Subsampling Gebaseerd op Random Shuffling

Probleemstelling

Differentieel Private Stochastic Gradient Descent (DP-SGD) is het standaardmechanisme voor het trainen van deep learning-modellen onder privacybeperkingen. Hoewel het $f$-Differentiële Privacy ($f$-DP) kader de strakst mogelijke karakterisering van privacygaranties biedt via trade-off functies tussen vals-positieve en vals-negatieve rates, hebben bestaande analyses zich voornamelijk gericht op Poisson-subsampling (waarbij datapunten onafhankelijk worden opgenomen in minibatches met een vaste waarschijnlijkheid).

Echter, praktische implementaties van DP-SGD en stochastische optimalisatie maken doorgaans gebruik van random shuffling, waarbij het dataset één keer per epoch wordt gepermuteerd en wordt opgedeeld in minibatches van vaste grootte. Dit verschil tussen het geanalyseerde algoritme (Poisson) en het ingezette algoritme (shuffling) heeft ervoor gezorgd dat de privacygaranties van real-world systemen onnauwkeurig zijn gekarakteriseerd. Eerdere werken over shuffled DP-SGD hebben slechts bovenste grenzen voor de trade-off functie (onderste grenzen voor privacyverlies) geleverd via expliciete adversariële gebeurtenissen of numerieke evaluaties, zonder gesloten-vormige, transparante uitdrukkingen. Bovendien wijzen recente onmogelijkheidsresultaten erop dat voor lage ruis-multiplicatoren ($\sigma \le 1/\sqrt{2 \ln M}$) de trade-off functie bewezen begrensd is tot een afstand van de ideale diagonaal van willekeurig gissen ($1-a$), maar het gedrag in het regime met hoge ruis een open vraag bleef die een strakke, gesloten-vormige analyse vereiste.

Methodologie

De auteurs leiden een strakke, gesloten-vormige analyse af van de trade-off functie voor DP-SGD met random shuffling binnen het $f$-DP kader. De methodologie verloopt via de volgende fasen:

1. Adversariële Reductie: Het probleem wordt gereduceerd tot een scalair hypothese-toetsingsprobleem. Onder het worst-case adversariële model (dat de bijdrage van één enkel afwijkend record kan isoleren) observeert de adversariër $M$ rondes. Onder de nulhypothese ($H_0$) zijn alle observaties pure ruis $N(0, 1)$. Onder de alternatieve hypothese ($H_1$) bevat precies één ronde (uniform willekeurig gekozen door de shuffling-permutatie) een verschoven observatie $N(1/\sigma, 1)$, terwijl de rest ruis blijft.
2. Likelihood Ratio Test: Volgens het lemma van Neyman-Pearson threshold de optimale test de likelihood ratio, wat reduceert tot het thresholden van het steekproefgemiddelde van lognormale variabelen $Y_j = \exp(X_j/\sigma - 1/(2\sigma^2))$, waarbij $X_j \sim N(0, 1)$.
3. Niet-Asymptotische Analyse (Berry-Esseen): Voor één epoch passen de auteurs de stelling van Berry-Esseen toe om de convergentiesnelheid van het steekproefgemiddelde van deze lognormale variabelen naar een normale verdeling te begrenzen. Dit levert een concrete, niet-asymptotische onderste grens voor de trade-off functie $f(a)$ op voor het regime $\sigma \ge \sqrt{3/\ln M}$. De grens wordt uitgedrukt als $f(a) \ge 1 - a - \delta$, waarbij $\delta$ een expliciete functie is van de ruis-multiplicator $\sigma$ en het aantal rondes $M$.
4. Asymptotische Analyse (Edgeworth-expansie): Om de Berry-Esseen-grenzen te verbeteren, die beperkt zijn door een $O(1/\sqrt{M})$ foutterm, introduceren de auteurs een bewijstechniek gebaseerd op een twee-term Edgeworth-expansie. Deze generalisatie van de Centrale Limietstelling maakt een fijnere asymptotische schatting mogelijk van de verdeling van de som van lognormale variabelen. Deze benadering vestigt het asymptotische gedrag van de trade-off functie als $M \to \infty$ met het aantal epochs $E$ dat schaalt als $E = c_M^2 M$ waarbij $c_M \to 0$.

Belangrijkste Bijdragen

1. Gesloten-vormige Onderste Grens voor Één Epoch: Het artikel biedt de eerste strakke, gesloten-vormige onderste grens voor de trade-off functie van shuffled DP-SGD in het regime met hoge ruis ($\sigma \ge \sqrt{3/\ln M}$). De grens wordt gegeven door:
   $$f(a) \ge 1 - a - \delta$$
   waarbij $\delta$ expliciet wordt gedefinieerd in termen van $\sigma$ en $M$ (Stelling 4.1). Dit resultaat is strak tot op constante factoren binnen het bewijskader van Berry-Esseen.
2. Concrete Aanbevelingen voor Parameters: De auteurs leiden specifieke parameterinstellingen af voor betekenisvolle differentiële privacy. Voor één epoch ($E=1$) met $\sigma=1$ en $\delta=10^{-2}$ tonen ze aan dat een datasetgrootte van $N \approx 1.14 \times 10^7$, opgedeeld in $M \approx 1.14 \times 10^6$ rondes, voldoende is. Dit demonstreert dat betekenisvolle privacy haalbaar is in federated learning-scenario's met grote datasets en één epoch.
3. Asymptotische Karakterisering van Gaussian-DP: Met behulp van Edgeworth-expansies stelt het artikel vast dat voor vaste $\sigma$, naarmate $M \to \infty$ en $E = c_M^2 M$ met $c_M \to 0$, de $E$-voudig samengestelde trade-off functie uniform convergeert naar de diagonaal van willekeurig gissen ($1-a$). Dit verbetert de afhankelijkheid van het aantal epochs van de lineaire $O(E)$-boete die door naïeve compositie wordt gesuggereerd, naar een asymptotische $O(\sqrt{E})$-scheiding (Corollarium 5.3).
4. Vergelijking met Poisson-subsampling: De auteurs vergelijken hun asymptotische resultaten met de corresponderende asymptotiek van Poisson-subsampling. Ze constateren dat in de limiet van lage ruis ($\sigma \to 0$), random shuffling asymptotisch een factor $\sqrt{2}$ dichter bij de ideale diagonaal van willekeurig gissen ligt dan Poisson-subsampling, terwijl de twee regimes equivalent worden in de limiet van hoge ruis ($\sigma \to \infty$).

Resultaten

• Regimegeldigheid: De analyse is geldig voor $\sigma \ge \sqrt{3/\ln M}$. Dit regime is complementair aan het onmogelijkheidsresultaat van Ertan en van Dijk [12], dat aantoont dat voor $\sigma < 1/\sqrt{2 \ln M}$ de trade-off functie begrensd is tot een afstand van $1-a$. Samen mapping deze resultaten het privacylandschap van shuffled DP-SGD.
• Compositiegrenzen:
  • Niet-Asymptotisch: Het itereren van de één-epoch-grens levert $f^{\otimes E}(a) \ge (1-\delta)^E - a$ op, wat een lineaire afhankelijkheid impliceert van $E$ voor het privacyverlies.
  • Asymptotisch: De op Edgeworth gebaseerde analyse suggereert een strakkere afhankelijkheid, waarbij de scheiding van de diagonaal schaalt als $O(\mu \sqrt{E})$ in plaats van $O(\mu E)$, mits $E$ sub-lineair schaalt met $M$.
• Praktische Implicaties: Het artikel identificeert het één-epoch-regime als het "praktische sweet spot" voor shuffled DP-SGD. In federated learning-scenario's waarbij clients aan weinig epochs deelnemen, zijn betekenisvolle privacygaranties ($\delta \approx 0.01$) haalbaar met realistische datasetgroottes. Omgekeerd wijst het artikel op een "multi-epoch explosie" waarbij het verhogen van $E$ onder de lineaire compositiegrens de vereiste datasetgrootte $N$ snel onpraktisch maakt (bijvoorbeeld door $N \sim 10^{11}$ te vereisen voor $E=100$).

Betekenis en Claims

Het artikel claimt een strakke, gesloten-vormige analyse te bieden die de discrepantie oplost tussen de in de literatuur geanalyseerde algoritmen (Poisson) en die welke in de praktijk worden ingezet (random shuffling). Door transparante, interpreteerbare grenzen af te leiden, stellen de auteurs praktici in staat om parametervereisten direct af te lezen zonder te vertrouwen op ondoorzichtige numerieke hulpmiddelen.

De betekenis van het werk ligt in:

1. Brug slaan tussen Theorie en Praktijk: Valideren dat random shuffling, de standaard in machine learning-frameworks, een rigoureuze privacyanalyse toelaat die vaak gunstiger is dan Poisson-subsampling in regimes met lage ruis.
2. Definiëren van het Privacylandschap: Bestaande onmogelijkheidsresultaten aanvullen om de precieze ruisdrempels te definiëren die nodig zijn voor betekenisvolle privacy in shuffled DP-SGD.
3. Richting geven aan Parameterselectie: Het bieden van concrete formules voor het selecteren van $M$, $N$ en $\sigma$ om specifieke privacybudgetten te bereiken, wat vooral relevant is voor federated learning-toepassingen.

De auteurs blijven bescheiden wat betreft toekomstig werk, met de opmerking dat hoewel de asymptotische resultaten een verbeterde $\sqrt{E}$-afhankelijkheid voor meerdere epochs suggereren, het afleiden van een concreet, gesloten-vormig bewijs van deze afhankelijkheid (in tegenstelling tot de asymptotische limiet) een open probleem blijft. Daarnaast wordt het expliciet maken van de sequenties $\delta_M$ en $\gamma_M$ in de Edgeworth-expansie om een concrete multi-epoch-grens te verkrijgen geïdentificeerd als een richting voor toekomstig onderzoek.