論文の概要: Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination

• arxiv url: http://arxiv.org/abs/2107.02237v1
• Date: Mon, 5 Jul 2021 19:20:34 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-07 13:54:12.163253
• Title: Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination
• Title（参考訳）: 効率的な1次文脈帯域:予測・割当・三角形判別
• Authors: Dylan J. Foster and Akshay Krishnamurthy
• Abstract要約: 統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。 1次保証は統計的およびオンライン学習において比較的よく理解されている。 三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
• 参考スコア（独自算出の注目度）: 82.52105963476703
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A recurring theme in statistical learning, online learning, and beyond is that faster convergence rates are possible for problems with low noise, often quantified by the performance of the best hypothesis; such results are known as first-order or small-loss guarantees. While first-order guarantees are relatively well understood in statistical and online learning, adapting to low noise in contextual bandits (and more broadly, decision making) presents major algorithmic challenges. In a COLT 2017 open problem, Agarwal, Krishnamurthy, Langford, Luo, and Schapire asked whether first-order guarantees are even possible for contextual bandits and -- if so -- whether they can be attained by efficient algorithms. We give a resolution to this question by providing an optimal and efficient reduction from contextual bandits to online regression with the logarithmic (or, cross-entropy) loss. Our algorithm is simple and practical, readily accommodates rich function classes, and requires no distributional assumptions beyond realizability. In a large-scale empirical evaluation, we find that our approach typically outperforms comparable non-first-order methods. On the technical side, we show that the logarithmic loss and an information-theoretic quantity called the triangular discrimination play a fundamental role in obtaining first-order guarantees, and we combine this observation with new refinements to the regression oracle reduction framework of Foster and Rakhlin. The use of triangular discrimination yields novel results even for the classical statistical learning model, and we anticipate that it will find broader use.
• Abstract（参考訳）: 統計的学習、オンライン学習、その他の分野における繰り返しのテーマは、ノイズの低い問題に対してより高速な収束率が可能であり、最良の仮説のパフォーマンスによって定量化されることが多い。 1次保証は統計的およびオンライン学習において比較的よく理解されているが、文脈的帯域幅(およびより広くは意思決定)の低ノイズに適応することは、アルゴリズム上の大きな課題をもたらす。 COLT 2017のオープンな問題において、Agarwal、Krishnamurthy、Langford、Luo、Schapireは、文脈的な盗賊に対して一階保証が可能であるかどうか、そして、もしそうなら、効率的なアルゴリズムで達成できるかどうかを尋ねた。 対数的(あるいはクロスエントロピー的)な損失を伴って、文脈的帯域幅からオンライン回帰への最適かつ効率的な削減を提供することにより、この問題に対する解決策を与える。 本アルゴリズムは単純かつ実用的であり,リッチな関数クラスに容易に対応でき,実現可能性以上の分布的仮定を必要としない。 大規模な経験的評価では、我々の手法は典型的には同等の非一階法より優れている。 技術面では、対数損失と三角弁別と呼ばれる情報理論的な量が、一階保証を得る上で基本的な役割を担っていることを示し、この観察と新たな改良とフォスターとラークリンの回帰オラクル削減フレームワークを組み合わせる。 三角形の識別は,古典的統計学習モデルにおいても新たな結果をもたらし,より広範な利用が期待できる。

関連論文リスト

• MaxMatch: Semi-Supervised Learning with Worst-Case Consistency [149.03760479533855]
  半教師付き学習(SSL)のための最悪ケース整合正則化手法を提案する。 本稿では,ラベル付きトレーニングデータとラベル付きトレーニングデータとを別々に比較した経験的損失項からなるSSLの一般化について述べる。 この境界によって動機づけられたSSLの目的は、元のラベルのないサンプルと、その複数の拡張版との最大の矛盾を最小限に抑えるものである。
  論文  参考訳（メタデータ） (2022-09-26T12:04:49Z)
• Interpolation-based Contrastive Learning for Few-Label Semi-Supervised Learning [43.51182049644767]
  半教師付き学習(SSL)は,ラベルが限定された強力なモデルを構築する上で,有効な手法であることが長年証明されてきた。 摂動サンプルを元のものと類似した予測を強制する正規化に基づく手法が注目されている。 本稿では,学習ネットワークの埋め込みを誘導し,サンプル間の線形変化を誘導する新たな対照的な損失を提案する。
  論文  参考訳（メタデータ） (2022-02-24T06:00:05Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  経験的リスク最小化(Empirical Risk Minimization, ERM)は、機械学習のワークホースであるが、適応的に収集されたデータを使用すると、そのモデルに依存しない保証が失敗する可能性がある。 本研究では,仮説クラス上での損失関数の平均値を最小限に抑えるため,適応的に収集したデータを用いた一般的な重み付きERMアルゴリズムについて検討する。 政策学習では、探索がゼロになるたびに既存の文献のオープンギャップを埋める率-最適後悔保証を提供する。
  論文  参考訳（メタデータ） (2021-06-03T09:50:13Z)
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs [48.44657553192801]
  我々は,適応的相手に対する盗聴フィードバックを用いたオンライン学習において,高い確率的後悔境界を得るための新しいアプローチを開発した。 我々のアプローチは、対数的に均質な自己協和障壁と強化されたフリードマンの不平等の助けを借りて、単純な学習率のスケジュールの増大に依存している。
  論文  参考訳（メタデータ） (2020-06-14T22:09:27Z)
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles [112.89548995091182]
  我々は、文脈的帯域幅からオンライン回帰への、初めての普遍的で最適な削減を提供する。 我々のアルゴリズムは、実現可能性以上の分布仮定は必要とせず、コンテキストが逆選択された場合でも機能する。
  論文  参考訳（メタデータ） (2020-02-12T11:33:46Z)
• Noise-tolerant, Reliable Active Classification with Comparison Queries [25.725730509014355]
  本研究では,大規模なデータプールにアクセス可能なアルゴリズムが,どのサンプルにラベルを付けるかを適応的に選択できる,アクティブラーニングのパラダイムについて検討する。 本研究では,有界(マサート)雑音に頑健な非同次線形分離器を学習するためのアルゴリズムを初めて提案する。
  論文  参考訳（メタデータ） (2020-01-15T19:00:00Z)

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

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