Performance of First Order Methods for Convex Minimization: A Novel Approach

Abstract

We introduce a novel approach for analyzing the worst-case performance of first-order black-box convex optimization methods. Our approach relies on the observation that by definition, the worst-case behavior of an optimization method is by itself an optimization problem which consists of finding the maximal abolute inacurracy over all possible inputs of the algorithm, and which we call the performance estimation problem (PEP). This is an abstract and challenging optimization problem in infinite dimension which appears to be untractable. We will present a methodology to design and analyze the PEP for a broad class of first order black-box algorithms. It allows to derive new and improved complexity bounds for the gradient method, the heavy-ball method and the fast gradient schemes. We also show an efficient procedure for finding optimal step sizes which results in a first-order black-box method that achieves best worst-case performance. This is joint work with Yoel Drori.