論文の概要: Pareto Optimal Model Selection in Linear Bandits

• arxiv url: http://arxiv.org/abs/2102.06593v1
• Date: Fri, 12 Feb 2021 16:02:06 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-15 13:20:35.890192
• Title: Pareto Optimal Model Selection in Linear Bandits
• Title（参考訳）: 線形バンドにおけるパレート最適モデル選択
• Authors: Yinglun Zhu, Robert Nowak
• Abstract要約: 本研究では,学習者が最適仮説クラスの次元に適応しなければならない線形帯域設定におけるモデル選択問題について検討する。 本稿では,まず,固定アクション集合であっても,未知の内在次元$d_star$ への適応がコスト的に現れることを示す下限を定式化する。
• 参考スコア（独自算出の注目度）: 15.85873315624132
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a model selection problem in the linear bandit setting, where the learner must adapt to the dimension of the optimal hypothesis class on the fly and balance exploration and exploitation. More specifically, we assume a sequence of nested linear hypothesis classes with dimensions $d_1 < d_2 < \dots$, and the goal is to automatically adapt to the smallest hypothesis class that contains the true linear model. Although previous papers provide various guarantees for this model selection problem, the analysis therein either works in favorable cases when one can cheaply conduct statistical testing to locate the right hypothesis class or is based on the idea of "corralling" multiple base algorithms which often performs relatively poorly in practice. These works also mainly focus on upper bounding the regret. In this paper, we first establish a lower bound showing that, even with a fixed action set, adaptation to the unknown intrinsic dimension $d_\star$ comes at a cost: there is no algorithm that can achieve the regret bound $\widetilde{O}(\sqrt{d_\star T})$ simultaneously for all values of $d_\star$. We also bring new ideas, i.e., constructing virtual mixture-arms to effectively summarize useful information, into the model selection problem in linear bandits. Under a mild assumption on the action set, we design a Pareto optimal algorithm with guarantees matching the rate in the lower bound. Experimental results confirm our theoretical results and show advantages of our algorithm compared to prior work.
• Abstract（参考訳）: 線形バンディット設定におけるモデル選択問題について検討し, 学習者はフライ上の最適仮説クラスの次元に適応し, バランス探索と搾取を行なわなければならない。 より具体的には、次元 $d_1 < d_2 < \dots$ の入れ子付き線形仮説クラスの列を仮定し、真の線型モデルを含む最小の仮説クラスに自動的に適応することを目標とする。 以前の論文では、このモデル選択問題に対して様々な保証を提供しているが、その分析は、適切な仮説クラスを見つけるために統計的テストを安価に行うことができる場合や、実際には比較的不十分に実行されることが多い「相関」マルチベースアルゴリズムのアイデアに基づいている場合に有効である。 これらの作品は主に後悔の表層に焦点をあてている。 本稿では,固定された作用集合であっても,未知の内在次元 $d_\star$ への適応にはコストがかかることを示す下界を最初に確立する:$d_\star$ のすべての値に対して,後悔すべき有界 $\widetilde{O}(\sqrt{d_\star T})$ を同時に達成できるアルゴリズムはない。 また,リニアバンディットのモデル選択問題において,有用な情報を効果的に要約する仮想混合アームを構築するという新しいアイデアを提案する。 作用集合の軽度な仮定の下で、下界の速度に一致することを保証したパレート最適アルゴリズムを設計する。 実験結果が理論結果を確認し, 先行作業と比較して, アルゴリズムの優位性を示した。

関連論文リスト

• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Oracle Inequalities for Model Selection in Offline Reinforcement Learning [105.74139523696284]
  本稿では,値関数近似を用いたオフラインRLにおけるモデル選択の問題について検討する。 対数係数まで最小値の速度-最適不等式を実現するオフラインRLの最初のモデル選択アルゴリズムを提案する。 そこで本研究では,優れたモデルクラスを確実に選択できることを示す数値シミュレーションを行った。
  論文  参考訳（メタデータ） (2022-11-03T17:32:34Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Universal and data-adaptive algorithms for model selection in linear contextual bandits [52.47796554359261]
  モデル選択の最も単純な非自明な例を考える: 単純な多重武装バンディット問題と線形文脈バンディット問題とを区別する。 データ適応的な方法で探索する新しいアルゴリズムを導入し、$mathcalO(dalpha T1- alpha)$という形式の保証を提供する。 我々のアプローチは、いくつかの仮定の下で、ネストされた線形文脈包帯のモデル選択に拡張する。
  論文  参考訳（メタデータ） (2021-11-08T18:05:35Z)
• Near Instance Optimal Model Selection for Pure Exploration Linear Bandits [20.67688737534517]
  純探索線形帯域設定におけるモデル選択問題について検討する。 私たちのゴールは、最小の仮説クラスのインスタンス依存の複雑性尺度に自動的に適応することです。 提案アルゴリズムは,実験設計に基づく新しい最適化問題を定義する。
  論文  参考訳（メタデータ） (2021-09-10T22:56:58Z)
• Towards Costless Model Selection in Contextual Bandits: A Bias-Variance Perspective [7.318831153179727]
  文脈的包帯設定における累積的後悔最小化のための同様の保証の実現可能性について検討した。 提案アルゴリズムは, 新たな不特定性テストに基づいており, モデル選択による報酬推定の利点を実証する。
  論文  参考訳（メタデータ） (2021-06-11T16:08:03Z)
• Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably [23.372021234032363]
  サブサンプルサイズが大きくなると、推定誤差が過度に犠牲になることを示す。 私たちの知る限りでは、線形テキスト+確率モデルが保証される最初の研究です。
  論文  参考訳（メタデータ） (2020-10-19T07:15:38Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
  部分ラベル学習(Partial-label Learning, PLL)は、典型的な弱教師付き学習問題であり、各トレーニングインスタンスには、真のラベルである候補ラベルのセットが設けられている。 既存のほとんどの手法は、特定の方法で解決しなければならない制約付き最適化として精巧に設計されており、計算複雑性をビッグデータにスケールアップするボトルネックにしている。 本稿では,モデルと最適化アルゴリズムの柔軟性を備えた分類器の新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-02-19T08:35:15Z)

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

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