論文の概要: Generalized Gradient Flows with Provable Fixed-Time Convergence and Fast Evasion of Non-Degenerate Saddle Points

• arxiv url: http://arxiv.org/abs/2212.03765v1
• Date: Wed, 7 Dec 2022 16:36:23 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-08 14:54:02.482044
• Title: Generalized Gradient Flows with Provable Fixed-Time Convergence and Fast Evasion of Non-Degenerate Saddle Points
• Title（参考訳）: 非退化サドル点の固定時間収束と高速蒸発を伴う一般化勾配流
• Authors: Mayank Baranwal, Param Budhraja, Vishal Raj, Ashish R. Hota
• Abstract要約: 勾配に基づく一階最適凸アルゴリズムは、機械学習タスクを含むさまざまな領域で広く適用可能である。 非デマックスサドル点を許容する関数に対しては、提案したGenFlowアルゴリズムでは、これらのサドル点を回避するのに要する時間は初期条件すべてに対して一様であることを示す。
• 参考スコア（独自算出の注目度）: 2.9822184411723645
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Gradient-based first-order convex optimization algorithms find widespread applicability in a variety of domains, including machine learning tasks. Motivated by the recent advances in fixed-time stability theory of continuous-time dynamical systems, we introduce a generalized framework for designing accelerated optimization algorithms with strongest convergence guarantees that further extend to a subclass of non-convex functions. In particular, we introduce the \emph{GenFlow} algorithm and its momentum variant that provably converge to the optimal solution of objective functions satisfying the Polyak-{\L}ojasiewicz (PL) inequality, in a fixed-time. Moreover for functions that admit non-degenerate saddle-points, we show that for the proposed GenFlow algorithm, the time required to evade these saddle-points is bounded uniformly for all initial conditions. Finally, for strongly convex-strongly concave minimax problems whose optimal solution is a saddle point, a similar scheme is shown to arrive at the optimal solution again in a fixed-time. The superior convergence properties of our algorithm are validated experimentally on a variety of benchmark datasets.
• Abstract（参考訳）: 勾配に基づく1次凸最適化アルゴリズムは、機械学習タスクを含む様々な領域で広く適用できる。 連続時間力学系の固定時間安定性理論の最近の進歩に動機づけられ、非凸関数のサブクラスにさらに拡張する最も強い収束保証を持つ高速化最適化アルゴリズムを設計するための一般化フレームワークを提案する。 特に,Polak-{\L}ojasiewicz (PL) の不等式を満たす目的関数の最適解に,固定時間で確実に収束する, \emph{GenFlow} アルゴリズムとその運動量不変量を導入する。 さらに、非退化サドル点を許容する関数に対しては、提案したGenFlowアルゴリズムでは、これらのサドル点を回避するのに要する時間は初期条件すべてに一様であることを示す。 最後に、最適解がサドル点である極小極小問題に対して、同様のスキームが固定時間内に再び最適解に到達することが示される。 このアルゴリズムの優れた収束特性は、様々なベンチマークデータセットで実験的に検証される。

関連論文リスト

• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Fixed-Time Convergence for a Class of Nonconvex-Nonconcave Min-Max Problems [5.787117733071416]
  min-max問題を解くための固定時間収束サドル点力学系を開発した。 提案手法は他のどの状態法と比較しても高速に実現できる。
  論文  参考訳（メタデータ） (2022-07-26T12:25:05Z)
• Two-Timescale Stochastic Approximation for Bilevel Optimisation Problems in Continuous-Time Models [0.0]
  本研究では,連続時間モデルにおける二段階最適化問題に対する連続時間2時間スケール近似アルゴリズムの特性を解析する。 我々はこのアルゴリズムの弱収束率を中心極限定理の形で得る。
  論文  参考訳（メタデータ） (2022-06-14T17:12:28Z)
• 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)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Sequential Subspace Search for Functional Bayesian Optimization Incorporating Experimenter Intuition [63.011641517977644]
  本アルゴリズムは,実験者のガウス過程から引き出された一組の引き数で区切られた関数空間の有限次元ランダム部分空間列を生成する。 標準ベイズ最適化は各部分空間に適用され、次の部分空間の出発点(オリジン)として用いられる最良の解である。 シミュレーションおよび実世界の実験,すなわちブラインド関数マッチング,アルミニウム合金の最適析出強化関数の探索,深層ネットワークの学習速度スケジュール最適化において,本アルゴリズムを検証した。
  論文  参考訳（メタデータ） (2020-09-08T06:54:11Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。 提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。 加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
  論文  参考訳（メタデータ） (2020-06-11T18:49:06Z)
• 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)

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

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