CAREER: Randomized Iterative Methods for Corrupted Data, Constrained Problems, and Compressed Updates

The scientific goal of this CAREER project is to develop theoretically-founded, randomized iterative methods for problems common in numerical linear algebra (NLA) and optimization, and extend their application and analysis to face a new and important set of challenges. The incredible growth in size and complexity of data sets commonly analyzed has made it imperative to have randomized computational techniques that are robust to adversarial error, incorporate or are adaptable to natural problem constraints, and can be applied in settings in which both the number and dimension of data are massive.

This project additionally provides opportunities for students to engage in cutting-edge research, and supports creation of materials for an advanced undergraduate-level modern numerical linear algebra course to be used at Harvey Mudd College (HMC) and beyond. This course will feature significant curricular research projects which align with the technical directions identified in this project; descriptions of potential course project topics will be released with the public course materials.

The project will additionally provide vertically-integrated mentorship opportunities for visiting graduate students, HMC undergraduates, and high school students through HMC’s federally funded Upward Bound (UB) program. Finally, the project will support an annual professional development workshop for early career participants interested in research mentorship at primarily undergraduate institutions.

The intellectual merit of this CAREER project is the development and analysis of a suite of randomized iterative methods for problems with devastating adversarial corruption, problem constraints, and extremely large data dimension. The project will focus specifically on three main research thrusts: (1) Developing and analyzing corruption-robust variants of randomized iterative methods in numerical linear algebra for least-squares regression, and generalizing these analyses to first-order methods in numerical optimization for a more general class of convex optimization problems. (2) Analyzing the iterative behavior of common combinatorial and numerical iterative methods for randomly sketched and subsampled regression problems with nonnegative and related constraints, and using these analyses to develop efficient randomized iterative methods for such problems. (3) Extending the application of randomized iterative methods to problems in which both the number and size of data may be massive by developing provably effective randomly compressed and sparsified iterative updates.

Open-source software implementations of the developed and analyzed methods will accompany the work completed under each of the above thrusts. Additionally, this work will be distributed both in formal peer-reviewed journal and conference submissions, and in educational resources for students.

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.