PaperlayerView exact revision on arXiv

Source-linked AI summary

When Gaussian Process Meets Big Data: A Review of Scalable GPs

Haitao Liu, Yew-Soon Ong, Xiaobo Shen, Jianfei Cai

arXiv:1807.01065v2stat.MLcs.LG

TL;DR

Big data makes standard GP regression difficult because its cubic complexity limits large-scale use. This paper reviews scalable GPs by organizing them into global and local approximations and examining their improvements and extensions. The review synthesizes methods that address scalability while retaining prediction quality, alongside their capability trade-offs and research directions.

  • Problem

    Big data creates computational demands for GP regression, whose cubic complexity limits scalability, while scalable methods had lacked a comprehensive review.

  • Method

    The paper classifies and reviews scalable GPs as global approximations, local approximations, and subsequent improvements and extensions.

  • Results

    The review covers scalable GP methods, including sparse and local approaches, scalability and capability improvements, extensions, and open issues.

  • Takeaways & Limitations

    The synthesis provides understanding of state-of-the-art scalable GPs and insights into new problems, discoveries, models, and theory for large-scale tasks.

Abstract

from arXiv · show

The vast quantity of information brought by big data as well as the evolving computer hardware encourages success stories in the machine learning community. In the meanwhile, it poses challenges for the Gaussian process (GP) regression, a well-known non-parametric and interpretable Bayesian model, which suffers from cubic complexity to data size. To improve the scalability while retaining desirable prediction quality, a variety of scalable GPs have been presented. But they have not yet been comprehensively reviewed and analyzed in order to be well understood by both academia and industry. The review of scalable GPs in the GP community is timely and important due to the explosion of data size. To this end, this paper is devoted to the review on state-of-the-art scalable GPs involving two main categories: global approximations which distillate the entire data and local approximations which divide the data for subspace learning. Particularly, for global approximations, we mainly focus on sparse approximations comprising prior approximations which modify the prior but perform exact inference, posterior approximations which retain exact prior but perform approximate inference, and structured sparse approximations which exploit specific structures in kernel matrix; for local approximations, we highlight the mixture/product of experts that conducts model averaging from multiple local experts to boost predictions. To present a complete review, recent advances for improving the scalability and capability of scalable GPs are reviewed. Finally, the extensions and open issues regarding the implementation of scalable GPs in various scenarios are reviewed and discussed to inspire novel ideas for future research avenues.

I. INTRODUCTION

Big data exposes the cubic cost of standard GP regression, motivating scalable methods that preserve prediction quality. This review classifies and analyzes global and local approximations, their improvements, extensions, and open research directions.

  • Gaussian processes are non-parametric, interpretable models used across active learning, multi-task learning, manifold learning, and optimization.
  • O(n3) time complexity from kernel-matrix inversion and determinant calculations makes standard GP regression unaffordable for large-scale datasets.
  • Scalable GPs aim to improve full-GP scalability while retaining favorable prediction quality for big data.
  • Global approximations distill the full kernel using subsets, sparse kernels, or low-rank inducing-point representations, whereas local approximations divide data among local experts and aggregate predictions.
  • Most sparse and local methods achieve O(nm2) training complexity, while structured and stochastic variants can reach O(n) and O(m3), respectively.Stochastic optimization enables regression with million- and even billion-sized datasets.
  • Global approximations capture global patterns but may miss local structure, while local methods capture non-stationarity but risk discontinuities and local over-fitting.Inter-domain, hierarchical, hybrid, and neural-network combinations are reported as capability improvements.

III. GLOBAL APPROXIMATIONS

Global approximations make GP regression scalable by sparsifying or simplifying the full kernel matrix through subsets, sparse entries, or low-rank representations.

  • Global approximations achieve full-kernel sparsity through subset-of-data, sparse-kernel, and sparse low-rank approximations.

A. Subset-of-data

Scalable GP approximations reduce computation by replacing full-data operations with subsets, inducing variables, sparse kernels, or structured representations. These methods trade computational efficiency against fidelity to global and local uncertainty patterns.

  • A. Subset-of-data: Subset-of-data uses m ≪ n training points, retaining exact GP inference on K_mm with O(m^3) time complexity.Subset points may be selected randomly, by clustering, or through active-learning criteria.
  • Kernel approximations: Nyström and compactly supported kernels reduce computation through low-rank or sparse kernel representations, but Nyström GP can yield negative prediction variances and compact support requires positive semidefiniteness.Compactly supported kernels also have potential for capturing local patterns because distant kernel entries are truncated.
  • Sparse approximations: Sparse approximations use m inducing points to summarize dependencies across the training data and generally reduce standard cubic complexity to O(nm^2).Inducing variables are modeled with the GP prior and treated as sufficient statistics for the latent function.
  • Sparse approximations: Prior approximations modify the prior for exact inference, whereas posterior approximations retain the exact prior while using approximate inference.The review further distinguishes structured sparse approximations that exploit kernel-matrix structure.
  • Prior approximations: SoR and related RVM-type models can produce overconfident prediction variances away from training data because they impose restrictive assumptions and have at most m kernel degrees of freedom.DTC increases variance relative to SoR and returns toward the prior away from inducing points, but remains an inexact GP under inconsistent conditionals.
  • Prior approximations: FITC partially retains uncertainty through diagonal corrections and more closely approximates the full GP, while PITC models joint distributions within independent data blocks but reportedly adds little over FITC.FITC targets predictive accuracy at low computational cost rather than exact recovery of the standard GP as m increases.

2) Posterior approximations:

Posterior approximations retain the exact GP prior while approximating inference, chiefly through variational objectives that support scalable and stochastic optimization. These methods can approach full-GP predictions, while structured variants exploit kernel structure for further speedups but face dimensionality and representation constraints.

  • Posterior approximations retain the exact prior and approximate the posterior using a variational distribution.
  • The variational free energy is an evidence lower bound optimized jointly over variational parameters and hyperparameters.
  • The VFE trace term regularizes over-fitting, improves inducing-set selection, and ensures recovery of the full GP as inducing points increase.
  • Stochastic variational inference enables unbiased mini-batch optimization and achieves O(m3) complexity when the mini-batch contains one observation.
  • SVGP trains sparse GPs incrementally from small data subsets, although its variational bound is less tight and its variational parameterization can be costly.
  • Weight-space variational methods have scaled GP training to billions of data points through distributed optimization, while structured methods exploit matrix algebra for further acceleration.
  • Structured inducing-point methods can reduce complexity substantially, but SKI becomes impractical beyond d > 5 because its grid size grows exponentially with dimensionality.

IV. LOCAL APPROXIMATIONS

Local approximations divide training data among localized experts, reducing GP computation while capturing non-stationary features. Mixture-of-experts and product-of-experts methods then average local predictions to improve their quality.

  • Local approximations use localized experts to improve GP scalability and capture non-stationary features.

A. Naive-local-experts

Naive-local-experts assign local GP models to data subregions or neighborhoods, reducing computation through divide-and-conquer. Their locality captures non-stationary behavior but creates boundary discontinuities and weak long-range generalization.

  • Naive-local-experts predict with the expert responsible for the local subregion containing the test input.
  • Inductive NLE partitions the input space before training, whereas transductive NLE selects a neighborhood around each test input.
  • Inductive and transductive NLE have complexities O(nm'2) and O(ntm'3), respectively, with the latter depending on test-set size.
  • Geometric neighborhood selection is simple but not optimal without considering spatial correlation, motivating GP-based active-learning updates.
  • NLE captures non-stationary features but produces discontinuous boundary predictions and poor generalization because it misses long-term spatial correlations.
  • Patched GPs impose boundary continuity but can yield inconsistent or negative variances and are limited to low-dimensional settings.

B. Mixture-of-experts

Mixture-of-experts combines diverse local experts through probabilistic gating, while product-of-experts combines their predictive distributions multiplicatively. Scalable GP expert models address both computational complexity and expert-number selection through localization, variational approximations, clustering, and nonparametric priors.

  • Mixture-of-experts combines local experts with individual hyperparameters to improve overall accuracy and reliability.
  • A Gaussian-mixture formulation uses gating functions to assign inputs probabilistically to experts and combine their predictive components.
  • Joint learning of gates and experts enables soft, overlapping partitions and diverse experts, typically optimized with gradient methods or EM.
  • For big-data GP experts, the central design problems are reducing model complexity and determining the number of experts.
  • Localization factorizes likelihoods over experts, yielding O(nm'2) complexity when experts have equal training size m'.
  • Global sparse approximations can be combined with experts under variational EM, with complexity O(nm2M) or O(nm2) using hard-cut EM.
  • MILE dynamically allocates data according to data properties and expert performance, but competitive learning can eliminate experts through zero coefficients.
  • MELE prepartitions inputs by clustering to reduce complexity and explicitly determine the expert architecture, while losing label information during partitioning.

C. Product-of-experts

Product-of-experts aggregate local GP predictions multiplicatively, reducing reliance on explicit gating but creating uncertainty and consistency challenges that motivate weighted and corrected variants.

  • Product-of-experts: PoE multiplies experts’ probability distributions, while MoE uses a weighted sum; PoE can therefore produce sharper predictions than any individual expert.The PoE likelihood is a special case of the MoE likelihood, but PoE may be overconfident when weak experts contribute.
  • Product-of-experts: O(nm0^2) complexity results when local experts each contain m0 training points, because the full kernel factorizes into diagonal expert blocks.This factorization replaces the full kernel inversion with separate inversions for the experts.
  • Product-of-experts: PoE can yield poor prediction means and overconfident variances when aggregating six independent experts, whereas MoE uses gating functions to provide desirable predictions.The weighted-sum structure of MoE cannot be sharper than the sharpest expert, while the product structure of PoE can be.
  • Product-of-experts: Constant PoE weights cause aggregated precision to grow rapidly with the number of experts, while GPoE’s flexible weights can produce explosive variance outside the training data.Constraining the weights to sum to one or using β∗i = 1/M addresses different uncertainty problems, with the latter producing underconfident variance.
  • Product-of-experts: NPAE removes the independence assumption for theoretically consistent predictions, but requires inversion of a new M × M kernel matrix at every test point.GRBCM instead uses a global communication expert and global-local covariance to improve efficiency while retaining consistency as n →∞.
  • Product-of-experts: Transductive aggregations usually share hyperparameters across experts, which regularizes local fitting but limits modeling of non-stationary features and creates Kolmogorov inconsistency across test points.BCM additionally requires shared hyperparameters because its common prior is conditioned on the same θ.

A. Scalability

Scalable GP implementations reduce computational cost through sparse, structured, local, hybrid, and distributed designs. These gains involve trade-offs between global and local pattern capture, prediction continuity, and representational flexibility.

  • Global and local scalability: Sparse approximations reduce standard cubic complexity to O(nm2), with further reductions through stochastic variational inference, structured data, GPUs, and distributed computing.Structured methods can reach O(n+d log m1+1/d), while SVI has O(m3) complexity.
  • Global and local scalability: Distributed sparse GPs have been trained successfully on up to one billion training points within two hours.The framework distributes several conventional sparse GP methods through varying correlated-noise structures.
  • Global and local scalability: Local approximations match global approximations’ complexity when each expert uses m0=m points and naturally support parallel or distributed computation.Their local structure enables computation to be divided across experts.
  • Model capability: Global sparse approximations suit slow-varying, highly correlated features, whereas limited global inducing sets struggle with quick-varying non-stationary features.Hybrid approaches such as PIC retain local dependence near the test point while integrating global and local approximations.
  • Hybrid approximations: Tree-structured GP approximations can reduce time complexity to linear in n by ignoring most intersubregion dependencies while retaining adjacent-subregion dependencies.They permit the use of many inducing points, but localized predictions can become discontinuous at subregion boundaries.
  • Capability extensions: Inter-domain and heteroscedastic extensions improve representational capability, but stochastic global inducing sets may sacrifice prediction mean when modeling heteroscedastic noise.Distributed experts with hybrid parameters improve both scalability and capability in the cited comparison.

VI. EXTENSIONS AND OPEN ISSUES

The review extends scalable GPs to high-dimensional, deep, and multi-task settings, while identifying unresolved challenges in representation, inference, dimensionality, and broader task regimes.

  • High-dimensional scalable GPs: High-dimensional scalable GPs address settings where input dimension d is comparable to or larger than training size n, often by exploiting lower-dimensional manifolds.Manifold GPs jointly learn dimensionality-reducing mappings and scalable regression in a Bayesian framework.
  • High-dimensional scalable GPs: Random-compression Bayesian model averaging can reduce computational demands without explicitly learning the intrinsic manifold when the function is not highly smooth.The cited theoretical result states that learning in the original high-dimensional space can still achieve the optimal rate under that condition.
  • Open issues: Scalable manifold GPs still require theoretical and empirical development of components such as convolutional kernels for applications including computer vision.This remains an open issue identified by the review.
  • Scalable deep GP: Scalable deep GPs combine feature extraction through neural or hierarchical latent-variable layers with sparse GP regression, but their inference is intractable and expensive.Approximate inference using inducing points makes training efficient but may limit capability.
  • Scalable multi-task GP: Multi-task GPs jointly learn correlated tasks so they can leverage information across tasks, but collecting T tasks with n points each leads to O(T3n3) complexity.Sparse and local approximations have therefore been applied to multi-task GPs.
  • Open issues: Current scalable multi-task GP research mainly assumes well-defined task labels and shared, modest-dimensional input spaces.Extending these models to the broader 4V challenges of multi-task learning remains necessary.

D. Scalable online GP

Scalable GP methods address online, sequential, and classification settings by adapting sparse or local approximations to streaming and recurrent data. These extensions improve applicability but retain constraints such as distribution-shift assumptions or intractable inference.

  • Scalable online GP: Online scalable GPs must adapt in real time while handling continuously arriving large-scale data.
  • Scalable online GP: Sparse GPs support fast online learning by summarizing training data with a small inducing set that interacts with new observations.FITC and PITC prediction updates rely on the inducing set and new data, while stochastic variants support mini-batch learning.
  • Scalable online GP: Some online GPs fix hyperparameters to maintain constant update complexity, although early online optimization can significantly improve the model.
  • Scalable online GP: When new and old data follow different distributions, local online GPs update a relevant expert or create a new one for distant data.This strategy targets evolving trajectories such as time series, where the shared-distribution assumption is unsuitable.
  • Scalable recurrent GP: GP-NARX forms regression inputs from delayed outputs and external inputs, enabling standard scalable GPs but creating an errors-in-variables problem when inputs are noisy.Proposed remedies include preprocessing, input-noise GPs, and state space models.
  • Scalable recurrent GP: GP-SSM models transition and emission noise without lagged parameters, but inference is intractable because all latent states must be marginalized.
  • Scalable GP classification: Scalable GP classification combines approximate inference methods such as Laplace approximation, EP, or VI with sparse strategies to address non-Gaussian likelihoods.Major challenges include intractable inference and high training complexity for many classes.
  • Conclusions: The review connects scalable GPs to large-scale real-world tasks while identifying new challenges, models, and theory for the GP community.

APPENDIX A LIBRARIES AND DATASETS

The appendix surveys software libraries and large regression datasets used to support and assess scalable GPs. It notes increasing use of Python and hardware acceleration and reports evaluations reaching roughly one billion training points.

  • Libraries: The appendix notes conventional inverse link functions including step, probit, logit, and softmax functions.
  • Libraries: Table I lists primary libraries supporting representative scalable GPs for academic and industry use.
  • Datasets: Table II summarizes big regression datasets with n ≥10^4 reported in the scalable GP literature.
  • Libraries: Python and hardware acceleration are becoming popular in the GP community, while some advanced scalable GP packages are omitted from the table.
  • Datasets: Researchers have assessed scalable GPs with up to about one billion training points.Reported UCI regression datasets span n ∈[15, 4.18 × 10^6], while LIBSVM datasets span n ∈[152, 2.06 × 10^4].
Loading 1807.01065v2…