論文の概要: Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equations

• arxiv url: http://arxiv.org/abs/2112.13826v3
• Date: Mon, 31 Jul 2023 15:12:29 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-02 01:17:37.111754
• Title: Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution Differential Equations
• Title（参考訳）: 高分解能微分方程式による鞍点オプティマイザのラストイテレート収束
• Authors: Tatjana Chavdarova, Michael I. Jordan and Manolis Zampetakis
• Abstract要約: 広く使われている1次サドル点最適化法は、帰納的導出時に同一の連続時間常微分方程式(ODE)を導出する。 しかし、これらの方法の収束特性は、単純な双線型ゲームでさえ質的に異なる。 いくつかのサドル点最適化法のための微分方程式モデルの設計に流体力学の研究フレームワークを採用する。
• 参考スコア（独自算出の注目度）: 83.3201889218775
• 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) that is identical to that of the Gradient Descent Ascent (GDA) method when derived naively. However, the convergence properties of these methods are qualitatively different, even on simple bilinear games. Thus the ODE perspective, which has proved powerful in analyzing single-objective optimization methods, has not played a similar role in saddle-point optimization. We adopt a framework studied in fluid dynamics -- known as High-Resolution Differential Equations (HRDEs) -- to design differential equation models for several saddle-point optimization methods. Critically, these HRDEs are distinct for various saddle-point optimization methods. Moreover, in bilinear games, the convergence properties of the HRDEs match the qualitative features of the corresponding discrete methods. Additionally, we show that the HRDE of Optimistic Gradient Descent Ascent (OGDA) exhibits \emph{last-iterate convergence} for general monotone variational inequalities. Finally, we provide rates of convergence for the \emph{best-iterate convergence} of the OGDA method, relying solely on the first-order smoothness of the monotone operator.
• Abstract（参考訳）: 広く使われている1次サドル点最適化法は、導出時のグラディエントDescent Ascent(GDA)法と同一の連続時間常微分方程式(ODE)を導出する。 しかし、これらの方法の収束特性は単純双線型ゲームでも定性的に異なる。 したがって、単目的最適化法の解析において強力であることが証明されたODEパースペクティブは、サドルポイント最適化において同様の役割を果たさなかった。 本研究では,高分解能微分方程式 (HRDE) と呼ばれる流体力学の枠組みを,いくつかのサドル点最適化法のための微分方程式モデルの設計に適用する。 批判的に、これらのHRDEは様々なサドルポイント最適化法で異なる。 さらに、双線型ゲームでは、HRDEの収束特性は対応する離散メソッドの定性的特徴と一致する。 さらに,OGDA(Optimistic Gradient Descent Ascent)のHRDEは,一般単調変分不等式に対して,emph{last-iterate convergence}を示すことを示した。 最後に、OGDA法におけるemph{best-iterate convergence} に対して、単調作用素の1次滑らかさのみに依存する収束率を与える。

関連論文リスト

• 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)

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

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