# When is there a free lunch?

The no free lunch theorem (NFL) states that

Theorem (Wolpert and Macready 1997) Let $A$ be any learning algorithm for the task of binary classification with respect to the $0−1$ loss over a domain $\chi$ . Let $m$ be any number smaller than $|X |/2$, representing a training set size. Then, there exists a distribution $D$ over $X \times \{0, 1\}$ such that:

1. There exists a function $f : X \rightarrow \{0, 1\}$ with $L_D(f) = 0$.
2. With probability of at least $1/7$ over the choice of $S \sim D^m$, we have that $L_D(A(S)) \geq 1/8$.

where $L_D$ is the error of the prediction rule.

I know some people in the ML community find the NFL theorem to be of questionable relevance as it seems to assume a uniform distribution over the class of all hypotheses $H = \{ f \text{ such that } f : X \rightarrow \{0, 1\} \}$, and in particular it includes adversarial problem classes.

So how bad is the problem raised by NFL? Or how plausible a structure can you put on $H$ before you get a free lunch?

Can you characterise the complexity required of $H$ required for no free lunch to hold? Or when do you get a free lunch?

• Have you read this? arxiv.org/pdf/1111.3846.pdf In general Hutter's papers are pretty much all on this topic. Some distributions over the hypothesis space give what he defines as "pareto optimality". Basically complex hypothesis should not have the same probability as simple ones. This is justified if you believe the universe is a very big computer and complex hypothesis are more resource intensive to compute. – Cagdas Ozgenc Feb 2 '18 at 7:05
• Thank you for the reference. I had looked at that paper although not in enough detail to fully understand the Solomonoff prior. From your outline I am not sure how plausible I find that assumption. Does he discuss Pareto optimality in that paper? I suppose I am really interested in the boundary between free lunch and no free lunch. I'll try to update the question to better reflect the contents of the paper. – MachineEpsilon Feb 4 '18 at 5:01
• Pareto optimality argument is in this paper: jmlr.org/papers/volume4/hutter03a/hutter03a.pdf – Cagdas Ozgenc Feb 4 '18 at 10:14