論文の概要: 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の再スケールされたラストイテレートは、ほぼ最適の共分散を達成するゼロ平均ガウス分布に収束する。
関連論文リスト
- Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳(メタデータ) (2021-12-29T18:46:52Z) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳(メタデータ) (2021-02-05T14:02:20Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳(メタデータ) (2020-06-19T14:11:26Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-14T10:42:23Z) - Asymptotic Analysis of Conditioned Stochastic Gradient Descent [0.0]
本研究では、勾配方向の事前条件付けに基づいて、条件付きSGDと呼ばれる勾配降下法(SGD)アルゴリズムのクラスについて検討する。
ほぼ確実に、独立した関心を持つかもしれない収束結果が提示される。
論文 参考訳(メタデータ) (2020-06-04T10:08:05Z) - S-ADDOPT: Decentralized stochastic first-order optimization over
directed graphs [16.96562173221624]
有向ネットワークノード上に分散する関数のスムーズかつ高コストな関数の和を最小化するために,分散凸最適化を提案する。
特に,各ノードに1次オラクルを仮定するtextbftextttS-ADDOPTアルゴリズムを提案する。
崩壊するステップサイズ$mathcalO (1/k)$に対して、textbfttS-ADDOPT が$mathcalO (1/k)$ で正解に達し、その収束はネットワーク非依存であることを示す。
論文 参考訳(メタデータ) (2020-05-15T21:14:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。