論文の概要: On the Suboptimality of Negative Momentum for Minimax Optimization

• arxiv url: http://arxiv.org/abs/2008.07459v4
• Date: Tue, 26 Jan 2021 17:26:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-28 03:24:26.532420
• Title: On the Suboptimality of Negative Momentum for Minimax Optimization
• Title（参考訳）: ミニマックス最適化における負運動量の準最適性について
• Authors: Guodong Zhang, Yuanhao Wang
• Abstract要約: 負の運動量によってゲームダイナミクスの収束は局所的に加速するが、最適以下の速度で加速することを示す。 これは、この設定において明示的な収束率運動量を与える最初の研究である。
• 参考スコア（独自算出の注目度）: 9.400440302623839
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Smooth game optimization has recently attracted great interest in machine learning as it generalizes the single-objective optimization paradigm. However, game dynamics is more complex due to the interaction between different players and is therefore fundamentally different from minimization, posing new challenges for algorithm design. Notably, it has been shown that negative momentum is preferred due to its ability to reduce oscillation in game dynamics. Nevertheless, the convergence rate of negative momentum was only established in simple bilinear games. In this paper, we extend the analysis to smooth and strongly-convex strongly-concave minimax games by taking the variational inequality formulation. By connecting momentum method with Chebyshev polynomials, we show that negative momentum accelerates convergence of game dynamics locally, though with a suboptimal rate. To the best of our knowledge, this is the \emph{first work} that provides an explicit convergence rate for negative momentum in this setting.
• Abstract（参考訳）: smooth game optimizationは最近、単一目的最適化パラダイムを一般化する上で、機械学習に大きな関心を集めている。 しかし、ゲームダイナミクスはプレイヤー間の相互作用によって複雑になり、したがって最小化とは根本的に異なるため、アルゴリズム設計に新たな課題が生じる。 特に、ゲームダイナミクスの振動を減少させる能力により、負のモーメントが好ましいことが示されている。 それでも、負運動量の収束速度は単純な双線型ゲームでのみ確立された。 本稿では, 微分不等式を定式化することにより, 滑らかかつ強凸な強凸ミニマックスゲームに解析を拡張できる。 チェビシェフ多項式と運動量法を結合することにより、負の運動量によってゲームダイナミクスの収束が局所的に加速することを示した。 私たちの知る限りでは、これはこの設定において負の運動量に対する明示的な収束率を提供する \emph{first work} である。

関連論文リスト

• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  時間変化ゲームにおける楽観的勾配降下(OGD)の収束を特徴付ける。 我々のフレームワークは、ゼロサムゲームにおけるOGDの平衡ギャップに対して鋭い収束境界をもたらす。 また,静的ゲームにおける動的後悔の保証に関する新たな洞察も提供する。
  論文  参考訳（メタデータ） (2023-01-26T17:25:45Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。 ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。 本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
  論文  参考訳（メタデータ） (2022-11-29T05:16:41Z)
• Momentum Doesn't Change the Implicit Bias [36.301490759243876]
  我々は運動量に基づく最適化の暗黙バイアスを分析する。 モデルパラメータと最大マージン解の間のギャップを解析するためのツールとして,新しいリアプノフ関数を構築した。
  論文  参考訳（メタデータ） (2021-10-08T04:37:18Z)
• Online Multiobjective Minimax Optimization and Applications [14.699969822572308]
  本稿では,適応的な対戦相手が新しいゲームを導入する,シンプルだが汎用的なオンライン学習フレームワークを提案する。 学習者のゴールは、累積ベクトル値損失の最大座標を最小化することである。 対戦相手がまず行動を発表しなければならない設定と競合する簡単なアルゴリズムを提供する。 最適なアルゴリズムと境界を回復して、外部の後悔、内部の後悔、適応的な後悔、多集団の後悔、その後の後悔、睡眠専門家の設定における後悔の概念を最小化できます。
  論文  参考訳（メタデータ） (2021-08-09T06:52:08Z)
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum [8.515692980023948]
  コンベックス最適化のための反復アルゴリズムの構築と解析のレシピとして機能するモジュラーフレームワークを開発した。 我々は,いくつかの制約セットに対して,FrankWolf Nesterovアルゴリズムを新たに3つ導入した。 第2部では、ある問題に対するPolyak運動量のモジュラー解析を開発する。
  論文  参考訳（メタデータ） (2021-06-23T17:53:39Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Complex Momentum for Learning in Games [42.081050296353574]
  我々は、微分可能なゲームにおいて学習する運動量を伴う勾配降下を複素数値運動量を持つように一般化する。 我々は、複雑な値の運動量によってゲーム内の収束性が改善できることを実証する。 我々はまた、CIFAR-10のより良いスコアにBigGANを訓練するために使用する複素値アダム変種への実用的な一般化を示す。
  論文  参考訳（メタデータ） (2021-02-16T19:55:27Z)
• Chaos, Extremism and Optimism: Volume Analysis of Learning in Games [55.24050445142637]
  本稿では,ゼロサムにおける乗算重み更新 (MWU) と最適乗算重み更新 (OMWU) のボリューム解析と協調ゲームについて述べる。 我々は、OMWUが、その既知の収束挙動の代替的な理解を提供するために、ボリュームを契約していることを示します。 我々はまた、コーディネートゲームを調べる際に役割が逆になるという意味で、自由ランチ型の定理も証明する: OMWU は指数関数的に高速に体積を拡大するが、MWU は契約する。
  論文  参考訳（メタデータ） (2020-05-28T13:47:09Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)
• Accelerating Smooth Games by Manipulating Spectral Shapes [51.366219027745174]
  滑らかなゲームにおけるアクセラレーションを特徴付けるために行列反復理論を用いる。 スペクトル形状の変換として, 勾配法, 指数勾配法について述べる。 バイリニアゲームに最適なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-01-02T19:21:48Z)

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

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