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

arXiv:2404.00529v1 Announce Type: cross
Abstract: 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 …

abstract adversarial algorithm application arxiv class concept cs.ds cs.lg functions low polynomial singular study threshold type