Research map / Learning theory and algorithms / Kernels and regression theory
The Price of Linear Time: Error Analysis of Structured Kernel Interpolation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives elementwise and spectral-norm error bounds for Structured Kernel Interpolation (SKI) Gram matrices with cubic convolutional interpolation and propagates them to GP hyperparameter MLE, log-likelihood, and posterior, identifying a d<=3 vs d>3 regime for linear-time scaling.
Problem
SKI scales Gaussian processes via inducing-point interpolation with claimed O(n) cost, but lacks rigorous error analysis: how many inducing points are needed for a given kernel-matrix error, and when is the cost truly linear, plus how errors affect likelihood, hyperparameter MLE, and posterior infer
Approach
Bounds the SKI kernel error via tensor-product cubic convolutional interpolation (error growing as c^d h^3), converts it to spectral-norm Gram-matrix error, and propagates this through the log-likelihood, gradient, and one-step MLE analysis, yielding a dimension-dependent condition (d<=3 vs d>3) for linear-time SKI.
Key results
- Proves elementwise SKI kernel error O(c^{2d} h^3) for tensor-product cubic convolutional interpolation, giving spectral-norm Gram error O(n c^{2d} h^3).
- Shows for d<=3 SKI with cubic interpolation is linear-time for sufficiently large n at any fixed error, while for d>3 the error must grow with n to keep linear time.
- Derives log-likelihood difference bound and one-step MLE closeness results under strong concavity assumptions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase sample size while decreasing the SKI Gram-matrix error | SKI with cubic interpolation · SKI computational complexity, d≤3 | computational complexity: O(n) | Helped |
| Maintain linear-time complexity as sample size increases | SKI with cubic interpolation · SKI computational complexity, d>3 | SKI Gram-matrix spectral-norm error: n (\log n)^{3/d}/n^{3/d} | Hurt |
Surprising findings
- For d>3 the error tolerance must increase with sample size to maintain linear time complexity.
Limitations
- Constants (c, K', C) are not explicit and depend on kernel and interpolation scheme.
- No empirical experiments validating the bounds.
- Relies on strong concavity and local identifiability assumptions for MLE results.
Experimental setup
Builds on: Structured Kernel Interpolation Nystrom approximation sparse variational GP
Closest papers by meaning
- Kernel Interpolation with Sparse Grids (NeurIPS 2022 · similarity 0.94)
- SKIing on Simplices: Kernel Interpolation on the Permutohedral Lattice for Scalable Gaussian Processes (ICML 2021 · similarity 0.91)
- Scalable Gaussian Process Separation for Kernels with a Non-Stationary Phase (ICML 2020 · similarity 0.87)
- gp2Scale: A Class of Compactly Supported Non-Stationary Kernels and Distributed Computing for Exact Gaussian Processes on 10 Million Data Points (ICML 2026 · similarity 0.87)
- Sparse Gaussian Processes: Structured Approximations and Power-EP Revisited (NeurIPS 2025 · similarity 0.85)
- Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality (NeurIPS 2024 · similarity 0.84)
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.