論文の概要: Local Convergence of Gradient Methods for Min-Max Games: Partial
Curvature Generically Suffices
- arxiv url: http://arxiv.org/abs/2305.17275v2
- Date: Tue, 7 Nov 2023 11:26:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-08 22:46:05.524147
- Title: Local Convergence of Gradient Methods for Min-Max Games: Partial
Curvature Generically Suffices
- Title（参考訳）: ミニマックスゲームにおけるグラディエント手法の局所収束性:部分曲率の一般性
- Authors: Guillaume Wang, L\'ena\"ic Chizat
- Abstract要約: 2つのプレイヤーゼロサム微分可能なゲームに対する勾配法の局所的ナッシュ平衡の収束について検討する。
偏曲のおかげで、円錐粒子法 -- 重みを最適化し、混合戦略をサポートする -- は、固定支持法よりも一般的に収束する。
- 参考スコア（独自算出の注目度）: 0.5439020425819
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the convergence to local Nash equilibria of gradient methods for
two-player zero-sum differentiable games. It is well-known that such dynamics
converge locally when $S \succ 0$ and may diverge when $S=0$, where $S\succeq
0$ is the symmetric part of the Jacobian at equilibrium that accounts for the
"potential" component of the game. We show that these dynamics also converge as
soon as $S$ is nonzero (partial curvature) and the eigenvectors of the
antisymmetric part $A$ are in general position with respect to the kernel of
$S$. We then study the convergence rates when $S \ll A$ and prove that they
typically depend on the average of the eigenvalues of $S$, instead of the
minimum as an analogy with minimization problems would suggest. To illustrate
our results, we consider the problem of computing mixed Nash equilibria of
continuous games. We show that, thanks to partial curvature, conic particle
methods -- which optimize over both weights and supports of the mixed
strategies -- generically converge faster than fixed-support methods. For
min-max games, it is thus beneficial to add degrees of freedom "with
curvature": this can be interpreted as yet another benefit of
over-parameterization.
- Abstract（参考訳）: 2つのプレイヤーゼロサム微分可能なゲームに対する勾配法の局所的ナッシュ平衡について検討する。
そのようなダイナミクスが局所的に収束するのは、$S \succ 0$ が$S=0$ のときであり、$S\succeq 0$ がゲームの「ポテンシャル」成分であるヤコビ行列の対称部分であるときである。
これらのダイナミクスは、$S$ が 0 でない(部分曲率)とすぐに収束し、反対称部分 $A$ の固有ベクトルは、一般に$S$ の核に関する位置にあることを示す。
次に、$s \ll a$の収束率を調べ、通常、最小化問題の類推が示唆する最小値ではなく、$s$の固有値の平均に依存することを証明します。
この結果を説明するために,連続ゲームにおける混合ナッシュ平衡の計算問題を考える。
部分曲率のおかげで、混合戦略の重みと支持の両方を最適化する円錐粒子法は、固定支持法よりも一般的に収束する。
min-maxゲームの場合、「曲率のある」自由度を加えることは有益であり、これはオーバーパラメータ化の別の利点と解釈できる。
関連論文リスト
- On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Doubly Regularized Entropic Wasserstein Barycenters [0.0]
本稿では, 正則性, 近似, 安定性, および(グリッドフリー)最適化特性を有する正則化ワッサーシュタインバリセンタの一般定式化について検討する。
論文 参考訳（メタデータ） (2023-03-21T13:42:43Z) - Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD [38.221784575853796]
この研究は、勾配を用いて潜在的に一定の滑らかさを持つ非アトー関数の1次定常点を求める問題を考える。
我々は、ノイズに一様境界を仮定することなく$mathcalO(fracmathrmpolylog(T)sigmatT)$収束率を証明できる技術を開発した。
論文 参考訳（メタデータ） (2023-02-13T18:13:36Z) - Forward Looking Best-Response Multiplicative Weights Update Methods [14.519198115835966]
エンフェルティプリケートウェイト更新法の新しい変種は、独自のエンフェルティプリケート平衡を持つエンフェルティプリケートサムゲームに対する最終点収束を保証する
以上の結果から,本アルゴリズムは従来手法と比較して,収束率と収縮領域の両方において有意な利得が得られることが明らかとなった。
論文 参考訳（メタデータ） (2021-06-07T13:03:33Z) - Estimating 2-Sinkhorn Divergence between Gaussian Processes from
Finite-Dimensional Marginals [4.416484585765028]
エルフガウス過程 (GP) 間の2-シンクホーンの偏差を有限次元の辺分布を用いて推定する収束性について検討する。
境界値が基底値に従ってサンプリングされた場合, ほぼ確実に発散の収束を示す。
論文 参考訳（メタデータ） (2021-02-05T16:17:55Z) - Gradient Descent-Ascent Provably Converges to Strict Local Minmax
Equilibria with a Finite Timescale Separation [11.091975655053547]
有限時間スケールの分離パラメータ $tau$ は、非プレイヤ、非コンケーブゼロサムゲームにおいて勾配降下度に比例することを示す。
タイムスケールコンピューティングがパフォーマンスに与える影響を実証的に示す。
論文 参考訳（メタデータ） (2020-09-30T17:51:28Z) - Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。
代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文 参考訳（メタデータ） (2020-06-12T10:21:40Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。