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

CC BY-SA 4.0
2018-10-21T13:33:35.513Z
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
CC BY-SA 4.0
2018-10-22T08:49:59.183Z
@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
CC BY-SA 4.0
2018-10-22T08:52:04.157Z
@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
<machine-learning><overfitting>
Does overfitting imply an upper bound on model size/complexity?
Shehryar Malik
# Does overfitting imply an upper bound on model size/complexity?

(Asked by: username_0 on 2018-10-21)

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

**Tags:** machine-learning, overfitting

> **Comments:**
> **username_1**: 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?  
> **username_0**: @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?  
> **username_0**: @DuttaA for now I am using the term complexity quite loosely. Here I mean the size of the model/number of parameters it has.  

---

## 0 answers

