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

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

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.