論文の概要: Potential Function-based Framework for Making the Gradients Small in
Convex and Min-Max Optimization
- arxiv url: http://arxiv.org/abs/2101.12101v1
- Date: Thu, 28 Jan 2021 16:41:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-13 11:29:54.831761
- Title: Potential Function-based Framework for Making the Gradients Small in
Convex and Min-Max Optimization
- Title(参考訳): Convex と Min-Max 最適化における勾配最小化のためのポテンシャル関数ベースフレームワーク
- Authors: Jelena Diakonikolas and Puqian Wang
- Abstract要約: 勾配を小さくすることは、統一的かつ単純な収束論証を導いた基本的な最適化問題である。
本稿では,勾配を小さくするための標準手法の収束を研究するために,新しいポテンシャル関数ベースのフレームワークを提案する。
- 参考スコア(独自算出の注目度): 14.848525762485872
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Making the gradients small is a fundamental optimization problem that has
eluded unifying and simple convergence arguments in first-order optimization,
so far primarily reserved for other convergence criteria, such as reducing the
optimality gap. We introduce a novel potential function-based framework to
study the convergence of standard methods for making the gradients small in
smooth convex optimization and convex-concave min-max optimization. Our
framework is intuitive and it provides a lens for viewing algorithms that make
the gradients small as being driven by a trade-off between reducing either the
gradient norm or a certain notion of an optimality gap. On the lower bounds
side, we discuss tightness of the obtained convergence results for the convex
setup and provide a new lower bound for minimizing norm of cocoercive operators
that allows us to argue about optimality of methods in the min-max setup.
- Abstract(参考訳): 勾配を小さくすることは、一階最適化において統一的かつ単純な収束論証を導いた基本的な最適化問題であり、これまでは最適性ギャップの減少など他の収束基準に留意されていた。
本研究では,スムーズな凸最適化および凸凹最小値最適化における勾配を小さくするための標準手法の収束について検討する。
我々のフレームワークは直感的であり、勾配基準の削減と最適性ギャップの特定の概念のトレードオフによって駆動されるように勾配を小さくするアルゴリズムを見るためのレンズを提供する。
下界側では、凸構成に対する得られた収束結果の厳密性について議論し、min-max構成におけるメソッドの最適性について議論できるコヒーレンシブ作用素のノルムを最小化する新しい下界を提供する。
関連論文リスト
- A Novel Unified Parametric Assumption for Nonconvex Optimization [53.943470475510196]
非最適化は機械学習の中心であるが、一般の非凸性は弱い収束を保証するため、他方に比べて悲観的すぎる。
非凸アルゴリズムに新しい統一仮定を導入する。
論文 参考訳(メタデータ) (2025-02-17T21:25:31Z) - Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳(メタデータ) (2024-06-28T02:56:22Z) - Low-Rank Extragradient Methods for Scalable Semidefinite Optimization [0.0]
この問題が低ランクの解を許容する高次元かつ高可算な設定に焦点をあてる。
これらの条件下では、よく知られた過次法が制約付き最適化問題の解に収束することを示す理論的結果がいくつか提示される。
論文 参考訳(メタデータ) (2024-02-14T10:48:00Z) - 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) - Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization [17.467589890017123]
本研究では,スムーズなミニマックス最適化のための準定常点を求める問題について検討する。
コンベックスコンケーブ・コンケーブの両ケースにおいて, RAIN (SFO) が最小限の最適化を実現することを示す。
論文 参考訳(メタデータ) (2022-08-11T16:55:26Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳(メタデータ) (2020-12-21T17:29:58Z) - 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) - Stochastic Coordinate Minimization with Progressive Precision for
Stochastic Convex Optimization [16.0251555430107]
凸最適化のための反復座標最小化(CM)に基づくフレームワークを開発した。
最適精度制御と結果の順序-最適後悔性能を確立する。
提案アルゴリズムは,大規模最適化のためのCMのスケーラビリティと並列性特性を継承し,オンライン実装に適したアルゴリズムである。
論文 参考訳(メタデータ) (2020-03-11T18:42:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。