Blitzkriging: Kronecker-structured Stochastic Gaussian Processes

Thomas E. Nickson, Tom Gunter, Chris Lloyd Michael, Stephen Roberts, Roberts, StephenarXiv 2015 · DOI · arXiv

Abstract

We present Blitzkriging, a new approach to fast inference for Gaussian processes, applicable to regression, optimisation and classification. State-of-the-art (stochastic) inference for Gaussian processes on very large datasets scales cubically in the number of 'inducing inputs', variables introduced to factorise the model. Blitzkriging shares state-of-the-art scaling with data, but reduces the scaling in the number of inducing points to approximately linear. Further, in contrast to other methods, Blitzkriging: does not force the data to conform to any particular structure (including grid-like); reduces reliance on error-prone optimisation of inducing point locations; and is able to learn rich (covariance) structure from the data. We demonstrate the benefits of our approach on real data in regression, time-series prediction and signal-interpolation experiments.

Introduction: The Scaling Problem of Gaussian Processes

Gaussian Processes (GPs) are a cornerstone of Bayesian functional inference, prized for their ability to provide well-calibrated uncertainty estimates. However, their practical application is severely limited by computational complexity: standard GPs scale cubically ($O(N^3)$) with the number of data points $N$. To address this, sparse methods introduce $M$ "inducing points" to act as a proxy for the full dataset. While this reduces complexity to $O(NM^2 + M^3)$, the cubic scaling with respect to $M$ remains a bottleneck. For complex, high-frequency signals requiring thousands of inducing points, standard sparse methods become computationally prohibitive. Furthermore, many existing acceleration techniques require input data to reside on a rigid grid, a condition rarely met in real-world scenarios.

Methodology: The Blitzkriging Framework

Blitzkriging addresses these limitations by imposing a Kronecker structure on the inducing points and the variational covariance. The framework is built upon the Stochastic Variational Gaussian Process (SVGP) but introduces three key structural innovations:

  1. Grid-Structured Inducing Points: Inducing points are placed on a regular grid, regardless of the actual data distribution.
  2. Kronecker-Structured Variational Covariance: The variational distribution's covariance matrix $S$ is constrained to factorize as a Kronecker product. This transformation reduces massive $M \times M$ matrix operations into a series of smaller operations along the grid's dimensions.
  3. Khatri-Rao Products: To bridge the gap between scattered data and the structured grid, Khatri-Rao matrices are employed. This allows for efficient inference without the need to explicitly compute or store full covariance matrices.

These innovations reduce the complexity of the most expensive operations from $O(M^3)$ to approximately $O(M \cdot D)$, where $D$ is the dimensionality of the input space.

Comparison of variational covariance matrices between SVGP and Blitzkriging.

A central concern with such structural constraints is the potential loss of expressivity. However, empirical evidence suggests that this approximation is "benign." As shown in the figure above, the Kronecker-structured covariance in Blitzkriging (b, d) effectively captures the essential covariance structure learned by a standard SVGP (a, c), while enabling the use of a significantly higher density of inducing points.

Experimental Results

The authors evaluated Blitzkriging across diverse benchmarks, ranging from synthetic pattern discovery to large-scale real-world datasets:

  • Efficiency and Stability: In power plant regression tasks, Blitzkriging achieved log-likelihoods comparable to full GPs in roughly half the runtime (216s vs 389s). Crucially, while standard SVGP often becomes numerically unstable beyond 120 inducing points, Blitzkriging maintains stability even with over 1,200 points.
  • Predictive Performance: On wind speed time-series data, Blitzkriging utilizing a Spectral Mixture kernel outperformed traditional baselines like Random Forests and Kalman filters in both RMSE and log-likelihood.
  • Large-Scale Application: On a dataset of over 172,000 UK housing sales, Blitzkriging successfully captured complex regional price variations that standard SVGP struggled to model effectively due to initialization and optimization challenges.

Discussion and Future Work

Blitzkriging demonstrates that for large-scale GP inference, a high density of fixed inducing points often outperforms a small number of optimized points. By making grid-based speed accessible to scattered data, it opens new avenues for modeling complex phenomena.

Current limitations include the "curse of dimensionality," as grid size grows exponentially with $D$. Future research will explore low-rank approximations for mean functions and the integration of rotation matrices to better align data with the grid axes, further extending the reach of Kronecker-structured inference.

Summary updated

Abstract

We present Blitzkriging, a new approach to fast inference for Gaussian processes, applicable to regression, optimisation and classification. State-of-the-art (stochastic) inference for Gaussian processes on very large datasets scales cubically in the number of 'inducing inputs', variables introduced to factorise the model. Blitzkriging shares state-of-the-art scaling with data, but reduces the scaling in the number of inducing points to approximately linear. Further, in contrast to other methods, Blitzkriging: does not force the data to conform to any particular structure (including grid-like); reduces reliance on error-prone optimisation of inducing point locations; and is able to learn rich (covariance) structure from the data. We demonstrate the benefits of our approach on real data in regression, time-series prediction and signal-interpolation experiments.
BibTeX
@misc{nickson2015blitzkriging,
  author = {Thomas E. Nickson and Tom Gunter and Chris Lloyd Michael and Stephen Roberts and Roberts, Stephen},
  title = {{Blitzkriging: Kronecker-structured Stochastic Gaussian Processes}},
  year = {2015},
  eprint = {1510.07965},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1510.07965},
}
Figure