Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project
Not on the map. Why?
Abstract (arXiv)
Gaussian processes (GPs) play an essential role in biostatistics, scientific machine learning, and Bayesian optimization for their ability to provide probabilistic predictions and model uncertainty. However, GP inference struggles to scale to large datasets (which are common in modern applications), since it requires the solution of a linear system whose size scales quadratically with the number of samples in the dataset. We propose an approximate, distributed, accelerated sketch-and-project algorithm (textttADASAP) for solving these linear systems, which improves scalability. We use the theory of determinantal point processes to show that the posterior mean induced by sketch-and-project rapidly converges to the true posterior mean. In particular, this yields the first efficient, condition number-free algorithm for estimating the posterior mean along the top spectral basis functions, showing that our approach is principled for GP inference. textttADASAP outperforms state-of-the-art solvers based on conjugate gradient and coordinate descent across several benchmark datasets and a large-scale Bayesian optimization task. Moreover, textttADASAP scales to a dataset with > 3 · 108 samples, a feat which has not been accomplished in the literature.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 50 of its 82 references that are in the map. First posted on arXiv 19 May 2025.
Builds on
50 of 82 references.
References · 50
- 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
- 2018GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Accelerationcited by 609
- 2013Gaussian Processes for Big Datacited by 383
- 2014Scalable Variational Gaussian Process Classificationcited by 228
- 2018Gaussian Processes and Kernel Methods: A Review on Connections and Equivalencescited by 192
- 2015Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)cited by 177
- 2016Generalization Properties of Learning with Random Featurescited by 164
- 2020Efficiently Sampling Functions from Gaussian Process Posteriorscited by 127
- 2019Exact Gaussian Processes on a Million Data Pointscited by 119
- 2020Kernel Operations on the GPU, with Autodiff, without Memory Overflowscited by 104
- 2015Less is More: Nystr"om Computational Regularizationcited by 91
- 2016Variational Fourier features for Gaussian processescited by 85
38 more
- 2015Bayesian optimization for materials designcited by 80
- 2013Revisiting the Nystrom Method for Improved Large-Scale Machine Learningcited by 77
- 2017Parallel and Distributed Thompson Sampling for Large-scale Accelerated Exploration of Chemical Spacecited by 76
- 2020Pathwise Conditioning of Gaussian Processescited by 64
- 2018Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spacescited by 59
- 2016Faster Kernel Ridge Regression Using Sketching and Preconditioningcited by 44
- 2020Determinantal Point Processes in Randomized Numerical Linear Algebracited by 41
- 2019RSN: Randomized Subspace Newtoncited by 34
- 2015Convergence rates of sub-sampled Newton methodscited by 33
- 2016Preconditioning Kernel Matricescited by 33
- 2018Approximation beats concentration? An approximation view on inference with smooth radial kernelscited by 33
- 2017Diving into the shallows: a computational perspective on large-scale shallow learningcited by 31
- 2023Sparse Cholesky Factorization for Solving Nonlinear PDEs via Gaussian Processescited by 31
- 2023Sampling from Gaussian Process Posteriors using Stochastic Gradient Descentcited by 27
- 2017Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Datacited by 23
- 2020Stochastic Subspace Cubic Newton Methodcited by 21
- 2015SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimizationcited by 19
- 2022Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decompositioncited by 19
- 2020Sampling from a k-DPP without looking at all itemscited by 17
- 2023Stochastic Gradient Descent for Gaussian Processes Done Rightcited by 17
- 2014Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexitycited by 14
- 2019Convergence Analysis of Block Coordinate Algorithms with Determinantal Samplingcited by 12
- 2023Solving Dense Linear Systems Faster Than via Preconditioningcited by 12
- 2018Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimizationcited by 11
- 2023PROMISE: Preconditioned Stochastic Optimization Methods by Incorporating Scalable Curvature Estimatescited by 11
- 2023Large-Scale Gaussian Processes via Alternating Projectioncited by 11
- 2020Randomized Kaczmarz converges along small singular vectorscited by 9
- 2023Robust, randomized preconditioning for kernel ridge regressioncited by 9
- 2019A Randomized Coordinate Descent Method with Volume Samplingcited by 8
- 2022Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independencecited by 8
- 2022SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimatescited by 8
- 2024Have ASkotch: A Neat Solution for Large-scale Kernel Ridge Regressioncited by 8
- 2024Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systemscited by 7
- 2025Randomized Kaczmarz Methods with Beyond-Krylov Convergencecited by 7
- 2016Fast spatial Gaussian process maximum likelihood estimation via skeletonization factorizationscited by 6
- 2020Isotropy and Log-Concave Polynomials: Accelerated Sampling and High-Precision Counting of Matroid Basescited by 5
- 2024Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Choleskycited by 5
- 2017Breaking Locality Accelerates Block Gauss-Seidelcited by 4
Built on by
Citing papers per year: 2026: 3.
3 papers.