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

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

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.