On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions
(2016) Optimization Letters — Vol. 11, n° 7, p. 1185-1199 (2017)
Files
document.pdf
Restricted Access - Adobe PDF
- 621.78 KB
Details
- Authors
- Abstract
- We consider the gradient (or steepest) descent method with exact line search applied to a strongly convex function with Lipschitz continuous gradient. We establish the exact worst-case rate of convergence of this scheme, and show that this worst-case behavior is exhibited by a certain convex quadratic function. We also give the tight worst-case complexity bound for a noisy variant of gradient descent method, where exact line-search is performed in a search direction that differs from negative gradient by at most a prescribed relative tolerance. The proofs are computer-assisted, and rely on the resolutions of semidefinite programming performance estimation problems as introduced in the paper [Y. Drori and M. Teboulle. Performance of first-order methods for smooth convex minimization: a novel approach. Mathematical Programming, 145(1-2):451-482, 2014].
- Affiliations
Citations
de Klerk, E., Glineur, F., & Taylor, A. (2016). On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions. Optimization Letters, 11(7), 1185-1199. https://doi.org/10.1007/s11590-016-1087-4 (Original work published 2017)