Why is deep learning hyped despite bad VC dimension?
&quot;If the map and the terrain disagree, trust the terrain.&quot;
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.
Update March 2020. A new hypothesis that appears to explain some of the mismatch between clear over-parameterisation of modern (feed-forward) NNs and good recognition performance is Frankle and Carbin's Lottery Ticket Hypothesis from 2018:

J. Frankle, M. Carbin, The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks.

The claim is that a &quot;randomly-initialised, dense [feed-forward] neural
network contains a subnetwork that is initialised such that when
trained in isolation it can match the test accuracy of the original
network after training for at most the same number of iterations.&quot; Regarding the original question, the Lottery Ticket Hypothesis might be understood as saying that:

Training by stochastic gradient descent searches for small subnetworks that work well and deemphasises the rest of the overparameterised network's learning capacity.

The bigger the original network, the more likely it is to contain a small subnetwork with good performance on the task at hand.


This has found empirical support, e.g. in

H. Zhou, J. Lan, R. Liu, J. Yosinski, Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask.

and theoretical support in:

E. Malach, G. Yehudai, S. Shalev-Shwartz, O. Shamir, Proving the Lottery Ticket Hypothesis: Pruning is All You Need.

As far as I'm aware, it has not yet been possible to generalise the Lottery Ticket Hypothesis to recurrent NNs.
Update March 2021. The original 2016 paper Understanding Deep Learning Requires Rethinking Generalization has been updated. Here is the new version:
C. Zhang, S. Bengio, M. Hardt, B. Recht, O. Vinyals, Understanding Deep Learning (Still) Requires Rethinking Generalization.