CCF-BSF: AF: Small: Collaborative Research: Practice-Friendly Theory and Algorithms for Linear Regression Problems

该项目的重点是应用数学和计算机科学交叉中最基本的问题之一：求解多变量的多线性方程组。这样的系统，也被称为线性回归问题，在各个领域都有应用，从经典工程到数据科学和机器学习。这些应用程序产生的系统有数百万个方程和变量。因此，非常有效的求解算法的设计是一个至关重要的问题。在过去的二十年里，在求解某些类型的线性系统的算法理论方面有了巨大的关注和进步，这些线性系统在应用中无处不在，尽管它们有些限制（例如每个方程只有两个变量）。沿着这些算法，大量的新概念、新技术和新工具被获得。该项目将发展这些技术的扩展，目标是在相关领域的具体应用。为此，该项目包括适合高年级本科生和研究生的研究问题，具有互补的兴趣和技能，从应用到理论。研究将通过所有标准渠道传播，其中重要的是包括自由软件。该项目将遵循三个主要方向：（i）将最新进展从理论带到实践领域。线性系统解算器在各种情况下都很有用，这意味着需要在不同的计算环境中实现，包括基本的消费者计算机，图形处理单元或大型并行和分布式系统。这就需要开发新的理论和算法，这些理论和算法是实践友好的，即在设计时考虑到实际性能的最终目标。(ii)线性系统求解器在数据科学和机器学习下游应用中的影响可以通过追求与目标应用的更紧密集成来加速和加强。因此，该项目的第二个主要目标是追求从线性回归理论到机器学习中特定问题的技术和概念的输出。这将需要对这些技术进行调整和改进。(iii)对机器学习中特定算法应用的研究也服务于该项目的第三个主要目标：设计回归问题的求解器，超越目前已知的有效求解器的受限类型。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

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 NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.