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

De Klerk, Etienne;Glineur, François;Taylor, Adrien B.
(2020) SIAM Journal on Optimization — Vol. 30, n° 3, p. 2053-2082 (2020)

Files

WORST-CASECONVERGENCEANALYSISOFINEXACTGRADIENT.pdf
  • Open Access
  • Adobe PDF
  • 590.16 KB
Download

Details

Authors
  • De Klerk, Etienneorcid-logoTilburg University, 5037 AB Tilburg, The Netherlands
    Author
  • Glineur, Françoisorcid-logoUCLouvain
    Author
  • Taylor, Adrien B.INRIA, D´epartement d’informatique de l’ENS, Ecole normale sup´erieure, CNRS, PSL Research University, Paris, France
    Author
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].
Affiliations

Citations

  • APA
  • Chicago
  • FWB

De Klerk, E., Glineur, F., & Taylor, A. B. (2020). Worst-Case Convergence Analysis of Inexact Gradient and Newton Methods Through Semidefinite Programming Performance Estimation. SIAM Journal on Optimization, 30(3), 2053-2082. https://doi.org/10.1137/19m1281368 (Original work published 2020)