How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?
arXiv:1805.07883
Abstract
It is widely believed that the practical success of Convolutional Neural Networks (CNNs) and Recurrent Neural Networks (RNNs) owes to the fact that CNNs and RNNs use a more compact parametric representation than their Fully-Connected Neural Network (FNN) counterparts, and consequently require fewer training examples to accurately estimate their parameters. We initiate the study of rigorously characterizing the sample-complexity of estimating CNNs and RNNs. We show that the sample-complexity to learn CNNs and RNNs scales linearly with their intrinsic dimension and this sample-complexity is much smaller than for their FNN counterparts. For both CNNs and RNNs, we also present lower bounds showing our sample complexities are tight up to logarithmic factors. Our main technical tools for deriving these results are a localized empirical process analysis and a new technical lemma characterizing the convolutional and recurrent structure. We believe that these tools may inspire further developments in understanding CNNs and RNNs.
arXiv commentRevised version, with new results on recurrent neural networks. Preliminary version in NeurIPS 2018
References in corpus (29)
- Simultaneous analysis of Lasso and Dantzig selector
- The Loss Surfaces of Multilayer Networks
- A Convergence Theory for Deep Learning via Over-Parameterization
- QANet: Combining Local Convolution with Global Self-Attention for Reading Comprehension
- A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
- Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
- Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
- The loss surface of deep and wide neural networks
- Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
- On the Power of Over-parametrization in Neural Networks with Quadratic Activation
- Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
- Gradient Descent Learns Linear Dynamical Systems
- Recovery Guarantees for One-hidden-layer Neural Networks
- Global Optimality in Tensor Factorization, Deep Learning, and Beyond
- Stronger generalization bounds for deep nets via a compression approach
- Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
- Norm-Based Capacity Control in Neural Networks
- When is a Convolutional Filter Easy To Learn?
- Reliably Learning the ReLU in Polynomial Time
- Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
- Learning One Convolutional Layer with Overlapping Patches
- Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels
- Learning Neural Networks with Two Nonlinear Layers in Polynomial Time
- Learning Halfspaces and Neural Networks with Random Initialization
- Convolutional Phase Retrieval via Gradient Descent
- The Landscape of Deep Learning Algorithms
- Noise-adaptive Margin-based Active Learning and Lower Bounds under Tsybakov Noise Condition
- PAC-Bayesian Margin Bounds for Convolutional Neural Networks