論文の概要: Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability

• arxiv url: http://arxiv.org/abs/2410.05117v1
• Date: Mon, 7 Oct 2024 15:14:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-02 00:08:45.330498
• Title: Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability
• Title（参考訳）: Assouad, Fano, Le Cam with Interaction: An Unification Lower Bound Framework and Characterization for Bandit Learnability (特集:ヒューマンコミュニケーション)
• Authors: Fan Chen, Dylan J. Foster, Yanjun Han, Jian Qian, Alexander Rakhlin, Yunbei Xu,
• Abstract要約: 我々は,統計的推定と対話的意思決定において,下位境界法のための統一的なフレームワークを開発する。 対話型意思決定のための新しい下位境界の複雑さを促進する新しい尺度である決定次元を導入する。
• 参考スコア（独自算出の注目度）: 71.82666334363174
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we develop a unified framework for lower bound methods in statistical estimation and interactive decision making. Classical lower bound techniques -- such as Fano's inequality, Le Cam's method, and Assouad's lemma -- have been central to the study of minimax risk in statistical estimation, yet they are insufficient for the analysis of methods that collect data in an interactive manner. The recent minimax lower bounds for interactive decision making via the Decision-Estimation Coefficient (DEC) appear to be genuinely different from the classical methods. We propose a unified view of these distinct methodologies through a general algorithmic lower bound method. We further introduce a novel complexity measure, decision dimension, which facilitates the derivation of new lower bounds for interactive decision making. In particular, decision dimension provides a characterization of bandit learnability for any structured bandit model class. Further, we characterize the sample complexity of learning convex model class up to a polynomial gap with the decision dimension, addressing the remaining gap between upper and lower bounds in Foster et al. (2021, 2023).
• Abstract（参考訳）: 本稿では,統計的推定と対話的意思決定における下界手法の統一的枠組みを開発する。 ファノの不等式、ル・カムの方法、アスーアの補題のような古典的な下界の手法は、統計的推定におけるミニマックスリスクの研究の中心であるが、データを対話的に収集する手法の分析には不十分である。 最近のDEC(Decision-Estimation Coefficient)による対話的意思決定の最小限境界は、古典的手法と真に異なるようである。 一般的なアルゴリズム的下界法を用いて,これらの異なる手法の統一的なビューを提案する。 さらに、インタラクティブな意思決定のための新しい下位境界の導出を容易にする、新しい複雑性尺度、決定次元を導入する。 特に、決定次元は任意の構造化バンディットモデルクラスに対するバンディット学習可能性の特徴を与える。 さらに,Foster et al (2021, 2023) における上界と下界の残りのギャップに対処し, 決定次元の多項式ギャップまで学習凸モデルクラスのサンプル複雑性を特徴付ける。

関連論文リスト

• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient [51.37720227675476]
  我々は、決定推定係数の新たな変種を導入し、それを用いて、3つの面における事前の作業を改善する新しい下界を導出する。 我々は同じ量でスケールした後悔について上界を与え、フォスター等における上界と下界の間のギャップの1つを除いて全てを閉じる。 この結果は、後悔のフレームワークとPACフレームワークの両方に適用され、我々が期待するいくつかの新しい分析とアルゴリズム設計技術を利用して、より広範な利用が期待できる。
  論文  参考訳（メタデータ） (2023-01-19T18:24:08Z)
• Model-Free Reinforcement Learning with the Decision-Estimation Coefficient [79.30248422988409]
  本稿では,汎用関数近似による構造化帯域と強化学習を包含する対話型意思決定の課題について考察する。 提案手法は,値関数近似を用いたモデル自由強化学習における残差を導出し,より一般的には有効かつ不可能な構造的結果を与える。
  論文  参考訳（メタデータ） (2022-11-25T17:29:40Z)
• On the Complexity of Adversarial Decision Making [101.14158787665252]
  決定推定係数は, 相手の意思決定に対する後悔度を低く抑えるのに必要であり, 十分であることを示す。 我々は、決定推定係数を他のよく知られた複雑性尺度の変種に結びつける新しい構造結果を提供する。
  論文  参考訳（メタデータ） (2022-06-27T06:20:37Z)
• The Statistical Complexity of Interactive Decision Making [126.04974881555094]
  複雑度尺度であるDecision-Estimation Coefficientは,サンプル効率のインタラクティブ学習に必要かつ十分であることが証明された。 統合アルゴリズム設計原則であるE2Dは、教師付き推定のための任意のアルゴリズムを、意思決定のためのオンラインアルゴリズムに変換する。
  論文  参考訳（メタデータ） (2021-12-27T02:53:44Z)
• Optimal learning of high-dimensional classification problems using deep neural networks [0.0]
  雑音のないトレーニングサンプルから分類関数を学習する際の問題について,決定境界が一定の規則性であることを前提として検討する。 局所バロン-正則な決定境界のクラスでは、最適推定率は本質的に基底次元とは独立である。
  論文  参考訳（メタデータ） (2021-12-23T14:15:10Z)
• Improved Algorithms for Agnostic Pool-based Active Classification [20.12178157010804]
  プールに依存しない環境でのバイナリ分類のためのアクティブラーニングを検討する。 我々のアルゴリズムは、画像分類データセットにおけるアートアクティブな学習アルゴリズムの状況よりも優れている。
  論文  参考訳（メタデータ） (2021-05-13T18:24:30Z)

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

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