# How Many Samples are Needed to Estimate a Convolutional or Recurrent Neural Network?

arXiv: https://arxiv.org/abs/1805.07883 · HTML: https://mlsanity.com/paper/1805.07883/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 May 2018.

## Built on by (most cited first, 19 of 19)

- [ResMLP: Feedforward networks for image classification with data-efficient training](https://mlsanity.com/paper/2105.03404/) (2021)
- [Approximation and Learning with Deep Convolutional Models: a Kernel Perspective](https://mlsanity.com/paper/2102.10032/) (2021)
- [The Exact Sample Complexity Gain from Invariances for Kernel Regression](https://mlsanity.com/paper/2303.14269/) (2023)
- [Theoretical Analysis of Inductive Biases in Deep Convolutional Networks](https://mlsanity.com/paper/2305.08404/) (2023)
- [On the Sample Complexity of Learning under Invariance and Geometric Stability](https://mlsanity.com/paper/2106.07148/) (2021)
- [The Sample Complexity of One-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.06233/) (2022)
- [Data-dependent Generalization Bounds via Variable-Size Compressibility](https://mlsanity.com/paper/2303.05369/) (2023)
- [Visualizing the Emergence of Intermediate Visual Patterns in DNNs](https://mlsanity.com/paper/2111.03505/) (2021)
- [Norm-based Generalization Bounds for Compositionally Sparse Neural Networks](https://mlsanity.com/paper/2301.12033/) (2023)
- [Role of Locality and Weight Sharing in Image-Based Tasks: A Sample Complexity Separation between CNNs, LCNs, and FCNs](https://mlsanity.com/paper/2403.15707/) (2024)
- [How many samples are needed to train a deep neural network?](https://mlsanity.com/paper/2405.16696/) (2024)
- [Graph CNN for Moving Object Detection in Complex Environments from Unseen Videos](https://mlsanity.com/paper/2207.06440/) (2022)
- [One-pass Stochastic Gradient Descent in Overparametrized Two-layer Neural Networks](https://mlsanity.com/paper/2105.00262/) (2021)
- [The Geometry of Polynomial Group Convolutional Neural Networks](https://mlsanity.com/paper/2603.29566/) (2026)
- [A New Measure of Model Redundancy for Compressed Convolutional Neural Networks](https://mlsanity.com/paper/2112.04857/) (2021)
- [A Sparse Coding Interpretation of Neural Networks and Theoretical Implications](https://mlsanity.com/paper/2108.06622/) (2021)
- [Training Patch Analysis and Mining Skills for Image Restoration Deep Neural Networks](https://mlsanity.com/paper/2207.01075/) (2022)
- [SynDaCaTE: A Synthetic Dataset For Evaluating Part-Whole Hierarchical Inference](https://mlsanity.com/paper/2506.17558/) (2025)
- [Towards High-Fidelity Gaussian Splatting with Queried-Convolution Neural Networks](https://mlsanity.com/paper/2512.12898/) (2025)

## Abstract (arXiv)

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.