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?

  • $\begingroup$ Which definition of the NFL theorem are you using? Which book, paper or source have you read or taken that definition from? $\endgroup$ – nbro Mar 26 at 13:51
  • 1
    $\begingroup$ @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/… $\endgroup$ – DuttaA Mar 26 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.