Efficiently learning halfspaces with Tsybakov noise

We study the problem of PAC learning homogeneous halfspaces with Tsybakov noise. In the Tsybakov noise model, the label of every example is independently flipped with an adversarially controlled probability that can be arbitrarily close to 1/2 for a fraction of the examples. We give the first polynomial-time algorithm for this fundamental learning problem. Our algorithm learns the true halfspace within any desired accuracy and succeeds under a broad family of well-behaved distributions including log-concave distributions. This extended abstract is a merge of two papers. In an earlier work, a subset of the authors developed an efficient reduction from learning to certifying the non-optimality of a candidate halfspace and gave a quasi-polynomial time certificate algorithm. In a subsequent work, the authors of the this paper developed a polynomial-time certificate algorithm.