AF: Medium: Collaborative Research: Beyond Sparsity: Refined Measures of Complexity for Linear Algebra

AF：媒介：协作研究：超越稀疏性：线性代数复杂性的精确度量

• 批准号: 1763481
• 负责人: Atri Rudra
• 金额: $ 46.94万
• 依托单位: SUNY at Buffalo
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-03-15 至 2023-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1763481&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; Beyond

Modern data science applications exploit structure in real life data using machine learning (including deep learning) algorithms. At the core of most of these systems are algorithms for a branch of mathematics called linear algebra. In particular, a large portion of these algorithms utilize the fact that real life data has properties that can be captured using certain parsimonious linear algebraic structures. This project studies new, more powerful linear algebraic structures and algorithms that exploit these new structures. Given the fundamental importance of these algorithms, ideas generated from this project are expected to be implemented in widely deployed machine learning systems. The outreach component of this project involves (1) a technical workshop for researchers from diverse areas and (2) outreach events for K-12 students.A variety of problems in modern data science have been successfully characterized using a width. For example, one of the most common widths, the rank of a matrix, has a near-ubiquitous use across many applications. This project significantly expands the understanding of several recently proposed widths and extracts their full potential for positive practical outcomes. Furthermore, it contributes to the recently growing work on beyond worst-case analysis in linear algebra, machine learning and coding theory.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.

现代数据科学应用程序使用机器学习（包括深度学习）算法来利用现实生活数据中的结构。大多数这些系统的核心是线性代数数学分支的算法。特别是，这些算法的很大一部分利用了这样一个事实：现实生活中的数据具有可以使用某些简约的线性代数结构来捕获的属性。该项目研究新的、更强大的线性代数结构和利用这些新结构的算法。鉴于这些算法的根本重要性，该项目产生的想法预计将在广泛部署的机器学习系统中得到实现。该项目的外展部分包括 (1) 为来自不同领域的研究人员举办的技术研讨会和 (2) 为 K-12 学生举办的外展活动。现代数据科学中的各种问题已成功使用宽度进行表征。例如，最常见的宽度之一，即矩阵的秩，在许多应用中几乎无处不在。该项目极大地扩展了对最近提出的几种宽度的理解，并充分发挥其积极实际成果的潜力。此外，它还有助于最近在线性代数、机器学习和编码理论中超越最坏情况分析的工作。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness

FlashAttention：具有 IO 感知功能的快速、内存高效的精确注意力

• 发表时间: 2022-12
• 期刊: Proceedings of the 35th Neural Information Processing Systems Conference (NeurIPS
• 作者: Dao, Tri;Fu, Daniel Y.;Ermon, Stefano;Rudra, Atri;Ré, Christopher
• 通讯作者: Ré, Christopher

Hypertree Decompositions Revisited for PGMs

重新审视 PGM 的超树分解

• 发表时间: 2018-07
• 期刊: International Workshop on Statistical Relational AI
• 作者: Arun, Aarthy S;Mani Jayaraman, Sai Vikneshwar;Re, Christopher;Rudra, Atri
• 通讯作者: Rudra, Atri

Simple Hardware-Efficient Long Convolutions for Sequence Modeling

用于序列建模的简单硬件高效长卷积

• DOI: 10.48550/arxiv.2302.06646
• 发表时间: 2023-02-13
• 期刊: ArXiv
• 作者: Daniel Y. Fu;Elliot L. Epstein;Eric N. D. Nguyen;A. Thomas;Michael Zhang;Tri Dao;A. Rudra;Christopher Ré
• 通讯作者: Christopher Ré

Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations

使用蝴蝶分解学习线性变换的快速算法

• 发表时间: 2019-06
• 期刊: Proceedings of Machine Learning Research
• 作者: Dao, Tri;Gu, Albert;Eichhorn, Matthew;Rudra, Atri;Re, Christopher
• 通讯作者: Re, Christopher

Sparse Recovery for Orthogonal Polynomial Transforms

正交多项式变换的稀疏恢复

• DOI: 10.4230/lipics.icalp.2020.58
• 发表时间: 2020-06
• 期刊: Leibniz international proceedings in informatics
• 作者: Gilbert, Anna;Gu, Albert;Re, Christopher;Rudra, Atri;Wootters, Mary
• 通讯作者: Wootters, Mary