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