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.

本文研究了卷积神经网络和循环神经网络的样本复杂度，发现其样本复杂度随内在维度线性增长，但远小于全连接神经网络。研究方法包括本地经验分析和新的技术引理，希望能激发进一步理解卷积神经网络和循环神经网络的发展。