Machine Learning for Algorithm Design
Part of the Special ECE Seminar Series
Modern Artificial Intelligence
Title:
Machine Learning for Algorithm Design
Speaker:
Maria Florina Balcan, Cadence Design Systems Professor of Computer Science, Carnegie Mellon University
Abstract:
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.
Bio:
Maria Florina Balcan is the Cadence Design Systems Professor of Computer Science in the School of Computer Science at Carnegie Mellon University. Her main research interests are machine learning, artificial intelligence, theory of computing, and algorithmic game theory. She is a Simons Investigator, a Sloan Fellow, a Microsoft Research New Faculty Fellow, and the recipient of the ACM Grace Murray Hopper Award, NSF CAREER award, and several best paper awards. She has co-chaired major conferences in the field: the Conference on Learning Theory (COLT) 2014, the International Conference on Machine Learning (ICML) 2016, and Neural Information Processing Systems (NeurIPS) 2020. She has also been the general chair for the International Conference on Machine Learning (ICML) 2021, a board member of the International Machine Learning Society, and a co-organizer for the Simons semester on Foundations of Machine Learning.