論文の概要: 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)$のみが可能であるようなフル情報実現可能な設定とは対照的である。

関連論文リスト

• Annotation Efficiency: Identifying Hard Samples via Blocked Sparse Linear Bandits [23.329605738829947]
  本稿では,ラベル・スカース・セッティングにおいて,少数のアノテーションラウンドしか持たない専門家によるアノテートデータポイントの問題について考察する。 そこで本稿では,データポイントの注釈付けの難しさに対する信頼性の高いフィードバックを,基礎的な真理ラベルに加えて専門家に提案する。
  論文  参考訳（メタデータ） (2024-10-26T01:42:03Z)
• Deterministic Apple Tasting [2.4554686192257424]
  我々は、初めて広く適用可能な決定論的リンゴテイスティング学習者を提供する。 すべてのクラス $mathcalH$ は簡単、困難、あるいは学習不能でなければならない、という三分法を証明します。 我々の上限は、リンゴの味付けフィードバックに関する専門家のアドバイスから学ぶための決定論的アルゴリズムに基づいている。
  論文  参考訳（メタデータ） (2024-10-14T11:54:46Z)
• The Real Price of Bandit Information in Multiclass Classification [73.17969992976501]
  バンディットフィードバックを用いた複数クラス分類の古典的問題を再考する。 我々は, 後悔すべき$smashwidetildeO(|H|+sqrtT)$を保証する新しい帯域分類アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-16T12:11:09Z)
• 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)
• Self-Directed Linear Classification [50.659479930171585]
  オンライン分類では、学習者は、誤りの総数を最小限に抑えるために、オンラインでラベルを予測することを目的としている。 そこで本研究では,予測順序の選択能力について検討し,最低次学習とランダム次学習の分離を初めて確立する。
  論文  参考訳（メタデータ） (2023-08-06T15:38:44Z)
• 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)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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