論文の概要: Constants of Motion: The Antidote to Chaos in Optimization and Game
Dynamics
- arxiv url: http://arxiv.org/abs/2109.03974v1
- Date: Wed, 8 Sep 2021 23:37:13 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-10 14:01:51.952854
- Title: Constants of Motion: The Antidote to Chaos in Optimization and Game
Dynamics
- Title（参考訳）: 動きの定数:最適化とゲームダイナミクスにおけるカオスに対するアンチドテ
- Authors: Georgios Piliouras and Xiao Wang
- Abstract要約: オンライン最適化とゲームダイナミクスに関する最近のいくつかの研究は、強い負の複雑さの結果を確立している。
これらの結果は次の質問を動機付けている: そのような力学の規則性を保証できる方法論ツールは?
運動の定数という不変函数の存在を証明することが、この方向の基本的な寄与であることを示す。
- 参考スコア（独自算出の注目度）: 36.09131227448527
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Several recent works in online optimization and game dynamics have
established strong negative complexity results including the formal emergence
of instability and chaos even in small such settings, e.g., $2\times 2$ games.
These results motivate the following question: Which methodological tools can
guarantee the regularity of such dynamics and how can we apply them in standard
settings of interest such as discrete-time first-order optimization dynamics?
We show how proving the existence of invariant functions, i.e., constant of
motions, is a fundamental contribution in this direction and establish a
plethora of such positive results (e.g. gradient descent, multiplicative
weights update, alternating gradient descent and manifold gradient descent)
both in optimization as well as in game settings. At a technical level, for
some conservation laws we provide an explicit and concise closed form, whereas
for other ones we present non-constructive proofs using tools from dynamical
systems.
- Abstract（参考訳）: オンライン最適化とゲームダイナミクスに関する最近のいくつかの研究は、不安定性とカオスの形式的な出現を含む強い負の複雑さの成果を確立している。
どの方法論ツールがそのようなダイナミクスの規則性を保証することができるのか、そしてそれらを離散時間一階最適化ダイナミクスのような関心の標準的な設定にどのように適用できるのか?
不変関数、すなわち運動定数の存在の証明が、この方向への基本的な貢献であることを示すとともに、そのような正の結果の多さ(例えば、等)を確立する。
勾配降下、乗法重み更新、交互勾配降下、多様体勾配降下) 最適化とゲーム設定の両方において。
技術的なレベルでは、いくつかの保存法則は明示的で簡潔な閉形式を提供するが、他の法則では動的システムからのツールを用いた非構成的証明を示す。
関連論文リスト
- Series of Hessian-Vector Products for Tractable Saddle-Free Newton
Optimisation of Neural Networks [1.3654846342364308]
絶対値固有値を持つ正逆 Hessian を,一階乗算可能な最適化アルゴリズムで効率的に利用できることを示す。
この級数のt-runは、他の1階と2階の最適化手法に匹敵する新しい最適化を提供する。
論文 参考訳（メタデータ） (2023-10-23T13:11:30Z) - ELRA: Exponential learning rate adaption gradient descent optimization
method [83.88591755871734]
我々は, 高速(指数率), ab initio(超自由)勾配に基づく適応法を提案する。
本手法の主な考え方は,状況認識による$alphaの適応である。
これは任意の次元 n の問題に適用でき、線型にしかスケールできない。
論文 参考訳（メタデータ） (2023-09-12T14:36:13Z) - Omega: Optimistic EMA Gradients [17.11877451333674]
我々は,その更新ルールに履歴勾配を組み込むことで,騒音の影響を緩和する楽観的な更新手法であるOmegaを紹介する。
収束保証は提供していないが,ゲーム実験により,線形プレイヤーに適用した場合に,オメガが楽観的勾配法より優れていることが示された。
論文 参考訳（メタデータ） (2023-06-13T16:56:13Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - Value Iteration in Continuous Actions, States and Time [99.00362538261972]
連続状態と動作に対する連続的適合値反復(cFVI)アルゴリズムを提案する。
非線形制御アフィンダイナミクスに対して最適なポリシを導出することができる。
物理システムのビデオは、urlhttps://sites.google.com/view/value-iteration.comで入手できる。
論文 参考訳（メタデータ） (2021-05-10T21:40:56Z) - Self-Tuning Stochastic Optimization with Curvature-Aware Gradient
Filtering [53.523517926927894]
サンプルごとのHessian-vector積と勾配を用いて、自己チューニングの二次構造を構築する。
モデルに基づく手続きが雑音勾配設定に収束することを証明する。
これは自己チューニング二次体を構築するための興味深いステップである。
論文 参考訳（メタデータ） (2020-11-09T22:07:30Z) - Accelerating Smooth Games by Manipulating Spectral Shapes [51.366219027745174]
滑らかなゲームにおけるアクセラレーションを特徴付けるために行列反復理論を用いる。
スペクトル形状の変換として, 勾配法, 指数勾配法について述べる。
バイリニアゲームに最適なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-01-02T19:21:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。