Fast Sketching of Polynomial Kernels of Polynomial Degree
Authors: Zhao Song, David Woodruff, Zheng Yu, Lichen Zhang
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We develop an efficient algorithm that computes a sketch of the polynomial kernel of degree p in time linear in p2 and nearly linear in nd. Our algorithm only uses two distinct sketches compared to the O(p) independent sketches of (Ahle et al., 2020). This enables us to use repeated powering to compute our sketch very efficiently. We characterize kernel matrices by considering their Taylor series, and provide different algorithmic schemes to solve them. Our characterization includes a family of interesting and popular kernels. We also use this sketch as a preconditioner for solving linear systems involving a kernel matrix, and we extend our sketch to solve kernel ridge regression, by composing it with another sketch that depends on the statistical dimension. |
| Researcher Affiliation | Academia | 1Princeton University and Institute for Advanced Study 2Carnegie Mellon University 3Princeton University 4Carnegie Mellon University. |
| Pseudocode | Yes | Algorithm 1 Our algorithm for sketching the vector x p with limited randomness. |
| Open Source Code | No | The paper does not provide any statements about open-source code availability or links to code repositories. |
| Open Datasets | No | The paper is theoretical, analyzing algorithmic complexity and properties. It does not describe experiments run on specific datasets, thus no dataset is mentioned as being publicly available for such use. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments with dataset splits. Therefore, no information on training, validation, or test splits is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments that would require specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not detail the software environment or dependencies with version numbers that would be required to reproduce experiments. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and analysis. It does not describe any specific experimental setup details such as hyperparameters or training configurations. |