Distribution-free Testing for Halfspaces (Almost) Requires PAC Learning
Distribution-free Testing for Halfspaces (Almost) Requires PAC Learning
复制标题
半空间的无分布测试（几乎）需要 PAC 学习
DOI：
10.1137/1.9781611977073.70
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Patel, Shyamal
中科院分区：
文献类型：
--
作者：
Chen, Xi;Patel, Shyamal
众所周知，在θ {0，1} n上的半空间是具有Θ（n）个样本的PAC可学习的。最近Blais等人[4]指出，即使是基于样本的无分布测试任务也需要Ω（n/logn）个半空间样本。在这项工作中，我们研究了带查询的半空间的无分布测试，我们证明了其复杂性仍然是。我们证明了以下更强的折衷结果：当k满足n.99 ≤k≤O（n/log 3 n）时，对于{0，1} n上的半空间，任何接收k个样本的分布无关测试算法都必须对输入函数进行查询.对于半空间上的n，我们表明，任何算法，使有限数量的查询必须绘制Ω（n/logn）许多样本。
It is well known that halfspaces over ℝnand {0, 1}nare PAC-learnable with Θ(n) samples. Recently Blais et al. [4] showed that even the easier task of distribution-free sample-based testing requires Ω(n/logn) samples for halfspaces.In this work we study the distribution-free testing of halfspaceswith queries, for which we show that the complexity remains to be . Indeed we prove the following stronger tradeoff result: any distribution-free testing algorithm for halfspaces over {0, 1}nthat receivesksamples must make queries on the input function, whenksatisfiesn.99≤k≤O(n/log3n). For halfspaces over ℝnwe show that any algorithm that makes a finite number of queries must draw Ω(n/logn) many samples.