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

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

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.