# 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 to output a hypotesis with a large error, with high probability. 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{ if } n>N \quad P(R_n - R^* > \epsilon)< 2exp(-C_dn \epsilon ^{2})$$ Where $$R^*$$ is the error of the bayes-optimal decision, and $$R_n$$ is the true error of the K-NN output (the probability is over the training set of size $$n$$). $$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!