論文の概要: Accelerated Algorithms for Monotone Inclusions and Constrained Nonconvex-Nonconcave Min-Max Optimization

• arxiv url: http://arxiv.org/abs/2206.05248v1
• Date: Fri, 10 Jun 2022 17:44:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-13 16:03:18.524874
• Title: Accelerated Algorithms for Monotone Inclusions and Constrained Nonconvex-Nonconcave Min-Max Optimization
• Title（参考訳）: モノトン包有物の加速アルゴリズムと制約付き非凸ノンコンケーブMin-Max最適化
• Authors: Yang Cai, Argyris Oikonomou, Weiqiang Zheng
• Abstract要約: まず,Yoon と Ryu によって提案された Extra Anchored Gradient (EAG) アルゴリズムが,Lipschitz 単調包摂の一般問題に応用可能であることを示す。 第2の結果は Extra Anchored Gradient Plus (EAG+) と呼ばれる新しいアルゴリズムであり、これは全ての単調包摂問題に対して加速された$O(frac1T)$収束率を達成する。
• 参考スコア（独自算出の注目度）: 4.6193503399184275
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study monotone inclusions and monotone variational inequalities, as well as their generalizations to non-monotone settings. We first show that the Extra Anchored Gradient (EAG) algorithm, originally proposed by Yoon and Ryu [2021] for unconstrained convex-concave min-max optimization, can be applied to solve the more general problem of Lipschitz monotone inclusion. More specifically, we prove that the EAG solves Lipschitz monotone inclusion problems with an \emph{accelerated convergence rate} of $O(\frac{1}{T})$, which is \emph{optimal among all first-order methods} [Diakonikolas, 2020, Yoon and Ryu, 2021]. Our second result is a new algorithm, called Extra Anchored Gradient Plus (EAG+), which not only achieves the accelerated $O(\frac{1}{T})$ convergence rate for all monotone inclusion problems, but also exhibits the same accelerated rate for a family of general (non-monotone) inclusion problems that concern negative comonotone operators. As a special case of our second result, EAG+ enjoys the $O(\frac{1}{T})$ convergence rate for solving a non-trivial class of nonconvex-nonconcave min-max optimization problems. Our analyses are based on simple potential function arguments, which might be useful for analysing other accelerated algorithms.
• Abstract（参考訳）: モノトン含量およびモノトン変量不等式および非モノトン設定への一般化について検討した。 まず, 制約のない凸凹最小値最適化のために, Yoon と Ryu [2021] によって提案された Extra Anchored Gradient (EAG) アルゴリズムが, リプシッツ単調包摂のより一般的な問題を解くために適用可能であることを示す。 より具体的には、eag がリプシッツ単調包含問題に対して $o(\frac{1}{t})$ の \emph{accelerated convergence rate} で解くことが証明され、これはすべての一階法において \emph{optimal} である [diakonikolas, 2020, yoon and ryu, 2021]。 第2の結果は Extra Anchored Gradient Plus (EAG+) と呼ばれる新しいアルゴリズムであり、これは加速された$O(\frac{1}{T})$収束率を全ての単調包含問題に対して達成するだけでなく、負のコモノトン作用素に関する一般(非単調)包含問題に対して同じ加速率を示す。 2つ目の結果の特別な場合として、EAG+ は非凸非凸 min-max 最適化問題の非自明なクラスを解くための$O(\frac{1}{T})$収束率を享受する。 我々の解析は単純なポテンシャル関数引数に基づいており、他の高速化アルゴリズムの解析に有用である。

関連論文リスト

• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization [108.35402316802765]
  本稿では,新しい一階最適化アルゴリズムであるAcceleratedGradient-OptimisticGradient (AG-OG) Ascentを提案する。 我々はAG-OGが様々な設定に対して最適収束率(定数まで)を達成することを示す。 アルゴリズムを拡張して設定を拡張し、bi-SC-SCとbi-C-SCの両方で最適な収束率を達成する。
  論文  参考訳（メタデータ） (2022-10-31T17:59:29Z)
• Accelerated Single-Call Methods for Constrained Min-Max Optimization [5.266784779001398]
  既存の方法は、各イテレーションで2つのグラデーションコールか2つのプロジェクションを必要とする。 本稿では,RGOG(Optimistic Gradient)の変種が,非可換な min-max 収束率問題に富むことを示した。 私たちの収束率は、自然や自然のような標準の尺度に当てはまる。
  論文  参考訳（メタデータ） (2022-10-06T17:50:42Z)
• Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization [14.719077076351377]
  本研究では,スムーズなミニマックス最適化のための準定常点を求める問題について検討する。 Recursive IteratioNRAINと呼ばれる新しいアルゴリズムは凸凹と強凹の両方のケースを実現する。
  論文  参考訳（メタデータ） (2022-08-11T16:55:26Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Lower Bounds and Accelerated Algorithms for Bilevel Optimization [62.192297758346484]
  バイレベル最適化は、最近の機械学習問題に広く応用されているため、近年、関心が高まりつつある。 結果がminimaxアプリケーションよりも難しいことを示します。
  論文  参考訳（メタデータ） (2021-02-07T21:46:29Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
  論文  参考訳（メタデータ） (2020-12-11T08:28:51Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。