論文の概要: Enhanced Adaptive Gradient Algorithms for Nonconvex-PL Minimax Optimization

• arxiv url: http://arxiv.org/abs/2303.03984v1
• Date: Tue, 7 Mar 2023 15:33:12 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-08 14:45:52.779631
• Title: Enhanced Adaptive Gradient Algorithms for Nonconvex-PL Minimax Optimization
• Title（参考訳）: 非凸plミニマックス最適化のための拡張適応勾配アルゴリズム
• Authors: Feihu Huang
• Abstract要約: フレームワーク $aknabla F(x) max_y f(x,y) が $ サンプルを見つけるのに使えることを証明します。 提案手法を効果的に分析する。
• 参考スコア（独自算出の注目度）: 14.579475552088692
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In the paper, we study a class of nonconvex nonconcave minimax optimization problems (i.e., $\min_x\max_y f(x,y)$), where $f(x,y)$ is possible nonconvex in $x$, and it is nonconcave and satisfies the Polyak-Lojasiewicz (PL) condition in $y$. Moreover, we propose a class of enhanced momentum-based gradient descent ascent methods (i.e., MSGDA and AdaMSGDA) to solve these stochastic Nonconvex-PL minimax problems. In particular, our AdaMSGDA algorithm can use various adaptive learning rates in updating the variables $x$ and $y$ without relying on any global and coordinate-wise adaptive learning rates. Theoretically, we present an effective convergence analysis framework for our methods. Specifically, we prove that our MSGDA and AdaMSGDA methods have the best known sample (gradient) complexity of $O(\epsilon^{-3})$ only requiring one sample at each loop in finding an $\epsilon$-stationary solution (i.e., $\mathbb{E}\|\nabla F(x)\|\leq \epsilon$, where $F(x)=\max_y f(x,y)$). This manuscript commemorates the mathematician Boris Polyak (1935-2023).
• Abstract（参考訳）: この論文では、非凸非凸ミニマックス最適化問題(例えば、$\min_x\max_y f(x,y)$)のクラスを研究し、ここで、$f(x,y)$ は非凸で$x$ であり、非凸であり、polyak-lojasiewicz (pl) 条件を $y$ で満たす。 さらに,これらの確率的非凸plミニマックス問題を解くために,運動量に基づく勾配降下上昇法(msgda,adamsgda)のクラスを提案する。 特に、我々のAdaMSGDAアルゴリズムは、グローバルかつ座標ワイドな適応学習率に頼ることなく、変数の$x$と$y$を更新する際に様々な適応学習率を使用することができる。 理論的には,本手法に有効な収束解析フレームワークを提案する。 具体的には、我々のMSGDA法とAdaMSGDA法が、$O(\epsilon^{-3})$の最もよく知られたサンプル(漸進的な)複雑性を持つことを証明し、$\epsilon$-定常解(例えば、$\mathbb{E}\|\nabla F(x)\|\leq \epsilon$, ここで$F(x)=\max_y f(x,y)$)を見つけるとき、各ループで1つのサンプルしか必要としない。 この写本は数学者ボリス・ポリャク(1935-2023)を記念している。

関連論文リスト

• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。 我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
  論文  参考訳（メタデータ） (2024-08-21T20:14:54Z)
• Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
  1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。 本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。 本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
  論文  参考訳（メタデータ） (2024-06-18T20:14:52Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum Optimization [25.21457349137344]
  私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
  論文  参考訳（メタデータ） (2022-10-25T11:37:11Z)
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization [104.96004056928474]
  本稿では,非コンケーブ最小値問題に対する高速適応勾配降下法を提案する。 我々は,本手法が,ミニバッチサイズが$O(kappa2.5epsilon-3)$のより低いサンプル複雑性に達することを示す。
  論文  参考訳（メタデータ） (2021-06-30T14:47:09Z)
• On Riemannian Gradient-Based Methods for Minimax Problems [24.199289678553896]
  ミニマックス問題を解くためのリーマン的手法のクラスを提案する。 我々はRGDAが$tildeO(kappa4eps-3)$であることを示す。 また、Acc-RSGDAが$tildeO(kappa4eps-3)$に対してより低いサンプル複雑性を実現することも示しています。
  論文  参考訳（メタデータ） (2020-10-13T00:54:00Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)
• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems [36.645753881826955]
  本稿では,分散を利用してより効率的に推定できるRecurEnti Ascent(SREDA)という新しい手法を提案する。 この方法はこの問題でよく知られている。
  論文  参考訳（メタデータ） (2020-01-11T09:05:03Z)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
  非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
  論文  参考訳（メタデータ） (2019-06-02T03:03:45Z)

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

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