論文の概要: Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition

• arxiv url: http://arxiv.org/abs/2006.06889v8
• Date: Mon, 17 Apr 2023 22:15:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-19 19:54:43.981049
• Title: Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition
• Title（参考訳）: pl条件をもつ非凸強凹min-max問題に対する高速目的と双対ギャップ収束
• Authors: Zhishuai Guo, Yan Yan, Zhuoning Yuan, Tianbao Yang
• Abstract要約: 本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
• 参考スコア（独自算出の注目度）: 52.08417569774822
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper focuses on stochastic methods for solving smooth non-convex strongly-concave min-max problems, which have received increasing attention due to their potential applications in deep learning (e.g., deep AUC maximization, distributionally robust optimization). However, most of the existing algorithms are slow in practice, and their analysis revolves around the convergence to a nearly stationary point.We consider leveraging the Polyak-Lojasiewicz (PL) condition to design faster stochastic algorithms with stronger convergence guarantee. Although PL condition has been utilized for designing many stochastic minimization algorithms, their applications for non-convex min-max optimization remain rare. In this paper, we propose and analyze a generic framework of proximal stage-based method with many well-known stochastic updates embeddable. Fast convergence is established in terms of both the primal objective gap and the duality gap. Compared with existing studies, (i) our analysis is based on a novel Lyapunov function consisting of the primal objective gap and the duality gap of a regularized function, and (ii) the results are more comprehensive with improved rates that have better dependence on the condition number under different assumptions. We also conduct deep and non-deep learning experiments to verify the effectiveness of our methods.
• Abstract（参考訳）: 本稿では, 深層学習(深層AUCの最大化, 分散ロバスト最適化など)の潜在的な応用により, 注目を集めているスムーズな非凸性 min-max 問題の解法に着目する。 しかし、既存のアルゴリズムの多くは実際は遅く、その解析は収束をほぼ定常点に回っており、より強力な収束保証を持つより高速な確率的アルゴリズムの設計にPolyak-Lojasiewicz(PL)条件を活用することを検討する。 PL条件は多くの確率最小化アルゴリズムの設計に利用されてきたが、その非凸min-max最適化への応用は稀である。 本稿では,多くの確率的更新を埋め込み可能な近位ステージベース手法の汎用フレームワークを提案し,解析する。 高速収束は主目的ギャップと双対性ギャップの両方の観点から確立される。 既存の研究と比較すると (i)本解析は,主目的ギャップと正規化関数の双対ギャップからなる新しいリアプノフ関数に基づく。 (ii) 結果はより包括的に改善され, 仮定の異なる条件数への依存度が向上した。 また,本手法の有効性を検証するために,深層および非深層学習実験を行った。

関連論文リスト

• Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
  分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。 本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-24T02:19:39Z)
• Generalized Gradient Flows with Provable Fixed-Time Convergence and Fast Evasion of Non-Degenerate Saddle Points [8.452349885923507]
  グラディエントベースの1次凸最適化アルゴリズムは、機械学習タスクを含むさまざまな領域で広く適用可能である。 最適時間の固定時間理論の最近の進歩に触発されて,高速化最適化アルゴリズムを設計するための枠組みを導入する。 非ド・サドル点を許容する関数に対しては、これらのサドル点を避けるのに必要な時間は初期条件すべてに一様有界であることを示す。
  論文  参考訳（メタデータ） (2022-12-07T16:36:23Z)
• Fixed-Time Convergence for a Class of Nonconvex-Nonconcave Min-Max Problems [5.787117733071416]
  min-max問題を解くための固定時間収束サドル点力学系を開発した。 提案手法は他のどの状態法と比較しても高速に実現できる。
  論文  参考訳（メタデータ） (2022-07-26T12:25:05Z)
• Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems [2.0305676256390934]
  連立勾配降下指数アルゴリズムの連続時間変動の有限時間特性を特徴付ける。 連続時間アルゴリズムの挙動に関する結果は、離散時間アルゴリズムの収束特性を高めるために用いられる。
  論文  参考訳（メタデータ） (2021-12-17T15:51:04Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency [83.02999769628593]
  強化学習におけるオフ・ポリティィ・アセスメント(OPE)の理論的特徴について述べる。 ミニマックス法により、重みと品質関数の高速収束を実現することができることを示す。 非タブラル環境における1次効率を持つ最初の有限サンプル結果を示す。
  論文  参考訳（メタデータ） (2021-02-05T03:20:39Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• 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)

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

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