論文の概要: Nesterov Meets Optimism: Rate-Optimal Optimistic-Gradient-Based Method
for Stochastic Bilinearly-Coupled Minimax Optimization
- arxiv url: http://arxiv.org/abs/2210.17550v1
- Date: Mon, 31 Oct 2022 17:59:29 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-01 16:33:31.645308
- Title: Nesterov Meets Optimism: Rate-Optimal Optimistic-Gradient-Based Method
for Stochastic Bilinearly-Coupled Minimax Optimization
- Title（参考訳）: Nesterov : 確率的双線形結合最小値最適化のための速度最適化勾配法
- Authors: Chris Junchi Li, Angela Yuan, Gauthier Gidel, Michael I. Jordan
- Abstract要約: 両線形結合型強結合ミニマックス問題に対する新しい一階最適化アルゴリズムを提案する。
提案アルゴリズムの主な考え方は,ミニマックス問題の構造を活用することである。
- 参考スコア（独自算出の注目度）: 83.49829299585033
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We provide a novel first-order optimization algorithm for bilinearly-coupled
strongly-convex-concave minimax optimization called the AcceleratedGradient
OptimisticGradient (AG-OG). The main idea of our algorithm is to leverage the
structure of the considered minimax problem and operates Nesterov's
acceleration on the individual part and optimistic gradient on the coupling
part of the objective. We motivate our method by showing that its
continuous-time dynamics corresponds to an organic combination of the dynamics
of optimistic gradient and of Nesterov's acceleration. By discretizing the
dynamics we conclude polynomial convergence behavior in discrete time. Further
enhancement of AG-OG with proper restarting allows us to achieve rate-optimal
(up to a constant) convergence rates with respect to the conditioning of the
coupling and individual parts, which results in the first single-call algorithm
achieving improved convergence in the deterministic setting and rate-optimality
in the stochastic setting under bilinearly coupled minimax problem sets.
- Abstract（参考訳）: 強凸凸型ミニマックス最適化のための新しい一階最適化アルゴリズムであるacceleratedgradient optgradient (ag-og)を提案する。
このアルゴリズムの主な考え方は, ミニマックス問題の構造を活用し, 個々の部分に対するネステロフの加速度と, 目的のカップリング部分における楽観的勾配を操作することである。
我々は,その連続時間ダイナミクスが,楽観的勾配のダイナミクスとネステロフの加速度の有機的組み合わせに対応していることを示すことによって,本手法の動機付けを行う。
ダイナミクスを離散化することにより、多項式収束挙動を離散時間に結論付ける。
適切な再起動によるag-ogのさらなる強化により、結合と個々の部分のコンディショニングに関して、レート最適(定数まで)の収束率を達成することができ、その結果、双線型結合ミニマックス問題の下での確率的設定における決定論的設定とレート最適性が改善された最初のシングルコールアルゴリズムが得られる。
関連論文リスト
- ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
ALEXRと呼ばれる,効率的な単ループプリマルデュアルブロックコーディネートアルゴリズムを提案する。
本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。
本稿では,ALEXRの収束速度が,検討されたcFCCO問題に対する1次ブロック座標アルゴリズムの中で最適であることを示すために,より低い複雑性境界を示す。
論文 参考訳（メタデータ） (2023-12-04T19:00:07Z) - Optimal Guarantees for Algorithmic Reproducibility and Gradient
Complexity in Convex Optimization [55.115992622028685]
以前の研究は、一階法はより良い収束率(漸進収束率)をトレードオフする必要があることを示唆している。
最適複雑性と準最適収束保証の両方を、滑らかな凸最小化と滑らかな凸最小化問題に対して達成できることを実証する。
論文 参考訳（メタデータ） (2023-10-26T19:56:52Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Near-Optimal Algorithms for Making the Gradient Small in Stochastic
Minimax Optimization [14.719077076351377]
本研究では,スムーズなミニマックス最適化のための準定常点を求める問題について検討する。
Recursive IteratioNRAINと呼ばれる新しいアルゴリズムは凸凹と強凹の両方のケースを実現する。
論文 参考訳（メタデータ） (2022-08-11T16:55:26Z) - Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion [9.551565016483833]
非コンケーブなmin-max最適化問題の構造化クラスであるコモノトンmin-max最適化について検討する。
最初のコントリビューションでは、extra Anchored Gradient (EAG)アルゴリズムを制約付きコモノトン min-max 最適化に拡張する。
第2のコントリビューションでは、FEG(Fast Extra Gradient)アルゴリズムを制約のないmin-max最適化に拡張する。
論文 参考訳（メタデータ） (2022-06-10T17:44:06Z) - Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
バイレベル最適化は、機械学習における問題の1つだ。
双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
論文 参考訳（メタデータ） (2022-02-08T07:10:06Z) - Potential Function-based Framework for Making the Gradients Small in
Convex and Min-Max Optimization [14.848525762485872]
勾配を小さくすることは、統一的かつ単純な収束論証を導いた基本的な最適化問題である。
本稿では,勾配を小さくするための標準手法の収束を研究するために,新しいポテンシャル関数ベースのフレームワークを提案する。
論文 参考訳（メタデータ） (2021-01-28T16:41:00Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Stochastic Coordinate Minimization with Progressive Precision for
Stochastic Convex Optimization [16.0251555430107]
凸最適化のための反復座標最小化(CM)に基づくフレームワークを開発した。
最適精度制御と結果の順序-最適後悔性能を確立する。
提案アルゴリズムは,大規模最適化のためのCMのスケーラビリティと並列性特性を継承し,オンライン実装に適したアルゴリズムである。
論文 参考訳（メタデータ） (2020-03-11T18:42:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。