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

Thank you for your supportive feedback and for recognizing the significance, quality, and originality of our work. As you point out, the compressibility of real-world data has long been studied by information theorists, and the consequent benefits of simplicity bias have historically been argued by theoretical computer scientists, especially in the wake of early no free lunch theorems. In our paper (Appendix B), we also reference literature on various notions of simplicity bias applied to neural networks. In this context, our work is valuable in several ways:

• The story we synthesize in our work and support with empirical evidence, namely that the low-complexity bias of neural networks enables general-purpose learners due to the shared structure underlying real world data, is actually not widely accepted across the deep learning community. We often see papers or prominent members of the ML community arguing for the fundamental necessity of problem-specific learners, sometimes explicitly referencing no free lunch theorems. For example, [1] say “the only way one strategy can outperform another is if it is specialized to the specific problem under consideration”, [2] reference the NFL in stating that “the business of developing search algorithms is one of building special-purpose methods to solve application-specific problems”, [3] say “the performance of the different algorithms over the 42 experiments considerably differ. This proves the validity of NFL theorems in our field”, and [4] reference NFL to explain why success on synthetic problems may not transfer to real ones. See [5,6] for examples of prominent community members leveraging the NFL to argue for specialized learners. Our work argues against these views intuitively, theoretically, and empirically.
• We present a number of novel experiments which we think will be interesting to the broad machine learning community, for example understanding the preferences of LLMs or repurposing tools from PAC-Bayes generalization theory to understand structure in data and to show that seemingly specialized models like CNNs actually possess a generic simplicity bias that allows them to compress and provably generalize on tabular datasets for which they were not designed.
• We phrase the no free lunch problem for machine learning as one of compression, which allows us to directly delineate between the no free lunch regime where data is incompressible, making learning impossible, and the regime which we actually observe in real world datasets, namely where data is highly structured and in fact shares structure in common with machine learning models, for example as measured by compressing labeling functions using neural networks which allows for highly nonvacuous PAC-Bayes generalization bounds.

Thank you again for your feedback. Do you have any other questions?

We thank you for your detailed review and thoughtful feedback. We address your questions and comments below:

Apparent contradiction between incompressible data being uncommon in the world we observe and common in the uniform distribution

When considering the uniform distribution, high complexity sequences are abundant. In the statement “All but exponentially few sequences …”, $n$ is indeed the sequence length, and we have now added that context to the paragraph. This classical result follows from the fact that there are at most $2^{L+1}$ terminating programs of length $L$, and therefore only at most that many distinct sequences with complexity $\le L$ out of the total $2^n$ sequences. Therefore the fraction of sequences with length $L$ is less than $2^{1+L-n}$. While high complexity sequences are abundant in the uniform distribution, we argue that they are very uncommon in natural data, including via experiments bounding the Kolmogorov complexity of real-world datasets.

$2^{k+1}$ labelings Y with $K(Y|X)≤k$

We reuse this classical counting argument for theorem 1. $K(Y|X)$ counts the length of the shortest program that produces $Y$ taking as input $X$. However, there are only at most $\sum_n^k 2^{n} = 2^{k+1}-1 \le 2^{k+1}$ programs of length $\le k$, and therefore there cannot be more than $2^{k+1}$ possible values of $Y$ given a fixed input $X$ (the programs are all deterministic).

Inequalities:

• “labels can be encoded in $K(Y|X, p) \leq - \sum_{i=1}^n \log_2 p(y_i | x_i) + 3$ bits” - This result comes from arithmetic coding using $p(y_i | x_i)$ at each index to form the probability distribution. The size of the arithmetic coding interval is $I = \Pi_i p(y_i|x_i)$ and an interval which is contained in it can be specified in at most $- \sum_{i=1}^n \log_2 p(y_i | x_i) +2$ (see p128 of Information Theory, Inference, and Learning Algorithms). The +3 is from a suboptimal strategy with additional overhead, but the bound holds true nevertheless.

• “$K(Y | X) \leq K(Y | X, p) + K(p) + 2 \log_2 K(p) + c$” - To derive this inequality, we note that $K(Y|X) \le K(Y, p | X)$, $K(Y,p|X) \le K(Y|X) + K(p|X) + 2\log K(p|X)+c$ (see e.g. p3 of [1]), and finally $K(p|X) \le K(p)$.

• $K_p(ℎ)≤K(ℎ)+2log_{2}⁡K(ℎ)$: this is an upper bound for the cost of converting an arbitrary encoding of $h$ into a prefix free code. Tighter bounds exist, but one way to see the asymptotic behavior is by leveraging arithmetic coding with three symbols ${0,1,STOP}$ according to the corresponding probabilities $1/2-1/(2N),1/2-1/(2N),1/N$, where $N=K(h)$ is the length of the original message. Encoding using arithmetic coding consumes at most $2+N log_2(\frac{2}{1-1/N) + \log_2(1/N)} = N + \log_2\big( \frac{1}{(1-1/N)^N}\big)$ bits, which is less than $N + 2\log_2(N)$, $\forall N \ge 24$.

“Randomly initialized models prefer low complexity”

While considering a single token at a time (independent of the others) at initialization, there exists a symmetry, so that all token probabilities on average would be as likely as all others. In contrast, it is not the case that a uniform initialization distribution would yield equal probabilities for pairs or sequences of tokens. In fact, it is very biased and this can be observed from the self attention layers:
$Softmax(QK^T)V = Softmax(X^TW_Q^TW_KX/d)V$. For modern LLMs, the $W_Q$ and $W_K$ matrices are shared, and the random initialization is such that $W_Q^TW_K \approx I$. Therefore the attention at initialization becomes $Softmax(X^TX/d)V$. Considering a single self attention layer, this creates correlations between the tokens that favor similarity, for example.

How do the authors demonstrate or claim that cross validation provably generalizes to millions of models with only thousands of data?

In Section 5.1, we demonstrate this is the case as an application of finite hypothesis generalization bounds, merely by selecting a uniform prior over the millions of models ($P(h) \ge 10^-8$ for 10 million models) and evaluating the bound with n=20000 for a classification problem with $\delta=.01$. Plugging these values into $R(H) - \hat{R}(h) \le \sqrt{\frac{\log 1/P(h)+\log 1/\delta}{2n}}$, we get $R(H) - \hat{R}(h) \le 0.034$, thereby demonstrating the claim.

Thank you for your engagement, and we are glad that all of your technical questions regarding theory have been addressed. Furthermore, we have now added citations and pointers to inequalities in Appendix D along with references in the main body of our updated draft, as suggested. We are grateful for the opportunity to respond to your additional questions below, and we would appreciate it if you could consider updating your score in light of our responses here:

It is not clear what the authors want to show by training a CNN over tabular data.

These experiments illustrate why a preference for low Kolmogorov complexity alone is sufficient for a nontrivial degree of generalization, provably, since real-world data labelings tend to have low complexity. We agree a model’s ability to generalize on a modality it was not designed for is not necessarily surprising, but the generalization bounds we compute only make use of the low Kolmogorov complexity preference, and this preference alone is able to explain almost all of the models’ generalization. Moreover, many in the community, explicitly motivated by no free lunch theorems, do argue that individual applications require specialized learners [1-6], and our work shows why this notion may be misguided in principle. We have now included additional clarifications in our updated draft.

Unclear how and what the right method of providing simplicity performance to architectures is.

We do not claim to have solved the problem of engineering an optimal low-complexity biased framework, but a point we make is that we do not need to compromise on flexibility in order to express a preference for low complexity solutions. In the GoogLeNet example, we illustrate the importance of also including the flexibility of a large model since some problems, for example ImageNet, require a higher complexity solution. Simply put, we want a model that prefers low complexity insofar as low complexity is appropriate for the data we observe; in other words, follow Occam’s Razor and choose the simplest explanation for the training set. For some datasets, the simplest explanation is more complex than for others. We have additionally updated the draft to make this point clear.

The authors do not train any models for the expression trees experiment.

We want to clarify that the examples involving numerical sequences are particularly interesting precisely because we did not train on such sequences. We show that both randomly initialized LLMs and ones pretrained on a vast text corpus naturally possess a generic notion of low-complexity bias. These experiments conceptually support the points we make using generalization bounds which explain generalization from an a priori low-complexity bias. It is also worth pointing out that training GPT-scale LLMs from scratch is infeasible on our computational budget, while a low-complexity bias would be much less surprising and interesting at very small architecture sizes we could afford to train.

Regarding the non-uniformity of sequences generated by LLMs, we actually used the stock GPT-2 architecture and initializer off-the-shelf with no modifications at all, which is to say that real architectures in circulation have this behavior. Moreover, the non-uniformity of labeling functions induced by neural network architectures was previously observed in simple classifiers [7], which we reference in our paper. Our experiments extend this observation to language models and to notions of complexity which are relevant to our work and notions of learnability from our formulation of the no free lunch theorem. Numerous architectural components (or combinations) may be responsible for this preference for low complexity numerical sequences in practice, including ones which are not yet understood, but our observation is simply that this property exists in neural networks, and it illustrates the low-complexity bias that can explain a nontrivial amount of generalization provably. Broadly speaking, understanding the components of neural networks which induce their low-complexity bias and how to improve this bias are foundational questions for the success of deep learning, and we intend to make progress on this long-term endeavor in our future work. As an aside, we suspect that the highly non-uniform distribution over functions induced by a diffuse or uniform distribution over parameters can explain why earlier PAC-Bayes generalization bounds work, even though they did not explicitly incorporate a preference for compressible parameter vectors. Namely, their diffuse prior probability distributions over parameters implicitly place disproportionate mass on low Kolmogorov complexity functions.

Do you have any other questions we can address? We appreciate the opportunity to engage with you, we think our draft has benefited from your feedback, and we are happy to provide any other additional information that would be helpful for your evaluation before the discussion phase closes tomorrow. Our work sheds light on foundational questions which underpin the success of deep learning, and we push back against pervasive and misguided ideas often justified by no free lunch theorems. We think that there is value in re-examining foundational questions and that this work will be broadly interesting to the ICLR community.

References:
[1] Ciuffo, Biagio and Vincenzo Punzo. "“No free lunch” theorems applied to the calibration of traffic simulation models." IEEE Transactions on Intelligent Transportation Systems (2013).
[2] Watson J-P, Barbulescu L, Howe AE, Whitley LD. Algorithm performance and problem structure for flow-shop scheduling. AAAI/IAAI (1999).
[3] Ho, Yu-Chi, and David L. Pepyne. “Simple explanation of the no-free-lunch theorem and its implications.” Journal of optimization theory and applications (2002).
[4] Whitley D, Watson JP. “Complexity theory and the no free lunch theorem.” Search methodologies (2005).
[5] twitter.com/GaryMarcus/status/1193209251834916864
[6] twitter.com/rasbt/status/1620125103966257152
[7] Valle-Perez, Guillermo, Chico Q. Camargo, and Ard A. Louis. "Deep learning generalizes because the parameter-function map is biased towards simple functions." International Conference on Learning Representations (2018).

The paper seems to suggest that No Free Lunch theorems somehow rule out the possibility of neural networks that can train successfully on a number of datasets and achieve non-trivial prediction or classification performance … I disagree with the premise that no-free lunch theorems state that “the world is hostile to inductive reasoning”.

The No Free Lunch Theorem of Wolpert (1996) proves the non-existence of general purpose learners and the hostility of the world to induction under the very strong assumption that learning problems are uniformly distributed. This theorem is frequently cited to argue that general purpose learners are impossible in practice, not only in theory. For example, [1] say “the performance of the different algorithms over the 42 experiments considerably differ. This proves the validity of NFL theorems in our field”, [2] reference NFL to explain why success on synthetic problems may not transfer to real ones, [3] say “the only way one strategy can outperform another is if it is specialized to the specific problem under consideration”, and [4] reference the NFL in stating that “the business of developing algorithms is one of building special-purpose methods to solve application-specific problems”. See [5,6] for examples of prominent community members leveraging the NFL to argue for specialized learners.

Our work fights back against this pervasive idea, arguing that real-world data shares a tremendous amount of structure in common with neural networks. We formalize the no free lunch problem in terms of compression, delineating between the compressible regime and incompressible regime where learning is impossible. We then examine the extent to which neural networks can compress data. Our experiments include results which fly in the face of arguments for specialized learners, for example we demonstrate the ability of convolutional networks to compress tabular data (with features written as pixels) which lacks any spatial structure and consequently prove highly non-vacuous cross-domain PAC-Bayes generalization bounds. In summary, while we agree that real-world learning problems are clearly non-uniform, there is a controversy surrounding the extent to which learning problems share common structure and the extent to which general purpose learners are possible. Our work synthesizes an explanation for why general purpose learners are possible and presents numerous novel experiments, including ones which show how established ideas, for example from information theory or learning theory, can explain the abilities of modern neural networks including LLMs.

The writing throughout the whole paper is very hand-wavy... A programming language can typically be compiled such that it can be executed on a UTM, …, but when considering a PyTorch program of 280 characters, the constant is far from negligible.

Your point that for very low complexity sequences, Kolmogorov complexity can vary significantly with different choices of the reference machine is well noted, and this choice (equivalent to a choice of language L) is referenced in our background section on Kolmogorov complexity. In this case, we define L using the Python programming language equipped with PyTorch and the standard libraries (and if desired the code to compile these libraries to any other reference turing machine). In terms of reference machine, this choice is as valid as any other, and the complexities computed (with the exception of the expression tree experiments) are with respect to this reference machine.

Using a more restrictive class like in the experimental tasks defined in the paper, ... the numbers reported in the paper should not be called Kolmogorov complexity

In Section 4.3, we consider a simplified non-universal language using expression trees. Language is included as a subset of the universal hypothesis class. If sequences are simple in this simplified language, then with some number of additional bits to encode the description of this language, the sequences will be simple according to Kolmogorov complexity too. However, we take your point that the language in this paragraph could be made more precise, and we have done so in the updated draft.

Thank you for your feedback and for recognizing the importance, timeliness, and simplicity of our work. We address each of your points below:

Its novelty is very limited.

We indeed cite a number of these works on Kolmogorov complexity, universal induction in the context of no free lunch theorems, or simplicity bias in neural networks. However, no free lunch theorems are commonly referenced in support of the need for domain-specific learners, and the community lacks an understanding of why machine learning algorithms possess generic generalization capabilities across real-world problems. See [1-6] for example claims that the NFL ensures that we need specialized learners for individual applications of machine learning in practice.

In our work, we synthesize an argument for shared common structure of real-world data distributions and neural networks, including numerous novel experiments from computing the first cross-domain generalization bounds to measuring the preference of LLMs for low-complexity numerical sequences, and we relate this phenomenon to NFL by deriving a new no free lunch theorem in terms of compressibility. Our formulation of the no free lunch theorem allows us to tease out the applicability of no free lunch theorems to real-world problems by performing compression of datasets and models. Our work argues directly against commonly held beliefs, and we synthesize a story that to our knowledge does not exist in its full form in the literature. Moreover, our experiments lead to conclusions which will likely be surprising to many in the community. For example, Reviewer VnMw says "given that it is a randomly initialized network, wouldn’t it basically give a uniform distribution over all possible sentences?" In contrast to the reviewer's intuition, we show that randomly initialized LLMs induce a highly non-uniform distribution over sequences, namely one which puts disproportionate mass on low-complexity sequences. Due to the controversial nature of our overarching argument, our novel experiments, and formulation of the no free lunch theorem, this work will attract attention and contribute significantly to ICLR 2024.

As a counter-argument consider [1], who investigate neural networks’ ability to learn simple algorithmic patterns across the levels of the Chomsky hierarchy (a hierarchy of computational complexity).

The point of our paper is not that neural networks perfectly mimic Solomonov induction or are near-optimal in any way, from the viewpoint of low-complexity bias. Rather, we argue that the extent of their low-complexity bias can explain their broad generalization capabilities and why general-purpose machine learning algorithms are possible. We don’t disagree with the point that in practice a given function may be hard to learn for a network even if it can be expressed in the model weights. Furthermore, many model architectures like transformers don’t have the ability to express an algorithm that solves a given problem due to the complexity class and how the compute grows as a function of the context length. However, we don’t think that the imperfections of neural networks detracts from the arguments we make in our paper.

Thank you again for your feedback. Do you have any other questions?

Thank you for your supportive feedback and for recognizing the originality, significance, and quality of our work. We address your individual comments below:

1. "The assertion that a universal high-degree polynomial can be effectively applied across diverse sample sizes, given a bias towards simplicity, lacks comparative analysis with contemporary leading methods."

Our polynomial experiment serves as an illustration of a broader principle, namely that the low complexity of datasets allows a single model to perform well on many problems (in this illustration, sample sizes) simultaneously as long as the model too encodes a preference for low complexity. This illustration is not intended to advocate for polynomials in particular as a competitive method for machine learning problems In fact, other expressive models likely encode an even better approximation of the Solomonov prior, for example, on relevant problems.

2. "The commentary on the combined effectiveness of GoogLeNet and ViT, underpinned by a simplicity preference, does not evidently align with the primary findings of the study."

This experiment shows that problems which seemingly benefit from different learners (e.g. small datasets vs large datasets) can be solved by a single learner with a simplicity bias. This point aligns with the broad message of our paper, namely that no free lunch theorems do not limit machine learning since real data tends to share common structure, enabling general purpose learners in principle. On the other hand, this experiment also verifies that ViTs do not possess as strong a simplicity bias as GoogLeNet, highlighting that different neural networks exhibit varying degrees of simplicity bias, and this bias can affect performance on various tasks. Thank you for pointing this out, and we have updated our draft with a corresponding discussion.

3. "The authors propose a heuristic for addressing the non-computability of Kolmogorov complexity by employing a simplified, non-universal computational language."

We adopt three different setups for complexity: (a) we bound Kolmogorov complexity directly via compression. In an ideal world, we could use Kolmogorov complexity across the boards, but comparing Kolmogorov complexity of different sequences is infeasible because we can only compare upper bounds; (b) we employ expression trees in Section 4.3. This setup allows us to measure complexity exactly for small sequences, and it allows us to bound Kolmogorov complexity formally as we discuss, but the language has the drawback of being simpler than a universal language; (c) we generate periodic sequences in 4.4. This language is even less rich than the expression trees, but it enables us to measure the complexity of very long sequences which are useful for experiments with randomly initialized models. Nonetheless, this third setup also is conveniently related to an upper bound on Kolmogorov complexity (e.g. in Python) given by the length of say print(n*x), where n denotes the number of repetitions, and x denotes the repeated subsequence.

4. "While the findings of the paper are intriguing, many of the experimental results seem tangential or conceptually disconnected from the core conclusions drawn in Theorem 1."

Theorem 1 delineates the cases where data is highly structured and those where data is incompressible and learning is impossible. We then spend the remainder of the paper showing that both real-world data and ML models share a common notion of structure and hence why learning is possible in practice. Proving a no free lunch theorem in terms of compressibility allows us to explore the extent to which that theorem is limiting in the real world by applying compression to datasets and models.

Thank you again for your thoughtful review. We made a significant effort to address your feedback and would appreciate it if you would consider raising your score in light of our response. Please let us know if you have additional questions we can address.

Thank you again for your feedback. Do you have any other questions?