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

Technische Samenvatting: Een Sieve-geaccelereerde Quadratuurmethode voor Exacte Privacy-rekening in de 2020 Amerikaanse Volkstelling

Probleemstelling
De Amerikaanse Census Bureau heeft voor de 20 de Volksstelling van 2020 differential privacy (DP) toegepast door integer-waardige discrete Gaussische ruis in census-tabulaties te injecteren. Hoewel het Bureau momenteel formele privacygaranties biedt met behulp van zero-concentrated differential privacy (zCDP), zijn deze garanties bovengrenzen op de exacte privacyverlies. Deze kloof dwingt tot de injectie van onnodige overtollige ruis om privacybudgetten te voldoen, wat de statistische bruikbaarheid van de gegevens voor kritieke downstream-toepassingen zoals federale financieringsallocatie en politieke herindeling verslechtert.

De kernuitdaging bestaat uit het evalueren van het exacte privacyprofiel van het 2020 Census Demographic and Housing Characteristics (DHC) bestand. Wiskundig gezien vereist dit het berekenen van de staartkansen van hoogdimensionale convoluties van heterogene discrete Gaussische verdelingen onder het $f$-differential privacy ($f$-DP) kader. Deze taak is computationeel onhaalbaar door drie factoren:

1. Heterogeniteit: Ruisvarianties verschillen over queries en geografische niveaus, wat de algebraïsche structuren die closed-form oplossingen mogelijk maken, vernietigt.
2. Dimensionaliteit: De compositie omvat tot wel 80-voudige composities langs geografische paden, wat resulteert in hoogdimensionale integralen.
3. Precisievereisten: Het Census Bureau stelt uitzonderlijk strikte numerieke fouttoleranties voor (bijv. $10^{-35}$) om de nauwkeurigheid van de resulterende $(\varepsilon, \delta)$-DP-curven te waarborgen. Eerdere methoden vereisten ongeveer 1.000 CPU-uren om een enkele privacybudget-allocatie te evalueren, waardoor een volledige schaal rekening van de 946 afzonderlijke allocatieparen in het DHC-bestand computationeel onhaalbaar was.

Methodologie
De auteurs stellen een computationeel efficiënte, wiskundig rigoureuze quadratuurmethode voor die het exacte privacy-rekenprobleem herformuleert als een numeriek integratietaak. De methode verloopt via vier stappen:

1. Probleemherformulering via Discrete Fourier Transformatie (DFT):
   Het probleem van het berekenen van de staartkans van een gewogen som van onafhankelijke discrete Gaussische variabelen wordt getransformeerd naar een numeriek integratietaak. Door gebruik te maken van de inverse discrete Fourier-transformatie, wordt de cumulatieve waarschijnlijkheid uitgedrukt als een integraal van het product van karakteristieke functies over het interval $[-\pi, \pi]$.

2. Exponentieel Convergerende Quadratuur:
   De auteurs passen de trapeziumregel toe om de integraal te benaderen. Zij stellen vast dat de trapeziumregel voor complex-analytische, periodieke integranden (specifiek de karakteristieke functies van discrete Gaussische verdelingen) een exponentiële convergentie bereikt. Dit maakt het mogelijk om de vereiste precisie te bereiken met exponentieel minder kwadratuurknopen vergeleken met standaard polynomiale convergentiemethoden.

3. Lattice Mapping voor Heterogene Gewichten:
   Om de heterogeniteit van de ruisparameters (waarbij gewichten rationele getallen zijn) aan te pakken, leiden de auteurs een verenigde schalfactor af met behulp van Bézout's identiteit. Dit brengt de heterogene gewogen som in kaart op een gemeenschappelijk integer rooster (lattice), waarbij de discrete kansmassa-functie behouden blijft zonder terug te vallen op verlieslatende binning. Deze stap maakt de afleiding van precieze sub-Gaussische concentratie-ongelijkheden mogelijk om de noodzakelijke afkapgrenzen voor de oneindige sommen te bepalen.

4. Sieve-geaccelereerde Integratie:
   Ondanks exponentiële convergentie vereisen hoogdimensionale settings met strikte toleranties ($10^{-35}$) nog steeds de evaluatie van miljoenen knopen. Om dit te overwinnen, introduceren de auteurs een "sieve-algoritme" geïnspireerd door de gethentheorie. Dit algoritme maakt gebruik van de periodieke piekstructuur van de karakteristieke functies om rigoureus de kwadratuurknopen te identificeren en weg te snijden waar de integrand gegarandeerd verwaarloosbaar is. Door deze knopen te verwijderen, reduceert de methode het aantal functie-evaluaties van meer dan $10^6$ naar ongeveer 203.

Kernbijdragen

• Exacte Privacy-rekening: Het artikel presenteert de eerste exacte, aannamevrije privacy-rekening voor het 2020 Census DHC-bestand, bewegend voorbij de upper-bound benaderingen van zCDP.
• Computationele Versnelling: De voorgestelde methode bereikt een versnelling van meer dan drie ordes van grootte vergeleken met eerdere state-of-the-art methoden. De evaluatie van een enkele privacybudget-allocatie daalt van ~1.000 CPU-uren naar 0,5 CPU-uur.
• Schaalbaarheid: De methode slaagt erin de exacte privacyprofielen voor alle 946 paren van privacybudget-allocaties in het DHC-bestand te berekenen, een taak die voorheen als computationeel onpraktisch werd beschouwd.
• Theoretisch Inzicht: De auteurs bieden een theoretische verklaring voor de divergentie tussen discrete en continue Gaussische mechanismen met behulp van Edgeworth-expansies, waarbij zij bewijzen dat de benaderingsfout van de orde $O(m^{-3/2})$ is, waarbij $m$ het aantal composities is.

Resultaten

• Privacy-Utility Afruil: Door exact accounting te gebruiken, demonstreren de auteurs dat de ruisvariantie met 15,08% tot 24,82% kan worden verminderd terwijl dezelfde privacygaranties behouden blijven als de huidige zCDP-gebaseerde aanpak van het Bureau. Dit verbetert de statistische bruikbaarheid van de vrijgegeven gegevens aanzienlijk.
• Prestaties: De methode berekent de exacte $f$-DP en $(\varepsilon, \delta)$-DP curven voor het 2020 Census DHC-bestand. De resultaten tonen aan dat de huidige upper-bound aanpak van het Bureau conservatief is, wat resulteert in een strikt slechtere privacy-utility afruil dan de exacte methode.
• Praktische Richtlijnen: De auteurs observeren dat privacygaranties over verschillende gecomponeerde mechanismen zeer vergelijkbaar zijn. Zij stellen voor om een enkel representatief gecomponeerd mechanisme (specifiek $[f_{M_0}, f_{M_0}]$) te gebruiken als proxy tijdens de fase van het afstemmen van het privacybudget, om de volledige schaal berekeningen te vermijden, met een uiteindelijke exacte evaluatie na de afstemming.

Betekenis
Het artikel beweert een cruciaal openstaand probleem op te lossen dat door het Census Bureau is geponeerd betreffende de suboptimale privacy-utility afruil veroorzaakt door losse privacy-bounds. Door exacte, aannamevrije rekening mogelijk te maken, stelt de methode beleidsmakers in staat om de privacykosten te behandelen als een regelbare hulpbron, waarbij de balans tussen databruikbaarheid en privacybescherming wordt geoptimaliseerd. Het kader is niet beperkt tot de Census; het biedt een algemene, snelle en numeriek betrouwbare aanpak voor exacte privacy-rekening in settings met grote composities betrokken bij heterogene discrete mechanismen. De auteurs benadrukken dat hun aanpak de "onnodige overtollige ruis" vermijdt die momenteel de kwaliteit van federale dataproducten gebruikt voor herindeling en economisch onderzoek verslechtert.