The Universal Approximation Theorem vs. The No Free Lunch Theorem: What's the caveat?

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?

• The first theorem does not imply that NNets are the "one learning approach to rule them all". There are other functions that can approximate any continuous function on compact subsets of $R^n$, see the Stone-Weierstrass theorem for example, and then there's the issue of generalizability, which the UAT does not address. – jbowman Oct 4 '18 at 17:08
• Stone-Weierstrass theorem - means polynomial linear regression also satisfies UAT – seanv507 Oct 4 '18 at 17:22

• While what you're saying is correct in terms of traininggeneralization, I don't think it correctly addresses the question. The NFL theorem has nothing to do with generalization. Rather it says that if you sample functions from a uniform distribution of the input/output space, then the overall expected cost of any algorithm will be the same at iteration step $m$. – Alex R. Oct 4 '18 at 17:09