論文の概要: Fundamental Benefit of Alternating Updates in Minimax Optimization
- arxiv url: http://arxiv.org/abs/2402.10475v2
- Date: Mon, 15 Jul 2024 08:21:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-17 01:55:15.620679
- Title: Fundamental Benefit of Alternating Updates in Minimax Optimization
- Title（参考訳）: ミニマックス最適化における代替更新の基本的利点
- Authors: Jaewook Lee, Hanseul Cho, Chulhee Yun,
- Abstract要約: Gradient Descent-Ascent gradients (GDA) アルゴリズムは、最小限の最適化問題を解決するために設計されている。
Alt-GDAはイテレーションを早く収束させるのが一般的であるが、両者のパフォーマンスギャップはまだよく理解されていない。
本稿では,強いコンケーブとリプシッツの勾配目的に対する両アルゴリズムの微細収束解析について述べる。
- 参考スコア（独自算出の注目度）: 15.170534286366744
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Gradient Descent-Ascent (GDA) algorithm, designed to solve minimax optimization problems, takes the descent and ascent steps either simultaneously (Sim-GDA) or alternately (Alt-GDA). While Alt-GDA is commonly observed to converge faster, the performance gap between the two is not yet well understood theoretically, especially in terms of global convergence rates. To address this theory-practice gap, we present fine-grained convergence analyses of both algorithms for strongly-convex-strongly-concave and Lipschitz-gradient objectives. Our new iteration complexity upper bound of Alt-GDA is strictly smaller than the lower bound of Sim-GDA; i.e., Alt-GDA is provably faster. Moreover, we propose Alternating-Extrapolation GDA (Alex-GDA), a general algorithmic framework that subsumes Sim-GDA and Alt-GDA, for which the main idea is to alternately take gradients from extrapolations of the iterates. We show that Alex-GDA satisfies a smaller iteration complexity bound, identical to that of the Extra-gradient method, while requiring less gradient computations. We also prove that Alex-GDA enjoys linear convergence for bilinear problems, for which both Sim-GDA and Alt-GDA fail to converge at all.
- Abstract（参考訳）: 最小最適化問題を解決するために設計されたグラディエントDescent-Ascent(GDA)アルゴリズムは、降下と昇降を同時に行う(Sim-GDA)か、交互に(Alt-GDA)。
一般にAlt-GDAはより速く収束することが観察されるが、この2つの間の性能差は理論上はまだよく理解されていない。
この理論-実践的ギャップに対処するために、強凸-強凸-凹面およびリプシッツ-勾配目的に対する両アルゴリズムの微細収束解析を提案する。
我々の新しい反復複雑性上界 Alt-GDA は、Sim-GDA の下限よりも厳密に小さく、すなわち Alt-GDA は証明的に高速である。
さらに,Sim-GDA と Alt-GDA を置換するアルゴリズムフレームワークである Alternating-Extrapolation GDA (Alex-GDA) を提案する。
この結果から,Alex-GDA は増進法と同一の最小限の反復複雑性を満足するが,勾配計算は必要としないことを示す。
また、Alex-GDA が双線型問題に対する線形収束を楽しみ、Sim-GDA も Alt-GDA も全く収束しないことを示す。
関連論文リスト
- Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳（メタデータ） (2022-11-14T12:32:18Z) - Randomized Stochastic Gradient Descent Ascent [37.887266927498395]
既存のアルゴリズムの堅牢性や逆転性といった機械学習問題の増加には、損失関数を最小化する必要がある。
より単純な理論解析によるループサイズを持つESGDAの変種であるRSGDA(Randomized SGD)を提案する。
論文 参考訳（メタデータ） (2021-11-25T16:44:19Z) - 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) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳（メタデータ） (2021-07-06T21:59:49Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Don't Fix What ain't Broke: Near-optimal Local Convergence of
Alternating Gradient Descent-Ascent for Minimax Optimization [24.236441934607154]
交互降下度(Alt-GDA)は多くの設定において同時降下度(Sim-GDA)よりも優れている。
強凹問題に対してalt-gdaが最適に近い局所収束率を達成することを示す。
特に,Alt-GDAが強凹問題に対してほぼ最適局所収束率を達成することを証明した。
論文 参考訳（メタデータ） (2021-02-18T16:39:35Z) - Proximal Gradient Descent-Ascent: Variable Convergence under K{\L}
Geometry [49.65455534654459]
有限降下指数パラメータ (GDA) はミニマックス最適化問題の解法として広く応用されている。
本稿では、KL-L型幾何学の収束を研究することにより、そのようなギャップを埋める。
論文 参考訳（メタデータ） (2021-02-09T05:35:53Z) - Global Convergence and Variance-Reduced Optimization for a Class of
Nonconvex-Nonconcave Minimax Problems [39.13924898972611]
非minimaxewicz問題は、生成的対向ネットワークと対向学習の応用において頻繁に現れる。
一定の大きさのGDAアルゴリズムは凸設定でも潜在的に分岐する可能性がある。
AGDAアルゴリズムは、サブレートに達する速度でグローバルに収束する。
論文 参考訳（メタデータ） (2020-02-22T04:20:37Z) - Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
適応性は現代最適化理論において重要であるが、研究されていない性質である。
提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
論文 参考訳（メタデータ） (2020-02-13T05:42:27Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。