Better Privacy Guarantees for Larger Groups

技術要約：大規模グループにおけるより優れたプライバシー保証

問題提起
本論文は、PujolおよびDesfontaines [2023]によって提示された、固定された互いに素なグループに対するプライベートなヒストグラム設計に関する未解決問題に取り組んでいる。標準的な差分プライバシーメカニズムは、通常、すべてのカウントに対して一定の大きさのノイズを加える。これは一様な絶対的プライバシーを提供する一方で、グループの規模が小さい場合に比べて、大規模なグループにおける相対誤差が著しく小さくなるという結果を招く。核心となる問いは、この余剰の精度をどのように「使い分ける」ことができるかである。すなわち、グループのカウント（$x_i$）に比例して誤差をスケールさせることで、より大きなグループのメンバーに対してより強力なプライバシー保証（より小さなプライバシー予算）を提供できるかという点である。

本論文は、これを**「1件の追加または削除（add-or-remove-one）」隣接モデルの下で調査している。目標は、プライバシー予算 $v(n)$ がグループの数 $n$ のみに依存し、非増加であり、かつカウント依存型のグループ単位ゼロ集中差分プライバシー（zCDP）**を満たすメカニズムを見つけることである。これには、隣接するデータセット間における、すべての次数 $\alpha > 1$ におけるレニィ・ダイバージェンス（Rényi divergence）の両方向の境界を定めることが求められる。

重要な技術的障壁として、**「ゼロにおける境界条件」**が特定された。元の定式化では、期待絶対誤差が厳密に $r x_i$ 未満であることを要求していた。$x_i = 0$ の場合、これは $E|\hat{x}_i| < 0$ を意味し、不可能である。さらに、不等式を $\leq$ に緩和したとしても、$0 \leftrightarrow 1$ のエッジにおいて有限の二側レニィ・ダイバージェンスを維持しようとすると矛盾が生じる（出力がカウント1において決定論的であることを強制し、誤差の境界に抵触する）。

手法と修正された定式化
この境界問題を解決するために、著者らは「修正された」効用要件を提案している：
$$E|\hat{x}_i - x_i| < r \max\{x_i, 1\}$$
これは、すべての正のカウントに対して相対誤差の目標を維持しつつ、ゼロにおいて固定された絶対許容誤差を導入することで、問題を解決可能にしている。

本論文では、主に2つの手法を用いている：

1. 実現可能性（上界）: 既存の「シフト変換（shifted-transformation）」フレームワーク（Finleyら [2026]）を特殊化している。カウント空間をシフト $c$ を伴う対数（すなわち $\log(x_i + c)$）によって変換し、固定分散のガウスノイズを加え、指数関数をとる前に決定論的なドリフトを適用する。

   • 主要な革新: 標準的な対数正規メカニズムは平均無偏性を確保するために $-\sigma^2/2$ のドリフトを使用するが、本メカニズムは $-\sigma^2$ のドリフトを使用する。この特定のドリフトは、本論文の効用指標である「期待絶対乗法的誤差」を最小化するように選択されている。
   • プライバシーメカニズム: 等分散の空間で対数計算を行うことにより、隣接するカウント間のレニィ・ダイバージェンスがすべての次数 $\alpha$ に対して有限であることを保証し、不等な分散によって一方の方向で無限のダイバージェンスが発生する「テールの障害（tail obstruction）」を回避している。

2. 不可能証明（下界）: 修正された効用およびカウント依存型zCDPの要件を満たすメカニズムは、カウントの逆二乗よりも速い速度でプライバシー予算が減衰することはできないことを証明する。

   • 2カウントによる議論: 2つの特定のカウント間のテストにより、$n^{-2}$ 指数を確立する。
   • 多カウントによる議論: 「隠れたオフセット（hidden offset）」となる乱数を利用し、情報理論的な議論（期待絶対誤差と相互情報量の関係）を用いることで、プライバシー予算の主要項に関するよりタイトな下限を導出している。

主要な結果

• 最適な漸近レート: 任意の固定された $0 < r < 1$ に対して、最適なプライバシー予算 $v(n)$ は $\Theta_r(n^{-2})$ で減衰する。

  • 上界: シフト・ログ・ガウス・メカニズムは $v(n) = O_r(n^{-2})$ を達成する。具体的には、$n \to \infty$ のとき、$v(n) \approx \frac{1}{2\sigma^2 n^2}$ となる。
  • 下界: いかなるメカニズムも要件を満たす場合、$\liminf_{n \to \infty} n^2 v(n) \geq \frac{(1-r)^6}{128r^2(1+r)^2}$ を満たさなければならない。これにより、逆二乗のレートが本質的なものであり、構成上のアーティファクトではないことが確認された。

• 主要係数: 本論文は、小規模な $r$ および大規模な $n$ の極限における、主要係数 $C^*$ の間のギャップを以下のように狭めている：
  $$\frac{\pi}{4e^2} \leq C^* \leq \frac{1}{\pi}$$
  これらの境界の比は約2.995であり、境界が3倍以内の範囲にあることを示している。

• 不等分散ガウス分布の失敗: 本論文は、単純な $N(n, r^2 n^2)$（カウントの二乗に比例する分散を持つガウスノイズ）を放出するメカニズムがzCDPの定義を満たさないことを示している。これは正しい誤差スケールを持っているものの、隣接するカウント間の不等な分散により、十分に高い次数 $\alpha$ において一方の方向へのレニィ・ダイバージェンスが無限となり、「全次数」の要件に違反する。

• 自明なケース: $r=1$ のとき、データに依存しない放出（例：常に0.5を出力する）は、修正された基準をプライバシー損失ゼロ（$v \equiv 0$）で満たす。

意義と主張
本論文は、この特定の形式のグループ単位プライバシーに対して、逆二乗のレートが最適であるという、メカニズムに依存しない最初の証明を提供したと主張している。

• 実現可能性: 「修正された」定式化が解決可能であることを確立し、最適なレートを達成する具体的な構成可能なメカニズム（シフト・ログ・ガウス）を提供している。
• 最適性: いかなる複雑さや相関構造を持つメカニズムであっても、$n^{-2}$ の減衰率を改善することはできないことを証明している。
• 精密性: 多カウントの情報理論的議論を用いることで、従来の2カウント分析と比較して主要係数の境界を大幅にタイトにし、不確実性を3倍未満の因子にまで減少させている。

著者らは、最適な係数 $C^*$ の正確な値を決定することは依然として未解決の問題であると明記している。また、彼らの結果は固定された互いに素なグループに適用されるものであり、重複するグループやデータ依存のグループには、別途の感度分析が必要であるとも述べている。このメカニズムは（$-\sigma^2$ のドリフトにより）バイアスがあるが、無偏であることではなく、期待絶対誤差を最小化するように特別に調整されている。