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

Dartmouth College, Hanover NH

Investigators

Abstract

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.