Abstract.
A kernel over the Boolean domain is said to be reflection-invariant, if its
value does not change when we flip the same bit in both arguments. (Many popular
kernels have this property.) We study the geometric margins that can be achieved
when we represent a specific Boolean function $f$ by a classifier that employs
a reflection-invariant kernel. It turns out $\|\hat{f}\|_\infty$ is an upper bound on the
average margin. Furthermore, $\|\hat{f}\|_\infty^{-1}$ is a lower bound on the smallest
dimension of a feature space associated with a reflection-invariant kernel that
allows for a correct representation of $f$. This is, to the best of our knowledge,
the first paper that exhibits margin and dimension bounds for {\em specific functions}
(as opposed to {\em function families}). Several generalizations are considered as
well. The main mathematical results are presented in a setting with arbitrary finite
domains and a quite general notion of invariance.
