# Large-Scale Gaussian Processes via Alternating Projection

arXiv: https://arxiv.org/abs/2310.17137 · HTML: https://mlsanity.com/paper/2310.17137/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 57 references that are in the map.
- First posted on arXiv 26 Oct 2023.

## Builds on (most cited first, 24 of 24)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Mixed Precision Training](https://mlsanity.com/paper/1710.03740/) (2017)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [BinaryConnect: Training Deep Neural Networks with binary weights during propagations](https://mlsanity.com/paper/1511.00363/) (2015)
- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [Scalable Variational Gaussian Process Classification](https://mlsanity.com/paper/1411.2005/) (2014)
- [GPflow: A Gaussian process library using TensorFlow](https://mlsanity.com/paper/1610.08733/) (2016)
- [Exact Gaussian Processes on a Million Data Points](https://mlsanity.com/paper/1903.08114/) (2019)
- [Kernel Operations on the GPU, with Autodiff, without Memory Overflows](https://mlsanity.com/paper/2004.11127/) (2020)
- [A general framework for Vecchia approximations of Gaussian processes](https://mlsanity.com/paper/1708.06302/) (2017)
- [Constant-Time Predictive Distributions for Gaussian Processes](https://mlsanity.com/paper/1803.06058/) (2018)
- [Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection](https://mlsanity.com/paper/1506.00552/) (2015)
- [Preconditioning Kernel Matrices](https://mlsanity.com/paper/1602.06693/) (2016)
- [Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent](https://mlsanity.com/paper/2306.11589/) (2023)
- [Fast Matrix Square Roots with Applications to Gaussian Processes and Bayesian Optimization](https://mlsanity.com/paper/2006.11267/) (2020)
- [Posterior and Computational Uncertainty in Gaussian Processes](https://mlsanity.com/paper/2205.15449/) (2022)
- [Preconditioning for Scalable Gaussian Process Hyperparameter Optimization](https://mlsanity.com/paper/2107.00243/) (2021)
- [Tighter Bounds on the Log Marginal Likelihood of Gaussian Process Regression Using Conjugate Gradients](https://mlsanity.com/paper/2102.08314/) (2021)
- [Orthogonally Decoupled Variational Gaussian Processes](https://mlsanity.com/paper/1809.08820/) (2018)
- [A la Carte - Learning Fast Kernels](https://mlsanity.com/paper/1412.6493/) (2014)
- [Let's Make Block Coordinate Descent Converge Faster: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence](https://mlsanity.com/paper/1712.08859/) (2017)
- [Bias-Free Scalable Gaussian Processes via Randomized Truncations](https://mlsanity.com/paper/2102.06695/) (2021)
- [Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions](https://mlsanity.com/paper/1705.04768/) (2017)
- [Low-Precision Arithmetic for Fast Gaussian Processes](https://mlsanity.com/paper/2207.06856/) (2022)

## Built on by (most cited first, 11 of 11)

- [Stochastic Gradient Descent for Gaussian Processes Done Right](https://mlsanity.com/paper/2310.20581/) (2023)
- [Improving Linear System Solvers for Hyperparameter Optimisation in Iterative Gaussian Processes](https://mlsanity.com/paper/2405.18457/) (2024)
- [Scalable Gaussian Processes with Latent Kronecker Structure](https://mlsanity.com/paper/2506.06895/) (2025)
- [Bayes without Underfitting: Fully Correlated Deep Learning Posteriors via Alternating Projections](https://mlsanity.com/paper/2410.16901/) (2024)
- [Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project](https://mlsanity.com/paper/2505.13723/) (2025)
- [Recommendations for Baselines and Benchmarking Approximate Gaussian Processes](https://mlsanity.com/paper/2402.09849/) (2024)
- [HiGP: A high-performance Python package for Gaussian Process](https://mlsanity.com/paper/2503.02259/) (2025)
- [Gradients of Functions of Large Matrices](https://mlsanity.com/paper/2405.17277/) (2024)
- [Warm Start Marginal Likelihood Optimisation for Iterative Gaussian Processes](https://mlsanity.com/paper/2405.18328/) (2024)
- [Kernel Multigrid: Accelerate Back-fitting via Sparse Gaussian Process Regression](https://mlsanity.com/paper/2403.13300/) (2024)
- [Warm-Starting Iterative Gaussian Processes for Faster Sequential Inference](https://mlsanity.com/paper/2511.16340/) (2025)

## Abstract (arXiv)

Training and inference in Gaussian processes (GPs) require solving linear systems with n× n kernel matrices. To address the prohibitive O(n3) time complexity, recent work has employed fast iterative methods, like conjugate gradients (CG). However, as datasets increase in magnitude, the kernel matrices become increasingly ill-conditioned and still require O(n2) space without partitioning. Thus, while CG increases the size of datasets GPs can be trained on, modern datasets reach scales beyond its applicability. In this work, we propose an iterative method which only accesses subblocks of the kernel matrix, effectively enabling mini-batching. Our algorithm, based on alternating projection, has O(n) per-iteration time and space complexity, solving many of the practical challenges of scaling GPs to very large datasets. Theoretically, we prove the method enjoys linear convergence. Empirically, we demonstrate its fast convergence in practice and robustness to ill-conditioning. On large-scale benchmark datasets with up to four million data points, our approach accelerates GP training and inference by speed-up factors up to 27× and 72 ×, respectively, compared to CG.