論文の概要: Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits

• arxiv url: http://arxiv.org/abs/2202.11795v1
• Date: Wed, 23 Feb 2022 21:34:20 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-26 08:33:40.247989
• Title: Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits
• Title（参考訳）: 低位選好バンディットの学習速度向上のための相関の活用
• Authors: Suprovat Ghoshal and Aadirupa Saha
• Abstract要約: 低ランクのような単純な相関構造を持つモデルがより高速な学習率をもたらすかどうかを考察する。 特に,新しいemphBlock-RankベースのRUMモデルを導入し,最もよい項目は$(epsilon,delta)$-PACで,$O(r epsilon-2 log(n/delta))$サンプルのみを学習可能であることを示した。
• 参考スコア（独自算出の注目度）: 21.70169149901781
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We introduce the \emph{Correlated Preference Bandits} problem with random utility-based choice models (RUMs), where the goal is to identify the best item from a given pool of $n$ items through online subsetwise preference feedback. We investigate whether models with a simple correlation structure, e.g. low rank, can result in faster learning rates. While we show that the problem can be impossible to solve for the general `low rank' choice models, faster learning rates can be attained assuming more structured item correlations. In particular, we introduce a new class of \emph{Block-Rank} based RUM model, where the best item is shown to be $(\epsilon,\delta)$-PAC learnable with only $O(r \epsilon^{-2} \log(n/\delta))$ samples. This improves on the standard sample complexity bound of $\tilde{O}(n\epsilon^{-2} \log(1/\delta))$ known for the usual learning algorithms which might not exploit the item-correlations ($r \ll n$). We complement the above sample complexity with a matching lower bound (up to logarithmic factors), justifying the tightness of our analysis. Surprisingly, we also show a lower bound of $\Omega(n\epsilon^{-2}\log(1/\delta))$ when the learner is forced to play just duels instead of larger subsetwise queries. Further, we extend the results to a more general `\emph{noisy Block-Rank}' model, which ensures robustness of our techniques. Overall, our results justify the advantage of playing subsetwise queries over pairwise preferences $(k=2)$, we show the latter provably fails to exploit correlation.
• Abstract（参考訳）: 本稿では,ランダムなユーティリティベース選択モデル (RUMs) を用いた「emph{Correlated Preference Bandits}」問題を紹介する。 低ランクのような単純な相関構造を持つモデルがより高速な学習率をもたらすかどうかを考察する。 一般の'低ランク'選択モデルでは問題を解くことは不可能であるが、より構造化された項目相関を仮定してより高速な学習率が得られる。 特に、新しいクラスである \emph{Block-Rank} ベースの RUM モデルを導入し、最良の項目は $(\epsilon,\delta)$-PAC で、サンプルは $O(r \epsilon^{-2} \log(n/\delta))$のみであることを示す。 これは通常の学習アルゴリズムで知られていて、アイテム相関(r \ll n$)を活用できないような、標準的なサンプル複雑性である$\tilde{o}(n\epsilon^{-2} \log(1/\delta))$の値で改善される。 上記のサンプルの複雑さを、(対数因子まで)下限の一致で補完し、解析の厳密さを正当化します。 驚くべきことに、学習者がより大きなサブセットワイドクエリの代わりにただデュエルをプレイせざるを得ない場合、$\Omega(n\epsilon^{-2}\log(1/\delta))$の低い境界を示す。 さらに、結果をより一般的な '\emph{noisy Block-Rank}' モデルに拡張することで、我々の手法の堅牢性を保証する。 全体として、我々の結果は、ペアワイズ選好の$(k=2)$に対してサブセットワイズクエリを再生する利点を正当化する。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• UniRank: Unimodal Bandit Algorithm for Online Ranking [0.0]
  We create a algorithm with a expected regret matching $O(fracLlog(L)Deltalog(T))$ with $2L$ player, $T$ and a least reward gap $Delta$。 いくつかの実験結果は、これらの理論的な結果が実際に裏付けられていることを示している。
  論文  参考訳（メタデータ） (2022-08-02T15:01:33Z)
• Unimodal Mono-Partite Matching in a Bandit Setting [0.0]
  We create a algorithm with a expected regret matching $O(fracLlog(L)Deltalog(T))$ with $2L$ player, $T$ and a least reward gap $Delta$。 いくつかの実験結果は、これらの理論的な結果が実際に裏付けられていることを示している。
  論文  参考訳（メタデータ） (2022-08-02T14:55:50Z)
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
  有限混合系における非パラメトリック分布の学習問題について検討する。 このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
  論文  参考訳（メタデータ） (2022-03-28T23:53:48Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。 これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
  論文  参考訳（メタデータ） (2022-02-03T18:18:28Z)
• Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
  我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-01T14:10:38Z)
• Structured Logconcave Sampling with a Restricted Gaussian Oracle [23.781520510778716]
  我々は,複数のロジコンケーブファミリーを高精度にサンプリングするアルゴリズムを提案する。 凸最適化における近点法にインスパイアされた縮小フレームワークをさらに発展させる。
  論文  参考訳（メタデータ） (2020-10-07T01:43:07Z)
• An Optimal Elimination Algorithm for Learning a Best Arm [37.18327505953403]
  古典的な問題である$(epsilon,delta)$-PAC学習をベストアームとみなす。 本稿では,$(epsilon,delta)$-PAC学習を最適なアームとして提案する。
  論文  参考訳（メタデータ） (2020-06-20T20:21:33Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

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

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