Analysis of regularized Nyström subsampling for regression functions of low smoothness
This addresses a less understood but practically important problem in kernel methods for researchers and practitioners dealing with misspecified regression functions.
The paper tackles the problem of large kernel learning in the misspecified case, where target functions are not in the kernel Hilbert space, by analyzing a Nyström subsampling approach with general source conditions. It shows that for most source conditions, learning rate bounds can be achieved with a single regularization parameter, enabling subquadratic cost while maintaining guaranteed rates.
This paper studies a Nyström type subsampling approach to large kernel learning methods in the misspecified case, where the target function is not assumed to belong to the reproducing kernel Hilbert space generated by the underlying kernel. This case is less understood, in spite of its practical importance. To model such a case, the smoothness of target functions is described in terms of general source conditions. It is surprising that almost for the whole range of the source conditions, describing the misspecified case, the corresponding learning rate bounds can be achieved with just one value of the regularization parameter. This observation allows a formulation of mild conditions under which the plain Nyström subsampling can be realized with subquadratic cost maintaining the guaranteed learning rates.