論文の概要: Linear convergence of Nesterov-1983 with the strong convexity

• arxiv url: http://arxiv.org/abs/2306.09694v1
• Date: Fri, 16 Jun 2023 08:58:40 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-19 14:28:36.916511
• Title: Linear convergence of Nesterov-1983 with the strong convexity
• Title（参考訳）: 強い凸性をもつネステロフ-1983の線型収束
• Authors: Bowen Li, Bin Shi, Ya-xiang Yuan
• Abstract要約: ネステロフ-1983 と FISTA が強凸函数に線型収束するかどうかは不明である。 また、近位下次ノルムは線型収束する。
• 参考スコア（独自算出の注目度）: 8.261388753972234
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: For modern gradient-based optimization, a developmental landmark is Nesterov's accelerated gradient descent method, which is proposed in [Nesterov, 1983], so shorten as Nesterov-1983. Afterward, one of the important progresses is its proximal generalization, named the fast iterative shrinkage-thresholding algorithm (FISTA), which is widely used in image science and engineering. However, it is unknown whether both Nesterov-1983 and FISTA converge linearly on the strongly convex function, which has been listed as the open problem in the comprehensive review [Chambolle and Pock, 2016, Appendix B]. In this paper, we answer this question by the use of the high-resolution differential equation framework. Along with the phase-space representation previously adopted, the key difference here in constructing the Lyapunov function is that the coefficient of the kinetic energy varies with the iteration. Furthermore, we point out that the linear convergence of both the two algorithms above has no dependence on the parameter $r$ on the strongly convex function. Meanwhile, it is also obtained that the proximal subgradient norm converges linearly.
• Abstract（参考訳）: 現代の勾配に基づく最適化では、発展的なランドマークはネステロフの加速勾配降下法であり、 [nesterov, 1983] で提案されている。 その後の重要な進歩の1つは、画像科学や工学で広く使われている高速反復収縮保持アルゴリズム (FISTA) と呼ばれる近位一般化である。 しかし、ネステロフ-1983 と fista が、包括的レビュー [chambolle and pock, 2016 appendix b] において開問題としてリストされた強凸関数に線形収束するかどうかは不明である。 本稿では,高分解能微分方程式の枠組みを用いて,この問題に答える。 前述した位相空間表現とともに、ここでのリャプノフ函数を構成する重要な違いは、運動エネルギーの係数が反復によって変化することである。 さらに,上記の2つのアルゴリズムの線形収束は,強凸関数に対するパラメータ $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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。