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.