The Price of Linear Time: Error Analysis of Structured Kernel Interpolation
Authors: Alexander Moreno, Justin Xiao, Jonathan Mei
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | To empirically investigate derived theoretical error bounds for the Structured Kernel Interpolation (SKI) Gram matrix approximation, we conducted numerical experiments. Experiments focused on spectral norm error ||K K||2 behavior as a function of data points (n), total inducing points (mtotal), and dimensionality (d). ... All computations were performed using Py Torch and GPy Torch. Two primary sets of experiments were run for dimensionalities d {1, 2, 3}: 1. Error vs. mtotal (Fixed n): For fixed n (1000 for d = 1, 500 for d = 2, 250 for d = 3), we varied total inducing points mtotal ... and measured ||K K||2. 2. Error vs. n (Scaled mtotal): We varied n (50 to 1000) and scaled mtotal k nd/3 ... We then measured ||K K||2. The results are presented in Figure 1. |
| Researcher Affiliation | Collaboration | Alexander Moreno 1 Justin Xiao 2 Jonathan Mei 3 1MBZUAI 2Darwin AI 3Ion Q. Correspondence to: Alexander Moreno <EMAIL>. |
| Pseudocode | No | The paper does not contain any explicit sections or figures labeled 'Pseudocode' or 'Algorithm', nor are there any structured, code-like procedural steps presented. |
| Open Source Code | No | The paper states, 'All computations were performed using Py Torch and GPy Torch.' This indicates the tools used but does not explicitly state that the authors' implementation code for the methodology is being released or provided. There are no links to code repositories or statements about code availability in supplementary materials. |
| Open Datasets | No | Experiments used synthetic datasets with input points xi Rd drawn uniformly from [0, 1]d. |
| Dataset Splits | No | The paper describes generating synthetic datasets for experiments by varying parameters 'n' (sample size) and 'd' (dimensionality). It does not mention splitting any dataset into training, validation, or test sets in the conventional machine learning sense, as the evaluation focuses on Gram matrix spectral norm error on the generated data. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used to run the experiments, such as GPU or CPU models, memory, or processing speeds. It only mentions the software used for computations. |
| Software Dependencies | No | All computations were performed using Py Torch and GPy Torch. No version numbers are provided for these software libraries. |
| Experiment Setup | Yes | Experiments used synthetic datasets with input points xi Rd drawn uniformly from [0, 1]d. We employed a standard Radial Basis Function (RBF) kernel for all tests. SKI used cubic convolutional interpolation, consistent with our theoretical focus. ... Two primary sets of experiments were run for dimensionalities d {1, 2, 3}: 1. Error vs. mtotal (Fixed n): For fixed n (1000 for d = 1, 500 for d = 2, 250 for d = 3), we varied total inducing points mtotal (with mpd per dimension, so mtotal = md pd) and measured ||K K||2. 2. Error vs. n (Scaled mtotal): We varied n (50 to 1000) and scaled mtotal k nd/3 (k = 1.0), setting mpd = max(4, round(k1/dn1/3)). We then measured ||K K||2. |