UBC Science Early Career Invited Lecture by Ellen Vitercik (Carnegie Mellon University)

Title:  Machine Learning as a Tool for Algorithm Design

Abstract:

Algorithms typically have tunable parameters that significantly influence computational efficiency and solution quality.  In practice, machine learning is a popular tool for parameter tuning:  given a set of typical problem instances from the application at hand, a machine learning approach will return a parameter setting with strong algorithmic performance on average over this set of problem instances. That parameter setting---ideally---will perform well on future problem instances as well. Learning-based approaches to algorithm configuration, however, have historically come with no provable performance guarantees.  The key challenge is that an algorithm’s performance is typically a volatile, discontinuous function of its parameters, since a small change in parameters can cause a cascade of changes in the algorithm's behavior.  In this talk, I will present work that helps solidify the foundations of algorithm configuration via machine learning, focusing on statistical performance guarantees for several widely-studied subset selection and combinatorial partitioning problems, including clustering.

Bio:

Ellen Vitercik is a PhD student in computer science at Carnegie Mellon University (CMU).  Her primary research interests are artificial intelligence, machine learning, theoretical computer science, and the interface between economics and computation.  Among other honors, she is a recipient of the IBM PhD Fellowship, the Fellowship in Digital Health from CMU's Center for Machine Learning and Health, and the NSF Graduate Research Fellowship.

Host:  Kevin Leyton-Brown