論文の概要: Partial Feedback Online Learning

• arxiv url: http://arxiv.org/abs/2601.21462v1
• Date: Thu, 29 Jan 2026 09:39:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-30 16:22:49.706053
• Title: Partial Feedback Online Learning
• Title（参考訳）: オンライン学習の部分的フィードバック
• Authors: Shihao Shao, Cong Fang, Zhouchen Lin, Dacheng Tao,
• Abstract要約: 本研究では,各インスタンスが正しいラベルのセットを付与する部分フィードバックオンライン学習について検討するが,学習者は1ラウンドあたりの正しいラベルを1つだけ観察する。 決定論的およびランダムな学習者に対して,ミニマックス後悔のほぼ完全な特徴を与える。
• 参考スコア（独自算出の注目度）: 88.27143767009376
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study partial-feedback online learning, where each instance admits a set of correct labels, but the learner only observes one correct label per round; any prediction within the correct set is counted as correct. This model captures settings such as language generation, where multiple responses may be valid but data provide only a single reference. We give a near-complete characterization of minimax regret for both deterministic and randomized learners in the set-realizable regime, i.e., in the regime where sublinear regret is generally attainable. For deterministic learners, we introduce the Partial-Feedback Littlestone dimension (PFLdim) and show it precisely governs learnability and minimax regret; technically, PFLdim cannot be defined via the standard version space, requiring a new collection version space viewpoint and an auxiliary dimension used only in the proof. We further develop the Partial-Feedback Measure Shattering dimension (PMSdim) to obtain tight bounds for randomized learners. We identify broad conditions ensuring inseparability between deterministic and randomized learnability (e.g., finite Helly number or nested-inclusion label structure), and extend the argument to set-valued online learning, resolving an open question of Raman et al. [2024b]. Finally, we show a sharp separation from weaker realistic and agnostic variants: outside set realizability, the problem can become information-theoretically intractable, with linear regret possible even for $|H|=2$. This highlights the need for fundamentally new, noise-sensitive complexity measures to meaningfully characterize learnability beyond set realizability.
• Abstract（参考訳）: 本研究では,各インスタンスが正しいラベルのセットを付与する部分フィードバックオンライン学習について検討するが,学習者は1ラウンドあたりの正しいラベルを1つだけ観察し,正しいセット内の予測は正しいとみなす。 このモデルは、複数のレスポンスが有効だがデータが単一の参照のみを提供する言語生成のような設定をキャプチャする。 我々は,決定論的かつランダムな学習者に対して,決定論的かつランダムな学習者,すなわち,下線的後悔が一般的に達成可能な体制において,ミニマックス後悔のほぼ完全な特徴を与える。 決定論的学習者に対しては、PFLdim(Partial-Feedback Littlestone dimension)を導入し、学習可能性とミニマックスの後悔を正確に制御することを示す。 さらに、ランダムな学習者に対して厳密な境界を求めるために、部分フィードバック測度シェータリング次元(PMSdim)を更に発展させる。 決定論的学習性とランダムな学習性(例えば、有限ヘルリー数やネストインクルージョンラベル構造)の分離性を保証する広い条件を特定し、その議論をオンライン学習に拡張し、Raman et al[2024b]のオープンな疑問を解決した。 最後に、より現実的で非現実的な変種から鋭い分離を示す:外集合実現可能性、問題は情報理論的に難解となり、|H|=2$ であっても線形後悔が可能である。 これは、設定された実現可能性を超えて学習可能性を有意義に特徴付けるために、根本的に新しい、ノイズに敏感な複雑さ尺度の必要性を強調している。

関連論文リスト

• Proper Learnability and the Role of Unlabeled Data [10.168670899305232]
  適切な学習可能性が論理的に決定不可能な問題、すなわちZFC公理に依存しない問題が存在することを示す。 そこで本研究では,PACモデルにおいて,適切な学習可能性の特性を損なう不確実性に関するすべての結果を示す。
  論文  参考訳（メタデータ） (2025-02-14T18:41:53Z)
• Probably Approximately Precision and Recall Learning [60.00180898830079]
  機械学習における重要な課題は、一方的なフィードバックの頻度である。 本稿では,確率的近似(PAC)フレームワークを導入し,各入力をラベルの集合にマッピングする仮説を定めている。 我々は、正のデータのみから学習する新しいアルゴリズムを開発し、実現可能な場合において最適なサンプル複雑性を実現する。
  論文  参考訳（メタデータ） (2024-11-20T04:21:07Z)
• Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds [59.875550175217874]
  本稿では,オンラインとオフラインのRL設定において,モデルベース強化学習方式が強い後悔とサンプル境界を実現することを示す。 我々のアルゴリズムは単純で、かなり標準的であり、実際にRLの文献で広く研究されている。
  論文  参考訳（メタデータ） (2024-08-16T19:52:53Z)
• Online Learning with Set-Valued Feedback [18.054632903107546]
  学習者は1つのラベルを予測するが、フィードバックとしてラベルのテキストセットを受け取る。 単一ラベルフィードバックによるオンラインマルチクラス学習とは異なり、決定論的かつランダムなオンライン学習は、実現可能な設定においてもテキストと同等であることを示す。
  論文  参考訳（メタデータ） (2023-06-09T20:43:19Z)
• Online Selective Classification with Limited Feedback [82.68009460301585]
  オンライン学習モデルにおいて、予測者がインスタンスの分類を控える可能性のある選択的分類について検討する。 私たちが考慮している設定の健全な2つの側面は、データが不可避である可能性があるため、データは不可避である可能性があるということです。 smash$tildeO(T1-mu)$ over abstention against Adaptive adversaries. smash$tildeO(T1-mu)$ incurring smash$tildeO(T1-mu)$ over abstention。
  論文  参考訳（メタデータ） (2021-10-27T08:00:53Z)

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

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