論文の概要: Apple Tasting: Combinatorial Dimensions and Minimax Rates
- arxiv url: http://arxiv.org/abs/2310.19064v2
- Date: Fri, 9 Feb 2024 18:35:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-12 20:21:54.081716
- Title: Apple Tasting: Combinatorial Dimensions and Minimax Rates
- Title(参考訳): appleの味覚:コンビネート次元とミニマックスレート
- Authors: Vinod Raman, Unique Subedi, Ananth Raman, Ambuj Tewari
- Abstract要約: エンファップル味覚フィードバックに基づくオンライン二項分類では、学習者は1を予測した場合のみ真のラベルを観察する。
実現可能な設定では、期待されるミスの回数が$Theta$または$Theta(T)$であることを示す。
- 参考スコア(独自算出の注目度): 18.054632903107546
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In online binary classification under \emph{apple tasting} feedback, the
learner only observes the true label if it predicts ``1". First studied by
\cite{helmbold2000apple}, we revisit this classical partial-feedback setting
and study online learnability from a combinatorial perspective. We show that
the Littlestone dimension continues to provide a tight quantitative
characterization of apple tasting in the agnostic setting, closing an open
question posed by \cite{helmbold2000apple}. In addition, we give a new
combinatorial parameter, called the Effective width, that tightly quantifies
the minimax expected mistakes in the realizable setting. As a corollary, we use
the Effective width to establish a \emph{trichotomy} of the minimax expected
number of mistakes in the realizable setting. In particular, we show that in
the realizable setting, the expected number of mistakes of any learner, under
apple tasting feedback, can be $\Theta(1), \Theta(\sqrt{T})$, or $\Theta(T)$.
This is in contrast to the full-information realizable setting where only
$\Theta(1)$ and $\Theta(T)$ are possible.
- Abstract(参考訳): emph{apple tasting} フィードバックに基づくオンラインバイナリ分類では、学習者は ``1" を予測した場合のみ真のラベルを観察する。
はじめはcite{helmbold2000apple} によって研究され、この古典的な部分フィードバック設定を再考し、組合せ論的観点からオンライン学習可能性を研究する。
リトルストーン次元は, リンゴの味付けの厳密な定量的評価を提供し続け, クエント{helmbold2000apple} によるオープンな質問を閉じていることを示す。
さらに,実現可能な設定における最小誤差を厳密に定量化する,エフェクト幅と呼ばれる新しい組合せパラメータを与える。
共役として、有効幅を用いて、実現可能な設定において、minimaxが期待する誤り数のemph{trichotomy}を確立する。
特に、実現可能な設定では、appleのテイスティングフィードバックの下で、すべての学習者の期待される誤り数は、$\theta(1)、 \theta(\sqrt{t})$、または$\theta(t)$である。
これは、$\Theta(1)$と$\Theta(T)$のみが可能であるようなフル情報実現可能な設定とは対照的である。
関連論文リスト
- Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit
Feedback and Unknown Transition [71.33787410075577]
線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。
我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-03-07T15:03:50Z) - Provably Efficient High-Dimensional Bandit Learning with Batched
Feedbacks [93.00280593719513]
本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。
具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。
我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
論文 参考訳(メタデータ) (2023-11-22T06:06:54Z) - A Trichotomy for Transductive Online Learning [32.03948071550447]
我々は,Ben-David, Kushilevitz, Mansour (1997) のオンライン学習環境における学習者の誤り数に関する,新たな上限と下限を提示する。
この設定は標準的なオンライン学習と似ているが、敵はゲームの開始時にラベル付けされる一連のインスタンスを修正し、このシーケンスは学習者に知られている。
論文 参考訳(メタデータ) (2023-11-10T23:27:23Z) - Towards the Fundamental Limits of Knowledge Transfer over Finite Domains [8.575522204707957]
3つの段階の特権情報によって転送が促進されることを示す。
第一段階では、ハードラベルを持つサンプルのみが知られており、最大極大推定器はミニマックスレート$sqrt|mathcal Smathcal A|/n$に達する。
第3のレベルはさらに、サンプル入力毎に$mathcal A$のソフトラベル(完全ロジット)を学生に提供するので、学生は$|mathcal S|/n$ free of $を楽しむことができる。
論文 参考訳(メタデータ) (2023-10-11T19:30:08Z) - Distribution-Independent Regression for Generalized Linear Models with
Oblivious Corruptions [49.69852011882769]
一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。
本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。
これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
論文 参考訳(メタデータ) (2023-09-20T21:41:59Z) - Self-Directed Linear Classification [50.659479930171585]
オンライン分類では、学習者は、誤りの総数を最小限に抑えるために、オンラインでラベルを予測することを目的としている。
そこで本研究では,予測順序の選択能力について検討し,最低次学習とランダム次学習の分離を初めて確立する。
論文 参考訳(メタデータ) (2023-08-06T15:38:44Z) - Online Learning with Set-Valued Feedback [20.291598040396302]
学習者は1つのラベルを予測するが、フィードバックとしてラベルのテキストセットを受け取る。
このモデルでは、学習者は、明らかにされた集合に含まれるラベルを出力しないようペナル化される。
単一ラベルフィードバックによるオンラインマルチクラス学習とは異なり、決定論的かつランダムなオンライン学習は、実現可能な環境ではテキストと同等であることを示す。
論文 参考訳(メタデータ) (2023-06-09T20:43:19Z) - High-dimensional Asymptotics of Feature Learning: How One Gradient Step
Improves the Representation [89.21686761957383]
2層ネットワークにおける第1層パラメータ $boldsymbolW$ の勾配降下ステップについて検討した。
我々の結果は、一つのステップでもランダムな特徴に対してかなりの優位性が得られることを示した。
論文 参考訳(メタデータ) (2022-05-03T12:09:59Z) - Bandit Phase Retrieval [45.12888201134656]
この問題におけるminimax累積後悔は$smashtilde Theta(d sqrtn)$であることを証明する。
また、minimax の単純な後悔は $smashtilde Theta(d / sqrtn)$ であり、これは適応アルゴリズムによってのみ達成可能であることを示す。
論文 参考訳(メタデータ) (2021-06-03T08:04:33Z) - Stronger Calibration Lower Bounds via Sidestepping [18.383889039268222]
予測器が1ビットあたり$T$のシーケンスを1つずつ観測するオンラインバイナリ予測設定について検討する。
予測器は、[0, 1]$の各$pに対して、予測器が確率$p$を予測する$n_p$ビットのうち、$p cdot n_p$に対して実際に$p cdot n_p$と等しい場合、よく校正される。
キャリブレーション誤差は$sum_p |m_p - p n_p|$と定義され、予測器が適切に校正されない範囲を定量化する。
論文 参考訳(メタデータ) (2020-12-07T05:29:28Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳(メタデータ) (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。