Technische Samenvatting: Private Rate-Constrained Optimization met Toepassingen voor Fair Learning

Probleemstelling

Veel kritieke machine learning-taken, variërend van groepsrechtvaardigheid (bijv. demografische pariteit, equalized odds) tot robuuste optimalisatie en kostengevoelig leren, kunnen worden geformuleerd als beperkte minimalisatieproblemen. Deze problemen vereisen het minimaliseren van de totale modelfout onder rate-constraints (snelheidsbeperkingen), die specifieke voorwaarden afdwingen op voorspellingspercentages over subpopulaties (bijv. het waarborgen van vergelijkbare positieve uitkomstpercentages over gendergroepen).

Een aanzienlijke uitdaging ontstaat bij het toepassen van Differential Privacy (DP) op deze problemen. Standaard DP-optimalisatietechnieken, zoals DP-SGD, vertrouwen op doelstellingen die ontleden over individuele voorbeelden, wat per-voorbeeld gradiënt clipping en ruistoevoeging mogelijk maakt. Echter, rate-constraints zijn afhankelijk van geaggregeerde statistieken over groepen, wat zorgt voor inter-sample afhankelijkheden die deze ontlegbaarheid schenden. Bestaande private leermethoden hebben zich grotendeels gericht op specifieke rechtvaardigheidsbeperkingen of vertrouwen op proxy-doelstellingen die niet uitbreiden naar de bredere familie van rate-constraints die in de praktijk voorkomen. Er is een gebrek aan een algemeen DP-framework dat in staat is om willekeurige rate-constrained problemen aan te pakken terwijl formele privacygaranties worden behouden.

Methodologie: RaCO-DP

Om de incompatibiliteit tussen rate-constraints en standaard DP-SGD aan te pakken, stellen de auteurs RaCO-DP voor, een differentieel private variant van het Stochastic Gradient Descent-Ascent (SGDA) algoritme. De methode lost de Lagrangian-formulering van het rate-constrained probleem op.

Belangrijke Technische Componenten

1. Gegeneraliseerde Rate Constraints:
   De auteurs introduceren een gegeneraliseerde vorm van rate-constraints die toepasbaar is in multi-class settings. Deze beperkingen zijn gedefinieerd op basis van een "globale partitie" van de dataset ($D_1, \dots, D_Q$) en maken het mogelijk dat elke constraint opereert op elke recombinatie van deze sub-datasets. Deze structuur maakt de efficiënte private schatting van noodzakelijke statistieken mogelijk.

2. Private Histogram Berekening:
   De kerninnovatie ligt in het berekenen van een private histogram bij elke trainingsstap. Voor een mini-batch $B^{(t)}$ berekent het algoritme zachte voorspellingspercentages voor elke klasse $k$ binnen elke partitie $D_q$.

   • In plaats van de constraints direct op de ruwe data te berekenen, aggregeert het algoritme softmax-voorspellingen in een histogram $H^{(t)}$.
   • Om privacy te waarborgen, wordt Laplace-ruis toegevoegd aan dit histogram. Omdat de $\ell_1$-sensitiviteit van het histogram 1 is (elk sample behoort tot precies één partitie en de softmax-kansen sommeren tot 1), zorgt het toevoegen van Laplace-ruis voor $\epsilon$-DP voor het histogram zelf.

3. Primal en Dual Updates via Post-Processing:

   • Primal Update (Modelparameters $\theta$): Het algoritme afleidt per-sample gradiënten voor de Lagrangian door de private histogram $\hat{H}^{(t)}$ te post-processen. Dit stelt de regularisatieterm (afgeleid van de constraints) in staat om te worden ontleed in per-sample termen, waardoor standaard DP-SGD technieken mogelijk worden: het clippen van per-sample gradiënten, middelen en het toevoegen van Gaussische ruis.
   • Dual Update (Lagrange Multipliers $\lambda$): De constraint-waarden die nodig zijn voor de dual ascent worden berekend door de private histogram $\hat{H}^{(t)}$ te post-processen. Omdat het histogram al geprivatiseerd is, zorgt de post-processing eigenschap van DP ervoor dat het evalueren van de constraints en het updaten van $\lambda$ geen extra privacykosten met zich meebrengt.

4. Convergentieanalyse:
   Het artikel biedt een nieuwe convergentieanalyse voor SGDA in de aanwezigheid van vertekende gradiëntschattingen en privacyruis.

   • De analyse maakt gebruik van de lineaire structuur van de duale parameter om snellere convergentiesnelheden te bereiken vergeleken met eerdere non-convex min-max analyses.
   • Het bewijst dat RaCO-DP convergeert naar een benaderd stationair punt, zelfs voor non-convex optimalisatieproblemen, met foutmarges die afhankelijk zijn van het privacybudget, de datasetgrootte en de ruisschalen.

Belangrijkste Bijdragen

• Algemeen Framework: Introductie van het eerste algemene DP-framework voor willekeurige rate-constrained problemen, wat verder gaat dan de smalle scope van rechtvaardigheids-specifieke methoden.
• Algoritmische Innovatie: Ontwikkeling van RaCO-DP, die gebruikmaakt van private histogrammen om de privacykosten van de constraint-evaluatie te ontkoppelen van de gradiëntberekening, waardoor het nodig zijn van meerdere private queries wordt vermeden.
• Theoretische Garanties: Een formeel convergentiebewijs voor SGDA onder DP met vertekende gradiënten, wat convergentie naar een benaderd stationair punt aantoont voor non-convex-lineaire losses.
• Schaalbaarheid: Demonstratie dat de methode schaalt naar diepe neurale netwerken (ResNet16) en een groot aantal gelijktijdige constraints afhandelt (tot 18 subgroup constraints).

Experimentele Resultaten

De auteurs evalueren RaCO-DP op vier standaard benchmarks (Adult, Credit-Card, Parkinsons, CelebA) en diverse type constraints (Demographic Parity, Equalized Odds, False Negative Rate).

• Utility-Fairness-Privacy Trade-off: RaCO-DP Pareto- domineert consistent bestaande private leermethoden (bijv. DP-FERMI, Tran et al., Jagielski et al.). Het bereikt een hogere nauwkeurigheid bij een vaste fairness disparity vergeleken met baselines onder dezelfde privacybudgetten.
• Deep Learning Prestaties: Op de CelebA dataset met een ResNet16 model bereikt RaCO-DP 90% nauwkeurigheid met slechts een 10% demografische disparity gap bij $\epsilon=1$, wat dicht bij de prestaties van non-private modellen (95% nauwkeurigheid) ligt.
• Constraint Satisfactie: In tegen tegenstelling tot eerdere methoden die vertrouwen op indirecte hyperparameter-tuning, stelt RaCO-DP beoefenaars in staat om de maximale disparity ($\gamma$) direct te specificeren. De methode realiseert consequent deze vooraf gespecificeerde constraint-waarden.
• Computationele Efficiëntie: RaCO-DP is ongeveer drie grootheden sneller dan DP-FERMI op tabulaire data, omdat het de zware computationele overhead van de proxy-doelstelling gebruikt die in eerder werk voorkomt.
• Lage Privacybudgetten: De methode vertoont een gracieuze degradatie; zelfs bij strikte privacybudgetten ($\epsilon=0.01$) behoudt het een redelijke nauwkeurigheid (ca. 80%) en voldoet het aan de constraints, hoewel met een grotere variantie in de disparity metrics.

Betekenis en Claims

Het artikel claimt dat RaCO-DP een kritieke kloof in betrouwbaar machine learning overbrugt door private optimalisatie mogelijk te maken voor een brede klasse van rate-constrained problemen, inclusief maar niet beperkt tot rechtvaardigheid.

• Herdefiniëring van Trade-offs: De resultaten suggereren dat de privacy-fairness trade-off minder significant kan zijn dan voorheen werd aangenomen. Door gebruik te maken van een gepaste algoritmische vormgeving (private histogrammen en Lagrangian formulering), is het mogelijk om tegelijkertijd sterke prestaties in utility, privacy en constraint-satisfactie te behalen.
• Directe Controle: Het framework biedt beoefenaars een betrouwbaardere en directere methode voor het afdwingen van constraints vergeleken met indirecte penaliseringsmethoden, waardoor expliciete specificatie van fairness of veiligheidslimieten mogelijk is.
• Brede Toepasbaarheid: Door te generaliseren voorbij binaire classificatie en specifieke rechtvaardigheidsmetrieken, opent de aanpak de deur naar private learning in medische settings (bijv. het beperken van false negative rates) en andere domeinen waar geaggregeerde rate-constraints cruciaal zijn.

De auteurs concluderen dat hoewel hun werk zich richt op groepsrechtvaardigheid en rate-constraints, de methodologie een robuuste fundering biedt voor toekomstige exploratie naar individuele rechtvaardigheid en andere robuustheidscriteria binnen het differential privacy framework.