Published as a conference paper at ICLR 2018 WHEN IS A CONVOLUTIONAL FILTER EASY TO LEARN?
We analyze the convergence of (stochastic) gradient descent algorithm for learning a convolutional filter with Rectified Linear Unit (ReLU) activation function. Our analysis does not rely on any specific form of the input distribution and our proofs only use the definition of ReLU, in contrast with previous works that are restricted to standard Gaussian input. We show that (stochastic) gradient descent with random initialization can learn the convolutional filter in polynomial time and the convergence rate depends on the smoothness of the input distribution and the closeness of patches. To the best of our knowledge, this is the first recovery guarantee of gradient-based algorithms for convolutional filter on non-Gaussian input distributions. Our theory also justifies the two-stage learning rate strategy in deep neural networks. While our focus is theoretical, we also present experiments that justify our theoretical findings.
This paper studies the problem of learning a single convolutional filter using SGD. The main result is: if the "patches" of the convolution are sufficiently aligned with each other, then SGD with a random initialization can recover the ground-truth parameter of a convolutional filter (single filter, ReLU, average pooling). The convergence rate, and how "sufficiently aligned" depend on some quantities related to the underlying data distribution. A major strength of the result is that it can work for general continuous distributions and does not really rely on the input distribution being Gaussian; the main weakness is that some of the distribution dependent quantities are not very intuitive, and the alignment requirement might be very high.
Detailed comments:
1. It would be good to clarify what the angle requirement means on page 2. It says the angle between Z_i, Z_j is at most \rho, is this for any i,j? From the later part it seems that each Z_i should be \rho close to the average, which would imply pairwise closeness (with some constant factor).
2. The paper first proves result for a single neuron, which is a clean result. It would be interesting to see what are values of \gamma(\phi) and L(\phi) for some distributions (e.g. Gaussian, uniform in hypercube, etc.) to give more intuitions. 
3. The convergence rate depends on \gamma(\phi_0), from the initialization, \phi_0 is probably very close to \pi/2 (the closeness depend on dimension), which is  also likely to make \gamma(\phi_0) depend on dimension (this is especially true of Gaussian). 
4. More precisely, \gamma(\phi_0) needs to be at least 6L_{cross} for the result to work, and L_{cross} seems to be a problem dependent constant that is not related to the dimension of the data. Also \gamma(\phi_0) depends on \gamma_{avg}(\phi_0) and \rho, when \rho is reasonable (say a constant), \gamma(\phi_0) really needs to be a constant that is independent of dimension. On the other hand, in Theorem 3.4 we can see that the upperbound on \alpha (the quality of initialization) depends on the dimension. 
5. Even assuming \rho is a constant strictly smaller than \pi/2 seems a bit strong. It is certainly plausible that nearby patches are highly correlated, but what is required here is that all patches are close to the average. Given an image it is probably not too hard to find an almost all white patch and an almost all dark patch so that they cannot both be within a good angle to the average. 
Overall I feel the result is interesting but hard to interpret correctly. The details of the theorem do not really support the high level claims very strongly. The paper would be much better if it goes over several example distributions and show explicitly what are the guarantees. The reviewer tried to do that for Gaussian and as I mentioned above (esp. 4) the result does not seem very impressive, maybe there are other distributions where this result works better?
After reading the response, I feel the contribution for the single neuron case does not require too much assumptions and is itself a reasonable result. I am still not convinced by the convolution case (which is the main point of this paper), as even though it does not require Gaussian input (a major plus), it still seems very far from "general distribution". Overall this is a first step in an interesting direction, so even though it is currently a bit weak I think it is OK to be accepted. I hope the revised version will clearly discuss the limitations of the approach and potential future directions as the response did.