Liefeng Bo

Toyota Technological Institute at Chicago, USA

Cristian Sminchisescu

Institute for Numerical Simulation, University of Bonn, Germany

Abstract: We propose a variable decomposition algorithm - greedy block coordinate descent (GBCD) [1] - in order to make dense Gaussian process regression [2] practical for large scale problems. GBCD breaks a large scale optimization into a series of small sub-problems. The challenge in variable decomposition algorithms is the identification of a subproblem (the active set of variables) that yields the largest improvement. We analyze the limitations of existing methods and cast the active set selection into a zero-norm constrained optimization problem that we solve using greedy methods. By directly estimating the decrease in the objective function, we obtain not only efficient approximate solutions for GBCD, but we are also able to demonstrate that the method is globally convergent. Empirical comparisons against competing dense methods like Conjugate Gradient or SMO show that GBCD is an order of magnitude faster. Comparisons against sparse GP methods show that GBCD is both accurate and capable of handling datasets of 100,000 samples or more.

References

1. Liefeng Bo and Cristian Sminchisescu, Greedy Block Coordinate Descent for Large Scale Gaussian Process Regression, In The Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI), July 2008. [PDF] [BIB]

2. C. Rasmussen and C. Williams, Gaussian Processes for Machine Learning. Adaptive Computation and Machine Learning, The MIT Press, 2006.