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

随着应用领域中大规模问题的数量和规模的增长，对可伸缩且高效的解算器的需求稳步增长。为了实现这一目标，随机迭代方法无处不在：随机化使这种方法更健壮，理论上更容易处理，而廉价的迭代步骤使其可伸缩和并行化，并允许步骤设计的灵活性。此外，数据通常具有一些算法可以利用的底层结构，要构建真正灵活和强大的随机迭代算法，我们需要学习如何有效地使用这些信息。本项目的总体目标是促进对数据感知和任务适应的探索阶段如何为随机算法的迭代步骤的设计提供信息的理解，以指导他们完成特定的学习任务。这类学习任务的例子包括消除腐败、探索外部知识、数据正规化或搜索多种解决方案。除了科学影响，该项目还将通过讲座、活动组织和开源代码来促进科学知识的广泛传播，并提供学生支持和研究培训机会。该项目旨在创建一系列灵活的数据和任务增强的随机迭代方法。这项工作的一个重要组成部分是开发新的相关数学工具来证明这类算法的收敛性质。算法的理论分析涉及到高维概率和几何方法、数值分析和线性代数方法以及最优化和随机矩阵理论。此外，它还促进了独立兴趣的支持结果的发展，例如结构化随机矩阵的新的谱界、测量估计的高维集中，以及更严格地控制随机迭代的新的几何和概率方法。该项目计划的副产品包括新的腐败--广泛用于压缩传感、低阶张量拟合和一阶随机优化的算法的稳健变体；增加了辅助知识的新的线性求解器及其在寻找偏微分方程组和常微分方程组的多个解方面的应用；以及数据感知的迭代算法，用于更规则的采样和部分矩阵缩放算法，并应用于发现数据中的局部不规则性。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.