論文の概要: Beyond first-order methods for non-convex non-concave min-max optimization

• arxiv url: http://arxiv.org/abs/2304.08389v1
• Date: Mon, 17 Apr 2023 15:55:40 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-18 14:20:54.127796
• Title: Beyond first-order methods for non-convex non-concave min-max optimization
• Title（参考訳）: 非凸非凸min-max最適化のための一階超解法
• Authors: Abhijeet Vyas and Brian Bullins
• Abstract要約: モノトーンおよびミンティ条件設定を超える改善が達成できることを示す。 具体的には、離散時間最小化の新しい理解を提供する。 離散時間設定に適合する連続時間解析を提示する。
• 参考スコア（独自算出の注目度）: 6.097141897343098
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a study of structured non-convex non-concave min-max problems which goes beyond standard first-order approaches. Inspired by the tight understanding established in recent works [Adil et al., 2022, Lin and Jordan, 2022b], we develop a suite of higher-order methods which show the improvements attainable beyond the monotone and Minty condition settings. Specifically, we provide a new understanding of the use of discrete-time $p^{th}$-order methods for operator norm minimization in the min-max setting, establishing an $O(1/\epsilon^\frac{2}{p})$ rate to achieve $\epsilon$-approximate stationarity, under the weakened Minty variational inequality condition of Diakonikolas et al. [2021]. We further present a continuous-time analysis alongside rates which match those for the discrete-time setting, and our empirical results highlight the practical benefits of our approach over first-order methods.
• Abstract（参考訳）: 本稿では,従来の一階法を超越した非凸最小値問題について検討する。 最近の作品 (adil et al., 2022, lin and jordan, 2022b) で確立された厳密な理解に触発されて,モノトーンやミントニー条件を超えて達成可能な改善を示す一連の高階法を開発した。 具体的には、min-max 設定における作用素ノルム最小化のための離散時間 $p^{th}$-order 法の使用について、diakonikolas 等の弱ミント変分不等式条件下で $o(1/\epsilon^\frac{2}{p})$ を達成するために $o(1//\epsilon^\frac{2}{p}) を成立させる新しい理解を提供する。 [2021]. さらに,離散時間設定に適合するレートと並行して連続時間解析を行い,実験結果から,一階法に対するアプローチの実用的メリットを浮き彫りにする。

関連論文リスト

• Strictly Low Rank Constraint Optimization -- An Asymptotically $\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
  最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。 我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
  論文  参考訳（メタデータ） (2023-07-04T16:55:41Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [114.69800889030142]
  本稿では,一階変分法の理論解析のための統一的アプローチを提案する。 提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。 凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
  論文  参考訳（メタデータ） (2023-05-25T11:11:31Z)
• A Fully First-Order Method for Stochastic Bilevel Optimization [8.663726907303303]
  一階勾配オラクルのみが利用できる場合、制約のない二段階最適化問題を考える。 完全一階近似法(F2SA)を提案し,その非漸近収束特性について検討する。 MNISTデータハイパクリーニング実験において,既存の2次手法よりも提案手法の実用性能が優れていることを示す。
  論文  参考訳（メタデータ） (2023-01-26T05:34:21Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [96.71652414591051]
  本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。 提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Accelerated Single-Call Methods for Constrained Min-Max Optimization [5.266784779001398]
  既存の方法は、各イテレーションで2つのグラデーションコールか2つのプロジェクションを必要とする。 本稿では,RGOG(Optimistic Gradient)の変種が,非可換な min-max 収束率問題に富むことを示した。 私たちの収束率は、自然や自然のような標準の尺度に当てはまる。
  論文  参考訳（メタデータ） (2022-10-06T17:50:42Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Higher-order methods for convex-concave min-max optimization and monotone variational inequalities [7.645449711892907]
  制約付き凸凹 min-max 問題に対する収束率の改善と高次滑らかな単調変分不等式を提供する。 p>2$の場合、ネミロフスキーの1階ミラープロキシ法の反復複雑性を改善する。 さらに、制約のない$p=2$ケースでアルゴリズム全体をインスタンス化する。
  論文  参考訳（メタデータ） (2020-07-09T03:12:33Z)
• 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)
• 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)

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

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