Collaborative Research: AF: Small: New Connections between Optimization and Property Testing

合作研究：AF：小型：优化和性能测试之间的新联系

• 批准号: 2402571
• 负责人: Deeparnab Chakrabarty
• 金额: $ 32.73万
• 依托单位: Dartmouth College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-04-01 至 2027-03-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2402571&HistoricalAwards=false
• 关键词: Collaborative; Research; AF; Small; New

An important requirement of many scientific studies is the need to learn from vast amounts of data. Two significant aspects of this activity are addressed by this project, namely the ability to process data at scale and to construct models that can accurately predict future behavior. The first aspect is connected to sublinear algorithms, which identify small subsets of data that accurately represent the entire dataset. The second aspect is connected to optimization methods to identify underlying models that best explain existing data. This project will discover new mathematical connections between these two aspects, and this interplay will lead to both faster optimization methods and better sublinear algorithms for fundamental problems of practical relevance. Furthermore, findings of this project will enhance curricula for advanced algorithms courses and will train future generations of graduate students.Many data sets today can be characterized as collection of points in high-dimensional space, and models are functions defined over this domain. Property testing provides a rigorous approach towards inferring properties of these functions with a small sample. Optimization problems address methods to choose a point that maximizes or minimizes the function value. This project will address connections between these methods. In particular, the project uses optimization techniques for developing better property testers for canonical properties such as submodularity and (discrete) convexity, both long-standing fundamental open problems. In the other direction, the project uses techniques from property testing to design new robust algorithms for optimization problems. These methods have the potential to help explain why certain non-convex optimization problems are tractable although they are NP-hard in the worst case. This project will develop mathematical connections between algorithms and geometry, and these will be incorporated into lecture notes and expository material.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.

许多科学研究的一个重要要求是需要从大量的数据中学习。该项目解决了这一活动的两个重要方面，即大规模处理数据的能力和构建能够准确预测未来行为的模型的能力。第一个方面与次线性算法有关，该算法识别准确表示整个数据集的小数据子集。第二个方面与优化方法有关，以确定最能解释现有数据的基础模型。该项目将发现这两个方面之间新的数学联系，这种相互作用将导致更快的优化方法和更好的次线性算法，用于实际相关的基本问题。此外，本项目的研究结果将加强高级算法课程的课程，并将培养未来的研究生。今天的许多数据集可以被描述为高维空间中的点的集合，模型是在该域上定义的函数。属性测试提供了一个严格的方法来推断这些功能的小样本的属性。最优化问题解决的方法来选择一个点，最大化或最小化函数值。本项目将解决这些方法之间的联系。特别是，该项目使用优化技术来开发更好的规范属性测试程序，如子模块性和（离散）凸性，这两个长期存在的基本开放问题。在另一个方向上，该项目使用属性测试的技术来设计新的鲁棒算法来解决优化问题。这些方法有可能帮助解释为什么某些非凸优化问题是易于处理的，尽管它们在最坏的情况下是NP困难的。该项目将发展算法和几何之间的数学联系，这些将被纳入课堂讲稿和临时材料。该奖项反映了NSF的法定使命，并已被认为是值得通过评估使用基金会的智力价值和更广泛的影响审查标准的支持。