Exact worst-case performance of first-order methods for composite convex optimization

Adrien B. Taylor (), Julien M. Hendrickx () and François Glineur
Additional contact information
Adrien B. Taylor: Université catholique de Louvain
Julien M. Hendrickx: Université catholique de Louvain

No 2016052, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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 compu- tation of the worst-case to solving a convex semidefinite program, generalizing previous works on performance estimation by Drori and Teboulle and the authors. 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 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.

Keywords: convex optimization; composite convex optimization; first-order methods; worst- case analysis; performance estimation; semidefinite programming; convex interpolation (search for similar items in EconPapers)
Date: 2016-12-31
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2016.html (application/pdf)

Related works:
Working Paper: Exact worst-case performance of first-order methods for composite convex optimization (2017)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2016052

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().