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

FRG：协作研究：随机化作为快速原型制作的资源

• 批准号: 1760316
• 负责人: Michael Mahoney
• 金额: $ 79.07万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-08-01 至 2023-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1760316&HistoricalAwards=false
• 关键词: FRG; Collaborative; Research; Randomization; Resource

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.

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

项目成果

Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update

Newton-LESS：无需权衡草图牛顿更新的稀疏化

• 发表时间: 2021
• 期刊: NeurIPS
• 作者: Michał Dereziński, Jonathan Lacotte

Sparse sketches with small inversion bias

• 发表时间: 2020-11
• 期刊: ArXiv
• 作者: Michal Derezinski;Zhenyu Liao;Edgar Dobriban;Michael W. Mahoney

Precise expressions for random projections: Low-rank approximation and randomized Newton

随机投影的精确表达式：低秩近似和随机牛顿

• 发表时间: 2020
• 期刊: NeurIPS
• 作者: M. Derezinski, F. Liang

Asymptotic Convergence Rate and Statistical Inference for Stochastic Sequential Quadratic Programming

• DOI: 10.48550/arxiv.2205.13687
• 发表时间: 2022
• 期刊: ArXiv
• 作者: Sen Na;Michael W. Mahoney

Error Estimation for Sketched SVD via the Bootstrap

• 发表时间: 2020-03
• 作者: Miles E. Lopes;N. Benjamin Erichson;Michael W. Mahoney