論文の概要: Alternating Mirror Descent for Constrained Min-Max Games

• arxiv url: http://arxiv.org/abs/2206.04160v1
• Date: Wed, 8 Jun 2022 20:48:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-11 05:12:02.537389
• Title: Alternating Mirror Descent for Constrained Min-Max Games
• Title（参考訳）: 制約付きmin-maxゲームにおける交互ミラー降下
• Authors: Andre Wibisono and Molei Tao and Georgios Piliouras
• Abstract要約: 制約付き戦略空間を持つ2プレイヤー双線形ゼロサムゲームについて検討する。 我々は,各プレイヤーが交互に行動する交互ミラー降下アルゴリズムを,制約付き最適化のためのミラー降下アルゴリズムに従って解析する。
• 参考スコア（独自算出の注目度）: 44.46086335474311
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper we study two-player bilinear zero-sum games with constrained strategy spaces. An instance of natural occurrences of such constraints is when mixed strategies are used, which correspond to a probability simplex constraint. We propose and analyze the alternating mirror descent algorithm, in which each player takes turns to take action following the mirror descent algorithm for constrained optimization. We interpret alternating mirror descent as an alternating discretization of a skew-gradient flow in the dual space, and use tools from convex optimization and modified energy function to establish an $O(K^{-2/3})$ bound on its average regret after $K$ iterations. This quantitatively verifies the algorithm's better behavior than the simultaneous version of mirror descent algorithm, which is known to diverge and yields an $O(K^{-1/2})$ average regret bound. In the special case of an unconstrained setting, our results recover the behavior of alternating gradient descent algorithm for zero-sum games which was studied in (Bailey et al., COLT 2020).
• Abstract（参考訳）: 本稿では,制約付き戦略空間を持つ2プレイヤーバイリニアゼロサムゲームについて検討する。 そのような制約の自然発生の例は混合戦略が使われるときであり、これは確率単純性制約に対応する。 そこで本研究では,各プレイヤーが交互に交互に行動を起こす交互ミラー降下アルゴリズムを提案し,その解析を行った。 交互ミラー降下を双対空間内の歪勾配流れの交互な離散化と解釈し、凸最適化や修正エネルギー関数のツールを用いて、k$反復後に平均的な後悔に縛られた$o(k^{-2/3}) を確立する。 このことは、ミラー降下アルゴリズムの同時バージョンよりもアルゴリズムの優れた振る舞いを定量的に検証し、このアルゴリズムは分岐し、平均後悔境界の$O(K^{-1/2})を生じる。 制約のない設定の場合、この結果から、ゼロサムゲーム(Bailey et al., COLT 2020)の交互勾配降下アルゴリズムの挙動を復元する。

関連論文リスト

• Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimization [3.802030070947573]
  滑らかかつ非滑らかなMEROに対してゼロ階ミラー降下(ZO-SMD)アルゴリズムを提案する。 提案アルゴリズムは, 最適収束率$mathcalOleft (1/sqrttright)$と$mathcalOleft (1/sqrttright)$を, 滑らかかつ非滑らかなMEROの最適化誤差$で収束することが証明された。
  論文  参考訳（メタデータ） (2024-08-22T08:35:41Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Mirror Natural Evolution Strategies [10.495496415022064]
  我々は、ゼロ階探索で近似された一階情報と二階情報の両方を利用するゼロ階最適化理論に焦点をあてる。 我々は、textttMiNES の推定共分散行列が、目的関数のヘッセン行列の逆行列に収束することを示す。
  論文  参考訳（メタデータ） (2023-08-01T11:45:24Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。 ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
  論文  参考訳（メタデータ） (2023-06-03T17:05:13Z)
• Accelerated Single-Call Methods for Constrained Min-Max Optimization [5.266784779001398]
  既存の方法は、各イテレーションで2つのグラデーションコールか2つのプロジェクションを必要とする。 本稿では,RGOG(Optimistic Gradient)の変種が,非可換な min-max 収束率問題に富むことを示した。 私たちの収束率は、自然や自然のような標準の尺度に当てはまる。
  論文  参考訳（メタデータ） (2022-10-06T17:50:42Z)
• A gradient estimator via L1-randomization for online zero-order optimization with two point feedback [93.57603470949266]
  2つの関数評価とランダム化に基づく新しい勾配推定器を提案する。 ゼロ次オラクルの雑音に対する仮定は,ノイズのキャンセルと逆方向雑音の2種類について考察する。 我々は、問題の全てのパラメータに適応する、いつでも完全にデータ駆動のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-05-27T11:23:57Z)
• Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization under Infinite Noise Variance [17.199063087458907]
  我々は一様凸ミラーマップのクラスを用いてミラーDescentアルゴリズムの収束率を定量化する。 このアルゴリズムは明確な勾配クリッピングや正規化を必要としない。 我々は,1次オラクルのみを用いた他のアルゴリズムでは改善率を達成できないことを示す情報理論の下界を補完する。
  論文  参考訳（メタデータ） (2022-02-23T17:08:40Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Block majorization-minimization with diminishing radius for constrained nonconvex optimization [9.907540661545328]
  BMM(Block tensor regularization-minimization)は、ブロックごとの大きなサロゲートを最小化する非制約最適化のための単純な反復アルゴリズムである。 凸サロゲートを用いた場合、BMMは勾配$O(epsilon-2(logepsilon-1)2)$を生成可能であることを示す。
  論文  参考訳（メタデータ） (2020-12-07T07:53:09Z)

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

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