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

CCF-BSF：AF：小型：协作研究：线性回归问题的实用理论和算法

基本信息

批准号：
1814041
负责人：
Petros Drineas
金额：
$ 24.99万
依托单位：
Purdue University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-10-01 至 2024-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1814041&HistoricalAwards=false
关键词：
CCF BSF AF Small Collaborative

项目摘要

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.

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