Scalable Gaussian Processes with Latent Kronecker Structure
Jihao Andreas Lin, Sebastian Ament, Maximilian Balandat, David Eriksson, José Miguel Hernández-Lobato, Eytan Bakshy · 2025
Read Scalable Gaussian Processes with Latent Kronecker Structure by Jihao Andreas Lin, Sebastian Ament, Maximilian Balandat, David Eriksson, José Miguel Hernández-Lobato, Eytan Bakshy (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-06895.txt.
Introduction
Jihao Andreas Lin and co-authors make Gaussian processes scale to huge, gappy data in a 2025 computing paper. Gaussian processes give predictions with honest uncertainty, but their cost explodes with dataset size. A matrix trick called Kronecker structure speeds the math when inputs form a perfect grid. Real data, like time series with missing readings, break that grid and the trick with it.
The authors hide the grid instead: observed values are treated as a projection of a latent Kronecker product. Paired with iterative solvers, the method keeps exact inference while using far fewer resources than standard iterative routes. Benchmarks beat the state of the art. Missing data no longer has to mean slow statistics.
Catalog record
| CREATOR | Jihao Andreas Lin, Sebastian Ament, Maximilian Balandat, David Eriksson, José Miguel Hernández-Lobato, Eytan Bakshy |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-06895
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Scalable Gaussian Processes with Latent Kronecker Structure Jihao Andreas Lin, Sebastian Ament, Maximilian Balandat, David Eriksson, José Miguel Hernández-Lobato, Eytan Bakshy Abstract Applying Gaussian processes (GPs) to very large datasets remains a challenge due to limited computational scalability. Matrix structures, such as the Kronecker product, can accelerate operations significantly, but their application commonly entails approximations or unrealistic assumptions. In particular, the most common path to creating a Kronecker-structured kernel matrix is by evaluating a product kernel on gridded inputs that can be expressed as a Cartesian product. However, this structure is lost if any observation is missing, breaking the Cartesian product structure, which frequently occurs in real-world data such as time series. To address this limitation, we propose leveraging latent Kronecker structure , by expressing the kernel matrix of observed values as the projection of a latent Kronecker product. In combination with iterative linear system solvers and pathwise conditioning, our method facilitates inference of exact GPs while requiring substantially fewer computational resources than standard iterative methods. We demonstrate that our method outperforms state-of-the-art sparse and variational GPs on real-world datasets with up to five million examples, including robotics, automated machine learning, and climate applications. Figure 1: Illustrative example considering input data points \{{\color[rgb]{0.1211,0.4648,0.707}({\mathbf{s}}_{1},{\mathbf{t}}_{1})},{\color[rgb]{0.1211,0.4648,0.707}({\mathbf{s}}_{1},{\mathbf{t}}_{2})},{\color[rgb]{1,0.4961,0.0547}({\mathbf{s}}_{2},{\mathbf{t}}_{1})},{\color[rgb]{1,0.4961,0.0547}({\mathbf{s}}_{2},{\mathbf{t}}_{2})},{\color[rgb]{1,0.4961,0.0547}({\mathbf{s}}_{2},{\mathbf{t}}_{3})}\} , consisting of two out of three time steps at spatial location {\color[rgb]{0.1211,0.4648,0.707}{\mathbf{s}}_{1}} and three out of three time steps at spatial location {\color[rgb]{1,0.4961,0.0547}{\mathbf{s}}_{2}} . Due to the missing observation at {\color[rgb]{0.1211,0.4648,0.707}({\mathbf{s}}_{1},{\mathbf{t}}_{3})} , the inputs cannot be expressed as a Cartesian product and the joint covariance matrix cannot be directly expressed as a Kronecker product. Latent Kronecker structure assumes that missing observations exist, such that a latent Kronecker product can be leveraged for computational benefits. The original joint covariance matrix is exactly recovered by removing the missing rows and columns via projections. 1 Introduction Gaussian processes (GPs) are probabilistic models prized for their flexibility, data efficiency, and well-calibrated uncertainty estimates. They play a key role in many applications such as Bayesian optimization ( Frazier 2018 ; Garnett 2023 ) , reinforcement learning ( Deisenroth & Rasmussen 2011 ) , and active learning ( Riis et al. 2022 ) . However, exact GPs are notoriously challenging to scale to large numbers of training examples n . This primarily stems from having to solve an n\times n linear system involving the kernel matrix to compute the marginal likelihood and the posterior, which has \mathcal{O}(n^{3}) time complexity using direct methods. To address these scalability challenges, a plethora of approaches have been proposed, which usually fall into two main categories. Sparse GP approaches reduce the size of the underlying linear system by introducing a set of inducing points to approximate the full GP; they include conventional ( Quinonero-Candela & Rasmussen 2005 ) and variational ( Titsias 2009 ) formulations. Iterative approaches ( Gardner et al. 2018a ; Wang et al. 2019 ) employ solvers such as the linear conjugate gradient method, often leveraging hardware parallelism and structured kernel matrices. In particular, Kronecker product structure permits efficient matrix-vector multiplication (MVM). This structure arises when a product kernel is evaluated on data points from a Cartesian product space. A common (though not the only) example of this is spatiotemporal data, as found in climate science for instance, where a quantity of interest, such as temperature or humidity, varies across space and is measured at regular time intervals. In particular, assuming observations collected at p locations and q times result in pq data points in total, the kernel matrix generated by evaluating a product kernel on this data can then be expressed as the Kronecker product of two smaller p\times p and q\times q matrices. This allows MVM in \mathcal{O}(p^{2}q+pq^{2}) instead of \mathcal{O}(p^{2}q^{2}) time and \mathcal{O}(p^{2}+q^{2}) instead of \mathcal{O}(p^{2}q^{2}) space, such that iterative methods require substantially less time and memory. However, in real-world data, this structure frequently breaks due to missing observations, typically requiring a reversion to generic sparse or iterative methods that either do not take advantage of special structure or entail approximations to the matrix. In this paper, we propose latent Kronecker structure , which enables efficient inference despite missing values by representing the joint covariance matrix of observed values as a lazily-evaluated product between projection matrices and a latent Kronecker product. Combined with iterative methods, which otherwise would not be able to leverage Kronecker structure in the presence of missing values, this reduces the asymptotic time complexity from \mathcal{O}(p^{2}q^{2}) to \mathcal{O}(p^{2}q+pq^{2}) , and space complexity from \mathcal{O}(p^{2}q^{2}) to \mathcal{O}(p^{2}+q^{2}) . Importantly, unlike sparse approaches, our method does not introduce approximations of the GP prior. This avoids common problems of sparse GPs, such as underestimating predictive variances ( Jankowiak et al. 2020 ) , and overestimating noise ( Titsias 2009 ; Bauer et al. 2016 ) due to limited model expressivity with a constant number of inducing points. In contrast, our method, Latent Kronecker GP (LKGP), facilitates highly scalable inference of exact GP models with product kernels. We empirically demonstrate the superior computational scalability, speed, and modeling performance of our approach on various real-world applications including inverse dynamics prediction for robotics, learning curve prediction, and climate modeling, using datasets with up to five million data points. Figure 2: Illustration of computational resources used during kernel evaluation and matrix multiplication on ten-dimensional synthetic datasets of different sizes. Without latent Kronecker structure, memory usage escalates quickly and kernel evaluation time dominates matrix multiplication time asymptotically. With latent Kronecker structure, computations can be scaled to several orders of magnitude larger datasets under similar computational resource usage, and matrix multiplication time dominates kernel evaluation time asymptotically. Reported results are the mean over one hundred repetitions using a squared exponential kernel. 2 Background and Related Work Let f:\mathcal{X}\rightarrow\mathbb{R} be a stochastic process such that for any finite subset \{{\mathbf{x}}_{i}\}_{i=1}^{n}\subset\mathcal{X} , the collection of random variables \{f({\mathbf{x}}_{i})\}_{i=1}^{n} follows a multivariate normal distribution. This property defines f as a Gaussian process (GP), which is uniquely identified by its mean function \mu(\cdot)=\mathbb{E}[f(\cdot)] and its kernel function k(\cdot,\cdot^{\prime})=\mathrm{Cov}(f(\cdot),f(\cdot^{\prime})) . We suppress the dependence on kernel hyperparameters for brevity. To perform GP regression, let the training data consist of inputs \{{\mathbf{x}}_{i}\}_{i=1}^{n}={\mathbf{X}}\subset\mathcal{X} and outputs \{y_{i}\}_{i=1}^{n}={\mathbf{y}}\in\mathbb{R}^{n} . We consider the Bayesian model y_{i}=f({\mathbf{x}}_{i})+\epsilon_{i} , where f\sim\mathrm{GP}(\mu,k) and each \epsilon_{i}\sim\mathcal{N}(0,\sigma^{2}) . Without loss of generality, we assume \mu\equiv 0 . The posterior of this model is given by f|{\mathbf{y}}\sim\mathrm{GP}(\mu_{f|{\mathbf{y}}},k_{f|{\mathbf{y}}}) , with \displaystyle\mu_{f|{\mathbf{y}}}(\cdot) \displaystyle={\mathbf{K}}_{(\cdot){\mathbf{X}}}({\mathbf{K}}_{{\mathbf{X}}{\mathbf{X}}}+\sigma^{2}{\mathbf{I}})^{-1}{\mathbf{y}}, (1) \displaystyle k_{f|{\mathbf{y}}}(\cdot,\cdot^{\prime}) \displaystyle={\mathbf{K}}_{(\cdot,\cdot^{\prime})}-{\mathbf{K}}_{(\cdot){\mathbf{X}}}({\mathbf{K}}_{{\mathbf{X}}{\mathbf{X}}}+\sigma^{2}{\mathbf{I}})^{-1}{\mathbf{K}}_{{\mathbf{X}}(\cdot^{\prime})}, where {\mathbf{K}}_{{\mathbf{X}}{\mathbf{X}}} denotes the covariance matrix [k({\mathbf{x}}_{i},{\mathbf{x}}_{j})]_{i,j=1}^{n} and {\mathbf{K}}_{(\cdot){\mathbf{X}}} , {\mathbf{K}}_{{\mathbf{X}}(\cdot^{\prime})} , and {\mathbf{K}}_{(\cdot,\cdot^{\prime})} denote pairwise evaluations of the same kind. For a comprehensive introduction to GPs, we refer to Rasmussen & Williams 2006 . Pathwise Conditioning Instead of computing the mean and covariance of the posterior distribution ( 1 ), Wilson et al. 2020 ; Wilson et al. 2021 directly express a sample from the GP posterior as a random function \displaystyle(f|{\mathbf{y}})(\cdot) \displaystyle=f(\cdot)+{\mathbf{K}}_{(\cdot){\mathbf{X}}}({\mathbf{K}}_{{\mathbf{X}}{\mathbf{X}}}+\sigma^{2}{\mathbf{I}})^{-1}({\mathbf{y}}-(\mathbf{f}_{{\mathbf{X}}}+\bm{\epsilon})), where f\sim\mathrm{GP}(\mu,k) is a sample from the GP prior, \mathbf{f}_{{\mathbf{X}}} is its evaluation at the training data {\mathbf{X}} , and \bm{\epsilon}\sim\mathcal{N}(\mathbf{0},\sigma^{2}{\mathbf{I}}) is a random vector. For product kernels on Cartesian product spaces, pathwise conditioning improves the asymptotic complexity of drawing samples from the GP posterior ( Maddox et al. 2021 ) . We leverage this property in Section 3 . Sparse and Variational Methods Conventional GP implementations scale poorly with the number of training