A faster and simpler algorithm for learning shallow networks
Sitan Chen Shyam Narayanan
We revisit the well-studied problem of learning a linear combination of $k$
ReLU activations given labeled examples drawn from the standard $d$-dimensional
Gaussian measure. Chen et al. [CDG+23] recently gave the first algorithm for
this problem to run in $\text{poly}(d,1/\varepsilon)$ time when $k = O(1)$,
where $\varepsilon$ is the target error. More precisely, their algorithm runs
in time $(d/\varepsilon)^{\mathrm{quasipoly}(k)}$ and learns over multiple
stages. Here we show that a much simpler one-stage version of their algorithm
suffices, and moreover its runtime is only $(d/\varepsilon)^{O(k^2)}$.