Computationally tractable robust differentially private mean estimation

Technische Samenvatting: Computationeel Tractabele Robuuste Differentieel Privaat Gemiddelde Schatting

Probleemstelling
Het artikel behandelt de uitdaging van het schatten van het gemiddelde van een hoogdimensionale distributie onder twee gelijktijdige beperkingen: differentieel privacy (DP) en robuustheid tegen uitschieters. De setting betreft een steekproef van $n$ vectoren in $\mathbb{R}^d$ getrokken uit een onbekende elliptische distributie $\nu = EC(\mu, \Sigma, F)$, die onderhevig is aan $\eta$-contaminatie. In dit model vervangt een tegenstander tot $\lfloor \eta n \rfloor$ observaties door willekeurige waarden die afhankelijk kunnen zijn van de oorspronkelijke steekproef. Het doel is om het populatiegemiddelde $\mu$ te schatten terwijl aan zero-concentrated differential privacy (zCDP) wordt voldaan en de statistische nauwkeurigheid behouden blijft ondanks heavy-tailed distributies en adversariële contaminatie.

Bestaande methoden in dit domein kampen met significante trade-offs. Veel robuuste private schatters vertrouwen op computationeel intensieve technieken zoals Markov Chain Monte Carlo (MCMC), sum-of-squares relaxaties of gradiëntgebaseerde optimalisatie, wat ze onpraktisch maakt voor hoogdimensionale data. Andere methoden, hoewel efficiënt, vertrouwen vaak op benaderde differential privacy of missen robuustheidsgaranties onder sterke privacy-noties zoals pure of zero-concentrated DP. Bovendien vereisen veel bestaande benaderingen parameters die moeilijk te interpreteren zijn of slecht schalen met de dimensie.

Methodologie: De Balloon Mean
De auteurs stellen een nieuwe estimator voor, de balloon mean, die complexe optimalisatiesubroutines vermijdt ten gunste van eenvoudige lineair-algebraïsche operaties. Het algoritme werkt iteratief door af te wisselen tussen twee stappen:

1. Gemiddelde Update (Projectie en Ruisige Averaging): Gegeven een huidige centrumschatting $\tilde{\mu}_{m-1}$ en een straal $\tilde{R}_{m-1}$, projecteert het algoritme alle datapunten op de Mahalanobis-bal $B_{\tilde{R}_{m-1}, \Sigma}(\tilde{\mu}_{m-1})$. Vervolgens berekent het het steekproefgemiddelde van deze projecties en voegt Gaussische ruis toe die gekalibreerd is aan de sensitiviteit van de projectie (die afhangt van de straal). Dit levert een nieuwe private gemiddelde schatting $\tilde{\mu}_m$ op.
2. Balloon Update (Private Straal Expansie): Het algoritme "blaast" de bal gecentreerd rond de nieuwe schatting $\tilde{\mu}_m$ op totdat deze een doelfractie $\tau_m$ van de data bevat. Dit wordt bereikt met een private versie van het AboveThreshold algoritme. Het algoritme bevraagt een reeks radii gedefinieerd door een geometrisch rooster ($R_{min} + \beta^i - 1$) en telt privaat hoeveel punten binnen elke straal vallen. Het stopt bij de eerste straal waar de ruisige telling de ruisige drempel overschrijdt die overeenkomt met de doelfractie $\tau_m$.

Het proces herhaalt zich voor $M$ iteraties. De uiteindelijke schatting is het gemiddelde van de projecties op de laatste ballon. De methode steunt op een paar interpreteerbare tuning parameters: de initiële straal, de grid expansiefactor $\beta$, het aantal iteraties $M$, en de doelfractie $\tau$.

Belangrijkste Bijdragen

1. Algoritmische Innovatie: De introductie van de balloon mean, een computationeel efficiënte estimator die iteratief het gemiddelde lokaliseert door privaat Mahalanobis-ballen te identificeren die de bulk van de data bevatten. Het vermijdt MCMC, sum-of-squares en gradiëntafdaling.
2. Theoretische Garanties: Het artikel biedt eind-steekproef foutmargen voor de balloon mean onder zowel heavy-tailed modellen (waar alleen het tweede moment bestaat) als adversariële gecontamineerde elliptische modellen. De analyse gaat uit van een bekende covariantie matrix $\Sigma$ (hoewel de auteurs opmerken dat een robuuste private schatting van $\Sigma$ kan worden gesubstitueerd).
3. Privacy en Complexiteit: De estimator voldoet aan $\rho$-zero-concentrated differential privacy (zCDP) met een natuurlijke extensie naar pure DP. De computationele complexiteit is $O(d^3 + nd^2 + Mnd + Mn \log n)$, wat reduceert tot $O(nd^2)$ onder standaard aannames ($n > d$ en $M < \log n$).

Theoretische Resultaten
Het belangrijkste theoretische resultaat (Theorem 4.4) stelt een bovengrens vast voor de Mahalanobis-fout $|\tilde{\mu}_M - \mu|_\Sigma$. Met hoge waarschijnlijkheid schaalt de fout als:
$$\sqrt{\frac{d}{n(\rho_- \wedge 1)}} + \sqrt{d\eta} + \sqrt{\frac{\log(\dots)}{n}}$$
waarbij $\rho_-$ het minimale privacybudget per iteratie is.

• Heavy-Tailed Setting ($\eta=0$): De estimator bereikt de minimax-optimale convergentiesnelheid tot aan logaritmische factoren.
• Adversariële Contaminatie ($\eta > 0$): De fout bevat een term die schaalt als $\sqrt{d\eta}$. De auteurs merken op dat hoewel bestaande ondergrenzen suggereren dat een afhankelijkheid van $\sqrt{\eta}$ (onafhankelijk van $d$) bereikbaar zou kunnen zijn, de huidige afhankelijkheid van $\sqrt{d}$ waarschijnlijk structureel is vanwege het onvermogen van het algoritme om contaminanten die langs een enkele richting in hoogdimensionale schillen zijn geplaatst, expliciet af te handelen. Ze erkennen dit gat, maar benadrukken dat geen enkel bestaand algoritme simultaan optimale contaminatie-afhankelijkheid, sterke privacy en computationele efficiëntie bereikt.

Empirische Evaluatie
Uit extensieve simulaties over dimensies ($d \in \{2, \dots, 128\}$), steekproefgroottes en privacybudgetten ($\rho \in \{0.01, 1\}$) blijkt de prestatie van de methode:

• Robuustheid: De balloon mean presteert significant beter dan bestaande computationeel tractabele private estimators (zoals COINPRESS, private Huber M-estimators, en instance-optimale gemiddelden) in gecontamineerde en heavy-tailed settings.
• Parameter Sensitiviteit: De methode vertoont een lage sensitiviteit voor de initiële gemiddelde gok, de initiële straal en de gridgrootte $\beta$. De parameter $\tau$ fungeert als een robuustheidscontrole; kleinere waarden van $\tau$ (die minder data uitsluiten) verbeteren de prestaties in gecontamineerde settings, maar kunnen de fout in 'clean' settings licht verhogen.
• Iteratie Aantal: De fout stabiliseert na 3–4 iteraties, wat suggereert dat $M=4$ voldoende is voor de meeste praktische toepassingen.

Betekenis en Claims
Het artikel positioneert de balloon mean als een praktische oplossing voor de "trilemma" van robuustheid, privacy en computationele tractabiliteit. De auteurs beweren dat, hoewel de methode mogelijk niet de theoretisch optimale afhankelijkheid van contaminatie in adversariële settings bereikt (vanwege structurele beperkingen), het een unieke combinatie biedt van:

1. Computationele Eenvoud: Het is implementeerbaar in hoge dimensies zonder complexe optimalisatie.
2. Sterke Privacy: Het voldoet aan zCDP, een sterkere privacy-notie dan de benaderde DP die vaak in robuuste settings wordt gebruikt.
3. Statistische Optimaliteit: Het bereikt minimax-rates in de heavy-tailed setting en biedt robuuste prestaties in gecontamineerde settings waar andere efficiënte methoden falen.

De auteurs concluderen dat de balloon mean een levensvatbaar instrument is voor private gemiddelde schatting in real-world scenario's met hoogdimensionale, potentieel heavy-tailed en gecontamineerde data, waarbij een balans wordt geboden tussen theoretische garanties en praktische haalbaarheid.