# The No-Free-Lunch Theorem and K-NN consistency

In computational learning, The NFL theorem states that there is no universal learner. For every learning algorithm , there is a distribution that causes the learner output a hypotesis with a large error, with high probability (although there is a low error hypotesis). The conclusion is that in order to learn, the hypotesis class or the distributions must be restricted. In their book "A probabilistic theory of pattern recognition", Devroye et al prove the following theroem for the K-nearest neighbors learner: $$\text{Assume } \mu \text{ has a density. if } k\to \infty \text{ and } k/n\to0 \\ \text{ then for every } \epsilon>0, \text{ there's } N, \text{ s.t.} \text{ for all } n>N : \\ P(R_n - R^* > \epsilon)< 2exp(-C_dn \epsilon ^{2})$$ Where $$R^*$$ is the error of the bayes-optimal rule, $$R_n$$ is the true error of the K-NN output (the probability is over the training set of size $$n$$), $$\mu$$ is the probability measure on the instance space $$\mathbb{R}^d$$ and $$C_d$$ is some constant depends only on the euclidean dimension. Therefore, we can get as close as we want to the best hypothesis there is (not the best in some restricted class), without making any assumption on the ditribution. So I'm trying to understand how this result does not contradict the NFL theroem? thanks!