論文の概要: On Underdamped Nesterov's Acceleration
- arxiv url: http://arxiv.org/abs/2304.14642v1
- Date: Fri, 28 Apr 2023 06:08:19 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-01 15:05:38.350655
- Title: On Underdamped Nesterov's Acceleration
- Title（参考訳）: ネステロフの加速に就て
- Authors: Shuo Chen, Bin Shi, Ya-xiang Yuan
- Abstract要約: ネステロフ加速勾配降下法のための高分解能微分方程式フレームワーク
アンダーダムケースのための新しいリャプノフ関数が構築されている。
収束率は、$r=-1$のアンダーダムの場合と一致する。
- 参考スコア（独自算出の注目度）: 6.53306151979817
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: The high-resolution differential equation framework has been proven to be
tailor-made for Nesterov's accelerated gradient descent method~(\texttt{NAG})
and its proximal correspondence -- the class of faster iterative shrinkage
thresholding algorithms (FISTA). However, the systems of theories is not still
complete, since the underdamped case ($r < 2$) has not been included. In this
paper, based on the high-resolution differential equation framework, we
construct the new Lyapunov functions for the underdamped case, which is
motivated by the power of the time $t^{\gamma}$ or the iteration $k^{\gamma}$
in the mixed term. When the momentum parameter $r$ is $2$, the new Lyapunov
functions are identical to the previous ones. These new proofs do not only
include the convergence rate of the objective value previously obtained
according to the low-resolution differential equation framework but also
characterize the convergence rate of the minimal gradient norm square. All the
convergence rates obtained for the underdamped case are continuously dependent
on the parameter $r$. In addition, it is observed that the high-resolution
differential equation approximately simulates the convergence behavior
of~\texttt{NAG} for the critical case $r=-1$, while the low-resolution
differential equation degenerates to the conservative Newton's equation. The
high-resolution differential equation framework also theoretically
characterizes the convergence rates, which are consistent with that obtained
for the underdamped case with $r=-1$.
- Abstract（参考訳）: 高分解能微分方程式フレームワークは、Nesterovの加速勾配降下法~(\texttt{NAG})とその近位対応 -- より高速な反復収縮しきい値アルゴリズム(FISTA)のクラスのために調整されたことが証明されている。
しかし、未成年の場合(r < 2$)は含まれていないため、理論体系はまだ完成していない。
本稿では,高分解能微分方程式の枠組みに基づいて,混合項における時間 $t^{\gamma}$ または反復 $k^{\gamma}$ のパワーを動機とする,弱減衰の場合の新しいリアプノフ関数を構築する。
運動量パラメータ $r$ が 2$ であるとき、新しいリャプノフ函数は以前のものと同じである。
これらの新しい証明は、低分解能微分方程式の枠組みに従って得られた目的値の収束率だけでなく、極小勾配ノルム二乗の収束率も含んでいる。
劣化したケースで得られるすべての収束率は、パラメータ $r$ に継続的に依存する。
さらに、高分解能微分方程式は臨界の場合 $r=-1$ に対して~\texttt{NAG} の収束挙動を概ねシミュレートし、低分解能微分方程式は保守ニュートン方程式に退化する。
高分解能微分方程式フレームワークも理論的に収束率を特徴付けており、これは下水の場合の$r=-1$と一致する。
関連論文リスト
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation [51.248784084461334]
我々はNesterov加速度アンダーホ条件の一般化版に対する新しい収束率を証明した。
本分析により, 従来の研究に比べて, 強い成長定数への依存度を$$$から$sqrt$に下げることができた。
論文 参考訳（メタデータ） (2024-04-03T00:41:19Z) - Over-Parameterization Exponentially Slows Down Gradient Descent for
Learning a Single Neuron [49.45105570960104]
ランダム勾配降下のグローバル収束を$Oleft(T-3right)$ rateで証明する。
これら2つの境界は、収束率の正確な特徴づけを与える。
このポテンシャル関数は緩やかに収束し、損失関数の緩やかな収束率を示す。
論文 参考訳（メタデータ） (2023-02-20T15:33:26Z) - Revisiting the acceleration phenomenon via high-resolution differential
equations [6.53306151979817]
ネステロフの加速勾配降下(NAG)は、一階アルゴリズムの歴史におけるマイルストーンの1つである。
Lyapunov解析と位相空間表現に基づく$mu$-strongly convex関数のNAGについて検討する。
NAGの暗黙的速度スキームによる高分解能微分方程式の枠組みは完璧であり、勾配補正スキームよりも優れていた。
論文 参考訳（メタデータ） (2022-12-12T04:36:37Z) - Proximal Subgradient Norm Minimization of ISTA and FISTA [8.261388753972234]
反復収縮保持アルゴリズムのクラスに対する2乗近位次数ノルムは逆2乗率で収束することを示す。
また、高速反復収縮保持アルゴリズム (FISTA) のクラスに対する2乗次次数次ノルムが、逆立方レートで収束するように加速されることも示している。
論文 参考訳（メタデータ） (2022-11-03T06:50:19Z) - A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
Yang et al. (2023) は最近、一般的な変分不等式を解決するために一階勾配法を使う方法を示した。
この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone である場合、この手法の最後の繰り返しのギャップ関数が$O(frac1sqrtK)$で減少することを示す。
論文 参考訳（メタデータ） (2022-10-27T17:59:09Z) - Gradient Norm Minimization of Nesterov Acceleration: $o(1/k^3)$ [6.53306151979817]
ネステロフの加速勾配降下(NAG)は、一階アルゴリズムのマイルストーンの1つである。
本稿では, 高精度な観測と, より厳密な不等式に基づく, より単純化された証明を提案する。
論文 参考訳（メタデータ） (2022-09-19T09:10:35Z) - A globally convergent fast iterative shrinkage-thresholding algorithm
with a new momentum factor for single and multi-objective convex optimization [0.0]
提案手法はまた,任意の$(a,b)$に対して,大域収束率$O(1/k2)$を持つことを示す。
様々な$(a,b)$で数値結果を報告し、これらの選択のいくつかが古典的な運動量因子よりも良い結果をもたらすことを示す。
論文 参考訳（メタデータ） (2022-05-11T04:26:00Z) - 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) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳（メタデータ） (2020-10-19T15:23:18Z) - Cumulant GAN [17.4556035872983]
GAN(Generative Adversarial Networks)を学習するための新しい損失関数を提案する。
対応する最適化問題は R'enyi divergence minimization と同値であることを示す。
我々は,画像生成がWasserstein GANに対してより堅牢であることを実験的に実証した。
論文 参考訳（メタデータ） (2020-06-11T17:23:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。