論文の概要: The connections between Lyapunov functions for some optimization
algorithms and differential equations
- arxiv url: http://arxiv.org/abs/2009.00673v2
- Date: Mon, 11 Jan 2021 11:18:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-23 02:07:12.848715
- Title: The connections between Lyapunov functions for some optimization
algorithms and differential equations
- Title（参考訳）: 最適化アルゴリズムにおけるリアプノフ関数と微分方程式との接続
- Authors: J.M. Sanz-Serna and Konstantinos C. Zygalakis
- Abstract要約: 我々は、ネステロフ最適化手法の族に対する(離散的な)リャプノフ関数を解析的に導出する。
重球法のようなODEの族における典型的な離散化の大多数は、ここで構築されたリャプノフ関数に類似した性質を持つリャプノフ函数を持たないことを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this manuscript, we study the properties of a family of second-order
differential equations with damping, its discretizations and their connections
with accelerated optimization algorithms for $m$-strongly convex and $L$-smooth
functions. In particular, using the Linear Matrix Inequality LMI framework
developed by \emph{Fazlyab et. al. $(2018)$}, we derive analytically a
(discrete) Lyapunov function for a two-parameter family of Nesterov
optimization methods, which allows for the complete characterization of their
convergence rate. In the appropriate limit, this family of methods may be seen
as a discretization of a family of second-order ordinary differential equations
for which we construct(continuous) Lyapunov functions by means of the LMI
framework. The continuous Lyapunov functions may alternatively, be obtained by
studying the limiting behaviour of their discrete counterparts. Finally, we
show that the majority of typical discretizations of the family of ODEs, such
as the Heavy ball method, do not possess Lyapunov functions with properties
similar to those of the Lyapunov function constructed here for the Nesterov
method.
- Abstract（参考訳）: 本稿では,減衰を伴う二階微分方程式の族の性質,その離散化,および高速化最適化アルゴリズムとの接続について,m$-strongly convex および $L$-smooth 関数について検討する。
特に、emph{Fazlyab et. によって開発された線形行列不等式 LMI フレームワークを使用する。
アル
$(2018)$} は、ネステロフ最適化法の2パラメータ族に対する解析的(離散的な)リャプノフ函数を導出し、収束率の完全な特徴づけを可能にする。
適切な極限において、この方法の族は LMI フレームワークを用いて Lyapunov 関数を構成する二階常微分方程式の族(英語版)の離散化と見なすことができる。
連続 lyapunov 関数は、その離散函数の制限挙動を研究することによって得られる。
最後に、重球法のようなODEの族における典型的な離散化の大部分は、ネステロフ法のためにここで構築されたリャプノフ関数に類似した性質を持つリャプノフ関数を持たないことを示す。
関連論文リスト
- Quantum algorithm for linear non-unitary dynamics with near-optimal
dependence on all parameters [5.471398994781521]
一般線型非ユニタリ進化作用素をユニタリ進化作用素の線形結合として表現するアイデンティティの族を導入する。
この定式化は、最近導入されたハミルトニアンシミュレーション(LCHS)法の線形結合の精度を指数関数的に向上させることができる。
論文 参考訳（メタデータ） (2023-12-06T21:30:26Z) - GloptiNets: Scalable Non-Convex Optimization with Certificates [61.50835040805378]
本稿では,ハイパーキューブやトーラス上のスムーズな関数を扱う証明書を用いた非キューブ最適化手法を提案する。
スペクトルの減衰に固有の対象関数の正則性を活用することにより、正確な証明を取得し、高度で強力なニューラルネットワークを活用することができる。
論文 参考訳（メタデータ） (2023-06-26T09:42:59Z) - On the connections between optimization algorithms, Lyapunov functions, and differential equations: theory and insights [0.0]
Fazylabらによって導入されたフレームワークを再検討し、離散的かつ連続的な時間で最適化アルゴリズムのためのLyapunov関数を構築する。
滑らかで強凸な目的関数に対して、そのような構成に必要な要求を緩和する。
文献で利用できるものよりも良い収束率を証明します。
論文 参考訳（メタデータ） (2023-05-15T14:03:16Z) - Understanding Accelerated Gradient Methods: Lyapunov Analyses and
Hamiltonian Assisted Interpretations [1.0152838128195465]
我々は、滑らかな凸関数と強凸関数を最小化するために、以前研究したよりも一般的な1次アルゴリズムの2つのクラスを定式化する。
我々は、新しい離散リアプノフ解析を通じて、強い凸条件と一般的な凸条件でネステロフの手法と一致する加速収束率を達成するのに十分な条件を確立する。
我々は、ハミルトン関数といくつかの解釈可能な操作を直接ベースとした、ハミルトン支援勾配法と呼ばれる新しい離散アルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2023-04-20T03:03:30Z) - An inexact LPA for DC composite optimization and application to matrix completions with outliers [5.746154410100363]
本稿では,複合最適化問題のクラスについて述べる。
合成構造を利用することで、ポテンシャル関数が反復列において1/2$のKL特性を持つ条件を与える。
論文 参考訳（メタデータ） (2023-03-29T16:15:34Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。
線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
論文 参考訳（メタデータ） (2022-04-20T21:15:38Z) - A Discrete Variational Derivation of Accelerated Methods in Optimization [68.8204255655161]
最適化のための異なる手法を導出できる変分法を導入する。
我々は1対1の対応において最適化手法の2つのファミリを導出する。
自律システムのシンプレクティシティの保存は、ここでは繊維のみに行われる。
論文 参考訳（メタデータ） (2021-06-04T20:21:53Z) - Automated and Sound Synthesis of Lyapunov Functions with SMT Solvers [70.70479436076238]
線形、非線形(ポリノミカル)およびパラメトリックモデルに対するリャプノフ関数を合成する。
パラメトリックテンプレートからLyapunov関数を合成するための帰納的フレームワークを利用する。
論文 参考訳（メタデータ） (2020-07-21T14:45:23Z) - Optimal Bounds between $f$-Divergences and Integral Probability Metrics [8.401473551081748]
確率分布の類似性を定量化するために、$f$-divergencesとIntegral Probability Metricsが広く使われている。
両家系の関係を凸双対性の観点から体系的に研究する。
我々は、Hoeffdingの補題のような統一的な方法でよく知られた結果を回復しながら、新しい境界を得る。
論文 参考訳（メタデータ） (2020-06-10T17:39:11Z) - Formal Synthesis of Lyapunov Neural Networks [61.79595926825511]
本稿では,リアプノフ関数の自動合成法を提案する。
我々は,数値学習者と記号検証器が相互作用して,確実に正しいリアプノフニューラルネットワークを構築する,反例誘導方式を採用する。
提案手法は,Lyapunov関数を他の手法よりも高速かつ広い空間領域で合成する。
論文 参考訳（メタデータ） (2020-03-19T17:21:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。