Optimization Online


Exact Worst-case Performance of First-order Methods for Composite Convex Optimization

Adrien B. Taylor (adrien.taylor***at***uclouvain.be)
Julien M. Hendrickx (julien.hendrickx***at***uclouvain.be)
François Glineur (francois.glineur***at***uclouvain.be)

Abstract: We provide a framework for computing the exact worst-case performance of any algorithm belonging to a broad class of oracle-based first-order methods for composite convex optimization, including those performing explicit, projected, proximal, conditional and inexact (sub)gradient steps. We simultaneously obtain tight worst-case guarantees and explicit instances of optimization problems on which the algorithm reaches this worst-case. We achieve this by reducing the computation of the worst-case to solving a convex semidefinite program, generalizing previous works on performance estimation by Drori and Teboulle [13] and the authors [43]. We use these developments to obtain a tighter analysis of the proximal point algorithm and of several variants of fast proximal gradient, conditional gradient, subgradient and alternating projection methods. In particular, we present a new analytical worst-case guarantee for the proximal point algorithm that is twice better than previously known, and improve the standard worst-case guarantee for the conditional gradient method by more than a factor of two. We also show how the optimized gradient method proposed by Kim and Fessler in [22] can be extended by incorporating a projection or a proximal operator, which leads to an algorithm that converges in the worst-case twice as fast as the standard accelerated proximal gradient method [2].

Keywords: composite convex optimization, first-order methods, performance estimation, ex- act worst-case analysis, convergence rate, proximal point algorithm, conditional gradient method, optimized gradient method, semidefinite programming, convex interpolation

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: Accepted in SIOPT

Download: [PDF]

Entry Submitted: 06/23/2016
Entry Accepted: 06/23/2016
Entry Last Modified: 02/06/2017

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