Los teoremas No Free Lunch (NFL) publicados en 1997 por David Wolpert y William MacReady, son un conjunto de teoremas matemáticos que tienen implicaciones para el campo de la optimización y el aprendizaje supervisado.
En otras palabras, no existe un algoritmo de optimización que se adapte a todos los problemas por igual.
Entonces, según el teorema NFL, debe existir alguna distribución de problemas sobre P y Q tal que el algoritmo A y el algoritmo B tengan un rendimiento igual en promedio.
En otras palabras, cualquier mejora en el rendimiento del algoritmo A sobre el algoritmo B en los problemas de clase P se compensa exactamente con una disminución en el rendimiento en los problemas de clase Q, y viceversa.
Podemos expresar esta idea utilizando el concepto de valor esperado.
Entonces, el valor esperado de una función f con respecto a la distribución D se define como:
donde la integral se toma sobre todo el espacio de entrada X.
En otras palabras, el valor esperado de una función f es el valor promedio que f toma sobre todas las posibles entradas, ponderado por su probabilidad de ocurrencia.
También significa que la búsqueda de un algoritmo óptimo universal es inútil.
la mejor solución encontrada por el algoritmo A en los problemas de la clase P, y
la mejor solución encontrada por el algoritmo B en los problemas de la clase Q.
Esto significa que, independientemente de lo bien que se desempeñe un algoritmo A en los problemas de la clase P, siempre existe alguna distribución de problemas sobre P y Q tal que el algoritmo B tenga un desempeño igualmente bueno en promedio.