Asynchronous Distributed Variational Gaussian Process for Regression

Hao Peng, Shandian Zhe, Xiao Zhang, Yuan QiICML 2017 · OpenReview

Gaussian Processes (GPs) are often considered the "Swiss Army Knife" of Bayesian machine learning. They are non-parametric, provide elegant uncertainty estimates, and naturally resist overfitting. However, they have a notorious reputation for being computationally demanding. Standard GP inference scales at $O(n^3)$, meaning that while they work beautifully for a few thousand data points, they traditionally choke on the massive datasets common in modern industry.

In this paper, researchers present ADVGP (Asynchronous Distributed Variational Gaussian Process), a framework that finally pushes GP regression into the realm of "Big Data"—scaling effortlessly to datasets with over a billion samples.

The Bottleneck: Synchrony and Stragglers

The primary bottleneck for GPs is computational complexity. While "Sparse GPs" (using a small set of $m$ inducing points) reduced complexity to $O(nm^2)$, scaling to millions of points still requires distributed computing systems.

Previous distributed approaches were largely synchronous. In a synchronous system, every computing node must wait for the slowest node (the "straggler") to finish its task before the model can update. This leads to massive idle times and inefficiency. Stochastic Variational Inference (SVI) exists but processes data sequentially, making it too slow to finish even a single "epoch" (one pass through the data) when $n$ is in the billions.

The ADVGP Solution

The authors tackle the scaling problem through two main innovations:

  1. Weight Space Augmentation: The authors reformulate the GP model by introducing an auxiliary random weight vector. This transformation allows them to rewrite the Variational Lower Bound (ELBO)—the objective function they want to maximize—into a "composite" form. This specific mathematical structure is crucial because it makes the GP objective compatible with advanced optimization techniques used in distributed systems.
  2. Asynchronous Proximal Gradient Optimization: Using a Parameter Server framework, ADVGP splits the work between "Servers" (which store model parameters) and "Workers" (which compute gradients on local data chunks).
  3. Asynchrony: Workers don't wait for each other. They push gradients to the server as soon as they are ready.
  4. Proximal Updates: Because the ELBO is reformulated into a composite form (a non-convex data term plus a convex regularization term), the servers can use "proximal" updates. These are incredibly fast, closed-form calculations that guarantee convergence even when gradients are slightly "stale" due to the asynchronous nature of the system.

Key Results and Performance

The authors evaluated ADVGP on two primary datasets: the US Flight Dataset (up to 2 million samples) and the NYC Taxi Trip Dataset (over 1.2 billion records).

Performance comparison of ADVGP against synchronous and sequential methods across different dataset sizes and inducing points.
  • Superior Scalability: On the US Flight data, ADVGP's per-iteration time remained almost constant as the number of CPU cores and data size increased. In contrast, synchronous methods saw their per-iteration time grow linearly. As seen in the performance comparisons, ADVGP converges significantly faster than DistGP and SVIGP baselines, reaching lower error rates in a fraction of the time.
  • Billion-Scale Performance: The NYC Taxi dataset served as a stress test. ADVGP achieved a Root Mean Square Error (RMSE) of 309.7, significantly outperforming Vowpal Wabbit's highly optimized linear regression (362.8) and simple mean prediction (556.3). ADVGP reached a better error rate in just 12 minutes of training than competing linear models could achieve at full convergence.

Insights and Limitations

A key insight of ADVGP is the use of a "delay limit" ($\tau$). By allowing a specific tolerance for stale gradients, the system doesn't stall if one machine is slow, fully exploiting network bandwidth and CPU power.

Effect of the delay limit ($\tau$) on the convergence of ADVGP.

However, this introduces a trade-off. As shown above, while higher delay limits can speed up early iterations, if $\tau$ is too large, the gradients become too stale, and the optimization can become unstable or fluctuate.

Furthermore, while the method scales the number of samples ($n$) effortlessly, it still depends on the number of inducing points ($m$). Choosing the number and location of these points remains a balancing act between predictive accuracy and local computational cost. Future work may explore extending this asynchronous framework to more complex kernels or non-Gaussian likelihoods for classification tasks.

Summary updated

Abstract

Gaussian processes (GPs) are powerful non-parametric function estimators. However, their applications are largely limited by the expensive computational cost of the inference procedures. Existing s...
BibTeX
@inproceedings{peng2017asynchronous,
  author = {Hao Peng and Shandian Zhe and Xiao Zhang and Yuan Qi},
  title = {{Asynchronous Distributed Variational Gaussian Process for Regression}},
  booktitle = {International Conference on Machine Learning},
  year = {2017},
  url = {https://openreview.net/forum?id=HJNews-d-H},
}
Figure