No free lunch theorems

Question

In James Spall's book, when explaining NFL theorems (http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization}) an example is given. Suppose input space has $3$ elements and output space has $2$ elements. Then we have $8$ possible mappings. Then it claims that an optimization algorithm which chooses one specific input value will be better for certain mappings and not better for certain mappings. This is confusing. An optimization algorithm chooses an input value depending on the mapping. The way it is written in the book means that an optimization algorithm finds the optimum independent of the function. Can someone please clarify it.

Answer 1

We are talking here about black-box optimization. There is no initializing input to the optimizer, so the optimizer's first input, $x_1$, to the objective function (mapping) $f$ depends on nothing. The optimizer's next input, $x_2$, depends only on the datum $f(x_1) = y_1$. The crucial thing to understand is that what has been observed so far of the relation of inputs to outputs imposes no constraint whatsoever on what has yet to be observed. The optimizer began with no information of the objective function, and can gain no information by processing data it has gathered. There is no way to deduce anything about the value of $f(x_2).$

The short answer to your question: No, the input does not depend on the mapping. That is why the mapping is referred to as a "black box." You can find some figures that might help (rare in the NFL literature) in a brief preface that I've added to my first paper on NFL (1996). However, the captions are dense, and I recommend that you rely on the text.