Faster Kernel Interpolation for Gaussian Processes
- URL: http://arxiv.org/abs/2101.11751v1
- Date: Thu, 28 Jan 2021 00:09:22 GMT
- Title: Faster Kernel Interpolation for Gaussian Processes
- Authors: Mohit Yadav, Daniel Sheldon, Cameron Musco
- Abstract summary: Key challenge in scaling Process (GP) regression to massive datasets is that exact inference requires a dense n x n kernel matrix.
Structured kernel (SKI) is among the most scalable methods.
We show that SKI can be reduced to O(m log m) after a single O(n) time precomputation step.
We demonstrate speedups in practice for a wide range of m and n and apply the method to GP inference on a three-dimensional weather radar dataset with over 100 million points.
- Score: 30.04235162264955
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A key challenge in scaling Gaussian Process (GP) regression to massive
datasets is that exact inference requires computation with a dense n x n kernel
matrix, where n is the number of data points. Significant work focuses on
approximating the kernel matrix via interpolation using a smaller set of m
inducing points. Structured kernel interpolation (SKI) is among the most
scalable methods: by placing inducing points on a dense grid and using
structured matrix algebra, SKI achieves per-iteration time of O(n + m log m)
for approximate inference. This linear scaling in n enables inference for very
large data sets; however the cost is per-iteration, which remains a limitation
for extremely large n. We show that the SKI per-iteration time can be reduced
to O(m log m) after a single O(n) time precomputation step by reframing SKI as
solving a natural Bayesian linear regression problem with a fixed set of m
compact basis functions. With per-iteration complexity independent of the
dataset size n for a fixed grid, our method scales to truly massive data sets.
We demonstrate speedups in practice for a wide range of m and n and apply the
method to GP inference on a three-dimensional weather radar dataset with over
100 million points.
Related papers
- High-Dimensional Gaussian Process Regression with Soft Kernel Interpolation [0.8057006406834466]
We introduce Soft Kernel Interpolation (SoftKI) designed for scalable Process (GP) regression on high-dimensional datasets.
Inspired by Structured Interpolation (SKI), which approximates a GP kernel via a structured lattice, SoftKI approximates a kernel via softmax from a smaller number of learned points.
By abandoning the lattice structure used in SKI-based methods, SoftKI separates the cost of forming an approximate GP kernel from the dimensionality of the data, making it well-suited for high-dimensional datasets.
arXiv Detail & Related papers (2024-10-28T18:13:56Z) - Polynomial-Time Solutions for ReLU Network Training: A Complexity
Classification via Max-Cut and Zonotopes [70.52097560486683]
We prove that the hardness of approximation of ReLU networks not only mirrors the complexity of the Max-Cut problem but also, in certain special cases, exactly corresponds to it.
In particular, when $epsilonleqsqrt84/83-1approx 0.006$, we show that it is NP-hard to find an approximate global dataset of the ReLU network objective with relative error $epsilon$ with respect to the objective value.
arXiv Detail & Related papers (2023-11-18T04:41:07Z) - Large-Scale Gaussian Processes via Alternating Projection [23.79090469387859]
We propose an iterative method which only accesses subblocks of the kernel matrix, effectively enabling mini-batching.
Our algorithm, based on alternating projection, has $mathcalO(n)$ per-iteration time and space complexity, solving many of the practical challenges of scaling GPs to very large datasets.
arXiv Detail & Related papers (2023-10-26T04:20:36Z) - Kernel Interpolation with Sparse Grids [25.167018679176838]
We propose the use of sparse grids within the Structured kernel amenable (SKI) framework.
These grids enable accurate algebra, but with a number of points growing more slowly with dimension.
We show that SKI can be scaled to higher dimensions while maintaining accuracy.
arXiv Detail & Related papers (2023-05-23T18:17:49Z) - Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
We propose a novel algorithm that uses a random feature approximation (RFA) of the Neural Network Gaussian Process (NNGP) kernel.
Our algorithm provides at least a 100-fold speedup over KIP and can run on a single GPU.
Our new method, termed an RFA Distillation (RFAD), performs competitively with KIP and other dataset condensation algorithms in accuracy over a range of large-scale datasets.
arXiv Detail & Related papers (2022-10-21T15:56:13Z) - The Fast Kernel Transform [21.001203328543006]
We propose the Fast Kernel Transform (FKT), a general algorithm to compute matrix-vector multiplications for datasets in moderate dimensions with quasilinear complexity.
The FKT is easily applied to a broad class of kernels, including Gaussian, Matern, and Rational Quadratic covariance functions and physically motivated Green's functions.
We illustrate the efficacy and versatility of the FKT by providing timing and accuracy benchmarks and by applying it to scale the neighborhood embedding (t-SNE) and Gaussian processes to large real-world data sets.
arXiv Detail & Related papers (2021-06-08T16:15:47Z) - SigGPDE: Scaling Sparse Gaussian Processes on Sequential Data [16.463077353773603]
We develop SigGPDE, a new scalable sparse variational inference framework for Gaussian Processes (GPs) on sequential data.
We show that the gradients of the GP signature kernel are solutions of a hyperbolic partial differential equation (PDE)
This theoretical insight allows us to build an efficient back-propagation algorithm to optimize the ELBO.
arXiv Detail & Related papers (2021-05-10T09:10:17Z) - Random Features for the Neural Tangent Kernel [57.132634274795066]
We propose an efficient feature map construction of the Neural Tangent Kernel (NTK) of fully-connected ReLU network.
We show that dimension of the resulting features is much smaller than other baseline feature map constructions to achieve comparable error bounds both in theory and practice.
arXiv Detail & Related papers (2021-04-03T09:08:12Z) - Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
We propose a new formulation for the bundle adjustment problem which relies on nullspace marginalization of landmark variables by QR decomposition.
Our approach, which we call square root bundle adjustment, is algebraically equivalent to the commonly used Schur complement trick.
We show in real-world experiments with the BAL datasets that even in single precision the proposed solver achieves on average equally accurate solutions.
arXiv Detail & Related papers (2021-03-02T16:26:20Z) - Multipole Graph Neural Operator for Parametric Partial Differential
Equations [57.90284928158383]
One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data.
We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity.
Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
arXiv Detail & Related papers (2020-06-16T21:56:22Z) - Improved guarantees and a multiple-descent curve for Column Subset
Selection and the Nystr\"om method [76.73096213472897]
We develop techniques which exploit spectral properties of the data matrix to obtain improved approximation guarantees.
Our approach leads to significantly better bounds for datasets with known rates of singular value decay.
We show that both our improved bounds and the multiple-descent curve can be observed on real datasets simply by varying the RBF parameter.
arXiv Detail & Related papers (2020-02-21T00:43:06Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.