Research map / Bandits and online learning / Online convex optimization and games
Multiclass Transductive Online Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes minimax expected mistakes and agnostic regret for multiclass transductive online learning with unbounded label spaces via new Level-constrained Littlestone and Branching dimensions, yielding a Theta(1)/Theta(log T)/Theta(T) trichotomy.
Problem
Characterizing the optimal minimax expected number of mistakes (realizable) and expected regret (agnostic) in multiclass transductive online learning when the label space may be unbounded or even uncountable.
Approach
Introduces the Level-constrained Littlestone dimension (trees whose internal nodes at each level share one instance) and the Level-constrained Branching dimension; a new shattering notion enables a Halving-style learner whose mistake bound does not depend on the label set size, giving a trichotomy of rates even for unbounded labels.
Key results
- Trichotomy: minimax expected mistakes in the realizable setting is Theta(1), Theta(log T), or Theta(T), determined by the Level-constrained Branching and Littlestone dimensions, even for unbounded label spaces.
- Agnostic expected regret satisfies sqrt(T D(C)/8) <= R*(T,C) <= sqrt(T D(C)) log(eT/D(C)), matching up to a log T factor.
- Upper bounds improve on prior multiclass bounds by removing dependence on label set size.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Level-constrained Branching dimension to set the prediction rule | Realizable transductive online learning · Realizable setting | expected mistakes | Helped |
| Use the Level-constrained Littlestone dimension to bound regret | Agnostic transductive online learning · Agnostic setting | expected regret: \sqrt{\frac{T \, \operatorname{D}(\mathcal{C})}{8}} \leq \, \operatorname{R}^{\star}(T, \mathcal{C})\, \leq \sqrt{T \, \ | Helped |
| Use the Level-constrained Branching dimension to characterize realizable minimax rates | Multiclass transductive online learning with unbounded label spaces · Realizable setting | expected mistakes: \Theta(1), \Theta(\log T), or \Theta(T) | Helped |
| Remove dependence on the label set size from multiclass upper bounds | Multiclass transductive online learning · Realizable setting | expected mistakes | Helped |
Surprising findings
- The mistake bound for constant concept classes over unbounded label sets (e.g., constant functions over N) is at most one mistake, even though the projection size is infinite.
Limitations
- Gap of a log T factor between agnostic regret upper and lower bounds.
- Results are purely theoretical with no experiments.
- Bandit feedback, list learning, and real-valued regression extensions left open.
Experimental setup
Metrics: expected number of mistakes expected regret
Builds on: Littlestone dimension Halving algorithm Standard Optimal Algorithm Hanneke et al. 2024 multiclass transductive online learning
Closest papers by meaning
- Optimal Mistake Bounds for Transductive Online Learning (NeurIPS 2025 · similarity 0.93)
- A Trichotomy for List Transductive Online Learning (ICML 2025 · similarity 0.91)
- Online Learning of Neural Networks (NeurIPS 2025 · similarity 0.87)
- Active Learning of General Halfspaces: Label Queries vs Membership Queries (NeurIPS 2024 · similarity 0.85)
- Tight and Fast Bounds for Multi-Label Learning (ICML 2025 · similarity 0.85)
- Learning with Multiple Correct Answers - Regret Bounds under Different Feedback Models (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.