論文の概要: When is Momentum Extragradient Optimal? A Polynomial-Based Analysis

• arxiv url: http://arxiv.org/abs/2211.04659v3
• Date: Sat, 10 Feb 2024 23:26:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-14 01:27:48.322281
• Title: When is Momentum Extragradient Optimal? A Polynomial-Based Analysis
• Title（参考訳）: 運動量はいつ最適か? 多項式に基づく解析
• Authors: Junhyung Lyle Kim, Gauthier Gidel, Anastasios Kyrillidis, Fabian Pedregosa
• Abstract要約: ゲーム力学は、複素平面に散在するゲームベクトル場のヤコビアンの固有値に反映される複素相互作用を含む。 この複雑さは、双線型ゲームにおいても単純な方法が分岐し、一方、過次法は収束する。 我々は勾配に基づく解析を用いて,この手法がさらに加速収束を示す3つの異なるシナリオを同定する。
• 参考スコア（独自算出の注目度）: 35.327135714647824
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The extragradient method has gained popularity due to its robust convergence properties for differentiable games. Unlike single-objective optimization, game dynamics involve complex interactions reflected by the eigenvalues of the game vector field's Jacobian scattered across the complex plane. This complexity can cause the simple gradient method to diverge, even for bilinear games, while the extragradient method achieves convergence. Building on the recently proven accelerated convergence of the momentum extragradient method for bilinear games \citep{azizian2020accelerating}, we use a polynomial-based analysis to identify three distinct scenarios where this method exhibits further accelerated convergence. These scenarios encompass situations where the eigenvalues reside on the (positive) real line, lie on the real line alongside complex conjugates, or exist solely as complex conjugates. Furthermore, we derive the hyperparameters for each scenario that achieve the fastest convergence rate.
• Abstract（参考訳）: 微分可能ゲームに対する頑健な収束特性により、過次法が人気を博した。 単目的最適化とは異なり、ゲーム力学は複素平面に散在するゲームベクトル場の固有値に反映される複雑な相互作用を含む。 この複雑さは、単純勾配法が双線型ゲームであっても分岐し、一方、過次法は収束する。 最近証明された双線型ゲームにおける運動量外進法の加速収束を基盤として、多項式解析を用いて、この手法がさらなる加速収束を示す3つの異なるシナリオを同定する。 これらのシナリオは、固有値が(正の)実数直線上に存在する場合や、複素共役と並んで実数直線上にある場合、あるいは単に複素共役として存在する場合を含む。 さらに,高速な収束率を達成する各シナリオのハイパーパラメータを導出する。

関連論文リスト

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

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

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