Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs
<|reference_start|>Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs: 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.<|reference_end|>
@article{diakonikolas2024super,
    title={Super Non-singular Decompositions of Polynomials and their Application
  to Robustly Learning Low-degree PTFs},
    author={Ilias Diakonikolas and Daniel M. Kane and Vasilis Kontonis and Sihan
  Liu and Nikos Zarifis},
    journal={arXiv preprint arXiv:2404.00529},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.00529},
    primaryClass={cs.DS cs.LG}
}