The universal approximation theorem:
A neural network with 3 layers and suitably chosen activation functions can any approximate continuous function on compact subsets of $R^n$.
The no free lunch theorem:
If a learning algorithm performs well on some data sets, it will perform poorly on some other data sets.
I sense a contradiction here: the first theorem implies that NNets are the "one learning approach to rule them all", while second says that such a learning approach doesn't exist.
I'm pretty certain NFLT holds, so there must be a caveat, but I can't put my finger on it?
What is the caveat in the universal approximation theorem so that NFLT holds?