mlsanityData to 14 Oct 2026

Randomized sketches for kernels: Fast and optimal non-parametric regression

arXiv 1501.06195 ↗First posted 25 Jan 2015stat.ML cs.DS cs.LGcited by 31

Not on the map. Why?

Abstract (arXiv)

Kernel ridge regression (KRR) is a standard method for performing non-parametric regression over reproducing kernel Hilbert spaces. Given n samples, the time and space complexity of computing the KRR estimate scale as O(n3) and O(n2) respectively, and so is prohibitive in many cases. We propose approximations of KRR based on m-dimensional randomized sketches of the kernel matrix, and study how small the projection dimension m can be chosen while still preserving minimax optimality of the approximate KRR estimate. For various classes of randomized sketches, including those based on Gaussian and randomized Hadamard matrices, we prove that it suffices to choose the sketch dimension m proportional to the statistical dimension (modulo logarithmic factors). Thus, we obtain fast and minimax optimal approximations to the KRR estimate for non-parametric regression.

Key facts. Cited by 31 papers in the map (data through 14 Oct 2026). First posted on arXiv 25 Jan 2015.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 11; 2022: 8; 2023: 4; 2024: 4; 2025: 4.

31 papers.

Sort:

  1. 2021Skyformer: Remodel Self-Attention with Gaussian Kernel and Nystr"om Methodcited by 63
  2. 2022Optimally tackling covariate shift in RKHS-based nonparametric regressioncited by 54
  3. 2021Optimal policy evaluation using kernel-based temporal difference methodscited by 24
  4. 2022Spectral Regularized Kernel Two-Sample Testscited by 20
  5. 2022Regularized Stein Variational Gradient Flowcited by 19
  6. 2021Fast Statistical Leverage Score Approximation in Kernel Ridge Regressioncited by 14
  7. 2021Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionalitycited by 14
  8. 2023Towards a Unified Analysis of Kernel-based Methods Under Covariate Shiftcited by 13
  9. 2021Accumulation of Sub-Sampling Matrices with Applications to Statistical Computationcited by 10
  10. 2021Statistical Optimality and Computational Efficiency of Nystr"om Kernel PCAcited by 10
  11. 2024Any2Graph: Deep End-To-End Supervised Graph Prediction With An Optimal Transport Losscited by 7
  12. 2023Spectral Regularized Kernel Goodness-of-Fit Testscited by 6
19 more
  1. 2021Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequencescited by 5
  2. 2022Fast Kernel Methods for Generic Lipschitz Losses via p-Sparsified Sketchescited by 5
  3. 2022Global Convergence of SGD On Two Layer Neural Netscited by 5
  4. 2023Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernelscited by 5
  5. 2025Wild refitting for black box predictioncited by 5
  6. 2022Target alignment in truncated kernel ridge regressioncited by 4
  7. 2021An Efficient One-Class SVM for Anomaly Detection in the Internet of Thingscited by 3
  8. 2021Nystr"om Regularization for Time Series Forecastingcited by 3
  9. 2023Global Convergence of SGD For Logistic Loss on Two Layer Neural Netscited by 3
  10. 2025Reinforcement Learning with Continuous Actions Under Unmeasured Confoundingcited by 3
  11. 2024Deep Sketched Output Kernel Regression for Structured Predictioncited by 2
  12. 2021Statistical optimality conditions for compressive ensemblescited by 1
  13. 2022Generalized Kernel Regularized Least Squarescited by 1
  14. 2022A Unified Analysis of Multi-task Functional Linear Regression Models with Manifold Constraint and Composite Quadratic Penaltycited by 1
  15. 2024A Bound on the Maximal Marginal Degrees of Freedomcited by 1
  16. 2024Newton Meets Marchenko-Pastur: Massively Parallel Second-Order Optimization with Hessian Sketching and Debiasingcited by 1
  17. 2025Operator-Based Generalization Bound for Deep Learning: Insights on Multi-Task Learningcited by 1
  18. 2021Kernel-based estimation for partially functional linear model: Minimax rates and randomized sketchescited by 0
  19. 2025Inertial Quadratic Majorization Minimization with Application to Kernel Regularized Learningcited by 0