論文の概要: Linear Convergence of ISTA and FISTA

• arxiv url: http://arxiv.org/abs/2212.06319v1
• Date: Tue, 13 Dec 2022 02:02:50 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-14 14:19:29.958849
• Title: Linear Convergence of ISTA and FISTA
• Title（参考訳）: ISTAとFISTAの線形収束
• Authors: Bowen Li, Bin Shi, Ya-xiang Yuan
• Abstract要約: 疎表現を用いた線形逆問題の解法として,反復縮小保持アルゴリズム (ISTA) のクラスを再検討する。 滑らかな部分を凸とする以前の仮定は最小二乗モデルを弱める。 目的値と2乗近位下次ノルムの両方において、線形収束を合成最適化に一般化する。
• 参考スコア（独自算出の注目度）: 8.261388753972234
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In this paper, we revisit the class of iterative shrinkage-thresholding algorithms (ISTA) for solving the linear inverse problem with sparse representation, which arises in signal and image processing. It is shown in the numerical experiment to deblur an image that the convergence behavior in the logarithmic-scale ordinate tends to be linear instead of logarithmic, approximating to be flat. Making meticulous observations, we find that the previous assumption for the smooth part to be convex weakens the least-square model. Specifically, assuming the smooth part to be strongly convex is more reasonable for the least-square model, even though the image matrix is probably ill-conditioned. Furthermore, we improve the pivotal inequality tighter for composite optimization with the smooth part to be strongly convex instead of general convex, which is first found in [Li et al., 2022]. Based on this pivotal inequality, we generalize the linear convergence to composite optimization in both the objective value and the squared proximal subgradient norm. Meanwhile, we set a simple ill-conditioned matrix which is easy to compute the singular values instead of the original blur matrix. The new numerical experiment shows the proximal generalization of Nesterov's accelerated gradient descent (NAG) for the strongly convex function has a faster linear convergence rate than ISTA. Based on the tighter pivotal inequality, we also generalize the faster linear convergence rate to composite optimization, in both the objective value and the squared proximal subgradient norm, by taking advantage of the well-constructed Lyapunov function with a slight modification and the phase-space representation based on the high-resolution differential equation framework from the implicit-velocity scheme.
• Abstract（参考訳）: 本稿では,信号処理や画像処理において発生する疎表現による線形逆問題の解法として,反復縮小保持アルゴリズム(ISTA)のクラスを再検討する。 数値実験では, 対数スケールのオーディネートにおける収束挙動が対数の代わりに線形になりがちで, ほぼ平坦であることを示す。 微妙な観察により、滑らかな部分を凸とする以前の仮定が最小二乗モデルを弱めることが分かる。 特に、画像行列が不条件であるとしても、滑らかな部分が強い凸となると仮定することは、最小二乗モデルにとってより合理的である。 さらに, [li et al., 2022] に初めて見られる一般凸の代わりに, 滑らかな部分で強凸となるように, 複合最適化のための重要な不等式を改良した。 この中心的不等式に基づいて、線形収束を目的値と2乗近位下次ノルムの両方の合成最適化に一般化する。 一方、元のぼやけた行列の代わりに特異値を簡単に計算できる単純な不条件行列を設定した。 新しい数値実験は、強い凸関数に対するネステロフの加速勾配勾配(NAG)の近位一般化がISTAよりも高速な線形収束速度を持つことを示している。 さらに,より厳密な主成分不等式に基づいて,より高速な線形収束率を,目的値と正方形近位劣勾配ノルムの両方において合成最適化に一般化し,わずかな修正で構築されたリアプノフ関数と,暗黙的速度スキームから高分解能微分方程式の枠組みに基づく位相空間表現を活用した。

関連論文リスト

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• An inexact LPA for DC composite optimization and application to matrix completions with outliers [5.746154410100363]
  本稿では,複合最適化問題のクラスについて述べる。 合成構造を利用することで、ポテンシャル関数が反復列において1/2$のKL特性を持つ条件を与える。
  論文  参考訳（メタデータ） (2023-03-29T16:15:34Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Proximal Subgradient Norm Minimization of ISTA and FISTA [8.261388753972234]
  反復収縮保持アルゴリズムのクラスに対する2乗近位次数ノルムは逆2乗率で収束することを示す。 また、高速反復収縮保持アルゴリズム (FISTA) のクラスに対する2乗次次数次ノルムが、逆立方レートで収束するように加速されることも示している。
  論文  参考訳（メタデータ） (2022-11-03T06:50:19Z)
• Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization [11.017632675093628]
  非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
  論文  参考訳（メタデータ） (2022-06-30T02:17:11Z)
• Hybrid Model-based / Data-driven Graph Transform for Image Coding [54.31406300524195]
  予測内残差ブロックを符号化するハイブリッドモデルベース/データ駆動方式を提案する。 変換行列の最初の$K$固有ベクトルは、安定性のための非対称離散正弦変換(ADST)のような統計モデルから導かれる。 WebPをベースライン画像として使用することにより、我々のハイブリッドグラフ変換は、デフォルトの離散コサイン変換(DCT)よりもエネルギーの圧縮が良く、KLTよりも安定性がよいことを示す。
  論文  参考訳（メタデータ） (2022-03-02T15:36:44Z)
• Efficient Algorithms for High-Dimensional Convex Subspace Optimization via Strict Complementarity [19.24470467199451]
  目的が$realsn$, $k$の部分空間を見つけることにある最適化問題を考慮し、凸の滑らかな損失を最小限に抑える。 この問題は高次元のレジームでは高いが、大域的最適解を見つけることは困難である。 本稿では自然について述べる。 収束する最適な次元緩和を 決定するのです グローバルは単純です
  論文  参考訳（メタデータ） (2022-02-08T17:36:43Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。 暗黙正則化現象の理論的保証を提供する。
  論文  参考訳（メタデータ） (2020-07-16T13:27:47Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。 一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。 本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
  論文  参考訳（メタデータ） (2020-06-16T13:41:54Z)
• Dualize, Split, Randomize: Toward Fast Nonsmooth Optimization Algorithms [21.904012114713428]
  第一のFが滑らかで第二のFが非滑らかで近似可能な3つの凸函数の和を考える。 このテンプレート問題には、画像処理や機械学習など、多くの応用がある。 この問題に対して PDDY と呼ぶ新しい原始双対アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-04-03T10:48:01Z)

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

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