論文の概要: Lyapunov Analysis For Monotonically Forward-Backward Accelerated Algorithms

• arxiv url: http://arxiv.org/abs/2412.13527v3
• Date: Tue, 05 Aug 2025 13:33:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-06 13:15:14.042293
• Title: Lyapunov Analysis For Monotonically Forward-Backward Accelerated Algorithms
• Title（参考訳）: 単調前方加速アルゴリズムのためのリアプノフ解析
• Authors: Mingwei Fu, Bin Shi,
• Abstract要約: ネステロフの加速勾配法(NAG)は凸最適化のための勾配勾配勾配よりも早く収束する。 Beck と Teboulle [2009b] は単調変種 M-NAG を提案し、ラッソのような複合問題に対する M-FISTA として近位に拡張した。 強い凸性の下でM-NAGとM-FISTAの線形収束を確立することは未解決の問題である。
• 参考スコア（独自算出の注目度）: 4.404496835736175
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Nesterov's accelerated gradient method (NAG) achieves faster convergence than gradient descent for convex optimization but lacks monotonicity in function values. To address this, Beck and Teboulle [2009b] proposed a monotonic variant, M-NAG, and extended it to the proximal setting as M-FISTA for composite problems such as Lasso. However, establishing the linear convergence of M-NAG and M-FISTA under strong convexity remains an open problem. In this paper, we analyze M-NAG via the implicit-velocity phase representation and show that an additional assumption, either the position update or the phase-coupling relation, is necessary to fully recover the NAG iterates. The essence of M-NAG lies in controlling an auxiliary sequence to enforce non-increase. We further demonstrate that the M-NAG update alone is sufficient to construct a Lyapunov function guaranteeing linear convergence, without relying on full NAG iterates. By modifying the mixed sequence to incorporate forward-indexed gradients, we develop a new Lyapunov function that removes the kinetic energy term, enabling a direct extension to M-NAG. The required starting index depends only on the momentum parameter and not on problem constants. Finally, leveraging newly developed proximal inequalities, we extend our results to M-FISTA, establishing its linear convergence and deepening the theoretical understanding of monotonic accelerated methods.
• Abstract（参考訳）: ネステロフの加速勾配法(NAG)は凸最適化の勾配降下よりも高速な収束を実現するが、関数値の単調性に欠ける。 これを解決するため、Beck と Teboulle [2009b] は単調変種 M-NAG を提案し、それをラッソのような複合問題に対する M-FISTA として近位に拡張した。 しかし、強い凸性の下で M-NAG と M-FISTA の線型収束を確立することは、未解決の問題である。 本稿では,M-NAGを暗黙の速度位相表現を用いて解析し,NAGの反復を完全回復するためには,位置更新あるいは位相結合関係のいずれにおいても追加の仮定が必要であることを示す。 M-NAGの本質は、非増加を強制する補助配列を制御することである。 さらに、M-NAGの更新だけでは、完全なNAGイテレートに頼ることなく、線形収束を保証するリアプノフ関数を構築するのに十分であることを示す。 混合配列を修正して前方進勾配を組み込むことにより、運動エネルギー項を除去し、M-NAGへの直接拡張を可能にする新しいリャプノフ関数を開発する。 要求される開始指数は運動量パラメータにのみ依存し、問題定数には依存しない。 最後に、新たに開発された近位不等式を利用して、結果をM-FISTAに拡張し、線形収束を確立し、単調加速法の理論的理解を深める。

関連論文リスト

• Controlling the Flow: Stability and Convergence for Stochastic Gradient Descent with Decaying Regularization [0.40964539027092917]
  我々は、余分な有界性仮定を伴わない元の問題の最小ノルム解に対して、reg-SGDの強い収束性を証明する。 分析の結果,Tikhonov正則化がSGDの流れを制御し,安定した学習力学が得られることがわかった。
  論文  参考訳（メタデータ） (2025-05-16T16:53:49Z)
• 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)
• Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks [59.142826407441106]
  本稿では,アルゴリズム安定性の概念を活用して,浅層ニューラルネットワーク(SNN)の一般化挙動について検討する。 我々は、SNNを訓練するために勾配降下(GD)と勾配降下(SGD)を考慮する。
  論文  参考訳（メタデータ） (2022-09-19T18:48:00Z)
• Optimization-Induced Graph Implicit Nonlinear Diffusion [64.39772634635273]
  我々はGIND(Graph Implicit Diffusion)と呼ばれる新しいグラフ畳み込み変種を提案する。 GINDは暗黙的に隣人の無限のホップにアクセスでき、非線型拡散を伴う特徴を適応的に集約することで過度な平滑化を防いでいる。 学習された表現は、明示的な凸最適化目標の最小化として定式化できることを示す。
  論文  参考訳（メタデータ） (2022-06-29T06:26:42Z)
• 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)
• Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximation [30.02577720946978]
  線形関数近似を用いたエントロピー規則化NPGの有限時間収束解析を確立した。 エントロピー規則化NPGは関数近似誤差までのエンフィナール収束を示すことを示す。
  論文  参考訳（メタデータ） (2021-06-08T04:30:39Z)
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling [55.498092486970364]
  最適化のためのNesterovのAccelerated Gradient(NAG)は、有限のステップサイズを使用する場合の連続時間制限(ノイズなしの運動的ランゲヴィン)よりも優れたパフォーマンスを持つ。 本研究は, この現象のサンプリング法について検討し, 離散化により加速勾配に基づくMCMC法が得られる拡散過程を提案する。
  論文  参考訳（メタデータ） (2020-06-16T15:07:37Z)

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

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