Lower Bounds on the Vapnik-Chervonenkis Dimension of Convex Polytope Classifiers

In statistical learning theory, the Vapnik-Chervonenkis (VC) dimension is an important combinatorial property of classifier families. In this paper we examine the case of convex polytope classification, i.e. when the separation of the two classes is done by a convex surface consisting of linear segments. We collect the known facts about the VC dimension of convex polytope classifiers with n facets in R^d and present two new lower bounds (one for the general case and one for the special case d = 4).