論文の概要: A Contraction Theory Approach to Optimization Algorithms from Acceleration Flows

• arxiv url: http://arxiv.org/abs/2105.08832v1
• Date: Tue, 18 May 2021 21:11:37 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-20 13:42:32.001438
• Title: A Contraction Theory Approach to Optimization Algorithms from Acceleration Flows
• Title（参考訳）: 加速流からの最適化アルゴリズムへの縮約理論のアプローチ
• Authors: Pedro Cisneros-Velarde, Francesco Bullo
• Abstract要約: 私たちは、適切なODEを設計し、識別するための原則化された方法論を提供するために収縮理論を使用します。 本稿では, ODE の新しいシステム,すなわち Accelerated-Contracting-Nesterov フローを提案する。 注目すべきことに、この流れの単純明示的なオイラー離散化はネステロフ加速度法に対応する。
• 参考スコア（独自算出の注目度）: 1.90365714903665
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Much recent interest has focused on the design of optimization algorithms from the discretization of an associated optimization flow, i.e., a system of differential equations (ODEs) whose trajectories solve an associated optimization problem. Such a design approach poses an important problem: how to find a principled methodology to design and discretize appropriate ODEs. This paper aims to provide a solution to this problem through the use of contraction theory. We first introduce general mathematical results that explain how contraction theory guarantees the stability of the implicit and explicit Euler integration methods. Then, we propose a novel system of ODEs, namely the Accelerated-Contracting-Nesterov flow, and use contraction theory to establish it is an optimization flow with exponential convergence rate, from which the linear convergence rate of its associated optimization algorithm is immediately established. Remarkably, a simple explicit Euler discretization of this flow corresponds to the Nesterov acceleration method. Finally, we present how our approach leads to performance guarantees in the design of optimization algorithms for time-varying optimization problems.
• Abstract（参考訳）: 最近では、関連する最適化フローの離散化、すなわち軌道が関連する最適化問題を解く微分方程式(ODE)システムから最適化アルゴリズムの設計に焦点が当てられている。 このような設計アプローチは、適切なODEを設計し、識別するための原則化された方法論を見つける方法という、重要な問題を引き起こします。 本稿では, この問題の解法として, 縮約理論を用いた解法を提案する。 まず、縮退理論が暗黙的かつ明示的なオイラー積分法の安定性をいかに保証するかを説明する一般的な数学的結果を紹介する。 そこで我々は,ODEの新しいシステム,すなわち Accelerated-Contracting-Nesterov フロー,およびそれを確立するための収縮理論を,指数収束率を持つ最適化フローとして提案し,その関連する最適化アルゴリズムの線形収束率を即時確立する。 この流れの単純明示的なオイラー離散化はネステロフ加速度法に対応する。 最後に,時間変動最適化問題に対する最適化アルゴリズムの設計において,このアプローチが性能保証にどのようにつながるかを示す。

関連論文リスト

• ODE-based Learning to Optimize [28.380622776436905]
  我々は、慣性系とヘッセン駆動制振方程式(ISHD)を統合した包括的枠組みを提案する。 収束・安定条件を考慮した停止時間を最小化することを目的とした新しい学習法(L2O)を定式化する。 本フレームワークの実証検証は,多種多様な最適化問題に対する広範な数値実験を通じて行われる。
  論文  参考訳（メタデータ） (2024-06-04T06:39:45Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。 本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。 Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
  論文  参考訳（メタデータ） (2023-12-28T23:15:18Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。 1つの典型的な戦略はアルゴリズムのアンローリングであり、これは反復解法の操作による自動微分に依存している。 本稿では,非ロール最適化の後方通過に関する理論的知見を提供し,効率よく解けるバックプロパゲーション解析モデルを生成するシステムに繋がる。
  論文  参考訳（メタデータ） (2023-01-28T01:50:42Z)
• A Derivation of Nesterov's Accelerated Gradient Algorithm from Optimal Control Theory [0.0]
  ネステロフの加速勾配アルゴリズムは第一原理から導かれる。 結果の微分方程式のオイラー離散化はネステロフのアルゴリズムを生成する。
  論文  参考訳（メタデータ） (2022-03-29T19:26:20Z)
• Breaking the Convergence Barrier: Optimization via Fixed-Time Convergent Flows [4.817429789586127]
  本稿では, 固定時間安定力学系の概念に基づいて, 加速を実現するための多言語最適化フレームワークを提案する。 提案手法の高速化された収束特性を,最先端の最適化アルゴリズムに対して様々な数値例で検証する。
  論文  参考訳（メタデータ） (2021-12-02T16:04:40Z)
• Optimization on manifolds: A symplectic approach [127.54402681305629]
  本稿では、最適化問題を解くための一般的な枠組みとして、ディラックの制約付きハミルトン系理論の散逸拡張を提案する。 我々の(加速された)アルゴリズムのクラスは単純で効率的なだけでなく、幅広い文脈にも適用できる。
  論文  参考訳（メタデータ） (2021-07-23T13:43:34Z)
• First-Order Optimization Inspired from Finite-Time Convergent Flows [26.931390502212825]
  本稿では, 1次有限時間流に対するオイラー離散化を提案し, 決定論的および決定論的設定において収束を保証する。 次に、提案したアルゴリズムを学術的な例に適用し、深層ニューラルネットワークトレーニングを行い、SVHNデータセット上でそのパフォーマンスを実証的にテストする。 提案手法は,標準最適化法に対してより高速な収束を示す。
  論文  参考訳（メタデータ） (2020-10-06T19:28:00Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。 提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。 加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
  論文  参考訳（メタデータ） (2020-06-11T18:49:06Z)

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

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