Privacy Amplification in Differentially Private Zeroth-Order Optimization with Hidden States

「隠れ状態を伴う微分プライバシーゼロ次最適化におけるプライバシー増幅」の論文の詳細な技術的概要を以下に示します。

1. 問題定義

本論文は、厳格なメモリ制約を管理しながら**微分プライバシー（DP）**制約下で大規模モデル（例：LLM）を学習するという課題に取り組んでいます。

• 背景: 標準的な一次微分プライバシー手法（DP-SGD など）は、逆伝播中にサンプルごとの勾配を保存する必要があり、モデルサイズに伴って悪化する巨大なメモリオーバーヘッドを引き起こします。
• 解決策の潮流: ゼロ次最適化（ZO）手法は、明示的な勾配を計算せず、前方伝播（損失評価）のみを必要とするため、メモリ効率の高い代替手段として登場しました。
• ギャップ: 既存の ZO 手法（例：DPZero）は経験的にはよく機能しますが、その理論的プライバシー分析は標準的な合成定理に依存しています。その結果、プライバシーコストはトレーニングステップ数（$T$）に対して線形に増加し、有用性とプライバシーの間のトレードオフを強いられます。
• 核心的な課題: 一次手法に対して収束する（一定の）プライバシー境界をもたらす**反復によるプライバシー増幅（PABI）**という技術を、ゼロ次手法へ拡張することです。
  • なぜ難しいか: 一次 PABI は、勾配に等方的（方向非依存）なガウスノイズを加えることに依存しており、「シフト・レーニィ・ダイバージェンス」補題の使用を可能にします。一方、効率的な ZO 手法は、ランダムな更新方向に沿って異方的（方向依存）なスカラーノイズを加えます。この異方性が、標準的なシフト・ダイバージェンス・フレームワークに必要な大域的リプシッツ性質を破るため、既存の PABI ツールは適用不可能となります。

2. 手法

著者らは、標準的な分析の限界を回避するために、ハイブリッドノイズ機構とカップリング分析を組み合わせた新しいフレームワークを提案します。

A. ハイブリッドノイズ機構（Noisy-ZOGD）

純粋な方向ノイズ（効率的だが分析が困難）か、純粋な等方ノイズ（分析が容易だが有用性を浪費する）のどちらかを選ぶのではなく、著者らは統一的な更新則を提案します：
$$w_{t+1} = \Pi_{\mathcal{B}_R} \left[ w_t - \frac{\eta}{K} \sum_{k=1}^K \hat{g}_t(w_t; u_{t,k}) + \frac{\eta}{\sqrt{K}} \sum_{k=1}^K G^{(1)}_{t,k} u_{t,k} + \eta \sqrt{d} G^{(2)}_t \right]$$

• $K$ 次元更新: 勾配推定分散を低減するために、各ステップで $K$ 個のランダムな方向を使用します。
• ハイブリッドノイズ:
  1. 方向ノイズ（$G^{(1)}$）: 更新方向 $u_{t,k}$ に沿って加えられるスカラーガウスノイズです。これは感度が存在する箇所にノイズを集中させることで有用性を維持します。
  2. 等方ノイズ（$G^{(2)}$）: 全次元にわたって加えられる小さな等方的ガウスノイズです。これはカップリング過程における「シフト」を処理するための理論的分析に不可欠です。
• 正規直交方向: 更新方向 $\{u_{t,k}\}$ は、独立同一分布（i.i.d.）のランダムベクトルではなく、シュティエフェル多様体から正規直交集合としてサンプリングされ、これによりプライバシー境界が厳密化されます。

B. 新規カップリング分析（シフト・ダイバージェンスの回避）

標準的な PABI 証明は、大域的リプシッツ条件を必要とするシフト・レーニィ・ダイバージェンス補題に依存しています。ZO 更新写像は大域的にリプシッツではない（高い確率で点ごとのリプシッツであるのみ）ため、著者らはカップリングされた補助過程 $\tilde{W}_t$ を構築します：

1. 構築: 隣接する 2 つのトレーニング過程（データセット $D$ 上の $W_t$ とデータセット $D'$ 上の $W'_t$）の「中間」に位置する補助軌道 $\tilde{W}_t$ を定義します。
2. 分解: プライバシー分析は 2 つの部分に分割されます：
   • 全変動（TV）境界: カップリングが失敗する（すなわち、$W_t$ と $\tilde{W}_t$ が発散する）確率を測定します。これは ZO 更新の点ごとのリプシッツ性質（高い確率で成り立つ）を用いて境界付けられます。
   • レーニィ・ダイバージェンス境界: 補助過程 $\tilde{W}_t$ と隣接過程 $W'_t$ の間の発散を測定します。$\tilde{W}_t$ はノイズ構造と整合するように構築されているため、この部分は標準的なシフト・ガウス機構を用いて分析可能です。
3. 結果: このアプローチは大域的リプシッツ定数を必要とせず、異方的ノイズであっても収束するプライバシー境界を可能にします。

3. 主要な貢献

1. ゼロ次における最初の収束する PABI: 本論文は、隠れ状態を伴うゼロ次最適化が $T$ に対して線形に増加するのではなく、収束するプライバシー境界（一定のステップ数後にプライバシーコストが飽和する）を達成することを示す、最初の理論的証明を提供します。
2. ハイブリッドノイズ機構: 有用性（方向ノイズを通じて）と分析的な取り扱いやすさ（小さな等方成分を通じて）のバランスを取るノイズ注入方式を導入します。
3. 更新次元（$K$）の役割:
   • 隠れ状態分析の下では、更新方向の数 $K$ を増やすことがプライバシー損失を低減することを明らかにします（$K$ がコストを増加させるという標準的な合成分析とは対照的です）。
   • 正規直交更新方向を使用することが、i.i.d. ランダム方向と比較してプライバシー境界を大幅に改善することを示します。
4. 新規カップリング手法: 大域的リプシッツの障壁を迂回する特定の補助過程構築を開発しました。これは、他の非滑らかまたは非リプシッツな最適化設定にも適用可能な可能性のある手法です。

4. 主要な結果

• プライバシー境界: 滑らかで強凸な損失関数に対して、提案された Noisy-ZOGD アルゴリズムは以下の $(\epsilon, \delta)$-DP を満たします：
  $$\epsilon = O\left( \sqrt{\frac{\Delta^2 \log(1/\delta)}{n^2 \sigma^2} \min\left(T, \frac{R n \sqrt{d}}{K \Delta}\right)} \right)$$
  • この境界は $T \approx \frac{R n \sqrt{d}}{K \Delta}$ で飽和し、それ以上の反復はプライバシーコストを増加させません。
  • この境界は $K$ に反比例しており、より多くの方向を使用することがプライバシーを改善することを示しています。
• 比較:
  • 標準的な合成との比較: 標準的な分析は $\epsilon \propto \sqrt{T}$ を生み出し、無制限に増加します。提案手法は収束します。
  • 出力摂動との比較: 出力摂動（最終段階でのみノイズを加える）は $T$ に依存しませんが、実用的な $T$ に対しては一般的に弱くなります。提案手法は中間的な $T$ に対してより tight な境界を提供します。
• 有用性: ハイブリッドノイズ機構は、総ノイズ分散が保存されるため、純粋な方向ノイズ（DPZero）と同じ有用性の保証を維持します。

5. 意義

• スケーラビリティ: この研究は、メモリが限られた DP 条件下で数十億パラメータの巨大モデルを学習するための理論的根拠を提供し、現在の LLM 微調整における重要なボトルネックを解決します。
• アルゴリズム設計: 複数のゼロ次方向（$K > 1$）を使用することは純粋な有用性のトレードオフであるという信念を覆します。本論文は、それがプライバシー上の利益でもあることを証明し、DP-ZO アルゴリズムにおける高次元更新の使用を促します。
• 理論的進展: PABI における「異方的ノイズ」の問題を解決することで、一次およびゼロ次プライバシー理論の間の重要なギャップを埋め、プライバシー制約下での複雑な非リプシッツ最適化ダイナミクスを分析するための新しいツールキット（補助過程を伴うカップリング）を提供します。
• 実用的影響: 実践者への具体的な指針を提供します：正規直交方向を使用し、ハイブリッドノイズパラメータ $\beta_t$ を調整し、メモリコストを増やすことなくより良いプライバシー - 有用性のトレードオフを達成するためにより大きな $K$ を活用します。