Nigerian spammers get theirs...

http://news.bbc.co.uk/1/hi/world/africa/3887493.stm

*coughs up lung*

(Thanks are due to galliana for the link)

This is just wrong,,,

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. :-)

Net deadness

My 1 month subscription to DSL just timed out. My debit card is out of date, thanks to the Bank of Moronia (aka Barclays) mailing out a new card too late for me to get it before I left for the States, and for no adequately explained reason it doesn't like either of my credit cards (which I'm pretty sure are working, because I've used them recently -- the DSL thingy refused them when I signed up initially too).

Bottom burps.

I should be able to sort something out, but it may take 2 - 3 weeks to get a bank account opened here. I'm still waiting for my social security number. This means I'm currently bank facilityless -- I can't use my UK bank, because none of my cards work and the nearest branch is 5500 miles away, and I can't open a US account until I get a social security number, which should have arrived today but (I'm told) can take up to 6 weeks to arrive rather than the two they quote.

Oh well. You're probably not going to hear much from me on here for a while, it seems. I might buy a one-shot prepay credit card from the local supermarket tomorrow, which at least should let me get DSL sorted out.

Don't expect me to see email or LJ posts until that is sorted, please!