論文の概要: On the connections between optimization algorithms, Lyapunov functions,
and differential equations: theory and insights
- arxiv url: http://arxiv.org/abs/2305.08658v1
- Date: Mon, 15 May 2023 14:03:16 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-16 14:13:53.831382
- Title: On the connections between optimization algorithms, Lyapunov functions,
and differential equations: theory and insights
- Title（参考訳）: 最適化アルゴリズム、リャプノフ関数、微分方程式の接続について:理論と洞察
- Authors: Paul Dobson and Jesus Maria Sanz-Serna and Konstantinos Zygalakis
- Abstract要約: 微分方程式と最適化アルゴリズムの接続を$m$-stronglyと$L$-smooth convex関数に対して検討する。
我々は、Polyak ODE に対する新しい Lyapunov 関数を求め、この ODE と Nesterov のアルゴリズムの接続を再検討する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study connections between differential equations and optimization
algorithms for $m$-strongly and $L$-smooth convex functions through the use of
Lyapunov functions by generalizing the Linear Matrix Inequality framework
developed by Fazylab et al. in 2018. Using the new framework we derive
analytically a new (discrete) Lyapunov function for a two-parameter family of
Nesterov optimization methods and characterize their convergence rate. This
allows us to prove a convergence rate that improves substantially on the
previously proven rate of Nesterov's method for the standard choice of
coefficients, as well as to characterize the choice of coefficients that yields
the optimal rate. We obtain a new Lyapunov function for the Polyak ODE and
revisit the connection between this ODE and the Nesterov's algorithms. In
addition discuss a new interpretation of Nesterov method as an additive
Runge-Kutta discretization and explain the structural conditions that
discretizations of the Polyak equation should satisfy in order to lead to
accelerated optimization algorithms.
- Abstract（参考訳）: ファジラブらによって2018年に開発された線形行列不等式フレームワークを一般化することにより、リアプノフ関数を用いて微分方程式と$m$-stronglyおよび$L$-smooth convex関数の最適化アルゴリズムの接続について検討する。
新しいフレームワークを用いて、ネステロフ最適化手法の2パラメータファミリーに対する新しい(離散的な)リアプノフ関数を解析的に導き、それらの収束率を特徴づける。
これにより、これまで証明されていた係数の標準的な選択に対するネステロフの方法よりも大幅に改善された収束率を証明でき、また、最適率を得る係数の選択を特徴づけることができる。
我々は、Polyak ODE に対する新しい Lyapunov 関数を求め、この ODE と Nesterov のアルゴリズムの接続を再検討する。
さらに, 付加的ランジュ・クッタ離散化としてネステロフ法を新たに解釈し, ポリアク方程式の離散化が最適化アルゴリズムを高速化するために満たすべき構造条件を説明する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。