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.

我们研究了在存在恶意污染的情况下低次多项式阈值函数（PTFs）的高效学习性能。我们的主要算法结果是在强污染模型下，基于高斯分布的概念类的多项式时间PAC学习算法，具有$O_{d, c}(	ext{opt}^{1-c})$的误差保证，其中$c>0$为常数，$	ext{opt}$为污染比例。我们的算法采用了一个受线性阈值函数学习环境启发的迭代方法，使用鲁棒感知器算法计算一个良好的部分分类器，并对未分类的点进行迭代。为了实现这一点，我们需要利用一些多项式不等式定义的集合，并将其划分为几个行为良好的子集。为此，我们开发了一些可能具有独立兴趣的新多项式分解技术。

多项式的超非奇异分解及其在鲁棒学习低次PTF中的应用