  We study the task of agnostically learning halfspaces under the Gaussian
distribution. Specifically, given labeled examples $(\mathbf{x},y)$ from an
unknown distribution on $\mathbb{R}^n \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. We prove a near-optimal computational hardness result
for this task, under the widely believed sub-exponential time hardness of the
Learning with Errors (LWE) problem. Prior hardness results are either
qualitatively suboptimal or apply to restricted families of algorithms. Our
techniques extend to yield near-optimal lower bounds for related problems,
including ReLU regression.
