Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
This addresses the problem of efficiently learning neural networks for researchers in computational learning theory, with incremental algorithmic progress for a specific case but foundational implications for understanding learnability limits.
The paper tackles PAC learning one-hidden-layer ReLU networks with positive coefficients under Gaussian marginals and label noise, providing the first polynomial-time algorithm for up to ~O(√log d) hidden units, answering an open question. It also proves a Statistical Query lower bound of d^Ω(k) for networks with arbitrary real coefficients, establishing a separation in efficient learnability.
We study the problem of PAC learning one-hidden-layer ReLU networks with $k$ hidden units on $\mathbb{R}^d$ under Gaussian marginals in the presence of additive label noise. For the case of positive coefficients, we give the first polynomial-time algorithm for this learning problem for $k$ up to $\tilde{O}(\sqrt{\log d})$. Previously, no polynomial time algorithm was known, even for $k=3$. This answers an open question posed by~\cite{Kliv17}. Importantly, our algorithm does not require any assumptions about the rank of the weight matrix and its complexity is independent of its condition number. On the negative side, for the more general task of PAC learning one-hidden-layer ReLU networks with arbitrary real coefficients, we prove a Statistical Query lower bound of $d^{Ω(k)}$. Thus, we provide a separation between the two classes in terms of efficient learnability. Our upper and lower bounds are general, extending to broader families of activation functions.