論文の概要: Online Multiobjective Minimax Optimization and Applications

• arxiv url: http://arxiv.org/abs/2108.03837v1
• Date: Mon, 9 Aug 2021 06:52:08 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-10 14:58:21.850904
• Title: Online Multiobjective Minimax Optimization and Applications
• Title（参考訳）: オンラインマルチ目的ミニマックス最適化とその応用
• Authors: Georgy Noarov, Mallesh Pai, Aaron Roth
• Abstract要約: 本稿では,適応的な対戦相手が新しいゲームを導入する,シンプルだが汎用的なオンライン学習フレームワークを提案する。 学習者のゴールは、累積ベクトル値損失の最大座標を最小化することである。 対戦相手がまず行動を発表しなければならない設定と競合する簡単なアルゴリズムを提供する。 最適なアルゴリズムと境界を回復して、外部の後悔、内部の後悔、適応的な後悔、多集団の後悔、その後の後悔、睡眠専門家の設定における後悔の概念を最小化できます。
• 参考スコア（独自算出の注目度）: 14.699969822572308
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a simple but general online learning framework, in which at every round, an adaptive adversary introduces a new game, consisting of an action space for the learner, an action space for the adversary, and a vector valued objective function that is convex-concave in every coordinate. The learner and the adversary then play in this game. The learner's goal is to play so as to minimize the maximum coordinate of the cumulative vector-valued loss. The resulting one-shot game is not convex-concave, and so the minimax theorem does not apply. Nevertheless, we give a simple algorithm that can compete with the setting in which the adversary must announce their action first, with optimally diminishing regret. We demonstrate the power of our simple framework by using it to derive optimal bounds and algorithms across a variety of domains. This includes no regret learning: we can recover optimal algorithms and bounds for minimizing external regret, internal regret, adaptive regret, multigroup regret, subsequence regret, and a notion of regret in the sleeping experts setting. Next, we use it to derive a variant of Blackwell's Approachability Theorem, which we term "Fast Polytope Approachability". Finally, we are able to recover recently derived algorithms and bounds for online adversarial multicalibration and related notions (mean-conditioned moment multicalibration, and prediction interval multivalidity).
• Abstract（参考訳）: 学習者の行動空間,学習者の行動空間,対向者に対する行動空間,各座標で凸対となるベクトル値の目的関数からなる新しいゲームを導入する,単純だが汎用的なオンライン学習フレームワークを提案する。 学習者と敵対者はこのゲームでプレーする。 学習者の目標は、累積ベクトル値損失の最大座標を最小にするために遊ぶことである。 結果として得られるワンショットゲームは凸凸ではないので、ミニマックス定理は適用されない。 それにもかかわらず、敵がまず行動を発表しなければならない設定と競合する単純なアルゴリズムを、最適に後悔を減らし、与える。 様々な領域にまたがる最適境界とアルゴリズムを導出することにより、我々のシンプルなフレームワークのパワーを実証する。 最適なアルゴリズムと境界を回復して、外部の後悔、内部の後悔、適応的な後悔、多集団の後悔、その後の後悔、睡眠専門家の設定における後悔の概念を最小化できます。 次に、ブラックウェルのアプローチ可能性理論の変種を導出し、これを「Fast Polytope Approachability」と呼ぶ。 最後に,オンラインの対数多重校正と関連する概念(平均条件付きモーメント多重校正,予測区間多重校正)について,最近導出したアルゴリズムと境界を復元する。

関連論文リスト

• Regret Minimization and Convergence to Equilibria in General-sum Markov Games [57.568118148036376]
  汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。 我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
  論文  参考訳（メタデータ） (2022-07-28T16:27:59Z)
• Efficient Adaptive Regret Minimization [35.121567896321885]
  オンライン凸最適化では、プレイヤーは繰り返しゲーム全体に対して固定されたコンパレータに対する後悔を最小限にすることを目的としている。 既存の適応的後悔アルゴリズムは計算的なペナルティに悩まされる - 典型的には、ゲームの繰り返し回数で対数的に増加する乗法的因子の順序である。 本稿では,この計算ペナルティをゲーム繰り返し回数で2倍に対数的に減らし,最適な適応的再帰限界を最小限に抑える方法を示す。
  論文  参考訳（メタデータ） (2022-07-01T19:43:11Z)
• No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
  固定ゼロサムゲームにおける繰り返しプレイからの学習は、ゲーム理論とオンライン学習における古典的な問題である。 提案手法は,3つの性能基準の下で,良好な保証を同時に享受できる1つのパラメータフリーアルゴリズムである。 本アルゴリズムは,ある特性を満たすブラックボックスベースラーナー群に対するメタアルゴリズムを用いた2層構造に基づく。
  論文  参考訳（メタデータ） (2022-01-30T06:10:04Z)
• No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization [20.718016474717196]
  我々は,非regretゲームダイナミクスを用いた凸最適化問題を解くためのアルゴリズムフレームワークを開発した。 これらの戦略の一般的な選択は、いわゆるno-regret学習アルゴリズムである。 コンベックス最適化のための古典的な一階法の多くは、我々のフレームワークの特別なケースとして解釈できることを示す。
  論文  参考訳（メタデータ） (2021-11-22T16:10:18Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Model-Free Online Learning in Unknown Sequential Decision Making Problems and Games [114.90723492840499]
  大規模な2人プレイのゼロサム情報ゲームでは、反事実後悔最小化(cfr)の現代的な拡張がnash均衡を計算するための実用的な技術である。 私たちは、戦略空間がエージェントに知られていないオンライン学習設定を形式化します。 エージェントが逆の環境に直面しても、その設定に高い確率で$O(T3/4)$後悔を達成する効率的なアルゴリズムを提供します。
  論文  参考訳（メタデータ） (2021-03-08T04:03:24Z)
• Faster Game Solving via Predictive Blackwell Approachability: Connecting Regret Matching and Mirror Descent [119.5481797273995]
  FTRL (Follow-the-regularized-leader) とオンラインミラー降下 (OMD) は、オンライン凸最適化における最も一般的な後悔の最小化手法である。 RMとRM+はFTRLとOMDをそれぞれ実行し、ブラックウェルのアプローチ性ゲームにおいて、ハーフスペースを常に強制的に選択するアルゴリズムであることを示す。 18の共通ゼロサムワイドフォームベンチマークゲームを対象とした実験では,予測的RM+と反ファクト的後悔の最小化が,最速のアルゴリズムよりもはるかに高速に収束することを示した。
  論文  参考訳（メタデータ） (2020-07-28T16:49:55Z)
• Stochastic Regret Minimization in Extensive-Form Games [109.43344748069933]
  Monte-Carlo counterfactual regret minimization (MCCFR) は、完全な木には大きすぎるシーケンシャルゲームを解くための最先端のアルゴリズムである。 後悔の最小化手法を開発するための新しい枠組みを開発する。 MCCFRよりも優れた方法がいくつかある3つのゲームについて広範な実験を行った。
  論文  参考訳（メタデータ） (2020-02-19T23:05:41Z)

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

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