  We study the fundamental problems of agnostically learning halfspaces and
ReLUs under Gaussian marginals. In the former problem, given labeled examples
$(\mathbf{x}, y)$ from an unknown distribution on $\mathbb{R}^d \times \{ \pm
1\}$, whose marginal distribution on $\mathbf{x}$ is the standard Gaussian and
the labels $y$ can be arbitrary, the goal is to output a hypothesis with 0-1
loss $\mathrm{OPT}+\epsilon$, where $\mathrm{OPT}$ is the 0-1 loss of the
best-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 standard
Gaussian and the labels $y$ can be arbitrary, the goal is to output a
hypothesis with square loss $\mathrm{OPT}+\epsilon$, where $\mathrm{OPT}$ is
the square loss of the best-fitting ReLU. We prove Statistical Query (SQ) lower
bounds of $d^{\mathrm{poly}(1/\epsilon)}$ for both of these problems. Our SQ
lower bounds provide strong evidence that current upper bounds for these tasks
are essentially best possible.
