The regularized least squares algorithm and the problem of learning halfspaces

We provide sample complexity of the problem of learning halfspaces with monotonic noise, using the regularized least squares algorithm in the reproducing kernel Hilbert spaces (RKHS) framework.

Research highlights► We provide the sample complexity for the problem of learning halfspaces under monotonic noise using the regularized least squares algorithm. ► We give the proof using the reproducing kernel Hilbert space (RKHS) framework. ► We show a connection between the RKHS framework and traditional computational learning theory.