論文の概要: Lyapunov Analysis For Monotonically Forward-Backward Accelerated Algorithms
- arxiv url: http://arxiv.org/abs/2412.13527v1
- Date: Wed, 18 Dec 2024 06:09:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-19 13:23:21.535692
- Title: Lyapunov Analysis For Monotonically Forward-Backward Accelerated Algorithms
- Title（参考訳）: 単調前方加速アルゴリズムのためのリアプノフ解析
- Authors: Mingwei Fu, Bin Shi,
- Abstract要約: ネステロフの加速勾配法(NAG)は勾配に基づく最適化の目覚ましい進歩である。
強凸函数に対しては、NAG が線型収束するかどうかは開問題である。
我々は、勾配項を導入して反復関係を修正し、新しい勾配に基づく反復関係を導出する。
- 参考スコア（独自算出の注目度）: 4.404496835736175
- License:
- Abstract: In the realm of gradient-based optimization, Nesterov's accelerated gradient method (NAG) is a landmark advancement, achieving an accelerated convergence rate that outperforms the vanilla gradient descent method for convex function. However, for strongly convex functions, whether NAG converges linearly remains an open question, as noted in the comprehensive review by Chambolle and Pock [2016]. This issue, aside from the critical step size, was addressed by Li et al. [2024a] using a high-resolution differential equation framework. Furthermore, Beck [2017, Section 10.7.4] introduced a monotonically convergent variant of NAG, referred to as M-NAG. Despite these developments, the Lyapunov analysis presented in [Li et al., 2024a] cannot be directly extended to M-NAG. In this paper, we propose a modification to the iterative relation by introducing a gradient term, leading to a new gradient-based iterative relation. This adjustment allows for the construction of a novel Lyapunov function that excludes kinetic energy. The linear convergence derived from this Lyapunov function is independent of both the parameters of the strongly convex functions and the step size, yielding a more general and robust result. Notably, we observe that the gradient iterative relation derived from M-NAG is equivalent to that from NAG when the position-velocity relation is applied. However, the Lyapunov analysis does not rely on the position-velocity relation, allowing us to extend the linear convergence to M-NAG. Finally, by utilizing two proximal inequalities, which serve as the proximal counterparts of strongly convex inequalities, we extend the linear convergence to both the fast iterative shrinkage-thresholding algorithm (FISTA) and its monotonic counterpart (M-FISTA).
- Abstract（参考訳）: 勾配に基づく最適化の分野では、ネステロフの加速勾配法(NAG)は目覚ましい進歩であり、凸関数のバニラ勾配勾配法よりも優れた加速収束率を達成する。
しかし、強い凸函数の場合、NAG が線型収束するかどうかは、Chambolle と Pock [2016] の包括的なレビューで述べられているように、未解決の問題である。
この問題は、臨界ステップサイズを除いて、高分解能微分方程式フレームワークを用いてLi et al [2024a] によって解決された。
さらに、Beck [2017, Section 10.7.4] は単調収束型 NAG (M-NAG) を導入した。
これらの発展にもかかわらず, [Li et al , 2024a] で示されるリャプノフ解析は直接 M-NAG に拡張することはできない。
本稿では、勾配項を導入して反復関係を修正し、新しい勾配に基づく反復関係を導出する。
この調整により、運動エネルギーを排除した新しいリャプノフ函数を構築することができる。
このリャプノフ函数から導かれる線型収束は、強い凸函数のパラメータとステップサイズの両方に独立であり、より一般かつ堅牢な結果をもたらす。
特に,M-NAGから導出される勾配反復関係は,位置-速度関係が適用された場合,NAGから導かれる勾配反復関係と等価である。
しかし、リアプノフ解析は位置-速度関係に頼らず、線型収束をM-NAGに拡張することができる。
最後に、強い凸不等式の近位不等式として機能する2つの近位不等式を利用することにより、線形収束を高速反復収縮保持アルゴリズム(FISTA)と単調不等式(M-FISTA)の両方に拡張する。
関連論文リスト
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity [16.779513676120096]
我々は、最適化の経路に沿った目的の条件付けに依存する勾配降下に対する新しい準最適境界を開発する。
我々の証明の鍵となるのは方向の滑らかさであり、これは、目的の上のバウンドを開発するために使用する勾配変動の尺度である。
我々は,方向の滑らかさの知識を使わずとも,ポリアクのステップサイズと正規化GDが高速で経路依存の速度を得ることを示した。
論文 参考訳（メタデータ） (2024-03-06T22:24:05Z) - Convergence Analysis of Fractional Gradient Descent [0.0]
最適化のためには、分数微分を用いて性質の収束を理解することが重要である。
本稿では,分数勾配降下のポテンシャルを解析する。
実験結果が提示されます
論文 参考訳（メタデータ） (2023-11-30T10:24:07Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - Linear convergence of forward-backward accelerated algorithms without knowledge of the modulus of strong convexity [14.0409219811182]
我々はネステロフの加速勾配降下(NAG)とFISTAの両方が強い凸関数に対して線形収束を示すことを示した。
我々は、運動エネルギーの動的適応係数を含むリアプノフ関数の創出に際し、特異なアプローチを強調した。
論文 参考訳（メタデータ） (2023-06-16T08:58:40Z) - Convergence of mean-field Langevin dynamics: Time and space
discretization, stochastic gradient, and variance reduction [49.66486092259376]
平均場ランゲヴィンダイナミクス(英: mean-field Langevin dynamics、MFLD)は、分布依存のドリフトを含むランゲヴィン力学の非線形一般化である。
近年の研究では、MFLDは測度空間で機能するエントロピー規則化された凸関数を地球規模で最小化することが示されている。
有限粒子近似,時間分散,勾配近似による誤差を考慮し,MFLDのカオスの均一時間伝播を示す枠組みを提供する。
論文 参考訳（メタデータ） (2023-06-12T16:28:11Z) - Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。
最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
論文 参考訳（メタデータ） (2023-06-02T04:21:59Z) - 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) - Convex Analysis of the Mean Field Langevin Dynamics [49.66486092259375]
平均場ランゲヴィン力学の収束速度解析について述べる。
ダイナミックスに付随する$p_q$により、凸最適化において古典的な結果と平行な収束理論を開発できる。
論文 参考訳（メタデータ） (2022-01-25T17:13:56Z) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳（メタデータ） (2021-12-29T18:46:52Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。