論文の概要: Gradient Norm Minimization of Nesterov Acceleration: $o(1/k^3)$
- arxiv url: http://arxiv.org/abs/2209.08862v1
- Date: Mon, 19 Sep 2022 09:10:35 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-20 20:25:41.054739
- Title: Gradient Norm Minimization of Nesterov Acceleration: $o(1/k^3)$
- Title（参考訳）: ネステロフ加速の勾配ノルム最小化:$o(1/k^3)$
- Authors: Shuo Chen, Bin Shi, Ya-xiang Yuan
- Abstract要約: ネステロフの加速勾配降下(NAG)は、一階アルゴリズムのマイルストーンの1つである。
本稿では, 高精度な観測と, より厳密な不等式に基づく, より単純化された証明を提案する。
- 参考スコア（独自算出の注目度）: 6.53306151979817
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In the history of first-order algorithms, Nesterov's accelerated gradient
descent (NAG) is one of the milestones. However, the cause of the acceleration
has been a mystery for a long time. It has not been revealed with the existence
of gradient correction until the high-resolution differential equation
framework proposed in [Shi et al., 2021]. In this paper, we continue to
investigate the acceleration phenomenon. First, we provide a significantly
simplified proof based on precise observation and a tighter inequality for
$L$-smooth functions. Then, a new implicit-velocity high-resolution
differential equation framework, as well as the corresponding implicit-velocity
version of phase-space representation and Lyapunov function, is proposed to
investigate the convergence behavior of the iterative sequence
$\{x_k\}_{k=0}^{\infty}$ of NAG. Furthermore, from two kinds of phase-space
representations, we find that the role played by gradient correction is
equivalent to that by velocity included implicitly in the gradient, where the
only difference comes from the iterative sequence $\{y_{k}\}_{k=0}^{\infty}$
replaced by $\{x_k\}_{k=0}^{\infty}$. Finally, for the open question of whether
the gradient norm minimization of NAG has a faster rate $o(1/k^3)$, we figure
out a positive answer with its proof. Meanwhile, a faster rate of objective
value minimization $o(1/k^2)$ is shown for the case $r > 2$.
- Abstract（参考訳）: 一階アルゴリズムの歴史において、ネステロフの加速勾配降下(NAG)はマイルストーンの1つである。
しかし、加速の原因は長い間謎に包まれてきた。
勾配補正の存在は [shi et al., 2021] で提案された高分解能微分方程式の枠組みまで明らかにされていない。
本稿では,加速度現象の研究を継続する。
まず,l$-smooth関数に対する厳密な観測とより厳密な不等式に基づく,大幅に単純化された証明を提供する。
次に,nagの反復列$\{x_k\}_{k=0}^{\infty}$の収束挙動を調べるために,位相空間表現とリアプノフ関数の対応する暗黙的速度バージョンとともに,新しい暗黙的速度高分解能微分方程式フレームワークを提案する。
さらに, 2種類の位相空間表現から, 勾配補正が果たす役割は, 勾配に暗黙的に包含される速度と等価であり, 反復列 $\{y_{k}\}_{k=0}^{\infty}$ が$\{x_k\}_{k=0}^{\infty}$ に置き換えられる唯一の差異であることがわかった。
最後に、nag の勾配ノルム最小化がより速いレート $o(1/k^3)$ を持つかどうかという疑問に対して、その証明で正の答えを求める。
一方、$r > 2$の場合、目的値最小化$o(1/k^2)$の高速化率を示す。
関連論文リスト
- Anytime Acceleration of Gradient Descent [92.02082223856479]
我々は,任意の停止時間に対して,勾配降下が$O(T-1.03)$の収束保証を達成するための段階的スケジュールを提案する。
我々はこの理論を拡張して、滑らかで強い凸最適化のために$exp(-Omega(T/kappa0.97)$の収束を保証する。
論文 参考訳（メタデータ） (2024-11-26T18:29:44Z) - Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients [0.196629787330046]
目的関数の部分的な2次情報を組み込むことで、分散還元勾配法のミニバッチサイズに対するロバスト性を劇的に向上させることができることを示す。
本稿では,この現象をプロトタイプNewton(textttMb-SVRN$)アルゴリズムで示す。
論文 参考訳（メタデータ） (2024-04-23T05:45:52Z) - Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth
Convex Optimization [26.328847475942894]
我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。
我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
論文 参考訳（メタデータ） (2023-06-03T23:31:27Z) - On Underdamped Nesterov's Acceleration [6.53306151979817]
ネステロフ加速勾配降下法のための高分解能微分方程式フレームワーク
アンダーダムケースのための新しいリャプノフ関数が構築されている。
収束率は、$r=-1$のアンダーダムの場合と一致する。
論文 参考訳（メタデータ） (2023-04-28T06:08:19Z) - Revisiting the acceleration phenomenon via high-resolution differential
equations [6.53306151979817]
ネステロフの加速勾配降下(NAG)は、一階アルゴリズムの歴史におけるマイルストーンの1つである。
Lyapunov解析と位相空間表現に基づく$mu$-strongly convex関数のNAGについて検討する。
NAGの暗黙的速度スキームによる高分解能微分方程式の枠組みは完璧であり、勾配補正スキームよりも優れていた。
論文 参考訳（メタデータ） (2022-12-12T04:36:37Z) - Generalization Bounds for Gradient Methods via Discrete and Continuous
Prior [8.76346911214414]
次数$O(frac1n + fracL2nsum_t=1T(gamma_t/varepsilon_t)2)$の新たな高確率一般化境界を示す。
また、あるSGDの変種に対する新しい境界を得ることもできる。
論文 参考訳（メタデータ） (2022-05-27T07:23:01Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - Restarted Nonconvex Accelerated Gradient Descent: No More
Polylogarithmic Factor in the $O(\epsilon^{-7/4})$ Complexity [70.65867695317633]
本稿では,2つの単純な加速勾配法,再発進勾配降下法(AGD)と再発進球法(HB)を提案する。
我々は、我々の手法が$frac1epsilon)$の勾配反復数を達成することを確証する。
我々のアルゴリズムは、ネストフの古典的なAGDオークのHBと再起動機構のみからなるという意味では単純である。
論文 参考訳（メタデータ） (2022-01-27T10:04:04Z) - A New Framework for Variance-Reduced Hamiltonian Monte Carlo [88.84622104944503]
分散還元型ハミルトン・モンテカルロ法 (HMC) の新たなフレームワークを提案し,$L$-smooth および $m$-strongly log-concave 分布からサンプリングする。
本研究では,SAGA法やSVRG法をベースとした非バイアス勾配推定器を用いて,バッチサイズを小さくすることで,高い勾配効率が得られることを示す。
総合的および実世界のベンチマークデータによる実験結果から、我々の新しいフレームワークは、完全な勾配と勾配HMCアプローチを著しく上回っていることが示された。
論文 参考訳（メタデータ） (2021-02-09T02:44:24Z) - 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) - Differentially Quantized Gradient Methods [53.3186247068836]
微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。
あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
論文 参考訳（メタデータ） (2020-02-06T20:40:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。