論文の概要: Better Theory for SGD in the Nonconvex World
- arxiv url: http://arxiv.org/abs/2002.03329v3
- Date: Fri, 24 Jul 2020 15:03:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-02 14:36:55.481640
- Title: Better Theory for SGD in the Nonconvex World
- Title（参考訳）: 非凸世界におけるSGDのより良い理論
- Authors: Ahmed Khaled and Peter Richt\'arik
- Abstract要約: 大規模な非最適化問題は、現代の機械学習ではユビキタスである。
我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
- 参考スコア（独自算出の注目度）: 2.6397379133308214
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Large-scale nonconvex optimization problems are ubiquitous in modern machine
learning, and among practitioners interested in solving them, Stochastic
Gradient Descent (SGD) reigns supreme. We revisit the analysis of SGD in the
nonconvex setting and propose a new variant of the recently introduced expected
smoothness assumption which governs the behaviour of the second moment of the
stochastic gradient. We show that our assumption is both more general and more
reasonable than assumptions made in all prior work. Moreover, our results yield
the optimal $\mathcal{O}(\varepsilon^{-4})$ rate for finding a stationary point
of nonconvex smooth functions, and recover the optimal
$\mathcal{O}(\varepsilon^{-1})$ rate for finding a global solution if the
Polyak-{\L}ojasiewicz condition is satisfied. We compare against convergence
rates under convexity and prove a theorem on the convergence of SGD under
Quadratic Functional Growth and convexity, which might be of independent
interest. Moreover, we perform our analysis in a framework which allows for a
detailed study of the effects of a wide array of sampling strategies and
minibatch sizes for finite-sum optimization problems. We corroborate our
theoretical results with experiments on real and synthetic data.
- Abstract（参考訳）: 大規模な非凸最適化問題は、現代の機械学習では至るところで行われており、SGD(Stochastic Gradient Descent)は、その解決に関心のある実践者の中では、最高である。
我々は,非凸設定におけるsgdの解析を再検討し,確率勾配の第2モーメントの挙動を規定する最近導入された期待平滑性仮定の新しい変種を提案する。
我々の仮定は、以前のすべての作業でなされた仮定よりも一般的で理にかなったものであることを示す。
さらに、この結果から、非凸な滑らかな関数の定常点を求めるための最適な$\mathcal{O}(\varepsilon^{-4})$レートが得られ、Polyak-{\L}ojasiewicz条件を満たす場合、大域的な解を求めるための最適な$\mathcal{O}(\varepsilon^{-1})$レートが回復される。
凸性下の収束率と比較し、二次汎関数成長および凸性の下でのsgdの収束に関する定理を証明する。
さらに,有限サム最適化問題に対する広範囲のサンプリング戦略とミニバッチサイズの影響を詳細に研究するフレームワークを用いて解析を行う。
我々は理論結果を実データと合成データの実験と照合する。
関連論文リスト
- Diffusion Stochastic Optimization for Min-Max Problems [33.73046548872663]
楽観的勾配法はミニマックス最適化問題に対処するのに有用である。
従来のバージョンでは大きなバッチサイズが必要であり,Samevareps-generativeOGOGと呼ばれる新しい定式化を導入,解析する。
論文 参考訳（メタデータ） (2024-01-26T01:16:59Z) - Demystifying the Myths and Legends of Nonconvex Convergence of SGD [17.445810977264067]
勾配勾配勾配(SGD)とその変種は、大規模最適化問題の解法の主要な仕事場である。
分析として,勾配の非収束に関連する神話や伝説について考察した。
論文 参考訳（メタデータ） (2023-10-19T17:58:59Z) - Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective
and Improved Bounds [12.699376765058137]
勾配降下法(SGD)は、おそらく現代の機械学習において最も一般的な最適化法である。
SGDを交換せずにサンプリングするSGDが分析されたのはごく最近のことだ。
データマトリックスに依存し、既存の境界によって予測されるものよりも決して悪くない、きめ細かい複雑性境界を証明します。
論文 参考訳（メタデータ） (2023-06-21T18:14:44Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
論文 参考訳（メタデータ） (2022-06-30T02:17:11Z) - Sharper Rates and Flexible Framework for Nonconvex SGD with Client and
Data Sampling [64.31011847952006]
我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。
我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。
我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
論文 参考訳（メタデータ） (2022-06-05T21:32:33Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳（メタデータ） (2021-08-25T21:30:27Z) - A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。
PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
論文 参考訳（メタデータ） (2021-07-23T19:38:17Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and
Interpolation [17.199023009789308]
予想されるSGD(SGD)の仮定は、非アーティザン関数に対して日常的に使われている。
本稿では,スムーズな非線形設定への収束のパラダイムを示す。
また,異なるステップサイズ条件の理論的保証も提供する。
論文 参考訳（メタデータ） (2020-06-18T07:05:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。