ORIE Colloquium: Jacob Abernethy (Georgia Tech) - Building Algorithms by Playing Games


Frank H. T. Rhodes Hall 253


A very popular trick for solving certain types of optimization problems is this: write your objective as the solution of a two-player zero-sum game, endow both players with an appropriate learning algorithm, watch how the opponents compete and extract an (approximate) solution from the actions/decisions taken by the players throughout the process. This approach is very generic and provides a natural template to produce new and interesting algorithms. I will describe this framework and show how it applies in several scenarios, and describe recent work drawing connections to classical algorithms including Frank-Wolfe and Nesterov Accelerated Gradient Descent.

Jacob Abernethy is an Associate Professor in the College of Computing at Georgia Tech. In October 2011 he finished a Ph.D. in the Division of Computer Science at the University of California at Berkeley, spent two years as a Simons postdoctoral fellow at the University of Pennsylvania, and held a faculty job at the University of Michigan for four years before joining Georgia Tech. Abernethy's primary interest is in machine learning, with a particular focus in sequential decision making, online learning, online algorithms, and adversarial learning models.