論文の概要: Anderson acceleration for iteratively reweighted $\ell_1$ algorithm

• arxiv url: http://arxiv.org/abs/2403.07271v1
• Date: Tue, 12 Mar 2024 03:00:15 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-13 23:02:39.467654
• Title: Anderson acceleration for iteratively reweighted $\ell_1$ algorithm
• Title（参考訳）: 反復再重み付き$\ell_1$アルゴリズムに対するアンダーソン加速度
• Authors: Kexin Li
• Abstract要約: 反復再重み付きL1アルゴリズム(IRL1)は、非滑らかな正規化による最適化問題の解法として一般的なアルゴリズムである。 アンダーソン加速IRL1アルゴリズムを提案し,その局所収束率を確立する。 実験結果から,我々のアルゴリズムは既存のNesterov加速度に基づくアルゴリズムよりも優れていた。
• 参考スコア（独自算出の注目度）: 4.327906253115976
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Iteratively reweighted L1 (IRL1) algorithm is a common algorithm for solving sparse optimization problems with nonconvex and nonsmooth regularization. The development of its acceleration algorithm, often employing Nesterov acceleration, has sparked significant interest. Nevertheless, the convergence and complexity analysis of these acceleration algorithms consistently poses substantial challenges. Recently, Anderson acceleration has gained prominence owing to its exceptional performance for speeding up fixed-point iteration, with numerous recent studies applying it to gradient-based algorithms. Motivated by the powerful impact of Anderson acceleration, we propose an Anderson-accelerated IRL1 algorithm and establish its local linear convergence rate. We extend this convergence result, typically observed in smooth settings, to a nonsmooth scenario. Importantly, our theoretical results do not depend on the Kurdyka-Lojasiewicz condition, a necessary condition in existing Nesterov acceleration-based algorithms. Furthermore, to ensure global convergence, we introduce a globally convergent Anderson accelerated IRL1 algorithm by incorporating a classical nonmonotone line search condition. Experimental results indicate that our algorithm outperforms existing Nesterov acceleration-based algorithms.
• Abstract（参考訳）: 反復再重み付きL1アルゴリズム(IRL1)は、非凸および非滑らかな正規化を伴うスパース最適化問題の解法である。 ネステロフ加速度を利用した加速アルゴリズムの開発は、大きな関心を呼んでいる。 それにもかかわらず、これらの加速度アルゴリズムの収束と複雑性解析は一貫して重大な課題をもたらす。 近年、アンダーソン加速度は、不動点反復の高速化に優れた性能を備え、近年では勾配に基づくアルゴリズムに応用されている。 アンダーソン加速度の強い影響に動機づけられ,アンダーソン加速irl1アルゴリズムを提案し,その局所線形収束速度を確立する。 我々はこの収束結果(典型的には滑らかな設定で観察される)を非滑らかなシナリオに拡張する。 重要な点は、既存のネステロフ加速度に基づくアルゴリズムにおいて必要条件であるクルディカ・ロジャシェヴィチ条件に依存しないことである。 さらに,グローバル収束を保証するため,古典的非単調線探索条件を取り入れたアンダーソン加速IRL1アルゴリズムを導入する。 実験の結果,提案アルゴリズムは既存のNesterov加速度に基づくアルゴリズムよりも優れていた。

関連論文リスト

• Accelerating AI Performance using Anderson Extrapolation on GPUs [2.114333871769023]
  Anderson外挿を利用したAI性能向上のための新しい手法を提案する。 混合ペナルティが生じるクロスオーバー点を特定することにより、反復を収束に還元することに焦点を当てる。 高速コンピューティングの領域におけるスケーラビリティと効率性の拡張を動機とした,トレーニングと推論の両面での大幅な改善を示す。
  論文  参考訳（メタデータ） (2024-10-25T10:45:17Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Adan: Adaptive Nesterov Momentum Algorithm for Faster Optimizing Deep Models [158.19276683455254]
  アダプティブ勾配アルゴリズムは、重ボール加速の移動平均アイデアを借用し、勾配の第1次モーメントを正確に推定し、収束を加速する。 ネステロフ加速は、理論上はボール加速よりも早く収束し、多くの経験的ケースでも収束する。 本稿では,計算勾配の余分な計算とメモリオーバーヘッドを回避するため,Nesterov運動量推定法(NME)を提案する。 Adan は視覚変換器 (ViT と CNN) で対応する SoTA を上回り,多くの人気ネットワークに対して新たな SoTA を設定する。
  論文  参考訳（メタデータ） (2022-08-13T16:04:39Z)
• Accelerated SGD for Non-Strongly-Convex Least Squares [14.010916616909743]
  非強凸設定における最小二乗回帰問題の近似を考察する。 本稿では,問題のノイズに依存して最適な予測誤差率を実現するための,最初の実用的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-03-03T14:39:33Z)
• An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimization [111.24899593052851]
  条件勾配アルゴリズム(Frank-Wolfeアルゴリズムとも呼ばれる)は、最近、機械学習コミュニティで人気を取り戻している。 ARCSは、ゼロ階最適化において凸問題を解く最初のゼロ階条件勾配スライディング型アルゴリズムである。 1次最適化では、ARCSの収束結果は、勾配クエリのオラクルの数で、従来のアルゴリズムよりも大幅に優れていた。
  論文  参考訳（メタデータ） (2021-09-18T07:08:11Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• An Accelerated DFO Algorithm for Finite-sum Convex Functions [0.0]
  デリバティブフリーの最適化(DFO)は最近、機械学習において大きな勢いを増している。 本稿では、有限サム目的関数を用いて、アクセス可能なDFOアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-07-07T09:57:31Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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