Suppose that I have a model M that overfits a large dataset S such that the test error is 30%. Does that mean that there will always exist a model that is smaller and less complex than M that will have a test error less than 30% on S (and does not overfit S).

  • 2
    $\begingroup$ If you want to discuss theoretical bounds, you should probably define a few more terms. Such as relative size of test and train sets, what counts as over-fitting in numerical terms (100% accuracy on training data - or something else?) If overfitting is 100%, the training and test data are drawn from the same distribution and test set is smaller, then you should be able to construct a smaller model which 100% fits the test data - such a model probably exists, but it would be very unlikely to be reachable by training on the training data. That seems trivial - is it what you are looking for? $\endgroup$ Oct 21 '18 at 13:33
  • $\begingroup$ What exactly you mean by less complex? $\endgroup$
    – user9947
    Oct 21 '18 at 14:03
  • $\begingroup$ @NeilSlater for now I only wanted an intuitive explanation. But it would be interesting to have some sort of theoretical bound. Could you point me to some resources that discuss these theoretical bounds? $\endgroup$ Oct 22 '18 at 8:49
  • $\begingroup$ @DuttaA for now I am using the term complexity quite loosely. Here I mean the size of the model/number of parameters it has. $\endgroup$ Oct 22 '18 at 8:52

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.