Link to original article

Welcome to The Nonlinear Library, where we use Text-to-Speech software to convert the best writing from the Rationalist and EA communities into audio. This is: The No Free Lunch theorems and their Razor, published by Adrià Garriga-alonso on May 24, 2022 on The AI Alignment Forum. The No Free Lunch (NFL) family of theorems contains some of the most misunderstood theorems of machine learning. They apply to learning[1] and optimization[2] and, in rough terms, they state: All algorithms for learning [respectively, optimization] do equally well at generalization performance [cost of the found solution] when averaged over all possible problems. This has some counterintuitive consequences. For example, consider a learning algorithm that chooses a hypothesis with the highest accuracy on a training set. This algorithm generalizes to a test set just as well as the algorithm which chooses the hypothesis with the lowest accuracy on training! Randomly guessing for every new instance is also just as good as these two. The NFL theorems thus seem to show that designing an algorithm that learns from experience is impossible. And yet, there exist processes (e.g. you, the reader of this sentence) which successfully learn from their environment and extrapolate to circumstances they never experienced before. How is this possible? The answer is that problems encountered in reality are not uniformly sampled from the set of all possible problems: the world is highly regular in specific ways. Successful learning and optimization processes (e.g. the scientific method, debate, evolution, gradient descent) exploit these regularities to generalize. If NFL theorems don't usually apply in reality, why should you care about them? My central claim is that they are essential to to think about why and when learning processes work. Notably, when analyzing some process, it is important to state the assumptions under which it can learn or optimize. Sometimes it is possible to test some of these assumptions, but ultimately unjustifiable assumptions will always remain. NFL theorems also allow us to quickly discard explanations for learning as incorrect or incomplete, if they make no reference to the conditions under which they apply. I call this the No Free Lunch Razor for theories of learning. In this post, I will: State a simple NFL theorem in detail and informally prove it. I describe some variants of it and the link between NFL theorems and Hume's problem of induction. Discuss when the NFL theorems are and aren't applicable in practice, and what they tell us about analyzing processes for generating knowledge that extrapolate (or interpolate). Introduce the NFL razor and use it to discard a simple theory of deep learning, as well as re-argue that the value loading problem is hard. Discuss PAC-Bayes generalization bounds as a possible way to pay for lunch in some worlds. NFL theorem statement and proof We will focus on a very simple NFL theorem about learning. The reasoning for other NFL theorems is pretty similar[1:1]. Suppose we have a finite set X of possible training points, as well as an arbitrary distribution D over the input space X. We are concerned with learning a function f:X→{0,1} that classifies elements of X into two classes. We are interested in algorithms A which, given a training set of input-output pairs (x1,f(x1)),(y2,f(y2)),.(yN,f(yN)), output a candidate hypothesis h which classifies elements of X. The training data are sampled independently from the distribution D. There are at least two ways in which we can measure the accuracy of a learning algorithm: The overall error or empirical risk, the proportion of possible inputs for which the learning algorithm makes a mistake. Its expression is R(h)=1/|X|∑x∈X[f(x)≠h(x)], and its value is between 0 and 1. This is the traditional measure in learning theory. The out-of-sample (OOS) generalization error, which is like the error but only for elements of X unseen during training. Its expression is ROO...