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

技術要約：2020年米国国勢調査における正確なプライバシー会計のための篩（ふるい）加速型求積法

問題提起
米国国勢調査局は、2020年国勢調査の集計において、整数値の離散ガウスノイズを注入することで差分プライバシー（DP）を採用した。現在、同局はゼロ集中差分プライバシー（zCDP）を用いて形式的なプライバシー保証を提供しているが、これらの保証は正確なプライバシー損失の上限値に過ぎない。この乖離により、プライバシー予算を満たすために不必要な過剰ノイズの注入を余儀なくされており、その結果、連邦資金の配分や政治的な区割り変更といった重要なダウンストリームのアプリケーションにおける統計的有用性が低下している。

核心となる課題は、2020年国勢調査の人口および住居特性（DHC）ファイルの正確なプライバシープロファイルを評価することである。数学的には、これは、不均一な離散ガウス分布の高次元畳み込みの裾確率を、$f$-差分プライバシー（$f$-DP）の枠組みの下で計算することを意味する。このタスクは、以下の3つの要因により計算上極めて困難である：

1. 不均一性： ノイズの分散はクエリや地理的レベルによって異なるため、閉形式の解を可能にする代数的構造が破壊される。
2. 高次元性： この合成は、地理的な経路に沿って最大80重の合成を含むため、高次元の積分を生じさせる。
3. 精度要件： 国勢調査局は、結果となる$(\varepsilon, \delta)$-DP曲線の精度を確保するために、極めて厳格な数値誤差許容範囲（例：$10^{-35}$）を課している。従来の手法では、単一のプライバシー予算割り当てを評価するために約1,000 CPU時間を必要としており、DHCファイルに含まれる946組の異なる割り当てペアの全規模な会計を行うことは計算上不可能であった。

手法
著者らは、問題を数値積分タスクとして再定式化する、計算効率が高く数学的に厳密な求積法を提案している。この手法は、以下の4つのステップで進行する：

1. 離散フーリエ変換（DFT）による問題の再定式化：
   独立な離然ガウス型確率変数の重み付き和の裾確率を計算する問題は、数値積分問題へと変換される。逆離散フーリエ変換を利用することで、累積確率は区間 $[-\pi, \pi]$ 上の特性関数の積の積分として表現される。

2. 指数収束型求積法：
   著者らは、積分を近似するために台形則を採用している。彼らは、複素解析的かつ周期的な被積分関数（具体的には離散ガウス分布の特性関数）に対して、台形則が指数収束を達成することを確立した。これにより、標準的な多項式収束法と比較して、指数関数的に少ない求積ノード数で必要な精度を満たすことが可能となる。

3. 不均一な重みのための格子写像：
   ノイズパラメータ（重みが有理数である場合）の不均一性を扱うために、著者らはベズーの等式を用いて統一されたスケーリング係数を導出している。これにより、不均一な重み付き和を共通の整数格子上に写像し、情報の損失を伴うビン化（binning）を行うことなく、離散確率質量関数を保持する。このステップにより、無限級数の打ち切り境界を決定するための精密な劣ガウス集中不等式の導出が可能になる。

4. 篩（ふるい）加速型積分：
   指数収束を実現しているとはいえ、厳格な許容誤差（$10^{-35}$）を伴う高次元の設定では、依然として数百万のノードを評価する必要がある。これを克服するため、著者らは数論に着想を得た「篩（ふるい）アルゴリズム」を導入している。このアルゴリズムは、特性関数の周期的なピーク構造を利用して、被積分関数が無視できることが保証されている求積ノードを厳密に特定し、刈り込む（プルーニングする）ものである。これらのノードを破棄することで、関数評価の回数を$10^6$回以上から約203回へと削減できる。

主な貢献

• 正確なプライバシー会計： 本論文は、zCDPによる上限近似を超えた、2020年国勢調査DHCファイルに対する初のエラーフリーで正確なプライバシー会計を提示している。
• 計算の加速： 提案手法は、従来の最先端手法と比較して3桁以上の高速化を実現している。単一のプライバシー予算割り当ての評価時間は、約1,000 CPU時間から0.5 CPU時間へと短縮された。
• スケーラビリティ： 本手法は、以前は計算上不可能と考えられていた、DHCファイル内の946組のプライバシー予算割り当ての全規模な会計を成功裏に完了した。
  エッジワース展開を用いることで、離散ガウスメカニズムと連続ガウスメカニズムの間の乖離に関する理論的説明を提供し、近似誤差が $O(m^{-3/2})$ （ここで $m$ は合成数）のオーダーであることを証明した。

結果

• プライバシーと有用性のトレードオフ： 正確な会計を用いることで、現在の国勢調査局のzCDPベースのアプローチと同じプライバシー保証を維持しつつ、ノイズ分散を**15.08%から24.82%**削減できることを実証した。これは、公開されるデータの統計的有用性を大幅に向上させる。
• 性能： 提案手法は、2020年国勢調査DHCファイルの正確な $f$-DP および $(\varepsilon, \delta)$-DP 曲線を計算する。結果は、現在の局の上限近似アプローチが保守的であり、正確な手法と比較して厳密に劣るプライバシー・有用性トレードオフをもたらしていることを示している。
• 実践的なガイダンス： 著者らは、合成されたメカニズム間のプライバシー保証が非常に類似していることを観察している。彼らは、プライバシー予算のチューニング段階において、代表的な合成メカニズム（具体的には $[f_{M_0}, f_{M_0}]$）をプロキシとして使用することを提案している。これにより、フルスケールの計算を繰り返すことなく、チューニング後に最終的な正確な評価を行うことができる。

意義
本論文は、不十分なプライバシー境界によって引き起こされる、プライバシーと有用性のトレードオフの最適化という、国勢調査局が直面している重要な未解決問題の解決策を提示している。正確で仮定のない会計を可能にすることで、政策立案者がプライバシーコストを調整可能なリソースとして扱い、データの有用性とプライバシー保護のバランスを最適化することを可能にする。このフレームワークは国勢調査に限定されるものではなく、不均一な離散メカニズムを含む大規模な合成設定における、正確なプライバシー会計のための汎用的かつ高速で、数値的に信頼性の高いアプローチを提供する。著者らは、自身のアプローチが、区割り変更や経済研究に使用される連邦データ製品の質を低下させている「不必要な過剰ノイズ」を回避するものであることを強調している。