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

arXiv: https://arxiv.org/abs/1805.02677 · HTML: https://mlsanity.com/paper/1805.02677/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2018.

## Built on by (most cited first, 18 of 18)

- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [From Local Pseudorandom Generators to Hardness of Learning](https://mlsanity.com/paper/2101.08303/) (2021)
- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [Provably learning a multi-head attention layer](https://mlsanity.com/paper/2402.04084/) (2024)
- [Six Lectures on Linearized Neural Networks](https://mlsanity.com/paper/2308.13431/) (2023)
- [Hardness of Learning Neural Networks under the Manifold Hypothesis](https://mlsanity.com/paper/2406.01461/) (2024)
- [On the Power of Preconditioning in Sparse Linear Regression](https://mlsanity.com/paper/2106.09207/) (2021)
- [On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries](https://mlsanity.com/paper/2407.05622/) (2024)
- [Learning Narrow One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2304.10524/) (2023)
- [Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy](https://mlsanity.com/paper/2302.07426/) (2023)
- [Learning (Very) Simple Generative Models Is Hard](https://mlsanity.com/paper/2205.16003/) (2022)
- [A faster and simpler algorithm for learning shallow networks](https://mlsanity.com/paper/2307.12496/) (2023)
- [Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models](https://mlsanity.com/paper/2411.15669/) (2024)
- [Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials](https://mlsanity.com/paper/2307.12840/) (2023)
- [Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees](https://mlsanity.com/paper/2502.16021/) (2025)
- [Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs](https://mlsanity.com/paper/2203.02824/) (2022)
- [Most Neural Networks Are Almost Learnable](https://mlsanity.com/paper/2305.16508/) (2023)
- [DNA-SE: Towards Deep Neural-Nets Assisted Semiparametric Estimation](https://mlsanity.com/paper/2408.02045/) (2024)

## Abstract (arXiv)

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 nO(k)log(1/ε). 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 nOmega(k) queries even when the target functions are restricted to a set of nO(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.