Ccf-Bsf: Af: Small: Collaborative Research: Practice-Friendly Theory And Algorithms For Linear Regression Problems

The project focuses on one of the most fundamental problems in the intersection of applied mathematics and computer science: solving systems of multiple linear equations in multiple variables. Such systems, also known as linear regression problems, have applications in various fields, from classical engineering to data science and machine learning. These applications yield systems with millions of equations and variables. The design of very efficient solver algorithms is thus a problem of paramount importance. Over the last twenty years there has been a tremendous focus and progress in the theory of algorithms for solving certain types of linear systems that are ubiquitous in applications, despite the fact that they are somewhat restricted (e.g. each equation has only two variables). Along with these algorithms, a wealth of new notions, techniques and tools has been acquired. The project will develop extensions of these techniques, targeting concrete applications in related fields. Towards this end, the project includes research problems that are appropriate for advanced undergraduate and graduate students with complementary interests and skills, ranging from applied to theoretical. Research will be disseminated through all standard channels, importantly including free software.The project will pursue three main directions: (i) Bring the recent progress from the theoretical to the practical realm. Linear system solvers are useful in a variety of contexts, implying a need for implementations in disparate computational environments, including basic consumer computers, graphical processing units, or big parallel and distributed systems. This necessitates the development of new theory and algorithms that are practice-friendly, i.e. designed with the practical performance end-goal in mind. (ii) The impact of linear system solvers in the downstream applications in Data Science and Machine Learning can be accelerated and strengthened by pursuing their tighter integration with the target applications. A second major goal of the project is thus to pursue an exportation of techniques and notions from the theory of linear regression to specific problems in Machine Learning. This will require the development of adaptations and enhancements of these techniques. (iii) The study of specific algorithmic applications in Machine Learning also serves the third major goal of the project: the design of solvers for regression problems that go beyond the restricted types for which efficient solvers are currently known.This award reflects National Science Foundation 's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.