AAAI 2023technical0 citations
On the Complexity of PAC Learning in Hilbert Spaces
Abstract
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 − ε of the distribution, with a probability of at least 1 − δ, where ε and δ are given parameters. Also, as a corollary, we improve some previous bounds for polyhedral classification in finite-dimensional spaces.
BibTeX
@article{Chubanov_2023, title={On the Complexity of PAC Learning in Hilbert Spaces}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/25878}, DOI={10.1609/aaai.v37i6.25878}, abstractNote={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 − ε of the distribution, with a probability of at least 1 − δ,
where ε and δ are given parameters. Also, as a corollary, we
improve some previous bounds for polyhedral classification
in finite-dimensional spaces.}, number={6}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Chubanov, Sergei}, year={2023}, month={Jun.}, pages={7202-7209} }