Analytic analysis of the worst-case complexity of the gradient method with exact line search and the Polyak stepsize
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913419175657472 |
|---|---|
| author | Huang, Ya-Kui Qi, Hou-Duo |
| author_facet | Huang, Ya-Kui Qi, Hou-Duo |
| contents | We give a novel analytic analysis of the worst-case complexity of the gradient method with exact line search and the Polyak stepsize, respectively, which previously could only be established by computer-assisted proof. Our analysis is based on studying the linear convergence of a family of gradient methods, whose stepsizes include the one determined by exact line search and the Polyak stepsize as special instances. The asymptotic behavior of the considered family is also investigated which shows that the gradient method with the Polyak stepsize will zigzag in a two-dimensional subspace spanned by the two eigenvectors corresponding to the largest and smallest eigenvalues of the Hessian. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_04914 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Analytic analysis of the worst-case complexity of the gradient method with exact line search and the Polyak stepsize Huang, Ya-Kui Qi, Hou-Duo Optimization and Control We give a novel analytic analysis of the worst-case complexity of the gradient method with exact line search and the Polyak stepsize, respectively, which previously could only be established by computer-assisted proof. Our analysis is based on studying the linear convergence of a family of gradient methods, whose stepsizes include the one determined by exact line search and the Polyak stepsize as special instances. The asymptotic behavior of the considered family is also investigated which shows that the gradient method with the Polyak stepsize will zigzag in a two-dimensional subspace spanned by the two eigenvectors corresponding to the largest and smallest eigenvalues of the Hessian. |
| title | Analytic analysis of the worst-case complexity of the gradient method with exact line search and the Polyak stepsize |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2407.04914 |