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.