# Analysis of regularized Nystr"om subsampling for regression functions of low smoothness

arXiv: https://arxiv.org/abs/1806.00826 · HTML: https://mlsanity.com/paper/1806.00826/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2018.

## Built on by (most cited first, 7 of 7)

- [On regularized Radon-Nikodym differentiation](https://mlsanity.com/paper/2308.07887/) (2023)
- [Optimal Kernel Quantile Learning with Random Features](https://mlsanity.com/paper/2408.13591/) (2024)
- [Nystr"om Regularization for Time Series Forecasting](https://mlsanity.com/paper/2111.07109/) (2021)
- [Adaptive Parameter Selection for Kernel Ridge Regression](https://mlsanity.com/paper/2312.05885/) (2023)
- [General regularization in covariate shift adaptation](https://mlsanity.com/paper/2307.11503/) (2023)
- [Sketching with Spherical Designs for Noisy Data Fitting on Spheres](https://mlsanity.com/paper/2303.04550/) (2023)
- [Scalable Operator Learning via Nystr"om Approximation With Denoising Applications](https://mlsanity.com/paper/2606.26652/) (2026)

## Abstract (arXiv)

This paper studies a Nystr"om 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"om subsampling can be realized with subquadratic cost maintaining the guaranteed learning rates.