Probabilistic Approximate LeastSquares
[edit]
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:676684, 2016.
Abstract
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.
Related Material



