Technische Samenvatting: INO-SGD: Aanpakken van Utiliteitsongelijkheid onder Geïndividualiseerde Differentiële Privacy

Probleemstelling

Het artikel behandelt een kritieke beperking in Geïndividualiseerde Differentiële Privacy (IDP), een raamwerk dat gegevensbezitters toestaat om op basis van hun gevoeligheidsvereisten verschillende privacybudgetten ($\epsilon_n$) in te stellen. Hoewel bestaande IDP-algoritmen (specifiek IDP-SGD-varianten: SAMPLE en SCALE) succesvol voldoen aan individuele privacybeperkingen, veroorzaken ze onbedoeld een ernstig probleem van utiliteitsongelijkheid.

Bij IDP-SGD krijgen gegevensbezitters met strengere privacyvereisten (lagere $\epsilon_n$) ofwel lagere bemonsteringspercentages (in SAMPLE) of kleinere gradiënt-afkapdrempels (in SCALE) toegewezen. Bijgevolg dragen tijdens het trainen de gradiënten van deze "privacybewusteren" minder bij aan de modelupdate dan de gradiënten van "minder privacybewuste" eigenaren. Het artikel identificeert twee specifieke negatieve fenomenen die het gevolg zijn van deze onbalans:

1. Minority Initial Drop (MID): Een initiële fase waarin de modelutiliteit voor de privacybewustere groepen niet verbetert of zelfs verslechtert, terwijl de utiliteit voor minder privacybewuste groepen normaal verbetert.
2. Biased Optimization Objective (BOO): Het uiteindelijk getrainde model convergeert naar een staat die de minder privacybewuste groepen bevoordeelt, wat resulteert in aanzienlijk slechtere prestaties op gegevens van de privacybewusteren eigenaren.

Cruciaal is dat de auteurs betogen dat bestaande technieken voor het corrigeren van data-ongelijkheid (bijvoorbeeld oversampling, herverdeling van het verlies) ongeschikt zijn voor IDP, omdat ze óf individuele privacybudgetten schenden, óf beschikbare privacybudgetten onvoldoende benutten (wat de algehele utiliteit verlaagt), óf dat hun effecten worden geneutraliseerd door de gradiënt-afkapmechanismen die inherent zijn aan DP.

Methodologie: INO-SGD

Om dit op te lossen, stellen de auteurs INO-SGD (Individualized Noisy Ordered SGD) voor. De kernintuïtie is om strategisch minder belangrijke gradiënten binnen elke batch te verzwakken zonder IDP-beperkingen te schenden.

Kernmechanisme

1. Op Verlies Gebaseerde Ordening: Binnen elke bemonsterde batch worden gradiënten in aflopende volgorde gesorteerd op basis van hun individuele verlieswaarden. De auteurs stellen dat gradiënten met een hoger verlies "moeilijkere" of belangrijkere datapunten vertegenwoordigen die het model moet leren, ongeacht het privacyniveau van de eigenaar.
2. Tail Importance Function (TIF): Een vooraf gedefinieerde functie, $f_{tail}$, koppelt de positie van een gradiënt in de gesorteerde lijst aan een belangrijkheidsscore tussen 0 en 1.
   • Gradiënten in de "kop" (hoog verlies) krijgen een score van 1 (volledig behouden).
   • Gradiënten in de "staart" (laag verlies) krijgen scores $< 1$ (verzwakt).
3. Batch Importance Function (BIF): De TIF wordt omgezet in een BIF, $f_t$, die belangrijkheidsscores toekent aan het continue bereik van geaccumuleerde afkapdrempels binnen de batch.
4. Gewogen Afkappen: In plaats van gradiënten simpelweg af te kappen op de drempel van de eigenaar $C_{o(d)}$, schaalt INO-SGD de afgekapte gradiënt met de berekende belangrijkheidsscore $\rho_k$.
   • Als een gradiënt als onbelangrijk wordt beschouwd (laag verlies), wordt zijn norm beperkt tot een waarde die strikt kleiner is dan $C_{o(d)}$.
   • Deze vermindering van de norm van "gemakkelijke" gradiënten creëert "ruimte" binnen het totale modulaire gevoeligheidsbudget om de bijdrage van "moeilijke" gradiënten (vaak van privacybewusteren eigenaren) effectief te behouden zonder de totale ruisgrootte te verhogen.
5. Privacybehoud: Het algoritme zorgt ervoor dat de modulaire gevoeligheid van het mechanisme met betrekking tot een enkel datapunt $d$ begrensd blijft door de afkapdrempel van zijn eigenaar $C_{o(d)}$. Dit wordt bereikt omdat de herweging gebaseerd is op de volgorde van verliezen (afgeleid van het model van de vorige iteratie, dat reeds DP-beschermd is) en de totale verandering in de som van de gradiënten bij het toevoegen/verwijderen van een datapunt wiskundig begrensd is door de eigen afkapdrempel van dat datapunt.

Belangrijkste Bijdragen

1. Identificatie van IDP-Geïnduceerde Utiliteitsongelijkheid: Het artikel toont theoretisch aan dat zelfs op gebalanceerde datasets IDP-SGD utiliteitsongelijkheid (MID en BOO) induceert als gevolg van de dispariteit in bemonsteringspercentages en afkapdrempels die nodig zijn om individuele privacybudgetten te voldoen.
2. Het INO-SGD Algoritme: Een nieuw optimalisatiealgoritme dat voldoet aan IDP terwijl het utiliteitsongelijkheid mitigeert. Dit bereikt het door gradiënten met laag verlies (vaak van minder privacybewuste eigenaren) te verzwakken om gradiënten met hoog verlies (vaak van privacybewusteren eigenaren) te prioriteren, wat effectief een andere doelwitfunctie optimaliseert.
3. Theoretische Garanties:
   • Privacy: Bewezen te voldoen aan $(\alpha, \bar{\epsilon})$-Rényi Geïndividualiseerde Differentiële Privacy (IRDP) met hetzelfde privacyverbruik als standaard IDP-SGD.
   • Doelwit: Het algoritme blijkt effectief een Mixed Conditional Value-at-Risk (CVaR) doelwit te minimaliseren (of een Gewogen Gemiddelde met niet-stijgende gewichten). Dit doelwit prioriteert het verminderen van de verliezen van de slechtst afgelegen groepen (privacybewusteren eigenaren) in plaats van het minimaliseren van het gemiddelde verlies.
4. Generalisatie (INO-SGM): De auteurs generaliseren het mechanisme naar INO-SGM (Individualized Noisy Ordered Gaussian Mechanism), toepasbaar op elke functie waar data-ordening belangrijk is, niet alleen bij gradiëntafdaal.

Experimentele Resultaten

De auteurs evalueerden INO-SGD tegen IDP-SGD over verschillende datasets (MNIST, CIFAR-10, CIFAR-100, Pneumonia, Cardiotocography) en modellen (CNN's, ResNet-18, LSTMs).

• Utiliteitsbalans: INO-SGD verbeterde consequent de prestaties (recall/nauwkeurigheid) van de privacybewusteren gegevensbezitters. In meerdere experimenten werd de prestatiekloof tussen privacybewuste en minder privacybewuste groepen aanzienlijk verkleind.
• Algemene Utiliteit: In tegenstelling tot de typische privacy-utiliteit trade-off, offerde INO-SGD de algehele modelutiliteit niet op. In veel gevallen bereikte het een gelijke of licht hogere algehele nauwkeurigheid dan IDP-SGD. De auteurs schrijven dit toe aan het verwijderen van "ruisachtige" of minder informatieve gradiënten die het model afleiden.
• Robuustheid: Het algoritme toonde robuustheid ten opzichte van hyperparameterkeuzes (staartlengte $\gamma$, parameters van de Beta-verdeling $\alpha, \beta$) en bleef effectief onder labelruis en adaptieve afkapinstellingen.
• Privacyverificatie: Lidmaatschapsinference-aanvallen (LiRA) bevestigden dat INO-SGD privacybescherming biedt die vergelijkbaar is met IDP-SGD, zonder significante lekken.

Betekenis en Claims

Het artikel claimt het eerste werk te zijn dat het specifieke probleem van IDP-geïnduceerde utiliteitsongelijkheid identificeert en aanpakt. De betekenis hiervan ligt in:

• Ethische AI: Het zorgt ervoor dat de inzet van privacybehoudende modellen niet onbedoeld discrimineert tegen gebruikers met gevoelige gegevens (bijvoorbeeld patiënten met gestigmatiseerde ziekten) door hen een model te bieden dat slecht presteert op hun specifieke gegevens.
• Efficiëntie: Het lost de trade-off op waarbij het voldoen aan individuele privacyvereisten voorheen leidde tot suboptimale modelprestaties voor specifieke groepen. INO-SGD stelt modelbezitters in staat om de volledige privacybudgetten van alle eigenaren te benutten terwijl een gebalanceerde prestatie wordt behouden.
• Pareto-superioriteit: De auteurs tonen aan dat INO-SGD naieve benaderingen (zoals uniform verlagen van privacybudgetten of willekeurige undersampling) Pareto-domeert, en een superieure trade-offcurve biedt tussen algehele utiliteit en utiliteitsbalans.

De auteurs erkennen bescheiden dat hoewel INO-SGD de balans verbetert, er nog steeds een fundamentele IDP-balans-utiliteit trade-off bestaat; te agressief streven naar balans (via extreme verzwakking) kan uiteindelijk de algehele utiliteit verslechteren. INO-SGD duwt de Pareto-grens echter dichter naar het ideaal dan bestaande methoden.