Optimal Fairness under Local Differential Privacy

Technische Samenvatting: Optimale Rechtvaardigheid onder Lokale Differentieel Privaatheid

Probleemstelling
Machine learning-modellen vertrouwen steeds vaker op gevoelige attributen (bijv. ras, geslacht) voor beslissingen met grote impact, wat zorgen oproept over rechtvaardigheid en privacy. Hoewel Differentieel Privaatheid (DP) de standaard is voor privacy, is aangetoond dat centrale DP de onrechtvaardigheid potentieel kan verergeren. In contrast hiermee blijft Lokale Differentieel Privaatheid (LDP), waarbij data wordt verstoord voordat deze het apparaat van de gebruiker verlaat, onderbelicht wat betreft de interactie met rechtvaardigheid. Bestaande LDP-gebaseerde benaderingen voor rechtvaardigheid vertrouwen vaak op specifieke mechanismen zoals Generalized Randomized Response (GRR) of Randomized Response (RR) en zijn frequent beperkt tot binaire gevoelige attributen. Het kernprobleem dat wordt geadresseerd is hoe men optimale LDP-mechanismen kan ontwerpen die data-onrechtvaardigheid minimaliseren voor zowel binaire als meerwaardige gevoelige attributen, terwijl een niet-triviale bruikbaarheid behouden blijft, en hoe men theoretisch kan vaststellen hoe deze reductie in data-onrechtvaardigheid vertaalt naar verbeterde classificatierech Rechtvaardigheid.

Methodologie
De auteurs stellen een pre-processing framework voor waarbij gevoelige attributen worden verstoord met een optimaal LDP-mechanisme voordat de modeltraining plaatsvindt. De methodologie is verdeeld in theoretische afleiding en empirische validatie:

1. Afleiding van het Optimale Mechanisme:

   • Binaire Attributen: Voor binaire gevoelige attributen ($A \in \{0, 1\}$) leiden de auteurs een gesloten vorm optimale oplossing af. Ze formuleren het probleem als het minimaliseren van de ratio van data-onrechtvaardigheid in de verstoorde dataset ten opzichte van de originele dataset, onder een vaste privacybudget $\epsilon$. Het optimale mechanisme blijkt afhankelijk te zijn van de datadistributie (specifiek de conditionele kansen van het label gegeven het attribuut) en de privacyparameter. In tegen tegenover de standaard RR, behandelt het optimale mechanisme beide klassen niet noodzakelijkerwijs symmetrisch; het past de kans op het rapporteren van de ware waarde aan op basis van welke klasse meer voorkomt of discriminerend is.
   • Niet-Binaire Attributen: Voor meerwaardige attributen ($A \in [k]$) wordt het probleem geherformuleerd als een min-max lineair fractioneel programma. Het doel is om een data-onrechtvaardigheidsmetriek (specifiek Definitie 1, $\Delta$) te minimaliseren onder:
     • $\epsilon$-LDP restricties.
     • Rij-stochastische restricties (kansen sommeren tot 1).
     • Waarheidsgetrouwheid-restricties (kans op correct rapporteren $\ge$ kans op foutief rapporteren).
     • Bruikbaarheidsrestricties (het beperken van de totale foutkans tot een drempelwaarde $\zeta$).
       Deze optimalisatie wordt numeriek opgelost met de branch-and-bound methode.

2. Theoretische Koppeling aan Classificatierechvaardigheid:
   Het paper legt een theoretische verbinding vast tussen het minimaliseren van data-onrechtvaardigheid en het reduceren van classificatie-onrechtvaardigheid. Het introduceert het concept van Discrimination-Accuracy (DA) optimale classifiers—classifiers die niet strikt gedomineerd worden door een andere classifier in termen van zowel accuratesse als discriminatie. De auteurs bewijzen dat voor DA-optimale classifiers, trainen op data met lagere onrechtvaardigheid (specifiek lagere $\Delta'$) een reductie garandeert in de statistische pariteit-kloof van de resulterende classifier.

3. Experimentele Validatie:
   Het voorgestelde optimale mechanisme (OPT) wordt geëvalueerd op diverse datasets (Adult, LSAC, COMPAS, Bank, Student Performance, German Credit) met behulp van LightGBM en Logistische Regressie.

   • Baselines: OPT wordt vergeleken met standaard LDP-mechanismen (GRR/RR, Subset Selection) en state-of-the-art rechtvaardigheidsinterventies (FairProjection, FairBalance).
   • Metrieken: Prestaties worden gemeten via Accuratesse, Statistische Pariteit ($\Delta_{SP}$), Gelijkheid van Kansen ($\Delta_{EO}$) en Gemiddelde Gelijkheid van Kansen ($\Delta_{MEO}$).

Kernbijdragen

• Optimale Mechanismeontwerp: Het paper biedt het eerste closed-form optimale LDP-mechanisme voor binaire gevoelige attributen en een hanteerbaar numeriek framework voor niet-binaire attributen om data-onrechtvaardigheid te minimaliseren.
• Theoretische Rechtvaardiging: Het bewijst dat voor DA-optimale classifiers, het reduceren van data-onrechtvaardigheid via LDP pre-processing direct leidt tot een verminderde classificatie-onrechtvaardigheid, waarmee de kloof tussen privacy-bewuste pre-processing en downstream rechtvaardigheid wordt overbrugd.
• Empirische Superieuriteit: Het voorgestelde OPT-mechanisme presteert consistent beter dan bestaande LDP-mechanismen (GRR, SS) in het reduceren van onrechtvaardigheid, terwijl het een vergelijkbare accuratesse behoudt met non-private baselines.
• Superieure Trade-offs: Vergeleken met toegewijde pre-processing (FairBalance) en post-processing (FairProjection) rechtvaardigheidsmethoden, bereikt OPT een gunstiger accuratesse-rechtvaardigheid trade-off terwijl het tegelijkertijd de privacy van gevoelige attributen waarborgt.

Resultaten

• Binaire Attributen: Op de Adult en LSAC datasets vermindert OPT de statistische pariteit en de gelijkheid van kansen-kloven significant (bijv. bijna de helft van de kloven op LSAC) terwijl de accuratesse vergelijkbaar blijft met RR en SS.
• Niet-Binaire Attributen: Voor meerwaardige attributen (bijv. ras, gezinsinkomen) bereikt het numeriek opgeloste OPT-mechanisme lagere rechtvaardigheidskloven dan GRR en SS, met name bij hogere privacybudgetten ($\epsilon$), met verwaarloosbaar verlies aan accuratesse.
• Vergelijking met Rechtvaardigheidsmethoden: Wanneer vergeleken met FairProjection (post-processing) en FairBalance (pre-processing) bij gematchte accuratesse-niveaus, levert OPT over het algemeen lagere rechtvaardigheidskloven (bijv. op de COMPAS dataset verminderde OPT $\Delta_{SP}$ van 26,8% naar 24,3% vergeleken met FairProjection). Op de Bank dataset behaalde OPT een hogere accuratesse (90,1% vs 84,5%) en een lagere $\Delta_{EO}$ dan FairBalance.
• Integratie: OPT vervangt succesvol RR in het twee-staps framework van [13], wat de adaptiviteit aantoont in scenario's waar alleen geprivatiseerde gevoelige attributen beschikbaar zijn.

Betekenis en Claims
Het paper claimt dat Lokale Differentieel Privaatheid dient als een geprincieerd en effectief pre-processing interventie voor het versterken van rechtvaardigheid. In tegenstelling tot centrale DP, dat fundamenteel incompatibel kan zijn met rechtvaardigheid, biedt LDP een mechanisme waarbij de inherent aan privacy-behoud aanwezige randomisatie de data-onrechtvaardigheid actief kan mitigeren. De auteurs positioneren hun werk als een directe link tussen privacy-bewuste pre-processing en classificatie-rechtvaardigheid, waarbij zij aantonen dat de optimale verstoring van gevoelige attributen een eenvoudige maar krachtige tool is voor het mitigeren van bias zonder de bruikbaarheid van het model op te offeren. De resultaten suggereren dat LDP niet louter een privacytool is, maar een levensvatbare strategie voor rechtvaardigheidsversterking in machine learning-pipelines.