III: Small: Combining Stochastics and Numerics for Improved Scalable Matrix Computations

III：小型：结合随机变量和数值以改进可扩展矩阵计算

• 批准号: 1815054
• 负责人: Michael Mahoney
• 金额: $ 50万
• 依托单位: International Computer Science Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1815054&HistoricalAwards=false
• 关键词: III; Small; Combining; Stochastics; Numerics

Data are often modeled as matrices. As a result, linear algebraic algorithms, and in particular matrix decompositions, have proven extremely successful in the analysis of datasets in the form of matrices. RandNLA (Randomized Numerical Linear Algebra), which integrates the complementary perspectives that theoretical computer science and numerical linear algebra bring to matrix computations, has led to nontrivial theory and high-quality implementations, and it has proven useful in a range of scientific and internet applications. This project will addresses statistical properties of RandNLA algorithms, and how these algorithms are used in downstream convex and non-convex optimization pipelines. This project will facilitate the development of algorithmic methods for the extraction of knowledge from large genetic, medical, internet, financial, astronomical, and other scientific data sets, and it will also focus on broader interdisciplinary educational opportunities, including undergraduate courses on the mathematics of data science. Examples of technical challenges of interest include that the randomness inside the algorithm can lead to implicit regularization, and that it can also lead to usefulness in downstream applications that is not captured by existing theory. These and other challenges will be addressed in several complementary ways. First, by developing bootstrapping methods for core RandNLA algorithms. Second, by developing improved statistical analysis of core RandNLA algorithms. Third, by developing non-linear leverage scores for more general statistical objectives. Fourth, by developing methods to combine in a principled manner SGD and RandNLA. And fifth, by providing implementations addressing scientific data analysis applications, and also by considering longer-term directions of interdisciplinary interest. In each case, there will be a focus on complementary stochastic and numerical aspects of RandNLA algorithms, as well as on how RandNLA primitives are used in realistic convex and non-convex machine learning pipelines. This will lead to new insights in algorithmic and statistical theory, as well as more useful algorithms in practical implementations and applications.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.

数据通常被建模为矩阵。 因此，线性代数算法，特别是矩阵分解，已经证明在矩阵形式的数据集分析中非常成功。 RandNLA（随机数值线性代数）集成了理论计算机科学和数值线性代数为矩阵计算带来的互补观点，导致了非平凡的理论和高质量的实现，并已被证明在一系列科学和互联网应用中非常有用。 该项目将解决RandNLA算法的统计特性，以及如何在下游凸和非凸优化管道中使用这些算法。 该项目将促进算法方法的开发，用于从大型遗传，医学，互联网，金融，天文和其他科学数据集中提取知识，并将重点关注更广泛的跨学科教育机会，包括数据科学数学的本科课程。感兴趣的技术挑战的例子包括算法内部的随机性可能导致隐式正则化，并且它还可能导致现有理论无法捕获的下游应用程序中的有用性。 这些挑战和其他挑战将以几种相辅相成的方式加以解决。 首先，通过开发核心RandNLA算法的自举方法。 第二，通过开发改进的核心RandNLA算法的统计分析。 第三，通过为更一般的统计目标开发非线性杠杆分数。 第四，通过开发方法，以原则性的方式将SGD和RandNLA联合收割机结合起来。 第五，通过提供解决科学数据分析应用的实现，以及考虑跨学科兴趣的长期方向。 在每种情况下，将重点关注RandNLA算法的互补随机和数值方面，以及RandNLA原语如何用于现实的凸和非凸机器学习管道。 该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。