A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
  We study the problem of PAC learning homogeneous halfspaces in the presence
of Tsybakov noise. In the Tsybakov noise model, the label of every sample is
independently flipped with an adversarially controlled probability that can be
arbitrarily close to $1/2$ for a fraction of the samples. {\em We give the
first polynomial-time algorithm for this fundamental learning problem.} Our
algorithm learns the true halfspace within any desired accuracy $\epsilon$ and
succeeds under a broad family of well-behaved distributions including
log-concave distributions. Prior to our work, the only previous algorithm for
this problem required quasi-polynomial runtime in $1/\epsilon$.
  Our algorithm employs a recently developed reduction \cite{DKTZ20b} from
learning to certifying the non-optimality of a candidate halfspace. This prior
work developed a quasi-polynomial time certificate algorithm based on
polynomial regression. {\em The main technical contribution of the current
paper is the first polynomial-time certificate algorithm.} Starting from a
non-trivial warm-start, our algorithm performs a novel "win-win" iterative
process which, at each step, either finds a valid certificate or improves the
angle between the current halfspace and the true one. Our warm-start algorithm
for isotropic log-concave distributions involves a number of analytic tools
that may be of broader interest. These include a new efficient method for
reweighting the distribution in order to recenter it and a novel
characterization of the spectrum of the degree-$2$ Chow parameters.
