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

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

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.