We pose a fundamental question in computational learning theory: can we efficiently test whether a training set satisfies the assumptions of a given noise model? This question has remained unaddressed despite decades of research on learning in the presence of noise. In this work, we show that this task is tractable and present the first efficient algorithm to test various noise assumptions on the training data. To model this question, we extend the recently proposed testable learning framework of Rubinfeld and Vasilyan (2023) and require a learner to run an associated test that satisfies the following two conditions: (1) whenever the test accepts, the learner outputs a classifier along with a certificate of optimality, and (2) the test must pass for any dataset drawn according to a specified modeling assumption on both the marginal distribution and the noise model. We then consider the problem of learning halfspaces over Gaussian marginals with Massart noise (where each label can be flipped with probability less than $1/2$ depending on the input features), and give a fully-polynomial time testable learning algorithm. We also show a separation between the classical setting of learning in the presence of structured noise and testable learning. In fact, for the simple case of random classification noise (where each label is flipped with fixed probability $η= 1/2$), we show that testable learning requires super-polynomial time while classical learning is trivial.

翻译：我们在计算学习理论中提出一个基础性问题：能否高效地检验训练集是否满足给定噪声模型的假设？尽管在噪声环境下学习的研究已进行数十年，该问题至今未被探讨。本文中，我们证明该任务是可处理的，并首次提出高效算法以检验训练数据上的各类噪声假设。为建模此问题，我们扩展了Rubinfeld与Vasilyan（2023）近期提出的可检验学习框架，要求学习器运行满足以下两个条件的关联检验：（1）当检验通过时，学习器输出分类器及其最优性证明；（2）对于任何根据边际分布与噪声模型的特定建模假设抽取的数据集，检验必须通过。随后我们研究在高斯边际分布与Massart噪声（每个标签可能以小于$1/2$的概率被翻转，该概率取决于输入特征）下学习半空间的问题，并给出完全多项式时间的可检验学习算法。我们还展示了结构化噪声下的经典学习与可检验学习之间的分离。事实上，对于简单的随机分类噪声（每个标签以固定概率$η= 1/2$被翻转），我们证明可检验学习需要超多项式时间，而经典学习是平凡的。