On the Worst-case Complexity of the Gradient Method with Exact Line Search for Smooth Strongly Convex Functions
(2016) , 12 pages
Files
coredp2016_27web.pdf
Open Access - Adobe PDF
- 423.87 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 extend the result to 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 proof is computer-assisted, and relies on the resolution 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 (CORE Discussion Paper 2016/27). https://hdl.handle.net/2078.5/185787