Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs

• Published in: arXiv.org 2024-03
• Main Authors: Diakonikolas, Ilias, Kane, Daniel M, Kontonis, Vasilis, Liu, Sihan, Zarifis, Nikos
• Format: Article
• Language: English
• Subjects: Algorithms; Contamination; Data points; Decomposition; Functions (mathematics); Labels; Machine learning; Normal distribution; Polynomials
• ISSN: 2331-8422

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.