Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise
  We give tight statistical query (SQ) lower bounds for learnining halfspaces
in the presence of Massart noise. In particular, suppose that all labels are
corrupted with probability at most $\eta$. We show that for arbitrary $\eta \in
[0,1/2]$ every SQ algorithm achieving misclassification error better than
$\eta$ requires queries of superpolynomial accuracy or at least a
superpolynomial number of queries. Further, this continues to hold even if the
information-theoretically optimal error $\mathrm{OPT}$ is as small as
$\exp\left(-\log^c(d)\right)$, where $d$ is the dimension and $0 < c < 1$ is an
arbitrary absolute constant, and an overwhelming fraction of examples are
noiseless. Our lower bound matches known polynomial time algorithms, which are
also implementable in the SQ framework. Previously, such lower bounds only
ruled out algorithms achieving error $\mathrm{OPT} + \epsilon$ or error better
than $\Omega(\eta)$ or, if $\eta$ is close to $1/2$, error $\eta - o_\eta(1)$,
where the term $o_\eta(1)$ is constant in $d$ but going to 0 for $\eta$
approaching $1/2$.
  As a consequence, we also show that achieving misclassification error better
than $1/2$ in the $(A,\alpha)$-Tsybakov model is SQ-hard for $A$ constant and
$\alpha$ bounded away from 1.
