技術要約：プライベート・オラクルを用いたプライベート最適化の勾配複雑性について

問題設定

本論文は、リプシッツ連続な凸損失関数における、差分プライバシー（DP）を満たす経験的リスク最小化（ERM）および確率的凸最適化（SCO）のオラクル複雑性（ファーストオーダー・オラクル・クエリによる実行時間の測定）を調査している。著者らは、以下の2つの異なる設定に焦力している：

1. プライベート・オラクルを伴う非平滑損失： 最適化器は、「プロキシ・オラクル」と相互作用する。このオラクルは、ミニバッチの勾配を処理し、差分プライバシー（具体的には $\rho$-zCDP）を満たすメッセージを返す。これは、勾配が送信前に摂動されるDP-SGDのような一般的な慣行をモデル化している。
2. プライベート・オプティマイザを伴う平滑損失： 内部のオラクル・メカニズムにプライバシーを要求せず、最終的な最適化手順が $(\epsilon, \delta)$-DPを満たすことのみを要求するという緩和された仮定である。

主な目的は、過剰リスク $\alpha$ を達成するために必要な勾配クエリの数に対する下界を確立することであり、特にプライバシー制約と次元数 $d$ が、非プライベートな場合と比較してランタイムにどのように影響するかを分析することである。

手法

著者らは、「ベクトル発見（vector discovery）」と情報理論的な下界手法のハイブリッドを採用している。

ハードな問題の構成

下界の核心は、ネミロフスキーの関数から着想を得て、正則化項を加えた特定の損失関数の構成に基づいている。損失は以下のように定義される：
$$L(w) = \max \left\{ \max_{k \in [K]} \{ |\langle w, X_k \rangle - \alpha| \}, \| \Pi_V w \| \right\}$$
ここで：

• $X_1, \dots, X_K$ は $\mathbb{R}^d$ におけるランダムな正規直交ベクトルである。
• $V$ は $\{X_k\}$ のスパンに直交するランダムな部分空間である。
• $\Pi_V$ は $V$ への直交射影である。
• この損失は、ERMの設定において $n$ 回複製される。

情報理論的分析

証明戦略は、この損失を最小化するためには、最適化器が各ベクトル $X_k$ を「発見」しなければならないことを示すことにある。しかし、標準的なベクトル発見ではベクトルを観測することが十分であるが、ここではプライバシー制約にもかかわらず、各 $X_k$ について高い相互情報量を得なければならない。

• 相互情報量の追跡： 著者らは、条件付き相互情報量の和 $\sum I(X_k; W | X_{\neq k}, V)$ （ここで $W$ は出力解）を追跡する。彼らは、他のベクトルが既知であっても、$X_k$ を推定することは依然として高次元の問題であることを主張している。
• プライバシー制約： プライベート・オラクルについて、著者らは $\rho$-zCDPとグループ・プライバシーの特性を用いて、$X_k$ に関して漏洩する情報の量を制限する。彼らは、最適化器が $V$ を学習するために $\Omega(d)$ 回のクエリを行わない限り、ペナルティのない部分空間を利用して $X_k$ を推定することはできないことを示している。
• 情報制限付きオラクル： この手法は、情報容量 $\Gamma$ （ビット）が制限されたオラクルにも拡張され、最適化器が勾配に関する十分な情報を蓄積するために、十分に多くのオラクル・クエリを行う必要があることを示している。

主な貢献と結果

1. プライベート・オラクルを伴う非平滑最適化

次元 $d \geq 1/\alpha^2$ に対して、$\rho$-zCDPプロキシ・オラクルと相互作用するあらゆる最適化器は、以下の期待実行時間を必要とすることを本論文は確立している：
$$\Omega\left( \min\left\{ \frac{\sqrt{d}}{\alpha^2 \sqrt{\rho}} + \frac{d}{\bar{m}\rho}, \frac{d}{\log(1/\alpha)} \right\} \right)$$
ここで $\bar{m}$ は最大ミニバッチサイズである。

• タイト性： この下界は、$d \geq 1/\alpha^4$ のレジームにおいて、DP-SGDの解析を通じて（対数因子を除いて）タイトであることが示されている。
• バッチサイズのインパクト： この結果は、プライベートな学習ダイナミクスにおける小さなバッチサイズ（$\bar{m}$）の負の影響を明示的に特徴付けている。もし $\bar{m} < \sqrt{d}$ であれば、ランタイムのペナルティが増大する。
• DP-SGDへの系： バッチサイズ $m$ を持つDP-SGDの場合、ランタイムは $\Omega(\min\{ \frac{\sqrt{d} + d/m}{\alpha^2}, \frac{d}{m \log(1/\alpha)} \})$ となる。

2. 情報制限付きオラクルを伴う非平滑最適化

証明手法を拡張することで、プロキシ・オラクルが勾配に関する情報を最大 $\Gamma$ ビットしか送信しない場合、必要なオラクル呼び出し回数は以下の通りであることを示している：
$$\Omega\left( \min\left\{ \frac{d}{\alpha^2 \Gamma}, \frac{d}{\log(1/\alpha)} \right\} \right)$$
この結果は、勾配の量子化技術の根本的な限界を浮き彫りにしており、最適化器が成功するためには勾配情報の「全体」を効果的に使用しなければならないことを示している。

3. プライベート・オプティマイザを伴う平滑最適化

（オラクルではなく）最終的な最適化器のみが $(\epsilon, \delta)$-DPを満たすことが要求される平滑損失の場合、著者らは期待オラクル呼び出し回数の下界を次のように証明している：
$$\tilde{\Omega}\left( \frac{\sqrt{d}}{\alpha} + \min\left\{ \frac{1}{\alpha^2}, n \right\} \right)$$

• プライバシー独立性： 特筆すべきは、この下界は（$\alpha$ が固定されている場合）、プライバシーパラメータ $\epsilon$ に依存しないことである。著者らは、より強力なプライバシー保証は、最小達成可能な精度（$\alpha^*_{\epsilon, \delta}$）には影響を与えるが、目標精度が固定されている場合のランタイムコストには影響を与えないと主張している。
• タイト性： 既存のアルゴリズム（Phased SGD）の修正により、この下界はほぼタイトであることが示されている。

4. ERMとSCOの間の簡約

本論文は、ランタイムとプライバシーにおいて $\text{polylog}(n)$ のオーバーヘッドのみを伴う簡約を通じて、DP-SCOは（多項式対数因子の範囲内で）DP-ERMよりも困難ではないことを示している。これは、DP-ERMの複雑性を特徴付けることが、ほとんどのレジームにおいてDP-SCOを理解するのに十分であることを意味する。

意義と主張

著者らは、ローカル・プライバシー・モデルを超えて差分プライバシーを活用した、最初のオラクル複雑性の下界を提供する研究として本研究を位置づけている。

• ランタイムのペナルティ： これらの結果は、プライベートな最適化器のクラス（プライベート・オラクルを使用するもの）が、非プライベートな最適化器と比較して、次元に依存したランタイム・ペナルティを受けることを形式的に示している。非プライベートな設定では、非平滑関数の複雑性は $\Theta(1/\alpha^2)$ であるが、プライベートな設定では、レジームに応じて $\sqrt{d}$ または $d$ の因子が導入される。
• 実用的な関連性： プライベート・オラクル・モデルは、信頼できないサーバーがノードに対して勾配を要求する、フェデレーテッドラーニングや分散学習などの実用的なシナリオによって動機付けられている。これらの知見は、プライバシー増幅のために頻繁に使用される小さなバッチサイズが、高次元においてランタイム性能を根本的に低下させることを示唆している。
• 量子化の限界： 情報制限付きオラクルの結果は、勾配量子化技術の限界に対する理論的な裏付けを提供しており、勾配をある閾値以下に圧縮すると、クエリ回数の比例的な増加を余儀なくされることを示している。

本論文は、アルゴリズムの進歩によって上界は改善されてきたものの、オラクル複雑性の観点におけるプライバシーの根本的なコストは今やより明確に特徴付けられており、これまで中央DPモデルにおいて完全には理解されていなかった、次元数、バッチサイズ、およびプライバシーの間のトレードオフが明らかになったと結論付けている。