Testing Halfspaces over Rotation-Invariant Distributions

We present an algorithm for testing halfspaces over arbitrary, unknown rotation-invariant distributions. Using tilde O(√nε-7) random examples of an unknown function f, the algorithm determines with high probability whether f is of the form f(x) = sign(sumi wixi-t) or is ε-far from all such functions. This sample size is significantly smaller than the well-known requirement of Omega(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.