技術的サマリー：ランダム割当下における行列メカニズムのためのサンプリング不要なプライバシー会計

問題定義

本論文は、行列分解メカニズムとランダム割当（「ボールインビン」または平衡イテレーション部分サンプリング方式としても知られる）を組み合わせた微分プライバシーモデル学習において、厳密かつ確定的なプライバシー保証を計算する課題に取り組んでいる。

部分サンプリングによるプライバシー増幅は、微分プライバシー確率的勾配降下法（DP-SGD）におけるノイズ低減のための標準的な手法であるが、大規模学習においては計算効率と均一なデータカバレッジの観点から、ポアソン部分サンプリングよりも「ボールインビン」方式が好まれる。しかし、行列分解（イテレーション間で相関ノイズを導入して有用性を向上させる手法）と組み合わせる場合、既存のプライバシー会計手法には重大な限界が存在する：

1. モンテカルロ依存性: 最近のアプローチ（例：Choquette-Choo ら、2025）は、増幅パラメータを推定するためにモンテカルロサンプリングに依存している。このアプローチは計算コストが高く、特に高プライバシー領域では必要サンプル数が $\delta$ に反比例して増加するため（例、$(\epsilon, 10^{-8})$-DP の証明は $(\epsilon, 10^{-3})$-DP の $10^5$ 倍のコストがかかる）、特に高コストとなる。
2. 確率的保証: これらのサンプリングベースの手法は、高確率でしか成立しない保証を提供するか、あるいはメカニズムがランダムな棄却を採用することを要求するものであり、確定的な $(\epsilon, \delta)$-DP 上限を提供するものではない。
3. 計算的非実行性: ランダム割当下における行列メカニズムのプライバシー損失分布は、高次元の混合分布を含むため、サンプリングなしではホッケースティックダイバージェンスの正確な評価が非現実的である。

手法

著者は、ランダム割当方式の構造と行列分解によって導入される相関を利用し、確定的な上限を明示的に計算する、2 つの異なるサンプリング不要な会計手続きを提案する。

1. レーニーダイバージェンス会計（動的計画法）

この手法は、レーニーダイバージェンスの上限を計算し、それを標準的な変換定理を用いて $(\epsilon, \delta)$-DP に変換する。

• 核心的洞察: データセットからデータポイントが「削除」される方向におけるプライバシー損失分布は、戦略行列 $C$ から導出されたグラム行列 $G$ に関する和として表現できる。
• 計算量削減: 一般の行列の場合、この和の計算は #P-完全であることが証明されている。しかし、構造化された行列（例、戦略行列 $C$ が帯幅 $p$ を持つ帯行列）の場合、グラム行列 $G$ は周期的帯状の構造を継承する。
• アルゴリズム: 著者は、$p$-帯行列に対してこの和を正確に計算するための動的計画法アプローチを定式化した。
  • 計算量: 実行時間は、次数 $\alpha$ における指数関数的 $O(2^\alpha)$ から、多項式 $O(b p \alpha^{2p})$ に削減される（ここで $b$ はエポックあたりのバッチ数）。
  • 切り捨て: 厳密な帯行列ではないが急速に減衰する要素を持つ行列（例、帯状逆行列）の場合、この手法はグラム行列を切り捨て、計算可能な加法補正項を追加して上限の有効性を保証する。
• 追加方向: 「追加」方向については、算術平均 - 幾何平均（AM-GM）不等式を用いて、別の厳密な解析的上限が導出される。

2. 条件付き合成会計

この手法は、レーニー変換式が緩やかになり得る「小さな $\epsilon$」（高プライバシー）領域に対処する。ノイズの相関と固定された参加回数によって引き起こされるステップ間の依存関係を克服する。

• 概念: 独立したステップを仮定する代わりに、この手法は条件付き合成を使用する。ステップ $n$ におけるメカニズムの条件付き分布が、2 つの固定された分解分布 $(P^{(n)}, Q^{(n)})$ によって支配される「良い」結果を特定する。
• 悪い事象: この手法は、支配性が成立しない「悪い」結果を、その確率 $\delta_E$ を上限付けることで考慮する。総プライバシー損失は、独立したステップの合成と $\delta_E$ の和となる。
• 支配基準: 著者は、ガウス混合重みの逆ハザード関数に基づいた基準を導出した。事後逆ハザード関数が、ターゲット分布の逆ハザード関数より点ごとに小さい場合、支配性が成立することを示している。
• 尾部上限: 支配分布のパラメータを決定するために、著者は 3 値ガウス混合のプライバシー損失に関する解析的尾部上限を導出した。これらの上限を厳密化するため、変分族の分布を利用し、尾部上限の標準偏差を最小化するように温度パラメータを最適化する。
• 効率性: 初期評価は $O(N^2 b^2)$ であるが、異なるノイズ乗数 $\sigma$ に対する後続の評価は $O(N b^2)$ に償却可能であり、メカニズムの較正に対して効率的である。

主要な貢献

1. 確定的会計: 本論文は、ランダム割当下における行列メカニズムに対して、モンテカルロ推定を不要とする、確定的な $(\epsilon, \delta)$-DP 保証を計算する初のサンプリング不要な手法を導入する。
2. DP-SGD における計算量の改善: 相関のないノイズ（標準的な DP-SGD）という特殊な場合において、提案されたレーニー会計は、ランダム割当下での正確な会計の計算量を、指数関数的 $O(2^\alpha)$ から多項式 $O(b \alpha^2)$ に改善し、既存の正確な手法を大幅に凌駕する。
3. 相関ノイズへの一般化: この枠組みは、任意の帯状および非帯状行列メカニズム（帯状平方根、帯状逆行列、バッファ付き線形トイプリッツを含む）に拡張され、これらのメカニズムに固有の複雑なステップ間相関を処理する。
4. 二重領域での厳密性: レーニー会計（低プライバシー/大きな $\epsilon$ 領域で強力）と条件付き合成会計（高プライバシー/小さな $\epsilon$ 領域でより厳密）の組み合わせにより、包括的な会計ソリューションを提供する。

結果

著者は、さまざまな行列メカニズム（DP-SGD、BSR、BISR、BandMF、BandInvMF、BLT）および設定（単一エポックおよび複数エポック）において、最先端のモンテカルロ会計との手法を評価した。

• 精度: 低プライバシー領域（$\epsilon \ge 2$）では、レーニー会計はモンテカルロ参照と密接に一致する。高プライバシー領域（$\epsilon \le 1$）では、条件付き合成会計がより厳密な上限を提供し、モンテカルロ推定と比較してより小さな較正済みノイズ乗数 $\sigma$ を可能にする。
• 頑健性: 性能は、異なる帯幅（$p$）およびバッチ数（$b$）において維持される。
• 有用性: CIFAR-10 に関する実験により、これらのサンプリング不要な保証から導出されたノイズ乗数が、相関ノイズを使用することによる有用性の利益を維持することが示された。
• 実行時間: これらの手法は、モンテカルロサンプリングの $O(\delta^{-1})$ 依存性を克服する。条件付き合成会計は大きな $N$ に対して初期コストが高いが、厳格なプライバシー予算における較正のための償却コストは、モンテカルロに比べて大幅に低い。

意義と主張

本論文は、相関する勾配と参加を持つメカニズムに対する初のサンプリング不要なプライバシー会計を提供すると主張している。その意義は以下の点にある：

• 確定的保証の実現: 確率的な上限やランダムな棄却への依存を排除する。これらは生産システムにおいて実用的でないか、理論的に弱いとされることが多い。
• スケーラビリティ: ランダム割当に対する正確なレーニー会計の計算量を指数関数的から多項式的に削減することで、モンテカルロサンプリングが計算的に不可能となる大規模学習実行においても、正確なプライバシー会計を可能にする。
• 実用的な較正: 広範な $\epsilon$ と $\delta$ にわたって厳密な上限を効率的に計算できる能力は、ノイズ乗数のより良い較正を促進し、微分プライバシー深層学習における有用性とプライバシーのトレードオフを直接改善する。

著者は限界を認めており、レーニー会計の計算量は帯幅 $p$ に対して指数関数的（ただし $\alpha$ に対しては多項式的）であること、および条件付き合成手法が結果の粗い分割に依存しており悲観的である可能性があることを指摘している。将来の研究としては、より微細な分割や、上限をさらに厳密化するためのより効率的な変分推論の探求が提案されている。