Computer Sciences Colloquium: Matrix Sketching Algorithms for Faster Linear and Non-linear Regression

Abstract: 

Least-squares regression is an important statistical and computational problem whose origin can be traced back to the work of Legendre and Gauss in the early 19th century. In the linear setting, it is a well-studied problem, with highly refined algorithms and high-quality software implementations. Nevertheless, matrix sketching has recently emerged as a key algorithmic device which enables a dramatic acceleration that often beats these traditional methods. However, so far this line of work has mostly addressed linear regression only. After surveying the basic algorithmic paradigms that enables fast linear regression, and state-of-the-art matrix sketching algorithms for it, we will discuss recent work on non-linear regression. In particular, we will discuss algorithms for regularized polynomial regression, and for kernel ridge regression.