論文の概要: A Family of Controllable Momentum Coefficients for Forward-Backward Accelerated Algorithms

• arxiv url: http://arxiv.org/abs/2501.10051v1
• Date: Fri, 17 Jan 2025 09:15:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-20 13:59:09.665171
• Title: A Family of Controllable Momentum Coefficients for Forward-Backward Accelerated Algorithms
• Title（参考訳）: 前向き加速アルゴリズムにおける制御可能なモーメント係数の一家系
• Authors: Mingwei Fu, Bin Shi,
• Abstract要約: ネステロフの加速勾配法(NAG)は勾配に基づく最適化において重要な進歩を示す。 強凸関数に適用した場合のアルゴリズムの複雑さは未だ不明である。 フォワード・バック・アクセラレーション法に対する制御可能な運動量係数の族を導入する。
• 参考スコア（独自算出の注目度）: 4.404496835736175
• License:
• Abstract: Nesterov's accelerated gradient method (NAG) marks a pivotal advancement in gradient-based optimization, achieving faster convergence compared to the vanilla gradient descent method for convex functions. However, its algorithmic complexity when applied to strongly convex functions remains unknown, 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. [2024b], with the monotonic case further explored by Fu and Shi [2024]. In this paper, we introduce a family of controllable momentum coefficients for forward-backward accelerated methods, focusing on the critical step size $s=1/L$. Unlike traditional linear forms, the proposed momentum coefficients follow an $\alpha$-th power structure, where the parameter $r$ is adaptively tuned to $\alpha$. Using a Lyapunov function specifically designed for $\alpha$, we establish a controllable $O\left(1/k^{2\alpha} \right)$ convergence rate for the NAG-$\alpha$ method, provided that $r > 2\alpha$. At the critical step size, NAG-$\alpha$ achieves an inverse polynomial convergence rate of arbitrary degree by adjusting $r$ according to $\alpha > 0$. We further simplify the Lyapunov function by expressing it in terms of the iterative sequences $x_k$ and $y_k$, eliminating the need for phase-space representations. This simplification enables us to extend the controllable $O \left(1/k^{2\alpha} \right)$ rate to the monotonic variant, M-NAG-$\alpha$, thereby enhancing optimization efficiency. Finally, by leveraging the fundamental inequality for composite functions, we extended the controllable $O\left(1/k^{2\alpha} \right)$ rate to proximal algorithms, including the fast iterative shrinkage-thresholding algorithm (FISTA-$\alpha$) and its monotonic counterpart (M-FISTA-$\alpha$).
• Abstract（参考訳）: ネステロフの加速勾配法(NAG)は、凸関数のバニラ勾配降下法と比較して、勾配に基づく最適化において重要な進歩を示す。 しかし、Chambolle と Pock [2016] による包括的なレビューで述べられているように、強凸関数に適用する際のアルゴリズムの複雑さは依然として不明である。 この問題は、重要なステップサイズを除いて、Li et al [2024b] によって対処され、Fu と Shi [2024b] によってさらに探索された。 本稿では,前向き加速法における制御可能な運動量係数の族を導入し,臨界ステップサイズ$s=1/L$に着目した。 従来の線型形式とは異なり、提案された運動量係数は、パラメータ $r$ を $\alpha$ に適応的に調整する $\alpha$-th Power 構造に従う。 Lyapunov 関数を $\alpha$ 用に特別に設計し、$r > 2\alpha$ とすると、NAG-$\alpha$ メソッドに対する制御可能な $O\left(1/k^{2\alpha} \right)$収束率を確立する。 臨界ステップサイズにおいて、NAG-$\alpha$は$\alpha > 0$に従って$r$を調整することで任意の次数の逆多項式収束率を達成する。 さらに Lyapunov 関数を $x_k$ および $y_k$ の反復列で表現することで単純化し、位相空間表現の必要性を排除した。 この単純化により、制御可能な$O \left(1/k^{2\alpha} \right)$レートをモノトニック変種 M-NAG-$\alpha$ に拡張し、最適化効率を向上することができる。 最後に、合成関数の基本的な不等式を活用することにより、制御可能な$O\left(1/k^{2\alpha} \right)$レートを、高速反復縮退保持アルゴリズム(FISTA-$\alpha$)とそのモノトニック(M-FISTA-$\alpha$)を含む近位アルゴリズムに拡張した。

関連論文リスト

• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimization [26.328847475942894]
  我々は,本手法が$Obigl(minfrac1k2, fracsqrtdlog kk2.5bigr)$の収束率を達成できることを証明した。 我々の知る限りでは、この結果はネステロフの加速勾配に対する準ニュートン型法の証明可能な利得を示す最初のものである。
  論文  参考訳（メタデータ） (2023-06-03T23:31:27Z)
• On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
  機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。 本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2023-05-30T17:47:27Z)
• Convergence rate of the (1+1)-evolution strategy on locally strongly convex functions with lipschitz continuous gradient and their monotonic transformations [20.666734673282498]
  進化戦略(ES)は、ブラックボックス連続最適化のための有望なアルゴリズムの1つである。 本研究では,局所$L$-強凸関数上の (1+1)-ES の線型収束率の上界と下界を$U$-Lipschitz連続勾配で導出した。
  論文  参考訳（メタデータ） (2022-09-26T07:16:50Z)
• Stochastic Zeroth order Descent with Structured Directions [10.604744518360464]
  我々は, 有限差分法であるStructured Zeroth Order Descent (SSZD)を導入・解析し, 集合 $lleq d 方向の勾配を近似し, $d は周囲空間の次元である。 凸凸に対して、すべての$c1/2$に対して$O( (d/l) k-c1/2$)$ 上の関数の収束はほぼ確実に証明する。
  論文  参考訳（メタデータ） (2022-06-10T14:00:06Z)
• Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization [7.197233473373693]
  2つの凸関数の和を最小化する問題を考える。 1つはリプシッツ連続勾配を持ち、オークルを介してアクセスでき、もう1つは「単純」である。 我々は、$tildeO (1/ sqrtepsilon)$ iterationsで$epsilon$prialdual gap(期待して)を達成することができることを示す。
  論文  参考訳（メタデータ） (2022-05-25T13:01:09Z)
• Continuous Submodular Maximization: Boosting via Non-oblivious Function [12.755674710719616]
  本稿では、オフラインおよびオンライン設定の両方において制約付きおよび連続的なサブモジュールイテレーションを再考する。 係数回帰最適化方程式を用いて、問題$max_boldsymbolxinmathCf(boldsymbolx)$に対して最適な補助関数$F$を導出する。 オンライン環境では、勾配フィードバックアルゴリズムの強化を提案し、$sqrtD$($D$は勾配フィードバックが$(fracgamma2)$に対する遅延の総和である)を後悔する。
  論文  参考訳（メタデータ） (2022-01-03T15:10:17Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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