The VC-dimension formula for neural networks ranges from $O(E)$ to $O(E^2)$, with $O(E^2V^2)$ in the worst case, where $E$ is the number of edges and $V$ is the number of nodes. The number of training samples needed to have a strong guarantee of generalization is linear with the VC-dimension.This means that for a network with billions of edges, as in the case of successful deep learning models, the training dataset needs billions of training samples in the best case, to quadrillions in the worst case. The largest training sets currently have about a hundred billion samples.  Since there is not enough training data, it is unlikely deep learning models are generalizing. Instead, they are overfitting the training data.  This means the models will not perform well on data that is dissimilar to the training data, which is an undesirable property for machine learning.Given the inability of deep learning to generalize, according to VC dimensional analysis, why are deep learning results so hyped? Merely having a high accuracy on some dataset does not mean much in itself. Is there something special about deep learning architectures that reduces the VC-dimension significantly?If you do not think the VC-dimension analysis is relevant, please provide evidence/explanation that deep learning is generalizing and is not overfitting. I.e. does it have good recall AND precision, or just good recall? 100% recall is trivial to achieve, as is 100% precision. Getting both close to 100% is very difficult.As a contrary example, here is evidence that deep learning is overfitting. An overfit model is easy to fool since it has incorporated deterministic/stochastic noise. See the following image for an example of overfitting.Also, see lower ranked answers to this question to understand the problems with an overfit model despite good accuracy on test data.Some have responded that regularization solves the problem of a large VC dimension.  See this question for further discussion.
Why is deep learning hyped despite bad VC dimension?
machine learning;vc dimension
If the map and the terrain disagree, trust the terrain.It's not really understood why deep learning works as well as it does, but certainly old concepts from learning theory such as VC dimensions appear not to be very helpful. The matter is hotly debated, see e.g.:H. W. Lin, M. Tegmark, D. Rolnick, Why does deep and cheap learning work so well?C. Zhang, S. Bengio, M. Hardt, B. Recht, O. Vinyals, Understanding Deep Learning Requires Rethinking Generalization.D. Krueger, B. Ballas, S. Jastrzebski, D. Arpit, M. S. Kanwal, T. Maharaj, E. Bengio, A. Fischer, A. Courville, Deep Nets Dont Learn Via Memorization.Regarding the issue of adversarial examples, the problem was discovered in:C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, A. Rabinovich, Going deeper with convolutions.It is further developed in: I. Goodfellow, J. Shlens, C. Szegedy, Explaining And Harnessing Adversarial Examples.There is a lot of follow-on work.