Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals

Abstract

We consider the problem of computing the best-fitting ReLU with respect to square-loss on a training set when the examples have been drawn according to a spherical Gaussian distribution (the labels can be arbitrary). Let $\mathsf{opt}<1$ be the population loss of the best-fitting ReLU. We prove: 1. Finding a ReLU with square-loss $\mathsf{opt}+\epsilon$ 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 -{\emph unconditionally}- that gradient descent cannot converge to the global minimum in polynomial time. 2. There exists an efficient approximation algorithm for finding the best-fitting ReLU that achieves error $O({\mathsf{opt}}^{2/3})$. The algorithm uses a novel reduction to noisy halfspace learning with respect to $0/1$ loss. Prior work due to Soltanolkotabi [Sol17] 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.

To appear in NeurIPS 2019 (Spotlight)

Cited by in corpus (13)

• Agnostic Learning of a Single Neuron with Gradient Descent
• Statistical-Query Lower Bounds via Functional Gradients
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals
• Approximation Schemes for ReLU Regression
• Learning Deep ReLU Networks Is Fixed-Parameter Tractable
• Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins
• The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals
• Proxy Convexity: A Unified Framework for the Analysis of Neural Networks Trained by Gradient Descent
• From Local Pseudorandom Generators to Hardness of Learning
• On the Cryptographic Hardness of Learning Single Periodic Neurons
• Understanding How Over-Parametrization Leads to Acceleration: A case of learning a single teacher neuron
• ReLU Regression with Massart Noise
• Provable Generalization of SGD-trained Neural Networks of Any Width in the Presence of Adversarial Label Noise