Distribution-free Testing for Halfspaces (Almost) Requires PAC Learning
Xi Chen, Shyamal Patel · Society for Industrial and Applied Mathematics eBooks · 2022
It is well known that halfspaces over ℝn and {0, 1}n are PAC-learnable with Θ(n) samples. Recently Blais et al. [4] showed that even the easier task of distribution-free sample-based testing requires Ω(n/log n) samples for halfspaces. In this work we study the distribution-free testing of halfspaces with 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}n that receives k samples must make queries on the input function, when k satisfies n.99 ≤ k ≤ O(n/ log3 n). For halfspaces over ℝn we show that any algorithm that makes a finite number of queries must draw Ω(n/log n) many samples.