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

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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.