Executive Summary
This paper provides the missing theoretical foundation for using Stochastic Gradient Descent (SGD) to train Gaussian Processes (GPs)—a setting where data points are inherently correlated. By proving that minibatch SGD converges to the true hyperparameters despite biased gradients, the authors unlock a massive new scale for GPs. The proposed approach enables training on over a million data points in just 30 minutes on a single CPU, while simultaneously achieving better generalization than state-of-the-art exact and sparse GP methods.
The Challenge of Scaling Gaussian Processes
Gaussian Processes are powerful, flexible Bayesian models renowned for their excellent uncertainty quantification. However, they are notoriously expensive to train. Because every data point is correlated with every other data point, computing the loss requires inverting an $n \times n$ covariance matrix. This leads to $O(n^3)$ computational complexity and $O(n^2)$ storage requirements. Traditionally, a "large" dataset for a GP was limited to just a few thousand points.
In deep learning, the standard solution to massive datasets is Stochastic Gradient Descent (SGD). But SGD assumes data samples are independent. In a GP, any finite collection of samples has a joint Gaussian distribution, meaning the stochastic gradient calculated on a minibatch is a biased estimator of the full gradient. This lack of theoretical backing has historically prevented researchers from simply plugging SGD into exact GP inference, leaving the field to rely on complex sparse approximations or massive, expensive GPU clusters to scale.
Methods: Minibatch SGD for GPs
The authors tackle this scaling bottleneck by applying standard minibatch SGD directly to the negative log marginal likelihood of the GP.
The core novelty of this work lies in its theoretical guarantees. Because the loss function lacks standard convexity or Lipschitz continuity, the authors use an $\epsilon$-net argument to concentrate the stochastic gradient to its conditional expectation. They then prove that this conditional expectation satisfies a "strongly convex-like" property by exploiting the eigenvalue structure of the empirical kernel matrix.
Practically, the algorithm updates the GP hyperparameters (noise variance, signal variance, and lengthscales) using minibatches. While the theory holds for uniform random sampling, the authors also introduce a practical nearest-neighbor sampling scheme for minibatches, which groups a randomly selected point with its $m-1$ nearest neighbors to form a batch.
Key Insights
- Correlation Changes the Error Math: In standard SGD with independent samples, statistical error usually depends on the total dataset size $n$. Here, because of the correlation between minibatches, the statistical error depends strictly on the minibatch size $m$.
- Implicit Regularization is a Feature, Not a Bug: The noise introduced by minibatch SGD actually acts as an implicit regularizer. The algorithm tends to settle into local minima that generalize better to unseen data compared to Exact GPs (EGP) that compute the full, precise gradient.
- No Need for Massive GPU Clusters: Recent breakthroughs in exact GPs required 8 GPUs running for days to process a million data points. By validating SGD for GPs, this paper demonstrates that similar or better results can be achieved on a single standard CPU core in a fraction of the time.
Key Results
The authors evaluated their approach on a mix of simulated datasets (to verify theoretical convergence rates and test massive scalability up to $n=2,000,000$) and real-world UCI Benchmarks (ranging from 10,000 to 1,000,000 data points).
- Theoretical Convergence: The authors prove that minibatch SGD converges to a critical point of the full loss function with an optimization error of $O(1/K)$ (where $K$ is the number of iterations). The statistical error is bounded by $O(m^{-1/2})$ for the noise variance and $O((\log m)^{-1/2})$ for the signal variance.
- Massive Speedups: On the 2-million-point OTL Circuit dataset, the SGD-based GP (sgGP) trained in just ~33 minutes using less than 1 GB of memory on a single CPU core.
- Superior Accuracy: Across the UCI benchmark datasets, sgGP consistently outperformed Exact GP (EGP), Sparse GP Regression (SGPR), and Stochastic Variational GP (SVGP) in Root Mean Square Error (RMSE). For example, on the PM2.5 dataset, sgGP achieved an RMSE of 0.287, compared to SVGP's 0.540 and SGPR's 0.638.
Limitations and Future Work
While highly effective, the approach has a few limitations:
- Kernel Assumptions: The theoretical guarantees currently rely on the assumption that the kernel function has exponential eigendecay. This holds true for the popular RBF kernel but may scale differently for polynomial kernels.
- Prediction Bottleneck: While training is vastly accelerated, making predictions on new data still requires large matrix operations. The authors suggest using nearest-neighbor approximations for prediction, but this remains a computational hurdle.
Looking forward, investigating variance reduction techniques specifically tailored for correlated settings could be a highly promising direction to further improve convergence and stability.
Summary updated