Distribution-free Testing for Halfspaces (Almost) Requires PAC Learning

It is well known that halfspaces over ℝn and 0, 1n 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, 1n 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.