論文の概要: Breaking the Convergence Barrier: Optimization via Fixed-Time Convergent Flows

• arxiv url: http://arxiv.org/abs/2112.01363v1
• Date: Thu, 2 Dec 2021 16:04:40 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-07 15:31:59.518483
• Title: Breaking the Convergence Barrier: Optimization via Fixed-Time Convergent Flows
• Title（参考訳）: 収束障壁を破る:固定時間収束流による最適化
• Authors: Param Budhraja, Mayank Baranwal, Kunal Garg, Ashish Hota
• Abstract要約: 本稿では, 固定時間安定力学系の概念に基づいて, 加速を実現するための多言語最適化フレームワークを提案する。 提案手法の高速化された収束特性を,最先端の最適化アルゴリズムに対して様々な数値例で検証する。
• 参考スコア（独自算出の注目度）: 4.817429789586127
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Accelerated gradient methods are the cornerstones of large-scale, data-driven optimization problems that arise naturally in machine learning and other fields concerning data analysis. We introduce a gradient-based optimization framework for achieving acceleration, based on the recently introduced notion of fixed-time stability of dynamical systems. The method presents itself as a generalization of simple gradient-based methods suitably scaled to achieve convergence to the optimizer in a fixed-time, independent of the initialization. We achieve this by first leveraging a continuous-time framework for designing fixed-time stable dynamical systems, and later providing a consistent discretization strategy, such that the equivalent discrete-time algorithm tracks the optimizer in a practically fixed number of iterations. We also provide a theoretical analysis of the convergence behavior of the proposed gradient flows, and their robustness to additive disturbances for a range of functions obeying strong convexity, strict convexity, and possibly nonconvexity but satisfying the Polyak-{\L}ojasiewicz inequality. We also show that the regret bound on the convergence rate is constant by virtue of the fixed-time convergence. The hyperparameters have intuitive interpretations and can be tuned to fit the requirements on the desired convergence rates. We validate the accelerated convergence properties of the proposed schemes on a range of numerical examples against the state-of-the-art optimization algorithms. Our work provides insights on developing novel optimization algorithms via discretization of continuous-time flows.
• Abstract（参考訳）: 加速度勾配法は、機械学習やその他のデータ分析の分野で自然に発生する大規模データ駆動最適化問題の基礎である。 最近導入された動的システムの固定時間安定性の概念に基づいて,加速を実現するための勾配に基づく最適化フレームワークを提案する。 この方法は、初期化とは独立に固定時間で最適化器への収束を達成するために適切にスケールされた単純な勾配法を一般化したものである。 まず、固定時間安定な力学系を設計するための連続時間フレームワークを活用し、その後、等価離散時間アルゴリズムが実質的に固定された反復数で最適化者を追跡するような一貫した離散化戦略を提供する。 また,提案する勾配流の収束挙動を理論的に解析し,強凸性,厳密な凸性,非凸性にも従うがポリak-{\l}ojasiewiczの不等式を満たす関数に対する加法外乱に対するロバスト性について考察した。 また, 収束率に拘束される後悔は, 一定時間収束によって一定であることを示す。 ハイパーパラメータは直感的な解釈を持ち、要求を所望の収束率に合わせるように調整することができる。 本研究では,提案手法の収束特性を,最先端最適化アルゴリズムに対する数値例で検証する。 我々の研究は、連続時間フローの離散化による新しい最適化アルゴリズムの開発に関する洞察を提供する。

関連論文リスト

• 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)
• 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)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  我々は、(離散時間)リアプノフ安定性理論が、必ずしも勾配ベースではない最適化アルゴリズムの分析(および潜在的な設計)において、いかに強力なツールとして役立つかを示す。 本稿では,不完全データベイズフレームワークにおけるパラメータ推定を,MAP-EM (maximum a reari expectation-maximization) と呼ばれる一般的な最適化アルゴリズムを用いて行うことに着目したML問題について述べる。 高速収束(線形あるいは二次的)が達成され,S&Cアプローチを使わずに発表することが困難であった可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-23T01:34:18Z)
• Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives [97.16266088683061]
  この論文は、運動量に基づく最適化アルゴリズムにおいてシンプレクティックな離散化スキームが重要であることを厳格に証明している。 これは加速収束を示すアルゴリズムの特性を提供する。
  論文  参考訳（メタデータ） (2020-02-28T00:32:47Z)
• Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problem [27.09339991866556]
  本稿では,コントローラの空間を直接探索することにより,未知の計算系に対する最適制御を求める。 我々は、安定化フィードバックゲインの勾配-フローのダイナミクスセットに焦点をあてて、そのような手法の性能と効率を最小化するための一歩を踏み出した。
  論文  参考訳（メタデータ） (2019-12-26T16:56:59Z)

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

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