技術的概要：ランダムシャッフルに基づくサブサンプリング付き DP-SGD のトレードオフ関数

問題定義

差分プライバシー付き確率的勾配降下法（DP-SGD）は、プライバシー制約下で深層学習モデルを訓練するための標準的なメカニズムである。$f$-差分プライバシー（$f$-DP）フレームワークは、偽陽性率と偽陰性率の間のトレードオフ関数を通じてプライバシー保証を可能な限り厳密に特徴づけるが、既存の分析は主にポアソンサブサンプリング（データ点が固定された確率でミニバッチに独立して含まれる場合）に焦点を当ててきた。

しかし、DP-SGD や確率的最適化の実用的な実装では、通常ランダムシャッフルが用いられる。これは、エポックごとにデータセットを一度だけ順列変換し、固定サイズのミニバッチに分割するものである。分析対象のアルゴリズム（ポアソン）と実装されたアルゴリズム（シャッフル）との間のこの不一致により、実世界のシステムのプライバシー保証は不正確に特徴づけられたままとなっている。シャッフルされた DP-SGD に関する先行研究は、明示的な敵対的イベントや数値評価を通じてトレードオフ関数の上限（プライバシー損失の下限）のみを提供しており、閉形式で透明な表現が欠けていた。さらに、最近の不可能性結果は、低ノイズ乗数（$\sigma \le 1/\sqrt{2 \ln M}$）の場合、トレードオフ関数が理想的なランダム推測の対角線（$1-a$）から証明的に離れて制限されることを示しているが、高ノイズ領域における振る舞いは、厳密な閉形式の分析を必要とする未解決の問題として残されていた。

手法

著者らは、$f$-DP フレームワーク内で、ランダムシャッフルを伴う DP-SGD のトレードオフ関数に関する厳密な閉形式の分析を導出した。手法は以下の段階を経て進められる。

1. 敵対者への帰着: 問題はスカラー仮説検定問題に帰着される。最悪ケースの敵対者モデル（単一の異なるレコードの寄与を分離できる）の下では、敵対者は $M$ ラウンドを観測する。帰無仮説（$H_0$）では、すべての観測は純粋なノイズ $N(0, 1)$ である。対立仮説（$H_1$）では、シャッフル順列によって均一にランダムに選ばれた正確に 1 ラウンドのみがシフトされた観測 $N(1/\sigma, 1)$ を含み、残りはノイズのままである。
2. 尤度比検定: ネイマン・ピアソンの補題により、最適な検定は尤度比を閾値処理するものであり、これは対数正規分布変数 $Y_j = \exp(X_j/\sigma - 1/(2\sigma^2))$（ただし $X_j \sim N(0, 1)$）の標本平均を閾値処理することに帰着される。
3. 非漸近分析（ベリー・エスéen）: 単一エポックについて、著者らはベリー・エスéenの定理を適用し、これらの対数正規分布変数の標本平均の正規分布への収束率を評価する。これにより、$\sigma \ge \sqrt{3/\ln M}$ の領域におけるトレードオフ関数 $f(a)$ に対する具体的で非漸近的な下限が得られる。この限界は $f(a) \ge 1 - a - \delta$ と表され、ここで $\delta$ はノイズ乗数 $\sigma$ とラウンド数 $M$ の明示的な関数である。
4. 漸近分析（エッジワース展開）: ベリー・エスéenの限界は $O(1/\sqrt{M})$ の誤差項によって制限されるため、著者らは 2 項エッジワース展開に基づく証明手法を導入してこれを改善する。中心極限定理のこの一般化により、対数正規分布変数の和の分布に関するより精緻な漸近推定が可能となる。このアプローチにより、エポック数 $E$ が $E = c_M^2 M$（ただし $c_M \to 0$）としてスケーリングする条件下で、$M \to \infty$ におけるトレードオフ関数の漸近的振る舞いが確立される。

主要な貢献

1. 単一エポックの閉形式下限: 本論文は、高ノイズ領域（$\sigma \ge \sqrt{3/\ln M}$）におけるシャッフルされた DP-SGD のトレードオフ関数に対する、最初の厳密な閉形式の下限を提供する。この限界は次式で与えられる。
   $$f(a) \ge 1 - a - \delta$$
   ここで $\delta$ は $\sigma$ と $M$ を用いて明示的に定義される（定理 4.1）。この結果は、ベリー・エスéenの証明フレームワーク内で定数因子まで厳密である。
2. 具体的なパラメータ推奨: 著者らは、意味のある差分プライバシーのための特定のパラメータ設定を導出した。単一エポック（$E=1$）で $\sigma=1$、$\delta=10^{-2}$ の場合、データセットサイズ $N \approx 1.14 \times 10^7$ を $M \approx 1.14 \times 10^6$ ラウンドに分割すれば十分であることを示した。これは、大規模なデータセットと単一エポックを伴う連合学習設定において、意味のあるプライバシーが達成可能であることを実証している。
3. 漸近的ガウス DP 特徴づけ: エッジワース展開を用いて、本論文は固定された $\sigma$ において、$M \to \infty$ かつ $E = c_M^2 M$（$c_M \to 0$）とするとき、$E$ 回合成されたトレードオフ関数がランダム推測の対角線（$1-a$）に一様に収束することを確立した。これは、単純な合成が示唆する線形 $O(E)$ のペナルティから、$E$ が $M$ と非線形にスケーリングする場合の漸近的 $O(\sqrt{E})$ の分離へと依存関係を改善する（系 5.3）。
4. ポアソンサブサンプリングとの比較: 著者らは、漸近結果を対応するポアソンサブサンプリングの漸近結果と比較した。その結果、低ノイズ限界（$\sigma \to 0$）において、ランダムシャッフルはポアソンサブサンプリングよりも理想的なランダム推測の対角線に漸近的に $\sqrt{2}$ 倍近いことが判明したが、高ノイズ限界（$\sigma \to \infty$）では両者の領域は同等になることが示された。

結果

• 領域の有効性: この分析は $\sigma \ge \sqrt{3/\ln M}$ に対して有効である。この領域は、$\sigma < 1/\sqrt{2 \ln M}$ においてトレードオフ関数が $1-a$ から離れて制限されることを示す Ertan と van Dijk [12] の不可能性結果と相補的である。これら二つの結果は、シャッフルされた DP-SGD のプライバシーの風景をマッピングする。
• 合成限界:
  • 非漸近的: 単一エポックの限界を反復すると $f^{\otimes E}(a) \ge (1-\delta)^E - a$ となり、プライバシー損失に対する $E$ への線形依存性を示唆する。
  • 漸近的: エッジワースに基づく分析は、より tight な依存性を示唆しており、対角線からの分離が $O(\mu E)$ ではなく $O(\mu \sqrt{E})$ としてスケーリングする。ただし、$E$ が $M$ と非線形にスケーリングすることが前提である。
• 実用的含意: 本論文は、シャッフルされた DP-SGD にとっての「実用的な絶好の地点」として単一エポック領域を特定している。クライアントが少数のエポックに参加する連合学習シナリオでは、現実的なデータセットサイズで意味のあるプライバシー保証（$\delta \approx 0.01$）が達成可能である。逆に、本論文は「多エポックの爆発」を指摘しており、線形合成限界の下で $E$ を増加させると、必要なデータセットサイズ $N$ が急速に非現実的になる（例えば、$E=100$ の場合 $N \sim 10^{11}$ が必要となるなど）ことを強調している。

意義と主張

本論文は、文献で分析されたアルゴリズム（ポアソン）と実務で展開されたアルゴリズム（ランダムシャッフル）との不一致を解決する厳密な閉形式の分析を提供すると主張している。透明で解釈可能な限界を導出することで、著者らは実務家が不透明な数値ツールに頼ることなく、パラメータ要件を直接読み取れるようにする。

この研究の意義は以下の点にある。

1. 理論と実践の架け橋: 機械学習フレームワークの標準であるランダムシャッフルが、厳密なプライバシー分析を許容し、低ノイズ領域ではポアソンサブサンプリングよりもしばしば有利であることを検証する。
2. プライバシー風景の定義: 既存の不可能性結果を補完し、シャッフルされた DP-SGD において意味のあるプライバシーに必要な正確なノイズ閾値を定義する。
3. パラメータ選択の指針: 特定のプライバシー予算を達成するための $M$、$N$、および $\sigma$ の選択に関する具体的な数式を提供し、特に連合学習アプリケーションに関連する。

著者らは将来の作業については控えめであり、漸近結果が複数エポックに対して改善された $\sqrt{E}$ 依存性を示唆しているものの、この依存性に関する具体的で閉形式の証明（漸近極限ではなく）の導出は未解決の問題であると指摘している。さらに、エッジワース展開における数列 $\delta_M$ と $\gamma_M$ を明示化して具体的な多エポック限界を得ることは、将来の研究の方向性として特定されている。