論文の概要: A Parallelizable Approach for Characterizing NE in Zero-Sum Games After a Linear Number of Iterations of Gradient Descent

• arxiv url: http://arxiv.org/abs/2507.11366v1
• Date: Tue, 15 Jul 2025 14:39:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-16 19:46:03.155787
• Title: A Parallelizable Approach for Characterizing NE in Zero-Sum Games After a Linear Number of Iterations of Gradient Descent
• Title（参考訳）: グラディエントDescentのリニア数によるゼロサムゲームにおけるNE特性の並列化
• Authors: Taemin Kim, James P. Bailey,
• Abstract要約: 我々は,ゼロサムゲームに対するオンライン最適化手法について検討し,機械学習,経済学,その他多くの分野における対戦型学習の基本的問題である。 物理学におけるハミルトン力学に基づく新しい手法を提案し、勾配設定における交互降下の有限(線形)個の繰り返しにおけるNEの集合を特徴づけることができることを証明した。 NEの標準的な計算方法とは異なり、提案手法は並列化可能であり、アルゴリズムゲーム理論において、任意の学習率で動作する。
• 参考スコア（独自算出の注目度）: 1.1970409518725493
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study online optimization methods for zero-sum games, a fundamental problem in adversarial learning in machine learning, economics, and many other domains. Traditional methods approximate Nash equilibria (NE) using either regret-based methods (time-average convergence) or contraction-map-based methods (last-iterate convergence). We propose a new method based on Hamiltonian dynamics in physics and prove that it can characterize the set of NE in a finite (linear) number of iterations of alternating gradient descent in the unbounded setting, modulo degeneracy, a first in online optimization. Unlike standard methods for computing NE, our proposed approach can be parallelized and works with arbitrary learning rates, both firsts in algorithmic game theory. Experimentally, we support our results by showing our approach drastically outperforms standard methods.
• Abstract（参考訳）: 我々は,ゼロサムゲームに対するオンライン最適化手法について検討し,機械学習,経済学,その他多くの分野における対戦型学習の基本的問題である。 伝統的な手法は、後悔に基づく方法(平均収束)または収縮マップに基づく方法(ラスト収束)を用いてナッシュ平衡(NE)を近似する。 物理におけるハミルトン力学に基づく新しい手法を提案し、オンライン最適化において初めて、非有界なセッティング、モジュロ縮退における交互勾配降下の有限(線形)個の反復において、NEの集合を特徴付けることを証明した。 NEの標準的な計算方法とは異なり、提案手法は並列化可能であり、アルゴリズムゲーム理論において、任意の学習率で動作する。 実験により,本手法が標準手法を大幅に上回ることを示すことにより,提案手法の有効性を実証した。

関連論文リスト

• Symmetric Rank-One Quasi-Newton Methods for Deep Learning Using Cubic Regularization [0.5120567378386615]
  アダムやアダグラッドのような一階降下や他の一階変種は、ディープラーニングの分野で一般的に使われている。 しかし、これらの手法は曲率情報を活用しない。 準ニュートン法は、以前計算された低ヘッセン近似を再利用する。
  論文  参考訳（メタデータ） (2025-02-17T20:20:11Z)
• Achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ Regret in Average-Reward POMDPs with Known Observation Models [56.92178753201331]
  平均逆無限水平POMDPを未知の遷移モデルで扱う。 この障壁を克服する斬新でシンプルな推定器を提示する。
  論文  参考訳（メタデータ） (2025-01-30T22:29:41Z)
• Efficient Methods for Non-stationary Online Learning [61.63338724659592]
  本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 また、さらに強化された測度、すなわち「インターバル・ダイナミック・リピート」を研究し、ラウンド当たりの射影数を$mathcalO(log2 T)$から$$$$に減らした。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• Online Learning Under A Separable Stochastic Approximation Framework [20.26530917721778]
  分離可能な近似フレームワークを用いて,機械学習モデルのクラスに対するオンライン学習アルゴリズムを提案する。 提案アルゴリズムは,他の一般的な学習アルゴリズムと比較して,より堅牢でテスト性能が高いことを示す。
  論文  参考訳（メタデータ） (2023-05-12T13:53:03Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• A Discrete Variational Derivation of Accelerated Methods in Optimization [68.8204255655161]
  最適化のための異なる手法を導出できる変分法を導入する。 我々は1対1の対応において最適化手法の2つのファミリを導出する。 自律システムのシンプレクティシティの保存は、ここでは繊維のみに行われる。
  論文  参考訳（メタデータ） (2021-06-04T20:21:53Z)
• Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
  目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる 新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
  論文  参考訳（メタデータ） (2021-05-13T04:23:07Z)
• Meta-Regularization: An Approach to Adaptive Choice of the Learning Rate in Gradient Descent [20.47598828422897]
  第一次下降法における学習率の適応的選択のための新しいアプローチであるtextit-Meta-Regularizationを提案する。 本手法は,正規化項を追加して目的関数を修正し,共同処理パラメータをキャストする。
  論文  参考訳（メタデータ） (2021-04-12T13:13:34Z)
• SMG: A Shuffling Gradient-Based Method with Momentum [25.389545522794172]
  機械学習の最適化に広く使われている2つの先進的なアイデアを組み合わせる。 我々はシャッフルに基づく新しいモーメント技術を開発した。 私たちのテストでは、新しいアルゴリズムの性能が向上しました。
  論文  参考訳（メタデータ） (2020-11-24T04:12:35Z)
• Interpolation Technique to Speed Up Gradients Propagation in Neural ODEs [71.26657499537366]
  本稿では,ニューラルネットワークモデルにおける勾配の効率的な近似法を提案する。 我々は、分類、密度推定、推論近似タスクにおいて、ニューラルODEをトレーニングするリバースダイナミック手法と比較する。
  論文  参考訳（メタデータ） (2020-03-11T13:15:57Z)

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

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