Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit
<|reference_start|>Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit: We study the problem of gradient descent learning of a single-index target function $f_*(\boldsymbol{x}) = \textstyle\sigma_*\left(\langle\boldsymbol{x},\boldsymbol{\theta}\rangle\right)$ under isotropic Gaussian data in $\mathbb{R}^d$, where the link function $\sigma_*:\mathbb{R}\to\mathbb{R}$ is an unknown degree $q$ polynomial with information exponent $p$ (defined as the lowest degree in the Hermite expansion). Prior works showed that gradient-based training of neural networks can learn this target with $n\gtrsim d^{\Theta(p)}$ samples, and such statistical complexity is predicted to be necessary by the correlational statistical query lower bound. Surprisingly, we prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ of arbitrary polynomial link function with a sample and runtime complexity of $n \asymp T \asymp C(q) \cdot d\mathrm{polylog} d$, where constant $C(q)$ only depends on the degree of $\sigma_*$, regardless of information exponent; this dimension dependence matches the information theoretic limit up to polylogarithmic factors. Core to our analysis is the reuse of minibatch in the gradient computation, which gives rise to higher-order information beyond correlational queries.<|reference_end|>
@article{lee2024neural,
    title={Neural network learns low-dimensional polynomials with SGD near the
  information-theoretic limit},
    author={Jason D. Lee and Kazusato Oko and Taiji Suzuki and Denny Wu},
    journal={arXiv preprint arXiv:2406.01581},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.01581},
    primaryClass={cs.LG stat.ML}
}