論文の概要: Near Instance Optimal Model Selection for Pure Exploration Linear Bandits

• arxiv url: http://arxiv.org/abs/2109.05131v1
• Date: Fri, 10 Sep 2021 22:56:58 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-14 16:02:47.778343
• Title: Near Instance Optimal Model Selection for Pure Exploration Linear Bandits
• Title（参考訳）: 純探査線形バンディットのニアインスタンス最適モデル選択
• Authors: Yinglun Zhu, Julian Katz-Samuels, Robert Nowak
• Abstract要約: 純探索線形帯域設定におけるモデル選択問題について検討する。 私たちのゴールは、最小の仮説クラスのインスタンス依存の複雑性尺度に自動的に適応することです。 提案アルゴリズムは,実験設計に基づく新しい最適化問題を定義する。
• 参考スコア（独自算出の注目度）: 20.67688737534517
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The model selection problem in the pure exploration linear bandit setting is introduced and studied in both the fixed confidence and fixed budget settings. The model selection problem considers a nested sequence of hypothesis classes of increasing complexities. Our goal is to automatically adapt to the instance-dependent complexity measure of the smallest hypothesis class containing the true model, rather than suffering from the complexity measure related to the largest hypothesis class. We provide evidence showing that a standard doubling trick over dimension fails to achieve the optimal instance-dependent sample complexity. Our algorithms define a new optimization problem based on experimental design that leverages the geometry of the action set to efficiently identify a near-optimal hypothesis class. Our fixed budget algorithm uses a novel application of a selection-validation trick in bandits. This provides a new method for the understudied fixed budget setting in linear bandits (even without the added challenge of model selection). We further generalize the model selection problem to the misspecified regime, adapting our algorithms in both fixed confidence and fixed budget settings.
• Abstract（参考訳）: 純探査線形バンディット設定におけるモデル選択問題を導入し、固定信頼設定と固定予算設定の両方で検討する。 モデル選択問題は、増大する複雑性の仮説クラスのネスト列を考える。 我々の目標は、最大の仮説クラスに関連する複雑性測度に苦しむのではなく、真のモデルを含む最小の仮説クラスのインスタンス依存複雑性測度に自動的に適応することである。 標準的な2倍の次元上のトリックが最適なインスタンス依存サンプル複雑性を達成するのに失敗することを示す証拠を提供する。 提案アルゴリズムは,動作集合の幾何を利用して近似仮説クラスを効率的に同定する実験設計に基づく新しい最適化問題を定義する。 固定予算アルゴリズムは,バンディットにおける選択バリデーション手法の新たな適用法を用いる。 これは(モデル選択という追加の課題を伴わずとも)線形帯域における未検討の固定予算設定のための新しい方法を提供する。 さらに,モデル選択問題を不特定体制に一般化し,信頼度と予算の固定設定の両方にアルゴリズムを適用する。

関連論文リスト

• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  確率に基づく推論の原理を再検討し、確率比を用いて妥当な信頼シーケンスを構築することを提案する。 本手法は, 精度の高い問題に特に適している。 提案手法は,オンライン凸最適化への接続に光を当てることにより,推定器の最適シーケンスを確実に選択する方法を示す。
  論文  参考訳（メタデータ） (2023-11-08T00:10:21Z)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  モデル構築における最適特徴の選択に関する基礎的問題について検討する。 この問題は、greedyアルゴリズムの変種を使用しても、大規模なデータセットで計算的に困難である。 適応クエリモデルは,最近提案された非モジュラー関数に対する直交整合探索のより高速なパラダイムに拡張する。 提案アルゴリズムは、適応型クエリモデルにおいて指数関数的に高速な並列実行を実現する。
  論文  参考訳（メタデータ） (2022-02-28T12:26:47Z)
• Universal and data-adaptive algorithms for model selection in linear contextual bandits [52.47796554359261]
  モデル選択の最も単純な非自明な例を考える: 単純な多重武装バンディット問題と線形文脈バンディット問題とを区別する。 データ適応的な方法で探索する新しいアルゴリズムを導入し、$mathcalO(dalpha T1- alpha)$という形式の保証を提供する。 我々のアプローチは、いくつかの仮定の下で、ネストされた線形文脈包帯のモデル選択に拡張する。
  論文  参考訳（メタデータ） (2021-11-08T18:05:35Z)
• Towards Costless Model Selection in Contextual Bandits: A Bias-Variance Perspective [7.318831153179727]
  文脈的包帯設定における累積的後悔最小化のための同様の保証の実現可能性について検討した。 提案アルゴリズムは, 新たな不特定性テストに基づいており, モデル選択による報酬推定の利点を実証する。
  論文  参考訳（メタデータ） (2021-06-11T16:08:03Z)
• Pareto Optimal Model Selection in Linear Bandits [15.85873315624132]
  本研究では,学習者が最適仮説クラスの次元に適応しなければならない線形帯域設定におけるモデル選択問題について検討する。 本稿では,まず,固定アクション集合であっても,未知の内在次元$d_star$ への適応がコスト的に現れることを示す下限を定式化する。
  論文  参考訳（メタデータ） (2021-02-12T16:02:06Z)
• On Statistical Efficiency in Learning [37.08000833961712]
  モデルフィッティングとモデル複雑性のバランスをとるためのモデル選択の課題に対処する。 モデルの複雑さを順次拡大し、選択安定性を高め、コストを削減するオンラインアルゴリズムを提案します。 実験の結果, 提案手法は予測能力が高く, 計算コストが比較的低いことがわかった。
  論文  参考訳（メタデータ） (2020-12-24T16:08:29Z)
• Open Problem: Model Selection for Contextual Bandits [82.57505650713496]
  文脈的バンディット学習において同様の保証が可能かどうかを問う。 統計的学習において、モデル選択のためのアルゴリズムは、学習者が最良の仮説クラスの複雑さに適応できるようにする。
  論文  参考訳（メタデータ） (2020-06-19T03:00:01Z)
• Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
  部分ラベル学習(Partial-label Learning, PLL)は、典型的な弱教師付き学習問題であり、各トレーニングインスタンスには、真のラベルである候補ラベルのセットが設けられている。 既存のほとんどの手法は、特定の方法で解決しなければならない制約付き最適化として精巧に設計されており、計算複雑性をビッグデータにスケールアップするボトルネックにしている。 本稿では,モデルと最適化アルゴリズムの柔軟性を備えた分類器の新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-02-19T08:35:15Z)

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

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