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". Several comments are in order:
A general-purpose almost-universal optimizer exists theoretically. Each search algorithm performs well on almost all objective functions.
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.
I was wondering
- 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?
- 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!