Fast and Provable Algorithms for Learning Two-Layer Polynomial Neural Networks

In this paper, we bridge the problem of (provably) learning shallow neural networks with the well-studied problem of low-rank matrix estimation. In particular, we consider two-layer networks with quadratic activations, and focus on the under-parameterized regime where the number of neurons in the hidden layer is smaller than the dimension of the input. Our main approach is to “lift” the learning problem into a higher dimension, which enables us to borrow algorithmic techniques from low-rank matrix estimation. Using this intuition, we propose three novel, non-convex training algorithms. We support our algorithms with rigorous theoretical analysis, and show that all three enjoy a linear convergence, fast running time per iteration, and near-optimal sample complexity. Finally, we complement our theoretical results with numerical experiments.