Outliers are not what they seem: data-aware, flexible, and robust randomized iterative methods

As the amount and size of the large-scale problems grow across the application areas, a need for scalable and efficient solvers steadily grows. Stochastic iterative methods are ubiquitous for this goal: the randomization makes such methods both more robust and theoretically treatable, and inexpensive iterative steps make them scalable and parallelizable and allow for flexibility in the step design. In addition, the data frequently have some underlying structure that the algorithm can exploit, and to build truly flexible and powerful randomized iterative algorithms we need to learn how to use this information efficiently. The general goal of this project is to advance the understanding of how the data-aware and task-adaptive exploration stage can inform the design of the iterative steps of stochastic algorithms to guide them toward a particular learning task. Examples of such learning tasks include corruption removal, exploration of external knowledge, data regularization, or search for multiple solutions. In addition to the scientific impact, this project will contribute to the broad dissemination of the scientific knowledge via the talks, events organization, and open-sourced codes, and provides student support and research training opportunities. This project aims to create a range of flexible data- and task-augmented randomized iterative methods. A crucial component of the work is to develop new relevant mathematical tools for proving the convergence properties of such algorithms. The theoretical analysis of the algorithms involves methods of high-dimensional probability and geometry, numerical analysis and linear algebra, as well as optimization and random matrix theory. Moreover, it motivates developing supporting results of independent interest, such as novel spectral bounds for structured random matrices, high-dimensional concentration of measure estimates, and new geometric and probabilistic approaches for tighter control of stochastic iterates. The planned byproducts of this project include new corruptions-robust variants of the algorithms widely used in compressed sensing, low-rank tensor fitting, and first-order stochastic optimization; new linear solvers augmented with side knowledge as well as their applications to finding multiple solutions to partial and ordinary differential equations; and data-aware iterative algorithms for more regular sampling and partial matrix scaling algorithms with application to finding local irregularities in the data. 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.