Improper Learning by Refuting
Improper Learning by Refuting
复制标题
反驳学习不当
DOI：
10.4230/lipics.itcs.2018.55
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Roi Livni
中科院分区：
文献类型：
--
作者：
Pravesh Kothari;Roi Livni
学习布尔值函数类的样品复杂性精确地以其ademacher的复杂性为特征。但是，这对有效的不可知论学习的样本复杂性几乎没有关系。
我们介绍了反驳复杂性，这是布尔概念类别的Rademacher复杂性的自然计算类似物，并表明它完全表征了有效不可知论的样本复杂性。在非正式的情况下，C类的反驳复杂性是有效区分标签与评估C（结构）和标签为I.I.D的情况相关的情况所需的示例标签对数量的最小数量。 Rademacher随机变量（噪声）。这种关系的简单方向是在最近的框架中隐式使用的，用于通过与反驳随机约束满意度问题的硬度联系而不当学习Daniely和合着者的下限。我们的工作可以看作是使不可知论的学习与在工作中隐含的反驳之间的关系变成明确的等价性。
在最近的独立作品中，萨利尔·瓦丹（Salil Vadhan）在可实现的（即无噪声）案件中发现了反驳与PAC学习之间的类似关系。
The sample complexity of learning a Boolean-valued function class is precisely characterized by its Rademacher complexity. This has little bearing, however, on the sample complexity of efficient agnostic learning.
We introduce refutation complexity, a natural computational analog of Rademacher complexity of a Boolean concept class and show that it exactly characterizes the sample complexity of efficient agnostic learning. Informally, refutation complexity of a class C is the minimum number of example-label pairs required to efficiently distinguish between the case that the labels correlate with the evaluation of some member of C (structure) and the case where the labels are i.i.d. Rademacher random variables (noise). The easy direction of this relationship was implicitly used in the recent framework for improper PAC learning lower bounds of Daniely and co-authors via connections to the hardness of refuting random constraint satisfaction problems. Our work can be seen as making the relationship between agnostic learning and refutation implicit in their work into an explicit equivalence.
In a recent, independent work, Salil Vadhan discovered a similar relationship between refutation and PAC-learning in the realizable (i.e. noiseless) case.