Sample-complexity of Estimating Convolutional and Recurrent Neural Networks
summary
Claims minimax sample complexity: two‑layer linear CNN with average pooling needs about M/N rate samples (filter size M), weighted pooling needs (M+J)/N, and linear RNN needs about RD/N (hidden dim R, input dim D); bounds assume a realizable linear generative model, isotropic sub‑Gaussian inputs, sub‑Gaussian noise, and use the least squares estimator, Dudley/covering arguments and restricted‑eigenvalue type tools; synthetic gradient‑descent experiments match the predicted scalings but the analysis ignores optimization/algorithmic issues.
AI-written summary · about
chapters (13)
- 0:00Intro
- 3:27FNN, CNN and RNN architectures
- 5:24CNN generative models
- 9:51Minimax analysis
- 12:18Estimator and Assumptions
- 14:28Main results (Informal)
- 16:47Related work
- 20:18Upper bounds (formal)
- 23:05Proof sketch
- 27:33Lower bounds (formal)
- 28:11Experiments - CNN (average pooling) vs FNN
- 28:58Experiments - CNN (weighted pooling) vs FNN
- 30:03Open questions
related talks
59mTutorial: Statistical Learning Theory and Neural Networks I
01h 04mRandomized Embeddings and Neural Networks
01h 01mMapping multisets to vectors
19mTraining (Overparametrized) Neural Networks in Near-Linear Time
01h 00mA Theoretical Framework of Convolutional Kernels on Image Datasets
45mNoisy Estimation of Simultaneously Structured Models
17mUniversality of Neural Networks
36mRepresentation Costs of Linear Neural Networks: Analysis and Design