Giving provable guarantees for learning neural networks is a core challenge of machine learning theory. Most prior work gives parameter recovery guarantees for one hidden layer networks, however, the networks used in practice have multiple non-linear layers. In this work, we show how we can strengthen such results to deeper networks -we address the problem of uncovering the lowest layer in a deep neural network under the assumption that the lowest layer uses a high threshold before applying the activation, the upper network can be modeled as a well-behaved polynomial and the input distribution is gaussian.
This paper gives provable recovery guarantees for a class of neural networks which have high-threshold activation in the first layer, followed by a "well-behaved" polynomial, under Gaussian input. The algorithm is based on the approach by Ge et al. (2017), as well as an iterative refinement method.
While this could be an interesting result, I have several concerns regarding the assumptions, correctness, and writing.
1) It is required that the threshold is at least sqrt{log d} (Thm. 1), where d is the number of hidden neurons in the first layer. It seems that this essentially zeros out almost all the neurons, since the maximum among d Gaussian random variables is roughly sqrt{log d}. The authors should explain what exactly this model is doing, i.e., what kind of functions it can compute, in order to justify why this is an interesting model.
Furthermore, the authors claim that the studied model is a "deep" neural network, but I disagree. As I understand, the difference between this model and two-layer networks is that the second layer here is a polynomial instead of a linear function. This doesn't make it a deep network since the (polynomial) part above the first layer is not modeled in a layer-wise fashion, not to mention that under the setting considered in the paper the polynomial behaves similar to a linear function.
2) It is stated at the end of Section 2 that the angle can be reduced by a factor of 1-1/d ***with constant probability***. How does this ensure you can succeed after O(d log(1/nu)) iterations? As far as I see you need the success probability in one iteration to be at least something like 1-1/Omega(d) so that you can apply a union bound.
3) Even if the issues of motivation and correctness are clarified, I find it very difficult to understand the overall intuition and main technical contributions in this paper. The writing needs to be significantly improved to reach the level of a top conference.