HyperAIHyperAI

Command Palette

Search for a command to run...

ミニマックス最適化における更新の交互化の根本的な利点

Jaewook Lee Hanseul Cho Chulhee Yun

概要

ミニマックス最適化問題を解くために設計された勾配降下・上昇法(Gradient Descent-Ascent, GDA)は、下降ステップと上昇ステップを同時に(Sim-GDA)または交互に(Alt-GDA)実行する。実際の計算ではAlt-GDAがより高速に収束することが多く見られる一方で、特にグローバル収束速度の観点から、両者の性能差についての理論的理解はまだ不十分である。この理論と実践のギャップを埋めるために、本研究では強凸-強凹およびリプシッツ勾配を持つ目的関数に対する、両アルゴリズムの詳細な収束解析を提示する。新たな結果として、Alt-GDAの反復複雑度上界がSim-GDAの下界を厳密に下回ることを示し、Alt-GDAが理論的にもより高速であることを証明した。さらに、Sim-GDAおよびAlt-GDAを包含する汎用的なアルゴリズム枠組みとして、交互補外勾配降下・上昇法(Alternating-Extrapolation GDA, Alex-GDA)を提案する。Alex-GDAの基本的なアイデアは、反復点の補外に基づいて勾配を交互に計算することである。我々は、Alex-GDAがExtra-gradient法と同一の反復複雑度上界を満たしつつ、勾配計算回数を削減できることを示した。また、双線形問題において、Alex-GDAが線形収束を達成する一方で、Sim-GDAおよびAlt-GDAはそもそも収束しないこと(発散する)ことを証明した。


AIでAIを構築

アイデアからローンチまで — 無料のAIコーディング支援、すぐに使える環境、最高のGPU価格でAI開発を加速。

AI コーディング補助
すぐに使える GPU
最適な料金体系

HyperAI Newsletters

最新情報を購読する
北京時間 毎週月曜日の午前9時 に、その週の最新情報をメールでお届けします
メール配信サービスは MailChimp によって提供されています