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

Abstract

The "No Free Lunch" (NFL) theorems traditionally suggest that no single machine learning model can outperform all others across all possible problems. However, the rise of "foundation models" like Transformers, which excel across diverse domains, challenges this notion. This paper argues that real-world data is not random but highly structured and "simple" in terms of Kolmogorov complexity. By leveraging this simplicity bias, modern neural networks can generalize across vastly different tasks without requiring specialized, hand-crafted inductive biases.

The NFL Paradox and the Rise of Foundation Models

In the late 1990s, the No Free Lunch theorems established that, averaged over all possible problems, every learning algorithm performs identically. This led to the belief that success requires tailoring "inductive biases"—specific architectural assumptions—to individual domains, such as using Convolutional Neural Networks (CNNs) for spatial image data.

The convergence of deep learning architectures across domains.

Despite this theory, the field is witnessing a consolidation. Architectures like Transformers are achieving state-of-the-art results in text, vision, and even protein folding. This paper addresses the tension between NFL theory and the empirical success of general-purpose models, proposing that the "hostile" assumption of the NFL theorems—that all data labelings are equally likely—does not hold for the real world.

Methodology: Kolmogorov Complexity as a Metric

The authors bridge theory and practice using Kolmogorov complexity, which measures the shortest program required to generate a dataset. They propose that real-world data is disproportionately "simple" and compressible.

  1. Neural Networks as Compressors: The study demonstrates that trained neural networks can losslessly compress data labels. Successful compression serves as empirical proof of low Kolmogorov complexity.
  2. A Kolmogorov-style NFL Theorem: The authors derive a new theorem proving that while learning is impossible on high-complexity (random) data, it is provably achievable on the compressible data characteristic of the physical world.
  3. Measuring Simplicity Bias: Using language models like GPT-3, they tested whether models inherently prefer simpler sequences generated by mathematical expression trees.
  4. Cross-Domain Stress Tests: To test the necessity of domain-specific biases, they applied CNNs to tabular data reshaped as images, evaluating if the model's general preference for simplicity outweighs its spatial architectural bias.

Key Insights: The Universality of Simplicity

The research yields several profound insights into why modern AI is so effective:

  • The World is Compressible: Every real-world dataset tested—from audio and text to tabular data—was significantly more compressible than random noise.
  • Inherent Simplicity Bias: Neural networks possess an intrinsic "simplicity bias." Even randomly initialized models are exponentially more likely to generate low-complexity, repetitive sequences than complex ones.
  • Architecture vs. Bias: The success of CNNs on tabular data suggests that their performance stems more from a general preference for low-complexity solutions than from vision-specific design.

Empirical Results

The authors' experiments confirm that simplicity is a powerful universal prior.

Compression results and generalization bounds for tabular and image datasets.
  • GPT-3's Preference: Larger models like davinci exhibit a stronger simplicity bias than smaller variants, assigning exponentially higher probabilities to sequences with lower Kolmogorov complexity.
  • Generalization Bounds: The complexity-based generalization bounds derived by the authors were "non-vacuous," meaning they provided meaningful information that closely tracked actual test errors across various datasets.
  • Unified Learning: By combining models of different scales with a simplicity-biased prior, the authors created a "learner" that automatically adapts to both small and large datasets, outperforming specialized model selection.

Limitations and Future Directions

While the paper provides a compelling theoretical framework, it acknowledges several hurdles. Kolmogorov complexity is technically uncomputable, forcing reliance on proxies like bzip2 or neural network negative log-likelihood (NLL). Furthermore, while the complexity-based bounds are informative, they remain loose compared to actual model performance. Future research may explore whether other structural properties, such as symmetry or causality, offer even more precise metrics for the "simplicity" that drives machine learning success.

Summary updated

BibTeX
@inproceedings{goldblum2024no,
  author = {Micah Goldblum and Marc Finzi and Keefer Rowan and Andrew Gordon Wilson},
  title = {{The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=EaJ7nqJ2Fa},
}
Figure