# 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? – user9947 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

## 1 Answer

over-fitting does seem to imply an upper bound on model complexity.

As complexity of the model increases, its generality tends to decrease. This is not an indisputable fact, but an identifiable trend, provided that the model is not inundated with redundancy.

For polynomial expressions, a Taylor series of 100 terms can always perfectly represent the position of 100 points in a time series, although no predictive general information can be ascertained from the 100 coefficients of the Taylor series. This is also true for spectral analysis, Lyapunov exponent estimation, spline fitting, or artificial network convergence.

What is generally accepted as the definition of over-fitting does not come from the AI field. It originates from the mathematics of surface approximation using closed forms. The closed forms may be derived from a single differential equation or systems of them, but not usually, since closed forms do not exist for many such systems.

The information science principles behind feature extraction are closely aligned to the correlation between generality and predictive usefulness.

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.