技術要約：f-Differential Privacyのための逐次監査

問題定義

差分プライバシー（DP）は、データ処理におけるプライバシーを定量化するための標準的な手法であるが、特定のアルゴリズムの実装がその理論的保証に従っているかを検証することは依然として重要な課題である。既存の経験的な監査手法は、通常、従来の$(\varepsilon, \delta)$-DP概念を対象とした固定サンプル（バッチ）手順に依存している。これらのアプローチには、主に2つの制限がある：

1. 非効率性： 事前にサンプルサイズを指定する必要がある。テストを行う前に「効果量」（プライバシー侵害の大きさ）が未知であるため、実務者は結果が不確定になることを避けるために、過度に大きなサンプルサイズを選択せざるを得ない。これは、DP-SGDのような計算コストの高い学習手順において、禁止的な計算コストを招く。
2. 表現力の限定： $(\varepsilon, \delta)$フレームワークはプライバシーの「局所的」な視点を提供するものであり、プライバシーとユーティリティの間の完全なトレードオフ・スペクトラムを捉えることはできない。対照的に、$f$-Differential Privacy ($f$-DP) は、単一のトレードオフ曲線を通じてプライバシー挙動全体を特徴付けることができ、統計的テストに適しており、現代的なメカニズムであるDP-SGDにより適している。

最近の研究では$(\varepsilon, \delta)$-DPに対する逐次テストが導入されているが、$f$-DPフレームワークにおいて、厳密な統計的保証を維持しながらサンプルサイズを適応的に決定できる逐次的監査器は不足している。

手法

著者らは、$f$-DPのための逐次的監査フレームワークであるAPT (Advanced Privacy Testing) を提案する。核心となるアイデアは、固定されたバッチサイズを使用するのではなく、決定（違反または違反なし）が統計的有意性を持って下されるまで、適応的にサンプルを収集することである。

1. 逐次的テスト・フレームワーク

監査者は問題を以下の仮説検定として定式化する：

• $H_0$： メカニズムは主張された$f$-DP曲線$f$を満たしている（すなわち、すべての$\alpha$に対してトレードオフ関数$T(\alpha) \geq f(\alpha)$）。
• $H_1$： メカニズムは主張に違反している（すなわち、$\exists \alpha^*$ s.t. $T(\alpha^*) < f(\alpha^*)$）。

素朴な逐次アプローチ（固定サンプルテストを繰り返し適用し、偽の棄却率を増大させるもの）とは異なり、APTは随時妥当な推論（anytime-valid inference）を採用する。これは、経験的な分類エラー$(\hat{\alpha}, \hat{\beta})$に基づいた逐次的テスト統計量を構築し、それをガウス近似理論（具体的にはブラウン運動の挙動）から導出された境界関数と比較するものである。これにより、サンプルサイズが無限に増大しても、誤棄却率（有意水準$\gamma$）が制御されることが保証される。

2. 分類器の構築

トレードオフ関数を推定するために、監査者は出力分布$P$（データセット$D$から）と$Q$（隣接するデータセット$D'$から）を区別するための分類器$\phi$を必要とする。本フレームワークは以下の両方をサポートする：

• ホワイトボックス設定： 解析者はメカニズムのパラメータ（例：ノイズ分布）を知っている。パラメトリックな尤度比分類器（例：ガウス閾値判定）が使用される。
• ブラックボックス設定： 入出力へのアクセスのみが可能である。監査者は**カーネル密度推定（KDE）**を用いて$P$と$Q$の密度を近似し、摂動を加えた尤度比分類器を構築する。

3. 最適な閾値チューニング

分類器の最適な閾値$\eta$を選択することは極めて重要な要素である。著者らは、推定されたエラーペア$(\hat{\alpha}, \hat{\beta})$と、45度線に沿った主張された曲線$f$との間のユークリッド距離を最大化するように$\eta$を選択する新しい幾何学的戦略（式8）を提案している。これは、従来の垂直距離ベースの選択ルールよりも検出力が高いことが示されている。

4. アルゴリズムの流れ

APTアルゴリズム（アルゴリズム1）は以下のように進行する：

1. バーンイン（Burn-in）： パラメータを較正し、初期の分類器を構築するために、少量の初期サンプルを抽出する。
2. 逐次的ループ： 新しいサンプル$(X_k, Y_k)$を反復的に抽出する。
3. 更新： （ブラックボックスモードの場合）分類器を定期的に更新し、分類エラーを再推定する。
4. 決定： 推定されたエラーが主張された曲線$f$を大幅に下回っているかどうかを確認するために、信頼区間調整済み推定器を適用する。境界を越えた場合、アルゴリズムは停止し、違反を報告する。

主な貢献

1. 初の逐次的 $f$-DP 監査器： 本論文は、ホワイトボックスおよびブラックボックスの両方の設定をサポートする、$f$-DPの主張を逐的にテストできる初の監査器を提示している。
2. 理論的保証： 著者らは、以下のことを示す証明（定理3.1）を提供している：
   • 誤棄却率は、（サンプルサイズが無限であっても）ユーザーが指定した$\gamma$によって抑えられる。
   • 違反を検出するために必要なサンプルサイズは、既知の効果量を持つ固定サンプルテストによって必要とされる理論的最小値の対数因子以内にあり、ほぼ最適である。
3. 改良された分類器チューニング： 既存の固定バッチ法よりも検出力を向上させる、最適な分類器閾値を選択するための新しい幾何学的戦略。
4. オープンソース実装： 著者らは、結果を再現し、監査器を適用するためのコードを含む公開リポジトリを提供している。

実験結果

著者らは、合成ベンチマーク（ガウスおよびラプラス・メカニズム）および実世界のDP-SGDシナリオにおいてAPTを評価した。

• サンプル効率： 制御された実験において、APTは固定バッチのベースラインよりも大幅に少ないサンプルで違反を検出した。強い違反の場合、検出はしばしば数百サンプル以内で発生した。
• 先行研究との比較： 本論文は、加法的ノイズベンチマークにおいて、最近の逐次的$(\varepsilon, \delta)$-DP監査器[22]とAPTを比較している。
  • 小さい$\varepsilon$の領域では、バギーなメカニズムを棄却するために、APTは[22]が報告したサンプルの約**10%〜25%**のサンプルしか必要としなかった。
  • 大きい$\varepsilon$の領域では、[22]で使用されているMMDベースのサロゲートは、テストマージンが消失する「飽和効果」に苦しみ、検出失敗を引き起こす。APTは、このサロゲートに依存していないため、より広い範囲のプライバシーパラメータに対して効果的であり続ける。
• 実世界のDP-SGD： CIFAR-10における「ワンラン（one-run）」監査シナリオにおいて、逐次的なアプローチは、明確な違反に対して、決定に至るために必要なカナリスコアの数が、全セットに対して固定バッチテストを実行する場合と比較して、劇的に減少すること（数千から数百へ）を示した。

意義と主張

本論文は、APTが、事前に指定された（しばしば過剰な）サンプルサイズを排除することにより、プライバシー監査における計算上のボトルネックを解決することを主張している。$f$-DPに焦点を当て、逐次的テストを利用することで、以下のことが可能になる：

• コスト削減： 特に、訓練や大量のカナリスコアリングが困難なDP-SGDのような高コストなメカニズムにおいて有益である。
• 厳密な制御： 素朴な逐次的テストに伴う「覗き見（peeking）」のペナルティを受けることなく、厳格な統計的有意性の保証を維持する。
• 適応性： 大きな違反を迅速に検出できる一方で、微細な違反に対しては必要な限りサンプリングを継続できる。

著者らは、本研究が既存の監査ツールを補完することを目的としており、あらゆる$f$-DP監査器に適用してサンプル効率を向上させることができる汎用的な逐次的ラッパーを提供することを強調している。また、[22]との比較は、両者が異なるプライバシー対象を監査しているため、普遍的な優位性を主張するものではなく、特定の関連する領域における優れた効率性を示すものであることを明記している。