Super Non-singular Decompositions of Polynomials and their Application
  to Robustly Learning Low-degree PTFs
Ilias Diakonikolas Daniel M. Kane Vasilis Kontonis Sihan Liu Nikos Zarifis
We study the efficient learnability of low-degree polynomial threshold
functions (PTFs) in the presence of a constant fraction of adversarial
corruptions. Our main algorithmic result is a polynomial-time PAC learning
algorithm for this concept class in the strong contamination model under the
Gaussian distribution with error guarantee $O_{d, c}(\text{opt}^{1-c})$, for
any desired constant $c>0$, where $\text{opt}$ is the fraction of corruptions.
In the strong contamination model, an omniscient adversary can arbitrarily
corrupt an $\text{opt}$-fraction of the data points and their labels. This
model generalizes the malicious noise model and the adversarial label noise
model. Prior to our work, known polynomial-time algorithms in this corruption
model (or even in the weaker adversarial label noise model) achieved error
$\tilde{O}_d(\text{opt}^{1/(d+1)})$, which deteriorates significantly as a
function of the degree $d$.
  Our algorithm employs an iterative approach inspired by localization
techniques previously used in the context of learning linear threshold
functions. Specifically, we use a robust perceptron algorithm to compute a good
partial classifier and then iterate on the unclassified points. In order to
achieve this, we need to take a set defined by a number of polynomial
inequalities and partition it into several well-behaved subsets. To this end,
we develop new polynomial decomposition techniques that may be of independent
interest.