7
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Have you read the whole article, in particular the formal statement and the interpretations? $\endgroup$ – Raphael♦ Feb 18 '14 at 12:59
  • $\begingroup$ 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. $\endgroup$ – vzn Feb 18 '14 at 18:30
10
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – Reinstate Monica Feb 18 '14 at 17:03
  • 3
    $\begingroup$ @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. $\endgroup$ – Tim S. Feb 18 '14 at 17:12
  • 4
    $\begingroup$ @yochannah You may think the nice salesperon just wants to invite you to lunch, but there's always a catch. $\endgroup$ – Raphael♦ Feb 18 '14 at 18:10
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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