Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
The Average Rate of Convergence of the Exact Line Search Gradient Descent Method
arXiv (Cornell University)
16 May 2023
Abstract
It 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
(among all seed vectors) deteriorates as the condition number of the Hessian of
the objective grows. By an elegant analysis by 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 using 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 somewhat
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 polynomial optimization problems arising from imaging and data sciences.
Metrics
7 Record Views
Details
- Title
- The Average Rate of Convergence of the Exact Line Search Gradient Descent Method
- Creators
- Thomas Yu
- Publication Details
- arXiv (Cornell University)
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Mathematics
- Other Identifier
- 991021878115604721