論文の概要: Linear convergence of forward-backward accelerated algorithms without knowledge of the modulus of strong convexity
- arxiv url: http://arxiv.org/abs/2306.09694v2
- Date: Tue, 9 Apr 2024 00:43:58 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-10 20:36:08.080707
- Title: Linear convergence of forward-backward accelerated algorithms without knowledge of the modulus of strong convexity
- Title（参考訳）: 強凸の係数の知識のない前方加速アルゴリズムの線形収束
- Authors: Bowen Li, Bin Shi, Ya-xiang Yuan,
- Abstract要約: 我々はネステロフの加速勾配降下(NAG)とFISTAの両方が強い凸関数に対して線形収束を示すことを示した。
我々は、運動エネルギーの動的適応係数を含むリアプノフ関数の創出に際し、特異なアプローチを強調した。
- 参考スコア（独自算出の注目度）: 14.0409219811182
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: A significant milestone in modern gradient-based optimization was achieved with the development of Nesterov's accelerated gradient descent (NAG) method. This forward-backward technique has been further advanced with the introduction of its proximal generalization, commonly known as the fast iterative shrinkage-thresholding algorithm (FISTA), which enjoys widespread application in image science and engineering. Nonetheless, it remains unclear whether both NAG and FISTA exhibit linear convergence for strongly convex functions. Remarkably, these algorithms demonstrate convergence without requiring any prior knowledge of strongly convex modulus, and this intriguing characteristic has been acknowledged as an open problem in the comprehensive review [Chambolle and Pock, 2016, Appendix B]. In this paper, we address this question by utilizing the high-resolution ordinary differential equation (ODE) framework. Expanding upon the established phase-space representation, we emphasize the distinctive approach employed in crafting the Lyapunov function, which involves a dynamically adapting coefficient of kinetic energy that evolves throughout the iterations. Furthermore, we highlight that the linear convergence of both NAG and FISTA is independent of the parameter $r$. Additionally, we demonstrate that the square of the proximal subgradient norm likewise advances towards linear convergence.
- Abstract（参考訳）: 現代の勾配に基づく最適化における重要なマイルストーンは、ネステロフの加速勾配降下法(NAG)の開発によって達成された。
このフォワードバックワード技術は、画像科学や工学に広く応用される高速反復収縮保持アルゴリズム(FISTA)を導入してさらに進歩した。
それでも、NAG と FISTA の両方が強い凸函数に対して線型収束を示すかどうかは不明である。
注目すべきことに、これらのアルゴリズムは強凸率の事前知識を必要としない収束を示しており、この興味深い特徴は包括的レビュー(Chambolle and Pock, 2016 Appendix B)においてオープン問題として認識されている。
本稿では,高分解能常微分方程式(ODE)フレームワークを用いてこの問題に対処する。
確立された位相空間表現に基づいて、反復を通して進化する運動エネルギーの動的適応係数を含むリアプノフ関数を作成する際に用いられる特異なアプローチを強調した。
さらに、NAG と FISTA の線形収束は、パラメータ $r$ とは独立である。
さらに、準次次ノルムの平方が同様に線型収束へと進むことを実証する。
関連論文リスト
- Adaptive Federated Learning Over the Air [108.62635460744109]
オーバー・ザ・エア・モデル・トレーニングの枠組みの中で,適応勾配法,特にAdaGradとAdamの連合バージョンを提案する。
解析の結果,AdaGrad に基づくトレーニングアルゴリズムは $mathcalO(ln(T) / T 1 - frac1alpha の速度で定常点に収束することがわかった。
論文 参考訳（メタデータ） (2024-03-11T09:10:37Z) - Directional Smoothness and Gradient Methods: Convergence and Adaptivity [16.779513676120096]
我々は、最適化の経路に沿った目的の条件付けに依存する勾配降下に対する新しい準最適境界を開発する。
我々の証明の鍵となるのは方向の滑らかさであり、これは、目的の上のバウンドを開発するために使用する勾配変動の尺度である。
我々は,方向の滑らかさの知識を使わずとも,ポリアクのステップサイズと正規化GDが高速で経路依存の速度を得ることを示した。
論文 参考訳（メタデータ） (2024-03-06T22:24:05Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - Curvature-Independent Last-Iterate Convergence for Games on Riemannian
Manifolds [77.4346324549323]
本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。
我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
論文 参考訳（メタデータ） (2023-06-29T01:20:44Z) - Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。
最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
論文 参考訳（メタデータ） (2023-06-02T04:21:59Z) - Understanding Accelerated Gradient Methods: Lyapunov Analyses and
Hamiltonian Assisted Interpretations [1.0152838128195465]
我々は、滑らかな凸関数と強凸関数を最小化するために、以前研究したよりも一般的な1次アルゴリズムの2つのクラスを定式化する。
我々は、新しい離散リアプノフ解析を通じて、強い凸条件と一般的な凸条件でネステロフの手法と一致する加速収束率を達成するのに十分な条件を確立する。
我々は、ハミルトン関数といくつかの解釈可能な操作を直接ベースとした、ハミルトン支援勾配法と呼ばれる新しい離散アルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2023-04-20T03:03:30Z) - Online Learning Guided Curvature Approximation: A Quasi-Newton Method
with Global Non-Asymptotic Superlinear Convergence [22.286753988825048]
非漸近的超線形収束率を明示する最初の大域的収束準ニュートン法を提案する。
古典的準ニュートン法とは異なり、我々はハイブリッド近位外勾配法に基づいてアルゴリズムを構築する。
論文 参考訳（メタデータ） (2023-02-16T20:58:09Z) - 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) - IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。
提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。
加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
論文 参考訳（メタデータ） (2020-06-11T18:49:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。