Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials

Understand

We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $\mathbb{R}^d$ with respect to the square loss.

• Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/\epsilon)^{O(k)}$, where $\epsilon>0$ is the target accuracy.
• Prior work had given an algorithm for this problem with complexity $(dk/\epsilon)^{h(k)}$, where the function $h(k)$ scales super-polynomially in $k$.
• Interestingly, the complexity of our algorithm is near-optimal within the class of Correlational Statistical Query algorithms.