# On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions

arXiv: https://arxiv.org/abs/1606.09365 · HTML: https://mlsanity.com/paper/1606.09365/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2016.

## Built on by (most cited first, 9 of 9)

- [Extragradient Method: O(1/K) Last-Iterate Convergence for Monotone Variational Inequalities and Connections With Cocoercivity](https://mlsanity.com/paper/2110.04261/) (2021)
- [Provably Faster Gradient Descent via Long Steps](https://mlsanity.com/paper/2307.06324/) (2023)
- [Searching for Optimal Per-Coordinate Step-sizes with Multidimensional Backtracking](https://mlsanity.com/paper/2306.02527/) (2023)
- [Bias-Optimal Bounds for SGD: A Computer-Aided Lyapunov Analysis](https://mlsanity.com/paper/2505.17965/) (2025)
- [Glocal Smoothness: Line search and adaptive step sizes can help in theory too!](https://mlsanity.com/paper/2506.12648/) (2025)
- [Tight analyses of first-order methods with error feedback](https://mlsanity.com/paper/2506.05271/) (2025)
- [Accelerated Evolving Set Processes for Local PageRank Computation](https://mlsanity.com/paper/2510.08010/) (2025)
- [AutoGD: Automatic Learning Rate Selection for Gradient Descent](https://mlsanity.com/paper/2510.09923/) (2025)
- [The Row Normalization Puzzle in Muon](https://mlsanity.com/paper/2609.39114/) (2026)

## Abstract (arXiv)

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].