A Sieve-Accelerated Quadrature Method for Exact Privacy Accounting in the 2020 U.S. Decennial Census

Technische Zusammenfassung: Eine Sieb-beschleunigte Quadraturmethode für die exakte Privacy-Abrechnung im US-Volkszählungsprogramm 2020

Problemstellung
Das U.S. Census Bureau hat für die Volkszählung 2020 (Decennial Census) Differential Privacy (DP) durch das Injizieren von ganzzahligen, diskreten Gaußschen Rauschwerten in die Volkszählungsdaten eingeführt. Während das Bureau derzeit formale Privatsitätsgarantien mittels Zero-Concentrated Differential Privacy (zCDP) bereitstellt, handelt es sich bei diesen Garantien lediglich um obere Schranken auf den exakten Privatsheitsverlust. Diese Lücke erzwingt die Injektion von unnötigem überschüssigem Rauschen, um die Privatsheitsbudgets zu erfüllen, was den statistischen Nutzen der Daten für kritische nachgelagerte Anwendungen wie die Zuweisung von Bundesmitteln oder die politische Wahlbezirksziehung (Redistricting) verschlechtert.

Die zentrale Herausforderung besteht in der Evaluierung des exakten Privatschaftsprofils der Datei „Demographic and Housing Characteristics“ (DHC) der Volkszählung 2020. Mathematisch erfordert dies die Berechnung der Endwahrscheinlichkeiten (Tail Probabilities) hochdimensionaler Faltungen heterogener diskreter Gaußscher Verteilungen unter dem $f$-Differential-Privacy ($f$-DP)-Rahmen. Diese Aufgabe ist aufgrund von drei Faktoren rechnerisch prohibitiv:

1. Heterogenität: Die Rauschvarianzen unterscheiden sich über Abfragen und geografische Ebenen hinweg, was die algebraischen Strukturen zerstört, die geschlossene Lösungen ermöglichen würden.
2. Dimensionalität: Die Komposition umfasst bis zu 80-fache Kompositionen entlang geografischer Pfade, was hochdimensionale Integrale erzeugt.
3. Präzisionsanforderungen: Das Census Bureau schreibt extrem strenge numerische Fehlertoleranzen vor (z. B. $10^{-35}$), um die Genauigkeit der resultierenden $(\varepsilon, \delta)$-DP-Kurven zu gewährleisten. Vorherige Methoden benötigten etwa 1.000 CPU-Stunden, um eine einzige Privatsheitsbudget-Allokation auszuwerten, was eine Vollskala-Abrechnung der 946 distinkten Allokationspaare der DHC-Datei rechnerisch unmöglich machte.

Methodik
Die Autoren schlagen eine recheneffiziente, mathematisch rigorose Quadraturmethode vor, die das Problem der exakten Privatschaftsabrechnung als numerisches Integrationsproblem umformuliert. Die Methode verläuft in vier Hauptschritten:

1. Problemumformulierung via Diskreter Fourier-Transformation (DFT):
   Das Problem der Berechnung der Endwahrscheinlichkeit einer gewichteten Summe unabhängiger diskreter Gaußscher Zufallsvariablen wird in ein numerisches Integrationsproblem transformiert. Durch Nutzung der inversen diskreten Fourier-Transformation wird die kumulative Wahrscheinlichkeit als Integral des Produkts von Charakteristischen Funktionen über das Intervall $[-\pi, \pi]$ ausgedrückt.

2. Exponentiell konvergente Quadratur:
   Die Autoren verwenden die Trapezregel zur Approximation des Integrals. Sie stellen fest, dass die Trapezregel für komplex-analytische, periodische Integranden (speziell die charakteristischen Funktionen diskreter Gaußscher Verteilungen) eine exponentielle Konvergenz erreicht. Dies ermöglicht es, die erforderliche Präzision mit exponentiell weniger Quadraturknoten zu erreichen als Standardmethoden mit polynomialer Konvergenz.

3. Gitter-Mapping für heterogene Gewichte:
   Um die Heterogenität der Rauschparameter (bei denen die Gewichte rationale Zahlen sind) zu handhaben, leiten die Autoren einen einheitlichen Skalierungsfaktor unter Verwendung des Bézoutschen Identität ab. Dies bildet die heterogene gewichtete Summe auf ein gemeinsames ganzzahliges Gitter ab, wodurch die diskrete Wahrscheinlichkeitsmassefunktion erhalten bleibt, ohne auf verlustbehaftetes Binning zurückzugreifen. Dieser Schritt ermöglicht die Ableitung präziser Sub-Gauß-Konzentrationsungleichheiten, um die notwendigen Trunkierungsgrenzen für die unendlichen Summen zu bestimmen.

4. Sieb-beschleunigte Integration:
   Trotz der exponentiellen Konvergenz erfordern hochdimensionale Einstellungen mit strengen Toleranzen ($10^{-35}$) immer noch die Evaluierung von Millionen von Knoten. Um dies zu überwinden, führen die Autoren einen „Sieb-Algorithmus“ ein, der von der Zahlentheorie inspiriert ist. Dieser Algorithmus nutzt die periodische Peak-Struktur der charakteristischen Funktionen aus, um Quadraturknoten, bei denen der Integrand garantiert vernachligbar ist, rigoros zu identifizieren und zu eliminieren (Pruning). Durch das Verwerfen dieser Knoten reduziert die Methode die Anzahl der Funktionsauswertungen von über $10^6$ auf etwa 203.

Kernbeiträge

• Exakte Privatschaftsabrechnung: Die Arbeit präsentiert die erste exakte, annahmenfreie Privatschaftsabrechnung für die 2020 Census DHC-Datei, die über die Approximationen der zCDP-basierten oberen Schranken hinausgeht.
• Rechenbeschleunigung: Der vorgeschlagene Ansatz erreicht eine Beschleunigung von über drei Größenordnungen im Vergleich zu bisherigen State-of-the-Art-Methoden. Die Evaluierung einer einzelnen Privatsheitsbudget-Allokation sinkt von ca. 1.000 CPU-Stunden auf 0,5 CPU-Stunden.
• Skalierbarkeit: Die Methode berechnet erfolgreich die exakten Privatschaftsprofile für alle 946 Paare der Privatsheitsbudget-Allokationen in der DHC-Datei – eine Aufgabe, die zuvor als rechnerisch unpraktikabel galt.
• Theoretische Erkenntnis: Die Autoren liefern eine theoretische Erklärung für die Divergenz zwischen diskreten und kontinuierlichen Gaußschen Mechanismen mittels Edgeworth-Expansions und beweisen, dass der Approximationsfehler der Ordnung $O(m^{-3/2})$ ist, wobei $m$ die Anzahl der Kompositionen darstellt.

Ergebnisse

• Privatschaft-Nützlichkeits-Trade-off: Durch die Verwendung der exakten Abrechnung zeigen die Autoren, dass die Rauschvarianz um 15,08 % bis 24,82 % reduziert werden kann, während dieselben Privatsheitsgarantien wie der aktuelle zCDP-basierte Ansatz des Bureau beibehalten werden. Dies verbessert den statistischen Nutzen der veröffentlichten Daten signifikant.
• Leistung: Die Methode berechnet die exakten $f$-DP und $(\varepsilon, \delta)$-DP Kurven für die 2020 Census DHC-Datei. Die Ergebnisse zeigen, dass der aktuelle Ansatz des Bureau mit oberen Schranken konservativ ist und einen strikt schlechteren Privatschaft-Nützlichkeits-Trade-off liefert als die exakte Methode.
• Praktische Orientierung: Die Autoren beobachten, dass die Privatsheitsgarantien über verschiedene zusammengesetzte Mechanismen hinweg sehr ähnlich sind. Sie schlagen vor, einen einzelnen repräsentativen zusammengesetzten Mechanismus (speziell $[f_{M_0}, f_{M_0}]$) als Proxy während der Phase der Privatsheitsbudget-Optimierung zu verwenden, um wiederholte Vollskala-Berechnungen zu vermeiden, wobei eine abschließende exakte Evaluierung nach der Optimierung erfolgt.

Bedeutung
Die Arbeit behauptet, ein kritisches offenes Problem gelöst zu zu haben, das das Census Bureau hinsichtlich des suboptimalen Privatschaft-Nützlichkeits-Trade-offs durch lose Privatschaftsschranken gestellt hat. Durch die Ermöglichung einer exakten, annahmenfreien Abrechnung erlaubt die Methode politischen Entscheidungsträgern, die Privatschaftskosten als eine steuerbare Ressource zu behandeln und so das Gleichgewicht zwischen Datennutzen und Privatschaftsschutz zu optimieren. Das Framework ist nicht auf die Volkszählung beschränkt; es bietet einen allgemeinen, schnellen und numerisch zuverlässigen Ansatz für die exakte Privatschaftsabrechnung in Settings mit großen Kompositionen unter Beteiligung heterogener diskreter Mechanismen. Die Autoren betonen, dass ihr Ansatz das „unnötige überschüssige Rauschen“ vermeidet, welches derzeit die Qualität der Bundesdatenerzeugnisse für die Wahlbezirksziehung und die Wirtschaftsforschung mindert.