Research map / Bandits and online learning / Online convex optimization and games
Online Classification with Predictions
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.
Gives online classification learners that use black-box access to a machine-learned Predictor of future examples, with mistake bounds that interpolate between transductive (offline) and worst-case online rates, and shows predictable streams make offline learnability sufficient for online learnability.
Problem
Online classification has worst-case impossibility results (Littlestone dimension), even for simple classes like thresholds; the paper asks how predictions of future examples can give beyond-worst-case guarantees on expected mistakes/regret.
Approach
Give the learner black-box access to an adaptive, consistent, lazy Predictor of future examples; restart a transductive (offline) learner each time the Predictor errs, and combine several such experts (parameterized by the number of restarts) with deterministic weighted majority so the mistake bound is never worse than the Littlestone-dimension worst case and degrades gracefully with predictor mis
Key results
- Expected mistake bound of the learner is at most 3*min(L(H), (M_P+1)M_B, 6((M_P+1) M̄_B(T/(M_P+1)+1)+log2 T)) + 5, so never worse than worst-case 3L(H)+5 (theoretical result).
- Lower bound: for thresholds there is a predictor with M_P = n such that any learner makes at least (n+1)/2 log2(T/(n+1)) expected mistakes, showing the product dependence is tight up to log factors.
- Corollary: predictable streams (M_P(T,Z)=o(T)) plus offline learnability (e.g., VC classes for binary labels) imply online learnability; for VC classes the mistake bound is O(VC(H)(M_P+1)log2(T/(M_P+1)) + log2 T).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| give the online learner access to a Predictor of future examples | Online classification with predictions · realizable online classification | expected mistakes: 3 \Biggl( \, \operatorname{L}(\mathcal{H}) \, \wedge \, (\operatorname{M}_{\mathcal{P}}(x_{1:T})+1)\operatorname{M}_{\ma | Helped |
| use accurate future-example predictions (zero Predictor mistakes) | Online classification with predictions · realizable online classification | expected mistakes: \operatorname{M}_{\mathcal{P}}(x_{1:T}) = 0 | Helped |
| use a Predictor whose mistakes are bounded on the stream class | Online classification with predictions · predictable example streams | expected mistakes: \operatorname{M}_{\mathcal{P}}(T, \mathcal{Z}) = o(T); \operatorname{M}_{\mathcal{B}}(T, \mathcal{H}) = o(T) | Helped |
| use a Predictor with n mistakes on the constructed threshold stream | Online classification with predictions · constructed realizable threshold streams | expected mistakes: \operatorname{M}_{\mathcal{P}}(x_{1:T}) = n; \frac{(n+1)}{2}\log_2\Bigl(\frac{T}{n+1}\Bigl) | Hurt |
Surprising findings
- Predictability of example streams can make classes that are not online learnable (e.g., thresholds) online learnable, with PAC/VC learnability sufficient under predictable streams.
Limitations
- Predictor quality is measured by mistake bounds on examples, which may be unrealistic for continuous input spaces.
- Results are stated for the realizable setting in main text; agnostic extension deferred to appendix.
- Mistake-bound product term (M_P+1)*M_B makes the bound loose when predictor errors are many.
Experimental setup
Metrics: expected mistakes expected regret
Baselines: Standard Optimal Algorithm (worst-case Littlestone learner) transductive online learner
Builds on: Standard Optimal Algorithm Deterministic Weighted Majority Algorithm transductive online learning smoothed online classification
Closest papers by meaning
- Learning-Augmented Algorithms with Explicit Predictors (NeurIPS 2024 · similarity 0.88)
- Information-theoretic Limits of Online Classification with Noisy Labels (NeurIPS 2024 · similarity 0.85)
- A Theory of Optimistically Universal Online Learnability for General Concept Classes (NeurIPS 2024 · similarity 0.85)
- Smoothed Online Classification can be Harder than Batch Classification (NeurIPS 2024 · similarity 0.85)
- Online Learning with Unknown Constraints (ICML 2025 · similarity 0.85)
- Bandit and Delayed Feedback in Online Structured Prediction (NeurIPS 2025 · similarity 0.85)
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.