Depth efficiency is an accepted result about neural networks that says the expressiveness of a network with additional layers can only be matched by a shallow network with exponentially many more nodes.
I fail to see how this is consistent with statistical learning. How does the fact that we can be more expressive with fewer units help? Perhaps this helps computational efficiency (though even this is tenuous, shallow architectures are more parallelizable), but don't we still need exponentially more data to compensate for the increase in VC dimension?
Update: the fact that we don't need exponentially more data to handle increases in VC dimension is an open question, and it's a proposition that holds up in practice, which actually is an indication that distribution-free statistical learning analysis may be insufficient for deep learning (see this post for related discussion). Nonetheless, the question still stands: if depth increases expressiveness exponentially, then how does empirical risk minimization (even local minimization) remain tractable?