Learning Polynomials with Neural Networks
Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang · 2014
We study the effectiveness of learning low degree polynomials using neural networks by the gradi-ent descent method. While neural networks have been shown to have great expressive power, and gradient descent has been widely used in prac-tice for learning neural networks, few theoretical guarantees are known for such methods. In par-ticular, it is well known that gradient descent can get stuck at local minima, even for simple classes of target functions. In this paper, we present sev-eral positive theoretical results to support the ef-fectiveness of neural networks. We focus on two-layer neural networks where the bottom layer is a set of non-linear hidden nodes, and the top layer node is a linear function, similar to Bar-ron (1993). First we show that for a randomly initialized neural network with sufficiently many hidden units, the generic gradient descent algo-rithm learns any low degree polynomial, assum-ing we initialize the weights randomly. Secondly, we show that if we use complex-valued weights (the target function can still be real), then un-der suitable conditions, there are no “robust lo-cal minima”: the neural network can always es-cape a local minimum by performing a random perturbation. This property does not hold for real-valued weights. Thirdly, we discuss whether sparse polynomials can be learned with small neural networks, with the size dependent on the sparsity of the target function.