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?

  • $\begingroup$ This question seems clear enough to me. $\endgroup$ – gung - Reinstate Monica Jul 22 '16 at 12:23
  • $\begingroup$ @gung are you referring to something? $\endgroup$ – VF1 Nov 2 '16 at 1:33
  • $\begingroup$ This question was presumably voted to close as unclear, @VFI. I must have voted to leave open & left a comment. It might help to tend to this question more often than every 3 months, though. $\endgroup$ – gung - Reinstate Monica Nov 2 '16 at 1:36

This is still an open question, and it doesn't look like I'll be getting an answer soon. Again, the discussion here mentions all relevant points and a couple high-level papers, but a cogent reply to this question simply doesn't exist right now.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.