# Less is More: Nystr"om Computational Regularization

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

## Key facts

- Cited by 91 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2015.

## Built on by (most cited first, 30 of 91)

- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [Reproducing Kernel Hilbert Space, Mercer's Theorem, Eigenfunctions, Nystr"om Method, and Use of Kernels in Machine Learning: Tutorial and Survey](https://mlsanity.com/paper/2106.08443/) (2021)
- [Information Theory with Kernel Methods](https://mlsanity.com/paper/2202.08545/) (2022)
- [Hybrid Random Features](https://mlsanity.com/paper/2110.04367/) (2021)
- [Nystr"om Kernel Mean Embeddings](https://mlsanity.com/paper/2201.13055/) (2022)
- [Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithm](https://mlsanity.com/paper/2312.07186/) (2023)
- [Learning new physics efficiently with nonparametric methods](https://mlsanity.com/paper/2204.02317/) (2022)
- [Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learning](https://mlsanity.com/paper/2202.04005/) (2022)
- [Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processes](https://mlsanity.com/paper/2106.01121/) (2021)
- [Estimating Koopman operators with sketching to provably learn large scale dynamical systems](https://mlsanity.com/paper/2306.04520/) (2023)
- [Fast Statistical Leverage Score Approximation in Kernel Ridge Regression](https://mlsanity.com/paper/2103.05238/) (2021)
- [Near-optimal estimation of smooth transport maps with kernel sums-of-squares](https://mlsanity.com/paper/2112.01907/) (2021)
- [Efficient Hyperparameter Tuning for Large Scale Kernel Ridge Regression](https://mlsanity.com/paper/2201.06314/) (2022)
- [Statistical Optimality and Computational Efficiency of Nystr"om Kernel PCA](https://mlsanity.com/paper/2105.08875/) (2021)
- [Generalized equivalences between subsampling and ridge regularization](https://mlsanity.com/paper/2305.18496/) (2023)
- [On regularized Radon-Nikodym differentiation](https://mlsanity.com/paper/2308.07887/) (2023)
- [Sampling from Arbitrary Functions via PSD Models](https://mlsanity.com/paper/2110.10527/) (2021)
- [Fast kernel methods for Data Quality Monitoring as a goodness-of-fit test](https://mlsanity.com/paper/2303.05413/) (2023)
- [Nonlinear Meta-Learning Can Guarantee Faster Rates](https://mlsanity.com/paper/2307.10870/) (2023)
- [A Theoretical Analysis of the Test Error of Finite-Rank Kernel Ridge Regression](https://mlsanity.com/paper/2310.00987/) (2023)
- [Nonparametric Instrumental Regression via Kernel Methods is Minimax Optimal](https://mlsanity.com/paper/2411.19653/) (2024)
- [Conditioning of Random Feature Matrices: Double Descent and Generalization Error](https://mlsanity.com/paper/2110.11477/) (2021)
- [Operator World Models for Reinforcement Learning](https://mlsanity.com/paper/2406.19861/) (2024)
- [ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions](https://mlsanity.com/paper/2106.12231/) (2021)
- [Mean Nystr"om Embeddings for Adaptive Compressive Learning](https://mlsanity.com/paper/2110.10996/) (2021)
- [Fast Instrument Learning with Faster Rates](https://mlsanity.com/paper/2205.10772/) (2022)
- [Sum-of-Squares Relaxations for Information Theory and Variational Inference](https://mlsanity.com/paper/2206.13285/) (2022)
- [The Galerkin method beats Graph-Based Approaches for Spectral Algorithms](https://mlsanity.com/paper/2306.00742/) (2023)
- [Online nonparametric regression with Sobolev kernels](https://mlsanity.com/paper/2102.03594/) (2021)
- [Fast Kernel Methods for Generic Lipschitz Losses via p-Sparsified Sketches](https://mlsanity.com/paper/2206.03827/) (2022)

## Abstract (arXiv)

We study Nystr"om type subsampling approaches to large scale kernel methods, and prove learning bounds in the statistical learning setting, where random sampling and high probability estimates are considered. In particular, we prove that these approaches can achieve optimal learning bounds, provided the subsampling level is suitably chosen. These results suggest a simple incremental variant of Nystr"om Kernel Regularized Least Squares, where the subsampling level implements a form of computational regularization, in the sense that it controls at the same time regularization and computations. Extensive experimental analysis shows that the considered approach achieves state of the art performances on benchmark large scale datasets.