On Random Subsampling of Gaussian Process Regression: A Graphon-Based Analysis
This work addresses computational efficiency in Gaussian process regression for practitioners, but it is incremental as it builds on existing subsampling techniques with theoretical analysis.
The paper tackles the problem of approximating Gaussian process regression via random subsampling, showing provable guarantees on predictive accuracy and generalization. Experimental results indicate that subsampling achieves a better trade-off between accuracy and runtime compared to Nyström and random Fourier expansion methods.
In this paper, we study random subsampling of Gaussian process regression, one of the simplest approximation baselines, from a theoretical perspective. Although subsampling discards a large part of training data, we show provable guarantees on the accuracy of the predictive mean/variance and its generalization ability. For analysis, we consider embedding kernel matrices into graphons, which encapsulate the difference of the sample size and enables us to evaluate the approximation and generalization errors in a unified manner. The experimental results show that the subsampling approximation achieves a better trade-off regarding accuracy and runtime than the Nyström and random Fourier expansion methods.