On the Weight of Halfspaces over Hamming Balls
Philip M. Long, Rocco A. Servedio · SIAM Journal on Discrete Mathematics · 2014
For $S \subseteq \{0,1\}^n$, a Boolean function $f: S \to \{-1,1\}$ is a halfspace over $S$ if there exist $w \in \mathbb{R}^n$ and $\theta \in \mathbb{R}$ such that $f(x)=\mathrm{sign}(w \cdot x - \theta)$ for all $x \in S$. We give bounds on the size of integer weights $w_1,\dots,w_n \in \mathbb{Z}$ that are required to represent halfspaces over Hamming balls $S = \{x \in \{0,1\}^n : x_1 + \cdots + x_n \leq k\}.$ Such weight bounds for halfspaces over Hamming balls have immediate consequences for the performance of learning algorithms in the 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. We give upper and lower bounds on weight both for exact representation (when $\mathrm{sign}(w \cdot x {-\theta})$ must equal $f(x)$ for every $x \in S$) and for $\varepsilon$-approximate representation (when $\mathrm{sign}(w \cdot x {- \theta})$ may disagree with $f(x)$ for up to an $\varepsilon$ fraction of points $x \in S$). Our results show that extremal bounds for exact representation are qualitatively rather similar whether the domain is all of $\{0,1\}^n$ or the Hamming ball $\{0,1\}^n_{\leq k}$, but extremal bounds for approximate representation are qualitatively very different between these two domains.