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

Resumo Técnico: Um Método de Quadratura Acelerado por Crivo para Contabilidade Exata de Privacidade no Censo dos EUA de 2020

Definição do Problema
O U.S. Census Bureau adotou a privacidade diferencial (DP) para o Censo Decenal de 2020 injetando ruído gaussiano discreto de valor inteiro nas tabulações do censo. Embora o Bureau forneça atualmente garantias formais de privacidade usando a privacidade diferencial de concentração zero (zCDP), essas garantias são limites superiores para a perda de privacidade exata. Essa lacuna força a injeção de ruído excessivo desnecessário para satisfazer os orçamentos de privacidade, degradando a utilidade estatística dos dados para aplicações críticas subsequentes, como a alocação de fundos federais e o redesenho de distritos políticos.

O desafio central é avaliar o perfil de privacidade exato do Arquivo de Características Demográficas e de Habitação (DHC) do Censo de 2020. Matematicamente, isso requer o cálculo das probabilidades de cauda de convoluções de alta dimensão de distribuições gaussianas discretas heterogêneas sob o framework de $f$-privacidade diferencial ($f$-DP). Esta tarefa é computacionalmente proibitiva devido a três fatores:

1. Heterogeneidade: As variâncias do ruído diferem entre as consultas e os níveis geográficos, destruindo as estruturas algébricas que permitem soluções em forma fechada.
2. Dimensionalidade: A composição envolve até 80 composições ao longo de caminhos geográficos, criando integrais de alta dimensão.
3. Requisitos de Precisão: O Census Bureau exige tolerâncias de erro numérico excepcionalmente rigorosas (ex: $10^{-35}$) para garantir a precisão das curvas $(\varepsilon, \delta)$-DP resultantes. Métodos anteriores exigiam aproximadamente 1.000 horas de CPU para avaliar uma única alocação de orçamento de privacidade, tornando o cálculo em escala total dos 946 pares distintos de alocação no Arquivo DHC computacionalmente inviável.

Metodologia
Os autores propõem um método de quadratura matematicamente rigoroso e computacionalmente eficiente que reformula o problema de contabilidade de privacidade exata como uma tarefa de integração numérica. O método procede em quatro etapas principais:

1. Reformulação do Problema via Transformada Discreta de Fourier (DFT):
   O problema de calcular a probabilidade de cauda de uma soma ponderada de variáveis aleatórias gaussianas discretas independentes é transformado em um problema de integração numérica. Ao utilizar a transformada discreta de Fourier inversa, a probabilidade cumulativa é expressa como uma integral do produto das funções características sobre o intervalo $[-\pi, \pi]$.

2. Quadratura de Convergência Exponencial:
   Os autores empregam a regra do trapézio para aproximar a integral. Eles estabelecem que, para integrandos complexo-analíticos e periódicos (especificamente as funções características de gaussianas discretas), a regra do trapézio alcança convergência exponencial. Isso permite que a precisão necessária seja atingida com significativamente menos nós de quadratura do que os métodos padrão de convergência polinomial.

3. Mapeamento de Rede para Pesos Heterogêneos:
   Para lidar com a heterogeneidade dos parâmetros de ruído (onde os pesos são números racionais), os autores derivam um fator de escala unificado usando a identidade de Bézout. Isso mapeia a soma ponderada heterogênea em uma rede inteira comum, preservando a função de massa de probabilidade discreta sem recorrer ao agrupamento (binning) com perda de informação. Esta etapa permite a derivação de desigualdades de concentração sub-gaussianas precisas para determinar os limites de truncamento necessários para as somas infinitas.

4. Integração Acelerada por Crivo:
   Apesar da convergência exponencial, configurações de alta dimensão com tolerâncias rigorosas ($10^{-35}$) ainda exigem a avaliação de milhões de nós. Para superar isso, os autores introduzem um "algoritmo de crivo" inspirado na teoria dos números. Este algoritmo explora a estrutura de pico periódica das funções características para identificar e podar rigorosamente os nós de quadratura onde é garantido que o integrando seja desprezível. Ao descartar esses nós, o método reduz o número de avaliações de função de mais de $10^6$ para aproximadamente 203.

Principais Contribuições

• Contabilidade de Privacidade Exata: O artigo apresenta a primeira contabilidade de privacidade exata e livre de suposições para o Arquivo DHC do Censo de 2020, indo além das aproximações de limite superior da zCDP.
• Aceleração Computacional: O método proposto alcança uma aceleração de mais de três ordens de magnitude em comparação com os métodos de estado da arte anteriores. A avaliação de uma única alocação de orçamento de privacidade cai de ~1.000 horas de CPU para 0,5 hora de CPU.
• Escalabilidade: O método computa com sucesso os perfis de privacidade exatos para todos os 946 pares de alocações de orçamento de privacidade no Arquivo DHC, uma tarefa anteriormente considerada computacionalmente impraticável.
• Insight Teórico: Os autores fornecem uma explicação teórica para a divergência entre mecanismos gaussianos discretos e contínuos usando expansões de Edgeworth, provando que o erro de aproximação é de ordem $O(m^{-3/2})$, onde $m$ é o número de composições.

Resultados

• Troca Privacidade-Utilidade: Ao usar a contabilidade exata, os autores demonstram que a variância do ruído pode ser reduzida em 15,08% a 24,82% mantendo as mesmas garantias de privacidade do atual método baseado em zCDP do Bureau. Isso aumenta significativamente a utilidade estatística dos dados liberados.
• Desempenho: O método calcula as curvas exatas de $f$-DP e $(\varepsilon, \delta)$-DP para o Arquivo DHC do Censo de 2020. Os resultados mostram que a abordagem atual de limite superior do Bureau é conservadora, gerando uma relação privacidade-utilidade estritamente pior do que o método exato.
• Orientação Prática: Os autores observam que as garantias de privacidade através de diferentes mecanismos compostos são altamente semelhantes. Eles propõem o uso de um único mecanismo composto representativo (especificamente $[f_{M_0}, f_{M_0}]$) como um proxy durante a fase de ajuste do orçamento de privacidade, para evitar repetições de computações de escala total, com uma avaliação exata final realizada após o ajuste.

Significância
O artigo afirma resolver um problema crítico colocado pelo Census Bureau referente à relação subótima privacidade-utilidade causada por limites de privacidade frouxos. Ao permitir a contabilidade exata e livre de suposições, o método permite que os formuladores de políticas tratem o custo de privacidade como um recurso ajustável, otimizando o equilíbrio entre a utilidade dos dados e a proteção da privacidade. O framework não se limita ao Censo; oferece uma abordagem geral, rápida e numericamente confiável para a contabilidade de privacidade exata em configurações de grande composição envolvendo mecanismos discretos heterogêneos. Os autores enfatizam que sua abordagem evita o "ruído excessivo desnecessário" que atualmente degrada a qualidade dos produtos de dados federais usados para o redesenho de distritos e pesquisa econômica.