論文の概要: Last-Iterate Convergence of Saddle Point Optimizers via High-Resolution
Differential Equations
- arxiv url: http://arxiv.org/abs/2112.13826v1
- Date: Mon, 27 Dec 2021 18:31:34 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-28 15:09:55.764452
- Title: Last-Iterate Convergence of Saddle Point Optimizers via High-Resolution
Differential Equations
- Title(参考訳): 高分解能微分方程式による鞍点オプティマイザのラストイテレート収束
- Authors: Tatjana Chavdarova, Michael I. Jordan and Manolis Zampetakis
- Abstract要約: OGDA (Optimistic Gradient Descent Ascent) のHRDEは, 一般単調変分不等式に対する最終点収束性を示す。
我々は, 単調作用素の1次滑らかさのみに依存するOGDA法の最適収束率を示す。
- 参考スコア(独自算出の注目度): 83.81435198149667
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Several widely-used first-order saddle point optimization methods yield an
identical continuous-time ordinary differential equation (ODE) to that of the
Gradient Descent Ascent (GDA) method when derived naively. However, their
convergence properties are very different even on simple bilinear games.
We use a technique from fluid dynamics called High-Resolution Differential
Equations (HRDEs) to design ODEs of several saddle point optimization methods.
On bilinear games, the convergence properties of the derived HRDEs correspond
to that of the starting discrete methods. Using these techniques, we show that
the HRDE of Optimistic Gradient Descent Ascent (OGDA) has last-iterate
convergence for general monotone variational inequalities. To our knowledge,
this is the first continuous-time dynamics shown to converge for such a general
setting. Moreover, we provide the rates for the best-iterate convergence of the
OGDA method, relying solely on the first-order smoothness of the monotone
operator.
- Abstract(参考訳): 広く使われている一階サドル点最適化法は、勾配降下上昇法 (gda) 法と同一の連続時間常微分方程式 (ode) を与える。
しかし、それらの収束特性は単純双線型ゲームでも大きく異なる。
高分解能微分方程式(hrdes)と呼ばれる流体力学の手法を用いて複数の鞍点最適化法のodeを設計する。
双線型ゲームでは、導出したHRDEの収束特性は開始離散法の収束特性に対応する。
これらの手法を用いて,OGDA (Optimistic Gradient Descent Ascent) のHRDEは,一般単調変分不等式に対する最終点収束性を示す。
我々の知る限り、これはそのような一般的な設定に収束することが示されている最初の連続時間力学である。
さらに, 単調作用素の1次滑らかさにのみ依存して, OGDA法の最適点収束率を示す。
関連論文リスト
- A Natural Primal-Dual Hybrid Gradient Method for Adversarial Neural Network Training on Solving Partial Differential Equations [9.588717577573684]
偏微分方程式(PDE)を解くためのスケーラブルな事前条件付き原始ハイブリッド勾配アルゴリズムを提案する。
本稿では,提案手法の性能を,一般的なディープラーニングアルゴリズムと比較する。
その結果,提案手法は効率的かつ堅牢に動作し,安定に収束することが示唆された。
論文 参考訳(メタデータ) (2024-11-09T20:39:10Z) - ODE-based Learning to Optimize [28.380622776436905]
我々は、慣性系とヘッセン駆動制振方程式(ISHD)を統合した包括的枠組みを提案する。
収束・安定条件を考慮した停止時間を最小化することを目的とした新しい学習法(L2O)を定式化する。
本フレームワークの実証検証は,多種多様な最適化問題に対する広範な数値実験を通じて行われる。
論文 参考訳(メタデータ) (2024-06-04T06:39:45Z) - Backward error analysis and the qualitative behaviour of stochastic
optimization algorithms: Application to stochastic coordinate descent [1.534667887016089]
一般最適化法の力学を近似した微分方程式のクラスを提案する。
座標降下の場合の修正方程式の安定性について検討する。
論文 参考訳(メタデータ) (2023-09-05T09:39:56Z) - A Homogenization Approach for Gradient-Dominated Stochastic Optimization [6.1144486886258065]
勾配支配を享受する関数に対する同次二階降下法(SHSOD)を提案する。
以上の結果から,SHSODMは勾配優先最適化法において,他の2次法で達成された最もよく知られたサンプルの複雑さと一致していることがわかった。
論文 参考訳(メタデータ) (2023-08-21T11:03:04Z) - Comparison of Single- and Multi- Objective Optimization Quality for
Evolutionary Equation Discovery [77.34726150561087]
進化的微分方程式の発見は、より優先順位の低い方程式を得るための道具であることが証明された。
提案した比較手法は、バーガーズ方程式、波動方程式、コルテヴェーグ・ド・ブリーズ方程式といった古典的なモデル例で示される。
論文 参考訳(メタデータ) (2023-06-29T15:37:19Z) - An Optimization-based Deep Equilibrium Model for Hyperspectral Image
Deconvolution with Convergence Guarantees [71.57324258813675]
本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。
新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。
導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
論文 参考訳(メタデータ) (2023-06-10T08:25:16Z) - First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
本稿では,一階変分法の理論解析のための統一的アプローチを提案する。
提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。
凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
論文 参考訳(メタデータ) (2023-05-25T11:11:31Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳(メタデータ) (2020-12-21T17:29:58Z) - Robust, Accurate Stochastic Optimization for Variational Inference [68.83746081733464]
また, 共通最適化手法は, 問題が適度に大きい場合, 変分近似の精度が低下することを示した。
これらの結果から,基礎となるアルゴリズムをマルコフ連鎖の生成とみなして,より堅牢で正確な最適化フレームワークを開発する。
論文 参考訳(メタデータ) (2020-09-01T19:12:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。