Answers.Body: <p>Ok so after a little more reading, I am currently satisfy with what I found for this question.</p>
  
  <ul>
  <li>Yes, the "under-parameterized" and "over-parameterized" terms do not currently have a widely accepted definitions.</li>
  <li>Any definition for those term should consider the input data domain as well as the architecture and training procedure.</li>
  </ul>
  
  <p>In a recent paper <a href="https://openai.com/blog/deep-double-descent" rel="nofollow noreferrer">Deep Double Descent</a> from OpenAI Nakkiran et. al 2019, the authors tried to formalized and generalized the concept of "interpolation threshold" in the "double descent" phenomenon, both terms popularized by Belkin et. al 2019 <a href="https://arxiv.org/abs/1812.11118" rel="nofollow noreferrer">Reconciling modern Machine Learning practices with the Bias-Variance Tradeoff</a>.</p>
  
  <p>In the Deep Double Descent paper, they define a concept called "Effective Model Complexity (EMC)", which include model architecture, training procedure and data to describe the "interpolation threshold" (the moment at which model can fit near perfect the training data). </p>
  
  <p>EMC below the interpolation threshold is considered "under-parameterized" and above interpolation threshold is considered "over-parameterized".</p>
  
  <p>So according to this definition of EMC, I suppose:</p>
  
  <blockquote>
    <p>1M-parameters model on 10M samples of 2 binary features, then it should not be over-parameterized</p>
  </blockquote>
  
  <p>is over-parameterized because of the simplicity of input data.</p>
  
  <blockquote>
    <p>1M-parameters model on 0.1M samples of 512x512 images, then is over-parameterized, or</p>
  </blockquote>
  
  <p>is probably not parameterized, if it cannot fit the training data with near 0 loss.</p>
  
  <blockquote>
    <p>the model in the paper Exploring the Limits of Weakly Supervised Pretraining "IG-940M-1.5k ResNeXt-101 32×48d" with 829M parameters, trained on 1B Instagram images, is not over-parameterized </p>
  </blockquote>
  
  <p>is not over parameterized because it cannot fit the entire training data perfectly.</p>
  
  <p>I am curious to see if EMC will catch on and be a popular measure for model complexity in the future.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-16T16:22:38.053Z
Answers.LastActivityDate: 2019-12-16T16:22:38.053Z
Answers.UserDisplayName: Phúc Lê
Body: <p>When exactly is a model considered over-parameterized?</p>
  <p>There are some recent researches in Deep Learning about the role of over-parameterization toward generalization, so it would be nice if I can know what exactly can be considered as such.</p>
  <p>A hand-wavy definition is: over-parameterized model is often used to described when you have a model bigger than necessary to fit your data.</p>
  <p>In some papers (for example, in <a href="https://arxiv.org/pdf/1811.03962.pdf" rel="nofollow noreferrer">A Convergence Theory for Deep Learning
  via Over-Parameterization</a>), over-parameterization is described as:</p>
  <blockquote>
  <p>they have much more parameters than the number of training samples</p>
  <p>meaning that the number of neurons is polynomially large comparing to the input size</p>
  <p>the network width is sufficiently large: polynomial in <span class="math-container">$L$</span>, the number of layers, and in <span class="math-container">$n$</span>, the number of samples</p>
  </blockquote>
  <p>Shouldn't this definition depend on the type of input data as well?</p>
  <p>For example, I fit:</p>
  <ul>
  <li><p>1M-parameters model on 10M samples of 2 binary features, then it should not be over-parameterized, or</p>
  </li>
  <li><p>1M-parameters model on 0.1M samples of 512x512 images, then is over-parameterized, or</p>
  </li>
  <li><p>the model in the paper <a href="https://research.fb.com/wp-content/uploads/2018/05/exploring_the_limits_of_weakly_supervised_pretraining.pdf" rel="nofollow noreferrer">Exploring the Limits of
  Weakly Supervised Pretraining</a> &quot;IG-940M-1.5k ResNeXt-101 32×48d&quot; with 829M parameters, trained on 1B Instagram images, is not over-parameterized</p>
  </li>
  </ul>
  
Tags: <deep-learning><definitions><convergence><generalization>
Title: When exactly is a model considered over-parameterized?
UserDisplayName: Phúc Lê
ThreadText: # When exactly is a model considered over-parameterized?
  
  (Asked by: username_0 on 2019-12-13)
  
  When exactly is a model considered over-parameterized?
  
  There are some recent researches in Deep Learning about the role of over-parameterization toward generalization, so it would be nice if I can know what exactly can be considered as such.
  
  A hand-wavy definition is: over-parameterized model is often used to described when you have a model bigger than necessary to fit your data.
  
  In some papers (for example, in [A Convergence Theory for Deep Learning
  via Over-Parameterization](https://arxiv.org/pdf/1811.03962.pdf)), over-parameterization is described as:
  
  > they have much more parameters than the number of training samples
  >
  > meaning that the number of neurons is polynomially large comparing to the input size
  >
  > the network width is sufficiently large: polynomial in $L$, the number of layers, and in $n$, the number of samples
  
  Shouldn't this definition depend on the type of input data as well?
  
  For example, I fit:
  
  * 1M-parameters model on 10M samples of 2 binary features, then it should not be over-parameterized, or
  * 1M-parameters model on 0.1M samples of 512x512 images, then is over-parameterized, or
  * the model in the paper [Exploring the Limits of
    Weakly Supervised Pretraining](https://research.fb.com/wp-content/uploads/2018/05/exploring_the_limits_of_weakly_supervised_pretraining.pdf) "IG-940M-1.5k ResNeXt-101 32×48d" with 829M parameters, trained on 1B Instagram images, is not over-parameterized
  
  **Tags:** deep-learning, definitions, convergence, generalization
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2019-12-16. Score: 2
  
  Ok so after a little more reading, I am currently satisfy with what I found for this question.
  
  * Yes, the "under-parameterized" and "over-parameterized" terms do not currently have a widely accepted definitions.
  * Any definition for those term should consider the input data domain as well as the architecture and training procedure.
  
  In a recent paper [Deep Double Descent](https://openai.com/blog/deep-double-descent) from OpenAI Nakkiran et. al 2019, the authors tried to formalized and generalized the concept of "interpolation threshold" in the "double descent" phenomenon, both terms popularized by Belkin et. al 2019 [Reconciling modern Machine Learning practices with the Bias-Variance Tradeoff](https://arxiv.org/abs/1812.11118).
  
  In the Deep Double Descent paper, they define a concept called "Effective Model Complexity (EMC)", which include model architecture, training procedure and data to describe the "interpolation threshold" (the moment at which model can fit near perfect the training data).
  
  EMC below the interpolation threshold is considered "under-parameterized" and above interpolation threshold is considered "over-parameterized".
  
  So according to this definition of EMC, I suppose:
  
  > 1M-parameters model on 10M samples of 2 binary features, then it should not be over-parameterized
  
  is over-parameterized because of the simplicity of input data.
  
  > 1M-parameters model on 0.1M samples of 512x512 images, then is over-parameterized, or
  
  is probably not parameterized, if it cannot fit the training data with near 0 loss.
  
  > the model in the paper Exploring the Limits of Weakly Supervised Pretraining "IG-940M-1.5k ResNeXt-101 32×48d" with 829M parameters, trained on 1B Instagram images, is not over-parameterized
  
  is not over parameterized because it cannot fit the entire training data perfectly.
  
  I am curious to see if EMC will catch on and be a popular measure for model complexity in the future.
  
  
  ---
  
  