Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent

Gaussian processes are a powerful framework for quantifying uncertainty and for sequential decision-making but are limited by the requirement of solving linear systems. In general, this has a cubic cost in dataset size and is sensitive to conditioning. We explore stochastic gradient algorithms as a computationally efficient method of approximately solving these linear systems: we develop low-variance optimization objectives for sampling from the posterior and extend these to inducing points. Counterintuitively, stochastic gradient descent often produces accurate predictions, even in cases where it does not converge quickly to the optimum. We explain this through a spectral characterization of the implicit bias from non-convergence. We show that stochastic gradient descent produces predictive distributions close to the true posterior both in regions with sufficient data coverage, and in regions sufficiently far away from the data. Experimentally, stochastic gradient descent achieves state-of-the-art performance on sufficiently large-scale or ill-conditioned regression tasks. Its uncertainty estimates match the performance of significantly more expensive baselines on a large-scale Bayesian optimization task.

Paper

References (47)

Scroll for more · 35 remaining

Similar papers

Peer review

Reviewer xja38/10 · confidence 4/52023-06-20

Summary

I thank the authors for supplying the additional experiments and making the comparisons. It appears the technique is a novel and competitive method that can perform very well even for difficult datasets in the large-scale regime. Below is the initial review, unchanged. ------------------------------------------------------------------- The authors propose to sample from the posterior of a GP via optimisation using SGD. The authors rephrase sampling as a quadratic optimisation problem that allows an efficient approximation of the gradient using random kernel features. Then, SGD is used to find the solution. Theoretical derivations show tht the proposed algorithm gives good variance estimates in densely sampled areas as well as areas far outside the sampled regions. Further, the algorithm performs better than CG and SVGP in certain settings.

Strengths

The article provides a reltive complete package with an understandable derivation, good theoretical results and experimental evaluations. The observations of the good performance of SGD in densely sampled regions is very interesting.

Weaknesses

The article omits subset of data (SoD) methods completely, both in the related work and the experimental section. [1] introduces them as as category, [2] establish them empirically as competitive method in sampling and [3] investigates the size of the subsampling dataset. [1] A Unifying View of Sparse Approximate Gaussian Process Regression, Qui~nonero-Candela and Rasmussen (2005) [2] A Framework for Evaluating Approximation Methods for Gaussian Process Regression, Chalupka and Murray and Williams (2013) [3] Adaptive Cholesky Gaussian Processes, Bartels et al. (2023) Subsampling methods perform similarly to the proposed method as they work well in densely sampled regions and also well in regions far away from the data distributions with only region of large error in the low sampled tails. This makes comparison mandatory. The compairosn with SVGP is unfair due to the small number of inducing points (1024) and a bad optimisation algorithm for them (ADAM). It seems like the authors did not tune the competing methods well, making the resulting baselines weak. Theoretically, the authors omit in their complexity class evaluations the number of SGD steps, which might become very large. Further, the authors omit the standard work on GP, while refering to standard notation introduced by it: [4] Gaussian Processes for Machine Learning, Carl Edward Rasmussen and Christopher K. I. Williams (2006)

Questions

Question: Can you provide plots including a parameter study of SVGP including a stronger optimizer? Suggestion: I would suggest to introduce SoP method in the related work, but also compare them to the proposed method in the experimental section. I would suggest to compare them empirically to the proposed method by given them a dataset size with computation budget the same as the proposed method to allow a fair comparison on wallclock time.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

-

Reviewer w7c59/10 · confidence 4/52023-07-04

Summary

The paper presents a novel approach for sampling from GP posteriors based on SGD, which bypasses the need to solve the typical linear system of equations that is prevalent in both the exact variant (cubic in the number of query points) or the pathwise approximation (cubic in the number of data points). The SGD approximation is provided for both exact GPs and for inducing point approximations. Moreover, the approximation quality is investigated for three regions of varying data density, and explanations for the (occasionally poor) approximation quality are given.

Strengths

- __Novel, interesting idea:__ The use of SGD for atypical objectives is interesting, and the analysis of the approach is detailed from both a theoretical and empirical perspective. - __Clearly addressed limitations:__ The SGD approach is _not_ a silver bullet, and the authors make this clear by highlighting the approximation quality in data-dense regions (good), faraway regions (good), and interpolation regions (not as good). - __Informative, well-designed figures:__ The various figures are not only visually appealing, but provide . Figure 1 and 4 in particular highlight the strengths and shortcomings of the method nicely, and seamlessly add intuition as to why that is. - __Diverse Experiments:__ Experiments from both large-scale GP regression and BO are included, which demonstrates that the method is applicable and potent in both domains. - __Clear writing:__ The paper is consistently well-formulated, pedagogical and as far as I could tell, correct. Moreover, I beieve that there has been substantial effort to provide the reader with additional intuition for why the approach is effective.

Weaknesses

I struggle to find weaknesses with the paper, but remain unconvinced on its potential impact due to the relatively small niche (sampling for GPs in large data regime) that is addressed. However, I am not overly confident in this assessment, and invite the authors to challenge my opinion on this topic. For example, do the authors see opportunities for impactful follow-up work which spans other areas of ML?

Questions

- __Comparison to Pathwise Sampling:__ Does the proposed method hold any advantages to pathwise sampling in a low-to-moderate data regime in terms of accuracy or complexity? At which point (in #data points) does SGD start becoming beneficial? - __Computing the predicitve uncertainty:__ Perhaps a trivial question, but how is the predicitve uncertainty computed when one can only access the posterior mean and samples from the posterior (and not the posterior variance) in Section 4.1?

Rating

9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

Limitations are adequately addressed.

Reviewer Hc1f7/10 · confidence 5/52023-07-05

Summary

This work proposes SGD GP, a method based on stochastic gradient descent to efficiently compute the GP posterior samples given fixed hyperparameters. The method relies on the pathwise conditioning GP posterior formulation and random Fourier features (RFF) approximation. The key idea is to express the GP posterior quantities as solutions to quadratic optimization problems whose objective is a sum over data points and hence SGD can be applied. The paper shows that SGD GP produce accurate predictions. However, SGD GP can converge slowly or converge to sub-optimum. However, non-convergence behaviors of SGD only occur in region closed to the data boundary. SGD GP performs comparably to SVGP and conjugate gradients (CG) in most settings, and can outperform them in large-scale systems or ill-conditioned problems.

Strengths

- The paper is overall well-written and easy to follow. - The proposed method is novel and sound. It is shown to provide better predictive performance given the same inference time compared to SVGP and CG. What I found is most compelling is that SGD-GP seems to be a stronger alternative in large-scale or ill-conditioned systems. - I also find the spectral analysis of SGD convergence of three different regions to be very insightful.

Weaknesses

- The major weakness is that the setting the paper considers is quite limited, which is the posterior inference given fixed learned hyperparameter. I would appreciate if the authors can elaborate on the significance of the setting and why the proposed methodology is in particular important. For example, how often would the ill-conditioned systems arise in practice and how common is the case that hyperparameters are known in advance. It also seems like the method is applied to a isotropic Gaussian likelihood (see the question section below). - The fact that SGD converges slowly in extrapolation region is a bit concerning. Especially in applications like Bayesian optimization, this is the region of high interests for exploration. Or in settings where there are distribution shifts, the under-calibrated uncertainty in this region can be an issue. In general, I found the "benign non-convergence" argument in the extrapolation region not convincing. Would appreciate if the authors can elaborate on this issue, and if if there is any potential way to alleviate the non-convergence property? - The SGD convergence analysis is insightful. But I would appreciate a more formal mathematical characterization of three regions.

Questions

- Related to the first point above, can the method be adapted for broader settings where the hyperparameters need to be learned, or the likelihood is not Gaussian? If not, what is the limiting factor there? - Regarding the experiment evaluation, sec 4.1, is the predictive RMSE and NLL good metrics for evaluation? If I understand it correctly, SGD and CG are based on the same set of learned hyperpararmeters (and SVGP is based on a separately learned variational model). The core goal of the comparison is whether SGD recovers more faithful inference approximation compared to CG as a baseline. So I thought the valuable metric should be a distance against the "exact" inference result (e.g. CG with max. number of iterations and with high numeric precision). So I am not sure how to interpret Table 1. - In Fig 3 and Fig 5, do you have a sense why CG errors first go up and then go down? In Fig 5 last panel (houseelectric) would you expect CG error to match SGD performance eventually if running for more time? In both figures, I think it would be helpful to provide an exact baseline (e.g. CG ran to reach tolerance like1e-3). Minor comments. - A few notations and figures are not very clear. E.g. Fig 4. top left panel, indicate the size of error bands (blue shaded area) and dotted black line; top right corner, indicate the black dots (observations). In Proposition 1, define G-sub-gaussian.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

The limitation discussion is missing. I don't think the paper would have negative societal impact. My main concern on technical limitaiton is weakness point 1.

Reviewer Hdii8/10 · confidence 3/52023-07-07

Summary

This paper introduces a method for fast approximating a Gaussian process posterior when the data size is large. Exact computation complexity would be cubic in the data size, while this method is linear. It originates from the idea of pairwise conditioning of Gaussian process, where the law of Gaussian process posterior is expressed in terms of the law of Gaussian process prior. Decomposition into eigenfunctions gives a way of approximating the Gaussian process posterior, so the posterior inference transforms into appropriately choosing the coefficients of decomposition. Objectives are formed quadratic in the coefficients, which can be optimized with SGD for the sake of lower computational complexity compared to conjugate gradient methods. Ideas of inducing points are also discussed for reducing the data size needed. Intuitive discussion of errors in different regions are companied by figure illustrations as well as some theoretical results. Adequate numerical experiments are presented to support the method.

Strengths

1. The paper has clear descriptions and is well written. 2. The ideas are mostly original and combine the advantages of multiple methods. 3. Many figure illustrations are present, making the ideas easily understood. 4. Supportive numerical experiments are conducted. 5. The problem of reducing the computational complexity of Gaussian process posteriors is itself very important and meaningful.

Weaknesses

It would be nice to discuss why the Fourier basis are used for eigen decomposition and how it performs compared to other basis such as wavelets.

Questions

To control the approximation error below a constant threshold, how does the number of basis L (number of components) needed scales with the data size and dimension? Either theoretical or numerical result could be interesting.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

See Weaknesses and Questions.

Reviewer w7c52023-08-10

Thank you!

Thanks to the authors for addressing my questions. I am very much aware of the BO implications, but I value the references to other use-cases, which points to the potentially substantial impact of the work. This paper was a pleasure to read. Once again, I greatly appreciated the clearly addressed limitations, which should not go unnoted. I have increased my score to a 9.

Reviewer Hc1f2023-08-17

I want to thank the authors for their thoughtful response. Most of my questions are touched and addressed. However, my concern on the potential impact of this work is not fully resolved. In the authors response to Reviewer w7c5, two promising applications are (1) large-scale BO (with parallel Thompson sampling), and (2) large-scale spatio-temporal modeling. The paper investigates the first application in a synthetic setting (correct me if I am wrong). While the results seem encouraging, it would be more convincing to conduct the experiments in benchmark BO datasets (ideally also ill-conditioned to demonstrate its advantage). Is there a reason that the authors did not choose to do so? For (2), since the proposed method can only perform posterior sampling given fixed hyper-parameters instead of _learning_ the hyperparameters, how can it be useful for sptaio-temporal modeling? Is there a scenario where the large-scale posterior sampling is of interest in that domain? Again, I wanted to say that I believe the proposed method could potentially shine in many applications. However, I feel the paper and the authors response haven't really touched upon its real applicability. I would be happy to raise my score once this concern is addressed.

Authorsrebuttal2023-08-18

Real applicability: BO over molecular properties with Tanimoto kernel and more

Thank you very much for your reply! We go on to describe our ongoing work on the application of SGD GPs to molecular property prediction as well as how the method can be applied more generally, for instance, to spatiotemporal modeling. ---- 1. We are currently working on **applying SGD inference to molecular binding energy prediction** using a dataset of 250k molecules introduced by [1]. We are using the Tanimoto kernel for graphs, which admits random features ([2]). In particular, we are searching for molecules which have a high probability of binding to proteins of interest using Bayesian Optimization. * The Tanimoto kernel only has 1 hyperparameter, the marginal kernel variance. For this task, the **authors of [1] provide an optimized kernel hyperparameter** value, which they used in their experiments. Additionally, the **authors of [3] show how marginal kernel variances can be learnt using only GP posterior samples.** Thus, our SGD-based inference can be directly applied to this setting for learning the Tanimoto kernel’s hyperparameter. * Although there is not enough time to conclude these experiments before the end of the discussion period (the 21st), we would be happy to include them in the camera-ready version of the paper. 2. **We think that GP inference methods can be useful even without hyperparameter learning.** A simple but general and effective approach to select hyperparameters is to **maximize the marginal likelihood on clustered subsets of the data**, as we do in our paper (See Appendix A.1). This yields results competitive with, and in some datasets outperforming, the hyperparameters learnt via conjugate gradients of [4]. This approach is particularly well-suited to length scale hyperparameters, which are of key importance in spatiotemporal modeling. 3. Next, **ill-conditioning appears consistently for large enough datasets or when the kernel distance between observations is small** (in fact, *often provably so* - see Section 2.3 of [5]), so one does not need to search particularly hard to find examples. The latter is bound to occur in Bayesian optimization, since methods often explore near previously-found well-performing locations. 4. Finally, there is strong precedent in the Gaussian processes where (a) **a novel method with significant advantages but important limitations was introduced**, and (b) **the limitations were addressed through follow-up work**. * For example, Titsias [6] introduced the variational-inference-based view of sparse Gaussian processes, developing a novel formalism for inducing points, whose complexity is $O(NM^2)$ - larger than for instance certain subset-of-data methods. Then, Hensman et al. [7] reduced this to $O(M^3)$ - a major improvement when $N$ is in the millions - by applying stochastic optimization to the variational inference objective. Achieving this improvement was only possible because the variational viewpoint had been developed previously. * Mirroring this example, **we expect that follow-up work, using for instance bilevel optimization techniques, can address limitations around hyperparameter learning** (for examples of such techniques in a neural network context, see [8,9]). This would start from the ideas we developed, but would likely introduce enough additional theoretical and methodological contributions, as well as experimental evaluation specific to hyperparameter optimization, to constitute another paper. [1] *DOCKSTRING: Easy Molecular Docking Yields Better Benchmarks for Ligand Design.* Miguel García-Ortegón*, Gregor N. C. Simm, Austin J. Tripp, José Miguel Hernández-Lobato, Andreas Bender, and Sergio Bacallado [2] *Tanimoto Random Features for Scalable Molecular Machine Learning*. Austin Tripp, Sergio Bacallado, Sukriti Singh, José Miguel Hernández-Lobato [3] *Sampling-based inference for large linear models, with application to linearised Laplace.* Javier Antorán, Shreyas Padhy, Riccardo Barbano, Eric Nalisnick, David Janz, José Miguel Hernández-Lobato [4] *Exact Gaussian Processes on a Million Data Points.* Ke Alexander Wang, Geoff Pleiss, Jacob R. Gardner, Stephen Tyree, Kilian Q. Weinberger, Andrew Gordon Wilson [5] *Numerically Stable Sparse Gaussian Processes via Minimum Separation using Cover Trees*. Alexander Terenin, David R. Burt, Artem Artemev, Seth Flaxman, Mark van der Wilk, Carl Edward Rasmussen, Hong Ge [6] *Variational learning of inducing variables in sparse Gaussian processes*. Michalis Titsias [7] *Gaussian processes for big data*. James Hensman, Nicolò Fusi, Neil Lawrence. [8] *Scalable One-Pass Optimisation of High-Dimensional Weight-Update Hyperparameters by Implicit Differentiation*. Ross M. Clarke, Elre T. Oldewage, José Miguel Hernández-Lobato [9] *Generalized Inner Loop Meta-Learning*. Edward Grefenstette, Brandon Amos, Denis Yarats, Phu Mon Htut, Artem Molchanov, Franziska Meier, Douwe Kiela, Kyunghyun Cho, Soumith Chintala

Reviewer Hc1f2023-08-18

Thanks to the authors for their response! These additional materials definitely strengthen the paper and would be great to be incorporated into the final version. I have raised my score from 6 to 7.

Reviewer Hdii2023-08-21

Thank you for the further explanations and responses to several questions. I am pretty satisfied with them and will keep the score as is.

Program Chairsdecision2023-09-21

Decision

Accept (oral)

© 2026 NYSGPT2525 LLC