技術要約：バイレベル最適化における条件数依存性について

問題設定

本論文は、一次手法を用いたバイレベル最適化問題における $\epsilon$-停留点の探索に関するオラクル計算量について調査している。検討されている具体的な設定は、以下の非凸・強凸（NC-SC）バイレベル最適化である：
$$\min_{x \in \mathbb{R}^{d_x}} F(x) = f(x, y^*(x)), \quad \text{ただし} \quad y^*(x) = \arg\min_{y \in \mathbb{R}^{d_y}} g(x, y).$$
ここで、上層の目的関数 $f$ は非凸であり、下層の目的関数 $g$ は $y$ に関して強凸である。主な課題は、収束レートが下層問題の条件数 $\kappa_y = L_1/\mu_y$ （ここで $L_1$ は滑らかさの定数、$\mu_y$ は強凸性の定数）およびグローバルな条件数 $\bar{\kappa}_y$ にどのように依存するかという点にある。

近年の研究では、決定論的な平滑問題に対して $\tilde{O}(\bar{\kappa}_y^4 \epsilon^{-2})$ または改善された $\tilde{O}(\bar{\kappa}_y^{7/2} \epsilon^{-2})$ という上界が確立されているが、条件数に対する最適な依存性は依然として不明である。具体的には、バイレベル問題が、条件数依存性に関してミニマックス問題（$f = -g$ の場合）よりも本質的に難しいことが証明可能であるかどうかは分かっていない。なお、ミニマックス問題は $\Omega(\sqrt{\kappa_y}\epsilon^{-2})$ の下界を持つ。

手法

著者らは、最適化の下界理論で広く用いられている手法である**ゼロチェーン（zero-chain）**構造に基づいた「困難なインスタンス」を構築することで、新たな下界を確立している。

1. 困難なインスタンスの構築:
   核心となる革新は、NC-SC ミニマックス問題で使用される連鎖状の困難なインスタンスの修正である。著者らは、変数の依存関係を増幅させるために、以下の2つの特定の変数を利用した構成を導入している：

   • 結合変数（coupling variable） $y$ （下層において）：$y^*(x)$ を計算する複雑さを捉える。
   • 再スケーリング変数（rescaling variable） $z$ （上層から下層へ移動）：ハイパー目的関数 $F(x)$ の滑らかさにおける依存性を捉える。
   • メカニズム: 変数 $x, z, y$ 間の接続を注意深く設計し、$x$ ではなく $z$ に非凸正則化を加えることで、上層における実効的なチェーンの長さが $\kappa_y$ に関連する因子によってスケールされるシナリオを作り出している。具体的には、ハイパー目的関数は、$K = \Omega(\sqrt{\kappa_y})$ における非凸ゼロチェーンとして評価される $K^2 x$ に等価となる。

2. アルゴリズムのクラス:
   下界は以下のクラスに適用されることが証明されている：

   • 決定論的一次アルゴリズム: 勾配 $\nabla f$ および $\nabla g$ にアクセスするもの。
   • HVPベースのアルゴリズム: ヘッセ行列・ベクトル積（HVP）にアクセスするもの。著者らは、二次形式の下層関数において、HVPオラクルは情報アクセスにおいて一次オラクルと同等であることを証明しており、したがって下界は両方のクラスに適用される。
   • 確率的アルゴリズム: ノイズと分散を扱うために、ランダム化されたゼロチェーンを用いた別の構成を使用している。

主な貢献と結果

1. 決定論的 NC-SC 下界

本論文は、条件数依存性に関して、バイレベル問題とミニマックス問題の間の最初の証明可能なギャップを確立した。

• 一次平滑 ($p=1$): $\Omega(\kappa_y^{5/2} \epsilon^{-2})$。これは、ミニマックスの下界である $\Omega(\sqrt{\kappa_y}\epsilon^{-2})$ を上回るものである。
• 二次平滑 ($p=2$): $\Omega(\kappa_y^{31/14} \epsilon^{-12/7})$。
• 任意次平滑 ($p \ge 3$): $\Omega(\kappa_y^{21/10} \epsilon^{-8/5})$。

2. 凸および強凸の設定

著者らは、ハイパー目的関数が凸または強凸である設定にも結果を拡張している：

• 凸・強凸 (C-SC): 従来の $\tilde{\Omega}(\min\{\kappa_y, \epsilon^{-3/2}\}/\sqrt{\epsilon})$ から $\Omega(\kappa_y^{3/2}/\sqrt{\epsilon})$ へと改善。
• 強凸・強凸 (SC-SC): $\tilde{\Omega}(\kappa_y \sqrt{\kappa_x})$ から $\tilde{\Omega}(\kappa_y^{3/2} \sqrt{\kappa_x})$ へと改善。

3. 確率的 NC-SC 下界

ノイズを含む勾配を用いた確率的問題について：

• 下界: $\Omega(\kappa_y^4 \epsilon^{-4})$ （分散項によって支配される）。
• 洞察: 著者らは、確率的設定においては、再スケーリング変数によって増幅された**分散（variance）**が、バイアス（結合変数によって捉えられるもの）よりも根本的なボトルネックであると主張している。これにより、バイアスに焦点を当てた同時期の研究と比較して、大幅にタイトな下界が得られている。

4. 洗練された上界

下界を文脈化するために、著者らは内側ループ（下層ソルバー）にネステロフの加速（Nesterov acceleration）を適用することで、既存の上界を洗練させている：

• 一次平滑の決定論的問題については、上界は $\tilde{O}(\bar{\kappa}_y^{7/2} \epsilon^{-2})$ に、下層関数が二次形式である場合は $\tilde{O}(\kappa_y^{5/2} \epsilon^{-2})$ に洗練される。
• これにより、二次形式の下層関数を持つ設定において、上界と下界の間のギャップは、小さな多項式因子または小さな対数多項式因子まで縮小され、これらの設定における近最適性が示唆されている。

意義と主張

本論文は、条件数依存性の観点から、バイレベル最適化とミニマックス最適化の複雑性の間の最初の証明可能な分離を提供したと主張している。

• 根本的な困難さ: 結果は、バイレベル問題がミニマックス問題よりも証明可能なほど困難であることを示している。$\kappa_y$ への依存性の増大（例：$\kappa_y^{5/2}$ 対 $\sqrt{\kappa_y}$）は、バイレベル構造そのもの、特に下層の解計算と上層の滑らかさの相互作用に由来する根本的な困難さを反映している。
• 分散 vs バイアス: 確率的設定において、本研究は分散を収束速度の主要な制限要因として特定しており、なぜ確率的バイレベル最適化が困難であるのかについて新しい視点を提供している。
• タイトさ: 二次形式の下層関数に対して、確立された下界はほぼ最適であることが示されている。これは、洗練された上界が小さな因子を除いて下界と一致するためである。

著者らは、彼らの下界は二次形式の下層関数に対してはタイトであるが、一般的な非二次形式の関数に対してよりタイトな下界を確立することは今後の課題であると述べている。また、高次の平滑性を持つランダム化アルゴリズムや、平均二乗平滑性などの他の問題設定への確率的下界の拡張についても、未解決の課題として残している。