Research map / Optimization / Optimizers
Stochastic Gradient Descent for Gaussian Processes Done Right
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes stochastic dual descent (SDD), a simple SGD variant that optimises the dual kernel objective with random coordinate gradients, Nesterov momentum and geometric iterate averaging, to compute GP posterior means and samples.
Problem
Gaussian process regression requires solving a large linear system (K+λI)^{-1}y, costing cubic time in the number of observations; existing scalable options are approximations (Nyström, variational), preconditioned CG, or SGD on the primal objective.
Approach
Run stochastic gradient descent on the dual objective rather than the primal kernel ridge objective, using random-coordinate (multiplicative-noise) gradient estimates, Nesterov momentum and geometric iterate averaging, so that the step size can be ~κn larger and convergence is more stable.
Key results
- On UCI, SDD achieves lowest RMSE on all 9 datasets (e.g., 0.04 on houseelectric vs 0.87 for CG and 0.09 for SGD), and about 30% faster than SGD per step.
- On DOCKSTRING, SDD matches Attentive FP R^2 on ESR2 (0.627) and F2 (0.880), and reaches 0.790 on KIT vs 0.806 for Attentive FP.
- In large-scale Thompson sampling SDD finds the highest maximum values with the least compute in both small and large compute budgets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the dual rather than primal objective for gradient descent (ablation) | Gaussian process regression on UCI pol · UCI pol | convergence / K-norm error: 500× higher | Helped |
| Use random coordinates instead of random Fourier features (ablation) | Dual stochastic gradient descent on UCI pol · UCI pol | K-norm error | Helped |
| Subsample the whole gradient rather than only the Kα term (ablation) | Random-coordinate dual SGD on UCI pol · UCI pol | K-norm error | Helped |
| Use Nesterov momentum (ablation) | Random-coordinate dual SGD on UCI pol · UCI pol | convergence speed | Helped |
| Use geometric instead of arithmetic iterate averaging (ablation) | Random-coordinate dual SGD on UCI pol · UCI pol | K-norm error | Helped |
| Use arithmetic iterate averaging instead of unaveraged iterates (ablation) | Random-coordinate dual SGD on UCI pol · UCI pol | K-norm convergence | Hurt |
| Increase step size with the multiplicative-noise estimator (ablation) | Dual stochastic gradient descent on UCI pol · UCI pol | asymptotic quality | Helped |
| Increase batch size with the multiplicative-noise estimator (ablation) | Dual stochastic gradient descent on UCI pol · UCI pol | optimization performance | No clear effect |
Surprising findings
- Dual gradient descent tolerates step sizes about 500x larger than primal gradient descent on the pol dataset.
- Random Fourier feature (additive noise) gradient estimates perform poorly compared with random coordinate (multiplicative noise) estimates, and Polyak-Ruppert averaging can slow convergence under multiplicative noise.
Limitations
- CG is run with limited iterations on the largest datasets, and comparisons depend on matched compute budgets and hand-tuned step sizes.
- The method does not explicitly address the subspace-based convergence notion considered by Lin et al. 2023 for generalisation-sensitive settings.
- Step-size and batch-size trade-offs must be chosen case by case.
Experimental setup
Datasets: UCI regression benchmarks (pol, elevators, bike, protein, keggdirected, 3droad, song, buzz, houseelectric) synthetic Matern-3/2 GP functions on [0,1]^8 DOCKSTRING (ESR2, F2, KIT, PARP1, PGR)
Benchmarks: UCI regression large-scale Thompson sampling DOCKSTRING
Metrics: RMSE NLL wall-clock time maximum function value found R^2 K-norm error K^2-norm error
Baselines: SGD (Lin et al. 2023) preconditioned conjugate gradients SVGP Attentive FP MPNN XGBoost
Builds on: stochastic dual coordinate ascent stochastic gradient descent for Gaussian processes (Lin et al. 2023) kernel adatron kernel least-mean-square parallel Thompson sampling
Closest papers by meaning
- Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent (NeurIPS 2023 · similarity 0.91)
- Stochastic Gradient Descent in Correlated Settings: A Study on Gaussian Processes (NeurIPS 2020 · similarity 0.87)
- Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project (NeurIPS 2025 · similarity 0.86)
- Active Learning for Gaussian Process Regression Under Self-Induced Boltzmann Weights (NeurIPS 2026 · similarity 0.85)
- Improving Linear System Solvers for Hyperparameter Optimisation in Iterative Gaussian Processes (NeurIPS 2024 · similarity 0.85)
- Optimizing Posterior Samples for Bayesian Optimization via Rootfinding (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.