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

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

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.