The problem of fitting a line to noisy data, also known as regression, is a classic and fundamental tool from statistics. Fast, provably efficient algorithms for solving regression are at the heart of traditional systems for artificial intelligence and data science. As modeling problems have become more complex, however, linear regression often fails to capture the high-dimensional relationships that arise in modern tasks. As such, researchers rely on sophisticated generalizations of regression, but the computational complexity of solving such problems is typically unknown (or thought to be intractable in general). The primary research goal of this project is to develop provably efficient algorithms for solving non-convex and nonlinear variants of classical linear regression and give applications to related problems in machine learning. Since tools for machine learning are now ubiquitous in science, these algorithms will have broad use across many fields. Also, these algorithms will be benchmarked experimentally against commonly used heuristics, giving rise to a wealth of projects appropriate for students at all levels.
The project centers around two open problems. First, is it possible to develop provably efficient algorithms for learning generalized linear models? In this scenario, the goal is to fit a (mildly) nonlinear function to data with respect to square loss, where the nonlinearity arises from a monotone, increasing function applied to the underlying linear form. As it turns out, algorithms for learning generalized linear models give rise to solutions for learning the dependency graph of a graphical model. This means that rich information about the features of a data set can be extracted by fitting a nonlinear function to the conditional distributions. The second problem is performing linear regression but in the presence of adversarially corrupted training sets. For example, if 90% of a data set is fit well by a linear function, it is often useful to remove the remaining 10% as outliers. Finding these outliers, however, is a difficult combinatorial problem. This project explores connections between these robust linear-regression problems and a new subfield of theoretical computer science that applies high-dimensional convex relaxations.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
