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

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

## Key facts

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

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

- [Skyformer: Remodel Self-Attention with Gaussian Kernel and Nystr"om Method](https://mlsanity.com/paper/2111.00035/) (2021)
- [Optimally tackling covariate shift in RKHS-based nonparametric regression](https://mlsanity.com/paper/2205.02986/) (2022)
- [Optimal policy evaluation using kernel-based temporal difference methods](https://mlsanity.com/paper/2109.12002/) (2021)
- [Spectral Regularized Kernel Two-Sample Tests](https://mlsanity.com/paper/2212.09201/) (2022)
- [Regularized Stein Variational Gradient Flow](https://mlsanity.com/paper/2211.07861/) (2022)
- [Fast Statistical Leverage Score Approximation in Kernel Ridge Regression](https://mlsanity.com/paper/2103.05238/) (2021)
- [Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality](https://mlsanity.com/paper/2105.07291/) (2021)
- [Towards a Unified Analysis of Kernel-based Methods Under Covariate Shift](https://mlsanity.com/paper/2310.08237/) (2023)
- [Accumulation of Sub-Sampling Matrices with Applications to Statistical Computation](https://mlsanity.com/paper/2103.04031/) (2021)
- [Statistical Optimality and Computational Efficiency of Nystr"om Kernel PCA](https://mlsanity.com/paper/2105.08875/) (2021)
- [Any2Graph: Deep End-To-End Supervised Graph Prediction With An Optimal Transport Loss](https://mlsanity.com/paper/2402.12269/) (2024)
- [Spectral Regularized Kernel Goodness-of-Fit Tests](https://mlsanity.com/paper/2308.04561/) (2023)
- [Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences](https://mlsanity.com/paper/2112.05359/) (2021)
- [Fast Kernel Methods for Generic Lipschitz Losses via p-Sparsified Sketches](https://mlsanity.com/paper/2206.03827/) (2022)
- [Global Convergence of SGD On Two Layer Neural Nets](https://mlsanity.com/paper/2210.11452/) (2022)
- [Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels](https://mlsanity.com/paper/2302.10128/) (2023)
- [Wild refitting for black box prediction](https://mlsanity.com/paper/2506.21460/) (2025)
- [Target alignment in truncated kernel ridge regression](https://mlsanity.com/paper/2206.14255/) (2022)
- [An Efficient One-Class SVM for Anomaly Detection in the Internet of Things](https://mlsanity.com/paper/2104.11146/) (2021)
- [Nystr"om Regularization for Time Series Forecasting](https://mlsanity.com/paper/2111.07109/) (2021)
- [Global Convergence of SGD For Logistic Loss on Two Layer Neural Nets](https://mlsanity.com/paper/2309.09258/) (2023)
- [Reinforcement Learning with Continuous Actions Under Unmeasured Confounding](https://mlsanity.com/paper/2505.00304/) (2025)
- [Deep Sketched Output Kernel Regression for Structured Prediction](https://mlsanity.com/paper/2406.09253/) (2024)
- [Statistical optimality conditions for compressive ensembles](https://mlsanity.com/paper/2106.01092/) (2021)
- [Generalized Kernel Regularized Least Squares](https://mlsanity.com/paper/2209.14355/) (2022)
- [A Unified Analysis of Multi-task Functional Linear Regression Models with Manifold Constraint and Composite Quadratic Penalty](https://mlsanity.com/paper/2211.04874/) (2022)
- [A Bound on the Maximal Marginal Degrees of Freedom](https://mlsanity.com/paper/2402.12885/) (2024)
- [Newton Meets Marchenko-Pastur: Massively Parallel Second-Order Optimization with Hessian Sketching and Debiasing](https://mlsanity.com/paper/2410.01374/) (2024)
- [Operator-Based Generalization Bound for Deep Learning: Insights on Multi-Task Learning](https://mlsanity.com/paper/2512.19184/) (2025)
- [Kernel-based estimation for partially functional linear model: Minimax rates and randomized sketches](https://mlsanity.com/paper/2110.09042/) (2021)

## 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.