Header logo is

Probabilistic Approximate Least-Squares


Conference Paper



Least-squares and kernel-ridge / Gaussian process regression are among the foundational algorithms of statistics and machine learning. Famously, the worst-case cost of exact nonparametric regression grows cubically with the data-set 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 least-squares that affords a probabilistic uncertainty estimate over the error between the approximate and exact least-squares solution (this is not the same as the posterior variance of the associated Gaussian process regressor). This allows estimating the error of the least-squares solution on a subset of the data relative to the full-data solution. The uncertainty can be used to control the computational effort invested in the approximation. Our algorithm has linear cost in the data-set 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)
Volume: 51
Pages: 676--684
Year: 2016
Month: May
Series: JMLR Workshop and Conference Proceedings
Editors: Gretton, A. and Robert, C. C.

Department(s): Empirical Inference, Probabilistic Numerics
Research Project(s): Probabilistic Inference
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


  title = {Probabilistic Approximate Least-Squares},
  author = {Bartels, S. and Hennig, P.},
  booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS)},
  volume = {51},
  pages = {676--684},
  series = {JMLR Workshop and Conference Proceedings},
  editors = {Gretton, A. and Robert, C. C. },
  month = may,
  year = {2016},
  url = {http://jmlr.org/proceedings/papers/v51/bartels16.html},
  month_numeric = {5}