Preserving Target Distributions With Differentially Private Count Mechanisms

1. 問題定義 (Problem)

差分プライバシーの標準的なメカニズム（ラプラス機構や幾何学的機構など）は、個々のカテゴリのカウント値にノイズを追加してプライバシーを保護します。しかし、これらのメカニズムは「個々のカウントの精度（Accuracy of Counts）」を最適化するように設計されているため、**「カウント値の分布（Distribution of Counts）」**を歪めてしまうという問題があります。

• 分布の重要性: 研究者や政策立案者は、特定のカテゴリ（例：「コロラド州の鳥インフルエンザ症例数」）だけでなく、分布に関する質問（例：「ゼロの症例数を持つ州の割合は？」、「2 人以上の女性がいる取締役会の割合は？」）を頻繁に行います。
• 既存手法の限界: 標準的な DP メカニズムを適用すると、分布のバイアスが生じます（例：ゼロカウントの過大評価）。
• 一貫性の欠如: 分布を別々に推定して公開する場合、カウント表と分布表の間に整合性が保たれず、統計分析の信頼性が損なわれます。
• 課題: カウント表のプライバシーを保護しつつ、**「分布の精度（Accuracy of Distribution）」**を維持し、かつ「カウントの精度」と「計算時間（Runtime）」とのバランスを取るメカニズムの設計が必要です。

2. 提案手法 (Methodology)

著者らは、**「2 段階のカウントフレームワーク」**を提案し、これを数学的に定式化しました。

2.1 2 段階フレームワーク

プライバシー予算 $\epsilon_t$ を $\epsilon_1$（分布の秘匿）と $\epsilon_2$（カウント表の秘匿）に分割して使用します。

1. 分布の秘匿化（Distribution Privatizer）:
   • 真のカウント分布 $\zeta$ を $\epsilon_1$ 予算で秘匿化し、目標分布 $z$（固定点）を生成します。
   • 新規メカニズム「Cyclic Laplace（循環ラプラス）」: 既存のヒストグラム用メカニズムではなく、分布の構造（隣接するビン間の移動）に特化した新しいメカニズムです。隣接するビン間でノイズを共有・循環させることで、累積分布の誤差を最小化します。
2. カウントメカニズムの構築（Constructor Algorithm）:
   • 生成された目標分布 $z$ を「固定点（Fixed Point）」として持つ、$\epsilon_2$-差分プライバシーを満たす遷移行列 $T$ を構築します。
   • 行列 $T$ を入力カウント $d_i$ に適用することで、出力カウントを生成します。固定点の性質により、出力分布の期待値は $z$ となり、結果として真の分布 $\zeta$ に近い分布が得られます。

2.2 数学的理論：$\epsilon$-スケールと多面体

固定点制約を満たす遷移行列の構造を解析するために、新しい数学的枠組みを構築しました。

• $\epsilon$-スケール（$\epsilon$-scale）: 差分プライバシーの制約が隣接するすべての位置で等号成立（binding）となる確率ベクトル。これらは、差分プライバシーを満たす遷移行列の「原子（基本構成要素）」となります。
• 多面体の表現:
  • 固定点制約を満たすメカニズムの集合 $F$ と、制約のない集合 $U$ を定義します。
  • これらの集合は凸多面体であり、その極点（Extreme Points）は $\epsilon$-スケールの非負線形結合（錐的結合）で表現できます。
  • 表現多面体（Representation Polytope）: 遷移行列 $T$ を $\epsilon$-スケールの重み行列 $B$ で表現する空間 $R_F$ を定義し、$T$ と $B$ の間の線形写像 $\Psi$ を導入しました。これにより、複雑な制約を満たす行列の探索を、より単純な空間での探索に変換できます。
• 極点の特性: 表現空間 $R_F$ の極点は、特定の線形独立性条件（$\Psi$-affinely simplified）を満たすことで特徴づけられ、これにより効率的なアルゴリズム設計が可能になります。

2.3 構築アルゴリズム

• ヒューリスティック構築アルゴリズム（Algorithm 1）: 線形計画法（LP） solver を使用すると計算コストが高すぎる場合（$n$ が大きい場合）のために開発された貪欲アルゴリズムです。
  • 単一ピークを持つ $\epsilon$-スケールを貪欲に選択し、列を埋めていくことで、$O(n^2)$ の計算時間で $F$ の極点を生成します。
  • 列選択関数 $\kappa$（最大確率、最小確率、サンドイッチ順序など）をパラメータとして持ち、データ特性に応じて調整可能です。
• 2 段階未固定最適構築（Algorithm 2）: 固定点制約を課さない場合の基準（Baseline）として、Ghosh らの結果を拡張し、$O(n^2)$ で最適解を導出するアルゴリズムも提案しています。

3. 主要な貢献 (Key Contributions)

1. 分布保持型カウントメカニズムの提案:
   • 「分布の精度」を明示的な設計基準とした新しいフレームワークの確立。
   • 分布に特化した「Cyclic Laplace」メカニズムの提案と、その差分プライバシー保証の証明。
2. 数学的理論の構築:
   • 固定点制約を持つ差分プライバシー遷移行列を $\epsilon$-スケールを用いて記述する理論的枠組みの提示。
   • 表現多面体 $R_F$ の極点を特徴づける条件（$\Psi$-affinely simplified）の導出。
3. 効率的な構築アルゴリズム:
   • 大規模な $n$ に対しても実用的な $O(n^2)$ 時間のヒューリスティック構築アルゴリズム（Algorithm 1）の開発。
   • 固定点制約なしの最適解を高速に求めるアルゴリズム（Algorithm 2）の提案。
4. 実証実験とトレードオフの分析:
   • 合成データおよび実データ（米国犯罪統計、学校教員数など）を用いた実験により、固定点制約が分布精度を大幅に向上させること、かつカウント精度や計算時間の損失は許容範囲であることを示しました。

4. 実験結果 (Results)

3 つの性能基準（分布精度、カウント精度、実行時間）に基づき評価を行いました。

• 分布の精度（Accuracy of Distribution）:
  • 固定点制約を導入した手法は、未固定のベースライン（既存手法）と比較して、分布誤差（Wasserstein 距離など）を劇的に改善しました。
  • 例：二項分布データにおいて、$\epsilon_t=0.48$ の場合、分布誤差が 94% 減少しました。
• カウントの精度（Accuracy of Counts）:
  • 固定点制約により、個々のカウント値の誤差（平均絶対偏差など）は若干増加しました（数%の増加）。
  • しかし、分布精度の大幅な向上と比較して、このコストは許容可能なトレードオフであることが示されました。
• 実行時間（Runtime）:
  • 既存の線形計画法（单纯形法や内部点法）は $n$ が大きくなると計算時間が爆発的に増加し、実用的ではありませんでした。
  • 提案したヒューリスティックアルゴリズム（Algorithm 1）は、$n=2000$ であっても 10 秒未満で実行可能であり、未固定のベースラインと同等の高速性を維持しました。
• プライバシー予算の配分:
  • 分布秘匿化（$\epsilon_1$）とカウント秘匿化（$\epsilon_2$）の最適な配分比率 $f = \epsilon_1/\epsilon_t$ について、データに依存しない経験則（Rule of Thumb）を提案しました。
  • 公式：$\hat{f}(\epsilon_t) = 0.106 + 0.533 \exp(-2.87\epsilon_t)$。これにより、予算配分をデータに依存せずに行うことが可能になりました。

5. 意義と結論 (Significance)

この研究は、差分プライバシーの適用において「個々の値の精度」だけでなく「分布の形状（統計的性質）」を保持することの重要性を浮き彫りにしました。

• 実用性: 国勢調査局や公衆衛生機関など、集計データを利用する組織にとって、分布の歪みは政策決定や研究に重大な影響を与えます。本フレームワークは、プライバシーを保護しつつ、分布ベースの分析を可能にする実用的なソリューションを提供します。
• 理論的進展: 差分プライバシーと固定点制約を組み合わせるための代数的・幾何学的な枠組みは、今後のメカニズム設計や最適化問題への応用が期待されます。
• バランスの取れたアプローチ: 分布精度の大幅な向上と、カウント精度・計算コストの最小限の犠牲という、実社会での導入に適したトレードオフを実現しました。

結論として、提案された「2 段階カウントフレームワーク」は、差分プライバシー下での集計データ公開において、統計的有用性とプライバシー保護の両立を達成する有望な手法です。