LEARNING TWO-LAYER NEURAL NETWORKS WITH SYMMETRIC INPUTS
We give a new algorithm for learning a two-layer neural network under a general class of input distributions. Assuming there is a ground-truth two-layer network
where A, W are weight matrices, ξ represents noise, and the number of neurons in the hidden layer is no larger than the input or output, our algorithm is guaranteed to recover the parameters A, W of the ground-truth network. The only requirement on the input x is that it is symmetric, which still allows highly complicated and structured input. Our algorithm is based on the method-of-moments framework and extends several results in tensor decompositions. We use spectral algorithms to avoid the complicated non-convex optimization in learning neural networks. Experiments show that our algorithm can robustly learn the ground-truth neural network with a small number of samples for many symmetric input distributions.
This paper studies the problem of learning the parameters of a two-layer (or one-hidden layer) ReLU network $y=A\sigma(Wx)$, under the assumption that the distribution of $x$ is symmetric. The main technique here is the "pure neuron detector", which is a high-order moment function of a vector. It can be proved that the pure neuron detector is zero if and only if the vector is equal to the row vector of A^{-1}. Hence, we can "purify" the two layer neural network into independent one layer neural networks, and solve the problem easily.
This paper proposes interesting ideas, supported by mathematical proofs. This paper contains analysis of the algorithm itself, analysis of finding z_i's from span(z_i z_i^T), and analysis of the noisy case. 
This paper is reasonably well-written in the sense that the main technical ideas are easy to follow, but there are several grammatical errors, some of which I list below. I list my major comments below:
1) [strong assumptions] The result critically depends on the fact that $x$ is symmetric around the origin and the requirement that activation function is a ReLU. Lemma 1, 2, 3 and Lemma 6 in the appendix are based on these two assumptions. For example, the algorithm fails if $x$ is symmetric around a number other than zero or there is a bias term (i.e. $y=A \sigma(Wx+b) + b'$ ). This strong assumptions significantly weaken the general message of this paper. Add a discussion on how to generalize the idea to more general cases, at least when the bias term is present. 
2) [sample efficiency] Tensor decomposition methods tend to suffer in sample efficiency, requiring a large number of samples. In the proposed algorithm (Algorithm 2), estimation of $E[y \otimes x^{\otimes 3}]$ and $E[y \otimes y \otimes (x \otimes x)]$ are needed. How is the sample complexity with respect to the dimension? The theory in this paper suggests a poly(d, 1/\epsilon) sample efficiency, but the exponent of the poly is not known. In Section 4.1, the authors talk about the sample efficiency and claim that the sample efficiency is 5x the number of parameters, but this does not match the result in Figure 2. In the left of Figure 2, when d=10, we need no more than 500 samples to get error of W and A very small, but in the right, when d=32, 10000 samples can not give very small error of W and A. I suspect that the required number of samples to achieve small error scales quadratically in the number of parameters in the neural network. Some theoretical or experimental investigation to identify the exponent of the polynomial on d is in order. Also, perhaps plotting in log-y is better for Figure 2.
3) The idea of "purifying" the neurons has a potential to provide new techniques to analyze deeper neural networks. Explain how one might use the "purification" idea for deeper neural networks and what the main challenges are. 
Minor comments: 
"Why can we efficiently learn a neural network even if we assume one exists?" -> "The question of whether we can efficiently learn a neural network still remains generally open, even when the data is drawn from a neural network."
"with simple input distribution" -> "with a simple input distribution"