Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel $k$-means Clustering
Authors: Taisuke Yasuda, David Woodruff, Manuel Fernandez
ICML 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, 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 Ω(ndλ eff/ε) where dλ eff is the effective statistical dimension, which is tight up to a log(dλ eff/ε) factor. For KKMC, our bound for finding a k-clustering achieving a relative error approximation of the objective function is Ω(nk/ε), which is tight up to a log(k/ε) factor. |
| Researcher Affiliation | Academia | 1Computer Science Department, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA 2Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA. |
| Pseudocode | No | The paper describes algorithms and their properties (e.g., in Section 5.1 'Proof overview'), but it does not include any formally labeled 'Pseudocode' or 'Algorithm' blocks with structured steps. |
| Open Source Code | No | The paper does not contain any explicit statements or links indicating that open-source code for the described methodology is available. |
| Open Datasets | No | This paper is theoretical, focusing on lower bounds and algorithm design. It defines 'hard input distribution' instances for its theoretical proofs (e.g., 'µKRR(n, J)', 'µKKMC(n, k, ε)') rather than using conventional public datasets for empirical training or evaluation. Therefore, it does not provide access information for a public dataset. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical experiments with data splits. Therefore, it does not provide details on validation dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not conduct empirical experiments that would require specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and focuses on mathematical proofs and algorithm design. It does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not conduct empirical experiments in the traditional sense. Therefore, it does not provide details about an experimental setup with hyperparameters or training settings. |