First-order methods of smooth convex optimization with inexact oracle

Olivier Devolder (), François Glineur and Yurii Nesterov ()
Additional contact information
Olivier Devolder: Université catholique de Louvain, CORE, B-1348 Louvain-la-Neuve, Belgium
Yurii Nesterov: Université catholique de Louvain, CORE, B-1348 Louvain-la-Neuve, Belgium

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

Abstract: In this paper, we analyze different first-order methods of smooth convex optimization employing inexact first-order information. We introduce the notion of an approximate first-order oracle. The list of examples of such an oracle includes smoothing technique, Moreau-Yosida regularization, Modified Lagrangians, and many others. For different methods, we derive complexity estimates and study the dependence of the desired accuracy in the objective function and the accuracy of the oracle. It appears that in inexact case, the superiority of the fast gradient methods over the classical ones is not anymore absolute. Contrary to the simple gradient schemes, fast gradient methods necessarily suffer from accumulation of errors. Thus, the choice of the method depends both on desired accuracy and accuracy of the oracle. We present applications of our results to smooth convex-concave saddle point problems, to the analysis of Modified Lagrangians, to the prox-method, and some others.

Keywords: smooth convex optimization; first-order methods; inexact oracle; gradient methods; fast gradient methods; complexity bounds (search for similar items in EconPapers)
Date: 2011-01-01
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (19)

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

Related works:
Working Paper: First-order methods of smooth convex optimization with inexact oracle (2014)
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:2011002

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 ().