The exact worst-case convergence rate of the gradient method with fixed step lengths for L-smooth functions

Hadi Abbaszadehpeivasti; Etienne de Klerk; Moslem Zamani

doi:10.1007/s11590-021-01821-1

The exact worst-case convergence rate of the gradient method with fixed step lengths for L-smooth functions

Hadi Abbaszadehpeivasti, Etienne de Klerk, Moslem Zamani^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › Scientific › peer-review

5 Citations (Scopus)

112 Downloads (Pure)

Abstract

In this paper, we study the convergence rate of the gradient (or steepest descent) method with fixed step lengths for finding a stationary point of an L-smooth function. We establish a new convergence rate, and show that the bound may be exact in some cases, in particular when all step lengths lie in the interval (0,1/L]. In addition, we derive an optimal step length with respect to the new bound.

Original language	English
Pages (from-to)	1649–1661
Journal	Optimization Letters
Volume	16
Issue number	6
DOIs	https://doi.org/10.1007/s11590-021-01821-1
Publication status	Published - Jul 2022

Keywords

l-smooth optimization
gradient method
performance estomation prolem
semidefinite programming

Access to Document

10.1007/s11590-021-01821-1

Gradient_descent_fixed_steps_v5 (Moslem Zamani's conflicted copy 2021-10-06)Accepted author manuscript, 420 KB

https://arxiv.org/abs/2104.05468

Cite this

@article{061688c6f97c4024bb5b1c81a859694d,

title = "The exact worst-case convergence rate of the gradient method with fixed step lengths for L-smooth functions",

abstract = "In this paper, we study the convergence rate of the gradient (or steepest descent) method with fixed step lengths for finding a stationary point of an L-smooth function. We establish a new convergence rate, and show that the bound may be exact in some cases, in particular when all step lengths lie in the interval (0,1/L]. In addition, we derive an optimal step length with respect to the new bound.",

keywords = "l-smooth optimization, gradient method, performance estomation prolem, semidefinite programming",

author = "Hadi Abbaszadehpeivasti and {de Klerk}, Etienne and Moslem Zamani",

year = "2022",

month = jul,

doi = "10.1007/s11590-021-01821-1",

language = "English",

volume = "16",

pages = "1649–1661",

journal = "Optimization Letters",

issn = "1862-4472",

publisher = "Springer Verlag",

number = "6",

}

TY - JOUR

T1 - The exact worst-case convergence rate of the gradient method with fixed step lengths for L-smooth functions

AU - Abbaszadehpeivasti, Hadi

AU - de Klerk, Etienne

AU - Zamani, Moslem

PY - 2022/7

Y1 - 2022/7

N2 - In this paper, we study the convergence rate of the gradient (or steepest descent) method with fixed step lengths for finding a stationary point of an L-smooth function. We establish a new convergence rate, and show that the bound may be exact in some cases, in particular when all step lengths lie in the interval (0,1/L]. In addition, we derive an optimal step length with respect to the new bound.

AB - In this paper, we study the convergence rate of the gradient (or steepest descent) method with fixed step lengths for finding a stationary point of an L-smooth function. We establish a new convergence rate, and show that the bound may be exact in some cases, in particular when all step lengths lie in the interval (0,1/L]. In addition, we derive an optimal step length with respect to the new bound.

KW - l-smooth optimization

KW - gradient method

KW - performance estomation prolem

KW - semidefinite programming

U2 - 10.1007/s11590-021-01821-1

DO - 10.1007/s11590-021-01821-1

M3 - Article

SN - 1862-4472

VL - 16

SP - 1649

EP - 1661

JO - Optimization Letters

JF - Optimization Letters

IS - 6

ER -

The exact worst-case convergence rate of the gradient method with fixed step lengths for L-smooth functions

Abstract

Keywords

Access to Document

Fingerprint

Cite this