論文の概要: Negative Stepsizes Make Gradient-Descent-Ascent Converge
- arxiv url: http://arxiv.org/abs/2505.01423v1
- Date: Fri, 02 May 2025 17:59:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-05 17:21:20.099537
- Title: Negative Stepsizes Make Gradient-Descent-Ascent Converge
- Title（参考訳）: 負のステップサイズでグラディエントDescent-Ascentが収束する
- Authors: Henry Shugart, Jason M. Altschuler,
- Abstract要約: GDAは, 正則な段数選択法を用いることで, 元の形式に収束することを示す。
我々はこれを二階有限差分アルゴリズムとして解釈し、興味深いことに、ほぼコンセンサス最適化を実装していることを示す。
- 参考スコア（独自算出の注目度）: 5.448070998907116
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Efficient computation of min-max problems is a central question in optimization, learning, games, and controls. Arguably the most natural algorithm is gradient-descent-ascent (GDA). However, since the 1970s, conventional wisdom has argued that GDA fails to converge even on simple problems. This failure spurred an extensive literature on modifying GDA with additional building blocks such as extragradients, optimism, momentum, anchoring, etc. In contrast, we show that GDA converges in its original form by simply using a judicious choice of stepsizes. The key innovation is the proposal of unconventional stepsize schedules (dubbed slingshot stepsize schedules) that are time-varying, asymmetric, and periodically negative. We show that all three properties are necessary for convergence, and that altogether this enables GDA to converge on the classical counterexamples (e.g., unconstrained convex-concave problems). All of our results apply to the last iterate of GDA, as is typically desired in practice. The core algorithmic intuition is that although negative stepsizes make backward progress, they de-synchronize the min and max variables (overcoming the cycling issue of GDA), and lead to a slingshot phenomenon in which the forward progress in the other iterations is overwhelmingly larger. This results in fast overall convergence. Geometrically, the slingshot dynamics leverage the non-reversibility of gradient flow: positive/negative steps cancel to first order, yielding a second-order net movement in a new direction that leads to convergence and is otherwise impossible for GDA to move in. We interpret this as a second-order finite-differencing algorithm and show that, intriguingly, it approximately implements consensus optimization, an empirically popular algorithm for min-max problems involving deep neural networks (e.g., training GANs).
- Abstract（参考訳）: min-max問題の効率的な計算は、最適化、学習、ゲーム、制御において中心的な問題である。
おそらく最も自然なアルゴリズムは勾配日射量(GDA)である。
しかし、1970年代以降、従来の知恵は、GDAは単純な問題にも収束しないと主張した。
この失敗により、グラディエント、楽観主義、運動量、アンカーリングといった追加のビルディングブロックによるGDAの変更に関する広範な文献が引き起こされた。
対照的に、GDAが元の形式に収束することを示すには、単に段数の司法的選択を用いるだけでよい。
鍵となる革新は、時間変化、非対称、周期的に否定的な非伝統的なステップサイズスケジュール(スリングショットステップサイズスケジュールと呼ばれる)の提案である。
収束には3つの性質がすべて必要であり、GDAが古典的な反例(例えば、制約のない凸凸凸問題)に収束できることを示す。
我々の結果は、一般的に望まれるように、GDAの最終イテレーションに適用されます。
アルゴリズムの中核的な直観は、負のステップ化は後進を進行させるが、min変数とmax変数(GDAのサイクリング問題に逆らう)を非同期化し、他のイテレーションの前進が圧倒的に大きいスリングショット現象を引き起こすことである。
これにより、全体の収束が早くなる。
幾何学的には、スリングショット力学は勾配流の非可逆性を利用する: 正・負のステップは1次にキャンセルされ、新しい方向に2階のネット運動をもたらす。
これを二階有限差分アルゴリズムとして解釈し、興味深いことに、ディープニューラルネットワーク(例えば、GANを訓練する)に関わるmin-max問題に対する経験的人気アルゴリズムであるコンセンサス最適化を概ね実装していることを示す。
関連論文リスト
- Fundamental Benefit of Alternating Updates in Minimax Optimization [15.170534286366744]
Gradient Descent-Ascent gradients (GDA) アルゴリズムは、最小限の最適化問題を解決するために設計されている。
Alt-GDAはイテレーションを早く収束させるのが一般的であるが、両者のパフォーマンスギャップはまだよく理解されていない。
本稿では,強いコンケーブとリプシッツの勾配目的に対する両アルゴリズムの微細収束解析について述べる。
論文 参考訳（メタデータ） (2024-02-16T06:41:35Z) - Differentiable Bilevel Programming for Stackelberg Congestion Games [47.60156422249365]
Stackelberg Congestion Game (SCG) において、リーダーは、群集が集まる平衡状態を予測し、操作することで、自身の利益を最大化することを目的としている。
本稿では,従来の手法と機械学習における最新の微分可能プログラミング技術を組み合わせることで,この計算課題に挑戦する。
本稿では,SCGの局所探索アルゴリズムを2つ提案する。第1に,微分可能プログラミングを用いてILDをアンロールすることで導関数を求める勾配降下アルゴリズムを提案する。
第二のアルゴリズムは、フォロワーの進化軌道を短くすることでツイストを加える。
論文 参考訳（メタデータ） (2022-09-15T21:32:23Z) - Escaping Saddle Points in Nonconvex Minimax Optimization via
Cubic-Regularized Gradient Descent-Ascent [13.565010494569243]
勾配降下度アルゴリズム(GDA)は、非ミニマックス最適化問題の解法として広く応用されている。
我々は,非コンケーブ極小最適化における点のエスケープのための第一型GDAアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-10-14T00:36:44Z) - Solve Minimax Optimization by Anderson Acceleration [5.900781483345349]
勾配降下上昇(GDA)は、その単純さから最もよく使われるアルゴリズムである。
本稿では,GDA力学を固定点反復とみなす新しいミニマックス最適化フレームワークGDA-AMを提案する。
理論上,このアルゴリズムは温和条件下での双線形問題に対する大域収束を実現することができることを示す。
論文 参考訳（メタデータ） (2021-10-06T02:08:54Z) - An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm
for First-order and Zeroth-order Optimization [111.24899593052851]
条件勾配アルゴリズム(Frank-Wolfeアルゴリズムとも呼ばれる)は、最近、機械学習コミュニティで人気を取り戻している。
ARCSは、ゼロ階最適化において凸問題を解く最初のゼロ階条件勾配スライディング型アルゴリズムである。
1次最適化では、ARCSの収束結果は、勾配クエリのオラクルの数で、従来のアルゴリズムよりも大幅に優れていた。
論文 参考訳（メタデータ） (2021-09-18T07:08:11Z) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳（メタデータ） (2021-07-06T21:59:49Z) - Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。
我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文 参考訳（メタデータ） (2021-03-04T19:01:20Z) - Proximal Gradient Descent-Ascent: Variable Convergence under K{\L}
Geometry [49.65455534654459]
有限降下指数パラメータ (GDA) はミニマックス最適化問題の解法として広く応用されている。
本稿では、KL-L型幾何学の収束を研究することにより、そのようなギャップを埋める。
論文 参考訳（メタデータ） (2021-02-09T05:35:53Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Global Convergence and Variance-Reduced Optimization for a Class of
Nonconvex-Nonconcave Minimax Problems [39.13924898972611]
非minimaxewicz問題は、生成的対向ネットワークと対向学習の応用において頻繁に現れる。
一定の大きさのGDAアルゴリズムは凸設定でも潜在的に分岐する可能性がある。
AGDAアルゴリズムは、サブレートに達する速度でグローバルに収束する。
論文 参考訳（メタデータ） (2020-02-22T04:20:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。