Greedy block coordinate descent for large scale Gaussian process regression

Liefeng Bo, Cristian Sminchisescu
Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, PMLR R6:43-52, 2008.

Abstract

We propose a variable decomposition algorithm-greedy block coordinate descent (GBCD)-in order to make dense Gaussian process regression 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 sub-problem (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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR6-bo08a, title = {Greedy block coordinate descent for large scale Gaussian process regression}, author = {Bo, Liefeng and Sminchisescu, Cristian}, booktitle = {Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence}, pages = {43--52}, year = {2008}, editor = {McAllester, David A. and Myllymäki, Petri}, volume = {R6}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r6/main/assets/bo08a/bo08a.pdf}, url = {https://proceedings.mlr.press/r6/bo08a.html}, abstract = {We propose a variable decomposition algorithm-greedy block coordinate descent (GBCD)-in order to make dense Gaussian process regression 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 sub-problem (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.}, note = {Reissued by PMLR on 09 October 2024.} }
Endnote
%0 Conference Paper %T Greedy block coordinate descent for large scale Gaussian process regression %A Liefeng Bo %A Cristian Sminchisescu %B Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2008 %E David A. McAllester %E Petri Myllymäki %F pmlr-vR6-bo08a %I PMLR %P 43--52 %U https://proceedings.mlr.press/r6/bo08a.html %V R6 %X We propose a variable decomposition algorithm-greedy block coordinate descent (GBCD)-in order to make dense Gaussian process regression 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 sub-problem (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. %Z Reissued by PMLR on 09 October 2024.
APA
Bo, L. & Sminchisescu, C.. (2008). Greedy block coordinate descent for large scale Gaussian process regression. Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R6:43-52 Available from https://proceedings.mlr.press/r6/bo08a.html. Reissued by PMLR on 09 October 2024.

Related Material