論文の概要: ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm

• arxiv url: http://arxiv.org/abs/2008.12690v4
• Date: Tue, 17 Sep 2024 19:46:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-09-20 00:13:22.785008
• Title: ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm
• Title（参考訳）: ROOT-SGD:1つのアルゴリズムにおけるシャープ非漸近と準最適漸近
• Authors: Chris Junchi Li, Wenlong Mou, Martin J. Wainwright, Michael I. Jordan,
• Abstract要約: 第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。 我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。 有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
• 参考スコア（独自算出の注目度）: 71.13558000599839
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of solving strongly convex and smooth unconstrained optimization problems using stochastic first-order algorithms. We devise a novel algorithm, referred to as Recursive One-Over-T SGD (ROOT-SGD), based on an easily implementable, recursive averaging of past stochastic gradients. We prove that it simultaneously achieves state-of-the-art performance in both a finite-sample, nonasymptotic sense and an asymptotic sense. On the non-asymptotic side, we prove risk bounds on the last iterate of ROOT-SGD with leading-order terms that match the optimal statistical risk with a unity pre-factor, along with a higher-order term that scales at the sharp rate of $O(n^{-3/2})$ under the Lipschitz condition on the Hessian matrix. On the asymptotic side, we show that when a mild, one-point Hessian continuity condition is imposed, the rescaled last iterate of (multi-epoch) ROOT-SGD converges asymptotically to a Gaussian limit with the Cram\'er-Rao optimal asymptotic covariance, for a broad range of step-size choices.
• Abstract（参考訳）: 確率的一階法アルゴリズムを用いて,厳密な凸と滑らかな非拘束最適化問題の解法について検討する。 本稿では,従来の確率勾配を再現可能な再帰的平均化に基づいて,再帰的1-Over-T SGD (ROOT-SGD) と呼ばれる新しいアルゴリズムを考案する。 有限サンプル, 漸近感覚, 漸近感覚の両方において, 同時に最先端の演奏を達成できることを実証する。 非漸近的な面において、ROOT-SGD の最終反復項に、最適統計リスクとユニティ事前因子とを一致させる先行項と、ヘッセン行列上のリプシッツ条件の下では$O(n^{-3/2})$の急速でスケールする高次項とのリスク境界を証明している。 漸近的側面から、軽度で一点のヘッセン連続性条件が課されると、(多重エポック) ROOT-SGD の再スケールされた最後の反復は、幅広いステップサイズの選択に対して、Cram\'er-Rao 最適漸近共分散を伴うガウス極限に漸近的に収束することを示す。

関連論文リスト

• Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation [22.652143194356864]
  ステップサイズが一定となる勾配勾配(SGD)アルゴリズムを用いて, 強い凸と滑らかな問題を解く問題に対処する。 得られた推定子の平均二乗誤差を$n$の反復数に対して拡張する。 我々は、この鎖が定義された重み付きワッサーシュタイン半計量に関して幾何学的にエルゴード的であることを確証する。
  論文  参考訳（メタデータ） (2024-10-07T15:02:48Z)
• 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)

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

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