Research map / Label-efficient and robust learning / Recognition and long-tail
Position: The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine 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.
Position paper arguing that real-world datasets and neural networks share a low-Kolmogorov-complexity bias, which lets flexible models with a simplicity prior act as a single general-purpose learner across domains and sample sizes.
Problem
No free lunch theorems are often cited to argue that each problem requires specially tailored inductive biases; the paper asks how real-world data structure and neural network biases relate to these theorems, using Kolmogorov complexity.
Approach
Formalizes the gap between uniform random labelings (incompressible, where learning is impossible) and real data (compressible) via Kolmogorov complexity, derives a Kolmogorov-style no free lunch theorem, and shows neural networks (CNNs on tabular data, GPT-style LMs, random initializations) prefer low-complexity outputs, so a flexible model with a simplicity penalty can serve many problems and sa
Key results
- Compression of CIFAR-10 and CIFAR-100 labels with CNNs and tabular labels with MLPs is far below n log2 C, rejecting uniform random labelings with extremely high confidence.
- GPT-3 log-probability of expression-tree sequences decays roughly exponentially with complexity, with larger GPT-3 variants (e.g., Davinci) showing a stronger preference for simple sequences.
- Randomly initialized GPT-2 models assign exponentially higher probability to low-complexity length-10 bitstrings; the one-sided t-test rejects the null of no simplicity bias with p-values near 0 across all models.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train GPT-2 Base rather than use a uniform sequence distribution | GPT-2 Base · Length-100 sequences | mean Kolmogorov complexity: 98.36 -> 60.81 | Helped |
| Train GPT-2 Medium rather than use a uniform sequence distribution | GPT-2 Medium · Length-100 sequences | mean Kolmogorov complexity: 98.36 -> 48.41 | Helped |
| Train GPT-2 Large rather than use a uniform sequence distribution | GPT-2 Large · Length-100 sequences | mean Kolmogorov complexity: 98.36 -> 46.34 | Helped |
| Use randomly initialized GPT-2 Base rather than a uniform sequence distribution | GPT-2 Base · Length-100 sequences | mean Kolmogorov complexity: 98.36 -> 98.00 | Helped |
| Combine GoogLeNet and ViT logits with weight decay favoring GoogLeNet | GoogLeNet and ViT-B/16 · CIFAR-10 test | accuracy: 72.020 % -> 93.860 % | Helped |
| Combine GoogLeNet and ViT logits with weight decay favoring GoogLeNet | GoogLeNet and ViT-B/16 · CIFAR-100 test | accuracy: 75.160 % -> 71.990 % | Hurt |
| Combine GoogLeNet and ViT logits with weight decay favoring GoogLeNet | GoogLeNet and ViT-B/16 · ImageNet | accuracy: 69.778 % -> 81.090 % | Helped |
| Combine GoogLeNet and Swin logits with weight decay favoring GoogLeNet | GoogLeNet and Swin-B · CIFAR-10 test | accuracy: 93.840 % -> 93.760 % | No clear effect |
| Combine GoogLeNet and Swin logits with weight decay favoring GoogLeNet | GoogLeNet and Swin-B · CIFAR-100 test | accuracy: 75.160 % -> 75.360 % | Helped |
| Combine GoogLeNet and Swin logits with weight decay favoring GoogLeNet | GoogLeNet and Swin-B · ImageNet | accuracy: 69.778 % -> 83.150 % | Helped |
Surprising findings
- Randomly initialized GPT-2 models already exhibit a low-complexity bias before any training data is seen.
- CNNs designed for computer vision generalize on tabular data with no spatial structure, with finite-hypothesis compression bounds nearly matching test error.
Limitations
- Kolmogorov complexity bounds from compression are likely very loose and non-optimal.
- Many experiments are proof-of-concept and cannot be guaranteed to hold for all datasets or models, since facts about real-world data distributions cannot be proven mathematically.
- Expression-tree complexity is only an upper-bound proxy for true Kolmogorov complexity under a simplified non-Turing-complete language.
Experimental setup
Datasets: CIFAR-10 CIFAR-100 ImageNet OpenML tabular classification datasets Amazon Review Full LibriSpeech
Benchmarks: CIFAR-10 CIFAR-100 ImageNet
Metrics: test accuracy cross-entropy average log-probability by complexity compressed size (bits) one-sided t-test p-value generalization bound gap
Baselines: GoogLeNet ViT-B/16 Swin-B uniform distribution over sequences
Builds on: no free lunch theorem (Wolpert) Solomonoff induction PAC-Bayes minimum description length
Closest papers by meaning
- When Is Inductive Inference Possible? (NeurIPS 2024 · similarity 0.86)
- Understanding Generalization Requires Universal Induction (NeurIPS 2026 · similarity 0.85)
- Local vs. Global Interpretability: A Computational Complexity Perspective (ICML 2024 · similarity 0.85)
- In-Context Learning and Occam's Razor (ICML 2025 · similarity 0.85)
- Additive Models Explained: A Computational Complexity Approach (NeurIPS 2025 · similarity 0.85)
- No Free Lunch: Fundamental Limits of Learning Non-Hallucinating Generative Models (ICLR 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.