The No Free Lunch Theorem - Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning

Aug 4, 2026

Upload by Logic

No free lunch theorems for supervised learning state that no learner can solve all problems or that all learners obtain the same average accuracy over a uniform distribution of learning problems. This motivates the belief that each problem needs tailored inductive biases. The work argues that while uniformly sampled datasets have high Kolmogorov complexity, real-world data is biased toward low complexity, and neural networks share this preference. It shows domain-specific architectures can compress diverse domains and that pre-trained and random language models generate low-complexity sequences, while supporting automation of model selection when labeled data is scarce or abundant.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages21

Reading Time53 min

AccessFree to download

Introduction

Inductive reasoning and learning feasibility

No free lunch theorems in supervised learning

Real-world structured data and inductive bias

Kolmogorov complexity and compressibility

Neural networks and low-complexity preference

The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning Micah Goldblum * Marc Finzi * Keefer Rowan Andrew Gordon Wilson New York University arXiv :2304 .05366v1 [ cs .LG] 11 Apr 2023 Abstract No free lunch theorems for supervised learning state that no learner can solve all problems or that all learners achieve exactly the same accuracy on average over a uniform distribution on learning problems. Accordingly, these theorems are often referenced in support of the notion that individual problems require specially tailored inductive biases. While virtually all uniformly sampled datasets have high complexity, real-world problems disproportionately generate low-complexity data, and we argue that neural network models share this same preference, formalized using Kolmogorov complexity. Notably, we show that architectures designed for a particular domain, such as computer vision, can compress datasets on a variety of seemingly unrelated domains. Our experiments show that pre-trained and even randomly initialized language models prefer to generate low-complexity sequences. Whereas no free lunch theorems seemingly indicate that individual problems require specialized learners, we explain how tasks that often require human intervention such as picking an appropriately sized model when labeled data is scarce or plentiful can be automated into a single learning algorithm. These observations justify the trend in deep learning of unifying seemingly disparate problems with an increasingly small set of machine learning models. 1. Introduction The problem of justifying inductive reasoning has challenged epistemologists since at least the 1700s (Hume, 1748) . How can we justify our belief that patterns we observed previously are likely to continue into the future without appealing to this same inductive reasoning in a circular fashion? Nonetheless, we adopt inductive reasoning in everyday life whenever we learn from our mistakes or make decisions based on past experience. Likewise, the feasibility of machine learning is entirely dependent on in- * Equal contribution. duction, as models extrapolate from patterns found in previously observed training data to new samples at inference time. More recently, in the late 1990s, no free lunch theorems emerged from the computer science community as rigorous arguments for the impossibility of induction in contexts seemingly relevant to real machine learning problems (Wolpert, 1996 ; Wolpert & Macready, 1997) . One such no free lunch theorem for supervised learning states that no single learner can achieve high accuracy on every problem (Shalev-Shwartz & Ben-David, 2014) . Another states that, assuming a world where labeling functions of learning problems are drawn from a uniform distribution, every learner is equally good on expectation, achieving the same accuracy as a random guess (Wolpert, 1996) . Such a world would be hostile to inductive reasoning. The assumption that labelings are drawn uniformly ensures that training data is uninformative about unseen samples. In contrast to this dismal outlook on machine learning, naturally occurring inference problems involve highly structured data, and basic structures are often shared even across seemingly disparate different problems. If we can design learning algorithms with inductive biases that are aligned with this structure, then we may hope to perform inference on a wide range of problems. In this work, we explore the alignment between structure in real-world data and machine learning models through the lens of Kolmogorov complexity. The Kolmogorov complexity of an output is deﬁned as the length of the shortest program under a ﬁxed language that produces that output. In Section 3, we explain the connection between Kolmogorov complexity and compressibility. We note that virtually all data drawn from a uniform distribution as assumed by the no free lunch theorem of Wolpert (1996) canno

FAQs

What do no free lunch theorems imply for supervised learning?

They imply that no learner can achieve high accuracy on every possible problem, and under a uniform distribution of learning labels, all learners have equal expected performance.

How does Kolmogorov complexity relate to the paper’s argument about inductive bias?

Kolmogorov complexity measures the length of the shortest program generating an output; the paper links this to compressibility and argues that real-world datasets and neural models preferentially produce or select low-complexity outputs.

What evidence does the paper provide that neural network models prefer low-complexity data?

It reports experiments where both pre-trained and randomly initialized language models favor generation of low-complexity sequences, and vision architectures prefer correct labelings even when inputs lack natural image structure.

Aug 4, 2026

Upload by Logic