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

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

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.