Logo image
Back
The essential best and average rate of convergence of the exact line search gradient descent method
Journal article   Open access   Peer reviewed

The essential best and average rate of convergence of the exact line search gradient descent method

Thomas P.-Y. Yu
Numerical algorithms, Forthcoming
18 Nov 2025
DOI: https://doi.org/10.1007/s11075-025-02244-0
Featured in Collection :   Research Supported by Drexel Libraries' OA Programs
url
https://doi.org/10.1007/s11075-025-02244-0View
Published, Version of Record (VoR)Open Access via Drexel Libraries Read and Publish Program 2025CC BY V4.0,  Open

Abstract

Gradient descent Exact line search Worst case versus average case rate of convergence Center and stable manifolds theorem Polynomial optimization problem Algorithms Optimization
t is very well known that when the exact line search gradient descent method is applied to a convex quadratic objective, the worst-case rate of convergence (ROC), among all seed vectors, deteriorates as the condition number of the Hessian of the objective grows. By an elegant analysis due to H. Akaike, it is generally believed – but not proved – that in the ill-conditioned regime the ROC for almost all initial vectors, and hence also the average ROC, is close to the worst case ROC. We complete Akaike’s analysis by determining the essential best case ROC (defined in a measure-theoretic way) by using a dynamical system approach, facilitated by the theorem of center and stable manifolds. Our analysis also makes apparent the effect of an intermediate eigenvalue in the Hessian by establishing the following amusing result: In the absence of an intermediate eigenvalue, the average ROC gets arbitrarily fast – not slow – as the Hessian gets increasingly ill-conditioned. We discuss in passing some contemporary applications of exact line search GD to well-conditioned polynomial optimization problems arising from imaging and data sciences. In particular, we observe that a tailored exact line search GD algorithm for a POP arising from the phase retrieval problem is only 50% more expensive per iteration than its constant step size counterpart, while promising a ROC only matched by the optimally tuned (constant) step size which can rarely be achieved in practice.

Metrics

7 Record Views

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Web of Science research areas
Mathematics, Applied
Logo image