論文の概要: SDEs for Minimax Optimization
- arxiv url: http://arxiv.org/abs/2402.12508v1
- Date: Mon, 19 Feb 2024 20:18:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-21 18:26:43.551831
- Title: SDEs for Minimax Optimization
- Title(参考訳): ミニマックス最適化のためのSDE
- Authors: Enea Monzio Compagnoni, Antonio Orvieto, Hans Kersting, Frank Norbert
Proske, Aurelien Lucchi
- Abstract要約: 本稿では,微分方程式(SDE)を用いてミニマックス収束の解析と比較を行う。
グラディエント・ディキセント、エクストラグラディエント、ハミルトニアン・ディキセントのSDEモデルはアルゴリズムの近似である。
この観点はまた、伊藤計算の原理に基づく統一的で単純化された分析戦略を可能にする。
- 参考スコア(独自算出の注目度): 11.290653315174382
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Minimax optimization problems have attracted a lot of attention over the past
few years, with applications ranging from economics to machine learning. While
advanced optimization methods exist for such problems, characterizing their
dynamics in stochastic scenarios remains notably challenging. In this paper, we
pioneer the use of stochastic differential equations (SDEs) to analyze and
compare Minimax optimizers. Our SDE models for Stochastic Gradient
Descent-Ascent, Stochastic Extragradient, and Stochastic Hamiltonian Gradient
Descent are provable approximations of their algorithmic counterparts, clearly
showcasing the interplay between hyperparameters, implicit regularization, and
implicit curvature-induced noise. This perspective also allows for a unified
and simplified analysis strategy based on the principles of It\^o calculus.
Finally, our approach facilitates the derivation of convergence conditions and
closed-form solutions for the dynamics in simplified settings, unveiling
further insights into the behavior of different optimizers.
- Abstract(参考訳): 最小限の最適化問題は、経済学から機械学習まで、ここ数年で多くの注目を集めている。
このような問題に対して高度な最適化手法が存在するが、確率的シナリオにおけるそのダイナミクスの特徴付けは特に難しい。
本稿では,ミニマックスオプティマイザを解析・比較するために確率微分方程式(sdes)を用いた。
確率的勾配勾配勾配勾配勾配, 確率的ハミルトン勾配勾配, および確率的ハミルトン勾配のSDEモデルは, そのアルゴリズムの近似として, ハイパーパラメータ間の相互作用, 暗黙的な正規化, 暗黙的な曲率誘発雑音を明らかに示す。
この観点はまた、it\^o計算の原理に基づく統一的かつ単純化された分析戦略を可能にする。
最後に, 提案手法は, 簡易な設定における動的条件の収束条件と閉形式解の導出を容易にし, 異なるオプティマイザの挙動に関するさらなる知見を明らかにする。
関連論文リスト
- Backward error analysis and the qualitative behaviour of stochastic
optimization algorithms: Application to stochastic coordinate descent [1.534667887016089]
一般最適化法の力学を近似した微分方程式のクラスを提案する。
座標降下の場合の修正方程式の安定性について検討する。
論文 参考訳(メタデータ) (2023-09-05T09:39:56Z) - Accelerated stochastic approximation with state-dependent noise [7.623467689146604]
勾配観測における2次雑音に対する一般仮定の下での滑らかな凸最適化問題を考察する。
このような問題は、統計学におけるよく知られた一般化された線形回帰問題において、様々な応用において自然に発生する。
SAGDとSGEは、適切な条件下で、最適収束率を達成することを示す。
論文 参考訳(メタデータ) (2023-07-04T06:06:10Z) - Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax
Problems [39.197569803430646]
最小限の最適化は、敵対的ネットワーク(GAN)や敵対的トレーニングなど、多くの機械学習タスクにおいて重要な役割を果たす。
近年,ミニマックス問題の解法として多種多様な最適化手法が提案されているが,そのほとんどは分散設定を無視している。
論文 参考訳(メタデータ) (2023-04-21T11:38:41Z) - Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。
我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。
提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
論文 参考訳(メタデータ) (2022-11-14T21:54:31Z) - 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) - Last-Iterate Convergence of Saddle-Point Optimizers via High-Resolution
Differential Equations [83.3201889218775]
広く使われている1次サドル点最適化法は、帰納的導出時に同一の連続時間常微分方程式(ODE)を導出する。
しかし、これらの方法の収束特性は、単純な双線型ゲームでさえ質的に異なる。
いくつかのサドル点最適化法のための微分方程式モデルの設計に流体力学の研究フレームワークを採用する。
論文 参考訳(メタデータ) (2021-12-27T18:31:34Z) - Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models [0.2741266294612776]
我々は高次元ランダム最小二乗問題に対して運動量を持つ勾配アルゴリズムのクラスを解析する。
固定運動量パラメータを持つ(小バッチ)運動量では,ステップサイズを正確に調整した場合,SGDよりも実際の性能向上は得られないことを示す。
非強凸条件では、運動量を用いてSGDよりも大きな改善が得られる。
論文 参考訳(メタデータ) (2021-06-07T15:08:24Z) - On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。
これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
論文 参考訳(メタデータ) (2021-04-30T08:50:24Z) - Fast Distributionally Robust Learning with Variance Reduced Min-Max
Optimization [85.84019017587477]
分散的ロバストな教師付き学習は、現実世界のアプリケーションのための信頼性の高い機械学習システムを構築するための重要なパラダイムとして登場している。
Wasserstein DRSLを解くための既存のアルゴリズムは、複雑なサブプロブレムを解くか、勾配を利用するのに失敗する。
我々はmin-max最適化のレンズを通してwaserstein drslを再検討し、スケーラブルで効率的に実装可能な超勾配アルゴリズムを導出する。
論文 参考訳(メタデータ) (2021-04-27T16:56:09Z) - Convergence Properties of Stochastic Hypergradients [38.64355126221992]
大規模データセットにおける低レベルの問題が経験的リスクである場合に重要となる過勾配の近似スキームについて検討する。
本研究では,理論解析を支援する数値実験を行い,実際にハイパーグラディエントを用いることの利点を示す。
論文 参考訳(メタデータ) (2020-11-13T20:50:36Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。