論文の概要: 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) のクラスの二乗的近位劣勾配ノルムは逆立方率で収束する。
関連論文リスト
- 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) - Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。
最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
論文 参考訳(メタデータ) (2023-06-02T04:21:59Z) - Fast global convergence of gradient descent for low-rank matrix
approximation [3.8725717612267774]
我々は、特に小さなランダム値で達成された場合、勾配降下の急速な大域収束を証明した。
我々は,非対称行列近似問題に対処するために解析を拡張し,リトラクションフリーな固有空間計算法の有効性について検討する。
論文 参考訳(メタデータ) (2023-05-30T16:55:34Z) - 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) - Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる
新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
論文 参考訳(メタデータ) (2021-05-13T04:23:07Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。