Learning deep networks is computationally hard in the general case. To show any positive theoretical results, one must make assumptions on the data distribution. Current theoretical works often make assumptions that are very far from describing real data, like sampling from Gaussian distribution or linear separability of the data. We describe an algorithm that learns convolutional neural network, assuming the data is sampled from a deep generative model that generates images level by level, where lower resolution images correspond to latent semantic classes. We analyze the convergence rate of our algorithm assuming the data is indeed generated according to this model (as well as additional assumptions). While we do not pretend to claim that the assumptions are realistic for natural images, we do believe that they capture some true properties of real data. Furthermore, we show that on CIFAR-10, the algorithm we analyze achieves results in the same ballpark with vanilla convolutional neural networks that are trained with SGD.
The paper claims to propose a computationally efficient algorithm for training deep CNNs by making assumptions about the distribution of data. The authors argue that (i) they don't make very simplistic assumptions about the data generating distribution as some other papers do, and (ii) their algorithm resembles the actual methods that are used for training deep models and shows some surprising properties of SGD.
Throughout the paper, the authors make a number of assumptions which seem arbitrary at times; not much justifications are provided. The authors claim that their assumptions are not as simplistic as assuming e.g., the inputs are sampled from Gaussian distribution. Unfortunately this is highly unclear: while the "assumptions" themselves are complex, the combination of those assumptions may make the problem solution trivial. While proving a lower bound to address this issue may be hard, at least the authors should try to illuminate more why the solution is not trivial (e.g., why a linear classifier doesn't work, etc.)
Despite the claims, I find the proposed algorithm very far from the usual SGD-based training methods; this is not a problem per se but I don't think that the result illuminates on the effectiveness of SGD (as the authors suggest). The proposed algorithm is a greedy layer-wise method that in each level does a clustering and also trains a "linear" CNN with SGD. So the hardness of end-to-end training of a deep network does not show up. Furthermore, it is not clear for training a linear CNN the SGD is even needed.
I suggest that the authors name each of the assumptions and clearly say which ones are assumed for which result. Here are some of the assumptions that the authors talk about.
1_ The data is generated by the following recursive procedure: First a small "high-level image" is generated from a distribution, G_0. The "pixels" of this high-level image are supposed to encode semantic classes, e.g., sky or ground. In the next step, each of these high-level pixels are turned into a small (lower-level) image. Therefore, we will have a more refined image after the second step. (each semantic class (e.g., sky) has a corresponding distribution that generates the smaller lower-level image (e.g., uniform over 4 possible types of skies)). This procedure continues recursively until we have the final image.
2_ G_0 is "linearly separable".
3_ Semantic classes defined in the model are different enough from each other
4_ {F_c} corresponding to semantic classes are linearly independent 
5_ Patch Orthonormality (apparently not assumed everywhere) 
it appears that if one assumes all of 1-5, then the problem becomes trivial (linearly separable). The authors then say that we don't want to make assumption 5 for this reason; still, the problem solution may be trivial (authors should at least intuitively justify why it isn't )
Here are some more uses of the word "assumption".
6_ "For simplicity of analysis, we assume only the first layer of the network is trained".
7_ "We assume the algorithm [KMEANS++] returns a mapping [...] such that [...]" 
The experiments do not seem conclusive. Only a few experiments have been done. I think the acquired results for CIFAR-10 are below the usual ones using CNNs, and the effects of various hyper-parameters may have interfered.
--
After reading the authors' response, I still think the way that the contributions are depicted (e.g., a justifying the effectiveness of SGD) are inaccurate/unsupported. 
Furthermore, although the authors' suggest that they have tested a linear classifier and observed that the data is not linearly separable, more explanations/intuitions are needed about the assumptions that are made throughout the paper.