Abstract
Gaussian processes (GPs) provide a principled nonparametric representation of functions but suffer from $O(N^3)$ computational complexity. We propose EigenGP, a sparse Bayesian approach that learns adaptive eigenfunctions—compact basis dictionary elements—within a reproducing kernel Hilbert space. By optimizing these eigenfunctions and prior precisions via marginal likelihood maximization, EigenGP achieves superior predictive performance and handles nonstationary data more effectively than traditional sparse GP methods.
The Scalability Challenge
Gaussian Processes are favored for their robust uncertainty estimates, yet their computational cost ($O(N^3)$ time, $O(N^2)$ space) limits their application to small datasets. Existing sparse approximations often rely on fixed basis functions (e.g., Sparse Spectrum GPs) or heuristic basis placement (e.g., K-means in Nyström methods). These approaches struggle with nonstationary data, where function behavior varies across the input space, and often fail to capture critical data trends due to suboptimal basis positioning.
The EigenGP Approach
EigenGP addresses these limitations by projecting the GP prior into an eigensubspace where the basis functions are not fixed but adaptive.
- Adaptive Eigenfunctions: Eigenfunctions are defined as finite linear combinations of kernel functions in a Reproducing Kernel Hilbert Space (RKHS). Among all orthogonal bases, eigenfunctions provide the most compact representation of a GP.
- Nyström Approximation: The model uses the Nyström method to compute these eigenfunctions efficiently using a small set of inducing inputs.
- Full Evidence Maximization: Unlike methods that fix inducing points or hyperparameters, EigenGP optimizes the inducing points, kernel lengthscales, and prior precisions simultaneously by maximizing the marginal likelihood (the "evidence").
- Computational Efficiency: Leveraging computational linear algebra, the authors maintain a training cost of $O(NM^2)$, where $M$ is the number of basis functions, ensuring linear scalability with the number of data points $N$.
Key Insights: Optimization vs. Heuristics
A central finding is that optimizing basis points via evidence maximization is significantly more effective than using heuristics like K-means clustering.
As shown in the figure above, K-means often places basis points in locations that fail to capture the underlying function's complexity. In contrast, EigenGP's adaptive approach aligns the basis functions with the data's structure, providing a more compact and accurate representation. This allows the model to adapt its "wiggliness" to different parts of the input space, effectively handling nonstationarity for free.
Results and Nonstationary Performance
EigenGP was evaluated against standard benchmarks like FITC and SSGP. On synthetic nonstationary data ($f(x) = x \sin(x^3)$), EigenGP demonstrated a unique ability to adapt to the increasing frequency and amplitude of the signal.
While SSGP produced "wavy" artifacts in regions lacking data and FITC struggled with the varying frequency, EigenGP accurately tracked the signal. On large-scale real-world datasets—including California Housing (10k samples) and Protein Tertiary Structures (20k samples)—EigenGP consistently achieved the lowest Normalized Mean Square Error (NMSE) and Mean Negative Log Probability (MNLP) compared to alternative sparse GP methods and Relevance Vector Machines (RVM).
Conclusion
EigenGP provides a powerful framework for scaling GPs while maintaining high predictive accuracy. By learning adaptive eigenfunctions, it bridges the gap between fixed-basis sparse models and full GP inference. While the finite nature of the model can sometimes lead to underestimated uncertainty far from data, it represents a significant step forward in making GPs practical for large, nonstationary datasets.
Summary updated