We give a new algorithm for learning a two-layer neural network under a very general class of input distributions. Assuming there is a ground-truth two-layer network 
 y = A \sigma(Wx) + \xi,
 where A, W are weight matrices, \xi 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. Deep neural networks have been extremely successful in many tasks related to images, videos and reinforcement learning. However, the success of deep learning is still far from being understood in theory. In particular, learning a neural network is a complicated non-convex optimization problem, which is hard in the worst-case. 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. Despite a lot of recent effort, the class of neural networks that we know how to provably learn in polynomial time is still very limited, and many results require strong assumptions on the input distribution.In this paper we design a new algorithm that is capable of learning a two-layer 1 neural network for a general class of input distributions. Following standard models for learning neural networks, we assume there is a ground truth neural network. The input data (x, y) is generated by first sampling the input x from an input distribution D, then computing y according to the ground truth network that is unknown to the learner. The learning algorithm will try to find a neural network f such that f (x) is as close to y as possible over the input distribution D. Learning a neural network is known to be a hard problem even in some simple settings (Goel et al., 2016; Brutzkus & Globerson, 2017) , so we need to make assumptions on the network structure or the input distribution D, or both. Many works have worked with a simple input distribution (such as Gaussians) and try to learn more and more complex networks (Tian, 2017; Brutzkus & Globerson, 2017; Li & Yuan, 2017; Soltanolkotabi, 2017; Zhong et al., 2017) . However, the input distributions in real life are distributions of very complicated objects such as texts, images or videos. These inputs are highly structured, clearly not Gaussian and do not even have a simple generative model.We consider a type of two-layer neural network, where the output y is generated as y = Aσ(W x) + ξ.Here x ∈ R d is the input, W ∈ R k×d and A ∈ R k×k are two weight matrices 2 . The function σ is the standard ReLU activation function σ(x ) = max{x, 0} applied entry-wise to the vector W x, and ξ is a noise vector that has E[ξ] = 0 and is independent of x. Although the network only has two layers, learning similar networks is far from trivial: even when the input distribution is Gaussian, Ge et al. (2017b) and Safran & Shamir (2018) showed that standard optimization objective can have bad local optimal solutions. Ge et al. (2017b) gave a new and more complicated objective function that does not have bad local minima.For the input distribution D, our only requirement is that D is symmetric. That is, for any x ∈ R d , the probability of observing x ∼ D is the same as the probability of observing −x ∼ D. A symmetric distribution can still be very complicated and cannot be represented by a finite number of parameters. In practice , one can often think of the symmetry requirement as a "factor-2" approximation to an arbitrary input distribution: if we have arbitrary training samples, it is possible to augment the input data with their negations to make the input distribution symmetric, and it should take at most twice the effort in labeling both the original and augmented data. In many cases (such as images) the augmented data can be interpreted (for images it will just be negated colors) so reasonable labels can be obtained. Optimizing the parameters of a neural network is a difficult problem, especially since the objective function depends on the input distribution which is often unknown and can be very complicated. In this paper, we design a new algorithm using method-of-moments and spectral techniques to avoid the Published as a conference paper at ICLR 2019 complicated non-convex optimization for neural networks. Our algorithm can learn a network that is of similar complexity as the previous works, while allowing much more general input distributions.There are still many open problems. The current result requires output to have the same (or higher) dimension than the hidden layer, and the hidden layer does not have a bias term. Removing these constraints are are immediate directions for future work. Besides the obvious ones of extending our results to more general distributions and more complicated networks, we are also interested in the relations to optimization landscape for neural networks. In particular, our algorithm shows there is a way to find the global optimal network in polynomial time, does that imply anything about the optimization landscape of the standard objective functions for learning such a neural network, or does it imply there exists an alternative objective function that does not have any local minima? We hope this work can lead to new insights for optimizing a neural network.
We give an algorithm for learning a two-layer neural network with symmetric input distribution. 
{"src": "scitldr-AIC_train", "paper_id": "H1xipsA5K7"}