Testing Halfspaces over Rotation-Invariant Distributions
This work addresses the challenge of property testing for halfspaces in machine learning, offering a distribution-free algorithm with significant sample efficiency improvements, though it is incremental as it builds on prior testing frameworks.
The paper tackles the problem of testing halfspaces over unknown rotation-invariant distributions, presenting an algorithm that uses $ ilde O(\sqrt{n}ε^{-7})$ random examples to determine if a function is a halfspace or ε-far from all such functions, which is optimal up to logarithmic factors compared to the Ω(n) samples needed for learning.
We present an algorithm for testing halfspaces over arbitrary, unknown rotation-invariant distributions. Using $\tilde O(\sqrt{n}ε^{-7})$ random examples of an unknown function $f$, the algorithm determines with high probability whether $f$ is of the form $f(x) = sign(\sum_i w_ix_i-t)$ or is $ε$-far from all such functions. This sample size is significantly smaller than the well-known requirement of $Ω(n)$ samples for learning halfspaces, and known lower bounds imply that our sample size is optimal (in its dependence on $n$) up to logarithmic factors. The algorithm is distribution-free in the sense that it requires no knowledge of the distribution aside from the promise of rotation invariance. To prove the correctness of this algorithm we present a theorem relating the distance between a function and a halfspace to the distance between their centers of mass, that applies to arbitrary distributions.