論文の概要: Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games

• arxiv url: http://arxiv.org/abs/2102.01646v1
• Date: Tue, 2 Feb 2021 18:02:01 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-03 19:40:44.463390
• Title: Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games
• Title（参考訳）: 簡易予測器によるオンライン学習と0/1ゲームにおけるMinimaxの組合せ評価
• Authors: Steve Hanneke, Roi Livni, and Shay Moran
• Abstract要約: 我々は、常に「単純な」予測器を用いて、ほぼ最適なミス/リグレット境界を達成する方法を示す。 この証明の技術的要素は、二元ゼロサムゲームに対する有名なミニマックス定理の一般化である。
• 参考スコア（独自算出の注目度）: 38.15628332832227
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Which classes can be learned properly in the online model? -- that is, by an algorithm that at each round uses a predictor from the concept class. While there are simple and natural cases where improper learning is necessary, it is natural to ask how complex must the improper predictors be in such cases. Can one always achieve nearly optimal mistake/regret bounds using "simple" predictors? In this work, we give a complete characterization of when this is possible, thus settling an open problem which has been studied since the pioneering works of Angluin (1987) and Littlestone (1988). More precisely, given any concept class C and any hypothesis class H, we provide nearly tight bounds (up to a log factor) on the optimal mistake bounds for online learning C using predictors from H. Our bound yields an exponential improvement over the previously best known bound by Chase and Freitag (2020). As applications, we give constructive proofs showing that (i) in the realizable setting, a near-optimal mistake bound (up to a constant factor) can be attained by a sparse majority-vote of proper predictors, and (ii) in the agnostic setting, a near-optimal regret bound (up to a log factor) can be attained by a randomized proper algorithm. A technical ingredient of our proof which may be of independent interest is a generalization of the celebrated Minimax Theorem (von Neumann, 1928) for binary zero-sum games. A simple game which fails to satisfy Minimax is "Guess the Larger Number", where each player picks a number and the larger number wins. The payoff matrix is infinite triangular. We show this is the only obstruction: if a game does not contain triangular submatrices of unbounded sizes then the Minimax Theorem holds. This generalizes von Neumann's Minimax Theorem by removing requirements of finiteness (or compactness), and captures precisely the games of interest in online learning.
• Abstract（参考訳）: どのクラスがオンラインモデルで適切に学習できるのか? つまり、各ラウンドで概念クラスから予測子を使用するアルゴリズムによって。 不適切な学習が必要な単純で自然なケースもあるが、不適切な予測器がどの程度複雑でなければならないのかを問うのは当然である。 単純な"予測器を使って、常にほぼ最適のミス/リグレット境界を達成できるのか? 本研究は,アングリン(1987年)とリトルストーン(1988年)の先駆的研究から研究されてきたオープンな課題を解決するために,これがいつ可能かを完全に特徴づける。 より正確には、任意の概念クラス C と任意の仮説クラス H を考えると、H からの予測器を用いてオンライン学習 C の最適誤差境界について、ほぼ厳しい境界 (ログファクタまで) を提供します。 アプリケーションとして、(i)実現可能な設定では、(定数まで)ほぼ最適の誤りバウンドが、適切な予測者のスパース多数投票によって達成可能であり、(ii)不可知な設定では、(ログ係数まで)ほぼ最適の後悔バウンドをランダム化された固有アルゴリズムで達成できることを示す構成的証明を与える。 独立性のある証明の技術的要素は、二元零サムゲームに対する有名なミニマックス定理(von Neumann, 1928)の一般化である。 Minimaxを満たすのに失敗する単純なゲームは、各プレーヤーが数字を選択し、より大きな数字が勝つ「大きな数字を誘導する」です。 ペイオフ行列は無限三角形である。 これが唯一の障害であることを示す:ゲームが非有界サイズの三角部分行列を含まないならば、ミニマックス定理は成立する。 これはフォン・ノイマンのミニマックス定理を有限性(あるいはコンパクト性)の要件を取り除いて一般化し、オンライン学習に関心のあるゲームを正確に捉えている。

関連論文リスト

• Barriers to Welfare Maximization with No-Regret Learning [68.66209476382213]
  我々は、ほぼ最適の$T$-sparse CCEの計算限界を低く証明する。 特に,最大傾斜角の不適応性は,時間内に非自明な間隔を達成できないことを示す。
  論文  参考訳（メタデータ） (2024-11-04T00:34:56Z)
• Expected Worst Case Regret via Stochastic Sequential Covering [14.834625066344582]
  我々は、既知のミニマックス後悔を一般化し包含する、予想される最悪のミニマックス後悔の概念を導入する。 そのようなミニマックスの後悔に対して、我々は上大域シーケンシャル被覆という新しい概念を通じて厳密な境界を確立する。 対数損失と一般に混合可能な損失に対する最小限の後悔に対する厳密な境界を確立することで,本手法の有効性を実証する。
  論文  参考訳（メタデータ） (2022-09-09T17:31:46Z)
• Strategizing against Learners in Bayesian Games [74.46970859427907]
  プレイヤーの1人である学習者が無学習の学習戦略を採用する2人プレイヤゲームについて検討した。 一般のベイズゲームでは,学習者と学習者の双方の報酬の支払いが,そのタイプに依存する可能性がある。
  論文  参考訳（メタデータ） (2022-05-17T18:10:25Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games [36.969021834291745]
  本稿では,仮説クラスの逐次的脂肪散乱次元の観点から,ほぼ最適誤差を導出する固有学習アルゴリズムを提案する。 この結果は、適切な学習者が準最適誤り境界を達成できるかどうかという疑問に答える。 実数値(回帰)設定では、最適誤り境界は不適切な学習者にさえ知られていなかった。
  論文  参考訳（メタデータ） (2021-11-17T05:24:21Z)
• Online Multiobjective Minimax Optimization and Applications [14.699969822572308]
  本稿では,適応的な対戦相手が新しいゲームを導入する,シンプルだが汎用的なオンライン学習フレームワークを提案する。 学習者のゴールは、累積ベクトル値損失の最大座標を最小化することである。 対戦相手がまず行動を発表しなければならない設定と競合する簡単なアルゴリズムを提供する。 最適なアルゴリズムと境界を回復して、外部の後悔、内部の後悔、適応的な後悔、多集団の後悔、その後の後悔、睡眠専門家の設定における後悔の概念を最小化できます。
  論文  参考訳（メタデータ） (2021-08-09T06:52:08Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Non-convex Min-Max Optimization: Applications, Challenges, and Recent Theoretical Advances [58.54078318403909]
  min-max問題(英: min-max problem)またはサドル点問題(英: saddle point problem)は、サムゲームにおいても研究されるクラス逆問題である。
  論文  参考訳（メタデータ） (2020-06-15T05:33:42Z)
• Solving Non-Convex Non-Differentiable Min-Max Games using Proximal Gradient Method [10.819408603463426]
  ミニマックスサドル点降下器は、機械の傾きと信号処理において幅広い用途に現れる。 単純な多段階LA-Ascentアルゴリズムは文献上の既存アルゴリズムよりも強いことを示す。
  論文  参考訳（メタデータ） (2020-03-18T08:38:34Z)
• A New Minimax Theorem for Randomized Algorithms [1.2284934135116514]
  新しいタイプのミニマックス定理を導入し、全てのバイアスレベルに一度に作用するハード分布の$mu$を提供する。 ランダム化クエリの複雑性,ランダム化通信の複雑性,近似度数,近似対数に対して有効であることを示す。 また、Impagliazzoのハードコアの改良版も証明した。
  論文  参考訳（メタデータ） (2020-02-25T11:46:08Z)

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

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