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.

The authors consider the parameter recovery problem that the data are generated from a teacher network''. The goal is to learn the network from the generated data which are from Gaussian distribution and labeled by the teacher network'' with some white noises. A simple algorithm is proposed to learn the ground-truth parameters of a non-overlapping CNN, which is shown to converge efficiently with high probability with a small sample complexity bound. Due to the good properties of Gaussian inputs, the expectation of each update lies in the span of w t and w * (v t and v * as well). Also, with some properties of a specific good set'', as long as we haven't yet achieved optimality, the gradient in each step would be large enough and get closer to w *.

The paper studies the parameter recovery problem in the teacher-student setting for a network with a single hidden layer under the assumption of Gaussian inputs and non-overlapping filters. It proposes a modified training algorithm, shows convergence, and derives sample complexity bounds. All the reviewers appreciated that the contribution is important and the paper is well written. The main concern raised by two reviewers is that the assumptions of Gaussian inputs and non-overlapping filters are very strong, especially considering prior work of Goel et al. has established recovery guarantees for symmetric distributions with a slightly worse sample complexity. Even considering these concerns, which the authors should addressed in the final version, the reviewers still feel the paper is above the bar for acceptance.

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.

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.