論文の概要: ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single
Algorithm
- arxiv url: http://arxiv.org/abs/2008.12690v1
- Date: Fri, 28 Aug 2020 14:46:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-24 01:58:14.776129
- Title: ROOT-SGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single
Algorithm
- Title(参考訳): ROOT-SGD:1つのアルゴリズムにおけるシャープ非漸近と漸近効率
- Authors: Chris Junchi Li, Wenlong Mou, Martin J. Wainwright, Michael I. Jordan
- Abstract要約: 我々は,過去の勾配を平均化する特定の形態を動機付け,一般統計の観点から一階最適化を考える。
emphRecursive One-Over-T SGD (ROOT-SGD) と呼ばれるこのアルゴリズムは、オンライン近似手法の最先端収束率と一致する。
- 参考スコア(独自算出の注目度): 102.61698955364831
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The theory and practice of stochastic optimization has focused on stochastic
gradient descent (SGD) in recent years, retaining the basic first-order
stochastic nature of SGD while aiming to improve it via mechanisms such as
averaging, momentum, and variance reduction. Improvement can be measured along
various dimensions, however, and it has proved difficult to achieve
improvements both in terms of nonasymptotic measures of convergence rate and
asymptotic measures of distributional tightness. In this work, we consider
first-order stochastic optimization from a general statistical point of view,
motivating a specific form of recursive averaging of past stochastic gradients.
The resulting algorithm, which we refer to as \emph{Recursive One-Over-T SGD}
(ROOT-SGD), matches the state-of-the-art convergence rate among online
variance-reduced stochastic approximation methods. Moreover, under slightly
stronger distributional assumptions, the rescaled last-iterate of ROOT-SGD
converges to a zero-mean Gaussian distribution that achieves near-optimal
covariance.
- Abstract(参考訳): 確率的最適化の理論と実践は、近年、確率的勾配降下(SGD)に焦点を当てており、平均化、運動量、分散還元といったメカニズムにより、SGDの基本的な一階確率的性質を維持している。
しかし、改善は様々な次元で測定できるため、収束率の漸近測度と分布の厳密度の漸近測度の両方において改善を達成することは困難である。
本研究では,従来の確率勾配の帰納的平均化の特定の形態を動機付け,一般統計の観点から一階確率最適化を考える。
結果として得られたアルゴリズムは \emph{recursive one-over-t sgd} (root-sgd) と呼ばれ、オンライン分散還元確率近似法における最先端収束率に一致する。
さらに、わずかに強い分布仮定の下で、ルートsgdの再スケールされたラストイテレートは、ほぼ最適の共分散を達成するゼロ平均ガウス分布に収束する。
関連論文リスト
- On Almost Sure Convergence Rates of Stochastic Gradient Methods [11.367487348673793]
勾配法で得られるほぼ確実な収束速度が、可能な限り最適な収束速度に任意に近づくことを示す。
非客観的関数に対しては、二乗勾配ノルムの重み付き平均がほぼ確実に収束するだけでなく、ほぼ確実に0となることを示す。
論文 参考訳(メタデータ) (2022-02-09T06:05:30Z) - On the Convergence of mSGD and AdaGrad for Stochastic Optimization [0.696125353550498]
凸降下(SGD)は、過去10年間に機械学習に大きく開発され、広く応用されてきた。
モーメントベースのSGD(mSGD)や適応的勾配最適化(AdaGrad)など、多くの競合や応用においてSGDよりも優れている修正SGD型アルゴリズムもある。
我々は,機械学習における任意の滑らかな(不可能かもしれない)損失関数に対するmSGDとAdaGradの収束解析に着目する。
論文 参考訳(メタデータ) (2022-01-26T22:02:21Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳(メタデータ) (2021-07-21T17:10:14Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳(メタデータ) (2021-07-02T16:21:52Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳(メタデータ) (2021-06-30T17:51:36Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳(メタデータ) (2021-04-30T08:50:24Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳(メタデータ) (2021-03-23T17:15:53Z) - Stochastic optimization with momentum: convergence, fluctuations, and
traps avoidance [0.0]
本稿では,重球法,ネステロフ加速勾配法(S-NAG),広く使用されているアダム法など,勾配勾配勾配のいくつかの変種を統一する一般最適化手法について検討する。
この回避は、非自明な常微分方程式のノイズ離散化として研究される。
論文 参考訳(メタデータ) (2020-12-07T19:14:49Z) - Variance Regularization for Accelerating Stochastic Optimization [14.545770519120898]
ミニバッチ勾配に隠れた統計情報を利用してランダムな誤りの蓄積を低減する普遍原理を提案する。
これは、ミニバッチのばらつきに応じて学習率を正規化することで達成される。
論文 参考訳(メタデータ) (2020-08-13T15:34:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。