論文の概要: Forward Looking Best-Response Multiplicative Weights Update Methods
- arxiv url: http://arxiv.org/abs/2106.03579v1
- Date: Mon, 7 Jun 2021 13:03:33 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-09 06:11:47.583292
- Title: Forward Looking Best-Response Multiplicative Weights Update Methods
- Title（参考訳）: forward forward best-response multiplicative weights update methods
- Authors: Michail Fasoulakis, Evangelos Markakis, Yannis Pantazis, Constantinos
Varsos
- Abstract要約: エンフェルティプリケートウェイト更新法の新しい変種は、独自のエンフェルティプリケート平衡を持つエンフェルティプリケートサムゲームに対する最終点収束を保証する
以上の結果から,本アルゴリズムは従来手法と比較して,収束率と収縮領域の両方において有意な利得が得られることが明らかとなった。
- 参考スコア（独自算出の注目度）: 14.519198115835966
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose a novel variant of the \emph{multiplicative weights update method}
with forward-looking best-response strategies, that guarantees last-iterate
convergence for \emph{zero-sum games} with a unique \emph{Nash equilibrium}.
Particularly, we show that the proposed algorithm converges to an
$\eta^{1/\rho}$-approximate Nash equilibrium, with $\rho > 1$, by decreasing
the Kullback-Leibler divergence of each iterate by a rate of at least
$\Omega(\eta^{1+\frac{1}{\rho}})$, for sufficiently small learning rate $\eta$.
When our method enters a sufficiently small neighborhood of the solution, it
becomes a contraction and converges to the Nash equilibrium of the game.
Furthermore, we perform an experimental comparison with the recently proposed
optimistic variant of the multiplicative weights update method, by
\cite{Daskalakis2019LastIterateCZ}, which has also been proved to attain
last-iterate convergence. Our findings reveal that our algorithm offers
substantial gains both in terms of the convergence rate and the region of
contraction relative to the previous approach.
- Abstract（参考訳）: 本稿では,一意な \emph{nash equilibrium} を持つ \emph{zero-sum games} のラストイテレート収束を保証する,前方向きの最良の応答戦略を持つ \emph{multiplicative weights update method} の新たな変種を提案する。
特に,本アルゴリズムは,学習率の十分に小さい場合において,少なくとも$\omega(\eta^{1+\frac{1}{\rho}})$の率で各反復のkullback-leiblerの発散を減少させることにより,$\rho > 1$の$\eta^{1/\rho}$-approximate nash平衡に収束することを示す。
我々の方法が解の十分小さな近傍に入ると、それは収縮となり、ゲームのナッシュ平衡に収束する。
さらに,最近提案された乗算重み更新法の楽観的な変種である \cite{Daskalakis2019LastIterateCZ} との比較を行った。
その結果,本アルゴリズムは従来の手法と比較して収束率と収縮領域の両方において有意な利益をもたらすことがわかった。
関連論文リスト
- Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。
我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
論文 参考訳（メタデータ） (2024-06-04T15:23:29Z) - Stochastic Gradient Succeeds for Bandits [64.17904367852563]
エンフィスト確率勾配帯域幅アルゴリズムは,O (1/t)$レートで,エンフィグロブな最適ポリシに収束することを示す。
興味深いことに、勾配帯域アルゴリズムのグローバル収束は以前に確立されていない。
論文 参考訳（メタデータ） (2024-02-27T06:05:01Z) - Last-Iterate Convergence Properties of Regret-Matching Algorithms in
Games [72.43065138581589]
RM$+$ の様々な一般的な変種の最後の点収束特性について検討する。
本稿では, RM$+$の同時適用, RM$+$の交互化, RM$+$の予測, 最終項目収束保証の欠如など, 実用的バリエーションのいくつかを数値的に示す。
そして、スムーズな手法に基づく最近のアルゴリズムの変種は、最終点収束を楽しむことを証明した。
論文 参考訳（メタデータ） (2023-11-01T17:34:58Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - Local Convergence of Gradient Methods for Min-Max Games: Partial
Curvature Generically Suffices [0.5439020425819]
2つのプレイヤーゼロサム微分可能なゲームに対する勾配法の局所的ナッシュ平衡の収束について検討する。
偏曲のおかげで、円錐粒子法 -- 重みを最適化し、混合戦略をサポートする -- は、固定支持法よりも一般的に収束する。
論文 参考訳（メタデータ） (2023-05-26T21:43:56Z) - A globally convergent fast iterative shrinkage-thresholding algorithm
with a new momentum factor for single and multi-objective convex optimization [0.0]
提案手法はまた,任意の$(a,b)$に対して,大域収束率$O(1/k2)$を持つことを示す。
様々な$(a,b)$で数値結果を報告し、これらの選択のいくつかが古典的な運動量因子よりも良い結果をもたらすことを示す。
論文 参考訳（メタデータ） (2022-05-11T04:26:00Z) - Hessian Averaging in Stochastic Newton Methods Achieves Superlinear
Convergence [69.65563161962245]
ニュートン法を用いて,滑らかで強凸な目的関数を考える。
最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
論文 参考訳（メタデータ） (2022-04-20T07:14:21Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。
最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
論文 参考訳（メタデータ） (2021-01-31T16:17:56Z) - Almost sure convergence rates for Stochastic Gradient Descent and
Stochastic Heavy Ball [17.33867778750777]
一般近似問題に対する勾配降下法(SGD)と重球法(SHB)について検討した。
SGD の場合、凸と滑らかな設定において、イテレートの重み付き平均に対して、最初の最も確実な収束式を提供する。
論文 参考訳（メタデータ） (2020-06-14T11:12:05Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。