論文の概要: 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の再スケールされたラストイテレートは、ほぼ最適の共分散を達成するゼロ平均ガウス分布に収束する。

関連論文リスト

• Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation [22.652143194356864]
  ステップサイズが一定となる勾配勾配(SGD)アルゴリズムを用いて, 強い凸と滑らかな問題を解く問題に対処する。 得られた推定子の平均二乗誤差を$n$の反復数に対して拡張する。 我々は、この鎖が定義された重み付きワッサーシュタイン半計量に関して幾何学的にエルゴード的であることを確証する。
  論文  参考訳（メタデータ） (2024-10-07T15:02:48Z)
• Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation [5.945710235932345]
  本稿では,長期平均報酬設定における関数近似を用いた最初の2段階の批評家・アクターアルゴリズムを提案する。 また、そのようなスキームに対する収束解析と同様に、最初の有限時間非漸近アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-02T12:48:49Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• 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)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• 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)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。