Algorithm Synthesis with Theoretical Guarantees
Abstract:
Algorithm configuration methods optimize the performance of parameterized heuristic algorithms on given distributions of problem instances; they can be seen as extending classical machine learning to hypothesis spaces consisting of algorithm designs. This talk will begin by defining the problem and illustrating its promise via some recent practical success stories. However, all widely used algorithm configuration methods both achieve poor asymptotic runtime performance in the worst case and optimize what I will argue is the wrong objective function. I will begin by explaining why we should leverage decision theory to maximize expected utility instead of minimizing average runtime. Then I will present a new algorithm configuration approach called Continuous, Online Utilitarian Procrastination (COUP), which optimizes this objective while offering strong theoretical guarantees. I will conclude by showing that these guarantees come effectively for free, as COUP achieves state-of-the-art empirical performance.
Bio:
Kevin Leyton-Brown is a professor of Computer Science and a Distinguished University Scholar at the University of British Columbia. He holds a Canada CIFAR AI Chair at the Alberta Machine Intelligence Institute and is an associate member of the Vancouver School of Economics. He received a PhD and an M.Sc. from Stanford University (2003; 2001) and a B.Sc. from McMaster University (1998). He studies artificial intelligence, mostly at the intersection of machine learning with either the design and operation of electronic markets or the design of heuristic algorithms. He has helped to design a government auction that reallocated North American radio spectrum; an electronic market that linked Ugandan farmers with buyers for surplus crops; and widely used open source software such as SATzilla (an algorithm portfolio for solving satisfiability problems), Mechanical TA (peer grading software used at universities around the world), and AutoWEKA (a machine learning tool that both selects a model family and optimizes its hyperparameters). He is increasingly interested in large language models, particularly as components of agent architectures. He believes we have both a moral obligation and a historical opportunity to leverage AI to benefit underserved communities, particularly in the developing world.