Performance of first-order methods for smooth convex minimization: a novel approach

By Yoel Drori, Marc Teboulle. Mathematical programming, 2012

345 citations recorded by the source corpus.

We introduce a novel approach for analyzing the worst-case performance of first-order black-box optimization methods. We focus on smooth unconstrained convex minimization over the Euclidean space. 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 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 worst-case performance.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/9ecd6b04fca04bb20b051ddf5bfefc0b2d882f07

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3 (2017, background): “See Drori-Teboulle [19] and Kim-Fessler [22] for a recent account on first-order methods that achieve best performance.”
iPiano: Inertial Proximal Algorithm for Nonconvex Optimization (2014, methodology): “On strongly convex functions, both methods are equally fast (up to constants), but Nesterov’s accelerated gradient method converges much faster on weakly convex functions [17].”
Solving inverse problems using data-driven models (2019, background): “Elad and P. Milanfar (2017a), ‘The little engine that could: Regularization by denoising (RED)’, SIAM J.”
A Lyapunov Analysis of Momentum Methods in Optimization (2016, neutral): “O C ] 3 1 D”
Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints (2014, methodology): “The main drawback of the Drori and Teboulle approach is that the size of the semidefinite program scales with the number of time steps desired.”
Global convergence of the Heavy-ball method for convex optimization (2014, methodology): “First-order methods designed to find the minimum of this cost function are expected to pertain very poor convergence behavior [6].”