Technische Zusammenfassung: Optimale Raten für differenziell private Hypothesentests mit E-Werten

Problemstellung

Diese Arbeit adressiert das fundamentale Problem des einfachen Hypothesentests unter den Einschränkungen der zentralen Differential Privacy (DP). Konkret untersuchen die Autoren den Test eines Datensatzes $X \sim P^n$ (Nullhypothese) gegen $X \sim Q^n$ (Alternativhypothese) unter Verwendung von E-Werten.

Im klassischen Setting wird die Leistung eines Tests durch seine Power (True-Positive-Rate) gemessen. Im E-Wert-Rahmen wird die Leistung durch E-Power gemessen, definiert als $\mathbb{E}_Q[\log E]$, wobei $E$ eine nicht-negative Zufallsvariable ist, die $\mathbb{E}_P[E] \le 1$ erfüllt. Die zentrale Frage lautet: Was ist die maximal erreichbare E-Power für einen $\varepsilon$-DP-E-Wert beim Testen von $P$ gegen $Q$?

Die Autoren betrachten zwei Settings:

1. Batch-Setting: Alle $n$ Datenpunkte sind gleichzeitig verfügbar.
2. Sequentielles Setting: Daten kommen einzeln an, und der Analyst wählt eine Stoppzeit $N$ adaptiv. Das Ziel ist es, die erwartete Stoppzeit $\mathbb{E}_Q[N]$ zu minimieren, die erforderlich ist, um ein bestimmtes Niveau an statistischer Evidenz zu erreichen.

Während es Vorarbeiten zu differenziell privaten Hypothesentests im entscheidungstheoretischen Setting (binäre Ausgaben) und zu E-Werten unter lokaler DP gibt, konzentriert sich diese Arbeit auf zentrale DP-E-Werte, ein Setting, für das nur begrenzte Vorarbeiten existieren (insbesondere Csillag und Mesquita [10], die auf beschränkte Likelihood-Verhältnisse beschränkt waren).

Methodik

1. Charakterisierung der optimalen E-Power (Batch-Setting)

Die Autoren entkoppeln den Privacy-Mechanismus von der Konstruktion der E-Variable. Sie stellen fest, dass für jeden festen $\varepsilon$-DP-Mechanismus $M$ die optimale Nachverarbeitung zur Erzeugung einer E-Variable das Likelihood-Verhältnis der Ausgabeverteilungen, $dM(Q^n)/dM(P^n)$, ist. Somit reduziert sich das Problem auf die Maximierung der Kullback-Leibler-Divergenz (KL) zwischen den Ausgabeverteilungen des Mechanismus:
$$R_{\varepsilon}(Q \| P) = \lim_{n \to \infty} \sup_{M \in \varepsilon\text{-DP}} \frac{1}{n} KL(M(Q^n) \| M(P^n))$$

Um dies zu lösen, führen die Autoren eine intermediäre Verteilung $\tilde{Q}$ ein. Sie konstruieren $\tilde{Q}$, indem sie die Dichte von $Q$ relativ zu $P$ in spezifischen Regionen modifizieren, die durch das Likelihood-Verhältnis $q(x)/p(x)$ definiert sind:

• Region A (Niedriges Likelihood-Verhältnis): $q(x) < c_1 p(x)$. Hier gilt $\tilde{q}(x) = c_1 p(x)$.
• Region B (Hohes Likelihood-Verhältnis): $q(x) > c_2 p(x)$. Hier gilt $\tilde{q}(x) = c_2 p(x)$.
• Region M (Intermediär): $\tilde{q}(x) = q(x)$.

Die Konstanten $c_1, c_2$ und die Regionen werden durch einen Lagrange-Multiplikator $\lambda^*$ bestimmt, der eine implizite Gleichung löst, die sicherstellt, dass $\tilde{Q}$ eine gültige Wahrscheinlichkeitsverteilung ist. Diese Konstruktion minimiert das Funktional $KL(Q' \| P) + \varepsilon \cdot TV(Q', Q)$.

Die Autoren beweisen, dass die optimale Rate exakt lautet:
$$R_{\varepsilon}(Q \| P) = KL(\tilde{Q} \| P) + \varepsilon \cdot TV(\tilde{Q}, Q)$$

Anschließend konstruieren sie eine nicht-private E-Variable $E^*$ basierend auf diesem $\tilde{Q}$ (speziell ein geklippes Likelihood-Verhältnis), die eine beschränkte Log-Sensitivität $\varepsilon$ aufweist. Um dies zu privatisieren, schlagen sie eine Merging-Funktion $\Lambda_n$ vor, die auf der Arbeit von Vovk und Wang basiert, und fügen Laplace-Rauschen mit einem sorgfältig kalibrierten Kompensator hinzu, um die E-Variable-Eigenschaft zu erhalten und gleichzeitig die asymptotische Optimalität zu bewahren.

2. Sequentielles Setting und Stoppzeiten

Im sequentiellen Setting definieren die Autoren einen $\varepsilon$-DP-E-Prozess als eine Sequenz von E-Werten, die von einem $\varepsilon$-DP-Mechanismus generiert werden. Sie leiten eine untere Schranke für die erwartete Stoppzeit für einen solchen Prozess her.

Mittels eines Potentialfunktionsarguments, das eine Kopplung zwischen der wahren Verteilung $Q$ und der intermediären Verteilung $\tilde{Q}$ beinhaltet, beweisen sie, dass für jede Stoppzeit $N$:
$$\mathbb{E}_Q[\log E_N] \le \mathbb{E}_Q[N] \cdot R_{\varepsilon}(Q \| P)$$
Dies impliziert eine untere Schranke für die Sample-Komplexität, die erforderlich ist, um eine bestimmte Power zu erreichen.

Um diese Schranke zu erreichen, schlagen sie Algorithmus 1 vor, eine „Batch-zu-E-Prozess-Konvertierung". Dieser Algorithmus:

• Nimmt eine nicht-private E-Variable mit beschränkter Log-Sensitivität entgegen.
• Verarbeitet Daten in Batches zunehmender Größe.
• Wendet am Ende jeder Batch eine privatisierte Merging-Funktion (ähnlich wie im Batch-Fall) an.
• Verwendet eine spezifische Rekursionsbeziehung, um die Batch-Größen zu bestimmen und den Trade-off zwischen der anfänglichen „Startzeit" und dem langfristigen Wettbewerbsverhältnis zu optimieren.

Wichtige Beiträge und Ergebnisse

1. Ergebnis zur instanzspezifischen Härte (Satz 2.2): Die Arbeit liefert eine explizite, berechenbare Formel für die maximal erreichbare E-Power unter $\varepsilon$-DP. Diese Rate wird durch die KL-Divergenz zu einer intermediären Verteilung $\tilde{Q}$ plus einer Total-Variation-Strafe charakterisiert.
2. Konstruktion eines optimalen Algorithmus (Satz 2.4): Die Autoren konstruieren einen $\varepsilon$-DP-E-Wert, der diese optimale Rate asymptotisch erreicht. Die Konstruktion beinhaltet ein spezifisches Clipping des Likelihood-Verhältnisses, gefolgt von einem Privatisierungsschema unter Verwendung von Laplace-Rauschen und einem Kompensatorterm.
3. Sequentielle untere Schranke (Satz 3.1): Sie leiten eine universelle untere Schranke für die erwartete Stoppzeit eines beliebigen $\varepsilon$-DP-E-Prozesses her und zeigen, dass diese umgekehrt proportional zur optimalen E-Power-Rate $R_{\varepsilon}(Q \| P)$ ist.
4. Optimaler sequentieller Algorithmus (Satz 3.2): Sie präsentieren Algorithmus 1, der eine nicht-private E-Variable in einen $\varepsilon$-DP-E-Prozess umwandelt. Dieser Algorithmus entspricht der theoretischen unteren Schranke für Stoppzeiten bis auf einen konstanten multiplikativen Faktor (Wettbewerbsverhältnis) für alle hinreichend großen Stoppzeiten.
5. Verteilungsunabhängige Alternative (Anhang C): Unter der Erkenntnis, dass die Berechnung des optimalen $\tilde{Q}$ für komplexe Verteilungen unlösbar sein kann, schlagen sie eine Statistik „abgeschnittenes und skaliertes Likelihood-Verhältnis" (tsLR) vor. Diese verteilungsunabhängige Statistik erreicht eine Rate innerhalb eines konstanten Faktors der optimalen Rate.

Experimentelle Validierung

Die Autoren führten numerische Experimente durch, bei denen ihr Algorithmus 1 mit DP-SPRT (Differenziell Privater Sequential Probability Ratio Test) von Michel et al. [25] verglichen wurde.

• Aufbau: Test von $P = \text{Bernoulli}(0.3)$ gegen $Q = \text{Bernoulli}(q)$.
• Metrik: Empirische Kumulative Verteilungsfunktionen (CDFs) von Stoppzeiten.
• Ergebnis: Über verschiedene Privatsphärenlevel ($\varepsilon$) und Alternativverteilungen ($q$) hinweg stoppte der vorgeschlagene private E-Prozess konsistent früher als DP-SPRT. Bemerkenswerterweise wurde dieser Leistungsgewinn erzielt, obwohl der vorgeschlagene Algorithmus keine parametrischen Annahmen über die Daten trifft, wohingegen DP-SPRT speziell für exponentielle Familien entwickelt wurde.

Bedeutung und Behauptungen

Die Arbeit behauptet, ein vollständiges Verständnis der fundamentalen Grenzen des einfachen Hypothesentests mit E-Werten unter zentraler Differential Privacy zu liefern.

• Theoretische Grundlage: Durch die Charakterisierung der optimalen Rate $R_{\varepsilon}(Q \| P)$ und die Bereitstellung eines Algorithmus, der diese Rate erreicht, etabliert die Arbeit eine Basislinie für das, was in der privatsphärewahrenden sequentiellen Analyse erreichbar ist.
• Praktischer Nutzen: Die vorgeschlagenen Algorithmen benötigen weniger Daten (weniger Stoppzeiten) als bestehende State-of-the-Art-Methoden (DP-SPRT) über einen Bereich von Settings hinweg.
• Zukünftige Richtungen: Die Autoren schlagen vor, dass ihre Härteergebnisse und Techniken (insbesondere die Verwendung von am wenigsten günstigen Paaren) als Grundlage dienen können, um diese Ergebnisse auf zusammengesetzte Hypothesentests und instanzoptimale DP-Schätzung zu erweitern, ähnlich wie grundlegende Arbeiten in nicht-privaten Settings Fortschritte in diesen Bereichen vorangetrieben haben. Sie stellen zudem fest, dass die Erweiterung dieser Ergebnisse auf approximative DP ($\delta > 0$) eine offene Frage bleibt.