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!
 A: The way I understand the NFL theorem is that there is no learning algorithm that's better than the rest in every task. This isn't however a theorem in the clear mathematical sense that it has a proof, rather an empirical observation.
Similar to what you said for the kNN, there is also the Universal Approximation Theorem for Neural Networks, which states that given a 2-layer neural network, we can approximate any function with any arbitrary error.
Now, how does this not break the NFL? It basically states that you can solve any conceivable problem with a simple 2-layer NN. The reason is that while, theoretically NNs can approximate anything, in practice its very hard to teach them to approximate anything. That's why for some tasks, other algorithms are preferable.
A more practical way to interpret NFL is the following:

There is no way of determine a-priori which algorithm will do best for a given task.

A: The answer to this question is already in the text of the question: "Assume $\mu$ has a density", which means the statement is only valid when the distribution $\mu(X,Y)$ is absolutely continuous. Hence NFL does not apply here.
To expand on this point, NFL theorem says that (see eg. 7.2 in Devroye book): "given any classification rule, there exists a distribution such that the excess risk is large." Intuitively, NFL implies that inductive bias is unavoidable and any consistency result regarding the performance of a classifier must be accompanied with certain assumptions on the distribution of data. These assumptions are required to exclude those "bad" distributions that result in large excess risk.
All consistency results for local averaging methods (histogram, k-NN, kernel) require absolute continuity of distribution of $(X,Y)$. Sometimes this assumption is stated in terms of continuity of the posterior probability function $\eta(x) = \mathbb{Pr}(Y=1\mid X)$. Such restrictions are very much necessary, since a local averaging method relies on labels varying "smoothly" within the feature space. In other words, two data points that are close with respect to some distance metric should have labels that are also close with high probability.
Local averaging methods, such as nearest-neighbor, utilize the neighborhood of a test point to make a decision about its label. Therefore, a bad distribution for k-NN would be one where the conditional distribution function $\eta(X)$ is very rough and the labels of the neighbors are no longer useful. The NFL theorem is about the existence of such bad distributions, while consistency results are specialized to avoid such bad distributions.
