論文の概要: Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization

• arxiv url: http://arxiv.org/abs/2206.00743v1
• Date: Wed, 1 Jun 2022 20:11:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-03 13:48:20.330779
• Title: Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization
• Title（参考訳）: Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization (特集:ユビキタスコンピューティング)
• Authors: Junchi Yang, Xiang Li, Niao He
• Abstract要約: AdaGradやAMSのような適応アルゴリズムは、非特異なパラメータの堅牢性に成功している。 我々はNeAdaが最適に近いレベルの知識を実現できることを示す。
• 参考スコア（独自算出の注目度）: 24.784754071913255
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Adaptive algorithms like AdaGrad and AMSGrad are successful in nonconvex optimization owing to their parameter-agnostic ability -- requiring no a priori knowledge about problem-specific parameters nor tuning of learning rates. However, when it comes to nonconvex minimax optimization, direct extensions of such adaptive optimizers without proper time-scale separation may fail to work in practice. We provide such an example proving that the simple combination of Gradient Descent Ascent (GDA) with adaptive stepsizes can diverge if the primal-dual stepsize ratio is not carefully chosen; hence, a fortiori, such adaptive extensions are not parameter-agnostic. To address the issue, we formally introduce a Nested Adaptive framework, NeAda for short, that carries an inner loop for adaptively maximizing the dual variable with controllable stopping criteria and an outer loop for adaptively minimizing the primal variable. Such mechanism can be equipped with off-the-shelf adaptive optimizers and automatically balance the progress in the primal and dual variables. Theoretically, for nonconvex-strongly-concave minimax problems, we show that NeAda can achieve the near-optimal $\tilde{O}(\epsilon^{-2})$ and $\tilde{O}(\epsilon^{-4})$ gradient complexities respectively in the deterministic and stochastic settings, without prior information on the problem's smoothness and strong concavity parameters. To the best of our knowledge, this is the first algorithm that simultaneously achieves near-optimal convergence rates and parameter-agnostic adaptation in the nonconvex minimax setting. Numerically, we further illustrate the robustness of the NeAda family with experiments on simple test functions and a real-world application.
• Abstract（参考訳）: AdaGradやAMSGradのような適応アルゴリズムは、パラメータに依存しない能力のため、非凸最適化に成功している。 しかし、非凸最小値最適化に関しては、適切な時間スケールの分離を伴わない適応最適化器の直接拡張が実際に動作しない場合がある。 このような例は、適応段階化のグラディエントDescent Ascent(GDA)と適応段階化の単純な組み合わせが、原始-双対段階化比が慎重に選択されていない場合、分岐可能であることを証明している。 この問題に対処するため,我々はNested Adaptive framework,NeAda(略してNeAda)を導入し,二変数を制御可能な停止基準で適応的に最大化する内ループと,主変数を適応的に最小化する外ループを新たに導入した。 このような機構はオフザシェルフ適応オプティマイザを備え、原始変数と双対変数の進捗を自動的にバランスさせることができる。 理論的には、非凸強凸ミニマックス問題に対して、NeAda は、問題の滑らかさと強凹度パラメータに関する事前情報なしで、それぞれ決定論的および確率的設定において、ほぼ最適の $\tilde{O}(\epsilon^{-2})$ と $\tilde{O}(\epsilon^{-4})$ の勾配複雑性を達成できることを示す。 我々の知る限り、このアルゴリズムは非凸ミニマックス設定における近似収束率とパラメータ非依存適応を同時に達成する最初のアルゴリズムである。 さらに,簡単なテスト関数と実世界の応用実験により,NeAdaファミリーのロバスト性について述べる。

関連論文リスト

• The Price of Adaptivity in Stochastic Convex Optimization [23.776027867314628]
  非平滑凸最適化における適応性の証明を行う。 準最適性の乗法的増加を測定する「適応性の値」(PoA)を定義する。
  論文  参考訳（メタデータ） (2024-02-16T18:56:41Z)
• ELRA: Exponential learning rate adaption gradient descent optimization method [83.88591755871734]
  我々は, 高速(指数率), ab initio(超自由)勾配に基づく適応法を提案する。 本手法の主な考え方は,状況認識による$alphaの適応である。 これは任意の次元 n の問題に適用でき、線型にしかスケールできない。
  論文  参考訳（メタデータ） (2023-09-12T14:36:13Z)
• 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)
• TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax Optimization [24.784754071913255]
  適応的手法は、パラメータに依存しない方法でハエの段差を調整する能力を示した。 非凹極小問題に対する勾配上昇の電流収束解析にはパラメータの注意深くチューニングが必要である。
  論文  参考訳（メタデータ） (2022-10-31T17:05:36Z)
• Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements [34.70493893170415]
  リプシッツの連続性や滑らか性に欠ける凸最小化問題に対する適応的な一階法の一群を提案する。 適応ミラー降下法 (AdaMir) は, 比較的連続的あるいは滑らかな問題において, min-max 最適率を同時に達成することにより, このギャップを埋めることを目的としている。
  論文  参考訳（メタデータ） (2021-07-16T16:59:40Z)
• AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimization [104.96004056928474]
  本稿では,非コンケーブ最小値問題に対する高速適応勾配降下法を提案する。 我々は,本手法が,ミニバッチサイズが$O(kappa2.5epsilon-3)$のより低いサンプル複雑性に達することを示す。
  論文  参考訳（メタデータ） (2021-06-30T14:47:09Z)
• Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities [32.51470158863247]
  AdaACSAとAdaAGD+は制約付き凸最適化の高速化手法である。 我々はこれらを、同じ特徴を享受し、標準の非加速収束率を達成する、より単純なアルゴリズムAdaGrad+で補完する。
  論文  参考訳（メタデータ） (2020-07-17T09:10:21Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• 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)
• Proximal Gradient Algorithm with Momentum and Flexible Parameter Restart for Nonconvex Optimization [73.38702974136102]
  アルゴリズムの高速化のために,パラメータ再起動方式が提案されている。 本論文では,非滑らかな問題を解くアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:06:27Z)

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

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