Worst-Case Convergence Analysis of Inexact Gradient and Newton Methods Through Semidefinite Programming Performance Estimation

Etienne De Klerk, François Glineur and Adrien B. Taylor

No 3134, LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: We provide new tools for worst-case performance analysis of the gradient (or steepest descent) method of Cauchy for smooth strongly convex functions, and Newton’s method for selfconcordant functions, including the case of inexact search directions. The analysis uses semidefinite programming performance estimation, as pioneered by Drori and Teboulle [Math. Program., 145 (2014), pp. 451–482], and extends recent performance estimation results for the method of Cauchy by the authors [Optim. Lett., 11 (2017), pp. 1185–1199]. To illustrate the applicability of the tools, we demonstrate a novel complexity analysis of short step interior point methods using inexact search directions. As an example in this framework, we sketch how to give a rigorous worst-case complexity analysis of a recent interior point method by Abernethy and and Hazan [PMLR, 48 (2016), pp. 2520– 2528].

Keywords: performance estimation problems; gradient method; inexact search directions; semidefinite programming; interior point methods (search for similar items in EconPapers)
Date: 2020-01-01
Note: In : SIAM Journal on Optimization - Vol. 30, no.3, p. 2053-2082 (2020)
References: Add references at CitEc
Citations: View citations in EconPapers (6)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
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:louvrp:3134

DOI: 10.1137/19m1281368

Access Statistics for this paper

More papers in LIDAM Reprints 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 ().