# Are No Free Lunch theorem and Universal Approximation theorem contradictory in the context of neural networks?

To my understanding NFL states that, we cannot have an hypothesis (let's assume it is an approximator like NN in this case) class that can't achieve certain accuracy parameters $$\leq \epsilon$$ with probability greater than a certain $$p$$ given the number of points from which we can sample is upper bounded to $$m$$.

Whereas, the UAC states that an approximator like a NN given enough hidden units can approximate any function (to my knowledge the function must be bounded).

The point where these 2 clashes (as per my knowledge) is that if we increase the paramters in a NN, the UAC will start to hold good, but the VC dimension will increase (or hypothesis class becomes richer) and for the same $$m$$ our $$\epsilon$$ increases or $$p$$ decreases (not sure which one is affected).

So what are the gaps in my knowledge here? How do we make these 2 consistent with each other?

• Which definition of the NFL theorem are you using? Which book, paper or source have you read or taken that definition from? – nbro Mar 26 at 13:51
• @nbro This is not the actual definition of NFL in truest sense, I have omitted a few details to make it look more informal. But you can find the formal definition here in my answer (UML by Shai Ben David and Shai shalev shwartz): ai.stackexchange.com/questions/17803/… – DuttaA Mar 26 at 14:02