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

Résumé technique : Une méthode de quadrature accélérée par tamis pour une comptabilité exacte de la confidentialité dans le Recensement des États-Unis de 2020

Énoncé du problème
Le Bureau du Recensement des États-Unis a adopté la confidentialité différentielle (DP) pour le recensement décennal de 2020 en injectant du bruit gaussien discret de type entier dans les tableaux du recensement. Bien que le Bureau fournisse actuellement des garanties de confidentialité formelles à l'aide de la confidentialité différentielle à concentration nulle (zCDP), ces garanties sont des bornes supérieures sur la perte de confidentialité exacte. Cet écart impose l'injection d'un excès de bruit inutile pour satisfaire aux budgets de confidentialité, ce qui dégrade l'utilité statistique des données pour des applications critiques en aval, telles que l'allocation des fonds fédéraux et le redécoupage électoral.

Le défi central est d'évaluer le profil de confidentialité exact du fichier des caractéristiques démographiques et du logement (DHC) du recensement de 2020. Mathématiquement, cela nécessite de calculer les probabilités de queue de hautes convolutions de distributions gaussiennes discrètes hétérogènes sous le cadre de la confidentialité $f$-différentielle ($f$-DP). Cette tâche est computationnellement prohibitive en raison de trois facteurs :

1. Hétérogénéité : Les variances du bruit diffèrent selon les requêtes et les niveaux géographiques, détruisant les structures algébriques qui permettent des solutions en forme close.
2. Dimensionnalité : La composition implique jusqu'à 80 compositions le long des chemins géographiques, créant des intégrales de haute dimension.
3. Exigences de précision : Le Bureau du Recensement exige des tolérances d'erreur numérique extrêmement strictes (par exemple, $10^{-35}$) pour garantir l'exactitude des courbes $(\varepsilon, \delta)$-DP résultantes. Les méthodes précédentes nécessitaient environ 1 000 heures CPU pour évaluer une seule allocation de budget de confidentialité, rendant l'évaluation complète des 946 paires d'allocations distinctes du fichier DHC informatiquement irréalisable.

Méthodologie
Les auteurs proposent une méthode de quadrature mathématiquement rigoureuse et efficace qui reformule le problème de la comptabilité exacte de la confidentialité comme un problème d'intégration numérique. La méthode se déroule en quatre étapes clés :

1. Reformulation du problème via la transformée de Fourier discrète (DFT) :
   Le problème consistant à calculer la probabilité de queue d'une somme pondérée de variables aléatoires gaussiennes discrètes indépendantes est transformé en un problème d'intégration numérique. En utilisant la transformée de Fourier discrète inverse, la probabilité cumulative est exprimée comme une intégrale du produit des fonctions caractéristiques sur l'intervalle $[-\pi, \pi]$.

2. Quadrature à convergence exponentielle :
   Les auteurs emploient la règle du trapèze pour approximer l'intégrale. Ils établissent que pour des intégrands analytiques complexes et périodiques (spécifiquement les fonctions caractéristiques des gaussiennes discrètes), la règle du trapèze atteint une convergence exponentielle. Cela permet de satisfaire la précision requise avec beaucoup moins de nœuds de quadrature que les méthodes de convergence polynomiale standard.

3. Cartographie sur réseau pour les poids hétérogènes :
   Pour gérer l'hétérogénéité des paramètres de bruit (où les poids sont des nombres rationnels), les auteurs dérivent un facteur d'échelle unifié en utilisant l'identité de Bézout. Cela projette la somme pondérée hétérogène sur un réseau entier commun, préservant la fonction de masse de probabilité discrète sans recourir à un regroupement (binning) destructeur. Cette étape permet de dériver des inégalités de concentration de type sous-gaussienne précises pour déterminer les limites de troncature nécessaires des sommes infinies.

4. Intégration accélérée par tamis :
   Malgré la convergence exponentielle, les contextes de haute dimension avec des tolérances strictes ($10^{-35}$) nécessitent encore l'évaluation de millions de nœuds. Pour surmonter cela, les auteurs introduisent un « algorithme de tamis » inspiré de la théorie des nombres. Cet algorithme exploite la structure de pic périodique des fonctions caractéristiques pour identifier et éliminer rigoureusement les nœuds de quadrature où l'intégrande est garanti comme étant négligeable. En écartant ces nœuds, la méthode réduit le nombre d'évaluations de fonctions de plus de $10^6$ à environ 203.

Contributions clés

• Comptabilité de la confidentialité exacte : L'article présente la première comptabilité de confidentialité exacte et sans hypothèse pour le fichier DHC du recensement de 2020, allant au-delà des approximations de la zCDP.
• Accélération computationnelle : La méthode proposée atteint une accélération de plus de trois ordres de grandeur par rapport aux méthodes de pointe précédentes. L'évaluation d'une seule allocation de budget de confidentialité passe d'environ 1 000 heures CPU à 0,5 heure CPU.
• Scalabilité : La méthode calcule avec succès les profils de confidentialité exacts des 946 paires d'allocations de budget de confidentialité du fichier DHC, une tâche auparavant jugée pratiquement impossible.
• Aperçu théorique : Les auteurs fournissent une explication théorique de la divergence entre les mécanismes gaussiens discrets et continus à l'aide des développements d'Edgeworth, prouvant que l'erreur d'approximation est de l'ordre de $O(m^{-3/2})$, où $m$ est le nombre de compositions.

Résultats

• Compromis confidentialité-utilité : En utilisant la comptabilité exacte, les auteurs démontrent que la variance du bruit peut être réduite de 15,08 % à 24,82 % tout en maintenant les mêmes garanties de confidentialité que l'approche actuelle de la zCDP du Bureau. Cela améliore considérablement l'utilité statistique des données publiées.
• Performance : La méthode calcule les courbes exactes $f$-DP et $(\varepsilon, \delta)$-DP du fichier DHC du recensement de 2020. Les résultats montrent que l'approche actuelle de borne supérieure du Bureau est conservatrice, produisant un compromis confidentialité-utilité strictement moins bon que la méthode exacte.
• Orientation pratique : Les auteurs observent que les garanties de confidentialité à travers différents mécanismes composés sont très similaires. Ils proposent d'utiliser un mécanisme composé représentatif unique (spécifiquement $[f_{M_0}, f_{M_0}]$) comme proxy lors de la phase de réglage du budget de confidentialité, avec une évaluation exacte finale effectuée après le réglage.

Signification
L'article prétend résoudre un problème critique posé par le Bureau du Recensement concernant le compromis sous-optimal confidentialité-utilité causé par des bornes de confidentialité lâches. En permettant une comptabilité exacte et sans hypothèse, la méthode permet aux décideurs de traiter le coût de la confidentialité comme une ressource ajustable, optimisant l'équilibre entre l'utilité des données et la protection de la vie privée. Le cadre n'est pas limité au Recensement ; il offre une approche générale, rapide et numériquement fiable pour la comptabilité de la confidentialité exacte dans les contextes de grande composition impliquant des mécanismes discrets hétérogènes. Les auteurs soulignent que leur approche évite « l'excès de bruit inutile » qui dégrade actuellement la qualité des produits de données fédéraux utilisés pour le redécoupage électoral et la recherche économique.