Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
  Classification Noise
Ilias Diakonikolas Jelena Diakonikolas Daniel M. Kane Puqian Wang Nikos Zarifis
We study the problem of learning general (i.e., not necessarily homogeneous)
halfspaces with Random Classification Noise under the Gaussian distribution. We
establish nearly-matching algorithmic and Statistical Query (SQ) lower bound
results revealing a surprising information-computation gap for this basic
problem. Specifically, the sample complexity of this learning problem is
$\widetilde{\Theta}(d/\epsilon)$, where $d$ is the dimension and $\epsilon$ is
the excess error. Our positive result is a computationally efficient learning
algorithm with sample complexity $\tilde{O}(d/\epsilon + d/(\max\{p,
\epsilon\})^2)$, where $p$ quantifies the bias of the target halfspace. On the
lower bound side, we show that any efficient SQ algorithm (or low-degree test)
for the problem requires sample complexity at least $\Omega(d^{1/2}/(\max\{p,
\epsilon\})^2)$. Our lower bound suggests that this quadratic dependence on
$1/\epsilon$ is inherent for efficient algorithms.