Research map / Learning theory and algorithms / Sample complexity
A Theory of Optimistically Universal Online Learnability for General Concept Classes
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 which binary concept classes are optimistically universally online learnable, via infinite Littlestone and VCL trees, and gives matching conditions on data processes for realizable and agnostic settings.
Problem
Determining, for every binary concept class, which data processes admit strongly universally consistent online learning and whether an optimistically universal online learner exists under the realizable and agnostic settings.
Approach
Shows that absence of infinite VCL trees characterizes concept classes where all processes admit universal online learning, and absence of infinite Littlestone trees characterizes optimistic universal learnability; extends realizable learners to agnostic via expert aggregation (Squint) with non-uniform priors 1/(i(i+1)).
Key results
- A concept class has no infinite VCL tree iff every data process admits strongly universally consistent online learning under it.
- A concept class has no infinite Littlestone tree iff it is optimistically universally online learnable (realizable case).
- The same characterizations hold in the agnostic case, via reduction from agnostic to realizable learning with Squint over experts with prior 1/(i(i+1)).
Surprising findings
- Threshold functions on the reals have no infinite VCL tree (all processes learnable) yet have an infinite Littlestone tree, so they are not optimistically universally online learnable.
Limitations
- Results are for binary labels and the 0-1 loss only.
- Learning algorithms are existential/non-constructive in places (rely on measurability and winning strategies), with no practical implementation.
Experimental setup
Metrics: long-run average mistake rate (almost sure) regret
Builds on: Littlestone dimension characterization of online learnability universal learning rates (VCL tree) optimistically universal learning (Hanneke 2021) Squint expert aggregation weighted majority algorithm
Closest papers by meaning
- Computable universal online learning (NeurIPS 2025 · similarity 0.89)
- Online Classification with Predictions (NeurIPS 2024 · similarity 0.85)
- Regret–Oracle Complexity Tradeoffs in Agnostic Online Learning (NeurIPS 2026 · similarity 0.84)
- Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning (NeurIPS 2025 · similarity 0.83)
- Multiclass Transductive Online Learning (NeurIPS 2024 · similarity 0.83)
- Fast Co-Training under Weak Dependence via Stream-Based Active Learning (ICML 2024 · similarity 0.83)
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.