Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy

技術要約：局所差分プライバシーを超えたプライバシーメカニズムのドブロシン係数

問題提起
本論文は、離散マルコフカーネル（プライバシーメカニズム）におけるプライバシーを定量化する指標として、局所差分プライバシー（LDP）を用いることの限界に対処している。LDPは広く採用されているが、著者らは主に2つの問題を指摘している：

1. 過度な制限性： パラメータ推定などの統計的応用において、厳格なLDP保証（小さな$\epsilon$）を達成しようとすると、推定性能（ミニマックスリスク）が極端に低下する場合がある。
2. ゼロ確率における直感に反する挙動： 標準的なLDPの定義では、メカニズムがある入力に対して任意の出力をゼロ確率で割り当てる場合（$K_{Y|X=x}(y) = 0$）、プライバシーコストが無限大となる。これは、メカニズムが（本論文の例における$K_1$のように）大幅なランダム化を含んでいる場合でも、ゼロの要素を持つという理由だけで、アイデンティティ写像や自明なメカニズム（例：$K_2$）と同一視してしまうことを意味しており、「ノイズの多さ」と「決定論的な挙動」によるプライバシー漏洩の違いを識別できていない。

これらの問題に対処するため、著者らは、厳密なLDPではなく点別最大漏洩（Pointwise Maximal Leakage: PML）を満たすメカニズムに対するドブロシン係数（全変動距離の収縮係数）を調査している。PMLは、入力分布 $P_X$ に依存する最大漏洩の点別適応版である。著者らは、入力分布 $P_X$ がゼロから一定の定数 $c$ 以上離れた最小確率質量を持つ（すなわち、$\min_x P_X(x) \geq c$）メカニズムに焦点を当てて分析を行っている。このフレームワークにより、標準的なLDPでは「無限にプライベート」または「無限にリークしている」とみなされてしまうような、ゼロ確率の割り当てを含むメカニズムの分析が可能になる。

手法
本論文では、情報理論的なツールを用いて、プライバシーメカニズムを通じた$f$-ダイバージェンスの収縮に関する境界を導出している。

• 定義： 著者らは、$(\epsilon, c)$-PMLを、集合 $Q_X(c) = \{P_X : \min_x P_X(x) \geq c\}$ に属するすべての入力分布に対する制約として定義している。これはLDPを一般化したものであり、$c \to 0$ の極限においてLDPに対応する。
• 収縮係数： 研究の核となる対象は、$(\epsilon, c)$-PMLを満たすメカニズムに対する全変動（TV）距離の収縮の上限であるドブロシン係数 $\eta_{TV}(\epsilon, c)$ である。
• 二値出力への簡略化： 著者らは、最大のドブロシン係数を見つけるためには、二値出力空間（$|Y|=2$）を持つメカニズムを検討すれば十分であることを証明している。これにより、最適化問題が大幅に簡素化される。
• 不等式： 導出には、TV境界を一般的な$f$-ダイバージェンス（相対エントロピーやヘリンジャー距離など）へ拡張するために、Binetteの不等式（逆ピンズカー不等式の一般化）を用いている。

主な貢献および結果

1. ドブロシン係数の達成可能な境界：
   本論文は、任意の $(\epsilon, c)$-PMLを満たすカーネルに対するドブロシン係数 $\eta_{TV}(\epsilon, c)$ のタイトな上界を導出している。その境界は以下で与えられる：
   $$\eta_{TV}(\epsilon, c) \leq \min\left( \frac{e^\epsilon - 1}{e^\epsilon(1 - Nc) + 1}, 1 \right)$$
   ここで $N$ は入力アルファベットのサイズである。

• 領域分析： 著者らは、$\epsilon \geq \log(2/Nc)$ の場合、収縮係数は1（収縮は起こらない）であることを示している。$\epsilon < \log(2/Nc)$ の場合、係数は1よりも厳密に小さくなり、プライバシーによる収縮が生じることを示している。
• LDPの回復： $c \to 0$ とすると、この境界は既知の$\epsilon$-LDPの結果 $\eta_{TV} \leq \frac{e^\epsilon - 1}{e^\epsilon + 1}$ を回復する。
• メカニズムの構成： 論文では、これらの境界を達成する具体的なメカニズム（特に二値出力メカニズム）の構成法を提供し、これらの境界が達成可能であることを示している。

2. 一般的な$f$-ダイバージェンスへの拡張：
   Binetteの不等式を用いることで、TV境界を一般的な$f$-ダイバージェンスへと拡張している。著者らは、$(\epsilon, c)$-PML制約下での相対エントロピーおよびヘリンジャー距離に対する強いデータ処理不等式（SDPI）を導出している。これらの境界は、TV収縮係数と出力分布の極値比に依存する。

3. ミニマックスリスクへの適用：
   導出された境界は、プライベートなミニマックス推定リスクに適用される。Le Camの2点法と$f$-ダイバージェンスのテンソル化特性を用いて、特定のリスクレベルを達成するために必要なサンプル複雑性が、プライベートなドブロシン係数の逆数に比例する因子によって増加することを示す。具体的には、係数が1であればサンプル複雑性は非プライベートな設定と一致し、1未満であれば実効的なサンプルサイズが減少する。

意義および主張
本論文は、LDP単独よりも精緻なプライバシーメカニズム分析の枠組みを提供すると主張している。パラメータ $c$ を導入することで、ゼロ確率の要素を含むメカニズムであっても、それらをLDPの下で問題となるものとして扱うことなく、プライバシー漏洩を定量化することができる。

• よりタイトな境界： LDPを満たすメカニズムに対して、提案された境界は、入力分布が最小質量 $c$ を持つことが既知である場合、従来の知見よりもタイトであるか、あるいはより適応性が高い。
• LDPを超えて： このフレームワークは、有限のLDP保証を持たないを含む、すべての離散カーネルへの収縮係数の分析を拡張する。
• 操作的な解釈： 結果は、理論的な収縮係数を統計的推定性能の劣化に直接結びつけており、リスクの増大やサンプル複雑性の観点から「プライバシーのコスト」を定量化するためのツールを提供している。

著者らは、本研究が既存のLDPの結果を特殊なケースとして回復しつつ、一様分布の制約から完全なLDP領域への連続的な補間を提供することで、特定の統計的文脈におけるLDPの「過度な制限性」に対処していることを強調している。