論文の概要: SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and
Interpolation
- arxiv url: http://arxiv.org/abs/2006.10311v3
- Date: Mon, 22 Mar 2021 14:31:30 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-19 13:22:46.823959
- Title: SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and
Interpolation
- Title（参考訳）: 構造化非凸関数のためのSGD:学習率、最小化、補間
- Authors: Robert M. Gower, Othmane Sebbouh, Nicolas Loizou
- Abstract要約: 予想されるSGD(SGD)の仮定は、非アーティザン関数に対して日常的に使われている。
本稿では,スムーズな非線形設定への収束のパラダイムを示す。
また,異なるステップサイズ条件の理論的保証も提供する。
- 参考スコア（独自算出の注目度）: 17.199023009789308
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic Gradient Descent (SGD) is being used routinely for optimizing
non-convex functions. Yet, the standard convergence theory for SGD in the
smooth non-convex setting gives a slow sublinear convergence to a stationary
point. In this work, we provide several convergence theorems for SGD showing
convergence to a global minimum for non-convex problems satisfying some extra
structural assumptions. In particular, we focus on two large classes of
structured non-convex functions: (i) Quasar (Strongly) Convex functions (a
generalization of convex functions) and (ii) functions satisfying the
Polyak-Lojasiewicz condition (a generalization of strongly-convex functions).
Our analysis relies on an Expected Residual condition which we show is a
strictly weaker assumption than previously used growth conditions, expected
smoothness or bounded variance assumptions. We provide theoretical guarantees
for the convergence of SGD for different step-size selections including
constant, decreasing and the recently proposed stochastic Polyak step-size. In
addition, all of our analysis holds for the arbitrary sampling paradigm, and as
such, we give insights into the complexity of minibatching and determine an
optimal minibatch size. Finally, we show that for models that interpolate the
training data, we can dispense of our Expected Residual condition and give
state-of-the-art results in this setting.
- Abstract（参考訳）: Stochastic Gradient Descent (SGD) は非凸関数の最適化に常用されている。
しかし、滑らかな非凸設定におけるSGDの標準収束理論は、定常点への遅い部分線型収束を与える。
本研究では,超構造的仮定を満たす非凸問題に対する大域的最小値への収束を示すsgdに対するいくつかの収束定理を提案する。
特に、構造化非凸関数の2つの大きなクラスに焦点を当てます。
(i)凸関数(凸関数の一般化)および(Strongly)凸関数
(ii)polyak-lojasiewicz条件を満たす関数(強凸関数の一般化)。
本解析では, 従来使用していた成長条件, 期待平滑性, 有界分散条件よりも厳密な弱さが期待残余条件に依拠する。
我々は、定数、減少、最近提案された確率的ポリアクステップサイズを含む異なるステップサイズ選択に対するSGDの収束に関する理論的保証を提供する。
さらに,任意のサンプリングパラダイムを解析対象とし,ミニバッチの複雑さに関する洞察を与え,最適なミニバッチサイズを決定する。
最後に、トレーニングデータを補間するモデルに対して、期待された残余条件を不要にし、この設定で最新結果を得られることを示す。
関連論文リスト
- Taming Nonconvex Stochastic Mirror Descent with General Bregman
Divergence [25.717501580080846]
本稿では、現代の非最適化設定における勾配フォワードミラー(SMD)の収束を再考する。
トレーニングのために,線形ネットワーク問題に対する確率収束アルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-02-27T17:56:49Z) - Demystifying the Myths and Legends of Nonconvex Convergence of SGD [17.445810977264067]
勾配勾配勾配(SGD)とその変種は、大規模最適化問題の解法の主要な仕事場である。
分析として,勾配の非収束に関連する神話や伝説について考察した。
論文 参考訳（メタデータ） (2023-10-19T17:58:59Z) - On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。
本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
論文 参考訳（メタデータ） (2023-05-30T17:47:27Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - Statistical Optimality of Divide and Conquer Kernel-based Functional
Linear Regression [1.7227952883644062]
本稿では,対象関数が基礎となるカーネル空間に存在しないシナリオにおいて,分割・コンカレント推定器の収束性能について検討する。
分解に基づくスケーラブルなアプローチとして、関数線形回帰の分割・収束推定器は、時間とメモリにおけるアルゴリズムの複雑さを大幅に減らすことができる。
論文 参考訳（メタデータ） (2022-11-20T12:29:06Z) - A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。
PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
論文 参考訳（メタデータ） (2021-07-23T19:38:17Z) - Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth
Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。
定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。
我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
論文 参考訳（メタデータ） (2021-06-30T18:32:46Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。
このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文 参考訳（メタデータ） (2020-10-31T21:35:42Z) - An improved convergence analysis for decentralized online stochastic
non-convex optimization [17.386715847732468]
本稿では,GT-Loakjasiewics(GT-Loakjasiewics)と呼ばれる手法が,GT-Loakjasiewics(GT-Loakjasiewics)が現在の収束率を満たすことを示す。
結果はすぐに適用できるだけでなく、現在知られている最高の収束率にも適用できる。
論文 参考訳（メタデータ） (2020-08-10T15:29:13Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳（メタデータ） (2020-06-12T00:32:21Z) - Better Theory for SGD in the Nonconvex World [2.6397379133308214]
大規模な非最適化問題は、現代の機械学習ではユビキタスである。
我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
論文 参考訳（メタデータ） (2020-02-09T09:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。