how to make sense of the number of observations per parameters in deep learning models?

Question

In a simple linear regression setting, it is common to talk about a minimum number of observations per parameter (which characterise the the degree of freedom). And it is easy to see that for multiple regression, there is a one to one correspondence between the features and the parameters. So, we can directly compare the number of observations to the number of parameters.

However the VGG model for instance has 138M parameters and is trained on 1.2M images giving a ratio of about 1/100 for observations/parameters. Clearly, the rule of thumb ratio of anywhere between 10/1 to 30/1 is not respected here.

My understanding of this problem is that most of the parameters are in the fully connected layers and they share the information from all the pixels for each images, so that there is no "1 to 1" correspondence between observations and parameters?

Answer 1

In a classical machine learning (i.e. statistical learning theory) setup, the number of parameters usually enters via the Vapnik–Chervonenkis (VC) dimension and the number of observations via the PAC bound. Very roughly speaking, this says that for classification problems, the worst-case difference in 0-1 loss between training and test set is of the order $\sqrt{D/N}$ with $N$ number of observations and $D$ the VC dimension. Usually, the VC dimension increases in the number of parameters (how exactly depends on the model class). This result can be generalized beyond the binary classification setting. For neural networks, a quick Google scholar search gives for example Size-Independent Sample Complexity of Neural Networks.

More recent results support the idea that as the number of parameters passes a threshold of perfect (over)fitting, the test error decreases again since a model with more parameters is more expressive and able to fit the data using smoother functions. This is probably what is happening in your example. See for example Reconciling modern machine learning and the bias-variance trade-off or Generalization in Machine Learning via Analytical Learning Theory

Answer 2

so essentially the answer is regularisation. for NNs this is stopped training (ie initialise weights near zero and stop when you reach minimum in validation error, before you reach minimum on training error), drop out (randomly disable parts of the network) and weight regularisation (l2).

even in the linear case, lasso (l1 regularisation) has been used for n<

and for ridge regression (l2 regularisation) you have the notion of effective degrees of freedom Effective degrees of freedom for regularized regression

Although you are right that the majority of params are in the fully connected layer, and pooling etc reduce the effective input dimension, the number of parameters in the fully connected layer is still an important quantity, as it regulates the nonlinearity. (cf 1-d polynomial regression)

Answer 3

For any estimation problem, one would typically require the parameters of the statistical model to be identifiable. The one-to-one correspondence between number of observations and number of parameters actually comes from inspecting whenever the Information Matrix is singular or not. If the information matrix is non-singular for all possible parameter values, then broadly speaking, you can find unique values to the parameters of the model given your observations. The information matrix can for the Gaussian distribution, which is equivalent to least square fitting with known covariance, be written as $$ I(\theta) = J^T(\theta) Q^{-1} J(\theta) $$ and if the Jacobian $J$ has more columns than rows, that is, more parameters than observations, $I$ will be singular for all values of $\theta$.

However, if you have an estimation problem with more parameters than observations, you typically need to constrain the space of allowable values of the parameters, which can be done with regularization. All of this is described more in detail here.