On the complexity of PAC learning in Hilbert 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 - \delta,$ where $\varepsilon$ and $\delta$ are given parameters. Also, as a corollary, we improve some previous bounds for polyhedral classification in finite-dimensional spaces.
Code (0)
등록된 구현이 없습니다.
Tasks
Binary ClassificationClassificationPAC learningSimilar Papers 제목 키워드 기반
Irregular Sampling of High-Dimensional Functions in Reproducing Kernel Hilbert Spaces
We develop sampling formulas for high-dimensional functions in reproducing kernel Hilbert spaces, where we rely on irregular samples that are taken at determining sequences of data points. We place particular emphasis on…
Learning Operators with Stochastic Gradient Descent in General Hilbert Spaces
This study investigates leveraging stochastic gradient descent (SGD) to learn operators between general Hilbert spaces. We propose weak and strong regularity conditions for the target operator to depict its intrinsic str…
Operator learningvalidWhich Spaces can be Embedded in $L_p$-type Reproducing Kernel Banach Space? A Characterization via Metric Entropy
In this paper, we establish a novel connection between the metric entropy growth and the embeddability of function spaces into reproducing kernel Hilbert/Banach spaces. Metric entropy characterizes the information comple…
CoVariance Filters and Neural Networks over Hilbert Spaces
CoVariance Neural Networks (VNNs) perform graph convolutions on the empirical covariance matrix of signals defined over finite-dimensional Hilbert spaces, motivated by robustness and transferability properties. Yet, litt…
Learning in Hilbert vs. Banach Spaces: A Measure Embedding Viewpoint
The goal of this paper is to investigate the advantages and disadvantages of learning in Banach spaces over Hilbert spaces. While many works have been carried out in generalizing Hilbert methods to Banach spaces, in this…