Exactly Optimal and Communication-Efficient Private Estimation via Block Designs

Technische Zusammenfassung: Exakt optimale und kommunikationseffiziente private Schätzung mittels Blockdesigns

Problemformulierung
Die Arbeit befasst sich mit dem Problem der privaten diskreten Verteilungsschätzung im Rahmen der Local Differential Privacy (LDP). In diesem Szenario beobachten $n$ Clients Datenpunkte $X_i$, die aus einer unbekannten Verteilung $P$ über einen Bereich der Größe $v$ gezogen wurden. Jeder Client wendet einen Privatsphäre-Mechanismus $Q$ an, um einen privatisierten Output $Y_i$ zu erzeugen, der $\epsilon$-LDP erfüllt, bevor er diesen an einen zentralen Server sendet. Der Server konstruiert dann einen Schätzer $\hat{P}_n$, um $P$ zu rekonstruieren. Das Ziel ist es, das Worst-Case-Risiko (Schätzfehler) unter einer spezifischen Verlustfunktion (primär $\ell_u^u$ für $1 \le u \le 2$) zu minimieren und gleichzeitig die Kommunikationskosten, definiert durch die Größe des Output-Alphabets $b = |\mathcal{Y}|$, zu minimieren.

Obwohl das Subset Selection (SS) Schema bekannt dafür ist, den exakt optimalen Privacy-Utility-Trade-off für alle $(v, \epsilon)$ zu erreichen, leidet es unter prohibitiv hohen Kommunikationskosten (exponentiell in $v$). Umgekehrt erreichen kommunikationseffiziente Schemata wie die Hadamard Response (HR) und die Projective Geometry Response (PGR) oft nur ordnungsgemäß optimale oder nahezu optimale Leistungen, wobei die Leistungslücken in mittleren Privatsphäre-Regimen signifikant werden. Die vorliegende Arbeit versucht, diese Lücke zu schließen, indem sie Schemata findet, die sowohl exakt optimal (oder nahezu optimal) als auch kommunikationseffizient sind.

Methodik
Die Autoren schlagen eine neue Klasse von LDP-Schemata vor, die auf kombinatorischen Blockdesigns und einer breiteren Klasse namens Regular and Pairwise-Balanced Designs (RPBD) basieren.

1. Blockdesign-Schemata:

   • Der Mechanismus wird mithilfe einer Inzidenzstruktur $(X, Y, I)$ konstruiert, wobei $X$ der Input-Bereich und $Y$ der Output-Bereich ist.
   • Die Struktur ist definiert durch die Parameter $(v, b, r, k, \lambda)$, welche die Eingangsgröße, die Ausgangsgröße, Regularität, Uniformität und paarweise Balance repräsentieren.
   • Der Mechanismus gibt ein Element $y \in I_x$ mit einer Wahrscheinlichkeit proportional zu $e^\epsilon$ aus und andernfalls ein Element aus $Y \setminus I_x$.
   • Ein kanonischer unverzerrter Schätzer wird basierend auf den Zählungen von Outputs abgeleitet, die in spezifische Mengen fallen.
   • Zentrale Erkenntnis: Die Autoren stellen fest, dass das Risiko eines Blockdesign-Schemas für eine feste Eingangsgröße $v$ und ein Privacy-Budget $\epsilon$ nur vom Parameter $k$ (der Größe der Schnittmenge zwischen Input- und Output-Mengen) abhängt, nicht aber von $b$, $r$ oder $\lambda$. Konkret sind zwei Blockdesign-Schemata mit demselben $k$ „marginal äquivalent“ und liefern für dekomponierbare Verlustfunktionen identische Risiken.

2. Optimalitätsbedingungen:

   • Unter Ausnutzung der bekannten exakten Optimalität des SS-Schemas beweist die Arbeit, dass jedes Blockdesign-Schema mit einem Parameter $k \in K^*_{v,\epsilon}$ (der Menge der ganzen Zahlen, die die Risikofunktion minimieren) ebenfalls exakt optimal ist.
   • Die Autoren charakterisieren $K^*_{v,\epsilon}$ präzise und zeigen, dass ein Schema exakt optimal ist, wenn $k$ spezifische Schranken in Bezug auf $\epsilon$ und $v$ erfüllt.

3. Kommunikationseffizienz:

   • Fishers Ungleichung schreibt vor, dass für jedes unverzerrte oder konsistente Schema $b \ge v$ gelten muss.
   • Die Autoren konzentrieren sich auf symmetrische Blockdesigns, bei denen $b = v$ gilt, wodurch sie die theoretisch minimale Kommunikationskosten für unverzerrte Schemata erreichen.
   • Wenn für ein gegebenes $(v, \epsilon)$ kein symmetrisches Blockdesign mit dem optimalen $k$ existiert, nutzt die Arbeit abgeleitete (derived) und residuelle (residual) Blockdesigns, um nicht-symmetrische Schemata zu konstruieren, die dennoch exakt optimal oder nahezu optimal mit niedrigem $b$ bleiben.

4. RPBD-Schemata:

   • Um die „dünne Existenz“ (sparse existence) von Blockdesigns für beliebige Parameter zu adressieren, lockern die Autoren die Uniformitätsbedingung und schlagen Regular and Pairwise-Balanced Designs (RPBD) vor.
   • RPBD-Schemata verzichten auf die Anforderung, dass $|I_y| = k$ für alle $y$ gelten muss, behalten aber die Regularität ($r$) und die paarweise Balance ($\lambda$) bei.
   • Die Autoren zeigen, dass RPBD-Schemata mit einem Verhältnis $[b:r:\lambda]$, das dem des optimalen SS-Schemas ähnelt, nahezu optimale Risiken erzielen. Diese können durch das Abschneiden (Truncation) bestehender symmetrischer Blockdesigns konstruiert werden.

Wichtigste Ergebnisse

• Exakte Optimalität bei geringen Kosten: Die Arbeit identifiziert zahlreiche neue LDP-Schemata, die den exakt optimalen Privacy-Utility-Trade-off (entsprechend der Untergrenze $M_{v,u,\epsilon}$) mit den minimal möglichen Kommunikationskosten ($b=v$) für eine breitere Palette von $(v, \epsilon)$-Paaren erreichen als bisher bekannt.
• Vereinheitlichung: Das Framework vereinheitlicht bestehende Schemata (Randomized Response, Subset Selection, Hadamard Response, Projective Geometry Response) unter dem gemeinsamen Dach der Blockdesigns.
• Nahezu-Optimalität durch Truncation: Für Fälle, in denen exakt optimale Blockdesigns nicht existieren, zeigt die Arbeit, dass das Abschneiden von symmetrischen Blockdesigns zur Bildung von RPBD-Schemata nahezu optimale Leistungen mit deutlich geringeren Kommunikationskosten als bisherige State-of-the-Art-Methoden (z. B. PGR) liefert.
  • Beispiel: Für $v=100, \epsilon=1$ erzielt ein trunkiertes RPBD-Schema basierend auf einem Quartic Residue Difference Set einen geringeren Schätzfehler und erfordert ca. 6,66 Bits pro Client, verglichen mit ca. 8,41 Bits für ein trunkiertes PGR-Schema.
• Verbindung zur Hadamard-Vermutung: Die Arbeit verknüpft die Existenz exakt optimaler Schemata mit minimalen Kommunikationskosten im High-Privacy-Regime ($\epsilon \approx 0$) mit der Hadamard-Vermutung. Wenn die Vermutung gilt, existieren exakt optimale Schemata mit $b=v$ (oder $b=2v$) für alle $v$.

Bedeutung
Die Arbeit behauptet, einen neuartigen, vereinheitlichten Rahmen zur Entdeckung von LDP-Schemata bereitzustellen, die den traditionellen Trade-off zwischen exakter Optimalität und Kommunikationseffizienz überwinden. Durch die Verlagerung des Fokus von spezifischen Ad-hoc-Konstruktionen auf die kombinatorischen Eigenschaften von Blockdesigns demonstrieren die Autoren, dass:

1. Viele zuvor vorgeschlagene Schemata (HR, PGR) tatsächlich für spezifische Regime exakt optimal sind, eine Tatsache, die zuvor nicht etabliert war.
2. Neue Schemata systematisch generiert werden können, um exakte Optimalität mit minimalen Kommunikationskosten zu erreichen.
3. Die Lockerung hin zu RPBD-Schemata eine nahezu optimale Leistung mit geringen Kommunikationskosten in Szenarien ermöglicht, in denen die Konstruktion exakt optimaler Blockdesigns mathematisch unmöglich ist.

Die Arbeit betont, dass die Analyse des exakten Privacy-Utility-Trade-offs (einschließlich konstanter Faktoren) für den praktischen Einsatz entscheidend ist, und bietet mit dem Blockdesign-Ansatz einen rigorosen Weg dorthin, ohne die Kommunikationseffizienz zu opfern.