Extragradient methods with complexity guarantees for hierarchical variational inequalities

技術要約：階層的変分不等式における複雑性保証を伴うエクストラグラディエント法

問題定式化
本論文は、実可分ヒルベルト空間 $Z$ における階層的平衡問題の解決に取り組む。核心となる目的は、別の階層的変分不等式（HVI）の解集合上で定義される半変分不等式（HVI）の解 $z^*$ を見つけることである。形式的には、問題 (P) は、$S_2$ のすべての $z$ に対して以下を満たす $z^* \in S_2$ を見つけることである：
$$\langle F_1(z^*), z - z^* \rangle + \ell_1(z) - \ell_1(z^*) \geq 0 \quad \forall z \in S_2$$
ここで、$S_2 = \text{zer}(F_2 + \partial \ell_2)$ は下位レベルの HVI の解集合である。ここで、$F_1, F_2$ は単調作用素であり、$\ell_1, \ell_2$ は、適切、凸、かつ下半連続な関数である。

この定式化は、以下の問題クラスを統合するものである：

• 単純なバイレベル最適化（$\ell_1, \ell_2$ が滑らかな場合、または合成項の場合）。
• 入れ子状の変分不等式（$\ell_1=0$ かつ $\ell_2$ が指示関数である場合）。
• 階層的な結合凸型一般化ナッシュ均衡問題（GNEP）。
• 変分不等式制約下における最適制御。

手法
著者らは、ティコノフ正則化に基づく楽観的エクストラグラディエント法（アルゴリズム1）を提案している。従来の（標準的なエクストラグラディエントのような）ダブル演算評価を必要とする手法とは異なり、本手法は「過去」の演算評価を利用することで、計算コストを1イテレーションあたり1回の演算評価へと削減している。

アルゴリズムは、正則化演算子 $V_k = F_2 + \sigma_k F_1$ および正則化関数 $G_k = \ell_2 + \sigma_k \ell_1$ を構成する。ここで、$(\sigma_k)$ はゼロに収束する減少する正則化列である。イテレーション・スキームは以下の通りである：

1. 予測 (Prediction): $z_{k+1/2} = \text{prox}_{t_k G_k}(z_k - t_k (F_2(z_{k-1/2}) + \sigma_k F_1(z_{k-1/2})))$
2. 修正 (Correction): $z_{k+1} = \text{prox}_{t_k G_k}(z_k - t_k (F_2(z_{k+1/2}) + \sigma_k F_1(z_{k+1/2})))$

解析は、以下の特定の幾何学的仮定に基づいている：

• 弱鋭鋭性 (Weak Sharpness): 下位レベルの解集合 $S_2$ は、ギャップ関数と解集合への距離を結びつける $(\alpha, \rho)$-弱鋭鋭性条件を満たすと仮定されている。
• Attouch-Czarnecki 条件: イテレートの有界性を保証するために、ステップサイズと正則化パラメータに関する和に関する条件が課されている。
• 階層的一貫性 (Hierarchical Coherence): 上位レベルの関数のドメインが下位レベルのドメインに含まれることを保証する条件。

主な貢献

1. 一般的な問題定式化: 本論文は、コンパクトな集合上の指示関数を用いた有限次元の制約ではなく、潜在的に無限次元のヒルベルト空間における一般的な凸合成項 $\ell_1, \ell_2$ を扱うことで、既存の文献（具体的には [1, 57]）を拡張している。
2. アルゴリズムの効率性: 提案手法は、1イテレーションあたり $F_1, F_2$ の演算評価を1回のみ必要とし、従来のダブルコール型のエクストラグラディエント法よりも改善されている。
3. 複雑性の保証: 著者らは、適切に構成されたエルゴード平均を用いて、実行可能領域ギャップ（下位レベル）および最適性ギャップ（階層的問題）の両方に関する最悪ケースのイテレーション複雑性レートを確立している。
4. コンパクト性仮定の除去: ドメインがコンパクトであることを要求していた従来の複雑性解析とは異なり、本研究では、幾何学的な弱鋭鋭性と漸近解析手法を用いることで、コンパクトなドメインを仮定せずに収束レートを導出している。

主な結果
本論文は、アルゴリズムによって生成されるエルゴード平均 $\bar{z}_K$ の劣線形収束レートを確立している。正則化列 $\sigma_k = O(k^{-\delta})$ （ただし $\delta \in (0,1)$）を仮定すると：

• 実行可能領域ギャップ: 下位レベル問題のギャップ関数は $O(k^{-\delta})$ のレートで収束する。
• 最適性ギャップ: 全体の階層的問題のギャップ関数は $O(k^{-(1-\delta)})$ のレートで収束する。
• 改善されたレート: 上位レベルの作用素 $F_1$ が強単調であるという仮定の下で、本論文は改善されたレートを導出し、一意の解への収束を示す。
• 弱収束: 弱鋭鋭性の幾何学的条件の下で、イテレートの列は $S_1$ 内の解に弱収束することが示される。

意義と主張
著者らは、その結果がイテレーション複雑性と問題定式化の汎用性の両面において、最先端の技術（state of the art）と一致し、それを上回るものであると主張している。具体的には、本論文は：

• 単純なバイレベル最適化および特定の VI ケースから、広範な階層的 HVI 問題のクラスへと複雑性の保証を拡張した。
• 以前は主に階層的最適化で使用されていた「弱鋭鋭性」条件が、統一された複雑性の記述を確立するために、変分設定へ効果的に翻訳できることを示した。
• 非自律的発展方程式解析の手法を用いた方法論的枠組みを提供しており、これは非有界なドメインを扱うための貢献であり、他の階層的平衡問題にも有用であると著者らは示唆している。

最後に、現在の解析は決定論的な設定を対象としているが、今後の研究では確率的な定式化や加速手法を探索できる可能性があると述べている。階層的ナッシュ均衡および制約付きミンマックス問題（一般化絶対値方程式を含む）に関する数値実験が、理論的知見を検証するために提示されている。