Research map / Bandits and online learning / Online convex optimization and games
Optimal Mistake Bounds for 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.
Shows that transductive online mistake bounds are Omega(sqrt(d)) for Littlestone dimension d and constructs classes achieving O(sqrt(d)), closing an exponential gap and establishing a quadratic separation from standard online learning.
Problem
How much does advance access to the unlabeled instance sequence reduce the optimal number of mistakes in online learning, compared with the standard online setting characterized by Littlestone dimension? Prior bounds left a large gap between Omega(log d) and (2/3)d.
Approach
An adversary that greedily forces mistakes only when the version space is balanced, combined with a probabilistically constructed sparse-encoding hypothesis class whose off-path labels are biased to 0, yields a tight sqrt(d) lower and upper bound on transductive mistakes; the learner uses splitting experts, danger-zone minimization, and a transition to Halving.
Key results
- Lower bound: every class with Littlestone dimension d has transductive mistake bound at least sqrt(d)/10 (Theorem 6.1), improving the prior Omega(log d).
- Upper bound: for every d >= 43 there is a class with LD = d and transductive mistake bound at most 48*sqrt(d) (Theorem 8.1), improving the prior (2/3)d.
- Establishes a quadratic gap: transductive mistakes Theta(sqrt(d)) versus standard mistakes d for the constructed class.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| provide advance access to the unlabeled instance sequence | Online learning for classes with Littlestone dimension d · Transductive versus standard online learning | mistake bound: standard: d; transductive: Ω(√d) | Helped |
| use the constructed hypothesis class and transductive learner | Constructed class with Littlestone dimension d · Transductive online learning | mistake bound: Mtr(H, n) ≤48 ⋅ √d; Mstd(H, n) = min {n, d} | Helped |
| replace the previous lower bound with the Ω(√d) lower bound | Transductive online learning · Classes with Littlestone dimension d | mistake bound: Ω(log d) -> Ω(√d) | Helped |
Surprising findings
- The minimal Littlestone-dimension-d class is hard transductively, while a randomly sparsified variant is easy: the sqrt(d) upper bound depends on sparse encodings of off-path labels.
Limitations
- The upper-bound learner is not known to be computationally efficient and the constructed class has domain size about 2^d.
- Bounds are only up to constants; the exact asymptotic constant is open.
Experimental setup
Metrics: optimal transductive mistake bound
Baselines: Ben-David et al. 1997 lower bound Omega(sqrt(log d)) Hanneke et al. 2023 lower bound Omega(log d) Ben-David et al. 1997 upper bound (2/3)d
Builds on: Littlestone dimension Halving algorithm Ben-David et al. transductive online learning Hanneke-Moran-Shafer lower bound
Closest papers by meaning
- Multiclass Transductive Online Learning (NeurIPS 2024 · similarity 0.93)
- Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning (NeurIPS 2025 · similarity 0.89)
- A Trichotomy for List Transductive Online Learning (ICML 2025 · similarity 0.87)
- Online Learning of Neural Networks (NeurIPS 2025 · similarity 0.87)
- A New Concentration Inequality for Sampling Without Replacement and Its Application for Transductive Learning (ICML 2025 · similarity 0.84)
- Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings (NeurIPS 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.