FRG: Collaborative Research: Randomization as a Resource for Rapid Prototyping

将开发快速原型数据分析方法的原则性基础。主要的方法将是使用快速随机矩阵算法，该算法是在被称为随机数字线性代数(RandNLA)的研究领域内开发的。先前的工作已经表明，这些RandNLA算法具有强大的理论基础，并且它们在许多实际数据科学和机器学习问题上表现良好。该基金会将开发随机化的新用途，将互补的算法和统计学观点结合起来。统计学观点将随机性归因于数据固有的和所需的属性，而算法观点则声称随机性是一种有待开发的计算资源。这些互补方法的耦合提出了要在拟议的工作中研究的具有挑战性的数学问题。拟议的工作将在两个方向上为快速原型建立基础：多管齐下的方向将RandNLA带到下一个水平并探索什么是技术可行的；以及总体协同方向，融合结果用于原型。多管齐下的方向包括以下主题：(I)矩阵扰动理论，一方面弥补了渐近小扰动的传统最坏情况界之间的差距；另一方面弥补了随机噪声引起的扰动和丢失或严重损坏的矩阵条目之间的差距。(Ii)隐式正则化与显式正则化，其中随机性作为加速算法的计算资源另外有助于隐式统计正则化，从而提高统计和数值稳健性。(3)Krylov空间方法，用于快速计算良好的热启动和低阶近似形式的代理模型，特别是在与算法无关的情况下更好地理解这些方法。(4)随机基构造法，它使用矩阵因式分解来计算中低精度的低阶近似。协同方向将探索机器学习应用程序中的超低精度矩阵计算等主题，在这些应用程序中，只需正确的符号或指数就足够了。作为一个群体，PI在将基本数学工具应用于机器学习、数据挖掘和科学计算的数值应用方面拥有无与伦比和互补的专业知识。重要的是，提出的方法将对大数据分析、科学计算、数据挖掘和机器学习产生重大影响，在这些领域，矩阵计算至关重要。拟议的工作从根本上是跨学科的，将能够快速、但用户友好地从这些具有社会重要性的科学领域的大规模数据中提取洞察力。具体地说，拟议的工作将：(1)为快速原型建立一个可靠和牢固的数值基础；(2)在计算机科学和统计学的界面上推进数学，其目标之一是使数值和统计的稳健性协同作用；(3)推动发展一个跨学科的社区，而兰德-作为数据数学的支柱。该奖项将允许研究人员更积极地接触本科生和研究生，以及数值线性代数、理论计算机科学、机器学习和天文学、材料科学和遗传学等科学领域的研究社区。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

A principled foundation for fast prototyping data analysis methods will be developed. The main approach will be to use fast randomized matrix algorithms, as developed within the research area known as Randomized Numerical Linear Algebra (RandNLA). Prior work has shown that these RandNLA algorithms come with strong theory and that they perform well for many practical data science and machine learning problems. The foundation will develop novel uses of randomization to combine complementary algorithmic and statistical perspectives. The statistical viewpoint attributes randomness to an inherent and desirable property of the data, while the algorithmic viewpoint claims randomness as a computational resource to be exploited. The coupling of these complementary approaches poses challenging mathematical problems to be investigated in the proposed work.The proposed work will establish the foundations for fast prototyping in two directions: A Multi-Pronged Direction to bring RandNLA to the next level and explore what is technically feasible; and an overarching Synergy Direction that fuses the results for prototyping. The Multi-Pronged Direction includes the following topics: (i) Matrix perturbation theory, to bridge the gap between traditional worst-case bounds for asymptotically small perturbations on the one hand; and perturbations caused by stochastic noise, and missing or highly corrupted matrix entries on the other hand. (ii) Implicit versus explicit regularization, where randomness as a computational resource for speeding up algorithms additionally contributes to implicit statistical regularization, thereby improving statistical and numerical robustness. (iii) Krylov space methods for fast computation of good warm-starts and computation of surrogate models in the form of low-rank approximations, and specifically a better understanding of these methods in an algorithm-independent setting. (iv) Randomized basis construction methods that use matrix factorizations to compute low-rank approximations at low to moderate levels of accuracy. The Synergy Direction will explore topics like ultra-low accuracy matrix computations in machine learning applications, where merely a correct sign or exponent is sufficient. As a group, the PIs possess unrivaled and complementary expertise in applying fundamental mathematical tools to numerical applications in machine learning, data mining and scientific computing. Importantly, the proposed methods will have significant impact in big data analysis, scientific computing, data mining and machine learning, where matrix computations are of paramount importance. The proposed work is fundamentally interdisciplinary and will enable fast, yet user-friendly extraction of insight from large-scale data these societally-important scientific domains. Specifically, the proposed work will (i) create a numerically reliable and robust footing for fast prototyping; (ii) advance mathematics at the interface of computer science and statistics, one of the objectives being a synergy of numerical and statistical robustness; and (iii) advance the development of an interdisciplinary community with RandNLA as a pillar for the mathematics of data. The award will allow the investigators to increase their active engagement in reaching out to undergraduate and graduate students, and research communities in numerical linear algebra, theoretical computer science, machine learning, and scientific domains such as astronomy, materials science, and genetics.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.