Abstract
The classic theory of computing approach to designing and analyzing algorithms considers hand-designed algorithms and focuses on worst-case guarantees. Since such hand-designed algorithms have weak worst-case guarantees for many problems, in practice machine learning components are often incorporated in algorithm design. In this talk, I will describe recent work in our group that provides theoretical foundations for such learning augmented algorithms. I will describe both specific case studies (from data science to operations research to computational economics) and general principles applicable broadly to a variety of combinatorial algorithmic problems. I will then show how we can loop back and use these tools to learn machine learning algorithms themselves!