論文の概要: Enhancing Stochastic Gradient Descent: A Unified Framework and Novel
Acceleration Methods for Faster Convergence
- arxiv url: http://arxiv.org/abs/2402.01515v1
- Date: Fri, 2 Feb 2024 15:55:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-05 14:25:58.716522
- Title: Enhancing Stochastic Gradient Descent: A Unified Framework and Novel
Acceleration Methods for Faster Convergence
- Title(参考訳): 確率的勾配降下の促進:統一フレームワークと高速収束のための新しい加速法
- Authors: Yichuan Deng, Zhao Song, Chiwun Yang
- Abstract要約: 2つのプラググルー収束条件下での収束に対処する統一的な枠組みを提案する。
これらの2つの手法が理論的にAインレートに導かれることを示す。
- 参考スコア(独自算出の注目度): 9.668078830796999
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Based on SGD, previous works have proposed many algorithms that have improved
convergence speed and generalization in stochastic optimization, such as SGDm,
AdaGrad, Adam, etc. However, their convergence analysis under non-convex
conditions is challenging. In this work, we propose a unified framework to
address this issue. For any first-order methods, we interpret the updated
direction $g_t$ as the sum of the stochastic subgradient $\nabla f_t(x_t)$ and
an additional acceleration term $\frac{2|\langle v_t, \nabla f_t(x_t)
\rangle|}{\|v_t\|_2^2} v_t$, thus we can discuss the convergence by analyzing
$\langle v_t, \nabla f_t(x_t) \rangle$. Through our framework, we have
discovered two plug-and-play acceleration methods: \textbf{Reject Accelerating}
and \textbf{Random Vector Accelerating}, we theoretically demonstrate that
these two methods can directly lead to an improvement in convergence rate.
- Abstract(参考訳): SGDに基づいて、SGDm、AdaGrad、Adamなどの確率最適化における収束速度と一般化を改善する多くのアルゴリズムが提案されている。
しかし,非凸条件下での収束解析は困難である。
本稿では,この問題に対処するための統一フレームワークを提案する。
任意の一階法に対して、更新された方向 $g_t$ を確率的次数 $\nabla f_t(x_t)$ と追加の加速項 $\frac{2|\langle v_t, \nabla f_t(x_t) \rangle|||v_t\|_2^2} v_t$ の和として解釈する。
提案手法により,2つのプラグ・アンド・プレイ・アクセラレーション法を発見した: \textbf{reject acceleration} と \textbf{random vector acceleration} であり,この2つの手法が直接収束率の向上につながることを理論的に証明した。
関連論文リスト
- Stochastic Newton Proximal Extragradient Method [18.47705532817026]
そこで本稿では,これらの境界を改良するNewton Extragradient法を提案する。
我々はHybrid Proximal Extragradient(HPE)フレームワークを拡張してこれを実現する。
論文 参考訳(メタデータ) (2024-06-03T16:06:23Z) - Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation [51.248784084461334]
我々はNesterov加速度アンダーホ条件の一般化版に対する新しい収束率を証明した。
本分析により, 従来の研究に比べて, 強い成長定数への依存度を$$$から$sqrt$に下げることができた。
論文 参考訳(メタデータ) (2024-04-03T00:41:19Z) - Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth
Convex Optimization [26.328847475942894]
我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。
我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
論文 参考訳(メタデータ) (2023-06-03T23:31:27Z) - Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods [57.050204432302195]
本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。
我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
論文 参考訳(メタデータ) (2022-11-03T14:12:51Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳(メタデータ) (2022-06-17T06:10:20Z) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳(メタデータ) (2022-06-16T17:10:57Z) - Nesterov Accelerated Shuffling Gradient Method for Convex Optimization [15.908060383231371]
このアルゴリズムは,統一シャッフル方式を用いて,$mathcalO (1/T)$の改善率を示す。
我々の収束解析は有界領域や有界勾配条件に関する仮定を必要としない。
数値シミュレーションはアルゴリズムの効率を実証する。
論文 参考訳(メタデータ) (2022-02-07T21:23:17Z) - A Unified Analysis of First-Order Methods for Smooth Games via Integral
Quadratic Constraints [10.578409461429626]
本研究では、滑らかで強可変なゲームやイテレーションのための一階法に積分二次的制約理論を適用する。
我々は、負の運動量法(NM)に対して、既知の下界と一致する複雑性$mathcalO(kappa1.5)$で、初めて大域収束率を与える。
一段階のメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば,高速化は不可能であることを示す。
論文 参考訳(メタデータ) (2020-09-23T20:02:00Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳(メタデータ) (2020-06-19T14:11:26Z) - Almost sure convergence rates for Stochastic Gradient Descent and
Stochastic Heavy Ball [17.33867778750777]
一般近似問題に対する勾配降下法(SGD)と重球法(SHB)について検討した。
SGD の場合、凸と滑らかな設定において、イテレートの重み付き平均に対して、最初の最も確実な収束式を提供する。
論文 参考訳(メタデータ) (2020-06-14T11:12:05Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳(メタデータ) (2020-03-05T01:56:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。