Events

Machine Learning for Algorithm Design

Speaker: Maria Florina Balcan

Location: On-Line

Date: Tuesday, September 26, 2023

The classic textbook approach to designing and analyzing algorithms assumes worst-case instances of the problem, about which the algorithm designer has absolutely no information at all. While highly desirable when achievable, such worst-case guarantees — either for solution quality or running time or other performance measures — are often weak for many algorithmic problems. Consequently, rather than using off the shelf algorithms with weak worst-case guarantees, practitioners often employ a data-driven algorithm design approach; specifically, given an application, they use machine learning and instances of the problem from the specific domain to learn a method that works best in that domain. A major question is what provable guarantees do these learning augmented algorithmic techniques enjoy. In this talk, I will describe general analysis techniques developed in my group for data-driven algorithms. I will discuss both for the batch and online scenarios where a collection of typical problem instances from the given application are presented either all at once or in an online fashion, respectively.

Registration link: https://nyu.zoom.us/meeting/register/tJcvce-hrTopHtwz5TtXmJcl_IG-kkqoKB0J?__s=btfyudzxbjsyabimcrg5#/registration