# Adaptive Nystr"om for Gaussian Process Regression

arXiv: https://arxiv.org/abs/2607.27427 · HTML: https://mlsanity.com/paper/2607.27427/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 34 references that are in the map.
- First posted on arXiv 29 Jul 2026.

## Builds on (most cited first, 6 of 6)

- [Gaussian Processes for Data-Efficient Learning in Robotics and Control](https://mlsanity.com/paper/1502.02860/) (2015)
- [Distributed Gaussian Processes](https://mlsanity.com/paper/1502.02843/) (2015)
- [Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processes](https://mlsanity.com/paper/2106.01121/) (2021)
- [Deep Mixed Effect Model using Gaussian Processes: A Personalized and Reliable Prediction for Healthcare](https://mlsanity.com/paper/1806.01551/) (2018)
- [Large-Scale Low-Rank Gaussian Process Prediction with Support Points](https://mlsanity.com/paper/2207.12804/) (2022)
- [Parallel inference for massive distributed spatial data using low-rank models](https://mlsanity.com/paper/1402.1472/) (2014)

## Abstract (arXiv)

Gaussian Process Regression (GPR) is a robust framework for uncertainty quantification, yet its O(n3) complexity limits its scalability. Low-rank Nystr"om approximations can reduce this burden to O(nm2), but their accuracy depends heavily on the selection of landmark points. We propose an adaptive Nystr"om 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.