Stochastic Gradient Descent in Correlated Settings: A Study on Gaussian Processes

Hao Chen, Lili Zheng, Raed Al Kontar, Garvesh RaskuttiNeurIPS 2020 · OpenReview

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.

Algorithm 1: Minibatch SGD

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.
Parameter convergence across different initializations
  • 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

Abstract

Stochastic gradient descent (SGD) and its variants have established themselves as the go-to algorithms for large-scale machine learning problems with independent samples due to their generalization performance and intrinsic computational advantage. However, the fact that the stochastic gradient is a biased estimator of the full gradient with correlated samples has led to the lack of theoretical understanding of how SGD behaves under correlated settings and hindered its use in such cases. In this paper, we focus on the Gaussian process (GP) and take a step forward towards breaking the barrier by proving minibatch SGD converges to a critical point of the full loss function, and recovers model hyperparameters with rate $O(\frac{1}{K})$ up to a statistical error term depending on the minibatch size. Numerical studies on both simulated and real datasets demonstrate that minibatch SGD has better generalization over state-of-the-art GP methods while reducing the computational burden and opening a new, previously unexplored, data size regime for GPs.
BibTeX
@inproceedings{chen2020stochastic,
  author = {Hao Chen and Lili Zheng and Raed Al Kontar and Garvesh Raskutti},
  title = {{Stochastic Gradient Descent in Correlated Settings: A Study on Gaussian Processes}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=4hFnRHjSwy},
}
Figure