Research map / Learning theory and algorithms / Prediction and decision losses
Computable universal 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 universal online learnability does not imply computable universal online learnability for hypothesis classes on N, gives exact characterizations of computable agnostic and proper learning for RER classes, and separates these notions.
Problem
When can universal online binary classification (finitely many mistakes against a mind-changing realizable adversary) be implemented by a computable program, and how do agnostic and proper variants behave in this computable regime?
Approach
Introduces computability constraints into universal online learning: the learner must be a total or almost-total computable program. Shows the closure of an RER class can contain uncomputable functions, yielding separations from the non-computable setting, and characterizes computable agnostic learning via an RER superset of the closure.
Key results
- Proposition: there exists a DR class that is universally online learnable but not computably universally online learnable.
- Theorem: a class is computably agnostically learnable iff its closure is contained in an RER class, and for RER classes computable universal online learnability is equivalent to this condition.
- Theorem: a RER class is computably universally online learnable by a proper learner iff its closure is RER; a separate RER class is computably learnable but has no computable proper learner.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| require the learner to be computable | universal online learning · RER hypothesis classes | learnability | Hurt |
| require computable agnostic learning instead of computable realizable learning | universal online learning · arbitrary hypothesis classes | agnostic learnability | Hurt |
| restrict the hypothesis class to RER classes | computable universal online learning · RER hypothesis classes | equivalence of realizable and agnostic learnability | Helped |
| require the learner to be proper | computable universal online learning · RER hypothesis classes | learnability | Hurt |
Surprising findings
- Universal online learnability does not imply computable universal online learnability even for DR classes.
- Universal online learnability does not imply computable agnostic learnability, unlike the non-computable setting.
Limitations
- Characterization of computable realizable universal online learning for arbitrary (non-RER) classes remains open.
- Restricted to hypotheses over the natural numbers (countable domains).
- Characterization of computable online learning with a uniform mistake bound is left open.
Experimental setup
Builds on: universal online learning (Bousquet et al. STOC 2021) RER classes prediction with expert advice (Hedge / weighted majority)
Closest papers by meaning
- A Theory of Optimistically Universal Online Learnability for General Concept Classes (NeurIPS 2024 · similarity 0.89)
- When Is Inductive Inference Possible? (NeurIPS 2024 · similarity 0.86)
- Private Online Learning against an Adaptive Adversary: Realizable and Agnostic Settings (NeurIPS 2025 · similarity 0.84)
- Smoothed Online Classification can be Harder than Batch Classification (NeurIPS 2024 · similarity 0.84)
- Online Classification with Predictions (NeurIPS 2024 · similarity 0.84)
- Universal Rates for Active Learning (NeurIPS 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.