論文の概要: Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization
- arxiv url: http://arxiv.org/abs/2208.05925v4
- Date: Mon, 03 Feb 2025 17:42:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-05 14:54:25.695578
- Title: Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization
- Title(参考訳): 確率最小値最適化における勾配最小化のための近似アルゴリズム
- Authors: Lesi Chen, Luo Luo,
- Abstract要約: 本研究では,スムーズなミニマックス最適化のための準定常点を求める問題について検討する。
コンベックスコンケーブ・コンケーブの両ケースにおいて, RAIN (SFO) が最小限の最適化を実現することを示す。
- 参考スコア(独自算出の注目度): 17.467589890017123
- License:
- Abstract: We study the problem of finding a near-stationary point for smooth minimax optimization. The recently proposed extra anchored gradient (EAG) methods achieve the optimal convergence rate for the convex-concave minimax problem in the deterministic setting. However, the direct extension of EAG to stochastic optimization is not efficient. In this paper, we design a novel stochastic algorithm called Recursive Anchored IteratioN (RAIN). We show that the RAIN achieves near-optimal stochastic first-order oracle (SFO) complexity for stochastic minimax optimization in both convex-concave and strongly-convex-strongly-concave cases. In addition, we extend the idea of RAIN to solve structured nonconvex-nonconcave minimax problem and it also achieves near-optimal SFO complexity.
- Abstract(参考訳): 本研究では,スムーズなミニマックス最適化のための準定常点を求める問題について検討する。
最近提案されたextra anchored gradient (EAG) 法は, 決定論的条件下での凸凹最小値問題に対する最適収束率を実現する。
しかし、確率最適化へのEAGの直接拡張は効率的ではない。
本稿では,Recursive Anchored IteratioN (RAIN)と呼ばれる新しい確率的アルゴリズムを設計する。
本研究は,コンベックス・コンベブと強凸・強凸・強凸・強凸・強凸のいずれにおいても,確率的最小値最適化のために,近最適1次オラクル(SFO)の複雑性を実現することを示す。
さらに、構造化された非凸非凹極小問題の解法としてRAINの概念を拡張し、ほぼ最適 SFO の複雑性も達成する。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳(メタデータ) (2024-06-28T02:56:22Z) - Optimal Guarantees for Algorithmic Reproducibility and Gradient
Complexity in Convex Optimization [55.115992622028685]
以前の研究は、一階法はより良い収束率(漸進収束率)をトレードオフする必要があることを示唆している。
最適複雑性と準最適収束保証の両方を、滑らかな凸最小化と滑らかな凸最小化問題に対して達成できることを実証する。
論文 参考訳(メタデータ) (2023-10-26T19:56:52Z) - 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) - Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
バイレベル最適化は、機械学習における問題の1つだ。
双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
論文 参考訳(メタデータ) (2022-02-08T07:10:06Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳(メタデータ) (2020-06-16T17:55:46Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。