Exact O(N2) Hyper-Parameter Optimization for Gaussian Process Regression

Hyper-parameter optimization remains as the core issue of Gaussian process (GP) for machine learning nowadays. The benchmark method using maximum likelihood (ML) estimation and gradient descent (GD) is impractical for processing big data due to its O(n
³
) complexity. Many sophisticated global or local approximation models have been proposed to address such complexity issue. In this paper, we propose two novel and exact GP hyper-parameter training schemes by replacing ML with cross-validation (CV) as the fitting criterion and replacing GD with a non-linearly constrained alternating direction method of multipliers (ADMM) as the optimization method. The proposed schemes are of O(n
²
) complexity for any covariance matrix without special structure. We conduct experiments based on synthetic and real datasets, wherein the proposed schemes show excellent performance in terms of convergence, hyper-parameter estimation, and computational time in comparison with the traditional ML based routines.