mlsanityData to 7 Oct 2026

Less is More: Nystr"om Computational Regularization

arXiv 1507.04717 ↗First posted 16 Jul 2015stat.ML cs.LGcited by 89

Not on the map. Why?

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.

Key facts. Cited by 89 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Jul 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 23; 2022: 16; 2023: 20; 2024: 13; 2025: 10; 2026: 7.

89 papers.

Sort:

By area:

  1. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
  2. 2022Information Theory with Kernel Methodscited by 37
  3. 2021Reproducing Kernel Hilbert Space, Mercer's Theorem, Eigenfunctions, Nystr"om Method, and Use of Kernels in Machine Learning: Tutorial and Surveycited by 36
  4. 2021Hybrid Random Featurescited by 25
  5. 2023Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithmcited by 22
  6. 2022Nystr"om Kernel Mean Embeddingscited by 21
  7. 2022Learning new physics efficiently with nonparametric methodscited by 20
  8. 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
  9. 2021Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processescited by 17
  10. 2023Estimating Koopman operators with sketching to provably learn large scale dynamical systemscited by 15
  11. 2021Fast Statistical Leverage Score Approximation in Kernel Ridge Regressioncited by 14
  12. 2021Near-optimal estimation of smooth transport maps with kernel sums-of-squarescited by 12
38 more
  1. 2022Efficient Hyperparameter Tuning for Large Scale Kernel Ridge Regressioncited by 11
  2. 2021Statistical Optimality and Computational Efficiency of Nystr"om Kernel PCAcited by 10
  3. 2023Generalized equivalences between subsampling and ridge regularizationcited by 10
  4. 2023On regularized Radon-Nikodym differentiationcited by 10
  5. 2021Sampling from Arbitrary Functions via PSD Modelscited by 8
  6. 2023Nonlinear Meta-Learning Can Guarantee Faster Ratescited by 8
  7. 2023A Theoretical Analysis of the Test Error of Finite-Rank Kernel Ridge Regressioncited by 8
  8. 2021Conditioning of Random Feature Matrices: Double Descent and Generalization Errorcited by 7
  9. 2023Fast kernel methods for Data Quality Monitoring as a goodness-of-fit testcited by 7
  10. 2024Operator World Models for Reinforcement Learningcited by 7
  11. 2024Nonparametric Instrumental Regression via Kernel Methods is Minimax Optimalcited by 7
  12. 2021Mean Nystr"om Embeddings for Adaptive Compressive Learningcited by 6
  13. 2022Fast Instrument Learning with Faster Ratescited by 6
  14. 2022Sum-of-Squares Relaxations for Information Theory and Variational Inferencecited by 6
  15. 2023The Galerkin method beats Graph-Based Approaches for Spectral Algorithmscited by 6
  16. 2021Online nonparametric regression with Sobolev kernelscited by 5
  17. 2021ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitionscited by 5
  18. 2022Fast Kernel Methods for Generic Lipschitz Losses via p-Sparsified Sketchescited by 5
  19. 2022Vector-Valued Least-Squares Regression under Output Regularity Assumptionscited by 5
  20. 2023Kernelized Diffusion mapscited by 5
  21. 2023Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernelscited by 5
  22. 2023Label Shift Quantification with Robustness Guarantees via Distribution Feature Matchingcited by 5
  23. 2023Nonparametric Linear Feature Learning in Regression Through Regularisationcited by 5
  24. 2022Target alignment in truncated kernel ridge regressioncited by 4
  25. 2024Nystr"om Kernel Stein Discrepancycited by 4
  26. 2025Random Forest Autoencoders for Guided Representation Learningcited by 4
  27. 2025Computational Efficiency under Covariate Shift in Kernel Ridge Regressioncited by 4
  28. 2025Comparing Generative Models with the New Physics Learning Machinecited by 4
  29. 2025Learning to Validate Generative Models: a Goodness-of-Fit Approachcited by 4
  30. 2021An Efficient One-Class SVM for Anomaly Detection in the Internet of Thingscited by 3
  31. 2021Variational Gaussian Processes: A Functional Analysis Viewcited by 3
  32. 2021Nystr"om Regularization for Time Series Forecastingcited by 3
  33. 2022Efficient Kernel UCB for Contextual Banditscited by 3
  34. 2022Active Labeling: Streaming Stochastic Gradientscited by 3
  35. 2024On the Approximation of Kernel functionscited by 3
  36. 2024Learning to Embed Distributions via Maximum Kernel Entropycited by 3
  37. 2025Turbocharging Gaussian Process Inference with Approximate Sketch-and-Projectcited by 3
  38. 2021Kernel PCA with the Nystr"om methodcited by 2

50 most cited of 89 All 89 (JSON)