Tight Sample Complexity of Learning One-hidden-layer Convolutional Neural Networks
Tight Sample Complexity of Learning One-hidden-layer Convolutional Neural Networks
复制标题
DOI：
--
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Yuan Cao;Quanquan Gu
中科院分区：
文献类型：
--
作者：
Yuan Cao;Quanquan Gu
研究了非重叠滤波器下学习单隐层卷积神经网络的样本复杂度。我们提出了一种称为近似梯度下降的新算法用于训练cnn，并表明，在高概率下，该算法具有随机初始化，使基本真值参数线性收敛，达到统计精度。与已有的工作相比，我们的结果适用于一般的非平凡、单调和Lipschitz连续激活函数，包括ReLU、Leaky ReLU、Sigmod和Softplus等。此外，在隐藏节点数量和过滤器大小的依赖性方面，我们的样本复杂性优于现有的结果。事实上，我们的结果与使用线性激活函数学习单隐层cnn的信息论下界相匹配，表明我们的样本复杂度很紧。我们的理论分析得到了数值实验的支持。
We study the sample complexity of learning one-hidden-layer convolutional neural networks (CNNs) with non-overlapping filters. We propose a novel algorithm called approximate gradient descent for training CNNs, and show that, with high probability, the proposed algorithm with random initialization grants a linear convergence to the ground-truth parameters up to statistical precision. Compared with existing work, our result applies to general non-trivial, monotonic and Lipschitz continuous activation functions including ReLU, Leaky ReLU, Sigmod and Softplus etc. Moreover, our sample complexity beats existing results in the dependency of the number of hidden nodes and filter size. In fact, our result matches the information-theoretic lower bound for learning one-hidden-layer CNNs with linear activation functions, suggesting that our sample complexity is tight. Our theoretical analysis is backed up by numerical experiments.