Federated and differentially private estimation of KL divergence

技術要約: FedPriKL – KLダイバージェンスのフェデレーテッドおよび差分プライバシーを考慮した推定

問題提起

現代のフェデレーテッドラーニング（連合学習）およびアナリティクスにおいて、モデルの再学習やファインチューニングが必要な時期を判断するために、分布のドリフトを監視することは極めて重要なタスクである。これには、分散されたクライアントが保持する経験的分布（$P$）と、固定された公開リファレンス分布（$\Pi$）との比較が必要となる。しかし、クライエントのデータを直接共有したり、完全なヒストグラムを共有したりすることは、高い通信コストとプライバシー制約のため、多くの場合において不可能である。

既存のアプローチは、以下の大きな障壁に直面している：

1. プライバシー: 中央でのサンプルの収集は、ユーザーのプライバシーを侵害する。
2. 不可能定理: シフト不変性定理 [9] は、ドメインサイズよりも小さい空間において、2つの未知の分布間のKLダイバージェンスを推定することは不可能であることを示唆している。
3. 通信量: クライアントからサーバーへ完全なヒストグラムを送信することは、ドメインが大きい場合、帯域幅の観点から実現不可能である。
4. 局所的摂動におけるバイアス: クライアントが集合前にノイズを加える標準的なローカル差分プライバシー（LDP）のアプローチは、KLダイバージェンスのような非線形関数の推定において、特に小さな確率質量を扱う際に、著しいバイアスを導入する。

本論文は、水平型フェデレーテッド設定において、$P$ が $n$ 個のクライアントの集約データによって定義され、$\Pi$ が既知の公開ベンチマークである場合の $D_{KL}(\Pi \parallel P)$ の推定問題を扱う。目標は、通信オーバーヘッドを最小限に抑えつつ、推定精度を維持しながら、形式的な例レベルの差分プライバシー（DP）を実現することである。

手法: FedPriKL

著者らは、差分プライバシー下での不偏推定を実現するために、「信頼できるアグリゲーター」モデルを活用したサンプリングベースのプロトコルである FedPriKL を提案する。その中核となる技術的革新は、尤度比に基づく不偏モンテカルロ推定器であり、これをセキュアな集計（Secure Aggregation）および較正されたノイズ注入と組み合わせたものである。

主要構成要素:

1. 不偏モンテカルロ推定器:
   完全なダイバージェンスを計算する代わりに、この手法はリファレンス分布 $\Pi$ から $m$ 個の点 $x_i$ をサンプリングする。各サンプルに対し、プロトコルは尤度比 $r(x) = P(x)/\Pi(x)$ を推定する。
   Fact IV.2から導出された恒等式を用いて、KLダイバージェンスは以下の関数を通じて推定される：
   $$\Phi(r(x), \lambda) = \lambda(r(x) - 1) - \ln(r(x))$$
   この関数の $\Pi$ 上での期待値は $D_{KL}(\Pi \parallel P)$ に等しい。パラメータ $\lambda$ は推定器の分散を制御する。

2. プロトコルのワークフロー (Algorithm 2):

   • サンプリング: サーバーは、互いに素なクライアントのバッチ（$C_t$）を選択し、$\Pi$ から点 $x_{i,t}$ をサンプリングする。
   • セキュア集計 (SecAgg): クライアントは、サンプリングされた点のローカルデータセット内での頻度を計算する。これらの頻度は、個々のクライアントデータを明らかにすることなく、グローバルな経験的確率質量 $P(x)$ を計算するために、セキュア集計プロトコル（例：シャミアの秘密分散法）を用いて集約される。
   • 信頼できるアグリゲーターによる処理: 集約された確率は、信頼できるアグリゲーターに送られる。アグリゲーターは尤度比 $r(x)$ を計算し、非線形変換 $\Phi$ を適用し、較正されたガウスノイズ（$\eta_{\epsilon, \delta}$）を結果に加える。
   • 最終推定: ノイズが付加された変換値は平均化され、最終的なDP推定値が生成される。

3. プライバシーメカニズム:
   クライアントが（集計前に）ローカルでノイズを加えるベースラインのアプローチとは異なり、FedPriKLは、セキュア集計の後、かつ非線形変換が完了する前にノイズを加える。これにより、ローカルノイズにおける負の値のクリッピングによって生じるバイアスを回避できる。推定器の感度は有界であり（定理 IV.4 および IV.5）、$(\epsilon, \delta)$-DPを満たすための精密なノイズ較正が可能となっている。

4. 信頼モデル:
   プロトコルは、クライアントの生のデータではなく、サンプリングされた点のセキュアに集約された統計量のみを閲覧する「信頼できるアグリゲーター」（またはTEE/SMCの実装）を想定している。サーバーは「正直だが好奇心旺盛（honest-but-curious）」であり、最終的なノイズ付き推定値のみを受け取る。

主な貢献

1. 問題の定式化: 公開リファレンスとプライベートな経験的分布の間でのKLダイバージェンスを計算する問題を、形式的な差分プライバシーの保証とともに、フェデレーテッド設定において定式化した。
2. FedPriKL アルゴリズム: 例レベルのDPを提供する、通信効率の高いサンプリングベースの $D_{KL}(\Pi \parallel P)$ フェデレーテッド推定器を初めて提示した。
3. 理論的分析:
   • 不偏性: 推定器が不偏であることを証明した（定理 IV.7）。
   • 感度境界: 推定器の有界な感度を確立し、最適なノイズスケールの導出を可能にした（定理 IV.4, IV.5）。
   • 分散の特性化: $\lambda, \epsilon, m$ の関数としての推定器の分散の理論的特性を提供し、分散を最小化するための最適な $\lambda$ を導出した（定理 V.1, V.3）。
4. 通信効率: クライアントあたりのペイロードはドメインサイズに依存しない。ドメインの要素数が $2^{16}$ である場合でも、ペイロードは1 KB未満に抑えられる。

実験結果

著者らは、FEMNIST データセット（筆記者ごとに分割された手書き数字）を用いて、FedPriKLを非プライベートな推定器およびベースラインのLDPアプローチ（Algorithm 1）と比較評価した。

• 精度 vs プライバシー: FedPriKLは、プライバシー予算 $\epsilon$ が中程度（$0.5 \le \epsilon \le 1.0$）の場合、非プライベートな推定器と同等の精度を達成する。
• ベースラインに対する優位性: FedPriKLは、精度と安定性の両面において、ベースライン（ローカル摂動）を大幅に上回る。ベースラインは、負の確率推定の不可避なクリッピングによるバイアスに苦しむ。
• パラメータ感度:
  • $\lambda$: 最適な分散パラメータ $\lambda$ は、経験的に0に近いことが判明した。
  • サンプルサイズ ($m$): 少数のサンプル（$m=10$）で、ほぼ最適な精度を得るのに十分であり、クライアントの通信を軽量に保つことができる。
  • バッチサイズ: 参加するクライアント数の変化は収束率に影響を与えるが、最適な $\lambda$ を根本的に変えることはない。
• 堅牢性: 本手法は、異なるダイバージェンスの大きさ（小さなKL値から大きなKL値まで）にわたって、低い絶対誤差を維持する。

重要性と主張

論文は、公開リファレンスとプライベートな集団の間のKLダイバージェンスのための、通信効率の高いフェデレーテッド推定器であり、かつ形式的な例レベルの差分プライバシーを提供するものは、FedPriKLが最初であると主張している。

その重要性は、以下の能力にある：

1. ドリフト検出の実現: センシティブなユーザーデータを公開することなく、プラットフォームが分布の変化を検出し、モデルの再学習をトリガーするためのプライバシー保護メカニックを提供する。
2. 不可能性の克服: 問題を既知の公開リファレンスに限定することで、未知の分布のスケッチングに関する不可能定理を回避している。
3. ユーティリティとプライバシーのバランス: 信頼できるコンポーネントを介してノイズ注入ステップを集計後に移動させることで、ローカル摂動法に固有のバイアスを回避し、厳格なプライバシー制約下でも高いユーティリティを維持できることを示している。

著者らは、信頼できるアグリゲーター（またはTEE/SMC）への依存は実用的なトレードオフであり、セキュアハードウェアやマルチパーティ計算によって解消可能であると述べており、この信頼の仮定を取り除くことが今後の研究課題であるとしている。