Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

I've been reading about the No Free Lunch Theorem, but I can't quite understand what it is about. I've heard this theorem described elsewhere as the claim that "no general purpose universal optimiser exists". On the other hand, the Wikipedia article talks about 'candidate solutions" that are "evaluated one by one" - if we only consider algorithms of a particular form, then that is a much more limited claim.

Can anyone explain what this theorem actually claims?

share|improve this question
    
Have you read the whole article, in particular the formal statement and the interpretations? –  Raphael Feb 18 at 12:59
    
fyi P≠NP can be regarded as related to the thm. a counterpoint to this theorem however is that definitely different ML algorithms have different performance on real-world data, and are optimizable. –  vzn Feb 18 at 18:30

2 Answers 2

The No Free Lunch theorem (NFL) was established to debunk claims of the form:

My optimisation strategy X is always best.

In particular, such claims arose in the area of genetic/evolutionary algorithms.

The statement is, roughly: every optimisation strategy performs badly on many problems. Therefore, there can be no always-best strategy and your claim about X is wrong.

share|improve this answer
    
Out of curiousity, how on earth does this get to be called 'no free lunch'? Your explanation makes sense, but I can't see what it has do do with lunch (nom). –  yochannah Feb 18 at 17:03
1  
@yochannah Ever heard the phrase, "There's no such thing as a free lunch"‌​? To me, in this context, it means that an algorithm can have some situations better, but not everything better. See also Wikipedia' article on the theorem‌​, with its own analogy/explanation. –  Tim S. Feb 18 at 17:12
1  
@yochannah You may think the nice salesperon just wants to invite you to lunch, but there's always a catch. –  Raphael Feb 18 at 18:10

As far as I understand it, this theory is aimed at global optimization methods like Genetic Algorithms, Neural Networks, Simulated Annealing and so on...

The main claim is that if we consider all possible problem instances of a certain problem, these methods are just as good as any other optimizer that consider the same amount of candidate solutions, even Random Walk for example.

The general purpose optimizers will probably work well on many popular/real life problem instances, but these do not represent well the entire space of possible problem instances.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.