Training neural networks is a highly non-convex problem and in general is NP-hard. Local search methods such as gradient descent get stuck in spurious local optima, especially in high dimensions. We present a novel method based on tensor decomposition that trains a two layer neural network with guaranteed risk bounds for a large class of target functions with polynomial sample and computational...