論文の概要: Transient growth of accelerated first-order methods for strongly convex
optimization problems
- arxiv url: http://arxiv.org/abs/2103.08017v1
- Date: Sun, 14 Mar 2021 20:01:14 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-16 13:43:09.566097
- Title: Transient growth of accelerated first-order methods for strongly convex
optimization problems
- Title(参考訳): 強凸最適化問題に対する加速一階法の過渡成長
- Authors: Hesameddin Mohammadi, Samantha Samuelson, Mihailo R. Jovanovi\'c
- Abstract要約: 本稿では,高速化第一次最適化アルゴリズムの過渡挙動について検討する。
二次最適化問題に対しては、線形系理論のツールを用いて、非正規ダイナミクスの存在から過渡的成長が生じることを示す。
強凸滑らかな最適化問題に対して, 積分二次制約の理論を応用し, ネステロフ加速法の過渡応答の大きさの上限を定式化する。
- 参考スコア(独自算出の注目度): 1.6114012813668934
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Optimization algorithms are increasingly being used in applications with
limited time budgets. In many real-time and embedded scenarios, only a few
iterations can be performed and traditional convergence metrics cannot be used
to evaluate performance in these non-asymptotic regimes. In this paper, we
examine the transient behavior of accelerated first-order optimization
algorithms. For quadratic optimization problems, we employ tools from linear
systems theory to show that transient growth arises from the presence of
non-normal dynamics. We identify the existence of modes that yield an algebraic
growth in early iterations and quantify the transient excursion from the
optimal solution caused by these modes. For strongly convex smooth optimization
problems, we utilize the theory of integral quadratic constraints to establish
an upper bound on the magnitude of the transient response of Nesterov's
accelerated method. We show that both the Euclidean distance between the
optimization variable and the global minimizer and the rise time to the
transient peak are proportional to the square root of the condition number of
the problem. Finally, for problems with large condition numbers, we demonstrate
tightness of the bounds that we derive up to constant factors.
- Abstract(参考訳): 最適化アルゴリズムは、限られた時間予算のアプリケーションでますます使われています。
多くのリアルタイムおよび組み込みシナリオでは、ほんの数回のイテレーションしか実行できず、伝統的な収束メトリクスはこれらの非漸近的なシステムのパフォーマンスを評価するために使用できない。
本稿では,高速化第一次最適化アルゴリズムの過渡挙動について検討する。
二次最適化問題に対しては、線形系理論のツールを用いて、非正規ダイナミクスの存在から過渡的成長が生じることを示す。
初期のイテレーションで代数的成長をもたらすモードの存在を同定し、これらのモードによって引き起こされる最適解からの過渡的エクスカージョンを定量化する。
強凸滑らかな最適化問題に対して, 積分二次制約の理論を応用し, ネステロフ加速法の過渡応答の大きさの上限を定式化する。
最適化変数と大域最小化器の間のユークリッド距離と過渡ピークへの上昇時間の両方が問題の条件数の平方根に比例していることを示す。
最後に,条件数が大きい問題に対して,定数係数まで導出する境界の厳密性を示す。
関連論文リスト
- Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - Generalized Gradient Flows with Provable Fixed-Time Convergence and Fast
Evasion of Non-Degenerate Saddle Points [8.452349885923507]
グラディエントベースの1次凸最適化アルゴリズムは、機械学習タスクを含むさまざまな領域で広く適用可能である。
最適時間の固定時間理論の最近の進歩に触発されて,高速化最適化アルゴリズムを設計するための枠組みを導入する。
非ド・サドル点を許容する関数に対しては、これらのサドル点を避けるのに必要な時間は初期条件すべてに一様有界であることを示す。
論文 参考訳(メタデータ) (2022-12-07T16:36:23Z) - Tight Convergence Rate Bounds for Optimization Under Power Law Spectral
Conditions [17.55171891411791]
スペクトルの所定の形状に対して、最適に加速された方法、そのスケジュール、収束上限が統一的に得られるかを示す。
実験により、得られた収束境界と加速度戦略は、正確に2次最適化問題に関係しているだけでなく、ニューラルネットワークのトレーニングに適用した場合にもかなり正確であることがわかった。
論文 参考訳(メタデータ) (2022-02-02T12:24:03Z) - Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for
Solving Nonconvex Min-Max Problems [2.0305676256390934]
連立勾配降下指数アルゴリズムの連続時間変動の有限時間特性を特徴付ける。
連続時間アルゴリズムの挙動に関する結果は、離散時間アルゴリズムの収束特性を高めるために用いられる。
論文 参考訳(メタデータ) (2021-12-17T15:51:04Z) - Breaking the Convergence Barrier: Optimization via Fixed-Time Convergent
Flows [4.817429789586127]
本稿では, 固定時間安定力学系の概念に基づいて, 加速を実現するための多言語最適化フレームワークを提案する。
提案手法の高速化された収束特性を,最先端の最適化アルゴリズムに対して様々な数値例で検証する。
論文 参考訳(メタデータ) (2021-12-02T16:04:40Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳(メタデータ) (2021-10-20T02:57:21Z) - Optimization on manifolds: A symplectic approach [127.54402681305629]
本稿では、最適化問題を解くための一般的な枠組みとして、ディラックの制約付きハミルトン系理論の散逸拡張を提案する。
我々の(加速された)アルゴリズムのクラスは単純で効率的なだけでなく、幅広い文脈にも適用できる。
論文 参考訳(メタデータ) (2021-07-23T13:43:34Z) - A Contraction Theory Approach to Optimization Algorithms from
Acceleration Flows [1.90365714903665]
私たちは、適切なODEを設計し、識別するための原則化された方法論を提供するために収縮理論を使用します。
本稿では, ODE の新しいシステム,すなわち Accelerated-Contracting-Nesterov フローを提案する。
注目すべきことに、この流れの単純明示的なオイラー離散化はネステロフ加速度法に対応する。
論文 参考訳(メタデータ) (2021-05-18T21:11:37Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - 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) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳(メタデータ) (2020-06-10T15:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。