Abstract: Often we want to design the best-possible algorithm for solving a given type of problem. Within modern optimization, this means finding a strategy for where to query gradients of an objective function that ultimately leads to the best final solution given a limited computational budget. Much recent progress in optimization theory has come from viewing this algorithm design task as, itself, a meta-optimization problem in the space of algorithms. Surprisingly, global optimization in this infinite-dimensional algorithm space can often be made tractable. This talk will discuss two such advances in the state-of-the-art for optimization theory: (1) Complete characterizations of sets of minimax optimal first-order methods and (2) Dynamically optimal methods that adapt as-well-as-possible at runtime in response to observed first-order information. Along the way, classical (beautiful) ideas from convex duality, minimax theorems, and game theory will be key tools.

Bio: Ben Grimmer is an assistant professor of applied mathematics and statistics at Johns Hopkins University, currently on sabbatical at MIT. Ben's work primarily focuses on novel methods for the design and analysis of first-order methods and is supported by AFOSR and as a Sloan Fellow. This work has received best paper prizes, including the most recent INFORMS Optimization Society's Young Researcher Prize. Some of his recent computer-assisted works have received substantial interest, being featured in popular mathematics venues like Quanta.