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

Sintesi Tecnica: Un Metodo di Quadratura Accelerato da Setaccio per il Calcolo Esatto della Privacy nel Censimento Decennale degli Stati Uniti del 2020

Definizione del Problema
L'U.S. Census Bureau ha adottato la privacy differenziale (DP) per il Censimento Decennale del 2020 iniettando rumore gaussiano discreto a valori interi nelle tabulazioni del censimento. Sebbene il Bureau fornisca attualmente garanzie formali di privacy utilizzando la zero-concentrated differential privacy (zCDP), tali garanzie sono limiti superiori del lussamento esatto della privacy. Questo divario impone l'iniezione di un eccesso di rumore non necessario per soddisfare i budget di privacy, degradando l'utilità statistica dei dati per applicazioni a valle critiche come l'allocazione dei finanziamenti federali e la redistricting politica.

La sfida principale consiste nel valutare il profilo di privacy esatto del File delle Caratteristiche Demografiche e Abitative (DHC) del Censimento del 2020. Matematicamente, ciò richiede il calcolo delle probabilità di coda di alte convoluzioni eterogenee di distribuzioni gaussiane discrete sotto il framework della $f$-differential privacy ($f$-DP). Questo compito è computazionalmente proibitivo a causa di tre fattori:

1. Eterogeneità: Le varianze del rumore differiscono tra le query e i livelli geografici, distruggendo le strutture algebriche che consentono soluzioni in forma chiusa.
2. Dimensionalità: La composizione comporta fino a 80 composizioni lungo i percorsi geografici, creando integrali ad alta dimensionalità.
3. Requisiti di Precisione: Il Census Bureau impone tolleranze di errore numerico eccezionalmente rigorose (ad esempio, $10^{-35}$) per garantire l'accuratezza delle curve $(\varepsilon, \delta)$-DP risultanti. I metodi precedenti richiedevano circa 1.000 ore di CPU per valutare una singola allocazione del budget di privacy, rendendo computazionalmente impraticabile la valutazione completa dei 946 distinti accoppiamenti di allocazione nel File DHC.

Metodologia
Gli autori propongono un metodo di quadratura computazionalmente efficiente e matematicamente rigoroso che riformula il problema del calcolo esatto della privacy come un compito di integrazione numerica. Il metodo procede in quattro fasi chiave:

1. Riformulazione del Problema tramite Trasformata Discreta di Fourier (DFT):
   Il problema del calcolo della probabilità di coda di una somma pesata di variabili casuali gaussiane discrete indipendenti viene trasformato in un problema di integrazione numerica. Utilizzando la trasformata discreta di Fourier inversa, la probabilità cumulativa viene espressa come un integrale del prodotto delle funzioni caratteristiche sull'intervallo $[-\pi, \pi]$.

2. Quadratura a Convergenza Esponenziale:
   Gli autori impiegano la regola del trapezio per approssimare l'integrale. Essi stabiliscono che, per integrandi complessi-analitici e periodici (specificamente le funzioni caratteristiche delle gaussiane discrete), la regola del trapezio raggiunge una convergenza esponenziale. Ciò consente di soddisfare la precisione richiesta con un numero di nodi di quadratura esponenzialmente inferiore rispetto ai metodi standard a convergenza polinomiale.

3. Mappatura su Reticolo per Pesi Eterogenei:
   Per gestire l'eterogeneità dei parametri del rumore (dove i pesi sono numeri razionali), gli autori derivano un fattore di scala unificato utilizzando l'identità di Bézout. Questo mappa la somma pesata eterogenea su un reticolo intero comune, preservando la funzione di massa di probabilità discreta senza ricorrere a un raggruppamento (binning) con perdita di informazioni. Questo passaggio consente la derivazione di precise disuguaglianze di concentrazione sub-gaussiane per determinare i limiti di troncamento necessari per le somme infinite.

4. Integrazione Accelerata da Setaccio:
   Nonostante la convergenza esponenziale, gli scenari ad alta dimensionalità con tolleranze rigorose ($10^{-35}$) richiedono ancora la valutazione di milioni di nodi. Per superare questo ostacolo, gli autori introducono un "algoritmo a setaccio" ispirato alla teoria dei numeri. Questo algoritmo sfrutta la struttura di picco periodico delle funzioni caratteristiche per identificare e scartare rigorosamente i nodi di quadratura dove l'integrando è garantito essere trascurabile. Scartando questi nodi, il metodo riduce il numero di valutazioni della funzione da oltre $10^6$ a circa 203.

Contributi Chiave

• Calcolo Esatto della Privacy: Il documento presenta il primo calcolo della privacy esatto e privo di assunzioni per il File DHC del Censimento del 2020, andando oltre le approssimazioni di limite superiore della zCDP.
• Accelerazione Computazionale: Il metodo proposto ottiene un'accelerazione di oltre tre ordini di grandezza rispetto ai metodi allo stato dell'arte precedenti. La valutazione di una singola allocazione del budget di privacy scende da circa 1.000 ore di CPU a 0,5 ore di CPU.
• Scalabilità: Il metodo calcola con successo i profili di privacy esatti per tutti i 946 accoppiamenti di allocazione del budget di privacy nel File DHC, un compito precedentemente ritenuto computazionalmente impraticabile.
• Approfondimento Teorico: Gli autori forniscono una spiegazione teorica della divergenza tra i meccanismi gaussiani discreti e continui utilizzando le espansioni di Edgeworth, dimostrando che l'errore di approssimazione è di ordine $O(m^{-3/2})$, dove $m$ è il numero di composizioni.

Risultati

• Trade-off Privacy-Utilità: Utilizzando il calcolo esatto, gli autori dimostrano che la varianza del rumore può essere ridotta del 15,08% - 24,82% mantenendo le stesse garanzie di privacy del attuale approccio del Bureau basato sulla zCDP. Ciò migliora significativamente l'utilità statistica dei dati rilasciati.
• Prestazioni: Il metodo calcola le curve esatte $f$-DP e $(\varepsilon, \delta)$-DP per il File DHC del Censimento del 2020. I risultati mostrano che l'attuale approccio basato su limiti superiori del Bureau è conservativo, fornendo un trade-off privacy-utilità strettamente peggiore rispetto al metodo esatto.
• Guida Pratica: Gli autori osservano che le garanzie di privacy attraverso diversi meccanismi composti sono altamente simili. Propongono di utilizzare un singolo meccanismo composto rappresentativo (specificamente $[f_{M_0}, f_{M_0}]$) come proxy durante la fase di sintonizzazione del budget di privacy, con una valutazione esatta finale eseguita post-sintonizzazione.

Significatività
Il documento sostiene di aver risolto un problema critico posto dal Census Bureau riguardante il trade-off subottimale tra privacy e utilità causato dai limiti di privacy troppo ampi. Consentendo un calcolo esatto e privo di assunzioni, il metodo permette ai decisori politici di trattare il costo della privacy come una risorsa sintonizzabile, ottimizzando l'equilibrio tra l'utilità dei dati e la protezione della privacy. Il framework non è limitato al Censimento; offre un approccio generale, veloce e numericamente affidabile per il calcolo esatto della privacy in contesti di grande composizione che coinvolgono meccanismi discreti eterogenei. Gli autori sottolineano che il loro approccio evita il "rumore eccessivo non necessario" che attualmente degrada la qualità dei prodotti dati federali utilizzati per la redistricting e la ricerca economica.