# Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel k-means Clustering

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2019.

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

- [Semi-supervised Active Regression](https://mlsanity.com/paper/2106.06676/) (2021)
- [Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming](https://mlsanity.com/paper/2310.19068/) (2023)

## Abstract (arXiv)

We present tight lower bounds on the number of kernel evaluations required to approximately solve kernel ridge regression (KRR) and kernel k-means clustering (KKMC) on n input points. For KRR, our bound for relative error approximation to the minimizer of the objective function is Omega(ndeffλ/varepsilon) where deffλ is the effective statistical dimension, which is tight up to a log(deffλ/varepsilon) factor. For KKMC, our bound for finding a k-clustering achieving a relative error approximation of the objective function is Omega(nk/varepsilon), which is tight up to a log(k/varepsilon) factor. Our KRR result resolves a variant of an open question of El Alaoui and Mahoney, asking whether the effective statistical dimension is a lower bound on the sampling complexity or not. Furthermore, for the important practical case when the input is a mixture of Gaussians, we provide a KKMC algorithm which bypasses the above lower bound.