Research map / Bandits and online learning / Online convex optimization and games
A Trichotomy for List 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.
Proves a trichotomy for transductive online learning (mistakes are n, Θ(log n), or Θ(1) depending on VC and Littlestone dimensions), sharpens the Littlestone-class constant to Ω(log d), extends to multiclass and agnostic settings.
Problem
Characterize the minimal number of learner mistakes in transductive online learning, where the adversary commits to a fixed sequence of instances known to the learner in advance, as a function of sequence length n.
Approach
Shows the mistake growth in n takes exactly one of three rates (n, Θ(log n), Θ(1)) governed by VC and Littlestone dimensions; improves the lower bound for the constant case from Ω(sqrt(log d)) to Ω(log d) via an adaptive adversary, and extends the trichotomy to multiclass (Natarajan dimension) and gives tight-up-to-log agnostic regret in terms of VC dimension.
Key results
- Trichotomy: minimal mistakes equal n if VC is infinite, Θ(log n) if VC finite and Littlestone infinite, and Θ(1) if Littlestone finite.
- Lower bound on mistakes for Littlestone dimension d improved from Ω(sqrt(log d)) to Ω(log d) (min with log log n terms).
- Agnostic transductive regret for 0<VC<∞ is Ω(sqrt(VC·n)) and O(sqrt(VC·n·log n)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Strengthen the Littlestone-dimension lower bound from Ω(√log(d)) to Ω(log(d)) | Binary transductive online learning for classes with finite Littlestone dimension d · Transductive mistake bound | mistakes lower bound: from \OmegaOf{\sqrt{\log(\LD{\cH})}} to \OmegaOf{\log(\LD{\cH})} | Helped |
Surprising findings
- The DS dimension does not characterize multiclass transductive online learning, even for finite label sets: a class with DS dimension 1 forces n mistakes.
- For infinite label sets, a class with infinite Littlestone dimension can be learned with a single mistake.
Limitations
- Exponential gap remains between upper and lower bounds for the Θ(1) constant in Littlestone classes.
- Agnostic upper bound has an extra log n factor compared to the lower bound.
- Multiclass Θ(log n) case and infinite label set characterization remain open.
Experimental setup
Metrics: mistake bound regret
Baselines: Ben-David et al. 1997 lower bound Ω(sqrt(log d)) Halving algorithm O(VC log n)
Builds on: Ben-David, Kushilevitz and Mansour (1997) transductive online model Littlestone dimension Brukhim et al. (2022) multiclass PAC characterization
Closest papers by meaning
- Multiclass Transductive Online Learning (NeurIPS 2024 · similarity 0.91)
- Improved Sample Complexity for Multiclass PAC Learning (NeurIPS 2024 · similarity 0.87)
- Optimal Mistake Bounds for Transductive Online Learning (NeurIPS 2025 · similarity 0.87)
- Surprises in Proper Positive-Only Learning (NeurIPS 2026 · similarity 0.85)
- Transductive Learning is Compact (NeurIPS 2024 · similarity 0.85)
- Statistical Query Hardness of Multiclass Linear Classification with Random Classification Noise (ICML 2025 · 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.