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

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

• 批准号: 1813374
• 负责人: Ioannis Koutis
• 金额: $ 24.99万
• 依托单位: New Jersey Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-10-01 至 2022-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1813374&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的法定任务，并通过该基金会的知识优点和广泛的影响来评估NSF的法定任务。

项目成果

SpecPart: A Supervised Spectral Framework for Hypergraph Partitioning Solution Improvement

SpecPart：用于改进超图分区解决方案的监督谱框架

• DOI: 10.1145/3508352.3549390
• 发表时间: 2022
• 期刊: Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design
• 作者: Bustany, Ismail;Kahng, Andrew B.;Koutis, Ioannis;Pramanik, Bodhisatta;Wang, Zhiang
• 通讯作者: Wang, Zhiang

Spectral Hypergraph Partitioning Revisited

重新审视谱超图划分

• 发表时间: 2021
• 期刊: SIAM Conference on Applied and Computational Discrete Algorithms
• 作者: Pramanik, Bodhisatta;Koutis, Ioannis
• 通讯作者: Koutis, Ioannis