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

异常值并不像看上去那样：数据感知、灵活且稳健的随机迭代方法

• 批准号: 2309685
• 负责人: Elizaveta Rebrova
• 金额: $ 25.83万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-07-01 至 2026-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2309685&HistoricalAwards=false
• 关键词: Outliers; what; they; seem; data

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.

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