Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds

By Santosh Srinivas Vempala, John Wilmes. 2018

51 citations recorded by the source corpus.

We study the complexity of training neural network models with one hidden nonlinear activation layer and an output weighted sum layer. We analyze Gradient Descent applied to learning a bounded target function on $n$ real-valued inputs. We give an agnostic learning guarantee for GD: starting from a randomly initialized network, it converges in mean squared loss to the minimum error (in $2$-norm) of the best approximation of the target function using a polynomial of degree at most $k$. Moreover, for any $k$, the size of the network and number of iterations needed are both bounded by $n^{O(k)}\log(1/\epsilon)$. In particular, this applies to training networks of unbiased sigmoids and ReLUs. We also rigorously explain the empirical finding that gradient descent discovers lower frequency Fourier components before higher frequency components. We complement this result with nearly matching lower bounds in the Statistical Query model. GD fits well in the SQ framework since each training step is determined by an expectation over the input distribution. We show that any SQ algorithm that achieves significant improvement over a constant function with queries of tolerance some inverse polynomial in the input dimensionality $n$ must use $n^{\Omega(k)}$ queries even when the target functions are restricted to a set of $n^{O(k)}$ degree-$k$ polynomials, and the input distribution is uniform over the unit sphere; for this class the information-theoretic lower bound is only $\Theta(k \log n)$. Our approach for both parts is based on spherical harmonics. We view gradient descent as an operator on the space of functions, and study its dynamics. An essential tool is the Funk-Hecke theorem, which explains the eigenfunctions of this operator in the case of the mean squared loss.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Frequency Bias in Neural Networks for Input of Non-Uniform Density (2020, methodology): “These analyses were applied to two-layer networks (Bach, 2017; Bietti & Mairal, 2019; Du et al., 2019; Vempala & Wilmes, 2018; Xie et al., 2017), multilayer perceptrons (i,e. fully connected), residual and convolutional networks (Allen-Zhu et al., 2018; 2019; Arora et al., 2019a; Huang & Yau, 2019;…”
On Learning Over-parameterized Neural Networks: A Functional Approximation Prospective (2019, background): “Recently, a handful of work studied linearized neural networks in high dimen-sion [GMMM19, YS19, VW18].”
Gradient Starvation: A Learning Proclivity in Neural Networks (2020, background): “More recently, with the introduction of neural tangent kernel (NTK) [52, 62], a new line of research is to study the convergence properties of gradient descent [e.g. 8, 69, 25, 29, 7, 44, 33, 110, 11, 99].”
Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK (2020, background): “…(2016); Soudry and Carmon (2016); Xie et al. (2016); Soltanolkotabi et al. (2017); Tian (2017); Brutzkus and Globerson (2017); Boob and Lan (2017); Vempala and Wilmes (2018); Oymak and Soltanolkotabi (2019); Bakshi et al. (2018); Yehudai and Shamir (2019); Zhang et al. (2018); Li and Liang…”
Towards Understanding the Spectral Bias of Deep Learning (2019, background): “[Vempala and Wilmes, 2019] studied twolayer neural networks with sigmoid activation function, and proved that in order to achieve 0 ` error, it requires T “ pd ` 1qOpkq log p}f}2{ q iterations and m “ pd ` 1qOpkqpolyp}f}2{ q wide neural networks, where f ̊ is the target function, and 0 is certain fu”