論文の概要: Min-Max Optimization under Delays

• arxiv url: http://arxiv.org/abs/2307.06886v2
• Date: Thu, 24 Aug 2023 14:22:44 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-25 17:31:06.057242
• Title: Min-Max Optimization under Delays
• Title（参考訳）: 遅延下におけるMin-Max最適化
• Authors: Arman Adibi, Aritra Mitra, and Hamed Hassani
• Abstract要約: 大規模な機械学習問題では遅延と非同期は避けられない。 min-max最適化に類似した理論は存在しない。 たとえ小さな遅延であっても、エクストラグラディエントのような顕著なアルゴリズムが分岐する可能性があることを示す。
• 参考スコア（独自算出の注目度）: 26.830212508878162
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Delays and asynchrony are inevitable in large-scale machine-learning problems where communication plays a key role. As such, several works have extensively analyzed stochastic optimization with delayed gradients. However, as far as we are aware, no analogous theory is available for min-max optimization, a topic that has gained recent popularity due to applications in adversarial robustness, game theory, and reinforcement learning. Motivated by this gap, we examine the performance of standard min-max optimization algorithms with delayed gradient updates. First, we show (empirically) that even small delays can cause prominent algorithms like Extra-gradient (\texttt{EG}) to diverge on simple instances for which \texttt{EG} guarantees convergence in the absence of delays. Our empirical study thus suggests the need for a careful analysis of delayed versions of min-max optimization algorithms. Accordingly, under suitable technical assumptions, we prove that Gradient Descent-Ascent (\texttt{GDA}) and \texttt{EG} with delayed updates continue to guarantee convergence to saddle points for convex-concave and strongly convex-strongly concave settings. Our complexity bounds reveal, in a transparent manner, the slow-down in convergence caused by delays.
• Abstract（参考訳）: コミュニケーションが重要な役割を果たす大規模機械学習では、遅延と非同期性は避けられない。 このように、いくつかの研究は遅延勾配を伴う確率的最適化を広範囲に分析している。 しかし、我々が認識している限り、min-max最適化の類似理論は存在せず、敵意の強固さ、ゲーム理論、強化学習の応用により最近人気を集めている。 このギャップにより、遅延勾配更新を伴う標準のmin-max最適化アルゴリズムの性能について検討する。 まず, 遅延が小さい場合でも, 遅延がない場合の収束が保証される単純なインスタンスに対して, 勾配外(\texttt{EG})のような顕著なアルゴリズムが発散することを示す。 その結果,min-max最適化アルゴリズムの遅延バージョンを注意深く解析する必要性が示唆された。 したがって、適切な技術的仮定の下では、遅延更新を伴う勾配降下(\texttt{gda})および \texttt{eg} が凸凹および強い凸強凸凹設定のためのサドル点への収束を保証し続けることが証明される。 私たちの複雑性は、透過的な方法で、遅延による収束の遅さを明らかにします。

関連論文リスト

• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。 我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
  論文  参考訳（メタデータ） (2024-02-19T03:08:02Z)
• Ordering for Non-Replacement SGD [7.11967773739707]
  我々は,アルゴリズムの非置換形式に対する収束率を改善する順序付けを求める。 我々は,強い凸関数と凸関数のステップサイズを一定かつ小さくするための最適順序付けを開発する。 さらに、注文とミニバッチを組み合わせることで、より複雑なニューラルネットワークにも適用できます。
  論文  参考訳（メタデータ） (2023-06-28T00:46:58Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• 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)
• Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems [2.0305676256390934]
  連立勾配降下指数アルゴリズムの連続時間変動の有限時間特性を特徴付ける。 連続時間アルゴリズムの挙動に関する結果は、離散時間アルゴリズムの収束特性を高めるために用いられる。
  論文  参考訳（メタデータ） (2021-12-17T15:51:04Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• 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)
• Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization [61.66927778694731]
  エポッチ勾配降下法(エポッチ勾配降下法、Epoch-GD)は、2011年にHazan and Kaleによって提唱された。 Epoch-GDA が SCSC min-max 問題の双対性ギャップに対して$O (1/T) の最適レートを達成できることを示す最初の実験である。
  論文  参考訳（メタデータ） (2020-02-13T02:16:57Z)

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

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