論文の概要: 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（参考訳）: 最適化アルゴリズムは、限られた時間予算のアプリケーションでますます使われています。 多くのリアルタイムおよび組み込みシナリオでは、ほんの数回のイテレーションしか実行できず、伝統的な収束メトリクスはこれらの非漸近的なシステムのパフォーマンスを評価するために使用できない。 本稿では,高速化第一次最適化アルゴリズムの過渡挙動について検討する。 二次最適化問題に対しては、線形系理論のツールを用いて、非正規ダイナミクスの存在から過渡的成長が生じることを示す。 初期のイテレーションで代数的成長をもたらすモードの存在を同定し、これらのモードによって引き起こされる最適解からの過渡的エクスカージョンを定量化する。 強凸滑らかな最適化問題に対して, 積分二次制約の理論を応用し, ネステロフ加速法の過渡応答の大きさの上限を定式化する。 最適化変数と大域最小化器の間のユークリッド距離と過渡ピークへの上昇時間の両方が問題の条件数の平方根に比例していることを示す。 最後に,条件数が大きい問題に対して,定数係数まで導出する境界の厳密性を示す。

関連論文リスト

• The inexact power augmented Lagrangian method for constrained nonconvex optimization [44.516958213972885]
  この研究は、強大な拡張ラグランジアン用語を導入し、拡大項はユークリッドのノルムを権力へと引き上げる。 その結果, 長期化に低消費電力を用いると, 残余の減少が遅くなるにもかかわらず, より高速な成長が期待できることがわかった。 以上の結果より, 持続時間の短縮には低消費電力が有効であるが, 残留率が低下する傾向が示唆された。
  論文  参考訳（メタデータ） (2024-10-26T11:31:56Z)
• From exponential to finite/fixed-time stability: Applications to optimization [0.0]
  指数関数的に安定な最適化アルゴリズムが与えられた場合、有限・固定時間安定アルゴリズムを得るように修正できるだろうか? 我々は、元の力学の右辺の単純なスケーリングを通して、解を有限時間間隔でどのように計算できるかを示す肯定的な答えを提供する。 我々は、元のシステムの指数的安定性を証明したリアプノフ関数を用いて、修正アルゴリズムの所望の性質を証明した。
  論文  参考訳（メタデータ） (2024-09-18T05:43:22Z)
• ODE-based Learning to Optimize [28.380622776436905]
  我々は、慣性系とヘッセン駆動制振方程式(ISHD)を統合した包括的枠組みを提案する。 収束・安定条件を考慮した停止時間を最小化することを目的とした新しい学習法(L2O)を定式化する。 本フレームワークの実証検証は,多種多様な最適化問題に対する広範な数値実験を通じて行われる。
  論文  参考訳（メタデータ） (2024-06-04T06:39:45Z)
• 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)
• 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)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。 また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
  論文  参考訳（メタデータ） (2021-04-30T08:50:24Z)
• Acceleration Methods [57.202881673406324]
  まず2次最適化問題を用いて加速法を2つ導入する。 我々は、ネステロフの精巧な研究から始まる運動量法を詳細に論じる。 我々は、ほぼ最適な収束率に達するための一連の簡単な手法である再起動スキームを議論することで結論付ける。
  論文  参考訳（メタデータ） (2021-01-23T17:58:25Z)
• 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)

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

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