論文の概要: Small-Gain Nash: Certified Contraction to Nash Equilibria in Differentiable Games

• arxiv url: http://arxiv.org/abs/2512.06791v2
• Date: Fri, 12 Dec 2025 17:29:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-15 13:50:28.990268
• Title: Small-Gain Nash: Certified Contraction to Nash Equilibria in Differentiable Games
• Title（参考訳）: スモールゲインナッシュ:差別ゲームにおけるナッシュ均衡の認定契約
• Authors: Vedansh Sharma,
• Abstract要約: 我々は,ブロック重み付き幾何学において,ブロック小利得条件であるスモールゲインナッシュ(SGN)を導入する。 SGNは局所曲率とクロスプレイヤのリプシッツ結合境界をトラクタブルな収縮証明書に変換する。 ユークリッドの単調性解析が収束の予測に失敗する二次ゲーム上で、この枠組みを検証する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Classical convergence guarantees for gradient-based learning in games require the pseudo-gradient to be (strongly) monotone in Euclidean geometry as shown by rosen(1965), a condition that often fails even in simple games with strong cross-player couplings. We introduce Small-Gain Nash (SGN), a block small-gain condition in a custom block-weighted geometry. SGN converts local curvature and cross-player Lipschitz coupling bounds into a tractable certificate of contraction. It constructs a weighted block metric in which the pseudo-gradient becomes strongly monotone on any region where these bounds hold, even when it is non-monotone in the Euclidean sense. The continuous flow is exponentially contracting in this designed geometry, and projected Euler and RK4 discretizations converge under explicit step-size bounds derived from the SGN margin and a local Lipschitz constant. Our analysis reveals a certified "timescale band", a non-asymptotic, metric-based certificate that plays a TTUR-like role: rather than forcing asymptotic timescale separation via vanishing, unequal step sizes, SGN identifies a finite band of relative metric weights for which a single-step-size dynamics is provably contractive. We validate the framework on quadratic games where Euclidean monotonicity analysis fails to predict convergence, but SGN successfully certifies it, and extend the construction to mirror/Fisher geometries for entropy-regularized policy gradient in Markov games. The result is an offline certification pipeline that estimates curvature, coupling, and Lipschitz parameters on compact regions, optimizes block weights to enlarge the SGN margin, and returns a structural, computable convergence certificate consisting of a metric, contraction rate, and safe step-sizes for non-monotone games.
• Abstract（参考訳）: ゲームにおける勾配に基づく学習の古典的な収束保証は、強いクロスプレイヤーカップリングを持つ単純なゲームでもしばしば失敗する条件であるローゼン(1965)で示されるように、ユークリッド幾何学において(強く)単調であることを要求する。 我々は,ブロック重み付き幾何学において,ブロック小利得条件であるスモールゲインナッシュ(SGN)を導入する。 SGNは局所曲率とクロスプレイヤのリプシッツ結合境界をトラクタブルな収縮証明書に変換する。 ユークリッドの意味では非単調である場合でも、これらの境界が保持する任意の領域において擬階数が強い単調となる重み付きブロック計量を構成する。 連続フローは、この設計された幾何学において指数関数的に収縮しており、ユーラーとRK4の離散化は、SGNマージンと局所リプシッツ定数から導かれる明示的なステップサイズ境界の下で収束する。 我々の分析では、TTURのような役割を果たす非漸近的・計量的証明である「タイムスケールバンド」が明らかにされている: 消失、不平等なステップサイズによる漸近的タイムスケールの分離を強制するのではなく、SGNはシングルステップサイズのダイナミクスが証明可能な、相対的計量量の有限バンドを同定する。 ユークリッドの単調性解析が収束を予測できない二次ゲーム上で、SGNはそれを証明し、マルコフゲームにおけるエントロピー規則化ポリシー勾配に対するミラー/フィッシャー幾何学へ拡張する。 結果は、コンパクトな領域における曲率、カップリング、リプシッツパラメータを推定し、ブロックウェイトを最適化してSGNマージンを拡大し、非モノトーンゲームに対するメートル法、収縮率、安全なステップサイズからなる構造的、計算可能な収束証明書を返却するオフライン認証パイプラインである。

関連論文リスト

• When Less is More: Approximating the Quantum Geometric Tensor with Block Structures [43.39839287869652]
  ブロック対角量子幾何テンソルを導入し、K-FACのようなブロック構造フィッシャー法に類似したネットワーク層で計量を分割する。 ハイゼンベルクの実験と、J_1$-$J$モデルのフラストレーションは、より高速な収束、低エネルギー、安定性の向上を示している。
  論文  参考訳（メタデータ） (2025-10-09T16:44:30Z)
• Learning Latent Graph Geometry via Fixed-Point Schrödinger-Type Activation: A Theoretical Study [1.1745324895296467]
  我々は、学習された潜在グラフ上の散逸的シュリンガー型ダイナミクスの定常状態として内部表現が進化するニューラルアーキテクチャの統一的理論的枠組みを開発する。 我々は、平衡の存在、一意性、滑らかな依存を証明し、力学がノルム保存ランダウ-リフシッツ流にブロッホ写像の下で等価であることを示す。 結果として得られるモデルクラスは、固定点 Schr"odinger 型のアクティベーションを通して潜在グラフ幾何学を学ぶためのコンパクトで幾何学的に解釈可能で解析的に抽出可能な基礎を提供する。
  論文  参考訳（メタデータ） (2025-07-27T00:35:15Z)
• Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent [25.846262685970164]
  本稿では,Burer-Monteiro因子化に基づく勾配型アルゴリズムの提案と解析を行う。 部分ユークリッド距離測定から点集合構成を再構成する。
  論文  参考訳（メタデータ） (2025-04-28T07:13:23Z)
• Exploiting hidden structures in non-convex games for convergence to Nash equilibrium [62.88214569402201]
  現代の機械学習アプリケーションは、非協調的なナッシュリリアとして定式化することができる。 決定論的環境と決定論的環境の両方に明確な収束保証を提供する。
  論文  参考訳（メタデータ） (2023-12-27T15:21:25Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  本稿では,テクスト幾何学的強単調ゲームに対する新たな収束結果を確立する。 我々のキーとなる結果は、RGDがテクスト幾何学的手法で最終定位線形収束を実現することを示しています。 全体として、ユークリッド設定を超えるゲームに対して、幾何学的に非依存な最終点収束解析を初めて提示する。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• Tight Second-Order Certificates for Randomized Smoothing [106.06908242424481]
  また、ガウス的ランダムな滑らか化のための普遍曲率的境界が存在することを示す。 この新たな証明書の正確性を証明することに加えて、SoS証明書は実現可能であり、したがって厳密であることを示す。
  論文  参考訳（メタデータ） (2020-10-20T18:03:45Z)

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

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