Research map / Learning theory and algorithms / Kernels and regression theory

Understanding Generalization Requires Universal Induction

NeurIPS 2026 · Learning theory and algorithms › Kernels and regression theory · approach: Statistical perspectives on generalization · 0 citations (OpenAlex)

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.

Argues that Solomonoff induction relativized to an information vantage point (oracle access to existing information) is the optimal universal inductive bias against meta-No-Free-Lunch, with regret bounded by algorithmic mutual information.

Problem

No Free Lunch theorems (and meta-NFL) imply that any learner needs an external inductive bias; the paper asks what principled bias can justify generalization of general-purpose AI systems.

Approach

Relativize Solomonoff induction to an information vantage point (a universal monotone machine with oracle q), favoring accessibility rather than absolute simplicity; prove regret of oracle SI against any predictor is bounded by the algorithmic mutual information between that predictor's program and the data.

Key results

• Theorem: regret of oracle Solomonoff induction M^q against predictor mu_p is bounded by MI^q(p:x) up to additive constant (theoretical).
• Proposition: for N-function meta-learning setting, k^{(N-m-1)n} of k^{(N-m)n} consistent meta-mappings predict each value, so meta-NFL holds.
• Theorem (no information ex nihilo): expected MI of a program generated by a small meta-algorithm r is at most |r| bits.

Surprising findings

• Any prior distribution can be reinterpreted as a simplicity bias, so 'simplicity' alone is an empty catch-all notion.

Limitations

• Solomonoff induction is incomputable; the result gives an idealized optimum rather than a practical algorithm.
• Regret bounds hide multiplicative and additive constants depending on the reference machine U.
• Analysis is limited to log loss; the paper notes the bound fails for 0-1 loss with adversarial sequences.

Experimental setup

Builds on: Solomonoff induction Kolmogorov complexity universal mixture prediction No Free Lunch theorems

Closest papers by meaning

• When Is Inductive Inference Possible? (NeurIPS 2024 · similarity 0.87)
• Slower Generalization, Faster Memorization: A Sweet Spot in Algorithmic Learning (NeurIPS 2026 · similarity 0.86)
• Position: The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning (ICML 2024 · similarity 0.85)
• Ascent Fails to Forget (NeurIPS 2025 · similarity 0.85)
• Epiplexity Guided Data Selection and Generation for Out-of-Distribution Generalization (NeurIPS 2026 · similarity 0.85)
• Does Compression Imply Generalization? A Minimum Description Length Perspective (NeurIPS 2026 · similarity 0.85)