# Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 47 references that are in the map.
- First posted on arXiv 20 Jun 2023.

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

- [An overview of gradient descent optimization algorithms](https://mlsanity.com/paper/1609.04747/) (2016)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Gaussian Processes for Big Data](https://mlsanity.com/paper/1309.6835/) (2013)
- [Stochastic Gradient Descent as Approximate Bayesian Inference](https://mlsanity.com/paper/1704.04289/) (2017)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)](https://mlsanity.com/paper/1503.01057/) (2015)
- [Efficiently Sampling Functions from Gaussian Process Posteriors](https://mlsanity.com/paper/2002.09309/) (2020)
- [Exact Gaussian Processes on a Million Data Points](https://mlsanity.com/paper/1903.08114/) (2019)
- [Bayesian Deep Learning via Subnetwork Inference](https://mlsanity.com/paper/2010.14689/) (2020)
- [On the Error of Random Fourier Features](https://mlsanity.com/paper/1506.02785/) (2015)
- [Parallel and Distributed Thompson Sampling for Large-scale Accelerated Exploration of Chemical Space](https://mlsanity.com/paper/1706.01825/) (2017)
- [Benign Overfitting of Constant-Stepsize SGD for Linear Regression](https://mlsanity.com/paper/2103.12692/) (2021)
- [Pathwise Conditioning of Gaussian Processes](https://mlsanity.com/paper/2011.04026/) (2020)
- [On Sparse variational methods and the Kullback-Leibler divergence between stochastic processes](https://mlsanity.com/paper/1504.07027/) (2015)
- [Scalable Kernel Methods via Doubly Stochastic Gradients](https://mlsanity.com/paper/1407.5599/) (2014)
- [Preconditioning Kernel Matrices](https://mlsanity.com/paper/1602.06693/) (2016)
- [Adapting the Linearised Laplace Model Evidence for Modern Deep Learning](https://mlsanity.com/paper/2206.08900/) (2022)
- [Tighter Bounds on the Log Marginal Likelihood of Gaussian Process Regression Using Conjugate Gradients](https://mlsanity.com/paper/2102.08314/) (2021)
- [Sampling-based inference for large linear models, with application to linearised Laplace](https://mlsanity.com/paper/2210.04994/) (2022)
- [Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processes](https://mlsanity.com/paper/2106.01121/) (2021)
- [State Space Expectation Propagation: Efficient Inference Schemes for Temporal Gaussian Processes](https://mlsanity.com/paper/2007.05994/) (2020)
- [Uncertainty Estimation for Computed Tomography with a Linearised Deep Image Prior](https://mlsanity.com/paper/2203.00479/) (2022)
- [Bayesian Experimental Design for Computed Tomography with the Linearised Deep Image Prior](https://mlsanity.com/paper/2207.05714/) (2022)
- [Numerically Stable Sparse Gaussian Processes via Minimum Separation using Cover Trees](https://mlsanity.com/paper/2210.07893/) (2022)
- [Enabling scalable stochastic gradient-based inference for Gaussian processes by employing the Unbiased LInear System SolvEr (ULISSE)](https://mlsanity.com/paper/1501.05427/) (2015)
- [On the Convergence of Stochastic Gradient Descent for Linear Inverse Problems in Banach Spaces](https://mlsanity.com/paper/2302.05197/) (2023)

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

- [A General Framework for User-Guided Bayesian Optimization](https://mlsanity.com/paper/2311.14645/) (2023)
- [Stochastic Gradient Descent for Gaussian Processes Done Right](https://mlsanity.com/paper/2310.20581/) (2023)
- [Large-Scale Gaussian Processes via Alternating Projection](https://mlsanity.com/paper/2310.17137/) (2023)
- [Scaling Gaussian Processes for Learning Curve Prediction via Latent Kronecker Structure](https://mlsanity.com/paper/2410.09239/) (2024)
- [A Unifying Perspective on Non-Stationary Kernels for Deeper Gaussian Processes](https://mlsanity.com/paper/2309.10068/) (2023)
- [Early-Exit Neural Networks with Nested Prediction Sets](https://mlsanity.com/paper/2311.05931/) (2023)
- [Towards safe and tractable Gaussian process-based MPC: Efficient sampling within a sequential quadratic programming framework](https://mlsanity.com/paper/2409.08616/) (2024)
- [Improving Linear System Solvers for Hyperparameter Optimisation in Iterative Gaussian Processes](https://mlsanity.com/paper/2405.18457/) (2024)
- [Towards Exact Computation of Inductive Bias](https://mlsanity.com/paper/2406.15941/) (2024)
- [Optimizing Posterior Samples for Bayesian Optimization via Rootfinding](https://mlsanity.com/paper/2410.22322/) (2024)
- [Scalable Gaussian Processes with Latent Kronecker Structure](https://mlsanity.com/paper/2506.06895/) (2025)
- [Graph Random Features for Scalable Gaussian Processes](https://mlsanity.com/paper/2509.03691/) (2025)
- [A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Lifting](https://mlsanity.com/paper/2404.12219/) (2024)
- [Towards Gaussian Process for operator learning: an uncertainty aware resolution independent operator learning algorithm for computational mechanics](https://mlsanity.com/paper/2409.10972/) (2024)
- [Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project](https://mlsanity.com/paper/2505.13723/) (2025)
- [Online Laplace Model Selection Revisited](https://mlsanity.com/paper/2307.06093/) (2023)
- [Trigonometric Quadrature Fourier Features for Scalable Gaussian Process Regression](https://mlsanity.com/paper/2310.14544/) (2023)
- [Recommendations for Baselines and Benchmarking Approximate Gaussian Processes](https://mlsanity.com/paper/2402.09849/) (2024)
- [Active Few-Shot Fine-Tuning](https://mlsanity.com/paper/2402.15441/) (2024)
- [Fixed-Mean Gaussian Processes for Post-hoc Bayesian Deep Learning](https://mlsanity.com/paper/2412.04177/) (2024)
- [Stochastic Poisson Surface Reconstruction with One Solve using Geometric Gaussian Processes](https://mlsanity.com/paper/2503.19136/) (2025)
- [Warm Start Marginal Likelihood Optimisation for Iterative Gaussian Processes](https://mlsanity.com/paper/2405.18328/) (2024)
- [Gaussian Processes Sampling with Sparse Grids under Additive Schwarz Preconditioner](https://mlsanity.com/paper/2408.00206/) (2024)
- [Aggregation Models with Optimal Weights for Distributed Gaussian Processes](https://mlsanity.com/paper/2408.00955/) (2024)
- [Exploiting Hankel-Toeplitz Structures for Fast Computation of Kernel Precision Matrices](https://mlsanity.com/paper/2408.02346/) (2024)
- [Variational Deep Learning via Implicit Regularization](https://mlsanity.com/paper/2505.20235/) (2025)
- [Warm-Starting Iterative Gaussian Processes for Faster Sequential Inference](https://mlsanity.com/paper/2511.16340/) (2025)

## Abstract (arXiv)

Gaussian processes are a powerful framework for quantifying uncertainty and for sequential decision-making but are limited by the requirement of solving linear systems. In general, this has a cubic cost in dataset size and is sensitive to conditioning. We explore stochastic gradient algorithms as a computationally efficient method of approximately solving these linear systems: we develop low-variance optimization objectives for sampling from the posterior and extend these to inducing points. Counterintuitively, stochastic gradient descent often produces accurate predictions, even in cases where it does not converge quickly to the optimum. We explain this through a spectral characterization of the implicit bias from non-convergence. We show that stochastic gradient descent produces predictive distributions close to the true posterior both in regions with sufficient data coverage, and in regions sufficiently far away from the data. Experimentally, stochastic gradient descent achieves state-of-the-art performance on sufficiently large-scale or ill-conditioned regression tasks. Its uncertainty estimates match the performance of significantly more expensive baselines on a large-scale Bayesian optimization task.