Adaptive Nyström for Gaussian Process Regression

• URL: http://arxiv.org/abs/2607.27427v1
• Date: Wed, 29 Jul 2026 19:55:12 GMT
• Title: Adaptive Nyström for Gaussian Process Regression
• Abstract summary: Low-rank Nystrm approximations can reduce this burden to $O(nm2)$, but their accuracy depends heavily on the selection of landmark points.<n>We propose an adaptive Nystrm approach that greedily selects landmarks to minimize the trace residual of the kernel approximation error.
• Score: 1.14219428942199
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Gaussian Process Regression (GPR) is a robust framework for uncertainty quantification, yet its $O(n^3)$ complexity limits its scalability. Low-rank Nyström approximations can reduce this burden to $O(nm^2)$, but their accuracy depends heavily on the selection of landmark points. We propose an adaptive Nyström approach that greedily selects landmarks to minimize the trace residual of the kernel approximation error. Unlike static approximations, our method interleaves landmark expansion with hyperparameter optimization, allowing the selection process to adapt as the covariance structure is refined. Numerical experiments on five benchmark functions demonstrate that this method significantly outperforms random landmark selection in both accuracy and stability. It achieves predictive performance comparable to exact GP inference while maintaining linear scaling with respect to the sample size, providing a principled and efficient framework for large-scale computer experiments.

Related papers

• Robust Stochastic Optimization via Gradient Quantile Clipping [6.2844649973308835]
  We introduce a quant clipping strategy for Gradient Descent (SGD) We use gradient new outliers as norm clipping chains. We propose an implementation of the algorithm using Huberiles.
  arXiv  Detail & Related papers  (2023-09-29T15:24:48Z)
• Nonconvex Stochastic Bregman Proximal Gradient Method with Application to Deep Learning [9.202586157819693]
  quadratic methods for minimizing robustness for non composite objective functions typically rely on the Lipschitz smoothness of the differentiable part.<n>We propose a family of Bregman (SBPG) methods that only adaptivity.<n>MSBPG, a momentum-based variant, enhances convergence sensitivity by relaxing the minibatch size requirement.
  arXiv  Detail & Related papers  (2023-06-26T08:54:46Z)
• Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent [43.097493761380186]
  gradient algorithms are an efficient method of approximately solving linear systems. We show that gradient descent produces accurate predictions, even in cases where it does not converge quickly to the optimum. Experimentally, gradient descent achieves state-of-the-art performance on sufficiently large-scale or ill-conditioned regression tasks.
  arXiv  Detail & Related papers  (2023-06-20T15:07:37Z)
• Stochastic Marginal Likelihood Gradients using Neural Tangent Kernels [78.6096486885658]
  We introduce lower bounds to the linearized Laplace approximation of the marginal likelihood. These bounds are amenable togradient-based optimization and allow to trade off estimation accuracy against computational complexity.
  arXiv  Detail & Related papers  (2023-06-06T19:02:57Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  We develop an adaptive inexact Newton method for equality-constrained nonlinear, nonIBS optimization problems. We demonstrate the superior performance of our method on benchmark nonlinear problems, constrained logistic regression with data from LVM, and a PDE-constrained problem.
  arXiv  Detail & Related papers  (2023-05-28T06:33:37Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  Many real-world problems have complicated non functional constraints and use a large number of data points. Our proposed method outperforms an existing method with the previously best-known result.
  arXiv  Detail & Related papers  (2022-12-19T14:48:54Z)
• Scalable Gaussian-process regression and variable selection using Vecchia approximations [3.4163060063961255]
  Vecchia-based mini-batch subsampling provides unbiased gradient estimators. We propose Vecchia-based mini-batch subsampling, which provides unbiased gradient estimators.
  arXiv  Detail & Related papers  (2022-02-25T21:22:38Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sampling (AIS) and related algorithms are highly effective tools for marginal likelihood estimation. Differentiability is a desirable property as it would admit the possibility of optimizing marginal likelihood as an objective. We propose a differentiable algorithm by abandoning Metropolis-Hastings steps, which further unlocks mini-batch computation.
  arXiv  Detail & Related papers  (2021-07-21T17:10:14Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Variable selection for Gaussian process regression through a sparse projection [0.802904964931021]
  This paper presents a new variable selection approach integrated with Gaussian process (GP) regression. The choice of tuning parameters and the accuracy of the estimation are evaluated with the simulation some chosen benchmark approaches.
  arXiv  Detail & Related papers  (2020-08-25T01:06:10Z)
• SLEIPNIR: Deterministic and Provably Accurate Feature Expansion for Gaussian Process Regression with Derivatives [86.01677297601624]
  We propose a novel approach for scaling GP regression with derivatives based on quadrature Fourier features. We prove deterministic, non-asymptotic and exponentially fast decaying error bounds which apply for both the approximated kernel as well as the approximated posterior.
  arXiv  Detail & Related papers  (2020-03-05T14:33:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.