AF: Small: Foundations for Data-driven Algorithmics

传统的优化方法假设底层目标是已知的，但在许多实际应用中，真正的目标是未知的，并从数据中学习。理论与实践之间的这种差距是相当显著的，并且使我们无法保证在此类应用中优化算法的性能。该项目的目标是为从数据中学习输入（即目标）的算法开发一种理论，并设计在这些设置中表现良好的算法。这个领域的技术挑战非常重要，但它们的解决方案将极大地影响我们在计算机科学方面的思维，并导致人工智能的重大进步。该项目开发优化和数据科学课程，培养跨学科方法。该项目将包括指导来自代表性不足群体的本科生和研究生，并促进开放获取研究文化。研究者将通过课程、研讨会和工作坊来发展新的跨学科联系，目的是促进研究人员在信息时代的算法方面的研究。根据研究者最近提出的一系列不可能的结果，这个项目的目标是研究优化的替代概念，这些概念可以促进数据驱动优化的理想保证。这个项目的第一个方向是考虑自适应样本的优化。令人惊讶的是，适应性的一般概念还没有得到充分的探索，在这方面的进展可以对理论和应用产生巨大的影响。一个互补的方向是考虑在训练数据集上给定样本的算法，并寻求从相同分布中提取的测试数据集的近似最优解。最后，考虑的最后一个方向是两两比较的优化方向。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The traditional approach in optimization assumes that the underlying objective is known, but in many real-life applications, the true objectives are not known and learned from data. This gap between theory and practice turns out to be quite dramatic, and leaves us without guarantees on the performance of optimization algorithms in such applications. The goal of this project is to develop a theory for algorithms whose input (i.e., the objective) is learned from data, and design algorithms that perform well in these settings. The technical challenges in this space are highly non-trivial, but their solution would dramatically impact our thinking in computer science and result in major advancements in AI. The project develops courses in optimization and data science that foster an interdisciplinary approach. The project will involve mentoring undergraduate and graduate students from underrepresented groups and promote an open access research culture. The investigator will develop new interdisciplinary connections through courses, seminars, and workshops with the goal of promoting a discipline of researchers working on algorithms for the information age.In light of a recent line of impossibility results initiated by the investigator, the goal of this project is to investigate alternative notions of optimization that can facilitate desirable guarantees for data-driven optimization. The first direction in this project considers optimization from adaptive samples. The general notion of adaptivity is surprisingly under-explored, and advancement on this front can have a tremendous impact both on theory and applications. A complementary direction is to consider algorithms that are given samples on a training datasets, and seek to approximate the optimal solution of the testing dataset, drawn from the same distribution. Finally, the last direction considered is that of optimization from pairwise comparisons.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.