What makes deep learning model complexity so different that conventional measures are not sufficient? Currently, there are some efforts to define a complexity measure for deep learning models. Such as topological, spectral ergodic, see in-depth recent survey.
What makes deep learning model complexity so different that conventional measures are not sufficient? Conventional in the sense that we would use for model selection, AIC or BIC. In other words, Are AIC or BIC not good enough for overparameterized models?
 A: Take as an example the simple neural network diagram from Wikipedia. Each arrow on the diagram shows the weight of the model, biases are not shown.

With the simple model as linear regression to judge its complexity, you would just count the parameters. Here notice that the parameters on the second layer depend on the parameters of the first layer. How should we count them? Adding the number of parameters from the first layer to the ones on the second layer wouldn't account for the dependence between them. Maybe we should instead multiply the number of parameters on the first layer by the number of parameters on the second layer? How would we treat the bias terms?
If we used linear activations, we would be de facto multiplying the parameters by each other, what illustrates to what degree they depend on one another. In such a case, the parameters collapse and the effective number of parameters would be smaller than the count of parameters on all the layers. Considering this, how exactly using non-linear activations should affect our counting?
What should we do with parts of the model that don't have parameters, for example, you could use residual connections where you would multiply the output of the layer by its inputs—would we say that such network is equally complex as the one without the residual connections?
As you can see, it is not obvious how should we count the parameters and how should we account for the parts of the model that don’t have parameters.
A: I want to preface this by saying that I am not an expert in this area but I did read some related articles a while back.
I think a reason that classical techniques like AIC does not work for neural networks is due to the symmetry of the weight space. If I recall correctly then AIC is based on the fact that the in the limit of infinite data the MLE will converge to a specific parameter setting, but in neural networks you have symmetries so that different parameter configurations can in fact model the exact same function. An example of this symmetry is if you have a network with ReLU activation functions. In this case you can multiply the incoming weights and bias for a neuron with a factor 1/k where k>0 and the outgoing weights from that same neuron with k and the function will remain identical. So the MLE cannot converge to a single parameter setting in the limit and the AIC theory will not hold.
Another reason that classical techniques does not apply is that the large modern networks can memorize the data even when the labels are random as shown in "Understanding deep learning requires rethinking generalization". This means that classical measures like Rademachers does not yield that much information.
