The main issue is that the VC dimension of a deep network is very high (iirc it grows proportionally to the number of edges of the network, which grows combinat

The main issue is that the VC dimension of a deep network is very high (iirc it grows proportionally to the number of edges of the network, which grows combinatorically with its depth), and for any dataset smaller than that the network can just learn the dataset and achieve 100% accuracy. However regularizing the network usually solves that problem.