論文の概要: Open Problem: Tight Bounds for Kernelized Multi-Armed Bandits with Bernoulli Rewards
- arxiv url: http://arxiv.org/abs/2407.06321v1
- Date: Mon, 8 Jul 2024 18:38:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-10 22:03:20.943913
- Title: Open Problem: Tight Bounds for Kernelized Multi-Armed Bandits with Bernoulli Rewards
- Title（参考訳）: オープンイシュー:Bernolli Rewards氏によるカーネル化されたマルチアーマッドバンドのタイトバウンド
- Authors: Marco Mussi, Simone Drago, Alberto Maria Metelli,
- Abstract要約: 我々は、Kernelized Bandits (KB) を、関数 $f : MathcalX rightarrow [0,1]$ を再生カーネル空間 (RKHS) $mathcalH_k$ に属するように最適化する。
- 参考スコア（独自算出の注目度）: 18.662468634576218
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider Kernelized Bandits (KBs) to optimize a function $f : \mathcal{X} \rightarrow [0,1]$ belonging to the Reproducing Kernel Hilbert Space (RKHS) $\mathcal{H}_k$. Mainstream works on kernelized bandits focus on a subgaussian noise model in which observations of the form $f(\mathbf{x}_t)+\epsilon_t$, being $\epsilon_t$ a subgaussian noise, are available (Chowdhury and Gopalan, 2017). Differently, we focus on the case in which we observe realizations $y_t \sim \text{Ber}(f(\mathbf{x}_t))$ sampled from a Bernoulli distribution with parameter $f(\mathbf{x}_t)$. While the Bernoulli model has been investigated successfully in multi-armed bandits (Garivier and Capp\'e, 2011), logistic bandits (Faury et al., 2022), bandits in metric spaces (Magureanu et al., 2014), it remains an open question whether tight results can be obtained for KBs. This paper aims to draw the attention of the online learning community to this open problem.
- Abstract（参考訳）: 我々は、Kernelized Bandits (KBs) を、再生Kernel Hilbert Space (RKHS) $\mathcal{H}_k$に属する関数 $f : \mathcal{X} \rightarrow [0,1]$ を最適化すると考えている。
メインストリームは、サブガウス雑音モデルに焦点を当て、$f(\mathbf{x}_t)+\epsilon_t$、$\epsilon_t$ a subガウス雑音が利用できる(Chowdhury and Gopalan, 2017)。
異なることに、パラメータ $f(\mathbf{x}_t)$ のベルヌーイ分布からサンプリングされた実数化が $y_t \sim \text{Ber}(f(\mathbf{x}_t))$ となる場合に焦点を当てる。
ベルヌーイモデルは、多武装の包帯(Garivier and Capp\'e, 2011)、ロジスティックな包帯(Faury et al , 2022)、計量空間の包帯(Magureanu et al , 2014)でうまく研究されているが、KBに対して厳密な結果が得られるかどうかについては未解決のままである。
本稿では,このオープンな問題に対して,オンライン学習コミュニティの注意を惹きつけることを目的とする。
関連論文リスト
- Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - On the Optimality of Misspecified Kernel Ridge Regression [13.995944403996566]
我々は、$mathcalH$がソボレフ RKHS であるとき、KRR が任意の$sin (0,1)$に対して最小値であることを示す。
論文 参考訳（メタデータ） (2023-05-12T04:12:12Z) - SQ Lower Bounds for Learning Single Neurons with Massart Noise [40.1662767099183]
マスアートノイズの存在下で単一ニューロンを学習するPAC。
我々は、任意の定数係数内で最適な誤差を近似できる効率的なSQアルゴリズムが存在しないことを証明した。
論文 参考訳（メタデータ） (2022-10-18T15:58:00Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - Multimeasurement Generative Models [7.502947376736449]
我々は、密度$p_X$ in $mathbbRd$を未知分布からサンプリングする問題を学習とサンプリングの問題を$p_mathbfY$ in $mathbbRMd$とする。
論文 参考訳（メタデータ） (2021-12-18T02:11:36Z) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Unique Games hardness of Quantum Max-Cut, and a conjectured
vector-valued Borell's inequality [6.621324975749854]
関数 $f:mathbbRn の -1, 1$ への雑音安定性は $f(boldsymbolx) cdot f(boldsymboly)$ の期待値であることを示す。
我々は $langle f(boldsymbolx), f(boldsymboly)rangle$ の期待値は、関数 $f(x) = x_leq k / Vert x_leq k / によって最小化されると予想する。
論文 参考訳（メタデータ） (2021-11-01T20:45:42Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - Efficient inference of interventional distributions [13.31079561447385]
有限個の観測値から因果ベイズネットワーク内の干渉分布を効率的に推定する問題を考察する。
我々は、$mathbfY$ が任意の集合であるとき、グラフ同型問題を含む統計的ゼロ知識を持つ全ての問題が効率的なランダム化アルゴリズムを持っていなければ、$varepsilon$-close である分布の評価器を$P_bf x(mathbfY)$ に出力する効率的なアルゴリズムは存在しないことを示した。
論文 参考訳（メタデータ） (2021-07-25T02:40:01Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。