AF: Small: Foundations for Data-driven Algorithmics

Harvard University, Cambridge MA

Investigators

Abstract

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.