論文の概要: Optimal Mistake Bounds for Transductive Online Learning

• arxiv url: http://arxiv.org/abs/2512.12567v1
• Date: Sun, 14 Dec 2025 06:16:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-16 17:54:56.316844
• Title: Optimal Mistake Bounds for Transductive Online Learning
• Title（参考訳）: トランスダクティブオンライン学習における最適誤り境界
• Authors: Zachary Chase, Steve Hanneke, Shay Moran, Jonathan Shafer,
• Abstract要約: 帰納的設定では、ミスバウンドは少なくとも$(sqrtd)$であることを示す。 すべての$d$に対して、$O(sqrtd)$ が有界な帰納的誤りを持つリトルストーン次元 $d$ のクラスが存在する。
• 参考スコア（独自算出の注目度）: 46.15912397714354
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We resolve a 30-year-old open problem concerning the power of unlabeled data in online learning by tightly quantifying the gap between transductive and standard online learning. In the standard setting, the optimal mistake bound is characterized by the Littlestone dimension $d$ of the concept class $H$ (Littlestone 1987). We prove that in the transductive setting, the mistake bound is at least $Ω(\sqrt{d})$. This constitutes an exponential improvement over previous lower bounds of $Ω(\log\log d)$, $Ω(\sqrt{\log d})$, and $Ω(\log d)$, due respectively to Ben-David, Kushilevitz, and Mansour (1995, 1997) and Hanneke, Moran, and Shafer (2023). We also show that this lower bound is tight: for every $d$, there exists a class of Littlestone dimension $d$ with transductive mistake bound $O(\sqrt{d})$. Our upper bound also improves upon the best known upper bound of $(2/3)d$ from Ben-David, Kushilevitz, and Mansour (1997). These results establish a quadratic gap between transductive and standard online learning, thereby highlighting the benefit of advance access to the unlabeled instance sequence. This contrasts with the PAC setting, where transductive and standard learning exhibit similar sample complexities.
• Abstract（参考訳）: 我々は,トランスダクティブ学習と標準オンライン学習のギャップを厳格に定量化することにより,オンライン学習におけるラベルなしデータのパワーに関する30年前の未解決問題を解決する。 標準設定では、最適誤差境界は、概念クラス $H$ (Littlestone 1987) のリトルストーン次元 $d$ によって特徴づけられる。 帰納的設定では、誤り境界は少なくとも$Ω(\sqrt{d})$であることを証明する。 これは、Ben-David, Kushilevitz, Mansour (1995, 1997) と Hanneke, Moran, Shafer (2023) により、$Ω(\sqrt{\log d})$, $Ω(\sqrt{\log d})$, $Ω(\log d)$ に対する指数関数的な改善を構成する。 すべての$d$に対して、帰納的誤りを持つリトルストーン次元$d$のクラスが存在し、$O(\sqrt{d})$である。 我々の上界はまた、ベンダビッド、クシレヴィッツ、マンスール (1997) の最もよく知られた上界(2/3)d$も改善する。 これらの結果は、トランスダクティブと標準オンライン学習の2つのギャップを確立し、未ラベルのインスタンスシーケンスへの事前アクセスの利点を強調している。 これは、トランスダクティブと標準学習が類似したサンプル複雑さを示すPAC設定とは対照的である。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• On the Growth of Mistakes in Differentially Private Online Learning: A Lower Bound Perspective [8.104151304193216]
  我々は、差分的プライベート(DP)オンライン学習アルゴリズムに対して、より低いバウンダリを提供する。 我々の研究は、DP-オンライン学習の下位境界の設定に向けた最初の成果である。
  論文  参考訳（メタデータ） (2024-02-26T17:49:37Z)
• A Trichotomy for Transductive Online Learning [32.03948071550447]
  我々は,Ben-David, Kushilevitz, Mansour (1997) のオンライン学習環境における学習者の誤り数に関する,新たな上限と下限を提示する。 この設定は標準的なオンライン学習と似ているが、敵はゲームの開始時にラベル付けされる一連のインスタンスを修正し、このシーケンスは学習者に知られている。
  論文  参考訳（メタデータ） (2023-11-10T23:27:23Z)
• The Sample Complexity of Online Contract Design [120.9833763323407]
  オンライン環境での隠れアクションの主エージェント問題について検討する。 各ラウンドにおいて、主席は、各結果に基づいてエージェントへの支払いを指定する契約を投稿する。 エージェントは、自身のユーティリティを最大化する戦略的な行動選択を行うが、プリンシパルによって直接観察できない。
  論文  参考訳（メタデータ） (2022-11-10T17:59:42Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Littlestone Classes are Privately Online Learnable [28.04975353867202]
  プライバシー制約下でのオンライン分類の問題点を考察する。 この設定では、学習者はラベル付き例のストリームを$(x_t, y_t)$, for $1 leq t leq T$で順次観察し、各イテレーションで新しい例のラベルを予測するために使用される仮説$h_t$を返す。 学習者のパフォーマンスは、既知の仮説クラスである$mathcalH$に対する後悔によって測定される。
  論文  参考訳（メタデータ） (2021-06-25T09:08:33Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)

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

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