Optimization Online


Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods

A.B. Taylor (adrien.taylor***at***uclouvain.be)
J.M. Hendrickx (julien.hendrickx***at***uclouvain.be)
F. Glineur (Francois.Glineur***at***uclouvain.be)

Abstract: We show that the exact worst-case performance of fixed-step first-order methods for unconstrained optimization of smooth (possibly strongly) convex functions can be obtained by solving convex programs. Finding the worst-case performance of a black-box first-order method is formulated as an optimization problem over a set of smooth (strongly) convex functions and initial conditions. We develop closed-form necessary and sufficient conditions for smooth (strongly) convex interpolation, which provide a finite representation for those functions. This allows us to reformulate the worst-case performance estimation problem as an equivalent finite dimension-independent semidefinite optimization problem, whose exact solution can be recovered up to numerical precision. Optimal solutions to this performance estimation problem provide both worst-case performance bounds and explicit functions matching them, as our smooth (strongly) convex interpolation procedure is constructive. Our works build on those of Drori and Teboulle in [Math. Prog. 145 (1-2), 2014] who introduced and solved relaxations of the performance estimation problem for smooth convex functions. We apply our approach to different fixed-step first-order methods with several performance criteria, including objective function accuracy and gradient norm. We conjecture several numerically supported worst-case bounds on the performance of the fixed-step gradient, fast gradient and optimized gradient methods, both in the smooth convex and the smooth strongly convex cases, and deduce tight estimates of the optimal step size for the gradient method.

Keywords: Smooth strongly convex interpolation, Smooth convex optimization, Smooth strongly convex optimization, Worst-case performance of first-order algorithms

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Submitted, 2015. MATLAB code for worst-case performance estimation can be downloaded from http://perso.uclouvain.be/adrien.taylor/

Download: [PDF]

Entry Submitted: 03/11/2015
Entry Accepted: 03/11/2015
Entry Last Modified: 05/18/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society