Toward a Justification of Meta-Learning: Is the No Free Lunch Theorem a Show-Stopper?

We present a preliminary analysis of the fundamental viability of meta-learning, revisiting the No Free Lunch (NFL) theorem.  The analysis shows that given some simple and very basic assumptions, the NFL theorem is of little relevance to research in Machine Learning.  We augment the basic NFL framework to illustrate that the notion of an Ultimate Learning Algorithm is well defined.  We show that, although cross-validation still is not a viable way to construct general-purpose learning algorithms, meta-learning offers a natural alternative.  We still have to pay for our lunch, but the cost is reasonable: the necessary fundamental assumptions are ones we all make anyway.