Is Deeper Better Only When Shallow Is Good?
summary
Claim: fractal-shaped classification problems can be represented exactly by a ReLU net of depth 2n+1 and width about 5d·r, while any network much shallower needs exponential width r^n (counting linear regions). For a one-dimensional Cantor-style distribution the paper proves gradient at random initialization has magnitude ~1/2 - p_j (with high probability), so gradient-based training stalls when the approximation curve p_j stays near 1/2. Empirics on 2D fractals and CIFAR show deeper nets help but shallow nets often achieve nontrivial accuracy.
AI-written summary · about
chapters (14)
- 0:00Introduction to the puzzle
- 1:47Depth separation hypothesis
- 3:51Fractal distributions
- 6:47IFS and fractal sets
- 9:35Deep network expressivity
- 11:45Proof of deep representation
- 15:33Shallow network limitations
- 18:55Approximation curve concept
- 22:33Failure of gradient descent
- 26:22Gradient magnitude analysis
- 29:42Conjecture on general failure
- 33:37Empirical evidence
- 36:13Implications for deep learning
- 39:44Conclusion and Q&A
related talks
01h 51mUnderstanding Neural Networks (Somewhat)
59mTutorial: Statistical Learning Theory and Neural Networks I
33mProvably Efficient Algorithms for Training Deep Networks
58mFeature Selection with Gradient Descent on Two-layer Networks in Low-rotation Regimes
01h 04mRandomized Embeddings and Neural Networks
01h 03mUnderstanding ReLU Networks Through Graph Problems and Polyhedra
32mTight Hardness Results for Training Depth-2 ReLU Networks
01h 14mApproximation Power