論文の概要: Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification

• arxiv url: http://arxiv.org/abs/2111.01479v1
• Date: Tue, 2 Nov 2021 10:27:17 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-03 14:17:36.979505
• Title: Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification
• Title（参考訳）: 固定信頼度線形トップm同定におけるミス種別対応
• Authors: Cl\'emence R\'eda (UP, INSERM), Andrea Tirinzoni (Scool, CNRS), R\'emy Degenne (Scool, CNRS)
• Abstract要約: 固定誤差率$delta$(固定信頼度Top-m識別)の下で最大の手段を持つmアームの識別問題について検討する。 この問題は、特に医療やレコメンデーションシステムにおける実践的な応用によって動機付けられている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of the identification of m arms with largest means under a fixed error rate $\delta$ (fixed-confidence Top-m identification), for misspecified linear bandit models. This problem is motivated by practical applications, especially in medicine and recommendation systems, where linear models are popular due to their simplicity and the existence of efficient algorithms, but in which data inevitably deviates from linearity. In this work, we first derive a tractable lower bound on the sample complexity of any $\delta$-correct algorithm for the general Top-m identification problem. We show that knowing the scale of the deviation from linearity is necessary to exploit the structure of the problem. We then describe the first algorithm for this setting, which is both practical and adapts to the amount of misspecification. We derive an upper bound to its sample complexity which confirms this adaptivity and that matches the lower bound when $\delta$ $\rightarrow$ 0. Finally, we evaluate our algorithm on both synthetic and real-world data, showing competitive performance with respect to existing baselines.
• Abstract（参考訳）: 我々は,不特定な線形バンディットモデルに対する固定誤差率$\delta$ (fixed-confidence top-m identification) の下で,最大の手段を持つmアームの同定の問題について検討した。 この問題は、特に医学やレコメンデーションシステムにおいて、その単純さと効率的なアルゴリズムの存在によって線形モデルが人気であるが、データが必然的に線形性から逸脱することによる。 本研究ではまず,一般的なTop-m識別問題に対する$\delta$-correctアルゴリズムのサンプリング複雑性に基づいて,トラクタブルな下界を導出する。 線形性からの逸脱の大きさを知ることは問題の構造を生かすために必要であることを示す。 次に,本設定における第1のアルゴリズムについて述べる。これは実用的であり,誤特定量に適応する。 この適応性を確認し、$\delta$$\rightarrow$ 0 のときの下位境界と一致するようなサンプル複雑性の上限を導出する。 最後に,本アルゴリズムを合成データと実世界データの両方で評価し,既存のベースラインに対する競合性能を示す。

関連論文リスト

• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。 提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
  論文  参考訳（メタデータ） (2024-10-22T10:19:27Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• An efficient, provably exact, practical algorithm for the 0-1 loss linear classification problem [4.418462313508022]
  インクリメンタルセル(ICE)は,0-1損失分類問題を正確に時間内に解くことができることを示す。 この長年の問題に対する、厳格に証明された実用的なアルゴリズムとしては、これが初めてだ。
  論文  参考訳（メタデータ） (2023-06-21T15:41:34Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• A Data-Driven Line Search Rule for Support Recovery in High-dimensional Data Analysis [5.180648702293017]
  適切なステップサイズを適応的に決定する新しい,効率的なデータ駆動行探索法を提案する。 線形回帰問題とロジスティック回帰問題における最先端アルゴリズムとの比較は,提案アルゴリズムの安定性,有効性,優越性を示す。
  論文  参考訳（メタデータ） (2021-11-21T12:18:18Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Universal and data-adaptive algorithms for model selection in linear contextual bandits [52.47796554359261]
  モデル選択の最も単純な非自明な例を考える: 単純な多重武装バンディット問題と線形文脈バンディット問題とを区別する。 データ適応的な方法で探索する新しいアルゴリズムを導入し、$mathcalO(dalpha T1- alpha)$という形式の保証を提供する。 我々のアプローチは、いくつかの仮定の下で、ネストされた線形文脈包帯のモデル選択に拡張する。
  論文  参考訳（メタデータ） (2021-11-08T18:05:35Z)
• Top-m identification for linear bandits [0.0]
  薬物再購入への適用を動機として, 線形バンディットモデルにおける最大平均のm $ge$ 1アームの同定に取り組むための最初のアルゴリズムを提案する。 これらのアルゴリズムはgap-indexフォーカスアルゴリズム(gifa)のジェネリックファミリーに属し、線形バンドイットにおけるトップm識別に導入する。
  論文  参考訳（メタデータ） (2021-03-18T08:04:45Z)
• Semi-Supervised Learning with Meta-Gradient [123.26748223837802]
  半教師付き学習における簡単なメタ学習アルゴリズムを提案する。 その結果,提案アルゴリズムは最先端の手法に対して良好に動作することがわかった。
  論文  参考訳（メタデータ） (2020-07-08T08:48:56Z)
• Differentiable Linear Bandit Algorithm [6.849358422233866]
  アッパー信頼境界は、線形多腕バンディット問題の最も一般的な方法である。 勾配上昇による信頼度を学習できる勾配推定器を導入する。 提案アルゴリズムは,腕の特徴の次元を$d$で,信頼度を$hatbeta$で学習したサイズを$tildemathcalO(hatbetasqrtdT)$上限とする。
  論文  参考訳（メタデータ） (2020-06-04T16:43:55Z)
• Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
  データフィッティングと正規化のための大域的スムーズなロバスト推定器に基づくロバストな非剛性登録のための定式化を提案する。 本稿では,L-BFGS を用いた最小二乗問題の解法に,各繰り返しを減らし,最大化最小化アルゴリズムを適用した。
  論文  参考訳（メタデータ） (2020-04-09T01:45:05Z)

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

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