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算法的互补随机和数值方面，以及如何在现实的凸和非Convex机器学习管道中使用Randnla原始图。 这将导致有关算法和统计理论的新见解，以及在实际实施和应用中更有用的算法。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的审查标准通过评估来获得支持的。