Realizable Learning is All You Need
Realizable Learning is All You Need
复制标题
DOI：
10.46298/theoretics.24.2
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Max Hopkins;D. Kane;Shachar Lovett;G. Mahajan
中科院分区：
文献类型：
--
作者：
Max Hopkins;D. Kane;Shachar Lovett;G. Mahajan
可实现和不可知论的可学习性的等效性是学习理论中的基本现象。随着从PAC学习和回归等经典环境到最近的趋势（例如对抗性稳健学习）的变体，令人惊讶的是，我们仍然缺乏统一的理论。等价的传统证明往往是不同的，并且依赖于统一收敛和样品压缩等强大的模型特定假设。在这项工作中，我们给出了第一个独立于模型的框架，以解释可实现和不可知论的可学习性的等效性：一种三行黑框减少，简化，统一并扩展了我们在各种环境中的理解。这包括没有知道可学习性的模型，例如具有任意分布假设和更一般损失功能的学习，以及许多其他流行的环境，例如健壮的学习，部分学习，公平学习和统计查询模型。更普遍地，我们认为，可实现和不可知论的学习实际上是一种更广泛现象的特殊情况，我们称之为财产概括：学习算法的任何理想特性（例如，噪声耐受性，隐私，稳定性）可以在有限假设上满足类别（可能有些变化）扩展到任何可学习的假设类别。
The equivalence of realizable and agnostic learnability is a fundamental phenomenon in learning theory. With variants ranging from classical settings like PAC learning and regression to recent trends such as adversarially robust learning, it's surprising that we still lack a unified theory; traditional proofs of the equivalence tend to be disparate, and rely on strong model-specific assumptions like uniform convergence and sample compression. In this work, we give the first model-independent framework explaining the equivalence of realizable and agnostic learnability: a three-line blackbox reduction that simplifies, unifies, and extends our understanding across a wide variety of settings. This includes models with no known characterization of learnability such as learning with arbitrary distributional assumptions and more general loss functions, as well as a host of other popular settings such as robust learning, partial learning, fair learning, and the statistical query model. More generally, we argue that the equivalence of realizable and agnostic learning is actually a special case of a broader phenomenon we call property generalization: any desirable property of a learning algorithm (e.g. noise tolerance, privacy, stability) that can be satisfied over finite hypothesis classes extends (possibly in some variation) to any learnable hypothesis class.