Computationally tractable robust differentially private mean estimation

Technisches Resümee: Rechentechnisch handhabbare, robuste differenziell private Mittelwertschätzung

Problemstellung
Die vorliegende Arbeit befasst sich mit der Herausforderung, den Mittelwert einer hochdimensionalen Verteilung unter zwei gleichzeitigen Nebenbedingungen zu schätzen: differenzieller Privatsphäre (Differential Privacy, DP) und Robustheit gegenüber Ausreißern. Das Szenario umfasst eine Stichprobe von $n$ Vektoren in $\mathbb{R}^d$, die aus einer unbekannten elliptischen Verteilung $\nu = EC(\mu, \Sigma, F)$ gezogen wurden, welche einer $\eta$-Kontamination unterliegt. In diesem Modell ersetzt ein Angreifer bis zu $\lfloor \eta n \rfloor$ Beobachtungen durch beliebige Werte, die auch von der ursprünglichen Stichprobe abhängen können. Das Ziel ist es, den Populationsmittelwert $\mu$ zu schätzen, während gleichzeitig Zero-Concentrated Differential Privacy (zCDP) erfüllt und die statistische Genauigkeit trotz schwerfälliger (heavy-tailed) Verteilungen und adversarieller Kontamination gewahrt bleibt.

Bestehende Methoden in diesem Bereich stehen vor erheblichen Kompromissen. Viele robuste private Schätzer stützen sich auf rechenintensive Techniken wie Markov-Chain-Monte-Carlo-Verfahren (MCMC), Sum-of-Squares-Relaxierungen oder gradientenbasierte Optimierung, was sie für hochdimensionale Daten unpraktikabel macht. Andere sind zwar effizient, verlassen sich jedoch oft auf approximative differenzielle Privatsphäre oder lassen Robustheitsgarantien unter starken Privatsphäre-Notionen wie reiner oder Zero-Concentrated DP vermissen. Darüber hinaus erfordern viele bestehende Ansätze Parameteranpassungen, die schwer zu interpretieren sind oder schlecht mit der Dimension skalieren.

Methodik: Der Ballon-Mittelwert (Balloon Mean)
Die Autoren schlagen einen neuen Schätzer vor, den Ballon-Mittelwert, der komplexe Optimierungssubroutinen zugunsten einfacher linear-algebraischer Operationen vermeidet. Der Algorithmus arbeitet iterativ und wechselt zwischen zwei Schritten:

1. Mittelwert-Update (Projektion und verrauschtes Mittelwertbilden): Gegeben seien ein aktueller Zentrumsschätzwert $\tilde{\mu}_{m-1}$ und ein Radius $\tilde{R}_{m-1}$. Der Algorithmus projiziert alle Datenpunkte auf den Mahalanobis-Ball $B_{\tilde{R}_{m-1}, \Sigma}(\tilde{\mu}_{m-1})$. Er berechnet dann den Stichprobenmittelwert dieser Projektionen und fügt Gauß-Rauschen hinzu, das auf die Sensitivität der Projektion (welche vom Radius abhängt) kalibriert ist. Dies liefert einen neuen privaten Mittelwertschätzwert $\tilde{\mu}_m$.
2. Ballon-Update (Private Radius-Expansion): Der Algorithmus „bläst“ den Ball, der um den neuen Schätzwert $\tilde{\mu}_m$ zentriert ist, so weit auf, bis er einen Zielanteil $\tau_m$ der Daten enthält. Dies wird durch eine private Version des AboveThreshold-Algorithmus erreicht. Der Algorithmus fragt eine Sequenz von Radien ab, die durch ein geometrisches Gitter ($R_{min} + \beta^i - 1$) definiert sind, und zählt privat, wie viele Punkte innerhalb jedes Radius liegen. Er stoppt beim ersten Radius, bei dem der verrauschte Zähler den verrauschten Schwellenwert überschreitet, der einem Zielanteil $\tau_m$ entspricht.

Der Prozess wiederholt sich für $M$ Iterationen. Der endgültige Schätzwert ist der Mittelwert der Projektionen auf den finalen Ballon. Die Methode stützt sich auf wenige interpretierbare Tuning-Parameter: den Anfangsradius, den Gitter-Expansionsfaktor $\beta$, die Anzahl der Iterationen $M$ und den Zielanteil $\tau$.

Wesentliche Beiträge

1. Algorithmische Innovation: Die Einführung des Ballon-Mittelwerts, eines recheneffizienten Schätzers, der den Mittelwert iterativ lokalisiert, indem er privat Mahalanobis-Bälle identifiziert, die den Großteil der Daten enthalten. Er vermeidet MCMC, Sum-of-Squares und Gradientenabstieg.
2. Theoretische Garantien: Die Arbeit liefert Fehlerschranken für endliche Stichproben für den Ballon-Mittelwert sowohl unter schwerfälligen Modellen (bei denen nur das zweite Moment existiert) als auch unter adversariell kontaminierten elliptischen Modellen. Die Analyse setzt eine bekannte Kovarianzmatrix $\Sigma$ voraus (obwohl die Autoren anmerken, dass ein robuster privater Schätzer für $\Sigma$ eingesetzt werden kann).
3. Privatsphäre und Komplexität: Der Schätzer erfüllt $\rho$-Zero-Concentrated Differential Privacy (zCDP) mit einer natürlichen Erweiterung zu reiner DP. Die rechnerische Komplexität beträgt $O(d^3 + nd^2 + Mnd + Mn \log n)$, was unter Standardannahmen ($n > d$ und $M < \log n$) auf $O(nd^2)$ reduziert.

Theoretische Ergebnisse
Das Hauptresultat (Theorem 4.4) etabliert eine obere Schranke für den Mahalanobis-Fehler $|\tilde{\mu}_M - \mu|_\Sigma$. Mit hoher Wahrscheinlichkeit skaliert der Fehler als:
$$\sqrt{\frac{d}{n(\rho_- \wedge 1)}} + \sqrt{d\eta} + \sqrt{\frac{\log(\dots)}{n}}$$
wobei $\rho_-$ das pro Iteration zugewiesene minimale Privatsphäre-Budget ist.

• Schwerfälliges Setting ($\eta=0$): Der Schätzer erreicht die minimax-optimale Konvergenzrate unter Berücksichtigung logarithmischer Faktoren.
• Adversarielles Kontaminations-Setting ($\eta > 0$): Der Fehler beinhaltet einen Term, der mit $\sqrt{d\eta}$ skaliert. Die Autoren merken an, dass, obwohl bestehende untere Schranken nahelegen, dass eine Abhängigkeit von $\sqrt{\eta}$ (unabhängig von $d$) erreichbar sein könnte, die aktuelle Abhängigkeit von $\sqrt{d}$ wahrscheinlich strukturell bedingt ist, da der Algorithmus nicht in der Lage ist, Kontaminationen, die entlang einer einzelnen Richtung in hochdimensionalen Schalen platziert sind, explizit zu behandeln. Sie räumen diese Lücke ein, betonen jedoch, dass kein existierender Algorithmus gleichzeitig optimale Kontaminationsabhängigkeit, starke Privatsphäre und rechnerische Effizienz erreicht.

Empirische Evaluierung
Umfangreiche Simulationen über verschiedene Dimensionen ($d \in \{2, \dots, 128\}$), Stichprobengrößen und Privatsphäre-Budgets ($\rho \in \{0.01, 1\}$) demonstrieren die Leistungsfähigkeit der Methode:

• Robustheit: Der Ballon-Mittelwert übertrifft bestehende rechentechnisch handhabbare private Schätzer (wie COINPRESS, private Huber-M-Schätzer und instanzoptimale Mittelwerte) in kontaminierten und schwerfälligen Settings signifikant.
• Parameter-Sensitivität: Die Methode zeigt eine geringe Sensitivität gegenüber der initialen Mittelwert-Vermutung, dem Anfangsradius und der Gittergröße $\beta$. Der Parameter $\tau$ fungt als Robustheitskontrolle; kleinere Werte von $\tau$ (die weniger Daten einschließen) verbessern die Performance in kontaminierten Settings, können aber den Fehler in sauberen Settings leicht erhöhen.
• Iterationsanzahl: Der Fehler stabilisiert sich nach 3–4 Iterationen, was darauf hindeutet, dass $M=4$ für die meisten praktischen Anwendungen ausreichend ist.

Bedeutung und Ansprüche
Das Paper positioniert den Ballon-Mittelwert als praktische Lösung für das „Trilemma“ aus Robustheit, Privatsphäre und Recheneffizienz. Die Autoren behaupten, dass die Methode – obwohl sie möglicherweise nicht die theoretisch optimale Abhängigkeit von der Kontamination für adversarielle Settings erreicht (aufgrund struktureller Limitationen) – eine einzigartige Kombination bietet:

1. Rechentechnische Einfachheit: Sie ist in hohen Dimensionen ohne komplexe Optimierung implementierbar.
2. Starke Privatsphäre: Sie erfüllt zCDP, eine stärkere Privatsphäre-Notion als die oft in robusten Settings verwendete approximative DP.
3. Statistische Optimalität: Sie erreicht minimax-Raten im schwerfälligen Setting und bietet eine robuste Performance in kontaminierten Settings, in denen andere effiziente Methoden versagen.

Die Autoren kommen zu dem Schluss, dass der Ballon-Mittelwert ein lebensfähiges Werkzeug für die private Mittelwertschätzung in realen Szenarien ist, die hochdimensionale, potenziell schwerfällige und kontaminierte Daten beinhalten, und dabei ein Gleichgewicht zwischen theoretischen Garantien und praktischer Machbarkeit bietet.