Research map / Learning theory and algorithms / Kernels and regression theory
Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel $k$-means Clustering
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require a (1+ε)-relative approximation to the KRR minimizer on worst-case instances | Kernel ridge regression · KRR, worst-case instances | kernel evaluations required: Ω(nd_eff^λ/ε) lower bound; O((nd_eff^λ/ε) log(nd_eff^λ/ε)) upper bound | Mixed |
| Require a (1+ε)-relative approximation to the clustering objective on worst-case instances | Kernel k-means · Kernel k-means, worst-case instances | kernel queries required: Ω(nk/ε) lower bound; O((nk/ε) log(k/ε)) upper bound | Mixed |
| Restrict inputs to the stated mixture-of-Gaussians setting and use sketches of the input points | Kernel k-means · Kernel k-means, Gaussian mixtures | kernel queries: Ω(nk/ε) worst-case lower bound; (n/ε) poly(log(k/ε)) upper bound | Helped |
| Approximate the optimal cost rather than output an approximate clustering | Kernel k-means · Kernel k-means, cost approximation | kernel queries required: Ω(nk) lower bound; O(nk) + poly(k,1/ε,log n) upper bound | Mixed |
Closest papers by meaning
- A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression (NeurIPS 2024 · similarity 0.88)
- Kernel Regression in Structured Non-IID Settings: Theory and Implications for Denoising Score Learning (NeurIPS 2025 · similarity 0.88)
- Supervised Kernel Thinning (NeurIPS 2024 · similarity 0.87)
- Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrum (ICML 2024 · similarity 0.87)
- Scalable Multiple Kernel Clustering: Learning Clustering Structure from Expectation (ICML 2024 · similarity 0.87)
- Kernel conditional tests from learning-theoretic bounds (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.