Ensemble Gaussian Processes with Spectral Features for Online Interactive Learning with Scalability

Qin Lu, Georgios Vasileios Karanikolas, Yanning Shen, Georgios B. GiannakisAISTATS 2020 · OpenReview

Abstract

Combining benefits of kernels with Bayesian models, Gaussian process (GP) based approaches have well-documented merits not only in learning over a rich class of nonlinear functions, but also quantifying uncertainty. However, standard GPs suffer from cubic computational complexity and the challenge of kernel selection. This paper introduces Online Interactive Ensemble Gaussian Processes (OI-EGP), a scalable framework that leverages random spectral features and a weighted ensemble of priors to interactively learn complex, non-stationary functions on-the-fly with a significantly lower regret bound ($O(\log T)$) and faster execution than existing state-of-the-art methods.

Introduction

Gaussian Processes (GPs) are a "gold standard" for Bayesian regression because they provide not just a prediction, but a measure of uncertainty. However, they face two major hurdles: scalability and kernel selection. Standard GPs have a computational complexity of $O(T^3)$, where $T$ is the number of training samples, making them unusable for large-scale or streaming data. Furthermore, GP performance depends heavily on choosing the right covariance function (kernel), which is typically pre-selected by researchers, limiting the model's ability to represent diverse data patterns.

Methodology

The proposed OI-EGP architecture rests on three pillars to overcome these limitations:

  • Random Features (RF) for Scalability: Instead of computing a massive $T \times T$ kernel matrix, the model approximates shift-invariant kernels using random spectral features. This transforms the non-parametric GP into a parametric model with $2D$ features, reducing per-iteration complexity to $O(D^2)$.
  • Weighted Ensemble: Rather than relying on a single kernel, the model maintains a dictionary of GP "experts," each using a different kernel. The system maintains a set of weights (probabilities) for these experts, updating them based on how well each expert predicts the next data point using a Bayesian loss function.
  • Interactive Online Updates: The model uses a "prediction-correction" cycle. When a new input arrives, it predicts the output; once the true output is revealed, it performs a second-order update on the model parameters and expert weights. This results in a much tighter "static regret" bound of $O(\log T)$ compared to the $O(\sqrt{T})$ typically seen in first-order methods.
  • Dynamic Tracking (DOI-EGP): For non-stationary functions that change over time, the authors introduce a version that incorporates a "random walk" state-space model, allowing parameters to evolve.

Experimental Evaluation

The researchers evaluated their model on several high-dimensional real-world datasets, including SARCOS (robot arm dynamics), Air Quality sensor data, and social media activity levels (Tom's Hardware & Twitter).

Comparison of nMSE across different datasets (a) SARCOS, (b) Air Quality, and (c) Tom's Hardware.

As shown in the performance plots above, (D)OI-EGP consistently achieved lower normalized Mean Square Error (nMSE) than competitors like AdaRaker, I-SSGPR, and SSGP. The dynamic version (DOI-EGP) showed particularly fast convergence, reaching stable error rates significantly earlier than other streaming GP approaches.

Normalized CPU time comparison across datasets (a) SARCOS, (b) Air Quality, and (c) Tom's Hardware.

Computational efficiency was a standout result. As illustrated in the CPU time analysis, OI-EGP's running time was less than 0.3% of the most closely competing alternative in terms of accuracy on the "Tom's Hardware" dataset.

Discussion and Conclusion

OI-EGP successfully bridges the gap between the theoretical elegance of GPs and the practical requirements of large-scale online learning. By staying within the Bayesian framework, the model provides a variance estimate for every prediction, which is crucial for safety-critical applications like robotics or finance.

While the ensemble approach is flexible, it still requires a prescribed kernel dictionary and primarily targets shift-invariant kernels. Future work remains to automate hyperparameter tuning (such as length-scales) in a purely online fashion and to extend the framework to non-shift-invariant kernels. Nonetheless, the $O(\log T)$ regret bound and massive speedups represent a significant advancement for interactive Bayesian learning.

Summary updated

Abstract

Combining benefits of kernels with Bayesian models, Gaussian process (GP) based approaches have well-documented merits not only in learning over a rich class of nonlinear functions, but also quanti...
BibTeX
@inproceedings{lu2020ensemble,
  author = {Qin Lu and Georgios Vasileios Karanikolas and Yanning Shen and Georgios B. Giannakis},
  title = {{Ensemble Gaussian Processes with Spectral Features for Online Interactive Learning with Scalability}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=HNqUivFQxOM},
}
Figure