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 try to incorporate machine learning components in algorithm design.  Historically, such algorithmic techniques have come with no performance guarantees.  In this talk, I will describe our recent work that helps put this data-driven algorithm design approach on firm foundation. I will describe both specific case studies and general principles applicable broadly to a variety of combinatorial problems. I will also discuss how we can leverage this work to loop back and help analyze learned machine learning algorithms themselves!

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 the recipient of numerous honors and awards including being an ACM fellow and the recipient of the ACM Grace Murray Hopper Award, a Simons Investigator Award, a Microsoft Faculty Research Fellowship, a Sloan Research Fellowship, an NSF CAREER Award, the CMU SCS Distinguished Dissertation Award, and paper awards at COLT, ACM-EC, and UAI. She also held several major leadership positions including co-chairing important 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, being the general chair for ICML 2021, and co-organizing the Simons semester on Foundations of Machine Learning in 2017.