一階双レベルミニマックス最適化の安定性と汎化について

要旨: 階層（バイレベル）最適化および階層（バイレベル）ミニマックス最適化は、ハイパーパラメータ最適化や強化学習を含むさまざまな機械学習タスクのための統一的枠組みとして、近年注目を集めています。既存文献は経験的効率性や収束保証に焦点を当てている一方で、これらのアルゴリズムがどの程度うまく一般化するのかを理解するうえでの、重要な理論的ギャップが残されています。このギャップを埋めるために、本研究では、下位レベルがミニマックス問題である階層（バイレベル）ミニマックスソルバに対する一次（ファーストオーダー）勾配ベース手法について、初めての体系的な一般化解析を提示します。具体的には、アルゴリズム的安定性の議論を活用することで、シングルタイムスケールの確率的勾配降下・上昇（SGD-ascent）を含む、代表的な3つのアルゴリズムに対して、きめ細かな一般化境界を導出します。さらに、2つのバリアントとして、ツータイムスケールの確率的勾配降下・上昇（SGD-ascent）も扱います。本研究の結果は、アルゴリズム的安定性、一般化ギャップ、および実運用上の設定の間に、正確なトレードオフが存在することを明らかにします。加えて、広範な経験的評価によって、階層（バイレベル）ミニマックス構造を持つ現実的な最適化タスクに関して、本理論的洞察が裏付けられます。