A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity
复制标题
DOI：
10.1145/3564246.3585206
复制
发表时间：
2022-11
期刊：
影响因子：
--
通讯作者：
Aravind Gollakota;Adam R. Klivans;Pravesh Kothari
中科院分区：
文献类型：
--
作者：
Aravind Gollakota;Adam R. Klivans;Pravesh Kothari
Rubinfeld和Vasilyan（2022）最近发表的一篇引人注目的论文发起了可测试学习的研究，其目标是用有效的可测试假设取代难以验证的分布假设（如高斯性），并要求学习者在未知分布通过相应测试时成功。在这个模型中，他们给出了一个有效的算法，用于在高斯可证明满足的可测试假设下学习半空间。在本文中，我们给出了一个强大的新方法，用于开发算法的可测试的学习工具，矩匹配和度量距离的概率。我们获得有效的可测试学习者的任何概念类，承认低程度的多项式，捕捉最重要的例子，我们有普通的不可知学习者。我们恢复Rubinfeld和Vasilyan的结果作为我们的技术的必然结果，同时实现了广泛的概念类和分布的改进，接近最佳的样本复杂性界限。令人惊讶的是，我们发现，可测试学习的信息理论样本复杂性的特征是紧密的概念类，在统计学习理论中研究最充分的措施之一的Rademacher复杂性。特别地，一致收敛对于可测试学习是必要的和充分的。这导致与（普通）特定于分布的不可知学习的根本分离，其中一致收敛是足够的，但不是必要的。
A remarkable recent paper by Rubinfeld and Vasilyan (2022) initiated the study of testable learning, where the goal is to replace hard-to-verify distributional assumptions (such as Gaussianity) with efficiently testable ones and to require that the learner succeed whenever the unknown distribution passes the corresponding test. In this model, they gave an efficient algorithm for learning halfspaces under testable assumptions that are provably satisfied by Gaussians. In this paper we give a powerful new approach for developing algorithms for testable learning using tools from moment matching and metric distances in probability. We obtain efficient testable learners for any concept class that admits low-degree sandwiching polynomials, capturing most important examples for which we have ordinary agnostic learners. We recover the results of Rubinfeld and Vasilyan as a corollary of our techniques while achieving improved, near-optimal sample complexity bounds for a broad range of concept classes and distributions. Surprisingly, we show that the information-theoretic sample complexity of testable learning is tightly characterized by the Rademacher complexity of the concept class, one of the most well-studied measures in statistical learning theory. In particular, uniform convergence is necessary and sufficient for testable learning. This leads to a fundamental separation from (ordinary) distribution-specific agnostic learning, where uniform convergence is sufficient but not necessary.