Optimization, Complexity and Invariant Theory

Abstract: It has long been understood that endowing a convex body with a Riemannian metric derived from the Hessian of a convex function can be instrumental in controlling the convergence of flows (local algorithms) toward equilibrium. This is because such geometries come equipped with a natural Lyapunov function (the associated Bregman divergence). I will discuss the basic theory of these dynamics and how they can be used to pursue a moving target through a convex body. This leads to the resolution of some long-standing open problems in competitive analysis. The talk is based on joint works with S. Bubeck, M. Cohen, Y. T. Lee, and A. Madry.