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. Unfortunately, for many problems such worst-case guarantees—either for solution quality or running time or other performance measures—are often weak. Consequently, rather than using off the shelf algorithms that have 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. Historically, such algorithmic techniques have come with no performance guarantees. In this talk, I will describe our recent work that helps put data-driven algorithm design on firm foundations. I will describe both specific case studies and general principles applicable broadly to a variety of combinatorial problems
Maria Florina Balcan 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.
