Skip to Main content Skip to Navigation
Journal articles

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

Etienne de Klerk 1 François Glineur 2 Adrien Taylor 3
3 SIERRA - Statistical Machine Learning and Parsimony
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
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 self-concordant functions, including the case of inexact search directions. The analysis uses semidefinite programming performance estimation, as pioneered by Drori and Teboulle [it Math. Program., 145 (2014), pp. 451--482], and extends recent performance estimation results for the method of Cauchy by the authors [it 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 Hazan [it PMLR, 48 (2016), pp. 2520--2528].
Document type :
Journal articles
Complete list of metadatas

Cited literature [38 references]  Display  Hide  Download

https://hal.inria.fr/hal-02956367
Contributor : Adrien Taylor <>
Submitted on : Wednesday, October 7, 2020 - 12:20:39 PM
Last modification on : Wednesday, October 14, 2020 - 4:20:15 AM

File

1709.05191.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Etienne de Klerk, François Glineur, Adrien Taylor. Worst-Case Convergence Analysis of Inexact Gradient and Newton Methods Through Semidefinite Programming Performance Estimation. SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2020, 30 (3), pp.2053-2082. ⟨10.1137/19M1281368⟩. ⟨hal-02956367⟩

Share

Metrics

Record views

665

Files downloads

40