Provably Efficient Algorithms for Training Deep Networks
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Shows that extreme overspecification removes no local non-global minima: if hidden neurons ≥ number of examples and mild rank conditions hold, every local minimum is global. Gives a matching hardness: even when labels come from a depth‑2 network with few hidden units, no algorithm can guarantee low test error without extra assumptions. Replaces sigmoids by square activations to get an efficient greedy "Gecko" algorithm that learns depth‑2 polynomial networks with R^2 overspecification; deeper product networks remain hard. Proposes vanishing component analysis when classes lie on algebraic sets.
AI-written summary · about
chapters (10)
- 0:00Introduction to neural networks
- 1:52Statistical learning perspective
- 3:46Statistical versus computational barriers
- 8:39The hardness of training
- 10:20Strategies for learning networks
- 12:37The limits of over-specification
- 17:23Negative results and trade-offs
- 21:51Sum-product networks
- 28:05Distributional assumptions
- 30:43Conclusion and Q&A
related talks
01h 14mRecent Developments in Over-parametrized Neural Networks, Part I
01h 04mRandomized Embeddings and Neural Networks
46mOn the Foundations of Deep Learning: SGD, Overparametrization, and Generalization
01h 20mThe elusive generalization: classical bounds to double descent to grokking
50mLearning and Generalization in Over-parametrized Neural Networks, Going Beyond Kernels
20mFeature Learning: From Optimization to Modern Generalization
32mTight Hardness Results for Training Depth-2 ReLU Networks
44mRobust Estimation and Generative Adversarial Nets