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

Resumen Técnico: Un método de cuadratura acelerado por cribado para la contabilidad exacta de la privacidad en el Censo de EE. UU. de 2020

Planteamiento del problema
La Oficina del Censo de EE. UU. adoptó la privacidad diferencial (DP) para el Censo Decenal de 2020 inyectando ruido gaussiano discreto con valores enteros en las tabulaciones del censo. Si bien la Oficina proporciona actualmente garantías formales de privacidad utilizando la privacidad diferencial de concentración cero (zCDP), estas garantías son límites superiores de la pérdida de privacidad exacta. Esta brecha obliga a la inyección de un exceso innecesario de ruido para satisfacer los presupuestos de privacidad, lo que degrada la utilidad estadística de los datos para aplicaciones críticas posteriores, como la asignación de fondos federales y la redistribución política.

El desafío central es evaluar el perfil de privacidad exacto del Archivo de Características Demográficas y de Vivienda (DHC) del Censo de 2020. Matemáticamente, esto requiere calcular las probabilidades de cola de convoluciones de alta dimensión de distribuciones gaussianas discretas heterogéneas bajo el marco de la privacidad $f$-diferencial ($f$-DP). Esta tarea es computacionalmente prohibitiva debido a tres factores:

1. Heterogeneidad: Las varianzas del ruido difieren entre consultas y niveles geográficos, lo que destruye las estructuras algebraicas que permiten soluciones de forma cerrada.
2. Dimensionalidad: La composición implica hasta 80 composiciones a lo largo de rutas geográficas, lo que crea integrales de alta dimensión.
3. Requisitos de precisión: La Oficina del Censo exige tolerancias de error numérico excepcionalmente estrictas (por ejemplo, $10^{-35}$) para asegurar la exactitud de las curvas $(\varepsilon, \delta)$-DP resultantes. Los métodos anteriores requerían aproximadamente 1,000 horas de CPU para evaluar una sola asignación de presupuesto de privacidad, lo que hace que la contabilidad a escala completa de los 946 pares distintos de asignación en el Archivo DHC sea computacionalmente inviable.

Metodología
Los autores proponen un método de cuadratura matemáticamente riguroso y computacionalmente eficiente que reformula el problema de la contabilidad exacta de la privacidad como una tarea de integración numérica. El método procede en cuatro etapas clave:

1. Reformulación del problema mediante la Transformada Discreta de Fourier (DFT):
   El problema de calcular la probabilidad de cola de una suma ponderada de variables aleatorias gaussianas discretas se transforma en un problema de integración numérica. Al utilizar la transformada inversa de Fourier discreta, la probabilidad acumulada se expresa como una integral del producto de las funciones características sobre el intervalo $[-\pi, \pi]$.

2. Cuadratura de convergencia exponencial:
   Los autores emplean la regla del trapecio para aproximar la integral. Establecen que, para integrandos complejos-analíticos y periódicos (específicamente las funciones características de las gaussianas discretas), la regla del trapecio logra una convergencia exponencial. Esto permite alcanzar la precisión requerida con significativamente menos nodos de cuadratura en comparación con los métodos de convergencia polinómica estándar.

3. Mapeo de red para pesos heterogéneos:
   Para manejar la heterogeneidad de los parámetros de ruido (donde los pesos son números racionales), los autores derivan un factor de escala unificado utilizando la identidad de Bézout. Esto mapea la suma ponderada heterogénea sobre una red entera común, preservando la función de masa de probabilidad discreta sin recurrir a un agrupamiento (binning) con pérdida de información. Este paso permite la derivación de desigualdades de concentración sub-gaussianas precisas para determinar los límites de truncamiento necesarios para las sumas infinitas.

4. Integración acelerada por cribado:
   A pesar de la convergencia exponencial, los entornos de alta dimensión con tolerancias estrictas ($10^{-35}$) aún requieren la evaluación de millones de nodos. Para superar esto, los autores introducen un "algoritmo de cribado" inspirado en la teoría de números. Este algoritmo explota la estructura de picos periódicos de las funciones características para identificar y descartar rigurosamente los nodos de cuadratura donde se garantiza que el integrando es insignificante. Al descartar estos nodos, el método reduce el número de evaluaciones de función de más de $10^6$ a aproximadamente 203.

Contribuciones clave

• Contabilidad de privacidad exacta: El artículo presenta la primera contabilidad de privacidad exacta y sin supuestos para el Archivo DHC del Censo de 2020, yendo más allá de las aproximaciones de límites superiores de la zCDP.
• Aceleración computacional: El método propuesto logra una aceleración de más de tres órdenes de magnitud en comparación con los métodos de vanguardia anteriores. La evaluación de una sola asignación de presupuesto de privacidad cae de ~1,000 horas de CPU a 0.5 horas de CPU.
• Escalabilidad: El método calcula con éxito los perfiles de privacidad exactos para los 946 pares de asignaciones de presupuesto de privacidad en el Archivo DHC, una tarea anteriormente considerada computacionalmente impracticable.
• Perspectiva teórica: Los autores proporcionan una explicación teórica de la divergencia entre los mecanismos gaussianos discretos y continuos utilizando expansiones de Edgeworth, demostando que el error de aproximación es de orden $O(m^{-3/2})$, donde $m$ es el número de composiciones.

Resultados

• Compromiso entre privacidad y utilidad: Al utilizar la contabilidad exacta, los autores demuestran que la varianza del ruido puede reducirse entre un 15.08% y un 24.82% manteniendo las mismas garantías de privacidad que el enfoque actual de la Oficina basado en zCDP. Esto mejora significativamente la utilidad estadística de los datos liberados.
• Desempeño: El método calcula las curvas exactas de $f$-DP y $(\varepsilon, \delta)$-DP para el Archivo DHC del Censo de 2020. Los resultados muestran que el enfoque actual de límites superiores de la Oficina es conservador, produciendo un compromiso entre privacidad y utilidad estrictamente peor que el método exacto.
• Guía práctica: Los autores observan que las garantías de privacidad a través de diferentes mecanismos compuestos son altamente similares. Proponen utilizar un único mecanismo compuesto representativo (específicamente $[f_{M_0}, f_{M_0}]$) como un sustituto (proxy) durante la fase de ajuste del presupuesto de privacidad para evitar cálculos completos repetidos, con una evaluación exacta final realizada post-ajuste.

Significancia
El artículo afirma resolver un problema crítico planteado por la Oficina del Censo relativo al compromiso subóptimo entre privacidad y utilidad causado por los límites de privacidad laxos. Al permitir una contabilidad exacta y sin supuestos, el método permite a los responsables de políticas tratar el costo de la privacidad como un recurso ajustable, optimizando el equilibrio entre la utilidad de los datos y la protección de la privacidad. El marco no se limita al Censo; ofrece un enfoque general, rápido y numéricamente confiable para la contabilidad de privacidad exacta en entornos de gran composición que involucran mecanismos discretos heterogéneos. Los autores enfatizan que su enfoque evita el "exceso de ruido innecesario" que actualmente degrada la calidad de los productos de datos federales utilizados para la redistribución de distritos y la investigación económica.