論文の概要: Proximal Subgradient Norm Minimization of ISTA and FISTA
- arxiv url: http://arxiv.org/abs/2211.01610v1
- Date: Thu, 3 Nov 2022 06:50:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-04 13:10:49.561951
- Title: Proximal Subgradient Norm Minimization of ISTA and FISTA
- Title（参考訳）: ISTAとFISTAの準次ノルム最小化
- Authors: Bowen Li, Bin Shi, Ya-xiang Yuan
- Abstract要約: 反復収縮保持アルゴリズムのクラスに対する2乗近位次数ノルムは逆2乗率で収束することを示す。
また、高速反復収縮保持アルゴリズム (FISTA) のクラスに対する2乗次次数次ノルムが、逆立方レートで収束するように加速されることも示している。
- 参考スコア（独自算出の注目度）: 8.261388753972234
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: For first-order smooth optimization, the research on the acceleration
phenomenon has a long-time history. Until recently, the mechanism leading to
acceleration was not successfully uncovered by the gradient correction term and
its equivalent implicit-velocity form. Furthermore, based on the
high-resolution differential equation framework with the corresponding emerging
techniques, phase-space representation and Lyapunov function, the squared
gradient norm of Nesterov's accelerated gradient descent (\texttt{NAG}) method
at an inverse cubic rate is discovered. However, this result cannot be directly
generalized to composite optimization widely used in practice, e.g., the linear
inverse problem with sparse representation. In this paper, we meticulously
observe a pivotal inequality used in composite optimization about the step size
$s$ and the Lipschitz constant $L$ and find that it can be improved tighter. We
apply the tighter inequality discovered in the well-constructed Lyapunov
function and then obtain the proximal subgradient norm minimization by the
phase-space representation, regardless of gradient-correction or
implicit-velocity. Furthermore, we demonstrate that the squared proximal
subgradient norm for the class of iterative shrinkage-thresholding algorithms
(ISTA) converges at an inverse square rate, and the squared proximal
subgradient norm for the class of faster iterative shrinkage-thresholding
algorithms (FISTA) is accelerated to convergence at an inverse cubic rate.
- Abstract（参考訳）: 一階スムーズな最適化のために、加速現象の研究には長い歴史がある。
最近まで、加速度につながるメカニズムは勾配補正項とその等価な暗黙速度形式によって発見されなかった。
さらに, 位相空間表現とリアプノフ関数を用いた高分解能微分方程式の枠組みに基づいて, 逆立方率でのネステロフの加速度勾配降下法(\textt{nag})の2乗勾配ノルムが発見された。
しかし、この結果は、例えばスパース表現を持つ線形逆問題など、実際に広く使われている複合最適化に直接一般化することはできない。
本稿では,ステップサイズ$s$ とリプシッツ定数 $l$ に関する複合最適化において用いられる重要な不等式を注意深く観察し,より厳密に改良できることを示す。
well-constructed Lyapunov 関数で発見されたより厳密な不等式を適用し、勾配補正や暗黙速度に関わらず位相空間表現による近位次ノルム最小化を得る。
さらに,反復的収縮緩和アルゴリズム (ista) のクラスに対する二乗的近位劣勾配ノルムは逆二乗率で収束し,高速な反復的収縮緩和アルゴリズム (fista) のクラスの二乗的近位劣勾配ノルムは逆立方率で収束する。
関連論文リスト
- An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness [15.656614304616006]
本稿では,上層関数が非非有界な滑らかさであり,下層関数が強く凸であるような二層最適化問題のクラスについて検討する。
これらの問題は、ニューラルネットワークを用いたテキスト分類など、データ学習に大きな応用がある。
論文 参考訳（メタデータ） (2024-09-28T02:30:44Z) - Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
勾配変分オンライン学習は、オンライン関数の勾配の変化とともにスケールする後悔の保証を達成することを目的としている。
ニューラルネットワーク最適化における最近の取り組みは、一般化された滑らかさ条件を示唆し、滑らかさは勾配ノルムと相関する。
ゲームにおける高速収束と拡張逆最適化への応用について述べる。
論文 参考訳（メタデータ） (2024-08-17T02:22:08Z) - 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) - Linear convergence of forward-backward accelerated algorithms without knowledge of the modulus of strong convexity [14.0409219811182]
我々はネステロフの加速勾配降下(NAG)とFISTAの両方が強い凸関数に対して線形収束を示すことを示した。
我々は、運動エネルギーの動的適応係数を含むリアプノフ関数の創出に際し、特異なアプローチを強調した。
論文 参考訳（メタデータ） (2023-06-16T08:58:40Z) - Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。
最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
論文 参考訳（メタデータ） (2023-06-02T04:21:59Z) - Linear Convergence of ISTA and FISTA [8.261388753972234]
疎表現を用いた線形逆問題の解法として,反復縮小保持アルゴリズム (ISTA) のクラスを再検討する。
滑らかな部分を凸とする以前の仮定は最小二乗モデルを弱める。
目的値と2乗近位下次ノルムの両方において、線形収束を合成最適化に一般化する。
論文 参考訳（メタデータ） (2022-12-13T02:02:50Z) - Revisiting the acceleration phenomenon via high-resolution differential
equations [6.53306151979817]
ネステロフの加速勾配降下(NAG)は、一階アルゴリズムの歴史におけるマイルストーンの1つである。
Lyapunov解析と位相空間表現に基づく$mu$-strongly convex関数のNAGについて検討する。
NAGの暗黙的速度スキームによる高分解能微分方程式の枠組みは完璧であり、勾配補正スキームよりも優れていた。
論文 参考訳（メタデータ） (2022-12-12T04:36:37Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - Hessian-Free High-Resolution Nesterov Acceleration for Sampling [55.498092486970364]
最適化のためのNesterovのAccelerated Gradient(NAG)は、有限のステップサイズを使用する場合の連続時間制限(ノイズなしの運動的ランゲヴィン)よりも優れたパフォーマンスを持つ。
本研究は, この現象のサンプリング法について検討し, 離散化により加速勾配に基づくMCMC法が得られる拡散過程を提案する。
論文 参考訳（メタデータ） (2020-06-16T15:07:37Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。