Research map / Bandits and online learning / Online convex optimization and games
When Is Inductive Inference Possible?
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 when inductive inference is possible by linking it to a new non-uniform online learning framework, showing learnability holds iff the hypothesis class is a countable union of Littlestone classes (realizable and agnostic settings).
Problem
When can a learner make only finitely many mistakes (hypothesis-wise) when inferring a ground-truth hypothesis from an infinite observation sequence, i.e., characterizing inductive inference beyond countable hypothesis classes?
Approach
Introduces non-uniform online learning, where the ground-truth hypothesis is fixed obliviously in advance and error bounds may depend on it; shows this is equivalent to inductive inference and characterizes it as countable unions of finite-Littlestone-dimension classes, with an SRM-style algorithm over the partition.
Key results
- Inductive inference (finite hypothesis-wise mistakes) is possible iff H is a countable union of Littlestone classes, under both adaptive and iid observations.
- In the agnostic setting, countable unions of Littlestone classes admit O~(sqrt(T)) regret, while other classes require arbitrarily slow rates; a trichotomy of rates is established.
- Uniform online learnability is strictly contained in non-uniform online learnability (rational thresholds example).
Surprising findings
- Non-uniform stochastic learnability is equivalent to non-uniform adaptive learnability, so iid versus adversarial observations give the same characterization.
- Consistency is shown to require no aleph_1-size tree, a necessary condition conjectured to be tight.
Limitations
- Focuses on error bounds without computational constraints; learners need not be computable.
- Sufficient condition for consistency remains open; the no aleph_1-size tree condition is only conjectured tight.
Experimental setup
Metrics: mistake bound expected regret
Baselines: Solomonoff induction Standard Optimal Algorithm
Builds on: Littlestone dimension Solomonoff induction non-uniform PAC learning Standard Optimal Algorithm Follow the Perturbed Leader
Closest papers by meaning
- Understanding Generalization Requires Universal Induction (NeurIPS 2026 · similarity 0.87)
- Computable universal online learning (NeurIPS 2025 · similarity 0.86)
- Phenomenal Yet Puzzling: Testing Inductive Reasoning Capabilities of Language Models with Hypothesis Refinement (ICLR 2024 · similarity 0.86)
- Position: The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning (ICML 2024 · similarity 0.86)
- Inductive Learning of Logical Theories with LLMs: A Expressivity-graded Analysis (AAAI 2025 · similarity 0.85)
- Hypothesis Search: Inductive Reasoning with Language Models (ICLR 2024 · 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.