2018/10/31 by Nathaniel Harms, Harms, Nathaniel · 3 citations
Computer Science · Mathematics · #Advanced Statistical Methods and Models #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1811.00139
openalex publication_date 2018/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present an algorithm for testing halfspaces over arbitrary, unknown rotation-invariant distributions. Using 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(∑i wixi-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.