The no free lunch theorem, due to David Wolpert and William Macready, is a result in the mathematics of optimization stating, loosely, that there is no universally superior algorithm for solving every possible optimization problem. It first appeared in their 1997 paper on the subject, building on related no free lunch results Wolpert had earlier derived for machine learning. In a later restatement, Wolpert and Macready summarized the theorem as saying that any two optimization algorithms perform equally well when their performance is averaged across every possible problem they might be applied to. The theorem is deliberately a weaker and more easily stated consequence of the fuller results the two authors actually proved, and its interpretation and relevance to practical machine learning research remain debated among specialists.
Facts
StatementFor the problem of optimizing a function f over a set V, no algorithm performs better than blind search. 1 Classification
Statement Form Connections
Has Statement Form
In Branch
Source No free lunch theorem, Wikipedia
Sources
1. No free lunch theorem, Wikipedia
Lead section
It appeared in the 1997 paper "No Free Lunch Theorems for Optimization".
In Branch: Optimization, Lead paragraph
In this case the intended meaning is that on the average there are no easy shortcuts to designing optimization algorithms.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.