# Does overfitting imply an upper bound on model size/complexity?

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).

• 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? – Neil Slater Oct 21 '18 at 13:33
• What exactly you mean by less complex? – DuttaA Oct 21 '18 at 14:03
• @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? – Shehryar Malik Oct 22 '18 at 8:49
• @DuttaA for now I am using the term complexity quite loosely. Here I mean the size of the model/number of parameters it has. – Shehryar Malik Oct 22 '18 at 8:52

Still, we can't conclude, "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$$." Counter examples can probably be constructed with a little thought and effort.