This is just wrong,,,

[compilerbitch]

Moved here from a conversation under a locked post, because it's too interesting to hide. (Thanks to lethargic_man)...

From http://www.no-free-lunch.org/ :

Wolpert and Macready (1995), "No Free Lunch Theorems for Search"
"...all algorithms that search for an extremum of a cost function perform exactly the same, when averaged over all possible cost functions. In particular, if algorithm A outperforms algorithm B on some cost functions, then loosely speaking there must exist exactly as many other functions where B outperforms A."

Wolpert and Macready (1997), "No Free Lunch Theorems for Optimization"
"...for any algorithm, any elevated performance over one class of problems is exactly paid for in performance over another class."

My reply earlier:

I have a slight problem with what I read on the 'no free lunch' site, because the argument (at least as regards computational complexity) seems to have a big hole in it that goes something like this:

A and B are both (deterministic) search algorithms operating on the same problem. Search time 'area under the curve' is equal in both cases, but O(A x) will typically differ from O(B x), for most x [EDIT: assume here that there exists an x and y such that O(A x) < O(B x) and O(A y) > O(B y) -- this trick doesn't apply if A is always better than B or vice-versa]. Let A|B be a composite algorithm, constructed by composing A and B in parallel (perhaps running on two separate processors, or as two fairly scheduled threads) such that (A|B) x returns a result as soon as the first of A or B returns a result, with the other (redundant) process being terminated immediately. It follows trivially that for all x, O((A|A) x) = O(A x), O((A|B) x) <= O(A x) and O((A|B) x) <= O(B x), so, strictly, A|B has better complexity than either A or B acting alone (assuming that O(A x) does not equal O(B x) for some x).

This would seem to be a trivial disproof by counterexample. A similar counterexample should also hold for quality of results in suboptimal optimisation (e.g. if P and Q generate results p = P x and q = Q x for some x, optimised against some cost function C, pick the best of p and q, so (to invent a bit more notation), C((P||Q) x) <= C(P x) and C((P||Q) x) <= C(Q x) for all x. Amortising this over the whole domain would inevitably show that the composite function is better than either of the original functions iff there exists at least one x where P x is not equal to Q x -- for the lattice theory pedants out there, I should probably mention also that all (some?) members of the range of C must be comparable).

Maybe there are still no free lunches, but it should be reasonable to go looking for free coffee refills, at least. :-)

Comments

[masterkill.livejournal.com]

I don't understand all of your post, but I think a condition is that every search algorithm under consideration must be equally efficient, in that each solution be considered only once, and each solution requires the same amount of time to check. So an A|B composite algorithm isn't any faster: if your search space is all integers up to a million, and A counts down from a million and B counts up from 2, then if the solution is 1 the A|B composite will take twice as much time as either A or B.

I understood the situation to be similar to that of data compression: data compression algorithms map the set of all strings (of length n, for this argument) to another set where some are longer than the original, and some are shorter. But there is no data compression algorithms for which the *average* length of compressed strings is less than n.

My response to Wolpert and Macready is that fortunately, the set of problems we care about are amenable to search, in just the same way that the set of data we care about is amenable to compression.

(Tried to post this yesterday but commenting wasn't working.)