When exactly is a model considered over-parameterized?
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.