論文の概要: Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent
- arxiv url: http://arxiv.org/abs/2110.11442v1
- Date: Thu, 21 Oct 2021 19:22:14 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-26 03:48:38.392056
- Title: Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent
- Title（参考訳）: 雑音適応型, 問題適応型確率的勾配
- Authors: Sharan Vaswani, Benjamin Dubois-Taine, Reza Babanezhad
- Abstract要約: 雑音に対して勾配降下(SGD)を適応させるステップサイズスキームを設計する。
我々は、Nesterov反復によるSGDの$T$反復がほぼ最適であることを示す。
他のステップサイズスキームと比較して、新しい指数的なステップサイズスキームの有効性を実証する。
- 参考スコア（独自算出の注目度）: 7.176107039687231
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We design step-size schemes that make stochastic gradient descent (SGD)
adaptive to (i) the noise $\sigma^2$ in the stochastic gradients and (ii)
problem-dependent constants. When minimizing smooth, strongly-convex functions
with condition number $\kappa$, we first prove that $T$ iterations of SGD with
Nesterov acceleration and exponentially decreasing step-sizes can achieve a
near-optimal $\tilde{O}(\exp(-T/\sqrt{\kappa}) + \sigma^2/T)$ convergence rate.
Under a relaxed assumption on the noise, with the same step-size scheme and
knowledge of the smoothness, we prove that SGD can achieve an
$\tilde{O}(\exp(-T/\kappa) + \sigma^2/T)$ rate. In order to be adaptive to the
smoothness, we use a stochastic line-search (SLS) and show (via upper and
lower-bounds) that SGD converges at the desired rate, but only to a
neighbourhood of the solution. Next, we use SGD with an offline estimate of the
smoothness and prove convergence to the minimizer. However, its convergence is
slowed down proportional to the estimation error and we prove a lower-bound
justifying this slowdown. Compared to other step-size schemes, we empirically
demonstrate the effectiveness of exponential step-sizes coupled with a novel
variant of SLS.
- Abstract（参考訳）: 確率勾配降下(SGD)を適応させるステップサイズスキームを設計する。
(i)確率勾配における雑音$\sigma^2$
(ii)問題依存定数。
条件数$\kappa$で滑らかで強凸な関数を最小化する場合、まず、Nesterov加速度と指数関数的に減少するステップサイズを持つSGDの反復が、ほぼ最適の $\tilde{O}(\exp(-T/\sqrt{\kappa}) + \sigma^2/T)$収束率が得られることを証明する。
雑音の緩和された仮定の下では、同じステップサイズスキームと滑らかさの知識で、SGD が $\tilde{O}(\exp(-T/\kappa) + \sigma^2/T)$ rate を達成できることを示す。
滑らかさに適応するために、確率線探索(SLS)を用いて、SGDが所望の速度で収束することを示すが、解の近傍にのみ適用できることを示す。
次に、滑らかさのオフライン推定でSGDを使用し、最小値への収束を証明する。
しかし、その収束は推定誤差に比例して遅くなり、この減速を正当化する下限が証明される。
他のステップサイズスキームと比較して,指数的ステップサイズの有効性を新しいslsと組み合わせて実証的に実証する。
関連論文リスト
- Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - Two Sides of One Coin: the Limits of Untuned SGD and the Power of
Adaptive Methods [22.052459124774504]
本研究では,未調整のSGDに対する適応的手法により,スムーズさと情報優位性で問題を緩和することを示す。
この結果から, 指数関数依存性が欠如している場合, 未修正SGDに対する適応手法の理論的正当性について検討した。
論文 参考訳（メタデータ） (2023-05-21T14:40:43Z) - STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。
我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
論文 参考訳（メタデータ） (2021-11-01T15:43:36Z) - A Variance Controlled Stochastic Method with Biased Estimation for
Faster Non-convex Optimization [0.0]
減少勾配(SVRG)の性能を向上させるために, 分散制御勾配(VCSG)という新しい手法を提案する。
ラムダ$はVCSGで導入され、SVRGによる分散の過剰還元を避ける。
$mathcalO(min1/epsilon3/2,n1/4/epsilon)$ 勾配評価の数。
論文 参考訳（メタデータ） (2021-02-19T12:22:56Z) - On the Convergence of Step Decay Step-Size for Stochastic Optimization [27.02857082612736]
神経系の収束は、特にネットワーク問題などの非数学問題において、ステップサイズ率に大きく依存する。
非スムース状態における崩壊の収束を提供し、勾配ノルムが消えることを保証する。
強い凸の場合、$(T/ST)$レートを確立し、$(T/ST)$レートであることも証明します。
論文 参考訳（メタデータ） (2021-02-18T14:37:25Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳（メタデータ） (2020-10-19T15:23:18Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳（メタデータ） (2020-07-02T16:02:02Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。