On the complexity of PAC learning in Hilbert spaces

In general, the classification problem we are dealing with can be formulated as follows: Find a binary classifier which consistently classifies the training data such that the number of elementary operations involved in the description of the classifier is as small as possible. The intuition behind restricting the complexity of the classifier is based on the well-known Occam's razor principle; it has been proved (see e.g. Blumer et al. [1987, 1989]) that there is a relationship between the complexity of a classifier and its prediction accuracy, in the sense of the probably approximately correct (PAC) classification. We study this problem from the point of view of polyhedral classification, where the concept class to be learned consists of polyhedra in a given inner-product space. Polyhedral separability is always realizable by choosing a suitable kernel; i.e., our results are universally applicable to the general case of binary classification.