Unbiased Stochastic Optimization for Gaussian Processes on Finite Dimensional RKHS

Neta Shoham, Haim Avron · 2025

Read Unbiased Stochastic Optimization for Gaussian Processes on Finite Dimensional RKHS by Neta Shoham, Haim Avron (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-2508-20588.txt.

Introduction

Neta Shoham and Haim Avron made Gaussian process tuning exact in two thousand twenty-five. Gaussian processes need hyperparameters fit from data. Stochastic methods for that fit use biased shortcuts. Those shortcuts may never reach the true best fit. Inducing point methods carry the same worry. The pair target kernels with modest finite dimension.

Their algorithms give unbiased stochastic gradients. Exact inference becomes possible in that setting. Convergence to a true stationary point is restored. An extension reaches infinite dimensions at some cost. Memory limits motivated the whole design. Experiments beat existing methods under tight memory. Small batches and few inducing points hurt rivals more. The work serves large spatial and time-series models.

Catalog record

CREATORNeta Shoham, Haim Avron
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE45 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-20588

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Unbiased Stochastic Optimization for Gaussian Processes on Finite Dimensional RKHS Neta Shoham, Haim Avron Abstract Current methods for stochastic hyperparameter learning in Gaussian Processes (GPs) rely on approximations, such as computing biased stochastic gradients or using inducing points in stochastic variational inference. However, when using such methods we are not guaranteed to converge to a stationary point of the true marginal likelihood. In this work, we propose algorithms for exact stochastic inference of GPs with kernels that induce a Reproducing Kernel Hilbert Space (RKHS) of moderate finite dimension. Our approach can also be extended to infinite dimensional RKHSs at the cost of forgoing exactness. Both for finite and infinite dimensional RKHSs, our method achieves better experimental results than existing methods when memory resources limit the feasible batch size and the possible number of inducing points. 1 Introduction Gaussian Processes (GPs) provide a powerful probabilistic framework which has been applied to a wide range of learning applications, such as multi-task learning ( Alvarez et al. 2012 ; Liu et al. 2018a ) , active learning ( Liu et al. 2018b ) , semi-supervised learning Jean et al. 2018 , and reinforcement learning ( Srinivas et al. 2010 ; Shahriari et al. 2015 ) . These successes can be attributed to the natural way in which uncertainty is incorporated into the predictions via a Bayesian interpretation. However, hyperparameter learning scales poorly. For a general covariance function (kernel function in kernel method’s parlance) the computational cost grows as O(n^{3}) where n denotes the number of samples, and the storage resources grow as O(n^{2}) . As a consequence, approximations are required for any modern application that involves GPs and big data. It is therefore unsurprising that much research effort has been devoted to approximate methods for learning GPs. For a comprehensive overview of this research, we refer the reader to the work of Liu et al. 2020 . The most expensive operation in training GPs is the inversion of the n\times n kernel matrix which is required during the maximization of the marginal likelihood and for the computation of the posterior of the responses. As a result, much research has been devoted to providing a cheap approximation of the kernel matrix. Broadly speaking approximations of GPs can be split in to data dependent and data independent methods. Data dependent approximations usually come with valuable probabilistic interpretations. An important work in this line of research is the seminal work of Quinonero-Candela & Rasmussen 2005 , which provides a unified view on previous work by using the concept of inducing points. Since then quite a few followup works have used inducing points, while exploiting the tool of variational inference as a theoretical platform ( Titsias 2009 ; Nguyen et al. 2014 ; Wilson & Nickisch 2015 ; Zhao & Sun 2016 ) . This approach is closely related to the Nyström approximation of kernel matrices ( Zhao & Sun 2016 ) . In contrast, data independent methods rely on approximating the kernel function itself. Typically, it is approximated by an inner product between low dimensional vectors ( Rahimi & Recht 2007 ; Yang et al. 2015 ; Shustin & Avron 2021 ) . Approximating the inverse of the kernel matrix is enough for frequentist kernel methods such as Kernel Ridge Regression. However, in order to harness the full power of Bayesian kernel methods such as Gaussian Process Regression (GPR), we need to be also able to maximize the marginal likelihood, and for that an approximation of the inverse of the kernel matrix is not enough, due to an additional log-determinant term. This is especially true in cases where the covariance function depends on a large number of parameters, e.g., evaluating the covariance function involves a forward pass of a deep neural network ( Wilson et al. 2016b ; Calandra et al. 2016 ; Wilson et al. 2016a ) . In such cases, it is important to be able to use a stochastic mini-batches based optimization, since otherwise the cost of making a pass over the entire dataset typically proves too expensive. Moreover, it is well appreciated in the literature that when the model involves deep neural networks, e.g., when the covariance function is defined by a neural network, it is important to use stochastic gradients, since they enable more efficient optimization and better generalization ( Goodfellow et al. 2016 ) . Currently, two main approaches are used for stochastic hyperparameter learning in GPs. The first relies on the inducing - points framework and employs stochastic variational inference (SVI) ( Hoffman et al. 2013 ; Hensman et al. 2013 ; Hoang et al. 2015 ; Wilson et al. 2016a ) . The second approach is more direct: it is based on computing stochastic batches while ignoring the fact that they provide only biased estimates of gradients. Interestingly, a recent work shows that despite the bias, given a large enough batch size, the direct approach produces almost optimal models (in terms of the marginal likelihood) ( Chen et al. 2020 ) . Both the SVI approach and the direct approach suffer from several disadvantages. For example, consider the case in which the covariance function is the inner product between two feature maps of a moderate dimension. This can be either because this decomposition serves as an approximation to another covariance function with an infinite dimensional reproducing kernel Hilbert space (RKHS), or because it has been defined this way to begin with, e.g., as an inner product between features that are created by passing the data through a neural network. Either way, using the SVI approach amounts to imposing an additional unnecessary approximation that comes from the need to use inducing points. As for the second approach, its applicability is highly dependent on our ability to use large batches. This can be a serious impediment in several cases, such as optimization on weak edge devices ( Chen et al. 2016 ) . In this paper, we propose two stochastic optimization algorithms based on mini-batches for maximizing the marginal likelihood of GPs (i.e., learning the hyperparameters). The first algorithm is based on reframing the problem as a nonconvex-concave minimax problem. We then leverage recent advancements in the theory of solving such problems ( Boţ & Böhm 2020 ; Lin et al. 2020 ; Luo et al. 2020 ) to propose a concrete algorithm. The second algorithm is based on writing the loss function in compositional form, i.e., as the composition of a function and the expected value of another function. We then use the recently introduced Stochastic Compositional Gradient Descent method ( Wang et al. 2017 ) . Our novel algorithms are applicable for covariance functions connected with an RKHS of a moderate dimension, and guarantee convergence of the marginal likelihood to a local minimum for any batch size without need for further approximations. In the infinite dimensional case (e.g., Gaussian covariance function) one can use our method on top of a low rank approximation of the covariance function, e.g., using the random features method Rahimi & Recht 2007 . Our experiments show that not only is our method superior to existing methods for stochastic optimization of the marginal likelihood in the finite dimensional case when the batches have a

Read the complete text