In computational complexity and optimisation the no free lunch (NFL) theorem is a result that states that for certain types of mathematical problems (definitely NOT all), the computational cost of finding a solution, averaged over all problems in the class, is the same for any solution method. In this case no solution therefore offers a "short-cut". This is under the assumption that the search space is a probability density function.
Here is the good bit, however:
The NFL theorem DOES NOT APPLY to the case where the search space has underlying structure (for example if the objective function is differentiable) that can be exploited more efficiently (f.e. Newton's method in optimization)!
That means that there is a very, very large class of problems where the clan of meta people can/could/should throw out the typical metaheuristic for much better tools that offer guarantees. Isn't that special? I have been aware of this for quite some time, but forgot it, but now I happened to discover it again.
So take the opportunity to look at your problem, and investigate whether the set-up in the theory works for YOU - and you may be awarded with a much better solution than what any meta-thing can achieve:
https://arxiv.org/pdf/1703.02628.pdf
https://machinelearningmastery.com/no-free-lunch-theorem-for-machine-learning/
- Badges
- Science topic