We introduce a novel approach for analyzing the performance of first-order blackbox optimization methods. We focus on smooth unconstrained convex minimization over the Euclidean space R d . Our approach relies on the observation that by definition, the worst case behavior of a black-box optimization method is by itself an optimization problem, which we call the Performance Estimation Problem (PEP). We formulate and analyze the PEP for two classes of first-order algorithms. We first apply this approach on the classical gradient method and derive a new and tight analytical bound on its performance. We then consider a broader class of first-order black-box methods, which among others, include the so-called heavy-ball method and the fast gradient schemes. We show that for this broader class, it is possible to derive new numerical bounds on the performance of these methods by solving an adequately relaxed convex semidefinite PEP. Finally, we show an efficient procedure for finding optimal step sizes which results in a first-order black-box method that achieves best performance.
The first among them is REF , in which Drori and Teboulle developed an SDP to derive analytical/numerical bounds on the worst-case performance of the unconstrained gradient method and its accelerated variant.
Performance of first-order methods for smooth convex minimization: a novel approach
arXiv: Optimization and Control
Mathematics Computer Science