Leastsquares and kernelridge / Gaussian process regression are among the foundational algorithms of statistics and machine learning. Famously, the worstcase cost of exact nonparametric regression grows cubically with the dataset size; but a growing number of approximations have been developed that estimate good solutions at lower cost. These algorithms typically return point estimators, without measures of uncertainty. Leveraging recent results casting elementary linear algebra operations as probabilistic inference, we propose a new approximate method for nonparametric leastsquares that affords a probabilistic uncertainty estimate over the error between the approximate and exact leastsquares solution (this is not the same as the posterior variance of the associated Gaussian process regressor). This allows estimating the error of the leastsquares solution on a subset of the data relative to the fulldata solution. The uncertainty can be used to control the computational effort invested in the approximation. Our algorithm has linear cost in the dataset size, and a simple formal form, so that it can be implemented with a few lines of code in programming languages with linear algebra functionality.
Author(s):  Bartels, S. and Hennig, P. 
Book Title:  Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS 2016) 
Volume:  51 
Pages:  676684 
Year:  2016 
Series:  JMLR Workshop and Conference Proceedings 
Editors:  Gretton, A. and Robert, C. C. 
Department(s):  Empirical Inference, Probabilistic Numerics 
Research Project(s): 
Probabilistic Methods for Linear Algebra

Bibtex Type:  Conference Paper (conference) 
Event Place:  Cadiz, Spain 
State:  Published 
URL:  http://jmlr.org/proceedings/papers/v51/bartels16.html 
Additional (custom) Fields:  
link:  http://jmlr.org/proceedings/papers/v51/bartels16.pdf 
Attachments:  
BibTex @conference{BarHen16, title = {Probabilistic Approximate LeastSquares}, author = {Bartels, S. and Hennig, P.}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS 2016)}, volume = {51}, pages = {676684}, series = {JMLR Workshop and Conference Proceedings}, editors = {Gretton, A. and Robert, C. C. }, year = {2016}, url = {http://jmlr.org/proceedings/papers/v51/bartels16.html} } 