論文の概要: Extragradient with Positive Momentum is Optimal for Games with Cross-Shaped Jacobian Spectrum

• arxiv url: http://arxiv.org/abs/2211.04659v1
• Date: Wed, 9 Nov 2022 03:22:30 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-10 16:28:34.336770
• Title: Extragradient with Positive Momentum is Optimal for Games with Cross-Shaped Jacobian Spectrum
• Title（参考訳）: 正のモメンタムによる外勾配は、クロスシェープジャコビアンスペクトルを持つゲームに最適である
• Authors: Junhyung Lyle Kim, Gauthier Gidel, Anastasios Kyrillidis, Fabian Pedregosa
• Abstract要約: n$-プレイヤ微分可能ゲームでは、ベクトル場のヤコビアンの固有値は複素平面上で分布する。 本研究では、複素平面上のジャコビアンスペクトルを持つゲームに対して、運動量と運動量の極小化に基づく解析を行う。
• 参考スコア（独自算出の注目度）: 33.429248621522596
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The extragradient method has recently gained increasing attention, due to its convergence behavior on smooth games. In $n$-player differentiable games, the eigenvalues of the Jacobian of the vector field are distributed on the complex plane, exhibiting more convoluted dynamics compared to classical (i.e., single player) minimization. In this work, we take a polynomial-based analysis of the extragradient with momentum for optimizing games with \emph{cross-shaped} Jacobian spectrum on the complex plane. We show two results. First, based on the hyperparameter setup, the extragradient with momentum exhibits three different modes of convergence: when the eigenvalues are distributed $i)$ on the real line, $ii)$ both on the real line along with complex conjugates, and $iii)$ only as complex conjugates. Then, we focus on the case $ii)$, i.e., when the eigenvalues of the Jacobian have \emph{cross-shaped} structure, as observed in training generative adversarial networks. For this problem class, we derive the optimal hyperparameters of the momentum extragradient method, and show that it achieves an accelerated convergence rate.
• Abstract（参考訳）: 滑らかなゲーム上での収束挙動が原因で,近年,段階的な手法が注目されている。 n$-player の微分可能ゲームでは、ベクトル場のヤコビアンの固有値が複素平面上に分布し、古典的(すなわち単一プレイヤー)の最小化と比較してより畳み込みのあるダイナミクスを示す。 本研究では,複素平面上の\emph{cross-shaped} ジャコビアンスペクトルを持つゲームを最適化するための運動量を持つ超次数の多項式に基づく解析を行う。 結果は2つあります まず、ハイパーパラメータのセットアップに基づいて、運動量を持つ退化度は3つの異なる収束モードを示す: 固有値が実数直線上で分散されたとき、$ii)$ は実数直線上で複素共役と共に分布し、$iii)$ は複素共役としてのみ成立する。 そして、生成逆数ネットワークのトレーニングで見られるように、ヤコビアンの固有値が \emph{cross-shaped} 構造を持つ場合、$$$(ii)$に焦点をあてる。 この問題のクラスでは、運動量外勾配法の最適ハイパーパラメータを導出し、それが加速収束率を達成することを示す。

関連論文リスト

• Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence [20.766358513158206]
  双対性ギャップの観点から、大域収束率を$O(min1/k,sqrtd/k1.25)$とする。 これらの結果は、外勾配法よりも準ニュートン法の証明可能な利点を示す最初の大域収束結果である。
  論文  参考訳（メタデータ） (2024-10-03T16:08:16Z)
• Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
  我々は、アダムがより現実的な条件下で、$O(epsilon-4)$勾配複雑性で$epsilon$-定常点に収束することを示している。 また、Adamの分散還元版を$O(epsilon-3)$の加速勾配複雑性で提案する。
  論文  参考訳（メタデータ） (2023-04-27T06:27:37Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• On Asymptotic Linear Convergence of Projected Gradient Descent for Constrained Least Squares [22.851500417035947]
  この写本は、制約最小二乗の文脈における射影勾配降下の解析のための統一的な枠組みを提示する。 本稿では,PGDの収束解析のレシピを提示し,このレシピを4つの基本的な問題に応用して実証する。
  論文  参考訳（メタデータ） (2021-12-22T09:49:51Z)
• A Discrete Variational Derivation of Accelerated Methods in Optimization [68.8204255655161]
  最適化のための異なる手法を導出できる変分法を導入する。 我々は1対1の対応において最適化手法の2つのファミリを導出する。 自律システムのシンプレクティシティの保存は、ここでは繊維のみに行われる。
  論文  参考訳（メタデータ） (2021-06-04T20:21:53Z)
• Better Regularization for Sequential Decision Spaces: Fast Convergence Rates for Nash, Correlated, and Team Equilibria [121.36609493711292]
  大規模2プレーヤワイドフォームゲームの計算平衡問題に対する反復的な一階法の適用について検討する。 正則化器を用いて一階法をインスタンス化することにより、相関平衡と元アンティー座標のチーム平衡を計算するための最初の加速一階法を開発する。
  論文  参考訳（メタデータ） (2021-05-27T06:10:24Z)
• AMITE: A Novel Polynomial Expansion for Analyzing Neural Network Nonlinearities [1.8761314918771685]
  多項式展開はニューラルネットワークの非線形性の解析において重要である。 既存のアプローチは古典的なテイラー法とチェビシェフ法にまたがる。 これらの性質をすべて拡張した一貫した方法を提供するアプローチは存在しない。
  論文  参考訳（メタデータ） (2020-07-13T07:58:47Z)
• Stochastic spectral embedding [0.0]
  確率スペクトル埋め込み(SSE)に基づく新しい逐次適応サロゲートモデリング法を提案する。 本手法は,複雑性と入力次元の異なるモデルの集合上で,最先端のスパースカオス展開に対して,どのように好意的に比較されるかを示す。
  論文  参考訳（メタデータ） (2020-04-09T11:00:07Z)
• Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives [97.16266088683061]
  この論文は、運動量に基づく最適化アルゴリズムにおいてシンプレクティックな離散化スキームが重要であることを厳格に証明している。 これは加速収束を示すアルゴリズムの特性を提供する。
  論文  参考訳（メタデータ） (2020-02-28T00:32:47Z)
• Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimization [25.680334940504405]
  本稿では,制約問題に対する運動量を持つ非滑らかな過渡法の割合の収束性を確立する。 問題としては、制約のないケースが、最先端技術よりも弱い仮定の下でどのように分析できるかを示す。
  論文  参考訳（メタデータ） (2020-02-13T12:10:17Z)

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

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