Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-10-21T13:33:35.513Z
Comments.Text: 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?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-10-22T08:49:59.183Z
Comments.Text: @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?
Comments.UserDisplayName: Shehryar Malik
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-10-22T08:52:04.157Z
Comments.Text: @DuttaA for now I am using the term complexity quite loosely. Here I mean the size of the model/number of parameters it has.
Comments.UserDisplayName: Shehryar Malik
Tags: <machine-learning><overfitting>
Title: Does overfitting imply an upper bound on model size/complexity?
UserDisplayName: Shehryar Malik
ThreadText: # 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
  
  