On the complexity of PAC learning in Hilbert spaces
This work addresses binary classification for machine learning practitioners by generalizing polyhedral learning to infinite-dimensional spaces, though it appears incremental as it builds on well-studied finite-dimensional methods.
The paper tackles the problem of binary classification by learning convex polyhedra in Hilbert spaces, proposing an algorithm that achieves a classification accuracy of at least 1-ε with probability at least 1-δ for given parameters ε and δ, and improves previous bounds for finite-dimensional spaces.
We study the problem of binary classification from the point of view of learning convex polyhedra in Hilbert spaces, to which one can reduce any binary classification problem. The problem of learning convex polyhedra in finite-dimensional spaces is sufficiently well studied in the literature. We generalize this problem to that in a Hilbert space and propose an algorithm for learning a polyhedron which correctly classifies at least $1- \varepsilon$ of the distribution, with a probability of at least $1 - δ,$ where $\varepsilon$ and $δ$ are given parameters. Also, as a corollary, we improve some previous bounds for polyhedral classification in finite-dimensional spaces.