Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks

Abstract

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^{\Omega (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.

References in corpus (6)

• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• Reliably Learning the ReLU in Polynomial Time
• The Computational Complexity of Training ReLU(s)
• Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds
• Learning Two-layer Neural Networks with Symmetric Inputs

Cited by in corpus (5)

• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals
• The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• From Local Pseudorandom Generators to Hardness of Learning
• The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning