We propose a new algorithm to learn a one-hidden-layer convolutional neural network where both the convolutional weights and the outputs weights are parameters to be learned. Our algorithm works for a general class of (potentially overlapping) patches, including commonly used structures for computer vision tasks. Our algorithm draws ideas from (1) isotonic regression for learning neural networks and (2) landscape analysis of non-convex matrix factorization problems. We believe these findings may inspire further development in designing provable algorithms for learning neural networks and other complex models. While our focus is theoretical, we also present experiments that illustrate our theoretical findings.
This paper gives a new algorithm for learning a two layer neural network which involves a single convolutional filter and a weight vector for different locations. The algorithm works on any symmetric input data. The techniques in this paper combines two previous approaches: 1. the algorithm Convotron for learning a single convolutional filter (while the second layer has fixed weight) on any symmetric input distributions; 2. non-convex optimization for low rank matrix factorization.
The main observation in the paper is that if the overlap in the convolutions is not large (in the sense that each location of the convolution has at least one input coordinate that is not used in any other locations), then the weight that corresponds to the non-overlapping part and the weights in the second layer can be computed by a matrix factorization step (the paper gives a way to estimate a gradient that is similar to the gradient for a linear neural network, and then the problem is very similar to a rank-1 matrix factorization). After this step, we know the second layer and the algorithm can generalize the previous Convotron algorithm to learn the full convolutional filter.
This is an interesting observation that allows the algorithm to learn a two-layer neural network. On the other hand this two layer neural network is still a bit limited as there is still only one convolutional filter, and in particular there is only one local and global optimum (up to scaling the two layers). The observation also limited how much the patches can overlap which was not a problem in the original convotron algorithm. 
Overall I feel the paper is interesting but a bit incremental.