論文の概要: On Stochastic Moving-Average Estimators for Non-Convex Optimization
- arxiv url: http://arxiv.org/abs/2104.14840v1
- Date: Fri, 30 Apr 2021 08:50:24 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-03 13:27:51.511087
- Title: On Stochastic Moving-Average Estimators for Non-Convex Optimization
- Title(参考訳): 非凸最適化のための確率移動平均推定器について
- Authors: Zhishuai Guo, Yi Xu, Wotao Yin, Rong Jin, Tianbao Yang
- Abstract要約: 本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
- 参考スコア(独自算出の注目度): 105.22760323075008
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we demonstrate the power of a widely used stochastic estimator
based on moving average (SEMA) on a range of stochastic non-convex optimization
problems, which only requires {\bf a general unbiased stochastic oracle}. We
analyze various stochastic methods (existing or newly proposed) based on the
{\bf variance recursion property} of SEMA for three families of non-convex
optimization, namely standard stochastic non-convex minimization, stochastic
non-convex strongly-concave min-max optimization, and stochastic bilevel
optimization. Our contributions include: (i) for standard stochastic non-convex
minimization, we present a simple and intuitive proof of convergence for a
family Adam-style methods (including Adam) with an increasing or large
"momentum" parameter for the first-order moment, which gives an alternative yet
more natural way to guarantee Adam converge; (ii) for stochastic non-convex
strongly-concave min-max optimization, we present a single-loop stochastic
gradient descent ascent method based on the moving average estimators and
establish its oracle complexity of $O(1/\epsilon^4)$ without using a large
mini-batch size, addressing a gap in the literature; (iii) for stochastic
bilevel optimization, we present a single-loop stochastic method based on the
moving average estimators and establish its oracle complexity of $\widetilde
O(1/\epsilon^4)$ without computing the inverse or SVD of the Hessian matrix,
improving state-of-the-art results. For all these problems, we also establish a
variance diminishing result for the used stochastic gradient estimators.
- Abstract(参考訳): 本稿では,移動平均(SEMA)に基づく確率的推定器の確率的非凸最適化問題に対する有効性を示す。
非凸最適化の3つのファミリー,すなわち標準確率的非凸最小化, 確率的非凸的 min-max 最適化, 確率的バイレベル最適化の3つのファミリに対するSEMAの分散再帰特性に基づいて, 様々な確率的手法(既存または新たに提案)を解析する。
Our contributions include: (i) for standard stochastic non-convex minimization, we present a simple and intuitive proof of convergence for a family Adam-style methods (including Adam) with an increasing or large "momentum" parameter for the first-order moment, which gives an alternative yet more natural way to guarantee Adam converge; (ii) for stochastic non-convex strongly-concave min-max optimization, we present a single-loop stochastic gradient descent ascent method based on the moving average estimators and establish its oracle complexity of $O(1/\epsilon^4)$ without using a large mini-batch size, addressing a gap in the literature; (iii) for stochastic bilevel optimization, we present a single-loop stochastic method based on the moving average estimators and establish its oracle complexity of $\widetilde O(1/\epsilon^4)$ without computing the inverse or SVD of the Hessian matrix, improving state-of-the-art results.
これらの問題に対して、使用済み確率勾配推定器の分散低減結果も確立する。
関連論文リスト
- Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax
Problems [39.197569803430646]
最小限の最適化は、敵対的ネットワーク(GAN)や敵対的トレーニングなど、多くの機械学習タスクにおいて重要な役割を果たす。
近年,ミニマックス問題の解法として多種多様な最適化手法が提案されているが,そのほとんどは分散設定を無視している。
論文 参考訳(メタデータ) (2023-04-21T11:38:41Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳(メタデータ) (2022-12-19T14:48:54Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳(メタデータ) (2022-01-05T15:17:35Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳(メタデータ) (2021-07-02T16:21:52Z) - An Optimal Hybrid Variance-Reduced Algorithm for Stochastic Composite
Nonconvex Optimization [23.355249183979907]
そこで本研究では, [7] におけるハイブリッド分散法の新しい変種を提案し, 標準仮定の下での共通合成非還元問題の解法を提案する。
我々は, [7] に導入した独立な非バイアス推定器を, 同一試料の勾配によって置き換える。
私たちの分析は基本的に[7]にインスパイアされていますが、2つの異なるステップサイズを使用しません。
論文 参考訳(メタデータ) (2020-08-20T16:15:12Z) - Stochastic Proximal Gradient Algorithm with Minibatches. Application to
Large Scale Learning Models [2.384873896423002]
非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。
我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
論文 参考訳(メタデータ) (2020-03-30T10:43:56Z) - Support recovery and sup-norm convergence rates for sparse pivotal
estimation [79.13844065776928]
高次元スパース回帰では、ピボット推定器は最適な正規化パラメータがノイズレベルに依存しない推定器である。
非滑らかで滑らかな単一タスクとマルチタスク正方形ラッソ型推定器に対するミニマックス超ノルム収束率を示す。
論文 参考訳(メタデータ) (2020-01-15T16:11:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。