Low-weight halfspaces for sparse boolean vectors
Philip M. Long, Rocco A. Servedio · 2013
For S ⊆ {0,1}n, a Boolean function f: S -> {-1,1} is a halfspace over S if there exist w ∈ Rn and θ ∈ R such that f(x)=sign(w ⋅ x - θ) for all x ∈ S. We give bounds on the size of integer weights w1,...,wn ∈ Z that are required to represent halfspaces over Hamming balls centered at 0n, i.e. halfspaces over S ={0,1}n≤ k = {x ∈ {0,1}n : x1 + ⋅⋅⋅ + xn ≤ k}. Such weight bounds for halfspaces over Hamming balls have immediate consequences for the performance of learning algorithms in the increasingly common scenario of learning from very high-dimensional categorical examples which are such that only a small number of features are active in each example.