Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

From Wikipedia about interpretations of no free lunch theorem

A conventional, but not entirely accurate, interpretation of the NFL results is that "a general-purpose universal optimization strategy is theoretically impossible, and the only way one strategy can outperform another is if it is specialized to the specific problem under consideration".[14] Several comments are in order:

A general-purpose almost-universal optimizer exists theoretically. Each search algorithm performs well on almost all objective functions.[11]

...

For almost all objective functions, specialization is essentially accidental. Incompressible, or Kolmogorov random, objective functions have no regularity for an algorithm to exploit. Given an incompressible objective function, there is no basis for choosing one algorithm over another. If a chosen algorithm performs better than most, the result is happenstance.[11]

I was wondering

  1. How shall I understand that a general-purpose universal optimizer doesn't exist but a general-purpose almost universal optimizer does? What differences are between universal and almost universal?
  2. Do the last two sentences in bold contradict each other? Do "an optimizer being almost-universal and perform well on all objective functions" and "it being specialized for almost all objective functions" imply each other?

Thanks and regards!

share|improve this question
    
You may want to take the question to brand-new cs.SE! –  Raphael Mar 23 '12 at 23:31
    
Thanks! Is it too theoretical for that new site? –  Tim Mar 23 '12 at 23:54
    
Not at all, we span all CS. –  Raphael Mar 24 '12 at 11:55
    
Is that an 'almost' full employment theorem? –  Trevor Alexander Mar 1 '13 at 9:30

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.