# Trouble in understanding a simple example of No Free Lunch theorem

 3 2 I have trouble in understanding a simple example following No Free Lunch theorem in James Spall's Introduction to stochastic search and optimization: My understanding is that a cost function is a mapping from a finite set ({ heta_i}) to a finite set ({L_j}). A search algorithm, when applied to a cost function, is to search for a ( heta_i) such that the value of the cost function at it is the least. If there are (N_ heta) possible values in ({ heta_i}) and (N_L) possible values in ({L_j}), then by direct enumeration there are ((N_{L})^{N_ heta}) possible mappings from ({ heta_i}) to ({L_j}). The NFL theorems indicate that: When averaging over all ((N_{L})^{N_ heta}) possible mappings from from ({ heta_i}) to ({L_j}), all algorithms work the same (i.e., none can work better than a blind random search). Example 1.7 — NFL implications in a small problem. Suppose that (Theta = { heta_i, heta_2, heta_3}) and that there are two possible outcomes for the noise-free loss measurements, ({L_1, L_2}). Hence, ((N_L)^{N_ heta} = 2^3 = 8). Table 1.1 summarizes the eight possible mappings. Note that all rows in Table 1.1 have the same number of (L_1) and (L_2) values. Hence, the mean loss value across all eight possible problems is the same regardless of which ( heta_i) is chosen. Because the algorithm chooses the ( heta_i), all algorithms produce the same mean loss value when averaging across all possible problems. As a specific instance of the implication of the NFL theorems, suppose that (L_1 < L_2). Then, an algorithm that puts priority on picking ( heta) will work well on problems 1, 2, 3, and 7, but poorly on problems 4, 5, 6, and 8. The average performance is the same as an algorithm that puts priority on picking ( heta_2) or ( heta_3). My questions are: Does the example assume that an algorithm will always output the same element in (Theta), regardless of which of the eight loss function it is applied to? (This is the only way that I can make sense out of the example. Otherwise, how shall I understand it?) If yes, isn't it contrary to what an algorithm is in reality? For example, for minimizing different cost functions, the gradient descent algorithm outputs different solutions instead of a fixed solution. If no, I can construct an algorithm that outputs ( heta_1) for cost functions 1, 2, 3, 7 and 8, ( heta_2) for cost functions 4 and 5, and ( heta_3) for cost function 6. This algorithm outputs the best solution for each cost function, so when considering its average performance over all cost functions, it is obviously better than many other algorithms. This violates NFL theorem. What is going wrong? What exactly is a search algorithm? Is it a mapping from some set to another set? Thanks and regards! asked 11 Feb '12, 17:44 Timo 59●3●5 accept rate: 0% fbahr ♦ 4.6k●7●16 Is there some LaTex support on this site? (11 Feb '12, 17:46) Timo 2 Yes, but (a) you need to use ( and ) rather than \$ to terminate inline math formulas and (b) you need to double all backslashes to escape them (including the ones I just wrote as singles). (11 Feb '12, 20:57) Paul Rubin ♦♦ @Paul: Thanks! I don't quite understand. Can someone do the edit on my post, so that I can see how? (11 Feb '12, 21:18) Timo Looks like Florian did it (danke sehr). (12 Feb '12, 10:31) Paul Rubin ♦♦

 1 I'm not overly familiar with the No Free Lunch theorem, but from reading on Wikipedia it seems ridiculous to me. Empirical evidence would seem to suggest that some algorithms are simply better than others - perhaps not on every problem instance, but definitely on most. This theorem seems to me like the Efficient Market Hypothesis from economics. Theorists come up with something that sounds good on paper, but is clearly at odds with what happens in the real world. answered 11 Feb '12, 19:03 DC Woods ♦ 4.1k●2●25●46 accept rate: 5% This theorem is not ridiculous. It is just that many of us haven't understood it correctly. I don't rule out the possiblity the example in the book I mentioned may be wrong. (11 Feb '12, 19:49) Timo Oh, it's very likely that I haven't understood it correctly. At least I hope so. (11 Feb '12, 21:34) DC Woods ♦ @DC actually, I believe that the problem instances we see in practice is only a tiny subset of all (conceivable, no matter how ridiculous) instances. I always think of "practice is much nicer to us than theory predicts", and my personal explanation for that is: practice is made by humans, and theory is much too complicated for humans, so there is no practical instance that matches theory's complexity ;-) (12 Feb '12, 06:40) Marco Luebbecke ♦
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×190
×29
×5