Abstract
We study the fundamental problems of agnostically learning halfspaces andReLUs under Gaussian marginals. In the former problem, given labeled examples$(\mathbf{x}, y)$ from an unknown distribution on $\mathbb{R}^d \times \{ \pm1\}$, whose marginal distribution on $\mathbf{x}$ is the standard Gaussian andthe labels $y$ can be arbitrary, the goal is to output a hypothesis with 0-1loss $\mathrm{OPT}+\epsilon$, where $\mathrm{OPT}$ is the 0-1 loss of thebest-fitting halfspace. In the latter problem, given labeled examples$(\mathbf{x}, y)$ from an unknown distribution on $\mathbb{R}^d \times\mathbb{R}$, whose marginal distribution on $\mathbf{x}$ is the standardGaussian and the labels $y$ can be arbitrary, the goal is to output ahypothesis with square loss $\mathrm{OPT}+\epsilon$, where $\mathrm{OPT}$ isthe square loss of the best-fitting ReLU. We prove Statistical Query (SQ) lowerbounds of $d^{\mathrm{poly}(1/\epsilon)}$ for both of these problems. Our SQlower bounds provide strong evidence that current upper bounds for these tasksare essentially best possible.