When exactly is a model considered over-parameterized?

Question

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), 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 "IG-940M-1.5k ResNeXt-101 32×48d" with 829M parameters, trained on 1B Instagram images, is not over-parameterized

Answer 1

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

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.