Abstract

We consider the problem of computing the best-fitting ReLU with respect to squareloss on a training set when the examples have been drawn according to a spherical Gaussian distribution (the labels can be arbitrary). Let opt < 1 be the population loss of the best-fitting ReLU. We prove:

    • Finding a ReLU with square-loss opt +  is as hard as the problem of learning sparse parities with noise, widely thought to be computationally intractable. This is the first hardness result for learning a ReLU with respect to Gaussian marginals, and our results imply –unconditionally– that gradient descent cannot converge to the global minimum in polynomial time.

    • There exists an efficient approximation algorithm for finding the best-fitting ReLU that achieves error The algorithm uses a novel reduction to noisy halfspace learning with respect to 0/1 loss. Prior work due to Soltanolkotabi [18] showed that gradient descent can find the best-fitting ReLU with respect to Gaussian marginals, if the training set is exactly labeled by a ReLU.