論文の概要: On the connections between optimization algorithms, Lyapunov functions, and differential equations: theory and insights

• arxiv url: http://arxiv.org/abs/2305.08658v3
• Date: Mon, 20 May 2024 11:42:43 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-22 01:00:22.538365
• Title: On the connections between optimization algorithms, Lyapunov functions, and differential equations: theory and insights
• Title（参考訳）: 最適化アルゴリズム、リャプノフ関数、微分方程式の接続について:理論と洞察
• Authors: Paul Dobson, Jesus Maria Sanz-Serna, Konstantinos Zygalakis,
• Abstract要約: Fazylabらによって導入されたフレームワークを再検討し、離散的かつ連続的な時間で最適化アルゴリズムのためのLyapunov関数を構築する。 滑らかで強凸な目的関数に対して、そのような構成に必要な要求を緩和する。 文献で利用できるものよりも良い収束率を証明します。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the general framework introduced by Fazylab et al. (SIAM J. Optim. 28, 2018) to construct Lyapunov functions for optimization algorithms in discrete and continuous time. For smooth, strongly convex objective functions, we relax the requirements necessary for such a construction. As a result we are able to prove for Polyak's ordinary differential equations and for a two-parameter family of Nesterov algorithms rates of convergence that improve on those available in the literature. We analyse the interpretation of Nesterov algorithms as discretizations of the Polyak equation. We show that the algorithms are instances of Additive Runge-Kutta integrators and discuss the reasons why most discretizations of the differential equation do not result in optimization algorithms with acceleration. We also introduce a modification of Polyak's equation and study its convergence properties. Finally we extend the general framework to the stochastic scenario and consider an application to random algorithms with acceleration for overparameterized models; again we are able to prove convergence rates that improve on those in the literature.
• Abstract（参考訳）: 我々はFazylab et al (SIAM J. Optim. 28 2018)によって導入された一般的なフレームワークを再検討し、離散的かつ連続的な時間で最適化アルゴリズムのためのリアプノフ関数を構築する。 滑らかで強凸な目的関数に対して、そのような構成に必要な要求を緩和する。 その結果、Polyak の常微分方程式と、Nesterov アルゴリズムの 2 パラメータの族に対して、文献で利用できるものよりも良い収束率を証明できる。 我々はNesterovアルゴリズムの解釈をPolyak方程式の離散化として分析する。 アルゴリズムが加法ランゲ・クッタ積分器の例であることを示し、微分方程式のほとんどの離散化が加速を伴う最適化アルゴリズムを導出しない理由を論じる。 また、Polyak方程式の修正を導入し、収束特性について研究する。 最後に、一般のフレームワークを確率的シナリオに拡張し、過パラメータモデルに対する加速度を伴うランダムアルゴリズムへの応用を検討する。

関連論文リスト

• Modeling AdaGrad, RMSProp, and Adam with Integro-Differential Equations [0.0]
  本稿では,AdaGrad,RMSProp,Adam最適化アルゴリズムの連続時間定式化を提案する。 我々はこれらの方程式の数値シミュレーションを行い、それらの妥当性を元のアルゴリズムの正確な近似として示す。
  論文  参考訳（メタデータ） (2024-11-14T19:00:01Z)
• Convergence of Expectation-Maximization Algorithm with Mixed-Integer Optimization [5.319361976450982]
  本稿では,特定の種類のEMアルゴリズムの収束を保証する一連の条件を紹介する。 本研究では,混合整数非線形最適化問題の解法として,反復アルゴリズムの新しい解析手法を提案する。
  論文  参考訳（メタデータ） (2024-01-31T11:42:46Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
  一般化された複合ミラー降下アルゴリズムの一群を提案し,解析する。 適応的なステップサイズでは、提案アルゴリズムは問題の事前知識を必要とせずに収束する。 決定集合の低次元構造を高次元問題に活用する。
  論文  参考訳（メタデータ） (2022-11-21T18:31:43Z)
• An Algebraically Converging Stochastic Gradient Descent Algorithm for Global Optimization [14.336473214524663]
  アルゴリズムの主要な構成要素は、目的関数の値に基づくランダム性である。 アルゴリズムの収束を代数学で証明し、パラメータ空間でチューニングする。 アルゴリズムの効率性とロバスト性を示す数値的な例をいくつか提示する。
  論文  参考訳（メタデータ） (2022-04-12T16:27:49Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。 厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。 このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
  論文  参考訳（メタデータ） (2021-11-29T15:10:09Z)
• 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)
• Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives [97.16266088683061]
  この論文は、運動量に基づく最適化アルゴリズムにおいてシンプレクティックな離散化スキームが重要であることを厳格に証明している。 これは加速収束を示すアルゴリズムの特性を提供する。
  論文  参考訳（メタデータ） (2020-02-28T00:32:47Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)

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

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